# Question
Title: Is this an $NP$-complete problem: Product-2-Partition
I want to prove the NP-hardness of some problem **P** in scheduling theory. I was trying with **Partition**, **3-Partition** and **Subset product**, But neither was successful.

Now, I can reduce a problem, say **PRODUCT-2-PARTITION** to P, but I am not sure whether such problem is $NP$-complete or not?

The problem **PRODUCT-2-PARTITION** is as follows:

Given $n$ integers. Can we partition them into $n/2$ subsets, where each subset contains exactly $2$ integers, and the product of the elements of any subset is equal to a given value $B$?

# Answer
> 1 votes
Denote these integers by $x\_1\ge x\_2\ge\cdots\ge x\_n$. We assume these integers are all positive (it is not hard to revise the following algorithm for instances including both positive and negative integers).

In a valid solution, the greatest element must match the smallest element. Otherwise, say $x\_1$ matches $x\_i$ where $x\_i\>x\_n$, and $x\_n$ matches $x\_j$, then $B=x\_1x\_i\>x\_1x\_n\ge x\_jx\_n=B$, a contradiction. Hence a valid solution can only be $\\{x\_1,x\_n\\},\\{x\_2,x\_{n-1}\\},\ldots$ We only need to check whether this partition is valid, i.e. whether $x\_1x\_n=x\_2x\_{n-1}=\cdots=B$.

---
Tags: np-hard, partitions, subset-sum
---


# Question
Title: Robustness of non-context-free proof against trivial manipulation
First, we state here a theorem that is well-known in computability theory:

> $L=\\{xx\mid x\in\Sigma^\*\\}\notin CFL$ for every fixed $|\Sigma|\geq2$

And, the standard proof is using *pumping lemma*. At first sight, we rarely face the language $L$ exactly as defined above in a broader theoretical research. Instead, what might be more frequent is $$L'=\\{\text{some-simple-manipulation}(x)x\mid x\in\Sigma^\*\\}$$ Perhaps, those simple manipulation are necessary for **unambiguous encoding**. For example, symbol doubling, prefix, postfix, etc. Those are quite frequent and unavoidable.

Now, the question is: **Can the above theorem still hold under these simple manipulations**?

**Symbol doubling** (as commented below) is a good starter, if one feels the question too broad.

**Or even worse**, there may be **some simple manipulation** that push $L$ down to CFL again.

# Answer
Note $\left\\{x^{\mathrm{R}}x\mid x\in\Sigma^\*\right\\}$ is context free, where $x^{\mathrm{R}}$ means the reverse of $x$.

> Or even worse, there may be some simple manipulation that push $L$ down to CFL again.

So if you consider reversing as a simple manipulation, the answer is indeed yes.
> 3 votes

---
Tags: complexity-theory, computability, context-free
---


title: In place and Out place sorting meaning?

text:
# Question
Title: In place and Out place sorting meaning?
What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.

# Answer
In place sorting is sorting without using extra memory (mostly swapping elements till getting it right).

**PS** In many cases it's impossible to not use any extra memory, but usually in place sorting indicates to constant extra memory.
> 4 votes

# Answer
An in-place sorting algorithm sorts the elements in place: that is, it needs only $O(1)$ extra space.

An out-of-place sorting algorithm needs extra space to put the elements in as it's sorting them. Usually this means $O(n)$ extra space.
> 1 votes

# Answer
The idea of an in-place algorithm isn't unique to sorting, but sorting is probably the most important case, or at least the most well-known. The idea is about space efficiency - `A sorting algorithm in which the sorted items occupy the same storage as the original ones. These algorithms may use o(n) additional memory for bookkeeping, but at most a constant number of items are kept in auxiliary memory at any time`. This was especially relevant to some devices (don't have enough space for ex. Embedded system like PDA, cellphone etc.)

The idea is to produce an output in the same memory space that contains the input by successively transforming that data (mainly by replacing) until the output is produced. This avoids the need to use twice the storage - one area for the input and an equal-sized area for the output.

A/c to Wikipedia page on in-place algorithms currently claims that an in-place algorithm can only use a constant amount - O(1) - of extra space.

> In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.

However, all algorithms require some additional storage for working variables.

Some In-place sorting algorithms :

* Bubble sort
* Insertion sort
* Selection sort
* Merge sort (modification in implementation)
* Quick-sort
* Heapsort

**References :**
> 1 votes

---
Tags: time-complexity, runtime-analysis, sorting
---


title: Robot swarm, Maximum area coverage

text:
# Question
Title: Robot swarm, Maximum area coverage
I have a swarm of`N` robots to place on a plane area. Each robot would control a sub part of the area (navigating in it). What algorithm could I use to deploy my robots so that they all control a comparable part of the area.

I was looking at Voronoi diagrams but I cannot find how to determine the location of the points.

Sorry if this is not very clear, I am not even sure what I am looking for.

# Answer
> 1 votes
I assume by "comparable part of the area" you mean that they should all scan a region of equal area. Additionally, knowing what kind of plane area you have would be helpful, is it convex, is it concave, is it just a regular polygon? If you know this then there are easier ways to do it. So assuming you want for the worst case, a concave polygon, the best solution that I know of is this. This page has a detailed explanation of the algorithm and there's even some comments with implementations.

---
Tags: computational-geometry, voronoi-diagrams, robotics
---


# Question
Title: All the possible inputs for a given AVL tree
Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?

# Answer
AVL trees are binary search trees with additional balancing restrictions. For any binary search tree the root is the first node that should be in the input. After the root all smaller items go left, and all larger items go right. As long as we do not change the relative order of the items that go left, we obtain the same left subtree, and similarly for the right subtree. We can however swap to consecutive input items if they do not belong to the same subtree.

We can find *any* input sequence using this observation recursively. The following non-deterministic algorithm would work, its datastucture is a list of trees (subtrees of the original tree).

Start with the original tree. While any trees left, choose one of the trees, remove its root, and replace the original tree by its subtrees.

The order in which the nodes are removed is a possible input sequence. Extra details: The algorithm is related to the algorithm for finding a linear order matching a given partial order: topological sorting. The order is *not* the order that defines the AVL tree, instead it is the tree order itself.
> 0 votes

---
Tags: data-structures, time-complexity, balanced-search-trees, binary-search-trees
---


# Question
Title: DFA for words with $a$s not a multiple of 3 and at least one $c$
Consider this language: $$L = \\{w \in \\{a,c\\}^\* \mid 3\nmid\\#a(w)\land\\#c(w)\>0\\}$$.

Here is an automaton for the first part of language, but I do not know how to devise and attach the second part of the condition $\\#c(w) \> 0$. Because $C$ can come in any state.

# Answer
> 1 votes
The product construction is a way of taking two DFAs for languages $L\_1,L\_2$, and constructing a new DFA for the language $L\_1 \cup L\_2$ or $L\_1 \cap L\_2$. In your case, $L\_1$ consists of all words in which the number of $a$s is not a multiple of 3, and $L\_2$ consists of all words containing at least one $c$. You have already constructed a DFA for $L\_1$. Construct one for $L\_2$, and use the product construction to construct one for $L\_1 \cap L\_2$.

# Answer
> 0 votes
You obviously need six states: Three states for the number of a's modulo 3, and for each of the three states whether a c was received or not.

Let's call these states a0, a1, a2, a0c, a1c, a2c. You obviously start in state a0. Getting a c leaves you in state a0c, a1c or a2c, or moves you from state a0, a1, a2 to a0c, a1c, a2c. Getting an a will move you from a0 -\> a1 -\> a2 -\> a0 or a0c -\> a1c -\> a2c -\> a0c.

a1c and a2c are success states.

---
Tags: finite-automata
---


# Question
Title: Is the complement of a semidecidable (r.e.) language always a semidecidable (r.e.) language?
Is the complement of every semi-decidable language a semi-decidable language?

# Answer
> 2 votes
No. A language $L$ and its complement $\bar L$ are semi-decidable if and only if $L$ is decidable (see here).

For example, the language containing all programs that terminate is semi-decidable, as you can run any program to see if it halts. Its complement on the other hand is not semi decidable, as you cannot have a routine that determines, if a program will run forever or not.

---
Tags: turing-machines
---


# Question
Title: Algorithm to organize a tournament where the team componentes change each round
So, I was tasked with creating an app that generates the schedule of a *doubles* tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of the players. The trick is every team should change in each round so that not only everyone played against everyone but the teams are not repeated.

I've tried implementing it using greedy search with backtracking, but it just takes too long to find a valid solution, so what I'm asking for is sugerences of an algorithm more efficient that I can use to solve this problem. This are the especifics of the problem:

* There is a multiple of 4 number 'n' of players.
* There is at least n/4 fields to play, so that in each round all players have a match.
* No player can play twice with the same partner, so in each round the teams must change.
* No player can play twice against the same opponent. At the end of the tournament, each player must have played against the rest.

The algorithm must search the ideal combination of matchs so it meets the requeriments above.

Any ideas? Thank you in advance.

EDIT 2: It's not possible for 4 players.

**ROUND 1**

* Player 1 & Player 2 vs Player 3 & Player 4

So far so good.

**ROUND 2**

* Player 1 & Player 3 vs Player 2 & Player 4

Player 1 already played against Player 4, not a valid solution. The other possibility:

**ROUND 2'**

* Player 1 & Player 4 vs Player 2 & Player 3

Player 1 already played against Player 3, not a valid solution either.

EDIT: It is double tennis, sorry for the misunderstanding. Each player must have played *against* the rest, but it's not mandatory that each player ended up playing *with* the rest. Question edited for clarity.

# Answer
> 1 votes
Sorry, but there is no solution. (Assuming that all games are 2 vs 2.)

How many matches does each player play?

* They play *with* each other player exactly once, one such player per match, for a total of $n-1$ matches.
* They play *against* each other player exactly once, two such players per match, for a total of $\frac{n-1}{2}$ matches.

This implies $n-1=\frac{n-1}{2}$ and thus $n=1$. But you said $n$ is even. And besides, a single-player tournament would not be interesting.

\[EDIT\]

The question was now changed to omit the requirement that every other player is a partner at least once. However, it is still not possible.

How many rounds should there be? For every player there are $n-1$ potential opponents. In every round there are $2$ opponents without repetition. Hence the number of rounds is $\frac{n-1}2$. This is not an integer number, because $n$ is even.

---
Tags: combinatorics, greedy-algorithms, search-problem, algorithm-design, backtracking
---


# Question
Title: Decidability of $E_{TM}$ and $A_{TM}$ for "erasing" Turing machines
Why is the $A\_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization argument not work:

> Assume $A\_{ETM}$ is decidable, and $R$ decides $A\_{ETM}$. Then, $R$ accepts $\langle M, w \rangle$ when ETM $M$ accepts $w$. **Let $D$ be an ETM that accepts exactly when $M$ does not accept $w$.** Then, $D$ rejects $\langle D \rangle$ when $D$ accepts $\langle D \rangle$, a contradiction.

Why does this not work?

Alternatively, if $A\_{ETM}$ is decidable, why is $E\_{ETM}$ undecidable? The conventional contradiction argument would not work in that case, and I don't know how to reduce it any other way.

Thanks in advance!

# Answer
> 1 votes
An ETM (Erasing Turing machine) can be safely simulated due to its erasing-only nature.

It can only pass the right-end of the input to a **finite limit** or else would *plunge off to infinity*. Adding this to the input itself, we can conclude that the languages accepted by an ETM must be context-sensitive.

So, an ETM can only accept some context-sensitive language. As a result, $A\_{ETM}$ is decidable.

Where is the source that says $E\_{ETM}$ is undecidable?

---
Tags: turing-machines, undecidability
---


# Question
Title: Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?
In lamport's paper, he define global local timestamp, which is composed of process id and local lamport timestamp.

This timestamp is used to order all the events in a distributed system.

The rule to compare two events is following.

## My Question

Imagine we have two events, one happens in process 1 (P1), with local timestamp 9, another event happens in process 2 (P1), with identical timestamp 9.

Based on lamport's rule, the first one is earlier than second one.

C1(9) =\> c2(9)

But why?

From my understanding, it does't make sense. An event is treated earlier just because it is born in a process which has smaller pid?

## Reference

1. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”

# Answer
> 3 votes
No, "it doesn't make sense". **You are correct in the sense that that choice is not a logical consequence of any requirements and known truths**. It could be considered as arbitrarily selected.

Well, we do not need to make any sense when we are forced to decide which one of two global timestamps, $(T\_i,i)$ and $(T\_j,j)$ where $T\_i=T\_j$, is earlier than the other one, as long as our choices are consistent, so that we will be able to arrive at a total ordering that respects the local ticks. There are indeed many different ways to decide that can lead to many different total orderings.

What does it mean by "choice being consistent"? Here is a simple example. Suppose we have three global timestamps, (1,5), (1,2), (1,4). It is consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,5) $\prec$ (1,4). However, it is not consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,4) $\prec$ (1,5). Intuitively, if (1,5) precedes (1,2) and (1,2) precedes (1,4), then (1,5) must precedes (1,4). That is, the transitivity of $\prec$ must be respected; otherwise, $\prec$ is not a partial ordering any more. The transitivity of temporal ordering of events is the essence of time.

Among many schemes to decide which global timestamp is earlier in a pair of two global timestamps with the same local timestamp, the easiest and most natural one is the one specified in the paper. That is, $(T\_i,i) \prec (T\_j,j)$ where $T\_i=T\_j$ and $i\<j$. Since we have assumed that the second coordinate, the process number is globally unique, this scheme is complete in the sense that all those kind of pairs are ordered and this scheme is apparently consistent. Moreover, whenever the process numbers do have any inkling to the actual order of physical time as what happens in many situations, smaller process number usually indicates earlier in physical time. So, after all, **that decision in the paper makes a lot of sense**.

---
Tags: algorithms, distributed-systems, synchronization, clocks
---


# Question
Title: Lamport logical clock: what does partial mean in the concept of `Partial ordering`?
In lamport's paper\[1\], he define two concept `The partial ordering` and `The totally ordering`.

1. What does partial mean in `partial ordering`?

assumption: this ordering only handle two cases, one is to order events happening in single process, second is communication events between two process. It can't handle concurrent events, so it's named as `Partial ordering`.

Is my assumption correct?
2. What does totally ordering mean?

Does that mean it can handle all the events in a distributed system?

## Reference

Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”

# Answer
The "partial ordering" in the papar means partial order as in standard mathemtics theory. To be more rigorous, the "partial ordering" in that paper, also called "irreflexive parital ordering" in that paper, means strict partial order. (Yes, "strict" means "irreflexive".) (Yes, "order" can be used interchangeably with "ordering" sometimes. I prefer "order" in a mathematics environment and "ordering" in non-mathematics environment, since "order" is such a common English word.)

Informally, that "partial" means it is possible a "\<" relation thereof is missing for some pairs of elements. Here is an example. Let $S=\\{a,b,c\\}$. We can define a relation $\<\_1$ on $S$ by $a\<\_1 b$ and $a\<\_1 c$. That is all. Note we did not say anything about the relationship between $a$ and $c$. In fact, we have specified that there should not be a relationship between $a$ and $c$. These two elements are incomparable. That is why we say $\<\_1$ is a "partial" relation on $S$.

In that paper, for example, $p\_3$ and $q\_3$ are two incomparable events. We cannot say $p\_3\to q\_3$ nor $q\_3\to p\_3$. The order relationship between $p\_3$ and $q\_3$ is missing. It is not defined. That is why it is referred as a "partial" ordering. "It can't handle concurrent events, so it's named as Partial ordering." That understanding is pretty good. However, I would phrase it as "It does not order concurrent events, ...". I mean, it does handle concurrent events, resulting in that concurrent events should be treated as incomparable.

In contrast, "a total ordering" or, a total order is a partial ordering under which every pair of elements are comparable. If you find these two math terms sound contradictory, think of them as square are also rectangles. In fact, the "total ordering" in the paper is the strict total order. Yes, you can understand that "total ordering" means "it can handle all the events in a distributed system", or "it can order every pair of events in a distributed system (as defined in the paper)".

---

You may find lots of terminologies in the theory of partially ordered set and order theory. It looks like overwhelming initially. However, most of the concepts are very easy to understand intuitively.

In your case, **all you need to understand is how is $\to$ defined on the set of events of a system and that a total ordering is such a special $\to$ that for any two events $e\_1$ and $e\_2$, either $e\_1\to e\_2$ or $e\_2\to e\_1$ must hold**. You could ignore all those formal concepts in math theory even though they might help understand more things later more clearly.

As mentioned by Gokul, here is a pretty good explanation about Lamports's logical clocks.
> 5 votes

---
Tags: algorithms, distributed-systems, synchronization, clocks
---


# Question
Title: When is the concatenation of a language $L$ with $\Sigma^*$ regular?
I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\\{0^n1^n|n\geq 0\\}$ and $\Sigma^\*$ was regular (over the alphabet $\Sigma = \\{0,1\\}$). Another provided a counterexample by the concatenation of $\\{a^{n^2}b|n\geq 0\\}$ with $\Sigma^\*$, which is irregular (over the alphabet $\Sigma = \\{a,b\\}$). Could someone provide clarification as to why some concatenations with $\Sigma^\*$ are regular while others aren't? Both cases concatenate an irregular language unrecognisable by a DFA to one that is, and I don't understand how this produces a language that is recognisable.

Links to source questions: https://math.stackexchange.com/questions/649335/are-languages-regular-if-their-concatenation-is-regular Why is $\Sigma^\*$ concatenated with some language regular?

# Answer
> 1 votes
In the first case, $n$ can be 0, and the concatenation will produce $\Sigma^\*$. So any other value of $n$ is irrelevant; no other strings could be added. If the restriction were $n\>1$, then the concatenation would not be regular.

---
Tags: formal-languages, automata
---


# Question
Title: Is this algorithm for partial ordering of sets complete and sound?
I need to build a partial order tree of sets for analysis.

Where the order is defined as `A <= B <=> for all x in A, y in B, x <= y`.

I realized that if I pre-sort all the maximal and minimal elements of the sets, like this:

```
// A [1,3]
// B [2,4]
// C [3,5]
// D [6,7]
// E [8,9]
// F [10,11]
const input = [['A', 1], ['B', 2], ['C', 3], ['A', 3], ['B', 4], ['C', 5], ['D', 6], ['D', 7], ['E', 8], ['E', 9], ['F', 10], ['F', 11]]

```

I can achieve it in `O(n)`, with the following algorithm:

```
let i = 0
const closed = []
const opened = {}
const lists = []
for (const item of input.reverse()) {
  if (!opened[item[0]]) { // Opening the range.
    // May need to create a new list.
    if (i <= closed.length) {
      lists.push([[i - 1, closed.length], []])
      i = closed.length + 1
    }

    // Add to list.
    lists[lists.length - 1][1].push(item[0])
    opened[item[0]] = true
  } else // Closing the range.
    closed.push(item[0])
}

```

This is javascript and you can pretty print the result like so:

```
console.log(lists.map(l => `${closed.slice(l[0][0],l[0][1])}:${l[1]}`).join('\n'))
// :F
// F:E
// E:D
// D:C,B,A

```

Are there orders for which this might not work?

# Answer
> 1 votes
It is pleasing to see such a nice algorithm.

Your algorithm is correct for all inputs except possibly for two corner cases.

* For example, if we have `input = [['A', 1], ['B', 2], ['A', 2], ['B', 3]]`, then your algorithm will not produce the expected `A<=B`.
* For example, if we have `input = [['A', 1], ['B', 1], ['A', 1], ['B',1]` or `input = [['A', 1], ['A', 1], ['B', 1], ['B',1]`, then your algorithm will not produce the expected `A<=B` and `B<=A`.

The issue is not in your algorithm proper but how you define your input and expected result and how you specify the way to sort all endpoints of the intervals. Here is a sample solution.

* Require that all input intervals are non-degenerate and different.
* When sorting, break ties with the other endpoint. That is, given A=\[1,2\] and B=\[2,3\], when \['A', 2\] and \['B',2\] are compared, we must put the former before the latter since 1 \< 3.

---

By the way, you can just use `const item of input` instead of `const item of input.reverse()`. Also, you may use `${closed.slice(l[0][0],l[0][1])} <= ${l[1]}` instead of `${closed.slice(l[0][0],l[0][1])}:${l[1]}` since you use "\<=" to define the relation. You should get a slightly prettier output.

---

Last but not least, Code View Stack Exchange should probably be a better place to post this kind of question.

---
Tags: algorithms, sorting, partial-order
---


title: Convert grammar to Greibach form

text:
# Question
Title: Convert grammar to Greibach form
The grammar is
$S \rightarrow AA|a$
$A \rightarrow SA|ab$
The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach form. I tried to substitute one rule in another but it didn't help. Any hints would be very helpful.

# Answer
> 0 votes
A context-free grammar can be simulated by a PDA with a single state (assuming acceptance by empty stack, for final state acceptance we need two states). Wikipedia suggests two solutions.

**Any** context-free grammar can be simulated using a expand-match method. The PDA nondeterministically kind of generates a right-most derivation, and whenever a terminal is generated, it should be read from the tape.

* expand. For production $A\to\alpha$ have instruction $(1,\varepsilon,1,A,\alpha)$
* match. For any terminal $a$ have instruction $(1,a,1,a,\varepsilon)$

The other (more direct) method is given for grammars in Greibach normal form, but will also work for Chomsky normal form. For any production $A\to a\alpha$, where $a$ is terminal **or** $\epsilon$, and $\alpha$ is a nonterminal string introduce $(1,a,1,A,\alpha)$.

Your example can of course be handled with the first method. For the second one, only the production $A\to ab$ cannot be directly dealt with. Either split that production, or use extra states in the PDA.

---
Tags: formal-grammars, pushdown-automata, normal-forms
---


# Question
Title: Why do we need to run the bellman-ford algorithm for n-1 times?
I'm a little confused about the concept of the Bellman-Ford(BF) algorithm to compute the shortest path in a general graph with negative weights knowing that there are no negative cycles present. I understand why Dikjstra doesn't work for a graph with negative weights. So in the Bellman-Ford algorithm we decide to update all nodes and their neighbors even though they might be visited before. My confusion can be summarized in a couple of questions:

1. Why running the BF algorithm once won't make sure that all nodes' distances have the minimum distance from the source?
2. Why do we have to run BF for N-1 (N: number of nodes) times to make sure all the nodes have the minimum distance from the source? Is it sort of because there are negative weights? How negative weights complicate things?

# Answer
> 9 votes
Answering your first question is simple. Try out a few graphs and see for yourself why it doesn't work. As to your second question, $n-1$ is the maximal length of a shortest path in the graph. After $k$ iterations of the Bellman–Ford algorithm, you know the minimum distance between any two vertices, when restricted to paths of length at most $k$. This is why you need $n-1$ iterations. Negative weights have absolutely nothing to do with it.

For a more sophisticated answer, consult the recent paper of Jukna and Schnitger, On the optimality of Bellman–Ford shortest path algorithm. They show that among the class of Bellman–Ford-like algorithms, the Bellman–Ford algorithm is optimal.

# Answer
> 4 votes
The longest possible shortest path from source s to destination $v\_k$ can have $|V|-1$ "stops". According to *Lemma 24.15 Path-relaxation property* in CLRS, after each "relaxation" step, you get $v\_i=\delta(s, v\_i)$ and this value remains unchanged ever since. So after $|V|-1$ times we must finish finding all results for a single-source shortest path problem. You make easily find a counterexample to say why loop for fewer than$|V|-1$ will fail to find all shortest paths.

---
Tags: algorithms, shortest-path, graph-algorithms
---


title: Which Peterson’s Solution is right?

text:
# Question
Title: Which Peterson’s Solution is right?
I have seen two different Peterson’s Solution to mutual exclusion, one is from *Modern Operating Systems*:

```
#define FALSE 0
#define TRUE 1
#define N 2

int turn;
int interested[N];

void enter_region(int process)
{
    int other;
    other = 1 - process;
    intersted[process] = TRUE;
    turn = process;
    while(turn == process && interested[other] == TRUE);
}

void leave_region(int process)
{
    interested[process] = FALSE;
}

```

The other is from *Operating System Concepts*:

```
while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ;
        /* critical section */
    flag[i] = false;
        /*remainder section */
}

```

But they are different. The first one set `turn` to itself, while the second one set `turn` to the other. The following `while` condition also has the same difference. After googling around, I think the second one is right, but not sure.

# Answer
> 2 votes
**Both versions of Peterson's algorithm are correct.**

The version at *Operating System Concepts* (OSC) is slightly better if you would believe the natural meaning of `turn` as whose turn it is to enter the critical section or who has the priority to enter the critical section. The version at *Modern Operating Systems* (MOS) is slightly better for its better variable name `interested`.

Let us verify that the two versions are equivalent to each other. Let us **rename the variable `turn` in the version at MOS to `wait`**, (which should be a better name for that variable), meaning who should be waiting or who should yield to the other process regarding entering the critical section. Now you can see two versions are similar. The version at MOS say that the current process intends to wait behind the other process when it sets the `wait` to be itself and checks its value later. The version at OSC says the other process should have the turn to enter the critical section when it sets the `turn` variable to the other process and checks its value later. Now you can feel that those two versions seems doing the same thing.

To go a step further, after we have renamed `turn` to `wait` in the version at MOS, let us further imagine that the way the computer for MOS implements `wait=0` is actually set some memory location to 1 and will name that location as `turn'`. It will implements `wait=1` as setting that location `turn'` to 0. Also when it checks `wait == 0` it actually checks `turn' == 1`. When it checks `wait == 1`, it actually checks `turn' == 0`. Other than this particular implementation for the `wait` variable, this computer is completely the same as another computer that runs the version at OSC. Now if you skip the intermediate syntactic step that set or check `wait` and view `turn'` at the computer for MOS as equivalent to `turn` at the computer for OSC, (and rename several other variables), you can see they are actually executing the same code.

(In short, if you **imagine that, only for the original `wait` variable at MOS version, 1 means 0 and 1 means 0**, then you can see both version are executing same kind of code.)

Another way to see the equivalence of the two versions is to notice, as the questioner has noted, each version sets some variable to some value and then checks whether that variable is still that value. This variable is only used in these two places. There are only two values for that variable. It does not matter what is name of the variable or what are those two values. **As long as the code sets some variable to some value and then checks whether that variable is still that value, that part of code has same behavior.** Of course, this reasoning here is somewhat shady. It can certainly to help your understanding, though.

---

Every time we refer to Peterson's algorithm, it is obligatory to praise what a simple and great distributed algorithm it is. How deceptively simple it is and how smart it deals with the intricacy of concurrency!

For a much more complete understanding of the Peterson's algorithm and why it is indeed correct, please check The assertional versus Tarskian methods.

---
Tags: operating-systems, concurrency
---


# Question
Title: Floating point number fractions excercise
During my preparation for an exam, I've come across an exercise that was focused on precision calculation with floating point numbers. It goes like this:

> Consider the expression : $$\frac{1}{1-x}-\frac{1}{1+x}, x\neq \pm1$$ For what range of values $x$ is it difficult to compute the expression accurately in foating-point arithmetic? Give a re-arrangement of the terms such that, for the range of values from part (a), the computation is more accurate in foating-point arithmetic.

I have some basics covered on floating point number systems, so I've tried to set $\pm x=0.9999...$, with a different number of decimal digits. The calculations are indeed more and more imprecise, however I don't know if this is the only problematic 'range'. Also, I have no idea how to transform this expression to be more accurate. I have tried $\frac{2x}{1-x^{2}}$ and $e^{\ln{2x}-\ln(1-x^{2})}$, but the results were pretty much the same.

Thanks for help!

# Answer
Actually, floating point arithmetic according to the IEEE 754 standard will calculate 1-x *exactly*, without any rounding error, if 0.5 ≤ x ≤ 2.0. So for x close to 1, 1-x is calculated exactly, 1 / (1-x) is calculated accurately, and 1 / (1 + x) and the sum will be calculated accurately as well.

What you are likely observing is the rounding error when 0.999999 for example is converted to a floating point number. x will not be equal to 0.999999, but a bit off. And the function itself as a function of real numbers is very sensitive to changes in the argument. That also explains why re-arranging the function can't help, because the function is sensitive to the arguments, and the arguments are not what you think.

The same applies for x close to -1, since f(x) = f(-x).

You will actually have a problem if x is close to 0. 1 / (1-x) and 1 / (1+x) can both be calculated with a very small absolute error, the difference is calculated exactly because both have about the same size, but because the result is close to zero, the small absolute errors turn into a rather large relative error.

When x is close to zero, 1 / (1 - x) = 1 + x + x^2 + x^3 ..., and a / (1 + x) = 1 - x + x^2 - x^3 ..., the mathematical difference is 2x + 2x^3 + 2x^5 ... ≈ 2x.

Let u be the value of the last bit in a number 1 ≤ x \< 2, then IEEE arithmetic has rounding errors up to u/2. 1 / (1 - u) ≥ 1 is calculated with an error up to u/2, 1 / (1 + u) has an error up to u/4. If you pick x^2 slightly larger than u/4, then 1 / (1 - x) is rounded to 1+x, 1 / (1 + x) is rounded to 1 - x + u/4, and the difference that is calculated is 2x - u/4, instead of 2x + x^3 + 2x^5 ..., so the absolute error is \> u/4, and the relative error about $(u/4)^{1/2}$.

You can fix this easily by **subtracting 1 from both sides**, giving $x / (1 - x) + x / (1 + x)$.
> 1 votes

---
Tags: floating-point
---


# Question
Title: Modify max value multiple times of a list
I have two lists say $A$ and $B$, each consisting of n positive integers. I make a list $C$ such that each element of $C$ i.e., $C\_i=A\_iB\_i$ for each element $A\_i \in A$ and $B\_i \in B$.

Now I have to update the value of the maximum element of $C$ say $C\_j$ by decreasing $B\_j$ such that $B\_j \geq 0$ and $C\_j$'s updated value should be less than the second maximum element of $C$.

The above operation have to be applied $m$-times.

The approach I used was:

* Build a Max Heap of list C
* repeat $m$-times
    + update the value of max element of heap according to the given condition
    + Apply *Max-Heapify*

The above approach worked fine. So my question is "Is there any way to do the above task in a faster way than my approach?"

# Answer
> 1 votes
One solution is changing the underlying data structure;

* In the binary heaps, Decrease\_Key is $\mathcal{O}(\log n)$ cost in the worst case. If you use Fibonacci heaps, Decrease\_Key is $\mathcal{\Theta(1)}$ in amortized time. With the binary heaps, you will have $\mathcal{O}(m \log n)$ whereas in Fibonacci heaps you will have $\mathcal{\theta(m)}$ in amortized time.

---

**note** : Fibonacci Heaps are theoretically better than Binary Heaps. But their the constant factors hidden are very high.

---

Introduction To Algorithms 3rd. Ed. Cormen et. al. at section 19.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Sorting algorithms which accept a random comparator
Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the algorithm is a sorted list/array.

I am wondering though which sort algorithms would actually *work* with a comparator that is not an order relation (in particular one which returns a random result on each comparison). By "work" I mean here that they continue return a permutation of their input and run at their typically quoted time complexity (as opposed to degrading to the worst case scenario always, or going into an infinite loop, or missing elements). The ordering of the results would be undefined however. Even better, the resulting ordering would be a uniform distribution when the comparator is a coin flip.

From my rough mental calculation it appears that a merge sort would be fine with this and maintain the same runtime cost and produce a fair random ordering. I think that something like a quick sort would however degenerate, possibly not finish, and not be fair.

What other sorting algorithms (other than merge sort) would work as described with a random comparator?

---

1. For reference, a comparator is an order relation if it is a proper function (deterministic) and satisfies the axioms of an order relation:

* it is deterministic: `compare(a,b)` for a particular `a` and `b` always returns the same result.
    * it is transitive: `compare(a,b) and compare(b,c) implies compare( a,c )`
    * it is antisymmetric `compare(a,b) and compare(b,a) implies a == b`

(Assume that all input elements are distinct, so reflexivity is not an issue.)

A random comparator violates all of these rules. There are however comparators that are not order relations yet are not random (for example they might violate perhaps only one rule, and only for particular elements in the set).

# Answer
So basically, you want to know if there is any sorting algorithm which wouldn't degrade from its average case if given a compare function similar to:

```
int Compare(object a, object b) { return Random.Next(-1,1); }

```

... where Random.Next() is some method that will produce a randomly-generated integer between a specified inclusive lower and upper bound.

The answer is actually that most basic sorting algorithms will perform according to their average case, because they obey at least one of the following two conditions:

1. A comparison between two unique elements is never made twice in the sort, and/or
2. In each iteration of the sort, the correct position of at least one element is determined and so that element is never compared again.

For instance, SelectionSort iterates through the sub-list of unsorted elements, finds the "least" and/or "greatest" element (by comparing each one to the greatest so far), places it in its correct position and repeats. As a result, even with a non-deterministic comparator, at the end of every iteration the algorithm will have found a value that it thinks is least or greatest, swaps it with the element in the position it is trying to determine, and never considers that element again, thus it obeys Condition 2. However, an A and B can be compared multiple times during this process (as the most extreme example, consider several passes of SelectionSort on an array that's sorted in reverse order) so it violates Condition 1.

MergeSort obeys Condition 1 but not 2; as sub-arrays are merged, elements in the same sub-array (on the left or right side) are not compared to each other because it has already been determined that the elements on that side of the array are in order among themselves; the algorithm only compares the least unmerged element of each subarray to the other to determine which is lesser and should go next in the merged list. This means that any two unique objects A and B will be compared to each other a maximum of one time, but any given element's "final" index in the full collection is not known until the algorithm is complete.

InsertionSort obeys only Condition 1 as well even though its overall strategy and complexity looks more like SelectionSort. Each unsorted element is compared with sorted elements, greatest-first, until one is found that is less than the element under inspection. the element is inserted at that point, and then the next element is considered. The result is that the relative order of any A and B is determined by one comparison, and further comparisons between that A and B are never performed, but the final position of any element cannot be known until all elements are considered.

QuickSort obeys *both* Conditions. At each level, a pivot is chosen and arranged such that the "left" side contains elements less than the pivot and the "right" side contains elements greater than the pivot. The result of that level is QuickSort(left) + pivot + QuickSort(right) which basically means the position of the pivot element is known (one index greater than the length of the left side), the pivot is never compared to any other element after it has been chosen as a pivot (it may have been compared with previous pivot elements, but those elements are also known and are not included in any subarrays), AND any A and B that end up on opposite sides of the pivot are never compared. In most implementations of pure QuickSort, the base case is one element, at which point its current index is its final index and no further comparisons are made.

The only comparative sort I can think of that wouldn't obey either condition is a non-optimized BubbleSort. If the sort does not accept that the X greatest elements are in their proper place after running X passes, and/or uses a "double-check" pass to verify the list is sorted, the sort will only be considered "done" when the random comparator has returned -1 or 0 for every two adjacent elements in the list during a pass and thus no swaps were performed (an event which, if truly random, would occur with probability $(2/3)^{N-1}$; for a relatively small list of 25 elements, that's a one in 2000 chance, while for 100 elements the probability is 3.7\*10-18). As the maximum absolute value of the result of the comparator increases, the probability for any one comparison to return negative or zero decreases towards .5, making the chance to end the algorithm that much less likely (the chance of 99 coin flips all landing heads, which is basically what this boils down to, is 1 in 1.2\*1030)

**EDIT A LONG TIME LATER:** There are a few "sorts" designed specifically as examples of what not to do which incorporate a random comparator; perhaps the most famous is BogoSort. "Given a list, if the list is not in order, shuffle the list and check again". Theoretically it will *eventually* hit on the right permutation of values, just like the "non-optimized BubbleSort" above, but the average case is factorial-time (N!/2), and because of the birthday problem (after enough random permutations you become more likely to encounter duplicate permutations than unique ones) there is a nonzero possibility of the algorithm never completing to officially the algorithm is time-unbounded.
> 13 votes

# Answer
Any algorithm that compares the same two elements twice is not a very clever algorithm, and in particular such an algorithm would perform less well than the most common sorting algorithms (merge-sort, quicksort, bubble-sort, insertion-sort). Any algorithm that compares pairs of elements at most once has the same (average) runtime cost regardless of the behavior of the compare function, *if greater-than and lesser-than are equally likely results*. Otherwise, you can at least guarantee that the sorting algorithm does no worse than the worst-case running time, which is less than $O(n^2)$ for any decent sorting algorithm.

I believe that a more interesting question is how *well* such an algorithm would perform if the compare function only gave the right answer in, say, 90% of cases on average. By how well it would perform i mean to answer the question: "what is, on average, the number of misplaced items when sorting a list of size $n$ by this algorithm?"

---

Edit: The problem is more interesting as I first thought, so here's a further comment:

Suppose that your $compare$ function is *fair*, that is $compare(x,y)=true$ with probability $1/2$ and $false$ with probability also $1/2$. Recall the insertion sort (functional style) algorithm:

```
insert x [] = [x]
insert x y:ys = if x < y then x:y:ys
                else y:insert x ys

sort_aux l e = match l with
                 [] -> e
                 x:xs -> sort_aux xs (insert x ys)

sort l = sort_aux l []

```

The average running time of this algorithm is then $\sum\_{k=1}^{n} f(k)$ where $n$ is the length of $l$ and $f(k)$ is the average running time of $insert$ on a list of length $k$, that is if we count only applications of $:$ as having cost (if we count destructions as well, the formula is similar).

Now for $compare$ as described above, this is quite small: the mean number of steps performed by the insertion is given by:

$$ \sum\_{i=1}^{k} i 2^{-i} \leq \sum\_{i=1}^{\infty}i 2^{-i} = 2$$

This gives an average running time of $O(2n)$ for insertion sort, which is significantly better than the $O(n^2)$ given by a "decent" comparison function.

It would be fun to work out the average running times for the different other algorithms given this uniform compare function.
> 10 votes

# Answer
Mergesort with a fair random comparator is not fair. I don't have a proof, but I have VERY strong empirical evidence. (Fair means uniformly distributed.)

```
module Main where

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import System.Random (randomIO)

--------------------------------------------------------------------------------

main :: IO ()
main = do
  let xs = [0..9]
  xss <- replicateM 100000 (msortRand xs)
  print $ countFrequencies xss

msortRand :: [a] -> IO [a]
msortRand = msort (\_ _ -> randomIO)

countFrequencies :: (Ord a) => [[a]] -> [Map a Int]
countFrequencies [] = []
countFrequencies xss = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty ys : countFrequencies wss
  where
    ys = map head xss
    zss = map tail xss
    wss = if head zss == []
      then []
      else zss

--------------------------------------------------------------------------------

msort :: (Monad m) => (a -> a -> m Bool) -> [a] -> m [a]
msort (<) [] = return []
msort (<) [x] = return [x]
msort (<) xs = do
  ys' <- msort (<) ys
  zs' <- msort (<) zs
  merge (<) ys' zs'
  where
    (ys, zs) = split xs

merge :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
merge (<) [] ys = return ys
merge (<) xs [] = return xs
merge (<) (x:xs) (y:ys) = do
  bool <- x < y
  if bool
    then liftM (x:) $ merge (<) xs (y:ys)
        else liftM (y:) $ merge (<) (x:xs) ys

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = split zs

```
> 2 votes

# Answer
A very much related question is answered in **All Sorts of Permutations (Functional Pearl)** by Christiansen, Danilenko and Dylus. They run a sorting algorithm in the list monad, which essentially simulates non-determinism, returning all permutations of a given input list. The interesting property is that each permutation is returned exactly once.

Quoting from the abstract:

> ...
>
> In this paper we look at the combination of non-determinism and sorting in a different light: given a sorting function, we apply it to a non-deterministic predicate to gain a function that enumerates permutations of the input list. We get to the bottom of necessary properties of the sorting algorithms and predicates in play as well as discuss variations of the modelled non-determinism.
>
> On top of that, we formulate and prove a theorem stating that no matter which sorting function we use, the corresponding permutation function enumerates all permutations of the input list. We use free theorems, which are derived from the type of a function alone, to prove the statement.
> 0 votes

---
Tags: algorithms, randomized-algorithms, sorting
---


# Question
Title: Is there a reason to NOT wrap preprocessor macros in parens?
I'm writing a design document for a macro expansion language that is specifically intended for arithmetic operations on integers. I've already determined that not wrapping macros with parens can lead to unexpected behavior. Rather than expect users to practice impeccable code hygiene, implementing automatic parens will save the users time and reduce bugs.

If a preprocessor adds enclosing parentheses every time a macro is expanded, is any useful functionality lost?

# Answer
For integer expressions, auto-wrapping in parentheses seems harmless.

For other macros, though, it would potentially break code. For instance in C, it's fairly common to see function-like macros like this:

```
#define swap(x,y)       \
   do {                 \
     int swap_tmp = x;  \
     y = x;             \
     x = swap_tmp;      \
   } while (0)

```

which would work as a regular statement, e.g.

```
if (condition)
  swap(x,y);
else
  swap(y,z);

```

Adding parentheses around `swap(x,y)` would break this.

Arguably, these macros are needed since the language has poor features, lacking pass-by-reference, or perhaps because the programmer wants to be sure the function is inlined for some reason. Still, they are used.
> 1 votes

# Answer
#define PLUS +

3 PLUS 5

Any more questions?
> 4 votes

# Answer
You can think of the C preprocessor as a machine that operates on lexical tokens. All of the fancy operations that it can do (e.g. string pasting, converting identifiers to strings) operate on tokens and produce tokens.

Compare this with, say, the Lisp macro system, which rewrites a tree into a tree.

Decide on the model of the macro system first. That should guide your thinking.
> 2 votes

---
Tags: language-design
---


# Question
Title: Solving T(n)=T(n−1)+2T(n−2) using substitution
I am trying to solve the following Recurrence relation using substitution method and I am stuck almost half way. I know the answer is 2^n but I can't reach it.

At first, my question is: Who decicdes the base cases? when do we take `T(n)=1 for n=1` or `T(n)=1 for n=0`?

The work I have done till now is as follows:

`T(n) = T(n−1) + 2T(n−2)`

`T(n-1) = T(n-2) + 2T(n-3)`

`T(n-2) = T(n-3) + 2T(n-4)`

Thus, using these, we can subsitute and we get

`T(n) = T(n-2) + 2T(n-3) + 2T(n-2)`

`T(n) = 3T(n-2) + 2T(n-3)` (add and then substitue again)

`T(n) = 5T(n-3) + + 6T(n-4)`

Now assume we go till `k`, but I am not able to generalize the usage of `k` and find a correct assumption that will lead to a result of time complexity of `Big O` of `2^n`

# Answer
The secret of effective substitution is to find the magic numbers -1 and 2. Look and behold.

$$ T(n)+T(n-1)=2T(n-1)+2T(n-2)=2(T(n-1)+T(n-2))$$ Let $S(n)=T(n)-(-1)T(n-1)$. Then $$S(n)=2S(n-1)=2^2S(n-2)=\cdots=2^{n-2}S(2)\tag{I}$$

$$ T(n)-2T(n-1)=-T(n-1)+2T(n-2)=-(T(n-1)-2T(n-2))$$ Let $R(n)=T(n)-2T(n-1)$. Then $$R(n)=-R(n-1)=R(n-2)=\cdots=(-1)^nR(2)\tag{II}$$

Eliminating $T(n-1)$ from formula ($\text{I}$) and ($\text{II}$), we obtain $$T(n)= \frac{2S(n) + R(n)}3=\frac{2^{n-1}S(2) + (-1)^nR(2)}3=\frac{S(2)}62^n + O(1)$$

So, $T(n) = O(2^n)$.

It is assumed in the above that S(2) and R(2) are defined or, what is equivalent, T(2) and T(1) are defined. Their actual values do not affect the conclusion.

In fact, we can be more precise. If $T(2)+T(n-1)\>0$, i.e., $S(2) \> 0$, we will have $T(n)=\Theta(2^n)$. If $T(2)+T(n-1)=0$, we will have $T(n)=O(1)$. If $T(2)+T(n-1)\<0$, we will have $-T(n)=\Theta(2^n)$.

---

How to find those two magic numbers?

Consider T(n) as $x^2$, T(n-1) as $x$ and T(n-2) as 1. Then you get $x^2 = x + 2$. Solving that equation, you get $x=-1$ or $x=2$.

---

(**Exercise.**) Let $F(n)=F(n-1)+F(n-2)$ for $n\in\Bbb N$, $n\ge2$. Show $F(n)= O(\alpha^n)$, where $\alpha = \frac{1+\sqrt 5}2$.
> 4 votes

# Answer
I like the method "try it out and see what happens".

Calculate the next items of the sequence starting with 0,1 and starting with 1,0. You will soon see a pattern. And from the pattern it is obvious that the solutions are

$a \cdot 2^n + b \cdot (-1)^n$
> 0 votes

---
Tags: recurrence-relation
---


# Question
Title: If a language has a regular grammar, is it regular?
If L has a regular grammar, is L always a regular language?

A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language.

So would this answer be true?

# Answer
A regular language can be defined as "a language with a regular grammar". So, yes, the existence of a regular grammar for $L$ means that $L$ is regular. \[Note 1\]

That doesn't mean that every grammar for $L$ is regular. That doesn't matter for this purpose.

It's important to keep the distinction between languages and grammars clear. In general, we say that a language is *X* if it has at least one grammar which is *X* (deterministic, regular, context-free, etc.).

Sometimes, the categorization of grammars is finer (makes more distinctions) than the categorization of languages. A grammar can be left regular or right regular, but a language is simply regular: if it has a left regular grammar, it must have a right regular grammar, and vice versa. Similarly, a grammar might be LR(1), LR(2), etc., but this distinction doesn't apply to languages because if there is an LR(k) grammar for a language, there is also an LR(1) grammar.

This distinction is very important when discussing the relationship between different categories. Failing to make the distinction correctly leads to confusion, because the contexts are very different. For example, there is a simple linear-time algorithm which will tell you if a grammar is regular. However, there is no algorithm which can tell you whether the language recognised by an arbitrary context-free grammar is a regular language.

---

### Notes

1. I believe the original definition of regular languages was based on Kleene's regular expressions. The concept of regular grammars comes from Chomsky's seminal work, in which he called them "Type 3 grammars". His 1959 paper which introduces this hierarchy of grammars (and, indirectly, of languages) contains the proof that Type 3 languages are the same as what he called "finite state languages" -- languages which can be recognised by a Finite State Automaton.

This equivalence leads some people to define "regular language" as "a language which can be recognised by a FSA", although that definition fails to justify the use of the word "regular". (It is the definition found in Michael Sipser's *Introduction to the Theory of Computation*, and also on Wikipedia, for example.)

It is also easy to show that the set of languages which can be described by a regular expressions (in Kleene's sense) is precisely the same as the set of languages which can be described with a regular grammar.
> 3 votes

---
Tags: formal-languages, automata, regular-languages
---


# Question
Title: unambiguous context-free languages and complementation
I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages:

1. Is the complement of an unambiguous context-free language also a context-free language?
2. If a language is context-free, and its complement is context-free as well (i.e., a so-called *strongly context-free language*), is it the case that the language is unambiguous context-free?

The first question above is motivated by the fact that it holds for deterministic context-free languages, which are a strict subclass of the unambiguous context-free languages.

# Answer
Both questions turn out to have negative answers, as shown in \[this\]\[1\] article. In particular, the authors construct

1. An unambiguous context-free language whose complement is not context-free.
2. An inherently ambiguous (i.e., non-unambiguous) context-free language whose complement is context-free.

Consequently, there is no relationship between the notion of unambiguity for context-free languages and the complementation operation.

\[1\] The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages" by Hibbard and Ullian, JACM, Volume 13 Issue 4, Oct. 1966, Pages 588-593 https://dl.acm.org/citation.cfm?doid=321356.321366
> 4 votes

---
Tags: formal-languages, context-free, closure-properties, ambiguity
---


# Question
Title: I want a fast rank only shuffling algorithm for a full 52 card deck
My goal is to do some large iteration Monte Carlo simulation of different card games that require on the order of 1 billion random decks to get a reliably accurate answer. The bulk of the computer time is actually shuffling/preparing the decks, not searching for the "hit" criteria I am looking for.

I am using an string function rich interpreted language. I have bit functions available that work up to 32 bit at a time. I am only interested in the ranks of the 52 card deck, not the suits. So I am looking for a fast algorithm that will give me 4 of each of the 13 ranks for a full 52 card deck. It doesn't matter which order the suits of a particular rank come in since we are ignoring the suits (other than we are enforcing that there only be 4 of each suit for each rank).

My first attempt was to just generate a normal deck with the ranks and suits "encoded" using cards numbered 1 thru 52 with an array of flags telling which cards were already seen. Each random number generated, (from 1 to 52), was for determining the next card (if there was no collision). This algorithm worked but was kinda slow, only producing about 6000 full decks per second on a 3.06 Ghz dual core computer (using only about 50% of the CPU).

My 2nd attempt was just to tweak the first attempt by only picking the first 48 cards (since the "seen" ratio is very high for the last 4 cards and likely many collisions will occur, slowing it down), then choosing a random number from 1 to 24 to handle the permutations of the last 4 "missing" cards which are known from simply scanning the flag array and finding the 4 that are marked "false" meaning they haven't been seen yet. This was roughly 50% faster as I was able to generate about 9000 full decks per second vs. about 6000 previously.

For my 3rd attempt, I am using a 32 bit random number to place 4 or 8 cards at a time from the unshuffled deck into a built up shuffled deck.

Any help/ideas would be greatly appreciated.

# Answer
The questioner, David James wrote on the occasion of bounty.

> Is there a way to speed this shuffle up being that there are repeated ranks? For example, suppose we only had 2 ranks but still 52 cards, could that be sped up over 52 distinct cards? if so, then how can we speed up 13 different ranks with 4 of each rank as in this problem? It seems like the rank only deck of 52 has many fewer possible distinct decks so there should be a way to shuffle them quicker. For example, suppose the deck starts out in rank order such as AAAA22223333... It won't matter if our random # generator (RNG) picks any of the first 4 cards, the result will be the same (a rank A card). I am hoping to use this to our advantage rather than just using Fisher-Yates shuffle as if we are dealing with 52 distinct cards.

Driven by David James's insight and insistence that there should be some way to speed this shuffle up being that there are repeated ranks, this new answer will be focusing whether it is possible to and how to take advantage of the repeated ranks. Other methods to improve the performance, which might be much more effective, powerful and randomness-correct are not considered.

---

Yes, there is **a way to take advantage of the repeated ranks**. Please go to my Java playground provided by repl.it and hit the button "run". You will see output like the following.

```
[6, 10, 3, 8, 7, 10, 3, 3, 5, 13, 2, 2, 4, 5, 4, 4, 1, 9, 11, 11, 6, 9, 10, 10, 5, 12, 13, 3, 1, 7, 2, 4, 8, 2, 3, 13, 8, 12, 6, 9, 4, 13, 9, 12, 5, 7, 1, 7, 11, 1, 3, 6]
    warm-up one: 532197/second
first 4 skipped: 552181/second
    warm-up two: 528262/second
    David-Apass: 656598/second
          Naive: 528541/second
    Improvement: 24.2

```

Your actual output might vary greatly because of many factors. What is important is the last three lines of output. "David-Apass: 656598/second" means 656598 decks per a second by David-Apass shuffle, a variation of Fisher-Yates shuffle that takes advantages of the equal ranks. "Naive: 528541/second" means 528541 decks per a second by a common implementation of the Fisher–Yates shuffle. The line of comparison "Improvement: 24.2%" shows the speed-up of David-Apass shuffle over the common Fisher-Yates shuffle. The nature or the mechanism of David-Apass shuffle apart might have been discovered many years ago. However, I have not found any reference to it yet. All I can claim is that I have discovered it independently, thanks to David James' insight and insistence.

---

\** The following is the accepted answer to the version of the question at https://cs.stackexchange.com/revisions/98273/5, which wass before the bounty.\**

It is not a trivial task to create 1 billion random decks, although it is not a daunting task any more because of today's fast computer.

Firstly, let us talk about the question proper. What would be a fast algorithm?

It looks like that the standard algorithm to shuffle cards, **Fisher–Yates shuffle** is a pretty good choice in term of speed. It is certainly one of the easiest to implement as well. Here is the complete pseudocode.

```
for t from 1 to 1000000000 do
    let arr=[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,11,11,11,11,12,12,12,12,13,13,13,13]
    for i from 51 down to 1 do
         let j  be a random integer such that 0 ≤ j ≤ i
         exchange arr[j] and arr[i]
    output arr

```

How can we make this algorithm run faster?

The very first rule about performance improvement in real-life task is measure, measure and measure. A very rough measurement in my Python code reveals that **the most of the time is spent in the generation of random integers.** This is not surprising once you take a close look at the algorithm above, assuming outputting `arr` is fast enough. In fact, that observation is probably true in any reasonably good algorithm to create a random deck of cards. So the next attack should be how to produce the random number faster or how to reduce the numbers of random numbers need to be generated. If a user has recorded billions of random numbers of similar kind, then fetching them from the records might be a faster way. Or use a faster random number generator. On the other hand, I cannot see how to reduce the number of needed random numbers without affecting the randomness of the generated deck.

Note that manipulation of string is much slower than manipulation of numbers in almost all programming languages, it is preferred to operate the cards in the form of numbers. Since there are a billion of decks, the storage becomes an issue. One of the most efficient ways to encode a deck is to encode them as a 52-digit number in base 13. However, it is not be very convenient to encode to decode from that big number. Another way is, as the questioner mentioned to me in chatroom, to encode each card in a nibble, i.e., four bits, similar to BCD, which is compact enough while much easier to manipulate. Also note that compression cannot probably do much to reduce the storage of this bunch of random numbers.

As Yuval mentioned, an obvious suggestion is to take the advantage of a fast programming language such as C. Let us do not consider assembly languages yet.

Let me conclude this answer with the strategy taken by the questioner, showing the art of applying compute science to real life situations may lead to very different directions.

> I decided to just store the 1 billion shuffled decks in a disk file (about 26GB for 1 billion decks), then I can just reread it when I want to do other analysis. Generating it once will isolate the speed reduction and then the analysis part should "rip" (relatively speaking).
> 2 votes

# Answer
I'm pretty sure there's no way to take any significant advantage of the fact that you don't care about the suits. The most effective solution is likely to just generate random permutations of the integers from 0 to 51, and map these to card ranks by dividing by 4 and rounding down (which can be done with a simple bit shift, since 4 is a power of 2).

As Apass.Jack notes in their answer, for generating the permutations you almost certainly want to use some form of the Fisher–Yates–Durstenfeld–Knuth shuffle, since it avoids the inefficiency of the sample-and-reject-duplicates method when only a few valid choices remain. Since you're generating permutations of consecutive integers, you may want to consider using the "inside-out" variant of the shuffle (probably first described by Knuth in 1994):

```
for i from 0 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← i

```

The main advantage of this algorithm over the "standard" FYDK shuffle is that you don't need to initialize the results array `a` before shuffling it, since it gets dynamically initialized during the shuffle.

Nonetheless, you may want to implement both a standard FYDK shuffle and the inside-out variant and benchmark them, since their different memory access patterns can affect real-world performance in ways that are hard to predict in advance.

---

In any case, at this point the biggest remaining opportunities for optimization are likely to be:

1. using random numbers more efficiently,
2. using a faster random number generator, and
3. switching to a lower-level language.

Of these three, I'd actually recommend starting with #3; this is exactly the kind of problem where using a low-level compiled language like C or C++ (or even a mid-level language with a good JIT compiler, like Java) can provide significant performance benefits with relatively little cost in development effort.

Once you've ported your code to a low-level language, you *may* want to consider optimizing your choice of RNG. There are some pretty fast PRNGs out there (my personal favorite being Bob Jenkins' "flea" RNG, as reviewed e.g. here), but to properly realize their benefits, you need to also minimize the overhead cost of *calling* the generator (ideally, letting your compiler inline the PRNG code directly into your shuffling loop).

---

Finally, it's worth noting that most PRNGs generate something like 32 or more bits of (pseudo)randomness per call, whereas a Fisher-Yates shuffle of a 52 card deck only uses less than 6 bits per iteration. Thus, there *could* certainly be room for optimization by splitting RNG outputs into smaller pieces and reusing them for multiple iterations of the shuffling loop.

That said, I'd personally rather avoid this option, at least until I had exhausted all other possible avenues for optimization. One problem is that, even if your RNG provides perfectly random outputs, it's easy to introduce subtle bugs in the splitting process that can bias your results in ways that may not be so easy to detect. Another problem is that trying to squeeze every last drop of entropy out of your (P)RNG output is a good way to magnify any non-random biases that output may have. Personally, I would feel safer using a fast but possibly not quite perfect PRNG to generate lots of extra random bits, and converting them to random numbers in the required range in a simple and relatively foolproof way, than trying to use up every last bit of my RNG output and relying on that RNG and my conversion code having no subtle weaknesses.

Still, there are *some* simple optimizations you can safely make here. For example, you can trivially save one RNG call (and some other unnecessary work) per shuffle by modifying the code above to look like this:

```
a[0] ← 0
for i from 1 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← i

```

The only difference between this code and the version I copied from Wikipedia above is that I skipped the first iteration, where we always had `i = j = 0`, and instead just initialized `a[0]` before the loop. While such little optimizations won't have much effect alone, they're pretty easy and safe and can add up.

In fact, since you said don't care about the card suits, I guess we can save a few more RNG calls:

```
for i from 0 to 3 do
    a[i] ← 0
for i from 4 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← ⌊i / 4⌋

```

This generates the card ranks directly, by doing the division by 4 inside the initialize-and-shuffle loop, and splits the first four iterations of that loop (where all elements of the array are still identical) into a separate loop. This way, you'll only need 48 RNG calls to shuffle 52 cards. That's almost an 8% speedup (assuming that random number generation dominates the time cost), which might be significant just by itself.

---

Ps. FWIW, while precalculating the shuffled decks and storing them on disk is certainly an option worth considering, I very much doubt it is optimal. With a fast shuffle and a fast RNG, both implemented in a low-level language, shuffling the decks dynamically *should* be orders of magnitude faster than reading them from even a very fast solid-state disk.

---

**Addendum:** There's a potential advantage to reshuffling your previously shuffled decks, rather than generating a new deck for each shuffle: it can smooth out possible biases in your shuffling process and give you a more uniform distribution of shuffles.

Basically, if you start with a new in-order deck for each shuffle (or generate one *during* the shuffle, like the code above does), then you're repeatedly sampling decks from the same distribution. If your RNG (or the way you convert its output into array indices) is not perfect, then this distribution may be biased.

In particular, if you're using a PRNG with less than $\log\_2(52!) \approx 225.6$ bits of internal state, then you're *guaranteed* to have some decks that you can never generate by shuffling an in-order deck, simply because there will be more possible decks than there are possible initial states for your PRNG at the beginning of the shuffle. If you don't care about the suits, the corresponding threshold drops to $\log\_2(52! \mathbin/ 4!^{13}) \approx 166$ bits. But of course, in either case, you'd need at least twice as many bits just to be reasonably sure that *all* possible decks can be generated, and even more to guarantee a reasonable level of uniformity.

On the other hand, if you keep reshuffling a previously shuffled deck, then you're effectively performing a (pseudo)random walk on the set of possible permutations, with the possible transitions defined by the relation "$A$ can be shuffled into $B$ by the PRNG". As long as this random walk is ergodic (and it should usually be, even for pretty crappy RNGs), it should converge towards a uniform distribution on the set of all possible permutations (since the transition kernel is also invariant with respect to the semigroup action).

Thus, if you could keep shuffling the same deck over and over, even with a poor-quality PRNG, you should in principle have a pretty high chance of eventually encountering each possible shuffle equally often. Of course, the order in which you'd encounter these shuffles might not be fully random, and (if you never reseeded the PRNG from a truly random source) there would still be a small probability of getting caught in a short cycle that visits only some of the possible shuffles. And of course, with a 52 card deck (with or without suits), you'd never actually be able to test this within your lifetime on any computer you could possibly build.

But still, in general, a good rule of thumb is that reshuffling the same deck over and over will tend to smooth out any possible biases in the shuffling process, compared to starting from an unshuffled deck each time. In fact, that's pretty much the reason why the often rather imperfect shuffling done by humans using a physical deck of cards is still sufficient to avoid generating noticeably biased decks, and why card players are advised to be extra careful in shuffling a new deck before using it for the first time.

Fortunately, both the standard Fisher-Yates shuffle and the inside-out version described above can be easily made to reshuffle an existing deck. In fact, the standard version does that by default, while for the inside-out variant the changes are minor. Specifically, assuming that `a` is already a (possibly shuffled) permutation of `n` cards, either of the following loops will serve to reshuffle it:

```
// standard FYDK shuffle (descending order)
for i from n - 1 down to 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i: swap a[i] and a[j]

// "inside-out" version (Knuth 1994)
for i from 1 up to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i: swap a[i] and a[j]

```

Either of these will require $n-1$ RNG calls to (re)shuffle an $n$ card deck; unfortunately, in this case, I really don't see any practical way to save any more RNG calls even if some of the cards in the deck are known to be equivalent.

---

**Addendum 2:** If your language / CPU can do fast 256-bit math (specifically, division and remainder), and you have access to a high-quality RNG than can generate 256-bit numbers quickly (such as using two calls to AES\_CTR\_DRBG, which should be pretty fast on x86 CPUs that support the AES-NI instruction set, if your crypto library makes use of it), then you could do something like this:

```
r ← random 256-bit integer (i.e. 0 ≤ r < 2^256)

// optional bias elimination via rejection sampling
while r < 2^256 mod 52!
    r ← random 256-bit integer (i.e. 0 ≤ r < 2^256)

// inside-out FYDK shuffle-and-initialize
a[0] ← 0
for i from 1 to 51 do
    j ← r mod (i + 1)
    r ← ⌊r / (i + 1)⌋
    if j ≠ i: a[i] ← a[j]
    a[j] ← i

```

where hopefully either your compiler is smart enough to fuse the modular reduction and division of `r` by `i + 1` into a single operation, or your language directly provides a combined "divmod" operator or function for it.

As noted in the comments above, the bias elimination by rejection sampling is not strictly required; omitting it just means that about 30% of all possible shuffles are very slightly more likely (about $1 + \frac{52!}{2^{256}} \approx 1.0000000007$ times as likely, to be exact) to occur than the rest. It's up to you to decide whether that bias is something you're willing to accept. If you do decide to use the bias elimination, do precalculate the constant `2^256 mod 52!`, as calculating it from scratch is likely to be almost as expensive as the shuffle itself.

If you *don't* have access to efficient 256-bit math, you can always split the shuffling loop into smaller pieces. For example, $20!$, $32!\mathbin/20!$, $43!\mathbin/32!$ and $52!\mathbin/43!$ are all less than $2^{64}$, so using 64-bit math you could do something like this:

```
s ← 1
a[0] ← 0
for t in (20, 32, 43, 52) do
    m ← 2^64 mod (t! / s!)
    r ← random integer such that m ≤ r < 2^64
    for i from s to t - 1 do
        j ← r mod (i + 1)
        r ← ⌊r / (i + 1)⌋
        if j ≠ i: a[i] ← a[j]
        a[j] ← i
    s ← t

```

where I'm assuming that the code used to generate a `random integer such that m ≤ r < 2^64` internally consumes 64-bit random numbers and does any rejection sampling needed to ensure that the fall into the desired range. Of course, in practice you'd probably want to unroll the outer loop and to precalculate the `m` values for each iteration, or at least to store them in a look-up table.

If you're limited to 32-bit math (or, in particular, if you only have a 64 → 32 + 32 bit divmod operation), you can instead iterate over `t in (12, 19, 25, 30, 35, 40, 44, 48, 52)` and set `m` to `2^32 mod (t! / s!)`. Note that this requires *nine* iterations of the outer loop instead of eight, since there will be some unused entropy left in `r` at the end of each iteration. In principle we could recycle this entropy, but that would complicate the code even more, so I'll leave that as an exercise. ;-)

---

In any case, whichever method you choose, you will definitely want to test your code very throughly before using it. I have not done so myself for the pseudocode examples above, so they might contain bugs, and porting them from pseudocode to your actual programming language could easily introduce more.

Unfortunately, shuffling is exactly the kind of task where it's very easy to make subtle mistakes that are hard to catch in testing due to the inherent stochasticity of the task. Some useful tests I'd recommend include:

* shuffling a small deck of, say, 3 to 5 cards many times, and checking that each possible shuffle occurs approximately equally often (e.g. using Pearson's $\chi^2$ test);
* shuffling a full 52 card deck many times (starting with an ordered deck each time, to maximize any observable bias), recording the position of some specific card in the deck, and checking that those positions are approximately uniformly distributed (again using e.g. a $\chi^2$ test; repeat this for each of the 52 cards);
* same as above, but instead recording the distribution of cards occurring in a given position in the shuffled deck;
* same as the two tests above, but instead record the difference in the positions of two specific cards (modulo 52) or the difference in the card values at two specific positions in the shuffled deck (note that in both cases there will be 51 possible differences, since 0 is not a possible result);
* same as above, but instead of just recording the difference, record each observed pair of positions or card values (note that you'll need more shuffles per test for this, since there will now be 52 × 51 possible outcomes);
* count the number of disjoint cycles in the permutation generated by the shuffle, and check that the distribution of this count over many shuffles matches the expected distribution given by the Stirling numbers of the first kind (in particular, this test should catch any off-by-one errors leading to an accidental implementation of Sattolo's algorithm instead of the standard FYDK shuffle);
* other statistical randomness tests, especially any tests that would directly measure some specific property that you both care about in your actual simulation and can predict the theoretically expected distribution of.
> 3 votes

# Answer
Just about the random number generation: You will need 52 billion random numbers, so the period of a pseudo-random generator must far exceed 52 billion.

I assume you don't need cryptograhically secure random numbers, so you can use a linear congruential random number generator, or some variation of Marsaglia's xorshift generator.

IBM implemented a linear congruential RNG taking one processor cycle per random number on a POWER processor; it should be portable to any processor with a FPU with fused multiply-add.

A 64-bit xorshift generator can probably be vectorised with 256 bit vectors to create four random numbers at a time, and the code to extract a number from 0 to 51 / 0 to 50 / 0 to 49 etc can be vectorised as well. Replicate this four times, and you will get 16 shuffled sequences at a time very, very fast indeed. Ten million sequences per second should be not very hard.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Trying to do HW - not understanding what this author means by giving an efficient algorithm
In this question, what exactly are they trying to ask? I.e. in the trivial case, just travel 200 miles regardless of how many miles posts there are. The penalty is always 0. What are my constraints? Am I missing something from this question that is giving me trouble about what the author means??

See 6.2.

# Answer
Read the question more carefully. You can only stop at hotels. If there isn't a hotel after 200 miles, you'll have to travel some other distance, so the penalty will be nonzero.

"Efficient" almost always means in polynomial time.
> 2 votes

# Answer
This is a classical DP problem. My tip is to first write out the backtracking recurrence, and then later reason about how to memoize the recursive calls.
> 2 votes

# Answer
First you need to understand what the total penalty of a trip would be. Read the question carefully until you understand that. For example, if distances are $50$, $100$, $50$, $100$, then you would drive $150+150$ miles to get a penalty of $50^2 + 50^2$, which is better than a single $300$ mile trip with penalty $100^2$, or $200+100$ miles which is a penalty of $0^2 + 100^2$.

To get the trip with the lowest total penalty: Find the trip with the lowest penalty from $a\_0$ to $a\_1$, from $a\_0$ to $a\_2$, from $a\_0$ to $a\_3$, and so on. Remember the trips and the total penalties. (In each case, you only need to remember the last drive.)

The best trip from $a\_0$ to $a\_0$ is obviously doing nothing. The best trip from $a\_0$ to $a\_1$ is obviously starting at $a\_0$, and driving to $a\_1$.

The best trip from $a\_0$ to $a\_k$ with $k \ge 2$ is either going directly $a\_0$ to $a\_k$, or doing the best trip from $a\_0$ to $a\_i$ for some $1 \le i \le k-1$, then travelling $a\_i$ to $a\_k$.

This is $O (n^2)$ trivially, but there will be obvious shortcuts. And the algorithm is independent of how the penalty of each drive is calculated. Shortcuts probably depend on the penalty being a convex function (that is as the distance grows, the penalty first shrinks up to some minimum, then increases).
> 1 votes

---
Tags: algorithms
---


# Question
Title: Why isn't the Swift programming language type inference more aggressive?
Couldn't the type inference in Apple's new programming language Swift had been done more aggressive? For instance why can't the return type of a function be deduced?

```
func sayHello(personName: String) -> String {
   let greeting = "Hello, " + personName + "!"
   return greeting
}

```

# Answer
> 10 votes
I don't understand Swift's typing system yet, so I can only speculate, but I imagine that it's for the same reason that Scala doesn't have full type inference: nobody knows how to do it in a pragmatically viable way. The combination of parametric polymorphism and subtyping is deadly from the point of view of algorithmic complexity.

# Answer
> 8 votes
I must admit I don't know Swift yet, but here are my thoughts. Putting *some* type annotations in here and there really helps produce better type error messages. Return types and arguments are a great checkpoint that'd use for this. Given a type inconsistency in a function application, a full type inference system doesn't know if you messed up the argument or the return value; it just sees that they are incompatible. By annotating, it we can basically tell the user they are (1) returning a value of the wrong type, or (2) taking a parameter of the wrong type. (The same could be said for an inferred assignment, but we want the inference to do some of the work, just not all of it.)

I am getting this from extensive Haskell experience, which performs full inference. Function signatures are generally the smart place to add a type annotations; then let the type system do the rest within the function.

Other benefits:

* It improves program comprehension and readability. Seeing the type next to the function helps us understand it quicker. We don't want to have read code and do type inference ourselves to understand what it returns.
* Extra type constraints speed up the inference process. I'm not totally convinced anyone cares about this too much. Maybe Apple does in their case.

# Answer
> 0 votes
There are situations in Swift already where compile times are slow because of type inference, so being more aggressive might (will) make this worse.

Type inference needs balancing. It helps you not having to figure out a type when you don’t care (C++ iterators are an example). It helps you using identical source code for different types. It can lead to hard-to-find bugs. That needs balancing, and then there are compilation times.

And I like looking at the first line of a function and figuring it out, without having to read the code.

---
Tags: programming-languages, type-inference
---


title: Running time of median of 3 partioning

text:
# Question
Title: Running time of median of 3 partioning
I am hoping someone can break something down for me in a way I can digest. I am trying to understand the running time for the median of three partitioning.

1. What is the goal of median of three partitioning? Is it to eliminate the possibility of selecting the largest / smallest element as the pivot, thus resulting in O(n^2) run time?
2. What would the run time be of a simple median of three partitioning function? Since there are only 3 possible comparisons, and the comparison operation runs in O(1) time, wouldn't it just be 3O(1) or negligible?

Any assistance would be greatly appreciated. Thus far, I have referenced CLRS and the following three pages for assistance:

# Answer
> 1 votes
You should not confuse **median-of-median algorithm** with **median-of-3 trick**.

The former is $O(n{\rm log}n)$ worst-case time.

**Ans. to 1**. The latter is still $O(n^2)$ worst-case time but faster in practice due to the low frequency of bad patterns seen in practice. This can be seen by the fact that randomized quicksort is $O(n{\rm log}n)$ expected time.

**Ans. to 2**. It is $O(n)$. The comparison work is $O(1)$ since there are only $3$ elements involving. After, determine the value of the median of three, you need to partition the array around this value. This takes $O(n)$ time.

# Answer
> 1 votes
When you implement QuickSort, if you could magically pick the median as pivot then you would get minimal number of comparisons. If you manage to pick pivots close to the median, sorting is faster.

The median of three random elements is usually closer to the median of the array than a single random element. Throw three dice repeatedly and write down the medians. You will get 3 and 4 much more often than the other numbers.

---
Tags: algorithms, runtime-analysis, quicksort
---


# Question
Title: Does co-inductive and co-recursive types also have their recursors?
I'm new to type theory, and recently read introductory materials where dependent type are discussed. One of my friend asked me, "Those dependent types are having recursors & 'inductors'(dependent eliminators), but how about those types that is co-inductive/co-recursive?"

Some related example is much appreciated.

# Answer
To understand coinduction, it helps to understand the categorical presentation of induction (since, as far as I know, coinduction comes from dualizing it there).

The idea behind induction is that we have a functor $F : C → C$, and we consider algebras $(A,\ α : F A → A)$. The operation $α$ specifies how to interpret the structure given by $F$ into $A$. Then, an inductively defined type is an initial algebra $(μF, \mathsf{in} : F μF → μF)$, which mean there is a unique homomorphism $\mathsf{fold}\_A : μF → A$ to any other algebra. This homomorphism is the recursor, and the uniqueness allows us to define the induction principle in various ways, depending on the setting.

Coinduction flips most of these arrows around. Instead of algebras, we have coalgebras, $(A, α : A → F A)$. And instead of being initial, the coinductively defined type is final, so we get a unique $unfold\_A : A → νF$ from any other coalgebra. So, instead of a recursive way of "eliminating", we get a recursive way of "introducing," and the eliminators are non-recursive.

However this flipping around makes some thing not work quite as nicely with coinductive types. I have an Agda development here that tries to explain the stuff about induction above in more detail, with the idea of finding something similar for coinduction. But I never got around to figuring that part out. And as far as I know, there is no known 'nice' interpretation of the coinductive case similar to the inductive one. The one thing to note is that 'just do the same thing with slices as induction' turns out to be uninteresting for coinduction.

One promising thing I have seen is that in cubical type theory, definition by coinduction gives a natural way of showing that two values of a coinductive type are equal, because it automatically corresponds to bisimulation, which is the usual notion of equality for coinductive things. The idea is that an identity from $x : A$ to $y : A$ is a function $eq : \mathbb{I} \to A$ (where $\mathbb{I}$ is an 'interval' type with distinguished values $0$ and $1$) such that $eq\\; 0$ evaluates to $x$ and $eq \\; 1$ evaluates to $y$. Then $unfold\_\mathbb{I}$ gives us a principle for proving $x = y : νF$ by breaking things down to individual pieces like $\mathsf{step} : \mathbb{I} \to F\ \mathbb{I}$. You can see an example of this here.

I don't know if that completely answers your question or not. Hopefully it helps some.
> 4 votes

---
Tags: type-theory, dependent-types, coinduction
---


# Question
Title: Bounded Quantification: Full F<: intuition
I'm currently looking into Chapter 26 of Types and Programming Languages and am a bit confused by the "intuition" for *Full F\<:* (p. 395):

> A type T = ∀X\<:T1.T2 describes a collection of functions from types to values, each mapping subtypes of T1 to instances of T2. If T1 is a subtype of S1, then the domain of T is smaller than that of S = ∀X\<:S1.S2, so S is a stronger constraint and describes a smaller collection of polymorphic values.

Why is S a stronger constraint due to the fact that T's domain is smaller than S's?

# Answer
Consider these assertions:

1. all the cats in my house are grey
2. all the cats in my town are grey

The second assertion implies the first, since any cat in my house is also in my town, so by the assertion it must be grey. In other words, "cats in my town" is a superset of "cats in my house", so the second assertion is stronger (it applies to more cats).

In the same way, the type `S = ∀X<:S1.T2` is stronger than `T = ∀X<:T1.T2` since `S1` is a supertype of `T1`. A program of type `S` must work in all cases (types `X`) where a program of type `T` would work, and possibly even more cases.
> 1 votes

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: “Left identity” of Monad laws in Haskell is wrong
Monad laws in Haskell

```
Left identity:  return a >>= f ≡ f a
Right identity: m >>= return ≡ m
Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

```

is widely known, and I think the "Left identity" rule does not make sense.

In category theory, it is true that Monads corresponds to Monoid, but this "Left identity" is twisting things around.

the binary operator `>>=` is a notation, so is `f a` or `f(x)` etc..

* `f(x)`
* `f a`
* `m >>= f`
* `monad.bind(f)`

In program semantics, all are the same, especially, when we define `f` always returns a monad value.

It's like "1" and "One" means the same entity in mathematics.

```
1 ≡ "One"  // Some Identity!
// this rule must be satisfied in terms of category theory!??

```

So-called "Left identity" in Haskell Monad law: `return a >>= f ≡ f a` is nothing to do with category theory but simply notation.

On the other hand "Right identity": `m >>= return ≡ m` makes sense because according to the notation replacement, it can be rewritten to `return m ≡ m`, and surely this defines one of monad feature or a rule of identity.

(edit)

* `TTX = TX`
* `unit(unit(a)) = unit(a)`
* `return m ≡ m`

whatever, the semantics is the same.

In the later part of `[Monad laws in Haskell][1]`, it makes an excuse saying

> Not in this form, no. To see precisely why they're called "identity laws" and an "associative law", you have to change your notation slightly.

then, it introduces "Kleisli composition operator" : `>=>`.

What?? The different operator is introduced, then they concluds:

> This is a very important way to express the three monad laws, because they are precisely the laws that are required for monads to form a mathematical category.

The widely known "Haskell monad laws" are based on the `bind` binary operator: `>>=`, but in fact, the "left identity" rule is nothing to do with catrgory theory but merely programming notation replacement, then later, by replacing the bind operator to "Kleisli composition operator" : `>=>`, it claims the notation replacement is based on category theory.

I think this fools the readers and is the source of confusion of Monad concept to beginers or all of us.

Probably, I also need to mention that this Monad laws are firstly fomalized in Monads for functional programming by Philip Wadler

EDIT:

Well, I do not deny `return a >>= f ≡ f a` is a binary operator definition. It's a replacement of notation, and here is the thing.

notation replacement is nothing to do with category theory or "Left identity" \`

# Answer
You should be more precise. When you say that `f(x)`, `f a` and `m >>= f` are "the same", that does not make sense as written. `f(x)` and `f a` cannot be the same, they do not even use the same variables. Did you mean to compare `f(u)`, `f u` and `u >>= f`? It is true that `f(u)` and `f u` are the same thing, but `u >>= f` is not. If `f` has type `a -> m b` (where `m` is the monad) then

* in `f u` the type of `u` must be `a`, but
* in `u >>= f` the type of `u` must be `m a`

So the types don't even match. Furthermore, if you look at concrete examples, you will see that `>>=` is not "just notation". It actually does things.

If we now look at the left identity law

```
return u >>= f  ≣  f u

```

we see that we cannot just rewrite the left-hand side to `f u`, or even `f (return u)`. We must take into account what `return` and `>>=` do in a specific case. For instance, in the list monad we define

```
return x = [x]

```

and

```
(xs >>= f) = concat (map f xs)

```

The left identity law holds *because* of how `concat` and `map` work:

```
return x >>= f      ≣
[x] >>= f           ≣
concat (map f [x])  ≣
concat [f x]        ≣
f x

```

The above calculation was not just "notation"!
> 16 votes

---
Tags: functional-programming, category-theory, haskell
---


# Question
Title: Showing that an equivalence relation on programs need not be a congruence
An optional exercise from *Programming Language Foundations* asks

> Can you think of a relation on commands that is an equivalence but not a congruence?

An equivalence here refers to an ordinary equivalence relation. A congruence refers to an equivalence relation where the equivalence of two subprograms implies the equivalence of the larger programs in which they are embedded, e.g., if $a\_1$ and $a\_1'$ are equivalent expressions, then so are $(x ::= a\_1)$ and $(x ::= a\_1')$.

I am unable to think of an example, although I would think one exists. The context of this exercise has to do with an imperative programming language, but an example in another context is welcomed as well.

Any ideas?

# Answer
Let $x,y$ be two fixed distinct variable names.

Call $P$ and $Q$ equivalent iff $Q$ is obtained from $P$ by optionally swapping the variable names $x$ and $y$. That is, either $Q=P$ or $Q=P\\{x/y,y/x\\}$ where the latter uses simultaneous substitution.

It is an equivalence. Reflexivity follows by construction. For symmetry, $P\equiv Q$ swaps if $Q\equiv P$ swaps. For transitivity, we consider the four cases: in the swap-swap case we get the same program back.

It is not a congruence since

$$ x:=x+1 \equiv y:=y+1 \quad \mbox{ but }\quad (x:=0;x:=x+1) \not\equiv (x:=0;y:=y+1) $$

---

Less formally, you can build many examples as follows. Take $f : \mathbb N \to \mathbb N$ to be a function which does NOT in general satisfy

$$ f(n)=f(m) \implies f(n+1)=f(m+1) $$

Say, $f$ is a hash function.

Then, we can say $P\equiv Q$ whenever $f(\\# vars(P))=f(\\# vars(Q))$, where $\\#vars$ counts the number of variables.

This is an equivalence (trivially), but not a congruence since if we add another fresh variable to both $P,Q$ we increment their variable count by one, but $f$ does not preserve that value in general.
> 2 votes

---
Tags: programming-languages
---