amh1k/daa-algorithm-visualizer
0
1---2title: DAA Algorithm Visualizer3emoji: 📊4colorFrom: blue5colorTo: green6sdk: docker7app_port: 78608pinned: false9---10 11# Design and Analysis of Algorithms - Project 202512 13[](https://isocpp.org/)14[](https://nextjs.org/)15[](https://reactjs.org/)16[](https://www.typescriptlang.org/)17[](LICENSE)18 19A comprehensive collection of divide-and-conquer algorithm implementations with **professional web-based visualizations** for the Design and Analysis of Algorithms course.20 21## 👥 Team Members22 23| Name | Roll Number |24|------|-------------|25| **Huzaifa Abdul Rehman** | 23k-0782 |26| **Abdul Moiz Hossain** | 23k-0553 |27| **Ajay Kumar** | 23K-0514 |28 29---30 31## 📋 Table of Contents32 33- [About the Project](#about-the-project)34- [Features](#features)35- [Technologies Used](#technologies-used)36- [Project Structure](#project-structure)37- [Problem Implementations](#problem-implementations)38 - [Question 1: Basic Algorithms](#question-1-basic-algorithms)39 - [Question 2: Advanced Visualization](#question-2-advanced-visualization)40- [How to Run](#how-to-run)41- [Screenshots](#screenshots)42- [Time Complexity Analysis](#time-complexity-analysis)43- [Contributing](#contributing)44 45---46 47## 🎯 About the Project48 49This project showcases **13 algorithmic implementations** focusing on the **Divide and Conquer** paradigm, featuring:50 51- 📊 **Interactive Web Visualizations** - Step-by-step algorithm execution52- 🎨 **Modern UI/UX** - Dark mode, glassmorphism, smooth animations53- ⚡ **High Performance** - Optimized C++ backend with Next.js frontend54- 📈 **Comprehensive Testing** - 40+ test cases with benchmark dashboard55- 🎓 **Educational Value** - Clear explanations and visual learning56 57---58 59## ✨ Features60 61### 🌐 Web Application (Question 2)62- **Beautiful Landing Page** with animated gradient backgrounds63- **Interactive Visualizations**:64 - Closest Pair: Step-by-step divide-and-conquer animation65 - Integer Multiplication: Recursive tree visualization66- **Dark/Light Mode** with system preference detection67- **Multiple Input Methods**: Predefined files, custom upload, manual entry68- **Real-time Performance Metrics** with benchmark dashboard69- **Responsive Design** - works on all screen sizes70- **Professional UI Components** using shadcn/ui and Radix UI71 72### 🔢 Algorithm Implementations (Question 1 & 2)73- **13 C++ Implementations** covering classic divide-and-conquer problems74- **Optimized Code** with `-O2` compilation flags75- **Detailed Output** including execution time and complexity analysis76- **Test Data Generation** for comprehensive testing77 78---79 80## 🛠️ Technologies Used81 82### Backend83-  **C++11/14** - Algorithm implementation84- **STL** - Data structures and algorithms85- **Chrono** - High-precision time measurement86 87### Frontend88-  **Next.js 14.1** - React framework with App Router89-  **React 18.2** - UI library90-  **TypeScript 5.3** - Type safety91-  **Tailwind CSS 3.4** - Utility-first styling92- **Framer Motion** - Smooth animations93- **Recharts** - Performance charts94- **shadcn/ui** - Modern UI components95 96---97 98## 📁 Project Structure99 100```101Daa-Project/102│103├── README.md # Main documentation104├── GIT_CHEAT_SHEET.md # Git collaboration guide105├── INSTRUCTIONS.md # Quick setup guide106├── .gitignore # Git ignore rules107│108├── q1/ # Question 1: Basic Algorithms109│ ├── a.cpp # Algorithm A110│ ├── b.cpp # Binary Exponentiation111│ ├── c.cpp # Counting Inversions112│ ├── e.cpp # Algorithm E113│ ├── f.cpp # Peak Element Finder114│ ├── g.cpp # Maximum Stock Profit115│ ├── h_1.cpp # Median of Two Arrays (Method 1)116│ ├── h_2.cpp # Median of Two Arrays (Method 2)117│ └── h_3.cpp # Median of Two Arrays (Method 3)118│119└── q2/ # Question 2: Advanced Visualization120 ├── closest_pair.cpp # Closest Pair Algorithm (247 lines)121 ├── integer_multiplication.cpp # Karatsuba Multiplication (214 lines)122 │123 ├── test_data/ # Test Files (40+ files)124 │ ├── closest_pair/ # 10 point datasets (100-1000 points)125 │ └── integer_multiplication/ # 10 digit datasets (100-1000 digits)126 │127 └── ui/ # Next.js Web Application128 ├── app/ # Pages & API Routes129 │ ├── page.tsx # Landing page130 │ ├── closest-pair/ # Closest pair visualization page131 │ ├── integer-multiplication/ # Karatsuba visualization page132 │ ├── benchmark/ # Performance dashboard133 │ └── api/ # API endpoints (5 routes)134 │135 ├── components/ # React Components (22 components)136 │ ├── closest-pair-step-visualization.tsx137 │ ├── recursive-tree.tsx138 │ ├── static-points-canvas.tsx139 │ ├── navigation.tsx140 │ ├── theme-provider.tsx141 │ └── ui/ # shadcn/ui components142 │143 ├── lib/ # Utilities144 ├── public/ # Static assets145 └── styles/ # Global styles146```147 148---149 150## 💡 Problem Implementations151 152### Question 1: Basic Algorithms153 154#### 1. Binary Exponentiation (`b.cpp`)155**Problem**: Compute `a^b` efficiently using divide and conquer.156- **Time Complexity**: O(log b)157- **Space Complexity**: O(log b) - recursion stack158- **Approach**: Exponentiation by squaring159```cpp160// If b is even: a^b = (a^(b/2))^2161// If b is odd: a^b = (a^(b/2))^2 × a162```163 164#### 2. Counting Inversions (`c.cpp`)165**Problem**: Count pairs (i, j) where i < j but arr[i] > arr[j].166- **Time Complexity**: O(n log n)167- **Space Complexity**: O(n)168- **Approach**: Modified merge sort169 170#### 3. Peak Element Finder (`f.cpp`)171**Problem**: Find an element greater than or equal to its neighbors.172- **Time Complexity**: O(log n)173- **Space Complexity**: O(log n) - recursion stack174- **Approach**: Binary search on array175 176#### 4. Maximum Stock Profit (`g.cpp`)177**Problem**: Find maximum profit from buying and selling stocks.178- **Time Complexity**: O(n log n)179- **Space Complexity**: O(n)180- **Approach**: Divide and conquer on difference array181 182#### 5. Median of Two Sorted Arrays (`h_1.cpp`, `h_2.cpp`, `h_3.cpp`)183**Problem**: Find n-th smallest element from two sorted arrays.184- **Time Complexity**: O(log n)185- **Space Complexity**: O(1)186- **Approach**: Binary search on partitions187 188---189 190### Question 2: Advanced Visualization191 192#### 🎯 Algorithm 1: Closest Pair of Points193 194**File**: `q2/closest_pair.cpp` (247 lines)195 196**Problem**: Find the two closest points among n points in 2D space.197 198**Algorithm**: Divide and Conquer199- **Time Complexity**: O(n log n)200- **Space Complexity**: O(n)201 202**Implementation Features**:203- ✅ Sorts points by x and y coordinates204- ✅ Recursively divides plane into halves205- ✅ Checks strip area for cross-boundary pairs206- ✅ Generates JSON trace for visualization (n ≤ 50)207- ✅ Handles 100-1000 point datasets208 209**Visualization Features**:210- 🎨 Step-by-step animation with playback controls211- 📍 Divide line visualization (red dashed)212- 🎯 Active region highlighting (teal)213- 🟣 Strip area visualization (purple)214- ✅ Closest pair highlighting (green)215- ⏯️ Play, pause, step forward/backward controls216- 📊 Progress tracking with step descriptions217 218---219 220#### 🔢 Algorithm 2: Karatsuba Integer Multiplication221 222**File**: `q2/integer_multiplication.cpp` (214 lines)223 224**Problem**: Multiply arbitrarily large integers efficiently.225 226**Algorithm**: Karatsuba's Fast Multiplication227- **Time Complexity**: O(n^1.585) where n = number of digits228- **Space Complexity**: O(n)229 230**Implementation Features**:231- ✅ String-based arithmetic for large numbers232- ✅ Recursive three-way split (z2, z0, z1)233- ✅ Generates tree visualization (≤50 digits)234- ✅ Handles 100-1000+ digit multiplication235- ✅ Falls back to naive method for small numbers236 237**Visualization Features**:238- 🌳 Interactive recursive tree display239- 🎨 Color-coded node types:240 - 🟣 Purple - Root (original multiplication)241 - 🔵 Blue - z₂ (high digits: a × c)242 - 🟢 Green - z₀ (low digits: b × d)243 - 🟠 Orange - z₁ (middle term)244- 🔍 Zoom controls (30%-150%)245- 🖱️ Pan with left-click drag246- 📏 Smart number truncation for readability247- 📊 Depth and digit count tracking248 249---250 251## 🚀 How to Run252 253### Prerequisites254- **Node.js** v18 or higher255- **npm** or **yarn** package manager256- **C++ Compiler** (g++/MinGW/MSVC)257- **Git** (optional)258 259### Quick Start (Question 2 - Web Application)260 261#### Step 1: Clone Repository262```bash263git clone https://github.com/amh1k/Daa-Project.git264cd Daa-Project265```266 267#### Step 2: Compile C++ Programs268```bash269cd q2270g++ -O2 closest_pair.cpp -o closest_pair.exe271g++ -O2 integer_multiplication.cpp -o integer_multiplication.exe272```273 274#### Step 3: Install Dependencies275```bash276cd ui277npm install278```279 280#### Step 4: Run Development Server281```bash282npm run dev283```284 285#### Step 5: Open Browser286Navigate to: **http://localhost:3000**287 288---289 290### Running Question 1 Algorithms291 292```bash293# Navigate to q1 directory294cd q1295 296# Compile and run any algorithm297g++ b.cpp -o b.exe298./b.exe299 300# Example: Binary Exponentiation301echo "2 10" | ./b.exe302# Output: 1024303 304# Example: Counting Inversions305./c.exe306# Output: The number of inversions are: 22307```308 309---310 311## 📸 Screenshots312 313### 🏠 Landing Page (Dark Mode)314315*Beautiful gradient animations with glassmorphism effects, featuring three main algorithm sections*316 317### 🌞 Light Mode Support318319*Professional light theme with optimal contrast and accessibility*320 321### 📍 Closest Pair Visualization322323*Step-by-step divide-and-conquer animation with playback controls, divide line visualization, and active region highlighting*324 325**Features:**326- Interactive canvas visualization327- Play, pause, step forward/backward controls328- Real-time algorithm step descriptions329- Multiple input methods (predefined, custom, manual)330- Compact footer legend with color coding331 332### 🔢 Integer Multiplication - Karatsuba Algorithm333334*Large number multiplication with result display and performance metrics*335 336**Features:**337- Support for 100-1000+ digit numbers338- Instant calculation results339- Execution time tracking340- Clean result presentation341 342### 🌳 Recursive Tree Visualization343344*Interactive tree showing Karatsuba's recursive breakdown with color-coded node types (z₀, z₁, z₂)*345 346**Features:**347- Expand view with zoom controls (30%-150%)348- Pan with left-click drag349- Shrink button for compact view350- Color-coded nodes: Purple (Root), Blue (z₂), Green (z₀), Orange (z₁)351- Horizontal scrollbar for wide trees352- Smart number truncation for readability353 354### 📊 Benchmark Dashboard355356*Comprehensive performance testing with real-time progress tracking for all 20 test cases*357 358**Features:**359- Batch execution of all test files360- Real-time progress indicators361- Side-by-side performance comparison362- Success/failure status for each test363- Execution time metrics364- Dataset size information365 366---367 368## ⏱️ Time Complexity Analysis369 370| Algorithm | Problem | Time Complexity | Space Complexity | Lines of Code |371|-----------|---------|-----------------|------------------|---------------|372| **Binary Exponentiation** | Compute a^b | O(log b) | O(log b) | ~30 |373| **Counting Inversions** | Count inversions | O(n log n) | O(n) | ~50 |374| **Peak Element** | Find peak | O(log n) | O(log n) | ~40 |375| **Max Stock Profit** | Maximum profit | O(n log n) | O(n) | ~60 |376| **Median of Arrays** | Find median | O(log n) | O(1) | ~70 |377| **Closest Pair** | 2D point distance | O(n log n) | O(n) | 247 |378| **Karatsuba Multiply** | Large integer multiplication | O(n^1.585) | O(n) | 214 |379 380---381 382## 🎓 Key Concepts Demonstrated383 384### Algorithmic Techniques385- ✅ **Divide and Conquer** - Breaking problems into smaller subproblems386- ✅ **Binary Search** - Efficient searching in sorted/partially sorted data387- ✅ **Merge Sort** - Efficient sorting with additional applications388- ✅ **Dynamic Problem Solving** - Converting problems to known formats389- ✅ **Optimization** - Achieving logarithmic and linearithmic complexities390 391### Software Engineering392- ✅ **Full-Stack Development** - C++ backend + React frontend393- ✅ **API Design** - RESTful endpoints with error handling394- ✅ **Component Architecture** - Reusable React components395- ✅ **Type Safety** - TypeScript for robust code396- ✅ **Performance Optimization** - Lazy loading, caching, GPU acceleration397- ✅ **Responsive Design** - Mobile-first approach398- ✅ **Accessibility** - WCAG-compliant UI399 400### UI/UX Design401- ✅ **Modern Design Patterns** - Glassmorphism, gradients402- ✅ **Smooth Animations** - Framer Motion for professional feel403- ✅ **Dark Mode** - System preference detection404- ✅ **Interactive Visualizations** - Canvas & SVG rendering405- ✅ **User Feedback** - Loading states, progress bars, error messages406 407---408 409## 📚 Educational Value410 411### For Students412- 📖 **Step-by-step algorithm execution** - Visual learning413- 💡 **Clear complexity explanations** - Understand time/space trade-offs414- 🧪 **Multiple test cases** - Edge case handling415- 📊 **Performance comparison** - Benchmark different inputs416 417### For Instructors418- ✅ **Production-ready code** - Demonstrates best practices419- ✅ **Comprehensive documentation** - Easy to understand and grade420- ✅ **Interactive demos** - Use in lectures421- ✅ **Extensible architecture** - Students can add more algorithms422 423---424 425## 🔧 Advanced Features426 427### Performance Optimization428- **C++ Backend**: `-O2` optimization flags429- **React Frontend**: Code splitting, lazy loading430- **Canvas Rendering**: GPU-accelerated drawing431- **Smart Caching**: Webpack build optimization432 433### Error Handling434- ✅ Executable validation435- ✅ Input file validation436- ✅ Parse error detection437- ✅ Timeout handling (30s limit)438- ✅ User-friendly error messages439 440### Testing441- 40+ predefined test files442- Custom file upload support443- Manual input validation444- Edge case coverage445- Performance benchmarking446 447---448 449## 🤝 Contributing450 451This is an academic project. For improvements:452 4531. Fork the repository4542. Create feature branch: `git checkout -b feature/improvement`4553. Commit changes: `git commit -m 'Add improvement'`4564. Push to branch: `git push origin feature/improvement`4575. Open Pull Request458 459---460 461## 📧 Contact462 463For questions or discussions:464 465- **Huzaifa Abdul Rehman** - 23k-0782466- **Abdul Moiz Hossain** - 23k-0553467- **Ajay Kumar** - 23K-0514468 469---470 471## 📄 License472 473This project is created for educational purposes as part of the Design and Analysis of Algorithms course (CS302 - 5th Semester).474 475---476 477## 🙏 Acknowledgments478 479### References480- **Introduction to Algorithms (CLRS)** - Algorithm theory481- **GeeksforGeeks & LeetCode** - Problem-solving inspiration482- **Next.js Documentation** - Web framework guidance483- **shadcn/ui** - Component library484- **Framer Motion** - Animation library485 486### Inspiration487- Algorithm visualization tools (VisuAlgo, Algorithm Visualizer)488- Professional web applications (Figma, VS Code)489- Academic research papers on divide-and-conquer490 491---492 493## 📊 Project Statistics494 495- **Total Files**: 2,800+ (including dependencies)496- **Custom Code**:497 - 13 C++ algorithm implementations498 - 22 React components499 - 5 API routes500 - 40+ test data files501- **Lines of Code**:502 - C++: 600+ lines503 - TypeScript/TSX: 3,000+ lines504- **Test Coverage**: 20 comprehensive test cases505- **Supported Input Sizes**:506 - Closest Pair: 10-1000 points507 - Integer Multiplication: 12-1000+ digits508 509---510 511## 🎯 Project Achievements512 513✅ Complete implementation of 13 divide-and-conquer algorithms514✅ Professional web application with modern tech stack515✅ Interactive visualizations demonstrating algorithm internals516✅ Comprehensive test suite with 40+ test cases517✅ Beautiful UI design with dark mode support518✅ Performance benchmarking capabilities519✅ Educational documentation for learning520✅ Multiple input methods for flexibility521✅ Robust error handling and validation522✅ Production-ready deployment capability523 524---525 526## 🚀 Future Enhancements527 528- [ ] Add more algorithms (Quick Sort, Heap Sort, etc.)529- [ ] Export visualization as GIF/Video530- [ ] Mobile app version531- [ ] Algorithm complexity calculator532- [ ] User accounts and saved visualizations533- [ ] Collaborative features534- [ ] Multi-language support535 536---537 538**⭐ If you find this repository helpful, please consider giving it a star!**539 540---541 542**Repository**: https://github.com/amh1k/Daa-Project543