Question

1.       Assume the following recursive formula:

R(n)=R(n-1)*n*n where R(0)=1

The code might look like this:

public double R(n)

{

              If n==0 return 1

              else return R(n-1);

}

a.       What is the recurrence relation showing the number of multiplications for the recursive function R(n) and program?

b.       Solve the recurrence relation.

2.       Show the following is true for all integers n > 1 using mathematical induction:

  

3.       Sort the following list into alphabetical order using selection sort. Write the list showing the swapped items at each iteration:

shazam

4. Sort the following list into alphabetical order using insertion sort. Write the list showing the position of the items at each iteration.

shazam

Answer 1

...

___________________________________________________________________

_______________________

___________________________________________________________________

List: shazam

Iteration 1:

Swap index: 2 0
i.e. Swap: a s
List: ahszam

Iteration 2:

Swap index: 4 1
i.e. Swap: a h
List: aaszhm

Iteration 3:

Swap index: 4 2
i.e. Swap: h s
List: aahzsm

Iteration 4:

Swap index: 5 3
i.e. Swap: m z
List: aahmsz

Iteration 5:

Swap index: 4 4
i.e. Swap: s s
List: aahmsz

So, sorted list: aahmsz

___________________________________________________________________

List: shazam

Iteration 1:
List: hsazam

Iteration 2:
List: ahszam

Iteration 3:
List: ahszam

Iteration 4:
List: aahszm

Iteration 5:
List: aahmsz

Iteration 6:
List: aahmsz

So, sorted list: aahmsz

___________________________________________________________________

Note: If you have queries or confusion regarding this question, please leave a comment. I would be happy to help you. If you find it to be useful, please upvote.