Problem Detail: A system has 6 identical resources and $N$ processes competing for them. Each process can request at most two requests. Which one of the following values of $N$ could lead to a deadlock? 1 2 3 4 My Read More …
Category: Uncategorized
[Solved]: Metrics and algorithms for complexity of a graph
Problem Detail: I am interested in what sort of metrics are there that try to give a measure of how complex a given graph is, what are the corresponding algorithms, and what is their time complexity. A short description or list Read More …
[Solved]: Why is the Shannon entropy 0.94 in this example?
Problem Detail: Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$. I must find Read More …
[Solved]: Algorithm to convert decimal number to binary
Problem Detail: I am reading this material to understand the basics of number system. I am stuck at a point in that material where it writes the algorithm to convert a decimal number to binary number. The heading of that part Read More …
[Solved]: Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?
Problem Detail: Can a two-stack PDA accept language $L={a^nb^mc^nd^m mid n geq m}$, which has no context-free grammar? I don’t believe this has a context-free grammar, but please correct me if I’m wrong. Asked By : Iancovici Answered By : Patrick87 A two-stack Read More …
[Solved]: Is there a non-brute force algorithm for Eulerization of graphs?
Problem Detail: Given some undirected, unweighted, connected, and potentially parallel-edged graph $G$, an Euler circuit may be constructed iff every vertex in $G$ has an even degree. In graphs with two or more vertices of odd degree (there may only be Read More …
[Solved]: What is an IELR(1)-parser?
Problem Detail: I try to teach myself the usage of bison. The manpage bison(1) says about bison: Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser tables. What is an IELR-parser? All relevant articles Read More …
[Solved]: Is regex golf NP-Complete?
Problem Detail: As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), “regex golf” (which might better be called the regular expression separation problem) is the puzzle of defining Read More …
[Solved]: Maximum degree of concurrency in task dependency graphs
Problem Detail: I’ve been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that’s bugging me is how can I find out the Read More …
[Solved]: How to convert an NFA with overlapping cycles into a regular expression?
Problem Detail: If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as alternatives and so on. But what to do in Read More …
