In: Computer Science
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
...
___________________________________________________________________
_______________________
___________________________________________________________________
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.