Algorithms and Data Structures
A.Y. 2023/2024
Learning objectives
The objective of the course is the introduction of the basic concepts for the design and analysis of algorithms and data structures. The course will illustrate the main data structures and will focus on some specific algorithms, also analyzing their computational complexity.
Expected learning outcomes
The student will know and will be able to use the main data structures and algorithms studied during the course. The student will also be able to propose adequate algorithmic solutions to simple problems, using the most appropriate data structures, and will be able to estimate the computational complexity of the proposed solution.
Lesson period: First four month period
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
First four month period
Course syllabus
1) Introduction. Algorithms and data representation. Computational complexity. Data structures.
2) Specification and creation of lists, stacks and queues.
3) Trees: visit algorithms, implementation. Heap and HeapSort.
4) Graphs: specification, implementation, visit algorithms, connected components.
5) Sets: specification and implementation, Mfset. Dictionaries: specification and implementation, hash tables. Balanced search trees.
6) Complexity of algorithms. Relationships due to the complexity of recursive algorithms.
7) Impact of data structures on the complexity of an algorithm. The problem of minimum paths. General algorithm scheme based on Bellman's theorem. Dijkstra, Johnson, Bellman-Ford-Moore, with stack and Pape-D'Esopo.
8) Divide et impera. Description of the paradigm. Examples: Mergesort, Quicksort.
9) Backtrack. Description of the paradigm. Example: String matching.
10) Dynamic Programming. Description of the paradigm. Example: Approximate string matching.
11) Greedy. Description of the paradigm. Examples: Minimum Cover Tree, Scheduling Schedule.
12) Non determinism and enumeration. Polynomial certificates. Non determinism. Enumeration.
13) NP-complete problems. Classes P and NP. Polynomial reducibility.
2) Specification and creation of lists, stacks and queues.
3) Trees: visit algorithms, implementation. Heap and HeapSort.
4) Graphs: specification, implementation, visit algorithms, connected components.
5) Sets: specification and implementation, Mfset. Dictionaries: specification and implementation, hash tables. Balanced search trees.
6) Complexity of algorithms. Relationships due to the complexity of recursive algorithms.
7) Impact of data structures on the complexity of an algorithm. The problem of minimum paths. General algorithm scheme based on Bellman's theorem. Dijkstra, Johnson, Bellman-Ford-Moore, with stack and Pape-D'Esopo.
8) Divide et impera. Description of the paradigm. Examples: Mergesort, Quicksort.
9) Backtrack. Description of the paradigm. Example: String matching.
10) Dynamic Programming. Description of the paradigm. Example: Approximate string matching.
11) Greedy. Description of the paradigm. Examples: Minimum Cover Tree, Scheduling Schedule.
12) Non determinism and enumeration. Polynomial certificates. Non determinism. Enumeration.
13) NP-complete problems. Classes P and NP. Polynomial reducibility.
Prerequisites for admission
It is compulsory to pass the exam of Computer Programming and it is recommended pass the exam of Continuum mathematics and Discrete mathematics
Teaching methods
Recorded lessons
Teaching Resources
A. Bertossi, "Algoritmi e Strutture Dati", UTET, 2000.
Material available on the e-learning platform.
Material available on the e-learning platform.
Assessment methods and Criteria
The exam consists of a written test that includes both theoretical questions and exercises. The written test, lasting two and a half hours, aims to verify the preparation and understanding of the subject. The evaluation, expressed in thirtieths, will take into account the correctness, completeness and clarity of the answers to the theoretical questions and the ability to reason and use the knowledge acquired for solving the exercises. The exam is closed book.
As per organization of the online learning mode, the exam can be split in two parts each covering part of the course. If the student passes both parts, the average of the two results corresponds to the final exam mark. The exam of each part is passed if a score greater than or equal to 15 is reached, while the average of the two parts must be greater than or equal to 18 to pass the exam. The results of the written tests will be communicated through the publication of a pdf file on the Ariel website of the course.
As per organization of the online learning mode, the exam can be split in two parts each covering part of the course. If the student passes both parts, the average of the two results corresponds to the final exam mark. The exam of each part is passed if a score greater than or equal to 15 is reached, while the average of the two parts must be greater than or equal to 18 to pass the exam. The results of the written tests will be communicated through the publication of a pdf file on the Ariel website of the course.
INF/01 - INFORMATICS - University credits: 12
Lessons: 96 hours
Professor:
De Capitani Di Vimercati Sabrina
Professor(s)