Instructor

• Nobo Komagata, komagata@tcnj.edu, Holman Hall 229, Office hours: See http://www.tcnj.edu/~komagata/schedule

On-line Resources (required reading)

• Course web page: http://www.tcnj.edu/~komagata/csc460/05s
• The instructor's information page for students (http://www.tcnj.edu/~komagata/students.html)
• SOCS: http://socs.tcnj.edu/ (the following sections will be used for this course)
• E-mail: Convenient to send messages to the class or a group of students.
• Discussion: The SOCS discussion board will be used for certain types of announcements, question-answer, and discussion.  In order to get informed of postings in a timely manner, students should turn on the Email Notification feature of the SOCS discussion board.
• Grading: Used for posting module and course grades. Note that the "Grade" field will show "1" when the grade is available and the actual grade will appear in the "Note" field.

Catalog Course Description

This course focuses on the traditional, algorithmic theory of computation consisting of three subareas: (1) computability, (2) complexity theory, and (3) formal languages and automata. The topics include: Turing machines, decidability/undecidability, reducibility, Church-Turing thesis, context-free grammars/languages, push-down automata, finite automata, regular expressions/languages, and time/space complexity including NP-completeness. [Prerequisites: CSC310, CSC340]

Learning Goals

In this course, we examine a small number of general principles that lie behind a variety of computational phenomena so that we will be able to apply these principles to a broad range of real-world computation. One of the main goals of this course is to convince students that "theory" is useful for practically anyone. To do so, we need to observe examples of theory at work. Once we understand the benefits of using theory in general, we will be ready to explore Theory of Computation, which has always been behind the development of computer science. At the same time, we will also examine the limitations of Theory and identify what is really behind real-world computation. In this course, we will discuss most of the topics traditionally covered in an undergraduate-level Theory of Computation course. However, our approach will be to explore the possibility of applying Theory to practical problems which students are interested in. The course will not follow the textbook, nor will it do most of the textbook problems.

Content Goals (mastery of the following core concepts, deep understandings, misunderstandings, and technical knowledge)

1. Practical problems can often be transformed into research and computational problems. Every problem is associated with cost/significance, which is relative to the evaluator. Computational problems can be represented as a set, readily available as the input to computational processing. [problem]
2. A theory is a potentially infinite, consistent body of knowledge which can be systematically derived from a small number of abstract principles. The gap between the principles and the entire information is the source of the theory's predictive power. Also being abstract, a theory can be applied to a broad range of phenomena, which might appear distinct. [theory]
3. Interactive computation subsumes algorithmic computation, but not vice versa. That is, there is a qualitative difference between these two modes of computation. [interactive computation]
4. The algorithmic notion of computation can be represented in a variety of equivalent forms, which define a bounded class of sets. That is, there is a limit to algorithmic computation. [computability]
5. The computable class of sets contains a hierarchy of proper subsets which can be characterized by distinct grammars and automata. [formal languages and automata]
6. The practicality of an algorithm depends on its complexity relative to the input data size. [complexity]
7. Power set, also encompassing the distinction between determinism and nondeterminism, can introduce discontinuity with respect to computability and complexity. [power set]

Performance Goals (expected outcomes and abilities to be observed as a result of successful learning)

1. Identify real-world problems which are relevant to the student's life and can be tackled by computational means. [awareness]
2. Transform real-world problems into research problems, and then into computational problems, along with the analysis of the cost/significance of a problem. [transformation]
3. Analyze computational problems with respect to interactivity, computability, language/automata hierarchy, and complexity hierarchy. Then, evaluate the analysis with respect to its usefulness, correctness, and accuracy. [analysis/evaluation]
4. Respect, analyze, and give constructive criticisms to the ideas in the literature and those expressed by other people. [critical attitude]
5. Express ideas orally and in writing, in a manner clearly understood by other students (with equivalent background). Explain your own ideas orally and in writing, clearly and logically. Revise the ideas, reflecting the feedback from other students and the instructor. [communication]
6. Take initiative in both independent and group activities. Also extend the domain of theoretical inquiry beyond the scope prepared by the instructor. [initiative]
7. Reflect upon the student's own thinking process and assess the student’s own performance relative to the content and performance goals. [reflection]

Course Modules

This course is divided into the following four modules.

• Module A: Problems, Theories, and Computability (1)
• Module B: Computability (2)
• Module C: Formal Languages and Automata
• Module D: Complexity

However, the topics of this course cannot be clearly separated into disjoint components. Thus, these modules should not be considered rigidly. Instead, these modules should be considered as evaluation units so that students can check their achievements in a timely manner.

Assessment

This course is expected to facilitate learning experience with which students can analyze practical computational problems in a intellectual manner by applying principles in Theory of Computation. Therefore, students’ assessment must reflect their ability to do that in a realistic context. Take-home exercises are designed to provide activities reflecting the learning goals (except for Performance Goal 8) in a realistic context. Thus, students’ assessment will primarily based on how well they accomplish these exercises. As for Performance Goal 8, evaluation workshops will provide opportunities for students to reflect upon their thought processes and self-evaluate their achievements with respect to the learning goals.

The main assessment tools are students’ self-evaluation at the end of each module. Students will evaluate themselves with respect to the learning goals following the instructions on the self-evaluation form (preliminary eval form for Module A). Since students will be given the form at the beginning of each module, they will be aware of what they are expected to achieve for that module. The evaluation form will list the learning goals relevant to the module as well as evaluation criteria for the relevant goals. Analysis and reflections on take-home exercises will be most important as the exercises address the learning goals directly or indirectly. Students are also expected to respond to the instructor’s feedback on their take-home exercises. The evaluation workshop will generally include peer discussion sessions, when students can share their learning and evaluation experiences.

The grading scheme for self-evaluation (and the instructor’s adjustment) is as follows:

• Grade A: Achieved all the learning goals relevant to the module
• Grade B: Achieved almost all the learning goals (except for one or two evaluation criteria) relevant to the module
• Grade C/Pass: Achieved most of the learning goals relevant to the module

The grades A, B, and C may be qualified with ‘+’ or ‘-’, where applicable. The overall course grade will be the weighted average of the module grades as shown below (using the standard conversion A = 4.00, A- = 3.67, etc., according to http://www.tcnj.edu/~recreg/policies/grading.html#three, not http://www.tcnj.edu/~academic/policy/Grading.htm).

• Module A: 10% (lower weighting for practice purposes)
• Module B: 30%
• Module C: 30%
• Module D: 30%

If a student far exceeds the standard, s/he may be assigned an A+. Although there will be no course grade beyond A, an A+ (for a module) could offset, say, A- in another module. For example, if a student receives A, A-, A, and A+ for the four modules, respectively, s/he will receive an A for the course.

After almost every class meeting, there will be take-home exercises. Students are expected to do them and hand them in at the beginning of the next class meeting. Although these exercises will not be graded by the instructor, the instructor will give feedback on them and return them at the beginning of the next class meeting. When students self-evaluate, they will submit all the take-home exercises along with their responses to the instructors’ feedback. After submission of a module evaluation folder (called "portfolio"), the instructor will adjust students’ self-evaluation, provide comments, and temporarily return them to students for review (when possible). Note that all the submitted work will eventually be kept with the instructor.

Learning Activities

The main learning activities consist of class meetings (two 80-minute sessions per week) and take-home exercises (expected amount of work equivalent to 360 minutes per week). Take-home exercises will be given after almost every class meeting and due at the beginning of the next class meeting (unless otherwise stated). Class meetings will contain components such as the following:

• Clarification of the learning goals as well as explanation of the evaluation form
• Survey (occasionally)
• Presentation of examples, cases, questions, and problems by students and the instructor
• Discussion of ideas, principles, and hypotheses known by the public and researchers
• Class and group discussion of different types
• Explanation and practice of using the evaluation form (esp. during Module A)
• Explanation of the take-home exercises given that day
• Evaluation workshop (at the end of each module)

Course Topics (subject contents)

1. Types of problems
   1. Practical, research, and computational problems
   2. Condition and cost/significance of a problem
   3. Set representation of a problem
2. Notion of "theory"
   1. Applicability of a theory
   2. Definition in the context of mathematical logic
3. Computability
   1. Formal models of computation, e.g., Turing machines (TMs)
   2. Decidability/undecidability including diagonalization and halting problem
   3. Reduction
   4. Church-Turing thesis
4. Formal languages and automata
   1. Chomsky hierarchy
   2. Context-free languages (CFL), context-free grammars (CFG), push-down automata (PDA); properties of CFLs
   3. Regular languages, regular expressions (RegExp), finite automata (FA); properties of regular languages
5. Complexity
   1. Tractability/Intractability
   2. Nondeterministic polynomial
   3. NP-complete
   4. Space complexity
6. Interactivity
   1. Effects of interaction
   2. Formal models of interaction

Textbook

• Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey D. 2001. Introduction to Automata Theory, Languages, and Computation, 2nd ed. Addison-Wesley. ISBN: 0-201-44124-1. [required (but listen to what the instructor will say about how we will use the textbook); available in the TCNJ bookstore; also available as 3-hour reserve in the library]

Schedule: Class meetings: Tue/Fri 4:00-5:20 p.m. in HH126

• The schedule is tentative and subject to change. Please always refer to the on-line syllabus, which contains the latest information.
• Course materials will be linked to the text in blue in the on-line syllabus.