Winter 2021

- 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".

- 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.

- 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

- 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)

- Assignments: 25%
- Midterm: 25%
- Final: 50%

- 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.
- Assignment 2 is due Sunday February 28, before 23:59.

- 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.

- Tuesday April 20, 2-4pm (or 2-5pm).

- 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.

- January 12:
- Video lecture 1, part 1: short introduction.
- Video lecture 1, part 2.
- My notes.
- Introduction to algorithms, running time, Big-O, Big-Omega, Big-Theta (Chapter 0).

- January 14:
- Video lecture 2, part 1.
- Video lecture 2, part 2.
- Video lecture 2, part 3.
- My notes.
- More notes.
- Divide-and-conquer algorithms and recurrence relations, merge-sort, multiplying large integers, Karatsuba's algorithm (Sections 2.1 and 2.3; Exercise 2.3).

- January 19:
- Recurrence relations, Master Theorem, matrix multiplication, Strassen's algorithm (Sections 2.2 and 2.5, my notes from January 14).
- Video lecture 3.

- January 21:
- Selection and median algorithms (Section 2.4).
- My notes.
- Video lecture 4.

- January 26:
- Randomized selection; my notes.
- Very short introduction to heaps (Section 4.5).
- Video lecture 5.

- January 28:
- Heaps.
- My notes.
- Video lecture 6.

- February 2:
- More on heaps.
- Very short introduction to graphs.
- Video lecture 7.

- 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:
- Shortest paths in directed acyclic graphs, Dijkstra's algorithm (Sections 4.1, 4.4, 4.7).
- My notes.
- Video lecture 12.

- March 2:
- Dijkstra's algorithm: running time and correctness (Section 4.4).
- My notes.
- Video lecture 13.

- Wednesday March 3:
- Midterm, 11:30am - 1pm.

- March 4:
- No lecture, because of the midterm.

- March 9:
- Union-Find (the solution presented in class is not in the textbook).
- Minimum spanning trees (Section 5.1).
- Introduction to Kruskal's algorithm (Section 5.1).
- My notes.
- Video lecture 14.

- March 11:
- Kruskal's algorithm (Section 5.1).
- Prim's algorithm (Section 5.1).
- My notes.
- Here is a more detailed description and correctness proof of Kruskal's and Prim's algorithms. These notes have a different data structure for Union-Find than the one presented in class.
- Video lecture 15.

- March 16:
- Finish Prim's algorithm.
- Dynamic programming (Chapter 6).
- Shortest/longest paths in a directed acyclic graph (Section 6.1).
- My notes.
- Video lecture 16.

- March 18:
- Longest increasing subsequence (Section 6.2).
- Matrix chain multiplication (Section 6.5).
- Video lecture 17.

- March 23:
- Longest Common Subsequence.
- All-pairs shortest paths: The Floyd-Warshall algorithm (Section 6.6).
- Lecture 18.

- March 10:
- Introduction to the complexity classes P and NP (Chapter 8).
- Formal definitions of P and NP.
- Examples of problems in NP: Hamilton Cycle, Traveling Salesman Problem, SubsetSum, Clique.
- P is contained in NP.
- P versus NP.
- 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.
- On page 183, condition 2 should be: x is an element of L if and only if f(x) is an element of L'.

- March 15:
- Reductions and some examples.

- 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:
- A list of NP-complete problems; and another list.
- Zero-knowledge proofs.