Algorithms and Data Structures
A.Y. 2018/2019
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
Undefined
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
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.
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
Lessons: 72 hours
Professors:
De Capitani Di Vimercati Sabrina, Livraga Giovanni
Professor(s)