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 semester
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 semester
Course syllabus
1- Basic concepts
Problem and algorithm concepts; analysis of algorithms, complexity in space, complexity in time, asymptotic notations, analysis of the complexity of algorithms; recurrence equations
2- Sorting algorithms
The sorting problem; sorting algorithms: insertion sort, selection sort, merge sort, heap sort, quick sort; linear time sorting
3- Elementary data structures
Stack, queues, lists: definitions and operations, implementation via arrays and pointers; dictionaries and hash tables
4- Trees
Definition of tree, main operations on trees, implementation of trees; binary search trees: definition, representation, operations; balanced trees: Red Black trees, B-trees
5- Graphs
Definition of graph, representation of graphs; visit in width and depth, concept of connected component; minimum cost spanning tree; problem of minimum length path
6- Algorithm design techniques [overview]
Examples of greedy algorithms and dynamic programming algorithms
Problem and algorithm concepts; analysis of algorithms, complexity in space, complexity in time, asymptotic notations, analysis of the complexity of algorithms; recurrence equations
2- Sorting algorithms
The sorting problem; sorting algorithms: insertion sort, selection sort, merge sort, heap sort, quick sort; linear time sorting
3- Elementary data structures
Stack, queues, lists: definitions and operations, implementation via arrays and pointers; dictionaries and hash tables
4- Trees
Definition of tree, main operations on trees, implementation of trees; binary search trees: definition, representation, operations; balanced trees: Red Black trees, B-trees
5- Graphs
Definition of graph, representation of graphs; visit in width and depth, concept of connected component; minimum cost spanning tree; problem of minimum length path
6- Algorithm design techniques [overview]
Examples of greedy algorithms and dynamic programming algorithms
Prerequisites for admission
Knowledge of the fundamental concepts and constructs of imperative programming is required.
Knowledge of the main mathematical functions and the main asymptotic notations is required.
The passing of the "Programmazione" exam is preparatory to the teaching of Algorithms and Data Structures. It's strongly recommended that you pass the "Matematica del continuo" exam.
Knowledge of the main mathematical functions and the main asymptotic notations is required.
The passing of the "Programmazione" exam is preparatory to the teaching of Algorithms and Data Structures. It's strongly recommended that you pass the "Matematica del continuo" exam.
Teaching methods
Lectures
Teaching Resources
Testo di riferimento:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 3/ed, 2009
The MIT Press
[ISBN: 9780262033848]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 3/ed, 2009
The MIT Press
[ISBN: 9780262033848]
Assessment methods and Criteria
The exam consists of a written test, which includes open-ended questions and exercises.
The test is aimed at evaluating the understanding and learning of the algorithms and data structures studied in the course. The test also aims to evaluate the ability to choose and use data structures and algorithms studied to solve simple problems. Notes or other material may not be consulted during the test.
The test is aimed at evaluating the understanding and learning of the algorithms and data structures studied in the course. The test also aims to evaluate the ability to choose and use data structures and algorithms studied to solve simple problems. Notes or other material may not be consulted during the test.
Educational website(s)
Professor(s)