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: Thursday, 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:
- Background Quiz.
The TAs will go over the solutions in the first tutorial on
January 14.
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:
Tentative schedule, based on the last time I taught this course.
Ignore the dates, they are from last year.
- January 13 (Section B); January 14 (Section A):
- January 15 (Section B); January 16 (Section A):
- January 20 (Section B); January 21 (Section A):
- January 22 (Section B); January 23 (Section A):
- January 27 (Section B); January 28 (Section A):
- Finish heaps.
- Max-heaps versus min-heaps.
- Introduction to graphs.
- How to represent graphs (Section 3.1).
- My notes.
- Video
lecture 7.
- January 29 (Section B); January 30 (Section A):
- 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 3 (Section B); February 4 (Section A):
- 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 5 (Section B); February 6 (Section A):
- 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:
- 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):