Lectures: MW 10:00 - 11:15, 217 College Center. Office Hours: MTW 12:30 - 2:00, or by appointment.
Text: Introducing the Theory of Computation by Wayne Goddard, Jones and Bartlett Publishers, 2009.
Description: A theoretical treatment of what can be computed and how fast it can be done. Applications to compilers, string searching, and control circuit design will be discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines will be analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course.
Exams: There will be six quizzes and I will count the best five (25%). There is one final examination (35%). The final will be December 6, Friday, 9 AM.
Assignments: Homeworks are worth 40% of your grade. You may do these with a partner, and one grade will be given to both people in each group. Read our department's academic integrity guidelines before you hand in any written work.
Goals: To appreciate computer science as a discipline with an elegant formal foundation with an uncanny number of practical applications. To understand abstract computational models, write machine “programs” for each one, and prove theorems with regard to their power. To appreciate and prove that some problems require more time and space for a computer solution, and some are undecidable.
Special Dates: There are no Jewish holidays on class days this semester. If there is any need to cancel a class, then instead of lecture, there will either be a zoom lecture, an assigned recorded video lecture, a quiz, or a TA homework review.
Video Links: Brilliant Video About Decidability Index of all ADUni Lectures YouTube of my Theory Lectures
Handouts: Syntax Diagrams for Pascal Closure Properties of Regular Sets, CFLs, DCFLs, and other Languages
Other Fun Links: Alan Turing Page Turing Award Funny Halting Poem Brzozowski's FSM Minimization Algorithm
A Real Turing Machine Halting Problem Video
Assignment_1 Assignment_2 Assignment_3 Assignment_4
Introduction: Languages, Grammars, and Automata (Machines). Fundamental connection to computer science. Applications. Reading: 5
Regular Sets: Finite State Machines, Regular Expressions, and Regular Grammars. Reading: 1, 2, 8.1
Non-determinism and equivalence of NFSM's to DFSM's. Other variants of FSM's. Reading: 3
Closure Properties of Regular Sets - a constructive review. Encoding FSMs, diagonalization and a non-regular set. Reading: 4.1- 4.2.
The Pumping Lemma - How to show that a set is not Regular. Reading: 4.3
Decision Algorithms for FSM's. (Problems whose inputs are FSM's.) Decidability. Reading: 4.2
Context Free Languages: Context Free Grammars and Applications, Syntax Diagrams. Reading: 6
Pushdown Machines - Deterministic versus non-deterministic. Reading: 7
Chomsky Normal Form - Three applications. Equivalence of NPDM and CFL's. Reading: 8, 9.1
Closure Properties of CFL's and DCFL's. Decision Algorithms for CFL's. Applications to compilers. Reading: 10.1, 10.2
The CFL Pumping Lemma - Showing that a set is not context free. Reading: 9.2
Turing Machines and Variants: Multi-tape, non-determinism, multidimensional, 2-stack machines. Reading: 11, 12
Decidability: The Halting Problem. Reductions and more Undecidable problems: Post's Correspondence Problem, CFL equivalence, CFL ambiguity. Reading:13, 14, 15
Computational Complexity - Measuring the time and space requirements of decidable problems. Reading: 17, 18
The computational classes P and NP. The concept of an NP-Complete Problems. Reductions revisited. Reading: 17.6, 19