# Recent activity by rawan

1
Let $A$ be an array of $31$ numbers consisting of a sequence of $0$'s followed by a sequence of $1$'s. The problem is to find the smallest index $i$ such that $A\left [i \right ]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ____________.
2
Consider the following deterministic finite state automaton $M$. Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is $1$ $5$ $7$ $8$
3
Consider the following relational database schemes: COURSES (Cno, Name) PRE_REQ(Cno, Pre_Cno) COMPLETED (Student_no, Cno) COURSES gives the number and name of all the available courses. PRE_REQ gives the information about which courses are pre-requisites for a ... following using relational algebra: List all the courses for which a student with Student_no 2310 has completed all the pre-requisites.
4
Construct a DAG for the following set of quadruples: E:=A+B F:=E-C G:=F*D H:=A+B I:=I-C J:=I+G
5
Complete the following production rules which generate the language:$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$ where variables $R$ and $Q$ are used to move back and forth over the current string generated $S \rightarrow aYc$ $Y \rightarrow a Yc\mid Q$ ... $Qc \rightarrow cQ$ $Q \rightarrow R'c$ $cR' \rightarrow ...$ $bR' \rightarrow ...$ $aR' \rightarrow a...$
6
Consider the following problem. Given $n$ positive integers $a_{1}, a_{2}\dots a_n,$ it is required to partition them in to two parts $A$ and $B$ such that $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}|$ is minimised Consider a greedy algorithm ... in that part whose sum in smaller at that step. Give an example with $n=5$ for which the solution produced by the greedy algorithm is not optimal.
7
The following algorithm (written in pseudo-pascal) work on an undirected graph G program Explore (G) procedure Visit (u) begin if Adj (u) is not empty {comment:Adj (u) is the list of edges incident to u} then begin Select an edge from Adj (u); Let edge ... edges, given that each vertex can be accessed and removed from LIST in constant time. Also show that all edges of the graph are traversed.
8
Consider the following grammars. Names representing terminals have been specified in capital letters. $\begin{array}{llll}\hline \text{$G1$:} & \text{stmnt} & \text{$\rightarrow$} & \text{WHILE (expr) stmnt} \\%\hline \text{} & \text{stmnt} & \text{$ ... regular and $G_1$ is regular Both $G_1$ and $G_2$ are regular Both $G_1$ and $G_2$ are context-free but neither of them is regular
9
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
10
We consider the addition of two $2's$ complement numbers $b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out by $c_{out}$ ... $c_{out}\oplus c_{n-1}$ $a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$
11
Consider the following statements about the context free grammar $G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \}$ $G$ is ambiguous $G$ produces all strings with equal number of $a$'s and $b$'s $G$ can ... deterministic PDA. Which combination below expresses all the true statements about $G$? I only I and III only II and III only I, II and III
12
Q- Which one of following languages is inherently ambiguous? (A) The set of all strings of the form $\left\{a^nb^n,n>0 \right\}$ (B) $\left\{a^nb^nc^md^m,n,m>0 \right\}$ (C) $\left\{a^nb^nc^md^m,n,m>0 \right\}\;\cup \;\left\{a^nb^mc^md^n,n,m>0 \right\}$ (D) Both (B) and (C) Plz explain.. ..........Is there any criteria on the basis of which we could identify inherently ambiguous grammar
13
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are $2048$ and the head can start from any track? $9$ $10$ $11$ $12$
14
A relation $R$ is defined on ordered pairs of integers as follows: $(x,y)R(u,v) \text{ if } x<u \text{ and } y>v$ Then R is: Neither a Partial Order nor an Equivalence Relation A Partial Order but not a Total Order A total Order An Equivalence Relation
15
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$. $5$ $6$ $7$ $10$
16
Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ is always regular never regular always a deterministic context-free language always a context-free language
17
Consider the following first order logic formula in which $R$ is a binary relation symbol. $∀x∀y (R(x, y) \implies R(y, x))$ The formula is satisfiable and valid satisfiable and so is its negation unsatisfiable but its negation is valid satisfiable but its negation is unsatisfiable
18
In a binary tree, the number of internal nodes of degree $1$ is $5$, and the number of internal nodes of degree $2$ is $10$. The number of leaf nodes in the binary tree is $10$ $11$ $12$ $15$
19
A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is $5, 3, 1, 2, 4, 6, 8, 7.$ If the tree is traversed in post-order, the sequence obtained would be $8, 7, 6, 5, 4, 3, 2, 1$ $1, 2, 3, 4, 8, 7, 6, 5$ $2, 1, 4, 3, 6, 7, 8, 5$ $2, 1, 4, 3, 7, 8, 6, 5$
20
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h > 0$, then the minimum number of nodes in the tree is $2^{h-1}$ $2^{h-1} + 1$ $2^h - 1$ $2^h$
21
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is $3$ $4$ $5$ $6$
22
A dynamic RAM has a memory cycle time of $64$ $\text{nsec}$. It has to be refreshed $100$ times per msec and each refresh takes $100$ $\text{nsec}$ . What percentage of the memory cycle time is used for refreshing? $10$ $6.4$ $1$ $0.64$
23
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ ... that $xy \notin L(G)$ There is a deterministic pushdown automaton that accepts $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$
24
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end of the ... gives maximum profit? All tasks are completed $T_1$ and $T_6$ are left out $T_1$ and $T_8$ are left out $T_4$ and $T_6$ are left out
25
For example, is there a way to calculate the value of $(7 \times 11 \times 13 \times 17) \% 5$ in terms of the values of $7\%5, 11\%5, 13\%5,$ and $17\%5$ ?
26
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one ... minimum weighted spanning tree a weighted shortest path from $s$ to $t$ an Euler walk from $s$ to $t$ a Hamiltonian path from $s$ to $t$
Let $G(x) = \frac{1}{(1-x)^2} = \sum\limits_{i=0}^\infty g(i)x^i$, where $|x| < 1$. What is $g(i)$? $i$ $i+1$ $2i$ $2^i$
Let $R$ and $S$ be any two equivalence relations on a non-empty set $A$. Which one of the following statements is TRUE? $R$ $∪$ $S$, $R$ $∩$ $S$ are both equivalence relations $R$ $∪$ $S$ is an equivalence relation $R$ $∩$ $S$ is an equivalence relation Neither $R$ $∪$ $S$ nor $R$ $∩$ $S$ are equivalence relations
Let $A, B$ and $C$ be non-empty sets and let $X = ( A - B ) - C$ and $Y = ( A - C ) - ( B - C ).$ Which one of the following is TRUE? $X = Y$ $X ⊂ Y$ $Y ⊂ X$ None of these