Algorithms and Data Structures Ii
A.Y. 2020/2021
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 cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
In case the Covid emergency prevents lectures from being given in class, these will be delivered live via the Zoom platform according to the regular schedule. Each live lecture will be video recorded and immediately made available to all students via a link. The teaching modality (in class vs. online) and the instructions for attending classes will be advertised on the course web page (see the Reference Materials section).
The syllabus and the reference material will not change.
The methods of assessment and the evaluation criteria will not change. However, oral exams may take place via Zoom depending on the rules being enforced at the time of the exam session.
The syllabus and the reference material will not change.
The methods of assessment and the evaluation criteria will not change. However, oral exams may take place via Zoom depending on the rules being enforced at the time of the exam session.
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 take the following exams: Calculus, Discrete mathematics, Algorithms and data structures.
Teaching methods
Lectures.
Teaching Resources
The main reference material are the lecture notes available through the portal ariel.unimi.it/
Additional references:
- Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson International Edition, 2006.
- David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010
Additional references:
- Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson International Edition, 2006.
- David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010
Assessment methods and Criteria
L'esame consiste di una prova orale relativa agli argomenti trattati nell'insegnamento.
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 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.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Cesa Bianchi Nicolo' Antonio
Professor(s)