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

- Sep. 15: The first assignment has been posted. It is due by Oct. 1 at 11:15am.
- Sep. 10: The first part of the second set of lecture notes has been posted.
- Sep. 8: The first 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: regular expressions, proving nonregularity | Sipser, 1.3–1.4 |

4 | Context-free languages: pushdown automata, grammars | Sipser, 2.1–2.2 |

5 | Context-free languages: ambiguous grammars, proving non-context-freeness | Sipser, 2.1, 2.3 |

6 | Mid-course review, midterm examination | — |

7 | Beyond context-free: Turing machines, variants | Sipser, 3.1–3.2 |

8 | Decidability | Sipser, 4.1 |

9 | Undecidability, reducibility | Sipser, 4.2, 5.1–5.3 |

— | Fall study break | — |

10 | Time complexity: algorithm analysis, P, NP | Sipser, 7.1–7.3 |

11 | Time complexity: NP-completeness, reducibility | Sipser, 7.4–7.5 |

12 | Space complexity: PSPACE, L, NL; course review | Sipser, 8.1–8.2, 8.4 |

## Assignments

- Assignment 1, due Oct. 1
- Assignment 2, due Oct. 22
- Assignment 3, due Nov. 19
- 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.

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