ALGORITHM DESIGN

Course objectives

The objective of the course is introduce the fundamental concepts of algorithms design for polynomial time and hard computational problems. The course will present the basic concepts of algorithm design for network flow and matching problems. General techniques such as greedy and dynamic programming will be applied to problems like shortest paths, spanning tree, knapsack, scheduling. Approximation algorithms will be presented for hard computational problems like TSP, vertex cover, set cover, sat, scheduling. Special emphasis will be given to methods based on Linear Programming and randomized algorithms. Finally, the course will introduce the major computational problems in game theory.

Channel 1
STEFANO LEONARDI Lecturers' profile

Program - Frequency - Exams

Course program
1 Lecture Overview of Algorithm Analysis Kleinberg and Tardos, Ch. 2.1 - 2.4 2 Lecture Stable Matching Kleinberg and Tardos, Ch. 1.1, 1.2 3 Lecture Network Flow: Ford and Fulkerson, Capacity Scaling, Shortest Augmenting Paths Kleinberg and Tardos, Ch. 7.1, 7.2, 7.3 4 Lecture Perfect Matching, Circulations, Improved algorithm for bipartite matching (Ascending Price Matching, Hopcroft-Karp) Kleinberg and Tardos, Ch. 1.1, 7.5, 7.7 5 Lecture Greedy Algorithms 6 Lecture Dynamic Programming Kleinberg and Tardos, Ch. 4.1, 4.4, 6.1, 6.2, 6.4, 6.4, 6.8 slides 7 Lecture Basics of complexity and NP-completeness 8 Lecture 8 Basics of approximation algorithms Reference [4], Chapters 1 and 3 slides 9 Lecture Basics of approximation algorithms Reference [4], Chapters 2.1, 8.1, 8.2 slides 10 Lecture Linear Programming based approximation algorithms Reference [4], Chapters 12 11 Lecture Basics of Randomized Algorithms Reference [5], Chapter 5 12 Lecture Introduction to Game Theory and Equilibria Computation Lecture Notes 13 Lecture Computing Equilibria in Zero-Sum Games and Efficiency of Equilibria Lecture Notes 14 Lecture Selfish Routing and Price of Anarchy See Lecture Notes of Lecture 14 and Exercises, Section 2
Prerequisites
A basic class on algorithms and a basic class on programming
Books
[1] J. Kleinberg and E. Tardos, Algorithm Design. Addison Wesley, Pearson Education, 2005. Additional material on the book can be found here: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/
Frequency
In person
Exam mode
There are two possibilities for passing the exam: 1) The first and most advised one is to submit the two Homeworks before deadline. The homeworks will be discussed during the exam. 2) The second one is to answer two questions on the topics of the first homework (Fundamental design methods and Poly-time algorithms) and three questions on the topics of the second homework (Approximation of hard problems and Computational game theory) during in the written exam. The student that either fails or does not submit the only first/second homework will answer only two/three questions in the written exam.
Lesson mode
Theory lectures and Exercises
  • Lesson code1044417
  • Academic year2025/2026
  • CourseEngineering in Computer Science and Artificial Intelligence
  • CurriculumSingle curriculum
  • Year1st year
  • Semester2nd semester
  • SSDING-INF/05
  • CFU6