COSC 340: Theory of Computation
Spring 2025
| General | |
| Python Tutorials | |
| Wikipedia |
|
| Videos | |
| Study Guides | |
| Projects |
| Week | Date | Topics | Due |
|---|---|---|---|
| 1 | Feb 3rd (Monday) | Course Introduction / Math Review For next time: Read the syllabus, download and install Java, download JFLAP, get the textbook and start reading Chapter 0 of your textbook (mostly focusing on 0.1 and 0.2), and brush up on Python. |
|
| Feb 5th (Wednesday) | Math Review For next time: Finish reviewing the material in 0.1 and 0.2. We will start with our first model of computation next time. Brush up on the Python programming language. |
||
| Feb 7th (Friday) | Deterministic Finite Automata (DFAs) For next time: Read 1.1 regarding DFAs. Start working on Project 1. |
|
|
| 2 | Feb 10th (Monday) | Deterministic Finite Automata (DFAs) For next time: Finish reading 1.1. Continue working on Project 1 (I strongly suggest to get started early, just in case you run into some problems with your code). |
|
| Feb 12th (Wednesday) | Nondeterministic Finite Automata (NFAs) For next time: Start reading 1.2. Continue working on Project 1. I’ll give you some Python tips for your project on Friday. |
|
|
| Feb 14th (Friday) | Nondeterministic Finite Automata (NFAs) For next time: Continue reading 1.2. Continue working on Project 1. You can use the Python tips I provided today, but don’t feel like you have to. |
||
| 3 | Feb 17th (Monday) | Nondeterministic Finite Automata (NFAs) For next time: Finish reading 1.2. Finish Project 1. |
|
| Feb 19th (Wednesday) | Regular Expressions (REGEX) For next time: Start reading 1.3. Finish Project 1 tonight. Project 2 will be assigned next time. |
|
|
| Feb 21st (Friday) | Regular Expressions (REGEX) For next time: Continue reading 1.3. Project 2 is now assigned. |
||
| 4 | Feb 24th (Monday) | Regular Expressions (REGEX) For next time: Finish reading 1.3. Continue working on Project 2. Check out the “RegExr” tool posted above. |
|
| Feb 26th (Wednesday) | Nonregular Languages (The Pumping Lemma) For next time: I will be at a conference on Thursday and Friday, so we will not have class Friday. Keep working on Project 2. I’m going to go ahead and post Project 3 for anyone that wants to get a head start on it. |
|
|
| Feb 28th (Friday) | SIGCSE 2025 - NO CLASS | ||
| 5 | Mar 3rd (Monday) | Nonregular Languages (The Pumping Lemma) For next time: Since I was gone, I will give you two extra days on Project 2 (it’s now due Wednesday night). So keep working on Project 2, and feel free to get a head start on Project 3. Our first exam will be Monday next week, and we will review on Wednesday. |
|
| Mar 5th (Wednesday) | Review for Exam 1 For next time: Study for Exam 1, which will be on Monday. Finish Project 2 tonight, and start on Project 3. |
|
|
| Mar 7th (Friday) | NO CLASS For next time: Exam 1 is on Monday. Turn your attention to studying for it, and then to working on Project 3. |
||
| 6 | Mar 10th (Monday) | Exam 1 For next time: Working on Project 3 (this one is trickier than Project 1!). |
|
| Mar 12th (Wednesday) | Context-Free Grammars (CFG) For next time: I’m moving Project 3 a bit to give you more time to work on it (it’s challenging). Start reading 2.1. |
||
| Mar 14th (Friday) | Context-Free Grammars (CFG) For next time: Keep working on Project 3. I’ll give some hints regarding it on Monday. Continue reading 2.1. |
||
| 7 | Mar 17th (Monday) | Context-Free Grammars (CFG) For next time: Keep working on Project 3. We will start a new model of a computer next time. |
|
| Mar 19th (Wednesday) | Pushdown Automata (PDA) For next time: Start reading 2.2. Finish Project 3. |
|
|
| Mar 21st (Friday) | Pushdown Automata (PDA) For next time: Project 3 is due tonight. Continue reading 2.2. We will finish off PDAs after break. |
|
|
| 8 | Mar 24th (Monday) | SPRING HOLIDAY - NO CLASS | |
| Mar 26th (Wednesday) | SPRING HOLIDAY - NO CLASS | ||
| Mar 28th (Friday) | SPRING HOLIDAY - NO CLASS | ||
| 9 | Mar 31st (Monday) | Pushdown Automata (PDA) For next time: Project 4 is now assigned. Finish reading 2.2. We will review for Exam 2 next time. |
|
| Apr 2nd (Wednesday) | Review for Exam 2 For next time: Start studying for Exam 2. Completing Project 4 should be helpful for reviewing some of the content. |
||
| Apr 4th (Friday) | Turing Machines (TMs) For next time: Continue studying for Exam 2 and working on Project 4. We will be spending some time on Turing Machines for a while, but you can start reading 3.1. |
||
| 10 | Apr 7th (Monday) | Turing Machines (TMs) For next time: Continue studying for Exam 2 and working on Project 4. Continue reading 3.1. I have went ahead and put up Project 5 already for those that want to get started early. |
|
| Apr 9th (Wednesday) | Turing Machines (TMs) For next time: Exam 2 is next time. Finish Project 4 (which will help you review some content), and move on to Project 5. |
|
|
| Apr 11th (Friday) | Exam 2 | ||
| 11 | Apr 14th (Monday) | Turing Machines (TMs) For next time: Continue working on Project 5. Read 3.2. |
|
| Apr 16th (Wednesday) | Decidability For next time: Continue working on Project 5. Read 3.3. I have gone ahead and posted the final project as well, for those that want to get started early. |
||
| Apr 18th (Friday) | Undecidability For next time: Continue working on Projects 5 and 6. Start reading 4.1 and 4.2. |
|
|
| 12 | Apr 21st (Monday) | Time Complexity For next time: Continue working on Projects 5 and 6. Read 7.1 |
|
| Apr 23rd (Wednesday) | Complexity Classes For next time: Finish Project 5, and start Project 6. Read 7.2. |
|
|
| Apr 25th (Friday) |
|
||
| 13 | Apr 28th (Monday) |
|
|
| Apr 30th (Wednesday) |
|
||
| May 2nd (Friday) |
|
||
| 14 | May 5th (Monday) | ||
| May 7th (Wednesday) | |||
| May 9th (Friday) |
|
||
| 15 | May 15th (Thursday) | Final Exam (8:00AM - 10:30AM) |