Date  Topics  Notes 
#1 10/09 
Pawel Wocjan Game Tree Evaluation Analysis of a randomized algorithm for evaluating binary uniform ANDOR 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 ELYaniv 
#4 10/30 
Stephen Fulwider Introduction to Online Algorithms Randomized online paging algorithms 
Chapter 4 in Online Computation and Competitive Analysis by Borodin and ELYaniv 
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 Online 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 11/e for this problem. 