Spring 2017

Unique Numbers 52060, 52065

CS 331Algorithms and Complexity

InstructorGreg Plaxton; office hours M 2:30-3:30 and W 1:30-2:30 in GDC 4.512; plaxton at cs dot utexas dot edu. Teaching AssistantChi-Kit (George) Lam; office hours T 10:30-12 in GDC 1.302 (Desk 4); geocklam at cs dot utexas dot edu. Lecture Time and LocationTTh 2-3:30 in GDC 2.216 Discussion Section Times and LocationsF 10-11 in CBA 4.348 (52060)

F 12-1 in GDC 4.302 (52065)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. Online ForumPiazza will be used for online discussion of the course material. If you have a question for the instructional staff that might be of interest to someone else, you should generally post it to Piazza instead of sending an email. With regard to problems that the class is actively working on, students are allowed to post questions and responses related to problem clarification, but should not post partial or complete solutions. AssignmentsThere will be six assignments. You may find that some of the problems on the assignments are challenging to solve. You are encouraged to attend the office hours and discussion sections, where we will provide hints for solving the problems. You can also post questions on Piazza. You can discuss high-level solution approaches with other students in the class, but you are not allowed to share detailed solutions, and you are required to write up your solutions on your own. If you obtain a key idea from another source (other than the instructor, TA, lecture notes, or course textbook), you are expected to cite that source in your solution, and to write up the solution in your own words. All assignments are due at the beginning of class on the due date. Assignments may be turned in late without penalty, subject to the following slip day policy. If a student turns in an assignment xdays late, the student is charged ⌈x⌉ slip days. A student is allowed to use at most 15 slip days over the course of the semester, and at most 5 slip days for any one assignment. Assignments that are more than 5 days late will not be accepted. If a student uses up all of their slip days, late assignments will no longer be accepted from that student.TestsThere will be three in-class tests. The tests will be closed book and closed notes; except that one page of notes will be allowed (both sides may be used). The first test will be held on Thursday, February 16and will cover all of the course material up to February 14. The second test will be held onThursday, March 30and will cover all of the course material from February 21 to March 28. The third test will be held onThursday, May 4and will cover all of the course material from April 4 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 ScoreThe six assignments are equally weighted, and together account for one-third of a student's overall raw score. The three tests are equally weighted and account for the remaining two-thirds. Letter GradesThe overall raw scores will be mapped to letter grades at the end of the semester. The numerical cutoffs associated with this mapping will depend to some degree on the overall performance of the class. Estimates of these cutoffs will be provided as the semester progresses. DisabilitiesStudents with disabilities may request appropriate academic accommodations from the Division of Diversity and Community Engagement, Services for Students with Disabilities, 512-471-6259. FeedbackThroughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.