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 …
Category: Uncategorized
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 …
Equivalence of regular expressions
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 …
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 …
Characteristic path length
Problem Detail: I am unable to understand that what the characteristic path length (CPL) of a graph is. In one of its definitions, it is written that it is defined as the median of the means of the shortest path lengths Read More …
Rice Theorem – What is non-trivial property?
Problem Detail: Every nontrivial property of the recursively enumerable languages is undecidable. What exactly is nontrivial property? Asked By : Alvar Answered By : Untitled A property that holds for every machine or holds for none is trivial. Rice’s theorem does not apply Read More …
How to determine the maximum RAM capacity for an operating system?
Problem Detail: I was curious to know what limits the max RAM capacity for an OS while reading about microprocessors being 32-bit and 64-bit. I know that limit for 32-bit OS is 4GB and for 64-bit OS is 16 Exabytes, but Read More …
