Computer Science 280: Homework 6

Homework 6:
3/12/08 (due 3/26/08) Read 4.5-4.7, 4.10 

Section   Number    Points    Comments 
4.3        35(b),(d) 4        DAM2: 4.8, 3(b),(d)
           36        2        DAM2: 4.8, 6
4.5        2 	     6        DAM2: same problem - Do this and the other 
                              two problems in this section both algebraically 
                              and combinatorially 
	   4         6 	      DAM2: same problem
	   6 	     6	      DAM2: same problem
4.6 	   2(a)      3 	      DAM2: same problem; use the binomial theorem (don't just use a calculator!)
	   6 	     4 	      DAM2: same problem; don't forget to say how it's relevant to the previous problem
	   8 	     3        DAM2: same problem
4.7 	   4 	     3        DAM2: same problem
           8         3        DAM2: same problem; assume u >= b.  Hint: there's an easy answer.
	   9 	     3        DAM2: same problem
           15(b)     3        DAM2: same problem; you must model this as a balls and urns problem
4.10 	   2 	     3        DAM2: same problem
	   8 	     3 	      DAM2: same problem. Warning: this problem is hard (although it has a short proof)
Extra problem (due to Jon Kleinberg:) [4 points] In a distributed computer system, there can be many computer programs executing concurrently on many different processors. In such a setting, it is often very hard to reason about the behavior of the system as a whole, since the output of all these programs may be interleaved in complicated and unpredictable ways. Here's a simple example to illustrate some of the difficulties that can arise. Systems that maintain airline seat reservations for a large commercial air carrier tend to be highly distributed -- some passengers are making reservations for themselves over the Internet; others are talking with ticket agents over the phone; and still others are purchasing tickets from independent ticket agents. Now, suppose you're talking to a ticket agent over the phone, and they say, ``Good news -- I got you the last seat on that flight." It's natural to worry, given the fact that ticket purchases are going on simultaneously world-wide, that someone else is having a conversation with their ticket agent, thinking that they too got this last seat on the same ight. Building systems where such things can't happen (e.g. where two users can't grab the same copy of a limited resource) is a core concern in distributed systems. Rather than delve into these issues in their full generality, let's consider a very specific combinatorial problem that arises in reasoning about the interleaved executions of multiple programs.

Suppose we have two programs, executing on different machines, and each issues a sequence of requests to a central server. The first program issues m requests in sequence, labeled r1, r2, ... rm, and the second program issues n requests in sequence, labeled s1, s2, ... sn. (For example, these could be requests to purchase seats on flights, being made to a central airline database.) Now, a scheduler at the server takes these two incoming streams and interleaves them to produce a single combined stream in which all the requests appear. We say that the combined stream is a valid interleaving of the two streams if the requests from the first program appear in the correct order relative to each other, and the requests from the second program appear in the correct order relative to each other (but we impose no requirement on how the requests from the first program appear relative to the requests from the second program). How many distinct valid interleavings are possible, given that the two programs are issuing m and n requests respectively? Write a formula for this quantity as a function of m and n, and give an explanation for why your formula is correct.

Example: If m = 2 and n = 1, then r1; r2; s1 and r1; s1; r2 would be two different valid interleavings. On the other hand, the sequence r2; s1; r1 would not be a valid interleaving, since r2 and r1 appear in the wrong order relative to each other.