Computer Science 789 Online Algorithms

Fall 1999 A Short Quiz

November 23, 1999.

  1. Short questions.
    1. Give a definition of expected value. Please give a definition, and not examples. You may assume that there are only a finite number of possible values.

      I require a "minimal" answer. That is, if your answer mentions anything not necessary to answer this question, such as "game," "online algorithm," etc., I will take off points. The answer should be about one line long.

    2. Write the negation of the statement below, without using the word "not," the word "no," or any symbol that means "not," "not equal to," or "not a member of."

      There exists a number n in the set X such that for any number i in the set Y, i > n or i2 < n.

  2. Let P be any metrical task system, and let C be the competitiveness of P. Suppose that A is a barely random online algorithm for P, which is a probability distribution on n deterministic algorithms A1, ... An, and let CA be the competitiveness of A.
    Prove that CA >= (C+n-1)/n.
    Let pi be the probability that A chooses to be Ai. Since _____ , There must be some i for which pi >= 1/n.
  3. Consider the metrical task system, similar to the buzzer problem defined below.
    1. Draw the offset function game graph. You may ignore nodes that you can prove are useless. (Hint: there are only N offset functions, and only N nodes in the game graph if useless nodes are eliminated.)
    2. Prove matching upper and lower bounds on the competitiveness of this problem.
    3. Prove that the randomized competitiveness of this metrical task system is N against an oblivious adversary.

Back to Course Page

Back to Assignment Page