Theoretical Computer Science Study Guide

Materials and sources that might help with studying for Introduction to Theoretical Computer Science or, at ASU, CSE 355. This page may be updated in the future.

Contents

• Introduction
• Chapter 1: Regular Languages
• Chapter 2: Context-Free Languages
• Chapter 3: The Church Turning Thesis
• Chapter 4: Decidability
• Chapter 5: Undecidability/Reducibility
• Chapter 7: Time Complexity
• Other Resources
• Contributing

Introduction

Materials in this repo are included for the sole purpose to study with in preparation for the ASU CSE 355 Final Exam for the Summer 2017 semester. I have no idea if these will be useful or helpful in the future.

There are six chapters from the book Introduction to the Theory of Computation (3^rd Edition) that were covered in lecture and will be covered in the final exam. In this repo, each chapter is broken down into four sections:

• Lectures: Lectures are PDFs of Ryan Dougherty's notes for the Summer 2017 CSE 355 course. These notes should be considered the ASU gold standard and are the most important resource on this page. Along with the PDFs are Ryan's YouTube videos for each set of notes, some sectioned off by breaks, which he has graciously provided us.
• Resources: Resources are external sites or documents that cover the same topics in class. These external resources may teach concepts in different ways that may help you understand the material better. However, as they are taught differently, these resources' content must be taken with a grain of salt and you must make sure to refer to Ryan's lecture notes to make sure you understand the content as taught in class. Since TutorialsPoint and GeeksforGeeks cover virtually every topic in Theory of Computation, only the sections are listed. If a section is linked, 📓 will be placed next to it.
• Sample Problems: Sample problems consist of problems that were found on external sites. All problem sets contain solutions along with the problems. However, even though these solutions may be mostly correct, their formatting or procedures may differ than what is actually expected on the exam.
• Recap: This section recaps concepts and topics you should be familiar with after reviewing each chapter. These concepts and topics many not all appear on the exam. Thanks to user Motunrayo on Piazza for the list of topics.

The problem sets and midterm solutions from the 355 class were purposely left out of this repository as their solutions will not be made public. However, it is recommended that you go back and check these documents out for yourselves and retry these problems yourselves for optimal studying.

If you wish to make a suggestion or contribute to the repository, please see Contributing.

Chapter 1: Regular Languages

The first chapter covers regular languages including topics like DFAs, NFAs, Product & Powerset Construction, Regular Expressions, Pumping Lemma, and Regular Grammar.

Lectures

• Theory of Computing & DFAs (YouTube)
• Operations & Product Construction & NFAs (YouTube 1 2 3)
• Powerset Construction & Regular Expressions (YouTube 1 2 3)
• GNFAs & Pumping Lemma (YouTube 1 2)
• Regular Grammars (YouTube) (First half of lecture notes)

Resources

• 📓 Introduction (GeeksforGeeks)
• 📓 CFG and CFL (GeekforGeeks)
• 📓 Automata Theory Tutorial (TutorialsPoint)
• 📓 Classification of Grammars (TutorialsPoint)
• 📓 Regular Grammar (TutorialsPoint)
• From DFAs/NFAs to Regular Expressions

Note: TutorialsPoint refers to NFAs as NDFAs

Sample Problems

• DFAs Problem Set
• DFA Construction Exercises (1^st & 2^nd page)
• Pumping Lemma Problems with Proofs
• Pumping Lemma Examples
• Mixed Problems (really useful!)

Recap

By the end of this section, you should know how to

• construct a DFA for a given language.
• perform a product construction (union and intersection).
• construct a NFA for a given language.
• understand union, concat, and star operations for NFA's.
• convert a NFA to a DFA using powerset construction.
• convert a regular expression to a NFA.
• convert a NFA to a regex using GNFA's.
• use the pumping lemma to prove a language is not regular.
• give a regular grammar for a given language.
• convert a DFA into a regular grammar.
• convert a regular grammar into a NFA.

Chapter 2: Context-Free Languages

Lectures

• Context Free Grammar & Chomsky Normal Form (YouTube) (Second half of lecture notes)
• CNF Continued (YouTube)
• CNF Continued & Pushdown Automata (YouTube 1 2)
• PDA Continued & Pumping Lemma for CFLs (YouTube 1 2)
• PL for CFLs Continued (YouTube) (1^st & 2^nd pages of lecture notes)

Resources

• 📓 CFG and CFL (GeeksforGeeks)
• Pushdown Automata (GeeksforGeeks)
• 📓 Context-Free Grammars (TutorialsPoint)
• 📓 Pushdown Automata (TutorialsPoint)

Sample Problems

• Example Conversion to Chomsky Normal Form (2^nd page)
• CFG/PDA Exam Sample Solutions (includes DFA/NFA content as well)

Recap

By the end of this section, you should know how to

• write a CFG in CNF.
• convert a CFG to a PDA.
• convert a PDA to a CFG.
• apply the pumping lemma for CFLs.

Chapter 3: The Church Turning Thesis

Lectures

• Turing Machines (YouTube 1 2)
• Nondeterministic Turing Machines (YouTube) (First half of lecture notes)

Resources

• Turing Machine (GeekforGeeks)
• 📓 Turing Machine (TutorialsPoint)

Sample Problems

• Turing Machine Exam Solutions (includes topics from Chapter 4)

Recap

By the end of this section, you should know how to

• construct a Turing Machine for a given language.
• variants of Turning Machines.

Chapter 4: Decidability

Lectures

• Enumerable Languages & Encodings (YouTube) (Second half of lecture notes)
• Decidable Languages (YouTube) (First half of lecture notes)

Resources

• Recursive and Recursive Enumerable Languages (GeekforGeeks)
• Decidability (GeekforGeeks)
• Language Decidability (TutorialsPoint)

Sample Problems

No sample problems found for this chapter. Found some? Consider contributing.

Recap

By the end of this section, you should know how to

• determine the decidability of a language.

Chapter 5: Undecidability/Reducibility

Lectures

• Undecidable Languages (YouTube) (Second half of lecture notes)
• Undecidability & Rice's Theorem (YouTube)
• Rice's Theorem Continued & Linear Bounded Automata (YouTube) (First half of lecture notes)

Resources

• Undecidability and Reducibility
• Undecidable Languages (TutorialsPoint)
• Rice's Theorem (TutorialsPoint)

Sample Problems

No sample problems found for this chapter. Found some? Consider contributing.

Recap

By the end of this section, you should know how to

• determine the undecidability of a language.

Chapter 6: Advanced Topics in Computability Theory

Chapter 6 was not covered in class and, thus, will not be covered in the final exam.

Chapter 7: Time Complexity

Topics covered in Chapter 7 are extra credit topics. There may be an extra credit problem on the test asking about one of these topics.

Lectures

• Intro to P/NP (YouTube) (Second half of lecture notes)
• P/NP & Cook-Levin Theorem & CLIQUE (YouTube 1 2)

Resources

• P & NP Class (TutorialsPoint)
• Cook's Theorem (TutorialsPoint)
• NP Hard and NP-Complete Classes (TutorialsPoint)

Sample Problems

No sample problems found for this chapter. Found some? Consider contributing.

Recap

By the end of this section, you should know how to

• understand concepts of N/P, N/P-Hard, and N/P-Complete.
• understand SPACE.

---

Other Resources

• Easy Theory: Ryan Doughtery, the aforementioned professor and author of many of the notes in this repository has started a YouTube channel going over algorithms and theoretical computation. His uploads include proofs, explanations, exam solution livestreams, and more. His channel is a great companion piece to any theoretical computer science course.
• Introduction to the Theory of Computation Solutions: This is a PDF of the solutions to problems in the book. It's suggested that you go through the problem sets for each chapter in the book and attempt to work out solutions before looking at this PDF. This link may be broken in the future if the PDF is removed.
• Practice Problems for Final Exam: These practice problems are not for the ASU CSE 355 courses. However, even though these are practice problems for a NJIT final exam, a review of these problems showed they are similar to ones we've seen in class and on previous exams. Friendly reminder to take their procedures and approaches to the problems with a grain of salt and always follow the procedures taught in class.

Recitations

There were four recitations over the course of the semester. You can find the PDFs of the worksheets to these recitations in the Recitations folder on the 355 page. These PDFs don't have the solutions to the problems and there's no known video source of the recitations.

However, Ryan Dougherty has a YouTube playlist of all his recordings for his Spring 2017 CSE 355 recitations. Most videos will look identical to others since Ryan had multiple recitations every week.

Previous Final Exam Review Session

For the ASU Spring 2017 CSE 355 class, Ryan held a final exam review session during class. The video can be seen here. Do note that some of the content may have changed since.

Contributing

If you wish to help mantain, update, or fix the information in this repository, great! Please feel free to suggest external resources and sample problems, suggest typo fixes, etc. There are two ways you can contribute.

Create a new issue

Create a new issue and assign the appropriate label to it. I will get around to looking at your suggestion/fix and implement any changes if needed.

Submit a pull request

If you want to dive into the repo itself, awesome! Clone this repository, make any edits, and submit a pull request. I'll review the request and merge if I approve.