| Instructor: |
Valentino Crespi, ET-A318, 3-4596.
vcrespi@calstatela.edu
Office Hours: M 4:45-6:00pm
|
| cs512 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS512/Lects/cs512.html |
| Prerequisites: |
CS312 |
| Schedule: |
M 6:10-10:00PM (with half an hour break) |
| Final Exam Day: |
Monday, December, 7, 2009. Time: 7:30-10:00pm. |
| 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. |
| Course Goals: |
- Learn classical design techniques such as: Greedy, Dynamic
Programming and Divide-and-conquer.
- Learn to analyze the computational complexity of algorithms.
- Understand paradigms of computational hardness.
|
| Topics Overview: |
- Foundations (Part I).
- Fast Fourier Transform (Chapter 30)
- Dynamic Programming (Chapter 15).
- Greedy Algorithms (Chapter 16).
- Advanced Data Structures
- 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: |
The course is structured as a mixture of lectures and student
presentations based on readings. Student presentations will be
graded based on their quality and also on the level of understanding
of the subject being presented. There will be one/two homework
assignments during the course, an in-class midterm examination and a
final class presentation/project due at end of the course. No final
exams.
Paper Presentations (20%), Final class Presentation/Project (20%),
Midterm exam (40%), Homework Assignments (20%).
| Score (%) |
Letter Grade |
|
90-100
|
A
|
|
80-89
|
B
|
|
60-79
|
C
|
|
50-59
|
D
|
|
0-49
|
F
|
|
| Policies:
|
- Makeup Exams: No.
- Use of the Computer: normally forbidden during lecture except
when authorized by the instructor.
- 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.
|