# Question
Title: Floating-point modular multiplication algorithm
Is there a well-known algorithm for modular multiplication of floating-point numbers?

I would like to multiply some large angle in single precision (6-7 significant digits) and wrap it back to 360 degrees, without losing too many significant digits.

```
float r = fmodf(a * b, 360);

```

My current approach is to split the numbers `a` and `b` into integer and decimal parts, get the remainder `(a_int * b_int) % 360`, and add it to the smaller decimal products.

Does a more efficient algorithm exist?

---

**Edit**: Here's an example expression:

```
float L = fmodf(13.17639647 * d, 360);

```

where `d` is a decimal number between -36525 and 36525 (it could theoretically be a wider range).

Unfortunately, double-precision math is not available.

# Answer
> 3 votes
A completely general solution for this is difficult to achieve if a wider floating-point format with at least twice the number of significand bits is not available. Normally, on common system platforms using C or C++ one could just use `float rem = (float) fmod ((double)a * (double)b, 360.0);` with `float` mapped to IEEE-754 `binary32` type, `double` mapped to IEEE-754 `binary64` types and therefore both the multiplication and `fmod()` being exact, with only a single rounding error incurred when rounding the result back to `float`.

A high-performance implementation is possible in the absence of `double` support if a few parameters and restrictions can be enforced. This answer assumes that a C or C++ program is executed on a system platform that supports IEEE-754 arithmetic and with the `binary32` data type exposed as `float`, and that the default rounding mode in effect is "to nearest or even". It is further assumed that the fused multiply-add (FMA) operation is provided in hardware, and exposed (for the `binary32` type) via the standard math function `fmaf()`. This latter assumption holds for most current systems based on the ARM, x86, and Power processor architectures, as well as commonly used GPUs.

It is further assumed that the product $a \cdot b$ is restricted to $\[-360 \cdot2^{22}, 360 \cdot 2^{22}\]$, approximately $\[-1.5\cdot 10^{9}, 1.5\cdot 10^{9}\]$, such that $\lfloor \frac{a \cdot b}{360}\rfloor$ is exactly representable in a `float` number. With this restriction in place, the desired result can be computed with an error of at most 2 ulp as follows.

With the help of FMA and the reciprocal $\frac{1}{360}$ one can quickly compute $\mathrm{nint}(\frac{a \cdot b}{360})$, where $\mathrm{nint}(\cdot)$ is the nearest integer function, and implement Kahan's accurate difference-of-products computation $ab-cd$. The remainder is computed as $a\cdot b - \mathrm{nint}(\frac{a \cdot b}{360}) \cdot 360$. To match `fmod()` semantics, the remainder must have the same sign as the dividend $ab$. This can be achieved by conditionally adding / subtracting $360$ if the condition is not met.

The final `float` result may round to exactly $360$. If this is problematic, an additional check should be added to the algorithm below to map this to zero.

```
/*
  Compute a*b-c*d with error <= 1.5 ulp.

  Claude-Pierre Jeannerod, Nicolas Louvet, and Jean-Michel Muller,
  "Further Analysis of Kahan's Algorithm for the Accurate Computation
  of 2x2 Determinants", Mathematics of Computation, Vol. 82, No. 284,
  Oct. 2013, pp. 2245-2264
*/
float diff_of_products_kahan (float a, float b, float c, float d)
{
    float w = d * c;
    float e = fmaf (c, -d, w);
    float f = fmaf (a, b, -w);
    return f + e;
}

/* Fast computation of fmod (a * b, 360). This is only accurate as long as the
   quotient round (a * b / 360) can be represented accurately by a 'float'. It
   is possible for the final result to equal 360 due to rounding error. If this
   is problematic, an additional correction could be added.
 */
float fmod360 (float a, float b)
{
    const float divisor = 360.0f;
    const float rcp_divisor = 2.77777777e-3f; // 1 / 360
    const float int_cvt_magic = 0x1.8p23f; // 2**23 + 2**22
    float prod, revs, rem;

    prod = a * b;

    /* approximate quotient and round it to the nearest integer */
    revs = fmaf (prod, rcp_divisor, int_cvt_magic);
    revs = revs - int_cvt_magic;

    /* compute preliminary remainder: a * b - revs * 360 */
    rem = diff_of_products_kahan (a, b, revs, divisor);

    /* remainder may have wrong sign as quotient rounded; fix as necessary */
    if ((rem * prod) < 0.0f) { // rem does not have same sign as product a*b
        rem = rem + copysignf (divisor, prod);
    }
    return rem;
}

```

# Answer
> -1 votes
If only single precision arithmetic is available:

You replace a with a mod 360, and b with b mod 360. That can be done *exactly*. You can force a, b into the ranges -180 \<= a, b \<= +180.

Calculating (a * b) mod 360 would have a huge rounding error. Single precision standard floating point has a 24 bit mantissa. The product is a\*b \<= 32,400 \< 2^15 (we are a bit lucky there). We let $a = a\_1 + a\_2 + a+3$, same for b, where $a\_1$ is a multiple of 1/16 (at most 12 bit mantissa), $a\_2$ has an absolute value of at most 1/32 and is a multiple of $2^{-17}$, and $a\_2$ is at most $2^{-18}.

You need to calculate 9 partial products, which are each exact. $a\_1 \cdot b\_1$ is reduced modulo 360, so the values are at most 180, at most 180/32 ≤ 6, and the others are smaller. Reduce $a\_1 b\_2$ and $a\_2 b\_1$ modulo 1/16, then add everything from the smallest to the largest, and one final reduction modulo 360.

---
Tags: algorithms, floating-point, modular-arithmetic
---


# Question
Title: Why is the problem of P and NP so difficult?
I understand the complexity of the issue in the event that P = NP: in this case, we couldn't prove it "by example" - it's simply impossible to sort through all possible tasks. The proof that, for all NP-complete problems, checking a solution is not easier than finding it, apparently, should be very non-trivial. However, if P =/= NP, is it not possible to prove this by simply providing an example of a problem for which it's always "easier" to check the correctness of the solution than to find the solution itself?

Do we really not have a single example of a problem for which finding a solution would be more difficult than checking it? Are there at least heuristic arguments in favor of the existence of such problems?

Thanks in advance.

# Answer
> 2 votes
If we had a single example where we can prove that finding a solution is more difficult then checking it, then this would immediately yield a proof of P != NP (well, with some assumptions). So, when people say it is hard to prove that P != NP, they are also saying it is hard to come up with even a single example where we can prove that.

Now, we have plenty of examples that are good candidates: where it is easy to check a solution, but it appears to be hard to find a solution. The thing is, we have no proof that it truly is hard to find a solution. Maybe there is some incredibly clever algorithm we just haven't thought up yet. That doesn't seem too likely, but we have no proof there is no such algorithm.

For instance, 3SAT is a good candidate. Or, any problem that is NP-complete is a good candidate.

There are certainly heuristic arguments. For instance, people have tried for decades to find an efficient, polynomial-time algorithm for 3SAT, but have not succeeded yet. This could be viewed as a heuristic that suggests that perhaps no such algorithm exists. But it is not a proof.

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


title: How to analyze quicksort

text:
# Question
Title: How to analyze quicksort
I am trying to prove that the following statements are true:

```
* The average time complexity of the quick sort is O(n log2 n).

* The average time complexity of the randomized quick sort is Θ(n log2 n).

* The worst case time complexity of the quick sort is Θ(n^2).

* The worst case time complexity of the randomized quick sort is O(n^2).

```

I wrote a program for quicksort and randomized quick sort

```
#quicksort

def partition(arr,low,high):
    pindex = low
    pivot = arr[high]
    print(arr)

    for j in range(low , high):

        if   arr[j] <= pivot:
            arr[pindex],arr[j] = arr[j],arr[pindex]
            pindex = pindex + 1
            print(arr)

    arr[pindex],arr[high] = arr[high],arr[pindex]
    return (pindex)

def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
        print(arr)

arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
print(arr)#quicksort

def partition(arr,low,high):
    pindex = low
    pivot = arr[high]
    print(arr)

    for j in range(low , high):

        if   arr[j] <= pivot:
            arr[pindex],arr[j] = arr[j],arr[pindex]
            pindex = pindex + 1
            print(arr)

    arr[pindex],arr[high] = arr[high],arr[pindex]
    return (pindex)

def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        print("pi",pi)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
        print(arr)

arr = [1, 4, 2, 7, 8, 3]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
print(arr)

```

and

```
#randomized quicksort

import random
def partition(arr,low,high):
    print(arr)
    pindex = low
    pivot_index = random.randint(low,high-1)
    pivot=arr[pivot_index]
    n_comparisons = 0
    arr[high],arr[pivot_index]=arr[pivot_index],arr[high]
    print("pivot:", arr[pivot_index])
    for j in range(low , high):

        if   arr[j] <= pivot:
            n_comparisons += 1
            arr[pindex],arr[j] = arr[j],arr[pindex]
            pindex = pindex + 1
            print("n_comparisions:", n_comparisons)

    arr[pindex],arr[high] = arr[high],arr[pindex]
    return (pindex)

def quickSort(arr,low,high):
    print(arr)
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
print(arr)

```

```
[10, 7, 8, 9, 1, 5]
[1, 7, 8, 9, 10, 5]
[1, 5, 8, 9, 10, 7]
[1, 5, 7, 9, 10, 8]
[1, 5, 7, 8, 10, 9]
[1, 5, 7, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
Sorted array is:
[1, 5, 7, 8, 9, 10]
[1, 4, 2, 7, 8, 3]
[1, 4, 2, 7, 8, 3]
[1, 2, 4, 7, 8, 3]
pi 2
[1, 2, 3, 7, 8, 4]
[1, 2, 3, 7, 8, 4]
pi 1
[1, 2, 3, 7, 8, 4]
[1, 2, 3, 7, 8, 4]
pi 3
[1, 2, 3, 4, 8, 7]
pi 4
[1, 2, 3, 4, 7, 8]
[1, 2, 3, 4, 7, 8]
[1, 2, 3, 4, 7, 8]
Sorted array is:
[1, 2, 3, 4, 7, 8]

```

As I worked through quick sort I was able to create the following output.

I'd like to use the results from this to show that the statements above are true. I would appreciate it if someone could help me with this. There is never enough time, thank you for yours.

# Answer
There are many pitfalls in your approach.

In the first place, you cannot obtain any reliable information on the time complexity of a program by timing it. Because for a small number of elements, the time is heavily polluted by many ancillary "setup" processes and many non-deterministic perturbations, and for a large number of elements, the memory accesses do not take constant time. Fortunately, the case of small numbers (like your example) is irrelevant as for asymptotic analysis it is meaningless.

It is better to instrument the code and count the comparisons and the data moves.

Even if you had reliable timing data, fitting a function to empirical data is extremely hazardous (for instance, you could probably not tell $n\log n$ from $n\sqrt n$). And to truly validate it, you should go to astronomical values of $n$, such that neither your computer nor your patience can afford.

To measure an average time complexity, in principle you need to perform several runs on different data sets and average the results. This is doable (with the above reservations); as a byproduct, you can get an estimate of the dispersion. Notice anyway that there isn't a single "average time": this time depends on the chosen statistical distribution of the input permutations.

There is no difference between running the algorithm on random data, and running the randomized algorithm on any data, so you can spare one of the first two tests.

The worst-case times are virtually inaccessible with random data, as they occur with astronomically small probabilities, plus you have no way to known that you reached the worst case. A reliable method is to try all permutations, but even for moderate sizes (say $n\ge15$) this is impractical.

To summarize, you don't analyze an algorithm by experimentation, but by reasoning.
> 2 votes

---
Tags: sorting, quicksort
---


# Question
Title: Prove that $O(\sum_{i=0}^{h}{2^i\times(h-i)}) \sim O(2^h)$
I want to prove that, $$\sum\_{i=0}^{h}{2^i\times(h-i)} \sim O(2^h).$$

---

I did come up with the below proof, $$\sum\_{i=0}^{h}{2^i\times(h-i)} \sim O(\sum\_{i=0}^{h-1}2^{h-1}) \sim O(h2^h),$$ but as it is clear I did not find the correct path for my proof.

# Answer
> 1 votes
Let $$S\_h:=\sum\_{i=0}^{h}{2^i(h-i)}.$$

We have

$$S\_h-S\_{h-1}=\sum\_{i=0}^{h}{2^i(h-i)}-\sum\_{i=0}^{h-1}{2^i(h-1-i)}=\sum\_{i=0}^{h-1}{2^i}=2^{h}-1.$$

So by induction,

$$S\_h=S\_0+\sum\_{i=1}^h(2^i-1)=2^{h+1}-h-2.$$

# Answer
> 3 votes
Consider $$1+x+x^2+x^3+\dots+x^n=\frac{x^{n+1}-1}{x-1}.$$ Differentiate from two sides: $$1+2x+3x^2+\dots+nx^{n-1}=\frac{(n (x-1)-1) x^n+1}{(x-1)^2}.$$ Multiply two sides by $x$: $$x+2x^2+3x^3+\dots+nx^{n}=\frac{(n (x-1)-1) x^{n+1}+x}{(x-1)^2}.$$

Plug $x=2$ into into formula you will get:

$$\begin{align} \sum\_{i=1}^h2^i(h-i)&=\sum\_{i=1}^h h2^i-\sum\_{i=1}^hi2^i\\ &=h(2^{h+1}-1)-((h-1)2^{h+1}+2)\\ &=h2^{h+1}-h2^{h+1}+2^{h+1}-3-h\\ &=O(2^h). \end{align}$$

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


title: Mutli-Path Collision Avoidance

text:
# Question
Title: Mutli-Path Collision Avoidance
I need an algorithm which can do the following:

> Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{R}^2$ for the particles to take so they won't collide.

The list of points for a particle specifies the order in which the particle must visit those points. All particles start moving at the same time. The time elapsed for a particle to travel from any prescribed point to the next is constant for every particle regardless of distance. I'd like to find a continuous trajectory for each particle, so they won't collide (the circles won't overlap). Ideally, I would like to find the solution which minimizes total path length under the constraint that there are no collisions.

Assume that the distance between the n'th prescribed point of different particles are at least the particle's diameter apart so that there are no unfixable collisions.

My best solution is just making splines for every path, and keeping a record of all the collisions. I have been reading papers about potentially adding more prescribed points to bend the paths, and 'elastic bands', but I'm not sure exactly how to do it.

# Answer
> 0 votes
Let me first discuss some possible solutions for the case of $n$ particles and 2 points per particle, then extend it to an arbitrary number of points.

Suppose we're given $n$ particles and 2 points per particle. Assume we're also given an additional constraint: the initial direction of each particle is also specified. For each particle, it's easy enough to draw a path from the starting point to the ending point. Now consider the collection of those paths, and find all collisions. If we don't have any limit on the velocities or accelerations of each particle, it should be straightforward to pick a particle, choose the speed at which it traverses its path (if a constant speed causes collisions, slow down until you reach the collision point, then speed up afterwards, and adjust until there are no more collisions), and repeat, one particle at a time.

Let's suppose you have an algorithm you're happy with, for $m=2$ points per particle. Then you can use that to solve the problem for $n$ particles and $m$ points per particle, for any $m \ge 2$: you simply solve it for each pair of adjacent time steps (i.e., the $i$th and $i+1$th points), then combine those solutions.

Probably this could be improved, by finding a better way to handle the $m=2$ case. For instance, if there is an algorithm for laying out a graph as a planar graph, given pre-specified locations for all vertices, that might help find better solutions. However, maybe this illustrates one approach that can find at least a possible solution, even if it's not optimal.

# Answer
> 0 votes
Leave the points immobile. They won't collide.

---
Tags: algorithms, optimization, constraint-satisfaction, algorithm-design, routing
---


title: Is $\overline{A_{TM}}$ co-NP Hard?

text:
# Question
Title: Is $\overline{A_{TM}}$ co-NP Hard?
I know that $A\_{TM}=\\{\<M,w\>|M~is~a~TM~and~M~accepts~w\\}$ is NP-Hard:

By showing a polynomial time reduction - $A \le\_p A\_{TM}$:

Let $A \in NP$, then there exists a $NTM$ that decides $A$ in polynomial time, thus there exists a $DTM$ $M\_A$ that decides $A$ in exp time.

Then $f(w)=\<M\_A,w\>$ is the reduction, so $A\_{TM}$ is NP-Hard.

Does it mean that $\overline{A\_{TM}}$ is co-NP Hard since it is $A\_{TM}$'s complement?

Thanks!

# Answer
Yes, let's show this in $2$ ways.

## Option A

Let $B\in Co-NP$. As such, there exists a NTM, say $N\_B$, such that for any $b$: if $b\notin B$ then $N\_B$ rejects in a polynomial time. We can also say there exists a DTM, say $M\_B$, such that for any $b\notin B$ it rejects it in (at most) exp time. We therefore reduce any $b$ to: $\<M\_B,b\>$. Note that $|M\_B|$ is constant, therefore the reduction is polynomial. This is the same argument as the one you presented.

## Option B

Ignore the above, simply use the fact $\overline{B}\in NP$, and therefore a reduction exists $\overline{B}\leq\_P A\_{TM}$. The **exact** same reduction works $B\leq\_P \overline{A\_{TM}}$.

## Conclusion

We showed $B\leq\_P \overline{A\_{TM}}$. We chose $B$ as an arbitrary language in $Co-NP$. It follows that $\overline{A\_{TM}}$ is $Co-NPH$.
> 0 votes

---
Tags: complexity-theory, np-complete, np-hard, np, decision-problem
---


title: Telling unique values in a short array

text:
# Question
Title: Telling unique values in a short array
I have thousands of short arrays (length less than 9) holding integers. These numbers can be identical with high probability (in many arrays there are two triples of equal numbers). I need to remove the duplicates in each array, as efficiently as possible.

An obvious solution is to sort using a fast sort (such as straight selection), then to compress with a linear pass. But is there a smarter way ?

Worth to know: the identical values are often consecutive (but not always). In-place processing is preferred.

# Answer
> 2 votes
After posting my question, I realized that it contains the answer. As there can be many duplicates, the size of the compressed array tends to be quite short. So

* it is advisable to avoid eliminating the duplicates as soon as possible. A modified straight insertion sort could do, the modification consisting of just dropping an element when it is found to be a duplicate,
* there is little benefit in keeping the values sorted. (The cost of keeping sorted order is that one might have to shift elements many times.)

Hence I will try this solution:

* consider every element in turn,
* search backward among the elements previously considered and kept,
* if the same value is found, drop the element; otherwise append it to those that were kept.

This is easily implemented in-place.

---
Tags: algorithms, sorting, efficiency
---


# Question
Title: Iterating over combinations of 4 timestamps from 2 timelines *efficiently*
I need help in finding a more performant algorithm.

I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list are only growing with higher indices. Each list has about 2000 elements.

From every timeline, I take two indices and thus timestamps behind them. From these four timestamps, I calculate the ratio `distance_2 / distance_1`. Only ratios of 0.8 to 1.2 are valid (simplified; in reality, they can be configured).

---

I need an efficient algorithm that yields all possible combinations of timestamp choices that correlate to a valid ratio. To increase performance, there must be as few iterations as possible; e.g., by early abortion.

I currently use an algorithm, which isn't fast enough, that iterates in the following manner (as if DCBA would be a number with varying numbers of digits):

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

|A||B
C|||D

||A|B
C|||D

A||B|
C|||D

|A|B|
C|||D

A|B||
C|||D

A|||B
|C||D

|A||B
|C||D

...

```

The algorithm works in the following way:

* The advancement of a timestamp is always stopped (resetting it and advancing the next) when the distance between the timestamps on a timeline *in index steps* falls below a minimum (currently 1). This means, timestamps cannot cross over each other.
* Only when advancing timestamps from the first timeline, I check if the resulting ratio grew over the max of 1.2. If so, it is reset and the next is advanced.
* Only when it comes to advancing the least significant and most often advanced "digit" (A in above diagram), and only the first time in a continuous series of advancements of just this "digit", I proactively quick-advance it with bisection. This helps in the following case: The distance C--D became short, so that, when the less significant "digits" A and B are reset to their home positions, the ratio is initially smaller than the minimum of 0.8. More quickly overcoming the initial A positions, that, given the current state of C and D, all correlate with too small ratios, improves performance. But I don't see how this would be possible for every "digit" and as deterministically as the check against max, described in the previous point, which is just early abortion.

# Answer
> 2 votes
# Algorithm

Step 1: Build the set of all possible distances from the first list, by enumerating all pairs of items from the first list and subtracting. Sort this set, and call $A$ the result.

Step 2: Do the same for the second list, and call $B$ the result.

Step 3: Now, scan through these two sorted sets of distances, to find all pairs of distances that are in the range $0.8$ to $1.2$. You can use a "two fingers and thumb" algorithm, with a thumb pointing at an element of $A$ (say its value is $a$), and two fingers pointing at the two elements of $B$ that form the range of values in $B$ that are between $0.8a$ to $1.2a$. Next, advance the thumb forward by one element, to an element of value $a'$, and then you can advance the two fingers forward as much as needed to the new range, containing all values in $B$ that are between $0.8a'$ and $1.2a'$. Continue.

Notice that your thumb and fingers only move left-to-right, and never go backwards.

In this case, since $1/0.8 \ne 1.2$, we should do this twice, once using a thumb on $A$ and two fingers on $B$, then once using a thumb on $B$ and two fingers on $A$.

# Running time analysis

If there are $n$ elements in each list, then step 1 can be done in $O(n^2 \log n)$ time, step 2 can be done in $O(n^2 \log n)$ time, and then the scanning process (to adjust the thumbs and fingers) in step 3 takes $O(n^2)$ time. In addition, if there are $N$ 4-tuples that should be output, then the process of outputting all the pairs of pairs in the appropriate range takes $O(N)$ time.

So, the total running time is $O(N + n^2 \log n)$, where $n$ is the length of each input list and $N$ is the length of the desired output.

---
Tags: combinatorics, enumeration, performance, combinatory-logic, time-series-analysis
---


# Question
Title: How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?
Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row.
Let $\Sigma\_2 = \left\\{ \begin{bmatrix}0\\ 0\end{bmatrix}, \begin{bmatrix}0\\ 1\end{bmatrix}, \begin{bmatrix}1\\ 0\end{bmatrix}, \begin{bmatrix}1\\ 1\end{bmatrix}\right\\}$ be the set of all 2-element column vectors of binary digits.

$A =\\{\begin{bmatrix}u\\ v\end{bmatrix}\in {\Sigma\_2}^\*\mid \[v\]\_2 = 5\[u\]\_2\\}$

Where $\[x\]\_k$ is the $x$ to the base $k$. So $\[x\]\_2$ is a binary number. $A$ is the language of words where the second row is five times the first row. For example, $\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}0\\ 0\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix}$ i.e. $1$ and $5$.

What I've realized so far is that the second row must be the first row shifted twice eg. $001 \to 100$ plus the first row. For example. $\[001\]\[101\] = 001$ {shift2} $100 + 001$. What I've been trying to do as of late is to design a DFA to recognize a language where the second row is the first row shifted twice and move on from there.

I've been at this for over a day now. Please provide some insight if you can.

# Answer
Define function $d:{\Sigma\_2}^\*\to \mathbb Z$, $d(w)=\underline w-5\overline w$, where

* $\overline w$ is the base-$2$ number formed by the digits on the first row of the letters in $w$
* $\underline w$ is the base-$2$ number formed by the digits on the second row of the letters in $w$.

For example, if $w=\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}$, then $\overline w=(001)\_2=1$, $\underline w=(110)\_2=6$, $d(w)=6-5\cdot1=1$.

The language in the question $A$ is $\\{w\in{\Sigma\_2}^\*\mid d(w)=0\\}$

---

How does $d(w)$ change if $w$ is extended by a letter $\sigma=\begin{bmatrix}a\\b\end{bmatrix}\in\Sigma\_2$?

Let us check. Let $w'=w\sigma$. By the definition of a base-$2$ number, we have \begin{aligned} \overline{w'} &= 2\times \overline{w} + a\\ \underline{w'} &= 2\times \underline{w} + b\\ \end{aligned} So, $$d(w') = 2\times d(w) + d(\sigma)$$ Since $-5\le d(\sigma)\le 1$, we know

* $d(w)\le -1 \implies d(w')\le -1$
* $d(w)\ge 5 \implies d(w')\ge 5$

---

Let us construct a DFA with 7 states $q\_{\le-1}, q\_0, q\_1, q\_2, q\_3, q\_4, q\_{\ge5}$, where

* $q\_{\le-1}$ for words $w$ such that $d(w)\le-1$.
* $q\_{i}$ for words $w$ such that $d(w)=i$, where $0\le i\le 4$.
* $q\_{\ge5}$ for words $w$ such that $d(w)=5$.

The transitions $\delta$ is defined by

* $\delta(q\_{\le-1}, \cdot)=q\_{\le-1}$.
* $\delta(q\_{i}, \sigma)=q\_{2\*i+d(\sigma)}$, for $0\le i\le 4$. Here $q\_{2\*i+d(\sigma)}$ should be understood as
    + $q\_{\le-1}$ if $2\*i+d(\sigma)\le -1$.
    + $q\_{\ge5}$ if $2\*i+d(\sigma)\ge 5$.
* $\delta(q\_{\ge5}, \cdot)=q\_{\ge5}$.

$q\_0$ is the start state and the unique accept state.

By the construction above, it is straightforward to check that the DFA accepts $A$.
> 1 votes

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


# Question
Title: What does exactly Medium term scheduler do?
I'm trying to know what is the exact function in medium term scheduler in operating systems.

As far my understanding, a process may be needed to be removed from the running queue when it is faced with an I/O request. So it is usually sent to blocked list which is also situated in the main memory. Medium term scheduler is responsible for this.

It's all good till here, but it is confusing in the next part. I looked up the function for medium term scheduler, and it says that it suspends any processes which receives I/O request and are sent to **secondary memory** in the process of swapping.

So the process is totally removed from the main memory, as opposed to moving it to blocked state within the Main memory. So is MTS really responsible for moving processes from running state to suspension in case of I/O requests or someone else is responsible for it?

# Answer
Before I try to explain your question, I need to make a few observations:

1. You claim that: "a process may be needed to be removed from the running queue when it is faced with an I/O request", not only, when a process is running, one of the following events can occur: **the process issues an I/O request and then is inserted into an I/O queue**; **the process creates a new child process and waits for it to finish**; or **the process may be forcibly removed from the CPU as a result of an interrupt and placed in the ready queue**.
2. "So it is usually sent to blocked list", no. The process moves from the waiting state to the ready state and is then returned to the ready queue.

Well, it is often advantageous to remove a process from memory and consequently from the "dispute" for the CPU, in order to reduce the degree of multiprogramming. Of course, later on, the process can be reintroduced into memory and its execution can resume where it left off, this is done by the medium-term scheduler and is called **swapping**. Swapping may be necessary to **improve process mixing or because a change in memory requirements has overloaded available memory and must be freed**. This permutation makes it possible for the space of physical addressing of all processes exceeds the actual physical memory of the system.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: Prove by reduction that language of TMs accepting only words starting with 101 is undecidable
Before an exam in Computability I go through questions from last year's test. So the question is:

$$A= \\{ \langle M\rangle x | M \text{ is a TM and accepts } x \\}$$ $$ L = \\{ \langle M \rangle | M \text{ is a TM and halts only on words starting with 101 } \\} $$ Prove by reduction that $L$ is undecidable. So this should be done without Rice's theorem.

I have troubles with constructing a reduction function, to show $A\leq L$.

Has someone probably some advice for this problem? Thanks in advance.

# Answer
Assume that $L$ is decidable. Then there is a Turing machine, $T$ that, on input $M$ decides whether $M$ halts only on words starting with $101$.

Using $T$, we will be able to decide $A$. Given $\langle M\rangle x$, we would like to decide if $M$ accepts $x$. In order to do that, imagine another Turing Machine $M\_x$, that

1. Does not halt if input does not begin with $101$.
2. If input begins with $101$ ignores remaining input and simulates $M$ on $x$. If $M$ accepts $x$, $M\_x$ halts else does not halt.

Now $M$ accepts $x$ if and only if $M\_x$ belongs to $L$ (i.e. $T$ accepts $\langle M\_x\rangle$).
> 0 votes

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


# Question
Title: Complexity of recursive function that calls itself with it's own return value
Given the following code:

```
int f3(int n)
{
   if(n <= 2) return 1;
   f3(1 + f3(n-2));
   return n - 1;
}

```

I was trying to find the time complexity and I got this expression: $T(n)=1+T(T(n-2))$ which I've never seen before.

I know the answer is $O(2^{\frac{n}{2}})$ but I have no idea how to get there. Can anyone explain the calculation process?

# Answer
**Hint:**

The correct recurrence is

$$T(n)=T(1+f\_3(n-2))+T(n-2),\\T\_0=T\_1=1.$$

That should be easier to solve.
> 1 votes

---
Tags: time-complexity, recursion, big-o-notation
---


title: Designing DFA for a language

text:
# Question
Title: Designing DFA for a language
I am working on designing a DFA with the language $a^i b^j c^k$ such that $i + j + k$ is odd
I thought along the following lines:
$i+j+k$ is odd $\Rightarrow$ two of them are even and one is odd or all of them are odd. But designing a DFA like this will lead to a complex and big DFA. I am not sure if there is a simpler way to design a DFA for this.

# Answer
this language is an intersection of 2 regular languages: a sequence of any number of a b and c in order: `a*b*c*` (a 3 stage + sink DFA will handle this one), and `[abc]([abc][abc])*` (which a 2 state DFA)

To create the DFA for the interesection you take the cartesian product of all stages and then connect them according to the transition function. $\delta((s\_1, s\_2), a) = (\delta(s\_1, a), \delta(s\_2, a))$

So you will end up with a 6 state + sink DFA.

$s\_{a0}$ : start and $\delta( s\_{a0}, a) = s\_{a1}$ , $\delta( s\_{a0}, b) = s\_{b1}$, $\delta( s\_{a0}, c) = s\_{c1}$
$s\_{a1}$ : accepting and $\delta( s\_{a1}, a) = s\_{a0}$ , $\delta( s\_{a1}, b) = s\_{b0}$, $\delta( s\_{a1}, c) = s\_{c0}$
$s\_{b0}$ : $\delta( s\_{b0}, a) = sink$ , $\delta( s\_{b0}, b) = s\_{b1}$, $\delta( s\_{b0}, c) = s\_{c1}$
$s\_{b1}$ : accepting and $\delta( s\_{b1}, a) = sink$ , $\delta( s\_{b1}, b) = s\_{b0}$, $\delta( s\_{b1}, c) = s\_{c0}$
$s\_{c0}$ : $\delta( s\_{c0}, a) = sink$ , $\delta( s\_{c0}, b) = sink$, $\delta( s\_{c0}, c) = s\_{c1}$
$s\_{c1}$ : accepting and $\delta( s\_{c1}, a) = sink$ , $\delta( s\_{c1}, b) = sink$, $\delta( s\_{c1}, c) = s\_{c0}$
and of course $sink$ only goes to itself
> 0 votes

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


# Question
Title: Getting an NFA with only one initial and final state without epsilon transitions
Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions, we may need to add final or initial states, depending on the method used (backwards removal vs forward removal).

Is there an efficient way to convert an NFA to an equivalent NFA with only one initial and final state, and no epsilon transitions? Converting it to a DFA can be exponential, so is there a better way to achieve this?

# Answer
> 2 votes
Yes, in fact we can. Provided the original automaton does not accept the empty string $\varepsilon$.

The construction is as follows. We start with the usual NFA with a single initial state (and no $\varepsilon$-edges). Add a new final state $f$. Whenever there is a transition $(s,a,t)$ into a final state $t$ we add a copy $(s,a,f)$ into new final $f$. Now demote every original final state into ordinary.

Voila, the new automaton accepts the original language except for $\varepsilon$, but has only a single final state.

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


# Question
Title: When the stall is actually going to happen?
Suppose in a 5 stage pipeline when the stall will actually happen if there is a RAW hazard? The stall will start after Instruction Fetch(IF) stage or Instruction decode(ID) stage? In few cases I see that the stall start after IF that is before executing ID and in multicycle pipeline, the stall starts after decode stage (ID). Can someone please clarify it?

# Answer
> 0 votes
As part of the instruction decode phase, the operands are fetched for the instruction. In a very naive pipeline implementation, the operands for read will only be visible after the write instruction has written back its changes to the internal registers (so the last stage).

To prevent such long stalls, a CPU can apply tricks like forwarding the store to the load as soon as the value is determined instead of needing to wait for the write to the registers.

Check out the following for a more detailed answer: https://youtu.be/EL8uqzSsg\_Q?t=433

# Answer
> 0 votes
All cpu pipelines are multi-cycle. In the MIPS five-stage pipeline registers are read in the second stage called ID (instruction decode/register fetch). And instructions usually stall as late as possible. For example in

```
daddi   r1, r2, r3
daddi   r4, r5, r1

```

the second instruction will stall for three cycles at ID because it can't proceed until the first instruction has written to `r1` which happens in the pipeline's fifth stage.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: If a graph is not 3-COLORable, then there are at most 2 Independant Sets in G?
Assuming $G=(V,E)$ is a 3-colorable graph, then there are 3 disjoint independent subsets of $V$: $S\_1,S\_2,S\_3$ such that $S\_1 \cup S\_2 \cup S\_3=V$, by taking each $S\_i$ to include the vertices of color $i$.

I wanted to know - if $G$ is not 3-colorable, then can it has 3 disjoint subsets that their union is $V$?

I think it can't be by the definition of 3-colorable.

Am I correct?

Thanks!

# Answer
This sounds like homework, so you should try to prove it. The title, by the way, doesn't make sense.

**Proof sketch.** Suppose that you can partition the vertex set into three independent sets, $S\_1, S\_2, S\_3$. Color the vertices in partition $S\_1$ red, $S\_2$ green, and $S\_3$ blue.

**Claim.** This is a proper coloring, hence the graph is 3-colorable.

We conclude that *if* the graph is 3-colorable, *then* its vertex set can be partitioned into three independent sets.
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, np-complete
---


# Question
Title: If the complementary language of an recognizable language is a non-recognizable language, is the recognizable language a non-decidable language?
The complementary language of a recognizable undecidable language is not recognizable.

If the complementary language of an recognizable language is a non-recognizable language, is the recognizable language a non-decidable language?

# Answer
If a language $L$ is recognizable but it's complement $\overline{L} $ is not, then there is no TM that will halt and accepts a string $w \in \overline{L} $, which implies that there is no TM that will halt and rejects $w \notin L$. However for a language to be decidable there must be a TM that accepts $w$ if it is in $L$ or rejects $w$, otherwise.
> 1 votes

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


# Question
Title: Explain meaning of states and transitions for DFA that accepts two binary words (a,b) with b = 5a
I was provided with the solution to the language being represented. An example of accepted input would be \[001\]\[101\]. The DFA that would recognize this language is below.

What do the states represent? What are the meaning of the transitions

# Answer
First look at the second component only. This represents a finite state automaton for strings that have a binary value that is a multiple of five. The states are the value of the string up to now, mod 5. We move from state $x$ with bit $d$ to state $2{\cdot}x+d\pmod 5$. This ensures that $b$ is indeed a multiple of five.

A similar automaton for strings that are a multiple of $3$ see Algorithms computing if a number is a multiple of 3.

The first component is performing a kind of long division, dividing $b$ by $5$ to obtain $a$. Whenever $2{\cdot}x+d \ge 5$ the first component is $1$, otherwise it is $0$.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Design an algorithm with linear complexity
Let A\[1 : n\] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A.

Beyond the algorithm, what I can't fully understand is why we are provided with the information "all elements except O(n^2/3)" It is certainly an information that guides the choice in some way of the algorithm. What considerations can we make on this information that is provided to us?. How can it guide us in choosing the best algorithm?

# Answer
The reason you are provided that information is that, without this extra promise, it is not possible to sort in linear time. With this extra promise, it *is* possible to sort in linear time.

It's your exercise, so I will leave it to you to come up with the strategy to sort such an array in linear time. Once you've found such an algorithm, hopefully you will be able to see why the same can't be used on any array (without that promise).
> 1 votes

---
Tags: algorithms, time-complexity, big-o-notation, linear-complexity
---


# Question
Title: Doubt regarding conjugations of permutations
I was studying the Barrington Theorem in https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture2.pdf when I found a doubt regarding permutations. Particularly, with conjugations.

It is said, in the 2nd page, 4th point, that two cyclic permutations $\pi$ and $\sigma$, always have a permutation $\tau$ s.t. $\tau\pi\tau^{-1} = \sigma$.

I have never studied permutations, and wanted to see why this is true.

The unique thing I have came up is that: $\tau\pi\tau^{-1} = \sigma$ iff $\tau\pi = \sigma\tau$ but I am stack here.

Any clue would be really appreciated.

# Answer
> 0 votes
As pointed by @D.W., Theorem 2 from the link https://www.planetmath.org/conjugacyclassesinthesymmetricgroupsn has a proof for the existance of such $\tau$.

In essence, consider two cycles $\pi$ = ($a\_1$ ... $a\_n$) and $\sigma$ = ($b\_1$ ... $b\_n$). We can build $\tau$ as the permutation that moves each $b\_i$ to $a\_i$.

Indeed, we see that, $\tau^{-1} \pi \tau(b\_i) = \tau^{-1} \pi (a\_i) = \tau^{-1}(a\_{i+1}) = b\_{i+1}$. That is, each $b\_i$ is mapped to $b\_{i+1}$ as $\sigma$ does.

# Answer
> 0 votes
Separate the domains of the permutation and the conjugation. If X is a set and $\sigma$ is some permutation of X (take $X=\\{1,2,\ldots, n\\}$, say), imagine there's a new set of Z of the same cardinality as X and a one-to-one, onto mapping $f: Z\to X$. Consider $f^{-1} \sigma f$. It's a function on Z that first maps everything to X, permutes according to $\sigma$, and maps back along the same "mapping lines" as f. Intuitively, "the result does to Z exactly what $\sigma$ does to X". Working out a few small examples should help.

But be careful: The permutations are conjugate in $S\_n$ if they have the same cycle structure. This may not be true in subgroups of $S\_n$. Consider $S\_4$. The elements (1 2 3) and (1 3 2) of $A\_4$ have the same cycle structure, but they are not conjugate in $A\_4$.

---
Tags: permutations, group-theory
---


# Question
Title: An Arithmetic Encoding's length being ambiguous?
Say they are two tokens, A and B. A has probability weight 0.99 (and B has 0.01). If I want to encode the sequence "AAA", wouldn't the binary encoding just be "0"? And wouldn't that be the same for encoding "AA", or "AAAA", or an number of A's? How is the decoder supposed to know how many A's are sent when all it receives is the message "0"? Or is it absolutely necessary to have/add an EOF token? But in that case, the EOF token will have to be given some weight, which will detract from the weight of the other more meaningful tokens, right?

# Answer
Yes - you need to be able to indicate EOF (and EOF is obviously meaningful). Note that you may have a natural message boundary in terms of decoding; for example, if you are writing to a file then the file has a size and thus the information can be encoded in a trailer (e.g., how many of the final decoded characters should be discarded). If there's no natural boundary (e.g., this is one message of many in a stream), then you either need to prefix the message with the encoded length, or yes, reserve probabilities for the EOF token (note that you can adjust the probabilities to be dynamic in the number of characters previously decoded, if this makes sense).
> 1 votes

# Answer
Arithmetic coding tries to get close to the theoretical maximum. Getting closer takes more effort. So two encoders will give different results, depending how much effort they put into the compression.

The easiest way to understand it properly is to write a decoder. It has to decode one A, two As, ..., thousand As, so each of these must be encoded in a different way. Once you have a decoder you can then write an encoder that produces something that will be decoded correctly. You have freedom in the encoder, not in the decoder.
> -1 votes

---
Tags: arithmetic, data-compression, encoding-scheme, communication-protocols
---


# Question
Title: Unrecognizable languages must be undecidable?
A decidable language must be recognizable.

Unrecognizable languages must be undecidable?

I want to know more about the relation of undecidability and unrecognizability

# Answer
> 1 votes
One of the most applicable basic laws of basic logic is the law of contraposition: $(P \rightarrow Q) \leftrightarrow (\neg Q \rightarrow \neg P)$.

Therefore, if you know decidable languages must be recognizable, its contrapositive readily follows: languages that are not recognizable can not be decidable.

For a more direct reasoning, observe that a decider for a language is always also a valid recognizer for a language. Therefore if a language has a decider, it also has a recognizer and therefore is recognizable; and if it has no recognizer, it cannot have a decider either.

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


title: Data hazard in MIPS: SW after ADD

text:
# Question
Title: Data hazard in MIPS: SW after ADD
Use the five-stage pipeline with forwarding unit.

```
add $t1, $t2, $t3
sw $t1, 0($t4)

```

In the above code, is the data hazard of t1 fixed by forwarding the correct t1 value from MEM stage to EXE stage?

Also, are there totally four forwarding paths, which are MEMtoEXE, WBtoEXE, MEMtoID, WBtoMEM, in pipeline?

It would be grateful if someone can help. Thank you!

# Answer
> 0 votes
Here is a pipeline diagram with no bypasses:

The five colors indicate the five stages; fetch (F), decode (D), execute (X), memory (M), and writeback (W). With no bypasses, `sw` stalls in decode until `add` has written the value of `$t1`.

Here is the situation if we assume a bypass from pipeline register X/M to X:

Note that pipeline bypasses are from *registers* to *stages*. So it is not technically correct (and slightly confusing) to say that you bypass from, for example, MEMtoEXE because the bypass is actually from M/W to X.

---
Tags: cpu-pipelines, mips
---


# Question
Title: Split an instruction into more than four sub instructions?
0

I am learning about the instructions-set in my computer science course, and I am wondering if it is possible to split an instruction into more than four sub-instructions.

Thank you

# Answer
Many processors with complex instructions split them up internally into less complex instructions and execute those. Often these are called “micro-OPs”. Intel x86 processors often split one instruction into four "micro-OPs". I think ARM 32 bit processors split "load multiple registers" and "store multiple registers" into up to 8 instructions; I might be wrong there. There is no reason why an instruction couldn’t be split into more.

Whether having instructions of that complexity is a good idea is a different question.

For vector instructions, which are expensive to implement, it is quite possible to split for example one 512 bit instruction into eight 64 bit instructions. Say you have a 16 core processor. Implementing 512 bit vector instructions in every core is expensive. So you could have two cores implementing the full 512 bit instructions, 14 cores splitting them into eight instructions (saving lots of money), and the OS switches threads using these instructions a lot to the two big cores.
> 2 votes

# Answer
If you're asking if instructions can be split into smaller instructions, then the answer is no. That's not how instructions work. Instructions are a sequence of bits (the opcode) and an operand (the data to be operated on). The operand can be an immediate value, a register, or a memory address. The operand can be encoded in the instruction, or it can be stored in a register or memory. There's no way to split the instruction into two smaller instructions. If you're asking if instructions can be split into more than four sub-instructions, then you may want to look at instruction pipelines. Instructions are executed in a series of steps, each of which takes some time. The CPU can execute multiple instructions in parallel, but not all of the steps at once.
> 0 votes

# Answer
Instructions are atomic and not splittable in any model of the computation. For any sequence of instructions, it can be assumed that the previous instruction has finished before the next instruction in the sequence runs. However, many optimization techniques either overlap instructions or split them into many microcode instructions. Overlapping is also called pipelining and means that instructions are split into several phases. The more phases, the more instructions can execute concurrently. Microcode means that assembler instructions are "recompiled" by the cpu into one or more microcode instructions. For example, the x86 `rep movsb` instruction can cause the cpu to execute hundreds of microcode instructions.
> 0 votes

---
Tags: cpu-pipelines
---


title: How a computer works?

text:
# Question
Title: How a computer works?
I know that a computer can be mechanical, screws/nuts or even water/pipes. Of course, it would be slow and big, but it doesn't have to be electric, transistors, etc. How can a machine like this do all that it does? I can't understand.

I would like a thought path for this, analogy. Especially one where I can think it as a some mechanical, physical thing.

I'm very interested in low-level operation, CPU.

# Answer
> 0 votes
**Short answer:**

Current computers are digital, and even binary, i.e. they represent numbers as strings of bits, and bits are "encoded" using some physical phenomenon such as electric voltages. Typically, the physical phenomenon can take two ranges of value that can be discriminated by comparison to a fixed threshold (low or high voltage). One could as well work with pressure in fluids or forces exercised by gears.

Every computation can be performed when you are able to build so-called *nand* gates, which are devices such that when you input two signals, the output is the logical complement of the logical and. In electronic computers, these gates are realized using transistors. But you can invent any other device that performs this logical operation.

By combining enough nand gates, you can represent any number, perform additions, multiplications and many other arithmetic operations. You can store data and route data where you want by means of *addresses*, which are also numbers. Last but not least, you can store numbers that encode a sequence of instructions and let you compose a program.

---
Tags: computer-architecture, programming-languages, cpu, binary, introductory-lesson
---


title: Why does it have that amount of stalls

text:
# Question
Title: Why does it have that amount of stalls
I'm doing an exercise about the MIPS pipeline with the following characteristics:

-Branches and Branch targets are calculated in the E-stage. -There is forward logic from the output to the input of the E-stage. -You can read an operand from the register file only the cycle after it has been written to it.

The task is to create a diagram for the instructions passing through the cycles. Stalls are marked with X and the aim is to mark the current stage for the instruction with F,D,E,M,WB, or X at that cycle.

This is the code I'm making the diagram for, I don't understand why there are two stalls (X) on the third instruction. Should it not be F X X X D given that the forwarding is from WB to D?

This task is from the course EDA333 given at Chalmers.

# Answer
How could the add instruction stall before it has been decoded (D)? At that point, it is not known that there is a data hazard via `$t2` so no stall is possible. So the correct sequence is:

```
F D stall stall stall E M W

```

Afaict, three stall cycles are required because "You can read an operand from the register file only the cycle **after it has been written to it**." But usually in exercises about the MIPS pipeline you are allowed to read and write the same register in the same cycle.
> 0 votes

---
Tags: cpu-pipelines, mips
---


# Question
Title: What are the hardest problems that are in P if and only if P=NP?
I used to think that NP complete problems are the "hardest" problems of all problems that would still be in P if P=NP. Now I think otherwise. What I'm asking is if there are any problems that are proved (/believed/maybe) to be harder than NP-Complete if $P\neq NP$, but are certainly in P if $P=NP$.

I was thinking of the sequence

$x\_0 = P$

$x\_{n+1} = $"All problems that have a checking algorithm in $x\_n$"

e.g. $x\_1 = NP$

If $P=NP$, then $x\_n = P$ for all $n$. But if $P\neq NP$ is then $x\_{n+1}$ different from $x\_n$ for all $n$? Is this an ever continuing sequence so that there is no "hardest problem that meets the criteria" (because there would always be a harder one), or does this also hold for $x\_\infty$ and would that be the hardest problem that meets the criteria? Or are there even harder such problems?

# Answer
Well, here is a trivial example of a problem.

Inputs: a program P, an input x
Desired output: if P=NP, output "sweet!", else if P halts on x output "halts", else output "doesn't halt"

If P=NP, then this problem is in P. If P$\ne$NP, then this problem is very hard (it's undecidable).

I realize this might not be what you're looking for; if so, perhaps it illustrates just how tricky it is to specify properties of this sort.
> 10 votes

# Answer
You have to say what "harder" means, that is which kind of *reduction* you want to use to order problems.

If you consider poly-time many-one reductions, all problems in P are equally hard.

If you consider log-space many-one reductions, we get a non-trivial set of P-complete problems.

If you consider ... I think you get the idea.
> 4 votes

# Answer
Your answer: Any problem that is NP-hard, that is today believed not to be in NP, but that actually *can* be proved to be in NP (except for the fact that nobody has yet been able to do so).

Obviously if P = NP then any problem that can be proved to be in NP is actually in P.
> 0 votes

---
Tags: complexity-theory, np-complete, np-hard
---


# Question
Title: How to find a term that proves a given proposition?
I'm reading this book, and there's something basic that I don't exactly get. The authors say that every common noun is declared to be a type. For example, $Human:Type$. Then, they give an example of semantics of an intransitive verb, which is $talk: Human \to Prop$, where $Prop$ is "the internal totality of all logical propositions" (I'm not sure what "internal totality" means, but maybe that's not exactly relevant here), with inference rules as shown below.

Now, if $j: Human$ ($j$ for "John"), then I believe in certain context we can prove that $talk(j): Prop$. But how do I find a term that would prove the proposition $talk(j)$? I'm not sure I understand even what such a term should look like.

# Answer
OK, so this is painful. I haven't read your book, but it looks like the authors are trying to appropriate Montague Grammar for their examples but they don't quite know what they're doing. So briefly, Montague Grammar is an approach to the semantics of natural languages analogous to Denotational semantics for programming languages. The idea of Montague Grammar is to create a parse tree for a sentence, and then combine the semantics of each word as you go up the tree in a clever sequence of function applications which ultimately combine to form a proposition. So to get to your question, the semantics of $talk(j)$ is just given to you as an axiom from the lexical semantics of "talk". In Montague grammar, you are assured that every word in a sentence has appropriate semantics. It's given in the lexicon, which is assumed to exist before the semantics of any sentence can be evaluated. The axioms you've provided look like barely enough to perform the various function combinations to yield a proposition from the lexical semantics, but don't provide any lexical semantics whatsoever.
> 0 votes

---
Tags: logic, lambda-calculus, type-theory, dependent-types
---


# Question
Title: Are there any problems that are easy to compute but hard to verify?
Assuming P $\neq$ NP, NP-complete problems are "hard to solve, but have answers that are easy to check." Does it make any sense to consider the opposite, that is, problems for which it's easy to compute a correct answer, but hard to verify an arbitrary purported solution?

I think such a problem would imply either:

1. Exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.
2. Some "correct" answers are easy to compute, but others are difficult to find.

# Answer
If you are fine with artificial problems, you can make plenty of them. Here are a few:

* *Given a positive integer *n* in unary, answer a satisfiable 3CNF formula in *n* Boolean variables.*
Giving one satisfiable 3CNF formula is easy, but deciding whether a given 3CNF formula is satisfiable or not is 3SAT, a well-known NP-complete problem.
* *There is no input. Just answer a Turing machine which halts (when run with an empty input tape).*
Giving one such Turing machine is easy, but whether a given Turing machine halts or not is undecidable.

*Added*: By the way, I do not think that what you wrote in the last paragraph holds:

> I think such a problem would imply exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.

If the problem has *one* solution, then indeed checking an answer is no harder than computing the correct solution. However, if the problem has one easy solution and one difficult solution, then you cannot compute all the solutions efficiently. Here is one such problem (which is very artificial):

* *Given a Turing machine *M*, answer one of the following statements that is true: “*M* halts on empty input tape,” “*M* does not halt on empty input tape,” and “*M* is a Turing machine.”*
Giving one solution is easy: you can always choose “*M* is a Turing machine.” However, whether a given answer is correct or not is undecidable. Note that in this problem, there are only two solutions for each instance.
> 25 votes

# Answer
Although Tsuyoshi Ito's answer covers the "main" answer, there were two subtler notes I wanted to add.

1. **Even when the solution is hard to verify, checking the solution is still easy to check with a short proof string.** That is, by extending the solution a bit with extra information, it becomes easily checkable; the verification is always in NP. One way to see this is that the agent computing a solution can record all the random bits they use, and then the verifier can use that same random string to execute the same computation. (The prover must use random bits, otherwise they always output the same answer, and the verifier can always easily check by computing an answer by the same method.)
2. **For quantum computers, this is a very open question.** For classical computers, the verifier can always do something like simulating the prover and checking that they get the same answer. It's entirely possible that for some tricky problem, there is quantum algorithm which produces a uniform distribution across all (exponentially many) solutions, which are hard to verify. You can't re-run the prover, because you will most likely get a different answer each time.

As a example of a similar kind of issue, the Deutsch-Jozsa problem suffers from this a bit. If an oracle is not a balanced function, then a quantum computer can quickly determine that this is the case, but there is no short proof that would allow a classical computer to verify this. (This is only a "similar" issue because it can still be checked by another quantum computer, and the checking is also in classical BPP even if it's not in P.)
> 2 votes

# Answer
Problem: Given an integer n, give a semi-prime number of n digits (that is a number which is the product of exactly two primes). For n = 200 for example, it is reasonably easy to find two 100 digit primes and multiply them, but proving that their product is the product of exactly two primes is very hard.

Or: Given an integer n, give a composite number of n digits. For n = 10,000 any product of two 5,000 digit numbers starting with 4 to 9 is a solution. But checking that a 10,000 digit number is a prime is usually much harder.

Of course in both cases it's easy if I am given the way these numbers were produced.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Confusion about adjacency list graph representation
From my understanding, the general implementation of an adjacency list is using a hashtable with vertices as keys and linked lists to as values in the hashtable to represent the adjacent vertices of the key. It is also said that the time complexity of finding all the neighbours of a given vertex in the graph using the adjacency list if O(1), as you simply look up the vertex in the hashtable. However, doesn't a hashtable look up have worst case O(n) time? So it shouldn't be constant time? Any help would be much appreciated.

# Answer
> 1 votes
Usually vertices can be represented with consecutive integers, then you can just use an array instead of a hash table. If you insist on using a hash table have a look at perfect hashing

---
Tags: graphs
---


# Question
Title: If a language is undecidable, then its complementary language must also be undecidable?
Reference from here If a Language is Non-Recognizable then what about its complement? There exist complementary languages of unrecognizable languages that are recognizable, and there exist complementary languages of unrecognizable languages that are undecidable.

If a language is unrecognizable, then it must be undecidable.

If a language is undecidable, then its complementary language must also be undecidable?

# Answer
> 1 votes
If $A(x)$ is an algorithm deciding $x\in L^c$, then $\lnot A(x)$ is an algorithm deciding $x\in L$.

To be more pedantic, by $\lnot A(x)$ I mean the algorithm that executes $A(x)$ and if that accepts (resp. rejects) then it rejects (resp. accepts). In a programming language it's likely something like `bool not_a(string x) { return not a(x); }`.

Hence, if $L^c$ is decidable then $L$ is such.

Using a similar argument you can prove that $L^c$ is decidable if and only if $L$ is such.

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


# Question
Title: Can we accept that all axioms are equivalent?
The proposirional logic is based on 3 schema of axioms of which (A1) is B ⇒ (C ⇒ B). Then, for any 2 axioms p and q, p ⇒ (q ⇒ p) is an instance axiom of (A1). We can have q ⇒ p by a step of MP as we have already p. We can have p ⇒ q in the same manner. So, we have p ⇔ q, that is, all axioms are equivalent. But can we accept this theorem ? If we cannot accept it, for which reason ?

# Answer
What you have discovered is that any two true propositions are logically equivalent (you do not need them to be axioms in your argument, only that they hold).

What may be confusing is that the truth value of $p \Rightarrow q$ has nothing to do with the *meaning* of $p$ and $q$, it only depends on the truth values of $p$ and $q$. When two statements are logically equivalent, that does *not* say that they have equivalent meanings, only that they have equal truth values.
> 5 votes

---
Tags: logic
---


# Question
Title: Querying a binary search tree, find maximum
I'm studying algorithms on the very famous book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. and I'm looking at the algorithms for finding the maximum and minimum elements in a binary search tree . In the book obviously such a tree is described as follows:

> "We can represent such a tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate attribute contains the value NIL."

The pseudo code given in the book for finding the maximum is as follows:

```
TREE-MAXIMUM(x)
    while x.right != NIL
         x = x.rigth
return x

```

My question is: doesn't this code always return NIL? knowing the properties of the binary search tree: so when there is a right-hand subtree the maximum node is substantially the last node at the bottom right. If we follow the pseudo algorithm code above the while loop will terminate at the moment x == NIL and will always be equal to NILL in this algorithm. So it will always return NILL. Wouldn't this pseudocode be more correct? :

```
TREE-MAXIMUM(x)
    while x.right != NIL
         y=x
         x = x.rigth
return y

```

# Answer
> 2 votes
No. Try an example. The loop terminates when x.right == NIL. This is not the same as x == NIL.

---
Tags: algorithms, binary-trees
---


# Question
Title: Correct defintion polynomial-time reduction
I have frequently seen two different definitions of polynomial-time reduction. In the following let $A, B \subseteq \Sigma^\*$ be decidable problems. I will try to formulate the definitions in my own words:

Definition 1: $A \le\_{p\_1} B$ iff there exists a polynomial-time computable function $f\colon \Sigma^\*\to\Sigma^\*$ such that for all $w\in\Sigma^\*$:

$$\begin{equation} w\in A \iff f(w) \in B.\tag{1} \end{equation}$$

Definition 2: $A \le\_{p\_2} B$ iff assuming we have a Turing Machine $M$ which solves $B$, there exists a Turing Machine $M'$ which may call $M$ as a subroutine a polynomial number of times and is also polynominal-time besides of calling $M$, such that the resulting function $f$ defined by $M'$ satisfies $(1)$ for all $w\in\Sigma^\*$.

Question 1a: Are these two definitions equivalent? Clearly $\le\_{p\_1}$ is at least as stronger as $\le\_{p\_2}$. I would assume it is strictly stronger, because clearly $L^2 \le\_{p\_2} L$ for any Problem $L$, however I wouldn't assume the assertion holds for $\le\_{p\_1}$.

Question 1b: What if we restrict our problems to be in $NP$ (and assume $P\neq NP$)? Does that change anything? For the same reason I would assume no.

Question 2: What is the correct definition? I think definition 2 is the correct one which confuses me because most textbooks I have seen use definition 1.

# Answer
Definition 1 is a polynomial-time many-one reduction, also known as a Karp reduction. Definition 2 is a Cook reduction.

NP-completeness is defined with respect to Karp reductions. If you found a textbook that defined NP-complete using Cook reduction, that textbook was wrong, or using a non-standard notion of NP-completeness. I am sympathetic, but the term "NP-complete" has an accepted meaning in the field, and that meaning is based on Karp reductions.

See also https://en.wikipedia.org/wiki/NP-completeness#Completeness\_under\_different\_types\_of\_reduction, https://cstheory.stackexchange.com/q/138/5038, Can we construct a Karp reduction from a Cook reduction between NP problems?, Teaching NP-completeness - Turing reductions vs Karp reductions, Can one show NP-hardness by Turing reductions?, Graph problem known to be $NP$-complete only under Cook reduction, If you have a Cook reduction in both directions, do you also have a Karp reduction?, https://cstheory.stackexchange.com/q/686/5038, If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions, complexity-classes
---


title: Complexity of this variant of 3-SAT?

text:
# Question
Title: Complexity of this variant of 3-SAT?
This post introduces a new variant of 3-SAT called EQUAL-3-SAT, where the number of 3-Literal clause is equal to the number of variable.

> Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables.

> For example, this formula has $3$ variables and has $3$ clauses $(\lnot x\_1 \vee \lnot x\_2 \vee \lnot x\_3 ) \wedge (\lnot x\_1 \vee \lnot x\_3) \wedge (\lnot x\_2 \vee \lnot x\_3)$, This is an instance of EQUAL -3-SAT.

> and the following formula has three variables but has only two clauses $(\lnot x\_1 \vee \lnot x\_2 \vee \lnot x\_3 ) \wedge (\lnot x\_2 \vee \lnot x\_3)$. This is not EQUAL-3-SAT Insatance.

By, EQUAL-3-SAT we mean a set of clause such that each clause can contain at most 3 -literal and at least 1 literal ,but the total number of clauses in this set of clause is same as the number of variables present and this restrcition on the number of clauses is applicable even on clauses with literals \< 3.

I was curious if the following variant of EQUAL-3-SAT are NP-complete:

1. **EQUAL-3-NAE-SAT** where the number of clause is the still same as the number of number of variable but we need to check if its Not-all-Equal Satisfiable.

I thought the usual reduction from 3-SAT to 3-NAE-SAT would work here but I got confused as to how the reduction would work when there's a restriction on the number of clauses we can have with respect to the variables.

Is the above mentioned variant of EQUAL-3-SAT Np-Complete?

# Answer
Yes. Given any formula with more clauses than variables, pad with extra clauses of the form

$$(x\_t \lor x\_u)$$

where $x\_t,x\_u$ are fresh new variables used only in that clause. You can verify that in this way you can add enough padding to meet the "EQUAL" requirement. You should be able to take it from here.
> 2 votes

---
Tags: np-complete, 3-sat, schaefers-dichotomy
---


title: Summation over shortest path lengths

text:
# Question
Title: Summation over shortest path lengths
Suppose directed graph $G=(V,E)$, let $\delta(u,v)$ as the shortest path between any pair $u,v\in V$. Also there is no negative cycle in $G$. Can we conclude that $$\sum\_{u\in V}\sum\_{v\in V}\delta(u,v)\geq0\\;\\;?$$

I try to find a counter example but I guess that it's true because if $\sum\_{u\in V}\sum\_{v\in V}\delta(u,v)\<0$ there is negative cycle in $G$ but I can't prove it. Any hint will appreciated.

# Answer
I will assume that $\delta(u,v)$ denotes the *distance* from $u$ to $v$ in $G$ (and not the shortest path) and that $\delta(u,v) = +\infty$ if $v$ is not reachable from $u$.

You can write: $$\sum\_{u\in V}\sum\_{v\in V}\delta(u,v) = \frac{1}{2} \cdot\sum\_{u\in V}\sum\_{v\in V} \left( \delta(u,v) + \delta(v,u) \right) $$

Then you just need to observe that $\delta(u,v) + \delta(v,u) \ge 0$ for all choices of $u,v$. Indeed, if $\delta(u,v) + \delta(v,u) \< 0$ then the concatenation of a shortest path from $u$ to $v$ with a shortest path from $v$ to $u$ yields a closed walk $W = \langle u= w\_1, w\_2, \dots, w\_k = u\rangle$ of negative total weight.

$W$ might contain repeated intermediate vertices, hence it might not be a (simple) cycle. If you are fine with that, you are done.

Otherwise there must be some repeated vertex $w = w\_j = w\_h$ with $j \< h$ (and $(j,h) \neq (1,k)$) and you can decompose the edges of $W$ into two closed walks $W\_1 = \langle u = w\_1, w\_2, \dots w\_j, w\_{h+1}, \dots w\_k = u \rangle$ and $W\_2 = \langle w = w\_j, w\_{j+1}, \dots, w\_k = w\rangle$. At least one walk between $W\_1$ and $W\_2$, say $W^\*$, has negative total weight. Either $W^\*$ is a cycle and you are done, or you can repeat the same argument on $W^\*$. This process eventually stops since the number of vertices (counting repetitions) in $W^\*$ is monotonically decreasing.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Directed weighted multigraph with dynamic edges - shortest path
I need to create an implementation of a directed weighted multigraph with dynamic edges:

The edges will be changing during the pathfinding, in the following way:

Summary of the pathfinding:

1. Pathfinding starts at **S**.
2. **S -\> V1** (through edge with weight 3)
3. **V1 -\> V2** (through edge with weight 7, as edge with weight 3 is not available for this path).
4. **V2 -\> V4** is not possible, so we go back for another iteration.
5. **S -\> V1** (through edge with weight 3)
6. **V1 -\> V3** (through edge with weight 8)
7. **V3 -\> V4** (through edge with weight 3)
8. **V4 -\> E** (through edge with weight 6)

Of course, this is a simplification of the process, but to provide a general idea of how the edges would change, according to current path - let us take for example, that if **S -\> V1** was made via the edge with weight 5, then **V1 -\> V2** will be possible via both paths. As a conclusion, the available edges for each next vertex in the pathfinding depend on characteristics of the last edge that has been selected.

A real world example that represents this problem could be the following:

We want to use public transportation to reach from the **City of Turin (Italy)**, to the **City of Palermo (Italy)**.

There are several paths with several available transportation services between them. Let us take a look at the path **Turin (Italy) -\> Naples (Italy) -\> Palermo (Italy)**.

The following trains are available for the path **Turin -\> Naples**:

* **Turin -\> Naples** (departs at 13:00 and arrives at 19:00)
* **Turin -\> Naples** (departs at 15:00 and arrives at 21:00)

Also, the following boats are available for the path **Naples -\> Palermo**:

* **Naples -\> Palermo** (departs at 18:00 and arrives at 01:00 on the next day)
* **Naples -\> Palermo** (departs at 20:00 and arrives at 04:00 on the next day)

So, despite we have multiple edges between the vertices **Turin -\> Naples** and **Naples -\> Palermo**, we only have one available travel option, and it is **Turin -\> Naples** (departs at 13:00) + **Naples -\> Palermo** (departs at 20:00).

My questions are:

1. Is the best way to represent this problem as a directed weighted multigraph (what I have chosen as of this point) - vertices being the cities, edges being the transportation options, weight being the time of transportation (time of arrival - time of departure)?
2. What would be the most efficient way of finding the shortest path of such a graph with dynamically changing edges (no new edges will be added to the graph during traversal, only the existing ones will be turned ON & OFF, depending on the path chosen prior them)?

# Answer
> 1 votes
You can model the problem you have by creating, for each location, a set of vertices, each saying "arrive at X in time Y", for all Ys which are a departing time of a transportation from X.

Then, for each possible transportation service, you'd add a path from its departing time at its departing place to the departing time of the first transportation which leaves after its arrival time at the arrival location, and set its weight to the time difference between them.

Additionally, you need to add edges between different times in the same place, for the action of waiting in place.

For the example instance, you would get the graph

(This assumes the trains are daily, if they aren't you need to remove the edges which aren't valid actions)

After you create this graph (which would have $O(M)$ vertices and edges), you can run Dijkstra's algorithm on it to find a shortest path in time $O(M \log(M))$

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


# Question
Title: Can Sutner's (1991) quadratic algorithm for testing reversibility of Cellular Automata be applied to 1-D CA with even sized neighborhoods?
Admittedly I haven't fully wrapped my head around the paper yet, but I'm curious if this algorithm can be adapted to say, a one dimensional cellular automata with two states, and an even sized neighborhood, there are references in the paper to "neighbor radius" and neighborhood size of 2r+1. But the reversibility of neighborhoods of size 2, 4, and 6, for example, are also of interest to me.

A link to the paper is here: https://wpmedia.wolfram.com/uploads/sites/13/2018/02/05-1-3.pdf

I know of one other algorithm, from Amoroso and Patt (1972) that seems to be generally applicable to even numbered neighborhoods from a brief overview of the paper, but I can't seem to find a time complexity analysis of it within or without. Although, other papers seem to imply it is worse than quadratic. (And I have been less able to understand the paper)

# Answer
A CA with neighborhood size $s$ can be trivially emulated by a CA with any neighborhood size $s' \> s$ that just ignores the extra cells in the neighborhood. So if the method works for CA with odd neighborhood size, then it can also be applied to CA with an even neighborhood size simply by adding one cell to the neighborhood to make its size odd.

That said, based on an (admittedly very quick) skim of the paper, I suspect that this trick is actually unnecessary here, and that the method described in the paper can in fact be directly applied to even neighborhood sizes with few if any substantial changes. In particular, I suspect that nothing *really* breaks if you let $2r$ take any positive integer value, not just even values.
> 1 votes

---
Tags: graphs, time-complexity, cellular-automata
---


# Question
Title: Scheduling jobs with two people where part (a) of each job must be finished before part (b)
* There are `n` jobs each consisting of two parts: `a` and `b`.
* There are two people:
    + person `A` is completing part `a` of each job (one at a time), and
    + person `B` is completing part `b` of each job (also one at a time).
* **Constraint:** part `a` of each job must be completed **before** part `b`
* We are given for each `i`:
    + `a[i]` : the time that it takes to complete part `a` of job `i`; and,
    + similarly, `b[i]` for part `b` of job `i`.

The **problem** is to find an algorithm to determine

* an order such that the total time to complete all jobs is minimized.

Note: `A` and `B` are able to work in parallel.

My question is: how can we solve this problem? And, what is a good reference to learn to solve similar scheduling problems?

# Answer
What you are looking for is Johnson's algorithm for job scheduling.

Johnson's algorithm works as follows on the situation described in the question.

1. Select a part of a job with the shortest completion time (break ties arbitrarily).

Suppose the job is job $i$.

* If the part is $a\[i\]$, schedule job $i$ first.
    * If the part is $b\[i\]$, schedule job $i$ last.

Eliminate job $i$ from further consideration.
2. Repeat step 1, working towards the center of the job schedule until all jobs have been scheduled.

---

When implementing the algorithm above, we can first sort all jobs by the shorter completion time of part (a) or part (b) of each job.

The time-complexity of the algorithm is $O(n\log n)$.

---

There are huge numbers of problems and algorithms in job scheduling such as job-shop scheduling, flow-shop scheduling and open-shop scheduling. You might be interested in some articles/ that returned by google search for "job scheduling algorithms".

If you are programming for fun or for programming contest, you could learn scheduling algorithms on a case-by-case approach. If you are writing for production software, you may want to read the chapters on scheduling of some books on operating systems. Just my two cents. Depending on your need, there are a variety of choices to learn.
> 2 votes

---
Tags: algorithms, greedy-algorithms, scheduling
---


# Question
Title: How do I find the most even combination for two arrays
I have two arrays that both contain $n$ elements (positive, non zero, not negative)
$\\{x\_1\dots x\_n\\}$
$\\{y\_1\dots y\_n\\}$

I want to pair them up optimally, one from each array, so that the pairs come out as even as possible, when paired up optimally. I want the difference between the highest sum of pair values and the lowest such sum to be as small as possible.
I know there are brute force ways but they take $O(n^2)$ time, and I want the time complexity to be low, say $O(n^{1.5})$ or lower.

My approach is to sort one of the arrays in ascending order, and one in descending order and pair them up.
How would I go about making sure they are actually paired optimally so that difference between the smallest sum and the highest sum among pairs is as small as possible?

# Answer
> 0 votes
If your goal is to minimize the maximum absolute difference of each pair, I suggest trying to explore greedy algorithms. In particular, suppose the arrays are presented in sorted order, and suppose for the moment that there are no duplicates, so $x\_1 \< x\_2 \< \cdots$ and $y\_1 \< y\_2 \< \cdots$. Suppose $x\_1 \< y\_1$. What can you say about which element $x\_1$ should be paired with? Can you make a greedy choice and proceed, and prove that this will give an optimal algorithm?

# Answer
> 0 votes
> my approach is to sort one of the arrays in ascending order, and one in descending order and pair them up

Yes, that's optimal.

You pair the smallest x-value $x$ with the largest y-value $Y$. Suppose that's a mistake, i.e., you end up with a solution worse than some optimal better solution which pairs $x$ with some other $y \le Y$ (and thus pairs $Y$ with some other $X \ge x$). So that optimal solution has sums $x+y$ and $X+Y$. Now modify that optimal solution to use $x+Y$ and $X+y$ instead. We have $x+y \le x+Y,X+y \le X+Y$, so replacing $x+y$ and $X+Y$ with $x+Y$ and $X+y$ doesn't extend the range and thus the solution stays optimal. Meaning there is an optimal solution that does pair $x$ and $Y$. You're good.

---
Tags: algorithms, dynamic-programming, arrays, coding-theory
---


# Question
Title: Algorithm to find minimum amount of swaps to convert array A into array B with repeated elements
I'm trying to create an algorithm that finds the minimum number of swaps to convert array A into array B. In this case the arrays can only contain the numbers 0, 1 or 2.

So for example: given `a = [0, 2, 1, 2] and b = [1, 2, 0, 2]`. The minimum number of swaps to convert a into b is 1, namely swap a\[0\] and a\[2\].

I've tried implenting the "Minimum number of swaps required to sort an array" algorithm (from geeksforgeeks), but this returns a higher number of swaps than expected.

Some test cases that failed:

```
a = [1, 1, 0, 2, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 0, 0, 2, 0, 1, 2]
b = [2, 2, 0, 1, 0, 1, 1, 2, 1, 0, 2, 0, 1, 1, 0, 2, 2, 0, 1, 2, 0]
expected: <9> but was <16>

a = [0, 0, 1, 2, 1, 2, 1, 1, 2, 2]
b = [2, 0, 2, 2, 1, 2, 1, 1, 1, 0]
expected: <2> but was <4>

```

Code:

```
import java.io.*;
import java.util.*;

class GfG {
    // Function returns the
    // minimum number of swaps
    // required to convert array a to array b
    public static int minSwaps(int[] a, int[] b)
    {
        int len = a.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++)
            map.put(a[i], i);

        // Initialize result
        int ans = 0;
        for (int i = 0; i < len; i++) {
            // If the ith element of array a is already equal to the ith element of array b
            // then we don't need to swap anything, so we can move to the next element
            if (a[i] == b[i])
                continue;

            // If we need to swap the ith element of array a with some other element
            // then we can find that element in array a using the index of the ith element of array b
            // that we stored in the map earlier
            int j = map.get(b[i]);

            // Swap the ith element of array a with the jth element
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            // Update the index of the swapped element in the map
            map.put(a[j], j);

            // Increment the answer
            ans++;
        }
        return ans;
    }
}

// Driver class
class MinSwaps {
    // Driver program to test the above function
    public static void main(String[] args)
    {
        int[] a = { 0, 0, 1, 2, 1, 2, 1, 1, 2, 2 }; // for example
        int[] b = { 2, 0, 2, 2, 1, 2, 1, 1, 1, 0 }; // for example
        GfG g = new GfG();
        System.out.println(g.minSwaps(a, b));
    }
}

```

# Answer
> 1 votes
Ignore already correct A-values. If you can correct two A-values by swapping them, do so. This leaves you with 3-cycles, all 0→1→2→0 or all 0→2→1→0. Each can be corrected with two swaps.

Python implementation, where I keep count of the different mismatches:

```
from collections import Counter

def solve(A, B):
  ctr = Counter()
  swaps = 0
  for a, b in zip(A, B):
    if a != b:
      if ctr[b, a]:
        ctr[b, a] -= 1
        swaps += 1
      else:
        ctr[a, b] += 1
  print(swaps + ctr.total() // 3 * 2)

solve([1, 1, 0, 2, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 0, 0, 2, 0, 1, 2], [2, 2, 0, 1, 0, 1, 1, 2, 1, 0, 2, 0, 1, 1, 0, 2, 2, 0, 1, 2, 0])
solve([0, 0, 1, 2, 1, 2, 1, 1, 2, 2], [2, 0, 2, 2, 1, 2, 1, 1, 1, 0])

```

Attempt This Online!

---
Tags: algorithms, sorting, arrays
---


title: Minimize bottleneck in flow network

text:
# Question
Title: Minimize bottleneck in flow network
Let $G=(V,E)$ be a flow network with two vertices $s,t$ also each edge has its capacity equal to $\infty$. Our goal is to transfer a flow of size $C$ from $s$ to $t$ so that minimize an edge that has highest flow value in it.

I guess by $O(1) $ times using the Ford-Fulkerson we can minimize such an edge. First let $k$ be the degree of $s$, then I set the capacity of each edges that outs from $s$ to $\frac{c}{k}$. Now at this step I get stuck. Any hint about how I can do it will be helpful.

# Answer
> 1 votes
Let us reverse the question. In other words, consider the dual question.

Instead of minimizing the highest flow value of all edges that can transfer a flow of size $C$, let us compute the maximum flow value of the network if every edge has capacity $x$.

Suppose that maximum flow value is $m$, which can be computed by the Ford–Fulkerson algorithm. Then the highest flow value of all edges that can transfer a flow of size $C$ must be at least $x\cdot\frac Cm$, assuming $m\>0$. The case $m=0$ is easy.

---
Tags: algorithms, optimization, network-flow, duality
---


# Question
Title: Can somebody explain to me the concept of mutability with respect to a NumPy array?
From the NumPy documentation:

> "NumPy arrays have a fixed size at creation, unlike Python lists (which can grow dynamically). Changing the size of an ndarray will create a new array and delete the original."

To my understanding, this would make the numpy array *immutable*, but from what I've seen, they're actually mutable.

When I was trying to learn about the concept of mutability/immutability, it was with respect to strings, and I was having a hard time understanding why a string was considered immutable if I could, in fact, quite easily manipulate it with, for example, a simple addition operation with another string. What I took away from that inquiry was that the key distinction was that you're not actually changing the original string. You're creating a new string that's stored in a new variable which lives in a new memory location. Ok, that made sense.

So how is that different from what NumPy is saying it does?

# Answer
> 2 votes
Just because the *size* of the array is fixed doesn't mean it is immutable. In an immutable array, both the size and the contents must be immutable. With a Numpy array, you can change its contents (the values at each position) in place, without creating a new array.

---
Tags: arrays, python
---


# Question
Title: What's the most scalable solver of this problem?
Consider the following optimisation problem that its size is parameterised by $n$ (width) and $m$ (depth):

Find $w\_1, w\_2, \ldots, w\_n$ that minmises: $$ \min \Big\[w\_1x\_1^0 + w\_2x\_2^0 + \ldots + w\_nx\_n^0 \Big\] $$

Subject to:

$$ b^1\_{\min} \le w\_1x\_1^1 + w\_2x\_2^1 + \ldots + w\_nx\_n^1 \le b^1\_{\max} $$ $$ b^2\_{\min} \le w\_1x\_1^2 + w\_2x\_2^2 + \ldots + w\_nx\_n^2 \le b^2\_{\max} $$ $$ \vdots $$ $$ b^m\_{\min} \le w\_1x\_1^m + w\_2x\_2^m + \ldots + w\_nx\_n^m \le b^m\_{\max} $$

Where:

* $w\_1, w\_2, \ldots, w\_n$ are variables that we must tune (by assigning real numbers to them) in order to solve the optimisation problem above.
* for any $1 \le i \le n$ and $1 \le j \le m$, $x\_i^j$ is a constant real number, and $b^j\_{\min}, b^j\_{\max}$ are bounds.

Note that superscript $^j$ is not an exponent, but a second index. I thought it would be more readable to write $x\_i^j$ than $x\_{i,j}$.

***Question:*** What's the best asymptotic worst run-time and space that we can get for a solver of this problem?

E.g. can it get as low as $O(nm)$? if not, what's the lowest we can achieve?

# Answer
This is an instance of linear programming, so you can solve it with any LP solver.

Any instance of linear programming can be represented in this form. For instance, minimize $c^\top w$ subject to $Aw \le b$ can be represented by setting $b^i\_\max = b\_i$, $x^i\_j = A\_{i,j}$, $b^i\_\min=-\infty$, $x^0\_j=c\_j$. Therefore, you can't expect any special-case algorithm that is more efficient than general-purpose linear programming.

The worst-case complexity of linear programming is polynomial but a bit messy, but in practice it is often very efficient on real-world instances.
> 1 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Why is the complement of a language that is not regular also not regular?
In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not regular, he wrote that it follows from the fact that the second language was the complement of the first, which we had already proved was not regular.

I was wondering if anyone could explain why this is the case?

# Answer
> 12 votes
Because regular langauges are closed under complementation. That is, if $L$ is regular, so is $\overline{L}$. (Exercise: prove this.)

So, suppose that $L$ is non-regular. If its complement $\overline{L}$ were regular, then $\overline{\overline{L}}=L$ would also have to be regular.

# Answer
> 0 votes
You can show this fact by a quick proof by contradiction. If you are not familiar with proof by contradiction, I recommend you read up on it to understand how it works. And you should also know that regular languages are closed under complement. This means that if a language is regular, then its complement must also be regular.

**Proof:**

We are given that $L$ is non-regular, and we are trying to prove that $\bar{L}$ (complement of $L$) is also non-regular.

We can prove this through proof by contradiction. Let's make the assumption that $\bar{L}$ is regular. Since regular languages are closed under complement, then the complement of $\bar{L}$, that is $\bar{\bar{L}}$, must be regular. But $\bar{\bar{L}} = L$, and we know $L$ should be NOT regular. Therefore we have a contradiction. Therefore our initial assumption that $\bar{L}$ is regular is incorrect, which must mean $\bar{L}$ is non-regular.

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