Overview of Course

Splay Trees

Amortized Time for Splay Trees

Maintaining Disjoint Sets

Binomial heaps

F-heap

Minimum Spanning Trees

Fredman-Tarjan MST Algorithm

Branching Problem

Light Approximate Shortest Path Trees

Matchings

Hopcroft-Karp Matching Algorithm

Two Processor Scheduling

Assignment Problem

Network Flow - Maximum Flow Problem

The Max Flow Problem

An O(n) Max-Flow Algorithm

Vertex Covers and Network Flow

Planar Graphs

Planar Graphs

Graph Coloring

Graph Minor Theorem and other CS Collectibles

The Min Cost Flow Problem

Min Mean Cycle Problem

Shortest Path based Algorithm for Min Cost Flows

NP-completeness

NP-Completeness

NP-Completeness

More on NP-Completeness

Satisfiability

Linear Programming

Bin Packing

Nemhauser-Trotter Theorem

Vertex Cover

Weighted Vertex Cover

A ( − f(n)) Approximation Algorithm for the Vertex Cover Problem

Approximation Algorithms: Set Cover

Approximation Algorithms: Set Cover and Max Coverage

Approximation Algorithms: K-Centers

Multi-cost Minimum Spanning Trees

Set and Vertex Cover Approximations: Randomized Algorithms

Steiner Tree Problem

Traveling Salesperson and Chinese Postman Problem

Vehicle Routing Problems:Stacker Crane

Vehicle Routing Problems: Capacity Bounded Vehicles

Unit Capacity Problem (-delivery TSP)

K-capacity problem

Unbounded capacity problem

Lower Bounds on Approximations

Lower Bounds on Approximations (contd)

Linear Programming: The Use of Duality

Using duality to analyze (and design) approximation algorithms

A General Approximation Technique for Constrained Forest Problems

The Primal-Dual Method for Linear Programming

The Primal-Dual Method applied to Max weight perfect matching in bipartite graphs

On Line vs. Off Line: A Measure for Quality Evaluation