CSCI 355: Algorithm Design and Analysis (Winter 2022)

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

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

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
Winter study break
6 Mid-course review, midterm examination
7 Divide and conquer: mergesort, quicksort, median/selection Kleinberg & Tardos, 5.1–5.2, 5.4
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

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: Mar. 2, 2022
Time: 11:15am–12:05pm
Place: Mulroney Hall, room 3022
Content: All material from Weeks 1 to 5

Final Exam

Date: Apr. 22, 2022
Time: 9am–11:30am
Place: Mulroney Hall, room 3034
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: Tuesday, 9:15am–11:15am