DataStructures – Assignment #1 Solved

Description

 

 

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.

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

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

1. 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
2. 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.