- Understanding techniques to design and analyse data structures. These will find applications in combinatorial algorithms that we study.
- Learning and designing efficient algorithms for basic graph theoretic problems that are used as building blocks elsewhere. These include shortest paths, minimum spanning trees, matching, flow etc.
- An understanding of the inherent complexity of problems: Polynomial time, NP-completeness, Approximation Algorithms etc.

Spring 2002

** Final exam is on May 21st. 1.30 - 3.30 pm in JMP 3201.You are allowed THREE handwritten sheets of paper (8.5 by 11 inches). The sheets could be written both sides. That is the only material allowed. The sheets HAVE to be handwritten.
**

** Solutions to a homework could be obtained by augmenting the class page URL with the string sx.ps where x is replaced by the corresponding homework number. This is to make sure that Google does not grab our homework solutions!
**

Graded homework 5 is available. You can collect yours at the TA office hours this Friday. Homework 6 will be available on Monday during the TA office hours.

General Information Course Overview Homeworks and Handouts Lectures Related StuffClass Time |
Tue, Thur 9:30-10:45. |

Room |
CLB 0109 |

Instructor |
Samir Khuller |

Office |
A.V. Williams 3217. |

Office phone |
405 6765 |

Office Hours |
Tue 10.45-11.45 and by appointment. |

Email |
samir@cs.umd.edu |

Teaching Assistant |
Srinivasan Parthasarathy |

Office |
A.V. Williams 4140. |

Office Hours |
Mon & Fri 2.30 - 3.30 |

Email |
sri@cs.umd.edu |

The following broad aims will be attempted.

Homework 01

Homework 02

Homework 03

Homework 04

Homework 05

Homework 06

Lecture 01: Overview and Mortized Analysis

Lecture 02: Bipartite Matching

Lecture 03: Bipartite Matching

Lecture 04: Two Processor Scheduling

Lecture 05 : Chapter 10, Combinatorial Optimization, Papadimitriou & Steiglitz

Lecture 06: Faster Bipartite Matching

Lecture 07: Weighted Matching

Lecture 08: Flows

Lecture 09: Flows

Lecture 10 : Max flow algorithm, Chapter 9, Combinatorial Optimization, P & S

Lecture 11 : (Flow in Unary Capacity Networks) Chapter 9, Combinatorial Optimization, P & S

Lecture 12 Introduction to Min Cost Flows

Lecture 13 : Min-mean cycle (Handout from Network Flow Book)

Lecture 14 : Min-mean cycle (Dynamic Programming)

Lecture 15 : Exam

Lecture 16 : Go over exam and finish min-mean cycle proof

Lecture 17 : Min Cost Flows - Shortest Paths (2 handouts)

Lecture 18 : Applications of Min Cost Flows - solving LP's (handout from Network Flow Book)

Lectures 19 & 20: Linear Programming and Duality

Lectures 21 & 22: Primal Dual Algorithms (read Chapter 5 of PS)

Lectures 23: Shortest Paths solved by a Primal Dual Algorithm (Chap 5)

Lecture 24: Min Cost Branchings

Lecture 25: Introduction to NP-completeness, 3 SAT to Graph coloring

Lecture 26: Reductions: 3SAT to Clique, 3 SAT to Vertex Cover, Clique to MultiProcessor Scheduling

Lecture 27: Cook's Theorem

Lecture 28: Approximation Algorithms: Vertex Cover