2016
Summer Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/S16
Lecture Time: Monday,
Wednesday, Friday 2:305: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), 55:30pm
·
TAs:
o Monday 121pm (Alireza), Location x141
o Tuesday 34pm (Alireza), Location x141
o Wednesday: 1pm2pm (Shiwen), Location DLC Table 2
o Wednesday 121pm (Alireza), Location x141
o Thursday 23pm
(Ricky), DLC Table 1
o Friday 122pm
(Ricky), DLC Table 1
Final Exam
·
Wednesday June
22nd, 122:30pm, in PHRM 1101.
·
No textbooks or electronic
devices are permitted.
·
Six pages of handwritten
notes, on doublesided 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
34: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 
NPcompleteness:
Definition of P and Reductions 
30.1,
30.2, 30.5 
8.1, 8.3 
15 
W 6/15 
NPcompleteness:
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 1112am (Alireza)
·
Tutorial B: Mon, Wed 56pm (Shiwen)
·
Tutorial C: Tue, Thu 1011am (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 
Divideandconquer 

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 
NPcompleteness 

11 
W 6/15 
Th 6/16 
NPcompleteness 
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, NPcompleteness 
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 15451.
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 KleinbergTardos 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)