Introduce the student to the fundamental concepts of efficient algorithm design, beginning with computational complexity, and the design of optimized data structures for solving specific problems.

Knowledge and understanding: be familiar with the main algorithms and data structures and the main techniques of algorithm design.

Ability to apply knowledge and understanding: be able to identify the 'best algorithm among those studied and possibly design efficient variants of them to solve computational problems. Being able to evaluate the complexity of an algorithm.

Judgment skills: be able to formalize a computational problem adequately and identify the algorithmic methodologies necessary for its solution.

Communication skills: be able to clearly explain the logic and operation of an algorithm, and also describe its operation using pseudocode

Learning skills: ability to learn new algorithmic techniques and data structures beyond those seen in class, motivated by specific problems to be solved.

Knowledge and understanding: to know the main algorithms and data structures and the main algorithm design techniques.

Ability to apply knowledge and understanding: to be able to identify the best algorithms among those studied and possibly design efficient variants to solve computational problems.

Communication skills: being able to clearly explain the logic and functioning of an algorithm, and to describe its functioning also by means of pseudocode

Learning skills: ability to learn new algorithmic techniques and new data structures in addition to those seen in class, motivated by specific problems to be solved.

Programming in Python, notions of analysis (series, integrals, successions), notions of probability (random variables, expected value).

Introduction to algorithm and data structure design, with focus on applications in data science and artificial intelligence. Sorting and search algorithms, fundamental data structures, binary trees, hash tables, algorithms on graphs.

Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to algorithms and data structures, 4th Edition, 2022.

Throughout the course: complexity analysis of iterative and recursive algorithms and techniques for designing efficient algorithms (complexity analysis, recursion, use of data structures, randomization, amortized analysis).


Sorting algorithms: insertion sort, merge sort, heap sort, quicksort

Selection algorithms: selection sort and bisection.

Fundamental data structures: Stacks, Queues, Lists, Heap.

Binary search trees: basic operations, rotations, AVL trees, (RB tree, B tree, Kd tree).

Hash tables

Cushioned analysis

Algorithms on graphs: visiting in breadth and depth, topological sorting, Tarjan algorithm strongly connected components, Bellman Ford and Dijkstra algorithm for minimal paths.

Dynamic programming: longest common subsequence, Floyd-Varshall algorithm.

The course will be conducted with a predominant part of lectures where the lecturer will introduce the fundamental concepts. These activities will be accompanied by classroom exercises in which typical exercises will be solved. Finally, exercises will be handed out for homework during individual study.

The examination will be written and oral. The written exam is compulsory and usually consists of a series of elementary multiple-choice barrier questions (the wrong answer of which precludes passing the exam) and some exercises, typically four, of the types seen in class. Each exercise is worth a certain number of points, clearly indicated in each paper, the sum of which is normally 30. A minimum of 18/30 is required to pass the written exam. The oral examination is optional depending on the score obtained, and usually allows a variation of ±5 points. The oral is mandatory for those who scored at least 28/30 in the written exam. The oral will consist of questions on theory or understanding of the topics covered. In addition to the written exam, there can be two intermediate tests. In case, if both are passed, the average grade earned counts as the grade on the written exam, and thus exempts the student from taking it. It will always be possible for a student to take the written exam to improve the grade.