MEMO

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: MATH 292 Discrete Mathematics I and CSCI 271 Data Structures.

Meeting times

MWThF 10:30-11:20 a.m.
Hemenway Hall 132 (annex)

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 the two equivalent models, Turing machines and Random Access 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 RAM model of computation, we will see that some computing problems cannot be solved algorithmically.

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, CSCI 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 CSCI 460, students are familiar, from their work with Discrete 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

· Handout material that will include papers on computability and interaction

· 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 12:30-1:30 p.m., W 9:30-10:30 a.m.,

F 12:30-1:20 p.m., others by appointment

Telephone: (508) 626-4724

Email: dkeil@framingham.edu

URL: www.framingham.edu/~dkeil

Basic or prerequisite skills

1. To manipulate strings, arrays, linked lists, and stacks

2. To use the inductive proof method

3. To define and represent directed graphs

4. To define and represent trees and to describe tree-based algorithms

5. To use the basic notations of sets, functions, logic, and formal language theory

Learning objectives

The entire course will be guided by the following learning objectives:

1a. To write a proof showing countability of a set

1b. To write a diagonal proof showing uncountability of a set

1c. To explain or write a coinductive definition

2a. To recognize and construct finite automata with given behavioral features

2b. To convert between regular expressions and finite automata

2c. To use non-diagonal proof by contradiction, e.g., the Pumping Lemma

2d. To use constructive proof to show expressiveness

2e. To perform simple lexical analysis (opt)

3a. To perform a derivation using a context-free grammar

3b. To define a context-free grammar

3c. To write a simple parser (opt)

4a. To describe three equivalent models of algorithmic computation

4b. To describe the Chomsky hierarchy

4c. To show some problems to be undecidable

4d. To explain the notion of reducibility of problems

5a. To explain the relation between recursive definability and computability of functions

6a. To distinguish algorithmic from interactive computation

6b. To compare and contrast models of algorithmic and interactive computation

7a. To describe some models of parallel computation

7b. To describe models of indirect interaction in distributed computation

7c. To describe self-organization in connectionist computing and multi-agent systems

8a. To relate theoretical topics to queuing, robotics, OCR, vision image processing, and information retrieval

8b. To perform and present research in theoretical computer science

8c. To solve a problem as part of a team

8d. To present a short talk in the classroom

8e. To write a short documented research paper

Topic quizzes and assignments will assess achievement of these objectives.

Grades and classroom format

The essay, “What we do in my classroom,” attached, is part of this syllabus. See especially guidelines there for assignments, grading, and collaboration.

Coding project

Students may optionally 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 2 and 3 to compiler construction.

Semester grading weights

Performance objectives 40

Assignments 10

Research paper 10

Problem-solving quizzes 10

Multiple-choice quizzes 10

Final exam 10

Preparation and participation 010
100 %

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.

Accommodations

“Students with disabilities who request accommodations are to provide Documentation Confirmation from the Office of Academic Support within the first two weeks of class. Academic Support is located in the Center for Academic Support and Advising (CASA). Please call (508) 626-4906 if you have questions or if you need to schedule an appointment.” (See www.framingham.edu/ CASA/ Accommodations/accomm.htm.)

	Topic	Reading
1/20-1/26	Introduction and discrete-math review	Handout; Hopcroft-Motwani-Ullman, Ch. 1
1/27-2/3	1. Cardinalities of sets, diagonal proof, incompleteness, coinduction	Handouts
2/4-2/17	2. Deterministic finite automata, regular languages, and lexical analysis	H-M-U, Ch. 2-4
2/18	Problem-solving quizzes on topics 1-2
2/23-3/3	3. Pushdown automata, context-free grammars, and parsing	H-M-U, Ch. 5-7
3/4-3/21	4. Turing machines and undecidability	H-M-U, Ch. 8-9
3/23	Problem-solving quizzes on topics 3-4
3/24-4/1	5. Random access machines and recursively definable functions	Davis-Sigal-Weyuker handout
4/4	Make-up quizzes on topics 1-4
4/6-4/13	6. Models of interactive computation	Wegner handout, Goldin handout
4/14	Problem-solving quizzes on topics 5-6
4/15-4/27	7. Models of parallel and distributed computation	Handouts
4/28-5/6	Quizzes, summary and course review
Fri., 5/13, 8:00 a.m.	Final exam (Topics 1-7)