# Question
Title: Dynamic graph (?) - combination of connections between vertices that for each 3 exist min 1 edge
I have to find number of ways (combination) to create graph that for each 3 vertices there are minimum 2 vertices connected. There is n vertices. For example when n=3, there are 7 possible combinations. How can I make this with maybe dynamic programming?

# Answer
> 2 votes
Your condition on the graph is the same as requiring its complement to be triangle-free. It is known that there are a lot of triangle-free graph. Indeed, since every bipartite graph is triangle-free, if we fix a partition of the vertex set into two sets of size $n/2$ (assuming for simplicity that $n$ is even), then we already get $2^{n^2/4}$ triangle-free graphs. It turns out that there aren't that much more, see this question on mathoverflow.

Perhaps you'd be interested in a paper on generating maximal triangle-free graphs up to isomorphism (in your case, you will be generating *minimal* graphs satisfying your condition), whose number is more manageable.

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


# Question
Title: Interval tree: find all intervals containing a given interval
Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(\min(n,(k + 1) \log n))$ where $k$ is the number of intervals returned. The only solution I can think of is bruteforcing in $O(n)$ time, but that's clearly too simple.
While looking for an answer I came across stabbing queries and the problem seemed very similar to this one. Is this something I could base my algorithm on or am I on the wrong track?

Edit: I might have an idea, but I'm still missing something.
Let $I=\[I\_s,I\_e\]$ and $x$ a node. If $x.s \leq I.s$ then there is an interval that contains $I$ in the left subtree of $x$ if and only if $\mathrm{left}\[x\].\max\geq I.e$. Suppose you had a similar statement for the right subtree of $x$, then you could do the following:
If the condition for the left or/and subtree is satisfied, recurse on those trees. Since there must be an interval covering $I$ in these subtrees this will result in $k$ paths with a maximum length of $\log n$.
If $x.s \> I.s$ there can't be an interval in the right subtree that covers $I$, but there might be one in the left, so recurse on left. If this happens repeatedly until you find a leaf, you get a path of length $logn$ without finding anything.

My question is: given $x.s \leq I.s$, how can I know for sure whether the right subtree of $x$ contains an interval covering $I$?

# Answer
Hint: A (non-root) interval can only contain I if its parent contains I.

For the algorithm in the pseudo-code below, TestInterval is not called for the same vertex twice, so the complexity is $O(n)$.

Consider the subtree S consisting of all nodes which TestInterval is called on. At every node in S which is not a leaf node, an interval must have been added to intervalContainingI (and k incremented). A binary tree with k non-leaf nodes can have at most $k+1$ leaf nodes. Therefore the complexity is in fact $O(k)$.

```
vector<int> intervalsContainingI;

void TestInterval(interval x)
{
    if (x.start <= I.start && x.end >= I.end)
    {
        intervalsContainingI.push_back(x);
        if (Exists(x.leftChild))
        {
            TestInterval(x.leftChild);
        }
        if (Exists(x.rightChild)
        {
             TestInterval(x.rightChild);
        }
    }
}

TestInterval(root_node);

```
> 0 votes

# Answer
If the nodes contain a `max_end` attribute in addition to the `interval`, you can use the `max_end` to stop looking further down the tree.

```
def find_containing_intervals(interval, root_node):
    stack = [root_node]
    containing_intervals = []
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.max_end < interval.end:
            continue
        if node.interval.contains(interval):
            containing_intervals.append(interval)
        if node.interval.start <= interval.start:
            stack.append(node.right_child)
        stack.append(node.left_child)

    return containing_intervals

```

Recursive solution:

```
class Node:
    def find_containing(self, interval):
        intervals = []
        if self.max_end < interval.end:
            return intervals
        if self.interval.contains(interval):
            intervals.append(interval)
        if self.right_child is not None and self.interval.start <= interval.start:
            intervals.extend(self.right_child.find_containing(interval))
        if self.left_child is not None:
            intervals.extend(self.left_child.find_containing(interval))
        return intervals

```
> 0 votes

---
Tags: algorithms, data-structures, search-trees, intervals
---


title: Computation of discrete logarithm

text:
# Question
Title: Computation of discrete logarithm
I know that an equation $$a^x \equiv b \pmod{p}$$ can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as follows: $$a^{nk} \equiv ba^{h} \pmod{p},$$ where $nk - h = x$.

I want to know whether one can solve the following equation (relatively) effectively: $$(a^x \bmod p) \equiv b \pmod{q} $$ where $p, q$ are primes and $p \> q$. I don't see how one can rewrite this one to apply meet-in-the-middle.

Problem source: I've been reading about Digital Signature Algorithm and I want to write a program that finds signature $(r, s)$ using public key only (for toy numbers), which can be done by solving for $r, s$ the following equation $$(r^s \bmod p) \bmod q = (g^{H(m)}y^{r} \bmod p) \bmod q$$

# Answer
As far as we know there is no efficient way to do that. Such a way would constitute a break of the DSA scheme, and no break of the DSA is known. In particular, DSA is believed to be secure, so it is believed that no efficient algorithm for this exists.

If you only want to do it for small numbers, you can just use brute force and try all possible values of $x$. Or, you can solve

$$a^x \equiv b \pmod p.$$

Then any solution to that equation will be a solution to your equation as well. More generally, you can pick any constant $c$ of your choice such that $0 \le c \< (p-b)/q$ and solve

$$a^x \equiv b + cq \pmod p;$$

if you can't find a solution for a particular value of $c$, try another one until you can. This won't be efficient once $p,q$ get large.
> 6 votes

---
Tags: algorithms, cryptography, number-theory
---


# Question
Title: Avoiding loops in Bellman-Ford algorithm
If you apply standard Bellman-Ford algorithm to a graph containing negative loop it can only report its existence. Are there approaches to modify it to find shortest path containing any vertex not more than once so effectively avoiding loops? I would appreciate if an answer will contain a link to a paper.

# Answer
As far as we know, you can't. The problem of finding the shortest simple path in a graph is NP-hard; it is equivalent to the problem of finding the longest simple path (just negate all edge lengths), which is at least as hard as Hamiltonian path, which is NP-hard. Therefore you shouldn't any simple modification to Bellman-Ford to yield an efficient algorithm for this problem; best guess right now is that no such algorithm exists.

See also https://cstheory.stackexchange.com/q/17462/5038 and https://en.wikipedia.org/wiki/Longest\_path\_problem. According to Wikipedia, the longest path problem is fixed-parameter tractable and can be solved in time exponential in the length of the longest path and linear in the size of the graph, which also applies to your problem as well.
> 3 votes

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: Black-box combinatorial optimization problem over permutations
I am solving general black-box optimization problems like: x\*: f(x) -\> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is represented by stand-alone computer code and x represents configuration of complex system with the response simulated by f(x).

I learned, that in this case I can use many heuristic methods. But, most of these methods use always some kind of local search, which require suitable distance metric at search space (space of permutations x in my case). Under suitable distance metric I mean the metric which fulfill the "locality" property, e.g. small change of permutation x produce small change of objective function f(x). In my case is not known any suitable distance metric with this property, so any kind of local search is nearly the random search.

I have a few questions:

1. Are there available any heuristic black-box combinatorial optimization methods, which does not use local search and/or any distance metric at search space? I need to overcome the low "locality" of the problem or simply the fact, that any suitable distance metric at search space is unknown.
2. Is the "locality" property really so restricted at combinatorial optimization in general? May be I miss something..., but the most of real-world black-box combinatorial problem has low or very low "locality" due to the fact, that the common permutation distance metrics (Hamming, Kendal, etc.) are not suitable metrics in general.
3. Is there any general method how to find suitable distance metric at search space to satisfy at least approximately the "locality"?

Additional remarks:

* In real, the black-box function f(x) is realized by stand-alone deterministic simulation code, where x plays a role of discrete configuration of the simulated physical system. So, function f(x) has definitely well defined properties, but this properties are so difficult, that is not possible to simple exploit it.
* Because of above mentioned complicated internal properties of function f(x) is not possible to find proper distance metric d(x,x') in search space which fulfill "locality" (similar x and x' in a sense of any distance metric produce similar responses f(x) and f(x'))
* So, finally, I am looking for any optimization heuristics, which are able to find any suitable sub-optimal solutions only by informations available by properties of f(x) at fitness space. Like EDA's (Estimation of Distribution Algorithms) for example.

The main reason of this question is, what types of optimization heuristics are suitable to solve this kind of problems.

# Answer
In general if you know nothing about f and it can be totally arbitrary, then there is nothing you can do: you cannot do better than brute-force. If f has no structure, no properties, no regularities, and is just totally random, then it is easy to see that any algorithm has to compute f on all $N!$ possible permutations to find the minimum.

In practice it is common to deal with functions f that do have *some* degree of structure. For instance, if x,x' are similar (for some notion of similarity), then f(x),f(x') might have a good chance of being similar. In those cases you can use techniques like local search. But if you don't have that property, then you can't use local search, and you may be back to a situation where you cannot do any better than brute force.

There are other approaches in other situations: e.g., if we know the symbolic expression for f, we might be able to use a SAT solver, especially if that symbolic expression is not too large. But again this requires f to have some structure and not be totally arbitrary.

There are no silver bullets. You need to know *something* about f to have a hope of doing anything.
> 2 votes

---
Tags: optimization, permutations, search
---


# Question
Title: Example of non extensible functions ( $f(x) \notin EXT $) for reduction
This is the definition of $EXT = \\{x\ | \varphi\_x\ can\ be\ extended\ to\ a\ total\ computable\ function \\}$. I'm trying to proof that $\overline{K} \le\_{rec} EXP$ and I can't think of an example of a function that can't be extended

# Answer
A classic example is

$$ f(n) = \begin{cases} k & \mbox{if $\phi\_n(n)\downarrow$ in exactly $k$ steps} \\ \uparrow & \mbox{if $\phi\_n(n)\uparrow$ } \\ \end{cases} $$

Above, "in $k$ steps" can be formalized more precisely using TMs (or another equivalent computational model), or Kleene's T,U normal form.

Here $f$ is trivially computable: we can try to simulate the evaluation of $\phi\_n(n)$ using a universal program / TM / whatever, and count the number of required computation steps.

Further, $f$ is partial since its domain is $K$.

However, $f$ can not be extended to a total recursive function $g$, since otherwise we could exploit $g$ to decide $K$. Indeed, $n\in K$ is equivalent to "$\phi\_n(n)$ converges in $g(n)$ steps", and the latter is decidable if $g$ is total recursive.
> 1 votes

# Answer
Every total uncomputable function cannot be extended to a total computable function. More generally, let $g$ be an uncomputable function, and let $h$ be a total computable one-to-one function, for example $h(x) = 2x$. Define a partial function $f$ by $f(h(x)) = g(x)$ (so $f$ is defined only on the range of $h$). The function $f$ cannot be extended to a total computable function.
> 1 votes

---
Tags: computability, reductions
---


# Question
Title: Is the intersection of infinitely many recursive sets recursive?
Is the intersection of infinitely many recursive sets $\bigcap\_{i}U\_{i}$ (where each set is different ) recursive? Recursively enumerable? I know the union need not be recursive, because deciding if an element is in the set $U\_i$ is the same as deciding the Halting Problem since you for each element you'll have to decide if the function that computes if $x \in U\_i$ for some $i$ will terminate.

# Answer
> 6 votes
Since you already know about unions, you could figure this out by remembering the de Morgan laws: the complement of a union is the complement of the intersection of complements. With this in mind: let $U\_i$ be the set of (indices of) Turing machines that do *not* halt within $i$ steps of execution. So, the complement $\mathbb{N} \setminus U\_i$ is the set of (indices) of those machines that halt within the first $i$ steps.

Now we have: $$\textstyle\bigcap\_i U\_i = \mathbb{N} \setminus \bigcup\_i (\mathbb{N} \setminus U\_i) = \mathbb{N} \setminus H$$ where $H$ is the halting set. The complement of $H$ is neither recursive nor recursively enumerable.

By the way, you state that "deciding if an element is in the set $U\_i$ is the same as deciding the Halting Problem ..." which is not necessarily true. For instance, if I set $U\_i = \\{42\\}$ for all $i$, then all the $U\_i$ are decidable. You need to pay attention to what your $U\_i$'s are.

# Answer
> 8 votes
For each $i\in \mathbb{N}$, take $S\_i = \mathbb{N}\setminus \\{i\\}$. You can now build any set you want as $X = \bigcap\_{i\notin X}S\_i$.

Similarly, an easier proof that a union of recursive sets can be anything at all is to let $T\_i=\\{i\\}$ and now any set $X$ is $X = \bigcup\_{i\in X}T\_i$.

---
Tags: computability, sets
---


# Question
Title: Remove parallel edges in a directed graph in linear time
Is there a $O(|V|+|E|)$ algorithm to find and remove all parallel edges in a directed graph? I'm stuck because each idea I've thought of boils down to $deg(v)^2$ comparisons per $v$ which is of course not linear.

Thanks.

# Answer
> 2 votes
Get a list of the edges, this should take no more than $O(|V|+|E|)$ in usual representations.

Run through the edges and check/add them to adjacency matrix represented as hash-table or sparse array. If an edge's entry has been set you know they are parallel. Do some constant time operations during and after iteration to handle the parallel edges how you'd like.

# Answer
> 0 votes
Assuming you mean a directed multigraph...

You can visit each vertex using a depth-first search with edge duplicate detection with a hash table (to avoid infinite cycles). If no cycles, each node gets visited exactly once ~ |V|. If there are cycles, one of the nodes in the cycle may be visited twice ~ \<|V|. |V|+\<|V|=O(|V|).

In the traversal, if an edge is already in the hash table, delete it (it is a duplicate), otherwise, traverse it and add it to the hash table. There will be exactly |E| duplicate checks and \<=|E| traversals. A hash table lookup is O(1) so you get O(|V|+|E|).

---
Tags: algorithms, graphs
---


title: Avarage height of Red-Black tree

text:
# Question
Title: Avarage height of Red-Black tree
I wrote a program to discover how height of the tree is relative to the number of elements in the tree (nodes).

On first test I filled array with 10-50-100-200...-1000 elements of random numbers from 0 to 32k~~ and checked their height and then second array with the same number of elements, however this time keys were picked randomly from 0-9, instead of 0-rand().

And I wonder if I have this right, is this possible height or im just getting some semi-random numbers. Would be grateful for checking that out. For now I don't know how to compare these scores and charts. The scores are very close, but the first array seems to have height slightly lower than second array.

# Answer
As a rule of thumb, your red-black tree depth can't be less than log(n) and it shouldn't be more than 2\*log(n+1). Your numbers look correct. (log(1000)=10 and your 1000 sample tests are between 10 and 20).

Ref: http://lcm.csa.iisc.ernet.in/dsa/node115.html
> 1 votes

---
Tags: data-structures, search-trees, balanced-search-trees, experimental-analysis
---


# Question
Title: Could a scientist make money off of the P vs. NP solution?
If someone solved the P vs. NP problem, would they be able to keep it a secret and make money off of it by, say, starting a software or security company? Or would they only be able to publish it for everyone to know?

Also, would that person (realistically) be at risk of being kidnapped, tortured, killed, etc. by governments?

Thanks!

Edit: not a duplicate because question focuses on the scientist who proves P=NP or P!=NP, whereas another thread focuses on worldwide impact as a result of a proof.

# Answer
Most immediately, if they publish it, they would win the Clay Mathematics Institute prize for solving this problem, so there's at least $1 million in it. They would also almost certainly be able to obtain a secure academic position, which would also be worth a significant amount.

Whether there's more money to be made off such a solution depends on a couple of things:

* Did they prove $\mathrm{P} = \mathrm{NP}$, or $\mathrm{P} \neq \mathrm{NP}$?
* If they showed $\mathrm{P} = \mathrm{NP}$, do they have a practical algorithm for everything in $\mathrm{NP}$?

For the first, if they proved $\mathrm{P} \neq \mathrm{NP}$, then perhaps nothing really changes. Most people are working under the assumption that this is true (give or take) now anyway. The maths they use may have something special in it that could be commercially useful, it may not.

If they showed $\mathrm{P} = \mathrm{NP}$, this is still not necessarily useful unless you have some way of getting *good* polynomial time algorithms, having a $\mathcal{O}(n^{2^{1000000}})$ algorithm for SAT is not really more useful than having an exponential one (in fact, would normally be worse, c.f. Alan Perlis).

Now, in the case that's interesting for script writers, if they show $\mathrm{P} = \mathrm{NP}$ *and* they have a fast algorithm for at least some interesting $\mathrm{NP}$-complete problems, then there are lots of ways to make money. Production planning, microchip layout, data mining, facility location, routing (both computer and otherwise), timetabling, etc. etc. are all major industrial problems, which already attract a lot of money and research, having the best algorithm in any one of these could be very financially lucrative.

Finally, if $\mathrm{P} = \mathrm{NP}$ *and* there's a fast algorithm for factoring (which is what I'm guessing you mean when you say security), then there is a brief window where someone could make money off that, before everyone just moved to already existing cryptographic schemes that don't rely on the apparent difficulty of factoring. The most white-hat version I can think of is helping ethically sound law enforcement agencies fight crime ("She's a cryptanalyst, he's a streetwise cop, together they fight crime!"). Almost every other use is black-hatted, probably run by organised crime or ethically challenged government agencies, and of dubious financial reward (there's definitely money to be made, but whether the person who discovers the proof makes that money is uncertain). The most extended version of this is that one of the three letter agencies (or equivalent) find out, quietly employ the discoverer, hush-up the discovery, and use the technology to spy on whomsoever they think has something they need to know. This would at least be a steady, probably well paying job, though it's hard to discern the exact salaries of, say, NSA employees, so it's a bit hard to tell.

It's difficult to imagine a sensible case where the person would be kidnapped, tortured or killed1. There's almost always simpler, more reliable and safer ways to get the information than attempting a rather dangerous operation (for example, just pay someone instead), but this is getting well away from the Computer Science part of this question.

**Footnotes**

1. As Evil (perfect name :D) points out in the comments, there is actually a potential motive for misdeed by those who are about to lose their jobs to the much better algorithm. My general counter in this case is that murder is insufficient; by the time they find out their businesses are dead in the water, the better solution has been commercialised and they would have to destroy an entire company, all its records, hardware and software. Conversely, they could, probably more easily, steal the technology and get in on the same game (the traditional route in IT - no-one got killed at Xerox PARC :D). My counter to my counter is that if someone found out about the discovery while it was still a one-person/one-computer operation, then you have a thriller movie (PSA time: always encrypt and back-up offsite, and set up a dead-man's switch...).
> 5 votes

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?
What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty (or randomness of some kind)? What are some examples in which the problems remain feasible? Can one tell in advance?

I am particularly interested in scheduling problems and what to know as to how the uncertainty in information (e.g. processing times of jobs) affects the difficulty of the problems. I believe the problem becomes more difficult when information is uncertain. Is it true?

# Answer
> 2 votes
Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic\_regulator

Interestingly, the problem remains easy when additive Gaussian noise disturbes the system and your observations of it:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic%E2%80%93Gaussian\_control

However, the problem becomes hard as soon as the noise is non-Gaussian (or even multiplicative Gaussian).

---
Tags: complexity-theory, scheduling
---


# Question
Title: L = { <M>, M is a DFA accepting all strings except finitely many
Is the $L$ = { $\<M\>$, $M$ is a DFA accepting all strings except finitely many. } decidable ?
I am sort of confused about the question - what exactly does $M$ accept. How are those finitely many strings look like for a particular $DFA$? It is known that $DFA$ accepts infinite number of strings if it accepts at least one string with length $\>=k$, where $k$ is the number of states. Does it mean that M doesn't accept any strings of size less then $|k|$ - since this number would be finite ?
I came up with the decider for $L$ call it $I$, which basically checks $M$ on accepting any strings of size less than $k$.
I = “On input $\<M\>$, where $M$ is a $DFA$:
1. Let $k$ be the number of states of $M$
2. Construct $k$ $DFA's$ denote them $D\_i$, where $i$ goes from $0$ to $k-1$, $D\_i$ accepts all strings of length exactly $i$
3. Construct a $DFA$ call it $T\_i$ such that $L\_i(T) = L(M) ∩ L(D\_i)$.
4. Test $L\_i(T) = ∅$ using the $E\_{DFA}$ decider
5. if $E\_{DFA} $ accepts for every $T\_i$ and $E\_{DFA}$ reject on $M$ =\> accept , otherwise reject.
Is there a simpler way of answering the question ?

# Answer
It is indeed decidable, but your solution is not quite correct.

To restate the problem, we're given an encoding $\langle M\rangle$ of a DFA $M$, and we want to decide whether accepts every possible string except a very small (finite) number of them. So for each DFA encoding in this language $L$, there's an associated $x\_{M} \in \mathbb{N}$ (which we don't know) and $M$ only rejects $x\_{M}$ strings.

So for example, a DFA $A$ that accepts everything (i.e. $\Sigma^{\ast}$) would be in $L$, because $x\_{A} = 0$, which is definitely a finite number. Similarly if we have a DFA $B$ which rejects the string $a$, but accepts everything else, this would be in $L$ as $x\_{B} = 1$, which is also finite.

Right, now to showing that this decidable for every DFA $M$. To do this we need to make a key observation, similar to what you were proposing, but sort of reversed; if a DFA rejects only finitely many strings, they must all have length smaller than $k-1$, where $k$ is the number of states. Why is this true? Suppose that it rejects a string with length greater than $k-1$, then to process this string the DFA must go around a cycle (either a loop or a longer path, or some combination thereof), but if it can go around the cycle once, it can do it twice, or three times, or any number of times. So if there's at least one long rejected string, there must be an infinite number of rejected strings.

Using this, we can see that if it rejects a string of length somewhere between $k$ and $2k$ (a single go around the cycle can use each state at most twice), then it must reject an infinite number of strings.

Finally we can get to our decider:

* On input $\langle M \rangle$ where $M$ is a DFA:
    1. One by one, enumerate all strings of length $k$ to $2k$.
        1. Simulate $M$ on each string.
        2. If $M$ rejects any tested string, reject.
    2. If $M$ rejects no strings of length between $k$ and $2k$, accept.
> 5 votes

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


# Question
Title: Using Myhill-Nerode to prove a language is non-regular
I'm trying to prove

```
L={w∈{0,1}∗:w contains more 00 substrings than 11 substrings}

```

is a non regular language using Myhill-Nerode theorem.

I'm a bit lost and not sure what to do. Thanks

# Answer
The basic idea here is that you are trying to show that there are infinitely many indistinguishable sets in $L$.

Distinguishable Strings: Let $L$ be a language over an alphabet $\sum$. We say that two strings $x$ and $y$ are distinguishable with respect to $L$ if there is a string $z$ such that $xz \in L$ and $yz \notin L$, or vice versa. That is, if we append $z$ to $x$ and $y$, the machine that processes $xz$ will be in a different state than if it were to process $yz$.

An indistinguishable set is then a collection of strings that are indistinguishable from one another but distinguishable from every other indistinguishable set.

Consider a FA $M$ that accepts $L$ = { even 0s } with alphabet $\sum = \\{0,1\\}$. The minimal FA for this machine has two states. There exists an indistinguishable set for every state, one set containing odd number of 0s and one set containing even number of 0s.

For your language, consider that you have { 1 00 substrings, 0 11 substrings } $\ne$ { 2 00 substrings, 1 11 substrings } $\ne$ { 2 00 substrings, 0 11 substrings } $\ne$ { 3 00 substrings, 2 11 substrings } $\ne$ { 3 00 substrings, 1 11 substrings } $\ne$ ... $\ne$ { $k$ 00 substrings, $l$ 11 substrings | $k \> l$ }. Each of these sets is distinguishable from other. In other words, your minimal FA would require infinitely many states due to its need for counting. Since an FA cannot have infinitely many states, the language cannot be regular.
> 3 votes

# Answer
Myhill-Nerode theorem defines an equivalence relation $xRy$ when $\forall w, xw \in L$ iff $yw \in L$

Then it says that this relation $R$ partitions $L$ in a finite number of partitions iff $L$ is regular.

So what you have to do is to show that if $L$ is not regular then this relation partitions $L$ into infinite number of partitions. For this you need to specify infinitely many strings which are not equivalent according to $R$.

Here are more details, How to prove that a language is not regular.
> 2 votes

# Answer
Consider any relation R which on $\\{0,1\\}^\*$ such that :

1. for any pair of strings $x, y$ related by $R$ we have, $xz, yz$ also related by $R$ (right congruence property)
2. any pair of strings $x, y$ are related by $R$ if either both $x, y$ are in $L$ or both are out of $L$ (refinement property)

Now if we have the property of finite index as well then by Myhill-Nerode theorem this will be a regular language, so to prove that this is not the case we should try to show that this doesn't have the finite index property:

consider 2 strings $a=(000)^n(11)^n$ and $b=(0000)^n(11)^n$ assume $a\ R\ b$ then by right congruence $(a1^n)\ R\ (b1^n)$ but $a1^n$ is not in $L$ but $b1^n$ is in $L$, therefore $R$ can not be of finite index, hence $L$ is non regular.
> 1 votes

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


# Question
Title: Prove that Big-O is transitive by relation. What does it mean by 'by relation'?
Prove $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$.

The question is

> Prove that Big-O is transitive **by relation.**

What does it mean by `by relation`??

# Answer
f(n)=O(g(n)) implies f(n) \<= c1\*g(n)
g(n)=O(h(n)) implies g(n) \<= c2\*h(n)
therefore,
f(n) \<= c1\*c2\*h(n) = c3\*h(n)

f(n) \<= c3\*h(n) implies f(n)=O(h(n))
> 0 votes

---
Tags: algorithms, proof-techniques
---


# Question
Title: Find all sets of nodes that can be connected with a single path
\** Edit: I just noticed my current algorithm is incorrect, as it only finds paths starting/ending at the given node. I'm trying to figure out a solution, but I'm a bit stuck.

Say I have an undirected graph. I would like to find all possible combinations of nodes that could be connected with a single path, that include a certain node.

--clarification: That is paths starting and ending at any node. Not just paths starting at the node in question.

Take this graph for example:

```
A----B
|    |
|    |
D----C

```

The solution for node A would be:

```
ABCD; example path A->B->C->D. Alternatively B->A->C->D or many others. As long as we have one, we're good.
ABC; example path C->B->A, etc.
ADC
AB
AD
A; 'path' from itself to itself

```

I understand this is a -very- hard problem with a lot of results. To make it simpler it is allowed to have some duplicates in the end result, but less would be better(this makes cyclic graphs a bit easier).

My current(naive) solution is as follows:

1. Start at the node in question
2. Note current path as possible path.
3. If no possible connections, return.
4. For each possible connection, go into recursion via \[2\].

See the following example. The problem with my algorithm is that a lot of duplicates are generated. Here the bottom two items in the example tree are the same solution.

# Answer
> 1 votes
Just use depth-first search. Each node you encounter in the search tree corresponds to a path from the source vertex.

---
Tags: graph-traversal
---


# Question
Title: How to prove that a transformed language is regular using an NFA
I am trying to prove that if a language $ L $ of binary strings (i.e. a subset of `[01]*`) is regular then so is the transformed language $ plus (L) $ consisting of the binary representations of those integers one greater than those represented by the elements of $ L $. That is to say $ plus (L) = \\{ plust (l) : l ∈ L \\} $ where $ plust $ transforms a binary of an integer $ n $ to a binary of $ n + 1 $, so $ plust ("0111") = "1000" $.

I am trying to prove this by assuming that there is a DFA that accepts $ L $ and using it to build an NFA that accepts $ plus (L) $.

However, I am totally at a loss as to how to do this. What is a good starting point, or what steps can I take to produce such a proof?

# Answer
Here's how to do it using closure operations; a similar idea can be used for constructing an NFA.

There are three cases to consider. The first case is words consisting only of ones. In this case, we want to transform $1^n$ to $10^n$. We accomplish this as follows. Let $h\colon \\{0,1\\} \to \\{0,1\\}^\*$ be the homomorphism defined by $h(0) = 1$ and $h(1) = 0$. We capture this part of $\operatorname{plus}(L)$ by the expression $1h(L \cap 1^\*)$.

The second case is words of the form $1x01^n$, which should be transformed to $1x10^n$. Here the construction is a bit more complicated. Let $a\colon \\{0,1,0',1'\\} \to \\{0,1\\}^\*$ be defined by $a(\sigma) = a(\sigma') = \sigma$ (where $\sigma \in \\{0,1\\}$). The expression $a^{-1}(L) \cap 1(0+1)^\*0'1'^\*$ replaces $x01^n$ with $x0'1'^n$. To complete the transformation, define $b\colon \\{0,1,0',1'\\} \to \\{0,1\\}^\*$ by $b(\sigma) = \sigma$, $b(0') = 1$, and $b(1') = 0'$. The expression $b(a^{-1}(L) \cap 1(0+1)^\*0'1'^\*)$ handles this part of $\operatorname{plus}(L)$.

The final case is the word $0$ (if it is in $L$), which should be transformed to $1$. This is accomplished by $h(L \cap 0)$.

In total, we obtain $$ \mathrm{plus}(L) = 1h(L \cap 1^\*) \cup b(a^{-1}(L) \cap 1(0+1)^\*0'1'^\*) \cup h(L \cap 0). $$ Note that any words in $L$ which are not binary encodings (in other words, the empty string and strings with leading zeroes) are just ignored. This can of course be changed if wanted.
> 1 votes

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


# Question
Title: How to use Neural Network classification if data not same size?
I have data like this.

```
[0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 1 0 1 ]
[0 1 0 1 0 1 1 1 1 0]
...

```

I want to classify with Neural Network but my data different size . I can not delete or add more arbitaly data. It may make the result not correct. So, How to classification data different size ?

# Answer
You can padd your data.

> I can not delete or add more arbitaly data. It may make the result not correct.

Don't make assumptions about neural networks. They can map any function, and if you don't add more data (padding) then you can't even train your network in the first place.

If your data consists of merely 0's and 1's. You could either do the following:

* pad all blanks with 0.5 (`[0 1 0 1 0, 0.5, 0.5, 0.5, .0.5]`), however the neural network will *think* that 0.5 is as far from 1 as it is from 0.
* pad all blanks with 0.5 (this is what I recommend), if your data is binary (e.g. true/false), then all false must be set to 0 consistently. 0 then has the double meaning: false or not present.

There is no other option besides adding 'blank' data, if you don't add data, the network will still see this as a `0`.

But you should *try before you ask*. "It may make the result not correct." is not a good argument to not do something. Your data doesn't seem that big, so you can easily test through trial and error.
> 1 votes

# Answer
I'm not an expert, but my understanding is the Recurrent Neural Networks are well suited to deal with sequences of data. This article gives a good (but possibly sensationalized) overview.
> 1 votes

---
Tags: neural-networks, data-mining, classification
---


# Question
Title: Undefined behaviour when composing primitive-recursive with $\mu$-recursive functions?
It is quite easy to show that the following two functions are primitive recursive and thus also $\mu$-recursive: $$ifthen(n,a,b) = \begin{cases}a & n \> 0 \\ b & else\end{cases} $$ $$ eq(x,y) = \begin{cases} 1 & x = y \\ 0 & else\end{cases} $$

Now, given a $\mu$-recusive function $f$ which is not total, i.e. whose domain $\mathcal{D}\_f$ is a proper subset of $\mathbb{N}\_0$, we can extend it to a function $f^\prime$ on $\mathcal{D}\_{f^\prime} = \mathcal{D}\_f\cup\\{x^\prime\\}$ for a fixed $x^\prime\not\in\mathcal{D}\_f$ via $$ f^\prime(x) = \begin{cases}x^\prime & x = x^\prime \\ f(x) & else\end{cases}$$ and this function $f^\prime$ can be expressed in terms of $ifthen$, $eq$, the constant function $x\mapsto x^\prime$ and $f$ as a composition of $\mu$-recursive functions as $$ g(x) = ifthen(eq(x,x^\prime), x^\prime, f(x)).$$

Here is the interesting question: Is there a consistent way to define at what time the arguments to any $\mu$-recursive function, and the function $g$ above in particular, are evaluated?

Let me illustrate the problem:

Assuming all arguments of $ifthen$ are evaluated before being passed to $ifthen$, then $g(x^\prime)$ will **not** return $x^\prime$ since the computation of $f(x^\prime)$ never terminates.

We could also assume some kind of "lazy evaluation" where arguments are only evaluated when they really are needed. Then, when implementing $ifthen$ using primitive recursion as $$ ifthen(0, a, b) = b \\ ifthen(n+1, a, b) = a,$$ the function $g$ would really be equal to the function $f^\prime$ as $f$ will never be called with argument $x^\prime$. But there is a different way to implement $ifthen$ using just arithmetic operations $$ ifthen(n, a, b) = a \cdot (1 \dot{-} (1 \dot{-} n)) + b \cdot (1 \dot{-} n)$$ where $\dot{-}$ is the modified difference $\dot{-}:\mathbb{N}\_0\times\mathbb{N}\_0 \rightarrow \mathbb{N}\_0$ defined by $$ x \dot{-} y = \begin{cases}x - y & x \geq y \\ 0 & else \end{cases}.$$ As primitive recursive functions, both implementation are equivalent and really compute $ifthen$, but if we assume $g$ uses this second implementation, then $f(x^\prime)$ again has to be evaluated and the computation of $g(x^\prime)$ never terminates, in particular $g(x^\prime) \neq f^\prime(x^\prime)$.

This seems odd to me, as computability of functions should not depend on the particular implementation of a function, but I have not been able to come up with a solution to fix that problem.

**EDIT:** More formally speaking, if we introduce the symbol $\bot$ for non-termination, the function $f$ above can be interpreted as a function $$ f:\mathbb{N}\_0\rightarrow\mathbb{N}\_0\cup\\{\bot\\} \\ f(x) = \begin{cases} f(x) & x\in\mathcal{D}\_f \\ \bot & else\end{cases}. $$ Using this notation, every $\mu$-recursive function $$ h : \mathbb{N}\_0^k \rightarrow \mathbb{N}\_0\cup\\{\bot\\} $$ can be extended to a $\mu$-recursive function $$ h^\prime : (\mathbb{N}\_0\cup\\{\bot\\})^k \rightarrow \mathbb{N}\_0\cup\\{\bot\\} \\ h^\prime(\bar{x}) = \begin{cases} h(\bar{x}) & \bar{x}\in\mathbb{N}\_0^k \\ \bot & else \end{cases}. $$ This corresponds to evaluation of arguments before the function $h$ is called.

Unfortunately, while this extension is sometimes unique (e.g. for the function $eq$ above), most of the time it is not. Especially in the case of a k-ary constant function it even is more natural to extend it to $$ const\_c^\prime : (\mathbb{N}\_0\cup\\{\bot\\})^k \rightarrow \mathbb{N}\_0 \\ const\_c^\prime(x\_1,\dots,x\_k) = c $$ instead.

The question I'm asking is the following: Given the implementation of a $\mu$-recursive function, is there a way to infer which extensions are / are not $\mu$-recursive?

One approach I tried is always assuming lazy evaluation of arguments. This yields the "correct" extension in the case of constant functions, $eq$ and the first implementation of $ifthen$, where the extension I need to be $\mu$-recursive in order to implement the function $f$ fulfills $$ ifthen^\prime : (\mathbb{N}\_0\cup\\{\bot\\})^3 \rightarrow \mathbb{N}\_0\cup\\{\bot\\} \\ ifthen^\prime(n, a, b) = \begin{cases} b & (n,a,b)\in {0}\times(\mathbb{N}\_0\cup\\{\bot\\})\times\mathbb{N}\_0 \\ a & (n, a, b) \in \mathbb{N}\_{\>0}\times\mathbb{N}\_0\times(\mathbb{N}\_0\cup\\{\bot\\}) \\ \bot & else\end{cases}. $$

But if I were just given the second implementation of $ifthen$, lazy evaluation just yields the canonical extension and not the one I require. Then the proof that $f^\prime$ is $\mu$-recursive would be incomplete unless I find the first implementation of $ifthen$ (or any other implementation of it that leads to the "correct" extension when assuming lazy evaluation), moreover it would be incorrect if there would not be such an implementation of $ifthen$.

How can I identify the possible behaviours of compositions of $\mu$-recursive functions?

# Answer
There's a couple of questions here, so a couple of answers.

# Changing when function parameters evaluated fundamentally changes your extensions of the function.

There seems to be a misunderstanding:

> As primitive recursive functions, both implementation are equivalent and really compute $ifthen$...

This depends on exactly what type of $ifthen$ function we're talking about. Let's look at your implementations. Your first:

> $ifthen(0, a, b)=b\\ ifthen(n+1, a, b)=a$

Note that, if the parameters are always "pre-evaluated" to natural numbers before being passed to the function, i.e. they can be treated simply as natural numbers, not as functions. In this case, this indeed implements a primitive recursive function, as you say. Now your second:

> $ifthen(n, a, b)=a⋅(1\overset{˙}{−}(1\overset{˙}{−}n))+b⋅(1\overset{˙}{−}n)$

Where $\overset{˙}{−}$ is truncated subtraction. Again, assuming pre-evaluation of parameters, this is primitive recursive and, as you point out, implements the same function as the first. Note that lazy evaluation does *not* affect this, since pre-evaluation means that no parameters except constant natural numbers will be passed to $ifthen$.

Since we're assuming pre-evaluation, both implementations *behave identically* in an extension such as the one you proposed:

> $g(x)=ifthen(eq(x, x'), x', f(x))$

Because any implementation of $f$ shouldn't halt when its input is undefined, but we're evaluting $f(x)$ before we even pass its value to $ifthen$, no program implementing $g$ will halt on $x$ when $f(x)$ is undefined, even if you assume lazy evaluation in $ifthen$.

Now, let's remove the restriction that the parameters to $ifthen$ are pre-evaluated; specifically, let us define a new function $ifthen^\*$ that accepts arbitrary $μ$-recursive functions for its parameters, along with some particular parameters for each function to be evaluated on. If all of the passed functions can be evaluated (i.e. they halt), then it evalutes $ifthen$ on the provided values; otherwise, it doesn't halt. By passing $ifthen^\*$ certain values, we can get a function equivalent to $g(x)$ implemented without lazy evaluation.

Note that $ifthen^\*$ is now a composition of arbitrary $μ$-recursive functions (its parameters). Therefore, by definition it is **not a primitive recursive function** and is not equivalent to the above $ifthen$ function!

However, it is *almost* equivalent to $ifthen'$, as defined in your post. The difference in the implementations of $ifthen^\*$ and your $ifthen'$ is simply lazy evaluation; i.e. it evaluates $n$ first, compares the result to $0$, then evaluates $a$ or $b$ as necessary, rather than always evaluating all the functions. Since $ifthen'$ is defined on some inputs that $ifthen^\*$ is not, *the two functions are not equivalent*. **This means that lazy evaluation is not just an implementation detail. It actually changes what function your program is implementing.**

This brings us to an excellent question of yours:

> How can I identify the possible behaviours of compositions of $μ$-recursive functions?

where a composition of a finite number of $μ$-recursive functions and no non-$μ$-recursive functions, is also $μ$-recursive. Likewise, you might ask, "given an implementation of an arbitrary $μ$-recursive function, can I determine which of its extensions require lazy evaluation". You seem to be looking for a consistent way to answer such questions regardless of the $μ$-recursive function in question, which leads to an unfortunate result:

# Non-trivial properties are undecidable over the $μ$-recursive functions.

That is, if you want to determine whether a particular $μ$-recursive function, its implementation, or its extensions have some sort of behavior or other property, unless the property applies to *all* $μ$-recursive functions or to *none* at all, there is no $μ$-recursive function that can decide whether some arbitrary $μ$-recursive function has this property. This is the main result of Rice's Theorem.

Note that this strictly refers to the semantics of arbitrary $μ$-recursive functions, i.e. whether the function itself has a property. Syntactic properties, i.e. properties of the implementation itself, not the function in question, *may* be decidable, e.g. the Bounded Halting Problem. However, the problem of determining whether a particular syntactic property is decidable is in turn semantic, and is undecidable for arbitrary properties.
> 2 votes

# Answer
I will only address a few points.

---

First, note that, in mathematics, the composition of two relations $R\circ S$ relates $x$ with $y$ iff $xRzSy$ for some $z$. This means that if there is no $z$ for which $xRz$, then there is no $y$ for which $x(R\circ S)y$ holds.

Since functions are relations too, the domain of $f\circ g$ is a subset of the one for $g$. Consequently, when writing $f(g(x))$, this is undefined if $g(x)$ is undefined.

Roughly speaking, the mathematical notation $f(g(x))$ assumes a "strict" interpretation: even if $f(n)=5$ for all $n$, we have that $f(1/0)$ is undefined.

---

In computability, if $f,g$ are primitive recursive, the function

$$ h(x,y) = \begin{cases} f(y) & \mbox{if $x\>0$} \\ g(y) & \mbox{if $x=0$} \\ \end{cases} $$

can be obtained as $h(x,y)=ifthen(x,f(y),g(y))$, so it is primitive recursive.

If $f,g$ are total recursive (not necessarily primitive), we also have $h(x,y)=ifthen(x,f(y),g(y))$, which becomes total recursive.

However, if $f,g$ are partial recursive, we no longer have $h(x,y)=ifthen(x,f(y),g(y))$ in general, since $h(x,y)$ is in general defined on more cases than $h(x,y)=ifthen(x,f(y),f(y))$. To prove that the conditional is partial recursive, usually the following steps are taken. We choose $i,j$ so that $f=\phi\_i$ and $g=\phi\_j$. Then, we exploit the universal function $eval(n,z)=\phi\_n(z)$, which we already know to be partial recursive, to derive

$$ h(x,y) = eval(ifthen(x,i,j),y) $$

Now, $ifthen$ is applied to "defined" arguments $x,i,j$, hence it will always produce a value: either $i$ or $j$ depending on whether $x\>0$. Hence, the final result will be either $eval(i,y)=\phi\_i(y)=f(y)$ or $eval(j,y)=\phi\_j(y)=g(y)$, as wanted.

This is the standard way to "lazify" the $ifthen$, so that it works on all prtial recursive functions.

As you see, this approach is different from using something like $lazyifthen(x,f(y),g(y))$, which can not work unless we allow $\bot$ in the domain. Doing so, however, requires some care, since e.g. $x=\bot$ can not be decided without solving the halting problem.
> 0 votes

---
Tags: computability, primitive-recursion, mu-recursion
---


# Question
Title: Compute the mode of an array concurrently
As an academic exercise, I have to write a parallel algorithm that given a sorted array of $n$ integers computes the mode (i.e. the item with the highest frequency) efficiently using $p$ processors, where $p \le n$ is a constant.

The model we use to describe these algorithms allows lock/unlock primitives to synchronize concurrent access to shared variables.

We cannot use hash tables. Could anyone share any hint on the optimal algorithm to solve this problem?

Edit: rephrased question according to comments.

Edit 2: adding my solution for feedback. While trying to solve the exercise I thought of an algorithm in the lines of

1. Declare two global variables, mode and modeFrequency and initialize them appropriately;
2. For i where $1 \le i \le p$, invoke a concurrent process on a portion of the array.
3. In each concurrent process: 3.1.. Find the local mode of the partition; 3.2. Store the local mode and its frequency in two local variables; 3.3. Compare the local mode with the global one: 3.3.1. if the mode is the same, add the local frequency to the global one; 3.3.2. if the local mode is different than the global one and the local frequency is higher than the global one, set the local mode/frequency to the global ones
4. Return the global mode.

but I am not convinced of the correctness of the algorithm. Please note that I omitted locks/unlocks for brevity. Also, can the way I partition the array make any difference on the correctness of the algorithm?

# Answer
> 1 votes
Since you asked for a hint:

> Partition the array.

Think about that for a while. If you need more of a hint:

> If you partitioned the array into $p$ partitions and assigned each partition to a single processor, could you compute the mode of the numbers within a particular partition efficiently? Would that help get you closer to a solution to what you want to achieve?

---
Tags: concurrency
---


# Question
Title: How is ReLU used in machine learning functions
I've seen how sigmoid would be used in machine learning

```
sigmoid(dot(activations, weights)-bias)

```

like this ^

but sigmoid makes sure your values are between 0 and 1. So how would ReLU ( max(0,x) ) be swapped out for sigmoid, if it doesn't clamp your values to a 0 to 1 range?

Or would I just use tanh(x) in the output layer?

My initial guess is that it would just look like this:

```
ReLU(dot(activations, weights)-bias) // all values are from 0 to +inf

```

Lastly, what is the traditional range for node biases? I'm guessing -1 to 1 just like weights.

# Answer
ReLU is used in all layers except at the very end. Normally softmax is used at the final output, to normalize the outputs to be in the range \[0,1\] and to ensure the outputs sum to 1.
> 1 votes

---
Tags: machine-learning, python, c++
---


title: Online set filling with redistributions

text:
# Question
Title: Online set filling with redistributions
**Edited**: Suppose we have 4 sets $A, B, C, D $ which can can hold a maximum of **two** elements, each.

Now, elements ($E\_i$) arrive **serially** with properties such as:

```
E1 : Should be placed in either B or C.
E2 : Should be placed in either A or B or C.
E3 : Should be placed in either A or B.

```

When an element arrives, we *have* to place the element in one of the 4 sets, *immediately* i.e. we *cannot wait* for all elements to arrive, and then decide.

When a new element arrives:

* If there exists space in one or more sets, satisfying the constraints, we place the element in the set with minimum cardinality. Ties are broken randomly.
* If there is no space satisfying the constraints, the existing elements may be redistributed to accommodate the new element.
* If even after redistribution, there is no space satisfying the constraints, discard the new element.

**Objective** Accommodate the newly arriving elements, while having less number of redistribution.

An illustrative example depicting the problem is attached.

**What strategy should i choose to achieve the objective?** I need an algorithm for the redistributions that is scalable to large number of sets and more than 2 entry for each set.

In the picture, randomly I have chosen 2 possibilities, one of which yields less number of redistribution than the other. So are there any approaches other than exhaustively checking all possible combinations?

# Answer
I can suggest two approaches:

# Brute-force search

First try to find if there is a way to place the element, without redistributing any previously placed elements.

If not, try to find a way to place it, by redistributing exactly one previously placed element. This can be done by enumerating all possibility for which element you redistribute and where you redistribute it to, to see if that leads to a valid placement.

If not, try to find a way to place it, by redistributing exactly two previously placed elements. This involves enumerating all combinations of two previously placed elements to redistribute.

In general, if $n$ elements have been previously placed and $r$ redistributions are needed, this will involve enumerating ${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose r}$ possibilities, which is $O(n^r)$. This might scale OK if you expect $r$ to be very small but becomes slow once $r$ is large.

# SAT solver

To get a more scalable solution, I suggest you use a SAT solver.

There's a natural way to encode your problem as SAT. Introduce boolean variables $x\_{i,j}$, meaning that element $i$ gets placed in set $j$ after redistribution. Each constraint is a clause (disjunction of some $x\_{i,j}$'s). Also, we can represent the requirement that at most $r$ redistributions be used as the sum of $\neg x\_{i,j}$ over all pairs $(i,j)$ that correspond to an element that is currently placed in set $j$ (before redistribution).

Thus, you can represent the problem of finding a solution using at most $r$ redistributions as an instance of SAT, and solve it using an off-the-shelf SAT solver. Use binary search over $r$ to find the minimal number of redistributions needed.

I expect that this will scale much better.
> 1 votes

# Answer
Suppose each set can contain at most $k$ entries.

Consider an arrangement as a flow in a directed graph where

* there is a source node $s$, a sink node $t$, a node $u\_E$ for each element $E$, and a node $v\_S$ for each set $S$,
* there is an edge with capacity $1$ from $s$ to each element node, an edge with capacity $k$ from each set node to $t$,
* there is an edge with capacity $1$ from $u\_E$ to $v\_S$ if $E$ can be placed in $S$, and
* a flow with value $1$ for each edge in the path $s\rightarrow u\_E\rightarrow v\_S\rightarrow t$ is sent to the graph if $E$ is placed in $S$.

In your example, the graph looks like the follows, where edges to $t$ have capacity $2$, and all other edges have capacity $1$.

The flow before redistribution is represented by bold edges in the following graph, where except the three edges indicated, values for other bold edges are all $1$.

Easy to see a redistribution corresponds to an augmenting path. For example, the red path in the following graph shows an augmenting path corresponding to your second possibility.

So the problem turns out to be finding the shortest augmenting path, which can be done by a breadth-first search from $s$. You can read Edmonds–Karp algorithm for more details, which is an algorithm to compute max-flow by repeatedly finding a shortest augmenting path.
> 1 votes

---
Tags: algorithms, greedy-algorithms, online-algorithms
---


# Question
Title: DFAs that must reach a certain state at least once
I was given this question:

> Let M = (Q,Σ, δ, q0, F) be a deterministic finite automaton. Assume that r∈Q is a state of M that is different from the start state q0.
>
> Define the language A⊆Σ\* to be the language consisting of all strings that are accepted by M and cause M to enter the state r at least once.
>
> Give a precise description (the 5-tuple definition) of a deterministic finite automaton N that accepts the language A.

My question is, wouldn't it be possible to define N as (Q,Σ, δ, q0, F) with F={r}? Unless I am sorely mistaken, it should be able to meet the question's criteria shouldn't it?

# Answer
> 2 votes
If it happened that $F \\{r\\}$, then that would also happen to be a DFA to which you wouldn't have to do anything to answer the question, but it doesn't cover the case where $r \notin F$.

To rephrase the question a little, imagine you have a DFA $M$ that accepts language $L$, and someone picks a random state $r\neq s\_{0}$, can you construct a DFA $M'$ that accepts language $L' \subseteq L$ where $s \in L'$ if it's in $L$ and it makes $M$ use state $r$?

Note that you don't get to pick $r$, it's essentially given as part of the input.

Taking it a little beyond your question, the answer is yes, it's possible, the trick is to do something special when you reach $r$.

A slightly more direct hint:

> Make a copy of $M$'s states (including accept status), cancel the accept status of any original states, and change the transitions out of $r$ to point to the counterparts in the duplicated set.

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: Agda: Which part does this type introduce universe inconsistency?
I was trying to prove following lemma,

```
  my_thm : ¬ (∀ {M : Set} (P Q : M → M → Set) →
    (∀ x → ∃ M , λ y → P x y ∨ Q x y) →
    (∀ x → ∃ M , P x) ∨ (∀ x → ∃ M , Q x))
  my_thm = ?

```

while Agda gives following mistake:

```
Set₁ != Set
when checking that the expression
{M : Set} (P Q : M → M → Set) →
(∀ x → ∃ M , λ y → P x y ∨ Q x y) →
(∀ x → ∃ M , P x) ∨ (∀ x → ∃ M , Q x)
has type Set

```

honestly, in my untrained eyes, this type looks entirely routine to me, and it shouldn't introduce universe inconsistency.

all extra quantifier and connectivities are defined as following,

```
  data _∨_ : Set → Set → Set where
    inl : {A B : Set} → A → A ∨ B
    inr : {A B : Set} → B → A ∨ B
  infixl 20 _∨_

  ¬_ : Set → Set
  ¬ P = P → False
  infix 40 ¬_

  data ∃_,_ : (A : Set) → (A → Set) → Set where
    ex : {A : Set}{P : A → Set} → (x : A) → (ev : P x) → ∃ A , P
  infix 10 ∃_,_

```

which part introduces `Set1` in this code?

---

ok, it turns out it's caused by negation: `¬_ : Set → Set`. However, I still not understand. why this innocent looking function does not do what I want? what's the correct way of implementing it?

# Answer
The term you're applying `¬_` to is large: it quantifies over all `M : Set` and therefore has type `Set 1`. So instead of `¬_ : Set -> Set` you need `¬_ : Set 1 -> Set 1`.

A more general solution it to make `¬_` level polymorphic as in the standard library: you will be able to use this definition of negation across the board no matter how large the thing you're negating is.
> 6 votes

---
Tags: type-theory, proof-assistants
---


# Question
Title: What is the maximum possible degrees of a vertex of an MST
What is the number that a minimum spanning tree can have a vertex with degree at most? Is there any rule? Is it related to the number of vertex or edge? Or not?

# Answer
Suppose that the graph is already a tree. Then the minimum spanning tree is the graph itself. In particular, if we take a star on $n$ vertices, we obtain a minimum spanning tree having a vertex of degree $n-1$. This is optimal, since in a graph containing $n$ vertices, all degrees are at most $n-1$.
> 1 votes

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


# Question
Title: How does automated verification of systems with infinitely many states work?
I need some help with basic definitions and intuition to understand why and how it's possible to verify systems with infinitely many states.

For example, if I consider an x86 computer, and assuming the CPU architecture is a large and finite state machine, it will have infinitely ($\aleph\_0$) many possible states (sequences) it can run, so how can systems with infinitely many states be theoretically verified at all?

# Answer
Infinite-state system verification is indeed a rather broad topic. First of all, all computers used nowadays can only have a finite number of states, as the amount of RAM is fixed. But that's is mainly a matter of terminology -- any verification technique that needs to iterate over all possible states is doomed from the beginning due to computation time.

Also note that you used "verification" in your title, and "to validate" in your question. These are different concepts that should not be confused. I will assume that you meant "verification".

To solve a verification problem with a large number of states, one typically constructs a *proof of correctness* of some sort. Such proofs do not need to refer to all possible states, rather they group sets of states by constraints that they satisfy. The description of the constraints can indeed by small, so that in the end we get a small proof.

For example consider the following function:

```
int comp(int parameter) {
    int p=parameter;
    if (p<0) {
        return p*p;
    } else {
        return p;
    }
}

```

We want to verify that the function comp never returns a negative number. If "int" is an arbitrary-length integer datatype, this program can already have an infinite number of states. To verify this program, we can perform a case split on whether "parameter" is negative or not, and then apply basic mathematical rules that we assume the integer data type to follow. What we get is a small correctness proof for an infinite-state system.

When researchers say that they work on infinite-state verification, they typically mean that they work of verifying systems in some type of modelling framework that allows to express systems with an infinite number of states - this does not mean that they can verify arbitrary such systems and their techniques are typically sound, but not complete.
> 9 votes

# Answer
While DCTLib's answer provides some insight in the general ideas, I think it is useful to give a more concrete example that has some use in practice.

One kind of 'infinite state system' is a labelled transition system $L$, where we describe a finite number of groups of states and transitions, but give each state a 'free' parameter from some domain, typically the natural numbers $\mathbb{N}$, and define transitions based on that parameter. We can ask whether certain proposition $P$ in the modal $\mu$-calculus hold (these include, but are not limited to CTL\* and thus can encode many questions about the process the state machine represents, such as whether the process will always halt).

If we restrict these transitions such that they are 'linear process equations', we can (relatively efficiently) transform the pair $(L,P)$ into a *Parameterised Boolean Equation System* (PBES) $E$, such that some state $s$ is true in the solution for this system if and only if the proposition $P$ on $L$ holds on $s$.

Although we cannot always solve this system $E$, there are approaches that work reasonably well and tools that implement them. One such tool is mCRL2. This tool uses various techniques to try to solve PBES's, but most generally boil down to attempt to construct an equivalent *Boolean Equation System* (BES), which is the 'finite version' of the PBES and can therefore be solved using Gaussian elimination.

---

The method of *proof graphs* might also be instructive:

The idea is to pick only a finite number of states as vertices in a graph, with an explicit parameter, e.g. $X(1)$, $Y(7)$, $X(3)$. Then, we take a labelling on the vertices and a (directed) edge relation on them that models the 'dependency' between these states. If a certain property over all finite prefixes of all infinite paths on this graph holds, we call this graph a proof graph (the general structure without this property is called a *dependency graph*).

The nice part is that we have that a certain variable ($\approx$state) $s$ is true in the PBES if and only if there exists a proof graph containing that state!

So, we have transformed a question of potentially infinite paths (CTL^\*) over an infinite system to a question of potentially infinite paths over a *finite* system. As all infinite paths on a finite system must eventually cycle, we can actually show that a graph is a proof graph automatically (Determining whether the proof graph exist may not be so easy, however. There is no panacea here!)
> 4 votes

---
Tags: complexity-theory, formal-methods
---


# Question
Title: Computing 'score' of string which preserves < relation
Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '\<' relation?

I've searched for order preserving compression/hashing but what I've found is either based on precomputing with known set of strings or is a some for of lossless compression.

**edit**:

To clarify - I don't need it to preserve order exactly. When I need is to have guarantee that if score(A) \< score(B) than A \< B. If score(A) \>= score(B) than it still can be true that A \< B. I just would be nice if probability of incorrect relation was 'low'.

# Answer
Suppose that your alphabet has size $N$ (say, $N=256$). You can think of each word as being over an alphabet of size $N+1$, with the extra element (first in the order) representing "end of word". Take a short prefix of the word (of some fixed constant size) and think of it as the base $N+1$ representation of a natural number.

As an example, suppose that the alphabet is $A\<B$ (in this order), and that we take prefixes of length 2. Consider the strings $$ A \< AA \< AAA \< B. $$ We think of these as the numbers $1,11,111,2$ in base 3. Taking prefixes of length 2, we get $10,11,11,20$ (here you see how the extra element is used). The encodings are thus $$ 3 \< 4 = 4 \< 6. $$
> 1 votes

---
Tags: strings, hash
---


# Question
Title: Control of the combinatorial aspects of a dynamic programming solution
I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems.

For this, I am looking at the canonical instance of the **coin exchange problem**: Let `S = [d_1, d_2, ..., d_m]` and `n > 0` be a requested amount. In how many ways can we add up to `n` using nothing but the elements in `S`?

If we follow a **Dynamic Programming** approach to design an algorithm for this problem that would allow for a solution with polynomial complexity, we would start by looking at the problem and how it is related to smaller and simpler sub-problems. This would yield a **recursive relation** describing an inductive step representing the problem in terms of the solutions to its related subproblems. We can then implement either a **memoization** technique or a **tabulation** technique to efficiently implement this recursive relation in a **top-down** or a **bottom-up** manner, respectively.

A recursive relation could be the following (Python 3.6 syntax and 0-based indexing):

```
def C(S, m, n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if m <= 0:
        return 0
    count_wout_high_coin = C(S, m - 1, n)
    count_with_high_coin = C(S, m, n - S[m - 1])
    return count_wout_high_coin + count_with_high_coin

```

However, when drawing the sub-problem DAG, one can see that any DP-based algorithm implementing this recursive relation would yield a correct amount of solutions but disregarding the order.

For example, for `S = [1, 2, 6]` and `n = 6`, one can identify the following ways (assumming *order matters*):

1. `1 + 1 + 1 + 1 + 1 + 1`
2. `2 + 1 + 1 + 1 + 1`
3. `1 + 2 + 1 + 1 + 1`
4. `1 + 1 + 2 + 1 + 1`
5. `1 + 1 + 1 + 2 + 1`
6. `1 + 1 + 1 + 1 + 2`
7. `2 + 2 + 1 + 1`
8. `1 + 2 + 2 + 1`
9. `1 + 1 + 2 + 2`
10. `2 + 1 + 2 + 1`
11. `1 + 2 + 1 + 2`
12. `2 + 1 + 1 + 2`
13. `2 + 2 + 2`
14. `6`

Assumming order does not matter, we could count the following solutions:

1. `1 + 1 + 1 + 1 + 1 + 1`
2. `2 + 1 + 1 + 1 + 1`
3. `2 + 2 + 1 + 1`
4. `2 + 2 + 2`
5. `6`

When approaching a problem solution from the Dynamic Programming standpoint, how can I control the order? Specifically, how could I write functions:

* `count_with_order()`
* `count_wout_order()`

?

Could it be that the need for order mattering implies choosing pruned backtracking over a Dynamic Programming approach?

# Answer
> 3 votes
There is absolutely no problem adapting dynamic programming to count solutions without regard to order (i.e., when order doesn't matter). Let $D(S,m,n)$ be the number of ways to obtain a change of $n$ using the first $m$ coins of $S = S\_1,\ldots,S\_M$. We have $D(S,m,0) = 1$, $D(S,m,n) = 0$ when $n \< 0$, and otherwise $$ D(S,m,n) = \sum\_{i=1}^m D(S,i,n-S\_i). $$ This recurrences forces the indices of coins used to be non-increasing: after using $S\_i$, we are only allowed to use $S\_1,\ldots,S\_i$. Counting non-increasing (or non-decreasing) solutions is the same as counting all solutions without regard to order.

---
Tags: combinatorics, dynamic-programming, python, memoization
---


title: Counting Deterministic Finite Automata

text:
# Question
Title: Counting Deterministic Finite Automata
I have a question regarding counting DFAs:

> Given a `Σ = {0, 1}` input string, with the state set `Q = {1...n}`, how would I find the total number of DFAs that can be constructed?

I believe this is a combinatorics problem, but I am not really sure what I would have to multiply.

Thanks.

# Answer
This is indeed a nontrivial problem. A solution can be found in this paper: Enumeration and Random Generation of Accessible Automata.
> 5 votes

# Answer
Essentially its the product of all transitions possible from each possible start state to each possible set of accept states. For this example, there are n^(2n) transition possibilities. Where there are n total states, each of which has n possible transitions per edge (input symbol) giving us n^(2n). We have n possible start states, and 2^n accept states (the power set of possible states.) The product of all three of these gives us: n^(2n)\*n\*2^(n).
> 1 votes

# Answer
TL;DR: $n \centerdot 2^n \centerdot n^{mn}$

where $\mid Q\mid$ $=$ $n$ and $\mid \Sigma\mid$ $=$ $m$.

We'll go through each element of a DFA 5-tuple to figure out the various combinations that would each yield a unique DFA. The 5-tuple consists of ($Q$, $\Sigma, \delta$, $s$, F)

$s$:

Any 1 element of $Q$ can be the start state. Thus there are $\mid Q\mid$ = $n$ ways to choose $s$.

F:

Any number of elements of Q can be accept states, therefore all subsets of Q are valid choices for F. The number of possible subsets for a set of cardinality n is 2$^n$. Another way to say this is the cardinality of $Q$'$s$ power set $P(Q)$ is 2$^n$

$\delta$:

$\delta$ is defined as f: $Q$ x $\Sigma\rightarrow Q$ i.e. the $\delta$ function's domain is $Q$ x $\Sigma$ and its range is $Q$. The cardinality of the domain is $mn$ where $\mid Q\mid$ $=$ $n$ and $\mid \Sigma\mid$ $=$ $m$, and that of the range is $\mid Q\mid$ $=$ $n$. Thus there are $n^{mn}$ ways to choose $\delta$.

$Q$ and $\Sigma$ are given; there is only $1$ way to choose them.

So the total number of ways to choose amongst the 5 elements of a DFA where $\mid Q\mid$ $=$ $n$ and $\mid \Sigma\mid$ $=$ $m$ is

$n \centerdot 2^n \centerdot n^{mn}$

Better 5 years late than never, huh?
> 1 votes

---
Tags: finite-automata, combinatorics
---


title: How to feed videos to a neural network

text:
# Question
Title: How to feed videos to a neural network
I have been coding and testing Neural Networks for a while but as of now I have only used IMAGE datasets. (i.e. I have **M training images and N testing images**).

Some datasets are video datasets. The UCSD Peds dataset for example has the following variants:

Peds 1: 34 training videos (of 200 frames each) and 36 testing videos (of 200 frames each) Peds 2: 16 training videos (of varying number of frames) and 12 testing videos (of varying number of frames)

So basically, in this case, I have **M *SETS* of training images and N *SETS* of testing images**.

I know the inputs to a neural network is arbitrary and anything can be fed, but I do not really understand how to feed a set of videos.

Will we merge all the 34 x 200 = 6800 training frames together and 36 x 200 = 7200 testing frames together and use the resulting set just like we use MNIST, etc?

How do we feed a set of training videos to a neural network?

What if I want to detect anomalies in the test videos? For example a neural network is trained using videos from UCSD dataset involving only pedestrians. And tested on videos which also have cars and bikes. So these cars and bikes are anomalies.

I'd want to classify an entire video on whether it contains just normal elements or some anomalous elements as well.

# Answer
> 2 votes
If you want to detect anomalies, my suggestion would be to build a classifier to classify individual frames of the video to determine whether that frame contains an anomaly. You'll need to categorize what you count as an "anomaly" and arrange for labelled data in your training set. But then you can extract all 6800 frames from the training videos, label each frame, and train a classifier on that training set of 6800 images. At this point the problem is the same as building a classifier on individual images. Then, given a test video, you apply the classifier to each frame to determine whether any of its frames contain an anomaly, and aggregate those results somehow (e.g., report the video as anomalous if the number of anomalous frames exceeds some threshold).

---
Tags: neural-networks, data-sets, video
---


title: What is a reducible flow graph?

text:
# Question
Title: What is a reducible flow graph?
What is a reducible flow graph? sorry if this is a stupid question but I'm having trouble finding an answer.
Also multiple equivalent definitions and some motivation would be nice too.

# Answer
> 1 votes
This blog post summarises the situation well my opinion, but let me go through some of your concerns:

Reducible is NOT equivalent to acyclic: consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with a loop from $z$ to $y$. Then there is an SCC $\\{y,z\\}$ so it is not acyclic. But it is reducible because the SCC $\\{y,z\\}$ has a single entry point y. Notice how this corresponds to a program with a while/for loop. On the other hand, if you consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with again a loop $z\rightarrow y$ but also a forward jump $x\rightarrow z$. Not this is not reducible anymore because the SCC $\\{y,z\\}$ has two entry points: $y$ can be entered from $x$, but $z$ can also be entered from $x$. This intuitively corresponds to a program like that:

```
x: if <some condition> goto z
y: do { <instruction>
z: }while(<cond condition}
w: end

```

Notice how there is no way to jump to $z$ without a goto, this is the point of reducibility and it corresponds to well-structured code without goto.

Concerning the back edges, if you take the counter-example for above, notice that there are two different ways to explore this tree in a DFS:

* from $x$, explore $z$ then $y$ and $w$: in this case the edge $z\rightarrow y$ is part of the spanning tree built by the DFS. But $z$ does not dominate $y$ because the path $x\rightarrow y$ does not go through $z$.
* from $x$, explore $y$ then $z$ then $w$: in this case the edge $y\rightarrow z$ is part of the spanning tree built by the DFS. But $y$ does not dominate $z$ because the path $x\rightarrow z$ does not go through $y$.

Maybe the source of your confusion is that domination is related to the initial vertex $x$, and not to the DFS. Recall that a vertex $y$ dominates a vertex $z$ if every path from the initial vertex to $z$ goes through $y$.

---
Tags: graphs, network-flow
---


title: Analysis of the Banana Game

text:
# Question
Title: Analysis of the Banana Game
My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs.

## Game Description

The banana game is played with a container -- e.g., a queue or a stack. The object of the game is to find a sequence of steps that will read a given string (i.e., sequence of letters) and print a given output string. There are 3 types of steps.

* **IN:** Read the next letter from input and insert it into the container.
* **PR:** Read the next letter from input and print it.
* **EX:** Extract a letter from the container and print it.

If such a sequence exists, then we want to find a shortest one. Otherwise we want to briefly and clearly explain why no such sequence exists. Link to original text: https://www.utsc.utoronto.ca/~nick/CSCA48/banana.html

Since the purpose of the game was only to play it, our professor never discussed any theory, or strategy for the game. Some students have come up with ways to generate solutions (for example by enumerating all sequences of valid moves and seeing if any of the results are equal to the destination string), but being first year students, none of our solutions were particularly novel or interesting. I have searched for a similar game, but my searches have not been fruitful. I am really interested in seeing the minimum time complexity algorithms for:

1. Finding the shortest solution
2. Finding out whether a given game is possible
3. Checking if a given solution is correct

Perhaps there are ways of representing this game that will make these thing easier to do (a graph or a tree)? I have also thought about this as some special version of The Tower of Hanoi (at least for the Stack ADT), but in this game you are not allowed to transfer characters back to the original "peg" so I guess it isn't very helpful. Note: this game can also be played with an ADT called `Bucket` which can only store one element.

# Answer
Your instructor might have been reading the article Stackable and queueable permutations by Peter G. Doyle, who considers two exercises in Knuth's Art of Computer Programming.

The context is that the string in question is a sequence of distinct numbers, and the task is to output them in increasing order (Doyle's article actually discusses the other direction – given numbers in increasing order, output them in a prescribed order).

When using a stack, there is no need to use operation **PR**, since it can be simulated by executing **IN** and then **EX**. It is a classical result that a sequence is stack-sortable iff it contains no instance of the pattern 231, that is, there are no three numbers $\ldots,a,\ldots,b,\ldots,c$ such that $c\<a\<b$.

When using a queue, if we don't use **PR** then the string would come out unchanged. When **PR** is allowed (which seems to go against Knuth's original intention), we obtain that a sequence is queue-sortable iff it contains no instance of the pattern 321.

Since then, the same problem has been studied with various other data structures (mostly, it seems, in the 1970s). The recent papers Permutations sortable by two stacks in parallel and quarter plane walks and Permutations sortable by deques and by two stacks in parallel contain many references on this interesting combinatorial pursuit.
> 3 votes

---
Tags: algorithms, game-theory, stacks, queues, towers-of-hanoi
---


# Question
Title: Can the following O(...) expression be simplified?
I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity:

$O(kn + k^2L + k^2nL + knL)$

I think I should be able to simplify this to:

$O(k^2nL)$

Am I correct? I'm a little fuzzy on how to simplify things when working with multiple variables, but it seems right that since every other term is a factor of $k^2nL$, it should dominate the other terms?

# Answer
Suppose that there exists a strictly positive constant $c \> 0$ such that $k,n,L \geq c$; this happens for example if $k,n,L$ are all positive integers. In this case, a function is in $O(kn + k^2L + k^2nL + knL)$ iff it is in $O(k^2nL)$, where for our purposes $f(k,n,L) = O(g(k,n,L))$ (read: $f(k,n,L)$ is in $O(g(k,n,L))$) if there exists a constant $C\>0$ such that for all $k,n,L$ "in range" we have $f(k,n,L) \leq C g(k,n,L)$. Here "in range" is the common domain of the functions $f,g$, such as all positive integers or all positive reals which are at least $c$, for some positive $c\>0$.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Why and how geometric series are used for proofs?
I often see that someone uses geometric series for proofs related to time complexity, but also I can't understand why they are used. Are they making proving easier? And how can I use this 'tool' for proofs? Can I transform problems to fit to geometric series?

For example the time complexity of this simple function to get a random prime is estimated by a geometric series, I don't see this is naturally (or rather intuitively) a geometric series.

The number of primes is guessed by $m / ln(m)$, so the expected value is $$\sum\_{i=1}^\infty i\left(1 - \frac{1}{\ln m}\right)^{i-1} \frac{1}{\ln m} = \frac{1}{\ln m} \cdot \frac{1}{1/(\ln m)^2} = \ln m.$$

# Answer
The pattern appears often because many randomly controlled loops behave like a series of coin flips!

Consider this sketch:

```
while P(state)
    do(state)

```

If the different evaluations of `P` are stochastically independent and identical (i.i.d.), the probability of the loop executing for $k$ times is

$\qquad\displaystyle \operatorname{Pr}(\mathtt{P(state) == false}) \cdot \sum\_{i=0}^k \operatorname{Pr}(\mathtt{P(state) == true})^{k}$;

this is exactly the probability weight of a geometric distribution. Therefore, it will appear in any analysis.

Many loops do *not* fall into this pattern, and then you will see other sums or recurrences during the analysis.
> 3 votes

# Answer
Okay, this is the first case of my comment. This isn't a "tool"; this is simply the formula that comes up when you try to estimate the expected time complexity. Or more precisely, the expected number of iterations of the loop.

The $\frac{m}{\ln m}$ estimate for the number of primes less than $m$ comes from the prime number theorem. If we uniformly pick a number from $\\{2,\dots,m\\}$, then the probability that it will be prime is $\frac{1}{\ln m}$. The probability that it won't be prime is then $1-\frac{1}{\ln m}$. The probability that we will find a prime in *exactly* $i$ iterations is the probability that we fail to find a prime in the first $i-1$ iterations, and then find one on the $i$th iteration. Since the selection of the random numbers are (assumed) independent, this is $(1-\frac{1}{\ln m})^{i-1}\frac{1}{\ln m}$. Let $S$ be the number of iterations the algorithm takes. The probability that the algorithm takes exactly $i$ iterations, i.e. $S=i$, is $$P(S=i)=\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$ except $P(S=0)=0$ since the algorithm always goes through at least one iteration.

By definition of expectation, the expected value of the number of steps is $$\mathsf{E}\[S\]=\sum\_{i=0}^\infty SP(S=i)$$ Expanding this out, we get $$\mathsf{E}\[S\]=\sum\_{i=1}^\infty i\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$

In other words, exactly the geometric series you mention. At no point did I attempt to get the problem in the form of a geometric series, and there is no guarantee that it would be of that form. Instead, you can just start from the definition of expected value which is what you're trying to show. Then you see you need the probability of $S=i$ which happens to have a form that leads to the expectation being a geometric series. That said, if each iteration of a loop independently has a constant probability of terminating, which is common, then you will get a similar geometric series. If the probability changed with each iteration or the probabilities were correlated, then you would not end up with a geometric series in general, but the approach to the solution would be just the same, though actually simplifying the resulting infinite series in those cases might be quite difficult or impossible.
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis, proof-techniques
---


# Question
Title: context free grammar not closed under relative complement using product construction of pda and dfa
Hello friends need a bit of help,

I Know that

given: $$L\_1 \in L\_{cfg}, L\_2 \in L\_{reg}$$ $$L\_2/L\_1\notin L\_{cfg}$$ because if it was contex free it would imply that $L\_{cfg} $ is closed under complement and this is not true. But at another glance I can build a product construction of pda and dfa that could solve this problem.

Consider this:

1. product construction of pda and dfa
2. at any input read the input and at the same time move through the pda and the dfa
3. the accept states will be all the states where $(q\_1, q\_2)$ s.t $q\_1\notin A\_{pda} $ and $ q\_2\in A\_{dfa}$

this machine should accept the language of $L\_2/L\_1$ and this would imply that this language is infect context free. I know that some-thing is wrong here but it scares me that I cant understand what... please help.

# Answer
If you forget about the product-part of this construction (or just consider $L\_2=\Sigma^\*$) then your proposal amounts to swapping the accepting states of the pushdown automaton. The new PDA has an accepting state iff the original one did not have one.

This is similar to the construction for *deterministic* finite state automata. The problem here is that the original PDA is not deterministic. Thus for a single input there might be two computations, one which accepts and the other that does not accept. With your construction both the original and the new PDA will accept that input.

Moreover there might be inputs that do not have a full computation (the machine "blocks"). With your construction both of the PDA will not accept.

PS. In his comment Raphael observes complementation for nondeterministic automata in general has the same flaw when one swaps accepting and nonaccepting states. Many of his links relate to Turing machines, but perhaps especially look at his own answer where the problem relates to finite automata: "Language described by inverting accepting states of NFA"
> 5 votes

---
Tags: automata, finite-automata, pushdown-automata, closure-properties
---


# Question
Title: Is there a logspace version of the reduction used in Cook-Levin?
The proof (one of the standard ones, anyway) for Cook-Levin uses snapshots. E.g., see Cook-Levin proof (end of page 2, early page 3)

Now, $z\_i$ ( where $z\_i$ describes a snapshot of the machine ) depends on $z\_{i-1}$ and $z\_{prev\_{m}(i)}$, but to calculate $z\_i$ we cannot erase index $i$, or we will forget what we are currently calculating. What happens if we are restricted to logspace? If we keep the recursive procedure, the stack may well take more than logspace since the variable i might become very large.

And a follow up is, if such log space reduction really exists, wouldn't that imply $P$ is in $L$?

# Answer
> 3 votes
To address your "follow-up", no. The ability to use logspace reductions instead of polynomial time reductions to prove **NP**-completeness doesn't prove that **P** is contained in **L**. It just proves that you don't need the full power of polynomial time reductions to define **NP**-completeness. The situation is similar to saying, "Hey, there are lots of polynomial-time algorithms for graph reachability but I just found out that the problem is in logspace. Does that mean that **P**$\\,=\\,$**L**?" except that now we're talking about a whole class of computations (the reductions) rather than just one problem.

In fact, if you check out books on descriptive complexity,1 you'll see that we can use even weaker notions of reduction (reductions definable by first-order formulas) and still define a meaningful and, as far as we know, equivalent notion of **NP**-completeness. This is reassuring: it tells us that **NP**-completeness is a robust concept that doesn't seem to depend exactly on how you define it.

I say "doesn't seem to depend" because, as far as I'm aware, it is not known that defining **NP**-completeness in terms of polynomial time, logspace and first-order reductions makes exactly the same class of problems **NP**-complete. But there are no problems known to be **NP**-complete under one of these kinds of reductions but not under one of the others. (Stand by for this paragraph to be edited after people comment!)

---

1 E.g., Immerman, *Descriptive Complexity* (Springer, 1999) or Libkin *Elements of Finite Model Theory* (Springer, 2004).

# Answer
> 2 votes
To answer your first question. Your variable i only ranges in between 1 and T, which is the total number of steps the TM being snapshot takes before halting. Since the TM runs in polynomial time, i.e. $n^c$ for some constant $c$. This the number of bits needed to represent $i$ should only range from 1 to $c \cdot logn$ which is only logarithmic space.

I should also add, that if you think about it, all that you need to compute the next snapshot is, the previous snapshot, $z\_{i-1}$ which doesn't vary based on input size. Also the current input tape content which needs at most logn bits as an index, and having to remember when the head had last visited its current working tape position or index it's currently on to re-check its tape contents to determine the next move, which is at most a constant. Thus it can be done under logarithmic space.

The proof for this is laid out in detail in Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach

---
Tags: complexity-theory, reductions
---


title: Find all the cumulative sums in a DAG

text:
# Question
Title: Find all the cumulative sums in a DAG
Let's call G a DAG (directed acyclic graph) with N nodes labeled with a natural value.

We define the cumulative sum of a node v as the sum of the value of all the ancestor nodes of v (including v).

For example, the cumulative sum of d in the following DAG is 7:

```
      a (2)
     / \
    v   v
(1) b   c (3)
     \ /
      v
      d (1)

```

Is it posible to compute the cumulative sum for a set of M nodes in G, in less than O(M\*(N + E))?

---

*Clarification*: computing the cumulative sum for a set of nodes refers to computing the cumulative sum for each node of the set.

---

*Further clarification*: for a given cumulative sum, each ancestor is counted only once (notice that the ancestors of $u$ include $u$):

$cumsum(v) = \sum\_{u \in \text{ancestors of } v} \text{value of } u$

Which does **not** imply:

$cumsum(v) = \text{value of } v + \sum\_{u \in \text{direct ancestors of } v} cumsum(u)$

because this last formula may count ancestors multiple times. For example, in the diamond example we have:

$cumsum(d) = 7$
$cumsum(b) = 3$
$cumsum(c) = 5$
so $cumsum(d) \neq 1 + cumsum(b) + cumsum(c)$

---

Solution in O(M\*(N + E)):

> To compute the cumulative sum of a single node v in O(N + E), sort the DAG topologically and traverse the sorted list of vertices backwards, tainting all ancestors of v with the back edges, and adding the values of all the ancestors. (You could also just do a DFS for the same price).
>
> Doing this for each node in the given set of M nodes gives a running time of O(M\*(N + E)).
>
> Although it doesn't affect the final running time, the topological sort could be done only once before looping through each cumulative sum calculation.

# Answer
> 1 votes
It's possible to do slightly faster, by using sophisticated algorithms for transitive closure based on fast matrix multiplication, but apparently it is not known how to do this much faster than the naive solution. See https://cstheory.stackexchange.com/q/553/5038 and https://cstheory.stackexchange.com/q/736/5038 and https://cstheory.stackexchange.com/q/4258/5038.

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


# Question
Title: Find a path that contains specific nodes without back and forward edges
I have a directed graph and and a set of nodes(set = \[1,2,5,9,24...\]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For example for set = \[1,3,4\] the following path is acceptable:

but for the same set of nodes the following paths are not acceptable:

and

First of all i thought that it would be a good step to write bfs code for finding the nodes that i can visit from a specific starting node. Here is my code:

```
def bfs(G, s):
    q = queue.Queue()
    visited = []
    #Put s onto a FIFO queue
    q.put(s)
    #mark s as visited
    visited.append(s)
    #Repeat until the queue is empty
    while not q.empty():
        #remove the least recently added vertex v
        v = q.get()
        #for each unmarked vertex pointing from v:
        #add to queue and mark as visited
        for node in G.neighbors(v):
            if node not in visited:
                q.put(node)
                visited.append(node)
    print(visited)

```

Does anyone have any idea about how to modify bfs algorithm for finding the path containing specific nodes without back and forward edges? Can you write a pseudocode example?

# Answer
This is the Hamiltonian path problem. No efficient algorithm is known, and it is widely suspected that no efficient algorithm exists. You can read the linked article for references that suggest a variety of algorithms for this problem.
> 0 votes

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


# Question
Title: Datastructure for lookup of single point in range (3d)?
I'm new to CS and being aware of what algorithms exist, but what data structure allows you to have fast lookups of single points within a distance in 3d?

e.g. (with 2d circles instead of 3d spheres)

I would expect the first location to return null, and the second one to return circle a.

Circles can not overlay, circles/spheres differ in radius.

I would assume this to be nearest neighbor, but maybe some optimizations can be made considering you are often outside the area?

# Answer
> 2 votes
I would not use a nearest neighbor query, they tend to be expensive compared to window query or range query. However, most indexes that support nearest neighbor also support window queries.

You can use any spacial index that supports shapes, quadtree, R-Tree (especially RStarTree), ...:

* Insert your circles into the index. This is often only supported as inserting rectangles, so you may have to insert the MMB (minimum bounding box).
* For querying, indexes commonly support window queries (rectangular, axis-aligned windows(boxes)). Just set the window size to 0 by defining the min/min/min corner and max/max/max corner of the query to be equal to your search point. This should return all MBBs that intersect with your search point.
* Finally, for all returned circles, you have to manually calculate whether they really intersect with your search point (they may not intersect because the MBB is larger than the circle.

For example-implementations (Java) of various spatial indexes have a look here (shameless self advertisement).

# Answer
> 1 votes
You could in principle use any data structure for nearest neighbor search, of which there are many. Your specific version of the problem is known as fixed-radius near neighbors, and there are many solutions in the literature that are optimized for this particular version of the problem.

One simple solution is to overlay a grid, map every point to its grid square, and then do lookups by looking at all points in the same and adjoining grid squares. Since you are in 3D space, you'll only have to look at 27 grid squares (assuming you make the width of each grid square equal to the fixed distance), so this should allow for essentially constant-time operations.

---
Tags: data-structures, computational-geometry
---


# Question
Title: Between every two MST's there's a series of "nearby" MST's
Given undirected connected graph $G=(V,E)$ and a weight function $w:E\to\mathbb{R}$, two MST's $T\_1, T\_2$ are nearby if there exists $e\in T, e'\in T'$ such that $T'=(T-\\{e\\})\cup\\{e'\\}$.

Prove that for every $T, T'$ there exists a series of $T=T\_1,T\_2,...,T\_k=T'$ such that every two consecutive MST's are nearby each other.

---

I started proving it using induction but it didn't work. Assume I have $T,T'$ that has $k+1$ distinct edges each, and I know (by induction assumption) that each two MST's with $k$ distinct edges has a series between them, what can I do next? All I know is that the sum of those $k+1$ edges in each MST is equal.

Thanks.

# Answer
Here is how you make progress from $k+1$ distinct edges to $k$ distinct edges.

Suppose $T$ and $T'$ has $k+1$ distinct edges, which refer to $k+1$ edges in $T$ and another $k+1$ edges in $T'$ and they are all distinct. Among these $2k+2$ edges suppose $e\in T$ has the smallest weight.

Adding $e$ to $T'$ results in a cycle $C\subseteq T'\cup\\{e\\}$. If there is an edge $e'\in C$ such that $w(e')=w(e)$ and $e'\notin T$, then we are done: let $T''=(T'\cup\\{e\\})-\\{e'\\}$, and now $T''$ has $k$ distinct edges with $T$, while $T''$ and $T'$ are nearby.

The rest is to show that such an edge $e'$ always exists. Since $C$ cannot be entirely contained in $T$, there must be an edge $e'\in C$ that $e'\notin T$. I leave it to you to verify that either $w(e')\<w(e)$ or $w(e')\>w(e)$ cannot happen, so it must holds $w(e')=w(e)$ and that $e'$ is what we want.
> 2 votes

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