Algorithms II
The second algorithms course: three further design techniques, the theory of NP-completeness, and the ways to cope with hard problems, taught through the problems of an invented regional courier company: look-alike problems on opposite sides of the efficiency boundary, input size in bits, and decision versus optimization; dynamic programming with memoization and tabulation, correctness by induction, longest common subsequence, edit distance and longest increasing subsequence, the 0/1 knapsack problem and pseudo-polynomial time, weighted interval scheduling, matrix chains and tree DP; Bellman–Ford as dynamic programming with negative-cycle detection, Floyd–Warshall and Johnson reweighting; maximum flow with residual graphs, the max-flow min-cut theorem, integrality and the Edmonds–Karp bound, and flow models for bipartite matching and König's theorem, disjoint paths, supply and demand, project selection and sports elimination; linear programming, the simplex, ellipsoid and interior-point methods, duality, complementary slackness, total unimodularity and integrality gaps; P, NP, co-NP, certificates and polynomial-time reductions, the Cook–Levin theorem through circuits and the Tseitin transformation, and gadget reductions to 3SAT, independent set, vertex cover, set cover, subset sum, knapsack, Hamiltonian cycle and TSP; approximation algorithms for vertex cover, set cover, metric TSP (doubling and Christofides), load balancing and a knapsack FPTAS, with the limits set by the PCP theorem; randomized algorithms including quicksort and quickselect, universal hashing, Freivalds' test, Karger's minimum cut and Miller–Rabin; and a capstone on Held–Karp, meet in the middle, fixed-parameter algorithms and kernels, local search and modern SAT and integer programming solvers. Every lesson has worked examples, practice with solutions and runnable Python checked against brute force.
CMPUT-304 Year 3 3 credits 12 lessons · 6 h 35 min ▶ Video lessons coming soon
Offered by HSM University · Computing Science
What you'll learn
- Distinguish tractable from apparently intractable problems, measure input size in bits, and move between decision, search and optimization versions of a problem.
- Design dynamic programming algorithms by defining subproblems, writing recurrences, choosing an evaluation order and recovering solutions, and prove them correct by induction.
- Apply dynamic programming to sequences, knapsack-type problems, intervals and trees, and explain pseudo-polynomial running times.
- Compute single-source and all-pairs shortest paths with negative weights using Bellman–Ford, Floyd–Warshall and Johnson reweighting, and detect negative cycles.
- Compute maximum flows with augmenting paths, prove the max-flow min-cut theorem and analyze the Edmonds–Karp algorithm.
- Model matching, disjoint paths, supply and demand, project selection and elimination problems as flows or cuts, proving both directions of each reduction.
- Formulate linear programs, write their duals, use weak and strong duality and complementary slackness, and explain LP relaxations and integrality gaps.
- Define P, NP, co-NP and NP-completeness, give certificates and verifiers, and construct polynomial-time reductions in the correct direction.
- Explain the Cook–Levin theorem and prove problems NP-complete with gadget reductions from SAT, 3SAT, independent set, subset sum and Hamiltonian cycle.
- Design and analyze approximation algorithms using lower bounds, greedy choices, LP rounding and scaling, and describe known limits of approximability.
- Design and analyze Las Vegas and Monte Carlo algorithms using indicator variables, universal hashing, amplification and random contraction.
- Choose and justify a response to an NP-hard problem among exact exponential, fixed-parameter, heuristic and solver-based methods, and evaluate solutions against lower bounds.
Course content
12 lessons · 6 h 35 min total · final exam
- 1 Why algorithms II: from efficient algorithms to hard problems 31 min · quiz
- 2 Dynamic programming I: principles, memoization and sequences 35 min · quiz
- 3 Dynamic programming II: knapsack, intervals and trees 31 min · quiz
- 4 Shortest paths revisited: Bellman–Ford, Floyd–Warshall and Johnson 31 min · quiz
- 5 Network flow: Ford–Fulkerson, Edmonds–Karp and max-flow min-cut 33 min · quiz
- 6 Applications of flow: matching, circulations and project selection 37 min · quiz
- 7 Linear programming and duality for algorithm design 32 min · quiz
- 8 P, NP and polynomial-time reductions 30 min · quiz
- 9 NP-completeness: Cook–Levin and classic reductions 34 min · quiz
- 10 Approximation algorithms: greedy, LP rounding and PTAS 34 min · quiz
- 11 Randomized algorithms: Las Vegas, Monte Carlo and hashing 34 min · quiz
- 12 Capstone: coping with hardness — parameterized, exact exponential and heuristic algorithms 33 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
The second algorithms course: three further design techniques, the theory of NP-completeness, and the ways to cope with hard problems, taught through the problems of an invented regional courier company: look-alike problems on opposite sides of the efficiency boundary, input size in bits, and decision versus optimization; dynamic programming with memoization and tabulation, correctness by induction, longest common subsequence, edit distance and longest increasing subsequence, the 0/1 knapsack problem and pseudo-polynomial time, weighted interval scheduling, matrix chains and tree DP; Bellman–Ford as dynamic programming with negative-cycle detection, Floyd–Warshall and Johnson reweighting; maximum flow with residual graphs, the max-flow min-cut theorem, integrality and the Edmonds–Karp bound, and flow models for bipartite matching and König's theorem, disjoint paths, supply and demand, project selection and sports elimination; linear programming, the simplex, ellipsoid and interior-point methods, duality, complementary slackness, total unimodularity and integrality gaps; P, NP, co-NP, certificates and polynomial-time reductions, the Cook–Levin theorem through circuits and the Tseitin transformation, and gadget reductions to 3SAT, independent set, vertex cover, set cover, subset sum, knapsack, Hamiltonian cycle and TSP; approximation algorithms for vertex cover, set cover, metric TSP (doubling and Christofides), load balancing and a knapsack FPTAS, with the limits set by the PCP theorem; randomized algorithms including quicksort and quickselect, universal hashing, Freivalds' test, Karger's minimum cut and Miller–Rabin; and a capstone on Held–Karp, meet in the middle, fixed-parameter algorithms and kernels, local search and modern SAT and integer programming solvers. Every lesson has worked examples, practice with solutions and runnable Python checked against brute force.
Part of the Science stream, typically taken in year 3.