Fall 2004
Unique Number 54245
CS 388G
Algorithms: Techniques and Theory


 
Instructor Greg Plaxton, 471-9751, TAY 3.132, office hours M 10-11 and F 2-3
   
TA Ned Dimitrov, office hours, PAI 3.12, MF 1-2; NOTE ADDED 9/13/04: Ned's office hours will be held in TAY 5.104 starting on Friday 9/17
   
Class Time MW 3:00-4:30
   
Class Location WEL 2.256
   
Textbook T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press/McGraw-Hill, 2nd edition, 2001.
   
Course Outline This is a graduate-level course in the design and analysis of algorithms. Topics covered will include common paradigms of algorithm design (e.g., divide-and-conquer, greedy,  dynamic programming, randomization) and analysis (e.g., recurrence-solving, amortized analysis, Chernoff bounds), sorting and searching, data structures (e.g., augmented balanced binary search trees, skip lists, splay trees, mergeable heaps, union-find structures), graph algorithms (e.g., depth-first search and its applications, network flow), linear programming, NP-completeness, approximation algorithms for NP-hard problems.
   
Prerequisites Graduate standing and either CS 357 (or an equivalent course) or consent of instructor
   
Problem Sets There will be six problem sets. The first problem set is for review purposes only and and will not be graded. For each of the remaining five problem sets, you will turn in solutions to a designated subset of the problems. Discussion of the problem sets with other members of the class is permitted. However, solutions must be written up separately. Also, any key idea that is obtained from another member of the class or from some other source (e.g., a web page or library book) must be properly cited. Over-reliance on such sources is strongly discouraged, i.e., you should make a significant effort to solve the problems on your own. If you find that you are having difficulty getting started on a problem, please stop by the office hours of either the TA or instructor to get some hints. The date on which each problem set is handed out or due is indicated on the class schedule. Solutions are due at the beginning of class.
   
Presentations Most of the lectures will begin with a student presenting a solution to one the problem set questions. These presentations should not exceed ten minutes in duration. (If you have a solution that requires more than ten minutes to present, then just present the main ideas.)
   
Grading Scheme The overall course grade will be based on five problem sets (6% each; 30% total), two in-class closed book tests (25% and 35%; 60% total), and class participation (10%). The class participation score is based on classroom attendance, contributions to classroom discussion, and scheduled in-class presentations.
   
Test Dates The two in-class tests will take place on Wednesday, October 6 and Wednesday, December 1. Please make sure that you can attend class on these two dates; no make-up tests will given. Each test is closed book and closed notes except that you are allowed to bring one 8.5 by 11 sheet with writing (or printing) on both sides. The tests are worth 25% and 35% of your final grade, respectively.