Blog

Problem Detail: The original statement for this problem can be found here This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD equals to Read More …

Problem Detail: I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don’t understand in bold. (BB(n) is defined as the number of steps made by n-state Busy Beavers.) Theorem: BB(n) is uncomputable. That is, there is no Turing Read More …

Problem Detail: I thought the answer would be 32 for remainder $0,1,2,dots, 31$. But answer given as $6$. and explanation is given as if the number is $2^n$ then number of states required would be $n+1$. Asked By : Vikrant Answered By : David Read More …

Problem Detail: I’ve been trying to make a CFG, a pushdown automaton and a regular expression for the language $qquad L(M) = {ww : w in {a, b}^*, |w| text{ is even}}$. I understand how the reverse of the string work, Read More …

Problem Detail: Is it true that the heaviest edge in a directed graph can not be in the MST of that graph? I don’t think it is true because we might end up with a heaviest edge that is not part Read More …

Problem Detail: I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) states that it Read More …

Problem Detail: In the book introduction to automata theory and languages, $L^*$ is defined as $$L^* = bigcup_{i=0}^infty L^i $$ The book also says that $emptyset^* = { epsilon }$. But since $emptyset$ is the empty set $$L^* = L^0 cup Read More …

Problem Detail: My question is the following: How to calculate the regret in practice? I am trying to implement the regret matching algorithm but I do not understand how to do it. First, I have $n$ players with the joint action Read More …

Problem Detail: We say that the language $J subseteq Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$ |J^c cap Sigma^n| leq p(n)$$ for all $n in mathbb{N}.$ In other words, for any given lenght $n$ there exist Read More …

Problem Detail: I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to the array representation where the next Read More …