|
| ||||||||||||
| |||||||||||||
| 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: |
|
| 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: |
Both exams will be closed book, with up to one letter-sized page of handwritten notes allowed. |
| Grade breakdown: |
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. | ||||||
| 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: |
|
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; http://sja.ucdavis.edu.) Ask the instructor for clarification beforehand if the above rules are not clear.
| 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] |