Algorithms and data structure

Course objectives

General objectives: Knowledge of the fundamental algorithms and data structures. Ability to both implement them in a modern programming language (Java or C) and to make design choices to solve real problems in application domains. Knowledge of aspects related to the computational cost of algorithms. Ability tto design algorithms for the solution of new problems, using or modifying algorithms and data structures seen during lessons. Specific objectives: Ability to: - design/implement algorithmic solutions based on known techniques or simple variants; - to approximately evaluate the computational resources necessary for an algorithmic solution; - make informed design choices for problem solving. Knowledge and understanding: Knowing the fundamental data structures and algorithms. Understanding the concepts of correctness and computational cost of an algorithm. Knowing the main paradigms for designing algorithms. Apply knowledge and understanding: Being able to design an algorithm that solves a problem and implement it in modern programming language. Critical and judgment skills: Being able to assess the correctness, adequacy and efficiency of the algorithmic solution of a problem. Communication skills: Being able to effectively describe the requirements of a problem and provide to third parties the relative specifications, design choices and the reasons underlying these choices. Learning ability: The course will allow the development of skills for the independent study of topics related to the course. It will also allow the student to easily consult advanced and/or specific manuals for autonomous learning of ad-hoc algorithmic solutions.

Channel 1
SILVIA BONOMI Lecturers' profile
FABRIZIO D'AMORE Lecturers' profile
Channel 2
LUCA BECCHETTI Lecturers' profile

Program - Frequency - Exams

Course program
1. Recursion 2. Introduction: uniform cost model and its limits 2.1. Cost models for algorithm analysis: uniform cost model 2.2. Worst-case and asymptotic analysis 3. Sorting and Selection 3.1. Introduzione della tecnica divide-and-conquer 3.2. Merge-Sort and Quick-Sort 3.3. Sorting: lower bounds 3.4. Linear sorting algorithms: Bucket Sort e Radix Sort 3.5. The Selection problem. Linear time sorting algorithms 4. Algorithm design: basic techniques 4.1. Greedy algorithms 4.2. Divide and Conquer 4.3. Dynamic programming 5. Data structures 5.1. Priority queues and heaps 5.2. Maps 5.3. Hash functions and hash tables 5.4. Sorted maps: binary search trees 6. Directed and undirected graphs: representation and algorithms 6.1. Algorithms for graph visit 6.2. Connected components and other application of depth and breadth visit algorithms 6.3. Shortest paths: problems and algorithms 6.4. Minimum spanning trees: problem and algorithms 6.5. Union Find 7. String algorithms 7.1. Pattern matching: Boyer-Moore and Knuth-Morris-Pratt's algorithm 7.2. Compression and Huffman'a algorithm 7.3. DNA sequencing 8. Randomization 8.1. Quicksort and Quickselect 8.2. Primality test 8.3. Efficient randomized algorithms for primality test
Prerequisites
Knowledge of basic mathematical notions and calculus, corresponding to the topics of an introductory course in Calculus Knowledge of key notions from probability theory, corresponding to the topics covered by an introductory course in Probability Basic programming skills, knowledge of elementary data structures and ability to implement them, corresponding to an introductory course in Programming and elementary data structures
Books
- Adopted textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduzione agli Algoritmi e Strutture Dati - IV edizione. McGraw Hill, Milano, Italia, 2023. - Suggested as an alternative textbook (in English): Tim Roughgarden. Algorithms Illuminated - Omnibus Edition. Soundlikeyourself Publishing LLC, New York, NY, 2022.
Exam mode
- Practical test on algorithm and data structure design and implementation on a computer - Written exam on course's topics
Lesson mode
Lectures will be held in presence. Part of the lectures will be applied, with the students involved, together with the instructor, in implementing notions and concepts introduced in the course
GIUSEPPE ANTONIO DI LUNA Lecturers' profile
  • Lesson code10616536
  • Academic year2025/2026
  • CourseComputer and Control Engineering
  • CurriculumAutomatica
  • Year2nd year
  • Semester2nd semester
  • SSDING-INF/05
  • CFU9
  • Subject areaIngegneria informatica