This course is a deep dive into the design, analysis, implementation, and theory of data structures. Over the course of the quarter, we'll explore fundamental techniques in data structure design (isometries, amortization, randomization, etc.), as well as perspectives and intuitions useful for developing new data structures. By the time we've finished, we'll have seen some truly beautiful strategies for solving problems efficiently. Possible topics include Fibonacci heaps, fusion trees, succinct rank and select, B-trees, range minimum queries, suffix trees, dynamic connectivity, cuckoo hashing, and planar point location. Prerequisites: CS 107 and CS 161.
3-4 units · Letter or Credit/No Credit
This course is a deep dive into the design, analysis, implementation, and theory of data structures. Over the course of the quarter, we'll explore fundamental techniques in data structure design (isometries, amortization, randomization, etc.), as well as perspectives and intuitions useful for developing new data structures. By the time we've finished, we'll have seen some truly beautiful strategies for solving problems efficiently. Possible topics include Fibonacci heaps, fusion trees, succinct rank and select, B-trees, range minimum queries, suffix trees, dynamic connectivity, cuckoo hashing, and planar point location. Prerequisites: CS107 and CS161.