 CMPS130 Home
 Fall 2012 Home
 Attached Files

Lecture Notes
 test
 Lecture 1 09/27/2012
 Lecture 2 10/02/2012
 Lecture 3 10/04/2012
 Lecture 4 10/09/2012
 Lecture 5 10/11/12
 Lecture 6 10/16/2012
 Lecture 7 10/18/12
 Lecture 8 10/23/12
 Lecture 9 10/25/12
 Lecture 10 10/30/2012
 Lecture 11 11/01/2012
 Lecture 12 11/06/12
 Lecture 13 11/08/12
 Lecture 14 11/13/2012
 Lecture 15 11/15/2012
 Lecture 16 11/20/12
 Lecture 17 11/27/12
 Lecture 18 11/29/12
 Lecture 19 12/04/12
 Lecture 20 12/06/12
 Homework Solutions
 Old Exams
CMPS130, Fall 2012, Section 01: Home
CMPS 130: Computational Models Fall Quarter, 2012
Lectures: TTh 8945AM E2 192
You are highly encouraged to attend 1 or two instructor or TA office hours/sections each week
Instructor: Robert Levinson
Office Hours: M 1:30pm3:30pm or after class or by appointment.
Office: 255 Engineering Building 2 (E2 255)
Phone number: 4592087 (x92087 on campus)
Email: levinson@soe.ucsc.edu. Use it!
Webpage: http://courses.soe.ucsc.edu/courses/cmps130/Fall12/01
TA: Thomas Schmitz
"Office": Jack's Lounge
Office Hours: M 10am12pm, Tu 10:30am12:30pm, W 10am12pm
Email: tschmitz@soe.ucsc.edu
Prereqs: Grad in CS/CE or CMPS101 or Instructor's Permission. Course 104A can be helpful, but not required.
REQUIRED TEXT:

Introduction to Automata Theory, Languages and Computation
Hopcroft, Motwani and Ullman, 2004. 3rd Edition
(IGNORE: "Gradiance" Problems)
http://wwwdb.stanford.edu/~ullman/ialc.html
TOTALLY OPTIONAL BOOKS:
 Equal in difficulty:
Introduction to Languages and the Theory of Computation
John Martin. 3rd Edition. McGrawHill, 2003.  A little Harder:
Automata and Computability Dexter C. Kozen.
SpringerVerlag 1997.  A little easier:
Theory of Computation: formal languages, automata and
complexity. J. Glenn Brookshear, AddisonWesley, 1989.  Even easier:
Introduction to the Theory of Computation
Michael Sipser, 1997, PWS Publishing
Course Affirmations:
MY ABSTRACT THINKING IS BECOMING SHARPER AND SHARPER.
WRITING CORRECT MATHEMATICAL PROOFS SHARPENS MY INTELLECT.
Course Content:
Lectures and text are of equal importance.
Course Evaluation:
4 Quizzes (1545min.) 35%
4 Written Homeworks 35%
1 Final 30%
Homeworks may be done in groups of 13 that stay consistent throughout the quarter. Homework is due at classtime on day specified below (or announced otherwise) and late homework will not be allowed.
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.
Minimally, a score of less than 50% overall in any of the 3 categories above disqualifies one from passing the course. There will be no incompletes given for the course and no makeup exams.
A will be 90.0 percent or above. B will be 80 percent or above. C, passing, will be 70 percent or above. These guidelines will probably not become more generous.
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. HOMEWORKS SHOULD SHOW YOUR OWN (OR YOUR GROUP'S) UNDERSTANDING IN YOUR OWN WORDS.

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! concentrate most on 1.5
1. (Thursday September 27)
II. Finite Automata and Regular Sets
Please Read 2.2,2.3,2.5
2. (Tuesday October 2)
3. (Thursday October 4)
4. (Tuesday October 9)
Quiz 1
5. (Thursday October 11)
6. (Tuesday October 16)
HW1 is due: 2.2.1, 2.2.2, 2.2.4, 2.2.6, 2.2.10, 2.3.1, 2.3.3, 2.3.4,
2.4.1, 2.5.1, 2.5.3
Note: 2.2.1 is more challenging than most... Don't be discouraged...
Now Read 3.13.2 and Chapter 4!
7. (Thursday October 18)
8. (Tuesday October 23)
Quiz 2
9. (Thursday October 25)
10. (Tuesday October 30)
Hw2 is due: 3.1.2, 3.1.4, 3.1.5, 3.2.1, 3.2.3, 3.2.4, 3.2.6, 4.1.2,
4.1.4, 4.2.1, 4.2.2, 4.2.13, 4.4.1
11. (Thursday November 1)
12. (Tuesday Nov. 6)
NOTHING IS DUE!
13. (Thursday Nov. 8)
III. ContextFree Languages:
Now Read 5.1,5.2,7.17.3,6.16.4
14. (Tuesday November 13)
QUIZ 3
15. (Thursday November 15)
16. (Tuesday November 20)
HW3 is due: 5.1.1, 5.1.3, 5.2.1, 5.3.1, 5.4.1, 6.1.1, 6.3.2, 6.4.2,
7.1.2, 7.1.3, 7.2.1, 7.2.2, 7.4.3
17. (Thursday November 22)
HOLIDAY  NO CLASS
IV. Turing machines.
Read Chapter 8.28.5, 8.1 and 9.19.3
Chapter 9 is a bit abstract and crazy! Hang in there...
17. (Tuesday Nov. 27)
[quiz moved to Thursday]
18. (Thursday Nov. 29)
QUIZ 4
19. (Tuesday December 4)
HW4 is due: 8.2.1, 8.2.2, 8.4.2, 8.4.4, 8.5.1
20. Thursday December 6.
REVIEW for the FINAL EXAM
FINAL EXAM: Time and date: Monday December 10 811am at classroom site.
The final exam will come from material in the lectures, quizzes and homework problems. It will almost certainly be an inclass exam. The exam will be cumulative and similar to the quizzes.
Instructors and Assistants
 Robert Levinson (bob) (Instructor)
 Thomas James Schmitz (tschmitz) (Assistant)