GATE CSE 2003
Q41.
Let S be a stack of size n \geq 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each , and Y seconds elapse between the end of the one such stack operation and the start of the next operation. For m \geq 1, define the stack-life of m as the time elapsed from the end or Push (m) to the start of the pop operation that removes m from S . The average stack-life of an element of this stack isQ42.
Which of the following scenarios may lead to an irrecoverable error in a database system?Q43.
Consider three data items D1,D2 and D3 and the following execution schedule of transactions T1,T2 and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D respectively. Which of the following statements is correct?Q44.
Which of the following functionalities must be implemented by a transport protocol over and above the network protocol ?Q45.
Consider two languages L1 and L2 each on the alphabet \Sigma. Let f:\Sigma \rightarrow \Sigma be a polynomial time computable bijection such that (\forall x)[x \in L1 \; \; if \; \; f(x) \in L2]. Further, let f^{-1} be also polynomial time computable. Which of the following CANNOT be true?Q46.
Define languages L0 and L1 as follows : L0 = {< M, w, 0 > | M halts on w} L1 = {< M, w, 1 > | M does not halts on w} Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L=L0 \cup L1. Which of the following is true ?Q47.
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?Q48.
A 1-input, 2-output synchronous sequential circuit behaves as follows. Let z_{k},n_{k} denote the number of 0's and 1's respectively in initial k bits of the input ( z_{k}+n_{k}=k ). The circuit outputs 00 until one of the following conditions holds. 1. z_{k}-n_{k}=2. In this case, the output at the k -th and all subsequency clock ticks is 10. 2. n_{k}-z_{k}=2. In this case, the output at the k -th and all subsequent clock ticks is 01. What in the minimum number of states required in the state transition graph of the above circuit?