Foundations of Computer Science, Spring 2008
School of Computing, University of Utah
Course Numbers: CPSC 5100 and 6100
T,H 2:00 PM-3:20 PM --- WEB 122

Instructor: Prof. Ganesh Gopalakrishnan
TA: Yang Chen

  index[.pdf] [.html] [.tex] --- Spring'07 --- HANDOUTS --- Tools [.pdf] [.html] --- book.pdf  
  All Classes --- Holidays --- ACS --- Finals 4/30/08, 1-3pm
Ofc Hrs: Yang: [Mon 4-5pm] Ganesh (3428 MEB) [Tue and Thu 4.30-5.30pm or by email appt ]

1  Overview

This offering of the courses CPSC 5100 and 6100 will, essentially, be taught through common lectures and assignments, and employ the same grading methods, barring some adjustments to the 5100 registrants. Only undergraduates who are not in the BS/MS program will be allowed to take 5100; others are be required to register for 6100.

I will be following the book ``Computation Engineering: Applied Automata Theory and Logic,'' Springer, 2006, by Ganesh L. Gopalakrishnan (myself) closely. I understand that used copies are available from various sources (bookstore, Amazon, etc). Being the first edition, there is an important errata page one should heed. There are also tools illustrated in the book. All these are described at http://www.cs.utah.edu/ganesh-comp-engg-book. I will also be following two other books periodically (some scanned copies will be put online; both these books are worth owning):
  1. ``Logic in Computer Science,'' by Huth and Ryan, Second Edition. Publisher: Cambridge, 2004. ISBN 0-521-54310-X. One tool used in this book is Alloy (see below).
  2. ``Software Abstractions,'' by Daniel Jackson. Publisher: MIT Press, 2006. ISBN 0-262-10114-9. Alloy is downloadable from http://alloy.mit.edu.
The class handouts will be kept at HANDOUTS, and frequently asked questions will be answered at FAQ. The rest of this page describes the course learning objectives, our class calendar of events, and the ADA statement.

2  Grading

There will be 15 assignments (one per week) numbered in Hex (1 through F). There will be one in-class midterm exam on April 28th, and a final exam (partly in-class and partly take-home) on April 30th in our class room between 1 and 3 pm. The midterm exam will be worth 10% of the course grade. Of the 15 assignment scores, we will pick the best 12 scores, and make them count for 5% (each) of the course grade, thus totalling to 60% of the course grades for the assignments. Then we will weigh the in-class and the take-home final exam each at 15% of the course grade, thus totalling to 15% of the course grades for the finals. The take-home final exam will be given on April 24th (last day of classes), and will be due when you come in to take your in-class final exam of April 30th at 1pm.

We will strive to have all assignments assigned on Thursdays, due at the beginning of the class of the following Thursday (you can make arrangements with the TA in case you cannot give it in class). Late submissions will not be accepted, unless you have made prior arrangements for late submission (backed by good reasons). None of the assignment questions are to be discussed amongst yourselves (reasons: we will give you plenty of worked out examples, and besides only the best 12 of the 15 assignments count). If code submissions and/or other electronic submissions are involved, we will require that you put it on a webpage, protect it under htaccess, and send us a URL to the webpage. Note down the URL as well as the htaccess login and password on your hardcopy submission in class.

3  Class Objectives

This class will present some of the foundational material of computer science that has far reaching impact -- not only in designing programs or formal specifications thereof, but also towards helping understand the strengths as well as limitations of various theories and procedures used in computer science. Diligent participants will gain the ability to read and understand various contemporary papers pertaining to computation, as well as software and hardware design.

The foundational material discussed includes results from Computability (The Halting Problem and related problems), Complexity (mainly the Theory of NP-Completeness), and Mathematical Logic (Propositional Logic, Predicate Logic, etc.). We will present automata theory and logic as one topic, illustrating their interplay.

We will emphasize the applications of automata theory and logic in the real world. Our main application domain will be concurrent system design. As almost everyone knows, concurrent system design is, after decades of research, still poorly practised. This manifests in the form of bugs that bring down concurrent systems. As engineers, we also need to have the tools to be able to specify and systematically debug1 concurrent systems. Automata theory and logic serve as the platform upon which one can create effective tools for specification and systematic debugging of concurrent systems. This has become especially urgent with the widespread use of multi-core computers. As Herb Sutter of Microsoft puts it: ``My 30 years of experience reasoning about and specifying systems has shown that the only way to understand any non-trivial system is as a state machine.''

A background quiz given on the first day will help you realize your level of preparation.

4  Calendar


      January               February               March                 April
Su Mo Tu We Th Fr Sa  Su Mo Tu We Th Fr Sa  Su Mo Tu We Th Fr Sa  Su Mo Tu We Th Fr Sa
          2  3  4  5                  1  2                     1         1  2 #B  4  5
 6  7 FL  9 10 11 12   3  4  5  6 #4  8  9   2  3  4  5 #8  7  8   6  7  8  9 #C 11 12
13 14 15 16 #1 18 19  10 11 12 13 #5 15 16   9 10 11 12 #9 14 15  13 14 15 16 #D 18 19
20 21 22 23 #2 25 26  17 18 19 20 #6 22 23  16 sb sb sb sb sb SB  20 21 22 23 #E 25 26
27 28 29 30 #3        24 25 26 27 MT 29     23 24 25 26 #A 28 29  27 28 29 FE
                                 +#7        30 31

FL = First lecture; #F on Last lecture; sb/SB = Spring Break
MT = Midterm; FE = FINAL EXAM; #1-#E (Hex) = Asg due dates (subject to change)

5  ADA Statement

The University of Utah seeks to provide equal access to its programs, services and activities for people with disabilities. If you will need accommodations in the class, reasonable prior notice needs to be given to the Center for Disability Services, 162 Union Building, 581-5020 (V/TDD). CDS will work with you and the instructor to make arrangements for accommodations.

1
Otherwise known as formal verification.
This document was translated from LATEX by HEVEA.