CSCI546 Introduction to Theory of Computation
Deterministic and non-deterministic Turing machines, decidable and
undecidable problems, complexity classes P and NP. PreReq: 431 Elective in
the CSci BS.
Note: this class will make more sense if you have completed CSCI500 first.
CSCI 646 Theory of Computation
Theoretical foundations of computer science: models of Computation,
recursive functions; Church's thesis and undecidable problems; complexity classes: P, NP, CO-NP and PSPACE. Prereq: classified. Elective in the CSci MS.
Note: this class will make most sense if you have completed CSCI600 or 500 first.
If you are enrolled in CS646 then to earn full credit for the work
you have to select the tougher exercises marked by an exclamation
mark in the book(!).
Why take this class
- Do you want to be a millionaire?
[ http://www.claymath.org/ ]
- Do you want to tackle some of the most intriguing and powerful
results in the whole CSci curriculum?
- Why is some encryption so hard to crack? Does it have to be that way?
- Why am I still waiting for the answer? Has the computer crashed?
- Which programs can not be solved by programming?
- What kind of problem is hard to solve quickly?
Instructor Information
I haven't taught this class for nearly a decade. I've
never taught it with this text book or as a co-scheduled
class (CS546 + CS646).
[ ../index.html ]
Calendar, Schedule, Required Work
The schedule may have to change.... since I've not used this
book before etc...
[ schedule.html ]
Support, Instructional Methods, Policies, & Grading
[ ../syllabus.html ]
Readings
Required Text
- INTRODUCTION TO AUTOMATA AND LANGUAGE THEORY
- John E. Hopcroft & Rajeev Motwani & Jeffrey D. Ullman
[ ialc.html ]
- Addison Wesley 2001 ISBN 0-201-44124-1
(We'll cover chapters 1,2,8,9,10, and 11 of it in this course, the
rest was in the previous quarter's theory course).
A relevant book
The following was used in previous editions of this class.
You may find it helpful but you don't need to buy it if you
haven't got a copy:
- Author: John Martin
- Title: Intro to Languages and Theory of Computation
- Edition: 3rd ISBN#: 0-07-232200-4
[ http://highered.mcgraw-hill.com/sites/0072322004/ ]
A Classic Text
- Marvin Minsky
- Computation: Finite and Infinite Machines
- Prentice Hall 1964
- =TEXT THEORY OBSOLETE READABLE TURING AUTOMATA FUNCTIONS POST
- Written before complexity and intractability was published.
I will be handing out a couple of pages as reading for one class.
This has just been rated the 13th most popular computer science book
that is out of print by the Association for Computing Machinery.
Do not buy -- unless you see a second hand copy going cheap.
Library
There are very few books on computability and tractability in the
CSUSB library. Possible library of congress classifications are
QA9 (Foundations of mathematics) and QA76.6 G35. I have found
(and borrowed) a useful reference work: Michael R Garey & David
S Johnson, Computers and Intractability: A Guide to the theory of
NP-Completeness, Bell Telephone Labs 1979.
Research on the World Wide Web
The preparation for two classes requires you to search the web
for topics and submit a relevant URL that you have discovered
as assigned work/study.
. . . . . . . . . ( end of section Readings) <<Contents | End>>
Work to be done
Project Work and Programming(6%)
You will work in a team to produce a simple simulator
of a Turing Machine. More details in the schedule. The whole
project earns 30 points: 10 points for a progress report(2%) and 20
points (4%) for the finished product and presentation.
Bonus(2%)
I will ask you to program and test a single, well known function.
This is a bonus of 10 points(2%).
Assigned work(26%)
(Study): The schedule assigns a piece of reading to be studied to prepare
for class.
You must "[Submit]" a questions based on the reading using the
"[Submit]" button on the web pages at least one hour before the start of
each class. This is worth 2 points if on time. You get a 2point
bonus for attending the first class.
Notice that if you don't ask about something we probably will not
spend time class time on it. So ask about things you need help with.
(Ex): You should
also attempt all the exercises that you have time for and bring
a written answer to one of them that is not marked by an asterisk(*).
An exercise is one part of a numbered exercise. For example, you
can hand in an attempt at exercise 2.2.1 b if you are taking 646
and 2.2.1 c if you are taking 546. However 2.2.1 a is on the web
and so won't count. You will get the same ammount of credit
which ever exercise part you hand in (within the above rules).
Don't forget that I may not pick the easy ones to formulate
questions for the final and so it may pay you to hand in an
exercise that you are doubtful about. By the way, if you
work for more than an hour on any one (non!) exercise part
you may need help -- and I'm available in my office.
You may work in a team of up to 4 people and hand in one answer
with all the names on the front sheet. This is worth 5 points(1%).
All members of the team will get the same score. I will pick
one person from the team to present -- and they may lose all their
points if they apparently don't know what their team did.
When the reading in the schedule is on the web you should
"[Submit]" a URL for a page at least one hour before class. This is
worth 5 points max(1%).
Quizzes and Exams (50%)
The will be a short test of the material in the first chapter
of the book (math) in the third class -- it contributes 50 points(10%)
to the total grade for the class. The final exam is comprehensive
and contributes 200 points (40%) to the total grade.
Participation (20%)
To earn all 5 points you must: (1) turn up and be ready to take
part at the start of the class, (2) stay until the class is dismissed,
(3) Answer questions, (4) ask questions, and (5) take part in
class discussions and exercises.
. . . . . . . . . ( end of section Work to be done) <<Contents | End>>
Grading
All points earned before the final will be totaled with the maximum
possible score being set to 300 points. The maximum on the final is
200 points. These two totals will be added together to calculate
the grade for the course according to the rules
[ ../syllabus.html ]
in my generic syllabus.