# Recent activity by Arkaprava

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$1 answer 2 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}$1 answer 3 Fill in the missing value 6 answers 4 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?$19968313653^{10}-2^{10}3^{10}$1 answer 5 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$1 answer 6 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$. 1 answer 7 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? 1 answer 8 How by Pumping Lemma we can prove that “context free grammar generate an infinite number of strings” and here what could be pumping length ? 1 answer 9 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. 1 answer 10 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). 1 answer 11 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? 3 answers 12 Is Y' + Z' same as (YZ)' ? Please explain this concept of compliments..!! 1 answer 13 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 - 1n^{2} + 1n + 32n + 14n - 3$2 answers 14 If$z=\dfrac{\sqrt{3}-i}{2}$and$\large(z^{95}+ i^{67})^{97}= z^{n}$, then the smallest value of$n$is?$1101112$None of the above. 2 answers 15 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 2 answers 16 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) 4 answers 17 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$1456$4 answers 18 1 answer 19 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 1 answer 20 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?? 0 answers 21 use mathematical induction to prove the sum rule for m tasks from the sum rule for two tasks. 2 answers 22$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? 0 answers 23 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 1 answer 24 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? 3 answers 25 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 3 answers 26 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?? 1 answer 27 is union of regular language and context free language always regular? 1 answer 28 I Have doubt about the language. Is it asking about the sum of elements if we make the GBL set for the given lattice . 0 answers 29 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??