# Question
Title: Finding all partitions of a grid into k connected components
I am working on floor planing on small orthogonal grids. I want to partition a given $m \times n$ grid into $k$ (where $k \leq nm$, but usually $k \ll nm$) connected components in all possible ways so that I can compute a fitness value for each solution and pick the best one. So far, I have the fitness evaluation at the end of the algorithm, no branch-and-bound or other type of early-termination, since the fitness function is specified by users and usually requires the complete solution.

My current approach to listing all possible grid partitions into connected components is quite straight forward and I am wondering what optimizations can be added to avoid listing duplicate partitions? There must be a better way than what I have right now. I know the problem is NP, but I would at like to push my algorithm from brute-force to a smart and efficient approach.

## Overview

For better visualization and description I will reformulate the task to an equivalent one: paint the grid cells using $k$ colors so that each color builds a single connected component (with respect to 4-neighborhood) and of course all grid is completely painted.

My approach so far:

1. Generate all seed scenarios. A seed scenario is a partial solution where each color is applied to a single cell only, the remaining cells are yet empty.
2. Collect all possible solutions for each seed scenario by expanding the color regions in a DFS manner.
3. Filter out duplicate solutions with help of a hash-table.

## Seed scenarios

I generate the seed scenarios as permutations of $k$ unique colors and $mn-k$ void elements (without repetition of the voids). Hence, the total number is $(nm)! / (mn-k)!$ For example, for a $1 \times 4$ grid and colors ${0, 1}$ with *void* denoted as $\square$ the seed scenarios are:

* $\[0 1 \square \square\]$
* $\[0 \square 1 \square\]$
* $\[0 \square \square 1\]$
* $\[1 0 \square \square\]$
* $\[1 \square 0 \square\]$
* $\[1 \square \square 0\]$
* $\[\square 0 1 \square\]$
* $\[\square 0 \square 1\]$
* $\[\square 1 0 \square\]$
* $\[\square 1 \square 0\]$
* $\[\square \square 0 1\]$
* $\[\square \square 1 0\]$

## Seed growth / multicolor flood-fill

I assume the painting to be performed in a fixed ordering of the colors. The seed scenario always comes with the first color set as the current one. New solutions are generated then either by switching to the next color or by painting empty cells by the current color.

```
//PSEUDOCODE
buffer.push(seed_scenario with current_color:=0);
while(buffer not empty)
{
    partial_solution := buffer.pop();
    if (partial_solution.available_cells.count == 0)
        result.add(partial_solution);
    else
    {
        buffer.push(partial_solution.nextColor()); //copy solution and increment color
        buffer.pushAll(partial_solution.expand()); //kind-of flood-fill produces new solutions
    }
}

```

`partial_solution.expand()` generates a number of new partial solutions. All of them have one additional cell colored by the current color. It examines the current region boundary and tries to paint each neighboring cell by the current color, if the cell is still void.

`partial_solution.nextColor()` duplicates the current partial solution but increments the current painting color.

This simple seed growth enumerates all possible solutions for the seed setup. However, **a pair of different seed scenarios can produce identical solutions**. There are indeed many duplicates produced. So far, I do not know how to take care of that. So I had to add the third step that filters duplicates so that the result contains only distinct solutions.

## Question

I assume there should be a way to get rid of the duplicates, since that is where the efficiency suffers the most. Is it possible to merge the seeds generation with the painting stage? I started to thing about some sort of dynamic programming, but I have no clear idea yet. In 1D it would be much easier, but the 4-connectivity in a 2D grid makes the problem much harder. I tried searching for solutions or publications, but didn't find anything useful yet. Maybe I am throwing in the wrong keywords. So any suggestions to my approach or pointers to literature are very much appreciated!

## Note

I found Grid Puzzle Split Algorithm, but not sure if the answers can be adapted to my problem.

## Further thoughts (update #1)

I started to think in the following direction. If there are two connected components, their union will be connected as well. So I could proceed in a divide-and-conquer way:

1. Generate all distinct 2-partitions (connectivity condition must hold of course).
2. For each solution from (1) paint one component with one of the available colors and recursively apply (1) to the second component using the remaining colors. Terminate each branch once all colors have been used for at least one cell.

This is a very rough idea, but I believe it should avoid duplicates. I will investigate further if I can prove it. But still, how to generate all distinct 2-partitions of a 2D grid efficiently remains an open question for me.

# Answer
# Two components

Here is an algorithm you can use to enumerate the ways to partition any graph (including a grid) into $k=2$ connected components, say a red component and a blue component. Let's define the "size" of such a partition to be the number of vertices in the red component.

The algorithm: generate all partitions of size 1; then generate all partitions of size 2; then all partitions of size 3; and so on.

Given all partitions of size $s$, you can enumerate all partitions of size $s+1$ as follows: pick a partition of size $s$, let $R$ denote the set of red vertices in that partition, pick a blue vertex $v \notin R$ that is adjacent to some red vertex in $R$; construct a new partition of size $s+1$ with red vertices $R' = R \cup \\{v\\}$ and blue vertices $V \setminus R'$; and test whether the blue vertices form a connected component.

The base case is that you can easily enumerate all partitions of size 1: each is just a single vertex, and you can choose any one vertex you want. (If you consider two partitions equivalent if one can be obtained from the other by swapping colors, and you only want to enumerate partitions up to equivalence, then it suffices to enumerate only those partitions where the first vertex is colored red. In that case, there is only one partition of size 1: the first vertex is red and the rest are blue.)

To make this run efficiently, I suggest you store a hashtable of all partitions of size $1$, a hashtable of all partitions of size $2$, and so on. The hash function will map a partition to a unique hashcode, by hashing the set of red vertices. This way you can efficiently test whether a partition generated using the above procedure is new or a duplicate, and avoid adding duplicates more than once. This will also allow you to enumerate all partitions of a given size.

To help make it more efficient to enumerate all vertices that are adjacent to some red vertex, I suggest you store each subset as a set of red vertices on the fringe and a set of red vertices on the interior. (The "fringe" are the red vertices in $R$ that are adjacent to at least one blue vertex; the interior are the rest of the red vertices.) This makes it easy to enumerate over all blue vertices that are adjacent to some red vertex in $R$ (by traversing the fringe and enumerating their neighbors).

With these methods, you can enumerate all such connected components in at most $O(N^2 2^N)$ time, where $N$ is the number of vertices in the graph ($N=mn$ in your example), and probably substantially less in practice.

# Multiple components

We can generalize this to handle an arbitrary number $k\ge 2$ of connected components, as follows. First, pick a partition of the graph into 2 components, one red and one blue. Then, pick a way to partition the blue component into two connected components, say one violet and one cyan. Repeat $k-1$ times, in each step partioning the last component, until you have $k$ components. If you at each stage you enumerate over all choices, at the end you will have enumerated all ways to partition the graph into $k$ connected components.

(If you consider two partitions equivalent if one can be obtained from the other by permuting the colors, then it suffices to enumerate the ways to partition into two components up to equivalence.)

The running time of this algorithm will be very bad: it might be close to $k^N$. So, this will only be useful when the number $N$ of vertices in the graph is very small.
> 0 votes

---
Tags: graphs, dynamic-programming, partitions
---


# Question
Title: Gap between numbers in fixed-point vs. floating point arithmetic
If $r$ is a machine-representable number and $f(r)$ is the next larger machine representable number, are the following true or false?

1. In fixed-point arithmetic, the distance between $r$ and $f(r)$ is constant.
2. In floating-point arithmetic, the relative distance $|(f(r)-r)/r|$ is constant.

I believe that (1) is true, but I'm not sure about (2). I am new to the world of numerical analysis and I'm just trying to hang on for dear life. Could anybody point me to a resource that does a good job of explaining the basic introductory topics of machine mathematics?

# Answer
1. Yes, the difference is constant.
2. It is not really constant, but approximately, yes. With exceptions.

With binary floating point numbers, the expression $(f(r)−r)/r$ is constant within a factor of $2$. It is between $1 \over 2^m$ and $1 \over 2^{m-1}$ where m is the number of bits in the mantissa. For rounding error calculations, you can assume it is constant.

A note on 0:
Obviously, you cannot apply the formula when $r=0$. But it is important to know that while $f(r)-r$ decreases when $r$ becomes small, $f(0)-0$ is much larger than, for instance, $f(f(r))-f(r)$. There is a huge non-representable gap around $0$.
> 5 votes

# Answer
(1) Yes, the numbers in fixed point arithmetic are just scaled integers.

(2) No, by a short counterexample. The floating-point arithmetic represents numbers as $r = i \times b^j$. Let us pick a random base, e.g. $b = 10$ and create the smallest positive number $r = 1 \times 10^m$. Let $m \< 0$ be the minimal possible exponent (its size depends on the number of bits assigned to the exponent).

Now the next two numbers are $f(r) = 2 \times 10^m$ and $f(f(r)) = 3 \times 10^m$. After inserting them into your equation $$|(2 \times 10^m - 1 \times 10^m) / 10^m| = 1$$ however $$|(3 \times 10^m - 2 \times 10^m) / (2 \times 10^m)| = 0.5$$
> 4 votes

# Answer
For ieee754 floating point numbers (the most common) we have abs(f(r) - r) \<= c with a rather small c as long as r is in the range of normalised numbers. For tiny numbers (denormalised) it behaves like fixed point.

You get better bounds if you assume that $2^k \<= x \< 2 \cdot 2^k$ with an error \<= $c \cdot 2^k$, especially if x is slightly smaller than some power of two - you can often improve the precision of an algorithm if you can arrange things so intermediate results are slightly smaller than powers of two.
> 0 votes

---
Tags: numerical-analysis, floating-point
---


title: Bellman Ford Dynamic Programming

text:
# Question
Title: Bellman Ford Dynamic Programming
I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so many unnecessary re-computations, it is not exactly efficient in the likes of other dynamic programming that computes the sub-problems bottom up to the final problem. For example, FloyWarshall has a well defined sub structure of considering all other vertices up to k.

But for Bellman Ford, the implementation is not really relying on any computed sub problems, it is just a brute force algorithm that correctly returns the shortest path but it is not correctly computing the sub-problems in some correct order needed by a dynamic programming algorithm?

# Answer
> 3 votes
Dynamic programming doesn't necessarily mean that your solution will be efficient. It just means that your problem can be defined using a recursive function, for which you can use memoization.

To understand what this function is, take a look at the proof. The invariant is "after $i$ iterations, we've found all shortest paths of length at most $i$". Therefore, we can define our function $f(v, \ell)$ \- the length of the shortest path to vertex $v$ with length at most $\ell$ \- in the following way:

$$f(v, \ell) = \min\_{u \ \in\ in(v)} (f(u, \ell-1) + d(u,v))$$

What Bellman-Ford does is slightly different (e.g. it can compute all shortest paths in a single iteration, if our order is lucky), but it can only help us, so we don't mind.

---
Tags: dynamic-programming, shortest-path
---


# Question
Title: Computing childrens of ith node of a d-ary tree
Assume that we represent a complete d-ary tree in an array\[1,...n\] (this is a 1-based array of size n).

The formula for indices of children of node no. i is given as:

{(1-i)d+2, ... , min{n,(1-i)d+d+1}}

I am not able to get the intuition to arrive at this formula. Can someone please help ?

# Answer
> 1 votes
The (traditional) binary heap (as e.g. in heapsort) is exactly your case, with $d = 2$; for 0-based arrays the children of $k$ are at $2 k + 1$ and $2 k + 2$. Analogously, in your case the children of $k$ are at $d k + 1, d k + 2, \dotsc, d k + d$.

The children of $0$ are at $1, 2, \dotsc, d$; children of $1$ start after that ($d + 1, d + 2, \dotsc, 2 d$), children of $2$ are at $2 d + 1, \dotsc, 3 d$, and so on. You should see the pattern here.

---
Tags: data-structures, trees, mathematical-analysis
---


# Question
Title: Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS
I was going through section of *Breadth First Search* of the text *Introduction to Algorithms* by *Cormen et. al.* and I faced difficulty in understanding a statement in the proof below which I have marked with $\dagger$

> Theorem: (**Correctness of breadth-first search**)
>
> Let $G = (V, E)$ be a directed or undirected graph, and suppose that $BFS$ is run on $G$ from a given source vertex $s \in V$. Then, during its execution, $BFS$ discovers every vertex $v \in V$ that is reachable from the source $s$, and upon termination, $d\[v\] = \delta(s, v)$ for all $v \in V$. Moreover, for any vertex $v \neq s$ that is reachable from $s$, one of the shortest paths from $s$ to $v$ is a shortest path from $s$ to $\pi\[v\]$ followed by the edge $(\pi\[v\], v)$.
>
> $\left\[ \delta(s,v) \rightarrow \text{Length of the shortest path from s to v}\\ d\[v\]\rightarrow \text{distance assigned to vertex $v$ from $s$ by BFS}\\\pi\[v\]\rightarrow \text{Predecessor of $v$ in the path from $s$ to $v$ in the BFS}\right\]$
>
> > **Proof**:
> >
> > Assume, for the purpose of contradiction, that some vertex receives a $d$ value not equal to its shortest path distance. Let $v$ be the vertex with minimum $\delta(s, v)$ that receives such an incorrect $d$ value; clearly $v \neq s$. We know $d\[v\] \geq \delta(s, v)$, and thus we have that $d\[v\] \> \delta(s, v)$. Vertex $v$ must be reachable from $s$, for if it is not, then $\delta(s, v) = \infty \geq d\[v\]$. Let $u$ be the vertex immediately preceding $v$ on a shortest path from $s$ to $v$, so that $\delta(s, v) = \delta(s, u) + 1$. Because $\delta(s, u) \< \delta(s, v)$, and ***because of how we chose $v$ , we have $d\[u\] = \delta(s, u)$$^\dagger$***. Putting these properties together, we have
> >
> > $d\[v\] \> \delta(s, v) = \delta(s, u) + 1 = d\[u\] + 1 $
> >
> > (The proof then continues, but I do not include the rest here...)

I could not understand the reasoning behind the statement marked with $\dagger$, $\text{"because of how we chose $v$ , we have $d\[u\] = \delta(s, u)$"}$

# Answer
> 2 votes
It is perhaps more illuminating to reformulate this proof by contradiction as a proof by induction. We prove that $d\[v\] = \delta(s,v)$ by induction on the latter (the case $\delta(s,v) = \infty$ should be taken care of separately). If $\delta(s,v) = 0$ then $v = s$, and indeed $d\[s\] = 0$. Now suppose that the result holds for all vertices at distance $i$ from $s$, and consider a vertex $v$ at distance $i+1$ from $s$. Let $u$ be a neighbor of $v$ at distance $i$ from $s$. By induction, $d\[u\] = \delta(s,u)$, and so once $u$ is processed, $d\[v\] \leq \delta(s,u) + 1 = \delta(s,v)$. Since $d\[v\] \geq \delta(s,v)$, it follows that $d\[v\] = \delta(s,v)$, as needed.

How do the two proofs relate? Let $U$ be the set of vertices such that $d\[v\] = \delta(s,v)$; clearly $s \in U$. Let $v \neq s$ be an arbitrary vertex reachable from $s$, and let $u$ be a predecessor of $v$, that is, a neighbor of $v$ such that $\delta(s,v) = \delta(s,u) + 1$. The proof shows that if $u \in U$ then also $v \in U$. You can now proceed in two different ways:

* Proof by contradiction: choose $v \in U$ minimizing $\delta(s,v)$. By definition, the predecessor of $v$ does lie in $U$, and so we reach a contradiction.
* Proof by induction: we show that all vertices reachable from $s$ are in $U$, by induction on their distance from $s$.

The two proofs are equivalent. I prefer the second.

---
Tags: algorithms, proof-techniques, shortest-path, graph-traversal
---


# Question
Title: Efficient Implementation of Boolean Lattice-Esque Operation
Let $X = \\{1,2,\dots n\\}$, and $Y\_i= \\{T \in \mathcal{P}(X): |T| \le i\\}$. I am interested in "avoidance sets" $A \subset Y\_n$. We say a subset $S \subset X$ is *valid* with respect to an avoidance set $A$ if $T \not \subseteq S$ for all $T \in A$.

We let $f(A)$ denote the set of $S\subset X$ that are valid with $A$. It may be helpful to note that $f(A' \cup A'') = f(A')\cap f(A'')$.

Given a list of avoidance sets $A\_1,A\_2,\dots A\_k \in Y\_2$, I want to return an avoidance set $A' \in Y\_2$ such $$\bigcup\_{1 \le i \le k} f(A\_i) \subseteq f(A')\tag{1}$$ and for any other $A'' \in Y\_2$ satisfying (1), we do not have $f(A'') \subsetneq f(A')$.

Can this be done in time linear to $\sum\_{1\le i \le k} |A\_i|$? (you may assume that all the sets $A\_i$ are simplified, i.e. if $\\{a\\}\in A\_i$ and $\\{b\\}\in A\_i$ then $\\{a,b\\} \not \in A\_i$)

**Context:**

The physical motivation behind my question is that I am trying to "roughly" keep track of events which must be avoided.

An element $x \in X$ corresponds to an "event" occurring in a probability space. A subset $S \subset X$ correspond to the intersection all the events $x\_1,x\_2 \dots x\_k \in S$ occurring at once.

An avoidance set $A$ is supposed to express certain events which have probability zero of occurring. (so $S \subset X$ is not valid with $A$ if the event corresponding to $S$ has zero probability) To keep the cost of space low, I have decided to concern myself with only working with avoidance sets in $Y\_2$. (thus this is a heuristic representation)

Now, let's say I am keeping track of avoidance sets $A\_i$ where $S$ is invalid with $A\_i$ represents that $S$ has probability zero given event $i$ happens. Now, if I know at least one of the events $A\_1,\dots A\_k$ occurs, then I am interested in finding $A'$.

# Answer
I believe the desired $A'$ is given by

$$A' = \\{T : \forall T' . T \subseteq T' \implies T' \notin \cup\_i f(A\_i)\\}.$$

Here is how to compute $A'$ in linear time from the $A\_i$'s. Basically, we want to include the set $T$ if: (1) for all $i$, there exists $T\_i \in A\_i$ such that $T\_i \subseteq T$ and (2) there exists $j$ such that $T \in A\_j$. You can find those sets as follows:

* For each $T \in A\_1 \cup \cdots \cup A\_k$:
    + Set flag := true.
    + For each $i := 1,2, \dots, k$:
        - If $\not\exists T\_i \in A\_i$ such that $T\_i \subseteq T$, set flag := false.
    + If flag := true, output $T$.

Naively, this seems likely to take quadratic time or more. However, since you're working in $Y\_2$, there is a more efficient algorithm. For each $i$, build a hashtable (an index) that, given $T$, lets you check whether $T \in A\_i$. Then, you can implement the algorithm above as:

* For each $T \in A\_1 \cup \cdots \cup A\_k$:
    + Set flag := true.
    + For each $i := 1,2, \dots, k$:
        - If $|T|=2$: suppose $T=\\{u,v\\}$; if $T \notin A\_i$ and $\\{u\\} \notin A\_i$ and $\\{v\\} \notin A\_i$, then set flag := false.
        - Otherwise if $|T|=1$: if $T \notin A\_i$, then set flag := false.
    + If flag := true, output $T$.

This can now be implemented in time proportional to $k \sum\_i |A\_i|$. I don't know whether this is efficient enough for you.

I think for this to work corretly in all cases, you might need to first convert each avoidance set $A\_i$ into canonical form. The canonical form of avoidance set $A$ is an avoidance set $A^\*$ with the smallest number of sets such that $f(A^\*)=f(A)$. When working in $Y\_2$ you can compute the canonical form with the following rules:

* Rule 1: If $\\{u,v\\} \in A$ and $\\{u\\} \in A$ or $\\{v\\} \in A$, delete $\\{u,v\\}$ from $A$.
* Rule 2: If $\\{x,u\\} \in A$ for each $x \in \\{1,\dots,n\\}\setminus\\{u\\}$, then add $\\{x\\}$ to $A$ and remove all $\\{x,u\\}$ from $A$.

You can enforce Rule 1 with a linear scan over $A$; and then you can enforce Rule 2 with a simple linear-time graph algorithm (build the undirected graph with an edge for each $\\{u,v\\} \in A$; check the degree of each vertex; apply Rule 2 to each vertex with degree $n-1$). So, at least when working in $Y\_2$, you can convert an avoidance set to canonical form in linear time. I haven't tried to think about a generalization to arbitrary $Y\_i$.
> 0 votes

---
Tags: sets, lattices
---


# Question
Title: foresightful acceleration and decelerations
I am programming a CNC machine (using matlab). In order to generate a surface with a "high" shape accuracy (order of $1\mu m$) and "small" micro roughness (order of few nm) I need to make sure that no large acceleration/decelerations takes place, because this would induce vibrations. If the amplitude of these vibrations exceeds approx. $50nm$ they would generate unwanted structures on the machined surface.

Since most people are not familiar with the CNC context, I like to transfer the problem to a car, which is driving down a street in 2D. As input to the program I have a 2D point cloud $(x,y)$, which represent the ideal path. The goal is to move along this ideal path as quickly as possible. However, not only should the change in position $(x, y)$ be smooth, but also the change of the accelerations $(a\_x, a\_y)$ -- we have to avoid vibrations.

The main problem I am currently facing is the deceleration. Since I like to move along the path as fast as possible, I accelerate the car till I reach it's maximal velocity. However, my code does not work well, if I reach a sharp edge. In order to stay within the given path the car has to "look ahead" and decelerate way before reaching the edge. Hence, I need to implement a foresightful driver. Are there simple methods available for this task? How would you implement this?

**Inputs:** The input is a dense point-cloud $(x,y)$ with a step side of $\Delta x = 1\mu m = \Delta y$. This raster is only used to define the surface.

**Outputs:** In order to achieve the high accuracy I have to use an external reference, which define a fixed time interval $\Delta t$. The path is defined as point-cloud $(x,y)$ in such a way, that the machine (car) gets one point per time interval:

> $$x\_1 y\_1$$ $$x\_2 y\_2$$ $$x\_3 y\_3$$

Hence, the velocity and the accelerations are defined by the point-cloud itself. Each point must be accurate to the $1nm$ level.

===

There are robotic communities, which did these kind of calculations. Here is one example: Link.

# Answer
I think an approach that will work is to "work backwards" through the path, keeping track of the maximum velocity that can be used at that point (subject to the restrictions on acceleration), then "work forwards" along the path, assigning a velocity at each point (subject to the restrictions on acceleration).

Represent the path as a sequence of evenly spaced points $P\_1,\dots,P\_n$, i.e., $P\_1$ is the start of the path, $P\_n$ is the end of the path, and $\\|P\_{i+1}-P\_i\\|\_2$ is the same for all $i$. At each point $P\_i$, you know the direction $D\_i$ the car will be heading: $D\_i$ is a unit-length vector that is tangent to the path at that point, so we can approximate $D\_i = (P\_{i+1}-P\_{i-1})/\\|P\_{i+1}-P\_{i-1}\\|\_2$, using vector arithmetic. I'll describe an algorithm to compute speeds $s\_1,\dots,s\_n$ so that $s\_i$ represents the speed of the car at point $P\_i$, and so that the acceleration constraints are satisfied. Then the car's velocity vector at point $V\_i$ will be $V\_i = s\_i D\_i$.

What constraints do the acceleration constraints impose on the $s\_i$? Well, I'll assume your goal is to impose an upper bound on the maximum acceleration allowed: in particular, I'll assume we have a constant threshold $c$ and we require that the acceleration vector $A\_i$ satisfies $\\|A\_i\\|\_2 \le c$ at every point. Notice $$A\_i = {V\_{i+1} - V\_i \over \\|V\_i\\|\_2/\\|P\_{i+1}-P\_i\\|},$$ so the constraint $\\|A\_i\\|\_2 \le c$ becomes

$$\\|s\_{i+1} D\_{i+1} - s\_i D\_i\\|\_2 \le c s\_i / \\|P\_{i+1}-P\_i\\|.$$

Given $s\_{i+1},D\_i,D\_{i+1}$, we can obtain an upper bound on the maximum allowable $s\_i$ that is consistent with this constraint, as the constraint is equivalent to

$$\\|s\_{i+1} D\_{i+1} - s\_i D\_i\\|\_2^2 - c' s\_i^2 \le 0,$$

where $c' = c \\|P\_{i+1}-P\_i\\|$ is a known constant. The left-hand side of that is a quadratic function in $s\_i$, so you can efficiently compute an upper bound on $s\_i$ by solving a quadratic equation. Moreover, given an upper bound on $s\_{i+1}$, we can obtain an upper bound on $s\_i$ by replacing $s\_{i+1}$ in the equation above with the upper bound and solving for the upper bound on $s\_i$.

So, our strategy during the backwards pass will be: at each point $P\_i$, we will compute an upper bound $u\_i$ on the maximum speed $\_i$ that the car can be permitted to have at that point. In particular, we'll choose $u\_i$ so we're assured that if the car has speed $u\_i$ or less at $P\_i$, then there is a way to complete the path so that from $P\_i \ldots P\_n$ the car satisfies all the constraints. We've already described how to do this: given $u\_{i+1}$ (an upper bound on $s\_{i+1}$), we described above how to compute $u\_i$ (the upper bound on $s\_i$). Thus, during the backwards pass, we will iterate through $i:=n,n-1,\dots,1$, setting at each step $u\_i$ based on $u\_{i+1}$. At the end of the backwards pass, we have computed all of the $u\_1,\dots,u\_n$.

Next, we will do the forwards pass, to assign a speed at each point. Iterate through the points in the order $i:=1,2,\dots,n$. At each step, we'll compute $s\_i$ based on $s\_{i-1}$ and $u\_i$. In particular, the acceleration constraints impose a constraint on $s\_i$: $\\|s\_{i} D\_{i} - s\_{i-1} D\_{i-1}\\|\_2^2 \le c' s\_i$. We also have the constraint $s\_i \le u\_i$. You can solve this to find the maximum possible value of $s\_i$ (it involves solving a quadratic equation), and assigning $s\_i$ this value. Continue forward along the path, until you have assigned speeds $s\_1,\dots,s\_n$ for the entire path.

The result will be a valid plan for how to traverse the path. In particular, at point $P\_i$, the car will be travelling at speed $s\_i$. While at point $P\_i$, you will accelerate or decelerate the car so that by point $P\_{i+1}$ it is travelling at speed $s\_{i+1}$. This can be done by using the gas pedal or brake pedal to accelerate by $A\_i \cdot D\_i$, where $A\_i = s\_{i+1} D\_{i+1} - s\_i D\_i$ (this will ensure acceleration in the $D\_i$ direction of the acceleration vector $A\_i$), using the steering to stay on the road (this will ensure acceleration in the direction perpendicular to $D\_i$ to stay on the road).

This solution assigns the maximum possible speed at each point, and thereby traverses through the path in the fastest way possible, while respecting the limits on acceleration at every point along the path.
> 2 votes

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


title: PDA kleene star construction

text:
# Question
Title: PDA kleene star construction
I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).

# Answer
> 2 votes
Use a PDA. Suppose you have a PDA for language $L$ and you want to recognize $L^\*$. Given an input $x$, it is in $L^\*$ if it can be partitioned as the concatenation $x=x\_1 \cdots x\_n$ of words $x\_i$, where each $x\_i \in L$. Construct a PDA as follows: the PDA nondeterministically guesses the end of each $x\_i$ (the boundary between $x\_i$ and $x\_{i+1}$); if it guesses that it is at a boundary, it checks that it is in an accept state and then pops everything off the stack and then transitions to its start state and continues from there.

---
Tags: context-free, pushdown-automata, closure-properties
---


# Question
Title: Prove that the language is not regular through Myhill-Nerode Equivalence
The language is given by: $$L=\\{a^nb^m|n\<m\\}$$ I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence. Any help would be appreciated.

# Answer
You have to find an infinite set of strings $s\_i$ such that for every two strings $s\_i ≠ s\_j$, there is a string $t\_{ij}$ such that exactly one of $s\_i t\_{ij}$ and $s\_j t\_{ij}$ is in the language, and the other is not.

Now if you look at $a^n$ and $a^m$, n ≠ m, can you find a string t such that exactly one of $a^n t$ and $a^m t$ is in the language, and the other is not?
> 4 votes

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


# Question
Title: Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?
Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum\_{i=0}^n\sqrt{i}\log\_2^2i \geq \Omega(n\sqrt{n}\log\_2n)$?

1. How can the function on the left be compared to a whole set? I thought usually a function is an element of the set, i.e. $g\in\Omega(f)$ or it is not, i.e. $g\notin\Omega(f)$.
2. If it would say $\sum\_{i=0}^n\sqrt{i}\log\_2^2i \in \Omega(n\sqrt{n}\log\_2n)$ instead, I still would not understand why it is true. How do you evaluate the limit of the left side?

# Answer
The notations $f = \Omega(g)$ and $f \geq \Omega(g)$ are identical. In both cases, they mean that there exists a positive constant $C$ such that for large $n$, $f(n) \geq Cg(n)$.

You can estimate the sum as follows: $$ \sum\_{i=0}^n \sqrt{i} \log\_2^2 i \geq \sum\_{i=n/2}^n \sqrt{i} \log\_2^2 i \geq \sum\_{i=n/2}^n \sqrt{n/2} \log\_2^2 (n/2) \geq \frac{n}{2} \cdot \sqrt{n/2} \log\_2^2 (n/2). $$ The latter expression is $\Omega(n^{3/2} \log^2 n)$, which is better than what you claim.

You can also estimate the sum by an integral. According to Wolfram alpha, $$ \int \sqrt{x} \log^2 x \\, dx = \frac{2}{27} x^{3/2} (9\log^2 x - 12 \log x + 8) + C. $$ Since $\sqrt{i} \log\_2^2 i$ is increasing, we have $$ \int\_0^n \sqrt{x} \log^2 x \\, dx \leq \sum\_{i=1}^n \sqrt{i} \log^2 i \leq \int\_1^{n+1} \sqrt{x} \log^2 x \\, dx, $$ from which we see that your sum is $\Theta(n^{3/2} \log^2 n)$.
> 1 votes

---
Tags: runtime-analysis, landau-notation
---


# Question
Title: If we want to map abbreviations of full-English words (e.g. map "Jan" to "January"), how can we identify abbreviations which map to multiple words?
## Short Version:

How can we construct a trie which maps abbreviations of names-of-the-month to full-month (we map the abbreviation "mar" to "march")?

> * The set of all abbreviations is formed by:
>     + keeping the first letter of the month name. (all abbreviations of "`january`" begin with "`j`")
>     + deleting 1 or more characters ("`jan`" deletes "`uary`" from "`january`"; "`jar`" deletes "`nuay`" from "`january`")

### The Long Version:

> How can we construct such a ***trie***?
> What algorithm will build the appropriate ***trie*** from the container of ***verbose*** strings?

Consider the English names for months of the year:

* January
* February
* March
* April
* \[... truncated ...\]
* October
* November
* December

We find it useful say that the English names for months of the year are "***verbose***" strings.
For any "***verbose***" string $v$, and any string $a$ we say that $a$ is an "***abbreviation***" of $v$ if and only if all of the following conditions are met:

* $a$ non-empty. $|a| \geq 1$
* $a$ can formed by deleting 1 or more characters from "***verbose***" string $v$
* $a(1) = v(1)$. Assume that string indexing begins at $1$, and not $0$.

For example, "`jan`" is an abbreviation of "`january`."

Suppose you want to write an algorithm which:

* accepts a list of ***verbose*** strings as inputs.
* the algorithm outputs a "***trie***" data-structure (information retrieval tree) $T$ such that:
    + The ***trie*** $T$ accepts any ASCII string as input.
    + An output (leaf node) of the ***trie*** should be set of strings $S$ such that:
        - every string in $S$ is a ***verbose*** string
        - the string fed as input into ***trie*** $T$ is an abbreviation of every verbose string in container $S$

Some examples of input to the ***trie*** and output of the ***trie*** are shown below:

* Example 1

+ Input: "`Ma`"
    + Output: $\\{$"`March`", "`May`"$\\}$
* Example 2

+ Input: "`Mar`"
    + Output: $\\{$"`March`"$\\}$
* Example 3

+ Input: "`Decuary`"
    + Output: $\\{$""$\\}$ ..... the empty-set

The output from the ***trie*** should be one of:

* the empty set
* a set of one item
* a set of two or more items

For months of the year, an application might be a web-page where end-user can type in any half-way reasonable date-format, instead getting an error message.

If you do not like the months of the year application, a different use-case would be to write write your own Linux Shell (similar to ***BASH***). Maybe any half-way reasonable abbreviation of "`make directory`" will map to "`mkdir`" In that case, we could have many-to-one mapping from high-level shell-commands to low-level ***Linux*** commands.

### The question is:

> How can we construct such a ***trie***?
> What algorithm will build the appropriate ***trie*** from the container of ***verbose*** strings.

Also, can we avoid brute-force generating a list of all abbreviations before-hand? The set of all strings form-able by deleting 1 or more characters from the verbose strings is quite large. We would like to avoid combinatorial explosion, if we can.

I am looking for an algorithm, not code written in any specific language.

### Additional Applications (Edit from October 30, 2020)

There are other practical applications than those I originally mentioned.

For example, suppose that you are trying to create a search engine which job applicants use to locate the name of the college they attended.

An example of a verbose string is "`The University of Colorado at Denver`".

In practice, end-users tend to delete letters from the verbose string. For example, and end-user might type in "`UC Denver`" or "`University Colorado Denver`".

---

Another application would be searching for mailing addresses.
An example, a "***verbose***" mailing address is shown below:

```
3751 North. Tower Road.\r\n
Aurora, Colorado\r\n
80011-3522\r\n
United States of America\r\n

```

End-users could write `3751 N Tower Rd.\r\nAurora, Colorado`:

* "`N`" instead of "`North`"
* "`Rd`" instead of "`Road`"
* "`CO`" instead of "`COLORADO`"

Our search engine would still find the correct mailing addres. For this specific example end users could write a dot at the end of the "N" or simply a space character, and it would still work.

> We assume that end-users always type in a valid mailing address, but with zero or more characters deleted.

We simply need to identify the set of verbose mailing address which the abbreviated mailing address maps to. If there is only one verbose mailing address, then we are in good shape. If there are 3 or 4 verbose mailing addresses, we could display them all, and ask the end-user to choose one.

# Answer
> 1 votes
Since the first symbol must match, we can just check it in the beginning, and solve the problem separately for each starting symbol (from here on, we just remove the starting letter from all strings).

**First, let's start with without-trie intuition**. As an example, consider all permutations of string $abbc$. All possible strings are the following:

$$S=\\{\cdot abbc, \cdot abcb, \cdot acbb, \cdot babc, \cdot bacb, \cdot bbac, \cdot bbca, \cdot bcab, \cdot bcba, \cdot cabb, \cdot cbab, \cdot cbba\\},$$

where by $\cdot$ I denote our current position in these strings (initially, we are at the beginning of all strings). Now, assume that the symbol $b$ arrives. For each string, we find the first position of $b$ after $\cdot$, and move there. I.e.

$$S\_b=\\{ab \cdot bc, ab \cdot cb, acb \cdot b, b \cdot abc, b \cdot acb, b \cdot bac, b \cdot bca, b \cdot cab, b \cdot cba, cab \cdot b, cb \cdot ab, cb \cdot ba\\}$$

Assume that the symbol $a$ arrives next. Again, we find the next position of $a$ after $\cdot$ in all strings. Strings that don't have such positions disappear from our set.

$$S\_{ba}=\\{ba \cdot bc, ba \cdot cb, bba \cdot c, bbca \cdot, bca \cdot b, bcba \cdot, cba \cdot b, cbba \cdot \\}$$

If symbol $b$ arrives next, we have

$$S\_{bab}=\\{bab \cdot c, bacb \cdot, bcab \cdot, cbab \cdot\\}$$

**Solution with trie**. Actually, the solution above already works, but it may require $O(\sum\_s len(s))$ time (and it often will). We can do better with tries.

First, we build a trie for our strings.

After we have an input symbol $b$, we want to find nodes corresponding to $S\_b$ (they are circled on the picture). On each branch, we want to find all nodes which go first after some $b$. Therefore, for each node $u$, we have to find all nodes $v$ such that there exists path $u \leadsto \ldots \to^b v$, and there is no another such node on the path. For example, while for node $9$ there is such path from the root, there is another such node ($8$) on its path.

We have to find all such nodes for all nodes and symbols. I.e. $next\[u\]\[c\]$ denotes the set of nodes in a subtree of $u$ which go first after symbol $c$. E.g. \begin{align\*} next\[0\]\[b\] &= \\{2, 8, 10, 28, 30\\} \\ next\[2\]\[c\] &= \\{4, 5\\} \\ next\[26\]\[a\] &= \\{27, 31, 34\\} \end{align\*}

This is a pseudo-code how it can be done ($sym(u)$ denotes a symbol by which precedes the node $u$. E.g. $sym(1)=a$, $sym(2)=b$):

```
for each node u:
    next[u] = {}

def dfs(u, stack):  # stack stores all ancestors of the current node
    c = sym(u)
    for v in stack:
        next[v][c].insert(u)
        if sym(v) == c:
            break  # for all nodes above, v is before u and has the same symbol

    for v in children(u):
        dfs(v, u :: stack)  # add u to stack

dfs(root, [])

```

Now, when we have a string $s$ as an input, finding an answer is as simple as:

```
nodes = [root]
for c in s:
    nodes = Union(next[node][c] for node in nodes)

return nodes

```

, where $next\[node\]\[c\]$ returns an empty set when it doesn't exists.

**Optimization?** (I'll update this section if I prove the statements here) While this code works, we may have large intermediate solutions but result in the empty set. One way to avoid it is to do some preprocessing: namely, build a DFA. Each state corresponds to a set of nodes, and transitions are as described in the second algorithm. I think it can be shown that the number of such states depends linearly on the total length of the strings. You also need to store a mapping from states to sets of nodes, and I think it'll also be linear in the total length of the strings.

# Answer
> -1 votes
This is in the end a programming question, and programming has to be effective - produce the result, minimising the cost, which is mostly the cost of programming.

For 12 items you don’t create any complex data structure. For example, in Swift you would write

```
let months = [“January”, “February”].filter { $0.hasPrefix(“J”) }

```

and you’re done. But what you plan doesn’t work anyway. For example, in German “März” is abbreviated as “Mrz”, not “Mär”. And typically the abbreviations used are fixed, not arbitrary numbers of letters.

---
Tags: strings, search-trees, substrings, information-retrieval, string-matching
---


title: Speedup with multi-head Turing Machine

text:
# Question
Title: Speedup with multi-head Turing Machine
What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits on different parts of the tape)?

ie. what is the overhead, worst-case, for a one-head Turing Machine to simulate a multi-head Turing Machine as the number of heads grow?

https://link.springer.com/content/pdf/10.1007/3-540-08342-1\_35.pdf

^ This paper ^ says linear time. But the multi-head machines have the additional property of a one-move shift operation (shift a given head to the position of some other given head), is this standard?

Thanks!

# Answer
First, the one-move shift is definitely NOT standard, but, as far as I understand, it only *strengthens* the result in that article. If a machine with the special operation can be simulated, then of course a machine without that operation can as well.

Second, here are some papers by Hans-Jörg Stoß dealing with multi-head machines. No one-move shifts here.

1. k-Band-Simulation von k-Kopf-Turing-Maschinen (1970) - establishes that $k$-head and $k$-tape can simulate each other without changing computation time.
2. Zwei-Band Simulation von Turingmaschinen (1971) - simulates a machine with $k$ heads on an $m$-dimensional tape by a machine with 1 normal tape plus 1 stack, establishing a rather precise time bound.
3. Linear-Time Simulation of Multihead Turing Machines (1989) - linearly simulates a machine with $k$-heads on a $d$-dimensional tape by a machine with $k$ separate $d$-dimensional tapes plus 1 normal tape.

Unfortunately, the first two are, as far as I know, only in German. The full text of the third one (translated) is here: doi.org/10.1016/0890-5401(89)90037-0
> 0 votes

---
Tags: complexity-theory, turing-machines
---


title: Terms for different models of sum types

text:
# Question
Title: Terms for different models of sum types
There seem to be at least a couple different possible ways of modeling sum types in a type system, but I haven't been able to find consistent terms for referring to them:

1. A sum type is formed from a set of "data constructors", which are function-like entities that notionally map values of a summand type to values of the sum type. This is the model adopted by e.g. Haskell and the various flavors of ML.
2. A sum type is formed directly from the underlying summand types, with no data constructors, and as a consequence the sum type is a supertype of the summands (or at least behaves very much like one). This model seems to be much less common, but it's the model adopted by Ceylon, and by C++'s `std::variant`.

Note that this is separate from the distinction between discriminated and non-discriminated unions: both models permit the sum type to be discriminated (although only if the summands are disjoint, in the case of #2).

Are there settled terms for distinguishing these two models?

# Answer
> 1 votes
1. The first concept you mention is that of an algebraic data type (or ADT). These are (recursive) sum-of-product types, though in many languages the product types are not first-class in that you may not refer to them directly, but only as part of the sum.
2. The second concept is a true sum type. However, in both the examples mentioned, the sum type has a restriction that the summands must be unique, e.g. you cannot describe the type $A + A$, because summands are referenced nominally, rather than by their index.

Note that ADTs suffice to describe sum types (even with non-unique summands), by wrapping their summands in new constructors. However, they are more general, as they can describe fixed point types, like binary trees.

---
Tags: programming-languages, type-theory
---


# Question
Title: Polynomial time counter of solutions of 2SAT expression with pure literals
As per the title, is there any polynomial time algorithm to count the number of satisfying arguments for a 2SAT expression with pure literals? An even shallower case: Is there any such counter when the literals in the expression are either all positive, or all negative?

# Answer
Counting the number of satisfying assignments in a positive 2SAT formula is the same as counting the number of vertex covers in the corresponding graph (after removing singleton clauses). Counting the number of vertex covers is known to be $\mathsf{\\#P}$-complete. See also this question on cstheory.
> 1 votes

---
Tags: counting, 2-sat
---


title: Minimizing series of XORs

text:
# Question
Title: Minimizing series of XORs
Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form

$$x\_i \leftarrow x\_i \oplus x\_j,$$

(where $\oplus$ is the binary XOR) can we efficiently find a minimal series of instructions (of the same form) that computes the same result, using up to $m$ initially zero extra temporaries?

# Answer
I don't know what sort of efficiency you are looking for, it would be good if you clarified it.

Each instruction can be described as a linear map in $\mathbb{F}\_2$, so the overall series of instructions is one linear map.

As for finding the *minimal* set of instructions, given a limited number of temporary variables, I believe this is analogous to the register allocation problem for compilers, which is NP-COMPLETE.
> 0 votes

---
Tags: program-optimization, xor
---


# Question
Title: Operating Systems - Page Table - Address Translation - Physical Address & Logical Address
Hi,

I am learning about memory management in operating systems. I am confused with Address Translation. In this question (pic attached), can anyone explain, how the answer is obtained for Blank #2? What are the steps? Thanks in advance

# Answer
> 0 votes
1. Since the question asked is to find the *logical* address, it follows that the thing given (0xABCD) is the *physical* address, the one obtained after translation.
2. Let's convert the address given to binary, and then split the address as prescribed in the question: 6 bits for page id, 10 bits for offset.

```
       A    B    C    D
    1010 1011 1100 1101

    101010 1111001101

```
4. Converting the page id `101010` to hex, we get `0x2A`, which is indeed one of the numbers in the page table - specifically, it's the location of the page number 1. Therefore, the 6-bit page id *before* the translation was just the number 1.
5. Just replace the physical page location with the logical page id, and convert back to hexadecimal.

```
    Physical: 101010 1111001101
    Logical:  000001 1111001101

              0000 0111 1100 1101
                 0    7    C    D

```

---
Tags: operating-systems
---


# Question
Title: Distribution of resources from providers to maximum number of receivers
Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what providers are available to him. Formally let resident $i$ has list of providers $a\_i$. Also each provider has a maximum number of connections he can give, that is, provider $i$ can have at max $k\_i$ connections. Find the optimal way of providing internet so that the number of residents having internet is maximum.

My thoughts on the question is that this question looks like a derivative of knack-pack problem with constraints, which suggests dynamic programing but i am unable to find the states. Could anyone help me?

# Answer
This problem is a case of maximum flow problem.

Suppose we are given internet providers $p\_1, p\_2, \cdots, p\_m$ and residents $r\_1, r\_2, \cdots, r\_n$. Consider a flow network specified as the following.

* Nodes are $s,\ p\_1, p\_2, \cdots, p\_m,\ r\_1, r\_2, \cdots, r\_n,\ t$, where $s$ and $t$ are two extra nodes standing for the source and the sink.
* There is an edge between $s$ and each $p\_i$ with capacity $k\_i$.
* There is an edge between $p\_i$ and $r\_j$ with capacity 1 if $p\_i$ can provide internet to $r\_j$.
* There is an edge between each $r\_j$ and $t$ with capacity 1.

What we want is to find the maximum flow from $s$ to $t$.

There are many algorithms to solve a maximum flow problem in polynomial time. For example, Ford–Fulkerson algorithm and Dinic's algorithm are pretty popular. Source code that implement those algorithms in various programming languages can be found easily.

All those algorithm will produce an integral maximal flow, so we will not worry in case the computed maximal flow stipulates that some provider should provide 0.42 or $\frac{\sqrt2}2$ internet to some resident. You can check the integral flow theorem.
> 3 votes

---
Tags: algorithms, graphs, dynamic-programming, knapsack-problems
---


# Question
Title: How to simulate natural number in Pi Calculus
I have some questions about Pi Calculus:

How to simulate the natural numbers only with its primitives?

It's possible simulate the if else clauses without the sum (+)?

A minimal and standart example would be interesting.

# Answer
> 2 votes
You can encode natural numbers in π-calculus in a way that is a variant on encodings of natural numbers in untyped λ-calculus, see (1). Milner, Parrow & Walker explain how to do this in the paper (2) that introduced π-calculus. Note that such encodings are not efficient (they are essentally unary encodings of numbers, so give rise to large terms). You only do such encodings to gauge expressive power of the untyped π-calculus. In any real implementation, you'd add numbers as a basic data-type.

---

1. Wikipedia, Church encoding.
2. R. Milner, J. Parrow, D. Walker, A Calculus of Mobile Processes, Part I.

---
Tags: pi-calculus
---


title: SAT satisfaction with 10 variables

text:
# Question
Title: SAT satisfaction with 10 variables
I am trying to prove that the next problem is NPC:

$$ A = \\{ \langle\phi\rangle \ \big| \ \phi \ \text{is CNF and has sat. assignment where exactly 10 vars are TRUE} \\} $$

I am trying to find polynomial mapping reduction from SAT but I can't find a way to force exactly 10 variables to get TRUE assignment. My idea was to create new formula, with 10 clauses, each clause is the intersection of a new variable $x\_i$ with the old formula, but I don't see how my idea helpful.

I would appreciate help.

# Answer
> 5 votes
The problem you mentioned is in $P$ so it is not NP-complete. We know that $|\phi| = n$ so the number of variables is less than $n$ and we know that members of $A$ exactly have 10 True assignments. So by a brute force algorithm check every possible assignment to variables. Choose 10 variables from n, $(^{n}\_{10})$ and set them to $True$ and set other variables to $False$ and check if this is a satisfying assignment. The run time of this algorithm is $(^{n}\_{10})\*n = O(n^{11})$.

---
Tags: polynomial-time-reductions
---


# Question
Title: Calculating the structural integrity of a pixel grid
## Preface

So this is a question that came from an idea for a game. This game is voxel-based, and I am interested in calculating structural integrity, with some blocks that break after a limit has been reached.

I know Medieval Engineers and 7 Days to Die implemented something along these lines, though I would like to see if I can solve this (with some help) before ripping someone's implementation.

Of course links to more examples are appreciated.

# Problem

In a 2D grid of constant size, there exists an *anchor* which all pixels/nodes must connect to. For example the bottom row will act as the "ground" and anchor all nodes. Finding unanchored nodes is easy, so assume all nodes are anchored.

Each node/pixel will have a mass, for simplification, this will be "1 block" of mass.

From there we need to find how much load each node is under (i.e. the amount of mass the node is supporting), and therefore how much "stress". In this problem load and stress are the same.

# My Implementation

For every node:

1. Split the mass of a block based on its valid connections i.e. paths that are not a dead end.
2. The fraction of mass on the neighbor node represents the fraction of weight of the source node it supports.
3. Repeatedly traverse splitting the mass until you get every path to an anchor node.

You should end up with a total number on each node representing how much "mass" it is supporting.

### Example:

**Mass distribution of one node**

Each color represents the initial path from the source node/pixel for clarity. The source mass is divided into three since the bottom path (in this example one block) cannot reach the anchor without going back on itself.
From this we can see the node with the most stress from the source node is *D2*, with the runner-up being *C2*. *B3* is not affected by the source because it is not supporting it.

Of course there are limitations with this solution:

* Bad time complexity
* Scales poorly with #nodes
* adding or removing one node is expensive

My solution involves finding every path from source to anchor for every block, which is bad.

I made a (very slow) example below, where the bottom of the grid is the anchor.
\[Codepen Example\]

# Question:

How do I improve this algorithm or simplify the model in which stress is calculated so it can perform near real-time?

# Answer
*So I found a solution using maximum flow algorithm with some tradeoffs.*

**The setup involves:**

* Connecting the source node to every node in the grid with an edge capacity equal to the nodes mass.
* Connecting the sink to the bottom layer
* Connecting every node in the grid to each other with some capacity defined by the node (i.e. the maximum stress/load from that direction)

After Dinic Max Flow algorithm runs, I traverse the residual graph starting at nodes which do not get the maximum flow from the source (i.e. nodes that can't apply their full mass) and find all nodes which have an edge with max capacity.

### \[CodePen Example\]

## Example configuration:

So the algorithm works much faster than mine, and that is because it does not spread mass evenly. As shown above the white squares are nodes which have edges with maximum flow. This does not necessarily mean that the node is overloaded, and as you can see there are alternative flows that are not at full capacity.

However since my goal was to simply find the overloaded nodes and destroy them (and floating parts) this does not matter so much.
> 1 votes

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


# Question
Title: Clustering Application with a Huge Number of Clusters
I am wondering if there are any clustering applications in practice where the number of clusters, i.e., the $k$ in the $k$-means problem is very high ($k\>50$, optimally $k\>200$), if possible with a citation.

The clustering can take place in any metric space.

# Answer
> 0 votes
In \`Learning Feature Representations with K-means' \[1\] the authors apply unsupervised learning, i.e., k-means to learn 256 features (centroids, centers). They also claim that the huge number of centers, in this case, k=256 is a limitation to this approach.

p\[11\]: \`\`Indeed, it is frequently best to set k as large as compute resources will allow, considering data requirements. Though performance typically asymptotes as k becomes extremely large, increasing the size of k is a very effective way to squeeze out a bit of extra performance from an already-built system''

\[1\] https://www-cs.stanford.edu/~acoates/papers/coatesng\_nntot2012.pdf

---
Tags: clustering
---


title: aⁿbⁿcⁿdⁿ using 2-stack PDA

text:
# Question
Title: aⁿbⁿcⁿdⁿ using 2-stack PDA
I need to construct a PDA using 2 stacks for accepting the language $L = \\{a^nb^nc^nd^n | $ $n \geq 0\\}$.

Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and $d$'s respectively won't work because that would mean number of $a$'s $= $number of $c$'s and number of $b$'s$ =$ number of $d$'s. I can't come up with an accurate solution.

# Answer
> 1 votes
Check out this link: https://stackoverflow.com/questions/40317006/pushdown-automaton-pda-for-l-anbncnn-1#*=* or check the answer below.

2 stack PDA to recognize the language {an bn cn dn n\>=0} for this we should follow the given steps:

Use the first stack for checking an bn, this can be done by pushing a whenever you see an a and then popping a when you see a b.

Use the second stack for checking bn cn this can be done by pushing b whenever you see a b and then popping b when you see a c.

Use the first stack for checking cn dn this can be done by pushing c whenever you see a c and then popping c when you see a d.

Accept if both stacks are empty at the end of this process, otherwise do not accept it.

Let ^ and z be the stack symbol of stack 1 and 2 respectively, then the transition diagram of the above PDA will be as follows:

# Answer
> 0 votes
A 2-stack nondeterministic PDA is easily shown to be equivalent to a nondeterministic Turing machine—just use the two stacks as the left and right halves of the tape. So you could just write a Turing machine that accepts the language and then convert that to a 2-stack PDA.

Not as elegant as ttnick's/Devharsh Trivedi's solution, perhaps, but it avoids having to be clever with stack management.

---
Tags: context-free, pushdown-automata
---


# Question
Title: Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths
I have a graph like this that starts from one top node and has cycles:

I need to write an algorithm to figure if `node1` depends on `node2`. The most primitive algorithm I've written simply starts with `node1` and recursively follows all available edges looking for `node2` starting from `node1`. It's very inefficient because I traverse the graph over and over again. I'm wondering if there's an algorithm I can look at that caches nodes and dependencies it already walked through so that I don't go through paths I've walked once and can figure if there's a dependency or not from cache?

For example, if I'm given node `D` and the question is whether it depends on node `F`, I'll walk `D->E->F`, and when next time I get the question if node `E` depends on `F`, I'll get that from cache without walking the graph.

Thanks for any ideas and suggestions!

# Answer
> 1 votes
This is a classic problem known as "reachability querying". There are various algorithms possible, with different complexities.

Unless you are working with some huge graphs and can not afford to store the index, the simplest is storing the $O(|V|^2)$ *transitive closure* of your graph. This can be computed quite simply with Floyd-Warshall in $O(|V|^3)$, and with a lot more effort in $O(|V||E|)$ using the methods found in Nuutila's thesis.

Now if your graphs are truly large and you can not afford to spend $O(|V|^2)$ memory you enter an academic world of dozens upon dozens of papers, each with slightly varying performance characteristics (very often incomparable, yet almost always claiming to beat the competition), and varying difficulty of implementation. I guarantee you that almost all of them will be hard to implement however.

Allow me to reproduce Table 1 from *Reachability querying: an independent permutation labeling approach*, a recent paper by Hao Wei et. al. Here we have as main parameters $n = |V|$, $m = |E|$, $k$ is the width of the graph, $t$ is the number of non-tree edges of the graph after a spanning tree is formed.

---
Tags: algorithms, graphs
---


# Question
Title: GATE CSE 2009, Which of the following is FALSE?
This is a question from GATE CSE 2009.

> Which of the following is FALSE?
>
> A\] There is a unique minimal DFA for every regular language.
>
> B\] Every NFA can be converted to an equivalent PDA.
>
> C\] Complement of every context-free language is recursive.
>
> D\] Every non-deterministic PDA can be converted to an equivalent deterministic PDA.

The answer provided to me (without any explanation) is B, which I think is wrong.

Here is my approach.

> A\] Every RL has an equivalent DFA and there is one unique minimal DFA for a given RL. \[so True\]
>
> B\] Since RL are proper sub-set of CFL and every RL has equivalent FA and every CFL has equivalent PDA, every FA can be converted to PDA but not vice versa. \[so True\]
>
> C\] Given a CFL we can create an equivalent Total TM \[RECURSIVE\], RECURSIVE languages are closed under complement. \[so True\]
>
> D\] This is only remaining option and by method of elimination answer.

Is my answer correct?

# Answer
A is true, but I don't find your argument convincing (it simply restates the claim). See this question for example.

B is not the correct answer to this problem, because as you say it's true. Your reasoning isn't very formal though, and swaps some reduction orders. A correct reduction would be NFA → (superset construction)→ DFA → (trivial) → PDA.

C seems fine to me.

D is indeed left over, and is indeed false. Inherently ambiguous context-free languages can be recognized by nondeterministic PDAs, but not by deterministic PDAs.
> 3 votes

---
Tags: formal-languages
---


# Question
Title: Graph search or shortest path algorithm for graph with multiple “goals”?
I did a project in a class using A\* search to solve an 8-puzzle. But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles. I’m not sure whether something like A\* search could still work or not. I have trouble fathoming how a heuristic might be designed. Are their other shortest path algorithms or search algorithms that are better suited for this kind of problem?

# Answer
If you have multiple goal nodes and a consistent (or admissible) heuristic to each of them, taking the minimum of them will be still be a consistent (or admissible) heuristic.

Aside from that, there is nothing in A\* that prevents you from having multiple goal nodes. The algorithm works fine unchanged.

---

\[Edit\] Another heuristic for your problem specifically: for each tile, compute the distance to the nearest valid goal-space, then take the sum over all tiles as the heuristic.

With $n$ spaces, $n-1$ tiles, and $g$ goals, this can be done in $O(n)$ time during the pathfinding by pre-computing the distance to the nearest goal, for each tile, using eg. BFS. This will require $O(n^2)$ space and $O(gn^2)$ time *(by searching backwards from each goal)*.
> 1 votes

# Answer
Yup! You can use A\* in that situation. Possibly the simplest method is to run A\* once per goal node. Another plausible approach is to consider all of the 'solved' states as a single goal node. Then the heuristic function $h(\cdot)$ is an estimate of the distance from the current node to the goal node, i.e., from the current node to any solved state. Thus, modifications to the heuristic function will be required. One way to modify it is to estimate the distance to each of the possible solved states, and take $h(\cdot)$ to be the smallest of those estimates.
> 0 votes

---
Tags: graphs, shortest-path, graph-traversal
---


title: Subset sum problem for permutations

text:
# Question
Title: Subset sum problem for permutations
Given permutations $g\_1,\\,\ldots, g\_m \in S\_n$ of size $n$ and target permutation $g \in S\_n$, decide if there exists a subset of $\\{g\_1,\\, \ldots, g\_m\\}$, which composition in some order (or, alternatively, as a variant of this problem, in the same order) is equal to $g$, i.e. $g\_{i\_1} \circ g\_{i\_2} \circ \cdots \circ g\_{i\_k} = g$.

This is actually a subset sum problem, but for symmetric group $(S\_n, \circ)$ instead of $(\mathbb{Z}, +)$.

The questions are:

1. Is there a known solution in polynomial time?
2. Otherwise, is this problem known as NP-complete?

I've found a paper on knapsack problems in groups, however, these results seems to be not applicable for symmetric group.

# Answer
> 2 votes
This problem, that I will call Subset-Perm-Sum, is NP-complete. Membership is easy: guess the subset non-deterministically and then check.

For hardness one can reduce from 3CNF-SAT in a very similar way to the standard proof of hardness for Subset-Sum.

Let $\varphi$ be an input formula with $v$ variables and $c$ clauses. We will build an instance of Subset-Perm-Sum over $S\_{2v+4c}$. For every variable we build $2$ permutations (one that will represent the variable, and one that will represent its negation), and for every clause we will build $2$ permutations as well.

To each clause $C\_j, 1\leq j \leq c$ we associate $4$ elements: $2v+4j-k$ for $0 \leq k \leq 3$. To build the $2$ permutations associated to a clause we simply do a cycle on its associated elements. That is, $$ p(C\_j) = (2v+4j-3, 2v+4j-2, 2v+4j-1, 2v+4j)$$ (we will add $2$ instance of $p(C\_j)$ to the set we want to find a subset-sum later.)

Consider the $i$-th variable, $x\_i$, and associate with it the elements $2i-1$ and $2i$ of $S\_{2v+4c}$. To build the permutation $p(x\_i)$ of variable $x\_i$ simply swap its associated elements ($2i-1$ and $2i$), and multiply by the permutation of each clause it is contained in. Then, in cycle notation you can write: $$ p(x\_i) = (2i-1, 2i) \prod\_{j | x\_i \in C\_j}p(C\_j) $$

Consider now the multiset $M$ that is the union of the $p(x\_i)$ and $p(\bar{x\_i})$ and two times each $p(C\_j)$.

We define the target permutation $t$ as:

$$ t = \prod\_{i=1}^v (2i-1, 2i) \cdot \prod\_{j=1}^c p(C\_j)^3 $$

**Claim:** There is a subset $X$ of $M$ that composes to the target permutation $t$ (let me write $p(X)=t$) if and only if $\varphi$ is satisfiable.

Assume such an $X$ exists, then we know $X$ contains exactly one out of $p(x\_i)$ and $p(\bar{x}\_i)$, as it is the only way for the composition of $X$ to include the cycle $(2i-1, 2i)$. Furthermore, we can see that for each clause $C\_j \in \varphi$, at least one if variables satisfies it, as to have $p(C\_j)^3$ in $p(X)$ we need to have included a $p(\ell\_i)$ such that literal $\ell\_i$ is in $C\_j$. Note that taking the two instances of $p(C\_j)$ in $X$ is not enough. Therefore, there is an assignment of variables that satisfies every clause. For the backward direction, let $\sigma$ be a satisfying assignment of $\varphi$. If $\sigma(x\_i) = 1$ then we let $X$ contain $p(x\_i)$ and otherwise we let it contain $p(\bar{x}\_i)$. For each clause $C\_j$, we know there are between $0 \leq r\_j \leq 2$ variables on it that are not satisfied by $\sigma$, and we add $r\_j$ occurrences of $p(C\_j)$ to $X$, so this way $p(X)$ includes $p(C\_j)^3$. It is clear that the composition of $X$ equals $t$.

# Answer
> 1 votes
The subset sum problem is even harder(NP-hard) for special groups which you can embed into $S\_n$. See the paper you have linked in the problem description.

$\textbf{Observation:}$ $g$ can be writtens as combination of elements $\\{g\_1,\ldots,g\_k\\}$ if and only if $g \in \langle g\_1,\ldots,g\_k\rangle$. Under the assumption that each of $g\_i$ can appears any number of times.

The complexity of the problem depends upon the input representation. There are two two most commonly used ways, Cayley table and generating set. For Cayley table see this paper for results. Read the CGM(Cayley membership problem) Link

$\textbf{CGM} $

$\textbf{Input :}$ A group $G$ by its Cayley table, $X \subseteq G$ and $t \in G$.

$\textbf{Output :}$ Does $t$ belong to the subgroup $\langle X \rangle$ generated by $X$?

In general problem is in Symmetric log space.

---

$\langle A \rangle$ means subgroup generated by $A$

---
Tags: algorithms, complexity-theory, permutations, subset-sum, group-theory
---


# Question
Title: shortest paths algorithm - why backtrack from the end node instead of starting from the starting node?
I was watching a dynamic programming video by Erik Demaine . He says here https://youtu.be/OQ5jsbhAv\_M?t=2133 , finding the shortest paths from S to V for all V, by guessing the node after the starting node is not the right approach, and instead should guess the node before the last node. I didn't understand his explanation. Can someone explain better why find the path backwards? It seems to me that you should get the same answer either way and both approaches are equally good.

# Answer
You want to find the shortest paths $S(s,v)$ to **all** nodes $v$ (31:30 in the video). In other words, we are interested in computing a function $f(v) = S(s,v)$, and, as explained in lecture, you can write it as $f(v) = \min\_{(u,v) \in E} f(u) + w(u,v)$. In the end, it allows you to compute all such values in one go.

If you instead consider an equation $S(s,v) = \min\_{(s,u) \in E} w(s,u) + S(u,v)$, you do can find $S(s,v)$ this way. However, you won't be able to find $S(s,u)$ for all other $u$ in the process, and you'll have to run the same algorithm again for other end vertices.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Clustering data for compression with PCA
If I have datapoints in a high dimensional space and want to find a (linear) subspace onto which a data-set projects well, I can use PCA and then discard less important dimensions of the new basis to get compressed datapoints. However, often the data can be projected onto lower dimensional spaces with much smaller error if one first separates them into a couple of classes and then performs PCA for each class individually. What kind of algorithm can find such clusters? Just clustering based on distance in the high dimensional space won't be very useful:

Example:

If I'd just cluster first based on distance in the high-dimensional space, I would arrive at the bad clustering. There are 5 clusters and the green and red clusters don't project very well onto a 2D subspace.

As a human looking at the data, I see however that if I separate the data as indicated, red and blue will project very well onto a plane each and green will project very well onto a line, so I can run PCA for each group individually and store the red data points with 2 values each and the gree ones with 1 value each (plus a 2bit index on each datapoint to label which group it belongs to) and get a very low error upon uncompressing.

How can I automate this clustering based on how well it will project onto as low-imensional subspaces as possible?

Something like minimize E = SumOverClusters(SumOverPoints(SquaredDist(projected\_point, original\_point)) * (number\_dims\_projected / number\_dims\_original)) + C * number\_of\_clusters

What technique is well suited to do that?

(edit: while the example shows a 3d space, I'm more interested in doing that in about 64dimensional spaces)

# Answer
> 0 votes
(Not really an answer, more like a suggestion)

Since it's almost surely NP-hard, we need some heuristics. The idea is, for each point, to build the cluster it's contained in:

```
def clustering(P):  # P is the set of points
    for each p in P:
        build a somewhat-optimal cluster C containing p
        remove C from P

```

Now, for each point we will build a cluster, one dimension at a time. We will build vectors $(v\_1, \ldots, v\_k)$, until the objective doesn't improve:

```
def build_cluster(p, P, t):  # t is a projection distance threshold
    S = ()  # current span
    for k = 1, 2, ...:  # cluster dimension
        sample m vectors v_1, ..., v_m
        for each v_i:
            compute the number of points in P within a distance t to p + span(S, v_i)
        select the best such v_i
        if adding v_i to S is not beneficial:
            break
        S = union(S, v_i)

```

Now, there is a lot of engineering which can be done, except for defining stop conditions. E.g. we can sample vectors, and then iteratively improve them (minimizing the loss, I.e. the distance to the span from vertices within distance t) (and we can also decrease t in the process of improvement). Also, maybe we should do something better than sampling random vectors since we are unlikely to hit the right one. We may try to compute some candidates based on our data.

Hope it helps.

---
Tags: data-compression
---


# Question
Title: Complexity of Subset Sum where the size of the subset is specified
I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum.

> Given a subset $S$ of positive integers and integers $k\>0$ and $N\>0$, is there a subset $T\subset S$ such that $|T|=k$ and the members of $T$ sum to $N$ ?

All of the formulations of subset sum that I've seen don't specify $k$ so I'm wondering if this problem can be solved in polynomial time. If $k$ is fixed for all instances, then I know that the problem is in P and solvable by brute force in $O(n^k)$ time. However, I'm allowing $k$ to vary from instance to instance.

# Answer
There are $\binom{n}{k}$ $k$-subsets of an $n$ set, and $\binom{n}{k} = n (n - 1) \dotsm (n - k + 1) / k!$, which is $O(n^k)$, as you observe. The brute force complexity is a bit more (need to add up the numbers too and check), but that is ballpark.

This is polynomial for any *fixed* $k$, but not polynomial in $n$ if e.g. $k = n / 2$ (that is the Partition problem, known NP-complete).
> 1 votes

# Answer
As vonbrand said, if $k$ is a number other than $\frac{n}{2}$ it doesn't change much. Your problem is in ${\sf{P}}$ as long as $k$ is a fixed number which does not depend on $n$.

You can try and show it is $\sf{NPC}$ by polynomial reduction from Partition (which is known to be NP complete).
> 0 votes

---
Tags: complexity-theory, np-complete, subset-sum
---


# Question
Title: Guided Backpropagation in Deep Neural Networks
I am reading about a method called guided backpropagation. https://ramprs.github.io/2017/01/21/Grad-CAM-Making-Off-the-Shelf-Deep-Models-Transparent-through-Visual-Explanations.html#deconv-and-guided-backprop.

As shown in the figure below, you essentially compute the derivates of the output with respect to the input image while zero-ing out negative gradients along the way. The website mentions

> Negative gradients at a particular ReLU neuron, state that this neuron has a negative influence on the class that we are trying to visualize.
>
> During backpropagation there are paths that have positive influence and some that have negative influence, and these end up cancelling out in a weird interference pattern, causing gradients to seem noisy. Whereas in Guided Backpropagation, **we only keep paths that lead to positive influence on the class score**, and supress the ones that have negative influence, leading to much cleaner looking images.

My question is why does the resulting image have pixels which are negative? Don't negative pixels indicate that the gradient of the output with respect to the pixel is negative? I.e. that pixel has a negative influence on the class score?

# Answer
> 5 votes
Guided backpropagation from the model output to the input of the first ReLU indeed results in non-negative values (as the gradient from ReLU output wrt. ReLU input is set to zero if it is negative). From the input of the first ReLU the gradient wrt. the input pixels can however become negative. Input images are mostly scaled to the range \[-1,1\] (e.g. by division by 127.5 and subtraction of 1 for Keras' pretrained models - that means roughly achieving zero mean and unit variance). If a negative input (pixel that is darker than the mean) contributes positively - via negative weights - to the output of the first convolutional layer the gradient for that pixel is negative. As negative gradients are only set to zero in guided backprop when passing through a ReLU and there is no ReLU between the input of the first ReLU and the overall input, guided backprop can result in negative values.

# Answer
> 4 votes
Kinda late but According to the gradcam paper (https://arxiv.org/abs/1610.02391), it says that negative gradient of the image will most likely contribute to other class.

> We apply a ReLU to the linear combination of maps because we are only interested in the features that have a positive influence on the class of interest, i.e. pixels c whose intensity should be increased in order to increase y. Negative pixels are likely to belong to other categories in the image. As expected, without this ReLU, localization maps sometimes highlight more than just the desired class and achieve lower localization performance

# Answer
> 1 votes
The focus is not on negative pixels but on negative gradients. Negative gradients indicate that the direction of change in the input space decreases the probability of predicted as a certain class. Intuitively, it tells what this class is NOT about. For example, if you are looking for a cat in an image, there are plenty of ways to make the image NOT look like a cat. But that information is NOT useful and contributes to noises in the visualizations. Put another way, we are only interested in what makes the image look like the class of interest.

---
Tags: neural-networks
---


# Question
Title: Converting a Mixed SUBSET-SUM Problem To All-Positive Case
Let's say we have a SUBSET-SUM problem with list {$x\_1,x\_2,x\_3,...x\_N$} and weight $W$, with some of $x\_i\<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent problem, but with all $x\_i \geq 0$? And if there aren't any, is it possible for there to be such an algorithm?

# Answer
> 2 votes
Both variants are NP-complete, so such a reduction surely exists: the definition of NP-completeness guarantees it.

If you want an explicit reduction, you can reduce one to the other (reduce to 3SAT using Cook's theorem, then reduce 3SAT to the other using its NP-completeness). The resulting reduction will be ugly, though, so I suspect this might not be what you're looking for.

If you want a simple and natural reduction, I'm not sure how to achieve it.

---
Tags: subset-sum, polynomial-time-reductions
---


# Question
Title: Is there a query language variant of Turing Completeness?
By this I mean a theory where you can say Language X is Query Complete so that you know that language is able to do any sort of query? I'm guessing not because some queries would run into things that a language would have to be Turing complete to work?

Why do I wonder - well you might have a relational database and a graph database and someone might say anything that can be done in the relational database can be done in the graph database (albeit at different speeds) so I would like if there were some terms DB A and DB B are both Query Complete - or if not that if there was a way to categorize levels of "query completeness" (I'm just going to assume my ill defined concept is totally understandable to everyone) so one can say stuff like "DB A is query level 4 but DB B is at query level 3, but of course much faster because of those limitations."

I sure hope (so as to not feel like a bigger idiot than normal) that the answer to this question isn't just a flat No.

# Answer
The most you could expect out of a query language would be Turing completeness. In other words, the most powerful you could make a (physically realizable) query language would be to allow operations equivalent to treating the entire database as a single string and running an arbitrary program with that string as input.

Any real-world database query language that includes WHILE loops in the query language (e.g. PL/SQL) is probably Turing-complete in this sense. With such a language, you can go all the way down to reading and writing single rows at a time as necessary to read arbitrary data out of the database and interpret a Turing machine with the data as input. Of course, this is horrifically inefficient, but that's beside the point!
> 4 votes

# Answer
For a query language to be "complete", in this sense of "being able to express all queries", it would have to be evaluated in its capacity to give a well-formed version of every question that can be posed, *whose answer can be given as an instance of the data model that is being used to parameterize said language*.

(I'm assuming your question is about what is *definable*, not computable, so to speak. The answer is trivial, otherwise.)

This is a heavy constraint on the kinds of questions that are considered legitimate. One would hope that a query language based on a powerful construct such as the logic/algebra of relations is good enough, at least for all practical purposes, especially because the data models that we use are always finitary. If that wasn't the case, all sorts of problems could emerge.

That said, being able to actually give a formal version to every possible (plausible) question is certainly an extremely tall order, technically speaking.
> 1 votes

---
Tags: turing-completeness
---