CPSC 627: Theory of Computability
Spring 2000

Syllabus

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.

• 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.

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

Announcements

• 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 upon itself.

• 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 are available.

Back to beginning

Project

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 open-ended environment than in the homework,

• practice in writing technical documents,

• practice in making oral presentations (class size permitting).

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

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 world-wide-web: Many people have copies of their papers available on line. Here are some bibliography links:
  • Collection of CS Bibliographies
  • Hypertext Bibliography Project

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).

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.

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.

Back to beginning

DLS Reports

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

Back to beginning

Calendar

• readings
• homework
• project
• DLS reports

• details on the assignments

Back to beginning

Useful Links

• Computer Science Department, TAMU

• Student Computing and Information Page: central source of information about student computing at TAMU.

• Schedule of short courses offered by the CIS Computer Help and Training Group. Includes introduction to TAMU computing resources, introduction to the Internet, using netscape, Unix.

Back to beginning