Unit ALGORITHMS AND DATA STRUCTURES
- Course
- Computer science and electronic engineering
- Study-unit Code
- 70A00090
- Curriculum
- Ingegneria informatica
- Teacher
- Emilio Di Giacomo
- Teachers
-
- Emilio Di Giacomo
- Hours
- 81 ore - Emilio Di Giacomo
- CFU
- 9
- Course Regulation
- Coorte 2020
- Offered
- 2022/23
- Learning activities
- Caratterizzante
- Area
- Ingegneria informatica
- Academic discipline
- ING-INF/05
- Type of study-unit
- Obbligatorio (Required)
- Type of learning activities
- Attività formativa monodisciplinare
- Language of instruction
- Italian
- Contents
- + Introduction to algorithms and data structures
+ Sorting
+ Data Structures
+ Advanced Techniques for Algorithm Design
+ Graphs and graph algorithms - Reference texts
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein "Introduzione agli Algoritmi e Strutture Dati", McGraw-Hill
- Educational objectives
- The course objective is to provide to the students basic competences on the design and use of the main data structures, on the design and use of algorithms to solve problems, and on the techniques to evaluate their performances.
At the end of the course the student is expected to have the following knowledges:
- knowledge of the techniques for the complexity analysis of algorithms and problems
- knowledge of some foundamentals data structures (priority queues, search trees, etc.)
- knowledge of some foundamentals computational problems (sorting, minimum spanning tree, shortest paths, etc.)
- knowledge of some techinques for the design of algorithms for optimization problems (dynamic programming, greedy techinques)
At the end of the course the student is expected to have the following abilities:
- ability of establishing the complexity of an algorithm (even a recursive one)
- ability to implement and use the data structures presented in the course
- ability to find efficient algorithmic solutions
- ability to design algorithms for optimization problems using the general techniques presented during the course (dynamic programming, greedy techniques) - Prerequisites
- In order to be able to understand the subjects of the course the student must know the basic concepts of programming. She should be able to write programs to solve simple problems. In particular she must be able to effectively use the recursion. Some mathematical background is also required. The student should be able to understand (and make) mathematical proofs. In particular she should know the mathematical induction and should be able to understand (and make) proofs by induction. Finally, some knowledge of concepts from the Mathematical analysis, such as the concept of function, of limit, of series and of integral.
- Teaching methods
- The course is organized as follows:
1- Lectures (69 hours) during which the various subjects of the course are explained and some excercises are done in order to help the understanding of the explained subjects and as a training for the exam.
2- Practical activity in the computer lab (12 hours). Students, helped by the teacher, write programs on the computer thus applying the concepts that they learned during the lectures. - Other information
- Learning verification modality
- The exam consists of an oral examination and an implementation project. The objective of the oral examination is to evaluate the student's knowledge of the theoretical concepts taught during the course and his/her ability to find algorithmic solutions to solve simple problems.
The project, whose object has to be defined with the teacher, consists of the implementation and experimentation of algorithms and/or data structures. The project can be carried out by a single student or by a group of 2-3 students. - Extended program
- + Introduction to algorithms and data structures
- Introduction to algorithms.
- Complexity Analysis.
- Asymptotic notation.
- Recurrences .
+ Sorting
- Comparison-based sorting algorithms.
- Sorting in linear time.
+ Data Structures
- Elementary Data Structures: Stacks, Queues, Lists, Trees.
- Hashing.
- Binary Serach Trees.
- Red-black trees.
- Priority Queues: Heap.
+ Advanced Tecniques for Algorithm Design
- Dynamic Programming.
- Greedy techniques.
+ Graphs and graph algorithms
- Graphs.
- Graph traversal.
- Topological sort.
- Minimum Spanning tree.
- Single source shortest paths.