Algorithms and Complexity
| Nature | Unknown label |
|---|
| Credit hour | 3 |
|---|---|
| Total number of hours | 20 |
| Number of hours for lectures | 20 |
Prerequisites
Aucun
Goals
Aucun
Content
This course presents some methods to analyzing the complexity of recursive algorithms, improving their running time, and showing the limitation of dynamic programming. We then show the meaning of Non-deterministic Polynomial algorithms (NP) and how to define the difficulty of some decision/search problems. Then assuming P = NP, we emphasize on Blackbox algorithm design. We also focus on communication complexity: deterministic communication protocols and methods to obtain lower bounds.
Additional Information
Aucun