| 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.
| 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 |
The University Academic Calendar may be consulted for further information about drop dates and other important dates in the semester.
Automata,Computability and Complexity: Theory and Applicationsby 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):
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.
| 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.
The second exam covers complexity. Note: the second exam has been superseded by assignment 4.
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).