MA5011 - Complexity

Objectives

General objective:

Understand and be able to compute the complexity of sequential algorithms.
Recognize combinatorial problems and be able to prove their hardness.
Apprehend cryptographic systems.

Detailed objectives:

Understand the different notions of the complexity of an algorithm and be able to analyze non-recursive
and recursive sequential algorithms.
Understand the complexity of decision problems and the underlying non-deterministic Turing machine
computation model.
Master Turing reduction between problems and classes P, NP and NPC.
Recognize and prove the NP completeness or hardness of combinatorial optimization problems.
Understand how complex problems can be used to create asymmetric cryptosystems.

Hours

• Lecture : 20h

Form of assessment

Total assessment hours: 3