Student's Portal

Exposition of Probabilistic Methods in Combinatorial Proofs and Their Algorithmic Applications. The Basic Method - Bays Law and Union Bound. Linearity of Expectation - Basic Use and Random Structures With Alterations. The Isolating Lemma. Concentration Methods - The Second Moment, Large Deviation Inequalities and Martingales. The Local Lemma. Correlation Inequalities. The Entropy Methods- Basic Equations and Applications. Introduction Random Walks. Learing Outcomes# By The End of The Course The Student# 1. Will Possess Knowledge Of Probabilistic Methods in Algorithmic Analysis and Combinatorics, Including Proving and Applying The Needed Theorems. 2. Will Acquire Knowlege and Practice of Solving Problems That Occur Naturally In Computer Science Theory.

Faculty: Computer Science
|Undergraduate Studies |Graduate Studies

Pre-required courses

(94412 - Probability (advanced) and 234247 - Algorithms 1) or (94412 - Probability (advanced) and 104291 - Combinatorial Algorithms) or (104222 - Probability Theory and 234247 - Algorithms 1) or (104222 - Probability Theory and 104291 - Combinatorial Algorithms)

Course with no extra credit

97329 - Probablistic Algorithms

• Elements of information theory - Cover, Thomas M.
• Elements of information theory - Cover, Thomas M.
• Elements of information theory [electronic resource] - Cover, Thomas M.
• Elements of information theory / [electronic resource] - Cover, T. M.,
• Elements of information theory [electronic resource] - Cover, T. M.,
• Probability and computing : randomized algorithms and probabilistic analysis - Mitzenmacher, Michael
• Randomized algorithms - Motwani, Rajeev.
• The probabilistic method - Alon, Noga
• The probabilistic method - Alon, Noga
• The probabilistic method [electronic resource] - Alon, Noga.