ALGORITHMIC TECHNIQUES FOR AI, GAMES AND NETWORKS

The course presents a variety of algorithmic approaches to computational problems inherent in modern digital systems. This includes real-world computational problems that occur in the context of networks such as social networks and street networks. We then turn to algorithmic techniques for games, i.e., computational settings characterized by multiple players with possibly diverging incentives. We then introduce algorithmic techniques that are at the basis of some modern machine learning approaches, such as the multiplicative weights update routine. By covering these methods, the course examines the fundamental algorithms underlying many of today's important digital infrastructures. This course takes a mathematically rigorous approach, we present algorithmic techniques, then prove their correctness, and formally analyze their performance.

Knowledge and understanding
The student:
- knows the algorithmic techniques used in modern computational systems;
- knows the techniques of proving the correctness of these algorithmic approaches;
- knows the techniques for evaluating their performance, scalability, and reliability


Ability to apply knowledge and understanding
The student:
- is able to design and develop algorithms for computational problems arising in modern computational environments;
- is able to analyze the developed algorithms in terms of correctness and scalability;
- is able to read scientific literature on related topics and to grasp the presented techniques.

Evaluation skills:
At the end of the course the student will be able to use the knowledge acquired to:
- Identify algorithms best suited to solve given problems in the context of networks, AI, and games
- Rigorously prove statements about an algorithm's behavior (most importantly correctness)
- Rigorously analyze performance of algorithms (runtime, approximation, probability of success in case of randomized algorithms)

We recommend a solid proficiency in the following prerequisites:
- Algorithms and data structures (topics covered in CT0667)
- Probability theory (topics covered in CT0675)
- Discrete mathematics (topics covered in CT0434)

+ Random Processes on Networks
- Information Diffusion in Networks
- Concentration Bounds
- Random Walks, Cover time

+ Algorithms for Specific Real-World Graphs
- Social Networks (Betweenness Centrality, Triangle Counting and Clustering Coefficients)
- Shortest Paths in Street Graphs (transit nodes, highway dimension)
- Congestion Games

+ Network Flows
- Max Flow (Ford Fulkerson) and Min Cut (Karger)
- Min-Cost Flow (negative cost cycle)

+ Online Selection Problems
- Secretary Problems
- Yao's Principle

+ Multiplicative Weights Framework
- Prediction with Expert Advice
- Solving Zero-Sum Games
- Boosting

+ Learning
- sample complexity
- VC dimension and PAC learning

- lecture notes of the teacher
- original research articles provided during the course

The exam consists of two parts, both mandatory. In order to pass the course it is necessary to pass both parts (>=18/30). If this condition is satisfied, the final grade is the average of the two grades obtained in the two parts (rounded up).

1. Written exam. The written exam will consist of both multiple choice and open questions that verify that the student acquired the knowledge presented in the course. During the course, exercises of similar flavor will be handed out on a regular basis.

2. Oral exam. The oral exam must be taken after the delivery of the written exam and can be taken only if the written exam was passed with at least 18/30. The exam starts with a brief and simple screening test (multiple short questions, around 10 minutes) designed to verify foundational knowledge of the course material. Thereafter the student will present one course topic of his choice in depth (around 20 minutes) at the blackboard (possibly interrupted or followed by questions regarding the presentation).

written and oral

The instructor is responsible for ensuring the authenticity and originality of all examinations and coursework. In cases of suspected academic misconduct, an additional on-site assessment may be required during the exams, which may differ from the standard format.

28-30L: the student masters the topics presented in the course;
he is capable to think algorithmically and to reason formally about correctness and performance guarantees of algorithms;
his exposition is very clear and scholarly

26-27: the student has a good knowledge of the topics presented in the course;
he generally succeeds to think algorithmically and to reason formally about correctness and performance guarantees of algorithms;
his exposition is very clear

24-25: the student does not thoroughly know all topics presented in the course;
he mostly succeeds to think algorithmically and to reason formally about correctness and performance guarantees of algorithms;
his exposition is clear

22-23: the student has a mostly superficial knowledge of the topics presented in the course;
he usually succeeds to think algorithmically and to reason formally about correctness and performance guarantees of algorithms;
his exposition is not always clear

18-21: the student has a very superficial knowledge of the topics presented in the course;
he has problems to think algorithmically and to reason formally about correctness and performance guarantees of algorithms;
his exposition is confused

Course organized in lectures in class, and exercises on paper.

The course will be held in English.