Advanced Algorithms - CS 6/76101

Fall 2022

 

Class schedule: MW 05:30 pm - 06:45 pm

Office hours: (Remote/F2F) MW 5:00 - 5:30 pm and 6:45 - 7:15 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

Network Flow and Matching

pdf

Reading 

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

 

 

Demos 

  1. Quick Hull
  2. Graham&Yao Hull
  3. Segment intersection
  4. 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 

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

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/14/2022 (25 minutes).

2.       Quiz #2 on Greedy Algorithms chapter (HC, AS and FK algorithms) is on 9/26/2022 (25 minutes).

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/2022 (25 minutes).

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/19/2022 (25 minutes).

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/02/2022 (25 minutes).

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/2022 (25 minutes).

 

EXAMS

  1. Mid-Term #1 by October 2022 (as 3 quizzes)
  2. Mid-Term #2 by November 2022 (as 3 quizzes)
  3. Mon., Dec. 12, 5:45 - 8:00 p.m. (info survey)

 

 

 

 

 


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

 

NOTICE OF MY COPYRIGHT AND INTELLECTUAL PROPERTY RIGHTS. Any intellectual property displayed or distributed to students during this course (including but not limited to powerpoint presentations, notes, quizzes, examinations) by the professor remains the intellectual property of the professor. This means that the student may not distribute, publish or provide such intellectual property to any other person or entity for any reason, commercial or otherwise, without the express written permission of the professor.