Design and Analysis of Algorithms I (COMP/MATH 3804)
Sections A and B
Winter 2025
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 Friday January 10.
- Winter break: February 17-21.
- Section A:
- Lectures: Tuesday and Thursday, 8:35-9:55.
- First lecture: Tuesday January 7.
- Last lecture: Thursday April 3.
- Tutorial: Friday, 10:05-11:25.
- Section B:
- Lectures: Monday and Wednesday, 10:05-11:25.
- First lecture: Monday January 6.
- Last lecture: Wednesday April 2.
- Tutorial: Friday, 10:05-11:25.
Office hours: will start in the week of January 13.
- Alma: Monday 2-3, Herzberg 4125
- Amirali: Tuesday 11-noon, and Wednesday 11:30-12:30, both in
Herzberg 4115
- Christopher, Tuesday, 12:30-1:30, Herzberg 4115: NO OFFICE HOURS ON
APRIL 1.
- Hussein: Wednesday noon-2, Herzberg 4115
- Jag: Monday 2-4, Herzberg 4115
- Justin: Tuesday 10-11, Herzberg 4115
- Karthik: Wednesday 3-5, Herzberg 4115
- Marco: Wednesday, 1:30-3:30, Herzberg 4115
- Michiel: Tuesday, 10:30-11:30, Herzberg 5125C
- Tyler: Thursday 3-4, Herzberg 4115
- Yan: Thursday 10-noon, 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:
- Assignment 1: posted January 16, due February 2
- Assignment 2: posted February 2, due February 16
- Midterm: Friday February 28, 10:05 - 11:25, in-person, during the
tutorial.
- Assignment 3: posted March 6, due March 20
- Assignment 4: posted March 20, due April 3
- Final exam: TBA
Grading scheme:
- Assignments: 25%
- Midterm: 25%
- Final: 50%
Assignments:
- Late assignments will not be accepted.
- You are encouraged to use
LaTeX to type
your solutions. In case you want to learn LaTeX,
here is a tutorial.
- You can use the freely available
Ipe drawing
editor to make figures.
- Each assignment must be submitted as one single PDF file through
Brightspace. If you have trouble finding the link, go to
Tools --> Assignments.
- You can type your solutions, or write them by hand and scan them
(for example, using a scan app on your phone or using a real
scanner).
- Assignment 1 is due Thursday January 30, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Assignment 2 is due Sunday February 16, before 23:59.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here is the figure.
- Here are the solutions.
- Assignment 3 is due Thursday March 20, before 23:59.
- Here is Assignment 3 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Assignment 4 is due Thursday April 3, before 23:59.
- Here is Assignment 4 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
Assignments from a previous term:
Tutorials:
Midterm:
- The midterm will be on Friday February 28, 10:05-11:25, during the
tutorial.
- All questions will be multiple-choice. The midterm will cover
everything done in the lectures up to, and including, shortest paths
in directed acyclic graphs, as well as assignments 1 and 2 and the
tutorials.
- The midterm paper will have "Some useful facts" and the
"Master Theorem" as in Assignment 1.
- Here is the midterm
from Winter 2023.
- Here are
the answers.
- Here is the solution for Q13.
- Here is the midterm
from Winter 2024.
- Here is the midterm from this
term. For the solutions, see the March 7 tutorial.
Final exam:
- The final exam will be on Thursday April 24, 2-4pm, in person,
location TBA.
- All questions will be multiple-choice. The final exam will cover
everything done in the lectures, as well as all four assignments and
all tutorials.
- Here is the exam from Winter 2023,
and
here are the answers.
- Here is the exam from Winter 2024,
and
here are the answers.
What was done in class: The videos are from previous terms.
- January 6 (Section B); January 7 (Section A):
- 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 8 (Section B); January 9 (Section A):
- 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.
- Some parts are in the videos (I think), whereas some parts are
not.
Tentative schedule, based on the last time I taught this course.
Ignore the dates, they are from last year.
- April 2 (Section B); April 3 (Section A):
- April 7 (Section B); April 8 (Section A):