28
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 ...
- 81.4k
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.♦
- 156k
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 ...
- 275k
10
votes
Accepted
Binary rooted tree isomorphism
There is a classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman. The algorithm actually uses a simple isomorphism invariant. See for example lecture notes of ...
- 275k
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,...
- 275k
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,431
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,431
8
votes
Accepted
Number of finite strings over a countably infinite alphabet
It's countable. The set $S_\ell$ of strings of length $\ell$ is $\Sigma\times\dots\times\Sigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite ...
- 81.4k
8
votes
Is it feasible to generate every possible RGB image?
The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not ...
D.W.♦
- 156k
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,077
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,273
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.5k
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 ...
- 275k
7
votes
Accepted
How Is a Computer Able to Store and Quickly Manipulate All the Data Required For A Computer Display?
You're confusing the number of possible values that a pixel can display with the amount of data being shown at any given instance. The number you give is the number of possible pixel states that your ...
- 29.7k
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 ...
- 275k
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{...
- 275k
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 ...
- 275k
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 ...
- 275k
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
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 ...
- 81.4k
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.♦
- 156k
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(...
- 28.4k
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 ...
- 275k
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.♦
- 156k
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 ...
- 38.6k
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,...
- 275k
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
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 ...
- 72k
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,012
Only top scored, non community-wiki answers of a minimum length are eligible