Problem Set 0 Solutions ----------------------- Note: the original problem set did not enumerate the sub problems. In the solution set we imagine that they were lettered (a) to (z) by first going right to left and then top to bottom. 1. Once you know that the math symbols respectively denote the floor function, the ceiling function, and absolute value, then it is a simple matter to apply them. (a) 10 (b) 11 (c) 1.1 (d) -1.1 2. (a) 4 (b) 2x We calculate this by removing the log and exponent of the same base, which cancel out. (c) lg(x) This can be directly obtained by using the identities under (2.9) on page 34 of the text. (d) 1 Because by identity, the expressions above and below the line are equivalent. 3. If we look at what we just did under 4.(c), we realize all we need do is use the c expression log(x) / log(2) whenever we want to calulate lg(x). 4. A little analysis shows that we execute line two floor(logn)+1 times. 5. (a) sum(i=1000 to 2000) = sum(i=1 to 2000) - sum(i=1 to 999) = ((2000 * 2001) / 2) - ((999 * 1000) / 2) = 1501500 (b) Consulting formula (3.4) on page 44 of the text, we re-write the summation in closed form and solve: sum(k=0 to infinity) 3^-k = sum(k=0 to infinity) (1/3)^k = 1 / (1 - (1/3)) = 3/2 (c) lg[mult(k=1 to n) 2^k] = lg[2^1 * 2^2 * 2^3 * 2^4 * ... * 2^n] = lg(2^1) + lg(2^2) + lg(2^3) + lg(2^4) + ... + lg(2^n) = 1 + 2 + 3 + 4 + ... + n = (n * (n+1))/2 (d) No, the x was not a typo. We may pull it out along with the n, which is the number of iterations of the inner sum. We then obtain n * x * [(m * (m+1))/2] 6. If you consult chapter 2, which explains asymptotic notation, you can quickly determine that (a), (d), and (e) are true. 7. The easiest way to solve this problem is to note that there are 36 possible die roles (each equally likely) and the determine how many of those rolls satisfy each constraint. (a) Only one possible roll; thus 1/36 is the probability. (b) There are five ways to satisfy this one: (1,5), (2,4), (3,3), (4,2), and (5,1). The answer is then 5/36. 8. a) O(logn) (in general the tree height) b) O(logn) c) O(n) d) O(nlogn) e) O(n) (may have to shift n items) f) O(n+m) if using an adjacency list, O(n^2) with an adj. matrix g) and h) both O(1)