DCS logo CSC373H Fall 2013
Algorithm Design, Analysis, and Complexity
Assignments CourseInfo FAQ Forum Time Table Links

Students should consult the forum at least once a week.

If you have a question, please check first the frequently asked questions and the forum to see if your question is already answered.

Please post non-personal questions (e.g. clarification requests about assignments, explanation requests for topics covered in lectures, etc.) on the forum so other students can also benefit from them.

If you are sending an email to us please read this note so we don't miss your email.

Course Info

Instructor
Name: Kaveh Ghasemloo
Email: csc373
Office: SF4306B
Teaching Assistants:
Names: Norman Huang, Joel Oren, Robert Charles Robere, Maryah Safi
Lectures
When: Mondays, Wednesdays, and Fridays 10AM-11AM
Where: MP203
Tutorials
When: Thursdays 2PM-3PM
Where: MP202
Instructor Office Hours
When: Mondays, 1PM-2PM, Wednesdays 11AM-12noon
Where: BA2230
TA Office Hours
When: Fridays, 4PM-5PM
Where: BA2230
Course Website
http://www.cs.toronto.edu/~kaveh/csc373h/
http://j.mp/csc373h
Course Forum
Piazza forum for CSC373H
We will be monitoring the board regularly to answer your questions.
Textbook
[DPV] Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani, "Algorithms", 2006. Errata.
 
You can download the draft of the book free of charge.
Supplementary/Reference Book
[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, "Introduction to Algorithms", 3rd. ed., 2009. Errata.
 
You have online access to the 2nd. edition through the UofT library.
 
[JeffE] Jeff Erickson, "Algorithms Course Materials", 2011.
 
You can download the complete version free of charge.
Other Books
[GT] Michael T. Goodrich and Roberto Tamassia, Algorithm Design, Foundations, Analysis, and Internet Examples", 2001.
 
[KT] Jon Kleinberg and Éva Tardos, "Algorithm Design", 2005.
 
[Skiena] Steven S. Skiena, "The Algorithm Design Manual", 2008.
 
[TAOCP] Donald E. Knuth, "The Art of Computer Programming", 1997-∞.
 
Course Description
Standard algorithm design techniques: divide & conquer, greedy strategies, dynamic programming, linear programming, randomization, network flows, approximation algorithms. 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.
(from Faculty of Arts & Science Calender)
Tentative Course Outline
Introduction (1 week), Greedy Algorithms (2 weeks), Dynamic Programming (2 weeks), Network Flow (2 weeks), Linear Programming (2 weeks), NP–completeness (3 weeks), Coping with Hard Problems (1 weeks).
Prerequisites
CSC263H1/ CSC265H1,
CGPA 3.0 or enrolment in a CSC Subject POSt.
The prerequisite requirement is strictly enforced in this course.
Exclusion
CSC375H1/CSC364H1.
Breadth Requirement
The Physical and Mathematical Universes (5).
Marking Scheme
Marking Scheme
Title Points Notes
Exercises 10

Several short exercises will be given over the course.
Assignments 30

3 assignments, each assignment 10 points.
Tests 20

2 tests, each test 10 points.
Take Home 10

Optional, see the instructions below.
Final Exam 40

To pass this course you must get at least 40% in the final exam.
Total 110

The extra points are bonus:
students with score > 100 points will get 100 as their mark,
students with score ≤ 100 points will get that score as their mark.
Course Information Sheet
csc373f13info.pdf

Time Table

Tentative Time Table
Dates Topics DPV CLRS Handouts Notes
Week 1
Sep. 9–13
Introduction
Optimization Problems
Brute–Force
Backtracking
Divide & Conquer
Greedy Algorithms
Interval Scheduling
 
 
 
 
 
5
 
 
 
 
 
 
16
 
Week 2
Sep. 16–20
Greedy Algorithms
Interval Coloring
Minimum Spanning Trees
Prim
Kruskal
5
 
 
 
 
16
 
23
 
 
 A1 out
Week 3
Sep. 23–27
Greedy Algorithms
Huffman Codes
Fractional Knapsack
5
 
 
16
 
 
Week 4
Sep. 30–Oct. 4
Dynamic Programming
Weighted Interval Scheduling
Bounded 0/1–Knapsack
Longest Increasing Subsequence
6
 
 
 
15
 
 
 
 A1 due
Week 5
Oct. 7–11
Dynamic Programming
Single–Source Shortest Paths
Dijkstra
Bellman–Ford
All–Pairs Shortest Paths
Floyd–Warshall
6
4
 
 
6
 
15
24
 
 
25
 
 T1
Oct. 14 Thanksgiving (no classes).
Week 6
Oct. 16–18
Network Flow
Local Search
Max Flow/Min Cut
Ford–Fulkerson
Other Algorithms
7
 
 
 
 
26
 
 
 
 
 A2 out
Week 7
Oct. 21–25
Network Flow
Black–Box Reductions
Maximum Bipartite Matching
7
 
 
26
 
 
Week 8
Oct. 28–Nov. 1
Linear Programming
Max Flow
Standard Form
Geometric Intuition
Convexity
Min Cut
Primal/Dual
7
 
 
 
 
 
 
29
 
 
 
 
 
 
 A2 due
Nov. 4 Last day to drop the course without penalty.
Week 9
Nov. 4–8
Linear Programming
Linear Feasibility Problem
Unboundedness
Simplex Algorithm
Interior Point Methods
7
 
 
 
 
29
 
 
 
 
 T2
Nov. 11 November Break (no classes).
Week 10
Nov. 13–15
NP–hardness
Complexity Theory
Cook Reductions
Karp Reductions
P, NP, NP–complete
8
 
 
 
 
34
 
 
 
 
 A3 out
Week 11
Nov. 18–22
NP–hardness
Satisfiability (SAT)
Circuit–SAT
3CNF–SAT
Self–Reducibility
8
 
 
 
 
34
 
 
 
 
Week 12
Nov. 25–29
NP–hardness
Integer Programming
0/1–Knapsack
Subset–Sum
Partition
Longest Path Problem
Hamiltonian Cycle Problem
Traveling Salesman Problem
Graph Coloring
Max–Clique
Independent–Set
NP–intermediate
Factoring
Graph Isomorphism
Minimum Circuit Size
8
 
 
 
 
 
 
 
 
 
 
 
 
 
 
34
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 A3 due
Week 13
Dec. 2
Coping with NP–hardness
Problem Instances in Practice
Approximation Algorithms
Vertex Cover ∈ 2–APX
Δ–TSP ∈ 2–APX
TSP ∉ APX
Max–3CNF–SAT ∈ 8/7–APX
Max–3CNF–SAT ∈ APX–hard
Subset–Sum ∈ FPTAS
9
 
 
 
 
 
 
 
 
35
 
 
 
 
 
 
 
 
Make up Monday
Dec. 4
Coping with NP–hardness
9
35
 TH due
Dec. 9–20 Examination period.
Thursday Dec. 12
2PM-5PM		 Final Exam at St. Vladimir Institute, Auditorium B.

FAQ and General Remarks

Email
Email is the preferred way to contact the instructor and the teaching assistants for personal issues. Feel free to email the instructor regarding any course related personal issues. For non–personal questions please post on the forum so other students can also benefit from them.
Please use only the email addresses provided in the course info section.
Please use descriptive subject lines for your emails and include "CSC373", e.g. "CSC373 prerequisite waiver request" or "CSC373 special consideration request for test 1". We may miss emails without subject line starting with "CSC373".
Please send email only from your official University of Toronto email address when contacting us if you want to receive a reply, this is required by regulations, we cannot reply to any other email address.
We will try to answer your emails in 2 working days but it may take longer. You should not rely on getting same–day answers (particularly near assignment deadlines).
Accessing files in the restricted areas of this website
If needed use "csc373h" and "fall2013" to access the files on this website.
Late homework policy
Every 30 minutes after a deadline will cost 1% of the mark. The assignments are due on Fridays nights, 10PM. If we don't receive your assignment by the following Sunday midnight (50 hours) your assignment will not be marked.
You may face technical issues when submitting an assignment. We advise that you submit your assignment a few days before the deadline to avoid such issues. You can resubmit your assignment as many times as you want, so if you improve your assignment you can resubmit it. We are going to read only your last submission.
Missed homework policy
If you miss a homework deadline because of a medical or serious personal emergency, you must fill out the Special Consideration Form and provide it to the instructor as soon as possible.
In case of a medical emergency, you must also submit the UofT Verification of Student Illness or Injury, completed and signed by your physician. Please check Frequently Asked Questions on UofT Health Services.
If you are emailing the forms the subject line of your email must start with "CSC373 special consideration request".
If we judge your reason for missing the deadline to be valid, we will use the average mark you achieved in other homeworks to compute your mark for the missed homework.
Missed test policy
If you miss a test due to a medical or other serious personal emergency, get in touch with your instructor immediately, and fill out the Special Consideration Form.
In case of a medical emergency, you must also submit the UofT Verification of Student Illness or Injury, completed and signed by your physician. Please check Frequently Asked Questions on UofT Health Services.
If you are emailing the forms the subject line of your email must start with "CSC373 special consideration request".
There will be no make-up test, but if we consider your reason for missing the test to be valid, we will use your final examination mark to compute your mark for the missed midterm test.
Tutorial attendance
Attendance in tutorials is as mandatory as attendance in lectures. A formal attendance is not taken in either. However, there will be new material that is presented only in tutorials and not discussed in the lectures for which you are responsible and in which you may be tested in homeworks or exams.
Prerequisite
The prerequisite requirement is strictly enforced in this course.
If you do not satisfy it, you must contact the instructor and submit a petition for a waiver within the first week of class.
If you want to request a waiver you must fill out the Prerequisite Waiver Request Form.
We will grant a waiver only in exceptional cases where we have enough confidence based on the information you have provided that you will not suffer in this course because of not completing the required prerequisite. In addition, you should provided good reasons for why you have not taken the prerequisites before taking this course. Please submit one email explaining all relevant information, the decisions are final, we will not consider any information provided later. Submitting a request doesn't mean that you will receive a waiver. If you are making any plans, you should do so assuming that your request is going to be rejected.
If you receive a waiver it will be your responsibility to learn any material needed from the prerequisite. Throughout the course the assumption will be that students are familiar with material from the prerequisite.
After we receive a request we have to wait for the undergraduate office to sends us the files for students requiring a waiver. We will check them in a week and let you know the result.
Accessibility
The University of Toronto is committed to accessibility. If you require accommodations or have any accessibility concerns, please visit Accessibility Services as soon as possible to make any required arrangements.
Remark request policy (for assignments/test)
You can ask for remarking if you believe there is a mistake in the marking. If your request concerns a simple addition error or similar kind of errors, see the instructor.
For any other kind of remarking request, you must submit your request in written form. To submit a remark request, please print and fill the Remark Request Form, attach it to your paper, and give it to the instructor. In the explanation section of the form, specify the question and the part you are requesting a remarking, and explain briefly and clearly which part of marking you disagree with and why.
You should submit your remark request at most one week (7 days) after the papers are returned. Remark requests after this date will not be accepted.
We will look at all remark request, however please try to submit a remark request only when you believe the remarking will result in a significant increase your mark, e.g. please don't submit a remark request if the total increase that can result from your remark request is less than 1% of your final grade.
Reminder: A remarking request can cause the overall mark to stay the same, increase or decrease: we may re-examine every question in the paper and if new mistakes are found they can also change the marking up or down accordingly. Please submit a remarking request only if: (a) you have read and completely understood our posted solution set, and (b) you still think that your solution is correct and was mistakenly marked as incorrect. We rarely if ever accept remarking requests of the type "yes, my solution is not correct, but I think you took off too many marks for this mistake": The marking scheme was decided and applied as uniformly as possible to all students. If you believe a marking scheme is too harsh, it is still fair as long as it is consistently applied, we will adjust the marks (by adding points to everyone) if the marks are unexpectedly low because of marking scheme being harsh.

Assignments

How to submit assignments:
Assignments must be typed and a PDF copy must be submitted for marking using CDF. We will mark only your submitted PDF file. The filenames must be the assignment's name, e.g. your submission for the assignment "A2" must be "A2.pdf". Similarly the filename for your TeX file must be "A2.tex".

To submit your assignment use CDF's website or CDF's submit command. To submit your files using CDF's submit command, log on to a CDF machine, then use the following command to submit your files:
submit -c csc373h -a A2 -f FILE
For example, for assignment A2 use the following commands:
submit -c csc373h -a A2 -f A2.pdf
submit -c csc373h -a A2 -f A2.tex
For exercises use "E" followed by exercise number and ".pdf", e.g. for exercise 2 use:
submit -c csc373h -a Exercise -f E2.pdf
Include your full name and student number inside your files.

Using LaTeX is strongly encouraged. If you have not used LaTeX before, you can check LaTeX links section. Please use these templates: sample.tex, csc_assignment.cls.

If you are using another program to write your assignment, your PDF must be similar to the following sample: sample.pdf.

Assignment 1 (10 points)
Due: Oct. 4
Topic: Greedy, Dynamic Programming
Questions: A1.pdf
Solutions: A1sol.pdf
Assignment 2 (10 points)
Due: Nov. 1
Topic: Dynamic Programming, Network Flow/Min-Cut, Linear Programming
Questions: A2.pdf
Solutions: A2sol.pdf
Assignment 3 (10 points)
Due: Nov. 29
Topic:
Questions: A3.pdf
Solutions: A3sol.pdf

Exercises

Exercises (10 points)
Exercises will be posted on the forum.

Tests

Test 1 (10 points)
When: Oct. 10, 2PM-3PM
Where: MP202
Questions: T1.pdf
Solutions: T1sol.pdf
Notes:
No aids permitted.
Test 2 (10 points)
When: Nov. 7
Where: MP202
Questions: T2.pdf
Solutions: T2sol.pdf
Notes:
No aids permitted.

Take Home

Takehome (10 points)
Due: Dec. 4, 2013 (topic selection by Nov. 24, 2013)
Questions: See the instructions below.
Sample file: THsample.tex, THsample.pdf
Instructions:
For takehome you have to read about a topic we have not covered in this course and write a short (2 pages long) brief high-level essay about it. The main goal is to make you familiar with some advanced topic in algorithms that is not covered in this course.
Topic confirmation:
You have to select a topic by Nov. 24, request it by sending an email to the instructor containing your name, your topic, and your references (use "CSC373 takehome topic" as the subject line), and receive a confirmation from the instructor before starting to work on your topic. A takehome submission without a confirmation email will not be accepted.
Topics:
The topic should not be part of what is covered in CSC263/CSC373/CSC463.
Your topic can be algorithmic or complexity theoretic.
You can pick a computational problem that you find interesting and write about one or more good algorithms for it. You can also pick a chapter or part of a chapter from CLRS (algorithmic topics) or from "Complexity Theory: A Modern Approach" by Arora and Barak (complexity theoretic topics) as your topic. You can also check Wikipedia: list of algorithms and other books to find a topic.
For general help with writing consult UofT writing resources.

Final Examination

Final Examination (40 points)
When: Thursday, December 12, 2PM-5PM
Where: St. Vladimir Institute, Auditorium B
           620 Spadina Avenue (Students should enter via the south doors.)
Notes:
No aids permitted.
Faculty of Arts and Sciences Examination Schedule
Faculty of Arts and Sciences Examination Locations
Faculty of Arts and Sciences Examination Reminders
Faculty of Arts and Sciences Examination Rules

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 must 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 must 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 must 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

We would like to thank Siavosh Benabbas, Milad Eftekhar, and François Pitt for their permission to use their CSC373 course material.

This page was last updated on Dec. 16, 2013.

Valid HTML 4.01 Strict Valid CSS!