David R. Cheriton School of Computer Science
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:
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.
# | Due | Marked 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 |
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 |
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.
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.