# Recent activity by Saurabh Sharma

1
Let the function $f(\theta) = \begin{vmatrix} \sin\theta & \cos\theta & \tan\theta \\ \sin(\frac{\pi}{6}) & \cos(\frac{\pi}{6}) & \tan(\frac{\pi}{6}) & \\ \sin(\frac{\pi}{3}) & \cos(\frac{\pi}{3}) & \tan(\frac{\pi}{3}) \end{vmatrix}$ ... $\theta \in (\frac{\pi}{6},\frac{\pi}{3})$ such that $f'(\theta)\neq 0$ I only II only Both I and II Neither I Nor II
2
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment. c = a + b; d = c ... place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code? 0 1 2 3
3
Which of the following statements are CORRECT? Static allocation of all data areas by a compiler makes it impossible to implement recursion. Automatic garbage collection is essential to implement recursion. Dynamic allocation of activation records is essential to implement recursion. Both heap and stack are essential to ... . $1$ and $2$ only $2$ and $3$ only $3$ and $4$ only $1$ and $3$ only
4
Let $f: B \to C$ and $g: A \to B$ be two functions and let $h = f o g$. Given that $h$ is an onto function which one of the following is TRUE? $f$ and $g$ should both be onto functions $f$ should be onto but $g$ need not to be onto $g$ should be onto but $f$ need not be onto both $f$ and $g$ need not be onto
5
Consider the grammar shown below. $S \rightarrow C \ C$ $C \rightarrow c \ C \mid d$ This grammar is LL(1) SLR(1) but not LL(1) LALR(1) but not SLR(1) LR(I) but not LALR(1)
6
Suppose a processor does not have any stack pointer registers, which of the following statements is true? It cannot have subroutine call instruction It cannot have nested subroutines call Interrupts are not possible All subroutine calls and interrupts are possible
7
Consider the relation account (customer, balance) where the customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. Ties are not broke but ranks are skipped: if ... order assigning ranks using ODBC. Which two of the above statements are correct? 2 and 5 1 and 3 1 and 4 3 and 5
8
Consider a hard disk with $16$ recording surfaces $(0-15)$ having 16384 cylinders $(0-16383)$ and each cylinder contains $64$ sectors $(0-63)$. Data storage capacity in each sector is $512$ bytes. Data are organized cylinder-wise and the addressing format is <cylinder no., ... is the cylinder number of the last sector of the file, if it is stored in a contiguous manner? $1281$ $1282$ $1283$ $1284$
9
Define languages $L_0$ and $L_1$ as follows : $L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\}$ $L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$ Here $\langle M, w, i \rangle$ is a triplet, whose first component $M$ ... but $L'$ is not $L'$ is recursively enumerable, but $L$ is not Both $L$ and $L'$ are recursive Neither $L$ nor $L'$ is recursively enumerable
10
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the following is always true? LASTIN = LASTPOST LASTIN = LASTPRE LASTPRE = LASTPOST None of the above
11
Consider a uniprocessor system executing three tasks $T_{1}, T_{2}$ and $T_{3}$ each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of $3$, $7$ and $20$ milliseconds, respectively ... the 1st millisecond and task preemptions are allowed, the first instance of $T_{3}$ completes its execution at the end of_____________________milliseconds.
12
THISCOURSEISOVER Choose the last elements as pivot elements (R). Also for duplicates, adopt the convention that both pointers stop. a) EHIOCOIERRUSSVTS b) EHISCOIERRUSOVTS b) EHIOCOUESRTSSVTR c) EHIOOCIERRUSSVTS
13
An implementation of a queue $Q$, using two stacks $S1$ and $S2$, is given below: void insert (Q, x) { push (S1, x); } void delete (Q) { if (stack-empty(S2)) then if (stack-empty(S1)) then { print( Q is empty ); return; } else while (!(stack-empty(S1))){ x=pop(S1); push(S2,x); } x= ... $2m\leq y\leq 2n$ $2m\leq x<2n$ and $2m\leq y\leq n+m$ $2m\leq x<2n$ and $2m\leq y\leq 2n$
14
T(n) = T(n - 1) + 1/n a) O(1) b) O(n) c) O(log n) d) O(log log n)
Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: $O\left(|V|^2\right)$ $O\left(|E|+|V|\log |V|\right)$ $O\left(|V|\log|V|\right)$ $O\left(\left(|E|+|V|\right)\log|V|\right)$
Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$