63.460: Theory of Computing
David
Keil,
SYLLABUS
Course description (FSC catalog)
An introduction to theoretical computer science and some key
applications. Course examines models of computation, including finite automata,
transducers, pushdown automata, and Turing machines. Concepts of formal
language theory are applied to lexical analyzer and compiler construction in
programming-language translation. The course will include an introduction to
the notions of computability and computational complexity, concepts used in
parallel computation, and some aspects of artificial intelligence.
Prerequisites: 43.292 Discrete Mathematics I and 63.271 Data Structures.
Course overview
Our central theme is models of computation. One question to be addressed: Is communication part of computation? Experts disagree.
Our foundation for this course is a group of concepts presented in Discrete Mathematics courses: logic, proofs, sets, cardinality, relations, graphs, and functions. We will present proofs that certain abstractions, such as real numbers, predicates, and functions, are uncountable.
We will use logic and methods of proof to show relationships among certain sets (e.g., languages), certain graphs (e.g., automata), and certain functions (e.g., computable ones).
What problems can be solved by computation? We will begin to sketch and answer by discussing a very simple three-operation programming language that can implement any algorithm, and we will relate that programming system to a set of functions that may be defined recursively.
We will investigate three increasingly powerful machine models associated with state-transition diagrams, each of which corresponds to a language model (kinds of input sequences the model can recognize). This hierarchy of simple models of computation consists of finite automata, stack machines, and Turing machines.
As we are discussing finite-state automata and pushdown automata, we will address program compilation, which puts these theoretical concepts into practice.
In discussing Turing machines and the
In summary, starting with the simplest kinds of abstract computing devices, we will show that any of three equivalent models is able to compute any algorithmically computable function.
We will also look at theoretical models of interactive systems and parallel and distributed systems. We will present results showing that interaction requires more expressive models than those for algorithms. Our hypothesis is that multi-stream interaction requires more expressive models than sequential interaction.
This course differs from the other theoretical course in
Computer Science, 63.347 Analysis of Algorithms, in that our concern here is models
and expressiveness
or computational power rather than performance or efficiency.
It is expected that before taking 63.460, students are familiar, from their work with dicrete math and data structures, with the notions of logic, sets, functions, relations, graphs, mathematical proof, different implementations of collections of data, and algorithms used to manipulate them.
Required reading
· Hopcroft, Motwani, and Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Ed. (Addison-Wesley, 2007), 0-321-45536-3
· Mitchel Resnick, Turtles, termites, and traffic jams (MIT Press, 2000), 0-262-68093-9
· Handout material that will include papers on computability, interaction, and cognitive systems
· Slides: See handouts and course web site.
Reading and studying text material related to the course is
a must. Slides and the study questions help tell which concepts are most
important to this course, but to understand this material, in-depth reading is
required, reinforced by exercises.
To contact instructor:
Office hours (Hemenway Hall 318A):
M
Th
Office: Hemenway Hall 318A
Telephone: (508) 626-4724
Email:
URL: www.framingham.edu/faculty/dkeil
Classroom format
Format will center on discussion, problem solving, and lecture with slides. Your questions and participation are essential. Part of our responsibility is to express doubt about each other’s claims.
On many occasions we will divide into in-class teams to solve discussion problems.
We will have one conversation in the classroom. Students may use laptops and enter and leave classroom consistent with a focused workplace governed by attention to business and by mutual respect.
Group work
This course involves work in which groups will solve different problems and present solutions.
Web aspect of course
This course is listed under http://framingham. blackboard.com. The site hosts a private discussion board for students enrolled in the course. Group work is to be submitted at the Blackboard Discussion Board, which is also a forum for written discussion.
Research paper
Each student will propose a topic for a short research paper, submit a preliminary version that responds to comments about proposal; present the paper in class; and submit a final version at the end of the course period. Subject to proper formatting, textual presentation, and documentation, all papers will be made available on the Web.
Papers should be at least 600 words and should use at least three proper references that are books, journal papers, or conference papers, i.e., edited or peer-reviewed sources. Format references to your sources using some variant of the American Psychological Association style. (For information on formatting and documenting research see, for example, http://owl.english.purdue.edu/ handouts/research/r_apa.html or http://webster. commnet.edu/apa/apa_intro.htm.)
Research should be in some area covered by the course, with meaningful references to the course’s textbook sources or handouts. Reference to the course material will be an important aspect of the research paper.
The following elements should appear in the research paper submission: title, byline, name of college, course number, date, page numbers, references at end and in body, and subsections. Use complete sentences with correct spelling and grammar.
Students will also be asked to critique each other’s research proposals and drafts.
Coding project
Students will complete a short project to implement some computation or model discussed in topics of the course. One option is to write a lexical analyzer and parser for arithmetic expressions. This project relates topics 3 and 4 to compiler construction. Project need not be lengthy.
Grading
Mini-quizzes are closed-book short-answer. Major quizzes are open-book and open notes. Final exam includes both types of question.
Participation includes attendance, class discussion, and written discussion via Blackboard.
Allocation of grading weights is as follows:
Graded group work 20
Major quizzes (2) 20
Mini-quizzes (6) 20
Final exam 20
Research paper 10
Coding project 5
Participation 5
100
Learning objectives
1. To gain a survey understanding of computability, automata, formal languages, parallel and distributed computing, and cognitive systems;
2. To recognize and construct automata with given behavioral features;
3. To use constructive, inductive, and diagonal proof methods;
4. To describe several models of computation
5. To create a simple formal computational model;
6. To compare and contrast algorithmic and interactive computation, relating interaction to problems associated with intelligence;
7. To relate theoretical concepts to practical applications, including with programming code;
8. To recognize some uncomputable functions;
9. To perform research in this area, drafting, documenting, and revising results;
10. To constructively criticize the work of others;
11. To present research to a group.
Research interest of instructor
Two special themes are: 1) can multi-agent systems (3 or more interacting entities) do things that two computing entities (a conversation) cannot? 2) Can indirect interaction via the environment (e.g., bulletin boards, markers left on trails) give systems more power than message passing?
The instructor is writing a doctoral thesis on scalable models of computation for multi-agent systems. Students in 63.460 are invited to participate in the research process by learning about these models and brainstorming about this question.
Collaboration and acknowledgement
of intellectual debts
All writing presented as one’s own must be one’s own. There is no objection to working together on ungraded exercises. Quizzes and final exam are to be done without communication.
It is expected that scholarly work is not entirely original, in that it is based on the work of others in the past. These intellectual debts must be acknowledged by using references to sources. Research papers must be properly referenced.
Educational philosophy
The approach used is aimed at helping the student construct knowledge for himself/herself by grappling with new ways of thinking and new facts, rather than memorizing facts. This approach favors collaboration, questioning, and problem solving. For an example of writing about this teaching approach, see Kain Bain, What the Best College Teachers Do (Harvard Univ. Press, 2004).
Accommodations
Students who seek accommodations during the semester because of disabilities should meet with the instructor after class or during office hours early in the semester.
Course Plan
|
Dates |
Topic |
|
|
1/29 |
Introduction and discrete-math review |
Handout; |
|
1/29-2/5 |
1. Cardinalities of sets, diagonal proof, |
Handouts |
|
2/12-2/26 |
2. Deterministic finite automata, regular languages, and lexical analysis |
|
|
2/26 |
Major Quiz 1 (topics
1-2) |
|
|
3/4-3/25 |
3. Pushdown automata, context-free grammars, |
|
|
3/25-4/8 |
4. Turing machines and undecidability |
|
|
4/8 |
Major Quiz 2 (topics 3-4) |
|
|
4/15-4/22 |
5. Random access machines and recursively definable functions |
Davis-Sigal-Weyuker handout |
|
4/22-5/6 |
6. Models of interactive, parallel, and distributed computation |
Wegner handout, Goldin handout; others |
|
5/6 |
Research paper
presentations and course review |
|
|
5/13 |
Final exam (Topics 1-6) |
|