Problem Detail: Suppose we have an algorithm like: n = 0 REPEAT c = randomInt(0,1) n = n + 1 UNTIL (c == 0) RETURN n (Assumuing the random number generator produces “good” random numbers in the mathematical sense.) I understand Read More …
Category: Uncategorized
[Solved]: Do fully optimizing compilers for terminating programs exist?
Problem Detail: In Andrew W. Appel’s book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and proceeds to prove that a fully optimizing compiler Read More …
[Solved]: Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation
Problem Detail: Given a string S of length n characters, is it possible to calculate the Hash of its substring [i, j] (From index i to index j. Inclusive) in O(1) using some form of precomputation ? Maybe a modification of Read More …
[Solved]: on “On the cruelty of really teaching computing science”
Problem Detail: Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course: On the one hand, we teach what looks like the predicate calculus, but we do it very differently Read More …
[Solved]: Proof for variation of Prim’s and Kruskal’s to find maximum-weight acyclic subgraph
Problem Detail: I have been scratching my head to find good counter examples to the following problem: Suppose we are given a directed graph G=(V,E) in which every edge has a distinct positive edge weight. A directed graph is acyclic if Read More …
[Solved]: Are all DFAs also NFAs?
Problem Detail: Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons? Asked By : user2441151 Answered By : Yuval Filmus That depends on how pedantic you are. Morally and semantically speaking, every DFA is an NFA in which there is a unique Read More …
[Solved]: Notation: SPACE(n) vs SPACE(O(n))
Problem Detail: I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not preferred in this case? In Read More …
[Solved]: Can a Multi-Tape Turing Machine have an infinite number of tapes?
Problem Detail: So if k is the number of tapes, is a multi-tape Turing machine allowed to have k = ∞ tapes. I’d assume not since this would give an infinite transition function? Asked By : Ozal Answered By : A.Schulz You need Read More …
[Solved]: Where am I wrong?: “countability” and “recursive enumerability”
Problem Detail: I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i Read More …
[Solved]: Reduction from PARTITION to MAX-CUT
Problem Detail: I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT are both in Karp’s list of Read More …
