Data Structures
Description
Fast and efficient data structures power a wide range of software systems. B-trees keep gigantic databases fast, count-min sketches let us find popular search terms in real-time, and suffix trees are a workhorse in computational biology. Learn the tools and techniques behind the design, analysis, implementation, and theory of data structures, and see some truly beautiful approaches to solving problems efficiently.
Prerequisites
This class is intended as a second course in data structures. CS166 builds on the coding techniques from CS107, the algorithmic and mathematical techniques from CS161, the treatment of random variables from CS109, and the mathematical proofwriting from CS103. Students interested in learning fundamental data structures like stacks, queues, linked lists, and hash tables should instead consider CS106B.
Topics include
- Data structure isometries
- Amortized analysis
- Suffix trees and arrays
- Count-min sketches
- Fibonacci and binomial heaps
- Splay trees