GATE 2022 Toppers Quiz 28

What will be the time complexity of the below program?

Consider the following, five binary string each of length 8 bits:
11111011, 01101010, 01010010, 11011011, 10011010
A hash table of size S = 8 (0 to 7) using open addressing for hashing the binary strings. Assume finding an empty slot is a successful probe, while non-empty is a unsuccessful probe. The total number of unsuccessful probes needed using linear probing to hash all strings are ________.

Consider two binary operator ‘+’ and ‘–’ with the precedence of ‘+’ being lower than that of operator ‘–’. Operator ‘–’ is right associative while operator ‘+’ to left associative. Which one of the following represents the parse tree for expression (5 + 2 – 7 + 3 – 4)

Consider a push down automata (PDA) below which runs over the input alphabet (a, b). It has the stack alphabet {z₀, X} where z₀ is the bottom of stack marker. The set of states of PDA is {q₀, q₁} where q₀ is the start state and final state.

δ{q₀, b, z₀} = {(q₀, Xz₀)}

δ{q₀, b, X} = {(q₀, XX)}

δ{q₀, a, X} = {(q₁, X)}

δ{q₀, ϵ, z₀} = {(q₀, ϵ)}

δ{q₀, b, X} = {(q₁, ϵ)}

δ{q₁, a, z₀} = {(q₀, z₀)}

The language accepted by PDA is

Consider the size of congestion window of a TCP connection be 36 KB when a timeout occurs. The RTT for the connection is 200 microseconds and the maximum segment size is 2KB. What is the time taken by the TCP connection to get back to 36 KB congestion window ?

Number of the grammars which is/are ambiguous?

I. S→0S1|01

II. S→+SS|−SS | a

III. S→S(S)S|ϵ

IV. S→aSbS | bSaS | ϵ

What will be the 10’s complement of (715)base 8 is