Report tasks for Design and Analysis on Information Systems.

Select two problems and answer them. Email the report to tokuyama@dais.is.tohoku.ac.jp  by February 8.


1.  Give a competitive ratio better than 2 for the ski rental problem by using a randomized algorithm.

2.  Describe the analysis of the online learning algorithm using randomized weighted majority (it was skipped in the lecture).
Reference: N. Littlestone and M.K. Warmuth, The Weighted Majority Algorithms.  Information and Computation 108, pp.212-261, 1994.

3. Give an improved analysis of the "red-black card gambling" if we would like maximize "expected profit" instead of "sure profit (about 90,000 yen)" 
if the next card will be drawn randomly from the deck of the rest of cards.  You may write a computer program for it.

4. Find an algorithmic problem useful in information science, and describe how it contribute to the information society.
If possible, give your own idea (not necessarily theoretical one) to design a better algorithm for it.    

5. Explain about your own research topic in graduate study, and discuss its relation to information science (if any).