Kirk Pruhs (He's the one on the left)
Email:
kirk@cs.pitt.edu
Phone : 412-624-8844
I will cover the basics of random processes and their analyses that arise frequently in CS related research, e.g.
Course Text
We will rather closely follow selected portions of the excellent text of Upfal and Mitzenmacher.
Course Format
We will cover essentially all of the excellent text of Upfal and Mitzenmacher. I will present all of these lectures. Each student may give one lecture at the end of the term on some paper from the area of random processes. I use the Socratic method, that is, I try to develop the ideas by asking the students leading questions. The grading will be based on a modest amount of daily homework and the final presentation.
Prerequisites
This is definitely not a pure algorithmics course. The graduate algorithms course is not a prerequisite. The prerequisite is familiarity with basic probability, e.g. random variables, expectations, conditional probability, etc., or the willingness to put more time in early in the course to catch up. Markov chains, Poisson processes etc. are widely used in many areas of CS, e.g. to model computing and communication systems. Having the ability to do basic analyses on such random processes will likely be an advantage to many of you in your research careers. So this course is intended for a broad range of students.
Class Time and Location
MW 2:30-3:45 in 5313 Sennott Square
Homework Groups
Schedule
|
Date |
Chapter |
Topic |
Applications |
Homework |
|
Wednesday January 4 |
1 |
Events and Probability |
Verifying matrix multiplication Min-cut |
1.6 (Group B solution) 1.22 (Group A solution) |
|
Monday January 9 |
2, 3 |
Expectations Moments and Deviations
|
Coupon Collector Quicksort |
2.21 (Group A solution) 2.25 (Group B solution) 3.21 (A) 3.22(Group B solution)
|
|
Wednesday January 11 |
3, 4 |
Moments and Deviations Chernoff Bounds |
Searching Permutation Routing on n-Cube |
4.9 (Group B solution) 4.25( Group A solution) |
|
Monday Janurary 16 No Class, Martin Luther King Day |
||||
|
Wednesday January 18 |
5 |
Balls and Bins |
Coupon Collector with Poisson Approximation |
5.10 (Group A solution) 5.11 (Group B solution) |
|
Monday January 23 No Class |
|
|
|
|
|
Wednesday January 25 |
5 |
Random Graphs |
Hamiltonian Cycle |
5.18 (Group B solution) 5.22 (Group A solution) |
|
Friday January 27 Special Class10:30am - SENSQ 5317 Distinguished Lecture by Sanjeev Arora
|
|
|
|
|
|
Monday January 28 |
6 |
Probabilistic Method |
|
6.2 (Group B solution) 6.8 (Group A solution) |
| Wednesday January 30 | 6 | Probabilistic Method |
6.14 (Group A solution) 6.16 (Group B solution) |
|
| Monday February 6 | 6 | Probabilistic Method | ||
| Wednesday February 8 | 7 |
Markov Chains Random Walks |
7.18 (Group A solution) 7.22 (B) |
|
| Monday February 13 | 7 |
Random Walks Relationship to Electrical Networks |
||
| Wednesday February 15 | 8 | Poisson Processes |
8.8(Group A solution) 8.10(Group A solution) 8.13(B) 8.23(B) |
|
| Monday February 20 | 8 | Queuing Theory | M|M|1 and M|M|Infinity Queues | |
| Wednesday February 22 | 9 | Entropy |
9.12 (Group B
solution) 9.16 (A) |
|
| Monday February 27 | No Class | No Class | No Class | |
| Wednesday March 1 | 10 | Monte Carlo Methods | ||
| Monday March 13 | 10, 11 | Monte Carlo Methods/Coupling |
10.6 (B) 10.10 (Group A solution) |
|
| Wednesday March 15 | 11 | Coupling |
11.7 (A)
11.16 (B) |
|
| Monday March 20 | 12 | Martingales | ||
| Wednesday March 22 | 12 | Martingales |
12.4 (A) 12.5 (B) 12.10 (B) 12.18 (A) |
|
| Monday March 27 | 13 | Pairwise Independence | ||
| Wednesday March 29 | 13 | Pairwise Independence | ||
| Monday April 3 | 14 | Balanced Allocations | ||
| Wednesday April 5 | 14 | Balanced Allocations | ||
| Monday April 10 | Christine Chung Presentation | |||
| Wednesday April 12 | Mohamed Aly Presentation | |||
| Friday April 14 | Mahmoud Elhaddad Presentation | |||
| Monday April 17 | Ihsan Qazi Presentation | |||
| Wednesday April 19 | Ziuohui Kong Presentation | |||
| Friday April 21 | Jonathan Misurda Presentation | |||
| Monday April 24 | Hammad Iobal Presentation | |||
| Wednesday April 26 | Dan Li Presentation | |||
| Friday April 28 | Make-up Presentation |
Research Papers
At the end of the semester, each student enrolled for a grade will present one paper from the recent theoretical computer science literature. Some possible papers (mostly from SODA 2005, STOC 2005, FOCS 2005, SODA 2006, STOC 2006) are listed below: