Log In

Recent activity by Arkaprava

1 answer
Find the no. of DFA’s that can be constructed over the alphabet Σ with 5 symbols, and with 10 states. (a) $2^5$^0$ × $50^5$ (b) $2^1$^0$ × $10^5$^0$ (c) $2^5$ × $10^5$^0$ (d) $2^5$^0$ × $50^5$
commented 4 days ago in Theory of Computation 161 views
1 answer
Given an array $A$ of n positive integers, write a program segment / pseudo-code to print the histogram of $A$ using the hash character ($\#$). Your histogram should consist of $n$ vertical columns of $\#$ with the $i$-th vertical bar containing $A[i]$ number of $\#$'s. For example, if you consider ... should look like $\begin{array}{llll} \# \\ \# \\ \# & & \# & \\ \# & \# & \# & \# \end{array}$
answered Mar 14 in Algorithms 176 views
6 answers
A row of $10$ houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses? $199$ $683$ $1365$ $3^{10}-2^{10}$ $3^{10}$
answer edited Jan 22 in Combinatory 1.1k views
1 answer
Consider the set of all functions from $\{1, 2, . . . ,m\}$ to $\{1, 2, . . . , n\}$,where $n > m$. If a function is chosen from this set at random, the probability that it will be strictly increasing is $\binom{n}{m}/n^m\\$ $\binom{n}{m}/m^n\\$ $\binom{m+n-1}{m-1}/n^m\\$ $\binom{m+n-1}{m}/m^n$
commented Jun 29, 2019 in Probability 418 views
1 answer
Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.
answered Jun 26, 2019 in Algorithms 32 views
1 answer
A carnival swing ride swings to the left with probability 0.4 and to the right with probability. If the ride stops after 10 swings, what is the probability that it is exactly at the place it started?
answered Jun 26, 2019 in Probability 164 views
1 answer
How by Pumping Lemma we can prove that “context free grammar generate an infinite number of strings” and here what could be pumping length ?
commented Jun 15, 2019 in Theory of Computation 120 views
1 answer
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.
commented Jun 14, 2019 in Algorithms 468 views
1 answer
Using Armstrong’s axioms of functional dependency derive the following rules: $\{ x \rightarrow y, \: z \subset y \} \mid= x \rightarrow z$ (Note: $x \rightarrow y$ denotes $y$ is functionally dependent on $x$, $z \subseteq y$ denotes $z$ is subset of $y$, and $\mid =$ means derives).
answered Jun 14, 2019 in Databases 254 views
1 answer
As per Gate Overflow Schedule for 2020 for the first week we have to study " Logical Reasoning and Data Interpretation: Verbal reasoning ­ deriving conclusion from passage, conclusions as in puzzles (can be in mathematical logic also) ". So which topics are covered under this and what questions to practice from GO PDF?
answered Jun 12, 2019 in Verbal Ability 203 views
3 answers
Is Y' + Z' same as (YZ)' ? Please explain this concept of compliments..!!
answered Jun 11, 2019 in Digital Logic 139 views
1 answer
Let $\text{ABC}$ be a triangle with $\text{n} $ distinct points inside. A triangulation of $\text{ABC}$ with respect to the $\text{n}$ points is obtained by connecting as many points as possible, such that no more line segments can be added without intersecting other line segments. In other words $\text{ABC}$ ... $n$ points inside it? $3n - 1$ $n^{2} + 1$ $n + 3$ $2n + 1$ $4n - 3$
commented Jun 11, 2019 in Numerical Ability 317 views
2 answers
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.
answered Jun 10, 2019 in Numerical Ability 404 views
2 answers
Hi, I am having a doubt understanding the result of CFL - Regular: Here's my approach: CFL - Regular = CFL INTERSECTION Regular' = CFL INTERSECTION Regular = CFL Suppose some CFL L1= {a^n b^n | n>=1} and some Regular R1= (a+b)* : Now if I do CFL - Reg = {ab, ... ) So is it better to say CFL - Regular = Regular or CFL - Regular = CFL ? If both are separate options, which one should I go for? Thanks
answered Jun 9, 2019 in Theory of Computation 93 views
2 answers
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)
answered Jun 9, 2019 in Algorithms 306 views
4 answers
Budhan covers a distance of $19$ km in $2$ hours by cycling one fourth of the time and walking the rest. The next day he cycles (at the same speed as before) for half the time and walks the rest (at the same speed as before) and covers $26$ km in $2$ hours. The speed in km/h at which Budhan walk is $1$ $4$ $5$ $6$
commented Jun 7, 2019 in Numerical Ability 438 views
4 answers
1 answer
In a mixture of 80 litres of milk and water, 25% of the mixture is milk. How much water should be added to the mixture so that milk becomes 20% of the mixture? (a) 20 litres (b) 15 litres (c) 25 litres (d) None of these
answer edited Jun 4, 2019 in Numerical Ability 84 views
1 answer
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??
commented Jun 2, 2019 in Algorithms 139 views
0 answers
use mathematical induction to prove the sum rule for m tasks from the sum rule for two tasks.
commented Jun 2, 2019 in Combinatory 70 views
2 answers
$1)n^{2019}=O\left (n^{2020} \right )$ $2)O(n^{2019})=O\left (n^{2020} \right )$ Which one is correct?? If $1)$ is correct, why $2)$ not correct?
commented Jun 2, 2019 in Algorithms 235 views
0 answers
A women's health clinic has four doctors and each patient is assigned to one of them. If a patient givs birth btween 8 am and 4 pm, then her chance of being attended by her assigned doctor is 3/4, otherwise it is 1/4. What is the probability that a patient is attended by the assigned doctor when she gives birth? (A) 25/144 (B) 5/12 (C) 7/12 (D) 1/12
commented May 30, 2019 in Mathematical Logic 215 views
1 answer
In a restaurant each of $n$ customer gives a hat to the hat check person. The hat check person gives the hat back to the customer in a random order. What is expected number of customer who get back their own hat?
commented May 27, 2019 in Probability 168 views
3 answers
What is the time complexity for checking whether an assignment of truth values to variables $x_1,\dots ,x_n$ satisfies a given formula $f(x_1\dots,x_n)$? $O(2^n)$ $O(g(n))$ where $g$ is a polynomial $O(log(n))$ None of the above
answered May 25, 2019 in Digital Logic 413 views
3 answers
In how many ways we can put $n$ distinct balls in $k$ dintinct bins?? Will it be $n^{k}$ or $k^{n}$?? Taking example will be easy way to remove this doubt or some other ways possible??
commented May 25, 2019 in Combinatory 146 views
1 answer
I Have doubt about the language. Is it asking about the sum of elements if we make the GBL set for the given lattice .
commented May 20, 2019 in Set Theory & Algebra 58 views
0 answers
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Complexity??
commented May 20, 2019 in Algorithms 114 views
3 answers
The horse has played a little known but very important role in the field of medicine. Horses were injected with toxins of diseases until their blood built up immunities. Then a serum was made from their blood. Serums to fight with diphtheria and ... , that horses were given immunity to diseases generally quite immune to diseases given medicines to fight toxins given diphtheria and tetanus serums
commented May 15, 2019 in Verbal Ability 481 views