Computing and Information Technology Interactive Digital Educational Library


Syllabus Collection >
Syllabus >

Please use this identifier to cite or link to this item:

Title: Introduction to the Theory of Computation
Issue Date: 
Abstract: Course Syllabus for ECS 120 "Introduction to the Theory of Computation" Spring Quarter 2001 General Information Instructor: Oliver Kreylos, Lecture: MWF 10:00am-10:50am, 107 Cruess Hall Office hours: MWF 11:00am-01:00pm, 3013 EU II, (530) 752-1951 Teaching assistant: Jevan Gray, Discussion section: F 8:00am-8:50am, 107 Cruess Hall Office hours: W 05:00pm-06:00pm, R 12:00 noon-03:00pm, 3082 EU II, (530) 752-5755 Newsgroups: ucd.class.ecs120 Do not post to this newsgroup. It is only for announcements, adjustments in the homework, and answers to questions on the homework. Since these things are of importance to everyone in the class, everyone should check this newsgroup regularly - at least once a day, especially before homework due dates or exams. ucd.class.ecs120.d The discussion group. This newsgroup is for discussion among students, and questions to the staff. Students are encouraged to discuss assignments and answer one another's questions, as long as specific homework answers (or parts thereof) are not posted (also see Academic Honesty). Also, this is not an open forum. Rude or irrelevant postings will not be tolerated; i.e., no "flaming" allowed. Note: Please do not email either the instructor or the TA with general questions about assignments or course material. Instead, post a message to the ucd.class.ecs120.d newsgroup. This will enable all students to see the questions and replies so they too can benefit, and it will generally get you a faster response since other students in the class might be able to help answer your question before one of us gets a chance to see it. Web site: The course web page will feature lecture notes, homework and exam solutions and grades. Textbook: Sipser, Michael, "Introduction to the Theory of Computation," PWS Pub. Co., Boston, MA, ISBN 0-534-94728-X Further reading: Hopcroft, John E. and Ullman, Jeffrey D., "Introduction to Automata Theory, Languages, and Computation," Addison-Wesley Pub. Co., ISBN 0-201-02988-X Aho, Alfred V. and Ullman, Jeffrey D., "Foundations of Computer Science (Principles of Computer Science Series)," W H Freeman & Co., ISBN 0-716-78284-7 Kfoury, A. J., Moll, Robert N. and Arbib, Michael A., "A Programming Approach to Computability," (out of print - nice if you can get it!) Course Description Prerequisites: ECS 20 "Discrete Mathematics for Computer Science" Math 108 "Introduction to Abstract Mathematics" (recommended) Course objectives: Theory of computation is the interface between abstract mathematics and computer science. It provides formalized models of computation to allow mathematical reasoning about computer science problems. Therefore, the goals of this course are twofold: First, it introduces basic computation models and their basic properties; second, it teaches the mathematical techniques necessary to prove more advanced properties of those models. Upon completion of this course, a student will be able to express computer science problems as mathematical statements; and will also be able to form proofs to investigate those problems. Expanded course description: I. Formal languages and automata 1. Formal languages and grammars. The Chomsky hierarchy. 2. Regular languages and finite state machines. Closure properties of regular languages. The pumping lemma. 3. Context-free languages and push-down automata. Normal forms. Closure properties of context-free languages. The pumping lemma for context-free languages. II. Computability theory 1. The Turing machine and equivalent models of computation. The Church-Turing thesis. 2. Decidable and undecidable problems. Recursively-enumerable sets. The halting problem as an example of an undecidable problem. 3. Reducibility. III. Complexity theory 1. Time complexity. P and NP. Polynomial-time reducibility. NP-Completeness. Space complexity. Approximation algorithms. Homework Assignments and Exams Homework: There will be nine written homework assignments. Homework assignments are to be turned in by dropping them in the appropriate box in room 2131 EU II by 4:00pm on the due date (every Friday). Each homework assignment consists of several problems (mostly taken from the textbook), and each problem is worth a number of points, based on its difficulty. The final homework grade will be the ratio of total points scored versus total points possible. Due to limited reader support, we might have to resort to only grading a subset of problems from each homework assignment. In this case, homework grades will only reflect the portion of the assignment graded. Assignments must be turned in on time to receive credit. Except in the most extreme cases, late assignments will not be accepted. If you cannot complete an assignment by the due date, hand in whatever you have done to receive partial credit. We realize that most of you have demanding schedules and some of you must work to support yourselves. However, please do not ask us to accept either of these as excuses for late assignments or diminished performance. Exams: Midterm One midterm exam on Wednesday, May 9 during class, 10:00am-10:50am in 107 Cruess Hall. Final exam Final exam on Saturday, June 9, 4:00pm-6:00pm in 107 Cruess Hall. Both exams will be closed book, with up to one letter-sized page of handwritten notes allowed. Students in need of special accomodations for the exams must make those known to the instructor during the first week of the quarter. Grading Policy Grade breakdown: Homework assignments: 60% Midterm: 15% Final exam: 25% A significant difference between homework scores and exam scores may result in an alternate grading scheme. For example, someone who scores 100% on all homework assignments and fails both exams will fail the course. Simplicity, presentation and neatness of your solutions are considered in the grading of assignments and exams. Graded paper return: Graded homework and exams can be picked up during discussion sections and TA office hours. Regrades: In general, papers to be considered for regrades must be turned in no later than one week after the graded papers were made available, not from when you picked up your paper. However, at the end of the quarter, papers to be considered for regrades must be turned in earlier, as will be announced. See the TA for regrades of assignments; see the instructor for regrades of exams. Similarly, any missing or misrecorded grades must be reported within a week of their posting, except as will be announced at the end of the quarter. Letter grades: A: 90% <= x B: 80% <= x < 90% C: 70% <= x < 80% D: 60% <= x < 70% F: x < 60% Academic Honesty Each student is to do his or her own work on the assignments and exams. It is fine to talk with others about general approaches used to solve the assignments, but each student is to develop her/his own solutions; collaborative efforts are not allowed. In addition, using solutions from any other source is forbidden; in particular, using solutions (either instructors' or other students') from previous offerings of this course is not allowed. To summarize: all assignments and exams are to be individual and original efforts. Any instance of suspected cheating or plagiarism (e.g., collaboration or copying on tests) will be referred to the Office of Student Judicial Affairs for adjudication. The "Code of Academic Conduct" describes relevant policies and procedures. (You should have a copy of this document. If not, you can obtain one through the Office of Student Judicial Affairs, 752-1128; Ask the instructor for clarification beforehand if the above rules are not clear. Tentative Course Outline and Reading Assignments Chapters/section numbers in the table refer to the course textbook. Chapter/section numbers in brackets will probably not be covered in class. Week Dates Topic Reading Week 1 03/30 - 04/07 Introduction, Regular Languages I 0 - 1.1 Week 2 04/08 - 04/14 Regular Languages II 1.2 - 1.3 Week 3 04/15 - 04/21 Regular Languages III, Context-free Languages I 1.3 - 2.1 Week 4 04/22 - 04/28 Context-free languages II 2.1 - 2.2 Week 5 04/29 - 05/05 Context-free Languages III, Turing Machines I 2.3 - 3.2 Week 6 05/06 - 05/12 Turing Machines II, Decidability 3.3 - 4.2 Week 7 05/13 - 05/19 Reducibility 5, [6 - 6.2] Week 8 05/20 - 05/26 Time Complexity I [6.3 - 6.4], 7 - 7.4 Week 9 05/27 - 06/02 Time Complexity II, Space Complexity 7.4 - 8.1, [8.2 - 8.6] Week 10 06/03 - 06/07 Intractability, Approximation Algorithms 9 - 10.1, [10.2 - 10.6]
Appears in Collections:Syllabus

Files in This Item:

File SizeFormat

All items in DSpace are protected by copyright, with all rights reserved.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback