cs5100/cs6100: Foundations of CS (Spring 2009)

Instructor Konrad Slind (MEB 3436)	Office Hours: After class, or by appointment
Class Time T/R, 14:00-15:20	Class Room EMCB 122
TA: Chang Liu (chang.liu@utah.edu)	Office Hours: TBA

Foundations of CS is a survey of topics in theoretical computer science. The course assumes a previous course in CS theory covering at least finite state automata, context-free grammars, and Turing machines. If you've taken the equivalent of cs3100 here at Utah, you should be fine. Taking such a course as a platform, we will study three central topics, namely Logic, Computability and Complexity, in some detail.

Topics

Logic	Computability	Complexity
Propositional Logic First Order Logic Logic for programs Computing with Formulas	Turing machines Computable functions Decidability Undecidability Reductions Rice's theorem Relative computability Recursion theorem	Non-deterministic TMs Complexity measures Time and space hierarchies P and NP NP-completeness Reductions Applications of intractability

Important Dates

Jan 13 First class
March 16-21 (Spring Break)
April 28 Last class

The University Academic Calendar may be consulted for further information about drop dates and other important dates in the semester.

Course Materials

We will use

   Automata,Computability and Complexity: Theory and Applications

by Elaine Rich as the course text. I chose this text because the author gives quite elementary explanations, and the scope of the book is very wide. It is fairly expensive (120 USD), so you should attempt to obtain a used copy online.

There are many other excellent books in this area. Here is a sampling (they should all be in the library, and some are even in the departmental library):

Sipser, Introduction to the Theory of Computation
Kozen, Automata and Computability
Lewis and Papadimitriou, Elements of the Theory of Computation
Hopcroft, Motwani, and Ullman, Introduction to Automata Theory, Languages, and Computation
John Martin, Introduction to Languages and the Theory of Computation
Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science
Greenlaw and Hoover, Fundamentals of the Theory of Computation: Principles and Practice
Linz, An Introduction to Formal Languages and Automata
Papadimitriou, Computational Complexity

These books should be read in order to get other perspectives and alternate explanations of the material. Since the subject is quite mature, the material is almost always exactly the same; however, different motivations and examples can often help.

Here are my lecture notes on the logic section of the course. They are being incrementally upgraded as we go along. Please let me know if you find any mistakes or parts that you don't understand. Also, please note that my notes on Floyd-Hoare program logic are derived from the much more detailed notes by Mike Gordon.

Grades

The grade will be based on assignments, two exams, and a presentation. Grades will be assigned as follows:

Assignments	40%
Exams (2 midterms)	40%
Presentation	20%
Total	100%

Should you discover what you think is an error in grading, you have exactly one week after the grades are posted to request for regrading. You should first go and see the TA and see if you can get the problem resolved. If you are still unsatisfied, then you should go and see Professor Slind.

Exams

The first exam covers computability. It will be held March 31. I'm giving people a week to write it.

The second exam covers complexity. Note: the second exam has been superseded by assignment 4.

Assignments

Assignments will be given every one or two weeks. Assignments will be handed in to me at the beginning of class. If a due assignment is not in my possession by the time class starts, it is deemed to be late. You are allowed a maximum of 2 late submissions. A late submission can be at most 24 hours late: after that it will not be accepted and you will get no marks for the assignment.

Assignment 1. Due February 3, beginning of class. Answers
Assignment 2. Due February 19, beginning of class. Answers
Assignment 3. Due March 12, beginning of class. Answers
Assignment 4. Due May 5.

Presentations and other material

Each student is expected to schedule a 20-minute presentation with me. The presentation will be accompanied by a 5-page typeset document covering the topic of the presentation. Students can pair up. In that case, the expected quality of the work will be correspondingly increased.

Students are free to pick a topic, although they must clear it with me. It is strongly recommended that students arrange a meeting with me before they give their presentation. This meeting can be an informal run-through of the presentation and can also serve to clarify outstanding points.

Some possible papers to base a presentation on, along with a collection of overview material (some of which is quite good).

Mailing lists

cs6100@list.eng.utah.edu: You will be subscribed to this list.

Other Important Information

Konrad Slind