All Questions
18
questions with no upvoted or accepted answers
5
votes
0
answers
131
views
Analysis of sorting Algorithm with probably wrong comparator?
It is an interesting question from an Interview, I failed it.
An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ （random order）.
We have a comparator $C$, but it has a probability $p$ to ...
- 61
2
votes
1
answer
216
views
Bounding the power of expected value of functions of a random variable.
I am interested in a problem and I do not know where to start looking for possible similar setting. If anyone has a direction to suggest, it would be greatly appreciated.
Consider a (finite) set $\...
- 121
1
vote
0
answers
87
views
Is there a measure that produces given values (probabilities or cardinals) for sets $A_1,\dots, A_n$ and all their intersections $A_i\cap A_j, ... $?
Assume that values (e.g., probabilities or cardinals) of a measure on a finite set $\Omega$ are given for sets $A_1,\dots, A_n$ and all of their intersections $A_i, A_i\cap A_j, A_i\cap A_j\cap A_k, ....
- 8,424
1
vote
0
answers
30
views
Can we find a proper $\phi$ so that maps each interval to its center?
For a compact interval $[0,1]$, we divide it into $N^{1/3}$ subintervals with length $N^{-1/3}$. Define a map $\phi: [0,1]\mapsto [0,1]$ maps each subintervals to its center.
For example, let $X\sim ...
- 1,520
1
vote
0
answers
35
views
Approximate estimation of number of occurrences using hash functions
Let $h: U \to \{0, \dots, M-1\}$ be a universal hash function.
Let $C$ be a counter of size $M$, initially $C[i] = 0$ for $i \in \{0, \dots, M-1\}$
Define $\operatorname{update}(x): C[h(x)] = C[h(x)] +...
- 11
1
vote
0
answers
65
views
How to construct a set system with given set and pairwise intersection sizes
Consider a finite set $X$ and some subsets $X_i \subset X$, $i = 1,\dots,n$, with $\bigcup_i X_i = X$, of which one only knows the sizes $|X_i|$ and $|X_i \cap X_j|$.
How do I systematically ...
- 18.2k
1
vote
0
answers
36
views
General equation for the number of combinations that connect upper part and lower part of grid
Given a square grid with either open or closed cells where open allows a path to be created across the cell. What would be the general equation that describes how many combinations create a path from ...
- 241
1
vote
0
answers
105
views
Does "expected entropy" make sense?
This question is inspired by Determining information in minimum trials (combinatorics problem). Here is the problem statement with some modifications
A student has to pass an exam, with $k$ ...
- 836
1
vote
0
answers
40
views
Choosing my most preferred card from a set of n cards.
I have $n$ cards, however, I like only 1 card the most out of all the $n$ cards and that card is my favourite. I consider the cards one by one, giving each an integer score, where the higher the score ...
- 11
1
vote
0
answers
21
views
Minimum 1-D finite pavement to fit in varying-length K bricks
Suppose you have a set of $k$ bricks, each of varying sizes. we want to fit all these brings one by one on a straight pavement of length $N$. we know the sizes of each brick but we do not know
a) ...
1
vote
0
answers
57
views
What does the 8 stand for in the Cantor pairing function?
What does the "8" stand for in the Cantor pairing function (which assigns a natural number to each pair of natural numbers)?
Can I change it, or is it constant?
The other function for getting the ...
- 17
1
vote
0
answers
185
views
Determine Huffman Tree Depth Using any combinactory ways?
I see this link for determining depth (height) of Huffman tree, but not useful for me.
My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
0
votes
0
answers
48
views
Coin weighting with constraints
Consider the following $(d,k,n)$-coin weighting (with spring scale):
You possess an electronic scale, $n$ coins, and $d$ of them are magnetic. Moreover, you always need to weight at least $k$ coins at ...
- 183
0
votes
0
answers
34
views
Expected size of a set with iterative probabilistic growth
We exhaustively compare every item in set $A$ to the items in set $B$, where $A\cap B=\emptyset$, to look for matches.
We repeat this across iterations, where at every iteration, $|A|=n\gt 0$. At ...
0
votes
0
answers
185
views
Greedy Algorithm on Knockout Tournaments: Proof of Correctness
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
- 11