Advanced Algorithms - CS 6/76101

Fall 2011

 

Class schedule: TR 12:30 – 1:45 pm, MSB 121

Office hours: TR 2:00 – 4:00 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 (2nd Edition) or 2009 (3rd 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).

HOMEWORKS 

  1. Homework#1   (Due 09/20/2011)
  2. Homework#2   (Due 10/04/2011)
  3. Homework#3   (Due 10/13/2011)
  4. Homework#4   (Due 11/08/2011)
  5. Homework#5   (Due 11/29/2011)
  6. Homework#6   (Due 12/06/2011)

 

 

Extra credit problem: distributed on 11/08/2011, due 11/29/2011.

 

 

EXAMS

  1. Tuesday, October 25, 2011, 12:30 -1:45 pm {Dynamic Programming, Greedy Algorithms, Amortized Analysis, Parallel Algorithms}  info survey
  2. Friday, December 16, 2011, 12:45 - 3:00 p.m.  {Computational Geometry, NP-Completeness, Approximation Algorithms, Max-Flow and Maximum Matching} info survey

 

 

 

 

 


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