Computability Theory CPSC513

Contact Information

Schedule

Exams, Assignments, Marking Schemes

Note: there will be 4 assignments plus one bonus assignment. The four best marks will be used to calculate the average on the assignments.

Midterm exam

Scheduled for Thursday, Oct. 26th, 14.00--15.15. The following material will be covered: For a sample midterm, click here For the solutions to the actual midterm, click here

Final exam

Scheduled for Dec. 14th, 15.30--18.30. The following material will be covered: The emphasis on the final exam will be on the material after the midterm. For a sample exam, click here. For a variation, click here.

Textbook

Computability, Complexity, and Languages (2nd Edition). M. Davis, R. Sigal, E. Weyuker. Academic Press, 1994.

How to write a proof?

In this course you will have to write proofs, and many students find that difficult or have little experience in doing so. The following links provide you with some general guidelines and tips:

Course Progress

Click on the week to see what I have covered in class, which sections in the book you are supposed to have read, and which exercises you should do.

week 1 (Sept. 11 - 15)

week 2 (Sept. 18 - 22)

week 3 (Sept. 25 - 29)

week 4 (Oct. 2 - Oct. 6)

week 5 (Oct. 9 - Oct. 13)

week 6 (Oct. 16 - Oct. 20)

week 7 (Oct. 23 - Oct. 27)

week 8 (Oct. 30 - Nov. 3)

week 9 (Nov. 6 - Nov. 10)

week 10 (Nov. 20 - Nov. 24)

week 11 (Nov. 27 - Nov. 31)

week 12 (Dec. 3 - Dec. 7)

Assignments

Solutions to Assignments

Course Summary

Click here for a 10-page summary of the course. Recommended for final exam preparation.

Other Information

More information about the course, assignments, exam dates etc. will appear on this website during the course. You are advised to check this website regularly for new information.