11929 - Algorithms and Data Structures (CL.B)

Learning outcomes

Upon completion of the course, the student knows:

- algorithms for solving basic computational problems on elementary data structures;

- basic techniques for calculating the computational cost of algorithms;

- the P, NP, and NP-hard computational complexity classes.

In particular, the student is able to:

- design efficient algorithms for solving simple computational problems;

- estimate in order of magnitude the computational cost of algorithms;

- analyze the computational complexity of basic computational problems;

- assess the efficiency and correctness of an algorithm;

- design and develop a solution for basic computational problems.

Course contents

basic notion of discrete mathematics for analyzing order of magnitude - Sorting - Median and selection - Elementary data structures: stacks, queues, graphs - Search algorithms on graphs - basic algorithms on graphs - Classes P and NP - NP hard Problems

Readings/Bibliography

T. Cormen, C. Leiserson, R. Rivest. Introduction to algorithms. MIT Press.

Teaching methods

Lectures in class

 

Assessment methods

Additional optional written and oral examination. Project.

The examination consists of two tests, project and written (optional oral). The project must be handed in and approved before the written test and does not contribute to the final grade but only qualifies for entry to the written test.

Class attendance is highly recommended but not mandatory.

The written test, lasting 1.5 h, consists of three exercises, a multiple-choice quiz and a theoretical question referring to the verification of knowledge (knowing) and an exercise referring to skills (knowing how to do), declined in the framework "knowledge and skills to be achieved."

Tools such as calculation aids, vocabularies, codes, etc. are not allowed during the tests.

Teaching tools

Lecture notes and handouts.

Office hours

See the website of Vittorio Maniezzo

See the website of Moreno Marzolla