Consider the following table
Match the algorithm to design paradigms they are based on:
Algorithms
GATE 2017 SET 1
Consider the C code fragment given below.
typedef struct node
{
int data;
node* next ;
} node;
void join(node* m, node* n)
{
node* p = n;
while (p->next != NULL)
{
p = p->next;
}
p–>next = m;
}
Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will
append list m to the end of list n for all inputs
either cause a null pointer dereference or append list m to the end of list n
cause a null pointer dereference for all inputs
append list n to the end of list m for all inputs.
Data Structures
GATE 2017 SET 1
Linked-List
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any 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?
Algorithms
GATE 2017 SET 1
Minimum-Spanning-Tree
In a RSA cryptosystem a particular A uses two prime numbers p = 13 and q =17 to generate her public and private keys. If the public key of Ais 35. Then the private key of A is ____________.
Computer Networks
GATE 2017 SET 1
The values of parameters for the Stop-and – Wait ARQ protocol are as given below.
Bit rate of the transmission channel = 1Mbps
Propagation delay from sender to receiver = 0.75 ms
Time to process a frame = 0.25ms
Number of bytes in the information frame = 1980
Number of bytes in the acknowledge frame = 20
Number of overhead bytes in the information frame = 20
Assume that there are no transmission errors. Then the transmission efficiency ( expressed in percentage) of the Stop-and – Wait ARQ protocol for the above parameters is _________( correct to 2 decimal place) .
Computer Networks
GATE 2017 SET 1
Consider a 2-way set associative cache with 256 blocks and uses LRU replacement, Initially the cache is empty. Conflict misses are those misses which occur due the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of accesses to memory blocks
(0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129)
is repeated 10 times. The number of conflict misses experienced by the cache is ___________.
computer organization
GATE 2017 SET 1
A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ______ bits.
computer organization
GATE 2017 SET 1
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________.
Algorithms
GATE 2017 SET 1
Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below.
The following query is made on the database.
T1 ← πCourseName(σStudentName=’SA’(CR))
T2 ← CR ÷ T1
The number of rows in T2 is ________.
DBMS
GATE 2017 SET 1
Instruction execution in a processor is divided into 5 stages. Instruction Fetch(IF), Instruction Decode (ID), Operand Fetch(OF), Execute(EX), and Write Back(WB), These stages take 5,4,20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementations of the processor are contemplated:
(i) a naïve pipeline implementation (NP) with 5 stages and
(ii) an efficient pipeline (EP) where the OF stage id divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.
The speedup (correct to two decimals places) achieved by EP over NP in executing 20 independent instructions with no hazards is ________________.
computer organization
GATE 2017 SET 1
Match the algorithms with their time complexities:
P-> (iii), Q -> (iv), R -> (i), S -> (ii)
P-> (iv), Q -> (iii), R -> (i), S -> (ii)
P-> (iii), Q -> (iv), R -> (ii), S -> (i)
P-> (iv), Q -> (iii), R -> (ii), S -> (i)
Algorithms
GATE 2017 SET2
Consider the following statements about the routing protocols, Routing Information Protocol(RIP) and Open Shortest Path First(OSPF) in an IPv4 network.
I. RIP uses distance vector routing
II. RIP packets are sent using UDP
III. OSPF packets are sent using TCP
IV. OSPF operation is based on link-state routing
Which of the following above are CORRECT?
Computer Networks
GATE 2017 SET2
The maximum number of IPv4 router address addresses that can be listed in the record route (RR) option field of an IPv4 header is ____.
Computer Networks
GATE 2017 SET2
Consider a socket API on Linux machine that supports UDP socket. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the following statements is/are correct ?
I. A connected UDP socket can be used to communicate
with multiple peers simultaneously.
II. A process can successfully call connect function
again for an already connected UDP socket.
Computer Networks
GATE 2017 SET2
A Circular queue has been implemented using singly linked list where each node consists of a value and a pointer to next node. We maintain exactly two pointers FRONT and REAR pointing to the front node and rear node of queue. Which of the following statements is/are correct for circular queue so that insertion and deletion operations can be performed in O(1) i.e. constant time.
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
Data Structures
GATE 2017 SET2
The read access times and the hit ratios for different caches in a memory hierarchy are as given below:
The read access time of main memory in 90 nanoseconds. Assume that the caches use the referred-word-first read policy and the writeback policy. Assume that all the caches are direct mapped caches. Assume that the dirty bit is always 0 for all the blocks in the caches. In execution of a program, 60% od memory reads are for instruction fetch and 40% are for memory operand fetch. The average read access time in nanoseconds (up to 2 decimal places) is _________
computer organization
GATE 2017 SET2
In a two-level cache system, the access times of L1 and L2 1 and 8 clock cycles, respectively. The miss penalty from the L2 cache to main memory is 18 clock cycles. The miss rate of L1 cache is twice that of L2. The average memory access time(AMAT) of this cache system is 2 cycles. The miss rates of L1 and L2 respectively are:
computer organization
GATE 2017 SET2
Consider a machine with byte addressable memory of 232 bytes divided into blocks of size 32 bytes. Assume a direct mapped cache having 512 cache lines is used with this machine. The size of tag field in bits is _____
computer organization
GATE 2017 SET2
Consider the following database table named top_scorer.
Consider the following SQL query:
SELECT ta.player FROM top_scorer AS ta
WHERE ta.goals > ALL ( SELECT tb.goals
FROM top_scorer AS tb
WHERE tb.country = 'Spain' )
AND ta.goals > ANY (SELECT tc.goals
FROM top_scorer AS tc
WHERE tc.country = 'Germany')
The number of tuples returned by the above SQL query is ____.
GATE 2017 SET2
Algorithms
GATE 2015 SET 1