Chris Pollett>Old Classes>**CS305, Fall
1997**

*Last modified 09/18/97*

**Chris Pollett**

MCS 283

353-8926

Click here to send mail to cpollett@yahoo.com.

MWF 10-11 am

*and by appointment*

Classes meet MWF, 2:00pm - 3:00pm in CAS 314

*Introduction to the Theory of Computation,* Michael Sipser, PWS Publishing Company, 1996. See http://www-math.mit.edu/~sipser/errata.html for an up-to-date list of errors in the book.

You will read most of the textbook in this course.

*Elements of the Theory of Computation,*Lewis & Papadimitriou, Prentice Hall, 1981*Introduction to Automata Theory, Languages, and Computation,*Hopcroft & Ullman, Addison-Wesley, 1979

To enroll in this course, you must have satisfied the following course requirements. If you haven't done so but still want to remain in the course, please see me.

- MA 293 (Discrete Mathematics 1).
- CS 112 or CS 113 (Programming & Data Structures in C).

This course is a core requirement in undergraduate computer science curriculums at most colleges. Its purpose is threefold; first, to encourage you to investigate the nature of computation; second, to further develop your formal reasoning and writing skills; and third, to add new techniques to your programming bag of tricks.

Accordingly, we will develop several formal models of computation, each more powerful than the last. At each stage we will prove some of what our intuition suggests (and sometimes, what it denies) about these models. We will also see how most models admit two very different characterizations: one of machines that are able to recognize certain events, and another of grammars that are able to generate exactly what these machines recognize.

In particular, we will study regular languages, regular expressions, finite deterministic and nondeterministic automata, context-free grammars, pushdown automata, turing machines --- and more, if time allows.

Homeworks 30% Midterm 30% Final 40%

The midterm will be in class Wednesday Oct.22.

The final will be 12:30-2:30p.m., Tuesday, Dec.16.

In general, you will have at least one week to work on a homework assignment and three opportunities to attend my office hours before a given assignment is due.

Late homeworks will not be accepted; however, your low homework score will be dropped.

Collaboration is encouraged when working on homework problems and preparing for exams. None of the problems in this class are intended to have secret solutions; the more resourceful you are at discovering solutions, the more time you will have to write them well. Indeed, if you are stuck on a problem, I will be happy to talk with you about it during office hours. However, the solutions you turn in must be your original writing. Copying a prepared solution is not collaboration at all; it is plagiarism. Plagiarizing another's words is not tolerated at Boston University. It is so disdained that there are specific procedures for accusing and punishing those who plagiarize. Do not copy another person's work and present it as your own.

Other announcements will be made only by email. To add yourself to the course mailing list, log on to a CS cluster computer (such as csa) and type:

```
csmail -a cs305
```

Prepared by Chris Pollett.