Algorithm Design, Analysis & Complexity, Spring 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.
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.
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.
A final question on dynamic programming has been added to Assignment 1.
The bonus question has been posted in Assignments.
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.
The second assigbnemnt is now posted
For students in the evening section, please consider the following request from accessibility services .
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.
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.
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.
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.
We have added a note regarding question 2. The note may also be helpful in solving the question.
The first two questions of Assignment 3 have been posted. More to follow.
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.
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.
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: abborodin@gmail.com, 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.
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.
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.
~