procedure MYSTERY (int n, int a if (n == 0) then return 0 end if int tmp1 = MYST

Question

procedure MYSTERY (int n, int a if (n == 0) then return 0 end if int tmp1 = MYSTERY(n/2, a)//assume n/2 rounds down. int tmp2 = 0 for int i = 1 to n/2 do tmp2 + = a end for if (n%2 = = 1) then return tmp1 + tmp2 end if end procedure Consider the previous recursive algorithm MYSTERY that takes as input integers n and a What does the mystery function compute Set up a runtime recurrence for the mystery method above. Do not forget the base case. Is this mystery function a divide-and-conquer algorithm? Briefly justify your answer

Explanation / Answer

1) The function simply computes n*a (n times a) by continuous addition and recurssion. Here is a java example using the provided algorithm.

PROGRAM CODE:

import java.util.*;
import java.lang.*;
import java.io.*;

class Mystery
{
   public static int mystery(int n, int a)
   {
       if(n==0)
           return 0;
      
       int temp1 = mystery(Integer.valueOf(n/2), a);
       int temp2 = 0;
       for(int i=1; i<=Integer.valueOf(n/2); i++)
           temp2 += a;
       if(n%2 == 1)
           return temp1+temp2+a;
       else return temp1+temp2;
   }
   public static void main (String[] args) throws java.lang.Exception
   {
       System.out.println(mystery(20,1));
       System.out.println(mystery(21,10));
       System.out.println(mystery(30,13));
   }
}

OUTPUT:

2) f(n, a) = f(n/2, a) + O(n/2, a) where n > 0 , a > 0

3) This function recursively divides n by half and computes the addition. One half goes into recursion and the other half is computed manually using for loop. So it does follow divide and conquer but not full fledgedly.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.