nptel 4th week assessment and assignment answer

ASSESSMENT
1.Consider the following code segment. Assume n to be a positive integer.

for(i=1; i<=n; i++)

{

    for(j=1; j<=n; j=j+i)
    {

        printf(“Hi”);

    }

}

Let T(n) represent the total running time of the above code segment. Specify which of the following statements are correct.

T(n)=O(n^2)

T(n)=O(n*log n)

 T(n)≠O(n^4)

 T(n)=O(log n)

2.Let P(x)=3x^2 + 4x + 2 be a polynomial in the variable x. If Horner’s rule is used, what is the number of multiplications to compute P(10)?

Ans:2

3.To multiply two six digit numbers what is the number of single digit multiplication operations performed by Karatsuba’s Algorithm?

Ans:12

4.What is the degree of the polynomial defined by R(x) = P(x) * Q(x) where P(x) = x^3+x^2+1 and Q(x) = x^2+ x + 1?

Ans:5

5.For the following array and the specified search key, what will be the number of comparisons performed by unordered linear search?
array = { 10, 7, 3, 9, 11, 18, 15, -6, 25, 9, 16, 19}
search key = 15

Ans:7

6.For the following array and the specified search key, what will be the number of iterations performed by binary search?
array = {-6, 3, 4, 7, 9, 10, 11, 15, 16, 18, 19, 22, 25 , 33, 47}
search key = 12

Ans:4

7.Can linear search take lesser number of comparisons than binary search to find an element in an array?

Yes

 No

8.Given the two arrays below which are to be merged into a single array sorted in ascending order, total number of comparisons required to merge these arrays will be:
A1 = (10, 20, 30, 40, 50, 60)
A2 = (15, 25, 35, 45)

Ans:8

9.You are given a sorted array A of size 200 elements. Five values are appended at the end of the array. Which sorting algorithm would be a better candidate for sorting the whole array?

Insertion Sort

 Merge Sort

10.Suppose that the range of values k in counting sort is not of O(n). Is counting sort still guaranteed to sort in linear time?

 Yes

 No

11.Does counting sort use comparisons for sorting?

 Yes

 No

12.If radix sort uses an unstable sorting algorithm to sort the digits in radix sort, is it still guaranteed to work correctly?

 Yes

 No

13.Let the numbers 794, 332, 561, 342, 200, 607, and 893 be sorted using radix sort. What will be the sixth number in the sequence of numbers after sorting the second digit?

Ans:893

14.Find median (arithmetic mean if more than one median) for the given array. A = { 10, 30, 20, 17, 25, 28, 13, 27}

Ans:21

15.Find median (arithmetic mean if more than one median) for the given array. A = { 10, 30, 20, 25, 28, 13, 27}

Ans:25

MERGEING WORDS

#include <stdio.h> 

 #include <string.h> 

 int main() { 

   char a[20], b[10], c; 

   int x[20]; 

   int i,j,l,n,swap; 

   scanf("%s",a); 

   scanf("%s",b); 

   strcat(a,b); 

   l=strlen(a);

   for(i=0; i<l; i++) { 

     n = a[i]; 

     x[i] = n; 

   } 

   for(i=0; i<(l-1); i++) { 

     for(j=0; j<(l-i-1); j++) { 

       if(x[j]>x[j+1]) { 

         swap = x[j]; 

         x[j] = x[j+1]; 

         x[j+1] = swap; 

       } 

     } 

   } 

   for(i=0; i<l; i++) { 

     c = x[i];  

printf("%c",c); 

   } 

 } 

SORTING WORDS

#include <stdio.h> 

 #include <string.h> 

 int main(){ 

 int num, i, j, result, index; 

 char name[100][11];  

 char temp[11];   

 scanf("%d", &num); 

 for(i = 0; i < num; i++) 

 scanf("%s", name[i]); 

 for(i = 0; i < num; i++)  

 {  

 index = i; 

 for(j = i + 1; j < num; j++) 

 { 

 result = strcmp(name[index], name[j]); 

 if(result > 0)                 

 index = j; 

 } 

 strcpy(temp, name[index]); 

 strcpy(name[index], name[i]);           

 strcpy(name[i], temp); 

 } 

 for(i = 0; i < num-1; i++)  

 { 

 printf("%s\n", name[i]); 

 } 

 printf("%s", name[i]); 

 return 0; 

 }