Advanced Algorithms - CS 6/76101

Fall 2017

 

Class schedule: T 5:30 pm - 08:15 pm, MSB 276

Office hours: T 4:00 - 5:30 PM or by appointment

 

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. Convex Hull
  3. Quick Hull
  4. Graham&Yao Hull
  5. Segment intersection
  6. An Applet of Max Flow

 

 

Textbook:  Introduction to Algorithms, McGraw Hill Publishing Company and MIT Press, 2009 (3rd edition). 

 

 

by Thomas Cormen
     Charles Leiserson
     Ronald Rivest, and 
     Cliff Stein 

http://www.cs.kent.edu/%7Edragan/CS6-76101-AdvAlgF11_files/image003.jpg

The MIT Press web site for the textbook is http://mitpress.mit.edu/algorithms.


HOMEWORKS 


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

QUIZZES (as parts of Mid-Terms) 


1.      Quiz #1 on Dynamic Programming chapter (LCS and CMM algorithms) is on 9/12/2017 (first 25 minutes of the class).

2.      Quiz #2 on Greedy Algorithms chapter (HC, AS and FK algorithms) is on 9/19/2017 (first 25 minutes of the class).

3.      Quiz #3 on Amortized Analysis chapter (one of the three methods to apply to a problem; see problems 1 - 3 of HW3) is on 10/??/2017 (first 25 minutes of the class).

4.      Quiz #4 on Parallel Algorithms chapter (there will be a problem(s) similar to problems 30.1-1, 30.1-2, 30.1-3, 30.2-8, 30.5-2, 30.5-3) is on 10/??/2017 (first 25 minutes of the class).

5.      Quiz #5 on Computational Geometry chapter (know cross product operations and algorithms for `whether any pair of segments intersect`, `convex hull`, `closest pair`) is on 11/??/2017 (first 25 minutes of the class).

6.      Quiz #6 on NP-Completeness chapter (know definitions of complexity classes and reductions: 3Col to CCov, 3SAT to IS, IS to CLIQUE, IS to VC, 3SAT to DHP) is on 12/??/2017 (first 25 minutes of the class).

 



EXAMS


  1. Mid-Term #1 by October, 2017 (as quizzes)
  2. Mid-Term #2 by November, 2017 (as quizzes)
  3. Tuesday, December 12, 2017, 8:15 - 10:30 p.m. info survey

 

 

 

 

 



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