Automata And Computability Kozen Homework Solutionsl
Vinnie Breidenthal
To study the fundamental abilities and limits of computation, in a mathematically rigorous way. This will be broadly subdivided into three units:automata theory, computability theory, and computational complexity theory.
CS 520 - Introduction to Theory of Computing Fall 2009 Course DescriptionThis course provides an undergraduate-level introduction to the theory of computing. The objective is two-fold. First, gaining an understanding of the nature of computation, its capabilities and its limitations, and obtaining the ability to reason rigorously about them; second, acquiring the mathematical foundation for applications of these insights in other areas of computer science. We will cover elements of automata theory and formal languages, computability theory, complexity theory, and cryptography. These topics have applications in algorithm design, programming languages and compiler construction, artificial intelligence,hardware and network protocols, and security.TextMichael Sipser, Introduction to the Theory of Computation, 2ndedition, 2006.Prerequisites Math 240 (Discrete Mathematics, especially proofs by induction and basicnotions of set theory, logic, discrete probability theory, and graph theory), and CS 367 (Data Structures, especially familiarity with algorithms and their complexity).A self-calibration homework will be handed out in the first lectureand there will be a special review session T 9/8, 7-9pm, in 1325 CS.Course Work
- Homework (50%).There will be an assignment every other week. Expect the problems to bechallenging so start early. You are allowed to discuss the problems in group but youshould write out the solutions on your own and give credit to yourcollaborators. No sources other than the course material, the instructor, the TA, and your fellow students in the course are allowed.
- Exams: Midterm (20%) M 10/19, 7:15-9:15pm,and Final (30%) N 12/20, 10:05am-12:05pm.Both exams are closed book and closed notes.
- Kenneth Rosen, Discrete Mathematics and Its Applications, 5th edition, 2002.
- Michael Sipser, Introduction to the Theory of Computation, 2nd edition, 2005.
- John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd edition, 2000.
- Dexter Kozen, Automata and Computability, 1997.
- Harry Lewis and Christos Papadimitriou, Elements of the Theory of Computation, 2nd edition, 1997.
- Christos Papadimitriou, Computational Complexity, 1994.
- Uwe Schöning and Randall Pruim, Gems of Theoretical Computer Science, 1995.