CS109A FINAL EXAM SOLUTIONS Note: 1-4 were graded by Scott, 5-9 by Tom, and 10-16 by Jeff. Problem 1 --------- Answers ------- (a) B The truth assignment {q=TRUE,p=TRUE} makes the expression TRUE, while the truth assignment {q=FALSE,p=FALSE} makes the expression FALSE. (b) C In order to make the last two AND terms TRUE, we must assign p=FALSE and q=FALSE. But this assignment makes the first AND term (p+q) FALSE. Therefore there is no truth assignment which makes the expression TRUE. (c) B The truth assignment {q=TRUE,p=TRUE} makes the expression TRUE, while the truth assignment {q=TRUE,p=FALSE} makes the expression FALSE. (d) B The truth assignment {q=TRUE,p=TRUE} makes the expression TRUE, while the truth assignment {q=FALSE,p=TRUE} makes the expression FALSE. Grading ------- Each of the four parts was worth 5 points. No partial credit was given. ------------------------------------------------------------------- Problem 2 --------- Answers ------- (a) Yes; (n0=0,c=4) is a minimal witness pair. (b) Yes; (n0=64,c=216/64=3.375) is a minimal witness pair. This was a difficult problem. The function f(x)=(log_2(x))^3/x is increasing at x < e^3 (e^3 is approximately 20.09) and decreasing at x > e^3. The function f reaches its peak at x=e^3. A minimal witness pair can be obtained by taking n0 to be a power of 2 greater than e^3, with c=(log_2(n0))^3/n0 (as was done in the solution given above). Picking n0 to be a power of 2 less than e^3 does NOT yield a witness pair at all. For example, (n0=16,c=4) is a not a witness pair, although it looks that way if you only look at the values of f at powers of two. Remember that we must have f(n) <= cn for all n>=n0 in order for (n0,c) to be a witness pair. The function f is still increasing at x=16,17, and thus (log_2(17))^3/17 > (log_2(16))^3/16. The right hand side of the inequality is c=4 in the incorrect witness pair (n0=16,c=4). Rearranging this last inequality gives (log_2(17))^3 > c * 17, and this means that (n0=16,c=4) is not a witness pair. The strategy given above leads to many correct minimal witness pairs. Another strategy is to note that the peak value of f is f(e^3). This gives the witness pair (n0=1,c=f(e^3) approx 4.036). (c) Yes; (n0=0,c=1) is a minimal witness pair. Grading ------- Each of the three parts was worth 5 points. Partial credit was given. The following codes were used: X -5 answer "no" X1 -1 answer (n0=1,c=4) for (a) or answer (n0=1,c=1) for (c) X2 -2 answer (n0,c) is a witness pair, but not a minimal one X3 -3 answer "yes" with a pair (n0,c) which is NOT a witness pair ------------------------------------------------------------------- Problem 3 --------- Answers ------- (a) S(n): If L is a list of length n, then sum(L) returns the sum of the elements in L. (b) n=1 (c) If L=[x], then the first pattern matches and sum returns x. Since x is the only element in L, it is indeed the sum of all the elements in L. Therefore sum works correctly on a list of length 1. (d) Our inductive hypothesis is S(n), n >= 1. We need to show that sum(L) returns the sum of the elements in a list L of length n+1. In this case, the second pattern matches (because n+1 >= 2) and x=hd(L), xs=tl(L). Note that the length of xs is n. By the inductive hypothesis, sum(xs) returns the sum of the elements in xs. Clearly, adding x to the sum of the elements in xs gives the sum of the elements in L. This is exactly the value returned in the second line of sum. Therefore sum(L) returns the sum of the elements in L. Grading ------- This question was graded less strictly than the similar "max" question on the first exam. Here are the point breakdowns and error codes that were used. (a) 3 points N -2 didn't mention that n is the length of the list (b) 1 point (c) 3 points FP -2 no indication that the first pattern of sum matches and the only element in the list is returned M -1 no logic/statement that the sum of the elements in a one element list is the single element in the list (d) 8 points SP 2 You need to give some indictation that the second pattern matches in this case. This could have been stated outright or strongly implied by the usage of our variable names (x,xs). IH 4 Statement and proper usage of the inductive hypothesis (including indication of where you used the inductive hypothesis) For each of the codes above, the point value indicates the maximum number of points that were taken off for an error/omission. ------------------------------------------------------------------- Problem 4 --------- Answer ------ fun sets(n,0) = [[]] | sets(0,m) = [] | sets(n,m) = sets(n-1,m) @ appendAll(n,sets(n-1,m-1)); Grading ------- Each of the two base cases were worth 3 points and the recursive part was worth 9 points. The grading of the recursive logic was further divided as follows: 2 points for each of the two recursive calls sets(n-1,m) and sets(n-1,m-1), 3 points for correctly calling appendAll, and 2 points for taking the union with @ (or with a correct helper function "Union" that you supplied). No error codes were used. Problem 5 (graded by Tom): --------- a. T(1) = 1 T(2) = 7 T(3) = 29 T(4) = 103 (2 points) b. There are three common forms for the answer: 9T(n-2) + 3 * 2^(n-1) + 2^n 9T(n-2) + (5/2) * 2^n 9T(n-2) + 5 * 2^(n-1) (4 points) c. There are three common forms for this also: 27T(n-3) + 9 * 2^(n-2) + 3 * 2^(n-1) + 2^n 27T(n-3) + 19 * 2^(n-2) 27T(n-3) + (9/4 + 3/2 + 1) * 2^n Note that the third form makes the series more "visible". (4 points) d. T(n) = 3^i * T(n-i) + Sum(from j=0 to j=i-1) of 3^j * 2^(n-j) (4 points) e. n-1 (2 points) f. 5 * 3^(n-1) - 2^(n+1) (4 points) Scoring: -1 for simple math errors -3 for major errors -3 if you didn't reduce the answer to 'f' to closed form ------------------------------------- Problem 6 (graded by Tom): --------- points answer 1 H(1) = 1 1 H(2) = 1 2 H(3) = 2 2 H(4) = 3 4 H(5) = 8 5 H(6) = 20 -------------------------------------- Problem 7 (graded by Tom): --------- a. 7/15 b. 1/3 c. 2/5 d. 2/7 e. No Scoring: 3 points for each subpart -1 if you didn't reduce 5/15 in 'b' to 1/3 -------------------------------------- Problem 8 (graded by Tom): --------- a. 3^5 = 243 There are 3 colors possible for each of 5 ordered place settings. b. C(5,2) * 2^3 Choose 2 of the 5 places for the blue plate. There are 3 remaining ordered places which can have one of 2 colors each. c. 3 * 2 * 2 * 2 * 2 There are three possible colors for place #1 and only 2 for each of the remaining 4 places. d. C(3 + 5 - 1, 5) == C(7,5) How many ways can we choose 3 colors for 5 non-distinct objects? We throw the 5 objects into the 3 "color bins". Scoring: 5 points each -3 if you had most of the idea but made a formula error -------------------------------------- Problem 9 (graded by Tom) a. 3744 = 52 * 3 * 48 / 2! 52 ways to choose the first card; 3 ways to choose the suit of the card with the same rank; 48 ways to choose the remaining card. Remove the order introduced for the first 2 cards as draw order doesn't matter. OR 3744 = C(13, 1) * C(12, 1) * C(4, 2) * C(4, 1) Choose the rank of the pair; choose the rank of the oddball card; choose the suits of the pair; choose the suit of the oddball. Note that a pair does not intersect with 3-of-a-kind in this problem. b. 52 = 52 * 3 * 2 / 3! 52 ways to choose the first card, 3 ways for the second, 2 ways for the third. Divide to remove the draw order introduced. OR 52 = C(13, 1) * C(4, 3) Choose the rank; choose the three suits. c. 704 = 44 * 4 * 4 Choose the beginning card of the straight; choose the suit of the next card; choose the suit of the end card. Note that there are 11 possible ranks which can be the beginning card (2 .. Queen). d. 1144 = 52 * 12 * 11 / 3! Choose a card which will determine the suit of the flush. Choose the rank of the second card and the rank of the third card. Divide to remove the order introduced when drawing 1st, 2nd, 3rd cards. OR 1144 = C(4, 1) * C(13, 3) Choose the suit for the flush; choose 3 ranks from the 13 possible. e. 44 Choose the beginning card of the straight flush. The remaining cards are thus determined. (e.g. A 4 of spades chosen means that the 5 and 6 of spades are the only possible options because we chose the beginning card) f. 16,500 = C(52, 3) - (a + b + c + d) + e The total number of combinations of 3 cards minus the ways of combining them that we mentioned in the problem. As a straight flush is both a straight and a flush, we've subtracted it twice and must add it back. Scoring: 5 points each -3 if you had the idea but made a formula error On part 'f', I was looking for the correct formula and C(52, 3). If your numbers were wrong from a..e, but your formula was correct, you got full credit. ------------------------------------------------------------------- Problem 10: ---------- val f = filter(fn(x) => x<10); Note that replacing x<10 by "if x<10 then true else false" isn't wrong, but why bother? Error codes: ----------- X1: not using an anonymous function. (-4) X2: using L or something as a second argument for f or for your anon. function. (-3) ------------------------------------------------------------------- Problem 11: ---------- (a) fun same(Empty,Empty) = true | same(Empty,_) = false | same(_,Empty) = false | same(Node(a,b),Node(c,d)) = same(a,c) andalso same(b,d); (b) fun samel(Empty,Empty) = true | samel(Empty,_) = false | samel(_,Empty) = false | samel(Node(x,a,b),Node(y,c,d)) = x=y andalso samel(a,c) andalso samel(b,d); Sorry about this; it was too much credit for two problems that are almost the same. Error Codes: ----------- X1: Empty doesn't take an argument (-5) X2: Confusing datatype values with lists (-5) X3: Not checking the Empty-Empty case first (-4). It causes Empty-Empty to get caught by a pattern like (Empty,_) and return false instead of true. ------------------------------------------------------------------- Problem 12: ---------- fun printList(L: int list ref) = while !L <> nil do ( print(hd(!L)); print("\n"); L := tl(!L); ); Error Codes: ----------- X1: Not using ! (-3) X2: Not using := (-3) X3: Not generating the newline "\n" (-1) X4: != instead of <> (-1) X5: Putting a recursion in the while-loop (-5). Your function will run forever. X6: Failing to mimic the C code as well as the answer above. ------------------------------------------------------------------- Problem 13: ---------- fun inv(1,A) = 0 | inv(n,A) = inv(n-1,A) + if sub(n-1,A) < sub(n-2,A) then 1 else 0; Error Codes: ----------- X1: Using a "helper" function to count up instead of down (-2) X2: Not using sub (-3) X3: (-2) for any of a number of "off-by-one" errors, such as using 0 as the basis or comparing A[n] with A[n-1]. (Note that as in C, an n-element array doesn't have an A[n].) ------------------------------------------------------------------- Problem 14: ---------- (a) The FBT of height 0 is a single node. The sum of the heights of the nodes is this tree is therefore 0. The value of 2^{n+1}-n-2 when n=0 is also 0. (b) The sum of the heights of the nodes in a FBT of height n+1 is 2^{n+2} - n -3. (c) n+1. (d) A FBT of height n+1 consists of a root at height n+1 and two FBT's of height n. By the inductive hypothesis, the sum of the heights of all nodes in these trees plus the root is 2(2^{n+1} - n - 2) + (n+1) = 2^{n+2} - n - 3. Error Codes: ----------- X1: Forgetting that S(n) is a statement, not a formula (-2) X2: Not referring to the tree in (b) or (d). (-2, each) X3: (not used) X4: Failing to simplify expressions (-1, each). ------------------------------------------------------------------- Problem 15: ---------- The answers to (a) through (d) are C, A, B, D, respectively. Scoring: ------- You lost 2 points for each letter that either should be there and wasn't or that wasn't there and should be (up to 20 pts. off). ------------------------------------------------------------------- Problem 16: ---------- The correct entries in the table: n n 1 1 n log n n log n Error Code: X1: Using a non-simple expression (-1)