MA/CSSE 474 Theory of Computation - Winter 2013-14 (201420)

• A book that I recommend for every Computer Scientist's library:
             Grimaldi, Ralph P. Discrete and Combinatorial Mathematics (Addison-Wesley, 2003)
• Other good books on Automata and Computation:
• Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman (Addison-Wesley, 2001)
• Introduction to the Theory of Computation by Michael Sipser (Thomson Course Technology-Hill, 2006)
• Languages and Machines by Thomas A. Sudkamp (Addison-Wesley, 2004)

Course Description

RHIT Catalog Description

Students study mathematical models by which to answer three questions: What is a computer? What limits exist on what problems computers can solve? What does it mean for a problem to be hard? Topics include models of computation (including Turing machines), undecidability (including the Halting Problem) and computational complexity (including NP-completeness).

Course Learning Outcomes (adopted by CSSE department, September 2009)

Students who successfully complete this course should be able to:

1. Explain the concepts of finite automata and regular languages.
2. Design deterministic and nondeterministic automata to recognize specified regular languages.
3. Design regular expressions to generate specified regular languages.
4. Explain the concepts of context-free and context-sensitive grammars.
5. Design context-free grammars to generate specified context-free languages.
6. Design push-down automata to recognize specified context-free languages.
7. Design Turing Machines to recognize languages and compute functions; explain the significance of the Universal Turing machine.
8. Explain the Church-Turing thesis and its significance.
9. Determine a language's location in the Chomsky hierarchy (regular, context-free, context-sensitive, recursively enumerable languages).
   
10. Prove that a language is in a specified class and that it is not in the next lower class.
11. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
12. Explain why some problems have no algorithmic solution.
13. Provide examples that illustrate the concept of undecidability
14. Prove that a problem is undecidable by reducing a classic known undecidable problem to it.
15. Define the classes P and NP.

Prerequisites

CSSE 230   Data Structures and Algorithms                MA 375  Discrete and Combinatorial Algebra II

Note: The course actually depends much more on MA 275 than on CSSE 230 or MA 375.  If you are very comfortable with the contents of chapters 2-7 of Grimaldi's book, and if mathematical induction is "second nature" to you, you should be fine.  If not, you may have to work extra-hard in this course for the first few weeks.  The MA 375 exposure to finite state machines will also be helpful, but we will take a slightly different approach in this course.

Appendix A of the textbook contains a review of most of the material you should know from those courses, some of it in slightly more depth than Ralph Grimaldi's book (for example, first-order logic).  In addition, you should know the basics of Finite State Machines (Grimaldi Chapter 6 and Section 7.5), although the perspective on FSMs in this course will be a bit different. 

The main things that you should bring into this course

• enthusiasm, curiosity, perseverance, and a "can do" attitude, especially concerning proofs and mathematical  terminology (if you don't pay attention to terminology, you're dead in this course!)
• willingness to work cooperatively with other students in the classroom to enhance the learning environment for everyone
• determination to consistently devote enough time to the course
• commitment to read the textbook and get all you can from it, so that more class time can be spent on problem solving
• commitment to avoid getting behind, and to ask questions when you don't understand something
• a reasonable comfort level with elementary discrete mathematics (especially proofs).  Appendix A of the Rich book is a good benchmark.  If you came to the course already comfortable with about 70% of that appendix, you should be fine.

Assignments (quizzes, Homework, etc.)

Some days there will be in-class note sheets, similar to in-class quizzes in other CSSE courses.  You will not be required to turn these in.  I will provide solutions for some of them.

When I give a reading assignment, I seriously expect you to read it. In-class discussions will assume that you have done the reading and understood the "easy stuff" before class. Sometimes there will be reading quizzes based on the definitions and simple concepts form a reading assignment.  You may of course ask about any details that you do not understand. When there is a reading quiz, you must submit a  hard copy at the beginning of class.  You can print it and write on it, or do it electronically and then print it.

I will assign many written problems, most of them from the textbook.  These will typically be short thought problems, mathematical analyses, formal proofs, or machine-design exercises. I expect you to think through them carefully and write your answers legibly and clearly (if you prefer, type them and print them). On some problems, not only the correctness but also the quality of your solution will determine your grade. Some of the problems will be straightforward practice with concepts from the course; others will require creative solutions. Don't put them off until the last minute! Get them into your mind soon after they are assigned, so you have an opportunity to take a break (perhaps to ask questions) and come back to the difficult problems later. 

When will problems be due? They will usually be due on Tuesdays and Fridays (Mondays and Fridays in weeks when there is a Tuesday exam). There may be some exceptions due to exams, break, or problems that are difficult enough to require more time.

How to submit?  You will submit your homework solutions to designated Moodle drop boxes. You can either compose your solutions on your computer or write them by hand and scan them to produce electronic copies.  There are scanners in F-217 and in the Logan Library (DRC).   For each assignment, submit a single file (can be a ZIP file); must be less than 5MB; aim for 2 MB or less.

There are no programming problems.  This is essentially an abstract mathematics course whose area of application is computer science. 

Due to limited time (yours and mine), I will only require you to formally write up a subset of the assigned problems.  You should make sure you understand all of them.  But sometimes the time required to write them clearly is greater than the time required to understand/solve them, so I will not ask you to submit all of them.  My assistants and I will do our best to grade all required problems, but occasionally we may have to grade a proper subset of them.

The textbook has many exercises at the ends of the chapters; Almost all are likely to be helpful; obviously I cannot assign all of them. For many of those problems, reading and thinking about them will be instructive, even if you don't have time to fully solve them.  I recommend that you read them all, regardless of whether they are assigned.

Get started early on all assignments! Sometimes you will need some "incubation time" before the problem is due.

Policy on Late Assignments: Because of the number of students taking this class and because I am teaching an overload for the last half this term,  I cannot accept late assignments.  Please submit whatever parts you have done 8:15 AM on the due date. The Moodle drop boxes will close shortly after that.   In calculating your assignment average, I will drop the score of the assignment on which you get the lowest percentage score, thus missing one assignment or reading quiz will not kill your grade.