1
Numerical

### GATE CSE 2016 Set 2

A file system uses an in-memory cache to cache disk blocks. The miss rate of the cache is shown in the figure. The latency to read a block from the cache is $1$ $ms$ and to read a block from the disk is $10$ $ms.$ Assume that the cost of checking whether a block exists in the cache is negligible. Available cache sizes are in multiples of $10$ $MB.$

The smallest cache size required to ensure an average read latency of less than $6$ $ms$ is _________ $MB.$

2
Numerical

### GATE CSE 2016 Set 2

Breadth First Search $(BFS)$ is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If t is the $n$-th vertex in this $BFS$ traversal, then the maximum possible value of $n$ is ___________.

3

### GATE CSE 2016 Set 2

$N$ items are stored in a sorted doubly linked list. For a $delete$ operation, a pointer is provided to the record to be deleted. For a $decrease$-$key$ operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order:
$\Theta \left( N \right),\,\,delete,\,\,O\left( {\log N} \right)\,insert,\,$ $\,O\left( {\log N} \right)\,fund, and$ $\Theta \left( N \right)\,$ $decrease$-$key.$ What is the time complexity of all these operations put together?

A
$O\left( {{{\log }^2}N} \right)$
B
$O\left( N \right)$
C
$O\left( {{N^2}} \right)$
D
$\Theta \left( {{N^2}\log N} \right)$
4

### GATE CSE 2016 Set 2

Consider the following $New-order$ strategy for traversing a binary tree:

$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$ Visit the root;
$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$ Visit the right subtree using $New-order;$
$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$ Visit the left subtree using $New-order;$

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:

A
+ - 1 6 7 * 2 ^ 5 - 3 4 *
B
- + 1 * 6 7 ^ 2 - 5 * 3 4
C
- + 1 * 7 6 ^ 2 - 5 * 4 3
D
1 7 6 * + 2 5 4 3 * - ^ - New-order;

### 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