Free to read · Three levels
Data Structures and Algorithms: contracts, proofs, and tested implementations
A complete course in invariants, complexity, sequences, search, trees, heaps, graphs, dynamic programming, greedy proofs, dynamic ranges, string matching, and amortized analysis.
Start learningIn this course
Learn to specify an algorithm’s result, prove its maintained invariants, and choose a representation whose complete operation contract fits the task. Three levels contain six developed lessons each, with two explained standalone Python examples, diagnostic mistakes, worked exercises, and primary references.
Examples use synthetic in-memory values, graphs, intervals, and strings. The course separates asymptotic models, exact correctness outputs, finite differential evidence, and real implementation measurements. It does not operate services, databases, devices, cloud systems, or production workloads.
What you will learn
- Specify invariants, duplicate policy, ownership, and cost models before selecting an algorithm.
- Implement and validate sequence, hashing, search, sorting, tree, heap, and traversal contracts.
- Choose shortest-path methods from their weight and reachability assumptions.
- Derive dynamic-programming dependencies, greedy exchanges, and spanning-forest decisions.
- Maintain dynamic range aggregates and overlapping string matches with explicit index semantics.
- Distinguish amortized, expected, worst-case, output-sensitive, and measured performance claims.
Your learning path
Three levels
Contracts, sequences, and search
Invariants, cost models, prefix sums, linked nodes, stacks, queues, hashing, and binary boundaries.
- Contracts, invariants, and cost models
- Arrays, prefix sums, and range contracts
- Linked nodes, ownership, and traversal
- Stacks, queues, and ordering policies
- Hash maps, membership, and duplicates
- Binary search and boundary invariants
Ordered structures and graph reasoning
Stable sorting, search trees, heaps, traversal, weighted paths, recursion, and selection.
- Sorting, stability, and merge invariants
- Binary search trees and traversals
- Heaps, priorities, and streaming top-k
- Graph representation, BFS, and DFS
- Weighted shortest paths and relaxation
- Recursion, divide and conquer, and selection
Optimization proofs and maintained aggregates
Dynamic programming, greedy exchanges, disjoint sets, spanning forests, range structures, string matching, and amortization.
- Dynamic programming: state, order, and reconstruction
- Greedy exchange arguments and counterexamples
- Disjoint sets and minimum spanning forests
- Fenwick and segment range structures
- Prefix functions and overlapping string matches
- Amortized costs and algorithm selection
Who this is for
- Programmers who know basic Python and want to reason about data structures and algorithms beyond memorized patterns.
- Developers preparing to review correctness, resource bounds, and representation choices with concrete evidence.
Before you start
- Functions, loops, lists, dictionaries, classes, and basic integer arithmetic in Python.
- Comfort with simple inequalities, induction-style reasoning, and explicit input/output contracts. Examples require only a compatible Python3 interpreter and standard library.