Algorithms
Undergraduate · CS / Programming
Syllabus focus
Topics typically covered
Standard syllabus
Design paradigms
- Divide and conquer: mergesort, quicksort, master theorem (intro)
- Greedy algorithms: activity selection, Huffman coding (intro)
- Dynamic programming: knapsack, LCS, matrix chain (intro)
- Graph representations and traversal (BFS, DFS)
- Topological sort and strongly connected components (intro)
Classic problems
- Shortest paths: Dijkstra and Bellman–Ford (intro)
- Minimum spanning trees: Kruskal and Prim
- Network flow overview (Ford–Fulkerson at survey level)
- Backtracking: N-queens, subset sum
- NP-completeness: reductions and classic problems (intro)
Theoretical / proof-based
Proofs and complexity
- Correctness proofs for iterative and recursive algorithms
- Loop invariants and termination arguments
- Reductions and NP-completeness proofs (intro)
- Amortized analysis: aggregate and potential methods (intro)
- Randomized algorithms: expected runtime (intro)
Advanced graph and optimization
- Matching and bipartite graphs (intro)
- Approximation algorithms and ratio proofs (intro)
- Linear programming formulation of combinatorial problems (intro)
- Parametric search and binary search on answer (intro)
- Problem-solving strategies for proof-based exams
Notes
Typically follows data structures and discrete math. Proof-heavy sections mirror theory-oriented algorithms courses.