Problem Detail: In statically-typed object-oriented languages (like Java, C++, C#, …), suppose I declare an abstract class: public abstract class myclass1 { …………….. } Most of these languages (like Java) wouldn’t allow us to create an Object of an Abstract class, Read More …
Blog
[Solved]: Chernoff bounds and Monte Carlo algorithms
Problem Detail: One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to bound the error probability of Read More …
[Solved]: Complexity of variation of partition problem
Problem Detail: I want to know whats the complexity of the following variant of the partition problem: Partition problem: http://en.wikipedia.org/wiki/Partition_problem Suppose we have one set formed by integers and we want to partition the set in two subsets of the same Read More …
[Solved]: How to find the big O notation of $log^b x$
Problem Detail: How would you determine big O notation for $log^b x$? I don’t think you can simply say $O(log^b x)$, can you? If you can, then here is a better question: $x^3 + log^b x$. How would you know if Read More …
[Solved]: If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?
Problem Detail: I learned that recursive Fibonacci is $O(2^N)$. However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or near Read More …
[Solved]: Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language
Problem Detail: In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. Now Assume that $R$ is a regular language and $D$ Read More …
[Solved]: Which kind of branch prediction is more important?
Problem Detail: I have observed that there are two different types of states in branch prediction. In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay. In the instruction pipeline, Read More …
[Solved]: Does two languages being in P imply reduction to each other?
Problem Detail: Given two languages $L_1$ and $L_2$ that are in $mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the empty Read More …
[Solved]: FM-index – print all patterns
Problem Detail: How is it possible to print all patterns, of length k, contained in a string using FM-index and burrows-wheeler transform? PROBLEM DETAIL: I think it’s better to leave more details regarding my problem. The input i have are: the Read More …
[Solved]: Showing that 3-colorable is NP-complete
Problem Detail: Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? I’m aware we Read More …
