Problem Detail: Given a post-order traversal of Binary Search tree with $k$ nodes, find an algorithm that constructs the BST. My Algortihm Let $n$ represent the next element to be inserted. Let $P(y)$ represent the parent of node $y$. We will read the traversal in reverse. The last element of the traversal is the root. Let…

# Month: January 2017

## [Solved]: Understanding Expected Running Time of Randomized Algorithms

Problem Detail: I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random numbers. What I don’t understand from the above equation is why the expected running time is given for one…

## [Solved]: How to prove polynomial time equivalence?

Problem Detail: Define the problem $W$: Input: A multi-set of numbers $S$, and a number $t$. Question: What is the smallest subset $s subseteq S$ so that $sum_{k in s} k = t$, if there is one? (If not, return none.) I am trying to find some polytime equivalent decision problem $D$ and provide a polytime…

## [Solved]: Compute the Hamming code with odd parity for the memory word 1101 1001 0001 1011

Problem Detail: This is the problem I have: Compute the Hamming code with odd parity for the memory word 1101 1001 0001 1011 (2 pts.). In your solution, mark the parity bits as in the following example, where parity bits are: 3, 5, 11, and 13 0001 0100 1011 1100 1001 1 P P P P…

## [Solved]: Polynomial-time algorithm with exponential space is eligible?

Problem Detail: I’m curious about two things. When we define the class called “probabilistic polynomial-time algorithm” in computer science, does it include polynomial-time algorithm with exponential space? For example, when algorithm is considered to be given a input from domain ${0,1}^n$, what if the algorithm internally queries its exponential sized table (ex. $0^nto0,0^{n-1}1to1$ and so on..)…

## [Solved]: Difference between Binomial and Fibonacci heap (marking)

Problem Detail: I am confused why Binomial heaps do not utilize marking. Concerning Fibonacci heap children: Each tree in a Fibonacci heap is allowed to lose at most two children before that tree needs to be “reprocessed” at a later step. The marking step in the Fibonacci heap allows the data structure to count how many…

## [Solved]: Is there a “sorting” algorithm which returns a random permutation when using a coin-flip comparator?

Problem Detail: Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft’s prominent failure to write a uniform permutation generator, my question is thus: Is there a comparison based sorting algorithm which…

## [Solved]: how do I find a undecidable subset of a set that’s decidable?

Problem Detail: Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable? Asked By : user3277633 Answered By : Yuval Filmus Hint: For every language $L$, the language $M = { 1^{2x+1} : x in L }$ is a subset…

## [Solved]: What Is The Complexity of Implementing a Particle Filter?

Problem Detail: In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations. Is this correct? Could someone explain this? Asked By : DorkRawk Answered By : John Percival Hackworth It appears that the speaker feels that there isn’t a definitive complexity…

## [Solved]: The difference between theoretical complexity and practical efficiency

Problem Detail: If I have this pseudocode: for i=0 to n/2 do for j=0 to n/2 do … do anything …. The number of iterations is $n^2/4$. What is the complexity of this program? Is it $O(n^2)$? What is the intuition formal/informal for which is that complexity? Next, if i have this other pseudocode : for…