# Problem Solving Through Programming In C Week 9

**Session: JULY-DEC 2023**

**Course Name: Problem Solving Through Programming In C**

**Course Link: Click Here**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q1. What is the worst case complexity of selection sort?**

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

**Answer: d) O(n ^{2})**

**Q2. What is the best case and worst case complexity of ordered linear search?**

a) O(nlogn), O(logn)

b) O(logn), O(nlogn)

c) O(n), O(1)

d) O(1), O(n)

**Answer: d) O(1), O(n)**

**Q3. Given an array arr = {12, 34, 47, 62, 85, 92, 95, 99,105} and key = 34; what are the mid values (corresponding array elements) generated in the first and second iterations?**

a) 85 and 12

b) 85 and 34

c) 62 and 34

d) 62 and 47

**Answer: b) 85 and 34**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q4. When the Binary search is best applied to an array?**

a) For very large size array

b) When the array is sorted

c) When the array elements are mixed data type

d) When the array is unsorted

**Answer: b) When the array is sorted**

**Q5. 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

**Answer: c) 75**

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

**Answer: a)**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q7. What will be the output?**

a) 3 5

b) 3 0

c) 5 0

d) 5 3

**Answer: d) 5 3**

**Q8. Consider an array of elements arr[5]= {5,4,3,2,1}, what are the steps of insertions done while doing insertion sort in the array.**

**Answer: a)**

**Q9. What will be the output of the following C code?**

a) 0

b) 1

c) 01

d) None of the above

**Answer: b) 1**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q10. What will be the output?**

a) 10 10

b) 10 50

c) 50 50

d) Compilation error

**Answer: d) Compilation error**

### Assignment

**Question 1Write 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 array5657If the element to search is 5 then the output will be5 is present at location 15 is present at location 35 is present 2 times in the array.**

**Solution:**

```
int kp=0;
for(c=0;c < n;c++)
{
if(search==array[c])
{
kp=1;
break;
}
}
if(kp==1)
{
for(c=0;c < n;c++)
{
if(search==array[c])
{
printf("%d is present at location %d.\n",search,(c+1));
count++;
}
}
printf("%d is present %d times in the array.\n",search,count);
}
else
printf("%d is not present in the array.\n",search);
return 0;
}
```

**Question 2Write 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:**

```
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[], int n, int find)
{
int cdc;
for (cdc = 0 ;cdc < n ; cdc++ )
{
if (a[cdc] == find)
return cdc;
}
return -1;
}
```

**Question 3Write 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.**

**Solution:**

```
int first, last, middle;
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last)
{
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
{
printf("%d found at location %d.", 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.", search);
return 0;
}
```

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

**Solution:**

```
int tp, end;
end = n - 1;
for (c = 0; c < n/2; c++)
{
tp = array[c];
array[c] = array[end];
array[end] = tp;
end--;
}
```

**These are Problem Solving Through Programming In C Assignment 9 Answers**

More Weeks of Problem Solving Through Programming In C: Click here

More Nptel Courses: Click here

**Session: JAN-APR 2023**

**Course Name: Problem Solving Through Programming In C**

**Course Link: Click Here**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q1. What is the worst case complexity of selection sort?**

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^2)

**Answer: d) O(n^2)**

**Q2. What is the error in the following program?**

a) Variable ‘a’ should be replaced by ‘si’

b) Nothing will print

c) Error due to multiple declaration of si

d) No error

**Answer: c) Error due to multiple declaration of si**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q3. When the Binary search is best applied to an array?**

a) For very large size array

b) When the array is sorted

c) When the array elements are mixed data type

d) When the array is unsorted

**Answer: b) When the array is sorted**

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

a) int unorderedLinear Search(int arr[], int size, int data) { int index; for(int i = 0; i < size; i++) { if(arr[i] { } } = data) index = i; break; } return index : }

b) int unordered Linear Search(int arr[], int size, int data) { int index; for(int i = 0; i < size; i++) { if(arr[i] == data) { break; } } return index : }

c) int unorderedLinear Search(int arr[], int size, int data) { int index; for(int i = 0; i <= size; i++) { } if(arr[i] = data) { index = i; continue; } return index : }

d) None of these

**Answer: a) int unorderedLinear Search(int arr[], int size, int data) { int index; for(int i = 0; i < size; i++) { if(arr[i] { } } = data) index = i; break; } return index : }**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q5. What is the best case and worst case complexity of ordered linear search?**

a) O(nlogn), O(logn)

b) O(logn), O(nlogn)

c) O(n), O(1)

d) O(1), O(n)

**Answer: d) O(1), O(n)**

**Q6. Which of the following is a disadvantage of linear search?**

a) Requires more space

b) Greater time complexities compared to other searching algorithms

c) Not easy to understand

d) All of the mentioned

**Answer: b) Greater time complexities compared to other searching algorithms**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

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

a) 91 and 98

b) 91 and 100

c) 89 and 94

d) 94 and 98

**Answer: a) 91 and 98**

**Q8. Select the appropriate pseudocode that performs selection sort**

a) int min; for(int j=0; j<arr.length-1; j++) { min = j; for(int k=j+1; k<=arr.length-1; k++) { if(arr[k] < arr[min]) min = k; } int temp = arr[min]; arr[min] = arr[j]; arr[j] = temp; }

b) int min; for(int j=0; j<arr.length-1; j++) { min =j; for(int k=j+1; k<=arr.length; k++) { if(arr[k] < arr[min]) min = k; } int temp = arr[min]; arr[min] = arr[j]; arr[j] = temp;

c) int min; for(int j=0; j arr[min]) min = k; } int temp = arr[min]; arr[min] = arr[j]; arr[j] = temp : }

d) int min; for(int j=0; j arr[min]) min = k; } int temp = arr[min]; arr[min] = arr[j]; arr[j] = temp : }

**Answer: a) int min; for(int j=0; j<arr.length-1; j++) { min = j; for(int k=j+1; k<=arr.length-1; k++) { if(arr[k] < arr[min]) min = k; } int temp = arr[min]; arr[min] = arr[j]; arr[j] = temp; }**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Q9. Consider the array A[ ]= {5,4.9,1,3} apply the insertion sort to sort the array. Consider the costassociated with each sort is 25 rupees, what is the total cost of the insertion sort when element 1reaches the first position of the array?**

a) 25

b) 50

c) 75

d) 100

**Answer: b) 50**

**Q10. Find the output of the following C program**

a) 5,4

b) 5,5

c) 4,4

d) 3,4

**Answer: c) 4,4**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

### Problem Solving Through Programming In C 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 there are 4 elements in the array 5 6 5 7The element to search is 5 then the output will be:5 is present at location 15 is present at location 35 is present 2 times in the array.**

**Solution:**

```
for (c = 0; c < n; c++)
{
if (array[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;
}
```

**Question 2**

**Write a C program to marge two given sorted arrays (sorted in ascending order).The code for input and output is already written. You have to write the merge function so that the merged array is displayed in ascending order.**

**Solution:**

```
void merge(int a[], int m, int b[], int n, int sorted[])
{
int i = 0, j = 0, k = 0;
while (i < m && j < n)
{
if (a[i] <= b[j])
{
sorted[k++] = a[i++];
}
else
{
sorted[k++] = b[j++];
}
}
while (i < m)
{
sorted[k++] = a[i++];
}
while (j < n)
{
sorted[k++] = b[j++];
}
}
```

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**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.**

**Solution:**

```
int first, last, middle;
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[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;
}
```

**Question 4**

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

**Solution:**

```
int temp, end;
end = n - 1;
for (c = 0; c < n/2; c++){
temp = array[c];
array[c] = array[end];
array[end] = temp;
end--;
}
```

**These are Problem Solving Through Programming In C Assignment 9 Answers**

More Weeks of Problem Solving Through Programming In C: Click Here

More Nptel courses: https://progiez.com/nptel

**Session: JULY-DEC 2022**

Course Name: Problem Solving Through Programming In C NPTEL

Link of course: Click Here

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**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 Problem Solving Through Programming In C Assignment 9 Answers**

**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

**Answer: c) 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 Problem Solving Through Programming In C Assignment 9 Answers**

**Q5. Consider an array of elements A[7]= {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

**Answer: b) 4,7,10,23,67,12,5**

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

**Answer: (a)**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**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, 8II. 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

**Answer: b) II**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**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

**Answer: c) 75**

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**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 Problem Solving Through Programming In C Assignment 9 Answers**

## Programming Assignment

**Question 1Write 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 array5 6 5 7If the element to search is 5, then the output will be:5 is present at location 15 is present at location 35 is present 2 times in the array.**

**Solution:**

`//Code`

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Question 2Write 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:**

`//Code`

**These are Problem Solving Through Programming In C Assignment 9 Answers**

**Question 3Write 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.**

`//Code`

**These are Problem Solving Through Programming In C Assignment 9 Answers**

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

**Solution:**

`//Code`

**These are Problem Solving Through Programming In C Assignment 9 Answers**

More NPTEL Solution: https://progiez.com/nptel