GATE CSE 2006
Q1.
Given two arrays of numbers a_{1},...,a_{n} and b_{1},...,b_{n} where each number is 0 or 1, the fastest algorithm to find the largest span(i,j) such that a_{i}+a_{i+1}+...+a_{j}=b_{i}+b_{i+1}+.....+b_{j} , or report that there is no such span,Q2.
An element in an array X is called a leader if it is grater than all elements to the right of it in X. The best algorithm to find all leaders in an array.Q3.
Consider the following C-program fragment in which i, j,and n are integer variables. for (i = n, j = 0; i > 0; i/=2, j += i); Let Val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?Q4.
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The roots is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i + 1]. To be able to store any binary tree on n vertices, the minimum size of X should beQ5.
Let L_{1}=\{0^{n+m}1^{n}0^{m}|n,m\geq 0\} L_{2}=\{0^{n+m}1^{n+m}0^{m}|n,m\geq 0\} L_{3}=\{0^{n+m}1^{n+m}0^{n+m}|n,m\geq 0\} Which of these languages are NOT context free?Q6.
Consider the following statements about the context-free grammer G=\{S\rightarrow SS, S\rightarrow ab, S\rightarrow ba, S\rightarrow \varepsilon \} 1. G is ambiguous 2. G produces all strings with equal number of a's and b's 3. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?Q7.
Consider the following snapshot of a system running n processes. Process i is holding x_{i} instances of a resource R, for 1\leq i\leq n. Currently, all instances of R are occupied. Further, for all i , process i has placed a request for an additional y_{i}, instances while holding the x_{i} instances it already has, There are exactly two processes p and q such that y_{p}=y_{q}=0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?Q8.
Let T be a depth first search tree in a undirected graph G Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?Q9.
The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?Q10.
In a binary max heap containing n numbers, the smallest element can be found in time