# Question
Title: How to uniformly sample a sorted simplex
I am looking for an algorithm to uniformly generate a descending array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should satisfy:

```
x + y + z = 1
0 <= x <= 1
0 <= y <= 1
0 <= z <= 1
x >= y >= z

```

My guess is all i have to do is uniformly sample a simplex (Uniform sampling from a simplex), and then sort the elements. But i'm not sure whether the result sampling algorithm is uniform.

Also, rejection sampling is not ideal for me, because i'll use this for high dimension.

# Answer
> 2 votes
Yes, all you have to do is to uniformly sample a simplex, and then sort the elements, under the assumption that the given distribution on the simplex is invariant under the permutation of the coordinates and the probability of a 0-measure set is 0.

That assumption holds often by default. Hopefully it holds in your situation. otherwise, a different sampling method or some preprocessing/postprocessing may be needed.

Here is a simple argument that should convince you that uniformly sampling and then sorting results in uniform sampling, given that assumption. Suppose we get a sample $x\<y\<z$ in the end. It may come from any one of the six kinds of original sampling, $(x,y,z)$, $(x,z,y)$, $(y,z,x)$, $(y,x,z)$, $(z,x,y)$ and $(z,y,x)$. The original sampling is uniform everywhere, and hence uniform on a neighborhood of these six points. Combining six identical (small) disjoint neighborhoods of them and dividing by 6, we see that sampling and sorting is also uniform on a neighborhood of $(x,y,z)$. Since $(x,y,z)$ can be any given point with distinct coordinates and the set of all points with at least two equal coordinates has measure 0, the sampling and sorting is uniform on the whole sorted simplex.

A rigorous proof along the same line of reasoning can be written if we want to be more formal.

---
Tags: algorithms, sampling, simplex
---


# Question
Title: Meaning of this python modulo operator exercise?
I just got started with Python PCEP course material on netacad.com.

I've come across the following exercises:

```
   2 % -4 = -2
   2 % 4 = 2

```

As I understand it, the *modulo* operator returns the remainder of a division. So 2 divided by (-4) gives (-0.5). How does Python3 calculate the remainder of that as 2?

I know it's stupid but what's the reasoning behind that result?

# Answer
> 0 votes
Briefly, if $a$ is an integer and $b\>0$ is a positive integers then you can find an integer $m$ and an integer $r \in \\{0,\ldots,b-1\\}$ such that $$ a = mb + r. $$ We say that $m$ is the *quotient* and $r$ is the *remainder*. For example, if $a=2$ and $b=4$ then $m=0$ and $r=2$.

When $b$ is allowed to be negative, the exact meaning is language-specific. You can work out the case of python by trying a few examples.

---
Tags: python
---


# Question
Title: Minimize edges of a directed unweighted graph
I need to find an algorithm to find a sub-graph $G'=(V, E')$ of a directed unweighted graph $G = (V, E)$ where for all $(u, v)\in E$ there exists a path in $G'$ from $u$ to $v$ and the size of $E'$ is minimal.

As an example, $(1, 2) (2, 3) (1, 3)$ reduces to $(1, 2) (2, 3)$. Additionally, $(1, 2) (2, 3) (1, 3) (3, 1)$ reduces to $(1, 2) (2, 3) (3, 1)$.

This is not an MST (or arborescence) problem since we care every vertex as a root hence Edmond's algorithm does not work.

I am clueless at this point. At least a hint is highly appreciated.

# Answer
Recall that the *transitive closure* $H$ of a digraph $G$ has the properties that

> * (1) there is a directed path from $u$ to $v$ in $H$ iff there is a directed path from $u$ to $v$ in $G$, and
> * (2) there is no graph with fewer arcs than $H$ that satisfies condition (1).

The difference to your problem is that you require $H$ to be a *subgraph of $G$*, so it's not exactly a transitive closure you want. But note that for this problem there *are* polynomial-time algorithms.

Instead, Moyles and Thompson \[1\] consider what I believe is your problem, i.e., the problem of finding the smallest subgraph $G'$ of $G$ such that there is to a path from $u$ to $v$ in $G'$ whenever there is a path from $u$ to $v$ in $G$. They give an algorithm (see Section 4) for the problem which runs in exponential-time, so it's likely not practical for even moderately-sized digraphs.

In fact, your problem is NP-hard and it has been studied in the literature. For instance, Khuller, Raghavachari and Young \[2\] give a polynomial-time approximation algorithm with a guarantee of 1.64. On a quick skim, their algorithm seem reasonable to implement and thus practical; another approach is of course to rely on other tools such as metaheuristics.

---

\[1\] Moyles, Dennis M., and Gerald L. Thompson. "An algorithm for finding a minimum equivalent graph of a digraph." Journal of the ACM (JACM) 16.3 (1969): 455-460.

\[2\] Khuller, Samir, Balaji Raghavachari, and Neal Young. "Approximating the minimum equivalent digraph." SIAM Journal on Computing 24.4 (1995): 859-872.
> 5 votes

# Answer
There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.

Let $H$ be a connected undirected graph with at least $2$ vertices and consider the directed graph $G$ obtained by replacing each undirected edge {u,v} of $H$ with the pair of directed edges $(u,v)$ and $(v,u)$.

If there is a Hamiltonian path traversing the vertices $\langle u\_0, \dots, u\_{n-1}, u\_n = u\_0 \rangle$ of $H$, in order, then the set of $n$ edges $\\{ (u\_i, u\_{(i+1) \bmod n}) \mid i=0,\dots,n-1\\}$ of $G$ induces a subgraph $G'$ with your property.

If there is a subgraph $G'$ of $G$ with at most $n$ edges that satisfies your property, then it must have exactly $n$ edges. Moreover the in-degree and the out-degree of each vertex must be exactly $1$, and the undirected version $H'$ of $G'$ must be connected. In other words $G'$ is a cycle that that traverses each vertex of $G$ exactly once, showing that $H'$ is a Hamiltonian path of $H$.
> 6 votes

---
Tags: graphs, optimization
---


# Question
Title: Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$
The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$

How can I prove by induction that this is $\Omega(n^2)$?

I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$

# Answer
> 2 votes
Assuming $T(1)=1$, you can show by induction that $T(n) = \frac{n(n-1)}{2} + 1$.

The base case is trivial since $T(1) = 1 = \frac{1 \cdot 0}{2} + 1$.

As for the inductive step, suppose that the claim holds up to $T(n)$. $\begin{align\*} T(n+1) &= T(n) + (n+1) - 1 =\frac{n(n-1)}{2} + 1 + n \\ &= \frac{n^2 -n +2n}{2} + 1 = \frac{n^2 + n}{2} + 1 = \frac{n(n+1)}{2} + 1 \\ &= \frac{(n+1)((n+1) - 1)}{2} + 1. \end{align\*} $

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


# Question
Title: Beginner Question Concerning the Logic of a Very Simple Correctness Proof
I'm trying to familiarize myself with correctness proofs and need some help. In the proof for SimpleSelect (P.25), why do we assume both $A'\[i\] \< A'\[k\]$ and $1 \leq i \leq k$? I'm not quite sure why we do this, as the text states that because "of what it means for an algorithm to meet its specification, any proof of correctness will begin by assuming the precondition." However, isn't the precondition here simply the precondition of SimpleSelect as specified here (P.6)?

# Answer
Both of the assumptions you mention are "local" in the sense that they are a subclaim in the proof and are not part of the conditions of the theorem. You can also see them as the definition of a local variable $i$, an equivalent formulation of the two assumptions would be

> 1. Let $i$ be such that $A'\[i\]\<A'\[k\]$ and $1\leq i \leq n$.
> 2. Let $i$ be such that $1\leq i \leq k$.

The proof counts the number of values of $i$ for which these statements hold, which shows that the postcondition is satisfied.

---

I think part of your confusion follows from some implicit language in these paragraphs, so I will rewrite one of them in full to be more explicit. The first paragraph from the book reads:

> Suppose $A'\[i\] \< A'\[k\]$ for some $i$, $1 \leq i \leq n$. Then $i \< k$, for if $k \< i$, $A'\[k\] \> A'\[i\]$ violates the postcondition of Sort. Hence, there are fewer than $k$ elements of $A'$ , and hence of $A$, with value less than $A' \[k\]$.

A more explicit phrasing is as follows:

Let $i$ be such that $A'\[i\]\<A'\[k\]$ and $1\leq i \leq n$. If $k\<i$, then $A'\[i\]\<A'\[k\]$ contradicts with the postcondition of Sort, so $i\leq k$. If $i=k$, then $A'\[i\]=A'\[k\]$, which contradicts with our definition of $i$.

So, we have shown that if $A'\[i\]\<A'\[k\]$ and $1\leq i \leq n$, then $i\<k$. This means that the number of elements of $A'$ with value strictly less than $A'\[k\]$ is strictly fewer than $k$. Since $A$ is a permutation of $A'$, there are fewer than $k$ elements of $A$ strictly less than $A'\[k\]$. Since $A'\[k\]$ is the return value of the algorithm, the first part of the postcondition of Select is satisfied.

The overall structure of the second paragraph is similar, so you should be able to grasp it if you can understand the first.
> 2 votes

---
Tags: algorithms, correctness-proof
---


title: Find Best N Points From a Graph

text:
# Question
Title: Find Best N Points From a Graph
I've given a task and wonder if there are any better solutions.

Inputs of task are:

1. Distance of district pairs
2. Population of pairs

Goal is:

* Find **n** districts at which its population and districts **x** miles range districts' population is max.

Extra information:

* Unique district size is tens of hundreds.

As an example, if I pick up district **A**, population will be **A**'s population plus other districts' population which are less than **x** miles far away from it. Total population will be **n** districts at which population is calculated as I mentioned.

What I've tried:

1. Brute Force
2. Generic Algorithms

What I planning to do:

1. A\* Search

My question is, there may be any other solution (optimal if possible) instead of these one. i.e. sorting districts by their population, merging **x** miles nearest to them into one until I get **n** districts.

Any ideas?

# Answer
> 1 votes
If I understand the problem correctly, there is no polynomial-time algorithm that finds an optimal solution to your problem unless $\mathsf{P}=\mathsf{NP}$. This holds even in the special case in which all distances are $1$, all populations are $1$, and $x=1$.

To see this notice that, given a graph $G=(V,E)$ and a non-negative integer $n \le |V|$, $G$ admits a dominating set of size at most $n$ if and only if there is a set $S \subseteq G$ with $|S| = n$ such that $\sum\_{u \in V : d(u, S) \le 1} 1 = |V|$.

On the bright side, a simple greedy algorithm has an approximation ratio of $\frac{e}{e-1} \< 1.582$: iteratively add to $S$ the district $v$ that maximizes the population that falls within distance $x$ of $S \cup \\{ v \\}$, i.e., the quantity $\sum\_{u \in V : d(u, S \cup \\{v\\}) \ge x} p(u)$.

The approximation ratio of the above algorithm follows from the fact that you can cast your problem as a weighted maximum coverage problem. In this problem you have a set $X$ of elements and a collection $\mathcal{S}$ of subsets of $X$. Each element $v \in X$ has a non-negative weight $w(v)$. You are given an integer $k \le |S|$ and you want to select a subset $S$ of at most $k$ sets of $\mathcal{S}$ such that $\sum\_{x \in \bigcup\_{S' \in S} S' } w(x)$ is maximized. To reduce your problem to weighted maximum coverage problem pick $X=V$, $\mathcal{S} = \\{S\_v \mid v \in V\\}$ where $S\_v = \\{u \in V \mid d(u,v) \le x\\}$, $w(v) = p(v)$, and $k=n$

Since you can also reduce any instance of weighted maximum coverage problem to your problem, this is essentially the best polynomial-time approximation algorithm that you can hope for. The reduction is as follows: Create a complete bipartite graph $G = (V,E)$ with $V = \mathcal{S} \cup X$ and $E = \mathcal{S} \times X$. Each edge in $E$ has weight $1$. The population $p(v)$ of a vertex $v \in V$ is $p(v) = 0$ if $v \in \mathcal{S}$, and $p(v) = w(v)$ if $v \in X$. Pick $n=k$ and $x=1$. You can easily see that you can restrict yourself to a solution $S$ that does not select any district in $v \in X$ (since $S \setminus X$ is as good as $S$ and $|\mathcal{S}| \ge k = n$). Then, selecting a subset $S \subseteq \mathcal{S}$ of districts corresponds to covering all the elements in $\bigcup\_{S' \in S} S' \subseteq X$, and the population within distance $x$ of a vertex in $S$ is exactly $\sum\_{x \in \bigcup\_{S' \in S} S'} p(x) = \sum\_{x \in \bigcup\_{S' \in S} S'} w(x)$.

---
Tags: algorithms, graphs, search-algorithms, genetic-algorithms
---


title: context free grammar of given language

text:
# Question
Title: context free grammar of given language
I wonder how can I find out what is *context-free grammar* of the following language?

$$ L\_4 = \\{w\_1\\#w\_2 \mid w\_1,w\_2 \in \Sigma^\*, w\_1 \neq w\_2^R \\} $$

# Answer
> 2 votes
Assume $\Sigma = \\{a,b\\}$. We want to generate a word $w\_1\\#w\_2$ is such that $w\_1 \ne w\_2^R$. There are two obvious possibilities:

1. $|w\_1| = |w\_2|$: In these words, there has to be at least one pair of positions equidistance from $\\#$ such that the letters in these positions are different. Using the non-terminal $S\_1$, we will generate the part of $w$ till we reach the first such pair; then we transition to non-terminal $S\_2$ which will generate the opposite letters at that pair of position and move to the non-terminal $S\_3$. From $S\_3$, we are free to generate whatever we want. This will make sure that we have at least such pair of opposite letters, and hence $w\_1 \ne w\_2^R$.
We can generate such words using following grammar: \begin{align} S\_1 &\rightarrow aS\_1a|bS\_1b|S\_2\\ S\_2 &\rightarrow aS\_3b|bS\_3a\\ S\_3 &\rightarrow aS\_3a| bS\_3b| aS\_3b | bS\_3a|\\# \end{align}
2. $|w\_1| \ne |w\_2|$: In this case, with the non-terminal $P\_1$ we will generate any word with equal number of letters on both side of $P\_1$, and then we will move to either the non-terminal $P\_2$ or $P\_3$. With $P\_2$ (or $P\_3$) we will generate more letters either on the left side (or the right side) of $\\#$. In the end, this will make sure that $|w\_1| \ne |w\_2|$. We can generate such words using the following grammar:

\begin{align} P\_1 &\rightarrow aP\_1a| bP\_1b| aP\_1b | bP\_1a| P\_2 |P\_3 \\ P\_2 &\rightarrow aP\_2|bP\_2|a\\# | b\\#\\ P\_3 &\rightarrow P\_3a|P\_3b|\\#a | \\#b\\ \end{align}

For the given language, the grammar would be: $S \rightarrow S\_1|P\_1$.

---
Tags: context-free
---


# Question
Title: What is context free grammer of $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$
I can't find out how to find a *context free grammar* for bellow language, is there any specific way to solve that?

$L = \\{w: n\_c(w) \ne n\_a(w) + n\_b(w)\\}$

# Answer
> 1 votes
$\Sigma = \\{a,b,c\\}$. Consider the two cases:

1. $n\_c(w) \> n\_a(w) + n\_b(w)$: The idea is to create one more $c$ for each $a$ or $b$ produce in the word: \begin{align} S\_c \rightarrow aS\_cS\_c | bS\_cS\_c | cS\_c | c \end{align}
2. $n\_c(w) \< n\_a(w) + n\_b(w)$: In this case, we can produce as many $c$'s as $a$ and $b$ combined + 1. \begin{align} S\_{ab} \rightarrow aS\_{ab} | bS\_{ab} | cS\_{ab}S\_{ab}|a|b \end{align}

The grammar for the required language would be : $S \rightarrow S\_c | S\_{ab}$.

---
Tags: context-free
---


# Question
Title: Is this an LL(1) grammar? How to solve First - Follow conflict?
im trying to check if this grammar is LL(1).

S -\> L = R
L -\> * L | id
R -\> L | R + R | num

As you can see there is a Left recursion on R production. So i remove that and what i get is:

S -\> L = R
L -\> * L | id
R -\> L R' | num R'
R' -\> + R R' | ε

Now the problem that i have is that First and Follow set of R' rule have a common non-terminal ("+") and also FIRST(R) and FOLLOW(R') has a common non-terminal. So i wonder how to create the parsing table if there's this conflict. My question is: is there a way to solve this problem or simply this isn't an LL(1) grammar?

Thanks.

# Answer
Your original grammar is not only left-recursive, it is also ambiguous. Left-recursion only matters to certain parsing techniques, but ambiguous grammars are, by definition, impossible to parse with a deterministic parser. And removing left-recursion does not in general fix ambiguity.

The ambiguity is in the production

```
R → R + R

```

which allows `1 + 2 + 3` to be parsed in two different ways: as the result of adding `3` to `1 + 2` or as the result of adding `2 + 3` to `1`. (These have the same value, but if the operator had been `-` instead of `+`, the ambiguity would allow two different evaluations.)

The correct way to write this grammar unambiguously is

```
 S → L = R
 L → *L | id
 R → F | R + F
 F → L | num

```

With that grammar, `1 + 2 + 3` can only be parsed as the sum of `1 + 2` and `3`, because `2 + 3` is not an `F`. That makes `+` a left-associative operator, which is the normal usage. (Again, this is clearer if you consider the operator `-`: `1 - 2 - 3` is `-4`, not `0`.)

You can then, if you want to, apply the left-recursion elimination algorithm, to yield:

```
 S → L = R
 L → *L | id
 R → F R'
 R'→ + F R' | ε
 F → L | num

```

Note, however, that after left-recursion elimination, the associativity of `+` is not so clear. With a simple operator grammar like this, left-recursion elimination is essentially the same as the two steps:

1. Change left-associative operators (left-recursive productions) to being right-associative.
2. Left-factor the productions.

Thus, after left-recursion elimination, a left-associative grammar and a right-associative grammar are the same.
> 1 votes

# Answer
Your factoring is wrong. It should be (written as regular espressions):

$\begin{align\*} R &\to (L \mid \operatorname{num}) (+ R)^\* \end{align\*}$

Thus the grammar with left recursion fixed is:

$\begin{align\*} S &\to L = R \\ L &\to * L \mid \operatorname{id} \\ R &\to L R' \mid \operatorname{num} R' \\ R' &\to + R R' \mid \varepsilon \end{align\*}$

You can check that this doesn't have conflicts.
> 0 votes

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time?
Goldbach's Conjecture says every even integer $\>$ $2$ can be expressed as the sum of two primes.

Let's say $N$ is our input and its $10$. Which is an integer \> 2 and is not odd.

## Algorithm

1.Create list of numbers from $1,to~N$

2.Use prime-testing algorithm for creating a second list of prime numbers

3.Use my 2\_sum solver that allows you to use primes twice that sum up to $N$

```
for j in range(list-of-primes)):
  if N-(list-of-primes[j]) in list-of-primes:
   print('yes')
   break

```

4.Verify solution efficently

```
if AKS-primality(N-(list-of-primes[j])):
    if AKS-primality(list-of-primes[j]):
        print('Solution is correct')

```

5.Output

```
yes 7 + 3
Solution is correct

```

## Question

If the conjecture is true, then the answer will always be Yes. Does that mean it can't be in $Co-NP$ because the answer is always Yes?

# Answer
I think you might be confusing a couple of things.

First, the complement of any problem in NP is in CoNP by definition. No further conditions are required. Second, admitting a polynomial time algorithm to verify solutions, and belonging to the class NP, are equivalent statements.

Third, Goldbach's conjecture is a mathematical statement, which under standard axioms is either true or false. That means that as a decision problem, in the same fashion that any other mathematical statement, Goldbach's conjecture has a constant time solution: machine A answers "true", machine B answers "false". Necessarily one of them is right, and they both take constant time. Obviously this is not helpful at all.

So you probably meant to ask about the problem that given an even integer N \> 2 asks you to decide whether it can be expressed as the sum of two primes. This problem is indeed in NP as you said, because if N = p + q for primes p, q. Then $\left\<p,q\right\>$ is a solution that can be verified in polynomial time, by using the poly-time algorithm to first check that p and q are indeed primes, and then any addition algorithm. I don't know if there is a polynomial time algorithm for this problem, but I wouldn't be surprised if there is one.

If Goldbach's conjecture is true, then the machine that answers "yes" without even looking at the input accepts the language described above and runs in constant time.
> 2 votes

---
Tags: number-theory, co-np
---


# Question
Title: How can I improve my algorithm for finding optimally balanced P-way partitioning of array
I have an array of $N$ weights $w\_i$, say $w\_i=\\{4, 5, 12, 16, 3, 10, 1\\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of weights of any partition is as small as possible. Luckily the problem is constrained by the fact that the weights can't be reordered. If the number of partitions is three, the above example would give the optimal partitions: $\\{4, 5, 12\\}, \\{16\\}, \\{3, 10, 1\\}$.

I have found efficient recipes (e.g. partition problem, subset sum, Optimal Partition of Book Chapters, A partition algorithm, An algorithm for k-way array partitioning) for many similar problems for the cases where the weights are unordered sets and/or the number of partitions is fixed at 2 or 3, but none that seem to exactly address my problem where the number of partitions is arbitrary.

I have solved the problem myself using divide-and-conquer algorithm (written in Python below), but it seems to be awfully slow for many partitions (e.g. N=100, P=8). So I was thinking that there got to be a better way, using dynamic programming or some other clever tricks?

Does anyone have any suggestions?

Slow Python divide-and-conquer algorithm:

```
def findOptimalPartitions(weights, num_partitions):
    if num_partitions == 1:
        # If there is only one partition, it must start at the first index
        # and have a size equal to the sum of all weights.
        return numpy.array([0], dtype=int), sum(weights)

    # Initially we let all partitions start at zero, meaning that all but the
    # last partition gets zero elements, and the last gets them all.
    partition_offsets = numpy.array([0] * num_partitions)
    max_partition_size = sum(weights)

    # We now divide the weigths into two partitions that split at index n.
    # We know that each partition should have at least one element, so there
    # is no point in looping over all elements.
    for n in range(1, len(weights) - num_partitions):
        first_partition_size = sum(weights[:n])

        if first_partition_size > max_partition_size:
            # If the first partition size is larger than the best currently
            # found, there is no point in searching further.
            break

        # The second partition that starts at n we now further split into
        # subpartitions in a recursive manner.
        subpartition_offsets, best_subpartition_size = \
            findOptimalPartitions(weights[n:], num_partitions - 1)

        # If the maximum size of any of the current partitions is smaller
        # than the current best partitioning, we update the best partitions.
        if ((first_partition_size < max_partition_size)
                and (best_subpartition_size < max_partition_size)):
            # The first partition always start at 0. The others start at
            # ones from the subpartition relative to the current index, so
            # add the current index to those.
            partition_offsets[1:] = n + subpartition_offsets
            # Find the maximum partition size.
            max_partition_size = max(first_partition_size, best_subpartition_size)

    return partition_offsets, max_partition_size

```

EDIT: A trivial Greedy algorithm where the last partition will typically be too large.

```
def greedyPartition(weights, num_partitions):
    target_size = sum(weights) / num_partitions

    partition_offsets = numpy.zeros(num_partitions, dtype=int)
    partition_sizes = numpy.zeros(num_partitions, dtype=int)
    current_divider = 0
    for p in range(0, num_partitions - 1):
        partition_size = 0
        for n in range(current_divider, len(weights)):
            if partition_size + weights[n] > target_size:
                current_divider = n
                partition_offsets[p + 1] = current_divider
                partition_sizes[p] = partition_size
                break

            partition_size += weights[n]
    partition_sizes[-1] = sum(weights) - sum(partition_sizes[:-1])
    max_partition_size = max(partition_sizes)

    return partition_offsets, max_partition_size

```

# Answer
Binary search is a general strategy that can often be applied to problems that seeks a single optimized number as an answer.

---

Let $A=\[a\_1, \cdots, a\_N\]$ be the given array of weights. Assume $1\lt P\lt N$; otherwise, the problem becomes trivial.

Given a weight $w$ such that $1\le w\le\sum a\_i$, we can associate a partition $\mathcal P(w)$, $A = P\_1\\,P\_2\\,\cdots P\_m$ such that

1. Subarray $P\_1$ is as long as possible such that the sum of all weights in it is no more than $w$.
2. Then subarray $P\_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
3. Then subarray $P\_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
4. And so on.
5. Finally, we are left with non-empty subarray $P\_m$, the sum of all weights in which is no more than $w$.

Note that $m=\\#\mathcal P(w)$ is the minimum number of subarrays in a partition where the sum of all weights in every subarray is at most $w$. We want to find $w$ such that $\\#\mathcal P(w)=P$ and $\\#\mathcal P(w+1)\<P$. Since the map from $w$ to $\mathcal P(w)$ is decreasing, we can use binary search to find it.

Here is the outline of an algorithm that finds the largest $w$ such that $\mathcal P(w)=P$. Assume the given weights are integers; otherwise, we need to tweak the algorithm a bit. .

1. Let $ma=\max\\{a\_i\\}$. If $P\ge \\#\mathcal P(ma)$, the least maximum sum is $ma$. Deal with this easy case and return.
2. Let $low=ma$ and $high=\sum a\_i$.
3. If $low\lt high-1$, $ mid = (low + high)//2$ and compute $m= \\#\mathcal P(mid)$.

* If $m\le P$, lower $high$ to $mid$.
    * If $m\gt P$, raise $low$ to $mid$.

Go back to the start of this step.
4. Let $H$ be the partition $\mathcal P(high)$. If $\\#H\not= P$, divide some subarrays of $H$ into smaller subarrays so as to increase the number of subarrays by $P-\\#(P)$. Return $H$.

The loop invariant for step 3 is $\\#\mathcal P(low)\>P$, $\\#\mathcal P(high)\le P$ and $low\le high-1$. When the loop ends, i.e., when $low==high-1$, we must still have $\\#\mathcal P(low)\>P$ and $\\#\mathcal P(high)\le P$. That means, $high$ is the minimum of the maximum sum of weights of any subarray in a partition of size no more than $P$, which explains largely why this algorithm is correct.

---

This algorithm runs in $O(N\log(\sum a\_i))$ time, since the most of time is spent on computing $\mathcal P(w)$ and it takes $O(N)$ time to compute $\mathcal P(w)$ for any given weight $w$.

---

**Exercise (the dual problem)**. Given an array of $N$ positive integer weights $w\_i$ and an integer $P$, divide the array into $P$ parts such that the parts are optimally balanced, i.e. that *minimum* sum of weights of any part is as *large* as possible.
> 0 votes

---
Tags: algorithms, partitions
---


title: Context free grammar for $A \circ B$

text:
# Question
Title: Context free grammar for $A \circ B$
If A and B are regular language, what is a context free grammar of the following language? $$ A \circ B = \\{ xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y| \\} $$

# Answer
> 1 votes
For simplicity, we can assume that neither $A$ or $B$ contains the empty string. Otherwise, we can either add a simple rule to our final grammar so that it generates the empty string or or do nothing so that our final grammar does not generate the empty string still.

Since $A$ is a regular language that does not contain empty string, we can have $(N\_A,\Sigma\_A, P\_A, S\_A)$, a *restricted right-linear* grammar for $A$, where each rule in $P\_A$ is of the form $U\to aX$ or $U\to a$, where $U, X\in N\_A$ and $a\in\Sigma\_A$.

Since $B$ is a regular language that does not contain empty string, we can have $(N\_B,\Sigma\_B, P\_B, S\_B)$, a *restricted left-linear* grammar for $B$, where each rule in $P\_B$ is of the form $V\to Yb$ or $V\to b$, where $V,Y\in N\_B$ and $b\in\Sigma\_B$.

Construct the grammar $\left(N\_A\times N\_B, \Sigma\_A\cup\Sigma\_B, P, (S\_A,S\_B)\right)$, where the production rules $P$ is $$\\{(U,V)\to a(X,Y)b: U\to aX \in P\_A\ \land\ V\to Yb \in P\_B\\}\\ \cup\\{(U,V)\to ab: U\to a\in P\_A\ \land\ V\to b \in P\_B\\}.$$

Basically, the grammar rules generate a string by adding a terminal on the left side as in $A$ (I am referring to $U\to aX$) as well as a terminal on the right side as in $B$ (I am referring to $V\to Yb$) at the same time. At the final step, the non-terminal in the middle is replaced by $ab$ (I am referring to $(U,V)\to ab$).

It should not be difficult to verify the constructed grammar is a context-free grammar for $A\circ B$. (In fact, it is a linear grammar.)

# Answer
> 2 votes
Suppose that DFA for $A$ and $B$ are $D\_A$ and $D\_B$ respectively. We will construct a PushDown Automata (PDA) for the given language $A \cdot B$ by combining $D\_A$ and $D\_B$ in a particular manner.

Modify the transitions of $D\_A$ such that on reading any letter it pushes a symbol $X$ on the stack. Join all the final states of $D\_A$ to the initial state of $D\_B$ with epsilon transitions. Modify all the transitions of $D\_B$ to Pop $X$ from the stack. **Accepting condition will be that on reading a word we should reach one of the final state of $D\_B$ and the stack should be empty.**

It will be quite easy for you to convince yourself that this will accept the language $A \cdot B$ as required. Now, we can apply the standard method to convert the PDA to grammar to get the required grammar.

---
Tags: context-free
---


# Question
Title: Scheduling of process manufacturing with setup times
# Overview

The process manufacturing is (in contrast to discrete manufacturing) focused on the production of continuous goods such as oil. The planning is typically solvable by means of Linear Programming, come constraints can be introduced for MILP.

# Problem Formulation

The problem consists of

* Sequence of consecutive time intervals $t\in\\{1,\dots,n\_t\\}$, each with start and end $(s\_t,e\_t)$ and length $l\_t=e\_t-s\_t$. Consecutive means $e\_{t}=s\_{t+1}$ for all $t\in\\{1,\dots,n\_t-1\\}$.
* List of type of goods that are being produced: $j\in \\{1,...,n\_j\\}$
* Demand of each type of good per time interval $d\_{j,t}$.
* List of production lines $i\in{1,\dots,n\_i}$
* Availability of production lines per time interval $a\_{i,t}$. $a\_{i,t}$ is binary - whether available or not.
* Manufacturing speed per production line per type goods $v\_{i,j}$.
* Setup time from one type of goods to another one $u\_{j,j'}$.
* Price for using a production line (leasing based), counted per minute $c\_{i}$

The goal is to plan the production lines so the demand is covered and the price for leasing is minimal.

Notes:

* The setup time can be shorter or longer or equal to the length of the intervals
* It is acceptable that the production line will not work the whole time interval if the supply has been completed sooner
* The setup to the production of another good can start any time, not necessarily at the beginning of an interval.

# Example

There are two production lines, i.e., $n\_i = 2$ and there are two types of goods, i.e. $n\_j=2$.

We have two intervals, i.e. $n\_t=2$, each has a leght of 1 hour. Say one starts at 1 pm, the second at 2 pm.

The demand is:

* $d\_{1,1}=1.1$
* $d\_{1,2}=1$
* $d\_{2,1}=1$
* $d\_{2,2}=0.5$

The of running the production lines are:

* $c\_{1} =c\_{2} = 1$ USD/minute

All possible setup times are 30 minutes, i.e.:

* $u\_{j,j'}=0.5$ for all $j,j'$ where $j\neq j'$.

The speeds are:

* $v\_{1,1}=1.1$
* $v\_{1,2}=1.5$
* $v\_{2,1}=1$
* $v\_{2,2}=1$

Obviously, the demand is met if the first line is producing the first type of goods at both intervals and the second line is producing the second type. The cost is 204.55. See the solution here:

However, it might be tempting to switch them. Line 1 is much more efficient for the second type of goods (1.5). If there would be no setup time, we would have the cost 180 USD. However, this is not possible.

# Question

*What is the algorithm to schedule this manufacturing process optimally?*

An answer is welcome even if it would outline the way and approach (MILP, SAT, CSP,...).

# Ideas fo far

* If the length of intervals would be fixed, say 1 hour and the setup time would be defined in terms of these units, say 2 hours. Then, it might be solvable by SAT/CSP.
* An idea is to use an evolutionary algorithm that would: consist of a sequence of activities with mutations (add an activity, delete activity, prolong activity) and crossover (mix two plans in a random way).

# Answer
> 1 votes
We use the index $k$ for time such that $k \in \[s\_1, e\_{n\_t}\]$

We introduce the following variables:

$\ell^{i,k}$ \- line $i$ is leased at line $k$

$\alpha^{i,k}\_{j,j'}$ \- binary indicator for line $i$ is switching from $j$ to $j'$ at time $k$.

$p^{i,k}\_j$ \- binary indicator for line $i$ is producing good $j$ at time $k$.

$h^{i,j}\_j$ \- binary indicator that line $i$ is waiting to produce good $j$ at time $k$

$g^{i,k}\_j$ \- generated amount for line $i$ for good $j$ at time $k$ (either $v\_{i,j}$ or $0$)

Then goal is to minimize $\sum\_{i,k} c\_i \ell^{i,k}$ subject to constraints:

Constraints for every $i,k$:

* can only switch to 1 good at a time: $\textrm{at-most-1} \alpha^{i,k}\_{j,j'}$
* can only make 1 good at a time: $\textrm{at-most-1} p^{i,k}\_j$
* can only hold for 1 good at a time: $\textrm{at-most-1} h^{i,k}\_j$
* if producing, not switching: $\bigvee\_j p^{i,k}\_j \rightarrow \neg \bigwedge\_{j,j'} \alpha^{i,k}\_{j,j'}$
* leasing iff producing or switching: $\ell^{i,k} \leftrightarrow \bigvee\_{j,j'} \alpha^{i,k}\_{j,j'} \vee \bigvee\_j p^{i,k}\_j$
* not leasing implies holding for some good: $ \neg \ell^{i,k} \Rightarrow \bigvee\_j h^{i,k}\_j$

Constaints for every $i,k,j$:

* Generating only if producing: $$p^{i,k}\_j \rightarrow g^{i,k}\_j = v\_{i,j}$$ $$\neg p^{i,k}\_j \rightarrow g^{i,k}\_j = 0$$
* when stopping producing, it must immediately hold for same good or switch to another good (for $k \< e\_{n\_t}$): $p^{i,k}\_j \wedge \neg p^{i,k+1}\_j \Rightarrow h^{i,k+1}\_j \vee \bigvee\_{j'} \alpha^{i,k+1}\_{j,j'}$
* if producing or holding at $k+1$ must have been producing, holding, or switching at $k \< e\_{n\_t}$: $p^{i,k+1}\_j \vee h^{i,k+1}\_j \Rightarrow p^{i,k}\_j \vee h^{i,k}\_j \vee \bigvee\_{j'} \alpha^{i,k}\_{j',j}$

Constraints for every $i,k \< e\_{n\_t},j,j'$:

* when switching, it must switch long enough: $(p^{i,k}\_j \vee h^{i,k}\_j) \wedge \alpha^{i,k+1}\_{j,j'} \Rightarrow \bigwedge\_{k'=k+2}^{\min(k+u\_{j,j'}, e\_{n,t})} \alpha^{i,k'}\_{j,j'}$

Constraints for every $d\_{j,t}$:

* $\sum\_{k=s\_t}^{e\_t} \sum\_i g^{i,k}\_j \geq d\_{j,t}$

---
Tags: optimization, process-scheduling, planning
---


# Question
Title: Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials
Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form finite trees, with numbers as leaf nodes and operators as internal nodes, binary operations having two child sub-expressions and the functions one. A value of such an expression is interpreted to mean some number in $\mathbb R$.

There are two limitations on the structure of the expressions: the divisor (the right-hand sub-expression) of $/$ can't be 0 and the argument of $\ln$ must be positive.

I have two questions about these kind of expressions:

* Is it possible to ensure "soundness" of such an expression, in the sense that the two limitations can be checked in finite time?
* is an equality check between two such expressions decidable?

These questions seem to be connected in the sense that if you're able to check equality of the relevant sub-expression to zero, you can decide whether a division parent expression is sound, and it doesn't seem hard to check whether a sub-expression of $\ln$ is positive or negative if it's known not to be zero.

I know that equality in $\mathbb R$ is generally not decidable, whereas equality in algebraic numbers is. However, I wonder how inclusion of {$\exp, \ln$} changes the result. I suspect that if there exists "pathological cases" where two expressions with dramatically different structure result to the same real number, checking the equality between them might be undecidable, as the $\exp$ and $\ln$ might hinder the normalization of such expressions.

(A side note: I posted an earlier version of a question with similar intent here, but it turned out to have too little thought behind it, and had unnecessary (= not related to the meat of the question) complications with complex logarithms.)

# Answer
I don't know, but I suspect it's an open question.

If the theory of the reals with exponential function is decidable, then your problem is decidable, too. It is known that if Shanuel's Conjecture holds, then the former is decidable, so your problem is too.

If I understand correctly, the following paper tackles your problem:

The identity problem for elementary functions and constants. Dan Richardson, John Fitch. ISSAC '94.

It appears that they show a procedure that always terminates if Shanuel's Conjecture holds; and if it doesn't terminate for a particular expression, then we can extract from that expression a counterexample to Shanuel's Conjecture. They then argue that it seems unlikely that we will find a counterexample any time soon, so it seems unlikely we will find inputs on which this procedure fails to terminate any time soon.

See also https://mathoverflow.net/q/118972/37212 and https://mathoverflow.net/q/129563/37212 and https://mathoverflow.net/q/145299/37212.
> 3 votes

---
Tags: computability, undecidability, number-theory, equality
---


# Question
Title: P=NP when number of inputs that give 1 is bounded by polynomial
Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \\{0, 1 \\}^\* \to \\{0, 1\\}$, then, for every $n$, $|\\{ x \in \\{0, 1 \\}^n : f(x) = 1\\}| \leq p(n)$ for some polynomial $p$. Then, I want to show that the existence of this problem implies $\mathsf{P} = \mathsf{NP}$. Is it somehow related to LEXSAT?

# Answer
The result you are trying to prove is known as Mahaney's theorem. It is covered by textbooks on complexity theory, and in many online lecture notes.

The proof in Jonathan Katz' lecture notes indeed uses LEXSAT.
> 4 votes

---
Tags: np-complete, np, satisfiability, p-vs-np
---


# Question
Title: Where does the base come from in a subsequence count?
If sequence `X` has `m` symbols, then `X` has 2m possible subsequences.

Where does the base (`2`) come from?

The origin of this question is the following paragraph:

> We are given two ordered sequences of symbols, and we wish to find a longest common subsequence of $X$ and $Y$.
>
> A subsequence of $X$ is just $X$ with some (or possibly all or none) of its elements removed. For example, one subsequence of `A; B; C; D; E; F; G` would be `B; C; E; G`.
>
> The length of a longest common subsequence of $X$ and $Y$ gives one measure of how similar these two sequences are. For example, if the two sequences are base pairs in DNA strands, then we might consider them similar if they have a long common subsequence.
>
> If $X$ has $m$ symbols and $Y$ has $n$ symbols, then $X$ and $Y$ have $2^m$ and $2^n$ possible subsequences respectively.

# Answer
> 1 votes
You can think of a subsequence $Y$ of $X$ as a characteristic vector $\chi\_Y$ that has $m$ elements, one per element of $X$. The $i$-th element of $\chi\_Y$ is $1$ if the $i$-th element of $X$ is also in $Y$ and $0$ otherwise.

It is easy to see that this is a bijection: every subsequence $Y$ has a distinct characteristic vector $\chi\_Y$, and every characteristic vector $\chi\_Y$ is associated to a distinct sequence $Y$.

This means that the number of subsequences $Y$ is equal to the number of vectors $\chi\_Y$. Since each vector $\chi\_Y$ has $m$ elements, each of which can have one of $2$ possible values, this number is $2^m$.

A concrete example of a sequence $X$, a subsequence $Y$, and its characteristic vector $\chi\_Y$ is the following:

---
Tags: algorithms, mathematical-foundations
---


# Question
Title: Show that the best case time complexity of Quicksort is $\Omega(n \log n)$
I am trying to show that the *best case* time complexity of Quicksort is $\Omega(n \log n)$.

The following recurrence describes the best-case time complexity of Quicksort:

$$T(n) = \min\_{0 \le q \le n-1} \left(T(q) + T(n-q-1) \right) + \Theta(n).$$

But I have difficulty in proving that $T(n) = \Omega(n \log n)$ using the recurrence above.

So how to solve this recurrence?

# Answer
Let us replace $\Theta(n)$ with $n$, for concreteness, and assume a base case of $T(0) = 0$. Let's try to prove inductively that $T(n) \geq cf(n)$, where $f(n) = n\log n$ for all $n$ (where $0\log 0 = 0$).

During the proof, we will need to minimize $f(q) + f(m-q)$ for $0 \leq q \leq m$. Since $f'(n) = \log n + 1$, any minimum point must satisfy $$ \log q + 1 = \log (m-q) + 1, $$ that is, $q = m/2$. Since $2f(m/2) = m\log(m/2)$ whereas $f(0) + f(m) = m\log m$, we see that $q = m/2$ is indeed a minimum.

We are now ready to prove inductively that $T(n) \geq cf(n)$. The base case is obvious. For the inductive step, note that for each $q \in \\{0,\ldots,n-1\\}$, $$ T(q) + T(n-1-q) \geq c(f(q) + f(n-1-q)) \geq c(n-1) \log((n-1)/2). $$ Therefore to complete the proof, we need to show that $$ c(n-1) \log \frac{n-1}{2} + n \geq cn\log n. $$ This holds trivially for $n=1$, and holds for all $n \geq 2$ when $c = 1/\log 3$.

Altogether, this shows that $T(n) \geq n\log\_3 n$.
> 2 votes

# Answer
You can use the recursion tree method.

The amount of work on the level at depth $0$ is at least $c n$ for some constant $c$ (from the $\Theta(\cdot)$ notation). The amount of work at depth $1$ is at least $c q + c (n-q -1) = c(n-1)$. The amount of work on the next level is at least $c(n-3)$ and, in general, the total amount of work on the level at depth $d$ is at least $c(n - 2^d - 1)$. You can prove this by induction on $d$.

The number of levels with non-zero amount of work must be at least $1+\log(n-2)$, therefore the total time complexity must be at least $\sum\_{d=0}^{\log(n) /2} c(n - 2^d - 1) \ge c \sum\_{d=0}^{\log(n) /2} (n-\sqrt{n}-1) = c \sum\_{d=0}^{\log(n) /2} \Omega(n) = \Omega(n \log n)$.
> 1 votes

---
Tags: time-complexity, asymptotics, quicksort
---


title: Find the power of 2

text:
# Question
Title: Find the power of 2
Assume $n=2^k$, write an algorithm that can find $k$.

\**log function is not allowed.

Is there an efficient way to find the power instead of multiplying by 2 until it equals $n$? What is the optimal efficiency?

# Answer
Assuming arithmetic operations take constant time, you can compute it in $O(\log \log n)$ time.

Start with $n\_0=2$ and iteratively compute $n\_i = n\_{i-1} \cdot n\_{i-1} = 2^{2^i}$ until $n\_{i} \> n$.

The number of iterations is then $\log \log n$ and $ n\_{i-1} = 2^{2^{i-1}} \le n \< 2^{2^i} = n\_i$. At this point you can binary search for the right exponent among the $2^i - 2^{i-1} = 2^{i-1} \le k$ possible exponents. This takes time $O(\log k) = O(\log \log n)$ (exponentiation with a base of $2$ can usually be performed with a single left shift operation).
> 6 votes

---
Tags: algorithms
---


# Question
Title: Minimization of automata with dead state
I am supposed to minimize the following DFA automa, which contains dead state:

But after the minimization of the automata, it stayed the same.

Is it correct?

# Answer
> 0 votes
I didn't try to minimize your particular automaton but it is definitely possible for a minimal DFA to have a dead state. Keep in mind that often such states are omitted from the graphical representation of the automaton (nevertheless they are still part of the set of states of the DFA).

Think, for example, of a minimal DFA that recognizes $L=\\{a\\}$ over the alphabet $\Sigma = \\{a, b\\}$.

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


title: Turning a regular expression into a DFA

text:
# Question
Title: Turning a regular expression into a DFA
i'm studying for an exam i'll have soon and i don't understand how to draw a DFA for a regular expression, i asked my professor by mail but he doesn't asnwer... In the courses available on my college's website there is no step by step exemple Here is the expression i'm trying to convert b(a∗dc)∗

Thank you for the help !

edit i've done this but i'm not sure:

# Answer
Recursively break down your regular expression into elementary sub-expressions.

In you case you can write your expression $E=b(a^\*dc)^\*$ as the concatenation of $b$ with $(a^\*dc)^\*$. In turn $(a^\*dc)^\*$ is the Kleene closure of $a^\*dc$ which can be broken down as $a^\*$ and $dc$. Finally $a^\*$ is the Kleene closure of $a$.

You can construct your NFA from bottom up: Design a DFA for $a$ (which is trivial).

Now transform it into a NFA for $a^\*$ (add an $\epsilon$-transition from the final state to the initial state $x$, then add a new initial state $x'$ and add an $\epsilon$-transition from $x'$ to $x$).

Design a DFA for dc (also trivial).

Concatenate the NFA for $a^\*$ with the DFA for $dc$ to obtain a NFA for $a^\*dc$.

Transform the NFA for $a^\*dc$ into a NFA for $(a^\*dc)^\*$.

Design a DFA for $b$ (again, trivial).

Concatenate the DFA for $b$ with the NFA for $a^\*dc$ to obtain a NFA for $b(a^\*dc)^\*$.

Transform the resulting NFA to a DFA using standard techniques.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Solving a multivariate equation for asymptotic complexity
I have a function $f(m, n)$ with time complexity $T(m, n)$ characterized by the recurrence relation

$$\begin{align} T(m,\ n) &= 2T\bigl(\frac{m}{2}, \frac{n}{2}\bigr) + c\_0 \log n + c\_1.\\ T(m,\ 1) &= T\bigl(\frac{m}{2}, 1 \bigr) + c\_1 \\ T(0,\ n) &= 1 \\ T(m,\ 0) &= 1 \end{align}$$

I can see that for fixed $m$, this is $O(n)$, and for fixed $n$, this is $O(m)$. But I don't see how I can get an expression that characterizes the performance in terms of variable $m$ and $n$.

How can I solve this to find the asymptotic complexity in terms of $m$ and $n$?

# Answer
> 3 votes
Suppose for simplicity that $m=2^a$, $n = 2^b$, $c\_0=1$, $c\_1=0$, and the base cases are $T(1,\cdot) = T(\cdot,1) = 0$. Then $$ T(2^a,2^b) = 2T(2^{a-1},2^{b-1}) + b = 4T(2^{a-2},2^{b-2}) + b + 2(b-1) = \cdots $$ The number of summands is $c = \min(a,b)$, and using this notation we obtain \begin{align} T(2^a,2^b) &= b + 2(b-1) + 4(b-2) + \cdots + 2^{c-1}(b-c+1) \\ &= (1+2+\cdots+2^{c-1})b - 2^1 (1) - 2^2 (2) - \cdots - 2^{c-1} (c-1) \\ &= (2^c-1)b - 2^c c + 2(2^c-1) \\ &= 2^c(b+2-c) - (b + 2). \end{align} In other words, $$ T(2^a,2^b) = \begin{cases} 2^{b+1} - (b+2) & \text{if } a \geq b, \\ (b+2)(2^a-1) - a2^a & \text{if } b \geq a. \end{cases} $$ When $m \geq n$, this gives $T(m,n) = \Theta(n)$, and when $n \> m$, we get $T(m,n) = \Theta(m\log (n/m)+m)$.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?
I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric.

An obvious approach is to make all $\frac{n^2-n}{2}$ comparisons among the $n$ vertices, giving us $O(n^2)$ time complexity.

Excluding parallelizing the comparisons, is there a better algorithm in terms of time complexity?

I'm interested in string metrics where strings of different length are allowed.

# Answer
> 3 votes
In the worst case any such algorithm will work $\Omega(n^2)$ because your graph can have $\Omega(n^2)$ edges.

By the way, are you interested in some particular string metric?

# Answer
> 0 votes
It's possible to use BK-Trees to speed this up. Inserting $n$ elements into the tree takes $O(n \log n)$ time. After this you can query the tree for all strings whose edit distance is exactly one away from your input. Doing this for all strings again takes $O(n^2)$ complexity, however with a very small constant factor (this page mentions only 5-8% of the tree needs to be inspected per query).

Here's a short description of how it works:

### Data structure

A BK-Tree is either

* Empty
* A node with a root value $r$ and a set of indexed children $c\_i$, each a BK-Tree (implemented using hash map, dynamic array, or similar)

A metric (important!) distance function $d(x,y)$ is used for insertion and queries.

### Inserting string $s$

* If the tree is empty, make it a new node with $s$ as the root value and no children
* If the tree is a node with root $r$ and children $c\_i$, let $k=d(r,s)$.
    + If $k=0$, skip insertion as $s$ is already at the root
    + Otherwise recursively insert $s$ into the $k$-th child tree $c\_k$.

The last step makes sure that all nodes in $c\_i$ have distance $i$ to the root

### Querying string $s$

* If the tree is empty, return no results
* If the tree is a node with root $r$ and children $c\_i$, let $k=d(r,s)$.
    + If $k=1$, add $r$ as a result (**Note**: This step is different from usual BK-Tree queries)
    + In addition, recursively query $s$ from the children $c\_{d-1}$, $c\_d$ and $c\_{d+1}$. Return all results from those queries as well

The last step there is the magic of BK-Trees, as it doesn't need to check the other children due to the distance being metric. Here's a partial proof of why others don't need to be checked:

Let's assume there was some string $x$ which has distance one from our query, so $d(s, x)=1$, but it's in the child tree $c\_{k+2}$. We know that $d(r, x)=k+2$ from the insertion procedure. This however (with the triangle inequality for metric spaces) gives

$$ k+2=d(r, x)\leq d(r, s)+d(s,x)=k+1 $$

But this is a contradiction! Similar can be done for all children with $i\>k+1$ and $i\<k-1$. This means that all strings in other children won't have distance one by construction, so we don't need to even check them, which saves processing time.

Edit: Another explanation: https://signal-to-noise.xyz/post/bk-tree/

---
Tags: algorithms, graphs, time-complexity, weighted-graphs, string-metrics
---


# Question
Title: If a decision problem is in $P$, must finding the solution be possible in polynomial-time?
Function Problem that finds the solution

* Given integer for $N$.
* Find $2$ integers distinct from $N$. (But, less than $N$)
* That have a product equal to $N$.

This means we must exclude integers $1$ and $N$.

## An algorithm that is pseudo-polynomial

```
N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)

for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

```

## Output

```
Soltuion Verified: 5 x 2 = N and N=10

```

## The algorithm that solves the Decision Problem

```
if AKS-primality(N) == False:
  OUTPUT YES

```

## Question

Since the decision problem is in $P$ must finding a solution also be solvable in polynomial-time?

# Answer
> 2 votes
No, and the example you list is a classic example: as far as we know, factoring does not appear to be in $P$, but determining whether a number is prime is definitely in $P$.

Another example: Consider the game Hex. Consider the decision problem: given $n$, determine whether the first player has a winning strategy for Hex on a $n \times n$ board. There is a corresponding function problem: given $n$, find such a winning strategy. Well, the decision problem is trivial (it is known that the answer is always "yes"), but the function problem is believed to be very hard (as far as we know).

---
Tags: decision-problem
---


# Question
Title: Why should an average programmer learn automata theory?
Good programming relies heavily on choosing an efficient algorithm for the task at hand and yet an average programmer hardly uses 50 pages worth of algorithms from the Cormen book in his/her career.

Recently I started reading some CS books, long after completing my bachelors degree. One of the books is the Theory of Computation by Micheal Sipser. Although I love the content and still am in the beginning chapters, I cannot imagine where I would use the information provided in this book in my job.

What is the use of Automata Theory in the industry?

# Answer
> 2 votes
Automata theory is rarely used by practicing programmers today. It is in principle useful for building compilers and parsers (though most developers don't need to do that today, and often use tools to help them). Some of the concepts can be useful for building state-machine based systems, which are widespread (including, e.g., embedded systems), though it's not clear you need to know all the ideas from automata theory to be successful at that. Also, many people study theory even if there is not a direct practical application.

---
Tags: automata
---


# Question
Title: What is the difference between "use case" and "function"?
In the use case diagram, we draw use cases as an ellipse. Are the use cases the same as functions? I mean by functions, those functions which we write in the program.Thank you in advance.

# Answer
If by "function" you mean functionality then a single use case may require more than one function to achieve and a single function may serve multiple use cases.

Here's a concrete example:

**Use case**:

* Allow user to withdraw money

**Functions**:

* Check user balance
* Prompt user to enter amount and check against balance
* Check amount against money in machine
* Output money

Depending on how you go about documenting your design you can argue that the 4 functions above can be written as a single function. Though doing this misses the important realization that `Check user balance` is a function that can be reused in another use case (`Allow user to see his balance`), even if we reduce them to one function the use case and function would be different ways to say the same thing:

**Use case:**

* Allow user to withdraw money

**Function**:

* Withdraw money

So, at its core level a **functionality** is an implementation of processes for a **use case**.

Why do we need two different names? Sometimes it makes it clearer to talk about a requirement and the solution to it. Similar to how in programming we have **classes** and **objects**.
> 1 votes

# Answer
The word *function* has several meanings. One of them is similar to the meaning of *use case*. Another is *mathematical function*. Yet another is *computer routine*. Wiktionary lists a few more.
> 0 votes

# Answer
From my experience use case is what the code is used for and function is what the code does. For example you may have a subroutine that calculates the length of the minnimal path between two nodes in a graph but a specific use case may be to find the minimal length between two points in a maze (when represented as a graph).
> 0 votes

---
Tags: graphical-models
---


# Question
Title: Maximum number of positive literals in 2SAT
MAX 2SAT is NP complete.

Instead of satisfying the maximum number of clauses, I have a fully satisfiable 2SAT formula and I want to have the maximum number of positive literals in the assignment (such that all the clauses are satisfied, of course).

What is the difficulty of this problem?

# Answer
This problem is NP-hard (and in addition hard to approximate and W\[1\]-hard), because maximum independent set can be reduced to it. Reduction: Each variable represents a vertex and each clause represents an edge.
> 1 votes

---
Tags: np, satisfiability, 2-sat
---


title: Domain of a Type-2 Computable Function

text:
# Question
Title: Domain of a Type-2 Computable Function
In Weihrauch's Type-2 computability theory, a string function $f\colon\subseteq \Sigma^{\omega}\rightarrow \Sigma^{\omega}$ (the $\colon\subseteq$ indicates that $f$ may be a partial function) is computable iff there exists a Type-2 Turing machine that *exactly* realizes $f$, which implies that the Turing machine *must* fail to produce an output on inputs that are not in the domain of $f$.

To extend this to functions between arbitrary domains $D\_1$ and $D\_2$, one specifies *representations* $\gamma\_i\colon\subseteq\Sigma^{\omega}\rightarrow D\_i$, and Weihrauch defines $f\colon\subseteq D\_1\rightarrow D\_2$ to be $(\gamma\_1,\gamma\_2)$-computable iff there exists a Type-2 computable string function $g$ such that $f(\gamma\_1(y)) = \gamma\_2(g(y))$ whenever $f(\gamma\_1(y))$ is defined.

*But $\gamma\_2(g(y))$ is allowed to be defined even when $f(\gamma\_1(y))$ is not*.

*Why is it defined this way?* It seems to me more natural to require $f\circ\gamma\_1 = \gamma\_2\circ g$, i.e. the domain of the realization $g$ must match the domain of $f$. With Weihrauch's definition we have the odd condition that, for a *string* function $f$, the statements "$f$ is Type-2 computable" and "$f$ is $(\mathrm{id},\mathrm{id})$-computable" (where $\mathrm{id}$ is the identity function) *are not equivalent*.

Reference: Weihrauch, K. (2000), *Computable Analysis: An Introduction*, Springer.

# Answer
> 4 votes
### Philosophical answer

The general philosophy in realizability theory (TTE is a special case of it) is that for a program $p$ realizes a map $f : A \to B$ then $p$, it should work correctly on realizers of arguments, i.e., if $r$ realizes $x \in A$ then $p\\,r$ realizes $f(x) \in B$. It is quite unnatural to say anything about "non-realizers", for at least two reasons. First, it would break the categorical structure of the category of representations (exponentials break). Second, from the programming point of view you are asking that a program always produce garbage output when given garbage input. This is an unreasonable request: the behavior should be *unspecified* for garbage input, as a program may in fact be unable to tell that it was given garbage input.

### Technical answer

We are in the realm of realizability theory, of which TTE is a special case. It is important to understand that, when working with representations, there are *two* notions of function:

1. The maps which take realizers to realizers, in the case of TTE these are the maps $\Sigma^\omega \to \Sigma^\omega$. Let us call these *realizers*.
2. The *morphisms* in the category of represented sets, which are maps between sets that are tracked by a realizers. In TTE these are also called $(\gamma\_1, \gamma\_2)$-computable maps, but we shall just call them morphisms.

Standard textbooks on computability theory almost alawys talk about the first notion. The question is asking about the relationship between the first and the second notion.

Typically realizers are not actually functions, but are elements of some model of computation, such as Turing machines (either type I or type II) or the closed terms of $\lambda$-calculus. In the case of Type Two Effectivity this becomes apparent once we try to compute the standard representation for the set of realized maps, because that is when we define what it means for an element of $\Sigma^\omega$ to implement a realizers $\Sigma^\omega \to \Sigma^\omega$.

Morphisms between represented sets are functions (which happen to be tracked by a realizer).

Let us consider the question "Is the restriction of a computable map also computable?" in both senses.

1. *Is the restriction of a realizers (as a map) again a realizer?* The answer is negative, for if $f {:}{\subseteq} \Sigma^\omega \to \Sigma^\omega$ is computed by a Turing machine, one can show that the domain of $f$ is a $G\_\delta$-set. Therefore, if we restrict $f$ to a domain which is not a $G\_\delta$-set there will be no Turing machine that computes the restriction.
2. *Is the restriction of a morphism $f : D\_1 \to D\_2$ again a morpshism?* Here we have to understand "restriction" in the sense of category theory, i.e., a precomposition with a (regular) mono. This amounts to restricting the representation $\gamma\_1 : \Sigma^\omega \to D\_1$ to a subset $D \subseteq D\_1$. We *could* define the realizability model so that restrictions need not be realized, but that would be silly and useless. It is much better to make sure that the resulting category has good properties, because then we can actually do something with it. And so we define the notion of "tracked by a computable map" in the way we do and enjoy the resulting ambient.

# Answer
> 1 votes
Andrej's answer raises some excellent points. I think we can gain some additional insight by looking at why we demand the computable partial functions come with their natural domain in classical computability theory.

One benefit we get from this is that in Type-1 computability a string function computation can only provide garbage in a very limited way: It either halts and provides an output, or it does not halt. Requiring that halting always indicates a valid input and subsequent valid computation means that we can trust any output we see. Already for a Type-2 computation on infinite sequences, invalid output can be more complicated, as we can see some finite prefix of an input before the computation stalls (the natural domain of a Type-1 computation is $\Sigma^0\_1$, that of a Type-2 computation is $\Pi^0\_2$). As soon as we move to more complicated represented spaces, garbage outputs can be arbitrarily hard to detect - so there is no gain in information coming from a requirement that garbage input must yield garbage output.

A second reason that we do want the set of computable partial functions to be countable, and in fact, want to have a standard enumeration of it. This motivation carries over to Type-2 computable partial functions of type $\Sigma^\omega \to \Sigma^\omega$, which we use as realizers. However, we (almost) never care about the set of partial computable functions from one represented space to another. We either speak about the set/space of computable total functions (which is countable without any garbage-in/garbage-out requirements, and in fact better behaved without); or we say that an individual partial function is computable. So this reason does not apply here, either.

---
Tags: computability
---


# Question
Title: Is $P$ defined for TM which decide or accept a language?
Sipser defines $TIME(t(n))$ as the set of all languages that are decidable by an $O(t(n))$ time TM and then $P = \bigcup\_k TIME(n^k).$

However I see also many definitions like $$ P = \\{ L \mid \text{There is a polynomial } p(n) \text{ and a TM which accepts each string } w\in L \text{ in max. } O(p(n)) \text{ steps.} \\} $$

The first definition by Sipser requires a TM which **decides** the language and the second definition requires only a TM which **accepts** the language.

Which definition is more common? Is there a theorem which relates both?

# Answer
> 2 votes
Both definitions are the same. They just use a different wording. The difference between "decide" and "accept" is commonplace in computability theory, but in complexity theory different terminology is typically used, since we usually deal with machines that always halt.

The class $\mathsf{P}$ consists of all languages $L$ for which there exists a Turing machine $T$ such that:

* $T$ runs in polynomial time. This means that there is a polynomial $p(n)$ such that $T(x)$ stops within $p(|x|)$ steps, where $|x|$ is the length of $x$.
* If $x \in L$, then $T$ accepts $x$.
* If $x \notin L$, then $T$ rejects $x$.

---

Suppose we have a machine $T$ with a different guarantee:

* If $x \in L$, then $T$ halts after $p(|x|)$ steps.
* If $x \notin L$, then $T$ never halts.

The language $L$ is in $\mathsf{P}$, since we can construct a different machine $T'$ which simulates $T$ for $p(|x|)$ steps, accepts the input if $T$ halts, and rejects the input if $T$ doesn't halt. Perhaps that answers your question.

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


# Question
Title: Algorithm for optimal rule-based arrangements?
I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in this table(I have one of each):

```
Num Vegetable     Friends      Foes
1   Watermelon    7,4,3        8,6
2   Tomatoes      9,8,6,5,1    7
3   Sunflowers    7,6,11
4   Zucchini      9,7,3
5   Eggplant      9,6,2        7,10
6   Cucumbers     9,7,3        8,1
7   Corn          8,6,4,3,1    5,2
8   Cantaloup     7,4,3        6,1
9   Bell peppers  6,5,11,10,2
10  Swiss chard   2            5
11  Rhubarb       9,3

```

How do I find the arrangement? Sort them using an algorithm? The title was my best guess at the answer. I am trying to understand the thought process and the implementation.

# Answer
> 2 votes
As @Steven wrote, this problem is NP-hard. However that doesn't mean that you can't solve the problem for small instances.

You can solve such a problem by simply iterating over all $n!$ different permutations, and checking each if any of the arrangements is allowed and how good it is. This has complexity $O(n \cdot n!)$.

Much faster (but still exponential complexity) will be a variation to the Bellman–Held–Karp algorithm. Compute for each pair $(V, v)$ with $V$ being a subset of all vegetables and and $v \in V$, if it is possible to arrange the vegetables $V$ in a way such that $v$ is the last one and what it's best value is. You can define a recursive formula for this function, and apply dynamic programming, like in the BHK algorithm. That should run in $O(n^2 \cdot 2^n)$.

# Answer
> 1 votes
Even just determining if your problem admits a feasible solution is NP-hard.

Let $G = (V,E)$ be a graph. For each vertex $u$ create a vegetable that has no friends and has all vegetables corresponding to vertices in $\\{v : (u,v) \not\in E\\}$ as foes.

There is a way to plant all vegetables in a row with no adjacent foes if and only if there is a simple path of length $|V|$ in $G$, that is, if and only if there is an Hamiltonian path in $G$ .

---
Tags: algorithms, optimization, search-algorithms, heuristics, constraint-satisfaction
---


# Question
Title: Decidability of Turing machines that never move their heads past any input string
> $L\_1 = \\{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \\}$
> $L\_2 = \\{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} \\}$

Consider the two languages above. I want to know which ones are decidable.

I know that $L\_1$ is decidable, because $M$ has only a finite amount of possible configurations with the input string $w$, so we can create a Turing Machine (TM) for to check 1 step past the number of combinations and decide.

However, for $L\_2$, can we do that? I feel like $L\_2$ is undecidable, because we can there seems to be no limit to the possible configurations.

# Answer
The halting problem, $\mathsf{HALT}$ reduces to $\overline{L\_2}$.

Given a TM $T$ and input $w$, create a new TM $N$ that on any input of length $n$, simulates $T$ on input $w$ for $n$ steps and then stops except that if $T$ ever halts before $n$ steps, $N$ will move its head to the right forever.

There is a gap in the above reduction. When $N$ simulates $T$ on $w$ for $n$ steps, it may move out of the input when it moves left (we assume that input is put to the right of the origin, the initial position of $N$'s head, inclusively). This gap can be resolved by the classic trick of "translating the tape". When the simulation is about the move to the left of origin, let $N$ translate the current of the tape one cell to the right. Then $N$ goes to the origin, as if it were the cell to the left of the origin. In this way, we will make sure $N$ will never move out of the input string as long as the simulated $T$ on $w$ does not halt. (To enable $N$ to recognize the origin, it should always mark the origin with a "compound" symbol that also tells its original symbol. For example, if the original symbol at the origin is $A$, $N$ should change it to $A\_o$, a symbol that is not $A$ but points to $A$. "Compound" symbols are also used when $N$ translates the content of the tape.)

Since $\mathsf{HALT}$ is not decidable, $\overline{L\_2}$ is not decidable. So, $L\_2$ is not decidable.
> 1 votes

---
Tags: turing-machines, computability, undecidability
---


# Question
Title: Reducing independent set to triangle-free subgraph
The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$.

An instance of the TFS (triangle-free-set) problem takes in a graph $G$ and an integer $k$ and it returns true iff $G$ has a subset of size $k$ whose induced subgraph is triangle free.

I want to perform a polynomial-time reduction of IS to an instance of triangle-free-set. So I start off with an instance of INDEPENDENT-SET, and I want to reduce it to an instance of TFS. But I'm not quite sure how to do this. I tried many things, like adding additional vertices for each pair of vertices, but I don't think this is right. I also saw a similar question here: NP Complete Proof - Polynomial Reduction, but I cannot quite figure out the approach from just that one person's question.

I would greatly appreciate any help.

# Answer
Let $\langle G=(V, E), k \rangle$ be an instance of Independent Set, and call $n=|V|$. Let $N$ be a set of $n+1$ new vertices (not in $V$), and construct a new graph $G' = (V', E')$ where $V' = V \cup N$ and $E' = E \cup (N \times V)$.

**If $G$ has an Independent Set $S$ of size at least at least $k$ then $G'$ has a Triangle-Free set $S'$ of size at least $n+k+1$**.

Select $S' = S \cup N$. To see that the subgraph of $G'$ induced by $S'$ is triangle free consider any triple $(a,b,c)$ of distinct vertices in $S'$. Clearly, if more than one of $a$, $b$, and $c$ is in $N$, the triple cannot induce a triangle since $G'$ has no edges between vertices in $N$. On the other hand, if at least two distinct vertices $u,v \in \\{a, b, c\\}$ are in $S$, then $(u,v) \not \in E$ and hence $(u,v) \not\in E'$.

**If $G$ has a Triangle-Free set $S'$ of size at least $n+k+1$ then $G'$ has an Independent Set $S$ of size at least at least $k$.**

Let $S=S' \setminus N$. Since $|S| \ge n+k+1$ and $|N|=n+1$, the cardinality of $S$ is at least $k$. To see that $S$ is an Independent Set of $G$ notice that $S' \cap N \neq \emptyset$ and let $v \in S' \cap N$. Let $a$ and $b$ be any two distinct vertices in $S$. Since the subgraph of $G'$ induced by $S'$ is triangle free and $\\{(v,a), (v,b) \\} \subseteq E'$, we must have $(a,b) \not\in E' \supseteq E$.
> 4 votes

---
Tags: np-complete, reductions, np-hard, np
---


# Question
Title: Polynomial-time reduction of Primality and 3-SAT
Is 3-SAT $\leq\_{p}$ Primality? And/or is Primality $\leq\_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.

Thank you.

# Answer
For the first question: This is an open problem. If $\mathsf{P} \neq \mathsf{NP}$ then the answer is no: the decision version of 3-SAT is $\mathsf{NP}$-Complete, while Primality is in $\mathsf{P}$, the means that a Karp reduction from 3-SAT to Primality would imply $\mathsf{P}=\mathsf{NP}$.

For the second question: Primality is in $\mathsf{P} \subseteq \mathsf{NP}$, therefore there is a Karp reduction from Primality to any $\mathsf{NP}$-Complete problem, such as 3-SAT.
> 1 votes

---
Tags: np-complete, np-hard, np
---


title: Do you ever "download" a language?

text:
# Question
Title: Do you ever "download" a language?
When one "downloads" a language (say, downloading the `python` file, or doing `apt-get ruby` or something), is it always the compiler/interpreter you are downloading?

In other words, does a "language" ever exist outside of its syntax and behavioral descriptions?

Perhaps standard libraries can be written in the language itself -- but other than that, would it be correct to say that we ever only "download" implementations of the language?

# Answer
> 7 votes
A programming language is a formal language. Most likely its context-free, sometimes context-sensitive, rarely just regular (mostly eso-langs, and some assembly languages). There usually exists a formal grammar somewhere that defines the *syntax* of the language. Sometimes, this grammar isn't even written down explicitly and only exists inside the reference implementation of the parser for the interpreter or compiler of the language.

The other part of a programming language is it semantic definition. What does a syntactically valid program *do*? In case of Java for example, this is defined in the same document that also defines the syntax, the Java Language Specification (JLS). In case of C#, it is defined in as *ISO/IEC 23270 Information technology — C# Language Specification*.

I'll use the abstract of the latter as example:

> This specification describes the form and establishes the interpretation of programs written in the C# programming language. It describes:
>
> * The representation of C# programs;
> * The syntax and constraints of the C# language;
> * The semantic rules for interpreting C# programs;
> * The restrictions and limits imposed by a conforming implementation of C#.

So what *is* a *programming* language? Its mostly a description of its syntax (grammar) and its semantic (what does the program mean).

Now, what do people mean when they "Download \[language\]"?. Well, in case of Java, they mean that they download *a JDK* -- one of the many JDKs that conform to the JLS and the acceptance tests (TCK). The reference *implementation* of Java is the OpenJDK. It contains both a compiler for java (`javac`) and the JVM, on top of which the bytecode produced by the compiler is run. The JDK thus includes tools to both build/compile Java programs as well as run them.

People usually don't mean they downloaded the language specification when saying that they "downloaded \[language\]".

Similarly, when people say they "download python" or "download ruby", what they mean is that they download a vm/interpreter that is able to run that language. In case of ruby, most people will likely just use the official reference implementation you can get at ruby-lang.org. But even for ruby other options exist, like JRuby and Rubinius. JRuby runs ruby programs atop the Java VM (JVM).

I've never heard people say they "downloaded C/C++". Its almost always that they say "gcc" or "CLang" or whatever compiler they use. Similarly, people do not say they "downloaded Javascript" when installing Node.

Suffice to say, saying you "downloaded \[language\]" is almost always imprecise and can lead to confusion, since it is a very colloquial term that can mean very different things for different languages or even people (when I say "download java", do I mean HotSpot? OpenJDK? Coretto? Zulu? Liberica?). Its almost always better to be precise.

# Answer
> 13 votes
A programming language is a *formal language*, informally speaking a collection of words with a well-formed set of specific rules. As such, you can write down the definition of a formal language and thus a programming language on a piece of paper.

Also, if I've written down somehow digitally the definition of a programming language, surely you can represent and download that description. So then you might talk about an interpreter or a compiler for a language. That is not a programming language, that's an interpreter or a compiler. It's a program you might download.

If the question is "does a programming language exist outside of its description", the answer is no with the above definition: a programming language is defined by a formal language.

# Answer
> 7 votes
You download the language's *tools*. If the language can be compiled to a "native" executable, (e.g., like "Rust") then you download the compiler, and probably a run-time support library, and maybe a linker, a debugger, etc. If the language requires an interpreter (e.g., like Ruby) or a "virtual runtime environment" (e.g., like Java) then you download those things.

# Answer
> 2 votes
Any Compiler, Interpreter, Assembler performs the task to encode the programming language into strings of binary instructions that the host system's processor could understand.

No matter what high-level programming language you use, the programs needs to be converted into binary strings specific to the instruction-set of the processor.

So on basis of my understanding of the question.

> When one "downloads" a language (say, downloading the python file, or doing apt-get ruby or something), is it always the compiler/interpreter you are downloading?

yes when we perform `apt install python`, we are installing the binaries of the interpreter.

But is it possible to download or install a language in the system?

Suppose if you could modify the microcode of the processor to implement new instructions. Since it is the foundation on which your processor works, at the lowest level you just downloaded/installed/changed-to a new machine language on your system. Now you could program your processor in the new machine language.

> In other words, does a "language" ever exist outside of its syntax and behavioral descriptions?

I don't completely understand the question. But if there are bugs in the syntax say like the ambiguity of dangling if else then the program might include working code that the language designer probably did not specified/wanted.

> Perhaps standard libraries can be written in the language itself -- but other than that, would it be correct to say that we ever only "download" implementations of the language?

You always download a set of instructions that the host system would understand. It might have been written in some specific programming language. For example when you download a game, it is a collection of binary instructions meant for your processor. When you download a byte code program, it is a collection of instructions for the JVM.

---
Tags: programming-languages, compilers, interpreters
---


# Question
Title: Dynamic Programming, Counting Independent Sets
My first thought is to make OPT(i, j), where i is n, and j is some condition on the column. But my experience with DP is from knapsack and weighted interval scheduling, but I'm unsure of how to approach this. Any ideas would be great.

# Answer
Let $OPT\_N\[i\]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that neither of the leftmost two vertices can be selected into an independent set.

Let $OPT\_T\[i\]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the top of the leftmost two vertices must be selected in the independent set.

Let $OPT\_B\[i\]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the bottom-most of the leftmost two vertices must be selected in the independent set.

According to the above definitions $OPT\_N\[1\] = OPT\_T\[1\] = OPT\_B\[1\] = 1$ while, for $i\>1$: $$ \begin{align\*} OPT\_N\[i\] &= OPT\_N\[i-1\] + OPT\_T\[i-1\] + OPT\_B\[i-1\]\\ OPT\_T\[i\] &= OPT\_N\[i-1\] + OPT\_B\[i-1\]\\ OPT\_B\[i\] &= OPT\_N\[i-1\] + OPT\_T\[i-1\] \end{align\*} $$

The number of independent sets on a graph with $2i$ vertices is then $OPT\_N\[n\] + OPT\_T\[n\] + OPT\_B\[n\] = OPT\_N\[n+1\]$.

You can simplify the above formulas by noticing that you must have $ OPT\_T\[i\] = OPT\_B\[i\]$.
> 2 votes

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


# Question
Title: How to connect line segments to form the least number of paths
I have a list of unordered line segments, some of whose endpoints lie on the same point. How do I connect these segments efficiently to form a minimal amount of paths?

For example, if I have the following lines $(x\_1, y\_1, x\_2, y\_2)$: `[[0, 0, 2, 2], [4, 0, 2, 1], [2, 2, 4, 0]]` the algorithm should be able to join these three segments into one path $(x, y)$: `[[0, 0], [4, 0], [2, 1]]`.

# Answer
You could solve this using any algorithm for the traveling salesman problem. Construct a graph with one vertex per line. Add an edge of cost 0 from line to another if they share an endpoint (these correspond to extending an existing path). Add an edge of cost 1 between each other pair of lines (these correspond to starting a new path). Now find the shortest traveling salesman tour of this graph. That will correspond to a minimal set of paths that cover all of the lines; the number of lines will be equal to the weight of the traveling salesman tour. There are standard algorithms and solvers for the TSP.
> 2 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Why is the complexity of the BFS O(V + E)?
Consider the algorithm (from another question):

```
set start vertex to visited
load it into queue
    while queue not empty
        for each edge incident to vertex
             if its not visited
                 load into queue
                 mark vertex

```

The complexity of the algorithm is defined as the upper bound of times the inner loop can run, right? Well, considering a complete graph. For each one of its N vertexes, we run the check `if its not visited` `N-1` times. So, that's `N * (N-1)` tests, which is quadratic. What is wrong with this view?

# Answer
> 2 votes
Overall, BFS accesses (and processes) each edge constant times (twice actually; we assume an undirected graph), costing $O(E)$ total time in edge processing. Similarly, all the vertices are totally accessed (including queue operations and checking operations) $O(E) \cdot O(1)$ times. The overhead for initialization is $O(V)$. Thus the total running time of BFS is $O(V + E)$.

This can be viewed as a simple instance of aggregate analysis.

# Answer
> 0 votes
Each vertex is visited once and each edge twice assuming implementation with an adjacency list so the running time is a constant multiple of the number of edges + number of vertices. Thus it is O(V + E).

# Answer
> -1 votes
In BFS algorithm we begin from a arbitary vertex, so we meet all of vertexes then we claim that $O(v)$.since we must meet all vertexes then we used maximum edges to reach other vertexes . so we have $O(V+E)$

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


title: Prove little o with just the definition

text:
# Question
Title: Prove little o with just the definition
I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation.

Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am supposed to prove, or disprove, the following statement: $f(n) \in \mathcal{o}(g(n))$.

I am fairly sure that it's true but now I need an idea of how to show this. We have just started out with this whole concept and this is the second exercise, the first one being a relatively easy big $\mathcal{O}$ task. But this exercise is just beyond me right now. The only definition I am allowed to use (meaning: NO LIMITS) is $\mathcal{o}(g(n)) = \\{f(n)|\forall C \> 0 \exists n\_{0} \forall n\geq n\_{0}:f(n) \< C * g(n)\\}$. This means other than with big $\mathcal{O}$, where it suffices to show that there's at least one pair $C$ and a $n\_{0}$ so that $f(n) \leq C * g(n)$ $\forall n \geq n\_{0}$, I now have to prove that for **every** $C \> 0$, there is such a $n\_{0}$ so that the condition stated in the set is true.

I first have been thinking about the functions, and I would have an answer for $\mathcal{O}$, because you can prove with induction that $2^{n} \< n!, \forall n\geq 4$. Meaning my C would be 1 here. However, I have no idea how to prove it for every C and would be grateful for any guidance! (It would already help to know how to start. Probably like, let $C$ be greater 0, and then I have to show that for any Value of this $C$, there is... because... My biggest struggle is to find meaningful estimations to get a chain of inequalities.)

# Answer
Pick $n\_0 = \max\\{ -\log c, 10 \\}$. Then, for all $n \ge n\_0 \ge 10$: $$ 2^n = \frac{4^n}{2^n} \le \frac{4^n}{2^{n\_0}} \le \frac{4^n}{1/c} = c \cdot (4^{n-10} \cdot 4^{10}) \< c \cdot (4^{n-10} \cdot 10!) \le cn! $$
> 3 votes

# Answer
One way to prove $f(n) = o(g(n))$ is to prove that:

$\begin{align\*} \lim\_{n \to \infty} \frac{f(n)}{g(n)} &= 0 \end{align\*}$

In this case, you know that:

$\begin{align\*} \lim\_{n \to \infty} \frac{2^n}{n!} &= 0 \end{align\*}$

since the series for $e^x$ converges for all $x$, so it converges for $x = 2$, and the terms of a convergent series have limit 0.

Or, if you take $n \ge 2$, you see that:

$\begin{align\*} \frac{2^n}{n!} &= \frac{2}{1} \cdot \frac{2}{2} \cdot \frac{2}{3} \dotsm \frac{2}{n} \end{align\*}$

Each successive factor after the second is smaller than 1, so the infinite product diverges to 0. That is, you can write for $n \ge 2$:

$\begin{align\*} 0 &\le \frac{2^n}{n!} \le \frac{2}{1} \cdot \frac{2}{2} \cdot \left(\frac{2}{3} \right)^{n - 2} \end{align\*}$

As $n \to \infty$, the right hand side tends to 0.
> 1 votes

# Answer
$2^n$ is the product of n numbers which are all equal to 2.

n! is the product of n numbers from 1 to n.

Once n ≥ 3, if you increase n by 1, $2^n$ is doubled, while n! is multiplied by 4 or more. So basic maths shows that for n ≥ 3, $n! ≥ 6/64 \cdot 4^n$.

Given any C \> 0 from the definition, you calculate how large n would have to be to make $2^n \< 6/64 \cdot 4^n$.
> 1 votes

---
Tags: algorithm-analysis, landau-notation, mathematical-foundations
---


# Question
Title: How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)
In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem:

I have a set of strings that appear in a corpus with their counts. I would like to merge the counts into any substrings that also appear in the corpus.

Here's a close, but incorrect example to demonstrate it. We create a directed graph of strings, where an edge exists from each node to each of its substrings. We then sum counts in topological order.

```
counts = {"hi":1, "hillo": 1,  "hillotoo":1, "hillotoothree": 1, "what": 1}

graph = nx.DiGraph()
graph.add_nodes_from(counts.keys())

for str1, str2 in combinations(graph.nodes, 2):
    if str1 in str2:
        graph.add_edge(str2, str1)
    elif str2 in str1:
        graph.add_edge(str1, str2)

for node in nx.topological_sort(graph):
    for neighbor in graph.neighbors(node):
        counts[neighbor] += counts[node]

```

In the end, 'hi's count should be 4, hi + hillo + hillotoo + hillotoothree. However, this code produces: `{'hi': 8, 'hillo': 4, 'hillotoo': 2, 'hillotoothree': 1, 'what': 1}`, because there's many more paths to 'hi' that get exponentially summed. This is because with substrings, there is a direct edge from every string to every one of its substrings by definition. Instead, I need to sum counts from each node to the **next smaller** substring on each path from that node to a sink in the graph, and remove/avoid "skip" edges from nodes to nodes further down paths to a sink.

(NOTE: This simple string example actually has a straightforward solution: copy the counts first, and only add the original counts to the new ones. However, this works **only** because there is a direct edge from every string to every one of its substrings, so this solution sidesteps the graph entirely. In the general case, this assumption does not hold. There, we do need to sum along paths, but only along the **longest** path from each node to each of its sinks, without taking any "skip" edges to avoid overcounting.)

Have a crack at this! Thanks.

# Answer
> 2 votes
## On the question from title

For fixed sink $s \in S$ you can find maximal distance from each vertex to this sink by running dynamic programming on topological order: $$ d(v)= \begin{cases} 0\text{ if } v = s\\ -\infty \text{ if } v \not= s \land v \in S\\ 1 + max\_{(v, u) \in E} d(u) \end{cases} $$ You can run this algorithm for every $s \in S$ to get the solution for whole problem.

## On your problem

Unfortunately your approach won't work, look at this graph:

```
A
|\
B |
| D
C |
|/
E

```

If you would look only for longest path to E from A, you would ignore existence of node D. So unfortunately I think you need to go with more "brute force" approach where you will have to run BFS/DFS from every node in the graph and check the number of reached nodes.

---
Tags: algorithms, graphs, graph-traversal, weighted-graphs, dag
---


# Question
Title: What's the name of this tree-like data structure?
I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties:

* It consists of nodes and leaves
* It has a single root element
* Both nodes and leaves each hold a single element
* Each node can have a non empty list of subtrees (a leaf could be considered a node with an empty list of children)
* All elements inside the tree are of the same type and can be compared against each other
* There are no duplicated elements inside a tree (this is especially interesting when it comes to inserting elements)

An implementation of this in Haskell could look like this (without the `Eq` constraint on `a` that would be required to compare the elements):

```
data Tree a = Node a (NonEmpty (Tree a)) | Leaf a

```

From my (rather limited) theoretical knowledge about data structures like this I think that it is some kind of unordered, unique tree. I guess that there is a well-known data structure somewhere out there and I'm hoping that someone can point me to the name as well as some resources about it.

I'm especially interested in algorithms for typical operations on this data structure:

* Traversing the tree
* Adding a single element to a tree
* Removing a single element from a tree
* Adding a tree to another tree (if the root element is already contained in the target tree, the tree should become a subtree to this element)
* Removing an element (including its children) from a tree

**To summarize: Is this data strucure well known? If so, what is the name for it and where can I find more information about efficient algorithms for operations on this data structure?**

# Answer
The data structure that is the closest to what's needed here seems to be the rose tree. It has all the properties except the uniqueness constraint.

There is also an implementation of this data structure in the containers package, where the implementation looks like this:

```
data Tree a = Node {
        rootLabel :: a,
        subForest :: Forest a
    }

type Forest a = [Tree a]

```

which almost matches the type definition in the question.

This data structure doesn't seem to be widely used in the Haskell community, but there are some functions that are interesting to understand, like the implementation for `Eq` and `Ord1`.
> 1 votes

# Answer
This is simply a tree, where all elements are unique. I'm not aware of any special name.
> 2 votes

---
Tags: data-structures, trees
---


# Question
Title: Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets
> Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.

More precisely, given a triplet $(i,j,k)$ with $i\<j\<k,$ it satisfies the question above if $A\[i\] \times A\[j\] \times A\[k\] = target$ and either ($j = i+1$ and $k \> j+1$) or ($k = j+1$ and $i \< j -1$.)

For example, if the list given is $A = \[1,2,2,2,4\]$ and target $= 8,$ then the answer is $2$ as $(0, 1, 4)$ and $(0, 3, 4)$ are the only triplets satisfying conditions above if we use $0$-based numbering.

I stucked at this question for 3 hours and not able to solve it.

Any hint is appreciated.

# Answer
> 1 votes
This will run fast unless someone creates a list specifically to make it hard for you:

```
Set count to 0.
Create a hash map with duplicates of all integers dividing the target, with their positions.
For all adjacent pairs i, i+1
  If A[i] * A[i+1] divides the target
    Look up all x equal to target / (A[i] * A[i+1])
    For each x
      If position < i-1 or position > i+2
        Increase count by 1.

```

This will be fast, assuming most products don't divide target.

# Answer
> 1 votes
Let $n$ be the number of integers and $t$ be the target integer. You can solve your problem in $O(n \log n)$ time as follows:

For every $i=0, \dots, n-1$, let $p = A\[i\] \cdot A\[i+1\]$ and compute, in $O(\log n)$ time, the number $\eta(t/p)$ of integers in $A$ that are equal to $t/p$ (more on that later). Then the number $\gamma\_i$ of triplets formed by $A\[i\]$, $A\[i+1\]$ and a non-adjacent element is $\gamma\_i = \eta(t/p) - |\\{A\[j\]=t/p \\, : \\, i-1 \le j \le i+2 \\}|$.

It follows that the number of triplets of interest is $\sum\_{i=1}^{n-1} \gamma\_i$.

To find the values $\eta(\cdot)$ do a preprocessing in which you create a copy $B$ of $A$, sort $B$ in $O(n \log n)$ time, and append an element with value $+\infty$ to $B$ (this is just to avoid edge cases, $+\infty$ can actually be any integer greater than $t$).

If $x \not\in\mathbb{Z}$, $\eta(x)=0$. Otherwise $\eta(x)$ can be found in $O(\log n)$ time by binary searching for the smallest indices $i$ and $j$ in $B$ such that $B\[i\]\ge x$ and $B\[j\] \> x$, respectively. Notice that $i$ and $j$ are always well defined and that $\eta(x) = j-i$.

---
Tags: algorithms, data-structures, arrays
---


title: Little O notation relationship

text:
# Question
Title: Little O notation relationship
Given the functions $()=^{n}$ and $()=10^{10n}$, I am trying to establish the following relationship: $()\notin o(())$.

I know to show for the opposite, $()\in o(())$, I would need to choos $c$ and $n\_{0}$ such that $\exists$ $c$, $\exists$ $n\_{0}$, $\forall n\geq{n\_{0}}$ then $f(n)\leq c. g(n)$, but how should I choose $c$ and $n\_{0}$. Note that I am beginner in studying CS and any help would be greatly appreciated.

# Answer
One possibility is to merely apply the definition. That is, we see that if $\lim\_{n \to \infty} f(n) / g(n) = 0$, then $f(n) = o(g(n))$. Computing this, we have that $$\lim\_{n \to \infty} f(n) / g(n) = \lim\_{n \to \infty} n^n/10^{10n} = \infty \neq 0.$$ We conclude that $f(n) = o(g(n))$ does not hold.
> 1 votes

# Answer
Your formulation of $f(n) \neq o(g(n))$ is wrong.

Recall that $f(n) = o(g(n))$ if for all $c \> 0$ there exists $n\_0$ such that for all $n \geq n\_0$, we have $f(n) \leq cg(n)$.

The negation of this is: there exists $c \> 0$ such that for all $n\_0$ there exists $n \geq n\_0$ such that $f(n) \> cg(n)$.

Take $c = 1$. Given $n\_0$, let $n = \max(n\_0,10^{10}+1)$. Then $$ f(n) = n^n \> (10^{10})^n = 10^{10n} = g(n). $$
> 1 votes

# Answer
start like this

$n \ge 10^{10}$, $\forall n \ge10^{10}$
raising exponent n on both side of inequality, we get
$\implies n^n\ge10^{10n}, \forall n \ge10^{10}$
$\implies 10^{10n}\le n^n,\forall n\ge 10^{10}$
$\implies 10^{10n}=O(n^n)$
$\implies n^n \notin o(10^{10n})$
Here the $c=1$ and $n\_0=10^{10}$

The value of $c$ and $n\_0$ must come from the derivation.
> 0 votes

---
Tags: time-complexity, asymptotics, runtime-analysis, big-o-notation
---


# Question
Title: Median-of-Medians proof for time complexity
Wikipedia mentions, that from the formula $$ T(n) \leq T(n/5) + T(n\cdot7/10) + c \cdot n $$

one can "easily" show using induction that

$$ T(n) \leq 10 \cdot c \cdot n $$

I am, as it seems, not so smart. So, can anyone tell me how to show this using induction?

# Answer
Assuming that you got the base covered, here is the inductive step: $$ T(n) \leq T(n/5) + T(7n/10) + cn \leq 10c(n/5) + 10c(7n/10) + cn = 10cn. $$ (Cheating a bit, since $n$ isn't necessarily divisible by 10; but that's a problem in the recurrence.)

You can also just apply the Akra–Bazzi theorem.
> 1 votes

# Answer
I am basically just paraphrasing the steps I've outlined here: https://cs.stackexchange.com/a/83650/68251.

This is assuming the base case is $T(n) \leq c$ when $n \< 5$.

### Claim

$T(n) \leq 10\cdot c\cdot n$

### Proof by Induction (on $n$)

**Basis**: $n \< 5 \implies T(n) \leq c \< 10\cdot c \< 10\cdot c \cdot n$

**Induction**: Assume the claim holds for any $n' \< n$, we then have

$$\begin{align} T(n) &\leq cn + T(n/5) + T(7n/10)\\ &\leq cn + 10c\cdot n /5 + 10c\cdot 7n /10\\ &= cn + 10c\cdot 9n /10\\ &= 10 \cdot c \cdot n & \square\\ \end{align}$$
> 1 votes

---
Tags: selection-problem
---


# Question
Title: LTL Model of (infinitely often p) ∧ ( infinitely often q) ∧ (¬ Eventually (p ∧ q))?
Can anyone give a model of the following LTL formula? $$ \Box\Diamond p \land \Box\Diamond q \land \lnot \Diamond (p \land q). $$ That is, we want each of $p$ and $q$ to hold infinitely often, but $p \land q$ should never hold.

# Answer
> 1 votes
Hint: Take $p$ to mean even number, $q = \neg p$ meaning odd number.

Can you come up with a model where you have infinitely often $p$ and infinitely often $q$ but never both at the same time?

---
Tags: formal-methods, linear-temporal-logic
---