Final Announcement: I hope everyone enjoyed the course. I wish everyone a good year this fall. Any remaining unreturned work (including regrades) is available from me in SF3213 (please do not bother my officemates, they do not know where I am, when I'll be back, or where I am storing your work for return). Once the CSSU is set up, I will be giving any remaining items to them.
Students should consult this page at least once a week for important information.
General techniques for efficient algorithm design: greedy
algorithms, dynamic programming; other topics may include network flow,
linear programming, randomized algorithms. Introduction to
complexity theory: models of computation, the classes P and NP,
polynomial time reducibility and NP-completeness, provably hard problems.
Introduction to the theory of computability: Church's thesis, computable
and noncomputable functions, reductions, the analogies
between complexity and computability theory.
Prerequisite: CSC238H1/(MAT246Y1/247H1, plus some
knowledge of programming); CGPA 3.0/enrolment in a CSC subject POSt
More information relevant to this incarnation of the course is available in the course outline. There are main three topics to this course.
Homework: Each week a number of problems will be assigned relating to the course material. You will be expected to complete some of the problems to be handed in and graded. These problems will compose three assignments throughout the term. Some problems will be assigned yet not form part of the assignments. You are encouraged to work on these problems and solve them, as they will further your understanding of the material (and may appear on quizzes!).
Quizzes: Occasionally quizzes will be held in the tutorial session. One (or a few) of these weekly assigned problems, or a closely related problem, will be asked. The quizzes will be closed book and presume you know how to solve the assigned problems.
Grading: Most of the problems in this course will involve proofs or counterexamples. Answers must be concise, clear, well thought out and presented neatly to obtain full marks. Up to 25% will be deducted for overly long, rambling, sloppy or unclear answers, at the grader's discretion.
Fifth Rule: In mathematics it is important to know both how to solve problems and when one does not know how to solve a given problem. Hence incorrect answers may be given zero credit, whereas if you recognize that you cannot solve a problem and state only this, you will be given one fifth (20%) credit on the problem. In other words, a wrong answer will earn zero marks, but an answer of "I don't know the answer" will earn 1/5 marks.
Policy on Lateness, Absence and Extensions: Late assignments will generally not be accepted. In the case of a missed quiz or test, a mark of zero will be recorded. No make-up quiz or test will be provided. Only in exceptional circumstances will requests for extensions for assignment deadlines or excuses for missed tests be entertained. Any such request must be presented to the course instructor (not a TA) with all supporting documentation as soon as possible. The sole remedy available in exceptional circumstances for missed tests is redistribution of its weight to other components.
Required:
Cormen, Leiserson, Rivest and Stein.
Introduction to Algorithms (2nd edition)
This text (CLRS) is also used in CSC378.
The most relevant chapters are 3,15,16,25,26,34.
It does not cover all the complexity and computability material we require.
Regardless, any computer scientist should have a good book on algorithms.
It should serve as a valuable reference throughout your career.
Recommended:
M. Sipser. Introduction to the Theory of Computation
The most relevant chapters are 0,3,4,5,7,8.
This text (Sipser) covers only computability and complexity.
Optional:
Garey and Johnson. Computers and Intractability: A Guide to the Theory
of NP-Completeness
The introductory chapters 1,2,3 are especially relevant.
This is a classic book, deserving a spot on any bookshelf.
There are several notes composed by previous instructors of this course. They will serve as a valuable, concise reference. They will be updated during the term as we cover the material, so only print out the current pieces.
| Component | Total Weight |
|---|---|
| 3 Homework Assignments (4% each) | 12% |
| 4 Quizzes in tutorial (4% each) | 16% |
| 2 Midterm Tests (16% each) | 32% |
| 1 Final Exam | 40% |
| Week of | Anticipated Lecture Topics | Events | Readings |
|---|---|---|---|
| May 15 | Introduction to computation and Turing machines Review of polynomials, asymptotic notation, space/time complexity |
First lecture. First tutorial. No Monday office hour |
CLRS: 3 Sipser: 0, 3.1 |
| May 22 | Introduction to decision problems and languages Other models of computation, decidable vs. recognizable languages |
Monday office hour cancelled (Victoria Day) | Sipser: 3.2-3.3 |
| May 29 | Church-Turing Thesis, Nondeterminism, Goedel's theorem | Quiz #1 in tutorial session | Sipser: 4 |
| June 5 | Universality, non-computability, diagonalization, reductions | Sipser: 5 | |
| June 12 | Efficiency of algorithms, greedy algorithms | Quiz #2 in tutorial session
Assignment #1 due (Thursday 6pm) |
CLRS: 16 |
| June 19 | The divide & conquer technique | Test #1 in lecture/tutorial | CLRS: 2.3, 33.4 |
| June 26 | Dynamic programming | CLRS: 15 | |
| July 3 | Flows and cuts, linear programming | Monday office hour cancelled (Canada Day) | CLRS: 26.1-26.3, CLRS: 29.1-29.3 |
| July 10 | Hard problems, classes of P and NP, efficiency vs. tractability | Quiz #3 in tutorial
Assignment #2 due (Thursday 6pm) |
Sipser: 7.1-7.3 |
| July 17 | Reductions and reducibility | Test #2 in lecture/tutorial Last day to withdraw without penalty July 21 |
CLRS: 34.1-34.3 |
| July 24 | Cook's theorem and NP-completeness | CLRS: 34.3 Sipser: 7.4 |
|
| July 31 | Guest lecturer! More NP-complete problems, related classes (co-NP, poly heirarchy) |
Quiz #4 in tutorial
Assignment #3 due (Thursday 6pm) |
CLRS: 34.4-34.5 Sipser:7.5 |
| August 7 | Dealing with hard problems, randomization, approximation | Monday office hour cancelled (Civic Holiday)
Last day of class. Last tutorial. |
CLRS: 35 |
| August 12-16 | Final Exam week -- see
Faculty for date and time Good luck! |
||
You are expected to work on each problem on your own and present your own solution. You may use the textbooks, notes, lectures, instructors, tutors and classmates to help you find general strategies to solve the problems, but you may not go out and find complete solutions to the problems. You may discuss the strategies to solve these problems with your fellow students, but you may not discuss complete solutions. You cannot take written notes or solutions away from a discussion with another student. Using other people's work or solutions, whether cited or not, is considered plagiarism and carries stiff academic penalties. If you are unsure whether an activity may constitute plagiarism or undue collaboration, consult the instructor immediately. You are encouraged to review the University of Toronto Code of Behaviour on Academic Matters.
Another instructor explains Academic Honesty very well here. I encourage you to read it.
Assignments are due by 6pm on the Thursday due date in the CSC 364 drop box on 2nd floor of Sandford Flemming Building. Assignments may also be turned in to the instructor at lecture preceeding the due date. Late assignments will not be accepted in the drop box.
Every assignment must include this cover page (PS) (PDF) as the first page of your assignment. Be sure to completely fill in and sign this page before submitting. Assignments should be stapled securely: do not submit within an envelope, binder or folder, or bound with paper-clips, string, or any origami technique. Remember you should only hand in the questions indicated by a star *.
|
Copyright ©
Richard Krueger
All rights reserved. |