Design and Analysis of Algorithms I (COMP 3804)
Sections A, B, C, and D
Winter 2022
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel(@scs.carleton.ca)
Lectures:
- Lecture times:
- Tuesday and Thursday, 16:05 - 17:25, Steacie Building 103,
Section B (online) and Section D (in-person).
- Wednesday and Friday, 16:05 - 17:25, Southam Hall 624,
Section A (online) and Section C (in-person).
- Until February 4, there won't be live lectures. Instead, links to
pre-recorded video lectures (from the winter term of 2021) can be found
in the section "What was done in class".
- Starting in the week of February 7, there
will be in-person lectures. Students in the online sections can join
the live in-person lectures through Zoom. The Zoom link can be found
on Brightspace.
- In the section "What was done in class", you will also find all video
lectures from the winter term of 2021.
Winter term:
- The first lecture is on Tuesday January 11.
- February 21-25: Winter break, no classes.
- The last lecture is on Friday April 8.
Office hours: Will start in the week of January 17.
Click on a name to join a Zoom or Google Meet session with that person
during their scheduled office hours.
- The Discord server for this course is
here.
- Braeden Hall,
Wednesday 2-4pm, on Zoom.
- Hussein
Houdrouge, Monday 5-7pm, on Zoom.
- Gowthaman
Sivakumaran, Thursday 10am-noon, on Zoom.
- Michiel Smid,
Tuesday and Thursday, 9-10am, on Google Meet or in my office.
- Vivek Thaker ,
Tuesday 6:30-8:30pm, on Zoom.
- Tyler Tuttle,
Wednesday noon-2pm, on Zoom.
- Marc Vicuna,
Monday 10:30am-12:30pm, on Zoom.
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 24, due February 7
- Assignment 2: posted February 7, due February 28
- Midterm: Thursday March 3, 16:00 - 17:30, on Brightspace. Note that
the midterm will be at this time for all sections.
- Assignment 3: posted March 14, due March 28
- Assignment 4: posted March 28, due April 11
- Final exam: Friday April 22, 14:00 - 16:00, on Brightspace. Note that
the final exam will be at this time for all sections.
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 Monday February 7, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Assignment 2 is due Monday February 28, before 23:59.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Assignment 3 is due Monday March 28, before 23:59.
- Here is Assignment 3 as a
pdf file.
- Here is the LaTeX file and
here is the figure.
- Here are the solutions.
- Assignment 4 is due Monday April 11, before 23:59.
- Here is Assignment 4 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
Assignments from the winter term of 2021:
Midterm:
- The midterm will be on Thursday March 3, between 3:50pm and
5:40pm.
- The midterm will be on Brightspace for all sections.
- Sign in to Brightspace on Thursday March 3 by 3:50pm and click the
Midterm link to begin. If you have trouble finding the link, go to
Tools-->Quizzes. Once you start, you have 90 minutes.
- All questions will be multiple-choice, and you will be able to
freely move between questions. 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.
- I have migrated multiple-choice questions from cuLearn to
Brightspace. Not all questions show up properly, especially those
that have a figure in it. Go to Tools --> Quizzes, and click on
"Practice Multiple Choice Questions". I hope you can access the
questions.
Final exam:
- The final exam will be on Friday April 22, between 1:50pm and
4:10pm.
- The final exam will be on Brightspace for all sections.
- Sign in to Brightspace on Friday April 22 by 1:50pm and click the
Final Exam link to begin. If you have trouble finding the link, go
to Tools-->Quizzes. Once you start, you have 120 minutes.
- All questions will be multiple-choice, and you will be able to
freely move between questions. The final exam will cover everything
done in the lectures, as well as all four assignments.
- I have migrated multiple-choice questions from cuLearn to
Brightspace. Not all questions show up properly, especially those
that have a figure in it. Go to Tools --> Quizzes, and click on
"Practice Multiple Choice Questions". I hope you can access the
questions.
- Here are two old exams:
winter 2008 and
winter 2011. Some questions will look
familiar to you.
Academic Integrity (New, Please Read):
As of 2020, there are new penalties in place for academic integrity
violations. These will be issued by the Associate Dean (Undergraduate
Affairs) of Science to students who copy, in whole or in part, work
they submit for assignments.
- First offence, first-year students (less than 4.0 credits completed):
No credit for assessment(s) in question, or a final grade reduction of
one full letter grade (e.g., A- becomes B-), whichever is a greater
reduction.
- First offence (anyone else): A grade of F in the course.
- Second offence (anyone): A grade of F in the course and a one-term
suspension from studies.
- Third offence: Expulsion from the University.
Note: While these are the standard penalties, more severe penalties may
be applied when warranted. For more information, click
here.
What was done in class:
- January 11/12:
- January 13/14:
- January 18/19:
- January 20/21:
- January 25/26:
- January 27/28:
- February 1/2:
- February 3/4:
- Graphs, how to represent them (Section 3.1).
- Exploring an undirected graph from a vertex (Section 3.2.1).
- My notes.
- Video
lecture 8.
- February 8/9:
- From now on, there will be in-person
lectures. Please come to campus, because I don't want to teach
in an empty classroom.
- Undirected graphs: Depth-first search, how to compute the
connected components (Section 3.2).
- My notes.
- February 8:
Video
lecture 9.
- February 9:
Video
lecture 9.
- Video
lecture 9 from winter 2021.
- February 10/11:
- 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.
- February 10: There was a technical issue; no video for lecture
10. You can watch the February 11 video.
- February 11:
Video
lecture 10.
- Video
lecture 10 from winter 2021.
- February 15/16:
- February 17/18:
- February 21-25: Winter break.
- March 1/2:
- March 2:
Video
lecture 13.
- Video
lecture 13 from winter 2021.
Thursday March 3: Midterm, 16:00 - 17:30.
Friday March 4: No lecture, because of the midterm.
March 8/9:
March 10/11:
March 15/16:
March 17/18:
March 22/23:
March 24/25:
March 29/30:
March 31/April 1:
April 5/6:
April 7/8:
Tentative schedule, based on the last time I taught this course.