Chapter 1
10 points
1) Suppose your calculator only did base 10 logarithms. Write an expression to compute log base 2 of 2048 using only log base 10.
10 points
2) Express the following summation in closed form (an expression that can be directly computed from k).
(Refer to slide 11)
3 + 5 + 7 + 9 + ... + 2k+1
10 points
3) Proof by counterexample
Prove that the following statement is false: n^3 > 2^n for any n >= 1
10 points
4) Proof by contradiction
Prove that the following statement is true: the square of an even number is also even
30 points
5) Induction proofs.
a. Prove by induction:
n
sum i^3 = [n^2][(n+1)^2]/4 i=1
Note: "sum" is the summation symbol, and ^ is for an exponent
b. Prove by induction: n^2 - n is even for any n >= 1
20 points 6) Recursion.
Note: You can use Java or pseudocode for these. If pseudocode then the logic must be complete and easy to understand.
a. Write a recursive function that when passed a value n displays n (n-1) (n-2) (n-3) ... 0 ... (n-3) (n-2) (n-1) n for example, if passed 5 displays 5 4 3 2 1 0 1 2 3 4 5
b. Write a recursive function that receives an array of integers and a position as parameters and returns the count of odd numbers in the array. Let each recursive call consider the next integer in the array.
10 points
7) Suppose there exists a generic Java class named Pair with type parameter T that stores two objects with get and set methods for each. Write the statements necessary to create an object of type Pair with String as its type parameter, and use the set methods to set the two strings, then the get methods to retrieve them for printing. Note that you do not need to write the
Pair class itself.
Submit to eLearning: assignment1.xxx where xxx is txt, doc, docx, pdf, or jpg You may scan handwritten work if you wish.
