Overview
Welcome to the course webpage for the Winter 2019 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 23) Final office hours before the exam will be held 10-11am and 2pm-3pm on Wednesday, April 24. Check this webpage for information about the exam.
- (Apr 19) Midterm Solutions are posted.
- (Apr 8) The solutions to Homework Assignment 4 are posted. See this sheet with more general LP duals, and feel free to incorporate it into your exam aid sheet.
- (Mar 31) The last office hours before the end of classes will be tomorrow, Monday April 1, from 1pm to 3pm. Please contact me if you want to meet me outside of this window.
- (Mar 29) The solutions to Homework Assignment 3 are posted.
- (Mar 20) Homework Assignment 4 is posted.
- (Mar 17) Class is canceled this morning, since the Bahen building is closed. See you on Wednesday.
- (Mar 13) I have added a Further Reading section to the website. Check it out for surveys and research papers related to the course material.
- (Mar 6) The solutions to Homework Assignment 2 are posted, and Homework Assignment 3 is posted.
- (Feb 22) There will be extra office hours on Monday Feb 25, from 1:30pm to 3:30pm. As usual, I also try to be available by appointment.
- (Feb 22) For the midterm exam, you are allowed a handwritten Aid Sheet taking one side of an A4 or US Letter page.
- (Feb 20) Here are some topics to focus on for the Midterm, which is on Monday, in the usual time and place:
- The Contraction algorithm for Min-Cut;
- Locality Sensitive Hashing;
- Sampling, Variance, Chebyshev's inequality;
- Markov chain basics: transition matrix, aperiodic and irreducible Markov chains, stationary distribution.
- (Feb 13) Homework Assignment 2 is posted.
- (Feb 8) Solutions posted for Homework Assignment 1.
- (Feb 6) Added the lecture notes on Random Walks and Markov Chains.
- (Feb 4) This is a reminder that there will be office hours from 1pm to 3pm in SF2301B today, Monday Feb 4. Moreover, please look over the Linear Algebra review sheet in preparation for the material on Markov Chains.
- (Jan 23) The lecture notes on Approximate Near Neighbor Search have been updated.
- (Jan 23) Homework Assignment 1 is posted. Check your email for the password.
- (Jan 07) 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: | Thu 2pm-4pm, 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 | Bahen 1170 | Bahen 1170 |
Time | Monday and Wednesday 11am - 12pm | Friday 11am - 12pm |
Grading Scheme
Your mark for the class will be based on the following components:
- Homework assignments: 32%
- Midterm exam: 20%
- Final exam: 48%
The midterm exam will be one hour long, and will take place on February 25, 2019, in the usual lecture 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.
Piazza
The link to sign up for our Piazza forum
is piazza.com/utoronto.ca/winter2019/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.