There won't be lectures on February 2, 3, 4, and 5.
Instead, you will watch the videos.
Michiel won't have office hours on February 3.
Hussein won't have office hours on February 4.
Design and Analysis of Algorithms I (COMP/MATH 3804)
Sections A and B
Winter 2026
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel@scs.carleton.ca
Course outline:
Lectures and tutorials:
- All lectures and tutorials will be in-person.
- Classrooms: Check Carleton Central.
- Tutorials will start on Wednesday January 14.
- Winter break: February 16-20.
- Section A:
- Lectures: Tuesday and Thursday, 8:35-9:55.
- First lecture: Tuesday January 6.
- Last lecture: Tuesday April 7
- Tutorial: Wednesday, 17:35-18:55.
- Section B:
- Lectures: Monday and Wednesday, 16:05-17:25.
- First lecture: Monday January 5.
- Last lecture: Monday April 6
- Tutorial: Wednesday, 17:35-18:55.
Office hours: will start in the week of January 12.
- Hussein: Wednesday, 9:45-10:45, Herzberg 4115
- Marco: Thursday, 4:30-5:30, Herzberg 4115
- Michiel: Tuesday, 10:15-11:15, Herzberg 5125C
- Nick: Friday, 1-2, Herzberg 4115
- Ryan: Monday, 11-noon, Herzberg 4115
- Tyler: Tuesday, 1-2, Herzberg 4115
- Zoltan: Wednesday, 1:30-2:30, Herzberg 4115
Course objectives:
An introduction to the design and analysis of algorithms.
Topics covered include:
Divide-and-conquer algorithms and their analysis using recurrence
relations, graph algorithms, dynamic programming, the theory of
NP-completeness.
Textbook:
Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, and
Umesh Vazirani, published by McGraw-Hill.
Important dates:
- Test 1: Wednesday, January 28, during the tutorial
- Test 2: Wednesday, February 11, during the tutorial
- Test 3: Wednesday, March 11, during the tutorial
- Test 4: Wednesday, March 25, during the tutorial
- Final exam: TBA
Grading scheme:
- Test 1: 12.5%
- Test 2: 12.5%
- Test 3: 12.5%
- Test 4: 12.5%
- Final: 50%
Problem sets:
Tutorials:
Test 1:
- The first test will be on Wednesday January 28, 17:35-18:55,
in-person, in the tutorial classroom. You must go to the classroom
corresponding to your section.
- It will be a multiple-choice test.
- You are supposed to know everything that was done in class up to,
and including, the randomized selection algorithm, as well as
problem sets 1 and 2, and the tutorials.
- If, for whatever reason, you miss this test, it will be covered by
the final exam. You do not have to send me an email.
- Here is Test 1, and
here are the answers.
What was done in class: The videos are from previous terms.
- January 5/6:
- Introduction to algorithms, running time, Big-O, Big-Omega,
Big-Theta, little-o (Chapter 0).
- My notes.
- Ignore this, it is from the winter term of 2022.
Video
lecture 1, part 1: short introduction.
- Ignore this, it is from the winter term of 2021.
Video
lecture 1, part 1: short introduction.
- Video
lecture 1, part 2 from a previous term.
- January 7/8:
- January 12/13:
- January 14/15:
- January 19/20:
- January 21/22:
- January 26/27:
- Finish heaps.
- Max-heaps versus min-heaps.
- Introduction to graphs.
- How to represent graphs (Section 3.1).
- My notes.
- Video
lecture 7.
- January 28/29:
- How to represent graphs (Section 3.1).
- Exploring an undirected graph from a vertex (Section 3.2.1).
- Undirected graphs: Depth-first search, how to compute the
connected components (Section 3.2).
- Undirected graphs: deciding if a graph is bipartite (Section 3.2).
- My notes.
- More notes.
- Video
lecture 8.
- Three versions of lecture 9:
- February 2/3:
No lecture, watch video
- Directed acyclic graphs: topological sorting (Section 3.3).
- Directed graphs: depth-first search, deciding if a graph is
acyclic (Section 3.3).
- My notes.
- Two versions of lecture 10:
- February 4/5:
No lecture, watch video
- Directed acyclic graphs: topological sorting (Section 3.3).
- Shortest paths in directed acyclic graphs (Sections 4.1, 4.7).
- My notes.
- Three versions of lecture 11:
Tentative schedule, based on the last time I taught this course.
Ignore the dates, they are from last year.
- February 10 (Section B); February 11 (Section A):
- Shortest paths in directed acyclic graphs,
Dijkstra's
algorithm
(Sections 4.1, 4.4, 4.7).
- Three versions of lecture 12:
- February 12 (Section B); February 13 (Section A):
- Dijkstra's algorithm:
correctness proof by
contradiction (Section 4.4).
- My notes have a different (and
longer) correctness proof.
- Shortest paths in directed graphs without cycles of negative
weight,
Bellman-Ford algorithm
(Section 4.6).
- My Bellman-Ford notes.
- Three versions of lecture 13:
February 17-21: Winter break.
February 24 (Section B); February 25 (Section A):
February 26 (Section B); February 27 (Section A):
-
Kruskal's algorithm (Section 5.1).
-
Prim's algorithm (Section 5.1).
- My notes.
- Here are more detailed descriptions
and correctness proofs of Kruskal's and Prim's algorithms.
These notes have a different data structure for Union-Find than
the one presented in class.
- Three versions of lecture 15:
March 3 (Section B); March 4 (Section A):
March 5 (Section B); March 6 (Section A):
March 10 (Section B); March 11 (Section A):
- Finish Longest Common Subsequence.
-
All-pairs shortest paths: The Floyd-Warshall algorithm
(Section 6.6).
- Introduction to the complexity classes
P
and
NP
(Chapter 8).
- Informal definitions of P and NP.
- Example of a problem in NP:
Hamilton cycle.
- My notes.
- Three versions of lecture 18:
March 12 (Section B); March 13 (Section A):
March 17 (Section B); March 18 (Section A):
- Formal definitions of P and NP.
- P is contained in NP.
-
P versus NP.
- Why decision (= YES/NO) problems? If we can decide HAM-CYCLE,
then we can find a Hamilton cycle (if it exists).
-
Reductions.
- My notes.
- Do you want to be a
millionaire?
- Gerhard Woeginger maintains a
P versus NP page, including links to "proofs" that
P and NP are (not) equal.
- Three versions of lecture 20:
March 19 (Section B); March 20 (Section A):
- More reductions.
- Three versions of lecture 21:
March 24 (Section B); March 25 (Section A):
- Definition of a problem being
NP-complete.
- Some properties of polynomial-time reductions.
- Introduction to Circuit-SAT.
- My notes, more
notes.
- Three versions of lecture 22:
March 26 (Section B); March 27 (Section A):
- Circuit-SAT is NP-complete.
- An example of
the reduction.
- Some more NP-complete problems.
- My notes.
- A
list of NP-complete problems.
- Video lectures:
March 31 (Section B); April 1 (Section A):
- Even more NP-complete problems.
- Reducing 3SAT to 3Color: My
notes and an example
graph for four variables
and two clauses.
- Some parts are in the videos (I think), whereas some parts are
not.
April 2 (Section B); April 3 (Section A):
April 7 (Section B); April 8 (Section A):