Algorithms and data structures

A.Y. 2018/2019
Overall hours
Learning objectives
Il corso ha lo scopo di introdurre i concetti fondamentali riguardanti l'analisi ed il progetto di algoritmi e strutture dati e l'analisi della complessità computazionale degli algoritmi.
Expected learning outcomes
Course syllabus and organization

Single session

Lesson period
First semester
Course syllabus
1. Introduction
Basic concepts. Analysis of algorithms, space and time complexity of recursive and non-recursive algorithms. Asymptotic notations.

2. Abstract data types
Lists, Stack, Code: definition and operations. Implementation (arrays, pointers) and advantages / disadvantages.

3. Trees
Basic concepts and definitions. Visiting techniques (inorder, preorder, postorder). Search, insert, and delete operations. Implementation techniques. Binary search trees: definition, representation, operations. Red-black binary trees: definition, representation, operations.

4. Sets
Definition, operations and representation techniques. Dictionaries: definition and operations. Priority codes: concepts, examples of use and implementation techniques. Heap: realization and execution of operations.

5. Hashing
Direct hashing. Hash functions. Collisions.

6. Advanced design techniques.
Dynamic programming. Greedy algorithms.

7. Graphs.
Oriented and non-oriented graphs: definitions and basic concepts. Implementation techniques. Minimum path in weighted graphs: problem and solutions. Visiting algorithms (BFS and DFS). Examples of DFS and BFS applications. Graph matching.

8. Sorting
Problem. Insertion sort, heapsort, quicksort, mergesort: description and analysis of complexity.

9. Management of data on external memory
Problems. B-trees: definition, properties and advantages. Execution of search, insertion and deletion operations. Merge and split operations.
INF/01 - INFORMATICS - University credits: 12
Laboratories: 48 hours
Lessons: 72 hours