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