CPSC 320: Intermediate Algorithm Analysis and Design

2015 Summer Term 1

General Information

Course Website: http://www.cs.ubc.ca/~nickhar/S15

Lecture Time: Monday, Wednesday, Friday 2:30-5:00pm

Lecture Room: DMP 110

Discussion Forum: Piazza (run primarily by TAs)

Staff

· Instructor: Prof. Nicholas Harvey

· TAs

o Michael Wathen, mwathen@cs.ubc.ca

o Alireza Shafaei, shafaei@cs.ubc.ca

Office Hours

· Instructor:

o After every lecture, in the lecture room (or my office), 5-5:30pm

· TAs:

o Mondays 12am-1pm (Alireza), DLC Table 1

o Tuesdays 11am-12:30pm (Sam), in ICCS x141

o Wednesdays, 12:30-2pm (Shiwen), DLC Table 2

o Thursdays 11am-12:30pm (Sikander), DLC Table 3

o Fridays 10-11am (Sikander), DLC Table 3

Exam

o Wednesday June 24th, 12:00pm in ANGU 098

o No calculators or textbooks.

o 6 pages of double-sided 8.5x11”, hand-written notes are allowed.

Lectures

	Date	Topics	Textbook	Notes
1	M 5/11	Stable matching	1.1	Ch 1
2	W 5/13	Asymptotic notation	2.1, 2.2, 2.4	Ch 2
3	F 5/15	Graphs, Dijkstra’s Algorithm	3.1, 3.2, 4.4	Ch 3
4	W 5/20	Greedy algorithms: Spanning Trees	4.5	Ch 3
5	F 5/22	Greedy algorithms: Interval Scheduling	4.1	Ch 3
6	M 5/25	Divide and conquer: Recurrence relations	5.1, 5.2, 5.3	Ch 5
7	W 5/27	Divide and conquer: Inversions, Multiplication	5.3, 5.5	Ch 5
8	F 5/29	Review
	M 6/1	Midterm: Forest Sciences Center 1005, 3-4:30pm
9	W 6/3	Dynamic programming: Weighted Interval Scheduling	6.1, 6.2	Ch 7
10	F 6/5	Dynamic programming: Segmented Least Squares, Knapsack	6.3, 6.4	Ch 7
11	M 6/8	Amortized analysis: Reallocating arrays, Stack with MultiPop	n/a	Ch 4
12	W 6/10	Randomized algorithm: Skip Lists	n/a	MIT
13	F 6/12	NP-completeness: Definition of P and Reductions	8.1-8.4	Ch 8
14	M 6/15	NP-completeness	8.1-8.4	Ch 8
15	W 6/17	Review

Disclaimer: I do not guarantee that lecture material matches other resources (text/notes).

Tutorials

· Tutorial A: Mon, Wed 11-12am (Alireza)

· Tutorial B: Mon, Wed 5-6pm (Shiwen)

· Tutorial C: Tue, Thu 10-11am (Sam)

Solutions will be posted on Piazza after Section C finishes.

Assignments

All assignments are due in room x235, box 2, by 2:15pm on the due date.

	Handout	Due date	Handback	Topics	Link
1	T 5/14	W 5/20	M 5/25	Stable matching, asymptotic notation	Questions
2	W 5/20	M 5/25	F 5/29	Graphs, Greedy algorithms	Questions
3	M 5/25	F 5/29	F 6/5	Recurrences, Divide and conquer	Questions
4	W 6/3	M 6/8	M 6/15	Dynamic programming	Questions
5	M 6/8	F 6/12	W 6/17	Amortized Analysis	Questions
6	F 6/12	W 6/17	M 6/22	Randomized algs, NP-completeness	Questions