# Recent questions tagged isi2011-pcb-cs

1
For the function given by the Karnaugh map shown below, you can change at most one $1$ or one $0$ entry to a DON'T CARE. Determine what single change of this kind produces the simplest two-level AND-OR realization. Assume both uncomplemented and complemented inputs are available.
2
Assume a machine has $4$ registers (one of which is the accumulator $A$) and the following instruction set. $\text{LOAD}$ and $\text{STORE}$ ... offset. Design an instruction encoding scheme that allows each of the above instructions (along with operands) to be encoded in $8$ bits.
3
One of your classmates has suggested the following modified version of a standard scheme for solving the $2$-process critical section problem (CSP). shared char want[2] = {0,0}; shared int turn = 0; 1. P_i() 2. { while (1) { 3. turn = j; 4. want[i] ... of instructions executed by two processes $P_0$ and $P_1$. Modify the above scheme so that it becomes a correct solution to the $2$-process CSP.
4
Suppose we have a relation $R(A, B, C, D, E)$ with the functional dependencies: $A \rightarrow D, B \rightarrow C, D \rightarrow E, CE \rightarrow B$. If we project $R$ and therefore its functional dependencies onto the schema $ABC$, what will the key(s) for $ABC$ be?
5
Consider relations $R(A, B)$ and $S(B, C)$. Find a propositional formula $\phi$ such that the following two relational algebra expressions produce the same answer. $\pi_{A,B}(\sigma_\phi(R \bowtie S))$ $R \cap ({\rho_T(A)}(\pi_C(S)) \times \pi_B(S))$
6
Recall that a typical URL has the following form. It starts with a protocol specifier, followed by a colon (:) and two forward slashes (/), followed by a hostname and a domain name. This is followed by an optional path specifier. Some example URLs are given below. {http ... are the only characters that can be used in a host / domain / file / directory name, write a regular expression for URLs.
7
Let $L$ be the set of strings over $\{0, 1\}$ containing an unequal number of $0$s and $1$s. Prove that $L$ is not regular. $L^2$ is regular.
1 vote
8
A vertex cover of a graph $G = (V, E)$ is a set of vertices $V' \subseteq V$ such that for any edge $(u, v) \in E$, either $u$ or $v$\ (or both) is in $V'$. Write a linear time algorithm to find the minimum vertex cover of a given tree $T$. Establish its correctness.
9
Let $T = (V, E)$ be a tree, and let $v \in V$ be any vertex of $T$. The $\text{eccentricity}$ of $v$ is the maximum distance from $v$ to any other vertex in $T$. The $\text{centre } C$ of $T$ is the set of vertices which have minimum eccentricity among all vertices in ... has disjoint centre and centroid, each having two vertices (i.e. $C \cap \mathcal{C} = \not{O}$ and $|C| = |\mathcal{C}| = 2)$.
10
Solve the following recurrence ($n$ is a natural number): $T(n) = \begin{cases} 7T(n\div3)+n^2 & ;n>2 \\ 1 & ;n \leq 2. \end{cases}$
You are given $k$ sorted lists, each containing $m$ integers in ascending order. Assume that (i) the lists are stored as singly-linked lists with one integer in each node, and (ii) the head pointers of these lists are stored in an array. Write an ... if you were permitted to use only constant additional storage? Analyse the time complexity of your algorithm for each of the above two cases.
There are $n$ students of a class standing in a line. The students have to arrange themselves in ascending order on the basis of their roll numbers. This rearrangement of the line must be accomplished only by successively swapping pairs of adjacent students. Design ... minimizes the number of swaps required. Derive an expression for the number of swaps needed by your algorithm in the worst case.
The function $divby3$ given below is intended to check whether a given number is divisible by 3. It assumes that the argument $(number)$ is a string containing the decimal representation of a positive integer, and returns 1 or 0 depending on whether the integer is ... for all positive integers. note: The smaller the number of ALU operations used by your function, the more marks you will get.