## 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. 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. 16: The second part of the lecture notes on reducibility has been posted.
- Nov. 5: The first part of the lecture notes on reducibility has been posted.
- Nov. 2: The second part of the lecture notes on decidability has been posted.
- Oct. 29: The first part of the lecture notes on decidability has been posted.
- Oct. 26: The second part of the lecture notes on Turing machines has been posted. The second assignment has also been posted. It is due by Nov. 26 at 9:15am.
- Oct. 22: The first part of the lecture notes on Turing machines has been posted.
- Oct. 15: The third part of the lecture notes on context-free languages has been posted. Information about the written report has also been posted.
- Oct. 13: There will be a special office hour to make up for the office hour cancelled due to Thanksgiving:
- Oct. 14, 11am–12pm
- Oct. 6: The second part of the lecture notes on context-free languages has been posted.
- Sep. 28: The first part of the lecture notes on context-free languages has been posted.
- Sep. 21: 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. 15 at 9:15am.
- Sep. 10: The first part of the lecture notes on regular languages has been posted.
- Sep. 7: The introductory set of lecture notes has been posted.
- Sep. 1: Welcome to the course! The first lecture is on Sep. 7.

## 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

- Assignment 1, due Oct. 15
- Topic Proposal, due Oct. 29
- Assignment 2, due Nov. 26
- Report, due Dec. 7

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