Computer Science 789 Online Algorithms

Fall 1999 A Short Quiz

November 23, 1999.

  1. Short questions.
    1. Give a definition of . Please give a definition, and not examples.

      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."
  2. Let P be any metrical task system, and let C be the deterministic competitiveness of P. Suppose that A is a barely random online algorithm for P. Let CA be the competitiveness of A. Prove that
  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