# Question
Title: Why is backtracking a necessary step in the Maze problem?
The problem I am working on is specifically this:

> A Maze is given as N\*N binary matrix of blocks where source block is the upper left most block i.e., maze\[0\]\[0\] and destination block is lower rightmost block i.e., maze\[N-1\]\[N-1\]. A rat starts from source and has to reach the destination. The rat can move only in two directions: forward and down.

The question essentially asks to find and print the path that exists through a given maze from the top left to the bottom right of the maze. The details of the problem can be found here.

The core of the C/C++ code for this problem's solution is this:

```
/* A utility function to check if x,
y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
    // if (x, y outside maze) return false
    if (
        x >= 0 && x < N && y >= 0
        && y < N && maze[x][y] == 1)
        return true;

    return false;
}

/* This function solves the Maze problem
using Backtracking. It mainly uses
solveMazeUtil() to solve the problem.
It returns false if no path is possible,
otherwise return true and prints the path
in the form of 1s. Please note that there
may be more than one solutions, this
function prints one of the feasible
solutions.*/
bool solveMaze(int maze[N][N])
{
    int sol[N][N] = { { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 } };

    if (solveMazeUtil(
            maze, 0, 0, sol)
        == false) {
        printf("Solution doesn't exist");
        return false;
    }

    printSolution(sol);
    return true;
}

/* A recursive utility function
to solve Maze problem */
bool solveMazeUtil(
    int maze[N][N], int x,
    int y, int sol[N][N])
{
    // if (x, y is goal) return true
    if (
        x == N - 1 && y == N - 1
        && maze[x][y] == 1) {
        sol[x][y] = 1;
        return true;
    }

    // Check if maze[x][y] is valid
    if (isSafe(maze, x, y) == true) {
        // mark x, y as part of solution path
        sol[x][y] = 1;

        /* Move forward in x direction */
        if (solveMazeUtil(
                maze, x + 1, y, sol)
            == true)
            return true;

        /* If moving in x direction
           doesn't give solution then
           Move down in y direction  */
        if (solveMazeUtil(
                maze, x, y + 1, sol)
            == true)
            return true;

        /* If none of the above movements
           work then BACKTRACK: unmark
           x, y as part of solution path */
        sol[x][y] = 0;
        return false;
    }

    return false;
}

```

I am confused about the following part of the solution in the function `solveMazeUtil`:

```
/* If none of the above movements
               work then BACKTRACK: unmark
               x, y as part of solution path */
            sol[x][y] = 0;
            return false;

```

What is the need to reset the value of the cell located at `x,y` in the solution matrix? The value of sol\[x\]\[y\] was set to 1 only because it was a valid cell to go to. I don't understand why `sol[x][y]` has to be reset just because its neighboring cells are invalid?

**EDIT:**

I thought about this problem a little more and I realized the cell is only reset to zero when the program runs into a dead-end (0s in the maze, in this case) on its right side **AND** below it. If this cell is reset, the cell is available to be explored again. What purpose does it serve? If the program encounters this reset cell again, it will perform the same computations for this cell again and encounter the same dead-ends as before.

# Answer
> 3 votes
Your question title doesn't match your question details. You're not asking why backtracking is necessary, but you're asking why a cell marked in the matrix needs to be unmarked when backtracking.

A general technique for solving questions like this is as follows.

We'll investigate statements about the state of the program. In this case, statements about the contents of the matrix.

We start by looking at the intended outcome: the required postcondition. A postcondition is a statement that must always hold after the program terminates. In this case: what is the matrix supposed to contain after the program terminates?

The answer: the cells of the matrix must mark a path found from start to finish, if such a path exists. All cells marked 0 must be off that path, and all cells marked 1 must be on it.

Then, we figure out which invariant the program maintains in order to achieve the required postcondition. An invariant is a property that always holds: before, while, and after the program runs. In this case: which cells are supposed to be marked 1 while the program is in progress?

The answer: they are exactly the cells of the path found from the starting point to the current cell. If the program always successfully maintains this invariant, the required postcondition will always be met.

To maintain the invariant, when you add a cell to the path, it must be marked; and when you retrace a step, removing the last cell from the current path, that cell must be unmarked.

What if we don't unmark it? Then, the program will maintain a different invariant: namely, the matrix will mark exactly those cells that have ever been visited, whether they are on the current path or not. This is the invariant Hansel was trying to maintain with his breadcrumbs.

If you follow Hansel, after the program terminates, all cells ever visited will be marked, even those that aren't on the path that was eventually found (and such cells will exist if any backtracking occurred). The requirement was for only the cells on the path to be marked. Backtracking can actually occur, so the program will no longer always be doing what it's supposed to do: it will no longer meet its required postcondition.

---
Tags: algorithms, dynamic-programming, backtracking, maze
---


# Question
Title: Continue on: Prove that $BPP^{BPP} = BPP$
> regarding the following post: Prove that $BPP^{BPP} = BPP$

Let $L\in BPP^{BPP}$, by definition $BPP^{BPP} =\bigcup\_{O\in BPP}BPP^O $, therefore there exists a language $A\in BPP$ such that $L\in BPP^{A}$.
This means that there exists a $\mathsf{PTM} $ $M^{A}(x,r)$ such that $\mathbb{P}\_{r}(M(x,r)\neq L(x))\leq \frac{1}{3}$, and $M^A$ runs in polinomial time.
In addition, since $A\in BPP\_{\[\frac{1}{3},\frac{2}{3}\]} \subset BPP\_{\[2^{-n},1-2^{-n}\]}$, there exists a $\mathsf{PTM} $ $M'(x,r)$ such that $\mathbb{P}\_{r}(M'(x,r)\neq L(x))\leq 2^{-n}$, and $M'$ runs in polinomial time.
I defiened a $\mathsf{PTM}$ $N$, that on input $x$ does the following:
Simulate $M^A$ on $x$ and every time we need to do an orcale quarey $\alpha\_i$, we would simulate $M'$ on $\alpha\_i$ and the answer to the query would be the answer of $M'$.

I understand why $N$ runs in polynomial time, but I was stuck in the probabilistic analysis.
This is what I have so far:
If $x\in L$ then $N$ answer correctly iff $M^A$ answer correctly and $M'$ answer correctly about every query, therefore I got:
$\mathbb{P}\_{r}(N(x,r)= 1)= \mathbb{P}\_{r}(M(x,r)= 1)\mathbb{P}\_{r}(\forall i, M'(\alpha\_i,r)$is correct$)\geq \frac{2}{3} \prod\_{i}(1-\frac{1}{2^{|\alpha\_i|}}) $

How can I prove from here that $\mathbb{P}\_{r}(N(x,r)= 1) \geq \frac{2}{3}$?
Would appreciate your help:)

# Answer
> 1 votes
Your BPP algorithm makes polynomially many queries to the BPP oracle, and assuming that all these queries are answered correctly, has error probability at most $1/3$, say.

In order to simulate this algorithm without appealing to the oracle, we replace each oracle call with the BPP algorithm itself. By repeating the BPP algorithm polynomially many times, we can reduce the error probability of each oracle call to $2^{-n}$, say. The union bound then implies that all oracle calls are answered correctly with probability $1-o(1)$, and so the entire algorithm has error probability at most $1/3+o(1)$, which suffices to put the language in BPP.

---
Tags: complexity-theory
---


# Question
Title: Definition of the state of an object in OOP
I need a concise definition of the "state of an object" in object-oriented programming (for a paper).

For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find one. All the papers I found were mostly general papers on object-oriented programming and they didn't define the state of an object.

I am unsure, but my best guess is something like: *The state of an object is defined by the state of the instance variables of the object.*

I am searching for a definition of the state of an object and/or a reference on the topic.

(btw, could I refer to the concept as "object state" or is this uncommon?)

# Answer
You can take a look to (and cite) the book "Object-Oriented Analysis and Design" by G. Booch:

> ... An object is an entity that has state, behavior, and identity. The structure and behavior of similar objects are defined in their common class. The terms instance and object are interchangeable.
>
> We will consider the concepts of state, behavior, and identity in more detail in the sections that follow. ...

And there is a whole subsection that describes the concept of **state**:

> ... From this example, we may form the following low-level definition.
>
> The state of an object encompasses all of the (usually static) properties of the object plus the current (usually dynamic) values of each of these properties ...
> 11 votes

# Answer
You would also want to keep in mind that the state of an object is an "abstract" entity, as determined by what is observable by the methods. For instance, an object that implements a hash table has as its state, the *collection of values* stored in the hash table, not all the internal representation details.
> 3 votes

# Answer
IBM has a glossary that defines the word "state" in several different definitions that are very similar to one another. They don't specifically state that they are related to Object Oriented Programming but one can extrapolate and use them in that context.

> Def 3: A stage in the lifecycle of an object that identifies the status of that object.
>
> Def 5: A condition or situation during the life of an object during which it satisfies some condition, performs some activity, or waits for some event.
>
> Def 8: An object's characteristic that is manifested in its public and private data members, and can be divided into two categories: essential state and non-essential state.
>
> Def 9: In a business state machine, one of several discrete individual stages that are organized in sequence to compose a business transaction.
>
> Def 10: A condition in which the circuit remains until application of a suitable pulse.

Webster's New World College Dictionary defines 'state' as:

> A set of circumstances or attributes characterizing a person or thing at a given time; way or form of being: condition

The common denominator of all these is time. State changes as time progresses. That is the nature of variables. If someone were to ask, "What is your current state?" You could say today that you are married and tomorrow you could be single.

Considering all these definitions one can extrapolate that 'state' is the way that an object exists at a particular point in time determined by the values of its attributes, namely it's properties/variables.

I don't think it gets any simpler than that.
> 2 votes

# Answer
The term ‘**state**’ may be used in various senses, which may not even all be susceptible of a precise definition. It was therefore important that you include a definition in your paper, to make quite clear how *you* were using the term. In the following I do not offer a unique definition of the state of an object but rather try to sketch a number of ways of thinking about it, which may be appropriate in different contexts.

First, however, you need to think what you mean by ‘**object**’: are you thinking about a conceptual object, i.e. some entity you are trying to model, or about an instance of a class in a specific programme; perhaps you also want to think about the state of a variable which could at different times refer to different objects or about a system, maybe as accessed via a certain user interface.

Part of the difficulty in defining the state of an object in OOP is that when we model entities in a particular language, that language often does not permit us to distinguish object attributes which are conceptually part of the same entity from others that are not. For example, a linked list of `Car` will consist of a number of `Link`-objects, which contain pointers to the next (and maybe previous) `Link` although conceptually the list is a single object; the links may also be embedded in `Car`-objects or contain pointers to them, but in this case the linked objects are conceptually separate rather than part of the list; in a list of recent changes, hoewever, the changes may only be present in the list and considered as part of it. In these various cases we must decide whether we consider the state of one object to include that of the linked objects. Further, a `Car` may have a link to an `Registering_Authority` – we probably do not consider the state of car to change when its registering authority changes the URL of its website. Unless the implementation language does allow us to distinguish different types of link, it will not be possible make a general definition of the state of an object in terms of the language alone.

The ‘**external**’ or ‘**functional****state** could be defined as ‘how it behaves’, ee.g. how it reacts to method invocations or to a user interface. For an object as a class instance this definition depends on the type to which the object is seen as belonging: seen as a `Circle`, the colour of a `Coloured_Circle` is not visible, and hence irrelevant to its state. A difficulty with this is that ‘how it reacts’ may need to defined in terms of values returned, and these ‘values’ might be the states of other objects. One way to formalise this is to say that two states of an object are the same if all possible future executions of some system in which it is embedded result in the same mapping from inputs to that system to outputs from it. This enclosing system may be required to be a self-contained system, capable of execution independent of its environment; on the other hand, one could allow it to be as small as the object in question itself. In any case, a mathematical approach is then to define a state as an equivalence class of

The ‘**internal****state** could be defined as the state of the representation. A first attempt is apparently circular but perhaps helpful: ‘The internal state of an object is the state of its members’. Here we need to take care to distinguish significant aspects of the representation from insignificant ones: at the lowest level, the representation of an object may well include addresses of other objects, but it is unlikely to be useful to consider a change in such an address as a change in state. On the other hand, a change in the state of a cache for the result of a query, while it makes no difference to the functional state (as described above), will be important when considering performance tests.
> 2 votes

# Answer
An object-oriented system integrates the terms of code and data using the concept of an "object". An object has state (data) and behavior (code). Hence, the states of object are the instances(variables) inside the object that contains the data.
> 1 votes

# Answer
An entity that has a state and behavior is known as an object. The state represents the data (value) of an object. Suppose a bank account is an object then Account Number, Amount, etc will be the states of my bank account, and deposit(), withdraw() will be the behavior.
> 0 votes

---
Tags: terminology, reference-request, programming-languages, object-oriented
---


# Question
Title: Does undecidability ever imply unmeasurability and make a notion of probability ill-defined?
Not sure precisely how to ask this question, but I want to understand if it is meaningful to ask about probabilities when aspects of the definition might be undecidable. My curiosity extends to potential implications for definitions of entropy in physical systems. Let me try to get a little more precise about the question, and maybe someone can point me in the direction of papers or textbooks that address the topic, or has an answer themselves.

For example, imagine I have a dynamical system which can be mapped to a universal Turing machine, so there are some input settings where I can map the outputs to Halting vs not. Now some inputs are chosen at random, and I want to know the probability that the machine halts or not. Does the fact that knowing if the problem halts on the input or not is undecidable imply that the a probability measure is ill-defined in this case? Are there any implications for probability of input or output in such a case?

# Answer
The space of possible inputs of a Turing machine is countable, so all its subsets are measurable. Same for outputs.

However, it's possible that this probability is not *computable*. In particular, you may want to look up Chaitin's constant. It isn't *exactly* what you are talking about, but closely related.
> 1 votes

# Answer
You might never be able to know if a turing machine halts or does not halt for an input. It still either does halt or does not. Thus it depends on other things if the probability that the turing machine halts for a specific distribution of inputs is well defined; not on actually knowing if it halts.

There are no implications for the probability itself, other than that you are unlikely to ever know what the probability is. To put it another way, think about betting on the turing machine halting. If you are able to determine the random input according to the distribution, then there will be a winner. You just do not know who it is and thus are unfortunately not able to settle the bet.

Another analogy is a bet on an event that everyone is unable to observe. It either will have happened or not. There will be a winner. You just do not know who it is...
> 1 votes

---
Tags: complexity-theory, probability-theory
---


# Question
Title: Show that term cons works by showing all beta reductions
I'm new to functional programming.

So the terms cons appends an element to the front of the list. Where cons ≜ λx:λl:λc:λn: c x (l c n).

How should I go about proving that cons works correctly using beta reduction for a sample function. For example reducing cons 3\[2,1\] to \[3,2,1\]? Is there a formula like for the artihmetic operations in lambda? I'm a bit confused on how to approach this comapred to a arithmetic operation (i.e. addtion or multiplication).

Thanks.

# Answer
$\[3,2,1\]$ is just syntactic sugar for $\mathsf{cons} \\, 3 \\, (\mathsf{cons} \\, 2 \\, (\mathsf{cons} \\, 1 \\, \mathsf{nil}))$. $\[3,2,1\]$ is $\mathsf{cons} \\, 3 \\, \[2,1\]$ by definition of the $\[\ldots\]$ notation.

Because $\mathsf{cons}$ is part of the definition of lists, it isn't meaningful to ask whether $\mathsf{cons}$ is correct on its own. The meaningful question is whether the definition of lists is correct as a whole. (More precisely, that's the definition of an encoding of lists in the lambda calculus.) Another way to look at it is that the goal isn't to prove that the definition of `cons` is *correct*, but that it's *consistent* with the rest of the definition of lists.

There are several, equivalent ways to define lists as an abstract type. Lists are an *abstract type*, defined by a number of functions and properties involving these functions. Lists are an abstract *data* type, so the functions can be classified into three groups: *constructors* (which build “bigger” lists from smaller lists and other stuff), *destructors* (which “break down” lists into smaller lists and other stuff) and other functions which can be built out of constructors and destructors. Any simple definition of lists uses two constructors: $\mathsf{nil}$ which is the empty list, and $\mathsf{cons}$ which takes two arguments, an element and a list, and returns a new list. The “most fundamental” (and easiest to reason with, but not easiest to understand) definition uses one destructor $\mathsf{case}$, and satisfies the following equations for any terms $f$, $g$, $h$, $t$ such that $t$ is a list: $$ \begin{align} \mathsf{case}\\,\mathsf{nil}\\,f\\,g &= f \\ \mathsf{case}\\,(\mathsf{cons}\\,h\\,t)\\,f\\,g &= g \\, h \\, t \\ \end{align} $$ An encoding of this abstract type in the lambda calculus is the definition of three lambda terms $\mathsf{nil}$, $\mathsf{cons}$ and $\mathsf{case}$. Proving the correctness of this encoding means proving that the equation above holds.

Another, equivalent, definition of lists uses three destructors $\mathsf{empty}$, $\mathsf{head}$ and $\mathsf{tail}$ with the following equations (which presuppose the existence of booleans) for any terms $h$, $t$ such that $t$ is a list: $$ \begin{align} \mathsf{empty}\\,\mathsf{nil} &= \mathsf{true} \\ \mathsf{empty}\\,(\mathsf{cons}\\,h\\,t) &= \mathsf{false} \\ \mathsf{head}\\,(\mathsf{cons}\\,h\\,t) &= h \\ \mathsf{tail}\\,(\mathsf{cons}\\,h\\,t) &= t \\ \end{align} $$ An encoding of this abstract type in the lambda calculus is the definition of five lambda terms $\mathsf{nil}$, $\mathsf{cons}$, $\mathsf{empty}$, $\mathsf{head}$ and $\mathsf{tail}$. Proving the correctness of this encoding means proving that the equation above holds.
> 2 votes

---
Tags: lambda-calculus, functional-programming, haskell
---


# Question
Title: Greedy algorithm for subset sum on powers of 2
I have some $n$ numbers which are powers of $2$, say $a\_1,a\_2,a\_3,\ldots,a\_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after that equal to *num*.

I have following algorithm which I am sure will work, by a lot of arguments and verification, but I am not able to prove it:

1. We sort the array.
2. Initialize another variable *temp* to $0$.
3. We traverse from highest element to lowest element.
4. If *temp*\>*num* then subtract $a\_i$, else add $a\_i$. If in the end *temp*=*num* then it's possible to assign signs such that we can make *num* out the array, otherwise it is not possible.

How to prove that the algorithm works?

# Answer
> 2 votes
You can prove the algorithm using induction. In order to prove by induction, your main statement would be: Let $s\_n$ be the (correct) sign of $a\_n$ (if it exists), then the algorithm trying to find $s^\*\_1,\dots,s^\*\_{n-1}$ such $\sum\_{i=1}^{n-1} s^\*\_ia\_i=num-s\_na\_n$ is correct (by induction assumption). Then, we only need to show that the algorithm chooses $s^\*\_n=s\_n$ and then we would get $\sum\_{i=1}^n s^\*\_ia\_i=num-s\_na\_n+s^\*\_na\_n=num$ as required.

Now the tricky part comes: how can we prove that the $s^\*\_n$ the algorithm chooses is indeed correct? We want to split this part into two cases:

* $num\ge0$, and assume towards contradiction $s\_n\neq 1$, i.e only $s\_n=-1$ gives a valid solution (there may be multiple solutions, so beware of saying there is only one such $s\_n$). Then we need to have $\sum\_{i=1}^{n-1}s\_ia\_i = num+a\_n$. Since we are dealing with only powers of $2$, and $a\_n$ is the highest value, then there must be some values whose sum (when summed with the appropriate sign) is **precisely** $a\_n$ (and this is because $a\_n$ is also a power of 2, if you want a complete proof to this statement, think about the numbers as binary numbers with only one "1" in them and the rest are "0"s), now we can "flip" the sign of those values, and we would get $\sum\_{i=1}^{n-1}=num-a\_n$ (since their sum is $a\_n$, the effect of flipping their sign is like subtructing $2a\_n$) and then by choosing $s\_n=+1$ we get $\sum\_{i=1}^n s\_ia\_i=num$, in contradiction to our assumption.
* $num \< 0$, we get that $s^\*\_n=-1$, and by flipping all of the signs as well as the sign of $num$ we get $s^\*\_n=1$ for $num\>0$, and notice this is the same as the first case.

---
Tags: algorithms, greedy-algorithms, binary
---


# Question
Title: In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3?
The paper is available here: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

The 1st paragraph of lemma 3's proof says

In other words,if event e is applicable to config C,and E is any config reachable from C without applying e,then e is applicable to E.

I can follow the whole proof except the above claim. In real,practical systems, the claim isn't necessarily true. Here is an example:

suppose process p has a code fragment like this:

```
open 2 udp sockets,f1 and f2,respectively,in nonblocking mode

s1: read a message m from f1，depending on m,do some local processing,then send a finite set of messages to other processes //m could be null

s2: read a message m' from f2，depending on m',do some local processing,then send a finite set of messages to other processes //m' could be null

```

The label s1 and s2 in the code are steps("In one atomic step, a process can attempt to receive a message, perform local computation on the basis of whether or not a messagewas delivered to it (and if so, which one), and send an arbitrary but finite set of messagesto other processe",quoted from the final paragraph of page 2 of the paper).

Use C and E to denote the system config when process p's program counter was pointing to s1 and s2,respectively. Obviously,E is reachable from C. Suppose another process q sent udp datagrams m1 and m2 to sockets f1 and f2,respectively,right before the system reached config C. Therefore,in config C,events (p,m1),(p,null) are both applicable.Suppose (p,null) was applied in config C,making the system reach config E.Obviously,event (p,m1) is not applicable in config E,because process p was unable to read socket f1 in config E.

Now we've seen (p,m1) was applicable in config C, config E was reachable from C, and along the path from C to E,(p,m1) was never applied, but (p,m1) was not applicable to E,violating the claim in lemma 3's 1st paragraph.

# Answer
> 1 votes
The crucial understanding here is the notion applicability of an event in some configuration versus the effect of applying the event to that configuration.

If an event e applies to configuration C, it follows that e applies to all C, where C is the set of all configurations reachable from C (all admissible extensions of C). This is a simple consequence of the model assumptions. If I can theoretically receive e now, and e can be delayed indefinitely, then I can apply e at any point in the future, perhaps having applied e', e'', and so on.

There is a myriad of conceivable scenarios where, in practice, either e will not be applied by the program (because the program counter has advanced beyond the point where this is possible, as per your example) or where the message in e will be rejected by the program because of some other condition (i.e. internal state that forbids the processing of e). An example of the latter is the receipt of phase 1a and 2a messages in Paxos: they may be silently discarded by an acceptor that has already promised a higher ballot number.

Now we come to the notion of effect, which was omitted from FLP. (One of the reasons that FLP is obscure.) Applying e in some configuration does not imply a measurable transition. A process p could conceivably pop a message from its receive queue and discard it immediately. FLP does not forbid this, provided p behaves deterministically at all times and does not rely on the notion of time. Perhaps, p has received some other message m', which has 'locked out' m, so to speak; ergo, the late delivery of m has no measurable effect on p. This is entirely possible.

The reasoning behind FLP is to only induce a contradiction. If applying e to any configuration in C results in a configuration in D, and if we can prove that D does not solely comprise univalent configurations, then we have shown that there is an ever-admissible schedule that spans bivalent states. Lemma 3 does not state that C and D are disjoint: some configurations in C may conceivably be in D. In the case where applying e to some state C' in C has no effect, then C' is in D by the assumption of the lemma.

In summary, applies simply means that an event may be delivered. It does not mean that it is acted upon in a transition-inducing way.

---
Tags: algorithms, distributed-systems, consensus
---


# Question
Title: Why would we want a self-hosting compiler?
I understand that a self-hosting compiler is a compiler which can compile the code of the language that it is written in into different language but I don't understand why we would want to do that. What are the benefits (and drawbacks) of a compiler which is self-hosting?

# Answer
There's no direct technical benefit for a compiler to be self-hosting. If anything, it makes things more complicated, because you have to have a working compiler before you can compile the compiler — the bootstrapping problem. (Solved either by having another implementation of the same language — often an interpreter — or by keeping around binaries of a previous compiler version.)

Compiler writers often like the language that they're writing a compiler for. This is the primary reason why many compilers are self-hosting.

Having a compiler that compiles itself does have an indirect technical benefit: it's a litmus test. A compiler is a complex program. If the language is comfortable enough to write a program in, that's a sign that it's comfortable enough for a large class of programs. If the compiler can compile itself without bugs, that's a sign that it's in a good enough shape to compile other programs with confidence.
> 10 votes

# Answer
Think about how the *first* compiler got written, for the first programming language supported by some platform (probably a C compiler). In other words, think about writing a C compiler for a platform where there is no other compiler available for any other language.

Your only option is to write the C compiler in assembly language. But writing an entire compiler in assembly language would be incredibly painful. You'd much rather write the compiler in a high-level language than in assembly (for the same reason you'd rather write pretty much any program in a high-level language).

If you can write a self-hosting compiler, then you've achieved that. The usual way to construct a self-hosting compiler is through bootstrapping. Wikipedia has articles on both.
> 3 votes

# Answer
The first assembly language compilers ("assemblers") were written in raw machine code. Once you got the program "breathing" enough to process statements, you could build a small piece of it using V1 of the assembler. Once the assembler accepted enough of the language to be useful, you used it to build V2 to add more features, and then V3, and so on. Each subsequent development providing more functionality. Since there were no other languages, the first assemblers had to be self-hosting.

Now, once someone wanted to write a new programming language, they did the same thing, only they'd write it in Assembler. Once the minimal language was working, you could add more features, each language Version N compiler being built by a version N-1 compiler.

Alternatively, if there was another high-level language available, the compiler can be written using that. Nicklaus Wirth wrote the first Pascal Compiler in Fortran, a language for which the CDC mainframe has lots of support.

Once enough of the target language is present in the proposed compiler, further development can use the compiler itself. On the other hand, they may find the original language easier to write a compiler using, or there may be resource limitations which means you can't write the compiler in its own language. The Gnu Compiler Collection provides "frontends" that translate a particular language into the symbols that the backend uses, which means any frontend to compile some other language using the GCC toolchain pretty much has to be written using c or c++, depending on what the backend uses.

The advantage to self-hosting is it reduces the number of languages the compiler writers have to know to two: the machine's assembly language (or object code) and the language of the compiler. If the compiler is not-self hosting, then they also need to know a third language: the language the compiler source is written in.

The only disadvantage to self-hosting I can think of is if the computer you're using does not have a compiler for the language you're writing it for. On the other hand, that may be the reason they wrote the compiler in the first place.
> 0 votes

---
Tags: compilers
---


# Question
Title: Using singly linked list instead of a doubly linked list?
Are there advantages of implementing a singly instead of a doubly linked list **other than space**?

# Answer
> 7 votes
Other than saving space, the first advantage I can see for singly linked lists over doubly linked lists is to avoid having to update two links instead of one when you modify the list, when adding an element for example.

Of course, one might say that you can always ignore the second link, but in that case, it is no longer doubly linked, but only an unused field.

What might also be seen as an advantage is that singly linked list are necessarily consistent, though possibly wrong when there are bugs in the program. Doubly linked lists can end-up having inconsistent links forward and backward. But it is debatable which of the two cases, if any, is an advantage.

update:

I had tried to see some impact on garbage collection, but found none. Actually, there is one when storage reclamation is done by reference counting, as reference counting is defeated by loops, and doubly linked lists contain loops. Singly linked list escape the problem. Of course, there are ways around it for doubly linked lists, such as the use of weak pointers, or programmable reference counting as part of data abstraction.

# Answer
> 4 votes
Yes. Singly linked lists are easier to work with in highly concurrent situations, because there's less data to keep consistent.

For example, suppose you want to append a lot of items to a linked list in a wait-free way. It's okay if consuming the items is not wait free, but producers absolutely must not block no matter what the other threads are doing.

With a singly linked list you can just do:

```
var newNode = new Node(someValue);
var prevNode = Interlocked.Exchange(ref _insertionNode, newNode);
prevNode.next = newNode; //note: next is volatile; this is a write-release

```

Easy! Guaranteed progress for every producer. Produced nodes may not be immediately visible from the head of the list (a previous producer may have yet to update the `next` pointer of the node it got), but they eventually will be.

With a doubly-linked list, you need CAS loops and other try-retry-retry-fix-up sorts of constructs. It's a lot easier to make a mistake, so I won't try to just zip off an example.

# Answer
> 0 votes
Single-link lists are easier to work with, and in many cases are adequate for the problem, but any application requiring moving both ways on the list requires a double-linked list. Presuming you were writing a text editor where each line was a dynamically generated string (so you don't waste tons of memory allocating strings much larger than any specific line normally is), in order to move, say, up to the previous line, or up or down a screen, you'd have to be able to quickly traverse the pointers to the next/previous line (or page/screen) in memory.

Also, a double-linked list does not have to be a loop. Each entry has a "prev" and "next" pointer, prev pointing to the prior (previous) entry, next pointing to the next one. The top of the list has a null prev pointer, the last one has a null next pointer.

---
Tags: data-structures, linked-lists
---


# Question
Title: I don't get why the time complexity of insertion on a linked list is O(1)
I was watching the algoritmhs course by mycodeschool and he said that when we add a new item on a given position the worst case would be $O(n)$. Everywhere I look says insertion is $O(1)$... Now I understand that insertion itself might be $O(1)$, but if I have the following interface (this is something I made up, not a real thing I'm working):

```
insertAtIndex(any item, int index)

```

Would this be $O(n)$? Since I will search $O(n)$ and then insert $O(1)$?

Thanks!

# Answer
> 2 votes
That is correct. There is no random indexing in a linked list so you will have to traverse it from the start until you reach the right index, requiring a $O(n)$ search. After that you have $O(1)$ reference/pointer bookkeeping for the insertion operation.

---
Tags: time-complexity
---


# Question
Title: Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations
Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations. Positions are numbered from 1 to 10^11. Every 3rd bit of a is equal to 1 (in other words bits number 3,6,9 and so-on), every 7th bit of b is equal to 1, every 4th bit of c is equal to 1, every 5th bit of d is equal to 1. The task is to determine the number of 1 bits in a ⊕ b ⊕ c ⊕ d, where ⊕ is bitwise XOR operation.

# Answer
The value of $(a \oplus b \oplus c \oplus d)\_i$ depends on whether $i$ is divisible by $3,4,5,7$, and in particular, by $i \bmod 3\cdot 4\cdot 5\cdot 7$. In order to complete the calculation, you need to know, for each $j \in \\{0,\ldots,3\cdot 4\cdot 5\cdot 7 - 1\\}$, how many indices $i \in \\{1,\ldots,10^{11}\\}$ satisfy $i \equiv j \pmod{3\cdot 4\cdot 5\cdot 7}$.
> 0 votes

---
Tags: logic, binary
---


# Question
Title: Using the pumping lemma for a specific language
Please help me with the following question:

> Define the language LONGERB to be the set of strings over $\\{a,b\\}$ where the longest substring containing only $b$’s is strictly longer than the longest substring containing only $a$’s (e.g. $aabaabaaabbbba$ is in LONGERB because the longest substring containing only $b$’s has length 4 while the longest substring containing only $a$’s has length 3, while $ab$ is not in LONGERB). Let $n$ be the integer from the pumping lemma. How many of the following strings can be used in a pumping lemma proof that LONGERB is not regular?
>
> (i) $abab^{n+1}$ (ii) $a^nb^{2n}$ (iii) $a^{10}b^{10}$ (iv) $a^nb^n$

The answer that has been given in the book is 3 (Options 1,2, and 4). But my doubt is, that the 4th option doesn't belong to the given language as there is an equal number of $a$'s and $b$'s in this option. So, according to me the correct answer should be 2 (Options 1 and 2 only).

Please give a proper reason for each of the four options, why it can or cannot be used to prove that the given language is not regular.

# Answer
* Option 1: the word is in the language and it is of length $\geq n$, yet there is no guarantee that pumping it yields a contradiction. That is, the word can be used in the pumping lemma, **but its not a good choice for proving non-regularity**. Indeed, if $\text{LONGERB}$ is regular, then we know that there is a partition of $abab^{n+1}$ to three words, $xyz = abab^{n+1}$, where $|xy| \leq n$, $|y|\> 0$, and $xy^iz\in \text{LONGERB}$ for every $i\geq 0$. Thus, if for example $y = ba$, then $xy^iz$ is indeed in $\text{LONGERB}$ for every $i\geq 0$ \- so we cannot reach a contradiction to the assumption that $\text{LONGERB}$ is regular.
* Option 2: the word is in the language and it is of length $\geq n$. Clearly it is good for pumping in the sense that it can be pumped for some $i$ so that $xy^i z \notin \text{LONGERB}$ \- this is an easy exercise and the details are left to you.
* Option 3: the word is of constant length that does not depend on the pumping constant $n$, so there is no guarantee that it is of length $\geq n$, so the pumping lemma says nothing about this word. Thus, we cannot use it to apply the pumping lemma on any language with a pumping constant $n$.
* Option 4: you're right, the word cannot be used when applying the pumping lemma directly on the language $\text{LONGERB}$. However, it can be used to prove the non-regularity of $\text{LONGERB}$ indirectly by applying the pumping lemma on the language $\overline{\text{LONGERB}}$ which is the language of the words over $\\{a, b\\}$ where the longest substring containing only $b$’s is *equal or shorter* than the longest substring containing only $a$’s. Indeed, assume by contradiction that $\overline{\text{LONGERB}}$ is regular. If you consider the word $w = a^n b^n$, it is longer that $n$ and it is in the language $\overline{\text{LONGERB}}$. Then, there is a partition $xyz = a^nb^n$, where $|xy| \leq n$, $|y|\> 0$, and $xy^iz\in \overline{\text{LONGERB}}$ for every $i\geq 0$. If you pump with $i = 0$, you get a contradiction. (BTW, I implicitly assumed that both a language and its complement have the same pumping constant $n$. This assumption is okay. Can you tell why?)
> 1 votes

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Ordering of operations in a DAG of git commits
Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug

## Summary of the current algorithm and shortcomings

git-bug is a distributed bug-tracker that embed in `git`, the distributed version control system. To do so, bugs are stored in the native git data structure (commits and branches). Each bug has its own branch and adding commits to it will evolve the bug state. This allows using git as both a database and a transport, in the sense that users can push/pull those branches to distributes updates and collaborate with each other.

More details can be found in this document: https://github.com/MichaelMure/git-bug/blob/master/doc/model.md

Now to deal with the distributed nature of this system and allow merges, the state of a bug can't be stored as-is. Instead, it's stored as an *ordered* series of operations: adding a comment, changing the title ... When reading a bug, the final state is "compiled" by applying those operations in order to an originally empty state.

I believe (but don't quote me on that) that this is a form of Operational Transformation (OT).

In reality, multiple operations can be stored in a single git commit but for the purpose of this conversation, let's assume that **one git commit stores exactly one operation**.

To make my life a bit easier at the beginning of this project, I reduced the complexity of this problem by imposing that **the series of commit holding the operations would have to be linear**, which make the ordering of the operations trivial: the order of the commit implies the order of the operations.

This purely linear restriction has a major implication: when fusing\[1\] together with two git DAG when doing a `git pull`, the equivalent of a `git rebase` has to be used. The commits of one diverging branch are reapplied on top of the other, which means that the data structure is not actually immutable. Not only this is problematic if commits are signed, but I'm also suspecting this can prevent the commits to reach a stable ordering when there is no central server acting as "source of truth". If three users A, B, and C are pulling and rebasing commits in a cycle A-\>B-\>C-\>A, I suspect they will never reach a stable ordering.

Another way to do things would be to use the equivalent of `git merge`: the diverging branches are fused together with a new commit having both branches as parents and we end up with a DAG. Although and this is important, in the normal git behavior this merge commit holds the fused state. For git-bug, each operation is disconnected from the others, so the merge commit would hold no fused state, just that the branches fused.

## The actual question

**I'm looking for an algorithm capable of doing this ordering of commits in a git DAG using git merge, in the most stable way possible.**

* using git merge: git merges are allowed, possibly rebase as well if necessary
* most stable way possible: in a perfect world, the operations should be ordered by their real-time creation. Obviously, this is not fully possible in a distributed system, so the goal is to get a logical order as close as possible, despite concurrent editions and merges. Thankfully, bugs in a bug-tracker are slightly malleable and will retain the user's intent even if the ordering is slightly wrong.

As you may have guessed, I'm a bit out of my depth here so, short of an actual algorithm, any pointers for theoretical ground or possible solutions would be helpful.

## Things I considered

* storing in each operation/commit the reference of the ancestor at the time of the creation
* using some form of logical clock, stored in each commit
* some sort of topological ordering
* a combination of those?

\[1\]: I'm avoiding "merge" here to avoid confusion, it's not the git merge.

# Answer
Assuming I understand the semantics:

* You cannot concurrently Create the same bug report twice, so that's not a problem
* Title could be a Last-Writer-Wins (LWW) register. If two users perform SetTitle concurrently, the one with the highest timestamp remains.
* You could use a CRDT set for comments. This way users can add and remove an arbitrary number of comments. With sets, a comment constitutes an element of the set; comments are unordered; a comment can be deleted. If a deleted comment cannot be revived, use 2Pset; otherwise use AWset.
* A more interesting approach for comments is to provide relations between comments, e.g., a comment may respond to an earlier comment. In this case a CRDT DAG or tree would work, e.g., WOOT or RGA. (RGA is ostensibly a list, but in fact it's a linearised tree.)
* If you want to allow concurrent EditComment's, the text of a comment could either be an edit-string CRDT, e.g. RGA, or more simply a multi-value register (MVR).
* For Tags, attach a CRDT set (AWset would be ideal) to a report, where users can add/remove arbitrary tags.
* Status: not sure what this means. You might again use AWset, or a custom semi-lattice if status always progresses in the same direction (e.g. from Open to Closed, never re-opened).

Does this help?
> 1 votes

# Answer
What exactly is an operation in your model? If two concurrent operations commute, then any topological sort of your DAG will give the same result (cf. Strong Eventual Consistency). If two concurrent operations are independent of one another it's likely they commute (or can be made to commute); otherwise, if there is a deterministic way to prioritise them, then do that (as in CRDTs). I can't be more specific without understanding what an operation is.
> 0 votes

---
Tags: distributed-systems, dag, clocks, topological-ordering
---


# Question
Title: Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph
Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$?

The best prime complexity I have found is $O(|V|^2)$, and the complexity of the Kruskal algorithm is $O(|E|\cdot \log(|E|))= O(|V|^2 \cdot \log(|V|))$.

Any ideas for how to improve the time complexity so that we get something more efficient than $|V|^2$?

# Answer
Since it is a complete undirected graph, the number of edges are $\Theta(n^{2})$, where $n = |V|$. In order to find the MST, you must find the edge of **minimum weight** among all the given edges since it is always a part of the Minimum Spanning Tree. Since, the lower bound of finding the minimum among $N$ elements is $\Omega(N)$. Therefore, you can not do better than $\Omega(n^{2})$ if the graph is complete.
> 0 votes

---
Tags: graphs, time-complexity, minimum-spanning-tree, prims-algorithm
---


# Question
Title: Conditional probability in Expectation Maximization (EM)
I've got the following equation:

$p(j = 1 | x, \theta) = \frac{p(j=1,x | \theta)}{p(x | \theta)}$

Why does it hold? Or maybe, how do I use Bayes Theorem in this case, i.e. if we do not only have $p(j = 1 | x)$ but $p(j = 1 | x, \theta)$?

# Answer
I think I found the solution.

In general we have: $$p(\theta,x,j=1) = p(j = 1 | x, \theta) \cdot p(x,\theta) \\ \Leftrightarrow \frac{p(\theta, x, j=1)}{p(x, \theta)} = p(j=1| x,\theta)$$

By using this, we get: $$p(j = 1 | x, \theta) = \frac{p(\theta, x, j=1)}{p(x,\theta)} = \frac{p(j=1,x|\theta) \cdot p(\theta)}{p(x|\theta) \cdot p(\theta)} = \frac{p(j=1,x | \theta)}{p(x|\theta)}$$
> 0 votes

---
Tags: machine-learning, probability-theory
---


# Question
Title: Determine if the language of words with same number of 1's and 2's is context-free or not
$$L\_2=\\{w \in \\{0,1,2\\}^\* : \text{$w$ has the same number of $1$'s and $2$'s}\\}$$

I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 is pushed onto the stack, there always is a 2 to get pop it out. The 0's are what is bothering me at the moment. Do we need to include them, or we can exclude them entirely?

I would do this with pumping lemma, but we did not learn that for our class.

# Answer
> 1 votes
When it comes up to deciding if a language is context-free or not, I try the following 'roadmap' to come up with an answer.

$1.$ Try to make a CFG for the given language. If we can make a CFG, we have proved that the language is context-free.

$2.$ If step $1$ did not work out, there is a probabilty that the language is not context-free. So try proving that the given language is not context-free by the pumping lemma.

$3.$ If I fail to prove that language is not context-free, I probably failed to make a CFG so I start to make a PDA.

*Remark*: This is my way to (dis)prove context-free languages, there are many other ways to do this. So don't take this as a general step-by-step plan.

In your example, we need to (dis)prove $$L\_2=\\{w \in \\{0,1,2\\}^\* : \text{$w$ has the same number of $1$'s and $2$'s}\\}$$

So when we think of a CFG, we should consider that whenever we add a $1$, we should also add a $2$ (and vice-versa), as $|1| = |2|$. We also know that the language can be empty and that the number of $0$'s do not matter.

So

$$S \rightarrow \epsilon $$ $$S \rightarrow 0S$$ $$S \rightarrow 1S2S$$ $$S \rightarrow 2S1S$$

As we were able to make a CFG, we can say that the language $L\_2$ is a CFL.

# Answer
> -1 votes
The above language is context free,whenever we encounter any symbol in input we can push it into stack or pop something out of stack or we simply skip that symbol according to definition of pda,so here the condition is that number of 1's and 2's must be equal so we design pda in such a way that when ever we encounter 1 we push that into stack and whenever 2is encountered we pop 1 out of stack and when we encounter 0 we simply skip it at the end stack will be empty and final state is reached if 1's and 2's are equal otherwise they halt at non final.

---
Tags: finite-automata, context-free
---


# Question
Title: Randomize List with guaranteed Index Change
I usually post on Stackoverflow, but I got stuck with a problem which I think fits better here and I hope someone can help me. The task ist pretty simple:

**Shuffle/Randomize an array/list**

*conditions*:

1. each Index has to change; an Item which was at index 0 before the shuffle has to be at an index != 0 after the shuffle
2. all possible resulting permutations which satisfy the first condition should be distributed equally

I am unable to find a satisfying solution. Brute force (shuffling the array with Fisher-Yates until first condition is met) obviously works but is not a solution I am looking for. Brute Force with an array with four elements resulted in following number of permutations (which is roughly distributed equally) for one million tries: `[111467, 111172, 111497, 111047, 111114, 111053, 110699, 110655, 111296]`

Another thing I tried was something like this:

1. iterate through the array object by object and randomly choose a new index for the object
2. the randomly chosen index must not have been chosen before and must not be same as the original index
3. if the last element would fall on its original index, swap the last element with a random other element

Using this approach, the distribution looks really bad: `[74166, 110734, 83581, 129486, 83210, 101904, 111305, 111235, 194379]`.

In theory, there must be a better solution than brute force but unfortunately everybody I asked so far (including google) didn't have a solution, or just had another non uniform solution comparable to my second approach.

Can anyone help me please? I would appreciate it a lot.

# Answer
**NOTE: updated (before it had low=i+1 always, this missed some valid results, and missed the extra check needed for the last index)** \**NOTE: update 2 - randomize order to ensure uniformity \**

Consider the following approach:

```
loopIndex[0..n-1] = permute([0..n-1])
index[0..n-1] = [0..n-1] // track indices
for i=0..n-2
   idx = loopIndex[i]
   if index[idx] == idx
      low = i+1
   else low = i
   swapIdx = random(low,n) // random(start,end) --> start <= i < end
   swapElement(index, idx, loopIndex[swapIdx])
   swapElement(array, idx, loopIndex[swapIdx])
finalIdx = loopIndex[n-1]
if index[finalIdx] == finalIdx
   finalSwapIdx = random(0,n-1)
   swapElement(index, finalSwapIdx, finalIdx)
   swapElement(array, finalSwapIdx, finalIdx)

```

**PROOF NOT YET UPDATED** Note the following:

1. loopIndex is used to give a random ordering on which we process the elements. This ensures that any non-uniformity is "smoothed out".
2. If an index $j$ is selected as swapIdx then that element is swapped to a place where it's not processed again in the loop.
3. If an index $j \< n-1$ is never selected as swapIdx then when $i==j$ the element will be swapped out from $j$ and never can return to $j$.
4. The final check handles the case where the final element was never selected. In this case, we swap between $n-1$ and some other random element.

Proof of uniformity by induction on the index - Let $p(j,k)$ be the probability that after completing $i=j$, the element at index $j$ is the element that originally had index $k \neq j$ (clearly $p(j,j)=0$). Then $p(0,k)=\frac{1}{n-1}$ clearly.

Assume then that the statement holds for all $j \leq t$ and we now prove for $j=t+1$.

$p(t+1,k)$ is the probability the element with original index $k$ is not in the first $t$ elements at step $i=t+1$, times the probability that $k$ is swapIdx now. By the assumption, this is then: $$ \left(\frac{n-2}{n-1}\right)\left(\frac{n-3}{n-2}\right)\dots\left(\frac{n-t-1}{n-t}\right)\left(\frac{1}{n-t-1}\right) = \frac{1}{n-1} $$ (Note that there is a minor difference between $k \leq t$ and $k \> t+1$. For the former, it must not have been selected as a swapIdx for $j \neq k \leq t$, and it must not have selected $t+1$ as its swapIdx. For the latter, it must not have been selected as a swapIdx. The result though is the same in terms of the math).
> 1 votes

# Answer
## Algorithm

There is an idea based on subfactorial formula `!n = (n-1)(!(n-1) + !(n-2))`.

There are two ways to generate derangement of size `n`:

1. Generate derangement of size `n-1`, append `n`-th item, swap `n`-th and random item in range `[1, n-1]`.
2. Generate derangement of size `n-2`, get `i = random[1, n-1]`, increment all values `>= i` in the derangement, insert value `i` to `i`-th place. The modified permutation is not derangement any more, but the only item (`i`) is on his place. Append `n`-th item, swap `n`-th and `i`-th items. The result is derangement.

To generate derangement we select first of second way with probabilities `!(n-1) / (!(n-1) + !(n-2))` and `!(n-2) / (!(n-1) + !(n-2))`.

The only issue is that this algorithm is not linear of `n` in time. I think it is `O(n^2)` due to item insertion and increment in the second way.

## Evaluation

Below is test in Python. It runs permutation generator 1000000 times and shows number of calls to random generator, expected number of permutations of particular kind, distribution of permutations.

`MotiNK` has been added in the last moment to check it. Unfortunately it does not generate all permutations.

`Derangement` implements the idea described above. It works OK but it is quadratic. :(

`FisherYatesDerangement1` is Fisher-Yates "try and reject".

`FisherYatesDerangement2` is optimized slightly. It is possible to reject permutation early while Fisher-Yates is generating permutation.

`FisherYates` is added as a baseline. It does not generate derangements but all permutations.

```
import collections
import random

def is_derangement(a):
    for i, v in enumerate(a):
        if i == v:
            return False
    return True

# suggested by [MotiNK](https://cs.stackexchange.com/users/37884/motink)
#
# for i=0..n-2
#   swapIdx = random(i+1,n) // random(start,end) --> start <= i < end
#   swapElement(array, i, swapIdx)

class MotiNK:
    def __init__(self, n):
        self._n = n
        self._c = 0

    def next(self):
        a = list(range(self._n))
        for i in range(self._n - 1):
            j = random.randrange(i + 1, self._n)
            self._c += 1
            a[i], a[j] = a[j], a[i]
        assert is_derangement(a)
        return tuple(a)

    def count(self):
        return self._c

class FisherYates:
    def __init__(self, n):
        self._n = n
        self._c = 0

    def next(self):
        a = list(range(self._n))
        for i in range(self._n):
            j = random.randrange(i, self._n)
            self._c += 1
            a[i], a[j] = a[j], a[i]
        return tuple(a)

    def count(self):
        return self._c

class FisherYatesDerangement1:
    def __init__(self, n):
        self._fy = FisherYates(n)

    def next(self):
        while True:
            a = self._fy.next()
            if is_derangement(a):
                return a

    def count(self):
        return self._fy.count()

class FisherYatesDerangement2:
    def __init__(self, n):
        self._n = n
        self._c = 0

    def next(self):
        while True:
            a = list(range(self._n))
            if self._shuffle(a):
                assert is_derangement(a)
                return tuple(a)

    def count(self):
        return self._c

    def _shuffle(self, a):
        for i in range(self._n):
            j = random.randrange(i, self._n)
            self._c += 1
            if i == a[j]:
                return False
            a[i], a[j] = a[j], a[i]
        return True

def subfactorial(n):
    f1 = 0
    f2 = 1
    for i in range(n):
        f1, f2 = f2, i * (f1 + f2)
    return f2

class Derangement:
    def __init__(self, n):
        self._n = n
        self._c = 0

    def next(self):
        a = self._derangement(self._n)
        assert(is_derangement(a))
        return tuple(a)

    def count(self):
        return self._c

    def _derangement(self, n):
        assert n != 1
        if n == 0:
            return []
        n1 = subfactorial(n - 1)
        n2 = subfactorial(n - 2)
        k = random.randrange(n1 + n2)
        self._c += 1
        i = random.randrange(n - 1)
        self._c += 1
        if k < n1:
            a = self._derangement(n - 1)
        else:
            a = self._derangement(n - 2)
            for j in range(n - 2):
                if a[j] >= i:
                    a[j] += 1
            a.insert(i, i)
        a.append(n - 1)
        a[i], a[n - 1] = a[n - 1], a[i]
        return a

def test_generator(k, label, gen):
    c = collections.Counter(gen.next() for _ in range(k))
    m = len(c)
    print(
        label,
        f'{gen.count():10}',
        f'{k / m:10.2f}',
        sorted(c.values())
    )

for n in range(3, 6):
    print('n =', n)
    m = 1000000
    test_generator(m, 'MotiNK                 ', MotiNK(n))
    test_generator(m, 'Derangement            ', Derangement(n))
    test_generator(m, 'FisherYatesDerangement1', FisherYatesDerangement1(n))
    test_generator(m, 'FisherYatesDerangement2', FisherYatesDerangement2(n))
    test_generator(m, 'FisherYates            ', FisherYates(n))

```

Results:

```
n = 3
MotiNK                     2000000  500000.00 [499557, 500443]
Derangement                4000000  500000.00 [499959, 500041]
FisherYatesDerangement1    8986053  500000.00 [499855, 500145]
FisherYatesDerangement2    6493519  500000.00 [498982, 501018]
FisherYates                3000000  166666.67 [166124, 166291, 166399, 166842, 166971, 167373]
n = 4
MotiNK                     3000000  166666.67 [165922, 166499, 166550, 166680, 166937, 167412]
Derangement                5332446  111111.11 [110578, 110775, 111087, 111098, 111105, 111165, 111184, 111501, 111507]
FisherYatesDerangement1   10663028  111111.11 [110525, 110740, 110906, 111113, 111193, 111203, 111421, 111436, 111463]
FisherYatesDerangement2    7434896  111111.11 [110378, 110400, 111099, 111141, 111186, 111194, 111300, 111543, 111759]
FisherYates                4000000   41666.67 [41325, ..., 41911]
n = 5
MotiNK                     4000000   41666.67 [41338, ..., 42069]
Derangement                7091636   22727.27 [22449, ..., 23012]
FisherYatesDerangement1   13626165   22727.27 [22403, ..., 23004]
FisherYatesDerangement2    9344157   22727.27 [22392, ..., 23014]
FisherYates                5000000    8333.33 [8118, ..., 8632]

```
> 1 votes

---
Tags: arrays, randomness
---


# Question
Title: What does 'Describe the language of this automaton' mean?
I've been asked to do this as part of an assignment. Here is the automaton:

I understood it as describing in terms of the 5 tuples so I wrote:

The states are as follows: Q = {A, B, C}

The alphabet is as follows: Σ = {0,1}

The start state is A

The accepting state is C

The transition function is as follows:

Is this what is meant by describing the language or am I supposed to answer using different metrics?

# Answer
> 1 votes
The language of an automaton is the language *accepted* by the automaton, that is, the set of words accepted by the automaton.

Now, certainly, one way of describing the language is as the language accepted by this particular automaton. But the question is asking you to find a simpler description. Here is the set of words accepted by your automaton: $$ 01, \\ 001, 101, \\ 0001, 0101, 1001, 1101, \\ 00001, 00101, 01001, 01101, 10001, 10101, 11001, 11101, \\ \ldots $$ Can you spot a pattern?

---
Tags: finite-automata
---


# Question
Title: Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?
How is it possible to prove whether the language $\\{a, b\\}^{∗} \setminus \\{S → ε, S → aSbS\\}$ is context free?

# Answer
> 1 votes
The first step is finding a simpler description of the language generated by the grammar $S \to aSbS \mid \epsilon$.

The second step is deducing a description of the complement, which is the language you're actually interested in.

Finally, in order to show that the language is context-free, you can consult our reference question on this topic.

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


# Question
Title: Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path
**Summary**: A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain physical locations with all the pairwise distance being known and fixed. The question is how to efficiently find the best location assignment so that the total traveling distance is minimized.

**What I Have Tried**: I cannot map this problem to any other algos that I know. For example, Dijkstra is to find the path given the graph, Knapsack is to find the right combination which the order doesn't matter.

* I posted this question on Stackoverflow
* I wrote an article on my blog to describe the problem in more detail for your reference
* I wrote a script to demonstrate how to find the optimal position assignment in a brute force way for a small number of objects.

Right now, this is at a complexity I believe of O(n!) and will totally explode as we increase the number of different objects.

```
# task is a sequence of order picking
task = '1212103' # means first pick up obj1, then obj2, then obj1, ..etc.

result = []
for c in permutations(range(4), 4):
    # c contains the positions for all objects
    # (1, 0, 2, 3) means obj0 stored at pos1, obj1 stored at pos0, etc.
    res = 0

    for f,t in zip(task, task[1:]):
        pos_f = c[int(f)]
        pos_t = c[int(t)]
        # abs(...) is one oversimplief way to calculating distance between two positions
        # in a 1d space for demonstration purpose
        res += abs(pos_f - pos_t)
    result.append((c, res))

```

And the outputs are all the permutations and the total distance:

```
[((1, 2, 3, 0), 6),   # optimal position assignment #1 the yields the shortest distance
((2, 1, 0, 3), 6),    # optimal position assignment #2 the yields the shortest distance
((0, 2, 3, 1), 7),
((1, 3, 2, 0), 7),
((2, 0, 1, 3), 7),
((3, 1, 0, 2), 7),
((0, 1, 2, 3), 8),
((0, 3, 2, 1), 8),
((3, 0, 1, 2), 8),
((3, 2, 1, 0), 8),
((0, 2, 1, 3), 9),
((3, 1, 2, 0), 9),
((0, 1, 3, 2), 11),
((1, 0, 2, 3), 11),
((1, 2, 0, 3), 11),
((2, 1, 3, 0), 11),
((2, 3, 1, 0), 11),
((3, 2, 0, 1), 11),
((0, 3, 1, 2), 13),
((3, 0, 2, 1), 13),
((1, 0, 3, 2), 14),
((2, 3, 0, 1), 14),
((1, 3, 0, 2), 15),
((2, 0, 3, 1), 15)]

```

# Answer
Let us call your problem as $TD$ (Total Distance problem). Now, we will show that there is a polynomial-time reduction from the $k$-clique problem to $TD$. Note that, the $k$-clique problem is $NP-hard$ and is defined as follow:

> Given an undirected graph $G\_{C} = (V\_{C},E\_{C})$. Does there exist a clique of size $k$ in $G\_{C}$?

The reduction from $k$-Clique to $TD$ happens in the following way:

Define a complete weighted undirected graph $G = (V,E)$ such that $V = V\_{C}$ and for an edge $(u,v) \in E$, the weight $w(u,v) = \infty$ if $(u,v) \notin E\_{C}$, and $w(u,v) = 1$ if $(u,v) \in E\_{C}$. Here, the vertex set $V$ represents the set of locations and weight on an edge represents the travelling cost between two locations. A $k$ size clique can be easily stated by some object sequence $S$. For example, suppose $k = 4$, then the object sequence would be: $S = (1,2,3,4,1,3,4,2)$. Similarly, for $k = 5$, the object sequence would be: $S = (1,2,3,4,5,1,3,5,2,4,1)$. Note that, we have $n$ number of distinct objects but only $k$ of them appears in the sequence. Now, the problem instance of $TD$ consists of the graph $G$ and sequence $S$. This completes the construction.

Now, suppose $A$ is an algorithm of $TD$ that returns a correct mapping of the objects to the locations such that the total traveling cost is minimized. Now, if the traveling cost of the mapping is $\infty$ then $G$ does not have a $k$ size clique. And, if the mapping gives the finite traveling cost then $G$ does have a $k$ size clique.

The above reduction implies that $TD$ is also $NP-hard$. So, we can not expect a polynomial-time running algorithm for $TD$.

---

Note that, in the reduction, instead of setting the edge weights of $G$ to be $\infty$, you can also use finite weights but with sufficiently large values such as $|V|^{|V|}$. That would also work.
> 1 votes

---
Tags: algorithms, graphs, time-complexity, shortest-path, permutations
---


# Question
Title: printf("%d",~5); prints out -6 why is that?
I was reading the book "Computer systems: A programmer's perspective" and saw that the operator, "~", is a NOT operator. When I use it to NOT positive integers, it returns the negative of the original number plus one. Why does that happen?

# Answer
> 2 votes
That's because computers use $2$'s complement representation of negative numbers. $5$ in binary is $101$. Assume an $8$-bit architecture. Then $5$ would be represented as $00000101$. Hence ~$5$ will flip all the bits which gives $11111010$ which is the $1$'s complement of $5$. Adding $1$ to it gives you the $2$'s complement representation which the computer interprets as $-5$. Hence ~$5=11111010$ is $-5-1=-6$.

---
Tags: programming-languages, c, c++
---


# Question
Title: What algorithm do computers use to compute the square root of a number?
What algorithm do computers use to compute the square root of a number ?

EDIT

It seems there is a similar question here: Finding square root without division and initial guess

But I like the answers provided here more. Plus the person asking the similar question had the question formed in a personal way.

My question has an easier to find wording. The similar one was asked having an insight about the inner mechanics of such an algorithm and was being asked like if it was something that had not yet been solved-found.

I don't know if there is a way for a moderator to merge the two posts.

# Answer
Have a look at the paper

https://www.lirmm.fr/arith18/papers/burgessn-divider.pdf

which describes the division / square root hardware implementation in some ARM processors.

Roughly the idea: For a division unit, you can look up the initial bits of divisor and dividend in a table to get two bits of result. For double precision with a 53 bit mantissa, you repeat that 26 or 27 times and you have the result. For single precision with 24 bit mantissa, you need to repeat only 12 or 13 times. All the other bits, calculating the exponent etc., can be done in parallel.

Now what does square root have to do with division? Simple: sqrt (x) = x / sqrt (x). You get the square root by dividing x by its square root. Now when you start this division, you don't know the square root yet. But as soon as you have say eight bits and you are very, very careful, you can produce two mantissa bits per cycle. And getting the first say eight bits is not hard, since unlike a division x / y, there is only one operand involved.

The paper describes this in much more detail, and importantly describes why this is superior for example to using Newton-Raphson or similar. Note: It is superior for typical floating-point numbers with 24 or 53 bit mantissa. Since that is what is used 99.9999% of the time it is important, but for different situations things are different.
> 1 votes

# Answer
Well, this is kind of a numerical method question and it is not related to **approximation algorithm**. Anyway I think you can search for Bisection method, Newton's method (or Newton-Raphason method), there are of course other ways but this is what I remember from a course in numerical methods.

Check this textbook:

> Steven C. Chapra, and Ryamond P. Canale. Numerical Methods. 7th edition. McGraw Hill Education.
> 2 votes

# Answer
If you are not a hardware designer, then you likely use the Newton iteration method. Given an equation f(x) = 0, and an approximate solution $x\_0$, Newton iteration calculates a (hopefully) better approximation as $x\_{n+1} = x\_n - f(x\_n) / f'(x\_n)$. If we change $x = a^{1/2}$ to $x^2 = a$ to $x^2 - a = 0$, then this gives the simple formula $x\_{n+1}$ = $x\_n - ({x\_n}^2 - a) / 2x\_n$ = $(x\_n + a/x\_n)/2$.

This works well with a good initial approximation, but each iteration round includes a division, and divisions are sloooow. We therefore use a different formula: Instead of solving $x = a^{1/2}$ we solve $x = a^{-1/2}$ and multiply the result by a, which gives $a^{1/2}$ as requested.

We rearrange $x = a^{-1/2}$ as $x^2 = 1/a$, then $1/x^2 = a$ and $1/x^2 - a = 0$. Now $f'(x) = -2/x^3$, so Newton-iteration gives $x\_n - (1/{x\_n}^2 - a) / (-2/{x\_n}^3)$ or $x\_n + (x\_n - a{x\_n}^3) / 2)$ or $1.5x\_n - (a/2){x\_n}^3))$. This can be calculated using multiplications only, which is much faster than division. On a modern processor which can calculate multiplications in parallel and has a fused multiply-add operation, you calculate $r = 1.5x\_n$, $s = (a/2)x\_n$, $t = {x\_n}^2$, then $x\_{n+1} = r + s \cdot t$.

To support this, x86 processors for example have a very fast hardware instruction calculating an approximation to $a^{-1/2}$ with a relative error less than 1 / 1024, implemented using a table.
> 2 votes

# Answer
You get a completely different answer if you ask for square roots of n-bit floating point numbers for LARGE n, say n ≥ 1000 or n ≥ 1,000,000.

For large n, we usually define the time it takes to multiply two n-bit numbers as M(n). That time depends on how clever our algorithm is; what we learned in school has M(n) = O (n^2), the Karatsuba algorithm has M(n) ≈ O (n^1.58), and FFT-based algorithms run in O (n log n). Division with n bit precision can be done in not much more time, about 2 M(n).

We can use the Newton-Raphson method, iterating $x\_{k+1}$ = $x\_k - ({x\_k}^2 - a) / 2x\_k$. However, we make one critical change: If we want a result with say 1,000,000 bits precision, we don't do the whole calculation with that precision. We calculate one approximation with just enough precision so that the final iteration step will give the required precision. For example, we might calculate the second-to-last value with 500,005 or 500,010 bits of precision and then do the last iteration with full precision. But calculating ${x\_k}^2$, we know that the first 500,000 bits of the result should be identical with a, so we can save a lot of time not calculating those 500,000 bits when we already know what they are. And we don't need to calculate $({x\_k}^2 - a) / 2x\_k$ with 1,000,000 bit precision because the result is only a tiny correction to $x\_k$ so just about 500,000 bits precision are enough. (Obviously you need to analyse error bounds very carefully).

When you calculate the second-to-last approximation, you also don't need 500,010 bits of precision throughout the whole calculation; it is enough to calculate the third-to-last approximation with say 250,015 bit precision and so on. So the total time is O(M(n)) + O(M(n/2)) + O(M(n/4)) + .... The cost of the last step dominates the rest as long as M(n) ≥ O(n), so a square root with n bit precision can be calculated in time c * M(n) for c probably around 6 to 10.

If you do many such calculations, it would be worthwhile checking whether calculating an approximation to $a^{-1/2}$ would give faster results.
> 2 votes

# Answer
Thanks to @YOUSEFY in the textbook of

> Steven C. Chapra, and Ryamond P. Canale. Numerical Methods. 7th edition. McGraw Hill Education.

I found an iterative method called "divide and average" where `a` is the number in the root.

```
x = (x+a/x)/2

```

But what I still don't know is if this is the preferred way to compute it (in terms of optimization).
> 0 votes

---
Tags: algorithms, approximation, numerical-algorithms
---


title: Why is this automaton considered DFA?

text:
# Question
Title: Why is this automaton considered DFA?
So I was watching this video https://www.youtube.com/watch?v=ZjjAbFxjxLQ and the guy was explaining why the top automaton is NFA (because the initial state doesn't know what to do if the input string begins with b) and the bottom is DFA (because the initial state points to a 'dead state' if the input string begins with b):  Okay, fair enough.

But when I went on this Automaton simulator and it generated an example of a DFA for me, I got confused because its the same as the NFA example above:

It doesn't have an option for when the input string begins with b. So what's going on?

# Answer
> 10 votes
Some people in the literature (very few actually) do not consider missing transitions as *nondeterminism*, and given a DFA, they allow themselves to remove all transitions that lead to states from which we cannot reach an accepting state. The reason for that is technical, as sometimes it may simplify proofs a bit. Or it could be a matter of taste.

Intuitively, allowing missing transitions is not justified as *nondeterminism*, or *guessing* occurs only when we have a *choice*, that is, when we have at least two different transitions $\langle q, \sigma, s\_1 \rangle$ and $\langle q, \sigma, s\_2 \rangle$, going out from the same state $q$, and are labeled with the same letter $\sigma$. So, DFAs with missing transitions, or more accurately NFAs such that for every state $q$, and letter $\sigma$, it holds that $|\delta(q, \sigma)|\leq 1$, are considered *deterministic* in the sense that they have at most one run on a given input word.

The most common formal definition of a DFA does not allow missing transitions. Please note that it does not really matter to which definition you stick as long as you're consistent with it. Also, given a DFA, it is easy to remove all transitions leading to a state from which we cannot reach an accepting state (because detecting states that do not lead to an accepting state can be done in polynomial time), and this does not affect the automaton's language. Conversely, given an automaton with missing transitions, you can direct all missing transitions to a *rejecting sink* which is a rejecting state with a self loop labeled with every letter.

# Answer
> 8 votes
Bader Abu Radi is right. In short, there are unfortunately competing definitions used by different people on this matter:

1. According to the most common definition, the YouTube video is right: the missing transition for strings starting with `b` means that the top machine is an NFA, and not a DFA.
2. But the Automaton simulator you used has a different definition, which allows missing transitions. In case of a missing transition, if you use this definition, the machine is said to not accept.

The difference between definitions (1) and (2) is minor: any valid DFA by definition (1) is a valid DFA by definition (2), and any valid DFA by definition (2) can be transformed into a valid DFA by definition (1) by adding just one additional state.

---
Tags: finite-automata
---


# Question
Title: Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree
CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have

```
MAYBE-MST-C(G,w)
  T = empty set
  for each edge e in G, taken in arbitrary order
    T = T U {e}
    if T has a cycle c
      let e' be a maximum-weight edge on c
      T = T - {e'}
  return T

```

I've found several other solutions (here, here and here) that claim that this procedure succeeds in finding an MST. However, I don't understand any of their proofs.

I can see that this results in a spanning tree. It's spanning because adding every edge e would certainly span G, and removing parts of cycles e' certainly doesn't affect that. It's a tree because any cycle that is added is guaranteed to be immediately removed.

I'm having a hard time seeing why it's minimal (or perhaps it actually isn't?). One of the solutions uses the result of exercise 23.1-5:

> if $G$ and has some cycle $c$, then there exists some MST of G that does not include the edge $e'$ with the largest weight on that cycle $c$.

While this result superficially resembles the operation performed in `MAYBE-MST-C`, upon closer inspection, it's not so obvious that it helps, since in the algorithm, T is *not* guaranteed to span G until the very end, and also the exercise result only claims that an MST exists when omitting *one* e'; it doesn't say we need to remove *all* e'. What if the MST that the exercise guarantees requires us to remove the *first* e', but keep the second? Further, upon removing e', how are we sure that the edges needed to compete the MST have not been removed in previous iterations of the loop?

# Answer
> 1 votes
`MAYBE-MST-C` **does** obtain the minimum spanning tree correctly.

Define a "local MST" as a spanning tree for which any cycle resulting from adding some edge $e$ would not have any edges on the cycle with weight $\> w(e)$.

**Lemma**: The tree $T$ generated by `MAYBE-MST-C` is a local MST.

**Proof**:

any edge $e$ that is not already in $T$ at the end of the algorithm must have been removed, and thus it must have been a part of some cycle $c$, and was a maximal-weight edge on that cycle at the time $e$ was removed.

Note the rest of $c - {e}$ could have been deformed *after* $e$ was removed, but each deformation can only replace an edge $f$ with a longer path consisting of weights that are at most $w(f) \leq w(e)$. Hence, if $e$ were added back into $T$ at the very end and completed some cycle $c'$ that had the final result of all those deformations, $e$ is still guaranteed to be a maximal-weight edge on $c'$.

**Main result**: `MAYBE-MST-C` results in a minimal spanning tree.

**proof**: From the lemma, `MAYBE-MST-C` results in a local MST, and since local MSTs are minimum, the result immediately follows.

---
Tags: graphs, graph-traversal, weighted-graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: Is the decision problem, for a Turing Machine are there any input strings rejected decidable?
**Given a Turing Machine T, are there any input strings rejected by T**. I need to decide whether this is decidable or recursively enumerable. I think it's undecidable, but I'm not sure how to prove it.

My initial approach would be to reduce the Halting Problem as either a string will 1)halt on final state i.e accepted or 2)halt on non-final state and go in a loop

Perhaps, there is another approach involving diagonalization where I can prove that the diagonalization language is finite - how do I do that?

# Answer
> 0 votes
Let us start by properly defining your language as say $$L = \\{\langle M \rangle \mid M \text{ rejects some input } x \in \Sigma^\ast\\}$$ where $\langle \cdot \rangle$ denotes some suitable encoding over our alphabet $\Sigma$. To reduce $L$ to the halting problem $\mathrm{Halt} = \\{\langle M, w \rangle \mid M \text{ halts on } w\\}$ we consider some $\mathrm{Halt}$ instance consisting of a TM $M$ and some input $w$ and define a new TM $M\_w$ which always, no matter what input it is given, just simulates the behavior of $M$ on $w$ with the slight change that it rejects if $M$ accepts, i.e. $M\_w$ rejects precisely if $M$ halts on $w$ and does not halt if $M$ does not halt on $w$. Note that $M\_w$ can be algorithmically constructed from $M$ and $w$.

We see that $\langle M, w \rangle \in \mathrm{Halt}$ if and only if $\langle M\_w \rangle \in L$, i.e. we have shown that the halting problem reduces to $L$ and thus $L$ is undecidable. However, $L$ is also recursively enumerable: Fix some ordering of $\Sigma^\ast$ and iteratively execute $M$ on the first $n$ strings of $\Sigma^\ast$ for $n$ steps. If $M$ rejects some string in $\Sigma^\ast$, this procedure will detect it in finitely many steps, showing that $L$ is semi-decidable and hence recursively enumerable.

---
Tags: computability, undecidability
---