Contents may differ from the current or most recent offering of the course.
Course Description
This course focuses on three areas central to the theory of computation: automata, computability and complexity, to investigate the question: What are the fundamental capabilities and limitations of computers? We study automata (models of computation) e.g., finite state machines, pushdown automata and Turing machines and the languages recognized by them. We investigate complexity theory, to classify problems as easy or hard and computability theory to classify problems as solvable or not.
See the course outline for more information.
Course Details
Lecture Time/Place
Tuesday, 8:15am–9:05am; Wednesday, 10:15am–11:05am; Friday, 9:15am–10:05am
All lectures are held in Mulroney Hall, room 4032.
Textbook
M. Sipser, Introduction to the Theory of Computation. Cengage, 3rd edition, 2012.
The textbook is available for sale at the campus bookstore. Course notes will also be provided for each lecture.
Marking Scheme
- Two assignments (15% each, total 30%)
- Two quizzes (12.5% each, total 25%)
- Written report (total 40%): topic proposal (10%) and report (30%)
- Participation in lectures (5%)
You must complete both the topic proposal and the written report in order to pass the course, even if the weighted sum of your other submissions is at least 50%.
News
- Dec. 6: Lecture notes for the twelfth week have been posted.
- Nov. 25: Lecture notes for the eleventh week have been posted.
- Nov. 18: Lecture notes for the tenth week have been posted.
- Nov. 15: Assignment 2 has been posted. It is due by Nov. 29 at 8:15am.
- Nov. 4: Lecture notes for the ninth week have been posted.
- Oct. 28: Lecture notes for the eighth week have been posted.
- Oct. 21: Lecture notes for the seventh week have been posted.
- Oct. 12: Lecture notes for the sixth week have been posted. As mentioned in lecture today, the lecture on Friday will be cancelled due to the instructor being away.
- Oct. 7: Lecture notes for the fifth week have been posted.
- Oct. 4: Information about the written report has been posted.
- Sep. 28: Lecture notes for the fourth week have been posted.
- Sep. 27: Due to the inclement weather over the weekend, both student hours and the lecture today are cancelled.
- Sep. 23: Lecture notes for the third week have been posted.
- Sep. 20: Assignment 1 has been posted. It is due by Oct. 11 at 8:15am. Following a discussion in lecture today, the quiz dates have also been adjusted. Quiz 1 will now be released on Oct. 11 and Quiz 2 will be released on Nov. 22.
- Sep. 16: Lecture notes for the second week have been posted.
- Sep. 9: Lecture notes for the first week have been posted.
- Sep. 1: Welcome to the course! The first lecture is on Sep. 6.
Lectures
Week | Notes | Readings |
1 | Introduction, mathematical preliminaries | Sipser, 0.1–0.2 |
2 | Regular languages: finite automata, nondeterminism | Sipser, 1.1–1.2 |
3 | Regular languages (cont’d): closure properties, regular expressions | Sipser, 1.3 |
4 | Regular languages (cont’d): proving nonregularity | Sipser, 1.4 |
5 | Context-free languages: grammars, ambiguity | Sipser, 2.1 |
6 | Context-free languages (cont’d): Chomsky normal form | Sipser, 2.1 |
7 | Context-free languages (cont’d): PDAs, DCFLs | Sipser, 2.2, 2.4 |
8 | Context-free languages (cont’d): proving non-context-freeness | Sipser, 2.3 |
9 | Beyond context-free: Turing machines, variants | Sipser, 3.1–3.2 |
– | Fall study break | – |
10 | Beyond context-free (cont’d): Universal TMs, Church-Turing thesis; Decidability | Sipser, 3.3, 4.1 |
11 | Reducibility | Sipser, 5.1, 5.3 |
12 | Time complexity: P, NP, NP-completeness | Sipser, 7.1–7.4 |
Assignments
- Assignment 1, due Oct. 11
- Topic Proposal, due Oct. 25
- Assignment 2, due Nov. 29
- Report, due Dec. 6
Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
The topic proposal and report must be submitted on the due date. Late submissions will not be accepted.
Quizzes
Quiz 1
Release Date: Oct. 4 Oct. 11, 2022, end of class
Due Date: Oct. 5 Oct. 12, 2022, beginning of class
Content: All material from Weeks 1 to 5
Quiz 2
Release Date: Nov. 1 Nov. 22, 2022, end of class
Due Date: Nov. 2 Nov. 23, 2022, beginning of class
Content: All material from Weeks 6 to 10
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Tuesday, 9:15am–11:15am