Problem Detail: Paxos is more powerful and in the famous writing “Consensus on Transaction Commit” : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case of Paxos. Why do relational database use 2PC in real world? Also 2PC Read More …
Category: Uncategorized
[Solved]: Queue, moving the element at the tail to the head
Problem Detail: Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right Read More …
[Solved]: Difference between SRSW and MRSW safe Boolean registers
Problem Detail: I’m reading The Art of Multiprocessor Programming and am currently trying to understand Chapter 4 — The Foundations of Shared Memory. In section 4.2 it is shown how to build a multi-reader, single-writer (MRSW) safe Boolean register from a Read More …
[Solved]: Is the difference of a non-recursive and recursive set recursive?
Problem Detail: I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively enumerable (to generate its elements, I Read More …
[Solved]: Name for this algorithm?
Problem Detail: I’m trying to figure out if there is a proper or commonly accepted name for this particular function (f). float clamp(float min, float max, float v) { if (v < min) return min; else if (v > max) return Read More …
[Solved]: Issue in comparing classifiers for pattern recognition
Problem Detail: I have designed a classifier M which recognizes gestures and classifies it under any category always. A gesture is classified based on the hamming distance between the sample time series y and the training time series x. The result Read More …
[Solved]: Why is the set of NFA that accept all words in co-NPSPACE?
Problem Detail: In Sipser’s book there is a section describing how to decide $qquaddisplaystyle mathrm{ALL}_mathrm{NFA} = { langle N rangle mid N text{ is an NFA}, L(N) = Sigma^*}$ in polynomial space. To do so, it shows $overline{mathrm{ALL}_mathrm{NFA} }$ is in Read More …
[Solved]: CCS process for a drink dispenser with two different prices
Problem Detail: A drink dispenser requires the user to insert a coin ($bar c$), then press one of three buttons: $bar d_{text{tea}}$ requests a cup of tea $e_{text{tea}}$, ditto for coffee, and $bar r$ requests a refund (i.e. the machine gives Read More …
[Solved]: Prove Σ* is decidable
Problem Detail: I see that Σ* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable. What is the proof that Σ* is decidable? Asked By : Charles Answered By Read More …
[Solved]: How do I explain that a polynomial time reduction is in fact polynomial time?
Problem Detail: I have as an assignment question to show that $QuadSat={langlephiranglemidphi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$}$ is $sf NP$-Complete. My solution is as follows, which is pretty much copied almost 100% from a textbook Read More …
