Algorithm Design, Analysis & Complexity, Winter 2017
Grades for assignment 3 have been posted to MarkUs. If you have a legitimate regrade request then you should submit it through MarkUs no later than April 20, 2017 by 8PM.
As some of you might know, I am the coach for our ACM ICPC teams. The programming contests that these teams participate in require you to solve short, but algorithmically and mathematically challenging problems. This upcoming Saturday, our programming team will be participating in the North American Invitational Programming Contest, but everyone is invited to participate in the open division.
The contest will be held in BA3175 from 12:30PM to 6:30PM. Thus, if you want to take a break from preparing for the finals and would like to participate in the open division, you need to act QUICKLY: you should register today or tomorrow by following these instructions.
If you are interested in the types of problems that you will be required to solve, you can check out these resources and references therein.
Posted information about the final. See tests webpage (it also has a link to past exams).
Please, fill out course and TA evaluations if you haven't done so already.
Assignment 3 solutions have been posted -- see assignments page.
Bring your laptops on Monday. If we have time at the end of the lecture we will do course evaluations.
TA evaluations are open. Please visit this website to evaluate your TAs this semester. The form allows students to select a course and then select from the list of TAs assigned to that course. Students are not restricted to evaluate only a single TA. This means that students who interact with a number of different TAs, may choose to comment on one or two that particularly comes to mind.
Note: the TAs running the tutorials are not necessarily the same ones grading your work. If you are evaluating a TA who did not grade your work, you should select N/A for the grading questions.
Grades for term test 2 have been posted to MarkUs. If you have a legitimate regrade request then you should submit it through MarkUs no later than April 1, 2017 by 8PM.
Grades for assignment 2 have been posted to MarkUs. If you have a legitimate regrade request then you should submit it through MarkUs no later than March 31, 2017 by 8PM.
Assignment 3 has been posted -- see assignments page. Have a look at it as early as possible, and start working on it. This assignment contains a couple of challenging problems, so I encourage you to not leave it until a few days before the deadline.
I have uploaded sample solutions for term test 2. See tests webpage.
Assignment 2 solutions posted -- see assignments page. Also, added Colin's notes for the previous regular tutorial. See course contents page. On the same page you will find some additional simplex practice problems.
Tests webpage has been updated with the information regarding the upcoming Term Test 2. Please, read it carefully.
I have been asked several times whether there is going to be a grade curve. The answer is yes! The curve will be applied at the end of the course, once I have all marks for all tests/exam/assignments. The final average for the course is going to be much higher than what you currently see for the test. Don't be discouraged by a low absolute mark for the first term test -- this course is difficult and historically test scores tend to be a bit lower than in many other courses. Concentrate on doing the best you can for the remainder of the term and you will be rewarded.
Posted sample solutions to term test 1 questions. See them on the tests webpage.
No office hours during the reading week.
Grades for term test 1 have been posted to MarkUs. If you have a legitimate regrade request then you should submit it through MarkUs no later than March 4, 2017 by 11am.
Grades for assignment 1 have been posted to MarkUs. If you have a legitimate regrade request then you should submit it through MarkUs no later than March 2, 2017 by 11am.
Assignment 2 has been posted. See "Assignments" webpage for details.
Correction for the lecture today. Reweighting procedure should be defined as c-tilde(u,v) = c(u,v) + h(u) - h(v). Then h(v) is defined as d(s,v) in the augmented graph, and by the optimality of d(s,.) we get d(s,v) <= d(s,u) + c(u,v). Thus c-tilde(u,v) = c(u,v) + h(u) - h(v) = c(u,v) + d(s,u) - d(s,v) >= 0. Note that in essence, it does not matter whether you define c-tilde(u,v) = c(u,v) + h(u) - h(v) or c-tilde'(u,v) = c(u,v) + h'(v) - h'(u), because you can always get one from another by setting h = -h', but it's important to be consistent. Apologies for the confusion that it might have caused.
I have added sample solutions for assignment 1 to Course Contents webpage.
Updated clarification for problem 5 assignment 1, runtime O(W^2 H^2 poly(n)) is acceptable. In general, when the question asks you to give an efficient algorithm it means that you should try to give as efficient algorithm as possible, but you won't be graded too harshly on the runtime as long as you avoid exponential time in the parameters. In contrast, if the problem specifies the desired runtime for a problem then you will be heavily penalized for not giving algorithm that is at least that efficient to the point of getting a grade of 0.
Added information about the upcoming first term test - location, aids allowed, material covered, test structure. See Term Tests page.
Course contents have been updated for January 30 and January 23. A writeup for the advanced tutorial on FFT (thanks, Eric!) and a writeup for the regular tutorial for January 23, 2017 (thanks, Colin!) have been added.
Tutorial structure and allocations have changed. See General Course Info page. There are two regular tutorials, as well as an advanced tutorial. Everyone is welcome to attend the advanced tutorial. The advanced tutorial is going to cover additional algorithms that might require a bit more background from students than the algorithms presented during lectures and regular tutorials. You are not required to know the material of the advanced tutorial for homework, tests, or exam. If you decide to attend the advanced tutorial you should still be aware of and know how to solve the problems covered during the regular tutorials.
IMPORTANT ANNOUNCEMENT FROM THE ACCESSIBILITY SERVICES:
Accessibility Services needs dependable volunteer note-takers to assist students living with a disability to achieve academic success!! Volunteers report that by giving to the U of T community their class attendance and note taking skills improve. All you have to do is attend classes regularly & submit them consistently.
Step 1: Register Online as a Volunteer Note-Taker at https://www.studentlife.utoronto.ca/accessibility/pcourselist.aspx
Step 2: Select your course and click Register
Step 3: Upload your notes after every class
Typed notes can be submitted online. Legible Hand-Written notes can be scanned at your home or at our office. Please see our office location and hours below.
Accessibility Services (Note-taking Program)
455 Spadina Avenue, 4th Floor Room 400
Office Hours: 9:00 AM-4:00 PM (Monday to Friday)
Daily Office closure 12:30 PM - 1:30 PM
Email us at as.notetaking@utoronto.ca or call 416-978-6186 if you have questions or require any assistance.
Volunteers may receive co-curricular credit or a certificate of appreciation.
Thank you for your support. See THIS PPT FILE for more info.
I suggest you read this article by the mathematician George Polya that appears in his book "How to Solve It." Think about an analogy between what this article describes and the difference between greedy and dynamic programming algorithmic paradigms.
Posted suggested exercises for week 2.
A clarification with regards to assignment 1: in problem 2 you may not hash images, the only way you may access images is through the comparison interface A[i]==A[j].
Assignment 1 has been posted. See "Assignments" webpage for details.
Updated tentative course schedule under Course Contents to reflect suggested readings (also see the new Q&A entry).
Updated Course Contents with suggested exercises for week 1.
Tutorials locations revealed - see General Course Info section. Next Monday please go to the tutorial room that you have been assigned. If you go to a different tutorial room, there might not be enough seating space. These allocations may change later in the course.
I added Q&A webpage. I will post answers to questions about the course there from time to time. Check it out.
No tutorial. Second lecture. See course contents webpage for description of the material covered.
First class! Description of the first lecture has been posted to Course Contents. It has a link to a writeup of the algorithm covered in the first lecture (and more). This is an exception rather than the rule - you should not expect lecture writeups in the future. Generally I will try to link relevant materials and mention relevant chapters of CLRS, but I do not guarantee that looking at Course Content page and links therein would replace attending lectures. Lectures are considered to be mandatory parts of the course.