Problem Detail: In order to achieve the time complexity of $O(log log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Read More …
Category: Uncategorized
[Solved]: Why is this $f(n) leq 6n^3 + n^2 log n in O(n^3)$ for all $n geq 1$?
Problem Detail: I’m currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples. The question equation: $f(n) = 6n^3 + n^2log Read More …
[Solved]: For a Turing Machine $M_1$, how is the set of machines $M_2$ which are “shorter” than $M_1$ and which accept the same language decidable?
Problem Detail: I wonder how come that the following language is in $mathrm R$. $L_{M_1}=Bigl{langle M_2rangle ;Big|;; M_2 text{ is a TM, and } L(M_1)=L(M_2), text{ and } |langle M_1rangle| > | langle M_2 rangle| Bigr} $ (I know that it’s Read More …
[Solved]: Why is this function computable in $O(n^{1.5})$ time?
Problem Detail: My textbook says: “We define the function $fcolon mathbb{N}tomathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number $i$ such that $n$ is sandwiched between $f(i)$ and $f(i+1)$.” How can Read More …
[Solved]: Operator overloading: Java vs. Python
Problem Detail: Why operator overloading was included in Python and not in Java? How does one decide to include or exclude operator overloading in a programming language? It is said here that operator overloading is excluded from Java to make the Read More …
[Solved]: $O(frac{log n}{log log n})$ algorithm for the prefix parity problem
Problem Detail: The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates such as follows. Read More …
[Solved]: Need for an augmented grammar
Problem Detail: The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S’->S to make it as augmented grammar? In short, I want to know the use Read More …
[Solved]: Why does a polynomial-time language have a polynomial-sized circuit?
Problem Detail: I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs use the Read More …
[Solved]: Closure against the operator $A(L)={ww^Rw mid w in L wedge |w| lt 2007}$
Problem Detail: I would like your help with the following question: Let $L$ be a language, and operator $A(L)={,ww^Rw mid w in L wedge |w| lt 2007,}$ where $x^R$ is the reversed string of $x$. Which of the following statements are Read More …
[Solved]: Is it possible to use plants as a medium to store data? By what data structure?
Problem Detail: my question is simple. Is it possible to use plants as a medium to store data? My opinion is: Possible, but we need to solve, how to distinguish 2 states. Duplication and CRC of stored DATA is quiet simple. Read More …
