CPSC 627: Theory of Computability
Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: Tuesday and Thursday, 2:00-3:30 PM; other times by
Office Phone: 845-5076
Home Phone: 774-0680 (please don't call after 9:00 PM)
Tuesday and Thursday, 12:45-2:00 PM, HRBB 104
The Theory of Computation,
Bernard M. Moret,
Web page for the text book is
http://www.cs.unm.edu/~moret/computation -- here you will
find some problem solutions and errata sheet.
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/course-info/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
You are expected to be familiar with the general concepts involved
in designing and analyzing sequential algorithms, at the undergraduate
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/McGraw-Hill
Book Company, 1990.
- To introduce you to the theoretical foundations of computer
- 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
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
|| preface, 1, 2, Appendix A
| 1/24 , 1/31
|| Finite Automata and Regular Languages
| 2/7, 2/14
|| Context-Free Languages and Push-Down Automata
|| Turing Machines
| 2/28, 3/6
|| Computability Theory
|| 5, supplement
|| Spring Break
|| Complexity Theory
| 3/27, 4/3
| 4/17 , 4/24
|| Applications TBA
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
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%.
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
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 E-3 (Ex 7.27(1)).
Also, a clarification/correction on Ex. 7-21: a vertex also
dominates itself; and a vertex also dominates any edge incident
- 4/13: Click here if you want
a hint on homework problem E-2 (Ex 7.23).
- 3/7: I've completed problem set C and added a clarification
to the problem about the 2-D 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 B-4 (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
Back to beginning
Purpose: This assignment has several purposes:
I encourage you to discuss your project with me as often as you like,
and at any stage, especially early on.
- introduction to the technical literature in the area,
- application of ideas and techniques presented in class in a more
extensive and open-ended environment than in the homework,
- practice in writing technical documents,
- practice in making oral presentations (class size permitting).
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:
Also, think about your own research area.
- computational learning theory
- VLSI ciruit testing
- artificial intelligence
Some good places to look for theory of computing papers are:
- Journal of the ACM
- Information and Computation
(formerly Information and Control)
- SIAM Journal on Computing
- 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
- The world-wide-web: Many people have copies of their papers
available on line. Here are some bibliography links:
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:
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.
- introduction (informal explanation of problem, why it
is important/interesting, overview of the paper contents)
- formal definitions
- conclusion (including open problems).
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:
You should use overhead transparencies, either drawn neatly by hand or
computer-generated. Judicious use of color, drawings and humor
- 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.
If class size permits oral presentations, they will be scheduled later.
- 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
- Apr 27:
Written project report due.
Back to beginning
We are fortunate to have a
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
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.
- 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
Back to beginning
This calendar lists all due dates as they become known for
Follow the links in the calendar to get
- DLS reports
- details on the assignments
| 1/18 |
Introduction and Math Preliminaries
Read preface, Ch 1-2, Appendix A
|| 1/20 |
Languages, Regular Expressions and Regular Grammars
Read Ch 3
|| 1/25 |
Regular Grammars and Finite Automata
| 1/26 |
| 1/27 |
Converting NFA to DFA
Converting reg expr to NFA
Converting NFA to reg expr
|| 2/1 |
Converting between reg grammar and NFA
Mitchell report due
|| 2/3 |
Pumping Lemma for Regular Languages
| 2/4 |
| 2/7 |
| 2/8 |
Closure Properties of Regular Languages
|| 2/10 |
Shin report due
|| 2/15 |
|| 2/17 |
Pumping Lemma for CFLs
|| 2/22 |
Read Ch 4
|| 2/24 |
More on Turing Machines
|| 2/29 |
Skim Ch 5
Project proposal due
|| 3/2 |
Undecidability of the Halting Problem
| 3/6 |
| 3/7 |
Blank Tape Problem and Reductions
| 3/8 |
| 3/9 |
| 3/13 |
| 3/14 |
| 3/15 |
| 3/16 |
| 3/17 |
| 3/20 |
| 3/21 |
More on Reductions
Read Ch 6
| 3/22 |
| 3/23 |
Complexity Classes, Deterministic Space Hierarchy
|| 3/28 |
Deterministic Time Hierarchy, Model Independent Classes
Borg report due
| 3/29 |
| 3/30 |
| 4/3 |
| 4/4 |
SAT is NP-complete
Witten report due
|| 4/6 |
Read Ch 7, sec 1
|| 4/11 |
More NP-Complete Reductions
|| 4/13 |
Restricting Hard Problems,
Read Ch 8
| 4/17 |
| 4/18 |
|| 4/20 |
More Approximation Algorithms
Perkins report due
|| 4/25 |
|| 4/27 |
last day of class
Project report due
|| 5/2 |
| 5/3 |
| 5/4 |
| 5/5 |
Back to beginning
Computing-Related at TAMU
Back to beginning