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   Shiwen He, shiwenhe@cs.ubc.ca

o   Alireza Shafaei, shafaei@cs.ubc.ca

o   Sam Creed, samcreed@cs.ubc.ca

o   Sikander Randhawa, sikander_94@alumni.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.

 

 

Date
Sections A&B

Date

Section C

Topics

Link

1

W 5/13

Th 5/14

Stable matching

Questions

2

W 5/20

Th 5/21

Asymptotic notation

Questions

3

M 5/25

Tu 5/26

Greedy algorithms

Questions

4

W 5/27

Th 5/28

Recurrences

Questions

5

W 6/3

Th 6/4

Divide-and-conquer

Questions

6

Virtual Tutorial

Dynamic programming 1

Questions

7

M 6/8

Tu 6/9

Dynamic programming 2

Questions

8

W 6/10

Th 6/11

Amortized analysis

Questions

9

Virtual Tutorial

Skip Lists

Questions

10

M 6/15

Tu 6/16

NP-completeness

Questions

11

W 6/17

Th 6/18

NP-completeness

Questions

 

 

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

 

Resources

Textbook: Kleinberg, Tardos. Algorithm Design

Slides: Princeton’s Kevin Wayne has made slides to accompany 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

·         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)