Students enrolled should also have access to the EdDiscussion board for the class, which will be used frequently. Homework solutions will appear on the resources page there. Click the downward-facing arrow in the top-right of the EdDiscussion window to access those.
Unit 1: Regular Languages. This also covers some mathematical preliminaries we'll discuss in the first week. This is expected to cover weeks one and two, plus Monday of week three.
Pumping Lemma Supplemental. We will cover this on Friday of week two and Monday of week three. We will likely not finish this entire handout, but the remaining constitute good practice questions. The last question is particularly challenging.
Unit 3.1: Intro to Turing Machines. This document is for the lecture on Monday, May 8; this topic is not on the exam on May 10. The first two digital pages is approximately the lecture on May 8, and the second two digital pages are a reading assignment that will help with context for the lecture on Friday May 12.
Unit 3.2: Intro to Decidability. This covers lecture on Friday, May 12. The first two digital pages are approximately the topic, and the next two cover an extension that we may or may not get to on Friday. If we do not, then we definitely will on Monday the 15th. We are approaching the topics that I think are the most philosophically interesting in the entire Computer Science curriculum; I hope you are as excited as I am!
Problem Set 1: Regular Languages. This is tentatively due Monday of week 3 (April 17), but that may change. If it changes, it will be due later not earlier. This is now due Monday night, not Monday morning. Please attempt the problem set before Monday's lecture.
These look a lot like homework, but I will not be collecting them. Solutions will be posted on Ed Discussion under "resources." I encourage you to use these as additional practice problems.
ReinforcementExtra Practice 0 covers counting problems, which I think can help you review for some week one material.
Extra Practice 6 is one more question about material from the unit 4 of the class, from a different textbook. I had intended to do this as an exercise in class on Monday the 5th, but we did not have the time to do so. It is still a great practice problem.
Lecture 21 covered that Independent Set and Vertex Cover are NP-complete. Note that the lecture slides are not complete proofs: how a proof is presented as a lecture and how one would write a proof are not identical.
Lecture 22 covered that Set Cover and 3-Color are NP-complete. We also began the proof that Hamiltonian Path is NP-complete. Note that the lecture slides are not complete proofs: how a proof is presented as a lecture and how one would write a proof are not identical.
Lecture 23 finished the proof that Hamiltonian Path is NP-complete. We also began the proof that Subset Sum is NP-complete. Note that the lecture slides are not complete proofs: how a proof is presented as a lecture and how one would write a proof are not identical.
Lecture 24 finished the proof that Subset Sum is NP-complete. Note that the lecture slides are not complete proofs: how a proof is presented as a lecture and how one would write a proof are not identical.
Unit 3: Decidable
Lecture 15 introduces Turing Machines (not Turning Machines). The second half of these slides covers what the next lecture would be, covering the Church-Turing Thesis, but because we are a little pressed for time, I am not using a lecture period to discuss it. Notes about it are in the handout for Unit 3.1, and the slides are attached as part of this.
Lecture 16 introduces decidability. Note that this PDF includes slides we didn't go over in lecture: I brought more with me just in case. We'll cover these as part of Monday's lecture (Lecture 17).
Lecture 17 introduces undecidability. This looks different from previous slides for reasons; amazingly, the slides I wanted to have with me were the second half of Lecture 16's, above (in case you're curious).
Lecture 19 covers LBAs. For the last question/slide, there is an in-depth explanation on EdDiscussion, posted May 21.
Unit 2: Context Free Languages
Lecture 8: introduction to context-free grammars. We will finish this topic and then begin push down automata on Monday.
Lecture 9: introduction to push-down automata. The last two slides are problems I wanted to get to in class, but I did not time it correctly. Matt will cover these in discusion tomorrow (Tuesday); please attempt them before then for best results.
Lecture 10 begins to show that CFGs and PDAs are equivalent (recognize the same set of languages).
Lecture 11 finishes that proof. I recommend, as reinforcement, taking a PDA (3-4 states are fine) and creating a CFG for the same language using the technique described in these slides.
Lecture 12 introduces the pumping lemma for context free languages. We will finish this on Wednesday, before going into closure properties.
Lecture 13 finishes pumping lemma and begins closure properties.
Lecture 14 covers closure properties of context free grammars.
Unit 1: Regular Languages
Lecture 1 : not the syllabus slides, just the part about functions. If you are viewing this and lecture 2 is posted below, it contains this too, so you probably don't want this file.
Lecture 2 : we see even more sets are countably infinite (equal in size to the natural numbers). Just wait until Friday...
Lecture 3 : finishing set theory, starting formal languages and automata.
Lecture 4 part 2 : NFAs (non-deterministic finite automata). We did not get to question 22 (the last two pages of the PDF) in lecture; give them some thought, we will cover them next lecture.
Lecture 5 : equivalences. In this, we prove that NFAs/DFAs (which we saw last time are equivalent) are equivalent to regular expressions in terms of what they can recognize. Questions 25 and 26 were not covered in lecture due to time, although they constitute good extra practice questions.
Lecture 6 : infinite regular languages. This is where we introduced the pumping lemma for regular languages.
Monday week 3 -- this is a continuation of Lecture 6, in which we did a subset of the extra practice questions to review for Wednesday's quiz.
Topic Exam 1: Regular Languages. There are three diagnostic exams. The real exam will have the same format. I recommend taking at least one of these in as close to exam-like circumstances as you can (preferably a printout and taken in a quiet area) to diagnose how well prepared you are for the test. The rest can either be used the same way or as additional practice questions. Two of the three are either entire or parts of former exams I have given in CompSci 162.
Topic Exam 2: Context Free Languages. There are three diagnostic exams, although there are two formatting choices. Diagnostic i has the same set of questions in each format; the difference is presentation. If you want to opt into the alternate format, there is a form on the Ed Discussion board to use.