- 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.
- Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
- Combinatorial Optimization by Papadimitriou and Steiglitz.
- Combinatorial Optimization by Cook, Cunningham, Pulleyblank and Schrijver.

Fall 2003

** 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.
Homework 8 has been graded. You could either pick it up during the TA's office hours on Tuesday or from his office
AVW-4122 (if he is there).
Solutions 1-8 are now on the class page
Class on Dec 10th will start at 4pm. Prof. Boneh from Stanford is giving a talk 3-4 pm in AVW 2460.
**

**
**

General Information Course Overview Homeworks and Handouts Lectures Related Stuff

Class Time |
Mon, Wed 3:30-4:45. |

Room |
CSIC 3120 |

Instructor |
Samir Khuller |

Office |
A.V. Williams 3369. |

Office phone |
405 6765 |

Office Hours |
Mon, Tue 2-3 |

Email |
samir@cs.umd.edu |

Teaching Assistant |
Chiu-Yuen Koo |

Office |
A.V. Williams 1151. |

Office Hours |
Tu 11-1 |

Email |
cykoo@cs.umd.edu |

The following broad aims will be attempted.

Median : 82

90-100 : 7

80-89 : 15

70-79 : 10

60-69 : 1

<=59 : 2

Homework 0 (Ungraded HW)

Homework 1 (Due Sep 24) (Average: 85.39)

Homework 2 (Due Oct 1) (Average: 80.48)

Homework 3 (Due Oct 15) (Average: 84.70)

Homework 4 (Due Oct 22) (Average: 80.96) NOTE: lcm is lowest common multiple (problem 5). Common Error: You will lose 7 points for problem 3 if you don't specify the source vertex for the Bellman-Ford Algorithm. Note that you cannot pick an arbitrary vertex v as the source since the negative cycle may not be reachable from v.

Homework 5 (Due Nov 10 (changed)) (Average: 88.45)

Homework 6 (Due Nov 19 (Average: 83.25)

Homework 7 (Due Dec 3 (Average: 87.73)

Homework 8 (Due Dec 10 (Average: 88.91) CHANGED PROBLEM 4! Sorry for the confusion. If you printed a copy before 10:30am on Fr, please print it again.

Lecture 01: Overview and Mortized Analysis

Lecture 02: Binomial and Fibonacci heaps

Lecture 03: Fibonacci Heaps and Two Processor Scheduling

Lecture 04: How to do Research (Gasarch CSIC 1121)

Lecture 05: Bipartite Matching

Lecture 06: Matching in general graphs (See Books)

Lecture 07: Weighted Matching

Lecture 08: Flows

Lecture 09: Flows

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

Lecture 11 : Preflow-Push method (read CLR)

Lecture 12: Introduction to Min Cost Flows

Lecture 13: Min-Mean Cycle Algorithm

Lecture 14 : Min-mean cycle (Dynamic Programming-- See Handout)

Lecture 15 : Min Cost Flows - Shortest Paths. See Handout for applications of Min Cost Flows.

Lecture 16 : Review

Lecture 17 : MIDTERM (CSIC 2117, Oct 29)

Lecture 18: Exam Review

Lecture 19: Guest Lecture by Micah Adler (U Mass). In 2460 AVW 3-4pm.

Lectures 20 and 21: Linear Programming

Lecture 22: Primal-Dual algorithms for LP's

Lecture 23: Weighted Matching solved by a Primal Dual Algorithm

Lectures 24 and 25: Introduction to NP-completeness, 3 SAT to Graph coloring, 3SAT to Clique, Clique to MultiProcessor Scheduling, 3 SAT to Disjoint Paths.

Lecture 26: 3 SAT to PARTITION.

Lecture 27: 2 SAT and Vertex Cover

Lecture 28: Cook's Theorem