DCS logo CSC373H Winter 2014
Algorithm Design, Analysis, and Complexity

Course Information Announcements Topics and Timetable Assignments, Tests, Solutions Policies Links Forum

Students should consult the forum at least once a week.

If you have a question, please check first the policies 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.


Announcements

March 25, 2014
Assignment 3 Solutions Posted. See the assignments page to download it.
March 13, 2014
Midterm Solutions Posted. See the assignments page to download it.
March 6, 2014
Assignment 3 Posted. See the assignments page to download it.
March 4, 2014
Programming Project Posted. See the assignments page to download it, and further information is available on the Piazza board.
February 10, 2014
Assignment 2 Solutions Posted. See the assignments page to download them.
February 10, 2014
Assignment 1 Solutions Posted. See the assignments page to download them.
February 10, 2014
Assignment 2 Deadline Extension. Assignment 2 has been extended by 3 days -- it is now due Feb 16th at 10pm.
January 30, 2014
Assignment 2 Posted -- Due Feb 13. A link to the assignment is located here.
January 16, 2014
Assignment 1 Posted -- Due Jan 30. Be sure to check the policies page for the assignment policies. The assignment (along with submission guidelines) are outlined on the assignments page.
January 15, 2014
Notes for Lecture 4 Posted on Piazza
Assignment 1 will be posted at noon on Thursday, January 16th.
January 13, 2014
Notes for Lecture 3 Posted on Piazza
Office Hours Poll The poll for office hours is closed! Office hours will now be Tuesdays and Fridays at 3:00pm.
January 10, 2014
Office Hours Poll THE POLL CLOSES SUNDAY! Vote for office hours this semester here.
Notes for Lecture 2 Posted on Piazza Here is a link.
Poll for interesting topics! I have added a poll to Piazza for things that you guys find interesting! The wonderful thing about algorithms is that you can almost always find an algorithmic problem snuggled into any topic. If you have something that you particularly like to think about then post it here.
January 8, 2014
Office Hours Vote for the office hours this semester at this doodle poll .
Prerequisite waiver: If you need a prerequisite waiver please send me an e-mail.

Course Information

Instructor
Name: Robert Robere
Email: robere AT cs DOT toronto DOT edu
Office: SF-4306D
Teaching Assistants
Names: David Yu Cheng Chan, Lalla Mouatadid, Joel Oren, Dhinakaran Vinayagamurthy
Lectures
When: Mondays, Wednesdays, and Fridays 11AM-12AM
Where: WI-1016
Tutorials
When: Monday 4PM-5PM (Begins January 13th)
Where: WI-1016
Office Hours
When: Tuesdays and Fridays at 3:00pm
Where: SF-4306D
Course Website
http://www.cs.toronto.edu/~robere/csc373h/
Course Forum
Piazza forum for CSC373H
We will be monitoring the board regularly to answer your questions.
Textbook
[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.
Supplementary/Reference Book
[DPV] Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani, "Algorithms", 2006. Errata.
 
[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-and-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
Title Points Notes
Participation 5

Actively engaging in lectures, tutorial attendance, picking up assignments and midterms

Assignments 30

Three assignments, each worth 10 points.

Midterm 10

One midterm worth 10 points.

Programming Project 15

One programming project worth 15 points.

Final Exam 40

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

Total 100
Course Information Sheet
Information Sheet


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

Valid HTML 4.01 Strict Valid CSS!