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

    In Assignment 2, Questions 1 and 2 have 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.

    February 24, 2020

    For the week of February 24, Allan Borodin will not have an office hour on Monday, the 24th. Instead there will be the usual office hour Wednesday, 4:30-5:30 and additional hour on Friday, 1:30-2:30. Sara Rahmati will have her usuall office hours. We are trying to organize one or two additional TA office hours and will post that infiormation when it becomes available

    Lecture slides for this week will be posted today but they are probably covering more materail than we will discuss. The slides will be updated at the end of the week to reflect what has been discussed in class.

    Quiz today at end of 4-5 hour and at start of 5-6 hour.

    February 25, 2020

  • Important - Midterm test will be held on March 2 as it was planned:
    • CSC373H1 L0101/2003 (day section):
    • Time: 02-MAR-20, 16:00 18:00
    • Location: Exam Centre, Rooms EX300 and EX320
      CSC373H1S L5101 (evening section):
    • Time: 02-MAR-20, 17:00 19:00
    • Location: Bahen Centre, Room BA1130

  • Midterm test will cover divide and conquer, greedy algorithms, dynamic programming, and flow networks.
  • March 2, 2020

    We have added a note regarding question 2. The note may also be helpful in solving the question.

    March 7, 2020

  • Important - Change in location of tutorials on March 9, 2020
    • 4-5 pm:
    • RW110 : birthdays 1-15
    • SS1072: birthdays 16-31
      5-6 pm:
    • RW142 : birthdays 1-15
    • BA1180: birthdays 16-31

    March 8, 2020

    The first two questions of Assignment 3 have been posted. More to follow.

    March 12, 2020

    The university is considering contingency plans to respond to the COVID-19 epidemic. As of now the University remains open and we are all asked to prepare plans should the University need to close. We plan to continue to hold lectures but will follow all instructions from the University. We understand that some students may feel uncomfortable about attending classes. As you know, lecture slides are available for those wishing not to attend class. In addition, we will try to be as available as possible for Skype calls in addition to our regular office hours and usual communication on Piazza.

    March 13, 2020

    As you probably now know, the University has cancelled all classes starting this coming Monday until April 3. The quiz scheduled for this coming Monday is therefore cancelled. Assignment 3 should still be submtted on time via Markus. Decisions about the final exam will be made by the University, We will be following their advice and instructions in all matters (including grading) as they are become known.

    March 15, 2020

    For the rest of the term, we will be posting lecture slides (as usual). However, we cannot stop to respond to questions nor can we add additional comments as we discuss the material.

    Both Allan Borodin and Sara Rahmati will hold office hours remotely (by skype) during the regular office hour times (Allan: Mondays 1:30-2:30 and Wednesdays 4:30-5:30; Sara: 5-6 pm Fridays) as well as additional skype meetings upon request. Skype addresses:, sara.rhmt. In order to schedule meetings during the regular office hours with Allan Borodin, please request a 10-15 minute time slot. To arrange Skype meetings with Sara Rahmati, please send her an email with title "CSC373 - office hour meeting request" at the latest one hour before regular office hours. For meeting her out of regular office hours entitle your email as "CSC373 - meeting request". We will try to meet all requests at some time. We will try to schedule some remote TA office hours.

    Mainly keep well. Study but get enough sleep.

    March 15, 10:30PM, 2020

    Clearly things are changing rapidly regarding how the A&S Faculty and the University are responding to COVID-19 issues regarding classes, exams and grading. We are still evaluating how best to proceed and will be taking advice from colleagues. As far as we know the University has not cancelled final exams while the Faculty has indicated that students need not return to campus. The DCS department is exploring the use of live stream lectures (using zoom). This will not be possible for Mondays lecture but may be available for the Wednesday 6-9 PM lecture which all students are welcome to attend IF we can get this organized. We will be adding questions for assignment 3. Many options are avaialble as to how to adapt the grading scheme in response to the events. Please be assured we fully understand your concerns about how grades will be determnined. We will keep you posted on this web page and piazza so please keep tuned.

    March 18, 2020

  • Given all the changes announced by the department and the faculty, we decided to merge day and evening section this week and hold the class on Wed 6-9 pm online. All day and evening CSC373 students should have received an email this morning about the details on how to join this online session . If you have not received the email please leave your email address under post @201 on Piazza and we will forward you these information once more.The recording will be available later for those who cannot attend the online class. Depending on the outcome of this experience we may separate the day and evening section starting Monday and hold classes at their regular times, or, we may continue with merged online classes, in which case we will use day sections lecture times for additional office hours and possibly tutorials; students of both sections will be very welcome to attend.
  • Although the deadline for remark request for graded work is usually one week after releasing the grades, considering the current unusual circumstances , we decided to extend the deadline for remark request for the midterm until March 29, 11:59 pm. Please try requesting for remarks only for questions you feel there has been a major mistake in grading your solution. Considering that our TAs, similar to everyone else, are affected by the unusual conditions, we will recommend them to consider major remark requests prior to negligible ones.
  • We highly encourage our students to, at this time, shift their focus from midterm to more important matters. First and foremost we recommend you to focus on finding the best ways to deal with the stress which is normal under the current uncertain conditions. Do not feel bad if you cannot study as efficiently as you used to as it is very normal. Take enough breaks to exercise, meditate, or do anything else that can help you reduce stress. Keep in touch with your friends and colleagues through online media. Remember, feeling unusual these days is normal, so do not feel bad sharing your feelings and concerns with others or asking for help. As for the course, try to, instead of thinking about the midterm results, focusing on learning the course material well and getting remaining course work done the best way you can. We want to reassure you that the CSC373 teaching team is doing their best to come up with an efficient and fair alternative plan for the rest of the term and for evaluation. We will announce you the details and put major changes to vote.
  • Please keep visiting this page frequently.
  • Information you need to join this online session . Passcode to the file is the passcode you use to access Sara Rahmati's lecture notes.
  • March 23, 2020

  • Sara Rahmati will hold her 11 am class today. Please notice that the information to join day sessions are different than the information for joining evening sessions.
  • Update: Information you need to join both day and evening section online classes . Passcode to the file is the passcode you use to access Sara Rahmati's lecture notes.
  • March 26, 2020

    More than half of the students registered in CSC373H1S (62% of the voters) approved the proposed grading scheme. We will update the grading scheme on the webpage later today. Assignment A4 has been posted. There may be one additional question.