# Tag Info

32

The are countably many computable functions: Each computable function has at least one algorithm. Each algorithm has a finite description using symbols from a finite set, e.g. finite binary strings using symbols $\{0,1\}$. The number of finite binary strings denoted by $\{0,1\}^*$ is countable (i.e. the same as the number of natural numbers $\mathsf{N}$). ...

29

I just did a quick animation to convince you. Yellow is one, blue is zero.

28

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 describe them as computer programs. The precise formalism you use doesn't much matter but the fundamental point is that each algorithm can be written down as a ...

24

I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with 1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ... You can find a not-so-nice recursion in the OEIS database. Basically the idea ...

17

If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order. Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller ...

15

The Akra-Bazzi method The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h_i(x)$ can cater for divisions that don't come out ...

14

A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts. The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of ...

13

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 represented using just $\lceil \lg 2598960 \rceil = 22$ bits. 22 bits is significantly shorter than 30 bits. How does the representation work? There are various ...

12

Summations Often one encounters a recurrence of the form $$T(n) = T(n-1) + f(n),$$ where $f(n)$ is monotone. In this case, we can expand $$T(n) = T(c) + \sum_{m=c+1}^n f(m),$$ and so given a starting value $T(c)$, in order to estimate $T(n)$ we need to estimate the sum $f(c+1) + \cdots + f(m)$. Non-decreasing $f(n)$ When $f(n)$ is monotone non-...

12

The block designs you want (for testing 3 things at a time, and covering all pairs) are called Steiner triple systems. There exists a Steiner triple system with $\frac{1}{3} {n \choose 2}$ triples whenever $n \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and algorithms are known to construct these. See, for example, this MathOverflow question (with a link to working ...

12

This is a summary of the paper On the Number of Distinct Languages Accepted by Finite Automata with n States. The paper provides relatively easy, yet far from tight, lower and upper bounds on the number of distinct languages accepted by NFA's. Their discussion on the number of distinct DFA's is very insightful, so I will also include that part. The paper ...

12

I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts. An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the ...

11

Nice idea! The problem seems to be in step $(b)$. Replacing $(X_1,B,X_2)$ in an $N$-path by $(X_1,X_2)$ gives an $\bar{N}$-path, but not every $\bar{N}$-path will contain $(X_1,X_2)$. So this is not a bijection. This only says $N(n) \leq \bar{N}(n)$. Or you can in fact show that $\bar{N}(n) = 3N(n)/2$, resulting in $N(n+1) = 3N^3$.

10

There are 5 (Boolean) variables in the formula. Each of these could be either true or false. This means that there are $2^5=32$ ways of assigning values to these variables. Of the 32 possibilities, only 16 of them make the formula true – this would have to be checked by hand (or machine).

10

You said you were going to multiply by two each time but you added. The simplest way to see it is just to count them. One bit: 0 or 1 -- two values. Two bits: 00, 01, 10 or 11 -- four values. Three bits: 000, 001, 010, 011, 100, 101, 110, 111 -- eight values. Four bits: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, ...

10

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 Vikram Sharma. Using this, you can solve unrooted tree isomorphism in linear time, as described for example in Smal's slides. Another classic algorithm is due to ...

10

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,A_{52}$. We can identify each $A_i$ as a binary number of length $27$ bits. The promise is that the XOR of any $1$ to $10$ of these numbers is never $0$. Using ...

10

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 algorithm into another, and this is the basis of computability theory. It allows us to formulate the halting problem, for example.

9

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{cases}$$ If you're like me, you'll realize you can't use the Master Theorem and then you may think, "hmmm... maybe a recurrence tree analysis could work." Then ...

9

I remember a problem I had to solve during a student programming contest in 2001. The problem was this one: Given masses of 1, 7, 13, ... (I don't remember which masses, but there was a finite, determinate set of masses), design a function that determines whether a given weight can be weighed on a scale with this set of masses. I started with nested ...

9

Here is an "explicit" construction of uncountably many non-computable Boolean functions. Let $K$ be some fixed non-computable Boolean function, say the characteristic function of the halting problem. Consider the set of functions $$F = \{ f \colon \mathbb{N} \to \{0,1\} : \forall x \in \mathbb{N}, f(2x) = K(x) \}.$$ Each $f \in F$ is non-computable, and $F$...

9

If you don't mind graphs with self-loops, the "easiest" expander family is probably this one, giving expanders that are 3-regular. Start with some prime number $p$, and construct vertices numbered $0$ to $p-1$. For every vertex $u \ne 0$, connect $u$ to $u-1$ and $u+1$, modulo $p$. Also connect $u$ to the unique vertex $v$ such that $uv \equiv 1 \mod p$. ...

8

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 domain if it's unclear how deep the recursion stack will go. For instance, take the following recurrence: T(n) = T(2^{2^{\sqrt{\log \log n}}}) + \log \log \log n$... 8 Ultimately, unless you can prove something very interesting, you're stuck with exponential backtracking. For at least one natural encoding of positions, Toads and Frogs is NP-hard. Jesse Hull observed that the position$T^n\Box TFT^m \Box TF$has the game value$\{m+n-1\mid \{ n\mid 2 \}\}$, which means If$T$moves first,$T$gets$m+n-1$free moves. If$...

8

There is no formal connection to anything because "combinatorial explosion" is an informal term. It refers to rapid growth of a function caused by the combinatorics of the situation.

8

No they have the same cardinality. They have the cardinality $\aleph_0$. Both sets are infinite in size so we have to compare them based on their level of infiniteness, since as we know there are infinite levels of infinity. Both sets are countably infinite so we say they have the same cardinality. To expand on this and show why this is the case: The set ...

8

The problem is NP-hard, by reduction from SUBSET-SUM. Given a multiset of numbers $x_1,\ldots,x_n$ and a target $T$, consider $n$ buckets with capacity $C=x_1+\cdots+x_n$, initially filled with $x_1,\ldots,x_n$, and ask whether you can obtain a bucket filled with exactly $T$. You can prove by induction that all buckets are always with filled either with $C$ ...

8

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 feasible to enumerate all such images within the lifetime of the solar system. (There's something wrong with your reasoning if you've concluded it's reasonably ...

8

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, there are a few combinatorial approaches that you can take. Both Yuval and ADG have given simpler and more intuitive arguments, so I definitely suggest checking ...

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