Spring 2013
Unique Number 53665
CS 388G
Algorithms: Techniques and Theory


 
Instructor Greg Plaxton, 471-9751, GDC 4.512, office hours M 2:30-3:30, W 3:30-4:30.
   
TA Onur Domanic, office hours TTh 10-11, GDC 1.302.
   
Class Time TTh 2-3:30
   
Class Location BUR 136
   
Required Textbook T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3rd edition, 2009.
   
Course Outline This 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.
   
Prerequisites Graduate standing and either CS 357 (or an equivalent course) or consent of instructor.
   
Recommended Exercises Six 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.
   
Quizzes Most 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.
   
Tests There will be three in-class tests, on February 14, March 28, and May 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 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 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 Score Each 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 Grades The 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+).
   
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.