Sections A, B, C, and D

Winter 2022

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

- The first lecture is on Tuesday January 11.
- February 21-25: Winter break, no classes.
- The last lecture is on Friday April 8.

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

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

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

- 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.
- Assignment 2 is due Monday February 28, before 23:59.
- Assignment 3 is due Monday March 28, before 23:59.
- Assignment 4 is due Monday April 11, before 23:59.

- Assignment 1, solutions, more solutions
- Assignment 2, solutions
- Assignment 3, solutions
- Assignment 4, solutions

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

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

- 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 11/12:
- Video lecture 1, part 1: short introduction.
- Ignore this, it is from the winter term of 2021. 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 13/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 18/19:
- Recurrence relations, Master Theorem, matrix multiplication, Strassen's algorithm (Sections 2.2 and 2.5, my notes from January 13/14).
- Video lecture 3.

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

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

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

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

- 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:
- Directed graphs: Depth-first search, deciding if a graph is acyclic, topological sorting (Section 3.3).
- My notes.
- February 15: Video lecture 11.
- February 16: Video lecture 11.
- Video lecture 11 from winter 2021.

- February 17/18:
- Shortest paths in directed acyclic graphs, Dijkstra's algorithm (Sections 4.1, 4.4, 4.7).
- My notes.
- February 17: Video lecture 12.
- February 18: Video lecture 12.
- Video lecture 12 from winter 2021.

- February 21-25: Winter break.
- March 1/2:
- Dijkstra's algorithm: running time and correctness (Section 4.4).
- My notes.
- March 1: Video lecture 13.
- 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:
- 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.
- March 8: Video lecture 14.
- March 9: Video lecture 14.
- Video lecture 14 from winter 2021.

- March 10/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.
- March 10: Video lecture 15.
- March 11: Video lecture 15.
- Video lecture 15 from winter 2021.

- March 15/16:
- Dynamic programming (Chapter 6).
- Shortest/longest paths in a directed acyclic graph (Section 6.1).
- Longest increasing subsequence (Section 6.2).
- My notes.
- March 15: Video lecture 16.
- March 16: Video lecture 16.
- Video lecture 16 from winter 2021.

- March 17/18:
- Matrix chain multiplication (Section 6.5).
- Longest Common Subsequence.
- March 17: Video lecture 17.
- March 18: Video lecture 17.
- Video lecture 17 from winter 2021.

- March 22/23:
- All-pairs shortest paths: The Floyd-Warshall algorithm (Section 6.6).
- Introduction to the complexity classes P and NP (Chapter 8).
- Informal definitions of P and NP.
- Examples of problems in NP: Hamilton Cycle, Traveling Salesman Problem, SubsetSum, Clique.
- My notes.
- March 22: Video lecture 18.
- March 23: Video lecture 18.
- Video lecture 18 from winter 2021.

- March 24/25:
- Formal definitions of P and NP.
- 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.
- My notes.
- March 24: Video lecture 19.
- March 25: Video lecture 19.
- Video lecture 19 from winter 2021.

- March 29/30:
- Reductions.
- My notes.
- March 29: Video lecture 20.
- March 30: Video lecture 20.
- Video lecture 20 from winter 2021.

- March 31/April 1:
- More reductions.
- March 31: Video lecture 21. This video has some remarks about Assignment 4.
- April 1: Video lecture 21. This video has some remarks about Assignment 4.
- Video lecture 21 from winter 2021.

- April 5/6:
- Definition of a language being NP-complete.
- Some properties of polynomial-time reductions.
- My notes.
- April 5: Video lecture 22.
- April 6: Video lecture 22.
- Video lecture 22 from winter 2021.

- April 7/8:
- Circuit-SAT is NP-complete.
- An example of the reduction.
- My notes, more notes, even more notes. (The last notes were not covered in the lectures.)
- April 7: Video lecture 23.
- April 8: Video lecture 23.
- Video lecture 23 from winter 2021.
- Video lecture 24 from winter 2021.
- A list of NP-complete problems.
- Worlde is NP-hard.
- No time this term to do this: Zero-knowledge proofs.

- We are done!