Course Description
An introduction to the theoretical foundations of computer science, examining finite automata, context-free grammars, Turing machines, decidability and undecidability, and complexity theory. Strategies will be developed to help categorize problems as tractable or intractable.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 1:30pm–2:20pm; Wednesday, 12:30pm–1:20pm; Friday, 11:30am–12:20pm
All lectures are held in J. Bruce Brown Hall, room 236.
Special Note for Fall 2023. On Tuesday, December 5, the Monday schedule of classes and labs will be offered again. On Wednesday, December 6, the Friday schedule of classes and labs will be offered.
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. 6: The final exam will be written on Dec. 11. See the review document and the Exams section below for details. A practice final exam is also available.
- Dec. 5: Lecture notes for the twelve-and-a-halfth week have been posted.
- Dec. 4: Due to inclement weather, both office hours and the lecture today are cancelled.
- Dec. 1: Lecture notes for the twelfth week have been posted.
- Nov. 24: Lecture notes for the eleventh week have been posted.
- Nov. 20: Assignment 4 has been posted. It is due by Dec. 6 at 11:30am.
- Nov. 17: Lecture notes for the tenth week have been posted.
- Nov. 3: Lecture notes for the ninth week have been posted.
- Nov. 1: Assignment 3 has been posted. It is due by Nov. 17 at 11:30am.
- Oct. 27: Lecture notes for the eighth week have been posted.
- Oct. 20: Lecture notes for the seventh week have been posted.
- Oct. 16: The midterm will be written this week during the Oct. 18 lecture. See the review document and the Exams section below for details. A practice midterm is also available.
- Oct. 11: 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. 6: Lecture notes for the fifth week have been posted.
- Sep. 28: Assignment 2 has been posted. It is due by Oct. 11 at 12:30pm.
- Sep. 27: Lecture notes for the fourth week have been posted.
- Sep. 22: Lecture notes for the third week have been posted.
- Sep. 15: Lecture notes for the second week have been posted.
- Sep. 8: Lecture notes for the first week have been posted. Assignment 1 has also been posted. It is due by Sep. 20 at 12:30pm.
- 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: regular expressions, finite automata | Sipser, 1.1, 1.3 |
| 3 | Regular languages (cont’d): nondeterminism, closure properties | Sipser, 1.2 |
| 4 | Regular languages (cont’d): conversions | Sipser, 1.2–1.3 |
| 5 | Regular languages (cont’d): proving nonregularity; Context-free languages: grammars | Sipser, 1.4, 2.1 |
| 6 | Context-free languages (cont’d): ambiguity, Chomsky normal form | Sipser, 2.1 |
| 7 | Context-free languages (cont’d): PDAs; mid-course review, midterm examination | Sipser, 2.2 |
| 8 | Context-free languages (cont’d): conversion between CFGs and PDAs | Sipser, 2.2 |
| 9 | Context-free languages (cont’d): proving non-context-freeness; Beyond context-free: Turing machines | Sipser, 2.3, 3.1 |
| – | Fall study break | – |
| 10 | Beyond context-free (cont’d): variants of TMs, universal TMs | Sipser, 3.2 |
| 11 | Beyond context-free (cont’d): Church-Turing thesis; Decidability | Sipser, 3.3, 4.1 |
| 12 | Undecidability; Reducibility | Sipser, 4.2, 5.1 |
| 12.5 | Reducibility (cont’d) | Sipser, 5.3 |
Assignments
- Assignment 1, due Sep. 20
- Assignment 2, due Oct. 11
- Assignment 3, due Nov. 17
- 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. 18, 2023
Time: 12:30pm–1:20pm
Place: J. Bruce Brown Hall, Room 236
Content: All material from Weeks 1 to 6
Final Exam
Date: Dec. 11, 2023
Time: 2:00pm–4:30pm
Place: Mulroney Hall, Room 3022
Content: Primarily material from Weeks 7 to 12, some earlier material
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday/Wednesday/Friday, 9:30am–10:30am