**Course:** Theory of Computing

Spring 2015

**Given by:**
Guy Kortsarz.

**Office: **319 Business and Science Bldg.

**Office hours:**

By appointment

**Url:**

http://crab.rutgers.edu/~guyk/courses.html

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.
**

Credit:

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
**