The Lectures · Course II
Data Structures & Algorithms
The course I TA'd for two years at UConn (CSE 2050), retaught here the way I wanted to teach it from the front of the room. Everything is in Python, following the arc of Donald R. Sheehy's A First Course on Data Structures in Python: abstract data types as contracts, implementations written from scratch and tested against the contract, and running-time analysis that starts from actual measurements rather than folklore. Each lecture carries an interactive plate, because the moment a data structure makes sense is the moment you watch it move.
The workbench
Every lecture in this course shares one instrument: a small Python workbench that
runs entirely in your browser (MicroPython compiled to WebAssembly; nothing is
sent anywhere). Edit the code, press Run, and call
visualize(obj) on any list, dictionary, linked structure, or binary
tree to see it drawn. Try it: remove another node, or link a node back to itself
and watch the cycle appear.
remove_first. Python runs locally in your browser.
The arc
-
I.
A mental model for Python published
Names and objects, sequence · selection · iteration, the collections and what they cost to misuse. Chapters 2–3.
Planned plate A names-and-objects tracer: step through short snippets and watch names point at objects; the list-aliasing trap, live.
-
II.
Testing first published
unittest, test-driven development, and testing against the ADT rather than the implementation. Chapters 4 and 7.5.
Planned plate A red–green loop: one subtly buggy Stack, a menu of tests; pick tests to run and watch them corner the bug.
-
III.
How fast is it, really? published
Timing programs, modeling cost, asymptotic analysis, big-O without hand-waving. Chapter 5.
Planned plate A growth-class lineup: real timing data on axes you control (linear or log-log); guess which curve is which before the labels reveal.
-
IV.
Stacks, queues, and the idea of an ADT published
The interface as contract; errors as part of the contract. Chapter 6.
Planned plate An ADT machine: push, pop, enqueue with running cost meters; a list-backed queue racing a deque-backed one until the list goes quadratic.
-
V.
Linked lists and the wrapper pattern published
Singly and doubly linked lists, storing the length, O(1) concatenation. Chapters 7–8.
Planned plate Pointer surgery: relink nodes by hand, splice two doubly linked lists in constant time, break the chain and see what is still reachable.
-
VI.
Recursion and the call stack published
Induction as a programming technique; Fibonacci and Euclid as the two canonical traces. Chapter 9.
Planned plate The call stack, animated: frames push and pop as you step; the recursion tree for fib(n) unfolds beside it.
-
VII.
Dynamic programming published
Greedy, recursive, memoized, tabulated: the same problem four ways. Chapter 10.
Planned plate A memoization heat map: the fib recursion tree with the memo toggled on and off, a node counter watching exponential collapse to linear.
-
VIII.
Binary search and the quadratic sorts published
The ordered list ADT; insertion and selection sort as honest baselines. Chapters 11–12.
Planned plate An invariant watcher: binary search with its loop invariant displayed at every step; try to pick a probe that breaks it.
-
IX.
Divide and conquer: mergesort, quicksort, quickselect published
The recurrences, the merging of iterators, and why randomized pivots are respectable. Chapters 13–14.
Planned plate The sorting races: mergesort against quicksort against insertion sort on inputs you design (sorted, reversed, nearly sorted), with comparison meters; a pivot lottery for quickselect.
-
X.
Hash tables, or: it’s too slow! published
The Mapping ADT, buckets, load factor, rehashing, and factoring out a superclass. Chapter 15.
Planned plate The bucket counter: type keys and watch them hash into buckets; drive the load factor up until rehashing fires, then feed it adversarial keys that all collide.
-
XI.
Trees, BSTs, and balance published
Tree ADTs and traversals, binary search trees, then rotations: weight-balanced, AVL, splay. Chapters 16–18.
Planned plate A rotation playground: build a BST in any insertion order and watch its height; perform rotations by hand, then let AVL do it and compare.
-
XII.
Heaps and priority queues published
The array-as-tree trick, _heapify from scratch, changing priorities, heapsort. Chapter 19.
Planned plate A dual view: heapify stepped through with the same cells highlighted in the array and in the tree at once, so the trick stops being a trick.
-
XIII.
Graphs: search, shortest paths, spanning trees published
Graph ADTs, DFS and BFS, Dijkstra, Prim, and priority-first search as the unifying frame. Chapters 20–21.
Planned plate Search on the map: BFS, DFS, Dijkstra, and Prim run over a real geographic graph, the frontier advancing edge by edge. The atlas plate this course was always going to have.
-
XIV.
Disjoint sets and Kruskal published
Union-find, path compression, merge by height and weight, and a second spanning-tree algorithm to close the loop. Chapter 22.
Planned plate A union-find forest: click to union, toggle path compression and watch the trees flatten; Kruskal builds the same spanning tree Prim did, edge by edge.