Problem Detail: Is it possible, in general, to determine whether two regular expressions admit the same set of strings? Also, in particular, is it possible to determine whether a given regular expression admits the same set of strings as the regular Read More …
Author: ignougroup
Solving recurrences using substitution method
Problem Detail: I already have a solution for this problem but it’s just not making sense to me. Here is the problem (It’s from Introduction to Algorithms by CLRS found in CH.4): Show $T(n) = 2T(lfloor n/2 rfloor +17)+n$ is $O(n Read More …
Are there subexponential-time algorithms for NP-complete problems?
Problem Detail: Are there NP-complete problems which have proven subexponential-time algorithms? I am asking for the general case inputs, I am not talking about tractable special cases here. By sub-exponential, I mean an order of growth above polynomials, but less than Read More …
Are there any steps or rules to draw a DFA?
Problem Detail: In my first lecture of “Theory of Automata”, after giving some concepts of Alphabet, Language, transition function etc. and a couple of simple automata of an electric circuit with one and two switches, is this question. I understand what Read More …
Is the class NP closed under complement?
Problem Detail: Is the class $sf NP$ closed under complement or is it unknown? I have looked online, but I couldn’t find anything. Asked By : user16742 Answered By : joebloggs The answer is “not known to science”. It is known that P Read More …
Is $a^n b^n c^n$ context-free?
Problem Detail: I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language $${a^nb^nc^nmid ngeq 1},.$$ Can anybody tell me if this is a Read More …
What’s an example of an unsatisfiable 3-CNF formula?
Problem Detail: I’m trying to wrap my head around an NP-completeness proof which seem to revolve around SAT/3CNF-SAT. Maybe it’s the late hour but I’m afraid I can’t think of a 3CNF formula that cannot be satisfied (I’m probably missing something Read More …
The purpose of grey node in graph depth-first search
Problem Detail: In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (discovered and all its neighbours was visited). Read More …
What’s the difference between Clock and Second Chance Page-Replacement Algorithm?
Problem Detail: I know that they both have reference bit, but I only understand the Second Chance but not the Clock Page-Replacement algorithm. could anyone help me understand? Asked By : Sino Ka Answered By : Wandering Logic Clock is second chance. Given Read More …
Swap space management during pure demand paging
Problem Detail: The following is a doubt that I came across while doing a OS home assignment – however, it seems more concept-based than a straightforward coding question, so IMHO I don’t think the homework tag is appropriate for this. In Read More …
