To show the organization of the course that includes this module, follow this link Course organization
In this course students will learn how to use a computer for solving real life problems via the design of suitable algorithms. Possible solutions are compared in terms of their efficiency. To this purpose the course includes the study of the mathematical methods for the analysis and the evaluation of the various algorithms. Abstract mathematical stuctures are used to represent the concrete data of a given problem; they play a fundamental role in the encoding of the concrete setting in the virtual world of computers.
-Computational problems: indecidability, tractability, computational model and computational complexity.
- Analysis of algorithms and the asynthotic notation.
-Arrays and lists: binary search, recursion, linked lists.
-Trees: recursive algorithms on binary trees, insertion and deletion, breadth-first visit and tree representations.
-Dictionaries: binary search trees, AVL trees.
-Dynamic Programming and Greedy Algorithms.
-Graphs: problems on graphs, graph representations, shortest paths.
-Stacks and queues: implementation, breadth-first and depth-first search.
-Priority queues: heaps, implementation, building and sorting a heap.
-NP-completeness: Polynomial time, NP-completeness and reducibility, NP-complete problems.
Author | Title | Publisher | Year | ISBN | Note |
T. Cormen, C. Leiserson, R. Rivest, C. Stein | Introduzione agli Algoritmi e Strutture Dati (Edizione 2) | McGraw-Hill | 2005 | 88-386-6251-7 | |
Crescenzi, P. - Gambosi, G. - Grossi, R. | Strutture di Dati e Algoritmi | Pearson Education Italia | 2006 | 8871922735 |
Written test divided in two parts: Teoria and Laboratorio. The duration of the test is 3 hours: 2 hours for the theory part and 1 hour for the practical part. Candidates must score at least 18/30 for each part of the test. The overall final score is calculated as the weighted sum of the two individual scores with weights 4/5 for the theory part and 1/5 for the practical part.
******** CSS e script comuni siti DOL - frase 9957 ********p>