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: TBA
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.
Midterm:
- The midterm will be on Wednesday March 3, 11:30am - 1pm.
- This is not during the official lecture time.
- Details TBA.
Final exam:
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:
Tentative schedule, based on the last time I taught this course.
Ignore the dates below, they are from last time.
- January 27:
- Graphs, depth-first search (Sections 3.1 and 3.2).
- Undirected graphs: Depth-first search, how to compute the
connected components, testing if a graph is bipartite
(Section 3.2).
- Directed graphs: Depth-first search (Section 3.3).
- February 1:
- Directed graphs: Depth-first search, deciding if a graph is
acyclic, topological sorting (Section 3.3).
- Shortest paths in directed acyclic graphs
(Sections 4.1 and 4.7).
-
Page 85: If (v,u) is a cross edge, then
pre(u) < post(u) < pre(v) < post(v), because explore(u)
finishes before explore(v) starts.
-
Page 86: Assume v_0 --> v_1 --> ... --> v_k --> v_0 is a
directed cycle. We may assume that v_0 has the largest
post-number among the vertices on this cycle. (Otherwise, we
can renumber the vertices on this cycle.)
There must be an index i such that post(v_i) < post(v_{i+1});
if i=k, then read i+1 as 0.
Then it follows from pages 84 and 85 that (v_i,v_{i+1}) is a
back edge.
-
Page 89: Correctness proof: Let (v,u) be any edge in G. We have
to show that in the topological sorting, the number of v is less
than the number of u. Thus, from the way we obtain the
topological sorting, we have to show that post(v) > post(u).
This follows from pages 84 and 85, because (v,u) is a tree edge,
a forward edge, or a cross edge. (Recall that (v,u) cannot be a
back edge, because G is acyclic.)
- February 3:
- Shortest paths in directed acyclic graphs,
Dijkstra's
algorithm
(Sections 4.1, 4.4, 4.7).
- February 8:
- Dijkstra's algorithm (Section 4.4).
-
Union-Find
(the solution presented in class is not in the textbook).
- February 10:
- February 15:
- February 17: ???
- February 22/24: winterbreak
- March 1:
- March 3:
- March 8:
- 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: