[UW Logo]

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

David R. Cheriton School of Computer Science


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


General Information


Organization

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

Time and Place: M W, 8:30-09:50, MC 2035

TAs:

General Office Hours: (starting Monday September 17; changes for specific weeks will be posted on Piazza)

Credit:

CS 466

CS 666


Announcements

Announcements will be posted on Piazza.

Resources

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:


Assignments

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 (if you pick up your assignment/exam late, your appeal period does not lengthen). 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 Tues. Sept. 25, 5 PM
2 pdf Tues. Oct. 2, 5 PM
3 pdf Tues. Oct. 16, 5 PM
4 pdf Tues. Oct. 30, 5 PM
5 pdf Tues. Nov. 6, 5 PM
6 pdf Tues. Nov. 13, 5 PM
7 pdf Tues. Nov. 20, 5 PM
8 pdf Thurs. Nov. 29, 5 PM (lates on Mon. Dec. 3


Midterm and Exam


Lectures

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

L01 M Sep 10 notes Introduction. The Travelling Salesman Problem (TSP) as a motivating example. Review: [CLRS chapters 2, 3, 34]. TSP approximation: [CLRS section 35.2].
L02 W Sep 12 notes Binomial heaps See the older (2nd) edition of CLRS, ch. 19, or wikipedia.
L03 M Sep 17 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 W Sep 19 notes Splay Trees Weiss, mentioned above. Or see, Goodrich and Tamassia, Data Structures and Algorithms in Java.
L05 W Sep 26 notes Union Find CLRS, Ch. 21 does the true inverse Ackermann bound.
L06 M Oct 1 notes Geometric Data Structures Goodrich and Tamassia, Algorithm Design, section 12.1. Or see the slides by Subhash Suri here. For point location the wikipedia page has a decent intro.
L07 W Oct 3 notes Randomized Algorithms - Intro Read CLRS Appendix C and/or Chapter 5. Jeff Erickson's on-line notes are good.
L08 F Oct 12 notes Randomized Primality Testing. RP and ZPP [CLRS 31.8] for primality testing. [MR section 1] for complexity classes. notes are good.
L09 M Oct 15 notes Verifying Polynomial Identities. [MR sections 7.1, 7.2, 7.6]
L10 W Oct 17 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.
L11 M Oct 22 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
L12 W Oct 24 notes Randomized linear time algorithm for Min Spanning Tree [MR Section 10.3] Another source is the lecture notes of Avrim Blum and Daniel Slater here, (Lecture 8). The version of the 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.
L13 M Oct 29 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 W Oct 31 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 M Nov 5 notes Max SAT [V, sections 16.1 - 16.3]
L16 W Nov 7 notes Approximation algorithms for geometric packing problems [H, section 9.3.3, or see the original paper]
L17 M Nov 10 notes Polynomial Time Approximation Schemes: Bin Packing. [V, chapter 9] [H, section 9.5.1], or see these lecture notes
L18 W Nov 12 notes Fully Polynomial Time Approximation Schemes: Knapsack [V, sections 8.1 and 8.2], [H, section 9.3.1]
L19 M Nov 19 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 W Nov 21 notes Online Algorithms: Paging [BE], [H, chapter 13]
L21 M Nov 26 notes Online Algorithms: k-server problem
L22 W Nov 28 notes Fixed Parameter Tractable Algorithms
L23 M Dec 3 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.