Sections A and B

Winter 2023

- All lectures and tutorials will be in-person.
- Tutorials will start on January 18.
- Winter break: February 20-24.
- Section A:
- Lectures: Monday and Wednesday, 8:35-9:55, Steacie Building 103.
- First lecture: Monday January 9.
- Last lecture: Monday April 10.
- Tutorial: Wednesday, 14:35-15:55, Tory Building 360.

- Section B:
- Lectures: Tuesday and Thursday, 11:35-12:55, Steacie Building 103.
- First lecture: Tuesday January 10.
- Last lecture: Tuesday April 11.
- Tutorial: Wednesday, 14:35-15:55, Minto Centre 5050.

- Zoltan Kalnay: Tuesday 2-3, in-person, Herzberg 4125
- Danniel Kim: Friday 2-3, in-person, Herzberg 4125
- Mariami Lomtadze: Thursday 10:15-11:15, in-person, Herzberg 4125
- Alma Arevalo Loyola: Monday 10-noon, in-person, Herzberg 4125
- Michiel Smid: Thursday 9-11, in-person, Herzberg 5125C
- Tyler Tuttle: Thursday 2-3, in-person, Herzber 4125
- Marc Vicuna: Friday 10-noon, online, click on the name

- Assignment 1: posted January 19, due February 2
- Assignment 2: posted February 2, due February 16
- Midterm: Wednesday March 1, 14:35 - 15:55, in-person, during the tutorial.
- Assignment 3: posted March 9, due March 23
- Assignment 4: posted March 23, due SUNDAY APRIL 9
- Final exam: Monday April 24, 9-11, in-person, Field House.

- 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 Thursday February 2, before 23:59.
- Assignment 2 is due Thursday February 16, before 23:59.
- Assignment 3 is due Thursday March 23, before 23:59.
- Assignment 4 is due SUNDAY APRIL 9, before 23:59.

- Background Quiz.
- Tutorial 1, January 18.
- Tutorial 2, January 25.
- THIS IS AN ASSIGNMENT FROM LAST YEAR: Assignment 1, Winter 2022. Here are the solutions.
- Tutorial 3, February 1.
- THIS IS AN ASSIGNMENT FROM LAST YEAR: Assignment 2, Winter 2022. Here are the solutions.
- Tutorial 4, February 8: Questions 2, 3, 4, and 5 from Assignment 2, winter 2022.
- Tutorial 5, February 15: Questions 6 and 7 from Assignment 2, winter 2022.
- Tutorial 6, March 8: Midterm solutions, Q13.
- THIS IS AN ASSIGNMENT FROM LAST YEAR: Assignment 3, Winter 2022. Here are the solutions.
- Tutorial 7, March 15: Some questions from Assignment 3, winter 2022.
- THIS IS AN ASSIGNMENT FROM LAST YEAR: Assignment 4, Winter 2022. Here are the solutions.
- Tutorial 8, March 22: Some questions from Assignment 3, winter 2022.

- The midterm will be on Wednesday March 1, 14:35-15:55, during the
tutorial.
- Tory Building 360: All students whose last names start with A-K.
- Minto Centre 5050: All students whose last names start with L-Z.

- All questions will be multiple-choice. 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.
- The midterm paper will have "Some useful facts" and the "Master Theorem" as in the solutions of Assignment 1.
- Here is the midterm from last year, and here are the answers.
- Here is this term's midterm, and here are the answers.

- The final exam will be on Monday April 24, 9-11, in person, Field House.
- All questions will be multiple-choice. The final exam will cover everything done in the lectures, as well as all four assignments.
- Here is the exam from last year, and here are the answers.

- January 9/10:
- Introduction to algorithms, running time, Big-O, Big-Omega, Big-Theta, little-o (Chapter 0).
- My notes.
- Ignore this, it is from the winter term of 2022. 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 from previous term.

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

- January 16/17:
- Finish Karatsuba, recurrence relations, Master Theorem, matrix multiplication, Strassen's algorithm (Sections 2.2 and 2.5, my notes from January 11/12).
- Video lecture 3.

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

- January 23/24:
- Randomized selection; my notes.
- Introduction to heaps (Section 4.5).
- My notes.
- Video lecture 5.

- January 25/26:
- Heaps.
- Video lecture 6.

- January 30/31:
- More on heaps.
- Introduction to graphs.
- My notes.
- Video lecture 7.

- February 1/2:
- Graphs, how to represent them (Section 3.1).
- Exploring an undirected graph from a vertex (Section 3.2.1).
- Undirected graphs: Depth-first search, how to compute the connected components (Section 3.2).
- My notes.
- Video lecture 8.
- Three versions of lecture 9:
- Video lecture 9 from winter 2022.
- Video lecture 9 from winter 2022.
- Video lecture 9 from winter 2021.

- February 6/7:
- 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.
- Two versions of lecture 10:
- Video lecture 10 from winter 2022.
- Video lecture 10 from winter 2021.

- February 8/9:
- Directed graphs: Depth-first search, deciding if a graph is acyclic, topological sorting (Section 3.3).
- My notes.
- Three versions of lecture 11:
- Video lecture 11 from winter 2022.
- Video lecture 11 from winter 2022.
- Video lecture 11 from winter 2021.

- February 13/14:
- Shortest paths in directed acyclic graphs, Dijkstra's algorithm (Sections 4.1, 4.4, 4.7).
- My notes.
- Three versions of lecture 12:
- Video lecture 12 from winter 2022.
- Video lecture 12 from winter 2022.
- Video lecture 12 from winter 2021.

- February 15/16:
- Dijkstra's algorithm: running time and correctness (Section 4.4).
- Very short introduction to minimum spanning trees.
- My notes.
- Three versions of lecture 13:
- Video lecture 13 from winter 2022.
- Video lecture 13 from winter 2022.
- Video lecture 13 from winter 2021.

- February 20-24: Winter break.
- February 27/28:
- Union-Find (the solution presented in class is not in the textbook).
- Minimum spanning trees (Section 5.1).
- Kruskal's algorithm (Section 5.1).
- My notes.
- Three versions of lecture 14:
- Video lecture 14 from winter 2022.
- Video lecture 14 from winter 2022.
- Video lecture 14 from winter 2021.

- March 1/2: Lecture 15.
- Prim's algorithm (Section 5.1).
- Introduction to Dynamic programming (Chapter 6).
- Introduction to shortest/longest paths in a directed acyclic graph (Section 6.1).
- My notes.
- Here are more detailed descriptions and correctness proofs of Kruskal's and Prim's algorithms. These notes have a different data structure for Union-Find than the one presented in class.
- My notes on dynamic programming.
- Three versions of lecture 15:
- Video lecture 15 from winter 2022.
- Video lecture 15 from winter 2022.
- Video lecture 15 from winter 2021.

- March 6/7:
- Dynamic programming (Chapter 6).
- Shortest/longest paths in a directed acyclic graph (Section 6.1).
- Longest increasing subsequence (Section 6.2).
- Matrix chain multiplication (Section 6.5).
- Three versions of lecture 16:
- Video lecture 16 from winter 2022.
- Video lecture 16 from winter 2022.
- Video lecture 16 from winter 2021.

- March 8/9:
- Matrix chain multiplication (Section 6.5).
- Longest Common Subsequence.
- Three versions of lecture 17:
- Video lecture 17 from winter 2022.
- Video lecture 17 from winter 2022.
- Video lecture 17 from winter 2021.

- March 13/14:
- 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, SubsetSum.
- My notes.
- Three versions of lecture 18:
- Video lecture 18 from winter 2022.
- Video lecture 18 from winter 2022.
- Video lecture 18 from winter 2021.

- March 15/16:
- Examples of problems in NP: Hamilton Cycle, Traveling Salesman Problem, SubsetSum, Clique.
- Formal definitions of P and NP.
- My notes.
- Three versions of lecture 19:
- Video lecture 19 from winter 2022.
- Video lecture 19 from winter 2022.
- Video lecture 19 from winter 2021.

- March 20/21:
- Formal definitions of P and NP.
- P is contained in NP.
- P versus NP.
- Why decision (= YES/NO) problems? If we can decide HAM-CYCLE, then we can find a Hamilton cycle (if it exists).
- 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.
- Three versions of lecture 20:
- Video lecture 20 from winter 2022.
- Video lecture 20 from winter 2022.
- Video lecture 20 from winter 2021.

- March 22/23:
- Reductions.
- My notes.
- Three versions of lecture 21:
- Video lecture 21 from winter 2022.
- Video lecture 21 from winter 2022.
- Video lecture 21 from winter 2021.

- March 27/28:
- More reductions.
- Three versions of lecture 22:
- Video lecture 22 from winter 2022.
- Video lecture 22 from winter 2022.
- Video lecture 22 from winter 2021.

- March 29/30:
- Definition of a language being NP-complete.
- Some properties of polynomial-time reductions.
- My notes.
- Watch video lecture 22 again.

- April 3/4:
- Circuit-SAT is NP-complete.
- An example of the reduction.
- My notes, more notes.
- Video lectures:
- Video lecture 23 from winter 2022.
- Video lecture 23 from winter 2022.
- Video lecture 23 from winter 2021.
- Video lecture 24 from winter 2021.

- A list of NP-complete problems.

- April 5/6:
- Zero-knowledge proofs.
- My notes.
- I do not have a video for this.

- April 10/11: No lecture.