About this site

Click an LLP algorithm and watch its forbidden / advance loop run on a concrete instance.

This is the companion site for the textbook A Systematic Approach to Algorithms. The site is intentionally minimal — its purpose is to let readers run the lattice-linear predicate (LLP) algorithms developed in the book. Each demo starts from an initial vector, identifies a forbidden index, advances it according to the algorithm's rule, and continues until no forbidden index remains. Use the Step button to follow the algorithm one advance at a time, or Run all to fast-forward to the fixed point.

New to LLP? Read What are LLP Algorithms? for a one-page overview of the framework. Browsing by chapter? Use the chapter list below. Want to write your own? The LL Playground compiles an LLP program you type or paste into JavaScript, right in your browser, and runs it on the same step / run / reset demo widget used throughout the site. All source code is also on GitHub: sequential book and parallel book.

Chapters

• Chapter 1 — Introduction to Algorithms

  Asymptotic notation, basic data structures, and the analysis of a few foundational algorithms (Euclid's GCD, binary search, Tower of Hanoi). Sets the vocabulary for the rest of the book.

• Chapter 2 — Lattice-Linear Predicate Detection

  The framework that drives the rest of the book: a finite distributive lattice, a lattice-linear predicate, and the LLP main loop. Includes runnable demos of LLP-GCD, LLP-EuclidGCD, and the LLP-JobScheduling variants.

• Chapter 3 — The Stable Marriage Problem

  Gale-Shapley as a special case of the LLP framework. Step through deferred-acceptance proposals on a 3×3 instance and watch the proposal vector advance.

  LLP form · Classical form

• Chapter 4 — Sorting Algorithms

  Sorting from the LLP perspective: every comparison-based sort can be cast as an LLP algorithm whose forbidden-index test detects an inversion. Demos for LLP-Sort-Adjacent (transposition form) and LLP-Sort-Pairwise.

  LLP form · Classical form

• Chapter 5 — Graphs

  Directed graphs, BFS, DFS, DAG layering, and strongly connected components. The LLP perspective recasts BFS distance and DAG layering as fixed-points on the vertex vector. Demos for LLP-BFS and LLP-Layering.

  LLP form · Classical form

• Chapter 6 — Greedy Algorithms

  Interval scheduling, interval partition, minimising maximum lateness, Huffman trees, and fractional knapsack. The exchange-argument template for proving greedy correctness, plus the LLP recasting on the boolean and start-time lattices. The chapter now also includes a Constrained Greedy section that composes mandatory subsets, excluded rooms, release times, and precedences with the base LLP programs.

  LLP form · Classical form

• Chapter 7 — The Shortest Path Problem

  Dijkstra (greedy), BellmanFord (DP), FloydWarshall (APSP), and Johnson (reweighting). Each has an LLP form on the distance vector; LLP-Dijkstra, LLP-BellmanFord, LLP-FloydWarshall, and LLP-Johnson. A Constrained Shortest Path section composes hop-budget and resource-budget rules onto LLP-Dijkstra.

  LLP form · Classical form

• Chapter 8 — The Minimum Spanning Tree Problem

  Kruskal, Prim, and Borůvka — three greedy algorithms on the same edge-inclusion lattice. LLP forms cover all three (LLP-Kruskal, LLP-Prim, LLP-Boruvka); LLP-Borůvka is the classic pointer-jumping kernel. A Constrained MST section adds mandatory-edge composition.

  LLP form · Classical form

• Chapter 9 — Divide and Conquer

  The Master Theorem and a tour of recurrence-driven algorithms: MergeSort, QuickSort, ClosestPair, CountingInversions, and Karatsuba.

  LLP form · Classical form

• Chapter 10 — Dynamic Programming

  Overlapping sub-problems via memoisation and bottom-up table fill. Covers Weighted Interval Scheduling, Longest Increasing Subsequence, Optimal Binary Search Tree, and 0/1 Knapsack.

  Chapter setup · Classical algorithms

• Chapter 11 — Network Flow

  Augmenting-path methods (FordFulkerson, EdmondsKarp), the max-flow / min-cut duality, and applications to bipartite matching and edge-disjoint paths.

  LLP form · Classical form

• Chapter 12 — Bipartite Matching

  The augmenting-path matching algorithm, the König / Dilworth duality, and chain-cover / antichain extraction. Demo for LLP-Antichain on a small poset; a vertex-cover construction ships as an LL program.

  LLP form · Classical form

• Chapter 13 — Intractability

  NP-completeness, polynomial-time reductions among 3-SAT, Independent Set, Vertex Cover, Clique, and Subset Sum.

• Chapter 14 — Approximation Algorithms

  Polynomial-time approximations for NP-hard problems: a 2-approximation for minimum Vertex Cover (ApproxVertexCover), the greedy $H_n$-approximation for Set Cover (ApproxSetCover), and an FPTAS for $0/1$ Knapsack (FPTAS-Knapsack). LLP recastings: LLP-LexMatchVertexCover, LLP-LexGreedySetCover, LLP-ApproxKnapsack.

  LLP form · Classical form

• Chapter 15 — The Housing Allocation Problem

  Core allocations in housing markets via Gale's Top Trading Cycle algorithm and an LLP formulation on the proposal vector (LLP-Housing-Market). Parallel TTC via randomised pointer-jumping.

  LLP form · Classical form

• Chapter 16 — Linear Programming

  Formulating and solving optimisation problems with linear constraints. The chapter includes a brief simplex sketch worked on the chapter's own primal example, a dual-recovery example using complementary slackness, an LP-rounding subsection that gives the $2$-approximation for vertex cover, and a max-flow / min-cut primal–dual LP pair that cross-references the Network Flow chapter.

• Chapter 17 — The Assignment Problem

  Market clearing prices, the Hungarian method, and the ascending-price LLP algorithm. Programs for ConstrainedMarketClearingPrice and LLP-Assignment.

  LLP form · Classical form

• Chapter 18 — Horn and 2-SAT Satisfiability

  Polynomial-time fragments of SAT. The lattice-linear formulation (LLP-HornSAT) and 2-SAT via implication graphs and strongly connected components.

  LLP form · Classical form

• Chapter 19 — Algorithms in Number Theory

  GCD and Extended Euclidean, cast as LLP algorithms on the divisor lattice. Programs: GCD1, Ext-GCD.

  LLP form · Classical form

• Chapter 20 — The Predicate Detection Problem

  Detecting global predicates on distributed computations using vector clocks and consistent cuts. Programs for ConjunctiveAlgorithm (forbidden/advance on the cut lattice). The chapter now also includes a Valiant–Vazirani section showing that lattice-linearity alone is not enough: there exist lattice-linear (in fact regular) predicates whose detection is NP-hard under randomized reductions, so the strong-polynomial LLP bounds require both lattice-linearity and efficient advancement.