CS 390 - Introduction to Theoretical Computer Science
Fall 2011 - Syllabus/Course Outline
Name: Jay
Morris
Office: Dragas Hall 1105E
Email: jdm@cs.odu.edu
ODU Phone:
757-683-6001
Fax Number: 757-683-4900
Meeting Times:
Monday/Wednesday/Friday
4:20
Place: Dragas Hall 1117
Office Hours:
Mon, Wednesday: 1500-1630
Course Text:
Introduction to Languages and the Theory of Computation
John C. Martin, McGraw Hill,
4th edition
Prerequisite: CS 381
It is assumed that students are
familiar with material covered in CS 381. These topics include formal logic,
sets, relations, functions, closures, and mathematical induction.
Course
Objectives: We want to learn about computation independent of platform. To study
computation we will need to consider topics such as grammars, regular languages,
context-free languages, automata and Turing Machines.
Grading Issues
Grade Percentages
Homework 10%
Tests (3) 60%
Final 30%
The instructor reserves the right to modify this distribution, add
quizzes etc as required.
Ten point grading scale: 90-100 = A etc.
The
honor code will be strictly enforced. For homework you may discuss and confer
with one another but each of you must create his/her individual documents for
submission. If you submit a document for homework credit then it is assumed that
you not only created the original yourself but that you also understand what you
have submitted.
Attendance : You are not required to attend. You are
responsible for the materials covered in class. In the case of an excused
absence, I will attempt to help you make up the material. You are responsible
for the lectures, reading assignments and homework. If you miss a class without
an acceptable excuse please do not ask the instructor what was covered.
Topics: We will study the theory of computation by using grammars that
generate languages and by using abstract machines as an alternative approach.
The text also introduces recursive function theory but unfortunately we will not
have time to look at this interesting method. Note that grammars, abstract
machines and recursive functions are three means to the same end, that being the
study of languages and computation. We will cover regular languages and finite
automata (chapters 3-5) followed by context-free languages and pushdown automata
(chapters 6-8). Regular and context-free languages play important roles in many
applications. We will investigate the Turing Machine (chapters 9-11).
Surprisingly this simple machine is more powerful than any computer that can
ever exist; thus the Turing Machine determines the upper limit on computability.
If time permits we will look at unsolvable problems and also at intractable
problems (chapters 12 and 15). Just in time since unsolvable problems make such
nice questions for a final. This schedule may be modified during the term to
adjust for contingencies.
On homework and tests in this course the word show
means prove. If we want an example then we will ask for an example explicitly.