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: TBA

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

- The midterm will be on Wednesday March 3, 11:30am - 1pm.
- This is not during the official lecture time.
- Details TBA.

- Details TBA.

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

- 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:
- February 8:
- Dijkstra's algorithm (Section 4.4).
- Union-Find (the solution presented in class is not in the textbook).

- February 10:
- Union-Find (not in the textbook).
- Minimum spanning trees (Section 5.1).
- Kruskal's algorithm (Section 5.1).
- Here is a more detailed description and correctness proof of Kruskal's algorithm (and Prim's algorithm as well).

- February 15:
- Prim's algorithm (Section 5.1).

- February 17: ???
- February 22/24: winterbreak
- March 1:
- Dynamic programming (Chapter 6).
- Shortest paths in a directed acyclic graph (Section 6.1).
- Longest increasing subsequence (Section 6.2).

- March 3:
- Matrix chain multiplication (Section 6.5).
- Longest Common Subsequence.

- March 8:
- All-pairs shortest paths: The Floyd-Warshall algorithm (Section 6.6).
- Introduction to the complexity classes P and NP (Chapter 8).

- March 10:
- 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.