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 Tuesday and Thursday from 2:30 to 3:50 PM in Barus & Holley 168.
CS16, CS18, or CS19, and one of CS22 or CS45.