CS 466/666: Design and Analysis of Algorithms, Spring 2013

link to S12 web page

David R. Cheriton School of Computer Science

Contents: General Info, Organization, Announcements, Resources, Assignments, Lectures, University Policies

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: Ian Munro, DC2334, x34433, imunro "at" uwaterloo.ca

Time and Place: T Th 10:00 - 11:20, PHY 235

TAs:

Stephen Kiazyk (DC 2569) s_kiazyk "at" hotmail.com
Vinayak Pathak (DC 3132) vpathak "at" uwaterloo.ca

General Office Hours (changes for specific weeks will be posted on Piazza):

Ian Munro, Tuesday and Thursday immediately after class i.e. 11:20-12:20, DC 2343
Stephen Kiazyk, alternate weeks, Friday (11:00-12:00), DC 2569
Vinayak Pathak alternate weeks, Friday (11:00-12:00), DC 3132
Before the final exam: All three of us are busy with conferences etc in the 2 weeks before the exam. Ian Munro (DC2343) will be available most of Wednesday August 14, Stephen Kiazyk (DC2569) on Friday from and Vinay Pathak (DC3132) on Thursday from 16:30 to 18:30.

Credit:

CS 466

(small) Written assignments (small, no programming, 8 or 9 assignments), 25%
Midterm exam, Thursday June 27, in class, 25%
Final exam, 50%

CS 666

as for CS 466, marks *.75
project, 25%. The project description is here.

Announcements

Also Piazza which we will use instead of a newsgroup.

Note the office hours before the final as given above; also that assignments can be picked up from the CS receptionist.

May 7 Nothing Yet.

Books: The main text for this course is Cormen, Leiserson, Rivest, and Stein (see below). It covers most of the necessary material though by no means all; it is also used as a text for CS 341 and so many students will have it already. The following references are in the DC library.

[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)

Other web resources:

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

The work you hand in must be your own. Acknowledge any sources you have used. You may discuss the assignment questions verbally with others, but you should come away from these discussions with no written or electronic records. Write your solutions in your own words, from your own head.

Please include a cover page for your assignment with your name and student number. The TAs will use the cover page to write your marks. Hand in your assignment to the assignment boxes on the 3rd floor of MC near the bridge to DC.

Assignments will be due on Mondays at noon, unless an explicit exception is made such as after a long weekend.

Assignments will be available here on the web page and will be handed back in class.

Questions regarding the marking of any assignment must be dealt with within 10 days of the marked assignment being available. See the TA who marked it.

We hope to hand assignments back in the Thursday class after they are handed in. As TA office hours are the next day, the plan is for the TA to have unclaimed assignments with him during that time.

Assignment 10 and all uncollected assignments will be available from the CS receptionist (Helen Jardine in DC 2326) from 1 pm Aug. 12 until the Friday August 16. Assignments will be sorted by the last digit of student ID.

Assignment 1 Due Tuesday, May 21, 2013, Marked by Stephen

Assignment 2 Due Monday, May 27, 2013, Marked by Stephen

Assignment 3 Due Monday, June 3, 2013, Marked by Vinayak

Assignment 4 Due Monday, June 10, 2013, Marked by Vinayak

Assignment 5 Due Monday, June 17, 2013, Marked by Stephen

Assignment 6 Due Monday, June 24, 2013, Marked by Vinayak

No Assignment 6 for Monday July 1, 2013

Assignment 7 Due Monday, July 9, 2013, Marked by Stephen

Assignment 8 Due Monday, July 15, 2013, Marked by Vinayak

Assignment 9 Due Monday, July 22, 2013, Marked by Stephen

Assignment 10 Due Monday, July 29, 2013, Marked by Vinayak

Exam

The time and location of the final exam will be announced. See the official schedule. The exam covers the whole course. Here is a sample exam --- note that it was a take-home exam, so it assumes a lot of thinking time. Your exam will have questions that can be answered more quickly.

Lectures

Tuesday May 7: Introduction, brief review of CS 341 topics.
Thursday May 9 - Tuesday May 28: Optimal and self-organizing linear and binary search notes, Sleator and Tarjan "Linear Search paper" and Sleator and Tarjan "Splay Tree paper"
Thursday May 30: A review of NP-completeness, linear time algorithm for 2-SAT. [CLRS] Chapter 34 , notes on NP-Completeness, and notes on 3-SAT and 2-SAT
Tuesday June 4: Various ways of dealing with NP-completeness -- Konig's theorem that says that in a bipartite graph, the size of a maximum matching is equal to the size of a minimum vertex cover, and (hence) polynomial time algorithms for finding minimum vertex cover (and hence maximum independent set) in bipartite graphs starting from maximum matching; Feedback vertex set is NP-complete in bipartite graphs (simple reduction from FVS in general graphs, simply subdivide every edge).
Thursday June 6: Exact exponential time algorithms: Held and Karp algorithm for finding the optimum TSP tour in O(2^n n^2) time using dynamic programming; a simple O(7^{n/3} n^c) algorithm for 3-SAT; introduction to parameterized complexity, Algorithms to determine whether a given graph on n vertices has a vertex cover of size at most k -- starting from an O(n^{k+2}) algorithm to O(1.618^k n^d) algorithms.
Tuesday June 11: More on parameterized complexity: O(3^kn^c) algorithm for 3-hitting set. Towards O(5^k n^c) algorithm for undirected feedback vertex set using iterated compression.
Thursday June 13: O(5^k n^2) algorithm for undirected feedback vertex set; Kernelization including O(k^2) kernel for k-vertex cover
Tuesday June 18 to Tuesday June 25: Approximation Algorithms for NP-Hard Problems: [CLRS] Chapter 35, notes on approximation for vertex cover and TSP
July 2 - 9: More on dealing with NP-Completeness, including randomized approaches and PTAS: [CLRS] Chapters 34 and 35.
July 11 - 25: Comparison based problems, lower bounds and probabilistic methods for them: [CLRS] Chapters 5 and 9, notes on comparison based problems, Floyd-Rivest median paper, and Matula's report on finding 2nd largest

Lectures from Fall 2012, the schedule and examples will differ substantially from this

Here is a list of the topics covered in each lecture, with references, mostly from the course books (see the abbreviations above).

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.

Discipline: A student is expected to know what constitutes academic integrity to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 – Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 - Student Discipline. For typical penalties check Guidelines for the Assessment of Penalties.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals.

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.