Good data structures begin with a question: what do we need to do with this information? The right representation makes the operations we need easy, while exposing the costs of the operations we use less often.
This collection develops that idea through sequences, graphs, searching and sorting. It brings together notes and slide decks from Data Structures and Algorithms I, with archived course editions kept alongside the continuing subject material.
A route through the material
Representing sequences. Arrays and linked lists offer different ways to store ordered data. Stacks, queues and deques make the allowed operations explicit.
Representing relationships. Adjacency lists, adjacency matrices and edge lists turn a graph into something an algorithm can work with.
Navigating graphs. Breadth-first and depth-first search provide organizing principles for reachability, shortest paths, connectivity and ordering.
Following every edge. Euler tours connect a structural condition on a graph with an algorithm for constructing a walk.
Searching and organizing. Sorting, heaps and search trees trade representation choices against the costs of insertion, deletion and lookup.
Accounting for efficiency. Asymptotic analysis lets us compare these choices beyond the size of a single example.
Stable matching and card tricks appear throughout the archived material as concrete settings in which to make and test these choices.
Using this collection
Start with the slide library, or browse a dated course edition. The subject collection can grow independently of the courses in which a particular version was used.
The archived introductory course is aimed at first- and second-year undergraduates. Familiarity with a programming language is useful; the archived laboratory work used C.
Reading
Open Data Structures, Pat Morin.
Algorithms, Jeff Erickson.
The January–April 2023 course page records the original topic list, prerequisites and reading references.