CS 466/666, Fall 2006

Advanced Algorithms

Classes: MWF 10:30 - 11:20 AM, MC 4063

Instructor: Anna Lubiw, DC2334, alubiw "at" uwaterloo.ca, office hour: Wednesday 11:30 - 12:30, or by appointment.

Teaching Assistants:
David Pal, DC 3549 B, dpal "at" cs.uwaterloo.ca, office hours: Thursday 11:30 AM - 12:30 PM
Hubert Chan, DC 3543, hy3chan "at" cs.uwaterloo.ca, office hours: Tuesday 2:00 PM - 3:00 PM

Announcements

• Dec. 12. Assignment 4 is available outside my office. Note that question 4 won't count for grad students since you didn't get the corrected version in time.
• Dec. 11. Final Exam. In Question 5(a), please replace the word "weight" by the word "value".
• Dec. 8. Final Exam. In Question 2, scale H to 1. And in part (a) the bins have size 1.
• Dec. 7. Assignment 3 is available outside my office, DC 2334.
• Dec. 6. Solutions to assigments 3 and 4 are available outside my office, DC 2334.
• Dec. 2. Problem Session for Monday. Here are some problems for Monday, with the people who will present them. You may send me email to reserve a problem, and I will update the list to reflect that. I may also add more problems. I have on record that the following people wish to present: Rusli C., Steve H., James M., Alex P., Jiawei Q., Peter R., Margaryta T., Dmytro T., Kevin Y. There are a couple of you registered for the course who are not on this list -- send me email if you intend to present something. There will be a strict 5 minute limit on presentations!
  1. Alex P. No deterministic paging algorithm is better than k-competitive.
  2. James, Kevin. [you may both present this, or either one of you may switch to another problem] The local greedy algorithm for the k-server problem is not c-competitive for any c.
  3. Jiawei Q. Show that if there is a polynomial time algorithm for TSP with approximation factor c for some constant c, then P=NP.
  4. Anton Z.The Least Frequently Used (LFU) paging strategy is to evict from the cache the page that has been accessed the fewest times since it was put into the cache. Show that LFU is not c-competitive for any c.
  5. Show that an optimum TSP tour for points in the plane with Euclidean distances never crosses itself.
  6. Peter R. Give an efficient greedy algorithm to find a min vertex cover in a tree.
  7. Rusli C. Assignment 4, question 2(d)
  8. Steve H.. In Assignment 4 you looked at Steiner triangulations. The idea of adding extra "Steiner" points also applies to the minimum spanning tree problem in the plane (with Euclidean distances). Give an example to show that the minimum Steiner spanning tree can have total length less than the minimum spanning tree.
  9. For the same problem as above, argue that the minimum Steiner spanning tree has at most n-2 Steiner points (where n is the number of input points given). Hint: it's a tree -- are the leaves input points or Steiner points?
  10. Dmytro. When we store elements in an unsorted array, insertions take constant time. One issue is what to do when the array fills up. One solution is to make a new array twice the size and copy the data over. The cost of creating the new array can be amortized against the cost of filling up the old one. Give a formal potential method analysis to show this.
  11. It is NP-complete to decide whether a planar graph has a 3-colouring, where every vertex is assigned one of 3 colours and no edge has both endpoints the same colour. The 4-colour theorem states that any planar graph can be 4-coloured (and there is a polynomial time algorithm to accomplish this). Consider the optimization problem: given a planar graph, find the minimum k such that the graph can be k-coloured. From the 4-colour theorem we know k <= 4. Give a polynomial time approximation algorithm that colours any planar graph within 1 colour of the optimum.
  12. Assignment 4, question 4 (the corrected version).
• Nov. 29. Please revise assignment 4, question 4 to ask about the weighted min 3-cluster problem: Given a graph G = (V,E) with weights on the edges, partition V into 3 sets A, B, C to minimize the sum of the weights of the edges where both endpoints lie in the same set. (The complementary edges cross from one set to a different set.) BONUS marks to anyone who solves the problem as originally stated. My apologies to those who lost time working on this.
• Nov. 28. Here is information about the take home final exam .
• Oct. 27, later in the day. The links work now, and the list of papers is complete.
• Oct. 27. Information about the project is here. The links to the ACM Digital Library do not work right now. I'm consulting with the library about this. Meanwhile, there is complete citation information, so you can look up the paper yourself through Trellis. I will add papers on the topic of approximation algorithms to the suggested list soon.
• Sept. 15. Assignment 1 is available, see below.
• Here is some more information about strong NP-completeness for question 1(ii):

  Encoding TSP in unary just means that the weights on the edges are written in unary. For example, 8 would not be written in binary as 1000 but in unary as 11111111. For a number n, the binary encoding has size log n, but the unary encoding has size n. "Polynomial time in the input size" then means a lot more time than before!

  As an example, it is trivial to test primality in polynomial time if the number is encoded in unary: To see if n is prime, try dividing by 2, 3, 4, ..., n/2. It is quite hard (only done a couple of years ago) to test primality in polynomial time if the number is encoded in binary.

  For this question you are asked to show that EVEN if the number are encoded in unary, a polynomial time solution to TSP would imply P=NP. You must show that some know NP-complete problem reduces in polynomial time to the decision version of unary-encoded TSP.

  Hope that helps. You can find a bit more info here or in a good algorithms text, or in Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness.

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

Schedule

• Mon. Sept. 11. Introduction. Expected background. The TSP problem as a motivating example
• Wed. Sept. 13. Continutation of TSP. Intro to amortized analysis. [CLRS, p. 406, 407-408].
• Fri. Sept. 15. Problem Session

• Mon. Sept. 18. Mergeable heaps. [CLRS, chapter 19, "Binomial heaps"]
• Wed. Sept. 20. The potential method of amortized analysis. [CLRS, section 17.3]. Lazy binomial heaps. [this isn'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"].
• Fri. Sept. 22. Fibonacci heaps (just an overview). [CLRS] Review of binary search trees. [any data structures/algorithms book]

• Mon. Sept. 25. Splay trees. [Weiss, mentioned above. Or see, Goodrich and Tamassia, Data Structures and Algorithms in Java, or the slides here].
• Wed. Sept. 27. continued.
• Fri. Sept. 29. Problem session. Intro to Union Find problem.

• Mon. Oct. 2. Union Find. [CLRS, Ch. 21. Or see Goodrich and Tamassia's slides.]
• Wed. Oct. 4. Geometric data structures -- range trees. [Goodrich and Tamassia, Algorithm Design, section 12.1. Some lecture slides can be found here.]
• Fri. Oct 6. Persistent data structures.

• Mon. Oct. 9. Thanksgiving - no class.
• Wed. Oct. 11. continuation of persistent data structures.
• Fri. Oct. 13. Problem Session.

• Mon. Oct. 16. Intro to Randomized Algorithms. For probability review see [CLRS, Chapter 5]. A good survey on randomized algorithms is: [K] Karp, "An introduction to randomized algorithms", Discrete Applied Mathematics 34: 165-201, 1991. [pdf]
• Wed. Oct. 18. Primality testing - the Miller-Rabin algorithm. [K]. Monte Carlo versus Las Vegas algorithms. [MR, section 1.2] or [K]. Randomized complexity classes. [MR, section 1.5] For information on polynomial time (non-randomized) algorithm for primality, see this notice from the AMS.
• Fri. Oct. 20. Fingerprinting used in string pattern matching.

• Mon. Oct. 23. Freivald's technique for verifying polynomial identities. [K]
• Wed. Oct. 25. Randomized incremental algorithm for linear programming. See sections 4.3 and 4.4 of: de Berg, van Kreveld, Overmars, Schwarzkopf, Computational Geometry Algorithms and Applications, 2nd edition, Springer, 2000.
• Fri. Oct. 27. Problem Session.

• Mon. Oct. 30. Continuation of linear programming. Intro to Approximation Algorithms. [CLRS, intro to chapter 35]. [V, chapter 1]
• Wed. Nov. 1. Vertex Cover and Set Cover -- greedy algorithm. [CLRS, sections 35.1 and 35.3]. [V, section 2.1 has a much shorter proof].
• Fri. Nov. 3. Set cover via primal-dual scheme. [V, chapter 15]

• Mon. Nov. 6. continued
• Wed. Nov. 8. Randomization in approximation algorithms - max cut and max SAT. [V, section 16.1 and 16.3]
• Fri. Nov. 10. Problem Session.

• Mon. Nov. 13. Approximation algorithms for geometric packing problems. [H, section 9.3.3]
• Wed. Nov. 15. Polynomial Time Approximation Schemes: Bin Packing. [V, chapter 9] [H, section 9.5.1]
• Fri. Nov. 17. Fully Polynomial Time Approximation Schemes: Knapsack. [V, sections 8.1 and 8.2], [H, section 9.3.1]

• Mon. Nov. 20. 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.
• Wed. Nov. 22. Hardness of approximation: reductions.
• Fri. Nov. 24. Problem Session

• Mon. Nov. 27. Hardness of approximation: new characterization of NP and consequences for approximation. (see references above.)
• Wed. Nov. 29. On-line algorithms. [H, chapter 13], or see this survey.
• Fri. Dec. 1. Problem Session

• Mon. Dec. 4. Problem Session.

Final Exam