Discrete Math Review
- Proof by induction
- Proof by contradiction
- Proof by contraposition
- Direct proofs
Introduction to Algorithms
- Basic notions: algorithms, problems, instances
- Correctness of algorithms
- Computational models:
- RAM model
- Running time & input size
- Big-O notation
Algorithm Design: Divide & Conquer
- Divide, conquer, combine
- Examples: Merge sort, Maximum subarray, Matrix multiplication, Strassen’s algorithm
- Analysis of divide & conquer:
- Recurrences & running time
- Methods: substitution, recursion tree, master theorem
- Quicksort analysis (probability review, expected value, indicator RVs)
Lower Bounds for Sorting
Decision tree model for comparison-based sorting.
Sorting Without Comparison
- Counting sort
- Radix sort
- Bucket sort
Dynamic Programming
- Fibonacci (recursive, bottom-up, top-down)
- Rod cutting
- Matrix chain multiplication
- Longest common subsequence
- Optimal BST
- General DP elements
Greedy Algorithms
- Coin changing
- Activity selection
- Job scheduling
- Greedy properties
- Greedy vs DP
- 0-1 Knapsack
Graph Algorithms
- Graph representations
- BFS & DFS (with applications: SCC, topological sort)
- Minimum spanning trees:
- Generic MST
- Kruskal’s algorithm
- Prim’s algorithm
- Shortest paths:
- Single-source
- All-pairs
- Maximum flow