| cs486 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS486/cs486.html |
| Lectures: |
MW 2:30-4:10PM, ET A210
|
| Final Exam: |
Wednesday, March 14, 1:30-4:00pm, ET A210
|
| Instructor: |
Valentino Crespi
vcrespi@calstatela.edu
(323) 343-4596.
ET-A318
|
| Office Hours: |
MW 6:00-7:00pm, T 4:00-6:00pm, 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: | Michael
Sipser. Introduction to the Theory of Computation, Second edition.
Course Technology, 2005. |
| References: |
- Hartley Rogers, Jr. Theory of Recursive Functions and
Effective Computability. The MIT Press (1987).
- Michael R. Garey, David S. Johnson. Computers and
Intractability: A Guide to the Theory of NP-Completeness.
W.H. Freeman and Company (June 1979).
- Christos Papadimitriou. Computational Complexity. Addison
Wesley; 1ST edition (November 30, 1993).
|
| Topics: |
- Review on Languages and Automata. Pushdown
Automata. Non-context-free languages (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 (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. All parties involved will receive a grade
of F for the course and be reported to the Academic Senate. |
| General Policies:
|
- Makeup Exams: No.
- Homework Assignments:
Homework assignments should be written neatly on standard sized
paper (8.5 x 11 inch), possibly in black or blue ink (please do not
use red) and submitted at the due date (no electronic
submissions accepted). Each page should be numbered. Late
submissions will not be accepted.
- Use of Cell Phones: forbidden.
- Late arrivals:
Students arriving 30min after the beginning of class will not be
admitted.
- 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.
|