# Recent questions tagged tifr2011

1
Consider the class of object oriented languages. Which of the following is true? Pascal is an object oriented language. Object oriented languages require heap management. Object oriented languages cannot be implemented in language C. Object oriented languages are more powerful than declarative programming languages. Parallelism cannot be realized in object oriented languages.
2
The first $n$ cells of an array $L$ contain positive integers sorted in decreasing order, and the remaining $m - n$ cells all contain 0. Then, given an integer $x$, in how many comparisons can one find the position of $x$ in $L$? At least $n$ comparisons are necessary in the ... . $O (\log (m - n))$ comparisons suffice. $O (\log n)$ comparisons suffice. $O (\log (m / n))$ comparisons suffice.
3
Consider the class of recursive and iterative programs. Which of the following is false? Recursive programs are more powerful than iterative programs. For every iterative program there is an equivalent recursive program. Recursive programs require dynamic memory management. Recursive programs do not terminate sometimes. Iterative programs and recursive programs are equally expressive.
4
Given an integer $n\geq 3$, consider the problem of determining if there exist integers $a,b\geq 2$ such that $n=a^{b}$. Call this the forward problem. The reverse problem is: given $a$ and $b$, compute $a^{b}$ (mod b). Note that the input length ... can be solved in polynomial time, however the forward problem is $NP$-hard. Both the forward and reverse problem are $NP$-hard. None of the above.
5
Consider malware programs. Which of the following is true? A worm is a parasite. A virus cannot affect a linux operating system. A trojan can be in the payload of only a worm. A worm and virus are self replicating programs. There is no difference between a virus and a worm.
6
Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the following statements is FALSE? ... weight spanning tree. The edge $e_{m}$ is never present in any maximum weight spanning tree. $G$ has a unique maximum weight spanning tree.
7
Consider the class of synchronization primitives. Which of the following is false? Test and set primitives are as powerful as semaphores. There are various synchronizations that can be implemented using an array of semaphores but not by binary semaphores. Split binary semaphores ... are equivalent. All statements a - c are false. Petri nets with and without inhibitor arcs have the same power.
8
Which of the following is NOT a sufficient and necessary condition for an undirected graph $G$ to be a tree? $G$ is connected and has $n -1$ edges. $G$ is acyclic and connected. $G$ is acyclic and has $n - 1$ edges. $G$ is acyclic, connected and has $n - 1$ edges. $G$ has $n - 1$ edges.
9
Various parameter passing mechanisms have been in used in different programming languages. Which of the following statements is true? Call by value result is used in language Ada. Call by value result is the same as call by name. Call by value is the most robust. Call by reference is the same as call by name. Call by name is the most efficient.
10
Given a set of $n=2^{k}$ distinct numbers, we would like to determine the smallest and the second smallest using comparisons. Which of the following statements is TRUE? Both these elements can be determined using $2k$ comparisons. Both these elements can be ... . $2n - 3$ comparisons are necessary to determine these two elements. $nk$ comparisons are necessary to determine these two elements.
11
Consider an array $A[1...n]$. It consists of a permutation of numbers $1....n$. Now compute another array $B[1...n]$ as follows: $B[A[i]]:= i$ for all $i$. Which of the following is true? $B$ will be a sorted array. $B$ is a permutation of array $A$. Doing the same transformation twice will not give the same array. $B$ is not a permutation of array $A$. None of the above.
12
You are given ten rings numbered from $1$ to $10$, and three pegs labeled $A$, $B$, and $C$. Initially all the rings are on peg $A$, arranged from top to bottom in ascending order of their numbers. The goal is to move all the rings to peg $B$ in the minimum ... ring be placed on top of another ring with a lower number. How many moves are required? $501$ $1023$ $2011$ $10079$ None of the above.
13
Consider a basic block: x:= a[i]; a[j]:= y; z:= a[j] optimized by removing common sub expression a[i] as follows: x:= a[i]; z:= x; a[j]:= y. Which of the following is true? Both are equivalent. The values computed by both are exactly the ... exactly the same values only if $i$ is not equal to $j$. They will be equivalent in concurrent programming languages with shared memory. None of the above.
14
Let $n$ be a large integer. Which of the following statements is TRUE? $n^{1 / \sqrt{\log_2 n}} < \sqrt{\log_2 n} < n^{1/100}$ $n^{1/100} < n^{1 / \sqrt{\log_2 n}} < \sqrt{\log_2 n}$ $n^{1 / \sqrt{\log_2 n}} < n^{1/100} < \sqrt{\log_2 n}$ $\sqrt{\log_2 n} < n^{1 / \sqrt{\log_2 n}} < n^{1/100}$ $\sqrt{\log_2 n} < n^{1/100} < n^{1 / \sqrt{\log_2 n}}$
15
Consider the following two scenarios in the dining philosophers problem: First a philosopher has to enter a room with the table that restricts the number of philosophers to four. There is no restriction on the number of philosophers entering the room. Which of the following is true? ... in (i). Starvation is possible in (i). Deadlock is not possible in (ii). Starvation is not possible in (ii)
16
Let $A_{TM}$ be defined as follows: $A_{TM}=\left \{ \left \langle M, w \right \rangle \mid \text{ The Turing machine$M$accepts the word } w \right \}$ And let $L$ be some $\mathbf{NP}-$ complete language. Which of the following statements is FALSE? $L\in \mathbf{NP}$ ... $A_{TM}$. Since $L$ is $\mathbf{NP}-$ complete, $A_{TM}$ is polynomial time reducible to $L$. $A_{TM} \notin \mathbf{NP}$.
17
Consider the program x:=0; y:=0; (r1:=x; r2:=x; y:= if r1 = r2 then 1 ∥ r3:= y; x:= r3) Note that ∥ denotes the parallel operator. In which of the following cases can the program possibly result in a final state ... . Possible in all sequential programming languages when the compiler appropriately translates the ∥ operator to interleaved statements in the sequential language. None of the above.
18
Suppose $(S_{1}, S_{2},\ldots,S_{m})$ is a finite collection of non-empty subsets of a universe $U.$ Note that the sets in this collection need not be distinct. Consider the following basic step to be performed on this sequence. While there exist sets $S_{i}$ ... of subsets of a finite universe $U$ and a choice of $S_{i}$ and $S_{j}$ in each step such that the process does not terminate.
19
Consider the program P:: x:=1; y:=1; z:=1; u:=0 And the program Q:: x, y, z, u := 1, 1, 1, 1; u:= 0 Which of the following is true? P and Q are equivalent for sequential processors. P and Q are equivalent for all multi-processor models. P and Q are equivalent for all multi-core machines. P and Q are equivalent for all networks of computers. None of the above
20
Let $S=\left \{ x_{1},....,x_{n} \right \}$ be a set of $n$ numbers. Consider the problem of storing the elements of $S$ in an array $A\left [ 1...n \right ]$ such that the following min-heap property is maintained for all $2\leq i\leq n: A [\lfloor i/2\rfloor]\leq A[i]$ ... $O (n)$ time. This problem can be solved in $O \left ( n^{2} \right )$ time but not in $O(n\log n)$ time. None of the above.
21
Let $n> 1$ be an odd integer. The number of zeros at the end of the number $99^{n}+1$ is. $1$ $2$ $3$ $4$ None of the above.
22
Three dice are rolled independently. What is the probability that the highest and the lowest value differ by $4$? $\left(\dfrac{1}{3}\right)$ $\left(\dfrac{1}{6}\right)$ $\left(\dfrac{1}{9}\right)$ $\left(\dfrac{5}{18}\right)$ $\left(\dfrac{2}{9}\right)$
23
The equation of the tangent to the unit circle at point ($\cos \alpha, \sin \alpha$) is $x\cos \alpha-y \sin\alpha=1$ $x\sin \alpha-y \cos\alpha =1$ $x\cos \alpha+ y\sin\alpha=1$ $x\sin \alpha-y \cos\alpha=1$ None of the above.
24
What is the value of the following limit? $\lim_{x \to 0} \frac{2^x-1}{x}$ $0$ $\log_2(e)$ $\log_e(2)$ $1$ None of the above.
25
A variable that takes thirteen possible values can be communicated using? Thirteen bits. Three bits. $\log_{2}13$ bits. Four bits. None of the above.
26
The exponent of $3$ in the product $100!$ is $27$ $33$ $44$ $48$ None of the above.
27
What is the value of the following limit? $\lim_{x \to 0} \frac{d}{dx}\,\frac{\sin^2 x}{x}$ $0$ $2$ $1$ $\frac{1}{2}$ None of the above
If $z=\dfrac{\sqrt{3}-i}{2}$ and $\large(z^{95}+ i^{67})^{97}= z^{n}$, then the smallest value of $n$ is? $1$ $10$ $11$ $12$ None of the above.
$\int_{0}^{1} \ln x\, \mathrm{d}x=$ $1$ $-1$ $\infty$ $-\infty$ None of the above.