Insegnamento a.a. 2024-2025

Recap of the basics
– Mathematical induction
– Asymptotic notation
– Sorting and searching algorithms
– Fundamental data structures: arrays, lists, stacks, queues
– Graph traversal algorithms: BFS, DFS, Dijkstra

Binary search trees and tournament trees

Graph algorithms
– Modelling computational problems using graphs
– Shortest paths
– Strong connectivity and biconnectivity
– Network flows and matchings

Algorithm design techniques
– Dynamic programming
– Greedy algorithms, and analysing their correctness
– Divide-and-conquer, analysing complexity of recursive algorithms

Hardness of computational problems
– NP-completenes, reductions, the P-vs-NP problem
– Fine-grained complexity lower bounds

Disclaimer: This is a tentative list of topics. It is subject to change depending on the group's background, level, and interests

• describe classic algorithms and data structures;
• estimate running time of algorithms using the big-O notation;
• illustrate algorithm design techniques with specific examples of algorithms;
• select the most efficient data structure for a given task;
• define basic concepts from computational complexity;
• identify sources of hardness of computational problems.
   

• analyse correctness and efficiency of algorithms;
• implement algorithms covered in class;
• model problems stated in natural language as formal computational problems;
• propose and analyse solutions to those problems;
• test, debug, and optimize implementations of algorithms.

• Lectures
• Practical Exercises
• Individual works / Assignments
• Interaction/Gamification

Homework exercises will involve designing and analysing algorithms for posted problems. For some of them, you will present your solutions oraly in class, for others you will write them down and get feedback on your writing.

There will be also individual programming assignments that involve implementing algorithms learned in class. You will submit your programs via an online system that will provide you with live feedback.
 

There will be no midterm. The single final exam will not distinguish between attending and non-attending students. However, throughout the semester you will have opportunities to collect points for assignments and active participation, and some of those opportunities might be available only if you are present in class. Collecting points is not mandatory. Each point guaranteess one percent of the final grade and decreases the contribution of the final exam by one percent. For instance, if you collect 40 points during the semester, your final grade (on the scale from 0 to 100) will be calculated as 40 + 0.6 * [exam-result].

The exam and assignments will test your understanding of basic concepts presented in class, and your ability to apply those concepts to new problems, explain and implement proposed solutions, and analyse their correctness and efficiency.

The main textbook for the course is:

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3rd edition.

It contains a very formal exposition of almost all the material we are going to cover during the course, and much much more. You are going to get references to relevant fragments in the 3rd edition, but if you happen to have access to any other edition, feel free to use it instead (and just keep in mind that chapters and sections may have different numbers).

Other textbooks -- which cover many of these topics and present them in a different style that some of you may prefer -- include:

• S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, Algorithms, McGraw-Hill, 2008.
• J. Erickson. Algorithms. 2019. URL: http://jeffe.cs.illinois.edu/teaching/algorithms/

Additional materials – e.g., research papers, technical reports, notes – will be posted on Blackboard throughout the semester.