Course Outline:

I. Models of computations. Computational complexity. Parallel computation.

II. General Computational Models:

1. Logic Circuits: Straight-Line Programs and Circuits, Normal Form Expansion of Boolean Functions, Specialized Circuits, Prefix Computations. Addition.

2. Machines with Memory: Finite State Machines, Simulating FSMs with Shallow Circuits, RAM machines, Turing machines, Circuit simulation of a Turing machine.

3. Selected Topics on FSMs: Morphisms of finite automata, minimization algorithm of complete finite automata, minimization algorithm of incomplete automata, alternating finite automata, synthesis algorithms for family of regular languages (generalization of Brzozowski's algorithm).

4. Computability: Techniques of Turing Machine design, recursive functions and Turing machines; functions computed by Turing machines, non-deterministic and alternating Turing machines, time and space complexity of Turing machine computations, halting problem; examples of unsolvable problems about Turing machines.

III. Computational complexity:

5. Complexity Classes: Relations among complexity measures, time and space-bounded Turing machines, P and NP computations, NP-completeness, P=NP question, definitions and examples of P-complete and NP-complete problems, boundary between class P and NP, examples of P-SPACE complete problems, circuit and PRAM model of computation, efficiently parallelizable languages.

6. Space-Time Tradeoffs:

Pebble game, straight-line vs. branching programs, time-space tradeoffs.

7. Memory-Hierarchy Tradeoffs:

Red-blue pebble game,the memory hierarchy pebble game,hierarchical memory model.

Examples of problems that will be discussed:

1. Selected Topics on Finite State Machines:

- elements of FSM representation (characteristic semigroup, notation)

- PLA effective implementation of FSM using NDFA

- morphims of FSM; sequential algorithm to compute homomorphisms of FSM; parallelization

- decomposition of FSM: algorithm to compute all SP partitions of a FSM

- Hopcroft’s minimization FSM algorithms with implementation and experiments.

- Shallow implementations of FSM using prefix circuits

- Relationships between FSM, RAM programs, and TMs; PRAM model.

2. NP-completeness of decision problems:

- modeling of decision problems by NDTM and DTM (PARTITION problem)

- acceptance of recursive functions by DTM (multiplication of two numbers).

- Cook theorem with proof of NP-completeness for SAT decision problem

- Technique to proof NP-completeness using a concept of polynomial reducibility

- NP-complete problems with proofs of NP-completeness (3-SAT, Vertex Cover, Clique, Map coloring, Graph Coloring, Timetable and Restricted Timetable problem)

- Subproblems of NP-complete problems that have polynomial algorithms (2-SAT is polynomial)

- implications of reducibility of decision problems (Map coloring vs. SAT, neural function vs. SAT)

- Dynamic programming algorithm for TSP.

3. Examples of fast parallel algorithms:

- parallel prefix computation in polylogarithmic time O(log n)

- carry-lookahead addition of numbers in polylogarithmic time

- bitonic sort in polylogarithmic time O(log² n)

4. P-complete problems and PSPACE-complete problems:

- Quantified SAT problem as a PSPACE-complete problem

5. Undecidability/Unsolvability:

- logic paradoxes, 3x+1 problem, meaning of unsolvability and undecidability

- halting problem as a generic undecidable problem

- decidable and undecidable problems for regular languages, FSM, CFG, PGA, and TM

Evaluation Procedures:
Mid-term examination	1 x 25	25
Final examination	1 x 25	25
5 Homework Assignments	5 x 5	25
2 Programming Assignments	2 x 12.5	25
	TOTAL =	100 pts