(as passed out in class) CIS 130: Computational Models Fall Quarter, 2004 Lectures: TTh 6-745PM Merrill Academy 102 You are highly encouraged to attend 1 or two office hours/sections each week. You are welcome to attend all. Instructor: Robert Levinson Office Hours: T 8-10pm in Merrill Academy 102 ?? by appointment. Phone number: 459-2087 (x92087 on campus) E-mail: levinson@cse.ucsc.edu. Use it! Newsgroup: ucsc.class.cmp130. Use it too! Office: BE153C. But after October 15: 255 Engineering 2. TA: Jonathan Panttaja (jpanttaj@soe.ucsc.edu) Reader: Nguyet Manh (nguyetmanh@gmail.com) Prereqs: Grad in CIS/CE or CIS101 or Instructor's Permission. Course 104A can be helpful, but not required. Required: Introduction to Automata Theory, Languages and Computation Hopcroft, Motwani and Ullman, 2001. Optional: Equal in difficulty: Introduction to Languages and the Theory of Computation John Martin 3rd Edition. McGraw-Hill, 2003. Automata and Computability Dexter C. Kozen. Springer-Verlag 1997. A little easier: Theory of Computation: formal languages, automata and complexity. J. Glenn Brookshear, Addison-Wesley, 1989. Even easier: Introduction to the Theory of Computation Michael Sipser, 1997, PWS Publishing A little harder: The Language of Machines 1994 Floyd W., Robert and Biegel, Richard. Computer Science Press Course Motto: EXPLOIT MATHEMATICAL STRUCTURE MAXIMALLY. Course Affirmations: MY ABSTRACT THINKING IS BECOMING SHARPER AND SHARPER. WRITING CORRECT MATHEMATICAL PROOFS SHARPENS MY INTELLECT. Lectures and text are of equal importance. Course Evaluation: OR 4 Quizzes (15-45min.) %30 %30 4 written Homeworks %50 %35 1 Final %20 %35 Homeworks may be done in groups of 1-3 that stay consistent throughout the quarter. Homework is due at classtime on day specified below and late homework will not be allowed. Course work is graded competitively as well as qualitatively. Scores will be normalized so top 5% of class on any item score 100 or above. All quizes and homeworks will be graded equally, regardless of their length. Unless stated elsewhere, each part of each homework problem will be graded equally. Thus a problem with 4 parts is twice as many points as a problem with 2 parts. Students will be scored on 30-50-20 or 30-35-35 scale whichever they do better at. Minimally, a score of less than 45% overall (after normalization) in any of the 3 categories above disqualifies one from even being considered to pass the course. A will be 92.5 percent or above. B will be 85 percent or above. C will be 75 percent or above. It is possible to get Extra Credit by doing exceptional work on above items (something above and beyond expectations). It is fine and encouraged to discuss homework problems with other students - BUT CHEATING or ACADEMIC DISHONESTY on any course item (such as direct verbatim copying from a member outside your group or during an exam) will result in not passing the course and other undesirable consequences. Lecture Schedule (Tentative. A few changes should be expected.) ---------------------------- All Homework sets occur in the text. *'d problems have solutions on the web. ! are challenging problems. I. Introduction Read Chapter 1! but concentrate on 1.5 1. (Thursday September 23) II. Finite Automata and Regular Sets Read Chapter 2! but skip 2.4 2. (Tuesday September 28) 3. (Thursday September 30 ) 4. (Tuesday October 5) 5. (Thursday October 7) Quiz 1 6. (Tuesday October 12) 7. (Thursday October 14 ) HW1 is due. 2.2.1, 2.2.3, 2.2.4, 2.2.5, 2.2.11 2.3.2. 2.3.3, 2.3.7, 2.4.1, 2.5.2, 2.5.3 Note: 2.2.1 is more challenging than most in the course! Don't be discouraged... Read 3.1-3.2 and Chapter 4! 8. (Tuesday October 19) 9. (Thursday October 21) Quiz 2 10. (Tuesday October 26) 11. (Thursday October 28) HW2 is due: 3.1.1, 3.1.4, 3.2.2, 3.2.3, 3.2.4, 3.2.5, 4.1.1, 4.2.1, 4.2.3, 4.2.13, 4.4.2 12. (Tuesday November 2) 13. (Thursday November 4) Quiz 3 III. Context-Free Languages Read 5.1, 5.2, Chapters 6-7! 14.. (Tuesday November 9) 15. (Thursday Novermber 11) NO CLASS 16. (Tuesday November 16) HW3 is due: 5.1.2, 5.1.3, 5.2.1, 5.3.1, 5.4.2, , 6.1.1, 6.2.1, , 6.3.5, 6.4.1, 7.1.4, 7.1.5, 7.4.3 Chapter IV: Turing machines. Read Chapter 8! 17. (Thursday November 18) Quiz 4 18. (Tuesday November 23) 19. (Thursday November 25) NO CLASS March 25, 2001 20. (Tuesday November 30 ) Review 21. (Thursday December 2) Review HW4 is due: 8.1.1, 8.2.1, 8.2.2, 8.4.2, 8.5.2 22. (Thursday December 9) 4-7PM final exam The final exam will come from material in the lectures and textbook. It will almost certainly be an inclass exam. The exam will be cumulative.