CS 591: Assignments

Homework

• Homework #1 (Due Thursday, September 16)
  Problems 3.3, 3.4, 3.12 in the text. In 3.4, set up the recurrence, but do not attempt to solve it -- instead, use the fact that we "know" the solution (we want to show the loglogn bound), postulate the answer, and verify that it satisfies the recurrence.
  Solution
  
• Homework #2 (Due Thursday, September 23)
  Problems 4.2 and 4.8 in the text.
  Solution
  
• Homework #3 (Due Thursday, October 7 -- 2 weeks)
  Problems 5.3, 5.5 in the text. In addition, also solve the following problem.
  Recall that K_n denotes the complete (undirected) graph on n nodes, i.e., the graph with n nodes and all possible (n choose 2) edges. Consider coloring the edges of K_n from a set of two colors, say red and blue. Thus each edge is assigned a single color; note that this is not what is termed a coloring of the graph (where coincident edges must have distinct colors). We are interested in the largest complete subgraph of K_n that is entirely red or entirely blue. Prove that there exists a red-blue coloring of K_n that does not induce a complete subgraph K_k that is entirely red nor one that is entirely blue whenever we have
  (n choose k) 2^{1-(k choose 2)} < 1.
  Prove it by showing that the event [no blue K_k and no red K_k] has non-zero probability. Next (as an exercise in asymptotics), find the largest n (as a function of k) for which the inequality above holds.
  Solution
  
• Homework #4 (Due Wednesday, October 13, 5pm)
  Problems 6.8 and 7.6 in the text; 7.6 has a typo: the field should be Z_p, not Z₂.
  Solution
  
• Homework #5 (Due Tuesday, October 26)
  Problems 7.12 and 8.10. (Note that the expressions defining the O( ) classes in Problem 8.10 are not unique; you may end up with slightly different, yet equivalent expressions.)
  Solution
  
• Homework #6 (Due Thursday, November 4)
  Problem 9.4 in the text, plus solve the following problems.
  Interpolation search (sometimes called dictionary search) attempts to use additional information about the key space to speed up searches. Let us assume that the dictionary distribution and the universe distribution are very similar; further, let us assume that the keys we are dealing with are simply integer values, so that we can perform arithmetic on them. Then, when given some key x and searching for it in the dictionary in interval [low,high] (those are indices), rather than checking (as in binary search) position (low+high)/2, we shall instead check position low-1+ceiling((high-low+1){x-key(low) / key(high)-key(low)})
  Prove that the average behavior of interpolation search (under uniform distribution) is O(loglog n)$with high variance -- prove that the worst case is of order n.
  Solution
  
• Homework #7 (Due Thursday, November 18)
  Problems 10.13, 10.14 (a), and 11.1 in the text.
  Solution
  
• Homework #8 (Due Tuesday, November 30)
  Problems 12.6, 12.7, and 12.12 in the text. In 12.12, replace the last question (can it be derandomized) by the question "This algorithm is easier to implement than the algorithm presented in the text; why?"
  Solution
  
• Homework #9 (Last homework, due Thursday, December 9; but can be turned in as late as December 18, 1999)
  Three problems:

  A. Verify that the competitive analysis of the simple randomized paging algorithm falls apart if the adversary is adaptive and offline: show where the proof fails and give a sequence of requests that increases the ratio as much as possible.

  B. Consider the following modification to the BIT algorithm for list maintenance: only complement the bit when the item is not at the head of the list. Show that the resulting algorithm is no longer 7/4-competitive.

  C. Define the following on-line game: the player receives, one at a time, a succession of values; at step i, the player must decide whether to choose value v_i or to move to the next step. Once the player has accepted value v_i, that value is the player's earning. If the player refuses to pick any value, then the player's earning at the end of the game is simply the lowest value encountered in the game, or the last value, or some fixed lower bound on values (depending on the game's details). (An interesting elaboration, known as one-way trading, has the player convert an initial stake in some currency, say dollars, to another currency, say pounds; at step i, the value v_i is the exchange rate and the player decides what fraction of his/her remaining dollar funds to convert to pounds at that step.)
  Assume that all values are drawn from the real interval [low,high] and define r to be the ratio high/low and assume, for simplicity, that r is a power of 2. Define a trivial deterministic algorithm RPP_i ("reservation price policy") that simply accepts the first value greater than low*2ⁱ, for some 1<=i<=log r. The randomized algorithm EXP chooses, with equal probability, a value of i in the set {1,2,...,log r} and runs algorithm RPP_i.
  Prove that the competitive ratio of EXP against an offline (non-adaptive!) adversary is O(log r), while its competitive ratio against an offline adaptive adversary is O(r/log r) (expected ratio) or O(\sqrt(r) log r) (ratio of expected payoffs).
  Further prove that, even if neither low nor high are known, but r is known, the same bound (for a nonadaptive adversary) holds -- EXP now picks the first value v₁ to serve in lieu of low, but its payoff is defined slightly differently: if it does not select anything, it can use v₁ as its payoff.
  In contrast, prove that, when only r is known, no deterministic algorithm can have a competitive ratio better than r -- that is, knowledge of r alone does not help at all in a deterministic context.

  Solution