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.
- Michiel: Tuesday, 10:30-11:30, Herzberg 5125C
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 January 30
- Assignment 2: posted January 30, due February 13
- 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).
- Assignments will be posted here.
Tutorials:
Midterm:
- Information about the midterm will be posted here.
Final exam:
- Information about the final exam will be posted here.
What was done in class: The videos are from previous terms.
Tentative schedule, based on the last time I taught this course.
Ignore the dates, they are from last year.
- January 9:
- 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 previous term.
- January 11:
- January 16:
- January 18:
- January 23:
- January 25:
- January 30:
- Max-heaps versus min-heaps.
- Introduction to graphs.
- How to represent graphs (Section 3.1).
- Introduction to: Exploring an undirected graph from a vertex
(Section 3.2.1).
- My notes.
- Video
lecture 7.
- February 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 6:
- 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 8:
- 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 13:
- Shortest paths in directed acyclic graphs (correctness),
Dijkstra's
algorithm
(Sections 4.1, 4.4, 4.7).
- See my notes from February 8.
- Three versions of lecture 12:
- February 15:
- Dijkstra's algorithm: correctness (Section 4.4).
- My notes.
- Alternative correctness proof of
Dijkstra's algorithm: by contradiction.
- 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 19-23: Winter break.
- 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.