Problem 1 (graded by Tom): a. not((not p) or q) or r b. (p and not q) or r *********************************************** Problem 2 (graded by Tom): a. p -> (p -> q) b. (forall X) (not p (X)) c. (not p) or q *********************************************** Problem 3 (graded by Scott) a) S(n): If L is a list of length n, then max(L) returns the maximum element in L. b) n=1 c) If L=[x], then the first pattern matches and max returns x. Since x is the only element in L, it is indeed the largest element in L. Therefore max works correctly on a list of length 1. d) Our inductive hypothesis is S(n), n >= 1. We need to show that max(L) returns the maximum element 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, m = max(xs) is the maximum element of xs. The maximum element of L is the maximum of its first element x and the maximum element in its tail xs. The "if" statement implements this logic in deciding whether to return x or m. Therefore max(L) returns the maximum element in L. Grading ------- a) 3 points N didn't mention that n is the length of the list -2 EX "a list of length n has a maximum element" -3 People who wrote this answer completely missed the point of the problem (you're trying to prove that a piece of ML code does what it is intended to do) and ended up getting somewhere in the neighborhood of 2-4 points total on the problem. Important Note: S(n) is NOT the max function. It is NOT an element of the input list. It is the statement that you are trying to prove true for all n >= 1. b) 1 point c) 3 points FP no indication that the first pattern of max matches and -2 the only element in the list is returned M no logic/statement that the maximum element in a one element -1 list is that element There are two parts to showing that max works on a list of length 1: saying what max returns (FP) and why this is the correct value to return (M). d) 8 points SP You need to give some indictation that the second pattern 2 matches in this case. This could have been stated outright or strongly implied by the usage of our variable names (x,xs,m). People who forgot that they were proving something about the function max did not have this component of a correct solution. IH Statement and proper usage of the inductive hypothesis 4 (including indication of where you used the inductive hypothesis) As in the proof of the basis case, you need to say what max 2 will return and why it is the correct value to return L logic that maximum(x,m) is the maximum of L=x::xs 1 R max returns maximum(x,m) 1 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 (graded by Scott) The function max (as given) does not handle the empty list input. When max receives the empty list it should raise an exception. Grading ------- empty list 5 raise an exception 5 Z "max([]) should return 0" -3 NIL "max([]) should return nil" -5 In this case, max won't even compile. *********************************************** Problem #5 (graded by Tom) Prove the basis. For n = 1, there are two cases. The base case can be a 0 or a 1. Both are true by definition. Prove the inductive step S(n) -> S(n+1). Assume: The induction is true for S(n). Prove true for S(n + 1). Let w be a string of length n+1, consisting of 0's and 1's. Then w = 0x or w = 1x, where x is a string of length n and by the inductive hypothesis is therefore a Goofy string. Case 1: w = 0x. This case is true by rule 1 of the induction. Case 2: w = 1x By rule 2, x^R (x reversed) is also a Goofy string. Let us append a 1 to x^R, yielding x^R1, which is a Goofy string by rule 1. If we reverse this Goofy string we get (x^R1)^R which is 1x and therefore is also w. Grading Codes of Problem #5, Test # 1 Code Meaning I Basis was not correct. Often n = 2 was included unnecessarily. II Omitting a needed basis case. III A basis value was omitted. IVa You did not show a string of length n+1 = 0 or 1 followed by a string of length n IVb Omitted Case: string begins with 0 IVc Omitted Case: string begins with 1 IVd You did not fully show reversal of string. IVe No form to your proof. Generally included the above errors. V You used strong induction. VI You went from the assumed to the known. *********************************************** Problem 6 (graded by Jeff): fun samePos(nil,_) = nil | samePos(_,nil) = nil | samePos(x::xs, y::ys) = if x=y then x::samePos(xs,ys) else samePos(xs,ys); Error Codes ----------- X1: Fail to handle case where both lists are nil (-3) X2: Fail to use tail of one of the lists in a recursion (-5) X3: Ignore all cases where one or both lists are nil (-7) X4: Missing case where one list is nil and the other is of length > 1. (-3) *********************************************** Problem 7 (graded by Jeff) a) (0,1) and (1, 3/4) where the most popular choices for n_0 and c. b) (1, 1.53), (4, 3/2), and (8, 11/8) were among the popular correct answers. (1, 3/2) is not correct; see the comment regarding code X3 below. c) (2,20), (3,15), (4, 40/3), and (11,11) appeared frequently. Error Codes ----------- X: "no" was your response. Note that the big-oh relationship held in each of the three parts. (-5) X1: Witnesses are not minimal (-2) X2: Non-witnesses offered but "yes" was the response (-3) X3: You lost one point for not realizing that for n=3, the ratio of n+ log_2(n) / n reaches its maximum, (3+1.59)/3 = 1.53 roughly. It was subtle, and I hadn't realized this point until I started grading, so I only deducted one point. Note that if you were unsure whether log_2(3) was bigger than 1.5, you could either finesse the issue by picking n_0 = 4, or you could figure it out as follows. To prove log_2(3) > 3/2, raise 2 to the power on each side. Thus log_2(3) > 3/2 if and only if 3 > 2^{3/2}. Now, square both sides: log_2(3) > 3/2 if and only if 9 > 2^3 = 8. Since 9>8 obviously, we can now RUN THE EQUIVALENCES backward to prove from 9>8 that log_2(3) > 3/2.