Course: Theory of Computing
Spring 2015

Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.

Office hours:
By appointment


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
Prentice Hall
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.

Subjects covered:

Basics: Alphabets Strings and Languages
Proof by induction
and operations on sets

Equivalence relations, and its use in
defining new structures.
Finite Automata.
Many examples of finite automata.
Minimizing the number of states in an automata.
Regular languages
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
Context-free languages
Pushdown automata, and non deterministic pushdown automata
Equivalence between NDPDA and CFL
Turing machines
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
no multiplication
Non-deterministic Turing machines
Problems that can not be solved even in super
high running time. Undecidability.
Recursive languages
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