ALGORITHMS AND DATA STRUCTURES - PART 1
|Academic year||2018/2019 Syllabus of previous years|
|Official course title||ALGORITMI E STRUTTURE DATI - MOD.1|
|Course code||CT0371 (AF:248803 AR:136463)|
|Modality||On campus classes|
|ECTS credits||6 out of 12 of ALGORITHMS AND DATA STRUCTURES|
|Degree level||Bachelor's Degree Programme|
|Educational sector code||INF/01|
|Moodle||Go to Moodle page|
- knowledge and understanding of the fundamental algorithms and data structures;
- understanding and evaluation of the complexity of computational problems and the ability to select appropriate methods for modeling and solving them;
Ability to apply knowledge and understanding:
- logical-deductive and problem-solving skills;
- ability to formalize and implement solutions for real problems and identification of appropriate solution patterns.
- being able to formulate and argue solutions, also developing a critical approach to the evaluation of alternative solutions.
Fundamental techniques for algorithm design: Divide-and-conquer. Dynamic programming. Greedy algorithms.
Graph algorithms: Graph representations. Breadth-first and depth-first search. Minimum spanning trees (Kruskal, Prim). Shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall).
NP-complete problems: complexity classes P and NP. Polynomial reducibility and NP-completeness. Examples of NP-complete problems.
Introduction to algorithms (3rd Edition), MIT Press, 2009.
C. Demetrescu, I. Finocchi, G. F. Italiano.
Algoritmi e strutture dati (seconda edizione), McGraw-Hill, 2008.
During the written test is not allowed the use of books, notes, electronic media.
During the oral exam, the student must demonstrate to manage the topics presented in class and be able to expose them in a formal way.
The students are assigned exercises in C. The purpose is to implement data structures, design techniques and algorithms presented in class and do exercise on the calculation of complexity. Making such exercises allows to get a bonus.