CS 466/666: Design and Analysis of Algorithms, Fall 2012

David R. Cheriton School of Computer Science

General Information

• Course Description: Advanced design and analysis of algorithms. Topics include: amortized analysis, randomized algorithms, lower bounds, approximation algorithms, and on-line algorithms.
• Objectives: To learn more about algorithms and how to analyze them.
• Calendar Description - Official course description from academic calendar.
• Handbook Description - Longer course description from Computer Science Undergraduate Handbook.

Organization

Instructor: Anna Lubiw, DC2334, x34449, alubiw "at" cs.uwaterloo.ca

Time and Place: T Th 1:00 - 2:20, PHY 313

TAs:

• Luke Schaeffer, lrschaeffer AT gmail.com
• Alexandre Laplante alaplante AT uwaterloo.ca

General Office Hours (changes for specific weeks will be posted on Piazza): (Note that Luke and I were reversed on Sept. 17. The following times are in effect for the rest of term.)

• Anna Lubiw, Monday 1:00 - 2:00, DC 2334
• Luke Schaeffer, Monday 3:00 - 4:00, DC 3523
• Alexandre Laplante, Friday 11:00 - 12:00, DC2531

Credit:

CS 466

• 11 (small) written assignments (no programming), 45%
  
• in-class quiz questions, 10% (can be replaced by exam mark)
  
• final exam, 45%

CS 666

• 11 (small) written assignments (no programming), 30%
  
• in-class quiz questions, 10% (can be replaced by exam mark)
  
• final exam, 30%
  
• project, 30%. The project description is here.

Announcements

• Dec. 4. Assignment 10 is marked and available outside my office, DC 2334. Old assignments are also there. All solutions are below.
• Nov. 28. Office hours before the exam are as follows:
  • Tuesday Dec. 4, 1:30 - 2:30 PM. Anna DC 2334
  • Thursday Dec. 6, 1:30 - 2:30 PM. Anna DC 2334
  • Thursday Dec. 6, 3 - 4 PM. Luke DC 3523
  • Friday Dec. 7, 11 - 12 AM. Alex DC 2531
• Nov. 20. Assignment 10 and solution 8 are available below.
• Nov. 20. There will be a quiz in each of the last 4 lectures.
• Nov. 16. There is info about the exam below, including a practice exam.
• Nov. 16. correction to Assignment 9, part (f). Show that the bound from (e) is asymptotically tight for Rule 2, i.e. find a general example where T2/OPT approaches 2. (Corrected in the assignment below.)
• Nov. 14. Assignment 9 is available below.
• Nov. 13. Solution 7 is available below. Also solution 6.
• Nov. 6. Assignment 8 is available below.
• Oct. 30. Solution 5 is available below.
• Oct. 30. Assignment 7 is available below.
• Oct. 24. Assignment 6 is available below.
• Oct. 17. The description of the grad project is available just above (under Credit for CS 666).
• Oct. 16. Assignment 5 is available below. Solutions 3 and 4 also.
• Oct. 2. Assignment 4 is available below.
• Sept. 25. Assignment 3 and Solution 1 are available below.
• Sept. 18. Luke and Anna have swapped office hours.
• Sep. 18. Assignment 2 is available below. Due date is Tuesday September 25.
• Sept. 16. Class is cancelled on Thursday Sept. 20.
• Sep. 13. Correction to A1Q2: the vacuum cleaner must return to its initial position. The correction has been added to the question.
• Sep. 12. Assignment 1 is available below. Due date is Tuesday September 18.
• Sep. 4. Sign up for Piazza here.
• Sep. 3. First lecture is Tuesday September 11. Welcome to CS 466/666!

Resources

• [CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.), MIT Press, 2009 (QA76.6 .C662 2009). (on-reserve in the DC library) You can also use the 2nd edition, which is available electronically through the library.
• [MR] Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68) [MR]
• [MU] M. Mitzenmacher and E. Upfal, Probability and Computing, Cambridge University Press, 2005 (QA274 .M574 2005)
  
• [V] Vazirani, Approximation Algorithms, Springer-Verlag, 2001 (QA76.9.A43 V39)
• [H] D.S. Hochbaum, ed., Approximation Algorithms For NP-Hard Problems, PWS, 1997 (T57.7.A68)
• [BE] Borodin and El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998 (QA76.9.A43 B67)

• David Eppstein's Data Structures course (with wikipedia course notes)
• Erik Demaine's Design and Analysis of Algorithms course
• Jeff Erickson's algorithms notes (with many exercises)
• Erik Demaine's Advanced Data Structures course (with video lectures)

Assignments

Exam

Lectures

• 1. Tues. Sept. 11. Introduction. Expected background. The Travelling Salesman Problem (TSP) problem as a motivating example. Remind yourself of big Oh notation, worst case asymptotic analysis of algorithms, and NP-completeness [CLRS chapters 2, 3, 34]. Basic approximation algorithms for the TSP are in [CLRS section 35.2.] The advanced MST results I mentioned are on wikipedia. TSP pictures are from William Cook's TSP web page.
• 2. Thurs. Sept. 13. Binomial heaps [See the older (2nd) edition of CLRS, ch. 19, or wikipedia]. Intro to amortized analysis [CLRS, ch. 17 (not 17.4), or wikipedia ].

• 3. Tues. Sept. 18. Lazy binomial heaps and overview of Fibonacci heaps [lazy binomial heaps are not in CLRS, but can be found in Weiss, "Data Structures and Algorithm Analysis"--this book comes in Java and C++ flavours, many editions--look for the section called "Lazy merging for binomial queues." Fibonacci heaps are in CLRS, ch. 19, or see wikipedia. Dexter Kozen's lecture notes from Cornell cover lazy Binomial heaps and Fibonacci heaps.]
• Thurs. Sept. 20. No class.

• 4. Tues. Sept. 25. Splay trees. [Weiss, mentioned above. Or see, Goodrich and Tamassia, Data Structures and Algorithms in Java, or the slides here].
• 5. Thurs. Sept. 27. Last of splay trees (dynamic optimality conjecture). Union Find. [CLRS, Ch. 21 does the true inverse Ackermann bound. A better analysis by Waterloo Profs. Biedl and Chan can be found here. In class we did a weaker and easier analysis as can be found on Goodrich and Tamassia's slides.]

• 6. Tues. Oct. 1. Last of Union-Find analysis. Geometric Data Structures: Range Trees [Goodrich and Tamassia, Algorithm Design, section 12.1. Or see the slides by Subhash Suri here.]
• Thurs. Oct. 3. Class cancelled due to illness.

• 7. Tues. Oct. 9. Point Location and Persistent Search Trees. [the wikipedia page has a decent intro.] Introduction to Randomized Algorithms [Read CLRS Appendix C and/or Chapter 5.]
• 8. Thurs. Oct. 11. Lecture given by Prof. Jeffrey Shallit. Analysis of Quickselect. [CLRS 9.2]. Primality Testing. [CLRS 31.8, but you can skip the number theory proofs. Or see MR section 14.6 (the Miller-Rabin algorithm presented in class is their "Algorithm Primality3")]

• 9. Tues. Oct. 16. Las Vegas vs. Monte Carlo Algorithms [MR section 1.2] Complexity classes for randomized algorithms [MR section 1.5.2]. Fingerprinting to test equality of strings [MR section 7.4]
• 10. Thurs. Oct. 18. Fingerprinting for pattern matching and verifying polynomial identities. [MR sections 7.1, 7.2, 7.6]

• 11. Tues. Oct. 23. Randomized incremental algorithm for linear programming in low dimension. [MR section 9.10.1, or see Chapter 4 of the book Computational Geometry by de Berg, van Kreveld, Overmars and Schwarzkopf, Springer 2000].
• 12. Thurs. Oct. 25. Randomized algorithms for Satisfiability [MR Section 6.1 has brief coverage. More can be found in Computational Complexity by Papadimitriou, p. 245. Another source is the lecture notes of Pavan Aduri here]

• 13. Tues. Oct. 30. Intro to Approximation Algorithms. [CLRS, intro to chapter 35]. [V, chapter 1]. Vertex cover and set cover -- greedy algorithm. [CLRS, sections 35.1 and 35.3]. [V, section 2.1 has a much shorter proof].
• 14. Thurs. Nov. 1. Set cover approximation via primal dual scheme. [V chapter 15], the 2-approximation for vertex cover can be found in [CLRS, section 35.1].

• 15. Tues. Nov. 6. Max cut and Max SAT -- randomized approximation algorithms. [V, section 16.1 and 16.3]
• 16. Thurs. Nov. 8. Approximation algorithms for geometric packing problems. [H, section 9.3.3, or see the original paper]

• 17. Tues. Nov. 13. Polynomial Time Approximation Schemes: Bin Packing. [V, chapter 9] [H, section 9.5.1], or see these lecture notes
• 18. Thurs. Nov. 15. Fully Polynomial Time Approximation Schemes: Knapsack/ [V, sections 8.1 and 8.2], [H, section 9.3.1]

• 19. Tues. Nov. 20. Hardness of Approximation: Reductions. This material is covered in both the reference books, though in more detail than we did: [V, chapter 29], [H, chapter 10].
• 20. Thurs. Nov. 22. Hardness of approximation: new characterization of NP and consequences for approximation. (see references above.)

• 21. Tues. Nov. 27. On-Line Algorithms. Introduction, robot navigation, auction bids.
• 22. Thurs. Nov. 29. Paging and the k-server problem. [BE], [H, chapter 13], or see this survey.

University Policies (University required text)

Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility.
[Check www.uwaterloo.ca/academicintegrity for more information. ]

Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.

Note for students with disabilities: The Office for Persons with Disabilities (OPD), located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the OPD at the beginning of each academic term.