29
votes
Accepted
Cardinality of the set of algorithms
An algorithm is informally described as a finite sequence of written instructions for accomplishing some task. More formally, they're identified as Turing machines, though you could equally well ...
- 82.1k
13
votes
Represent a 5 card poker hand
If we have a set of size $n$, you can represent an element of the set using $\lceil \lg n \rceil$ bits. You say that there are 2598960 possible 5-card hands. That means that a 5-card hand can be ...
D.W.♦
- 164k
13
votes
Accepted
Is there a linear-time algorithm for randomly sampling weighted combinations?
There is a very simple $O(n \log k)$ algorithm described in Weighted random sampling with a reservoir by Pavlos S. Efraimidis and Paul G. Spirakis, which can be summarized as:
Associate a value $r_i^{...
- 13.8k
11
votes
Cardinality of the set of algorithms
The set of algorithms is countably infinite. This is because each algorithm has a finite description, say as a Turing machine.
The fact that an algorithm has finite description allows us to input one ...
- 278k
10
votes
Accepted
Represent a 5 card poker hand
Let $C$ be a $[52,25,11]$ code. The parity check matrix of $C$ is a $27 \times 52$ bit matrix such that the minimal number of columns whose XOR vanishes is $11$. Denote the $52$ columns by $A_1,\ldots,...
- 278k
9
votes
Solving or approximating recurrence relations for sequences of numbers
There may be times when you come across a strange recurrence like this:
$$T(n) = \begin{cases}
c & n < 7\\
2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7
\end{...
- 4,513
9
votes
Solving or approximating recurrence relations for sequences of numbers
After checking this post again, I'm surprised this isn't on here yet.
Domain Transformation / Change of Variables
When dealing with recurrences it's sometimes useful to be able to change your ...
- 4,513
8
votes
Accepted
Upper bound of of fib(n+2)
So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\{a, b\}$) where the factor/substring $aa$ does not appear right?
In this case, ...
- 1,097
8
votes
Cardinality of the set of algorithms
at least continuum number of strategies to approach a specific problem
"Continuum" is probably supposed to mean the real numbers... using "at least" together with that word is absurdly over the top. ...
- 1,303
8
votes
Hard connected instances for Weisfeiler-Lehman test of isomorphism
Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on ...
- 82.1k
8
votes
Accepted
Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?
Discrete mathematics, linear algebra, calculus, and probability are all used pretty much everywhere in computer science. Basically, discrete maths is the basis of everything, while linear algebra and ...
- 11.6k
7
votes
Solving or approximating recurrence relations for sequences of numbers
Case 2 of the master theorem, as usually stated, handles only recurrences of the form $T(n) = aT(n/b) + f(n)$ in which $f(n) = \Theta(n^{\log_ab}\log^k n)$ for $k \geq 0$. The following theorem, taken ...
- 278k
7
votes
Deriving the average number of inversions across all permutations
For $i < j$ and a random permutation $A$, let $X_{ij}$ be the indicator variable for the event $A[i] > A[j]$. Clearly $\Pr[X_{ij} = 1] = 1/2$ and so $E[X_{ij}] = 1/2$. The total number of ...
- 278k
7
votes
Accepted
Counting the number of squares in a graph
There is a simple $O(n^4)$-time algorithm which I will let you discover yourself. A better algorithm follows from the following formula for the number of squares:
$$
\frac{1}{8} \left( \operatorname{...
- 278k
7
votes
Upper bound of of fib(n+2)
Lee Gao's answer is excellent. Here is a different account. Consider the following automaton:
This is an unambiguous finite automaton (UFA) without $\epsilon$ transitions: an NFA such that each word ...
- 278k
7
votes
Suitable choice for moderate-size square matrix multiplication?
Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and ...
- 278k
7
votes
Accepted
Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?
If you have $n$ bits available you can represent the numbers $0$ to $2^n-1$ in binary. Therefore, if you want to represent a number $x$ in binary, you need a number of bits $n$ that is large enough so ...
- 1,058
7
votes
Cardinality of the set of algorithms
See Gödel Numbering, it is a basic fact in computer science that algorithms are countable, as are by extension recursively enumerable sets.
Algorithms being countable, it is easy to show that there ...
- 171
7
votes
Number of combinations without given pairs
Don't expect an efficient algorithm. This is the problem of counting the number of independent sets in an undirected graph. This problem is #P-complete [1,2], so there is unlikely to be any ...
D.W.♦
- 164k
7
votes
Accepted
Faster algorithm for a specific inversion
Each element $j$ contributes $1$ to the cardinality of all sets $\{j > i \mid \sigma_j > i\}$ for which $i < \min\{\sigma_j, j\}$, and $0$ to the other sets.
You can compute all $n$ values $K(...
- 29.6k
7
votes
Find all n bit numbers with k ones and unique under circular shift
Binary strings considered up to rotation are known as necklaces. You are interested in enumerating binary necklaces with given density. You can find one solution in Wang and Savage, A Gray Code for ...
- 278k
7
votes
Accepted
Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?
It appears your question is equivalent to sampling uniformly at random from the integer partitions of $N$, but constrained so that your partition has $\le B$ parts.
If that is correct, there are ...
D.W.♦
- 164k
6
votes
Accepted
How to find greatest set intersection of at least a given cardinality?
Here is how to reduce clique to your problem. Given a graph $G = (V,E)$ and a number $\ell$, for each vertex $x$ let
$$
S_x = \left\{\{y,z\} \in \binom{V}{2} : y,z \neq x\right\} \cup \{ \{x,y\} : \{x,...
- 278k
6
votes
Accepted
Filling bins with pairs of balls
TL;DR -- No, there is no better strategy than the simple strategy. Here is the main idea of the proof. When there are not enough balls, there will be a "ball path" from a $k$-full bin to a bin with ...
- 39.1k
6
votes
Accepted
Deriving the average number of inversions across all permutations
You can not go directly from one equation to the other; you need to add a whole proof which is separate from what I explain there. Hence my statement "it has been shown".
A boring proof using ...
- 72.8k
6
votes
Accepted
Finding a fixed-size set whose members are contained by the largest number of other sets
I believe your problem is a direct instance of the NP-hard Maximum Coverage Problem, which is related to Set Cover.
From wikipedia, Maximum Coverage Problem:
As input you are given several sets ...
- 76
6
votes
Accepted
Uniformly Random Nested Subset Pairs
For the sake of simplicity, I will assume that: 1) empty sets are allowed, 2) we count a set as a subset of itself (i.e.: both the big set and small set can represent the same set). If these ...
- 2,146
6
votes
Accepted
Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black?
Your problem is #P-complete. The set of solutions can be identified with the set of antichains with the poset corresponding to the DAG (the correspondence identifies a coloring with the black vertices ...
- 278k
6
votes
Choose the kth choice of choosing n things out of m
This is called unranking. The combinatorial number system provides a clean solution to this particular problem.
See also https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-...
D.W.♦
- 164k
6
votes
Smallest set of balls under hamming distance that covers all $n$-bit strings
The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-...
- 278k
Only top scored, non community-wiki answers of a minimum length are eligible