MA/CSSE 474 Theory of Computation - Summer 2013 (201340)

• 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 the Theory of Computation by Michael Sipser (Thomson Course Technology-Hill, 2006)
• Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman (Addison-Wesley, 2001)
• 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. Explain the Church-Turing thesis and its significance.
8. Determine a language's location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, recursively enumerable languages).
9. Prove that a language is in a specified class and that it is not in the next lower class.
10. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
11. Explain why some problems have no algorithmic solution.
12. Provide examples that illustrate the concept of undecidability.
13. Prove that a problem is undecidable by reducing a classic known undecidable problem to it.
14. 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.

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
• willingness to work cooperatively with other students (inside the classroom and out) to enhance the learning environment for everyone
• willingness 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)

Course Assignments

Many days there will be in-class quizzes, similar to other CSSE courses.  In addition to questions that can be answered from the in-class material, there will sometimes be questions based on simple concepts from the reading assignments, as an encouragement for you to actually do the reading.  [In the summer, these will not be assignments.  I will post the quizzes and solutions on-line.  I recommend that you read through the PowerPoint slides and try to do the quizzes, looking at the answers when necessary.]

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. You may of course ask about any details that you do not understand. I strongly believe that reading the textbook will help you; sometimes there may  be an ANGEL quiz that covers a reading assignment.

I will assign some written problems, many of them from the textbook. They will usually be due on Mondays and Thursdays. 

When will problems be due? The usual pattern will be that problems assigned on Thursdays or Fridays will be due at noon on the following Tuesday, and problems assigned on Mondays or Tuesdays will be due on Friday. There may be some exceptions due to exams, break, or problems that are difficult enough to require more time. But you can always count on at least 60 hours between a problem's assignment and its due date.

You will submit the homework to ANGEL drop boxes. You can either write them on your computer or write them by hand and scan them. 

 The written problems will usually 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 can't write it neatly, type it and print it). 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 come back to difficult ones more often.

Unless I specify otherwise for some problem, you may communicate with other students about the problems, and work out solutions together. But when you write it up to turn it in, you must do it on your own without reference to things that you wrote together. You should also acknowledge the collaboration in writing on the paper that you submit.

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.

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 this term,  I cannot accept late assignments.  Please submit whatever parts you have done by noon on the due date.  In calculating your assignment average, I will drop the score on which you get the lowest percentage score, so missing one assignment will not kill your grade.

 

70% Assignments (including written homework  and any special assignments) 30% Examinations I reserve the right to adjust your final grade if your percentage for any category is way out of balance with the other categories.  Special note:  I do not intend to give any D or D+ grades in this course.  The grading scale is a little different than in some other courses, to reflect the difficulty of some of the problems.  It is possible that these numbers will be lowered a little bit, but you should not count on it. Bounty for discovering new errata. If you are the first to find and document an error in the required textbook or in any document that I produce for the course (including this syllabus), I will give you some bonus Assignments points. The number of points is proportional to the importance and subtlety of the error. Even spelling errors will count for something! There will be a folder on Piazza for reporting these.  Already-known errors in the textbook: http://www.cs.utexas.edu/~ear/cs341/automatabook/errata.html

MA/CSSE 474 Community