title: Lambda Expression Reduction

text:
# Question
Title: Lambda Expression Reduction
I am unable to solve the following lambda expression using both normal order (Call-by-name) and applicative order (Call-by-value) reduction. I keep getting different answers for both. This is the lambda expression that has to be reduced using both techniques:

$(\lambda f\ x\ldotp f\ (f\ x))\ (\lambda f\ x\ldotp f\ (f\ x))\ f\ x$

# Answer
> I keep getting different answers for both.

You should get the same result for both orders. Please show your work so that the community can help you find your mistake.

My guess is you have mistakenly substituted $f$ instead of $x$ towards the end, when $f$ is in fact free.

The correct reduction procedure is shown below.

---

$(\lambda f\ x\ldotp f\ (f\ x))\ (\lambda f\ x\ldotp f\ (f\ x))\ f\ x$

There is no difference between normal order and applicative order at the first step.

$(\lambda f\ x\ldotp f\ (f\ x))\ ((\lambda f\ x\ldotp f\ (f\ x))\ f)\ x$

---

At this step there is a difference, because the value being applied to, $((\lambda f\ x\ldotp f\ (f\ x))\ f)$ is not in beta normal form. Let's ignore it and use normal order first.

### Normal Order

$((\lambda f\ x\ldotp f\ (f\ x))\ f)\ (((\lambda f\ x\ldotp f\ (f\ x))\ f)\ x)$

$(\lambda x\ldotp\ f\ (f\ x))\ (((\lambda f\ x\ldotp f\ (f\ x))\ f)\ x)$

$f\ (f\ (((\lambda f\ x\ldotp f\ (f\ x))\ f)\ x))$

$f\ (f\ (f\ (f\ x)))$

---

Let's go back to the first step.

$(\lambda f\ x\ldotp f\ (f\ x))\ ((\lambda f\ x\ldotp f\ (f\ x))\ f)\ x$

---

This time let's use applicative order

### Applicative Order

$(\lambda f\ x\ldotp f\ (f\ x))\ (\lambda x\ldotp f\ (f\ x))\ x$

$(\lambda x\ldotp f\ (f\ x))\ ((\lambda x\ldotp f\ (f\ x))\ x)$

$(\lambda x\ldotp f\ (f\ x))\ (f\ (f\ x))$

$f\ (f\ (f\ (f\ x)))$

---

With normal order we reduced the expression to:

$f\ (f\ (f\ (f\ x)))$

With applicative order we reduced the expression to:

$f\ (f\ (f\ (f\ x)))$

The results are the same.
> 2 votes

---
Tags: lambda-calculus, functional-programming, encoding-scheme
---


# Question
Title: Why the 127 encodings of ASCII needed to be extended to 256?
As you all know the ASCII chart needed to be extended from ***127 encoding to 256,*** I can't really see why. Some google expert on Coursera said **"We needed that because of the foreign languages".** I still Can't understand what that has to do with the ASCII Chart.

***Can anyone explain the full story?***

# Answer
ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters.

Nowadays people mostly use Unicode, with a bit over a million code points, which can be further combined to produce more characters. There are plenty of unused code points which can be assigned values in the future, and that happens all the time.

Please note that for most people English is a foreign language. And it would be “naïve” to think that ASCII let’s you write all English text.
> 11 votes

# Answer
There are a few other good reasons to expand from 7-bit ASCII, but since you ask specifically about foreign languages, I want to tell you about that angle.

English has words with diacritical marks, usually loan words like *naïve* or *café*. They are rare, and usually you'll get into no trouble for omitting the diacritics. Occasionally one might stumble into a word that means something else when you omit the diacritical marks, such as *exposé* vs *expose*, but those cases are rare and usually the meaning can be inferred from the context without much difficulty.

The same is not true for most languages written on the Latin alphabet, though. Romance languages like Italian, French, Spanish and Romanian use diacritics much more than English does, and omitting the diacritics as 7-bit ASCII would impose would make text harder to read. The same is true for Germanic languages other than English, as many of those make heavy use of umlauts and special letters like the å found in Swedish. My native Finnish, too, considers ä, ö and å to be separate characters distinct from *a* and *o*, and telling them apart from each other is necessary to correctly parse words without needing to infer from context.

Therefore, when computing picked up pace among users who do not use English as their native language, it was essentially inevitable that the character sets should be expanded. The alternative would have been massive orthographic reforms in some of the most spoken languages in the world to make them conform to the limitations of the increasingly vital computers. That would not have worked out – although semi-official conventions did occasionally spring up (eg. replacing ö with oe). So in order to not get in the way, 8-bit Extended ASCII encodings usually lend support to these special characters, relieving at least some of the non-English languages.

Fast-forwarding to today, Unicode has support for a vast array of characters that extend the support well beyond Latin-based alphabets as well. This means almost everyone can type their native languages without the computer's charset limitations needing to get in the way.
> 6 votes

# Answer
The question of how foreign languages justifies expanding the encoding in actual usage is well explained by earlier answers. The question of why *foreign* languages would affect the *American* Standard Code for Information Interchange is subtly different.

> As you all know the ASCII chart needed to be extended from 127 encoding to 256

No. The original American Standard Code for Information Interchange (ASCII) has never been extended to 8-bit. It remains to this day a 7-bit encoding standard. The latest revision to the ASCII standard was in 2017, with (ANSI) INCITS 4-1986\[R2017\].

Due to the same needs for exchanging computer information, non-English speaking countries have to develop their own standard codes. The countries using Latin scripts were already using ASCII in their computers and existing documents. When the 8-bit word architecture became popular, they developed their own standard codes based on the 7-bit ASCII, using the additional bit-space for additional symbols they need. By habit, these standards are sometimes called "extended ASCII" standards. But they are actually new standards, and to this day remain distinct from ASCII. They are standardized as ECMA-94, ECMA-113, ECMA-114, ECMA-118, ECMA-121, ECMA-128, and ECMA-144, as well as the ISO/IEC 8859 series.
> 4 votes

---
Tags: data-structures, history, encoding-scheme, binary
---


# Question
Title: How to Generate Münchhausen Numbers in High Radices?
A Münchhausen number is a whole number equal to the sum of its digits raised to powers of themselves. For the purpose of such calculations, the convention is that $0^0 = 1$. For example, in radix 10, the number 3435 is a Münchhausen number, since $3435 = 3^3 + 4^4 + 3^3 + 5^5$. In radix 4, the number 313 is a Münchhausen number, since $313 = 3^3 + 1^1 + 3^3$. On a curious property of 3435 covers more details, and shows that Münchhausen numbers in radix $b$ must be less than or equal to $2b^b$.

Münchhausen numbers for base $b$ can be generated with a brute-force search, by checking whether each number from 1 to $2b^b$ is equal to the sum of its digits raised to powers of themselves. One way to improve upon this is to generate multisets of digits, and for each combination check whether the sum of digits raised to powers of themselves produces a number with the same multiset of digits. Even with parallelization, this seems infeasible for large bases. For example, for base 35, a Münchhausen number would have at most 36 digits. The number of combinations (with repetitions) of 36 elements from 35 digits is $\binom{35 + 36 - 1}{36}=\binom{70}{36}=109,069,992,321,755,544,170.$ This is in addition to those multisets with fewer than 36 elements that would also be checked.

If any, what algorithm(s) can be used to generate Münchhausen numbers feasibly for high bases (e.g., base 35)? OEIS sequence A166623 includes Münchhausen numbers for bases between 2 and 35.

# Answer
> 3 votes
# Meet-in-the-middle

One approach is to use a meet-in-the-middle algorithm. This will reduce the running time from $2b^b$ to something in the ballpark of $\sqrt{2b^b}$.

In particular, let your candidate number be $$A = a\_b b^b + \dots + a\_1 b + a\_0.$$ We'll write this in the form $A=A^\* + A^\dagger$ where $$\begin{align\*} A^\* &= a\_b b^b + \dots + a\_{\lfloor b/2 \rfloor+1} b^{\lfloor b/2 \rfloor+1}\\ A^\dagger &=a\_{\lfloor b/2 \rfloor} b^{\lfloor b/2 \rfloor} + \dots + a\_0. \end{align\*}$$ Finally, let $s(a\_i b^i + \dots + a\_0) = a\_i^{a\_i} + \dots + a\_0^{a\_0}$. We'll look for all solutions to the equation $$A^\* + A^\dagger = s(A^\*) + s(A^\dagger).$$ This is equivalent to $$A^\* - s(A^\*) = s(A^\dagger) - A^\dagger.$$ We'll compute a table of all possible values for $s(A^\dagger)-A^\dagger$, where $A^\dagger$ varies over all possibilities of the form above. Then, we'll compute $A^\*-s(A^\*)$, for each $A^\*$ of the form above, and look it up in the table to check for a match. Each match yields a solution to the equation above, and thus a valid Münchhausen number. This can be used to enumerate all Münchhausens.

For $b=10$, the running time becomes something like $10^5$ steps of computation, which should be no problem. However, this is entirely infeasible for $b=35$. The algorithm is still exponential-time.

# Linear programming

Another possible idea is to use integer linear programming.

Let $x\_{i,d}$ be a 0-or-1 variable, with the intended meaning that $x\_{i,d}=1$ means that $a\_i = d$. Then we can obtain a bunch of linear inequalities that characterize a correct solution. In particular, we have $$\sum\_{i,d} x\_{i,d} d b^i = \sum\_{i,d} x\_{i,d} d^d.$$ We also have $\sum\_d x\_{i,d} = 1$ for each $i$.

Next, given a lower and upper bound $L,U$, we could use integer linear programming to search for a valid solution in the range $\[L,U\]$, by adding the inequality $L \le \sum\_{i,d} x\_{i,d} d b^i \le U$ and looking for a valid solution. To enumerate all solutions, start with a broad range $\[0,2b^b\]$, then when you find a valid solution, split the current range in two and recurse. Then, use an off-the-shelf ILP solver to find solutions.

I don't expect this to be very effective, but you could augment it with additional inequalities that might help the ILP solver run faster. In particular, for each prime number $p$ less than $2b^b$, we have $$\sum\_{i,d} x\_{i,d} d b^i \equiv \sum\_{i,d} x\_{i,d} d^d \pmod p$$ This can be encoded via the linear equality $$\sum\_{i,d} x\_{i,d} d b^i = \sum\_{i,d} x\_{i,d} x\_{i,d} d^d + y\_p p$$ where $y\_p$ is an integer variable. Note that $d b^i$ and $d^d$ are integer constants, so you can reduce them modulo $p$. Thus we get the linear equality $$\sum\_{i,d} \alpha\_{i,d,p} x\_{i,d} = \sum\_{i,d} \beta\_{d,p} x\_{i,d} + y\_p p$$ where $\alpha\_{i,d,p} = d b^i \bmod p$ and $\beta\_{d,p} = d^d \bmod p$ are constants you can precompute. You can do the same if $p$ is a power of a prime.

So, you might add linear inequalities of this form for several well-chosen prime powers (say, all of the prime powers below some bound; or all small prime numbers, plus the prime power factors of $b$, $b-1$, $b+1$, $b^2$, $b^2-1$, $b^2+1$). One could hope that these help the linear solver find solutions faster.

I don't know whether this will be effective, but it is something you could try. It would not be too hard to implement and see how well it works.

---
Tags: number-theory
---


# Question
Title: Design a Turing Machine which accepts strings $x \# y$ where $x \ge y$
> Imagine you are designing a TM where $x$ and $y$ are binary representation( $x \ge y$). the TM should accept $1101\\#1001$ and reject strings such as $110\\#10001$, as well as it could reject if you have more than one $\\#$ or less than one $\\#$.

Now, I have tried doing this. my idea is that:

1. For step one is to mark the left side first input as X, then scan to the right until you find a # sign, go to step 2, else if # sign not there reject
2. For step 2, zigzag left most side and compare each input to compare the 1's with each other. but i think i'm way off.

# Answer
> 1 votes
> zigzag left most side and compare each input to compare the 1's with each other.

That is the right idea -- comparing the input one character at a time will work.

However we should be careful that we are comparing the right digits. For example, we don't want to say that `11` is bigger than `101` just because we compared the first two digits only, and said that `11` is bigger than `10`. So, maybe it would be helpful to have, as a first step, to see which of them has more digits. Make sure that you ignore leading zeros when doing this.

> but i think i'm way off

Not at all, you have the right idea.

---
Tags: turing-machines
---


# Question
Title: Time complexities of state-of-the-art SAT solvers with respect to length of the formula
I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables.

If I am not mistaken, one of the reasons why most believe P does not equal to NP is that there exists no polynomial-time algorithm for SAT despite tremendous effort from mathematicians and computer scientists. However, the P vs NP problem only cares about the time complexity with respect to the length of the formula, not the number of variables.

If these state-of-the-art SAT solvers were run on 3CNF formulas, then a time complexity exponential to the number of variables implies a time complexity exponential to the length of the 3CNF.

However, if they were run on arbitrary CNFs, whose length can be exponential to the number of variables, then a time complexity exponential to the number of variables would not necessarily imply a time complexity exponential to the length of the CNF.

Thus, a related question is, are these SAT solvers run on 3CNF or CNF while measuring time complexity?

# Answer
> 4 votes
For 3SAT, the number of variables is polynomially related to the number of clauses. (See the end for the justification.)

Consequently, any algorithm for 3SAT whose running time is polynomial in the number of clauses would also be polynomial in the number of variables; and any algorithm for 3SAT whose running time is polynomial in the number of variables would also be polynomial in the number of clauses.

It is known that there is a polynomial-time algorithm for 3SAT, if and only if there is a polynomial-time algorithm for SAT, if and only if there is a polynomial-time algorithm for CircuitSAT (e.g., for formulas). Also, despite decades of work on SAT solvers, no one knows any algorithm for 3SAT that runs in polynomial time (or indeed in less than exponential time in the worst case). You could take this as evidence that there is no polynomial-time algorithm for 3SAT; which implies that there is no polynomial-time algorithm for SAT or CircuitSAT, either, and also implies that P != NP.

---

Justification: Let $n$ denote the number of variables and $m$ the number of clauses. We have $n \le 3m$ (a variable that doesn't appear in any clause can be ignored) and $m \le 8n^3$ (each clause has three literals, and you can ignore repeated clauses). It follows that $n/3 \le m \le 8n^3$ and $\sqrt\[3\]{m/8} \le n \le 3m$, i.e., each is polynomially related to the other.

---

I see that you revised your question. That clarifies that I think you have a misconception. You talk about "run\[ning\] \[a SAT solver\] on arbitrary Boolean formulas". However, you can't run a SAT solver on an arbitrary Boolean formula. SAT solvers only work on CNF formulas.

However, we do know that any Boolean formula can be converted to an equisatisfiable CNF formula of size at most polynomial in the size of the formula, and vice versa. If you had an algorithm that could test satisfiability of arbitrary Boolean formulas in time polynomial in the size of the formula, then it would follow that you have an algorithm that could test satisfiability of 3CNF formulas in time polynomial in the size of the formula (every 3CNF formula is a Boolean formula), and thus an algorithm that could test satisfiability of 3CNF formulas in time polynomial in the number of variables -- which contradicts the available evidence. So, if you believe that there is no algorithm to solve 3SAT in time polynomial in the number of variables, then you should also believe that there is no algorithm to test satisfiability of arbitrary Boolean formulas in time polynomial in the size of the formula.

---
Tags: turing-machines, time-complexity, satisfiability, p-vs-np, 3-sat
---


# Question
Title: Algorithm for identifying polygons (set of points)
Are there any known algorithms for uniquely identifying some set of points despite scaling, moving and with some amount of threshold?

I have an "ideal" set of points with coordinates and I need to check if other set matches the ideal one. Other set could be rotated, scaled or distorted a bit (points could be placed with slight offset).

All sets have one common property: there are 2 points located farthest apart. This can be used to, at least, negate rotation. We do know angle (45deg) that line between farthest points create with axis, and we do know needed distance between them.

I've tried following algorithm:

1. Rotate "other" set to some point (so that farthest points create line that is 45 degrees to "x" axis);
2. Scale set so farthest points distance = "ideal" distance;
3. Use sort of GeoHashing algorithm to get point hash with some accuracy (like threshold).

But that approach gave nothing. "GeoHashing" produces semi random results and probably not suitable for 1000x1000 calculations. And using geometric operations furthermore reduced accuracy (initial distortion of points + inaccuracy of some geometric methods).

## EDIT:

I want to add some details to it:

1. Points set contains only 5 points (including those distant ones);
2. There could be several "ideal" point sets and I want to find if given set matches something (that's why I used GeoHash);
3. Basically task is to find matching polygon/set of points with given accuracy. If points do not match exactly (not located in the same coordinates), but are pretty close to ideal location (like +-2) it's a match.

# Answer
I'll assume you are given two sets of points and want to determine whether one can be transformed to match the other. This is the pointset registration problem in computer vision. There are standard algorithms for this problem.

One of the crucial challenges is outliers -- e.g., points in the first set that don't have any corresponding point in the second set, or that have a large amount of error in their location. If you don't have outliers in your setting, then the problem becomes noticeably easier: simple least-squares linear regression might suffice.

If you have to deal with outliers, one standard way is to use RANSAC to find a rigid transformation that, when applied to the first set, makes it match the second set. A rigid transformation is determined by the correspondence between two points. So, you can use RANSAC: repeatedly pick a pair of points in the first set, choose a candidate pair of points in the second set for them to be matched to, compute the rigid transformation that maps the first two points to the latter two points, apply it to all points in the first set, find all inliers (points that are well-matched), update your estimate of the rigid transformation, count the number of inliers, and do this many times and keep the best rigid transformation you've found.

There are many other approaches as well. If you do some research, you should be able to find many algorithms, techniques, and even existing tools.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Arden's Rule, DFA & NFA to regular expressions
I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state:

if *x = s + xr*
then *x = sr*\*, with $s,r\in$ Regular Expressions

With that said, when I'm trying to transform one DFA in a RE this questions pop:

For example regarding this DFA

1. The $\epsilon$ is added in the entry stage A or in the final stage D and A ?
2. The equations should be written regarding the transitions in or out of a given state

2.1 For example A = $\epsilon$ \+ 0B + 1C or A = $\epsilon$ \+ 0C
3. Can the equational method and Arden's Rule be applied to a NFA with multiple initial states ?

Final thoughts, I have been trying out and it seems that when we count the transitions out of a state the $\epsilon$ should be added to the final state. When we count the transitions into a state the $\epsilon$ should be added to the initial state.

Keep in mind that I SERIOUSLY doubt my conclusions and I really need some help.

# Answer
> 4 votes
You can use either way. In both cases you construct a mapping from the states of the automaton to regular expressions, $\[-\]: Q\to RE$.

Let $(s, l, t)$ denote a transition from $s$ with label $l$ to target state $t$.

Also, let $\oplus\_{i\leq n}r\_i = r\_1 + \ldots + r\_n$.

## 1st case: By incoming edges.

1. Add a final state, $F$, and an $\varepsilon$-transition from each previous final state to $F$.
2. For every state $X$ with $n$ incoming edges $(s\_i, l\_i, X)\_{i\leq n}$, make an equation $\[X\] = \oplus\_{i\leq n}(\[s\_i\]l\_i)$.
3. Use rule: $X = s + Xr \Longrightarrow X = sr^\*$ on the equations
4. The final regular expression is $\[F\]$.

## 2nd case: By outgoing edges.

1. Add a new initial state, $S$, and an $\varepsilon$-transition from $S$ to the previous initial state.
2. For every state $X$ with $n$ outgoing edges $(X, l\_i, t\_i)\_{i\leq n}$, make an equation $\[X\] = \oplus\_{i\leq n}(l\_i\[t\_i\])$.
3. Use rule: $X = s + rX \Longrightarrow X = r^\*s$ on the equations
4. The final regular expression is $\[S\]$.

Both methods work for NFAs as well. None of the above transformations depend on determinism.

Regarding your final thoughts, when you count the outgoing edges, if you add the $\varepsilon$-transition in the final states, then $\[F\] = \emptyset$, because $F$ (the new final state) has no outgoing edges, and this doesn't contribute to the equations. What you want to add is a new initial state, so that you can compute $\[S\]$. For your DFA example, $\[S\] = \varepsilon\[A\]$. Similarly, adding a new initial state is useless when transforming by incoming edges. In this case, $\[S\] = \emptyset$ and what you want is $\[F\]$, which for your example, would be $\[F\] = \[A\]\varepsilon + \[D\]\varepsilon$.

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


title: Minimum XOR for queries

text:
# Question
Title: Minimum XOR for queries
I was asked the following question in an interview.

Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \otimes b$ is minimum, where $x\otimes y$ for to integers $x$ and $y$ is the bitwise xor operation of $x$ and $y$.

For example:

Input:

```
A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]

```

Output

```
[6, 9, 6, 9]

```

Because when 4 is XORed with any element in A minimum value will occur when A\[I\] = 6

```
4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5

```

Here is my brute force solution in python.

```
def get_min_xor(A, B):

    ans = []

    for val_b in B:
        min_xor = val_b ^ A[0]

        for val_a in A:
            min_xor = min(min_xor, val_b ^ val_a)
            # print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))

        ans.append(min_xor ^ val_b)

    return ans

```

Any ideas on how this could be solved in sub O(MxN) time complexity?

I had the following idea in mind. I would sort the array A in O(NlogN) time then for each element in B. I would try to find it's place in the array A using binary search.Let's say B\[X\] would fit at ith position in A then I would check the min XOR of `B[X] ^ A[i-1]` and `B[X] ^ A[i+1]`. But this approach won't work in all the cases. For example the following input

```
A = [1,2,3]
B = [2, 5, 8]

```

Output:

```
[2, 1, 1]

```

Here is the trie based solution

```
class trie(object):
    head = {}

    def convert_number(self, number):
        return format(number, '#032b')

    def add(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:

            if bit not in cur_dict:
                cur_dict[bit] = {}
            cur_dict = cur_dict[bit]

        cur_dict[number] = True

    def search(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:
            if bit not in cur_dict:
                if bit == "1":
                    cur_dict = cur_dict["0"]
                else:
                    cur_dict = cur_dict["1"]
            else:
                cur_dict = cur_dict[bit]

        return list(cur_dict.keys())[0]

def get_min_xor_with_trie(A,B):

    number_trie = trie()

    for val in A:
        number_trie.add(val)

    ans = []

    for val in B:
        ans.append(number_trie.search(val))

    return ans

```

# Answer
> 6 votes
Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values).

Let say we know that all integers in $A$ are 32-bit values. Use the following steps:

* Create an empty trie. Every node of trie may contains at most two children for 0 and 1 bits.
* Insert all values in $A$ into the tree in $O(32 \times m) = O(m)$
* For each value in $B$, traverse the tree from the leftmost bit. If a bit doesn't match with child of a middle node, continue the traverse using the existing child until you reach a leaf. Traversing finishes in $O(32 \times n) = O(n)$

Which in total, the complexity is $O(m + n)$.

# Answer
> -2 votes
Using Trie Data Structure.

```
public class Solution {

    public int[] solve(int[] A, int[] B) {
        int ans[] = new int[B.length];
        Trie root = new Trie();
        for (int s : A) {
            insert(root, s);
        }
        for (int i = 0; i < B.length; i++) {
            ans[i] = search(root, B[i]);
        }
        return ans;
    }

    class Trie {
        public Trie left, right;
        public int val;

        public Trie() {
            left = right = null;
            val = Integer.MIN_VALUE;
        }
    }

    public void insert(Trie t, int n) {
        Trie root = t;
        for (int pos = 31; pos >= 0; pos--) {
            int bit = (1 << pos) & n;
            if (bit == 0) {
                if (t.left == null) {
                    t.left = new Trie();
                }
                t = t.left;
            } else {
                if (t.right == null)
                    t.right = new Trie();
                t = t.right;
            }
            if (pos == 0)
                t.val = n;

        }
    }

    private int search(Trie t, int n) {
        // TODO Auto-generated method stub
        Trie root = t;
        for (int pos = 31; pos >= 0; pos--) {
            int bit = (1 << pos) & n;
            if (bit == 0) {
                if (t.left != null)
                    t = t.left;
                else
                    t = t.right;

            } else {
                if (t.right != null)
                    t = t.right;
                else
                    t = t.left;
            }
            if (pos == 0)
                return t.val;
        }
        return 0;
    }
}

```

---
Tags: algorithms, optimization, sorting, bit-manipulation, xor
---


# Question
Title: What happens when there are two same IP addresses?
IPv4 addresses run out few years ago. But everywhere I can see mine or someone elses IP address it's in IPv4, not IPv6. I understand that world switched to IPv6? So why we can see address in older format? Does that mean somewhere someone can have same address as I? How can that work?

# Answer
ISPs asign *one* IPv4 address to a customer, and your "WiFi box" acts as a router/NAT box/ DHCP server doling out addresses from a private range internally. It is possible that the "outside" IPv4 address is itself in a private range, leaving your ISP through a mere handful of IPv4 addresses via NAT (real one, your box really does PAT, port forwarding through one IPv4 address).
> 1 votes

# Answer
Yes and no -- the same IPv4 adress adress can be used by other computers. But only "locally", not globally.

IP-adresses are often translated using things like NAT - network adress translation.

Every computer I have seen has an internal IP-adress of 127.0.0.1. This adress can be used inside the computer, not from the outside.

On my LAN my computer currently has the IP adress 10.0.1.30. I would expect millions of LAN connected computers to have the same adress.

Before going to the internet, the adress is translated by my access point into something else, assigned by the ISP. The access point keeps track of which of the several computers on the LAN that has started the connection and that has sent a request and will receive a response. In effect all computers on my LAN has the same external IPv4 adress. A further translation or "packaging" of adresses may be done by the ISP.

My adress on the "global" internet is currently IPv4 and is unique, no other computer has that adress. The adresses are in limited (exhausted really) supply. So we will be able to live only a while more on IPv4.

The idea of IPv6 is that every computing device will have its own, unique, adress. I guess this was the original idea between IPv4, but then the number of devices simply exploded.
> 1 votes

---
Tags: computer-networks
---


# Question
Title: In a bottom-up evaluation of a syntax directed definition, inherited attributes can
In a bottom-up evaluation of a syntax directed definition, inherited attributes can

1. always be evaluated
2. be evaluated only if the definition is L-attributed
3. be evaluated only if the definition has synthesized attributes
4. never be evaluated

---

My attempt:

> Option $(3)$ should be true, since ,
>
> Synthesized Attributes: They are computed from the values of the attributes of the children nodes.
>
> Inherited Attributes: They are computed from the values of the attributes of both the siblings and the parent nodes.

But, one of my friends commented that "Your explanation is correct, but option C says "has" not "is"." (In fact, I did not get this comment).

---

Somewhere it explain as below:

A Syntax Directed Definition (SDD) is called S Attributed if it has only synthesized attributes.

L-Attributed Definitions contain both synthesized and inherited attributes but do not need to build a dependency graph to evaluate them. So, option $(2)$ is true.

> > Can you explain it in a formal way, please?

# Answer
Indeed option (2) is true.

Synthesized attributes contain those attributes which inherit properties from their children.

Inherited attributes are those which inherit properties from their parents or their left siblings.

L-attributed definitions contain both synthesized and inherited attributes.

So for an SDT to evaluate inherited attributes, it must follow L-attributed definition.
> -1 votes

# Answer
3) would be the answer because synthesized attributes are evaluated using Bottom up parsing.Stack is used for this which is implemented using arrays.
> -1 votes

---
Tags: compilers, syntax, code-generation
---


# Question
Title: Variations of Activity Scheduling Algorithm
I've been following Greedy algorithms in the textbook Jeff Erickson. Here is the following Question I was stuck in proving Proof of Correctness for the following variant of the standard Activity Selection problem.

For each of the following alternative greedy strategies, either prove that the resulting algorithm always constructs an optimal schedule, or describe a small input example for which the algorithm does not produce an optimal schedule.

(a) Choose the course x that ends last, discard classes that conflict with x, and recurse.

(b) Choose the course x that starts first, discard all classes that conflict with x, and recurse.

(c) Choose the course x that starts last, discard all classes that conflict with x, and recurse.

(d) Choose the course x with shortest duration, discard all classes that conflict with x, and recurse.

(e) Choose a course x that conflicts with the fewest other courses, discard all classes that conflict with x, and recurse.

(f) If no classes conflict, choose them all. Otherwise, discard the course with longest duration and recurse.

(g) If no classes conflict, choose them all. Otherwise, discard a course that conflicts with the most other courses and recurse.

(h) Let x be the class with the earliest start time, and let y be the class with the second earliest start time.

```
  • If x and y are disjoint, choose x and recurse on everything but x.

  • If x completely contains y, discard x and recurse.

  • Otherwise, discard y and recurse.

```

(i) If any course x completely contains another course, discard x and recurse. Otherwise, choose the course y that ends last, discard all classes that conflict with y, and recurse.

I've been able to provide counter examples for (a),(b),(d) and I found that (c) is correct as it is just the the original problem if we imagine time running in reverse.

It will be very helpful if one provides the idea of proof of correctness for the remaining 2 correct strategies (as it's said in the text that out of all 9 strategies, 3 are correct).

# Answer
The three Greedy strategies that work are (c),(h),(i).I'll prove them as follows, and for the remaining taking examples of 2-3 classes and tweaking them a bit, works as a contradictory example. Thanks, @D.W for providing a general strategy for proving correctness.

**(c)**
**Claim $\textbf{1}.$** There is an optimal schedule that includes the course that starts last.
Proof: Let $x$ be the course that starts last. Let $S$ be any schedule that does not contain $x,$ and let $y$ be the last course in $S .$ Because $x$ starts last, we have $S\[y\]\<S\[x\]$ Thus $F\[i\]\<S\[y\]\<S\[x\]$ for every other class $i$ in $S,$ which implies that $S^{\prime}=S-y+x$ is still a valid schedule, containing the same number of classes as $S .$ In particular, if $S$ is an optimal schedule, then $S^{\prime}$ is an optimal schedule containing $x$.
By the general greedy proof strategy described here and by using the above claim, by induction we can prove that this strategy works.

**(h)**
**Claim $\textbf{2} .$** If $x$ and $y$ are disjoint, then every optimal schedule contains $x .$
Proof: If $x$ and $y$ are disjoint, then $F\[x\]\<S\[y\],$ which implies that $F\[x\]\<S\[i\]$ for all $i \neq x .$ Thus, if $S$ is any valid schedule that does not contain $x,$ then $S+x$ is a larger valid schedule. Thus, no optimal schedule excludes $x .$

**Claim $\textbf{3} .$** If $x$ contains $y,$ there is an optimal schedule that excludes $x$
Proof: If $x$ contains $y,$ then every class that conflicts with $y$ also conflicts with $x$ Thus, for any valid schedule $S$ that contains $x,$ there is another valid schedule $S-x+y$ of the same size that excludes $x$

**Claim $\textbf{4} .$** If $x$ and $y$ overlap, but $x$ does not contain $y,$ there is an optimal schedule that excludes $y$
Proof: Suppose $x$ and $y$ overlap, but $x$ does not contain $y .$ Then $x$ must end before $y$ ends, and therefore every class that conflicts with $x$ also conflicts with $y .$ Thus, for any valid schedule $S$ that contains $y,$ there is another valid schedule $S-y+x$ of the same size that excludes $y$.
By the general greedy proof strategy described here and by using the above claims, by induction we can prove that this strategy works.

**(i)**
**Claim $\textbf{5} $.** If any course $x$ contains another course $y,$ there is an optimal schedule that does not include $x$. Proof: Let $S$ be any valid schedule that contains $x .$ Then $S-x+y$ is another valid schedule of the same size.

**Claim $\textbf{6} $.** Suppose no course contains any other course. Then there is an optimal schedule containing the course that ends last.
Proof: If no course contains any other course, then the class that ends last is also the class that starts last. This claim now follows from Claim 1.
Hence, by the general greedy proof strategy described here and by using the above two claims, by induction we can prove that this strategy works.
> 0 votes

---
Tags: algorithms, correctness-proof, greedy-algorithms
---


# Question
Title: motivation and idea of defining non-deterministic Turing machine
This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms and I also have some basic knowledge of how computers operate. However, I am really interested in the idea of a Turing machine, especially the non-deterministic one.

I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):

1. A Turing machine is a machine performing works specified on a cookery book (algorithm).
2. The pages of the cookery book represent the "states" of your machine and each page contains a table saying that which state and which cell your machine will move to given the alphabet the machine read and your current state. (NB. This is not a function but a partial function because it is possible that the machine stops.)
3. So, to guess the idea and motivation of defining an abstract Turing machine, I imagine that the algorithm corresponds to the partial map, the memory of the computer corresponds to the (infinitely long) tape and what's finally on the tape is the answer to the question you wanna solve.

So, Turing machine looks like a machine to realize any algorithm to solve problems. One just "translates" any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.

In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.

---

OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty much similar to a Turing machine except that the partial function is now replaced by a "relation". That is, it is a one-to-multiple map and it is no longer a (partial) function.

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm. It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers? If no, why do we need to allow multiple choices for a Turing machine?

Any help will be appreciated!

---

**update** From the linked post, it looks like the introduction of NTM naturally leads to a class of "problems" (not algorithms because a problem can be solved by several algorithms with different efficiencies) called NP problems. Forgive me that I still feel that every step is such a huge jump... Could someone close the gaps a little bit? thanks a lot!

Motivated by @reinierpost's answer, I found this explanation of NP problems on CMI website. The example problem is to choose 100 students from 400 candidates subject to some constraint that some pairs of students cannot be included. In this case, I can imagine that a Turing machine trying to solve this may naturally equip itself with a cloning ability such that it is able to generate the solution with multiple choices in the steps. Then, as long as some choices or branches of the NTM work, the machine finds the solution(s). In this sense, an NTM looks like a multi-threading parallelization to save time?

# Answer
> 5 votes
> Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm.

I think this is your primary misconception: an NTM is **not supposed to be a realistic machine.** That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real world are not written in this way with "multiple options".

An NTM is, instead, supposed to be a *hypothetical more powerful computer;* in contrast to the Turing machine, which corresponds to real computers, NTMs can do even more. Why can they do more? Basically, because they can branch off on several different options, or parallel universes; and they accept a string if and only if *one* of those universes accepts. A regular Turing machine corresponds to just having one parallel universe.

Let's see an example. Consider the following problem: Given as input an integer $x$, is the square root of $x$ an integer? Accept if yes, reject if no.

* A Turing machine would have to do some math and figure out how to calculate the square root. So we have to do the hard work of designing a correct algorithm :(
* An NTM doesn't have to do any of that hard work, and can just cheat :) It works in the following way: just nondeterministically guess the number $y$. Then check if $y^2 = x$. If so, accept.

This is how NTMs are unrealistic: they can just cheat and try all possibilities in different universes, even though when we know in the real world that this is impossible. For example, if we input $9$ to the NTM we just described, then there are lots of parallel universes that try different values of $y$: one tries $y = 1$, one tries $y = 2$, one tries $y = 3$, one tries $y = 4$, and so on. In many of these universes the NTM does the wrong thing: for example, it picks $y = 4$ and finds that $4^2 \ne 9$, and rejects (incorrectly). But those universes are just ignored; we don't care about them. The only thing that matters is that there is *some* universe where the machine accepts, namely the universe where we picked $y = 3$, and found that $3^2 = 9$.

> It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

It isn't exactly like "choosing for yourself"; it's that each choice is tried in a different parallel universe.

> Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers?

No, they are a little bit different than uncertainty choosing random numbers, mainly because we only care about the parallel universes where the machine accepts (in particular, we care if there is at least one parallel universe where it accepts), and we ignore all the universes where the machine rejects.

> If no, why do we need to allow multiple choices for a Turing machine?

We don't need them to describe real computations, but they are a useful tool for understanding the limits of computation. In particular, there are many problems that NTMs can solve efficiently, that we don't know how to solve efficiently with TMs; these are the famous "NP-complete" problems, and it is useful in practice to know what problems will be hard to design an algorithm for.

> In this sense, an NTM looks like a multi-threading parallelization to save time?

Yes, it is a lot like this, except a little bit less general: the thing is that the multiple parallel universes cannot communicate, but they only work independently, and then we care if at least one universe accepts.

In other words, with a multi-threading machine, you could try lots of different parallel threads, and then at the end you could have all the threads come together, and then decide what to do with all the outputs of the different threads. NTMs can't do that; they just spawn off lots of parallel universes and accept if at least one universe accepts.

Another difference (in terms of practicality) is that multi-threading on a real computer usually only allows for a small (probably constant) number of parallel threads. On the other hand, NTMs can spawn off as many parallel universes as you like; if the input is size $n$, they often might spawn of $2^n$ threads, which is a larger number than is possible in practice. This is why NTMs are not a realistic type of machine, and are just a theoretical object of study.

# Answer
> 0 votes
You're getting caught up in definitions. Algorithms are usually *defined* to be deterministic because they are usually introduced in a context where deterministic computation is the norm, the vehicle of choice for the task at hand.

Many real-life algorithms are nondeterministic (e.g. many cookbook recipes are *very* nondeterministic, and many algorithms in pseudo-code have lines that say "pick an *x*"). If we are denied the option of calling them "algorithms", and thus are left without a useful term to describe what they are, that is purely a matter of definition, it's not because such things do not exist.

---
Tags: algorithms, turing-machines, polynomial-time, nondeterminism
---


title: NFA for all strings not containing 1010

text:
# Question
Title: NFA for all strings not containing 1010
if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting state itself, right?

the starting state accepts 0,1 so I can essentially take the string 1010 and self loop it in the starting state itself... is that correct?

# Answer
> 2 votes
As mentioned in the comments, your NFA actually accepts all strings. What you have hit upon is the fact that NFAs are not resilient to complementation. Whereas given a DFA for a language, you can turn it to a DFA for the complement of the language by complementing the set of accepting states, the same doesn't hold for NFAs. In fact, "complementing" an NFA (that is, constructing an NFA for the complemented language) could result in exponential blow-up in the number of states!

As an example, consider the language of all words over $\\{1,\ldots,n\\}$ which do *not* contain all symbols. There is an NFA with $n$ states accepting the language (the NFA has multiple initial states, which might not be allowed under your definition), but any NFA for the complement must contain at least $2^n$ states. This blow-up is worst possible due to the powerset construction which converts an NFA with $n$ states to an equivalent DFA with $2^n$ states, which can be complemented without increasing the number of states.

# Answer
> 0 votes
From S with input 1, you can’t go both to state S and A. In states A, B, C where do you go with the other input? What happens in state D if you get further input?

# Answer
> 0 votes
> if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting state itself, right?

Your machine is not correct. The problem is as you pointed out: If you start in state $S$ of your machine, you can take the string `1010` and self-loop in the starting state. That shows that your machine accepts `1010`, but you wanted to design a machine that does not accept `1010` :(

This is an example of a language that is hard to make an NFA for. Often, NFAs are easier than DFAs because they allow nondeterminism, but here an NFA will probably need just as many states as a DFA.

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


# Question
Title: Find longest path by number of edges, excluding cycles
I need to analyse a directed graph (not a DAG) but I don't know the name of the algorithm I would need to use. The graph has many cycles.

My desired behaviour is: given a graph source and graph sink, find the longest path by number of edges, excluding cycles.

By graph source, I mean a vertex with one or more edges to other vertices and no incoming edges, and the opposite for sink. If there's better terminology, then please let me know about this.

It's important that I'm able to determine what the path is, so I would need an algorithm that can produce a list of edges.

By excluding cycles, this might entail not traversing an edge the process traversed previously.

Do you recognise this algorithm and could you tell me the name, please?

Thanks in advance

# Answer
The problem you are defining is called *Longest Path* (and occasionally *Longest $s$-$t$-Path*) and is NP-complete.

That is, there is an algorithm for solving it, but you shouldn't keep you hopes up when it comes to the running time of the algorithm: it's unlikely to run in polynomial time.

The trivial algorithm is to check for every permutation of the graph, in time $O(d! \cdot 2^{dn})$, but this becomes intractable extremely quickly. It is possible to bring this down to $O(2^n \cdot \text{poly}(n))$.

You have three options as far as I can see it:

* limit the length of the path you need to some reasonable integer $k$ and solve with FPT techniques
* use an approximation algorithm
* limit the type of input graph to certain smaller and *easier* graph classes.

**Note 1:** As Yuval Filmus points out, the problem *Longest Path* is *usually* referring to the undirected version. However, the problem remains NP-complete also in its directed version by a reduction from *Directed Hamiltonian Path (Between Two Vertices)* (Garey & Johnson, 1979).

**Note 2:** Yuval Filmus also pointed out that it is solvable in single-exponential time.

**Note 3:** The problem is solvable in linear time on DAGs, and if you allow repeating edges, the answer is always *infinite* when your graph has a cycle.
> 3 votes

---
Tags: graphs
---


# Question
Title: Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable
Using 2SAT and implication graphs, how could I prove the following properties of implication graphs:

Suppose there is a directed path between literals l1 and l2 in G\_φ. Then there is also a directed path between their complements. Then, there is τ, a truth assignment satisfying φ where τ(l1) is true, then τ(l2) must also be true.

Using this, show that φ is unsatisfiable \<=\> there is some directed cycle in G\_φ containing a variable x and its complement.

Where G\_φ is the directed implication graph of 2SAT containing formula φ with n variables. Hence 2n vertices with one for every possible literal in φ, and edges (not l1, l2) and (not l2, l1) for every clause (l1 ∨ l2) in φ.

My first intuition was a proof by contradiction however I failed to construct a general enough assumption. I then tried to show that if the truth assignment means that l1 and l2 are true, then by building a cycle connecting all variables, the assignment is only valid when those edges exist. However this doesn't seem rigorous enough since I'm not properly understanding why the cycle requires the complement of x to exist.

Currently I build G by adding a vertex for every variable x and it's complement as well. Then for each clause (a v b) I add an edge between not a and b and not b and a.

However I fail to see how this would specifically form a cycle.

Working of the sipser textbook.

# Answer
> 1 votes
Here is a proof sketch. We will show that the given formula is unsatisfiable iff there exists a cycle containing both $x$ and $\lnot x$, for some variable $x$.

Suppose first that there exists a cycle containing both $x$ and $\lnot x$. The existence of a path $x \to^\* y$ in the implication graph means that in a satisfying assignment, if $x$ holds then so does $y$ (you can prove it by induction on the length of the path). Since there is a cycle containing both $x$ and $\lnot x$, there are paths $x \to^\* \lnot x$ and $\lnot x \to^\* x$. In any satisfying assignment, either $x$ or $\lnot x$ holds, and both cases lead to contradiction.

Suppose next that there are no cycles containing both $x$ and $\lnot x$. We will construct a satisfying assignment as follows. Choose some variable $x$. If there is a path $x \to^\* \lnot x$, assign $x = F$, and for each literal $\ell$ such that $\lnot x \to^\* \ell$, assign the value to the underlying variable which makes $\ell$ true. You cannot be assigning the same variable two different truth values, since if $\lnot x \to^\* y$ and $\lnot x \to^\* \lnot y$ then also $y \to^\* x$ and so also $\lnot x \to^\* x$, completing a cycle involving $x$ and $\lnot x$.

If there is a path $\lnot x \to^\* x$, assign $x = T$, and continue analogously.

If neither of these paths exist, assign $x$ arbitrarily, and continue as before. This cannot lead to a contradiction, for the following reason. Suppose that we assign $x = F$, and that there are paths $x \to^\* y$ and $x \to^\* \lnot y$. Then there is also a path $y \to^\* \lnot x$ and so a path $x \to^\* \lnot x$, contradicting the assumption that none of the two paths exists.

If after this process there is some unassigned variable left, choose one of them, and repeat until the assignment covers all variables.

---
Tags: graphs, computability, satisfiability, 2-sat
---


# Question
Title: How to prove the NP-completeness of MOD-PARTITION
MOD-PARTITION: Given a set of integers $A={a\_1,...,a\_n}$, their weights $w = \\{w\_1, w\_2, \dots, w\_n\\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum\_{x \in X} w(x) * x) \mod k \\; = \\; (\sum\_{a \in A \setminus X} w(a) * a) \mod k$?

Can some please provide some idea on how to prove the NP-Completeness of this problem? I saw the proof of the set-partition problem (using a reduction from subset-sum) and I suppose, that this proof maybe will be some little modification of it.

# Answer
> 2 votes
Showing that this your problem is in NP is easy.

To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.

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


# Question
Title: How the kernel works in a LCF theorem prover
I heard that there is some mechanism in LCF-based theorem provers that only allows some functions to create values of type theorem. I believe these are based on abstract data types.

Could someone sketch in pseudo-code how does this work? (in case the above is correct)

# Answer
> 1 votes
Here are some thoughts and code from the kernel (file thm.ML in Isabelle/Pure) from Isabelle:

```
abstype thm = Thm of
 deriv *                        (*derivation*)
 {cert: Context.certificate,    (*background theory certificate*)
  tags: Properties.T,           (*additional annotations/comments*)
  maxidx: int,                  (*maximum index of any Var or TVar*)
  shyps: sort Ord_List.T,       (*sort hypotheses*)
  hyps: term Ord_List.T,        (*hypotheses*)
  tpairs: (term * term) list,   (*flex-flex pairs*)
  prop: term}                   (*conclusion*)
and deriv = Deriv of
 {promises: (serial * thm future) Ord_List.T,
  body: Proofterm.proof_body}
with

```

Also here is a quotation of from Paulson book on ML. About abstract datatypes he says:

> A modular structure makes a program easier to understand. Better still, the modules ought to serve as interchangeable parts: replacing one module by an improved version should not require changing the rest of the. program. Standard ml's abstract types and functors can help us meet this objective too. A module may reveal its internal details. When the module is replaced, other parts of the program that depend upon such details will fail. ML provides several ways of declaring an abstract type and related operations, while hiding the type's representation.

So you cannot instantiate an abstract datatype you can use it (its fields + functions). The matter on how you implement this feature is very of dependent of the language. If you want to do it in the lambda-calculus, there should be something like that in Benjamin Pierce's TAPL book on the later chapters.

A nice reference for this is also here.

# Answer
> 2 votes
If I recall correctly, this was chapter 5 or 6 of John Harrison's *Handbook of Practical Logic and Automated Reasoning*.

Jon Sterling wrote some notes for a recitation a year or two back, specifically for an LCF prover using sequent calculus.

---
Tags: programming-languages, automated-theorem-proving
---


# Question
Title: Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable
I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma\_1$ is Turing recognizable. I'm not sure what's the general way to approach this, but I noticed $A\_{TM}$ is in $\Sigma\_1$ by described in follows.

First note $\Sigma\_1$ = the language of the form $\\{x | \exists y R(x,y)\\}$, where $R(x,y)$ is decidable predicate.

$A\_{TM}$ = $\\{\big \langle M, w \big \rangle| \exists t \[M \text{ accept $w$ in $t$ steps}\]\\}$, where $M \text{ accept $w$ in $t$ steps}$ is decidable predicate.

$A\_{TM}$ = $\\{\big \langle M, w \big \rangle| \exists t T(\big \langle M \big \rangle, w, t)\\}$

So we show that $A\_{TM} \in \Sigma\_1$, but does it sufficient to show that $\Sigma\_1$ is in r.e.? Any suggestion?

# Answer
Suppose that $L = \\{x \mid \exists y R(x,y)\\}$, where $R(x,y)$ is a decidable predicate.

To recognize $L$, given an input $x$, enumerate all possible $y$, and check whether $R(x,y)$ holds for at least one of them. This will halt iff $x \in L$.
> 1 votes

---
Tags: complexity-theory, formal-languages, turing-machines
---


# Question
Title: Algorithm that finds the number of simple paths from $s$ to $t$ in $G$
Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$.
I have an algorithm in which I will run a DFS(Depth First Search) but if DFS finds $t$ then it will not change the color(from white to grey) of any of the nodes which comes in the path $s \rightsquigarrow t$ so that if this is the subpath of any other path then also DFS goes through this subpath again.For example consider the adjacency list where we need to find the number of paths from $p$ to $v$.
$$\begin{array}{|c|c c c|} \hline p &o &s &z \\ \hline o &r &s &v\\ \hline s &r \\ \hline r &y \\ \hline y &v \\ \hline v &w \\ \hline z & \\ \hline w &z \\ \hline \end{array}$$ Here DFS will start with $p$ and then lets say it goes to $p \rightsquigarrow z$ since it doesnot encounter $v$ DFS will run normally.Now second path is $psryv$ since it encounter $v$ we will not change the color of vertices $s,r,y,v$ to grey.Then the path $pov$ since color of $v$ is still white.Then the path $posryv$ since color of $s$ is white and similarly of path $poryv$.Also a counter is maintained which get incremented when $v$ is encountered.

Is my algorithm correct? if not, what modifications are needed to make it correct or any other approaches will be greatly appreciated.

**Note**:Here I have considered the DFS algorithm which is given in the book *"Introduction to algorithms by Cormen"* in which it colors the nodes according to its status.So if the node is unvisited , unexplored and explored then the color will be white,grey and black respectively.All other things are standard.

# Answer
Your current implementation will compute the correct number of paths in a DAG. However, by not marking paths it will take exponential time. For example, in the illustration below, each stage of the DAG increases the total number of paths by a multiple of 3. This exponential growth can be handled with dynamic programming.

Computing the number of $s$-$t$ paths in a DAG is given by the recurrence, $$\text{Paths}(u) = \begin{cases} 1 & \text{if } u = t \\ \sum\_{(u,v) \in E} \text{Paths}(v) & \text{otherwise.}\\ \end{cases}$$

A simple modification of DFS will compute this given as

```
def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

```

It is not difficult to see that each edge is looked at only once, hence a runtime of $O(V + E)$.
> 43 votes

# Answer
You only need to notice that the number of paths from one node to the target node is the sum of the number of paths from its children to the target. You know that this algorithm will always stop because your graph doesn't have any cycles.

Now, if you save the number of paths from one node to the target as you visit the nodes, the time complexity becomes linear in the number of vertices and memory linear in the number of nodes.
> 16 votes

# Answer
The number of paths between any two vertices in a DAG can be found using adjacency matrix representation.

Suppose A is the adjacency matrix of G. Taking Kth power of A after adding identity matrix to it, gives the number of paths of length \<=K.

Since the max length of any simple path in a DAG is |V|-1, calculating |V|-1 th power would give number of paths between all pairs of vertices.

Calculating |V|-1 th power can be done by doing log(|V|-1) muliplications each of TC: |V|^2.
> 0 votes

# Answer
As Nicholas' answer mentioned, you can use a top-down recursive approach, and use memoïzation to prevent solving overlapping subproblems. However, you can also use a bottom-up approach, which counts the number of paths to the target from *all* nodes in the graph, with the same complexity of $O(V+E)$.

```
def dfs(G, s, t):
    fifo = Queue()
    fifo.put(s)
    n_paths = [0] * len(G.V)
    n_paths[s] = 1
    while not fifo.empty():
        current = fifo.get()
        for p in G.parents(current):
            n_paths[p] += n_paths[current]
            if not p.already_visited:
                fifo.put(p)
                p.already_visited = True
    return n_paths[t]

```
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Recover a matrix with minimum number of queries
Alice has a matrix $A \in \\{0,1\\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob can ask Alice is: "Does $\sum a\_{i,j} = 0$" for some subset $\\{a\_{i,j}\\}$ of size $n$. How fast (i.e. minimum questions) can Bob recover the ones (even with high probability)?

# Answer
Let me consider the case $n = m$ for concreteness. Since the entropy of $A$ is $n\log n$ and each question results in at most one bit of information, at least $n\log n$ queries are needed.

Suppose that a question is selected uniformly at random. The probability that the answer is zero is $(1-1/n)^n \approx 1/e$, and in that case, we can mark all the queried entries as zero. Imagine making such queries until $N$ are successful. This is the same as making $N$ queries, each of which involves $n$ zero positions at random. The probability that a particular zero position is never queried is $$ \left(1 - \frac{n}{n(n-1)}\right)^N \approx e^{-N/n}. $$ Therefore after $(2+\epsilon) n\log n$ queries, the probability that a particular zero position is never queried is at most roughly $n^{-2-\epsilon}$, and so the probability that not all zero positions are revealed is at most $n^{-\epsilon}$. We conclude that $(2e+\epsilon) n\log n$ queries suffice to reveal the matrix with probability $1-o(1)$.

We can repeat the calculation for general $m$, but the bounds no longer match. For example, when $m$ is very large, the answer to most questions will be zero, and so bounding the amount of information obtained from a single query by one bit is too generous.
> 2 votes

---
Tags: algorithms, probabilistic-algorithms, search-problem, game-theory
---


# Question
Title: Representing "but not" in formal grammar
I just came across the following grammar definition:

> **CommentChar ::**
>
> **SourceCharacter** *but not* **LineTerminator**

But for discussion, I'll present this similar construct:

> **Digit ::**
>
> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
>
> **Zero ::**
>
> '0'
>
> **NonZeroDigit ::**
>
> **Digit** *but not* **Zero**

Is this "but not" construct common in formal grammar specifications? If there a name for it?

I realize that **NonZeroDigit** could be defined by "manually" expanding the nonterminals and finding the difference -- here that process is as straightforward as it gets. But for more complicated "but not" constructs, I imagine that would be painful and error-prone.

Or, in grammars that support it, is this just considered just a sequence of (a) a negative lookahead (for **Zero**) combined with (b) the nonterminal for **Digit**.

# Answer
For context-free grammars (I guess your question concerns this type of formal grammars), it would be not only painful, but also impossible in general.

Suppose we have an algorithm that provides such "expansion" and yields a new grammar without $\text{but not }$occurrences. Then we can take two arbitrary context-free languages $L, L'$ with start nonterminals $A, A'$ respectively, write down a rule $B \longrightarrow A \text{ but not } A'$, run the algorithm on it, and get a context-free grammar for $L\backslash L'$. It contradicts a well-known fact that difference of two context-free languages can be not context-free.
> 11 votes

# Answer
In the case of regular languages (and in your examples, we're just talking about character classes, which are an especially simple form of regular language), they are closed under set difference. Not only that, but unlike (say) Thompson's method, Brzozowski's method for constructing DFAs can be easily extended to handle the set difference operator.

I'm going to use ring notation, because Brzozowski's algorithm looks much neater that way.

* $0$ is the language with no strings in it (i.e. the empty set), and $1$ is the language containing just the zero-length string.
* $E\_1 + E\_2$ is the set union of $E\_1$ and $E\_2$.
* $E\_1 E\_2$ is the language concatenation operator.
* $E^\*$ is the Kleene closure of $E$.
* $E\_1 - E\_2$ is the set difference.

Now we introduce some additional notation.

$E(0)$ is $1$ if $1 \in E$, otherwise $0$. You can compute this by replacing all of the terminal symbols in $E$ with $0$ and simplifying; if you think of the terminal symbols as "variables", this is what you get by "evaluating" the expression at $0$.

If it seems unclear as to why you would think of terminal symbols as "variables", then the Brzozowski derivative should make this much more obvious. If $a, b, \ldots$ are terminal symbols, recursively define the Brzozowski derivative as:

$$\begin{align\*} \frac{\partial}{\partial a} a & = 1 \\ \frac{\partial}{\partial a} b & = 0 \\ \frac{\partial}{\partial a} \left( E\_1 + E\_2 \right) & = \frac{\partial}{\partial a} E\_1 + \frac{\partial}{\partial a} E\_2 \\ \frac{\partial}{\partial a} E^\* & = \frac{\partial}{\partial a} E\\,E^\* \\ \frac{\partial}{\partial a} \left(E\_1 E\_2 \right) & = \frac{\partial}{\partial a} E\_1\\, E\_2 + E\_1(0)\\,\frac{\partial}{\partial a} E\_2 \\ \frac{\partial}{\partial a} \left( E\_1 - E\_2 \right) & = \frac{\partial}{\partial a} E\_1 - \frac{\partial}{\partial a} E\_2 \end{align\*}$$

The interesting things to note:

* Terminal symbols act like variables.
* Addition and subtraction (i.e. set union and set difference) behave normally.
* Kleene closure acts like $e^x$ (i.e. $\frac{\partial}{\partial x} e^{E} = \frac{\partial E}{\partial x} e^{E}$).
* Concatenation acts a bit like a product, but it's asymmetrical.

(Exercise: Suppose there was another product operator which obeyed the symmetric product rule $\frac{\partial}{\partial a} \left(E\_1 \times E\_2 \right) = \frac{\partial E\_1}{\partial a} \times E\_2 + E\_1 \times \frac{\partial E\_2}{\partial a}$. What would that operator mean?)

Then Taylor's theorem for regular languages states:

$$E = E(0) + a \frac{\partial E}{\partial a} + b \frac{\partial E}{\partial b} + \cdots$$

where the sum is taken over all terminal symbols. This gives an expansion for a DFA state. The first term, $E(0)$, tells you whether the expression represents a final state or not, and the other terms give the transitions.

So, for example, if we want to construct the DFA for $q\_0 = (a + b)^\* - (a + b)^\* a a (a + b)^\*$, we just do the expansion.

$$\begin{align\*} q\_0(0) & = (0 + 0)^\* - (0 + 0)^\* 0 0 (0 + 0)^\* = 1 \\ \frac{\partial q\_0}{\partial a} & = \frac{\partial}{\partial a}(a + b)^\* - \frac{\partial}{\partial a} \left( (a + b)^\* a a (a + b)^\* \right) \\ & = \frac{\partial}{\partial a}(a + b) \\, (a + b)^\* - \left( \frac{\partial}{\partial a} (a + b)^\* \left( (a + b)^\* a a (a + b)^\* \right) + \left( (a + b)^\* \right)(0) \frac{\partial}{\partial a} \left( a a (a + b)^\* \right) \right) \\ & \hbox {(some calculation later)} \\ & = (a + b)^\* - \left( (a + b)^\* a a (a + b)^\* + a (a + b)^\* \right) \\ \frac{\partial q\_0}{\partial b} & = (a + b)^\* - \left( (a + b)^\* a a (a + b)^\* \right) \end{align\*}$$

That is:

$$q\_0 = 1 + a\\,q\_1 + b\\,q\_0$$

where

$$q\_1 = (a + b)^\* - \left( (a + b)^\* a a (a + b)^\* + a (a + b)^\* \right)$$

That is, the start state is a final state, with a $b$ transition back to itself, and an $a$ transition to the next state, which we can then calculate using the same method.
> 9 votes

# Answer
The particular grammar formalism used in the grammar you cite is defined in Appendix A of that document, which includes in section A.3, a precise definition:

> A grammar production may specify that certain expansions are not permitted by using the phrase “but not” and then indicating the expansions to be excluded.

That phrasing is certainly not unique to GraphQL. ECMA-262, which defines the language formerly known as Javascript, contains virtually the same wording in the description of the formalism it uses:

> The right-hand side of a production may specify that certain expansions are not permitted by using the phrase “but not” and then indicating the expansions to be excluded.

Although the grammar formalisms are not identical, I think the authors of the GraphQL document were influenced, at least, by the ECMAScript formalism, since there is quite a lot of overlap (and the typography is also very similar). They also share the use of `:` vs. `::` to distinguish between syntactic and lexical rules, the use of negative lookahead rules of the form `[ lookahead ∉ *Set* ]`, parameterised non-terminal symbols using bracketed subscripts, and the use of the subscript `<sub>opt</sub>` to indicate optional elements in right-hand side. GraphQL adds the use of the subscript `<sub>list</sub>` for repeated elements. The `<sub>opt</sub>` subscript convention is fairly widespread -- it's also used in the C and C++ formal specifications, for example. The other ones are less common.

(GraphQL also uses the phrase `one of` in the same way that it is used in ECMA-262 and the C and C++ standards. However, the usage is not formally noted in the notation summary as far as I can see.)

Given the similarity, I'm assuming that the `but not` from GraphQL and the one from ECMA-262 are the same operator, which only serves to increase the number of examples of use that I have available.

Semantically, `but not` is not a lookahead assertion. Rather, it's the set difference operator. (As noted above, the grammar formalism has a negative lookahead assertion, but set difference does not have anything to do with lookahead.) The left-hand argument of `but not` is the right-hand side of a production. In all the examples of use we have, it's a single a non-terminal but in theory it could be any sequence of non-terminals. (And that detail doesn't matter since it would always be possible to create a new non-terminal to avoid that restriction.) So the left-hand side refers to a possibly infinite context-free "language" (in the formal sense of the word: a set of sentences).

The right-hand side is less clear, since the documents only say "the expansions to be excluded". In both GraphQL and ECMA-262, there is a mechanism to create a union of exclusions. GraphQL is explicit: "A grammar may also list a number of restrictions after “but not” separated by `or`". ECMA-262 uses the essentially the same form (except that the restriction list is then introduced with the words `one of`), without bothering to provide a formal definition.

In practice, the exclusion set is always a finite set. In most cases, it is used to create what would be described as a character class in most regular expression libraries, as in the example of **NonZeroDigit** which you cite. This usage is widespread in both documents; it applies to a lexical rule (introduced with `::`), and both the left- and right-hand sides of `but not` are subsets of *SourceCharacter*. \[Note 1\]

But it is also used for a more interesting case: the distinction between *Identifier* and the various keyword tokens. In GraphQL, for example, we have:

```
*EnumValue* :
     *Name* but not **true** or **false** or **null**

*FragmentName* :
     *Name* but not **on**

```

Similarly, in ECMA-262 we find

```
*Identifier* :
     *IdentifierName* but not *ReservedWord*

```

\[Note 2\]

These are all syntactic rules, as indicated by the single `:`, although both the left- and the right-hand sides use lexical symbols. Crucially, in all cases of this usage, the right-hand sides represent finite sets.

The question that then confronts us is whether the fact that the right-hand side of `but not` is always finite is an unmentioned restriction on the formalism, or whether it simply reflects the fact that more complex uses were not necessary in these particular grammars.

Without the restriction, this formalism could be used to advantage in C++, for example. Consider the well-known parsing ambiguity which gives rise to the so-called "Most Vexing Parse", whose resolution is written in English in the C++ standard, rather than using any grammar formalism:

> There is an ambiguity in the grammar involving *expression-statements* and declarations: An *expression-statement* with a function-style explicit type conversion as its leftmost subexpression can be indistinguishable from a *declaration* where the first *declarator* starts with a **(**. In those cases the statement is a *declaration*.
> —*(§9.8/1, \[stmt.ambig\])*

Using an unrestricted `but for` operator, this could be written:

```
*expression-statement* : *candidate-expression-statement* but not *declaration*

```

where *candidate-expression-statement* is the previous definition of *expression-statement*. It is not immediately obvious whether the result is context-free or not, but the parsing strategy to handle it would reflect current practice: do both possible parses, perhaps in parallel, and if they both work then forget about the `expression-statement` parse. (In the context of C++, it doesn't really matter whether or not this is context-free. C++ parsers already need to deal with many non-contet-free aspects.)

If this kind of ambiguity existed within GraphQL (or ECMA-262), then the failure to use `but not` to express the resolution could be considered *de facto* evidence that the intention of the `but for` formalism was that the right-hand side not be a general syntax object. While I haven't yet found an example of that, the fix to the error described in \[Note 2\] would involve a use of the `but for` formalism in which the right-hand side was not finite. \[Also see Note 3\]

For what it's worth, I believe that the intention of the formalism was that the right-hand side be finite, but I obviously have no way to prove it. If so, then the `but not` formalism does not add any expressive power to BNF, since the difference between a context-free language and a finite set (or, indeed, any regular language) is still context-free.

If, on the other hand, the intention was that `but not` could remove an arbitrary subset of derivations described by a sequence of grammar symbols, then it would permit the definition of non-context-free grammars.

---

### Notes

1. In C and C++, this sort of restriction is expressed as narrative. For example, a character literal is defined in BNF as a sequence of *c-char* enclosed between **'** characters, with the following definition of *c-char*:

> ```
> c-char:
>     any member of the source character set except
>     the single-quote **'**, backslash **\**, or new-line character
>
> ```
>
> —*(§5.13.3, \[lex.ccon\])*
2. The GraphQL document is marked as a draft, so it would be churlish to criticise it on the basis of small errors. However, I couldn't help noting that it includes an obvious misuse of the `but not` operator:

> ```
> *BlockStringCharacter* ::
>     *SourceCharacter* but not **"""** or **\"""**
>     **\"""**
> ```

Here, neither **"""** nor **\\"""** are in *SourceCharacter*, so the restriction has no effect. What was intended was something like

```
*NoTripleQuote* ::
    *SourceCharacter*<sub>list</sub> but not *SourceCharacter*<sub>list,opt</sub> **"""** *SourceCharacter*<sub>list,opt</sub>
*BlockStringCharacterList* ::
    *NoTripleQuote*
    *BlockStringCharacterList*<sub>opt</sub> **\"""** *NoTripleQuote*<sub>opt</sub>
    **\"""**
```
3. It would be possible to loosen the restriction to also allow infinite sets described by regular grammars, and the fix in \[Note 2\] is a regular grammar (although that might not be immediately obvious). However, describing that loosened description in the context of the documents in question would be require hauling in quite a lot of formal language theory which is otherwise unnecessary.
> 8 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: Compilation with a witness / certificate
Sometimes, to install a program, you have a choice between compiling it yourself or downloading a precompiled binary. In theory (using a new programming language and a new compiler designed specifically for this), is it possible to generate a witness / certificate with the compiled binary such that checking the witness / certificate is very easy when compared to compiling things yourself, but ensures that the compilation indeed yields this binary ?

To avoid trivial answers, I'll specify things a bit more: The source language should contain ML, and the target language should be some realistic assembly language. The compiler should do many optimizations so that speed of the compiled program is comparable to that of OCaml, and in particular the compilation can not be just concatenating an interpreter and the source.

From what I've read, the longest thing in compilation is the optimizations. So my question is more or less: Can optimizations run much faster on a non-deterministic machine (in which case, we can use the witness to know which path to take on the real machine).

# Answer
> 2 votes
In theory, what you are asking about has been studied, under the name "translation validation". See, e.g., the following classic paper:

George C. Necula. "Translation validation for an optimizing compiler." PLDI 2000.

In practice, compilation is such a complicated messy process that I doubt there will be any easy-to-verify certificate that proves the entire compilation process was done correctly (including lexing, parsing, front-end, optimization, back-end, assembly, linking, etc.). Academic work typically focuses on just one or two phases of the process (e.g., some of the stages of optimization).

One should separate two separate issues: can the verifier be simpler than the compiler? can the verifier be faster than the compiler?

Simpler is interesting, because it means the verifier can potentially be more trustworthy (e.g., less likely to have bugs). Classic work on translation validation focuses on that case.

Faster is a different question. Some optimizations are deterministic and won't benefit, but there are certainly plenty of optimizations that involve a search over some space of possibilities. An extreme version of that is the concept of "superoptimization", which optimizes a short code sequence by searching over all possible optimized versions and finding the one that is the fastest while remaining semantically equivalent to the original. See, e.g., the following papers:

R. Sausnauskas, Y. Chen, P. Collingbourne, J. Ketema, G. Lup, J. Taneja, J. Regehr. "A Synthesizing Superoptimizer."

Sorav Bansal, Alex Aiken. "Automatic Generation of Peephole Superoptimizers." ASPLOS 2006.

---
Tags: compilers
---


# Question
Title: Parallel programming models: Why do OpenMP and MPI dominate?
In a lecture on HPC parallel programming (for CPUs) we discussed various models available from Pthreads to OpenMP to MPI and others like Charm++, X10, UPC, Chapel…. The main focus was clearly on the first three. Intrigued by the topic I did some research on my own but could find sources, examples and discussions mainly for those first three. Later I discovered "AMPI" which can even run legacy MPI application with many of the benefits Charm++ offers but nobody seems to use it.

Why are the other models so neglected? Compared to the rather crude MPI alternatives like Charm++ and UPC appear more convenient as they handle a lot of the "dirty work" neatly in the background.

# Answer
> 1 votes
I will give you two main reasons why MPI and OpenMP dominate.

The first one is that they are *standards*. There are several available implementations, and you can be sure to find them available on every possible supercomputer machine. This is strictly related to the concept of *portability*: you write your parallel code and, if you do not use anything else related to a particular machine, you can run the same code on all of the parallel machines you have available.

The second reason is the *programmer's resistance*. With MPI and OpenMP covering both message-passing and shared-memory parallel programming (and you can even use them simultaneously if useful and/or required) why a programmer, especially a beginner in the field, should spend his/her time learning new parallel programming languages that are not granted to become standards? Sure, as you pointed out, other languages provide some benefits but the question is, would you invest your time betting on something that may even totally disappear in the future ? Standards are here to stay. Anyway, regarding this specific point, my humble opinion is that, if possible, one should instead spend some time on different languages (not just those one for parallel programming) because this is a useful discipline and learning different paradigms is always beneficial. However, when reading your curriculum vitae for possible hiring, the people that can hire you for a position will be in general mostly interested to your knowledge of the standards, not to your knowledge of niche languages (in general, even though there could be exceptions of course).

---
Tags: programming-languages, computation-models, parallel-computing, message-passing
---


title: About P2P networking

text:
# Question
Title: About P2P networking
In P2P(peer-to-peer) networking, it is possible for the server program(software) and the client program(software) to be running on the same computer.

So the two must have the same IP address.

I am confused about this. Is there nothing going wrong if both of them uses the same IP address?

Please clarify.

# Answer
> 1 votes
Sure. That's fine. Nothing wrong with that. Transport-layer protocols (such as UDP or TCP) use port numbers so that you can run multiple applications on the same machine without any difficulty.

---
Tags: computer-networks, peer-to-peer
---


# Question
Title: Revert array shuffle faster than in O(n^2)
I want to reverse an array that was shuffled with the function

```
array<integer> shuffle(arr: array<integer>, f: (integer) -> integer) {
    for (i: integer = 0; i < arr.length; i++) swap(arr[i], arr[f(i)]);
    return arr;
}

```

The array passed to this function is `[0, 1, 2, 3, ... n-1]` and **function `f` for any `i` returns a value that is less or equal to `i`**. I have an array returned by the function and I want to restore the results of `f(i)` for each iteration. What I do currently is:

```
array<integer> deshuffle(arr: array<integer>) {
    array<integer> result = [];
    for (i : integer = arr.length - 1; i > 0; i++) {
        index: integer = -1;
        for (j: integer = 0; j < i + 1; j++) {
            if (arr[j] == i) {
                index = j;
                break;
            }
        }
        result.push(index);
        swap(arr[i], arr[index]);
    }
}

```

Here I rely on the fact that the last member of the array can only be shuffled during the last iteration, which means I can find it, push the index and reswap it back and repeat it recursively (this is kinda like the insertion sort if I remember the name correctly). But the trouble is that this code is slow (O($n^{2}$)). Is there any way to do it faster?

# Answer
"Unshuffling" the array is sorting it, there are $\Theta(n \log n)$ algorithms available (e.g. mergesort or heapsort), and it is not hard to prove that that the problem requires $\Omega(n \log n)$ comparisons.

Or, as the elements are $0, 1, 2, \dotsc, n - 1$, just go through the array, undoing the permutation: see where `i = arr[0]`should go, where `j = arr[i]`should go, ... until you get back to `0` (you just identified a cycle). Pick the first value not already identified to belong to a cycle, and identify another, and keep going until you've got them all. That clearly is $\Theta(n)$, just that you get the permutation in cycle form.
> 0 votes

# Answer
It's not very clear what you are asking. It seems you want to find the values of f(i) for all i.

Problem: You can't distinguish between f(0) = 1, f(1) = 0, and f(0) = 0, f(1) = 1.
> 0 votes

---
Tags: algorithms, sorting
---


# Question
Title: What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?
I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other.

Also as an aside, if anyone knows any good resources that go over the topic of optimization in detail (especially gradient free optimization) that I could read or watch, i'd really appreciate it if you could point me in the right direction.

Thanks in advance guys and apologies if its a basic question, I'm quite new to the topic.

# Answer
> 1 votes
Actually, derivative methods such as random search shorten the time allocated for function evaluation if the problem is big. On the other hand, derivative-free methods take much time to complete function evaluation that leads to a dramatic increase in optimization time.

---
Tags: algorithms, optimization, machine-learning, search-algorithms, gradient-descent
---


# Question
Title: Worst case $O(n \ln n)$ in place stable sort?
I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources?

Just a reminder, in place means it uses the array passed in and the sorting algorithm is only allowed to use constant extra space. Stable means that elements with the same key appear in the same order in the sorted array as they did in the original.

For example, naive merge sort is worst case $O(n \ln n)$ and stable but uses $O(n)$ extra space. Standard quicksort can be made stable, is in place but is worst case $O(n^2)$. Heapsort is in place, worst case $O(n \ln n)$ but isn't stable. Wikipedia has a nice chart of which sorting algorithms have which drawbacks. Notice that there is no sorting algorithm that they list that has all three conditions of stability, worst case $O(n \ln n)$ and being in place.

I have found a paper called "Practical in-place mergesort" by Katajainen, Pasanen and Teuhola, which claims to have a worst case $O(n \ln n)$ in place stable mergesort variant. If I understand their results correctly, they use (bottom-up?) mergesort recursively on the first $\frac{1}{4}$ of the array and the latter $\frac{1}{2}$ of the array and use the second $\frac{1}{4}$ as scratch space to do the merge. I'm still reading through this so any more information on whether I'm interpreting their results correctly is appreciated.

I would also be very interested in a worst case $O(n \ln n)$ in place stable quicksort. From what I understand, modifying quicksort to be worst case $O(n \ln n)$ requires selecting a proper pivot which would destroy the stability that it would otherwise normally enjoy.

This is purely of theoretical interest and I have no practical application. I would just like to know the algorithm that has all three of these features.

# Answer
There are several algorithms that are all of the above, and pretty much all of them have been invented in the last 30 years.

Probably the nicest is the class of algorithms called Block sort, including the version (called WikiSort) by Kim and Kutzner in 2008. It is not only stable and completely in-place (O(1) memory overhead in the transdichotomous model), it is also adaptive, and thus will take fewer steps to sort nearly sorted lists, converging to O(n) comparisons in the case of an already sorted list. You can find an implementation in C, C++, and Java here: https://github.com/BonzaiThePenguin/WikiSort

Also of interest is the GrailSort algorithm (also a Block sort) by Huang and Langston (1989-1992), which actually outperforms WikiSort on several types of test cases. A C++ implementation is available here: https://github.com/Mrrl/GrailSort
> 12 votes

# Answer
You can write an in-place, stable mergesort. See this for details. In the author's own words:

> A beautiful in place - merge algorithm. Test it on inverted arrays to understand how rotations work. Fastest known in place stable sort. No risk of exploding a stack. Cost: a relatively high number of moves. Stack can still be expensive too. This is a merge sort with a smart in place merge that 'rotates' the sub arrays. This code is litteraly copied from the C++ stl library and translated in Java.

I won't copy the code here, but you can find it at the link or by checking the C++ STL. Please let me know if you would like me to try to provide a more detailed description of what's going on here.
> 9 votes

# Answer
Please take this as a long comment on some practical thoughts. Although this is not an answer to your question, I think you might be interested in this Python discussion:

> This describes an adaptive, **stable**, natural mergesort, modestly called timsort (hey, I earned it ). It has supernatural performance on many kinds of partially ordered arrays (less than $\lg(N!)$ comparisons needed, and as few as $N-1$), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.
>
> \[...\]
>
> Merging adjacent runs of lengths A and B **in-place is very difficult**. Theoretical constructions are known that can do it, but they're too difficult and **slow for practical use**. But if we have temp memory equal to min(A, B), it's easy.

Source: bugs.python.org, author: Tim Peters

So it seems as if Timsort still has advantages over an stable, in-place, $\mathcal{O}(n \log n)$ worst-case time complexity merge sort.

Also note that Timsort performs good on already-sorted arrays.

So Python makes use of Timsort (which is Mergesort with some tweaks) and as I've looked up the Java implementation some years ago, it was also Mergesort (I think they now also use Timsort).
> 1 votes

# Answer
**Any unstable sorting algorithm can be made stable**, by adding the original relative positions of the objects being compared as a tie-breaker in the comparison function. This can be done without any extra memory **if you are already sorting array indices**, as a way to avoid moving the actual objects around; otherwise it's an O(n) extra memory technique.

If this technique is applicable, then you can use it with heapsort to get a stable O(n log n) in-place sort for free.

**Quicksort** is a funny algorithm whose *average case* runtime is O(n log n), but whose *worst case* runtime is governed by some rare pathological conditions which can effectively reduce it to an inefficient insertion sort with O(n^2) runtime. A valid way to evade those pathological cases (especially those which might be deliberately constructed by an adversary) is to choose the pivots using a good randomiser, eg. a decent PRNG seeded using some true RNG, which makes the probability of experiencing the pathological behaviour infinitesimally small. Then, to avoid the PRNG dominating performance, switch to insertion sort for small divisions of the array (traditionally, 16 elements or less).

As noted by previous answers, quicksort is available in a stable-sorting variant. This does not depend on details of choosing the pivot, so the above random pivot technique remains applicable. Since insertion sort is also stable, this optimisation can also be used.
> -1 votes

---
Tags: algorithms, reference-request, sorting, in-place
---


# Question
Title: What does it mean to isolate a field in a word?
I have been reading in the 'computer organization and design' book and I encountered this section:

`what operations isolate a field in a word`

I know that the answer is logic operations and shift instructions from the book but. I want to know what does it even mean to isolate a field

# Answer
Consider an 8-bit word whose contents can be described as follows:

* Bits 0–2 encode some value $x$.
* Bits 3–4 encode some value $y$.
* Bits 5–7 encode some value $z$.

Each of these different values is known, in this context, as a *field*. You can think of it as a field in some form.

Isolating a field out of a word means extracting just the value of the field. For example, denoting the entire word $w$, here is how we can isolate each of the fields:

* $x$: AND $w$ with the mask $7$ (which is $111$ in binary).
* $y$: Right-shift $w$ by 3 positions, and AND the result with the mask $3$.
* $z$: Right-shift $w$ by 5 positions.

In C, you could implement these as follows:

```
x = w & 7;
y = (w >> 3) & 3;
z = w >> 5;

```
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)
given the input

> `(((lambda f (lambda x (f x))) (lambda y (* y y))) 12)`

**`what does this step evaluate to: lambda x (f x)`**

I am trying to evaluate this and I have the following tree so far:

how do I evaluate this ? looking for guidance on what I might be doing wrong or how to proceed with this.

# Answer
Lambda expressions are evaluated by reducing the leftmost redex first. A redex is something of the form $(\lambda a.b)c$ . Your expression is $(\lambda f.\lambda x.fx)(\lambda y . \*yy)~12$. So your first redex is

$$(\lambda f.\lambda x.fx)(\lambda y . \*yy)$$

So you substitute $(\lambda y . \*yy)$ for $y$ in $\lambda x.fx$ to get $$\lambda x.(\lambda y . \*yy)x~ 12$$

Then your next redex is the entire expression, ($(\lambda y . \*yy)x$ is also a redex but it isn't the leftmost one) substituting $12$ in for $x$. So you get $$(\lambda y . \*yy)~12$$

Then your last redex is the entire expression again so you get

$$\*~12~12$$
> 1 votes

---
Tags: lambda-calculus
---