ALGORITHMS |Gate-2015|
- Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant. [GATE – 2015]
a. T(n) = 2T(n/2) + cn
b. T(n) = T(n – 1) + T(1) + cn
c. T(n) = 2T(n – 1) + cn
d. T(n) = T(n/2) + cn
Answer : b)
- Match the following : [GATE – 2015]
P. Prim’s algorithm for minimum spacing tree i) Backtracking
Q. Floyd-Warshall algorithm for all pairs shortest paths ii) Greedy method
R. Mergesort iii) Dyanamic Programming
S. Hamilton Circuit. iv) Divide and conquer
a. P-iii, Q-ii, R-iv, S-i
b. P-i, Q-ii, R-iv, S-iii
c. P-ii, Q-iii, R-iv, S-i
d. P-ii, Q-i, R-iii, S-iv
Answer : c)
- An algorithm performs (log N)1/2 find operations, N insert operations, (log N)1/2 delete operations, and (log N)1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations? [GATE – 2015]
a. Unsorted array
b. Min-heap
c. Sorted array
d. Sorted doubly linked list
Answer : a)
ALGORITHMS |Gate-2015|
- The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________. [GATE – 2015]
a. 69
b. 70
c. 71
d. 72
Answer : a)
- GIven below are some algorthims, and some algothim design paradigms
1) Dijkstra’s shortest path i) Divide and conquer
2) Floyd-Warshall algorithm for all pairs shortest paths ii) Dyanamic Programming
3) Binary search on a sorted array iii) Greedy Design
4) Backtracking search on a graph iv) Depth- first search
v) Breadth-first search
Match the above given algorithm: [GATE – 2015]
a. 1-i, 2-iii, 3-i, 4-v.
b. 1-iii, 2-iii, 3-i, 4-v.
c. 1-iii, 2-ii, 3-i, 4-iv.
d. 1-iii, 2-ii, 3-i, 4-v.
Answer : c)
- Suppose you are provided with the following function decleration in the C programming language.
int partition (int a[], int n);
The function treat the first element of a [ ] a as pivot, and rearrange the arrays so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is last elements of the left part. The return value is the number of elements in the left part.
The following partially given function in the C programming language is used to find the Kth smallest elements in the array a[ ] of size n using the partition function We assume k<= n.
int kth_smallest (int a[ ] , int n , int k)
{
int left_end = partition (a,n);
if(left_end+1 = = k)
{
return a[left_end];
}
if(left_end+1 >k )
{
return kth_smallest (_______________);
}
else
{
return Kth_smallest (______________);
}
}
The missing arguments lists are respectively. [GATE – 2015]
a. (a, left_end, k) and (a + left_end + 1, n – left_end – 1, k – left_end – 1)
b. (a, left_end, k) and (a, n – left_end – 1, k – left_end – 1)
c. (a + left_end + 1, n – left_end – 1, k – left_end – 1) and (a, left_end, k)
d. (a, n – left_end – 1, k – left_end – 1) and (a, left_end, k)
Answer : a)
- Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50×106 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller’s transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512-byte sector of the disk is _____________. [GATE – 2015]
a. 6
b. 6.1
c. 6.2
d. 6.3
Answer : b)
ALGORITHMS |Gate-2015|
- Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes? [GATE – 2015]
a. 256
b. 512
c. 1024
d. 2048
Answer : b)
- Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes __________. [GATE – 2015]
a. 995
b. 996
c. 997
d. 998
Answer : a)