search
Log In

Recent questions tagged isi2011-pcb-cs

4 votes
0 answers
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.
asked Jun 3, 2016 in Digital Logic jothee 326 views
9 votes
2 answers
2
14 votes
2 answers
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.
asked Jun 3, 2016 in Operating System jothee 564 views
16 votes
4 answers
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?
asked Jun 3, 2016 in Databases jothee 823 views
2 votes
2 answers
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))$
asked Jun 3, 2016 in Databases jothee 285 views
2 votes
0 answers
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.
asked Jun 3, 2016 in Theory of Computation jothee 114 views
5 votes
1 answer
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.
asked Jun 3, 2016 in Theory of Computation jothee 276 views
1 vote
2 answers
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.
asked Jun 3, 2016 in Graph Theory jothee 198 views
2 votes
0 answers
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)$.
asked Jun 3, 2016 in Graph Theory jothee 180 views
3 votes
4 answers
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}$
asked Jun 3, 2016 in Algorithms jothee 197 views
2 votes
1 answer
11
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.
asked Jun 3, 2016 in Algorithms jothee 249 views
3 votes
1 answer
12
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.
asked Jun 3, 2016 in Algorithms jothee 257 views
1 vote
0 answers
13
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.
asked Jun 3, 2016 in Digital Logic jothee 190 views
To see more, click for the full list of questions or popular tags.
...