Gregory Friedman The Greg Wide Web on the name →

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.

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.

python runs in your browser · first run downloads ~240 kb
Plate I The workbench. A linked list built by hand, visualized before and after remove_first. Python runs locally in your browser.
  • 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.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.