# Question
Title: What are efficient ways to compute the derivatives of iterated functions?
The derivatives of iterated functions at a fixed point $z\_0$ are useful in constructing a Taylors series of iterated analytic functions - in other words, the Taylors series of a dynamical system $f^t(z\_0)$.

A simpler version of the problem casts light on possible approaches. Instead of iterated functions, consider composite functions and Faà di Bruno's formula The combinatorial structure integer partitions serves as the index to the summations in Faà di Bruno's formula. So the first step of evaluation is to enumerate all integer partitions of a given order.

While combinatorial structure integer partitions are associated with the derivatives of composite functions, the unlabeled version of the labeled combinatorial structure total partitions are associated with iterated functions. See Partition Diagrams for more information on the different relevant combinatorial structures. The following Mathematica code does what I need, but the cost of simplicity is that it first enumerates the labeled total partitions to compute the unlabeled total partitions. So for $n=10$, $D^{10}f^t(z\_0)$, there are 282,137,824 labeled total partitions, while there are only 2,312 unlabeled partitions.

## Combinatorial Examples

a(4)=5 unlabeled total partitions: (oooo),(oo(oo)),(o(ooo)),(o(o(oo))),((oo)(oo)).

b(4)=26 labeled total partitions: ((1,4),2,3), (1,(2,4),3), (1,2,(3,4)), (((1,4),2),3), ((1,(2,4)),3), ((1,2),(3,4)), (((1,4),3),2), ((1,(3,4)),2), ((1,3),(2,4)), ((1,4),(2,3)), (1,((2,4),3)), (1,(2,(3,4))), (1,2,3,4), ((1,2,4),3), ((1,2),3,4), ((1,3,4),2), ((1,3),2,4), (1,(2,3,4)), (1,(2,3),4), ((1,2,3),4), (((1,2),4),3), (((1,2),3),4), (((1,3),4),2), (((1,3),2),4), (1,((2,3),4)), ((1,(2,3)),4)

b(4) = 12 (o(o(oo))) + 3 ((oo)(oo)) + 6 ((oo(oo)) + 4 (o(ooo)) + (oooo) = 26

I would like to have an efficient way to reproduce the preceding results.

## Mathematica code

```
TotalPartitions[0] = {{}};
TotalPartitions[1] = {{1}};
TotalPartitions[2] = {{1, 2}};
Match[l_List, pattern_] := Extract[l, Position[l, pattern]];
TP1[l_List, next_Integer] :=
  Map[( l /. # -> {#, next}) &, Match[l, _Integer] ];
TP2[l_List, next_Integer] :=
  Map[( l /. # -> Append[#, next]) &, Match[l, _List] ];
TP3[l_List, next_Integer] :=
  Map[( l /. # -> {#, next}) &, Match[l, _List] ];
TotalPartitions[n_Integer] :=
  TotalPartitions[n] =
   Flatten[ {Map[(TP1[#, n] ) &, TotalPartitions[n - 1]],
     Map[(TP2[#, n] ) &, TotalPartitions[n - 1]],
     Map[(TP3[#, n] ) &, TotalPartitions[n - 1]]}, 2];

u = TotalPartitions[4] /. _Integer -> 1
> {{{{1, 1}, 1}, 1}, {{1, {1, 1}}, 1},
>  {{1, 1}, {1, 1}}, {{1, 1}, {1, 1}},
>  {1, {{1, 1}, 1}}, {1, {1, {1, 1}}},
>  {{1, 1}, 1, 1}, {1, {1, 1}, 1},
>  {1, 1, {1, 1}}, {{{1, 1}, 1}, 1},
>  {{1, {1, 1}}, 1}, {{1, 1}, {1, 1}},
>  {{1, 1, 1}, 1}, {{1, 1}, 1, 1},
>  {1, {1, 1, 1}}, {1, {1, 1}, 1},
>  {1, 1, 1, 1}, {{1, 1, 1}, 1},
>  {{1, 1}, 1, 1}, {{{1, 1}, 1}, 1},
>  {{{1, 1}, 1}, 1}, {1, {{1, 1}, 1}},
>  {{1, {1, 1}}, 1}, {{1, 1, 1}, 1},
>  {{{1, 1}, 1}, 1}, {{{1, 1}, 1}, 1}}

SetAttributes[Z, Orderless];
Tally[Apply[List, Apply[Z, u, Infinity], Infinity]]
>  {{{1, {1, {1, 1}}}, 12}, {{{1, 1}, {1, 1}}, 3}, {{1, 1, {1, 1}}, 6},
>   {{1, {1, 1, 1}}, 4}, {{1, 1, 1, 1}, 1}}

```

Note that the Tally function displays the number of occurrences of labeled total partitions for each unlabeled total partition, so that $12+3+6+4+1=26$ shows how the 5 unlabeled total partitions of order 4 map to the 26 labeled total partitions. I've tried pure analytic approaches, combinatorial approaches and a hybrid of the two in my Mathematica programs Schroeder Summations and Iterate. I believe this is a useful problem in dynamics and combinatorics and merits an efficient answer.

# Answer
An unordered hierarchical partition of $n \geq 2$ is composed out of two ingredients:

1. A non-trivial partition $n\_1,\ldots,n\_k \vdash n$, where $n\_1 \leq \cdots \leq n\_k$ and $k \> 1$.
2. For each $n\_i$, an unordered hierarchical partition of $n\_i$. Furthermore, if $n\_i = n\_{i+1}$ then in some fixed order of hierarchical partitions of $n\_i$, the one chosen for $n\_i$ must precede or equal the one chosen for $n\_{i+1}$.

In the base case $n = 1$ there is a single unordered hierarchical partition.

This gives the following algorithm for generating all unordered hierarchical partitions. We generate a list $P^{(n)}\_1,\ldots,P^{(n)}\_{q(i)}$ of all $q(n)$ unordered hierarchical partitions of $n$. For $n = 1$, the list consists of the single trivial partition. In order to generate the list for $n$:

1. Go over all non-trivial partitions $n\_1,\ldots,n\_k \vdash n$. We can write this partition more succinctly as $1^{m\_1},\ldots,(n-1)^{m\_{n-1}}$, where $m\_i$ is the multiplicity of $i$.
2. For each $i \in \\{1,\ldots,n-1\\}$, make a list of all non-decreasing sequences of length $m\_i$ consisting of numbers in $\\{1,\ldots,q(i)\\}$; there are $\binom{q(i)+m\_i-1}{q(i)}$ of these.
3. Each choice of one sequence for each $i$ from the corresponding list corresponds to one unordered hierarchical partition of $n$.
> 1 votes

# Answer
@YuvalFilmus has provided an algorithm that I believe answers the question of how to enumerate the ordered hierarchical partitions in terms of unordered hierarchical partitions. Ideally this would be a comment to his answer, but it is too lengthy. I am trying to write Yuval's algorithm in Mathematica as a precursor to coding an efficient way to compute the derivatives of iterated functions. The following Mathematica code comes close to correctly enumerating the unordered hierarchical partitions.

```
<< Combinatorica`
o[1] = {1};
o[n_ /; n > 1] :=
 Apply[Sequence,
  Map[Tuples, Rest[Partitions[n]] /. m_Integer -> o[m]], 1];
Table[Length[o[i]], {i, 6}]
> {1, 1, 2, 5, 12, 34}

```

The value o\[6\] should be 33, not 34. This is because the `Tuple` command is used and produces both {{{1,1},1},{1,1,1}} and {{1,1,1},{{1,1},1}} which are the same when unordered.

```
o[3]={{1, 1, 1}, {{1, 1}, 1}}

```

This is where step 2. of Yuval's algorithm comes into play. The following are legitimate values for non-decreasing sequences

```
{o[3][[1]],o[3][[1]]}
> {{{1,1},1},{{1,1},1}}
{o[3][[1]],o[3][[2]]}
> {{{1,1},1},{1,1,1}}
{o[3][[2]],o[3][[2]]}
> {{1,1,1},{1,1,1}}

```

while the following with indices 2, 1 is an invalid decreasing sequence

```
{o[3][[2]],o[3][[1]]}
> {{1,1,1},{{1,1},1}}

```

The `Tuple` command therefore needs to be replaced with a version where no tuple is in non-descending order.
> 0 votes

---
Tags: algorithms, combinatorics, recursion
---


# Question
Title: Turing machines and languages -- recursive (enumerable) or not
For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could explain it to me.

```
In this question, L1, L2, L3, L4 refer to languages and M, M1, M2 refer to Turing machines.

```

Let

```
L1 = {(M1,M2) | L(M1) is a subset of L(M2)},
L2 = {M | There exists an input on which TM M halts within 100 steps},
L3 = {M | There exists an input w of size less than 100, such that M accepts w},
L4 = {M | L(M) contains at least 2 strings}.

```

Decide whether each of L1, L2, L3 and L4 are recursive, RE or neither. Then identify the true statement below.

```
     a)      The complement of L3 is recursively enumerable.
     b)      The complement of L2 is recursive.
     c)      The complement of L2 is not recursively enumerable.
     d)      L1 is recursively enumerable.

```

**What I do not understand is, how the definitions of L1, L2, L3, L4 can tell me whether or not they are recursive (enumerable).**

My guesses (probably wrong) are:

L1: ?

L2: recursive enumerable (I thought this since obviously there are inputs on which the TM halts but we can not say if it halts every time – therefore only recursive enumerable and not recursive)

L3: recursive enumerable (Same explanation as for L2)

L4: not recursive (This is only a guess, I don't get how the number of minimum strings of the language can imply any type of recursiveness.)

# Answer
> 1 votes
**Hints.**

1. If you're trying to figure out some property of a Turing machine and the only thing you can think of is, "Check every input" then it's probably not recursive.
2. If a language is RE and so is its complement, both are actually recursive (this is a good way of proving that languages aren't RE: for example, the language of pairs $\langle M,x\rangle$ such that Turing machine $M$ *does not* halt on input $x$ is not RE for this reason).
3. If a Turing machine halts within 100 steps, how much of its input has it seen?

Note that L2 and L3 are subtly different so you can't use the same explanation for both (the answers are actually different).

---
Tags: formal-languages, turing-machines, halting-problem
---


# Question
Title: What is pass-by-value-result and its advantage and disadvantage?
I have searched on Google, but I can't quite understand what is pass-by-value-result. What is the advantage and disadvantage of using pass-by-value-result?

If I have a program code like this, what will be the result when parameters are passed by value-result?

```
#include <stdio.h>

int a=2;
int b=1;

void fun(int x, int y) {
    b=x+y;
    x=a+y;
    y=b+x;
}

void main() {
    fun(b,b);
    printf("%d %d\n",a,b);
}

```

# Answer
> 10 votes
**Note**: parameter passing by xxx is sometimes called "pass by xxx" and sometimes "call by xxx". I will use both expressions indifferently.

Parameter passing by value-result consists in passing by value when the subprogram (whatever it is) is called, and then, when it terminates, assign the current value of the formal parameter in the subprogram back to the actual parameter if it is a mutable entity, such as a variable or an array entry. Of course, no such assignment may occur if the actual parameter is a non mutable value providing entity such as an expression, a function call, a constant (though some old versions of Fortran have been known to assign values to constants, so that printing 3 could actually print 5).

Afaik, fortran was first to use this mechanism (I do not know for Cobol). It is also available in Ada. Actually, Ada has call by value (IN parameter) and call by result (OUT parameter). OUT parameters are not initialized at call, but assign current value of formal parameter to the actual parameter upon return. Parameter passing by value-result (IN OUT) is the combination of both. Actually, the case of Ada is more complicated (at least in its initial versions) because it was explicitly allowed to implement these parameter passing mechanism with a call by reference. I am not sure of the current status of the language. This of course muddles the discussion below.

**Comparing parameters passing mechanisms is dependent on the language considered.**

**Issues** you may want to consider are cost in time or space, readability and maintenance, compiling issues such as efficiency and optimization, and also semantics such as determinacy of programs, and also programming convenience. (I may have forgotten some).

Many of these issue are stongly impacted by **aliasing** phenomena. Whenever the same mutable entity (possibly a simple variable) can be accessed in different ways, it becomes harder to analyse the program, determine what parts of the computation may interfere with other parts. When there are several threads of computation, this may cause race conditions making the computation dependent on timing. When compiling program, aliasing may make it harder to get a reliable definition-use relation for performing some otpimizations.

Hence,I would consider aliasing problems a major issue when comparing computing mechanisms.

Since you need ways to communicate in programs, assessing a parameter passing mechanism can only by comparing to alternatives.

Regarding pass-by-value-result, the are only two that I see:

* Doing nothing on exit.
Then you can pass information back to the caller only as function result, or by assigning a global variable visible from both callee and caller.
* Using pass by reference.
Then the formal parameter becomes just another name, an alias, for the actual parameter, so that the actual parameter has the value of the formal one upon exit (as well as before exit).

## Issues

**Time and space cost**

One advantage of call by reference over call by value-result is that it is often cheaper, especially if the data to be passed is large (time/space costs of copying). Call by reference may have a time cost because of indirect addressing, though that can sometimes be optimized out.

**Aliasing**

The major drawback of call by reference is all I said about aliasing. So that may be considered a very good point for pass-by-value-result.

**Side effects and evaluation order**

Then call by value-return has a problem when returning the values, as in your example. If two formal parameters (x and y in the example) actually get the same actual parameter (b in the example) then the actual parameter will take on return a value that depends on the order chosen for returning values. Hence, it is essential to define it. In any case, such a situation is a sure indicator of bad programming practice.

This problem does not exists with call by reference. But call by reference is a completely different kind of computation, as shown by executing your example in call by reference.

Returning values is a side-effect on the actual parameters. Computations with side-effects always raise issues of order dependence. If the evaluation of actuall parameters entails some side-effects (for example by calling a function with side-effects), then the order of evaluation of arguments may have an impact on the computation. That is why side-effect are to be avoided, or at least carefully managed.

**Objects identity**

If you have a language that allows to distinguish identity and egality, the call by reference wil preserve identity, while call by value will not. For example, when you copy an integer (for example by assignment), there is no way you can distinguish the new copy from the old one. But Object-Oriented (OO) languages could let you make a difference, and have a test for equality (same value) and a test for identity (same reference).

**Well definedness of call by value** (irrespective of result)

Another problem is that call by value may not be well defined. You have to determine what a value is. How deep do you copy an object implemented with references (pointers) when doing call by value. When a reference is not followed for copying, it is an open door for aliasing problems.

I am not saying these issues are untractable, but only that you have to deal with them consistently throughout the language (consistency with assigment in particular). And that does not make for a clearcut answer, independently of the rest of the language, and the style of programming it supports.

## Running the example in call by value-result and call by reference

**Notation**

```
    a<==b  a becomes aliased to b
    a==b   a is alias of b  (reminder)
    a<-3   a is assigned the value 3

```

**Call by value-result:**

```
    Call of fun(b,b): x<-1 y<-1 b<-2 x<-3 y<-5 return print 2 (3 or 5)

```

unpon returning, b ends up with 3 or 5 depending on the order of argument return.

**Call by reference:**

```
    Call of fun(b,b) x<==b y<==b b==b<-2 b==x<-4 b==y<-8 return print 2 8

```

---
Tags: terminology, programming-languages, semantics
---


title: Reversing Key Algorithm

text:
# Question
Title: Reversing Key Algorithm
I have to craft up a number made of 19 digits so that, after some mathematical operations made 11 times, the resulting sum of the remainders of the first ten operations is equal to the the remainder of the eleventh operation. The eleven calculations are as follows. I need to reverse them in order to be able to craft up the x.

op\_10 : (x / 256) mod 256 =\> This is the remainder that must be equal to the sum of the ten remainders below.

op\_0 : (x / 72057594037927936) mod 256 =\> 1st remainder

op\_1 : (x / 281474976710656) mod 256 =\> 2nd remainder

op\_2 : (x / 65536) mod 16 =\> 3rd remainder

op\_3 : (x / 1048576) mod 16 =\> 4th remainder

op\_4 : (x / 16777216) mod 16 =\> 5th remainder

op\_5 : (x / 268435456) mod 16 =\> 6th remainder

op\_6 : (x / 4294967296) mod 16 =\> 7th remainder

op\_7 : (x / 68719476736) mod 16 =\> 8th remainder

op\_8 : (x / 1099511627776) mod 16 =\> 9th remainder

op\_9 : (x / 17592186044416) mod 16 =\> 10th remainder

Is there such an algorithm? x is the number i need to craft up.

# Answer
You forgot to mention that $x$ is in fact $64$ bits long. Write $x$ in binary notation: $$ x\_{63} x\_{62} \ldots x\_1 x\_0. $$ We have $$ \begin{align\*} op\_0 &= x\_{63} \cdots x\_{56} \\ op\_1 &= x\_{55} \cdots x\_{48} \\ op\_2 &= x\_{19} \cdots x\_{16} \\ op\_3 &= x\_{23} \cdots x\_{20} \\ op\_4 &= x\_{27} \cdots x\_{24} \\ op\_5 &= x\_{31} \cdots x\_{28} \\ op\_6 &= x\_{35} \cdots x\_{32} \\ op\_7 &= x\_{39} \cdots x\_{36} \\ op\_8 &= x\_{43} \cdots x\_{40} \\ op\_9 &= x\_{47} \cdots x\_{44} \\ op\_{10} &= x\_{15} \cdots x\_8 \end{align\*} $$ All these, in binary notation.

I'll let you take it from here.
> 1 votes

---
Tags: algorithms, number-theory
---


# Question
Title: Find the minimum amount of swaps in fixed indices to sort an array
When given the length of a source array, I want to generate the array of swaps that need to be performed in order to sort the source array. I want to make this array **as small as possible**. Swaps will be performed only if necessary for sorting, as defined by the following function.

```
def compare_swap(array, a, b):
    if array[a] < array[b]:
      (array[a], array[b]) = (array[b], array[a])

```

Example

* input: **3**
* Output: **\[(0,1), (1,2), (0,1)\]**

What I mean is something like network sorting.

I want to understand how to calculate the number of such swaps and how to generate such array exactly.

# Answer
Your question appears to be about sorting networks. Sorting an array in the comparison model requires $\Omega(n\log n)$ comparisons, and so $\Omega(n\log n)$ of your *swaps*. Ajtai, Komlós and Szemerédi were the first to come up with a matching $O(n\log n)$ sorting network (the AKS sorting network), and their construction was simplified by Patterson. These networks also have the advantage that they can be divided into $O(\log n)$ layers of disjoint swaps. Very recently, Goodrich came up with Zigzag sort, another $O(n\log n)$ sorting network.

Since we know that there exist $O(n\log n)$ sorting networks, we can find an optimal sorting network in time $\binom{n}{2}^{O(n\log n)} = 2^{O(n\log^2 n)}$ (verifying that a network works takes time roughly $2^n$ using the zero-one principle). There is no reason to expect any subexponential algorithm.

You might be interested in Ian Parberry's page on sorting.

---

This part answers the following question: What is the maximal number of swaps needed to order an array of length $n$?

Suppose that your array contained numbers from $1$ to $n$. Then you can think of it as a permutation $\pi \in S\_n$. Swapping two elements in the same as multiplying by a transposition, so the question is how many transpositions we need to multiply to get $\pi$. If the cycle structure of $\pi$ is $a\_1,\ldots,a\_k$ then this number is $(a\_1-1) + \cdots + (a\_k-1) = n - k$. Therefore $n-1$ is the most that is needed. An example of a permutation needing $n-1$ swaps is $(234\cdots n1)$, which corresponds to the array $2,3,4,\ldots,n,1$.
> 5 votes

# Answer
A swap array that will work for any list is $\[01, 12, \ldots, (n-1)n, 01, 12, \ldots, (n-2)(n-1), \ldots, 01, 12, 01\]$. So compare each subsequent pair of elements: this fixes the last element. Then compare each pair excluding the last element: this fixes the second to last element. In all there are $nC2$ comparisons. Your example fits this algorithm for $n=3$.

Edit: however I think this is not minimal
> 0 votes

---
Tags: algorithms, sorting
---


title: Approximating NP-complete problems

text:
# Question
Title: Approximating NP-complete problems
Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it.

Could we get around this by finding an algorithm which approximates the solution to a certain accuracy?

That is, would the result above bar the existence of an algorithm which finds a maximum independent set to an accuracy of 0.5? I.e., it is guaranteed to be less than 0.5 away from the size of a maximum set? (And hence implying that it actually *is* a maximum independent set.)

It seems to me that the latter wouldn't violate our proofs of non-tractability, which are discrete in nature, while still giving an answer that satisfies the problem from a practical perspective.

# Answer
We do not know for certain that independent set cannot be solved exactly in polynomial time. However, it is considered unlikely, and this is the famous P$\neq$NP conjecture.

In cases where exact optimal solutions cannot (probably) be found in polynomial time, it is natural to look for approximately optimal solutions. Algorithms tackling this are known as *approximation algorithms*. If an algorithm always returns a solution whose value is within $\rho$ of the optimum, then we call it a *$\rho$-approximation algorithm*, and say that its *approximation ratio* is $\rho$.

A good example is MAX-3SAT, in which we are given a 3CNF formula, and our goal is to find an assignment maximizing the number of satisfied clauses. The corresponding decision version is a generalization of 3SAT, and so it is NP-complete. However, if we choose an assignment at random, it satisfies $7/8$th of the clauses in expectation, and we can in fact deterministically find such an assignment. Since the optimal solution satisfies at most a $1$-fraction of the clauses, this algorithm has an approximation ratio of $7/8$. It is a consequence of the PCP theorem that it is NP-hard to do any better (this is a result of Håstad). We say that MAX-3SAT is *NP-hard to approximate within $7/8+\epsilon$* for any $\epsilon \> 0$.

The independent set problem is much harder than MAX-3SAT. Indeed, it is NP-hard to approximate within $n^{1-\epsilon}$ for any $\epsilon \> 0$. The best approximation algorithm known has approximation ratio $O(n(\log\log n)^2/\log^3 n)$ (as per Wikipedia).

In practice, independent set can probably be approximated better, but this is different to formalize, since it is not clear what properties *real-world* graphs satisfy. For random $G(n,1/2)$ graphs (in which each edge is chosen with probability $1/2$ independently), there is a $1/2$-approximation algorithm (the approximation ratio is with high probability over the choice of the graph).

Sometimes one considers *smooth analysis* of algorithms to model real-world instances. The idea is that real-world instances are noisy, and so instead of being interested in a specific graph $G$, we should be looking at a "neighborhood" of $G$ formed from graphs close to $G$ (differing by a relatively small number of edges). It could be the case that some algorithm has good approximation ratio on most of the graphs in the neighborhood of *any* graph $G$. I am not aware of any such analysis for independent set.
> 10 votes

# Answer
To supplement Yuval's answer (since I've already written this out!):

If we assume a proof exists showing NP-complete problems cannot be solved in polynomial time (a very important corollary for such a proof would be that $P \neq NP$), such a proof would not invalidate any of the existing methods we have for coping with NP-complete problems:

* A brute force algorithm may be fine if instances of the problem are small.
* Sometimes the structure of problem instances can be used to solve it more quickly (2SAT vs. SAT).
* Sometimes certain parameters of problem instances can be used to solve the problem faster (CLIQUE with $k=10$ is solvable in ${\binom{n}{k}}$ ~ $n^k$).
* Heuristics can be used to find a good enough solution: Backtracking, genetic algos, local search...
* Approximation algorithms (like your suggestion) can be used to find sub-optimal but good enough solutions.

An example of an approximation algorithm can be given for MAX-2SAT. MAX-2SAT is the problem of finding the maximum number of clauses that can be simultaneously satisfied by an assignment to the variables of a 2-CNF (a boolean formula in conjunctive normal form with clauses that contain 2 literals). Each variable in a boolean formula can either be $0$ or $1$, so we just flip a coin to decide whether we assign $0$ or $1$ to each variable. With this approach, we can easily find an assignment to each variable that satisfies up to 75% of the clauses!

None of these techniques contradict our assumption that NP-complete problems have been proven to be unsolvable in polynomial time.
> 4 votes

# Answer
Here's an example: Take a graph with n nodes. Determining whether there is a cycle of length n is NP-complete. Now take "travelling salesman without triangular equation". Set the distance to 1 if two nodes are connected, and n^2 if they are not connected. If there was a cycle then the shortest tour has length n, otherwise it has length at least \> n^2. Our inability to find an approximation comes from the fact that if there was a cycle, then there just isn't any near-optimal solution.

Or take "minimum number of colors required to color a planar graph". This is trivially solved if 0, 1 or 2 colors are needed, NP-complete to determine that the solution is 3, and there is always a way to color a graph with four colours. If the solution is 3, there is no approximation less than 33 percent away.
> 2 votes

# Answer
There are some NP-complete problems for which it has been shown that even getting an approximation to the solution is already NP-complete. I don't remember details now. It does depend on the problem, others are amenable to getting approximations efficiently.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, time-complexity
---


title: What is Finite Automata Bowl?

text:
# Question
Title: What is Finite Automata Bowl?
I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the temporal order of the stack. So instead of being restricted to only removing the top symbol of the stack, you can remove any symbol of the bowl.

The question is, does there exist a context-free language that is *not* accepted by an FAB?

# Answer
If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered finite because of the Bowl.

All you can do with the bowl symbols is to count, with a different count for each symbol.

So the bowl automaton is only a multicounter automaton, which has been analyzed a long time ago as counter machine, with many variants.

There seems to be significant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as powerful as Turing machines (TM), up to proper initial encoding of the problem ... which is a significant constraint. Read the proof in Wikipedia. But this constraint is apparently only when the input of the TM is to be encoded in the counters. This result appears in a 1967 book by Minsky, *Computation*. For off-line TM, taking their input on a separate tape, there is no such problem.

So all recursively enumerable languages can be recognized by a two symbol Bowl Automaton, including of course the CF languages. The simpler case of the PDA is worth examining, as it is an important step of the general proof.

The PushDown Automaton is an off-line machine since the input is from a normal read-only tape. The encoding suggested in the proof (step 2 of the proof) TM allows it to simulate a PDA with only two bowl symbols. The gist of the construction is to consider the PDA stack as representing a number in base $n$, where $n$ is the cardinality of the stack alphabet. Instead, you use one bowl symbol to represent the stack number in unary notation (just use a very big bowl). Actually, you simplify by first using a stack with only two symbols, to use binary notation before making it unary in the bowl. The remaining bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is quite simple.

So **each CF language is accepted by some Bowl Automaton**, actually even restricted to two bowl symbols (but a very large number of each :-)

The construction is simpler for the simulation of a PDA stack. But since a TM can be simulated with two stacks and a finite control, a TM can be simulated by a Bowl Automaton. An the four counters (2 for each stack) can actually be reduced to two.
> 4 votes

# Answer
In your question it sounds like you have a stack but are allowed to see all of it at once and pop at any level, but your comment says order can't be distinguished at all. Going with the second characterization: as Jackie said, a FAB can't recognize any context-free language for which order matters.

Either way, I think an FAB can also recognize the *non context-free* language of strings with the same number of a's b's and c's. It could just store the whole string and then pop one a, then one b, then one c, in a cycle, accepting if the whole "stack" can be matched up in this way or rejecting if some cycle can't be completed because there is too many of some symbol.
> 0 votes

---
Tags: terminology, reference-request, automata, finite-automata
---


title: Quick calculation for $(x^y) \bmod z$

text:
# Question
Title: Quick calculation for $(x^y) \bmod z$
What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers? Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.

# Answer
> 4 votes
Here is the quickest way I can think. Assume first that $x$ and $z$ are coprime.

1. Factor $z = \prod\_i p\_i^{a\_i}$ and calculate $\varphi(z) = \prod\_i p\_i^{a\_i-1} (p\_i-1)$.
2. Compute $x' = x \pmod{z}$ and $y' = y \pmod \varphi(z)$, so that $x^y \equiv x'^{y'} \pmod{z}$.
3. Compute $x'^{y'} \pmod{z}$ using repeated squaring.

Here is what to do in the more general case.

1. Factor $z = \prod\_i p\_i^{a\_i}$ and calculate $\varphi(z) = \prod\_i p\_i^{a\_i-1} (p\_i-1)$.
2. Compute $x' = x \pmod{z}$, $y' = y \pmod \varphi(z)$, $g = gcd(x',z)$, $h = x'/g$, so that $x^y \equiv g^{y'} h^y \pmod{z}$.
3. Compute $g^{y'} \pmod{z}$ using repeated squaring.
4. Factor $h = \prod\_i p\_i^{b\_i}$.
5. Compute $c\_i = \min(a\_i,yb\_i)$. This is easy since we only need to explicitly compute $yb\_i$ when $y \leq a\_i$.
6. Compute $\prod\_i p\_i^{c\_i} \equiv h^y \pmod{z}$.
7. Compute $g^{y'} h^y \equiv x^y \pmod{z}$.

# Answer
> 5 votes
Computation with large integers is one of the topics of Knuth's "Seminumerical Algorithms" (volume 2 of "The Art of Computer Programming"). Results in elementary number theory, like the properties of modular arithmetic, the Chinese Remainder Theorem, Fermat's little theorem/Euler's theorem are critical here.

As commented, this operation is central in cryptography, like RSA. Doing this operation efficiently for fixed $y$ and $z$ are critical.

There are several efficient libraries for doing multiprecision computation, perhaps the most known is GMP, which in turn is used in several languages that offer "big integers." Most computer algebra systems offer computation with large integers.

---
Tags: integers, number-theory, arithmetic
---


# Question
Title: Difference between diameter of a graph vs longest path of the graph
I am curious what is the difference between diameter of a graph vs longest path of a graph. I just read diameter of a graph can be solved using Floyd warshall in O(V^3) while longest path can be calculated in O(V + E) using topological sort.

# Answer
> 10 votes
The longest path of the graph is the longest path between any two vertices. There may be several with the same longest length.

Since you are comparing with the diameter, which is an integer, you probably mean the length of the longest path

The diameter is the length of the longest of the shortest path between any two vertices. That means that you compute the shortest path for any pair of vertices, and take the longest one of them.

The distance between two vertices being the shortest path, the diameter is the longest distance between two vertices,

# Answer
> 6 votes
In general, they are not the same thing. Also, for the general graph, it is easy to compute the diameter, but hard to compute the longest path. In the graph below, the diameter is 4. A path from $6$ to $2$ is highlighted, which is of length 4.

However, there is a longer (simple) path from $6$ to $2$ of length 5.

# Answer
> 4 votes
Topological sort is only defined for directed acyclic graphs so you can't use it to find longest paths in general directed graphs or undirected graphs. Finding the longest path in an undirected graph (in the whole graph or between two specific vertices) is **NP**-hard. I assume this holds for cyclic directed graphs, too.

Note that it's "unfair" to compare Floyd Warshall with an algorithm for finding the longest single path in a graph. Floyd Warshall computes $\Theta(n^2)$ different things (the length of the shortest path between every pair of vertices) so it's running time is, in a sense, $O(n)$ per answer.

---
Tags: graphs, terminology
---


# Question
Title: Is the language $\{ a^pb^q \mid p, q \text{ are prime} \}$ regular?
I am interested to know whether that language $$ L = \\{ a^pb^q \mid p, q \text{ are prime} \\} $$ is regular. How do you prove that it is not regular?

# Answer
This language is not regular, the easiest way to see this is to use the Pumping Lemma, see http://en.wikipedia.org/wiki/Pumping\_lemma\_for\_regular\_languages Alternatively, you could also use the Myhill-Nerode theorem, see http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode\_theorem

To give you some more details, assume (towards a contradiction) that

$$ L = \\{ a^pb^q \mid p,q \text{ are prime} \\} $$

was regular. By the Pumping Lemma, there is an integer $l \geq 1$ such that every word $w \in L$ of length at least $l$ can be written as $w=xyz$ with

1. $y$ is not the empty string,
2. $xy$ has at most length $l$,
3. $xy^iz \in L$ for every $i \geq 0$.

Now we can pick $w$ as $a^2b^q \in L$ for some prime $q \geq l$. This word meets the conditions of the Pumping Lemma. Without loss of generality we can assume that $xy=a^2b^k$ for some $k \geq 1$ (the case for $xy=a$ or $xy=aa$ is even simpler). Now, either $y=a^jb^k$ for some $j \geq 1$ or $y=b^k$. But in both cases, we immediately see that we can choose $i \geq 0$ such that $xy^iz \not\in L$, which contradicts our initial assumption that $L$ is regular, hence $L$ is not regular.
> 3 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Soft Margin Loss and Conditional Probabilities
Consider the following soft margin loss function: $\max(0, 1-yf(x))$. I have the problem of needing to compute the conditional probability $p(y|x)$ corresponding to this function and am having trouble making the connection between conditional probability and this function. I have come across a few papers (e.g. http://www.unc.edu/~yfliu/papers/lum.pdf) that say that "soft classifiers explicitly calculate the class conditional probabilities", but I do not understand how as the output of a classifier is not a probability. Can someone please explain what I am missing?

# Answer
It is not possible to consistently estimate $P(y \mid x)$ if you are learning with hinge loss. Strictly proper losses, also known as strictly proper scoring rules, are the subclass of loss functions that are consistent for probability estimation. There is now a comprehensive and rich theory of proper losses, the larger class containing strictly proper losses. Without getting far into the theory of these losses, I'll give some examples/non-examples and some properties that strictly proper losses have.

The following are strictly proper losses: squared loss (least squares), log loss (logistic regression), exponential loss (boosting). The following are not strictly proper nor even proper losses: absolute loss, hinge loss (SVM).

One reason proper losses are so important is that if a loss is proper, then it is possible to map the *edge* $y f(x)$ to a class probability in a consistent way (if we ignore regularization). This can be done by appealing to a link function corresponding to the proper loss. In the binary classification setting, a link function maps from the interval $\[0, 1\]$ to the "edge space" inhabited by $y f(x)$. Given an edge $y f(x)$, the inverse link can be used to get a probability. For strictly proper margin losses (any of the strictly proper losses listed above), you can get the link function from Corollary 14 of this paper: http://jmlr.org/papers/volume11/reid10a/reid10a.pdf. This paper also discusses the problem with hinge loss for class probability estimation.

Briefly, the problem with absolute loss and hinge loss are that if a learning algorithm believes $P(Y = 1 \mid X = x) \> 0.5$, then both these losses are minimized by maximizing the edge $y f(x)$. In contrast, for squared loss and other strictly proper losses, the loss is minimized when the edge (after passing it through the inverse link function) corresponds to Learner's believed $P(Y = 1 \mid X = x)$.
> 4 votes

# Answer
The loss function you give is the hinge loss, which is what is used by SVM. See equation (1) in the paper you link and the paragraph that immediately follows it. SVM is not a soft classifier as defined in the paper you link. Furthermore, SVMs do not estimate class probabilities, they simply define a decision boundary. If you google "estimating class probabilities svm" you'll find papers that try to do what you want. In my experience these techniques work rather poorly and if you require a class probability, you're better off using a method that estimates class probabilities. This would include things like logistic regression or neural networks (using an appropriate output and loss function of course).
> 1 votes

---
Tags: machine-learning, probability-theory, classification
---


# Question
Title: Compact representation of paths in a graph
I've a subset of the simple paths in a graph. The length of the paths is bounded by $d$.

What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the selected ones are represented?

Note that I want to use this representation in an algorithm that will iterate through this subset of paths over and over again and that I want to be fairly fast, so for instance, I can't use any standard compression algorithms.

One representation that came to my mind was representing them as a set of trees. I'm guessing though that getting it down to an optimal number of trees is NP-hard? What other representations would be good?

# Answer
> 4 votes
A Trie might do the trick: http://en.wikipedia.org/wiki/Trie

Label each edge of your graph with a letter. Then add the strings which represent paths through your graph to the trie. To fulfill the requirement that "no other paths apart from the selected ones are represented" you could leave all vertices of the trie blank, and label the edges, except when the edges leading from the root to the vertex represent one of your paths, then label the vertex with something. A bool, the number of the path under some ordering, etc.

Once you have your trie built, there are algorithms for compressing it down to an optimal (or near optimal) representation. (see the linked Wikipedia article.)

# Answer
> 2 votes
Perhaps you should have a look at succinct data structures. They are data structures that attempt to store information in space close to the information-theoretic lower bound while still preserving the ability to perform operations on them.

There are such structures for trees, dictionaries, etc. I don't recall any that would do exactly what you want but perhaps some combination or modification of them would help you.

# Answer
> 1 votes
Depending on the complexity and the pre/post processing required for your algorithm, perhaps the simplest option is the way. You could trivially represent them as arrays, and save them compressed in a HDF5. This library is equipped with some fast compression algorithms, so that reading and writing compressed data may be even faster than uncompressed.

Here are some plots:

Sequential access time per element for a 15 GB EArray and different chunksizes:

Decompression speed using Blosc on PyTables:

And, if they are bounded in lenght, you could store them in a table, and thus probably gaining a bit more space. And when retrieving them from memory, you have them already in a very convenient form to apply your algorithm.

---
Tags: graphs, data-structures
---


title: Expected number of updates of minimum

text:
# Question
Title: Expected number of updates of minimum
I came across the following problem in a exam.

We choose a permutation of n elements $\[1,n\]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ initially. Now during our inspection if we see a smaller value than MIN, then MIN is updated to the new value.

For example, if we consider the permutation,

$$5\ 9\ 4\ 2\ 6\ 8\ 0\ 3\ 1\ 7$$ the MIN is updated 4 times as $5,4,2,0$. Then the expected no. of times MIN is updated?

I tried to find the no. of permutations, for which MIN is updated $i$ times, so that I can find the value by $\sum\_{i=1}^{n}iN(i)$, where $N(i)$, is the no. of permutations for which MIN is updated $i$ times.

But for $i\geq2$, $N(i)$ is getting very complicated and unable to find the total sum.

# Answer
The trick is to use *linearity of expectation*. Let $E\_k$ be the event that the $k$th input is a left-to-right minimum (i.e., requires an update), and let $X\_k$ be an indicator variable for $E\_k$, that is, $X\_k$ is $1$ if $E\_k$ happens and $0$ otherwise. Let $U = X\_1 + \cdots + X\_n$ be the number of updates. The expected number of updates is $$ \mathbb{E}\[U\] = \sum\_{k=1}^n \mathbb{E}\[X\_k\] = \sum\_{k=1}^n \Pr\[E\_k\]. $$ It remains to compute $\Pr\[E\_k\]$. We can construct a random permutation $\pi$ of $\[n\] = \\{1,\ldots,n\\}$ in the following way: take a random permutation of $\[n\]$, and randomly permute the first $k$ elements. This shows that the probability that $\pi(k) = \min(\pi(1),\ldots,\pi(k))$ is exactly $1/k$, and so $\Pr\[E\_k\] = 1/k$. All in all, we get $$ \mathbb{E}\[U\] = \sum\_{k=1}^n \Pr\[E\_k\] = \sum\_{k=1}^n \frac{1}{k} = H\_n, $$ the $n$th Harmonic number. It is well-known that $H\_n = \ln n + \gamma + O(1/n)$ (Wikipedia contains the entire asymptotic expansion).

We can also compute the variance in this way: $$ \begin{align\*} \mathbb{E}\[U^2\] &= \sum\_{k=1}^n \mathbb{E}\[X\_k^2\] + 2\sum\_{k=1}^{n-1} \sum\_{\ell=k+1}^n \mathbb{E}\[X\_k X\_\ell\] \\ &= \sum\_{k=1}^n \Pr\[E\_k\] + 2\sum\_{k=1}^{n-1} \sum\_{\ell=k+1}^n \Pr\[E\_k \land E\_\ell\], \end{align\*} $$ where $\land$ is logical AND. We already know that $\Pr\[E\_k\] = 1/k$. In order to compute $\Pr\[E\_k \land E\_\ell\]$ (where $k \< \ell$), we follow the same route as before. With probability $1/\ell$, $\pi(\ell)$ is a left-to-right minimum. Given that, the probability that $\pi(k)$ is a left-to-right minimum is $1/k$. Therefore $\Pr\[E\_k \land E\_\ell\] = 1/(k\ell)$, and so $$ \begin{align\*} 2\sum\_{k=1}^{n-1} \sum\_{\ell=k+1}^n \Pr\[E\_k \land E\_\ell\] &= 2\sum\_{k=1}^{n-1} \sum\_{\ell=k+1}^n \frac{1}{k\ell} \\ &= \left(\sum\_{k=1}^n \frac{1}{k}\right)^2 - \sum\_{k=1}^n \frac{1}{k^2} \\ &= H\_n^2 - \sum\_{k=1}^n \frac{1}{k^2}. \end{align\*} $$ Therefore $$ \begin{align\*} \mathbb{E}\[U^2\] &= H\_n + H\_n^2 - \sum\_{k=1}^n \frac{1}{k^2}, \\ \mathbb{V}\[U\] &= H\_n - \sum\_{k=1}^n \frac{1}{k^2} = \ln n + \gamma - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right). \end{align\*} $$ We can compute all other moments in a similar way using (essentially) the inclusion-exclusion principle and the formula $$ \mathbb{E}\[U^d\] = \sum\_{i\_1,\ldots,i\_d=1}^n \prod\_{i \in \\{i\_1,\ldots,i\_d\\}} \frac{1}{i}. $$ If we are careful enough then we can probably establish the asymptotic normality of $U$.
> 7 votes

# Answer
The quantity you are interested in is known as the average number of *left-to-right minimima* and is well-studied, e.g. by Knuth \[1, 1.2.10\].

As it turns out, the answer is that

$\qquad\displaystyle H\_n - 1 \sim \ln n$

updates happen on average. Find the details in Knuth's book, I can't do a better job explaining than he does. I'll say that the approach he uses is well worth knowing.

---

1. The Art of Computer Programming, Volume 1 by D. E. Knuth (1997, 3rd ed)
> 5 votes

---
Tags: algorithm-analysis, runtime-analysis, search-algorithms
---


title: Variable programs and variable data

text:
# Question
Title: Variable programs and variable data
I'm reading "Sets for Mathematics" by Lawvere, and he uses the following metaphor at the end of section 1.3: "we will see...how any abstract set F of the right size can act as mappings between given abstract sets. (For example, in computers variable programs are just a particular kind of variable data.)"

The internet seems silent on these so called "variable programs". Has anyone heard of them/has an accessible introduction (at an introductory graduate level)? Extra bonus points if you can explain how this relates to sets and functions.

# Answer
It seems that the authors refer to "functions as first-class variables". In functional languages you have variables which store functions. You can think of them as *program variables* since they store programs. On the other hand, if you look at how the programs are stored physically, then you get unstructured *variable data*.

Let's be more concrete. The (somewhat functional) programming language Python has a function `eval` which takes as argument a Python program. Consider the following code:

```
prog = "sum([x for x in range(5)])"
print eval(prog)

```

This prints $10$ (since in Python `range(5) = [0,1,2,3,4]`). Here `prog` is a *program variable* since it stores a program. On the other hand, `prog` is also just a mundane string (*variable data*). From the point of view of Python, unless you try to evaluate it ("cast" it into a program), `prog` is basically just a string.

If we use an enumeration of programs like in recursion theory, then program variables really are unstructured — they are just integers. If Python supported this convention then `prog` would be just some number with no apparent structure.

In the same way, a set-theoretic function is just another set, unless you treat it as a function. Given two sets $A,B$, we can construct the set which contains all mappings from $A$ to $B$; I don't quite understand why only the "size" (i.e., cardinality) of this set matters, but I guess you'll have to wait until Chapter 5. Perhaps they mean that with the correct encoding function, every set of the correct cardinality can be used as an *index set* for all mappings from $A$ to $B$, just like the enumeration of programs mentioned above.
> 2 votes

---
Tags: terminology, programming-languages
---


# Question
Title: Lambda Calculus: How do evaluation contexts "work"
In the pure lambda calculus, we have the inductively defined set of terms (the grammar): $$e::= x \mid \lambda x . e \mid e\_1 e\_2$$

Under the call-by-value evaluation strategy, we have the inference rules for beta-reduction and rules on how to evaluate applications (congruence rules). I am trying to understand how evaluation contexts can replace the congruence rules without actually changing the syntax of the language. Without evaluation contexts, we have the following:

$$ \frac{e\_1 \rightarrow e\_1'}{e\_1e\_2 \rightarrow e\_1'e\_2} $$ and $$ \frac{e\_2 \rightarrow e\_2'}{ve\_2 \rightarrow ve\_2'}. $$

This makes sense, since if we have an instance of an expression $t = (\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w$, it is clear that it is of the form $e\_1e\_2 \rightarrow e\_1'e\_2$ and thus $$(\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w \rightarrow (\lambda f . \lambda x. f x)(\lambda z .z)\lambda w.w$$

If we replace the congruence rules with evaluation contexts: $$E::= \[\cdot\] \mid Ee \mid vE$$ then we need only a single rule to express the congruence rules of the language: $$ \frac{e \rightarrow e'}{E\[e\] \rightarrow E\[e'\]}. $$

I am confused as to how evaluation contexts can tell us how to evaluate the expression $t$ from above without changing the syntax of the language. I don't understand how the evaluation context "works" without rewriting $t$ as

$$E\_t = (\lambda f . \lambda x. f x)\[\cdot\]\lambda w.w$$

where $t = E\_t\[((\lambda y .y)\lambda z .z)\]$. There is no obvious a priori reason to evaluate $t$ under call-by-value without knowledge of $E\_t$. I really have no idea where I am going wrong. Can someone help correct my thinking?

# Answer
> 10 votes
The subtlety lies in where the distinction between language and meta-language is made. As René Magritte put it:

$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$ is a lambda-term, written in the syntax for lambda-terms. Let's call this lambda-term $t$. Let $M$ be the lambda-term $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z))$. I can write $t = M \\, (\lambda w.w)$ (and this is a true equality): all I did was to give a name to a subterm. If you consider the right-hand side of this equality “$M \\, (\lambda w.w)$”, it is not written in the syntax of lambda-terms; it is written in a mathematical notation where we allow a letter to stand for a lambda-term.

When we write a rule like $$ \frac{e\_2 \to e\_2'}{v \\, e\_2 \to v \\, e\_2'} $$ it states the following axiom: for any lambda-terms $e\_2$ and $e\_2'$ and any value $v$, if $e\_2$ reduces to $e\_2'$ then $v \\, e\_2$ reduces to $v \\, e\_2'$. Here we're again using meta-notations (i.e. mathematical notations to reason about a language): the arrow $\to$ to express the reduction relation; metavariables where a letter indicates the sort ($e$ for lambda-terms, $v$ for values) and subscripts and primes distinguish between metavariables of the same sort; the fraction notation to write an inductive axiom.

When we write the rule $$ \frac{e \to e'}{E\[e\] \to E\[e'\]} $$ then again $E\[\cdot\]$ is a meta-notation, part of the meta-language and not of the lambda-term syntax. The rule means: for any lambda-terms $e$ and $e'$ and any evaluation context $E\[\cdot\]$, if $e$ reduces to $e'$ then $E\[e\]$ reduces to $E\[e'\]$.

If we call the context $(\lambda f. \lambda x. f x)\[\cdot\] (\lambda w.w)$ by the (meta-)name $E\_t$, then $t = E\_t\[(\lambda y.y)(\lambda z.z)\]$. Again, this is an equality between two lambda-terms, i.e. the same lambda-term is on both sides of the equal sign. What we have on the left and on the right are two different meta-notations for the same lambda-term $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$: one that uses a name that we gave to it, another that's a bit more complicated involving a context that we gave a name to.

Given the term $t$, how do you find how it can reduce?

* With the notation using multiple rules, you have to find a deduction tree (in general — here the derivation is linear, so you merely have to find a chain leading to an axiom).
* With the notation using evaluation contexts, you have to find a suitable evaluation context.

The grammar of evaluation contexts follows the structure of the evaluation rules, so these are in fact not really two methods but two different ways of expressing the same definition.

To understand this, I strongly recommend the following exercise: in your favorite language, implement lambda-term call-by-value evaluation in a straightforward way, with a type representing lambda-terms and a function performing one reduction step.

---
Tags: programming-languages, lambda-calculus, semantics
---


# Question
Title: What is average number of cycles in an undirected ordered graph of size n?
What is average number of cycles in an undirected ordered graph of size $n$? I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.

# Answer
Hint: Suppose that there are $Z\_m$ cycles of length $m$, and that $p\_m$ is the probability that a specific cycle of length $m$ is in the graph. Then the expected number of cycles is $$ \sum\_{m=3}^n Z\_m p\_m $$ due to linearity of expectation.

Here is the entire calculation. In the $G(n,p)$ model, in which each edge is present with probability $p$ independently, clearly $p\_m = p^m$. The number of ordered $m$-tuples of points is $n!/(n-m)!$. Each cycle of length $m$ is described by $2m$ such tuples: choose a starting point and an orientation. Therefore the total number of cycles of length $m$ is $n!/2m(n-m)!$, and the expected number of cycles is $$ E = \sum\_{m=3}^n \frac{n!}{2m(n-m)!} p^m. $$

In order to estimate this number, let's find the largest term. The ratio of two successive terms is roughly $$ \frac{p^{m+1}}{(n-m-1)!} \frac{(n-m)!}{p^m} = (n-m)p. $$ When $p$ is constant, we see that the most important term corresponds to $m = n$, namely $n! p^n/(2n)$, and we deduce that for large enough $n$, the expected number of cycles satisfies $$ 2(n-1)! p^n \leq E \leq 2n! p^n. $$
> 6 votes

---
Tags: graphs, combinatorics
---


# Question
Title: Can we test whether two vertices are connected in time linear in the number of nodes?
Consider the problem:

> Given an undirected graph and two of its vertices, is there a path between them?

I often read that this problem can be solved in linear time in the number of vertices! I am not sure why this claim holds.

Can this really be done in linear time (not amortized) without preprocessing?

# Answer
It is not possible to decide $s$-$t$ connectivity in $O(n)$, in the adjacency matrix model. In fact, here is an $\Omega(n^2)$ lower bound. Let $|S| = |T| = n/2$ be a partition of the vertex set, and choose some $s \in S$ and $t \in T$. Consider the graph in which $S$ and $T$ are both cliques. In this graph $t$ is not reachable from $s$. If we add any edge from $S$ to $T$, then $t$ is reachable from $s$. A simple adversary argument shows that any algorithm that decides where $t$ is reachable from $s$ has to potentially check all $|S| \cdot |T| = n^2/4$ potential edges: if it didn't query some edge $(x,y)$, then it wouldn't be able to distinguish the case in which there is no edge from $S$ to $T$ (and so $t$ is not reachable from $s$) from the case in which $(x,y)$ is the unique edge from $S$ to $T$ (and so $t$ is reachable from $s$).
> 8 votes

# Answer
Your sources are sloppy or you misinterpret something. In general, deciding reachability requires time $\Omega(n+m)$ (assuming adjacency lists). This is linear in the *input size* (which is in $\Theta(m)$), however, so saying that reachability is solvable in linear time \[in input size, which is the default\] is correct.

For a proof of this lower bound, see Yuval's answer; the argument remains the same but we conclude that the algorithm must traverse all adjency lists of all nodes in $S$, which contain in total $\Omega(n^2)$ many entries.
> 5 votes

# Answer
Perhaps your source text is dealing with undirected graphs that fulfill some additional structural requirements. For example, for a tree, $m = n - 1$. Therefore, an algorithm that takes $O(n+m)$ time on a general graph actually runs in $O(n)$ time on trees since $n \> m$.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: What data is stored in the symbol table for a number token?
I'm reading the Dragon Book. The following is from the start of Section 3.1.3.

> When more than one lexeme can match a pattern, the lexical analyzer must provide the subsequent compiler phases additional information about the particular lexeme that matched. For example, the pattern for token **number** matches both 0 and 1, but it is extremely important for the code generator to know which lexeme was found in the source program. Thus, in many cases, the lexical analyzer returns to the parser not only a token name, but an attribute value that describes the lexeme represented by the token; the token name influences parsing decisions, while the attribute value influences translation of tokens after the parse.

From what I understand the symbol table stores the variable name and the some details like the type, scope etc. So if a character `0` is found by the lexical analyzer, it matches the pattern for a number so it uses the token name `number` so the token becomes `<number, attrb>`.

As per the snippet I have cited above, I don't understand what data is stored in the symbol table for numbers. Is the value of the number stored in the symbol table?

# Answer
Typical lexers will return a sequence of pairs, where the pair consists of the token type and an optional value. For a token such as `12345`, the token type will be something like "number" and the value will be 12345. If the lexer only emitted the information that there was a numeric constant in the input, then the following phases of the parser would have no way to know which number it was, and that is obviously important.

I don't understand why you started talking about the symbol table in the end of your question, and I think you may be confused. The quotation you gave says nothing at all about the symbol table, which usually belongs to a later phase of compilation. A symbol table maps symbols (that is, names) to values. The quotation in your question is about tokens, not symbols. Tokens are not usually stored in a symbol table, and there is no reason to store numbers in a symbol table. Typically a parser will have a stack, and will push whole tokens onto the stack, and pop them off again as needed.
> 2 votes

# Answer
What the compiler stores in the symbol table is whatever it needs to do its job of code generation. The value of the number certainly is a must. Other data might include stuff like small/large (small numbers might have shorter representations, or be included inline in instructions).
> 1 votes

# Answer
No, the symbol table could only keep an "identifier" for the number. E.g. if 56 it's the first integer met then a possible id could be "iconst\_1".

The numbers, as number are stored either in the memory or the Abstract Syntax Tree (AST). If numbers appear as initializations (e.g. int array\[3\] = {0} in C), then they initialize the array in where you allocated memory. If they appear in expressions they are the leafs of the AST:

E.g. a = 12 + 34.5 is

```
    =
  /   \
 a     +
     /   \
 iconst  rconst
 = 12    = 34.5

```
> 1 votes

---
Tags: compilers, parsers, lexical-analysis
---


# Question
Title: How does Paxos maintain the promise that future proposal will not break the current chosen value without knowing the future?
I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was trying to understand page 4, specifically, the following paragraph:

"To maintain the invariance of $P2^c$, a proposer that wants to issue a proposal numbered n must learn the highest-numbered proposal with number less than n, if any, that has been or **will be accepted by each acceptor in some majority of acceptors**. Learning about proposals already accepted is easy enough; predicting future acceptances is hard. Instead of trying to predict the future, the proposer controls it by extracting a promise that there won’t be any such acceptances. In other words, the proposer requests that the acceptors not accept any more proposals numbered less than n. This leads to the following algorithm for issuing proposals."

Where condition $P2c$ is:

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that

(a) no acceptor in S has accepted any proposal numbered less than n, or

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

I was specifically confused about the section I have in bold. I was confused why, if we want to develop some hypothetical consensus distributed algorithm, why do we need to know about higher sequence numbers that have not happened? What is the intuition behind that?

Sorry if my title is a little strange, I was not sure what was a good title for the question.

---

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

# Answer
> 2 votes
The bold section is saying that before proposing a value know if a value is accepted or if there is a higher proposal number that is chosen by one of the majority. If there is a higher proposal number, the proposer needs to propose a higher number than that is already proposed. If a value is already accepted then majority should know if a value is accepted. The proposer accepts the value. The majority is because two majorities always overlap.

---
Tags: distributed-systems
---


# Question
Title: How to read edge labels like "01, 1" on a state diagram?
Is this state machine a moore machine or a mealy machine? I am confused because the states have outputs and the transitions have output based on the input. I tried making a state table but I think its wrong. Can anyone provide the state machine?

# Answer
> 1 votes
Since the states define the output, it's a Moore machine.

The edge labels can be understood as follows: an edge $A \xrightarrow{w\_1, \dots, w\_k} B$ with $w \in \Sigma^\*$ means that you can transition from $A$ to $B$ reading any of the *words* $w\_1, \dots, w\_k$.

Essentially, it's just a way to compact automata. As an exercise, you can expand the edges and see what you get. It's clear that this compactification is valid for finite automata, even if you add output (if you allow state output $\varepsilon$).

---
Tags: terminology, automata, finite-automata
---


# Question
Title: Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm?
I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and operations such as swap are ignored. Link to selection sort analysis. Please help me understand.

# Answer
There are 2 major reasons:

1. For most algorithms the number of other operations can be bounded by a multiple of the number of comparisons (i.e. runtime in $\mathcal{O}(\\#comparisons)$). This is because e.g. a swap does not occur without a prior comparison requiring this swap (depends on algorithm).
2. Using comparisons you can prove an $\mathcal{O}(n \log n)$ lower bound for any comparison based sorting algorithm on $n$ elements.
> 1 votes

# Answer
```
...while calculating time complexity and operations such as swap are ignored

```

You are wrong. All the operations are taken into account when calculating time complexity. But as loops are dominant compared to other operations, we ignore other operations and only consider dominant operations(Because for large input value, cost of all other operations are much smaller than the dominant operations) .

As an example with selection sort: When you consider all statement costs into account then you get a function $f(n)=an^2+bn+c$ ($a$,$b$ and $c$ are constants and depend on machine architecture). Here dominant term is $an^2$.So we can say Time complexity of selection sort $O(an^2)$.We also ignore leading terms coefficient $a$ ,as $a$ does not change the rate of growth.

I suggest you to study some standard algorithm textbook to understand it properly.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting
---


title: Proof of P ⊆ NP

text:
# Question
Title: Proof of P ⊆ NP
What is the proof of P ⊆ NP? I cannot happen to find a good explanation for it. I read that the `verifier` will just ignore the proof and accept any proof if the solution is YES and reject all proofs if the answer is NO. I'm also unclear about verifier.

Definition of P and NP I follow:

P: a problem 'Q' is said to be in P if there exists an efficient (polynomial worst-case time) algorithm for solving the problem. E.g.- "is a given natural number 'x' even?".

NP: a problem 'Q' is said to be in NP if there exists efficient verifiers (an algorithm for verifying if a given proof is correct).

# Answer
It's much easier to just define **P** as the class of languages decided by polynomial-time deterministic Turing machines and **NP** as the languages decided by polynomial-time nondeterministic Turing machines. Since the deterministic machines are a subset of the nondeterministic ones (the subset that happens to have exactly one option to nondeterministic "choose" from at each step), it's **P** $\subseteq$ **NP** is trivial.

If you want to define **NP** using verifiers, it's not much harder: for a problem in **P**, the instance is its own certificate. Because you can compute a solution in polynomial time, you can certainly verify whether or not one exists in polynomial time.
> 5 votes

---
Tags: complexity-theory, decision-problem, complexity-classes
---


# Question
Title: How does an Operating System without kernel mode work?
Andrew S. Tanenbaum, in his book *Modern Operating Systems (3rd Edition)*, states that the distinction between operating system software and normal (user mode) software can sometimes be blurred in embedded systems (which **may not have a kernel mode**).

> Can someone please describe more what an OS without a kernel mode looks like and how it works?

Thank you.

# Answer
It's more like an operating system without a *user* mode. In many embedded systems there is only one (or a small number) of "applications" and so the application is just built right into the lowest-level of the system.

Desktop/server operating systems provide many services, some of them unnecessary for embedded systems.

At the lowest level you typically need some wrapper routines for accessing various physical devices (serial buses, sensors, actuators) and interrupt service routines for devices that need asynchronous attention. In a desktop/server OS the device registers or memory mapped locations for accessing the device registers would be protected/hidden from the applications, but in an embedded system you can trust the application writer.

As you go up the stack some services may be necessary for a particular embedded system, but those can be provided by library routines. For example, you might need a file system, but you just implement this as a library that provides `open`, `read`, `write`, `close`, `make_directory` and such routines to the rest of the system.

Your embedded system may (or may not) need to be able to load and execute programs not built into the kernel. Again, you can provide the ability to load the executable part of a file off the disk into memory and then jump to some start location.

Your embedded system may (or may not) need dynamic memory allocation. This just means that all the memory not otherwise in use is managed by a library routine (usually called `malloc` and `free` or something similar).

Your embedded system may (or may not) need multiple threads. Many embedded systems manage the threads *cooperatively*. That means that there are library routines to allocate and initialize memory for a new thread, and then the library selects one thread to run for awhile and when the thread calls some function (often called `yield`) this jumps back to the thread management library, which then selects a different thread to run and performs any necessary book-keeping. This can be taken a step further by making the thread library *preemptive* (an interrupt handling routine calls the library's `yield` routine on a timer interrupt if the current thread doesn't call it itself.)

Since you know the apps that are running (and trust their authors) you generally don't bother with the hardware expense of different protected address spaces. Similarly you generally don't bother with virtualizing the memory (using the disk or SSD to make the memory look larger than it really is.)
> 11 votes

---
Tags: operating-systems
---


title: Optimality of A*

text:
# Question
Title: Optimality of A*
I read in the artificial-intelligence book of Russel and Norvig that The tree-search version of A\* is optimal if heuristic function is admissible, while the graph-search version is optimal if heuristic function is consistent(monotone). An admissible heuristic is one that never overestimates the cost to reach the goal. A heuristic $h(n)$ is consistent if, for every node $n$ and every successor $n'$ of $n$ generated by any action $a$, the estimated cost of reaching the goal from $n$ is no greater than the step cost of getting to $n'$ plus the estimated cost of reaching the goal from $n'$ : $h(n) ≤ c(n, a, n') + h(n')$.

My question is about this graph and heuristic.

Suppose this graph is a state space of a problem in Artificial intelligence. $A$ is the start node(initial state),and $D$ is the goal. Numbers on the edges are path costs. Numbers on the nodes are value of heuristic function for this problem. I think this heuristic function is consistent. So A\* can find the optimal path from start to goal.

```
step 1: g(A)=0, h(A)=5, so f(A)=5
        Expand A : B, C
        add A to close list.
        add B and C to open list.

step 2: g(B)=10, h(B)=1, so f(B)=11
        g(C)=1, h(C)=8, so f(C)=9
        f(C) < f(B) so:
            Expand C : D
            add C to close list
            add D to open list.

step 3: g(D)=1+16=17,h(D)=0, so f(D)=17
        f(B) < f(D) so:
            Expande B : nothing because D is already in open list.

step 4: Just D in open list so
             Expand D : D is goal

Result: path:ACD, cost=17

```

A\* found the path ACD but optimal path is ABD.

# Answer
> 3 votes
The heuristic is both admissible and consistent. However, the algorithm *has* found the path ABD, not ACD as you state. At step 3, although expanding B doesn't add any new nodes to the open list, it does update node D with the information that the cheapest route to it is via B.

To your description of the stages of the search, you should add the following actions, after updating the open and closed lists:

```
step 1: note that the cheapest path to B is from A
        note that the cheapest path to C is from A

step 2: note that the cheapest path to D is from C

step 3: note that the cheapest path to D is from B (not C)

```

After step 2, the algorithm believes that the cheapest path to D is via C. However, at step 3, it finds a cheaper path via B and updates its belief.

---
Tags: algorithms, artificial-intelligence, search-algorithms
---


# Question
Title: Min-entropy of a random pre-image of a random function
I am facing hard time understanding min-entropy.

Fix $v \in \\{0,1\\}^{n/2}$, let $F\colon \\{0,1\\}^n \to \\{0,1\\}^{n/2}$ be chosen randomly, and let $X\_v$ be a string chosen uniformly at random among $F^{(-1)}(v)$ (or a special string $\epsilon$ if $F^{(-1)}(v) = \emptyset$). We want to compute the probability that $H\_\infty(X\_v) \leq n/4$ (over the choice of $F$), where $H\_\infty(X\_v)=-\log(\max\_{x}\\{\Pr\[X\_v=x\]\\})$ is the *min-entropy* of $X\_v$.

It's not obvious what approach is needed to solve such things! It would be helpful if one could explain where to start...

# Answer
Since $X\_v$ is a random variable which is uniformly distributed over its support $F^{-1}(v)$, its min-entropy depends only on the size of the support (and it equals the entropy). The min-entropy is at most $n/4$ if and only if $|F^{-1}(v)| \leq 2^{n/4}$. Now $|F^{-1}(v)|$ is binomially distributed $\mathrm{Bin}(2^n,2^{-n/2})$, since for each string $x \in \\{0,1\\}^n$, the probability that $F(x) = v$ is $2^{-n/2}$. Therefore you are interested in bounding $$ \Pr\[\mathrm{Bin}(2^n,2^{-n/2}) \leq 2^{n/4}\]. $$ You can obtain a good bound on this event, which is rather unlikely, using Chernoff's bound or Hoeffding's bound. Let us know if you encounter any difficulties.
> 1 votes

---
Tags: probability-theory
---


# Question
Title: executing threads with no synchronization
suppose Threads 1 and 2 are executing concurrently with shared integer variables A, B, and C. Thread 1 executes:A=4, B=5, C=B-A; Thread 2 executes: A=3, B=6, C=A+B;

I'm trying to find what can the possible values of C be after execution of this fragment when synchronization is not implemented.

I know if there is no synchronization then the reads see writes that occur later in the execution order and it will be counter intuitive ( execution will be happens-before consistency)

I am confused what can be the possible values of C. Can the possible values for C be 1,2,3,8,9,10 after substituting the all possible values for A & B from both thread 1 and thread 2 for C=B-A & C=A+B

# Answer
> 1 votes
Hint: Let $C = B \pm A$ be the final instruction being executed. Clearly $A \in \\{3,4\\}$ and $B \in \\{5,6\\}$, and this shows that $C \in \\{1,2,3,8,9,10\\}$. For the other direction, show that by carefully scheduling both threads, you can choose which of $C = B \pm A$ is executed last, and choose the value that $A$ and $B$ get prior to that instruction being executed.

---
Tags: threads
---


# Question
Title: Determine if two edges of a graph cross?
Is there a standard way to check if two edges of a graph cross? I'm having trouble coming up with an algorithm to do this, and any insight/intuition into how this can be done would be great.

To be clear, here's an example:

The algorithm would ideally return that the edge shared by 7 and 8 crosses with that between 5 and 11. Similarly for 11 and 10, 8 and 9.

# Answer
> 1 votes
If you don't care about time complexity, the following algorithm would do. Go over all pairs of edges. For each pair, we have to find whether the two segments intersect. There are two cases: the two segments have the same slope, or they don't have the same slope.

If they have the same slope, then they could be two segments on the same line, or they could belong to different lines. In the second case, they don't intersect. In the first case, this is a one-dimensional problem which is easy to solve (you can reduce it to checking whether two intervals on the real line intersect).

If the two segments have different slope, then the corresponding lines intersect at a unique point. It remains to find whether this point also belongs to both segments.

---

There are probably more efficient solutions out there, but this shows how to solve your problem in a naive way.

---
Tags: computational-geometry
---


# Question
Title: When is the AKS primality test actually faster than other tests?
I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality testing on computers.

The test has polynomial runtime but with high degree and possible high constants. So, in practive, at which $n$ does it surpass other primality tests? Here, $n$ is the number of digits of the prime, and "surpass" refers to the approximate runtime of the tests on typical computer architectures.

I am interested in functionally comparable algorithms, that is deterministic ones that do not need conjectures for correctness.

Additionally, is using such a test over the others practical given the test's memory requirements?

# Answer
Quick answer: Never, for practical purposes. It is not currently of any practical use.

First, let's separate out "practical" compositeness testing from primality proofs. The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate. For numbers under 2^64, no more than 7 Miller-Rabin tests, or one BPSW test is required for a deterministic answer. This will be vastly faster than AKS and be just as correct in all cases. For numbers over 2^64, BPSW is a good choice, with some additional random-base Miller-Rabin tests adding some extra confidence for very little cost. Almost all of the proof methods will start out (or they should) with a test like this because it is cheap and means we only do the hard work on numbers which are almost certainly prime.

Moving on to proofs. In each case the resulting proof requires no conjectures, so these may be functionally compared. The "gotcha" of APR-CL is that it isn't quite polynomial, and the "gotcha" of ECPP/fastECPP is that there may exist numbers that take longer than expected.

In the graph, we see two open source AKS implementations -- the first being from the v6 paper, the second including improvements from Bernstein and Voloch and a nice r/s heuristic from Bornemann. These use binary segmentation in GMP for the polynomial multiplies so are pretty efficient, and memory use is a non-issue for the sizes considered here. They produce nice straight lines with a slope of ~6.4 on the log-log graph, which is great. But extrapolating out to 1000 digits arrives at estimated times in the hundreds of thousands to millions of years, vs. a few minutes for APR-CL and ECPP. There are further optimizations which could be done from the 2002 Bernstein paper, but I don't think this will materially change the situation (though until implemented this isn't proven).

Eventually AKS beats trial division. The BLS75 theorem 5 (e.g. n-1 proof) method requires partial factoring of n-1. This works great at small sizes, and also when we're lucky and n-1 is easy to factor, but eventually we'll get stuck having to factor some large semi-prime. There are more efficient implementations, but it really doesn't scale past 100 digits regardless. We can see that AKS will pass this method. So if you asked the question in 1975 (and had the AKS algorithm back then) we could calculate the crossover for where AKS was the most practical algorithm. But by the late 1980s, APR-CL and other cyclotomic methods was the correct comparison, and by the mid 1990s we'd have to include ECPP.

The APR-CL and ECPP methods are both open source implementations. Primo (free but not open source ECPP) will be faster for larger digit sizes and I'm sure has a nicer curve (I haven't done new benchmarking yet). APR-CL is non-polynomial but the exponent has a factor $\log \log \log n$ which as someone quipped "goes to infinity but has never been observed to do so". This leads us to believe that in theory the lines would not cross for any value of n where AKS would finish before our sun burned out. ECPP is a Las Vegas algorithm, in that when we get an answer it is 100% correct, we expect a result in conjectured $O(\log^{5+\epsilon}(n))$ (ECPP) or $O(\log^{4+\epsilon}(n))$ ("fastECPP") time, but there may be numbers that take longer. So our expectation is that standard AKS will always be slower than ECPP for almost all numbers (it certainly has shown itself so for numbers up to 25k digits).

AKS may have more improvements waiting to be discovered that makes it practical. Bernstein's Quartic paper discusses an AKS-based randomized $O(\log^{4+\epsilon}(n))$ algorithm, and Morain's fastECPP paper references other non-deterministic AKS-based methods. This is a fundamental change, but shows how AKS opened up some new research areas. However, almost 10 years later I have not seen anyone use this method (or even any implementations). He writes in the introduction, "Is the $(\lg n)^{4+o(1)}$ time for the new algorithm smaller than the $(\lg n)^{4+o(1)}$ time to find elliptic-curve certificates? My current impression is that the answer is no, but that further results \[...\] could change the answer."

Some of these algorithms can be easily parallelized or distributed. AKS very easily (each 's' test is independent). ECPP isn't too hard. I'm not sure about APR-CL.

ECPP and the BLS75 methods produce certificates which can be independently and quickly verified. This is a huge advantage over AKS and APR-CL, where we just have to trust the implementation and computer that produced it.
> 27 votes

# Answer
The (asymptotically) most efficient deterministic primality testing algorithm is due to Lenstra and Pomerance, running in time $\tilde{O}(\log^6 n)$. If you believe the Extended Riemann Hypothesis, then Miller's algorithm runs in time $\tilde{O}(\log^4 n)$. There are many other deterministic primality testing algorithms, for example Miller's paper has an $\tilde{O}(n^{1/7})$ algorithm, and another well-known algorithm is Adleman–Pomerance–Rumley, running in time $O(\log n^{O(\log\log\log n)})$.

In reality, no one uses these algorithms, since they are too slow. Instead, probabilistic primality testing algorithms are used, mainly Miller–Rabin, which is a modification of Miller's algorithm mentioned above (another important algorithm is Solovay–Strassen). Each iteration of Miller–Rabin runs in time $\tilde{O}(\log^2 n)$, and so for a constant error probability (say $2^{-80}$) the entire algorithm runs in time $\tilde{O}(\log^2 n)$, which is much faster than Lenstra–Pomerance.

In all of these tests, memory is not an issue.

---

In their comment, jbapple raises the issue of deciding which primality test to use in practice. This is a question of implementation and benchmarking: implement and optimize a few algorithms, and experimentally determine which is fastest in which range. For the curious, the coders of PARI did just that, and they came up with a deterministic function `isprime` and a probabilistic function `ispseudoprime`, both of which can be found here. The probabilistic test used is Miller–Rabin. The deterministic one is BPSW.

---

Here is more information from Dana Jacobsen:

Pari since version 2.3 uses an APR-CL primality proof for `isprime(x)`, and BPSW probable prime test (with "almost extra strong" Lucas test) for `ispseudoprime(x)`.

They do take arguments which change the behavior:

* `isprime(x,0)` (default.) Uses combination (BPSW, quick Pocklington or BLS75 theorem 5, APR-CL).
* `isprime(x,1)` Uses Pocklington–Lehmer test (simple $n-1$).
* `isprime(x,2)` Uses APR-CL.
* `ispseudoprime(x,0)` (default.) Uses BPSW (M-R with base 2, "almost extra strong" Lucas).
* `ispseudoprime(x,k)` (for $k\geq 1$.) Does $k$ M-R tests with random bases. The RNG is seeded identically in each Pari run (so the sequence is deterministic) but is not reseeded between calls like GMP does (GMP's random bases are in fact the same bases every call so if `mpz_is_probab_prime_p(x,k)` is wrong once it will always be wrong).

Pari 2.1.7 used a much worse setup. `isprime(x)` was just M-R tests (default 10), which led to fun things like `isprime(9)` returning true quite often. Using `isprime(x,1)` would do a Pocklington proof, which was fine for about 80 digits and then became too slow to be generally useful.

You also write *In reality, no one uses these algorithms, since they are too slow.* I believe I know what you mean, but I think this is too strong depending on your audience. AKS in of course, stupendously slow, but APR-CL and ECPP are fast enough that some people use them. They are useful for paranoid crypto, and useful for people doing things like `primegaps` or `factordb` where one has enough time to want proven primes.

\[My comment on that: when looking for a prime number in a specific range, we use some sieving approach followed by some relatively quick probabilistic tests. Only then, if at all, we run a deterministic test.\]

*In all of these tests, memory is not an issue.* It is an issue for AKS. See, for instance, this eprint. Some of this depends on the implementation. If one implements what numberphile's video calls AKS (which is actually a generalization of Fermat's Little Theorem), memory use will be extremely high. Using an NTL implementation of the v1 or v6 algorithm like the referenced paper will result in stupid large amounts of memory. A good v6 GMP implementation will still use ~2GB for a 1024-bit prime, which is a *lot* of memory for such a small number. Using some of the Bernstein improvements and GMP binary segmentation leads to much better growth (e.g. ~120MB for 1024-bits). This is still much larger than other methods need, and no surprise, will be millions of times slower than APR-CL or ECPP.
> 19 votes

# Answer
this is a complicated question because of what are known as "large/galactic constants" associated with the inflections between efficiencies of different algorithms. in other words the $O(f(n))$ associated with each different algorithm can hide very large constants such that a more efficient $O(f(n))$ over another $O(g(n))$ based on asymptotic/function complexity only "kicks in" for very large $n$. my understanding is that AKS is "more efficient" (than competing algorithms) only for "much larger $n$" out of range of current practical use (and that precise $n$ is actually very difficult to calculate exactly), but theoretical improvements on the algorithm implementation (actively sought by some) could change that in the future.

saw this recent paper on arxiv which analyzes this topic in depth/detail, not sure what people think of it, have not heard reactions so far, it seems maybe a student-created thesis, but possibly one of the most detailed/comprehensive analyses of *practical* usage of the algorithm available.
> 3 votes

---
Tags: algorithms, efficiency, primes
---


# Question
Title: Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight
There is a basic result in circuit complexity that says:

> There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.

The argument is a simple counting argument on the number of boolean functions and the number of distinct circuits. See, for example, these lecture notes.

I believe it is unknown whether or not this bound is tight. That is, we don't know if the following statement is true:

> Every language can be solved with circuits of size $O(\frac{2^n}{n})$.

If this statement were true, would it have any interesting implications for complexity theory?

# Answer
> 7 votes
This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute *all* possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see below), for a total of $O(2^{2^k}) + O(2^{n-k})$. Choosing $k = \log (n - \log n)$, we obtain the desired bound.

We compute all possible functions on $k$ inputs inductively. Let $Z\_k$ be the size of a circuit computing all possible functions on $k$ inputs. There are two functions on zero inputs, so $Z\_0 = 2$. Every function $f(x\_1,\ldots,x\_k)$ on $k$ inputs can be written as $x\_k f(x\_1,\ldots,x\_{k-1},1) + \overline{x\_k} f(x\_1,\ldots,x\_{k-1},0)$, so $Z\_k = Z\_{k-1} + 2^{2^k} \cdot O(1)$. The solution of this recurrence is $Z\_k = O(2^{2^k})$.

In order to compute the decision tree, we use a similar construction: given a tree $T$ for the first $k-1$ variables, we can construct a tree for the first $k$ variables of the form $x\_k T + \overline{x\_k} T$. The recurrence we get is $W\_k = 2W\_{k-1} + O(1)$, whose solution is $W\_k = O(2^k)$.

---
Tags: complexity-theory, lower-bounds, circuits
---


# Question
Title: Can we improve the precision of IEEE floats by dropping leading zeros in the mantissa?
It seems like it would be possible to add more precision to the IEEE 32-bit mantissa system if the leading zeroes were also dropped, just like the leading 1 is dropped due to it being implicitly known.

For example, the number 17 would be represented as 0|10000100|00010000000000000000000. The leading 1 of the mantissa is always dropped, since every number in scientific notation starts with a 1. My question is why can't the leading zeroes also be dropped? If we know based on the exponent that the decimal place gets moved 4 spots, shouldn't we also be able to deduce, just like the implied 1, that all other missing bits afterwards would be 0? Granted, in this example it wouldn't make a difference, but for larger numbers, or numbers with a lot of digits past the decimal point, it seems like you would be able to get more precision the more implied bits you drop.

(As I'm typing this, I'm also realizing that you might even be able to drop the next 1 in the mantissa. If the computer knows the number of places to move the exponent, you could have as many zeroes as you want sandwiched between two implied 1's)

Does anyone know if this was ever addressed (or if I completely messed up in my calculations, and it isn't really possible to drop that many bits)?

# Answer
> 6 votes
If you drop the leading zeroes then $3,5,9,17$ and so on will all have the same representation. Don't forget that the number being represented need not be an integer.

---
Tags: floating-point, number-formats
---


# Question
Title: What are good counter-examples when training an apple classifier?
I am doing a project in order to recognize an apple. (I am using Emgucv with Visual Studio 2010 C#, if that's relevant). My project is a classification (is or is not an apple). I have 2000 images of apples but I need images for the second class.

I have read about classification using ANN but they have multiple classes but I need to recognize if image contain an apple or not. So what kind of images do I need for the second classes? I want to use background of apples like second class. Is that a good idea?

I only want that ANN recognize if a image contain a pen or not so I have 2 classes(pen and non-pen) My question is What kind of image can I use to the second class? For example My first class are images of pen and second class are images of non pen (pencil, apples, grapes, tables); is that correct?

# Answer
A standard approach is to pick a standard image bank of other images that you might run into that aren't apples, and use that as your other class. The way you figure out what kind of images you need is: figure out what kind of images your classifier might be run on, and try to make the training set as similar as possible to the kinds of images that it will be run on in production.
> 3 votes

---
Tags: machine-learning, neural-networks, data-sets
---


# Question
Title: What is this problem? Largest set of contiguous x values for which the same y value can be held
I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it. The best I've come up with is:

> Given a set of rectangles on a plane find the set(s) which allow the same `y` value for some largest contiguous set of `x` values. All rectangles are axis aligned, the same width, and do not overlap.

I find this much easier to visualize so below is an example problem instance and solution.

Edit:

We have a linear solution that has a constant factor on the order $y\_{max} - y\_{min}$ which can be pretty big. Here is an idea of the algorithm I've been trying to work out since originally posting this.

* Rectangles are already sorted by $x$ position.
* Maintain an ordered list $I$ of the intervals currently allowing a contiguous line.
* Maintain two variables $(i\_{min}, i\_{max})$ which are the min and max $y$ value of the current intersection (in the example solution $(5, 5.25)$).
* Iterate from $x\_0$ to $x\_{max}$
* At each $x$ position test if any of the current rectangle(s) intersect $(i\_{min}, i\_{max})$.

+ 1) If yes, add the rectangle to $I$ and update $(i\_{min}, i\_{max})$.
    + 2) If no, find the longest suffix of $I$ s.t. it allows overlap with current rectangle.
    + 3) If no suffix exists or the current $x$ position has no rectangles skip to the next $x$ position with rectangles and reinitialize $I$, and $(i\_{min}, i\_{max})$.
* In #2 and #3 save the current $I$ if it allows the widest contiguous line so far.

# Answer
Here is a slightly different algorithm. Start by sorting the list according to the $y$ value. Iterating through all different $y$ values, maintain a list of all rectangles which intersect the given $y$ value, as well as the $x$-intervals that they span. When you lose an interval, you need to split a range. When you add an interval, you need to find which intervals, if any, it is adjacent to, and then enlarge the interval and possible merge two intervals. Some kind of search tree containing all endpoints of the current intervals can be useful for locating the intervals adjacent to a new segment (if they exist). Maintaining the intervals (shortening, splitting, enlarging, joining) should be possible with a Union-Split-Find data structure.

If you use the correct data structures, this algorithm should run in time $O(n\log n)$, where $n$ is the number of intervals. (That's an informed guess.)
> 1 votes

---
Tags: algorithms, data-structures, computational-geometry, intervals
---


# Question
Title: how to draw a complement of a Turing Machine?
I am now pretty confident on how I would turn something into a Turing Machine. Now my question is how do you convert TM into a complement of a Turing Machine. From what I can remember in Finite Automata, complementing it you would just turn a start state into a ending state, also if you have an ending state you would make it into a start state..How would you do complement of a Turing Machine ?

For example here I have a simple TM of a Palindrome and I want a Palindrome'

# Answer
> 11 votes
You cannot do it in general.

It would make the complement of your language semi-decidable, like the language itself. Hence they would be both decidable by running both machines in parallel.

Of course, this concerns only the case of semi -decidable languages for which the TM does not always halt for words not in the language.

If you have a decidable language for which the TM always halt with a yes or a no, you just exchange the yes and the no.

However there are some precautions to be taken:

* compatibility of accepting and non-accepting configurations

Depending on your chosen definition of Turing Machines, accepting and halting non-accepting configurations may not be compatible, hence may not be interchangeable. If it is allowed for an accepting state to have transitions that could be used, then making it a normal state may just make the computation go on, rather than halt without accepting. Hence some rather simple precautions must be taken regarding how acceptance and rejection are identified and how to exchange them.
* non-deterministic machines

Non deterministic machines are anti-managers. When a manager says "no" it means no, and when he says "yes" it means "maybe".

Non deterministic machines do the opposite: when they say "yes" it means "yes", and when they seem to say "no" (halting in a non-accepting configuration) it means "maybe". The reason it means maybe is that it might have answered yes with a different non-deterministic choice of some transitions. Actually, non-deterministic automata should be more accurately supposed never to give a negative answer. It is convenient with deterministic automata, but means nothing with non-deterministic ones. It is also "maybe" when they do not terminate, for two reasons: (1) another transition choice might have produced acceptance, and (2) you cannot assert non acceptance as the computation may go on.

Hence it is not easy to complement a language recognized by a non-deterministic or non halting device. You cannot simply exchange "yes" and "no", since you only have "yes" and "maybe". You would only get a managerial machine answering only "no" or "maybe", not recognized by the Automata Theory Union. **Automata must accept by terminating and answering "yes" unambiguously** iff the word to be recognized is in the language. Being able to answer no in some cases is just a bonus of deterministic machines, when kind enough to halt.

So, you must first convert your machine into a deterministic one. Then you can exchange accepting and rejecting configurations (with due respect to the previous point above), assuming furthermore that the machine always halt.

To get the complement of a regular set, it is convenient to first buid a DFA that recognizes it.

A Turing machine can always be turned into a deterministic one, but it may not halt, thus leaving room for "maybe". Hence it is not always possible to complement a language recognized by a Turing Machine, as stated above. But it is possible for a (determinized) TM that always halt with a yes/no answer.

---
Tags: turing-machines, automata, closure-properties
---