# Question
Title: Comparison of different algorithms for summing floating point numbers
I am exploring several approaches to summing floating point values, such as:

1. Naive summation, for comparison
2. Summing sorted values
3. summing with numpy, again for comparison
4. Kahan's algorithm
5. Pairwise summation
6. Kahan's algorithm on the same sequence sorted by absolute value
7. Pairwise summation on the same sequence sorted by absolute value
8. The Python Decimal package, which is exact.

As shown below, I tested all of these algorithms on 14 arrays of floating point numbers, `not_okay`, from a real world problem.

```
import numpy as np
from math import floor
from decimal import Decimal

ok = [
    [6.333333333333335, 2.3333333333333335, 2.220446049250313e-16, -2.0, -1.0, -1.0, -1.0000000000000002, -0.9999999999999999, -4.710277376051324e-16, -0.6666666666666665, -0.6666666666666669, -0.6666666666666669],
    [2.3333333333333335, 6.333333333333334, 2.220446049250313e-16, -2.0, -1.0, -1.0, -4.710277376051324e-16, -1.0000000000000002, -0.9999999999999999, -0.6666666666666669, -0.6666666666666665, -0.6666666666666669],
    [2.220446049250313e-16, 2.220446049250313e-16, 9.333333333333334, -2.0, -0.9999999999999999, -1.0000000000000002, -0.9999999999999999, -1.0000000000000002, -0.6666666666666669, -0.6666666666666669, -0.6666666666666663],
    [-2.0, 6.333333333333335, -2.3333333333333335, -5.360630966617861e-16, -1.0, 1.0, -1.0000000000000002, 0.9999999999999999, -0.6666666666666665, 0.6666666666666669, 0.6666666666666669, -1.099064721078642e-15, 3.1401849173675484e-16],
    [-2.3333333333333335, 6.333333333333335, -1.1102230246251565e-16, 1.0, -1.0, -2.0, -4.710277376051324e-16, 0.6666666666666669, -0.6666666666666665, -0.6666666666666669, -1.0000000000000007, -0.9999999999999996]
]

not_ok = [
    [-2.0, 0.9999999999999999, -1.0000000000000002, 0.9999999999999999, -1.0000000000000002, 0.6666666666666669, 0.6666666666666669, -0.6666666666666663, -3.3306690738754696e-16, -3.3306690738754696e-16, 9.333333333333332, 3.1401849173675503e-16, -2.0, -0.9999999999999997, -1.0000000000000004, -0.9999999999999997, -1.0000000000000004, -0.6666666666666667, -0.6666666666666667, -0.6666666666666667],
    [-0.9999999999999999, -1.0000000000000002, -2.0, -0.6666666666666669, 0.6666666666666669, -0.6666666666666663, 3.1401849173675484e-16, 0.9999999999999996, -1.0000000000000004, 5.551115123125783e-16, -5.551115123125783e-16, 9.333333333333334, 3.1401849173675503e-16, 0.9999999999999997, -1.0000000000000004, -2.0, 0.6666666666666663, -0.6666666666666663, -0.6666666666666677, -0.9999999999999997, -1.0000000000000004],
    [-0.9999999999999999, -1.0000000000000002, 0.6666666666666669, -0.6666666666666669, -0.6666666666666663, -2.0, 0.9999999999999996, 3.1401849173675484e-16, -1.0000000000000004, 3.1401849173675503e-16, -5.551115123125783e-16, 5.551115123125783e-16, 9.333333333333336, 0.9999999999999997, -1.0000000000000004, -0.6666666666666663, 0.6666666666666663, -0.6666666666666677, -2.0, -0.9999999999999997, -1.0000000000000004],
    [-2.0, 0.9999999999999997, -1.0000000000000004, 0.9999999999999997, -1.0000000000000004, 0.6666666666666667, 0.6666666666666667, -0.6666666666666667, -7.771561172376096e-16, -6.661338147750939e-16, 9.333333333333334, -9.420554752102646e-16, -2.0, -0.9999999999999993, -1.0000000000000004, -0.9999999999999993, -1.0000000000000004, -0.6666666666666664, -0.6666666666666664, -0.6666666666666667],
    [-0.9999999999999997, -1.0000000000000004, -2.0, -0.6666666666666663, 0.6666666666666663, -0.6666666666666677, 0.9999999999999997, -1.0000000000000004, -3.625639149961434e-15, 2.9976021664879227e-15, 9.33333333333333, -9.420554752102646e-16, 1.0000000000000018, -0.999999999999998, -2.0, 0.6666666666666673, -0.6666666666666673, -0.666666666666665, 6.2803698347351125e-16, -1.0000000000000018, -0.999999999999998],
    [-0.9999999999999997, -1.0000000000000004, 0.6666666666666663, -0.6666666666666663, -0.6666666666666677, -2.0, 0.9999999999999997, -1.0000000000000004, -9.420554752102646e-16, 2.9976021664879227e-15, -3.6637359812630166e-15, 9.33333333333333, 1.0000000000000018, -0.999999999999998, -0.6666666666666673, 0.6666666666666673, -0.666666666666665, -2.0, -1.0000000000000018, 6.2803698347351125e-16, -0.999999999999998],
    [-0.6666666666666667, -0.6666666666666667, -0.6666666666666667, -0.9999999999999997, -1.0000000000000004, -0.9999999999999997, -1.0000000000000004, -2.0, -9.420554752102646e-16, -3.181549940111371e-15, -3.219646771412954e-15, 9.333333333333329, 0.6666666666666673, 0.6666666666666673, -0.666666666666665, 6.2803698347351125e-16, 1.0000000000000018, -0.999999999999998, 1.0000000000000018, 6.2803698347351125e-16, -0.999999999999998, -2.0],
    [-2.0, 1.0000000000000018, -0.999999999999998, 1.0000000000000018, -0.999999999999998, 0.6666666666666673, 0.6666666666666673, -0.666666666666665, -9.992007221626409e-16, -8.881784197001252e-16, 9.333333333333325, -9.420554752102646e-16, -2.0, -1.0000000000000018, -0.999999999999998, -1.0000000000000018, -0.999999999999998, -0.6666666666666664, -0.6666666666666664, -0.6666666666666667],
    [-0.9999999999999993, -1.0000000000000004, -2.0, -0.6666666666666673, 0.6666666666666673, -0.666666666666665, 6.2803698347351125e-16, 1.0000000000000018, -0.999999999999998, -1.703431368239316e-15, 1.7763568394002505e-15, 9.333333333333323, -9.420554752102646e-16, 1.0000000000000018, -0.999999999999998, -2.0, 0.6666666666666664, -0.6666666666666664, -0.6666666666666667, -6.280369834735128e-16, -1.0000000000000044, -0.9999999999999954],
    [-0.9999999999999993, -1.0000000000000004, 0.6666666666666673, -0.6666666666666673, -0.666666666666665, -2.0, 1.0000000000000018, 6.2803698347351125e-16, -0.999999999999998, -9.420554752102646e-16, 1.7763568394002505e-15, -1.5543122344752192e-15, 9.333333333333325, 1.0000000000000018, -0.999999999999998, -0.6666666666666664, 0.6666666666666664, -0.6666666666666667, -2.0, -1.0000000000000044, -6.280369834735128e-16, -0.9999999999999954],
    [-2.0, 1.0000000000000018, -0.999999999999998, 1.0000000000000018, -0.999999999999998, 0.6666666666666664, 0.6666666666666664, -0.6666666666666667, 1.2212453270876722e-15, 1.1102230246251565e-15, 9.333333333333321, 4.082240392577823e-15, -2.0, -1.0000000000000024, -0.999999999999998, -1.0000000000000024, -0.999999999999998, -0.6666666666666671, -0.6666666666666671, -0.6666666666666667],
    [-1.0000000000000018, -0.999999999999998, -2.0, -0.6666666666666664, 0.6666666666666664, -0.6666666666666667, -6.280369834735128e-16, 1.0000000000000044, -0.9999999999999954, 4.440892098500626e-15, -6.5503158452884236e-15, 9.333333333333329, 4.082240392577823e-15, 0.9999999999999974, -1.0000000000000029, -2.0, 0.6666666666666671, -0.6666666666666671, -0.6666666666666667, -0.9999999999999974, -1.0000000000000029],
    [-1.0000000000000018, -0.999999999999998, 0.6666666666666664, -0.6666666666666664, -0.6666666666666667, -2.0, 1.0000000000000044, -6.280369834735128e-16, -0.9999999999999954, 4.082240392577823e-15, -6.5503158452884236e-15, 4.3298697960381105e-15, 9.33333333333333, 0.9999999999999974, -1.0000000000000029, -0.6666666666666671, 0.6666666666666671, -0.6666666666666667, -2.0, -0.9999999999999974, -1.0000000000000029],
    [-0.6666666666666664, -0.6666666666666664, -0.6666666666666667, -6.280369834735128e-16, -1.0000000000000044, -0.9999999999999954, -1.0000000000000044, -6.280369834735128e-16, -0.9999999999999954, -2.0, 4.082240392577823e-15, 2.1094237467877974e-15, 1.9984014443252818e-15, 9.333333333333316, 0.6666666666666671, 0.6666666666666671, -0.6666666666666667, 1.0000000000000024, -0.999999999999998, 1.0000000000000024, -0.999999999999998, -2.0]
]

# https://en.wikipedia.org/wiki/Kahan_summation_algorithm
def kahan_summation(x):
    result = 0.0
    c = 0.0

    for x_ in x:
        y = x_ - c
        t = result + y
        c = (t - result) - y
        result = t

    return result

# https://en.wikipedia.org/wiki/Pairwise_summation
def pairwise_summation(x):
    if len(x) <= 2:
        return sum(x)
    else:
        m = floor(len(x)/2)
        return pairwise_summation(x[:m]) + pairwise_summation(x[m:])

def summation_algorithms(data):
    print("{:>24} {:>24} {:>24} {:>24} {:>24} {:>24} {:>24} {:>24}".format("naive sum", "sum sorted values", "numpy sum", "kahan sum", "pairwise sum", "kahan sum sorted", "pairwise sum sorted", "Decimal sum"))

    for values in data:
        sorted_values = sorted(values, key = lambda x_: abs(x_))

        naive_sum = sum(values)
        sum_sorted_values = sum(sorted_values)
        numpy_sum = np.sum(np.array(values))
        kahan_sum = kahan_summation(values)
        pairwise_sum = pairwise_summation(values)
        decimal_sum = sum([Decimal(str(x_)) for x_ in values])
        pairwise_sum_sorted = pairwise_summation(sorted_values)
        kahan_sum_sorted = kahan_summation(sorted_values)

        print("{:24} {:24} {:24} {:24} {:24} {:24} {:24} {:24}".format(naive_sum, sum_sorted_values, numpy_sum, kahan_sum, pairwise_sum, kahan_sum_sorted, pairwise_sum_sorted, decimal_sum))

#summation_algorithms(ok)
summation_algorithms(not_ok)

```

Result (row-wise)

```
               naive sum        sum sorted values                numpy sum                kahan sum             pairwise sum         kahan sum sorted      pairwise sum sorted              Decimal sum
 -2.4424906541753444e-15                      0.0   -6.661338147750939e-16  -1.9984014443252818e-15  -1.5543122344752192e-15  -1.7763568394002505e-15  -1.7763568394002505e-15      -1.752115323039E-15
  -1.887379141862766e-15  -1.7763568394002505e-15                      0.0  -1.3322676295501878e-15                      0.0  -1.7763568394002505e-15  -1.3322676295501878e-15      -1.071963016526E-15
  1.7763568394002505e-15                      0.0                      0.0                      0.0   1.7763568394002505e-15                      0.0    4.440892098500626e-16        9.28036983474E-16
 -2.7755575615628914e-15  -1.7763568394002505e-15  -2.7755575615628914e-15  -2.6645352591003757e-15   -3.552713678800501e-15  -1.7763568394002505e-15  -2.6645352591003757e-15      -1.985345407223E-15
  -6.661338147750939e-16                      0.0   -2.220446049250313e-16    4.440892098500626e-16  -1.7763568394002505e-15                      0.0    2.220446049250313e-16       -4.42055475209E-16
  -8.881784197001252e-16                      0.0   -8.881784197001252e-16   -4.440892098500626e-16   1.7763568394002505e-15                      0.0    2.220446049250313e-16      -4.801523065115E-16
 -1.9984014443252818e-15  -1.7763568394002505e-15  -1.1102230246251565e-15                      0.0                      0.0                      0.0                      0.0       -1.87178219786E-16
 -1.1102230246251565e-16                      0.0   3.3306690738754696e-16                      0.0   -4.440892098500626e-16                      0.0    8.881784197001252e-16        2.70565382927E-16
 -1.2212453270876722e-15  -1.7763568394002505e-15  -2.1094237467877974e-15   -1.887379141862766e-15  -2.6645352591003757e-15  -1.7763568394002505e-15  -1.3322676295501878e-15      -1.469130004049E-15
  -5.551115123125783e-16                      0.0   1.2212453270876722e-15    7.771561172376096e-16    8.881784197001252e-16                      0.0    6.661338147750939e-16       6.799891297155E-16
  -7.771561172376096e-16                      0.0    -2.55351295663786e-15   -4.440892098500626e-16   -8.881784197001252e-16                      0.0   -4.440892098500626e-16       -5.86291255709E-16
   6.661338147750939e-16                      0.0   -6.661338147750939e-16   -4.440892098500626e-16   -8.881784197001252e-16                      0.0   -8.881784197001252e-16        3.44779662317E-16
  2.4424906541753444e-15   1.7763568394002505e-15   1.5543122344752192e-15   1.7763568394002505e-15   2.6645352591003757e-15   1.7763568394002505e-15    8.881784197001252e-16       1.233757359854E-15
                     0.0                      0.0    8.881784197001252e-16    4.440892098500626e-16   -8.881784197001252e-16                      0.0    2.220446049250313e-16        1.33991616743E-16

```

Disappointingly Kahan's method does not seem to work well. In fact no other method consistently agrees with the "Decimal sum".

What am I doing wrong? Is there a better way to approach this problem?

---

As a sanity check of my implementations I provided five arrays of "unproblematic" floating numbers `okay` the sum of which is given below

```
               naive sum        sum sorted values                numpy sum                kahan sum             pairwise sum         kahan sum sorted      pairwise sum sorted              Decimal sum
      0.6666666666666671       0.6666666666666687       0.6666666666666671       0.6666666666666677        0.666666666666667       0.6666666666666679       0.6666666666666679 0.666666666666667851016867320
      0.6666666666666666       0.6666666666666679       0.6666666666666666       0.6666666666666673        0.666666666666667        0.666666666666667       0.6666666666666679 0.666666666666666851016867320
      1.3333333333333337        1.333333333333334       1.3333333333333337        1.333333333333334        1.333333333333334        1.333333333333334       1.3333333333333344 1.333333333333334144089209850
      2.6666666666666674        2.666666666666667       2.6666666666666674        2.666666666666667       2.6666666666666674        2.666666666666667        2.666666666666668 2.666666666666667178890673996
     -0.6666666666666654      -0.6666666666666652      -0.6666666666666654      -0.6666666666666663      -0.6666666666666652      -0.6666666666666661      -0.6666666666666659 -0.666666666666665882050040068

```

# Answer
> 1 votes
Kahan’s algorithm calculates a+b and the exact rounding error if |a| \>= |b|. Actually for a slightly larger range of values. So for a sum of array elements, if the sum so far is always absolutely greater than the next array element, then Kahan calculates simultaneously the naive sum, and the naive sum of the exact rounding errors. The sum of rounding errors will have a very small error because the numbers added are small. So adding the naive sum and the sum of rounding errors will very often give the correctly rounded result.

Exceptions are: If the sum of the numbers as real numbers is quite precisely between two floating point numbers, and instead of rounding by 0.4999999999 bits in one direction the result is rounded by 0.500000001 bits in the other direction. And the other situation, if the sum is much smaller than the original numbers. Worst case the correct sum is smaller than the individual rounding errors.

And of course the big exception: If the first operand had a smaller absolute value during the summation. That’s easy to fix: if |a| \< |b| then calculate b+a instead (same as a+b obviously) but calculate the rounding error for b+a which will then be correct.

None of these methods will guarantee a correctly rounded sum. All you can do is keep the error smaller.

---
Tags: floating-point
---


# Question
Title: Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$
I want to build a context sensitive grammar for the language $\\{a^{2^n}\mid n\geq 0\\}$. I think it should be something like this \begin{align\*} S &\to aA \mid a\\ aA&\to aaaA \mid aa \end{align\*}

# Answer
This is from Hopcroft and Ullman's book, Example 9.4, pg 220:

$$ S \rightarrow ACaB $$ $$ Ca \rightarrow aaC $$ $$ CB \rightarrow DB $$ $$ CB \rightarrow E $$ $$ aD \rightarrow Da $$ $$ AD \rightarrow AC $$ $$ aE \rightarrow Ea $$ $$ AE \rightarrow \epsilon $$

**Update**: in fact given grammar is unrestricted which can be modified as a context sensitive.

But if your ultimate goal is to prove that the given language is a CSL, then it is enough to create a **linear bounded automaton** \- a TM whose computational ability is restricted to the portion of input. In other words, the head of the TM cannot move beyond the input area. LBA's and CSG's are equivalent.

You can just erase one input symbol at a time starting from the right, and each time you erase one symbol increase a counter by one (binary symbols 0 and 1) which are stored in place of erased symbols. When you erase all input symbols check if the counter is of the form 100...0. If yes then accept, otherwise reject). 100...0 means it is a power of 2.
> 2 votes

# Answer
I just had this as a homework and would like to share an IMO much simpler and more intuitive solution than the one from the textbook.

$$ \begin{align\*} S&\rightarrow EAE\ |\ a\ |\ aa\\ EA&\rightarrow E2A\ |\ TA\\ 2A&\rightarrow AA2\\ 2AE&\rightarrow AAE\\ TA&\rightarrow aaaaT\\ TAE&\rightarrow aaaa \end{align\*} $$

$E$ marks beginning and end. $2$ marks that we do another doubling of our number of $A$s and whenever a $2$ is inserted, it then "walks" over the whole string, doubling all $A$s it passes. $T$ is used to translate the $A$s into $a$s. We translate $A$ to $aaaa$ instead of $a$, so that our grammar is context sensitive.
> 2 votes

# Answer
The shortest non-contracting grammar we could come up with is: \begin{align\*} S&\rightarrow a\ |\ LR\\ L&\rightarrow LD\ |\ D\\ Da&\rightarrow a^2D\\ DR&\rightarrow aR\ |\ a^2 \end{align\*}

* L marks the left side of the word, produces the doubling symbol D, and can only be eliminated by conversion to a D.
* D is moved through the word from left to right, doubles each a and can only be eliminated on an R.
* R marks the right side of the word and also acts like an a, to accomplish non-contraction in the rules. It can only be eliminated with a D.

The shortest non-trivial derivations are: \begin{align\*} S\rightarrow LR\rightarrow DR\rightarrow a^2\\ S\rightarrow LR\rightarrow LDR\rightarrow DDR\rightarrow DaR\rightarrow a^2DR\rightarrow a^4 \end{align\*} Hence, the number $i$ of D's produced with the rule $L\rightarrow LD$ determines which word $a^{2^i}$ is generated by the grammar.
> 1 votes

# Answer
How do you express the rule $Da\rightarrow aaD$ in terms of valid rules of CSG? I mean, rules like $\alpha A\beta\rightarrow\alpha\psi\beta$.
> 0 votes

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: ( Soft question ) P vs NP - is such a situation possible?
Currently P vs NP is the holy grail of theoretical computer science. And the nature of the problem is as such that if actually P = NP is proved then most of the proofs for mathematical statements would be trivial to find, and on the exact other end if P != NP is proved then one would appreciate the hardship of finding its own proof finally....

People working in this field are so tired and exhausted of trying to find the solution that many have accepted that they might not even be alive by the time its solved, and many believe we would have to make some other groundbreaking discoveries in math to even be able to think of a rigorous solution.

In fact almost every proof method frequently used to separate complexity classes - like in halting problem's proof - have been proven "insufficient" to solve the problem...

Regardless of the answer being positive or negative, is it possible that if a proof is announced and its actually correct - ONLY for us to realise how trivial it actually was...? like we actually never needed any new concepts... the whole problem was basically hiding right in front of our sight. And maybe or maybe not we require other monumental maths to recognise the trivialness of the problem, but the proof itself, a rigorous and correct one, only needs concepts we have today.....

I know such extreme cases are rare or maybe haven't even occurred yet in maths, but the shear simplicity of the problem - in the sense that a 7th standard student can grasp the essence of the problem efficiently and effectively, just makes me wonder about this situation many a times....

# Answer
Yes of course it is possible. Everything is possible. Such situations have been rare in mathematics, so I would not bet on it, but we have no way to rule out such a possibility. We do know that most of the standard proof techniques we use every day in complexity theory are unlikely to work, which might be taken as some kind of evidence that it's less likely that the proof will turn out to be simple, but you never know.

In any case, it doesn't really have any actionable implications that I can see, so it's probably not worth worrying about too much.
> 0 votes

# Answer
Consider what happens if I find a polynomial time solution for an NP complete problem. Say a solution taking $n^{100}$ nanoseconds on my computer.

For n = 2 that’s $2^{100} \approx 10^{30}$ nanoseconds. Or $10^{21}$ seconds. Or 30 trillion years. So all but the smallest instance are not trivial, but practically unsolvable.

Now here is a problem that was believed to be very hard and is now known to be trivial: I’ll give you one integer n \>= 0 and m \>= 1, and you tell me if there are a, b, c \>= 1 with at most $10^m$ digits so that $a^n + b^n = c^n$. Finding the answer for n = 3 or n = 4 alone was very, very hard. Today I know that the answer is “Yes” if n=1 or n=2 and “No” otherwise.
> 0 votes

---
Tags: complexity-theory, np-complete, p-vs-np, open-problem
---


# Question
Title: Expected maximum matching size in a random bipartite graphs
What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed $p$. If a general formula doesn't exist how about for $p = 0.5$ or some other $p$.

# Answer
> 2 votes
There is not likely to be any exact formula, but we can investigate the asymptotic behavior. If $p$ is a little bit larger than $(\log n)/n$, then with high probability there exists a maximum matching, so the expected size of the maximum matching is close to $n$. See https://math.stackexchange.com/q/1267387/14578.

So the only interesting case is where $p \< (\log n)/n$. I don't have an estimate for that case, but perhaps someone else will be able to handle that case.

---
Tags: algorithms, graphs, bipartite-matching, bipartite-graph
---


title: About next operator duality in LTL

text:
# Question
Title: About next operator duality in LTL
I'm learning LTL (linear temporal logic) and we learned that a model $M$ and a starting position $q\_0$ satisfies a LTL formula $\psi$ iff for every path $\pi$ starting at $q\_0$ it is true that $\pi \models \psi$.

I also learned that the Next ($X$) operator is dual to its negation meaning $X \neg p = \neg Xp$. This confuses me, because in the simple example below, $Xp$ doesn't hold, hence $\neg Xp$ holds, and from the equality, $X \neg p$ holds, but that means that every path starting from $q\_0$, $\neg p$ holds, which clearly isn't true.

Where does my logic doesn't hold?

# Answer
> 1 votes
Your error is in the sentence "Xp doesn't hold, hence ¬Xp holds". In your example, neither Xp nor ¬Xp hold for the model: of the two possible traces in the model, the upper branch only satisfies Xp, and the lower branch only satisfies ¬Xp. Neither Xp nor ¬Xp hold for *all traces in the model*, so neither of these LTL formulas holds for the model. TL;DR M ⊨/ φ does not imply M ⊨ ¬φ .

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


# Question
Title: Expression with fastest growth in lambda-calculus
Well-known example of divergent expression in lambda calculus is big-Omega combinator, defined as `(λf. f f)(λf. f f)`. Although big-Omega is divergent expression, it's size became stable and always equal `(λf. f f)(λf. f f)` . Big-Omega combinator can be extended to provide more growth speed, for instance, expression `(λf. f f f)(λf. f f f)` has linear growth speed and increases by one term `(λf. f f f)` via one beta-reduction.

Expression divergence growth speed can be significantly increased to exponential one with using following lambda-expression `(λf.λu. f f (u u))(λf.λu. f f (u u))(λx.x)`, which doubles `(λx.x)` every two beta-reductions. Of course, by doubling `(u u)` in `(λf.λu. f f (u u))` term growth speed can be increased, but still left in exponential class. Also, another mechanics can be applied to increase growth so on.

But question is: which lambda expression has largest theoretically-known growth speed, and what this growth speed is? For example, in different mathematical fields there are huge numbers, like Tree(3) or BigFoot. Maybe is there known something like equivalent for lambda-calculus - divergent expression with maximum divergence growth speed?

Thanks!

# Answer
> 2 votes
Ok, I want to interpret this question as: what is the biggest growth rate a term $t$ of size $|t| = C$ can have, after $n$ $\beta$-reductions (as a function of $n$).

There are several different interpretations for the question, as well as within the question: for example, am I allowed to pick *which* $\beta$-reduction I want at each step, or do I want the "worst case" (smallest increase possible)?

All these questions are interesting!

It's pretty easy to bound the growth from above by $C^{2^n}$ (double exponential): a redex $(\lambda x.t)\ u$ has at most $C$ occurrences of $x$ and the size of $u$ is also bounded by $C$, which gives $C^2$ as the maximum size for $t\[u/x\]$.

Iterating this gives $(({C^2})^2)^\ldots$, that is, $C^{2^n}$.

But is this upper bound attained? I suspect not. As you note, there is an exponential lower bound, which leaves quite a gap.

---
Tags: computability, lambda-calculus
---


title: Optimal torch placement in voxel games

text:
# Question
Title: Optimal torch placement in voxel games
# Problem definition

The world consists of an infinite three-dimensional cartesian grid, i.e. every position is in $P = \mathbb{Z}^3$.

Neighbours of a position $p \in P$ are defined by $N(p) = \\{p + e\_1, p - e\_1, p + e\_2, p - e\_2, p + e\_3, p - e\_3\\}$, where $e\_i$ are the unit vectors, for example $e\_1 = (1,0,0)^T$.

For a torch placement $T \subset P$, at each position $p$, there is a voxel $b(T, p)$, which is air, a torch or stone: $$ M \subset 2^{P} \\ b: M \times P \rightarrow \\{air, torch, stone\\} \\ b(T, p) = torch \iff p \in T $$ Furthermore, a torch can only exist next to stone and the positions of stone voxels are fixed: $$ \forall p \in P: \left(b(T, p) = torch \Rightarrow \exists n \in N(p): b(\\{\\}, n) = stone\right) \\ \forall p \in P: \left(b(T, p) = stone \iff b(\\{\\}, p) = stone \right) $$

Light originates from torches, recursively spreads to neighbouring positions, and does not go into stone. This means the light $l(T, p)$ at the position $p$ is defined by $$ l(T, p) = \begin{cases} 0, & b(T, p) = stone \\ 12, & b(T, p) = torch \\ max(\\{1\\} \cup \\{l(T, n) | n \in N(p)\\}) - 1, & b(T, p) = air \end{cases} $$

Light at $p$ has an effect on visibility ($v(p)$) if and only if it is next to stone and not in stone itself, i.e. $$ v(p) \iff b(\\{\\}, p) \neq stone \land \exists n \in N(p): b(\\{\\}, n) = stone $$

The optimisation problem is to find a torch placement $T$ such that everything is visible with a light of at least one and as few torches as possible are placed: $$ T\_{opt} \in argmin\_{T}\left\\{|T| : \forall p \in P: (v(p) \Rightarrow l(T, p) \> 0) \right\\} $$

To make the optimisation feasible, we assume that everything outside a cube of side length $a$ is stone: $$ \forall p \in P: \forall i \in \\{1,2,3\\}: (p\_i \< 0 \lor p\_i \geq a \Rightarrow b(\\{\\}, p) = stone) $$

# My Question

I know that it is possible to find a $T$ with a greedy algorithm which places torches one after another until everything is lit up sufficiently, but it does not give an optimal solution in general, so it gives only an upper bound on $|T\_{opt}|$.

Is there a computational and memory-efficient algorithm to find a $T\_{opt}$ and what is its asymptotic time and memory requirement with respect to $a$?

# Answer
> 3 votes
No, assuming $\mathsf{P} \neq \mathsf{NP}$ there is no efficient algorithm for optimal torch placement, even if the world is just a 2D grid.

This can be shown by providing a reduction from the vertex cover problem on cubic planar graphs, which is known to be $\mathsf{NP}$-hard. I'm only going to sketch the general idea of the reduction, so I'll be somewhat sloppy.

Let $G = (V, E)$ be a cubic planar graph with $n = |V|$ vertices edges and consider an embedding on the infinite grid such that all edges can be drawn with axis-parallel polylines between the corresponding vertices. Now "scale up" this embedding so that each vertex becomes a square and there is "enough space" between different edges and vertices.

The whole world (a plane) except for consists of stone except for the following "room" and "tunnel" gadgets, that will encode vertices and edges (respectively).

Each vertex $v$ of the graph is encoded by the following "room".

This room has three openings on the top which we will use to connect the three edges incident to $v$. Moreover, this room has the following properties:

* Regardless of the placement of the torches outside of the room, there must be at least one torch inside the room.
* Regardless of the placement of the torches outside of the room, there is exactly only way to illuminate the whole room with one torch, i.e., placing the torch in the spot highlighted in yellow.
* A torch in the yellow spot "provides no light" to the locations immediately after the three openings (marked with $x$).
* Any light coming from one of the three openings cannot "reach" any other opening.
* Using two torches (e.g. in the yellow and in the red spot), it is possible to light the whole room and provide a light level of at least $4$ to all the locations marked with $\times$.

Each edge $e=(u,v)$ is encoded with a "tunnel of width 1" having a length of $23k\_e + h\_e$ where $k\_e$ is a positive integer and $h\_e \in \\{1,2\\}$. The tunnel can twist and bend in 90-degree turns and connects an opening of $u$ with an opening of $v$. Notice that it is always possible to create tunnels of the prescribed length. Indeed, it suffices to ensure that the tunnels detaching form a node continue straight for at least $30$ blocks. In this way each tunnel has at least $12$ sections as the one shown below in figure (a) (i.e., $6$ sections for each endvertex). Each of these $12$ sections can be kept unaltered or it can be replaced with the one of figure (b) to extend the length of the tunnel by $2$. This allows to extend the length by any even amount of choice ranging from $0$ to $24$, which is always enough to satisfy the constraint.

Consider any (partial) placement of torches that lights up all the rooms and let $23k\_e + h\_e$ be the length of a generic tunnel that corresponds to edge $e = (u,v)$. If $u$ and $v$ have exactly one torch each, at least $k\_e+1$ torches need to be placed in the tunnel (since each torch lights up at most $23$ spots). If at least one of $u$ and $v$ provides a light level of at least $2$ on the first location of the tunnel (marked with $\times$), then $\left\lceil \frac{23k\_e+h\_e - 2}{23} \right\rceil \le k\_e$ torches suffice. Moreover, regardless of the light levels provided by $u$ and $v$ on their respective entrances of the tunnel (which can be at most $11$), at least $\left\lceil\frac{23k\_e+h\_e - 2 \cdot 11}{23} \right\rceil \ge \left\lceil \frac{23k\_e - 21}{23} \right\rceil = k\_e$ torches are needed to light up the tunnel.

This shows that if there exists a vertex cover $S$ of size at most $x$, we can light up all the world with at most $n + x + \sum\_{e \in E} k\_e$ torches (place a torch in the yellow spot of each room, place a torch in the red spot of the rooms corresponding to vertices in $S$, use $k\_e$ torches for each tunnel $e$).

On the other hand, if we can light up the whole world with some arrangement of at most $n + x + \sum\_{e \in E} k\_e$ torches, then there must also be an arrangement that uses at most the same number of torches in total but uses exactly $k\_e$ torches for each tunnel $e$ (there cannot be less than $k\_e$ torches in the tunnel; if there are more than $k\_e$ torches then add one to an arbitrary endvertex of $e$ and re-light the tunnel using exactly $k\_e$ torches).

Consider such an arrangement: since each tunnel $e=(u,v)$ uses exactly $k\_e$ torches, at least one of the rooms of $u$ and $v$ contains more than one torch. Then the set $S$ of vertices whose rooms contain $2$ or more torches is a vertex cover. Since each room must use at least one torch, $|S| \le \left( n + x + \sum\_{e \in E} k\_e \right) - \sum\_{e \in E} k\_e - n = x$.

---
Tags: algorithms, optimization
---


title: $k$-way number contiguous partitioning

text:
# Question
Title: $k$-way number contiguous partitioning
Given a set $S$ of $n$ positive integers $S=\\{a\_1,\ldots,a\_n\\}$, can we partition $S$ into $k$ subsets of equal sum such that each subset has contiguous elements from $S$?

Here, a contiguous subset is in the form $\\{a\_i,a\_{i+1},a\_{i+2},\ldots\\}$ for some $i$. For example, with $S=\\{3,6,2,1\\}$, possible contiguous subsets are $\\{3\\}$, $\\{3,6\\}$, $\\{3,6,2\\}$, $\\{6,2,1\\}$, etc.

Is this variant of $k$-wat number partitioning NP-hard?

# Answer
The problem is in $\mathsf{P}$ (and is not trivial), hence it is $\mathsf{NP}$-Hard if and only if $\mathsf{P} = \mathsf{NP}$.

In particular, you can design an easy linear-time greedy algorithm by observing that the sum of the numbers in each set of the partition must be exactly $T =\frac{1}{k} \sum\_{i=1}^{n} a\_n$. Since all $a\_i$ are integers, the answer can only be yes if $T$ is an integer. Moreover, since all $a\_i$ are positive, either there is no index $j$ such that the elements in $\\{a\_1, a\_2,\dots, a\_j\\}$ sum to $T$, or such a $j$ is unique. In the latter case $\\{a\_1, a\_2,\dots, a\_j\\}$ must be one of the sets of the partition, hence you can select it and repeat the above argument starting form $a\_{j+1}$.

Here is the pseudocode of an iterative implementation of this algorithm, where `a[i]` represents $a\_i$:

```
T = a[1] + a[2] + .... + a[n]
if T%n != 0:
  return false

T = T/k              //target sum of each set of the partition
sum = 0              //sum of the elements in the current set of the partition
for i = 1, ..., n:
  sum = sum + a[i]
  if sum > T:        //no way to create the next set with sum T
    return false

  if sum = T:        //we found the next set of the partition
    sum = 0

return true

```
> 1 votes

---
Tags: partitions
---


title: The three elevator problem

text:
# Question
Title: The three elevator problem
There are three elevators in a building that has twelve floors. Find an algorithm that needs to find the best possible way for the elevators to stop at any particular floor considering the traffic waiting for the lift on that floor. Consider the following constraints:

1. there can be any number of people that need to use the lift at any given time
2. these people can be on any floor at any time (they do not particularly start at the ground floor)
3. there is no way of finding the accurate number of people waiting for the elevators on any floor
4. there are two buttons next to each of the elevators, for calling the lift up and down

This is just an actual problem I am facing. The building I live in has three elevators and I think its code is bad. Put thoughts, interesting changes to the problem itself and of course creative solutions. Thank you ;)

# Answer
> 0 votes
For a precise problem statement, first describe how a “standard” elevator setup works. Human users are supposed to know how it works and do things to get where they want to get.

There are lifts, floors, and a scheduler. Lifts are in the “up”, “down” or “idle” mode. They are standing still or they are moving. When standing still the door will be opened until it is safe to close. When moving there is a destination where to stop, and the next floor where it can stop. The lift will go there, stop, and open the door.

Each lift has buttons for each floor that the users press; each sets a destination. There may be another destination set by the scheduler. In up mode, the elevator goes up to the next destination upwards and stops there, then forgets that target. It stays in up mode until it has stopped, opened and closed the door, and there is no higher destination; similar in down mode.

On each floor, there are buttons to call a lift to go up, or to go down. There are indicators outside each lift showing whether a lift in “up” mode is going to stop on the floor, or a lift in “down” mode is going to stop. Pressing th up/down button indicates that at least one person wants to go up or down. This stays active until a lift going in the right direction stops. If people do not all fit then they need to be clever enough to wait until the lift leaves and press the button again once the lift is gone.

The scheduler gets all the state. All that it can do is to set an external destination for each lift (or none).

So you describe the lift state: Up, down, or idle. Moving to destination, next possible stop, stopped with door opened, stopped with door closed again. List of internal targets. Optional external targets. The floor state: Someone wants up or not. Someone wants down or not. Outside each lift: Lift will stop or is stopped to go up, same for down.

Most of the actions are forced. What is not forced is the external destination that the scheduler can set, that’s what you are optimising. The scheduler sets external destinations for the lifts if anyone wants to go up or down. Since it knows all the state it may just call the lift that will arrive first going in the right direction.

Rules for setting external destination: The scheduler cannot change the direction of a lift. So if someone wants up, you can call a list that is idle or that goes up and isn’t past this floor. You can estimate the time: The time a lift travels, plus time for each stop. The cost is a function of the waiting time, plus a function of lift wear and tear.

Note that the scheduler can change its decision, for example if a lift stayed on some floor for a very long time, or users in the lift add stops. But it is very bad style to announce that a lift is coming, and then clearing it.

Now if you wanted advice how to solve the optimisation problem: No. The difficult part is stating the problem. You need to do that very, very, very carefully. Then at any point in time, the scheduler makes three decisions which lift to send to which floor or whether not to send it anywhere. This decision is updated every time something happens, and every second (in case guesses about timing were wrong). That part is easy.

---
Tags: algorithms
---


# Question
Title: If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?
First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could the size of the input vary if the problem was the three dimensions one? Seems not if the number of equations is limited. Could this problem be classifiable in a problem class?

Trying to figure it out...but stuck.

Navier-Stokes problem

P vs NP problem where you can find the formal definition of P and NP problems.

I have been reading the following question, it did not help me, but may help to answer my question. Why is the set for which a decision problem is true called a "language"?

# Answer
> 1 votes
Languages are a good way of discussing *yes or no* questions with a *finite bit-length input size*. There are plenty of alternatives to languages, in complexity theory! They often have some 'moral equivalence' to languages.

Two important cases are *Function problems* and *Approximation problems*.

Function problems give you some bitstring $s$ and you need to compute some output function $f(s)$. Now instead of the set $\mathsf{P}$ of polynomial time *languages*, you talk about the set $\mathsf{FP}$ of functions that a language can compute in polynomial time. There is also $\mathsf{FNP}$, problems where you can compute the answer if you manage to guess the right 'proof'; $\mathsf{FBPP}$, where you can compute the right answer with probability at least 2/3; and so on.

Approximation problems are sort of a refinement of function problems, where now the input string $f(s)$ is interpreted as a real number (in some standard encoding) and you're asked to give not necessarily the exact number, but to give *a* number somewhere close to $f(s)$. The input consists of the problem string $s$ together with a precision parameter $\epsilon$. Typically you talk about multiplicative approximation where you need to answer within a factor of $1\pm \epsilon$, or additive approximation where you need to answer within an additive error of $\pm \epsilon$. Some important classes here are $\mathsf{FPTAS}$, see here, which includes problems that you can solve in time $O(n^3 / \epsilon^3)$, for instance; $\mathsf{APX}$, see here, where you can solve in polynomial time as long as $\epsilon \> c$ for some constant $c$; and others.

Alright, with that out of the way!

---

"Solving the Navier-Stokes equations", as a problem, I would generally write down as an approximation problem as follows. The input string gives some finite-size description of the initial state. This would probably be a grid size $n$, where I specify initial pressure and velocity values at each point on the grid. Then we have some agreed-upon encoding to turn this into a continuous function: for instance, third-order polynomial interpolation. This defines an initial state. There is similar data for boundary conditions. Then you give me a time $t$, a point $(x,y,z)$, a query variable that is one of the thre symbols $\\{VX,VY,VZ\\}$, and a precision $\epsilon$. The problem is then to output the relevant variable (the velocity $VX$, or $VY$, or $VZ$) after evolving the initial conditions for $t$ time, and to output with an additive error $\epsilon$.

The difficulty of the problem would be quantified in terms of different quantities like $n$ (the complexity of the boundary conditions), the precision $\epsilon$, and the time $t$. Difficulty could also be in terms of the Lipschitz constant $K$ of the boundary conditions, or the *magnitude* $M$ of the initial conditions (if I make all the initial velocities extremely fast, I could make things happen very quickly and the problem might become might harder!), or the *energy* $E$ of the system, or the worst *condition number* $\kappa$ reached during solving.

I think people would consider the Navier-Stokes equations to be "polynomial time" if there was an algorithm to solve this, with a runtime like $O(n^{c\_1} t^{c\_2} \epsilon^{-c\_3} K^{c\_4} M^{c\_5})$, where $c\_i$ are all some constants. Equivalently, if it run in $poly(ntKM/\epsilon)$ time.

The differential equations that people generally regard as "well-behaved" all have algorithms of this form. There are some differential equations that compute (say) the answer to an NP-hard problem in a small amount of time -- in the sense that, if you had a poly time algorithm to solve them (in the sense I just gave), that it would imply $P=NP$.

---
Tags: computability, decision-problem, p-vs-np
---


# Question
Title: How are pointers modeled on bit-based computer models?
## Why bit-based computer models?

The perhaps most commonly used computer model is a random access machine that can store natural (or even real) numbers in infinitely many cells indexed by natural numbers. This model's main benefit is that it greatly simplifies calculating Runtimes, as arithmetic and indexing are simply assumed to be O(1), so that there is no need to estimate the size of numbers and pointers used, greatly simplifying runtime estimation.

This model is however obviously not realistic, as real computers simply cannot save natural numbers of any length in one "cell", or operate on them in constant time. This sort of constitutes the necessity of bit-based (or byte-based) computer models, where any cell holds either 1 or 0. The best known one of those is the Turing Machine.

## The indexing problem

While one certainly can simulate indexing on a Turing Machine or similar, it is probably painstakingly slow. In reality, this problem is solved by building computers with specialized indexing hardware, and this remedy obviously is not accounted for in the Turing Machine model.

## The question

**Now the question is, is there a bit-based computer model that models faster indexing (which in reality is achieved by specialized hardware) in a senseful way?**

In particular, is there a bit-based model where indexing is in O(1), regardless of index length? Would such a model even make sense?

# Answer
It sounds like you're just asking for the definition of Random-access machine, which is similarly formal to Turing machines, but formally defines how to do "indexing" operations.

There's also easy ways to equip a Turing machine with random access capabilities. You give it an extra "index" tape that it can only write to (so it can't use it for extra read-memory), and the Turing machine has an extra operation which is "Query". Upon doing a "Query" operation, you look at the position on the (main) tape pointed to by the "index" tape, take the symbol there, write it under the Turing machine's head on the (main) tape. So in this way, the Turing machine writes out the location that it wants to read, in binary, and then the query lets it copy the appropriate data from there. Similarly, then, there's a "Store" operation that takes the symbol under the Turing machine's head and writes it somewhere else in memory based on what's on the index tape. This generally captures efficient pointer operation. It does mean that copying pointers takes $\log(n)$ time, where $n$ is the size of memory in use. Typically $\log(n)$ factors are happily ignored of course; they only come into play when doing *very* fine-grained runtime analysis. It also adds a factor of $\log(n)$ to space complexity over a RAM-style "register machine", which is slightly more likely to be an issue.
> 2 votes

---
Tags: time-complexity, asymptotics, computer-architecture, runtime-analysis, computation-models
---


# Question
Title: Is there an algorithm to remap every Int32?
I'm making a web application that can generate unique unsigned Int32 post IDs for posts. Normally I would just make it auto-increment from `0`.

But I don't want the user to "guess" what's the next ID will be from their own post ID. So I would like the sequence to be random. Let's say the very first post has the ID of `9681034`, then `106871123`, `681021`, `3006477106`...

Basically I want each UInt32 has its own unique map of another UInt32 with no obvious patterns.

```
f(0) = 9681034
f(1) = 106871123
f(2) = 681021
f(3) = 3006477106
...
f(4294967295) = 1627792604

```

Also it would be even better if I could provide a key to a generator function, and then the generator function could give me two functions that for mapping and unmapping the sequence.

```
gen(42) = [f, f']

```

Let's say the example above was generated by this generator, and the `f'()` can unmap the sequence for me

```
f'(f(0)) = 0
f'(f(1)) = 1
f'(f(2)) = 2
f'(f(3)) = 3
...
f'(f(4294967295)) = 4294967295

```

When I provide another key, the sequence changes completely.

---

Sorry I'm very new to CS and algorithm. Is there a known algorithm for this kind of mapping? What is it called? If not, how could I achieve it?

# Answer
> 1 votes
If you don't need a cryptography-proof solution, add a 32 bits number, then scramble the bits. This is easy to invert.

# Answer
> 1 votes
Take the Speck cipher 32-bit block size variant, the key size is not important for you therefore select any of the 64,72, or 96-bit versions. The steps

1. select a uniform random key $k$ and store it.
2. keep a counter $counter = 0$
3. When need a new ID, encrypt the $counter$ with the key

$$ID = Speck32\_k(counter) $$

4. Increment $counter$

Repeat the steps 3 and 4 for when a new ID is required.

---

A little theory to explain why this is a permutation.

Speck like AES is a block cipher and block cipher are synonym for pseudo-random permutation. A block cipher must be reversible for the decryption therefore it is a permutation. And, sometimes we also say that a block cipher is a family of permutations that are selected/determined by the key from all possible permutations from $2^{32}$ to $2^{32}$.

If you keep the same key, you have selected one of the permutations of the family, and asking from 0 to $2^{32}-1$ you get the permuted values.

---
Tags: algorithms, encryption
---


# Question
Title: True or false? Any finite problem is in P
Please explain to me if this is true or false. I had this in an exam, and I really need to know if I got this correct. I believe it is true because finite problems have finite solutions, which can be done in polynomial time.

# Answer
If by finite problem, you mean a problem with a finite domain, then yes. Such problems are not only in P, but can be done in constant time since you can build a mapping between every possible input and its correct output.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Solving Recurrence Relations with induction
We got the following tasks in our Higher Algorithm class, to repeat our proof techniques from class:

> 1. Find asymptotic upper bounds (as sharp as possible) for $T(n)$ in each of the following cases,
> using your favorite method.
> You may assume that $T(n) \< 10$ for all $0 ≤ n ≤ 5$.

Where me and my colleague got stuck specifically are the following functions:

> D) $T(n) = T(n − 1) + 1/n$
> E) $T(n) = T(3n/4) + T(n/4) + n$

In the lecture we learned three methods to proof the recurrences:

1. Direct method (just expand until you see f.e. a sum for which you know the growth rate
2. Master theorem
3. Induction

Specifically for Induction we got told to start expanding our T(n) so we can see patterns and make a good guess for the induction claim.

In D) we noticed that the function generated the **harmonic partial sum**.
And for E) we noticed that the recurrence generated the values of the pascal triangle, so basically the **binomial coefficients**.

Our issue is that we are not really sure, how to use those insights to make a good guess for the induction.

I checked the following answer Median of Medians Time Complexity but was unable to replicate the procedure, as no matter what I plugged in, I would not get my induction guess as a result to finish the proof..

As we need to write an exam at the end of the semster, help in understanding rather than straight up solutions are much appreciated! :-)

# Answer
Since you already noticed that the solution to D) appears to be $T(n) = H\_n$, where $H\_n = \sum\_{i=1}^n \frac{1}{i}$ is the $n$-th harmonic number, why don't you use exactly this guess for the induction proof?

Assuming $T(1)=1$, you have:

* Base case: For $n=1$, $T(1)=1=H\_1$.
* Inductive step, assume that $n\>1$ and that $T(n-1)=H\_{n-1}$. You have $T(n)= T(n-1) + \frac{1}{n} = H\_{n-1} + \frac{1}{n} = \sum\_{i=1}^{n-1} \frac{1}{i} + \frac{1}{n} = \sum\_{i=1}^{n} \frac{1}{i} = H\_n$.

For E) you can observe that each level of the recursion tree contributes $O(n)$ to the final value of the recurrence. Since there are $O(\log n)$ levels, we must have $T(n) = O(n \log n)$. Similarly, each of the first $\lfloor \log\_4 n \rfloor = \Omega(\log n)$ levels of the tree contributes $\Omega(n)$, and hence we also have $T(n) = \Omega(n \log n)$. Combining the upper and lower bound we get $T(n) = \Theta(n \log n)$.

If you insist on using induction you can use the above observation to guess that a solution will satisfy $T(n)=a n \log n + b$ for some constants $a \> 0$, and $b$.

* Base case: for $2 \le n \< 8$, $T(n) \le b \le a n \log n + b$ whenever $b$ is sufficiently large (regardless of the choice of $a$).
* Inductive step, consider $n \ge 8$ and assume that $T(n') \le a n' \log n' + b$ for all $2 \le n' \le \frac{3}{4}n$. $$ \begin{align\*}T(n) &= T(3n/4) + T(n/4) + n \le \frac{3}{4} an \log(3n/4) + b + \frac{1}{4} an \log(n/4) + b \\ &\le a n \log (3n/4) + 2b = an \log(n) - a n \log(4/3) + 2b \\ &\le a n \log (n) - 8a + 2b. \end{align\*} $$ This is at most $a n \log n + b$ as soon as $a \ge b/8$.
> 0 votes

---
Tags: time-complexity, algorithm-analysis, recurrence-relation, induction
---


# Question
Title: Intuition for a projection in tuple relational calculus
Let's have a relation $R = (name, surname, age)$. I want to obtain a new relation with only the $name$ attribute. In relational algebra I would simply do $\Pi\_{\mathrm{name}}(R)$ but in relational calculus the general way of doing that is $$ \newcommand{\Set}\[2\]{% \\{\\, #1 \mid #2 \\, \\}% } \Set{t}{\exists z \\; (R(z) \land t.\mathrm{name} = z.\mathrm{name}}. $$

How does it work? I thought that relation is basically a table and tuple is a row from that table. How does this expression retrieve the original relation with only the name as an attribute?

If I don't specify where the tuple variable $t$ belongs to, we're ranging over all tuples $t$ from the schema right?

1. How can a tuple be just a slice of a table?
2. Take a tuple from $R$ that contains $name$, $surname$ and $age$. It also follows the rule that $t.\mathrm{name} = z.\mathrm{name}$ doesn't it? How come it doesn't show up in the result? I'm so confused.

# Answer
> 0 votes
Note: in the following I assume that a tuple has a fixed set of values, and its order is significant: in other words, if R(a, b) has a tuple *t1* = (2, 4), then *t1*.a = 2 and *t1*.b = 4.

The basic idea behind the tuple relational calculus is that each relation represents a certain predicate, and a relation extension (the tuples) represents a model (i.e. a set of objects) that makes true such predicate. So for instance if R in your example has only three tuples,

```
("John", "Rean", 19)
("Mary", "Rean", 24)
("Mary", "June", 18)

```

this means that it is true that John Rean, Mary Rean, and Mary June satisfy the predicate R, and *only* them.

A query is expressed as a (well-formed) first order formula, and its “result” is obtained by finding in the model the objects that, substituted to the free variables of the formula, make it true.

So the query:

{*t* | P(*t*) }

means: the set of tuples *t* that satisfy the predicate P (remember that we want always, as result, a set of tuples, that is a relation).

So, in your example, the formula:

```
{ ∣ ∃(() ∧ .name = .name}

```

means: “all the tuples *t* for which exists at least a tuple true for R with the same name of *t*”; in other words, all the tuples that have a name among the names of the tuples model of R. So, note that if we have more than one tuple with the same name, in the result we will have only a tuple with such name.

Remember that we are looking for all the possible tuples that can be retrieved by the model that makes the predicate true: this means that we are looking for all the tuples such that:

```
∃(() ∧ .name = .name)

```

is true. And so there are two and only two tuples that satisfy this predicate:

```
("John")
("Mary")

```

so this is the result of our query (note that we assume that a tuple returned has only the "fields" mentioned in its predicate, so *t* has only the “field” name).

# Answer
> -1 votes
**Equation for projection:**

${ t ∣ ∃z ( R(z) ∧ t.name = z.name }$

Now, here we don't specify anywhere that $R(t)$ or $t \ belongs \ to \ relation \ R$. So, $t$ is basically just empty tuple with no specified attributes. The only thing we specified here is that $R(z)$ which makes $z$ a tuple with all other attributes.

And other way around we say that $z.name = t.name$, which makes $t$ a new tuple with only $name$ attribute. And that $name$ only is the output with $t$.

In simple words, $z$ has all attributes, but we gave $t$ only $name$ attribute ($t$ was basically empty before). And that's what we want to project here.

---
Tags: database-theory, relational-calculus, tuple-relational-calculus
---


# Question
Title: Subset sum reducible to barter economy problem?
I was given the following problem called the barter economy problem: Given a set of $n$ people $\\{p\_1, \ldots, p\_n\\}$ and a set of $m$ distinct objects $\\{a\_1, \ldots, a\_m\\}$, where each object $a\_j$ is owned by exactly one person, and each person $p\_i$ has a valuation function $v\_i$ such that $v\_i(a\_j)$ is a non-negative integer representing how much object $a\_j$ is worth to person $p\_i$, determine whether there is a trade between any two people $p\_i$ and $p\_j$ with subsets of objects $A\_i$ and $A\_j$ they currently own, such that: The total valuation for $p\_i$ of objects in $A\_j$, $\sum\_{a \in A\_j} v\_i(a)$, is greater than the total valuation for $p\_i$ of objects in $A\_i$, $\sum\_{a \in A\_i} v\_i(a)$, and The total valuation for $p\_j$ of objects in $A\_i$, $\sum\_{a \in A\_i} v\_j(a)$, is greater than the total valuation for $p\_j$ of objects in $A\_j$, $\sum\_{a \in A\_j} v\_j(a)$. Basically, each of the two people, according to their own valuation function, values the objects they would receive from the trade strictly more than they value the items they're offering up. Note that the objects each people offer can be a subset of the objects they own. I want to prove that this problem is NP-complete.

It is simple to prove this problem is in NP. What's challenging is finding a known np-complete problem to reduce to it. My initial idea was the subset sum problem: for every element $x$ in the set $S$, create a corresponding object $a\_x$ who's value is $v\_i(a\_x) = v\_j(a\_x) = x$, then give $p\_i$ all the items and $p\_j$ none of the items, and somehow assign a $T$ such that the 'yes' answers and 'no' answers to the problems are in correspondance. Is this the path I should continue to try to work down, or might anyone be able to suggest a better, more applicable problem to try to reduce from instead? I feel I'm not on the correct path, because an instance of barter economy involves a collection of people for whom we want to determine if a two-person trade exists, not just two people for whom we want to determine a trade exists, if i'm explaining that distinction clearly

# Answer
> 1 votes
You can reduce from subset-sum as follows: given a set of $n$ positive integers $x\_1, \dots, x\_n$ and a positive integer target $T$, consider an instance with $2$ people $p\_1, p\_n$ and $n+1$ objects $a\_1, \dots, a\_{n+1}$. Objects $a\_1, \dots, a\_n$ are owned by $p\_1$ while $a\_{n+1}$ is owned by $p\_2$. The valuations are as follows: $v\_1(a\_i) = v\_2(a\_i) = x\_i$ for $i=1, \dots, n$, $v\_1(a\_{n+1}) = T + 1$, and $v\_2(a\_{n+1}) = T-1$.

If there is a set of indices $S \subseteq \\{1, \dots, n\\}$ such that $\sum\_{i \in S} x\_i = T$, then we can trade $A\_1 = \\{ a\_i \mid i \in S\\}$ with $A\_2 = \\{ a\_{n+1} \\}$. Indeed: $$ \sum\_{a \in A\_1} v\_2(a) = \sum\_{i \in S} x\_i = T \> T-1 = v\_2(a\_{n+1}) = \sum\_{a \in A\_2} v\_2(a), $$ and $$ \sum\_{a \in A\_2} v\_1(a) = v\_1(a\_{n+1}) = T + 1 \> T = \sum\_{i \in S}x\_i =\sum\_{a \in A\_1} v\_1(a). $$

Conversely, if there is a trade $A\_1$, $A\_2$ such that $\sum\_{a \in A\_1} v\_2(a) \> \sum\_{a \in A\_2} v\_2(a)$ and $\sum\_{a \in A\_2} v\_1(a) \> \sum\_{a \in A\_1} v\_1(a)$, then we cannot have $A\_2 = \emptyset$ and hence $A\_2 = \\{a\_{n+1}\\}$. Let $S = \\{ i \mid a\_i \in A\_1\\}$. The above conditions imply: $$ \sum\_{i \in S} x\_i = \sum\_{a \in A\_1} v\_2(a) \> \sum\_{a \in A\_2} v\_2(a) = v\_2(a\_{n+1}) = T - 1, $$ and $$ T + 1 = v\_1(a\_{n+1}) = \sum\_{a \in A\_2} v\_1(a) \> \sum\_{a \in A\_1} v\_1(a) = \sum\_{i \in S} x\_i. $$ Combining the above two inequalities we get $$ T + 1 \> \sum\_{i \in S} x\_i \> T - 1, $$ and since each $x\_i$ is an integer, we must have $\sum\_{i \in S} x\_i = T$,

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


title: Valid rules in CSG

text:
# Question
Title: Valid rules in CSG
In the book of Hopcroft-Ullman (the 1979 edition) there is a rule $Da\rightarrow aaD$ in the example of the CSL language $a^{2^i}$.

Valid rules in CSG have the form $\alpha A \beta\rightarrow \alpha\psi\beta$. I think the mentioned rule is not valid, since there is no way to get rid of the terminal $a$ at the right side.

Or is there some magic that escapes me?

# Answer
What Hopcroft and Ullman call a context-sensitive grammar is nowadays called a noncontracting grammar; see page 223. The two types of grammar are equivalent in power.
> 2 votes

---
Tags: formal-languages, context-sensitive
---


title: Showing SAT is auto-reducible

text:
# Question
Title: Showing SAT is auto-reducible
I am trying to wrap my head around the concepts of *auto-reducibility* and *having access to an Oracle*. The way I understand is that a language is auto-reducible iff there is a Turing Machine $M^{L}(x)=1$ for every *x $\in$ L* with the special requirement that on input *x* the Turing Machine is not allowed to query the Oracle for x.

Does that mean it can query anything else?

For example in the case of SAT, we can then query the Oracle for *x $\land$ True*, which would be a different input, however it would still include the entirety of *x*. Would that be allowed?

# Answer
Autoreducibility was introduced in Buhrman, Fortnow and Torenvliet, Using autoreducibility to separate complexity classes. Here is the (informal) definition (page 520):

> A set $L$ is autoreducible if there is a polynomial-time oracle Turing machine $M$ that accepts $L$ using $L$ as an oracle with the caveat that $M(x)$ may not query whether $x \in L$.
> 2 votes

---
Tags: turing-machines, oracle-machines, sat-solvers
---


# Question
Title: Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth
As stated in the question title, if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then how can we show $g(n)$ also has polynomial growth?

$g(n)=\Theta(f(n))$ gives us $0\leq c\_1f(n)\leq g(n)\leq c\_2f(n)$ for some positive constants $c\_1, c\_2$ for some $n\>n\_0\>0$. But how can I conclude $g(n)$ also satisfies the polynomial growth condition?

A function $f(n)$ defined on all sufficiently large positive reals satisfies the *polynomial-growth condition* if there exists a constant $\hat{n} \> 0$ such that the following holds: for every constant $\phi \geq 1$, there exits a constant $d\>1$ (depending on $\phi$) such that $f(n)/d \leq f(\psi n) \leq d f(n)$ for all $1 \leq \psi \leq \phi$ and $n \geq \hat{n}$.

# Answer
Let us consider only sufficiently large values of $n$. As you have pointed out there are two constants $c\_1, c\_2$ with $0\< c\_1 \le c\_2$ such that: $$ c\_1 f(n) \le g(n) \le c\_2f(n). $$

Also, since $f$ has polynomial growth, for every $\phi \ge 1$ there exists some $d\_\phi \> 1$ such that: $$ \frac{1}{d\_\phi} f(n) \le f(\psi n) \le d\_\phi f(n) \quad \forall 1 \le\psi \le \phi. $$

Then the following holds for all $1 \le\psi \le \phi$: $$ \frac{c\_1}{c\_2 d\_\phi} g(n) \le \frac{c\_1 }{d\_\phi} f(n) \le c\_1 f(\psi n) \le g(\psi n) \le c\_2 f(\psi n) \le c\_2 d\_\phi f(n) \le \frac{c\_2 d\_\phi}{c\_1} g(n). $$ Which means that $g$ also satisfies the polynomial growth condition. In particular, for a given $\phi$, we can choose $d'\_\phi = \frac{c\_2 d\_\phi}{c\_1}$ to obtain: $$ \frac{1}{d'\_\phi} g(n) \le g(\psi n) \le d'\_\phi g(n) \quad \forall 1 \le\psi \le \phi, $$ where $d'\_\phi \> 1$ holds since $c\_2 \ge c\_1$ and $d\_\phi \> 1$.
> 1 votes

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


# Question
Title: Are there any open source SAT solvers with UNSAT core extraction algorithm built in?
Just like the title says. I need to use a SAT solver on a series of CNF formulas but not only do I need an answer of the type satisfiable/unsatisfiable but also some subset of clauses whose conjunction is still unsatisfiable (the unsatisfiability core).

I have read somewhere that it is possible to hack the code of some SAT solver (like MiniSAT) to produce UNSAT core, but I don't feel competent enough to actually do it. I was hoping that somebody else have already done it and have uploaded the code somewhere, but either that is not the case or I suck at Googling.

# Answer
MUSer2 is probably *the* tool for extracting minimal unsatisfiable cores (MUS) currently. It treats the SAT solver as a black box, so you can plug in any solver you want.

If you want a solver with MUS extraction capability, the newest version of PicoSAT comes with a utility tool PicoMUS that does the job.
> 4 votes

# Answer
For the Java world: Sat4j also has a MUS extraction tool, buried in the `org.sat4j.tools` package.

```
AllMUSes musFinder = new AllMUSes(SolverFactory.instance());
ISolver solver = musFinder.getSolverInstance();

// add clauses to solver . . .

List<IVecInt> muses = musFinder.computeAllMUSes();

```
> 0 votes

# Answer
Minisat and Z3 have the same hack to extract unsat cores. I found the Z3 example easy to understand. The link is here:

https://github.com/Z3Prover/z3/blob/master/examples/c%2B%2B/example.cpp

There are about 4 examples on extracting unsat cores. You can use the code as is by modifying the assertions, if you like C++.
> 0 votes

---
Tags: reference-request, satisfiability, sat-solvers
---


# Question
Title: Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time
In a graph with `N` nodes, where each node represents a house and is labeled from `0` to `N-1`, an adjacency matrix `graph[i][j]` indicates the distance from node `i` to node `j`.

Consider a list of tuples `[[init_1, target_1], ..., [init_k, target_k]]`, representing delivery requests. Each tuple, like `[[1, 2], [2, 3], [5, 3]]`, requires a delivery person to transport food from `init_i` to `target_i` (e.g., from houses 1, 2, 5 to houses 2, 3). **Each delivery person can carry an unlimited amount of items/orders at same time.**

There is also a list of delivery personnel `[v1, v2, ..., vn]`, where each `vi` indicates the current location (node) of the `i`-th delivery person. Assuming all personnel move at the same speed and ignore the stopping time at each node, how can one assign a route to each (a list of houses for pickup and delivery) to minimize the maximum time taken by any delivery person?

# Answer
> 1 votes
The problem is unlikely to admit any efficient solution since it is NP-Hard even when there is only one delivery person and, for all edges $(u,v)$ in the graph, the distance between $u$ and $v$ is $1$.

To see this let $G=(V, E)$ be the graph and let $V = \\{v\_1, \dots, v\_n\\}$. Construct a new graph $H = (V', E')$ where $V' = V \cup \\{ s, u\_1, \dots, u\_n\\}$ (where $s$ and $u\_1, \dots, u\_n$ are new nodes) and $E' = E \cup \\{ (s,v\_i) \mid i =1,\dots, n\\} \cup \\{ (u\_i, v\_i) \mid i= 1,\dots, n \\}$ (if you are interested in directed graphs then add also the revers edges $(v\_i, u\_i)$).

Let $s$ be the starting location of the only delivery person. There are $n$ deliveries, the $i$-th delivery requires food to be transported food $u\_i$ to $v\_i$.

There is a route on $H$ that delivers all the food and has length at most $3n$ if and only if $G$ is hamiltonian.

---
Tags: algorithms, graphs, optimization, graph-traversal
---


# Question
Title: Turing machine comparing two binary numbers in linear time
I was wondering how you would go about making a two-tape Turing machine in linear time that starts with input # on Tape 1, where and are binary integers that might have leading 0's. It would accept the input if and have the same value such as 001101 has the same value as 1101. Would it be a good idea to replace the 1s and 0s with something like n and m to read the inputs and then if the turing machine gets to the # symbol it goes to the next binary string. Then if the n/m are the same it would accept the input and if they are different it would reject it? How would this be implemented?

# Answer
> 1 votes
Here is a sketch: Put the machine in a state where the first tape contains $x$ with no leading zeros, and the second tape contains $y$ with no leading zeros, then check that the contents of two tapes are equal.

To reach such state, assume that both $x$ an $y$ contain at least one $1$ (this can be easily checked). Then, scan the first (input) tape deleting all leading zeros. Continue scanning the tape without changing it until you find $\\#$. Delete $\\#$, then "move" $y$ to the second tape ignoring the leading zeros (write blanks on the first tape and the significant digits of $y$ to the second tape). Reset both heads to the first non-zero character of the respective tapes.

Interesting there exists no subquadratic Turing machine that solves your problem using only one tape.

Suppose such a Turing machine existed $T$, then you could use it to build the following Turing machine that decides the language $L$ containing all strings of the form $x' 2^n y'$ where $x',y' \in \\{0,1\\}^\ell$, $x'=y'$, and $\ell \ge 2$.

To do so you can:

* Check that the string is of the form $\\{0,1\\}^\*2^\* \\{0,1\\}^\*$ (if not, reject). This can be done in linear time.
* Check that the string is of the form $\\{0,1\\}^\ell 2^\ell \\{0,1\\}^\ell$ with $\ell \ge 2$. This can be done in time $O(n \log n)$, where $n$ is the length of the input.
* Prepend a $1$ to $x$
* Replace all $2$s except the first and the last one with $0$.
* Replace the first $2$ with $\\#$ and the last $2$ with $1$.
* Run $T$ on the current tape contents (which are now of the form $1x'\\#00\dots 01y')$.

The overall time spent is $O(n \log n)$, where $n$ is the length of the input. However $L$ cannot be decided by any Turing machine with running time $o(n^2)$. See pages 566-569 of One-Tape, Off-Line Turing Machine Computations.

---
Tags: turing-machines
---


# Question
Title: Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?
$f$ and $g$ being known functions.

We suppose that the problem is solvable.

To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because if it was a P problem, we would have to answer it in polynomial time, and so test every $u$ function in a single polynomial time, which is impossible?

So, is it possible to say, because the instance is infinitely numerous, it is not in P?

If exist at least one $u$ function that solve the problem, and with which you can check that the answer problem is « yes » in polynomial time, is the problem in NP?

# Answer
I'm going to assume that $f:A\to B$ and $g:A\to B$ for some (known) sets $A$ and $B$ and that, given a set $C\ni0$ we are to find a function $u:C\to A$ such that $f(u(0))=g(u(0))$. Of course, this is just the same as asking for an element $a\in A$ such that $f(a)=g(a)$ (consider, for instance, the constant function $u(x)=a$). This, in turn, is the same as asking if $f(A)\cap g(A)$ is empty or not.

But this isn't even decidable. Consider the function $f(n)$ which is 1 if n is the binary representation of a Lean proof of the Riemann hypothesis and 0 otherwise, and the function $g(n)=1.$ Now replace $f$ with the undecidable function of your choice.

So definitely not in NP.
> 1 votes

---
Tags: np, decision-problem, p-vs-np
---


# Question
Title: How to find prefixes and suffixes for infinite languages? (Automata)
```
L= {abc}
prefix = {epsilon,a,ab,abc}
suffix = {epsilon,c,bc,abc}

```

It's easy to find suffixes and prefixes for finite Regular languages. But what will be the approach for infinite Regular languages?

For example:-

```
Alphabet = {a,b}

L1 = Every string starts with a.
L2 = Every string ends with a.
L3 = {waw|w belongs to {a,b}^*}/ every string contains at least one a.

```

What will be the Suffixes and Prefixes for the given Regular languages and how to find them?

# Answer
For regular languages this is relatively straighforward. Let $L\subseteq\Sigma^\*$ be regular. Let $A = (Q, \Sigma, q\_0, \delta, F)$ be an NFA that recognises $L$. Construct another NFA $A' = (Q, \Sigma, q\_0, \delta, F')$ from $A$ by changing just the final state set as follows: set $F'$ to the set of all states in $Q$ from which a state in $F$ can be reached by any number of transtions in $\delta$. This makes $A'$ accept the language of prefixes of $L$.

For the suffix construction, realise that suffixes are reversed prefixes of reverse words in $L$. Wikipedia explains how to reverse a regular language.
> 0 votes

# Answer
Let's see what others say but I think you could adapt the algorithm that enumerates the sentences of a language and restrict it to enumerate prefixes or suffixes only. I assume you are familiar with formal languages, the algorithm I sketched takes advantage of standard notation and well-known techniques.

An algorithm for enumerating the sentences of a possibly infinite context-free language $\mathcal{L\_0}$ is the following (notice I stated the language has to be context-free or the algorithm will require exponential time and space to run; also the very first step will be inapplicable).

Let $\mathcal{G}$ be a context-free grammar such that $\mathcal{G}=(T,N,\Sigma,S,P)$ and $\mathcal{L}(\mathcal{G})=\mathcal{L\_0}$. Let $K$ be the maximum length of the sequences you want to enumerate.

1. Convert $\mathcal{G}$ to CNF (Chomsky Normal Form) obtaining $\mathcal{G'}=(T,N',\Sigma,S',P')$,
2. declare $q$ a queue of symbols (terminal and non-terminal),
3. insert $S'$ in $q$,
4. while there are elements in $q$:
5. take the head sequence $s$, remove it and scan it:
6. if $s$ does not contain non-terminal symbols or is $s=\epsilon$ or $\vert s\vert=K$, give it as output.
7. conversely, if it does contain some non-terminal replace the leftmost non-terminal symbol $n$ with the RHSs of the all productions $p\in P . n \rightarrow \alpha $, generating (possibly many) new sequence(s) $\\{s\_0,...,s\_k\\}$,
8. enqueue sequences $s\_0,...,s\_k$.
9. goto 4.

This algorithm will behave differently depending on the grammar you provide.

1. If you run it on a grammar whose language is finite and $K$ is large enough, it will generate all sentences. In case $K$ is smaller than the longest sentence of the language it will provide some mangled sentences (that is, containing non-terminal symbols).
2. In case the language is infinite it will not get stuck enumerating one sentence, it will operate a rewrite step on some sequence and then switch to the next one, enforcing progress.
3. If the grammar is ambiguous, sentences having two (or more) distinct derivation trees will be given as output two (or more) times.

I think you could employ this algorithm for generating $prefixes$, and the version replacing the rightmost non-terminal in step 7. to generate $suffixes$.

The first step where I convert to CNF is required to avoid an explosion of the queue during the rewriting phase. CNF is characterized by the property of having RHSs of at most 2 non-terminal symbols. Considering you replace a non-terminal with some RHS, the length of the string taking the place of the removed symbol is at most two. Hence, each time you rewrite you will add only one symbol at most to each sequence. This approach makes the algorithm practical.
> 0 votes

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


# Question
Title: "Cannot return a value from a method with void result type" but it's not void?
In Java, I'm getting the error for all my return statements that I can't return a value with a void result type, but I don't declare the return type as void anywhere, and I'm really not sure what the issue is. Here's my code:

public class Card {

```
private int suit;
private int rank;

public Card(int suit, int rank) {
    this.suit = suit;
    this.rank = rank;

public String toString() {
    String[] suits = {"clubs", "diamonds", "spades", "hearts"};
    String[] ranks = {"non-existing-rank", "A","2","3","4","5","6","7","8","9","10","J","Q","K"};
    return ranks[rank] + " of " + suits[suit];
}

public int getSuit() {
    return suit;
}

public int getRank() {
    return rank;
}

public boolean equals(Card other) {
    // Two cards are equal only if they have the same suit and the same rank.
    return suit == other.suit && rank == other.rank;
}

public int compareTo(Card other) {
    // First compare the suit, and only if the suit is the same compare the rank.
    if (suit < other.suit) {
        return -1;
    } else if (suit > other.suit) {
        return 1;
    } else {
        if (rank < other.rank) {
            return -1;
        } else if (rank > other.rank) {
            return 1;
        } else {
            return 0;
        }
    }
}

```

}

# Answer
You didn't close the paranthesis in the Card() constructor:

```
public Card(int suit, int rank) {
    this.suit = suit;
    this.rank = rank;
} // missed

```

Other than that everything is fine.
> 0 votes

---
Tags: java
---


title: Parallel Algorithm Analysis: Loops

text:
# Question
Title: Parallel Algorithm Analysis: Loops
I have come across what seems to be a collapsed loop.

```
parallel-for i, j = 1...n

```

What would be the work and span/depth/critical path length be of loops like this? Would it be the same as that of the following:

```
parallel-for i = 1...n
  parallel-for j = 1...n

```

**EDIT**:

**Work** = the asymptotic running time of the algorithm on a single core (total computational steps)

**Span**/**depth**/**critical path length** = the asymptotic running time of the algorithm on an infinite number of cores (the point beyond which more parallel processors won't give any performance gains).

# Answer
The **work** $W(n)$ is the total number of nodes in your computation graph and the **span** $D(n)$ is the number of nodes on the longest path of that graph. $T\_P(n)$ is the **runtime** of the algorithm using $P$ processors; $T\_1(n) = W(n)$ and $T\_\inf(n) = D(n)$.

Suppose your code has the following shape

```
parfor i in range(n):
    parfor j in range(n):
        f()

```

where $f() \in O(1)$ is some function (with side-effects). The keyword "parfor" means that every loop iteration is independent. There are $n^2$ independent iterations so in theory $W(n)\in O(n^2)$ and $T\_\inf(n) = D(n)\in O(1)$.

However, the work of starting each $f()$ thread and waiting for its result must be accounted for. That is, we must implement the "parfor" keyword. Here is one way:

```
parfor_impl(f, lo, hi):
    if hi - lo <= 1:
        f()
    else:
        mid = (lo + hi) // 2
        spawn parfor_impl(f, lo, mid)
        spawn parfor_impl(f, mid, hi)
        wait

```

where the keywords "spawn" and "wait" launches threads and waits for previously launched threads' completion respectively. This is a classical recursive scheme with $W\_{parfor} \in O(n)$ and $D\_{parfor} \in O(\log n)$. To get the total runtime (and span) we just add the runtime of the two nested loops $O(2\log n) = O(\log n)$. We do not multiply the runtime since the loops run in parallel.

I can highly recommend the "Intro to the Work-Span Model" chapter of Udacity's High Performance Computing course which delves deep into this topic.
> 1 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, runtime-analysis, parallel-computing
---


title: 3 Processor Scheduling

text:
# Question
Title: 3 Processor Scheduling
A set of n independent tasks, each having integer execution times, are to be executed using three identical processors. A task can be executed in any of the three processors. Develop a sequential algorithm to find minimal total execution time for scheduling all the tasks. For this develop an initial recursive definition, indicate the properties of the unfolded recursion tree and develop a final algorithm. Show the working of your algorithm on a task set having the following execution times = {5, 7, 6, 9, 11, 17} using processors P1, P2 and P3. Analyze the time and space complexity of your initial and final algorithms.

I tried to use a DP based approach but still the time complexity is O(3^N). Is there a polynomial time algorithm for this problem?

Note: 2 processor scheduling is NP-Complete problem.

# Answer
> 0 votes
You should be able to do this in exponential time, but much faster than n^3 operations.

Get a quick upper bound by sorting the tasks in descending length, then scheduling each task in turn to the processor that has the least work. That’s 17, 11+6, 9+7+5. So you can do it in 22 units, and you only look for solutions where each processor uses at most 21 units; if you don’t find any solution than you have the next best already. Since the sum of tasks is 55, you can’t do it in less than 19 units.

For processor 1, it must do at most 21 units, and at least 13 because 13 \>= 55-21-21. So you let it do the longest task (17) and any subset of the remaining tasks that takes at most 4 units, for a total of x units of tasks. The other two processors do tasks of total length y and z. You have the sum y+z = 55-x, and y, z \<= 21. So y ranges from 55-x-21 to 21. You give the second processor the second longest task, and any subset of the remaining tasks so that 55-x-21 \<= y \<= 21.

And when you find a solution you strengthen the requirements. Say you find a solution with maximum length 21, then you only look for solutions where the longest task has length 20.

You save most time because for the first processor you only select subsets that make the sum close to the total task length divided by 3.

---
Tags: algorithms, np-complete, dynamic-programming, scheduling, p-vs-np
---


# Question
Title: What is the reason or advantage of having special purpose status flags for the result of comparisons?
The C semantics treat the result of a comparison or any `true`/`false` operation as just an `int` with value `1` for `true` or `0` for `false`. This is simple and intuitive.

However, mainstream processors do not work this way. Comparison instructions do not output a byte or integer or any value with `1` or `0` as the result of the comparisons. Rather, they store the comparison results in a special purpose flags register. Then, to use the result of the comparison as an `int`, more instructions which may or may not even result in a branch, to actually extract the bit.

What is the reason for this? What is the advantage of using a special purpose flags register for comparisons or similar operations instead of simply return a ready-to-use integer result, the same way arithmetic operators do?

# Answer
> 1 votes
You have two choices. Either you have separate compare instructions for ==, !=, \<, \<= etc. which all create 0 or 1, or you have one compare instruction creating flags and various branch instructions. Just s matter of choice.

However, it seems that storing the result of a compare instruction in a special place where it can be accessed directly by the branch unit, and especially can be accessed to resolve predicted branches, seems beneficial. And the result of a comparison in a general purpose register is usually *not* “ready to use” for its main purpose, which is making decisions.

Also consider that operations like add, multiply, subtract, shifts or sign extend may set these flags, so “if (x+y \> 0)”, “if (x * y \< 0)” etc. can be done by performing the operation and using a conditional branch.

---
Tags: cpu, c, assembly, instruction-set
---


# Question
Title: Work and depth of DAG - problem in understanding exam question
I have some problems understanding the following 2 question from an exam last year, which I am preparing for this week in Parallel Programming.

Determine the Work -\> $W(n) = 7$ (#vertices)

Determine the Depth -\> $D(n) = 4$ (longest path)

Determine average parallelism -\> $\frac{W(n)}{D(n)} = 7/4$

Ok, now the 2 questions, which I have problems with:

*What is the minimum number of processors that are needed to achieve depth?*

For this question I only have a vague idea: $infinity$? Because if we use Brents theorem:

$$\frac{W(n)}{p} \<=T\_p(n) \<= \frac{W(n)}{p} + D(n)$$

maybe we can achive depth? I am not sure.

*What is the number of processors larger or equal to 2 that achieves the maximum efficiency for this problem?*

That should be relatively easy, but I am not sure, how I should calculate the Speedup? I know several formulas, but I do not know how to calculate the fraction, which must be run sequentially ($S=\frac{p}{1+(p-1)f)}$) or the execution times.

Can someone point me in the right direction?

# Answer
$D = 5$ (and is not a funtion of $n$ here) and goes $1 - 2 - 4 - 5 - 6$.

> What is the minimum number of processors that are needed to achieve depth?

It clearly cannot be achieved with one processor, but here is a schedule that achieves it using two processors:

| Time | $P\_1$ | $P\_2$ |
| --- | --- | --- |
| 1 | 1 | 3 |
| 2 | 2 |  |
| 3 | 4 |  |
| 4 | 5 | 7 |
| 5 | 6 |  |

Since $T\_2 = D$, speedup is simply $S\_2 = T\_1/T\_2 = W/D = 7/5$.
> 1 votes

---
Tags: parallel-computing
---


title: Sorting rational numbers in linear time

text:
# Question
Title: Sorting rational numbers in linear time
I am currently studying algorithms and computational complexity at University.

I have recently got through three questions I found in an old exam:

1. *Is it possible to sort in asymptotically linear time an array of rational numbers between $\[1, 1.5\]$ with limited numerator?*
2. *Is it possible to sort in asymptotically linear time an array of rational numbers between $\[0, 0.5\]$ with limited numerator?*
3. *Is it possible to sort in asymptotically linear time an array of rational numbers between $\[0, 100\]$ with limited denominator?*

First of all I tried to understand what the author meant with "*limited*": I assumed it to be a synonym of "*fixed*" (i.e. a generic value $k$) and what comes below is based on this assumption.

As far as I know we can use three algorithms to achieve $O(n)$: *counting sort*, *radix sort* and *bucket sort*. In these questions no uniform distributions are guaranteed, so I basically ignored the last one.

For (1) I thought this: if all the numerators are the same ($k$), then we only have to sort all the elements by their denominator, in reverse order. Since the range is $\[1, 1.5\]$, the denominators must be an integer between $\left\[\left\lceil\frac{2}{3}k\right\rceil, k\right\]$. That is a limited interval of integers, so we can use counting sort and get $O(n)$. The answer is indeed "*true*", as stated in the solution.

For (2) I tried a similar approach: in this case we have a lower bound of $0$, so to reach it with a $k$ numerator we would need an infinite denominator. Since counting sort requires a finite range, we conclude that we can't get $O(n)$. The solution says "*false*", as I did.

For (3) we have a little difference but my intuition was to apply the same reasoning: if we set $k$ as denominator, then we must have a numerator in $\[0, 100k\]$ to fit within the original range. A fixed interval: we can apply counting sort! But the answer in the solution this time is "*false*", we do not sort in linear time.

The only other difference compared to (1) and (2) is the upper bound, which is higher. So, if we had a very large $k$, the range would be even larger and in $O(n + k)$ it would dominate over $n$. Anyway, I found another exam paper in which the range is completely removed, and the answer keeps to be marked as false.

I repeat: I based all of the above on the original assumption. I ask, therefore: was it wrong? Does "*limited*" have another meaning in this context? Or, more in general: why can't (3) be sorted in linear time, while (1) can?

Thanks in advance to everyone.

# Answer
You can sort an array in linear time if the set of possible array elements is finite. Because in that case you just pick the array elements that have the smallest possible value, then the array elements that have the second smallest possible value, and so on. Each of these operations is linear in time, and there is a finite number of them, so the total time is linear.

The rational numbers between 0 and 0.5 with limited numerator are infinite. They contain for example the rational numbers 1/2, 1/3, 1/4, 1/5 ..., in general 1/n for all n \>= 2. Plus many other rational numbers.

The rational numbers between 0 and 100 with limited denominator are finite. Let's say the limit for the denominator is K. Then we have the numbers i/1 for 1 \<= i \<= 100, exactly 100 of them. And the numbers i/2 for 1 \<= i \<= 200, exactly 200 of them, and eventually the numbers i/K for 1 \<= i \<= 100K, exactly 100K of those. There are roughly 100 * K^2 / 2 rational numbers in this set, so finite, so sorting can be done in linear time.
> 1 votes

---
Tags: algorithms, asymptotics, sorting, arrays, linear-complexity
---


# Question
Title: Reducing euclidean TSP of smaller size to euclidean TSP of bigger size
Assume I have a euclidean TSP solver that is **optimal**, but it can only solve inputs with exactly $N$ vertices. Let's call it the **N-solver**.

Now, I have an input with $K$ vertices in the 2D plane, where $K \< N$. Can I convert this $K$ sized input to an $N$ sized input where I can feed it into my N-solver and obtain an optimal answer, and then try to convert it back to an optimal solution for the original $K$ vertices?

**I assume that you are not allowed to have multiple vertices at the same coordinate.**

Has this problem been discussed, investigated, or solved anywhere? Even some approach that guarantees some gap compared to the optimal answer would be good. Any thoughts?

# Answer
> 0 votes
If you need a mathematical guarantee, you should run $k-1$ times the $N$-solver algorithm. In other words, repeat the following approach for each vertex $v\_i\ \ i=2,...,k$ and take the best solution.

Introduce $N-K$ new vertices $V\_j\ \ j=k+1,...,N$ on the line segment between two vertices $v\_1$ and $v\_i$; e.g. With distance $d\_{1j}=(j-k)\frac{d\_{1i}}{N-K+1}$ and $d\_{ij}=d\_{1i}-d\_{1j}$. Then, if $x\_{1i}=1$ in the optimal solution on $k$ vertices then on N vertices we have $x\_{1,k+1}=x\_{k+1,K+2}=...=x\_{N-1,N}=x\_{Ni}=1$ with a same optimal value .

But, if you want to execute the idea of @greybeard, find $d\_{a,b}=max\\{d\_{ij}\\}$ and add $N-k-1$ far away new vertices $V\_j\ \ j=k+1,...,N-1$ on the left side of the line $v\_a-v\_b$; e.g. With distance $d\_{aj}=(d\_{a,b})^{10}+j$ and $d\_{bj}=d\_{aj}+d\_{ab}$. Moreover, add a new vertex $v\_N$ close to the vertex $v\_a$ as much as it is possible.

# Answer
> 0 votes
Here's an idea that doesn't work: Assume K = N-1. Take any node X and create another node X' at a distance epsilon from X, and calculate all the distances to X', then solve the N problem. If that solution directly connects X and X', then removing X' gives an optimal solution for the original problem, otherwise move X' closer to X and try again.

You might get it to work if you pick an X at the outside of the graph so you can guarantee nobody will want to go to X or a very nearby place twice.

---
Tags: algorithms, complexity-theory, reductions, approximation, traveling-salesman
---


# Question
Title: fastest algorithm to count leaf nodes (i.e. terminal nodes)
With the following recursive code to count leaf nodes of a binary tree, is there any way to make it faster or parallel-computing optimized in time?

Python code - (mag(P) = number of leaf nodes of tree P depth H, left(P) = produces left subtree and right(P)= produces right subtree, not given here, reduce the tree P to subtrees until terminal nodes are reached):

```
temp = 0
def mag(P):
    global temp
    if len(P) == 0:  #counts the one terminal node
        return temp+1
    elif len(P) == 1:   #counts the two terminal nodes
        return temp+2
    elif len(P) >= 2:
        return mag(left(P)) + mag(right(P))

```

# Answer
Store the tree in an array $A$ so that $A\_i$ contains the index of the parent's node. For example:

```
A = [-1 0 1 1]

```

would be a four-node-tree where the root node has one child and that child in turn has two children. The root node has no parent, denoted by -1.

Now go through all array elements in parallel. For every element, increase a counter if its value is not marked and mark the value. The counter now contains the number of non-leaf nodes and its trivial to get the number of leaf nodes from that. Python pseudo code:

```
A = array of length N
M = [False] * N
cnt = 0
parfor e in A:
    if e >= 0 and not M[e]:
        M[e] = True
        cnt += 1
n_leaves = N - cnt

```

The `parfor` keyword stands for "parallel for" and runs its loop body in $O(\log n)$ time (well-known result). This is probably as fast as it gets.
> 0 votes

---
Tags: trees, parallel-computing, counting, backtracking, subtree
---


# Question
Title: Is L={0^n 1^n ∣n≥0} context free language?
I looked through many sources which give this as an example for cfl. It also makes sense according to this:

But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can decompose s into uvxyz like: u=0, v=0, x=0,y=01, z=111

If we pump it, it clearly fails. So, is 0^n1^n context free or not?

# Answer
> 2 votes
You have just shown that the given language does not meet the condition of the pumping lemma for $n=5$ and **one particular decomposition**.

To conclude that $L$ is not context free you need to show that the language does not meet the condition of the pumping lemma for some word of **sufficiently large length $n$** and **all** decompositions of such word (within the constraints of the pumping lemma).

It turns out that the words of $L = \\{0^n 1^n \mid n \ge 0\\}$ admit a valid decomposition as soon as $n \ge 1$. Here is a decomposition of $0^5 1^5$ into $uvxyz$ that can be pumped: $u=0^4$, $v=0$, $x=\varepsilon$, $y=1$, $z=1^4$.

This is not surprising, since $L$ is indeed context-free as the argument in your question shows.

---
Tags: formal-languages, automata, context-free, pumping-lemma
---


# Question
Title: function is computable iff its graph is recursively enumerable?
How do I show that a (possibly partial) function is computable iff its graph is recursively enumerable?

# Answer
Let's say f is partially computable. Then you can bound the number of computational steps. for example if e is the index of the machine which computes f you can define B(S) to be the following set:

{\<i,f(i)\> | the machine with index e halts and give f(i) as output with i as input in less than S computational steps.}

So graph(f) = U B(S) for all S \>= 0.

Since B(S) is recursively enumerable for all S, So is graph(f).

Now, let's say graph(f) is recursively enumerable and you want to compute f(j). You enumerate graph(f)'s members ((According to assumption, there is a machine which can do that)) until you get a member which is in the form \<j, k\>. Then k is f(j).
> 1 votes

---
Tags: computability, semi-decidability, recursively-enumerable
---


title: Worst Case Scenario Quick Sort

text:
# Question
Title: Worst Case Scenario Quick Sort
I'm aware that the worst case scenario recurrence relation corresponding equation is: $$ T(n) = T(n-1) + T(0) + \Theta(n) $$

However, I really don't get how the last term $ \Theta(n)$ was determined.

1. I dont understand why $ \Theta(n)$ and not $ \mathcal{O}(N) $
2. I don't get why it is $ \Theta(N) $ and not $ \Theta(N-1) $ because in quick sort you compare the pivot with (n-1) elements, not "n" elements.

Specially the number 2 it's hard for me to understand.

# Answer
1. For sure you have to do $n-1$ comparisons with the pivot, you can't do less, so it is $\Omega(n-1)=\Omega(n)$. At the same time you do at most $n-1$ comparisons and swaps. Thus it is $O(n-1)=O(n)$. Thus it is $\Theta(n)$.
2. As stated in 1., summing constants does not affect asymptothic notation, so $\Theta(n)=\Theta(n-1)$.
> 0 votes

---
Tags: algorithms, quicksort
---


# Question
Title: Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$
From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the notion of non-determinism in the context of TM's yet.

I suppose this TM would work *something* like this: Given an input $x$, non-deterministically try different divisions of $x$. For instance, if $x$ was of length 10, $x$ could be divided as $w\_1w\_2$ or $w\_1w\_2w\_3w\_4w\_5$. Then, for each "guess" check if each of the substrings is the same.

I understand this is in and of itself an "informal description," but I would like to include some more "implementation-level" details. Some things that are confusing me... How can we be sure that the possible subdivisions of $x$ where the number of subdivisions does not divide the length of $x$ will not accept? For instance, in my example, how can we enure that the "guess" of $w\_1w\_2w\_3$ will not accept? Furthermore, how can we go about the actual process of ensuring each $w\_i$ are equal? I am familiar with the construction of the TM for $L = \\{ww \mid w \in \\{a, b\\}^\*\\}$ where you first mark the midpoint with a $\\#$, but I am not sure how you would mark the subdivision points when there can be an arbitrary number of substrings.

Anyway, hints are appreciated.

# Answer
When "marking a letter" on the Turing tape, we replace a symbol $a$ by another symbol, like $X$, $\bar a$, or $\underline a$. Since various markings might be needed it is practically more convenient to consider a tape with various parallel components. We may write on each of these components to record phases of the computation.

The first $w$ can be guessed by marking its last position on the tape. Then is is straightforward to check whether the next segment also equals $w$. Just match the letters of $w$ one by one with the letters of the next segment. The machine marks the letters that have been checked. When everything is OK, unmark initial $w$ and repeat for the next segment. Etcetera, until the final segment is empty.

We accept if the segments match. In case the length of the string is not a multiple of $|w|$ the machine will be unable to match the final segment with initial $w$.

Final point. You state "non-deterministically try different divisions". Technically a deterministic machine would try various divisions. A non-deterministic machine tries only one. If there is a way to guess right, the string will be accepted.
> 0 votes

---
Tags: formal-languages, turing-machines, automata, nondeterminism
---