| Complexity basics | comparison of different complexity classes |
| Proof techniques | substitution, induction, recursion tree method |
| Recursion | recurrence relations |
| Divide and Conquer Technique | Quicksort, Mergesort, Heapsort |
| Master method | proof of master method |
| Merge sort analysis | Time and Space |
| Quick sort analysis | specific-split case, average case and worst cases |
| Linear time sorting methods | counting sort (also see. radix sort) |
| Analysis of DFS and BFS | advantages and disadvantages of both techniques |
| BFS tree | also see DFS tree |
| Cycle finding using BFS | also try using DFS |
| Water Jug Problem | Solve using graph and BFS/DFS |
| Job sequencing problem with deadlines | brute force, Greedy |
| Shortest path in graph | Floyed warshall, Dijkstra |
| Dynamic Programming | Concepts - overlapping subproblems and optimal substructure properties |
| 0-1 Knapsack | Dynamic Programming |
| Fractional Knapsack | Greedy |
| Matrix Multiplication (Basic and Strassen's) | Divide and Conquer |
| Matrix Chain Multiplication | Dynamic Programming |
| NP Completeness | classes of problems, decision problems and optimization problems, reference |
| NP Completeness - reductions | SAT, 3-CNF-SAT, SUBSET SUM, CLIQUE, VERTEX COVER, HAM-CYCLE, 0-1 KNAPSACK, TSP |
| Backtracking | Subset sum, N-queen, Graph coloring, Maze Problem |
| Branch and Bound | 0-1 Knapsack, 15-puzzle |
| Network Flow | Flow Basics, Max flow properties, Max-flow Min-cut Theorem, Bipartite matching |
| Approximation Algorithms | Notions of approximation, Min-Vertex-Cover, Graph-coloring/Wigderson's Approximation, Euclidean-TSP |
| Pattern Matching | Basics, Rabin-Karp, Knuth-Morris-Pratt |