CMPT 307
Data Structures & Algorithms - Summer 2019
Announcements
- May 6: Please note that there is no class on Wed, May 8. See you on Friday!
older announcements...
Course description
The course introduces concepts and problem-solving techniques useful for the design and analysis of efficient algorithms.
- Topics
- Texts
- Lectures
- Office hours
- Marking scheme
- Motivating example: the stable matching problem
- Greedy (graph) algorithms, BFS, DFS, Dijkstra's, Kruskal's, and Prim's
- Simple data structures: priority queues (with heaps) and union-find
- Divide & Conquer algorithms (solving recurrences)
- Dynamic Programming algorithms
- Network Flow algorithms and matching
- Randomized algorithms
- NP-completeness
- Advanced topics
- Algorithm Design by J. Kleinberg and E. Tardos, 2006 [main]
- Introduction to Algorithms by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, 2001 [optional]
| day | time | room |
|---|---|---|
| Mon | 15:30-16:20 | AQ 3181 |
| Wed | 15:30-16:20 | AQ 3181 |
| Fri | 15:30-16:20 | AQ 3181 |
| day | time | room |
|---|---|---|
| Wed | 12:30-13:20 | TASC1 8011 |
| Fri | 12:30-13:20 | TASC1 8011 |
- four 50-min in-class quizzes @ 15% each,
- final exam @ 40%.
Teaching staff
Instructor: Valentine Kabanets (kabanets@cs.sfu.ca), Office: TASC1 8011
TAs: Ermin Hodzic (ehodzic@sfu.ca), Amirhossein Kazeminia (akazemin@sfu.ca), Shohre Masoumi (smasoumi@sfu.ca)
If you have grading-related questions, please email the TAs and ask for an appointment. If you still have questions after meeting with the TA, then come and see me.
Important dates
The 50-minute quizzes will be given during our regular lecture times on the following dates.
| Quiz 1 | Quiz 2 | Quiz 3 | Quiz 4 |
|---|---|---|---|
| June 3 | June 24 | July 8 | July 29 |
Final exam: Aug 9, 15:30-18:30, room TBA
Assignments
I'll post homework assignments & solutions.
Lecture notes & Slides
I'll post my lecture notes (slides), and the reading assignment.
- 05/6: Lecture 1: Intro; Stable matching algorithm: correctness analysis. Read: KT, Sec. 1.1 (for the algorithm); Secs. 2.1 and 2.2 (for some background). Also check out this Nobel Prize note about the stable matching algorithm!
- 05/10: Lecture 2: Stable matching algorithm (cont'd): man-optimal matching; woman-pessimal matching; efficient implementation (using arrays & linked lists). Read: KT, Secs. 2.3 & 2.4. (If you want to read ahead: KT, Secs. 2.5 & 3.1-3.3).
- 05/13: Lecture 3: Graphs (basic definitions & representations of graphs); BFS; runtime O(m+n); graph reachability Reach(s,t). Read: KT, Secs. 3.1-3.4. (Read ahead: KT, Secs. 3.5-3.6.)