Fall 2012
Unique Number 53078
CS 378
Algorithms and Complexity

Instructor Greg Plaxton (office hours M 10-11, W 11-12, and F 3-4, ACE 3.420; email: plaxton at cs)

Teaching Assistants Venkata Koppula (office hours T 9-10, Th 11-12, PAI 5.33, Desk 6; kvenkata at cs) and Muhibur Rasheed (office hours M 2:30-3:30, W 4:30-5:30, PAI 5.33, Desk 6; muhibur at cs)

Class Time MWF 9-10

Class Location WAG 101

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, undecidability, approximation algorithms, randomized algorithms. See the schedule for a more detailed lecture plan.

Prerequisites The following coursework with a grade of at least C- in each course: CS 313K or 313H, 314 or 314H, 429 or 429H; M 408C or 408N; SSC 321 or M 362K; and a pre-req or co-req of M 340L or SSC 329C.

Assignments There 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.

Quizzes Many of the lectures will include a brief quiz based on material from the previous lecture. The quizzes are open book/notes. Electronic devices may be used during the quizzes, but only for the following two purposes: (1) to access an electronic version of the class textbook; (2) to access an electronic version of your personal class 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, October 1 and will cover all of the course material up to September 28. The second test will be held on Friday, November 2 and will cover all of the course material from October 3 to October 31. The third test will be held on Friday, December 7 and will cover all of the course material from November 5 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 three tests, and the quizzes. Assignment 1 is worth 4 points, and Assignments 2 through 6 are each worth 8 points, for a total of 44 points. The tests are worth 8 points each, for a total of 24 points. The quizzes are equally weighted and worth a total of 32 points. However, any individual quiz score that is lower than your test average will be replaced by your test average. For example, if your test average is 78 percent and you score 6 out of 10 on a particular quiz, then your score for that quiz will be treated as 7.8 out of 10. Consequently, your test scores can determine as much as 24 + 32 = 56 percent of your overall raw score.

Letter Grades The 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.

Feedback Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.

Academic Honesty See the following departmental document.

Instructor	Greg Plaxton (office hours M 10-11, W 11-12, and F 3-4, ACE 3.420; email: plaxton at cs)

Teaching Assistants	Venkata Koppula (office hours T 9-10, Th 11-12, PAI 5.33, Desk 6; kvenkata at cs) and Muhibur Rasheed (office hours M 2:30-3:30, W 4:30-5:30, PAI 5.33, Desk 6; muhibur at cs)

Class Time	MWF 9-10

Class Location	WAG 101

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, undecidability, approximation algorithms, randomized algorithms. See the schedule for a more detailed lecture plan.

Prerequisites	The following coursework with a grade of at least C- in each course: CS 313K or 313H, 314 or 314H, 429 or 429H; M 408C or 408N; SSC 321 or M 362K; and a pre-req or co-req of M 340L or SSC 329C.

Assignments	There 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.

Quizzes	Many of the lectures will include a brief quiz based on material from the previous lecture. The quizzes are open book/notes. Electronic devices may be used during the quizzes, but only for the following two purposes: (1) to access an electronic version of the class textbook; (2) to access an electronic version of your personal class 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, October 1 and will cover all of the course material up to September 28. The second test will be held on Friday, November 2 and will cover all of the course material from October 3 to October 31. The third test will be held on Friday, December 7 and will cover all of the course material from November 5 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 three tests, and the quizzes. Assignment 1 is worth 4 points, and Assignments 2 through 6 are each worth 8 points, for a total of 44 points. The tests are worth 8 points each, for a total of 24 points. The quizzes are equally weighted and worth a total of 32 points. However, any individual quiz score that is lower than your test average will be replaced by your test average. For example, if your test average is 78 percent and you score 6 out of 10 on a particular quiz, then your score for that quiz will be treated as 7.8 out of 10. Consequently, your test scores can determine as much as 24 + 32 = 56 percent of your overall raw score.

Letter Grades	The 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.

Feedback	Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.

Academic Honesty	See the following departmental document.