Fall 2011Unique Number 52475CS 357Design and Analysis of Algorithms

InstructorGreg Plaxton (office hours M 11-12 and W 2-3, ACE 3.420; email: plaxton at cs) Teaching AssistantChinmayi Krishnappa (office hours T 3-4 and Th 10-11, PAI 5.33, Desk 3; email: chinmayi at cs). Class TimeMWF 10-11 Class LocationART 1.110 TextbookThe textbook for the course is Algorithm Designby Kleinberg and Tardos (Addison-Wesley, 2006).Course OutlineThe 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 lecture plan. PrerequisitesThe following courses, with a grade of at least C- in each: Computer Science 310 or 310H, 336 or 336H, 337 or 337H, and Mathematics 408D or 408M. AssignmentsThere will be six assignments. Each assignment will have a first part, labeled "Programming and Problem Solving", and a second part, labeled "Textbook Exercises". The first part may be done with a partner, and you are strongly encouraged to do so. The second part consists of exercises for each student to solve and turn in separately. QuizzesMany 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. TestsThere 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 26and will cover all of the course material up to September 23. The second test will be held onFriday, October 28and will cover all of the course material from September 28 to October 26. The third test will be held onFriday, December 2and will cover all of the course material from October 31 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 TestsPlease 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 ScoreEach 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 1 is worth 4 points, and Assignments 2 through 6 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 GradesThe mapping from overall raw scores to letter grades will depend somewhat on the overall performance of the class. The nominal A/A- cutoff is 90; A-/B+ is 85; B+/B is 80; B/B- is 75; B-/C+ is 70; C+/C is 65; C/C- is 60. These nominal cutoffs will not be increased; for example, a student achieving a raw score of 90 is guaranteed to receive an A in the course. However, these cutoffs might be lowered if necessary in order to improve the grade distribution. In Fall 2010, a total of 44 students (39 undergrads and 5 graduate students) took the course for a letter grade, and the average GPA was 2.9. In Fall 2009, the average GPA was also 2.9. FeedbackThroughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. Academic HonestySee the following departmental document.