
CITIDEL >
Syllabus Collection >
Syllabus >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10117/5621

Title:  Introduction to the Theory of Computation 
Authors:  
Issue Date:  
Publisher:  
Citation:  http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2001/Syllabus.html 
Abstract:  Course Syllabus for ECS 120 "Introduction to the Theory of Computation" Spring Quarter 2001
General Information
Instructor: Oliver Kreylos, kreylos@cs.ucdavis.edu
Lecture: MWF 10:00am10:50am,
107 Cruess Hall
Office hours: MWF 11:00am01:00pm,
3013 EU II,
(530) 7521951
Teaching assistant: Jevan Gray, grayj@cs.ucdavis.edu
Discussion section: F 8:00am8:50am,
107 Cruess Hall
Office hours: W 05:00pm06:00pm, R 12:00 noon03:00pm,
3082 EU II,
(530) 7525755
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:
http://wwwcsif.cs.ucdavis.edu/~cs120
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 053494728X
Further reading: Hopcroft, John E. and Ullman, Jeffrey D., "Introduction to Automata Theory, Languages, and Computation," AddisonWesley Pub. Co., ISBN 020102988X
Aho, Alfred V. and Ullman, Jeffrey D., "Foundations of Computer Science (Principles of Computer Science Series)," W H Freeman & Co., ISBN 0716782847
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. Contextfree languages and pushdown automata. Normal forms. Closure properties of contextfree languages. The pumping lemma for contextfree languages.
II. Computability theory
1. The Turing machine and equivalent models of computation. The ChurchTuring thesis.
2. Decidable and undecidable problems. Recursivelyenumerable sets. The halting problem as an example of an undecidable problem.
3. Reducibility.
III. Complexity theory
1. Time complexity. P and NP. Polynomialtime reducibility. NPCompleteness. 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:00am10:50am in 107 Cruess Hall.
Final exam
Final exam on Saturday, June 9, 4:00pm6:00pm in 107 Cruess Hall.
Both exams will be closed book, with up to one lettersized 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, 7521128; http://sja.ucdavis.edu.) 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, Contextfree Languages I 1.3  2.1
Week 4 04/22  04/28 Contextfree languages II 2.1  2.2
Week 5 04/29  05/05 Contextfree 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] 
URI:  http://www.citidel.org/handle/10117/5621 
Appears in Collections:  Syllabus

Files in This Item:
File 
Size  Format 
45Syllabus.html  11Kb  HTML  View/Open 

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