CPSC 420 requires CPSC 320 as a pre-requisite. CPSC 500 is intended for graduate students who have taken at least one upper division algorithms course. We will review some of the basics of algorithm analysis, but graduate students without this background may find the pace a little quick.
We will look at problems coming from many areas of computer science to motivate our exploration of algorithm design and analysis techniques. The techniques include divide-and-conquer, dynamic programming, randomization, amortized analysis, and reduction. The types of problems we'll consider come from the following areas:
Geometry Convex Hull, Voronoi Diagrams, ...
Data Structures Universal, perfect, cuckoo hashing; Suffix trees/arrays; Splay trees; ...
Graphs Matching, planarity, ...
Strings Matching, compression, ...
On-line Page replacement, k-server, ...
Approximation Bin-packing, traveling salesman, scheduling, NP-hardness, hardness of approximation, ...
Linear Programming Network flows, duality, zero-sum games, ...
Cryptography RSA, zero-knowledge proofs, ...
|
|
We will have written assignments roughly every week. I accept no late solutions, but I will drop your lowest assignment mark from the calculation of your course grade. Each assignment will have some straightforward problems and at least one challenging problem. You shouldn't feel that you must get all the problems, but you should at least think about them. You may work together discussing problems and course material, but you should write up and hand in your own solutions. Do not write up your solutions while looking at a reference or working with another person. If you do, you risk copying someone else's work. Plagiarism (the submission of work of another person as your own) is not allowed. For futher clarification see the department's policy on Collaboration and Plagiarism. If you have any questions concerning what constitutes acceptable behaviour, ask me. If you do work with someone or use some outside source, you must acknowledge them in your write-up.
CPSC 500 students must serve as a scribe for at least one lecture pair in the course. A lecture pair is two consecutive lectures one of which is on a Wednesday. Scribing involves producing typeset notes for the lecture pair. The typeset lecture notes are due one week after the lecture pair. I will look at them and possibly suggest revisons. CPSC 500 students must also read and summerize (in at most five pages) a paper (or two) that describes an application, deeper analysis, or improvement of the technique presented in the lecture pair (or a related technique). The final version of the notes and the (at most five page) summary paper are due two weeks after the lecture pair. Please sign up to scribe for a lecture pair as soon as possible.
CPSC 420 students may serve as a scribe for at most one lecture pair, for which they will receive a 1% bonus.
Wednesday work is in-class work intended to take 15-20 minutes. It may take the form of a short quiz or small-group work on a particular problem. The goal is for me to see how you are doing with the course material and for you to feel more engaged in the class. Wednesday work is marked based on participation.
Written Assignment 2 due 30 Jan 2017 at 21:00 (9pm)
Written Assignment 3
due 15 17 Feb 2017 at 21:00 (9pm)
Written Assignment 4 due 6 Mar 2017 at 21:00 (9pm)
Written Assignment 5 due 13 Mar 2017 at 21:00 (9pm)
Written Assignment 6 due 27 Mar 2017 at 21:00 (9pm)
Written Assignment 7 due 3 Apr 2017 at 21:00 (9pm)
An asterisk (*) means the notes are the final version.
1. Jan 4+6 Convex Hull - Jarvis March (Alice Fredine*) (Elizabeth Hu*) (Laura Cang*) (Naomi Kam*) (Tyler House*)
2. Jan 9+11 Convex Hull - Graham's Scan, Lower bound (Nikhil Agarwal)
3. Jan 11+13 Convex Hull - Element Uniqueness, Linear Decision Tree Otfried Cheong's Algebraic Decision Tree Notes (Omar AlOmeir*)
4. Jan 16+18 Linear Decision Trees, Element Uniqueness (David Penco*) (Minghao Liu*)
5. Jan 18+20 Lower Bounds, Chan's Algorithm (Matthew Nyhus*) (Zipeng Liu*) (Tianri Gu*) (Laura Barton*)
6. Jan 23+25 Linear Programming Introduction (Sharon Yang*)
7. Jan 25+27 Bandwidth Allocation, Network Flow Introduction
8. Jan 30 Network Flow, Ford-Fulkerson Algorithm (Melody Wong*)
[Midterm 1] Feb 1
9. Feb 3 Proof of Ford-Fulkerson, Bipartite Matching (Michelle Findlay-Olynyk) (Gabriel Henderson*) (Yu Lei) (Nancy Chen)
10. Feb 6+8 Maximum matching, Pennant Race. (Alex Budkina*) (Xiaomeng Ju*)
11. Feb 8+10 Network Flow: Pennant Race, Open-pit Mining (Arthur Marques*) (Tingting Yu*) (Jocelyn Minns*)
[Family Day] Feb 13
12. Feb 15+17 Linear Programming Duality and Zero-Sum Games (Clement Fung) (Curtis Fox*)
[Spring Break] Feb 20+22+24
13. Feb 27 + Mar 1 Zero-Sum Games and Dynamic Programming: Longest Common Subsequence (Adrian She*) (Rodrigo Araujo*)
14. Mar 1+3 Dynamic Programming: Longest Increasing Subsequence (Enrique Rosales*) (Jackson Qiu)
15. Mar 6+8 NP-Completeness Introduction (Amin Aghaee*)
16. Mar 8+10 Clique, Vertex Cover, and 3SAT are NP-complete (Natalie So*) (Tianri Gu*)
17. Mar 13 NP-Completeness wrap-up and Approximation Algorithm Introduction (Seong-Hwan Jun*) (Weining Hu*) (Daniyar Ospanov*)
[Midterm 2] Mar 15
18. Mar 17 Approximation Algorithms: Vertex Cover and List Scheduling (Stephanie Knill*) (Stephen Kan*) (Siang Lim*) (Jennifer She*)
19. Mar 20+22 Approximation Algorithms: Triangle TSP (Yuefan Liu*) (Tian Sijia) (Ajang Bul*) (Ellie Liu)
20. Mar 22+24 Hardness of Approximation, Online Algorithms (Ben Chugg*) (Vincent Hui*) (Xin Jiang*) (Hanlin Liu*) (Sean Copeland*)
21. Mar 27+29 Online paging. (Julieta Martinez*) (Sikander Randhawa*) (Anya McGee*)
22. Mar 29+31 Randomized online paging. Universal hashing. (Peter West*) (Matthew Hounslow*) (Andrew Comminos*)
23. Apr 3+5 Rasmus Pagh's Cuckoo Hashing for Undergraduates (Yasha Pushak*) (Mason Yang*) (Alex Martinez*) (Gülipek Candan)