COMPUTER SCIENCE DEPARTMENT

COURSE: CS 541(3 cr hrs)Mathematical Foundations of CS Fall, 2006

PREREQUISITES: Graduate Student status

INSTRUCTOR: Dr. Shindhelm

OFFICE:TCCW 137A
Phone: 745-6247
Hours: TR 8:30:9:30;MWF 11:30-12:30 + by appointment

TEXT: Introduction to Computer Theory,by Cohen, 2nd edition,
Wiley Publishing Company

COURSE PURPOSE: This course is designed to acquaint students with basic
abstract models of computers including automata theory, and Turing machines. An introduction to the theory of computability will also be given.

ATTENDANCE: Attendance will be taken for the first few weeks until I learn
your name. After that I will keep track of absences without calling the roll. It is to your advantage to attend classes since those topics covered in class are the primary ones that I consider important and I will hold you responsible to know for exam purposes.

GRADING: Each of three hour exam grades will count 20% of the final course grade. A comprehensive final exam will count 40%.The final course letter grade will be assigned according to:
90-100=A 80-89=B 70-79=C 60-69=D below 60=F
NO MAKE_UP EXAMS ARE GIVEN!!! -unless a documented medical reason is given.

The following is a tentative outline of the assigned readings from the text Introduction to Computer Theory, Second edition, by Cohen

Assignment Topics Read Ch. Do Ex
-------------------------------------------------------------------
1. : Background and Introduction : 1,2 : Ch2, 1-9
2. : Recursive Defs,Regular Expressions : 3,4 : Ch4,1-6,18
3. : Finite Automata : 5 : 2-9,17-20
4. : Transition Graphs and Kleene's Thm : 6,7 :Ch6,4-12;Ch7,1-7
: Nondeterministic FA's : :8-19
5. : Regular Languages :9 :1-20
------------------------------------------------------------------------
: Exam # 1 : :
------------------------------------------------------------------------
6. :Nonregular Languages, Pumping Lemma :10 :1-9,15,16
7. :Decidability :11 :9-13
8. :Context-free Grammars :12 :1-16
9. :Grammatical Format :13 :1-11,14
------------------------------------------------------------------------
: Exam # 2 : :
-----------------------------------------------------------------------
10. : Pushdown Automata (CFG=PDA) :14,15 :Ch14:1-3;Ch15:1-8
11. : Non-Context-Free languages, :16 :10-15
12. : Context-Free Languages :17 :1-3,7,8,9-12,19
13 : Decidability :18 :1,3,6-10
-----------------------------------------------------------------------
: Exam # 3 : :
----------------------------------------------------------------------
14. : Turing Machines : 19 : 1-6,19
15. : Recursively Enumerable Languages : 23 : 1-12
16 : Chomsky Hierarchy : 24 :TBA
17. : Computers and Computability : 25 :1,2
---------------------------------------------------------------------
Review - if time permits
----------------------------------------------------------------------
Final Exam -
----------------------------------------------------------------------