# Theory of Computing

CSE 30151 | Spring 2022

## Overview

#### Course Description

Introduction to formal languages and automata, computability theory, and complexity theory with the goal of developing understanding of the power and limits of different computational models. Topics covered include:

- regular languages and finite automata
- context-free grammars and pushdown automata
- Turing machines; undecidable languages
- the classes P and NP; NP completeness

#### Prerequisites

Discrete Math (CSE 20110) and Data Structures (CSE 20312/24312). You especially need to be comfortable with sets, tuples, functions, relations, and graphs; and writing proofs by contradiction and by induction.

- Time
- Tue/Thu 2-3:15pm
- Location
- DeBartolo Hall 138
- Instructor
- Brian DuSell

#### Links

## Schedule

Please do the assigned readings from the textbook before each class. Unless otherwise stated, each assignment is due at 11:59pm on Thursday of the week in which it is listed.

Unit | Date | Topic | Reading | Due |
---|---|---|---|---|

Jan 11 | Welcome | |||

Jan 13 | Strings, languages, and proofs | 0 (p. 1-25) | Survey | |

I | Jan 18 | Finite automata | 1.1 (p. 31-47) | |

Jan 20 | DFAs = NFAs | 1.2 (p. 47-63) | HW1 | |

Jan 25 | Regular expressions | 1.3 (p. 63-69) | ||

Jan 27 | REs = NFAs | 1.3 (p. 69-76) · DFA Min. | HW2 · PA Team | |

Feb 1 | Non-regular languages | 1.4 (p. 77-82) | ||

Feb 3 | Non-regular languages | PA1 | ||

Feb 8 | Review | Study Guide | ||

Feb 10 | Midterm Exam 1 | |||

II | Feb 15 | CFGs | 2.1 (p. 101-111) | |

Feb 17 | PDAs | 2.2 (p. 111-116) | HW3 | |

Feb 22 | CFGs = PDAs | 2.2 (p. 117-125) | ||

Feb 24 | More on CFLs | 2.4 (p. 130-131) | HW4 | |

Mar 1 | Non-CFLs | 2.3 (p. 125-129) | ||

Mar 3 | Non-CFLs | PL for CFLs | ||

Spring Break | ||||

III | Mar 15 | Turing machines | 3.1 (p. 165-175) | |

Mar 17 | TM variants | 3.2 (p. 176-187) | PA2 · HW5 | |

Mar 22 | Review | Study Guide | ||

Mar 24 | Midterm Exam 2 | |||

Mar 29 | Recognizers, Deciders, and NTMs | 4.1 (p. 193-201) | ||

Mar 31 | Universal TM | 4.2 (p. 201-210) | HW6 | |

Apr 5 | Undecidability | 5.1 (p. 215-220) | ||

Apr 7 | Reducibility | 5.1-5.3 (p. 220-238) | PA3 | |

IV | Apr 12 | Mapping reducibility, PCP, and time complexity | 7.1-7.2 (p. 275-291) | |

Apr 14 | P and NP | 7.3 (p. 292-298) | HW7 | |

Apr 19 | NP-completeness | 7.4 (p. 299-311) · NP-completeness | ||

Apr 21 | Polynomial reductions | 7.5 (p. 311-322) | ||

Apr 26 | Optional review session 7-8:30 PM in DeBartolo Hall 138 | Study Guide | HW8 · All late assignments | |

Reading Days | ||||

May 4 | Final Exam10:30 AM-12:30 PM in DeBartolo Hall 138 |

## Staff

- Instructor

Brian DuSell

bdusell1@ - Graduate TA

Gang Liu

gliu7@ - Graduate TA

Mahsa Mitcheff

mmitchef@ - Graduate TA

Ken Sible

ksible@ - Undergraduate TA

Jonathan Abbott

jabbott4@ - Undergraduate TA

Vito Lin

vlin2@ - Undergraduate TA

Sam Manfreda

smanfred@ - Undergraduate TA

Colin McDonald

cmcdona8@ - Undergraduate TA

Luke Miller

lmille24@ - Undergraduate TA

Gabriel Silva Simões

gsilvasi@

### Office Hours

Day | Time | Person | Location |
---|---|---|---|

Mon | 4-5 | DuSell | Fitzpatrick 150A |

5-7 | Mitcheff | Fitzpatrick 150B | |

7-8 | Miller | Fitzpatrick 150 | |

Tue | 3:30-5:30 | Manfreda | DeBartolo B011 |

5:30-6:30 | Liu | Fitzpatrick 150B | |

7:30-9:30 | McDonald | DeBartolo B011 | |

Wed | 3-5 | Lin | Fitzpatrick 150 |

5-7 | DuSell | Fitzpatrick 150A | |

7-8 | Miller | Fitzpatrick 150 | |

8-10 | Simões | DeBartolo B011 | |

Thu | 4-6 | Abbott | DeBartolo B011 |

6-8 | Sible | Fitzpatrick 150B |

## Textbook

The following textbook is required for this course:

Michael Sipser, Introduction to the Theory of Computation, 3rd Edition

The 3rd edition of this book has both a domestic hardcover version and an international softcover version. Although the numbering of problems differs between the two, their contents are otherwise the same. You may use either one for this course, but please ensure that in either case, you get the 3rd edition and not an earlier edition.

## Acknowledgments

The design and materials for this course were strongly influenced by past instructors, including: Dr. David Chiang, Dr. Marina Blanton, Dr. Peter Kogge, and Dr. Satyaki Sikdar.