1.
Algorithm Foundations
• Las Vegas vs Monte Carlo algorithms
- Las Vegas: always correct, runtime varies.
- Monte Carlo: fixed runtime, correctness probabilistic.
• Complexity classes
- Big-O, Big-Theta, Big-Omega fundamentals
- Master theorem basics
2. Sorting Algorithms
• Comparison-based sorting overview
- Lower bound: Ω(n log n) comparisons
- Heapsort, mergesort principles
• Counting Sort
- Runtime O(n + k)
- Works when range of keys is small
• Radix Sort
- LSD/MSD ordering
- Requires stable intermediate sorting
3. Selection & Linear-Time Techniques
• Median-of-medians
- Deterministic O(n) selection
• Quickselect
- Expected linear time
4. Hashing & Universal Hash Families
• Independent uniform hashing assumption
• Chaining vs Open addressing
• Universal hash functions: h(x)=(ax+b mod p) mod n
• Collision probability = 1/n
5. Graph Representations
• Adjacency list vs adjacency matrix
• Directed vs undirected graphs
• When to use each representation
- Sparse graphs → adjacency list
- Dense graphs → adjacency matrix
6. Depth-First Search (DFS)
• DFS traversal order
• Recursion tree
• Edge classification:
- Tree edges
- Back edges (cycle indicator)
- Forward edges
- Cross edges
7. Breadth-First Search (BFS)
• Layered exploration
• Shortest paths in unweighted graphs
8. Shortest Path Algorithms
• Dijkstra’s Algorithm
- Requires nonnegative weights
- Priority queue operations
- dist[] and predecessor[] tables
• Bellman-Ford
- Handles negative weights
- Detects negative cycles
9. Minimum Spanning Trees (MST)
• Kruskal's Algorithm
- Sort edges → Union-Find
- Builds forest → merges components
• Prim's Algorithm
- PQ-based greedy approach
10. Dynamic Programming
• DP table construction
• Common patterns
- LCS
- Knapsack (0/1 and unbounded)
- Seam carving
- All-pairs shortest paths (Floyd–Warshall)
• Polynomial vs pseudopolynomial