Topics Covered in CSIT 443

1) Strings and languages.

2) Historical overview.

3) Finite automata.

4) Deterministic finite automata (DFA).

5) Minimizing DFA.

6) Nondeterministic finite automata (NFA).

7) Nonregular languages.

8) Equivalence of NFA and DFA: converting NFA to DFA.

9) Pushdown automata.

10) Friday, Mar 2, 07: Finish PDA, solution of first 3 assignments.

11) Monday, Mar 5, 07: Quiz, Turning machines (TM).

12) Multitape TM; Nondeterministic TM; Enumerators.

13) Friday, Mar 30, 07: Finish TM’s and begin Chapter 4; Algorithms; decidable; undecidable; Hilbert’s 10^th problem.

14) Decidable languages (concerning regular languages and contest-free languages).

15) The Halting Problem.

16) Undecidable languages.

17) Turing-unrecognizable languages.

18) Reducibility; computable functions.

19) Class P, class NP, class NPC, class L, class NL, class PSPACE, class L, class NL, class coNL, class NLC.

20) Many other topics from time and space complexity and many examples from the classes mentioned above.

21) Other topics.

22) Topics skipped: Review of sequences, sets, multisets, graphs, prime numbers, Boolean logic, proof techniques, functions, relations, big O and small o notation, analyzing algorithms; Regular expressions and languages; Contest-free grammar/languages.

Remark: In addition to almost all of the first 8 chapters of the textbook, I covered/will cover a lot of material from other books. The examples (as it’s the case in my other classes) are usually not from the book in order for students to have more examples to look at.