Algorithm
Q211.
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after second pass of the algorithm is:Q212.
How many comparisons are needed to sort an array of length 5 if a straight selection sort is used and array is already in the opposite order?Q214.
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 ?Q215.
Let G=(V,E) be a directed, weighed graph with weight function w:E\rightarrow \mathbb{R}. For some function f:V\rightarrow \mathbb{R}, for each edge (u,v) \in E, define w'(u,v) as w(u,v)+f(u)-f(v). Which one of the options completes the following sentence so that it is TRUE? "The shortest paths in G under w are shortest paths under w' too,_________".Q216.
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: (I) Minimum spanning tree of G is always unique. (II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?Q217.
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 isQ218.
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computingQ219.
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change