Problem Detail: Which of the following statements is correct? sufficient and necessary conditions about regularity of a language exist but not discovered yet. There’s no sufficient and necessary condition about regularity of a language. Pumping lemma is a necessary condition Read More …
Blog
Decidability of prefix language
Problem Detail: At the midterm there was a variant of the following question: For a decidable $L$ define $$text{Pref}(L) = { x mid exists y text{ s.t. } xy in L}$$ Show that $text{Pref}(L)$ is not necessarily decidable. But if I Read More …
Finding nested intervals efficiently
Problem Detail: The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique. If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$ How do I find out which intervals are nested in others efficiently? Read More …
Selection in expected linear time: Why am I getting $O(n)$ bound instead of $Omega(n lg n)$?
Problem Detail: The problem is from CLRS 9.3-1: In the algorithm SELECT, the input elements are divided into groups of $5$. Argue that SELECT does not run in linear time if groups of $3$ are used. If we do the “divide Read More …
Why is the class NP-Complete important compared to NP-hard?
Problem Detail: I’m studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we’re interested in showing a given NP problem is NP-hard. I also understand the definition Read More …
If $L$ is a subset of ${0}^*$, then how can we show that $L^*$ is regular?
Problem Detail: Say, $L subseteq {0}^*$. Then how can we prove that $L^*$ is regular? If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular. Also I Read More …
Minimum cost closed walk in a graph
Problem Detail: Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices? Does this problem have a name? I tried to reduce this to similar problems (in particular the traveling salesman Read More …
NFAs with more than one initial state
Problem Detail: I’m trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it mentions that “There is Read More …
Computational power of deterministic versus nondeterministic min-heap automata
Problem Detail: This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show Read More …
Solve a recurrence using the master theorem
Problem Detail: This is the recursive formula for which I’m trying to find an asymptotic closed form by the master theorem: $$T(n)=9T(n/27)+(n cdot lg(n))^{1/2}$$ I started with $a=9,b=27$ and $f(n)=(ncdot lg n)^{1/2}$ for using the master theorem by $n^{log_b(a)}$, and if Read More …
