Course: Theory of Computing
Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.
The course is based on slide notes
I made. Please report any error you find.
A book recommended for the course is
""Introduction to automata theory, languages and computation"
by J.E Hopcroft, R Motwani and J.D Ullman.
Another recommended book is: Elements of the Theory of Computation
(2nd Edition) (Paperback)
by Harry R. Lewis (Author), Christos H. Papadimitriou
Lecture notes For a pdf file
The lecture notes contain
most of the material.
But some of the material
will be taught in class.
If you do not attend you may
face question on material
you did not learn.
Basics: Alphabets Strings and Languages
Proof by induction
and operations on sets
Equivalence relations, and its use in
defining new structures.
Many examples of finite automata.
Minimizing the number of states in an automata.
The pumping lemma and disproving
that a string is regular
Non deterministic finite automata
NDFA with epsilon moves
Equivalence between non-deterministic and
deterministic finite automata
Grammar for regular languages
The equivalence of regular languages and finite automata
Closure properties of regular sets
Pushdown automata, and non deterministic pushdown automata
Equivalence between NDPDA and CFL
Random access machines.
A program in assembly for multiplying two numbers.
Simulating a RAM via a Turing machine.
Polynomial equivalence of the simulation
of a RAM with a Turing machine
for the case the RAM commands have
Non-deterministic Turing machines
Problems that can not be solved even in super
high running time. Undecidability.
Recursively enumerable problems and languages.
Reductions: a tool to show that
Various proofs that other problems are undecidable.
The classes P and NP Is P equal NP?
Several examples of problems that
admit a polynomial solution.
Shortest path, Euler Paths, Minimum
spaning trees and flows.
Completeness in NP and a host of NPC problems
How to prove a new problem belongs to NPC? Many examples.
1) Homework: 50 percent
3)Take home exam: 50 percent.
Exercise 1: For a pdf file
Exercise 2: For a pdf file
Exercise 3: For a pdf file
Exercise 4: For a pdf file
Previous final Exam For a pdf file
Exam Fall 2011 For a pdf file