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 2022
Offered
2024/25
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.
Condividi su