cs5100/cs6100: Foundations of CS (Spring 2006)

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: Jianjun Duan	Office Hours: 13:00-14:00 the day before assignment due, or by appointment

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 two central topics, namely Computability and Complexity, in some detail.

We will also survey a collection of other topics. Each of these other topics are important and deep, so our time constraints will force us to usually give only quick and superficial coverage. However, that seems to be necessary in order to give an overview. The following table gives more detail. Note that the survey topics are preliminary and will likely change.

Topics

Computability	Complexity	Survey of Other Topics
Turing machines Alternative models 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	Computability/Complexity for R Program specification and verification Programming language semantics L-systems Infinite state automata Models for concurrency Termination

Important Dates

Jan 10 First class
March 13-17 (Spring Break)
April 25 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

    Problem Solving in Automata, Languages, and Complexity

by Ding-Zhu Du and Ker-I Ko (ISBN: 0-471-43960-6) as the course text. I chose this text because the authors are quite precise and give a wealth of examples. It is fairly expensive, so you may want 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. Although the subject is quite mature, different motivations and examples can often help.

For background you might also refer to my class notes for cs3100.

In the survey portion of the course, we will make use of papers and other resources available through the library and the WWW.

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 who graded your work and see if you can get it resolved. If you are still unsatisfied, then you should go and see Professor Slind.

Exams

Exam 1 covers computability.

Exam 2 covers complexity

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 Thursday, Jan. 19, beginning of class. Questions 4.1.2 (a,b), 4.1.6, 4.3.1, 4.3.6 from the text. 5100 students don't need to do the last one, but they can, for extra credit.
Assignment 2 due Tuesday, Jan. 31, beginning of class. Questions 5.2.3(a), 5.2.4, 5.2.7(a,e), 5.2.8(a,b) (just the A+B case), 5.3.2, 5.3.6, 5.3.7, 5.3.8 from the text. 5100 students don't need to do the last two, but they can, for extra credit.
Assignment 3 due Thursday, Feb. 16, beginning of class.
Assignment 4 due Wednesday, March 30, 5:00 pm.

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 with a collection of overview papers (some are quite good).

The (evolving) schedule of presentations.

Mailing lists

cs6100@cs.utah.edu: You must subscribe to this class mailing list, but do not send messages to this list. Teaching staff will use it to send messages to the class. To subscribe, follow the directions at http://mailman.cs.utah.edu/mailman/listinfo/cs6100
teach-cs6100@cs.utah.edu: This is the teaching staff mailing list. Use it to send questions to the instructor and TAs. If you want to send messages directly to the TA, use
- jjduan@cs.utah.edu

Other Important Information

Don't cheat
College of Engineering information for students.
Students with disabilities

Konrad Slind