Abstract
Discrete probability is not only interesting in itself but also essential for analysis of algorithms. In this short course, you will be introduced to some probability theory topics such as tail inequalities and martingales that are useful for computer science.
Our starting point is the analysis of a simple algorithm for finding the maximum among n elements. Next some entertaining counterintuitive examples are mentioned like nontransitive dice, and games that if played longer do not favor the stronger. Several inequalities, including a recent one by Ross that is stronger than the second moment method, are stated. Finally, it is shown that one can apply martingale tail inequalities to Doob martingales to analyze problems like binpacking.
Information:
Date and Time:  Wednesday, October 22 at 9:0010:30 and 15:3017:00
Thursday, October 23 at 13:3015:00
Wednesday, October 29 at 9:0010:30 and 14:00115:00
Thursday, October 30 at 13:3015:00
 Place:  Niavaran Bldg., Niavaran Square, Tehran, Iran 
