(Formerly CS157)

Design and Analysis of Algorithms

Course Home Page:
Location:85 Waterman room 130 (Remote asynch possible via section 2)
Meeting Time:K hr: T, Th 2:30-3:50
Exam Group:12: 20-DEC-2021 Exam Time: 02:00:00 PM
Offered this year?Yes
When Offered?Every year


A single algorithmic improvement can have a greater impact on our ability to solve a problem than ten years of incremental improvements in CPU speed. We study techniques for designing and analyzing algorithms. Typical problem areas addressed include hashing, searching, dynamic programming, graph algorithms, network flow, optimization algorithms including linear programming. Topics include: Dynamic programming: strategies and formal analysis, Divide and conquer: median finding, Strassen, FFT and applications of FFT, Systems-aware algorithm design: memory hierarchy, and competitive analysis, Hashing and data structures: analysis tools and applications, augmenting search trees, Data compression: entropy, Huffman coding, practical examples, NP hardness, Optimization and linear programming: local search, ellipsoid algorithm, Graph algorithms: union-find, spectral methods. Advanced topics: parallel and randomized algorithms. Prerequisite: CSCI0160 or CSCI0180 or CSCI0190, and one of CSCI0220 or CSCI1450.

CRN: 16064