Instructor Information
Name: Nisarg Shah
Webpage: This Page
Email: firstname at cs.toronto.edu
Office: SF 2301C (do not drop by unless you have scheduled an in-person meeting with me)
Important Links
Course Page: This page!
Discussion Board: Piazza
Online Homework Submission: MarkUs
Course Delivery
All Zoom links use the same password, which has been emailed to all registered students and is available on Piazza.
All times are in Eastern time zone.
Tutorial divisions are by birth month: A = Jan-Apr, B = May-Aug, C = Sep-Dec
| Section | Meeting | Time | Delivery (Until Sep 23) | Delivery (From Sep 27) | Delivery (From Nov 15) |
|---|---|---|---|---|---|
| LEC 0101 | Lectures | Tue 1-3pm, Thu 2-3pm | Zoom Link | BA 1190 + Zoom Link | BA 1190 + Zoom Link |
| Tutorials | Mon 4-5pm | A: Zoom Link
B: Zoom Link C: Zoom Link |
A: BA 2195
B: BA 2185 C: ES B149 |
ES B149 | |
| LEC 0201 | Lectures | Tue 3-4pm, Thu 3-5pm | Zoom Link | KP 108 + Zoom Link | |
| Tutorials | Mon 4-5pm | A: Zoom Link
B: Zoom Link C: Zoom Link |
A: WB 119
B: BA 2135 C: BA B024 |
WB 119 | |
| BOTH SECTIONS | Office Hours | Tue 4:30-5:30pm, Thu 10-11am | Zoom Link | ||
Tutorial Format
A problem set will be released on the course web page prior to each tutorial. Students are encouraged to attempt the problems before coming to the tutorials. During the tutorials, the TAs will explain the problems and then go over key steps of the solutions.
Term Test Format
Term tests will likely be conducted in person on Mondays, 4-6pm ET (dates below).
For students who have a conflicting commitment on Mondays, 5-6pm ET, I may offer them to take the term test on the same day, 10am-12pm ET.
Note: If you have a regular commitment that conflicts with this timeslot, especially on the term test dates, you need to reach out to me and let me know by Sep 30. If you do not reach out by this date, I will only make an exception for medical or personal emergencies, at my discretion.
Grading Scheme
Best 3/4 Assignments: 30% (10% each)
2 Term Tests: 40% (20% each)
Embedded EthiCS Module: 5%
Final Exam / End-of-Term Test: 25%
Due Dates
Assignment 1: Oct 9
Assignment 2: Oct 30
Assignment 3: Nov 25
Assignment 4: Dec 8
Midterm 1: Oct 25
Midterm 2: Nov 22
Course Learning Goals
By the end of this course, you will be familiar with standard algorithm design techniques (divide and conquer, greedy algorithms, dynamic programming, network flow, linear programming, approximation, randomization), and understand the importance of computational complexity. More specifically, you will be able to:
- recognize algorithms and write new ones that employ each technique,
- prove correctness of such algorithms and analyze their efficiency,
- demonstrate membership in P and NP,
- show NP-completeness.
Textbook
The primary reference for this course will be the slides uploaded by the instructors. In addition, you should refer to the following textbooks. Readings from these books will be posted along with each lecture.
- Required: [CLRS] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms.
- Supplementary: [DPV] Dasgupta, Papadimitriou, Vazirani: Algorithms.
- Supplementary: [KT] Kleinberg; Tardos: Algorithm Design.
For information about assignments, exams, grading, and policies, refer to the course information sheet.