| Date | Topics | Notes |
| #1 10/09 |
Pawel Wocjan Game Tree Evaluation Analysis of a randomized algorithm for evaluating binary uniform AND-OR trees |
Section 2.1 in Randomized Algorithms by Motwani and Raghavan |
| #2 10/16 |
Pawel Wocjan The Minimax Principle Game theory; von Neumann's Minimax Theorem; Loomis' Theorem |
Sections 2.1 - 2.2.1 in Randomized Algorithms by Motwani and Raghavan |
| #3 10/23 |
Raymond Yiu Yu Ho Introduction to Online Algorithms Deterministic online paging algorithms |
Chapter 1 & 3 in Online Computation and Competitive Analysis by Borodin and EL-Yaniv |
| #4 10/30 |
Stephen Fulwider Introduction to Online Algorithms Randomized online paging algorithms |
Chapter 4 in Online Computation and Competitive Analysis by Borodin and EL-Yaniv |
| 11/06 |
No Lecture |
|
| #5 11/13 |
Paul Wiegand Introduction to randomized algorithm analysis of evolutionary computation References: |
|
| #6 11/20 |
Paul Wiegand Introduction to randomized algorithm analysis of evolutionary computation |
|
| 11/27 |
No Lecture (Thanksigiving Holidays) |
#7 12/04 |
Pawel Wocjan The Minimax Principle Yao's Minimax Principle; Lower bound on game tree evaluation |
Sections 2.2.2 - 2.2.3 in Randomized Algorithms by Motwani and Raghavan |
| #8 12/11 |
Stephen Fulwider Approximation Algorithms via Linear Programming Relaxation |
|
| #9 12/18 |
Pawel Wocjan | Raymond Yiu Yu Ho Presentation of the article AdWords and Generalized On-line Matching Abstract: How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1-1/e for this problem. |