# Question
Title: Increased rounding relative error when subtracting
I'm reading the book "Lessons in Scientific Computing" by Schoerghofer and it says:

> If x and y are real numbers of the same sign, their sum x + y has an absolute error that adds the two individual absolute errors, and the relative error is at most as large as the relative error of x or y. Hence, adding them is insensitive to roundoff. On the other hand, x−y has increased relative error.

I am not sure how to obtain the result for subtraction, i.e. how to show for $$ x(1+\epsilon\_x)-y(1+\epsilon\_y) = (x-y)(1+\epsilon) $$ that $\epsilon\ge\max(\epsilon\_x,\epsilon\_y)$.

# Answer
> On the other hand, $x−y$ has increased relative error.

The correct conclusion should be $x-y$ may have increased relative error. In other words, $x-y$ may have decreased relative error.

---

Let us review what is absolute error and relative error in scientific computing.

The absolute error in approximating $x$ by $\hat x$ is $e = e\_x= e\_{x, \hat x}= \hat x − x$. The relative error is $\epsilon =\epsilon\_x=\epsilon\_{x,\hat x}=\dfrac ex$, a dimensionless measure of error which is usually considered more informative.

Yuval has shown an extreme example where the relative error becomes 0. Here are a few more examples on the relative error of approximating $d=x-y$ by $\hat d =\hat x-\hat y$.

1. $x=2$, $\hat x=2.04$, $y=1$, $\hat y = 1.03$. Then $\epsilon\_x = 0.02$, $\epsilon\_y=0.03$, $d=1$, $\hat d=1.01$, $\epsilon\_d=0.01$.
2. $x=4$, $\hat x=4.04$, $y=1$, $\hat y = 0.95$. Then $\epsilon\_x =0.01$, $\epsilon\_y=0.05$, $d=3$, $\hat d=3.09$, $\epsilon\_d=-0.03$.
3. $x=21$, $\hat x=21.4$, $y=20$, $\hat y = 20.2$. Then $\epsilon\_x \approx 0.019$, $\epsilon\_y=0.01$, $d=1$, $\hat d=1.2$, $\epsilon\_d=0.2$.
4. $x=2100$, $\hat x=2140$, $y=2098$, $\hat y = 2096$. Then $\epsilon\_x \approx 0.019$, $\epsilon\_y\approx0.00095$, $d=2$, $\hat d=44$, $\epsilon\_d=22$.

We can make several observations.

The example 1 shows the relative error of the difference can be smaller than both original relative errors while example 2, 3 and 4 demonstrate the absolute value of the relative error can be bigger than one or both of the original relative errors. In particular, the example 4, where $\epsilon\_d = 2310\max(\epsilon\_x, \epsilon\_y)$ illustrates the relative-error explosion where the relative error can go wildly larger when the two original values, which are 2100 and 2098 here, are near to each other.

---

Exercise 1. Let $x=cy$ for $x, y\>0$. Let $\hat x=x(1+\epsilon\_x)$, $\hat y = y(1+\epsilon\_y)$. Let $d=x+y$ and $\hat d=\hat x+\hat y$. Then $$|\epsilon\_d|\le\max(|\epsilon\_x|,|\epsilon\_y|)$$

Exercise 2. Let $x=cy$ for $x, y\>0, c\>1$. Let $\hat x=x(1+\epsilon\_x)$, $\hat y = y(1+\epsilon\_y)$. Let $d=x-y$ and $\hat d=\hat x-\hat y$. Then $$|\epsilon\_d|\lt \frac {2c}{c-1}\max(|\epsilon\_x|,|\epsilon\_y|)$$
> 1 votes

# Answer
You can't prove it because it's not true. For example, $x(1+\epsilon) - x(1+\epsilon) = 0$. What you can say is that if all you know is that $x$ has relative error $\epsilon$ then the best bound on the relative error of $x-y$ is larger than $\epsilon$. This is because $$ \frac{x(1+\epsilon)-y}{x-y} = 1 + \frac{x}{x-y} \epsilon. $$
> 0 votes

---
Tags: arithmetic, floating-point, rounding
---


# Question
Title: Data hazard after in load word after addi
5 stage pipline

```
addi $t1,$zero,0x30
lw $t2,0($t1)
sw $t2,0xff18($zero)
addi $t2,$zero,100

```

Question is to find hazards existing in the code and the answer is:

* Hazard 1: Between lines 1 and 2. Register t1. Solved using forwarding.
* Hazard 2: Between lines 2 and 3. Register t2. Solved using forwarding.

But I found the answer is rather strange,

* So there is a hazard between line 1 and 2, in the first line t1 writes back in the fifth stage, and in the second line t1 uses in the decode stage, in my opinion there should be a stalling first and then forward to have access to t1 in the second line.
* I don't see a hazard between line 2 and 3? line 2 t2 write back in the fifth stage, and line 3 fetches t2 in the first stage

Am I thinking something strange, why the correct answer seems not correct to me?

# Answer
> 2 votes
THe answers are correct. There is a data hazard when the information stored in the "regular" location (generally a data reg) is incorrect with respect to the program flow.

Here information copied in the ID stage at line 2 will be the previous value of $t1, as the new one will be copied at the end of WB stage of instruction 1 (and hence at the end of MEM stage of instr 2).

Forwarding means discarding the regular information and replacing it by the new (and correct value). It can be done

1/ as soon as the new value is available *in the processor*. Lets call t\_a this time

2/ up to the last time that this information is required (because it will be transformed by the ALU, written to the mem, etc). Lets call t\_u this instant

If t\_a \<= t\_u, simple forwarding can be done. Otherwise one or more stalls are required.

Lets look at the code

```
1 addi $t1,$zero,0x30
2 lw $t2,0($t1)

```

Say Stage IF of instr 1 is t1, ID t2, etc

1 the new value of $t1 will be available at the end of stage WB (t5)

2 the value of $t1 is read at the start of ID stage (t3)

There is a data hazard.

When is the *information* associated with $t1 available ? After EX stage of 1. So t\_a=t3

When is the last time that this information is required by instruction 2 ? Just before the adresse (0+$t1) is computed by the ALU. I.e. t\_u=t4

There is no need of any stall. The value read in $t1 register is just discarded and replaced by the one in the ppline register.

Consider now instructions 2 and 3.

```
2 lw $t2,0($t1)
3 sw $t2,0xff18($zero)

```

There is a hasard as $t2 is written at the end of WB stage of inst 2 (t6) and read at the beginning of ID stage of inst 3 (t4).

When if the *information* associated with $t2 available *in the processor*. At the end of MEM of instr 2 it is written in some ppline reg of the proc (t5=t\_a).

When is this information *required* ? Just before writing to the memory by inst 3. After it is too late. That is at the start of MEM stage of inst 3 t6=t\_u.

Again a simple forward can solve the problem.

(note that if instr 3 had been sw $t5,0xff18($t2) the situation would have been different. $t2 would have been required for the address computation (*start* of EX stage of inst 3 at t5), that is *before* its production (*end* of MEM of instr 2 t5), and a stall would have been required over the forwarding.)

---
Tags: computer-architecture, mips
---


# Question
Title: Why researchers don't study the parameterizations of the problems unlikely to be NP-Hard?
I have seen the parameterization of the very well known problems like vertex cover, hitting set etc which are NP-hard (NP-complete precisely). Many researchers in the past have been studied the parameterization of these problems. My question is why researcher's don't study the parameterizations of the problems unlikely to be NP-Hard?

# Answer
This is not true, there is a program known as "FPT inside P" where we look for interesting parameterizations for problems inside P. The results are perhaps indeed more scattered as opposed to FPT for hard problems which you tend to see much more.

For example, look at the work of Niedermeier and others \[1,2\] for graph matchings. There is also work for longest path on interval graphs \[3\]. You will find more by looking at papers that reference the ones mentioned.

---

\[1\] Korenwein, Viatcheslav, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. "Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments." In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

\[2\] Mertzios, George B., André Nichterlein, and Rolf Niedermeier. "The power of linear-time data reduction for matching." Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017.

\[3\] Giannopoulou, Archontia C., George B. Mertzios, and Rolf Niedermeier. "Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs." Theoretical Computer Science 689 (2017): 67-95.
> 7 votes

# Answer
Most problems that aren't NP-hard are in P, so they're trivially fixed-parameter tractable.

That only leaves NP-intermediate problems such as graph isomorphism and integer factoring, or the possibility of using tighter notions of FPT, such as fixed-parameter linearity.
> 3 votes

---
Tags: complexity-theory
---


title: Cover the maximum of elements

text:
# Question
Title: Cover the maximum of elements
I have a collection of subsets $\\{S\_1,\ldots,S\_m\\}$ where each $S\_i\subset \\{1,\ldots,n\\}$. I would like to cover the maximum number of elements from $\\{1,\ldots,n\\}$ by choosing a single element from each $S\_i$. What is the optimal way to do this?

For example, say I have $S\_1=\\{1\\}$ and $S\_2=\\{2,3\\}$ and $S\_3=\\{3\\}$ and $n=3$. If my algorithm picks randomly (or the maximum number say) a number from each $S\_i$, then I could obtain a solution that covers only $\\{1,3\\}$ but there is a solution that covers all elements.

# Answer
> 2 votes
This problem is the same as the problem of finding the maximum matching in bipartite graphs, which can be solved by the Ford-Fulkerson algorithm in $O((n+m)s)$ time or the Hopcroft-Karp algorithm in $O(\sqrt{n+m}s)$ time, where $s$ is the number of elements in all $S\_i$ combined.

---

Given a collection of subsets $\\{S\_1,\ldots,S\_m\\}$ where each $S\_i\subset \\{1,\ldots,n\\}$, let $G$ be the graph with nodes $\\{1, 2, \cdots, n, S\_1,S\_2,\cdots,S\_m\\}$. Whenever $j\in S\_i$, there is an edge $e\_{j,S\_i}$ in $G$ that connects node $j$ and node $S\_i$. $G$ is a bipartite graph with vertex sets $X=\\{1, 2, \cdots, n\\}$ and $Y=\\{S\_1,S\_2,\cdots,S\_m\\}$

Suppose we have selected $k\_i$ from $S\_i$ for all $i$. Having removed duplicate numbers among ${k\_1}, {k\_2}, \cdots, {k\_m}$, we can assume $\\{k\_i\mid i\in I\\}$ for some $I\subseteq \\{1,2,\cdots,m\\}$ is the set of distinct numbers among them. Then $\\{e\_{k\_i, S\_i}\mid i\in I\\}$ is a matching in $G$.

Conversely, if we have a matching $\\{e\_{k\_i, S\_i}\mid i\in I\\}$ in $G$ for some $I\subseteq \\{1,2,\cdots,m\\}$, we can select $k\_i$ from $S\_i$ when $i\in I$ while selecting any element from $S\_i$ when $i\not\in I$.

The above two conversions show that the problem in the question, finding the maximal number of selected elements is the same as the problem of find the cardinality of the maximum matching in a bipartite graph. Note that the conversion takes linear time or polynomial time depending on which parameters are used.

---

Here is a variation for which I do not know if there exists a polynomial algorithm.

**Problem**. What if we select two elements from each set, assuming each set has at least two elements?

# Answer
> -1 votes
This is the hitting set problem, you can find greedy algorithm for solving it.

---
Tags: algorithms
---


# Question
Title: What are the things one can do with the internet without the World Wide Web?
If the question above makes any sense!

# Answer
> 3 votes
Lots of Internet services people use daily are not based on the WWW. A few examples from the top of my mind: email (POP/IMAP protocols), copy files remotely (FTP), login into a remote server (SSH), instant messaging, file sharing, gaming, newsgroups, anything. The World Wide Web, in this respect, is just one particularly successful Internet service.

---
Tags: computer-networks
---


# Question
Title: Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?
I think I'm able to prove NTIME($n^\alpha$) $\subset$ EXPTIME for arbitrary $\alpha$.

* Is this a new result?
* If it was, would there be a way to deduce NP $\subset$ EXPTIME from it?

# Answer
> 1 votes
Upon reflection this is an easy consequence of the Time Hierarchy Theorem.

* NTIME$(n^\alpha) \subseteq$ TIME$\left(2^{n^\alpha}\right)$ by brute force
* TIME$\left(2^{n^\alpha}\right) \subset$ TIME$\left(2^{n^{2\alpha}}\right)$ by the Time Hierarchy Theorem
* TIME$\left(2^{n^{2\alpha}}\right) \subseteq$ EXPTIME obviously

So there's nothing new here.

# Answer
> 1 votes
As you've already shown, $\mathrm{NTIME}\[n^\alpha\]\subsetneq\mathrm{EXPTIME}$ isn't new, as it follows easily from the time hierarchy theorem.

Furthermore, the fact that, for some class $X$, $\mathrm{NTIME}\[n^\alpha\]\subsetneq X$ for all $\alpha$ doesn't imply that $\mathrm{NP}\subsetneq X$. For example, the time hierarchy theorem tells us $\mathrm{NTIME}\[n^\alpha\]\subsetneq\mathrm{NP}$ for all $\alpha$ but that certainly doesn't imply that $\mathrm{NP}\subsetneq\mathrm{NP}\\,$!

---
Tags: time-complexity, np
---


# Question
Title: How to construct Context Free Grammar of words with equal number of 0's and 1's
i am trying to find a cfg for this cfl

L = $\\{ w \mid w \text{ has an equal number of 0's and 1's} \\}$

is there a way to count the number of 0's or 1's in the string?

# Answer
> 8 votes
The question defining a context-free grammar for $\\{\in\\{0,1\\}^\*:\\#\_0(w)=\\#\_1(w)\\}$ restricts its answers to one particular grammar and the proof for its correctness is somewhat involved. Here I would like to show a different grammar that is easier to figure out.

Since the requirement is the same number of 0's and 1's, we can grow the start non-terminal $S$ by a pair of 0 and 1 in all sorts of way. (This is more or less what your idea of "counting" should be). We will have the following production rules, $$S\to S01\mid S10\mid 01S\mid 10S\mid 01S\mid 10S\mid \epsilon.$$

However, if we check closely, the above grammar does not generate 00111100. What happens is that the above grammar will generate the first part 0011 as a whole, missing the second part 1100. That suggests us to add another rule $S\to SS$. Once we have added that rule, rules $S\to S01\mid S10\mid 01S\mid 10S$ become redundant. The final grammar is $$S\to SS\mid 0S1\mid 1S0\mid \epsilon.$$

---

It is clear that the word generated by that grammar has the same number of 0's and 1's.

**Are all such words generated by that grammar?**

The rule $S\to\epsilon$ show that unique word of length 0 can be generated.

As the induction hypothesis, suppose all words of length less than $2n\le2$ can be generated.

Let $w$ be such a word of length $2n$.

Let $d(k)$ be the difference of the number of 0's and the number of 1's in the first $k$ letter of $w$. In particular, $d(2n)=0$. Since the situation is symmetric with respect to 0 and 1, WLOG assume $w$ starts with a 0, i.e., $d(1)=1$.

* If $w$ ends with a 1, then $w=0w'1$ for some word $w'$. $S$ generates $w$ since $w'$ have the same number of 0's and 1's and $w'$ is shorter than $w$. So $S\Rightarrow0S1\Rightarrow0w'1=w$.
* If $w$ ends with a 0, then $d(2n-1)=-1$. Since $d(x)$ changes 1 by 1, $d(k)=0$ for some $1\lt k\lt 2n-1$. Let $w\_1$ be the first $k$ letters of $w$ and $w\_2$ the rest of $w$. By induction hypothesis, $S\Rightarrow w\_1$ and $S\Rightarrow w\_2$. Hence $S\Rightarrow SS\Rightarrow w\_1w\_2=w$.

We have completed mathematical induction. All such words can be generated.

---

**Exercise**. $L$ cannot be generated by a context-free grammar that has no non-terminal other than the start symbol and has no production rule in which the start symbol appears on the right-hand side more than once. In other words, a context-free grammar for $L$ must contain either at least two non-terminals or a production rule that contains two $S$s on the right hand side, such as $S\to SS$ or $S\to 0S1S$.

# Answer
> -1 votes
S → B1S | S1B | 1SB | 1BS | BS1 | SB1 | ɛ

B → 0

Basically, this is it. For every 1 it puts, it says that there have to be a derived 0 in the string, so it stays balanced. Every order of 1's and 0's can be derived.

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


# Question
Title: Buchi automata in formal software verification
As I am studying the application of Buchi automata in formal software verification, I am interested in the computational complexity (or links to papers) for the algorithms used to solve the problem in practice.

Let me recall the mathematical intuition behind model checking using these techniques. Buchi automata are the automata associated to $\omega$-regular languages. You can think of these languages as the infinite version of the regular languages (infinite in the sense that they operate on infinite words). As regular languages, they enjoy closure properties under composition and intersection. It is also well known that these Automata are "isomorphic" to proposition of a logic called S1S. This is the logic of Monadic Second Order Logic (i.e. you can have quantification of on the predicates of the logic, but the elements can ranges over a finite set). S1S has the nice property of being decidable, i.e. for each preposition we can tell if it is true or not. To find if a S1S formula is satisfiable, we can find if the associated atomata has an accepting state. In Buchi automata this is done by finding cycles between the starting state and any final state.

To find a "bug" in a software we proceed like this:

* we formalize our software as $\mathbb{S}$ using a S1S logic (a monaidic second order logic).
* we formalize the security properties of our software in the logic $\mathbb{P}$
* now we use closeness properties of $\omega$-languages, whose associated automata are equivalent to S1S logic: we build Buchi automata of $\overline{\mathbb{S}} \cap \mathbb{P}$

In this way, if the software **does not** comply to the security properties, the resulting automata will have *at least* an accepting state. In practice, the accepting state of a Buchi automata can be found by finding *a* cycle in the associated graph between the starting state and *any* final state.

I suspect in practice an algorithm for **cycle detection** cannot be used. This is due to the constraint that the cycle should pass from the only starting state and should pass through an accepting state, so the likelihood of finding the cycle you need might be very low. Anyway, the best algorithm for Cycle detection is solved by the Johnson Algorithm in time $O((n + e)(c + 1))$ and space bounded by $O(n + e)$).

In practice, S1S decidibility using Buchi automata might be best to be solved with s-t connectivity. For instance, NetworkX solves s-t connectivity with this algorithm by Abdol-Hossein Esfahanian.

Am I correct?

Which graph algorithm is used in practice to solve S1S satisfiability using Buchi automata?

I have found this, but it just shows a better reduction from S1S to Buchi, and it doesn't talk about graphs.

# Answer
> 1 votes
A Buchi automaton has a non-empty language if and only if there is an accepting **lasso**, i.e., a path from an initial state to some lasso starting state $s$, and a loop from $s$ to itself along which an accepting state is reached.

There is a very simple linear-time algorithm for this problem that model checkers such as spin implement. Javier Esparza has a nice slide set on this problem that can be found here. I've never heard of Johnson's Algorithm or s-t connectivity being used to find words accepted by Buchi automata - at the very least, they appear to be much more complicated than the standard solution. You will also find the algorithm in the book "Model Checking" by Clarke, Peled, and Grumberg, as well as the book "Principles of Model Checking" by Baier and Katoen.

Note that S1S is a logic that is quite useful in theory to characterize what can be expressed with Buchi automata. It is possible that by restricting your search to publications and book that mention S1S, you are missing out a lot of research. There is a lot of semi-applied research that does not use S1S, but rather uses logics such as linear temporal logic (LTL) to express properties of programs. The reason that translating from logics such as LTL has a much lower complexity (it is only exponential instead of non-elementary as in the S1S case). So it is much easier to build scaling tools for the translation. For this reason, all practically available mature tools for the translation that I am aware of use a logic other than S1S. While the non-elementariness of the translation does not rule out that there *could* be tools that are efficient in practice, S1S is also criticized for being quite hard to specify in.

There is another efficiency problem with your approach: You translate the program you want to check to S1S. Now since the translation from there to Buchi automata is non-elementary *and* programs are typically non-trivially large, you will not be able to use this approach without extremely good translation tools that make use of all kinds of heuristic optimizations. It's much easier to translate the program directly to a Buchi automaton that represents all of its executions and then make the language intersection with the specification on the automaton level. Now you mentioned security properties, and I'm not sure how exactly you would have to adapt this approach to cover meaningful security properties. But for classical reactive system properties (safety, liveness), this is the usual approach.

# Answer
> 1 votes
The fastest theoretical algorithm to solve Büchi Games in **game graphs** is presented in \[1\] and runs in $O(n^2)$: The algorithm uses a hierarchical decomposition approach. An easier folklore algorithm with $O(mn)$ running time using just the attractor concept is mentioned.

Büchi Games on **graphs** should be in linear time after computing the strongly connected components of the graph.

\[1\] Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition. J. ACM, (2014)

---
Tags: formal-languages, formal-grammars, formal-methods, model-checking, buchi-automata
---


# Question
Title: Dijsktra's algorithm applied to travelling salesman problem
I am a novice(total newbie to computational complexity theory) and I have a question.

Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it?

From a start point we compute the shortest distance between two points. We go to the point. We delete the source point. Then we compute the next shortest distance point from the current point and so on...

Every step we make the graph smaller while we move the next available shortest distance point. Until we visit all the points.

Will this solve the traveling salesman problem.

# Answer
Dijkstra's algorithm returns a shortest path tree, containing the shortest path from a starting vertex to each other vertex, but not necessarily the shortest paths between the other vertices, or a shortest route that visits all the vertices.

Here's a counter example where the greedy algorithm you describe will not work:

Starting from $a$, the greedy algorithm will choose the route $\[a,b,c,d,a\]$, but the shortest route starting and ending at $a$ is $\[a,b,d,c,a\]$. Since the TSP route is not allowed to repeat vertices, once the greedy algorithm chooses $a,b,c,d$, it is forced to take the longest edge $d,a$ to return to the starting city.
> 24 votes

# Answer
As it already turned out in the other replies, your suggestion does not effectively solve the Travelling Salesman Problem, let me please indicate the best way known in the field of heuristic search (since I see Dijkstra's algorithm somewhat related to this field of Artificial Intelligence).

A heuristic algorithm can return optimal solutions (though the sizes it can manage are relatively small as a matter of fact) and the following method was suggested by Richard Korf in the 90s. While it works perfectly for the symmetric travelling salesman problem (where the cost of the edge $(u,v)$ equals the cost of the same edge when traversed in the opposite direction $(v,u)$), it can be easily adapted to the alternative case of the asymmetric version.

The best approach (I am aware of) consists of running a Depth-First Branch-and-Bound heuristic search algorithm where the heuristic is the cost of the Minimum Spanning Tree (MST). Since the MST can be computed in polynomial time with either the Prim's algorithm or the Kruskal's algorithm, then it can be expected to return solutions in a reasonable amount of time. For a wonderful discussion of these two algorithms I do strongly suggest you to have a look at The Algorithm Design Manual

As a matter of fact, let me highlight that since this approach was suggested not much progress have been seen in the field for deriving optimal bounds of this problem so that I do consider it to be a hot question in the field of combinatorial search.

Hope this helps,
> 10 votes

# Answer
I have no idea how anyone here didn't notice that the application of Dijkstra's algorithm would be entirely unnecessary in this case? You could implement this greedy algorithm by simply selecting the closest node, which is known apriori. Dijkstra's algorithm is used for discovering paths, but you are only taking a single step each time. This obviously does not find the optimal solution to the TSP, but many very good approaches do not find it either. All optimal solution finders for TSP are very computationally demanding.
> 2 votes

# Answer
The answer is no, that's not a good way of solving the TSP problem. A good counter example is where all the points are on a line, like the following:

--5------------------3-----1--0---2----------4

using Dijsktra's algorithm, would make the poor salesman starting at point 0, first go to 1 then to 2 then to 3 ect. which is not the optimal.

Hope that helps. Have a look at the first chapter in Steven S. Skiena excellent book called "The Algorithm Design" it explains this example in more detail.

The TSP problem is not finding the shortest way between two points, but in making a route between all the points which are optimal. When you have the optimal route you can use Dijsktra to find the shortest path between each points in the route.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: what does this phrase mean: "train a policy network"
I am familiar with the basics (and perhaps a substantial amount of basics) of imitation learning and reinforcement learning. In IL (imitation), we take demonstrations from an assumed expert, which we also assume has the most efficient policy.

What does this statement mean: This will train a policy network using the expert dataset and store the results.

Question: Why do I need to TRAIN a policy network? What is it for? Are there any algorithms that come with this training a policy?

Thanks

# Answer
A policy is just a response or action given a state (situation). Training a neural network with samples from an expert is just searching for a function F that efficiently maps states to actions.

For example for chess, a neural network can be trained with the action to be taken in a given state of the board. This can be trained using a database of existing (human) expert games. The resulting network is a policy network that maps a given board setup (state) to the chess move to be executed in that state that more likely leads to a win (action).
> 1 votes

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


# Question
Title: Looking for an algorithm to generate an identicon/avatar from genome data
I am looking to develop an app that generates a single identicon image that summarizes the genome information in visual form.

Identicons are essentially a visual hash of of data. usually string data such as an IP address or name. In this case, rather than generating an identicon from a single piece of string data. I want to use the entirety of the genotype information (the 4th column) to summarize this data into a graphical representation as a way to visually identify someone from their partial genome.

The input file is a tab-separated file consisting of 600,000 rows. Each row contains the chromosome identifier (There are 23 in total: 1-20, X, Y or MT), the position of the single nucleotide polymorphism (SNP) and the genotype (a two character variation of G,A,T or C). Below is a two line excerpt from the file.

```
#RSID        Chromosome   Position  Genotype
rs7537756       1         854250    AG
rs13302982      1         861808    GG

```

Using the Chromasome, Position and Genotype columns. I would like to generate an abstract identifying image from this data. Since there is far too much data, this image does not need to capture the data, only summarize it in a visual fashion. The goal is to setup a service that analyzes anyone's genome file and generates an identicon that is unique to them.

For more information on identicons See the wiki page

# Answer
> 1 votes
If all you want is uniqueness, you could use a *visual hash*. Hash all of the data (say, with SHA256), then apply a visual hash.

A visual hash is a function $H$. Given a short binary string $x$ (say, 256 bits long), the visual hash computes $H(x)$, a random picture that is a visualization of $x$. The output of the hash is a visualization of the string -- a picture or image of some form -- with the property that different binary strings will lead to different images. Also, $H$ is a deterministic algorithm, so if you hash the same binary string twice, you'll get the same picture both times.

Below I list some visual hash schemes that have been proposed, along with sample images produced by each scheme.

## Random Art for PGP keys

https://user.xmission.com/~atoponce/art/

(As you'll notice, this is actually a visualization of multiple different schemes at once.)

See also the following research paper:

Hash Visualization: a New Technique to improve Real-World Security. Adrian Perrig and Dawn Song. Proceedings of the International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC), Hong Kong, July 1999.

## VizHash GD

http://sebsauvage.net/wiki/doku.php?id=php:vizhash\_gd

## JrSnowflake

https://wiki.debian.org/JrSnowflake

Older: README, source

## OpenSSH's Visual Host Key

```
+--[ RSA 2048]----+
|   .+            |
|   + o           |
|  o o +          |
|   + o +         |
|  . o E S        |
|   + * .         |
|    X o .        |
|   . * o         |
|   .o .          |
+-----------------+

```

https://stackoverflow.com/a/3601278/781723

# Answer
> 1 votes
**Use the Edinburgh Genome Foundry**

This answer is rather late to the party but may be useful to others seeking a library.

The Edinburgh Genome Foundry provides a range of useful DNA manipulation tools and releases their code under the MIT licence.

In the case of the genome identicon, they provide the sequenticon project which provides a standard set of colours and patterns for use in laboratories.

---
Tags: genetic-algorithms, mathematical-analysis
---


# Question
Title: Is the set of surjective recursive functions in RE/coRE?
Let L be a set of recursive funtions with $L = \\{i\in \mathbb{N}|f\_i\space is\space surjective\\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$?

I can't think of a way to show either of the two.

# Answer
Rice-Shapiro proves that $L$ is not RE nor coRE.

Let $F$ be the set of computable surjective functions. $L$ is the the index set associated to $F$.

Assume by contradiction $L$ is RE. By Rice-Shapiro (compactness), since the identity function belongs to $F$, some finite restriction of the identity must belong to $L$ as well. But a finite-domain function can not be surjective -- contradiction.

Assume by contradiction $\bar L$ is RE. The always undefined function $g$ belongs to $\bar F$, so by Rice-Shapiro (monotonicity), $\bar F$ contains any computable extension of $g$, including the identity function, which is surjective. Contradiction.
> 1 votes

---
Tags: computability
---


# Question
Title: Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1
**Problem statement**: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n \> 1$, and $T(1)=1$.

**My attempt**: I tried back substituting but I am unable to find a general pattern: $$\begin{align\*} T(n) &=2^2 T(n-2)+3n-2 \\ &=2^3 T(n-3)+7n-10 \\ &=2^4 T(n-4)+15n-34 \\ &=\cdots \end{align\*}$$

# Answer
Hint: $$\begin{align\*} T(n) &= 2T(n-1) + n \\ &= 2^2 T(n-2) + (2n + n) - 2 \\ &= 2^3 T(n-3) + (2^2n + 2n + n) - (2^2 \cdot 2 - 2) \\ &= 2^4 T(n-4) + (2^3n + 2^2n + 2n + n) - (2^3 \cdot 3 + 2^2 \cdot 2 + 2^1 \cdot 1) \\ &= \cdots \end{align\*}$$

If you are familiar with the required methods, you can also solve it using generating functions (and, e.g., techniques from here or chapter 7 of "Concrete Mathematics" by Graham, Knuth, et al.).
> 2 votes

# Answer
A different general method to solve these recurrences is to frame them as a matrix multiplication :

$$ \left( \begin{matrix}T\_{n+1}\\ n+1 \\ 1\end{matrix} \right) = \left( \begin{matrix}2T\_{n}+n+1\\ n+1 \\ 1\end{matrix} \right) = \underbrace{\left( \begin{matrix}2&1&1 \\ 0&1&1 \\ 0&0&1\end{matrix} \right)}\_M \left( \begin{matrix}T\_{n}\\ n \\ 1\end{matrix} \right) $$

Now you have: $$ \left( \begin{matrix}T\_{n}\\ n \\ 1\end{matrix} \right) = M^n \left( \begin{matrix}1\\ 1 \\ 1\end{matrix} \right) $$

You can get $M^n$ in $O(log(n))$ time through exponentiation.
> 2 votes

# Answer
Another option is to consider the related sequence $S(n) = T(n)/2^n$, which satisfies the recurrence $$ S(n) = S(n-1) + \frac{n}{2^n}, $$ whose solution is simply $$ S(n) = S(1) + \sum\_{m=2}^n \frac{m}{2^m}. $$ The sum can be evaluated in many ways, for example (adding the $m=1$ term) $$ \sum\_{m=1}^n \frac{m}{2^m} = \sum\_{m=1}^n \sum\_{k=1}^m \frac{1}{2^m} = \sum\_{k=1}^n \sum\_{m=k}^n \frac{1}{2^m} = \sum\_{k=1}^n \left(\frac{1}{2^{k-1}} - \frac{1}{2^n} \right) = 2 - \frac{n+2}{2^n}. $$ This shows that $$ S(n) = 2 - \frac{n+2}{2^n}, \quad T(n) = 2^{n+1} - n - 2. $$ Indeed, one calculates that $T(1) = 2^2-1-2 = 1$, and $$ T(n) - 2T(n-1) = 2^{n+1} - n - 2 - 2(2^n - n - 1) = n. $$
> 0 votes

---
Tags: recurrence-relation
---


# Question
Title: Solving recurrence relations with two variables
I am trying to solve this recurrence relation with two variables:

$$T(n, k) = T(n - 1, k - 1) + T(n - 1, k)$$

The base cases are:

* $T(n, k) = 1$ if $k = 0$
* $T(n, k) = 0$ if $k \> n$

I was wondering if standard techniques like characteristic polynomial and generating function would work in this situation.

# Answer
> 5 votes
The standard technique is to notice that your recurrence is just Pascal's identity, and so $$ T(n,k) = \binom{n}{k} $$ is a solution to the recurrence. There are other solutions, for example $T(n,k) = 2^n$, and multiples of both.

In your case, the binomial coefficient satisfies the initial conditions, so it is the solution.

---

Now, let's solve it using generating functions. Let $$ f(x,y) = \sum\_{n,k} T(n,k) x^n y^k. $$ The initial conditions imply that $T(0,0) = 1$ and $T(0,k) = 0$ for $k \> 0$. Also, $T(n,0) = 1$ for all $n$. Applying the recurrence for all $n,k\>0$ and using these base cases, we get $$ \begin{align\*} f(x,y) &= \sum\_{n=0}^\infty x^n + \sum\_{n,k\>0} \[T(n-1,k-1)+T(n-1,k)\] x^n y^k \\ &= \sum\_{n=0}^\infty x^n + \sum\_{n,k} T(n,k) x^{n+1} y^{k+1} + \sum\_{\substack{n \geq 0\\k\>0}} T(n,k) x^{n+1} y^k \\ &= \sum\_{n=0}^\infty x^n + xyf(x,y) + xf(x,y) - \sum\_{n=0}^\infty x^{n+1} \\ &= 1 + (x+xy) f(x,y). \end{align\*} $$ Therefore $$ f(x,y) = \frac{1}{1-x-xy}. $$ The coefficient of $x^n y^k$ is the number of walks that start at $(0,0)$, end at $(n,k)$, and at each step, either move right or diagonally. Clearly they have to move right exactly $n-k$ times (so if $n \< k$ the coefficient is zero) and diagonally exactly $k$ times, but the order is not important. Therefore the number of walks is $\binom{(n-k)+k}{k} = \binom{n}{k}$.

---
Tags: recurrence-relation
---


# Question
Title: Are the capabilities of programming languages the same?
Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could (theoretically) do the exact same thing with ever language, don't you?

# Answer
> -1 votes
Yes, that's correct.

The usual justification for the computational equivalence of two programming languages X and Y is that we can write an interpreter `runX` for X programs written in the Y language, and vice versa.

Therefore, any program `y` written in Y can be simulated in language X using something like `runX("y")`, and vice versa. So, the computational power of the two languages is the same.

Sometimes, we state these fact stating "all programming languages are Turing-equivalent", i.e. that they can compute anything that a Turing machine can compute (and nothing else).

Note that this does not mean that the two languages have the same features. For instance, X might feature OOP classes, while Y might be purely procedural. X might have primitives for 3D graphics, while Y has not. X might allow access to files, Y might not. X might have garbage collection, when Y has not. X might be a functional (or logic) language, while Y is imperative. X might feature higher order functions, or dependent types, etc. which Y does not have. When we say that they have the "same power", here we only mean that they can compute the same set of functions (say, mapping an input strings to an output string).

Finally, note that there do exist some computer languages which are less powerful than general purpose programming languages like Python, Java, and the like. These are not usually called programming languages, even if they might share some aspects. For instance, the Bitcoin scripting language allows some limited computation, but has no loops (e.g. `while`), so it drastically restricts the algorithms one can implement. The basic querying part of SQL (`select`) is a simple reporting language, and is not Turing powerful (unless one adds triggers / stored procedures or other more advanced features.).

# Answer
> 7 votes
The answer to the question depends on what you mean by "the same".

It is a famous result of computability theory that many reasonable models of computation all calculate the same *nubmber-theoretic* functions. That is, all reasonable general-purpose programming languages compute the same partial functions $\mathbb{N} \to \mathbb{N}$. So in this sense the capabilities of all programming languages are "the same". By the way, this is *not* the Church-Turing thesis, contrary to what you may be told.

However, a programming language can do many other things in addition to computing with numbers. For instance, it may access external devices, run parallel programs etc. While these features do not allow it to compute any extra number-theoretic functions, they may make a difference when it comes to computing other functions. For instance, a famous early example is that of the language PCF. It can simulate Turing machines, but it cannot compute the "parallel or" function, while its parallel variant PCF++ can.

When we look at higher-order functions languages differ in their capabilities. A purely functional language such as Haskell cannot compute the modulus of continuity but a functional language extended with local state can.

So it really depends on what you mean by "the same".

---
Tags: computability, programming-languages
---


# Question
Title: Which address bits are used for set selection/tag check in a cache?
If

> Capacity = 24 KiB Associativity = 6 Line Size = 32 B

As far as I know:

$$Capacity = Associtivity * Line Size * Sets$$

so $24576 = 32 * 6 * Sets$

$Sets = 128 = 2^7$

thus 7 least significant bits are needed to identify set number.

Am I doing it correctly?

# Answer
Your result is almost correct. The number of sets is indeed 128. But 128=2^7 And 7 bits are required to identify a set...
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys?
From *Algorithms 4th*:

> Quicksort with 3-way partitioning uses ~$(2\ln 2)NH$ compares to sort $N$ items, where $H$ is the Shannon entropy, defined from the frequencies of key values.

$ H = -(p\_{1}\log\_{2}{p\_1} + p\_{2}\log\_{2}{p\_2} + .... + p\_{k}\log\_{2}{p\_k}) $

> Given $N$ keys with $k$ distinct key values, for each $i$ from $1$ to $k$ define $f\_{i}$ to be frequency of occurrence of the $i$-th key value and $p\_{i}$ to be $f\_{i} / N$, the probability that the $i$-th key value is found when a random entry of the array is sampled.

---

How does $(2 \ln 2)NH$ become linear when there are many duplicated keys?

So does it mean that I need to prove:

$H$ is a constant (or should I say have a upperbound ?), and not related to $N$, when there are many duplicated keys.

# Answer
Basically yes and slightly no.

---

The purpose of the quoted paragraphs is to summarize the improvement of quicksort with 3-way partitioning over the basic quicksort (with Hoare partition scheme) in the case of many duplicated keys. The root cause of the improvement is simple, "every item encountered leads to an exchange *except* for those items with keys equal to the partitioning item’s key". The quantification of the improvement is given by that formula involving the Shannon entropy.

> How does $(2\ln2)NH$ become linear when there are many duplicated keys? So does it mean that I need to prove: $H$ is a constant (or should I say have a upper bound ?), and not related to $N$, when there are many duplicated keys.

I would turn the question around.

How can we define "many duplicated keys"? The book *Algorithms* chooses to mention this concept casually, probably in an attempt to make the situation sounds immediately familiar to the widest audience at the expense of some rigor.

In fact, the more applicable and rigorous concept should be "stable discrete distributions", i.e., the distribution of all discrete key values stays roughly the same, which is somewhat more technical but still within reach of most of targeted audience of that book. Note that entropy of a multi-set is determined by the frequencies of all values appearing in the multi-set, as explained in the last paragraph quoted in the question. If the distribution of all key values stays the same, the entropy of a sample array viewed as a multi-set will be roughly the same regardless of the sample size. When sample size goes larger and larger, there will be more and more duplicate keys in the sense of the sum of duplicities. For example, if the probability of some key $k$ is 0.2, then there is likely about 20 items with key $k$ when the sample size is 100 and there is likely about 200 items with key $k$ when the sample size is 1000. That is the meaning of "many duplicate keys" here.

In other words, we could simply define "many duplicated keys" by "the same entropy regardless of the size $N$". Then there is, actually, nothing for you to prove once you have agreed that "Quicksort with 3-way partitioning uses $\sim(2\ln2)NH$".

Or, we could try to prove the following more precise proposition.

> It will take quicksort with 3-way partitioning approximately $(2\ln2)NH$ time on average to sort an array of size $N$ that comes from sampling a discrete distribution with entropy $H$, where $H$ is a constant and $N$ goes to infinity.

The following excerpt of the book implies the explanation above implicitly. The boldface is added by me.

> As with standard quicksort, the running time tends to the average as the array size grows, and large deviations from the average are extremely unlikely, so that you can depend on 3-way quicksort’s running time to be proportional to N times the entropy of the distribution of input key values. This property of the algorithm is important in practice because it reduces the time of the sort from linearithmic to linear for arrays with large numbers of duplicate keys. The order of the keys is immaterial, because the algorithm shuffles them to protect against the worst case. **The distribution of keys defines the entropy** and no compare-based algorithm can use fewer compares than defined by the entropy. This ability to adapt to duplicates in the input makes 3-way quicksort the algorithm of choice for a library sort—clients that sort arrays containing large numbers of duplicate keys are not unusual.

---

My explanation above suffers the same weakness of ambiguity as the book, although on a slightly different level, since I would also like my explanation to be understood by widest audience easily with least amount of expense of rigor. Hopefully, I have made the point clearly enough so that readers should be comfortable enough to believe he/she has understood the relevant idea in the book.

---

Assume the **Proposition N** of the book, which is the first paragraph of this question.

**Exercise.** Given a constant positive integer $m$, it will take quicksort with 3-way partitioning approximately less than $2N\ln2\log\_2m$ time to sort an array of size $N$ whose number of distinct elements is $m$. (Hint, maximum entropy with $m$ possible values is obtained with uniform distribution.)
> 1 votes

---
Tags: complexity-theory, time-complexity
---


title: Data Hazard in Pipelining

text:
# Question
Title: Data Hazard in Pipelining
To be precise I am here for RAW hazard. Consider a 5 stage pipeline .

In case of $I\_4-I\_1$ dependency , I am not sure if it is an $RAW$ hazard as $I\_4$ does not depends on value of $R\_1$ that $I\_1$ gives. and even if it fetches it ,it still be a wrong value as per the instruction sequence as $I\_2$ is modifying it.

So , is $I\_4-I\_1$ a $RAW$ hazard ?
and if yes, then please give suitable explanation why so and related information about $RAW$ hazard as it happened even if $I\_2$ modified the Value in between .

# Answer
> 1 votes
> We can't say without knowing number of stages used in pipeline. If stages are not more than $3$, it's not RAW.

First of all, this statement of mine is incorrect if we talk about **data dependency**. Dependency is a matter of instructions itself, architecture doesn't come into play directly. Architecture can only ensure that stall not to happens even with dependencies but it doesn't change the fact of dependencies among instructions. But in a pipeline if any data dependency results into stall then it is called **data hazard**.

> and even if it fetches it ,it still be a wrong value as per the instruction sequence as I2 is modifying it.

Again, as I have explained above, the modification is irrelevant here if we are just talking about dependencies. To check data hazard What we need to do is to see whether dependencies result into stall in pipelining or not. If yes, it results, then it is data hazard.

---
Tags: cpu-pipelines
---


# Question
Title: Confused about the correctness proof of Dijkstra's algorithm
In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow:

> Let u be v's predecessor on a shortest path P:s-\>...-\>u-\>v from s to v. Then, If d(u) = δ(s,u) and edge (u, v) is relaxed, we have d(v) = δ(s,v), where the funciton δ(x, y) denotes the minimum path weight from x to y.

I wonder why we need the condition d(u) = δ(s,u) in this lemma. If Path P: s-\>...-\>u-\>v is a shortest path from s to v, then by the property of optimal substructure, the subpath s-\>...-\>u of P must also be a shortest path from s to u. Therefore, d(u) must equal to δ(s,u).

Does there exist the case that d(u) ≠ δ(s,u) but P: s-\>...-\>u-\>v is a shortest from s to v? If it does, can someone offer an example here.

Any help will be appreciated

> PS: if you are interested in the entire proof. Check here, the proof starts at 45:30

# Answer
> 4 votes
It looks like you misunderstood the nature of $d(v)$ for a vertex $v$.

$d(v)$ is designed to hold the current known shortest distance from $s$ to $v$ at each step/stage of the algorithm. That is, $d(v)$ is not a fixed value given $s$ and $v$ alone.

At the start of Dijkstra's algorithm, $d(s)$ is initialized to 0 and $d(v)$ is initialized to $\infty$ for each vertex $v\not=s$ in $G$. For example, let graph $G$ have three vertices $s, u, v$ and two edges $\\{s,u\\}, \\{u,v\\}$. The path $s,u,v$ is a shortest path from $s$ to $v$. Right right after Dijkstra's algorithm has initialized $d(u)$ to $\infty$, we have $d(u)=\infty\not=1=\delta(s,u)$. This is one of the examples you are looking for. In fact, for all graphs in which $u$ is reachable from $s$, as long as $d(u)$ has not been relaxed to $\delta(s,u)$, we will have, of course, $d(u)\not=\delta(s,u)$.

On the other hand, $d(u)=\delta(s,u)$ must hold at the time when the edge $(u, v)$ is being relaxed in Dijkstra's algorithm. That might be the reason that prompts you to raise this question. Note that as a property of the Dijkstra's algorithm, that fact is not proved yet at the point of time in that lesson.

---
Tags: algorithms, graphs, shortest-path, correctness-proof
---


# Question
Title: "Mathematical Physics"'s equivalent for Computer Science
Mathematical Physics is a **well defined** scientific fields that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of physics.

Is there a **well defined** scientific field that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of computer science ?

# Answer
When you use mathematics or mathematical models to understand physical nature around us and its dynamics, the mathematics in its association with physical laws become Physics. Similarly, when you leverage mathematics or its models like trees, graph, first-order logic etc to understand computational problems it becomes computer science.
> 2 votes

# Answer
Theoretical computer science? Computational theory?
> 0 votes

---
Tags: mathematical-foundations
---


title: Example of a parsing/rewriting system?

text:
# Question
Title: Example of a parsing/rewriting system?
I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually implemented examples of rewriters. For example, suppose I had the rules

WORD: \[A-Z\]+

QUOTE: "

And I wanted to input a lot of words,put quotes around each one, and write out the string. Or go back and forth. Something like this:

(WORD \[' '\])+ \<--\> (QUOTE WORD QUOTE \[' '\])+

That seems kind of possible to implement automatically without ambiguity, but I was hoping someone had seen something along that line that already exists.

# Answer
Thue language is based on string rewriting and it's just 179 lines of c code.

Pure is an LGPL'd functional language based on term rewriting.

Not an example, but a course with really complete slides on the theory of term rewriting systems.
> 3 votes

# Answer
My DMS Software Reengineering Toolkit is an example of a system based on rewriting terms (ASTs produced by parsing), used to carry out massive code transformations. You can see a description of its rewrite rules.
> 0 votes

# Answer
I wrote a relatively simple bottom-up parser using a string rewriting system in Prolog. In this example, the input is `[a,plus,b,plus,sum,of,c,and,d]` and the output is `[[[a,+,b],+,c],+,d]`:

```
:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :-
    rewrite_system([a,plus,b,plus,sum,of,c,and,d],X),writeln(X).

% this predicate is from https://stackoverflow.com/a/8312742/975097
replace(ToReplace, ToInsert, List, Result) :-
    once(append([Left, ToReplace, Right], List)),
    append([Left, ToInsert, Right], Result).

rewrite_system(Input,Output) :-
    is_terminal(Input),Input=Output;
    rewrite_rule(A,B),
    replace(A,B,Input,Input1),
    writeln(Input1),
    rewrite_system(Input1,Output).

rewrite_rule([sum,of,A,and,B],[A,plus,B]).
rewrite_rule([A,plus,B],[A,+,B]).
rewrite_rule([A,+,B],[[A,+,B]]).
is_terminal([A,+,B]).

```

Using the same principle, I wrote an adaptive parser that "learns" new grammar rules from its input.
> 0 votes

---
Tags: formal-languages, parsers, term-rewriting
---


# Question
Title: Is there a name for this type of Turing machine?
I'm considering turing machines with tape alphabet equal to $\\{0,1\\}$ and the blank symbol equal to $0$. Is there a name for this type of Turing machines? Isn't this type the one computers are based on?

# Answer
That would be a **Turing machine with a binary tape alphabet**. The term **binary Turing machine** also seems to be common enough (a Google search gives just under 1000 results for the term).

As David Richerby pointed out in the other answer, though, Turing machines are *not* what computers are based on. Rather, (modern) computers are based on *register machines* (Wikipedia). What we do have is an equivalence between the two computation models.
> 2 votes

# Answer
Not sure about a name, but real computers aren't based on Turing machines at all.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?
The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each respective sample, compute an approximate smallest CFG for the language?

I want to make a parser generator that automatically detects a grammar given some samples of programming languages.

# Answer
This is extremely optimistic.

The first problem you face is that an approximate smallest grammar will at best help you find strings which occur frequently. It won't distinguish keywords from names, and it won't isolate words. (Note for reference that Lempel-Ziv has a good approximation ratio. Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, & Shelat (2005) The smallest grammar problem, Information Theory, IEEE Transactions on, 51(7), 2554-2576).

The second, related, problem you face is tokenisation. Programming language grammars deal in tokens, not in characters. Just the issue of tabs vs spaces in the samples is likely to mess things up. This might be finessed by making assumptions about tokenisation and then finding approximate smallest grammars over the language of tokens, but be prepared for nasty surprises. E.g. string literals in C# are definitely non-trivial, and you might not have many instances of `@`-strings from which to infer.

The third problem is that some languages (particularly those designed for code-golf) have unusual tokenisation and so little grammar that the tokenisation is where the real difficulty lies. E.g. identifying the tokenisation of CJam operators is going to be hard. You might do *slightly* better if instead of working from a grammar per sample you concatenate the samples, separated by a token which doesn't occur in any sample, and then find an approximate shortest grammar for that super-sample. At least that way you might have sufficiently many occurrences of the more common multi-character tokens to pick them out as symbols.
> 3 votes

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


# Question
Title: Find value of $a$ or $b$ of two XOR equations
Is it possible to find $a$ or $b$ given that $a \oplus b = c$ and $c \oplus b = a$ when I only have the value of $b$?

# Answer
> 3 votes
No. $a\oplus b = c$ and $c\oplus b = a$ are just rearrangements of the same equation, since

$$a\oplus b = c \iff (a\oplus b)\oplus b = c\oplus b\iff a=c\oplus b\\,.$$

---
Tags: logic, arithmetic, xor
---


title: PRNG for a gaussian distribution?

text:
# Question
Title: PRNG for a gaussian distribution?
I need suggestions for algorithm for Pseudo random number generators that will produce a near gaussian distribution (bell curve) for automatically generating test data. I know that PRNG produce recurring 'patterns, but google has revealed none that expressively produce gaussian distributions. Do you have an recommendations ideally I'd like several suggestions to produce multiple different test datasets usable for automated testing.

# Answer
You can generate any distribution by using a standard PRNG to choose $X$ uniformly from the interval $\[0,1\]$ and then returning $F^{-1}(X)$, where $F$ is the cumulative distribution function of the distribution you're interested in.

For the Gaussian distribution, though, it's usually better to use Box–Muller or ziggurat.
> 6 votes

---
Tags: randomness, pseudo-random-generators
---


# Question
Title: What is the Curry-Howard analogue for linear logics?
As defined by Wikipedia,

> (The Curry-Howard correspondence) is a generalization of a syntactic analogy between systems of formal logic and computational calculi that was first discovered by the American mathematician Haskell Curry and logician William Alvin Howard.

Related to it is the λ-cube, which is a graphical representation of the possible axes of refinement from simple types to the calculus of constructions, which has a logical interpretation:

As far as I know, the Curry-Howard correspondence is a connection between type theory and classical logics. My question is: is there any analogue correspondence between type systems and **linear** logics?

# Answer
Linear logic corresponds to a type system for a process calculus (a variant of the internal π-calculus), where:

* **proofs** *correspond to* **processes**;
* **propositions** *correspond to* **session types** (communication protocols).

This is a pretty active area of research. While people expected a correspondence between linear logic and some concurrency model since the inception of linear logic by Girard \[1987\], finding something that is satisfying from both the logical and the concurrency modelling perspectives has been somewhat elusive.

Here is a summary of the key developments so far.

* Abramsky \[1994\] and Bellin and Scott \[1994\] proposed the first "Proofs as Processes" correspondence, where linear propositions are types for linear channels in a process calculus. For example, the proposition $A \otimes B$ is interpreted as the channel type "send $A$ and $B$"; it is used to type a process that uses a channel to output a message including something of type $A$ and $B$ (a pair, if you like), respectively, and then the channel must not be used anymore. The key idea is that the cut rule of linear logic can be used to type the parallel execution of two processes that communicate over a private channel. The duality check performed by the cut rule in linear logic corresponds to checking that the two processes use the shared private channel in compatible ways.
* The idea of duality inspired also several typing disciplines for process calculi, most notably linear types and session types, but the direct link to linear logic was lost. Session types in particular, by Honda \[1993\], describe communication protocols and their applicability became evident pretty soon: the idea spawned a research area.
* Seven years later after Honda developed session types, Caires and Pfenning \[2010\] found that propositions in intuitionistic linear logic can be interpreted as session types. For example, the proposition $A \otimes B$ is interpreted as the protocol "send $A$ and then proceed as $B$". This discovery has rejuvenated the "Proofs as Processes" research line: there are a lot of papers on this topic published in the last decade. Thanks to the logical foundations, we can import ideas from logic for extending the typing discipline of session types.
* Wadler \[2014\] reformulated the correspondence with session types for classical linear logic and formalised the first connection between a standard presentation of session types for a functional language and linear logic.
* There is an "issue" shared by all the works cited above: while the linear logic side is the expected one, the process calculus side is not, both syntactically and semantically. For example, a notable discrepancy is that parallel composition ($P|Q$) is not a standalone term constructor, because it lacks a corresponding rule for reasoning about it directly in linear logic. This issue has been resolved in \[Kokke et al., 2019\] (disclaimer: I'm one of the authors), by conservatively reformulating the rules for $\otimes$, cut, and mix. This gives rise to new proof transformations, which turn out to correspond to the expected observational semantics of the π-calculus.

If you're looking for a couple of papers to get started, I would start from \[Wadler, 2014\] and then \[Kokke et al., 2019\] (to see the latest system).
> 12 votes

# Answer
You can impose similar requirements within your type system, which amounts to requiring that objects never be destroyed nor duplicated. For an example of a practical application, see Linear Types can Change the World! by Philip Wadler, which specifies typing rules for this. It also shows how a type system can combine linear and non-linear types.

For a practical application of this, take a look at `std::unique_ptr` in C++. Here, linearity ensures that deallocation always occurs exactly once.

In a functional language, linearity also gives the possibility of destructive updates (that appear pure to the programmer). However, in practice it seems like monads are a more common approach to solving this problem.

**Update**: I noticed that in the NLab Computational Trinitarianism table the absence of contraction in a logic (i.e. being unable to duplicate an assumption) corresponds to the No-Cloning Theorem from quantum mechanics. I (unfortunately) don't understand the implications of this, but I thought you might find it interesting.
> 8 votes

---
Tags: logic, type-theory, functional-programming
---


title: Typing rule for binding groups

text:
# Question
Title: Typing rule for binding groups
In "Typing Haskell in Haskell", by Mark P. Jones, is provided a sort of haskell-like specification for typing Haskell. As stated in this paper, binding groups is a area "neglected in most theoretical treatments of type inference". Jones provided inference and checking algorithms for this syntactic construct, but it's typing rule is not referenced.

As far I know, binding groups is quite differente from usual let bindings. You can have mutual recursion, for example. Also, I don't know if is possible to simulate binding groups only using *let* expressions.

There is a typing rule for typing binding groups anywhere in the literature? If there is, then maybe the rest of this question is pointless.

This paper also doesn't give us a (in)formal grammar for the syntax, because it's goal is type inference/checking from the data stucture itself. I don't think this is strictly necessary, but a syntactic definition of binding groups may help defining a typing rule. So, I decided to give a sugestion of what this informal grammar may look like. Brackets means finite sequence and curly bracket means no-empty finite sequence.

So, what I'm asking here is a rule for typing binding groups.

EDIT:

It seems that my question is not clear enough. I apologize for that. I'll try to make it more clear...

By typing rule (or type rule) I mean: en.wikipedia.org/wiki/Type\_rule and by type checking algorithm I mean something easy to translate to code. I think the difference is more fundamental than just representation style. A rule is closer to a relation and an algorithm is closer to a function. What is missing is a rule, like in the wikipedia page, that could be used for certification of the algorithm.

Certification is the motivation behind my question. I want to certify the algorithms described in this paper.

# Answer
I don't know what rule Jones intended to use, but I'd guess it's something like

$$ \dfrac{ \Gamma' = \Gamma,x\_1:\tau\_1,\ldots,x\_n:\tau\_n \\ \Gamma' \vdash e\_1 : \tau\_1 \\ \cdots \\ \Gamma' \vdash e\_n : \tau\_n \\ \Gamma' \vdash e : \tau }{ \Gamma \vdash {\sf let}\ x\_1=e\_1;\cdots;x\_n=e\_n\ {\sf in}\ e : \tau } $$

which handles mutual recursion in groups. The rule above does not consider patterns as in `x [p] = e`, but it could be amended to support those as well.

I think binding groups are usually neglected since mutual recursion can be translated into non-mutual one (e.g. exploiting Bekić's theorem). However, in a real-world language it's convenient to have mutual recursion, even if from a purely theoretical point it's redundant. Hence, having a typing rule for it and an inference algorithm is still quite useful.
> 3 votes

---
Tags: type-theory, type-inference, typing, haskell
---


# Question
Title: How to transform a Infinite decimal of $\frac{23}{6}$ into binary?
How to transform a decimal of $\frac{23}{6}$ into binary?

$\frac{23}{6}$ is equal to $3.83333\bar{33}$, where the digit $3$s are repeated forever.

I do know how to translate **finite decimal** into binary, but is there any procedure to translate such **Infinite decimal** like $\frac{23}{6}$ into binary?

Any hint is appreciated!

# Answer
> 1 votes
Here is a hint by example.

$\frac{23}6 \> 2$
$\frac{23}6-2 = \frac {11}6 \> 1$
$\frac{11}6-1 = \frac {5}6 \> \frac 12$
$\frac{5}6-\frac12 = \frac {1}3 \> \frac 14$
$\frac{1}3-\frac14 = \frac {1}{12} \> \frac 1{16}$
$\vdots$

So $\frac{23}6=2+1 +\frac12+\frac14+\frac1{16}+\cdots=(11.1101\cdots)\_2$

---

**Exercise.** How to determine the period of the fraction part of the binary expansion of $\frac {23}6$?

---
Tags: binary
---


# Question
Title: How can I efficiently find the largest positive interval in an unsorted array?
Given a set of values like \[4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9\], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an interval of 4 because `8 - 4 = 4`. But the largest positive interval is between index 2 and index 10, because `11 - 1 = 10`.

I can see that there's a way to do this in linear time, but I can't figure out what it is. The n^2 brute force solution is straightforward, but I want to understand the better way.

---

To be clear, the largest positive interval in `[20, 1, 4]` would be 3, not 19, because 20 -\> 1 is an interval of -19.

---

The solution I would put forward is to translate the array in linear time to an array of differences, e.g. \[20, 1, 7, 4, 2\] becomes \[0, -19, 6, -3, -2\], and then use Kadane's algorithm for finding the maximum contiguous subsequence. The largest subsequence would be `6` on its own, implying indices 1 and 2 provided the answer.

# Answer
> 0 votes
I know of two solutions:

The first is put forward by @Apass.Jack, and is the simpler and better one:

```
def maximumInterval(array):
  min_value = array[0]
  max_interval = -1
  for i in range(1, len(array)):
    if array[i] - min_value > max_interval :
        max_interval = array[i] - min_value
    if array[i] < min_value :
        min_value = array[i]
  return max_interval

result = maximumInterval([4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9])
print(result)

result  = maximumInterval([20,1,4])
print(result)

```

The other solution is as described in the question above. Convert the array to an array of differences and find the maximum contiguous subarray using Kadane's algorithm.

# Answer
> 3 votes
Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned.

Here is the Python code for the simple linear algorithm hinted. Hit the "run" button to see a couple of test result.

---
Tags: algorithms, subsequences
---


# Question
Title: Can I compute closest split pair of points where distance is strictly less than delta
I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "Finding the closest pair of points" of *introduction to algorithms*, third edition by CLRS.

I understand why I'd need 7 comparisons for a non pairwise distinct set of points and only 5 otherwise (33.4-2). Both of them follow from the fact that I can fit only 4 points, at least Delta away from each other, on a Delta x Delta box.

What I've been wondering though, is if I could trim the number of comparisons down to 3 if I included only points strictly less than Delta away from the middle line, in the middle Delta x 2 Delta strip. The reasoning is that I already have a pair of points Delta away from each other from the recursive calls, I only need points less than Delta and I can only fit 2 points Delta away from each other AND less than Delta from the middle line on each side.

Have I missed something or can I really just compare the 3 following points of every point in a middle strip only containing points strictly less than Delta from the center?

**Edit:** I have started a bounty for a very similar question on stack overflow also and we have come up with a very interesting discussion there. So I'm linking it here. We've also started a very insightful chat here.

# Answer
Yes, as you have observed, we can just compute pair of points whose distances are strictly less than $\delta$ in the "combine" step of the "divide-conquer-combine" algorithm, where we examine the minimal distance between the points to the left and the points to the right.

However, it is not enough to just compute the next 3 points.

---

The above graph, taken from CLRS, illustrates the original argument for 7 in the case of non-pairwise distinct points and for 5 in the case of pairwise distinct points. For the sake of clearer explanation, assume the central line $l$ is the vertical axis and $\delta=\delta\_L=\delta\_R=1000$. Let the strip consist of the area between the line $x=1000$ and $x=1000$, excluding those two lines. This strip contains only the points that are strictly less than 1000 away from the central line $l$. Suppose all distinct points in the strip in the ascending order of vertical coordinate are $s\_0, s\_1, s\_2, s\_3, s\_4$.

Suppose we have verified that $d(s\_0,s\_i)\ge1000$ for $i=1,2,3$. Can we conclude that there is no point $s$ such that $d(s\_0,s)\<1000$?

No. It might happen that
$$\begin{align}\\ s\_0&=(79,0)\\ s\_1&=(-921,1)\\ s\_2&=(999,500)\\ s\_3&=(-999, 998)\\ s\_4&=(79, 999) \end{align}$$

Note that $d(s\_0, s\_4)= 999\<1000$. In fact, $d(s\_i,s\_j)\gt1000$ for all $i$ and $j$ except $d(s\_0, s\_4)$.
$$\begin{align} d(s\_0, s\_1)&=\sqrt{1000001} \\ d(s\_0, s\_2)&=\sqrt{1096400} \\ d(s\_0, s\_3)&=\sqrt{2158088} \\ d(s\_0, s\_4)&=\sqrt{998001} \\ d(s\_1, s\_2)&=\sqrt{3935401} \\ d(s\_1, s\_3)&=\sqrt{1000093} \\ d(s\_1, s\_4)&=\sqrt{1996004} \\ d(s\_2, s\_3)&=\sqrt{4240008} \\ d(s\_2, s\_4)&=\sqrt{1095401} \\ d(s\_3, s\_4)&=\sqrt{1162085} \\ \end{align}$$ So if we only compute the distance with the next 3 points, we will not find that shortest edge from $s\_0$ to $s\_4$ at the end of the algorithm.

The above counterexample shows that it is not sufficient to just compare 3 following points of every point in a middle strip only containing points strictly less than $\delta$ from the center line, even if we assume that all points are distinct.
> 3 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Trilinear interpolation for distorted cubes?
Is there a variation of trilinear interpolation that works on a "cube" that has been distorted (by moving one or more of its corners by an arbitrary amount into an arbitrary direction)?

I know that I could use the inverse of the distance to each of the 8 corners as weights to get an interpolated point within the distorted cube, but that would involve taking a lot of square roots which would slow my algorithm way down. I like the elegant way of trilinear interpolation but I can't figure out how to adapt it to a distorted cube. Any hint on a fast interpolation method for this situation would be much appreciated.

# Answer
> 1 votes
Imagine a cube with each corner a different RGB color value - as you know you could interpolate the colors inside the cube using trilinear interpolation.

You can reuse this same logic for coordinates as well -- set the RGB values of the corners to be the XYZ coords of your distorted cube's corners.

Now the RGB "color" you sample in this cube is the distorted coordinate -- eg, it is the coordinate of your sampling point after that point has been "remapped" to the now-distorted cube, using the normal trilinear algorithm.

Hope this helps.

---
Tags: algorithms, performance
---


title: additive hash function

text:
# Question
Title: additive hash function
Do functions with the following properties exists for x being arbitrary stream of bytes:

1. op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation and op is an easily computable operation
2. f(x) is fixed length of about 160-512 bytes
3. f does not need to be hard to revert, but should be useful at finding transmission errors or duplicates.

Could you provide any names/articles/pointers?

# Answer
> 1 votes
Try the CRC hash; it has this property. You can also look at Merkle tree hashing.

See also https://crypto.stackexchange.com/q/24622/351, Which fingerprinting/hashing algorithms support compounding?, https://crypto.stackexchange.com/q/6497/351.

---
Tags: reference-request, hashing
---


# Question
Title: What's the right way to think about a CFG symbol with an infinite null derivation?
I'm curious about the right way to characterize symbol $A$ in a CFG like this one:

$$ \begin{align\*} A &\to A B\\ A &\to x\\ B &\to y\\ B &\to \varepsilon \end{align\*} $$

$B$ is certainly nullable. However, should $A$ be considered nullable? It feels like the answer is probably "no" (and most first-follow implementations I've seen either agree or crash on this). However, you can derive an infinitely large parse tree for the null symbol sequence like $A \to A(A(A(...) B()) B()$.

# Answer
The infinitely large parse tree you propose does not represent the parse of any sentence, because its leaves are not all terminals.

A more precise statement would be that $A$ cannot derive the empty sentence. You can produce an arbitrarily long derivation of $A$ by repeatedly using the rules $A \to A B$ and $B \to \epsilon$ but none of those derivations is empty. Since the precise definition of "nullable" is "a non-terminal which can derive the empty sentence", $A$ is not nullable.

If a FIRST/FOLLOW implementation crashes on that input, then the implementation is buggy. The correct computations are:

$$\begin{align} FIRST(A) &= \\{x\\} \\ FIRST(B) &= \\{y, \epsilon\\} \\ FOLLOW(A) &= \\{y, \epsilon\\} \\ FOLLOW(B) &= \\{y, \epsilon\\} \end{align}$$
> 2 votes

# Answer
A variable is nullable if you can derive the empty word from it. Hence, in your example, $A$ is not nullable. However, if you add a rule as, for example,

$$A \to B$$ then it is, as $A\Rightarrow B\Rightarrow \varepsilon$.
> 1 votes

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


# Question
Title: Why do I get different results from two calculation methods?
I am wondering what the reason for the following is

We know that ,

exponential has a taylor representation : $$exp(x)=1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+...$$

Using the first n terms , in R , I compute

$\exp(-10)$ and get one answer.

However, if I compute $\frac{1}{\exp(10)}$, I get a slightly different answer.

For example, when I use the first 30 terms of the Taylor Series,

I get

$\exp(-10)=0.0009703416$

but $\frac{1}{\exp(10)}=4.539993\times10^{-5}$

Once I get to a large enough number of iterations, both converge to the correct value.

So why do we get differing answers when I use the same method, only replacing by a division of 1 over?

Thanks!

# Answer
> 3 votes
For $\exp(-10)$, more terms have to be computed since the 30-th term $\dfrac{(-10)^{30}}{30!}\approx 0.00377$ is several times bigger than the partial sum so far, 0.0009703416.

For $\exp(10)$, all terms are positive. The 30-th term $\dfrac{(10)^{30}}{30!}\approx 0.00377$ is already substantially negligible to the partial sum so far, 22026.464.

Here is the output of the program of my Python program that computes $\exp(-10)$ by that Taylor series. The first column tells the ordinals of the terms. The second columns show the values of that terms. The third terms is the partial sums so far.

```
0                     1.0                     1.0
1                   -10.0                    -9.0
2                    50.0                    41.0
3     -166.66666666666666     -125.66666666666666
4      416.66666666666663                   291.0
5     -833.33333333333326     -542.33333333333326
6      1388.8888888888887      846.55555555555543
7     -1984.1269841269839     -1137.5714285714284
8      2480.1587301587297      1342.5873015873012
9     -2755.7319223985887     -1413.1446208112875
10      2755.7319223985887      1342.5873015873012
11     -2505.2108385441716     -1162.6235369568703
12      2087.6756987868098      925.05216182993945
13     -1605.9043836821616      -680.8522218522221
14      1147.0745597729726      466.22233792075053
15     -764.71637318198179     -298.49403526123126
16      477.94773323873864      179.45369797750737
17     -281.14572543455211     -101.69202745704473
18      156.19206968586229      54.500042228817563
19     -82.206352466243317     -27.706310237425754
20      41.103176233121658      13.396865995695904
21     -19.572941063391266     -6.1760750676953613
22      8.8967913924505755      2.7207163247552142
23     -3.8681701706306848     -1.1474538458754706
24      1.6117375710961186     0.46428372522064798
25    -0.64469502843844739    -0.18041130321779941
26     0.24795962632247978    0.067548323104680369
27    -0.09183689863795548   -0.024288575533275111
28    0.032798892370698378     0.00851031683742327
29   -0.011309962886447721  -0.0027996460490244501
30   0.0037699876288159102  0.00097034157979145996
31  -0.0012161250415535199 -0.00024578346176205997
32  0.00038003907548547002  0.00013425561372341999
33    -0.00011516335620772       1.90922575157e-05
34  3.3871575355210003e-05  5.2963832870910003e-05
35 -9.6775929586300006e-06  4.3286239912280003e-05
36  2.6882202662899999e-06  4.5974460178560002e-05
37 -7.2654601791999997e-07  4.5247914160649999e-05
38  1.9119632050000001e-07  4.5439110481150002e-05
39 -4.9024697569999999e-08      4.539008578359e-05
40         1.225617439e-08  4.5402341957980002e-05
41 -2.9893108300000001e-09  4.5399352647149997e-05
42  7.1174066999999995e-10  4.5400064387830001e-05
43 -1.6552109000000001e-10  4.5399898866740002e-05
44            3.761843e-11      4.539993648517e-05
45 -8.3596500000000006e-12  4.5399928125519999e-05
46             1.81732e-12      4.539992994283e-05
47 -3.8665999999999999e-13  4.5399929556169997e-05
48  8.0549999999999995e-14  4.5399929636719997e-05
49 -1.6440000000000001e-14  4.5399929620280003e-05
50  3.2899999999999998e-15  4.5399929623570001e-05
51 -6.4000000000000005e-16  4.5399929622930003e-05
52                 1.2e-16  4.5399929623049997e-05
53 -2.0000000000000001e-17      4.539992962303e-05
54                     0.0      4.539992962303e-05
55                    -0.0      4.539992962303e-05
4.539992962303116e-05

```

Although the partial sums becomes stable after 55-th term, not all digits of 4.539992962303e-05 is correct, because of the precision of the terms such as the 8-th term. The actual value of $\exp(-10)$ should be something like 4.5399929762485e-05

In the end, it is faster and easier to compute $\exp(-x)$ to a specified precision using $\dfrac1{\exp(x)}$ instead of directly for $x\>0$, especially when $x$ is large.

---
Tags: floating-point, numerical-analysis
---


title: Beta reduction order in Lambda calulus

text:
# Question
Title: Beta reduction order in Lambda calulus
Will it be wrong to use g for reducing (λx.λy.x) first in step (2) instead of using to reduce λg?

Is there a rule against it?

# Answer
You can do that, beta reduction can be applied at any point where an abstraction is immediately followed by application $((\lambda x. \cdots)t)$. In general, as you ovserved, there might be many redexes, i.e. many points where beta reduction can be applied.

However, note that sometimes we want to study what happens if we restrict ourselves to some reduction strategy. Essentially, a reduction strategy is a rule which chooses which redex to beta reduce when there are many. When doing that, there is a unique reduction sequence, a kind of unique execution run, for any term.

So, unless an exercise mandates the use of a specific reduction strategy, you are free to apply beta reduction at any point.

As a final remark, note that the choice of the redex can affect the termination of our reduction sequence. For instance, $(\lambda x.\ y)\Omega$ where $\Omega=(\lambda w.ww)(\lambda w.ww)$ can immediately reduce to $y$, or can loop indefinitely on reducing $\Omega$ to itself.

The Church-Rosser property (aka confluence, aka diamond property, mentioned above by xuq01) only ensures that, whenever we reduce a term $t$ with many beta reduction steps, possibly in two different ways leading to two terms $t\_1,t\_2$, there is a way to "reconcile" $t\_1$ and $t\_2$ and beta reduce those (in many steps) to a common form $t\_f$.

This ensures that choosing the "wrong" beta redex does not compromise the reachability of the "intended" result (e.g. a normal form, if it exist). However, as seen in the example above, if we insist in selecting the "wrong" redex, it is possible that we get stuck into an infinite reduction sequence, when another one would lead to the intended result.
> 4 votes

# Answer
No, you can try that and you'll get the same answer. Untyped lambda calculus has the *Church-Rosser property*, meaning that the order of $\beta$-reduction has no influence on the result of the reduction.

However, note that there is no guarantee that each term has a $\beta$ normal form, i.e. not necessarily exista a reduction sequence that leads to a final form. So, your term might diverge under one reduction order but not one other. However, if your term does have a $\beta$-normal form, the order of evaluation does not matter.
> 2 votes

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


# Question
Title: Recognizer for decidable language and words it doesn't halt on
Suppose we have a decidable language `B` (there exists some TM that decides it). Suppose we have another TM `M` which **only** recognizes B but does not decide it - there are words not in B that `M` **doesn't halt on** (for words not in B M might either reject or not halt).

Let A = {w | M does not halt on the word w}.

Which of the following has to be true:

1) `A` must be decidable

2) `A` might not be decidable but it has to be recognizable

3) `A` might not be recognizable but its complement has to be recognizable.

4) It **might** be that A and its complement are both not recognizable.

I was asked this question and i think that the answer is 3.

What i don't understand is why give the extra information about some decidable language B that M recognizes if the complement of A will always be recognizable regardless of whether it recognizes some decidable language B -\> for any TM, the set of all the words it **does** halt on will always be recognizable. The recognizer for A complement will be - run M on w and accept if it halts).

What am i missing ? Is the info about B redundant ?

# Answer
The question is designed to test your understanding, so it's legitimate regardless of whether the details of $B$ are actually relevant. Maybe you're supposed to understand why they're relevant; maybe you're supposed to understand why they're not.

You've said that "recognize" is defined to mean that the Turing machine accepts all words in the language, and either rejects or loops on words not in the language. This means that $A$ is some subset of $\overline{B}$ (the complement of $B$). Since $B$ is decidable, we know that $\overline{B}$ is also decidable. So, $A$ is a subset of some decidable language. Well, $\Sigma^\*$ is a decidable language, so $A$ could be any subset of $\Sigma^\*$. So it looks like $A$ *could be* any language at all! However, we have a little more information: $\overline{A} = \\{w\mid M(w)\text{ halts}\\}$, so $\overline{A}$ is recognizable.
> 2 votes

# Answer
By definition, $\bar A = \\{w \ |\ M \mbox{ halts on } w \\}$, which is recognizable: we run $M$ on $w$, accepting if it ever halts (and diverging otherwise).

So, the complement of $A$ must be recognizable. We now need to understand what class $A$ might belong to.

Take the trivial case where $B=\emptyset$ (which is decidable). This can be recognized by a TM $M$ which does the following: on input $w$, it semi-decides the halting problem on $w$, rejecting when $w\in HALT$, and diverging otherwise. Since this never accepts, it indeed recognizes $B=\emptyset$.

In this case, $A$ becomes the set of those $w$s making $M$ diverge, i.e. those $w \notin HALT$. Hence $A$ is the complement of the halting problem, which is not recognizable.

So, the answer is 3, as you pointed out.

The information about $B$ being decidable may appear a bit redundant at first, but actually it constraints our choice of $B$ when we wanted to prove that $A$ might be non recognizable. We could not pick $B=HALT$, for instance.
> 2 votes

---
Tags: turing-machines, computability, undecidability, halting-problem
---


# Question
Title: Which is better ? Iterations or Recursions?
I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa.

But which type of repetition is preferable for minimum amount of computational effort and resource consumption ? Iteration or Recursion ?

# Answer
> 2 votes
A straightforward answer would be "iteration", since recursion consumes stack memory and imposes computational overhead for calling functions.

However, in practice both implementations can be equivalent at machine code level due to compiler optimizations (such as tail call optimization). In general, you shouldn't really be concerned about these matters unless you have strong reasons to believe they are relevant in your particular case.

As a rule of thumb, you should concentrate on clarity and efficiency of your algorithm, and use constructions that look natural for the logic of your method. This recommendation is repeated virtually in all books on the subject, so please follow it.

P.S. You should also consider that certain algorithms require you to store certain local values on each iteration. Recursion gives you this capability "for free", so you should also consider that iterative procedures may need additional data structures comparing to their recursive equivalents.

# Answer
> 0 votes
It depends on the problem and the approach. For example, when you're computing a dp, and you won't use some of the calculated answers, it's better to do it with the recursive algorithm, because you will use more time and memory, computing them in the iterations in general. But for computing the n-th fibonacci sequence number, it is better to calculate using iteration. So it really depends on the problem itself. Generally, recursion may take more time, due to the more calls for a single calculation. for further information, please check this link and this file link.

# Answer
> 0 votes
Some problems are naturally calculated with a loop. Some problems are naturally calculated using recursion. Use whatever makes one particular problem easier. Try implementing Quicksort without recursion (much more difficult).

---
Tags: algorithms, optimization, recursion, iteration
---


title: Multi-variate complexity semplification

text:
# Question
Title: Multi-variate complexity semplification
I developed an algorithm with the following multi-variate complexity: $$O((k^n+kn)l^{kn}),$$ where $n,k,l$ are variables.

I have very little knowledge of complexity theory, and I'm not sure whether this expression can be simplified. Since $k^n$ dominates $kn$ it seems reasonable to $O(k^nl^{kn})$. Is this correct? Assuming $l\ge 2$, can the expression be simplified even further?

# Answer
Yes. you're right (for $k,n \geq 1$). Also you can right the final answer as $O((kl^k)^n)$.
> 1 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Understanding B tree key deletion step from CLRS algorithm
CLRS explains B tree key deletion as follows:

> 1. If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$.
> 2. If the key $k$ is in node $x$ and $x$ is an internal node, do the following:
>
> a. If the child $y$ that precedes $k$ in node $x$ has at least $t$ keys, then find the predecessor $k'$ of $k$ in the subtree rooted at $y$. Recursively delete $k'$, and replace $k$ by $k'$ in x. (We can find $k'$ and delete it in a single downward pass.)
>
> b. If $y$ has fewer than $t$ keys, then, symmetrically, examine the child $z$ that follows $k$ in node $x$. If $z$ has at least $t$ keys, then find the successor $k'$ of $k$ in the subtree rooted at $z$. Recursively delete $k'$, and replace $k$ by $k'$in $x$. (We can find $k'$ and delete it in a single downward pass.)
>
> c. Otherwise, if both $y$ and $z$ have only $t-1$ keys, merge $k$ and all of $z$ into $y$, so that $x$ loses both $k$ and the pointer to $z$, and $y$ now contains $2t-1$ keys. Then free $z$ and recursively delete $k$ from $y$.
> 3. If the key $k$ is not present in internal node $x$, determine the root $x.c\_i$ of the appropriate subtree that must contain $k$, if $k$ is in the tree at all. If $x.c\_i$ has only $t-1$ keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least $t$ keys. Then finish by recursing on the appropriate child of $x$.
>
> a. If $x.c\_i$ has only $t - 1$ keys but has an immediate sibling with at least $t$ keys, give $x.c\_i$ an extra key by moving a key from $x$ down into $x.c\_i$ , moving a key from $x.c\_i$’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into $x.c\_i$.
>
> b. If $x.c\_i$ and both of $x.c\_i$ ’s immediate siblings have $t - 1$ keys, merge $x.c\_i$ with one sibling, which involves moving a key from $x$ down into the new merged node to become the median key for that node.

---

I have a doubt in step 2c. In this step, $y$ is a node containing the predecessor of the key and $z$ is a node containing the successor of the key, both of which has minimum number of keys ($t-1$) and hence authors say we need to merge both of nodes. The authors give following example:

> First tree is before deleting $G$, second is after deleting $G$, which utilized step 2c.
> Here, $y=\[D,E\]$ is a predecessor node of $G$, with predecessor $E$ and $z=\[J,K\]$ is a successor node of $G$, with successor $J$. So we merge both $\[D,E\]$ and $\[J,K\]$ forming $\[D,E,J,K\]$.

My doubt is do we always end up successor and predecessor node if they contain minimum number of nodes ($t-1$)? This is what authors must mean to say when they say "merge $k$ and all of $z$ into $y$" in step 2c. But I feel they might not be the predecessor and successor nodes, they are just immediate next children of key $k$, as can be seen in this example I tried out:

Here we have not merged nodes of predecessor (node $\[N,O\]$) and successor (node $\[R,S\]$), but have merged immediate children of $Q$, i.e. node $\[C,G,L\]$ and node $\[T,X\]$.

So am I right with "we need to merge immediate next children of key $k$ but not predecessor and successor node"? If yes, is book have mistake? Or book does indeed tries to say the same and I am misinterpreting? Or I got it all wrong? Or am unnecessarily overthinking?

# Answer
> 1 votes
You are probably overthinking it by thinking in terms of predecessor/successor nodes.

The rule just says, if the key to be deleted has both children at least capacity, you cannot take a predecessor(or successor) from its left(or right) child without violating the B-Tree property. So, we decide that we will merge it with both its children and push the decision to delete one level downward. That's it.

An intermediate step in 2c. would be where G is pushed downward and merged with \[DE\] and \[JK\] to give

\[\[AB\] , \[C\], \[DEGJK\], \[L\], \[NO\]\]

Now we can apply the algorithm to this node \[DEGJK\], and since it's a leaf node, step 1 will apply here and we can simply delete G from it.

---
Tags: trees, binary-trees, search-trees, b-tree
---