# Question
Title: Translating Natural Language to LTL Formulae
I'm brand new to LTL and working on becoming better with LTL formulae. I've got two examples where I am unsure whether my LTL formula is correct.

I'm given the sentences, and my assumption is that $l$ is true:

1. $l$ is always false after $m$

LTL Translation: $G(m \to G(\neg l))$ i.e on all paths m implies on all paths not l

2. $l$ is false between $m$ and $n$

LTL Translation: $G((m \land Fn) \to \neg l \space Un)$ i.e on all paths m and finally n, implies not l until n

Is my thinking correct in the examples? Thanks for the help!

# Answer
> 0 votes
There is a kind of templates to translate common NLP patterns into LTL. https://matthewbdwyer.github.io/psp/patterns/ltl.html

Hope it helps :D.

---
Tags: logic, linear-temporal-logic
---


# Question
Title: Faster way to calculate number of passes needed for bubble sort
Is there is a faster way to calculate the **number of passes** (**not** the number of swaps) needed to complete the bubble sort than actually doing the sort (as demonstrated in the code)?

E.g.

1, 2, 3 -\> 1 pass

1, 3, 2 -\> 2 passes

3, 2, 1 -\> 2 passes

3, 1, 2, 4 -\> 2 passes

0, 4, 2, 6, 1, 5, 3, 7 -\> 4 passes

Code in Python:

```
def count_passes(A):
    cont = True
    i = 0
    length = len(A)
    passes = 0
    while cont and i < length - 1:
        cont = False
        for j in range(length - i - 1):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                cont = True
        i += 1
        passes += 1
    return passes

```

# Answer
You sort the array say with quick sort, but also keep track of which position which array element is moved to.

Bubblesort can move an element at most 1 position towards the start of the array in each pass, not more. So you find in linear time the array element that was moved forward the most. The number of passes is the number of positions it is moved to the start, plus one for the last pass where nothing is moved.

And then you have to prove that in each pass, array elements at maximum distance from their final position at the front are indeed moved to the front, but that is easy.

Now if someone can post an answer for shakersort…
> 1 votes

# Answer
Python version of what I think gnasher729 described:

```
def compute_passes(A):
    n = len(A)
    I = sorted(range(n), key=A.__getitem__)
    return n and min(max(j - i for i, j in enumerate(I)) + 1, n - 1)

```

Tests with various lists (showing the kind of order, whether all results were correct, and the results)

```
ascend   True [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
descend  True [0, 0, 1, 2, 3, 4, 5, 6, 7, 8]
constant True [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
random   True [960, 968, 935, 987, 943, 982, 981, 947, 945, 970]

```

Whole code (Try it online!):

```
import random

def count_passes(A):
    cont = True
    i = 0
    length = len(A)
    passes = 0
    while cont and i < length - 1:
        cont = False
        for j in range(length - i - 1):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                cont = True
        i += 1
        passes += 1
    return passes

def compute_passes(A):
    n = len(A)
    I = sorted(range(n), key=A.__getitem__)
    return n and min(max(j - i for i, j in enumerate(I)) + 1, n - 1)

def test(label, As):
    counted = [count_passes(A[:]) for A in As]
    computed = [compute_passes(A[:]) for A in As]
    print(f'{label:8}', computed == counted, counted)

test('ascend', [list(range(n)) for n in range(10)])
test('descend', [list(reversed(range(n))) for n in range(10)])
test('constant', [[n] * n for n in range(10)])
n = 1000
test('random', [random.choices(range(n), k=n) for _ in range(10)])

```
> 1 votes

# Answer
As said by others, the number of passes equals the amplitude of the largest element displacement required. The displacement is the difference between the index and the rank of an element. Finding all ranks is... a sorting operation. I don't see a possible shortcut (but I cannot swear).
> 0 votes

---
Tags: sorting
---


# Question
Title: Having Moore's law is it worth looking for more algorithms?
knowing that Moore's law states that **is the observation that the number of transistors in a dense integrated circuit (IC) doubles about every two years.** is it worth looking for more algorithms?

# Answer
Yes.

1. Better algorithms, that run in less time complexity - work way better than just an increase in constant factor for large enough input, but more transistors is just a constant factor of work.
2. We have reached the "end" of this "law". Now we are in an era where its hard to make transistors smaller due to quantum effects on them.
3. Having newer and better algorithms will make programs run faster on **current** computers, and we wont have to always buy new ones.
4. Why not have both? more transistors + newer algorithms = even better performance!
> 1 votes

# Answer
The quest for new algorithms is unending. It is not just about solving the solved problems faster, it is about how to solve more problems.

By the way, improvements by a factor $2$ is peanuts. In extreme cases, algorithmic improvements allow you to gain factors like $2^{3000}$, for instance.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Spanning tree - minimum difference between smallest and largest weight
I am given an undirected, weighted graph $G$, on its base I have to create a spanning tree with such a property that the difference between the largest edge weight and the smallest edge weight is the smallest possible.

I know how to find a minimal spanning tree, e.g. using Prim's algorithm or Kruskal's algorithm, but I don't know how to find a tree satisfying the above condition. Is it enough to modify the MST algorithm in some way? Anyone have an idea how to approach this?

# Answer
> 4 votes
I realized that my answer is similar to **Steven**'s answer but maybe suitable for someone.

Based on increasing values of weights, sort the edges; e.g. $e\_1,...,e\_m$.

For $i=1,...,m-n+1$ (we need atleast $n-1$ edges to produce a spanning tree) produce an MST $T\_i$ on $e\_i,...,e\_m$ and calculate the difference $d\_i$ between the edge weight which is selected with maximum value and $w(e\_i)$. Note that, the edge $e\_i$ will be selected in produced MST, certainly.

Finally, select an MST $T\_i$ with minimum $d\_i$.

# Answer
> 4 votes
You can solve the problem in $O(m \log n)$ time. For the sake of simplicity assume that all edge weights are distinct (this assumption can be easily removed).

Let $e\_1, e\_2, \dots, e\_m$ be the edges in the input graph $G$ in increasing order of weight. Define $G\_i$ as the subgraph of $G$ induced by $\\{e\_i, \dots, e\_m\\}$, and let $k$ be the largest integer such that $G\_k$ spans $G$.

For every $i=1,\dots,k$ let $T\_i$ be a MST of $G\_i$ and call $M\_i$ the weight of the maximum-weight edge in $T\_i$. The problem is equivalent to returning a tree $T\_i$ minimizing $M\_i - w\_i$, where $w\_i$ is the weight of $e\_i$ (notice that $T\_i$ must include $e\_i$). This is because a MST minimizes the maximum-weight of the selected edges.

As a consequence of the above discussion, we can focus on finding the trees $T\_i$. We compute $T\_k$ explicitly and then, for $i=k-1, k-2, \dots, 1$ we find $T\_i$ by updating $T\_{i+1}$ as follows:

* Find the bottleneck edge $f\_i$ in the unique path $P\_i$ between the endvertices of $e\_i$ in $T\_{i+1}$, i.e., the edge of maximum weight in $P\_i$.
* Let $T\_{i}$ be the tree obtained from $T\_{i+1}$ by replacing $f$ with $e\_i$.

Notice that it is possible to maintain a tree under edge insertions, deletions, and bottleneck queries in $O(\log n)$ amortized time per operation. Similarly, we can keep the maximum edge weight in $T\_i$ updated in $O(\log n)$ time per iteration by storing the weights of the selected edges in a heap.

Overall the time spent is $O(m \log n)$, which also accounts for the time needed to sort the edges of $G$ and to find $T\_k$.

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


# Question
Title: Binary compression algorithm with decompress by index
I have a list of 256-bit binary data to store. Any algorithm for doing lossless compression on it in a way I can retrieve an entry by its index without decompressing the whole data (if possible). The decompressed data will also be stored as binary. I will also need to code this algorithm ground-up in a domain-specific language.

I'm trying to store 256-bit addresses in a blockchain smart-contract. I will need to later lookup addresses by index so, it'd be helpful if I can do that without full decompression.

Sample data with each entry pasted end to end here. I tried this site to compress using LSW and it seems I get a good reduction. Also here is another sample with each entry separated with line-break. The real data will contain from 2 to 65,000 entries.

# Answer
You can't compress blockchain addresses (in any blockchain I am familiar with), so this is a dead end.
> 1 votes

# Answer
Due to nature of data, just storing the data is better of than compressing it.
> 0 votes

---
Tags: algorithms, complexity-theory, data-structures, information-theory, data-compression
---


# Question
Title: Enumerating through Turing Machines That Solve Same Problem
Is it possible to enumerate through all the Turing Machines that solve the same given problem? For example, we know that there exists a Turing Machine that finds a satisfying assignment given a 3SAT formula. Therefore there are infinitely many 3SAT assignment finder Turing Machines. Could we enumerate all of them? Intuitively, I would expect to be able to find a function that maps natural numbers to 3SAT assignment finders as 3SAT assignment finders is just a subset of all Turing Machines, and the set of all Turing Machines is countable. However, could we compute this function that enumerates the problem solvers? Intuitively it feels like this should not be possible, but I am not sure.

# Answer
> 2 votes
Your question is, given a TM $M$, where $L(M) = L$, is it possible to create an enumerator $E\_L$ that enumerates every $TM \ M'$, such that $L(M') = L$

The answer to this interesting question is actually no, we prove this by contradiction

First consider the language $ATM = \\{\<M, w\>| M \ is \ a \ TM \ and \ M \ accepts \ w\\}$, which we know is undecidable

Our proof will show that if we can construct $E\_L$, then $A\_{TM}$ is decidable, hence a contradiction

Assume given $TM, M$, where $L(M) = L$ we can construct enumerator $E\_L$ enumerating every $TM \ M'$ such that $L(M') = L$

Now we will have two subroutines that we will run in parallel $A$ and $B$

Given $\<M,w\>$, $A$ halts if $w \in L(M)$, $B$ halts if $w \notin L(M)$, either one of them is the case, so eventually one halts and gives us the answer

First lets explain how $A$ works, given $M,w$, $A$ constructs a new machine $M\_w$ which recognises the language $L(M) \cup \\{w\\}$, $M\_w$ just checks if the input is $w$ if so it accepts, otherwise it simulates $M$, now we construct the enumerator $E\_{L\_{M\_w}}$ which enumerates every $TM$ recognising $L(M) \cup \\{w\\}$, now if $M$ already accepts $w$, then $L(M) \cup \\{w\\} = L(M)$, and so $E\_{L\_{M\_w}}$ eventually prints the description of $M$ and hence we halt and accept

Next lets go with $B$, given $M,w$, $B$ constructs an new machine $M\_{\bar w}$ which recognises the language $L(M) - \\{w\\}$, so $M\_{\bar w}$ just checks if the input is $w$, if so it rejects otherwise it simulates $M$, now we construct the enumerator $E\_{L\_{M\_{\bar w}}}$ which enumerates every $TM$ recognising $L(M) - \\{w\\}$, if $w \notin L(M)$, then $L(M) - \\{w\\} = L(M)$ and hence $E\_{L\_{M\_{\bar w}}}$ eventually prints the description of $M$ and hence we halt and reject

Again its important that we run both enumerators $E\_{L\_{M\_{w}}}$ and $E\_{L\_{M\_{\bar w}}}$ from $A$ and $B$ respectively in parallel to guarantee that we don't loop

Using this construction, we can show that $A\_{TM}$ is decidable yielding a contradiction, and hence we cannot construct such an Enumerator

---
Tags: complexity-theory, turing-machines, computability, enumeration, 3-sat
---


# Question
Title: Finding the constants in Landau notation
I am trying to find the constants $n\_0$ and $c$ to show that some given functions belong to the $O(\cdot)$ equivalence class. But, while it seems easy, I am not sure whether I am allowed to do what I will showcase below, or rather, what decides which constants I should take into consideration. For example:

$$n^{\frac 2 3} \in \Omega(\log^8n).$$

The definition is: $g(n) \in \Omega(f(n))$ if there exist $c,n\_0$ such that for all $n \> n\_0$, we have $cf(n) \leq g(n)$.

So, if I am asked to find the constants $n\_0$ and $c$, with nothing more asked (no extra conditions etc), how can I decide which values to consider?

# Answer
> 1 votes
The assertion can be proved without finding a particular value of $n\_0$, but by just proving there exists an $n\_0$ satisfying the desired conditions. More specifically, to show $n^{2/3}$ grows asymptotically faster than $(\log n)^8$, it suffices to show that $\lim\_{n \rightarrow \infty} \frac{n^{2/3}}{(\log n)^8} \ =\infty$, which can be shown by repeated application of L'Hospital's rule.

Suppose that $\lim\_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty$. By definition, this means the ratio $\frac{f(n)}{g(n)}$ grows without bound, i.e. for all $B \> 0$, $\frac{f(n)}{g(n)} \ge B$ for all sufficiently large $n$. In other words, for all $B \> 0$, there exists $n\_0 \> 0$ such that $\frac{f(n)}{g(n)} \ge B$ for all $n \ge n\_0$. In particular, taking $B=1$, we get that there exists $n\_0$ such that $f(n) \ge g(n)$ for all $n \ge n\_0$. This implies $f(n) = \Omega(g(n))$.

# Answer
> 0 votes
By solving for $n\_0$ and $c$ the system of inequations

$$\begin{cases}n\>n\_0,\\f(n)\>c\\,g(n).\end{cases}$$

Concretely, you can study the function $\dfrac{f(n)}{g(n)}$ and find a lower bound (f.i. the global minimum, or any gross approximation).

---
Tags: landau-notation
---


# Question
Title: How to move spheres in 3d without collision
Is there an algorithm that gets as an input 2 arrays (arr\_origin, arr\_dest) that represent spheres with a set radius (R) in a 3d space, (x,y,z) points. And finds a route for the spheres from origin to dest without collisions, in the fastest way given each sphere can move at a speed from 0 to V?

# Answer
Here's how I would do it: Create an oriented bounding box around the path of each sphere, with dimensions equal to the sphere's diameter. Now perform collision detection on all of those bounding boxes. For the ones which do not collide, their correlating sphere's can travel at max velocity. For the bounding boxes that DO collide, do they collide at a point equidistant to the spheres' starting points (+/- radii)? If not then they are free to move at max velocity. If they DO collide at an equidistant point(+/- radii), then you must slow one sphere down so that it will not collide.

Hope this helps. Good luck!
> 0 votes

# Answer
In the case of two spheres

* if the two straight-line trajectories do not interfere (in space-time), this is the optimal solution and the time taken is the length of the longest trajectory over the maximum speed;
* if they do interfere, there are several options:

+ let the two spheres travel in a straight line, and let the one with the shortest distance wait when it meets the other; more precisely, it can come in contact with it and remain so until the path is freed; note that if that would imply a backward move, the second sphere should anticipate and stop when it hits the envelope of the trajectory of the first (a cylindre);
    + let the sphere with the longest distance travel in a straight line and let the other deviate to avoid it, both at maximum speed; the modified trajectory will be made of two straight portions and some complex curve in between (to be determined by variation calculus ?);
    + keep both spheres at maximum speed and slow down both when they come in contact; there should be optimal relations between the speeds over time and the total time spent;
    + deviate both spheres optimally (?);
    + combine stalling and deviation in the best way.

This just gives you a taste of the problem complexity.
> 0 votes

---
Tags: algorithms
---


title: Comparing Registers with 16-bits

text:
# Question
Title: Comparing Registers with 16-bits
I am given with this information:

*"CMP OP1,OP2 will compare registers OP1 and OP2 if they are equal, flag values will be ZF=1, CF=0, if the first operands value is greater flag values will be ZF=0, CF=0, if the first operands value is less than the second operand flag values will be ZF=0,CF=1."*

I need to design instruction set architecture for this compare operation but I couldn't understand how to add ZF and CF values inside CMP instruction

# Answer
> 0 votes
It's not entirely clear to me what you need to design. You seem to have quoted a part of a description of a ready ISA.

In your description the CMP instruction takes two arguments, i.e. the two registers to be compared. The instruction sets two 1 bit registers or flags based on the outcome of the comparison. These flags don't have to be explicitly given to the CMP instruction because CMP always sets these same registers. After these flags have been set according to the comparison you can use a conditional jump instruction that uses these flags.

# Answer
> 0 votes
ZF and CF are computed by the instruction and stored in some "status register". They can later be used by conditional jumps. ZF is the "zero" flag and CF the "less than" flag. They can be obtained as a by-product of the subtraction of the two operands.

---
Tags: logic, memory-access, algorithm-design
---


title: Reduce $\sqrt{n}$-CLIQUE to CLIQUE

text:
# Question
Title: Reduce $\sqrt{n}$-CLIQUE to CLIQUE
Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices. Define CLIQUE as the decision problem

$$\\{ \langle G, c \rangle \mid G \text{ has a clique of size } c\\}$$

Define the problem $\sqrt{n}$-CLIQUE as follows:

$$\\{\langle G \rangle \mid G \text{ has a clique of at least size } \sqrt{n}\\}$$

where $n$ is the number of vertices of $G$. It is easy to reduce $\sqrt{n}$-CLIQUE to CLIQUE. How can we go the other way and thereby show that $\sqrt{n}$-CLIQUE is NP-complete?

---

Idea: If $c \geq \sqrt{n}$, we can add dummy vertices to $G$ until $c = \sqrt{n}$. What do we do if $c \< \sqrt{n}$? It seems we need to be able to remove vertices without disturbing the size of the largest clique. My idea in this case to remove a vertex if it has less than $c-1$ edges. Obviously the new graph has a clique of size $c$ if and only if the original graph does. But what happens if we can't remove enough vertices? Can we conclude that if a graph has $n \> c^2$ vertices each with degree $\geq c$ then a clique exists?

# Answer
> 6 votes
When $c \> \sqrt{n}$, you add an independent set of size $m$ so that $c = \sqrt{n+m}$ (i.e., you need $m = c^2-n$).

When $c \< \sqrt{n}$, try doing the same, increasing both $n$ and $c$ at the same time, by adding a *complement* of an independent set. (You might need to add a few isolated vertices as well.)

# Answer
> 1 votes
Below is a different reduction from CLIQUE to $\sqrt{n}$-CLIQUE which is essentially an extension of the reduction from CLIQUE to $\frac{n}{2}$-CLIQUE.

Given an instance $(G=(V,E),k)$ of CLIQUE, we construct an instance $G'=(V',E')$ of $\sqrt{n}$-CLIQUE as follows. Suppose $V=\\{v\_1,...,v\_n\\}$, then $G'$ is defined as follows $$V'=V\cup\\{u\_1,...,u\_{n-k}\\}\cup\\{w\_1,...,w\_{n^2-2n+k}\\}$$ $$E'=E\cup\\{\\{u\_i,u\_j\\}\mid \forall i,j\in\[n-k\]\\}\cup\\{\\{v\_{i},u\_j\\}\mid \forall i\in\[n\],\forall j\in\[n-k\]\\}$$ Intuitively, we are constructing $G'$ to have one copy of $G$ which is fully connected to a $K\_{n-k}$ clique, and we pad the number of vertices to $n^2$ using isolated vertices.

**Claim:** $(G=(V,E),k)\in$ CLIQUE if and only if $G'\in\sqrt{n}$-CLIQUE.

*proof.* $\Longrightarrow$ If $(G=(V,E),k)\in$ CLIQUE, then the copy of $G$ in $G'$ has a clique of size $\geq k$. Since $G$ in $G'$ is fully connected to $K\_{n-k}$, $G'$ will have a clique of size $\geq (n-k)+k=n$.

$\Longleftarrow$ If $G'\in\sqrt{n}$-CLIQUE, then suppose for contradiction that $G$ has all cliques of size $\<k$. This implies that $G'$ has all cliques of size $\<(n-k)+k=n$. A contradiction. Thus $G$ has a clique of size $\geq k$.

Finally, it is easy to construct $G'$ in poly$(n)$-time. So we are done.

---
Tags: complexity-theory, graphs, reductions, clique
---


# Question
Title: Minimum vertex cover with minimum overlap of one side
In a bipartite graph $(X+Y,E)$, it is possible to find a minimum vertex cover in polynomial time, by Konig's theorem.

Suppose the minimum size is $s$. Is there an efficient algorithm for finding a vertex cover $S$ of size $s$, such that $S\cap X$ has a minimum cardinality?

What I could do so far is to formulate this problem as an ILP where each vertex $u\in X$ has a variable $x\_u$ and each vertex $v\in Y$ has a variable $y\_v$. Its LP relaxation is:

\begin{align} \text{minimize} && \sum\_{u\in X} x\_u && \\ \text{subject to} && x\_u + y\_v \geq 1 && \forall (u,v)\in E \\ && \sum\_{u\in X} x\_u + \sum\_{v\in Y}y\_v = s \\ && 1\geq x\_{u}\geq 0, 1\geq y\_v \geq 0 && \forall u\in X, v\in Y \end{align}

But I do not know how to check whether this ILP has an integer solution.

Is there a better approach to this problem?

# Answer
Dulmage–Mendelsohn decomposition is a powerful tool to capture the structure of the bipartite graph, and it can be found by computing any maximum matching.

> Let $G = (V = (A, B), E)$ be a bipartite graph, then $G$ can be partitioned into three parts $(C, H, R)$ and we let :
>
> 1. $C \subseteq V$ is an independent set.
> 2. $N(C) = H$.
> 3. $G\[R\]$ has a perfect marching.
> 4. $H$ is the intersection of all the minimum vertex covers.
> 5. Any maximum-matching in $G$ saturates all vertices in $R \cup U$.

According to the Dulmage–Mendelsohn decomposition, $H$ must be in the solution, so $S = H \cup (A \cap R)$ is a vertex cover with a minimum overlap of $B$ such that $S \cap B = H \cap B \subseteq H$.

---

We can also solve this problem by using the maximum flow algorithm. Since the Vertex Cover in bipartite problem can be reduced to the minimum cut problem, this problem can be reduced to the minimum cut in the edge-weighted graphs.

Specially, we add a source node $s$ connecting every vertex in $A$ and add a sink node $t$ connecting every vertex in $B$. Suppose that $n = |V|$, the weight of every edge adjacent to the $s$ is $n$, and the weight of every edge adjacent to the $t$ is $n-1$. Besides the weight of the edge in the original graph is large enough such as $n^{2}$. Note that if the size of the minimum vertex cover in $G$ is $k$, we know that the minimum $s$-$t$ cut is in $((k-1)n, kn\]$.
> 1 votes

# Answer
Suppose that the minimum VCP size is s.

If $|Y|=s$ then the optimal solution (without solving any problem) is $Y=1$ and $X=0$.

Else, we can solve $min$ $W\_uX\_u+W\_vY\_v$ s.t. {$x\_u+y\_v\ge 1$, $0\le x\_u,y\_v \le 1$}; i.e. the original VCP relaxation model, where $W\_u=1$ and $W\_v=1-\epsilon$.

Based on Nemhauser and Trotter Theorem (1975), all extreme optimal solutions have values $V\_0=0$, $V\_{0.5}=0.5$ or $V\_1=1$ for their variables and always we have an optimal solution which is equal to the union of $V\_1$ and a subset of $V\_{0.5}$.

Therefore, in the optimal solution we have $z^\*\approx s$ and between all optimal solutions of original problem with size $s$, the priority of vertex selection of the model is from $Y$.

Then, in optimal solution of the proposed model, select $V\_1$ and then solve the problem on $V\_{0.5}$. Note that, if $V\_0=V\_1=\emptyset$ and $V\_{0.5}=V$, you can produce an adjacent optimal LP relaxation solution where $V\_{0.5}\ne V$.
> 0 votes

---
Tags: graphs
---


# Question
Title: Estimate the running time of a while-for-while loop
```
i, sq ← 1, 1
while sq < n
    for j ← 1 to sq
        k ← 1
        while k ≤ j
            k ← 2 ∗ k
    i ← i + 1
    sq ← i ∗ i

```

I have expressed the running time of the "for" loop as a sum in this way :

$$\sum\_{j=1}^{i^2} \log(j)$$

In a similar way, how can I express the running time of the outer "while" loop with sigma in terms of $i$ ? I have tried the following: $$\sum\_{i=1}^\sqrt{n} i^2\log(i)$$

# Answer
The outer most while loop ends when $\text{sq} = n$ and by definition $\text{sq} = i^2$ and thus it will run $i^2 = n \Rightarrow i = \sqrt{n}$ times ( as we increment $i$ by one each iteration).

Note that -
The for loop runs at $\log(j)$ from $1$ to $\text{sq} = i^2$ and $1 \leq i \leq \sqrt{n}$ so we have this sum:

$$\sum\_{k=1}^{i^2}\log(k) ~~ \forall i \in\\{1,2, \dots,\sqrt{n}\\}$$

Recall: $\log(a) + \log(b) = \log(a \cdot b)$
Some examples:
$i=1 \Rightarrow \sum\_{k=1}^{1}\log(k) \Rightarrow \log(1!)$
$i=2 \Rightarrow \log(4!)$
$i=3 \Rightarrow \log(9!)$
$i=4 \Rightarrow \sum\_{k=1}^{16}\log(k) = \log(1)+\log(2) + \dots + \log(16) \Rightarrow \log(16!) ~~~~~~ \\ \text{etc... until } i=\sqrt{n}$

And thus this whole system of loops runs at:

$$\sum\_{k=1}^{ \sqrt{n}}\log\[(k^2)!\] = \log{( \prod\_{k=1}^{\sqrt{n}}k^2! )}$$
This can be bounded by $O(\sqrt{n} \log(n!))$ or $O(n^{1.5} \log(n))$ by taking the largest element in that sum ( $\log(n!)$ ) and multiplying it by the number of elements ( $ \sqrt{n}$ )
> 1 votes

# Answer
The innermost loop runs $\lg(j)$ times.

The middle loop executes it for all $j$ from $1$ to $s$, hence $\displaystyle\sum\_{j=1}^{s}\lg(j)=\lg(s!)$.

The outer loop executes the latter for all perfect squares from $1$ to $n$, hence $\displaystyle\sum\_{k=1}^{\sqrt n}\lg((k^2)!)$.

Using Stirling, we can approximate with $\displaystyle\sum\_{k=1}^{\sqrt n}k^2(2\lg(k)-1)$, which is $\Theta(n^{3/2}\log(n))$, by integration.
> 1 votes

---
Tags: algorithms, time-complexity, summation
---


title: Bellman-Ford and zero-distance cycle

text:
# Question
Title: Bellman-Ford and zero-distance cycle
Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length cycle, and no negative-length cycles?

Background information: The question came up when I tried to implement in code the solution to what is called the "tramp steamer" problem: Given a graph G(V,E) in which each node is associated with a cost $c\_i$ and each edge is associated with a time (number of days) $t\_i$, find the cycle with the smallest ratio of cost to time $\frac{\sum\_i(c\_i)}{\sum\_i(t\_i)}$ (i.e. minimal cost/day cycle).

One solution is to do a binary search with the range of possible rations, trying to identify the minimum cost-to-time ratio $\mu$. In each iteration of the binary search in the range $\[left...right\]$, you "guess" a value of $\mu = \frac{left+right}{2}$ and then run Bellman-Ford:

* if a negative cycle exists then the value of $\mu$ is too high; the range is reset to $\[left...\mu\]$
* if all cycles are positive then the value of $\mu$ is too low; the range is reset to $\[\mu...right\]$
* if there is a zero-length cycle (with all other cycles being positive), then we have found the best value for $\mu$ and we can stop, returning the zero-length cycle as the answer

How exactly is the third case detected? Assume the graph A-\>B-\>C-\>D-\>{A,B} with two cycles (fro D back to A or B) where the cycle B-\>C-\>D-\>B is the optimal one and yields zero length for some selection of $\mu$ for which the other cycle is positive. Suppose we happen to try this particular value of $\mu$ (let's assume it's during the very first iteration because we got lucky). If I am using vertex A as the fixed point from which I run Bellman-Ford on each iteration, it will complete successfully without detecting a negative cycle. But how would the zero-length cycle be identified?

Currently I only handle the first 2 cases and my implementation keeps iterating until the $\[left...right\]$ range becomes becomes too small, so that floating point precision can't handle a smaller range. At that point I detect that $\frac{left+right}{2}$ is equal to one of the range limits (either left or right) and stop the binary search. How would I go about detecting that a particular value of $\mu$ has produced a zero-length cycle?

# Answer
Here's how you can detect whether a weighted graph $G$ contains a zero-length cycle, assuming it does not contain any negative cycle.

1. Run Bellman-Ford on it to compute the distance $d(v)$ from the source to $v$, for each vertex $v$.
2. Color each edge $(v,w)$ red if $d(v) + \text{wt}(v,w) = d(w)$.
3. Form a new unweighted, directed graph $G'$ containing just the red edges from $G$. Check whether $G'$ has any cycles, using a standard algorithm (e.g., depth-first search). This can be done in linear time.

I'll leave it to you as an exercise to prove that the original graph $G$ contains a zero-length cycle if and only if the new graph $G'$ has a cycle.
> 3 votes

# Answer
Note that this answer only contains the proof that was left as an exercise by D.W.. First, give it a try by yourself. And, in case you get stuck then refer to it.

**Statement**: The original graph $G$ contains a zero-length cycle if and only if the new graph $G′$ has a cycle.

**Proof**: Let $d\_{s}(v)$ denote the shortest path length from $s$ to $v$ for any $v \in V$. First, we will prove the "only if" direction.

$(\to)$ Suppose $G$ contains a zero weight cycle $C = (u\_{1},\dotsc,u\_{k} )$. For the sake of contradiction assume that $G'$ does not contain this cycle. It means there are some two vertices in $C$, say $u\_{1}$ and $u\_{2}$ for which $d\_{s}(u\_{2}) \neq d\_{s}(u\_{1}) + w(u\_{1},u\_{2})$. It means, $d\_{s}(u\_{2}) \< d\_{s}(u\_{1}) + w(u\_{1},u\_{2})$. Let us call this equation $(1)$.

Now, consider the path $p$ from $s$ to $u\_{1}$ as: $s$ -\> $u\_{2}\dotsc$-\>$u\_{k}$-\>$u\_{1}$. The length of this path is: $(d\_{s}(u\_{2}) + length(u\_{2} \textrm{ to } u\_{1}))$. Since $length(u\_{2} \textrm{ to } u\_{1})+ w(u\_{1},u\_{2}) = 0$. The length of $p$ is: $(d\_{s}(u\_{2}) - w(u\_{1},u\_{2}))$. From equation $(1)$, this value is at $\< d\_{s}(u\_{1})$. It contradicts the fact that the shortest path length from $s$ to $u\_{1}$ is $d\_{s}(u\_{1})$. This completes the proof of "only if" direction. Now, we will prove the other direction.

$(\gets)$ Suppose $G'$ has a cycle $C = (u\_{1},\dotsc,u\_{k} )$. We will show that the weight of this cycle is $0$.

Let $u\_{1}$ and $u\_{2}$ be the two vertices in $C$. We have that:

\begin{align} d\_{s}(u\_{1}) &= d\_{s}(u\_{k}) + w(u\_{k},u\_{1}) \\ &= d\_{s}(u\_{k-1}) + w(u\_{k-1},u\_{k}) + w(u\_{k},u\_{1})\\ &\quad ... continuing \\ &= d\_{s}(u\_{2}) + w(u\_{2},u\_{3}) + \dotsc + w(u\_{k},u\_{1}) \\ &= d\_{s}(u\_{1}) + w(u\_{1},u\_{2}) + w(u\_{2},u\_{3}) + \dotsc + w(u\_{k},u\_{1}) \\ &= d\_{s}(u\_{1}) + length(C)\\ \end{align}

It implies that the length of the cycle is $0$. This completes the proof of "if" direction.
> 3 votes

# Answer
Adding to the discussion, you can also detect negative or zero-length cycles using Floyd-Warshall in $O(n^3)$ by setting the initial value of the minimum distance of each node to itself as infinity.

Also, there is this problem (APIO 2017 Travelling Merchant) that is slightly similar to your problem, with a solution available here that also uses binary search and cycle detection.
> 1 votes

# Answer
I don't think there is a known algorithm to find whether there is a zero-distance cycle in a graph in a polynomial time, as it is an NP-complete problem.

As you might know, if a known NP-Complete problem $X$ can be reduced in polynomial time to another problem $Y$ ($X \leqslant\_p Y$) then $Y$ is an NP-complete problem too. Such is the case with Zero-distance cycle problem (which I will call $Z$) and the Subset Sum Problem (which I will call $S$).

$S$ is a known NP-Complete problem. A proof of its NP-Completeness can be found in chapter 8, section 8.8 of Algorithm Design, by Jon Kleinberg and Éva Tardos. It reduces SAT to 3D-Matching to Subset-Sum. It has another version of $S$, but it can be proven equivalent by polynomial reduction with the one used in this answer.

Now, here's a proof of how $S \leqslant\_p Z$:

Suppose you have an $S$ problem. Its input is a set $W = \\{w\_1, \ldots, w\_n\\} \subseteq \mathbb{Z}$. The input is accepted by $S$ if there is a subset $A \subseteq W$ so that

$$\sum\_{a \in A} a = 0. $$

So let's model this $S$ problem as a $Z$ problem. To do so, we build a Graph $G = (V,E)$ with $2n$ vertices as follows:

* For each element $w\_i$ we create two vertices, $u\_i$ and $v\_i$.
* For every $v\_i$ we add the edge $(v\_i,u\_i)$ to $E$ with weight $w\_i$.
* For every $u\_i$ and $v\_j$ we add the edge $(u\_i, v\_j)$ to $E$ with weight $0$.

For a three element $S$ problem we would get a graph such as this:

Now, we send that graph to an hypothetic $Z$ solver. Some important notes:

* If there is a cycle, it goes through at least one complete element ($u\_i$ and $v\_i$).
* If a cycle goes through such an element, the total distance increments by $w\_i$.
* If a cycle goes through multiple elements, the total distance will be the sum of all of them.

As a conclusion, if a zero-distance cycle is found by the $Z$ solver, that would mean that there is a subset of $W$ with zero sum. This confirms that $S \leqslant\_p Z$, and because of that $Z$ is NP-Complete.
> 0 votes

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


# Question
Title: Graph Layout Algorithm that optimizes only `x` (not `y`) of nodes?
I have a hierarchical graph structure on a vertical timeline with nodes that have a fixed `y` coordinate. I am now looking for:

1. an algorithm (suggestions, any related papers, anything at all) to optimize the `x` of each node to reduce edge crossings (and generally increase graph readability).
    * One idea that I have been exploring is a grid layout: my nodes already have specific rows (one per row) but determining the column for each node (or node group) is the difficult part.
2. (not as important) an algorithm to draw edges while minimizing clutter. Most algorithms have straight edges, but I would not mind trying something else, where, for example, in a grid layout, I optimize edges by finding the cells the edges should go through. I know that straighter or just short edges are generally better, but maybe there is something that can be improved here as well?

So far, the algorithms I found are limited to unconstrained nodes and, except for some papers on edge bundling, do not discuss optimizing the edge path itself.

Any help/keywords/papers, anything really, would be largely appreciated!

# Answer
> 1 votes
One plausible approach would be to adapt a graph drawing algorithm algorithm to your situation. Some of them use optimization (e.g., force-based layout algorithms); it should be easy to adapt them by treating the $y$-coordinate of each point as a fixed constant and only optimizing the values of the $x$-coordinates. I don't know whether this will minimize the number of edge crossings, but it seems plausible it might do a reasonable job.

---
Tags: graphs
---


# Question
Title: Why is the certificate version of NP so ubiquitous?
I've noticed that the certificate/verification version of the definition of the class NP is much more popular online than the Turing machine version. In particular, the Wikipedia page has the certificate version stating

> NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine.

listed first, and Google's featured result (via Britannica) has this version. This seems to be especially true for explanations aimed at wider audiences such as YouTube videos from popular creators (i.e. not lectures on the subject or course recordings) such as here and here).

Is there a fundamental reason why this appears to be the preferred presentation online?

# Answer
> 3 votes
It's likely due to the simplicity, because if you use the TM definition, which I assume is the non-deterministic TM solving in poly time, now you have to explain what a non-deterministic TM is, how it works, and why it would work to solve such a problem.

Understanding that an NP problem is so because we can check its answer in poly time is much easier to understand for most people.

For a concrete example, you can either explain to someone that for Sudoku

1. It is in NP because given a solution, we can check every group of squares, and every column and row to make sure the solution works.
2. It is in NP because given a sudoku board, we can construct an algorithm for a non-deterministic TM that tries all 1-9 numbers for each empty square, and one of the TMs will have the right answer...and then you have to explain why the correct answer exists in this scheme

So 1. is easier and that's likely why we use that definition.

---
Tags: complexity-theory, knowledge-representation
---


# Question
Title: Does a closed formula exist for each recurrent formula?
I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the question.

Short and simple, if there exists a recurrent formula for some process, can it be either proven or disproven (was it already?) that a closed formula also exists for the same process?

Thanks.

# Answer
> 1 votes
As a general rule, $x\_{n+1}=f(x\_n)$ does not have a closed form. But I don't know of a general proof. (This seems to be at the same level of difficulty as the antiderivative or closed-form zeroes problems.)

---

**An interesting case:**

Let us consider the following iteration:

$$x\_{n+1}=\frac{x\_n^2+a^2}{2x\_n}.$$

One can recognize the Heron method for the computation of the square root. The next iterate would be

$$x\_{n+2}=\frac{\left(\dfrac{x\_n^2+a^2}{2x\_n} \right)^2+a^2}{2\left(\dfrac{x\_n^2+a^2}{2x\_n} \right)}=\frac{x\_n^4+6x\_n^2a^2+a^4}{4x\_n^3+4x\_na^2},$$ and the next iterations seem scary to evaluate.

But consider

$$\frac{x\_{n+1}-a}{x\_{n+1}+a}=\frac{x\_n^2+a^2-2x\_na}{x\_n^2+a^2+2x\_na}=\left(\frac{x\_n-a}{x\_n+a}\right)^2$$ and all of a sudden we get the easy solution

$$\frac{x\_{n}-a}{x\_{n}+a}=\left(\frac{x\_0-a}{x\_0+a}\right)^{2^n}$$ which we can solve for $x\_n$.

---
Tags: recurrence-relation, recursion
---


# Question
Title: Exact formulation of definition of $NP$, in relation to $R$
One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial time. There is no loops, so $P\subseteq R$.

One definition for $NP$ is having a certificate and a deterministic turing machine $N$ s.t. if $y\in B$ then there is a (polynomial size) certificate $u$ s.t. $N$ accepts $y$ and $u$ in polynomial time. What if $y\notin B$? There will be no such certificate, but are we forced to halt? Polynomial time rejection? Seems that there is no refering to this case, and it bothers me - to know what is the exact definition.

An alternative definition for $NP$ is for a language $B$ to have a non deterministic turing machine $N$ s.t. if $y\in B$ then $N$ accepts in polynomial time. What about the case $y\notin B$? Do we have any requirements? Must it halt? Polynomially? Definitions I found seem to miss it.

Having the two definitions equivalent is easy for me to see, and the problem I described is the same problem, only once for each definition.

Additionally, this problem occurs when define $NTIME$ and $NSPACE$. If the input is in the language, we will need $f(n)$ time (or space) for a non deterministic turing machine. But otherwise - if the input is not in the language - what limitations do we have, by definition, on the computation time (or space)? Must we reject? Or loop?

I am aware that classically $NP\subseteq R$ as well. Yet, this issue bothers me, so I am hoping to tidy this gap in the definitions.

**Edit:** I have read chi's answer in Is rejecting in polynomial time required for language to be in P? . However, I am unsatisfied with his answer, as running in some time limit $O(f(n))$ (polynomial or other) doesn't grant you a numerical upper bound on the number of steps! Say we have an input of size $n=20$ and we had $f(n)=n^2$, so the running time is $O(n^2)$, this can be any $c\cdot 400$, we can't count the number of steps and compare it to this!

# Answer
> 2 votes
#### A definition of $\mathsf{NP}$

Definition of $\mathsf{NP}$: A decision problem $prob$ (i.e., a set of input strings) is in $\mathsf{NP}$ iff there is a deterministic Turing machine (DTM) $D$ such that for each yes-instance $x$ of $prob$, there is a certificate $(x,y)$ that is accepted by $D$ in polynomial time of $|x|$.

It is notable, as described in the question, the definition above says nothing about the behavior of $D$ for a no-instance $z$ of $prob$. In particular, it is fine if $D$ does not even halt on some $(z, w)$!

#### An equivalent definition of $\mathsf{NP}$

However, with the definition above, we have the following.

**Claim**. A decision problem $prob$ is in $\mathsf{NP}$ iff there is a DTM $E$ such that for any $(x,y)$ where $x$ is an instance of $prob$, $E$ will halt in polynomial time of $|x|$ and for each yes-instance $x$ of $prob$, $E$ accepts a certificate $(x,y)$ for some $y$.
**Proof**.
"$\impliedby$": This is trivial.
"$\implies$": By the definition above, we have a DTM $D$ such that for each yes-instance $x$ of $prob$, there is a certificate $(x,y)$ that is accepted by $D$ in $p(|x|)$ time for some polynomial $p$.
Let us can build a new TM $E$, which on input $(x,y)$ will simulate $D$ on input $(x,y)$ for at most $p(|x|)$ steps and

* when the simulated $E$ accepts $(x,y)$ as a certificate, $E$ will accept $(x,y)$ as a certificate as well,
* otherwise, if the simulation is done, $E$ will reject.

Furthermore, we require the simulation of $s$ steps, including the check of "at most $p(|x|)$ steps" at each step, takes no more than $O(s^2)$ steps. (If you are concerned that $s^2$ may not be enough, replace it with $s^k$ with a big $k$ such as $k=2+\deg(p)$.) So, $E$ runs in polynomial time of $|x|$. $\quad\checkmark$

**Corollary**. $\mathsf{NP}\subseteq\mathsf{R}$
**Proof**. Suppose $prob\in\mathsf{NP}$. Then there is DTM $E$ such that for any $(x,y)$ where $x$ is an instance of $prob$, $E$ will halt in $p(|x|)$ time where $p(\cdot)$ is a polynomial, and for each yes-instance $x$ of $prob$, $E$ accepts a certificate $(x,y)$ for some $y$.

Let us build DTM $F$ such that upon $x$ where $x$ is an instance of $prob$, $F$ will, for every string $y$ such that $|y|\le p(|x|)$, try simulating $E$. At the end of each simulation, if the simulated $E$ accepts a certificate $(x, y)$, then $F$ accepts $x$ (and halts). If $F$ has not accepted when all simulations are done, then $F$ rejects $x$ (and halts).

Note that $F$ is a decider for $prob$. $\quad\checkmark$

Since the number of such $y$s is $2^{O(p(|x|))}$, $F$ decides $prob$ in $2^{O(p(|x|))}\*p(|x|)$ time. So we have shown that $$\mathsf{NP}\subseteq\mathsf{EXPTIME}.$$

#### More definitions of $\mathsf{NP}$

Similarly, if we define a language $B\in \mathsf{NP}$ iff there is non-deterministic Turing machine (NDTM) $N$ such that if $y\in B$ then $N$ accepts $y$ in polynomial time and if $y\notin B$ then $N$ does not accept $y$, then for each language $B\in\mathsf{NP}$, there is a NDTM $N$ that decides $B$ in (non-deterministic) polynomial time.

#### Some references

The exposition above is not very formal. For example, "certificate" is not defined in formal terms here. It should be good enough as an explanation, though.

Here are a few related posts.
Formal definitions of $\mathsf{P}$ and $\mathsf{NP}$
What is EXPTIME?
What is co-something such as $\mathsf{coNP}$ and $\mathsf{coRE}$?
How to understand a class of languages as decision problems?
Is rejecting in polynomial time required for language to be in P?

---
Tags: complexity-theory, turing-machines, polynomial-time, nondeterminism, recursively-enumerable
---


# Question
Title: Proving that the greedy algorithm for job scheduling has a 2 - (1/m) approximation ratio
In the scheduling problem, the input is a sequence $T\_1,T\_2,...,T\_n$ which are the times of $n$ jobs to be executed in m identical machines. A schedule is an assignment of the jobs to machines. The load of each machine is the sum of the times of the jobs assigned to it. The objective is to find a schedule with minimum makespan; the makespan is the maximum load among the machines.

The greedy algorithm for assigning jobs to machines assigns the jobs one-by-one; each job is assigned to a machine which currently has minimum load.

I'm trying to prove that this has a 2 - (1/m) approximation ratio.

I know that $opt(x) \>= max(max(T\_1,T\_2,...,T\_n), (1/m) \sum\_{i=1}^n{T\_i})$

I've proven an approximation ratio of 2, but can't seem to figure out how to prove that it's 2 - (1/m)

# Answer
> 1 votes
Suppose machine $A$ ends up with the maximum load $M$ . Let $i$ be the last job scheduled on machine $A$. Right before $i$ was scheduled, machine $A$ had the smallest load, which was at most the average load at that time. We have, $$\begin{aligned} M &= (M − T\_i ) + T\_i\\ &\le\frac 1m(\sum\_{1\le k\le n}T\_k\\,-T\_i) + T\_i\\ &=\frac 1m\sum\_{1\le k\le n}T\_k + (1-\frac 1m)T\_i\\ &\le opt + (1-\frac1m)opt\\ &=(2-\frac1m)opt \end{aligned}$$

---
Tags: approximation, greedy-algorithms
---


# Question
Title: A red-black full tree where every black node has at most 1 red child has at most (n-1)/4 red nodes
Let us call a red-black tree strict when every black node has at most one red child.

Show that a strict red-black full tree has at most $(n − 1)/4$ red nodes; a binary tree is full when every node has zero or two children.

The hint for this problem says to use a charging argument but I can't seem to figure one out.

My idea was to consider the root of the tree (which must be black) and recursively consider the number of red nodes in the left and right subtrees and show by induction that this holds. But I can't seem to figure out some of the details (and there seem to be some inconsistencies).

# Answer
Deposit 3 dollars on each red nodes initially.

For each black node, if it is a sibling or a child of a red node, move one dollar on that red node onto the black node.

Claim 1: there is at most one dollar on each black node. There is no dollar on the root of the tree.

Claim 2: there is no dollar on red nodes.

The total amount of dollars was $3\times\\#\text{red nodes}$ initially. The total amount of dollars at the end is at most $\\#\text{black nodes} - 1$. $$3\times\\#\text{red nodes} \le \\#\text{black nodes} - 1$$ which means $4\times\\#\text{red nodes} \le (\\#\text{black nodes} + \\#\text{red nodes}) - 1=\\#\text{all nodes}-1$.

I will let you prove the two claims.
> 1 votes

---
Tags: data-structures, red-black-trees
---


# Question
Title: Determine if string can be constructed from given building blocks
Let's say building blocks are X, Y, XX, YY, XY and YX. Each building block has an associated count ($c\_X, c\_Y, c\_{XX}, \ldots$, $c\_i$ can be 0).

Given a string $s$ and building block counts, figure out if it can be constructed from the building blocks that are used exactly the amount of times allowed by counts.

Example: XXYXY, $c\_X=2, c\_{XY}=1, c\_{Y}=1$ is possible, because X|X|Y| XY (there's more than 1 possible way to build the given string).

My approach was counting the appearances of building blocks in the string $s$. It's easy to figure out of there isn't enough X or Y to create the string, but a bit harder to figure out if there's too much XY and YX.

I expect that the algorithm is linear but I cannot figure it out.

# Answer
For every prefix of the string, determine how it can be produced. We always prefer two letter blocks to two single letter blocks.

Let s = eps: Create s by using no blocks.

Let s = A where A is a single letter X or Y. s cannot be created if $c\_A = 0$, otherwise it is created by using the single-letter block A.

Let s be a string of length n+2, ending in AB. It can be created in various ways. If there is a two letter block AB left then s is created by adding AB to every solution for the first n letters. If there is a single letter block B left then we add a single letter block B to any solution for the first n+1 letters that ended in a two-letter block, and to any solution for the first n+1 letters that ended in A unless there is a two letter block AB left. Then we remove all duplicates with the same number of each block lefts. That's it.

In your example:

```
eps = empty
X = X
XX = X, X (no XX available)
XXY = X, XY (preferred to X, X, Y)
XXYX = X, XY, X (no XY available)
XXYXY = X, XY, X, Y.

```

This will grow at most with $2^n$ where n is the number of letters, but is likely easier in practice, and possibly easier in the worst case as well.
> 1 votes

---
Tags: algorithms, strings
---


# Question
Title: Benefit of Petri Net Transition as Separate Object
In learning about Timed Automata, Coloured Petri Nets, and Process Calculi, I am wondering what the benefit is of having the Petri Net transition be a separate type of node in Petri Nets.

It seems that you can model the same stuff (eventually) using Timed Automata or Process Calculi, which both only have states and transitions (as edges, not objects). Instead of transition nodes, you could just have two types of "state", one be the Petri net place, the other be the Petri net transition. Then this second node does all it's queuing/guarding/checking of the tokens and whatnot. So I'm not sure the benefit is of having transition be a separate object in Petri Nets, when it could just be a second kind of "place" or "state".

That makes me wonder if there is a generalization of Petri nets to arbitrary number of node types (where instead of just place/transition, you have x, y, z, ...). In this sense it seems that process calculi are a generalization of Petri Nets.

# Answer
In my experience, the duality of Petri nets is a great strength.

It forces us to specify the potential events or actions in a system (the transitions), as they may happen to individual items (the tokens), together with their preconditions and postconditions (the places). This forces us to think through what a step really means as we're denoting it, because we're denoting its effects as well.

When done right, it also matches a natural language specification. In a natural model, transitions represent predicates involving verbs of change, places represent predicates involving verbs of state, and tokens represent their subjects. For instance:

* a transition can be *a customer arrives*, or *switch the light off*, or *the light breaks*, or *the sun goes down*;
* a place can be *a customer is waiting*, or *a customer is ready to pay*, or *the light is off*, or *the sun is down*;
* a token is *a customer*, *the light*, *the sun*.

(Further expanded in this answer.)

It greatly helps to adopt this as a naming convention for your Petri nets. You can then read the model out loud as a bunch of natural statements in natural language.

Let's compare this to models without this duality.

On one hand, we have state machine based models.

These list the system's states and connect them with arrows representing state transitions. Such a model can only be in one state at once; it does not allow the specification of individual conditions that together specify the global state, like places in a Petri net do. Of course we can draw several state machines for several subsystems and say they somehow operate together, and we can add that into the modeling technique by adding ways of specifying how submodels combine and coordinate; in Petri nets, we don't need to do that, the ability is already there. Moreover, if we want to start describing a system we don't already know, or design a system that doesn't already exist, writing down a bunch of predicates describing the relevant conditions and potential changes, like we can when specifying Petri nets, feels more natural to me, and leaves more freedom, than having to write down a specification in terms of state machines.

(That being said, when state-machine based techniques and Petri nets are extended to support modelling arbitrary processes in detail, the results may be very similar. Abstract State Machines look quite similar to algebraic Petri nets.)

On the other hand, we have process models in which the objects are steps to be taken, connected with arrows to describe the order in which they (may) happen. In my opinion, these are awful and a hindrance to good process design.

The simplest kind I've seen is just a bunch of boxes and arrows, like this:

What does this say? After we go home, do we both feed the cat and get a glass of water? Do we choose between them? Does it vary? We have no idea. This is not a specification, it's a sketch.

Then, of course, we have flowcharts. Flowcharts, like state machines, describe completely sequential processes. Starting in the initial state, each box in the flowchart takes us to the next state, until we reach the final state. The two examples in Wikipedia:

The boxes are actions; the diamonds are tests, which pick the next step based on the test result. An imperative computer works this way, and so do many completely sequential algorithms executed by something other than a computer. Flowcharts can describe them, but they are of little help in reasoning about them: in designing them, redesigning them, or proving their correctness.

A flowchart models the actions that change certain conditions, and tests that inspect certain conditions, but it doesn't model the conditions themselves. To prove correctness, we must explicitly model all of the relevant conditions, state which conditions must hold at the start, state which conditions must hold at the end, and by bookkeeping the conditions along the way, prove whether or not the algorithm is guaranteed to achieve that.

This is exactly what proof techniques for correctness of algorithms do (e.g. Hoare logic) and it will happen when turning a flowchart into a Petri net. The places will specify the relevant conditions.

So one limitation of flowcharts is that, by omitting bookkeeping on the relevant conditions, they don't support reasoning about the algorithms being specified. But at least they can specify such algorithms. Things get much worse when the algorithm in question isn't already given.

How do you design an algorithm for a given problem from scratch? You specify the initial and final conditions and you figure out a bunch of intermediate conditions and steps to bridge that gap. The designer must be explicit about the intermediate steps and how they affect the intermediate conditions. This is not usually a linear process in which the designer specifies all steps one by one from start to finish; rather, it tends to be a more unstructured refinement and reshuffling process. The exact order in which things are done may only be determined towards the end.

Or such a strict order may not exist at all. Many systems we need to describe or design aren't strictly sequential in nature; they use constructs such as pipelines and asynchronous calls, and are generally composed of various agents working together in some coordinated way, without all of the steps happening in a strictly sequential order. In interactive systems, users interacting with the system typically do not use fixed sets of sequences of actions, but they may wander through the systems in all sorts of ways. We need to be able to reason about such systems, too, and flowcharts, being sequential, cannot describe them well.

This has been recognized in industry, with lots of augmented flowcharting techniques as a result, such as

These add constructs for parallel execution and much more; some have a very rich set of constructs. However, they still only specify process steps and their compositions, without specifying the relevant pre- and postconditions. As a result, working with these formalisms still feels like programming potential solutions, rather than reasoning about the problem being solved.

This can be remedied by systematically inscribing the steps of such models with variables tested by testing steps and modified by the action steps. The variables can be used like the places in Petri nets.

You may argue that the need for such reasoning doesn't mean the results need to be visible within the process model. It can be specified separately. But in my experience, that's not what happens. Instead, people just write down the steps of their programs, with or without constructs for parallelism, and any reasoning about its correctness remains in the minds of the designers. If you're lucky, there will be a comment here and there.

This is not only true for computer programming, but it holds for all sorts of process specifications. Take, for instance, use case modeling or test case specifications. A modern interactive computer application is highly nondeterministic: at practically every point, a user has multiple different ways of continuing - for instance, multiple different buttons that can be pressed. The designer wants to leave the user as much freedom as possible. However, it must be proved that the program serves its intended purpose, and this is what use case and test specifications intend to do. What I've noticed is that in practice, these specification often take the form of a linear sequence of steps, or at best, a flowchart-like sequential algorithm. As a result, they do not describe any of the user's freedom at all. This has two risks: the implementation may end up straitjacketing the user into these overly sequential specifications, or, if it doesn't, the application may end up underspecified and undertested, and users may take untested paths with possibly disastrous consequences. You end up with a proof that a particular sequence of actions produces a particular result, without getting anything like a full proof of program correctness or completeness. All this because those writing the use case / test case specifications couldn't think of anything but a purely sequential specification. This can be remedied by using Petri nets or a similar formalism, with support for concurrency and explicit representation of intermediate application states.

Petri nets have limitations of their own, and using them won't magically solve your process design or test case specification problems, but at least it will enforce the mental hygiene of always thinking about the steps of a process together with its pre- and postconditions. In doing so, it supports a much greater degree of freedom of specification than allowed by flowchart-based techniques or simple state machines. These things are needed when reasoning about processes.
> 2 votes

# Answer
The state transition graph underlying a Petri Net model is called the Reachability Graph. Yes, it exists, and it is the foundation of Petri Net semantics. However, it is possible to define simple, easily understandable Petri Net models that have reachability graphs of a size and structure that no human could make sense of. They might also be graphs with an infinite number of states.

It's similar to programming languages: every conceivable algorithm or program could be written in assembly language. But there are dozens, if not hundreds, of higher level programming languages that make it easier, simpler, and faster for humans to write and understand programs, to express the algorithms and the processing they need to implement. And then a compiler or interpreter turns the high-level program into a stream of processor instructions.

Petri Nets are meant as a way for humans to create meaningful, understandable models, without drilling down to individual states and transitions. Then Petri Net tools handle the simulation and/or analysis of the models.
> 1 votes

---
Tags: automata, petri-nets, process-algebras
---


# Question
Title: determining the relationship between two regular languages using the myhill nerode theorem
> For a regular language $A$ with an alphabet $\Sigma$, define an equivalence relation for strings $x,y \in \Sigma^\*$ by $x\equiv\_A y\Leftrightarrow \\,\forall w\in \Sigma^\*, xw, yw\in A$ or $xw, yw\not\in A$. Let $\[x\] := \\{ y\in \Sigma^\* : y\equiv\_A x\\}$ be the equivalence class of $x$ with respect to $A$ for any $x\in \Sigma^\*$. Let $A$ and $B$ be two regular languages, and suppose they have the exact same set of equivalence classes (as defined above).

> Prove or disprove that $A$ and $B$ are either equal or complements.

I think the statement is true. Let $A\_1,\cdots, A\_k$ be the equivalence classes of $\Sigma^\*$ with respect to $A$ (there are finitely many by the Myhill-Nerode theorem). I'm not sure how to get a contradiction if I assume there's a string $x$ in $A$ but not in $B$ and a string $y$ in $A$ and $B$. Obviously both strings must belong to different equivalence classes of $B$, and hence $A$.

# Answer
> 1 votes
No, the statement is not true. The language defines the equivalence classes, but not the other way around. Each class can be totally within or totally outside the language. So with several classes we have some room to choose which classes are in and which classes are out the language. We have to be careful though, some choices will change the equivalence relation itself.

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


# Question
Title: Approximate x*(a/b)^(c/d) using integer arithmetic only (assembler)
0 \< x,a,b,c,d \< M are all positive integers (uint64). also, a\<b if that helps.

we have assembler (integer only) operations available (e.g. division only yields integers).

we want to approximate: x\*(a/b)^(c/d)

how to do this in the simplest way?

thx

edit: added x

# Answer
The standard way to implement exponentiation is using logarithm and exponentiation. In particular,

$$u^v = e^{v \log u}.$$

So, you need algorithms for multiplication, division, exponentiation, and logarithm. Multiplication and division are documented well in many standard places. Some algorithms for division can be found on Wikipedia at https://en.wikipedia.org/wiki/Logarithm#Calculation. A standard way to compute $e^x$ is using the Taylor series expansion of that function.

See also https://ethereum.stackexchange.com/q/83785/19041, https://ethereum.stackexchange.com/q/10425/19041.
> 2 votes

---
Tags: approximation, arithmetic, integers, assembly
---


# Question
Title: Looking for a subjective ranking algorithm
I'm interested in learning about ranking algorithms that sort items based on preference. For example: If a person was food taster/judge and had 10 small bowls of chili that they had to rank in order from best to worst, in what way should the judge taste the chili from the individual bowls to complete the task of ranking with as small a number of repeat tastings of the same bowl as possible? The initial approach I thought of was as follows. I've named the bowls A - J:

initial order:

> A, B, C, D, E, F, G, H, I, and J

Taste A then taste B. If B is better than A, switch them around in the order.

Judge thinks B is better than A:

> B, A, C, D, E, F, G, H, I, and J

Taste A then taste C. If C is better than A, switch them around in the order.

Judge thinks C is better than A:

> B, C, A, D, E, F, G, H, I, and J

Already though there is a problem. What if C was also better than B? We could complete the process then repeat again but its not clear to me how many times the process would have to be repeated in order to have everything ranked properly. What kinds of algorithms are these? Where can I learn more about them. Thanks.

# Answer
> 1 votes
If the tastings are reliable (i.e. always returning the same results for the same samples and forming a true total order relation - A better than B and B better than C implies A better than C), what you are after is a "minimum comparison sorting" procedure.

The number of comparisons for N elements is very close to N.Log2(N), but the exact procedure depends on N in a non trivial way, and not all configurations require exactly the same numer. https://en.wikipedia.org/wiki/Comparison\_sort#Number\_of\_comparisons\_required\_to\_sort\_a\_list

---

As far as I know, there has been no study on minimizing the number of comparisons involving the same element (which could be understood as minimizing the largest number of comparisons with the same element).

---

Also note that an efficient sorting procedure cannot be static, i.e. work with a predefined set of comparisons. On the opposite, the outcome of the first tests decide which next tests should be performed. A purely static procedure should be exhaustive, i.e. require N(N-1)/2 comparisons.

# Answer
> 0 votes
*Analytic hierarchy process* (AHP) is a way to maximize or minimize or rank or prioritize things which are given in data formulated as qualitative comparisons, like a customer likes A more than B and so on. Given a set of customers and all their preferences, AHP can provide the max or a 'best' ranking or something like this.

See: https://en.wikipedia.org/wiki/Analytic\_hierarchy\_process

---
Tags: algorithms, sorting
---


# Question
Title: Finding smallest triangle to fit all points
I'm supposed to find an algorithm that, given a bunch of points on the Euclidean plane, I have to return the tightest (smallest) origin centered upright equilateral triangle that fits all the given points inside of it, in a way that if I input some random new point, the algorithm will return $+$ if the point is inside the triangle and $-$ if not.

Someone has suggested me to go over all the possible points and finding the point with the largest Eucledean distance from the origin, then, say the point is $(x\_1,x\_2)$, I should calculate the following:

$(x\_1,x\_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})=x\_{1}\cdot\frac{\sqrt{3}}{2}+x\_{2}\cdot-\frac{1}{2}=r\_{1}$

$(x\_1,x\_2)⋅(-\frac{\sqrt{3}}{2},-\frac{1}{2})=x\_{1}\cdot-\frac{\sqrt{3}}{2}+x\_{2}\cdot-\frac{1}{2}=r\_{2}$

$(x\_1,x\_2)⋅(0,1)=x\_{1}\cdot0+x\_{2}\cdot1=r\_{3}$

Then take the maximum of $r\_1,r\_2,r\_3$, denote it $r\_{max}$ and given a new random point $(y\_1,y\_2)$ output $+$ if

$(y\_1,y\_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})\le r\_{max}$

$(y\_1,y\_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})\le r\_{max}$

$(y\_1,y\_2)⋅(0,1)\le r\_{max}$

It should look something like this:

and output this triangle:

Now when I try to graph points with the same Eucledean distance on a graph, they do indeed seem to be on the sides of the same origin centered upright equilateral triangle, but I can get different $r$ values for different points which have the same Eucledean distance, so I'm quiet baffled as to how it is supposed to work, if this method even works..

# Answer
If the triangle is centered at the origin, in general only one point touches it. You find this point as the one furthest in the three directions normal to the triangle sides (by taking the dot product with the normal vectors). As there are three distances, you take the largest.

Beware that the relevant distance is not the Euclidean distance to the center.
> 3 votes

---
Tags: computational-geometry, data-sets, euclidean-distance
---


title: MAX-SAT 2-Approximation algorithm

text:
# Question
Title: MAX-SAT 2-Approximation algorithm
I have the two following questions:

1. I know SAT -\> MAX-SAT but how can I show that if MAX-SAT is solved in polynomial time then SAT is solved in polynomial time as well?(I guess using approximation algorithms)
2. I have this simple randomized algorithm for approximating the MAX-SAT problem:

***The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. It then outputs the resulting assignment.***

```
for(i=1,2,...,n){
    set xi = 0 or xi = 1 with probability 1/2 for each case
}

```

So everywhere I have looked I found people presenting this as an 1/2 approximation algorithm but I'm supposed to prove that this is a 2 approximation algorithm. Can anyone help clarify this?

# Answer
A $1/2$-approximation algorithm and a $2$-approximation algorithm are exactly the same thing.

Here are two definitions of a $\rho$-approximation algorithm for a maximization problem:

1. On an instance whose optimal value is $O$, the algorithm is guaranteed to output a solution whose values is at least $\rho \cdot O$.
2. On an instance whose optimal value is $O$, the algorithm is guaranteed to output a solution whose values is at least $O/\rho$.

The first definition only makes sense when $\rho \leq 1$, while the second only makes sense when $\rho \geq 1$. Some people prefer the first one, others prefer the second one. Fortunately, you can tell from the value of $\rho$ which one is meant (when $\rho = 1$, both concepts are the same).
> 2 votes

---
Tags: approximation, sat-solvers, maxsat
---


# Question
Title: Interpreting the time complexity of a program from function
$T(n)=5T(n/3)+n^2$ Consider this to be the running time of a program. How could we interpret
then numbers 5 and 3.
My Thoughts:
5 times will mean that the problem is divided into 5 subproblems each of size n/3
and then probably to get the solution to the main problem it required $n^2$ steps

I am not sure if that is a perfect explanation or a better way to explain the $n^2$ addition

# Answer
> 0 votes
You are right. This could be a problem solved using a divide-and-conquer strategy such that the data set is recursively processed in five subsets, each a third of the data, while the split and the merge phases cost $n^2$ altogether.

---
Tags: algorithms, runtime-analysis
---


title: Covering all colors with unit intervals

text:
# Question
Title: Covering all colors with unit intervals
Suppose we are given $n$ points on the real line, where each point is colored with a color from set $C=\\{c\_1,c\_2,\ldots,c\_k\\}$ that contains $k$ distinct colors. We try to cover the $k$ distinct colors with as few unit length intervals as possible.

I think this problem is NP-hard and we can reduce from set cover problem. But I get stuck.

Also when $k=3$, is there a polynomial solution. I read this link but I can't understand his idea?

# Answer
> 5 votes
If $k$ is part of the input then the problem is NP-hard and you can indeed reduce from the set-cover problem. Let $x\_{1}, \dots, x\_k$ be the items and $S\_1, \dots, S\_m$ be the sets. Create a color for each item. Then, for each set $S\_i$, create $|S\_i|$ points on the real line at coordinates $2i + \frac{1}{|S\_i|}, 2i + \frac{2}{|S\_i|}, \dots, 2i + 1$. Color the $j$-th of such points with the color of the $j$-th item in $S\_i$. Notice that: (i) one interval cannot cover two points from two sets, and (ii) all points from the same set can be covered with a single interval.

If $k$ is not part of the input then the problem is not NP-hard, unless P=NP. Indeed a trivial algorithm guesses one covered point for each color (there are only $O(n^k)$ guesses) and then covers the guessed points with the minimum number of intervals (this can be done via an easy greedy algorithm).

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


# Question
Title: Modified knapsack problem with multiple boxes to choose from
I have seen the solution to the knapsack problem and understand it. But I am trying to
come up with a dynamic programming solution to the following problem, which is a modified
a version of the knapsack.
Consider a store with n boxes, each containing m items, and we could only choose one
item out of each box, and the goal is to maximize the value of items, and there is only
one knapsack is available with volume V.

I am not sure how to begin to solve this using dynamic programming.

# Answer
For $i=0,\dots,n$ and $v=0, \dots V$ define $OPT\[i,v\]$ as the maximum value that can be attained by selecting at most one item from each of the first $i$ boxes (and no items from the remaining boxes) when the knapsack volume is $v$.

Let $v\_{i,j}$ and $w\_{i,j}$ be the value and the weight of the $j$-th item in the $i$-th box, respectively. Finally, for the sake of technical convenience, define $v\_{i,0} = w\_{i,0} = 0$.

You have: $$ OPT\[0,v\] = 0 \\; \forall v $$ and, for $i \ge 1$: $$ OPT\[i, v\] = \max\_{\substack{j=0, \dots, m \\ w\_{i,j} \le v}} \left( v\_{i,j} + OPT\[i-1, v-w\_{i,j}\] \right). $$

The optimal value for the original instance is $OPT\[n,V\]$. Moreover, the value of $OPT\[i, v\]$ can be found in time $O(m)$ once the values of $OPT\[i-1, \cdot\]$ are known. Therefore the overall running time is $O(mnV)$.
> 0 votes

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


# Question
Title: Java | If a=250, b=3, c=(a + b/2)/b * b, Why doesn't c equal 251 but rather 249?
If

```
int a = 250;
int b = 3;
int c = (a + b/2)/b * b;

```

Why doesn't `c` equal 251, but rather 249?
How is it that `c` is smaller than `a` when we are adding?
Doesn't the `divide by b` and `multiply by b` cancel out?

I thought `c= int(250+1.5)=251`

# Answer
Operations are executed in order of precedence. When two operations have the same preference, they are evaluated from left to right. In your specific case:

* `b/2` is evaluated first and it evaluates to $1$ (notice the integer division).
* `a+1` is evaluated next, yielding $251$.
* `251/b` is next, yielding $83$.
* Finally, `83*b` evaluates to $249$.
> 1 votes

# Answer
Let's discuss your confusion with precedence and associativity.

Among all the operators Parentheses has highest precedence. That's why $()$ is evaluated first. And then inside $()$ we see two operators $+$ and $/.$ Consequently $/$ has highest precedence than $+$ operator. That's why $/$ is evaluated first then $+$. Now $()$ is completed.

Now we have two operators $/$ and $\*$, both have same precedence. Now what is evaluated first between two? Here now you use the associativity to break the tie. $/$ and $\*$ uses left to right associativity$($which is known as left associativity$).$ That why $/$ is evaluated first because it is at left most operator. And then $\*.$

N. B:- For two $\uparrow,$ the associativity right to left means follows right associativity.
> 0 votes

---
Tags: arithmetic, integers, java
---


# Question
Title: Solution Verification: How does the postorder traversal of a BST change after rotating left?
> Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$.
> How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the traversal not change?

**My Attempt:**
I've decided to draw a sketch of the sub-tree of $T$ rooted in $x$:

```
             x
           /   \
          a     y
              /   \
             b     c

```

Where a,b,c are whatever subtrees/nodes rooted under $y$ and $x$.
The postorder traversal of this subtree is: $postOrder(a), postOrder(b), postOrder(c), y, x$.
After rotating the subtree on node x we will get:

```
         y
       /   \
      x     c
     / \
    a   b

```

And now the post order traversal will be: $postOrder(a), postOrder(b), x, postOrder(c), y$.
So in order for the traversal order not to change (after the rotation), we need to have:
$postOrder(c) = x$
$postOrder(c) = y$
$x = y$
Which means we must have a tree that looks like this:

```
         x
       /   \
      a     x
          /   \
         b     x

```

So in order for the postOrder traversal not to change (after the rotation) we must have 3 equal nodes on the right side of this subtree.
I would really appreciate any feedback on my solution attempt, thanks in advance!

# Answer
> 2 votes
The sketches of the sub-tree before and after the left rotation are clear.

"In order for the traversal order not to change (after the rotation), we need to have" $$\begin{aligned} &postOrder(a), postOrder(b), postOrder(c), y, x \\ =\ &postOrder(a), postOrder(b), x, postOrder(c), y. \end{aligned}$$

Suppose $postOrder(c) = u\_1, u\_2, \cdots, u\_k$, $k\ge0$. Then $$u\_1, u\_2, \cdots, u\_k, y, x = x, u\_1, u\_2, \cdots, u\_k, y,$$ which means $x=u\_1=u\_2=\cdots=u\_k=y=x$. So we must have $x$, $y$ and, if $y$ has a right child, all nodes of the subtree rooted the right child of $y$ are the same.

---

By the way, postorder traversal of a BST (binary search tree) does not make much sense. We usually perform inorder traversal on a BST, which passes all nodes in the sorted order of the keys. It might be better if "BST" in the exercise is replaced with "binary tree".

---
Tags: data-structures, binary-trees, binary-search-trees, tree-traversal
---


title: Finding bits per address in memory

text:
# Question
Title: Finding bits per address in memory
I dont know if this is any important IRL, but I am trying to understand lines below.

> 4K words of main memory (this implies 12 bits per address).

> 4M X 16 means the memory is 4M long (4M = $2^2 \times 2^{20} = 2^{22}$ words) and it is 16 bits wide (each word is 16 bits).

So, how bits per address is really calculated, what does 4K/4M represents and how does that formula in parenthesis works?

# Answer
> 1 votes
In computer science, the following suffixes are commonly used:

* K (Kilo): $2^{10}$
* M (Mega): $2^{20}$
* G (Giga): $2^{30}$
* T (Tera): $2^{40}$

The next one is P (Peta), but it is not in common usage. Usually these suffixes are accompanied by another unit, for example KB (Kilobyte, or $2^{10}$ bytes) or MHz (Megahertz, or $2^{20}$ cycles per second).

Using $n$ bits, you can address $2^n$ words.

---
Tags: computer-architecture
---


# Question
Title: (Why) is $NP\subseteq coNP/poly$ same as $coNP\subseteq NP/poly$?
If I rememeber right, I read somewhere that $NP\subseteq coNP/poly$ is the same as $coNP\subseteq NP/poly$. Is this true? If yes, is there a relatively simple proof for this?

## Definitions

**Class $NP/poly$**.
We say that a language $L$ belongs to the complexity class $NP/poly$ if there is a Turing machine $M$ and a sequence of strings $\\{a\_n\colon n\in\mathbb{N}\\}$ called advice, such that the following hold.

* Machine $M$, when given an input $x$ of length $n$, has access to the string $a\_n$ and has to decide whether $x\in L$. Machine $M$ works in nondeterministic polynomial time.
* $|a\_n|\leq p(n)$ for some polynomial $p$.

$coNP/poly$ is the complement of $NP/poly$.

*Is the following definition correct?*

**Class $coNP/poly$**.
We say that a language $L$ belongs to the complexity class $coNP/poly$ if there is a Turing machine $M$ and a sequence of strings $\\{a\_n\colon n\in\mathbb{N}\\}$ called advice, such that such that the following hold.

* Machine $M$, when given an input $x$ of length $n$, has access to the string $a\_n$ and has to decide whether $x\notin L$. Machine $M$ works in nondeterministic polynomial time.
* $|a\_n|\leq p(n)$ for some polynomial $p$.

# Answer
By definition, $$ L \in \mathsf{coNP} \Longleftrightarrow \overline{L} \in \mathsf{NP} \\ L \in \mathsf{coNP/poly} \Longleftrightarrow \overline{L} \in \mathsf{NP/poly} $$ From this you can easily deduce your claim.
> 2 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: What is the regular expression describing this language?
The language is $\\{w \mid \text{$w$ is any string except $11$ and $111$}\\}$ where the alphabet is $\\{0,1\\}$.

Drawing the DFA recognizing $\\{v \mid \text{$v$ is either $11$ or $111$}\\}$, then switching the accept and non-accept states, and finally examining this resulting structure, I thought of it as being:

$(ϵ∪0Σ^\*∪1∪10Σ^\*∪110Σ^\*∪111Σ^+)$

My reasoning was that it has to accept the empty string, or a 0 followed by whatever or just a $1$ or, if it begins with a $1$, a $10$ followed by whatever or, if it begins with $11$, then a $110$ followed by whatever or a $111$ followed by at least a $0$ or a $1$

Does this appear to be correct? If I'm wrong, could you please tell me why?

Thank you,

# Answer
Yes, your idea is correct.
Basically here two things are happening.

1. Regular languages are closed under compliment operation
2. If L1 is accepted by DFA1 and DFA2 is obtained by interchanging the final states to non-final states and non-final states to final states of DFA1 then the language accepted by DFA2 is compliment of L1. That is, if
    * DFA1 is a quintuple (Q, Σ, δ , q0, F)
    And L1 is language accepted by DFA1
    * DFA2 is (Q, Σ, δ , q0, (Q - F))
    And L2 is language accepted by DFA2
    Then L2 is compliment of L1.

In this case the languages
L1 = {w∣w is any string except 11 and 111} and L2 = {v∣v is either 11 or 111} are compliment o each other .
Hence your approach is correct.
> 2 votes

# Answer
€+(0+1)+0(0+1)+10+0(0+1)(0+1)+10(0+1)+110+(0+1)³(0+1)⁴
> 0 votes

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


# Question
Title: Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$
I'm having problems determining the *productions* for a CFG describing the language $L=\\{ a^nb^m | n \le m+3 \\}$

where $n,m \ge 0$

I'm very new to this so this example might be a little harder, but everything I try I end up not finding the correct solutions. Some example strings are $\epsilon$, $a$, $aa$, $aaa$, $b$, $ab$, $aab$, $aaab$, $aaaab$, $bb$, $abb$, $aabb$, $aaabb$, $aaaabb$, $aaaaabb$ etc.

This is how I tried reasoning:

since there can be a loop of $a$ in the beginning, I thought that *one* production could be

$A \rightarrow aAb | \epsilon$

But this is as far as my reasoning goes. What's confusing is that for each value of $m$, I have increasing $n$.

Can anyone give a hint, or give general hints how to construct CFG from languages?

Thanks!

# Answer
$S \rightarrow aSb/A $

$A \rightarrow \epsilon/a/aa/aaa/B$

$B \rightarrow bB/\epsilon$
> 2 votes

---
Tags: formal-languages, automata, context-free, formal-grammars
---


# Question
Title: How to prove that a subset of a language L is related to NP while L is related to P?
a friend sent me a question where we're given language $L$ and its subset $E(L)$ such that:

$$E(L)=\\{E(w)\ |\ w\in L\\}\\\text{such that}\\ E(w)=\\{w\_{even}=\sigma\_2\sigma\_4\dots\ |\ w=\sigma\_1\sigma\_2\dots\sigma\_{n-1}\sigma\_n\\}$$

We need to prove that if $L\in P$ then $E(L)\in NP$.

***My Question:*** I'm finding it somehow hard or illogical to prove such a thing, that is if $L\in P$ then $E(L)\in NP$ since $E(L)$ seems to be easier than $P$ and in the same time I couldn't find a polynomial algorithm that solves it. So if someone could give a hint on how to prove or any other help I'll be thankful.

# Answer
Given a word $\sigma\_2 \sigma\_4 \sigma\_6\dots$, nondeterministically guess $\sigma\_1 \sigma\_3 \sigma\_5 \dots$ and check (in polynomial-time) whether $\sigma\_1 \sigma\_2\sigma\_3\sigma\_4\sigma\_5\dots \in L$. If that's the case, accept. Otherwise reject.
> 2 votes

---
Tags: complexity-theory, formal-languages, np
---


# Question
Title: Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$
I need to find the production rules for the following language:

$L = \\{u \in \\{a, b\\}^\* \mid |u|\_a = |u|\_b\\}$

Well, the first thing I could come up with is

$S \to aSb | \epsilon$

But this only covers the situation where all symbols $a$ precede $b$.So I tried to add all rules containing only one symbol of $a$, $b$, and one non-terminal symbol on the right-side:

$S \to aSb|bSa|abS|baS|Sab|Sba|\epsilon$

Do you think this would work?

I used this website CFG Developer and entered my productions, and for the string "bbbbaaaaabababbabababbaa" the output is false, meaning that the string cannot be produced by the mentioned rules.

Does anyone know where the mistake is?

# Answer
By your above mentioned grammar $S \to aSb|bSa|abS|baS|Sab|Sba|\epsilon$ has four redundants $abS,baS,Sab,Sba$ and one missing term is $SS.$ Because if you use $S \to aSb|bSa|\epsilon$ only after removing redundants then the strings that does starts and ends with same symbol like $abba$ is not possible to generate(but $n\_a(w)=n\_b(w)$), that's why you need to add $SS.$

Therefore your complete grammar is $S \to aSb|bSa|SS|\epsilon$
> 1 votes

---
Tags: formal-languages, automata, context-free, formal-grammars
---


# Question
Title: Worrying about details: high-level arguments about polynomial-time computability
I am learning complexity theory with a background in mathematics, and I want to better understand why certain reductions are polynomial-time computable. Let me give two examples of my worries.

**Example 1: The Cook–Levin reduction.** In the proof of the Cook–Levin theorem (say in Arora–Barak or Sipser), given a language $L\in\textbf{NP}$ and a polynomial-time verifier $M$ for $L$, we construct a reduction $f\colon x\mapsto\varphi\_x$ mapping a string $x\in\\{0,1\\}^\*$ to (an encoding of) a CNF formula that is satisfiable iff $x\in L$. It is then proven that the size of this formula is polynomial in the running time $T(n)$ of $M$. I am comfortable up to this point. But then now many authors claim that this immediately implies that the reduction $f$ is polynomial-time computable. Let me quote three books:

Sanjeev Arora and Boaz Barak, *Computational Complexity: A Modern Approach* section 2.3.4, page 49:

> Moreover, this CNF formula can be computed in time polynomial in the running time of $M$.

Michael Sipser, *Introduction to The Theory of Computation* 3e, section 7.4, pages 309–310:

> To see that we can generate the formula in polynomial time, observe its highly repetitive nature. Each component of the formula is composed of many nearly identical fragments, which differ only at the indices in a simple way. Therefore, we may easily construct a reduction that produces $\phi$ in polynomial time from the input $w$.

Michael Garey and David Johnson, *Computers and Intractability: A Guide to the Theory of NP-completeness*, section 2.6, page 44:

> All that remains to be shown is that, for any fixed language $L$, $f\_L(x)$ can be constructed from $x$ in time bounded by a polynomial function of $n=|x|$. … The polynomial boundedness of this computation will follow immediately once we show that $\text{Length}\[f\_L(x)\]$ is bounded above by a polynomial function of $n$, where $\text{Length}\[I\]$ reflects the length of a string encoding the instance $I$ under a reasonable encoding scheme, as discussed in Section 2.1.

On an intuitive level, it feels right, and I am almost willing to accept such arguments. But nonetheless I feel uneasy about it, since we are arguing at a very high-level, with no discussion of the details of a TM that computes $f$.

**Example 2: The halting problem is $\textbf{NP}$-hard.** We may argue that the halting problem $\textsf{HALT}$ is $\textbf{NP}$-hard by reducing from $L\in\textbf{NP}$ as follows: since $\textbf{NP}\subset\textbf{EXP}$, there exists an exponential-time TM $M$ deciding $L$ (doing so by brute-force searching for a certificate); we may modify $M$ to enter an infinite loop if it rejects a string $x\in\\{0,1\\}^\*$. This then gives us a reduction $x\mapsto\langle\llcorner M\lrcorner,x\rangle$ such that $x\in L$ iff $\langle \llcorner M\lrcorner,x\rangle\in\textsf{HALT}$, and intuitively this reduction is polynomial-time computable because “the modification of $M$ is quite minor”, whatever that means.

**Summary.** How do I be more comfortable with high-level arguments concerning whether certain functions are polynomial-time computable? Are there authors that write with careful attention to such details, or should I just learn to stop worrying about it? (This MathOverflow post may be relevant: https://mathoverflow.net/q/76558/)

Thank you.

# Answer
> 3 votes
The way you convince yourself of those claims is that you figure out how to write out an explicit proof of them. This same issue occurs with every mathematical proof. Every mathematical proof has some aspects that are described in detail in the proof and some claims or statements that are not explained in further detail (because it is assumed that they are obvious enough that the reader will be able to work out for themselves why they are true). So, the way you convince yourself is to spend the time to work out those details and convincing yourself that they are true. As you get more experienced, you will become adept at doing that, to the point where it is so easy that you do indeed find those statements obvious.

Example 1: How to prove that it is a polynomial-time reduction? You write an algorithm to implement $f$, and convince yourself that its running time is polynomial. It gets a bit tedious to write out the details, and once you understand the main idea for how to do the reduction, then creating the algorithm is pretty straightforward (it's more akin to writing a program than to mathematics), so many authors don't bother to go through those tedious details, but you can do it.

Example 2: Same.

---
Tags: turing-machines, reductions
---


# Question
Title: Making use of one function to recursively find n/3 of another
Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A.

This is a problem I am tasked with, and I have thought of a simple soln but I am not sure how to make it terminate:

To simply recursively call the M algorithm until I find the n/3. So it keeps halving until it finds the n/3 item.

However, since it is using recursion, how would I know when it has reached n/3 without calculating it prior?

# Answer
> 1 votes
* Take the median and the median of the first half\*.
* In the subset between these, take the median and the median of the first half\*.

Repeat the line above until the subset is a singleton.

The bounds between which the medians are taken are successively

$\[0,n), \[0,\frac n2)$

$\[\frac n4,\frac n2), \[\frac n4,\frac{3n}8)$

$\[\frac{5n}{16},\frac{3n}8),\[\frac{5n}{16},\frac{11n}{32})$

$\cdots$

The bounds converge to $\frac n3$, and the interval size each time decreases by a factor $4$. Hence the time complexity remains linear. ($n+\frac n2+\frac n4+\frac n8+\frac n{16}+\frac n{32}+\cdots=2n$)

---

\*If the median algorithm does not rearrange the small and large elements on either side of the median respectively, you need to do it yourself. That does not impair the complexity.

---
Tags: algorithms, recursion
---


title: How the indirect addressing works?

text:
# Question
Title: How the indirect addressing works?
By other words, can anyone explain how indirect addressing works?

I red MARIE's LoadI X over and over and still didnt understand the logic behind it.

```
LoadI X loads the value which is stored at address of the address X into the AC

```

Thanks for any answer.

# Answer
> 3 votes
Let the variable X contain the value 0xABC, assumed to be a valid memory address, and let the address of X be 0xDEF.

Then X denotes the value of what is stored at 0xDEF and \*X (indirect addressing) is the value of what is stored at 0xABC (not said here).

---

Without indirect addressing, there would probably be no computers, because only dumb programs could be written.

---
Tags: functional-programming
---


# Question
Title: How to incorporate Duplicate Letter Handling for Wordle?
I am trying to reverse engineer the following image. So far, the way I would take into account of duplicate letter handling is the following .

I am unsure how I could code this such that the duplicates are not colored incorrectly. For example, in my code output in the first row, the first "N" should not be yellow, but rather dark grey since the other "N" at the center is correctly placed and shaded in green. As there is only 1 N in the secret word (BANAL), then only 1 N must be shaded.

My current approach consists of the following:

```
public static char[] duplicates(char[] MysteryWordArr, char[] guessArr){
    int dup = 0; // adds up dup values
        for (int i=0; i<WORD_LENGTH; i++){
            if (MysteryWordArr[i] != guessArr[i]){
                for(int j=0; j<WORD_LENGTH; j++){
                    if ((MysteryWordArr[i] == guessArr[j])) {
                        MysteryWordArr[i] = ' ';
                    }
                else{
                    continue;
                }
                }
            }
        }
        return MysteryWordArr;
    }

```

My reasoning is that provided the char at same index of secret and guess are not the same, if the index of secret is equal to any other index of guess, then change that index of secret to a random string (in this empty). This I presumed, would mean that the duplicates would be grey as they cannot compare to their identical value in secret.

What do you think I should do.

# Answer
> 1 votes
I sat on that same issue for a couple weeks and wracked my brain over it. I finally found someone who posted the solution in Python. I was able to convert it to Visual Basic for my self and it works perfectly. Here is the code if you still need it.

```
Function Compare(Guess As String, Target as String) As String
Dim Output As String = "-----"

'Match all of the Exact Match Characters first
For i = 1 To 5
    If Guess.Substring(i - 1, 1) = Target.Substring(i - 1, 1) Then
        Output = Output.Remove(i - 1, 1).Insert(i - 1, "X")
        Target = Target.Remove(i - 1, 1).Insert(i - 1, "-")
    End If
Next

'Next Match Characters in the word but in the wrong spot
For i = 1 To 5
    For j = 1 To 5
        If (Guess.Substring(j - 1, 1) = Target.Substring(i - 1, 1)) And Output.Substring(j - 1, 1) = "-" Then
            Output = Output.Remove(j - 1, 1).Insert(j - 1, "O")
            Target = Target.Remove(i - 1, 1).Insert(i - 1, "-")
        End If
    Next
Next
Compare = Output

```

End Function

---
Tags: programming-languages, java
---


title: Definition of an $f$-speedup

text:
# Question
Title: Definition of an $f$-speedup
My question is motivated by this one

I am looking for a reference in which the definition of an $f$-speedup is provided.

Let's assume that we have an algorithmic problem to solve. This problem takes an integer $n$ as input to describe it and provides as output a bit string providing the answer we are expecting.

Then, I have two algorithms, $C$ and $Q$ to solve the task. The first one requires $C(n)$ operations while the second one requires $Q(n)$ operations.

What are the conditions that $C(n)$ and $Q(n)$ have to satisfy in order to say that the algorithm $Q$ has an $f$-speedup over the algorithm $C$.

A naïve definition would be to ask, where $\alpha$ is some constant:

$$\frac{C(n)}{Q(n)}=\Omega(f(Poly(n)))$$

With this definition, it means that I have to do "at least" $f(Poly(n))$ more operations (where $Poly(n)$ is some polynome in $n$) with the algorithm $C$ compared to the algorithm $Q$. For instance, if $f=\exp$, it would mean that the algorithm $C$ is $\exp(Poly(n))$ times longer than $Q$, hence I have an exponential speedup.

Note that in this example for $C(n)=e^{n}$ and $Q(n)=e^{0.99 n}$, we would still say that $Q$ has an exponential speedup as $C(n)/Q(n)=e^{0.001n}$

Another definition could say, for $f$ bijective:

$$C(n)=f(\Omega(Poly(Q(n)))) \Leftrightarrow f^{-1}(C(n))=\Omega(Poly(Q(n)))$$

This for for instance used here for $f(n)=2^n$ to define a superpolynomial speedup.

Overall: **what is the definition used by the community to define an $f$-speedup**, and **what is its motivation?** If it doesn't agree with one of my definitions here I would like to understand what is "bad" in my proposals.

# Answer
> 1 votes
To the best of my knowledge there is no such notion in the parallel computing community. The closest definition that I can think of is the following, that you will find in the book "Introduction to Parallel Algorithms" by C. Xavier and S. S. Iyengar (beware: its not actually used in practice):

Asymptotic Real Speedup

Let $S(n)$ be the asymptotic complexity of the best sequential algorithm for the problem and let $P(n)$ be the asymptotic complexity of the parallel algorithm under the assumption that the parallel computer has available to it as many processors as it can gainfully use. The asymptotic real speedup $ARS(n)$ is $$ARS(n) = \frac{S(n)}{P(n)}$$.

One can also define Asymptotic Relative Speedup: this differs from asymptotic real speedup, in that for the sequential complexity we use the asymptotic time complexity of the parallel algorithm when run on a single processor.

# Answer
> 1 votes
The *speedup* is the ratio of the running times of two "programs", in the same conditions. This follows a statistical distribution that is a function of the input size, which you can characterize with asymptotic $O$ and $\Omega$ bounds, as usual.

E.g. the speedup of QuickSort over InsertionSort is $\Omega(1)$ and $O\left(\dfrac n{\log n}\right)$.

---
Tags: complexity-theory
---


# Question
Title: What can be the topic of my assignment for presentation about overall computing performance?
I have received the below question for presentation. It was random assignment, its not my field. What is this specifically in Computer Architecture?

> how CPU and GPU architecture, memory bandwidth/interfaces, and storage interfaces, all combine to contribute to overall computing performance?

How and where can I get the material for its preparation? Any recommendation?

I am trying the following material (Chapter 1 & 2) if its right for above topic?

https://nap.nationalacademies.org/catalog/12980/the-future-of-computing-performance-game-over-or-next-level

# Answer
The topic cover broad range of work, It should start with

1- CPU-GPU Architecture, you can compare the latest one with the previous one in comparison section and show how it contribute towards the performance. Performance is not only based on CPU-GPU, next point should be

2- SDRAM , explain the concept of SDRAM, SDR SDRAM, DDR SDRAM, again you can compare DDR4 with DDR5

3- M.2 SSD NVMe, explain about utilizing the full capacity of SSD, you can compare it with SATA 3.0 and AHCI

4- PCIe, again compare it with PCIe 5.0 with PCIe 4.0

5- Explain about the motherboard.

All these major component contribute towards the performance of the system.
> 1 votes

---
Tags: computer-architecture, cpu, performance, high-performance-computing
---