SE 4I03: Theoretical Foundations of Computation
Fall 2001
Instructor: Michael Soltys, email:
my last name at mcmaster.ca
Check this web page regularly for announcements. If you need a
PostScript previewer, go to
Ghostview Software.
Course Information (revised on Sept 17)
Announcements:
- FINAL EXAM
- Dec 6: Click here to see your
term marks. Assignment 4 has been marked, and I'll put it in a box in
front of my office, tomorrow (Friday). Check that your marks have
been entered correctly, and let me know if there are discrepancies.
- Dec 3: The OCGS approved the PhD in Software Engineering; thus,
our department has now four graduate programmes: Master's and PhD in
both Software Engineering and Computer Science.
- Nov 30: Solutions to Assignment 4 are posted below.
- Nov 28: You are NOT responsible for the P/NP material (Wed Nov
28 lecture) for the final exam. I will do course review on Friday. I
will also try to bring Test 2 to class on Friday.
- Nov 28: If you are interested, you can read more about PGP
cryptography at How PGP
works.
- Nov 28: If you are interested, you can check out the following
Turing Machine "implementation" on the web:
TM Applet. You can program it yourself, and then watch it run,
but you can also load the PALINDROMES program; unfortunatelly, I did
not know about this until today.
- Nov 23: In the remaining 4 lectures, we will do the following:
- Finish Computability, that is cover the material in the notes
Computability II, posted below.
- Introduce the complexity classes P and NP; essentially cover
pages 1-5 in the notes "P vs NP", posted below.
- A review of the course material.
- Nov 22: As was announced in class on Monday, there is no class
this Friday (Nov 23). See you on Monday (Nov 26).
- Nov 19: Assignment 4 (the last one!) has been posted below.
- Nov 19: The solutions to Test 2 have been posted below.
- Old Announcements
Notes:
Problem Sets:
- Assignment 1 (due Sept 26):
- Assignment 2 (due Oct 26):
- Assignment 3 (due Nov 12):
- Assignment 4 (due Nov 30):
Tests: