Spring 2013Unique Number 53665CS 388GAlgorithms: Techniques and Theory

InstructorGreg Plaxton, 471-9751, GDC 4.512, office hours M 2:30-3:30, W 3:30-4:30. TAOnur Domanic, office hours TTh 10-11, GDC 1.302. Class TimeTTh 2-3:30 Class LocationBUR 136 Required TextbookT. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3rd edition, 2009.Course OutlineThis is a graduate course in the design and analysis of algorithms. Some of the course material revisits topics that are covered in a typical undergraduate algorithms course such as CS 357; in such cases, we emphasize more advanced aspects. See the schedule for a more detailed lecture plan. PrerequisitesGraduate standing and either CS 357 (or an equivalent course) or consent of instructor. Recommended ExercisesSix sets of recommended exercises will be handed out during the semester. The tentative dates for these handouts are indicated on the class schedule. Sample solutions will also be handed out. It is suggested that students attempt to solve the recommended exercises (either alone or in a group) before reading the sample solutions. QuizzesMost of the lectures will begin with a short quiz based on material covered in the previous lecture. Each quiz will be graded out of 20. Attendance is worth 50%, i.e., anyone who turns in a quiz will get a score of at least 10 out of 20. 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. TestsThere will be three in-class tests, on February 14,March 28, andMay 2(all test dates are Thursdays). The tests are closed book/notes, except that you are allowed to bring one page of notes (both sides may be used).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 based on the other test scores. More complicated scenarios, e.g., where a student misses multiple 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 will be determined from the quiz and test scores as follows. First, the test average is computed (as a percentage), call it X. Then, each individual quiz score lower than X is replaced by X. Let Y denote the resulting quiz average. Then the overall raw score is 0.4 X + 0.6 Y. Letter GradesThe mapping from overall raw scores to letter grades is not based on a fixed formula; it will depend to some extent on the overall performance of the class. Typically about half of the students who complete the class receive a grade an A (or A-), and about half receive a B (or B-, B+). FeedbackThroughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. Academic HonestySee the following departmental document.