COMP 3602 -- Intro to the Theory of Computation, Fall 2021
- 08/09/2021 We have our first lecture today, 4pm at EN-2043. Exciting! It will be great to see you in person -- at a 2m distance and with masks on, of course!
I am trying to get the setup to have all our lectures recorded (including today's). This will be through the university's lecture capture system.
If there is interest, I could also try running Zoom on my laptop as I am teaching (though the sound quality is probably going to be atrocious) -- please let me know if you'd like me to do that, and I'll post a link on D2L.
- 29/08/2021 The Brightspace/D2L page for the course should now be live. If you are registered, please check it out and fill in the survey/calibrating questionnaire. Thank you so much!
- 14/08/2021 Welcome to COMP 3602, a new course on the theory of computation! Here are a very tentative course outline, marking scheme, etc. So far, as far as I know and unless something changes, the plan is to have the course in person this semester. Given the situation and also since it is a new course, a lot of details will be decided on during the first week of classes, in particular via a "calibrating questionnaire" on D2L which will be available in a few days.
Course page: We will be using Brightspace/D2L for course materials, announcements, etc. Please subscribe to the D2L notifications so that you get emails about the announcements at your actual email address (outside of D2L).
Lectures: 4:00pm -- 4:50pm Monday/Wednesday/Friday in EN-2043
Instructor: Antonina
Kolokolova , office ER-6033,
Email: kol at mun dot ca. Please do not send me emails with attachments or pictures to that address, as it is a small mailbox and overflows easily. If you'd like to send something large such as a screenshot or a photo, please email it to me at D2L (Brightspace), and also send a short email to kol at mun dot ca telling me to check D2L mail.
Instructor office hours: TBD.
Textbook: There will be no required textbook for this course; some course notes /slides will be posted.
That said, we will mostly follow Michael Sipser's "Intro to the theory of computation" (3rd edition preferred, 2nd OK).
For more advanced material we will probably use Sanjeev Arora and Boaz Barak "Computational complexity: a modern approach" .
Marking scheme
( very tentative! ):
- Auto-graded multi-attempt drills: 15% total.
- 2 tests of 25% each. Dates TBD. There will be ungraded assignments with practice problems similar to what will appear on the tests.
- A final exam of 35%
- Maybe an optional project (for a part of an exam grade), if there is interest.
- Additionally, a bonus "bug bounty" for finding errors in slides, drills, assignments and tests.
Note that there might be a test during the last week of the semester.
We will discuss the marking scheme in more detail, as well as what happens if we have to go remote again, during the first week of classes.
Prerequisites/background
This is one of the most abstract/conceptual courses in our curriculum. There will be no implementations, some pseudocode, and a lot of proofs. It will mostly build upon the material and skills from COMP 1002 and the non-programming parts of COMP 1003, as well as the basic knowledge of algorithms and data structures at the extent of COMP 2002 (if you did COMP 1000 instead of COMP 1003, that should be OK too. It would be useful to have seen finite automata, Turing machines and the Halting problem somewhere). Overall, expect to spend more time thinking and less time writing/coding.
Tentative course outline
What is an algorithm? What does it mean for a problem to be computationally easy, hard or unsolvable? What can be solved by a computer with only small finite memory or by circuits of a limited size? This course is about what is known and what is open about the power of computation, and its connections to areas from logic (including Gödel's incompleteness theorems) to cryptography. Time permitting, we may touch upon more advanced topics such as complexity of learning, Kolmogorov complexity, communication complexity, and/or quantum computing.
You are welcome to check the lecture notes from a somewhat similar course (1/2 to 2/3 overlap with COMP 3602).