1

### GATE CSE 2016 Set 2

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$ Quicksort runs in $\Theta \left( {{n^2}} \right)$ time
$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,$ Bubblesort runs in $\Theta \left( {{n^2}} \right)$ time
$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,$ Mergesort runs in $\Theta \left( n \right)$ time
$\,\,\,{\rm I}V.\,\,\,\,\,\,\,$ Insertion sort runs in $\Theta \left( n \right)$ time

A
${\rm I}$ and ${\rm II}$ only
B
${\rm I}$ and ${\rm III}$ only
C
${\rm II}$ and ${\rm IV}$ only
D
${\rm I}$ and ${\rm IV}$ only
2

### GATE CSE 2016 Set 2

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
A
B
C
D
neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
3
Numerical

### GATE CSE 2016 Set 2

A complete binary min-heap is made by including each integer in $[1,1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth $0.$ The maximum depth at which integer $9$ can appear is ___________.

4
Numerical

### GATE CSE 2016 Set 2

Let ${A_1},{A_2},{A_3},$ and ${A_4}$ be four matrices of dimensions $10 \times 5,\,\,5 \times 20,\,\,20 \times 10,$ and $10 \times 5,\,$ respectively. The minimum number of scalar multiplications required to find the product ${A_1}{A_2}{A_3}{A_4}$ using the basic matrix multiplication method is ______________.

### Paper Analysis of GATE CSE 2016 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization6
Data Structures5
Database Management System4
Digital Logic3
Discrete Mathematics11
Operating Systems3
Theory of Computation6
General Aptitude10