** EXERCISE 4 is DUE IN 24 of April **

The class of the 24 ** It is mandatory to attend the class
at the 24 in 09:00**

In the 24, You will fill feedbacks, and then we read the home exam.

You can return the home exam any time between

the 27, from 09:00 to 17:00.

In such a case please put the exam in my mail box

in the room of Kelly.

Spring 2015

By appointment

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

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.

Proof by induction

and operations on sets

defining new structures.

that a string is regular

deterministic finite automata

The equivalence of regular languages and finite automata

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

high running time. Undecidability.

Recursive languages

Recursively enumerable problems and languages.

Various proofs that other problems are undecidable.

Several examples of problems that

admit a polynomial solution.

Shortest path, Euler Paths, Minimum

spanning trees and flows.

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