# Tag Info

34

Converting Full History to Limited History This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence $$T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)$$ which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...

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}$). ...

31

$k$-SUM can be solved more quickly as follows. For even $k$: Compute a sorted list $S$ of all sums of $k/2$ input elements. Check whether $S$ contains both some number $x$ and its negation $-x$. The algorithm runs in $O(n^{k/2}\log n)$ time. For odd $k$: Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements. For each input element $a$, ...

28

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 ...

27

Generating Functions $\newcommand{\nats}{\mathbb{N}}$ Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked. This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this ...

23

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 ...

21

Assume for contradiction that $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ and $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ are two paths in $G$ of length $k$ with no shared vertices. As $G$ is connected, there is a path $P'$ connecting $v_{i}$ to $u_{j}$ for some $i,j \in [1,k]$ such that $P'$ shares no vertices with $P_{1} \cup P_{2}$ other than $v_{i}$ and ...

20

Master Theorem The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is ...

18

Ok, A bit more detailed answer than in the comments. Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$. ...

17

Guess & Prove Or how I like to call it, the "$\dots$ technique". It can be applied to all kinds of identities. The idea is simple: Guess the solution and prove its correctness. This is a popular method, arguably because it usually requires some creativity and/or experience (good for showing off) but few mechanics (looks elegant). The art here is to ...

16

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

$d$-SUM requires time $n^{\Omega(d)}$ unless k-SAT can be solved in $2^{o(n)}$ time for any constant k. This was shown in a paper by Mihai Patrascu and Ryan Williams(1). In other words, assuming the exponential time hypothesis, your algorithm is optimal up to a constant factor in the exponent (a polynomial factor in $n$) (1) Mihai Patrascu and Ryan ...

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

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

Generating functions are useful when you're designing counting algorithms. That is, not only when you're looking for the number of objects having a certain property, but also when you're looking for a way to enumerate these objects (and, perhaps, generate an algorithm to count the objects). There is a very good presentation in chapter 7 of Concrete ...

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$.

11

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 ...

10

The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum. In formula: \qquad \displaystyle \operatorname{mino}(s, C) = \begin{cases} |s| &, |C| = 1 \\ |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\... 10 So basically there are three questions involved. I know thatE(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it? You use the linearity of expectation and some smart re-writing. First of all, note that $$X_k = \sum_{T \subseteq V, \, |T|=k} \mathbb{1}[T \text{ is clique}].$$ Now, when taking the expectation of$X_k$, one can simply draw ... 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 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

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

Sedgewick and Flajolet have done extensive work in analytic combinatorics, which allows recurrences to be solved asymptotically using a combination of generating functions and complex analysis. Their work allows many recurrences to be solved automatically, and has been implemented in some computer algebra systems. This textbook on the subject was written ...

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