### CS4123 Theory of Computation  Syllabus - B 2004

#### PROF. CAROLINA RUIZ

WARNING: Small changes to this syllabus may be made during the course of the term.

#### COURSE DESCRIPTION:

Building on the theoretical foundations from CS 3133, this course addresses the fundamental question of what it means to be "computable," including different characterization of computable sets and functions. Topics include the halting problem, the Church-Turing thesis, primitive recursive functions, recursive sets, recursively enumerable sets, NP-completeness, and reducibilities.

```

```

#### Course Goals:

The goal of CS4123 is to provide the students with knowledge and techniques that will allow them to determine whether a given problem is or is not solvable with a computer (decidable vs. undecidable problems), and if it is solvable with a computer, whether or not it can be solved within a "reasonable" amount of time (tractable vs. intractable problems).

#### Course Outcomes:

During the course of the term the students will learn the necessary knowledge and will gain the necessary first hand experience to:
• Understand the difference between decidable and undecidable problems
• Classify a given formal description of a problem as either decidable or undecidable
• Design Turing Machines to solve problems
• Understand Church-Turing Thesis
• Understand the difference between tractable and intractable problems
• Classify a given formal description of a decidable problem as either tractable or intractable
• Apply Reducibility techniques to classify problems
• Analyze the time complexity of a given problem
• Classify a given decidable problem as belonging to P, NP, NP-complete, or exponential time complexity classes

#### "IDEA Form" Objectives:

The following idea form objectives are relevant for this course:
• Gaining Factual Knowledge, including basic terminology for decidability and undecidability, mechanisms to define computation, and classification of computational problems into decidable, tractable, intractable, and undecidable.

• Learning fundamental principles, generalizations, or theories including approaches to to determine if a given computational problem is decidable or not, approaches to to determine if a given decidable problem is tractable or not, and reducibility techniques to classify a computational problem based on the classification of related computational problems.

• Learning to apply course material to determine and rigorously prove the classification (decidable, tractable, intractable, and undecidable) of real-world computational problems.

• Developing creative capacities to devise approaches to rigorously classify computational problems.

#### CLASS MEETING:

Mo, Tu, Th, Fr 12:00 - 12:50 p.m.
Classroom: HL154

```

```

#### PROFESSOR:

Prof. Carolina Ruiz
Office: FL 232
Phone Number: (508) 831-5640
Office Hours:
 Mo. 1:00 - 2:00 pm Th. 2:00 - 3:00 pm, or by appointment

#### TEACHING ASSISTANT:

Adam Zellers Office Hours: Fuller Labs A22
 Mondays 10:00 - 11:00 am Thursdays 6:00 - 7:00 pm Fridays 9:00 - 10:00 am

#### SENIOR ASSISTANT:

Piotr Mardziel
Office Hours: Fuller Labs A22
 Tuesdays 4:00 - 5:00 pm Wednesday 3:00 - 4:00 pm

#### RECOMMENDED BACKGROUND:

CS 3133 Foundations of Computer Science.

 Exam 1 25% Exam 2 25% Quiz 1 10% Quiz 2 10% Homework 30% Class Participation Extra Points

You may discuss the homework with your classmates if you wish, but you must develop and write your own solutions. Your solutions must be your own original work. However, if for some reason you use any other sources of ideas, including for instance books, web pages, etc., you must explicitly acknowledge those sources. Failure to identify non-original work is considered academic dishonesty. Collaboration or other outside assistance on exams is not allowed.

#### EXAMS

There will be a total of 2 exams. Each exam will cover the material presented in class since the beginning of the term. In particular, the final exam is cumulative. Both exams will be in-class, closed-book, individual exams, unless otherwise noted.

#### HOMEWORK

A total of four homework assignments will be given during the term. Solutions to the homework will be made available soon after homework is collected so no late homework will be accepted. Homework in this class is individual. You may discuss the homework with your classmates if you wish, but you must develop and write your own solutions.

According to the WPI Undergraduate Catalog, "Unless otherwise indicated, WPI courses usually carry credit of 1/3 unit. This level of activity suggests at least 17 hours of work per week, including class and laboratory time." Hence, you are expected to spend at least 13 hours of work per week on this course outside the classroom.

#### QUIZZES

Two major quizzes will be given during the term. One between the beginning of the term and Exam 1, and one between the Exam 1 and Exam 2. These quizzes will be based on the homework assignments and the material covered in class, and will serve as preparation for the Exams.

Also, other smaller, pop quizzes may be given during the term. Be prepared!

#### CLASS PARTICIPATION

Students are expected to attend class and to read the material assigned to each class in advance. Class participation will add extra points to students' grades.

#### CLASS MAILING LIST

The mailing lists for this class are: cs4123-all ~~AT~~ cs.wpi.edu and cs4123-staff ~~AT~~ cs.wpi.edu
• Messages sent to cs4123-all ~~AT~~ cs.wpi.edu reach the entire class, and
• Messages sent to cs4123-staff ~~AT~~ cs.wpi.edu reach the professor, the TA, and the SA only.
There is also a myWPI forum for this class.

This course may be taken for graduate credit by students in the BS/MS CS program. Written permission from the professor is required. In order to receive graduate credit, students who have signed up for this program need to solve and turn in solutions to additional, higher level problems included in each of the course's homework assignments.

#### CLASS WEB PAGES

The web pages for this class are located at: http://www.cs.wpi.edu/~cs4123/b04/
Announcements will be posted on the web pages and/or the class mailing list, and so you are urged to check your email and the class web pages frequently.

The following additional references complement and/or supplement the material contained in the required textbook (listed in alphabetical order).

1. G.S. Boolos and R. C. Jeffrey. "Computability and Logic." 3rd Edition. Cambridge University Press. 1989.

2. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. "Introduction to Algorithms". McGraw-Hill. 1989.

3. M.R. Garey and D.S. Johnson. "Computers and Intractability: A Guide to the Theory of NP-Completeness". W.H. Freeman. 1979.

4. R. Greenlaw and H.J. Hoover. "Fundamentals of the Theory of Computation. Principles and Practice." Morgan Kaufmann. 1998.

5. H. Hamburger and D. Richards. "Logic and Language Models for Computer Science." Prentice Hall. 2002.

6. J.E. Hopcroft, R. Motwani, and J.D. Ullman. "Introduction to Automata Theory, Languages, and Computation". 2nd Edition. Addison Wesley. 2001.

7. E. Kinber and C. Smith. "Theory of Computing. A Gentle Introduction." Prentice Hall. 2001.

8. H.R. Lewis and C.H. Papadimitriou. "Elements of the Theory of Computation". 2nd edition. Prentice Hall. 1998.

9. P. Linz "Introduction to Formal Languages and Automata." 3rd Edition. Jones and Bartlett Publishers. 2000.

10. J. Martin. "Introduction to Languages and the Theory of Computation." 3rd Edition. McGraw Hill. 2003.

11. B.M. Moret. "The Theory of Computation." Addison Wesley. 1998.