Course Description
The development of provably-correct algorithms to solve problems and their analyses. Topics include basic algorithm design techniques such as greedy, divide-and-conquer, and dynamic programming, and network flows. Intractability and NP-completeness.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 12:15pm–1:05pm; Wednesday, 11:15am–12:05pm; Thursday, 1:15pm–2:05pm
All lectures are held in Mulroney Hall, room 3022.
Textbook
J. Kleinberg and É. Tardos, Algorithm Design. Pearson Addison-Wesley, 2005.
The textbook is available for sale at the campus bookstore. Course notes will also be provided for each lecture.
Marking Scheme
- Four assignments (12.5% each, total 50%)
- Midterm examination (25%)
- Final examination (25%)
You must write the final examination in order to pass the course, even if the weighted sum of your assignment and midterm examination grades is at least 50%.
News
- Apr. 5: The final exam will be written on Apr. 21. See the review document and the Exams section below for details. A practice final exam is also available.
- Mar. 31: Lecture slides for the twelfth week have been posted.
- Mar. 24: Lecture slides for the eleventh week have been posted.
- Mar. 20: The fourth assignment has been posted. It is due by Apr. 3 at 1:15pm.
- Mar. 17: Lecture slides for the tenth week have been posted.
- Mar. 10: Lecture slides for the ninth week have been posted.
- Mar. 3: Lecture slides for the eighth week have been posted.
- Feb. 27: The third assignment has been posted. It is due by Mar. 16 at 1:15pm.
- Feb. 17: Lecture slides for the seventh week have been posted.
- Feb. 3: Lecture slides for the fifth week have been posted.
- Feb. 2: The midterm will be written next week during the Feb. 9 lecture. See the review document and the Exams section below for more details. A practice midterm is also available.
- Jan. 30: The second assignment has been posted. It is due by Feb. 16 at 1:15pm.
- Jan. 27: Lecture slides for the fourth week have been posted.
- Jan. 20: Lecture slides for the third week have been posted.
- Jan. 16: Due to the delayed opening of the university, the lecture today is cancelled.
- Jan. 13: Lecture slides for the second week have been posted.
- Jan. 9: The first assignment has been posted. It is due by Jan. 26 at 1:15pm.
- Jan. 6: Lecture slides for the first week have been posted.
- Jan. 4: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Notes | Readings |
| 1 | Introduction: stable matching, representative problems | Kleinberg & Tardos, 1.1–1.2 |
| 2 | Algorithm analysis | Kleinberg & Tardos, 2.1–2.2, 2.4 |
| 3 | Graphs | Kleinberg & Tardos, 3.1–3.2, 3.4–3.6 |
| 4 | Greedy algorithms: coin changing, scheduling, partitioning | Kleinberg & Tardos, 4.1–4.2 |
| 5 | Greedy algorithms (cont’d): Dijkstra, MSTs (Prim, Kruskal, Borůvka) | Kleinberg & Tardos, 4.4–4.6 |
| 6 | Mid-course review, midterm examination | — |
| 7 | Divide and conquer: mergesort, quicksort, median/selection | Kleinberg & Tardos, 5.1–5.2, 5.4 |
| — | Winter study break | — |
| 8 | Divide and conquer (cont’d): master theorem, integer and matrix multiplication | Kleinberg & Tardos, 5.5 |
| 9 | Dynamic programming: scheduling, least squares, knapsack | Kleinberg & Tardos, 6.1–6.5 |
| 10 | Network flow: bipartite matching, disjoint paths, other applications | Kleinberg & Tardos, 7.1–7.2, 7.5–7.10 |
| 11 | Intractability: polynomial-time reductions | Kleinberg & Tardos, 8.1–8.2, 8.5–8.8 |
| 12 | Intractability (cont’d): P vs. NP, NP-completeness | Kleinberg & Tardos, 8.3–8.4 |
Credit. Lecture slide sources courtesy of Kevin Wayne.
Assignments
- Assignment 1, due Jan. 26
- Assignment 2, due Feb. 16
- Assignment 3, due Mar. 16
- Assignment 4, due Apr. 3
Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
Exams
Midterm
Date: Feb. 9, 2023
Time: 1:15pm–2:05pm
Place: Mulroney Hall, room 3022
Content: All material from Weeks 1 to 5
Final Exam
Date: Apr. 21, 2023
Time: 9:00am–11:30am
Place: Mulroney Hall, room 3022
Content: Primarily material from Weeks 6 to 12, some earlier material
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Thursday, 9:15am–11:15am