A Systematic Approach to Algorithms

Vijay K. Garg · The University of Texas at Austin

A textbook that develops a systematic method for deriving algorithms by casting each problem as the search for an element satisfying an appropriate predicate in a distributive lattice.

• Companion website for students Runnable code and interactive demos
• Resources for instructors A solution manual is available to instructors on request

Problems and algorithms covered

• Introduction to Algorithms: Asymptotic notation, analysis of efficiency, common data structures, heaps.
• Lattice Linear Predicate Detection: Lattice-linear predicates and LLP notation; a sequential implementation of the LLP algorithm; the priority tag; the dual of lattice-linearity.
• Stable Marriage Problem: Gale-Shapley algorithm.
• Sorting: Bubble, insertion, quicksort, and merge sort; counting and radix sort; the comparison-based lower bound.
• Graphs: Breadth-first and depth-first search; layering of a directed acyclic graph; topological sort; strongly connected components.
• Greedy Algorithms: Interval scheduling, interval partitioning, minimizing maximum lateness, Huffman codes, fractional knapsack.
• Shortest Path Problems: Dijkstra's, Bellman-Ford, and Johnson's algorithms.
• Minimum Spanning Tree: Kruskal's, Prim's, and Boruvka's algorithms; constrained minimum spanning tree.
• Divide and Conquer: Closest pair of points, counting inversions, planar convex hull, Karatsuba's multiplication, Strassen's matrix multiplication, the fast Fourier transform; the Master Theorem.
• Dynamic Programming: Longest increasing subsequence, optimal binary search tree, knapsack.
• Network Flow: Ford-Fulkerson and Edmonds-Karp algorithms; max-flow min-cut duality.
• Bipartite Matching: Maximum matching; vertex cover in a bipartite graph; chain partition of a poset; Dilworth's and Menger's theorems.
• Intractability: Class P, polynomial-time reductions, NP-completeness, co-NP; coping with NP-hardness.
• Approximation Algorithms: Vertex cover, set cover, PTAS and FPTAS; hardness of approximation.
• Housing Allocation: Gale's top trading cycle algorithm.
• Linear Programming: Duality, LP relaxation and total unimodularity, LP formulations of combinatorial problems.
• Assignment Problem: Demange-Gale-Sotomayor algorithm.
• Horn and 2-SAT Satisfiability: Algorithms to check satisfiability of a Horn formula and of a 2-SAT formula.
• Number Theory: Euclid's GCD and extended GCD algorithms; the Chinese Remainder Theorem.
• Predicate Detection: Complexity of predicate detection; conjunctive predicates; recognizing closure properties.

Related publications on lattice-linear predicates

The following papers develop the lattice-linear predicate framework, extend it to related classes of predicates, or apply it to algorithm design.

1. Robert P. Streit and Vijay K. Garg. Invited Paper: Approximation Algorithms via Lattice-Linear Predicates. SSS 2026. [PDF]
2. Robert Streit and Vijay K. Garg. Constrained Cuts, Flows, and Lattice-Linearity. PDCO 2026, with IPDPS 2026. [arXiv]
3. Arya Tanmay Gupta and Sandeep S. Kulkarni. Tolerance to Asynchrony in Algorithms for Multiplication and Modulo. Theoretical Computer Science 1024, 114914, 2025. [DOI] [arXiv]
4. Vijay K. Garg and Robert P. Streit. Parallel Algorithms for Equilevel Predicates. ICDCN 2024, pp. 104–113. [DOI] [arXiv]
5. Vijay K. Garg and Changyong Hu. Improved Paths to Stability for the Stable Marriage Problem. SSS 2023, pp. 126–140. [DOI] [arXiv]
6. Vijay K. Garg. Keynote Talk: Lattice Linear Predicate Algorithms for the Constrained Stable Marriage Problem with Ties. ICDCN 2023, pp. 2–11. [DOI] [arXiv]
7. David R. Alves and Vijay K. Garg. Parallel Minimum Spanning Tree Algorithms via Lattice Linear Predicate Detection. PDCO 2022, with IPDPS 2022, pp. 774–782. [PDF] [DOI]
8. Vijay K. Garg. A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems. ICDCN 2022. [arXiv]
9. Vijay K. Garg. A Lattice Linear Predicate Parallel Algorithm for the Housing Market Problem. SSS 2021, pp. 108–122. [PDF] [DOI]
10. Arya Tanmay Gupta and Sandeep S. Kulkarni. Extending Lattice Linearity for Self-Stabilizing Algorithms. SSS 2021, pp. 365–379. [DOI] [arXiv]
11. Vijay K. Garg. Predicate Detection to Solve Combinatorial Optimization Problems. SPAA 2020, pp. 235–245. [PDF] [DOI] [slides] [video]
12. Vijay K. Garg and Rohan Garg. Parallel Algorithms for Predicate Detection. ICDCN 2019, pp. 51–60. [DOI]
13. Vijay K. Garg. Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem. DISC 2017, pp. 52:1–52:3. [DOI]