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

Instructor: Prof. Ganesh Gopalakrishnan
TA: Lu Zhao

    This index [.tex] --- HANDOUTS --- FAQ.pdf FAQ.html    
    CLASSES --- Spring'07 --- ACS --- FINALS
Ofc Hrs: Lu: [Mon 10.40-11.40, Tue 3.30-5.00] Ganesh: [Wed 2.00-3.30, Thu 3.30-5.00]

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. The main difference will be that only undergraduates who are not in the BS/MS program will be allowed to take 5100. Hence, the peer groups for calculating the final relative grades will be these respective classes (which means that a 5100 student's grade will be calculated by comparing him/her with his peers in the 5100 class -- and likewise for 6100 students).

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 the book ``Specifying Systems'' by Leslie Lamport, who has provided a downloadable PDF copy of the book at http://research.microsoft.com/users/lamport/tla/book.html.

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  Learning Objectives

This class will present foundational material with far reaching impact, and their applications in solving practical problems. Foundational material 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.

Students will undoubtedly have different levels of preparation coming into this class. A background test on the first day will help you realize your level of preparation. I will also give you some guidelines for deciding whether you will find this class an uphill battle or a fruitful learning experience. The final decision to continue with this class will be your own (I can provide customized advise if desired).

3  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  
    1  2  3  4  5  6               1  2  3               1  2  3   1  2  3  4  5  6  7  
 7  8 FL 10 11 12 13   4  5  6  7  8  9 10   4  5  6  7  8  9 10   8  9 10 11 12 13 14  
14 15 16 17 18 19 20  11 12 13 14 15 16 17  11 12 13 14 15 16 17  15 16 17 18 19 20 21  
21 22 23 24 25 26 27  18 19 20 21 22 23 24  18 sb          SB 24  22 23 LL 
28 29 30 31           25 26 27 28           25 26 27 28 29 30 31

FL = First lecture; LL = Last lecture; sb/SB = Spring Break

4  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.