General Info

Visit Canvas for the Zoom lecture link.

Announcements

Welcome to CS166!
March 30, 2021

Welcome to CS166, a course in the design, analysis, and implementation of data structures. We've got an exciting quarter ahead of us - the data structures we'll investigate are some of the most beautiful constructs I've ever come across - and I hope you're able to join us.

CS166 has two prerequisites - CS107 and CS161. From CS107, we'll assume that you're comfortable working from the command-line; designing, testing, and debugging nontrivial programs; manipulating pointers and arrays; using bitwise operators; and reasoning about the memory hierarchy. From CS161, we'll assume you're comfortable designing and analyzing nontrivial algorithms; using O, o, Θ, Ω, and ω notation; solving recurrences; working through standard graph and sequence algorithms; and structuring proofs of correctness.

We'll update this site with more information as we get closer to the start of the quarter. In the meantime, feel free to email me at htiek@cs.stanford.edu if you have any questions about the class!

 

Schedule and Readings

This syllabus is still under construction and is subject to change as we fine-tune the course. Stay tuned for more information and updates!

Tuesday Thursday
Orthogonal Range Searching
May 4

Imagine you've got a huge collection of points stored in 2D space. Maybe they're points on a map, or maybe they're points in an abstract feature space. You want to find all points in an axis-aligned rectangle, such as the viewport on a map window. How quickly can you do so? By using some clever techniques, we can make this type of search just as fast as in the 1D case.

Slides:

Handouts:

Planar Point Location
May 6

The planar point location problem is the following: given a collection of borders on a map and a point p, which region of the map is p contained in? This question can be answered quickly and efficiently using persistent data structures, a family of data structures where each operation keeps the old version around while producing a new version.

Slides:

Readings:

Hashing and Sketching, Part I
April 27

How can Google keep track of frequent search queries without storing all the queries it gets in memory? How can you estimate frequently- occurring tweets without storing every tweet in RAM? As long as you're willing to trade off accuracy for space, you get get excellent approximations.

Slides:

Readings:

Hashing and Sketching, Part II
April 29

We've now seen how to build an estimator: make a simple data structure that gives a good chance of success, then run it in parallel. This idea can be extended to build frequency estimators with other properties, as well as to build estimators for how many distinct items we've seen.

Slides:

Readings:

Fibonacci Heaps
April 20

Fibonacci heaps are a type of priority queue that efficiently supports decrease-key, an operation used as a subroutine in many graph algorithms (Dijkstra's algorithm, Prim's algorithm, the Stoer-Wagner min cut algorithm, etc.) They're formed by a clever transformation on a lazy binomial heap. Although Fibonacci heaps have a reputation for being ferociously complicated, they're a lot less scary than they might seem!

Slides:

Readings:

Cuckoo Hashing
April 22

Most hash tables give expected O(1) lookups. Can we make hash tables with no collisions at all, and if so, can we do it efficiently? Amazingly, the answer is yes. There are many schemes for achieving this, one of which, cuckoo hashing, is surprisingly simple to implement. The analysis, on the other hand, goes deep into properties of random graph theory.

Slides:

Readings:

Handouts:

Amortized Analysis
April 13

In many cases we only care about the total time required to process a set of data. In those cases, we can design data structures that make some operations more expensive in order to lower the total cost of all aggregate operations. How do you analyze these structures?

Slides:

Readings:

  • CLRS: Chapter 17

Handouts:

Binomial Heaps
April 15

Binomial heaps are a simple and flexible priority queue structure that supports efficient melding of priority queues. The intuition behind binomial heaps is particularly elegant, and they'll serve as a building block toward the more complex Fibonacci heap data structure that we'll talk about on Thursday.

Slides:

Readings:

Balanced Trees, Part I
April 6

Balanced search trees are among the most versatile and flexible data structures. They're used extensively in theory and in practice. What sorts of balanced trees exist? How would you design them? And what can you do with them?

Slides:

Handouts:

Readings:

Balanced Trees, Part II
April 8

Our last lecture concluded with a view of red/black trees as isometries of 2-3-4 trees. How far does this connection go? How can we use it to derive the rules for red/black trees? And now that we've got red/black trees, what else can we do with them?

Slides:

Readings:

  • CLRS, Chapter 14.
Range Minimum Queries, Part One
March 30

The range minimum query problem is the following: given an array, preprocess it so that you can efficiently determine the smallest value in a variety of subranges. RMQ has tons of applications throughout computer science and is an excellent proving ground for a number of advanced algorithmic techniques.

Slides:

Readings:

Range Minimum Queries, Part Two
April 1

Our last lecture took us very, very close to a ⟨O(n), O(1)⟩-time solution to RMQ. Using a new data structure called a Cartesian tree in conjunction with a technique called the Method of Four Russians, we can adapt our approach to end up with a linear-preprocessing-time, constant-query-time solution to RMQ. In doing so, we'll see a number of clever techniques that will appear time and time again in data structure design.

Slides:

Readings: