Locality of reference implies that the page reference being made by a process
A) will always be to the page used in the previous page reference
B) is likely to be to one of the pages used in the last few page references
C) will always be to one of the pages existing in memory
D) will always lead to a page fault
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?
B) O(n Log n)
In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?
A) ? (n2)
B) ? (n log n)
C) ? (n1.5)
D) ? (n)
Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?
A) Every minimum spanning tree of G must contain emin
B) If emax is in a minimum spanning tree, then its removal must disconnect G
C) No minimum spanning tree contains emax
D) G has a unique minimum spanning tree
"The Forum is to encourage students discussions. If you expect our mentors to resolve your doubts/queries please reach out to us by posting comments under the video lectures or sending us a mail on firstname.lastname@example.org. Our mentors will get back to you in 3-4 working hours."