CSCI 355: Algorithm Design and Analysis (Winter 2024)

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

Monday, 12:30pm–1:20pm; Wednesday, 11:30am–12:20pm; Thursday, 1:30pm–2:20pm

All lectures are held in Mulroney Hall, room 3022.

Special Note for Winter 2024. On Monday, April 8, the Friday schedule of classes and labs will be offered.


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

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%.



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
6 Mid-course review, midterm examination
Winter study break
7 Divide and conquer (cont’d): master theorem, integer and matrix multiplication Kleinberg & Tardos, 5.5
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 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.



Date: Feb. 15, 2024
Time: 1:30pm–2:20pm
Place: Mulroney Hall, room 3022
Content: All material from Weeks 1 to 5

Final Exam

Date: Apr. 16, 2024
Time: 9:00am–11:30am
Place: Mulroney Hall, room 3022
Content: Primarily material from Weeks 6 to 12, some earlier material



Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday/Wednesday/Friday, 9:30am–10:30am