Final Review

Quick Reference Tables, Common Mistakes, Last-Minute Tips

Focus on Your Problem Sets!

Your problem sets (ps1-sol.pdf through ps8-sol.pdf) are in the Assignment_answer_sols folder. These are gold!

Rework Problems: Try solving without looking at solutions first
Understand Solutions: Don't just read - understand WHY each step works
Identify Patterns: Notice which techniques apply to which problem types
Tricky Problems: Problems you got wrong initially are likely to appear in similar form

Problem Set Focus Areas

ps1-ps3: Likely focus on graphs, BFS/DFS, topological sort, SCCs
ps3-ps4: Dijkstra's, divide & conquer, recurrence relations
ps4-ps5: Master theorem, greedy algorithms, activity selection
ps5-ps6: MST (Kruskal & Prim), Huffman coding
ps6-ps7: Dynamic programming problems
ps8: Maximum flow, bipartite matching

Common Exam Mistakes to Avoid:

Confusing BFS and DFS applications
Applying Master Theorem when it doesn't apply
Using Dijkstra's with negative weights
Forgetting to check if graph is a DAG for topological sort
Mixing up Kruskal's and Prim's approaches
Not understanding WHEN to use greedy vs DP

▼ 7. Final Morning Review

Last Hour Before Exam:

Review all complexity tables below
Skim through algorithm pseudocode
Quick mental walk-through of each algorithm
Review any problem set problems you struggled with
Stay calm - you've got this!

Master Complexity Reference

Algorithm/Structure	Time Complexity	Space	Notes
BFS	O(V + E)	O(V)	Queue, level-by-level
DFS	O(V + E)	O(V)	Stack/recursion, depth-first
Topological Sort	O(V + E)	O(V)	DFS-based, DAGs only
SCC (Kosaraju)	O(V + E)	O(V)	Two DFS passes
Dijkstra's	O((V+E) log V)	O(V)	Non-negative weights only
Strassen's	O(n^2.81)	O(n²)	7 multiplications
Activity Selection	O(n log n)	O(1)	Sort by finish time
Huffman Coding	O(n log n)	O(n)	Min-heap based
Kruskal's MST	O(E log E)	O(V)	Sort edges, Union-Find
Prim's MST	O((V+E) log V)	O(V)	Grow from vertex, min-heap
Matrix Chain Mult.	O(n³)	O(n²)	DP, optimal parenthesization
LCS	O(mn)	O(mn)	DP, 2D table
Ford-Fulkerson	O(E·\|f*\|)	O(V+E)	Augmenting paths
Edmonds-Karp	O(VE²)	O(V+E)	BFS for paths

Key Theorems & Properties

Master Theorem: T(n) = aT(n/b) + f(n) - compare f(n) with n^(log_b a)
Greedy Choice Property: Optimal solution contains greedy choice
Optimal Substructure: Required for both DP and greedy
Max-Flow Min-Cut: Maximum flow = Minimum cut capacity
MST Properties: V-1 edges, unique if weights distinct, light edge crossing cut is safe
Cut Property: For any cut, minimum weight edge crossing it is in some MST

If You Have Extra Time:

🎥 Abdul Bari's Algorithm Playlist (Full Course Review) 🔗 VisuAlgo - Algorithm Visualizations 🔗 Big-O Cheat Sheet