### 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 Approximation Algorithms pdf Exact Solutions to NP-Complete Problems - Network Flow and Matching pdf

Demos

Textbook:  Introduction to Algorithms, McGraw Hill Publishing Company and MIT Press, 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.

HOMEWORKS

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/03/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/17/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 10/31/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 11/21/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