CSC 364H L5101: Computability and Complexity

Summer 2000

Evening Section

Please check this page regularly for important information.

Announcements:

August 20: Click here for your final marks.
Old Announcements

Instructor: Valentine Kabanets, email: kabanets@cs.toronto.edu

Lectures: T7-9 SS2102

Office Hours: R9-10pm SF3207, or by appointment.

Tutorials: T6. See the following table to find out where your tutorial will be held.

Students whose last name starts with the letter in	Tutorial Room	TA
A-G	SS 2102	Kit-Sun Ng
H-M	RW 142	Mohammad Salavatipour
N-Z	SS 1080	Frank van Bussel

Course information [html] [ps]

Important Dates:

June 6: Problem Set 1 is due
June 13: Test 1
July 4: Problem Set 2 is due
July 11: Test 2
August 1: Problem Set 3 is due
August 8: Test 3

Lecture Notes:

Greedy Algorithms
Dynamic Programming Algorithms
Flow networks are covered in CLR, pp. 579-604. No lecture notes on this topic will be posted.
Turing Machines and Polynomial Time
NP and NP-completeness
Computability and Noncomputability

Problem Sets:

Problem Set 1 and Solutions to Problem Set 1 and tutor's comments
Problem Set 2 and Solutions to Problem Set 2 and tutor's comments
Problem Set 3 and Solutions to Problem Set 3 and tutor's comments

Quizzes:

Some useful documents:

"Big-Oh" notation

Some useful links:

Last modified: August 20 2000