Server: Netscape-Communications/1.1 Date: Wednesday, 20-Nov-96 23:25:04 GMT Last-modified: Tuesday, 05-Nov-96 22:46:08 GMT Content-length: 4961 Content-type: text/html CSE 262 Handout 1

CSE 262, Fall 96

Automata, Computability & Complexity
Course Information
August 30, 1996

Coordinates:

TOWNE 311, Mo We Fr 11-12

Instructor:

Jean H. Gallier, MRE 176, 8-4405, jean@saul

Office Hours:

Mon-Wed, 3-4pm, Thurs, 4:45-5:45pm

Teaching Assistant:

David Parkes, Towne 353, dparkes@unagi

Office Hours:

Mon.-Wed., 5-6pm

Textbook(required):

An Introduction to Formal Languages and Automata, Peter Linz, D.C. Heath and Co

Also recommended:

Introduction to Automata Theory, Languages and Computation , J.E. Hopcroft and J.D. Ullman, Addison Wesley

Grades:

1/2: Homework Assignments (5-6 of them)

1/8: Intermediate Exam 1 (1h closed book; Wed. October 23, 1996)

1/8: Intermediate Exam 2 (1h closed book; mid November)

1/4: Final Exam

Problem Sets

Some Transparencies and Notes

Brief description:

The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) computability and recursive function theory; (3) complexity theory. The course will focus mostly on (1) and (2). Applications of (1) to programming (and natural) language specification and recognition (in particular, compiler construction), will be emphasized.

Topics will include:

published by:

Jean Gallier