CMPS 130: Computational Models Fall Quarter, 2012

Lectures: TTh 8-945AM 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:30pm-3:30pm or after class or by appointment.

Office: 255 Engineering Building 2 (E2 255)

Phone number: 459-2087 (x92087 on campus)

E-mail: 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 10am-12pm, Tu 10:30am-12:30pm, W 10am-12pm

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:

TOTALLY OPTIONAL BOOKS:

- Equal in difficulty:

Introduction to Languages and the Theory of Computation

John Martin. 3rd Edition. McGraw-Hill, 2003.
- A little Harder:

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

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 (15-45min.) 35%

4 Written Homeworks 35%

1 Final 30%

Homeworks may be done in groups of 1-3 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.1-3.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. Context-Free Languages:

Now Read 5.1,5.2,7.1-7.3,6.1-6.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.2-8.5, 8.1 and 9.1-9.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 8-11am at classroom site.

The final exam will come from material in the lectures, quizzes and homework problems. It will almost certainly be an in-class exam. The exam will be cumulative and similar to the quizzes.