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?

- a)Insertion Sort with time complexity O(kn)
- b)Heap Sort with time complexity O(nLogk)
- c)Quick Sort with time complexity O(kLogk)
- d)Merge Sort with time complexity O(kLogk)

Correct answer is option 'B'. Can you explain this answer?

Gate Gurus answered • 7 hours ago

1) to sort the array firstly create a min-heap 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 min-heap(extract min) and put it in the result array.

4) Now,insert another element from the unsorted array into the mean-heap, 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 min-heap 2) O((n-k)logk) for remaining elements... 3) 0(1) for extract min so overall O(k) + O((n-k)logk) + 0(1) = O(nlogk)

Consider a fully associative cache with 8 cache blocks (numbered 0-7) and the following sequence of memory block requests: 4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7 If LRU replacement policy is used, which cache block will have memory block 7?

- a)4
- b)5
- c)6
- d)7

Correct answer is option 'B'. Can you explain this answer?

Gate Gurus answered • 19 hours ago

Block size is =8 Given 4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7 So from 0 to 7 ,we have

4 3 25 8 19 6 16 35 //25,8 LRU so next 16,35 come in the block.

45 3 25 8 19 6 16 35

45 22 25 8 19 6 16 35

45 22 25 8 19 6 16 35

45 22 25 8 3 6 16 35 //16 and 25 already there

45 22 25 8 3 7 16 35 //7 in 5th block Therefore , answer is B

4 3 25 8 19 6 16 35 //25,8 LRU so next 16,35 come in the block.

45 3 25 8 19 6 16 35

45 22 25 8 19 6 16 35

45 22 25 8 19 6 16 35

45 22 25 8 3 6 16 35 //16 and 25 already there

45 22 25 8 3 7 16 35 //7 in 5th block Therefore , answer is B

Consider a computer system with ten physical page frames. The system is provided with an access sequence a1, a2, ..., a20, a1, a2, ..., a20), where each ai number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is __________ [Note that this question was originally Fill-in-the-Blanks question]

- a)0
- b)1
- c)2
- d)3

Correct answer is option 'B'. Can you explain this answer?

Cstoppers Instructors answered • 19 hours ago

LIFO stands for last in, first out a1 to a10 will result in page faults, So 10 page faults from a1 to a10. Then a11 will replace a10(last in is a10), a12 will replace a11 and so on till a20, so 10 page faults from a11 to a20 and a20 will be top of stack and a9…a1 are remained as such. Then a1 to a9 are already there. So 0 page faults from a1 to a9. a10 will replace a20, a11 will replace a10 and so on. So 11 page faults from a10 to a20. So total faults will be 10+10+11 = 31. Optimal a1 to a10 will result in page faults, So 10 page faults from a1 to a10. Then a11 will replace a10 because among a1 to a10, a10 will be used later, a12 will replace a11 and so on. So 10 page faults from a11 to a20 and a20 will be top of stack and a9…a1 are remained as such. Then a1 to a9 are already there. So 0 page faults from a1 to a9. a10 will replace a1 because it will not be used afterwards and so on, a10 to a19 will have 10 page faults. a20 is already there, so no page fault for a20. Total faults 10+10+10 = 30. Difference = 1

Which of the following is not a form of memory?

- a)instruction cache
- b)instruction register
- c)instruction opcode
- d)translation lookaside buffer

Correct answer is option 'C'. Can you explain this answer?

Gate Gurus answered • 19 hours ago

Instruction Cache - Used for storing instructions that are frequently used Instruction Register - Part of CPU's control unit that stores the instruction currently being executed Instruction Opcode - It is the portion of a machine language instruction that specifies the operation to be performed Translation Lookaside Buffer - It is a memory cache that stores recent translations of virtual memory to physical addresses for faster access. So, all the above except Instruction Opcode are memories. Thus, C is the correct choice. Please comment below if you find anything wrong in the above post.

Mrudul Addipalli asked • 28 minutes ago

A function f(x) is continuous in the interval [0,2]. It is known that f(0) = f(2) = -1 and f(1) =1 . which one of the following statemnts must be true?

- a)There exists a y in the interval (0,1) such that f(y)= f(y+1)
- b)for every y in the interval (0,1), f(2) = f(2-y)
- c)The maximum value of the function in the interval (0,2) is 1
- d)There exists a y in the interval (0,1) such that f(y) = -f(2-y)

Correct answer is option 'A'. Can you explain this answer?

Which of the following is correct recurrence for worst case of Binary Search?

- a)T(n) = 2T(n/2) + O(1) and T(1) = T(0) = O(1)
- b)T(n) = T(n-1) + O(1) and T(1) = T(0) = O(1)
- c)T(n) = T(n/2) + O(1) and T(1) = T(0) = O(1)
- d)T(n) = T(n-2) + O(1) and T(1) = T(0) = O(1)

Correct answer is option 'C'. Can you explain this answer?

Cstoppers Instructors answered • 19 hours ago

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)

If LRU and Geek page replacement are compared (in terms of page faults) only for above reference string then find the correct statement from the following:

- a)LRU and Geek are same
- b)LRU is better than Geek
- c)Geek is better than LRU
- d)None

Correct answer is option 'C'. Can you explain this answer?

Cstoppers Instructors answered • 19 hours ago

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

- a)Assembly
- b)Parsing
- c)Relocation
- d)Symbol resolution

Correct answer is option 'C'. Can you explain this answer?

Cstoppers Instructors answered • 19 hours ago

Relocation of code is the process done by the linker-loader when a program is copied from external storage into main memory.

A linker relocates the code by searching files and libraries to replace symbolic references of libraries with actual usable addresses in memory before running a program.

Thus, option (C) is the answer.

A linker relocates the code by searching files and libraries to replace symbolic references of libraries with actual usable addresses in memory before running a program.

Thus, option (C) is the answer.

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]

- a)list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4]
- b)list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6
- c)list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 3 ^ 4 ^ 5
- d)~(list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4])

Correct answer is option 'B'. Can you explain this answer?

Cstoppers Instructors answered • 19 hours ago

XOR of all list elements and numbers from 1 to 6 gives the missing number.

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.

- a)O(n^2 Logn)
- b)O(n^2)
- c)O(n Logn Logn)
- d)O(nLogn)

Correct answer is option 'D'. Can you explain this answer?

Cstoppers Instructors answered • 19 hours ago

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.

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?

- a)10
- b)20
- c)30
- d)40

Correct answer is option 'C'. Can you explain this answer?

Cstoppers Instructors answered • 19 hours ago

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.

Which of the following statement(s) is TRUE?

- A hash function takes a message of arbitrary length and generates a fixed length code.
- A hash function takes a message of fixed length and generates a code of variable length.
- A hash function may give the same hash value for distinct messages.

- a)I only
- b)II and III only
- c)I and III only
- d)II only

Correct answer is option 'C'. Can you explain this answer?

Machine Experts answered • 19 hours ago

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.

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.

- a)O(LogLogn)
- b)O(n)
- c)O(Logn)
- d)O(Logn * Logn)

Correct answer is option 'C'. Can you explain this answer?

Machine Experts answered • 19 hours ago

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[mid-1...high] */ else { if(mid - 1 >= low && x > arr[mid-1]) 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, n-1, 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]

Rasazna Kls asked • 1 hour ago

A priority queue can efficiently implemented using which of the following data structures? Assume that the number of insert and peek (operation to see the current highest priority item) and extraction (remove the highest priority item) operations are almost same.

- a)Array
- b)Linked List
- c)Heap Data Structures like Binary Heap, Fibonacci Heap
- d)None of the above

Correct answer is option 'C'. Can you explain this answer?

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

- a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
- b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
- c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
- d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

Correct answer is option 'B'. Can you explain this answer?

Machine Experts answered • 19 hours ago

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 (n-1). So recurrence is T(n) = T(n-1) + T(0) + O(n) The above expression can be rewritten as T(n) = T(n-1) + 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]

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

- a)i only
- b)ii only
- c)i and ii only
- d)iii or iv

Correct answer is option 'C'. Can you explain this answer?

Machine Experts answered • 19 hours ago

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

9679, 1989 and 4199 all these give same hash value i.e 9

1471 and 6171 give hash value 1

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

- a)Quick Sort
- b)Heap Sort
- c)Merge Sort
- d)Insertion Sort

Correct answer is option 'D'. Can you explain this answer?

Machine Experts answered • 19 hours ago

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.

Virat Kohli asked • 2 hours ago

Which of the following is true about merge sort?

- a)Merge Sort works better than quick sort if data is accessed from slow sequential memory.
- b)Merge Sort is stable sort by nature
- c)Merge sort outperforms heap sort in most of the practical situations.
- d)All of the above.

Correct answer is option 'D'. Can you explain this answer?

Manikant Sharma asked • 2 hours ago

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z_{0}, X} where Z_{0} is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ_{0}) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z_{0} and X (in that order) on the stack.

Pooja Daphal asked • 2 hours ago

A computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The

processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in

addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit.

processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in

addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit.

- a)160 Kbits
- b)136 Kbits
- c)40 Kbits
- d)32 Kbits

Correct answer is option 'A'. Can you explain this answer?

Javed Ahmad asked • 2 hours ago

Which of the following is not true about comparison based sorting algorithms?

- a)The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array
- b)Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared
- c)Counting Sort is not a comparison based sorting algortihm
- d)Heap Sort is not a comparison based sorting algorithm

Correct answer is option 'D'. Can you explain this answer?

Gaurav Kumar asked • 3 hours ago

An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-diagonal elements are 1‘s. which one of the following is TRUE?

- a)Graph G has no minimum spanning tree (MST)
- b)Graph G has a unique MST of cost n-1
- c)Graph G has multiple distinct MSTs, each of cost n-1
- d)Graph G has multiple spanning trees of different costs

Correct answer is option 'C'. Can you explain this answer?

Navya Nalamasa asked • 3 hours ago

- a)A serializable schedule
- b)A schedule that is not conflict serializable
- c)A conflict serializable schedule
- d)A schedule for which a precedence graph cannot be drawn

Correct answer is option 'B'. Can you explain this answer?

Jnani Kurmadasu asked • 4 hours ago

the following logical formulae represents the above statement?

- a)
^{} - b)
- c)
- d)

Correct answer is option 'D'. Can you explain this answer?

Nisi Gupta asked • 7 hours ago

Consider six memory partitions of size 200 KB, 400 KB, 600 KB, 500 KB, 300 KB, and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?

Correct answer is between '200 KB,300 KB'. Can you explain this answer?

Shruti Kumari asked • 7 hours ago

Kavya Basavaraj asked • 7 hours ago

The probabilities that a student passes in Mathematics, Physics and Chemistry are m, p, and c respectively

. Of these subjects, the student has 75% chance of passing in atleast one, a 50% chance of passing in atleast two and a 40% chance of passing in exactly two. Following relation are drawn in m, p, c.

I. p + m + c = 27/20

II. p + m + c = 13/20

III. (p)+(m)+(C)= 1/10

- a)only relation I is true
- b)only relation II is true
- c)relations II and III are true
- d)relations I and iii are true

Correct answer is option 'D'. Can you explain this answer?

Tarun Kumar asked • 7 hours ago

The correct matching for the following pairs is:

(A) DMA I/O (1) High speed RAM

(B) Cache (2) Disk

(C) Interrupt I/O (3) Printer

(D) Condition Code Register (4) ALU

(A) DMA I/O (1) High speed RAM

(B) Cache (2) Disk

(C) Interrupt I/O (3) Printer

(D) Condition Code Register (4) ALU

- a)A-4 B-3 C-1 D-2
- b)A-2 B-1 C-3 D-4
- c)A-4 B-3 C-2 D-1
- d)A-2 B-3 C-4 D-1

Correct answer is option 'B'. Can you explain this answer?

Neha Prajaapati asked • 8 hours ago

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

- a)Leftmost derivation
- b)Leftmost derivation traced out in reverse
- c)Rightmost derivation
- d)Rightmost derivation traced out in reverse

Correct answer is option 'A'. Can you explain this answer?

Damayanti Daule asked • 9 hours ago

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a

given graph. In this scenario, which one of the following represents the correct Venn diagram of the

complexity classes P, NP and NP Complete (NPC)?

given graph. In this scenario, which one of the following represents the correct Venn diagram of the

complexity classes P, NP and NP Complete (NPC)?

- a)
- b)
- c)
- d)

Correct answer is option 'D'. Can you explain this answer?

Adepu Veena asked • 9 hours ago

The temporal aspect of the locality of reference means

- a)That the recently executed instruction wont be executed soon
- b)That the recently executed instruction is temporarily not referenced
- c)That the recently executed instruction will be executed soon again
- d)None of the mentioned

Correct answer is option 'C'. Can you explain this answer?

Apurva Patel asked • 11 hours ago

Consider the relation "enrolled(student, course)" in which (student, course) is the primary key, and the relation "paid(student, amount)" where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Given the following four queries:

- a)All queries return identical row sets for any database
- b)Query2 and Query4 return identical row sets for all databases but there exist databases for which Query1 and Query2 return different row sets.
- c)There exist databases for which Query3 returns strictly fewer rows than Query2
- d)There exist databases for which Query4 will encounter an integrity violation at runtime.

Correct answer is option 'B'. Can you explain this answer?

AMAN RAJ asked • 12 hours ago

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

- a)Ω(log n)
- b)Ω(n)
- c)Ω(n log n)
- d)Ω(n
^{2})

Correct answer is option 'A'. Can you explain this answer?

Puja Kunwar Kunwar asked • 13 hours ago

Satish Gaikwad asked • 15 hours ago

Consider the following pseudo code. What is the total number of multiplications to be performed?

- a)Half of the product of the 3 consecutive integers.
- b)One-third of the product of the 3 consecutive integers.
- c)One-sixth of the product of the 3 consecutive integers.
- d)None of the above.

Correct answer is option 'C'. Can you explain this answer?

Ambati Rajendra asked • 15 hours ago

How is a privilege exception dealt with?

- a)The program is alted and the system switches into supervisor mode and restarts the program execution
- b)The Program is stopped and removed from the queue
- c)The system switches the mode and starts the execution of a new process
- d)The system switches mode and runs the debugger

Correct answer is option 'A'. Can you explain this answer?

Apurva Patel asked • 15 hours ago

Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array {12, -13, -5, 25, -20, 30, 10}, the maximum subarray sum is 45. The naive solution for this problem is to calculate sum of all subarrays starting with every element and return the maximum of all. We can solve this using Divide and Conquer, what will be the worst case time complexity using Divide and Conquer.

- a)O(n)
- b)O(nLogn)
- c)O(Logn)
- d)O(n^2)

Correct answer is option 'B'. Can you explain this answer?

Shweta Sonkar asked • 16 hours ago

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?

- a)Insertion Sort with time complexity O(kn)
- b)Heap Sort with time complexity O(nLogk)
- c)Quick Sort with time complexity O(kLogk)
- d)Merge Sort with time complexity O(kLogk)

Correct answer is option 'B'. Can you explain this answer?

Kajal R Patil asked • 19 hours ago

"We lived in culture and denied any merit to literally works, Considering them important only when they were handmaidens to something seemingly more urgent - namely ideology. This was a country where all gestures even the most private , interpreted as political terms." The author's believes that ideology is not as important as literature is revealed by the word :

- a)culture
- b)seemingly
- c)urgent
- d)political

Correct answer is option 'B'. Can you explain this answer?

Lohit Jindal asked • 19 hours ago

Fetching relevant content for you

Ask a question