Algorithm Design, Analysis & Complexity, Spring 2020

January 6, 2020

Slides for the weekly lectures will be posted to Course Contents. It has a link to the lecture slides (and more). Generally I will try to link relevant materials and mention relevant chapters of CLRS, KT and DPV, but the Course Content page and links therein do not replace attending lectures. Lectures and Tutorials are considered to be mandatory parts of the course.

January 13, 2020

You can enrol as a student on piazza. This is not mandatory but we think you will find it useful. You are welcome to reply to questions/comments submitted by other students as well as posting your own questions/comments. You are welcome to submit assignments by yourself in groups of 2 (preferably) or 3. Once a group is formed you are committed to submitting as a group and cannot change your group. Tutorials begin this week. Important Here is the assignment of students to tutorial rooms. The assignment is according to the day of the month in which you were born. For Monday (16:00-17:00): RW110 (birthday 1-10), SS1072 (birthday 11-20), SS2125 (birthday 21-31). For Monday (17:00-18:00): BA1180 (birthday 1-10), RW142 (birthday 11-20), LM157 (birthday 21-31).

Assignment 1 has now been posted. Since i am told that there is only one markus file for all of CSC373, you can form a group with students from another section. But again, we advise 2 per group and a max of 3.

January 20, 2020

Some small changes/clarifications with respect to Assignment 1:

In question 2, polynomial inputs and outputs are given in terms of their coefficients. Part (a) have been reworded to hopefully make it clearer.

In question 3, we changed  "i < j " to "i less than or equal jn".

Rewording of question 4, part b. In your example for a 3-colorable graph G such that the greedy algorithm does not optimally colour G, you can order the vertices in any way which then fixes the way the bgraph is coloured.

January 24, 2020

Here is a link to Markus.
  • markus link
  • A final question on dynamic programming has been added to Assignment 1.

    The bonus question has been posted in Assignments.

    February 2, 2020

    Tomorrows tutorial will be conducted in the ``invertted classroom'' format. All students will go to one location Monday, February 3 (RW110 for the 4-5 section and BA1180 for the 5-6 section). Students can work on their assignment or other course material individually or in groups and call one of the TAs if they need to ask questions. However, the TAs will only comment on your work and not solve any questions for you. There will also be an additional dynmaic programming question for everyone to work on.

    Reminder: The first assignment is due this coming Thursday, February 6 at 4:59. Markus is unforgiving about submission deadlines and we strongly suggest submitting in advance.

    February 13, 2020

    The second assigbnemnt is now posted

    For students in the evening section, please consider the following request from accessibility services .

    February 14, 2020

    The second quiz will be held on Feb 24 during tutorials. The topics include dynamic programming, and flow networks. Please go to the rooms and at the time that you attended during your last quiz (unless there is a good reason not to do so).

    During the quiz no cell phones are allowed. 4-5 students are not allowed to leave the quiz before the TAs collects all quizzes. For the students in the 5-6 tutorial no late arrivals are accepted, so if anyone misses the start time, they will not be allowed to write the quiz and will lose it completely.

    February 16, 2020

    There is a rewording of the flow question to make it easier to answer. You can copy and post marked up copies of the given flow network to document what is happending during each iteration of the Ford Fulerson algorithm.

    During reading week, we will not have the usual office hours. Allan Borodin will not be available and Sara Rahmati will be available on Friday but you need to cnfirm a time with her. If there is a demand for another office hour we will try to orgamize a TA office hour.

    February 17, 2020

    Question 2 has been reworded.

    On Friday, Feb 21, Sara Rahmati's office hour will start at the usual time (5 pm) but only this once, the location will be BA7172.