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:00-3:30 PM; other times by appointment
Email: welch@cs.tamu.edu
Office Phone: 845-5076
Home Phone: 774-0680 (please don't call after 9:00 PM)

Lecture: Tuesday and Thursday, 12:45-2:00 PM, HRBB 104

Textbook: The Theory of Computation, Bernard M. Moret, Addison-Wesley, 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/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 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/McGraw-Hill Book Company, 1990.

Course Goals:

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 Context-Free Languages and Push-Down 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:

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


Back to beginning


[Purpose] [Topic] [Written Report] [Oral Presentation] [Deadlines]

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.

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:

Also, think about your own research area.

Some good places to look for theory of computing papers are:

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:

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:

You should use overhead transparencies, either drawn neatly by hand or computer-generated. Judicious use of color, drawings and humor is encouraged.


If class size permits oral presentations, they will be scheduled later.

Back to beginning

DLS Reports

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

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 Follow the links in the calendar to get

Monday Tuesday Wednesday Thursday Friday
Introduction and Math Preliminaries
Read preface, Ch 1-2, Appendix A
1/19 1/20
Languages, Regular Expressions and Regular Grammars
Read Ch 3
1/24 1/25
Regular Grammars and Finite Automata
DLS: Mitchell
Converting NFA to DFA
Converting reg expr to NFA
Converting NFA to reg expr
1/31 2/1
Converting between reg grammar and NFA
HW due
Mitchell report due
2/2 2/3
Pumping Lemma for Regular Languages
DLS: Shin
Closure Properties of Regular Languages
2/9 2/10
Context-Free Grammars
Shin report due

Monday Tuesday Wednesday Thursday Friday
2/14 2/15
Pushdown Automata
HW due
2/16 2/17
Pumping Lemma for CFLs
2/21 2/22
Turing Machines
Read Ch 4
2/23 2/24
More on Turing Machines
2/28 2/29
Skim Ch 5
Project proposal due
3/1 3/2
Undecidability of the Halting Problem
Blank Tape Problem and Reductions
Rice's Theorem
HW due

Monday Tuesday Wednesday Thursday Friday
Spring Break
Spring Break
Spring Break
Spring Break
Spring Break
DLS: Borg
More on Reductions
Read Ch 6
DLS: Witten
Complexity Classes, Deterministic Space Hierarchy
3/27 3/28
Deterministic Time Hierarchy, Model Independent Classes
Borg report due
Nondeterministic Classes
SAT is NP-complete
HW due
Witten report due
4/5 4/6
NP-Complete Reductions
Read Ch 7, sec 1

Monday Tuesday Wednesday Thursday Friday
4/10 4/11
More NP-Complete Reductions
4/12 4/13
Restricting Hard Problems, Strong NP-Completeness
Read Ch 8
DLS: Perkins
Approximation Algorithms
HW due
4/19 4/20
More Approximation Algorithms
Perkins report due
4/24 4/25
Student presentations
4/26 4/27
Student presentations
last day of class
Project report due
5/1 5/2
HW due
reading day
reading day
finals start

Back to beginning

Useful Links

Computing-Related at TAMU

Back to beginning