CS 466/666, Fall 2007

Advanced Algorithms

Classes: MWF 11:30 AM - 12:20 PM, MC 4042

Instructor: Anna Lubiw, DC2334, alubiw "at" uwaterloo.ca, office hour: Wednesday 2:30 - 3:30, or by appointment (send email)

Teaching Assistants:

Mina Razaghpour, DC 2581, mrazaghp "at" cs.uwaterloo.ca, office hours: Thursday 12-1 PM

Margareta (Rita) Ackerman, DC 2515, mackerma "at" uwaterloo.ca, office hours: Wednesday 1-2 PM

Announcements

• Dec. 21. Undergraduates: Please check that your marks have been recorded correctly. You are sorted alphabetically by last name, but only identified by the last 4 digits of your ID number. The final computation was 45% assignments, 10% presentation, 45% final exam.
• Dec. 9. Solutions to assignment 3 available below
• Dec. 8. Typo in exam, question 1: 2_i should be 2^i.
• Nov. 26. Two clarifications for Assignment 4:
  • For 2(c), you will need to normalize so that H=1.
  • For 4, replace "weight" by "value". In more detail: For the knapsack problem you are given items i=1..n with values v_i and sizes s_i. You are given a capacity B. The optimization problem is to find the max sum of values of a set of items whose sizes sum to at most B. The question should refer to "a solution of VALUE at least OPT - k".
• Nov. 1. Details about the Final Exam are below.
• Oct. 31. There were a few typos in Assignment 3:
  Question 2(b). Count should return 2^r - 1. (What's written is 2^{r-1} by mistake.) For part (ii) prove that the expected value returned by Count is c.
  Question 3. In Line (1) of the pseudocode, instead of "return C_{i-1}" it should say, "set C_i = C_{i-1}"
  Sorry if this has caused you any trouble.
• Oct. 23. Assignment 3 is now complete. The first 2 questions are unchanged. One more question, worth 20 marks, has been added.
• Oct. 23. The CS 666 project is now available.
• Sept. 26. For Assignment 1, question 3(iii), the sqrt(n) bound is tricky, and I don't wish to penalize anyone for not getting it. The value of this question is to learn something about pairing heaps, and to get some experience manipulating potential functions. We will allocate 5 of the 10 marks for the question to the O(1) bounds, and 5 marks to the sqrt(n) bound. We will count the assignment as out of 35, which makes those 5 marks a bonus.
• Sept. 26. A clarification on Assignment 1, Question 2. You are asked to prove a lower bound on the problem, i.e. a lower bound on any possible implementation.
• Sept. 17. The first problem session will be Monday September 24. See below for the list of problems and how to sign up for one.
• Sept. 17. I made a little correction to the note at the end of Assignment 1, Problem 3. It does not affect the question though.
• Sept. 14. Assignment 1 is available.

Credit

Policies

The work you hand in must be your own. Plagarism is the act of presenting someone else's words or ideas as your own. In particular, here are some common forms of plagarism:

• looking at someone else's completed assignment before completing yours
• asking for solutions/hints to assignment questions on the internet
• copying sentences verbatim from a research paper to include in your project

• you discuss an assignment question with someone; you leave the discussion with no written notes and write up your own solution and acknowledge your discussion partner
• you think about a problem and get stuck and search in the library or the internet for similar topics; you write up your own solution without any reference materials or notes in front of you and you acknowledge the sources you looked at
• you find relevant material for your project in a research paper; you make point-form notes and from them your write up that section of your project, acknowledging that you are summarizing work from that paper. If you take a whole sentence verbatim you put it in quotes.

Resources

Assignments

Problem Sessions

Problem Session 1, Monday September 24.

Problem Session 2, Monday October 1.

Problem Session 3, Monday October 15.

Problem Session 4, Monday October 29.

Problem Session 5, Monday November 12.

Problem Session 6, Monday November 26.

Problem Session 7, Friday November 30.

Problem Session 8, Monday December 3.

Schedule

• 1. Mon. Sept. 10. Introduction. Expected background. The TSP problem as a motivating example.
• 2. Wed. Sept. 12. Binomial heaps [CLRS, ch. 19]
• 3. Fri. Sept. 14. Intro to amortized analysis [CLRS, ch. 17 (not 17.4)]

• 4. Mon. Sept. 17. Lazy binomial heaps and overview of Fibonacci heaps [lazy binomial heaps aren't 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. 20]
• 5. Wed. Sept. 19. Splay trees. [Weiss, mentioned above. Or see, Goodrich and Tamassia, Data Structures and Algorithms in Java, or the slides here].
• 6. Fri. Sept. 21. continuation of splay trees.

• Mon. Sept. 24. Problem Session 1
• 7. Wed. Sept. 26. Union Find. [CLRS, Ch. 21. Or see Goodrich and Tamassia's slides. ]
• 8. Fri. Sept. 28. continued.

• Mon. Oct. 1. Problem Session 2
• 9. Wed. Oct. 3. Geometric data structures -- range trees. [Goodrich and Tamassia, Algorithm Design, section 12.1. Some lecture slides can be found here.]
• 10. Fri. Oct. 5. continued. [For a good explanation of the "fractional cascading" idea see de Berg et al., Computational Geometry:Theory and Applications, Springer, 2000]

• Mon. Oct. 8. Thanksgiving holiday.
• 11. Wed. Oct. 10. Introduction to Randomized Algorithms. Quickselect. For probability review see [CLRS, Chapter 5]. A version of Quickselect is in [CLRS, section 9.2]. A good survey on randomized algorithms is: [K] Karp, "An introduction to randomized algorithms", Discrete Applied Mathematics 34: 165-201, 1991. [pdf]
• 12. Fri. Oct. 12. Primality testing [CLRS section 31.8, or MR section 14.6 (the Miller-Rabin algorithm I presented is their "Algorithm Primality3")]. Las Vegas versus Monte Carlo algorithms [MR section 1.2].

• Mon. Oct. 15. Problem Session 3
• 13. Wed. Oct. 17. Complexity classes of randomized algorithms [MR, section 1.5.2]. Fingerprinting to test equality of strings. [K, section 5; MR, section 7.4]
• 14. Fri. Oct. 19. Pattern matching - the Rabin-Karp algorithm. [K, secton 5.1; MR, section 7.6]. Fingerprinting for polynomial identities [K, section 4; MR section 7.1, 7.2].

• 15. Mon. Oct. 22. Perfect matchings in graphs [K, section 4.2; MR section 7.3]. Comparing fingerprinting techniques for verifying equality of strings [MR, section 7.5]. Intro to linear programming.
• 16. Wed. Oct. 24. A randomized algorithm for linear programming in low dimension. [K, section 7.2; MR section 9.10.1].
• 17. Fri. Oct. 26.

• Mon. Oct. 29. Problem Session 4
• 18. Wed. Oct. 31. 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].
• 19. Fri. Nov. 2. Set cover via primal-dual scheme. [V, chapter 15]

• 20. Mon. Nov. 5. continuation from Friday. A local improvement algorithm for max cut.
• 21. Wed. Nov. 7. Randomization in approximation algorithms - max cut and max SAT. [V, section 16.1 and 16.3]
• 22. Fri. Nov. 9. Approximation algorithms for geometric packing problems. [H, section 9.3.3]

• Mon. Nov. 12. Problem Session 5
• 23. Wed. Nov. 14. Polynomial Time Approximation Schemes: Bin Packing. [V, chapter 9] [H, section 9.5.1]
• 24. Fri. Nov. 16. Fully Polynomial Time Approximation Schemes: Knapsack. [V, sections 8.1 and 8.2], [H, section 9.3.1]

• 25. Mon. Nov. 19. Hardness of approximation: intro, reduction from Max3SAT to Independent Set. This material is covered in both the reference books, though in more detail than we did: [V, chapter 29], [H, chapter 10]. You might find this survey by Babai more readable.
• 26. Wed. Nov. 21. continued. Reduction from Max3SAT to Vertex Cover.
• 27. Fri. Nov. 23. Hardness of approximation: new characterization of NP and con sequences for approximation. (see references above.)

• Mon. Nov. 26. Problem Session 6
• 28. Wed. Nov. 28. On-Line Algorithms. Robot navigation.
• Fri. Nov. 30. (half problem session, half lecture) Problem Session 7
  29. On-Line Algorithms. Paging and the k-server problem. [BE], [H, chapter 13], or see this survey.

• Mon. Dec. 6. Problem Session 8

Project for CS 666

For more suggestions, see the list of papers for last term's course offering here.

Final Exam