Description
Chapter 1
10 points
1) Suppose your calculator only did base 8ik.
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.
