1 Crore+ students have signed up on EduRev. Have you? 
Which of the following is correct recurrence for worst case of Binary Search?
Following is typical implementation of Binary Search. In Binary Search, we first compare the given element x with middle of the array. If x matches with middle element, then we return middle index. Otherwise, we either recur for left half of array or right half of array. So recurrence is T(n) = T(n/2) + O(1)
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. (GATE CS 2008)
f(int Y[10], int x) {
int i, j, k;
i = 0; j = 9;
do {
k = (i + j) /2;
if( Y[k] < x) i = k; else j = k;
} while(Y[k] != x && i < j);
if(Y[k] == x) printf ("x is in the array ") ;
else printf (" x is not in the array ") ;
}
On which of the following contents of Y and x does the program fail?
The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.
Given a sorted array of integers, what can be the minimum worst case time complexity to find ceiling of a number x in given array? Ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then output should be 100.
We modify standard binary search to find ceiling. The time complexity T(n) can be written as T(n) <= T(n/2) + O(1) Solution of above recurrence can be obtained by Master Method. It falls in case 2 of Master Method. Solution is O(Logn). [sourcecode language="C"] #include /* Function to get index of ceiling of x in arr[low..high]*/ int ceilSearch(int arr[], int low, int high, int x) { int mid; /* If x is smaller than or equal to the first element, then return the first element */ if(x <= arr[low]) return low; /* If x is greater than the last element, then return 1 */ if(x > arr[high]) return 1; /* get the index of middle element of arr[low..high]*/ mid = (low + high)/2; /* low + (high  low)/2 */ /* If x is same as middle element, then return mid */ if(arr[mid] == x) return mid; /* If x is greater than arr[mid], then either arr[mid + 1] is ceiling of x or ceiling lies in arr[mid+1...high] */ else if(arr[mid] < x) { if(mid + 1 <= high && x <= arr[mid+1]) return mid + 1; else return ceilSearch(arr, mid+1, high, x); } /* If x is smaller than arr[mid], then either arr[mid] is ceiling of x or ceiling lies in arr[mid1...high] */ else { if(mid  1 >= low && x > arr[mid1]) return mid; else return ceilSearch(arr, low, mid  1, x); } } /* Driver program to check above functions */ int main() { int arr[] = {1, 2, 8, 10, 10, 12, 19}; int n = sizeof(arr)/sizeof(arr[0]); int x = 20; int index = ceilSearch(arr, 0, n1, x); if(index == 1) printf("Ceiling of %d doesn't exist in array ", x); else printf("ceiling of %d is %d", x, arr[index]); getchar(); return 0; } [/sourcecode]
You are given a list of 5 integers and these integers are in the range from 1 to 6. There are no duplicates in list. One of the integers is missing in the list. Which of the following expression would give the missing number. ^ is bitwise XOR operator. ~ is bitwise NOT operator. Let elements of list can be accessed as list[0], list[1], list[2], list[3], list[4]
XOR of all list elements and numbers from 1 to 6 gives the missing number.
In the above question, the correction needed in the program to make it work properly is
Below is the corrected function f(int Y[10], int x) { int i, j, k; i = 0; j = 9; do { k = (i + j) /2; if( Y[k] < x) i = k + 1; else j = k  1; } while(Y[k] != x && i < j); if(Y[k] == x) printf ("x is in the array ") ; else printf (" x is not in the array ") ; }[/sourcecode]
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.
If we use median as a pivot element, then the recurrence for all cases becomes T(n) = 2T(n/2) + O(n) The above recurrence can be solved using Master Method. It falls in case 2 of master method.
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
The worst case of QuickSort occurs when the picked pivot is always one of the corner elements in sorted array. In worst case, QuickSort recursively calls one subproblem with size 0 and other subproblem with size (n1). So recurrence is T(n) = T(n1) + T(0) + O(n) The above expression can be rewritten as T(n) = T(n1) + O(n) void exchange(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition(int arr[], int si, int ei) { int x = arr[ei]; int i = (si  1); int j; for (j = si; j <= ei  1; j++) { if(arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); return (i + 1); } /* Implementation of Quick Sort arr[] > Array to be sorted si > Starting index ei > Ending index */ void quickSort(int arr[], int si, int ei) { int pi; /* Partitioning index */ if(si < ei) { pi = partition(arr, si, ei); quickSort(arr, si, pi  1); quickSort(arr, pi + 1, ei); } } [/sourcecode]
Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).
Insertion sort takes linear time when input array is sorted or almost sorted (maximum 1 or 2 elements are misplaced). All other sorting algorithms mentioned above will take more than lienear time in their typical implementation.
Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?
Selection sort makes O(n) swaps which is minimum among all sorting algorithms mentioned above.
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
1) to sort the array firstly create a minheap with first k+1 elements and a separate array as resultant array.
2) because elements are at most k distance apart from original position so, it is guranteed that the smallest element will be in this K+1 elements.
3) remove the smallest element from the minheap(extract min) and put it in the result array.
4) Now,insert another element from the unsorted array into the meanheap, now,the second smallest element will be in this, perform extract min and continue this process until no more elements are in the unsorted array.finally, use simple heap sort for the remaining elements Time Complexity  1) O(k) to build the initial minheap 2) O((nk)logk) for remaining elements... 3) 0(1) for extract min so overall O(k) + O((nk)logk) + 0(1) = O(nlogk)
How many different insertion sequences of the key values using the hash function h(k) = k mod 10 and linear probing will result in the hash table shown below?
In a valid insertion sequence, the elements 42, 23 and 34 must appear before 52 and 33, and 46 must appear before 33. Total number of different sequences = 3! x 5 = 30 In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.
The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.
The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.
The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include: linear probing in which the interval between probes is fixedoften at 1. quadratic probing in which the interval between probes increases linearly (hence, the indices are described by a quadratic function). double hashing in which the interval between probes is fixed for each record but is computed by another hash function.
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i. 9679, 1989, 4199 hash to the same value ii. 1471, 6171 hash to the same value iii. All elements hash to the same value iv. Each element hashes to a different value
Hash function given is mod(10).
9679, 1989 and 4199 all these give same hash value i.e 9
1471 and 6171 give hash value 1
Which of the following statement(s) is TRUE?
Hash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes : Statement 1 is correct Yes, it is possible that a Hash Function maps a value to a same location in the memmory that's why collision occurs and we have different technique to handle this problem : Statement 3 is coorect. eg : we have hash function, h(x) = x mod 3 Acc to Statement 1, no matter what the value of 'x' is h(x) results in a fixed mapping location. Acc. to Statement 3, h(x) can result in same mapping mapping location for different value of 'x' e.g. if x = 4 or x = 7 , h(x) = 1 in both the cases, although collision occurs.
61 videos7 docs165 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
61 videos7 docs165 tests








