Design and Analysis of Algorithms I (COMP 3804)
Sections A and B
Winter 2024
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel@scs.carleton.ca
Lectures and tutorials:
- All lectures and tutorials will be in-person.
- Tutorials will start on January 12.
- Winter break: February 19-23.
- Section A:
- Lectures: Tuesday and Thursday, 8:35-9:55, Azrieli Theatre 101.
- First lecture: Tuesday January 9.
- Last lecture: Tuesday April 9.
- Tutorial: Friday, 10:05-11:25, Azrieli Theatre 101.
- Section B:
- Lectures: Tuesday and Thursday, 13:05-14:25, Azrieli Theatre 302.
- First lecture: Tuesday January 9.
- Last lecture: Tuesday April 9.
- Tutorial: Friday, 10:05-11:25, Azrieli Theatre 102.
Office hours: will start in the week of January 15.
- Alma Arevalo Loyola: Monday, 11-noon, Herzerg 3115
- Yan Garito: Monday, 14-16, Herzerg 3115
- Michiel Smid: Tuesday, 10:15-11:30, Herzberg 5125C.
- Karthik Murali: Tuesday, 14:30-16:30, Herzberg 3115
- Hussein Houdrouge: Tuesday, 15-17, Herzberg 3115
- Tyler Tuttle: Wednesday, 11-noon, Herzber 3115
- Jag Zhang: Wednesday, 15-17, Herzberg 3115
- Ajay Sandhu: Thursday, 16-18, Herzberg 3115
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 18, due February 1
- Assignment 2: posted February 1, due February 15
- Midterm: Friday March 1, 10:05 - 11:25, in-person, during the
tutorial.
- Assignment 3: posted March 11, due March 25
- Assignment 4: posted March 25, due April 8
- 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 February 1, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here is the figure.
- Here are the solutions
for Assignment 1.
- Assignment 2 is due Thursday February 15, before 23:59.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here,
here, and
here are the figures.
- Here are the solutions
for Assignment 2.
- Assignment 3 is due Monday March 25, before 23:59.
- Here is Assignment 3 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions
for Assignment 3.
- Assignment 4 is due Monday April 8, before 23:59.
- Here is Assignment 4 as a
pdf file.
- Here is the LaTeX file.
Tutorials:
- Background Quiz,
January 12.
- Tutorial, January 19.
Solutions
P2, P3, P4.
Solutions
P5, P6.
Solution P7.
- Tutorial, January 26.
Solutions.
- Tutorial, February 2.
Solutions.
- Tutorial, February 9.
Solutions.
- Tutorial, February 16.
Solutions.
- Tutorial, March 8. Solutions
midterm.
Solutions.
- Tutorial, March 15.
Solutions.
- Tutorial, March 22: Finish the questions from March 15.
Midterm:
- The midterm will be on Friday March 1, 10:05-11:25, during the
tutorial.
- Azrieli Theatre 101: All students registered in Section A.
- Azrieli Theatre 102: All students registered in Section B.
- 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 the solutions of Assignment 1.
- Here is the midterm from last
year, and
here are the answers.
- Here is the midterm from this
term. For the answers, see tutorial March 8.
Final exam:
Academic Integrity:
If you are unsure of the expectations regarding academic integrity
(how to use and cite references, if collaboration with lab- or
classmates is permitted (and, if so, to what degree), then you must
ASK your instructor. Sharing assignment or quiz specifications or
posting them online (to sites like Chegg, CourseHero, OneClass, etc.)
is ALWAYS considered academic misconduct. You are NEVER permitted to
post, share, or upload course materials without explicit permission
from your instructor. Academic integrity offences are reported to
the office of the Dean of Science. Information, process and penalties
for such offences can be found
here.
What was done in class: The videos are from previous terms.
- 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:
Tentative schedule, based on the last time I taught this course.
- March 28:
- Definition of a language being
NP-complete.
- Some properties of polynomial-time reductions.
- My notes.
- Watch video lecture 22 again.
- April 2:
- Circuit-SAT is NP-complete.
- An example of
the reduction.
- My notes, more
notes.
- Video lectures:
- A
list of NP-complete problems.
- April 4:
April 9: ???.