Problem Detail: According to wikipedia, every finite set is computable. Definition: set $S subset N$ is computable if there exists an algorithm which defines in finite time if a given number $n$ is in Set. Question: what is wrong with this Read More …
Blog
[Solved]: Finding simpler equivalent regular expressions
Problem Detail: I’m doing an exercise from my book that says: Let $r$ and $s$ be arbitrary regular expressions over the alphabet $Sigma$. Find a simpler equivalent regular expression: a. $r(r^*r + r^*) + r^*$ b. $(r + Lambda)^*$ c. $(r Read More …
[Solved]: Virtual Address and Physical Address Space
Problem Detail: A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8K. How many entries are needed for a conventional page table ? The answer is 2^35 entries Why not (2^32) / (2^13) = 2^19 entries…? My doubt Read More …
[Solved]: Starvation Condition in CPU/Process Scheduling?
Problem Detail: Let’s say OS is using preemptive CPU scheduling. A process P1 gets a chance to run for some time and then next higher priority process comes and preempts P1. After that higher priority processes are coming regularly and P1 Read More …
[Solved]: Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular
Problem Detail: Suppose we define an operation such that $$A text{ avoiding } B = {w in A mid wtext{ has no substring in }B},.$$ How can I prove that, if $A$ and $B$ are regular then $Atext{ avoiding }B$ is Read More …
[Solved]: Interpretation of ‘1/3’ in IEEE floating point representation
Problem Detail: For a rational number 1/3 below is the floating point representation(64 bit) of decimal expansion 0.3333333…. As per the above bit structure, I would like to interpret the value of exponent(11 bits) and value of fraction(52 bits). exponent has Read More …
[Solved]: Shortest path in a matrix
Problem Detail: I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each number in Read More …
[Solved]: What is the difference between radix trees and Patricia tries?
Problem Detail: I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a normal (uncompressed) trie by Read More …
[Solved]: Is a stack machine with a forward read iterator Turing complete?
Problem Detail: It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful Read More …
[Solved]: NP-complete problems not “obviously” in NP
Problem Detail: It occurred to many that in all the $textbf{NP}$-completeness proofs I’ve read (that I can remember), it’s always trivial to show that a problem is in $textbf{NP}$, and showing that it is $textbf{NP}$-hard is the… hard part. What $textbf{NP}$-complete Read More …
