# Question
Title: Why does parallelising slow down this simple problem against looping through all the data?
I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn anything, just on the 4 CPUs of my Mac.

I created a task to add 100 to every element in a 500,000 element list. To my surprise, I noticed that batching this data and using Python's parallelising tools to implement this actually slowed it down hugely, compared to just looping through the 500,000 elements and adding 1.

I'd like to understand why.

Consider the two methods for doing this task below:

```
import numpy as np
from sqlitedict import SqliteDict
from multiprocessing import Pool, cpu_count
from gensim.corpora.wikicorpus import init_to_ignore_interrupt
from itertools import zip_longest
import timeit as t

def grouper(iterable, n, fillvalue=None):
    args = [iter(iterable)] * n
    return zip_longest(*args, fillvalue=fillvalue)

class Add100ToData():
    def __init__(self):
        self.data = [np.random.randint(0, 100) for _ in range(500000)]

    def add100(self):
        for i in range(len(self.data)):
            self.data[i] = self.data[i] + 100
        return self.data

class Add100ToDataMultiprocess():
    def __init__(self):
        self.data = [np.random.randint(0, 100) for _ in range(500000)]

    def process_batch(self, batch):
        new_data = []
        for i in batch:
            new_data.append(i + 100)
        return new_data

    def add100(self, batch_size):
        processes = cpu_count()
        pool = Pool(processes, init_to_ignore_interrupt)
        gr = grouper(self.data, batch_size)

        for batch_result in pool.imap(self.process_batch, gr):
            count = 0
            for i in batch_result:
                count += 1
                self.data[count] = i
        return self.data

if __name__ == "__main__":
    add1 = Add100ToData()
    start = t.default_timer()
    final1 = add1.add100()
    end = t.default_timer()
    print("Looping run-time: {:.2f} seconds".format(end - start))

    add2 = Add100ToDataMultiprocess()
    start = t.default_timer()
    final2 = add2.add100()
    end = t.default_timer()
    print("Looping run-time: {:.2f} seconds".format(end - start))

```

This gives me:

```
Looping run-time: 0.13 seconds
Multiprocessing run-time: 1.23 seconds

```

Why is there an improvement in simply looping through the data as opposed to parallelising and batching with simple tasks?

When I was doing this for a far more labour-intensive task (one task was transforming 800,000 sentences into their 300-dimensional word embeddings, and another was applying a classifier to these), I gained huge speed improvements using 32 CPUs on the Google cloud, with a very similar code structure to this.

Can someone help me to understand why I'm not getting speed improvements here?

# Answer
Parallelism has costs. The processes have to be scheduled, communicate with each other, manage resources, etc. In return you can do multiple things at the same time.

When you have a lot of slow tasks that can be done independently, parallel processing will speed things up a lot.

But when you try to parallelize an easy task it might take longer to handle the overhead than to actually do the work. That seems to be the case here.
> 3 votes

---
Tags: runtime-analysis, efficiency, cpu, python, multi-tasking
---


# Question
Title: Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles
Given a weighted complete bipartite directed graph K\_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m\*n) when there exist simple cycles with negative weight?

For general graphs this problem is NP-complete (Finding the lowest-weight negative cycle in a weighted digraph). Using Bellman-Ford it is possible to find a cycle with negative weight if such a cycle exists, but this algorithm gives no guarantee that it is the most negative cycle.

In total there are

simple cycles in this graph, so checking all of them would already give a subexponential algorithm. But can this be reduced to a polynomial time algorithm?

Some assumptions I can make:

* The absolute value of the weights are bounded by a constant C.
* There exists a negative simple cycle and all negative simple cycles visit at least 4 nodes.

Thanks.

# Answer
> 1 votes
No.

That is, there is no polynomial time algorithm in $m\times n$ that can find a simple cycle with minimal weight in any given weighted complete bipartite directed graph K\_$\\{m, n\\}$ in the sense that it is a NP-complete problem.

To prove it, let us reduce the undirected Hamiltonian cycle problem, one of Karp's 21 NP-complete problems, to the current problem by a polynomial-time reduction.

Let $G$ be an undirected graph with vertices $V$ and edges $E$. For each vertex $u$ in $G$, we create two new vertices, $u\_{in}$ and $u\_{out}$. Let $V\_{in}=\\{u\_{in}|u\in V\\}$. Let $V\_{out}=\\{u\_{out}|u\in V\\}$. Let $K$ be the complete bipartite digraph connecting the vertex sets $V\_{in}$ and $V\_{out}$. For every vertex $u\in G$, both edges $(u\_{in},u\_{out})$ and $(u\_{out}, u\_{in})$ in $K$ weigh 0. If edge $(u, v)$ is in $G$, then the both edge $(u\_{out},v\_{in})$ and edge $(v\_{out},u\_{in})$ in $K$ weigh $-1$. Any other edge in $K$ weigh $|V|$. $K$ with its edge-weights thus defined is a weighted complete bipartite directed graph with $|V|$ vertices in each of its two vertex sets (that is, $m=n=|V|$ for $K$).

Each simple cycle in $G$ corresponds to a simple cycle in $K$ with the same weight in the natural way as illustrated by the following example. A cycle $a, b, c, a$ in $G$ corresponds to the cycle $a\_{in}, a\_{out}, b\_{in}, b\_{out}, c\_{in}, c\_{out}, a\_{in}$ in $K$. In particular, a Hamiltonian Cycle in $G$ corresponds to a simple cycle in $K$ of weight $-|V|$. Conversely, it is easy to see that a simple cycle of weight $-|V|$ in $K$ corresponds to a Hamiltonian Cycle in $G$ under the same correspondence. Note that a simple cycle of weight $-|V|$ in $K$ must be simple cycle of minimal weight in $K$.

Assume we can find a simple cycle $C$ of the minimal weight in $K$ by some algorithm. We can then check the weight of $C$. If the weight of $C$ is $-|V|$, the simple cycle in $G$ that corresponds to $C$ is a Hamiltonian Cycle. Otherwise, there is no Hamiltonian Cycle in $G$. So we have reduced the undirected Hamiltonian cycle problem to the current problem. We can see easily that this reduction is a polynomial-time reduction.

---
Tags: algorithms, complexity-theory, graphs, optimization
---


# Question
Title: Algorithm for using power series to numerically solve a partial differential equation given a boundary condition?
**Motivation:**

Following this discussion about using asymptotic expansions (i.e. polynomial power series) for numerically solving partial differential and algebraic equations (PDAE), I couldn't find any implementation of the method. So I'm thinking of implementing a SymPy function similar to Mathematica's `AsymptoticDSolveValue` (here) but for PDEs (here or here). So far I'm able to generate a symbolic multivariate polynomial given a list of non-negative integers `D=[d1,...,dm]` (here, here and here).

**Example:**

Now I'm able to use the symbolic multivariate polynomial to numerically solve a PDE. For example (from here) given the PDE:

$$\frac{\partial^2 u}{\partial x\_1^2} - \frac{\partial^2 u}{\partial x\_2^2}=0 \\, ,\tag{1}$$

and the boundary conditions:

1. $u(x\_1,0)=x\_1^2+x\_1\\, , \tag{2}$
2. $u\_{x\_2}(x\_1,0)=2x\_1+1 \\, , \tag{3}$

I can generate a 2D symbolic polynomial in Sympy:

```
from itertools import product
from sympy import IndexedBase, symbols, Poly
D = (5, 5) # 5 and 5 are just some random integers, any non-negative integer should do
d = len(D)
indices=list(product(*map(range, D)))
a = IndexedBase('a')
coeffs = {i: a[i] for i in indices}
vars = symbols(f'x1:{d+1}')
u = Poly(coeffs, *vars)

```

Equation 1 can be implemented as:

```
pde=u.diff(0,0).add(-u.diff(1,1))

```

Implying

$$j(j+1)a\_{i,j+1}=(i+1)(i+2)a\_{i+2,j} \tag{4}$$

The first boundary condition:

```
u.eval(1,0)

```

Implying

$$a\_{0,0}=0 \\, , \\, a\_{1,0}=1 \\, , \\, a\_{2,0}=1 \\, , \\,a\_{i,0}=0 \\, \forall \\,(2\<i) \tag{5}$$

and the second boundary condition

```
u.diff(1).eval(1,0)

```

giving

$$a\_{0,1}=1 \\, , \\, a\_{1,1}=2 \\, , \\, a\_{i,1}=0 \\, \forall \\, (2\<i) \tag{6}$$

Now from this point it is just a system of nonlinear algebraic equation of $a$s (in this specific case linear). Which should be solvable with other analytical/numerical methods.

**Question:**

I want to automate the process above. I want to have a function:

```
AsymptoticPdeSolve(eqns,fs,vars,D)

```

Where `eqns` is the set of symbolic partial differential expressions, `fs` are the set of functions we want to solve, `vars` are the variables and `D` is the dimension of our multivariate polynomials.

I would appreciate if you could help me know what is the best algorithm for this process. I will use an existing symbolic library/software like SymPy, so anything already existing doesn't need to be reimplemented.

**P.S.** Axiom-FriCAS has a `seriesSolve` function which source code can be found here. Also since I posted this question, Nicolas CELLIER was so kind to implement an early version in sympy which can be seen in this Jupyter notebook.

# Answer
> 1 votes
Instead of building a polynomial and trying to deduce the equation on the coefficients, you can just derive it directly from a general term coefficient

```
>>> i, j, x1, x2 = symbols('i j x1 x2')
>>> a = IndexedBase('a')
>>> u = Function('u')
>>> pde = u(x1, x2).diff(x1, 2) - u(x1, x2).diff(x2, 2)
>>> term = a[i, j]*x1**i*x2**j
>>> pdeterm = powsimp(pde.replace(u, Lambda((x1, x2), term)).doit())
>>> pdeterm
i*x1**(i - 2)*x2**j*(i - 1)*a[i, j] - j*x1**i*x2**(j - 2)*(j - 1)*a[i, j]

```

The PDE being identically zero means each coefficient of each x1, x2 term is 0.

```
>>> pdeterm.coeff(x1**i*x2**(j - 2))
-j*(j - 1)*a[i, j]
>>> pdeterm.coeff(x1**(i - 2)*x2**j)
i*(i - 1)*a[i, j]

```

This is the same as what you had above if you shift `i` and `j`

```
>>> pdeterm.coeff(x1**i*x2**(j - 2)).subs({j: j + 1})
-j*(j + 1)*a[i, j + 1]
>>> pdeterm.coeff(x1**(i - 2)*x2**j).subs({i: i + 2})
(i + 1)*(i + 2)*a[i + 2, j]

```

I'm not sure if there's an advantage to having them one way or another. For a general PDE, you'd want to write a function that does this automatically.

The boundary conditions can be managed in a similar way using `subs`.

You can then solve the system analytically with `solve` or numerically with `nsolve`.

---
Tags: algorithms, asymptotics, numerical-algorithms
---


# Question
Title: Finding missing edge weights in the context of minimum spanning tree
I came across following problem:

> **Problem 1**
> Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights $x$ and $z$, then what are $x$ and $z$?

The solution given was as follows:

> There are two ways to reach node $F$, one from node $A$, other from node $G$. Maximum weight of the edge in MST is smallest of two. Hence 11. Similarly there are four edges incident on node $B$, having weights $13,14,8,z$. If $z$ is included in MST, then it should be at least $min(13,14,8)$, that is 8.

Then I came across another problem:

> **Problem 2**
> In below graph, the edge weights of only those edges which are in the MST are given. What are the weights of other edges?

Solution was:

> In every cycle, the weight of an edge that is not part of MST must by greater than or equal to weights of other edges which are part of MST. Since all edge weights are distinct, the weight must be greater. So $w(ED)=6, w(CD)=15$ and $w(AB)=9$

First solution chooses min degree of a node, whereas second solution chooses max edge weight in cycle. This seems to be obvious since first problem has "unknown MST edge weights", whereas second problem have "unknown non-MST edge weights".

But, I have several doubts here:

1. In solution 1, why we examine edges incident on node $B$ only, but not node $C$? I guessed following procedure:

> If we start preparing MST using Kruskal's algorithm, we will go on adding edges in sequence $AG,IJ,CD,...$ and $C$ gets connected to MST. So in this particular example, it works by preparing MST using the known edge weights such that the edges chosen wont change whatever the unknown weights turn out to be. And then based upon vertices connected to the MST prepared so far, decide which of the vertices of unknown weight edge is to be reached by that edge.

Is this procedure correct? Does it work in all cases / graphs? Is there any other standard approach to solve such problem?
2. Second solution used cycle $E-D-F-E$ to determine the weight of edge $ED$, but not cycle $B-E-D-C$. Though I understand that decision of choosing $EF$ and $DF$ are dependent on $ED$, doesnt decision of selecting $BE$ is dependent on total of weights of $CD$ and $ED$? What is exact rule/idea for deciding which cycle to consider while determining non MST edge weight?
3. Is there some standard well defined steps for both problems? Or its more sort of trial and error work?

# Answer
Firstly, to make the nice answer given by OP to Problem 1 the only valid answer, we should change its question "what are $x$ and $z$?" to "what are the maximal weights of $x$ and $z$?". Otherwise, we can have many valid answers such as "$x=3, z = 5".

Secondly, to make the nice answer given by OP to Problem 2 the only valid answer, we should change its question "What are the weights of other edges?" to "What are the minimal weights of other edges?". Otherwise, we can have many valid answers such as "$w(ED)=16, w(CD)=115$ and $w(AB)=19$".

Lastly and most importantly, let us answer the central question, "Is there some standard well defined steps for both problems? Or its more sort of trial and error work?". A standard way to rephrase the question is, "Is there an effective algorithm for both kinds of problems?"

Let $G$ be an edge-weighted connected undirected graph with some unknown weights. Let us state the questions clearly in more detail. We will assume there are graphs that satisfy the given conditions in the problems. (Otherwise, we can add extra steps to the algorithms below to detect those impossible situations).

## The first kind of problem: unknown weights in an MST

> Assume that we know a minimum spanning tree (MST) of $G$ such that all edges of unknown weights belong to that MST. What are the maximal values of those unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.

Pick any edge $e$ that is not that MST. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$x\leq a$" where $x$ is the unknown weight of some edge in that MST and $a$ is a known number. Repeat until we have gone through all edges that are not in that MST.

Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$x\leq a$" with the smallest number $a$ where $x$ is an unknown. Let $x=a$ be part of the answer. Repeat this process until we have no more inequalities.

## The second kind of problem: unknown weights outside an MST

> Assume that we know a minimum spanning tree (MST) of $G$ such that all weights of edges of the MST are known. What are the minimal values of the unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.

Pick any edge $e$ of unknown weight. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$a\leq x$" where $x$ is the unknown weight of $e$ and $a$ is a known number. Repeat until we have gone through all such edge $e$ of unknown weight.

Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$a\leq x$" with the largest number $a$ where $x$ is an unknown. Let $x=a$ be part of the answer. Repeat this process until we have no more inequalities.

## More general problems?

If you have read this far, it will be obvious that we could create more general problems of similar kinds. We will have a general approach towards producing an algorithm as well. So much for my answer that is already long.
> 3 votes

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Determining the existence of a forced win vs determining the best outcome
A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position.

Is this problem equivalent under polynomial-time reduction to identifying the best forced outcome of a game, where that outcome might not be a win?

If necessary, assume that it’s a two player zero-sum game that pays out 1 for a win, 0 for a draw, and -1 for a loss.

# Answer
They are equivalent under Turing reductions, assuming that the game has finite/polynomial-size branching factor (i.e., only that many moves are possible from each position). I don't know if they are equivalent under Karp reductions.

Consider a position $P$. Assume there are $k$ moves that are legal there. Let $P\_1,\dots,P\_k$ denote the possible positions after making a single move.

Check whether $P$ is a forced win for player #1. If yes, you are done.

Check whether any of $P\_1,\dots,P\_k$ is a forced win for player #2. If they are all a forced win for player #2, then $P$ is a forced lose for player #1.

Otherwise, $P$ is a forced draw for player #1.
> 3 votes

# Answer
There's a game named "chomp" where it is mathematically proven that the player who starts has a winning strategy, but finding the winning strategy seems to be very hard.

Given is an n x m rectangular board of n x m pieces. The players take turns. Each player choses (x, y) and removes all pieces with coordinates both ≥ x and ≥ y. At least one piece must be removed. The player removing the last piece loses.

The first player can take the one piece at (n, m). This is either a winning move, or the second player has a winning move (x, y). But this produces the same position as if the first player had taken (x, y) in the first place, so (x, y) is a winning move for the first player. In any case, the player going first has a winning move.
> 1 votes

---
Tags: algorithms, complexity-theory, game-theory, board-games
---


# Question
Title: Divide an array into two sub arrays such that their sums are equal and possibly maximum
Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum. We are free to omit items from the subarrays.

For example, `[7,2,5,7,12]` can be divided as the following:

1. `[5,2][7] = 7`
2. `[5,7][12] = 12`
3. `[7,7][2,12] = 14`

We need the final answer as `14` because the max possible sum is `14`.

I initially tried to generate all possible combinations of from length `1` to `N` and compare the sums and take intersection between two subsets. But it takes `pow(2,N)` time.

Is there an efficient algorithm to solve this problem?

Please help how to approach this problem. I have tried state space tree with recursion like in the problem `subset_sum`. But couldn't solve this. Please help.

# Answer
The problem is NP-hard, by a straightforward reduction from the partition problem. Therefore, you should not expect any efficient algorithm. However, there is a pseudo-polynomial-time algorithm using dynamic programming (see pseudo-polynomial-time algorithm for the partition problem for inspiration).
> 2 votes

---
Tags: dynamic-programming, partitions, backtracking
---


# Question
Title: Is two arrows on each state necessary in DFA?
In DFA, is two arrows on each state necessary?

Or it depend on language alphabets? I mean if there is $\Sigma = \\{a\\}$ then there should be one arrows on each state.

OR if there are $\Sigma = \\{a , b\\}$ then there should be two arrows on each state.

OR if there are $\Sigma = \\{a , b , c\\}$ then there should be three arrows on each state.

and so on...

# Answer
You are correct.

In an NFA, there might be more arrows (for epsilon transitions, or multiple transitions on the same symbol) or fewer arrows (for undefined transitions) than there are symbols in the alphabet. In a DFA, neither of these is allowed: in fact, a DFA is specifically defined as an NFA where neither of these things happens.

Therefore a DFA will always have exactly as many arrows from each state as there are symbols in the alphabet.
> 1 votes

---
Tags: formal-languages, finite-automata
---


# Question
Title: Understanding characterizations of Matching on Graphs
I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right.

**Definition:** Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a *matching in $G$* if and only if each vertex $v$ in $V$ is incident to at most one edge in $M$, that is, $\forall v \in V ( \forall w \in V ( \forall x \in V (( vw \in M \wedge vx \in M) \rightarrow w = x)))$ holds. Edges may be weighted. For any matching $M$ and weight function $w: E \rightarrow \mathbb Q$ we define $w(M) := \Sigma\_{e \in M} w(e)$.

In the following are the definitions of the two computational problems I am currently working with. For simplicity sometimes I use bipartite graphs only.

---

**Problem Name:** $\text{MAXIMUM-CARDINALITY MATCHING}$

**Input:** A graph $G = (V, E)$.

**Task:** Find a matching $M$ such that $|M|$ is maximum.

---

**Problem Name:** $\text{MAXIMUM-WEIGHT BIPARTITE MATCHING}$

**Input:** A bipartite graph $G = (V, E)$ with weights $w: E \rightarrow \mathbb Q$ on the edges.

**Task:** Find a matching $M$ such that $w(M)$ is maximum.

---

**Definition:** A path $P$ in $G$ is called *$M$-alternating* if and only if the edges in $P$ are alternatingly out of and in $M$.

**Definition:** A path $P$ in $G$ is called *$M$-augmenting* if and only if $P$ is $M$-alternating and both its end vertices are not covered by $M$.

**Thoerem (I think it is due to Peterson):** Let $G = (V, E)$ be a graph and let $M$ be a matching in $G$. Then either $M$ is a solution to $\text{MAXIMUM-CARDINALITY}$ $\text{MATCHING}$ or there exists an $M$-augmenting path.

**Theorem (Egervary):** Let $G = (V, E)$ be a bipartite graph and let $w: E \rightarrow \mathbb Q$ be a weight function. Then the maximum weight of a matching in $G$ (that is, the weight of a solution to the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem) is equal to the minimum value of $y(V)$, where $y : V \rightarrow \mathbb Q$ is such that $y\_u + y\_v \geq w\_e$ for each edge $e = uv$. If $w$ is integer, we can take $y$ integer.

My question is: Does there exist a simpler characterization of the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem similar to Peterson's Theorem? What is wrong with the following characterization?

First, let $A \\; \Delta \\; B$ denote the symmetric difference of two sets $A$ and $B$. Further, if $P$ is a path, then let $E(P)$ denote the set of edges in $P$.

**Hypothesis:** Let $G = (V, E)$ be a bipartite graph, $w: E \rightarrow \mathbb Q$ a weight function, and $M$ a matching in $G$. Then either $w(M)$ is maximum or there exists an $M$-alternating (note: not necessarily $M$-augmenting) path $P$ such that $M' := M \\; \Delta \\; E(P)$ is a matching in $G$ and $w(M') \> w(M)$.

Is the hypothesis correct? If not, why is it wrong? What about the hypothesis with respect to non-bipartite graphs? If the hypothesis is correct, why is always Egervary's Theorem used?

# Answer
> 2 votes
It is nice for OP to extract the essence of the proof for Berge's Lemma, which is described as the "Theorem (I think it is due to Peterson)" to create the hypothesis.

"Is the hypothesis correct? If not, why is it wrong?" Yes, it is correct.

"What about the hypothesis with respect to non-bipartite graphs?" Yes, it is still correct with respect to non-bipartite graphs.

"If the hypothesis is correct, why is always Egervary's Theorem used?" Well, I cannot avow Egervary's Theorem is always used (when? and where?). It is true, however, that in the case of bipartite graph, Egervary's Theorem is instrumental in creating a fast and easily-implementable algorithm to find the maximum weight matching. In comparison, I cannot find a similarly good algorithm for which the hypothesis can be equally helpful. So it is no wonder that Egervary's Theorem is usually mentioned when we come to the maximum weight matching for bipartite graph.

---
Tags: graphs, weighted-graphs, matching, bipartite-matching
---


# Question
Title: If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$?
I tried to solve it as the following: $$\overline{L}=\big\\{\langle M\_1,M\_2\rangle\mid M\_1, M\_2\text{ are TM and } L(M\_1)\cup L(M\_1)\neq\Sigma^\* \big\\}$$ I'll show that $\overline{L}\not\in RE$ by reduction from $$\overline{A\_{TM}} = \big\\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ rejects } w \big\\}$$ I begin by assuming that $\overline{L}$ is recognized by some TM $M'$.

Next, I construct a machine $M\_{\overline{A\_{TM}}}$ that will use $M'$ to recognize $\overline{A\_{TM}}$.

TM $M'$ on input $\langle M, w\rangle$:

1. Build TM $M\_1,M\_2$
2. Simulate $M\_1,M\_2$ on all $x\in\Sigma^\*$, Any simulation will be at most $|x|$ steps.
3. If $M\_1$ and $M\_2$ reject the same $x$, then $M'$ will accept $\langle M, w\rangle$.
4. If $M\_1$ or $M\_2$ accept some $x$, then $M'$ will reject $\langle M, w\rangle$.

Therefore, $\langle M, w \rangle\in\overline{A\_{TM}}$ exactly when $\langle M\_1,M\_2\rangle\in\overline{L}$.

Because $\overline{A\_{TM}}\not\in RE$ so is $\overline{L}$, then $L\not\in co-RE$

Is it true and can I use similar approach to show that $L\not\in RE$?

Thanks.

# Answer
> 0 votes
Your proof is not very clear to me. In your description of $M'$ I don't understand what $M\_1$ and $M\_2$ are, or why they have the properties you claim they do.

A typical reduction proof looks like:

1. You have some language $L$ which you wish to prove is, say, not $RE$.
2. You have a language $L'$ which you know is not $RE$.
3. Suppose there exists a TM $D$ which recognizes $L$
4. Construct a TM $D'$ to recognize $L'$. Usually $D'$ will take some input $x$ and transform it into an input $y$ for $D$, such that $D'$ accepts $x$ if and only if $D$ accepts $y$

So let's do the same thing for this problem. We'll reduce $TOTAL$ (which is neither $RE$ nor $co-RE$) to $L$.

Suppose $D$ recognizes $L$. Let $D'$ be the TM:

TM $D'$ on input $\langle M \rangle$:

1. Let $M'$ be the TM that acts as $M$ but inverts the output
2. Run $D$ on $\langle M, M' \rangle$
3. Accept if $D$ accepts, reject if $D$ rejects.

Now we want to prove that $D'$ recognizes $TOTAL$. This is straightforward. $\langle M, M' \rangle$ is in $L$ if and only if $L(M) \cup L(M') = \Sigma^\*$. But $L(M') = \overline{L(M)}$. So $D'$ accepts $M$ if and only if $M$ either accepts or rejects every input, which is precisely what it means for $M$ to be in $TOTAL$!

So we have shown that no TM can recognize $L$, so $L$ isn't $RE$.

To show that it's not $co-RE$ either we take $D$ to recognize $\bar{L}$ instead, and define $D'$ just as above. So now $D'$ accepts $M$ if and only if $\langle M, M' \rangle$ is not in $L$. The same argument above shows us this is exactly true when $M$ is not in $TOTAL$.

---
Tags: turing-machines, reductions
---


# Question
Title: How to solve for the precondition give a postcondtion that must satisfy two conditions
I tried solving past exam question but there is this one that I haven't been able to solve.

The question states that a suitable precondition should be found for the statement.

$$ a= i +2; i++\\{(a = 7)\land(i = 5)\\} $$ Here's my solution and where I got stuck:

$$ wp(a= i +2; i++,(a = 7 \land i = 5) \\ =wp(a= i +2, wp(i=i+1,a = 7\land i = 5) $$

I've tried solving it intuitively and I arrive at the conclusion that no such value for `i`i should exist.

I haven't been able to find a rule to combine the two predicates of the post-condition.

Please I would like to know when solving similar questions can I change the `^` to an algebra symbol or should I take the relevant condition and find the weakest precondition with that.

# Answer
> 2 votes
The rules for $wp$ are straightforward for non-loops:

$$wp(c\_1 ; c\_2, V) = wp(c\_1, wp(c\_2, V))$$ $$wp(x := e ; V) = V\left\[x \mapsto e\right\]$$

Plugging in the original values, you need to compute

$$ wp(a := i + 2; i := i + 1, (a = 7) \wedge (i = 5)) $$

The first rule applies here, giving

$$ wp(a := i + 2, wp(i := i + 1, (a = 7) \wedge (i = 5))) $$

In the second $wp$ expression, the second rule applies, giving

$$ wp(a := i + 2, (a = 7) \wedge (i + 1 = 5)) $$

Now the second rule applies again to the remaining $wp$:

$$ ((i + 2) = 7) \wedge (i + 1 = 5) $$

Now, you just need to know that the above is always false, regardless of the value of $i$. There are various automatic approaches to do this (since these are linear equations, you could use the simplex method). In this case, since they're so simple, you could just normalize your equations into $i = constant$:

$$(i = 7 - 2) \wedge (i = 5 - 1)$$

Knowing $7 - 2$ and $5 -1$ are constant expressions, you can get $$i = 5 \wedge i = 4$$ which would imply $$4 = 5$$ which is always false, so the original statement must be always false.

---
Tags: logic, formal-methods, hoare-logic
---


title: SAT Solving + Turing Machines

text:
# Question
Title: SAT Solving + Turing Machines
I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:

* Randomness
* Heuristics
* Backtracking

SAT is just one example of an NP-complete problem. Is it common to use such techniques **in conjunction** to solve intractable problems? I normally see approaches to solving difficult problems in sections, like probabilistic algorithms or parallelism, but what stops them from being employed simultaneously?

Further to this, how is randomness achieved on a Turing machine? I mean by this pseudo-randomness, so is this possible on a Turing machine?

This is a slightly more specific question, but heuristic algorithms will have different meanings based on the problem. So if someone were to make a polynomial-time solver for another NP-complete problem like clique, based on heuristics, how would this also make SAT in P? Basically, certain methods of solving certain NP-complete problems will undoubtedly differ. How can this all at the end of the day reduce to the same problem? Can methods of solving an NP-complete problem be reduced to others?

# Answer
> 2 votes
Yes, it is common for a SAT solver to combine several techniques, e.g., random restarts with smart backtracking or other tricks. More generally, nothing stops you from throwing everything and anything at a problem you want to solve. (The reason a book might talk very specifically about say "probabilistic algorithms" instead of "here's how you solve problem X by using a probabilistic algorithm in combination with this trick, that heuristic and this data structure" is that it wants to keep focus on a specific algorithmic idea and its analysis).

The key point here is that a SAT solver is intended to be used in practice, and this is why it makes sense to combine several algorithmic techniques, data structures, etc. to achieve practical efficiency. Still, in general, no matter what the solver does, it cannot be fast and correct on every possible instance (due to NP-completeness).

To understand why having a fast algorithm for an NP-complete problem allows you to solve other such problems, look up polynomial-time reductions, and read up on NP-completeness. Here, again, it is useful to notice that all of this is perfectly fine in theory, but in practice things might be different (it is *not* true that "polynomial time" necessarily means "efficient in practice").

---
Tags: turing-machines, np-complete, heuristics, probabilistic-algorithms, backtracking
---


# Question
Title: Understanding algorithm for maximum sum of non-consecutive elements
There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it:

https://stackoverflow.com/questions/4487438/maximum-sum-of-non-consecutive-elements

That said, I have read this post many times, and many other posts online about how to solve this problem, and I still do not understand *why* the solution is correct.

Following another post about the problem (that shows the solution, but again lacks in an explanation as to *why* the solution is correct), I created the following snippit to run in JShell:

```
class MaxSubset {
    public static Integer maxSum(final List<Integer> ints) {
        final class MaxSubsetR {
            private Integer maxSumR(final List<Integer> ints, final Integer i, final String str) {
                if(i == 0) {
                    System.out.println("in i == 0: " + str);
                    System.out.println("in i == 0: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 0: get 0 " + ints.get(0) + " " + str);
                    System.out.println("returning: " + ints.get(0));
                    return ints.get(0);
                }

                if(i == 1) {
                    System.out.println("in i == 1: " + str);
                    System.out.println("in i == 1: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 1: get 0 " + ints.get(0) + " " + str);
                    System.out.println("in i == 1: get 1 " + ints.get(1) + " " + str);
                    System.out.println("returning: " + Math.max(ints.get(0), ints.get(1)));
                    return Math.max(ints.get(0), ints.get(1));
                }
                System.out.println("no match " + i + " " + str);
                return Math.max(maxSumR(ints, (i - 1), "left"), ints.get(i) + maxSumR(ints, (i - 2), "right"));
            }
        }
        return new MaxSubsetR().maxSumR(ints, ints.size() - 1, "init");
    }
}

```

but after running the algorithm and watching the output, I'm still just as confused as I was when I began.

Can someone explain this algorithm to me? In particular:

1) How is the alternation of choosing (i - 1) or (i - 2) is even determined in the recursion in the first place?

2) How does simply subtracting 1 or 2 from the size of the array create the effect of selecting the optimal subset of non-adjacent items?

3) And just generally, how is it going about picking the right items from the list to achieve the stated goal?

*New Question*

4) We note that the `List<Integer>` never mutates during the recursion, so for the two `if` statements, `i == 0` will always return the first item in the list, regardless of list size, and the `i == 1` case will always return the greater of the first or second item in the list, regardless of list size. So, how is it that every item in the list is even being considered, if the return statements *literally* only care about `arr[0]` and `arr[1]`?

EDIT NOTES

I have re-written my second question to, hopefully, make it more clear what I mean.

For ease of reading, here is the algorithm in pseudo-code, without print statements:

```
func maxSum(Int[] arr, Int i)
  if(i == 0) return arr[0]
  if(i == 1) return Math.max(arr[0], arr[1])
  return Math.max(maxSum(arr, (i - 1)), maxSum(arr, (i - 2)) + arr[i])

```

and it would be called with

```
maxSum(arr, arr.size - 1)

```

# Answer
Let me try to explain how to solve the problem. You are looking for a set of non-consecutive array elements with a maximum sum.

Let's say you have an array of 100 elements. Which ones of elements #99 and #100 can be in the optimal solution? They cannot both be present, because they would be consecutive. They cannot both be absent, because then adding #100 would create a larger sum without violating the rules. So one of #99 and #100 is present, and the other is not.

If #99 is present, then the solution is also the optimal solution for 99 elements. If #100 is present, then the items without #100 would be the optimal solution for 98 elements. So there are two possible ways to get an optimal solution for 100 elements: You take the optimal solution for 98 elements and add #100, or you take the optimal solution for 99 elements.

So f (A, n) = max (f (A, n-1), f (A, n-2) + A\[n\]) if n ≥ 2; f (A, 1) = A\[1\] and f (A, 0) = 0.

Note that implementing this using recursion is horribly inefficient. It's best to calculate f (A, 1), f (A, 2), f (A, 3) in sequence in linear time.
> 1 votes

# Answer
Say we have an array `Arr[0..i]` and `M(i)` being the optimal solution of (maximum sum of non-adjacent elements) from `0 to i`. We define `M(0)=Arr[0]` and `M(-1)=0`.

Then we build our recurrence relation as follows;

```
M(i) = Max(M(i-1),M(i-2)+Arr[i]) for 0..i

```

`M(n)` being the solution we want. I will try to explain your questions using examples.

1. > How is the alternation of choosing (i - 1) or (i - 2) is even determined in the recursion in the first place?

Here we choose the max of `M(i-1)` and `M(i-2)+Arr[i]`, where `M(i-1)` alone means we take the solution before without adding `Arr[i]` to it since it would be two adjacent elements added. Next option is to take `M(i-2)+Arr[i]` this would be okay since (i-2)th solution wont be adjacent to the `Arr[i]` we are considering at the moment. Take note that since we set `M(0)=0` before and if any `i-1 or i-2` results in `-1`it will be `M(-1)=0` thus it's like a recurrence exit condition. Also take note that `M(i)` here is the representation of maximum sum of non adjacent elements from `0 to i` it's not a separate array. So if `i=3`, `M(0)=0` and `M(1)` will be `Max(M(0),M(-1)+Arr[1])` which is `M(0)=0` and `M(-1)=0 + Arr[1]`'s value and so on for other values of `i`. You can use a Dynamic Programming approach and store the values of `M()` to not calculate repeating sub-problems over and over again. I believe these should answer all your bullet-points.

Just to clear any misunderstandings, `M(i)` is the maximum value of non-adjacent elements summed until element `i`(inclusive). That is why we choose the max of `M(i-1)` and `M(i-2)+Arr[i]`, because if we add `i` to the sum until `i-1` we would break the rule of non-adjacency that's why we consider the value of `M(i-1)` with `Arr[i]` not added and `M(i-2)` with `Arr[i]` added

Hope this helps!
> 0 votes

---
Tags: dynamic-programming, subset-sum, maximum-subarray
---


# Question
Title: NP-hardness of existence of spanning tree with given maximal degree
I am trying to solve the following exercise:

> Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:
>
> 1. $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.
> 2. $G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.

I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?

# Answer
> 2 votes
Hint for part 1: What does it mean when $G$ has a spanning tree where every node has at most 2 neighbors?

Hint for part 2: Suppose you know that it is NP-hard to show that $G$ has a spanning tree where every node has at most 2 neighbors. Can you reduce this problem of at most 2 neighbors to the current problem of at most 5 neighbors?

This post is made out of user53923's comment as I have verified it is useful.

---
Tags: graphs, np-hard, minimum-spanning-tree
---


# Question
Title: Contradiction in regularity of a language
Lets say we have $L\_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = L\_1$ so that $L\_1$ must be regular.

Now I have the problem that my teacher told me that $L\_2 = \\{ww| w \in \\{0,1\\}\*$ and $w$ ends with 10$\\}$ is not context free.

But if $L\_1$ is regular or context-free, so should $L\_1L\_1=L\_2$ be also regular and context free.

Where is the mistake?

# Answer
There is a difference between $L\_2 = \\{ww\mid w \in L\_1\\}$ and $L\_3 = L\_1 L\_1$. $L\_3$ is $\\{wx\mid w, x \in L\_1\\}$; in, other words all strings consisting of two sentences from $L\_1$, which is regular / context-free if $L\_1$ is regular / context-free.

$L\_2$ is the set of all strings consisting of one repeated string from $L\_1$, which is not in general context-free. (It is regular if $L\_1$ is finite or is a regular language over a singleton alphabet. But your example does not fall into either of these categories.)
> 4 votes

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


# Question
Title: Hindley-Milner type inference for language with implicit type casting
I've only implemented the HM algorithm on a small academic language with a few primitive types and functions. In that case, the unification algorithm would return a type error if two different primitive types were given. For example, if statements unify their condition with primitive type `bool`, producing the following results:

```
if (true) ... // type safe
if ("5") // type error, cannot unify string and bool

```

I've now been tasked to implement a type inference algorithm on a language that allows type casting on primitive types. For example, one cast is `int -> bool` such that `if(5) ...` is now a valid expression.

The problem is, I can't figure out how to adapt the unify algorithm. Specifically, I'm stuck on dealing with the one directional nature of type casts, e.g. `int -> bool` is defined, but `bool -> int` is not. The unify algorithm has no notion of direction. Unifying type `a` and type `b` is the same as unifying type `b` and type `a`. So in the case of the if statement, if I say that unify `int` with `bool` is allowed, then unify `bool` and `int` must also be allowed, and suddenly the statement `true + false` is type safe.

I've searched for details of existing type systems that do this, but unfortunately I've only found resources that either show a basic HM inference algorithm similar to the first one I implemented, or are completely off topic.

# Answer
> 3 votes
Hindley-Milnor type inference doesn't support implicit type casting, so you can't fix that easily. You'd need a fundamentally different algorithm for type inference, and I'm not sure whether such a thing exists. I think there are ways to handle type inference with implicit type casts if you don't care about supporting polymorphic types, but as far as I know, the combination of polymorphic types, type inference, recursion, and implicit type casts is hard to handle simultaneously.

In contrast, it's straightforward to extend HM type inference to handle explicit type casting.

---
Tags: algorithms, type-theory, type-inference
---


title: Hough Transform, Computer Vision

text:
# Question
Title: Hough Transform, Computer Vision
There is some thing i dont understand about Hough Transform in polar coordinates.

**From wikipedia article:**

***"The simplest case of Hough transform is detecting straight lines. In general, the straight line y = mx + b can be represented as a point (b, m) in the parameter space. However, vertical lines pose a problem. They would give rise to unbounded values of the slope parameter m. Thus, for computational reasons, Duda and Hart\[5\] proposed the use of the Hesse normal form $R = X\*Cos(\theta) + Y\*Sin(\theta)$ , where $R$ is the distance from the origin to the closest point on the straight line, and $\theta$ is the angle between the x axis and the line connecting the origin with that closest point."***

now the issue im having with this is:
The Distance from the origin to the closest point on the straight line would be $\sqrt{x^2 + y^2}$ by the euclidean metric
and not $R = X\*Cos(\theta) + Y\*Sin(\theta)$

# Answer
> 2 votes
Consider a vector $\mathbf v$ of any dimension. The hyperplanes orthogonal to that vector are given by the equation $r = \mathbf u\cdot \mathbf v$ for various $r$s. That is, the collection of vectors $\mathbf u$ satisfying $r=\mathbf u\cdot\mathbf v$ describe a hyperplane orthogonal to $\mathbf v$. If $\varphi$ is the (acute) angle between $\mathbf u$ and $\mathbf v$ (in the plane that they span, not to be confused with the hyperplane the earlier equation describes), this can be written as $r=|\mathbf u||\mathbf v|\cos\varphi$. From this we can see that $|\mathbf u|$ is minimum when $\varphi = 0$ so that $\cos\varphi=1$, the maximum value of $\cos$. If we choose $\mathbf v$ to be a unit vector, i.e. $|\mathbf v|=1$, then the point on the hyperplane closest to the origin is $\mathbf u=r\mathbf v$ and has distance $r$, i.e. $|\mathbf u|=r$.

In the 2D case, the "hyperplane" is actually a line. A unit vector in the plane has the form $\mathbf v = (\cos\theta,\sin\theta)$ for some $\theta$. The dot product equation describing the line is then $r=\mathbf u\cdot\mathbf v = u\_x\cos\theta + u\_y\sin\theta$ where $\mathbf u = (u\_x,u\_y)$. The point on the line closest to the origin is then $r\mathbf v = (r\cos\theta,r\sin\theta)$ which is a vector of length $r$ just as stated in the article. As mentioned in the previous paragraph, if $\mathbf v$ is chosen as a unit vector (and it always can be), then this is true in general: $r$ is the distance of the closest point to the origin of the described hyperplane, and that closest point is $r\mathbf v$.

---
Tags: computer-vision
---


title: Machine code and punched cards

text:
# Question
Title: Machine code and punched cards
I have been looking into the history of programming, and everybody and their grandmothers begin the subject with a claim more or less similar to the following:

> At first, programmers used machine code. Later, there were assemblers. Then, pseudo code, and finally Fortran came.

With some Google-fu I can very easily find examples of punch cards containing Fortran statements, COBOL statements, and some Assembly statements. Wikipedia has some punch card examples for short code.

But I am yet to find a reliable source explaining how programmers entered machine code into computers using punch cards. Or pseudo code using punch cards.

Were there really punch cards for machine code? Or when stored programs appeared they were already programmable with Assembly?

# Answer
You normally started by entering a little loader program one word at a time by setting the bits with a line of toggle switches on the front panel, like this:

Wikipedia has a bit of explanation of the process. (Yes, it was tedious.) The little program would then read a larger program off of some convenient input device, which could be a card reader, although the machines I used in those days used paper tape.

It could even be magnetic tape or some other magnetic storage device.

The larger program was the equivalent to the boot loader which is on sector zero of the persistent storage of whatever computer you used to ask this question, so the process is not that different.

A useful innovation was storing the initial boot loader loader in hardwired persistent memory (aka BIOS).

The use of symbolic codes to replace individual binary toggle switches (or equivalent) grew over time, and the distinction between assemblers and "higher level" languages is not a clear line. Fortran was certainly not the first higher level language, but it was extremely important.

(Some of the images come from David Gesswein's wonderfully nostalgic PDP-8 site.)
> 4 votes

# Answer
If I understand the question correctly, you can find some examples of punch cards containing machine code for the IBM 701 here (pdf link). Also, you can see some of the original manuals and documentation for the IBM 701 here.
> 1 votes

---
Tags: programming-languages, history
---


# Question
Title: Matching two lists of different sizes with exceptions?
Suppose that I have two lists of numbers (which represent IDs for rows in a database):

```
list1 = [1, 4, 7, 8]
list2 = [2, 3, 5, 6, 7]

```

I would like to write an algorithm to pair each number in the larger of the two lists with a number in the smaller list such that:

* Every item must appear in at least one pairing
* No item from the larger list appears in more than one pairing
* No item from the smaller list appears more *than is necessary* to satisfy the first constraint (in other words, if the larger list has 5 members and the smaller list has 3, no item from the smaller list appears more than twice)

The algorithm I came up with is fairly simple (in pseudo-code):

```
offset_into_smaller_list = 0
foreach item in larger_list
    pairing = [ item, smaller_list[offset_into_smaller_list] ]
    offset_into_smaller_list++
    if offset_into_smaller_list == sizeof(smaller_list)
        offset_into_smaller_list = 0

```

However, there's a small twist.

I also have a list of exceptions (a pairing that is forbidden).

I would like to modify the algorithm to take these exceptions into account. If one or more valid solutions exists, I'd like the algorithm to find one in the least amount of time possible.

My initial approach began with:

* Calculating all combinations (there are `sizeof(list1) * sizeof(list2)`)
* Removing the exceptions from the list of combinations
* Grouping the combinations using the item in each pair that belongs to the larger list
* Iterating over the groups and selecting one pair from each group

I get stuck at the last step. After each iteration, the number of valid combinations that remain in each group shrinks.

Is there a better approach to this problem? How can I ensure that this algorithm will always find a valid solution if one exists? How can I make it as efficient as possible?

# Answer
> 1 votes
This is an instance of bipartite matching. Build a graph where each left vertex represents one item from the larger list. Duplicate each element in the smaller list the minimum number (e.g., if you want no item from the smaller list to appear more than twice, duplicate each item in the smaller list twice), then use one right vertex for each such (duplicated) item. Draw an edge between items if they are not a forbidden pairing. Then, use any standard algorithm (e.g., the Hungarian algorithm) to search for a perfect matching in this bipartite graph.

---
Tags: algorithms
---


title: Why is this n^2 growth?

text:
# Question
Title: Why is this n^2 growth?
I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading:

"... performs of the order of $n^2$ steps on a sequence of length $n$."

Could someone please explain how this is calculated in the following code, which is also taken from the book?

If I print out the statements when the lines are executed, it first executes $n$ steps, then decreases $n-1$ steps for each loop iteration until it reaches $0$. This does not seem like exponential growth to me. Why does this grow at $n^2$?

```
dataset = [3,1,2,7,5]
product = 0

# algorithm begins here
for i in range(len(dataset)):
  for j in range(i + 1, len(dataset)):
    product = max(product, dataset[i]* dataset[j])

```

# Answer
> 4 votes
Because $n + (n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n+1)}{2} \in \mathcal{O}(n^2)$.

Note that $n^2$ is polynomial, not exponential (that would be $2^n$ for example).

---
Tags: algorithms, algorithm-analysis, python
---


# Question
Title: Edit distance for huge strings with bounds
My question is simple but I don't know if the answer is.

> If you have two strings of length 10 million each, is there an algorithm that would allow you in practice to compute their edit distance (Levenshtein) if you are told it is at most 100?

# Answer
> 3 votes
You can use the usual dynamic programming algorithm. Instead of computing the edit distance between *all* prefixes of the input strings, compute only the edit distance between prefixes whose length is at most 100 apart. This reduces the number of entries to compute from $10^{14}$ to roughly $2\cdot 10^9$, which is feasible.

---
Tags: algorithms, edit-distance
---


# Question
Title: Formal grammar with variables for consistent substitutions
In a rewriting system, suppose the production rule `S→xAyAz` (or `<S>:=x<A>y<A>z`, in BNF), where **S** and **A** are nonterminal symbols and **x, y, z** are any string.

This rule produces the string *xa1ya2z*, where **a1** and **a2** are strings substituted by the nonterminal symbol **A**. The substitutions **a1** and **a2** may be equal or different strings.

But what if I want to **a1** and **a2** to be the same string; that is, if the nonterminal **A** be substituted by the same instance in both its occurrences in that production rule?

I used a kind of BNF I created informally for such purpose, with `<v:A>` instead of `<A>`: a kind of "typed variable", whose type is a nonterminal symbol and the variable is the same substitution for all its occurrences. Thus, `<S>:=x<v:A>y<v:A>z`, and `<v:A>` is substituted for the same string in its both occurrences.

What is the name of such a grammar that uses variables for consistent substitution of a nonterminal? And there is a grammar formalism for it?

# Answer
You've created an affix grammar, so named because they were created to deal with affixes (prefixes and suffixes) in natural languages.

Specifically, this is a type of affix grammar where the "affixes" (what you call typed variables) are defined by the same type of grammar rather than coming from a simpler (finite) grammar. This creates a two-level grammar, specifically a type known as a Van Wijngaarden grammar after its creator.

It turns out that this type of grammar is in fact Turing-complete, so non-trivial semantic properties of such grammars are undecidable by Rice's theorem. On the one hand this makes them extremely powerful; on the other hand, it makes them not as useful in practice, since you could use some other Turing-complete system instead.
> 2 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Why can't every computation be expressed in the style of MapReduce?
What are the limitations of map reduce in the sense of the types of computations that they can express? Is Map Reduce "turning complete"?

I have been told that map reduce only works on things that can be expressed in the Map and Reduce framework, but my question is, why can't everything be expressed like that?

This might be the reason why Distributed Shared Memory systems like tread marks or IVY started to exist. So that we could express general programs and deal with them in a distributed computing manner.

Can someone give me an example of a task that can be done in a DMS and one that cannot be in map reduce? Or maybe, is there a formal theorem or proof showing what things can't be done in MapReduce but that a general programing language can do? What are the inherit limitations of Map Reduce and why are they the way it is?

# Answer
In MapReduce you take a big computation and split it up into many small computations that are done in parallel and that don't depend on one another. That way you can use many cores and if one calculation fails, you don't have to redo the entire job, just that small task.

But if you have a problem that can't be broken down into sub-problems that are independent of one another or dependent on some global state, then you are stuck with doing one long big computation and lose the benefits of MapReduce.
> 5 votes

# Answer
there are two different/separate concepts to keep in mind. computation related to Turing completeness is not about parallelism. a general purpose parallel computing system, of which Mapreduce is one, is Turing complete, and all Turing complete operations can run on a parallel system, but (as pointed out in the other answer) the *speedup* due to parallelism may not be possible.

Mapreduce in a single operation is actually designed for a narrow class of parallel problems known as embarrassingly parallel where no communication between processors is required. any problems that require communication between processors are not reducible to single Mapreduce operations although could generally be broken down into multiple Mapreduce operations with communications of results between processors (or centrally operated on) in intermediate steps.

the question about which problems can be efficiently computed in one architecture (eg Parallel) vs others are mostly open in complexity theory. about all that can be proven is that some problems can be "sped up" via parallelism but other basic questions such as "do there exist algorithms that cannot be parallelized (ie speedup due to parallelism)" cannot be answered definitively at the current state of knowledge.
> 3 votes

# Answer
By googling I found a list of example:

http://csci8980-2.blogspot.com/2012/10/limitations-of-mapreduce-where-not-to.html

I provide it as a reference, but I would still love to see the intuition (or proofs) on why these methods can't be expressed in MapReduce.
> 2 votes

# Answer
MapReduce is based on splitting a task and have it done by several machines. It is obvious that some tasks can not be spitted. The reason is that the result is kind of Holistic meaning that whole data should be considered at once. Two types of holistic problems are:
1) **Intensive calculations:**
First let see what is extensive property: suppose you want to square 2K numbers and then add them up. this is extensive operation since you can send every (per say) 200 numbers to every machine and have them do the operation for you and finally add the result coming from each machine. Another way to think about this is that you do the operation on given 2K numbers and another number is received, in this case you can simply square the number and add it to the previous result. Now think that you need to first sum all the numbers and then square the result.
Oops! you can not do this easily. As you can see you can simply extend the operation to new number. ( note that for this simple example one can use $c^2 = a^2 + b^2 + 2ab$ however this is not the case for all problems)
2) **Graphs:**
most of the calculations on graphs require data from whole graph so those kinds of calculations can not be done using distributed systems.
How do we find out if a calculation can be done by distributed system or not?
If you remember distribution property in Algebra you have the answer. for the above example we have:
extensive scenario: $ a^2 + b^2 + c^2 = (a^2 + b^2) + c^2 = a^2 + (b^2 + c^2)$
Intensive Scenario: $(a+ b+ c)^2 != (a+b)^2 + c^2$
> 1 votes

---
Tags: distributed-systems
---


# Question
Title: Mimimum spanning tree with a constraint on number of certain types of edges
I have the the following problem.

Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning tree such that we minimize total weight but also we can only use a maximum of $c$ edges in $B$.

I feel like this is just Prim/Kruskal with an additional condition in the main if condition, but is that correct? I think we can still use a greedy algorithm but do not know how to show correctness.

# Answer
> 2 votes
Let us take Kruskal's algorithm for an example. Apparently, OP refers to the adjusted version such that when we choose among edges of equal weight, we will pick the ones in $A$ before the ones in $B$ as long as at least one edge in $A$ is left available. If the MST we arrive in the end has no more than $c$ edges in $B$, then that MST is the output. Otherwise, the output is empty, indicating no such MST has been found. Let us name this algorithm **$A$-favoured Kruskal's algorithm**.

To prove that **$A$-favoured Kruskal's algorithm will find a satisfying MST whenever there is one** is, in fact, not trivial even if we have been enlightened with or especially when we are distracted by the general techniques on how to prove greedy algorithm is correct.

Here goes my proof. Let us fix the weighted graph $G$ so that we will often be referring to $G$ implicitly. Let $R$ be a particular run of Kruskal's algorithm that produces $m$, an MST. Let $RA$ be a particular run of $A$-favoured Kruskal's algorithm that produce $ma$, another MST. ($RA$ may or may not be the same as $A$ and $ma$ may or may not be the same as $m$). Suppose $w\_1\lt w\_2\lt\cdots$ is the increasing sequence of all distinct edge weights. Break up the while loop of $R$ into smaller loops $R\_1\lt R\_2\lt\cdots$. For each $i$, $R\_i$ iterates over all edges of weight $w\_i$. For each such edge, $R\_i$ adds it to the growing forest if it connects two different trees and ignores it otherwise. Let $F\_i$ be the forest obtained at the end of $R\_i$. Let $E\_0=G$. For $i\gt0$, let graph $E\_i$ has the same vertices as $G$ and all edges of $G$ except the edges of weights greater than $w\_i$.

Using induction on $i \> 0$, we can see that each connected component of $F\_i$ (, which is a tree) is its corresponding connected component of $E\_i$ minus some edges (the edges that were discarded because they did not connect different connected components(trees)). Let $g\_i$ be the number of edges in $A$ of weight $w\_i$ that are selected into $m$ during $R\_i$. We can see that $g\_i$ cannot bigger than $h\_i$, the largest number of edges in $A$ of weight $w\_i$ that can be added to $H\_{i-1}$ without causing a cycle. In fact, $h\_i$ is the decrease from the number of connected components in $E\_{i-1}$ to the number of connected components in $E\_{i-1}$ with all edges in $A$ of weight $w\_i$ added. So $h\_i$ depends only on $G$, $A$ and $i$. Note that $g\_i$ will be $h\_i$ if $R$ is actually a run of $A$-favoured Kruskal's algorithm, such as $RA$. So $$\\#\\{\text{edges in } A \text{ and } m\\} = \sum\_{i}g\_i \leq \sum\_{i}h\_i = \\#\\{\text{edges in } A \text{ and } ma\\}$$

Note that all MSTs can be found by Kruskal's algorithm. For a proof, you can check any MST is reachable by any MST algorithm with some minor exceptions. So we have shown that of all MSTs, $ma$ has the most edges in $A$. Since the number of edges in $ma$ is the same, $ma$ has the least edges in $B$. Proof is completed.

Indeed, we have proved more. **Any run of $A$-favoured Kruskal's algorithm will produce an MST with the same number of edges with any given weight in $A$ and in $B$**.

---
Tags: algorithms, greedy-algorithms, weighted-graphs, minimum-spanning-tree, constraint-satisfaction
---


title: Deletion from 2,3,4 tree

text:
# Question
Title: Deletion from 2,3,4 tree
Consider a 2,3,4 tree like so,

```
           53
         /    \
        /      \
       /        \
     46          60 | 70
    / \         /    \   \
   /   \       /      \   \
  /     \     /        \   \
 41     48  55|59    65|68  73|75|79

```

How to delete 41 from the tree from here ? I would like to know the intermediate steps involved.

# Answer
> 3 votes
The problem you're encountering is that a deletion is cascading and triggering another deletion. In particular, you're deleting from a node with only one key. Rather than working from the bottom up, it may be easier to work from the top downwards to preserve all of the properties of the 2-3-4 tree while giving an extra key to the node you're deleting from. Here are the rules for deletion:

* If node containing key has more than one key, just remove the key.
* Otherwise, we're trying to remove a 2-node (node containing 1 key). Traverse the path from the root to this node and perform one of the following operations on every 2-node except the root node to transform it into a 3-node or 4-node (node containing 2 or 3 keys):
    1. If node has a sibling that's a 3-node or a 4-node, have the parent steal a key from one such sibling and have the 2-node in question steal from the parent. The child of the sibling key we stole becomes a child of the node we just expanded.
    2. If the node's parent is a 2-node and its sibling is also a 2-node, fuse all three together into a new 4-node. Note that this can only happen when the parent is the root since all other 2-nodes should've already been fixed.
    3. If all of the node's siblings are 2-nodes, steal a key from the parent (we know we can do this because we're converting every node we hit into a 3-node or a 4-node) and fuse together the node, the stolen key, and an adjacent sibling.

So starting from the tree below, we see that 41 is the only key in its node so let's start from the root and perform operations as necessary on the way to 41. We start at the root 53 and do nothing:

```
    -->   53
        /    \
       /      \
      /        \
    46          60 | 70
   / \         /    \   \
  /   \       /      \   \
 /     \     /        \   \
41     48  55|59    65|68  73|75|79

```

Then we get to 46 which is a 2-node. One of its siblings has more than 1 key so we perform operation 1. In particular, have the parent steal a sibling key 60 and have the node containing 46 steal 53 from the parent. The original left child of 60 becomes the right child of 53.

```
              60
            /     \
           /       \
          /         \
   --> 46 | 53       70
      /   |  \       \   \
     /    |   \       \    \
    /     |    \       \     \
   41     48  55|59   65|68  73|75|79

```

Finally we're at 41 which is also a 2-node and all of its siblings are 2-nodes so we perform operation 3. In particular, we steal 46 from the parent and fuse 41, 46, and 48 into a new node.

```
                   60
                 /     \
                /       \
               /         \
              53         70
             / \         / \
            /   \       /   \
           /     \     /     \
--> 41|46|48  55|59  65|68  73|75|79

```

Now the node containing 41 has more than one key so we can go ahead and delete 41.

---
Tags: search-trees, balanced-search-trees
---


# Question
Title: How hexadecimal representation is more compact and intelligible for documentation?
My textbook says, "Instead, it is far better to use a hexadecimal representation for documentation purposes. Whether or not a code represents a binary number, it can be treated as such and converted to the corresponding hexadecimal number. This makes the representation more compact and, as a result, more intelligible." would any body explain it to me plz? Thanks!

# Answer
> 1 votes
This is just the ordinary English language use of the word "compact": taking up less space. As to whether it's more intelligible, eh, that's basically a matter of reader preference and very context-dependent. Probably nobody wants to read "The system supports up to 0x64 users."

---
Tags: information-theory, number-theory, encoding-scheme
---


# Question
Title: Breadth First Search actually require specifically Queue instead of any other type of Collection?
As far as I know, **Breadth-First-Search \[BFS\] theory traditionally requires a Queue** to process a given level of a graph (i.e: wiki seems to assume so).

But **does BFS really actually require a Queue, rather than just any type of Collection**?

* A Queue is a Collection
* A Set is also a Collection, for example

Wiki states that BFS...

> "explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level."

What about that quote requires specifically a Queue? Why would BFS not work if implemented with any other type of Collection besides a Queue?

It seems to me that as long as any Collection is used to explore "all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level", by storing such neighbor nodes in that Collection and ensuring the entire Collection is emptied (or otherwise completely processed or explored) before moving on to the next depth level, then the level-ordering requirement of BFS is achieved?

I understand that a Queue would ensure a certain order (i.e: left-to-right) while processing/exploring *within* a given level; but is that ordering *within* a given level really necessary such that the algorithm still meet the requirements of BFS? Otherwise why is order *within* a given level actually necessary?

# Answer
It doesn't literally have to be a queue. Anything that ensures that one level is completely explored before moving to the next one would suffice. However, the most natural way to do this is with a queue and any other implementation is going to be harder to describe and/or harder to implement than just "use a queue."

As evidence that it's harder to describe, note that your claim in the question that it suffices to ensure that the collection is empty before moving onto the next level is incorrect. Consider the following tree.

```
    1
   / \
  2   3
  .   .
  .   .
  .   .

```

We start searching at node 1. We place its children 2 and 3 in the collection. So the collection isn't empty but it's definitely time to move on to the next level.

OK, how do we fix this? Well, we could have *two* collections: one for the current level and one for the nodes that need to be expanded at the next level. Each time we process a node at the current level, we add its children to the "next level" collection. When the current level is all done, the "next level" collection becomes the "current level" collection, and we start a new, empty, "next level". OK, that works, but it's harder to describe than using a queue. On the other hand, if you want to claim that it's easier to prove that the two-collection version is correct, you'd have a point. Really, everything is a trade-off.
> 5 votes

---
Tags: data-structures, graph-traversal, queues
---


# Question
Title: Applying a permutation on a sequence with multiplication
We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum\_{i=1}^n{\alpha\_i.\pi\_i} = x$ or tell if there is none.

Well I wasn't able to solve it in polynomial time and I'm not sure whether it's possible. So if it's NP would you give me some observations on the reason?

# Answer
The problem is NP-complete. Here is a reduction from 3SAT.

Given an instance of 3SAT with variables $v\_1,\ldots,v\_n$ and clauses $c\_1,\ldots, c\_m$, construct numbers as follows. We represent a number as the form $\lambda\_1p^{\mu\_1}+\lambda\_2p^{\mu\_2}+\cdots$ where $p$ is a very large number (we will estimate $p$ later) so that we can assume there is no carry when performing addition of numbers.

1. Construct $2n-1$ numbers $u\_1,\ldots,u\_{2n-1}$: $p^0, p^1, \ldots, p^{2n-2}$.
2. For each variable $v\_i$, if $v\_i$ shows up in clauses $c\_{j\_1},c\_{j\_2},\ldots$ and $\bar{v}\_i$ shows up in $c\_{k\_1},c\_{k\_2},\ldots$, construct two numbers $y\_i=p^{2n-2+i}+mp^{3n-2+j\_1}+mp^{3n-2+j\_2}+\cdots$ and $\bar{y}\_i=p^{2n-2+i}+mp^{3n-2+k\_1}+mp^{3n-2+k\_2}+\cdots$.
3. For each clause $c\_j$, construct numbers $z\_j=p^{3n-2+j}$.
4. Add $0$s to make there are $(13n+1)m$ numbers in total.
5. The target $$ \begin{align} x=\\;&(n+1)p^0+(n+2)p^1+\cdots+(3n-1)p^{2n-2}\\ &+4np^{2n-1}+4np^{2n}+\cdots+4np^{3n-2}\\ &+16nmp^{3n-1}+(16nm+1)p^{3n}+\cdots+(16nm+m-1)p^{3n-2+m}. \end{align} $$

Since there are $(13n+1)m$ numbers and the coefficient of $p^{\mu}$ is at most $m$, we can choose $p=(13n+1)m^2+1$. The construction is in polynomial time.

Now we can see in a valid permutation, the first $2n-1$ numbers must occupy the positions from $n+1$ to $3n-1$, and the next $2n$ numbers $y\_1,\bar{y}\_1,\ldots$ must occupy the positions $1,\ldots, n$ (say *low positions*) and $3n,\ldots, 4n-1$ (say *high positions*), where for each $i$, one of $y\_i,\bar{y}\_i$ occupies a low position and the other occupies a high position.

Suppose the instance of 3SAT is satisfiable. If $v\_i$ is assigned $1$, we arrange $y\_i$ at a high position and $\bar{y}\_i$ at a low position; otherwise we arrange $y\_i$ at a low position and $\bar{y}\_i$ at a high position. Now the numbers constructed in steps 1 and 2 are arranged. Consider $\sum\alpha\_i\pi\_i=\cdots+\lambda\_1p^{3n-2+1}+\cdots+\lambda\_m p^{3n-2+m}$ for these numbers. We can arrange $z\_j$ at position $16nm+j-\lambda\_j$ to satisfy the sum goal. Note at least one literal in a clause must be assigned $1$, i.e. its corresponding number ($y\_i$ or $\bar{y}\_i$) must be at a high position, hence we have

$$m\cdot 3n \< \lambda\_j\le m\cdot (4n-1+4n-2+4n-3)\<12nm,$$

i.e. $4nm+j\<16nm+j-\lambda\_j\<13nm+j\le (13n+1)m$, thus the positions for $z\_j$'s are valid. Also note $\lambda\_j$ is a multiple of $m$, then $16nm+j-\lambda\_j \equiv j \pmod m$, which means these positions do not conflict with each other. As a result, we have arranged these numbers such that $\sum\alpha\_i\pi\_i=x$.

On the other hand, if there is a permutation satisfying $\sum\alpha\_i\pi\_i=x$, then for each $i$, if $y\_i$ is arranged at a high position, we assign $v\_i=1$; otherwise we assign $v\_i=0$. Consider $\sum\alpha\_i\pi\_i=\cdots+\lambda\_1p^{3n-2+1}+\cdots+\lambda\_m p^{3n-2+m}$ for numbers constructed in steps 1 and 2, then the position of $z\_j$ must be $16nm+j-\lambda\_j$, which is a valid position, meaning $16nm+j-\lambda\_j\le (13n+1)m$, i.e. $\lambda\_j\>(3n-1)m$. This means at least one number ($y\_i$ or $\bar{y}\_i$) related to clause $c\_j$ is arranged a high position, which means the clause is satisfied.

---

For example, consider an instance with two clauses $\bar{v}\_1\vee v\_2\vee v\_3$ and $v\_1\vee \bar{v}\_2\vee v\_3$, the numbers are:

```
           p^0  p^1  p^2  p^3  p^4  p^5  p^6  p^7  p^8  p^9
                                    v_1  v_2  v_3  c_1  c_2
u_1        1
u_2             1
u_3                  1
u_4                       1
u_5                            1
y_1                                 1                   2
\bar{y}_1                           1              2
y_2                                      1         2
\bar{y}_2                                1              2
y_3                                           1    2    2
\bar{y}_3                                     1
z_1                                                1
z_2                                                     1
0
0
...
-----------------------------------------------------------
x          4    5    6    7    8    12   12   12   96   97

```

There are $80$ numbers in total. (One of) the permutation(s) corresponding to the solution $v\_1=v\_2=v\_3=1$ is $\bar{y}\_1\bar{y}\_2\bar{y}\_3u\_1u\_2u\_3u\_4u\_5y\_1y\_2y\_30\cdots 0z\_1z\_20\cdots$ where $z\_1$ is at position $73$ and $z\_2$ is at position $74$.

---

If the numbers are upper-bounded by a **constant**, say $100$, then the problem can be solved in polynomial time.

Let $f(\alpha, x)$ denote whether such permutation exists. Note for any permutation $\pi$, suppose $\alpha\_k$ is placed at the first position (i.e. $\pi\_k=1$), we have $$\sum \alpha\_i\pi\_i=\alpha\_k+\sum\_{i\neq k}\alpha\_i\pi\_i=\sum \alpha\_i+\sum\_{i\neq k}\alpha\_i(\pi\_i-1),$$ which means the primary problem has a valid solution iff there exists $k$ such that the subproblem for sequence $\alpha-\alpha\_k$ (meaning the sequence $\alpha\_1,\ldots,\alpha\_{k-1},\alpha\_{k+1},\ldots$) and target $x-\sum \alpha\_i$ has a valid solution, so we have

$$f(\alpha,x)=\bigvee\_{i=1}^n f\left(\alpha-\alpha\_i,x-\sum\_{j=1}^n \alpha\_j\right).$$

Note we do not care the order of the sequence, so every subsequence of $\alpha$ can be expressed as "$n\_1$ $1$s, ..., $n\_{100}$ $100$s", which means there are up to $n^{100}$ different subsequences of $\alpha$. Therefore, we can compute $f(\alpha,x)$ using the recursion formula above in $O(n\cdot xn^{100})=O(n^{103})$ time.
> 3 votes

---
Tags: algorithms, np-complete, decision-problem, permutations
---


# Question
Title: Define a grammar to emmulate chess rules
Is it possible to define a 《chess language》: language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}?

I looked online but I cannot find a way to define the grammar. Every way I can think of, is either stupidly long and complicated, or does not cover all the rules.

I presume the hard part is that the grammar has to take in consideration the state of the board before evaluating a move as valid or not.

Do you have insight how to approach this problem i.e: define a grammar that emulates chess rules?

The way chess apps work(not engines), is that at every move they calculate all possible moves and then check if the user's move is among the calculated moves, else it is invalid.

I want to accept the user's move and only then check if it's a valid one.

# Answer
> 1 votes
"The way chess apps work(not engines), is that at every move they calculate all possible moves and then check if the user's move is among the calculated moves, else it is invalid."

No, no, no, no, that's not how you check if a move is valid.

If you want all possible moves, then you generate all possible moves. If you want to check if a move is valid, then you check if that move is valid, and nothing else. There's no reason to know anything about all the other moves *if all you want to know is to check if one move is valid*.

---
Tags: formal-languages, regular-languages, automata, formal-grammars
---


# Question
Title: Finding minimum spanning tree of a special form graph
I'm trying to find an efficient algorithm that will find me the **minimum spanning tree** of an **undirected**, **weighted graph** of this particular form:

My idea was a recursive solution: Suppose the algorithm recieve the graph with n as a parameter,

```
if n==2 then:
    take the lower cost path between vo-->v1-->v2 and v0-->v2
if n==1 then:
    take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1
else:
    - recursivly call the algorithm for n-1
    - take the lower cost edge between v0-->vn and v(n-1)-->vn

```

I'm really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.

Any suggestions would be much appreciated.

# Answer
> 3 votes
That recursive algorithm is wrong, although it was an interesting attempt to improve established algorithms on specialized graphs.

Here is a counterexample with $n=3$.

The graph above was drawn at https://graphonline.ru/en

All edges weigh 2 except that the rightmost two edges, $(v0,v3)$ and $(v2,v3)$ weigh 1. The recursive algorithm will pick only one edge from the rightmost two edges while an MST must include both of them.

By the way, I cannot understand clearly the description of the algorithm in the case of $n=1$ and in the case of $n=2$. Fortunately (or unfortunately), that does not affect this answer since the counterexample depends only on the "else" branch of the algorithm, which is described clearly.

---
Tags: algorithms, graphs, correctness-proof, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Why is deep learning hyped despite bad VC dimension?
The Vapnik–Chervonenkis (VC)-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. The number of training samples needed to have a strong guarantee of generalization is linear with the VC-dimension.

This means that for a network with billions of edges, as in the case of successful deep learning models, the training dataset needs billions of training samples in the best case, to quadrillions in the worst case. The largest training sets currently have about a hundred billion samples. Since there is not enough training data, it is unlikely deep learning models are generalizing. Instead, they are overfitting the training data. This means the models will not perform well on data that is dissimilar to the training data, which is an undesirable property for machine learning.

Given the inability of deep learning to generalize, according to VC dimensional analysis, why are deep learning results so hyped? Merely having a high accuracy on some dataset does not mean much in itself. Is there something special about deep learning architectures that reduces the VC-dimension significantly?

If you do not think the VC-dimension analysis is relevant, please provide evidence/explanation that deep learning is generalizing and is not overfitting. I.e. does it have good recall AND precision, or just good recall? 100% recall is trivial to achieve, as is 100% precision. Getting both close to 100% is very difficult.

As a contrary example, here is evidence that deep learning is overfitting. An overfit model is easy to fool since it has incorporated deterministic/stochastic noise. See the following image for an example of overfitting.

Also, see lower ranked answers to this question to understand the problems with an overfit model despite good accuracy on test data.

Some have responded that regularization solves the problem of a large VC dimension. See this question for further discussion.

# Answer
> 96 votes
"If the map and the terrain disagree, trust the terrain."

It's not really understood why deep learning works as well as it does, but certainly old concepts from learning theory such as VC dimensions appear not to be very helpful.

The matter is hotly debated, see e.g.:

Regarding the issue of *adversarial examples*, the problem was discovered in:

It is further developed in:

There is a lot of follow-on work.

**Update March 2020.** A new hypothesis that appears to explain some of the mismatch between clear over-parameterisation of modern (feed-forward) NNs and good recognition performance is Frankle and Carbin's *Lottery Ticket Hypothesis* from 2018:

The claim is that a "randomly-initialised, dense \[feed-forward\] neural network contains a subnetwork that is initialised such that when trained in isolation it can match the test accuracy of the original network after training for at most the same number of iterations." Regarding the original question, the Lottery Ticket Hypothesis might be understood as saying that:

* Training by stochastic gradient descent searches for small subnetworks that work well and deemphasises the rest of the overparameterised network's learning capacity.
* The bigger the original network, the more likely it is to contain a small subnetwork with good performance on the task at hand.

This has found empirical support, e.g. in

and theoretical support in:

As far as I'm aware, it has not yet been possible to generalise the Lottery Ticket Hypothesis to recurrent NNs.

**Update March 2021.** The original 2016 paper Understanding Deep Learning Requires Rethinking Generalization has been updated. Here is the new version:

C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding Deep Learning (Still) Requires Rethinking Generalization.

# Answer
> 70 votes
> "Given the inability of Deep Learning to generalize, according to VC dimensional analysis \[...\]"

No, that's not what VC dimensional analysis says. VC dimensional analysis gives some sufficient conditions under which generalization is guaranteed. But the converse ain't necessarily so. Even if you fail to meet those conditions, the ML method still might generalize.

Put another way: deep learning works better than VC dimensional analysis would lead you to expect (better than VC analysis "predicts"). That's a shortcoming of VC dimensional analysis, not a shortcoming of deep learning. It doesn't imply that deep learning is flawed. Rather, it means that we don't know why deep learning works as well as it does -- and VC analysis is unable to provide any useful insights.

High VC dimension does not imply that deep learning can be fooled. High VC dimension doesn't guarantee anything at all about whether it can be fooled in practical situations. VC dimension provides a unidirectional, worst-case bound: if you meet these conditions, then good things happen, but if you don't meet these conditions, we don't know what will happen (maybe good things will still happen anyway, if nature behaves better than the worst possible case; VC analysis doesn't promise that good things *can't*/*won't* happen).

It could be that the VC dimension of the model space is large (it includes very complex patterns as possible), but nature is explained by simple patterns, and the ML algorithm learns the simple pattern present in nature (e.g., because of regularization) -- in this case, VC dimension would be high but the model would generalize (for the particular pattern that is present in nature).

That said... there is growing evidence that deep learning *can* be fooled by adversarial examples. But be careful about your chain of reasoning. The conclusions you are drawing don't follow from the premises you started with.

# Answer
> 26 votes
Industry people have no regard for VC dimension, hooligans...

On a more serious note, although the PAC model is an elegant way to think about learning (in my opinion at least), and is complex enough to give rise to interesting concepts and questions (such as VC dimension and its connection to sample complexity), it has very little to do with real life situations.

Remember that in the PAC model you are required to handle arbitrary distributions, this means that your algorithm should handle adversarial distributions. When trying to learn some phenomena in the real world, no one is giving you "adversarial data" to mess up your results, so requiring a concept class to be PAC learnable might be way too strong. Sometimes you can bound the generalization error independently of the VC dimension, for a specific class of distributions. This is the case of margin bounds, who are formulated independently of the VC dimension. They can promise low generalization error if you can guarantee high empirical margin (which of course, cannot happen for all distributions, e.g. take two close points on the plane with opposite tags, and focus the distribution on them).

So, putting the PAC model and VC dimension aside, I think the hype comes from the fact they just seem to work, and succeed in tasks that were previously not possible (one of the latest achievements that comes to mind is AlphaGo). I know very little about neural nets, so I hope someone with more experience will pitch in, but to my knowledge there are no good guarantees yet (definitely not like in the PAC model). Perhaps under the right assumptions one could justify formally the success of neural nets (I assume there are works around the formal treatment of neural nets and "deep learning", so I'm hoping people with more knowledge on the subject could link some papers).

# Answer
> 15 votes
> Given the inability of Deep Learning to generalize,

I don't know where you take that from. Empirically, generalization is seen as the score (e.g. accuracy) on unseen data.

The answer why CNNs are used is simple: **CNNs work much better than anything else**. See ImageNet 2012 for example:

* CNNs: 15.315% (that was an early example. CNNs are much better now. At about 4% top-5 error)
* Best non-CNN: 26.172% Top-5-error (source \- up to my knowledge techniques which do not use CNNs didn't get below 25% top-5 error)

Create a classifier which is better and people will shift to that.

> UPDATE: I will award an answer to anyone providing published evidence that machine learning in general is easily fooled, like this evidence for Deep Learning.

This is not the case. You can create a classifier which is extremely simple on a simple dataset. It will not be possible to fool it (it doesn't even matter what "easy" means) , but it also is not interesting.

# Answer
> 12 votes
The one word answer is "regularization". The naive VC dimension formula does not really apply here because regularization requires that the weights not be general. Only a tiny (infinitesimal?) proportion of weight combinations have acceptable loss after regularization. The true dimension is many orders of magnitude less as a result, so generalization can occur with the training sets we have. The real life results bear out that overfitting isn't generally happening.

# Answer
> 3 votes
We address the paper: Understanding Deep Learning Requires Rethinking Generalization. in

Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior Charles H. Martin and Michael W. Mahoney

See: https://arxiv.org/pdf/1710.09553.pdf

Basically, we argue that the VC bounds are too loose because the fundamental approach and how the statistical limit that is taken is unrealistic.

A better approach lies in Statistical Mechanics, which considers a class of data dependent functions, takes the Thermodynamic limit (not just the limit of large numbers)

Moreover, we also point out how the natural discontinuities in deep need lead to a phase transitions in the learning curve, which we believe is being observed in the Google paper (above)

With regard to the limits, see section 4.2 of our paper

"Clearly, if we fix the sample size m and let \[the size of the function class\] N → ∞ , \[or vise versa, fix N, let m → ∞\] the we should not expect a non-trivial result, since \[N\] is becoming larger but the sample size is fixed. Thus, \[in Statistical Mechanics\] one typically considers the case that m, N → ∞ such that α = m/N is a fixed constant."

That is, very rarely would we just add more data (m) to a deep net. We always increase the size of the net (N) too, because we know that we can capture more detailed features / information from the data. Instead we do in practice what we argue for in the paper--take the limit of large size, with the ratio m/N fixed (as opposed to say fixing m and let N increase).

These results are well known in the Statistical Mechanics of Learning. The analysis is more complicated, but the results lead to a much richer structure that explains many phenomena in deep learning.

Also, and in particular, it is known that many bounds from statistics become either trivial or do not apply to non-smooth probability distributions, or when the variables take on discrete values. With neural networks, non-trivial behavior arises because of discontinuities (in the activation functions), leading to phase transitions (which arise in the thermodynamic limit).

The paper we wrote tries to explain the salient ideas to a computer science audience.

Vapnik himself realized that his theory was not really applicable to neural networks...way back in 1994

"The extension of \[the VC dimension\] to multilayer networks faces \[many\] difficulties..the existing learning algorithms can not be viewed as minimizing the empirical risk over the entire set of functions implementable by the network...\[because\] it is likely...the search will be confined to a subset of \[these\] functions...The capacity of this set can be much lower than the capacity of the whole set...\[and\] may change with the number of observations. This may require a theory that considers the notion of a non-constant capacity with an 'active' subset of functions"
Vapnik, Levin, and LeCun 1994

http://yann.lecun.com/exdb/publis/pdf/vapnik-levin-lecun-94.pdf

While not easy to treat with VC theory, this is not an issue for stat mech..and what they describe looks very much like Energy Landscape Theory of protein folding. (which will be the topic of a future paper)

# Answer
> 2 votes
No one seems to have pointed out in the above answers, that the VC dimension formula quoted is only for a 1-layer neural network. My guess is that the VC dimension actually grows **exponentially** as the number of layers L increases. My reasoning is based on considering deep neural networks where the activation function is replaced by polynomial ones. Then the degree of the composed polynomials grows exponentially as the layers increase.

---
Tags: machine-learning, vc-dimension
---


# Question
Title: Is there a complexity class “BQP without error”?
I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm never fails. Another way of asking would be: is there a class (call it Q) such that Q is to P what BQP is to BPP?

I guess classically the question also makes sense: is there a class for problems that can be solved efficiently by a computer with access to randomness and never making an error? (I suspect this is simply equal to P?)

# Answer
Yes, it's called EQP (exact quantum polynomial) and is listed in the complexity zoo:

> The same as BQP, except that the quantum algorithm must return the correct answer with probability 1, and run in polynomial time with probability 1. Unlike bounded-error quantum computing, there is no theory of universal QTMs for exact quantum computing models. In the original definition in \[BV97\], each language in EQP is computed by a single QTM, equivalently to a uniform family of quantum circuits with a finite gate set K whose amplitudes can be computed in polynomial time. See EQP\_K. However, some results require an infinite gate set. The official definition here is that the gate set should be finite.
> 3 votes

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


title: FPTAS definition

text:
# Question
Title: FPTAS definition
I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/\epsilon$. However, this leaves some ambiguity.

For example, $T(n,1/\epsilon)=\min(n^{1/\epsilon},(1/\epsilon)^n)$ is both polynomial in $n$ (when holding $1/\epsilon$ constant) and polynomial in $1/\epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/\epsilon$ or $(n+1/\epsilon)$ because $\sqrt x^\sqrt x$ and $(x/2)^{x/2}$ aren't bounded by polynomials.

Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/\epsilon$?

# Answer
The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/\epsilon$" means. Judging from examples, it means $O(n^C(1/\epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/\epsilon)^C)$.
> 2 votes

---
Tags: algorithms, complexity-theory, terminology
---


title: Random walk increasing distance

text:
# Question
Title: Random walk increasing distance
I'm wondering why if I increase the number of step in a set of simulation of a random walk on a grid the distance from the origin is higher.

If I can move on the grid in 4 directions, there are 0.5 chance of getting closer to origin and 0.5 of getting farther.

This is a simple javascript example (well, here maybe I made some other errors because the points ends always with a negative x and a positive y, or maybe I just cannot rely on javascript random function in this case)

```
var steps = 100; //number of steps for each simulation (initially)
var simulations = 100; //number of total simulation
var points = Array.from({length:simulations}, () => ({x:0,y:0})); // init the array of points from the origin

//the 4 possible moves
var moves = [{x:0,y:1},{x:1,y:0},{x:0,y:-1},{x:-1,y:0}];
//ranom util function
var random = (max) => parseInt(Math.random() * max)

for (var s=0;s < simulations;s++) {
    //note the steps are increasing: 100,200,300,...,1000
    for (var i=1;i <= steps * s;i++) {
        let move = moves[random(4)];
        //console.log(move)
        points[s].x += move.x
        points[s].y += move.y
        //console.log(s, move)
    }
    console.log(`simulation n.${s} total steps: ${steps*s}`, points[s].x, points[s].y, `distance: ${Math.abs(points[s].x) + Math.abs(points[s].y)}` )

}

```

**EDIT**: thanks to @GASSA I fixed my code, but watching the results I'm still in doubt: **the distance actually is not increased** (see the graph below). Not sure what's the problem..

# Answer
It's easiest to understand with a one-dimensional random walk. After $n$ steps, the typical value for the distance from the origin is proportional to $\sqrt{n}$. Thus, the more steps you take, the greater the typical distance from the origin. For an analysis and explanation, see https://en.wikipedia.org/wiki/Random\_walk#One-dimensional\_random\_walk. The math is well-developed in many standard places, so I'm not going to repeat it here.
> 4 votes

# Answer
A two-dimensional random walk is equivalent to two independent one-dimensional random walks running in parallel. To see this, rotate the plane 45 degrees. The possible steps are all four diagonals, and each one corresponds to both a step in the horizontal direction and a step in the vertical direction.

The horizontal displacement after $n$ steps is the sum of $n$ random $\pm 1$ steps. According to the central limit theorem, its distribution is roughly normal with mean zero and variance $n$. Consequently, the absolute horizontal displacement is of expected order $\sqrt{n}$. The same is true for the absolute vertical displacement, and so for the distance from the origin.
> 1 votes

---
Tags: random-walks
---


# Question
Title: Recurrence Substitution Method with multiple givens
Solve by using the substitution method $T(n)=T(n-1)+2T(n-2)+3$
Given $T(0)=3$ and $T(1)=5$

I kind of understand it with only one given and one recurrence call by expanding the call using what is inside.
ex. if it was $T(n)=T(n-1)+3$
Given $T(1)=5$
I would take the $n-1$ and plug it into the the first equation $T(n)=T(n-1)+3$
and repeat until I can find a general case. After that simplify it to get my answer.

My problem is when I have two givens and two recurrences. I first though about solving each one separately using the first recurrence and then the second but it wasn't making any sense to me.

# Answer
Let $S(n) = T(n) + 1.5$. Then $$ S(n) = T(n) + 1.5 = T(n-1) + 2T(n-2) + 4.5 = S(n-1) + 2S(n-2). $$ The recurrence $S(n) = S(n-1) + 2S(n-2)$ is homogeneous with constant coefficients, so we know how to solve it. We first solve the equation $\lambda^2 = \lambda + 2$, finding that the solutions are $2,-1$. This implies that there exist constants $A,B$ such that $$ S(n) = A 2^n + B (-1)^n. $$ Since $S(0) = 4.5$ and $S(1) = 6.5$, we see that $A + B = 4.5$ and $2A - B = 6.5$, from which we find that $A = 11/3$ and $B = 5/6$. Therefore $$ T(n) = \frac{11}{3} 2^n + \frac{5}{6} (-1)^n - \frac{3}{2}. $$
> 1 votes

---
Tags: algorithms, time-complexity, recurrence-relation
---


title: DFS algorithm (directed graph)

text:
# Question
Title: DFS algorithm (directed graph)
If you have a back edge in a directed graph, then you may have a cycle or must have a cycle?

# Answer
> 0 votes
Yes. Back edge is a method to detect cycle in the directed graph.

---
Tags: graphs
---