A single algorithmic improvement can have a greater impact on our ability to solve a problem than ten years of incremental hardware improvements. We study techniques for designing and analyzing algorithms. Topics include: dynamic programming, divide and conquer algorithm design, Fourier transforms, competitive analysis and online algorithms, data structures including techniques for hashing and self-balancing binary search trees, information compression, greedy algorithms, NP hardness, optimization techniques including convex optimization and local search, linear programming and duality, maximum matching and max-flow and related graph algorithms, and a focus on algorithms in the context of real systems including massively parallel GPU computing.
Classes will be held every Monday, Wednesday, and Friday from 2 to 2:50 PM in Barus & Holley 166.
CS16, CS18, or CS19, and one of CS22, CS145 or APMA1650.
Lecture videos can be found on Canvas here.