Problem 1 (Scott) --------- Answer ------ Guess T(n)=x^n => x^2 - (5/2)x + 1 = 0 => roots x1 = 1/2, x2 = 2 => T(n) = A ((1/2)^n) + B (2^n) satisfies T(n) = (5/2)T(n-1) - T(n-2) for constants A and B. T(0)=1 => A + B = 1. T(1)=4 => (1/2)A + 2B = 4. Solving for A, B gives A = -(4/3), B = 7/3. Therefore, the solution is T(n) = -(4/3) ((1/2)^n) + (7/3) (2^n). Grading Breakdown ----------------- 5 pts correct characteristic equation: x^2 - (5/2)x + 1 = 0 3 pts correct solutions of characteristic equation: x1 = 1/2, x2 = 2 2 pts T(n) = A ((1/2)^n) + B (2^n), correctly substituting computed values for A and B 3 pts correct equations for A,B: A + B = 1, (1/2)A + 2B = 4 2 pts correct solution of previous two equations: A = -(4/3), B = 7/3 Error Codes ----------- L (-3) solved for x1 and x2 incorrectly AB (-2) solved for A and B incorrectly Grading Notes ------------- If you made an error (e.g. wrong values for x1, x2), I graded the rest of the problem as if your numbers/expression were correct. No one was penalized, for example, for incorrect values for A and B if he/she had the wrong roots x1 and x2. Some people discovered that the repeated expansion strategy leads to a mess. A solution that simply wrote out a few iterations of this strategy and stopped or found an incorrect pattern received 0 points. Problem 2 (Scott) --------- (a) Choose 6 positions of the 11 for the 6 G's. The remaining 5 positions hold the A's. The number of ways to do this is 11 choose 6 = 462. (b) Using the logic from (a), the number of ways to fill two of the first three spaces with G's is (3 choose 2). In the remaining 8 spaces, we must arrange the remaining 4 G's and 4 A's. Again using the logic from (a), there are (8 choose 4) ways to fill the last 8 positions. The answer is (3 choose 2) * (8 choose 4) = 3 * 70 = 210. (c) Except for the numbers involved, this question is the same as (b). We must put 4 G's and 2 A's into the first 6 positions and 2 G's and 3 A's into the last 5 positions. The number of ways to do this is (6 choose 4) * (5 choose 2) = 15 * 10 = 150. (d) We want to know the number of orders x1 x2 x3 ... x10 x11 which do NOT have exactly two of the first three places filled with G's and do NOT have exactly two of the last five places filled with G's. Let A1 = { orders such that exactly two of the first three places are G's } A2 = { orders such that exactly two of the last five places are G's } The answer to the question is ans = total # of orders - | A1 union A2 |. Here |S| denotes the size of a set S. Using the Principle of Inclusion/Exclusion and the answers to parts (a), (b), and (c), we have ans = total # of orders - (|A1| + |A2| - | A1 intersect A2 |) = 462 - (210 + 150 - | A1 intersect A2 |). An element in the set (A1 intersect A2) has (i) 2 G's and 1 A in the first 3 positions (ii) 2 G's and 1 A in positions 4,5,6 (iii) 2 G's and 3 A's in the last 5 positions. The number of ways to make such an assignment of G's and A's to slots is | A1 intersect A2 | = (3 choose 2) * (3 choose 2) * (5 choose 2) = 3 * 3 * 10 = 90 Therefore, the answer to our problem is ans = 462 - (210 + 150 - 90) = 192. Grading Breakdown ----------------- (a) 5 pts (b),(c) 5 pts total (d) 5 pts Error Codes ----------- I (-2) Answer to (d) is missing the intersection term. The formula (answer to a) - (answer to b) - (answer to c) received 3 points for part (d). E (-1) An answer was left in an unexpanded form (e.g. (11 choose 5) or a product of integers). Grading Notes ------------- One common mistake that people made was to forget that the G's (and A's) are indistinguishable. A solution to (b) that started "Pick 2 of the 6 Giants fans and 1 of the 5 A's fans ..." is incorrect. Another common mistake is that people forgot about the other part of the order not mentioned in the question (e.g. the last 8 positions in question (b)). In order to receive some partial credit on a question, there had to be something written on the page which made some sort of sense. On parts (b) and (c), partial credit was usually 1 or 2 points (out of 5). Complete, correct logic with an incorrect calculation for one of the terms involved received 4 points. On part (d), I had a breakdown for "common" answers as follows: 5 pts if the answer is completely correct 4 pts if the only error was that | A1 intersect A2 | was calculated incorrectly 3 pts for the answer [answer to (a) - answer to (b) - answer to (c)] 2 pts for an answer which is of the form shown above, but with some strange terms in place of (answer to (b)) and (answer to (c)). 1 pt for computing the size of some subset of the orders that we actually want to count 0 pts nothing written or nothing wriiten that makes any sense The above list is not an exhaustive list of answers given. ------------------------------------------------------- Problem 3 (Jeff) (a), (b) The tree looks something like this: if-match O(n^2) + 2T(n/2) / | asgn match same O(1) | block same / | \ nodes for each of lines 3-10 Important points: line 5 is O(n^2) and lines 6 and 7 are each T(n/2) (c) - (e) The recurrence is: T(1) = O(1) T(n) = O(n^2) + 2T(n/2) By the table on p. 151 FCS, we have c = d = k = 2, so T(n) is O(n^2). Error Codes: ------------ X1: Misread the table on p. 151. (-3) X2: not separating match and block. (-1) note that the match is always executed, the block might not be, although in this case you could prove that if the second pattern is reached it must match. X3: not separating if/else in line (1). (-1) X4: block elements in a line, rather than children of the block. (-2) X5: no if-match. (-1) X6: not giving running times of interior nodes. (-3) X7: T(n-1) instead of T(n/2) for the recursive calls. (-3) ------------------------------------------------------------------- Problem 4 (Jeff) ---------- fun first(One(x)) = x | first(Two(x,_)) = x | first(Three(x,_,_)) = x The type of first is 'a group -> 'a That is, it takes a group with elements of any type 'a and returns an element of that type. Error Codes: ----------- X1: Assuming nil is a value of type 'a group. (-3) X2: Confusing the group datatype with list. (-3) Problem 5: (Tom) --------- Problem #5.a. There are 6 points where the first die is a 1 and 6 points where the first die is a 2. (One point for each of the possible second die values). Thus there are 12 points out of 36 which are in event E, yielding P[E] = 1/3. b. There are 6 events where the sum of the dice is 2, 3 or 4. This occurs with the following rolls: (1,1), (1,2), (2,1), (1,3), (3,1), (2,2). This yields P[F] = 1/6. c. Given that we know there are 6 points in F, we know that the denominator will be 6. How many of these 6 points satisfy the event E? There are 5 cases where the first die is a one or a two and the sum of the two dice is 2, 3 or 4. Thus we determine P[E/F] = 5/6. --------------------------------------------------------------- Problem 6: (Tom) ---------- Problem #6.a. "If n is a power of 2 then forall n >= 1, T(n) <= 2n^2 - n where T(n) = 4T(n/2) + n and T(1) = 1. b. The basis value for n is 1. T(n) = 1 <= 2 (1^2) - 1 = 1. c. Prove the inductive step: S(n/2) \implies S(n). Assume: The induction is true for S(i): i < n. Prove T(n) <= 2n^2 - n for S(n): T(n) = 4T(n/2) + n. Show that this is <= 2n^2 - n. T(n) = 4T(n/2) + n <= 4[2(n/2)^2 - n/2] + n (using the IH). T(n) = 4T(n/2) + n <= 8(n^2/4) - 4n/2 + n. T(n) = 4T(n/2) + n <= 2n^2 - n. T(n) <= 2n^2 - n. Scoring: a. 3 pts b. 4 pts c. 8 pts.