Contents may differ from the current or most recent offering of the course.
Course Description
An introduction to the theoretical foundations of computer science, examining finite automata, context-free grammars, Turing machines, undecidability, and NP-completeness. Abstract models are employed to help categorize problems as undecidable, intractable, tractable, and efficient.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 1:15pm–2:05pm; Wednesday, 12:15pm–1:05pm; Friday, 11:15am–12:05pm
All lectures are held in J. Bruce Brown Hall, room 236.
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
- Four assignments (12.5% each, total 50%)
- Midterm examination (25%)
- Final examination (25%)
You must write the final examination in order to pass the course, even if the weighted sum of your assignment and midterm examination grades is at least 50%.
News
- Dec. 9: The final exam will be written on Dec. 11. Following the guidance provided by the university, this exam will be written in person. An email has been sent to you with further information. See the review document and the Exams section below for details.
- Dec. 3: The second part of the lecture notes on time complexity has been posted.
- Nov. 26: The first part of the lecture notes on time complexity has been posted.
- Nov. 19: The fourth assignment has been posted. It is due by Dec. 6 at 1:15pm.
- Nov. 17: The lecture notes on reducibility have been posted.
- Nov. 15: The second part of the lecture notes on decidability has been posted.
- Nov. 3: The first part of the lecture notes on decidability has been posted.
- Nov. 1: The second part of the lecture notes on Turing machines has been posted.
- Oct. 25: The first part of the lecture notes on Turing machines has been posted. The third assignment has also been posted. It is due by Nov. 15 at 1:15pm.
- Oct. 18: The third part of the lecture notes on context-free languages has been posted.
- Oct. 13: The midterm will be written this week during the Oct. 15 lecture. See the review document and the Exams section below for details. There will also be a special student hour to make up for the student hour cancelled due to Thanksgiving:
- Oct. 14, 3pm–4pm
- Oct. 6: The second part of the lecture notes on context-free languages has been posted.
- Sep. 29: The first part of the lecture notes on context-free languages has been posted. The second assignment has also been posted. It is due by Oct. 22 at 11:15am.
- Sep. 22: The second part of the lecture notes on regular languages has been posted.
- Sep. 15: The first assignment has been posted. It is due by Oct. 1 at 11:15am.
- Sep. 10: The first part of the lecture notes on regular languages has been posted.
- Sep. 8: The introductory set of lecture notes has been posted.
- Sep. 1: Welcome to the course! The first lecture is on Sep. 8.
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): regular expressions, proving nonregularity | Sipser, 1.3–1.4 |
| 4 | Context-free languages: grammars, ambiguity | Sipser, 2.1 |
| 5 | Context-free languages (cont’d): Chomsky normal form, PDAs | Sipser, 2.2 |
| 6 | Mid-course review, midterm examination | — |
| 7 | Context-free languages (cont’d): proving non-context-freeness | Sipser, 2.3 |
| 8 | Beyond context-free: Turing machines, variants | Sipser, 3.1–3.2 |
| 9 | Beyond context-free (cont’d): Church-Turing thesis; Decidability | Sipser, 3.3, 4.1 |
| — | Fall study break | — |
| 10 | Undecidability; Reducibility | Sipser, 4.2, 5.1, 5.3 |
| 11 | Time complexity: P, NP | Sipser, 7.1–7.3 |
| 12 | Time complexity (cont’d): NP-completeness; Space complexity: PSPACE, L, NL | Sipser, 7.4, 8.1–8.2, 8.4 |
Assignments
- Assignment 1, due Oct. 1
- Assignment 2, due Oct. 22
- Assignment 3, due Nov. 15
- Assignment 4, 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.
Exams
Midterm
Date: Oct. 15, 2021
Time: 11:15am–12:05pm
Place: J. Bruce Brown Hall, room 236
Content: All material from Weeks 1 to 5
Final Exam
Date: Dec. 11, 2021
Time: 2:00pm–4:30pm
Place: Mulroney Hall, Room 2034
Content: Primarily material from Weeks 6 to 12, some earlier material
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Monday, 2:15pm–3:15pm; Tuesday, 9:15am–10:15am