by Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran
This repository contains comprehensive implementations of algorithms from the classic textbook "Fundamentals of Computer Algorithms" (Second Edition) by Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran.
The repository serves as a practical companion to the theoretical concepts presented in the book, providing working code examples, implementations, and additional resources for students, educators, and algorithm enthusiasts.
Fundamentals-Of-Computer-Algorithms/
β
βββ Chapter_01/ # Introduction to Algorithms and Complexity Analysis
βββ Chapter_02/ # Divide and Conquer Algorithms
βββ Chapter_03/ # Greedy Algorithms
βββ Chapter_04/ # Dynamic Programming
βββ Chapter_05/ # Basic Traversal and Search Techniques
βββ Chapter_06/ # Backtracking Algorithms
βββ Chapter_07/ # Branch and Bound Algorithms
βββ Chapter_08/ # Algebraic Algorithms
βββ Chapter_09/ # Lower Bound Theory and NP-Hard/NP-Complete Problems
βββ Chapter_10/ # (Concepts only - likely Approximation Algorithms)
βββ Chapter_11/ # Parallel Algorithms
βββ Chapter_12/ # Computational Geometry
βββ Chapter_13/ # Selected Topics and Advanced Algorithms
β βββ Algorithm/ # Specialized algorithm implementations
βββ Multithread/ # Multithreading and parallel computing examples
βββ TimeCalculation.cpp # Performance analysis and timing utilities
βββ README.md # This documentation file
- Algorithm definition and properties
- Complexity analysis (Big O, Big Ξ©, Big Ξ)
- Time and space complexity
- Asymptotic notations
- Algorithm design paradigms overview
- Binary search
- Merge sort
- Quick sort
- Strassen's matrix multiplication
- Closest pair of points
- Maximum subarray problem
- Activity selection problem
- Huffman coding
- Fractional knapsack problem
- Job sequencing with deadlines
- Minimum spanning trees (Prim's, Kruskal's)
- Dijkstra's shortest path algorithm
- Fibonacci numbers
- 0/1 Knapsack problem
- Matrix chain multiplication
- Longest common subsequence
- Traveling salesman problem
- Bellman-Ford algorithm
- Floyd-Warshall algorithm
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Topological sorting
- Connected components
- Biconnected components
- Strongly connected components
- N-Queens problem
- Sum of subsets
- Graph coloring
- Hamiltonian cycles
- 0/1 Knapsack (backtracking approach)
- Maze solving problems
- 0/1 Knapsack (branch and bound)
- Traveling salesman problem
- Assignment problem
- Job scheduling
- Lower bound calculations
- Polynomial evaluation
- Fast Fourier Transform (FFT)
- Matrix operations
- Polynomial multiplication
- Solving linear equations
- Decision problems
- P, NP, NP-Complete, NP-Hard classes
- Reduction techniques
- Satisfiability (SAT) problem
- Vertex cover, clique, Hamiltonian cycle
- Approximation algorithms introduction
- Parallel computing models
- PRAM (Parallel Random Access Machine)
- Parallel sorting algorithms
- Parallel search algorithms
- Parallel matrix operations
- Load balancing techniques
- Convex hull algorithms (Graham's scan, Jarvis march)
- Line segment intersection
- Closest pair of points (divide and conquer)
- Range searching
- Voronoi diagrams
- Geometric transformations
- Randomized algorithms
- String matching algorithms
- Number theoretic algorithms
- Graph algorithms
- Advanced data structures
- External sorting algorithms
- Thread synchronization examples
- Parallel algorithm implementations
- Concurrent data structures
- Performance comparison examples
- C++ Compiler (G++ 7.0+ or equivalent)
- Basic understanding of data structures
- Familiarity with algorithm analysis
# Compile a specific algorithm
g++ -std=c++11 -O2 Chapter_02/MergeSort.cpp -o mergesort
# Compile with debugging information
g++ -std=c++11 -g Chapter_03/Dijkstra.cpp -o dijkstra
# Compile timing utilities
g++ -std=c++11 TimeCalculation.cpp -o timer# Run a compiled algorithm
./mergesort
# Test with custom input
echo "5 3 8 1 9 2" | ./quicksort
# Measure algorithm performance
./timer --algorithm="quicksort" --size=10000| Chapter | Title | Completion | Key Algorithms |
|---|---|---|---|
| 01 | Introduction to Algorithms | β | Complexity analysis tools |
| 02 | Divide and Conquer | β | MergeSort, QuickSort, Binary Search |
| 03 | Greedy Algorithms | β | Dijkstra, Prim's, Huffman Coding |
| 04 | Dynamic Programming | β | Knapsack, LCS, Matrix Chain |
| 05 | Basic Traversal | β | BFS, DFS, Topological Sort |
| 06 | Backtracking | β | N-Queens, Graph Coloring |
| 07 | Branch and Bound | β | 0/1 Knapsack (B&B), TSP |
| 08 | Algebraic Algorithms | β | Polynomial operations, FFT |
| 09 | NP-Completeness | β | SAT reductions, Vertex Cover |
| 10 | (Theoretical/No implementations) | π | Concepts only |
| 11 | Parallel Algorithms | β | Parallel sorts, PRAM models |
| 12 | Computational Geometry | β | Convex Hull, Closest Pair |
| 13 | Selected Topics | β | String matching, Randomized algos |
| Extra | Multithreading | β | Parallel implementations |
- 350+ individual algorithm implementations
- Covers all major algorithm design paradigms
- Includes both classic and advanced algorithms
- Well-commented code for easy understanding
- Step-by-step algorithm execution traces
- Complexity analysis for each implementation
- Comparative performance metrics
TimeCalculation.cppfor benchmarking- Test cases with various input sizes
- Visualization-ready output formats
- Multithreading examples
- Consistent coding style and conventions
- Modular and reusable components
- Error handling and input validation
- Memory management best practices
# Run basic tests
./test_runner --chapter=all
# Benchmark specific algorithms
./benchmark --algorithm="quicksort" --iterations=100
# Validate correctness
./validator --input=test_cases/ --algorithm="dijkstra"Test coverage includes:
- Unit tests for individual functions
- Integration tests for complete algorithms
- Stress tests for large inputs
- Correctness verification against known results
- Start with Chapter 1 (Complexity Analysis)
- Move to Chapter 5 (Basic Traversal)
- Practice Chapter 2 (Divide and Conquer)
- Explore Chapter 3 (Greedy Algorithms)
- Master Chapter 4 (Dynamic Programming)
- Understand Chapter 6 (Backtracking)
- Study Chapter 9 (NP-Completeness)
- Experiment with Multithreading examples
- Dive into Chapter 11 (Parallel Algorithms)
- Explore Chapter 12 (Computational Geometry)
- Implement Chapter 13 (Advanced Topics)
- Contribute optimizations and new algorithms
We welcome contributions! Here's how you can help:
- Bug reports
- Implementation errors
- Missing algorithms
- Documentation improvements
- Optimize existing implementations
- Add missing algorithms (especially Chapter 10)
- Improve test coverage
- Add visualizations or explanations
- Use C++11/14/17 features appropriately
- Follow consistent naming conventions
- Add detailed comments
- Include time/space complexity analysis
- Provide test cases
- Update algorithm descriptions
- Add usage examples
- Include mathematical formulations
- Reference textbook pages
The TimeCalculation.cpp utility provides:
- Execution time measurement
- Memory usage tracking
- Comparative analysis between algorithms
- Scalability testing with increasing input sizes
- Complexity validation against theoretical bounds
Example output:
Algorithm: QuickSort
Input Size: 10000
Execution Time: 15.2 ms
Memory Usage: 4.2 MB
Comparisons: 120,453
Theoretical Complexity: O(n log n) β
- Fundamentals of Computer Algorithms (2nd Ed.)
- Introduction to Algorithms (CLRS)
- Algorithm Design Manual
- VisualGo - Algorithm visualizations
- LeetCode - Coding practice
- GeeksforGeeks - Algorithm tutorials
- Ellis Horowitz - For foundational algorithm concepts
- Sartaj Sahni - For comprehensive algorithm design techniques
- Sanguthevar Rajasekaran - For parallel and advanced algorithms
- Feroz455 - Repository maintainer and primary contributor
- Open source community - For inspiration and collaboration
This repository serves students and educators worldwide in understanding computer algorithms through practical implementation.
This repository is intended for educational and learning purposes. The implementations are created to help students understand algorithms from the textbook.
All algorithms are based on "Fundamentals of Computer Algorithms" (2nd Edition). Please support the authors by purchasing the official textbook.
- Free for educational use
- Attribute to original authors when used
- Not for commercial redistribution
- Respect intellectual property rights
| Metric | Value |
|---|---|
| Total Files | 350+ |
| Lines of Code | 50,000+ |
| Total Commits | 359 |
| First Commit | Mar 10, 2022 |
| Last Update | Jun 20, 2022 |
| Primary Language | C++ (100%) |
| Contributors | 1+ |
If this repository helps you in your algorithm studies:
- β Star the repository to show your support
- π Share with classmates and colleagues
- π Report issues you encounter
- π‘ Suggest improvements or new features
- π Fork and contribute to make it better
For questions, suggestions, or collaboration:
- GitHub Issues: Open an Issue
- Educational Use: Suitable for classroom demonstrations
- Research Reference: Cite as a practical implementation resource
Happy Learning and Coding! π
Master the fundamentals, and you can build anything.
Last Updated: December 2024 | Maintainer: Feroz455
