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.

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 — Lattice-Linear Language

  A small surface language for composing LLP programs. Seven composition operators — sequencing, parallel composition, nondeterministic choice, pipelining, predicate conjunction, synchronous composition, and feedback — let larger LLP programs be assembled from smaller ones. Stub page; full demos to follow.

• Chapter 4 — 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 5 — 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 6 — 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 7 — 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 8 — 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, and LLP-Johnson. A Constrained Shortest Path section composes hop-budget and resource-budget rules onto LLP-Dijkstra.

  LLP form · Classical form

• Chapter 9 — 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.

• Chapter 10 — Divide and Conquer

  The Master Theorem and a tour of recurrence-driven algorithms: MergeSort, QuickSort, ClosestPair, CountingInversions, and Karatsuba. LLP reformulations for LLP-NearestNeighbor, LLP-CountInversions, and LLP-ConvexHull.

• Chapter 11 — 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. Demos for LLP-WeightedIntervalScheduling, LLP-LIS, and LLP-Knapsack-Step.

• Chapter 12 — Network Flow

  Augmenting-path methods (FordFulkerson, EdmondsKarp), the max-flow / min-cut duality, and applications to bipartite matching and edge-disjoint paths. The lattice of mincuts admits a constrained-mincut LLP algorithm LLP-MinCut.

• Chapter 13 — 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; parallel chain-cover and vertex-cover constructions ship as LL programs.

• Chapter 14 — Intractability

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

• Chapter 15 — 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-LexicallyFirstVertexCover, LLP-LexicallyFirstSetCover, LLP-ApproxKnapsack.

• Chapter 16 — 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.

• Chapter 17 — 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 18 — The Assignment Problem

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

• Chapter 19 — Horn and 2-SAT Satisfiability

  Polynomial-time fragments of SAT. Dowling–Gallier forward chaining (HornSAT-FC), the lattice-linear formulation (LLP-HornSAT), and 2-SAT via implication graphs and strongly connected components.

• Chapter 20 — Algorithms in Number Theory

  GCD (descending and ascending), Extended Euclidean, Chinese Remainder Theorem (ascending and descending), LCM, and multiplicative order — all cast as LLP algorithms on the divisor lattice. Programs: GCD1, GCD2, Ext-GCD, Par-CRT, Par-CRT2, LCM1, Ord.

• Chapter 21 — 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) and ParallelCut (five-step parallel algorithm with state rejection and transitive closure). 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.

• Chapter 22 — Enumeration Algorithms

  Enumerating all min cuts via join-irreducible decomposition and slicing on the lattice of minimum $s$-$t$ cuts. Programs: ComputeSlice, LeastJoinIrreducible, AllJoinIrreducible.

• Chapter 23 — Equilevel Predicate Detection

  Advance every forbidden index in parallel: the equilevel pattern that underlies the parallel forms of bipartite matching, MST, shortest paths, and the housing market. Algorithms Equilevel, Equilevel-Independence, Solitary, and LLPwithRejection formalise the schema; demo program EquilevelDemo.

• Chapter 24 — The Stable Marriage Problem Revisited

  Variants of stable matching: downward (β) traversal of the proposal lattice, strongly and super-stable matchings under ties, the hospital–resident generalisation, online arrivals, and early-fixing. Demo program LLP-BetaStableMarriage.

• Chapter 25 — The Shortest Path Problem Revisited

  Early-fixing shortest-path algorithms (SP$_1$, SP$_2$, SP$_3$) that fix multiple vertices per outer iteration, plus the integration of Dijkstra's algorithm with the topological-sort algorithm for acyclic graphs. Stub page; full demos to follow.