Navigation

CMPT 307

Data Structures & Algorithms   -   Summer 2019

Announcements

  • Aug 2: I'll have 2-hour office hours on Wed, Aug 7, 11:30-13:30.
  • Aug 2: The final exam on Aug 9 will be on all topics of the course, with equal emphasis. You'll have 3 hours for an exam that will be roughly two quizzes in size. To prepare, go over all lecture slides and notes, HWs, quizzes, and the textbook. The questions on the final exam will be similar to those on the quizzes we had.

    Note that there won't be any questions on the final asking you to prove some problem NP-complete. However, you do need to know what an NP-problem is (using the concept of a "guess-and-check" algorithm, for example), and you need to be able to state a couple of examples of NP-complete problems you saw in class.

    I won't be asking you about the randomized algorithm for Min-Cut which we haven't covered in class. I may ask some basic questions on randomized algorithms (and basic probability theory that we saw in class).

  • July 30: Quiz 4 solutions are now posted.

older announcements...

  • July 25: Quiz 4 will cover Lectures 22-27 (inclusive): Max Network Flows (Min Cut), with applications. (NP-completeness will not be part of Quiz 4, but rather appear on the final exam.)
  • July 21: The solutions to HW 4 are now posted.
  • July 14: Quiz 3 solutions are now posted.
  • July 4: No classes on Wed, July 10, and Fri, July 12, as I'm away at a conference.
  • July 1: Quiz 3 will cover Dynamic Programming, lectures 16-21 (inclusive).
  • June 28: Starting July 3, our classes will move to SWH 10081 (due to construction noise near our present class room).
  • June 20: There will be no class on Wed, June 26 (as I'll be away).
  • June 16: Quiz 2 will cover the material from lectures 9-15 (inclusive), that is, Greedy Algorithms and Divide&Conquer Algorithms (recurrences).
  • June 16: The solutions to HW 2 are now posted.
  • May 24: Quiz 1 will cover the material from lectures 1-8 (inclusive), that is, stable matchings and graph algorithms (BFS, DFS, bipartiteness, topological ordering of DAGs), Dijkstra's algorithm, and priority queue (min-heap) data structures. The questions on the quiz will be similar to those on HW 1. You may be asked to describe an algorithm, do a proof of correctness, analyze the runtime, and run the algorithm on a small input example. To prepare, study the lecture notes and the textbook, and make sure you have worked on the HW problems by yourself to understand the solutions well enough to be able to solve similar questions on the quiz. The more problems you work on before the quiz, the easier it will be for you during the quiz.
  • May 23: Each Monday, 12:30-1:20 pm, will be additional office hours by TAs. The room is ASB 9808.
  • May 16: HW 1 is now available.

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 SWH 10081
Wed 15:30-16:20 SWH 10081
Fri 15:30-16:20 SWH 10081
day time room
Mon 12:30-13:20 ASB 9808 (by TAs)
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%.
Note: I will post 4 homework assignments (one before each quiz), which will not be collected and graded. The solutions to homework problems will be posted before the quiz. The quizzes will be loosely based on the homework problems, so you will benefit by solving the homework problems by yourself!

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
A--L in AQ 3181; M--T in AQ 3150; W--Z in AQ 3154 IMAGTH IMAGTH IMAGTH

 

Note: Quizzes 2, 3, and 4 will be held in Images Theatre (IMAGTH) (for everyone). Quiz 1 will have three sections: The students with the last name starting with a letter between A to L (inclusive) will write the quiz in AQ 3181; the students whose last name begins with a letter between M to T (inclusive) will write the quiz in AQ 3150; the students whose last name begins with a letter between W and Z (inclusive) will write the quiz in AQ 3154.

 

Final exam: Aug 9, 15:30-18:30, SSCC 9001

Assignments

I'll post homework assignments & solutions.

Lecture notes & Slides

I'll post my lecture notes (slides), and the reading assignment.