2016
Summer Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/S16
Lecture Time: Monday,
Wednesday, Friday 2:30-5:00pm
Lecture Room: DMP 110
Discussion Forum: Piazza (run primarily by TAs)
Staff
·
Instructor: Nick Harvey
·
TAs
o Reza Babanezhad, rezababa@cs.ubc.ca
o Prithu Banerjee, prithu@cs.ubc.ca
o Ricky Chen, tqichen@cs.ubc.ca
o Shiwen He, shiwenhe@cs.ubc.ca
o Alireza Zakeri Hosseinabadi, azakeri@cs.ubc.ca
Office Hours
·
Instructor:
o After every lecture,
in the lecture room (or my office), 5-5:30pm
·
TAs:
o Monday 12-1pm (Alireza), Location x141
o Tuesday 3-4pm (Alireza), Location x141
o Wednesday: 1pm-2pm (Shiwen), Location DLC Table 2
o Wednesday 12-1pm (Alireza), Location x141
o Thursday 2-3pm
(Ricky), DLC Table 1
o Friday 12-2pm
(Ricky), DLC Table 1
Final Exam
·
Wednesday June
22nd, 12-2:30pm, in PHRM 1101.
·
No textbooks or electronic
devices are permitted.
·
Six pages of handwritten
notes, on double-sided 8.5x11” paper are permitted.
Lectures
|
|
Date |
Topics |
Erickson |
KT |
|
1 |
M 5/9 |
Stable
matching |
Ch 0 |
1.1 |
|
2 |
W 5/11 |
Asymptotic
notation |
|
2.1, 2.2,
2.4 |
|
3 |
F 5/13 |
Graphs:
BFS, Bipartite Graphs |
Ch 18 |
3.1, 3.2,
3.4 |
|
4 |
M 5/16 |
Greedy:
Interval Scheduling, Minimizing Lateness |
Ch 7 |
4.1, 4.2 |
|
5 |
W 5/18 |
Graphs: Dijkstra, Spanning Trees |
Ch 21, 20 |
4.4, 4.5 |
|
6 |
F 5/20 |
Divide
and conquer: Recurrence Relations |
App 2 |
5.1, 5.2,
5.3 |
|
7 |
W 5/25 |
Divide
and conquer: Inversions, Multiplication |
1.3, 1.8 |
5.3, 5.5 |
|
8 |
F 5/27 |
Optional
review session |
|
|
|
M 5/30 |
Midterm
3-4:30pm in PHRM 1101 |
|
|
|
|
9 |
W 6/1 |
DP1:
Weighted Interval Scheduling, Knapsack |
6.1, 6.4 |
|
|
10 |
F 6/3 |
DP2: Edit
Distance, Cache Partitioning, Viterbi Algorithm |
5.5 |
6.6 |
|
11 |
M 6/6 |
Amortized
analysis: Reallocating arrays, Stack with MultiPop |
Ch 15 |
|
|
12 |
W 6/8 |
Randomized
algorithms: Bloom Filters, Set Similarity |
||
|
13 |
F 6/10 |
Streaming
algorithms: Heavy Hitters |
||
|
14 |
M 6/13 |
NP-completeness:
Definition of P and Reductions |
30.1,
30.2, 30.5 |
8.1, 8.3 |
|
15 |
W 6/15 |
NP-completeness:
Examples of Reductions |
30.3,
30.8, 30.9 |
8.4 |
|
16 |
F 6/17 |
Optional
review session |
Chapter numbers for Erickson’s book refer to the “All
algorithms lecture notes in one file” PDF.
Disclaimer: I do not guarantee that lecture material
matches the textbooks.
Tutorials
·
Tutorial A: Mon, Wed 11-12am (Alireza)
·
Tutorial B: Mon, Wed 5-6pm (Shiwen)
·
Tutorial C: Tue, Thu 10-11am (Prithu)
All are held in DMP 101.
Solutions will be posted on Piazza after Section C finishes.
|
|
Date |
Date Section C |
Topics |
Link |
|
1 |
W 5/11 |
Th 5/12 |
Stable
matching |
|
|
2 |
Virtual Tutorial |
Asymptotic
notation |
||
|
3 |
M 5/16 |
Tu 5/17 |
Graphs |
|
|
4 |
W 5/18 |
Th 5/19 |
Greedy
algorithms |
|
|
5 |
W 5/25 |
Th 5/26 |
Recurrences |
|
|
6 |
Virtual Tutorial |
Divide-and-conquer |
||
|
7 |
W 6/1 |
Th 6/2 |
Dynamic
programming 1 |
|
|
8 |
M 6/6 |
Tu 6/7 |
Dynamic
programming 2 |
|
|
9 |
W 6/8 |
Th 6/9 |
Amortized
Analysis |
|
|
10 |
M 6/13 |
Tu 6/14 |
NP-completeness |
|
|
11 |
W 6/15 |
Th 6/16 |
NP-completeness |
|
Assignments
All assignments are due in room x235, box 32
(labeled “CPSC 320”), by 2:15pm on the due date.
|
|
Handout |
Due |
Handback |
Topics |
Link |
TA
Grader |
|
1 |
W 5/11 |
M 5/16 |
F 5/20 |
Stable
matching, asymptotic notation |
Ricky |
|
|
2 |
M 5/16 |
F 5/20 |
F 5/27 |
Graphs,
Greedy algorithms |
Reza |
|
|
3 |
F 5/20 |
F 5/27 |
W 6/1 |
Recurrences,
Divide and conquer |
Reza |
|
|
4 |
W 6/1 |
M 6/6 |
F 6/10 |
Dynamic
programming |
Ricky |
|
|
5 |
M 6/6 |
F 6/10 |
M 6/13 |
Amortized
Analysis, Hashing |
Reza |
|
|
6 |
F 6/10 |
F 6/17 |
Streaming
Algs, NP-completeness |
Shiwen |
Late
assignment policy: Due to the extremely tight schedule
of the summer term, no allowances are made for late assignments. Please contact
the TA grader directly about any issues with handing in the assignment.
Handouts
· Guide to Greedy Algorithms, by Roughgarden, Sharp and Wexler.
·
Amortized
Analysis: a Summary, by Patrice Belleville.
· Hashing and Bloom Filters, by Michael Mitzenmacher. Lecture notes for Harvard CS 124.
· Document Similarity, by Michael Mitzenmacher. Lecture notes for Harvard CS 124.
·
Streaming Algorithms,
by Anupam Gupta and Danny Sleator.
Lecture notes for CMU 15-451.
Resources
Textbooks:
·
Required: “Algorithms”
by Jeff Erickson. Exclusively available as a free
PDF.
·
Optional: “Algorithm
Design” by Jon Kleinberg and Eva Tardos.
·
Optional:
“Introduction to Algorithms” by Cormen, Leiserson, Rivest and Stein.
Available online from UBC
libraries.
·
Optional: “Mathematics for Computer
Science” by Eric Lehman, Tom Leighton and Albert Meyer. For now, a free
PDF.
This has great background material on proofs, induction, graphs, etc.
Slides: Kevin Wayne at Princeton has excellent slides to accompany
the Kleinberg-Tardos textbook.
Syllabus
Grading
Scheme:
·
25% assignments, 25% midterm
exam, 50% final exam
·
Must submit at least 4
assignments.
·
Must get at least 50% on
weighted average of exams.
Past offerings of this course
·
2015 Summer Term (Harvey)
·
2014 Summer Term
(Schroeder)
·
2014 Winter Term 2 (Wolfman)
·
2014 Winter Term 1
(Belleville)
·
2013 Winter Term 2
(Belleville)
·
2012 Winter Term 2 (Meyer)
·
2009 Winter Term 2 (Wolfman)
·
2009 Winter Term 1 (Evans)