Saint Mary’s University
Department of Mathematics and Computing Science
CSC 452.2: Topics in Theoretical Computing Science I
WINTER 1998-99
Instructor: Dr. Pawan Lingras
Class time: Tuesday and Thursday 4:00-5:15 p.m.
Room: L269 (Loyola Academic Complex)
Brief Description
In conjunction with CSC 451.1, this class is designed to provide a detailed introduction to various topics in theoretical computing science. The second part deals with the languages and machines. The course will include mathematical background necessary for the analysis. The objectives of the course are:
Textbook
Thomas A. Sudkamp, Languages and Machines, Addison-Wesley Publishing Company Inc., New York, NY.
Topics
Week |
Topics |
Chapter |
1 |
Elementary Set Theory, Cardinality, Recursion, and Induction | 1 |
2 |
Words and Languages, Finite State Machines | 2, 6 |
3 |
Nondeterministic Finite Automata, Lambda NFA's | 6 |
4 |
Introduction to Context Free Grammars, Grammars and Languages | 3 |
5 |
Grammars and NFA's, | 7 |
6 |
Chomsky Normal Form & The Pumping Lemma | 5, 7 |
7 |
Normal Forms and Parsing, Midterm | 5 |
8 |
Automata Accepting LCF, CFG's and Closure Properties | 9 |
9 |
Turing Machines, Turing Machine Computations | 9 |
10 |
Turing Machine Variants, Church's Thesis | 11 |
11 |
Universal Turing Machines, Classical Undecideability Problems, Closure Properties and Post Correspondence | 11 |
12 |
Student Presentations | NA |
Evaluation scheme
Method of Evaluation |
Marks |
| In Class Quizzes (5) | 10 |
| Test 1 (Date TBA) | 25 |
| Test 2 (Date TBA) | 25 |
| Final | 40 |
Total |
100 |
Final Examination
The final examination will be scheduled by the Registrar’s office during the examination period from April 8-24, 1999. A link to the guide for the final examination will be available here.