CPSC 627: Theory of Computability
Spring 2000
[Syllabus]
[Announcements]
[Project]
[DLS Reports]
[Calendar]
[Useful Links]
Instructor:
Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: Tuesday and Thursday, 2:003:30 PM; other times by
appointment
Email: welch@cs.tamu.edu
Office Phone: 8455076
Home Phone: 7740680 (please don't call after 9:00 PM)
Lecture:
Tuesday and Thursday, 12:452:00 PM, HRBB 104
Textbook:
The Theory of Computation,
Bernard M. Moret,
AddisonWesley, 1998.
Web page for the text book is
http://www.cs.unm.edu/~moret/computation  here you will
find some problem solutions and errata sheet.
Prerequisite:
CPSC 311 (Analysis of Algorithms) or equivalent, or permission
of the instructor.
(The catalog is incorrect in stating that CPSC 433 is a prerequisite.)
Course URL: http://www.cs.tamu.edu/courseinfo/cpsc627/welch
THIS IS A THEORETICAL COURSE.
The emphasis will be on formal models of computing and proving
possibility and impossibility of solving certain problems in
certain models.
You are expected to be familiar with the general concepts involved
in designing and analyzing sequential algorithms, at the undergraduate
level.
Such familiarity would come from CPSC 311 or equivalent.
A good reference book for sequential algorithm analysis is
Introduction to Algorithms, Thomas H. Cormen,
Charles E. Leiserson, and Ronald L. Rivest, The MIT Press/McGrawHill
Book Company, 1990.
Course Goals:
 To introduce you to the theoretical foundations of computer
science concerning
 the relationships between languages and machines
 the inherent limits of what can be computed
 the inherent efficiency of solving problems
 To familiarize you with the applications of these theoretical
topics to practical problems
 To increase your ability to recognize and create rigorous
mathematical arguments
Course Content and Tentative Schedule:
The course will cover the following topics.
The relevant chapters of the textbook are indicated.
More detailed reading assignments and supplemental material
will be given later.
week of
 topic
 chapter

1/17
 Introduction
 preface, 1, 2, Appendix A

1/24 , 1/31
 Finite Automata and Regular Languages
 3

2/7, 2/14
 ContextFree Languages and PushDown Automata
 supplement

2/21
 Turing Machines
 4

2/28, 3/6
 Computability Theory
 5, supplement

3/13
 Spring Break
 .

3/20
 Complexity Theory
 6

3/27, 4/3
 Reductions
 7

4/10
 Approximation
 8

4/17 , 4/24
 Applications TBA
 supplement

Assignments and Grading:
All assignments will be announced in class and posted on the course web page.
If you cannot turn in an assignment on time, discuss the situation
in advance with the instructor.
Your grade will be based on three components:
 homeworks 50%  homework will consist of written problems
(e.g., design an algorithm, extend or modify a result presented
in class). Homework assignments will be due roughly every 2 or 3 weeks.
Click here for assignments so far.
 project 40%  a term project involving a written report
and possibly an oral presentation.
More information is here.
 culture 10%  reports on the
Distinguished
Lecturer Series.
More information is here.
Course grades will be assigned according to this scale:
A for 90% or above of the total points,
B for 80 to 89%,
C for 70 to 79%,
D for 60 to 69%,
and F for less than 60%.
Collaboration:
Discussion of concepts with others and consulting written sources
is encouraged, but all assignments must be done on your
own, unless otherwise instructed.
If you use any source other than the text, reference it/him/her,
whether it be a person, a book, a solution set, a web page or whatever.
You MUST write up the solutions in your own words. Copying is
strictly forbidden.
University Regulations, Section 42, define scholastic
dishonesty to include acquiring answers from any unauthorized source,
working with another person when not specifically permitted, observing
the work of other students during any exam, providing answers when not
specifically authorized to do so, informing any person of the contents
of an exam prior to the exam, and failing to credit sources used.
Disciplinary actions range from grade penalty to expulsion.
Back to beginning
 4/17: Please see CORRECTED hint for 7.23.
 4/14: Click here if you want
a hint on homework problem E3 (Ex 7.27(1)).
Also, a clarification/correction on Ex. 721: a vertex also
dominates itself; and a vertex also dominates any edge incident
upon itself.
 4/13: Click here if you want
a hint on homework problem E2 (Ex 7.23).
 3/7: I've completed problem set C and added a clarification
to the problem about the 2D tape.
 2/29: Problem set C due date is postponed to Thu, Mar 9.
Additional problems will be added.
 2/29: My handwritten lecture notes on Decidability are available
from Bright building copy center.
 2/22: Homework is due 3/2. A fifth Distinguished Lecturer has
been added on Mar 20.
 2/10: Click here if you want
a hint on homework problem B4 (Ex 3.25, part (2)).
 2/10: The complete problem set B is now available.
 2/3: I moved up the due date for the Shin report to 2/10
from 2/15, because there is now homework due on 2/15.
(If this is a hardship, you can turn in the Shin report
on 2/15 along with the homework.)
 1/31: Corrections and clarifications to the homework:
 Exercise 3.4, part 3: If a string has length less than 4,
then it has no substring of length 4 and thus the condition
required is trivially true.
 Exercise 3.7, part 1: If you have already done the problem
with both final states, that is fine. Otherwise, you may
assume that only the start state is a final state.
(Note that the statement of the exercise said that there was
only one final state per DFA.)
 Exercise 3.7, part 2: Notice that this is not a DFA as
drawn, because the top right state has two outgoing transitions
labeled 1. To fix this, change the label on the transition
going to the state below to be 0.
 1/20: A fifth Distinguished Lecturer will probably be added shortly
to the culture assignment. Dates will be announced as soon as they
are available.
Back to beginning
[Purpose]
[Topic]
[Written Report]
[Oral Presentation]
[Deadlines]
Purpose: This assignment has several purposes:
 introduction to the technical literature in the area,
 application of ideas and techniques presented in class in a more
extensive and openended environment than in the homework,
 practice in writing technical documents,
 practice in making oral presentations (class size permitting).
I encourage you to discuss your project with me as often as you like,
and at any stage, especially early on.
Topic:
Your project will involve reading several related papers
from the technical literature and explaining the results in your own words.
There must also be some original aspect to your work, for instance,
a critical analysis of what is done;
a comparison with other work;
making a connection between this area and another area;
finding a simpler presentation of the work; or
extending the work in some way.
Your topic must be the use of computability or
complexity analysis, as presented in class or in the textbook,
to an application area.
Some potential application areas are:
 cryptography
 computational learning theory
 VLSI ciruit testing
 logic
 artificial intelligence
Also, think about your own research area.
Some good places to look for theory of computing papers are:
 Journals:
 Journal of the ACM
 Information and Computation
(formerly Information and Control)
 SIAM Journal on Computing
 Algorithmica
 Theoretical Computer Science
 Information Processing Letters
 Mathematical Systems Theory
 Journal of Computer and System Sciences
 Acta Informatica
 Conference proceedings:
 ACM Symposium on Theory of Computing (STOC)
 IEEE Symposium on Foundations of Computer Science (FOCS)
 IEEE Conference on Computational Complexity
 International Colloquium on Automata, Languages and Programming
(ICALP)
 The worldwideweb: Many people have copies of their papers
available on line. Here are some bibliography links:
Written Report:
The report is to be typed, at least 10 pages long and no more than
20 pages long.
If you believe you have a good reason why the length of your paper
should not conform to these guidelines, discuss it with me in advance.
Part of your grade will be based on the quality of your composition
(including spelling, grammar, logical flow).
Typical organization for a technical paper in this area is:
 introduction (informal explanation of problem, why it
is important/interesting, overview of the paper contents)
 formal definitions
 results
 conclusion (including open problems).
As a general rule, very little, if any, of your paper should consist
of copying the contents of the papers you read, and of course if you
do quote from a paper, be sure to credit the source.
Oral Presentation:
You will be allotted some number of minutes (depending on the size of the
class) for your presentation. This is a STRICT limit. In order to
maximize the effectiveness of your presentation, you should carefully
plan what you will say and PRACTICE. This is not enough time to go
into technical details. A good organization is:
 describe the application area and problem,
 explain why they are interesting/important,
 state the computability/complexity result(s)
 give an overview of the technicalities
 summarize your original contribution
 conclude and describe any interesting related open problems.
You should use overhead transparencies, either drawn neatly by hand or
computergenerated. Judicious use of color, drawings and humor
is encouraged.
Deadlines:
 Feb 29:
Turn in your project proposal  a page or two describing your chosen
topic and what you plan to do, and listing at least three
research papers upon which your project will be based.
A significant amount of work should go into this choice.
If your plan is not sufficiently relevant to the course, I will
not approve it, so it is best to talk with me in advance about
your plans.
 Apr 27:
Written project report due.
If class size permits oral presentations, they will be scheduled later.
Back to beginning
We are fortunate to have a
distinguished
collection of computer scientists coming to visit this semester.
For each visitor, you
are STRONGLY ENCOURAGED to attend the seminar.
If you have a legitimate scheduling conflict for a seminar,
then you can substitute attendance by reading a technical paper
by the speaker.
For each distinguished lecturer, you are to submit a short (1 to 2
page) typed report. The report must include
 brief biography of the lecturer
 summary of the lecture (or paper)
 your assessment of the level of contribution of the work described
 three questions raised in your mind by the lecture (or paper)
 bibliography of your sources for the biography
If you read a paper instead of attending the seminar, be sure
to attach a copy of the paper to your report and indicate
the full bibliographic citation of the paper.
Back to beginning
This calendar lists all due dates as they become known for
 readings
 homework
 project
 DLS reports
Follow the links in the calendar to get
 details on the assignments
Monday
 Tuesday
 Wednesday
 Thursday
 Friday

1/17
Holiday
 1/18
Introduction and Math Preliminaries
Read preface, Ch 12, Appendix A
 1/19
 1/20
Languages, Regular Expressions and Regular Grammars
Read Ch 3
 1/21

1/24
 1/25
Regular Grammars and Finite Automata
 1/26
DLS: Mitchell
 1/27
Converting NFA to DFA
Converting reg expr to NFA
Converting NFA to reg expr
 1/28

1/31
 2/1
Converting between reg grammar and NFA
HW due
Mitchell report due
 2/2
 2/3
Pumping Lemma for Regular Languages
 2/4
DLS: Shin

2/7
 2/8
Closure Properties of Regular Languages
 2/9
 2/10
ContextFree Grammars
Shin report due
 2/11

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

2/14
 2/15
Pushdown Automata
HW due
 2/16
 2/17
Pumping Lemma for CFLs
 2/18

2/21
 2/22
Turing Machines
Read Ch 4
 2/23
 2/24
More on Turing Machines
 2/25

2/28
 2/29
Decidability
Skim Ch 5
Project proposal due
 3/1
 3/2
Undecidability of the Halting Problem
 3/3

3/6
 3/7
Blank Tape Problem and Reductions
 3/8
 3/9
Rice's Theorem
HW due
 3/10

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

3/13
Spring Break
 3/14
Spring Break
 3/15
Spring Break
 3/16
Spring Break
 3/17
Spring Break

3/20
DLS: Borg
 3/21
More on Reductions
Read Ch 6
 3/22
DLS: Witten
 3/23
Complexity Classes, Deterministic Space Hierarchy
 3/24

3/27
 3/28
Deterministic Time Hierarchy, Model Independent Classes
Borg report due
 3/29
 3/30
Nondeterministic Classes
 3/31

4/3
 4/4
SAT is NPcomplete
HW due
Witten report due
 4/5
 4/6
NPComplete Reductions
Read Ch 7, sec 1
 4/7

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

4/10
 4/11
More NPComplete Reductions
 4/12
 4/13
Restricting Hard Problems,
Strong NPCompleteness
Read Ch 8
 4/14

4/17
DLS: Perkins
 4/18
Approximation Algorithms
HW due
 4/19
 4/20
More Approximation Algorithms
Perkins report due
 4/21

4/24
 4/25
Student presentations
 4/26
 4/27
Student presentations
last day of class
Project report due
 4/28

5/1
 5/2
HW due
 5/3
reading day
 5/4
reading day
 5/5
finals start

Back to beginning
ComputingRelated at TAMU
Back to beginning