[UW Logo]

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

David R. Cheriton School of Computer Science

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

General Information


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

Time and Place: T Th, 10:00-11:20, E2 1732


General Office Hours: (To be announced. Starting Monday September 9; changes for specific weeks will be posted on Piazza.)


CS 466

CS 666


Announcements will be posted on Piazza.


Books: There is no required textbook for this course. The following references will be placed on reserve in the DC library (for 3 hour loan). Other web resources: Further reading:


Instructions for Assignments: Your written solutions will be judged not only for correctness but also for the quality of your presentation and explanations. In questions that involve designing an algorithm, (i) describe the main idea first, (ii) give details at a level mimicking the style of the lectures, the model solutions, or the textbook, (iii) give a correctness proof/argument if it is not immediately obvious, and (iv) include an analysis (of the running time, error probability, approximation factor, etc.).

Collaboration policy: The work you hand in must be your own. The value of the assignment is in doing it yourself (as you must do on tests and exams). Acknowledge any sources (human or non-human) 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 and you must acknowledge the discussion. If you use an electronic source, again, read it, then close it, then compose your solution and acknowledge your source. Write your solutions in your own words, from your own head. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.

Submission: Assignments will be submitted as pdf files (each question as a separate pdf). Type your assignments or write legibly. We are using Crowdmark to submit assignments this term. Before the submission deadline (usually the weekend before the deadline), we will send a submission link to your uwaterloo email and make an announcement on piazza. If you didn't get the link or have any question about the submission, you can contact Hong Zhou (h76zhou@uwaterloo.ca). If you need any help for submitting via Crowdmark, you can find instructions here.

Late Policy: Assignments are due at 5 PM on Tuesdays. To give you some flexibility we will allow up to 2 late submissions A "late submission" means handing in an assignment on Thursday at 5 PM.

Mark Appeals: All mark appeals (for assignments and midterm) must be made within two weeks of the date of the return. Your appeal should be submitted to the TA who marked the question in writing. Only if the problem is still unresolved should you then bring the case to the instructor's attention.

#DueMarked by
1 pdf tex Tues. Sept. 17, 5 PM
2 pdf tex Tues. Sept. 24, 5 PM
3 pdf tex Tues. Oct. 1, 5 PM
4 pdf tex Tues. Oct. 8, 5 PM
5 pdf tex fig Tues. Oct. 29, 5 PM
6 pdf tex Tues. Nov. 5, 5 PM
7 pdf tex Tues. Nov. 12, 5 PM
8 pdf tex Tues. Nov. 19, 5 PM
9 pdf tex Tues. Nov. 26, 5 PM

Midterm and Exam


Lecture notes will be posted after the lectures. References are mostly from the course books (see the abbreviations above).

L01 Th Sep 05 notes Introduction. The Travelling Salesman Problem (TSP) as a motivating example. Review: [CLRS chapters 2, 3, 34]. TSP approximation: [CLRS section 35.2].
L02 T Sep 10 notes Binomial heaps See the older (2nd) edition of CLRS, ch. 19, or wikipedia.
L03 Th Sep 12 notes Amortized Analysis and Lazy Binomial 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.]
L04 T Sep 17 notes Splay Trees Weiss, mentioned above. Or see, Goodrich and Tamassia, Data Structures and Algorithms in Java.
L05 Th Sep 19 notes Union Find CLRS, Ch. 21 does the true inverse Ackermann bound.
L06 T Sep 24 notes Randomized Algorithms - Intro Jeff Erickson's on-line notes1 notes2 are good. Or see CLRS Appendix C and/or Chapter 5.
L07 Th Sep 26 notes Randomized Primality Testing. RP and ZPP [CLRS 31.8] for primality testing. [MR section 1] for complexity classes. These notes are good.
L08 T Oct 1 notes Verifying Polynomial Identities. [MR sections 7.1, 7.2, 7.3] or see these notes
L09 Th Oct 3 notes 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.
L10 T Oct 8 notes 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
L11 Th Oct 10 notes Randomized graph algorithms [MR Sections 1.1, 10.2, 10.3] Another source for MST is the lecture notes of Avrim Blum and Daniel Slater here, (Lecture 8). The version of the MST algorithm I presented is from Timothy Chan's notes. It uses a sample of 2n edges, and gets expected number of light edges m/2. Other presentations (including the original) reverse these: the sample has expected size m/2 and the expected number of light edges is 2n.
L12 T Oct 22 notes Lovasz Local Lemma [MR Sections 5.1, 5.2, 5.5] Another source is the lecture notes of Tim Roughgarden here.
L13 Th Oct 24 notes Intro to Approximation Algorithms. Vertex Cover and Set Cover [CLRS, intro to chapter 35]. [V, chapter 1]. Greedy Cover: [CLRS, sections 35.1 and 35.3]. [V, section 2.1 has a much shorter proof].
L14 T Oct 29 notes Approximation via Linear Program rounding the 2-approximation for unweighted vertex cover can be found in [CLRS, section 35.1]. [V Chapters 13-15] cover way more than we did.
L15 Th Oct 31 notes Max SAT [V, sections 16.1 - 16.3]
L16 T Nov 5 notes Approximation algorithms for geometric packing problems [H, section 9.3.3, or see the original paper]
L17 Th Nov 7 notes Polynomial Time Approximation Schemes: Bin Packing. [V, chapter 9] [H, section 9.5.1], or see these lecture notes
L18 T Nov 12 notes Fully Polynomial Time Approximation Schemes: Knapsack [V, sections 8.1 and 8.2], [H, section 9.3.1]
L19 Th Nov 14 notes Hardness of Approxmation This material is covered in both the reference books, though in more detail than we did: [V, chapter 29], [H, chapter 10].
L20 T Nov 19 notes Fixed Parameter Tractable Algorithms good notes
L21 Th Nov 21 notes Online Algorithms: Paging [BE], [H, chapter 13]
L22 T Nov 26 notes Online Algorithms: k-server problem
L23 Th Nov 28 notes Fixed Parameter Tractable Algorithms continued good notes

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.

Intellectual Property: Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:

Course materials and the intellectual property contained therein, are used to enhance a student's educational experience. However, sharing this intellectual property without the intellectual property owner's permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository). Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.

Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).

Note for Students with Disabilities: The AccessAbility office, located in Needles Hall Room 1401, 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 AccessAbility Services at the beginning of each academic term.