CMPT 705
Design & Analysis of Algorithms - Spring 2013
Announcements
- Apr 10: Our last class is this Friday, April 12. The final exam is next Monday, April 15. The final will cover all topics that we studied in the course; it will be a 3-hour closed-book exam. The solutions to Quiz 4 are now posted.
older announcements...
- Apr 5: Quiz 4 next Wednesday will cover Network Flows, NP-completeness, and Randomized Algorithms (that is, Chapters 7, 8, and 13 of [KT]). The solutions to HW 4 are now posted.
- Mar 27: No class this Friday (Easter break). Next class is Wednesday, April 3.
- Mar 24: HW 4 is now available. Solutions to Quiz 3 are also posted.
- Mar 8: Quiz 3 next Friday will be a 50-min quiz, covering Dynamic Programming algorithms (Chap. 6 of [KT]). The solutions to HW 3 are now posted.
- Mar 4: The solutions to Quiz 2 are now posted.
- Mar 3: HW 3 is now available.
- Feb 22: Your marked Quiz 1 is available for pickup on Monday (Feb 25), from the TA in TASC 1-8208, between 2pm and 3pm.
- Feb 21: The solutions to HW 2 are now posted. The password is in your email.
- Feb 19: There is no class this Friday, Feb 22 (as I'm away at a conference). Quiz 2 (on Feb 27) will be conducted by the TA. The quiz will cover Greedy Algorithms and Divide-and-Conquer Algorithms (starting from Dijkstra's algorithm and up to FFT, inclusive); that is, Chapters 4 and 5 of [KT].
- Feb 10: HW 2 is now available.
- Feb 7: The solutions to Quiz 1 are now available (see below). The pdf file is password-protected; you should have received the password by email. Please keep the password confidential!
- Jan 29: The solutions to HW 1 are now available (see below). The pdf file is password-protected; you should have received the password by email. Please keep the password confidential!
- Jan 17: HW 1 is now available! (see below)
- Jan 16: The final exam date has been decided now. See below, under "Important dates".
- Dec 11: The first lecture is January 9.
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 and conquer algorithms and their anaysis: solving recurrences
- Dynamic programming algorithms and their analysis
- Flow algorithms and matching
- Linear programming
- Randomized algorithms
- Approximation algorithms
- NP-completeness
- Advanced topics
- Algorithm Design by J. Kleinberg and E. Tardos, 2006
- Introduction to Algorithms by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, 2001
| day | time | room |
|---|---|---|
| Wed | 15:30-16:20 | AQ 5016 |
| Fri | 14:30-16:20 | AQ 5016 |
Fri 16:30-17:20 in TASC1 8011, or email me
for an appointment.
- 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
TA: Ruiwen Chen (ruiwenc@sfu.ca)
If you have grading-related questions, please email Ruiwen Chen 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 lectures on the following dates.
| Quiz 1 | Quiz 2 | Quiz 3 | Quiz 4 |
|---|---|---|---|
| Feb 6 | Feb 27 | Mar 15 | Apr 10 |
Final exam: Apr 15, 12:00-15:00, in BLU 10011
Assignments
I'll post homework assignments & solutions.
- Homework 1 solutions
- quiz 1 solutions
- Homework 2 solutions
- quiz 2 solutions
- Homework 3 solutions
- quiz 3 solutions
- Homework 4 solutions
- quiz 4 solutions
Lecture notes
I'll post a brief outline of what I have done in class, and the reading assignment.
- 01/9: Intro; Stable matching algorithm. 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!
- 01/11: Stable matching algorithm (cont'd): correctness, man-optimal/woman-pessimal, efficient implementation (using arrays & linked lists); Min-Heaps and Priority Queues (based on min-heaps); HeapSort. Read: KT, Secs. 2.3 - 2.5. (If you want to read ahead: KT, Secs. 3.1 - 3.3).
- 01/16: Ω(n log n) lower bound for comparison-based sorting of n input numbers; Graphs (basic definitions & representations of graphs); BFS & DFS. Read: KT, Secs. 2.5, 3.1 - 3.2. (Read ahead: KT, Secs. 3.3-3.6.)
- 01/18: Graph algorithms (cont'd): BFS and DFS implementations: using queues and stacks; the run time is O(m+n); can produce BFS and DFS trees within the same O(m+n) time. 2-Colorability Algorithm. Digraphs (BFS and DFS still work); topological ordering for DAGs. Read: KT, Sec. 3.3-3.6 (Read ahead: KT, Secs. 4.4-4.6.)
- 01/23: Decomposing a digraph into strongly connected components using O(m+n) time. Read: KT, Sec. 3.5 and CLRS, Sec. 22.5; the actual algorithm is in CLRS! (Read ahead: KT, Secs. 4.4-4.6.)
- 01/25: Dijkstra's algorithm (all shortest paths from a given node s): description, correctness, & runtime analysis (when implemented using priority queues). Min Spanning Tree: two greedy algorithms (Kruskal's and Prim's); correctness proof using promising partial solutions. Read: KT, Secs. 4.4-4.5, plus these lecture notes for Kruskal's analysis. (Read ahead: KT, Secs. 4.6, 4.7.)
- 01/30: Prim's algorithm and its correctness analysis; Implementations of Kruskal's and Prim's algorithms (using UnionFind and Priority Queue, respectively). Read: KT, Secs. 4.5 & 4.6. (Read ahead: KT, Sec. 4.7, 4.8.)
- 02/1: Clustering (from Kruskal), Huffman coding. Read: KT, Secs. 4.7, 4.8. (Read ahead: KT, Secs. 5.1, 5.2, 5.5.)
- 02/8: Divide&Conquer algorithms: MergeSort and FFT. Read: KT, Secs. 5.1, 5.2, 5.6; CLRS, Chap. 30. (Read ahead: KT, Secs. 5.5, 6.1, 6.2.)
- 02/20: Dynamic programming: The Knapsack problem. (Here are the lecture notes for some of the DP problems discussed in class, for this and next lectures.) Read: KT, Secs. 6.1, 6.2, and 6.4. (Read ahead: KT, Sec. 6.8.)
- 03/1: Floyd-Warshall algorithm for All-pairs shortest paths problem & Bellman-Ford algorithm for the Shortest s-t path in a digraph with negative edge weights allowed (but no negative cycles). Read: KT, Sec. 6.8. (Read ahead: the DP lecture notes posted above.)
- 03/6: Detecting negative cycles in digraphs; Edit distance problem. Read: KT, Sec. 6.10.
- 03/8: Network flows: Ford-Fulkerson algorithm (runtime and correctness analysis); MaxFlow=MinCut; Edmonds-Karp implementation (using shortest augmenting paths). Read: KT, Secs. 7.1, 7.2; CLRS, pages 660-663.
- 03/13: Linear Programming. [guest lecture by Ramesh]
- 03/20: Applications of Ford-Fulkerson's algorithm: Perfect matchings; edge-disjoint paths. Read: KT, Secs. 7.5, 7.6. (Read ahead: 7.7-7.11.)
- 03/22: Applications of Ford-Fulkerson: Circulation with demands and lower bounds; survey design problem; image segmentation problem. NP-completeness: basic definitions. Read: KT, Secs. 7.7-7.11, 8.1-8.4. (Read ahead: 8.5-8.8.)
- 03/27: NP-completeness (sample NP-complete problems, and reductions); Search-to-Decision reduction for SAT. Read: KT, Secs. 8.1-8.4, 8.7-8.8. (Read ahead: 13.1-13.3.)
- 04/3: Randomized algorithms: MinCut, and MAX-2SAT. Read: KT, Secs. 13.2-13.4. (Read ahead: 13.9, 13.12.)
- 04/5: Pairwise Independent sample spaces (with application to MAX-2SAT); Universal hash function families; Polynomial Identity Testing (and the Schwartz-Zippel Lemma); Chernoff bounds.
- 04/12: Course review.