| Topic | Details | Resources |
|---|---|---|
| Complexity basics | comparison of different complexity classes | |
| Proof techniques | substitution, induction, recursion tree method | |
| Recursion | recurrence relations | |
| Master method | Usage and proof of master method | Master Method Proof, Practice Problems |
| Divide and Conquer Technique | Quicksort, Mergesort, Heapsort | |
| Analysis of Sorting techniques | Time and Space for Quicksort, Mergesort, heapsort | |
| BFS and DFS | BFS and DFS tree, Cycle finding, Analysis of both algorithms | |
| Minimum Spanning Tree | Prim's and Kruskal's and Analysis of both algorithms | |
| Shortest paths in graph | Floyed Warshall, Dijkstra, Bellman Ford | |
| Dynamic Programming 1 | Concepts - overlapping subproblems and optimal substructure properties | |
| Dynamic Programming 2 | 0-1 Knapsack, Matrix Chain Multiplication | |
| Greedy | Fractional Knapsack, Job sequencing problem with deadlines | |
| Divide and Conquer | Matrix Multiplication (Basic and Strassen's) | |
| Notion of NP Completeness | classes of problems, decision problems and optimization problems, | reference |
| NP Completeness - reductions | SUBSET SUM, CLIQUE, VERTEX COVER, HAM-CYCLE, 0-1 KNAPSACK, TSP | SAT, 3-CNF-SAT |
| Backtracking | Subset sum, N-queen, Graph coloring | |
| Branch and Bound | 0-1 Knapsack, 15-puzzle, TSP | |
| Network Flow | Flow Basics, Max flow properties, Max-flow Min-cut Theorem, Bipartite matching | |
| Approximation Algorithms | Notions of approximation, Min-Vertex-Cover | reference |
| Pattern Matching | Basics, Rabin-Karp, Knuth-Morris-Pratt | |
| Concepts of Amortization Algorithms | Examples, methods for Amortization | reference |