Printer-friendly version

Syllabus, Spring 2008 CSci 4011: Introduction to Automata Theory

Instructor: Dr. Carl Sturtivant, carl@cs.umn.edu

Textbook: Michael Sipser "Intoduction to the Theory of Computation" 2nd Edition Thomson Publishing, 2006 Other books of interest: Harel, "Algorithmics", Addison Wesley, --- for a broad overview of the abstract concepts of computer science with little mathematics Garey and Johnson, "Computers and Intractability, a Guide to the Theory of NP-Completeness", Freeman & Company --- an excellent reference to NP-completeness and its practical ramifications

Read this document very carefully, as it defines what is required to perform effectively in this class. Course content very approximately in temporal order:

Mathematics from chapter zero of the text will be assumed where necessary (via the prerequisite). Sections of the book listed below should be read in conjunction with the class. As the class proceeds it should be clear which sections have just been covered in order, and therefore which are about to be covered. The course content is precisely defined by the sections listed below. Chapter 1 Finite automata and regular languages. Chapter 2 excluding p.115-122 Context-free languages, grammars, pushdown automata. Chapter 3 Turing machines and the formal definition of an algorithm. Chapter 4 Decidability, and the Halting Problem. Chapter 5 Reductions and unsolvable problems. §6.2, §6.3 Decidability of Logical Theories; Turing Reducibility. Chapter 7 Time complexity and NP-completeness.

Evaluation: The following rules will be strictly enforced. Evaluation will consist of assignments (13) a Midterm and a Final exam. Assignments are a vital part of the learning process: persons who do not submit reasonable attempts at all thriteen assignments will receive an F for the course. Due dates for assignments are strict: all assignments must be received during the recitation in which they are due in order to receive credit. Keep a copy of each of your submissions as evidence that you have indeed submitted each assignment. Do not ever put your assignment under the instructors office door. Grading is absolute (i.e. not on a curve). The overall grade will be based upon: 4% for each homework, 8% for the midterm and 40% for the final. A minimum of 60% is necessary for an S or C- grade. Grading will be as follows: 95.0% or above yields an A, 90.0% an A-, 85% = B+, 80% = B, 75% = B-, 70% =: C+, 65% = C, 60% = C-, 55% = D+, 50% = D, and less than 50% yields an F. Percentages are not rounded when using this scheme, because this would be tantamount to moving all of the grade boundaries down by 0.5%. Grading is performed by the TA. If you have a question about grading, address it to the TA. Only if something wholely unreasonable has occurred will the instructor intervene. And this has not yet proved necessary. Furthermore, there is a limit of ten (10) days from the day assignments are returned in recitation for grading problems to be rectified, whether or not you attend and pick up your homework. After that period, such will not be considered. The sole exception to this rule is the final examination. Please ensure that you verify promptly that your assigment and examination grades have been recorded on GRIT, and complain to the TA if a grade record is missing. Incompletes (or make up exams) will in general not be given. These options will be considered only when a provably serious family or personal emergency arises, proof is presented, and the student has already completed all but a small portion of the work. Scholastic conduct must be acceptable. Specifically, you must do your homeworks, and examinations yourself, on your own. Do not search for answers to questions from the book on the world-wide-web. This is not meant to block general discussion of HOW to tackle homework problems, which you will also get if you come to office hours, but you must declare on your homework with whom you discussed any homework question. Do not write any notes when having such discussions, and be alone when writing out answers to homework questions. The instructor may at his discretion at any time give any student a short oral quiz on the student's submitted answer to any homework question to determine whether the student understands the text they have supplied. Failure to supply an adequate response will be deemed evidence for academic dishonesty (plagiarism), which may lead to failing the course and disciplinary action from the university.