Algorithms and Data Structures Ii
A.Y. 2024/2025
Learning objectives
Algorithm design and analysis is a fundamental part of computer science. This course introduces students to advanced techniques for the design and analysis of algorithms, and explores a variety of applications. We will focus on three main themes: computational complexity, randomized algorithms, games and markets.
Expected learning outcomes
Upon completion of the course, students will be able to: (1) describe the main complexity classes of decision problems and prove some of their properties; (2) describe and analyze various randomized algorithms; (3) understand some of the main ideas in game theory and their application to online auctions and digital markets. These objectives will be assessed via an oral discussion whose evaluation will determine the final grade.
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Course syllabus
1. Computational complexity
- Polynomial reducibility between decision problems
- The classes P and NP
- NP-complete problems
2. Randomized algorithms
- Montecarlo and Las Vegas algorithms
- The probabilistic complexity classes
- The von Neumann extractor
- The coupon collector problem
- Reservoir sampling
- Karger's algorithm for MinCut
- Hedge e Exp3 algorithms for sequential decisions
3. Hashing and randomization
- Universal hashing
- Approximate counting: Count-Min Sketch
- Random projections
4. Clustering and randomization
- Correlation clustering
- K-Means++
5. Games, auctions, and markets
- Von Neumann's minimax theorem
- Auctions
- Matching markets
- Polynomial reducibility between decision problems
- The classes P and NP
- NP-complete problems
2. Randomized algorithms
- Montecarlo and Las Vegas algorithms
- The probabilistic complexity classes
- The von Neumann extractor
- The coupon collector problem
- Reservoir sampling
- Karger's algorithm for MinCut
- Hedge e Exp3 algorithms for sequential decisions
3. Hashing and randomization
- Universal hashing
- Approximate counting: Count-Min Sketch
- Random projections
4. Clustering and randomization
- Correlation clustering
- K-Means++
5. Games, auctions, and markets
- Von Neumann's minimax theorem
- Auctions
- Matching markets
Prerequisites for admission
Before attending this course, students are strongly advised to pass the following exams: Calculus, Discrete mathematics, Algorithms and data structures.
Teaching methods
Lecture-style instruction. Attendance: optional.
Teaching Resources
The main reference material are the lecture notes available through the portal ariel.unimi.it/
Assessment methods and Criteria
The method of assessment is oral exam.
The final score, on a scale of thirty points, takes into account the knowledge of the subject, the clarity of exposition, and the language skills.
The final score, on a scale of thirty points, takes into account the knowledge of the subject, the clarity of exposition, and the language skills.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Cesa Bianchi Nicolo' Antonio
Shifts:
Turno
Professor:
Cesa Bianchi Nicolo' AntonioProfessor(s)