CIS 130: Computational Models Fall Quarter, 2003 Lectures: TuTH2-345PM Baskin Engineering 152 Instructor will be at "white boards" in Baskin Engineering, 6-8pm on Wednesday evenings. 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: TuTh 4-430pm or by appointment. Phone number: 459-2087 (x2087 on campus) n BE 372. E-mail: levinson@cse.ucsc.edu. Use it! Newsgroup: ucsc.class.cmp130. Use it too! Teaching Assistants: Jonathan Panttaj (jpanttaj@cse) Sanjit Jhala (sanjit@cse) Readers/Tutors: Prereqs: Grad in CIS/CE or CIS101 or Instructor's Permission. Course 104A can be helpful, but not required. Required: Introduction to Languages and the Theory of Computation John Martin 3rd Edition. McGraw-Hill, 2003. Optional: Previous texts for the course: Introduction to Automata Theory, Languages and Hopcroft, Motwani and Ullman, 2001. 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. 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. Course Jingle: "GOOD, BETTER AND BEST... I WILL NOT LET THEM REST UNTIL MY GOOD IS BETTER and MY BETTER IS BEST!" Lectures and text are of equal importance. Course Evaluation: 4 Quizzes (15-60min.) 4 written Homeworks 1 Final 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 5 points. Thus a problem with 4 parts is twice as many points as a problem with 2 parts. Students will be scored on 40-35-25 percent scale weighing the three main categories of quizzes, homeworks and final in the order you have done best 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 90.0 percent or above. B will be 80 percent or above. C will be 70 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. Written problem solutions should reflect your own understanding and be in your own words! Lecture Schedule (Tentative. A few changes should be expected.) ---------------------------- All Homework sets occur in the text and are listed below. I. Introduction. Read Chapters 1-2 (mainly review, skip 2.5, and focus on 1.5) Homework 1: 1.12, 1.38, 1.39, 1.40, 1.42, 1.44, 1.46, 1.70 1. (Thurs. Sept. 25) II. Finite Automata and Regular Sets Read Chapters 3-5.3 2. (Tues. Sept. 30) 3. (Thurs. Oct. 2) Quiz 1 4. (Tues. Oct 7) 5. (Thurs. Oct 9) HW1 is due. Homework 2: 3.1-3.2, 3.9ai, 3.10, 3.18, 3.19ai, 3.20af, 3.43c, 3.45,3.46, 4.2, 4.6,4.7, 4.10 aceg, 4.16, 4.35a, 5.17, 5.20 5.24a, 5.26 6. (Tues. October 14) 7. (Thurs. October 16) 8. (Tues. October 21) 9. (Thurs. October 23) Quiz 2. III. Context-Free Languages and Push Down Automata Read Sections 6.1-6.3, 7.1-7.5, 8.1-2. Homework 3: 6.1abc, 6.4, 6.6, 6.9h, 6.10, 6.13, 6.14, 6.39 a ,b,d, 6.43, 6.46. 7.1, 7.5, 7.9, 7.13, 8.1, 8.5, 8.15abcde 10. (Tues. October 28) 11. (Thurs October 30 ) Hw2 is due. 11 (Tues. November 4) 12. (Thurs. November 6) Quiz 3 Chapter IV: Turing machines. Read Chapters 9-11 but focus on 9.1, 10.1, 10.5,11.1-11.4 Homework 4: 9.2i, 9.6af, 9.14, 9.18, 9.39, 9.40 10.1, 10.5, 10.34 13 (Tues. November 11) NO CLASS 14. (Thurs. November 13) Hw3 is due. 15. (Tues. November 18) 16. (Thurs. November 20) Quiz 4 17. (Tues. November 25) 18. (Thurs. November 27) NO CLASS 19. (Tues. Dec. 2.) REVIEW 1 - HW4 is due 20. (Thurs. December 4) REVIEW 2 Final Exam - Tuesday, December 9, 8-11am. Normal Classroom site. The final exam will be an inclass exam and be cumulative.