NOTE: THE FINAL EXAM IS POSTED
Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.
Office hours: Wednesday I will see you at any hour I am in the office (unless I have a deadline).
Url:
http://crab.rutgers.edu/~guyk/courses.html
Book of the course
Elements of the Theory of Computation (2nd Edition) (Paperback)
by Harry R. Lewis (Author), Christos H. Papadimitriouo
Prentice Hall.
You do not need to buy the book. I will teach by slides
that will contains everything you need to know.
The lecture notes: For a pdf file
Remark: The lecture notes are partial for now. The last part of the lecture notes will be given soon
Subjects covered:
Basics: Alphabets Strings and Languages
Proof by induction
and operations on sets
Finite Automata
and regular languages
The pumping lemma and disproving
that a string is regular
Finite automata with epsilon moves
and non-deterministic finite automata
Equivalence between non-deterministic and
deterministic finite automata
Grammar rules for regular languages and the equivalence to automata
Closure properties of regular sets
Context-free languages and derivation trees
Pushdown automata
Equivalence between PDA and CFL
Turing machines
Random access machines and
the equivalence to Turing machines
Decidable and undecidable problems.Reductions
Rice theorem
Credit:
1) Homework: 20% (there will be three exercises)
2) Midterm 30%
3) Exam: 50%
Exercise 1 For a pdf file
Exercise 2 For a pdf file
The Mid term For a pdf file
Exercise III For a pdf file
Final Exam For a pdf file