Contents may differ from the current or most recent offering of the course.
Course Description
An introduction to the design, analysis, and implementation of algorithms to solve common computational problems. Basic algorithm design techniques such as the greedy strategy, divide-and-conquer, and dynamic programming, as well as network flows, intractability, and NP-completeness will be discussed.
See the course outline for more information.
Course Details
Lecture Time/Place
Tuesday, 12:30pm–1:20pm; Thursday, 11:30am–12:20pm; Friday, 1:30pm–2:20pm
All lectures are held in Mulroney Hall, room 4032.
Textbook
J. Kleinberg and É. Tardos, Algorithm Design. Pearson Addison-Wesley, 2005.
Course notes will be provided for each lecture. The course textbook will be used as an optional supplement.
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
- Dec. 4: The final exam will be written on Dec. 11. See the review document and the Exams section below for details. A practice final exam is also available.
- Dec. 2: Due to classes being cancelled on Tuesday, Dec. 3, office hours will be moved to Thursday, Dec. 5.
- Nov. 29: Lecture notes for the twelfth week have been posted.
- Nov. 25: The fourth assignment has been posted. It is due by Dec. 5 at 11:30am.
- Nov. 21: Lecture notes for the eleventh week have been posted.
- Nov. 15: Lecture notes for the tenth week have been posted.
- Nov. 8: The third assignment has been posted. It is due by Nov. 21 at 11:30am.
- Nov. 7: Lecture notes for the eighth and ninth weeks have been posted.
- Oct. 28: Lecture notes for the sixth week have been posted.
- Oct. 25: The midterm will be written next week during the Nov. 1 lecture. See the review document and the Exams section below for details. A practice midterm is also available.
- Oct. 8: Lecture notes for the fifth week have been posted.
- Oct. 3: As mentioned in lecture today, the lecture on Friday will be cancelled due to the instructor being away.
- Sep. 27: Lecture notes for the fourth week have been posted.
- Sep. 25: Due to the fact that the instructor will be away on Oct. 4 (oops!), the deadline for the second assignment has been moved to Oct. 8 at 12:30pm.
- Sep. 24: Due to the holiday next Monday, the deadline for the second assignment has been moved to Oct. 4 at 1:30pm.
- Sep. 23: The second assignment has been posted. It is due by Oct. 3 at 11:30am.
- Sep. 17: Lecture notes for the third week have been posted.
- Sep. 10: Lecture notes for the second week have been posted.
- Sep. 6: The first assignment has been posted. It is due by Sep. 19 at 11:30am.
- Sep. 5: Lecture notes for the first week have been posted.
- Sep. 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 |
| — | Review of graphs (optional reading) | Kleinberg & Tardos, Ch. 3 |
| 3 | Greedy algorithms: coin changing, scheduling, partitioning | Kleinberg & Tardos, 4.1–4.2 |
| 4 | Greedy algorithms (cont’d): Dijkstra, MSTs (Prim, Kruskal, Borůvka) | Kleinberg & Tardos, 4.4–4.6 |
| 5 | Divide and conquer: mergesort, quicksort, median/selection | Kleinberg & Tardos, 5.1–5.2, 5.4 |
| — | Fall study break | — |
| 6 | Divide and conquer (cont’d): master theorem, integer and matrix multiplication | Kleinberg & Tardos, 5.5 |
| 7 | Mid-course review, midterm examination | — |
| 8 | Dynamic programming: scheduling, least squares | Kleinberg & Tardos, 6.1–6.3 |
| 9 | Dynamic programming (cont’d): knapsack problem, RNA secondary structures | Kleinberg & Tardos, 6.4–6.5 |
| 10 | Dynamic programming (cont’d): sequence alignment, Bellman–Ford–Moore | Kleinberg & Tardos, 6.6, 6.8 |
| 11 | Network flow: max-flow and min-cut, Ford–Fulkerson | Kleinberg & Tardos, 7.1–7.2 |
| 12 | Intractability: reductions, P vs. NP, NP-completeness | Kleinberg & Tardos, 8.1–8.4 |
Credit. Lecture slide sources courtesy of Kevin Wayne.
Assignments
- Assignment 1, due Sep. 19
- Assignment 2, due
Oct. 3Oct. 8 - Assignment 3, due Nov. 21
- Assignment 4, due Dec. 5
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: Nov. 1, 2024
Time: 1:30pm–2:20pm
Place: Mulroney Hall, room 4032
Content: All material from Weeks 1 to 6
Final Exam
Date: Dec. 11, 2024
Time: 2:00pm–4:30pm
Place: Mulroney Hall, room 4032
Content: Primarily material from Weeks 7 to 12, some earlier material
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday/Tuesday/Wednesday, 10:30am–11:20am, or by appointment