CSE 322: Introduction to Formal Models in Computer Science, Winter 2005

Steam-powered Turing Machine

University of Washington Computer Science & Engineering

CSE 322: Introduction to Formal Models in Computer Science, Winter 2005

Instructor:

Venkatesan Guruswami (venkat@cs)
Office: Allen 656, Ph: 685-1959
Office Hours: Wed 11-12

Teaching Assistants:

Ethan Phleps-Goodman (ethanpg@cs)
Office hours: Tu 11-12, Thu 10-11am,
CSE 216
Uday Prakash (uday0210@cs)
Office hours: Thursdays 3:30-4:30pm,
CSE 220.

Meeting Times:

Monday, Wednesday, and Friday, 1:30-2:20pm.
Location: EE1 037.

Problem Sets

Assigned weekly, roughly 8 of them, generally due on Fridays
Late solutions will not be accepted (unless PRIOR approval is obtained)
IMPORTANT, Please Read: Homework Policies
Problem set 1 (due Jan 14): ps pdf
Problem set 2 (due Jan 21): ps pdf
Problem set 3 (due Jan 28): ps pdf
Problem set 4 (due Feb 4): ps pdf
Problem set 5 (due Feb 18): ps pdf
Problem set 6 (due Feb 25): ps pdf
Problem set 7 (due Mar 4): ps pdf
Problem set 8 (due Mar 11): ps pdf

Handouts

Finite automata to regular expression conversion
Myhill-Nerode Theorem
State minimization for DFAs
Pattern matching using DFAs (Notes from Fall'02 offering of CSE 417)
Converting grammars to Chomsky Normal Form
Cocke-Kasami-Younger algorithm example (From previous year, note slight change in Chomsky Normal Form definition in the handout.)

Sample midterm: ps pdf. Here is another sample midterm from an earlier offering.
Sample final: ps pdf.
Final exam topic list: ps pdf.

Mailing List:

It is important to subscribe to the class mailing list immediately. Everyone is expected to be reading cse322 e-mail to keep up-to-date on the course.
To subscribe to the CSE 322 mailing list, visit http://mailman.cs.washington.edu/mailman/listinfo/cse322.

Text Book

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997.
We will cover Chapters 1,2,3 and parts of Chapters 4,5.
There is a list of errors in the first printing and errors in the second printing of the textbook available.

Exams

Midterm exam: Friday, Feb 11, in class.
Final exam: Monday, Mar 14, 2:30-4:20pm.

Grading (Rough split)

Weekly assignments (40-50%)
Midterm exam (15-20%)
Final exam (35-40%)


	Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX