v2.8.0 (4329)

Enseignement de Master - CSC7341 : Algorithm Analysis and ComputationalComplexity


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

Diplôme(s) concerné(s)

Parcours de rattachement

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

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