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)
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.