ALGORITHMS AND DATA STRUCTURES
ALGORITMI E STRUTTURE DATI
| A.Y. | Credits |
|---|---|
| 2023/2024 | 9 |
| Lecturer | Office hours for students | |
|---|---|---|
| Valerio Freschi | Tuesday 11.00 - 13.00 or on demand |
| Teaching in foreign languages |
|---|
|
Course with optional materials in a foreign language
English
This course is entirely taught in Italian. Study materials can be provided in the foreign language and the final exam can be taken in the foreign language. |
Assigned to the Degree Course
| Date | Time | Classroom / Location |
|---|
| Date | Time | Classroom / Location |
|---|
Learning Objectives
The aim of the course is to illustrate the main techniques for algorithms design and to describe and analyze the most known basic algorithms together with respective used data structures, with particular focus on computational complexity facets.
Program
01. Introduction to algorithms and data structures:
01.01 Algorithms and their typologies
01.02 Correctness of an algorithm with respect to a problem
01.03 Complexity of an algorithm with respect to resource usage
01.04 Data structures and their typologies
02. Classes of problems:
02.01 Decidable and undecidable problems
02.02 Tractable and intractable problems
02.03 Cook theorem
02.04 NP-completeness
03. Complexity of the algorithms:
03.01 Notations to express the asymptotic complexity
03.02 Computing the complexity of non-recursive algorithms
03.03 Computing the complexity of recursive algorithms
04. Array algorithms:
04.01 Arrays: basic definitions and classical problems
04.02 Traversal algorithm for arrays
04.03 Linear search algorithm for arrays
04.04 Binary search algorithm for sorted arrays
04.05 Comparison criteria for sorting algorithms for arrays
04.06 Insertsort
04.07 Selectsort
04.08 Bubblesort
04.09 Mergesort
04.10 Quicksort
04.11 Heapsort
05. List algorithms:
05.01 Lists: basic definitions and classical problems
05.02 Traversal, search, insertion and removal algorithms for lists
05.03 Insertion and removal algorithms for queues
05.04 Insertion and removal algorithms for stacks
06. Tree algorithms:
06.01 Trees: basic definitions and classical problems
06.02 Traversal and search algorithms for binary trees
06.03 Search, insertion and removal algorithms for binary search trees
06.04 Balancing criteria for binary search trees
07. Hash tables:
07.01 Dictionaries, associative arrays, maps: basic functions and implementation through arrays, lists, trees
07.02 Direct access tables
07.03 Hash functions
07.04 Collision resolution: collision lists, open addressing
08. Graph algorithms:
08.01 Graphs: basic definitions and classical problems
08.02 Traversal and search algorithms for graphs
08.03 Topological sorting algorithm for direct acyclic graphs
08.04 Properties of the shortest path
08.05 Bellman-Ford algorithm
08.06 Dijkstra algorithm
09. Algorithmic techniques:
09.01 Divide-and-conquer technique
09.02 Dynamic programming
09.03 Greedy technique
09.04 Backtracking technique
10. Laboratory activity:
10.01 C language fundamentals: recall, editing, compilation, debugging
10.02 Algorithms complexity experimental evaluation: timing and counters
10.03 Pseudorandom number generators: rand and srand functions
10.04 Experimental comparison of sorting algorithms for arrays
10.05 Implementation of algorithms for lists
10.06 Implementation of traversal and search algorithms for binary trees
10.07 Implementation of graph algorithms: breadth-first and depth-first traversal algorithms
Bridging Courses
Although there are no mandatory prerequisites for this exam, students are strongly recommended to take it after Procedural Programming and Calculus 1.
It is also worth noticing that the topics covered by this course will be used in Operating Systems, Databases, Object Oriented Programming and Modeling, and Logic and Functional Programming.
Learning Achievements (Dublin Descriptors)
Knowledge and understanding:
At the end of the course, the student will learn: to be aware of the importance of efficient design of algorithms; the fundamental knowledge for analyzing the computational resources required by an algorithm; the main algorithms and data structures for solving basic computational problems.
Applying knowledge and understanding:
The student will learn the methodologies typical of algorithmic design and analysis. In particular she/he will be able to design a series of classic algorithms (sorting, search, etc.) working on different data structures (arrays, lists, trees, graphs) and to analyze their computational complexity. The ability to apply these techniques will be developed and sharpened during laboratory activities, where various algorithms will be analyzed and implementated in C language.
Making judgements:
The student will learn how to apply the algorithmic methodologies to understand and solve new problems of computational nature. Critical discussions during classes and laboratory activities will stimulate and develop the making judgements ability of the student.
Communication skills:
The student will acquire the ability to communicate the fundamental concepts of algorithms and data structures with an appropriate and rigorous terminology. She/he will learn to describe the problems related to the design and analysis of efficient algorithms, and the methodologies adopted to solve them.
Learning skills:
The student will acquire the ability to study and learn algoritmic techniques and fundamental data structures. She/he will learn to recognize the importance of computational resources (in particular space and time) in order to be able to autonomoulsy develop solutions for novel problems related to efficient program design.
Teaching Material
The teaching material prepared by the lecturer in addition to recommended textbooks (such as for instance slides, lecture notes, exercises, bibliography) and communications from the lecturer specific to the course can be found inside the Moodle platform › blended.uniurb.it
Supporting Activities
Multiple choice questions and solved exercises for the self-assessment of the student's preparation available on the Moodle platform for blended learning.
Teaching, Attendance, Course Books and Assessment
- Teaching
Theory lectures and laboratory exercises.
- Attendance
Although recommended, course attendance is not mandatory.
- Course books
Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2023.
(Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2022.)
Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2008.
Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2012.
Sedgewick, "Algoritmi in C", Pearson, 2015.
(Sedgewick, "Algorithms in C", Addison-Wesley, 1998.)
- Assessment
Written exam and oral exam.
This procedure is aimed in particular at evaluating the achievement of applying knowledge and understanding, with respect to problem solving and efficient usage of computational resources and, at the same time, at assessing the student's capabilities of summarizing concepts and her/his communication skills.The written exam (2 hours long) consists of a programming exercise (to be solved at the computer) and of a set of multiple choice questions; it is considered passed if the mark (which is valid only for the exam call in which the written exam is taken) is at least 18/30.
The oral exam, which can be taken only if the written exam has been passed, consists of questions about the course program. If passed, it determines a spread between -5/30 and 5/30 of the previous marks, thus yielding the final mark.
During the period of suspension of the teaching activities envisaged in the academic calendar intermediate tests will take place.
- Disabilità e DSA
Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.
A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.
Additional Information for Non-Attending Students
- Teaching
As for attending students.
- Attendance
As for attending students.
- Course books
As for attending students.
- Assessment
As for attending students.
- Disabilità e DSA
Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.
A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.
| « back | Last update: 06/07/2023 |
