Algorithms II

CS 474 is the proof-heavy second half of the algorithms sequence, where the focus shifts from "can you sort and search" to designing and rigorously justifying algorithms on graphs and amortized data structures. You'll spend the term writing correctness proofs, doing amortized analyses (potential method on Fibonacci heaps, union-by-rank with path compression), and working through three projects plus two midterms that lean on Cormen-style reasoning rather than coding tricks. It builds directly on CS 473 and is the backbone for almost everything theoretical that follows — network flows, advanced graph theory, optimization, and any grad course that assumes you can read and produce an algorithmic proof.