| Instructor: |
Valentino Crespi, ET-A318, 3-4596.
vcrespi@calstatela.edu
Office Hours: MW 1:00-2:00pm, T 12:30-2:30pm.
|
| cs312 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS512/cs512.html |
| Prerequisites: |
MATH208, MATH248, CS203, CS312 |
| Schedule: |
MW 10:50-12:30PM ET-A220 |
| Abstract: |
CS512 is our graduate course on Algorithms. The focus will be on
advanced methods for the design and analysis of efficient computer
algorithms. These will include, as time permits, randomization and
approximation techniques.
Students are invited also to check the material covered in CS312 and review their background
accordingly. |
| Topics Overview: |
- Review on the foundations (Part I).
- Advanced Data Structures
- Fast Fourier Transform (Chapter 30)
- Dynamic Programming (Chapter 15).
- Greedy Algorithms (Chapter 16).
- Graph Algorithms (Chapters 24 and 25)
- Linear Programming (Chapter 29).
- NP-completeness (Chapter 34)
- Approximation Algorithms (Chapter 35)
- Randomized Algorithms (Notes from the instructor)
|
| Course Book: |
Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms (2nd edition). MIT Press and
McGraw Hill, 2001. |
| Grading: | One Midterm Exam (25%), One
class Project (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, June, 6, 2005. Time: 10:45-1:15pm. |
| 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 unless stated otherwise in class). 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 CS512 (e.g. Subject: CS512 ...).
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.
|