Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
  • 161k
12 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^{...
orlp's user avatar
  • 13.6k
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,511
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 ...
ryan's user avatar
  • 4,511
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,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. ...
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.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 ...
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 ...
Joey Eremondi's user avatar
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
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{...
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
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 ...
Sebastian Oberhoff'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
  • 161k
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
  • 29.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
  • 161k
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
  • 39k
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
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 ...
Raphael's user avatar
  • 72.5k
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 ...
mhum's user avatar
  • 2,102
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 ...
Yuval Filmus's user avatar

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