# CSCI 4602 Fall 2000

## Announcements

The final exam will be from 11:00 to 1:00 on Friday, December 8.

## Syllabus

This is a course on the theory of computing. See the syllabus for details.

MWF 1:00-2:00
TTh 9:00-10:00
MW 8:00pm-8:30>

## Assignments

Assignments will appear here as they are assigned.

• Homework 1 (due Friday, 8/25)
• Homework 2 (due Friday, 9/1)
• Homework 3 (due Wednesday, 9/5)
• Homework 4 (due Monday 9/11)
• Homework 5 (due Wednesday 9/20)
• Homework 6 (due Monday 9/25)
• Homework 7 (due Friday 9/29)
• Homework 8 (due Monday 10/8)
• Homework 9 (due Friday 10/13)
• Homework 10 (due Friday 10/20)
• Homework 11 (due Friday 11/3)
• Homework 12 (due Friday 11/15)
• Homework 13 (practice only)
• ## Practice questions for quizzes

Here are the practice questions for quizzes that have been posted.
• Practice questions for quiz 2
• Practice questions for quiz 3
• Practice questions for quiz 4
• Practice questions for quiz 5
• ## Lecture summaries

1. [8/16] I handed out and briefly discussed the syllabus. We began going over Chapter 0 of Sipser.

2. [8/18] We went over examples of proofs. Some important kinds of proofs are
1. forward proofs
2. backward proofs
3. proof by contradition
4. proof by cases
5. constructive existence proofs
6. nonconstructive existence proofs
7. proof by induction

3. [8/21] We finished going over proofs, and began Chapter 1 of Sipser, on finite state computation. We went through the fundamental ideas of computation, and the concept of a finite state machine. A finite state machine reads a string over a given alphabet, and produces a yes or no answer. It uses a finite amount of memory, regardless of the size of the input.

[8/23] We formally defined finite state machines and began to look at their properties. You should continue reading Chapter 1 of Sipser. I gave homework assignment 1, due 8/25.

4. [8/25] We went over a solution to the homework, did another example of finite state machine design, and began to look at regular operations.

5. [8/28] We looked more at regular operations, and defined regular expressions. Homework exercise 2 is due Friday 9/1.

6. [8/30] We began to study the tools needed to show that regular expressions and finite state machines have equivalent descriptive power. The fundamental concept is nondeterminism. Nondeterministic finite automata (NFAs) are discussed in the text.

7. [9/1] We demonstrated conversions between different ways of describing languages. The conversions are as follows.
```     Regular languages --> NFA(epsilon) <--> NFA <--> DFA
```
The only remaining conversion is to show how to convert an NFA(epsilon) to a regular expression. Homework exercise 3 is due Wednesday, 9/6.

8. [9/6] We spend most of the lecture going over exercises and doing review of principles of finite state machines and regular expressions.

9. [9/8] We showed how to convert an NFAepsilon to an equivalent regular expression, and look at closure results (such as the result that, if L is regular then LR is also regular). Homework exercise 4, due 9/11, was assigned.

10. [9/11] We reviewed exercises and material on regular languages.

11. [9/13] Quiz. We looked at a method for proving that a language is not regular.

12. [9/15] We did more examples of proving that a language is not regular. Exercise 5 was assigned.

13. [9/18] We began chapter 2 in the text, on context-free languages.

14. [9/20] We looked more at context-free grammars, and proved that any regular expression can be converted into an equivalent context-free grammar.

15. [9/22] We looked at push-down machines, and did part of the proof of the theorem that nondeterministic push-down machines can recognize all context free languages, and only context-free languages.

16. [9/25] We looked more at context-free grammars and push-down machines. We showed that a language is context-free by designing a push-down machine for it.

17. [9/27] We turned to general computation, and began to accumulate evidence for the Church/Turing Thesis. We are beginning Chapter 3 of Sipser.

18. [9/29] We looked more at the Church/Turing Thesis and the notion of computability.

19. [10/2] Quiz 2. We looked at some computable problems involving finite automata.

20. [10/4] We asked how a problem might be shown to be uncomputable. We used diagonalization to show that the halting problem is undecidable.

21. [10/6] We looked more at diagonalization, and showed that the language K = {p | p eventually halts on input p} is undecidable. We also began to look at reductions between problems, and showed that K reduces to the halting problem.

22. [10/9] We continued to look at reductions between problems.

23. [10/13] We did more examples of reductions.

24. [10/16] We proved Rice's theorem: Every nontrivial transparent set of programs is undecidable. A set S of programs is transparent if, whenever two programs p and q are equivalent, either p and q are both in S or both not in S.

25. [10/18] We defined and study the Turing recognizable languages. They are also called the recursively enumerable languages.

26. [10/20] We defined the m-complete languages and showed that that halting problem is m-complete.

27. [10/25] We discussed Post's correspondence problem, and showed that it is Turing-recognizable.

28. [10/27] Quiz. We continued looking at Post's correspondence problem after the quiz.

29. [10/30] We finished looking at computability.

30. [11/1] We began the study of complexity theory, where the cost of performing a computation is taken into account.

31. [11/3] We went over exercises and looked at polynomial time computation, and saw a poor algorithm for computing greatest common divisors.

32. [11/6] We showed that the problem of computing greatest common divisors is solvable in polynomial time, and will ask how a problem might be shown not to be solvable in polynomial time.

33. [11/8] We defined nondeterministic polynomial time computation, and the class NP of decision problems that are solvable nondeterministically in polynomial time. We define polynomial time reductions and the notion of NP-completeness, and looked at a few properties of polynomial time reductions.

34. [11/10] We went through a sketch of a proof of the Cook/Levin theorem, that the satisfiability problem is NP-complet.

35. [11/13] We showed that 3-SAT is NP-complete and began looking at the clique problem.

36. [11/15] We answered questions about homework and showed how to reduce the 3-SAT problem to the clique problem, thus completing the proof that the clique problem is NP-complete.

37. [11/17] Quiz. We will also see another NP-complete problem.