Advanced Algorithms - CS 6/76101

Fall 2009

 

Class schedule: TR 11:00 am -12:15 pm, MSB 115

Office hours: R 1:30 – 3:00 PM, TR 5:00 – 6:00 PM

 

 

Topics 

Slides per Page 

Dynamic Programming 

1 (pdf),  2 (pdf)

Greedy Algorithms 

1 (pdf),  2 (pdf)

Amortized Analysis 

1 (pdf),  2 (pdf)

Parallel Algorithms

1 (pdf),  2 (pdf)

Computational Geometry 

1 (pdf),  2 (pdf)

NP-Completeness:1 

1 (pdf),  2 (pdf)

NP-Completeness:2 

1 (pdf),  2 (pdf)

Approximation Algorithms 

1 (pdf),  2 (pdf)

Exact Solutions to NP-Complete Problems

1 (pdf),  2 (pdf)

Network Flow and Matching

1 (pdf),  2 (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 (2nd 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 3rd edition and we use the 2nd edition).

HOMEWORKS 

important notes (pdf)

  1. Homework#1   (Due 9/22/2009) results
  2. Homework#2   (Due 9/29/2009) results
  3. Homework#3   (Due 10/13/2009) results
  4. Homework#4   (Due 11/12/2009) results 
  5. Homework#5   (Due 11/19/2009) results 
  6. Homework#6   (Due 12/03/2009) results 

 

Extra credit problem: distributed on 11/12/2009, due 12/01/2009. results

 

HW Total

 

EXAMS

  1. Tuesday, October 27, 2009, 11:00 am -12:15 pm {Dynamic Programming, Greedy Algorithms, Amortized Analysis, Parallel Algorithms}  info survey results
  2. Tuesday, December 15, 2009, 12:45 - 3:00 p.m.  {Computational Geometry, NP-Completeness, Approximation Algorithms, Max-Flow and Maximum Matching} info survey results

 

Final Grades

 

 

 

 


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