Overview
Welcome to the course webpage for the Winter 2020 term of CSC473, Advanced Algorithms. Here is the course content:
Advanced algorithm design techniques, with emphasis on the role that geometry, approximation, randomization, and parallelism play in modern algorithms. Examples will be drawn from linear programming; randomized algorithms; streaming algorithms and parallel algorithms in the Map-Reduce model.
This is a theoretical and advanced course. While we will cover algorithmic techniques useful in practice, our focus will be on proofs, theoretical analysis, and creative problem solving. Mathematical maturity, and a strong background in probability theory, linear algebra, data structures, and algorithm design are all essential.
Prerequisites for the course:
- CSC373
- MAT221H1/MAT223H1/MAT240H1
Make sure to read and understand the course information sheet. Check this website and Piazza frequently to make sure you receive any course announcements. Check the Lectures page for the required reading.
Announcements
- (Apr 10) Solutions have been added to Assignment 4. Thank you all for a great course under unusual (to put it mildly) circumstances.
- (Apr 4) Solutions have been added to Assignment 3.
- (Mar 30) Tomorrow office hours will be only 11am-12pm. I will also be available on Friday, April 3, 11am-12pm, and on Tuesday, April 7, 10-12pm.
- (Mar 23) The proposal for reweighting the marking scheme has passed (there is an hour more left to vote, but more than half the students registered votes "yes" already). The marking scheme and deadlines are now updated.
- (Mar 19) Assignment 4 is out.
- (Mar 18) Please go to Quercus to vote on the proposed new marking scheme for the course (each of the four assignments worth 20% of the course, and the midterm worth 20%, as well). You have until noon on March 23. Additionally, I am proposing to extend the deadline for A3 until March 27, and the deadline for A4 until April 10.
- (Mar 16) Slides for today's lecture are posted.
- (Mar 15) The Assignment 3 deadline is extended until Monday, March 23, at midnight. Assignment 4 will still come out on March 19 and be due on April 2, as originally scheduled.
- (Mar 15) We will have the rest of the lectures and office hours online. For now, we will try to use Bb Collaborate from Quercus. Lectures will happen at the usual class time, and will be recorded and available to view from Quercus. We will still use this website and Piazza for announcements and homeworks. Please log into Quercus to view the first online lecture this Monday.
- (Mar 13) Per this announcement, in-person classes are now cancelled. Stay tuned for more information regarding how we will continue the class for the next three weeks.
- (Mar 13) Midterm grades are posted on MarkUs, and the midterm solutions are here. Please see Piazza for some additional remarks about it.
- (Mar 5) Assignment 3 is out.
- (Mar 6) Solutions have been added to Assignment 2.
- (Mar 1) I have corrected a mistake in Assignment 2: the running time requirement for Q1 was too strict. I apologize for any wasted time on this! I have given one more day to complete A2, and the deadline is now midnight on March 3.
- (Feb 24) The 2018 and 2019 midterms are posted for practice. The midterm will cover the first six weeks of class. You are allowed one handwritten two-sided aid sheet. When reviewing, you can focus on:
- The Contraction algorithm and its analysis;
- Locality sensitive hashing;
- Sampling, Variance, and Chebyshev's inequality.
- (Feb 21) As a result of the vote last week, the midterm is moved to March 6, and the deadline for A2 is moved to March 2. Moreover, A2 is updated with a clarification on Question 1.
- (Feb 13) Assignment 2 is out.
- (Feb 12) Solutions have been added to Assignment 1.
- (Jan 27) I have posted a correction to Assignment 1. Intially Question 1a asked about the probability that an edge of the cut is contracted, while it should have asked for the probability that no edge of the cut is contracted. I also reworded the question to remove some possible ambiguities.
- (Jan 23) Assignment 1 is out. Check your email for the username and password to access it.
- (Jan 13) There are no office hours this week. Also, the Karger-Stein notes have been updated.
- (Jan 06) Look over the probability theory review sheet. Attempt the problems: if you struggle with them, you should review your probability theory as soon as possible.
Contact information
| Instructor/TA | Aleksandar Nikolov | Calum MacRury (TA) | Lily Li (TA) |
|---|---|---|---|
| |
|
|
|
| Office | Sandford Fleming 2301B | ||
| Office Hours: | Tuesdays 10am-12 noon, or by appointment | N/A | N/A |
Prof. Nikolov will attempt to respond to legitimate email inquiries from students within 48 hours. Please include "CSC473" in the subject line of the email.
Where and When
| Type | Lecture | Tutorial |
|---|---|---|
| Room | Earth Sciences B142 | Earth Sciences B142 |
| Time | Monday and Wednesday 11am - 12pm | Friday 11am - 12pm |
Piazza
The link to sign up for our Piazza forum
is piazza.com/utoronto.ca/winter2020/csc473/home.
Piazza is a third-party software. It will be used in this
class strictly as a discussion board. When posting, abide by
the academic integrity policy. In particular, do not
post solutions to homework problems. Make sure to
read the Piazza terms of use before signing up, and if you
have any concerns, contact the instructor directly. If you
decide to participate in Piazza, only provide content that you
are comfortable sharing under the terms of the Privacy Policy
and Terms of Use.
When using Piazza, be respectful to your instructors and fellow students. Offensive language and threatening behavior will not be tolerated. Keep in mind that when posting "anonymously", you are anonymous only to other students, but not to the instructors.
Grading Scheme
Your mark for the class will be based on the following components:
- Homework assignments: 80%
- Midterm exam: 20%
The midterm exam will be one hour long, and will take place on March 6, 2020, in the usual tutorial time slot and room. It will cover all the material in the first six weeks of the course.
You need to score at least 40% on the final exam to pass the course.
Academic Integrity
Every student must abide by the University of Toronto academic integrity policy, and the Code of Student Conduct. Academic misconduct is taken very seriously! See the Homeworks page for information about what resources you are allowed to use when working on your assignments.