Design and Analysis of Algorithms I (COMP 3804)
Sections A and B
Winter 2023
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 18.
- Winter break: February 20-24.
- Section A:
- Lectures: Monday and Wednesday, 8:35-9:55, Steacie Building 103.
- First lecture: Monday January 9.
- Last lecture: Monday April 10.
- Tutorial: Wednesday, 14:35-15:55, Tory Building 360.
- Section B:
- Lectures: Tuesday and Thursday, 11:35-12:55, Steacie Building 103.
- First lecture: Tuesday January 10.
- Last lecture: Tuesday April 11.
- Tutorial: Wednesday, 14:35-15:55, Minto Centre 5050.
Office hours: will start in the week of January 16.
- Zoltan Kalnay: Tuesday 2-3, in-person, Herzberg 4125
- Danniel Kim: Friday 2-3, in-person, Herzberg 4125
- Mariami Lomtadze: Thursday 10:15-11:15, in-person, Herzberg 4125
- Alma Arevalo Loyola: Monday 10-noon, in-person, Herzberg 4125
- Michiel Smid: Thursday 9-11, in-person, Herzberg 5125C
- Tyler Tuttle: Thursday 2-3, in-person, Herzber 4125
- Marc Vicuna:
Friday 10-noon, online, click on the name
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 19, due February 2
- Assignment 2: posted February 2, due February 16
- Midterm: Wednesday March 1, 14:35 - 15:55, in-person, during the
tutorial.
- Assignment 3: posted March 9, due March 23
- Assignment 4: posted March 23, due SUNDAY APRIL 9
- Final exam: Monday April 24, 9-11, in-person, Field House.
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 2, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Assignment 2 is due Thursday February 16, before 23:59.
- Assignment 3 is due Thursday March 23, before 23:59.
- Here is Assignment 3 as a
pdf file.
- Here is the LaTeX file.
- The figures are
here and
here.
- Here are the solutions.
- Assignment 4 is due SUNDAY APRIL 9, before 23:59.
- Here is Assignment 4 as a
pdf file.
- Here is the LaTeX file.
- The figure is here.
- Here are the solutions.
Tutorials:
- Background Quiz.
- Tutorial 1, January 18.
- Tutorial 2, January 25.
- THIS IS AN ASSIGNMENT FROM LAST YEAR:
Assignment 1, Winter 2022.
Here are the solutions.
- Tutorial 3, February 1.
- THIS IS AN ASSIGNMENT FROM LAST YEAR:
Assignment 2, Winter 2022.
Here are the solutions.
- Tutorial 4, February 8: Questions 2, 3, 4, and 5 from
Assignment 2, winter 2022.
- Tutorial 5, February 15: Questions 6 and 7 from
Assignment 2, winter 2022.
- Tutorial 6, March 8: Midterm
solutions,
Q13.
- THIS IS AN ASSIGNMENT FROM LAST YEAR:
Assignment 3, Winter 2022.
Here are the solutions.
- Tutorial 7, March 15: Some questions from Assignment 3, winter 2022.
- THIS IS AN ASSIGNMENT FROM LAST YEAR:
Assignment 4, Winter 2022.
Here are the solutions.
- Tutorial 8, March 22: Some questions from Assignment 3, winter 2022.
Midterm:
- The midterm will be on Wednesday March 1, 14:35-15:55, during the
tutorial.
- Tory Building 360: All students whose last names start with
A-K.
- Minto Centre 5050: All students whose last names start with
L-Z.
- 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.
- 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 this term's midterm, and
here are the answers.
Final exam:
- The final exam will be on Monday April 24, 9-11, in person,
Field House.
- All questions will be multiple-choice. The final exam will cover
everything done in the lectures, as well as all four assignments.
- Here is the exam from last
year, and
here are the answers.
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/10:
- 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/12:
- January 16/17:
- January 18/19:
- January 23/24:
- January 25/26:
- January 30/31:
- February 1/2:
- Graphs, how to represent them (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).
- My notes.
- Video
lecture 8.
- Three versions of lecture 9:
- February 6/7:
- Undirected graphs: deciding if a graph is bipartite (Section 3.2).
- Directed acyclic graphs: topological sorting (Section 3.3).
- Directed graphs: depth-first search (Section 3.3).
- My notes.
- Two versions of lecture 10:
- February 8/9:
- Directed graphs: Depth-first search, deciding if a graph is
acyclic, topological sorting (Section 3.3).
- My notes.
- Three versions of lecture 11:
- February 13/14:
- Shortest paths in directed acyclic graphs,
Dijkstra's
algorithm
(Sections 4.1, 4.4, 4.7).
- My notes.
- Three versions of lecture 12:
- February 15/16:
- Dijkstra's algorithm: running time and correctness (Section 4.4).
- Very short introduction to minimum spanning trees.
- My notes.
- Three versions of lecture 13:
- February 20-24: Winter break.
- February 27/28:
- March 1/2: Lecture 15.
-
Prim's algorithm (Section 5.1).
- Introduction to
Dynamic programming (Chapter 6).
- Introduction to shortest/longest paths in a directed acyclic
graph (Section 6.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.
- My notes on dynamic
programming.
- Three versions of lecture 15:
- March 6/7:
- March 8/9:
- March 13/14:
- March 15/16:
- March 20/21:
- 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 22/23:
March 27/28:
- More reductions.
- Three versions of lecture 22:
March 29/30:
- Definition of a language being
NP-complete.
- Some properties of polynomial-time reductions.
- My notes.
- Watch video lecture 22 again.
April 3/4:
- Circuit-SAT is NP-complete.
- An example of
the reduction.
- My notes, more
notes.
- Video lectures:
- A
list of NP-complete problems.
April 5/6:
Tentative schedule, based on the last time I taught this course.