v2.10.0 (4913)

Enseignement de Master - CSC7341 : Algorithm Analysis et Computation Complexity


Computer Science does not live without algorithms, and furthermore, ‘good’ algorithms, and thus, their analysis is crucial. The successful students after this class should understand why big industrial players now put a lot of efforts into the algorithm analysis and should be able to perform such analysis by themselves.
In the context of the CSN program we will tackle the network related classical and non-classical problems in computer communications and will study how to perform their analysis.
The main objective of the course is therefore the study of the design and analysis of algorithms, including the proofs of their correctness and their complexity estimation.
Lecturers: Drs. Natalia Kushik and Jorge López (TSP)

21 heures en présentiel

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Computer Science for Networks

Le rattrapage est autorisé (Max entre les deux notes)
  • le rattrapage est obligatoire si :
    Note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS

La note obtenue rentre dans le calcul de votre GPA.

La note obtenue est classante.

L'UE est évaluée par les étudiants.

Programme détaillé

Turing Machines. Computability. Decision problems. Decidable and undecidable problems. The Halting Problem (Lecture and exercises).
Algorithm and Problem Complexity. Complexity classes. Time and Space Complexity. Hardness and completeness of (decision) problems (Lecture and exercises).
SAT-problem (Lecture and exercises).
Algorithm analysis for “very known” problems (e.g., sorting) – where to start and how to proceed.
Hamiltonian path, Hamiltonian cycle problems, Clique problem (Lecture and exercises).
Data structures as a complexity reduction strategy.
Greedy algorithms as tempting ideas: how often do they lies and what is the price?
Algorithms and their analysis in related fields of Communication Networks:
– Complexity issues in information security (Lecture, discussion and students’ presentations) – background for the guaranteed secrecy.
– Complexity issues in software testing (Lecture, discussion and students’ presentations) – background for software certification.

Discussions and debates on open (Millennium) problems:
i) P =? NP.
ii) Alternative complexity definitions?
iii) Improving the performance of an implementation? ‘Classical’ compiler optimizations and beyond that; from high to low level programming languages?

Individual laboratories on the listed subjects will be performed. The algorithm analysis will be supported by the experimental evaluation of software quality parameters, such as performance, disc load, energy consumption, etc.

The evaluation includes a 3 hour written exam (1/2 of the final grade).
The class also contains the continuous evaluation represented as homework, laboratories and students’ presentations (1/2 of the final grade).

Veuillez patienter