MATH-467 / 5 credits

Teacher: Marcus Adam Wade

Language: English


Summary

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpected (and sometimes paradoxical) properties for which no other methods of construction are known.

Content

Keywords

random variable, expected value, probabilistic method, random graph

Learning Prerequisites

Required courses

Probability theory

Recommended courses

  • Discrete Mathematics or Graph Theory
  • Linear Algebra

Important concepts to start the course

Graph, random variable, expectation, variance, binomial coefficients, asymptotics, eigenvalues

Learning Outcomes

By the end of the course, the student must be able to:

  • Define and explain basic concepts in probability and discrete mathematics
  • Prove explain, and apply the first and second moment methods
  • Prove explain, and apply the Local Lemma
  • Solve exercises, design randomized algorithms
  • Describe and explain the method of interlacing polynomials

Transversal skills

  • Summarize an article or a technical report.
  • Demonstrate the capacity for critical thinking
  • Assess progress against the plan, and adapt the plan as appropriate.

Teaching methods

Lectures and exercises

Expected student activities

Attending the lectures, solving the exercises, reading sections from the textbook

Assessment methods

Exam written

Dans le cas de l'art. 3 al. 5 du Règlement de section, l'enseignant décide de la forme de l'examen qu'il communique aux étudiants concernés.

Resources

Bibliography

Noga Alon-Joel Spencer: The Probabilistic Method (Wiley)

Ressources en bibliothèque

In the programs

  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Probabilistic methods in combinatorics
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks

Reference week

 MoTuWeThFr
8-9     
9-10     
10-11     
11-12     
12-13     
13-14    MED21522
14-15    
15-16    MED21522
16-17    
17-18     
18-19     
19-20     
20-21     
21-22     

Friday, 13h - 15h: Lecture MED21522

Friday, 15h - 17h: Exercise, TP MED21522