# Question
Title: Functor laws and natural transformations in Haskell
As I've been struggling to get a deeper understanding of monads in Haskell, I started reading about functors and their counterparts in category theory. Keep in mind that I have no background in the latter.

According to Milewski(1), *any polymorphic function of the type* `F a -> G a`*, where* `F` *and* `G` *are functors, automatically satisfies the naturality condition*, although I have yet to figure out why. Anyways, this should hold in particular when `F` is the identity functor, which if understand correctly would correspond to the aforesaid function having the type `a -> G a`. Now, for simplicity let:

```
data G a = C a

```

If `G` is a functor, then since `C :: a -> G a`, `C` is a natural transformation. Viceversa, suppose `C` is a natural transformation. Thus, for all functions `f`:

```
(fmap f) . C == C . f

```

which I imagine is what leads to the wrapping-unwrapping analogy. In fact, if we render `C x` as `{x}` as in "wrapped `x`", then the previous can be re-written as:

```
(fmap f) {x} == {f x}

```

which quite literally means that applying the transformed `f` to the wrapped value is the same as unwrapping, applying `f` to the unwrapped value and re-wrap it. By the previous equality:

```
law 1) (fmap id) {x}      == {id x}
                          == {x}

law 2) (fmap (f . g)) {x} == {(f . g) x}
                          == {f (g x)}
                          == (fmap f) {g x}
                          == (fmap f) ((fmap g) {x})
                          == ((fmap f) . (fmap g)) {x}

```

It follows that `G` is a functor.

So is it correct to say that requiring the functor laws on a type constructor is equivalent to requiring that its data constructors satisfy the naturality conditions or something along these lines? And if not, then what is the purpose of the functor laws from a "practical" point of view?

**Edit**: I just wanted to clarify that I don't really need an answer to the previous question. What really troubles me is that most tutorials on Haskell's functors make it seem like their wrapper-like nature (on which the intuition behind applicatives and monads is often based) stems from their laws when in reality it seems to be a consequence of the naturality conditions due to Wadler's free theorems(2), unless I'm completely mistaken. What role do the functor laws play in their interpretation as abstractions of some functional programming pattern?

(1) Milewski, B.; *Category Theory for Programmers*; 164
(2) Maguire, S.; *Review: Theorems for Free*

# Answer
> 2 votes
I'm having a little trouble exactly what question you're asking, but I think it might help if we went through the connection between homomorphisms and free theorems.

But here's the executive summary of what I think you want to know:

* The fmap laws are not redundant when you have free theorems. On the contrary, you need fmap to state the free theorem for any function that involves a Haskell `Functor`.
* Specifically, if a function has the type of a natural transformation, its free theorem is the naturality condition expressed in terms of fmap.

First off, let's get a bit of intuition about what the parametricity theorem states. An informal way of stating it is this: For any function which has a "forall" in its type, that "forall" really does mean "for all types". The function cannot make any assumptions whatsoever about the type.

To explain what this means when we involve types with an algebra, we need the language of homomorphisms. So let's review what a homomorphism is. (Sorry if this is revision for you, but I think it's worth going through this.)

Let's consider monoids. A monoid is a set $M$ along with two operations $0\_M$ and $+\_M$ which obeys the laws:

$$\forall x \in M, x +\_M 0\_M = 0\_M +\_M x = x$$ $$\forall x,y,z \in M, x +\_M (y +\_M z) = (x +\_M y) +\_M z$$

A monoid homomorphism is a function between two monoids $f : M \rightarrow N$ which "respects" the two operations:

$$f(0\_M) = 0\_M$$ $$f(x +\_M y) = f(x) +\_N f(y)$$

In Haskell, we might represent monoids as a type class:

```
class Monoid m where
    mzero :: m
    mplus :: m -> m -> m

```

If `M1` and `M2` are instances of `Monoid`, a `Monoid` homomorphism `f :: M1 -> M2` must obey the laws:

```
f mzero = mzero
f (mplus x y) = mplus (f x) (f y)

```

Remember that the monoid operations on the left-hand side of these "laws" are different from the monoid operations on the right-hand side. The left-hand side are the operations for `M1` and the right-hand side are the operations for `M2`.

Now consider the following typeclass (which isn't the same as Haskell's `Ord` typeclass, but is close enough):

```
class Ordered a where
    lessThan :: a -> a -> Bool

```

Again, there are laws that any reasonable "less than" operator must obey. But what I want to concentrate on here is the `Bool` part.

What does it mean for a function to "respect" this algebra? It essentially means that the `Bool` has to be the same. That is, if `A` and `B` are both instances of `Ordered`, an `Ordered` homomorphism `f :: A -> B` must obey the law:

```
lessThan (f x) (f y) = lessThan x y

```

Think about what this means semantically: this law is stating that for any two elements, `f` doesn't change their relative ordering. That is what it means for `f` to "respect" the ordering algebra.

OK, now back to the parametricity theorem. The free theorem for the function:

```
sortBy :: forall a. (a -> a -> Bool) -> [a] -> [a]

```

is this, written out in a slightly fuller form:

```
for all f :: A -> B,
If lt :: A -> A -> Bool is a function such that
    for all x, y :: A, lt x y = lt (f x) (f y)
Then
    for all xs :: [A], sortBy lt . map f = map f . sortBy lt

```

We can say the same thing with type classes:

```
sort :: forall a. Ordered a => [a] -> [a]

```

The free theorem here is, essentially:

```
for all f :: A -> B,
if f is an Ordered homomorphism
then sort . map f = map f . sort

```

Which is, of course, just that `f` doesn't change the ordering of elements, then performing the substitution `map f` and then sorting is the same thing as sorting them performing the substitution.

The complication with `Functor` is that it's a constructor class, so the intuition about what a `Functor` homomorphism should be is a little less clear. But let's step back a moment and talk about category homomorphisms.

Categories are algebras just like any other. A category has two operations, $1$ and $\circ$, which satisfies the laws that you know and love. So a category homomorphism $F$ is a function which satisfies:

$$F(\hbox{id}) = \hbox{id}$$ $$F(g \circ f) = F(g) \circ F(f)$$

If you think of a functor between the "Haskell category" (objects are Haskell types, morphisms are Haskell functions) and a Haskell `Functor` category (objects are Haskell functors and morphisms are Haskell functions between these objects), then this is exactly the `Functor` laws.

```
fmap id = id
fmap (g . f) = fmap g . fmap f

```

Now here's the important part: The fmap operation *is* the homomorphism precondition that you need for free theorems involving `Functor`.

Consider, for example, something with the same type as `fmap` but isn't necessarily `fmap`:

```
instance Functor F where ...

somethingLikeFmap :: forall a b. (a -> b) -> (F a -> F b)

```

The free theorem for this function is:

```
if q . f = g . p,
then somethingLikeFmap q . fmap f = fmap g . somethingLikeFmap p

```

From this you can conclude a bunch of interesting things, such as that if `somethingLikeFmap id = id` then `fmap = somethingLikeFmap`. In particular, `somethingLikeFmap` can be characterised entirely by what it does with `id`.

This has to be the case. The parametricity theorem, which generates these free theorems, states the "forall" in a parametric type really does mean "for *all* types".

If the functor is a container-like type, for example, the function cannot make any decision about what to do based on the *value* of an element in the container. But it could do anything with the *structure* of the container which doesn't depend on the *values* in it.

```
somethingLikeMap1 f = reverse . map f
somethingLikeMap2 f = map f . tail
somethingLikeMap3 f = []

```

If a polymorphic function does has a way to make decisions based on the values (e.g. `lessThan` in the case of `sort`), then the free theorem states that this is the *only* way that it can make a decision about what to do, so if the mapping doesn't affect the decisions (e.g. the values returned by `lessThan`), then it doesn't affect the operation of the polymorphic function (e.g what `sort` does).

So this is why the fmap laws are not redundant with respect to free theorems: they define the homomorphism between the Haskell category and the (endo-) functor category that you need to state the free theorems.

Finally, what is the free theorem of a function which has the type of a natural transformation?

```
instance Functor F where ...
instance Functor G where ...

eta :: forall a. F a -> G a

```

It is:

```
fmap_G f . eta = eta . fmap_F f

```

This is exactly the naturality condition. This a good way to think about what's so "natural" about a natural transformation.

# Answer
> 0 votes
Let me answer all your questions as stated, keeping to the practical programmer's point of view.

*Is it correct to say that requiring the functor laws on a type constructor is equivalent to requiring that its data constructors satisfy the naturality conditions or something along these lines?*

No, this is not quite correct. One of the functor laws can be derived from naturality but not the other. Also, note that not all functors have simple data constructors like in your example. Your example is too simple; it's the identity functor whose `fmap` is an identity function. Any law will always hold for an identity function. An identity functor is at the same time a monad, an applicative, and a traversable. You need a more complicated example (such as `Either a (r -> a)`) to see what laws follow from naturality.

*And if not, then what is the purpose of the functor laws from a "practical" point of view?*

The purpose of functor laws is to express the programmer's expectation about what `fmap` should be doing to a data structure. The programmer's expectation is that `fmap` should transform all the data stored within the data structure but should not modify the shape of the data structure. For example, `List`'s `fmap` should apply a given transformation to each value separately but should not change the length of the list. Since the shape of the data structure does not change, composing two `fmap`s should give the same result as a single `fmap` with a composed function. This is the functor's composition law.

Programmers also expect that `fmap` should work in the same way for all choices of type parameters. So, `fmap` should not try to make decisions based on inspecting the types of values stored in the data structure, `fmap` should always work in the same way for all types. This gives rise to the naturality law.

Another expectation is that `fmap id` should leave the data structure entirely unchanged. This is the functor's identity law.

In this way, you can explain all the laws of `fmap` (naturality, composition, identity) as equations that formalize a programmer's reasonable expectations about what `fmap` should do.

*Tutorials on Haskell's functors make it seem like their wrapper-like nature (on which the intuition behind applicatives and monads is often based) stems from their laws when in reality it seems to be a consequence of the naturality conditions due to Wadler's free theorems(2), unless I'm completely mistaken. What role do the functor laws play in their interpretation as abstractions of some functional programming pattern?*

The special property of functors is that, for a given covariant type constructor, there is only one way of implementing `fmap` that satisfies the laws. So, in some sense, the functor's `fmap` is a direct consequence of a functor's type expression.

One proof of that goes by structural analysis of a given type constructor. A covariant type constructor `F a` must be one of the following: a constant type `F a = Int` (independent of `a`), or `F a = a`, or `F a = (G a, H a)`, or `F a = Either (G a) (H a)` where G and H are also covariant, or `F a = G a -> H a` where G is cotravariant and H is covariant. In each case you can show that there is only one way of implementing `fmap` that satisfies the laws. (The inductive assumption that `G` and `H` already have their own unique `fmap`s that satisfy the laws.) A similar procedure for contravariant functors.

Once you go through these proofs, you will be able to write `fmap` for any type constructor, such as:

```
  type F a = Either ((a -> Int) -> a) (a, a, Int, Either (Int -> a) (List a))

```

You will be able to quickly recognize whether any given type constructor is covariant, contravariant, or neither, and implement their methods accordingly.

---
Tags: category-theory, haskell
---


# Question
Title: Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete
How to show that the shortest simple path problem between two vertices $s$ and $t$ (finding a minimum weight path between $s$ and $t$) in a graph is NP-complete? I saw the following proof in a combinatorial optimization lecture, which I didn't understood (I stressed the moment that I didn't understand).

Let $P\_1$ be the Hamiltonian path problem:

> The Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. From Wikipedia.

Does it exists an Hamiltonian path in $G$?

Let $P\_2$ be the shortest path problem in a directed graph.

If $G$ is the graph within which we search such a Hamiltonian path, we transform $G$ into $\hat G$, replacing each edge $(i,j)$ with two edges $(i,j)$ and $(j,i)$.

For each edge $\\{i,j\\}$ in $G$, we erase $(i,j)$ and $(j,i)$ from $\hat{G}$, give a weight of $-1$ to all remaining edges, and calculate the shortest (simple) path from $i$ to $j$. If the path length is $-(n-1)$, then this is a Hamiltonian path in $G$. If we found no such path going over all edges, then $G$ has no Hamiltonian path.

* Why is is the case that if the path has length $-(n-1)$ then it constitutes a Hamiltonian path in $G$?
* Why if not such path has length $-(n-1)$ then $G$ has no Hamiltonian path?

Maybe if you were kind to help me understand with a visual example I would better understand?

Last but not least, how did we proves that Hamiltonian path is NP-complete?

# Answer
> 2 votes
In fact, it does not prove NP-completeness (see a list of our related reference questions).

For the shortest path problem (SPP) to be NP-complete, it is crucial you allow negative edge weights. Then, there is a simple polynomial-time reduction from the Hamiltonian path problem to SPP. In other words, you take an arbitrary instance $I$ of the Hamiltonian path problem, and construct an instance $I'$ of SPP such that $I$ has a solution if and only if $I'$ has a solution. To make the reduction work, you only need to set up the edge weights in $I'$ suitably.

# Answer
> 1 votes
Suppose there is a simple path of weight $-(n-1)$ from $i$ to $j$. Since each edge has weight $-1$, this path must contain $n-1$ edges, and so it corresponds to a Hamiltonian path in the original graph.

Conversely, suppose that the original graph has a Hamiltonian path, say starting at $i$ and ending at $j$. This path leads to a directed path of weight $-(n-1)$ in $\hat{G}$ which doesn't use the edges $(i,j),(j,i)$, and so it will be found when considering the edge $\\{i,j\\}$.

# Answer
> 0 votes
Given an HP (Hamiltonian path) instance ($G=(V,E),s,t$), we define a Shortest-Simple-Path instance ($G,s,t,w,L$) as follows.

We simply let the weight $w(e)$ of every edge $e∈E$ be $−1$ and let $L=−(n−1)$. ($n=|V|$ is the number of vertices in $G$.) So, in this instance, we need to know whether there is a simple path in $G$ from $s$ to $t$ of weight at most $−(n−1)$ or not.

As all weights are $−1$, this is the same as whether there is a simple path in $G$ from $s$ to $t$ with at least $n−1$ edges or not. Such a path must be a Hamiltonian path in $G$ from $s$ to $t$ as $G$ contains only $n$ vertices. Thus, $G$ contains a Hamiltonian path from $s$ to $t$ if and only if the shortest simple path from $s$ to $t$ in $G$ has cost at most $−(n−1)$. This proves HP $≤\_P$ Shortest-Simple-Path.

---
Tags: complexity-theory, graphs, np-complete, reductions, shortest-path
---


title: FFT of logarithmic input data

text:
# Question
Title: FFT of logarithmic input data
Is there a reasonably accurate method of computing an FFT of logarithmically-represented input data (with a sign bit, that is $±2^{\text{double-precision value}}$)?

The naive method (convert to linear representation, do an ordinary FFT, and convert back to logarithmic representation) very quickly runs into overflow/underflow issues.

Normalizing, by 'dividing' (subtraction in log-representation) the input by the largest absolute value beforehand1 and restoring at the end helps somewhat, but still suffers from accuracy issues in some cases. Consider e.g. $\[C, -C, 1, 0\]$ where $C$ is, say, $2^{2^{100}}$. Your constant output term 'should' be $1$, but ends up as $0$, because when normalized the third input term is $\frac{1}{C}=\frac{1}{2^{2^{100}}}=2^{-2^{100}}$, which underflows double precision and is rounded to $0$.

1: Or, more likely, normalizing such that the largest input's absolute value is `double.MAX_VAL` instead of `1`.

# Answer
Unfortunately, I've found out that this scheme is untenable *regardless*. The point of a log-represented input is to handle high dynamic range - but consider the following input:

$$ \[2^{-(2^{1000})}, 0, 2^{(2^{1000})}, 0\] $$

An exact DFT would produce the following output:

$$ \[2^{-(2^{1000})} + 2^{(2^{1000})}, 2^{-(2^{1000})} - 2^{(2^{1000})}, 2^{-(2^{1000})} + 2^{(2^{1000})}, 2^{-(2^{1000})} - 2^{(2^{1000})}\] $$

Unfortunately, in log-rep none of these are distinguishable from $\pm 2^{(2^{1000})}$. So you end up - even if correctly rounded - with an fft output of

$$ \[2^{(2^{1000})}, -(2^{(2^{1000})}), 2^{(2^{1000})}, -(2^{(2^{1000})})\] $$

...which when inverted becomes

$$ \[0, 0, 2^{(2^{1000})}, 0\] $$

...rather defeating the point of the extended dynamic range.
> 2 votes

---
Tags: floating-point, numerical-algorithms, fast-fourier-transform
---


# Question
Title: How to understand CSMA/CD algorithm from this graph?
I am currently studying Computer Network, and I have some problems when encountered CSMA/CD, I can understand how it works, but I am struggling in understanding this graph, anyone can give me some help?

# Answer
> 1 votes
This is a space-time diagram so, going from top to bottom, the time elapsed is increasing.
Here, A and B are two nodes that are broadcasting messages to the other nodes present with it on the same channel.
At tA, A senses that the channel is idle and then starts transmitting its message as shown in the diagram below. As A's message travels away from it, the time increases which is why the message section in the channel space is shown slanting downwards on both sides of A. At tB, B senses that the channel is still empty as A's message hasn't reached it yet and so, assuming the channel is idle, it also starts transmitting. At time tC, First bit of A's message and B's message reach the same point and this is where "collision" happens.

---
Tags: computer-networks
---


# Question
Title: What is an algorithm to do this binary image segmantation task?
What I need to do is go from a binary image like this:

to a segmented structure like this:

because I have a program that operates on those separated line contours after. As you see, those contours are not perfect, they might be slightly bent but where they meet it's always pretty much orthogonal, there are no 45 degree lines. The lines are between 3 and 20 pixels wide. The whole image is sometimes slightly rotated (less that 10 degrees) but if you find a solution that only works without rotation I could look into de-rotating stuff before. The inserted gap may be of any width (preferably 1px or 2px) as long as it entirely separates one line from another.

I thought one could do something like on page 15 of this paper (the description of what they do is on page 13). Essentially this would come down to finding one marker per line segment and then watershed, but I have no idea how to find that marker.

Just to be clear:

On any point of line intersection, this

is good, as well as this:

If easier to achieve,

this:

is acceptable too, although not preferred.

What's not ok is this:

This is not only true for three-line t-sections but also two-line corner connections (= it doesn't matter which of the two lines meeting gets shortened).

Sorry for the huge pictures, didn't know how to prevent them from turning out this big.

I am working with python and cv2 so it would be a plus if you use that. On the other hand, even a link to a re-implementable algorithm or an idea how to find markers would be fine. Also, I'm looking for a fast and easy algorithm that works on binary (0 or 255) images, not any crazy machine-learning stuff (if avoidable). I have really time but lack the right idea. Thanks in advance.

# Answer
A morphological closing with an horizontal structuring element of sufficient width will erase the vertical segments.

The you can erode them to make them thicker and erase them in white to obtain non-touching vertical segments.
> 1 votes

# Answer
Well, you could use convolutions to filter the crossings, the horizontal and the vertical lines separately. With these, you could choose the connectivity of which ones to preserve (without jumps).

Let's say you want to preserve the vertical lines. What you would need to do then is just erase the expanded crossings from the horizonal lines and finally add the vertical lines.

Don't got any code of this, but maybe this video will help you a bit: https://campus.datacamp.com/courses/biomedical-image-analysis-in-python/masks-and-filters?ex=8
> -1 votes

---
Tags: algorithms, image-processing, python, digital-image-processing
---


# Question
Title: Example of an algorithm that's in O(f(n)), but not in Θ(f(n))
What would be an example of an algorithm that's in O(f(n)), but not in Θ(f(n))?

The only thing I could think of, is an algorithm that behaves differently for different problem sizes, such as an algorithm that performs n operations for even problem sizes and n^2 operations for odd problem sizes. Such algorithms are rare in practice though. Is there a more commonly occurring example (preferably a textbook algorithm) that is in O(f(n)), but not in Θ(f(n))?

**EDIT.** I know that an algorithm belongs to an infinite number of O-classes. We are always interested in the lowest O-class in practice. So, the question is, what is the example of an algorithm whose lowest O-class is not the same as its highest Ω-class?

# Answer
First, there is a problem with the formulation of your question, which needs to be corrected before it can be answered. Algorithms are not in $O(f(n))$ or $\Theta(f(n))$. Functions can be.

So, now we need to ask what function you are associating with an algorithm. Normally, when we use big-O notation in algorithm analysis, we are typically looking at the worst-case running time of an algorithm. (Perhaps you have heard someone say "QuickSort is $O(n^2)$." If so, that was sloppy wording. The precise, accurate wording is "the worst-case running time of QuickSort is $O(n^2)$".)

So, I am going to interpret your question as asking for an algorithm whose worst-case running time is in $O(f(n))$ and not in $\Theta(f(n))$. Such an algorithm is easy to come up with. For instance, consider MergeSort. It is in $O(n^3)$ but not $\Theta(n^3)$.

Your edit suggests you are looking for an algorithm whose worst-case running time is in $O(f(n))$, but not $O(g(n))$ for any smaller $g(n)$, and is not in $\Omega(f(n))$. No such algorithm exists. Let $T(n)$ denote the worst-case running time of the algorithm. Then this algorithm's worst-case running time is in $O(T(n))$, but not $O(g(n))$ for any smaller $g(n)$. It is also in $\Omega(T(n))$ (but not $\Omega(h(n))$ for any bigger $h(n)$).

So the "smallest big-O class" and the "largest big-Omega class" always coincide -- they are exactly equal to the worst-case running time of the algorithm.

Lastly, you might be wondering about algorithms that, on some inputs, run much faster than the worst-case. There are many examples of that. For instance, insertion sort runs in $O(n)$ time if its input is already sorted, but in $O(n^2)$ time in the worst case. QuickSort runs in $O(n \log n)$ time on many inputs, but its worst-case running time is $O(n^2)$.
> 2 votes

# Answer
Finding the maximum value in an array of length $n$ is in $\mathcal{O}(n^2)$, but not in $\Theta(n^2)$. It is however in $\Theta(n)$.

The reason is that $\mathcal{O}$ only gives an upper bound. Since finding the maximum value can be done in linear time, the complexity is in $\mathcal{O}(f(n))$ for any $f$ that grows more quickly than $n\mapsto n$.
> 1 votes

# Answer
Take any textbook algorithm, and let $g(n)$ be its worst case running time on inputs of size $n$. Define $f(n) = n \cdot g(n)$.

Since $g(n) \le f(n)$ the algorithm runs in time $g(n) = O(f(n))$. Moreover, the algorithm does not run in time $\Theta(f(n))$ because it is false that $g(n)= \Omega(f(n))$, as it can be seen by considering $$\lim\_{n \to \infty} \frac{g(n)}{f(n)} = \lim\_{n \to \infty} \frac{g(n)}{n \cdot g(n)} = \lim\_{n \to \infty} \frac{1}{n} = 0.$$
> 1 votes

---
Tags: time-complexity
---


# Question
Title: Algorithm to find Minimal Spanning Subgraph
I'm attempting to solve this problem:

Given an undirected connected graph $G=(V,E)$ with $\mathrm{weight}(e)\>0$ for all $e \in E$, and a subset $S \subseteq V$, we define that a sub-graph $H=(V',E')$ of $G$ **spans** $S$ if $S \subseteq V'$ and $H$ is connected.

We define $H$ to be **minimal spanning** if the sum of all weights in $E'$ is smaller than the sum of all weights in every other sub-graph of $G$ which spans $S$.

The problem requires that given $G$ and $S=(v\_i , v\_j , v\_k)$ where $i\neq j \neq k$ to describe an efficient algorithm to find a minimal spanning sub-graph.

I attempted to prove that a minimal spanning sub-graph will always contain the cheapest path between $2$ of the $3$ vertices in $S$, but found counter-examples that disproved my claim.

In a previous section of the problem, I've proved that a minimal spanning subgraph when $|S|=2$ is always the cheapest path between the $2$ vertices in $S$.

However, I was not able to incorporate this proof into my attempts in solving this problem.

# Answer
> 1 votes
To my understanding, what you are looking at is a Steiner tree problem variant.

This is a $\mathsf{NP}$-hard problem, so it's no wonder you have difficulties solving it.

Maybe you can find some answers here (didn't read the paper in details, though).

# Answer
> 1 votes
Since there are only three vertices in ***S***, you can solve this problem by solving the following integer program. Let $w(e)$ be the weight of edge $e$ and $x\_e$ a binary variable indicating if $e \in H$. We also define $\delta(U) = \\{uv \in E: u \in U, v \notin U\\}$ for some $U \subseteq V$.

$min$ $\Sigma(w(e)x\_e: e \in E)$

$\Sigma(x\_e: e \in \delta(U))$ $\\\>$ $(U \subseteq V, v\_i \in U, v\_j \notin U)$
$\Sigma(x\_e: e \in \delta(U))$ $\\\>$ $(U \subseteq V, v\_i \in U, v\_k \notin U)$
$\Sigma(x\_e: e \in \delta(U))$ $\\\>$ $(U \subseteq V, v\_j \in U, v\_k \notin U)$
$x\_e \geq 0$ $\forall e \in E$
$x\_e \in \mathbb{Z}$ $\forall e \in E$

# Answer
> 0 votes
This is the Steiner tree problem in graphs with three terminals. It can be solved in polynomial time. You can use for example the Dreyfus-Wagner algorithm to solve it. In the case of three terminals it boils down to the following: Compute for each vertex (including the three terminals) the shortest path to each of the terminals and choose the vertex such that the sum of these paths is minimum. The three (possibly single-vertex) shortest paths to the terminals give you an optimal solution.

---
Tags: algorithms, graphs, weighted-graphs, connected, subgraphs
---


# Question
Title: Is there a well known name for an optimal route problem with continuous vertex weight?
I have the following problem. Imagine a fully connected undirected graph, and I wish to calculate the optimal route for a traveller across that graph. Each vertice can only be visited once or not at all. Each vertex visited gives a positive payoff. However, each edge has a negative cost associated with its distance. The traveller desires to maximize its profit (payoff-cost).

Is this a known problem with existing literature? The problem is clearly related to the travelling salesman, since it naturally contains a "shortest path". However, I'm yet to find a shortest path problem with continuous vertex weights and optional visitation.

The closest I found is the Target visitation problem. But in this paper, the study uses rank as vertex weights, not actual continuous weights. Further it does assume that the traveller has to visit all vertices. So it does not quite fit the formulation.

# Answer
> 0 votes
Your problem is NP-hard. The Hamiltonian path problem is a special case of this problem: put +1 payoff on each vertex, 0 payoff on each edge, then there is a path that achieves total payoff $|V|$ iff there is a Hamiltonian path in the problem.

Your problem is equivalent to the weighted longest path problem. First, create a new source vertex $s$, with payoff 0 and edges of cost 0 to each other vertex in the graph. Next, transform the graph as follows: for each vertex with payoff $p$, add $p$ from the payoff of each edge that is inbound on that vertex, and zero out the payoff on that vertex. Then you obtain a graph with payoffs on the edges and nothing on the vertices. In this graph, the longest path starting at $s$ (measured by sum of edges in the path) in the new graph is the same as the optimal route in the original graph. Moreover, if we pick a sufficiently large constant $C$ (e.g., larger than the sum of all edge costs), and make each edge out of $s$ have cost $C$, then the longest path in the new graph is the same as the optimal route in the original graph.

So, it follows that any algorithm for the weighted longest path problem can be used to solve your problem.

---
Tags: routing
---


# Question
Title: Equivalence of echo state networks and DFAs/NFAs
Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and some not, and then train it to output one or zero to indicate whether the string belongs to the language?

# Answer
Depending upon your goals, learning from example inputs might not be the best approach. It might work fine in many cases, but there are some hard languages where it will fail.

In particular, it is known that learning a regular language from a finite set of examples is NP-hard. See, e.g., https://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/, Smallest DFA that accepts given strings and rejects other given strings, https://cstheory.stackexchange.com/q/1854/5038, https://cstheory.stackexchange.com/q/27971/5038, https://cstheory.stackexchange.com/q/9807/5038, https://cstheory.stackexchange.com/q/27347/5038. It follows that there exist some regular languages where feeding in positive and negative examples and trying to train from there thus is doomed to fail.

You mention theoretical equivalence. I suspect that is true if you are allowed to choose all of the weights of the network, including those governing the hidden states. There are standard theorems saying that neural networks are universal function approximators, so a natural approach is to have the hidden state be a suitable encoding of the state of the DFA, and then select weights that make the neural network's computation of the next hidden state match the transition function of the DFA. The exact details of how you do that will depend on the exact nature of the internal architecture of the echo state network and what activation function is used, but is typically straightforward.

For more details of the universal function approximator theorem, I recommend the textbook Neural Networks and Deep Learning, specifically Chapter 4. If you work through that chapter, I suspect you will see how to prove the equivalence theorem and fill in the weights to make the ESN behave in a way that is equivalent to a DFA.

Or, you could consult the proof of the equivalence claim you relate and follow through their reasoning.
> 0 votes

---
Tags: complexity-theory, finite-automata, neural-networks
---


# Question
Title: If the certification of a problem is P-complete, is the problem NP complete?
Let's say I have some problem $A \in \mathcal{NP}$, and the problem of certifying a solution of $A$ is a $\mathcal{P}$-complete problem (I'm considering $\leq\_{logspace}$ reductions). Does this imply that $A$ is $\mathcal{NP}$-complete?

**Example / Motivation:** $\text{Circuit-SAT} \in \mathcal{NP}$, and certifying a solution of $\text{Circuit-SAT}$ is equivalent to solving the $\text{Circuit-Value}$ problem, which is $\mathcal{P}$-complete. $\text{Circuit-SAT}$ is $\mathcal{NP}$-complete.

Does this hold for all $A \in \mathcal{NP}$?

# Answer
> 1 votes
While the $\mathrm{NP}$-problems we typically study tend come with a natural notion of what a certificate is, for questions like this we need to be careful. Let's recall the certificate-based definition of $\mathrm{NP}$:

A language $L$ is $\mathrm{NP}$, if there is a polynomial-time decidable language $R$ and a constant $k$ such that $$w \in L \Leftrightarrow \exists z \in \Sigma^{|w|^k} \ \langle w,z\rangle \in R$$

Here, $\langle \cdot,\cdot \rangle$ denotes a suitable pairing function. The question now asks whether $\mathrm{P}$-completeness of $R$ (under logspace reductions) lets us conclude something about $L$. However, while $R$ determines $L$, the converse is not true. We can in fact take any given polytime decidable language $R$ and modify it in a way that makes it $\mathrm{P}$-complete without altering what language $L$ it is a certificate language for. We just make $R$ more complicated (if need be) on some useless parts; or eg require a new certificate to be an old certificate together with a solution to our favourite $\mathrm{P}$-complete problem on an instance indexed in a suitable way by the original input $w$.

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


# Question
Title: How to write recursive function in pseudocode for this number $a_n=n!+2^n$
I need to write **recursive function** in pseudocode for n-th number term of $a\_n=n!+2^n$. Whole code should be contained in one function with $n$ as function argument.

# Answer
Try to find simple functions $x=x(n)$ and $y=y(n)$ such that $a\_{n+1} = x\cdot a\_n + y\cdot a\_{n-1}$.

Thus $(n+1)! + 2^{n+1} = x n! + x 2^n + y\cdot (n-1)! + y\cdot 2^{n-1}$.

Then, hoping for good luck, separate the factorial and 2-power parts.

$(n+1)! = x\cdot n! + y\cdot (n-1)! $ and $2^{n+1} = x\cdot 2^n + y\cdot 2^{n-1}$.

After simple divisions we see this is equivalent to

$n{\cdot}(n+1) = x\cdot n + y$ and $4 = x\cdot 2 + y$.

If you plug $y = 4 -2x$ into the first equation you get a solution expressing $x(n)$ as a fractional function of $n$. This will give you $y(n)$ and thus a simple recurrence of order two for $a\_n$.
> 3 votes

# Answer
I don't think that we can find a simple recurrence of the form

$$a\_n=f(n,a\_{n-1}).$$

Following Jan's method for a recurrence on the previous two terms, we write

$$a\_n=u(n)\\,a\_{n-1}+v(n)\\,a\_{n-2}$$ or $$n(n-1)(n-2)!+4\\,2^{n-2}=u(n)((n-1)(n-2)!+2\\,2^{n-2})+v(n)((n-2)!+2^{n-2}).$$

Then by simple identification of the coefficients of the factorial and power, $$\begin{cases}n(n-1)=(n-1)u(n)+v(v),\\4=2u(n)+v(n)\end{cases}$$ which gives $$\begin{cases}u(n)=\dfrac{n^2-n-4}{n-3},\\v(n)=4-2u(n).\end{cases}$$
> 1 votes

# Answer
$$a\_{n} = n! + 2^{n}\\a\_{n+1} = (n+1)! + 2^{n+1}\\a\_{n+1}-a\_{n}=(n+1)!+2^{n+1}-n!-2^{n}= (n+1)\cdot n!-n! + 2\cdot2^{n}-2^{n}=n\cdot n!+2^n$$

$$a\_{n+1} = n\cdot n! + 2^n + a\_{n}$$

Implementing/writing a pseudocode should be fairly straightforward, although there are more terms which can be calculated recursively.
> -2 votes

---
Tags: recurrence-relation, pseudocode
---


# Question
Title: Reduction to Diagonalization language to prove that Universal language is not REC
I am having troubles in understanding why this proof is done like that. Why do we need to make a reduction to Ld which isn't even in RE to disprove Lu being rec?

And why does the book (Automata Theory, Languages and computation by Hopcroft, Motwani, ullman) constructs a machine for Ld to get a contradiction?

This is the machine that I dont understand at all

Thanks everybody in advance

# Answer
> 1 votes
The reduction is not done **to** the diagonalization language, but **from** the diagonalization language. The difference is very important here.

The idea of reduction is that the fact that there is a reduction from $A$ to $B$, noted $A\leqslant B$, can be translated as:

> if we know how to solve $B$, then we know how to solve $A$.

Another interpretation could be:

> if we cannot solve $A$, then we cannot solve $B$.

The principle of such a reduction is the following: from an instance $x$ of the problem $A$, construct an instance $y$ of the problem $B$ such that $x\in A\Leftrightarrow y \in B$.

In the reduction in HMU, the proof gives a reduction from $L\_d$ to $\overline{L\_u}$. Since the book has previously proved that $L\_d$ is not recursive (indeed, it is not even recursively enumerable), the reduction $L\_d\leqslant \overline{L\_u}$ proves that $\overline{L\_u}$ is not recursive, hence $L\_u$ is not recursive.

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


# Question
Title: When converting from nfa to dfa, do we always ignore the trap state?
Let's say we have a NFA such as follows:

We know it's equivalent DFA is follows, after minimization:

We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of states in NFA ). This is where I get a bit confused: Should we consider the "dead state" of NFA when converting to DFA. Because if we do, we would have 32 states in DFA ( in the above example ) before minimization, and if we don't, then we would have around 16 states in DFA before minimization

According to me, we should not consider the "dead state" of NFA when converting to DFA because, a dead state on a certain branch of computation of NFA just implies that that particular branch has rejected the input so there's no further state on this branch of computation. So, even if we were to consider the "dead state" in NFA, when we would convert the NFA to DFA we would have some states paired up with "dead state" ( in the power set of states )which could imply most of them would end up rejecting input because a dead state will always point back to itself

So when we not consider the "dead state" of NFA during conversion, we still end up with correct DFA because since we have 2^(states of NFA) in DFA, one of them is "phi" which we can use as sink state, because since we aren't considering the "phi" ( dead state ) of NFA, there's no other use of this state in DFA. So, in this case q4 of NFA and epsilon transition of every state of NFA would point to "phi", which, we will change from epsilon to appropriate state in DFA and point q4 to "phi". Also we can minimize this DFA and remove the dead state itself

Am i correct?

# Answer
You can indeed ignore dead states in NFA when doing the conversion. Actually, even without considering the conversion, it is generally common not to draw dead states in NFA (the notion of complete automaton stands for DFA, not for NFA).
> 2 votes

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Confusion regarding the intuition behind epsilon transition in NFA
I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )

Let's use this E-NFA as an example

My question is, do we transition along "epsilon transition" before reading any input or after reading any input?

assume input is "a"

Case 1: Before reading any input, in that case the machine would start in two states q1 and q3. Then it would read the input "a", q1 would transition to trap state and q3 would transition to q1 state, which is an accept state

Case 2: After reading any input, in that case the machine would start in state q1, it would read "a" and move to trap state + branch into 2 different states of epsilon transition i.e q1 and q3

I understand the fact that an "epsilon transition" just implies existence at both the states at the same time, but is that before reading the input or after reading the input?

Due to this, i am facing issues in the section "equivalence of DFAs and NFAs" in the same book.

Can someone explain me which is the correct case?

# Answer
> 0 votes
In the case of the E-NFA shown in the first diagram, the epsilon transitions are taken before reading any input. This is because epsilon transitions do not consume any input and are taken automatically when the machine is in a state that has an epsilon transition.

Therefore, in the example you provided, the correct case would be Case 1, where the machine starts in states q1 and q3, takes the epsilon transitions to q1 and q3, respectively, and then reads the input "a". This results in the machine transitioning to the accept state q1 and the trap state, respectively.

On the other hand, in Case 2, the epsilon transitions are taken after reading the input "a", which is not how epsilon transitions work in an E-NFA.

The reason why the machine does not "split" into multiple states after reading "a" is because the machine is not literally splitting into multiple copies of itself. Instead, the machine is simply transitioning to another state based on the input it has received and the transitions defined in the machine.

In an E-NFA, the epsilon transition is a special type of transition that does not consume an input symbol. Instead, it allows the machine to transition to another state without reading an input symbol. This means that the machine can make multiple transitions without consuming any input, which can result in the machine being in multiple states simultaneously.

---
Tags: automata, finite-automata, computation-models, nondeterminism
---


# Question
Title: Understanding Rabin-Karp's rolling hash computation
Possibly related to this. Let $T$ be the text and $n$ be the length of the pattern. I understand that if substrings of $T$ are interpreted as base-$d$ numbers where $d$ is the alphabet's size, then for all suitable $k$: $$T\[k+1\text{..}k+n\] = (T\[k\text{..}k+n−1\] − T\[k\]\cdot d^{n-1})\cdot d + T\[k+n\]$$ What I don't understand is why: $$T\[k+1\text{..}k+n\]\pmod{q} = ((T\[k\text{..}k+n−1\]\pmod{q} − T\[k\]\cdot h)\cdot d + T\[k+n\])\pmod{q}$$ where $h=d^{n-1}\pmod{q}$. Given the base recurrence above, how do you derive the corresponding modular-arithmetic recurrence? Did I even write it correctly?

# Answer
> 5 votes
#### Two modulo operations

There are two modulo operations for a modulus $0\not=q\in\Bbb N$. $\newcommand{\q}{\\!\\!\pmod q}$ $\newcommand{\Q}{\text{mod}\_q}$.

* Let $\text{mod}\_q:\Bbb Z\to\Bbb Z/q\Bbb Z$, $\text{mod}\_q(x)=\\{\cdots, x-2q,x-q, x, x+q, x+2q, \cdots,\\}$. We also write the last set as $\bar x\_q$ or $x\q$ or, with $q$ understood, $\bar x$.
* Let $\\%\_q: \Bbb Z\to\\{0,1,2,\cdots, q-1\\}\subset\Bbb Z$, $\\%\_q(x)$ is the unique number in $\\{0,1,2,\cdots, q-1\\}$ whose difference with $x$ is a multiple of $q$. We will write $\\%\_q(x)$ also as $x\\%q$, just as what we do in various programming languages.

Please note these two similar modulo operations are **very different**!

Any equality of expressions of integers that involve only addition, subtraction, multiplication and exponentiation with positive exponent becomes an equality in $\Bbb Z/q\Bbb Z$ when we apply $\text{mod}\_q$ to every integer except the exponents in the equality.

Since $\text{mod}\_q$ is so well-behaved, people also write expression like $5\\!\\!\pmod7+4$, or $T\[k\text{..}k+n−1\]\q − T\[k\]⋅h$. Thinking for a moment, how will you interpret the meaning of $5\\!\\!\pmod7+4$? Is the result an integer or an element in $\Bbb Z/7\Bbb Z$? Where does the addition take place?

That ambiguity or sloppiness might be the reason you doubt "did I even write it correctly?"

When we apply $\text{mod}\_q$ to an equality, we usually write like the following, where $\\!\\!\pmod q$ is just appended to the equality once. $$T\[k+1\text{..}k+n\] = (T\[k\text{..}k+n−1\] − T\[k\]⋅d^{n-1})⋅d + T\[k+n\]\pmod{q},$$ which is a shorthand for $$\Q(T\[k+1\text{..}k+n\]) =\Q((T\[k\text{..}k+n−1\] − T\[k\]⋅d^{n-1})⋅d + T\[k+n\])$$

#### The correct equality

Instead of the sloppy one in the question, what you intended to write might be the following equality in $\Bbb Z$. $$T\[k+1\text{..}k+n\]\\%q = ((T\[k\text{..}k+n−1\]\\%q − T\[k\]⋅h)⋅d + T\[k+n\])\\%q\label{\***}\tag{\***}$$ where $h:=d^{n-1}\\%q$.

Let us **prove** it. We know that (as integers) $$T\[k+1\text{..}k+n\] = (T\[k\text{..}k+n−1\] − T\[k\]⋅d^{n-1})⋅d + T\[k+n\]$$

By definition of $\\%q()$, we know $x-x\\%q$ is a multiple of $q$ for all $x$. In particular, for some integer $a,b$, $$T\[k\text{..}k+n−1\]= T\[k\text{..}k+n−1\]\\%q + q\cdot a$$ $$d^{n-1}= d^{n-1}\\%q + q\cdot b$$ So, $$(T\[k+1\text{..}k+n\])- (T\[k\text{..}k+n−1\]\\%q − T\[k\]⋅(d^{n-1}\\%q))⋅d + T\[k+n\])=(qa-T\[k\]\cdot q\cdot b)\cdot d, $$ which is a multiple of $q$. Since $x\\%q=y\\%q$ when the difference between $x$ and $y$ is a multiple or $q$ (i.e., when $x\q=y\q$), we obtain $\eqref{\***}$.

---

People could also interpret the equality in the question as the following equality in $\Bbb Z/q\Bbb Z$, $$\Q(T\[k+1\text{..}k+n\]) = (\Q(T\[k\text{..}k+n−1\]) − \Q(T\[k\])⋅h)⋅\Q(d) + \Q(T\[k+n\])$$ where $h:=\Q(d^{n−1})$, or the following equality in $\Bbb Z$, $$\overline\\%q(\Q(T\[k+1\text{..}k+n\])) = \overline\\%q(\Q((T\[k\text{..}k+n−1\]) − T\[k\]\cdot h)\cdot(d) + (T\[k+n\])))$$ where $h:=d^{n-1}$ and $\overline\\%q:\Bbb Z/q\Bbb Z\to\Bbb Z$, $\overline\\%q(\Q(x))=\\%q(x)$.

#### A defense for sloppiness

There is a reason why people become sloppy when applying $\Q$ or $\\%\_q$.

**Sloppy-Modulo principle.** Fix a modulus $q$. Given two expressions, we can replace any integer in either expression by another integer whose difference from it is a multiple of $q$ repeatedly any number of times. As long as the last step is applying $\Q$ or $\\%\_q$ or $\overline\\%\_q$ to both sides, the two expressions at the end will be equal if they were equal originally.

Although not for all expressions such as the ones that involve division, the principle applies to many situations, endowing you with lots of freedom to transform many equalities.

---
Tags: search-algorithms, modular-arithmetic, string-matching, rolling-hash
---


# Question
Title: Why is data generated from a randomly constructed Markov chain not compressible?
For a project I'm working on, I need to generate some data to test the Gzip compressor, and I wrote my own implementation of Markov chain for it, and it's a 2-level nested one.

But when I generate data using my script and feed it to Gzip, it always - without exception - expands the data, as if there's no redundancy in it.

What could be causing this? How can I modify my Markov chain so that it generates compressible data?

# Answer
> 1 votes
In the factory function that generates MC definition, each state has the probability of transitioning to other states that're uniformly random, I guess that this is the biggest problem.

Suggestion for improvement: Make the probability more sparse and skewed for each state for starters.

(I've made a new commit)

---
Tags: data-compression, markov-chains
---


# Question
Title: Is a^n , n = 3j+4k , n>=0, a context-free language?
I have no idea how to approach this question... How would I go about proving or disproving this? any explanation is appreciated.

# Answer
As nothing is mentioned about $j,k$ I can think of 2 possible cases,

**Case 1**: when $j,k \in N$

$L = $ {$a^{n}$ | $n=3j+4k\>=0$}

We have to find possible solutions of $3j+4k\>=0$, for $j,k \>=0$ this equation holds true, we can rewrite $a^{n}$ as follow

$a^{n} = a^{3j+4k}$ $=a^{3j}.a^{4k}$ $=(a^{3})^{j}.(a^{4})^{k}$

from here the language can be written as $L=(a^{3})^{\*}(a^{4})^{\*}$, as we have obtained a regular expression our language $L$ is **regular** as well as **context-free**

**Case 2**: when $j,k\in R$

Any whole number $n$ can be written as $3j+4k$ where $j=n/6, k=n/8$ hence our language $L$ becomes $a^{\*}$ which is **regular** and **content-free** also.
> 0 votes

---
Tags: regular-languages, context-free, pumping-lemma
---


title: MST Of An Almost Tree

text:
# Question
Title: MST Of An Almost Tree
A graph $G = (V,E)$ is called an *almost tree* if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given almost tree graph $G$ with distinct edge weight costs that computes a minimum spanning tree of $G$ in time $O(n)$?

# Answer
> 1 votes
Here is the description of a desired algorithm in Python style pseudocode.

```
Generate a spanning tree T of G
Put all remaining edges that are not in T in a list L
For each edge e in L:
  Find the cycle C in the graph that is T plus edge e.
  If e is lighter than the heaviest edge e' in C:
    add e to T and remove e' from T

```

It requires $O(n)$ operations to generate a spanning tree. It requires $O(n)$ operations to find a cycle when you add an edge to a tree and $O(n)$ operations to find the heaviest edge in a cycle. Since there were total $c+1$ edges remaining, where $c+1$ is a constant, the for loop requires $O(n)$ operations. Adding up other operations of small time, we find that the time-complexity of the algorithm is $O(n)$.

The correctness of the above algorithm has been proved in my answer to turn MST of G to MST of G with one new edge. Note that initially T is its own MST.

# Answer
> 0 votes
I am writing a new answer because I can't comment yet.

I'm new to graph problems, but I think it is possible to optimise a bit Jonh L.'s answer by finding the cycle in a way that is O(logn) instead of O(n).

Of course, the complexity of the whole algorithm itself remains the same ((c + 1)logn + n is still O(n)), but it's just something I wanted to mention since I took the time study this problem a bit.

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


# Question
Title: Implementation of cantor set without recursion
I'm working on the implementation of a cantor set on a 2-dimensional plane. It looks like this. Honestly, There is the obvious algorithm for the cantor set, but it includes a recursive method call. Unfortunately, My environment(Houdini vex) does not support recursive function calls, so I have to design the algorithm without using recursion.

1. Is it possible to represent a cantor set without recursion?
2. How can I represent the recursive thing in the algorithm without recursion?

```
int size=ch("size"); //size=27
int can[]={0};
int offset=0;
int col=size;
append(can,size);
int index=0;
int step=1;
int temp[]={};
int firstentry=0;

function void line(int x1; int x2)
{
    //this function gets x1(startpoint), x2(endpoint) and color entries in
        int step= x2-x1;
        if (step==0)
        {

        //color the single sqaure
            setprimgroup(0,"cantor",x1,1,"set");
        }

        else{

             //setprimgroup do the role of coloring the squre.

            for(int i=x1; i<=step+x1; i++)
            {
                setprimgroup(0,"cantor",i,1,"set");
            }
        }

}
while(size>=1)
{
    //first step 0~26
    if(index<size)
    {
        //first line is set.
        setprimgroup(0,"cantor",index,1,"set");
        index+=1;

        //first entry indicates the first entry of the row.

    }

///
    else{
        //split by 1/3
        //first entry indicates the first entry of the row.
        firstentry+=col;
        size=size/3;
        step=step*2;

        //done only for subdivision ex 1,2,4...
        for(int i=0; i<step; i++)
        {

            offset = size*2;
            int start=index;
            int end= start+size-1;

            line(start,end);

            printf("start %g end %g \n",start,end);

            index+=offset;
           //
        }

        index=firstentry+col;

        //for recursive step, multiply by 2.

    }

}

```

this language resembles C, I don't want you to do coding for me. Please present just an idea for correcting the gap calculation.

# Answer
> 2 votes
Yes. It can be expressed without recursion, as long as you have loops and data structures. Any recursive algorithm can be converted to a non-recursive iterative algorithm, by introducing an explicit stack. See, e.g., Iteration can replace Recursion?, Iterative and/or tail-recursive implementations of merge sort?, Do we need recursion in programming language to solve any problem?.

---
Tags: recursion
---


# Question
Title: Is the equivalence problem of a CFG and a FSM decidable?
I have the following problem:

> Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\\{0, 1\\}$. Is it decidable whether $L(\mathcal{G})=L(\mathcal{A})$?

I assume this is *undecidable*, since I already know the following fact:

> It is undecidable whether $L(\mathcal G)=R$ for CFG $\mathcal G$ and regular language $R$.

Therefore I think it should be impossible to decide whether a CFG and a FSM generate the same language. Is my assumption correct?

# Answer
Yes, your assumption is right regularity of context-free languages is undecidable.

You can look at the problem like this, If $L(G) = L(A)$ then we can say $L(G) \subseteq L(A)$ and $L(A) \subseteq L(G)$ which can also be written as

$L(G) \cap L(A)^{c} = \emptyset$ and $L(A) \cap L(G)^{c} = \emptyset$

Now for the first equation, regular languages are closed under complement so it comes down to checking the emptiness of $CFL$ $\cap$ $Reg$ which is equivalent to the emptiness of $CFL$ which is decidable.

Similarly, for the second part, we need to check the emptiness of $Reg$ $\cap$ $CSL$(as $CFL$ are not closed under complement) which is equivalent to the emptiness of $CSL$ which is undecidable.

Hence the equivalence problem of a CFG and an FSM is undecidable.
> 1 votes

---
Tags: regular-languages, finite-automata, context-free, undecidability
---


# Question
Title: Logic Programming - A definite program for the theory of groups
I am studying theoretical computer science using Ayala's book "Fundamentos da Programação Lógica e Funcional" (the book is written in Portuguese), but the part I am studying right now is based on Lloyd's book "Foundations of Logic Programming".

I am currently in the part about definite programs, trying to solve the following textbook exercise:

> Give a definite program for the theory of groups, specified with the axioms $x \cdot (y \cdot z) = (x \cdot y) \cdot z$, $x \cdot e = x$ and $x x^{-1} = e$. Prove that $e x = x$ and $x^{-1} x = e$.

My doubt is in the beginning. I think that the terms should be formed using the constant $e$ (to represent the identity of the group), the unary function $i$ (to represent the inverse), the binary function $\cdot$ (to represent the group operation) and variables $x, y, z, \ldots$ But what should I use as a predicate symbol in my definite program?

Thanks in advance.

# Answer
I am not sure it's the most elegant approach, but you can use a predicate symbol for equality. Let's denote this predicate symbol by $eq$. A definite program for the task would contain the following 3 definite program clauses for the 3 axioms:

> $eq(x \cdot (y \cdot z), (x \cdot y) \cdot z) \leftarrow $
>
> $eq(x \cdot e, x) \leftarrow$
>
> $eq(x \cdot i(x), e) \leftarrow$

I would also add the following clauses to operate easily with the idea of equality:

> $eq(x, x) \leftarrow$
>
> $eq(x, y) \leftarrow eq(y, x)$
>
> $eq(x, y) \leftarrow eq(x, z), eq(z, y)$
>
> $eq(x \cdot y, x' \cdot y') \leftarrow eq(x, x'), eq(y, y')$
>
> $eq(i(x), i(x')) \leftarrow eq(x, x')$

Then, proving $x^{-1} x = e$ means proving the goal $G\_0: \ \leftarrow eq(i(x) \cdot x, e)$, which can be done as sketched (I switched to traditional group notation):

> 1. Obtain $eq(e, (x^{-1}x) (x^{-1}x)^{-1})$
> 2. Obtain $eq(x^{-1}x, x^{-1}(x x^{-1}) x)$ and hence obtain $eq((x^{-1}x) (x^{-1}x)^{-1}, (x^{-1}x) (x^{-1}x) (x^{-1}x)^{-1})$
> 3. Obtain $eq((x^{-1}x) (x^{-1}x) (x^{-1}x)^{-1}, x^{-1} x) $
> 4. Combine the results from steps 1, 2 and 3.

Finall, proving $e \cdot x = x$ means proving the goal $G\_1: \ \leftarrow eq(e \cdot x, x)$, which can be done as sketched (I switched to traditional group notation) below:

> 1. Obtain $eq(ex, xx^{-1}x)$
> 2. Use what we just proved: $x^{-1} x = e$ to obtain $eq(xx^{-1}x, xe)$.
> 3. Obtain $eq(xe, x)$ and, combining that with the two previous step, the result will follow.
> 0 votes

---
Tags: group-theory, logic-programming
---


# Question
Title: Efficient Way to Calculate Timebased Followership
**Problem**

A time based followship is defined as a person changing to a new job, and there is an existing employee there in the new company whom he used to work together. In this case, the old guy gets 1 ***follow***.

**Challenge**

I wrote some simulation code, but the complexity is quadratic and already taking a few minutes for 10k-ish of people, very hard to distribute and scale for a large population. (estimated to take 4hs for 100K people)

**What I Tried**

Here is my implementation:

1. loop through every year
2. for each year, find who changed the job
3. for each job change, find the new coworkers
4. for each new coworkers, find whether they used to work together or not
5. if so, add a point to the coworker as the "leader"

**input** The is individual employment history (person, year, company), similar to linkedin.

```
year | person | company
2000 | p1     | c1
2000 | p2     | c2
2000 | p3     | c2     p2, p3 coworking at c2
2010 | p1     | c3
2010 | p2     | c10
2011 | p1     | c3
2011 | p2     | c3     p2 followed p1 at c3
...                    because p2 changed job from c10 (2010) to c3 (2011)
...                    and p2 and p3 used to work together

```

**outcome**: The final outcome is a list of people and how many followers they have at the last year. for example:

```
person | year | follower
p3     | 2010 | 0
p2     | 2010 | 0
p3     | 2011 | 1 <- p2 followed p3
p2     | 2011 | 0

```

I had some optimization for the find/lookups, for example:

1. a dictionary maintaining company/year to quickly find coworkers
2. a set maintaining pair of coworkers (once coworker, always coworker)

The code was implemented in Python with a lot of for loops, bit manipulation and vectorization could help but I don't think it will change the quadratic nature of the problem, the bottleneck will still exist.

I was thinking about relational database (postgres) or graph database (Neo4j) but cannot think of any immediate benefit.

Is there an algorithm that can handle this efficiently? My performance benchmark states it is O(n^2) so looking for something that is O(n) or faster.

# Answer
> 1 votes
Here is a pragmatic approach that is quadratic in principle but might be good enough in practice, depending patterns of employee movement from company to company.

For each employee, enumerate all pairs of two companies that this employee has worked for. Build up a dict that maps from a pair of companies to the list of employees who have worked for both companies.

Next, for each pair of employees who have worked at the same two companies, check if they were at those two companies at overlapping times, and if so, increment one of their follower counts.

My hope for efficiency is based on the following assumptions: (1) each person is only employed by a few companies during their career, (2) there aren't too many pairs of employees who have worked at the same pair of companies. If these assumptions are sufficiently wrong, this algorithm might be very inefficient.

At a technical level, this appears to be related to finding instances of $K\_{2,2}$ as a subgraph of a large bipartite graph.

---
Tags: time-complexity, time-series-analysis
---


# Question
Title: Why is this a flawed counterexample to P=NP?
I apologize in advance for asking this, since I'm sure this site is flooded by amateurs like me asking about P and NP. If there's a better platform to ask this on, please let me know, but this question has always bothered me.

Suppose you have a perfect binary tree of depth $d$. Each node contains a boolean. Of the $2^{d}$ leaves, exactly one is labelled `true` (at random) and the rest are `false`. The question is "Is the `true` node in the left half of the tree"? Clearly, there is no efficient algorithm for finding the `true` node (since it has been assigned at random) besides exploring all $O(2^d)$ leaves. A solution, however, can be verified in $O(d)$ time by simply providing the path from the root node to the `true` leaf.

If valid, this would be an example problem that is in NP, but not P, showing that P!=NP (unless I'm mistaken). I believe where this example goes wrong is that in the formal definition of a decision problem, $n$ is the size of the input. Since our tree is an input, $n=2^d$ and the naive algorithm is actually $O(n)$, and thus in P. Is this the only issue, or is there something more fundamental that I'm completely missing?

If that's the only issue, then can we circumvent it by some clever mechanism for generating a similar problem from a smaller input?

# Answer
The problem is that representing the tree takes exponential space, so the input length is $2^d$. Therefore a running time of $O(2^d)$ is actually polynomial in the length of the input: we care about whether the algorithm's running time is polynomial in the length of the input, in bits, not some other parameter. In other words, this problem is in P.

I think you are accurately getting at a core aspect of the P vs NP problem. Suppose instead of writing down the entire tree, we had a function $f$ that was implicitly specified, that let us compute for a given leaf whether it is labelled true or false. Maybe there is a way to write down an algorithm or circuit or description for $f$ that is much shorter than $2^d$ in length. Then we get a new problem, that is similar to your problem but not identical. Intuitively, it seems unlikely that there is anything better than trying all leaves, for this new problem. But actually proving that is very hard. Our intuition might be misleading. Maybe there is some way to use the structure in $f$ (that ensures it is not a totally arbitrary function, but rather one with a short description) to more quickly find the leaf that is true. It seems challenging to imagine how that could be the case, but we have no proof that it is impossible. This could be said to be a reason why we might intuitively expect P != NP, but we don't know how to prove that rigorously.
> 2 votes

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


# Question
Title: Choosing root for maximum matching in tree
This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part.

> Choose a root arbitrarily. For each subtree, calculate the maximum matching within the subtree, as well the maximum matching within the subtree that doesn't touch the root of the subtree. You can think of it as a form of dynamic programming.

How do we *prove* that choosing a root arbitrarily does not result in a non-optimal solution?

I tried to think in terms of another solution: every tree is a bipartite graph, and size of maximum matching in a bipartite graph equals maximum flow in a modified graph. But could not proceed.

---

**Edit:**

Let the nodes of the rooted tree be $1,\dots,n$.

I am using these DP states

* $without\[i\]$ is the size of a maximum matching in the subtree of node $i$, where $i$ is not matched to any of its children
* $with\[i\]$ is the size of a maximum matching in the subtree of node $i$, where $i$ is matched to one of its children

Transitions

* $without\[i\] = \sum\_{j\in children(i)}\big\[\max(with\[j\],without\[j\])\big\]$
* $with\[i\] = \sum\_{j\in children(i)}\bigg\[1+without\[j\]+\sum\_{k\in children(i)\backslash j}\big\[\max(with\[k\],without\[k\])\big\]\bigg\] \\ = \sum\_{j\in children(i)}\big\[1+without\[j\]+(without\[i\]-\max(with\[j\],without\[j\]))\big\]$

# Answer
> 0 votes
You can prove this by a case analysis. Consider any optimal solution. Either the root is matched to another vertex, or it is unmatched. If it is matched to some other vertex, consider all possible cases for what the root might be matched to. Make sure that your dynamic programming algorithm handles all of those cases correctly.

In other words, the way you prove it is correct is by writing down a proof of correctness for your algorithm (which happens to choose the root arbitrarily). I have attempted to outline above how I anticipate such a proof of correctness will go. If the proof works correctly no matter how the root is chosen, then you have solved your problem.

---
Tags: graphs, trees, matching
---


# Question
Title: ε-NFA to DFA - initial state with only epsilon transitions
I am having trouble discovering how to convert a ε-NFA to DFA (image below) when all transitions in the initial state are epsilon transitions. I already know how to convert ε-NFA to DFA (common cases), but this case I never saw before.

Thank you guys!

# Answer
Here is an algorithm to convert an $\epsilon$-NFA to an equivalent DFA.

Let the $\epsilon$-NFA consist of a set of states $Q$, an initial state $q\_0$, a set of accepting states $F$, and a transition function. We construct a DFA on the set of states $2^Q$ (the power set of $Q$). The initial state is the $\epsilon$-closure of $q\_0$ (the set of all states in $Q$ reachable from $q\_0$ by a path of $\epsilon$-transitions). A state is accepting if it intersects $F$. We define the transition function $\delta$ as follows: given a state $S \in 2^Q$ and a letter $a$, $\delta(S,a)$ consists of all states in $Q$ reachable from a state in $S$ by taking an $a$-transition followed by a path of $\epsilon$-transitions.
> 1 votes

# Answer
to start, ask yourself: from the start state where I can go with epsilon transitions (including start state itself)? from q1 using epsilon, we can go to 0, 1, 2, 4, 6 after that draw a combined state. next: give it an input, and consider each state alone, For example: if we are on state 4 and read 'a' where can we be? 5, but 5 has an epsilon transition to 3,1,0,2,6,4 so combine them all together again. use this algorithm and think about each state alone and their connection using epsilon transition,our final diagram will be something like what I drew above
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Checking if there exists a 'source' vertex
In a directed graph $G=(V,E)$ we denote a vertex $s\in V$ to be a 'source' if there exists in $G$ a path from $s$ to all other vertices $u \in V$.

The problem asks for an efficient algorithm to return the 'source', in case there isnt any, return false.

I've been able to come up with a naive approach to his problem:

$\forall v\in V$:

Do $DFS(v)$, mark $S\_v$ to be the set of vertices contained in DFS tree starting at $v$

if $|S\_v|=|V|$, return $v$

After doing this for all $v\in V$, if we finished looping, return false.

This algorithm runs in $O(|V|\cdot (|V|+|E|))$ which is far from what I'm looking for, however I am unsure how to improve this.

EDIT:

Since we know a DAG has a vertex $v$ which $degree\_{in}(v)=0$, we can use this fact to solve this problem:

I've come up with a new algorithm with a $O(|V|+|E|)$ runtime:

1. perform tarjan's algorithm to find SCC's and create the quotient graph $G'$.

(since the quotient is a DAG, we can apply the topological sort algorithm)

2. perform a topological sort on $G'$, mark $v$ to be the first node after sorting
3. perform $BFS$ on the first node after sorting.
4. if any of the paths from $v$ to a node in $G'$ is of length $\infty$ (which means there isnt a path from $v$ to said vertex), return that there is no source vertex.
5. return $v$

I'm not completely sure about choosing the first vertex after sorting, but it's the only thing that came to mind.

Are there any ways to improve this/simplify in a way that the proving stage would be simpler?

# Answer
Hint: if you find all the *strongly connected components* in the graph, the *quotient graph* of the SCCs is a DAG. In this DAG, if there is a meta-node that can reach all the other meta-nodes, you have your answer.

Check out the Wikipedia article on strongly connected components.

A DAG has a *source* vertex if and only if it is connected and *only one vertex* has in-degree 0.
> 2 votes

---
Tags: graphs, depth-first-search, topological-ordering
---


# Question
Title: Enumeration of tree vertices such that each vertex has unique neighbor appearing before it
*(Diestel, Graph Theory)* **Corollary 1.5.2:** Every tree has an enumeration of the vertices $\\{v\_1, v\_2\ldots v\_n\\}$ such that each vertex $v\_i$, with $i\geq 2$, has a unique neighbour in $\\{v\_1, v\_2\ldots v\_{i-1}\\}$.

I am wondering if there is an efficient algorithm that could produce such an enumeration in $O(n)$.

# Answer
> 1 votes
Pick an arbitrary root. Do a preorder traversal. Now, each vertex has a unique neighbour prior to it in the ordering, namely its parent.

---
Tags: algorithms, graphs, trees
---


# Question
Title: Is there a sub-NP algorithm to satisfy or prove unsatisfiable a set of a<b<c OR c<b<a constraints
This problem's been stumping me for the better part of a week:

You're given a set of triplets of variables. The variables are all distinct and ordered. Each triplet $a,b,c$ means that either $a\<b\<c$ or $c\<b\<a$. The problem is to find an ordering of the variables satisfying all constraints.

For example, the set $\\\{(a,b,c),(d,c,b),(b,d,e)\\\}$ is solvable by assigning $a\<b\<c\<d\<e$. By symmetry you can assume $a\<b\<c$ to start, and the rest of the sequence is derivable by finding triplets where a pair has been seen already. In contrast, a set like $\\\{(a,b,c),(a,c,b)\\\}$ is unsatisfiable, as if $a\<b\<c$ then the second triplet implies either $b\>c$ or $a\>b$.

---

The natural solution to me is do directly model this as integer linear programming, where all values are distinct integers in $\[0, |\text{Variables}|)$ and the triplets are directly encoded as an equation and solved. This works (and is performant), but it may be suboptimal for the special case.

Most of my attention has been looking at whether you can build a directed (acyclic) graph where the variables can be topologically sorted: $a \> b$ if the DAG has a path from $a$ to $b$, and if at any point an unavoidable cycle occurs then it's UNSAT. This also works, but I can't find a clever way avoid doing backtracking at some point, as there are many problem instances where guessing orderings becomes necessary.

I suspect the problem is NP, but I can't prove it. This also seems like the type of problem that would have been heavily researched due to its simplicity, but I can't find any references.

# Answer
> 1 votes
This is known as the betweenness problem. It is in NP (you can easily check the correctness of any proposed solution in polynomial time), and is NP-hard.

---
Tags: algorithms, integers, ordering
---


# Question
Title: Example of a function with specified running time
Can someone help with an example of a function such that $f(m ,n)$:

1. $f(m ,n)$ takes 2 parameters $(m, n); \ m, n \in \mathbb{Z^+}$
2. The optimal running time to compute is $C(|m|^{|n|})$ in the worst case, where $|n|$ and $|m|$ is the size (number of bits) of $n$ and $m$ respectively.
3. The value of $f(m, n)$ is dependent on both $m$ and $n$ such that for two sets: $\\{f(1, n\_0),f(2, n\_0)...f(\infty, n\_0)\\} = \\{f(1, n\_1),f(2, n\_1)...f(\infty, n\_1)\\}$ iff $n\_0=n\_1$
4. The output of the function is polynomial in size as compared to $|m|+|n|$

I have been thinking about it but couldn't find a specific example.

# Answer
A plausible candidate is

$$f(m,n)=(m,n,H(m,|m|^{|n|}),H(n,|m|^{|n|})),$$

where $H(t,k)=1$ if the Turing machine denoted by $t$ halts in at most $k$ steps, or $H(t,k)=0$ otherwise. I have no proof that the optimal running time is as claimed, but I suspect that it does, and all other criteria are met.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Comparing two rooted n-ary trees irrespective of the order of children nodes?
I want to compare two trees: I will consider the trees equal if they are:
Isomeric-i.e have the same structure.
Nodes in both trees have the same values but the order of the children nodes are not necessarily the same.
A picture is worth a thousand words: eg:

```
A)                B)              C)                D)
    (2)                (2)               (2)                  (2)
  /  |  \            /  |  \           /  |  \              /  |  \
(4) (5) (7)        (5) (7) (4)       (5) (4) (7)          (5) (4) (7)
 |   |              |       |         |   |                |   |
(3) (7)            (7)     (3)       (7) (3)              (3) (7)
    / \            / \               / \                      / \
   (0) (1)       (1) (0)           (0) (1)                  (0) (1)

```

```
Trees A), B) and C) are equal.
Tree D) isnt equal to any of the trees due to subtrees:
(5) and  (4)
 |        |
(3)      (7)
         / \
       (0) (1)

```

I have already looked at the classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman but his algo only checks for structure but doesnt account for contents/values in the respctive nodes. link

I was wondering if its possible to incomporate the comparison of the actual node values into this algorithm?

A trivial algorithm will be to sort children nodes for all nodes seriallize the resulting tree for both trees then a simple comparison might suffice.

I was wondering if there exist a more eficient way of accomplishing this.

**Update: NODE values are not distinct and could be repetive.**

# Answer
> 8 votes
It's much simpler than isomorphism.

For each vertex, check that the parent is the same in both trees.

---
Tags: trees
---


# Question
Title: Assignment problem with time constraints on both axes
I have a number of agents and tasks. In my case, the agents and the tasks have time constraints: so agent1 loves doing task1, but task1 must be done at 10am or 11am, and agent1 is only available after 1130am, also, task1 and task2 can happen at the same time, but the cost increases if so.

Is there a way to introduce duplicate rows/cols or some such to account for this while still applying a naive assignment problem algorithm (e.g. Hungarian)?

# Answer
If all tasks take one hour and are required to start "on the hour", then you can make a bunch of copies of each agent and each task, one per hour of the day.

For more complicated situations, I don't know of any way to represent this as an assignment problem. You might do better to solve it using integer linear programming, which is much more flexible (though potentially can be much harder to solve).
> 1 votes

---
Tags: algorithms
---


# Question
Title: If $L_1 \cup L_2 \in RE$ does it implicate that at least one of them is also in RE?
This was one of my exam questions and the answer is apparently no.

Can someone explain why because I don't understand.

# Answer
> 1 votes
There exist languages which are **Non-RE** and their complement is also **Non-RE**, let $L$ be such a language we can say that

$L \cup L^{c} = \Sigma^{\*}$

Here both languages are **Non-RE** but their union is $\Sigma^{\*}$ which is regular as well as **RE** also.

---
Tags: regular-languages, automata
---


# Question
Title: Difference b/w Functional and Decisional Problem's computational complexity
I am trying to understand the difference b/w functional and decisional problems. The core as I understand is this:

**Functional Problems:** Given an input $x$ we calculate some function $f(x)=y$ over it.

**Decisional Problems:** Given inputs we output *YES* or *NO* depending on some logic or algorithm.

As far as I have read a functional problem can always be converted into a decisional problem as follows:

For any functional problem $f(x)=y$ where we compute $y$ we instead post this as a decision problem $d(x, y)$. The output is YES, if $f(x)=y$ and no otherwise. Thus, the Turing Machine which internally encodes the function $f(x)$'s logic, takes the potential (input, output) pair and decides if the given input can achieve the given output according to the internally encoded logic of $f(x)$.

**Query 1:** Let the Turing machine $T\_f$ reads input $x$ and outputs the calculated output $f(x)$ on the tape and halts. Let the second Turing machine $T\_d$ reads the pair of values $x, f(x)$ decide that the $f(x)$ is achievable from $x$ or not and accordingly outputs YES or NO on tape and halts.

Won't both of these Turing Machines have the same computational complexity? In fact they would have nearly the same running time since in both cases we are calculating the same function $f(x)$: In $t\_f$ we output the calculated value and in $T\_d$ we compare the calculated value to the second input and output YES/NO? But wiki states otherwise:

https://en.wikipedia.org/wiki/Decision\_problem

"Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair $(x,y)$) when the function is not computable in polynomial time (in which case running time is computed as a function of x alone). The function $f(x) = 2^x$ has this property."

What am I missing? Can someone please elaborate.

# Answer
What you're missing:

First, given $x,y$, there might be an easier way to test whether $f(x)=y$, without having to compute $f$ on input $x$. For instance, when $x$ is an integer, suppose that $f(x)$ outputs the factorization of $x$. This is believed to be hard to compute (there is no known polynomial-time algorithm). But if you give me a candidate factorization, I can very efficiently verify whether it is a correct factorization (it can be done in polynomial time).

Second, as Wikipedia explains even though both Turing machines have the same running time as a function of the length of $x$, they do not have the same running time as a function of the length of the input. The length of $y$ might be much larger than the length of $x$, so the length of the input $(x,y)$ to the second Turing machine might be much larger than the length of the input to the first Turing machine. The computational complexity is measured as a function of the length of the input. So, the same running time (namely, $x$) might be an exponential function of the length of the input to the first Turing machine (namely, $\lg x$), but be a polynomial function of the length of the input to the second Turing machine (namely, $x+\lg x$, in the example given in Wikipedia).
> 1 votes

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


title: Binary subsets for a given set

text:
# Question
Title: Binary subsets for a given set
Lets take an example of the range of N=32 bits

```
2^32 = 4294967296

00000000000000000000000000000000
00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000011
...
11111111111111111111111111111100
11111111111111111111111111111101
11111111111111111111111111111110
11111111111111111111111111111111

```

Now lets consider a subset within this range whose consecutive 0s can be 0 to maximum 3 0s.

The following are examples of valid and invalid subsets -

Valid subset (consecutive 0s - 0 to maximum 3):

```
00100100100100100100100100100101 - (subset 0)
10101010101010101010101010101010 - (subset 1)
10010010010010001000100010101111 - (subset 2)
11011001000111101000100010010011 - (subset 3)
...
11111111111111111111111111111111 - (subset S max value)

```

So, count(valid subset) \< 2^32

Invalid subset (at least 1 consecutive 0s \> 3):

```
10000111111111111111111111111001
10101010100000000001111000100111
11111111101010101010101010000001
10000000000000001111010100010101
...

```

I have the following queries -

1. How to find the total count of valid subsets for a given value of N (ex. 2^32, 2^40, 2^64 etc)
2. How to dynamically generate the subset value for each matching subset, in an incremental manner, for a given value of N (ex. 2^32, 2^40, 2^64 etc)

So, for N=32,

```
If the value is "00100100100100100100100100100101", then subset value "0" must be dynamically generated
If the value is "10101010101010101010101010101010", then subset value "1" must be dynamically generated
If the value is "10010010010010001000100010101111", then subset value "2" must be dynamically generated
If the value is "11011001000111101000100010010011", then subset value "3" must be dynamically generated
If the value is "11111111111111111111111111111111", then subset value "subset S max" must be dynamically generated

```
3. Consecutively, given the subset value, the bit value must also be dynamically generated

So, for N=32,

```
If subset value is "0", then bit value "00100100100100100100100100100101" must be dynamically generated
If subset value is "subset S max", then bit value "11111111111111111111111111111111" must be dynamically generated

```

and so on...

The main point is *dynamically generating the values*, so they are not required to be stored; this is feasible for large values of N (ex. 2^32, 2^40, 2^64 etc and greater)

# Answer
Let $A(n,k)$ denote the number of valid strings of length $n$ ending with a string of $k$ zeroes. Then:

* $A(0,0) = 1$
* $A(0,1) = A(0,2) = A(0,3) = 0$
* $A(n+1,0) = A(n,0) + A(n,1) + A(n,2) + A(n,3)$
* $A(n+1,k+1) = A(n,k)$

You are interested in $A(n,0) + A(n,1) + A(n,2) + A(n,3)$ for various values of $n$.

Using these formulas, it is routine to implement ranking and unranking, that is, to convert a valid string to its index in the list of all valid strings, ordered lexicographically (ranking) and vice versa (unranking).

---

With slightly more effort, we can obtain a direct recurrence formula for $B(n) = A(n,0) + A(n,1) + A(n,2) + A(n,3)$: $$ B(n) = B(n-1) + B(n-2) + B(n-3) + B(n-4) $$ with initial values $B(0),B(1),B(2),B(3) = 1,2,4,8$.
> 2 votes

---
Tags: sets, binary, computer-algebra
---


# Question
Title: Optimize Multiple Agents Completing Multiple Tasks in Parallel
I have an optimization problem and I am wondering if there is a better way to solve it than using a naïve brute force method. I have a number of tasks T that must be completed, and a number of agents A to do work in parallel to one another. For this, T \> A.

What I would like to do is write a program to figure out the optimal agent-to-task assignments such that all tasks have been completed and the least amount of time OVERALL has passed. In other words, because the agents work in parallel to one another, the agent that finishes their assigned tasks last is the limiting factor and determines the overall time needed. The amount of time a task takes is independent of which agent the task is assigned to. Each task can only be assigned to and worked on by one agent.

As a simple example:

Lets say we have 3 tasks, A, B and C, which take 30, 90, and 45 minutes respectively. Lets say we have 2 agents.

A bad assignment list would be:

> Agent 1: Tasks A and B = 30 + 90 = 120 minutes
>
> Agent 2: Task C = 45 minutes
>
> overall time is 120 minutes

The optimal assignments would be:

> Agent 1: Tasks A and C = 30 + 45 = 75 minutes
>
> Agent 2: Task B = 90 minutes
>
> overall time is 90 minutes.

The way I have solved this so far is with a simple brute force method like so:

1. Generate a new permutation of the task list
2. For each task in the list:
    * Find the agent whose current task list requires the ***minimum*** time to complete
    * Assign the task to this agent
3. Once all tasks have been assigned:
    * Find the agent whose current task list requires the ***maximum*** time to complete
    * Note this time as the **result** for this permutation of the task list
    * Clear each agent's task list
4. Repeat steps 1 - 3 until all permutations have been generated
5. Once all permutations have been generated
    * Find the permutation with the minimum **result**
    * The agent-to-task assignments generated by this permutation is the optimal solution

The obvious problem with this is that when you get to more than 11 or 12 tasks the amount of permutations needed becomes unreasonable for a brute force solution.

Is there a more elegant solution to something like this? I'm not the most mathematically minded person, but the closest thing I could find when googling around was an unbalanced assignment problem, and as far as I could tell thats not quite the same thing.

PS: I'm not sure what tags to add to this question other than "optimization". I added "assignment-problem" as well but if there are more apt tags let me know and I will add them.

Thanks!

# Answer
> 1 votes
This problem is known as Makespan Scheduling and is $\mathsf{NP}$-complete. Hence, computing an optimal assignment cannot be done in polynomial time unless $\mathsf{P} = \mathsf{NP}$; i.e., under common complexity-theoretic assumptions, there is no algorithm which is guaranteed to find optimal assignments quickly.

However, steps (1) and (2) of your algorithm basically already yield a $2$-approximation (i.e. achieves an assignment whose makespan is at most twice the optimal makespan), and with some easy techniques, the approximation factor can be brought down to $4/3$. Indeed, the problem also admits a polynomial-time approximation scheme (PTAS) which achieves a $(1 + \varepsilon)$-approximation using time polynomial in the instance size and $1 / \varepsilon$. You can find a treatment of the problem in the great book *Approximation Algorithms* by Vazirani.

I don't know about existing software tools, but I would be amazed to learn that none exist given the practical relevence of the problem.

# Answer
> 0 votes
I believe your problem is equivalent to a bin packing problem. To determine whether there exists a schedule that finishes in M minutes, set the bin capacity to M. Each task is a item, whose size is equal to the time it takes to complete that that task, so we have T items. Then there exists a bin packing for these items into at most A bins, iff there is a schedule that finishes in at most M minutes. You can use any algorithm for bin packing to solve your scheduling problem, using binary search on M. Conversely, you can use any algorithm for your scheduling problem to solve bin packing, using binary search on A.

Consequently, assuming I didn't make any mistakes, your problem is about as hard or easy as bin packing is. Unfortunately, bin packing is NP-hard, so your problem is NP-hard, too. Fortunately, this does mean you can use any approximation algorithm or heuristic algorithm for bin packing to solve your scheduling problem.

A pragmatic approach for solving your problem (as for solving many real-world scheduling problems) is to formulate the problem as an instance of integer linear programming, then use an off-the-shelf ILP solver (e.g., Gurobi, CPLEX).

---
Tags: optimization, scheduling
---


# Question
Title: An algorithm to evaluate the strength of Quiz Participants
As a side-project, I had the idea to write some kind of an algorithm that would evaluate all participations in our weekly Pub quiz, to then calculate the average strength of the participants.

### This is the information that I have available:

* The final score of the group
* All members of the group for a particular week
    + As such, also the team size
    + As such, also all the past participations of every single person

### This is how I attempted to solve it:

The first, and obviously the simplest solution that I had, was thinking of the information that I have as a system of linear equations:

$$ 0 * x\_1 + 0 * x\_2 + 0 * x\_3 + \dots + 0 * x\_n = S $$

The idea was that every row represents a game, every participant gets an ID somewhere between 1 and n and every person who participated on that specific week gets a factor 1 in the corresponding row with the rest getting a zero. after solving all the linear equations, the value of each $ x\_n $ would represent how strong the person with ID $ n $ is, and the $ S $ would be the final score of the group for that week. (In the case where it's impossible to solve it, use the difference between expected answers and calculated answer as fitness to be minimized). Obviously this had a ton of flaws, the biggest one being that it would predict insane scores for bigger groups, since all the strengths are added together. This seemed like an easy fix with adding:

$$ (0 * x\_1 + 0 * x\_2 + 0 * x\_3 + \dots + 0 * x\_n) * (1 - w * log(P)) = S $$

with $ P $ being the number of players. This already worked a lot better, the idea was that the overlap of knowledge goes up logarithmically multiplied by some weight that will get calculated in the future. (can then be rewritten as $ S / (1 - w * log(P)) $ once w is set to some constant). While this "worked" for a couple of months, I am spotting more and more flaws that seem to be unsolvable without scrapping the whole system of linear equations stuff. The reason why I believe ML to not be a good solution for this, and the same reason why I think this isn't purely a data science question, is because with one datapoint being added per week, that's 52 data points per year, which I believe is way too low for any type of actual machine learning.

### The problems:

* The biggest flaw that I see in my system is that for a player $ x\_a $ with a low weight it is often that:

$$ (x\_1 + \dots + x\_n) * (1 - w * log(P)) \> (x\_1 + \dots + x\_n + x\_a) * (1 - w * log(P + 1)) $$

which to me seems absolutely absurd. (Adding an extra person to the group leads to lower predicted score than without that person)

* Second biggest flaw I see that the probabilities are missing from the equation. Assume 4 Players get 20 points on a bad week, then get 30 points on the next week with a 5th player who is participating for the first time. The solution that I get every time is to set the 5th player strength to 10 and make the 30 point game have no influence on the other 4 players. That's definitely not the solution I am looking for though, as I would expect all games to have at least some influence on the strength of all participants.

---

The question is, are there any real life problems that are similar to this? Does this type or class of problem already have a name?

# Answer
I suspect this is primarily a statistics and data modelling question, rather than a question about computer science.

If you have a model $f$ for predicting the score of a team from the strengths of the participants (i.e., the predicted score is $f(x\_1,\dots,x\_k)$, where $x\_1,\dots,x\_k$ represent the strengths of each participant in the team), then you could use inference to try to predict the unknown strengths $x\_1,\dots,x\_n$ from the observed scores. You would define a loss function $\ell$ that computes how "bad" an incorrect prediction is, such as squared error: $$\ell(\hat{s},s) = (\hat{s}-s)^2,$$ where $\hat{s}$ is the predicted score and $s$ is the true score. Then, you would define a total loss $$L(x\_1,\dots,x\_n) = \sum\_i \ell(f(x\_{p\_{i,1}},\dots,x\_{p\_{i,k}}),s\_i),$$ where $s\_i$ is the score of the $i$th team, and $p\_{i,1},\dots,p\_{i,k}$ are the participants of the $i$th team. Finally, you would use a numerical optimization algorithm to find $x\_1,\dots,x\_n$ that minimize $L(x\_1,\dots,x\_n)$.

This leaves open the question of how to build an appropriate model. That will require domain expertise and possible some intuition and art. I don't know how to choose an appropriate model. I imagine that a team with two members with strengths $x\_1,x\_2$ does better than a team with one member of strength $(x\_1+x\_2)/2$ (e.g., in the two-person team, one person might know a lot about action movies and the other person might know a lot about romance movies, so the former can answer some questions that the latter cannot and vice versa), but worse than a team with one member of strength $\max(x\_1,x\_2)$ (sometimes the two team members both think they know the answer but disagree, and they're basically flipping a coin between them). So, I leave you to devise a plausible model. Perhaps the average strength could be a reasonable starting point for a model, or you could try a few models and see which seem to yield the best results (e.g., at predicting scores for the last two weeks given data on all prior weeks).

You asked about related concepts. You might be interested in the Bradley-Terry model, which is definitely different but still related. You might also be interested in rating systems for individuals in team games. I'm not very well informed on that topic. You might be interested in TrueSkill and TrueSkill2, though I think their model $f$ would be inappropriate for your particular setting.
> 1 votes

---
Tags: linear-programming, algorithm-design
---


# Question
Title: Can we prove that any set of finite strings without substrings is finite?
I want to prove (or disprove) the following conjecture:

> Let $\Sigma$ be a finite alphabet, and let $L \subseteq \Sigma^\*$ satisfy that there are no $v, w \in L$ such that $v$ is a proper substring of $w$. Then $L$ is finite.

I have the intuition that this is true, haven't been able to find a counter example, but am unable to prove it. If this is true, how can we prove it? If this is false, how can we construct such infinite $L$?

# Answer
Assuming that by *substring* you mean *consecutive substring*, take $$ L= \\{10^n1 : n \ge 0\\}. $$

On the other hand, if you refer to nonconsecutive substrings, or *subsequence* ordering, then Higman's Lemma states that any set of incomparable strings is indeed finite.
> 10 votes

---
Tags: formal-languages, strings, finite-sets
---


title: Binary Search Tree Updating

text:
# Question
Title: Binary Search Tree Updating
How can I update values in Binary Search Tree without affecting its properties (all the nodes in the left subtree have values that are less than the value of the root node and all the nodes of the right subtree have values that are greater than the value of the root node).

I tried deleting and inserting the new Value, but It's an assignment and my teacher wants different solution with swaping nodes or rotations .

# Answer
I don't think that rotation and swapping of node value can fix the problem caused by an update. Consider the situation where the value of node $x$ decreases to $x'$. Let $y$ be the ancestor of $x$ closest to the root such that $y \< x$. Assume that $x' \< y \< x$. Then before update, $x$ is in the *right subtree* of $y$ and after update, $x'$ must be on $y$'s *left subtree* but it is in the *right subtree*.

Rotation cannot fix that. Rotation is not meant to move a node to another subtree, but rather to change the parent-child relation of two nodes while ensuring that the symmetric order (BST property) is maintained *if symmetric order holds prior to the rotation*.

Swapping of node values is not going to fix this either, since *node $x'$ should not be on $y$'s right subtree in the first place*, so you cannot simply find another node that will take the place of $x'$ to fix the tree.

If your current solution is not acceptable, then I think the closest thing you can do is to detach $x'$, while ensuring that the subtree where it was removed is fixed and attaching it to a correct location in $y$'s subtree. Your delete and insert solution is a essentially a simulation of this detach-attach approach.
> 1 votes

# Answer
Deleting the value and inserting a new one is a valid way to update a value in a binary search tree. Its asymptotic running time is as good as any other solution.
> 0 votes

---
Tags: binary-search-trees
---