# Question
Title: In theory, is it impossible, or possible (although ridiculously impractical), to inline recursive functions?
In an older question I asked about stack, the statement came up that recursive functions cannot be inlined (link). I am interested in whether this statement is actually true or not. I understand that it is extremely impractical. But, is it impossible, in theory? To my intuition, it seems like it should be possible. But I might lack the ability to imagine recursive functions that cannot be inlined.

I am in no way an expert. I am just curious. I like to understand constraints.

The recursive factorial function for a factorial like this:

```
int factorial(int n) {
    if(n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}

```

Can for example be inlined as below. Each return value is stored in its own integer. The max depth here is 4, but can be increased arbitrarily at the cost of program size (in some way analogous to how the cost for recursive functions with subroutines is the stack size. ) Extremely impractical, but, I am just interested in: is it impossible, or possible.

```
int factorial_inlined(int n) {
    if(n > 1) {
        int n1;
        if((n-1) > 1) {
            int n2;
            if((n-2) > 1) {
                int n3;
                if((n-3) > 1) {
                    int n4;
                    if((n-4) > 1) {
                        n4 = 1; // Inlining max depth reached
                    }
                    else {
                        n4 = 1;
                    }
                    n3 = (n-3)*n4;
                }
                else {
                    n3 = 1;
                }
                n2 = (n-2)*n3;
            }
            else {
                n2 = 1;
            }
            n1 = (n-1)*n2;
        }
        else {
            n1 = 1;
        }
        return n*n1;
    }
    else
        return 1;
}

int main() {
  cout << factorial_inlined(4) << endl;
  return 0;
}

```

I am also able to inline Towers of Hanoi to a depth of two (it has no return values though) and my intuition is that it can be arbitrarily increased to any depth (at the cost of program size. )

```
void hanoi(int n, char src, char dst, char aux) {
    if (n == 0) {
        // base case: do nothing
    } else if (n == 1) {
        // base case: move top disk from src to dst
        cout << "Move disk from " << src << " to " << dst << endl;
    } else {
        // recursive case:
        // move top n-1 disks from src to aux
        if (n-1 == 0) {
            // base case: do nothing
        } else if (n-1 == 1) {
            // base case: move top disk from src to aux
            cout << "Move disk from " << src << " to " << aux << endl;
        } else {
            // recursive case:
            // move top n-2 disks from src to dst
            if (n-2 == 0) {
                // base case: do nothing
            } else if (n-2 == 1) {
                // base case: move top disk from src to dst
                cout << "Move disk from " << src << " to " << dst << endl;
            } else {
                // recursive case: do nothing
            }
            // move remaining disk from src to aux
            cout << "Move disk from " << src << " to " << aux << endl;
            // move top n-2 disks from dst to aux
            if (n-2 == 0) {
                // base case: do nothing
            } else if (n-2 == 1) {
                // base case: move top disk from dst to aux
                cout << "Move disk from " << dst << " to " << aux << endl;
            } else {
                // recursive case: do nothing
            }
        }
        // move remaining disk from src to dst
        cout << "Move disk from " << src << " to " << dst << endl;
        // move top n-1 disks from aux to dst
        if (n-1 == 0) {
            // base case: do nothing
        } else if (n-1 == 1) {
            // base case: move top disk from aux to dst
            cout << "Move disk from " << aux << " to " << dst << endl;
        } else {
            // recursive case: do nothing
        }
    }
}

int main() {
hanoi(2, 'A', 'C', 'B');
return 0;
}

```

**Edit:** To clarify in response to answer that mentioned the inlined Factorial could not do n = 10, yes it was inlined to a max depth of 4. To inline it to a max depth of 11 (supporting n = 10 and also n = 11) it can just be expanded as below. The cost in program size for this, is in some way analogous to the cost in stack size (a larger stack is needed for deeper recursive calls, or it will overflow. )

```
int factorial_inlined(int n) {
    if(n > 1) {
        int n1;
        if((n-1) > 1) {
            int n2;
            if((n-2) > 1) {
                int n3;
                if((n-3) > 1) {
                    int n4;
                    if((n-4) > 1) {
                        int n5;
                        if((n-5) > 1) {
                            int n6;
                            if((n-6) > 1) {
                                int n7;
                                if((n-7) > 1) {
                                    int n8;
                                    if((n-8) > 1) {
                                        int n9;
                                        if((n-9) > 1) {
                                            int n10;
                                            if((n-10) > 1) {
                                                int n11;
                                                if((n-11) > 1) {
                                                    n11 = 1; // Inlining max depth reached
                                                }
                                                else {
                                                    n11 = 1;
                                                }
                                                n10 = (n-10)*n11;
                                            }
                                            else {
                                                n10 = 1;
                                            }
                                            n9 = (n-9)*n10;
                                        }
                                        else {
                                            n9 = 1;
                                        }
                                        n8 = (n-8)*n9;
                                    }
                                    else {
                                        n8 = 1;
                                    }
                                    n7 = (n-7)*n8;
                                }
                                else {
                                    n7 = 1;
                                }
                                n6 = (n-6)*n7;
                            }
                            else {
                                n6 = 1;
                            }
                            n5 = (n-5)*n6;
                        }
                        else {
                            n5 = 1;
                        }
                        n4 = (n-4)*n5;
                    }
                    else {
                        n4 = 1;
                    }
                    n3 = (n-3)*n4;
                }
                else {
                    n3 = 1;
                }
                n2 = (n-2)*n3;
            }
            else {
                n2 = 1;
            }
            n1 = (n-1)*n2;
        }
        else {
            n1 = 1;
        }
        return n*n1;
    }
    else
        return 1;
}

int main() {
  cout << factorial_inlined(11) << endl;
  return 0;
}

```

# Answer
> 3 votes
I think you're conflating two different problems here.

One is "inlining" (the elimination of a method call), the other is "loop unrolling" (the elimination of a jump instruction).

Certainly, recursive method calls can always be replaced with a loop and a stack, and therefore a recursive method can be inlined by transforming it into a loop with a stack.

And loops which operate for a fixed number of iterations can always be unrolled.

# Answer
> 2 votes
Your inlined factorial function is incorrect. When $n=10$ (for instance), it gives the wrong result. This is not considered a correct way of inlining. The implicit requirement, when inlining is that the code must maintain the same behavior.

Of course, if you don't require that the code produce the same result in all cases, it is trivial to do such an inlining. For instance, you could just replace the factorial function with "return 42". But this is rather silly and useless.

As far as whether you can inline a recursive function, not in the straightforward way. But there are ways to inline it while maintaining correct behavior. For instance, if it is tail-recursive, as in the factorial function, you can replace the entire function with a loop. More generally, you can replace the recursive implementation with an iterative implementation that uses an explicit stack, and then inline that.

So, in general, yes, it is always possible to replace the code of the function in such a way that it can be inlined, while always producing the same result from the computation. Whether you consider that useful in practice or the kind of answer you were looking for is up to you.

# Answer
> 2 votes
It is usually up to the compiler what exactly to do, and an "inline" command is just a hint. Inlining is usually a trade between call overhead and the amount of code, and the compiler is in the best position to decide. In addition, the compiler may be able to optimise the code because it knows the parameters at call time, so factorial(5) might be turned into 120. For trivial functions, calling them could be more code than inlining, so the decision is easy. For the factorial function, it's not.

I'd expect the compiler to recognise recursion, directly or indirectly, so it doesn't inline forever. It can just refuse inlining. In case of the factorial function, analysis by a human and the assumption that n is usually not small (0, 1 or 2) shows that one level of inlining in the function itself saves half the calls. I'll write a slightly different call for readability. Original:

```
return n <= 1 ? 1 : n * factorial(n-1)

```

Inlining one level:

```
return n <= 1 ? 1 : n * (n - 1 <= 1 ? 1 : (n-1) * factorial(n-2)

```

Simplify:

```
return n <= 1 ? 1 : n * (n <= 2 ? 1 : (n-1) * factorial(n-2)

```

Optimise:

```
return n <= 1 ? 1 : n <= 2 ? n : n * ((n-1) * factorial(n-2))

```

This saves half the calls, with little extra code. Now the compiler needs to realise that at some time it needs to stop inlining. As an intelligent human I know that another level of inlining reduces the calls from 1/2 to 1/3, so much less benefit, and ten levels of inlining is pointless. For a compiler that could be a compiler setting, or the compiler author having a clever algorithm to stop at the right time.

From experience, I did an experiment with an inlined fibonacci function, and the compiler got very, very slow with fib(20) and crashed with fib(26).

Note that in this case inlining is most effective if you only inline calls within the function itself - if a random other function calls "factorial" then inlining at the caller site has very little positive effect.

---
Tags: recursion, assembly
---


title: Coding max as an interaction net

text:
# Question
Title: Coding max as an interaction net
I am reading Yves Lafont's introductory paper Interaction Nets. Early in the beginning he mentions that max cannot be coded as follows

since in this coding it is not possible to choose which argument to look at first (so necessitating the need for a principle port). But I don't understand why it's wrong. I am trying to come up with an example where certain choice of rewritings will lead to a wrong answer.

# Answer
> 2 votes
Rules for agents in interaction nets are defined by what the principal port of that agent is connected to and each agent has exactly one principal port.

In the "max" example, for the top left rule to work the principal port of the Max agent must be the one connected to the 0.

But then the top right rule can only depend on the value of x, not the 0. So the top right rule cannot be differentiated from the bottom rule (assuming x is not 0) and the bottom rule does not work if the y value is 0.

It is usual, when drawing interaction nets, for the principal port to have a little arrow drawn on it, to make this clear.

Lafont goes on to show how to make this work via an intermediate step, but I assume you've read that.

---
Tags: programming-languages, term-rewriting, combinatory-logic
---


# Question
Title: What remains after removing leaves and roots from a directed graph?
Suppose I start with a directed graph, and remove any leaf nodes, and then repeatedly remove leaf nodes from the now-modified graph until there are no more leaves. Then I repeatedly remove root nodes as well. What is the remaining graph when there are no more roots or leaves? (Assuming it's not empty.)

I have an idea that any remaining subgraph is the "loopy part", which, I guess, must contain any cycles in the original graph. Is there a name or very short description of this loopy part?

# Answer
> 2 votes
I don't think there is a particular name for this. Indeed, each cycle is contained in this graph, but there also could be some vertices which are not in any cycle, so I am not so sure about the "loopy" name.

For example, consider the following graph. No vertex is removed using your transformation, but the vertex $4$ is not in any cycle.

---
Tags: graphs
---


# Question
Title: Choosing the appropriate starting vertex
There are n houses in a city T, some of which are connected by streets in such a way that there is exactly one path between any two houses (i.e. the graph of houses and streets is a tree T).

Tanya has already prepared $m$ gift bags but she ran into a problem. After all, she herself also needs to find a house in the city of T for the celebration of the New Year. The distribution of gifts, as usual, will be done by deer.

You can give exactly one bag to one deer and send it on its way. At the same time, deer do not walk along the same street twice. The i-th bag is intended for residents of all houses on the path from $a\_i$ to $b\_i$. Therefore, it is considered that the deer can be given the i-th bag of gifts if he can leave the place where Tanya is celebrated and go through all the houses on the way from $a\_i$ to $b\_i$ without going through the same street twice -- that is, there should be a linear path from the starting location to house $b\_i$, starting at house $a\_i$.

How do we efficiently compute the maximum number of bags with gifts that Tanya can give away if she chooses the optimal house for the celebration.

We know that given a choice of root vertex she can give away a big of gifts that is supposed to travel on a route from $a\_i$ to vertex $b\_i$ if the least common ancestor of $a\_i$ and $b\_i$ is just $a\_i$, so we could compute it in O(n\*m) but it should be possible to do it faster.

The input consists of the following:

First we specify the number of vertices $n$.

Then we have $n-1$ edges given as $x\_i, y\_i$.

Then we have a number $m$ followed by $m$ lines that indicate what routes we want to deliver bags along

Each line is of the form $a\_i$, $b\_i$.

Source: https://algocode.ru/files/course\_ap2021/contest-24956-ru.pdf

# Answer
> 1 votes
It should be possible to solve the problem in O(NlogN+M) time. I don't currently have a functional algorithm, but here's an outline of my first thoughts that may help. What I thought of was a mix of DFS and a sweeping line algorithm, starting at a leaf node. A key observation seems to be that starting on all nodes on the side of the `a_i` node that doesn't have `b_i` on it will allow Tanya to give that gift while starting on the side with the `b_i` will not allow Tanya to give the gift. If only we knew which side each `b_i` was on, relative to each `a_i`, then we would be able to solve the problem easily.

Algorithm outline:

1. Input the graph as an adjacency list.
2. Keep a map mapping all the a\_i's to b\_i's and all the b\_i's to a\_i's. Call this map `C`.
3. Keep a set of all the a\_i's `A`.
4. Keep an array of booleans `D` of size `N`, initialized to all be false. This will record whether each node has been visited.
5. Preparation for DFS.

**a.** Keep an array `gifts` of size `N` to store the number of gifts we can give if we start at each node.
**b.** Keep an integer `k`, initialized to `0`. This will be the amount by which the values of the graph are offset.
**c.** Find an arbitrary leaf node `v` by looping through the adjacency list and finding a node with only one edge. This will be the starting point for the DFS.
**d.** Initialize `gifts[v]` by setting it equal to `m`, and initialize `D[v]` by setting it to `true`.
6. Start DFS at `v`. For every node `w`:

**a.** If `w` is in the set `A` and `D[C[w]]` is `false` (`w` is an a\_i and its corresponding b\_i has not been visited), set `gifts[next unvisited child of w]` to be `gifts[w]-1`. Continue DFS from that child.
**b.** Else if 'w' is in the set `A` and `D[C[w]]` is `true` (`w` is an a\_i and its corresponding b\_i has been visited), set `gifts[w]` to be `gifts[w]+1`. Set `k` to `k+1`. Continue DFS from the next unvisited child of `w`.
**c.** If neither of the above statements is true, then set `gifts[next unvisited child of w]` to `gifts[w]`. Continue DFS from that child.
**d.** Update D to show that the new node in the DFS is now visited.
7. Analyze results. For each node `w`, the number of gifts Tanya will get by starting from that node will be `gifts[w]-k`. The answer you're looking for will be the maximum value of this over all possible `w`.

If you've read this far, try working this algorithm out on a sample test case.

Note that right now the solution doesn't work 100% -- when the a\_i and b\_i are on separate branches and the DFS reaches the a\_i first, the algorithm will return the wrong answer. Perhaps this is fixable while still maintaining a good runtime, or perhaps we need a different way of traversing the graph (other than DFS).

The time complexity of the above algorithm is `O(NlogN+M)` as DFS goes through N nodes and the complexity for each node is `O(logN)` from checking whether node `w` is in set `A`, while preprocessing of the `M` paths gives the `+M`.

---
Tags: algorithms, graphs
---


# Question
Title: Greedy algorithm-maximal minimum average of n pairs
Lets assume $2n $ gifts such that each gift $i$ has price $a\_i$

The goal is to find a partition of the gifts into $n$ pairs such that each pair $P\_i=\left(a\_{i\_{0}},a\_{i\_{1}}\right)$ has maximal minimum average IE $ \min\_{i\le n}\left\\{ \frac{a\_{i\_{0}}+a\_{i\_{1}}}{2}\right\\} $ is maximal.

How to get a contradiction inside the induction proof?

So the algorithm I guessed(with a lot of python examples):

```
 1. Initiate a pair array P of size n
 2. Sort the array of prices A in ascending order.
 3. for i<n:
        P.insert(A[i],A[2n-1-i])

```

I struggle to prove its correctness with induction. for the base case I assume that since $Sol\_0=\emptyset$ then $Sol\_0\subseteq Opt $ for some optimal solution. then assuming for $i\<k$ that each iteration is good,IE $Sol\_i\subseteq Opt $ for some opt.

now the kth iteration, IE $Sol\_k=Sol\_{k-1}\cup (a\[k\],a\[2n-1-k\])\nsubseteq Opt $

This means that the pair we just added is not part of any optimal solution, so there are some $\left(a\[r\],a\[w\]\right)\in\widehat{Opt}$ such that $ \frac{a\[k\]+a\[2n-1-k\]}{2}\<\frac{a\[r\]+a\[w\]}{2} $

$(a\[r\],a\[w\])$ are the minimum average of some $Opt$

How do I get a contradiction here?

As for the $Sol\_{n}\supseteq Opt$ I can say that since we had $n$ iterations and at each iteration we added a single pair, after $n$ iterations we have $\left|Opt\right|=\left|Sol\right|=n$ therefore there is a mutual inclusion.

# Answer
Here is the induction step that shows $Sol\_k\subset$ some optimal solution.

By induction assumption, there is an optimal solution $O\_k$ that contains the same pairs as $Sol\_k$ except possibly the last pair, $(a\[k\],a\[2n-1-k\])$.

* If $(a\[k\],a\[2n-1-k\])\in O\_k$, we are done.
* Otherwise, $(a\[k\],a\[2n-1-k\])\notin O\_k$.
Let $(a\[k\],a\[j\])$ and $(a\[\ell\], a\[2n-1-k\])$ be the pairs in $O\_k$ that contain $a\[k\]$ and $a\[2n-1-k\]$ respectively.

Let $O\_k'$ be the solution that is the same as $O\_k$ except that pairs $(a\[k\],a\[j\])$, $(a\[\ell\], a\[2n-1-k\])$ are replaced with $(a\[k\],a\[2n-1-k\])$, $(a\[\ell\],a\[j\])$.

Since $a\[k\]$ and $a\[2n-1-k\]$ are the minimum element and the maximum element in the remaining elements respectively, we have $a\[k\] \le a\[\ell\]$ and $a\[j\]\le a\[2n-1-k\]$. So $$ \frac{a\[k\]+a\[j\]}2 \le \min(\frac{a\[k\]+a\[2n-1-k\]}2, \frac{a\[\ell\]+a\[j\]}2),$$ which implies the minimum pair average of $O\_k$ is not greater than that of $O\_k'$. Since $O\_k$ is an optimal solution, so must be $O\_k'$.

Since $O\_k'$ contains the pair $(a\[k\],a\[2n-1-k\])$, we are done.

---

If you have to use proof by contradiction, then the existence of $O\_k'$ gives rise to a contradiction. This will be an example when proof by contradiction only brings unnecessary clutter.
> 1 votes

# Answer
Let $P = \\{P\_0, …, P\_{n-1}\\}$ be the set of pairs returned by your algorithm and $P' = \\{P\_0', …, P\_{n-1}'\\}$ be an other set of pairs.

Denote $f(P) = \min\limits\_{i=1}^n(a\_{i,0} + a\_{i,1})$ where $P\_i = \\{a\_{i,0}, a\_{i,1}\\} = \\{a\_i, a\_{2n-i-1}\\}$ (I got rid of the $\frac{\cdot}2$ part, because it does not change the result) and let $m\in \\{0, …, n-1\\}$ be an index such that $f(P) = a\_m + a\_{2n-m-1}$.

Let $i\in \\{0, …, 2n - 1\\}$ be the index of the element paired with $a\_m$ in $P'$. Let us distinguish:

* if $i \leqslant 2n-m-1$, then $f(P') \leqslant a\_m + a\_i \leqslant a\_m + a\_{2n-m-1} = f(P)$;
* if $2n-m-1 \< i$, then by the pigeonhole principle, there exist two indices $j \< m$ and $k \leqslant 2n-m-1$ such that $a\_j$ and $a\_k$ are paired together in $P'$. If that's the case, $f(P') \leqslant a\_j + a\_k \leqslant a\_m + a\_{2n-m-1} = f(P)$.

That means that $P$ is optimal.
> 3 votes

---
Tags: greedy-algorithms, correctness-proof, induction
---


# Question
Title: Inflate a polyline so that the 2D band can be triangulated without self-intersections
**Introduction**

I have simple polylines as sequences of points. I need a triangulation with a configurable width. The goal is to get a 2D 'band' from the input polyline without self-intersections.

**Description:**

Input is a 2D point sequence {P1, ..., Pn} (Polyline) and a target width of the triangulated band. Output is the triangulation without self intersection:

In the current implementation I move the segments formed by {P1, .., Pn} in both perpendicular directions. The outline points to be triangulated are calculated by intersection of the translated segments (red dots in the image above).

The problem with this approach is that in sharp angles the resulting intersection points generate self-intersecting triangles:

**Question**

Is there a robust algorithm to triangulate a band from a polyline without generating self-intersections?

**References:**

* this approach seems to be similar but also does not solve the self intersection problem
* Clipper2 has an InflatePath method that does the offset but I don't know how to triangulate the resulting path
* An approach would be to just triangulate the outline points with Delaunay but I don't know how to restrict the result to triangles inside the 'Band'
* A very nice explanation of Constrained Delaunay Triangulation

# Answer
> 1 votes
I think your "inflated polyline" can be correctly defined as a *union* of "inflated line segments". Each such "inflated line segment" will be a rectangle with half-disks on its two opposite ends, describing all points $p \in \Bbb R^2$, such that their distance from the segment is not more than a (configurable) constant $W$:

However you'll get an area with *circular arcs* on its boundary, so it'll be not easy to triangulate it. Probably you don't need all this heavy artillery, like the Delaunay triangulation - a couple of simple heuristics will do the job for you.

For example, to solve the problem with intersecting triangles in case of sharp turns you need to consider not only pairs of adjacent segments - you need to **analyze longer chains of segments** and skip segments, which don't contribute to the boundary. Please see below - the segment $s2$ doesn't contribute to the boundary, because it's located too deep inside the "inflated polyline". The point, marked by red color, belongs to the boundary of the union of two "inflated line segments" $s1$ and $s3$, so this point should be the triangulation vertex:

Please note, that this segment $s2$ can't be ignored on the other side of the polyline. These ignored segments can appear in groups, and be on both sides of the polyline. As a result, this triangulation won't be so simple and regular compared to your one.

---
Tags: algorithms, computational-geometry, polygons, triangulation
---


# Question
Title: Why is a heap better than a linked list for implementation of a priority queue?
Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.

Why is it better to have log-n for both than n for one and constant time for the other?

# Answer
It only really matters in the limit: for small sizes, the difference isn't really important.

But if you're doing a large number of each operation, $O(\log n) + O(\log n) = O(\log n)$ is asymptotically faster than $O(n) + O(1) = O(n)$.
> 3 votes

# Answer
We have a simple equation: Number of insertions = number of removals + size of priority queue. If the number of insertions is n, then the heap will be faster as long as the number of removals is at least n / log n. And if the number of removals isn't that large, then your priority queue will grow in size very, very quickly.
> 1 votes

---
Tags: complexity-theory, time-complexity, runtime-analysis, heaps, priority-queues
---


# Question
Title: Derive complexity from recurrence relation
On the Wikipedia article on Karatsuba algorithm (https://en.wikipedia.org/wiki/Karatsuba\_algorithm#Time\_complexity\_analysis) it is stated:

$T(n) = 3 T(\frac{n}{2}) + cn + d$

And then, by invocation of the "master theorem" it is deduced that $T(n) = O(n^{\log\_2{3}})$.

My question is, is there an easy way in this case to derive this complexity from the relation without referring to the master theorem nor to a recurrence that supposes we already know the result?

# Answer
Here is a way to solve the recurrence without using the Master theorem and without substitution (which requires guessing the form of the solution). I'll assume for simplicity that $n$ is a power of $2$ and that $T(1) \le c + d$ (otherwise you can just consider a larger value of $d$).

Let's make some simplifications first. They are not really needed, but will make the following calculations easier. First of all notice that you can hide the additive constant $d$ into the multiplicative constant of $n$. For example, by defining $k=(c+d)$ you have $T(n) \le \frac{3}{2} T(n/2) + kn$ for all $n \ge 1$.

We can now get rid of $k$ altogether by defining $S(n) = \frac{T(n)}{k}$, which satisfies $S(n) = \Theta(T(n))$ and leads to the following recurrence: $$ S(n) = \frac{T(n)}{k} \le 3 \cdot \frac{T(n/2)}{k} + n = 3 S(n/2) + n. $$

Consider now the recursion tree for $S(n)$. Each recursive call will halve the input size, therefore the height of the tree will be $\log\_2 n$. Moreover, there are $3^i$ recursive calls at a generic depth $i$ (each having input size $\frac{n}{2^i}$), which contribute $3^i \cdot \frac{n}{2^i} = n \cdot \left( \frac{3}{2} \right)^i$ to $S(n)$.

Upper bounding $S(n)$, and hence $T(n)$, is now just a matter of finding an upper bound to the overall time spent across all depths, which yields the following geometric series (the base of all $\log$s is $2$): $$ \begin{align\*} S(n) \le n \sum\_{i=0}^{\log n} \left( \frac{3}{2} \right)^i & \le n \cdot \left( \frac{3}{2} \right)^{\log n + 1} = \frac{3n}{2} \cdot 2^{\log n \cdot \log \frac{3}{2}} = \frac{3n}{2} \cdot n^{\log \frac{3}{2}} \\ &= \frac{3}{2} \cdot n^{\log 2 + \log \frac{3}{2}} = \frac{3}{2} n^{\log 3} = O(n^{\log 3}). \end{align\*} $$
> 0 votes

# Answer
Set $n=2^m$. The recurrence now writes

$$T(2^m)=3T(2^{m-1})+2^mc+d$$ or

$$S(m)=3S(m-1)+2^mc+d.$$

A solution of the homogeneous recurrence ($S(m)=3S(m-1)$) is $S(m)=3^m$ and this makes us set, by variation of the constant

$$S(m)=3^mR(m),$$ giving

$$R(m)=R(m-1)+\frac{2^mc+d}{3^m}.$$

The solution is easily seen to be

$$R(m)=R(0)+\sum\_{k=1}^m\frac{2^kc+d}{3^k}\\\=R(0)+\frac{\dfrac23\left(1-\left(\dfrac23\right)^m\right)c+\dfrac13\left(1-\left(\dfrac13\right)^m\right)d}{1-\dfrac13}.$$

This is asymptotic to the constant

$$R(0)+c+\frac d2,$$

making $R(m)=\Theta(1)$, $S(m)=\Theta(3^m)$ and $T(n)=\Theta(3^{\log\_2n})=\Theta(n^{\log\_23})$.
> 0 votes

---
Tags: algorithms, time-complexity, big-o-notation
---


# Question
Title: Paint a Cube by rolling it (Puzzle Algorithm)
I stumbled across this game in Simon Tatham's puzzle app. It's called cube. The description according to the game is:

> You have a grid of 16 squares, six of which are blue; on one square rests a cube. Your move is to use the arrow keys to roll the cube through 90 degrees so that it moves to an adjacent square. If you roll the cube on to a blue square, the blue square is picked up on one face of the cube; if you roll a blue face of the cube on to a non-blue square, the blueness is put down again. (In general, whenever you roll the cube, the two faces that come into contact swap colours.) Your job is to get all six blue squares on to the six faces of the cube at the same time.

Attached is a link to a screenshot of the game .

I would like to ask the CS community if there is a known algorithm for solving such a problem as I haven't found anything online.

# Answer
> 12 votes
As Dmitry noticed there is very little possible states of the game, so it's relevant to search for solution using BFS traversal. But let's start from some numbers.

### Staring positions

In terms of possible staring states we have $$ 16 \cdot {16 \choose 6} = 128128 $$ Coloring of $4\times4$ gird using $6$ colors gives ${16 \choose 6}$ cases, and $16$ for initial position of cube, but you can easily reduce this number by a factor of $16$, because you always can place cuboid on any (white) cell of the gird not changing its coloring pattern (after each move doing its reverse and doing this move again).

**notice:** we can use such trick only finding any solution, not optimal one.

Secondly we aren't interested in starting positions that are symmetric. So let's eliminate them, and enumerate positions (Burnside lemma will be helpful). The final count equals

$$1051 \\; \text{positions}$$

Concluding, we can use this fact and precompute solutions for all possible starting game states and it won't hurt our memory.

### Algorithm

Let's construct directed graph of this game. Each node will be representing some state of the game (including current coloring of grid, position of cube and colors on the cube itself). Each directed edge from one state to another will represent possibility of moving between this states (each state has at most $4$ neighbors, so graph isn't dense).

Then using BFS on so build graph, we can calculate (for example) distance to each state from initial one. That's even better, because now we can find optimal solution! And this is description of above approach:

1. Create queue containing starting state
2. Repeat while solved state aren't found
3. Take first state from queue and mark as visited
4. For each achievable next state, push it on queue (if next state is unvisited already)

### Implementation

I have created github repo with implementation of such approach. Check it out if you are interested!

Lastly, example solution may look like this one:

# Answer
> 6 votes
Of course, but let me show the process on simpler example and then just use same method for calculating final count.

### Small example

We are given $2 \times 2$ square grid and two colors (black and white). We are trying to find out number of different coloring of this grid. Obviously, there are $2^4 = 16$ possible patterns, but we don't want to count symmetrical ones twice. To visualize problem, look at below table:

I've printed all $16$ cases, but I also grouped them by symmetry (there are $6$ different patterns). The key is to deeply analyze those symmetries. There are $8$ isometries of a square:

1. Identity (or $0^\circ$ rotation)
2. Rotations: $90^\circ$, $180^\circ$, $270^\circ$ rotations
3. Reflections: x-axis, y-axis reflections and both diagonal reflections

From now, we'll call this set a **group**, also denoted as $D\_4$ (more info about this particular group here)

#### Useful definitions

For some coloring $a$, let **orbit** of $a$ be the set of coloring patterns that are achievable from $a$ by applying on it any symmetry of a square (denoted as $\texttt{orb}(a)$). Example:

**note:** On the first table we grouped patterns into orbits.

For any isometry $g$, the set of its **fixed points** will be all colorings of a such that $g(a) = a$ \- we will denote this set as $\texttt{fix}(g)$. Example (here $g$ is vertical reflection):

Our problem has been reduced to counting orbits. So let's jump right into Burnside lemma:

$$ | \Omega | = \frac{1}{|G|} \cdot \sum\_{g \in G} | \texttt{fix}(g) | $$

Here $\Omega$ is set consisting all orbits, so finding $|\Omega|$ is our goal. Our group of symmetries is here denoted as $G$.

That's great because we don't care about set of possible colorings (which can have too many elements). The only difficulty left is calculation for each isometry how many fixed points it has. To do this, we have to look which of the corners of the square the given isometry transforms on which ones. This way we will break them down into cycles and each one will have to be the same color. If an isometry has $k$ cycles, then it has $2^k$ fixed points, because we color each of them with one color.

For simplicity, let's enumerate corners of the square from $1$ to $4$. The table below shows what cycles will arise for all isometries. I encourage to do a thorough analysis.

And just plug this result into Burnside lemma:

$$ | \Omega | = \frac{2^4 + 2 \cdot 2^3 + 3 \cdot 2^2 + 2 \cdot 2 }{8} = \frac{48}{8} = 6 $$

Just as we expected.

**side note:** It's easy to generalize this process for any number of colors.

### Final count

Now, when we have such a powerful mathematical machinery, we can proceed to calculate the proper count. This time we should take into consideration larger grid, hence we must analyze more complex cycles.

Let's start from identity. We have $16$ one-piece cycles, but only $6$ may be blue. Value of $\texttt{fix}$ for identity is $16 \choose 6$.

Then $90^\circ$ and $270^\circ$ rotation have $4$ cycles, each with $4$ elemets, we cannot color such gird using $6$ colors. Hence $\texttt{fix}$ for both this rotations is $0$.

Let's move on to $180^\circ$ rotation and both vertical and horizontal flips. All of these isometries has $8$ cycles, with $2$ elements in each. So we must color $3$ out of $8$ cycles to blue. Hence result for these three is $8 \choose 3$.

And lastly, both diagonal flips has $4$ single element cycles and $6$ containing two elements. So we can pick $4$, $2$ or $0$ from diagonal which sum up to $116 = 6 + 90 + 20 = 6 + {4 \choose 2} {6 \choose 2} + {6 \choose 3}$.

What gives longed-for result (denoted with $F$)

$$ F = \frac{8008 + 3 \cdot 56 + 2 \cdot 116}{8} = \frac{8408}{8} = 1051 $$

---
Tags: algorithms, board-games, group-theory
---


# Question
Title: Size and height of binary tree, different interpretations?
I can't seem to get my head around the formulas to use for size of binary tree. Depending on who I ask, what website, etc.
I see different similar answers.

So if someone could explain simply either: the differences between these formulas, the cases to use one or another, or any other explanation. It would be greatly appreciated.

**I've seen:**

* 2^h
* 2^(h+1)
* 2^(h+1) - 1

**And I've seen the reverse for calculating the height:**

* log(n)
* log(n+1)
* log(n+1) - 1

*assume base 2*

If someone could clear up my confusion that would be appreciated.
I'm an undergraduate at university, that needs to make sure my revision flashcards are correct! Thanks! :)

# Answer
First, let us start with some definitions:

* the size of a binary tree $T$, often denoted $|T|$, is the number of nodes. I believe it is what you called $n$ in your post. The size of a binary tree can be computed by induction using:

+ the size of the empty tree is $0$;
    + the size of a node $N(l, r)$ is $1 + |l| + |r|$.
* the height of a binary tree $T$, denoted $h(T)$, can have two definitions that I know of. However, both have the same induction relation for a non-empty tree, which is $h(N(l, r)) = 1 + \max(h(l), h(r))$. The difference comes from the convention for the empty tree.

+ the first one defines the height as the maximum length of a path from the root to a leaf. As such, the height of the empty tree is defined (by convention for convenience purposes) as $-1$, and the height of a tree with one node is $0$;
    + the second one defines the height as the maximum number of nodes in a path from the root to a leaf. As such, the height of the empty tree is $0$, and the height of a tree with one node is $1$.

I prefer to use the first definition, but this is a matter of personnal choice. After all, it only results in an offset of $1$.

Now for your formulas and reverse formulas, it is very unclear what you are trying to do. My guess is that you have seen some formulas that compare the height and the size of a binary tree. What can be proven is the following (using the first convention for height):

$$h(T) + 1 \leqslant |T| \leqslant 2^{h(T) + 1} - 1$$

The proof for this is a proof by induction using the previous induction relations for both the size and the height.

The previous inequalities can be tweaked a bit to obtain:

$$ \log\_2 (|T| + 1) - 1 \leqslant h(T) \leqslant |T| - 1$$

However, note that even though those inequalities can be equalities in some cases, this is not always the case.

When using the second convention for height, those formulas would become: $$h(T) \leqslant |T| \leqslant 2^{h(T)} - 1$$ and $$ \log\_2 (|T| + 1) \leqslant h(T) \leqslant |T|$$

However, when computing time complexities, like in AVL trees, only the asymptotics matter. For example, in AVL trees, $h(T) \in \mathcal{O}(\log |T|)$.
> 3 votes

# Answer
For $h=1$, all three formulas give different sizes, so it suffices to build a tree of height $1$ and count the nodes. If no formula gives the correct answer, question the definitions of $h$ and $n$.

---

The formula for the height is obtained by inversion. $n=f(h)\iff h=f^{-1}(n)$.
> 0 votes

# Answer
You need to define $h$ and $n$ first to use any of the formulas.

Consider $h$ starting from $0$, i.e. root is at height $0$.

$2^h$ gives the maximum number of nodes at given height $h$ and $2^{h+1}-1$ gives the maximum number of nodes in a complete binary tree of height $h$. And for the rest as you mentioned, take their inverses to get the height.
> 0 votes

---
Tags: algorithms, time-complexity, binary-trees
---


# Question
Title: Automata: Are there algorithms to judge whether two automata are isomorphic?
When I want to judge whether two regular forms represent the same language, I have learned the next method:

1. create the (non-deterministic) finite-state automata which accepts the language the given regular form represents for two regular forms respectively.
2. convert the two NFA into DFAs.
3. **Judge whether the two DFAs are isomorphic**.

However, I don't really know how to do 3.

Are there any algorithms to do 3? In more general, how to **judge whether two given graphs is isomorphism**. (If both graph is non-labeled, I think it is very difficult and I'm not sure how to do it.)

Thank you.

**Notation** There is already a question regarding algorithms to judege the equivalence of two automata and the method is different from above one. Although that way is much smarter, I am wondering whether it is possible to judge the equivalence of two automata in **the direction above**.

Thus, I want to just learn about the algorithms to judge whether two DFAs (or graphs) are isomorphic.
What I want to do is to distinguish automata by whether their shape, that is, **if two given automata is not isomorphic, then they should be regarded as "different", even if they accept the same language**.

# Answer
DFAs can be minimized. The minimal DFA for a regular language is unique up to isomorphism. So you can compare them by walking both transition graphs in parallel, in the same order, e.g. depth-first. As soon as you find a mismatch, the DFAs aren't isomorphic; once you've visited all states and transitions without any mismatch, they are isomorphic.
> 2 votes

# Answer
I don't think it's correct to look at the equivalence of **DFA's** as an isomorphism of their graph representation, as two **DFA's** accepting the same language may have **different** numbers of states(nodes), from graph point of view they will not be isomorphic but they happen to be equivalent as they accept the same language.

You could create a product automata accepting the language $L = L\_{1} \oplus L\_{2}$ using the given two DFA, here if $L$ is empty that means there exists no string that is present in $L\_{1}$ and not present in $L\_{2}$ and no string that is present in $L\_{2}$ and not present in $L\_{1}$, hence our languages will be equal.

Now we have a product DFA (directed graph) and we have to check if it's the language accepted by it is empty or not, this can be done by performing a DFS/BFS from the start state of our product DFA.

If no final state is reachable in our DFS/BFS from the start state ($L$ is empty) then the languages $L\_{1}$ and $L\_{2}$ are equal else if there is a final state reachable ($L$ is not empty) then the languages are not equal.
> 1 votes

---
Tags: automata, finite-automata, graph-isomorphism
---


# Question
Title: Does it make sense to apply path compression to kruskal algorithm?
I am reading about Kruskal and analysing it’s time complexity.

Let’s say there are E edges and V vertices. Kruskal algorithm has two important time complexity equations ,

1. Sort edges- Elog(E)
2. For whether edge from v1-\>v2 , apply find(v1) and find(v2). If cycle exist don’t connect. Other wise connect them. - E\*timecomplexity(find(v))

Now in the second step , time complexity of find(v) will be O(v) for skewed sets. We can improve it by using union by rank where we append small to talk in term a of height, O(log(v)).

Now my question is can we apply path compression here to further reduce find operation time complexity further to O(α(n)) (where α is the inverse of the Ackerman function). ? Wouldn’t path compression distort the graph itself as we will be re arranging the edges!!

So I believe best case for union and find Is -\> E(log(V))

I am thinking time complexity without path compression using union by rank is , O(ElogE)(sort) +O(Elogv)(find and union) that would be upperbound O(ElogE)

Am i right here ? Or we can use path compression here ??

# Answer
You can apply path compression, as the structure Union-Find does not change the structure of the graph at all (with or without path compression).

The structure is only there to check efficiently if two vertices are in the same connected component, but the "edges" in the tree representation of the structure union find are unrelated to the edges in the minimum spanning tree.

Though path compression is quite easy to implement and improve time complexity, as you have stated the overall time complexity does not change, because the first step (sorting edges) is the one that takes the longest time.

However, with further hypotheses on the weights, it could be possible to sort edges in linear time (using radix sort for example). In that case, path compression would decrease the overall time complexity.
> 3 votes

---
Tags: time-complexity, minimum-spanning-tree, union-find, disjoint-sets
---


# Question
Title: Create a binary search tree from a sorted array: Space complexity reasoning
Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'.

```
class TreeNode:
    def __init__(self, x):
        self.right = None
        self.left = None
        self.val = x

```

Here is the solution:

```
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        left = 0
        right = len(nums) - 1

        return Solution.recursive_insert(nums, left, right)

    @staticmethod
    def recursive_insert(nums, left, right):

        if left <= right:

            mid = (left + right)//2
            node = TreeNode(nums[mid])

            node.left = Solution.recursive_insert(nums, left, mid - 1)
            node.right = Solution.recursive_insert(nums, mid + 1, right)

            return node

example_insertion = Solution()
example_insertion.sortedArrayToBST([1, 2, 3, 4, 5, 6, 7, 8])

```

I understand proving the time complexity is $O(n)$ by using the following recurrence relation:

$$T(n) = 2T(n/2) + C$$

I have a question about the space complexity... Here is how I rationalize it. Please correct me if I'm wrong.

The code to insert the left and the right child involves simply performing a worst case binary search (until left becomes greater than right, or start becomes greater than end). The function call stack keeps getting re-used, but goes to a maximum of $O(\log n)$ (which happens to be the worst case space complexity of binary search when done recursively and not iteratively).

Is my reasoning correct?

# Answer
> 0 votes
I would say try to think about it more in the terms of data structures used directly in the calculation of the result. Typically you wouldn't consider the call stack because you could in theory rewrite you algorithm to be iterative and have no issues with the call stack. The call stack is only an issue when you reach the max recersion depth. It is also not considered when just analyzing algorithms.

Space complexity is constant or $O(1)$ because you can modify the tree in place.

Your answer about call stacks more so relates to the worst-case time complexity as this is directly related to number of function calls (or call stacks in your case). This is going to be $O(\text{height})$ of the tree which is at most $n$, so $O(n)$ in worst case, but $\Theta(\log(n))$ in average case. The time complexity can be improved to better than $O(n)$ if you keep your tree balanced after each insertion.

# Answer
> 0 votes
Besides the recursive calls, the function `recursive_insert` does not require local variables, hence no extra space.

The arguments are `nums`, `left`, `right`, and two situations could arise:

* the whole of `nums` is copied on every call, causing $n$ elements to be stored on the stack, for a total of $n\log n$ extra space.
* only a reference to `nums` is used, and the extra space is just proportional to $\log n$.

Note that, assuming that the copies cannot be avoided, the list need not be copied in full every time. On the opposite, every recursion level can do with the half of the previous and the total stack space requirement will be $\frac n2+\frac n4+\frac n8\sim n$.

---
Tags: algorithms, graphs, runtime-analysis, space-complexity
---


# Question
Title: Is there a CTL* formula that translates into mu-calculus formula Y.νZ.(...) with alternation depths 2,1 for Y,Z?
A CTL\* formula `EFG p` is equivalent to mu-calculus formula `Y.(<>Y | νZ.(<>Z & p))`. In this formula, the alternation depths are `ad(Y)=ad(Z)=1`. Is there a CTL\* formula that translates into `YνZ(...)` with alternation depths 2,1 for Y,Z?

And a similar question:
Is there a CTL\* formula that translates into `νXYνZ(...)` with alternation depths 3,2,1?

# Answer
> 0 votes
Answer: `Y.νZ.[](Y | pZ)`, which corresponds to CTL formula `AFAG p`.

**Long answer to 1st question**
For this answer I use the def of alternation depth taken from Handbook on Model Checking, Chapter 26. For instance, the formula `Y.(<>Y | νZ.(<>(Zp)))` has alternation depths ad(Y)=ad(Z)=1, so the AD of the formula is 1 as well. Note that this formula can also be written as `Y.νZ.<>(Y | Zp)` which has AD of 2. So the original question asks about the *minimal* possible depth.
Now consider a slightly different formula `Y.νZ.[](Y | Zp)` of AD=2. In contrast to the formula with `<>` operator, this formula cannot be rewritten into a formula of depth 1 (I believe so). Finally, this formula corresponds to the CTL\* formula `AXFG p`. This answers the original question.

Remark. I mistakenly thought that `Y.νZ.[](Y | pZ)` could be rewritten into a formula of AD=1 just like for `<>`, which prompted the question.

**Answer to 2nd question**
`νX.Y.νZ.[](sZ | Y | Xn)`, which corresponds to CTL\* formula `AX(GF!n -> GFs)`.

---
Tags: computation-tree-logic, mu-calculus
---


# Question
Title: Algorithm to select a random bit string with constraints
# Problem Description

Given $a, b, n \in \mathbb{N}$ with $a \< b \< n$.

Let $M$ be the set of all possible bit strings of length $n$ which begin and end with one and have at least $a$ and at most $b$ zeros between every pair of successive ones: $$ AZ\_s(x, y) :\equiv s\_{x} = s\_{x+1} = \ldots = s\_{y} = 0 \\ M := \left\\{s \in \\{0,1\\}^n \mid s\_1 = s\_n = 1 \land \\ \forall i \in \\{1, 2, \ldots n-1\\}: s\_i = 1 \Rightarrow AZ\_s(i+1, \min\\{i+a, n\\}) \land \lnot AZ\_s(i+1, \min\\{i+b, n\\}) \right\\} $$ For example, with $a=1, b=3, n=8$, the set of possible bit strings is $M = \\{10001001, 10010001, 10010101, 10100101, 10101001\\}$.

I need a fast algorithm which gets $a$, $b$ and $n$, and returns one random element of $M$ with uniform probability.

Here $a$ and $b$ are small constants and "fast" refers to the asymptotic time with respect to $n$. If possible, the algorithm's execution time should be polynomial in $n$ and not probabilistic.

There may be existing solutions for my problem but I don't know what I would need to search for to find them. Suggestions and links are welcome.

# My Solution Approaches

I've thought about ways to solve the problem but couldn't find a solution which fulfils all criteria yet.

## Greedy Probabilistic Algorithm

This algorithm repeatedly appends zeros followed by a one to the bit string $s$ until the length of $s$ is $n$ or longer. If $s$ is too long, it truncates $s$ at the beginning and then goes back to the appending phase. A result is found once $s$ has length $n$.

Let $|s|$ denote the current length of the bit string.

1. Initialise the bit string to $s = 1$
2. Select $k$ randomly from $\\{a, a+1, \ldots, b\\}$ and append $k$ zeros followed by a one to $s$
3. If $|s| \< n$, goto 2
4. If $|s| = n$, return $s$
5. Remove the prefix `^10*` (a one followed by one or more zeros) from $s$
6. goto 3

I doubt (but haven't proven) that this algorithm selects each element from $M$ with the same probability. Perhaps it is possible to modify this algorithm to fulfil this criteria; for example it could skip step 4 with a probability which depends on the current number of ones in $s$.

## Enumeration

With an ordering of the elements of $M$, each $s \in M$ can be bijectively associated with a number in $\\{1, 2, \ldots, |M|\\}$. It may be possible to create an algorithm which selects such a number randomly and returns the corresponding bit string.

Consider the example from above: $a=1, b=3, n=8$, $M = \\{10001001, 10010001, 10010101, 10100101, 10101001\\}$.

* Partition $M$ into $M\_k$ such that $M\_k$ contains all bit strings with $k$ ones. Here: $M\_3 = \\{10001001, 10010001\\}, M\_4 = \\{10010101, 10100101, 10101001\\}$
* Partition $M\_k$ into $M\_{k,G}$ such that $G$ is a multiset which contains the lengths of consecutive zeros. Here: $M\_{3, \\{2,3\\}} = \\{10001001, 10010001\\}, M\_{4, \\{1,1,2\\}} = \\{10010101, 10100101, 10101001\\}$. Note that in general there can be multiple $G$ for one $k$; for example $Y\_3 = \\{1001001, 1010001, 1000101\\} \Rightarrow Y\_{3,\\{2,2\\}} = \\{1001001\\}, Y\_{3,\\{1,3\\}} = \\{1010001, 1000101\\}$.
* $|M\_{k,G}|$ is the number of tuples which map to $G$ if the order of their elements is ignored.

Omitting the details, an algorithm could do following:

1. Calculate $|M|$ and select $x \in \\{1, 2, \ldots, |M|\\}$ with uniform probability
2. Find $k$ such that $\sum\_{i\<k} |M\_i| \< x \leq \sum\_{i \leq k} |M\_i|$ and set $x\_k := x - \sum\_{i\<k} |M\_i|$
3. Similarly to step 2, find $G$ and calculate $x\_{k,G}$. This requires an ordering of the sets $M\_{k,G}$ with respect to $G$.
4. Return the $x\_{k,G}$-th element of $M\_{k,G}$, which is the $x$-th element of $M$. This requires an ordering of the elements in $M\_{k,G}$.

I haven't found a fast version of this algorithm yet; for example, I don't know how to calculate $|M|$ in constant time.

## Graph Colouring

It could be possible to create a graph where each $s\_i$ is represented by a node and the edges represent the constraints for the bit string $s \in M$. The edges would be set such that there is a bijective mapping between the valid colourings of this graph and $M$. For example, due to the edges, the nodes corresponding to $s\_1$ and $s\_n$ must always have the same colour in any colouring. The graph can have more than $n$ nodes.

An algorithm which returns one of all possible colourings with uniform probability would solve the problem but I think that this algorithm would be slow.

## Additional Algorithms Mentioned for Completeness

### Brute-Force Probabilistic Algorithm

It should be possible to repeatedly select a random $s \in \\{0,1\\}^n$ until $s \in M$ holds. However, for big $n$, $M$ is very large and the success probability is low, so this algorithm would be too slow.

### Explicit Calculation of $M$

It should be possible to calculate all possible elements of $M$ explicitly and then return one of them randomly. However, for large $M$, this simple algorithm is too slow.

# Answer
> 2 votes
I think this can be done using a bit of dynamic programming. First, let us try to solve a different problem, which is computing $|M|$ given $n$, $a$ and $b$.

Denote $f(n, a, b)$ this number. Note that a string in $M$ is composed of a $1$, followed by a sequence of substrings of the form $0^k1$, with $k\in \\{a, a+1, …, b\\}$. Using that fact, considering the length of the last substring, we conclude that for $n\>1$:

$$f(n, a, b) = \sum\limits\_{k=a}^bf(n - k - 1, a, b)$$

The base cases are $f(1, a, b) = 1$ (only one string of length $1$) and $f(n, a,b) = 0$ if $n\<0$.

Since we can assume $0 \leqslant a \leqslant b \leqslant n$ without loss of generality, this gives a $\mathcal{O}(n^2)$ algorithm to compute $f(n, a, b)$.

Now back to the random selection. In the same way as previously, we will create the string backward:

* if $n = 1$, return $1$;
* otherwise, pick $k\in \\{a, a+1, …, b\\}$ with probability $\frac{f(n-k-1, a, b)}{f(n, a, b)}$ and return recursively a random string of length $n-k-1$ followed by $0^k1$.

With memoisation of the computation of $f(n, a, b)$, this algorithm is also in $\mathcal{O}(n^2)$.

---
Tags: algorithms, probability-theory, randomized-algorithms, probabilistic-algorithms
---


# Question
Title: Largest isomorphic subgraphs of two graphs with features
the following question came up in a problem I am working on:

Suppose you have two graphs $G\_1=(V\_1, E\_1), G\_2=(V\_2,E\_2)$ that have features attached to them, i.e. to every $v\in V\_1$ or $v\in V\_2$ there is a vector $w\_v\in\mathbb R^n$ with fixed $n$ of features mapped to, and similarly for all edges. We call two of these graphs isomorphic, if there exists a bijective function $f: V\_1\to V\_2$, such that $$uv\in E\_1\Leftrightarrow f(u)f(v)\in E\_2,$$ $$w\_u=w\_{f(u)}\text{ and}$$ $$w\_{uv}=w\_{f(u)f(v)}$$ for all $u,v\in V\_1$.

Given such two graphs, what would be the best way to get the *maximal isomorphic subgraphs*, i.e. a subgraph of $G\_1$ induced by a set of vertices $U\_1$, such that there exists an injective $f:U\_1\to V\_2$ like above (with $E\_1, E\_2$ replaced by the appropriate induced edge sets) that has a maximal amount of vertices.

Thanks in advance!

# Answer
This looks like it is at least as hard as the induced subgraph isomorphism problem. Suppose that all $w$ vectors are 0. Then your question is identical to asking whether for a maximal induced subgraph of $G\_1$ that is isomorphic to an induced subgraph of $G\_1$. The solution to your problem will be all of $G\_1$ iff $G\_1$ is isomorphic to an induced subgraph of $G\_2$.

Consequently, your problem is NP-hard, since it is at least as hard as a problem known to be NP-hard.

Your problem can be viewed as working with colored graphs. Typically, on practical instances, the colorings only make the problem easier, but from worst-complexity, the problem remains NP-hard.

If this is something you need to solve in a practical setting, one plausible approach is to formulate this as an instance of SAT and solve with an off-the-shelf SAT solver. It appears that the Glasgow Subgraph Solver supports induced subgraph isomorphism; I don't know whether it supports the colored version. You could also look at algorithms for subgraph isomorphism, such as these, to see if they can be extended to support induced subgraph isomorphism.
> 2 votes

---
Tags: graphs, graph-isomorphism, features, subgraphs
---


# Question
Title: Practicability of enumerating all Turing machines with fewer than $s$ states to find a potential polynomial-time algorithm for subset-sum?
It is known that the $\mathbf{P}\overset{?}{=}\mathbf{NP}$ problem is equivalent to asking whether there exists a polynomial-time Turing machine that decides an $\mathbf{NP}$-complete problem. Let's say this problem is subset-sum. Now I'm considering enumerating all the Turing machines with fewer than $s$ states. Since the number of states are limited, the number of Turing machines we need to enumerate are limited. I want to select the Turing machine that decides the subset-sum problem in the fewest steps. By Rice's theorem, it is impossible to decide whether a Turing machine correctly solves the subset-sum problem, but we can design some test cases, feed them to the Turing machines and simulate their execution on these inputs. Those who pass all the tests are likely to successfully decide the problem. We can then manually check the correctness of the machines which consume the least steps. Another issue here is that a Turing machine may not halt, but we can set a step limit for each test case and terminate the execution of a machine if it has consumed all the available steps. If $\mathbf{P}=\mathbf{NP}$, the best machine we found may decide the subset-sum problem in polynomial time. If $\mathbf{P}\ne\mathbf{NP}$, it is still possible for us to find a machine that solves the subset-sum problem faster than any methods we've already known.

My questions are:

1. Are there any loopholes in my idea?
2. Is it practical to implement my idea (or an improved version of my idea)?

Note:

1. We may not necessarily choose Turing machines as the computing model. We can also use $\lambda$-calculus and enumerate functions which consist of fewer than $s$ elementary functions, using $\beta$-reduction to assess time complexity.
2. We assume that we can "understand" a Turing machine and if it provides a correct solution to the subset-sum problem, we can prove its correctness.

# Answer
> 1 votes
There are a lot of Turing machines, so no, this idea is completely unpractical (I don't think there is really a loophole, since you are considering many restrictions). For example, there are roughly $10^{140}$ machines with an alphabet of $5$ letters and $10$ states. Try to write a Turing machine that implement quicksort, and you will see that $10$ states is a very small number.

You could consider that this is the same reason we are not trying to prove the Riemann conjecture by enumerating all possible proofs and checking which are true.

---
Tags: turing-machines, np-complete, np
---


# Question
Title: Independent set problem for graphs with very large independent sets
Is there a number $\alpha \< 1$ such that the independent set problem is polynomial for input graphs whose independence number is at least $\alpha n$ (where $n$ is the number of vertices)?

# Answer
There is no such $\alpha$ unless $\mathsf{P}= \mathsf{NP}$. Assuming such an $\alpha$ exists, you could solve the problem Independent Set for any graph in polynomial time.

Indeed, suppose $G = (V, E)$ a graph and $n = |V|$ ($V = \\{1, 2, …, n\\}$). Consider $N = \left\lceil \frac{n}{1-\alpha}\right\rceil$, $K = N - n$ and $G' = (V', E')$ with:

* $V' = V\cup \\{n+1, n+2, …, n + K\\}$;
* $E' = E$.

Meaning you add a certain number of isolated vertices. It is clear that the independence number of $G'$ is the independence number of $G$ plus $K$. However, $K = N - n \geqslant N - (1-\alpha)n = \alpha N = \alpha |V'|$. Given that the size of $G'$ is polynomial in the size of $G$, if you can compute the independence number of $G'$ in polynomial time, you can do it for $G$.
> 2 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Proving that non-regular languages are closed under concatenation
How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\\{a^nb^n|n\ge1\\}$ ?

# Answer
> 8 votes
You can't prove it because it isn't true: the class of non-regular languages isn't closed under concatenation.

Let $X\subseteq \mathbb{N}$ be any undecidable set containing $1$ and every even number. For example, take your favourite undecidable set $S$ and let $$X = \\{0, 2, 4, \dots\\} \cup \\{1\\} \cup \\{2i+1\mid i\in S\\}\\,.$$ The language $\mathcal{L} = \\{a^i\mid i\in X\\}$ is undecidable, so it certainly isn't regular. But $$\mathcal{L}\cdot\mathcal{L} = \\{a^{i+j}\mid i,j\in X\\} = \\{a^i\mid i\in\mathbb{N}\\}\\,,$$ is regular.

# Answer
> 1 votes
Here is another example showing that the claim is false. Let $L$ be any non-regular language over $\\{0,1\\}$, and take $$ L\_0 = \\{ 0 w : w \in L \\} \cup \\{ 1 w : w \in \\{0,1\\}^\* \\} \cup \\{\epsilon\\}, \\ L\_1 = \\{ 1 w : w \in L \\} \cup \\{ 0 w : w \in \\{0,1\\}^\* \\} \cup \\{\epsilon\\}. $$ You can check that $L\_0,L\_1$ are not regular, but $L\_0L\_1 = \\{0,1\\}^\*$ is regular.

---

Another nice example uses Lagrange's four square theorem, which states that every non-negative integer is a sum of four squares. Define $L\_1 = \\{1^{n^2} : n \geq 0\\}$, $L\_2 = L\_1^2$ and $L\_4 = L\_2^2$. The four square theorem shows that $L\_4 = 1^\*$ is regular. Conversely, the pumping lemma shows that $L\_1$ is not regular. Hence either $L\_2$ is regular, in which case $L\_4 = L\_2^2$ is a counterexample to the claim, or $L\_2$ is not regular, in which case $L\_2 = L\_1^2$ is a counterexample to the claim. (In fact, $L\_2$ is not regular.)

---

Yet another example assumes the Goldbach conjecture: every even integer larger than 4 is the sum of two odd primes. Let $L = \\{ 1^p : \text{$p$ is an odd prime } \\}$. Using the pumping lemma it is not hard to show that $L$ isn't regular. Assuming the Goldbach conjecture, $L^2 = \\{ (11)^n : n \geq 3 \\}$, which is regular.

# Answer
> 1 votes
Concatenation of two non-regular languages may be regular.

Constructive Proof:

Let $L$ be any non-regular language. Now, we know $L’$ is also non-regular.

Consider $(L \cup \\{ \epsilon \\})$$(L’ \cup \\{ \epsilon \\})$, both of which are non-regular.

Now, $(L \cup \\{ \epsilon \\}).(L’ \cup \\{ \epsilon \\}) = \Sigma^\*$, which is regular.

For concrete example:

Consider $L =$ Set of All Prime Numbers over $\\{ 0 \\}$

$M =$ Set of All Composite Numbers over $\\{ 0 \\}$

Both $L,M$ are Non-regular.

Now, $L.M = \\{ 0^n , n \geq 6 \\}$ which is regular.

---
Tags: formal-languages, closure-properties
---


# Question
Title: Does superpolynomial lower bounds of a problem in $NP$ mean that $P \neq NP$?
If one proves that the lower bounds of an $NP$ problem, are not bounded by any polynomial, is this enough to prove that $P$ does not equal $NP$?

# Answer
> 1 votes
Yes, if you prove a super-polynomial lower bound on time needed to decide a problem $\Pi \in \mathsf{NP}$, then this means that $\Pi \not\in \mathsf{P}$. Since $\Pi \in \mathsf{NP} \setminus\mathsf{P}$, the set $\mathsf{NP} \setminus\mathsf{P}$ cannot be empty, i.e., $\mathsf{P} \subset \mathsf{NP}$.

# Answer
> 1 votes
Yes. Unfortunately *proving* even a worse than linear lower bound is very often very difficult.

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Distributing cards randomly given constraints
We want to distribute 3\*n known cards among 3 players evenly given a set of constraints that prohibits some players from having certain suits.

For example: We want to distribute 1H, 2H, 3S, 4S, 5D, 6D (second letter refers to suit of card) among three players A, B, C such that A does not get any card of suit Hearts.

Is there an efficient algorithm that gives a random valid distribution given the constraints?

I have tried successively assigning each player a random card and checking if the constraints are satisfied for that player. If they are not satisfied, we save the chosen card for later and try again with a random card. This does not work in cases when we have only one card left to assign and we are forced to deal that card to a player that cannot have the card of that suit. Trying to satisfy the constraints from this condition by making random swaps with other cards can still not be enough to guarantee all card assignments follow the constraints.

What is the most efficient way to do this?

Edit: Clarifying the constraints

The known cards are a subset of standard deck of cards. Each constraint is in the form of player X cannot have cards of suit Y.

Edit #2: There exists at least one way to distribute cards satisfying all the constraints

# Answer
> 1 votes
Consider $X = \[x\_1, x\_2, …, x\_{3n}\]$ the sequence of cards. For $i \in \\{1, …, 3n\\}$, denote $s(i)\subseteq \\{A, B, C\\}$ the set of players allowed to get card $x\_i$. For $i\in \\{1, …, 3n\\}$ and $a, b, c\in \\{1, …, n\\}$, denote $f(i, a, b, c)$ the number of possibilities to distribute cards $1, …, i$ among $A$, $B$ and $C$, assuming that they can only receive respectively $a$, $b$ and $c$ cards.

Considering the possibilities to give card $i$, we get: $$f(i, a, b, c) = \_{A\in s(i)}f(i-1, a-1, b, c) + \_{B\in s(i)}f(i-1, a, b-1, c) + \_{C\in s(i)}f(i-1, a, b, c-1)$$ where $\_{A\in s(i)}$ is equal to $1$ if $A\in s(i)$ and $0$ otherwise (and same for $B$ and $C$).

The base cases are:

* $f(i, a, b, c) = 0$ if $a\< 0$ or $b\<0$ or $c\< 0$;
* $f(0, 0, 0, 0) = 1$.

This gives the idea of a $\mathcal{O}(n^4)$ (actually $\mathcal{O}(n^3)$ because $a+b+c =i$) dynamic programming algorithm to compute the number of possibilities to distribute all $3n$ cards to $A$, $B$ and $C$: this is $f(3n, n, n, n)$. Since you consider a standard card set, the complexity is not a problem.

Now to create a random distribution, you can use the values previously computed:

* set $a, b, c = n$
* for $i =3n$ down to $1$:
    + give card $x\_i$ to player $A$ with probability $\dfrac{\_{A\in s(i)}f(i-1, a-1, b, c)}{f(i, a, b, c)}$ and decrease $a$ by one;
    + same thing for other players (those are disjoints events, so that a card can only be given to one player).

---
Tags: probability-theory, board-games
---


# Question
Title: Build a context-free grammar for the language
Build a context-free grammar for the language:

> $L=\\{\\#x\\#y\\#\\,\\,;\\,\\,|x|=|y|\\,\\,\wedge\\,\\,x,y\in\\{0,1\\}^{\*}\\}$ over $\sum=\\{0,1,\\#\\}$

How can I make sure that |x|=|y|?

# Answer
Without giving you all the answer, consider using the following rules (to be completed):

> $X \to AXA$
>
> $A \to 0 \mid 1$
> 1 votes

---
Tags: formal-languages, context-free
---


# Question
Title: Build a context-free grammar for the language
Build a context-free grammar for the the complementary language of:

> $L=\\{ww^{R}\\,\\,|\\,\\,w\in\\{0,1\\}^{\*}\\}$

I think $L^C$ is the set of all strings that are not palindromes,

but I don't know how to start building the grammar.

**Attempt:**

> S→ A | B
>
> A→ AAA | 0 | 1
>
> B→ 0C1 | 1C0 | 0B0 | 1B1
>
> C→ 00C | 01C | 10C | 11C | ε

# Answer
A word in $L^C$ is either a word of odd length or a word $uv$ with $|u| = |v|$ and $v \neq u^R$:

$$L^C = L\_1 \cup L\_2$$

with $L\_1 = (\Sigma\Sigma)^\*\Sigma$ and $L\_2 = \\{uv\mid |u| = |v| \text{ and }v\neq u^R\\}$.

It should be easy for you to find a CFG for $L\_1$. As for $L\_2$, note that if $u=u\_1…u\_n$ and $v = v\_1…v\_n$, then $uv\in L^C$ if and only if there exists $i\in\\{1, …, n\\}$ such that $u\_i = 0$ and $v\_{n+1-i} = 1$ (or $1$ and $0$). You should be able to find a CFG for $L\_2$ from that.
> 1 votes

---
Tags: formal-languages, context-free
---


# Question
Title: Upper limit of instructions of a program for a Turing machine that has been converted from a real programming language
Imagine that I have an algorithm written in C that is of, let's say, 10,000 characters in length. Such a program can be simulated on a turing machine (Wikipedia: Anything a real computer can compute, a Turing machine can also compute. For example: "A Turing machine can simulate any type of subroutine found in programming languages, including recursive procedures and any of the known parameter-passing mechanisms"). Intuitively it seems obvious that there exists such a program among all programs for a Turing machine of at most $10^{10^{100}}$ (googolplex) instructions. How can I go about proving the last sentence?

# Answer
You could write a Turing machine that implements a C interpreter, and is less than a googolplex instructions long.

Of course you probably wouldn't want to actually do that, as that would be far too tedious and painful. So, for example, perhaps you instead might write a Turing machine that can evaluate any boolean circuit; then write a boolean circuit that implements a 8086 microprocessor, and hardcode it with the Turing machine; then write an assembler and C compiler for 8086, and hardcode it. If all of that, plus the C program itself, fits in less than a googolplex instructions, then you have built up a way to implement your C program (very very slowly) using a Turing machine.
> 1 votes

---
Tags: turing-machines, c
---


# Question
Title: Efficient comparison whether set of values is between min-max filters
I'm trying to optimize a practical problem in a database query. Suppose we have a db table`Products` and each product has a few numeric properties. I save the properties values in a different table `ProductProperty` table because the user can add more property types. The user wants to look for products using range filters for each property.

For example if the product has five property types with values `{20, 30, 25, 50, 40}` and the user searches products with values for each property in ranges `{10-35, 20-50, 30-60, 0-100, 10-80}` that product is excluded from results because the third value 25 is not between 30 and 60. The database query for this is not very efficient, it has to go for each product, join `ProductProperty` table, iterate and check every value if it's inside the range.

What I was thinking is to encode the product values `{20, 30, 25, 50, 40}` possibly to some string (I don't think it can fit in any numeric data type) and save them in a column in `Products`, `EncodedValues`.

So my query could then be a simple string comparison

```
select * from products p
where minEncodedValues <= p.encodedValues AND p.encodedValues <= maxEncodedValues

```

I'm wondering if there could be some transformation of numeric values into a string so `s1<s2` returns `false` if not all values `v1` are less than the corresponding values of `v2`.

# Answer
Databases are not a silver bullet for every problem under the sun. You are asking how to answer multi-dimensional range searches efficiently. Rather than trying to contort your data into a form which lets you solve this with a standard database (a problem for which you probably won't find a good solution), instead, I recommend you look for a data structure that is well-suited to this specific type of query.

In particular, you want a solution to orthogonal range searching. There are standard data structures for this problem. I expect you will find that, for your specific situation, with orthogonal range queries over a 5-dimensional space, those sophisticated data structures are a bit faster if you are doing an enormous number of queries, but the savings aren't worth it, and it's simpler to simply do a linear scan over all data items: check each data item and see which satisfies the filter.

As far as I can see, nothing forces you to split data across two tables in the form that you mention, so if that makes your data processing workload slow, I recommend a different data format.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How do i delete one single unequal element from an array of equal elements without using hashing?
The rules of the question state that:

> 0. Only one element is different.
> 1. Rest are all same.
> 2. Array A size is 8.
> 3. I need to find the different element and remove it (Hashing cannot be used).

I have not developed the code but I have come up with an algorithm.
There will be two cases one where the different element value is less and other where it has greater value.
Suppose I take case 2, here I compare the sum of 1st 3 elements and the next 3 elements. If both are same, compare A\[6\] and A\[7\]. If both are different, suppose 1st 3 elements has greater sum, then compare A\[0\] and A\[1\], if they are the same, A\[3\] is the unequal element, otherwise either A\[0\] or A\[1\] is greater, according to their value.

Now my question is what if the array size is $N$\>8, what will be the algorithm or code for that?

# Answer
* Compare the first two elements (1 comparison.)
* If they are equal, find the different element among the remaining ones ($n-2$ comparisons).
* If they are different, compare the third element to the first ($1$ comparison). If they differ, the different element is the first; otherwise the second.

So you conclude in either $n-1$ comparisons (with probability $1-\frac2n$) or in $2$ (with probability $\frac2n$). The expectation is $n-3+\frac6n$, assuming the locations to be equiprobable.

---

**Based on Nathaniel's comment, there is a better way:**

* find the first pair of distinct elements (at most $m:=\lfloor\frac n2\rfloor$ comparisons);
* conclude with an extra comparison.

More precisely,

* when you found an heterogeneous pair, perform a majority vote with a value from another pair.
* if $n$ is even, you only need to process the first $m-1$ pairs (if they are all homogeneous, the last one is not). Worst case $m = \frac n2$ comparisons; expected case $\frac{1+2+...m-1}m+1 = \frac n4+\frac 12$ comparisons.
* if $n$ is odd, you need to process m pairs; if none is heterogenous, the different element is the last one. Worst case $m+1 = \frac{n+3}2$ comparisons; expected case $\frac{(n-1)(\frac{1+2+...m}m+1)+m}n = \frac n4 +\frac32-\frac 7{4n}$ comparisons.

Note that in the worst case it is impossible to beat $m$ comparisons as you must read all values before you can conclude.
> 1 votes

# Answer
Assuming n \>= 3. You have n-1 values x, and one value y.

To determine x, compare any two elements a and b. If they are equal then x=a. Otherwise compare a with a third element c. If a=c then x=a, else x=b.

Now you know x, walk through the array until you find the element ≠ x, and that is what you remove.
> 0 votes

# Answer
There are many ways to approach this problem, you could:

1. sort the list and then drop the first or last element based on which one isn't equal to a third item in the list (with index 1 ... n-2, where n is the size of the list)
2. you could have two pointers, one at the beginning (p1) and one at the end of the list (p2). p1 moves to the right (towards the end of the list) and p2 moves to the left (towards the beginning of the list) and as they move you capture the cumulative sums (s1 and s2) and stop when s1 != s2, and where the pointers stop then one of these items will be the unequal element. \[Note this has an edge case where you have an odd sized list with the unequal element in the middle so code for that\]
3. you can check if the first three items and see if any of them are not equal. If so, then you found the unequal element. If not, you have the equal element and so you can keep randomly picking from the list until you find the unequal element.

There are a lot of ways to solve this problem with varying complexities.
> 0 votes

---
Tags: algorithms, arrays, hash, hash-tables, maximum-subarray
---


# Question
Title: Finding the time complexity of a prime factorization algorithm
In this question, I'm going to introduce a prime factorization algorithm which I'm working on as my personal project.

I may attach a Python code to introduce the algorithm. If it contravenes the rule please let me know, I will consider it editing as a pseudo-code or substitute it with some link.

```
import timeit
import gmpy2
import math

A = gmpy2.mpz(11111111111)
# Input a positive integer to factor.
# Put it inside the parentheses as "A = gmpy2.mpz(....)"

def factor(A):
    B = gmpy2.mpz(math.sqrt(2 * A + 0.25) - 1)
    D = gmpy2.mpz(A - (B * B + B) / 2)
    while (D > 0):
        B += 1
        D = gmpy2.mpz(A - (B * B + B) / 2)
    n = gmpy2.mpz(0)
    while (D != 0 and B <= A):
        if (D > 0):
            B += 1
            D -= B
        else:
            n += 1
            D += n
    if B > A:
        return output(0, 0, 0)
    else:
        if (B - n) % 2 == 0:
            E = gmpy2.mpz((B - n) / 2)
            F = gmpy2.mpz(B + n + 1)
        else:
            E = gmpy2.mpz(B - n)
            F = gmpy2.mpz((B + n + 1) / 2)
        return output(A, E, F)

def output(A, E, F):
    if A == 0:
        print(f"Initial Value Error: Reset the B value")
    else:
        if A % E != 0 or A % F != 0 or A != E * F:
            print(f"[Error Occurred]  {A}  !=  {E}  *  {F}")
        else:
            print(f"{A}  =  {E}  *  {F}")
    return 0

if __name__ == '__main__':
    if A >= 2:
        timer_start = timeit.default_timer()
        factor(A)
        timer_stop = timeit.default_timer()
        running_time = round(timer_stop - timer_start, 6)
        print("running time: ", running_time, " seconds")
    else:
        print("undefined for A<2")

```

As I said, the code is a part of the personal project which I'm working on. So the theoretical explanation of the code can't be introduced in detail as of now. However, I may try to summarize the overview of the theory behind as follows.

Any positive integer $A$ can be represented as $A = a \times b$. When we think about $a \times b$, where $b \neq 1$, we can notice that it can be alternatively represented as $$ A = \cdots (a-2) + (a-1) + a + (a+1) + (a+2) +\cdots $$ when A is odd $$ A = \cdots (a-2) + (a-1) + (a+1) + (a+2) \cdots $$ when A is even.

The mechanism of this algorithm aims to find the value of $B$ and $n$ of the following equation \begin{equation} A - \frac{B^2+B}{2} + \frac{n^2+n}{2} = D \tag{1}\end{equation} for when $D=0$.

If we manipulate the equations by subtracting and adding summation of positive integers

$$\begin{aligned} A - \frac{B^2+B}{2} + \frac{n^2+n}{2} &= \[\cdots (a-2) + (a-1) + a + (a+1) + (a+2) +\cdots\] \\\&\hspace{7mm}- \[u + (u+1) + (u+2) \cdots\] + \[1 + 2 + 3 \cdots + n\] \\\&= 0 \end{aligned}$$

we can observe a property as follows $$ A = \frac{(B-n)(B+n+1)}{2} $$

Among the numerous cases of $ A = a \times b$, only $A \in $ {prime number} $\bigcup$ {perfect power of 2} are represented as $A = 1 \times A$. The reason for a prime number being represented as $A = 1 \times A$ is obvious. The reason for the case when $A$ is a perfect power of 2, $2^e$ can be represented only as a multiplication between powers of 2, which are all even, unless $2^e = 1 \times 2^e$.

The procedure of algorithm repeats the addition and subtraction of positive integers which let the value of D (the RHS of equation (1)) to oscillate between 0, until it reaches 0. So the longest expected computation time for the algorithm of $A$ is the case when $A$ is represented as $$A = \frac{\[A-(A-1)\]\[A+(A-1)+1\]}{2}$$ or $$A = \frac{\[(\frac{A-1}{2}+1)-(\frac{A-1}{2}-1)\]\[(\frac{A-1}{2}+1)+(\frac{A-1}{2}-1)+1\]}{2}$$

The fact that $2^e$ can be only represented as $2^e = 1 \times 2^e$, particularly as $$2^e = \frac{\[2^e - (2^e-1)\]\[2^e + (2^e - 1)+1\]}{2}$$ gives us a good tool to assume the time complexity.

In my numerical experiments, the computation time for $2^e$ doubles every time as $e$ gets larger by 1. Furthermore, I've observed that the computation time of every other $A$'s of which $A \< 2^e$ are less than the computation time of $2^e$.

By this observation, I'm assuming that the time complexity of this algorithm is not bad, somewhat, no more than sub-exponential time. However, I'm not an expert nor experienced with evaluating the time complexity of algorithms. If I observe some profiles and answers from some named users, I see that there are lots of experts who have experiences in those fields. So I'm here to ask for some advice.

Any kind of advice or opinion would be grateful. Looking forward to an honest opinion via comments and answers. Thank you.

**\[Edit\]**

I wanted to engage on discussion as much as I can. However, because of some unfriendly behavior which I encountered at the comment section of here, I concluded that Stackexchange community might not be the right place to bring up a post like mine.

I also respect all the points made by moderator. Still, I may not endeavor to delete this post by myself since some number of people have already encountered it. So just leaving the post as it was, I may not engage on further discussion unless definitely required.

You may feel free to test and modify this code without noticing me.

# Answer
I didn't read the details of how your code functions, so I won't comment on your algorithm. However, the code itself seems to have a time complexity of `O(sqrt(A))`. As A becomes very large, B approaches `sqrt(2A)`, making D approach `-sqrt(2A)`. Then, your second `while` loop seems to have a time complexity of `O(B)`, as the statement `n <= B+1` must always be true in your code, and `n` is incremented with a constant step up to `B`. However, if your code reaches the point where `n = B`, then your code will continually add or subtract `1` every two iterations (depending on the starting values of B and D) from `D` until `D == 0`, adding `O(|D|)` to the complexity. Thus, your algorithm in total has a complexity of around `O(B)+O(|D|)`, which can be simplified to `O(sqrt(A))`. So, your algorithm has similar runtime complexity to a classic brute-force algorithm looping from `1` to `sqrt(A)`, although the constant factor may vary greatly (I don't think I'm qualified to state which algorithm has a better constant factor in the worst case).

Disclaimer: I am not an expert in CS research, I'm a competitive programmer, and thus I only know how to make basic estimates of runtime.

Hope this helps somewhat. Good luck with your project!
> 1 votes

# Answer
I’d suggest running your algorithm and comparing its runtime to the trivial trial division algorithm. (Try dividing by 2, 3, followed by 6K-1 and 6K+1 until the square of the divisor exceeds the remaining number).

Try especially the behaviour for products of two or three large primes or for primes or numbers like 2^30 with many factors.

PS it looks very similar to the Fermat algorithm, which is quite fast for factors close to sqrt(a) but awfully bad if you have one tiny and one large factor. So try this fror a 12 digit prime multiplied by 3, 5 or 7.
> 0 votes

---
Tags: algorithms, complexity-theory, time-complexity, integers, factoring
---


title: Safety VS. Liveliness Property

text:
# Question
Title: Safety VS. Liveliness Property
I have to prove whether a certain property is safety or liveliness. The property represents the absence of deadlock so I expected it to be a safety property from what I read online.

The issue is that I seem to show that it is both, but this is impossible as the only property that is both safety and liveliness would be $\left(2^{\Xi}\right)^{\omega}$, where $\Xi$ is the set of propositional symbols. I would like to understand where the mistake is, and naturally if any of the solutions would be correct. Also, I would like to do it in a formal way instead of using the "something bad never happens" intuitive idea.

The property in question is: $$ \mathsf{G}((P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))) $$

1. The definition I have for safety property goes as follows:

> An LT property $P\_{safe}$ over $\Xi$ is called a safety property if for all words $\sigma \in\left(2^{\Xi}\right)^{\omega} \setminus P\_{safe}$ there exists a finite prefix $\hat\sigma$ of $\sigma$ such that $$P\_{safe} \cap \\{\sigma^\prime\in \left(2^{\Xi}\right)^{\omega}\\; |\\; \hat\sigma \textrm{ is a finite prefix of }\sigma^\prime \\} = \emptyset $$

What I tried to do is as follows:

Let $\sigma\in \left(2^{\Xi} \right)^{\omega}$ be an arbitrary word such that $\sigma\not \Vdash \mathsf{G}((P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))) $, then there exists $i\geq 0$ such that $\sigma, i\\,\not \Vdash (P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C)) $. Let $\hat\sigma=\sigma\[..i\]$, this is a bad prefix of $\sigma$, and for any word $\sigma^\prime\in \left(2^{\Xi} \right)^{\omega}$ such that $\hat\sigma$ is a prefix of $\sigma^\prime$, we have that $\sigma^\prime,i \not \Vdash(P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))$, thus: $\sigma^\prime\not \Vdash \mathsf{G}((P1E \wedge P2E) \rightarrow (\mathsf{F}\\, ( P1C \vee P2C))) $. We conclude it is a **safety property**.

2. The definition I have for liveliness property goes as follows:

> An LT property $P\_{live}$ over $\Xi$ is called a liveness property if $pref(P\_{live}) = \left(2^{\Xi} \right)^{\*}$.

So, I can't see why I can't prove it is a liveliness property as:

Take $\hat\sigma\in\left(2^{\Xi} \right)^{\*}$ of length $n+1$, $\hat\sigma=v\_0...v\_n$, let $\sigma=\hat\sigma.P1C.\varnothing^{\omega}$ .

For all $i\> n$, we have that $\sigma,i \not \Vdash P1E \wedge P2E $ thus $\sigma,i \Vdash (P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))$.

For all $i\leq n$, we have $i\<n+1$ and $\sigma, n+1 \Vdash P1C$ thus $\sigma, i\Vdash \mathsf{F}(P1C \vee P2C)$, hence $\sigma,i \Vdash (P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))$.

Therefore we have that $\forall i\geq 0, \\;\\; \sigma, i\Vdash (P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))$. Thus:

$$\sigma \Vdash \mathsf{G}((P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))) $$

Hence, it is a **liveliness property**.

Note: This is my first time posting in this community so any comments are appreciated. Also if it were better to post this in the math.stack, let me know!

# Answer
I found the error on the safety proof.

> Let $\hat\sigma=\sigma\[..i\]$, this is a bad prefix for our property.

This is of course wrong. If the property is not satisfied, i.e., $\sigma \not\Vdash \mathsf{G}((P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C)))$ then indeed there is as $i\geq 0$ such that $\sigma, i\not \Vdash ((P1E \wedge P2E) \rightarrow (\mathsf{F}\\, (P1C \vee P2C))$, that is:

$$\sigma, i\Vdash P1E \\,\wedge\\, P2E \\;\\;\textrm{ and } \sigma, i\not\Vdash \mathsf{F}\\, (P1C \vee P2C)$$

The thing is that just because we have $\sigma, i\not\Vdash \mathsf{F}\\, (P1C \vee P2C)$, it does not mean that it cannot become true in the future, therefore we cannot state that $\hat\sigma$ is a bad prefix for the property, as a word $\sigma^\prime$ with prefix $\hat\sigma$ can still be extended in order to satisfy the property.

Hence, this was wrong and it is indeed a liveliness property.
> 0 votes

---
Tags: logic, model-checking, check-my-answer, linear-temporal-logic
---


# Question
Title: How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover
The problem I am trying to solve is that there is an underlying undirected graph `G = (V, E)` with weights on the vertices, where the weight on vertex `v` is denoted by `wv = d(v)` (the degree of the vertex). My goal is to find a vertex cover set `U` (a set where for every `e = (u, v)`, one of vertices `u, v` is in `U`) with the minimal total weight possible.

I have to show that any greedy algorithm, gives a 2-approximation to the best vertex cover.

I can't seem to come up with an idea for such an algorithm. The best I could think of is to select the vertex with minimum weight first and then continue like any greedy algorithm by picking two vertices where edges have not been covered.

Any help would be highly appreciated.

Thank you.

\[Edit\] Since the downvotes for no reason, here's the whole text (Whicih is the same as question text I wrote) we got for the exercise and can't seem to figure out how to even approach to prove.

# Answer
I had to re-read the question multiple times to understand what you wanted to do, but I think I finally understood.

To prove that any greedy algorithm returns a $2$-approximation is the same as showing that any vertex cover is a $2$-approximation (assuming that any greedy algorithm returns a vertex cover, which is not clear to me, depending on how you define the family of greedy algorithms). Since any vertex cover is a subset of the set of all vertices, the problem is equivalent to proving that the set of all vertices is a $2$-approximation.

Since the weight of each vertex is its degree, if each edge is covered, then at least half of the degrees are "covered" (meaning that if $C$ is a vertex cover, then $\sum\limits\_{v\in C}\deg(v) \geqslant \frac12 \sum\limits\_{v\in V}\deg(v)$), because an edge increases the degree of each of its extremities of 1.

I honestly don't find the exercise well formulated using greedy algorithms (surely because there is no very formal way to define a greedy algorithm). It would have been clearer, less confusing, to ask to prove that $V$ itself or any vertex cover is a $2$-approximation.
> 1 votes

---
Tags: algorithms, approximation, weighted-graphs, vertex-cover
---


# Question
Title: Algorithms that depend on expected time and "regular" time complexities
Assume that I have designed an algorithm A, which runs two sub-methods: M1 and M2.

M1 has a O($n$) expected time complexity.

M2 has a O($n^2$) time complexity.

Clearly A uses O($n + n^2$) = O($n^2$) time. Since $n^2$ \> $n$, in terms of time complexity, should A be described as having an **expected** time complexity of O($n^2$), or can the expected term be dropped as the $n$ term was dropped?

# Answer
I'm assuming that $M\_1$ is a randomized algorithm and that the expectation is taken over the random bits.

If you just say that $A$ has time complexity $O(n^2)$, the default assumption is that your are talking about *worst-case* time. Then it would be incorrect to say that $A$ runs in time $O(n^2)$ since (without further assumptions on $M\_1$), it could be the case that $M\_1$ takes time $\omega(n^2)$ on some bad executions.

However, since $M\_2$ runs in time $O(n^2)$ anyway, you can claim that $A$ runs in time $O(n^2)$ *with high probability*. Indeed, by Markov's inequality, $M\_1$ takes $O(n^2)$ time with probability at least $1-\frac{1}{n}$. If you perform $c$ parallel and independent executions of $M\_1$ and stop as soon as one halts, then the running time will be $O(cn^2)$ with probability at least $1-\frac{1}{n^c}$. For $c=O(1)$ this allows you to pick any arbitrary large (but constant) exponent in the probability lower bound while keeping the running time in $O(n^2)$.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?
If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?

# Answer
No, there will be absolutely no implication, for several reasons:

1. The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard problems in polynomial time (which we don't expect them to be able to do), it could still be the case that classical computers cannot solve them in polynomial time.
2. Universal quantum computers, in a theoretical sense, are (to the best of my knowledge) already known to exist. These are just the quantum analogs of universal Turing machines: they can execute any given quantum "program".
3. Both quantum computation and the P vs. NP problem are theoretical notions. What someone can construct in the physical world has absolutely no bearing on anything having to do with them.

Lieuwe Vinkhuijzen gave a different interpretation of your question:

> Will quantum computers be able to solve NP-complete problems efficiently?

The expected answer is: no. So even in this sense, physical quantum computers won't enable us to solve NP-complete problems at will.
> 41 votes

# Answer
No implications are known either way: classical simulation of quantum computers tells us nothing about how hard NP search problems are; fast solutions to NP search problems tell us nothing about how fast quantum computers can be simulated classically. The following scenarios are possible:

* $P=NP=BQP$
* $P=NP\subsetneq BQP$
* $P\subsetneq NP=BQP$
* $P\subsetneq NP\subsetneq BQP$
* $P\subsetneq NP$, $P\subsetneq BQP$ but $BQP$ and $NP$ are incomparable
* NP problems require brute force classically, but are solved by fast (though not necessarily polynomial) quantum algorithms

The blog of one influential theoretical quantum computer scientist, Scott Aaronson, has the header "*If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by just trying all solutions at once*".
> 22 votes

# Answer
If there would be an efficient quantum computer algorithm for $NP$-complete problems, then the $P$ vs. $NP$ problem would be still unsolved. But if one can show, that there is no quantum computer to solve an $NP$-hard problem in polynomial time, then $P$ is unequal $NP$, because $P\subseteq BQP$.

It is unlikely, that an $NP$-complete problem is in $BQP$. Due to the BBBV-Theorem Grover's algorithm is optimal for search problems $\\{ x \in\\{0,1\\}^n\mid f(x)=1\\}$ where f is a computable black-box function. In this case we need $\Theta(\sqrt(2^n))$ steps.

If $M$ is an arbitrary Turing machine, then $L(M)$ is undecidable. Assume there is an oracle to compute $M$. Then one need $\Theta(\sqrt(2^n))$ accesses to the oracle with a QC. The set $\\{\langle M, x, 1^t \rangle \mid \text{ TM }M \text{ accepts }x\in \\{0,1\\}^n\text{ within }t\text{ steps} \\}$ is $NP$-complete. If $t$ is big enough, then $M$ accepts an $x\in\\{0,1\\}^n$ within $t$ steps iff $x\in L(M)$. In this case a QC can not search faster than Grover-like algorithm. So, quantum computers still need exponential run time for $NP$-complete problems. There are good reasons to believe, that $NP$-hard problems are not in $BQP$.
> 1 votes

# Answer
In one (considered unlikely) scenario, building a universal quantum computer would indeed have implications on the problem of P vs. NP.

This is expanding on the case mentioned by Yuval Filmus, "if quantum computers could solve NP-hard problems in polynomial time".

In such a situation, building a universal quantum computer vs just theoretically reasoning about one, would have implications for the P vs NP problem. It would allow for the possibility of just using quantum computers to search/find a proof that resolves P vs NP, which could then be verified by a classical computer.

However, as mentioned by the other answers, while there is no proof separating BQP and NP-complete, currently the evidence and expectations are that quantum computers will not be able to solve NP-complete problems efficiently.
> 0 votes

---
Tags: complexity-theory, complexity-classes, quantum-computing
---