Algorithms Lab

Applications of LP Duality: Matchings, Flows and Shortest Path

Steiner Forest via Primal-Dual

MaxSat by LP Rounding

LP-based Approximation Algorithms for Set Cover: LP Rounding, Primal-Dual and Dual fitting

Linear Programming (LP) Duality, part 1: Introduction and Physical Interpretation

Linear Programming (LP) Duality, part 2: Farkas Lemma

Simplex Algorithm, part 4: Efficiency/Pivot Rules

Simplex Algorithm, part 2: Exceptions

Simplex Algorithm, part 3: the simplex algorithm in general

Simplex Algorithm, part 1: Introductory Example

Theory of Linear Programming: convex polytopes, equational form and basic feasible solutions

Integer Linear Programming

Traveling Salesperson Problem and the Held-Karp Dynamic Programming Algorithm

Approximation Algorithm for Metric k-Center using Parametric Pruning

Advanced Algorithms - Pre-Knowledge Check

Hash Tables (part 2): Resolving Collisions

Heaps (part 2): Heap Operations, Build Heap, Heapsort

Approximation Algorithms: Introduction by the Example of Vertex Cover

Polygon Triangulation, Art Gallery Problem

Elementary Data Structures (part 1): Stacks and Dynamic Arrays

searching in a hash table, worst-case vs average case

5.2 Elementary Data Structures: Resizing Growable Arrays (old version)

Approximation algorithm for vertex cover using local ratio (aka layering)

Binomial heaps (part 1/3): Introduction and worst-case analysis

Greedy Approximation Algorithm for Set Cover

Range Searching

Amortized Analysis: Aggregate Analysis and Accounting Method