# Question
Title: Dijkstra's algorithm - Finding additional paths with same weight but different edges
given a network with n stations. assuming the shortest between s,t was found using dijkstra's algorithm. let that path be denoted as $(a\_1,a\_2,...,a\_k)$

assume that between the nodes s and t, there's an at least additional path with the same weight, but with different edges(meaning both paths have different edges, nothing in common). how can we find that additional path?

My attempt: let's create an array that holds the parent. that array will be separate, so the value of $parent\[v\_i\]$ for some vertex $v\_i \in V$ stores the parent of $v\_i$ in the array, in the shortest path tree that is formed by the algorithm. now, we'll initiate the first element, meaning the parent of the root to be -1, and if we find shorter path through some vertex u, we can make u the parent of the current vertex. but i am not sure it solves the problem unfortunately.

would really appreciate if you could explain what you do so i can understand it.

tried to do a research on the site, but couldn't find a similar problem with no same edges and i don't know how to solve it, so i am asking for help here

thank you very much

# Answer
> 1 votes
One way to proceed may be to store for each node a list of parents so $parents\[v\_i\]$ becomes an array of lists. There is also the same array of distance from $s$, $d\[v\_i\]$ initially infinite for all $v\_i$ but $s$ ($d\[s\] = 0$).

So like standard version of Dijkstra's algorithm, you maintaint a priority queue $q$ (sorted by $d$). When $v\_i$ is depiled from the queue you explored all the nodes $v\_j$ reached from $v\_i$, in the standard version of the algorithm, there was 2 cases:

* a smallest path to $v\_j$ has been found: $d\[v\_j\]$ and $parents\[v\_j\]$ are updated and $v\_j$ is added to the queue.
* the new path is not better, do nothing.

So now, if the path is smallest, $parents\[v\_j\]$ is replaced by the list with one element $\[v\_i\]$.

And there is an additional case: if path to $v\_j$ is exactly the same in distance, append $v\_i$ to $parents\[v\_j\]$. Note that there is no need to put $v\_j$ again in the queue.

Once you reach $t$ and you backtrack path using $parents\[v\_i\]$, if there are several elements in the list, any may be picked and lead to a different shortest path.

Note that $parents\[v\_i\]$ is $O(N^2)$ in space. The worst cases are very dense graphs, and this would mean that there is a large number of shortest paths. In this case, other method to store $parents\[v\_i\]$ may be more adapted.

---
Tags: graphs, graph-traversal, weighted-graphs, dijkstras-algorithm
---


# Question
Title: How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'?
I call a string of brackets 'correct' if every opening bracket has a corresponding closing bracket somewhere after it and every closing bracket has a corresponding opening bracket somewhere before it. For example

> (())()((()()))

is a correct string and

> )()()(

is an incorrect string.

An operation consists of taking a contiguous subsequence of the input string and 'flipping' every bracket in that subsequence.

Given an arbitrary string of brackets (of even length), the task is to find the smallest number of such operations needed to change it to a 'correct' string of brackets.

Another way to look at this problem is to have a string of +1s and -1s, and to try to find the smallest number of operations (of multiplying every number on an interval by -1) needed to make every prefix of this string nonnegative and every suffix nonpositive.

# Answer
> 4 votes
The DP suggested in the comments by Yuval Filmus indeed works: we can solve the problem in $\mathcal{O}(n^{2})$ by DP.

First note that we may assume that intervals are not allowed to overlap. Take any two overlapping intervals $\[a, b)$ and $\[c, d)$. WLOG $a \leq c$. Then we can replace the two intervals with the intervals $\[a, c)$ and $\[\min(b, d), \max(b, d))$ that do not overlap, have shorter total length and cover exactly the same elements.

Replace opening brackets with $1$, closing brackets with $-1$. Now the problem corresponds to applying the minimum number of operations "multiply interval by $-1$" such that every prefix has nonnegative sum, and the sum over the entire array is zero.

We construct a solution left-to-right. At every position we can either start an interval, or end an active interval.

Let $DP\[m\]\[s\]\[0\]$ denote the minimum number of intervals we need to use such that every prefix sum in the first $m$ elements is nonnegative, the sum of the first $m$ elements is $s$, and we do not have an active interval. Similarly $DP\[m\]\[s\]\[1\]$ is the same value where we do have an active interval.

If the $m$th value is $1$, for $0 \leq s \leq m$ we set

* $DP\[m\]\[s\]\[0\] = DP\[m-1\]\[s-1\]\[0\]$
* $DP\[m\]\[s\]\[1\] = DP\[m-1\]\[s+1\]\[1\]$

Otherwise we set

* $DP\[m\]\[s\]\[0\] = DP\[m-1\]\[s+1\]\[0\]$
* $DP\[m\]\[s\]\[1\] = DP\[m-1\]\[s-1\]\[1\]$.

Then we end and start intervals, setting

* $DP\[m\]\[s\]\[0\] = \min(DP\[m\]\[s\]\[0\], DP\[m\]\[s\]\[1\])$
* $DP\[m\]\[s\]\[1\] = \min(DP\[m\]\[s\]\[1\], DP\[m\]\[s\]\[0\] + 1)$

The base case is $DP\[0\]\[0\]\[0\] = 0$, $DP\[0\]\[0\]\[1\] = 1$.

There are $\mathcal{O}(n^{2})$ states, and we do $\mathcal{O}(1)$ work to calculate each of them, therefore the algorithm runs in $\mathcal{O}(n^{2})$. The DP can be implemented to use $\mathcal{O}(n)$ memory by only storing the values of $DP$ for the current $m$.

Here is a C++ implementation of the algorithm.

```
#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}

```

# Answer
> 0 votes
Nice question!

Here is the problem in more popular terms.

### Balanced Parentheses

A string of parentheses is balanced if we can change it to the empty string by removing substrings "()" repeatedly. For example, empty string, "()" and "(())()((()()))" are balanced but none of "())" and ")()()(" is balanced.

It is clear that a balanced string must start with "(" and ending with ")". It must be of even length as well.

### the Problem of Minimum Operations to Balance a String

Let `s` be a non-empty string of parentheses of length `n`. The only operation we can perform is flipping every parenthesis in a substring, that is, changing every "(" to ")" and every ")" to "(" for some contiguous characters in the string. The problem is how to find the smallest number of operations that make `s` balanced.

### an Approach by Dynamic Programming

What are the appropriate subproblems? They are `dp[i][j]` for `0 <= i < j < n`, where `dp[i][j]` is the minimum number of operations that balance the substring between indice `i` and index `j` inclusive. The wanted minimum number of operations that balance `s` is `dp[0][n-1]`.

Since any string of odd length cannot be balanced, we will restrict our attention to strings of even length from now on.

**the base cases** `dp[i][i+1]` is 0 if the substring between `i` and `i+1` is balanced, i.e, "()". It is 1 otherwise.

**the recurrence relation** I will use Java to define the recurrence relation.

```
void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

```

The recurrence relation comes from the following well-known property of balanced strings. A non-empty string is balanced if and only if it is the concatenation of two balanced strings or "(" followed by a balanced string followed by ")".

The processing before the `for` loop, which sets `min` to be `dp[i + 1][j - 1]` plus 0, 1 or 2, comes from the fact that "(" followed by a balanced string followed by ")" must be a balanced string.

The processing in the `for` loop, which tries to shrink `min` to `dp[i][k] + dp[k + 1][j]` minus 0 or 1 for some `k` that is between `i` and `j`, comes from the fact that the concatenation of two balanced strings must be a balanced string.

The time-complexity of this approach is $O(n^3)$. The space-complexity is $O(n^2)$.

## Length of the "most unbalanced" strings

The smallest length of a string that cannot be balanced by less than 2 operations is 4. For example, ")((("

The smallest length of a string that cannot be balanced by less than 3 operations is 10. For example, ")(((((())("

The smallest length of a string that cannot be balanced by less than 4 operations is 22. For example, ")(())))(((((((((((())(".

Question: What is the smallest length of a string that needs at least 5 operations? As I have computed, it must be greater than 28. However, my computation is not enough to determine the actual value. How fast can we compute these smallest lengths?

---
Tags: strings, substrings
---


# Question
Title: Shortest path between all pairs with colored nodes
I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly. The question is:

Let's say we have a directed graph with no cycles, it has `N` vertices and `M` edges. **Exactly** 2018 vertices are colored green, and the others are black. We know that in each **shortest** path, each vertex is colored green, **perhaps** without the first and the last node.

We can find the shortest path of all two pairs of nodes in: `O(___)` and not less

What I tried:
If we run the `Floyd Warshall` algorithm on the 2018 green vertices we get the shortest path between all pairs of greens. (This is `O(1)` because of the green vertices amount is constant).

Now for each (u,v) in `VxV`:

* If both u and v are green we already have the shortest path from `Floyd Warshall`.
* If one is green and the other black, we add the edge's weight that connects the source/destination to the green group and add the `Floyd Warshall` result.
* If both u and v, are black, we add the lightest weight of each which connects to the green group.

I think my solution is kind of messy, and I do not know if it's 100% correct.

The solution is: We can find the shortest path of all two pairs of nodes in: `O(n^2)` and not less.

# Answer
Your answer and reasoning are correct, but the last steps in your algorithm are wrong.

First, discard all edges with no green vertex. Then:

To find the shortest path between a green and black node, you have to consider all of the black node's green-adjacent edges, and add the shortest path to/from the green. There are at most 2018 of these, so it's still constant time.

To find the shortest path between two black nodes, you have to consider all combinations of their green-adjacent edges, and add the distance between the greens. There are at most 20182 of these combinations, so it's still constant time.

So you can certainly do this in O(n2) time, and you can't do any better, because that's also the size of the output.

It may be simpler just to show how you can optimize Floyd-Warshall to take O(n2) time when all edges are known to be green-adjacent.
> 2 votes

# Answer
The time complexity of `Floyd Warshall` to find shortest path among all pairs of nodes isn't `O(n^2)`. It's `O(n^3)`.

> This is O(1) because of the green vertices amount is constant.

This is not correct. if the number of green node is `G`, then the complexity of running `Floyd Warshall` to find all pair shortest path among `G` nodes is - `O(G^3)`.

Now the second part's complexity is correct. That's `O(n^2)` because you are traversing `VxV` nodes.

So your proposed solution would have a time complexity of - `O(n^2 + G^3)`.

Now here what I don't know is - is `N` way more bigger than `G`(2018)? What you need to consider here - which one would take more computation? if `n^2` is way bigger than `G^3`, then we can ignore the `G^3` part as `Big-O` notation is the upper bound indication. And if `G^3` is bigger then we can ignore the `n^2` part.

**Note** \- Now I am not sure about the `not less` part in your question. `Big-O` notation is the upper bound indication. This inherently mean that `this solution would take X computation at most`. You can see `Big-O` means `not more`. I think what your question expects is to find the lower bound(`not less`). If so, then it should have been `Omega` notation not `Big-O`.
> -2 votes

---
Tags: shortest-path
---


# Question
Title: Understanding denormalized numbers in floating point representation
I am confused about how denormalized numbers work in floating point representation.

I was referring to Stallings book and this article. The book initially explains floating point number format in general and then explains IEEE 754 floating point format. I will tell explicitly when I am talking about floating point format in general and when about IEEE 754.

First let me tell you what I understand. Lets consider single precision (32 bit) numbers. As shown in the book, the normalized numbers in IEEE 754 takes following form:

In both general and IEEE 754 floating point number,

* Sign bit is 0 for positive number, 1 for negative number.
* Fraction aka significand has implicit leading 1.
* Biased component is exponent with bias 127.

With this information, I am able to come p with range of normalized numbers in IEEE 754 standard. Its $\pm2^{-126}$ to $(2-2^{-23})\times 2^{127}$ as given in that article. This is how I interpret, how its derived.

* **Max significand:** $(1.\underbrace{11..11}\_{23\text{ bits}})\_2=(2-2^{-23})\_{10}$
* **Min significand:** $(1.\underbrace{00..00}\_{23\text{ bits}})\_2=(1)\_{10}$ and is simply omitted from multiplication to $\pm2^{-126}$
* **Min exponent:** Biased: $(00000001)\_2=(1)\_{10}$, Unbiased: $1-127=-126$
* **Max exponent:** Biased: $(11111110)\_2=(254)\_{10}$, Unbiased: $254-127=127$

I know that significand in de-normalized range does not have implicit leading 1 and in fact has leading 0.

**Doubts**

I have following doubts about denormalized range in IEEE 754 format:

1. As give in that article, how is the denormalized single precision range is $\pm 2^{-149}$ to ${(1-2^{-23})\times2^{-126}}$
2. Consider below table from Stallings book. In this, in the biased exponent column, entries for positive and negative denormalized (last two) rows is $0$, but in the value column, the exponent of $2$ is $e-126$, even though there is no $e$ elsewhere in those rows.
3. Now consider the below table given under summary section of that article. Note that in 2nd row and 5th last row of denormalized real, "Exponent" column says $00..00$, however in value column, there is $+1$ in the exponent: $2^{(-b\color{red}{+1})}$. From where this $+1$ came?
4. How exponents in the book (as explained in the question 2) and the exponent in the article (as explained in the question 3) compare and how they lead to the range asked in question 1?

# Answer
Although, the question is a bit old, but it may help people coming here for similar question.

A vital detail was missed out in the article that you referred to and it is that the standard chose to interpret an all 0s exponent to be equivalent to '-126' and not '-127'. One place, where I found a nice explanation (and an explicit statement about this truth) is this article. To quote from it:

> **Subnormal Numbers**: When all the exponent bits are 0 and the leading hidden bit of the siginificand is 0, then the floating point number is called a *subnormal number*. Thus, one logical representation of a subnormal number is
>
> `(–1)s × 0.f × 2<sup>–127</sup> (all 0s for the exponent) ,`
>
> where f has at least one 1 (otherwise the number will be taken as 0). However, **the standard uses –126, i.e., bias +1 for the exponent rather than –127** which is the bias for some not so obvious reason, possibly because by using –126 instead of –127, the gap between the largest subnormal number and the smallest normalized number is smaller.
>
> The largest subnormal number is 0.999999988×2–126. It is close to the smallest normalized number 2–126.
> 9 votes

---
Tags: floating-point
---


# Question
Title: Mathematical proof for why gradient descent algorithm always converges
I am currently learning machine learning and I stumbled across gradient descent. I understand why the algorithm always converges to the global/local minimum when the learning rate is small enough in my head, but is there a mathematical proof?

Thank you!

# Answer
It looks like you put some emphasis on mathematical rigor. It just happens my motto is currently "from math and larger than math".

Yes, there are many mathematical proofs for conclusions along the line that gradient descent method converges to local minimum when the steps are small enough. We will need some precise statement on the condition of $f$ and the steps taken. Let me quote from Wikipedia,

> With certain assumptions on the function $F$ (for example, $F$ convex and $\nabla F$ Lipschitz) and particular choices of $\gamma$ (e.g., chosen either via a line search that satisfies the Wolfe conditions or the Barzilai-Borwein method shown as following), $$ \gamma\_n=\frac{(x\_n-x\_{n-1})^T\[\nabla F(x\_n) - \nabla F(x\_{n-1})\]} {||\nabla F(x\_n) - \nabla F(x\_{n-1})||^2}$$ convergence to a local minimum can be guaranteed. When the function $F$ is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

For some actual statements and proofs in their full clear detail, you can read a course note by Ryan Tibshirani at CMU. Unfortunately, because of the required mathematical rigor, they are too long to be included here.
> 5 votes

# Answer
$$let,\ x\_{(n)} \ be\ a\ point\ on\ x-axis\ where\ f'( x) \ =\ 0\ ,\ and\ x\_{(n\ +\ h)} \ is\ any\ other\ arbitary\ point \\ \therefore \ \ \frac{f'( x\_{(n\ +\ h)})}{|\ f'( x\_{(n\ +\ h)}) \ |} =\begin{cases} 1 & \mathrm{if,} \ h\ \ \>0\\ 0 & \mathrm{if,} \ h\ =\ 0\\ -1 & \mathrm{if,} \ h\ \< \ 0 \end{cases}\\similarly,\ \ \frac{x\_{(n)} \ -\ x\_{(n\ +\ h)} \ }{|\ x\_{(n)} \ -\ x\_{(n\ +\ h)} \ |} \ =\ \begin{cases} 1 & \mathrm{if,} \ h\ \ \< 0\\ 0 & \mathrm{if,} \ h\ =\ 0\\ -1 & \mathrm{if,} \ h\ \>\ 0 \end{cases}\\or,\ \frac{x\_{(n)} \ -\ x\_{(n\ +\ h)} \ }{|\ x\_{(n)} \ -\ x\_{(n\ +\ h)} \ |} \ =\ -\ \ \ \frac{f'( x\_{(n\ +\ h)})}{|\ f'( x\_{(n\ +\ h)}) \ |}\\ \therefore \ x\_{(n)} \ =x\_{(n\ +\ h)} \ -\ \eta \times f'( x\_{(n\ +\ h)}) \ \ \ \ \ \ \left\[ where\ \eta \ =\frac{|\ x\_{(n)} \ -\ x\_{(n\ +\ h)} \ |}{|f'( x\_{(n\ +\ h)}) \ |} \ \right\]$$
> 0 votes

---
Tags: machine-learning
---


# Question
Title: What is the time complexity of this "reverse words" algorithm?
I had to write an algorithm that, given the input `['h', 'a', 'r', 'd', ' ', 'i', 's', ' ', 'c', 's']` would return `['c', 's', ' ', 'i', 's', ' ', 'h', 'a', 'r', 'd']`. I found an algorithm that I *think* I am happy with, but unfortunately, I do not know how to compute its running-time.

The algorithm essentially has two stages. First, I reverse the entire string. Then, I scan that string to find words, and when I find a word, I reverse only that word. In terms of `message`, the first time we reverse we will do (n/2) steps. Then, for each word we find, we'll do (m / 2) steps, where m is the length of the word (m is not constant). How do I express the Big O notation for this?

function reverseWords(message) {
  // reverse entire string
  reverseStrArr(message, 0, message.length - 1);

  let wordStart = 0;
  let wordEnd = null;

  for (let i = 0; i < message.length; i++) {
    const char = message[i];

    if (char === " ") {
      wordEnd = i - 1;

      reverseStrArr(message, wordStart, wordEnd);

      // reset
      wordStart = wordEnd + 2;
      wordEnd = null;
    }

    if (i === message.length - 1) {
      reverseStrArr(message, wordStart, i);
    }
  }
}

function reverseStrArr(stArr, minIdx, maxIdx) {
  const midIdx = Math.floor((minIdx + maxIdx) / 2);

  for (let i = minIdx; i <= midIdx; i++) {
    const tailIdx = maxIdx - (i - minIdx);

    const temp = stArr[tailIdx];
    stArr[tailIdx] = stArr[i];
    stArr[i] = temp;
  }
}
```

# Answer
This algorithm runs in linear time in the size of the input $O(n)$.

To see why try to count how many times you read/write to a position in the string. Note that asymptotically this is equal to the total running time.
> 1 votes

# Answer
Have you run the code?

If you reverse the array `['d', 'r', 'a', 'h', ' ', 's', 'i', ' ', 's', 'c']` you get the desired result of `['c', 's', ' ', 'i', 's', ' ', 'h', 'a', 'r', 'd']`. If you then reverse the words you get `['s', 'c', ' ', 's', 'i', ' ', 'd', 'r', 'a', 'h']`, which is not what you want.

You can't get better than an $O(n)$ complexity for reversing an array of size $n$. If you want an explanation as to why this is the case, then we must be slightly more precise. Below I do the analysis for an easy to analyze implementation, not an inplace version. (The analysis is similar for an inplace version, and I think that you can work it out.)

Let's assume that the operations which have a cost are "reading a value from an array", "writing a value to an array", and "comparing two values". The input to our algorithm is an array `input` of size $n$ and the output is an array `output` also of size $n$, and we must ensure that when the algorithm terminates that `output[i] == input[n-i-1]` where $0 \leq i \leq n$. (Take a minute and convince yourself that this is a correct description of the problem, and that the equality is correct for both even and odd values of $n$.) To make the analysis as simple as possible, we will assume that there is an array named `output` of size $n$ just waiting for us, and that `output[i] == 0` for all $i \< n$.

Therefore, any algorithm must assign to `output[i]` the value `input[n-i-1]` for all $n$ possible values of $i$, unless `input[n-i-1] == 0`, in which case no assignment needs to be made, as the correct value is already present. So one possible implementation would loop through the $n$ different values of $i$ and check if `input[n-i-1] == 0` and continue when the condition was true and assign the value to `output[i]` when the condition was false.

If the input array is $n$ `0`s then this implementation would perform exactly $2n$ operations, one operation to get the value at `input[n-i-1]` and one operation to compare it to `0`. However, if there are no values of `0` in the input, then there are exactly $3n$ operations performed, $2n$ of the operations are the same as before, but now there are $n$ assignments of the value to the correct position in the output array (here we assume we don't need to read the value from the input array again). More generally if `0` occurs $m$ times in the input then there are exactly $2n + m$ operations performed.

Now this part is important: if we don't check the value, but instead just do the assignment then there are always $2n$ operations, one to read from the input and one to write to the output. Checking the value each time to avoid an unnecessary copy does more work than not checking the value in the majority of cases. Since any algorithm which uses these operations must do at least this much work, you can't do better than $O(n)$ operations.

But what about other operations? For an inplace version you might consider an operation which swaps two values in the array `swap(i, j)`. Such an operation allows you to reverse the array in $n/2$ operations (for even $n$), which is still $O(n)$.
> 0 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, string-manipulation
---


# Question
Title: Why and how is a quantum computer faster than a regular computer?
I'm currently reading a book (and a lot of wikipedia) about quantum physics and I've yet to understand how a quantum computer can be faster than the computers we have today.

How can a quantum computer solve a problem in sub-exponential time that a classic computer can only solve in exponential time?

# Answer
> 40 votes
A quantum computer by itself isn't faster. Instead, it has a different *model of computation*. In this model, there are algorithms for certain (not all!) problems, which are asymptotically faster than the fastest possible (or fastest known, for some problems) classical algorithms.

I recommend reading The Limits of Quantum by Scott Aaronson: it's a short popular article explaining just what we can expect from quantum computers.

# Answer
> 19 votes
The basic idea is that quantum devices can be in several states at the same time. Typically, a particle can have its spin up and down at the same time. This is called superposition. If you combine n particle, you can have something that can superpose $2^n$ states. Then, if you manage to extend, say, bolean operations to superposed states (or superposed symbols) you can do several computations at the same time. This has constraints but can speed up some algorithms. One major physical problem is that it is harder to maintain superposition on larger systems.

# Answer
> 8 votes
its an open problem subject to cutting edge research whether quantum algorithms will ever be faster than "classical" algorithms both on the theoretical and applied levels. in complexity theory it is reflected in the question eg BQP =? P ie whether quantum computing "P" class is equivalent or not to the classical P (Polynomial time) class & there are many other related open questions.

there is one very intriguing & significant datapoint: the award-winning Shors algorithm factors numbers in P quantum time, but it is still not known whether there exists a P-time classical factoring algorithm.

a new direction over last few years is work in adiabatic quantum computing which is easier to implement/engineer than other standard methods involving qbit transport (but yet still extremely difficult to implement).

the only quantum computer(s) ever built to date is by Dwave systems and is currently subject to intense scientific scrutiny and controversy regarding its actual quantum effects & performance; it is very expensive and basically does not outperform a desktop computer, when the classical code is fully (human-/hand-) optimized. however it can be fairly stated no other corporate, government, or university research entities appear to be anywhere close to their level of applied/technical/engineering advancement so far.

the *scientific* outlook is cloudy at the moment & some scientific experts/critics/skeptics eg Dyakonov have long believed/argue strongly that *scalable* QM computers will *never* materialize due to insurmountable technical difficulties and/or barriers.

# Answer
> 0 votes
Think of it this way: There are problems that can be solved by solving a whole lot of individual sub-cases \[example: factoring by trial division\]. These problems take a long time to solve if one has to solve the sub-cases one after another. They can be solved much faster if one can provide enough hardware to solve all of the sub-cases in parallel, but that is not practical because the amount of hardware needed increases with the problem size. Quantum computing exploits the *superposition-of-states* feature of Quantum Mechanics to *simulate* providing enough hardware - i.e each state in the superposition is 'the machine' for one of the sub-cases. Note that this simulation is done NOT by software, but by Nature itself.

# Answer
> 0 votes
*(Note: my English might be insufficient at some points. Sorry if it's distracting.)*

### How QC solutions work in theory

A good analogy of how they work would be this seemingly unrelated video. We see salt particles on a limited flat surface, navigating themselves into a certain pattern when they "hear" a sound with a specific wavelength. (It's all about the small integer ratios of the wavelength and the plane size; much like steady Lissajous curves, or chords in music.) The point is, they move around until they reach a state where they "like to stay".

Quantum Computers, according to their believers (and to the best of my knowledge), work similarly. They are a network of qbits taking every possible state (at once!) but they only get stable in a certain constellation - the one that satisfies your criteria. Then you go read their final state, and it should be the answer itself, or one of the likely answers. It's as if you calculated all points of a curve with the salt-and-sound method. Classical computers would do this like a particle emulator where you'd have to calculate every grain of salt; with this sound wave thing, you get an instant answer because salt is "everywhere" at the beginning, just as qbit states.

And this is nice - in theory.

### May never work

The problem is, you can't communicate with quantum bits. I mean, not really. Physicists have a *theory*, merely a theory, that such thing as superposition even exists. It's not a thing, it's an attempt to explain something we don't know. It's a method of working with unsure data. It's like saying *"until you solve this equation, x has all the possible values, and then it suddenly collapses and takes on only one"*. Sure, it's one way to look at things; but it's not reality itself, it's just a side effect of missing information. If you already know x and I don't, then only I will have this uncertainty, and x, *in fact,* has a very specific value all along.

### A pair of gloves

The same is true for quantum entanglement. According to the mainstream theory, when you *observe* one of the pairs, you gain instant information of the other. This sounds like magic, but it's like a pair of gloves: if we put them in two bags, then we both take one of the bags (random) and travel to the opposite ends of the galaxy, you will still know that if you have the left one in yours, then the right one was in mine. No information travels thru spacetime, nothing happens, only we know something on both sides - as soon as we "make the glove function collapse", aka check the bag. Yes, they say there's a *wave function* that *collapses* when you observe an entity; but again, this is not how it *is*, it's how we *imagine it might as well be*.

### Schrödinger told us, we never listened

There's the very concept of *superposition*, somethng being in more than one state at the same time, that's constantly being referred to and is already too much for common sense. It all goes back to the Copenhagen Interpretation, with a lot of debate around it, and honestly I'll open a champagne when they finally admit there's a better explanation. Even Schrödinger himself insisted that the probability approach to the poor cat's wellbeing is just wrong; it was a disproval of an explanation attempt, he said "guys, this must be false because it leads to a contradiction in this simple thought experiment, the cat is dead *and* alive which is impossible"; instead, they accepted the impossible. Multiple values for the same thing at the same time. Against the very reason to use variables in the first place - to have one exact meaning. Against the concept of proving or disproving theorems where two values for x means your statement is wrong.

However crazy this may sound, however you want to believe "they didn't give all that money for nothing" and "big companies know what they're doing" - superposition is probably a misunderstanding, and quantum computers will probably fail to deliver anything reliable. Also they're very-very specific to a problem, you have to rewire them each time you want to add different numbers together, and even then, it's a very unstable way. It's like calculating the ratio of two numbers by cutting a plane to the right size, put salt on it, and then turn up the music.

### TL;DR

* Quantum computers do NOT help us, and it's not known if they ever will;
* They only ever will if we were right about the cat (which is unlikely);
* Efforts and expenses are way beyond the point of "worth it";
* The most practical problem they will ever solve is like factoring numbers;
* They will advertise the hell out of them no matter what.

# Answer
> -1 votes
A quantum system is a system that exists in a quantum state(s) at different probabilities determined by environmental constraints. Assuming that a quantum computer contains all the states of an n-bit quantum system the extraction of one of these states collapses the system to one of the states. This is akin to a hash function using O(1) to search for a bucket without iteration. Two things are needed, quantum storage of the n-bit systems and a hash-like function to collapse the state that is needed. The constrains play the role of different hashing functions for collapsing the n-bit system into the wanted state.

---
Tags: quantum-computing
---


# Question
Title: Repeated addition and comparisons of floating point numbers
In the following program where I repeatedly *half* an integer, it takes until `i = 1074` for my integer to be equal to zero (I know that ideally the while loop shouldn't have ended, and the reason why it stopped was because of the memory limit of the computer).

```
a = 1.0
i = 0
while a != 0:
    a = a / 2
    i = i + 1
    print(a, i)

```

However, the next program, where I compare the *halved* integer using addition ends at `i = 53`.

```
a = 1.0
b = 1.0
i = 0
while a + b != b:
    a = a / 2
    i = i + 1
    print(a, i)

```

My question is *why is there a big difference* here? Why does the first program go up to `1075` iterations, while the latter goes up to `53`?

Also, when I tried `a + b + c != b + c`, it went up to just `52`, furthermore

```
a + b + c + d != b + c + d

```

only went up to `51`. Why isn't there a big difference here?

# Answer
> 3 votes
The reason you are seeing these results are not due to the memory limits of your computer, but rather of the limits of the encoding of "floating point" numbers. Python uses 64 bit floats (aka double precision floating point numbers), which are well described on wikipedia: https://en.wikipedia.org/wiki/Double-precision\_floating-point\_format

In short, there are only 52 bits for the significand and 11 bits for the exponent. $2^{1023}$ is the highest exponent that can be represented.

---
Tags: python, number-formats
---


# Question
Title: Why do negative array indices make sense?
I have came across a weird experience in C programming. Consider this code:

```
int main(){
  int array1[6] = {0, 1, 2, 3, 4, 5};
  int array2[6] = {6, 7, 8, 9, 10, 11};

  printf("%d\n", array1[-1]);
  return 0;
}

```

When I compile and run this, I don't get any errors or warnings. As my lecturer said, the array index `-1` accesses another variable. I'm still confused, why on earth does a programming language have this capability? I mean, why allow negative array indices?

# Answer
> 27 votes
The array indexing operation `a[i]` gains its meaning from the following features of C

1. The syntax `a[i]` is equivalent to `*(a + i)`. Thus it is valid to say `5[a]` to get at the 5th element of `a`.
2. Pointer-arithmetic says that given a pointer `p` and an integer `i`, `p + i` the pointer `p` advanced by `i * sizeof(*p)` bytes
3. The name of an array `a` very quickly devolves to a pointer to the 0th element of `a`

In effect, array-indexing is a special case of pointer-indexing. Since a pointer can point to any place inside an array, any arbitrary expression that looks like `p[-1]` is *not* wrong by examination, and so compilers don't (can't) consider all such expressions as errors.

Your example `a[-1]` where `a` is actually the name of an array is actually invalid. IIRC, it is undefined if there's a meaningful pointer value as the result of the expression `a - 1` where `a` is know to be a pointer to the 0th element of an array. So, a clever compiler could detect this and flag it as an error. Other compilers can still be compliant while allowing you to shoot yourself in the foot by giving you a pointer to a random stack slot.

The computer science answer is:

* In C, the `[]` operator is defined on pointers, not arrays. In particular, it's defined in terms of pointer arithmetic and pointer dereference.
* In C, a pointer is abstractly a tuple `(start, length, offset)` with the condition that `0 <= offset <= length`. Pointer arithmetic is essentially lifted arithmetic on the offset, with the caveat that if the result of the operation violates the pointer condition, it is an undefined value. De-referencing a pointer adds an additional constraint that `offset < length`.
* C has a notion of `undefined behaviour` which allows a compiler to concretely represent that tuple as a single number, and *not* have to detect any violations of the pointer condition. Any program that satisfies the abstract semantics will be safe with the concrete (lossy) semantics. Anything that violates the abstract semantics can be, without comment, accepted by the compiler and it can do anything it wants to do with it.

# Answer
> 15 votes
Arrays are simply laid out as contiguous chunks of memory. An array access such as a\[i\] is converted to an access to memory location *addressOf*(a)+i. This the code `a[-1]` is perfectly understandable, it simply refers to the address one before the start of the array.

This may seem crazy, but there are many reasons why this is allowed:

* it is expensive to check whether the index i to a\[-\] is within bounds of the array.
* some programming techniques actually exploit the fact that `a[-1]` is valid. For instance, if I know that `a` is not actually the start of the array, but a pointer into the middle of the array, then `a[-1]` simply gets the element of the array that is to the left of the pointer.

# Answer
> 4 votes
As the other answers explain, this is undefined behaviour in C. Consider that C was defined (and is mostly used) as a "high level assembler". C's users value it for its uncompromising speed, and checking stuff at runtime is (mostly) out of the question for the sake of sheer performance. Some C constructs that *look* nonsensical for people comming from other languages make perfect sense in C, like this `a[-1]`. Yes, it doesn't *always* make sense (

# Answer
> 3 votes
One can use such a feature to write memory allocation methods that access memory directly. One such use is to check the previous memory block using a negative array index to determine if the two blocks can be merged. I've used this feature when I develop a non-volatile memory manager.

# Answer
> 2 votes
C is not strongly typed. A standard C compiler wouldn't check array bounds. The other thing is that an array in C is nothing but a contiguous block of memory and indexing starts at 0 so an index of -1 is the location of whatever bit-pattern is before `a[0]`.

Other languages exploit negative indices in a nice way. In Python, `a[-1]` will return the last element, `a[-2]` will return the second-to-last element and so on.

# Answer
> 1 votes
In simple words:

All variables(including arrays) in C are stored in memory. Let's say you have 14 bytes of "memory" and you initialize the following:

```
int a=0;
int array1[6] = {0, 1, 2, 3, 4, 5};

```

Also,consider the size of an int as 2 bytes. Then,hypothetically, in the first 2 bytes of memory the integer a will be saved.In the next 2 bytes the integer of the first position of the array will be saved(that means array\[0\]).

Then, when you say array\[-1\] is like referring to the integer saved in memory that is just before array\[0\],which in our is,hypothetically, integer a. In reality, this is not exactly the way that variables are stored in memory.

# Answer
> 0 votes
```
//:Example of negative index:
//:A memory pool with a heap and a stack:

unsigned char memory_pool[64] = {0};

unsigned char* stack = &( memory_pool[ 64 - 1] );
unsigned char* heap  = &( memory_pool[ 0     ] );

int stack_index =    0;
int  heap_index =    0;

//:reserve 4 bytes on stack:
stack_index += 4;

//:reserve 8 bytes on heap:
heap_index  += 8;

//:Read back all reserved memory from stack:
for( int i = 0; i < stack_index; i++ ){
    unsigned char c = stack[ 0 - i ];
    //:do something with c
};;
//:Read back all reserved memory from heap:
for( int i = 0; i < heap_index; i++ ){
    unsigned char c = heap[ 0 + i ];
    //:do something with c
};;

```

---
Tags: programming-languages, arrays, c
---


title: Kirchhoff's Spanning Tree Algorithm

text:
# Question
Title: Kirchhoff's Spanning Tree Algorithm
Recently I have studied *Kirchhoff's spanning tree algorithm* to count the number of spanning trees of a graph, which has the following steps:

1. Build an adjacency matrix
2. Replace the diagonal entries with the degrees of the corresponding nodes
3. Replace all the other ones excluding the one's included in the
diagonal by $-1$
4. Then find the minor of any one of the elements to get your answer.

These all steps looks like magic to me. Can anyone explain how Kirchhoff derived this to obtain the number of spanning trees, I want to know the logic behind how this algorithm works, but all I can find in YouTube is the above steps only.

# Answer
It looks like magic because the proof of Kirchhoff's Matrix Tree Theorem is nontrivial. It relies on several algebraic properties of the matrix constructed in steps 1-3, which is called the Laplacian matrix of the graph. Let $A$ be the adjacency matrix, and let $D$ be the diagonal matrix with the degrees of the nodes on the diagonal. Steps 1-3 build the matrix $L = D-A$: this is the Laplacian matrix of the graph.

So the question becomes, why should a minor of the Laplacian matrix be equal to the number of spanning trees of the graph?

To answer this question, we need to use other properties of $L$. One property is that we can also write $L$ as $B \cdot B^\top$ where $B$ is the oriented incidence matrix of the graph, that is, a matrix with one row per node $u$ and one column per edge $e$, where entry $B\_{ue}=1$ if $e=\\{u,v\\}$ with $u\<v$, $B\_{ue}=-1$ if $e=\\{u,v\\}$ with $v \< u$, and $B\_{ue}=0$ if $e$ does not contain $u$. For example, for a triangle graph, the Laplacian matrix is $$ L=\left\[\begin{array}{ccc} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{array}\right\] $$ and the incidence matrix is $$ B=\left\[\begin{array}{ccc} 1 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & -1 & -1 \end{array}\right\]. $$ Note that the inner product of two distinct rows of $B$ is $-1$ if the corresponding nodes are adjacent, and 0 if they are not. The inner product of a row of $B$ with itself equals the degree of the corresponding node. (Just use the definition of $B$.) This is why $L=B\cdot B^\top$.

Assuming the graph is connected, the rank of $B$ is exactly $n-1$ where $n$ is the number of nodes of the graph. It is not $n$ because if you sum all rows, you get a zero vector. It is $n-1$ because the number of independent columns of $B$ is $n-1$: if you take any subset of columns corresponding to the set of edges of any spanning tree of the graph, these columns will be independent; the only way to have a dependent set of columns is when the edges selected contain a cycle.

If we delete a row and corresponding column of $L$, we obtain a matrix $M$. If we delete the corresponding row of $B$, we obtain a matrix $C$. Now $M=C \cdot C^\top$ for the same reasons that $L=B \cdot B^\top$. We are interested in $\det(M)=\det(CC^\top)$. In the example of the triangle graph above, $$ M=\left\[\begin{array}{cc} 2 & -1 \\ -1 & 2 \end{array}\right\] $$ and $$ C=\left\[\begin{array}{ccc} 1 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right\]. $$

The last step is to invoke another algebraic fact, the Cauchy-Binet formula. This says that for any matrix $C$,
$$ \det(C C^\top) = \det (C\_{K\_1}) \det(C\_{K\_1}^\top) + \ldots + \det (C\_{K\_q}) \det(C\_{K\_q}^\top) $$ where each $C\_{K\_i}$ denotes an $(n-1) \times (n-1)$ submatrix of $C$ and the sum runs over all such submatrices. Thus, $$ \det(C C^\top) = \det (C\_{K\_1})^2 + \ldots + \det (C\_{K\_q})^2. $$

However, $\det(C\_{K\_i})=\pm 1$ if the edges corresponding to $C\_{K\_i}$ comprise a spanning tree, while $\det(C\_{K\_i})=0$ otherwise (because then the set contains a cycle and the corresponding columns are not independent). Thus, the value of the sum is exactly the number of spanning trees.
> 4 votes

---
Tags: algorithms, algorithm-analysis, spanning-trees
---


# Question
Title: Demonstrating that probability for every possible result is uniform at the end of an algorithm
I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$. At some point ($t=k+1$) the array will be full and we must choose a value inside the array to replace with the new one. The objective is to find an algorithm that outputs a uniform subset of $k$ elements. For example, with $k=2$ and $t=3$ it will output with uniform probability one of the following: $\\{1,2\\}$, $\\{1,3\\}$ or $\\{2,3\\}$. One possible algorithm is the following:

1. create array of $k$ elements
2. FOR $t=1,.\ldots,T$:
3. if array is not full insert an empty space
4. receive an input
5. discard the input with probability $1 - k/t$
6. else insert the input at a uniform location
7. END FOR
8. return array

It's easy to implement such a program and convince yourself that this is indeed a solution to the problem but how do I demonstrate it? Essentially I need to demonstrate that each subset has probability $1/\binom tk$ to be the result at the end (that's because $\binom tk$ is the number of possible subsets of $k$ elements at time $t$).

# Answer
The proof is by induction. The base case $t = k$ is clear. Suppose that the claim is true at some time $t$. We will prove it for time $t+1$.

Let the first $t+1$ elements be $x\_1,\ldots,x\_{t+1}$. By the induction hypothesis, at time $t$ each of the $\binom{t}{k}$ possible $k$-subsets of $x\_1,\ldots,x\_t$ is found in the array with equal probability. The probability that at step $t+1$ the array remains the same is $1-k/(t+1)$, hence each of the $k$-subsets of $x\_1,\ldots,x\_t$ appears at time $t+1$ with probability $$ \frac{t+1-k}{t+1} \frac{1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}. $$ Now consider some $k$-subset $S$ of $x\_1,\ldots,x\_{t+1}$ that contains $x\_{t+1}$. For this set to be appear at time $t+1$, the following two events need to happen: at time $t$, the array consisted of $S \setminus \\{x\_{t+1}\\}$ together with one of the $t-(k-1)$ remaining elements; and at time $t+1$, this element was replaced by $x\_{t+1}$. In total, the probability is $$ \frac{k}{t+1} \cdot \frac{1}{k} \cdot \frac{t-k+1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}. $$
> 1 votes

---
Tags: algorithms, algorithm-analysis, probability-theory, sets, probabilistic-algorithms
---


# Question
Title: What is the shortest superstring for $\{c (ab)^k, (ba)^k, (ab)^k c\}$?
In this paper on PDF page 3, they give $\\{c (ab)^k, (ba)^k, (ab)^k c\\}$ as an example of an input to the GREEDY algorithm for shortest superstring that causes it to have an approximation ratio of 2.

As far as I can tell, the shortest superstring of that set is either $c (ab)^k c (ba)^k$ or $b (ab)^k c (ab)^k$ -- either way, the length is $4k + 2$. Unfortunately, this contradicts the claim in the paper that GREEDY outputs a string of length 2 times the optimal superstring.

* Without loss of generality, we can assume that GREEDY will never output a string longer than the concatenation of its input set -- if the GREEDY algorithm really is described in that way, we can just add an if statement to check that case and return the concatenation instead.
* The length of the concatenation of the input strings is $6k + 2$.
* For all $k \in \mathbb{N}$, $1 \le \frac{6k + 2}{4k + 2} \le 1.5$
* Therefore either the approximation ratio for any reasonable algorithm on this class of problems must be less than or equal to 1.5, or what I think is the shortest superstring is not actually the shortest one.

Can someone either explain why this line of argumentation doesn't work, or say what the actual shortest superstring of this set is?

# Answer
A shorter superstring is $c(ab)^{k+1}c$, which has length $2k+4$.
> 1 votes

---
Tags: substrings
---


# Question
Title: Is every program is equivalent to a Push Down Automata?
so I was reading about stack-organized computer. Does a stack-organized computer implies that every program is equivalent to (and not more powerful than) a Push Down Automata?

# Answer
> 1 votes
No. The class of languages recognised by pushdown automata is the class of context-free languages, whereas the class of languages recognised by Turing machines is the class of Turing-recognizable (aka recursively enumerable) languages. All context-free languages are recognisable but the converse does not hold.

---
Tags: automata
---


# Question
Title: How to compare n number of m-dimensional points among one another with minimum time complexity?
Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all points among one another based on their values in corresponding dimensions ? Aim is to have minimum time complexity . (Practically n \>\> m ). The mentioned comparison is carried out to check whether points are ***mutually non-dominated*** or not. Example :

1. A(4,1) and B(5,6) -\> B dominates A since (5\>4) and (6\>1) . Therefore, A and B are ***not mutually non-dominated***.
2. C(4,1) and D(2,3) -\> D doesn't dominate C ,since (3\>1) but (2\<4) . Similarly C also doesn't dominate D ,since (4\>2) but (1\<3) . Therefore, C and D ***are mutually non-dominated***.

(***Note : In general, if (X\>=Y) -\> X dominates Y*** )

***Goal*** is ***to check for non-dominance among all possible combinations of points from the given set of points with minimum time complexity*** . With four points A, B, C, D possible combinations are AB, AC, AD, BC, BD, CD . ***If ALL of these six combinations are mutually non-dominated , then it can be concluded that given set of points are mutually non-dominated, else dominated***.

***Input :*** Set of points, ***Task :*** Check for non-dominance among all possible combination of points from the given set of points , ***Output :*** If ***ALL combinations*** are mutually non-dominated , print ('set of points are mutually non-dominated') . Else print ('set of points are not mutually non-dominated') .

I have taken a 2-D array for this purpose . For n points which are m-dimensional , I have used a (n * m) matrix and compared each row with every other row to check for non-dominance among rows. Suppose if points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4) , then matrix is : x\[4\]\[4\] = { {4,1,1,1}, {3,2,1,1}, {2,3,3,3}, {1,4,4,4} } . Here the time complexity is : **O(m * n * n)**.

(***Note :In this method , each row of matrix is representing one point*** )

**Is there any better approach which results lesser time complexity ?**

# Answer
> 1 votes
So you suggested the basic technique of checking all pairs which is $O(mn^2)$. Here are some things you can try first, at lower complexity, before falling back to an approach with a similar worst-case bound but likely better constants.

We represent each point $p\_i = (x^i\_1, \dots, x^i\_m)$.

Then clearly there is a dominated pair if $\min\_i \max\_j x^i\_j \leq \max\_i \min\_j x^i\_j$. The time to evaluate this is $O(mn)$.

Next, we sort the points $m$ times, by each dimension. Let $r^i\_j$ and $R^i\_j$ be the indexes at which $p\_i$ appears in each list (in range $\[0,n)$), where the $r$ values have tie-breaks resolved down and $R$ values have tie-breaks resolved up, respectively. In other words, considering the values $3, 5, 5, 6$. Then the $r$ and $R$ values for the two points having $5$ would be $1$ and $2$. The time to evaluate this is $O(mn \log n)$, before we check conditions.

If $\min\_i \max\_j R^i\_j \leq \max\_i \min\_j r^i\_j$, then there is a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Next, let $w\_i = \sum\_j r^i\_j$ and $W\_i = m(n-1) - \sum R^i\_j$. Note that $w\_i$ is an upper bound on the number of points that can't dominate $p\_i$. Similarly, $W\_i$ is an upper bound on the number of points that $p\_i$ can't dominate. Thus, if $\min\_i w\_i \< n - 1$ or $\min\_i W\_i \< n - 1$, then there must be a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Finally, as a fallback, for each point $p\_i$ we know there are at most $\min\_j R^i\_j$ points which $p\_i$ can dominate. Thus, knowing which list each $p\_i$ obtained its minimum $R^i\_j$ can give us a shorter list of points to check. The time here is still $O(mn^2)$ in the worst case, but the constant will be better than all pairs.

---
Tags: complexity-theory, algorithm-analysis, time-complexity, data-structures, big-o-notation
---


title: Summing $1,3,5,\ldots$

text:
# Question
Title: Summing $1,3,5,\ldots$
I solved a recurrence to get the formula $T(n) = \sum\_{i=1}^{k}2i+1$ for $k = \frac{n-1}{2}$, namely

$$ T(n) = 1 + 3 + \dots + (n-4) + (n-2) + n, $$

but I'm not sure how to finish off the problem by writing the summation and solving for the complexity.

# Answer
Perhaps this will help:

* $1 = 1$
* $1 + 3 = 4$
* $1 + 3 + 5 = 9$
* $1 + 3 + 5 + 7 = 16$
* $1 + 3 + 5 + 7 + 9 = 25$

Can you recognize the sequence $1,4,9,16,25$?

To prove the corresponding formula, use the following idea: $$ 1 + 3 + 5 + 7 = \frac{1+7}{2} + \frac{3+5}{2} + \frac{5+3}{2} + \frac{7+1}{2}. $$
> 1 votes

# Answer
If we define $\begin{cases} S(n)=\sum\limits\_{i=0}^n i \\ T(n)=\sum\limits\_{i=0}^{\lfloor n/2\rfloor} (2i+1)\\ U(n)=\sum\limits\_{i=0}^{\lfloor n/2\rfloor} (2i)\end{cases}$.

1. Find (or recall) a closed-form expression of $S(n)$
2. Express $U$ in terms of $S$ then derive a closed-form solution for $U$
3. Conclude using the fact that $S(n)=T(n)+U(n)$.
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: NP-completeness of a problem with pretty fast algorithm
Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?

# Answer
> 2 votes
Yes, such problems can be NP-complete.

Consider classical NP-complete graph problems like clique.

Clique has an $O(2^n)$ time algorithm, where $n$ is the number of vertices. However the input for clique is the adjacency matrix of the graph, which has $n^2$ bits. Therefore when the size of input is measured in bits, clique has an $O(2^\sqrt{n})$ time algorithm, which is $O(2^{\alpha n})$ for any positive $\alpha$.

---
Tags: algorithms, complexity-theory, time-complexity, np-complete, np
---


# Question
Title: Uniqueness of non-dominated two-dimensional points
This question is a nice variant of How to compare n number of m-dimensional points among one another with minimum time complexity? for two dimensions.

We say point $p\_i=(x^i\_1, x^i\_2)$ dominates point $p\_j=(x^j\_1, x^j\_2)$ if $x^i\_1 \geq x^j\_1$ and $x^i\_2 \geq x^j\_2$. Prove that if in a set of $n$ points there are no pairs such that one dominates the other, that the points can be ordered such that one dimension is strictly ascending and the second is strictly descending.

# Answer
> 1 votes
For $n=1$ the statement is trivially true. Otherwise $n \> 1$.

Sort the points in each dimension in ascending order. Let $r^i\_1, r^i\_2$ be the rank of point $i$ in each dimension, rounding ties down. (Thus if there is a duplicate value (1,2,2,3) we take the index of the first appearance in the list). We use 0-based indexing.

First we note that for a point $p\_i$ that $w\_i = r^i\_1 + r^i\_2$ gives an upper bound on the number of points that can't dominate $p\_i$. Therefore, by a counting argument, if $w\_i \< n-1$ there must be a point that dominates $p\_i$.

We will now assume that we have a set of points that doesn't have a dominated pair. For convenience, we rename all the points such that they are ordered in the first dimension, thus $p^0\_1 \leq p^1\_1 \leq \dots p^{n-1}\_1$.

We will now prove that $r^i\_1 = i$ and $r^i\_2 = n - 1 - i$.

Clearly $r^0\_1 = 0$. Therefore, $r^0\_2 = n-1$, otherwise $w^0 \< n-1$, and there is a point dominating $p\_0$. Since $r^0\_2 = n-1$ there is no point having the same value in the second dimension (otherwise, $r^0\_2 \< n-1$).

Assume that we have proved for the first $j$ points, we now prove for $j+1$. Note that since each of the first $j$ points have $r^i\_2 = n-1 - i$, this means that there are no other points having those rankings. Since the points are in ascending order in the first dimension, $r^{j+1}\_1 = j$ or $r^{j+1}\_1 = {j+1}$. Let us assume by contradiction the former. Therefore, since there are no dominated pairs, we have that $r^{j+1}\_2 \geq n - 1 - j$, which is a contradiction (to no other points having those rankings). Therefore, $r^{j+1}\_1 = {j+1}$ and since there are no dominated pairs, $r^{j+1}\_2 = n - 1 - {j+1}$, and no other point may have that value.

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


title: Reactiveness, cpu and caches

text:
# Question
Title: Reactiveness, cpu and caches
I was messing around with a reactive-based frameworks and found it very expressive. Unfortunately, most of them are using techniques that are not very efficient on CPU cashing mechanism such as calling indirect code, and traversing sometimes big collections of subscribers, some of which are readonly, but some can mutate them. That made me thinking of some optimizations that could be implemented : for example, you can imagine that when a core encounters an object that broadcast changes, which is implemented as calling indirect functions, the cpu may miss that data and spend hundreds of cycles loading necessary information. That makes some potential application domains to not be populated with reactive approaches. So my question is that if it would be possible to make it such that cores can be delegated execution of such code in parallel? Or am i mistaken and this kind of code could still be efficiently processed due to all speed-up tricks in modern cpus?

And if the former is true, how to make cpu cores signal they companions in multiprocessor cpu to load pieces of data so they handle them concurrently?

# Answer
CPUs are developed with typical code in mind. For example, indirect function calls are no problem - the destination of such a function call will be *predicted*, just as we do with branch prediction.

Remember that "hundreds of cycles" are only "tens of nanoseconds". Typically, 3,000 cycles is just one microsecond. So if a programming pattern wastes "hundreds of cycles", that's no big deal and no reason not to use that pattern. "Traversing big collections of subscribers" - there are efficient methods for doing so.
> 1 votes

---
Tags: cpu-cache, cpu
---


# Question
Title: Minimum number of edges to remove to disconnect two node sets $A$ and $B$ in a directed graph
We have directed graph $G$ (not necessarily a DAG), two disjoint sets $A$, $B$, of vertices.
I need to plan an algorithm returning the minimum number of edges that need to be removed, such that there will be no path from any node in $A$, to any node in $B$ and vice versa.

I had the idea using max flow min-cut to find the minimum number of edges needing to be removed such that there won't be a path from $A$ to $B$, and then using the algorithm again on $B$ (so there won't be a path to $A$).
The problem is that the sum of these minimum number of edges isn't necessarily the "global" minimum.

Does there even exist such an algorithm running in polynomial time?

# Answer
You could try reducing your problem to the directed $s$-$t$ cut problem.

That is, given an instance $G=(V,A)$ of your problem, construct a graph $H$ that is initially a copy of $G$. Then, add to $H$ two new vertices $x$ and $y$, add an arc from $x$ to each $a \in A$ and from $y$ to each $b \in B$; all with a large weight (say $m+1$, where $m = |A|$). The intuition is that an $s$-$t$ cut of $H$ will never use any of the arcs originating from $x$ or $y$ since they are so heavy, but instead only use arcs present in $G$.

You should try to formalize this intuition, i.e., (i) show that the reduction is correct and (ii) show that there is an efficient algorithm for directed $s$-$t$ cut. If both check out, you are done.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Checking disjointness between subsets of a poset
If there is a poset $(P, \le)$ and two sets $X \subseteq P$ and $Y \subseteq P$, and we have a way $f : P^2 \to 2$ to efficiently compute for any $(x, y) \in P^2$ whether there exists a $z \in P$ such that $(x \le z) \wedge (y \le z)$, we want to return $\mathbf{T}$ if there exists a pair $(x, y) \in X \times Y$ such that $f(x, y) = 1$ and $\mathbf{F}$ otherwise, using the fewest possible number of calls to $f$ and $\le$.

# Answer
Without further information, you can't do any better than $O(n^2)$ queries to $f$, where $n=|X|+|Y|$. There is a simple adversary argument.

Imagine you have an algorithm that uses $o(n^2)$ queries. Consider running it on a set $X,Y$ chosen so that $f(x,y)=0$ for all $x \in X, y \in Y$. If the algorithm is correct, the algorithm must return F on this input. Since the algorithm runs in $o(n^2)$ time, there must exist some pair of elements $x\_0,y\_0$ that was never queried. Now run the algorithm on a pair of sets $X,Y$ chosen so that $f(x\_0,y\_0)=1$ but $f(x,y)=0$ for all other pairs $x,y$. We see that $f$ always returns 0 during this execution, too, so this execution must follow exactly the same path as the first execution, and thus must also return F on this input. However, returning F on this input is incorrect. Therefore, there is no algorithm that takes $o(n^2)$ time and is always correct.
> 1 votes

---
Tags: lattices
---


# Question
Title: Is call stack compile time or runtime detail?
I'm sorry if the question is quite naive, but I don't understand if a call stack is a **language** implementation detail or it depends on OS?

What I'm trying to understand is what decides how to store local variables and parameters of a function - the language's compiler or OS while running the application? Is it possible to write a C compiler, let's say, for Windows so that it won't be stack based? Or the language syntax dictates us that it must be stack-based language?

Sorry if I say something wrong, just trying to get the basic idea how everything works.

# Answer
> 2 votes
The architecture of a computer is where concepts like "heap" and "call stack" originate from. If you take a look at the C standard (http://www.iso-9899.info/wiki/The\_Standard) you won't find anything about the stack or heap.

Compilers for a language like C can implement the specification in a number of ways in order to target specific architectures; even ones where memory is not organized in a stack, such as a "LISP cpu" (for example Sussman and Steele's: https://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf?sequence=2) where memory is organized as linked lists.

Of course a language specification *could* define these things, but I am not aware of any language which goes so far. (The closest I can think of is forth.)

Operating systems and libraries can abstract away some of the details of the underlying architecture via system calls and apis.

# Answer
> 1 votes
The use (or not) of a stack is strictly a matter of the language's implementation. E.g. FORTRAN is (was?) carefully defined so that no recursion is allowed, and no stack is needed. If your FORTRAN compiler uses a stack (and allows recursion) or not is anybody's guess. If your CPU sports a stack, chances are your FORTRAN uses it (as it is the machine's standard/efficient way to manage routine calls). Lisp introduced recursion all over the place, even on machines that don't handle stacks natively.

The machine stacks you see in current CPUs were defined precisely to support Algol (and Pascal, and C, and ...) type languages with recursion easily (and efficiently).

The operating system has no say either way. And shouldn't, it better stay out of the user program's hair as far as possible.

---
Tags: compilers, stacks, memory-allocation, c
---


# Question
Title: Do compilers of high programming languages always compile them directly to machine code?
As an amateur Bash/JavaScript scripter who never wrote one sentence in Assembly, I ask:

Do compilers of high programming languages always compile them directly to machine code, or are there cases when a compiler of some high programming language compiles it to assembly (and then assembler will assemble input to machine code output)?

# Answer
> 4 votes
I've seen compilers that compile directly to object code.

I've seen compilers that compile to assembler code.

I've seen compilers that compile to byte code for a virtual machine.

I've seen compilers that compile to bit code which is intended to be further compiled to code for slightly different processors.

I've seen compilers that compile to a different language.

I've seen compilers for Javascript specifically that start interpreting code, then compile it very quickly to not very good code, then compile it carefully to reasonably good code, then compile it with a highly optimising compiler to very fast code, all depending how often some code is executed.

# Answer
> 0 votes
One popular way to get a language quickly off the ground is to compile to a high-level language, like C. It gives you portability for free, and you can leverage the extensive optimization of the C compiler to get good object code.

An interesting artifact from the early Unix times is RATFOR, a preprocessor for a somewhat-C-like language to FORTRAN (a prehistoric dialect with no decent control structures). There is a f2c compiler for FORTRAN 77 to C.

Most "scripting" languages compile to a virtual machine code, which is interpreted. Some (e.g. modern Java virtual machines) translate often used stretches of code to machine code on the fly (Just In Time compilation, JIT).

---
Tags: compilers, assembly
---


title: Confused on Variational AutoEncoder

text:
# Question
Title: Confused on Variational AutoEncoder
I'm a bit confused on how Variational Autoencoders are trained. In particular I'm confused on how the latent variable is generated for each input.

My questions are as follows:

1. When running stochastic gradient descent does the sampled latent variable stick with the data point during the entire run or does a new latent variable get sampled each time descent is run?
2. If running batch or full gradient descent, each data point gets its own set of sampled latent variables right?
3. How do you check for convergence? Assuming the latent variable is sampled at each iteration, it's not clear to me how you can evaluate if you have converged or not given the stochastic nature of the performance function.

# Answer
VAE's have an encoder. The encoder maps an input to a latent vector. The latent vector doesn't "stick". Instead, in each iteration, we use the encoder to map to a latent distribution, sample from that latent distribution, then use the decoder to map to a reconstruction, and compute the loss. Yes, each data point is mapped to its own latent vector. Yes, you run the encoder anew and sample anew for each point and each iteration of training.

You check for convergence in the standard way for any neural network: you look for the value of the loss function to plateau.
> 0 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Given an array with N elements and an array of N indices find the lowest possible amounts of swaps
So I have two arrays $d$ and $s$ with size $n \in \mathbb{N}$. Array $d$ contains the elements and array $s$ contains indices. Array $s$ contains all numbers from $0$ upto $n$ with no duplicates.

The indices in $s$ indicate where the elements in $d$ need to go. So the element at $d\[q\]$ needs to be at $d\[s\[q\]\]$ where $n \> q \geq 0$.

The goal is to find the minimum amount of $q \in \mathbb{N}$ swaps such that the after all swaps are performed the above holds.

# Answer
> 0 votes
Hint: Assume you have four items that are in order a,b,c,d but you want them in order b, c, d, a. How many swaps do you need and why?

Then you generalise this to the whole array.

---
Tags: algorithms, optimization, sorting
---


# Question
Title: Minimum number of cans needed to carry all used water
so I've just attempted an online technical test. It was on hacker rank however I'm sure leetcode usually has the same (and more) so thought i'd ask.

I could not think of a nice solution and cannot find a leetcode exercise that matches what was being asked so I'm here for someone to point me in the right direction.

The problem:

Someone has to carry water in cans and can only carry one can at a time. I was given 2 arrays, one of which had the total amount of water each can can hold and the second has the amount of water that was currently used by each can. I had to find the minimum number of cans needed to carry the entirety of the used water.

An example input was:

Total = \[ 3 , 5 , 3 , 5 , 5\]

Used = \[ 3 , 2 , 1 , 3 , 1\]

So can \[0\] has a total of 3 and is currently full. Can \[1\] has a total of 5 but only 2 is being used etc etc. I had to find the minimum amount of cans needed in order to be able to carry all of the water. **The solution in this example was 2** since you could take the water from can \[0\] and put into can \[1\] to fill it up. You could then take water from cans \[2\] and \[3\] and put into can \[4\] therefore only needing cans \[2\] and \[4\] to carry all the water.

Does anyone recognise this question and could you be able to point me in the direction of the problem on leet code or hackerrank? I cannot come up with a nice algorithm myself.

# Answer
Okay so after a nudge from @John in comments, I think this algorithm will work.

1. Count all elements in the Used array ( will get us 10 )
2. Sort the Total array
3. Can the iterate down the sorted Total array and take away each iteration from the total until its equal or less than 0.

This will only work on a sorted array since this is the only way of knowing that the and I quote 'global optimum can be arrived at by selecting a local optimum'. I.e we know that the next item is the biggest therefore it must be the biggest can. Need to read up on greedy algorithms and what actually makes this one greedy but I think this is the reason
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?
Consider the following algorithmic problem: Given a list of strings $L = \[s\_1, s\_2, \dots, s\_n\]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of length at maximum $m$, where $m \<\< n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| \<\< n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a sub-string of $y$ is much smaller than $n$.

A trivial algorithm would be this:

```
1. foreach x in L:
2.   foreach y in L:
3.      if x is substring of y:
4.         OUTPUT x,y

```

However, this has complexity $O(n^2 \cdot m)$ \- I am curious to know whether there is a faster algorithm?

***Edit***: As pointed out in the comments, there can be at most $n^2$ such pairs, so I don't see how there can be an algorithm faster than $O(n^2)$. However, I was wondering if there is something like a $P-FPT$ algorithm where the squared complexity is dependent on the number of output pairs, rather than $n$? Or at least an algorithm that reduces the complexity to something better than $O(n^2 \cdot m)$.

# Answer
> 5 votes
This can be solved with Aho-Corasick algorithm in $O(nm + Mm)$ time, where $M$ is the number of pairs outputted.

First build the Aho-Corasick automaton for the set of strings in $O(nm)$ time. Then run each string through the automaton - this takes $O(nm)$ time for running the strings through the automaton and $O(Mm)$ time for outputting the matches because the same string can match $m$ times in the worst case. (For example `ab` matches `ababab` 3 times.)

---

This can be improved to true linear $O(L + M)$ time, where $L$ is the total length of the strings and $M$ is the number of matches:

When running the strings through the automaton, store for each node of the automaton the index of the previous string for which this node was visited. When outputting the matches, stop following the dictionary links if the link leads to a node that has already been visited for this string - you have already outputted all matches that are upwards from that node. Now each match gets outputted exactly once, and we traverse dictionary links only when new matches are outputted.

---
Tags: algorithms, strings, substrings, string-matching
---


# Question
Title: Can I use the following method to prove an algorithm is correct?
I'm trying to show that a solution I have obtained via an algorithm is correct. The way I plan on doing this is first by showing that an optimal solution does indeed exist. Then, I plan on showing that every other solution that is not the solution provided by my algorithm cannot be optimal. Finally, I show that the solution I have cannot be improved in the same way as any other solution.

Is this enough to show that my algorithm is optimal? In this case I am avoiding doing an "exchange argument" a la greedy algorithms. In fact, I don't really prove anything about how my solution is an improvement of the other ones, but simply that all of the other ones can be improved, and given that an optimal solution exists, the one I have must be it because it cannot be improved in the same way that the other ones can.

# Answer
> 16 votes
I am rather surprised that you raised this question since the meticulous and enlightening answers you have written to some math questions demonstrate sufficiently that you are capable of rigorous logical deduction. It seems that you became somewhat uncomfortable when you stumbled upon a new and unorthodox way to prove an algorithm is correct.

Believe in yourself. Believe in logic.

Yes, I believe you have shown your algorithm is correct. To be absolutely clear, suppose you have shown all of the following.

* An optimal solution exists.
* Your algorithm provides a solution and only one solution.
* Every solution that is not the solution provided by your algorithm cannot be optimal.

Then your algorithm must provide an optimal solution. The implication is just simple logic.

You do not even need to show that solution provided cannot be improved in the same way as any other solution.

# Answer
> 6 votes
You have: There is an optimal solution, and any solution not found by your algorithm is non-optimal. It follows that the optimal solution is found by your algorithm, so the third part is not needed.

For problems with two or more optimal solutions you won’t be able to show the second part unless your algorithm finds *all* optimal solutions.

# Answer
> 2 votes
> but simply that all of the other ones can be improved, and given that an optimal solution exists, the one I have must be it because it cannot be improved in the same way that the other ones can.

It does seem that there's something slightly to patch up here. Do you have a proof that this procedure for making an improvement *always* makes an improvement when one is available? If you have such a proof, then simply showing that the procedure makes no improvement to your solution is enough to qualify the solution as optimal, and the only reason to even refer to other solutions is to show that yours is a *unique* optimum.

If you don't have such a proof, then you need to prove that your solution is actually optimal and not just a point where your "improvement procedure" fails to make progress. I think your intuition is correct that if every other solution can be improved, then the one that can't is an optimum, but it may fall short of a really rigorous proof without an appeal to something like the contraction mapping theorem.

In particular, if you could show that your "improvement procedure"

1. Never actually produces a worse solution, and
2. Always produces a solution that is *nearer* by some metric to your chosen solution than the one it was given as input

then you would be showing that your solution is a fixed-point of the improvement procedure and that every sequence leading to it is monotone, which should prove, using monotone convergence, that your solution is optimal.

---
Tags: correctness-proof
---


# Question
Title: Algorithm for finding the best “route” of tasks
I have the following problem: Let's say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every person can move x coordinates per second. Every task has:

* A coordinate where it can be completed (for example (40/50))
* A importance value ranging from 0 to X (for example importance = 5)
* A time that is needed to complete this task

Also, some tasks can only be done if a certain other task has already been completed.

Now comes the tricky thing: The group has a certain time, in which they can complete tasks. They now need to choose which tasks they want to complete, the goal is that the summarized "importance value" of the completed tasks is as high as possible. The group is also allowed to split up.

---

I tried to bruteforce it, but that didn't work out. There are around 11 tasks usually and 4-6 can be done, resulting in up to a million and something possiblities. Also, I had a solution without calculating the time needed to travel between the points which was basically calculating a importance per time value and just doing the tasks based on this value... which won't work for the full problem.

# Answer
> 1 votes
If you have just one person to complete the tasks, this is the (in)famous Travelling Salesman Problem (TSP), which is NP-complete, so an efficient exact algorithm is a very remote possibility. Unless your problem is quite small, you'd have to settle for approximate solutions. There are algorithms that can solve enormous instances of TSP in (somewhat) reasonable time, but I have no pointers at hand.

# Answer
> 0 votes
Depending on how you want to model the problem, you can approach it in several ways. Since it seems like you are working with an imaginary 2D plane I will start with the most relevant options.

**Arrange waypoints.** Obviously if X comes before Y, then with lower precedence if X is easier than Z. You will need a difficulty function which will depend primarily on distance to the waypoint, which means that you will probably need to calculate the path from every other possible waypoint and then calculate according to the path. (Though I may be missing some nice method to solve this).

**EDIT:** To clarify, you need to determine the best order of steps, first in relation to one another (if Y requires X), and then in order of optimal path (see below). This isn't an algorithm, it is a necessary prerequisite for further calculations. If you don't do this then the brute force method below will be extremely resource hungry.

**A\* path finding (to calculate difficulty from each 'end point').** By 'end point' I mean the initial location and the location of every other objective. This method is inefficient, especially when you have lots of waypoints, but it has obstacle navigation built in if you need it, and once each waypoint has a path length value relative to every other waypoint, you can use simpler functions to approach the objective sequence.

**EDIT:** This is useful instead of drawing a direct path in the case of obstacles. It will calculate the shortest distance from point A to point B with and without obstacles in the way. WIKIPEDIA

**Brute force paths.** This is a starting point for what should be a better algorithm. Calculate every possible configuration (I would use a branching method to simplify the concept) and remove less optimal ones after calculating scores.

```
def NextStep(Plan,Steps,ID): ##Warning: written at 5AM. Run at own risk.
    if len(Steps)==0:
        print "Possible plan: ",ID; ALL_THE_PLANS.append(Plan);
        return;
    for s in Steps: ##Uncomment next line for multiple people.
      #for ppl in PEOPLE:
        temp_plan = Plan; temp_steps = Steps; #Use ID.copy() for objects.
        temp_id = ID+"Then "+ppl+" does "+s;
        temp_plan+=Steps[s]; temp_steps.replace(Steps[s],""); #Or .remove
        NextStep(temp_plan, temp_steps, temp_ID);
        #This will recurse until all possible arrangements are calculated.

```

Once you have a list of all paths you can remove those which break the rules (ie Y before X). Note that it helps to do this BEFORE calculating the paths, but it is still very slow and you should try to rewrite the above code to skip illegal plans.

```
PPL = ALL_THE_PEOPLE_IN_THE_GROUP()
for P in PLANS:
    p = PLANS[P] ##Just makes my job easier...
    STEPS = p.Objectives ##...And the code looks nicer.
    ##Assume that all PPL have .Location == START_POINT
    for O in STEPS:
        p.DIST+=AStar(PPL[O.Person].Location,OBJS[O].Location).Dist;
        #Add the distance that the person will travel from their last
        # location to the objective to the total distance of this plan.
        PPL[O.Person].Location=OBJS[O].Location;

```

Now just use some imagination... Get the PLAN with the smallest DIST.

**Other approaches.** You could also model the problem mathematically and try using other optimizing methods here. I'm not sure how applicable any of these are since it is 5AM and I can't think of ways to remodel your problem, but I will make you aware of them in case you aren't in the hopes that someone benefits.

* Neural networks
* Finite State Automata
* Genetic algoritms
* Minimax (probably only applicable in a 2-player version)

Hope I could help!

---
Tags: algorithms, routing
---


# Question
Title: Algorithm for finding the limit of unkown function
I have a case of costly calculations method like this:

```
Input -> Output
0 -> 8
8 -> 9
9 -> 9.5
9.5 -> 9.6
9.6 -> 9.65
9.65 -> 9.654

```

I use the output for the next input so this way im trying to find where the output exactly matches the input or is a tiny fraction smaller. The goal of the algorithm is to find the smallest X=Y or X\>Y where (X-Y) \> 10^(-10).

However since the method for calculations is costly I'm looking for an efficient way to reduce the amount of time I'm calling the method, but still retain for example the accuracy of 10 fractional digits.

Some additional Caveats: Output is not always increasing by increasing the Input. It might hop around the limit from both sides. Also increasing the Input value more drastically might change the value the Output approaches to which is not the desired outcome.

Since I'm posting here first time i would be glad if someone tagged this question with proper tags, since honestly i don't know which tags to use.

# Answer
> 2 votes
This is some form of fixed point iteration (you are going $x\_{n + 1} = f(x\_n)$, and looking for $x^\* = f(x^\*)$). If you know that the convergence is linear (i.e., $e\_{n + 1} \approx C e\_n$, where $e\_n$ is the $n$-th error), you can accelerate the convergence by Aitken's $\Delta^2$ method. Say you have $x\_0$, $x\_1$ and $x\_2$. A (hopefully much better) approximation is given by:

$\begin{align\*} x^+ &= x\_2 - \frac{(\Delta x\_1)^2}{\Delta^2 x\_0} \\ &= x\_2 - \frac{(x\_2 - x\_1)^2}{x\_2 - 2 x\_1 + x\_0} \end{align\*}$

Start with $x\_0 = x^+$ and compute new values for $x\_1, x\_2$. Repeat until satisfactory precision.

# Answer
> 1 votes
You appear to be looking for a fixed point of a function $f(x)$. Let $g(x)=f(x)-x$. Then $x$ is a fixed point of $f$, if and only if it is a root of $g$. Therefore, you can use any standard root-finding algorithm with $g$. For instance, if you have the ability to compute the derivative of $f$, you can use gradient descent; if you have the ability to compute the second derivative, you can use Newton's method; if you cannot compute the derivative of $f$, you can use the secant method or Brent's method. Those are just examples; there is a vast literature on root-finding.

---
Tags: algorithms
---


# Question
Title: Neural network game players and incremental updates
Neural networks in recent years have been successfully used for gameplaying. A difference between games and e.g. image processing is that the game boards get updated incrementally. Do any neural network implementations optimize for this fact?

For example, there are 361 squares on a Go board; in a typical turn, only one of those squares will change value. On the face of it, a program like AlphaGo could save time by not redoing the calculations from the other 360 squares each time it looks at a new board position.

On the other hand, if the calculations are being done on a GPU, this optimization involves moving away from the straight vector arithmetic that GPU's do so well, which would offset the efficiency gain.

On the third hand, the potential efficiency gain would become larger as you move to more complex games; how many variables are there in StarCraft?

Has anyone ever done this optimization, or studied it and given reasons for not doing it?

# Answer
The AlphaGo algorithm does not benefit from this kind of optimization. It's hard to share an intuition for why without diving into the details of the algorithm, but at a coarse level: a single small change to the board can make a dramatic change to the strategic nature of the position, so it's not clear that one can reuse calculations effectively. In particular, it sounds like you are assuming that AlphaGo does some computation separately for each square of the board, so we could avoid re-doing the same ones for squares that haven't changed. However, that's not at all how AlphaGo works, so that kind of optimization is not applicable here.
> 1 votes

# Answer
Try changing your input in this case if you wanted to take only the difference of two states into consideration. Think of each rounds in a discrete manner, they will be of their own distinctive state if not encountered the exactly same configuration of the board beforehand.

What do you get? You get another set of states that takes differentiated states into account. So they are no different than the previous set of states, a raw states. It does not significantly change your problem but in a game where state changes are not substantial in each round, you might be able to get a slight advantage in input variable size.
> 0 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, board-games
---


# Question
Title: What kind of bigram probability smoothing is this?
I hope it isn't off topic but I need to understand this example. Given the corpus `12 1 13 12 15 234 2526` and smoothing factor of `k=1`. The example does the following operations:

Considers OOV(out of vocabulary) words and assigns them a zero times value, after that `k=1` is added to the times every words appears, to avoid zero probabilities. So the result of smoothing the bigrams probability will be:

$P(1|12)=(1+k)/(2+2+6\*k)=0.2$
$P(15|12)=(1+k)/(2+2+6\*k)=0.2$
$P(13|1)=(1+k)/(2+6\*k)=0.25$
$P(12|13)=(1+k)/(2+6\*k)=0.25$
$P(234|15)=(1+k)/(2+6\*k)=0.25$
$P(2526|234)=(1+k)/(2+6\*k)=0.25$

My question is, What kind of smoothing is this? shouldn't be for example like this?; $P(1|12)=(1+k)/(2+6\*k)=0.25$
Besides it also says "If OOV words appear, you need to use smoothing to return a value; $P(234|12)=1/((2/7)\*6+6)=0.1296$"

PS: I take this example from a small section of the translated version of this chinese webpage, it is just explaining a code implementation.

# Answer
This looks like it might be implementing Laplace smoothing (though I can't explain the extra +2 in the first two calculations).

There are many smoothing methods, e.g., Lidstone, Good-Turing, Kneser-Tey, Witten-Bell. You can also use interpolation and backoff to handle rare or low-probability events when computing conditional probabilities like this.
> 1 votes

---
Tags: machine-learning, probability-theory, natural-language-processing
---


# Question
Title: Are there any NP-hard problems for which the following statement is true:
$\overline{A} \le A\ and $ $A \le \overline{A}$

Is the following proof correct?

If $\overline{A} \le A \Rightarrow \overline{A} \in NP$ since A is NP-hard $ \Rightarrow A \in coNP$

Since $\overline{A} \le A$ and $A \in coNP \Rightarrow \overline{A} \in coNP \Rightarrow A \in NP$

$A \in coNP$ and $A \in NP$ iff $NP=coNP$

# Answer
> 2 votes
You are confusing NP and NP-hard in a couple places. For example, let $A$ be the problem of deciding ATL\*, which is 2EXPTIME-complete. $A$ is NP-hard and polynomial-time many-one reduces to its complement, but is neither in NP nor in co-NP by the time hierarchy theorem.

---

Recall that an NP-complete problem is one that is in NP and is NP-hard. For every NP-complete problem $A$, we have that $A$ is in co-NP if and only if NP = co-NP. Make sure you understand why: try proving the if direction (easy) and the only if direction (requires a little more thought). Here is the proof of the only if direction, if you get stuck:

> Suppose there exists an NP-complete problem X that is in co-NP. Since all problems in NP can be reduced to X, it follows that for every problem in NP we can construct a non-deterministic Turing machine that decides its complement in polynomial time, i.e., NP ⊆ co-NP. From this it follows that the set of complements of the problems in NP is a subset of the set of complements of the problems in co-NP, i.e., co-NP ⊆ NP. Thus co-NP = NP. (from Wikipedia)

---

Let $\mathbf{C}$ be any complexity class that is closed under complement and polynomial-time many-one reductions (such as PSPACE, EXPTIME, 2EXPTIME, etc.). Let $P$ be any $\mathbf{C}$-complete problem. Then its complement $\overline{P}$ is also $\mathbf{C}$-complete.

Proof:

> Suppose we are given some problem $Q \in \mathbf{C}$ and we want to reduce it to $\overline{P}$. Since $\mathbf{C}$ is closed under complement, we know that $\overline{Q} \in \mathbf{C}$ as well. Since $P$ is $\mathbf{C}$-complete, there is a reduction $\overline{Q}$ to $P$. But this reduction is *also* a reduction from $Q$ to $\overline{P}$: the accepting and rejecting instances are simply swapped.

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


# Question
Title: What is the difference between finite automata and finite state machines?
I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?

# Answer
> 14 votes
As far as I understand, both have "states", and "actions" that make the machine move from one state to another upon an input signal. Thus the conceptual ideas are the same. There is some difference in the details.

In FSM for circuit designs the input signal is mostly assumed to be a bit (binary), whereas in finite state automata one can have a general "abstract" alphabet of input symbols. Second, a FSM also generates an output, associated to the state reached, also binary. In automata terminology this 'extension' is called a Moore machine. Automata however have final (or accepting) states, that signal a favourable input read. Finally, FSM are mostly deterministic, i.e., for each input in a certain state there is one next state. In automata theory one also considers the nondeterministic variant where one might have choice in where to move.

# Answer
> 7 votes
Based on my experience as well as the Wikipedia article, there are several kinds of finite state machines, including

Some of the notions flying around differ mostly in motivation; some arose from language and/or computability theory, others from computer architecture.

Note that you can also change several paradigms to get automata that are, arguably, still finite-state automata, for instance

As you can see, vanilla finite automata as taught in TCS 101 is but one flavor of many, each with their own (more or less formal) definition.

# Answer
> 3 votes
Although the main idea on which they both rely on is same. Both use finite states and jump to another state as the input feed. However, FSM being a machine, like Full adder or SR flipflop has bits as input and output. Yeah, FSA also has bit output, 0 for non terminating state and 1 for terminating state, but it is an abstract mechanism and not seen. There is difference in the digraphs that is drawn to represent them. Beside that FSA is a logical and computation device while FSM is a digital logic device.

# Answer
> 1 votes
Based on the book, Introduction to Languages and the Theory of Computation, they are interchangeable terms.

> ... These are examples of a type of language acceptor called **a finite automaton (FA), or finite-state machine**.

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


# Question
Title: Show that if A is regular, then the subset containing only even language strings, is also regular
A language A, even(A) is the subset of A consisting of those strings in A of even length:

```
even(A) = { x∈A | |x| is even}

```

I need to use closure properties show that if A is regular, then even(A) is also regular.

Isn't that a definition called "A language is called a regular language if some finite automaton recognizes it", could prove even(A) is regular? How to use closure properties to prove this question?

# Answer
Could you make a FA that accepts all and only even-length strings? What do you know about the intersection of two regular languages?
> 2 votes

# Answer
You need to use one intersection operation. It is a known closure property that if two languages $A, B$ are regular, then the intersection $A \cap B$ will also be regular. In this case, $A$ is the given regular language. The other one, $B = \textrm{Even}(\Sigma^\*)$, is the language of all even-length strings. The language you want to prove is the language containing all the strings in $A$ AND having even length \[in $B$\].

It is easy to show that $B$ is regular as well. Its regular expression is `(..)*`, where the period is the metacharacter that matches any character in the alphabet.

Your language is equivalent to determining that $B$ is regular, and then stating that $A \cap B$ is also regular. However, determining the regular expression of the intersection, will take doubly exponential time to do so.
> 2 votes

# Answer
Be careful, $L\_1 \subseteq L\_2$ with $L\_2$ regular doesn't always mean that $L\_1$ is regular. For one example, pick $L\_1 = \\{a^n b^n \colon n \ge 1\\}$ (usually the first language proven non-regular), $L\_2 = \mathcal{L}(a^\* b^\*)$ (defined by a regular expression, thus regular).
> 0 votes

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