# Question
Title: Shortest walk from $u$ to $v$ through $w$
We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W\_1 : E \rightarrow \mathbb{R}^{+}$ and $W\_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W\_1(e) \> W\_2(e)$.

The length of a walk $\sigma$ is calculated in such a way that for every edge $e \in E$, for the first appearance of $e$ in $\sigma$ we calculate the weight of $e$ by $W\_1(e)$, and for reminding appearances of $e$ in $\sigma$ we calculate the weight of $e$ by $W\_2(e)$.

The goal is to find the shortest walk from $u$ to $v$ through $w$. Is this problem $\mathsf{NP}$-hard? If not, how can we find such a walk?

# Answer
The shortest walk must have the form

```
u
 \
  t<->w
 /
v

```

where the edges in each arrow are disjoint. To see this, suppose in the shortest walk, we go through nodes $u\_1'=u,\ldots,u\_{k'}',u\_1,\ldots,u\_k=w$ from $u$ to $w$, go through nodes $v\_1=w,\ldots,v\_l,v\_1',\ldots,v\_{l'}'=v$ from $w$ to $v$, where $v\_1',\ldots,v\_{l'}' \notin \\{u\_1',\ldots,u\_{k'}',u\_1,\ldots,u\_k\\}$, and $v\_l=u\_1$, like the following graph:

```
                  u    (u_1,...,u_k)
 (u_1',...,u_{k'}')\        /\
                    u_1(v_l)  w       The walk (u_1,...,u_k) may overlap with (v_1,...,v_l)
 (v_1',...,v_{l'}')/        \/
                  v    (v_1,...,v_l)

```

Now suppose edges $e\_1,\ldots,e\_h$ are shown in both the walk $(u\_1,...,u\_k)$ and the walk $(v\_1,\ldots,v\_l)$, and the remaining edges in both walks are $f\_1,\ldots,f\_p$ and $g\_1,\ldots,g\_q$ respectively. Then the cost of the walk $(u\_1,...,u\_k=v\_1,\ldots,v\_l)$ is \begin{align\*} &\sum\_{i=1}^h (W\_1(e\_i)+W\_2(e\_i))+\sum\_{i=1}^pW\_1(f\_i)+\sum\_{i=1}^qW\_1(g\_i)\\ \ge{}&\sum\_{i=1}^h (W\_1(e\_i)+W\_2(e\_i))+\frac{1}{2}\left(\sum\_{i=1}^p(W\_1(f\_i)+W\_2(f\_i))+\sum\_{i=1}^q(W\_1(g\_i)+W\_2(g\_i))\right). \end{align\*} That is, the average cost of the walk $(u\_1,\ldots,u\_k,\ldots,u\_1)$ and the walk $(v\_l,\ldots,v\_1,\ldots,v\_l)$ is no more than that of the walk $(u\_1,...,u\_k=v\_1,\ldots,v\_l)$. So the shortest walk must have the form shown in the first figure.

Now you can try every node as $t$ to compute the optimal walk from $u$ to $w$ to $v$. This is a polynomial-time algorithm.
> 1 votes

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


title: ETM Undecidability

text:
# Question
Title: ETM Undecidability
I'm having trouble convincing myself of the proof for the following theorem:

> $E\_{TM} = \\{\langle M\rangle\mid M$ is a TM and $L(M) = \emptyset\\}$ is undecidable.

I think I understand why we reduce $A\_{TM}$ to this problem, where $A\_{TM} = \\{\langle M, w\rangle\mid M$ is a TM and $M$ accepts $w\\}$, but here is where I get lost. We create a modified TM $M\_1$ such that:

> $M\_1=$ "On input $x$:
>
> 1. If $x\neq w$, reject.
> 2. If $x = w$, run $M$ on input $w$ and accept if $M$ does."

and consequently create a TM $S$ that decides $A\_{TM}$:

> $S=$ "On input $\langle M, w\rangle$, an encoding of a TM $M$ and a string $w$:
>
> 1. Use the description of $M$ and $w$ to construct the TM $M\_1$ just described.
> 2. Run $R$ on input $\langle M\_1\rangle$.
> 3. If $R$ accepts, reject; if $R$ rejects, accept."

My issue here lies with line 3 of TM $S$. If $R$ accepted, then we must have had $x = w$ and $L(M) = \emptyset$, and $S$ would have rejected. Likewise, if $R$ rejected, then we must have had $x\neq w$ (where $x$ could be any string but $w$). Yet $S$ would accept this, even though the 'goal' for $S$ was to accept string $w$. Can someone show me how to think about this correctly? It would be very much appreciated.

# Answer
> 2 votes
In answer to your question about line 3 of the description of $S$, let's first clarify things a bit: we assume there is a decider, $R$, for $E\_{TM}$ and we use this to build a decider, $S$, for $A\_{TM}$ (thus eventually establishing that such an $R$ is impossible).

With that out of the way, your question is about what happens when $R$ accepts $\langle M\_1\rangle$:

1. Since $R$ was assumed to be a decider for $E\_{TM}$, $R$ accepts $\langle M\_1\rangle$ if and only if $L(M\_1)=\varnothing$.
2. From the way $M\_1$ was constructed, that can happen only if $M$ doesn't accept $w$ (since $M\_1$ rejects everything else),
3. So $R$ will accept $\langle M\_1\rangle$ only if $\langle M, w\rangle\notin A\_{TM}$.

Similarly,

1. $R$ will reject $\langle M\_1\rangle$ iff $L(M\_1)\ne\varnothing$,
2. And that can only happen when $M$ accepts $w$,
3. And hence $R$ will reject $\langle M\_1\rangle$ only if $\langle M, w\rangle\in A\_{TM}$.

Finally, since $S$ was designed to do the opposite of what $R$ does, we've constructed a decider for $A\_{TM}$, which of course is a contradiction, so $E\_{TM}$ must be undecidable.

# Answer
> 1 votes
The approach is a little different from usual reduction is because $A\_{TM}$, the accepting language, is RE and $E\_{TM}$, the empty language, is co-RE.

Therefore we need to reduce $A\_{TM}$ instance to $E\_{TM}$ instance in such a way that

> $\langle M,w \rangle \in A\_{TM}$ iff $M\_1 \not\in E\_{TM}$

We construct $M\_1$ from $\langle M,w \rangle$ as follows:

> $M\_1$:
> Input: $x$
> If $x\neq w$ then reject
> else if $x=w$ then Run Universal TM on $\langle M,w \rangle$ and accept if $M$ accepts $w$ (i.e. output the answer of Universal TM).

Step 1 of the Turing Machine $S$ does exactly the reduction from $\langle M,w \rangle$ to $M\_1$.

We prove by contradiction that $E\_{TM}$ is undecidable. Assume $E\_{TM}$ is decidable by a Turing machine $R$. Then we can show that $A\_{TM}$ is decidable by reducing an instance $\langle M,w \rangle$ of $A\_{TM}$ to instance $M\_1$ of $E\_{TM}$, get an answer using $R$ on $M\_1$ and then flip the answer. But $A\_{TM}=L\_u$, the universal language, is undecidable. Hence by contradiction $E\_{TM}$ is undecidable.

Turing Machine $R$ is used (in OP's description) to tell that if there is a Turing Machine $R$ which decides $E\_{TM}$ then we can use it to decide $A\_{TM}$. And since we know that $A\_{TM}$ is undecidable, surely we can't have such an $R$ and therefore $E\_{TM}$ is undecidable too.

Turing machine $S$ (again in OP's description) is a machine that decides $E\_{TM}$ if there is an availability of Turing machine $R$ that decides $A\_{TM}$ by flipping the answer.

# Answer
> 0 votes
I think the issue might be in the difference between saying "M is the kind of machine that accepts $w$" and "I simulated M on w, and it accepted."

The decider $R$ does not run $M\_1$ on any particular input. $R$ just (somehow!) checks whether the language of $M\_1$ is empty or not.

We've defined $M\_1$ so that its language will be empty if and only if $M$ is a machine that rejects $w$. We did this by having $M^\prime$ reject all strings besides $w$ right away. Then it decides whether to accept $w$ by just copying whatever $M$ does. So, if $M$ rejects $w$, then $M^\prime$ is a machine that rejects everything. If $M$ accepts $w$, then $M^\prime$ is a machine that rejects everything except for $w$.

The machine $R$ is supposed to be able to tell whether a TM is the sort of machine that rejects everything. If that were possible, you could solve the acceptance problem. Given $M$ and $w$, construct the machine $M^\prime$ that copies $M$'s behavior on $w$ and rejects all other strings. Then $M^\prime$ is the type of machine that rejects all strings if and only if $M$ is the type of machine that accepts $w$.

The decider $S$ takes in $M$ and $w$ and produces $M^\prime$. It decides whether $M^\prime$ has an empty language, which immediately tells you whether $M$ rejects $w$. If $M^\prime$ has an empty language, then $M$ rejects $w$, so respond NO—M doesn't accept w. If $M^\prime$ turns out not to have an empty language, we know it has just one string in it— w, and that can only happen if w is in the language of $M$. Respond YES—M accepts $w$.

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


# Question
Title: Solve recurrence where the base case's time complexity is a function of the original input size
I'm trying to analyse the time complexity of the following algorithm for generating the power set:

```
 public static List<List<Integer>> generatePowerSet(List<Integer> inputSet) {
    List<List<Integer>> powerSet = new ArrayList<>();
    directedPowerSet(inputSet, 0, new ArrayList<Integer>(), powerSet);
    return powerSet;
  }

  private static void directedPowerSet(List<Integer> inputSet, int toBeSelected,
                                       List<Integer> selectedSoFar,
                                       List<List<Integer>> powerSet) {
    if (toBeSelected == inputSet.size()) {
      powerSet.add(new ArrayList<>(selectedSoFar));
      return;
    }
    selectedSoFar.add(inputSet.get(toBeSelected));
    directedPowerSet(inputSet, toBeSelected + 1, selectedSoFar, powerSet);
    selectedSoFar.remove(selectedSoFar.size() - 1);
    directedPowerSet(inputSet, toBeSelected + 1, selectedSoFar, powerSet);
  }

```

It generates the power set as a union of all subsets that include a particular element (`toBeSelected`) and those subsets that don't.

Let $n$ be the size of the sub list `[inputSet, inputSet.size()-1]` and let $N$ be the size of `inputSet` which never changes in subsequent recursive calls. The recurrence relation is

$T(n)=\begin{cases}\mathcal{O}(N) \mbox {, if n=0}\\2T(n-1)+\Theta(1)\end{cases}$

By analysing the recursion tree we can see that $T(n) = 2^n\*\mathcal{O}(N)+2^{n-1}+\ldots+1= \mathcal{O}(N2^n)$.

I'm a bit concerned about $N$ in the answer, some analyses that I've seen just say it's $\mathcal{O}(n2^n)$. My problem with it is that if we take $n$ as the size of the original input the recurrence doesn't make sense - $n$ doesn't change from call to call. If we take $n$ as the sub lists's size the we end up with $N$ in the base case's runtime, also $N$ is a constant, in which case is the base case in $\mathcal{O}(1)$ and the algorithm's time is just $\mathcal{O}(2^n)$? Doesn't make sense too. Should we consider $T$ as a function of two variables $T(N, n)$?

# Answer
You are right that in order to analyze the recurrence, you need to take two parameters into account: the original list size $N$, and the size of the sublist currently operated on $n$. In terms of these parameters, the running time is $\Theta(N2^n)$.

However, what we are really interested in is the running time of the algorithm when running on the entire list (in your snippet, the running time of the first procedure rather than the second procedure); the fact that the algorithm proceeds recursively is an implementation detail. In other words, when analyzing the algorithm, there is only one parameter, namely the input size $n$. Therefore we can safely identify $N$ and $n$ in the final formula, and conclude that the running time is $\Theta(n2^n)$, where $n$ is the input size.

Stated differently, our end goal is understanding the running time of the algorithm (your first procedure) as a function of the input size. This analysis involves analyzing a certain recursive procedure (your second procedure), whose analysis involves both the original input size and the current input size. The final conclusion is that if we run the recursive procedure on an array of size $n$, then its running time is $\Theta(n2^n)$, and this is what we care about. The more refined running time $\Theta(N2^n)$ only shows up as part of the analysis, but is not reflected in the final result.
> 1 votes

---
Tags: time-complexity, runtime-analysis, recurrence-relation, recursion
---


# Question
Title: Concise Way To Specify The Space Of All Python Programs Under A Certain Size And Running Time?
Given the grammar of the Python language, is there a concise way to specify the space of all possible (and correct) Python programs?

To avoid the underlying halting problem, the specification would include a user-definable maximum program size and running time. This concise specification could then be fed to another program, a search/optimization algorithm to be precise, as the domain to operate in. And yes, I'm aware of how intractable such a space would be.

I don't know much about computer science or language theory, so any help would be appreciated.

# Answer
You can't determine the running time of a generic program automatically, this is an undecidable problem similar to the Halting problem.

Maybe you can try to enumerate a very well defined subset of the possible codes up to certain size. But in order to be useful for an search/optimization algorithm (other than random search), this subset needs to be equipped with some sort of vicinity function. Moreover, this vicinity function should allow you to explore genuinely different programs. Preferably this function should form a connected space among all plausible programs in this subset, and have a short diameter so optimizer can succeed on the search. All that said, is pretty clear that the problem is far from being easy.

I read recently a very interesting post about applying genetic algorithm to produce brainfuck code to solve specific simple tasks. You can read it here. The post is from 2013, but there is no particular breakthrough in this area that I'm aware. This field is known as program-synthesis and there are a lot of teams working on it, most recently they are trying to use classic combinatorial algorithms boosted with deep learning to prune the search space.
> 1 votes

# Answer
I had a similar question once and thought that the K Framework would be a good place to start (I didn't pursue it).

From https://experts.illinois.edu/en/publications/specifying-languages-and-verifying-programs-with-k:

> The K framework is designed to allow implementing a variety of generic tools that can be used with any language defined in K, such as parsers, interpreters, symbolic execution engines, semantic debuggers, test-case generators, state-space explorers, model checkers, and even deductive program verifiers.

There is a Python implementation:

https://github.com/kframework/python-semantics
> 0 votes

---
Tags: computability, enumeration
---


# Question
Title: How to estimate the average time complexity of greatest common divisor?
As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$.

Formally, let $f(x)$ be the number of divisions when calculating $\gcd(x,n)$. How to give a bound of $\frac 1 n \sum\_{x=1}^n f(x)$?

I don't konw whether it is strictly $o(\log n)$ or $\Theta(\log n)$. How to prove the bound?

I list some of $n$ and the coresponding value here.

$n$ ; $\frac 1 n \sum\_{x=1}^n f(x)$
1000;6.42;
10000;8.34;
100000;10.26;
1000000;12.20;
10000000;14.13;
100000000;16.07;

# Answer
> 1 votes
If you start wit a pair (a, b), a\>=b, one step goes to (b,a’) with a’ \< a/2. This gives an easy upper bound for the number is steps. You can analyse two steps from (a, b) to (a’, b,’) and get a slightly better upper bound.

For a lower bound for the highest number of steps, if a and b are the n-th an (n-1)-st Fibonacci number, then you will go through pairs of Fibonacci numbers and take n steps.

# Answer
> 0 votes
Since $n\geq x$ in your sum, $O(\log\min(x,n))$ simplifies to $O(\log x)$. Being very careless with constants here, but $$\frac{1}{n}\sum\limits\_{x=1}^n f(x)=\frac{1}{n}\left(n\cdot O(\log n)\right)=O(\log n)$$

I'm not sure what this is calculating though; average runtime of all input sizes less than $n$?

---
Tags: time-complexity, number-theory, average-case
---


# Question
Title: Meaning of "approximation within $n^{1−\epsilon}$"
I am not sure I understand correctly the following assertion (source):

> For all $\epsilon \> 0$, approximating the chromatic number within $n^{1−\epsilon}$ is NP-hard.

Does this mean that, for any given graph G, it is NP-hard to decide whether G is $k$-colorable with $k\<n$ given colors?

Otherwise, could you explain it in layman terms? Thanks!

# Answer
It is unfortunate that papers in hardness of approximation use this kind of phrasing, since it is rather inaccurate. Here is what the paper actually proves (see the proof of Theorem 1.2 on page 118):

> For every $\epsilon \> 0$ and any language $L$ in NP there is a polytime reduction $f$, whose output is a graph on $n$ vertices, such that:
>
> * If $x \in L$ then $f(x)$ has chromatic number at most $n^\epsilon$.
> * If $x \notin L$ then $f(x)$ has chromatic number at least $n^{1-\epsilon}$.

(This actually corresponds to a factor of $n^{1-2\epsilon}$, but since $\epsilon$ is arbitrary, it makes no difference.)

---

A different way to express this is using *promise problems*. A promise problem $L = (L\_+,L\_-)$ consists of two disjoint sets $L\_+,L\_-$, which we think of as Yes instances and No instances. Every language $L$ naturally corresponds to the promise problem $(L,\overline{L})$.

A promise problem $L = (L\_+,L\_-)$ is in NP if there exists a nondeterministic polytime algorithm $f$ such that if $x \in L\_+$ then $f(x) = 1$, and if $x \notin L\_-$ then $f(x) = 0$. Equivalently, there is a polytime algorithm $f$ and a polynomial bound $p$ such that:

* If $x \in L\_+$ then there exists $y$ of length at most $p(|x|)$ such that $f(x,y) = 1$.
* If $x \in L\_-$ then for all $y$ of length at most $p(|x|)$, we have $f(x,y) = 0$.

A promise problem $L = (L\_+,L\_-)$ is NP-hard if for any promise problem $L' = (L'\_+,L'\_-)$ in NP there is a polytime reduction $f$ such that:

* If $x \in L'\_+$ then $f(x) \in L\_+$.
* If $x \in L'\_-$ then $f(x) \in L\_-$.

A promise problem is NP-complete if it is both in NP and NP-hard. What the paper shows is that for every $\epsilon \> 0$, the following promise problem $L\_\epsilon = (L\_{\epsilon,+},L\_{\epsilon,-})$ is NP-hard, and so NP-complete:

* $L\_{\epsilon,+}$ consists of all graphs on $n$ vertices whose chromatic number is at most $n^\epsilon$.
* $L\_{\epsilon,-}$ consists of all graphs on $n$ vertices whose chromatic number is at least $n^{1-\epsilon}$.

---

There is one more way to formulate the inapproximability result, more vaguely:

> If there exists $\epsilon \> 0$ and a polynomial time algorithm for computing the chromatic number whose approximation ratio is at most $n^{1-\epsilon}$ then P=NP.

Here an algorithm for computing the chromatic number has approximation ratio $\rho(n)$ if for graphs on $n$ vertices, it outputs a number which is between $\chi$ and $\rho(n) \cdot \chi$, where $\chi$ is the chromatic number.

This statement can be derived from the statements above, but not vice versa.
> 5 votes

---
Tags: approximation, colorings
---


# Question
Title: Irregularity of $\{a^p : p \text{ prime}\}$ using Myhill–Nerode
Consider the language $$ L = \\{2^k : k \text{ is prime}\\}. $$ This language contains, for example, $2^3=222$, $2^5=22222$, $2^7=2222222$, and so on.

I know that $L$ is irregular and so there must exist a set of strings that are pairwise distinguishable with respect to $L$, but I'm struggling to come up with such a set of strings. Any help would be appreciated!

# Answer
> 3 votes
You can choose $2^\*$ as your set of words. Indeed, consider the words $2^a,2^b$, where $a \< b$. If these words are indistinguishable then for all $c \geq 0$, $a + c$ is prime iff $b + c$ is prime. Since there are infinitely many primes, we can find a prime $p \geq a$. Let $c\_1 = p-a$. Since $p$ is prime, so is $b + c\_1 = p + (b-a)$. Choosing $c\_2 = p-a+(b-a)$, we similarly get that $b + c\_2 = p + 2(b-a)$ is prime. Continuing in this fashion, we see that $p + k(b-a)$ is prime for all $k \geq 0$. In particular, $p + p(b-a)$ should be prime. But $p + p(b-a) = p(b-a+1)$ clearly isn't prime. This contradiction shows that $2^a,2^b$ are distinguishable.

# Answer
> 2 votes
Take the sets 2^p where p is prime and the gap between p and the next larger prime is some number g fixed for that set. Sets with different g can be distinguished, and gaps between consecutive primes become arbitrary large.

This applies when you don’t take primes, but numbers f(n) where f(n) / n goes towards infinity. Trivial cases would be squares, cubes, factorials etc. instead of primes. Or any subsets of these.

---
Tags: regular-languages
---


# Question
Title: Showing Turing machines are more computationally powerful than Finite State Machines
I've been pondering on whether Finite State Machines, particularly Mealy machines, can describe any computable function as Turing machines do. However "Mealy-computability" does not seem to be a term Google likes, and the most I was able to find was an answer in a post of this website:

"Turing Machines have has more computational power than FSM. There are tasks which no FSM can do, but which Turing Machines can do."

Yet no proof as to why.

---

**What is an example of a computable function that cannot be expressed by means of Mealy machines?**

# Answer
A Mealy machine (and more generaly a subsequential transducer) is a FSM that preserves regularity, meaning that if $L$ is a regular language and $M$ is a Mealy machine, then $\varphi\_M(L)$ is regular.

A Turing machine can transform a regular language in a non-regular language. For example, it could turn $\\{a^n\mid n\geqslant 0\\}$ (which is regular) into $\\{a^nb^n\mid n\geqslant 0\\}$ (which is well-known as a non-regular language).
> 1 votes

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


title: modify dfs to find longest path

text:
# Question
Title: modify dfs to find longest path
Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v\_d$.

For each vertex $v \in V$, we need to store in $v\_d$ the length of the longest path in $G$ that begins at $v$. The length of a path is given by the number of edges on this path.

How can i modify the above algorithm to find the **u.dist value correctly for each node u.**

# Answer
> 0 votes
I'm not going to tell you the exact modifications you need to do to the pseudo-code, but here is the high-level idea, which also shows why the longest-path problem on DAGs can be solved with just a DFS visit.

Forget about the visit for a second and suppose that you somehow know a topological order of the vertices of the graph. Let this order be $v\_1, v\_2, \dots, v\_n$. Let $\ell(v\_i)$ be the length of the longest path starting from $v\_i$.

If $v\_i$ is a sink we clearly have $\ell(v\_i) = 0$. Otherwise: $$ \ell(v\_i) = 1 + \max\_{v\_j \\, : \\, (v\_i, v\_j) \in E} \ell(v\_j). $$

Notice that, due to our topological order, we necessarily have that $j\>i$ in the above formula. This means that we are always able to compute $\ell(v\_i)$ if we consider the vertices $v\_i$ in **reverse** topological order.

This is where the above dynamic-programming algorithm connects with the DFS visit: if you consider the order of the vertices induced by the ending times of DFS visit, you obtain a **reverse topological order** of $G$, which is exactly what you need. This means that you can compute $\ell(v\_i)$ just before the DFS visit on node $v\_i$ ends.

---
Tags: algorithms, graphs, graph-traversal, dag, depth-first-search
---


# Question
Title: Is there a name for this modification to the subset sum problem?
Let $S = \\{\\{x\_{1},y\_{1},z\_{1}\\},\\{x\_{2},y\_{2},z\_{2}\\}, \ldots, \\{x\_{n},y\_{n},z\_{n}\\}\\}$ and a target $t$. Let $S\_i$ be the subset list $\\{x\_{i},y\_{i},z\_{i}\\}$. Find a subset sum that sums to $t$ such that one and only one element is chosen from each subset list $S\_i$.

I can also imagine this is the same as finding the longest path from $s$ to some sink such that the path costs less than $t$, where the sum of the edges is the same as choosing from each subset list $S\_i$.

Is there a name for this problem? Thanks.

# Answer
> 1 votes
I've seen this described as a "a variant of sum of subsets problem" by Arya et al.

Your formulation reminds me of some work I did on the problem of phase identification in electricity networks (e.g. see p118 of my Thesis, p135 of the pdf). Perhaps the references there (from 193 onwards) would be helpful.

---
Tags: subset-sum
---


# Question
Title: Prove $\text{CorrectSuccintSolver} \in \mathbf{coNP}$
Define the following languages:

> $$ \text{SUCC-CVAL}=\\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C\_i(x)=1 \text{ where } C\_i \text{ is the i'th gate in } C(x) } \\} $$ $$ \text{CorrectSuccintSolver} = \\{C \\, | \\, \forall S,x,i\\,C(S,x,i)=1\Leftrightarrow (S,x,i)\in \text{SUCC-CVAL} \\} $$

I need to prove that $\text{CorrectSuccintSolver} \in \mathbf{coNP}$.

I have tried to far constructing a $\forall$ sentence with a polynomial-time TM $M$ that validates the correctness of the given input circuit $C$, such that $C\in\text{CorrectSuccintSolver} \textbf{ iff } \\, \forall S,x,i\ M(C,S,x,i)$.

We need to check if the circuit $C$ is correct. The machine $M$ uses the given input circuit $C$ to check whether $C$'s output on gate $i$ is **consistent** with $C$'s outputs for gates $j,k$ that are connected to gate $i$ (w.l.o.g., $i = j \text{ op } k$ where $\text{op}\in{\\{\wedge,\vee,\neg}\\}$).

I think that there is a problem in my solution (something is missing). In addition, I have few missing details. For example, how to find gates $i,j,k$ only from *succint* representation?

Please advise. Thank you.

# Answer
> 0 votes
Thanks to @ArturRiazanov for the help.

The following $\Pi\_1=\mathbf{coNP}$ sentence solves the problem: $$ C\in\text{CorrectSuccintSolver} \quad\textbf{ iff } \quad \forall S,x,i,j,k\ \[M(C,S,x,i,j,k)=1\] $$

> The TM $M(C,S,x,i,j,k)$: Using the input circuit $C$, checks the following:
>
> * If $i$ is an input gates, checks that the input is consistent with $x$.
> * If $i$ is a logical gate, check whether $C$'s output on gate $i$ is **consistent** with $C$'s outputs for gates $j,k$ that are connected to gate $i$ (w.l.o.g., $i = j \text{ op } k$ where $\text{op}\in{\\{\wedge,\vee,\neg}\\}$).

Assuming that the *succint circuit* $S$ on input $i,j,k\in\\{0,1\\}^{\log n}$, $\text{op}\in{\\{\wedge,\vee,\neg}\\}$ returns 1 iff $j,k$ are connected to $i$ and $i$ computes operation $\text{op}$.

If $C$ is consistent with all of the above, $C$ is correct succint solver as required.

---
Tags: complexity-theory, circuits, co-np
---


# Question
Title: Determine whether the system of equations is underdetermined or overdetermined
Suppose I have a set of $n$ equations (each equation can be linear or quadratic).

I want to determine whether the system is underdetermined or overdetermined. For example, $a\_1=2,a\_1=3$ is overdetermined since I already know $a\_1$ from the first equation, while $a\_1+a\_2+a\_3=1,a\_1^2+a\_2=5$ is underdetermined.

If I know which variables are presented in each equation, is it possible to tell whether the system is underdetermined or overdetermined?

For now I'm thinking about the following algorithm:

1. Determine the number of variables in each equation (let it be $m$).
2. Add weight $\frac{1}{m}$ to each variable presented.
3. After examining all equations the system is overdetermined when any weight is greater than two or sum of all weights is greater than $n$. It is underdetermined if any weight is less than one or sum of all weights is less than $n$.

For example, consider the above system $a\_1+a\_2+a\_3=1,a\_1^2+a\_2=5$.

First equation: $w\_{a\_1}=\frac{1}{3}$, $w\_{a\_2}=\frac{1}{3}$, $w\_{a\_3}=\frac{1}{3}$.

Second equation: $w\_{a\_2}=\frac{1}{2}$, $w\_{a\_2}=\frac{1}{2}$.

Total: $w\_{a\_1}=\frac{5}{6}$, $w\_{a\_2}=\frac{5}{6}$, $w\_{a\_3}=\frac{1}{3}$.

Thus, the system is underdetermined.

There are cases, that due to the above definition, the system can be both overdetermined and underdetermined: $a\_1=2,a\_1=3,a\_1+a\_2+a\_3=3$. We consider such equations overdetermined.

Are there any other ideas?

# Answer
If your system is linear, Gaussian elimination will tell you everything you want.

In contrast, given a system of quadratic equations, it is NP-hard to determine whether it has any solution. I'm not sure what is your definition of *overdetermined* and *underdetermined*, but the corresponding problems are likely also NP-hard, by reduction to the above-mentioned problem.

To see that this problem is indeed NP-hard, we show that quadratic equations can encode Boolean circuits. Suppose that we have a Boolean circuit on inputs $x\_1,\ldots,x\_n$ with output $r$. We will have equations $x\_i^2 = x\_i$ for all $i$, and for each gate $g$, the equation $g^2 = g$ together with:

* If $g = \lnot h$ then $g = 1-h$.
* If $g = a \land b$, the equations $g + G = a+b$ (where $G$ is a new variable), $G^2 = G$, and the two equations $g(1-a) = g(1-b) = 0$.
* If $g = a \lor b$, the equations $g + G = a+b$ (where $G$ is a new variable), $G^2 = G$, and the two equations $a(1-g) = b(1-g) = 0$.

If we add the equation $r = 1$, then every satisfying assignment for the circuit (that is, an assignment which causes the circuit to output $1$) lifts to a unique solution of the system, and these are the only solutions of the system. In particular, this gives a reduction from SAT to our problem.
> 2 votes

---
Tags: algorithms
---


title: A high-level call-by-reference question

text:
# Question
Title: A high-level call-by-reference question
First, let $H$ be a graph represented as an array of adjacency lists say. Next, let FindDegree$(H,y)$ be a standard subroutine that takes $H$ and a vertex $y$ in $H$ as input, and that returns the degree $d\_H(y)$ of $y$ in $H$ as output. I am writing pseudocode that does the following: The subroutine FindDegree$(H,y\_k)$; $k=1,\ldots, r$; is called by the pseudocode for $r$ arbitrary vertices $y\_1,\ldots, y\_r$ in $H$ \[the graph $H$ is the same for all $r$ calls however\]. I'd like to say that the total work done by these $r$ calls of FindDegree is only $O(|H|+\sum\_{k=1}^r d\_H(y))$ word steps as opposed to \[good grief\] $\theta(r|H|)$ word steps. Is this a reasonable assumption on my part? Does call-by-reference in say C support this? \[Here the $O$-notation is allowed to hide polylogarithmic factors in $|H|$.\]

As far as context, I am writing pseudocode that takes as input a large graph $H$, and that makes several calls to subroutines that each use, to put informally, only a small part of $H$ i.e., the structure of the neighborhood of a vertex in $H$.

# Answer
> 1 votes
What you say is correct. In fact the total time spent by all the `FindDegree` calls is $O(\sum\_{k=1}^r d\_H(y\_k))$ (the additional $O(|H|)$ time is probably spent by the rest of the algorithm to read the graph and store it into the array of adjacency lists).

You can do what you suggest in $C$ by passing a pointer to the array of lists (C doesn't have references). Besides, if loaded the graph into adjacency lists, don't you immediately know each vertex's degree (in constant time)? That's just the list size. Either you already have that information in your list implementation, or it can be easily maintained as satellite data.

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: Having a lot of trouble trying to reason the formal definition of Big O
My professor recently brushed over the formal definition of Big O:

To be completely honest even after him explaining it to a few different students we all seem to still not understand it at its core. The problems in comprehension mostly occurred with the following examples we went through:

So far my reasoning is as follows:

When you multiply a function's highest term by a constant, you get a new function that eventually surpasses the initial function at a given ***n***. He called this ***n*** a "witness" to the function ***O(g(n))***

How is this ***c*** term created/found? He mentioned bounds a couple of times but didn't really specify what bounds signify or how to find them/use them.

I think I just need a more solid foundation of the formal definition and how these examples back up the definition.

# Answer
> 1 votes
> How is this c term created/found?

Answer is individual to each example. Let's take Your first one $f(n)=n^2+3n$ and $g(n)=n^2$. We need constants to satisfy inequality $$n^2+3n \lt c \cdot n^2$$ simplification gives $n \gt \frac{3}{c-1}$. I hope you easily found infinity couples of $n\_0,c$ for which inequality is true.

Let me, also, help you with 3'd example assuming, that base of $\log$ is more $1$. Proving, that some function is $O(n\log n)$ doesn't mean, that it is not in $O(n)$. More: we have $O(n) \subset O(n\log n)$, so, each function from $O(n)$ is also in $O(n\log n)$.

To prove directly, that some function is not in some big-$O$, you need negation of definition $f(n)\in O(g(n)),n\to\infty$:

$$\forall c \>0, \forall n\_0\in\mathbb{N}, \exists n\>n\_0, f(n)\>c\cdot g(n) $$

Taking now $f(n)=n\log n+2n$ and $g(n)=n$ we need to prove $n\log n+2n\>c\cdot n$. After simplification we obtain $\log n \> c-2$. This inequality, in required conditions, comes from $\lim\log n=+\infty$.

# Answer
> 1 votes
Adding another note to the already great answers.

A source of possible confusion might be from the notation surrounding this concept. The equals sign used in the statement$\ f(x) = O(g(x))$ is not meant to indicate an equality relation but instead should be interpreted as set membership. There are plenty of explanations made by much more informed people than me, including this math stack exchange question and throughout various parts of this wikipedia article.

For a formalization of the concept read the beginning of this paper. To put it briefly though,$\ O(g)$ is a set of functions and $\ f(x) = O(g(x))$ should be interpreted as saying $\ f \in O(g)$. In the context with which you are learning about it,$\ O(g(x))$ can be intuitively thought of as a class of functions that share the property of having a growth rate that is equal to or less than$\ g(x)$.

# Answer
> 0 votes
Look no further than the picture you attached that say

> $f(n)$ is $O(g(n))$ if there exist two positive constants $c$ and $n\_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \> n\_0$.

That's the full formal definition and foundation for the O notation.

Sit down and prove that $n^2$ is not $O(n)$.

# Answer
> 0 votes
This is an addendum to the other answers, which are very good.

The formal definition is important, but intuition comes from concrete examples. If you think about *why* we use asymptotic notation for, say, the time that an algorithm takes to run in the worst case, it's because the *actual* time may depend on a bunch of factors not in your control, such as how good your compiler is, how many other programs are running on the same machine, CPU clock speed, etc.

When analysing the run-time of algorithms, the constant $c$ "comes from" all of that.

This isn't the only use for big-oh notation, of course; if you learn numeric analysis, it will be used for other purposes, such as truncating power series. But this is one of the most common that you will see.

You haven't gotten to little-oh notation, yet, but here's something that might help.

$f(n)$ is $O\left(g(n)\right)$ if *there exists* a $c$, such that there exists a $n\_0$, such that for all $n\>n\_0$, $f(n) \< c\cdot g(n)$

$f(n)$ is $o\left(g(n)\right)$ if *for all* $c$, there exists a $n\_0$, such that for all $n\>n\_0$, $f(n) \< c\cdot g(n)$

The difference between big-oh and little-oh is that with big-oh, the constant is chosen for you, and with little-oh, *you* choose the constant and therefore it can be as small as you like. (This is why when discussing little-oh notation, $c$ is often spelled $\varepsilon$.)

---
Tags: algorithms, algorithm-analysis, big-o-notation
---


# Question
Title: Independent set problem with given black box
I'm very new to P and NP complexity classes and reductions. I'm trying to solve this problem and I want to verify my solution and if it is wrong, understand why.

> Suppose that I'm given a polynomial time algorithm $A$ that takes a graph $G=(V,E)$ as input along with integer $k$ and outputs yes if there is an independent set of size atleast $k$, no otherwise. How can I use this algorithm to get an independent set of size atleast $k$ if it exist in polynomial time?

We have $A(G, k) = $ yes if and only if there is an independent set of size atleast $k$. This means if the output is yes, then there is an independent set of size exactly $k$. For a given set of nodes of size $k$, I can verify if it forms an independent set in $O(|E|k)$ time (iterate through the list of edges and ensure that not both ends of an edge lie in my set).

I already know from $A(G,k)$ that there is an independent set of size exactly $k$. Can I check all the subsets of size $k$ if they form an independent set and return the one that does?

There are $|V|\choose k $ $\< |V|^k$ subsets of size $k$. According to me, this way, I should be able to get my independent set in $O(|V|^k |E|k)$ which is still polynomial. Could you please tell me if this is correct?

Also, could someone please tell me why such hypothetical problems are discussed? For instance, I know independent set problem is NP Complete and it is suggested by my professor that designers should stop looking for a solution once a problem is proved NP Complete.

# Answer
> 0 votes
No, it is not. "Polynomial time" means "polynomial in the length of the input" (i.e., number of bits needed to represent the input). The length of the input is something like $|V|+|E|+\lg k$, not $|V| + |E| + k$ (assuming $k$ is represented in binary). The running time of your procedure is exponential in the length of $k$ (exponential in $\lg k$), so it is not polynomial time.

The implication of the exercise you're solving is that the task of "find an independent set" is about the same level of difficulty as "check whether an independent set is present (yes/no)" -- it's not much harder. Neither task is likely to have a polynomial time solution. There's not much point looking for an efficient algorithm for either task.

---
Tags: complexity-theory, optimization, np, decision-problem
---


title: Streaming interval cover algorithm

text:
# Question
Title: Streaming interval cover algorithm
I'm given a target integer range $\[x, y\]$ which needs to be covered $n$ times, and a stream of integer ranges $\[x\_i, y\_i\]$. I need an algorithm which consumes integer ranges from the stream and returns immediately after processing the first element which causes $\[x, y\]$ to be covered $n$ times.

Example:

The target range is $\[0, 5\]$, $n$ is $2$, and the stream contains the ranges $\[0, 2\]$, $\[1, 5\]$, $\[0, 0\]$, $\[3, 5\]$, $\[0, 2\]$. The algorithm should return after processing the 4th element $\[3, 5\]$, because the first four ranges are the minimum required to cover $\[0, 5\]$ twice.

My initial idea here is to process the stream one item at a time and keep track of three variables:

* `k`: The number of times the target range has already been covered using the items processed so far
* `uncovered`: The list of sub-ranges that need to be covered in order to finish the next covering of the target range
* `pending`: A queue of sub-ranges that have been cached and not yet processed.

For each element in the stream, we search `uncovered` to see if the element can cover any of the uncovered sub-ranges. If not, we add the element to `pending`. Otherwise, we cover as many uncovered sub-ranges as we can with the element, update `uncovered`, and add any "unused" portions of the element to `pending`.

Each time we complete a covering of the target range, we increment `k`, and then make one pass over `pending` in order to complete as much of the next covering as possible using the cached sub-ranges before continuing to consume new elements from the stream.

Is there a more optimal algorithm here? Or, are there tweaks / improvements to my algorithm that can be made in order to make it more efficient? For example, it's not quite clear to me how to search or update `uncovered` efficiently. Perhaps I can store the sub-ranges in a binary tree instead of a list?

# Answer
> 0 votes
I would suggest a different approach. I suggest building a data structure that maps from an integer $v$ to the number of times that $v$ has been covered by the intervals seen so far. You should be able to build this data structure easily using any balanced binary search tree, where the leaves are intervals that all map to the same number.

Then, when a new interval arrives, it is easy to update this data structure (you might need to split an existing leaf or two, and then increment the counters for the leaves covered by the new interval). In this way, you can process each incoming interval in $O(\log n)$ time, where $n$ is the number of intervals seen so far.

Also, at each step, you can check whether the interval $\[x,y\]$ has been covered the required number of times so far. This is probably easiest if you augment each internal node with the smaller of the numbers on its two children. These augmented values can be updated on-the-fly. Then checking whether $\[x,y\]$ has been covered the requisite number of times can be done in $O(1)$ time by checking the root of the tree. (I assume that your intervals don't contain any values outside $\[x,y\]$, so the root will correspond to $\[x,y\]$. If that is not the case, first replace each interval with its intersection with $\[x,y\]$, so that it doesn't contain anything outside $\[x,y\]$.)

---
Tags: algorithms, streaming-algorithm
---


# Question
Title: What happens if 2 processor try to access the same memory in one clock cycle?
Assume a parralled adder program:

```
CPU0:
ADD sum,eax;or
LOCK ADD sum,eax

CPU1:
ADD sum,eax;or
LOCK ADD sum,eax

```

If these 2 instructions are issued in the same clock cycle, and reach memory control unit/cache control module, how does it decide which one will be served first? If not using lock, it seems that `ADD` requires read&write, and the memory might be modified in between the latency of read&write.

If lock is asserted, will the other processor have to wait until the first one get served? And is this kind of wait similar like a cache miss?

# Answer
> 0 votes
It doesn’t decide which one is first, it decides that *one* goes first and *the other* goes second.

It’s tricky, but you can and must build hardware that handles the case of two lock requests at the same time. A simple method: If you have four cores, check whether core 0 has a lock request in cycle n, check core 1 in cycle n+1, check core 2 in cycle n+2, core 3 in cycle n+3, and back to core 0 in cycle n+4. So to that hardware, there can’t be “simultaneous” lock requests.

And obviously when the first CPU is given access, the second one has to wait. That’s the whole point. (Obviously the processor can try to do other work while waiting for the lock).

---
Tags: multi-tasking, assembly
---


# Question
Title: All possible sum of each array combination
Is there a name for this algorithm?

I have an array {1,2,3} and all my possible sums are

{1},{2},{3},{1+2},{1+3},{2+3}, {1+2+3} = {1},{2},{3},{4},{5},{6}

{1,1,2} =\> {1}, {2}, {3}, {4}

I tried to find another algorithm rather than brute-force combinations, is there any formal name for algorithm that solves this problem or any better implementation like using dynamic programming?

Constraints - array can have n positive integers, repeated or not

* input - array of integers
* output - array of every possible sum you could make with the input array

{1,1,2} - {1} {2} {3} {4}

{1,2,2} - {1} {2} {3} {4} {5}

# Answer
Sadly, the worst case scenario is exponential in time, no matter what algorithm you use.

To see why, consider the following set of numbers: $A:=\\{2^k \mid 0 \le k\le n\\}$. There are $n$ numbers in this set, each taking at most $n$ bits to represent. Hence the input is of size $m:=n^2$.

Now, notice that for any two subsets $S\_1,S\_2\subseteq A$, if $S\_1\neq S\_2$ then there must be some $i$ such that (without loss of generality) $2^i\in S\_1$ but $2^i\notin S\_2$.

We can think of the numbers in $A$ as binary numbers, and then $2^i$ will be the binary number with $1$ at the $i$'th spot and $0$ everywhere else. You can easily show that you cannot construct $2^i$ as a sum of numbers from $A\setminus \\{2^i\\}$ (try to prove this!), and in particular this means that for any subset of $A\setminus\\{2^i\\}$, the $i$'th bit in the summation will always be $0$ (again, show this!).

Since $2^i\notin S\_2$, then $S\_2\subseteq A\setminus\\{2^i\\}$ and therefore $s\_2:=\sum\_{x\in S\_2} x$ will have $0$ at the $i$'th spot in its binary representation. But $ s\_1:=\sum\_{x\in S\_1} x = 2^i + \sum\_{x\in S\_1\setminus \\{2^i\\}} x$.

Denote $s\_1':=\sum\_{x\in S\_1\setminus \\{2^i\\}} x$ and since $S\_1\setminus\\{2^i\\}\subseteq A\setminus\\{2^i\\}$ then the $i$'th bit at $s\_1'$ must be $0$.

Thus, the $i$'th bit at $s\_1$ has to be $1$, since it is a sum of $2^i$ with another number that has $0$ at the $i$'th bit.

But this means that $s\_1\neq s\_2$, since $s\_2$ had $0$ at the $i$'th bit!

Thus the summation operation must be a one-to-one (injective) function, and hence the number of different summations has to be at least the number os subsets of $A$ (and its not hard to show it actually equals that), which is $|P(A)|=2^{|A|}=2^n=2^\sqrt{m}$.

Thus the output in this case is of size at least $2^\sqrt{m}$ when the input was of size (in bits) $m$. One can even improve upon this bound to get that the output size in bits has to be $\Omega(2^{2\sqrt{m}})$, which is achieved by observing that all values in the output are distinct natural numbers.

---

Notice that this is result shows that any algorithm will have to "brute-force" in the specific case of this $A$.

That being said, one *can* construct a dynamic programming solution for this problem when we know that the size of the output (i.e, the number of different summations) is small. Say, the output has $k$ elements - then one can construct a dynamic programming solution with $O(n \cdot k)$:

* For any $1\le i\le n$, define $sum\_i$ to be the *sorted* array of all possible summations of the first $i$ items in $A$.
* To compute $sum\_{i+1}$, do the following:
    1. create a copy of $sum\_i$ called $sum'\_i$, and you will need to add $x\_i$ (the $i$'th element in $A$) to each of the values in $sum'\_i$.
    2. Now, merge $sum\_i$ and $sum'\_i$ together, **while removing any duplicates** (this step can take an additional $O(|sum\_i|+ |sum'\_i|)= O(k)$ time, if we use the merging algorithm from MergeSort).
    3. If we also add $k$ to the resulting array, it will be exactly $sum\_{i+1}$ (prove this!).

This will be computed $n$ times, for a total of $O(n\cdot k)$.
> 4 votes

# Answer
If you have n random real numbers, then there are $2^n$ possible and different sums. So you need $2^n$ operations

For something like your example, many small integers, you calculate all possible sums involving the first number, then the first two, etc. You will have many sums that are equal, so that saves time. And you will have complete ranges. For example “all integers from 12 to 17”. If the next number to add is 6, you get a range “all integers from 12 to 23” in constant time.
> 0 votes

---
Tags: algorithms, time-complexity, combinatorics
---


# Question
Title: How to calculate number of tuples in a page?
I have been working on this particular question since yesterday and I can seem to figure out how to solve it:

*Assume that your files are organised based on slotted page array which contains a header (8B) and slot references of 2B each. Insert in the text below the number of tuples that you believe can fit completely in a 10KB slotted page array for the relation of Publisher which defines two fields: PUB\_NAME: char(22) and website:char(32).*

I don't know if I'm missing something, however I originally thought that you need to add 8B + 2B + 2B + 22B + 32B = 66B and then divide it 10000B/66B = 151,515152 where I round it to 151B.

That is not the right answer, neither is 152 if I round it up.

I would appreciate it if I could get some guideance/help on how to solve it.

Thanks in advance!

# Answer
First why store the refernce twice. It saved 2 bytes. Second 10 KB is Not 10000, it is 10240.

So the result should be 160 flat

64B of meta data (8 + 2 + 22 + 32).
> 0 votes

---
Tags: storage
---


# Question
Title: What is the meaning of Sub_tm in this context?
Im working on a problem for a homework assignment in finite automata, but I'm having trouble conceptually grasping the problem in the first place.

Prove that the following is undecidable: $SUB\_{TM} = \\{\langle M\_1,M\_2 \rangle \mid L(M\_1) \subseteq L(M\_2)\\}$

I'm not sure what kind of Turing machine $SUB\_{TM}$ is even describing. Can anyone help me conceptually understand this problem or possibly give me any hints? I would of course cite this post in my homework submission. Thank you.

# Answer
$SUB\_{TM}$ is the **problem** (language) of deciding whether for two given turing machines $M\_1$ and $M\_2$, we have that $L(M\_1)\subseteq L(M\_2)$.

Your task is to show that this language is undecidable - there is no turing machine that decides $SUB\_{TM}$.
> 0 votes

---
Tags: finite-automata, undecidability
---


# Question
Title: Are sample memory access traces/dumps available, and where?
I am looking for a realistic physical memory access trace/dump of significant, but not insane, length (on the order of 1M accesses) for the purpose of cache simulation. Preferably for a 16-bit or 32-bit RAM. Preferably in Tarmac format. The actual architecture is irrelevant. Are such files publicly available, and if so, where can I find them? (Googling did not help.)

# Answer
> 1 votes
Incidentally, I found an answer to my question: `valgrind`, when instrumented with `lackey` tool, can capture reliable, though not perfect, traces. For example, here's how one saves the trace for `ls -l`:

```
$ valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l > trace.log

```

Hope it helps not just me but others as well.

---
Tags: cpu-cache, memory-hardware, simulation, memory-access
---


# Question
Title: Find equivalent LTL formula, without Y (Yesterday) operator. How can I handle first state?
The task is to find an equivalent LTL formula for $G(a \Rightarrow Yb)$, which doesn't contain the Y operator. My idea is to search for invalid path patterns with 2 $a$'s in a row, e.g. bbbbaab.

Therefore I'm thinking of $G(Xa \Rightarrow b)$, so whenever an $a$ occurs in the next state the the current state must be true for $b$. But I have a problem with the starting states. Consider a path starting with $a$, e.g. s3-\>s4-\>... this path would be false for the original formula (iv), since Yb is always false for the first state. But this exact state would be true for the formula $G(Xa \Rightarrow b)$.

How do I have to modify my formula to also cover the starting states correctly?

# Answer
Initial states are somewhat of an anomaly. A similar problem is encountered in the $X$ operator when you try to define LTL over finite words. That is, it somehow would have made more sense to define PLTL over computations that are "infinite on both sides".

So, being an anomaly, it is probably easiest to treat it as such, and just explicitly deal with the initial state, requiring the first state not to have $a$.

Thus, an equivalent formula would be $G(Xa\to b)\wedge \neg a$.
> 2 votes

# Answer
Considering those equivalences: $G \phi \sim \phi \wedge X G \phi$ and $f \to g \sim \neg f \vee g$

We obtain that: $G(a \to Yb) \sim (\neg a \vee Yb) \wedge X G(\neg a \vee Yb)$

Assuming that $Yb$ cannot be satisfied in the first state (state 0) (notice that this is a semantic option for operator Y) so $(\neg a \vee Yb)$ can be reduced to $\neg a$. Thus the whole formula can be reduced to $\neg a \wedge X G(\neg a \vee Yb)$

The latter formula tells us that $G(\neg a \vee Yb)$ must be satisfied in states 1. Hence $(\neg a \vee Yb)$ must be satisfied in any state whose index is $\geq 1$. Let $i \geq 1$. Satisfying $(\neg a \vee Yb)$ at state $i$ is equivalent to satisfy $b \vee X \neg a$ at state $i-1$ (which exists since $i \geq 1$). You can derive this by considering that when $i \geq 1$, $i \models \phi$ $\Leftrightarrow$ $i-1 \models X \phi$. In our case : $i \models ( \neg a \vee Yb)$ $\Leftrightarrow$ $i-1 \models X( \neg a \vee Yb) = X \neg a \vee X Yb = X \neg a \vee b$.

We conclude that satisfying $G( \neg a \vee Yb)$ from state 1 is the same than satisfying $G(b \vee X \neg a)$ from state 0.

Hence the equivalent requested formula is: $\neg a \wedge G(b \vee X \neg a)$

As $X \neg a \sim \neg X a$

This formula can also be written $\neg a \wedge G(Xa \to b)$ as already given in a previous answer above.
> 0 votes

---
Tags: model-checking, linear-temporal-logic
---


# Question
Title: What does c represent in Sipser's explanation of the modified post correspondence problem Introduction to the Theory of Computation book?
I'm supposed to perform actions corresponding to the different steps in Sipser's explanation of the Modified Post Correspondence Problem, but I'm not sure I understand the third step. The part I'm referring to is:

Part 3. For every $a, b, c ∈ Γ$ and every $q, r ∈ Q$ where $q$ != $q\_{reject}$,

if δ(q, a) = (r, b,L), put $\frac{cqa}{rcb}$ into P'.

What does c represent? Any other value besides a, b in Γ? So if I'm constructing a domino for every value that exists outside of that one?

# Answer
The domino simulates a move to the left. Initially the head of the TM is reading $a$. It will rewrite that cell into $b$. Note that $a,b\in\Gamma$ are fixed by the specific transition $\delta(q,a) = (r,b,L)$. Then the head moves left. We do not know the symbol on that new position, so we allow any $c\in \Gamma$ for that domino.
> 0 votes

---
Tags: turing-machines, finite-automata
---


# Question
Title: What Graph Algorithm can determine ideal distribution of items to travel the least amount of distance from any node?
I have a problem that's been bugging me, but I'm not sure what algorithm can solve it.

Alice has medicine that she needs to use as quickly as possible in case of an allergy attack. She wants to distribute $k$ number of medicines in caches throughout her house, but doesn't know what is the ideal distribution such that at any room (or node) in the house she would travel the least amount of distance.

For simplicity, we map her house into an undirected graph where the edges represent distance to travel from one node (representing a room) to another node. The nodes and edges cannot be altered, and are static.

For $0 \< k \< |V|$, what algorithm can determine the ideal placement of medicines such that the Alice travels least amount of distance possible from any room (node) as starting point?

# Answer
These kinds of problems are known as clustering problems. Given an undirected graph $G$, the distance between any two nodes can be defined as the shortest path length between the two nodes. Now, note that the shortest path distances form a metric space.

In the clustering problem, each node represents a client. And, the task is to open $k$ facilities (medicines in your case) at some nodes in the graph such that the transportation cost of all the clients to their closest facility is minimized. There are many ways to quantify the clustering cost, such as $k$-center, $k$-median, and $k$-means objectives. All these problems are $\mathsf{NP}$-hard.
> 2 votes

---
Tags: algorithms, graphs, minmax-algorithm
---


# Question
Title: How does ssl handshake secures TCP connection?
I will explain whatever I understand about SSL handshake or simply SSL.

1. First client sends hello to server
2. Server sends signed certificate with its public key.
3. Client checks if certificate is valid, if it looks valid it generates its own private key, encrypts with server's public key and send back to server.

After this I don't understand-:

> the server unlooks the data with it’s own private key, gets the client private key.

> the server uses the client’s private key to unlook the data part of the packets send by the client.

Source-:https://osamana.com/en/blog/securing-tcp-connections-with-ssltls/

I don't understand once client sends encrypted private key and server's public key to server. And I don't understand holistic view of how this secures TCP connection.

# Answer
> 0 votes
I don't know how it works because I've never implemented the algorithm myself. Basically, the algorithm is RSA from the NIST agency in the US (FIPS 186). From https://nvlpubs.nist.gov/nistpubs/specialpublications/nist.sp.800-175b.pdf, you can read:

> The RSA algorithm is approved for the generation and verification of digital signatures in FIPS 186\] and specified in PKCS 1 35 and ANS X9.31 36. FIPS 186 includes restrictions on the use of RSA to generate digital signatures, methods to generate RSA key pairs, and defines the key lengths to be used for secure interoperability.

In RSA, two keys are created. One that is private (which allows to decrypt the data) and one that is public (which allows to encrypt the data). This is known as asymmetric encryption.

The public key is sent to the client of the server. The client generates a symmetric key that is encrypted with the public key and sent back to the server. The server can thus decrypt the message with its private counterpart and then use symmetric encryption afterwards which is faster.

Meanwhile, authentication is another thing. In authentication, there is a root certificate in the web browser that is provided by the certificate authority (like Let's Encrypt, GoDaddy and others). These certificate authorities derive other keys (public keys) from that certificate and this allows to verify the authenticity of the public keys of the clients of that certain certificate authority.

For example, if I'm a client of Let's Encrypt and get a certificate from them. I derive my public key from the certificate they give me. Then, when I send this key, the web browser verifies that it's a genuine key by verifying it against the root certificate stored somewhere on your filesystem.

This allows to ensure that you get a strong warning message if you are attacked on your network with attacks such as man-in-the-middle using ARP spoofing (which is common and practical). For example, if you go on your bank account and get this warning message then don't go further and verify your network.

# Answer
> 0 votes
that article is not technically correct.

(1) TLS handshake itself does not make your connection secure, what makes it secure is what happens after the handshake. Handshake is needed to negotiate parameters, necessary to establish secure communication.

(2) After connection establishment, TLS essentially does two things: encrypts the data \[confidentiality\] and computes message authentication code (which is secure version of hash function), which is used to detect tampering with data \[integrity\] *(note, contrary to what the article you link said, in Internet you cannot prevent anybody from changing your packets on the way. Integrity allows you to detect if packet was tampered with, and act accordingly)*. So, to answer your question, connection becomes secure because the content of the packet is encrypted and can only be decrypted by the other communication partner. The other partner can also verify that the packet was not tampered with on the way.

(3) Both encryption and message authentication codes (MAC) requires that client and server know corresponding keys (encryption key and key used to compute the MAC).

(4) There are basically two kinds of encryption schemes: symmetric encryption schemes and assymetric (or public key) encryption. Symmetric encryption requires the same key to both encrypt and decrypt the message, and this key needs to be known to both communication parties. This is usually referred to just key. Assymetic encryption uses two keys: public key to encrypt and secret key or private key to decrypt. Public keys are, well, public, in that you can just publish it. This way everybody can send you an encrypted message and be sure (well, in cryptographic terms) that you will be the only person who can decrypt and read it.

In order for two parties to communicate encrypted messages they can either communicate with symmetric cryptography, while somehow exchanging the key beforehand or with assymetric cryptography, where each party publishes its public key and the other party uses this key to encrypt the message to the other party.

The issue is that the existing algorithms for public key crypto are couple orders of magnitude slower than for symmetric crypto. This is why the common solution is to use public cryptography to exchange the symmetric keys and then use symmetric encryption for the actual payload. Exchanging symmetric keys is what handshake is accomplishing.

*Note however: I believe that the prase "cliend generates private key" actually means that the client generates a symmetric key and sends it to the server. If you are talking about public key crypto, private keys are NEVER sent anywhere. Also, this is also technically incorrect. Due to some specific attacks on the handshake, and other properties, the secret key is generated from data generated by both the client and the server in a quite complicated procedure. The main point is that as a result of TLS handshake, both the client and the server can compute secret keys used to encrypt and integrity-check payload later.*

(5) as explained in the other answer certificates are used for a different thing, called authentication. The idea is that the server gets an equivalent of a notary to sign him a ID, so that when the client connects to the server it can be sure that it indeed talks to the right server (its a network, there are ways somewhone can reroute client's packets not to the server, the cliend is intended to connect to). Well, how secure this is is a long story, so its a good idea to check the certificate before you insert your credit card data.

(6) P.S. there are also two ways to accertain message integrity: digital signatures which are public key schemes and message authentication codes, which are symmetric schemes. Digital signatures are basically inverse of the encryption, one signs with their private key, and everyone else can verify the signature with the public key, and be sure that the person who knows private key was the one who signed the message, and also that the message is not tampered with. Message authentication codes use symmetric key, so you can be sure that the other person who computed the code, also knows the key. Assuming that only your communication partner and you know the key, you can be sure that the code was created by your communication partner and thus the message was not tampered with by someone else. TLS use symmetric codes, and the key is computed based on data, exchanged during handshake. Digital signatures are used in certificates.

---
Tags: computer-networks, tcp
---


# Question
Title: Queuing delay in packet switched network
So I was going through the exercises in the '**Kurose and Ross**' book.

Suppose users share a 2 Mbps link. Also, suppose each user transmits continuously at 1 Mbps when transmitting, but each user transmits only 20 percent of the time. Suppose packet switching is used. Why will there be essentially no queuing delay before the link if two or fewer users transmit at the same time? Why will there be a queuing delay if three users transmit at the same time?

The solution says that there won't be any queuing delay since the output link has a 2Mbps bandwidth. But if both the user is sending the packet simultaneously,won't there be a delay to the second packet that arrived. Suppose 1Mb packet is sent at the same time from the two sources, then the second packet will suffer a 0.5s queuing delay right? That's what I understood and please correct me if I'm wrong.

# Answer
you are absolutely right, if two packets arrive simultaneously, then one of the packets will have to wait for the other one to be sent. Actually, queues are there in the first place, because in a packet switched network this is likely to happen.

I don't think, that this situation is generally referred to as having a queue. Since in packet switched networks (as opposite to cirquit switched networks) this situation is sort of artifact of the design, such short term queue which happens because packets are arriving at once and where all packets are removed from the queue shortly after are expected to happen. They are referred to as temporary bursts, or maybe temporary queue or short term queues. When we talk about queues, we usually talk about queues that build up and persist over "longer" period of time (without the proper definition of longer), because these queues arise when senders are sending too much data (also known as persistent queue). Because usually this is what needs to be avoided. If there is a permanent queue on the interface, then all traffic passing though this interface takes longer to deliver, and we usually do not want extra latency.

P.S.. In "best effort" delivery model, your application, is supposed to deal with the fact that there can be short term queues, because a burst of packets can arrive simultaneously. If you consider "textbook" applications, like file transfer, they are indeed not a problem. I am not sure how it is for the web, but should also not be that big of a deal. There are applications that do not deal with these bursts: almost all real-time multimedia (video-conferences, online streaming), and they require special support from the network devices in order to avoid this. However, the queue of one packet is unavoidable, as once sending of the packet has started, it is usually not interrupted. There is a different class of networks - real-time, where this one-packet latency is a problem, and they require even more complicated logic to avoid it.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: How does LALR(1) parser behave compared to LR(1) paser?
In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads:

> "The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... The error will eventually be caught; in fact, it will be caught before any more input symbols are shifted."

I understand an LR(1) parsing table can be revised to an LALR(1) parsing table by combing states. However, I don't quite understand (for an LALR(1) grammar),

* Why does the revised parser LALR(1) behave the same with the original LR(1)?
* Why will the wrong reduce step in LALR(1) (relative to LR(1)) be caught before any more input symbols are shifted?

# Answer
The explanation is given in the following paragraphs. Given a correct input, the LALR parser produces exactly the same sequence of reduce and shift actions as would an LR parser for the same grammar. On an incorrect input, the LALR parser produces the same sequence of actions up to the last shift action, although it might then do a few more reduce actions before reporting the error. So although the LALR parser has fewer states, its *behaviour* is identical for correct inputs, and extremely similar for incorrect inputs.

The shift error will be caught at exactly the same input point as with the LR parser because the shift actions are precisely the same between the two parsers, which is why the LALR construction cannot introduce a shift-reduce conflict which was not produced by the LR algorithm. A shift of a terminal $A$ can be done in any state whose itemset contains one or more items with the • marker just before $A$. The LR→LALR state merge only merges states with the same itemsets --that is, it merges lookaheads, not itemsets-- so the shift actions available are the same in both state machines.

This is also true of the reduce actions, available if the • is at the end of a production in the itemset. But because lookaheads are taken into account, it's possible that an itemset has more than one reduction action in the LALR state machine. The fact that the lookahead set in the LALR state machine includes tokens merged from different states does not affect the set of tokens which can eventually be shifted; it just means that the LALR state machine will not realise that the token cannot be shifted until it reaches a state in which a reduction is no longer available.
> 2 votes

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


title: Quicksort for Strings

text:
# Question
Title: Quicksort for Strings
I am currently trying to study the Quicksort algorithm. I understand how it works for integers but can anyone explain how does Quicksort algorithm work with strings?

The reason for my confusion is that strings do not have values assigned to them and the Quicksort algorithm seems to be using values to arrange an array of numbers. Most of the websites I have visited do not seem to offer explanations on this and only focus more on the integer value sorts.

Thank you in advance

# Answer
> 2 votes
The quicksort algorithm, and all other comparison based algorithms, all sort the "data" (any kind of "data") if they are given a a function that can compare two data points.

In the specific case of integers - the comparison is intuitive. For strings - one might use the alphabetical ordering: for two strings $w\_1,w\_2$, we can say that $w\_1\<w\_2$ if $w\_1$ comes before $w\_2$ lexicographically speaking.

---
Tags: algorithms, strings, quicksort
---


# Question
Title: Why does the exact string matching brute force algorithm not compare index 1 of P with index 1 of S in the first round of the for?
In my ADS course we were given this pseudo code for the "**exact string matching brute force**" algorithm:

```
1 ESM-BF(P, S)
2   m = length(P), n = length(S)
3   k = 0    # number of matches
4   for j=1,...,n-m+1do
5      i=1
6      while i ≤ m and P[i] == S[j+i] do
7         i = i +1
8      if i == m+1 then
9         k=k+1
10   return k

```

Given the example pattern P = **ACGTACT**

and the example string S = ACGGTACGT**ACGTACT**

Note that indexing starts at 1.

I started to write down with pen and paper what would happen in the first 2 times the for is executed:

```
1 ESM-BF('ACGTACT', 'ACGGTACGTACGTACT')
2   m = 7
3   n = 16
4   for j = 1    # first round
5      i = 1
6      while 1 < 7 AND P[1] == S[1+1] # (--> 'A' == 'C' FALSE skip body)
7      if 1 == 7+1 # (FALSE skip body)
8   for j = 2 # second round in for loop
9      i = 1
10     while 1 < 7 AND P[1] == S[2+1] # (--> 'A' == 'G' FALSE skip body)
11     if 1 == 7+1 # (FALSE skip body)# back to next for
12   for j = 3 # third round in for loop
13     i = 1
14     while 1 < 7 AND P[1] == S[3+1] # (--> 'A' == 'G' FALSE skip body)
15     if 1 == 7+1 # (FALSE skip body)# back to next for

```

I see how it would eventually the right match once we reach S\[6\].

1. Why do we not start comparing P\[1\] with S\[1\]?
2. What would happen if the pattern P remained the same but the string was changed to: S = **ACGTACT**ACGGTACGT (- as far as I can understand the algo would just miss the match...)?

Our professor told us that the ESM-BF compares the letters one by one starting from position one in the pattern and string and encouraged us to do it with pen and paper.

I asked some colleagues if they k but they are also confused about it.

What am I missing?

In case I got typos I will add the original from the slides to exclude that I just wrote it down wrong for myself:

# Answer
> 0 votes
As rici pointed out the bug-free pseudo code is indeed:

```
1 ESM-BF(P, S)
2   m = length(P), n = length(S)
3   k = 0    # number of matches
4   for j=0,...,n-m do
5      i=1
6      while i ≤ m and P[i] == S[j+i] do
7         i = i +1
8      if i == m+1 then
9         k=k+1
10   return k

```

---
Tags: algorithms, exact-string-matching
---


# Question
Title: Ask for help to prove a inequality, thanks
Can anyone help to prove that $\sum\limits\_{i=0}^{k-2}\log\_2\left(\frac{n-i}{k-i-1}\right) \> cn$ for some constant $c\>0$? Here $k=\Big\[\frac{n}{2\log\_2 n}\Big\]$ and $\[x\]$ denotes the integer part of $x$, for example, x=5.2999, then $\[x\]=5$.

# Answer
Your sum is equal to $\log\_2 \binom{n}{k-1}$.

Let $\ell = k-1$. It is well-known that $(n/\ell)^\ell \leq \binom{n}{\ell} \leq (en/\ell)^\ell$, and so your sum is $\ell (\log(n/\ell) + O(1))$.

Now $\ell = \Theta(n/\log n)$ and $\log(n/\ell) = \log \Theta(\log n) = \Theta(\log\log n)$, so altogether your sum is $\Theta(n\log\log n/\log n)$.
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, algorithm-analysis, space-complexity
---


# Question
Title: Counting all subsequences constrained to a condition
I was trying to find all subsequences constrained to the following conditions:

1. remove element from the end.
2. remove element from the beginning.
3. remove element from both sides.

For example, given the sequence $(1,2,3,4)$ have subsequences $\\{(1,2,3,4), (1,2,3), (1,2), (1), (2,3,4), (2,3), (2), (3,4), (3), (4)\\}$. So, we have get total 10 subsequences.

**Attempt**: I was thinking of using combinators ${N}\choose{i}$, where $N$ is the length of subsequence in our case and $i$ is the limit boundary of subsequence that starts at $i=1$ and increase all the way to $N-1$. However, since jumps are not allowed, this approach does not seem valid as it will count subsequence like $(1,3,4)$ which is not allowed.

Can you think of an hint/approach based on combinators/permutations to solve this please if possible or this can only be solved iteratively (through for loops/recursion)?

# Answer
> 1 votes
If I understand it correctly, you are counting the number of continuous subsequences. Every continuous subsequence one-to-one corresponds to a pair of positions representing its start position and end position, so the total number is $\binom{N}{2}$.

---
Tags: algorithms, counting
---


# Question
Title: Efficient Network Clustering Algorithm for Million Node Networks
I am looking for a clustering algorithm that is scalable up to large sparse undirected, unweighted networks (10-40M nodes, 10-80M edges). The most important aspects I care about are scaling efficiency to this size network and maybe consistency/stability. I'm mostly interested in this as a way to try and understand the network in more detail. I'm open to many types of clustering (including overlapping clusters, etc.).

# Answer
The Louvain algorithm does just this, and it easily handles graphs of this size. It is implemented in most, if not all, graph libraries. In particular, Networkit provides a fast parallel implementation. If you are interested in clusters only, you may use a dedicated implementation like the generalized version documented in this paper.
> 3 votes

---
Tags: clustering, social-networks, network-analysis
---


title: Is log^2 (n) ∈ O(n) true?

text:
# Question
Title: Is log^2 (n) ∈ O(n) true?
I'm new to algorithm, and I am already overwhelmed with the term ∈ I really could use some good explanation.

# Answer
For your question in the title,$\ log(n)\in O(n)$ is true.

For what you seem to actually be looking for. The the "is element of" relation, denoted by $\in$, is not specific to algorithms and complexity theory, but is a concept from set theory that is used everywhere throughout pure and applied mathematics. Where$\ O(n)$ is a "set" of functions, the statement$\ log(n)\in O(n)$ is saying that $\ log(n)$ is one of the functions in this set.

For a great introduction to these concepts I would highly suggest *How to Prove It* by Daniel J Velleman for learning about set theory and then *Introduction to the Theory of Computation* by Michael Sipser to learn more about how these concepts are applied to the theory of computation.
> 1 votes

# Answer
Yes $(log(n))^k \in O(n)$ for any positive fixed $k$. In fact, for any fixed positive small $c$, you further have that $(log(n))^k \in O(n^c)$ for every fixed $k$. So even $(log(n))^{100} \in O(\sqrt{n})$, for example.
> 0 votes

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


# Question
Title: Shortest possible path between closest pair of specific nodes in a maze
Need to find the shortest distance between the closest pair of 'r' and 'b' nodes. You can traverse along '.' elements, but not 'o' elements. How can we do this in $O(MN)$ time? (M rows, N cols). $O(RMN)$ time would also be sufficient (R is numbers of 'r' nodes).

Below is an adopted version the Lee algorithm from here that uses BFS to find the shortest distance between a given a single source node and a single destination node in $O(MN)$ time.

Can I extend this framework for the problem at hand? Any ideas are much appreciated.

import sys
from collections import deque

# Below lists detail all four possible movements from a cell
row = [-1, 0, 0, 1]
col = [0, -1, 1, 0]

# Function to check if it is possible to go to position (row, col)
# from the current position. The function returns false if row, col
# is not a valid position or has a value 0 or already visited.
def isValid(mat, visited, row, col):
    return (row >= 0) and (row < len(mat)) and (col >= 0) and (col < len(mat[0])) \
           and mat[row][col] == '.' or mat[row][col] == 'r' or mat[row][col] == 'b' and not visited[row][col]

# Find the shortest possible route in a matrix `mat` from source `src` to
# destination `dest`
def findShortestPathLength(mat):
    src = (1, 1)
    (M, N) = (len(mat), len(mat[0]))
    dest = (M-2, N-2)
    # get source cell (i, j)
    i, j = src

    # get destination cell (x, y)
    x, y = dest

    # base case: invalid input
    if not mat or len(mat) == 0 or mat[i][j] == 'o' or mat[x][y] == 'o':
        return -1

    # construct a matrix to keep track of visited cells
    visited = [[False for x in range(N)] for y in range(M)]

    # create an empty queue
    q = deque()

    # mark the source cell as visited and enqueue the source node
    visited[i][j] = True

    # (i, j, dist) represents matrix cell coordinates, and their
    # minimum distance from the source
    q.append((i, j, 0))

    # stores length of the longest path from source to destination
    min_dist = sys.maxsize

    # loop till queue is empty
    while q:

        # dequeue front node and process it
        (i, j, dist) = q.popleft()

        # (i, j) represents a current cell, and `dist` stores its
        # minimum distance from the source

        # if the destination is found, update `min_dist` and stop
        if i == x and j == y:
            min_dist = dist
            break

        # check for all four possible movements from the current cell
        # and enqueue each valid movement
        for k in range(4):
            # check if it is possible to go to position
            # (i + row[k], j + col[k]) from current position
            if isValid(mat, visited, i + row[k], j + col[k]):
                # mark next cell as visited and enqueue it
                visited[i + row[k]][j + col[k]] = True
                q.append((i + row[k], j + col[k], dist + 1))
    if min_dist != sys.maxsize:
        return min_dist
    else:
        return sys.maxsize

mat = [
        ['o','o','o','o','o','o'],
        ['o','r','.','.','b','o'],
        ['o','r','.','.','b','o'],
        ['o','r','.','.','b','o'],
        ['o','o','o','o','o','o'],
    ]

print(findShortestPathLength(mat))

mat = [
        ['o','o','o','o','o'],
        ['o','r','o','o','o'],
        ['o','o','o','o','o'],
        ['o','o','o','b','o'],
        ['o','o','o','o','o'],
    ]

print(findShortestPathLength(mat))

mat = [
        ['o','o','o','o','o','o','o','o'],
        ['o','.','.','r','.','.','.','o'],
        ['o','o','o','o','o','o','.','o'],
        ['o','.','.','.','.','.','.','o'],
        ['o','.','o','o','o','o','o','o'],
        ['o','.','.','b','.','.','.','o'],
        ['o','o','o','o','o','o','o','o'],
    ]

print(findShortestPathLength(mat))

```
</code></pre>

# Answer
You can append all `'r'` nodes to the initial empty queue.

Instead of checking whether the front node is the single destination node, check whether the front node is in the set of all destination nodes.

With the two extensions above, the Lee algorithm will be able to find the shortest distance between the closest pair of 'r' and 'b' nodes in $O(MN)$ time.

---

Here is an implementation in Python. Instead of checking the front node, i.e., when the node is popped out of the queue, this implementation check each node when it was pushed into the queue. This minor change improves the performance slightly.

```
from collections import deque

def find_shortest_path_length(mat):
    """Return the length of the shortest route from an 'r' node to a 'b' node

    `mat` is a 2-dimensional list of nodes. There are four kinds of node. An 'r'
    node is a source node. A 'b' node is a destination node. A '.' node can
    be passed while a 'o' node is an obstructed node that cannot be passed.
    """
    m, n = len(mat), len(mat[0])
    visited = [[False] * n for row in range(m)]
    q = deque()
    destinations = set()

    def should_visit(row, col):
        """Return true if (row,col) is a valid position not processed yet"""
        return 0 <= row < m and 0 <= col < n and \
               mat[row][col] != 'o' and not visited[row][col]

    for r in range(m):
        for c in range(n):
            if mat[r][c] == 'r':
                q.append((r, c))
                visited[r][c] = True
            elif mat[r][c] == 'b':
                destinations.add((r, c))

    dist = 1  # the level in breadth-first-search.
    while q:
        for _ in range(len(q)):
            (r, c) = q.popleft()

            for (new_r, new_c) in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
                if should_visit(new_r, new_c):
                    if (new_r, new_c) in destinations:
                        return dist
                    q.append((new_r, new_c))
                    visited[new_r][new_c] = True
        dist += 1

    # The destinations can not be reached.
    return -1

```
> 1 votes

---
Tags: algorithms, graphs, data-structures, shortest-path
---


# Question
Title: Find two non-overlapping subarrays, with total sum equal to k
Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total length of the two subarrays that have total sum K.

Also, after I checked the biggest test cases that we got, N doesn't go above $10^4$ and K doesn't go above $10^6$ (but specific subarrays can have a sum way larger than that)

The algorithm implementation (using C++), must have a time complexity of at most `O(logN * N^2)`.

The only idea I've had that is better than `O(n^3)` is to find all possible contiguous subarrays and their sum (`O(N^2)` using a prefix sum array), then sort them by sum (`O(logN * N^2)`), and for each subarray I do a binary search to find the subarray that has the remaining sum (which is K - (sum of first subarray)).

While this idea has better time complexity than `O(n^3)`, its space complexity is pretty bad, because I have to save three arrays of size `N(N+1)/2`, and the C++ program ends up using 1-2 GB of RAM for large N (\>1000).

So my question is: Is there any way to solve the problem efficiently, without the need of the longer arrays?? Or is there any other way I can implement the idea above with C++ so that I don't use up so much memory?

Thanks

# Answer
Our professor gave us this solution, which has $O(N^2 + K)$ time complexity, and $O(N+K)$ space complexity (since for the biggest test cases $K$ is about $N^{1.5}$, it is as good as $O(N^2)$ for these upper bounds).

We start by initializing an array $Lengths$ of size $K$, every value set to $N+1$, and calculating a prefix-sum for the initial array. We also keep a variable $min$ for the final answer (initially set to $N+1$).

Then we iterate the initial array with an index $y$, starting from $N-1$ down to $0$. For each iteration we do the following:

1. We iterate the array with an index $z$ starting from $y+1$ up to $N$. For each subarray, we calculate its sum, and if its length is less than $Lengths\[sum\]$ (where sum is the one we just computed), we set $Lengths\[sum\]$ to $z-y$, the length of this subarray.
2. We iterate the array with an index $x$ starting from $0$ up to $y$. For each subarray, we calculate its sum, and if this subarray's length PLUS $Lengths\[K-sum\]$ is less than $min$, then we update $min$ with the new value.
> 1 votes

# Answer
**The following algorithm works but does not achieve the required time complexity of $O(n^2 \log n)$, since I misread the time constraint as just being subcubic.**

Let $a\_i$ be the $i$-th element in the array and $\varepsilon \> 0$ be an arbitrary small constant. Construct a prefix sum array (in time $O(n)$) and then, for each pair $i,j$ with $j-i \ge n^{1-\varepsilon}$ generate the tuple $(\sum\_{h=i}^j a\_h, i, j)$. This requires time $O(n^{1+\varepsilon})$.

Next, construct two sorted lists $L^+, L^-$ containing the above tuples. Both lists sort the tuples w.r.t. the first entry. Additionally, the first (resp. second) list breaks ties w.r.t. the second entry while the second list breaks ties w.r.t. the third entry. This requires time $O(n^{1+\varepsilon} \log n)$.

Next use your approach with a slight variation: guess the start position $i$ and the end position $j$ of the first subarray (there are $O(n^2)$ guesses). For each guess $(i,j)$:

* Compute the sum $S = \sum\_{h=i}^j a\_h$ (in constant time).
* Binary search $L^+$ and $L^-$ to decide whether there is a disjoint array of length at least $n^{1-\varepsilon}$ with sum $K - S$. If this is the case you are done.
* Otherwise exhaustively search all disjoint subarrays of length smaller than $n^{1-\varepsilon}$.

Overall this requires time $O(\log n + n^{1-\varepsilon}) = O(n^{1-\varepsilon})$ per guess and time $O(n^{3-\varepsilon})$ in total, which falls within the time requirements. The space requirement is only $O(n^{1+\epsilon})$.
> 1 votes

# Answer
Compute the sums of all subarrays ($O(n^2)$), sort all **distinct** sums ($O(n^2\log n)$), then find all pairs of sums that sum to $K$ ($O(n^2)$).

Note each sum may correspond to multiple subarrays. Given two sums that sum to $K$, you have to check for all pairs of subarrays corresponding to the two sums whether they overlap. To solve this, for each sum, pre-find the subarray with the leftmost end position and the subarray with the rightmost start position. You only need to store and check these two subarrays (also note to store a subarray, you only need to store its start position and end position).
> 1 votes

# Answer
Slight modification to other answers that may help:

1. Since one subarray must have a sum from 0 to K/2, and the other must have a sum from K/2 to K, only look at subarrays with a sum \<= K. This may help a lot, especially if K is much smaller than the total size of all array elements.
2. If K is large, but heuristically you expect only few solutions, pick a prime p and find solutions modulo p, picking p large enough so there are still few solutions, but small enough to reduce your memory requirements. Then check whether your solution modulo p is a solution of the original problem.
3. Once you found a solution with length M, only consider subarrays with fewer than M elements.
> 0 votes

# Answer
The restriction to non-negative values simplifies solving the problem drastically:
Once the sum has reached $K$, adding elements increases length, if not sum.

This reduces the number of subarrays to know from $O(n^2)$ (start and end) to $O(K^2)$ (length and subtotal).

If $K$ is not greater than zero, you dont even need to inspect the array.
Check if $K$ is the value of an element of the array upfront: With $0 \< K$, the combined length won't go below 1.

With a largish K and hell bent going lowest/$o(n^2)$ space, how about the following?

0. let $array$ be the input array of $n$ integral numbers no less than 0;
$best$, $left$ and $combined$ for the best pair known
the subtotal of the left subarray, its length and the combined length;
$length$ and $end$ arrays of $n$ candidate subarray lengths and ends, respectively
1. for $target$ from 0 to $K-1$
1.1. from index 0 up, for each subarray totaling $target$ of record brevity, keep length and end
1.2. next $target$ if none found
1.3. for each subarray $right$ with sum $K - target$ from the end of $array$
if sum of its length and the shortest one kept "to the left of $right$" $^\*$
bests $best$, update $best$
2. re-find the rightmost subarray with sum $K - best$ and length $combined - left$

$O(n)$ storage, $O(nK)$ time: $O(n^2 \log n)$ where $K \in O(n \log n)$

Exchange the roles of *subarray length* and and *target subtotal* for
$O(K)$ storage, $O(n^2)$ time

$^\*$ linear search from the end should do nicely, if the last index used is kept
> 0 votes

---
Tags: algorithms, time-complexity, space-complexity
---


# Question
Title: Changing a relation to become transitive
Given a binary relation $R$ on a finite set $S$, is there an efficient algorithm to transform $R$ to a transitive relation $R'$ by minimum number of addition or deletion of pairs $(x,y)$ to or from $R$ where $x,y \in S$?

# Answer
This problem (for symmetric relations) is in graph theoretic terms called Cluster Editing and is a well know NP-complete problem.

For digraphs, it had been studied under the name Transitivity Editing Weller, M., Komusiewicz, C., Niedermeier, R. and Uhlmann, J., 2012. On making directed graphs transitive. Journal of Computer and System Sciences, 78(2), pp.559-574. as pointed out by idmean in a comment below, and is not surprisingly NP-complete.
> 8 votes

---
Tags: algorithms, transitivity
---


# Question
Title: Optimal order to minimise time until first success
Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t\_i$ time to talk to and there is $p\_i$ probability to make the sale to that customer - you find out immediately at the end of the conversation with that customer whether they agree or not. You have no control over the $t\_i$ or $p\_i$ values but you choose in which order to call the customers. So, once you've chosen the order, you just call the customers one by one, each immediately after the last one, until you make the sale (can ignore the case where you never make the sale, as having negligible probability).

You want to minimise the expected/average amount of time until you succeed in your sale (you only need one sale).

I would like to find an algorithm to find that optimal ordering of the customers.

Here is what I thought about so far:

* Let $\sigma$ be a chosen order, i.e.a permutation of the $N$ indices. Let $I\_{\sigma(i)}$ be an indicator random variable signifying that you speak to the $i$-th customer in your ordering $\sigma$.

Then the random variable corresponding to the amount of time taken is $T(\sigma) = I\_{\sigma(1)}t\_{\sigma(1)} + I\_{\sigma(2)}t\_{\sigma(2)} + ... + I\_{\sigma(N)}t\_{\sigma(N)} $. Then, the average amount of time is $E(T(\sigma)) = E(I\_{\sigma(1)}t\_{\sigma(1)} + I\_{\sigma(2)}t\_{\sigma(2)} + ... + I\_{\sigma(N)}t\_{\sigma(N)}) = E(I\_{\sigma(1)})t\_{\sigma(1)} + E(I\_{\sigma(2)})t\_{\sigma(2)} + ... + E(I\_{\sigma(N)})t\_{\sigma(N)}$

$E(I\_{\sigma(i)})$ is the probability that you end up speaking with the $i$-th customer in the order, which is the probability that all preceding ones in the order fail, i.e. $E(I\_{\sigma(N)}) = (1 - p\_{\sigma(1)})(1 - p\_{\sigma(2)})...(1 - p\_{\sigma(i - 1)})$

So overall the expected time is $t\_{\sigma(1)} + (1 - p\_{\sigma(1)})t\_{\sigma(2)} + (1 - p\_{\sigma(1)})(1 - p\_{\sigma(2)})t\_{\sigma(3)} + ...$

So that at least gives the function we want to minimise.
* I thought of using dynamic programming, but onyl thought of ways to do it where I store the optimal ordering for each subset, of the $2^N$ subsets. I also thought of a kind of bubble sort where I start with some order and then try to swap two adjacent customers and see if that gives a better result, but that seems to me a greedy algorithm and not sure if woudl give the overall optimal result.

# Answer
We can assume that $p\_i \> 0$ for all $i$: if $p\_i = 0$, ask them last.

Consider a certain arrangement, where customer $j$ is contacted directly after customer $i$. What happens if we switch the order of $i$ and $j$? For a certain $\rho \ge 0$, we replace $$ \rho t\_i + \rho (1-p\_i) t\_j $$ with $$ \rho t\_j + \rho (1-p\_j) t\_i $$ in the sum. The difference between these two options (former minus latter) is $$ \Delta = \rho (p\_j t\_i - p\_i t\_j) = \rho p\_i p\_j \left( \frac{t\_i}{p\_i} - \frac{t\_j}{p\_j} \right). $$ This suggests the following greedy rule:

> Arrange the customers in nondecreasing order of $\displaystyle\frac{t\_i}{p\_i}$.

Remaining details left to you.
> 0 votes

---
Tags: algorithms, optimization, greedy-algorithms, ordering
---


title: FPT for Special Matching

text:
# Question
Title: FPT for Special Matching
> In Special Matching, we are given an undirected graph $G$, a function $w:E\rightarrow\mathbb{N}$, and an integer $k$. The objective is to decide whether $G$ contains a matching $M$ of size at least $k$ such that for every two edges $e , e' \in M$ then $w(e) \neq w(e')$.

I want to design a random Dynamic Programing that solves Special Matching at $O^\*(4^k)$ ie. $O(4^k \bullet n^{O(1)})$.

Hint: need to color the vertices with $2k$ colors and solve the assumption that all the vertices in the solution get different colors.

# Answer
> 1 votes
it's actually a very simple reduction to 3-set-packing. the solution can be found here: https://drops.dagstuhl.de/opus/volltexte/2017/8124/pdf/LIPIcs-MFCS-2017-71.pdf

---
Tags: dynamic-programming
---


# Question
Title: Real life examples of negative weight edges in graphs
I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. Data transfer rates cannot be negative. I am just blanking out while thinking of negative weight edges in graphs.

---

Can we have a list of say 6 or 7 real-life examples where negative weights make intuitive sense?

# Answer
> 35 votes
Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that into account when predicting range.

In a neural network, we can use negative weights to indicate that one neuron firing is inversely correlated with another neuron.

In a clustering network we can use negative edges to indicate that two points should certainly not belong together. This is also relevant in community detection.

In sports, you can use a directed edge from $a$ to $b$ to mean the likelihood that $a$ will win against $b$ when $a$ is home team. In *general*, when we have non-symmetric relationships, $a\to b$ is different from $b \to a$ and we can't necessarily encode negative numbers with reverse arcs. This is also relevant in finance where $a \to b$ can mean that $a$ either owes money or $b$ owes money. The direction of the arrow can mean who is responsible for the transaction to take place.

Attractive and repulsive forces are used both in graph drawing, but also in particle simulation and simulation of other dynamical systems. These are often undirected positive or negative edges. In simulation of fluids, you will also have negative values denoting different forms of pressures from one area to another.

# Answer
> 7 votes
In a social network. Where the source node is a person the target node is another person and the connection represents the preference the source has for the target. The sign representing the direction of the sentiment.

In quantitative finance where the nodes are securities and the connections are the correlation coefficients.

A few years ago I made a triangular arbitrage algorithm that used a signed metric to determine the transactional inefficiencies an agent is exposed to when they use currency A to buy some currency B. As the agent walks through the graph (they trade from one currency to the next) they keep track of the sum of the values from edges they've traversed, lets call this value s. Once they make it back to the node they started from, the final amount of money they finish with is equal to the amount they started with times s+1. The trick to making money is to find a cycle that leaves you with an s\>0. The metric I developed was designed in a way that walking the same cycle but in the opposite direction leaves you with -s.

# Answer
> 4 votes
Say you are traveling city to city and along the way, you can pick up cargo or a passenger or whatever and earn profit on some of the travel hops (there are a number of carpooling services online where people post their to/from/when needs and how much they are willing to pay). So building a graph of possible profits (and on legs without a carpool offer, there will just be a negative cost for gas) can give you a way to plan your cheapest (i.e. most profitable) way to cross the country.

# Answer
> 4 votes
Negative edge weights are important for abstract planning.

In a typical graph you might use for this, there are two specific properties that are important:

* The nodes represent possible states of a complex system that is being modeled.
* The graph is directed.

As a result, the graph is functionally a representation of a state machine.

In such a graph, each edge can then be weighted with a relative value of making the state transition that the edge represents as compared to a value of zero for maintaining the current state (though often the system being modeled will not let you maintain the current state). You can then use the resultant value of a path through the graph to compare it to other paths and decide on which sequence of steps to take.

The ‘classic’ application of this from computer science is writing a chess engine. In chess, each possible board state can be assigned a value for each of the two players indicating how advantageous it is. Once you have a way to assign those values, you can compare the difference between the current position and each possible derivative position to pick the ‘best’ move. This is, at their core, how a majority of ‘traditional’ chess engines work, though they vary in how they assign values to each position (and how many steps ahead they may look).

The same approach though can be used to plan utilization of almost any system you can model as a state machine, be it an abstract strategy game like chess, or a business plan, or even the process of assembling a car, which makes it exceedingly useful for many real-life applications.

# Answer
> 3 votes
Consider someone speedrunning a complex videogame, which we abstract to moving through a graph. While the run is measured in absolute time, they might want to use *relative* time for judging strategies: how much time a route gains or loses them relative to some baseline "par". Then negative edges would correspond to time saved, and positive edges to time lost.

# Answer
> 0 votes
How about an electricity network where the positivity/negativity of the weight indicates the direction of current flow.

---
Tags: algorithms, graphs, discrete-mathematics, weighted-graphs
---