As of May 31, 2023, we have updated our Code of Conduct.
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 ...
David Richerby's user avatar
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.'s user avatar
  • 152k
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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,...
Yuval Filmus's user avatar
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{...
ryan's user avatar
  • 4,391
8 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 ...
ryan's user avatar
  • 4,391
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 ...
David Richerby's user avatar
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.'s user avatar
  • 152k
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, ...
Lee's user avatar
  • 1,057
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. ...
AnoE's user avatar
  • 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 ...
nir shahar's user avatar
  • 11.4k
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 ...
Yuval Filmus's user avatar
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 ...
jmite's user avatar
  • 29.5k
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
drilow's user avatar
  • 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 ...
David Richerby's user avatar
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.'s user avatar
  • 152k
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(...
Steven's user avatar
  • 26.5k
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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 152k
6 votes
Accepted

Heaviest planar subgraph

This is NP-hard even for weighted complete graphs. For an easy algorithm, you can compute a maximum-weight spanning tree: negate the edge weights and run Kruskal's algorithm. This gives you a ...
Juho's user avatar
  • 22.4k
6 votes

Why isn't chess an impartial game?

Chess violates all three conditions, so I don't really understand what there is to ask. (1) The game is not finite. Although the 50-move and threefold repetition rules allow a player to end the game ...
David Richerby's user avatar
6 votes
Accepted

Algorithm: Cracking the Safe

The answer is to use a de Bruijn sequence, as discussed in response to this question on CS Theory. This gives a sequence of length $10^4=10\,000$. However, the sequence is cyclic, in the sense that if ...
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 ...
John L.'s user avatar
  • 38.2k
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,...
Yuval Filmus's user avatar
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 ...
Soeholm's user avatar
  • 76

Only top scored, non community-wiki answers of a minimum length are eligible