### Problem Solving Through Programming In C NPTEL Assignment 9

Course Name: Problem Solving Through Programming In C NPTEL

### These are answers for Problem Solving Through Programming In C Assignment 9

Q1. What is the best case complexity of ordered linear search and worst case complexity of selection sort respectively?
a) 0(1), O(n²)
b) O(logn), O(1).
c) O(n), O(logn)
d) O(n²), O(nlogn)

Answer: a) 0(1), O(n²)

Q2. Which of the following is/are correct?
I.Binary search is applied when elements are sorted.
II.Linear search can be applied when elements are in random order.
III. Binary search can be categorized into divide and conquer rule.

a) I & II
b) Only I
c) I and III
d) I,II & III

Answer: d) I,II & III

These are answers for Problem Solving Through Programming In C Assignment 9

Q3. What is the recurrence relation for the linear search recursive algorithm?
a) T(n-2)+c
b) 2T(n-1)+c
c) T(n-1)+c
d) T(n+1)+c

Q4. Given an array arr = {20, 45, 77, 89, 91, 94, 98,100} and key = 45; what are the mid values (corresponding array elements) generated in the first and second iterations?
a) 91 and 98
b) 89 and 45
c) 89 and 77
d) 91 and 94

Answer: b) 89 and 45

These are answers for Problem Solving Through Programming In C Assignment 9

Q5. Consider an array of elements A= {10,4,7,23,67,12,5}, what will be the resultant array A after third pass of insertion sort.
a) 67,12,10,5,4,7,23
b) 4,7,10,23,67,12,5
c) 4,5,7,67,10,12,23
d) 10,7,4,67,23,12,5

Q6. Select the code snippet which performs unordered linear search iteratively?

These are answers for Problem Solving Through Programming In C Assignment 9

Q7. Which of the following input will give worst case time complexity for selection sort to sort an array in ascending order?
I. 1,2,3, 4, 5, 6, 7, 8
II. 8,7,6, 5, 4, 3, 2, 1,
III. 8,7,5,6,3,2,1,4

a) I
b) II
c) II and III
d) I,II and III

These are answers for Problem Solving Through Programming In C Assignment 9

Q8. Consider the array A[] {5,4,9,1,3} apply the insertion sort to sort the array. Consider the cost associated with each sort is 25 rupees, what is the total cost of the insertion sort for sorting the entire array?
a) 25
b) 50
c) 75
d) 100

These are answers for Problem Solving Through Programming In C Assignment 9

Q9. A sorting technique is called stable if :
a) It takes O(nlog n)time
b) It maintains the relative order of occurrence of non-distinct elements
c) It uses divide and conquer paradigm
d) It takes O(n) space

Answer: b) It maintains the relative order of occurrence of non-distinct elements

Q10. The average case occurs in the Linear Search Algorithm when
a) The item to be searched is in some where middle of the Array
b) The item to be searched is not in the array
c) The item to be searched is in the last of the array
d) The item to be searched is either in the last or not in the array

Answer: a) The item to be searched is in some where middle of the Array

These are answers for Problem Solving Through Programming In C Assignment 9

## Programming Assignment

Question 1
Write a program to print all the locations at which a particular element (taken as input) is found in a list and also print the total number of times it occurs in the list. The location starts from 1.
For example if there are 4 elements in the array
5 6 5 7
If the element to search is 5,  then the output will be:
5 is present at location 1
5 is present at location 3
5 is present 2 times in the array.

Solution:

``````#include &lt;stdio.h>
int main()
{
int array&#91;100], search, n, count = 0;
scanf("%d", &amp;n);
int c;
for (c = 0; c &lt; n; c++)
scanf("%d", &amp;array&#91;c]);

scanf("%d", &amp;search);
for (c = 0; c &lt; n; c++)
{
if (array&#91;c] == search)
{
printf("%d is present at location %d.\n", search, c+1);
count++;
}
}
if (count == 0)
printf("%d is not present in the array.\n", search);
else
printf("%d is present %d times in the array.\n", search, count);

return 0;
}``````

These are answers for Problem Solving Through Programming In C Assignment 9

Question 2
Write a C program to search a given element from a 1D array and display the position at which it is found by using linear search function. The index location starts from 1.

Solution:

``````#include &lt;stdio.h>
int linear_search(int&#91;], int, int);
int main()
{
int array&#91;100], search, c, n, position;

scanf("%d", &amp;n);
for (c = 0; c &lt; n; c++)
scanf("%d", &amp;array&#91;c]);

scanf("%d", &amp;search);
position = linear_search(array, n, search);

if(position == -1)
printf("%d is not present in the array.\n", search);
else
printf("%d is present at location %d.\n", search, position+1);
return 0;
}

int linear_search(int a&#91;], int n, int find)
{
int c;
for(c = 0; c&lt;n; c++)
{
if(a&#91;c] == find)
return c;
}
return -1;
}``````

These are answers for Problem Solving Through Programming In C Assignment 9

Question 3
Write a C program to search a given number from a sorted 1D array and display the position at which it is found using binary search algorithm.
The index location starts from 1.

``````#include &lt;stdio.h>
int main()
{
int c, n, search,array&#91;100];
scanf("%d",&amp;n);

for (c = 0; c &lt; n; c++)
scanf("%d",&amp;array&#91;c]);

scanf("%d", &amp;search);
int first, last, middle;
first = 0;
last = n - 1;
middle = (first+last)/2;

while(first &lt;= last)
{
if(array&#91;middle] &lt; search)
first = middle + 1;
else if(array&#91;middle] == search)
{
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last)/2;
}
if(first > last)
printf("Not found! %d isn't present in the list.\n", search);

return 0;
}``````

These are answers for Problem Solving Through Programming In C Assignment 9

Question 4
Write a C program to reverse an array by swapping the elements and without using any new array.

Solution:

``````#include &lt;stdio.h>
int main() {
int array&#91;100], n, c;
scanf("%d", &amp;n); // n is number of elements in the array.
for (c = 0; c &lt; n; c++)
{
scanf("%d", &amp;array&#91;c]);
}
int temp, end;
end = n - 1;
for(c = 0; c &lt; n/2; c++)
{
temp = array&#91;c];
array&#91;c] = array&#91;end];
array&#91;end] = temp;
end--;
}
printf("Reversed array elements are:\n");

for (c = 0; c &lt; n; c++)
{
printf("%d\n", array&#91;c]);
}
return 0;
}``````

These are answers for Problem Solving Through Programming In C Assignment 9

All weeks of Problem Solving Through Programming In C: https://progies.in/answers/nptel/problem-solving-through-programming-in-c

More NPTEL Solution: https://progies.in/answers/nptel

* The material and content uploaded on this website are for general information and reference purposes only. Please do it by your own first.

### Correct Slippers: CORRSLP