Course Roadmap
Full Design and Analysis of Algorithms syllabus arranged in course order from easy to hard. Algorithmic topics, theory concepts, and data-structure operation complexities are separated for clarity.
1. Basic Algorithms (Easy -> Moderate)
Core introductory algorithms and number-theory fundamentals.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Euclid Algorithm (GCD) | O(log n) | O(log n) | O(log n) | O(1) | Existing |
| Linear Search | O(1) | O(n) | O(n) | O(1) | Existing |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | Existing |
| Chinese Remainder Theorem | O(k log M) | O(k log M) | O(k log M) | O(1) | Existing |
2. Sorting Algorithms (Easy -> Hard)
Comparison and non-comparison sorting techniques.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | Existing |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Existing |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | Existing |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Existing |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Existing |
| Bucket Sort | O(n + k) | O(n + k) | O(n^2) | O(n) | Existing |
3. String Matching Algorithms
Pattern matching on text with hashing and prefix-suffix techniques.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Rabin-Karp | O(n + m) | O(n + m) | O(nm) | O(1) | Existing |
| KMP (Knuth-Morris-Pratt) | O(n + m) | O(n + m) | O(n + m) | O(m) | Existing |
| Boyer-Moore | O(n/m) | O(n) | O(nm) | O(sigma) | Existing |
4. Graph Algorithms
Traversal and ordering fundamentals on graph structures.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Breadth First Search (BFS) | O(V + E) | O(V + E) | O(V + E) | O(V) | Existing |
| Depth First Search (DFS) | O(V + E) | O(V + E) | O(V + E) | O(V) | Existing |
| Topological Sort | O(V + E) | O(V + E) | O(V + E) | O(V) | Existing |
5. Shortest Path Algorithms
Single-source and all-pairs shortest path methods.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Dijkstra (heap) | O(E log V) | O(E log V) | O(E log V) | O(V) | Existing |
| Bellman-Ford | O(VE) | O(VE) | O(VE) | O(V) | Existing |
| Floyd-Warshall | O(V^3) | O(V^3) | O(V^3) | O(V^2) | Existing |
6. Minimum Spanning Tree
Greedy edge-selection strategies for spanning trees.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Prim's MST | O(E log V) | O(E log V) | O(E log V) | O(V) | Existing |
| Kruskal's MST | O(E log E) | O(E log E) | O(E log E) | O(V) | Existing |
| Sollin/Boruvka's MST | O(E log V) | O(E log V) | O(E log V) | O(V) | Existing |
7. Divide and Conquer
Recursive decomposition into independent subproblems.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Binary Search (D&C view) | O(1) | O(log n) | O(log n) | O(1) | Existing |
| Max and Min of Sequence | O(n) | O(n) | O(n) | O(1) | Existing |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Existing |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | Existing |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | Existing |
| Strassen's Matrix Multiplication | O(n^2.81) | O(n^2.81) | O(n^2.81) | O(n^2) | Existing |
8. Greedy Algorithms
Locally optimal choices leading to globally optimal outcomes.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Fractional Knapsack | O(n log n) | O(n log n) | O(n log n) | O(1) | Existing |
| Prim's MST | O(E log V) | O(E log V) | O(E log V) | O(V) | Existing |
| Kruskal's MST | O(E log E) | O(E log E) | O(E log E) | O(V) | Existing |
| Huffman Coding | O(n log n) | O(n log n) | O(n log n) | O(n) | Existing |
| Optimal Merge Patterns | O(n log n) | O(n log n) | O(n log n) | O(n) | Existing |
9. Dynamic Programming
Tabulation and memoization for overlapping subproblems.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| 0/1 Knapsack | O(nW) | O(nW) | O(nW) | O(nW) | Existing |
| Subset Sum (DP) | O(nW) | O(nW) | O(nW) | O(nW) | Existing |
| Change Making (Coin Change) | O(amount * coins) | O(amount * coins) | O(amount * coins) | O(amount) | Existing |
| Optimal Binary Search Tree | O(n^3) | O(n^3) | O(n^3) | O(n^2) | Existing |
| Matrix Chain Multiplication | O(n^3) | O(n^3) | O(n^3) | O(n^2) | Existing |
| Longest Common Subsequence | O(mn) | O(mn) | O(mn) | O(mn) | Existing |
| Travelling Salesperson (DP / Held-Karp) | O(n^2 * 2^n) | O(n^2 * 2^n) | O(n^2 * 2^n) | O(n * 2^n) | Existing |
10. Backtracking
Systematic search with pruning on decision trees.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| N-Queens | N/A | N/A | O(n!) | O(n) | Existing |
| Sum of Subsets | N/A | N/A | O(2^n) | O(n) | Existing |
| Hamiltonian Cycle | N/A | N/A | O(n!) | O(n) | Existing |
11. Branch and Bound
Bounding plus search to reduce combinatorial explosion.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| 0/1 Knapsack (Branch and Bound) | N/A | N/A | O(2^n) | O(n) | Existing |
| Travelling Salesperson (Branch and Bound) | N/A | N/A | O(n!) | O(n) | Existing |
12. Geometry
Computational geometry core algorithm.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Convex Hull (Graham Scan) | O(n log n) | O(n log n) | O(n log n) | O(n) | Existing |
13. Sorting in Linear Time
Non-comparison sorting methods for constrained domains.
| Topic | Best | Average | Worst | Space | Coverage |
|---|---|---|---|---|---|
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Existing |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Existing |
| Bucket Sort | O(n + k) | O(n + k) | O(n^2) | O(n) | Existing |
Theory Topics (Separate)
Conceptual topics are listed independently; standard best/average/worst complexity does not apply.
| Topic | Best | Average | Worst | Space | Notes |
|---|---|---|---|---|---|
| Modulo Arithmetic Basics | N/A | N/A | N/A | N/A | Covers congruence rules, modular inverse, and arithmetic properties used in hashing and number theory. |
| Complexity Class P | N/A | N/A | N/A | N/A | Decision problems solvable in polynomial time by deterministic algorithms. |
| Complexity Class NP | N/A | N/A | N/A | N/A | Decision problems whose proposed solutions can be verified in polynomial time. |
| NP-hard Basics and Proof Pattern | N/A | N/A | N/A | N/A | Reduction-based hardness arguments from known NP-hard problems. |
| NP-complete Basics and Proof Pattern | N/A | N/A | N/A | N/A | Show membership in NP and NP-hardness via polynomial-time reductions. |
| Graph Representation Models | N/A | N/A | N/A | N/A | Adjacency matrix, adjacency list, and edge list trade-offs. |
| Backtracking: General Method | N/A | N/A | N/A | N/A | State-space tree, feasibility checks, pruning strategy, and recursion template. |
| Branch and Bound: General Method | N/A | N/A | N/A | N/A | Search with upper/lower bounds and node-selection strategy. |
| Divide and Conquer: General Method | N/A | N/A | N/A | N/A | Divide, conquer, combine recurrence design and master-theorem reasoning. |
| Greedy: General Method | N/A | N/A | N/A | N/A | Greedy-choice property and optimal substructure proof approach. |
| Dynamic Programming: General Method | N/A | N/A | N/A | N/A | State definition, transition, base cases, and tabulation order. |
| Divide and Conquer vs Dynamic Programming | N/A | N/A | N/A | N/A | Independent subproblems vs overlapping subproblems and memoization reuse. |
Data Structures Operations (Separate)
Operation-wise complexity reference for core data structures from your course syllabus.
| Data Structure | Operation | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Array | Access by index | O(1) | O(1) | O(1) | O(n) |
| Array | Search (unsorted) | O(1) | O(n) | O(n) | O(n) |
| Array | Insert at end (dynamic array) | O(1) | O(1) | O(n) | O(n) |
| Stack | Push / Pop | O(1) | O(1) | O(1) | O(n) |
| Queue | Enqueue / Dequeue | O(1) | O(1) | O(1) | O(n) |
| Pointers | Dereference / update | O(1) | O(1) | O(1) | O(1) |
| Singly Linked List | Insert at head | O(1) | O(1) | O(1) | O(n) |
| Singly Linked List | Search | O(1) | O(n) | O(n) | O(n) |
| Doubly Linked List | Insert/Delete with node pointer | O(1) | O(1) | O(1) | O(n) |
| Circular Doubly Linked List | Rotate by one step | O(1) | O(1) | O(1) | O(n) |
| Hash Table | Lookup | O(1) | O(1) | O(n) | O(n) |
| Hash Table | Insert / Delete | O(1) | O(1) | O(n) | O(n) |
| BST | Search | O(log n) | O(log n) | O(n) | O(n) |
| BST | Insert / Delete | O(log n) | O(log n) | O(n) | O(n) |
| B-Tree | Search | O(log n) | O(log n) | O(log n) | O(n) |
| B-Tree | Insert / Delete | O(log n) | O(log n) | O(log n) | O(n) |
| AVL Tree | Search / Insert / Delete | O(log n) | O(log n) | O(log n) | O(n) |
| Red-Black Tree | Search / Insert / Delete | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | Insert / Delete | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | Peek top element | O(1) | O(1) | O(1) | O(n) |
| Graph (Adjacency List) | Edge existence check (u, v) | O(1) | O(deg(u)) | O(V) | O(V + E) |
| Graph (Adjacency Matrix) | Edge existence check (u, v) | O(1) | O(1) | O(1) | O(V^2) |
| Graph (Edge List) | Edge existence check (u, v) | O(1) | O(E) | O(E) | O(E) |