# Question
Title: fast and stable x * tanh(log1pexp(x)) computation
$$f(x) = x \tanh(\log(1 + e^x))$$

The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally heavy.

Is it possible to write a more direct numerically stable implementation which is faster?

Accuracy as good as `x * std::tanh(std::log1p(std::exp(x)))` would be nice. There is no strict constraints but it should be reasonably accurate for use in neural networks.

The distribution of inputs is from $\[-\infty, \infty\]$. It should work everywhere.

# Answer
OP points to a particular implementation of the `mish` activation function for accuracy specifications, so I had to characterize this first. That implementation uses single precision (`float`), and is stable and accurate in the positive half-plane. In the negative half-plane, because it uses `logf` instead of `log1pf`, relative error quickly grows a $x\to-\infty$. Loss of accuracy starts around $-1$ and already at $-16.6355324$ the implementation falsely returns $0$, because $\exp(-16.6355324) = 2^{-24}$.

The same accuracy and behavior can be achieved by using a simple mathematical transformation that eliminates $\mathrm{tanh}$, and considering that GPUs typically offer a fused multiply-add (FMA) as well as a fast reciprocal, which one would want to utilize. Exemplary CUDA code looks as follows:

```
__device__ float my_mishf (float x)
{
    float r;
    float e = expf (x);
    r = 1.0f / fmaf (fmaf (-0.5f, e, -1.0f), e, -1.0f);
    r = fmaf (r, x, x);
    return r;
}

```

As with the reference implementation pointed to by OP, this has excellent accuracy in the positive half-plane, and in the negative half-plane error increases rapidly so at $-16.6355324$ the implementation falsely returns $0$.

If there is a desire to address these accuracy issues, we can apply the following observations. For sufficiently small $x$, $f(x) = x \exp(x)$ to within floating-point accuracy. For `float` computation this holds for $x \< -15$. For the interval $\[-15,-1\]$, we can use a rational approximation $R(x)$ to compute $f(x) := R(x)x\exp(x)$. Exemplary CUDA code looks as follows:

```
__device__ float my_mishf (float x)
{
    float r;
    if (x >= -1.0f) {
        float e = expf (x);
        r = 1.0f / fmaf (fmaf (-0.5f, e, -1.0f), e, -1.0f);
        r = fmaf (r, x, x);
    } else {
        float eh = expf (0.5f * x);
        float p =        1.03628484e-3f;  //  0x1.0fa7e6p-10
        p = fmaf (p, x, -7.28869531e-3f); // -0x1.ddac04p-8
        p = fmaf (p, x,  3.47027816e-2f); //  0x1.1c4902p-5
        p = fmaf (p, x, -3.54762226e-1f); // -0x1.6b46cap-2
        p = fmaf (p, x,  8.58785570e-1f); //  0x1.b7b2bep-1
        p = fmaf (p, x, -1.38065982e+0f); // -0x1.6172ecp+0
        p = fmaf (p, x,  5.97694337e-1f); //  0x1.3204fep-1
        float q =        1.03527203e-3f;  //  0x1.0f63eep-10
        q = fmaf (q, x, -7.35638570e-3f); // -0x1.e21bacp-8
        q = fmaf (q, x,  3.28683928e-2f); //  0x1.0d4204p-5
        q = fmaf (q, x, -3.79927397e-1f); // -0x1.850bb0p-2
        q = fmaf (q, x,  6.86127126e-1f); //  0x1.5f4c0ep-1
        q = fmaf (q, x, -1.81509292e+0f); // -0x1.d0a9eep+0
        q = fmaf (q, x,  1.00000000e+0f); //  0x1.000000p+0
        r = (1.0f / q) * p;
        if (x < -15.0f) r = 1.0f;
        r = r * x * eh * eh;
    }
    return r;
}

```

Unfortunately, this accurate solution is achieved at the cost of a significant drop in performance. If one is willing to accept reduced accuracy while still achieving a smoothly decaying left tail, the following interpolation scheme, again based on $f(x) \approx x\exp(x)$, recovers much of the performance:

```
__device__ float my_mishf (float x)
{
    float r;
    float e = expf (x);
    if (x >= -6.0625f) {
        r = 1.0f / fmaf (fmaf (-0.5f, e, -1.0f), e, -1.0f);
        r = fmaf (r, x, x);
    } else {
        r = fmaf (-0.5f, e, 1.0f);
        r = r * x * e;
    }
    return r;
}

```

As a machine-specific performance enhancement, `expf()` could be replaced by the device intrinsic `__expf()`.
> 4 votes

# Answer
With some algebraic manipulation (as pointed out in @orlp's answer), we can deduce the following:

$$f(x) = x \tanh(\log(1+e^x)) \tag{1}$$ $$ = x\frac{(1+e^x)^2 - 1}{(1+e^x)^2 + 1} = x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2}\tag{2}$$ $$ = x - \frac{2x}{(1 + e^x)^2 + 1} \tag{3}$$

Expression $(3)$ works great when $x$ is negative with very little loss of precision. Expression $(2)$ is not suitable for large values of $x$ since the terms are going to blow up both in the numerator and denominator.

The function $(1)$ asymptotically hits zero as $x \to-\infty$. Now as $x$ becomes larger in magnitude, the expression $(3)$ will suffer from catastrophic cancellation: two large terms cancelling each other to give a really small number. The expression $(2)$ is more suitable in this range.

This works fairly well until $-18$ and beyond which you lose multiple significant figures.

Let's take a closer look at the function and try to approximate $f(x)$ as $x \to-\infty$.

$$f(x) = x \frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2}$$

The $e^{2x}$ will be orders of magnitude smaller than $e^x$. $e^x$ will be orders of magnitude smaller than $1$. Using these two facts, we can approximate $f(x)$ to:

$f(x) \approx x\frac{e^x}{e^x+1}\approx xe^x$

**Result:**

$f(x) \approx \begin{cases} xe^x, & \text{if $x \le -18$} \\ x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2} & \text{if $-18 \lt x \le -0.6$} \\ x - \frac{2x}{(1 + e^x)^2 + 1}, & \text{otherwise} \end{cases} $

**Fast CUDA implementation:**

```
__device__ float mish(float x)
{
    auto e = __expf(x);
    if (x <= -18.0f)
        return x * e;

    auto n = e * e + 2 * e;
    if (x <= -0.6f)
        return x * __fdividef(n, n + 2);

    return x - 2 * __fdividef(x, n + 2);
}

```

**EDIT:**

An even more faster and accurate version:

$f(x) \approx \begin{cases} x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2} & \text{$x \le -0.6$} \\ x - \frac{2x}{(1 + e^x)^2 + 1}, & \text{otherwise} \end{cases} $

```
__device__ float mish(float x)
{
    auto e = __expf(value);
    auto n = e * e + 2 * e;
    if (value <= -0.6f)
        return value * __fdividef(n, n + 2);

    return value - 2 * __fdividef(value, n + 2);
}

```

Code: https://gist.github.com/YashasSamaga/8ad0cd3b30dbd0eb588c1f4c035db28c

Benchmarks with other implementations: https://github.com/YashasSamaga/ConvolutionBuildingBlocks/tree/master/mish

$$\begin{array}{c|c|c|c|} & \text{Time (float)} & \text{Time (float4)} & \text{L2 norm of error vector} \\ \hline \text{mish} & 1.49ms & 1.39ms & 2.4583e-05 \\ \hline \text{relu} & 1.47ms & 1.39ms & \text{N/A} \\ \hline \end{array}$$
> 6 votes

# Answer
There's no need to perform the logarithm. If you let $p = 1+\exp(x)$ then we have $f(x) = x\cdot\dfrac{p^2-1}{p^2+1}$ or alternatively $f(x) = x - \dfrac{2x}{p^2+1}$.
> 3 votes

# Answer
My impression is that someone wanted to multiply x by a function f(x) that goes smoothly from 0 to 1, and experimented until they found an expression using elementary functions that did this, with no mathematical reason behind the choice of functions.

After choosing a parameter t, let $p\_t(x) = 1/2 + (3 / 4t)x - x^3 / (4t^3)$, then $p\_t(0) = 1/2$, $p\_t(t) = 1$, $p\_t(-t) = 0$, and $p\_t'(t) = p\_t'(-t) = 0$. Let g(x) = 0 if x \< -t, 1 if x \> +1, and $p\_t(x)$ if -t ≤ x ≤ +t. This is a function that smoothly changes from 0 to 1. Choose another parameter s, and instead of f(x) calculate x * g (x - s).

t = 3.0 and s = -0.3 matches the given function quite reasonably and is calculated an awful lot faster (which seems important). It's different of course. As this function is used as a tool in some problem, I'd want to see a mathemtical reason why the original function is *better*.
> 2 votes

# Answer
The context here is computer vision and the activation function for training neural nets.

Chances are this code is going to be executed on a GPU. While performance is going to depend on the distribution of typical inputs, *generally speaking it is important to avoid branches in GPU code*. Warp divergence can significantly degrade performance of your code. For example, the CUDA Toolkit Documentation says:

> Note:High Priority: Avoid different execution paths within the same warp. Flow control instructions (if, switch, do, for, while) can significantly affect the instruction throughput by causing threads of the same warp to diverge; that is, to follow different execution paths. If this happens, the different execution paths must be executed separately; this increases the total number of instructions executed for this warp. ... For branches including just a few instructions, warp divergence generally results in marginal performance losses. For example, the compiler may use predication to avoid an actual branch. Instead, all instructions are scheduled, but a per-thread condition code or predicate controls which threads execute the instructions. Threads with a false predicate do not write results, and also do not evaluate addresses or read operands.

## Two branch-free implementations

OP's answer does have short branches so branch predication may happen with some compilers. One other thing I noticed is that it appears to be acceptable to compute the exponential once per call. That is, I understand OP's answer to say one call to the exponential is not "expensive" or "slow".

In that case, I would suggest the following simple code:

```
__device__ float mish(float x)
{
    float expx = __expf(x);
    return x / (1.0f + 2.0f / (expx * (2.0f + expx)));
}

```

It has no branches, one exponential, one multiplication, and two divisions. Divisions are often more expensive than multiplications so I also tried out this code:

```
__device__ float mish(float x)
{
    float expx = __expf(x);
    float psi = expx * (2.0f + expx);
    return x * (psi / (2.0f + psi));
}

```

This has no branches, one exponential, two multiplications, and one division.

## Relative error

I computed the log10 relative accuracy of these two implementations plus OP's answer. I computed over the interval (-100,100) with an increment of 1/1024, then computed a running maximum over 51 values (to reduce the visual clutter but still give the correct impression). Computing the first implementation with double precision suffices as a reference. The exponential is accurate to within one ULP, and there are only a handful of arithmetic operations; the rest of the bits are more than sufficient to make a table maker's dilemma very unlikely. Thus we're very likely to be able to compute correctly rounded single-precision reference values.

Green: first implementation. Red: second implemenation. Blue: OP's implementation. The blue and red overlap through most of their range (left of about -20).

Note to OP: you'll want to change the cutoff to greater than -5 if you want to maintain full precision.

## Performance

You'll have to test these two implementations to see which is faster. They should be at least as fast as OP's, and I suspect they'll be much faster because of the lack of branches. However, if they are not fast enough for you, there's more you can do.

### An important question:

What is the distribution of typical input values you expect to see? Are values going to be uniformly distributed over the entire range the function is effectively computable? Or are they going to be clustered around 0 almost all the time? If so, with what variance/spread?

### The asymptotics can be improved.

On the left, OP uses `x * expx` with a cutoff of -18. This cutoff can be increased to about -15.5625 with no loss of precision. With the cost of one extra multiplication, you could use `x * expx * (1.0f - 0.5f * expx)` and a cutoff of about -4.875. Note: the multiplication by 0.5 can be optimized to a subtraction of 1 from the exponent so I'm not counting that here.

On the right, you can introduce another asymptotic. If `x > 8.75`, simply `return x`. With a little more cost, you could do `x * (1.0f - 2.0f * __expf(-2.0f * x))` when `x > 6.0`.

### Interpolation

For the center part of the range (-4.875, 6.0), you can use a table of interpolants. If their ranges are equally spaced, you can use one division to compute a direct index into the table (without branching). Calculating such a table would take some effort, but depending on your needs may be worth it: a handful of multiplies and adds *might* be less expensive than the exponential. That said, the implementers of the exponential in the library probably have spent a lot of time and effort getting theirs correct and fast. Also, the "mish" function doesn't present any opportunities for range reduction.
> 2 votes

---
Tags: approximation, neural-networks, floating-point, numerical-algorithms, numerical-analysis
---


# Question
Title: Can Homotopy Type Theory be used to derive more efficient algorithms on more efficient data representations from less efficient ones?
I've read here that in HoTT, compilers could swap out less efficient representations of data for more efficient ones and I'm wondering whether my interpretation of that statement is correct.

Say we have two different ways of representing the natural numbers, unary (zero and successor) and binary. Here is a function that checks evenness on the former representation:

```
even : UnaryNat -> Bool
even zero = true
even (succ zero) = false
even (succ (succ n)) = even n

```

If we then have an isomorphism between the unary and binary representations, we trivially get an evenness function for the binary representation "for free", simply by converting a given binary natural number to a unary one, applying the `even` function, and converting the result back to the binary representation. Obviously, this is not very efficient, and we also don't need HoTT for this.

A better way to check whether a binary natural number is even would be to check if its least significant digit is a zero. My question is: Could we derive this more efficient algorithm for binary natural numbers from our definition of evenness for unary natural numbers using HoTT? If so, would this also be possible for other data types? I haven't studied any HoTT yet and since its appears to be a pretty complex subject I would like to find out whether it's as exciting as I think it is. Thanks!

# Answer
> 3 votes
You ask if *we* could derive a more efficent way to compute `even`? Yes, we could of course. The point however is that *compilers* could not.

Having a compiler automatically perform very fancy optimization techniques is a hard problem. In fact, if you ask for too much the problem may become undecidable, and for almost all interesting cases at least extremely hard. Even just asking whether two simple types are isomorphic quickly leads to open research questions.

What we have gained from HoTT is not a magic wand, but rather a formalism that provides a very good and structured way of *thinking* and *reasoning* about isomorphism, equivalence and equality in general. One can think easily enough about "small scale" notion of equivalence, for example when we focus just on one particular data structure, such as a dictionary, but it's a whole other matter to be able to talk about *all* notions of equivalence at the same time.

In your particular case it is easy to see what it would mean to have an equivalence between two implementations of natural numbers. But how about equivalence of large software components? Or equivalence of implementations of partial differential equation solvers? How do we even being to think about it? HoTT has an answer.

---
Tags: optimization, homotopy-type-theory
---


# Question
Title: what is the relationship between increasing the number of cores and scalability?
Whenever I increase the number of cores the speedup will increase. with this increasing can I consider the system as scalable?

I mean based on the speedup obtained for a different number of cores e.g. 10,20,30, is the system scalable with the increase of cores?

# Answer
If the problem size (input data set and/or computation) is fixed , then **NO**. Amdahl's law says that. Speed up will be bounded by serial portion of the program.

If the problem size (input data set and/or computation) increases with the increase in the number of cores, then **YES**, Gustafson's law says that.
> 2 votes

---
Tags: parallel-computing
---


title: Turing machine that can remember

text:
# Question
Title: Turing machine that can remember
Special Turing Machine is defined just like standard Turing Machine, only that each step is made according to the content of the tape starting from the left edge to the head position in tape. (The transition function in this case belongs to Q X Γ\* -\> Q X Γ X {L,R})

Which of the following is true:

A. Every language L has a Turing machine that decides L if and only if there is a special Turing machine that decides L.

B. Every language L has a Turing machine that decides L in a polynomial time if and only if there is an special Turing machine that decides L in a polynomial (input length polynomial).

C. A,B answers are correct.

D. A,B answers are incorrect.

and my question is: the correct answer is D and I can't understand why.

The answer is: Each language can be decided by a special Turing machine in linear input length time (O(n) when n is the input length). A transition function goes to the right as long as no blank space is seen, and as soon as you see a blank space switches to receiving or rejecting according to the word written on the tape.

My question is: How can I decide whether to reject or accept a word? In other computational models, such as PDA, DFA, we defined the transition function similarly, and no power was added to the model. Why does it seem that power is added to the computational model as a result of the change of the transition function when it comes to Turing machines?

Thanks.

# Answer
Given any language $L$ there is a special Turing machine $T$ that decides $L$ in polynomial time.

The Turing machine has 3 states: the initial states $q\_0$, the accepting state $q\_A$ and the rejecting state $q\_R$. Let $\Gamma$ be the tape alphabet (including the blank symbol $\varepsilon$), and let $\alpha x$ denote the contents of the tape starting from the left edge to the head position in tape, where $\alpha \in \Gamma^\*$ and $x \in \Gamma$. As usual, I am going to assume that the input is written starting from the beginning of the tape and that the head is initially positioned at the beginning of the tape. The transition function $\delta$ is defined as follows:

* $\delta(q\_0, \alpha x) = (q\_0, x, R)$ if $x \neq \varepsilon$
* $\delta(q\_0, \alpha x) = (q\_A, x, R)$ if $x = \varepsilon$ and $\alpha \in L$
* $\delta(q\_0, \alpha x) = (q\_A, x, R)$ if $x = \varepsilon$ and $\alpha \not\in L$

Since there are undecidable languages for regular Turing Machines, this immediately implies that A and B are false.

Answers D and C are unclear. They talk about "both answers" but you are given $4$ possible answers.
> 1 votes

---
Tags: turing-machines, computability
---


title: Huffman Code VS Hu–Tucker Code

text:
# Question
Title: Huffman Code VS Hu–Tucker Code
Before I'll ask my question, let me start with my understanding of the definitions, to prevent myself with further confusion, as well as giving some background.

**Huffman Code** is the binary-code induced from a binary tree, constructed by Huffman's Algorithm.
**Hu–Tucker Code** is the binary-code induced from an alphabetical search tree.
According to Wikipedia (see the paragraph on Optimal alphabetic binary trees (Hu–Tucker coding)):

> In the standard Huffman coding problem, it is assumed that any codeword can correspond to any input symbol. In the alphabetic version, the alphabetic order of inputs and outputs must be identical. Thus, for example, $A = \left\\{a,b,c\right\\}$ could not be assigned code $H\left(A,C\right) = \left\\{00,1,01\right\\}$, but instead should be assigned either $H\left(A,C\right) =\left\\{00,01,1\right\\}$ or $H\left(A,C\right) = \left\\{0,10,11\right\\}$. This is also known as the Hu–Tucker problem, after T. C. Hu and Alan Tucker, the authors of the paper presenting the first linearithmic solution to this optimal binary alphabetic problem, which has some similarities to Huffman algorithm, but is not a variation of this algorithm. These optimal alphabetic binary trees are often used as binary search trees.

My question is, what are the applications of such trees? (alphabetic binary tree)
I tried to search online, but couldn't find a satisfying answer.
I also read the introduction in Hu & Tucker's paper on the subject: Optimal Computer Search Trees and Variable-Length Alphabetical Code, but I couldn't figure out exactly the use of such tree from their example.

I can very well understand the need of a compact, optimal prefix code, induced by an optimal tree (i.e. Huffman Code); this can be used for compression, but what is the use of alphabetical binary trees?

# Answer
> 6 votes
Let me give you a real-world example, that's very similar to something I wrote once.

Let's say you're implementing a library catalogue system. A library catalogue is conceptually a collection of documents (perhaps in MARC format). A user of this system might enter a query, as in any search engine, and get a set of documents in return. The user would like to be able to sort the result set by some field (e.g. title or author), and display the result set a screenful at a time.

Sorting is a well-understood problem. However, suppose this is a big library, and a search returns 100,000 relevant documents. Clearly the user is not going to look through all of them! In fact, the user might only look at the first couple of screens of results (say, 50-100 documents) and realise that their query was too broad, and so refine it further.

Moreover, accessing the sort key for a document requires parsing the document. True, you could extract the possible sort keys into a form where you didn't require parsing MARC (or, even worse, SGML/XML), although that would duplicate data. And besides, these are strings we're talking about. They are variable length, which makes memory and disk management difficult.

So you could try a fixed-size format. You could take, say, the first K characters from every title for some predetermined K, and store it in an array on disk, indexed by document number. Then you could first sort the documents by those string prefixes (i.e. something like a bucket/radix sort), and any documents which fall in the same bucket could then be sorted by extracting the "real" sort key from the documents.

The nice thing about this is you don't need to fully sort the result set. Because the user is paging through the set, you only have to completely sort the first few screenfuls, and just retain enough bucket information to sort the others if the user decides to page through that far.

So that's an improvement, but how do you set K? A lot of titles start with the letters "The ", and that's using 32 bits of information for very little discriminatory power. In fact, you'd probably be surprised how many periodicals are called "The International Journal of X", or similar boilerplate, and some searches are likely to return a lot of documents with similar titles just like that.

One possible solution is to use an order-preserving code. Compress all titles using that code, and store first 64 bits (or some other fixed amount) of the compressed title in an on-disk array. This has quite a few practical advantages: parts of the title which have very little discriminatory power get very short code words (so you don't waste space on irrelevant detail), you can sort by it because it's order-preserving, and the keys are fixed-length (so they're easy to manage in an efficient way).

# Answer
> 2 votes
Let's say you wanted to compress a dictionary using Huffman Algorithm, yes it would be small, but all the ordering would disappear. So if you wanted to get the definition of for example the word 'Apple' then you would have de-compress the WHOLE FILE just to get the definition.

So, using the Hu-Tucker Algorithm, you can compress the dictionary in that order and only partially de-compress to get the partial information of the definition of 'Apple' that you want.

---
Tags: binary-trees, huffman-coding
---


# Question
Title: Use tree in-order traversal to determine whether a BST or Heap
Given these in-order traversal lists:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

I need to determine whether each one of those lists represent a valid BST / min or max heap, or none.
I was trying to figure how to approach this, but besides brute-forcing every possible option I couldn't figure a "smart" way to solve this.

What indicators can I use, if there are any, or the way to solve this would be literally brute forcing every option?

# Answer
> 1 votes
None of them can be a BST. An in-order traversal of a BST visits the vertices in non-decreasing order of their keys (this is easy to prove by induction).

To determine if they are heaps, notice that by the number of elements in the list you already know the topology of the tree (heaps are completely binary trees up to the one-to-last level, and all the leaves on the last level are packed on the left side). Then the exercise boils down to writing down the given keys in the same order of the traversal and checking if the heap property holds.

In the specific example the first sequence cannot be a in-order traversal of a heap since the resulting tree would have a path with keys $23, 1, 53$ (in increasing order of depth). The same argument applies to the second sequence for a path with keys $71, 32, 49$.

---
Tags: data-structures, binary-trees, heaps
---


# Question
Title: Equivalence between a TM and a changing TM
Let a changing TM be a TM which is not able to write the same symbol which is being read. Formal: $M^\*=(Q,\Sigma,\Gamma,\delta,q\_{accept},q\_{reject})$,$\delta(q,a)=(q^\*,a^\*,c),a \neq a^\*$ with $q,q^\* \in Q, a,a^\* \in \Gamma, c \in \\{R,L\\}$ . Now I need to proof that a changing TM is equivalent to a normal TM.

My guess was to create a multi-tape TM which is able to simulate the changing TM(and therefore a TM is equivalt to a changing TM, since every multi Tape TM has equivalent single tape TM), but I am unnable to finish(write it formal and unformal down).

# Answer
> 1 votes
This is another easy way to prove that a changing TM can simulate a TM. The advantage of this solution over the previous one is that it works without any additional tedious work regardless of whether the "stay" movement is allowed.

Let $T$ be a TM with tape alphabet $\Gamma$. Create a changing TM $T'$ with the same state space and a tape alphabet $\Gamma'$ with $2|\Gamma|$ symbols: for each symbol $a \in \Gamma$ add both $a$ and a new symbol $a'$ to $\Gamma'$.

For each transition $(q,a) \to (q', b, m)$ of $T$ add the following transitions to $T'$ (notice that you might have $a=b$):

* $(q, a) \to (q', b', m)$
* $(q, a') \to (q', b, m)$

In other words you are treating two symbols $a$ and $a'$ as if they were identical. Whenever you read a "regular" symbol (i.e., one from $\Gamma$) you will write a "prime" symbol. Whenever you read a "prime" symbol (i.e., one from $\Gamma' \setminus \Gamma$) you will write a "regular" symbol.

# Answer
> 1 votes
It is clear that a TM can simulate a changing TM, so you only need to show the converse. Let me allow to use the "stay" movement in the changing Turing machine. It is easy (but tedious) to remove this assumption and keeping it makes the following argument more intuitive.

You can do the following: start from a TM $T$ with set of states $Q$ and tape alphabet $\Gamma$. Then, create a changing TM $T'$ with states $Q' = Q \cup (Q \times \Gamma \times \\{L,R\\})$ and tape alphabet $\Gamma' = \Gamma \cup \\{ \gamma \\}$.

Intuitively, state $q \in Q$ of $T'$ represents state $q$ of $T$, while state $(q, a, m) \in Q \times \Gamma \times \\{L,R\\}$ of $T'$ represents the fact that we plan to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$ (notice that this a state, *not* a transition, we are just keeping track of our future plans).

Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

* $(q, a) \to ( (q', b, m), \gamma, S)$, and
* $( (q', b, m), \gamma) \to (q',b, m)$

Intuitively, this replaces the writing of a symbol $b$ on the tape with two operations: 1) we write $\gamma$ without moving the head, and 2) we overwrite $\gamma$ with $b$, move the head in the intended direction $m$, and transition to the corresponding state $q'$ of $T$.

---

This is a tedious simulaton of a TM with a changing TM if the "stay movement" is not allowed. Define $\Gamma' = \Gamma \cup \\{\gamma\_1, \gamma\_2\\}$ and $Q'= Q \cup (Q \times \Gamma \times \\{L,R\\} \times \Gamma')$. Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

* $(q, a) \to ( (q', b, m, \gamma\_1), \gamma\_1, R)$,
* $( (q', b, m, \gamma\_1), x) \to ( (q', b, m, x), \gamma\_2, L)$ $\quad \forall x \in \Gamma$,
* $( (q', b, m, x), \gamma\_1) \to ( (q', b, m, x), \gamma\_2, R)$ $\quad \forall x \in \Gamma$,
* $ ( (q', b, m, x), \gamma\_2) \to ( (q', b, m, \gamma\_1), x, L)$ $\quad \forall x \in \Gamma$,
* $( (q', b, m, \gamma\_1), \gamma\_2) \to (q', b, m)$

What we are doing is the following: 1) We write $\gamma\_1$ and move right, 2) we store the current tape symbol $x$, replace it with $\gamma\_2$, and move left, 3) we replace the tape symbol $\gamma\_1$ with $\gamma\_2$ and move right, 4) we write back the stored type symbol $x$ in place of $\gamma\_2$ and move left, 5) we finally write $b$, move according to $m$, and transition to state $q'$.

---
Tags: turing-machines, computation-models, turing-completeness, church-turing-thesis
---


title: Create a PDA for the given language

text:
# Question
Title: Create a PDA for the given language
The task is to create a PDA for this language. The **|u|** a reffers to the number of a's in that word. I have tried working on it as two separate languages that I can later combine, but I fail to even do any of the two.

I would appreciate any help.

# Answer
> 0 votes
Since you mention splitting $L$ in two different languages and combining the resulting PDAs, I assume you are fine with nondeterministic PDAs.

Let me show you a context-free grammar for $L$ instead (there are standard and completely mechanical ways to convert CFG grammars to PDAs).

Let $\Sigma = \\{a,b,c\\}$ and split $L$ into two languages $L\_1 = \\{ uv \in \Sigma^\* : 3|u|\_a = |v|\_b + |v|\_c \\}$ and $L\_2 = \\{ uv \in \Sigma^\* : |u|\_c = 2|v|\_a \\}$. We can then design a context-free grammar for $L\_1$ and $L\_2$ separately.

A CFG for $L\_1$ is the following (where the axiom is $S\_1$): $$ \begin{align\*} S\_1 &\to XS\_1A \mid aS\_1YAYAY \mid \epsilon \\ X & \to bX \mid cX \mid \epsilon \\ A & \to aA \mid \epsilon \\ Y & \to b \mid c \end{align\*} $$

A CFG for $L\_2$ is the following (where the axiom is $S\_2$): $$ \begin{align\*} S\_2 &\to WS\_2Z \mid cWcS\_2a \mid \epsilon \\ W & \to aW \mid bW \mid \epsilon \\ Z & \to bZ \mid cZ \mid \epsilon \end{align\*} $$

To get a grammar for $L$, it suffices to combine the former two Grammars and add the production $S \to S\_1 \mid S\_2$ (where $S$ is the new axiom).

---
Tags: formal-languages, pushdown-automata
---


# Question
Title: Is s-grammar powerful enough to generate all possible DCFL?
In s-grammar all productions are in form of `A → , A∈V , a∈T , ∈V*`

> "... and any pair (A, a) occurs at most once in P." *\[P. Linz, 6th ed. , p. 144\]*

s-grammar is Unambiguous and i think (not sure) we can describe all Unambiguous-CFL by s-grammar. I want to know **can s-grammar describe all possible DCFL or not ?** according to this sentence, I think we can't do it but i'm not sure about that:

> Unfortunately, not all features of a typical programming language can be expressed by an s-grammar. *\[P. Linz, 6th ed. , p. 152\]*

but **all languages which described by an s-grammar is Deterministic**.

I say this, because we can made 2-state DPDA for any simple-grammar with this definition:

```
R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

```

if there is any DCFL that we can not provide an s-grammar for it , show me that please and correct me if i'm wrong.

Thanks.

# Answer
> 2 votes
Actually the example of a language not accepted can be quite simple, due to a technicality. The language $a^\*$ is not generated by a s-grammar.

In fact, an s-grammar cannot generate $\varepsilon$. In order to remove $S$ from the stack we have to apply at least one production, and any production will produce a terminal symbol.

But even if we see this as a technicality, we cannot generate two strings, one of which is the prefix of another. If we can generate a string $\alpha$ which then is accepted because all veriables have been rewritten (the stack only contains the new $z'$), then how would we generate a longer string $\alpha\beta$? It must follow the same computation initially.

This is the case because the PDA you produce is actually a PDA with empty stack acceptance: when the stack is empty (or actually only has $z'$) we must accept. It is well known that deterministice PDA with empty stack acceptance can only generate prefix-free languages. Addingan end-of-string marker is usually the remedy.

The real-time property (reading a symbol every step) is a larger problem. Consider the language $\\{ a^i b^j c^i \mid i,j \ge 1\\} \cup \\{ a^i b^j d^j \mid i,j \ge 1\\}$. It can be accepted by a DPDA. push $a$'s, push $b$'s. Then when reading a $c$ we pop the $b$'s and compare the $a$'s and $c$'s. Otherwise when reading a $d$ we compare the $d$'s with the $b$'s using the stack. Thus you need popping of stack symbols without reading input. A real-time PDA cannot do that (and neither the s-grammar). The source I know for this refers to Autebert, Berstel, Boasson: Context-Free Languages and Pushdown Automata in the Handbook of Formal Languages.

Of course the PDA has only a single state. I do have to check: it seems that also the single state restriction reduces the languages accepted.

---
Tags: context-free, formal-grammars, nondeterminism
---


# Question
Title: Halting problem vs. automated theorem proving?
In the Theory of Computation tutorial offered by Complexity Tree (I just began the 2nd video), it talks about how the Halting problem was developed to show that mathematics could not be automated. Lately, I've heard quite a bit about automated/automatic theorem proving--some people are even positing that some day mathematicians will be replaced by machines. My question is: Do we need to find a flaw in the reasoning of the Halting problem to prove that mathematics can be automated? (Or is the Halting problem, in the age of Machine Learning, reduced to a nice historical account of the past...)

# Answer
> 3 votes
The notion of automating mathematics is a vague one, and that's accounting for the discrepancy here.

One interpretation would be: to automate mathematics would be to produce a machine $M$ which could tell whether or not a given sentence is true (or, more weakly, provable from some agreed-upon set of axioms like $\mathsf{ZFC}$). Even the weaker version is ruled out by the incomputability of the halting problem.

Another interpretation is: to automate mathematics is to produce a machine $M$ which will find proofs of all provable (again, from that agreed-upon set of axioms) sentences. Note that $M$ is *not* required to determine whether a sentence is provable in the first place, merely to find a proof *if such a proof exists at all*. This **is** possible via brute force search.

Of course that second type of automation is highly *infeasible* \- in general, it will take ridiculously long to find proofs of theorems. But that doesn't impact its in-principle-possibility. This is really the *starting point* of automated theorem proving: trivially brute-force-proof-search is possible, and trivially it's horrible in general - can we find clever proof search strategies in *some cases of interest*? (And this is where complexity theory enters the picture.)

# Answer
> 3 votes
You are conflating two possible meanings of the phrase "mathematics can be automated":

1. "any theorem can be proved true or false by an algorithm"
2. "the practical activity of proving theorems, as presently performed by humans, can instead be performed by computers in an economically-viable fashion"

Due to the halting problem, it is impossible for any algorithm to be able to prove or disprove all theorems. But this applies just as well to humans as to computers!

There does not need to be a flaw in the proof of the halting problem's undecidability for (theoretically) the job of human mathematicians to become obsolete. A machine does not have to be able to solve undecidable problems to eliminate the job function of human mathematicians—it just has to be able to prove theorems of interest *more efficiently than humans can*. This is a not a question of computability or asymptotic computational complexity but of economics.

There is no reason to think that human brains are uniquely superior in proving mathematical theorems. Moreover, due to Moravec's paradox, we should *expect* that computers might be better at proving theorems than humans. A human brain is a sack of meat whose evolutionary history includes virtually no fitness rewards for the phenotype of "can prove difficult theorems." So we would expect that we might see a computer that is superintelligent in the area of proving theorems sooner than we would expect to see a computer that is superintelligent in the area of, say, hunting megafauna.

# Answer
> -2 votes
I think this question should give you the answer.

https://cstheory.stackexchange.com/questions/2800/if-p-np-could-we-obtain-proofs-of-goldbachs-conjecture-etc

In short, if P=NP then any conjecture with a reasonable length proof can be proved by a computer.

---
Tags: halting-problem, automated-theorem-proving
---


# Question
Title: Why Right-Division of regular language with RE\E language is regualr?
I think I can't understand the meaning of language being decidable. The next case makes no sense to me:

Considering I have language L1 which is regular, and language L2 which is in RE\R (in particular, it cannot be decided).

The right-division of any regular language with some language is regular, and in particular in R.

so:

L1/L2={x ∈ Σ\* | ∃ y ∈ L2 : xy ∈ L1}

is decidable.

But I can't see why. I can't describe an algorithm that decides L1\L2, so how come this language is decidable? I know how to define the transition function, but does it means that the language is decidable? After all, I can also define a transition function to the accepting problem, it still does not make it decidable.

After all, to check if x belongs to L1 \ L2 I need to go over words and check if there is a word in L2 that completes x to a word in L1, but if there is none, I will run forever.

I think I'm missing something, so I'm very confused. Would appreciate help!

# Answer
In fact, if $L\_1$ is regular then $L\_1/L\_2$ is regular for *any* $L\_2$.

Indeed, consider a DFA for $L\_1$ with transition function $\delta$ and accepting states $F$. We modify the set of accepting states to $$ F' = \\{ q : \delta(q,w) \in F \text{ for some } w \in L\_2 \\}. $$

You might object that "$F'$ cannot be computed". So what? We never said that you can compute a DFA for $L\_1/L\_2$ given one for $L\_1$ and some reasonable representation of $L\_2$. All we claim is that $L\_1/L\_2$ is regular.

Check out this question for a similar but simpler situation.
> 3 votes

---
Tags: turing-machines, computability, regular-languages, decision-problem
---


# Question
Title: How to do supervised learning without knowing the target
I'm working on an optimization algorithm that I think could be considered machine learning, but I'm not sure. Basically I have a model that I want to optimize by adjusting its parameters. I don't have any target data to compare the output of my model to, so I don't know the loss factor. However, I'm able to generate information on whether increasing or decreasing a parameter will improve my model.

This information consists of a sum of positive and negative numbers that I'll call votes, and they are very noisy. I know I should increase the parameter if the average vote is positive and decrease it otherwise. I can generate as many votes as I like if I invest the computational resources, and I need to generate a sufficient number to over come the noise. I only know I've optimized the parameters if the average votes are zero.

I'm having a hard time optimizing my algorithm. Basically it's hard to decide how many votes I should take before shifting the parameters, and then how much I should shift them. I believe the optimal amounts depend very much on the circumstances. I'm wondering if my algorithm falls under a class of optimization algorithms that have a literature I could research. Or if anyone knows any literature that my be useful to what I'm working on.

# Answer
It's hard to know what to recommend, without more context.

One possible approach is to use hill-climbing, simulated annealing, or some other form of local search. A simple form of hill-climbing is to pick a random variable, determine whether increasing/decreasing it will improve your model, and if so, increase/decrease it; then repeat until no further improvement is possible. You can combine with random restarts, or use a more powerful method like simulated annealing.

Alternatively, you could try using something like gradient descent. Suppose you learn not only whether increasing the parameter will improve the model, but how much it improves it. If you have this information, you can estimate the gradient at a point, then move in the direction of the gradient, and repeat. Based on experience with stochastic gradient descent, rather than repeating this many times at a single point and averaging, it's likely to be more effective to do this only once at each point and instead repeat for more iterations of gradient descent (perhaps with a smaller step size). Basically, because your information is noisy, each step is mostly random and is only loosely correlated with the correct direction, so this does a random walk that is slightly more likely to go in a good direction than a bad direction; after sufficiently many iterations, this should converge to a good solution. The analysis of stochastic gradient descent shows that in many settings this performs better than trying to compute many votes at a single point, average them to get a very good estimate of the direction to go, and repeat for many fewer iterations. So, the theory says: take only one vote. There's no theory to tell you how much to change the parameters (the step size). Usual practice in the machine learning literature is to treat this as a hyperparameter, try multiple different values (e.g., 0.0001, 0.001, 0.01, 0.1), and see which works best. Sometimes it may be helpful to start with a large step size and then reduce it after some number of iterations. There are also heuristic optimizers that try to adaptively adjust the step size, such as the Adam optimizer, but it's unclear whether they help or not.

Another approach is to use Bayesian optimization, which uses machine learning to construct a surrogate model that can predicts how well any set of parameters will perform, and then uses optimization methods on the surrogate model. See, e.g., Google Vizier for one representative of this approach.

I can't predict which approach is likely to be most suitable to your setting. That may depend on the number of dimensions (how many parameters you have), the dependence of the metric you care about as a function of the parameters (how nonlinear it is), and what kind of information you receive about any set of parameters.

Related: What solution to apply for finding the optimal parameters?, What is an appropriate global optimization technique for a noisy and expensive function?, Mathematical optimization on a noisy function.
> 0 votes

---
Tags: optimization, machine-learning
---


title: Connect a graph

text:
# Question
Title: Connect a graph
Given an undirected graph, We need to convert it into a connected graph by adding/removing the edges keeping the summation of absolute difference of change in degree of nodes minimum. There can be multiple edges. Formally, we need to minimize: $$\sum\_{i = 1}^{i = n} |d\_i - e\_i|$$ Where, $e\_i$ is the new degree of node i.

My approach was separating all the connected components first and then for every connected component, I noted down the edges which were not present in the DFS tree. These edges do not contribute to the connectivity of the graph and hence I can redirect them to other components to connect them. Is this claim correct? Also since the number of these type of edges can be arbitrary, what would be the constraints under which I use them to connect to other components.

The algorithm should work in linear time.

# Answer
> 2 votes
I'll just discuss the core idea of the algorithm and skip the details. It is easier to think that the connected components of your graphs are not singletons (If there are singletons, ignore their connected components. I will point out how to handle them in brackets).

You can modify your graph in a way that doesn't change the degree of any vertex and such that resulting graph will be either:

* Connected, or
* A forest

If neither of the above two condition is met then you can iteratively perform the following "merge" operation:

* Pick an edge $(u,v)$ from a connected component $C$ such that $C-e$ is still connected. This edge exists otherwise the graph would be a forest.
* Pick an edge $(x,y)$ from a connected component $C'$ other than $C$. $C'$ exists otherwise the graph would be connected.
* Replace $(u,v)$ and $(x,y)$ with $(u,x)$ and $(v,y)$. You have now a graph with the same degrees and one less connected component (effectively, $C'$ is now merged into $C$).

If the resulting graph is connected you are done (If the graph had singletons then reroute some of the edges not needed for connectivity to them, each of these rerouted edges contributes $1$ to the measure to minimize. If there are not enough edges then you'll need to add new ones, which contribute $2$ each to the measure).

If the resulting graph is a forest $F$ of $k\>1$ trees then you'll need to add $k-1$ edges to connect the trees of $F$ (if there were singletons then consider them as trees in $F$).

You can implement this algorithm in linear time by keeping, for each connected component $C$:

* A list $T\_C$ of the edges in a spanning tree of $C$,
* A a list $L\_C$ of edges that are in $C$ but not in $T\_C$.

Constructing these lists takes time $O(n+m)$ where $n$ and $m$ are the number of vertices and edges of the input graph, respectively. Then the edges $(u,v)$ and $(x,y)$ can be found in constant time. Pick $(u,v)$ from $L\_C$ and $(x,y)$ from $T\_{C'}$. In this way $T\_C$ and $L\_C$ can be updated in constant time to reflect the result of the "merge" operation. The number of "merge" operations is at most $O(n)$.

---
Tags: graphs, graph-traversal
---


# Question
Title: Minimization of amount in the change coins problem using the dynamic programing approach
I'm learning the dynamic programming approach to solve the coins change problem, I don't understand the substitution part

Given: `amount=9, coins = [6,5,1]`,

the instructor simplified it with this function:

`minCoins = min {(9-6)+1 , (9-5)+1, (9-1) +1} = min{4, 5, 9} = 4`

I don't understand the logic of this `min` method: why we say that to change amount of 9 coins, we can simply, take the minimum of: 9 - {all coins} +1 ?

here's a Gif that visualizes the instructor's approach: https://i.stack.imgur.com/Zx2cG.gif

(\*taken from the Algorithmic Toolbox course/ instructor: Prof. Pavel A. Pevzner)

# Answer
Your formula is wrong (I would like to see where exactly this formula appears in the course, it is not in the gif you linked).

The correct formula is the following: Let $n$ be your amount. Let minCoins be an array of $n+1$ elements indexed from $0$ to $n$, where minCoins$\[i\]$ is the minimum amount of coins needed to give change for the amount $i$. Let $c\_1, \dots, c\_k$ be the denominations of coins you have available.

Then minCoins$\[0\]=0$ and, for $i\>0$: $ \text{minCoins}\[i\] = \min\_{\substack{j=1,\dots,k\\c\_j \le i}} \\{1 + \text{minCoins}\[i-c\_j\] \\}. $

In your specific example:

$$ \begin{align\*} \text{minCoins}\[9\] &= \min \\{\text{minCoins}\[9-6\]+1 , \text{minCoins}\[9-5\]+1, \text{minCoins}\[9-1\] +1\\} \\ &= \min \\{\text{minCoins}\[3\]+1 , \text{minCoins}\[4\]+1, \text{minCoins}\[8\] +1\\} \\ &= \min\\{ 3+1, 4+1, 3+1\\} \\ &= \min\\{ 4, 5, 4\\} = 4. \end{align\*} $$
> 2 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Arbitrary depth nested for-loops without recursion
Suppose I have an array of `n` values I want to apply nested for-loops over to an arbitrary depth `m`.

```
const array = [1, 2, 3];

// 2-depth for-loop
for (const i of array) {
  for (const j of array) {
    // do the thing
  }
}

// 3-depth for-loop
for (const i of array) {
  for (const j of array) {
    for (const k of array) {
      // do the thing
    }
  }
}

```

The obvious solution is to use recursion. In JavaScript/TypeScript, a generator lends itself well here. For an example problem, let's calculate the probability distribution of the sum of rolling `m` 6-sided dice.

```
type Reducer<T, TResult> = (current: T, accumulator?: TResult) => TResult;

function* nestForLoopRecursive<T, TResult>(
  array: T[],
  depth: number,
  reduce: Reducer<T, TResult>
): Generator<TResult> {
  for (const value of array) {
    if (depth === 1) {
      yield reduce(value);
    } else {
      for (const next of nestForLoopRecursive(array, depth - 1, reduce)) {
        yield reduce(value, next);
      }
    }
  }
}

function reduceSum(current: number, prev = 0): number {
  return current + prev;
}

const pips = [1, 2, 3, 4, 5, 6];

interface RollDistribution {
  [key: number]: number;
}

function rollMDice(m: number): RollDistribution {
  const results: RollDistribution = {};

  for (const result of nestForLoopRecursive(pips, m, reduceSum)) {
    results[result] = results[result] !== undefined ? results[result] + 1 : 1;
  }

  return results;
}

for (let m = 1; m <= 3; m++) {
  console.log(`Rolling ${m} ${m === 1 ? 'die' : 'dice'}`);
  console.log(rollMDice(m));
  console.log();
}

```

### Output

```
Rolling 1 die
{ '1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 1 }

Rolling 2 dice
{
  '2': 1,
  '3': 2,
  '4': 3,
  '5': 4,
  '6': 5,
  '7': 6,
  '8': 5,
  '9': 4,
  '10': 3,
  '11': 2,
  '12': 1
}

Rolling 3 dice
{
  '3': 1,
  '4': 3,
  '5': 6,
  '6': 10,
  '7': 15,
  '8': 21,
  '9': 25,
  '10': 27,
  '11': 27,
  '12': 25,
  '13': 21,
  '14': 15,
  '15': 10,
  '16': 6,
  '17': 3,
  '18': 1
}

```

My understanding is that any recursive function can be rewritten iteratively, though it usually requires some augmentation. (For example, an in-order traversal of a binary tree can be done iteratively if you augment each node with two bits and a parent pointer.)

**How can I rewrite `nestForLoopRecursive()` without using a stack or any other recursive data structure?** In particular, is it possible to do this in at most `O(n lg(m))` space?

Here's a CodeSandbox with everything needed written in TypeScript. The code yet to be written starts at line 16. Feel free to answer using whatever language you choose, though, including pseudocode.

# Answer
It is impossible to do this in $O(n \log m)$ space, by a counting argument. Fix $n = 2$ and consider the number of iterations for which the program must execute. There are $m$ nested loops, each with $2$ indices, so the inner statement executes exactly $2^m$ times and then the iteration terminates. But the configuration space of the program only has $2^{O(\log m)} = \operatorname{poly}(m)$ possible states. So as $m \rightarrow \infty$, by the pigeonhole principle some state must be visited twice during the iteration, which is impossible because it would result in an infinite loop.

On the other hand, you can easily do this in $O(\log(n^m)) = O(m \log n)$ space. (Note that this is reversed from what you wrote!) All you have to do is count in base $n$. That is, keep an array of integers of size $\log n$ and treat them as the base $n$ digits of a single number that you are incrementing. Or you can use an arbitrary precision integer data type and use division and modulo operators to extract the base $n$ digits. Either way, this is trivially equivalent to using a stack, but maybe it feels less "recursive" to you.
> 1 votes

---
Tags: recursion, loops, iteration
---


# Question
Title: What complexity class is the TSP problem?
Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?

# Answer
It has been proven that TSP is $FP^{NP}$-complete but it remains an open question whether TSP is a function problem in $FNP$ (it *probably* is not). The reason is that, in the case of TSP, the optimal solution is not an adequate certificate, as we do not know how to verify in polynomial time that it is optimal.

You can see a proof that TSP is $FP^{NP}$-complete here, starting on page 418.

Note: I don't know if it's allowed to put the link to that PDF although it's from a university. You can buy the full book searching for *Computational Complexity by Christos H. Papadimitriou*.
> 2 votes

---
Tags: complexity-theory, np-complete, np-hard, complexity-classes, traveling-salesman
---


# Question
Title: Computation of iterated logarithm function
I recently came across the iterated algorithm function denoted as $\lg^\* n$.

But I am having a hard time understanding this statement:

$\lg^\* n = \min \\{i \ge 0: \lg^{(i)} n ≤ 1\\}$

I could not understand what $\min$ set is used to signify. Also, could someone please provide an example of how this works. I also came across examples like:

$\lg^\* 4= 2$

But could not understand the computation, specifically how did they take up the values of i?

Thank you.

# Answer
> 3 votes
$\lg^\* n$ is just the *minimum* number of times you need to apply the $\lg$ function to $n$ in order to obtain a number that is smaller than or equal to $1$.

For example, assuming that you are working with base-2 logarithms and that $n=65536$ you have the following:

* $\lg^{(0)} 65536 = 65536$,
* $\lg^{(1)} 65536 = \lg 65536 = 16$,
* $\lg^{(2)} 65536 = \lg 16 = 4$,
* $\lg^{(3)} 65536 = \lg 4 = 2$,
* $\lg^{(4)} 65536 = \lg 2 = 1$.

As you can see $4$ is the smallest integer value of $i \ge 0$ for which $\lg^{(i)} 65536 \le 1$. Therefore $\lg^\* 65536 = 4$.

---
Tags: algorithms, iteration
---


title: Review my proof that Co-NP != P

text:
# Question
Title: Review my proof that Co-NP != P
The idea is to pick a problem category in Co-NP, where the correct answer is hard to verify because of circuit complexity, express it as 1-in-k SAT formula, and show there also exists a short certificate, whose length in bits is exactly twice the number of clauses. It might be true or false that all of Co-NP problems have such a short certificate in this form (Co-NP ?= NP), but I show that regardless of that, the short certificate for this problem can be made arbitrarily hard to find, because of the interleaved relationship with NP. Basically, I want to highlight a particular circular dependency between the oracles of NP and Co-NP. The argument to stomp against Co-NP = P is that no TM can hope to attack the problem of searching for the short certificate in subexponential time, because the way I define the problem makes it contain an arbitrary amount of "actual random". Basically, it is one specific recipe to build a "monster" Co-NP problem from a simple certificate.

Now I have many questions for anyone with more formal training than me:

* Has this category of problem been expressed with a different name?
* Is this an obvious dead end or unexplored?
* How can I express the same ideas but more formally against TM capabilities?

# Answer
> 1 votes
WTLU is in P.

**Algorithm:**

* Make the 1-in-k SAT formula monotone by adding one clause for each pair of literals (x + ~x) = 1 and replacing ~x with a new variable.
* Pick a large prime p, at least larger than the number of clauses.
* Turn the 1-in-k SAT formula into a system of linear equations modulo p. Each original clause in the form (x,y,z...)=1 becomes an equation (x,y,z...)=1 mod p.
* Perform Gaussian Elimination.
* If the formula was a WTLU instance, then a contradiction is found before row echelon form is reached, in the form of a contradictory equation 0 = k mod p (with k != 0).

**Why it works:**

If there are two sets of clauses that cover the same set of literals, such that (C1+C2+C3...) = X and (C1'+C2'+C3'...) = Y and X != Y, then it is also the case modulo p. Thus, the system of equations modulo p is not satisfiable either.

# Answer
> 2 votes
Here's a counterargument. A similar proof structure, could be easily used to prove that XOR-SAT is hard.

1. Take an unsatisfiable XOR-SAT formula with a large space. You can't solve it with a resolution-like algorithm.
2. Now there exists a short unsatisfiability certificate, because XOR-SAT is in P.
3. If you don't know about elimination then you combine random clauses together until two clauses have the same variables, one row equals zero and the other row equals one. Lining up is a special case of addition where the clauses have no literals in common.
4. Add random clauses and variables to the XOR-SAT formula to make it harder to randomly do things.

But in reality you can do Gaussian Elimination in a polynomial amount of time and space until two rows cancel each other to produce 0=1.

To expand your argument and make it interesting you would need to at least show that there is a fundamental difference with XOR-SAT, for a start that there is no process similar to elimination where you can take out the variables one by one during the process of isolating the 2 conflictual sets of clauses while ignoring the extra information.

---
Tags: p-vs-np
---


# Question
Title: How to prove transitivity of < (Software Foundations exercise)?
I'm working through the "Properties of Relations" chapter of Software Foundations, but have got stuck on one of the exercises, `lt_trans''`:

```
Theorem lt_trans'' :
  transitive lt.
Proof.
  unfold lt. unfold transitive.
  intros n m o Hnm Hmo.
  induction o as [| o'].
  (* FILL IN HERE *) Admitted.

```

The base case for the induction is straightforward, but I'm stumped as to how to progress on the successor case. Proof state is:

```
  n, m, o' : nat
  Hnm : S n <= m
  Hmo : S m <= S o'
  IHo' : S m <= o' -> S n <= o'
  ============================
  S n <= S o'

```

To apply the induction hypothesis, I need `S m <= o'`, but I only know that `S m <= S o'`, and so it feels there is no way to make progress. Hoping someone can point me in the right direction as to how to solve this exercise.

# Answer
Not all relations are transitive, so you're going to need to use the definition of `lt` and `le`, or some lemma that you've already proved about them.

Intuitively speaking, there are two cases: either $m = o'$ or $m \lt o'$. In the first case, `Hnm` says that $S(n) \le o'$, from which the conclusion is one application of `le_S` away. In the second case, you can apply `IHo'`.

This form of reasoning assumes some very well-known facts about arithmetic. (It's usually hard to formally prove something if you don't already have some intuition about the topic.) But you haven't proved them yet, so you can't directly use them. Instead, you have to make these cases appear via the construction of the data or the proof. It's very common to reason about the structure of a proof hypothesis: such-and-such hypothesis is of this form, and therefore it can only have been constructed in a certain way.

An important tactic for reasoning about the structure of a hypotheses in a non-recursive way is `inversion`. Roughly speaking, `inversion` does case analysis on a hypothesis and works out how these cases can be possible, unlike `destruct` which does case analysis but loses information on how the hypothesis could be possible. We want to reason about how $m \le o'$ can be possible, and there's a hypothesis that's very cloes to this: `Hmo`. So apply the tactic `inversion Hmo`.

I'll let you work out the details of the proof. If you don't care about the details, Coq will fill them in for you, but as a learning exercise you should complete these `auto` steps by hand.

```
Theorem lt_trans'' :
  forall n m o, n < m -> m < o -> n < o.
Proof.
  unfold lt.
  intros n m o Hnm Hmo.
  induction o; inversion Hmo; subst; auto.
Qed.

```
> 2 votes

---
Tags: coq
---


# Question
Title: Binomial trees in binomial heap with 27 elements
How many binomial trees are in a binomial heap with 27 elements and how would you find this number?

# Answer
> 2 votes
A binomial heap stores a collection of binomial trees whose sizes are powers of two and such that there is at most one tree for each size.

How can you write 27 as a sum of distinct powers of 2? How many powers do you need?

---
Tags: data-structures
---


# Question
Title: Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope
I want to solve a linear programming problem in the $2n$ variables $x\_1, \ldots, x\_n$ and $y\_1, \ldots, y\_n$ where the cost is of the form $x\_1/y\_1 + \cdots + x\_n/y\_n$. Specifically, I want to solve \begin{align\*} & {\rm minimize}~ \sum\_{i=1}^n x\_i/y\_i \\ &\mbox{ subject to } Ax + B y \leq c \\ & x\>0, y\>0, \end{align\*} where $A$ and $B$ are given matrices and $c$ is a given vector.

This feels like it should be NP-hard due to the non-convexity of the objective, but I have no idea how to show this, or even whether I'm missing some kind of clever trick that makes it convex. If the matrices $A$ and $B$ were positive, you could plug in $x\_i=e^{u\_i}, y\_i = e^{v\_i}$ and the problem would become a convex problem that you could solve via geometric programming, but positivity is not an assumption. I'm not even sure what would be a natural combinatorial problem to try to write in this format, so any suggestions would be very welcome.

# Answer
> 1 votes
Your objective function is indeed not convex, but you can make it convex with the appropriate transformation, which means it is solvable in polynomial time. But applying this reformulation is complex: you should try a non-convex solver first and stop there if it works in practice.

## The easy way: Non-convex quadratic model

As pointed in the comments, it is a quadratic program, so you can solve it with a non-convex quadratic solver. Although not a polynomial-time algorithm theoretically, these solvers are really efficient in practice.

\begin{align\*} {\rm minimize}&~ \sum\_{i=1}^n r\_i \\ \mbox{ subject to } & \\ & Ax + B y \leq c \\ & r\_iy\_i \geq x\_i \\ & x\>0, y\>0 \end{align\*}

## The hard way: Convex fractional programming reformulation

Stated as follows, it is clear that it is a fractional programming problem: \begin{align\*} {\rm minimize}&~ \frac{\sum\_{i=1}^n x\_i \prod\_{j\neq i} y\_j}{\prod\_{j=1}^n y\_j} \\ \mbox{ subject to }& \\ & Ax + B y \leq c \\ & r\_i \geq x\_iy\_i \\ & x\>0, y\>0 \end{align\*}

Both the numerator and denominator are convex, so you can follow the transformation given in the above link to make it convex. This makes it solvable in polynomial time.

$$ \begin{align\*} z\_i &= \frac{x\_i}{\prod\_{j=1}^n y\_j} \\ w\_i &= \frac{y\_i}{\prod\_{j=1}^n y\_j} \\ t &= \frac{1}{\prod\_{j=1}^n y\_j} \\ \end{align\*} $$

And solve (yes, the convexity is far from obvious):

$$ \begin{align\*} {\rm minimize}& ~ \frac{1}{t^{n-1}} \sum\_{i=1}^n z\_i \prod\_{j\neq i} w\_j \\ \mbox{ subject to } & \\ & \frac{\prod\_{j\neq i} w\_j}{t^{n-1}} \leq 1 \\ & Ax + By \leq ct \\ & z\>0, w\>0, t \geq 0 \end{align\*} $$

---
Tags: complexity-theory, optimization, np-hard
---


# Question
Title: What is the time complexity of subset testing?
Consider the following problem:

> Let $A = \\{a\_1,...,a\_n\\}$ and $B = \\{b\_1,...,b\_m\\}$ be two finite sets over $\mathbb{N}$. The sequences $a\_1,...,a\_n$ and $b\_1,...,b\_m$ do not have to be sorted. Given as inputs the strings $a\_1,...,a\_n$ and $b\_1,...,b\_m$, determine if $A \subseteq B$.

What is the time complexity of this problem?

# Answer
> 2 votes
Since you talk about sets I assume that there are no duplicates.

You can assume $n \le m$ otherwise you can answer "no" in time $O(1)$. You can further assume $\max\_{a \in A} a \le \max\_{b \in B} b$, otherwise the answer is again "no", and can be found in time $O(\min\\{m, U\\})$, where $U = \max\_{a \in A} a$.

Your problem can be solved in $O(\min\\{m \log n, U\\})$ worst-case time. To do so use the best of the following two strategies:

* Sort $A$. Keep a counter $x$ of how many elements from $B$ have been found in $A$. Initially $x=0$. For each element of $b \in B$ (in arbitrary order), determine whether $b \in A$ using a binary search. If $b \in A$ increment $x$. After all elements of $B$ have been examined, return true if and only if $x=n$.
* Keep an array $X\[0, \dots, U\]$ of $U+1$ boolean elements. Initially all the elements of $X$ are false. For each element $b \in B$, check if $b \le U$ and if that is the case set $X\[b\]$ to true. Iterate over the elements $a \in A$ and check whether $X\[a\]$ is true for all of them. If this is the case return true, otherwise return false.

Notice that $\Omega(m \log n)$ is a lower bound on the worst-case time complexity needed to solve your problem (as a function of $m$ and $n$) in the algebraic computation tree model. See Corollary 3 on page 147 (155 of the pdf file) here.

You can also solve your problem in $O(m)$ expected time by using a hashset $H$:

* Insert all the elements of $B$ into $H$. This takes $O(1)$ expected time per insert operation, i.e., $O(m)$ time in total.
* For each element $a \in A$, check whether $a \in H$. This takes $O(1)$ expected time per check.

---
Tags: complexity-theory, time-complexity, sets
---


# Question
Title: What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?
I would like to know what is the VC dimension of the following hypothesis class.

$$H=\left\\{f\_{\theta\_{1}, \theta\_{2}}: R^{2} \rightarrow\\{0,1\\} \mid 0\<\theta\_{1}\<\theta\_{2}\right\\}$$

where $f\_{\theta\_{1}, \theta\_{2}}(x, y)=1$ if $\theta\_{1} x \leqslant y \leqslant \theta\_{2} x,$ else $f\_{\theta\_{1}, \theta\_{2}}(x, y)=0$.

I am not really sure how to prove it. What do you think?

# Answer
> 2 votes
The VC-dimension of your hypothesis class $\mathcal H$ is 2. To see this, we begin by showing that $\mathcal H$ shatters any 2-element set $\\{(a\_1 a\_2), (b\_1, b\_2)\\}$ of real numbers where all components of the pairs are positive:

1. $\emptyset$ is accounted for by $f\_{c, c + \varepsilon}$ for any real $c$ such that $ca\_1 \neq a\_a$ and $cb\_1 \neq b\_2$ and some sufficiently small $\varepsilon \> 0$.
2. $\\{a\\}$ (and similarly $\\{b\\}$) is accounted for by $f\_{c, c + \varepsilon}$ where $c = a\_2/a\_1$ and $\varepsilon \> 0$ is sufficiently small.
3. $\\{a, b\\}$ is accounted for by $f\_{\varepsilon, c}$ for some sufficiently small $\varepsilon \> 0$ and some sufficiently large $c$ (specifically, one can set $\varepsilon = \min \\{a\_2 / a\_1, b\_2 / b\_1\\} / 2$ and $c = 1 + \max \\{a\_2 / a\_1, b\_2 / b\_1\\}$)

This yields $\operatorname{VC}(\mathcal H) \geq 2$.

Now consider some arbitrary set $X = \\{(a\_1, a\_2), (b\_1, b\_2), (c\_1, c\_2)\\}$ of pairwise distinct points in $\mathbb R^2$. If the points in $X \cup \\{(0, 0)\\}$ are not in general position then $\mathcal H$ cannot shatter $X$ as it means that there are at least two points $s, t \in X$ which fall onto a line with the origin and as every classifier in $\mathcal H$ has linear decision boundaries it must always label $s$ and $t$ the same way, preventing it from shattering any set containing these points.

So let us assume that $X \cup \\{(0, 0)\\}$ is a set of points in general position and shattered by $\mathcal H$. As all functions $f\_{\theta, \varphi} \in \mathcal H$ represent areas between two lines with positive slopes (since we require $0 \< \theta \< \varphi$) we can infer that all the lines connecting points in $X$ with the origin also must have positive slopes (note that $X$ is not in general position when the origin is an element of $X$). Hence we can order the points in $X$ ascendingly by these slopes, i.e. we may write $$ a\_2 / a\_1 \< b\_2/ b\_1 \< c\_2 / c\_1$$ and since this requires all $x$-coordinates of the points in $X$ to be nonzero, we can simplify the expression for the preimage of $1$ of any $f\_{\theta, \varphi} \in \mathcal H$ restricted to $X$ to $$ f\_{\theta, \varphi}|\_X(x, y)^{-1} = \\{(x, y) \in X \mid \theta \leq y / x \leq \varphi\\} $$ by dividing by $x$. Now consider the subset $X' = \\{a, c\\}$ of $X$ and suppose $f\_{\theta, \varphi} \in \mathcal H$ accounts for $X'$, i.e. $f\_{\theta, \varphi}|\_X^{-1}(1) = X'$. But then we must have $$\theta \leq a\_2 / a\_1 \< b\_2 / b\_ 1 \< c\_2 / c\_1 \leq \varphi$$ which yields $f\_{\theta, \varphi}|\_X(b) = 1$ and thus $f\_{\theta, \varphi}$ does not account for $X'$ which is a contradiction. Therefore $\mathcal H$ does not shatter $X$ and and thus no set of size $\geq 3$.

It follows that $2 \leq \operatorname{VC}(\mathcal H) \< 3$ and thereby $$\operatorname{VC}(\mathcal H) = 2.$$

---
Tags: learning-theory, vc-dimension
---


title: Question about turing machines

text:
# Question
Title: Question about turing machines
I've been reading a book about turing machines and it has a challenge about a building a Turing Machine that has as many 0s as many 1s but that can appear in any order.

I don't understand how do you set the reading to the beginning and then make a transition to the beginning.

But it deals with only 0s that shows up before 1s, how would i go about in the same instance if i find something like 100, or 100001?

# Answer
> 1 votes
The Turing machine uses the tape alphabet $\Gamma = \\{0,1,x,\epsilon\\}$. Writing down all the transitions explicitly is tedious, so I'll just summarize the main steps:

* Move right until you find a 1 or $\epsilon$.
* If a 1 is found proceed as follows:

+ Replace the $1$ with $x$.
    + Move the head back to the initial position (move left until you find $\epsilon$, then move right once).
    + Move right until you find a $0$ or $\epsilon$. If no $0$ is found reject.
    + Replace the 0 with $x$.
    + Move right until you find a $0$ or $\epsilon$. If no $0$ is found reject.
    + Replace the 0 with $x$.
    + Move the head back to the initial position.
    + Repeat everything from the very first step.
* Otherwise, if no 1 is found:

+ Move left until you find a $0$ or $\epsilon$. If no 0 is found, accept.
    + Reject.

---
Tags: turing-machines
---


# Question
Title: How to compute the max. speedup achievable of parallel program?
I was given the following problem to solve:

Consider a system that has 128 compute units of the same type. Suppose that a program runs for 1025 time units on a single compute unit. The total amount of serial work for this program is 1 time unit. Compute the maximum speedup achievable for the given system.

I am confused about whether to use Ahmadhl's, Gustafson's law, or neither. Also, what is confusing are the given numbers - the program runs serially for 1025 time units, but only 1 time unit is the total amount of serial work - so that means that 1024 time units are parallelizable?

# Answer
> 0 votes
You understand the problem correctly; 1024 units are parallelizable. To calculate speedup, you can divide the serial runtime by the parallel runtime (no laws required). Or plug into the version of Amdahl's law that actually uses the number of processors (https://stackoverflow.com/a/37335032/5039395).

---
Tags: parallel-computing, performance
---


# Question
Title: Finding most efficient sorting algorithm
Arr is an array that contains $ n$ numbers.
Suggest the most efficient algorithm for each case and analyze the runtime.
Explain why the algorithm you chose is the best one.

1. Arr contains exactly $\frac{n}{5}$ distinct values.
2. Arr contains integers in the range $\[0, … , ^7 − 1\]$.
3. There are exactly ( − √) integers in Arr, which are between 1 to 100. The remaining √ elements are not integers.

I was trying to look at some of the sorting algorithms and try to figure one by one which one is the best, but I believe there's a better way to do it. What would be the right approach?

# Answer
For 1) Use any $O(n \log n)$-time sorting algorithm, like Mergesort. Without additional assumptions on the elements you cannot do better.

For 2) Use Radix sort with any base $b = n^\epsilon$ for any constant $\epsilon \in (0, 1\]$ of your choice. For example pick $\epsilon =1$ so that $b=n$. The time needed for each iteration of Radix sort will be $O(n+b) = O(n)$. The number of iterations will be $O(\log\_b n^7) = O(7 \log\_n n) = O(1)$. The overall time is then $O(n)$.

For 3) As Jean-Claude Arbaut points out: find the integer elements and sort them once for all with counting sort. This requires time $O(n)$. Sort the remaining $\sqrt{n}$ element with any $O(n^2)$-time sorting algorithm. For example Mergesort or insertion sort. This takes time $O\left(\left( \sqrt{n} \right)^2\right) = O(n)$. Finally, merge the two sorted arrays in time $O(n)$ (similarly to the Merge step of Mergesort). The overall time required is $O(n)$.
> 0 votes

---
Tags: sorting, efficiency
---


# Question
Title: Can we create faster sort algorithm than O(N log N)
I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$

Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort this given array. The clear solution is to sort the array using the classic merge sort algorithm, which works in $O(N \log N)$ time and space complexity. I was thinking that this trick can improve the complexity.

Let $N\_{1} = 10^5$, clearly $N = 10\cdot N\_{1}$. Let's split the array $A$ in $10$ smaller array where each array consist of $N\_{1}$ elements and sort those $10$ arrays with standard merge sort ( time complexity: $O(N\_{1}\cdot\log N\_{1})$), so we have 10 arrays where each array is sorted, we can merge those 10 array into one array in time complexity $O(N\cdot\log(10))$ using priority queue.

So the total complexity will be $O(10 \cdot N\_{1}\cdot\log N\_{1} +N\cdot\log(10))$. Now let's say we split the array in $\sqrt{N}$ arrays, so the complexity will look like: $$O(\sqrt{N} \cdot \sqrt{N} \cdot \log \sqrt N + N \cdot \sqrt N)\\ = O(N \cdot \log (\sqrt N) + N \log (\sqrt N))$$

Is everything in my algorithm correct, and is this trick efficent in memory usage?

# Answer
You got a result of $O(N\cdot \log(\sqrt N)+N\log(\sqrt N))$.

But $\log \sqrt N = (\log N)/2$, so $N⋅log(\sqrt N)+N·\log(\sqrt N) = N·\log N$. So not only is it the same complexity class, where constant factors don't matter, it is even the same function, therefore the same constant factor.

But the underlying reason for any comparison based sorting algorithm to take $O(\log N)$ comparisons is that there are N! possible permutations of the array elements, each comparison can rule out at most half the possible cases, so you absolutely need at least $\log\_2 N!$ comparisons in the worst case, which is $O(N\cdot \log N)$. That $\log\_2 N!$ is not a big-O, it is an absolute number. You cannot achieve for example $0.999 \log\_2 N!$ comparisons in the worst case.

So you would have to come up with an algorithm that isn't based on comparison. For example, if an image contains pixels using 24 bits each, then you can sort the $N$ pixels of an image in $O(N)$ (see "The Player of Games" for reasons why you would want to sort all the pixels in a large library).
> 13 votes

# Answer
Your example is an unfortunate one. Since you are sorting integers, you can pose a specific requirement to sort, such as the value, if that is the only thing to sort on you can use the radix sort, which would put the complexity at O(#ofdigits*n) or O(k*n) which is 99% of cases is much better than lg(n), the only reason is sorting alrogithm isn't used more often is because it is too restrictive with the type of data it can sort.

For example: If you had 10^6 integers in the worst cause scenario, because integers can only have 8 digits, you would have 8\*10^6 calculations for radix sort, but for MergeSort you would have 20\*10^6 which is significantly slower.
> 0 votes

---
Tags: optimization, time-complexity, sorting
---


title: Paint graph ordered vertices

text:
# Question
Title: Paint graph ordered vertices
I have the following question: Given graph $G=(V,E)$ with given order on its vertices, I mean $v\_1\<v\_2\<...\<v\_n$ I need to find minimal colors ordered paining of the graph vertices s.t neighbor vertices don't have the same color, I mean: $(v\_1,v\_2,...,v\_j)$ \- painted in fist color and non of them are neighbors. $(v\_{j+1},...,v\_l)$ \- painted in second color and non of them are neighbors. and so on.

The complexity needs to be $O(V+E)$. Anyone have an idea?

# Answer
> 1 votes
If understand the question correctly you want to find a $k$-coloring of the given graph, given an ordered list of the vertex such that vertex with the same colors are consecutive in this list.

If that is the case then this problem can be solved greedy.

We should only find maximal independent sets which are contiguous segments in your list starting from the beginning. Start with an empty set. Go for every vertex in the ordered list, if the vertex is not connected to any other node in the set, include it. Otherwise, paint all vertex in the set with the same color, notice they form a consecutive interval in the list, then clear the list and include the current node you are processing. At the end you should paint all nodes remaining in the list with the same color.

## Rationale

We should partition the list in minimum amount of intervals such that all vertex within the same interval are not connected to any other vertex (they are an independent set). Since the first vertex in the list belong to an interval, this interval should start at this vertex. The proposed algorithm will find maximal interval containing this vertex. It is impossible to find any bigger interval containing the first vertex (since the one chosen is maximal) and it doesn't make any sense to find any smaller interval, since not taken vertex will only increase our restrictions in the future while taking next intervals.

## Pseudocode

```
Graph := Relations between vertex. Graph[u] is the list of all neighbors of u
List := Order of vertex. List[1] = v1, List[2] = v2, etc...

S := {} (Set with all nodes in the interval we are keeping)
color := 0 (Number of colors used so far)

# Iterate through all vertex
for vertex in List:

   # Check this node is not connected to any other node in S
   ok := True
   for neig in Graph[vertex]:
      if neig in S:
          ok := False
          break

   if ok:
       # If vertex is not neighbor of any other vertex in S, include it in.
       S.add(vertex)
   else:

       # Paint all vertex in S with color
       paint(S, color)

       # Increase color, since an interval of nodes was painted
       color += 1

       # Reset S, starting with current node.
       S := {vertex}

# Don't forget to paint last interval

# Paint all vertex in S with color
paint(S, color)

# Increase color, since an interval of nodes was painted
color += 1

```

## Complexity and details

Notice in the implementation you don't need to maintain the set of taken nodes S explicitly, since all nodes in that set belong to an interval they can be easily represented with two pointer (the begin of the interval and the end of the interval). The overall complexity of this solution is $O(|V| + |E|)$, since every node is visited once in the first loop, and edges are traversed twice, one per endpoint. Regarding `paint` function, it is potentially linear in the number of vertex it is painting, but that is ok, since we paint each vertex exactly once.

---
Tags: graphs
---


# Question
Title: Name of BFS variant with multiple queues with different priorities
Is there a name for the following variant of BFS that operates on trees with non-root starting point?:

* Instead of a single queue that all neighbor nodes are added to when processing a node, two queues are used ($Q\_A$ and $Q\_B$).
* Children nodes are added to $Q\_A$, and parent nodes are added to $Q\_B$.
* When selecting the next node to process, $Q\_A$ is drawn from, and only when $Q\_A$ is empty is $Q\_B$ drawn from.

One application for this (and the one that made me think of this) is for ranking "close" documents in a folder hierarchy (based on the leaf-node discovery order of the algorithm). For example in the following hierarchy:

```
- Root Folder
  - Folder 1
    - Document 1.1
    - Folder 1.2
      - Folder 1.2.1
        - Folder 1.2.1.1
          - Document 1.2.1.1.1
    - Folder 1.3
      - Document 1.3.1
  - Folder 2
    - Document 2.1

```

If we start our search at `Document 1.1` we would like to see the following ranking (which the algorithm produces):

1. `Document 1.1`
2. `Document 1.3.1`
3. `Document 1.2.1.1.1`
4. `Document 2.1`

`Document 1.2.1.1.1` should appear higher than `Document 2.1` since there is a closer common ancestor (`Folder 1`), even though the former is technically further away (distance of 4 vs. 5).

Some other things I considered that don't actually work:

* BFS using a single queue but always enqueuing the parent last. This doesn't work as it's still regular BFS and ranks based on shortest path.
* DFS, and always pushing the parent onto the stack first so it's discovered last. This could rank `Document 1.2.1.1.1` above `Document 1.3.1` depending on the order children are enqueued.

This seems like a pretty standard algorithm, but I couldn't find anything when I searched for it, so I was hoping someone might recognize it and know what it's called.

# Answer
> 0 votes
I don't think this particular implementation has a name, but there is a slightly different implementation that achieve the same goal and has a name: BFS 0-1.

Let me briefly describe the algorithm, and then let's solve your problem using this algorithm. For more complete description use previous link or Google about, it has a name.

Suppose you have a general graph (a tree will also work) where each edge has a weight, but the weight can only be 0 or 1. You are given a source node and should find minimal distance to every other node in the graph. This can be easily solved with Dijkstra's algorithm but complexity worsens. Instead of using Dijkstra, let's use BFS, with a deque (in the place of the queue). When we are traversing an edge with weight 0 we add this node to the beginning of the deque, otherwise you add it at the end.

Without going too much into the details of BFS 0-1 I'll apply it to your problem. Suppose that every time you are visiting an unvisited parent you add it to the end of the deque, and when you are visiting an unvisited child you add it to the front of the deque. The order in which you will visit the nodes in your file system will be the one desired. Notice now, that we are treating edges going to a parent as if they have weight 1, and edges going to children as if they have edge 0 (graph is obviously directed, since each edge has different weight when direction changes). The distance to each node from the source will be the distance to the closest common ancestor in the initial tree.

---

This is not exactly the same algorithm you were proposing, but notice that using the idea of two queues, is the same as having the deque and inserting from the beginning or from the end, so we can say both algorithms are basically equivalent. It can be naturally extended following your idea to support graphs were edges has weight such that they are numbers between $0$ and $k - 1$, using $k$ queues, however it is more tricky and out of the scope of this question.

---
Tags: algorithms, graphs, trees, graph-traversal, breadth-first-search
---


# Question
Title: necessary and sufficient pumping lemma - bounded pumping variant
There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular.

According to that lemma:

A language $L$ is regular **iff** $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^\*$, $ x=uvw \cap |v|\ge 1$ such that:

$$\forall i \ge 0,\ \forall z\in \Sigma^\*: uvwz\in L \iff uv^iwz\in L.$$

My question to you is: is there any way changing the *for all $i \ge 0$* condition to *for all $ 0\le i\le N$* for some $N$ \- and the lemma will still be correct?

That $N$ may be constant, depend on the lemma's k, and so on.

I can't find an approach to prove it, any ideas?

# Answer
> 1 votes
Yes, what you have observed is correct. We can, in fact, always take $N=0$. Here is the variant of Jeffrey Jaffe's pumping lemma where strings are pumped up or down exactly once.

---

A language $L$ is regular **iff** $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^\*$ such that $ x=uvw$, $|v|\ge 1$ and $\forall z\in \Sigma^\*$, $$uvwz\in L \iff uwz\in L.$$

---

As you have observed, the article has basically proved the above fact.

Here is a simpler proof of the "$\Longleftarrow$" direction. Let $\[y\]$ be the Myhill-Nerode equivalence class represented by string $y$. Suppose $|y|\ge k$.

Let $x$ be the first $k$ symbols of $y$ and $t$ be the rest of $y$, i.e., $y=xt$ and $|x|=k$. By assumption, there exists $u,v,w\in\Sigma^\*$ such that $x=uvw$, $|v|=1$ and $$yz=x(tz)=uvw(tz)\in L\iff uw(tz)=(uwt)z\in L.$$ The equivalence above means $\[y\]=\[uwt\]$. Since $uwt$ is $y$ with $v$ deleted, $|uwt|\lt |y|$. That means the shortest string in a Myhill-Nerode equivalence class must be shorter than $k$.

Since there are finitely many strings that are shorter than $k$ symbols, there are only finitely many Myhill-Nerode equivalence classes. By the celebrated Myhill-Nerode theorem, $L$ is regular.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Shortest distance between a point in A and a point in B
> Given two sets $A$ and $B$ each containing $n$ disjoint points in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \\{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q \in B \space \\} $.

I am not sure if I am right, but this problem very similar to problems that can be solved by linear programming in computational geometry. However, the reduction to LP is not straightforward. Also my problem looks related to finding the thinnest stip between two sets of points which obviously can be solved by LP in $O(n)$ in 2-dimensional space.

# Answer
> 5 votes
I have a solution which may seem a bit convoluted, but should be more efficient than the naive $\mathcal O(n^2)$ brute-force search:

1. let $v$ be the axis between the centres of mass of $A$ and $B$.
2. Sort the points in $A$ and $B$ along this axis in descending and ascending order respectively, resulting in the sequences $a\_0$, $a\_1$, ... , $a\_n$ and $b\_0$, $b\_1$, ... , $b\_n$.

The rest is in pseudo-code to make it clearer:

```
d = infinity.
for j from 1 to n
    if (b_1 - a_j) along v > d then break endif
    for k from 1 to n
        if (b_k - a_j) along v > d then
            break
        else
            d = min( d , ||b_k - a_j|| )
        endif
    enddo
enddo

```

That is, by pre-sorting the points along $v$, you can filter out pairs that will never be within $d$ of each other since $b\_k-a\_j$ along $v$ will always be $\le \\|b\_k-a\_j\\|$.

In the worse case this is still $\mathcal O(n^2)$, but if $A$ and $B$ are well separated, it should be much faster than that, but not better than $\mathcal O(n\log n)$, which is required for the sorting.

**Update**

This solution is by no means pulled out of a hat. It's a special case of what I use in particle simulations to find all the interacting pairs of particles with spatial binning. My own work explaining the more general problem is here.

As for the suggestion to use a modified line-sweep algorithm, although intuitively simple, I'm not convinced that this is in $\mathcal O(n\log n)$ when disjoint sets are considered. The same goes for Rabin's randomized algorithm.

There doesn't seem to be much literature dealing with the closest pair problem in disjoint sets, but I've found this, which makes no claim to being under $\mathcal O(n^2)$, and this, which doesn't seem to make any claims about anything.

The algorithm above can be seen as a variant of the plane sweep suggested in the first paper (Shan, Zhang and Salzberg), yet instead of using the $x$-axis and no sorting, the axis between the sets is used and the sets are traversed in descending/ascending order.

# Answer
> 4 votes
You can adapt the "closest pair" linesweep algorithm which is $O(n \log n)$.

The only change you will have to do is to ignore pairs that belong to the same set.

**Edit:** This is actually not simple (or even possible) as I described. See comments for discussion.

# Answer
> 4 votes
The idea in problems like this is to create an ordered structure from one of the sets that allows efficient queries of Nearest Neighbor. The classic paper that presented an O(log n) query structure for arbitrary dimension was:

Shamos and Hoey on Voronoi solutions

A number of other space partitions based on ideas from Delauney tesselations have been created since then, and these translate to a variety of subspace sweep descriptions as well. Note that the Voronoi method would also fall under a general divide-and-conquer description due to it's plane partitioning that makes the construction step O(n log n).

So, the basic solution to this problem is:

1. Take set A and build the efficient Nearest Neighbor query structure of your choice. This construction step is O(n log n) \[see theorem 4\].
2. For each element in B, query structure A for the nearest neighbor. Each query is O(log n) \[see theorem 15, fixed dimension\], so the total query time for all points in B is O(n log n).
3. When the result for the nearest point in A to each B is retrieved, put it in a structure ordered on the distance. This is O(log n) insert each result, or O(n log n) for all.
4. When all B have been looked at, you can quickly (O(1)) get the point B in the ordered structure with the smallest neighbor distance to a point in A.

As one can see looking at the complexity of each step, the total complexity is O(n log n). For the modern reader not looking at classic papers, this is covered in many algorithm books, e.g. "The Algorithm Design Manual" by Skiena.

# Answer
> 1 votes
> I am not sure if I am right, but this problem very similar to problems that can be solved by linear programming in computational geometry. However, the reduction to LP is not straightforward. Also my problem looks related to finding the thinnest stip between two sets of points which obviously can be solved by LP in in 2-dimensional space.

The Lower bound for this problem is $O(n\*\log{n})$ under algebraic decision tree model. I will give a rough sketch of its proof here.

We will reduce the instance of Element distinctness problem E to C.

* Input to E: $S = \\{a\_1, a\_2, a\_3,...,a\_n\\}$
* Let $\epsilon$ \> 0 be a a small fraction
* A = $\\{(a\_i,0) : 1 \leq i \leq n\\}$, $B = \\{(a\_i + \epsilon) : 1 \leq i \leq n\\}$
* Now If we can find the shortest distance (d) between sets A and B. We can decide the element distinctness problem in additional $O(n)$ time as follows
    + The set $S$ has a duplicate if and only if d = $\epsilon$

We know that the lower bound on runtime for deciding Element distinctness problem is $O(n\*\log{n})$. Therefore, by reduction the lower bound also applies to our problem.

# Answer
> 1 votes
If you are using Python, you can use the implementation of sklearn pairwise\_distances\_argmin\_min that given two point sets A and B returns the closest point *p*B in B and the distance from *pA* to *pB* for each point *pA* in A.

You then select the pair of points with the smallest distance of all in $O(n\log n)$:

```
from sklearn.metrics import pairwise_distances_argmin_min
import numpy as np

def get_closest_pair_of_points(point_list_1: List[Tuple[float]],
                           point_list_2: List[Tuple[float]]) -> Tuple[Tuple, Tuple, float]:
    """
    Determine the two points from two disjoint lists of points that are closest to
    each other and the distance between them.

    Args:
        point_list_1: First list of points.
        point_list_2: Second list of points.

    Returns:
        Two points that make the closest distance and the distance between them.
    """
    indeces_of_closest_point_in_list_2, distances = pairwise_distances_argmin_min(point_list_1, point_list_2)

    # Get index of a point pair that makes the smallest distance.
    min_distance_pair_index = np.argmin(distances)

    # Get the two points that make this smallest distance.
    min_distance_pair_point_1 = point_list_1[min_distance_pair_index]
    min_distance_pair_point_2 = point_list_2[indeces_of_closest_point_in_list_2[min_distance_pair_index]]

    min_distance = distances[min_distance_pair_index]

    return min_distance_pair_point_1, min_distance_pair_point_2, min_distance

```

Of all implementations I have tested this is was fastest. It also does not have any limitations on the point distribution (such as two point sets being separable in space by a plane, etc.)

---
Tags: algorithms, computational-geometry
---


# Question
Title: Is regex with backreference still able to be implemented by finite automata?
I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex `(.)\1{2,}` matches two or more consecutive appearances of the same character like 'aa', '...', '------', etc. However, such feature seems exceeds the capability of finite state machine which is the underlying implementation of regex. It seem like it needs to remember the matched part and match with it again, but the matched part its self have infinite possible values. I'm just speculating but have no idea to prove or disprove it. My doubt is, does the regex with backreference still have finite number of states?

# Answer
No, it doesn't. With backreferences, it is trivial to write a regex that matches exactly the standard textbook example of a non-regular language, $\\{ a^nb^n \mid n \in \mathbb{N} \\}$. A finite number of states can only distinguish between finitely many different prefixes in $a^\*$, so it won't do.
> 2 votes

---
Tags: finite-automata, regular-expressions
---


# Question
Title: Smallest number close to 0 in IEEE754 (64bits)?
I thought the smallest number close to 0 would be : 0 00000000001 (exponent) 0000000000000000000000000000000000000000000000000000 (significand)

But this site (http://binaryconvert.com/result\_double.html?hexadecimal=0000000000000001) shows that the smallest number close to 0 is : 0 00000000000 (exponent) 0000000000000000000000000000000000000000000000000001 (significand) According to what I know, when all components of exponent are 0 then the number must represent 0. Thus, this is not possible! How could this happen?

# Answer
It's not true that when all components of the exponent are 0 then the number must represent 0. A (normalized) floating point number is composed of two parts: sign, exponent, and mantissa. The value of the number is $$ \text{sign} \times 1.\text{mantissa} \times 2^{\text{exponent} + \text{base}}, $$ where the sign is $\pm 1$ (though encoded as a bit), and $\text{base}$ is a constant which depends on the format.

As you can see, $0$ cannot actually be represented at all! Some numbers, like zero, infinity, NaN and denormalized numbers have special representations. Zero, for example, is represented in IEEE 754 (the standard format) using zeroes for both mantissa and exponent.

In IEEE 754, an exponent of zeroes represents a *denormalized* number. In such numbers, instead of 1.mantissa we have 0.mantissa, and this allows representing numbers which are closer to zero (calculate and see!).
> 4 votes

# Answer
"According to what I know": What often gets us into trouble are the things that we "know", but that aren't so.

A stored exponent of zero means this is a denormalised number. The mantissa has no implicit leading bit but can have any number of bits set, and the mantissa is then scaled the same as if the stored exponent was 1. So the smallest none-zero floating point number is indeed a stored exponent of 0, and a stored mantissa of 1.
> 0 votes

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