Advanced Algorithms
Fall 2000
CS 6/76101
Email: jbaker@mcs.kent.edu
Office: Normally MSB 241B; Occasionally 260
Phones: 672-9055 or 672-9061
Office Hours:
- 11-2 on TuTh and immediately after class.
- I normally have some free time during 12-4 MWF, but my free time varies.
- By special appointment.
Teaching Assistant: Haoyi Wang
Email: hwang@mcs.kent.edu
Office: 132
Phone: 29001
Office Hours: MW 2:30-4:30 pm
Syllabus (pdf)
Primary Textbook
Thomas Cormen, Charles Leisterson, and Ronald Rivest, Introduction to Algorithms, McGraw Hill Publishing
Company and MIT Press, 1990.
Additional Primary Book & Web References
- Ellis Horowitz, Sartaj Sahni, and Sangurthevar Rajasekaran, Computer Algorithms , Computer Science
Press, 1998.
- Gilles Brassard and Paul Bratley, Fundamental of Algorithmics , Prentice Hall, 1996.
- Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms , Cambridge University Press, 1995.
- Michel Goemans, Advanced Algorithms Course Notes are available
from this website.
- Homepage for textbook
- 1994 Textbook Errata : Some old errors are not easily
fixed without changing page numbering.
Lecture Notes and Tests:
- Comments on Lecture Notes
- Syllabus & Introduction ( pdf )
- Amortized Analysis I ( pdf )
- Amortized Analysis II ( pdf )
- Dynamic Algorithms ( pdf )
- Greedy Algorithms: Class Handout of copy of slides
- Parallel Algorithms: Class Handout of copy of slides
- Computational Geometry: Class Handout of copy of slides
- Midterm Exam covers preceding lectures and problem sets, except for problem set on Computational geometry.
- NP-Completeness: Class Handout of copy of slides
- Approximation Algorithms: Class Handout of copy of slides
- Algorithms for Exact Solutions of NP-hard Problems: Class Handout of copy of slides
- Randomized/Probabilistic Algorithms: Class Handout of copy of slides
- Review comments for final exam, which
includes all material covered since the midterm (i.e., starting with Ch. 36 on NP-Completeness)
Reading Assignments
- Read Chapter 18 in CLR textbook
- Read Sections 16.1, 16.2, 16.4 in CLR textbook
- Read Sections 17.2, 17.3 in CLR textbook
- Read Sections 30.1, 30.2, 30.5 in CLR textbook
- Read Chapter 35 in CLR
- Read Chapter 36 in CLR
- Read Chapter 37 in CLR
- Read Sections 7.1, 7.2, 7.3, 7.5, 8.1, 8.1.1, 8.1.2, 8.1.3 in HSR reference
- Read Chapter 10 in BB reference (skip subsections of 10.6 and 10.7 that are not discussed in slides). Chapter
1 of MR reference is also a primary reference here, but is not assigned reading.
Homework Assignments -- Due Dates:
- Assignment I: Exercises 18.1-3, 18.2-2, 18.3-3, 18.4-3, Problem 18.2
- Assignment II: Exercises 16.1-2, 16.2-3, 16.4-1, Problem 16.3, Exercises 17.3-4, 17.3-7, Problem 17.1
- Assignment III: Exercises 30.1-2, 30.1-9(Cost Optimal Prefix Operations), 30.2-4, 30.2-8, 30.5-4
- Assignment IV: Exercises 35.1-7, 35.2-4, 35.3-2, 35.4-2, 36.1-1, 36.1-4
- Assignment V: Exercises 36.3-1, 36.3-3, 36.4-3, 36.5-2, 36.5-7
- Assignment VI: Work 4 of the following 6 problems and discuss briefly problem requirements and solution ideas
on all unsolved problem. Extra credit given for solving additional problems in this list. Due at time of final
exam.
- Problems 37.1-2, 37.2-2, (37.3-2 or 36.5-4 on NP reductions), 37.3-5, Exercise 1 on pg 355 in HSR, Exercise
3 on pg 366 of HSR.