CIS 511, Spring 2003

Introduction to the Theory of Computation
Course Information
January 8

** Answers to the Final Exam Are Posted **

Coordinates:

Moore 23, Tu-Th, 12:00-1:30pm

Instructor:

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

Office Hours:

Mon. 3:00-4:00pm, Tu. 4:30-6:00pm

Teaching Assistants:

Swarat Chaudhuri, swarat@gradient, Pender 329A

Office Hours:

Wed. 4:00-6:00pm

Newsgroup:

upenn.cis.cis511

Textbook (required):

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

Also recommended:

Elements of the Theory of Computation, H. Lewis and C. Papadimitriou, Prentice Hall

Introduction to the Theory of Computation, Michael Sipser, PWS Publishing

Additional Useful References:

Automata and Computability, Dexter Kozen, Springer

Theory of Computation, Derick Wood, Wiley

Mathematical Theory of Computation, Zohar Manna, McGraw Hill

An Introduction to the General Theory of Algorithms, M. Machtey and P. Young, Elsevier North-Holland

Introduction to Formal Language Theory, M. Harrison, Addison Wesley

The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Martin Davis, Raven Press

Theory of Recursive Functions and Effective Computability, Hartley Rogers, MIT Press

Introduction to Metamathematics, Stephen Kleene, North-Holland

Computability and Unsolvability, Martin Davis, McGraw-Hill

Enumerability, Decidability, Computability, Hans Hermes, Springer-Verlag

Computational Complexity, Christos Papadimitriou, Addison Wesley

Some Historical and Leading Figures

David Hilbert, Alan Turing, Stephen Kleene, Kurt Godel, Alonzo Church, Haskell Curry, Jacques Herbrand, Emil Post, Wilhelm Ackermann, Axel Thue, Walther von Dyck, Dana Scott, Stephen Cook, Anil Nerode, Sheila Greibach (home page), Sheila Greibach (photo), Half-century of automata theory

Recent Paper Relevant to the Course Material

Deterministic Finite Automata with Recursive Calls and DPDA's (ps)
With Salvatore La Torre and Supratik Mukhopadyay
March 2003.

WPE I

Recall that since January 2002, the WPE I (A, Theory) IS the FINAL EXAM in CIS511. The questions for this Exam will be given by a small group of faculty members (2 to 3) and will be graded by the same group of faculty members. Students are responsible for all the non * entries in the syllabus found below.

Note that Homeworks and the Programming project DO NOT count for the WPE, but they count 70% of the grade of the course.

Thus, it is possible that a student:
Fails the WPE and passes CIS511
Passes the WPE and fails CIS511
Fails both the WPE and CIS511
Passes both the WPE and CIS511!

Grades: homework assignments (45%), Programming Project (25%), Final (30%)

Homework assignments (6 of them)

You will find below two files of Latex macros mac(.tex) and mathmac(.tex),
as well as the Latex source for the assignments.

A Word of Advice :

Expect to be held to high standards, and conversely! In addition to transparencies, I will distribute lecture notes. Please, read the course notes regularly, and start working very early on the problems sets. They will be hard! Take pride in your work. Be clear, rigorous, neat, and concise. Preferably, use a good text processor, such as LATEX, to write up your solutions.

Due to the difficulty of the homework problems and in order to give you an opportunity to learn how to collaborate more effectively (I do not mean "copy"), I will allow you, in fact, URGE you, to work in small groups. A group consists of AT MOST THREE students. All members of a group will get the SAME grade on the homeworks and the project.

We will have special problems sessions, roughly every two weeks, during which we will solve the problems together. I am hard to convince, especially if your use blatantly ``handwaving'' arguments.

Late Homework Policy

If Homework due on Tuesday:

If Homework due on Thursday:

** ZERO credit ** if turned in later than specified above!
Policy will be ** strictly enforced **
No Excuses, plan ahead!

Plagiarism Policy

I assume that you are all responsible adults.
Copying old solutions verbatim or blatantly isomorphic solutions are easily detectable.
DO NOT copy solutions from old solution sheets, books, or friend!
Either credit will be split among the perpetrators, or worse!

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) Models of computation, computability, and basics of recursive function theory; (3) complexity theory.

Level of the course: Students are EXPECTED to have undergraduate knowledge of the theory of computation, roughly equivalent to the material covered in CSE262. Most material on the regular languages will not be covered in class.
Material assumed to be known and either not covered in class or reviewed very quickly is marked with a (-).
Material NOT required for the WPE is marked with a (*).

The course will focus mostly on (1) and (2), but will also cover some of (3): the classes P and NP, and NP-complete problems. Applications of (1) to programming (and natural) language specification and parsing (top-down and bottom-up parsing) will be mentioned, whenever appropriate.

Topics will include:

PART 1: Languages and Automata

PART II: Models of Computation and Basics of Recursive Function Theory

PART III: Computational Complexity

Some Course Notes and Slides

Relevant Fun Software

** Jflap

Back to Gallier Homepage

published by:

Jean Gallier