Spring 2007
Unique Number 55160
CS 388G
Algorithms: Techniques and Theory

Instructor Greg Plaxton, 471-9751, TAY 3.132, office hours T 5-6, W 1-2, or by appointment.

TA Ned Dimitrov, office hours F 12-1, ESB 229. In any week when there is a problem set due on a Thursday, Ned will hold an extra office hour Th 10-11, also in ESB 229. However, Ned will be out of town February 12 to 20 and March 18 to 26. Ned will be holding some make-up office hours, as indicated on this schedule.

Class Time TTh 3:30-5

Class Location PAR 206

Required Textbook Jon Kleinberg and Éva Tardos, Algorithm Design, Addison Wesley, 2005.

Course Outline This is a graduate-level course in the design and analysis of algorithms. Most of the lecture material will be drawn from the course textbook. Here is the sequence of major topics to be covered, along with the corresponding textbook chapters: basic graph algorithms (2 lectures, Chapter 3); greedy algorithms (4 lectures, Chapter 4); divide and conquer (2 lectures, Chapter 5); dynamic programming (3 lectures, Chapter 6); network flow (4 lectures, Chapter 7); NP-completeness (2 lectures, Chapter 8); PSPACE-completeness (1 lecture, Chapter 9); extending the limits of tractability (1 lecture, Chapter 10); approximation algorithms (4 lectures, Chapter 11); randomized algorithms (3 lectures, Chapter 13). Time permitting, we will discuss some topics related to local search (Chapter 12).

Prerequisites Graduate standing and either CS 357 (or an equivalent course) or consent of instructor

Problem Sets There will be five problem sets. For each problem set, you will turn in solutions to a designated subset of the problems. Ned has prepared a brief (one page) style guide that offers some recommendations on how to write up your solutions. 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.

Quizzes Most of the lectures will begin with a short quiz based on material covered in the previous lecture. Each quiz will be graded out of 10. Attendance is worth 50%, i.e., anyone who turns in a quiz will get a score of at least 5 out of 10. The quizzes are open book/notes. As explained in the section below entitled "Overall Raw Score", all of your low quiz scores will be dropped in the computation of your course grade. If you miss a quiz for any reason (legitimate or otherwise), your score for that quiz will be a zero, so it will be dropped.

Tests There will be two in-class tests, on Tuesday, March 27 and Thursday, May 3. The tests are closed book/notes, except that you are allowed to bring one 8.5 by 11 sheet with writing (or printed material) on both sides.

Overall Raw Score Each student's overall raw score, out of 100 points, will be determined from performance on the five problem sets, the quizzes, and the two tests. The problem sets account for one-third of the overall raw score, with each problem set being weighted equally. The remaining two-thirds of the raw score is determined as follows. Let x denote your average score on the tests (expressed as a fraction, e.g., if you have a 70% test average, then x is 0.7), let n denote the total number of quizzes, let A denote the set of quizzes on which you scored higher than your test average, let y denote your average score (again expressed as a fraction) over the quizzes in set A, and let w denote 100 * |A| / (3n). Then your raw score out of 200/3 for the quizzes and tests is ((200/3) - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on both tests. Mary's raw score for the quizzes and tests is 200/3. Example 2: Joe enjoys a brief quiz -- and aces all of them -- but, for unknown reasons, he refuses to participate in any sort of "test". Joe's raw score for the quizzes and tests is 100/3. Example 3: Pat has a test average of 72%, and gets better than 72% on 20 out of a total of 30 quizzes. The average of Pat's top 20 quiz scores is 90%. Pat's raw score for the quizzes and tests is 400/9 * 0.72 + 200/9 * 0.9 = 52.

Instructor	Greg Plaxton, 471-9751, TAY 3.132, office hours T 5-6, W 1-2, or by appointment.

TA	Ned Dimitrov, office hours F 12-1, ESB 229. In any week when there is a problem set due on a Thursday, Ned will hold an extra office hour Th 10-11, also in ESB 229. However, Ned will be out of town February 12 to 20 and March 18 to 26. Ned will be holding some make-up office hours, as indicated on this schedule.

Class Time	TTh 3:30-5

Class Location	PAR 206

Required Textbook	Jon Kleinberg and Éva Tardos, Algorithm Design, Addison Wesley, 2005.

Course Outline	This is a graduate-level course in the design and analysis of algorithms. Most of the lecture material will be drawn from the course textbook. Here is the sequence of major topics to be covered, along with the corresponding textbook chapters: basic graph algorithms (2 lectures, Chapter 3); greedy algorithms (4 lectures, Chapter 4); divide and conquer (2 lectures, Chapter 5); dynamic programming (3 lectures, Chapter 6); network flow (4 lectures, Chapter 7); NP-completeness (2 lectures, Chapter 8); PSPACE-completeness (1 lecture, Chapter 9); extending the limits of tractability (1 lecture, Chapter 10); approximation algorithms (4 lectures, Chapter 11); randomized algorithms (3 lectures, Chapter 13). Time permitting, we will discuss some topics related to local search (Chapter 12).

Prerequisites	Graduate standing and either CS 357 (or an equivalent course) or consent of instructor

Problem Sets	There will be five problem sets. For each problem set, you will turn in solutions to a designated subset of the problems. Ned has prepared a brief (one page) style guide that offers some recommendations on how to write up your solutions. 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.

Quizzes	Most of the lectures will begin with a short quiz based on material covered in the previous lecture. Each quiz will be graded out of 10. Attendance is worth 50%, i.e., anyone who turns in a quiz will get a score of at least 5 out of 10. The quizzes are open book/notes. As explained in the section below entitled "Overall Raw Score", all of your low quiz scores will be dropped in the computation of your course grade. If you miss a quiz for any reason (legitimate or otherwise), your score for that quiz will be a zero, so it will be dropped.

Tests	There will be two in-class tests, on Tuesday, March 27 and Thursday, May 3. The tests are closed book/notes, except that you are allowed to bring one 8.5 by 11 sheet with writing (or printed material) on both sides.

Overall Raw Score	Each student's overall raw score, out of 100 points, will be determined from performance on the five problem sets, the quizzes, and the two tests. The problem sets account for one-third of the overall raw score, with each problem set being weighted equally. The remaining two-thirds of the raw score is determined as follows. Let x denote your average score on the tests (expressed as a fraction, e.g., if you have a 70% test average, then x is 0.7), let n denote the total number of quizzes, let A denote the set of quizzes on which you scored higher than your test average, let y denote your average score (again expressed as a fraction) over the quizzes in set A, and let w denote 100 * \|A\| / (3n). Then your raw score out of 200/3 for the quizzes and tests is ((200/3) - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on both tests. Mary's raw score for the quizzes and tests is 200/3. Example 2: Joe enjoys a brief quiz -- and aces all of them -- but, for unknown reasons, he refuses to participate in any sort of "test". Joe's raw score for the quizzes and tests is 100/3. Example 3: Pat has a test average of 72%, and gets better than 72% on 20 out of a total of 30 quizzes. The average of Pat's top 20 quiz scores is 90%. Pat's raw score for the quizzes and tests is 400/9 * 0.72 + 200/9 * 0.9 = 52.