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;
}
.jpg "idly")
