Fall 2008
Unique Number 55695
CS 357
Design and Analysis of Algorithms

Instructor Greg Plaxton (office hours W 4-5 and F 3-4, TAY 3.132; email: plaxton at cs)

Teaching Assistant Chinmayi Krishnappa (office hours T 10-11 and Th 4-5, Desk 1 in ENS 31NQ; email: chinmayi at cs). Directions to ENS 31NQ: (1) take the elevator down to "LB" (lower basement); (2) exit the elevator to the right; (3) keep going down the hallway, which will curve to the right; (4) enter room 31NR, which will be on your left; (5) go through 31NR to a smaller room, which is 31NQ; (6) there are six desks marked 1 through 6.

Extended Office Hours Each of the four office hours listed above will be extended half an hour (e.g., W 4-5:30 instead of W 4-5) if there is a test or an assignment due during the week following the office hour. Example: Suppose that an assignment is due at 10am on Wednesday, September 24. Then every office hour between 10am on Wednesday, September 17 and 10am on Wednesday, September 24 will be extended by half an hour.

Class Time MWF 10-11

Class Location ENS 145

Textbook The textbook for the course is Algorithm Design by Kleinberg and Tardos (Addison-Wesley, 2006).

Course Outline The following major topics will be covered: analysis of algorithms, graph algorithms, greedy algorithms, divide-and-conquer, dynamic programming, network flow, NP-completeness, approximation algorithms, randomized algorithms. See the schedule for a more detailed specification of the lecture plan.

Assignments There will be six assignments. For the most part, the assignments will involve paper-and-pencil problem solving. However, some of the assignments will include a small programming component. You are allowed to discuss high-level approaches to the assignment problems with other members of the class, but you are not allowed to discuss or exchange detailed solutions.

Quizzes Most of the lectures will include a brief quiz based on material from the previous lecture. 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 three in-class tests. The tests will be closed book and closed notes; you are only allowed to bring one page of notes (both sides may be used). The first test will be held on Monday, September 29 and will cover all of the course material up to September 26. The second test will be held on Friday, October 31 and will cover all of the course material from October 1 to October 29. The third test will be held on Friday, December 5 and will cover all of the course material from November 3 onward. Please try to arrive in class a few minutes early on the test dates; this will allow us to start the test right at the beginning of the class period.

Make-Up Tests Please note that no make-up tests will be given in this course. If a student has a legitimate and properly documented excuse for missing one of the tests, the missing test score will be estimated as the average of the other two test scores. More complicated scenarios, e.g., where a student misses two tests for legitimate reasons, will be treated on a case-by-case basis. In the event of a non-excused absence, a score of zero will be assigned.

Overall Raw Score Each student's overall raw score, out of 100 points, will be determined from performance on the six assignments, the quizzes, and the three tests. Assignment 0 is worth 4 points, and Assignments 1 through 5 are each worth 8 points, for a total of 44 points. The remainder 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 32 * |A| / n. Then your raw score out of 56 for the quizzes and tests is (56 - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on all three tests. Mary's raw score for the quizzes and tests is 56 out of 56. 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 32 out of 56. Example 3: Pat has a test average of 75%, and gets better than 75% on 27 out of a total of 36 quizzes. The average of Pat's top 27 quiz scores is 90%. Pat's raw score for the quizzes and tests is (56 - 24) * 0.75 + 24 * 0.9 = 45.6 out of 56, or 81.43%.

Letter Grades The nominal cutoff for getting an A in the course is 90. For a B, it is 80, and for a C, it is 60. These nominal cutoffs will not be increased; for example, a student achieving a raw score of 90 is guaranteed to get an A in the course. These cutoffs might be lowered if necessary in order to improve the grade distribution.

Feedback Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. If you wish to provide feedback anonymously, one way to do so is to turn in an extra sheet with comments whenever a quiz is being collected.

Academic Dishonesty Cheating on the assignments, quizzes, or tests will not be tolerated. If you find yourself overwhelmed by coursework or other special circumstances, do not resort to cheating. Instead, make an appointment to see the instructor to discuss your situation.

Instructor	Greg Plaxton (office hours W 4-5 and F 3-4, TAY 3.132; email: plaxton at cs)

Teaching Assistant	Chinmayi Krishnappa (office hours T 10-11 and Th 4-5, Desk 1 in ENS 31NQ; email: chinmayi at cs). Directions to ENS 31NQ: (1) take the elevator down to "LB" (lower basement); (2) exit the elevator to the right; (3) keep going down the hallway, which will curve to the right; (4) enter room 31NR, which will be on your left; (5) go through 31NR to a smaller room, which is 31NQ; (6) there are six desks marked 1 through 6.

Extended Office Hours	Each of the four office hours listed above will be extended half an hour (e.g., W 4-5:30 instead of W 4-5) if there is a test or an assignment due during the week following the office hour. Example: Suppose that an assignment is due at 10am on Wednesday, September 24. Then every office hour between 10am on Wednesday, September 17 and 10am on Wednesday, September 24 will be extended by half an hour.

Class Time	MWF 10-11

Class Location	ENS 145

Textbook	The textbook for the course is Algorithm Design by Kleinberg and Tardos (Addison-Wesley, 2006).

Course Outline	The following major topics will be covered: analysis of algorithms, graph algorithms, greedy algorithms, divide-and-conquer, dynamic programming, network flow, NP-completeness, approximation algorithms, randomized algorithms. See the schedule for a more detailed specification of the lecture plan.

Assignments	There will be six assignments. For the most part, the assignments will involve paper-and-pencil problem solving. However, some of the assignments will include a small programming component. You are allowed to discuss high-level approaches to the assignment problems with other members of the class, but you are not allowed to discuss or exchange detailed solutions.

Quizzes	Most of the lectures will include a brief quiz based on material from the previous lecture. 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 three in-class tests. The tests will be closed book and closed notes; you are only allowed to bring one page of notes (both sides may be used). The first test will be held on Monday, September 29 and will cover all of the course material up to September 26. The second test will be held on Friday, October 31 and will cover all of the course material from October 1 to October 29. The third test will be held on Friday, December 5 and will cover all of the course material from November 3 onward. Please try to arrive in class a few minutes early on the test dates; this will allow us to start the test right at the beginning of the class period.

Make-Up Tests	Please note that no make-up tests will be given in this course. If a student has a legitimate and properly documented excuse for missing one of the tests, the missing test score will be estimated as the average of the other two test scores. More complicated scenarios, e.g., where a student misses two tests for legitimate reasons, will be treated on a case-by-case basis. In the event of a non-excused absence, a score of zero will be assigned.

Overall Raw Score	Each student's overall raw score, out of 100 points, will be determined from performance on the six assignments, the quizzes, and the three tests. Assignment 0 is worth 4 points, and Assignments 1 through 5 are each worth 8 points, for a total of 44 points. The remainder 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 32 * \|A\| / n. Then your raw score out of 56 for the quizzes and tests is (56 - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on all three tests. Mary's raw score for the quizzes and tests is 56 out of 56. 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 32 out of 56. Example 3: Pat has a test average of 75%, and gets better than 75% on 27 out of a total of 36 quizzes. The average of Pat's top 27 quiz scores is 90%. Pat's raw score for the quizzes and tests is (56 - 24) * 0.75 + 24 * 0.9 = 45.6 out of 56, or 81.43%.

Letter Grades	The nominal cutoff for getting an A in the course is 90. For a B, it is 80, and for a C, it is 60. These nominal cutoffs will not be increased; for example, a student achieving a raw score of 90 is guaranteed to get an A in the course. These cutoffs might be lowered if necessary in order to improve the grade distribution.

Feedback	Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. If you wish to provide feedback anonymously, one way to do so is to turn in an extra sheet with comments whenever a quiz is being collected.

Academic Dishonesty	Cheating on the assignments, quizzes, or tests will not be tolerated. If you find yourself overwhelmed by coursework or other special circumstances, do not resort to cheating. Instead, make an appointment to see the instructor to discuss your situation.