Algorithm Design
Designing and proving algorithms beyond the first course: formulating problems precisely, loop invariants and exchange arguments, greedy scheduling and Huffman codes, divide and conquer with inversion counting, closest pair, Karatsuba multiplication and the master theorem, dynamic programming for weighted scheduling, knapsack, subsequences, edit distance, linear-space alignment, DAGs and trees, maximum flow, minimum cuts and bipartite matching, Bellman-Ford, difference constraints, Floyd-Warshall and Johnson, randomized quickselect, universal hashing and Bloom filters, amortized analysis with potential functions and union-find, P, NP and reductions, NP-completeness from Cook-Levin to vertex cover, Hamiltonian cycles, the TSP and knapsack, and coping with hardness through special structure, exact and fixed-parameter solvers, approximation and local search, ending in a capstone that schedules sensor uploads as a minimum-cost flow.
CMP-301 Year 3 3 credits 12 lessons · 4 h 3 min ▶ Video lessons coming soon
Offered by HSM University · Computer Engineering
This is the American version of this course. See the Canadian version.
What you'll learn
- Formulate engineering requests as precise computational problems, prove algorithms correct with loop invariants, induction and exchange arguments, and analyze their worst-case cost.
- Design greedy algorithms for scheduling and coding problems, prove them optimal with stays-ahead and exchange arguments, and construct counterexamples when greedy fails.
- Design divide-and-conquer algorithms, including inversion counting, closest pair and Karatsuba multiplication, and solve their recurrences with recursion trees and the master theorem.
- Design dynamic programs by defining subproblems, writing recurrences, choosing evaluation orders and tracing back solutions, for weighted scheduling, knapsack and longest common subsequence.
- Apply dynamic programming to edit distance and sequence alignment in linear space, to longest paths in DAGs, and to optimization problems on trees.
- Model problems as maximum flows, compute them with Ford-Fulkerson and Edmonds-Karp, use the max-flow min-cut theorem to find bottlenecks, and solve bipartite matching by reduction.
- Compute shortest paths with negative edge weights using Bellman-Ford, detect negative cycles, solve difference constraints, and compute all-pairs distances with Floyd-Warshall and Johnson.
- Analyze randomized algorithms by expected running time, and apply quickselect, universal hashing, Bloom filters and reservoir sampling with quantified error rates.
- Prove amortized bounds with aggregate, accounting and potential methods for dynamic arrays, counters, two-stack queues and union-find.
- Define P, NP, NP-hard and NP-complete, verify membership in NP with certificates, and construct polynomial-time reductions in the correct direction.
- Explain the Cook-Levin theorem and prove NP-completeness of 3-SAT, independent set, vertex cover, Hamiltonian cycle, TSP and knapsack through chains of reductions.
- Respond to NP-hard problems with special structure, fixed-parameter and exact solvers, approximation algorithms with guarantees and local search, and formulate scheduling problems as minimum-cost flow.
Course content
12 lessons · 4 h 3 min total · final exam
- 1 Algorithm design: paradigms, correctness and cost 22 min · quiz
- 2 Greedy algorithms and exchange arguments 20 min · quiz
- 3 Divide and conquer and the master theorem 19 min · quiz
- 4 Dynamic programming I: memoization, knapsack and subsequences 21 min · quiz
- 5 Dynamic programming II: edit distance, alignment, trees and DAGs 20 min · quiz
- 6 Network flow and bipartite matching 21 min · quiz
- 7 Shortest paths with negative edges and between all pairs 19 min · quiz
- 8 Randomized algorithms and hashing 20 min · quiz
- 9 Amortized analysis 20 min · quiz
- 10 P, NP and polynomial-time reductions 21 min · quiz
- 11 NP-completeness: SAT, vertex cover, Hamiltonian cycles and the TSP 19 min · quiz
- 12 Coping with hardness and capstone: scheduling sensor uploads 21 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
Designing and proving algorithms beyond the first course: formulating problems precisely, loop invariants and exchange arguments, greedy scheduling and Huffman codes, divide and conquer with inversion counting, closest pair, Karatsuba multiplication and the master theorem, dynamic programming for weighted scheduling, knapsack, subsequences, edit distance, linear-space alignment, DAGs and trees, maximum flow, minimum cuts and bipartite matching, Bellman-Ford, difference constraints, Floyd-Warshall and Johnson, randomized quickselect, universal hashing and Bloom filters, amortized analysis with potential functions and union-find, P, NP and reductions, NP-completeness from Cook-Levin to vertex cover, Hamiltonian cycles, the TSP and knapsack, and coping with hardness through special structure, exact and fixed-parameter solvers, approximation and local search, ending in a capstone that schedules sensor uploads as a minimum-cost flow.
Part of the Engineering stream, typically taken in year 3.