CS 135 Spring 2025 Mid-Term Practice Problems
Uploaded by
alanhujrCS 135 Spring 2025 Mid-Term Practice Problems
Uploaded by
alanhujrCommon questions
Powered by AIThe Scheme function 'func' reverses a list through 'myfun', appending elements in reverse order. Inductive proof: For n=0, myfun A B returns B, valid as reversing nothing adds nothing. Assume for n, reversing A of length n appends to B correctly. For n+1, 'myfun (cdr A) (cons (car A) B)' integrates the head of A after reverse of cdr. Inductively following this process confirms reversal correctness for any n-length A, as returning elements prepended ensures full list reversal .
The function 'func' uses auxiliary 'myfun' to reverse its input list. For '(1 2 3)', it returns '(3 2 1)'. The function acts by recursively moving the first element to the back of accumulating parameter B, reversing the entire list cumulatively. This behavior proves consistent for lists of any length, applying recursion until all input elements are transferred to B in reverse order .
By changing the recursive combination line in the function, the structure fits Fibonacci's definition: f(n) = f(n-1) + f(n-2). In the original scheme, adding the result of the next step onwards with two-stepped prior echoes Fibonacci progression. Validation uses induction: Given base case fits f(0)=0, f(1)=1, modify recursion validates f(n)=f(n-1)+f(n-2), confirming Fibonacci calculation specification, building numbers sequentially in recursive results .
The function 'mystery' computes ⌈n/2⌉, where n is the length of the list. This indicates it counts the number of elements, considering every two elements count as one. Proof by induction: For n=0, it returns 0. For n=1, it returns 1, which matches ⌈1/2⌉. Assuming for n, it holds ⌈n/2⌉, then for n+1, analyzing 'mystery' shows return value of 1 plus the value for the list of length n-1: 1 + ⌈n/2⌉ = ⌈(n+1)/2⌉. This confirms the functionality .
To prove 1 + 2 + 2^2 + ... + 2^n = 2^(n+1) - 1 by induction, establish the base case for n=0: 1 = 2^1 - 1, which holds. Inductive hypothesis assumes true up to some k, i.e., 1 + 2 + ... + 2^k = 2^(k+1) - 1. The step shows for k+1, adding 2^(k+1) to both sides gives 2^(k+1) - 1 + 2^(k+1) = 2^(k+2) - 1. The manipulation concludes the hypothesis holds for k+1 as well, proving the statement .
To prove that any postage amount of 30 cents or more can be created using 4-cent and 11-cent stamps, start with a base case showing 30, 31, 32, 33 can be made explicitly: 30 = 2*4 + 2*11, 31 = 5*4 + 1*11, 32 = 8*4, 33 = 3*11. Inductive hypothesis assumes for some k≥33, all amounts from 30 to k can be made. The inductive step shows that by adding a 4-cent stamp to any k≥33 whose postage can be created, the next number k+1 can be formed: (k−3) + 4 = k+1. This completes the inductive proof .
The formula 1^2 + 2^2 + ... + n^2 = (1 + 2 + ... + n)^2 can be proven by induction. Base case n=1 confirms 1^2 = 1^2. Inductive hypothesis assumes true for some k, i.e., 1^2 + ... + k^2 = (1 + 2 + ... + k)^2. The step considers adding (k+1)^2 to both sides: LHS becomes 1^2 + ... + (k+1)^2, and RHS transforms with binomial expansion and simplification to match (1 + 2 + ... + (k+1))^2, confirming the hypothesis for k+1 .
With the modification, 'mystery' computes the Fibonacci sequence. Defined through recursive equations: f(0) = 0, f(1) = 1, f(n) = f(n−1) + f(n−2), the function construction mirrors this. The change to add results of mystery(cdr L) and mystery(cddr L) reflects the Fibonacci addition between previous terms. Identifying each step with Fibonacci definitions justifies the computation of the Fibonacci function by the modified 'mystery' .
Using set identities, (B−A) ∪ (C−A) can be rewritten as (B∩A̅) ∪ (C∩A̅). This is equivalent to (B∪C)∩A̅, which simplifies to (B∪C)−A, showing that (B−A) ∪ (C−A) is indeed a subset of (B∪C)−A. The transformation uses the identities of union, intersection, and set complement, thus proving the statement .
The argument's validity can be analyzed by examining logical propositions and checking if any counterexamples exist. The propositions are: U: Bob carries an umbrella, R: It is raining, C: It is cloudy. We have U→(R∨C) and C→¬U with the conclusion R→U. The argument is invalid because when R is true and U is false, both hypotheses are true regardless of C, and the conclusion is false. Therefore, this scenario serves as a valid counterexample showing the argument is invalid .