| Instructor: |
Valentino Crespi, ET-A138, 3-4596.
vcrespi@calstatela.edu
Office Hours: M 1:30-2:30pm, T 11:30-12:30, W 12:20-2:20pm
|
| cs486 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS486/cs486.html |
| Prerequisites: |
CS386 |
| Schedule: |
MW 2:30-4:10PM ET-A220 |
| Abstract: |
CS486 deals with Calculability and Intractability. This class is
theoretical in character and aims at providing a nontrivial
understanding of the power of computers from the point of view of
which kind of problems cannot be solved through computing
devices. It is the natural followup of CS386 (see archive) and so it will include
some elements of Automata Theory. Then it will focus on Turing
Machines and on the Theory of NP-completeness. |
| Topics Overview (cp. 7-11): |
- Review on Languages and Automata.
- Turing Machines.
- Undecidability.
- Intractability: the classes P and
NP. NP-completeness. Cook's Theorem.
|
| Course Book: | J. Hopcroft, R. Motwani,
J. Ullman. Introduction Automata Theory, Languages and
Computation. Addison-Wesley. |
| Recommended Books: | Michael R. Garey,
David S. Johnson. Computers and Intractability. W.H. Freeman
and Company. |
| Grading: |
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
|
|
| Date and Time of Final Exam: |
Monday, March 15, 2004. Time: 1:30-4:00pm. |
| 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.
- Academic integrity and honesty:
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.
- 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.
|