CSCI 541: Theory of Computing (Fall 2021)

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

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

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, 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 Context-free languages (cont’d): non-context-freeness Sipser, 2.3
7 Beyond context-free: Turing machines, variants Sipser, 3.1–3.2
8 Beyond context-free (cont’d): Universal TMs, Church-Turing thesis; Decidability Sipser, 3.3, 4.1
9 Undecidability; Reducibility Sipser, 4.2, 5.3
Fall study break
10 Reducibility (cont’d) Sipser, 5.1
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

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. 5, 2021, end of class
Due Date: Oct. 6, 2021, beginning of class
Content: All material from Weeks 1 to 4

Quiz 2

Release Date: Nov. 2, 2021, end of class
Due Date: Nov. 3, 2021, beginning of class
Content: All material from Weeks 5 to 8

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