title: Hashing and number of comparisons

text:
# Question
Title: Hashing and number of comparisons
Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all but last full?

Basically, this is due to me not really understanding the theory. I tried googling it, but didn't get it either. Can I have an explanation even a monkey would understand?

# Answer
This explanation is for the *Homo sapiens sapiens* subspecies of *Cercopithecidae* (old world monkeys). For an explanation suitable for other subspecies you'll have to try Knuth.

I'll assume you are talking about collision resolution by open addressing, and double hashing to determine the probe sequence. Further we'll assume that the hash functions are good (that is: that they are essentially producing uniformly distributed, independent random integers.)

We will use $N$ for the number of objects already in the hash table, $M$ for the total number of buckets in the hash table and $\alpha = N/M$ as the *load factor*. The load factor is the fraction of buckets that are already taken, and is really the important thing here.

If I try to insert a new item in a hash table with load factor $\alpha$ what is the probability that I will get a collision on my first probe? Answer: $\alpha$. Thus the probability that I find an open bucket on my first probe is $1-\alpha$.

What is the probability that I will find an open bucket on exactly my second probe? Well the probability that I failed to find an open bucket on my first probe is $\alpha$ and the probability that I succeed on my second probe is $1-\alpha$, which gives a total probability of $\alpha (1-\alpha)$.

What is the probability that I will find an open bucket on exactly my third probe? Well the probability that I failed to find an open bucket on my first and second probes is $\alpha^2$, and the probability that I succeed on my third probe is $1-\alpha$ so I have a total probability of $\alpha^2 (1-\alpha)$.

I'm an engineer, not a mathematician, so that's good enough for me to assume that the pattern holds for all positive integers. That is I've just "proved" that the probability I will take $k$ probes to find an open bucket is $$ p(k) = \alpha^{k-1} (1-\alpha). $$

(Exercise: make sure that this is a good probability by showing that $\sum\_{k=1}^\infty \alpha^{k-1}(1-\alpha)=1$.) Now what's the *expected* number of probes to find an open bucket?

$$ \begin{eqnarray} E\[\mathrm{number\ of\ probes}\] &=& \sum\_{k=1}^\infty k p(k) \\ &=& \sum\_{k=1}^\infty k \alpha^{k-1}(1-\alpha) \\ &=& (1-\alpha)\sum\_{k=1}^\infty k \alpha^{k-1} \\ &=& \frac{1-\alpha}{\alpha}\sum\_{k=1}^\infty k \alpha^k. \end{eqnarray}$$

I look up this series on Wikipedia and see that $\sum\_{k=1}^\infty k \alpha^k = \alpha / (1-\alpha)^2$ so

$$ E\[\mathrm{number\ of\ probes}\] = \frac{1}{1-\alpha}. $$
> 4 votes

---
Tags: algorithm-analysis, data-structures, hash-tables
---


# Question
Title: efficient algorithms for factoring polynomials
Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within the context of the field of integers but I wouldn't mind the rationals as well.

# Answer
Do you know of Berlekamp's algorithm and the Cantor–Zassenhaus algorithm?

http://en.wikipedia.org/wiki/Berlekamp%27s\_algorithm

http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus\_algorithm

Unless I'm misunderstanding your question, there is no field of integers- they form a ring but don't have multiplicative inverses
> 2 votes

---
Tags: algorithms, reference-request, factoring, polynomials
---


# Question
Title: Can an NP-hard problem be polynomial on average?
I'm wondering if there are any $NP$-hard problems which are \`\`polynomial" in the average case. I think there are two ways to interpret this?

* If $P \neq NP$, can there be an algorithm solving an $NP$-hard problem with amortized (average case) running time of $O(n^k)$ for a constant $k$?
* Are there any problems which are $NP$-hard which are also in $BPP$, or even $PP$?

Can anyone answer or provide a reference answering either of these questions?

# Answer
> 5 votes
It would seem that the question has been answered at CSTheory.SE.

Summary: it is, indeed possible.

For example, the Max 2-CSP problem is NP hard with an $O(n)$ expected time algorithm.

This makes sense, I guess. Sometimes only a small subset of instances is needed to make a problem $NP$-hard, like SAT vs 3SAT. But you can expand the problem, and as long as it still contains the hard instances, it will be NP-hard, but the probability of success with a fast algorithm will be raised.

---
Tags: complexity-theory, reference-request, np-complete, probabilistic-algorithms, amortized-analysis
---


# Question
Title: What are the current known implications of the complexity of Integer Factorization?
According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP. However, do we know any other implications yet- like if P != NP, does this mean that Integer Factorization is necessarily not in P? Conversely, if Integer Factorization is in P, does this imply anything about the polynomial hierarchy? Thanks.

# Answer
> 1 votes
Before answering your questions a distinction has to be made, when talking about $NP$ completeness we are talking about the decision problem not the function problem, which is given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 \< d \< M.

So answering your questions in order, Since integer factorization is not *known to be* NP complete, $P \neq NP$ would not cause it to automatically not be in $P$ since quite often things that were thought to be in $NP$ are moved to $P$, only an $NP$ complete problem would be excluded from being in $P$. For the second one, again since it is not $NP$ complete a polynomial time solution to it will not effect the hierarchy for the same reason as before.

As an extra note, the actual location of factorization in the hierarchy is unknown, we know is is $BQP$, $NP$, $co-NP$, $FNP$ and $UP$. It may end up being $NP$-Intermediate, but no one knows for sure.

---
Tags: complexity-theory, p-vs-np, factoring
---


# Question
Title: No need to rename a free variable in substitution?
I wonder if the following two substitutions are correct: $$(x\\,y)\[x:=y\] = (y\\,y)$$

$$ \lambda y. (x\\,y) \[x:=y\] = \lambda z.(y\\,z)$$

They are what I understand from http://en.wikipedia.org/wiki/Lambda\_calculus#Substitution.

Although I can follow the rules there mechanically, I wonder why there is no renaming of $y$ to $z$ in the first substitution, while there is in the second?

Is it correct that in substitution $E\[x:=M\]$, if both $E$ and $M$ have some free variable with the same name, there is no need to rename the free variable in $E$, just as in the first substitution? Thanks.

# Answer
> 3 votes
Yes, it is all correct.

Lambda-calculus may be just taken as a formal system, with rules to be followed. Period.

However, it may be useful to try to understand intuitively why the rules are what they are.

So the following is very informal and should be taken as an attempt at answering intuitively.

Consider whether the following expressions are equivalent:

* $y$ and $z$ : they are not equivalent because a substitution on $y$ has no effect on $z$, and conversely. The variables $y$ and $z$ are free variables. They stand for themselves, or for whatever value is associated to them in an environment where you evaluate the expression, or by a substitution. Changing a free variable for another (it is not *renaming* in such a case) will change what you get in the environment, or by applying a substitution (which amounts to the same).
* $\lambda y. (x\\,y)$ and $\lambda z.(x\\,z)$ : they are equivalent via alpha conversion. When applied to the same argument, and more generally when used in the same context, they will always give the same result. The variables $y$ and $z$ are bound variables. Renaming a bound variable can be done at any time, independently of the context, without ever changing the behavior of the $\lambda$-abstraction.

The renaming in your example $ \lambda y. (x\\,y) \[x:=y\] = \lambda z.(y\\,z)$ is needed because the $y$ in the substitution is a free variable (possibly taking a value in whatever environment or substitution may be provided). Without the renaming, it would be undistinguisable from the bound variable of the $\lambda$-abstraction once the substitution is performed. To avoid that, the bound variable is renamed, since renaming it does not matter.

Contrarily, in the expression $(x\\,y)\[x:=y\]$, both occurences of $y$ stand for the same free variable $y$ in the current environment. There is no reason to try distinguishing them.

---
Tags: lambda-calculus
---


# Question
Title: What is an oracle separating IP and PSPACE?
I saw this link on cstheory:

https://cstheory.stackexchange.com/questions/6634/is-there-an-oracle-that-separates-two-complexity-classes-known-to-be-equal

but it did not provide specific details. Can anyone tell me what the specific oracle is (or direct me to a paper which does)? Also on a meta-level why does this not call into question the legitimacy of oracle Turing machines- if two classes coincide, how can they be separated? Thanks.

# Answer
> 3 votes
The answer to the question you link contains all the information you need. The multi-authored paper The random oracle hypothesis is false proves the stronger result that IP and PSPACE are different with probability 1 with respect to a *random* oracle. They also comment that a concrete oracle under which IP differs from PSPACE can be constructed using standard techniques, by which they mean the form of diagonalization used to separate P from NP with respect to a concrete oracle; they do not provide any details, though. Presumably it is a not too difficult exercise.

The meta-question is addressed both in the answer you link and in the paper. I suggest you first read the paper, and then if you have more questions, you can ask them here in this site.

---
Tags: complexity-theory, oracle-machines
---


title: What is the Big O of $2^{\log \log n}$?

text:
# Question
Title: What is the Big O of $2^{\log \log n}$?
What is the Big O class of the following expression:

$$2^{\log \log n}$$

I think the Big O is $2^n$ as I assume $\log \log n$ to be $n$. Is my assumption correct?

# Answer
The big O (or rather, *a* big O) of $2^{\lg\lg n}$ is $O(2^{\lg\lg n})$. It is also $O(\log n)$, assuming $\lg$ is logarithm to base 2. Both expressions are tight, in the sense that in fact $2^{\lg\lg n} = \Theta(2^{\lg\lg n}) = \Theta(\log n)$.

The morale is that any expression can function as big O. We are usually aiming at a *simple* expressions, which is why we use $O(n^3)$ for $2n^3 + 15n\log$, for example. There are some canonical big O expressions, such as $O(n^a\log^b n)$. That means that if your function $f$ has order of growth $\Theta(n^a\log^b n)$, then you would usually describe it this way. Under this convention, a (tight) big O of $2^{\lg\lg n}$ is $O(\log n)$.
> 3 votes

---
Tags: asymptotics
---


# Question
Title: What are practical applications of AI Planning?
note: any tips toward making this more constructive will be highly appreciated.

I've dealt with ai-related problems, from searching algorithms, to computer vision, to machine learning. However none of which required planning, just algorithms following algorithms.

I'm not sure how effective will it be to implement AI Planning in practical problems, so I'm curious to know if there's a significant effect in doing so. Like at what point does the programmer/designer realize we need to apply AI Planning to solve this.

# Answer
\[*In the following, I am providing links to some events in 2011/2013, but you can find much more looking for previous years*\]

By AI Planning I assume that you mean Automated Planning (STRIPS, SAS$^+$ and so on) instead of path-planning and other problems more tightly related to robot navigation. If this is the case, SPARK is the right forum to look at.

Other practical applications are often discussed at the main track of the conference ICAPS. A couple of examples:

1. Maria Fox, Derek Long, Daniele Magazzeni: *Automatic Construction of Efficient Multiple Battery Usage Policies*. ICAPS 2011
2. José E. Flórez, Álvaro Torralba Arias de Reyna, Javier García, Carlos Linares López, Angel García Olaya, Daniel Borrajo: *Planning Multi-Modal Transportation Problems*. ICAPS 2011 (admittedly, I am adding here a reference of my own, beg your pardon, I did just because it was easier for me to locate the reference).

Hope this helps,
> 1 votes

---
Tags: reference-request, artificial-intelligence, applied-theory, planning
---


# Question
Title: In what context does "definition" arise?
If I am correct, the concept of a "theorem" doesn't appear until the concept of a formal system is introduced. "Definition" is used more often than "theorem" is. So I wonder if the concept of "definition" also arise in a formal system, or some other "system" or "structure"?

Is the definition of something just a name for that thing?

Does "what a definition of something defines that thing to be" belong to the metalanguage?

Thanks.

# Answer
> 4 votes
There are two notions of definition: definition in the meta-language and definition in the language. When developing logic and formal systems as a mathematical field, we use definitions in the meta-language. For example, we could define various notions relating to first-order logic. These are ordinary definitions just as in any other mathematical area.

Definitions in the language, in contrast, are abbreviations. For example, suppose that we are studying propositional logic, and our original language includes only the connectives $\lnot$ and $\lor$. We can define $\land$ by $$ A \land B = \lnot (\lnot A \lor \lnot B). $$ This is just an abbreviation. Whenever we use $\land$, we actually mean the expression above. More complicated examples are definitions of functions: a function $f(x)$ is defined as the unique $y$ such that some relation $R(x,y)$ holds. When defining functions, we also prove that $y$ always exists and is always unique. It is still an abbreviation, though.

There are two corresponding notions of theorems. Theorems in the metalanguage are results proved as in any other mathematical field. Theorems in the language are results provable from the axioms of the formal system using the derivation rules of the system. The two notions are very similar, however, in contrast to the situation with definitions.

---
Tags: proof-techniques
---


# Question
Title: Stable marriage problem preferential to asking side
Watching this youtube video: https://www.youtube.com/watch?v=w1leqkpDaRw it described the problem with the stable marriage problem, that the asking side get a better deal then the asked site. Meaning that the result may differ if the woman ask the men instead of the men asking the women. I have test this and found it to be true, but i can not find any scientific papers on this, so i where hoping that some of you guys might know of one or more?

# Answer
> 2 votes
One place to look at is the classic book The stable marriage problem. The link provides a relevant excerpt, showing that the matching produced by the standard Gale–Shapley algorithm is *male optimal* and *female pessimal*: any man gets the best possible partner (in his view) he can get in any perfect matching, and any woman gets the worst possible partner (in her view) she can get in any perfect matching. If we switch men and women, we will obtain the female optimal, male pessimal matching.

The quoted book, as well as Knuth's book on the subject, contain other material on stable marriages, including the number of different stable marriages, the lattice structure of stable marriages, sampling a random stable marriage, related problems such as the stable roommate problem, and much more.

From another angle, a distinctly different algorithm for the stable marriage problem has been developed by Subramanian and picked up by Feder; see for example Section 6 of this paper.

---
Tags: algorithms, assignment-problem
---


# Question
Title: Adding a node between two others, minimizing its maximum distance to any other node
We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a new node, such that the length of the path $(a,c,b)$ is equal to the inital length of $(a,b)$, and such that the choice of the length of $(a,c)$ minimizes the maximum distance of node $c$ to any other node of the graph. Is there any graph-theory based algorithm that can solve such problem rather than brute force?

Actually, the existence of the original edge $(a,b)$ is not essential. Only the end nodes $a$ and $b$, and the length matter.

For example we have a graph:

```
1 2 10
2 3 10
3 4 1
4 1 5

```

In every line the first two values indicate the node number, and the 3rd one is the corresponding edge value. Now I want to find a new node $c$ between nodes 1 and 2. The answer gives a node $c$ at distance 2 to node 1 (and distance 8 to node 2). The distance of node $c$ is 2 to node 1, 8 to node 2, 1+5+2=8 to node 3, and 5+2=7 to node 4. The maximum distance is 8, which is minimal for all possible choices of the length of $(a,c)$.

# Answer
## Introduction

This answer is in two parts.

The first is an **analysis of the problem** mixed with a sketch of the algorithm to solve it. As it is my first version, it is detailed, but results in an algorithm that is a bit more complex than needed.

It is followed by a **pseudo-code version** of the algorithm, written sometime later, as the algorithm was clearer. This pseudo-code is more direct, and somewhat simpler, but probably easier to understand after reading the first part.

In retrospect, the more important ideas are:

* to see that the maximum distance of a node to the new node C, as a function of the length of $(A,C)$, is given by the superposition of roof shaped (inverted V) curves, characterized by their top, associated to nodes of the graph.
* to see that irrelevant curves can be eliminated efficiently by a scan in monotonic order of abscissa of tops (with minimum backtrack).
* then minimal points can be enumerated simply by intersecting the remaining curves two by two, again in monotonic order of abscissa of tops.

## Sketch of an algorithm

NOTE: I changed the initial presentation of the question to get a more standard view of graphs, by considering that the edge $(A,B)$ is replaced by a new node $C$ and two edges $(A,C)$ and $(C,B)$ with the same total length as $(A,B)$.

Let $(A,B)$ be the distinguished edge, and let $l$ be its length. Let $e$ and $n$ be respectively the number of edges and the number of nodes in the graph.

First you remove the edge $(A,B)$. Then, for every node $U$ of the graph, you compute the distance $\alpha(U)$ between $A$ and $U$, and the distance $\beta(U)$ between $B$ and $U$. This can be done with Dijkstra's shortest path algorithm, in time $O(e+n\log n)$.

Then you add a new node $C$ with an edge $(A,C)$ and an edge $(C,B)$, of length respectively $a$ and $b$, such that $a+b=l$. The length $a$ is not known, and is to be found so as to minimize the distance of the most remote node to node $C$. The distance of $C$ to $A$ or $B$ may be 0.

The difficulty of the problem is that the node most distant from $C$ via $A$ may be close to $C$ via $B$, and thus does not matter. Also, a node closer to $C$ via $A$ than via $B$ may inverse that situation as $C$ moves between $A$ and $B$, i.e. as $a$ varies in $\[0,l\]$.

We consider three sets of nodes in the graph, forming a partition of all nodes:

* the set $N\_A$ of nodes that are always closer to $C$ via $A$ independently of the value of $a$: $N\_A=\\{U|\alpha(U)+l\leq\beta(U)\\}$
* the set $N\_B$ of nodes that are always closer to $C$ via $B$ independently of the value of $a$: $N\_B=\\{U|\beta(U)+l\leq\alpha(U)\\}$
* and $N\_{AB}$ the set of nodes that can be closer to $C$ via $A$ or via $B$, depending on the value of $a$, actually closer via $A$ for smaller values of $a$, and closer via $B$ for larger values of $a$ in $\[0,l\]$: $N\_{AB}=\\{U\mid\alpha(U)+l\>\beta(U) \wedge \beta(U)+l\>\alpha(U)\\}$

Let $U\_A$ the node in $N\_A$ most remote from $A$, and $U\_B$ the node in $N\_B$ most remote from $B$.

No other node in $N\_A\cup N\_B$ is ever more distant from $C$ than the more distant of these two nodes, whatever the distance $a$ of $(A,C)$. Hence all other nodes in $N\_A\cup N\_B$ can be discarded for the computation of the optimal value of $a$.

Note that it may happen that $N\_A$, or $N\_B$, or both, are empty. In which case, the corresponding nodes $U\_A$ and/or $U\_B$ do not exist.

We will build a **distance curve** on a plane with coordinate $(x,y)$, which will ultimately represent the longest distance $y$ of a node from $C$ as a function of the distance $x=a$ of $C$ from $A$. Hence $x=a\in\[0,l\]$

This distance curve is actually a zig-zag composed of segments angled $\pm 45^\circ$. Once it is built, the point minimizing the longest distance is to be found in the minimal points of the curve. There may be several such points. All these points have to be computed, and then compared.

We describe below how to compute them.

Actually, we consider a collection of simpler distance curves, with only one or two segments in the interval $\[0,l\]$, such that the longest distance of a node from $C$ is always on or above the curve. The final curve is obtained by taking for every value of $x$ the maximum value of $y$ given by one of the distance curves. This can be done formally by computing the intersection of the segments in an ordered fashion.

First we have (at most) two distance curves composed of only one segment. These are the curves corresponding to the distance of $U\_A$ and $U\_B$ to $C$. The first is upward at a $45^\circ$ angle, and the second is downward at a $45^\circ$ angle.

Assuming no other node is ever more distant from $C$, the optimal value of $a$ is the abcissa of their intersection. At that abscissa, that value for $a$, the nodes $U\_A$ and $U\_B$ are at the same distance from $C$. Hence the distance is minimum when $a$ satisfies the equation $\alpha(U\_A)+a=\beta(U\_B)+b$. Since $a+b=l$, this gives $\alpha(U\_A)+a=\beta(U\_B)+l-a$, and finally $a=(\beta(U\_B)-\alpha(U\_A)+l)/2$. This corresponds to a distance $y=(\alpha(U\_A)+\beta(U\_B)+l)/2$ of both nodes to $C$.

Together, the two curves give a V shaped curve, with a minimum at the point just computed.

But we also have to account for all the nodes in $N\_{AB}$. The distance of a node $U\in N\_{AB}$ to $C$ first increases with $x$ while the shortest path goes through $A$, them it decreases with $x$ when the shortest path goes through $B$. Hence, the corresponding distance curve is formed of two segments, roof shaped, with a maximum at an abscissa such that the distance to $C$ is the same through $A$ or through $B$. This gives the equation $\alpha(U)+a=\beta(U)+b$. Resolving it as above, we get $x=a=(\beta(U)-\alpha(U)+l)/2$, and $y=\alpha(U)+\beta(U)+l)/2$. We note $T\_U$ (for Top of $U$) the point with these coordinate. The top $T\_U$ characterizes the roof shaped distance curve for node $U$ since the slope of both side is $\pm 45^\circ$.

Now all the difficulty of the problem is that several nodes $U\in N\_{AB}$ may be such that $T\_U$ is above our first V-shaped curve, which will lead to the final zig-zag line.

But, we first can eliminate all nodes $U\in N\_{AB}$ such that $T\_U$ is below the V-shaped distance curve, as they will not ever contribute to the longest distance. This is easily done and is skipped here for clarity.

Then we want also to eliminates all nodes $U\in N\_{AB}$ such that their roof-shaped curve is always below the curve of another node $V\in N\_{AB}$. This is determined by the position of their tops, and we say that $T\_V$ dominates $T\_U$, or that $V$ dominates $U$. Actually $T\_V$ and $T\_U$ are in a domination relation iff the absolute value of the abcissa difference is less than the absolute value of the ordinate difference. The dominating node/top is the one with the highest ordinate.

For this purpose, we first sort all tops of the remanining nodes of $N\_{AB}$ in ascending order of increasing abscissa. This is done in time $O(n\log n)$.

Then we remark that if top $T\_U$ dominate a non adjacent top $T\_V$, then any intermediary top $T\_W$ dominate $T\_V$, or is dominated by $T\_U$, or both. Hence, to eliminate all nodes/tops that are dominated, on can simply proceed from left to right (by increasing abscissa), comparing only adjacent nodes, and removing any that is dominated. If the node on the right is dominated, it is removed and the node on the left is compared again to the next right. If the node on the left is dominated, it is removed and the node on the right is then compared with the previous one on its left. If none dominates the other, then the node on left is kept, and the node on right is then compared with the next right. This is repeated until the rightmost node/top has been thus processed, in time $O(n)$.

Whatever nodes have been kept do contribute to the final curve, in left to right order of their tops, with the line for $U\_A$ at the left and the line for $U\_B$ at the right, if they exist. The minima are easy to compute by considering the intersections of the contributing curves from left to right, in time $O(n)$.

Finally, the abcissa for the smallest distance of all nodes to $C$ may be found by a linear scan of all minima for the lowest ones. They may actually be several such abscissa, i.e. values for the length $a$ of edge $(A,C)$.

If the distances have to be integers, the abscissa of the minima can be rounded up or down.

**The time complexity** of the algorithm is: $O(e+n\log n)$.

*With thanks to user3153970 who remarked that my initial solution was not quite correct.*

## Pseudo-code version

The procedure described in the analysis of the problem is modified or improved in some ways.

* the length `l` is changed to `d` to avoid confusion with the number `1`.
* for simplification, the V curve is replaced by two tops of roof curves placed on both end of the interval \[0,d\].
* the sets $N\_A$ and $N\_B$ need not be created. Only $d\_A$ and $d\_B$ are needed, briefly, to crate the two extra tops.
* the set $N\_AB$ is not created either, only the corresponding set (actually a multiset, or bag, that may be implemented as a list) of tops, as two distinct nodes may produce the same top, if at the same distance of A and B.

(*bugs are provided free of charge*)

```
d := distance (A,B)
none := -1     % programming trick - none is for distances to be ignored %
Remove the edge (A,B) from the graph.
Using Dijkstra's shortest path algorithm, for every node $U$ compute its shortest
    distances α(U) and β(U) to respectively A and B.
d_A := none
d_B := none
  % We use lists of pairs, representing the [x,y] coordinate of points, where the %
  % abcissa x stands for the choice of length (A,C), and the ordinate y stands is the %
  % distance of some node to C. %
  % The call first(L) returns a pointer to the first pair of list L. %
  % Given a pointer t to a pair, t.x and t.y give the two components of the pair, %
  % and the functions prev and next return a pointer to the previous or the next pair, or %
  % NIL if it does not exist. The call add([a, b], L) adds the pair [a, b] to the list L. %
  % The call remove(t) removes the element pointed by t from its list. %
For every node U do
T := []     % T is the list of tops of curves for individual nodes %
    if    α(U)+d ≤ β(U) then d_A := max(d_A, α(U))
    elsif β(U)+d ≤ α(U) then d_B := max(d_B, β(U))
    else add( [(β(U)-α(U)+d)/2, (β(U)+α(U)+d)/2], T)
% Instead of V curve, create dummy tops at ends of [0,d] interval %
if d_A ≠none then add( [d, d_A+d], T)
if d_B ≠none then add( [0, d_B+d], T)
Sort T in increasng order of abscissa
% Remove from T all tops that are dominated by another top %
t1 := first(T)
t2 := next(t1)
Repeat
    if abs(t1.x-t2.x) ≤abs(t1.y-t2.y)
    then  % one top dominates the other %
        if t1.y≥t2.y
            then  % t1 dominates %
            remove(t2)
            t2 := next(t1)
            if t2=NIL then exit loop
        else % t2 dominates %
            remove(t1)
            t1 := pred(t2)
            if t1=NIL then
                t1 := t2;
                t2 := next(t1)
                if t2=NIL then exit loop
     else % neither top dominate the other %
         t1 := t2
         t2 := next(t1)
         if t2=NIL then exit loop
% Compute all local minima %
M := []  % M is the list of minima, where roof shaped curves intersect, %
         % or intersect the boundaries of the interval [0.d]. %
t2 := first(T);
if t2.x≠0 then add( [0, t2.y-t2.x], M)
repeat
    t1 := t2
    t2 := next(t1)
    if t2=NIL then exit loop
    add( [(t1.y-t2.y+t1.x+t2.x)/2, (t1.y+t2.y+t1.x-t2.x)/2], M)
if t2.x≠d then add( [d, t2.y-d+t2.x], M)
Select in M the pairs with the smallest ordinates. Their abcissas are all
    the possible answers to the problem.

```

If the solutions must be in integer values, it is possible to round the coordinates of the points in M to the nearest integer(s), before selecting the pairs with smallest ordinates. However some more analysis is needed to check whether it can involve passing over a top, and whether abcissas and ordinates are always integer simultaneously. This is left to the reader as an exercise.

All bug reports are welcome.
> 5 votes

# Answer
Edit: For a counterexample, see the comment below. The description of the problem itself might still, however, be helpful.

Let me first rephrase your question. You are given a weighted graph with positive weights, which are interpreted as distance. We can think of each edge $(a,b)$ of length $\ell$ as consisting of a continuum of points: for each $x \in \[0,\ell\] $ there is a point at distance $x$ from $a$ and $\ell-x$ from $b$. Given an edge $(x,y)$, you want to find a point $p$ on the edge that minimizes $\delta = \max\_v d(p,v)$. Suppose that $p$ is at distance $a$ from $x$ and $b$ from $y$ (so $a+b = w(x,y)$, where $w(e)$ is the weight on $e$). Then $d(p,v) = \min(a+d(x,v),b+d(y,v))$, and so you are trying to minimize $$ \delta = \max\_v \min (a+d(x,v),b+d(y,v)) = \min\big(a + \max\_v d(x,v), b + \max\_u d(y,u)\big).$$ This proposes the following algorithm:

1. Determine the maximal distance $d\_x$ of a node from $x$, and the maximal distance $d\_y$ of a node from $y$.
2. Let $a$ be the solution of $a+d\_x = (w(x,y)-a)+d\_y$.
3. If $a \< 0$, return $x$. If $a \> w(x,y)$, return $y$. Otherwise, return the point at distance $a$ from $x$.

This algorithm runs in linear time.
> 1 votes

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: Can an intersection of two context-free languages be an undecidable language?
I'm trying to prove that

$\exists L\_1, L\_2 : L\_1$ and $L\_2$ are context-free languages $\land\\;L\_1 \cap L\_2 = L\_3$ is an undecidable language.

---

I know that context-free languages are not closed under intersection.

This means that I can produce an $L\_3$, which is undecidable.

An example would be $L\_1 = \\{a^n | n \in \mathbb{N}\\} \cap L\_2 = \\{0\\} = \emptyset$.

* Is this a correct proof?
* If not, how can I prove this theorem?
* Is the empty language decidable?

# Answer
> 9 votes
Context-free languages are decidable, and decidable languages are closed under intersection.

So, though the intersection of two CF languages may not be CF, it is decidable.

Remarks on your example:

* $\emptyset=\\{\\}\neq$ $\\{0\\}$
* $L\_1\cap\emptyset=\emptyset$ which is context-free.
* You cannot prove your claim, because it is wrong
* the empty language is decidable: the answer is always "no, this string is not in the empty set".

# Answer
> 6 votes
Make sure that you understand what *decidable* means for a language $L$: it means that there is an algorithm that, given $x$, terminates and outputs either $x \in L$ or $x \notin L$ (correctly). It is easy to construct such an algorithm for the language $L = \emptyset$: it always returns $x \notin L$.

As babou mentions in their answer, while context-free languages are not closed under intersection, it is easy to decide whether $x \in L\_1 \cap L\_2$ for any context-free $L\_1,L\_2$:

* First determine whether $x \in L\_1$ and $x \in L\_2$
* If both are true:
    + return $x \in L\_1 \cap L\_2$
* Otherwise:
    + return the converse.

As babou mentions, we only really use the fact that $L\_1,L\_2$ are themselves decidable.

---
Tags: computability, context-free, undecidability
---


# Question
Title: Can the definition of regular languages be simplified?
Wikipedia says

> The collection of regular languages over an alphabet Σ is defined recursively as follows:
>
> * The empty language Ø is a regular language.
> * For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.
> * If A and B are regular languages, then A ∪ B (union), A • B (concatenation), and A\* (Kleene star) are regular languages.
> * No other languages over Σ are regular.

I think that if it is closed under concatenation, then it must be closed under Kleene star, because we can take B to be A. So the definition can be without being closed under Kleene star?

# Answer
> 11 votes
No. Closure under concatenation means that, if $A$ and $B$ are regular languages, then so is the language of strings formed by concatenating taking one string from $A$ and one from $B$. Closure under Kleene star means that, if $A$ is a regular language, then so is the langauge formed by taking *any* finite number of strings from $A$ and concatenating them.

If you delete Kleene star then every regular language would be finite. The reason is that any given regular language must be formed by a finite number of operations from the basic languages ($\emptyset$ and singletons). But any language whose definition involves no Kleene stars and only $k$ concatenations can only contain strings of length at most $k$, so it must be finite (it has at most $|\Sigma|^k$ strings in it).

Since there are infinite regular languages, the languages formed without Kleene star are a strict subset of the regular languages.

---
Tags: formal-languages, terminology, regular-languages
---


# Question
Title: Algorithm for distributing members over activites (with individual preferences)
So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils assigned to the activity change. (So in block 1 pupil x takes part in activity a and in the second block in activity d).

Before this day starts, we give make lists in which each pupil can tell us his 3 (or 4) favorite activities (he only takes part in two of them, these again are ordered from most "favorite" to least) in which he wants to take part. Now our job is to assign these pupils in a way that we have the best overall satisfaction among the pupils (so everybody did more or less did get his/her chosen activities).

What would be a good algorithm to solve this? Is there any way to do this, apart from calculating such a "satisfaction" value for each possible solution?

An optional feature would be that if someone can't get in to his/her project, they would get into a similar one according to some predefined distance.

# Answer
Here is partly a solution, partly an approximation:

Let $T$ denote set of time blocks. Let $C$ denote set of children. Let $A$ denote set of activities.

Let $T\_i$, $C\_i$, $A\_i$ denote $i$-the time block, child, activity. Let $S\_{ij}$ denote the satisfaction for child $i$ from activity $j$. Let $M\_j$ denote maximum number of pupils that can participate in $j$-th activity.

1. Create a bipartite graph where pupils are on the left side and activities are on the right.
2. For each pupil $C\_i$ and activity $A\_j$ create an edge with capacity equal to 1 and cost equal to $-S\_{ij}$.
3. Create a source and connect it to all $C\_i$, capacity equal to $|T|$.
4. Create a sink and connect all $A\_j$ to sink, with capacity equal to $M\_j * |T|$.
5. Find minimum cost maximum flow on this graph.
6. Now for each pupil you have assigned number of activities equal to the number of time blocks. If there exists a valid assignment of activities to pupils, the algorithm above will surely find some (not necessarily valid) assignment.

Let $P\_j$ denote number of pupils that were assigned to $j$-th activity after the algorithm above.

Now, for the approximation part:

1. Let's create a grid of $|T|$ rows and $|A|$ columns, $i$-th row denoting all activities that will happen during $i$-th time interval.
2. Let's fill in our table. We will loop through it's columns, and for a column, we will loop from top to the bottom of the row. In parallel let's loop through all activities in some order. For activity $j$ let's put into the next cell of the table $j$ activity and move to the next cell, total of $P\_j$ times for $j$ activity.
3. Since $P\_j \le M\_j * |T|$, in each row of the table there will be at most $M\_j$ entries of $j$-th activity, satisfying the condition that during one time interval only $M\_j$ persons can participate in $j-th$ activity.
4. Each row should have some permutation of pupils. Let's for each for find maximum matching between pupils and and activities in some row. Two problematic situations might occur:

* Pupil is assigned to the same activities in different time blocks. We can overcome this in two possible ways:

    a. Once pupil was assigned to some activity in one row, don't connect the appropriate pupil vertex to the appropriate activity vertex in the following rows.

    b. Who ever said that satisfaction decreases if you participate in your favorite activity again? ;)
    * For some rows, we may not find perfect matching. Well, this is why it is an approximation, not a solution. since it is maximum matching, we will still find for many pupils their preferred activities from first part. For others, we can match them with other activities in a row.

Possible heuristics:

Match pupils in a row not using bipartite matching, but using Hungarian algorithm (for perfect maximum weighted matching, with weights equal to $S\_{ij}$, where $j$ is activity in the appropriate cell in a row.

Try different orderings when creating a grid. For example, we may try to use simulated annealing based on the permutation of order, in which we put activities to the grid, and transition between steps that results in a swap of neighboring / any two elements in this permutation.
> 1 votes

---
Tags: algorithms, matching, assignment-problem
---


title: A quine in pure lambda calculus

text:
# Question
Title: A quine in pure lambda calculus
I would like an example of a quine in pure lambda calculus. I was quite surprised that I couldn't find one by googling. The quine page lists quines for many "real" languages, but not for lambda calculus.

Of course, this means defining what I mean by a quine in the lambda calculus, which I do below. (I'm asking for something quite specific.)

In a few places, e.g. Larkin and Stocks (2004), I see the following quoted as a "self-replicating" expression: $(\lambda x.x \\; x)\\;(\lambda x.x \\; x)$. This reduces to itself after a single beta-reduction step, giving it a somehow quine-like feel. However, it's un-quine-like in that it doesn't terminate: further beta-reductions will keep producing the same expression, so it will never reduce to normal form. To me a quine is a program that terminates and outputs itself, and so I would like a lambda expression with that property.

Of course, any expression that contains no redexes is already in normal form, and will therefore terminate and output itself. But that's too trivial. So I propose the following definition in the hope that it will admit a non-trivial solution:

*definition* (tentative): A quine in lambda calculus is an expression of the form $$(\lambda x . A)$$ (where $A$ stands for some specific lambda calculus expression) such that $((\lambda x . A)\\,\\, y)$ becomes $(\lambda x . A)$, or something equivalent to it under changes of variable names, when reduced to normal form, for *any* input $y$.

Given that the lambda calculus is as Turing equivalent as any other language, it seems as if this should be possible, but my lambda calculus is rusty, so I can't think of an example.

**Reference**

James Larkin and Phil Stocks. (2004) "Self-replicating expressions in the Lambda Calculus" Conferences in Research and Practice in Information Technology, 26 (1), 167-173. http://epublications.bond.edu.au/infotech\_pubs/158

# Answer
You want a term $Q$ such that $\forall M \in \Lambda$:

$$QM \rhd\_\beta Q$$

I will specify no further restrictions on $Q$ (e.g. regarding its form and whether it is normalising) and I will show you that it definitely must be non-normalising.

1. Assume $Q$ is *in* normal form. Choose $M \equiv x$ (we can do so because the theorem needs to hold for all $M$). Then there are three cases.

* $Q$ is some atom $a$. Then $QM \equiv ax$. This is not reducible to $a$.
    * $Q$ is some application $(RS)$. Then $QM \equiv (RS)x$. $(RS)$ is a normal form by hypothesis, so $(RS)x$ is also in normal form and not reducible to $(RS)$.
    * $Q$ is some abstraction $(\lambda x.A)$ (if $x$ is supposed to be free in $A$, then for simplicity we can just choose $M$ equivalent to whatever variable $\lambda$ abstracts over). Then $QM \equiv (\lambda x.A)x \rhd\_\beta A\[x/x\] \equiv A$. Since $(\lambda x.A)$ is in normal form, so is $A$. Consequently we cannot reduce $A$ to $(\lambda x.A)$.

So if such a $Q$ exists, it cannot be *in* normal form.
2. For completeness, suppose $Q$ *has* a normal form, but is not *in* normal form (perhaps it is weakly normalising), i.e. $\exists N \in \beta\text{-nf}$ with $N \not\equiv Q$ such that $\forall M \in \Lambda$: $$QM \rhd\_\beta Q \rhd\_\beta N$$

Then with $M \equiv x$ there must also be exist a reduction sequence $Qx \rhd\_\beta Nx \rhd\_\beta N$, because:

* $Qx \rhd\_\beta Nx$ is possible by the fact that $Q \rhd\_\beta N$.
    * $Nx$ must normalise since $N$ is a $\beta$-nf and $x$ is just an atom.
    * If $Nx$ were to normalise to anything other than $N$, then $Qx$ has two $\beta$-nfs, which is not possible by a corollary to the Church-Rosser theorem. (The Church-Rosser theorem essentially states that reductions are confluent, as you probably already know.)

But note that $Nx \rhd\_\beta N$ is not possible by argument (1) above, so our assumption that $Q$ has a normal form is not tenable.
3. If we permit such a $Q$, then, we are certain that it must be non-normalising. In that case we can simply use a combinator that eliminates any argument it receives. Denis's suggestion works just fine: $$Q \equiv (\lambda z.(λx.λz.(x x)) (λx.λz.(x x)))$$ Then in only two $\beta$-reductions: \begin{align} QM &\equiv (\lambda z.(λx.λz.(x x)) (λx.λz.(x x))) M \\ & \rhd\_{1\beta} (λx.λz.(x x)) (λx.λz.(x x)) \\ & \rhd\_{1\beta} (λz.((λx.λz.(x x))(λx.λz.(x x))) \\ & \equiv Q \end{align}

This result is not very surprising, since you *are* essentially asking for a term that eliminates any argument it receives, and this is something I often see mentioned as a direct application of the fixed-point theorem.
> 10 votes

# Answer
One one hand this is impossible, because a quine is supposed to output its own code, and the pure lambda calculus has no means for performing output.

On the other hand, if you assume that the resulting term is the output, then every normal form is a quine.

For example, lambda term $(\lambda x. x)$ is already a normal form, then assuming that its output is the resulting normal form, the output is $(\lambda x. x)$. Thus $(\lambda x. x)$ is a quine.
> 10 votes

# Answer
Here is a proposition:

We choose $A$ to be a fixpoint of the function $f=\lambda t. (\lambda z.t)$.

This can be done by using the fixpoint combinator $Y=\lambda g.((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)))$, and setting $A=Y f=(\lambda x.\lambda z.(x\ x))\ (\lambda x.\lambda z.(x\ x)) $.

Now we show that $A$ is a quine. Indeed $A$ reduces to $\lambda z.A$, so it means that for any $y$, $(\lambda z.A)y \to\_\beta A \to\_\beta (\lambda z.A)$.
> 8 votes

---
Tags: lambda-calculus
---


# Question
Title: Generative grammars and analytic grammars?
1. What are a generative grammar and an analytic grammar?
2. How are they different from a formal grammar?
3. Is the recursive definition of the language of a propositional calculus, a first order logic system, or the set of lambda expressions a generative or analytic grammar?

# Answer
Generative Grammars were proposed by Chomsky in the 1950's as a possible base for a theory of syntax of Natural Languages. The issue was, and still is, to provide a mathematical description of (some aspects of) Natural Language, so as to address more formally (more scientifically?) the analysis of natural language. Other approaches have since been developed, though grammars remain often one basic ingredient of the analysis.

Their mathematical description is given in the Wikipedia article you reference. You can see yourself that **Generative Grammars are Formal Grammars** in the usual sense of formal language theory. Indeed the work of Chomsky was part of the founding contributions to formal language theory.

*Analytic grammars* is mostly a pragmatic technological concept.

Generative grammars were created to describe the syntax of natural language, and the idea is that sentences of the language are obtained from the initial symbol by applying the rules.

**Syntax analysis** is the reverse problem: given a sentence of the language, can one find the succession of rules that were applied, and were in the string they were applied, in order to generate the sentence.

This problem is simple for type 3 grammars, which are the grammars of regular sets, but they are too weak to describe large parts of natural language.

Type 0 and type 1 grammars are technically difficult to handle, both theoretically and pragmatically, and the most successful class of generative grammars has been the type 2 grammars, which are the context-free grammars, of which several variants (no longer strictly context-free) were since developed, as they are more powerful while preserving many of the interesting qualities of CF grammars.

Still, syntax analysis, also known as *parsing*, remained a somewhat difficult task, even in the CF case, given the very limited power of the computers of the times.

Hence, subclasses of the CF grammars, and some variants, were identified, characterized by the fact that they had a corresponding parsing technology that was considered more tractable.

Some people thought it useful to describe the language syntax (especially natural and programming languages, not mathematical languages afaik) directly with such specialized classes or variants of CF languages, so as to directly address the parsing problem (actually, I am not sure they all are context-free, or deeply analyzed regarding their mathematical properties)

This was a very pragmatic approach, to meet the computational constraints of the computers. These grammars were conceptualized as *Analytic Grammars*, but this is more circumstancial technology than a fundamental concept.

The role of formal grammars in syntax is definitional and descriptive. It should be simple, expressive and perspicuous with respect to semantic concepts and whatever is understood of the language structure, and generally easy to understand for human beings. The issue of mechanized processing by computers should be separated.

In general, when formalizing concepts mathematically, one must choose the form that is the most appropriate to understand the concepts and to reason about them, and to serve as reference definition. The description must be perspicuous, expressive and hopefully intuitive. But it should avoid concerning itself with practical computational issues. This typically what is attempted with denotational semantics of programming languages.

Then there can be other descriptions that are intended to better meet technological and computational need, including possibly current hardware technology and limitations and algorithmic know-how, but may not be very convenient for human understanding and mathematical reasonning. These are to be seen as secondary definitions used by specialists and implementors, but not to be seen by most users.

One of the roles of implementors is to use these technological descriptions for whatever purpose, after proving that they are equivalent to the better reference description.

To take an image, there is an abstract way to describe a car by its functionality and security measures. Most people, including legislators, need no more. Then there can be other ways of describing them by describing their internal make, but that is only a concern for car makers, and it is far from a convenient description or a car for users and legislators. Actually they do not care, as long as the maker can produce a correctness proof, i.e. can show that the car works consistently with the definition used by drivers and legislators.

So-called "analytic grammars" are to be placed in this category: a device for implementors of parsers (i.e., syntax analyzers) for languages, not a concept for understanding languages. I guess **Analytic grammars could be seen as formal grammars, or may be as automata in some cases**, but they are used specifically for their algorithmic properties. But they first have to be proved conformant (i.e. generating the same language) to the more natural grammar actually used to define the syntax. And the relation with semantics has also to conform with the corresponding semantics for the natural defining grammar.

Actually, things may be a bit more subtle or intricate, but this is to give an idea of the role of multiple definitions of the same language, and to explain the purely technical purpose of so-called "analytic grammars".

Definition of mathematical languages and formalism are always generative grammars, usually context-free, as what is desired is expressiveness, clarity and mathematical tractability.
> 5 votes

---
Tags: formal-languages, terminology, formal-grammars
---


# Question
Title: Emulation, interpreters and parallel execution
I'm interested in how software emulators of old game consoles work. These must consist of an interpreter for the machine language of the emulated processor.

If I have understood correctly an interpreter, for each instruction: reads the instruction and scrolls a huge switch-case (or sequence of `if-elseif-...`) like structure comparing the instruction with each possible instruction in the architecture of the emulated processor, and then executes the related branch.

Is it possible to **distribute** the switch-case into severial thread, and give them to a parallel processor (GPGPU, FPGA, ...) ?
In my opinion, this problem is inherently parallel, because if **1 core = 1 opcode**, and each core can **read the next opcode**, then just the right core will execute the instruction.
After finishing the execution of the current instruction, then it does the same thing for the next one.

**Is it a good idea to create an interpreter (slowest type of emulation, but also the easiest type of emulator and free of problems like self-modifying code) and make it faster using distribute computing?**
Each instruction means a different process for a different core
No problem with concurrency, because just one instruction branch is executed.
Is this a good idea or there is any problem?

# Answer
> 2 votes
Your understanding of the complexity of a `switch` or `case` statement is not correct. In most languages these statements make a decision based on the value of a single integer variable. If those integers are densely packed together (as they typically are when an interpreter is decoding an instruction opcode) then the compiler turns this into an $O(1)$ lookup table.

The table is simply an array of addresses. The control variable for the `switch` statement is used to determine the offset into the array. Then the code simply jumps to the address given at that offset in the array.

In the case where the integers are not densely packed together then the compiler builds a logarithmic-height tree of branches each of which divides the remaining range in half, like in the children's "number guessing game." So, for example, if you have a `switch` statement over 1000 different cases spread over the numbers 0-1000000000, then you'll be able to determine whether any given input is one of the cases, and which case, in less than 10 comparisons. (Because $\log\_2 1000 \< 10$.)

---
Tags: distributed-systems, parallel-computing, interpreters
---


# Question
Title: Is there a 'string stack' data structure that supports these string operations?
I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing the set of strings $S$.

* `Add-Prefix-Set` on $\mathcal{D}(S)$: given some set $T$ of (possibly empty) strings, whose size is bounded by a constant and whose string lengths are bounded by a constant, return $\mathcal{D}( \\{ t s\ |\ t \in T, s \in S\\} )$. Both these bounding constants are global: they are the same for all inputs $T$.
* `Get-Prefixes` on $\mathcal{D}(S)$: return $\\{ a \ | \ as \in S, a \in \Sigma \\}$. Note that I don't really mind what structure is used for this set, as long as I can enumerate its contents in $O(|\Sigma|)$ time.
* `Remove-Prefixes` on $\mathcal{D}(S)$: return $\mathcal{D}( \\{ s \ | \ as \in S, a \in \Sigma \\} )$.
* `Merge`: given $\mathcal{D}(S)$ and $\mathcal{D}(T)$, return $\mathcal{D}(S \cup T)$.

Now, I'd really like to do all these operations in $O(1)$ time, but I'm fine with a structure that does all these operations in $o(n)$ time, where $n$ is the length of the longest string in the structure. In the case of the merge, I'd like a $o(n\_1+n\_2)$ running time, where $n\_1$ is $n$ for the first and $n\_2$ the $n$ for the second structure.

An additional requirement is that the structure is immutable, or at least that the above operations return 'new' structures such that pointers to the old ones still function as before.

A note about amortization: that is fine, but you have to watch out for persistence. As I re-use old structures all the time, I'll be in trouble if I hit a worst case with some particular set of operations on the same structure (so ignoring the new structures it creates).

I'd like to use such a structure in a parsing algorithm I'm working on; the above structure would hold the lookahead I need for the algorithm.

I've already considered using a trie, but the main problem is that I don't know how to merge tries efficiently. If the set of strings for `Add-Prefix-Set` consists of only single-character strings, then you could store these sets in a stack, which would give you $O(1)$ running times for the first three operations. However, this approach doesn't work for merging either.

Finally, note that I'm not interested in factors $|\Sigma|$: this is constant for all I care.

# Answer
I thought for quite some time, but didn't find the problem with doing all of your operations in the most stupid possible way in a trie-like DAG structure:

# Add-Prefix-Set

Create a trie of strings from $T$. Connect each leaf node to the root of the old trie.

Complexity: $O(|T|)$

# Merge

Unite roots of two structures: make all children nodes of the second root children of the first node. You may now have multiple edges marked with the same character going from the same node.

Complexity: $O(1)$

# Lazy update of the root

1. For each character unite all children of the root accessible by the edges marked with this character. ($O(|\Sigma|)$ \+ Amortized $O(1)$ for each edge ever added)
2. Delete all edges going into the root from the top. (Can happen after Remove-prefixes, amortized $O(1)$ for each edge ever added)

# Get-prefixes

Lazy update the root. Now find all children of the root and report set of letters on edges going to them.

Complexity: $O(|\Sigma|)$

# Remove-prefixes

Lazy update the root. Unite all children of the root and set the root pointer to the result of this unite. Lazy update the new root.

Complexity: $O(|\Sigma|)$ \+ Lazy update

# Persistence

All information about this data structure can be saved in arrays, with $O(1)$ information per node plus $O(|\Sigma|)$ information for each child of the node. Each operation can be held out as set of assignments in these arrays. Use persistent range tree or any other data structure that can be viewed as a persistent array. Additional multiplier for memory and space complexity $O(log N)$, where $N$ is the total number of characters in all queries.
> 5 votes

---
Tags: data-structures, time-complexity, strings, stacks
---


# Question
Title: Is a language closed under string concatenation, repetition, and/or taking substring regular?
Is a language $L$ regular, context-free, context-sensitive, recursively enumerable, or ..., if $L$ is closed under

* string concatenation, and/or
* string repetition, and/or
* taking substring?

Somehow related but not identical to https://cs.stackexchange.com/questions/28534/what-are-the-formal-grammars-of-the-following-recursively-defined-formal-languag

Furthermore, the same question if $L$ further satisfies that every string of length 1 is also in $L$?

# Answer
Considering how much you have been learning so far, you should try answering some questions by yourself.

For example, quite trivially, a language closed under string concatenation and "taking substring" is regular. The reason is that only two language have both closure properties: $\Sigma^\*$ and $\emptyset$.

Actually, I guess the empty set is closed under a lot of operations, since there are no strings to operate upon.

Given any non-empty language, if it is closed under "taking substring", all strings of length 1 are in the language (assuming the alphabet is restricted to what is actually used). And if it is closed under string concatenation, you can concatenate any number of these strings of length 1 in any order, thus producing any word in $\Sigma^\*$.

But your question is just too many questions, which is not customary on this site, even if there is some flexibility.
> 6 votes

---
Tags: formal-languages, closure-properties
---


# Question
Title: Use of Big-O Notation: Size of Input vs Input
It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the *size* of the input as opposed to the *input itself* (particularly in the case of numeric algorithms).

For instance, trial division for integer factorization takes up to $\sqrt N$ divisions to factor the integer $N$. However, the *size* of the input is the number of bits, $w = \lg(N)$. Thus, integer factorization takes $\mathcal{O}\left(2^{w/2}\right)$ time with respect to the size of the input ($w$ bits).

**My question:** Given the above, would it be considered correct to write in a CS article (relatively informal--on the scale of a blog post) to write that "integer factorization takes $\mathcal{O}(\sqrt{N})$ time *with respect to the input variable $N$*," and assume that the reader realizes they should substitute $w=\lg(N)$ to obtain the time complexity with respect to the size of the input?

# Answer
> 6 votes
You have it backwards, but you are on to an important distinction.

$O(N)$ if $N$ is a number in the input is perfectly well-defined and can appear in, say, the $\Theta$-asymptotic of a runtime function.

In your example, note that $\sqrt{N} = 2^{w/2}$ and thus $O(\sqrt{N}) = O(2^{w/2})$ -- it's just another way of expressing the same function class, given the identity $w = \lg N$.

The distinction between $f(N)$ and $f(\langle N \rangle)$ is only important in the context of *complexity classes*. Many of those are defined along the lines of

> Class $X$ contains all problems for which there is an algorithm with runtime in $O(f(|x|))$ where $x$ is an input string.

For examples, see pseudo-polynomial problems/algorithms.

---
Tags: terminology, asymptotics
---


# Question
Title: Programming languages for genetic engineering
I'm interested in getting a Ph.D. and would love to work on a project such the GEC project at Microsoft Research, which studies the application of programming languages for synthetic biology and genetic engineering. What groups are doing work like this in a university setting?

# Answer
> 1 votes
I choose to reply in an answer rather than a comment because I think that is actually the proper answer to your question (and it is too long for a comment anyway).

1. Style

If you intend to do research and write papers for an audience, then you should learn to be easy to read. Any improvement costs only once to you, and saves time and energy to each one of your readers. That includes giving web references that can be clicked, rather than having to be cut and pasted in a browser window. That also include briefly telling your readers what the reference is about, so that they do not have to jump into unknown territory. (this is a comment on the original version of your question, before the friendly editing of David Richerby).

The same is actually true for programs. It is not enough to write a program that solves the problem, you should also make sure that it is easy to understand and to use, so as to spare aggravation to your users.
2. Substance

Getting a Ph.D entails doing a fair amount of research. The very first step is to find litterature that is relevant to your research topic. Usually, if you choose the topic, you are supposed to have some knowledge of it. In your case, you know of a project that is relevant. So that gives you names, keywords, and topics to search for on the web. Then some reading of that should give you a better understanding, increase your competence and allow you to search for more ... and find research groups that do that kind of work by looking at the authors of papers. Their affiliation is usually given, and many have a web site.

Doing this yourself will increase you general competence at doing research, and also increase your knowledge of the field. It is in no way wasted work. Doing if for you is not doing you a service. You would not think of getting someone on the net to write your dissertation for you. Of course, it does make sense to discuss issues and ask questions, but usually after doing what work you can, so as to spare the time of colleagues ... they do not have so much available.

But if you cannot do it yourself, you probably do not have the maturity to do research and you should rather consider another academic path, or professional path.

---
Tags: reference-request, programming-languages, bioinformatics, research
---


# Question
Title: Understanding the reason behind the μ (mu) operator
* What is the purpose of the $\mu$ operator?
* Is there a real world example?
* Is it correct that it can create partial functions out of total functions and it makes a function $g$ with k parameters out of a function $f$ with $k+1$ parameters?

# Answer
Adding the μ-operator to the five primitive recursive operators makes it possible to define all computable functions. It is well explained in wikipedia.
> 2 votes

---
Tags: recursion, mu-calculus
---


title: Reduce Set problem to SAT

text:
# Question
Title: Reduce Set problem to SAT
So the problem is, given some set $M = \\{x\_1,x\_2,\ldots,x\_n\\}$ and a set of subsets $S = \\{S\_1, S\_2, \ldots, S\_m\\}$ where $S\_i \subseteq M$. We want to find some set $X \subseteq M$ such that $|X| \le k$ and $X \cap S\_i \neq \emptyset$ for all $S\_i \in S$.

My solution, I would take some set $M = \\{x\_1,x\_2,x\_3,x\_4\\}$ and suppose $S\_1 = \\{x\_1,x\_2\\}$, $S\_2 = \\{x\_2,x\_3\\}$, $S\_3 = \\{x\_4\\}$. I would then transform this to a SAT instance to get:

$\phi = (x\_1 \vee x\_2) \wedge (x\_2 \vee x\_3) \wedge (x\_4)$

Clearly if $\phi$ is satisfiable then there exists some $X \subseteq M$ however this does not guarantee that $|X| \le k$.

So my question is, how can I reduce this problem further so that $|X| \le k$ in polynomial time?

**EDIT**

I realized there may be an easier way to reduce this to the **set-cover** problem but need confirmation that my idea is correct.

*Will post a new question containing this.*

# Answer
The final constraint you need to encode is that $k$ or fewer variables in the set ${x\_1, x\_2, ..., x\_n}$ is set true. There is a good reference question that outlines several methods for encoding a 1-out-of-$n$ constraint. Those methods can be extended to fit your constraint. Using a chain of adder circuits plus a comparison circuit seems the most straightforward method to me.
> 4 votes

---
Tags: complexity-theory, reductions, satisfiability
---


title: How to bound a running time equation?

text:
# Question
Title: How to bound a running time equation?
I simply need a standard way to find the upper and lower bound of a running time equation (please no shortcuts that only work for this specific problem)....

Example: $T(n)=\frac{c}{5}(4^{\left \lfloor \log\_{4} (2n^{2}) \right \rfloor +1}-1)$

I think I understand how to put it in $\Theta$, $\Omega$, and $O$ after I get the bounds.... But I can't figure out a standard way to find the bounds for the running time of an algorithm (it's all unrelated or obscure shortcuts) for any given formula. Any help out there?

EDIT: Apparently it might be thought I am asking for a specific number for each bound. I am not, I'm looking for how to find the equation that the bound gives.... For instance, on a problem (not this one), a bound might be $3^\frac{\ln a}{\ln n}+1$ for a certain bound.... The actual problem says to show your work putting the equation into $\Theta$ by bounding it on the upper and lower bounds. I need to know how to show work for that on this and similar problems. Make more sense?

# Answer
Every function is big $\Theta,\Omega,O$ of itself, so you can already put your result in big $\Theta,\Omega,O$ notation. Using $4^{\log\_4 (2n^2)} = 2n^2 = \Theta(n^2)$, you can also write $T(n) = \Theta(n^2)$; I'll leave you the details.
> 1 votes

---
Tags: asymptotics, lower-bounds
---


# Question
Title: What is the asymptotic behaviour of a sum of powers of three?
I'm more concerned with just finding big oh since that can be used to find big omega. I am also told I cannot use limits to find the answer.

I'm given: $3+9+27+\dots+3^n$. My first assumption is that $3^n = \Theta(3^n)$. The method we're supposed to use goes something like this:

$3+9+27+\dots+3^n\<3^n+3^n+\dots+3^n$

Or I think that's what we're supposed to do here. I'm not sure how to simplify a sequence of repeating $3^n$ in order to find a constant C.

Any help is appreciated.

# Answer
First, your assumption, `I'm more concerned with just finding big oh, since that can be used to find big omega` is a bit dangerous. You could indeed easily find a $O()$ upper bound for your sum, $S(n)=3^1+3^2+3^3+\cdots+3^n$ by observing that each term is less than $3^n$ so you could have $$ 3^1+3^2+\cdots+3^n\le \underbrace{3^n+3^n+\cdots+3^n}\_{n}=n3^n=O(n3^n) $$ but that's a huge overestimate (try it for, say, $n=5$) and so will almost certainly not serve as a suitable big-Omega bound\*. Instead, you could simply use the formula for a geometric series and get an exact value, but suppose you didn't know that formula (or were prohibited from simply invoking it).

On the way to finding a good estimate, you could always try this helpful idiom: We've written $S(n)=3^1+3^2+3^3+\cdots+3^n$ and so we also have $S(n+1)=3^1+3^2+3^3+\cdots+3^{n+1}$ so $$\begin{align} S(n+1)-3S(n)&=(3^1+3^2+\cdots+3^{n+1})-3(3^1+3^2+\cdots+3^n)\\ &=(3^1+3^2+\cdots+3^{n+1})-(3^2+3^3+\cdots++3^{n+1})\\ &= 3 \end{align}$$ But we also know that $S(n+1)=S(n)+3^{n+1}$ so we have $$ 3=S(n+1)-3S(n)=S(n)+3^{n+1}-3S(n)=-2S(n)+3^{n+1} $$ and so with a little algebra we find $$ S(n) = \frac{3^{n+1}-3}{2}=\frac{3}{2}(3^n-1) $$ Since we have an exact value for the sum, we can easily see that $S(n)=\Theta(3^n)$. However, if you need to establish explicit constants to show $S(n)\ge c\\,3^n$ (for big-omega) and $S(n)\le d\\,3^n$ (for big-o) it's not too difficult. (Hint, can you see that you can use any $d\ge 3/2$?)

---

$^\*$As an aside, you might have been misled in your choice of replacements at the very start by the proof that $1^k+2^k+3^k+\cdots+n^k\le n^k+n^k+\cdots+n^k=n^{k+1}$ which does indeed lead to a big-Theta estimate, though for a different sum.
> 7 votes

# Answer
Hint: use the formula for the sum of a geometric series.

Note that, when you write $3^n + \dots + 3^n$, you have $n$ terms so that sum evaluates to $n3^n\notin\Theta(3^n)$.
> 3 votes

---
Tags: asymptotics
---


# Question
Title: Which textbook can I use after a high school CS course?
I just finished the AP Computer Science course in high school and since my school does not have any further classes, I was thinking about getting a textbook and continuing my study. APCS goes through Big O, Arrays + ArrayLists, Recursion, Linked Lists, a rough overview of some other data structures and some sorting and searching algorithms (all in Java).

I will start Calculus in school next year (if that helps to determine math level).

Since I was thinking about participating in CS tournaments, I thought it would be useful to learn more about algorithms and data structures.

I was looking at two textbooks, *The Algorithm Design Manual* by Steven S Skiena and *Introduction to Algorithms* by Cormen et. al. I was wondering which one, if any of these, would best fit my situation.

# Answer
> 4 votes
Personally, I recommend either Algorithms by Dasgupta, Papadimitriou, and Vazirani, or *The Algorithm Design Manual* by Skiena.

The Algorithm Design Manual is super-practical and full of excellent pragmatic advice, useful stories, and is well-written and easy to read. If you want to help get ready for programming contests, I strongly recommend that one.

I think Dasgupta has a better introduction from the perspective of learning the conceptual material, the theory, the proofs underneath the algorithms, etc. So, if you want to learn the theory, I recommend Dasgupta.

You won't go wrong with either; they are both outstanding.

Personally, I think they are better than Cormen. I learned from Cormen, and it's a perfectly fine book, but it can be a bit dense in places and a bit challenging to learn from, so it wouldn't be my first recommendation. Still, it's a reasonable contender and you wouldn't be led astray by it; I just think the others are better.

# Answer
> 3 votes
Cormen et al (CLRS) is aimed towards (undergrad) university students so it may be hard to follow with your current level of mathematics. So, if it has to be one of the two, Skiena may be the more reasonable choice as it is (also) written for professionals.

Other than that, I can recommend Robert Sedgewick's stack. Start with Introduction to Programming in Java which takes an interdisciplinary approach (hence requires little formal knowledge) and move on to Algorithms and An Introduction to the Analysis of Algorithms. Note that the latter *will* require you dig more into mathematics.

If you are willing do read up on necessary mathematics, almost any introductory undergrad textbook (see here for longer lists) should be a good start: pick one you can afford and read the first chapter to see if you like the style. There is no one best book; some work better for some people than others.

Note that these books will give you the university-level computer *science* treatment. If all you want is to be effective in school-level programming tournaments and quickly, you're likely better off with other resources, but I can't help you with that.

---
Tags: algorithms, reference-request, books
---


title: Min-max selection sort

text:
# Question
Title: Min-max selection sort
Is there already modified version of selection sort that works like this pseudocode:

```
a // the array, index starts at 1 (not zero-based)
n = len(a)
for x in 1 to n
  big = x
  small = x
  last = n-x+1
  for y in x+1 to last
    if a[big] < a[y] then big = y
    if a[small] > a[y] then small = y
  if big <> small
    if small <> x then swap(a[small],a[x])
    if big <> last then swap(a[big],a[last])

```

if there is such an algorithm, what is the name of it?

# Answer
> 4 votes
As the wikipedia article on selection sort states, this variant is called cocktail sort.

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


title: Are all Chomsky-Type3 grammars LL(1)?

text:
# Question
Title: Are all Chomsky-Type3 grammars LL(1)?
Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1).

If not, why is it so? Are there maybe ambiguous grammars in the set of the Type 3 grammars?

# Answer
> 3 votes
Chomsky hierarchy is primarily a hierarchy of grammars, not of languages. As stated in Wikipedia:

> The Chomsky hierarchy (occasionally referred to as Chomsky-Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.

Type 3 grammars are characterized by the fact that they have to have only left linear rules (i.e., productions), or only right linear rules, plus possibly an empty rule for the initial non-terminal symbol. For any language, both forms exist.

A rule is left linear iff its right hand side (RHS) is composed of a terminal symbol, possibly preceded by a single non-terminal.

A rule is right linear iff its right hand side (RHS) is composed of a terminal symbol, possibly followed by a single non-terminal.

(There are small variants of these definitions, allowing for a terminal string of any length, instead of a single terminal)

When the language is not finite, some of the rules are necessarily recursive. But a left linear rules that is recursive is necessarily left recursive. Hence the grammar is not LL(1).

Hence some type 3 grammars, even with the strict definition above, are not LL(1).

---
Tags: formal-languages, formal-grammars
---


# Question
Title: difference between multilayer perceptron and linear regression
What is the difference between multilayer perceptron and linear regression classifier. I am trying to learn a model with numerical attributes, and predict a numerical value.

Thanks

# Answer
> 14 votes
If you have a neural network (aka a multilayer perceptron) with only an input and an output layer and with no activation function, that is exactly equal to linear regression. In your case, each attribute corresponds to an input node and your network has one output node, which represents the target value you're trying to predict.

However, most neural networks are more complex. Usually, the input nodes first feed into a layer of hidden units. These hidden units take the sum of their weighted inputs, as the output node did in the simple network, but apply an activation function to them (usually a sigmoid function which compresses the domain $(-\infty, \infty)$ to $(-1, 1)$). The output nodes are each a linear combination of all the nodes in the hidden layer. These days there are even effective methods to train networks with many hidden layer each feeding into the next.

Practically, there are two important differences:

* Linear regression (and the linear network with no hidden layers) have a closed form solution. You can compute the optimal model directly and efficiently. Once you add an activation function, and possibly hidden layers, you cannot compute an optimal model directly anymore, and you're forced to use an *iterative solution*: an algorithm that goes through steps, usually improving the model with each step. There are no guarantees that the process will converge, or that you'll find the best model. It's also a lot slower than the direct solution.
* The flipside is that with a hidden layer and activation function, you have a much more powerful model. You can even show that so long as you have enough nodes in your hidden layer, you can approximate any continuous function with an abritrarily small error. Linear regression and the simple neural network can only model linear functions. You can however use a design matrix (or basis functions, in neural network terminology) to increase the power of linear regression without losing the closed form solution.

## Glossary

* **Neural Network**: A collection of nodes and arrows. Computation flows through the network along the arrows. The value of node $n$ is determined by the nodes which have arrows from them to $n$. Each arrow contains a *weight* which determines the strength of the connection.
* **Activation function**: A node in a neural network works as follows: it takes all the values of all nodes which are connected to it by an arrow, multiplies all these by their respective weights, and then sums them. It then passes this sum through an activation function to ensure that its output stays in the range $(-1, 1)$. Common activations functions are the logistic function and tanh.
* **Hidden layers**: The nodes and arrows in a neural network can be arranged in any way, but the most common arrangement is in layers. This is called a **multilayer perceptron**. It groups the nodes into layers. Each node in layer $i$ takes all nodes in layer $i-1$ as input. The nodes in the first layer are the input nodes and the nodes in the last layer are the output nodes. The rest of the layers are called **hidden layers**.

The following image comes from this tutorial.

---
Tags: algorithms, algorithm-analysis, data-mining
---


# Question
Title: Efficient way to check if a graph node's children were visited during traversal
I have a generic traversal algorithm for graphs:

```
Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
    }
}

```

and I want to make a time-efficient "child head count" for nodes that sets a flag for nodes whenever all their children have been visited:

```
Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        set close flag on parent nodes if last child to be visited
    }
}

```

The best ways that i could think of was to have pointers to "visited" booleans of the node's children and just "and" them up as such:

```
node1 -> [node2(true), node5(false), node7(true)]

node1.all_children_visited() = false

```

Or iterate through the parents whenever I visit the node for the first time:

```
Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        if first visit {
            for each parent {
                increase count
                if count(parent) = number of children {close(parent)}
            }
            if count(this) = number of children {close(this)}
        }
    }
}

```

Is there a way to do this with lower than O(n) complexity?

# Answer
> 2 votes
If you can afford more memory, add a field to each node's data containing a count of already visited children. Assuming that you know the number of children, if you update this field each time you visit a child, you will know when all children have been visited.

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


# Question
Title: Understanding Property Testing with a toy example
I am newbie with this property testing and I am trying to understand it with a few examples. I first dealt with a toy example.

I did not understand the first step of the test in the following slide. Why is the first step $S= 2/\epsilon$?

Could someone please explain me in more detail (i.e. with a concrete example)? I would appreciate with that.

# Answer
> 4 votes
The problem is, given a string of length $n$ over $\\{0,1\\}$, to distinguish the following two cases:

1. The string is entirely 0.
2. The string is $\epsilon$-far from being entirely 0, i.e., has at least an $\epsilon$-fraction of 1s.

The proposed algorithm tests $S = 2/\epsilon$ positions, and returns (1) if all positions were 0. If the original string consisted of 0s then this algorithm always returns (1) correctly, and otherwise it makes a mistake with probability $(1-\epsilon)^S \leq e^{-2}$.

We choose $S = 2/\epsilon$ in the first step so that the error probability is constant, in particular less than $1/3$. If you want a different error probability, you'll choose a different value of $S$.

---
Tags: algorithm-analysis, randomized-algorithms
---


# Question
Title: Closed form solution for a single layer linear perceptron
Let f be a one-layer neural network which is linear (ie. no activation function). Let it have $p$ inputs and $q$ outputs. These are fully connected by weights $W$. We have $n$ inputs $x \in \mathbb{R}^d$ and $n$ outputs $y \in \mathbb{R}^{d'}$. We arrange these (column) vectors into matrices $Y$ and $X$, and the weights into a matrix, so that we can express the computation of the network on the whole dataset as $WX = Y$ (that is, if we could find the perfect $W$). Just to clarify, the network contains no hidden layer, just the input and output layers.

Training the network is a matter of choosing $W$ to minimize $e\_W = \sum\_{i=1}^n||y\_i - Wx\_i||^2$.

It seems to me that this problem should have a closed form solution that can be solved by a linear solver in some way. Unfortunately, my linear algebra is lacking. Is there a closed form solution? If not, where is the difficulty?

# Answer
> 5 votes
Yes, there is a closed form solution.

In the most general terms, $WX = Y$ is a linear equation, so it can be solved as $W = X^{-1}Y$. If $X$ has no inverse, using the pseudo-inverse $X^\dagger = X^T(XX^T)^{-1}$ will give the $W$ that minimizes $\sum\_i||Wx\_i - y\_i||^2$.

For practical computation, it's best to compute the pseudo-inverse from a matrix decomposition, rather than multiplying the matrices explicity. The safest option is the singular value decomposition. The wikipedia article details the procedure.

The principle behind this solution used only basic calculus. Calling the error $E$, we set $\frac{\partial E}{\partial w\_{ij}} = 0$ and solve for $w\_{ij}$. This is detailed in \[1, pages 89–93) and \[2\], both available online.

Alternative phrases for this problem are **multivariate linear regression** and **affine registration**.

\[1\] Neural Networks for Pattern Recognition, Christopher M. Bishop.

\[2\] Fitting affine and orthogonal transformations between two sets of points, Helmuth Späth, 2004

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: If Halting problem is decidable, are all RE languages decidable?
Assume the halting problem was decidable. Is then every recursively enumerable languagerecursive?

# Answer
> 15 votes
While we know for sure that the halting problem is (and always will be) undecidable by a Turing machine, we can take the following approach to investigate your question:

Assume that we have a magical machine that can solve the halting problem. We call this machine an **oracle**. We can now wire this machine into a Turing machine, creating Turing machines that can solve the halting problem.

Unfortunately, the same problem we had with the original Turing machines occurs again: we can enumerate our oracle-enriched Turing machines. We can define the function that computes $T\_i(i)+1$. This function cannot occur in our enumeration, because it differs from all Turing machines. In short, **if we have machines that can solve the halting problem, we get a new halting problem for those machines**.

This principle gives us a hierarchy of uncomputable functions (called the Turing hierarchy). Some functions become computable if we have machines with an oracle for the first halting problem, while others stay incomputable. If we give our machines an oracle for the second level halting problems, more functions become computable, but some functions will always be uncomputable.

And yes, **languages that are only recursively enumerable to regular Turing machines are fully recursive to oracle-enriched Turing machines**. Let's use the following definitions:

* A recursive set is one for which there exists a TM which can answer **yes** if a given element is in the set, and **no** if it isn't.
* A recursively enumerable set is one for which there exists a TM which can answer **yes** if a given element is in the set and compute indefinitely if it isn't.

In the second case, we can create an oracle enriched TM which checks if the non-enriched TM halts. So the enriched TM can give a yes-or-no answer.

Of course, there will be new languages which are recursively enumerable in the oracle-enriched world, but not recursive. In the non-enriched world, these languages were not enumerable in any way.

*NB: In general, the phrase 'oracle' can mean any addition to enrich a Turing machine, not just one to solve the halting problem. If the type of oracle isn't clear from context a phrase like "a Turing machine with an oracle for the halting problem" should be used to avoid confusion.*

# Answer
> 3 votes
This is an impossible situation to occur. It will not become decidable. It was proven by Turing in 1936 to be undecidable. So technically you can say anything will happen if it is decidable since it can never be, and would cause a contradiction if it was.

# Answer
> 2 votes
In classical logic, everything follows from a contradiction. Since we know that the halting problem is not decidable, then if we assume that it is decidable, we reach a contradiction, and so everything follows. So the answer is both TRUE and FALSE.

---
Tags: computability, halting-problem
---


# Question
Title: Computing binomial coefficients and factorials modulo a composite number
Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular (for composite moduli I am interested in the case where the factorization is not necessarily known) I know that for primes and factorials we can apply Wilson's Theorem but I was wondering if there is also a fast method for composite numbers. For binomial coefficients I was thinking of using recursion and the addition rule: $$\binom{n}{x} + \binom{n}{x+1} = \binom{n+1}{x+1}$$ somehow but I'm not sure really how to go about it. Any suggessions? Thanks.

# Answer
> 6 votes
If $p$ is prime and $n = n\_\ell \ldots n\_0$, $x = x\_\ell \ldots x\_0$ in base $p$, then (Lucas' theorem) $$ \binom{n}{x} \equiv \binom{n\_\ell}{x\_\ell} \cdots \binom{n\_0}{x\_0} \pmod{p}. $$

For a product of distinct primes, you can apply the Chinese remainder theorem. So it remains to deal with prime powers. Such a method is described in this paper of Andrew Granville, though it's not as nice as the formula above.

---
Tags: algorithms, combinatorics
---


# Question
Title: Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?
I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths.

An example is if we have vertices 1 to 5. We can see that initially, all of the paths are infinite except for the diagonal entries, i.e.:

```
  1 2 3 4 5
1 0 i i i i
2 i 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

```

where i means "infinite". But if we add an edge (1, 2) then the 1-2nd and 2-1st entries of the table are updated:

```
  1 2 3 4 5
1 0 1 i i i
2 1 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

```

Now, if we add the edge (2, 3), then obviously the 2-3rd and 3-2nd entires are updated, but also are 1-3rd and 3-1st (which has length 2, since the path is 1-\>2-\>3 and 3-\>2-\>1):

```
  1 2 3 4 5
1 0 1 2 i i
2 1 0 1 i i
3 2 1 0 i i
4 i i i 0 i
5 i i i i 0

```

Now, the more edges and vertices we add, the more complex the problem becomes, since we need to update other entries in the matrix if they are connected. The one fact that I know about this kind of graph is that it is symmetric along the diagonal.

I've been looking at this problem for a few hours and I do not think there is a generic algorithm that will solve the problem for a general unweighted, undirected graph. Are there resources on the problem?

# Answer
The paper A New Approach to Dynamic All Pairs Shortest Paths by Camil Demetrescu and Giuseppe F. Italiano gives a solution to the directed version of the problem.

It involves saving two priority queues at each position on the matrix and updating and extracting information from these queues as edges are added. The psuedocode for the algorithm is on page 9 of the link.

For undirected graphs like this one, you could add 2 edges for each edge, one in each direction. This will not affect the time complexity of the algorithm.
> 3 votes

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


# Question
Title: Explanation of Tag, Index, and Offset in Direct Mapping Cache
I'm going through an exercise trying to store address references into a direct mapped cache with 128 blocks and a block size of 32 bytes. The address are 20000, 20004, 20008, and 20016 in base 10.

When I start to store them, I realize that the offset is the only value that changes. All of the examples I find determine hits and misses based on the target and index values, without mention of offset. What is the purpose of the offset? If the tag and index are in the cache, is it a hit regardless of the offset? Or is the offset also looked at?

# Answer
If the cache blocks are not sectored, then if the tag field matches any offset within the block will be a hit. With sectoring a cache block can have multiple valid bits, in which case the tag might match but the valid bit for the section corresponding to the offset might be cleared (indicating that the section is invalid).

In theory a valid bit could be provided for every smallest unit of access (commonly an 8-bit byte), but sectoring is more commonly used to allow an outer level of cache to use a larger block size than L1 caches without forcing all the data associated with a tag to be invalidated when the smaller unit needs to be. For an inclusive cache, this avoids unnecessary back-invalidation of L1 cache. (It would also be possible to include fully independent coherence state, e.g., MESI, rather than just validity. This could be used to avoid unnecessary writebacks, e.g.)

Sectoring can also be used to directly fill the cache and allow early restart; alternatives include using a side (fill) buffer with extra valid bits (similar to a write buffer) and waiting for the entire cache block is loaded before restarting execution.

To confuse matters, Intel uses cache line to indicate the smaller unit that shares a tag with other lines in a sector while some others use cache block/line for the larger unit with the term sector used for the portion that can be individually invalidated.

For the level of complexity for this type of exercise, one can reasonably assume that sectoring is not used, so a tag match would indicate a hit regardless of the offset.
> 2 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Difference between hypervisor and exokernel
An hypervisor (1st type) is a software that creates and run virtual machines, managing guest's operative systems's requests to the hardware.
An exokernel is an operative system kernel, that let's programs access directly to the hardware **or, with the support of specific libraries that implements abstactions, run different types of executables for that architecture**.

Both the two are an abstraction layer between hardware and application software.
Both the two let you run on the same machine different executables/software/operative systems/whatever

So what's the difference between the two?

# Answer
> 7 votes
The thing that runs on top of a hypervisor is one or more full operating systems. A hypervisor *virtualizes* the hardware, so that each operating system is "tricked" into believing that it has an entire machine to itself. The engineering genius that goes into hypervisors is how to provide this virtualization at little or no cost (compared to running one operating system directly on the physical hardware.)

The thing that runs on top of an exokernel is a bunch of user-level processes. The processes each attach to a library (maybe the same library maybe different libraries) that provide various services and policies. The goal of the exokernel is to provide only *protection* (keeping one process from using the resources devoted to a different process,) and leave user-level programs to select the *policies* that were most efficient for them. Exokernel was really a research project whose main output was a series of studies about different kinds of operating system services and the barriers to implementing those services efficiently. Another way to view the Exokernel project was that it was a project to investigate how to make a microkernel that isn't dreadfully inefficient and slow.

One of the big problems with microkernels is that they are constantly "crossing process boundaries" and/or switching back and forth between user mode and kernel mode more frequently than would a monolithic kernel (like Linux.) The cost of switching from user mode to kernel mode or from kernel mode to user mode is surprisingly high (in the 1000s of machine cycles per switch).

It's not clear to me to what degree the Exokernel project succeeded or failed. There are certainly several cases where they came up with surprising new ways to provide resource protection (like their disk model where the operating system manages permissions for disk blocks and the entire file system is managed at user level). They also were able to leverage several of the good ideas from around that time, for example, Carl Waldsburger's Lottery Scheduling techniques. And there were some cases in which capability-based protection turned out to be pretty efficient.

There were other cases where providing policy flexibility dramatically increased the number of kernel boundary crossings and they had to resort to other techniques. For example, in network packet filtering instead of doing the filtering at user level they did it in the kernel, but gave the user program the ability to submit a little program (in a limited (and therefore safe) programming language) that would run in the kernel. Similar ideas in this domain were being investigated around the same time by University of Washington's SPIN operating system project.

---
Tags: terminology, operating-systems, os-kernel
---


# Question
Title: Call by need compared to pass by function
SML uses pass‑by‑value, Haskell uses call‑by‑need. Unless I'm wrong (the purpose of this question), one can do call‑by‑need with SML, passing a function instead of a value; a function to be later evaluated when needed.

Adapting a classical example:

```
(* This will print `0` *)

fun pass_by_function (cond, a1, a2) =
   if cond then a1
   else a2

val e1 = fn () => 1 * 0
val e2 = fn () => 1 div 0

val _ = print (Int.toString (pass_by_function (true, e1, e2) ()))

(* This will fail with a divide error *)

fun pass_by_value (cond, a1, a2) =
   if cond then a1
   else a2

val _ = print (Int.toString (pass_by_value (true, 1 * 0, 1 div 0)))

```

It's a big matter for Haskell to be call‑by‑need. I'm just wondering if there is something else or if it's just, say “syntactic sugar”, compared to the way it needs to be done with SML.

Is this just a different way to write the same or is there a semantic difference I'm not aware of? Passing a function, is it indeed always the same as call‑by‑need? If not, when and how does it differs?

# Answer
> 6 votes
Call-by-need is more than call-by-name. Call-by-name is syntactic sugar for wrapping a closure (thunk) around each argument and then passing the pointer to the closure. Your example shows what call-by-name turns into under the covers.

Call-by-need goes one step further by *memoizing*. If an argument is used twice in a function then the thunk corresponding to that argument is only evaluated once, the result is stored, and then on the second (and after) use of that argument the stored value is returned instead of paying the cost of reevaluating the function.

This only works because Haskell is pure functional. That means that every function call always returns the same result for the same inputs. With a language with *any* mutation you can't make this guarantee, so it is much harder to do call-by-need automatically. SML allows mutation.

---
Tags: functional-programming, semantics
---


title: Video lectures on type systems

text:
# Question
Title: Video lectures on type systems
For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of *Types and Programming Languages* and that's great, but I'd really like to watch someone work through it.

In my school, the course that teaches this is called "Programming Languages," but searching for "video lectures programming languages" turns up lots of stuff about how to learn C++, which I'm not interested in. I couldn't find anything on MIT Open Courseware.

I'd really like video lectures that go through *TAPL*, but I'll settle for anything useful. Are there good resources out there?

# Answer
> 5 votes
If you poke around the Oregon Programming Languages Summer School web site you should find a lot of video lectures on the topic, given by the leaders in the area. For instance, see Robert Harper's "Type Theory Foundations" on the curriculum page.

---
Tags: reference-request, type-theory, education, types-and-programming-languages
---