Fall 2004Unique Number 54245CS 388GAlgorithms: Techniques and Theory

InstructorGreg Plaxton, 471-9751, TAY 3.132, office hours M 10-11 and F 2-3TANed 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/17Class TimeMW 3:00-4:30 Class LocationWEL 2.256 TextbookT. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press/McGraw-Hill, 2nd edition, 2001.Course OutlineThis 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. PrerequisitesGraduate standing and either CS 357 (or an equivalent course) or consent of instructor Problem SetsThere 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.PresentationsMost 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 SchemeThe 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 DatesThe two in-class tests will take place on Wednesday, October 6andWednesday, 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.