| cs486 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS486/cs486.html |
| Lectures: |
MW 11:40-1:20PM, ET A220
|
| Final Exam: |
Monday, March 15, 10:45am - 1:15pm
(See also the official on line schedule of the final exams.)
|
| Instructor: |
Valentino Crespi
vcrespi@calstatela.edu
(323) 343-4596.
ET-A318
|
| Office Hours: |
MW 11:00-11:40am, ET-A318.
|
| Course Description: |
Theory of Computing; nondeterminisms, decidability and
unsolvable problems; NP completeness and intractable
computations. |
| Course Goals: |
At the end of the course, students are able to
- Understand the rigorous notion of algorithm and study the
decidability of computational problems. In particular students will
learn to distinguish between recursive, recursively enumerable and
non recursively enumerable problems.
- Understand the role of nondeterministic computations and
characterize the class of problems NP. In particular students will
learn the concept of NP-completeness and its implications in the P vs
NP question.
|
| Prerequisites: |
CS386 |
| Textbook: | [S] Michael
Sipser. Introduction to the Theory of Computation, Second edition.
Course Technology, 2005. |
| References: |
- [HMU] J.Hopcroft, R.Motwani,J.D.Ullman. Introduction to Automata Theory,
Languages, and Computation. Addison-Wesley, 2001.
- [R] Hartley Rogers, Jr. Theory of Recursive Functions and
Effective Computability. The MIT Press (1987).
- [GJ] Michael R. Garey, David S. Johnson. Computers and
Intractability: A Guide to the Theory of NP-Completeness.
W.H. Freeman and Company (June 1979).
- [P] Christos Papadimitriou. Computational Complexity. Addison
Wesley; 1ST edition (November 30, 1993).
|
| Topics: |
- Review on Languages and Automata (Part I)
- Computability Theory (Part II: chapters 3, 4, 5, 6).
- Complexity Theory (Part III: chapters 7, 8, 9).
- Selected Topics from Chapter 10.
|
| Grading Policy: |
Two Midterm Exams (25%+25%), Final Exam (40%), Homework
Assignments/Quizzes (10%)
| Score (%) |
Letter Grade |
|
90-100
|
A
|
|
80-89
|
B
|
|
60-79
|
C
|
|
50-59
|
D
|
|
0-49
|
F
|
|
| Academic Integrity: | Students are
allowed and encouraged to discuss reading materials with each
other. However, homework assignments must be solved and written
individually. If you obtain a solution with help then you
should acknowledge your source in the paper and then write
independently your own solution.
Cheating will not be tolerated. Cheating on any assignment or
exam will be taken seriously and reported to the chair of the
Department. |
| General Policies:
|
- Makeup Exams: No.
- Homework Assignments:
Late submissions will not be accepted.
- Use of Cell Phones and Computer: forbidden.
- Office:
Students are warmly invited to visit the instructor (during
the announced office hours) for questions and clarifications.
- E-mail:
E-mails addressed to vcrespi@calstatela.edu must have, in the
subject, the keyword CS486 (e.g. Subject: CS486 ...).
All the E-mails will be possibly processed in the evening and so
will be answered with a minimum delay. Be careful, the keyword in
the subject is important for automatic filtering. Wrong subjects may
result in the accidental loss of the message.
|