Problem Detail: From what I have found, a very large amount of protocols that travel over the internet are “text-based” rather than binary. The protocols in question include, but are not limited to HTTP, SMTP, FTP (I think this one is Read More …
Blog
Finding constants C and k for big-O of fraction of polynomials
Problem Detail: I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for finding the constants $C$ and $k$ 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 …
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 …
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 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 …
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 …
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 …
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 …
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 …
