GATE Solved Paper 2017-19 - GATE 2017 Shift 1

11. The statement (¬p)⇒(¬q) is logically equivalent to which of the statements below?
I. p⇒q
II. q⇒p
III. (¬q)∨p
IV. (¬p)∨q

  • Option : D
  • Explanation :
    Option D.
    (∼p)⇒(∼q)
    ∼(∼p)∨(∼q)
    p∨(∼q)
    (∼q)∨p ----------------> III is True
    q⇒p -----------------> II is True
Cancel reply
Cancel reply

12. Consider the following table:

 AlgorithmsDesign Paradigms
 P. Kruskal i. Divide and conquer
 Q. Quicksort ii. Greedy
 R. Floyd-Warshall iii Dynamic Programming

  • Option : C
  • Explanation :
    Kruskal’s algorithm follows greedy approach in order to find MST of a connected graph. Quick sort follows divide and conquer strategy. Floyd Warshal algorithm is used to find the shortest path between every pair of vertices and it follows dynamic programming strategy.
Cancel reply
Cancel reply

13. A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place.
(I) S can launch a birthday attack to replace m with a fraudulent message.
(II) A third party attacker can launch a birthday attack to replace m with a fraudulent message.
(III) R can launch a birthday attack to replace m with a fraudulent message.
Which of the following are possible security violations?

  • Option : B
  • Explanation :
    First you know what is Birthday attack :
    by Using Birthday Attack, some fraudulent message can be generated which has same hash value and digital signature as the original message.
    I. Instead of intended message, Sender can take some fraudulent message and encrypt it with own private key and then receiver’s public key. This is POSSIBLE. II. Third party don’t have that Private Key to encrypt the message. So this is NOT possible. III. And the same way R also don’t have that Private key to encrypt the message.
    So, the only possibility is – (I) S can launch a birthday attack to replace m with a fraudulent message.
    Option (B) is correct.
Cancel reply
Cancel reply

14. Consider the following grammar.

 P → QRS
 Q → yz|z
 R → w|ε
 S → y

What is FOLLOW (Q)?

  • Option : C
  • Explanation :
    FOLLOW(Q) is FIRST(R) hence
    FIRST (R)={w,ε}
    We add ‘w’ in FOLLOW(Q) and for ϵ we calculate FIRST(S)
    FIRST(S) ={y}
    FOLLOW(Q) is {w,y}
Cancel reply
Cancel reply

15. Threads of a process share

  • Option : D
  • Explanation :
    Threads of a process can share all resources except stack and register set.
Cancel reply
Cancel reply