Computability Theory CPSC513

Contact Information

Instructor: Pieter J.W. Hofstra
Office hours: Monday, 15.00 -- 17.00 or by appointment
Office: ICT627
Phone: 210 9403
Email: hofstrap@cpsc.ucalgary.ca

Schedule

Lectures: Tuesdays and Thursdays, 14.00 -- 15.15, MS527
Tutorial Sessions: Fridays, 13.00 -- 13.50
TA: X. Guo

Exams, Assignments, Marking Schemes

Midterm Exam: 25%
Final Exam: 35%
Assignments: 40%

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:

Chapter 2,3 entirely
Chapter 4: sections 1,2,3,4,5.

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:

Chapter 2,3 entirely
Chapter 4: sections 1-8
Chapter 5: sections 1-3
Chapter 6: sections 1-4
Chapter 8: sections 1-6

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:

Proofguide (introduction to proofs, various good and bad examples)
Common mistakes in proofs (ten typical mistakes to avoid)
On proofs (a bit of philosophical background and some examples)

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

Assignment 1 (due: Oct 10th)
Assignment 2 (due: Nov 1st)
Assignment 3 (due: Nov 21st)
Assignment 4 (plus bonus assignment, due: Dec 14th)

Solutions to Assignments

Solutions to assignment 1

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.