Materials and sources that might help with studying for the ASU CSE 355 Summer 2017 Final Exam. This page will continually be updated with new content.
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. I just want to do good on the final, man.
There are six chapters from the book Introduction to the Theory of Computation (3rd Edition) that were covered in lecture and will be covered in the final exam. Each chapter is broken down into three 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 for proper notes.
- 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.
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.
The first chapter covers regular languages including topics like DFAs, NFAs, Product & Powerset Construction, Regular Expressions, Pumping Lemma, and Regular Grammar.
- 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)
- Finite Automata (GeekforGeeks)
- NFA to DFA Conversion (GeekforGeeks)
- Pumping Lemma(GeekforGeeks)
- Regular Expressions, Regular Grammar and Regular Languages (GeekforGeeks)
- From DFAs/NFAs to Regular Expressions
- DFAs Problem Set
- DFA Construction Exercises (1st & 2nd page)
- Pumping Lemma Problems with Proofs
- Pumping Lemma Examples
- Mixed Problems (really useful!)
- 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) (1st & 2nd pages of lecture notes)
- Turing Machines (YouTube 1 2)
- Nondeterministic Turing Machines (YouTube) (First half of lecture notes)
- Enumerable Languages & Encodings (YouTube) (Second half of lecture notes)
- Decidable Languages (YouTube) (First half of lecture notes)
- 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)
While there is a section in the book for Chapter 6, there appears to be no lecture notes for this content, leading me to believe this will not be covered on the final.
- Intro to P/NP (YouTube) (Second half of lecture notes)
- P/NP & Cook-Levin Theorem & CLIQUE (YouTube 1 2)
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.
For the 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.
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 and assign the appropriate label to it. I will get around to looking at your suggestion/fix and implement any changes if needed.
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.