## 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.