Question

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

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

Solutions

Expert Solution



...

___________________________________________________________________




_______________________

___________________________________________________________________

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.


Related Solutions

Give a recursive algorithm to solve the following recursive function. f(0) = 0;    f(1) = 1;...
Give a recursive algorithm to solve the following recursive function. f(0) = 0;    f(1) = 1;   f(2) = 4; f(n) = 2 f(n-1) - f(n-2) + 2; n > 2 b) Solve f(n) as a function of n using the methodology used in class for Homogenous Equations. Must solve for the constants as well as the initial conditions are given.
Consider the following recursive method in Java public static int mystery(int n) {   if (n ==...
Consider the following recursive method in Java public static int mystery(int n) {   if (n == 0)   return 1;    else    return 4 * mystery (n - 1);   } What is the output of  mystery (3) using the code segment above Show your work on your trace file
1)(a) Approximate the value of the double integral, ∫ ∫ R x 2 ydA, where R...
1)(a) Approximate the value of the double integral, ∫ ∫ R x 2 ydA, where R = [−1, 5] × [0, 4], using the midpoint rule with m = 3 and n = 2. (b) Evaluate the double integral in the part (a), evaluating the corresponding iterated integral. 2)Let D be a region in the xy plane, between the graphs of y = 2 cos(x) and y = − sin(x), for 0 ≤ x ≤ π 2 . Sketch D...
Write the first four terms of the sequence defined by the recursive formula a1 = 2, an = an − 1 + n.
Write the first four terms of the sequence defined by the recursive formula a1 = 2, an = an − 1 + n.
Fix the following java code package running; public class Run {    public double distance; //in...
Fix the following java code package running; public class Run {    public double distance; //in kms    public int time; //in seconds    public Run prev;    public Run next;    //DO NOT MODIFY - Parameterized constructor    public Run(double d, int t) {        distance = Math.max(0, d);        time = Math.max(1, t);    }       //DO NOT MODIFY - Copy Constructor to create an instance copy    //NOTE: Only the data section should be...
Write a recursive formula for the arithmetic sequence 0, −1/2 , −1, −3/2 , … , and then find the 31st term.
Write a recursive formula for the arithmetic sequence 0, −1/2 , −1, −3/2 , … , and then find the 31st term.  
Let x, y ∈ R. Prove the following: (a) 0 < 1 (b) For all n...
Let x, y ∈ R. Prove the following: (a) 0 < 1 (b) For all n ∈ N, if 0 < x < y, then x^n < y^n. (c) |x · y| = |x| · |y|
What is the value of n after this code runs? 1 Point int n = 0;...
What is the value of n after this code runs? 1 Point int n = 0; int j = 7; if ((j!=0) && (n < 25)) { n = 1; if (j > 4) { n = 2; } else { n = 3; } } else { n = 4; if (j%2 >= 2) { n = 5; } else { n = 6; } }
Modify the following code to make the input and output look like this. Input 5 Vader...
Modify the following code to make the input and output look like this. Input 5 Vader 1300 Kirk 1250 Adama 1000 Reynolds 1615 Oneill 1470 Output Enter the number of candidates: 5 Enter candidate's name :Vader 1300 Enter votes received :Enter candidate's name :Kirk 1250 Enter votes received :Enter candidate's name :Adama 1000 Enter votes received :Enter candidate's name :Reynolds 1615 Enter votes received :Enter candidate's name :Oneill 1470 Enter votes received : Name Votes Percentage Vader 1300.00 19.59% Kirk...
Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the...
Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the function f(n)? Consider the following recurrence: an= 2an-1 + 3 (where a1 = 1). Compute the values of an for n ≤ 5. Find a solution for the recurrence definition and validate its correctness. Consider the following recurrence: an=2an-1 +an-1an-2 (where a1 = 1). Compute the values of an for n ≤ 5.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT