Design and Analysis of Algorithms I (COMP 3804B)
Winter 2021
Instructor:
Michiel Smid
Office: Herzberg Building 5125C (But: we are not allowed to
enter Herzberg.)
E-mail: michiel(@scs.carleton.ca)
Lectures:
- Official lecture times: Tuesday and Thursday, 8:35 - 9:55 am.
- There won't be live lectures. Instead, links to pre-recorded video
lectures will be posted in the section "What was done in class".
Winter term:
- First lecture is on Tuesday January 12.
- February 15-19: Winter break, no classes.
- Last lecture is on Tuesday April 13.
- Wednesday April 14: Last day of classes in the winter term. Classes
follow a Friday schedule.
Office hours: You can go to office hours of this Section B of
COMP 3804, as well as those of Section A, taught by Alina Shaikhet.
- Section A:
- Omar Ben Ismail, Tuesday 10am-noon, on Discord
- Christopher Blackman, Friday 2-4pm, on Discord
- Ilan Gofman, Wednesday 4-6pm, on Discord
- Alina Shaikhet, Wednesday and Friday 1-2pm, on Discord
- Section B:
- Zoltan Kalnay, Thursday 5-7pm, on Discord
- Damien Robichaud, Thursday 10am-noon, on Discord
- Michiel Smid:
Tuesday and Thursday, 4-5pm, on Google Meet, click on the name.
- Tyler Tuttle, Tuesday 1-3pm, on Discord
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: Wednesday March 3, 11:30am - 1pm
- Assignment 3: posted March 14, due March 28
- Assignment 4: posted March 28, due April 11
- Final exam: Tuesday April 20, 2-4pm (or 2-5pm)
Grading scheme:
- Assignments: 25%
- Midterm: 25%
- Final: 50%
Assignments:
- Late assignments will not be accepted.
- Real computer scientists use
LaTeX to type
their 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
cuLearn.
- 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 Sunday February 7, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions,
and here is the solution for
Question 5.
- Assignment 2 is due Sunday February 28, before 23:59.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
Midterm:
- The midterm will be on Wednesday March 3, between 11:20am and 1:10pm.
- This is not during the official lecture time.
- The midterm will be on cuLearn. The link is available on cuLearn
in the topic "Midterm". There are 19 multiple-choice questions.
The midterm will become available at 11:20am and it will close at
1:10pm. The moment you start the test, you will have 90 minutes to
complete it. Be sure to attend - there will be no make-up midterm.
Do not start your test late. For example, if you start your test at
12:00pm, then your attempt will terminate after 70 minutes at 1:10pm.
- 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.
- Here and
here are some old midterms.
Note that these are not multiple-choice midterms. This is the first
time that I teach COMP 3804 on-line; because of this, I do not have
old multiple-choice midterms.
Final exam:
- Tuesday April 20, 2-4pm (or 2-5pm).
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 12:
- January 14:
- January 19:
- January 21:
- January 26:
- January 28:
- February 2:
- February 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 9:
- Undirected graphs: Depth-first search, how to compute the
connected components (Section 3.2).
- My notes.
- Video
lecture 9.
- February 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.
- Video
lecture 10.
- February 15-19: Winter break.
- February 23:
- Directed graphs: Depth-first search, deciding if a graph is
acyclic, topological sorting (Section 3.3).
- My notes.
- Video
lecture 11.
- February 25:
- March 2:
- Wednesday March 3:
- March 4:
- No lecture, because of the midterm.
- March 9:
- March 11:
- March 16:
- March 18:
- March 23:
Tentative schedule, based on the last time I taught this course.
Ignore the dates below, they are from last time.
- March 10:
- March 15:
- March 17:
- More reductions.
- Definition of a language being
NP-complete.
- March 22:
- NP-completeness.
- Circuit-SAT is NP-complete.
- March 24:
- Some NP-completeness proofs.
- March 29: