Advanced Algorithms - CS 6/76101

Fall 2012

Class schedule: MW 5:30 - 6:45 pm, MSB 109

Office hours: MW 1:15 - 3:15 PM

Topics	Slides
Dynamic Programming	pdf
Greedy Algorithms	pdf
Amortized Analysis	pdf
Parallel Algorithms	pdf
Computational Geometry	pdf
NP-Completeness:1	pdf
NP-Completeness:2	pdf
Approximation Algorithms	pdf
Exact Solutions to NP-Complete Problems	-
Network Flow and Matching	pdf

Reading

1. The P versus NP Problem .
2. PRIMES is in P
3. Ch
4. TSP

Demos 

1. A Stable Marriage Applet 
2. An Applet of SkipList
3. Convex Hull
4. Quick Hull
5. Graham&Yao Hull
6. Segment intersection
7. An Applet of Max Flow

Textbook:  Introduction to Algorithms, McGraw Hill Publishing Company and MIT Press, 2001 (2^nd Edition) or 2009 (3^rd edition). 

by Thomas Cormen,       Charles Leiserson,       Ronald Rivest, and       Cliff Stein

The MIT Press web site for the textbook is http://mitpress.mit.edu/algorithms (note that it is for the 3^rd edition).

---

HOMEWORKS 

---

1. Homework#1
2. Homework#2
3. Homework#3
4. Homework#4
5. Homework#5
6. Homework#6

Extra credit problem: distributed on 11/14/2012, due 11/28/2012.

---

EXAMS

---

1. Monday, October 22, 2012, 5:30 -6:45 pm {Dynamic Programming, Greedy Algorithms, Amortized Analysis, Parallel Algorithms}  info survey
2. Monday, December 10, 2012, 5:45 - 8:00 p.m. {Computational Geometry, NP-Completeness, Approximation Algorithms} info survey

---

F. Dragan
dragan at cs.kent.edu
Fall 2012