| Instructor: |
Valentino Crespi, ET-A318, 3-4596.
vcrespi@calstatela.edu
Office Hours: TR 6:00-6:30pm
|
| cs512 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS512/Lects/cs512.html |
| Prerequisites: |
CS312 |
| Schedule: |
TR 4:20-6:00pm ET-A332 |
| 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 course logs
of 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)
- Quantum Computing (Notes from the instructor)
|
| Course Book: |
Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms (3rd edition). MIT Press, September 2009. |
| Grading: |
Midterm exam (35%), Final exam (20%), Quizzes (15%), Homework
Assignments/Project (10%), Presentation (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.
|