Provide an introduction to topics at the interphase between probability, discrete mathematics, and theoretical computer science, with a focus on the following three topics:
• Randomized algorithms and average-case analysis
• Random graphs and stochastic processes on graphs: random walks and models for the spread of infections/rumors/opinions on social networks
• Optimal stopping times and prophet inequalities, with applications to combinatorial auctions
• Randomized algorithms and average-case analysis
• Random graphs and stochastic processes on graphs: random walks and models for the spread of infections/rumors/opinions on social networks
• Optimal stopping times and prophet inequalities, with applications to combinatorial auctions
Curriculum
teacher profile teaching materials
- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
Programme
Methods:- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
Core Documentation
The lectures will be based primarily on the following books:- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Attendance
Lectures will be held three times a week, two hours each (for a total of 30 lectures). Attendance is not mandatory.Type of evaluation
The oral exam will cover the topics presented in class. teacher profile teaching materials
- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
Programme
Methods:- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
Core Documentation
The lectures will be based primarily on the following books:- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Attendance
Lectures will be held three times a week, two hours each (for a total of 30 lectures). Attendance is not mandatory.Type of evaluation
The oral exam will cover the topics presented in class. teacher profile teaching materials
- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
Programme
Methods:- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
Core Documentation
The lectures will be based primarily on the following books:- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Attendance
Lectures will be held three times a week, two hours each (for a total of 30 lectures). Attendance is not mandatory.Type of evaluation
The oral exam will cover the topics presented in class. teacher profile teaching materials
- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
Programme
Methods:- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
Core Documentation
The lectures will be based primarily on the following books:- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Attendance
Lectures will be held three times a week, two hours each (for a total of 30 lectures). Attendance is not mandatory.Type of evaluation
The oral exam will cover the topics presented in class.