GATE Solved Paper 2017-19 - GATE 2018

57. The instruction pipeline of a RISC processor has the following stages. Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. assume that there are no data hazards and no control hazards. The number of clock cycles required for completion of execution of the sequence of instructions is ____________.

  • Option : A
  • Explanation :
    Given, total number of instructions (n) = 100
    Number of stages (k) = 5
    Since, if n instructions take c cycle, so (c-1) stalls will occur for these instructions.
    Therefore, the number of clock cycles required = Total number of cycles required in general case + Extra cycles required (here, in PO stage)
    = (n + k – 1) + Extra cycles
    = (100 + 5 -1) + 40*(3-1)+35*(2-1)+20*(1-1)
    = (100 + 4) + 40*2+35*1+20*0
    = 104 + 115
    = 219 cycles
Cancel reply
Cancel reply

58. Let G be a graph with 100! Vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G and z denote the number of connected components in G.
Then, y + 10z = _________.

  • Option : B
  • Explanation :
    The graph has 100! Vertices which each vertex labeled by one of the 100! Permutation.
    take a vertex whose labeling is say 1,2,3,4, …..,100.
    Now it will be connected to all vertices where exactly 2 of the adjacent numbers all swapped.
    The two swapped numbers could be (1, 2), (2, 3), (3, 4) …. etc. upto (99, 100) which makes for 99 edges for each such vertex.
    So the graph is a regular graph with each vertex connected to 99 other vertices.
    So y = 99
    The number of connected components = z = 1 since we can go from any vertex to any other vertex by only swapping 2 adjacent number at a time, many times i.e. there is a path from any vertex to any other vertex.
    Graph is connected.
    So z = 1
    So y + 10z = 99 + 10 x 1 = 109
Cancel reply
Cancel reply

59. Given a language L, define Li as follows:

Li = Li-1∙L for all i>0
The order of a language L is defined as the smallest k such that Lk=Lk+1. Consider the language L1 (over alphabet 0) accepted by the following automaton.

The order of is ___________.

Note – Numerical Type question

  • Option : A
  • Explanation :
    We need to find smallest value of k which satisfies
    L1k = L1k+1

    L1 = ε + (00)
    Try k = 0; L10 = L11
    ε = L1 which is false.
    So order is not 0.
    Try k = 1: L11 = L12
    L12 = L1 Now, L12 =(ε + 0(00)*)(ε + 0(00)*)
    = ε + 0(00)* + 00(00)* = 0*
    Clearly L12 ≠ L1
    So order is not 1.
    Try k = 2: L12 = L13
    Now, L13 = L12.L1
    = 0*(ε + 0(00)*) = 0*
    Clearly L13 = L12=0*
    (so, order of L1 is 2)
Cancel reply
Cancel reply

60. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _______.

  • Option : A
  • Explanation :
    T(N) =(N-1)Ck * T(k) * T(N-k-1), where k = number of nodes on left subtree
    T(1) = 1
    T(2) = 1
    T(3) = 2
    T(4) = 3C2 * T(2) * T(1) = 3
    T(5) = 4C3 * T(3) * T(1) = 8
    T(6) = 5C3 * T(3) * T(2) = 20
    T(7) = 5C3 * T(3) * T(3) = 80
Cancel reply
Cancel reply