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 6PM7PM at
WI1017BA1220  Thursdays 6PM8PM at BA1170
 Tutorials
 When: Tuesdays 7PM8PM
Where: BA2165 (last names AJ), BA2175 (last names KZ) Where: BA2165 (last names AD), BA2175 (last names EM), BA2159 (last names NZ)
 Office Hours
 When: Tuesdays and Thursdays 4:30PM5: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 NPcompleteness: polynomial time reductions, examples of various NPcomplete problems, selfreducibility.
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: RobinKarp 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 FordFulkerson 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 261: Escape problem July 10nd Network Flow CLRS Problem 261: Escape problem Term Test 2. July 12th Network Flow CLRS Problem 263: 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 NPCompleteness CLRS (Intro. of) Chap 34 and Section 34.1: Intro., Encoding and input length, class P (Tutorial Notes) Assignment 3 due. July 26st NPCompleteness CLRS Sections 34.1 and 34.2: Classes P and NP July 31st NPCompleteness CLRS Section 34.2: CSAT is in NP Term Test3. August 2nd NPCompleteness CLRS Section 34.3: Reductions and NPhardness, CSAT is NPcomplete August 7th NPCompleteness CLRS Section 34.3: 3SAT is NPcomplete (Tutorial Notes) August 9th NPCompleteness 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 NPCompleteness" or "Clarification for assignment 1".
Announcements
 August 30th, 2012
 Solutions to (nonprogramming) 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 PA2solfast.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 ~/PA2report.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 57PM. 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 56PM. 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:305: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:305: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:007:00 and Thursday August 2nd 4:305: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:305:30 and tomorrow 6:007: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:305:30 and Wednesday July 18th 6:007: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:305: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:006: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 AJ will go to BA2165, KZ to BA2175. We will have 3 tutorials starting from next week.
 June 4, 2012
 We now have 3 tutorials so the nametutorial assignment has changed. Last names AD will now go to BA2165, EM to BA2175, and NZ 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 24pm. 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
5th12th, 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: PA1test.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: PA2soltemplate.cc PA2soltemplate.java
 Solutions: PA2sol.cc PA2sol.java PA2solfast.cc
 Test cases: PA2IO.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 NPcompleteness 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
Links
 DCS Resources
 Undergraduate CS Course Help Centre
 Course Websites from Previous Years
 CSC 373 Spring 2012: Algorithm Design, Analysis and Complexity by Prof. Allan Jepson
 CSC 373 Fall 2011: Algorithm Design, Analysis and Complexity by Prof. Allan Borodin
 LaTeX Resources
 TeXLive, a cross platform TeX/LaTeX distribution
 LEd, editor for Windows
 Kile, editor for Linux/Unix
 TeXShop, editor for Mac
 TeXMaker, cross platform editor
 TeX.SX, Q & A site for TeX/LaTeX
 A (Not So) Short Introduction to LaTeX2e
 Symbols accessible from LaTeX
 The Comprehensive TeX Archive Network
 Misc
 Theory Group at University of Toronto, Department of Computer Science
 Complexity Zoo
 Mathematics StackExchange, a Q & A site for mathematics
 Computer Science StackExchange, a Q & A site for Computer Science
 cstheory: TCS StackExchange, a Q & A site for TCS
 Theory Matters
 ACM SIGACT
 Some Theory Blogs
 Theory of Computing Blog Aggregator maintained by Arvind Narayanan
 Gödel’s Lost Letter and P=NP blog by Richard J. Lipton and Kenneth W. Regan
 in theory blog by Luca Trevisan
 my choices by Oded Goldreich
 Computational Complexity blog by Lance Fortnow and Bill Gasarch
 ShtetlOptimized blog by Scott Aaronson
 cstheory community blog
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