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: Tuesday April 8.
- Tutorial: Friday, 10:05-11:25.
- Section B:
- Lectures: Monday and Wednesday, 10:05-11:25.
- First lecture: Monday January 6.
- Last lecture: Monday April 7.
- 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
- 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.
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.
Final exam:
- Information about the final exam will be posted here.
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.
Tentative schedule, based on the last time I taught this course.
Ignore the dates, they are from last year.
- February 27:
- February 29:
-
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 5:
- March 7:
- March 12:
- March 14:
- March 19:
- 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).
- 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 21:
March 26:
- More reductions.
- Three versions of lecture 22:
March 28:
- Definition of a language being
NP-complete.
- Some properties of polynomial-time reductions.
- Introduction to Circuit-SAT.
- My notes, more
notes.
- Watch video lecture 22 again.
April 2:
- Circuit-SAT is NP-complete.
- An example of
the reduction.
- My notes.
- Video lectures:
- A
list of NP-complete problems.
April 4:
April 9: No lecture.