Problem Detail: Suppose that there is an algorithm which sorts a sequence of $n$ elements $$a_1, a_2, …, a_n$$ Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers. Is it true, given that Read More …
Category: Uncategorized
[Solved]: Calculating genus of graph
Problem Detail: How to calculate genus of arbitrary graph? I am interested in any algorithm, even it based on full search. Asked By : Interloper Answered By : Rick Decker One way that always works and is relatively easy to turn into code Read More …
[Solved]: Why does the map function in MapReduce take two parameters?
Problem Detail: I am playing around with MapReduce and wanted to ask why the map function takes two inputs (key, value)? Why not just pass along the value? Specifically, if you look at the word count example on Wikipedia page you Read More …
[Solved]: Theta Runtime of Nested for Loops
Problem Detail: I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much for(int i = 0; i Read More …
[Solved]: Set combination data structure (And storage complexity)
Problem Detail: I have already posted this question on Stackoverflow, but I’m starting to think that this is the right place. I have a problem where I am required to associate unique combinations from a set (unique subsets) to a given Read More …
[Solved]: Where does the lg(lg(N)) factor come from in Schönhage–Strassen’s run time?
Problem Detail: According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N cdot lg(N))$ except for the recursion step which ends up costing $O(Ncdot lg(N) cdot lg(lg(N)))$. I don’t understand why the Read More …
[Solved]: Checking whether all integers appear exactly once
Problem Detail: Let $texttt{a[]}$ be a finite array. We want to check whether every number between $texttt {min(a[])}$ and $texttt {max(a[])}$ appears exactly once. An obvious solution is sorting the array in time $O(nlog(n))$ and go through the sorted array in Read More …
[Solved]: Closing shapes at non-endpoints
Problem Detail: Consider how one would represent the following image in vector graphics: Pretty simple, right? The entire shape can be represented by a single path element. But suppose additionally that you want to color the heart at the top red. Read More …
[Solved]: DFA with limited states
Problem Detail: Lets $L_z := { a^i b^i c^i : 0 leq i < z }$ ${a,b,c} in sum^*$ there is a DFA with $frac{z(z+1)}{2}+1$ states – How can I prove this? And I need largest possible number $n_z$, for which Read More …
[Solved]: Guessing Number Game
Problem Detail: I was solving this question. It is as follows Joe picks an integer from the list $1,2,cdots,N$ with a probability $p_i$ of picking $i$ for all $1leq i leq N$. He then gives Jason $K$ attempts to guess his Read More …
