Overview
Welcome to the course webpage for the Winter 2018 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 6) The solutions to Homework 3 are posted. Also, check the suggested exercises from the Williamson and Shmoys book.
- (Mar 24) A modification was made to Assignment 3: one assumption for Q1b was missing.
- (Mar 21) The solutions to Homework 2 are posted.
- (Mar 19) Additional exercises added to the Streaming and Linear Programming lecture notes. See the suggested exercises for details.
- (Mar 12) Midterm grades are available. The midterm will be graded out of 53. (7 points from Q1b, given for the correct lower bound, are considered bonus). You can see the solved midterm questions here.
- (Feb 27) Revise the material from the first six weeks of the course for the midterm. From the material on Streaming, focus on how to use Chebyshev and Markov's inequalities to analyze sampling algorithms. From the material on Markov Chains, focus on the definitions, and make sure you understand the Metropolis Hastings algorithm. You are allowed a two-sided handwritten aid sheet on the exam.
- (Feb 27) Suggested exercises for String Matching and Markov Chains are posted. Remember that there are also suggested exercises inside the lecture notes on other topics. The solutions to Homework 1 are also posted.
- (Feb 12) A linear algebra review sheet is posted.
- (Jan 31) Tomorrow's office hours will be shorter: from 11am to 12 noon. Please send me an email if this does not work for you and you want to see me.
- (Jan 31) Assignment 1 is available, and will be due on February 14.
- (Jan 23) Notes posted for last week's tutorial.
- (Jan 18) I have posted suggested exercises. Exercises for future topics will be posted there as well.
- (Jan 08) Look over the probability theory review sheet.
Contact information
Instructor/TA | Aleksandar Nikolov | Sepehr Abbasi Zadeh (TA) | Gregory Rosenthal (TA) |
---|---|---|---|
|
|
|
|
Office | Sandford Fleming 2301B | ||
Office Hours: | Thu 10am-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 | Bahen 1220 | Bahen 1220 |
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: 30%
- Midterm exam: 20%
- Final exam: 50%
The midterm exam will be one hour long, and will take place on March 2, 2018, in the tutorial time slot. 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/winter2018/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.