Question

Analysis of Algorithms Fall 2013 Do any (4) out of the following (5) problems 1. Assume n-3t is a power of 3 fork20. Solve accurately the following recursion. If you cannot find the exact solution, use the big-O notation. Tu) T(n)Tin/3)+2 2. Suppose that you have 2 differeut algorithms to solve a giveu probleen Algorithm A has worst-case time complexity e(n2) and Algorithm B has worst-case time complexity e(nlog n). Which of the following statements are true and which are false? Justify your answers (a) Algorithm B runs faster than algorithm A on all possible inpats of length n, for n 2 1 (b) There exists no such that for any n > no, algorithm B runs faster than algorithm A on all imputs of length n. (c) It is possible that for n- 100, algorithm A runs faster than algorithm B on all possible Inrests nf lergth 100 3. Let A-lAll < AI2I < . . . < Aİnl be a sorted array ontaining n distinct positive integers. Let z be a positive integer such that both z and 2z are not in A Describe an efficient algorithn to find the aumber of integers in A that are larger than and smaller than 2s. What is the complexity of your algorithm? Justify your answer 4. The union of two graphs with the same set of vertices is a graph with the same vertex set, and all of the edges of both graphs. A graph contains another greph if its set of edges includes all of the edges of the other graph. Let F, G, and H be three graphs on the same set of n vertices. Assume these graphs are represensted by their adjsceney matrices. Dascribe an O(n) algorithm to decide whetber G contains the union of F and H (FUHSG). 5、Consider the sets P, NP, and NPC. Mark each of the following six statements as true, false, or unknown. NPCS NP NPS NPC

Answer 1

1)

Code://using Recursion

#include <iostream>

using namespace std;

long int calculatePower(int exponent)
{
   if (exponent == 1)
   {
       return 3;
   }
   return calculatePower( exponent - 1) * 3;
}
void main()
{
   cout << "Value : " << calculatePower(3);
}

2)a) True. Algorithm B runs more faster more increasing data size that is when n increases.

b) True, For most of the values of n Algorithm B runs faster than Algorithm A.For example for n = 2 O(n^2) = 4 and for O(n log n) it will be almost equal to 4 .This indicates that for small values of n which is less than 5.Both the time complexities will be almost equal.

c)False, For input size n like 100 Algorithm B will run many times faster when compared to Algorithm A. As explained in section b.