Course description
The course continues with the study of concepts and problem-solving techniques useful for the design and analysis of efficient algorithms. The students are assumed to have taken cmpt 307 or its equivalent. After a review of the basic algorithm-design topics (BFS, DFS, greedy, dynamic programming, divide-and-conquer, network flow), we will study some or all of these more advanced topics:
- Linear programming
- Randomized algorithms
- Approximation algorithms
- NP-completeness
- Streaming algorithms
- Advanced data structures
- Other topics
Texts
- Required: Algorithm Design by J. Kleinberg and E. Tardos, 2006
- Reference: Introduction to Algorithms by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, 2001
- Reference: Computers and Intractability: A Guide to the Theory of NP-Completeness by M. Garey and D.S. Johnson, 1979
Teaching staff
| Instructor: | Tom Shermer email: shermer at sfu-dot-ca office: TASC 1, 8021 office hours: MF13:30-14:20 or by appointment |
|
| T.A.: | Alireza Ensan email: aensan at sfu-dot-ca office: ASB 9808 (in CSIL lab) office hours: R9:30-11:30 |
Marking
| 4 in-class quizzes | 15% each | |
| final exam | 40% |
Allowances may be made for documented emergent medical (and other) circumstances.
Do not expect that preset notions of the equivalences of percentage scores with letter marks will hold. I do not have set ideas such as: "90% and above is an 'A'." The cutoff line for "A" could be 96% or it could be 80%, or it could be anywhere else. Setting the difficulty of quiz and examination questions in a 400-level course is not as easy as in a 100-level course, so the difficulty (hence scores) may vary.
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!
Important dates
| 5 Oct | quiz 1 | |
| 26 Oct | quiz 2 | |
| 16 Nov | quiz 3 | |
| 7 Dec | quiz 4 | |
| 10 Dec | final exam (15:30 - 18:30, room TBA) |
Lecture Topics
Here I will try to post a list of topics covered in each lecture. (In previous semesters I have been unable to maintain such a list, so I'm not guaranteeing this one will continue to be correctly populated.)
- 9 Sept
- Welcome lecture. My philosophies, policies, and advice.
- 11 Sept
- Problems mainly on three domains: strings, graphs, and geometry.
Machine models: TM, RAM, log-cost RAM, Real RAM. - 14 Sept
- Finished Machine Models.
Abstraction and modelling: important, but not covered in this course.
Basic graph/digraph terminology; adjacency matrices and incidence lists. - 16 Sept
- Properties of non-tree edges in BFS/DFS.
Bipartite detection - 18 Sept
- Bipartite detection analyzed
Topological sort - 21 Sept
- Greedy algorithms
Minimum Spanning Tree correctness lemma - 23 Sept
- Kruskal's algorithm
Union-find (disjoint set union)
Ackermann's function and its inverse - 25 Sept
- Prim's algorithm, and its correctness
- 28 Sept
- Prim's algorithm (cont'd)
Heaps vs. Fibonacci or relaxed heaps - 30 Sept
- Dijkstra's algorithm
Defined Weighted Interval Scheduling - 2 Oct
- Memoization and Dynamic Programming (Read K&T Chapter 6)
Weighted Interval Scheduling - 5 Oct
- RNA Secondary Structure
Sequence Alignment with space reduction - 8 Oct
- Quiz 1