# Question
Title: MergeSort's merge function loop invariant
I am reading a proof of correctness for the MergeSort Algorithm. This is the code for the MergeSort and the Merge function:

The correctness of the MergeSort function is easy to prove since the two `MergeSort` recursive calls decrease the size of the problem by half, which guarantees the convergence to the base case ($p = r$). Furthermore, assuming the first recursive call to `MergeSort` leaves the array `A[p..q]` sorted and the second recursive call leaves `A[q+1..r]` sorted, it is clear that merging the subarrays `A[p..q]` and `A[q+1..r]` will leave the array `A[p..r]` sorted. However, the key thing here is proving the correctness of the `Merge` function.

Cormen's book suggests the following invariant for the main loop in the `Merge` function (lines from 12 to 17):

1. The subarray $A\[p\ldots(k−1)\]$ consists of the $k−p$ smallest elements of $L\[1\ldots(n\_1 + 1)\]$ and $R\[1\ldots(n\_2 + 1)\]$, in sorted order.
2. The elements $L\[i\]$ and $R\[j\]$ are the smallest elements of their arrays that have not been copied back to $A$.

I understand this invariant and the full proof (Initialization, Maintenance, and Termination). However, the above invariant is mostly written in natural language, and I wonder if there is a more formal way to state it. This is because I need a more rigorous proof that need not rely on natural language. For example, to verify the program with a theorem prover I can't use natural language at all.

#### Update

@Dmitry suggested a different invariant that requires using the concept of permutation. However, Coq's axioms of permutation look really complicated. Is there a simpler way to formally prove the Merge function without resorting to Coq's axioms or other external libraries?

# Answer
# Merge function proof of correctness

Let $A'\[p \ldots r\]$ be a copy of the array $A\[p\ldots r\]$ right after entering the Merge function.

### Precondition

$0 \leq p \leq q \lt r$

$\forall p\leq x\leq r: A'\[x\] \neq \infty$

$A'\[p\ldots q\]$ and $A'\[q+1\ldots r\]$ are sorted in ascending order.

### Postcondition

Permutations can be formalized by using the concept of bijection. We say that $A\[p \ldots r\]$ is a permutation of $A'\[p \ldots r\]$ (or vice versa) if and only if:

There exists a bijection $F : \\{p \ldots r\\} \rightarrow \\{p \ldots r\\}$ such that $\forall p \le x \le r : A\[x\] = A'\[F(x)\]$

Furthermore, if we want to verify that $A\[p \ldots r\]$ is sorted in ascending order, we just need to add another constraint:

$\forall p\leq x \lt r : A\[x\] \leq A\[x + 1\]$

These two expressions will be the Postcondition of the Merge function.

### Loop invariant

We can craft an invariant by weakening the postcondition:

$\varphi:$ There exists a bijection $F : \\{p\ldots k-1\\} \rightarrow \\{p \ldots p+i-2\\} \cup \\{q+1\ldots q+j-1\\}$ such that

$\forall p \leq x \leq k-1 : A\[x\] = A'\[F(x)\]$. Furthermore $\forall p\leq x \lt k-1 : A\[x\] \leq A\[x + 1\]$.

We still need to add some properties to the invariant. These are required for proving the termination step:

* $i \leq q-p+2$
* $j \leq r-q+1$
* $k = p+j+i-2$
* $p \leq k \leq r + 1$

and these are required for proving the maintenance step:

* $\forall 1 \leq x \leq q-p+1 : L\[x\] = A'\[p+x-1\]$
* $\forall 1 \leq x \leq r-q : R\[x\] = A'\[q+x\]$
* $\Psi: \forall p \leq x \leq k-1 : A\[x\] \leq min(L\[i\],R\[j\])$
* $L\[q-p+2\] = R\[r-q+1\] = \infty$
* $A'\[p\ldots q\]$ and $A'\[q+1\ldots r\]$ are already sorted. This is part of Merge's precondition.

Now, let us calculate the continuation condition $B$ and exit condition $\neg B$ of the loop (line 12). We know from the pseudocode that $B$ is $k \leq r$. We can see this more clearly if we translate the `for k = p to r` loop into a normal for loop: `for(k = p; k <= r; k++){ ... }`. As we can see, the loop will continue provided that $k \leq r$. Therefore, the exit condition will be $\neg B$, that is $k \gt r$. However, since the invariant asserts that $k \leq r + 1$, we can simply consider that the exit condition is $k = r + 1$.

### Initialization step

$Pre \wedge (k = p) \wedge (i = 1) \wedge (j = 1) \implies Inv$

$k = p$ leads to the empty domain $\\{p\ldots p-1\\}$. Universal quantification over an empty domain is trivially true. The rest of the properties of the invariant are easy to prove by just substituting the values of the variables in the first iteration ($k = p$, $i = 1$, $j = 1$).

### Maintenance step

The general rule for proving maintenance is: $\\{Inv \wedge B\\}$ $S$ $\\{Inv\\}$, being $S$ the set of instructions in the loop body.

The maintenance of the following invariant properties need not be proved:

$\forall 1 \leq x \leq q-p+1 : L\[x\] = A'\[p+x-1\]$

$\forall 1 \leq x \leq r-q : R\[x\] = A'\[q+x\]$

$L\[q-p+2\] = R\[r-q+1\] = \infty$

$A'\[p\ldots q\]$ and $A\_1\[q+1\ldots r\]$ are already sorted.

since $A'$, $L$, $R$, $p$, $q$ and $r$ are not modified during the execution of the loop.

For the rest of the properties, we are going to prove their maintenance by considering the two possible cases that can occur (either $L\[i\] \leq R\[j\]$ or $L\[i\] \gt R\[j\]$):

(a) $Inv \wedge B \wedge (L\[i\] \leq R\[j\]) \wedge (A\[k\] = L\[i\]) \implies ((Inv)\_{i+1}^{i})\_{k+1}^{k}$

1. Maintenance of $p \leq k \leq r + 1$

$p \leq k \leq r + 1 \wedge B \implies (p \leq k \leq r + 1)^{k}\_{k+1}$

$p \leq k \leq r + 1 \wedge k\leq r \implies p \leq k+1 \leq r + 1$

$p \leq k \leq r \implies p \leq k+1 \leq r + 1$

2. Maintenance of $k = p+j+i-2$

At the end of the iteration, both $k$ and $i$ will have incremented by one with respect to their previous value, and $j$ will remain unchanged. Hence, the equality $k = p+j+i-2$ will be preserved.

3. Maintenance of $i \leq q-p+2$ and $j \leq r-q+1$.

The variable $j$ remains unchanged so $j \leq r-q+1$ is maintained.

The variable $i$ cannot grow larger than $q-p+2$ because if $i = q-p+2$, then $L\[i\] = \infty$, and the condition $L\[i\] \leq R\[j\]$ (line 13) will fail provided that $R\[j\] \neq \infty$, or equivalently, $j \neq r-q+1$. Now, suppose $i = q-p+2$ and $j = r-q+1$ occur at the same time:

$Inv \wedge \color{red}{B} \wedge (i = q-p+2) \wedge (j = r-q+1)\implies$

$(k = p+j+i-2) \wedge (i = q-p+2) \wedge (j = r-q+1) \implies k = r + 1 \implies \color{red}{\lnot B}$

This is a contradiction, therefore, $i = q-p+2$ and $j = r-q+1$ cannot occur at the same time provided $Inv \wedge B$.

4. Maintenance of $\varphi$

$Inv \wedge B \wedge (L\[i\] \leq R\[j\]) \wedge (A\[k\] = L\[i\]) \implies ((\varphi)^{i}\_{i+1})^{k}\_{k+1}$

We want to prove that $((\varphi)^{i}\_{i+1})^{k}\_{k+1}$, that is:

There exists a bijection $F : \\{p\ldots k\\} \rightarrow \\{p \ldots p+i-1\\} \cup \\{q+1\ldots q+j-1\\}$ such that

$\forall p \leq x \leq k : A\[x\] = A'\[F(x)\]$. Furthermore $\forall p\leq x \lt k : A\[x\] \leq A\[x + 1\]$.

We will do this in two steps. First we are going to prove $\forall p\leq x \lt k : A\[x\] \leq A\[x + 1\]$.

We know from $\Psi$ that $\forall p \leq x \leq k-1 : A\[x\] \leq min(L\[i\],R\[j\])$. Since $L\[i\] \leq R\[j\]$, then $\forall p \leq x \leq k-1 : A\[x\] \leq L\[i\]$. Since $A\[k\] = L\[i\]$, then $\forall p \leq x \leq k-1 : A\[x\] \leq A\[k\]$.

We know from $\varphi$ that $\forall p\leq x \lt k-1 : A\[x\] \leq A\[x + 1\]$. We can conclude that:

$$(\forall p\leq x \lt k-1 : A\[x\] \leq A\[x + 1\]) \wedge (\forall p \leq x \leq k-1 : A\[x\] \leq A\[k\]) \implies$$ $$\forall p\leq x \lt k : A\[x\] \leq A\[x + 1\]$$

Let's continue with the second part.

Let there be a bijection $F : \\{p\ldots k-1\\} \rightarrow \\{p \ldots p+i-2\\} \cup \\{q+1\ldots q+j-1\\}$ such that

$\forall p \leq x \leq k-1 : A\[x\] = A'\[F(x)\]$.

Since $A\[k\] = L\[i\] = A'\[p+i-1\]$, we can construct another bijection $F' : \\{p\ldots k\\} \rightarrow \\{p \ldots p+i-1\\} \cup \\{q+1\ldots q+j-1\\}$ such that

$\forall p \leq x \leq k : A\[x\] = A'\[F'(x)\]$.

5. Maintenance of $\Psi$

$Inv \wedge B \wedge (L\[i\] \leq R\[j\]) \wedge (A\[k\] = L\[i\]) \implies ((\Psi)^{i}\_{i+1})^{k}\_{k+1}$

$\Psi: \forall p \leq x \leq k-1 : A\[x\] \leq min(L\[i\],R\[j\])$

Since $A\[k\] = L\[i\]$ and $L\[i\] \leq R\[j\]$, then $A\[k\] \leq min(L\[i\],R\[j\])$

Since $L\[i\] \leq L\[i+1\]$, then $min(L\[i\],R\[j\]) \leq min(L\[i+1\],R\[j\])$

Therefore, $\forall p \leq x \leq k : A\[x\] \leq min(L\[i+1\],R\[j\])$

(b) $Inv \wedge B \wedge (L\[i\] \gt R\[j\]) \wedge (A\[k\] = R\[j\]) \implies ((Inv)\_{j+1}^{j})\_{k+1}^{k}$

The proof of (b) is analogous to (a).

### Termination step

First, we can derive that $Inv \wedge (k = r + 1)$ implies $(i = q-p+2)\wedge(j=r-q+1)$.

Proof:

$(k = r+1) \wedge (k = p+j+i-2) \implies r+1=p+j+i-2$

The system of equations

$$r+1=p+j+i-2$$

$$i \leq q-p+2$$

$$j \leq r-q+1$$

has only one solution for $(i,j)$: $i = q-p+2$ and $j = r-q+1$. If there was another solution for $(i,j)$, then $p+j+i-2 \lt r+1$, which contradicts $r+1=p+j+i-2$.

---

The above makes proving $Inv \wedge \lnot B \implies Post$ much easier:

$Inv \wedge (k=r+1) \implies Inv \wedge (k=r+1) \wedge (i=q-p+2) \wedge (j=r-q+1) \implies Post$

# Merge's proof of terminality

By the invariant we know that $k \leq r + 1$. Also, we know that the exit condition of the loop is $k = r + 1$. Since the $k$ variable is always incremented by one on each iteration, we can be sure that $k$ will eventually reach $r + 1$, causing the loop to exit. This can be reflected via the following bound function:

$\tau(k) = r + 1 - k$

We can verify that $\tau(k)$ holds the following properties:

* $Inv \wedge B \implies \tau(k) \gt 0$

Proof: $Inv \wedge B \implies B \implies k \leq r \implies r - k \geq 0 \implies r + 1 - k \gt 0$

* $\tau(k) = V \implies \tau(k + 1) \lt V$

Proof: $\tau(k + 1) = r - k = \tau(k) - 1 = V - 1 \lt V$

The first property ensures that when $\tau(k)$ reaches a value less than or equal to $0$, the loop will exit.

The second property ensures that $\tau(k)$ decreases strictly upon each iteration.

Therefore, the loop will always halt.
> 0 votes

---
Tags: algorithm-analysis, formal-methods, software-verification, loop-invariants, automated-theorem-proving
---


title: Possible reduction from SUBSET-SUM

text:
# Question
Title: Possible reduction from SUBSET-SUM
Given is a multiset $S$, a finite set $T = \\{t\_1, t\_2, t\_3\\}$, and an integer $k \in \mathbb{N}$.

Let $v(t\_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s\_i$, and $c(t\_j)$ be the cost of assigning $v(t\_j)$ to $s\_i$. Since $S$ is a multiset, assigning $v(t\_j)$ to $s\_i$ will affect every occurrance of $s\_i$.

Given that $v(t\_j)$ and $c(t\_j)$ are known, which assignment of $v(t\_j)$ to $s\_i$ gives a value ($\sum\_{s\_i \in S}$) either equal to or as close as possible to $k$ that has the least cost?

**Start of example**

$S=\\{s\_0, s\_1, s\_2, s\_3, s\_4, s\_5, s\_4, s\_3, s\_2, s\_1\\}$, $k = 100$,

$v(t\_j) = \\{5, 12.5, 50\\}$, and $c(t\_j)=\\{10, 100, 1000\\}$.

We observe that the multiplicity of $s\_1,s\_2,s\_3,s\_4$ is $2$. Thus, assigning $t\_2$ to those elements in the set gives $12.5 * 2 * 4 = 100$, and a cost of $c(t\_2) * 4 = 400$.

**End of example**

Now, I am suspecting the SUBSET-SUM problem can be reduced to this problem. As far as I know, however, SUBSET-SUM specifies that the values either sum up to exactly $k$, OR is at most $k$, being as close as possible.

Assume $k = 100$, but the values of $v(t\_j)$ are different. Then, assume two solutions that are just as close to $k$, but the first being less than $k$ and the last being greater than $k$, e.g., $98$ and $102$. Also, the cost of the first solution larger than the last.

Of course, the cheapest solution is the preferred one, but the value is greater than $k$; can the solution yielding $102$ be considered a solution at all?

When it comes to attempting to reduce SUBSET-SUM to this problem, I am not sure where to start, but I can definetly see the relation between them. I am looking for guidelines on how to go about the reduction, if it actually is possible.

# Answer
> 0 votes
After some research, this problem seems more related to KNAPSACK rather than SUBSET-SUM. From Garey & Johnson (1979)\[p.247\], **KNAPSACK is defined as:**

Instance: Finite set $U$, for each $u \in U$, a size $s(u) \in \mathbb{Z^+}$ and a value $v(u) \in \mathbb{Z^+}$, and positive integers $B$ and $K$.

Question: Is there a subset $U' \subseteq U$ such that $\sum\_{u \in U'}s(u) \leq B$ and such that $\sum\_{u \in U'}v(u) \geq K$?

Comments: If $v(u) = s(u)$ for all $u \in U$, then the problem is SUBSET-SUM.

**The problem in question can be re-formulated as:**

Finite sets $S$ and $T = \\{t\_0, t\_1, t\_2, t\_3\\}$, for each $t \in T$, a cost $c(t) \in \mathbb{Z^+}$ and a value $v(t) \in \mathbb{Z^+}$, and a positive integer $K$. Let $v(t)$ be a value that can be assigned to any $S \in S$, and $c(t)$ be the cost of assigning $v(t)$. $|T| = |v(t)| = |c(t)| = 4$ for all instances of the problem.

Let $Q = \\{s\_1t\_0, s\_1t\_2, s\_1t\_2, s\_1t\_3, \dots, s\_it\_3\\}$ be the set containing every possible assignment, such that $|Q| = |T|^{|S|} = 4^{|S|}$ Then, let $c(q)$ be the cost of assigning $t$ to $s$, and $v(q)$ be the value of the assignment.

Instance: Finite set $Q$, for each $q \in Q$, a cost $c(q) \in \mathbb{R^+}$ and a value $v(q) \in \mathbb{R^+}$, and a positive integer $K$.

Question: Is there a subset $Q' \subseteq Q$ such that $\sum\_{q \in Q'} \geq K$?

Final remarks: We can observe that by constructing the set $Q$, the problem formulation is nearly identical with Garey & Johnson's formulation of KNAPSACK. The only notable difference I can see is that the problem in question does not have a capacity $B$. This "constraint" can be added for a reduction, but is somewhat trivial. Also note that $S$ is now denoted as a set, not a multiset, e.g., a set of all the unique elements in the set $S$ from the original question.

---
Tags: complexity-theory, np-complete, reductions, np-hard, subset-sum
---


# Question
Title: Proving $L=\{wvw|v\in \{0,1\}^*, w\in \{0,1\}^+\}$ is not regular using the myhill-nerode and pumping lemma
Firstly, I've tried assuming $L$ is regular and find a contradiction with help of the pumping lemma's 3 conditions, I was not able to get to a contradiction.

I've tried thinking of a word $z\in \\{0,1\\}^\*$ to attach to $wv^i$ and $wv^j$ for some $i\neq j$, and to combine that with the pumping lemma's $xy^2z\in L, k\geq 1$ yet I got stuck on the way.

I'm looking for a direction of thought, a colleague suggested looking at the example word $10000000110000000$ , yet I cant see the how this example promotes what I'm trying to prove.

# Answer
> 1 votes
This language is regular. Denote $L = \\{wvw\mid v,w\in\\{0,1\\}^\*\\}$.

I claim $L = \\{0,1\\}^\*$. Indeed, the inclusion $\subseteq$ is clear. Conversely, let $u\in \\{0,1\\}^\*$. Then $u = \varepsilon u\varepsilon \in L$.

# Answer
> -1 votes
Of course it is regular, because it contains the complete set {0,1}\*.

Note: This was the correct answer to the question before it was edited.

---
Tags: pumping-lemma
---


# Question
Title: Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?
The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (`replaceme` and `withme`), it takes a keyed set of `N` `[before, after]` pairs as an argument, and for each pair in the set, replaces all instances of `<before>` in the string with `<after>`.

For example, if we have this initial string:

```
three point one four one five

```

... and our set of `[before, after]` pairs looks like this:

```
[one, two]
[two, three]
[three, four]
[four, five]
[five, six]

```

... then after the operation completed, our updated string would be:

```
four point two five two six

```

The intuitive (but wrong) way to implement this would be to just iterate over the set and do a traditional search-and-replace for each pair in series. That works for cases where the values in the set are unrelated, but it fails in other cases (such as our example above) because the later iterations inappropriately operate on the results of the earlier operations. So doing it that way yields an incorrect result like this:

```
six point six six six six

```

My question is, there any well-known algorithm for handling this operation efficiently? I was able to come up with an algorithm that seems to accomplish it, but I suspect there might be a better way to do it than my hackish approach.

# Answer
> 1 votes
In principle: Starting with position I=0, check if one of your original strings is stored at position I. If not, increase i by 1. If yes, replace the string and set I = I + length of replacement. Note that an empty string as original string cannot be allowed.

To optimise: Make a table with the starting characters, look from position I until you find one of the starting characters, reducing the number of long comparisons.

# Answer
> 3 votes
You can build an Aho-Corasick automata for the before words, run your string through it, and whenever you find a match go back in the string and replace it with the after value, and then reset the automata. This takes linear time (in the length of both the input and output).

# Answer
> 1 votes
Well yeah, the Trie algorithm is a well-known technique for effectively performing this task. This technique can efficiently conduct numerous search-and-replace operations in a single pass over the input text, avoiding the problems that occur when the operations are performed in succession.

The temporal complexity of this approach is O(n + k), where n is the length of the input string and k is the total length of all 'before' strings. This is significantly quicker than doing the operations sequentially, which has a temporal complexity of O(n\*k).

and also there are several Trie algorithm implementations available in many programming languages, thus it should be very simple to implement in your unique use case.

# Answer
> -1 votes
Store original: replacement in a map. Make an empty output string. Run through the string and word by word find new word using map and concatenate with output. return output.

---
Tags: algorithms, strings, c++
---


# Question
Title: Prove a language created by applying a function on a regular language is regular
Let $L$ be a language over $\Sigma=$ {$a,b,c$}

We define $\forall w\in \Sigma ^{\*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$.

Let $T(L)=${$ T(w) : w\in L$}, we need to show that if $L$ is regular, than so is $T(L)$.

I've came to mind of an approach, which consists of claiming there is a DFA/NFA $M\_L$ that accepts $L$, constructing a DFA/NFA $M\_{T(L)}$ that works for $T(L)$ and proving it's correctness, and then proving that $L(M\_L)=L(M\_{T(L)})$ by showing two-way inclusion. (basically $\subseteq$ and "the other way around").

Thing is, I feel that this approach is overdoing it, and that there is a shorter "path" to prove this.

Unsure in which direction to take this.

# Answer
If $L$ is regular then it has a NFA $M\_L$. I think you can answer your problem if you can answer the following:

* If for all $w \in L$, $w$ has no $a$, then what would can you say about the elements of $T(L)$?
* If for some $w \in L$, $w$ has an $a$ then there must be some transition in $M\_L$ that consumes an $a$. Now, if all instance of $a$ is removed in all $w \in L$, what happens to the transitions in $M\_L$ that consumes an $a$?
> 2 votes

# Answer
No, you are not overdoing this. Formally all these steps need to be established. In practise the equivalence step might be skipped, when the constructed automaton "obviously" is doing what it is claimed to do.

On the other hand a formal proof is not that hard. The new automaton might be one where the letter $a$ is replaced by the empty word $\varepsilon$. Now there is a one-to-one correspondence between computations of the two automata, which helps formalities.

Another option might be to work with regular expressions. If you have an expression for $L$, then the expression for $T(L)$ is found by deleting $a$'s. Intuitively clear. The formal proof would need a proof with induction (on the structure of the expression) I guess.

By the way. Your closure property is a special case of closure under homomorphisms.
> 1 votes

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


# Question
Title: Dividing a list of files with constraints
I don't know if a solution to this problem is too complicated to figure out, but I've been banging my head on it for a couple weeks, so I'm hoping for an outside point of view.

I have a list of 88 files today from different sources:
Alpha sent 9 files.
Beta sent 7 files.
Gamma sent 19 files.
Delta sent 13 files.
Epsilon sent 20 files.
Zeta sent 20 files.

I need to divide them up between Ann, Bob, Charley, and Ren.

Ren always gets all the files from Delta, but can receive more.
There are a couple processors that have assigned customers, while everyone else just assigned to a processor at random.

Ann can only get 15 files today.
This is an example of a processor with a max file limit. Say someone has other projects they are working on, or is recovering from being sick, or has family stuff going on, or whatever, and their manager decides to give them a lighter load. Instead of dividing them evenly among all 4 and then have to reassign work after the fact they can set the limit ahead of time.

The main question is how do I divide them up as evenly as possible, so Ann gets 15, and the other 3 get close to the same amount?
"Close to the same amount" means to divide it as evenly as possible, with any remainder passed out to someone, so in the example Bob got 25, while Charley and Ren got 24, because 73/3 = 24 with a remainder of 1.

The optimal solution that I worked out manually for this data set was:
Ann: 15 files
Bob: 25 files.
Charley: 24 files.
Ren: 13 Delta files, and 11 additional files, bringing her total to 24.

The variables are the number of files, the number of people who get files, and the maximum number that they can each receive. Also, left out to remove some complexity, but Ren ALWAYS gets all the files from Delta, even if she has the day off, but she won't get any other files in that instance.

# Answer
> 0 votes
After a lot of thought and trial and error, this is the solution that I believe solves my problem:

1. Get list of processors that are selected to get files with the limit they are allowed to receive, and their current count initialized at 0.
2. Get a list of all designated processors and file sources.
3. Loop through the list of files and see if each one needs to be assigned to a designated processor. If so put it in their queue, subtract one from their allowed limit, and add 1 to their current count. If not then put the file in a file queue to be passed out.
4. Calculate the rolling average that each processor should receive by dividing the file queue count by the number of processors.
5. While there are still files in the queue, and processors that still haven't reached their max:
a. Loop through the list of processors sorted by their allowed limit ascending.
b. Dequeue a file and give it to the processor, subtract 1 from allowed limit, add 1 to current count.
c. check to see if they have reached the rolling average or their allowed limit. If so go to next processor, else go to next file.
6. Once all processors have reached the rolling average, if there are still files to be passed out, and if there are any processors that haven't reached their limit, then re-calculate the rolling average, adding the total to the original total. Go to 5.

Pseudo code:

```
For each selected processor
    SelectedProcessorList.Add with ID, FileLimit, CurrentCount = 0

Get list of DesignatedProcessors and Sources
For each file
    If the file Source belongs to a DesignatedProcessor
        Assign to DesignatedProcessor
        Add 1 to CurrentCount
        Subtract 1 from FileLimit
    Else
        FileStack.Enqueue(file)
Next file

RollingAverage = FileStack count / SelectedProcessorList count

While FileStack count > 0 and SelectedProcessorList(with FileLimit > 0) count > 0
    For each Processor in SelectedProcessorList Order by FileLimit
        While FileStack count > 0
            File = FileStack.Dequeue
            Assign File to Processor
            Add 1 to CurrentCount
            Subtract 1 from FileLimit
            If Processor CurrentCount >= RollingAverage Or Processor FileLimit < 1 Then
                Exit While
        Loop While
    Next Processor
    If all Processors have been assigned work, And any Processor has a FileLimit > 0 then
        RollingAverage += Math.Ceiling(FileStack count / SelectedProcessorList(Where FileLimit > 0) count)
Loop While

```

---
Tags: algorithms
---


title: Threads and its priority in Java

text:
# Question
Title: Threads and its priority in Java
I was experimenting with the concept of threading in java, we have a method setPriority, using which we can set thread priority. In official documentation it is given as below,

But while seeing in actual execution, I observed something else, threads were executed normally as before without priority, on researching I found out that a thread will only run as per priority if there is a constraint with the system that is low memory, cpu, etc otherwise it will execute randomly since the system has no reason to stop other thread execution as we have ample amount of resources.

Having said that, I understood the context but what will happen if I have some real-time uses cases, where a delay of even milliseconds is not bearable? What is your understanding of it, how do I force priority-wise execution? Thanks in advance for sharing your wisdom :)

# Answer
> 1 votes
Operating systems don't always let a user control thread priority in the way that a programmer would like, and certainly not without extra privileges.

General-purpose operating systems have multiple classes of task priority. For example, you may find (in decreasing order of "priority"):

* A few very high priority levels only accessible by the operating system itself (e.g. for kernel tasks or device drivers).
* User-space real-time fixed-priority tasks.
* User-space timeshared variable-priority tasks.
* User-space low-priority tasks.
* Idle tasks, which should only run when absolutely nothing else needs to run.

As well as priority (i.e. what should run), another thing that may be class-dependent is preemption. A system task would typically be non-preemptable, but a real-time task might be able to choose for itself whether or not it can be preempted.

A task would typically need permission to run in a higher-priority class. This is a security matter; if any task can decide itself to be non-preemptable, then any buggy or malicious task could take over the system and prevent, say, user interaction. You can imagine how malware might make use of this.

So this may be part of the answer to your question: Your task may not have permission to elevate its priority quite that far.

(Just to complicate things further, in microkernel and hybrid operating systems, some scheduling may occur outside the microkernel, and so a task might have different kinds of priority depending on who is doing it. This is the case in macOS, for example, and it's why a task has two separate priorities: the "Mach priority" and the "BSD priority". But I digress.)

A typical example of variable-priority timesharing scheduling is the Unix timesharing system, which might reserve 100 or so priority levels for user-space threads, and a thread's priority is determined by what it's doing. A thread which relinquishes the CPU because it is waiting for I/O, for example, will get a higher priority than one which exhausts its quantum.

The theory is that threads that wait tend to be more "interactive", so the system as a whole would feel more responsive if they got priority.

Within these constraints, a task can tell the operating system that it is more or less important/urgent, but that would typically be implemented as an adjustment on top of the timesharing scheduling system.

Exactly how the Java runtime implements thread priorities on top of the operating system is OS-dependent. Windows, for example, only has seven user priority levels, which is fewer than the Java API, and so the mapping will inevitably map some distinct Java priorities onto the same OS priority.

But even if there are a lot of priority levels available, the OS is free to interpret a thread priority however it wants. So this is possibly the other answer to your question: Even if your task has permission to elevate its priority to be real-time, the JDK may not provide a way to do it.

---
Tags: threads, java
---


# Question
Title: Reconstructing a string from two its partitions into substrings of varying size
Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice.

Under an *unordered partition* of a string I understand a multiset composed of the parts of any partition of this string into substrings (without overlaps). For example, $\\{ aa, aa, abb \\}$ is an unordered partition of a string $aaabbaa$ (since it can be partioned as $aa|abb|aa$).

I'm interested in the regime when the original string has length $n$ and the substrings have varying lengths within $O(\log n)$.

What would be a practical algorithm for this problem?

# Answer
> 3 votes
This problem, or at least one interesting variant of it, is **NP-complete** even for binary alphabets and word lengths at most logarithmic in the total number $p$ of partition parts, so it's very unlikely that a polynomial-time algorithm can be found. I have some ideas about ways to reduce the $O(p!)$ time complexity of a naive algorithm to "just" exponential, but that will have to wait for another post -- please let me know if that would be interesting.

# Promise problem vs. unrestricted decision problem

Your framing of the problem implies that a solution is guaranteed to exist -- that is, you have formulated it as a promise problem, with the promise being that the two partitions do derive from some common underlying string. I wasn't able to make progress on this version of the problem. (This is perhaps not too surprising, since it turns out that checking whether this promise holds for an unrestricted instance is itself hard -- but note that this hardness of verification does not rule out the possibility that a more efficient algorithm exists that takes advantage of the promise in some clever way.)

In the remainder, I'll consider the more general underlying search and decision problems, in which we may *not* assume that any solution exists. It's possible that this is actually the variant you are interested in anyway -- certainly, if your intention is to actually apply an algorithm for the problem to noisy real-world data, then this is the right variant to consider, since an algorithm that assumes the promise holds is allowed not to terminate on inputs that violate the promise.

# Definitions

An unordered partition (subsequently *partition*) *supports* a string if concatenating the partition's parts (or *words*) in some order produces the string. An *alignment* is an ordered sequence of words from one partition written above an ordered sequence of words from another partition and such that the 2 characters at each horizontal position are equal.

I'll call your problem **Reconstruct String from 2 Partitions (RS2P)**. The search problem version is: Given 2 multisets of words, containing $p\_1$ and $p\_2$ words, respectively, with each multiset having total length $q$, find a string of length $q$ that they both support, or report that this is impossible. Define $p=p\_1+p\_2$.

The decision version of this search problem returns YES if some such length-$q$ string exists, and NO otherwise. (Note that the decision and search problems are polynomially equivalent: Given an algorithm for solving the decision problem, the search problem can be solved by trying each of the $p\_1p\_2$ combinations of words from the first and second partitions and such that one is a prefix of the other as the leftmost part of the solution in turn, and for each such combination removing the shorter word from its partition and cutting off the corresponding first part of the longer word, and solving the decision problem on the remainder; whenever the resulting subproblem has a YES solution, that combination is the leftmost part of a solution to the original problem, and can be fixed in place.)

# NP-completeness proof

I'll show NP-completeness by reducing the NP-complete problem of finding a **Hamiltonian Cycle in a digraph (HCD)** to it. This is research-level original work; if you're interested in publishing academic work that makes use of it, please let me know in a comment so that we can discuss credit.

For simplicity, in this proof I'll consider a variant of the problem in which the alphabet is $\\{1, \dots, n\\}$, plus a handful of additional special characters ("colours"). The argument can be straightforwardly transferred to the case of a binary alphabet by expanding each character to its $\lceil\log\_2(n+4)\rceil$-digit binary representation (these blocks of size $\lceil\log\_2(n+4)\rceil$ necessarily align to each other in any solution, since nothing could fill the smaller gap that would otherwise be left).

The basic idea is to represent each arc $(v\_i, v\_j)$ in the original digraph as a 4-character word $v\_ibbv\_j$ in partition 1, and set partition 2 to contain $n-1$ 4-character words, one word $bv\_iv\_ib$ for each vertex $v\_i$ except for $v\_n$. A path through the original digraph corresponds to a sequence of 4-character words from partition 1 that "match like dominoes" (the last character in one word equals the first character in the next), so some ordering of the $n$ words from partition 2, *after being right-shifted by 2 positions*, will match them and help to enforce a Hamiltonian Path property. The main difficulty is in dealing with the "leftover edges" in partition 1 in a sufficiently strict way -- specifically, ensuring that the additional gadgets used for collecting them extract individual edges, rather than paths.

Given an instance $G = (V, A)$ of HCD with $n=|V|$ vertices and $m=|A|$ arcs, we construct an instance of RS2P as follows:

* Set the alphabet to be $\\{1, \dots, n\\} \cup \\{w, b, r, g\\}$ (the latter can be thought of as white, black, red and green, respectively).
* Set partition 1 to contain the words:
    + $v\_ibbv\_j$ for each arc $(v\_i, v\_j) \in A$ (the "edge words")
    + $w$
    + $r$ (the "end word")
    + $m-n$ copies of $rg$
* Set partition 2 to contain the words:
    + $bv\_iv\_ib$ for each $1 \le i \le n-1$ (the "Hamiltonian words")
    + $wv\_nb$ (the "start word")
    + $bv\_nr$ (the "mid word")
    + $\deg\_+(v\_i)-1$ copies of $gv\_ibb$ for each $1 \le i \le n$ (the "out-gathering words"), where $\deg\_+(v\_i)$ is the outdegree of $v\_i$ in $G$
    + $\deg\_-(v\_i)-1$ copies of $v\_ir$ for each $1 \le 1 \le n$ (the "in-gathering words"), where $\deg\_-(v\_i)$ is the indegree of $v\_i$ in $G$

Recall that $\sum\_i\deg\_+(v\_i)=\sum\_j\deg\_-(v\_j)=m$, so there are $m-n$ total out-gathering words in partition 2, and the same number of in-gathering words.

## A YES answer to the HCD instance $\implies$ a YES answer to the constructed RS2P instance:

We know a HC exists. Let $s\_1$ be the string formed by concatenating words from partition 1 in the following order:

* $w$
* All edge words corresponding to edges in the HC, starting from the unique edge in it that leaves $v\_n$
* $m-n$ 2-word blocks, in any order, each consisting of:
    + $rg$
    + An edge word $v\_ibbv\_j$ corresponding to a "leftover" edge (an edge not partiticipating in the HC)
* $r$

Let $s\_2$ be the string formed by concatenating words from partition 2 in the following order:

* $wv\_nb$
* All $n-1$ Hamiltonian words, with each matching the two edge words it overlaps in $s\_1$
* $bv\_nr$
* $m-n$ 2-word blocks, each matching the "leftover" edge $v\_ibbv\_j$ it overlaps in $s\_1$ and consisting of:
    + $gv\_ibb$
    + $v\_jr$

The diagram below shows an example digraph with a YES answer, and the solution to its corresponding RS2P construction. Vertices and their corresponding characters are shown in pastel colours.

## A YES answer to the constructed RS2P instance $\implies$ a YES answer to the HCD instance:

### "Leftover blocks" form a chain of length exactly $m-n$

If $m=n$ then the end word $r$ in partition 1 necessarily aligns with last character of the mid word $bv\_nr$ in partition 2, and we are done.

Otherwise, each out-gathering word $gv\_ibb$ in partition 2 must align to a word pair $rg|v\_ibbv\_j$ for some $j$ in partition 1, since partition 1 has no other words besides $rg$ that contain $g$, and the only words in partition 1 beginning with $v\_i$ are the edge words. The overhanging $v\_j$ that remains in partition 1 can only align to a corresponding in-gathering word $v\_jr$ in partition 2, since partition 2 contains no other words beginning with any $v\_k$. This implies that in any solution, there exist $m-n$ of these "leftover blocks", each of the form $rg|v\_ibbv\_j$ "on the top" (in partition 1) and $gv\_ibb|v\_jr$ "on the bottom" (in partition 2), each having an $r$ character overhanging at the top-left, and an $r$ character overhanging at the bottom-right. The rightmost-ending such block must have its overhanging-on-the-bottom $r$ aligned to the end word $r$ in partition 1, since otherwise it must align with the overhanging-on-the-top $r$ of some other leftover block, implying it is not the rightmost-ending such block: a contradiction. Similarly, the leftmost-beginning such block must have its overhanging-on-the-top $r$ aligned to the end of the mid word $bv\_nr$ in partition 2, since otherwise it must align with the overhanging-on-the-bottom $r$ from some other leftover block, implying it is not leftmost-beginning: a contradiction. Since the leftover blocks exhaust the remaining occurrences of $r$ characters in both partitions, their overhangs must overlap sequentially to form a dense chain that begins with the mid word $bv\_nr$ in partition 2, contains all $m-n$ leftover blocks with no other words from either partition, and ends on the bottom with a leftover block, the final $r$ of which aligns to the $r$ word on the top. Call this chain of blocks, beginning with the mid word $bv\_nr$ jutting out 2 characters to the left on the bottom, and ending "flush" with aligned $r$ characters, the *leftover chain*.

### The leftover chain is at the right end

We now establish that none of the remaining words in partition 2 (and, thus, none of the remaining words in partition 1) can appear to the right of the leftover chain.

With exactly $m-n$ edge words used up inside the leftover chain, $m-(m-n)=n$ edge words, plus the word $w$, remain in partition 1. The start word $wv\_nb$ and the $n-1$ Hamiltonian words remain in partition 2.

The leftover chain has a flush right end, so the only way that any word could appear to the right of it is if it would form a flush left end with a word from the other partition, i.e., if one is a prefix of the other. But the only such pair of words with this property is $w$ and $wv\_nb$, since all other words remaining in partition 1 begin with some $v\_i$, while all other words remaining in partition 2 begin with $b$. But the word $wv\_nb$ is 2 characters longer than the word $w$, so stacking them vertically cannot form the rightmost end of the alignment -- and, since all remaining words in both partitions have length 4, the flushness needed to end the alignment cannot be achieved by appending any number of words from either partition. Hence, the leftover chain forms the rightmost part of the alignment, and all remaining words appear to the left of it.

### A Hamiltonian Cycle can be read off the top, between $w$ and $r$

A similar parity argument forces the $w$ and $wv\_nb$ words to be aligned to each other at the leftmost end of the alignment (any other placement would imply a ragged left end). It follows that the $n-1$ Hamiltonian words that remain in partition 2 must appear on the bottom, in some order, between $wv\_nb$ and $bv\_nr$. This leaves $4n$ spaces on top, into which the $n$ remaining edge words must slot, with the first forced to be $v\_nbbv\_i$ for some $i$ on account of the overlap with the start word $wv\_nb$, and the last forced to be $v\_jbbv\_n$ for some $j$ on account of the overlap with the mid word $bv\_nr$. The first and last words correspond to edges out of and into vertex $v\_n$ in $G$, respectively, and the $n-1$ Hamiltonian words on the bottom guarantee that the intervening $n-2$ edge words above correspond to edges that form a path that visits each vertex exactly once, so a Hamiltonian Cycle can be read off the $n$ edge words on top between $w$ and $r$.

A YES solution to either instance implies a YES solution to the other, and the construction is polynomial-time, so it follows that RS2P is NP-hard for integer alphabets and words of length at most 4, and by the expansion argument given at the top, for binary alphabets and words of length $O(\log p)$. Since a solution to it can be verified in polynomial time, it is also NP-complete. $\blacksquare$

---
Tags: algorithms, time-complexity, strings, substrings
---


# Question
Title: Is it better to arrange datatypes in a computer programme using arrays or linked lists?
How should datatypes be organised in a computer programme? Is it better to utilise arrays or linked lists? I'm not sure what the difference is, but I seem to recall hearing that arrays are quicker. Or perhaps it was connected lists? So, which one should I go with?

# Answer
> 1 votes
Data structures are not chosen "randomly" and there is no absolute preference order.

For a given application, different data structure options can be compared. In particular, for containers or associative containers, one looks at the time and space complexities of insertions, deletions, lookups..., put in relation to what the application will effectively require.

So saying "arrays are quicker" makes little sense. Your question sounds like "is a hammer better than a screwdriver, I heard that they are heavier"?

# Answer
> -2 votes
Whether to use arrays or linked lists to arrange data types in a computer program depends on the specific requirements and characteristics of the program.

Arrays are a good choice when the data size is fixed and known in advance, and when random access to elements is required. They are also more memory efficient than linked lists for small data sets, and the elements of an array are stored in contiguous memory locations, which can result in faster access times.

Linked lists, on the other hand, are a better choice when the data size is not fixed and when frequent insertions or deletions are required. They can be more memory efficient than arrays for large data sets because they only allocate memory for the elements that are actually used, and can be resized dynamically as needed. Linked lists are also useful when elements need to be inserted or deleted frequently, as they can be modified more easily than arrays.

Therefore, the choice between arrays and linked lists depends on the specific requirements of the program. If you need fast access to elements and the size of the data set is known in advance, use an array. If the size of the data set is not fixed and frequent insertions or deletions are required, use a linked list.

---
Tags: data-structures
---


title: Simplifying regex expression (L+M*)*

text:
# Question
Title: Simplifying regex expression (L+M*)*
To simplify it, it seems that we can do $(L+M^\*)^\* = (L+M)^\*$, but I also need to prove it.$(L+M)^\* ⊆ (L+M^\*)^\*$ seems straight forward. However, $(L+M^\*)^\* ⊆ (L+M)^\*$ is what I couldn't figure out. Should I use $ (L^\*M^\*)^\*$ instead of $( L+M)^\*$? If I use it and do induction on k, $ u ∈ (L+M^\*)^\*$ and u = (v1+m1)...(vk+mk); j = 1...k, vj ∈ L, and mj ∈ M\*.

For k=1, $v1⊆L ⊆ (L^\*M^\*)^\*$ and $m1⊆M^\* ⊆ (L^\*M^\*)^\*$, $v1+m1⊆ (L^\*M^\*)^\*$. How do I continue afterwards?

# Answer
Informally, $(L+M)^\*$ represents any sequence made of $L$s and/or $M$s, you can't make it more general. $(L+M^\*)^\*$ of course includes $(L+M)^\*$, but the latter cannot be a proper subset.

---

More rigorously,

$$L+M^\*⊆(L+M)^\*$$ so that

$$(L+M^\*)^\*⊆((L+M)^\*)^\*=(L+M)^\*$$
> 0 votes

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


# Question
Title: More efficient way to parse array into binary search tree
Let's assume I have array which I need to parse into binary tree

```
[10, 15, 8, 12, 94, 81, 5, 2, 11]:

          10
         /  \
        8   15
       /   /  \
      5   12  94
     /   /   /
    2   11  81

```

or slightly modified arrays with the same elements generate the same binary tree above: `[10, 8, 5, 15, 2, 12, 11, 94, 81]` or `[10, 15, 94, 8, 5, 2, 81, 12, 11]`

The first element of the array is always root of the binary search tree. The parsing should populate the tree from array sequentially without swapping/sorting elements in the array.

Something like this:

```
data class Node(
      val value: Int,
      var left: Node? = null,
      var right: Node? = null
 )

 fun Node.populateNode(currentValue: Int) {
        if(value <= currentValue) {
            if(right == null)
                right = Node(currentValue)
            else right?.populateNode(currentValue)
        } else if(left == null)
                left = Node(currentValue)
        else left?.populateNode(currentValue)
 }

 fun IntArray.parseToBst(): Node? {
        val root = Node(first())
        for(i in 1 .. lastIndex) {
            root.populateNode(this[i])
        }
        return root
 }

```

Usage:

```
val tree = intArrayOf(10, 8, 5, 15, 2, 12, 11, 94, 81).parseToBst()

```

I wonder if is any more efficient algorithm (faster in terms of time complexity) to parse binary search tree from array by requirements described above?

# Answer
> 1 votes
There's a linear-time algorithm to reconstruct a binary search tree given a depth-first preorder left-to-right traverse. But it seems to me that what you're looking for is an algorithm which will work with a traverse which only satisfies the property that a parent appears before its children.

The algorithm you present is $O(N log N)$ on average, but worst case $O(N^2)$. I don't believe you can improve on the average construction time of $O(N log N)$ but I think you can improve the worst case behaviour by maintaining the list of insertion ranges in a semi-balanced binary search tree (such as a red-black or AVL tree) where each node points at the parent node for that range.

# Answer
> 0 votes
A BST traversal will output the keys in sorted order in linear time, so no comparison-based tree building algorithm can work faster than in $O(n\log n)$ time.

As said at other places, this bound can be reached by filling a balanced BST one key at a time, and this is optimal. If the *balance* condition is not enforced, the worst-case time can get... worse. *Randomizing* could ensure *expected* $O(n\log n)$ time, but your question does not allow this.

---
Tags: trees, binary-trees, arrays, parsers, search-trees
---


# Question
Title: Time complexity to convert a truth table to a boolean circuit
The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table?

But how about going the other way? A function problem that inputs a truth table, and asks you to construct a boolean circuit that computes that truth table. Is this NP? Is it P?

# Answer
A truth table for $m$ variables has $n=2^m$ entries. A corresponding sum-of-products expression is made of at most $2^m$ terms, each of length $m$. So the total complexity of outputting them is $O(m2^m)=O(n\log n)$, in terms of the input size. This is polynomial.

---

As regards minimization of the expression, a possible approach is the Quine–McCluskey algorithm. From Wikipedia "For a function of $m$ variables the number of prime implicants can be as large as $\dfrac{3^{m}}{\sqrt {m}}$", which is $O(n^{\log3/\log2})$, still polynomial. Then "Step two of the algorithm amounts to solving the set cover problem, which is NP-hard". But I could not find an explicit expression of the complexity of the latter.
> 2 votes

---
Tags: np-complete, np, satisfiability, search-problem
---


# Question
Title: What can I read about permutations in 3D space?
I'm interested in the theory of calculating the position of an element when the face of a cube is moved - like in a Rubik's Cup. That is, for example, I rotate the face of the cube - how can I mathematically write down:

* all the displacements of its neighbors relative to each other
* the entire cube as a whole
* relative to a given point (tile) of the cube?

I am not a mathematician, but I was very interested in this question. Is there any particular area that studies this?

(Sorry for possible errors, I'm using a translator)

Thank you.

# Answer
Let a small cube be centered at the coordinates $(x,y,z)$, where $x,y,z\in\\{-1,0,1\\}$. By a rotation of a quater turn around the $X$ axis, $(x,y,z)$ moves to $(x,-z,y)$. By composition, a rotation by a half turn goes to $(x,-y,-z)$ and so on. You can easily generalize to all three axis.

In the Rubik's Cube, a face has from one to three visible sides, which can be discriminated by a unit normal vector, such as $(u,v,z)$, where one of $u, v, w$ is $\pm1$ and the other components are $0$. The unit normals undergo the rotation following the same transformation. (E.g. $(0,1,0)$ to $(0,0,1)$.)

A rotation can thus be denoted as the product of a $3\times3$ matrix with two vectors. Rotations can be concatenated by multiplying the matrices. Beware that the rotations may no apply to all three slices simultaneously.

$$\begin{pmatrix}1&0&0\\0&0&-1\\0&1&0\end{pmatrix}\begin{pmatrix}1&0\\1&1\\1&0\end{pmatrix}=\begin{pmatrix}1&0\\\-1&0\\0&1\end{pmatrix}$$

Alternatively, you can designate a normal as being in the direction of $X,Y$ or $Z$, with the sign being implicitly that of the corresponding component of the position. Hence $(1,1,1,Y)\to(1,-1,1,Z)$.
> 1 votes

---
Tags: permutations
---


title: Is DNA computation Turing complete?

text:
# Question
Title: Is DNA computation Turing complete?
I have heard DNA being referred to as "code", this is because it is an instruction set which dictates the bodies' properties. However, DNA (as far as I have learned), has no conditional jumps or normal jumps.

After reading the article *DNA computing* on Wikipedia briefly, I cannot find whether computations with DNA is Turing complete or not.

Please state why DNA is or is not Turing-complete and why.

# Answer
You seem to confuse a code understood as a way to encode information (such as the Gray code) and as a piece of program written in some programming language (such as *source* code and *binary* code).

*DNA code* belongs to the first meaning. The DNA code is similar to a mixed base $4^3=64$ numeration (I don't mean https://en.wikipedia.org/wiki/Base64), though not all combinations encode distinct amino-acids. There are no instructions, let alone *control* instructions.
> 1 votes

---
Tags: turing-completeness
---


# Question
Title: Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)
Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as -

F(i) = minimum\_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ Ai / Bm ⌉ * Cm)

where ⌈x⌉ is defined as the ceiling function. For example : ⌈2.3⌉ = 3, ⌈3.9⌉ = 4 and ⌈3⌉ = 3.

Find the value of F(1) + F(2) + F(3) + ..... + F(n).

Constraints: 1 \<= n, m, Ai, Bi, Ci \<= 1000000

How do I solve this question in better than O(N\*N) time complexity? The question is from a past onsite final. Problem link

# Answer
> 0 votes
Let's take a particular $a\_i$ and $b\_j$, what would be it's result if $a\_i$ is a multiple of $b\_j$, obviously $\frac{a\_i}{b\_j} \cdot c\_j$.

Now, think about what would be the result if $a\_i$ isn't a multiple of $b\_j$, it would be the same answer as for the least multiple of $b\_j$ which is greater than $a\_i$.

For all $b\_j$'s, we can calculate the answer for their multiples, now we just have to take minimum of the answer for the least multiples for every $b\_j$, think about how to do it.

---
Tags: algorithms, data-structures, discrete-mathematics, mathematical-programming
---


title: Optimization of algorithm

text:
# Question
Title: Optimization of algorithm
**Question:**
There are N soldiers standing in a straight line with ID 1 to N: \[1,2,3,4,5\]

You are given array of IDs of length K in the order they are called : \[3,1,2,1\]

When a ID is called the soldiers with that ID will attack the enemy and he will do the same damage as number of soldiers infront of him and will stand in front of the line.

When 3 is called, he will do 2 damage, and stand in front of the line : \[3,1,2,4,5\]

When 1 is called he will do 1 damage: \[1,3,2,4,5\]

When 2 is called he will do 2 damage: \[2,1,3,4,5\]

When 1 is called he will do 1 damage: \[1,2,3,4,5\]

You have to return the damages done in order: Result: \[2,1,2,1\]

---

I know how to solve this question in O(NK) which is simply by modifying the array for each query but I am not sure how to optimize it.

# Answer
> 3 votes
Generally, if a soldier was called out before, its position in the line equals the number of distinct soldiers between the current and the previous callout. This is because of the fact that after a callout of a soldier, its position equals $1$, and this number will increase by $1$ after each new callout of another soldier standing behind him. So this problem is explicitly converted to: "How to count the number of distinct elements in a subarray?" which I would refer to Answer queries about the number of distinct numbers in a given range or Is it possible to query number of distinct integers in a range in O(lg N)?.

To find the answer for the first call of any soldier, you can append the reversed index array to the front. According to your provided example, the finalized array would be $$A = \[5, 4, 3, 2, 1, 3, 1, 2, 1\]$$

* For the first call out, soldier $3$'s corresponding position in $A$ are $3$ and $6$ (assume that $A$ is 1-indexed). The subarray between them is $\[2, 1\]$, and its number of distinct values equals $2$.
* For the second call out, soldier $1$'s corresponding position in $A$ are $5$ and $7$. The subarray between them is $\[3\]$, and its number of distinct values equals $1$.
* For the third call out, soldier $2$'s corresponding position in $A$ are $4$ and $8$. The subarray between them is $\[1, 3, 1\]$, and its number of distinct values equals $2$.
* For the fourth call out, soldier $1$'s corresponding position in $A$ are $7$ and $9$. The subarray between them is $\[2\]$, and its number of distinct values equals $1$.

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


# Question
Title: String Search - how to find the "most" accurate string?
Assume I have the following list of companies:

* Apple
* Big Apple
* Google

Then I have this sample string:

> Big Apple is a company that is trying to be the next Google.

Given the list of companies and the sample string above, how can I find the list of companies in the sample string?

If I iterate through the list of companies and search for it in the sample string, I would find three matches: Apple (because "Apple" exist in "Big Apple"), Big Apple, and Google. In my scenario, I wouldn't want just Apple to match since Big Apple is a more accurate match.

I'm trying to implement the solution in PHP, but a general description/strategy on how to solve this would be helpful.

# Answer
From your explanations I understand that "most accurate" should be understood as "longest".

* Sort the search strings by decreasing length.
* Perform searches of the strings in that order.
* Every time you find a match, delete these characters from the target string.

E.g. "Big Apple", "Google", "Apple".

"*Big Apple* is a company that is trying to be the next Google."

" is a company that is trying to be the next *Google*."

" is a company that is trying to be the next ."

---

It is also possible to perform approximate matchings, but in cases like "Bug Apple", the solution would be ambiguous.
> 1 votes

# Answer
One way to do so is as follows:

1. Sort the company names from longest to shortest.
2. For each company name $c$:

a. Find all the substrings of the input string that equal $c$ and don't use any characters from a previous occurrence of a company name.

b. If some substring exists, add $c$ to the solution.

This strategy works if you're trying to solve the problem you've stated. But if you want a more robust solution, you should look into using natural language processing tools like Python's NLTK. These tools allow you to take syntax and context into account, and might help you tell the difference between "I ate a big apple", and "I bought shares in Big Apple".
> 0 votes

---
Tags: search-algorithms, strings, search-problem, substrings
---


# Question
Title: Division by zero in APL: assign return value 0 or 1
Recently I began learning a couple array based programming languages: Dyalog APL and BQN. And I cam across this peculiar manner in which division by zero is handled in Dyalog APL. Using the in-built method `⎕DIV` a user can change the behaviour of $0÷0$. For instance if `⎕DIV=0` then $0÷0$ will return $1$ and if `⎕DIV=1` then $0÷0$ will return $1$. In BQN the returned value is NaN. IF the numerator is other than 0, an error is returned.

My question is, how does this not cause issues for programming in DYALOG APL? I am unclear what advantage this provides; whereas, throwing an error are returning NaN seems rather useful insofar as it signals to the user there is an issue with their code. Moreover, algebraically this is problematic.

# Answer
I might be about to provide an unusual perspective on this, but in my view there is no one convention on division that suits all practical purposes.

I can certainly recall code I've fixed in the past - I forget any exact details - where a division by zero was not considered an error at all, but the result was intended to be zero in the case that the divisor (an integer) was zero.

There was probably no great mathematical integrity to this calculation, but the fix was simply to hard-code a result of zero when the divisor was zero, to avoid provoking an error.

Cobbling together what I can remember of this kind of situation, these sorts of calculations are common when trying to calculate distributional questions, like "how many people will receive what share of a dividend?".

In the case where there are no recipients available, the share is zero (as is the count of recipients). This is practically equivalent to the case where there are potential recipients, but the dividend is zero, so each share is zero - this case would cause no error anyway.

In these kinds of calculations, the programmer does not typically think of the quotient as having a mathematical relationship to the dividend, but of a zero quotient as being a special case which models the case of "no distribution occurs" or "nothing is transferred" in the real world. An absence of recipients (a zero divisor) is just as capable of causing "no distribution" as is an absence of anything to transfer (a zero dividend).

Division is the only standard arithmetical operator where inputting a seemingly non-extreme quantity is capable of producing a crash. I don't even specifically remember what I was taught at school about the result of a division by zero, but I certainly don't recall being told the result is "NaN" or "Error". I suspect something was murmured about "don't do that", but with no guidance on how to systematically handle practical situations which call for division by zero.

This unusual behaviour of computerised division is the cause of error (or of extra programming effort) in simple arithmetic, far more often than it helps identify an error.

Because APL seems to originate in a philosophy of using mathematics for practical data-processing purposes, rather than in trying to express a single coherent system of mathematical tenets, making division by zero a non-error, and being able to determine the default result of such division, seems perfectly sensible.

Also, whilst division by zero = 0 or 1 violates certain standard mathematical properties, it almost certainly acquires new desirable properties which are useful in conjunction with other functions in APL.
> 3 votes

# Answer
> how does this not cause issues for programming in DYALOG APL?

Truth to be told, it *does* cause issues, but maybe not the issues you'd think: The real issue is the introduction of a global variable that governs core language behaviour. If one expects divisions by zero, then it is wise to set a local value for `⎕DIV`. However, APLers are largely used to such issues, as multiple settings exist which affect the core language; `⎕IO`, `⎕ML`, and more.

> I am unclear what advantage this provides;

Depending on the exact algorithms in use, either of the two values could be the "correct" one for edge cases. (It should be noted that APLers often expect edge cases to "just work" — more on that below.) For example, if we're computing the percentage of apples in the first bucket:

```
      buckets ← 3 1 4
      first ← ⊃ buckets
      100 × first ÷ +/buckets   ⍝ +/ is sum
37.5

```

Now for the edge case where there are no buckets at all (keeping in mind that by default, $0÷0$ gives 1):

```
      buckets ← ⍬   ⍝ empty list
      first ← ⊃ buckets   ⍝ this gives the fill-value 0
      100 × first ÷ +/buckets
100

```

Which is correct; "all" the apples are in the first bucket.

Now we want to compute the average number of apples per bucket:

```
      (+/buckets) ÷ ⍴ buckets   ⍝ ⍴ is length
1

```

That makes little sense, and arguably 0 would have been a better value:

```
      ⎕DIV ← 1   ⍝ let 0 ÷ 0 give 0
      (+/buckets) ÷ ⍴ buckets
0

```

> whereas, throwing an error are returning NaN seems rather useful insofar as it signals to the user there is an issue with their code.

APL code will often compute multiple values at once. If such divisions errored when even one of multiple collections hit edge cases, the programmer would have a preprocessing task to filter those out first. Conversely, giving NaNs would force a postprocessing task of cleaning those out. With the current behaviour, the appropriate results can be computed directly.

> Moreover, algebraically this is problematic.

But algorithmically sound.
> 0 votes

---
Tags: programming-languages, arrays, mathematical-foundations
---


# Question
Title: A new algorithm for determining if a number is prime or not
This approach has been on my mind for quite some time. I did come up with it myself, I searched some methods for determining prime numbers but never came across anything similar to this.

```
import math
n = int(input())
def is_prime(n):
    x=n
    i= 2
    while(x>i):
        if n%i==0:
            return False
        x = math.ceil(n/i)
        i+=1
    return True
print(is_prime(n))

```

Can anyone tell me if this method already exists and can someone give me its time complexity.

# Answer
> 1 votes
Very sorry, but this is just a variant of the successive divisions method, the most basic of all, that a simple Web search would have shown you. Nothing new.

Note that trying all integers instead of the odd numbers is a little waste. Also, divisions are more costly than multiplies, so the test $i^2\<n$ would be better (even better to precompute $\sqrt n$).

# Answer
> 0 votes
You are testing whether n is divisible by consecutive i, for 2 ≤ i up to some limit. You want that limit to be small, to avoid unnecessary tests. Usually people start at their very first attempt with trying 2 ≤ i ≤ n-1 which does roughly n divisions is n is a prime.

If n is not prime, then it has a smallest prime factor i and another factor j ≥ i. (j isn't smaller than i because i is the smallest prime factor). The smallest number that has i as its smallest prime factor is i * i, so you only need to test numbers i such that i\*i ≤ n. You do that quite accurately, so you do about $\sqrt n$ divisions.

What is fatal (and what lots of people get wrong) is to stop too early. If you do that, the problem is typically that squares of primes are falsely recognised as primes. For example, if you divide $19^2$ by the numbers i = 2 to 18 only, you miss the prime factor 19 and falsely identify $19^2$ as a prime. My very first program to list prime numbers displayed the number 121 :-( You got that right, so your code is correct.

One improvement is to avoid dividing n by so many non-primes. You divide by 2, 3, 4, 5, 6 for example. But n cannot be divisible by 4 or 6 because you would have stopped when you divide by 2. So you can divide by 2, and then by odd numbers starting with 3 (3, 5, 7, 9, 11, 13, 15, ...). That saves about half the divisions. You can get another 33% improvement by dividing by 2, 3, and then the numbers 6k-1 and 6k+1, that is (5, 7), (11, 13), (17, 19) and so on. The numbers of the form 6k+3 are all divisible by 3 and would have been filtered out at the very beginning. You need only one test for each pair of two numbers to check if they are too large, you may do one division too many, but you save one comparison for every two divisions.

You should always test your code. Good tests are the numbers 0 to 10 (0 and 1 are not prime but also not composite), primes obviously, squares or cubes of primes.

---
Tags: algorithms, number-theory, primes
---


# Question
Title: Spaced-bounded Probabilistic Turing Machine Always Halts
For example, in the definition of BPL, we require that the probabilistic Turing machine has to halt for every input and every randomness. What is the reason for us to define them this way? What would happen if they don't halt? On the other hand, we don't require space-bounded non-deterministic Turing machines to halt.

# Answer
> 1 votes
This is a very old question, but is a good question and deserves an answer.

The basic issue is that if we let the probabilistic algorithm run for an unbounded amount of time (and randomness), it can solve NL in a trivial way. In fact, it can solve NL in RL, and even ZPL. But it does so by running in an exponential amount of time, which doesn't feel fair.

The idea of the algorithm is simple: store the current state, ask for the next state transition. If the transition is invalid, restart. Otherwise, transition to that state. If we ever transition from the start state to an accept state, accept. Since we know that NL = coNL, each time we restart, switch between the NL and coNL statement. Clearly this algorithm only uses logarithmic space, never outputs the wrong answer, and every time it runs has a 1/exp(n) chance of outputting the right answer. So after an expected exponential amount of time, we output the right answer with high probability.

And if we give two way access to the randomness and unbounded time/randomness, it gets even worse, allowing us to run the same idea but with polynomial length states, giving us BPSPACE is in ZPL.

In contrast, we don't require NL algorithms to halt because a non halting nondeterministic algorithm can be turned into one. If a path to the accepting vertex exists, it is reachable in polynomial time. Thus we can just reject if we didn't find this shortest route to the accept vertex. This only requires holding a counter, which only takes logarithmic space and polynomial time. Unfortunately, our BP algorithm for NL does not accept within polynomial time with high probability.

For reference, see Nisan's "On read-once vs. multiple access to randomness in logspace".

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


# Question
Title: What's the difference between user registers and kernel registers?
I am reading Operating Systems: Three Easy Pieces, but I can't fully understand the following paragraph. It's from the 6th chapter of the book. I think it's self-contained, so I quote here.

> Note that there are two types of register saves/restores that happen during this protocol (context switch). The first is when the timer interrupt occurs; in this case, the **user registers** of the running process are implicitly saved by the hardware, using the kernel stack of that process. The second is when the OS decides to switch from A to B; in this case, the **kernel registers** are explicitly saved by the software (i.e., the OS), but this time into memory in the process structure of the process. The latter action moves the system from running as if it just trapped into the kernel from A to as if it just trapped into the kernel from B.

I understand that OS need to save some registers to do context switch, but what does it mean by saying user registers and kernel registers? What are the differences between them?

Thanks!

# Answer
It's simple - when each application program runs, it has access to its own set of registers. When you switch to other application, these register contents is saved to memory, and registers, saved from other application, loaded and this application continues its execution.

Similarly, OS has its own register contents. Depending on CPU, it may even has its own, different register set. Moreover, some CPUs has two physical register sets - for apps and for OS, thus allowing fast switching from app to OS and back again (f.e. when app requests some service from OS).

Now let's look at your citation. I'm not an OS specialist, but this text means that for each application, we have specific contents of OS registers. F.e. these registers may hold app-specific data which isn't available to app itself (such as security context of the app). So, when you switch from app to OS (usually by requesting some OS service), OS registers are immediately ready to use, making the call faster. OTOH, when you switch to other app, the entire set of kernel registers need to be saved and kernel registers for other app should be loaded instead.

Since task switching is much less frequent operation, this makes the entire execution faster.
> 7 votes

# Answer
I would add that kernel registers are the ones extraneous to a user process, but help the OS and CPU enforce privilege levels. The registers that contain the upper and lower bounds of memory accessible by a user process in x86 are examples.
> 0 votes

# Answer
There have been processors doing it differently, but it is most most likely that your processor has one set of registers per virtual core. Having a second set of registers that are just needed when switching between user mode and kernel mode would be extremely wasteful. Registers are expensive.

What happens: Your user mode program is running and using all the registers. Then it is interrupted. The interrupt stashes a copy of all the registers away in a location for your process, then it grabs the register contents for the kernel mode, puts it into the same registers, and switches to kernel mode - so the kernel continues exactly where it left over. Eventually the kernel decides to switch back to your process. At that point all the registers are stored in a location that only the kernel can access, your user mode register values are restored from where they were stored, and the processor switches back to your user mode program, with all the registers exactly the same as they were before.

The same registers inside the processor are used both for user mode and kernel mode.

Sometimes you have interrupts that can be handle very easily. In that situation, maybe only 16 of your 32 integer registers, and none of your floating point or vector registers are stored and restored. If the kernel can run the interrupt handler code with these 16 registers only, then this can save substantial time.
> 0 votes

# Answer
Kernel registers can only be accessed in kernel mode, but are particular to a process. In x86 they include, for example, a pair of registers which demlimit the address space of the process.
> 0 votes

---
Tags: operating-systems
---


title: An algorithm that is $O(n^{\log(n)})$

text:
# Question
Title: An algorithm that is $O(n^{\log(n)})$
After having searched for a while, and after having read this

https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities

I was just wondering: is there some example of algorithm whose time complexity is ?$$O(n^{\log(n)})$$

Sorry for the arid question, I would just like to know if there is some example, being this a function that grows faster than polynomials but slower than exponentials.

# Answer
> 9 votes
Yes, there are examples, though I don't know of any elementary ones. Before I give one, notice that $$ n^{\log n} = (2^{\log n})^{\log n} = 2^{(\log n)^2} = O(2^{\text{poly}(\log n)}) $$

where $\text{poly}$ is a polynomial function (in this case quadratic). For this reason, the time complexity you are interested in ($n^{\log n}$) is an example of **quasi-polynomial time** (QP) - it's two to the power of a polynomial function of $\log n$.

Quasi-polynomial time is somewhat unusual to encounter, but by the time hierarchy theorem, we know that there are decision problems that require any complexity bound we might be interested in, including quasi-polynomial time. That includes that there must be problems that require $n^{\log n}$ (up to a logarithmic factor). But that doesn't mean that any of those examples is necessarily natural.

Perhaps the most famous examples of quasi-polynomial time algorithms are:

1. The best known algorithm for the graph isomorphism problem. The graph isomorphism problem is, on input two graphs $G\_1$ and $G\_2$, are $G\_1$ and $G\_2$ isomorphic? László Babai proposed an algorithm in 2017 which runs in quasipolynomial time.
2. The best known algorithm for the parity game problem, which has time $O(n^{\log n + 6})$. (See this paper.)

Neither of these algorithms is known to be asymptotically optimal.

# Answer
> 0 votes
Suppose you want to compute $$\binom{n}{k}$$ for given $k$ and $n$. A simple way is to use brute-force that running time will be $O(n^{k})$. Now if we set $k=O(\log n)$ we achieved desired bound.

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


# Question
Title: Find Number of subsequences such that bitwise OR is same as sum
Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0\<=Ai\<=Bi. Count How many sequences satisfy A1|A2|A3|..|An=A1+A2+A3+..An, where | is bitwise OR.

# Answer
Your numbers are less than $10^{18} \< 2^{60}$, so only bits 0 to 59 can be set. Prove that for 59 \>= b \>= 0, bit number b is set in at most one of the $A\_i$, and go from there.
> 0 votes

---
Tags: algorithms, dynamic-programming, counting, bit-manipulation
---


# Question
Title: Is there a maximal set of programs that terminate?
It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem:

Is there a maximal decidable set of terminating programs?

A set is maximal if it is not the subset of another such set. A program may be a Turing Machine or an equivalent model.

I came up with a simple argument to prove that such a maximal set cannot exist: We can take an arbitrary terminating program that is not yet in the set and add it, the result would still be decidable. The only candidate left for the maximal set is the set of all terminating programs which is however not decidable.

I am not completely convinced by my own argument though and it does not seem to give me any insight into the problem. Is it correct? Is there a more satisfying explanation? Can the problem be formulated differently to make it more meaningful, maybe ignoring the case that finitely many problems can always be added?

Furthermore, I think an equivalent, more practical formulation of the question I have in mind is whether there is an "optimal" termination decider (cannot detect more terminating programs). The implications confuse me. If it does not exist, does that mean any such decider program can always be improved?

# Answer
> 1 votes
Your proof is correct. There is no maximal decidable set. Yes, your conclusion is right, there is no optimal termination decider, as you can always come up with another one that detects one more terminating program. It's like noting that there is no largest number: for any number you name, I can always name one that is bigger.

---
Tags: undecidability, halting-problem
---


# Question
Title: Traveling salesman problem - negative distances allowed
I am interested in the following version of TSP:

**Assumption:** TSP where the distances are non-negative. We know the algorithm A which computes the optional solution for such instances of TSP.
**Task:** State an algorithm that uses the algorithm A and computes an optimal solition for instances where negative distances are allowed.

# Answer
> 5 votes
Hint: Every TSP tour has the same number of edges. Use this to modify the weights in the graph in a way which affects all TSP tours in the same way.

# Answer
> 0 votes
If you have n cities, and you increase every single distance by the same amount d, then the length of every tour is increased by the same amount n x d. So whether tour A is better than tour B or not is unchanged, and the optimal tour stays the same. For the decision problem: instead of deciding whether there is a tour of length K, you decide if there is one of length K + n x d.

To handle negative distance, find d’ = most negative distance, and let d = -d’. You can also enforce that the distances all follow the triangular equation by picking a larger d.

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


# Question
Title: Explanation of Cook-Levin Suitable for First Years
**TLDR**; Looking for Explanation of Cook-Levin theorem palatable to CS first years who are theory averse

I'm a prof. teaching first year algorithms+programming and want to give my students a taste of deeper CS theory.

In the very last week of class, I want to cover (in two lectures) the key idea behind Turing Machines NP-completeness, and NP ?= P.

I'd also love to somehow weave in Cook-Levin.

They won't have covered formal languages, so I plan to avoid them where possible. I *will* introduce SAT, and could talk about the number of variables in a tableau. We covered big-O and correctness proofs earlier in semester.

I'm also not a theoretician, so figuring out the minimal possible explanation that still contains meat is a bit tricky!

I'd love **a) thoughts on how best to do this or b) an explanation that provides the key intuitions.**

# Answer
I anticipate that the Cook-Levin theorem and its proof will be too much for CS first-years. I do not recommend that you try to teach that.

Instead, I recommend that you show them something awesome that is appropriate for their level of development and understanding. Maybe show them two lectures on machine learning (e.g., via nearest neighbors), or two lectures on how some data structure or algorithm is applied in practice, or something else awesome. To get ideas for awesome things you can show them, I recommend taking a look at introductory courses at a few top universities and see what they do.
> 1 votes

# Answer
If you will introduce SAT then you could use a SAT solver to do Soduku.
> 1 votes

---
Tags: complexity-theory, education
---


# Question
Title: How do you write a logic function to determine if one 2s complement binary number is less than another?
Working on logic design in class, and I'm trying to figure out how to write a specific logic function \[and by write, I mean something along the lines of (x NOR y) OR (a NOR b), for example\]

It asks to assume 2 variables, X and Y, both of which consist of 3 bits (x2,x1,x0, and y2,y1,y0). I need to write a logic function that is true if and only if X \< Y, assuming that they are *signed* 2's complement numbers.

I have somewhat of an idea of how to form a logic circuit that accomplishes this by subtracting and checking if the result is negative, which would use full-adders to add X to Y's inverse plus 1. I'm just struggling to figure out how to actually write that down in the form I stated above.

Edit: I really wasn't able to wrap my head around how to write this down as a function, so I went and made an adder/subtractor using a logic gate simulator:

and I worked up from bit 0, piecing together each logic equation:

Bit 0's sum is:

```
(x0 XOR y0') XOR (Cin0)

```

Bit 0's carry out is:

```
(Sum w/o carry-in) XOR (x0 AND y0')

```

Which is the same as:

```
((x0 XOR y0') AND (Cin0)) OR (x0 AND y0')

```

That then becomes the carry-in (Cin) of bit 1:

```
((x1 XOR y1') AND (((x0 XOR y0') AND (Cin0)) OR (x0 AND y0'))) OR (x1 AND y1'))

```

Then finally, for bit 2 (the sign bit), I dropped the carry out, plugging in bit 1's carry out to bit 2's carry in:

```
(x2 XOR y2') XOR (((x1 XOR y1') AND (((x0 XOR y0') AND (Cin0)) OR (x0 AND y0'))) OR (x1 AND y1'))

```

The first carry-in, Cin0, is 1 for the purpose of converting from a signed 2s complement number. Then the function just checks whether or not the sign bit is on or off, b/c if x - y is negative, then x \< y.

I did x = -1 and y = 3 for an example (in 2s complement, those are 111 and 011 respectively)

I feel like this is all really, really convoluted though, and I can't help but wonder if I've messed up somewhere along the way, or if I'm overthinking this. I just can't visualize how the logic works without... well, visuals.

# Answer
This page shows you the formula for a one-bit subtractor with borrows in and out. You can use this as a building block for a three-bits subtractor: https://www.geeksforgeeks.org/full-subtractor-in-digital-logic/.

$$D=(A\oplus B)\oplus B\_{\text{in}}\\B\_{\text{out}}=((\lnot A)\land (B\_{\text{in}}\lor B))\lor(B\land B\_{\text{in}})$$

You can eliminate the intermediate borrow variables if you want.
> 1 votes

# Answer
For each bit, you can `XOR` to check if they are different (if they are not, then no need to compare) and if they are different, you can use the value in `Y` (if `(X,Y)` is `(0,1)` we need to return true) and or the results together. If all the `XORs` return 0, the two numbers are equal. Now to implement your specific question, you just need to `OR` the different results together.
> 0 votes

# Answer
If you have just two bit values A and B, then(A \> B) = A AND NOT B, and (A \>= B) = A OR NOT B.

With two bits A1,A2 and B1,B2 (A \> B) = (A1 \> B1) OR (A1 \>= B1) AND (A2 \> B2), (A \>= B) = (A1 \> B1) OR (A1 \>= B1) AND (A2 \>= B2).

You can add more bits in the same way. Creating a circuit, you’d check what logic is repeated.
> 0 votes

---
Tags: logic, circuits, digital-circuits, comparison
---


title: Parsing algorithms

text:
# Question
Title: Parsing algorithms
I have experimented with a grammar that I could turn into a strict left-to-right finite state automaton driven algorithm (bottom up, table driven). The FSA could be complex, that's not a problem. It doesn't need to deal with infinite recursive structures.

I then moved the grammar into BNF, and built a standard SLR parse table. And I found that the SLR parser relies a lot on building non-terminal symbols on the right before it finishes the symbol that it has started on the left. This causes -- in my implementation at least -- a major disadvantage, because if I could just read token for token from left to right, everything would be much, much faster.

I like to know if this is something that has been discussed in the literature and where I would find that discussion. I.e., a certain restricted subset of grammars which can be parsed with a simple FSA token by token from left to right?

Trying to wrap my head around it, let's take the simple expression grammar example:

```
E : E + T
E : T
T : T * F
T : F
F : n
F : ( E )

```

I think I can turn this into a simple FSA if I limited the depth of the recursion on `F : ( E )`.

```
S   -[n]-> Sn   : push(token)
Sn  -[+]-> Snp
Sn  -[*]-> Snt
Snt -[n]-> ST   : push(token * pop())
Snp -[n]-> Snpn : push(token)
Snpn-[*]-> Snt  :
ST  -[*]-> Snt
...

```

I can't finish this idea right now, I should, to think this all the way through, but my intuition (and experience with having crafted a grammar before only by creating an FSA table directly, is that it causes a lot of states to be created, that the state carries a memory of a lot of what came before, that there appears to be quite a bit of redundancy in those many states, and that the S-attributes, that compute the value of the expression (or parse tree) will be a lot more to deal with those several cases.

But despite this redundancy doesn't matter as it is just a quick table lookup at every state for every new token and goes strictly left to right, terminal token by terminal token.

You might say, that perhaps I can't deal with shift-reduce, shift-shift and reduce-reduce conflicts, and here I am telling you that I don't care about those, because in my application I want to just follow every possible path, creating multiple parse trees if necessary. I.e., there isn't just one stack, but each instance of a state in the state machine carries its own value stack, so that, when conflicts arise, two or more states are derived, and the FSA continues on both of them with the next token. If there is no transition given the next token for any state, that simply gets abandoned. I guess this is a GLR parser in a way.

But the point is that I want to run it strictly as a finite state automaton.

Anyone ever done that or heard of such a thing?

# Answer
The comment basically has the right idea: What you want is some kind of LR parsing; GLR is fine.

You see, if a grammar is not $LR(k)$ but you try to build a $LR(k)$ automaton for it anyway, then the automaton is still correct and will still parse it just fine. The catch is that it is nondeterministic. Shift-reduce and reduce-reduce conflicts (there is no such thing as a shift-shift conflict in $LR$ parsing) are choice points that you need to handle somehow, such as by backtracking.

$GLR$ parsing embraces the nondeterminism. The automaton, and I can't stress this enough, is the same as the $LR$ automaton. The only difference is in how it's executed.
> 2 votes

---
Tags: parsers
---


# Question
Title: Can the pre-order traversal of two different trees be the same even though they are different?
This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.

It is also mentioned that the in-order traversal of two different trees can be the same though they are structurally different. Is there an example of this?

# Answer
Tree Examples (image):

```
     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /
 3

```

This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3.

Tree B root׳s value is 1, having a left child with value 2 and a right child with value 3.

In both cases the Preorder traversal is 1-\>2-\>3.
> 28 votes

# Answer
# Counting argument

The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C\_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes,

```
    o         o         o         o         o
   /         /         / \         \         \
  o         o         o   o         o         o      .
 /           \                     /           \
o             o                   o             o

```

Labeling these gives a factor of $n!$ on top of that, so that the number of labeled binary trees is $$\frac{(2n)!}{(n+1)!} = 2n\cdot(2n-1)\cdot \dots (n+2).$$

By contrast there are only $n!$ traversals of a tree of $n$ nodes. Since we just multiplied the former by $n!$, no traversal can therefore contain the full structure of the tree for $C\_n\>1$ hence $n\>1.$ And this in general holds for any data structure which has more than one configuration with unlabeled nodes; you don't *need* to know this detail about the Catalan numbers at all, as long as you know that there are at least two unlabeled binary trees of size $n$.
> 10 votes

# Answer
Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $1,2,\dots,n$.

This means that we can name the nodes of any binary tree structure so that it will generate the same pre-order sequence as that of another given tree.

This will not work if we have to assume other properties of the tree. For instance, if the tree is supposed to be a binary search tree, with all keys different, its pre-order sequence will uniquely determine the tree.
> 8 votes

# Answer
Regarding your second question, yes two structurally different trees can have same inorder traversal. One such example is:

```
     A:                 B:

     1                  2
    / \                  \
   2   3                  1
                           \
                            3

```

Inorder traversal of both the trees is same. 2 -\> 1 -\> 3
> 1 votes

# Answer
Given a preorder traversal of a tree, say a-b-c-d-e-f, you can guess a tree as follows:

* use the first element as the root,
* partition the rest of the sequence in a number of subsequences than will correspond to descendants, left to right,
* repeat recursively.

E.g.

```
 abcdefg

    a
  / | \
bc def g

     a
  /  |  \
 b   d   g
 |  / \
 c  e f

```

It should be clear that on every subdivision levels, there are several choices.
> 0 votes

---
Tags: trees, binary-trees, graph-traversal, search-trees
---


# Question
Title: Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?
At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the pumping lemma for context free languages, that it is not context free. But it upon further pondering I came up with a pushdown automaton that would match this language. So I'm a bit at loss as to what type of language it is. I hope someone can help.

# Answer
The language is context-free. You can use the pumping lemma for regular languages to show that it is not regular. However, you can construct a context-free grammar to show that the language is context free. For example, the following CFG grammar would generate it

$S \to A\ |\ aS $

$A \to \epsilon\ |b A cc $
> 1 votes

# Answer
If the language required twice as many c's as a's, the equivalent grammar should look like

S -\> aScc | bB | epsilon

B -\> bB | epsilon
> 0 votes

---
Tags: formal-languages, chomsky-hierarchy
---


# Question
Title: Prove that the problem MATCH is NP-complete
The problem MATCHED is defined as follows: given an infinite set S of strings of arbitrary length over the alphabet {0, 1}, determine if there exists a character of length n over the alphabet {0, 1} such that for every string s ∈ S, s and w does not match.

My approach: TO prove MATCHED is in NP is easy. For NP Hard, I was trying to reduce SAT to MATCH in polynomial time where length of the set S is equal to the number of clauses in the boolean formula and number of literals in each clause equal to the string length. But, I am finding difficulty in showing the transformation of any boolean formula in CNF form to a set of strings in set S.

# Answer
> 2 votes
Let $\phi = c\_1 \wedge c\_2 \wedge \dots c\_m$ be a 3-SAT formula on $n$ variables $x\_1, \dots, x\_n$, where $c\_i$ is the $i$-th clause. Assume w.l.o.g. that no clause contains both a literal and its complement (these clauses are always true and can be removed).

The set $S$ contains one string $s\_i$ of length $n$ for each clause $c\_i$. The $j$-th symbol of $s\_i$ is $0$ if $c\_i$ contains $\overline{x\_j}$ as a literal, it is $1$ if $c\_j$ contains $x\_j$ as a literal, and it is $\*$ otherwise.

If there is a solution $w$ to the match instance, consider the truth assignment that sets $x\_j$ to true iff the $j$-th symbol of $w$ is $1$. Since each clause $c\_i$ has at least one $0$ or $1$ in common with $w$, there is at least one negated literal for which the corresponding variable has been set to false, or one positive literal for which the corresponding variable has been set to true. Hence, all clauses of $\phi$ are satisfied.

If there a truth assignment that satisfies $\phi$, then define $w$ by letting the $j$-th symbol be $0$ if $x\_j$ is set to false, and $1$ otherwise. Each clause $c\_i$ has at least one satisfied literal $\ell\_i$, and this literal is either a positive variable $x\_j$ that is set to true, or a negated variable $\overline{x}\_j$ that is set to false. In the former case the $j$-th symbol of both $s\_i$ and $w$ is $1$, in the latter it is $0$. Therefore $w$ is a solution for the match instance.

---
Tags: complexity-theory, computability, algorithm-analysis, np-complete, np-hard
---


title: Knapsack with no capacity

text:
# Question
Title: Knapsack with no capacity
Given a set $S$, a value function $v(s)$ and a cost function $c(s)$ for all $s \in S$, and integers $B$ and $K$, the classic formulation of the Knapsack problem asks if there is a subset $S' \subseteq S$ in which $\sum\_{s \in S'} v(s) \geq K$ and $\sum\_{s \in S'} c(s) \leq B$.

Is there a variation/special case of the Knapsack problem where there is no $B$? I read through this question: Is there a name for the knapsack problem with no bound on knapsack capacity?, but the author assumes multiple knapsacks.

One way to formulate the problem where no capacity is given could be to ask for the cheapest subset $S'$ where $\sum\_{s \in S'} v(s) \geq K$, but then I'm not sure if this is still considered a Knapsack.

# Answer
Is there such a variation? Yes, you have defined one. Can it be considered as a knapsack problem? As far as I know, there is no formal definition of what counts as a "knapsack problem", so that's a matter of opinion and up to you.
> 1 votes

---
Tags: complexity-theory, knapsack-problems
---


# Question
Title: As far as we know, what does GPT-4's training data look like?
I was asking ChatGPT local history questions, because I knew many of the answers and could test the robot. But lots of details were wrong and while it can write citations, it won't disclose its training data i.e., I can't see its blind spots.

# Answer
> 3 votes
OpenAI does not fully disclose what the training set was. This is a space where there is heavy competition, and I imagine they probably view these details as part of their competitive advantage. What is known about GPT-3 and GPT-4 are disclosed in papers from the authors.

The GPT-4 paper says:

> "GPT-4 is a Transformer-style model \[39\] pre-trained to predict the next token in a document, using both publicly available data (such as internet data) and data licensed from third-party providers."
>
> GPT-4 Technical Report, OpenAI, arXiv:2303.08774.

The paper on GPT-3 contains more details:

> "Datasets for language models have rapidly expanded, culminating in the Common Crawl dataset \[RSR+19\] constituting nearly a trillion words."
>
> Language Models are Few-Shot Learners, Tom Brown et al, arXiv:2005.14165.

Table 2.2 goes on to show all of the datasets they used, including the Common Crawl (processed appropriately), WebText, Wikipedia, and more.

To learn more about these training datasets, you can learn more about Common Crawl, or read the references in the GPT-3 paper.

Don't be surprised if ChatGPT gets some facts wrong. That is what happens, given the current technology. This is known as the problem of hallucination, and it is an ongoing challenge to address.

---
Tags: neural-networks
---


title: Is every AVL tree a BST or just BT?

text:
# Question
Title: Is every AVL tree a BST or just BT?
I was going through the concepts of AVL tree and came across the definition of AVL tree from the wiki.

> In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree

even most of the definition claims that AVL tree is BST, but is every AVL tree needs to be BST can't it be just BT?

In my point of view, AVL follows an algorithm that balances the Binary Tree, as BST is the subset of the binary tree, then this balancing algorithm can be applied on it.

is there anything that I am missing? Any contradictory example will be highly appreciated.

# Answer
> 6 votes
Yes every AVL tree is a BST

also note that every binary search tree itself is a binary tree (binary tree is basically a tree that each node has at most two child) so therefore every AVL is a binary tree as well.

AVL tree is just a binary search tree that tries to do rotations when its needed (when the tree becomes unbalanced) in order to stay balanced, and therefore the search time would be O(logn)

the reason behind using AVL instead of BST is to make sure the search time is O(logn) because if we use BST and insert the values in a decreasing or increasing order then the BST would be one sided and the search time will be O(n), but if we do that using AVL then the tree will balance itself using rotations.

i suggest you to read the definitions of all of them so you can understand better.

# Answer
> 1 votes
AVL is BST by definition of AVL.

However, its self-balancing mechanism can be applied to any binary tree.

---
Tags: trees, balanced-search-trees
---