Algorithms and Complexity

Course objectives

The training objectives of the course are mainly two. The first is to provide an introduction to the design and analysis of algorithms resting on a solid conceptual and mathematical basis. The second is to provide an introduction to the fundamental phenomenon known as the computational complexity of algorithmic problems. Concerning the first objective, an introduction to the main design techniques will be provided through a series of notable algorithmic problems. For the second, the main focus will be on the notions of undecidability and NP-completeness.

Channel 1
ALESSANDRO PANCONESI Lecturers' profile
FLAVIO CHIERICHETTI Lecturers' profile

Program - Frequency - Exams

Course program
Dynamic Programming: Segmented Least Squares, Bellman-Ford Data Structures: Union find; hash tables Greedy: Huffman codes Divide-et-Impera: integer multiplication Introduction to approximation algorithms and to online learning ("expert problems") Introduction to computability and complexity: Turing machines; undecidability; reductions; NP-completeness
Prerequisites
No formal prerequisites
Books
"Algorithm Design", Kleinberg, Tardos Learning material provided by the instructor
Frequency
Attendance is not mandatory, but it is strongly recommended.
Exam mode
Written exam
Bibliography
"Algorithm Design", Kleinberg, Tardos "Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein "Automata and computatability", Kozen
Lesson mode
Lectures will be given on a blackboard and/or with slides.
  • Lesson code10603315
  • Academic year2025/2026
  • CourseMathematical Sciences for Artificial Intelligence
  • CurriculumSingle curriculum
  • Year2nd year
  • Semester1st semester
  • SSDINF/01
  • CFU6
  • Subject areaAttività formative affini o integrative