# Question
Title: Fast algorithm for Graph Edit Distance to vertex-labeled Path Graph
Let $G$ be a vertex-labeled directed graph with unique labels $L$. Let $G\_P$ be a path graph with the same vertex labels and the same number of vertices as $G$.

I know that in the general case computing the Graph Edit Distance is NP-hard (if approximations are excluded) and APX-hard to approximate.

I'm interested in a subset of the problem:

**Is there a general algorithm for quickly computing the Graph Edit Distance from any $G$ to any $G\_P$, restricted to only adding and removing edges?**

Let, for example, $G=(\\{a,b,c\\}, \\{(a,b), (b,c), (c,a)\\})$:

Then the graph edit distance, excluding vertex addition/deletion, to the path directed graph $G\_P=(\\{a,b,c\\}, \\{(a,b), (b,c)\\})$ is 1.

It feels to me like this is a case that's restricted enough that there should be an efficient algorithm for computing the distance, but I might be mistaken.

Furthermore, for a given directed vertex-labeled graph, **is there a known algorithm for finding the set of labeled path graphs with the minimal graph-edit distance to the original graph?**

So far, for both questions, I haven't been able to find an answer (google scholar gives only semi-related answers to "graph edit distance to linear graph" and "graph edit distance to path graph".

Context for why I'm asking the question, probably not relevant to the answer.

# Answer
If both graphs have the same unique labels, there is a unique minimal way to edit edges: remove edges missing in the target, and add edges missing in the source. This problem is solvable in a linear time.

For finding the minimal-distance path graph (permutation), this is equivalent to the 0-1 TSP (the traveling salesman problem with edge cost 0 or 1):

The edit cost can be expressed as $|E| + |P| - 2 |E \cap P|$ where $(V, E)$ is the source graph and $P$ is the target path. By setting cost $0$ on edges and cost $1$ to non-edges, the cost of a tour is equal to the edit cost of the path plus some constant.

0-1 TSP is NP-hard but solvable in $O(2^n n^2)$ time by dynamic programming.
> 1 votes

---
Tags: algorithms, graphs, edit-distance
---


# Question
Title: determining whether a context-free language is regular
I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-terminals.

> $G:\ S\to aABb,\ A\to BAS \mid\epsilon,\ B\to a \mid b.$

It doesn't seem easy to determine exactly what set of strings the given language represents (e.g. there isn't some description like $\\{a^i b^i : i\ge 0\\}$ or the complement of some set that's easy to describe without explicitly listing the rules of a CFG).

The strings of $G$, where $G$ is the context-free grammar, seem to always end in some number of $Bb$'s and start with some number of $A$'s. Obviously every generated string must end in a b. There might be some relationship between the number of a's and b's of the language (e.g. maybe if a b appears then a certain number of a's must follow the b. The intuition is that the grammar doesn't generate strings with too many b's).

I think the language might be non-regular; the rules don't look like they'll translate to a regular expression easily. Two ways of showing a language is nonregular is to show that it fails the pumping lemma or it has infinitely many equivalence classes. Suppose $n$ is a pumping length for the language. The string $a(a^{3n} b^n)ab$ is in the language for every $n\ge 0$. It seems hard to verify whether a string is not generated by the grammar in cases other than the obvious ones (e.g. $b$ is not at the end of the generated string).

# Answer
> 2 votes
As you suspected, $L(G)$ is nonregular.

A common strategy to prove a language $X$ is nonregular is to find a regular language $Y$ such that $X\cap Y$ is nonregular. When $X$ is context-free, this strategy becomes more attractive since $X\cap Y$ is still context-free, indicating that it might be easy to guess, understand, and verify $X\cap Y$. We can consider $Y$ among some simple regular languages, hoping $X\cap Y$ is nonregular.

Check this question for a couple of examples.

---

Claim: $L(G)\cap L(a^\*b^\*)=\\{a^{2n-1}b^{2n}\mid n\ge1\\}\cup\\{a^{2n}b^{2n-1}\mid n\ge1\\}$.

Proof: Substituting $BAS \mid \epsilon$ for $A$ in rule $S\to aABb$, we obtain a context-free grammar $G\_1$ that is equivalent to $G$, $$G\_1: \ S\to aBASBb \mid aBb, \ A\to BAS \mid \epsilon, \ B\to a \mid b.$$

Let us investigate $G\_1$.
Suppose the derivation $S\to aBASBb$ will end up with a string in $L(a^\*b^\*)$. For any string in $L(a^\*b^\*)$, any symbol before an $a$ in that string must be an $a$ and any symbol after a $b$ in that string must be a $b$. Note that $S$ in $G\_1$ will generate strings that start with $a$ and end with $b$. Look at the right hand side of $S\to aBASBb$.

* $aBA$, which is before $S$ can only generate $a$'s. That means
    + the $B$ here can only use rule $B\to a$.
    + the $A$ here cannot derive $BAS$; otherwise, $aBA$ will generate at least one $b$ as $S$ will generate a string that ends with $b$. So the $A$ here can only derive $\epsilon$.
* the last $B$, which is after $S$ can only generate $b$'s. That means the last $B$ can only derive $b$.

The analysis above means that $L(G\_1)\cap L(a^\*b^\*)=L(G\_2)$, where $$G\_2: \ S\to aaSbb \mid aBb, \ A\to BAS \mid \epsilon, \ B\to a \mid b.$$ Substituting $a\mid b$ for $B$ in rule $S\to aBb$, we obtain grammar $G\_3$ that is equivalent to $G\_2$, $$G\_3: \ S\to aaSbb \mid aab \mid abb, \ A\to BAS \mid \epsilon, \ B\to a \mid b.$$ Since all useful rules in $G\_3$ are $S\to aaSbb \mid aab \mid abb$, it is easy to see $L(G\_3)=\\{a^{2n-1}b^{2n}\mid n\ge1\\}\cup\\{a^{2n}b^{2n-1}\mid n\ge1\\}.$ Note that $$L(G)\cap L(a^\*b^\*)=L(G\_1)\cap L(a^\*b^\*)=L(G\_2)=L(G\_3).$$

---

Corollary: $L(G)$ is not regular.

Proof: $$L(G)\cap L(a^\*\left(b^2\right)^\*)=(L(G)\cap L(a^\*b^\*))\cap L(a^\*\left(b^2\right)^\*)=\\{a^{2n-1}b^{2n}\mid n\ge1\\}.$$ Since $L(a^\*\left(b^2\right)^\*)$ is regular but $\\{a^{2n-1}b^{2n}\mid n\ge1\\}$ is not regular, $L(G)$ is not regular.

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


# Question
Title: if $RA$ is context-free, is $A$ context-free?
> If $RA$ is context-free for a regular language R, is $A$ context-free?

I think this statement is true. Let G be the CFG given by the rules $S\_0\mapsto LA\_1, S\mapsto LA\_1, A\_1\mapsto SA\_2 | RS | 1, A\_2\mapsto RS | 1, L\mapsto 0, R\mapsto 1$, where $S\_0$ is the start symbol. How would one modify G to get a CFG that generates the same grammar but with $0$ removed from the front of every string? Clearly the only way a derivation in G could generate a string starting with 0 is if it contains one of the nonterminals $L,S,A\_1$. So one should probably mark these nonterminals somehow and then modify the rules containing these nonterminals on the RHS.

# Answer
> 0 votes
Note that $\Sigma^\*A=\Sigma^\*$ is a regular language, where $A$ is any language that contains the empty string. So, given language $A$, the existence of an regular language $R$ such that $RA$ is regular (and hence also context-free) does not imply $A$ is context-free. Nor does it does imply $A$ is context-sensitive, etc.

If $R$ is meant to be any regular language, then letting $R=\\{\epsilon\\}$, we see the condition implies $A=\\{\epsilon\\}A$ is a regular language (and hence also context-free).

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


# Question
Title: Why is there a difference between the meaning of the word 'statement' in programming and linguistics?
In linguistics, the word 'statement' means something that is true or false, closer to a declarative sentence, but in programming, the meaning is closer to an imperative sentence.

What is the reason for this difference?

# Answer
You meet numerous "jargonic" meanings of common words in the field of mathematics, of which computer science is a branch (and in many other fields).

E.g. a function:

* an activity that is natural to or the purpose of a person or thing.

vs.

* a relation or expression involving one or more variables.

---

I acknowledge that the use of statement sounds a little weird as it evokes more a *logical proposition* than an programmatic action that modifies the state of variables. This acception was already in use in the frame of FORTRAN, the first symbolic programming language, created in 1957. Below, the "formal definition":

* A program unit is a sequence of statements, terminated by an END.
* A statement consists of zero or more key words, symbolic names, literal constants, statement labels, operators, and special characters.
> 0 votes

# Answer
The reason is very simple. In computer science, as well as in many other sciences, concepts are given names without much recourse to linguistic and historic significance of the name. This is not to say that names are chosen randomly, far from it, but I cannot imagine a group of people who are constructing a programming language discussing the meaning of “statement” in linguistics. (And the same can be said about linguists, who am I sure do not pay much attention to programming languages.)
> 1 votes

---
Tags: terminology, programming-languages
---


# Question
Title: what will be the space complexity of the following?
if two vectors are used for ex, vector\<vector\> temp; vector temp2;

then what will be the space complexity, will it be O(n) or O(n^2)?

# Answer
The complexity of `temp` will be

$$\sum\_{i=1}^n v\_i$$ where $n$ denotes the size of the outer vector and the $v\_i$ are the sizes of the inner vectors.

Space complexities are in principle given in terms of units of storage.
> 1 votes

---
Tags: space-complexity
---


title: safe edge for Minimum spanning tree

text:
# Question
Title: safe edge for Minimum spanning tree
I know this question is posted many times, but i am still posting this because i have my own doubt which pulls me out to move forward to kruskal and prim's algorithm.So Please do help me out $-:$

## Question

> Let $G=\left(V,E\right)$ be a be a **connected, undirected graph** with a real valued weight function $w$ defined on $E$.Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$.Let $\left(S,V-S\right)$ be any cut of $G$ that ***respects*** $A$.Let $\left(u,v\right)$ be a ***light edge*** **crossing** $\left(S,V-S\right)$.Then, edge $\left(u,v\right)$ is safe for $A$.

Terminologies Used
> we say that an edge $\left(u,v \right)$ **crosses** the cut if one of the endpoint is in $S$ and other in $V-S.$

---

> **Safe edge** is edge at each step that we can add in A without violating any invariant.

---

> we say that a Cut **RESPECTS** a set A of edges if no edge in A **crosses** the cut.

---

> we say that an edge is a **light edge** satisfying a given property if its weight is the minimum of any edge satisfying the property

### MY Approach/Doubt

With the help of book, i am able to understand the proof as-:

We Assume that $T$ is a MST(Minimum Spanning tree) which do not have **light edge** $\left(u,v \right)$, if we can manage to construct another MST $T^{'}$which contains $\left(u,v \right)$ and have weight less than that of $T$, then we are done! i.e we have to prove that $w \left(T^{'}\right) \leq w \left(T\right)$

---

Consider the figure below

As MST $T$ will not contain $\left(u,v \right)$(given) ,there must be an edge **that crosses the cut**, otherwise it will be divided into 2 components.

Let that edge be $\left(x,y \right)$

---

Now let us construct the MST$T^{'}$ from $T$ by removing $\left(x,y \right)$ and adding $\left(u,v \right)$ given as-:

$$w \left(T^{'}\right)=w \left(T\right)-w \left(x,y\right)+w \left(u,v\right) $$

$\Rightarrow \left(u,v \right) \leq w \left(x,y\right)$ as $\left(u,v \right)$ is light edge

$\Rightarrow w(T^{'}) \leq w(T)$

My doubt is -:

> 1.Is the above proof explained above correct?am i missing something?

---

> 2.If the above proof is correct, then i have one issue .Issue is that after proving the above inequality **$w(T^{'}) \leq w(T)$**,the book says that **$\left(u,v \right)$ is actually a safe edge for A**,but is n't this contradictory?

I mean if $\left(u,v \right)$ is safe for $A$ ,then **cut $\left(S,V-S\right)$ no longer respect $A$** because $\left(u,v \right)$ is an cross edge .

please help me out !

# Answer
> 4 votes
For a set $A$ which is a subset of some minimum spanning tree, an edge $e \notin A$ is *safe* if $A \cup \\{e\\}$ is a subset of some minimum spanning tree. In particular, if $|A| = n-2$, then any safe edge will cross the cut $(S,V-S)$. There is absolutely no requirement that $e$ not cross the cut.

# Answer
> 0 votes
I think the issue you having is the understanding of why **A** respects the cut, and you think that if **(u,v)** crosses the cut, then **A** is no longer a valid condition. In the proof when **A** respects the cut it doesn't imply that if we add an edge that crosses the cut, it won't be safe. Let me provide you with an informal definition of a safe edge.

```
("Paraphrased: A light edge that crosses a cut that respects A is safe for A.")

```

(taken from University of Hawaii)

So, this definition shows that **When we add (u,v) to two separate unconnected parts of a graph that one of them is A and it's an MST, that edge since it's minimum( light edge ), therefore, it must be safe**. This is the main argument of the proof, that needs to be shown, that the addition of light edge will result in the connections of parts of the graphs that are not connected and will keep the property of MST after that addtion.

---
Tags: algorithms, graphs, spanning-trees, minimum-spanning-tree
---


# Question
Title: Are there superexponential NP-complete problems?
Are there any NP-complete problems where the fastest known algorithm solves the problem in superexponential time (like $O(n!)$ time)? Every NP-complete problem that I am aware of has fastest known algorithms that are all exponential time, but it is not obvious to me whether there is anything preventing such problems from having best-case algorithms that run in superexponential time.

# Answer
> 5 votes
I’m not sure how you define “superexponential”, could you make it precise for me?

**If you define "super-exponential" as something described in the previous link like $2^{n^c}$**: In this context, $O(n!)$ (as you described) is something bounded by $O(n^n) = O(2^{n\log n}) \leq O(2^{n^2})$, not super-exponential; and since $\sf NP \subseteq EXP$, all problems in $\sf NP$ should be bounded by this "exponential time".

**If you define "super-exponential" traditionally, i.e. $2^{O(n)}$**: In this case, if you can find a $\sf NP$-complete problem $A$ that is not in ${\sf TIME}(2^{O(n)})$, then it's not in ${\sf SPACE}(n)$ either, thus we can know ${\sf NP} \nsubseteq {\sf SPACE}(n)$; but it's still unknown that if ${\sf NP} \subseteq {\sf SPACE}(n)$ now (maybe new results are published? I don't know, and I learn this from CMU 15-455 hw7 p4, spring 2017 by Prof. Ryan), so I guess proving this is hard.

(In fact this is more like a comment than an answer, but I don’t have enough reputation to do so, sorry about that)

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


# Question
Title: Create binary numbers with a described pattern
I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

* For size 2, $E = 1$, and the one number is given by $0^1 1^1 = 01$.
* For size 4, $E = 2$, and the two numbers are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.
* For size 8, $E = 3$, and the three numbers are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.
* For size $n = 2^E$, the $E$ numbers include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ numbers can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Is there an algorithm using bit manipulation that can generate each of these numbers in the set with algorithm in the range of $O(1)$ to $O(n)$?

**Important Note:** I am looking for an algorithm that generates binary numbers not strings unless transformation from strings to binary numbers can be in the range of $O(1)$ to $O(n)$.

# Answer
Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

* For size 2, $E = 1$, and the one string is given by $0^1 1^1 = 01$.
* For size 4, $E = 2$, and the two strings are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.
* For size 8, $E = 3$, and the three strings are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.
* For size $n = 2^E$, the $E$ strings include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ strings can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Thus, the examples are:

* Size 2: $E = 1$. The one string is $(0^1 1^1)^1 = (0^{2^0}1^{2^0})^{2^0}$
* Size 4: $E = 2$. The two strings are $0101 = (0^1 1^1)^2 = (0^{2^0} 1^{2^0})^{2^1}$ and $0011 = (0^2 1^2)^1 = (0^{2^1} = 1^{2^1})^{2^0}$.
* Size 8: $E = 3$. The three strings are $01010101 = (0^{2^0} 1^{2^0})^{2^2}$ with $k = 0$, $00110011 = (0^{2^1} 1^{2^1})^{2^1}$ with $k = 1$, $00001111 = (0^{2^2} 1^{2^2})^{2^0}$ with $k = 2$.

This is an iterative algorithm. You list each string, of length $n$ a total of $\log n$ times. It is $O(n \log n)$ to list all the strings explicity. It is $O(\log n)$ to express them regex style like $(0^x 1^x)^y$ \[note $x, y$ are powers of 2, and the exponents in the power form of $x, y$ add up to $E-1$\].
> 0 votes

# Answer
As said in my comment, binary numbers of size $n$ are not supported by current computers. We have two situations:

* only support the native binary type; as $n$ does not exceed $64$, you can very well precompute all patterns and store them in an array. (Counting all feasible sizes, there would be $2016$ patterns.)
* allow BigNums made of a sequence of $64$ bits integers; this is a little more tricky; you need to distinguish the case of inner patterns of length $\le64$ and $\>64$. But the basic principle is simple: generate the inner pattern and replicate it as many times as needed. You can't avoid an exhaustive construction.
> 0 votes

---
Tags: algorithms, time-complexity, combinatorics, binary, bit-manipulation
---


# Question
Title: Understanding of Turing's Answer to the Entscheidungsproblem
I apologize if this question has been asked before, but I was not able to find a duplicate.

I have just finished reading The Annotated Turing and I am a bit confused.

From what I understand, the Entscheidungsproblem is whether or not an algorithm exists that can determine whether a statement is provable. In the paper, Turing defines a *K* machine that will prove all formulae that are provable. This seems almost like a resolution to the problem, but later Turing writes:

> If the negation of what Gödel has shown had been proved, i.e. if, for each *A*, either *A* or *-A* is provable, then we should have an immediate solution of the Entscheidungsproblem. For we can invent a machine *K* which will prove consecutively all provable formulae. Sooner or later *K* will reach either *A* or *-A*. If it reaches *A*, then we know that *A* is provable. If it reaches *-A*, then, since **K** is consistent (Hilbert and Ackermann, p.65), we know that *A* is not provable.

Gödel's Theorem showed that some statements are true, but not provable. I guess what I don't understand is how Gödel's result prevents Turing's *K* machine from being a solution to the Entscheidungsproblem. Is it just as simple as that there are some formula that the *K* machine will never encounter, so it will keep running forever and never conclude that the formula is unprovable?

# Answer
> 5 votes
What Gödel showed is that there is no finite first-order axiomatization of the theory of the natural numbers. What this means is that if you give a finite list of first-order axioms and schemas, then the corresponding proof system won't be able to prove all true statements about the natural numbers. For example, it won't be able to prove its own consistency (this is Gödel's second incompleteness theorem). (A proof system is consistent if it doesn't prove a statement and its converse.)

Turing's machine, when applied to any given finite first-order proof system $\Pi$, will thus be able to prove neither the statement that $\Pi$ is consistent nor its negation.

Of course, this is not a proof that the Entscheidungsproblem itself is unsolvable; perhaps there is an altogether different approach that does work. Turing was able to show that, in fact, *no* (computable) approach works.

# Answer
> 0 votes
It is not correct. Robinson arithmetic system is finite axioms system, which is incomplete same as Peano axioms system.

---
Tags: computability, turing-machines, logic, decision-problem, incompleteness
---


# Question
Title: Why do we rely on computers in critical fields?
I assume that computers make many mistakes (like errors, bugs, glitches, etc.), which can be observed from the amount of questions asked everyday on different communities (like Stack Overflow) showing people trying to fix such issues.

If computers really make many errors (as I assumed earlier) then critical tasks (like signing in or receiving a receipt) must be designed to be almost error-free, unlike most of the tasks of most software and video games.

# Answer
> 24 votes
> If computers really make many errors (as I assumed earlier)...

Your assumption is wrong. Firstly, computers do not (except in extreme cases) "make many errors", humans do. Computers simply do what they are told to, very quickly and very well. Extraordinarily well, all things considered.

Secondly, what you're perceiving as a high rate of errors is in reality a high *perception* of errors. A banking system that handles millions of transactions per day may have a hidden bug (a human error in coding) that in a very specific set of circumstances does something incorrect. Those circumstances may only occur after years of correct operations. One failure in several billion operations is not a high error rate, but you hear about the failure and assume that the banking system must be error prone.

Back in the days when humans handled all the transactions - way, way back when that was even possible - the average error rate for transactions was many orders of magnitude higher. You can see that today in accounting circles, where end-of-month processing routinely involves tracking down human data entry errors to figure out why the (electronically recorded and processed) books don't balance.

> then critical tasks (like signing in or receiving a receipt) must be designed to be almost error-free

While signing into a system is a relatively simple thing to implement, the big-ticket flaws you've heard about generally come from outside of your own implementation. OpenSSL's Heartbleed vulnerability potentially allowed an attacker to snoop on your secure communications, Spectre/Meltdown potentially allows malware to snoop on your program's memory, and there are all sorts of interesting attacks on encryption that make life difficult. And any time you hear about one of these things it's sensational, front-page news on the tech sites and a flurry of "how do I protect against this" posts on programming sites.

And yet billions of logins happen daily, more billions of transactions get processed, making the true failure rate almost absurdly low.

> unlike most of the tasks of software and video games.

Software development for critical systems is an entirely different environment than game development. For one thing, only one of the two is about making money as quickly and cheaply as possible. Games developers don't actually care if a few bugs go through to production, because who cares if your car clips through walls in an out-of-the-way part of the map, or in some rare case manages to slide through the ground and you end up falling out of the map... just reload a save or something, and we'll patch that later. After all, modern gamers are used to being used as alpha testers on games, just as long as they get to have some fun who cares? Especially if they're paying for the privilege. And it's not like you have the time or the budget to rigorously test every possible code path.

Critical systems development *can't* be that sloppy. Every element is tested thoroughly, ever combination of elements is further tested. A lot of very bright people are paid a lot of money to find new ways to torture your code to make it break down and produce errors, and when they succeed it's back to the dev team to find out whay it broke and fix that issue. The customer doesn't get to see the system in action until it has been tested in every conceivable way. Because when it fails really bad things happen, and save points are *really* far apart in the real world.

> Why do we rely on computers in critical fields?

The simple reality is that there is no better option available to us. The things we use computers for simply can't be handled by humans alone in the volume, speed and accuracy required.

Are there alternatives? Maybe. Analog computing is great for some things, quantum computing offers some interesting possibilities. But for right now general-purpose computing is the best option on so many levels, and it's what we've spent most of the last century focusing on.

# Answer
> 26 votes
Computer *hardware* almost always does exactly what software tells it to do.
It's useful to distinguish software bugs from unreliable hardware.

---

Cosmic rays can randomly flip a bit in memory, though; that's why servers often use ECC (Error Correction Code) memory to correct single-bit errors and detect most multi-bit errors. (And internally, CPUs usually use ECC for their caches.)

Computers that need even more reliability and *availability*1 than that, like flight computers in aircraft or space craft, often have 3 separate computers processing the same inputs. (Triple Modular Redundancy) If all 3 produce the same output, great, it's almost certainly correct. (Especially if each of the 3 computers is running software written by different teams.) If only 2 out of the 3 outputs match, the odd one out is assumed wrong, so it gets reset and the system uses the outputs of the remaining two until the faulty one is rebooted and agreeing with them. If all 3 systems give different outputs, you have a big problem. If 2 systems give the same *wrong* answer, that's even worse.

Safety-critical systems like those are programmed in software much more carefully than video games or even mainstream OSes. Practices like avoiding dynamic memory allocation (`malloc`) remove whole classes of bugs and possible corner cases.

Footnote 1: detecting an error and rebooting is not sufficient when the system is part of the flight controls of a jet plane that could crash if the controls stopped responding for half a second.

---

Related:

# Answer
> 15 votes
Most errors in computer systems are caused by humans directly through design and programming errors.

Almost all questions on Stack Overflow concern programming problems and most errors that make it to end users are software bugs (human oversight).

Logic errors in hardware design (human oversight) have also caused trouble but theses errors are less common. Such issues can normally only be worked around at the OS or compiler level as hardware is almost impossible to fix once shipped.

Finally, as computers are electronic devices, they are susceptible to environmental influences (such as heat or radiation) and undesired complex physical interactions. Electrical interference can, for example, cause bit flips in DRAM but this is extremely rare as far as we are aware. It turns out such bit flips can even be caused intentionally from malicious software, which is known as row hammering, and it is believed by some that certain software might in rare instances cause bit flips by accident.

While the first two kinds of errors can be avoided through careful testing, simulation and formal modeling and verification, it is almost impossible to build an accurate physical model of an entire computer and all its smallest building blocks. As such, we will almost never be able to build a 100% reliable computer that works in uncontrolled environments. Nonetheless, finding better ways to build correct software through modeling and verification will already make computers much more reliable.

# Answer
> 14 votes
Because there's no practical alternative. Modern life is too complex for ordinary humans to keep track of all the details. And critical systems often require reaction times far quicker than humans or mechanical systems are capable of.

Consider a spacecraft. It likely has thousands of components that have to be monitored constantly. Mission Control would have to have hundreds of people on each shift watching all these readings, and they still wouldn't be as reliable as the computers.

Or in a hospital ICU, what would you replace all the computerized monitors with? You can't have a nurse watching each patient. We need to automate this, and have the computers raise alarms when a reading goes to an abnormal value.

The old saying "Don't let the perfect be the enemy of the good" applies. Despite the potential problems, computers are good enough to do what we need of them. There are millions of cars on the road with computerized control systems in the engines -- when have you heard of any of them failing?

Computers can have bugs, but safety-critical systems go through extensive testing. When computer software fails, the bugs can be fixed or the equipment can be replaced; it's harder to fix human error (you can do additional training, but people have inherent limits on speed and concentration).

There are other ways to mitigave computer problems, such as redundancy. The Space Shuttle had 5 identical computers operating the avionics system. During critical mission phases, 4 of them would would operate together, each calculating a result, and they would "vote" on the output. See Redundancy Management Technique for Space Shuttle Computers. Some airliners use redundant computers with completely different hardware and independently-written software, to avoid the possiblility that the same bug will be in both; see How dissimilar are redundant flight control computers?

Of course, less critical systems do fail more often. A few days ago the display of my car's navigation and entertainment system froze after displaying the startup message about using the system safely. Restarting the car rebooted the system and it was fine then. This system isn't necessary for driving, so it wouldn't have been a problem if it happened during high speed driving when I couldn't stop and start the car.

# Answer
> 3 votes
Basically hardware is reliable because it has to. It's not possible to fix a chip, and it's either impossible or not economical to fix a circuit board after it has left the factory. If a company sells buggy hardware, they can expect customers to ask for a refund.

In addition, hardware and especially chips have huge upfront costs. If the design for a cpu makes it to manufacture with bugs, someone is going to lose a bucketload of money and be very displeased about it.

Therefore, hardware and chip companies had to come up with ways to ensure the product actually works. And when there's a bug and the product is sold anyway, you can expect full documentation, erratas and workarounds.

On the other hand, no-one cares about software. It's kinda expected that it's going to be full of bugs, and it's easy to fix them with an update, which costs very little. The huge cost of throwing away bad chips and redoing a fabrication run does not exist for software.

Unless the software runs something like a rocket, or a plane, or a fabrication plant, where bugs cost a bucketload of money, there is really no incentive to make software that actually works 100% free of bugs. In fact, "release early with bugs" is often the more profitable option...

On top of the incentives, it's easier to test hardware because it is simpler. It has less state. The number of flops in a design is known. Hardware rarely manages complex data structures, buffers are usually of fixed size, synchronization is handled by well characterized primitives like FIFOs, there are much less object classes, less genericity, etc. It is designed as small pieces that can be unit tested (I heard that also exists for software, but who does that?...). And the tools pretty much guarantee that what is synthetized will do what the HDL says it should do.

The way to make sure a class of bugs doesn't happen is to find a provably correct solution and automate it. For example, if a language supports automatic memory allocation, then there can't be memory allocation bugs. It's the same for many classes of bugs. Can't have buffer overruns in a language that actually knows the size of a buffer. That kind of stuff. But using a new language is complicated, due to mountains of legacy code. This is different from hardware, where each big new generation of CPU tends to throw away large parts of the previous designs.

Now for example, SQL injections. There's one way to do it right, and that's to use a library or language that does it properly, where you pass a SQL query with placeholders and variables separately, like python DBAPI does. This is such an obvious fact, that it should not even need mentioning, yet many languages have (or are still using) the old bug-prone way of putting raw strings into queries.

A tool like PHP, which consistently produces bugs, would not live for long in the world of hardware. It would not be profitable. Yet PHP still thrives, on the software side.

**Extra:**

There was a time where software had a similar "cost per bug" as hardware, that was before the internet. Back in the day, bugs could not be fixed by an easy auto-update download. Sometimes, you had to mail floppies... and in the worst case, like arcade machines, game consoles, software that is burned into mask ROM, it was impossible to modify. These had the same cost incentives as hardware to get it right. These must have been thoroughly tested. Software was also much simpler back in the day, of course.

# Answer
> 2 votes
First of all nothing is unfailable. And if it be only, that its hit by a meteorite and gets completely destroyed.

Under the assumption, that there are no external factors, such as power failures, excessive heat, flooding, cosmic rays, etc. a computer will do exactly what you tell it to do.

As mentioned in other answers, this is the main crux of computers. If you do not give it clear enough constructions, there's room for error or malfunction, but this solely based on human error.

Testing exists for this purpose, but testing alone is not enough. You need to make sure, your tests are worth your money. There is a famous joke among programmers:

> A programmer programs a bartender. He tests it by ordering a beer, ordering 20 beers, ordering 0 beers, ordering milk and ordering pretzels. Convinced that his software works, he opens the bar. The first guest comes in and asks for the restroom. The bar burns down in flames.

The punchline (forgive me for explaining it) is, that the programmer did not anticipate such input. As such, especially critical systems need to be guarded against all possible forms of failures in order to avoid a crush or bug. This way, a much higher reliability can be reached than letting a human do the operations.

Humans get tired, distracted, lazy. There have been too many incidents to count, where people did not bother to follow safety instructions completly (even in super critical sectors as the flight industry) which ultimately lead to disaster. Computers will follow your orders to the letter. It's on humans to account for all possible options.

While this may sound impossible (after all, aren't there infinite possibilities) let me conclude this with a small example.

Suppose you write a program that wants to read in a number greater than zero. The user could input 0, a negative number, a letter, a picture, whatever. So if your code looks like this:

```
user_input = get_user_input();
result = 1 / square_root(user_input);

```

the last line could become problematic and indeed the program will most likely crash if incorrect input was entered. So to guard it, you'd write

```
user_input = get_user_input();
result = default_value;
if( is_valid_number(user_input) ){
    result = 1/square_root(user_value);
}
else{
    print("Error: Please enter a number > 0");
}

```

As such, it is very much possible to build very reliable software, even with human error factors.

# Answer
> 2 votes
Computers aren't the source of the failure. Programming isn't the source of the failure.

Algorithms thought of by humans are the source of the failures.

If we get a human to do steps to "login" or "provide receipts", they will **make as many, or more, errors than the program that replaces them**.

In fact, when you take a set of clear steps and automate them, you get a massive reduction in process errors. This can be so large that you make a different kind of error -- you try to apply the process in cases when it isn't very reliable!

When someone signs into a hotel, for example, the front desk does a bunch of steps involving verifying their identity, checking the payment method, ensuring the room is clean, etc. Prior to computers this was all done without them, using paper records and steps the people involved where supposed to follow.

It was slow, extremely error prone, and cost a bunch of money.

Replacing the steps that humans are bad at with computers doing them made it faster, less error prone, and much cheaper. But when they did this, they also tended to implicitly fold in tasks the computers where **not** good at into the same workflow, like dealing with exceptions and the like.

So you can get powerless front desk staff who are unable to make the computer make an exception when it is in the business interests of the owner of the hotel and computer to let them do it. And when the computer does make a mistake, there isn't the skills or ability to route around it and fix it.

Computers have replaced entire office buildings full of paper-shufflers. Forms getting mailed in, processed following certain algorithms, totals added up and written on other forms, summaries generated and put on other forms. Typists typing up documents, sometimes in triplicate or more. Secretaries taking memos and categorizing them by importance and presenting them to their executive. All steps we now do with computers for far less cost and far faster.

The computer doesn't always do it better, but it does it with far, far less errors.

The result of this lower error rate is that we pile more systems on top of systems. If you had something that failed 99% of the time, you can't build much on top of it; but you drop that failure rate to 0.001%, you can now treat it as reliable. So you build a system on top of it and 1000 other systems; and now your failure rate is upwards of 1%. You keep doing this, generating value, until the failure rate is high.

The only super complex systems we have are either the result of extensive engineering, like cars or rockets or integrated circuits or manufacturing line or bridges, or are the result of computer programming. Of these, computer programming is by far the cheapest one to prototype and modify and extend.

With this cheap extension and prototyping, you get these insanely complex systems built on a budget that solve problems. But the cost to make them reliable is *very high*, much higher than the cost to build them and see if they work. So computer programs are almost always written the be cheap and fast.

There is a whole pile of computer programs that are not written this way. Software to control air planes and rockets, for example. And software for medical systems. But even there, the temptation remains; you could either make something cost 100,000x as much and be utterly reliable, or be 100,000x cheaper and fail "very rarely". There is a lot of economic pressure to save a 100,000x cost increase and justify the cheaper way of writing software.

Modern software engineering is the economic management of insanely complex systems. When and where should you spend efforts on making something reliable, and when should you accept the insane cost savings of not ensuring reliability? Every spot you can accept bugs in is a spot that is much cheaper, but also a possible reason your entire project won't work.

# Answer
> 2 votes
As others have data to show correctness in computers, I wanted to add something about computer errors. In short, a filed bug can be designated as expected behavior for several reasons, and then adopted as part of the process.

This was an actual postmortem to code that managed account creation for credit report data. So very related to sign-in. The expected behavior was to continue account creation, even when the user failed their credit bureau verification. In doing so, there was a statistical subset where two accounts with two SSNs were linked.

Being assigned the bug, I fixed it by halting account creation on failing verification. This is my point, I made a value judgement and applied my own bias of what is right or wrong. The team lead drilled it into the team at the postmortem that there was no bug and errors had multiplied after my fix, further proof that the fix was incorrect.

In summary, there are real situations in which the computer's ability to be impartial is important. Is it really an error? To a business, ethical questions are debatable, sometimes what's important is to execute steps without bias.

# Answer
> 1 votes
The short answer is that we *don't* rely on them being error-free to any greater degree than we rely on anything else in a critical system to be error-free. Just as an individual computer hardware component can fail (and *will* fail in certain circumstances), any other non-computer component (mechanical, human or otherwise) can also fail. Just as the procedures ("programs") we write for computers can be incorrectly written, so can the procedures we write for humans to follow.

We achieve high reliability in systems not by counting on things not to fail but by knowing how and when they fail and designing the system to accommodate those failures.

# Answer
> 1 votes
Someone compared self driving cars to cars driven by humans. I would look at text messages instead: Delivering a text message without computer would force you to write it say on a postcard, take it to a letter box, where it is collected, sorted by delivery town, then some postman takes it to my home and drops it through the letter box.

Not only would the error rate be a lot higher (probably one percent or more of lost or misdelivered postcards), but you could expect a cost of say $0.50 per postcard, not counting the time it takes for you. There are kids sending hundreds of messages a day, they would bankrupt their parents in a short time.

A cheap computer can easily do 100 trillion floating-point operations in a day. So if that is what you need to do, then you have no choice but using a computer.

# Answer
> 0 votes
You get the wrong impression if you look at stack overflow for questions how to fix bugs. These bugs are 99% of the time not in shipping software! If an inexperienced developer creates a bug, either they detect immediately that their software doesn't work and fix it, or some more experienced developer checks it and it gets fixed, or QA tests the software, finds the bug, fixes it, or sometimes a bug appears only in very exceptional circumstances, so nobody ever finds it.

And you get the wrong impression again because humans make many mistakes that go undetected. If your car is repaired, but the repair is badly done, you will likely never find out. If your hotel bill, calculated by a human, is not correct, you will never find out. Computer programs do the same things again and again, and that is how mistakes get found out and fixed.

# Answer
> 0 votes
I can assure you that safety-critical software is produced in a way which ensures a high level of "software integrity".

* The vast majority of commonly encountered programming errors are **not made** at all because the safety rules demand specifically educated and certified personnel, demand using best practices, observing coding rules and using specific tools;
* the vast majority of the few errors actually made are **found** in mandatory reviews and mandatory, very thorough tests;
* the companies producing such software are regularly audited to ensure that they adhere to these principles;
* the systems are designed so that errors which are inevitably still present (which is where you are right) are **mitigated.** Mitigation strategies include redundancy, safe failure modes (like stopping a car or a train in case of an error), isolation of defective subsystems, or fallback to a degraded but still useful state.

These strategies make it possible to produce software that exposes so few catastrophic failures that it can be used where such failure would mean death.

# Answer
> -1 votes
The alternative is to *not* rely on computers. While there are some instances where humans clearly outperform computers (looking at you, Tesla Autopilot), in the vast majority of cases where computers do something safety-critical, they also outperform humans by a significant margin (c.f., anti-lock brakes, traction control systems, flight computers, pacemakers, etc. ad nauseum).

***EDIT*** Since the Tesla fanboys are so easily triggered by the shade I threw at Autopilot, I'll just leave this here for your viewing pleasure...

---
Tags: computer-architecture, security, error-estimation, reliability
---


# Question
Title: Algorithm with amortized time complexity
While I understand the process of considering/observing an algorithm and finding an average time, necessary to perform an operation that happens in this algorithm, I still cannot quite gasp the idea, or rather the expression:

**"The Algorithm has an amortized time complexity which is cost./linear etc"**.

What to understand when someone says the above expression?

One further question: Are the operations considered of the same type? What I mean by that, I'll try to showcase it with an example:

If we use pushback(), to input an element in an dynamic array, the operation here, is the input of an element. Sometimes the operation is cheap (in terms of the amount of times it requires to be executed) and sometimes is expensive. But there is only one type of operation here, the pushback operation. So can we talk about the amortized time of an algorithm, in other words can we talk about the average time for an operation, when different types of operations are taking place in the algorithm?

Sorry for the lack in my vocabulary. CS is not my major or main degree!

# Answer
> 1 votes
The amortized time is indeed the average time over a larger number of repetition of an operation (large enough that the variations are smoothed away).

A typical example is a growable array supporting `push_back` operations. When there is room at the end of the allocated space, a `push_back` costs $O(1)$. But when the allocated space is full, you increase it by doubling, and transfer all elements. This takes time $O(n)$, but only when $n$ is a power of $2$, so that the average remains $O(1)$.

In principle, only one operation is involved. In some cases, several can be (say insertions+deletions), provided this makes sense.

# Answer
> 0 votes
In my understanding, the statement "The Algorithm $A$ has an amortized time complexity which is linear" is something like $$\frac{1}{|\Sigma|^n} \sum\_{w \in \Sigma^n} \text{running time of $A(w)$} = O(n)$$ i.e. the algorithm may behave badly on some examples, but the "average" case is good. It's something just as you thought when you talked about expectations.

For your second question, I think that for a certain algorithm, it can not know which operation it will perform when it runs on a particular input. It's some code like `if (n >= 100) do()`, something you can't know exactly how it behaves at runtime when you analyze the time complexity. So when you do the analysis, you can only say something like "the memory allocation will occur somewhere", rather than "the memory allocation will occur when $n\geq 100$, and the same for $n \geq 200$, $n \geq 300$": it's not a general case.

# Answer
> 0 votes
Take the other answers first...

What must not happen is for example an algorithm that always takes a long time if an array size goes from 100 to 101, 200 to 201 etc. if this also happens if I change the size from 100 to 101 to 100 to 101 to 100 to 101 and so on. In this situation the changes from 100 to 101 must *not* take long. Where "amortised execution time" works is if you increase the array size say be 50% if it is not enough, and shrink the array size if it is at 60% of the original size. So if 100-\>101 increases the array size, you'd have to remove 42 elements to get the size down to less than 60 to get a slow operation again and reduce the size to 100, and then you'd need another 42 operations to get back to 101 elements where you increase the size.

Another thing that doesn't count: If you want a sorted array all the time. Adding a random element to an array and keeping it sorted takes O(n). Starting with an empty array and adding n random items takes O(n^2) if the array needs to stay sorted all the time. If you only sort it at the very end, that's only O(n log n), but that is not amortised time.

Another thing to remember: In CS we are usually talking about time complexity. But assume that an operation can take either 10ns or 10µs on a real implementation. Both are O(1) but 10ns is what you would very much prefer in practice. Sometimes you find algorithms that are executed repeatedly that you can manipulate so that the expensive case happens only rarely.

---
Tags: time-complexity, amortized-analysis
---


# Question
Title: How to disambiguate CFG with unary/binary minus and binary prefix operator
I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1).

I'm facing the current fragment of the language:

$$ \begin{align} S & → T \quad | \quad \texttt{prefix} \quad T \quad S \\ T & → F \quad | \quad T \texttt{-} F \quad | \quad \texttt{-} F \\ F & → \texttt{1} \end{align} $$

The tokens `prefix` and `1` and `-` are terminals.

Note that `prefix 1 - 1 - 1` has at least two parses: `prefix (1-1) (-1)` and `prefix 1 (-(1-1))`.

I'm willing to make small changes to the language to resolve this ambiguity, but I would prefer only making grammar changes that resolve just this ambiguity. Are there local transformations I can make? Global ones?

I think inserting a new token, e.g. `:`, between T and S in the `prefix` production should disambiguate the grammar.

Is it possible to transform the grammar such that it (a) becomes LR(1); and (b) encodes the rule "always parse the shortest possible substring as the T part in a prefix production"?

(I think I cannot do the longest string—it seems hard to know that what follows will fail to parse as an S. It will become even harder once I add in the rest of the language.)

# Answer
I'm going to limit myself, at least for now, to the question actually asked here: how to deal with the ambiguity between an operator which could be prefix or infix (such as unary negation) and a prefix operator which takes two consecutive arguments. There is a second interesting question, which has to do with prefix operators which bind less tightly than (some) infix operators.

These two language features are not really related, but they are similar in that the naïve grammars are ambiguous, and the ambiguities are difficult to resolve in a strict LR(k) grammar. They are also similar in the fact that many languages suffer from inadequate resolutions of these ambiguities, or resolve them in ways that are poorly understood by language users, in part because the resolutions are hard to document.

## Ambiguity with prefix negation

Since prefix negation and infix difference operators generally use the same symbol (`-`), an ambiguity is created in any syntactic construct in which two expressions can appear consecutively without an intervening token. Many languages have such constructs. They include:

* Prefix operators which take more than one argument, as in your question.
* **Implicit operators** such as implied multiplication (`2x` instead of `2*x`) and function application (as in Haskell, where `f a` calls `f` with argument `a`, similar to `f(a)` in many other languages). Other examples include Awk's implicit string concatenation syntax, where `a b` represents the concatenation of the two variables.
* **Undelimited sequences**, usually lists or tuples, where consecutive elements are simply specified one after another and the elements can be expressions. One early language with this feature is Logo, but there are many others.
* **Undelimited statements**. In languages in which statements can be written consecutively without a separating delimiter (Lua, for example), two expressions can be consecutive if an expression can be a statement, or more generally if there are statement syntaxes which start with an expression (such as assignment statements) and other syntaxes which end with an expression (such as `return` statements).

That's not an exhaustive catalogue, but it gives an idea of the range of the issue.

There are three broad strategies to resolve this ambiguity:

1. Require the first expression (or both expressions) to be either an atomic term or a parenthesised subexpression. If the ambiguity is the result of an implicit operator, this resolution will be natural if the implicit operator's binding precedence is at the top of the precedence list; that's the case with Haskell, for example, where function application takes precedence over any other operator. This strategy is also sometimes used for undelimited lists, allowing a list of three elements to be written `[a b c]` if the components are simple, but requiring `[a (b + c) d]` for more complicated components.
2. Prohibit the second expression from starting with an ambiguous prefix operator. Or, in other words, resolve the ambiguity in favour of the infix operator, when there is a choice. This is the preferred solution for implicit multiplication, and it follows the Principle of Least Astonishment, since resolving `2-x` as `2*(-x)` would astonish most users. This does not require the implicit operator to have maximum precedence; indeed, most grammars with implicit multiplication would parse `2x^4` (where `^` is the exponentiation operator) as `2*(x^4)`, again to avoid surprises. (Different parsers resolve `2a/3b` in different ways, so there can still be surprises. Some people feel that implicit multiplication should bind more strongly than explicit multiplication and division; others that implicit and explicit multiplication should bind equally. But that's a different issue.)
3. Resolve the ambiguity between unary negation and binary difference during lexical analysis. For example, Logo requires that the unary negation operator either be preceded by an open parenthesis or some token which cannot be part of an expression, so that binary difference is not a possible interpretation, or that it be written with at least one space before and no spaces after. The second rule allows `a -10 * b` to be interpreted as the two expressions `a` and `((-10)*b)`, while `a - 10 * b` would necessarily be interpreted as a single expression. A similar, but more complicated, set of whitespace-aware rules was proposed for the Frontier language (never implemented, to my knowledge); it was criticised for being too subtle for code readers.

Solution one is appropriate for Haskell. Since it's simply an operator precedence rule, it's easy to describe. The expression `fmap f (Just x)` needs to be written that way because function application is left-associative; `fmap f Just x` would be `(((fmap f) Just) x)` so the requirement to parenthesise `(Just x)` is pretty clear, in the same way that you would have to write `a - (b - c)`, if that's what you meant. (It's worth noting that Haskell also has an explicit application operator, `$`, with low binding precedence, which can sometimes be used to avoid parentheses.)

Solution three is certainly possible, but whitespace-aware syntax is a common source of confusion for casual users. (And, as noted above, is easy to miss when you're reading code.)

So my preference would be solution two: when both interpretations of the unary/binary operator are possible, always prefer the binary interpretation. That's often simply the expected interpretation, although it can lead to surprises when the consecutive expressions are separated by a newline; even then, the rule is easy to explain.

It's also easy to implement. The basic idea is to define two different expression non-terminals. One is unrestricted; it is used for the first expression in a consecutive sequence. The other one does not accept any expression whose first token is an ambiguous unary operator. (If the language has unambiguous unary operators, they don't need to be restricted.)

If you were using a parser generator which accepted the formalism in the ECMAScript standard, this would be trivial. Unfortunately, few (if any) parser generators allow templated non-terminals, so the implementation requires annoying code duplication in the grammar. In yacc/bison syntax, assuming that operator precedence is established with prior precedence declarations:

```
expr: expr '+' expr
    | expr '-' expr
    | expr '*' expr
    /* other binary operators omitted */
    | '-' expr %prec UNOP
    | '+' expr %prec UNOP
    | CONSTANT
    | IDENTIFIER
    | '(' expr ')'
expr_follow
    : expr_follow '+' expr
    | expr_follow '-' expr
    | expr_follow '*' expr
    /* ... other binary operators */
    /* ambiguous unary operators omitted */
    | CONSTANT
    | IDENTIFIER
    | '(' expr ')'

```

Note that the `expr_follow` restriction cascades only through the first operand of the productions; the operands following an operator or `(` do not need to be restricted since they will not affect the first token in the expression.

If you were using cascading-precedence style rather than precedence operators, you'd need to create two non-terminals at each precedence level, something like this:

```
expr: additive
additive
    : additive '+' multiplicative
    | additive '-' multiplicative
    | multiplicative
multiplicative
    : multiplicative '*' negative
    | multiplicative '/' negative
    | multiplicative '%' negative
    | negative
negative
    : '-' negative
    | exponential
exponential
    : unary '^' negative
    | unary
unary
    : '&' unary   /* '&' represents an unambiguous unary operator */
    | atom
atom: CONSTANT
    | IDENTIFIER
    | '(' expr ')'

expr_follow
    : additive_follow
additive_follow
    : additive_follow '+' multiplicative
    | additive_follow '-' multiplicative
    | multiplicative_follow
multiplicative_follow
    : multiplicative_follow '*' exponential
    | multiplicative_follow '/' exponential
    | multiplicative_follow '%' exponential
    | exponential

```

In the first stanza, I would usually simplify `negative` to:

```
negative
    : '-' negative
    | unary '^' negative
    | unary

```

I wrote it the way I did to better illustrate the difference between the two cascades. The second cascade does not have `negative` because the unary negative cannot appear at the start of `expr_follow` (so there is no `negative_follow`). `exponential`, `unary` and `atom` do not need to be duplicated because none of them can start with unary negative.

## Read this if you're considering designing a language with consecutive expressions

On the whole, a syntax which allows two consecutive expressions is a snakepit of perpetual syntactic problems. Each ambiguity needs to be identified and then resolved in the parser. Since there is no universal principle which determines a unique resolution, the language designer needs to think through the possible disambiguations and choose the one they feel is best suited to the problem domain.

Each such resolution is, in general, easy to implement once it has been precisely spelled out, but the rules can be very difficult to describe or justify to users. That can lead to mysterious bugs, in which a syntactic construct was resolved in an unexpected way, or mysterious syntax errors, in which a syntactic construct which seems reasonable to the coder was banned for ease of implementation. One frequent consequence in languages which develop to the point of having style guides and linters, is a stylistic ban on precisely these syntactic constructs; either alternative syntaxes or redundant parentheses are required, and these can even give rise to the language implementation itself issuing warnings.
> 1 votes

# Answer
I came up with a simple and acceptable solution: the first argument to the binary prefix operator can be any expression with a precedence binding tighter than unary negation. That's almost no expressions, but it does include integer literals which is the most common case.

This reminds me of a bit of haskell syntax. Note that `<Expression> <Expression>` is valid Haskell syntax, e.g. for function application which associates left; the associativity and precedence should be enough to work around the ambiguity of $E → E \ E$.

There's also pattern matching in function declarations, e.g.

```
fmap f (Just x) = Just (f x)
fmap f Nothing = Nothing

```

Here you have to parenthesize the multi-token pattern `(Just x)`, but not the single-token pattern `Nothing`. I suspect this is for similar reasons.

To answer rici's questions in the comments: I am trying to implement this and would prefer an LALR(1) grammar.

My current grammar, including my solution, does the usual

```
<Term> ::= <Factor>
         | <Term> + <Factor>

```

shenanigans to encode precedence and associativity. I have some productions which benefit from the rules being split up into small chunks this way, once again having to do with ambiguities around prefix vs. infix operators.

I guess I could look in the Happy manual and experiment with precedence rules to express my solution that way, but I'd rather start by building something that works on the basis of my understanding of context-free grammars. Also, I'm learning plenty in the process, which is one of my goals. But I'll definitely put experimenting with precedence rules on the TODO list, just to see if it does anything to the underlying PDA.
> 0 votes

---
Tags: formal-languages, context-free, ambiguity, language-design, lr-k
---


# Question
Title: Why is $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ decidable?
I get that the argument for this set $\\{ w \in \Sigma^\* : M\_w\[\epsilon\]\downarrow \land |w| \leq 7\\}$ to be decidable is that $|w|\leq7$ meaning it is a finite set and therefore it can be decided. But my problem is that for each of the $w$ it could be the case that one has to wait an infinite amount of time in order to decide whether or not it belongs in the set. So where lies my mistake in this reasoning?

$M\_w\[\epsilon\]$ is the output of the Turing machine corresponding to encoding $w$ on input $\epsilon$.

$M\_w\[\epsilon\]\downarrow$ is short for $M\_w\[\epsilon\]$ halts.

# Answer
First, note that if $|\Sigma| \> 1$, you have more than eight different $w$.

Second, I would assume that $M\_w\[\varepsilon\]$ is the output of the Turing machine corresponding to encoding $w$ on input $\varepsilon$.

I assume, that $M\_w\[v\]\downarrow$ is short for $M\_w$ halts on $v$.

You correctly observed that the restriction to $|w| \leq 7$ guarantees that the set is finite and hence, decidable. However, this reason is indeed not very constructive: Which Turing machine codes are actually in your language is not clear but it is a (finite) subset of $\\{w \in \Sigma^\ast \mid |w| \leq 7\\}$. For each of those subsets you can construct a TM (in fact, a finite automaton even) and one of these TMs is the correct machine, you just do not know which one.
> 0 votes

# Answer
The error in your reasoning is where you say "one has to wait an infinite amount of time in order to decide whether or not it belongs in the set". You are hypothesizing one possible way to decide, and then demonstrating that this possible way doesn't work. That is all correct as far as it goes.

But this doesn't mean that the problem is undecidable. There is another way to decide the problem, that doesn't require doing things the way you were hypothesizing, but that does things differently. The other way works by hardcoding the answers, without simulating the Turing machine or running it for a while. See How can it be decidable whether $\pi$ has some sequence of digits?. That other way shows that the problem is decidable.

You can't show a problem is undecidable by showing that one particular way of deciding fails. You can only show a problem is undecidable if you can show that *all* candidate ways of deciding don't work.

Regarding your comment about "feels like cheating", whenever you get that feeling, I recommend you go back to the mathematical definition. The mathematical definition of when a problem is decidable is if there exists an algorithm that decides it, and there is a specific mathematical definition of when we consider an algorithm to decide a problem. Hardcoding yields an algorithm meets all of those criteria.

I understand your sense that it "feels like cheating". What that sense is teaching you is that your intuition isn't quite right yet: it doesn't quite match the mathematical definition. These examples are designed to help you refine your intuition so that it better captures the actual mathematical definition.
> 0 votes

---
Tags: turing-machines, sets, halting-problem
---


title: Transition System vs State Machines

text:
# Question
Title: Transition System vs State Machines
Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (for describing its language). I just want to know about the basics. Can I call a DFA a transition system (because DFA is a state machine, but never saw it be called a transition system)? NFA/DFA are finite state machines (FSM) and transition systems can have a finite or infinite set of states (does it mean it is an infinite state machine?). A more basic question, is every "state machine" a "system" or vice versa? What is the difference between "machine" and "system"? Why we are not calling "Transition Machine"?)

(Note: I asked the same question in Mathematics Stack Exchange but got no answer. That is why posting it in here.)

# Answer
> 1 votes
From each DFA or NFA, you can obtain a labelled transition system, by ignoring which states are the initial or final states.

If you have a labelled transition system with a finite set of states and a finite alphabet, as well as an initial state and a set of final states, you can define a corresponding NFA.

See https://en.wikipedia.org/wiki/Transition\_system, which has answers to several of your questions. In general, I recommend reading standard resources (such as textbooks and Wikipedia) before asking here, to ensure that your question is not already answered in them.

The difference between "machine" vs "system" is just an arbitrary choice and has no particular meaning in this context.

---
Tags: formal-languages, finite-automata, computation-models, model-checking, transition-systems
---


# Question
Title: Impossibility for Byzantine Generals Problem where $n \leq 3m$
Wiki: https://en.wikipedia.org/wiki/Byzantine\_fault\_tolerance

---

In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the problem for $n \leq 3m$, where $n$ stands for the number of generals and $m$ stands for the number of traitors. The key of their proof this the impossibility of the case $n=3,m=1$. However, the method they used does not look like an information theoretic proof. Thus, it seems like that their result is not "impossibility of arbitrary protocol".

---

> **My question:** Is there a infomation-theory-based proof for the case $n=3,m=1$? More formally, is there a proof or counterexample for the proposition "there does not exist any kind of protocol, which solves Byzantine generals problem where $n=3,m=1$"?

---

Note: The typical protocol $\mathrm{SM}(m)$ (it works for arbitrary $n,m$) suggested by L. Lamport et al. is NOT a suitable counterexample, because it needs a signature mechanism, which is NOT perfect reliable in the sense of information theory, if we assume that traitors have infinity computing resources.

# Answer
> 3 votes
In the synchronous model of communication, there are $n$ agents which share a clock. In each round of communication, each agent sends an arbitrary message to each other agent, and then receives the message sent her by every other agent.

A protocol for byzantine agreement on $n$ agents supporting $m$ byzantine agents is a communication protocol for the agents satisfying the following properties:

* Each agent receives an input bit.
* The agents all start talking at time 0.
* There are at most $m$ byzantine agents, whose behavior is arbitrary.
* The other agents follow the protocol.
* The protocol always terminates (this means that the non-byzantine agents always reach a special "terminate" state of the protocol, and then stop talking forever), with a return value which is also a bit.
* The return values must all agree (note that this only applies to the non-byzantine agents).
* If all input bits are the same, then the return values have to be the same bit.

The impossibility result states that such a protocol exists if and only if $n \> 3m$.

There is a different model in which an agent can sign a message, and this signature cannot be tampered with. In this model (which I will not specify formally) the problem can be solved for any $n,m$.

One of the difficulties in the area of distributed systems is the complicated nature of the computation model. If you want to understand the meaning of impossibility results, you have to familiarize yourself with these models in full detail (even more detail than the rather informal treatment in this answer).

# Answer
> -1 votes
I have thought the same issue as yours for a long time(I mean from the view of information theory). Maybe there is some fundemental things behind the consensus in the paper, such as entropy (uncertainty) in the whole distributed system of all the nodes, and the purpose of a consensus is to eliminate the entropy or you can say to figure out something that will make the uncertainty disappear. And maybe identifying the false nodes(byzantine nodes) in the system is a way to remove uncertainty, what do you think of this idea? (But I don't know how to quantify the entropy) oh, there is a solid proof in the paper "*Impossibility of Distributed Consensus with One Faulty Process*", but it is focused on the CFT scenario, not BFT.

---
Tags: distributed-systems, information-theory, fault-tolerance
---


# Question
Title: A different algorithm called the 'bubble sort'?
In Robert Lafore's book "Object Oriented Programming in C++, Fourth Edition", on page 450, he has a section on the bubble sort. The way he describes it is as follows:

> Here's how it works, assuming we want to arrange the numbers in the array in ascending order. First the first element of the array (arr\[0\]) is compared in turn with each of the other elements (starting with the second). If it's greater than any of them, the two are swapped. When this is done we know that at least the first element is in order; it's now the smallest element. Next the second element is compared in turn with all the other elements, starting with the third, and again swapped if it's bigger. When we're done we know that the second element has the second-smallest value. This process is continued for all the elements until the next-to-the-last, at which time the array is assumed to be ordered.

This sounds to me like it is very different from what is commonly called the bubble sort (you iterate through the array comparing 0 and 1, 1 and 2, 2 and 3 and so on, repeatedly, until they are all in order). I wrote some code to compare the speed of these two algorithms and found that Lafore's bubble sort is consistently twice as fast as the standard one. So what's going on here? Does Lafore's bubble sort ordinarily go by a different name?

# Answer
Ok, I think I found what Lafore is calling the "Bubble sort". It is commonly known as selection sort: https://www.geeksforgeeks.org/selection-sort/

**Edit**: As greybeard and Yves Daoust have pointed out, Lafore's algorithm actually performs a lot more swaps than selection sort. Someone has since pointed out to me that in fact Lafore's bubble sort performs a roughly similar number of comparisons and swaps to the standard bubble sort. He also showed me that the difference in speed that I observed is due to the way I wrote the code and can be eliminated by implementing the standard bubble sort differently. So in conclusion, although it may not be obvious at first, it seems that Lafore's bubble sort is actually just another version of the standard bubble sort.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Generating uniformly distributed random numbers using a coin
You have one coin. You may flip it as many times as you want.

You want to generate a random number $r$ such that $a \leq r \< b$ where $r,a,b\in \mathbb{Z}^+$.

Distribution of the numbers should be uniform.

It is easy if $b -a = 2^n$:

```
r = a + binary2dec(flip n times write 0 for heads and 1 for tails)

```

What if $b-a \neq 2^n$?

# Answer
> 14 votes
What you're looking for is based on Rejection sampling or the accept-reject method (note that the Wiki page is a bit technical).

This method is useful in these kinds of situations: you want to pick some random object from a set (a random integer in the set $\[a,b\]$ in your case), but you don't know how to do that, but you *can* pick some random object from a larger set containing the first set (in your case, $\[a, 2^k + a\]$ for some $k$ such that $2^k + a \ge b$; this corresponds to $k$ coin flips).

In such a scenario, you just keep picking elements from the bigger set until you randomly pick an element in the smaller set. If your smaller set is big enough compared to your larger set (in your case, $\[a, 2^k + a\]$ contains at most twice as many integers as $\[a,b\]$, which is good enough), this is efficient.

An alternative example: suppose you want to pick a random point inside a circle with radius 1. Now, it isn't really easy to come up with a direct method for this. We turn to the accept-reject method: we sample points in a 1x1 square encompassing the circle, and test if the number we draw lies inside the circle.

# Answer
> 7 votes
Choose a number in the next larger power of 2 range, and discard answers greater than $b-a$.

```
n = b-a;
N = round_to_next_larger_power_of_2(n)
while (1) {
  x = random(0 included to N excluded);
  if (x < n) break;
}
r = a + x;

```

# Answer
> 7 votes
*(technicalities: the answer fits selection of number $a \le x \< b$)*

Since you are allowed to flip your coin as many times as you wish, you can get your probability as-close-as-you-wish to uniform by picking a fraction $r\in \[0,1\]$ (using binary radix: you flip the coin for each digit after the point) and multiply $r$ by $b-a$ to get a number between 0 and \[b-a-1\] (rounding down to an integer). Add this number to $a$ and you're done.

*Example*: say $b-a=3$. 1/3 in binary is 0.0101010101.... Then, if your flip is between 0 and 0.010101... your pick is $b$. if it is beween 0.010101.. and 0.10101010... your pick will be $a+1$, and otherwise it will be $a+2$.

If you flip your coin $t$ times then each number between $a$ and $b$ will be chosen with probability $\frac{1}{b-a}\pm 2^{-(t+1)}$.

# Answer
> 7 votes
Nobody mentioned this, so let me formally prove that if $D$ is a domain whose size is not a power of two, then finitely many fair coin tosses aren't enough to generate a uniformly random member of $D$. Suppose you use $k$ coins to generate a member of $D$. For each $d \in D$, the probability that your algorithm generated $d$ is of the form $A/2^k$ for some integer $A$. The fundamental theorem of arithmetic shows that $A/2^k \neq 1/{|D|}$.

If you want to generate $n$ independent uniform samples of $D$, then the expected number of coin tosses you need (under the optimal algorithm) is roughly $n \log\_2 |D|$. More generally, if you want to generate from a distribution of entropy $H$, you need roughly $nH$ random bits in expectation. An algorithm achieving this is arithmetic decoding, applied to an (ostensibly) infinite sequence of random bits.

# Answer
> 3 votes
If b-a is not a power of 2 then you may have to flip many coins in order to get a result. You may even never get a result, but that is unlikely in the extreme.

**Methods**

The simplest method is to generate a number in \[a, a+2^n), where 2^n \>= b-a, until one happens to land in \[a, b). You throw away a lot of entropy with this method.

A more expensive method allows you to keep all of the entropy, but becomes very expensive computationally as the number of coin flips / dice rolls increases. Intuitively it is like treating the coin flips as the digits of a binary number to the right of the decimal point, converting that number from base 2 to base a-b after, and returning the digits of that number as they become 'stuck'.

**Example**

The following code converts rolls of a fair n-sided die into rolls of a fair m-sided die (in your case n=2, m=a-b), with increasing marginal cost as the number of rolls increases. Note the need for a Rational number type with arbitrary precision. One nice property is that converting from n-sided to m-sided and back to n-sided will return the original stream, though perhaps delayed by a couple rolls due to digits having to become stuck.

```
public static IEnumerable<BigInteger> DigitConversion(this IEnumerable<BigInteger> inputStream, BigInteger modIn, BigInteger modOut) {
    //note: values are implicitly scaled so the first unfixed digit of the output ranges from 0 to 1
    Rational b = 0; //offset of the chosen range
    Rational d = 1; //size of the chosen range
    foreach (var r in inputStream) {
        //narrow the chosen range towards the real value represented by the input
        d /= modIn;
        b += d * r;
        //check for output digits that have become fixed
        while (true) {
            var i1 = (b * modOut).Floor();
            var i2 = ((b + d) * modOut).Floor(); //note: ideally b+d-epsilon, but another iteration makes that correction unnecessary
            if (i1 != i2) break; //digit became fixed?
            //fix the next output digit (rescale the range to make next digit range from 0 to 1)
            d *= modOut;
            b *= modOut;
            b -= i1;
            yield return i1;
        }
    }
}

```

# Answer
> 2 votes
Generate a binary decimal. Instead of storing it explicitly, just keep track of the min and max possible values. Once those values lie within the same integer, return that integer. Sketch of the code is below.

(Edit) Fuller explanation: Say you want to generate a random integer from 1 to 3 inclusive with 1/3 probability each. We do this by generating a random binary decimal real, x in the range (0, 1). If x \< 1/3, return 1, else if x \< 2/3 return 2, else return 3. Instead of generating the digits for x explicitly, we just keep track of the minimum and maximum possible values of x. Initially, the min value of x is 0 and the max is 1. If you flip heads first then the first digit of x behind the decimal point (in binary) is 1. The minimum possible value of x (in binary) then becomes 0.100000 = 1/2 and the max is 0.111111111 = 1. Now if your next flip is tails x starts with 0.10. The min possible value is 0.1000000 = 1/2 and the max is 0.1011111 = 3/4. The min possible value of x is 1/2 so you know there's no chance of returning 1 since that requires x \< 1/3. You can still return 2 if x ends up being 1/2 \< x \< 2/3 or 3 if 2/3 \< x \< 3/4. Now suppose the third flip is tails. Then x must start with 0.100. Min = 0.10000000 = 1/2 and max = 0.100111111 = 5/8. Now since 1/3 \< 1/2 \< 5/8 \< 2/3 we know that x must fall in the interval (1/3, 2/3), so we can stop generating digits of x and just return 2.

The code does essentially this except instead of generating x between 0 and 1 it generates x between a and b, but the principle is the same.

```
def gen(a, b):
  min_possible = a
  max_possible = b

  while True:
    floor_min_possible = floor(min_possible)
    floor_max_possible = floor(max_possible)
    if max_possible.is_integer():
      floor_max_possible -= 1

    if floor_max_possible == floor_min_possible:
      return floor_max_possible

    mid = (min_possible + max_possible)/2
    if coin_flip():
      min_possible = mid
    else:
      max_possible = mid

```

Remark: I tested this code against the accept/reject method and both yield uniform distributions. This code requires less coin flips than accept reject except when b - a is close to the next power of 2. E.x. if you want to generate a = 0, b = 62 then accept/reject does better. I was able to prove that this code can use on average no more than 2 more coin flips than accept/reject. From my reading, it looks like Knuth and Yao (1976) gave a method to solve this problem and proved that their method is optimal in the expected number of coin flips. They further proved that expected number of flips must be greater than the Shannon entropy of the distribution. I could not find a copy of the text of the paper however and would be curious to see what their method is. (Update: just found an exposition of Knuth Yao 1976 here: http://www.nrbook.com/devroye/Devroye\_files/chapter\_fifteen\_1.pdf but I have not yet read it). Someone also mentioned Han Hoshi in this thread which seems to be more general and solves it using a biased coin. See also http://paper.ijcsns.org/07\_book/200909/20090930.pdf by Pae (2009) for a good discussion of the literature.

# Answer
> 2 votes
**Theoretically optimal algorithm**

Here is an improvement of the other answer I posted. The other answer has the advantage that it is easier to extend to the more general case of generating one discrete distribution from another. In fact, the other answer is a special case of the algorithm due to Han and Hoshi.

The algorithm I will describe here is based on Knuth and Yao (1976). In their paper, they also proved that this algorithm achieves the minimum possible expected number of coin flips.

To illustrate it, consider the Rejection sampling method described by other answers. As an example, suppose you want to generate one of 5 numbers uniformly \[0, 4\]. The next power of 2 is 8 so you flip the coin 3 times and generate a random number up to 8. If the number is 0 to 4 then you return it. Otherwise, you throw it out and generate another number up to 8 and try again until you succeed. But when you throw out the number, you just wasted some entropy. You can instead condition on the number you threw out to reduce the number of future coin flips you'll need in expectation. Concretely, once you generate the number \[0, 7\], if it is \[0, 4\], return. Otherwise, it's 5, 6, or 7, and you do something different in each case. If it's 5, flip the coin again and return either 0 or 1 based on the flip. If it's 6, flip the coin and return either 2 or 3. If it's 7, flip the coin; if it's heads, return 4, if it's tails start over.

The leftover entropy from our initial failed attempt gave us 3 cases (5, 6, or 7). If we just throw this out, we throw away log2(3) coin flips. We instead keep it, and combine it with the outcome of another flip to generate 6 possible cases (5H, 5T, 6H, 6T, 7H, 7T) which let's us immediately try again to generate a final answer with probability of success 5/6.

Here is the code:

```
# returns an int from [0, b)
def __gen(b):
  rand_num = 0
  num_choices = 1

  while True:
    num_choices *= 2
    rand_num *= 2
    if coin.flip():
      rand_num += 1

    if num_choices >= b:
      if rand_num < b:
        return rand_num
      num_choices -= b
      rand_num -= b

# returns an int from [a, b)
def gen(a, b):
  return a + __gen(b - a)

```

# Answer
> 1 votes
The simple answer?

If $b-a$ is not a power of 2, then after generating $r$, check whether it is in-range, and if not, generate it again.

The most likely time you will have to re-generate $r$ is when $b - a = 2^n + 1$ for some integer $n$, but even then it will have a greater than 50% chance of falling within range on each generation.

# Answer
> 1 votes
This is a proposed solution for the case when b - a does not equal 2^k. It is supposed to work in fixed number of steps (no need to throw away candidates which are outside your expected range).

However, I am not sure this correct. Please critique and help describe the exact non-uniformity in this random number generator (if any), and how to measure/quantify it.

Firstly convert to equivalent problem of generating uniformly distributed random numbers in range \[0, z-1\] where z = b - a.

Also, let m = 2^k be the smallest power of 2 \>= z.

As per the solution above, we already have a uniformly distributed random number generator R(m) in range \[0,m-1\] (can be done by tossing k coins, one for each bit).

```
    Keep a random seed s and initialize with s = R(m).

    function random [0, z-1] :
        x = R(m) + s
        while x >= z:
            x -= z
        s = x
        return x

```

The while loop runs at most 3 times, giving next random number in fixed number of steps (best case = worst case).

See a test program for numbers \[0,2\] here: http://pastebin.com/zuDD2V6H

# Answer
> 0 votes
If $2^{n-1} \< b - a ≤ 2^n$ then pick a number x, $0 ≤ x \< 2^n$, using n coin throws to determine the highest, second highest etc. bit of x. If x \< b-a then return a + x otherwise try again. As an optimisation, try again as soon as the throws so far tell you that $x \< b - a$ is not possible. For example if b - a = 33, and the first coin is 1 = 32, and the second coin is 1 = 16, then x ≥ 48 so restart already.

---
Tags: algorithms, probability-theory, randomness, random-number-generator
---


# Question
Title: Algorithm to generate points uniformly at random from a ball
Consider a 2-dimensional version of generating points in the circumference of a unit radius circle, independently generate each coordinate uniformly at random from the interval \[-1,1\].

How to generate a random point in a higher dimension? High level idea is also welcomed.

If we try to extend the above idea (2-dimensional version) it will not work as number of points inside the ball drops to zero as dimension become very high.

Note that this is not an assignment, I am reading data science currently and during reading I find out this question.

Edit: Uniformity means probability with equally likely outcomes enter link description here

# Answer
The textbook that you linked outlines a solution, in the part that begins "The solution is".

1. Generate $x\_1, ..., x\_d$ independently at random with a Gaussian distribution centered at the origin. The distribution of the vector $(x\_1, ..., x\_d)$ is then rotationally invariant.
2. Normalize the vector. This gets you a distribution that is uniform on the unit sphere.
3. Multiply the normalized vector by a random scalar between $0$ and $1$ with the probability distribution $ρ(r)=dr^{d-1}$.

Normalizing the vector is numerically unstable if its norm is small, so you might want to discard it and reroll in that case.
> 1 votes

# Answer
Think of a sphere centered in the origin and describe the points using spherical coordinates $(1, \theta, \phi)$ with $0 \le \theta \le \pi$ and $0 \le \phi \< 2\pi$.

Generate $\phi$ uniformly at random in its interval. Regarding $\theta$, pick it proportionally to the length of the circumference at angle $\theta$. I.e., its density function $f$ is such that $$ f(\theta) \propto 2\pi |\cos(\theta)|. $$

You can compute the proportionality constant as follows: $$ \int\_{\theta=0}^{\pi} 2 \pi |\cos(\theta)| \\, \text{d}\theta = 4\pi\int\_{\theta=0}^{\pi/2} \cos(\theta) \\, \text{d}\theta =4 \pi. $$

Then we have $f(\theta) = \frac{1}{2} | \cos(\theta) |$. The cumulative distribution function for $\theta \le \pi/2$ is: $$ F(\theta) = \int\_{\psi=0}^\theta \frac{1}{2} \cos(\psi) = \frac{1}{2}\sin(\theta), $$ and for $\theta \> \pi/2$ it is $F(\theta) = 1 - F(\pi-\theta) = 1-\frac{1}{2} \sin(\pi - \theta) = 1- \frac{1}{2}\sin(\theta)$.

To choose $\theta$ you can first pick a number $\psi$ uniformly at random in $\[0,1\]$ and then let $\theta = F^{-1}(\psi)$, where: $$ F^{-1}(\psi) = \begin{cases} \arcsin(2\psi) & \text{if } \psi \le \frac{1}{2}, \\ \arcsin( 2(1-\psi) ) & \text{if } \psi \> \frac{1}{2}. \end{cases} $$
> 1 votes

---
Tags: algorithms
---


# Question
Title: Does the concept of "side-effect" predate functional programming?
When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before the invention of the functional programming paradigm, but the author is asking for a citation that I was not able to find. Does the concept of "side-effect" actually predate functional programming, or is the author right?

# Answer
The earliest usages of the term that I'm aware of are in regard to Algol 60, one of the first languages to be (or attempted to be) defined by a specification. When people started implementing it, they found that desirable optimizations (such as reordering expressions) could not be performed if the order of evaluation matters, which is possible only if side-effects are permitted. Also, side-effects may be considered mathematically inelegant, and one goal of the Algol effort was to produce a formal notation for algorithms.

Now, for some actual citations:

* In “ALGOL 60 maintenance” (ALGOL bulletin **10**, 1960), M. Woodger comments on the current draft of the specification, stating “It is quite unreasonable to allow the evaluation of expressions to induce side-effects”.
* Samelson and Bauer (ALGOL bulletin **12**, 1961) concur strongly, calling side-effects “preposterous”.
* Dijkstra, on the other hand, in a letter to the editor, asserts that side-effects can be useful, e.g., in writing a random number generator.
* Knuth, in “ALGOL 60 confidential” \[Communications of the ACM **4**(6), 1961\], discusses the problem of side effects being poorly defined by the specification (it was unclear whether they were allowed or forbidden, and whether the order of evaluation was prescribed at all), although he does not use the term “side-effect”.
* Knuth again, in “The remaining trouble spots in ALGOL 60” \[Communications of the ACM **10**(10), 1967\] contains extensive commentary on side-effects and how they affect Algol 60 programmers and implementors.

Unrelated to Algol:

* Leavenworth's “FORTRAN IV as a syntax language” \[Communications of the ACM **7**(2), 1964\] considers how side-effects may be convenient alongside short-circuiting boolean expressions.
* Abrahams et al., in “The LISP 2 programming language” \[Proceedings of AFIPS '66\], use the term in noting that their compiler always treats the order of evaluation as undefined, unless the code uses a special operator `ORDER` to force left-to-right.
> 3 votes

# Answer
The term and intuitive notion of a *side effect* of course predates functional programming. So your question is really, does the meaning of *side effect* in programming languages (i.e., a function which has effects beyond its input-output behavior) date back to functional programming? To this I think the answer is yes for trivial reasons, if "functional programming" is interpreted broadly: the *definition* of a side effect is in terms of a function's *input-output behavior*, which is exactly the meaning of a functional program. So as long as people were studying side effects, they were doing so in contrast to pure functional programs.

It is also not easy to put a start date on the study of functional programming, which is why I adopt this broad view. Functional programming traces its roots back to Alonzo Church and the lambda calculus. At that time, people were already aware of the meaning of programs and the equivalence between different models of computation. The usage of the term *side effect* for programs entails an understanding of program input-output behavior which implies an understanding of what a purely functional program is.

For what it's worth, the earliest instance of "side effect" I could find in this usage, in papers indexed by Google Scholar, was in the study of LISP in the 1970s. Though I would not be surprised if there are earlier instances.

* *Output driven interpretation of recursive programs, or writing creates and destroys data structures,* Friedman, Daniel P., and David S. Wise. Information Processing Letters, 1976. Paywalled link.
> 2 votes

---
Tags: terminology, programming-languages, functional-programming, history
---


# Question
Title: Efficiently count distinct in large range
I have a pubsub channel where an event is fired every time a user logs in, and I want to be able to query the unique users in a date range.

Solutions I thought:

* Put the data in bigquery, and then use `APPROX_COUNT_DISTINCT`, but it's too expensive
* Same as above, plus a cache. Past data doesn't change, so it's a good approach, but still very expensive because I would need to import the pubsub channel in bigquery
* Precompute daily uniques, and then do something very rough like `max(range)^log(days)`

I was also thinking about storing a 64 bytes bloom filter and a counter per day, then merge the filters in range and do some estimation on the count, but I couldn't find any paper on it.

Any better idea?

If it can be helpful we're speaking about 2/3 gb of data per day, around 6 months and growing.

# Answer
> 2 votes
I think the Google Scholar keywords you're looking for are "sliding window" and "hyperloglog". I found "Cardinalities estimation under sliding time window by sharing HyperLogLog Counter" and "Sliding HyperLogLog: Estimating cardinality in a data stream".

For a simple version, you can store a HyperLogLog sketch for each day and then merge the sketches to get an estimate, but this scales as $m$, the number of days you query.

Finally, you could store a Merkle tree of merged HLL sketches, making counting take $\lg\_2 m$ HLL merges and one HLL estimation.

---
Tags: counting, bloom-filters
---


# Question
Title: Proof in the "Reaching Agreement in the Presence of Faults"
I am reading the "Reaching Agreement in the Presence of Faults", M. Pease et al and trying to understand their proof for the $n \geq 3m+1$ case.

In the induction step $m \gt 0$ it says the following:

> ... Any other set satisfying these requirements, moreover, must contain a nonfaulty processor (since it must be of size $\gt \frac{(n + m)}{2}$, and $n \ge 3m + 1$) and must therefore also yield $V\_q$ as the common value. The algorithm thus terminates at step (1), and $p$ records $V\_q$ and $q$ as required...

This is not obvious to me and seems wrong. For example, assume $Q$ is a set of processors of length $\ \ge \frac{n+m}{2}$ where only one is a faulty processor $f$ and rest are nonfaulty. Now we consider all strings $w$ of length $\le m$ of this set and in particular $\sigma\_p(pfq)$. Since $f$ is a faulty processor it can return any value, not necessarily $V\_q$, thus there cannot be a common value between all $w$ strings. This means that any set $Q$ that contains at least one nonfaulty processor cannot be used at all.

Is my understanding wrong?

# Answer
What is important about the paragraph above are the few lines that proceed it in the proof. This is all under the context of *"First note that if q is nonfaulty"*. If we know that q is nonfaulty, then we know that q has sent the same value of its internal state, Vq, to every processor. Therefore, if we have a subset of processors that meet the requirements of all reporting to p that all of them have received the same value from everyone else in the subset for Vq, and the subset includes at least 1 nonfaulty processor **and** we are in the scenario that q is nonfaulty, then we know no matter which subset this happens to be, there can only be one value of Vq which could possibly be used in generating such a set (i.e. the true internal state of q)
> 1 votes

# Answer
The word "requirements" is the key to solve the question. the requirements mean: (1) some subset Q ofPofsize \>(n + m)/2 (2) some value v,op(pwq) = v for each string w over Q of length \_\<m, p records v. The second requirement is very important, which solves your question.
> 0 votes

---
Tags: distributed-systems, information-theory, fault-tolerance
---