Practice Problems
CS F364 — Design & Analysis of Algorithms | Summer 2026
This collection of practice problems covers all major topics from tutorials and exams. Each problem includes a detailed solution — click to expand.
4 problems — Big-Oh, Big-Theta, Big-Omega, comparing growth rates.
5 problems — Substitution method, Master theorem, two-variable recurrences.
7 problems — Merge sort variants, missing integer, MST, convex polygon, matrix search.
5 problems — Interval scheduling, interval stabbing, cookie assignment, knapsack.
3 problems — String interleaving, petrol pump stops, subset sum.
Post-Midsem Topics
4 problems — Independence axioms, matroid properties, greedy on weighted matroids.
6 problems — Aggregate/potential/accounting methods, binary counter, dynamic table variants.
5 problems — Ford-Fulkerson, max-flow min-cut, edge-disjoint paths, project selection, flow properties.
3 problems — Las Vegas vs Monte Carlo, dot-product lemma, Freivalds.
5 problems — P vs NP, 3-SAT to CLIQUE, Vertex Cover, Independent Set reductions.
3 problems — LP/IP formulation, LP relaxation, Vertex Cover rounding, integrality gap.