This repository contains implementations of fundamental algorithms and data structures as part of the Design and Analysis of Algorithms course. All implementations are written in C language with a focus on efficiency, readability, and proper analysis.
- Overview
- Assignment List
- How to Run
- Implementation Details
- Time and Space Complexity
- Contributing
- Resources
This repository is organized into assignment folders, each containing implementations of specific algorithms. The focus is on understanding fundamental algorithm design paradigms and analyzing their efficiency.
- Linear Search: Simple sequential search algorithm
- Binary Search: Efficient search algorithm for sorted arrays
- Merge Sort: Divide and conquer sorting algorithm
- Quick Sort: Efficient sorting method with partitioning
- Maximum and Minimum Element: Finding max/min using divide and conquer
- Strassen's Matrix Multiplication: Optimized matrix multiplication
- Depth First Search (DFS): Graph traversal algorithm
- Breadth First Search (BFS): Level-order traversal of graphs
- Dijkstra's Algorithm: Finding shortest path in weighted graphs
- N-Queen Problem: Classic backtracking challenge
- 0/1 Knapsack Problem: Optimization using dynamic programming
- Fractional Knapsack: Greedy approach to knapsack problem
- Job Sequencing: Scheduling jobs for maximum profit
-
Clone the repository:
git clone https://github.com/yourusername/DAA-ASSIGNMENTS.git
-
Navigate to the desired algorithm folder:
cd "DAA ASSIGNMENTS/ASSIGNMENT XX"
-
Compile the C program:
gcc XX_AlgorithmName.c -o algorithm
-
Execute the program:
./algorithm
Each implementation includes:
- Proper documentation and comments
- Input/output examples
- Core algorithm implementation
- Supporting utility functions
| Algorithm | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity |
|---|---|---|---|
| Linear Search | O(n) | O(n) | O(1) |
| Binary Search | O(log n) | O(log n) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n²) | O(log n) |
| DFS | O(V + E) | O(V + E) | O(V) |
| BFS | O(V + E) | O(V + E) | O(V) |
| Dijkstra's Algorithm | O(V² + E) | O(V² + E) | O(V + E) |
| N-Queen | O(n!) | O(n!) | O(n) |
| Knapsack (DP) | O(n×W) | O(n×W) | O(n×W) |
| Job Sequencing | O(n²) | O(n²) | O(n) |
| Fractional Knapsack | O(n log n) | O(n log n) | O(1) |
Contributions are welcome! If you'd like to improve implementations or add new algorithms:
- Fork the repository
- Create your feature branch:
git checkout -b feature/new-algorithm - Commit your changes:
git commit -m 'Add new algorithm' - Push to the branch:
git push origin feature/new-algorithm - Submit a pull request
- Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
- The Algorithm Design Manual by Steven S. Skiena
- GeeksforGeeks: https://www.geeksforgeeks.org/
- VisuAlgo: https://visualgo.net/