University of Toronto, Department of Computer Science
CSC373H Algorithm Design & Analysis
Summer 2012


Students should consult this page at least once a week and check for new announcements.


Course Info

Instructor
Name: Siavosh Benabbas
Email: csc373 AT cs DOT toronto DOT edu
Office: 10 King's College Road, Sandford Flemming Bulding, Room 4306A
Teaching Assistants:
Names: Jackie Cheung, Sergey Gorbunov, Dai Le, Robere Robert
Lectures
Tuesdays 6PM-7PM at WI1017 BA1220
Thursdays 6PM-8PM at BA1170
Tutorials
When: Tuesdays 7PM-8PM
Where: BA2165 (last names A-J), BA2175 (last names K-Z)
Where: BA2165 (last names A-D), BA2175 (last names E-M), BA2159 (last names N-Z)
Office Hours
When: Tuesdays and Thursdays 4:30PM-5:30PM
Where: SF 4306A
or email the instructor for an appointment.
Notes
Notes from Allan Jepson's offering of the same course in the spring can be found here:http://www.cs.toronto.edu/~jepson/csc373/ (ask for the password in class)
I do not have the copyright for these and they are password protected. Please do not distribute them.
Course Website
http://www.cs.toronto.edu/~siavosh/csc373h/
Course Forum
https://csc.cdf.toronto.edu/mybb/forumdisplay.php?fid=21
The course forum is not monitored by the instructor or teaching assistants.
Textbook
T. H. Cormen; C. E. Leiserson; R. L. Rivest; C. Stein, Introduction to Algorithms, 3nd Edition, 2009.
(The library has the 2nd version of the book which is essentially the same as an "electronic resource" here. You can log in with your UTORid and use it free of charge.)
References
S. Dasgupta; C. H. Papadimitriou; U. Vazirani, Algorithms, 2006.
This is not the main reference for the course but you might find it easier to read than Cormen et. al.
Course Description (Taken from the undergraduate handbook)

Standard algorithm design techniques: Greedy strategies, dynamic programming, network flows, linear programming, network flows and some randomized and approximation algorithms time permitting. Brief introduction to NP-completeness: polynomial time reductions, examples of various NP-complete problems, self-reducibility.

Students will be expected to show good design principles and adequate skills at reasoning about the correctness and complexity of algorithms.

Prerequisites

Prerequisite: CSC263H1/CSC265H1/CSC378H1; CGPA 3.0/ enrolment in a CSC subject POSt.

In general if you did well in CSC263/CSC265 you should be all set. Here is a list of a few concepts we use again and again during the course: (ordered from the most important to the least)

  • Asymptotic notation: O(), \Theta(), etc.
  • (Asymptotically) Solving recurrence relations, Master Theorem etc.
  • Proving an algorithm correct: Induction, etc.
  • Computing the asymptotic (worst case) runtime of algorithms.
  • Your standard data structures: Heaps, BSTs, Disjoint Sets, etc.
  • Your standard algorithms from Data Structures course: Binary Search, Sorting, etc.
  • Your standard discrete math definitions: Graphs, etc.
  • Basic counting: Binomials, Inclusion/Exclusion, etc.
  • A little bit of discrete probability: Expectation, Linearity of Expectation, etc.
  • A little bit of programming: C/C++ or Java preferably but Python might do

There will be some programming assignments. You don't need any Object Oriented or other fancy stuff but you need to be able to write code that compiles and solves simple math problems reading input from standard input, writing output to standard output.

Finally, I have prepared a list of questions (Homework 0 if you will) to test yourself on the above material. Keep in mind that some of the questions on the list are pretty hard and you definitely don't need to be able to solve them all. You can download it from here: pre.pdf

Course Contents
Marking Scheme
Date Topic Sample material Deadlines?
May 15th Course Intro
May 17th Greedy Algorithms Minimizing Avg. Finishing Time, Interval Scheduling
May 22nd Greedy Algorithms Interval Coloring (Tutorial Notes)
May 24th Greedy Algorithms Charging Arguments and Approx. Alg. for JISP, Intro. to MST
May 29th Greedy Algorithms CLRS Ch. 23:Prim's Alg. (Tutorial Notes)
May 31st Dynamic Programming Prim's Alg. continued, Rod cutting CLRS Sec. 15.1
June 5th Dynamic Programming Rod cutting CLRS Sec. 15.1 (Tutorial Notes) Assignment 1 due.
June 7th Dynamic Programming Interval Scheduling with profits
June 12th CLRS Sec. 32.2: Robin-Karp String Matching Term Test 1.
June 14th Dynamic Programming Collecting Coins going up and right
June 19th Dunamic Programming Longest Common Subsequence (Tutorial Notes)
June 21st Network Flow CLRS Sec. 26.1 and 26.2: The Ford-Fulkerson Method
June 26th Reading week: No class
June 28th Reading week: No class
July 3rd Network Flow CLRS Sec. 26.2 and 26.3: FF Method and Bipartite Matching (Tutorial Notes) Assignment 2 due.
July 5th Network Flow CLRS Problem 26-1: Escape problem
July 10nd Network Flow CLRS Problem 26-1: Escape problem Term Test 2.
July 12th Network Flow CLRS Problem 26-3: Algorithmic consulting (Experts and Projects) Programming Assignment 1 due.
July 17th Linear Programming CLRS (Intro. of) Chap. 29: Intro. to LPs, Sec. 29.2: MaxFlow as an LP (Tutorial Notes)
July 19st Linear Programming More applications of Linear Programming
July 22nd Last day to drop the course from academic record and GPA.
July 24th NP-Completeness CLRS (Intro. of) Chap 34 and Section 34.1: Intro., Encoding and input length, class P (Tutorial Notes) Assignment 3 due.
July 26st NP-Completeness CLRS Sections 34.1 and 34.2: Classes P and NP
July 31st NP-Completeness CLRS Section 34.2: C-SAT is in NP Term Test3.
August 2nd NP-Completeness CLRS Section 34.3: Reductions and NP-hardness, C-SAT is NP-complete
August 7th NP-Completeness CLRS Section 34.3: 3-SAT is NP-complete (Tutorial Notes)
August 9th NP-Completeness Programming Assignment 2 due.
Marking Scheme
Marking Scheme
Title Points Notes
Assignments 3, 4% each

Programming Assignment 2, 4% each

See the description below.

Term Tests 3, 45% in total

Each Term Test follows an assignment and is very similar to it.

Final Exam 35%
Course Information Sheet
infosheet.pdf

General Remarks

  • Email is the preferred way to contact the instructor and the teaching assistant. Feel free to email the instructor regarding any course related issues. Questions by email are also welcome. We will try to answer your emails in 3 working days.
  • Please use informative subject lines for your emails, e.g. "A question about NP-Completeness" or "Clarification for assignment 1".

Announcements

August 30th, 2012
Solutions to (non-programming) assignments removed as requested by the fall term instructor. Email me if you are not in that class and want the solutions.
August 21st, 2012
The final marks have been submitted for approval to the chair's office. I wanted to thank the tutors for doing a great job and all of you guys for a being a terrific audience!
August 12th, 2012
Solutions to Programming Assignment 1 are posted: PA2sol.cc PA2sol.java. Both these solutions are fast enough to get full marks but a faster C++ solution (which uses an algorithmic optimization) is also available PA2sol-fast.cc that runs 5x fasters. Read the new marker's comments file for the idea.
August 12th, 2012
Programming Assignment 2 has been marked. The test cases are posted here, the marker's comments here. The mark distribution can be seen here. To get a copy of your ``detailed report'' (which contains your mark) run ``cp /u/csc373h/summer/pub/PA2logfiles/[your user name].txt ~/PA2-report.txt'' on a CDF machine.
August 11th, 2012
If you have any remarking requests for Assignment or Term Test 3 the TA who marked them will hold an office hour on Tuesday August 14th 5-7PM. This is exclusively for remarking requests. If you have any questions regarding course material you can ask them in the office hour held on Monday.
If you can not make this office hour you should send your written remarking requests to me by email no later than August 18th.
August 10th, 2012
Term Test 3 has been marked; you can pick up your paper Monday at office hours. The average was 22 out of 30; also take a look at the mark distribution and the marker's comments.
August 9th, 2012
Some information about the final exam has been added to the relevant section of this website.
August 9th, 2012
There will be an extra office hour on August 13th 5-6PM. There will NOT be any office hours that week on Tuesday or Thursday (except for remarking requests.)
August 7th, 2012
Assignment 3 has been marked; you can pick up your paper at office hours. The average was 11.8 out of 16; also take a look at the mark distribution and the marker's comments.
August 2nd, 2012
Reminder: If you want to talk the TA who marked Assignment and Term Test 2 he will hold office hours today 4:30-5:30 at SF4302 (the usual place I hold my office hours). If you have remarking requests but you can't make it to these office hours you should submit your requests by email to me no later than August 5th.
August 1st, 2012
The mark distribution for Programming Assignment 1 can be seen here. Also, you can get a copy of your ``detailed report'' by doing ``cp /u/csc373h/summer/pub/PA1logfiles/[your user name].txt ~/'' on the CDF machines.
July 31th, 2012
Programming Assignment 1 has been marked. The test cases are posted here, the marker's comments here. You can come to the office hour to pick up the ``detailed report'' of how your program did on each test cases.
July 30th, 2012
Programming Assignment 2 is posted: PA2.pdf. Make sure you check the website for corrections/clarifications.
July 29th, 2012
There will be an extra office hour Monday July 30th 4:30-5:30.
July 29th, 2012
The main idea of the solutions for questions in Assignment 3 are posted:A3sol.pdf.
July 25th, 2012
If you want to talk the TA who marked Assignment and Term Test 2 he will hold office hours Wednesday August 1st 6:00-7:00 and Thursday August 2nd 4:30-5:30 in SF4302 (where we hold office hours.) If you have remarking requests but you can't make it to these office hours you should submit your requests by email to me no later than August 5th.
July 21th, 2012
Assignment 3 has been updated to version 1.2. Examples of question 1 as well as some typos are corrected. A3.pdf
July 20th, 2012
Term Test 2 has been marked; you can pick up your paper in class or at office hours. The average was 21.5 out of 30; also take a look at the mark distribution and the marker's comments.
July 18th, 2012
Assignment 3 is posted: A3.pdf. The deadline is next week but this assignment is shorter and easier than the previous one.
July 18th, 2012
A C++ solution to Programming Assignment 1 is posted: PA1sol.cc.
July 17th, 2012
Reminder: If you want to talk the TA who marked Assignment and Term Test 1 he will hold office hours today 4:30-5:30 and tomorrow 6:00-7:00 at SF4302 (the usual place I hold my office hours). If you have remarking requests but you can't make it to these office hours you should submit your requests by email to me no later than July 22nd.
July 8th, 2012
There was a typo in the solution of question 1 in the assignment "D[0][j]=1 for ..." should have been "D[0][j]=0 for ...". The A2sol.pdf file has been updated to version 1.1
July 6th, 2012
The main idea of the solutions for questions in Assignment 2 are posted:A2sol.pdf.
July 6th, 2012
If you want to talk the TA who marked Assignment and Term Test 1 he will hold office hours Tuesday July 17th 4:30-5:30 and Wednesday July 18th 6:00-7:00. The place will be assigned shortly. If you have remarking requests but you can't make it to these office hours you should submit your requests by email.
July 6th, 2012
There will be an extra office hour Monday July 9th 4:30-5:30.
July 5th, 2012
Assignment 2 has been updated. A sentence in Question 1 is reworded to make the announcement of June 26th more clear. A typo in Question 2 is corrected. You can "drive" the truck not "drop" it.
July 4th, 2012
Term Test 1 will be marked out of 27 instead of 36. So if you got 27 on the test you will get the full percentage in your final mark.
July 4th, 2012
The deadline for PA1 is postponed to July 12th. Sample C++ and java solutions have been uploaded as well. Make sure you look at these specially if you are submitting your program in java. It is important that your program can be run with the commands discussed below.
June 28, 2012
TT1 is marked. The marker's comments are here:TT1mr.txt
June 26, 2012
For Question 1 of Assignment 2: The correct interpretation of the sentence "calculates the number of valid programs of length n modulo p." is "Calculate (the number of valid programs of length n) modulo p", not "calculates the number of valid programs of length (n modulo p)."
June 26, 2012
The marking of Term Test 1 is almost done. You can pick up your term test during the office hour on Thursday, June 28th.
June 26, 2012
There will be no office hour today as this is the reading week. There will be an office hour on Thursdaa,y June 28th.
June 24, 2012
Assignment 2 and Programming Assignment 1 are updated to version 1.2. Some typos have been fixed, the required runtime of the algorithms are clarified and Assignment 1 now has a second question.
June 24, 2012
First version of Assignment 2 is posted: A2.pdf. The second question is not done yet. Make sure you check the website for the next version which will have Question 2.
June 23, 2012
Programming Assignment 1 is posted: PA1.pdf. Make sure you check the website for corrections/clarifications.
June 19, 2012
Assignment 1 has been marked; you can pick up your assignment in class or at office hours. The average was 5.6 out of 9; also take a look at the mark distribution and the marker's comments.
There were many (around 10) assignment submitted electronically which did not have names. We went through the files and figured out the names this time but make sure the PDF file you submit can be viewed on linux (has all fonts embedded) and has your name and student number for the next assignment.
Also, we are back to 3 tutorial sections.
June 14, 2012
Term Test 1 has been posted:TT1.pdf
June 11, 2012
There will be an extra office hour today, Monday June 11th, 5:00-6:30 at my office (SF4306A.)
June 8, 2012
I was asked by the Accessibility Services to post the following announcement. There is a student in this class who requires a volunteer notetaker as an accommodation for a disability. By signing up and posting your notes, you can make a significant difference for this individual's capacity to fully participate in this course. Go to: http://www.studentlife.utoronto.ca/accessibility/pcourselist.aspx or come in person to Accessibility Services 215 Huron St. Suite 939. Many students notice the quality of their notetaking improves through volunteering. You will also receive a certificate of recognition.
June 5, 2012
Due to unforeseen problems we will have 2 tutorials this week. Last names A-J will go to BA2165, K-Z to BA2175. We will have 3 tutorials starting from next week.
June 4, 2012
We now have 3 tutorials so the name-tutorial assignment has changed. Last names A-D will now go to BA2165, E-M to BA2175, and N-Z to BA2159.
June 3, 2012
If you need it for assignment 1 you can assume that Prim runs in time O(e + v log v) where e is the number of edges in the graph and v is the number of vertices. Also, for none of the questions you need to prove that your algorithm is the fastest possible algorithm but for all of them you need to do a runtime analysis of your algorithm.
June 2, 2012
Assignment 1 is updated to version 1.5 to clarify Question 1 and add an example. What you are asked to do is come up with an algorithm that solves this problem.
May 28, 2012
Assignment 1 is updated to version 1.3 to fix two typos in the example for Question 4 and add the 10cent coin in Question 3.
May 28, 2012
Assignment 1 is posted: A1.pdf
May 23, 2012
The Tuesday classes are now moved to BA1220. The Thursday classes are still at BA1170.
May 22, 2012
A link to last term notes has been posted. Ask me for the password in class.
May 16, 2012
Starting May 22nd the Help Centre opens for Summer sessions. Their hours are Monday to Thursdays 2-4pm. Treat these like extra office hours. The stuff are not affiliated with the course so they can't help you with questions that are administrative in nature but they can help you with the material.
May 2, 2012
Course starts on May 15th.
Students should check this page regularly (at least once a week) for new announcements.

Assignments (12%)

Assignments should be handed at the start of the class on Tuesdays (before 6:10PM). Late assignments are NOT accepted except the following. On any assignment you can choose to type your assignment and submit the PDF electronically no later than the start of the class on Thursday. That is you get two free grace days if you type your assignment. The submission should be on cslab using the standard submission tools and the deadline is enforced by a computer program (no exceptions.) If you submit the same assignment both on Tuesday and then electronically before Thursday only your later submission counts. Other than this exception no late assignments are accepted.

The recommended way of typing your assignment is using LaTeX. This is a good skill to pick up and there will be a sample LaTeX file provided.

The assignment can always be solved in 5 pages if you are writing significantly more you are either (a) on the wrong track (b) delving in too much detail.

Assignment 1 (4%)
Due: Tuesday, June 5th, 6:00PM (Electronic submissions due June 7th, 6PM)
Electronic submissions: Use CDF submit command. Assignment name is A1. File name should be A1sol.pdf
Questions: A1.pdf
LaTeX file: A1temp.tex
Mark distribution: a1_marks.png
Marker's Remarks: A1mr.txt
Assignment 2 (4%)
Due: Tuesday, July 3rd, 6:00PM (Electronic submissions due July 5th, 6PM)
Electronic submissions: Use CDF submit command. Assignment name is A2. File name should be A2sol.pdf
Questions: A2.pdf
LaTeX file: A2temp.tex
Main ideas for the solutions: Removed. Email the instructor. A2sol.pdf
Mark distribution: a2_marks.png
Marker's Remarks: A2mr.txt
Assignment 3 (4%)
Due: Tuesday, July 24th, 6:00PM (Electronic submissions due July 26th, 6PM)
Electronic submissions: Use CDF submit command. Assignment name is A3. File name should be A3sol.pdf
Questions: A3.pdf
LaTeX file: A3temp.tex
Main ideas for the solutions: Removed. Email the instructor. A3sol.pdf
Mark distribution: a3_marks.png
Marker's Remarks: A3mr.txt

Programming Assignments (8%)

Each programming assignment will describe an algorithmic task to be solved, the precise format of input and output and an allowed runtime. Any submission that:

  • does not compile,
  • produces a runtime error,
  • does not adhere to the precise input/output format,

will not get any marks. Marks are earned based on passing (producing correct answer for) 20 test cases. For each test case that your program produces the correct output in the allocated runtime you get 5% of the assignment's mark.

You are free to write your answers in Python, Java, or C/C++ but be warned that Python programs might be at a disadvantage in terms of speed.

The runtime limit of the problem is there to test if you have implemented the fastest algorithm for the problem and is designed to be tight. A suboptimal algorithm, or a particularly poor implementation is not supposed to pass all the tests. (But if you can't figure out or implement the fastest algorithm feel free to submit a slower implementation; you will get the marks from the easier test cases.)

Java submissions are run using the following two commands. First we run "javac PA1sol.java" to compile your submission. Then we run "java PA1sol" (in the linux shell) to run it. We will NOT run the submissions in the NetBeans shell or anything like that. Look at the PA1sol.java file below to see an example of how to read input/write output and how to make your program runable with those instructions.

Programming Assignment 1 (4%)
Due: Thursday, July 5th 12th, 6PM
Electronic submissions: Use CDF submit command. Assignment name is PA1. File name should be PA1sol.c, PA1sol.cc, PA1sol.java or PA1sol.py
Questions: PA1.pdf
Solution: PA1sol.cc
Mark distribution: PA1_marks.png
Test cases: PA1-test.tar
Marker's Remarks: PA1mr.txt
Programming Assignment 2 (4%)
Due: Thursday, August 9th, 6PM
Electronic submissions: Use CDF submit command. Assignment name is PA2. File name should be PA2sol.c, PA2sol.cc, PA2sol.java or PA2sol.py
Questions: PA2.pdf
Example source codes: PA2sol-template.cc PA2sol-template.java
Solutions: PA2sol.cc PA2sol.java PA2sol-fast.cc
Test cases: PA2-IO.tar.bz2
Marker's Remarks: PA2mr.pdf

Term Tests (45%)

To help you out in case you do particularly poorly on one term test the total marks of the term tests will be distributed as follows: The term test you do worst at will be worth 9% of your final mark, the other two will be 18% each.

Term Test 1
When: Tuesday, June 12th
Questions: TT1.pdf
Mark distribution: tt1_marks.png
Marker's Remarks: TT1mr.txt
Term Test 2
When: Tuesday, July 10th. 6:45PM
Duration: 75 minutes
Questions: TT2.pdf
Mark distribution: tt2_marks.png
Marker's Remarks: TT2mr.txt
Term Test 3
When: Tuesday, July 31st. 6:45PM
Duration: 75 minutes
Questions: TT3.pdf
Mark distribution: tt3_marks.png
Marker's Remarks: TT3mr.txt

Final Examination (35%)

Final Examination (35%)
When and Where: Check the official calendar
Information about the exam quetions: The exam will have 5 questions (some of them with subparts.) The first three questions will be on the topics covered in the assignments/term tests. The last two will be on NP-completeness and other related material. One of these two questions will be primarily concerned with basic understanding of the material and will be in multiple choice form. The other will be a problem.
Examination Aids: One 8.5” × 11” sheet of paper, handwritten on both sides.
Notes:
Faculty of Arts and Sciences August 2012 Examination Schedule
Faculty of Arts and Sciences Examination Reminders
Faculty of Arts and Sciences Examination Rules

Time Table



Policy Regarding Plagiarism and Academic Offense

University of Toronto has strict rules against plagiarism. You must not submit work belonging to others as yours. It is considered an academic offense and will be dealt with accordingly. The work you submit must be your own, if you are going to get help from any resource (books, online resources, people including other students, ...) other than the course material (textbook, course lecture notes) you should acknowledge them explicitly and give proper credit to them in your work.

For this course, you have the permission to discuss and work on assignments together with other students, but you should prepare the written solutions alone. It is fine to get help to understand, but the work you submit must represent your understanding in your words. You should be able to explain what you have submitted to the instructor orally without any previous preparation or notice during the semester. To make sure that you are writing what you have understood in your own words, don't take any notes from your discussions, wait a few hours before writing any notes related to them, and do not show your written answers to other students before due dates. Copying assignments and allowing others to copy your assignment are strictly forbidden.

For more information see Advice About Academic Offences by Jim Clarke



Based on a similar course website made by Kaveh Ghasemloo

Valid HTML 4.01 Strict Valid CSS!