Spring 2014Unique Numbers 53735, 53740, 53745, 53750CS 331Algorithms and Complexity

InstructorGreg Plaxton (office hours M 3:30-5, GDC 4.512; plaxton at cs dot utexas dot edu). NOTE: Most questions should be submitted to Piazza rather than by sending an email to the instructor. AssistantsReece Davies (Th 2-3:30; TA Station 3 in GDC 1.302; rdavies717 at gmail dot com); Avani Gupta (office hours Tu 12:30-2; TA Station 2 in GDC 1.302; avanigupta at utexas dot edu); George Lam (W 1:30-3; GDC TA Station 4 in GDC 1.302; geocklam at cs dot utexas dot edu); Chunzhi Su (Tu 2-3:30; GDC TA Station 2 in GDC 1.302; suchunzhi at gmail dot com). NOTE: Most questions should be submitted to Piazza rather than by sending an email to a member of the instructional staff. Lecture Time and LocationMW 11-12:30 in GDC 2.216 Discussion Section Times and LocationsF 10-11 in RLM 7.124 (53735)

F 11-12 in GDC 5.302 (53740)

F 12-1 in GSB 2.122 (53745)

F 1-2 in CLA 1.104 (53750)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, undecidability, approximation algorithms, randomized algorithms. See the schedule for a more detailed lecture plan. PrerequisitesThe following coursework with a grade of at least C- in each course: CS 311 or 311H, 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. AssignmentsThere will be six assignments. Most (and quite possibly all) of the assignments will include a small programming task. The last five assignments will also include paper-and-pencil exercises to be turned in for grading. All of the assignments will include additional recommended exercises (not to be turned in) that should help you to prepare for the tests. The graded portions of the assignment are to be done on an individual basis. 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 Wednesday, February 12and will cover all of the course material up to February 10. The second test will be held onWednesday, March 26and will cover all of the course material from February 17 to March 24. The third test will be held onWednesday, April 30and will cover all of the course material from March 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 and three tests. Assignment 1 is worth 3 points, and Assignments 2 through 6 are each worth 5 points, for a total of 28 points. The tests are worth 24 points each, for a total of 72 points. 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; C-/D is 55. 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. FeedbackThroughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. Academic HonestySee the following departmental document.