# Question
Title: Primitive Recursion equipped with an evaluator function
The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ ev(i,j) $ which computes the $ i $th primitive recursive function on input $ j $.

I was wondering what you can compute with primitive recursion equipped with $ ev $, which I will refer to as secondary recursive functions.

More formally,

* any primitive recursive function is secondary recursive
* secondary recursive functions are closed under composition and primitive recursion (just like primitive recursive functions)
* $ ev $ is secondary recursive
* $ ev $ indexes function such that computing the index of a projection, composition, or recursion is primitive recursive.

Note that in the above, $ev$ is still only computing primitive recursion. Thus, secondary recursion always halts - $ ev $ always halts and the other ways of building secondary recursive functions can't turn halting functions into non-halting functions.

I've found that some "nice" examples of non-primitive-recursive functions are secondary recursive.

For example, for any fixed $ n $ , the function $ f\_n(a,b) = a \uparrow^n b $ is primitive recursive. Given arbitrary $ n $, we can compute the index of $f\_n$ (with some work), then use $ ev $ to compute $ arrow(a,b,n) = a \uparrow^n b $ which is not primitive recursive (it can be used to compute the Ackermann function).

We can also further generalize this to $n$-ary recursion, with $1$-ary recursion being primitive recursion, and $(n+1)$-ary recursion being primitive recursion equipped with an function that evaluates $n$-ary recursive functions. (Then we can generalize this even further, with $ \omega $-ary recursive functions which are the union of $n$-ary recursive functions for all $n$, $(\omega+1) $-ary recursion being primitive recursion equipped with a function that evaluates $\omega$-ary recursion etc. )

I have 2 questions:

* Have these been studied? Do they have a name?
* Are there any "nice" examples of functions which are recursive but not secondary recursive?

# Answer
A paper of Sylvain Schmitz, Complexity hierarchies beyond elementary, seems to tackle a similar question. While not necessarily defining your exact class (I haven't read the paper), it discusses classes of function between primitive recursive and recursive (as well as between elementary and primitive recursive).
> 3 votes

---
Tags: computability, computation-models, primitive-recursion
---


# Question
Title: Undecidability instance on a "find a proof/disproof" machine
I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on:

Suppose we built the following machine in attempt to solve the halting problem. It takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I. It then tries every one-page proof that machine M never halts on input I. Then it tries every two-page proof of each, and so on and so on.

It's quite plain that this wouldn't necessarily always work. By incompleteness, there are statements that can't be proven true or false; it makes sense that there might be Turing machines that are equivalent to these statements. The undecidability problem assures that indeed these do exist.

So, let's follow that through. \[Begin standard proof.\] We have built this function $f(a,b)$ to return $1$ if it finds a proof that program $a$ halts on input $b$, and $0$ if it finds a proof that $a$ doesn't halt. (We note that this function $f$ might never return, so it's not total computable.) We can make a function $g(a)$ that first calls $f(a,a)$, and returns $0$ if $f(a,a)=0$, and enters an infinite loop if $f(a,a)=1$.

If $f(g,g)$ terminated and returned 0, then $g(g)$ would terminate and return 0 -- but $f(g,g)$ terminating and returning 0 implies it found a proof of $g(g)$ not terminating, so this is impossible. If $f(g,g)$ terminated and returned 1, then $g(g)$ would never terminate -- but $f(g,g)$ returning 1 implies it found a proof of $g(g)$ terminating. \[End standard proof.\]

This pair of paradoxes is used in the standard proof to show that there is no function $f$ that always returns $0$ or $1$. There's no problem here, though, because we allow $f$ to not terminate -- and so indeed, it must never terminate, when given the inputs $g$ and $g$.

Here's where I'm confused. Because $f(g,g)$ never terminates, this implies that there is no disproof to be found, because it tries all of them. Suppose that $g(g)$ terminated at some point. Then by running simply it for that many steps, we can see that terminates, and this constitutes a perfectly valid proof.

Keep in mind that $f$ is a *real program*, and *so is $g$*. We know that for these concrete values (in some numbering system), $g(g)$ can't terminate, otherwise $f(g,g)$ would find the dumb proof of simply running it to that point.

The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof, and use it to show that $g(g)$ doesn't terminate, but this is also a problem.

I'm sure there's something here I'm dramatically misunderstanding; I appreciate the time from anyone to answer.

# Answer
> 3 votes
So $f(M,I)$ is this machine that "takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I"...

That's fine, but later on you say "The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof."

That is not true, since you didn't write that proof as a formal proof in terms of "ZFC, let's say, or Peano arithmetic, or whatever", so there is no reason to expect $f(g,g)$ to find it. You didn't even define $f(a,b)$ of $g(x)$ in terms that would translate into most such formal systems.

You assume that you would be able to specify a real formal system if you had to, with sufficient power to express $f$ and $g$ in concrete terms and prove what you say about them, but Godel's theorem says that's not necessarily so.

Furthermore, you say that $f$ and $g$ are *real programs*, but that is not true until this formal system is specified. Because of this you have not proven what you set out to prove. What you have proven is Godel's theorem -- any formal system that allows you to express your claim in terms of itself will either be inconsistent, or will not contain your proof.

# Answer
> 0 votes
If you want to do a proof by contradiction, you have to structure the proof like this. (1) assume the thing, (2) derive some conclusion (3) the conclusion is logically inconsistent, so the assumption is false. Q.E.D! $\square$ In this case: suppose that the Halting Problem is decidable. Then there is a Turing Machine $H$ which computes it. Then I can define another Turing Machine with logically inconsistent behaviour: it calls $M$ and halts iff it says I loop forever, and otherwise, if it says I'm ok, then I go and enter an infinite loop. So any supposed answer errs on at least one instance. Therefore the Halting Problem is not decidable.

All proofs by contradiction follow this scheme. The mistake you made was to omit step (1), where you have to assume that the Halting Problem is decidable. You say, *we note that this function $f$ might never return, so it's not total computable*. Well, if $f$ is not required even to halt, it isn't required to do *anything*! In your formulation, you assume that the Halting Problem is *semi*-decidable, which is true. A language is semi-decidable if there is a Turing Machine which halts on all *yes* instances but not on all *no* instances.

Now for something else. Take a set of axioms: ZFC, Peano Arithmetic or your personal favorite. It is a finite list of axioms, and a finite list of rules that infer from these axioms. So go and do that: Let $M$ be a Turing Machine that, when given the empty tape, writes down the axioms, then makes all the one-step inferences, then writes down all the two-step proofs, and so forth. With each proof, it checks for a contradiction: Have I proved $p\wedge\neg p$? When it finds a contradiction, it halts.

$M$ May halt or not, but whatever the case, you cannot prove it in the same system you started with because if you could, then ZFC could prove its own consistency, but we know that it can't! Scott Aaronson has a nice entry on this on his blog (link). This is an explicit TM with $7,918$ states whose halting behaviour is not provable within a particular axiomatic setting.

This means it's not provable within ZFC, or Peano arithmetic, which is quite different from what you are trying to do, which is to establish unconditionally that there is no TM which always outputs the right answer.

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


# Question
Title: How to use the Pumping Lemma to prove that a restricted subset of 0*1*2*3*, where there are as many 3's as 0's and 1's, is not a CFL?
> Use the pumping lemma for context-free languages to show that the following language is not context-free: $ L = \\{0^i 1^j 2^i 3^k \mid k=i+j \\} $

So I have started like this:

Let us assume that $ L = \\{0^i 1^j 2^i 3^k \mid k=i+j \\} $ is a context-free language. Then $ ∃ p∈N $ such that $∀ w∈L$, $|w|≥p$, then $∃ u,v,x,y,z∈Σ^\*$ such that we can write $w=xuyvz$ which is subject to the following conditions:

$ |uyv|≤p\\ |uv|\>0\\ ∀ k≥0,xu^k yv^k z∈L $

Now, let $p$ be the constant in the Pumping lemma and let $w=0^q 1^p 2^q 3^{p+q}$.

Here I have gotten stuck. I am not sure about my choice of $w$ and very unsure about what I can actually say about $w$ since I know nothing about $q$ compared to $p$ except that the number of $3$'s is $p+q$. I am even doubting that it is possible to show that $L$ is not context-free. At the moment there is always the possibility that $uyv$ is in both the $1$'s and $3$'s or the $0$'s and $2$'s (if I swap $p$ and $q$), and then I could possibly pump them just fine.

What am I missing here? Been starring myself blind trying to find it.

# Answer
> 1 votes
Use $|uyv|\le p$ to avoid the cases you mention, e.g., that $u,v$ pump both the $1$'s and the $3$'s. You can choose $p,q$ in $w$ such a way that this way of pumping is not possible. There is no problem in choosing $p=q$!

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


title: Countability of a binary tree

text:
# Question
Title: Countability of a binary tree
Problem:

> We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable.

My attempt:

A set is countable if it is finite or there is a one-to-one correspondence with the natural numbers. So we need to show that a strategy for an enumeration exists. I'm not sure exactly how detailed I'm supposed to be here, but I just tried to give a general way in which one could enumerate the set of binary trees as defined above...

Assign the first k\_0 positive integers for each binary tree with height 0, then assign the next positive integers for each binary tree having height 1, and so on. The set of all binary trees can be enumerated this way and is thus countable.

Is the above the right way to go about this problem? (I'm not sure if I'm supposed to provide a specific function for how many binary trees there are at any given height k.) Thanks.

# Answer
> 1 votes
To show countability we need not alway show one-to-one onto mapping to $\cal N$. We can instead show a one-to-one onto mapping to a subset of $\cal N$.

# Answer
> 1 votes
It depends how constructive you want your proof to be. The proof you have given seems OK (as long as you point out that there are finitely many binary trees of each height $k$) but it might be possible to do it more elegantly. Here is a sketch.

Every binary tree is one of the following:

* A node which has no children.
* A node whose left child is a binary tree and which has no right child.
* A node which has no left child, and whose right child is a binary tree.
* A node which has a left child and a right child, each of which is a binary tree.

So proceed as follows:

* Label the node with no children as "0".
* Label the node with a left child only as "1", followed by the complete labelling of the child tree.
* Label the node with a right child only as "2", followed by the complete labelling of the child tree.
* Label the tree with a left and a right child as "3", followed by the complete labelling of the left child tree, followed by the complete labelling of the right child tree.

(The process is, in other words, recursive).

So every binary tree is mapped into a unique **finite** sequence of digits "0", "1", "2" and "3". You could interpret them as base 4, if you wanted, or stick to base 10. Not every number corresponds to a binary tree, but every binary tree corresponds to a number, and since the natural numbers are countable, so are the binary trees.

The only advantage over your proof is the aesthetic one that given a tree you can find a number and given a number you can find its tree.

---
Tags: combinatorics, trees, binary-trees, sets, uncountability
---


# Question
Title: smallest circle that covers two points with its center in x axis
I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know how to solve it mathematically.

> Give two planar points p1=(a1,b1) and p2=(a2,b2) and a line y=0, design an algorithm to find the smallest circle that covers both points such that its center (x\*, 0) lies on y=0.

# Answer
Don't solve it mathematically. Solve it by hand for a few cases first, and **then** have a go at making it mathematical. That way you will actually understand what you are doing.

The plane is divided up into points which are closer to $(a\_1,b\_1)$ than to $(a\_2,b\_2)$, points which are further away, and points which are equidistant. The $x$-axis is divided in the same way.

In the zone where points are closer to $(a\_1,b\_1)$, the radius of the circle (with a centre at such a point) is governed by the distance to the *further* point, $(a\_2,b\_2)$. So, in that part of the $x$-axis, you are trying to minimise the distance to $(a\_2,b\_2)$. That is a quadratic function of $x$ (or rather, its square is; but minimising the distance is the same as minimising the square).

In the zone where points are further from $(a\_1,b\_1)$, the radius of the circle is governed by the distance to $(a\_1,b\_1)$. So minimise that.

The zone (or, rather, the point on the $x$-axis) where the points are equidistant doesn't need special treatment because you can treat it as being a member of both the above zones at once.

So you already have an algorithm, more or less: find the minimum radius for the "closer to $(a\_1,b\_1)$" part of the $x$-axis, find the minimum radius for the "closer to $(a\_2,b\_2)$ part, and pick the minimum of the two minima.

But for real understanding, consider the possible geometries of the distance function in each of the two halves, and how the geometry of one half might relate to the geometry of the other half. Because nobody wants a solution to the question (it is known!) so the only benefit of doing the work is to gain understanding.
> 2 votes

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


# Question
Title: How to generate stereo image pair from a stationary mono camera?
I have a stationary mono camera which captures a single image frame at some fps. Assume the camera is not allowed to move,how do i generate a stereo image pair of the acquired frame? Is there any algorithms exists for this? If so, do they available in Open-CV?

# Answer
You can't. You have video of the scene from a single vantage point. Without depth information, you can't infer what the scene would look like from another vantage point.
> 15 votes

# Answer
The terms you probably want to google for are "inferring depth maps". Just like your brain tricks you into seeing 3d if you close one of your eyes, you can heuristically recover depth maps from single 2d images. See for example

Once you have a depth map you can compute a second camera's viewpoint if you also make some (rather bold) assumptions about textures in parts of the image your source camera can't see.
> 9 votes

# Answer
You might be able to do some creative hackery by having different color light sources from different directions, and then do some intense processing (don't ask me how) to figure out the shapes of things based on how much of which light color there is and then change perspective of the 2nd frame.

Or make a lens or mirror to attach to it that will give you 2 perspectives in each frame.
> 2 votes

# Answer
If you can capture an image, shift the scene sideways while keeping the camera stationary, then capture another image, that would produce similar results to having two cameras or having the camera move.
> 1 votes

---
Tags: image-processing, computer-vision, graphics
---


title: Taking the modulus of 2 arrays

text:
# Question
Title: Taking the modulus of 2 arrays
I'm putting together a primality tester for large numbers. When the numbers were smaller things were more straightforwards. I got refined it to a point where I could quickly test any number within the range of long long ints. I wanted to be able to test larger numbers. I've gotten it to read the numbers in as strings then convert to an array. I now have the issue of not knowing how to perform mod on arrays. (int\*)mod(int) isn't too bad but (int\*)mod(int\*) is more complicated.

In short:

1. Is there a relationship between n%c and n%a,n%b where a+b=c
2. How do you take the mod of 2 sums where either sum would give you overload.

# Answer
> 1 votes
Representing integers that are larger than the machine integer size by an array of digits is the standard way to do it, and it's usually called *bignum*, or more formally arbitrary-precision arithmetic.

Division on bignums is not simple. There's no shortcut: it isn't like with addition and subtraction where you can make a single loop that goes over both arrays. You can use the long division method you learned in primary school. There are more complex methods that have better performance in general; the Wikipedia article has a good overview.

There is no useful relationship between $n \bmod (a+b)$ and $n \bmod a$ and $n \bmod b$. I don't see where this would come up anyway. (On the other hand, $(a+b) \bmod p$ is either $(a \bmod p) + (b \bmod p)$ or $(a \bmod p) + (b \bmod p) - p$ depending on whether the sum overflows $p$).

When computing with numbers modulo $n$, always reduce modulo $n$ after each operation, to avoid having numbers grow too large. During one operation, it's usually useful to allow one more digit, to accumulate carries on partial results.

Note that primality testing is rarely done on large numbers, because it gets extremely slow. In cryptography, approximate algorithms are used, that have a small probability of accepting a composite number as prime (but if the algorithm says “prime”, then the number may not be prime, but it's “difficult” to factor).

---
Tags: algorithms, arrays, modular-arithmetic
---


# Question
Title: Densely connected non overlapping subgraph
I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster.

I'm currently trying to detect community using Louvain algorithm, but it detects subgraphs with a low clustering coefficient (0.60) and when I detect maximal or quasi cliques they tend to overlap.

How can I compute a clique decomposition of an undirected graph with no overlap between clusters ? Is there an algorithm with an implementation of it which can deal with my problem ?

Thanks

# Answer
> 3 votes
If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters. When it comes to *community detection* or *clustering*, you need to make a formal definition of a *community* or *cluster* (in this case it is a clique). There are two types of definitions:

**Non-overlapping definitions** \- There are some definitions that do not allow any overlap between communities such as $k$-cores. Basically, the following properties prevent $k$-cores of being overlapping:

1. $k$-cores are maximal
2. Union of two $k$-cores is a $k$-core.

There are lots of different techniques such as modularity optimization, seed expansion, etc. If you are looking for stricter non-overlapping community definitions, you can dig further in this paper (and the sequence of other papers) and find the one ghat works well on coefficient clustering score:

Fortunato, Santo. "Community detection in graphs." Physics reports 486.3 (2010): 75-174.

**Overlapping definitions** \- However, some definitions such as cliques or quasi-cliques, allow overlap between clusters, even though you consider maximality. Below, I show a simple example where few maximal cliques overlap with each other (link for image).

---
Tags: algorithms, graphs, optimization, social-networks, clustering
---


# Question
Title: Numerical Boardgame -- Help with with a pruning method (alpha-beta : minimax)
I'm developing a simple AI to play a boardgame which consists of `N x N` squares, each with a predefined value.

```
44 33 75 12 99 23
53 89 14 01 32 98
34 98 67 45 02 38
89 87 54 21 34 87
65 84 99 72 95 17

```

Each player can either (a) instant claim an unclaimed cell anywhere on the board, or (b) rush an unclaimed cell from a cell already owned. In the case of (b), any enemy cells that are touching the newly claimed cell are converted to your side.

Example:

* Player 1: (1,1) -- {89}
* Player 2: (3,1) -- {87}
* Player 1: rush-\>(2,1) -- {98}

In the scenario above, after the `rush` move, Player 1 now owns all three cells (since `(3,1)` was an adjacent cell to `(2,1)`).

I have the MiniMax algorithm working great for this. It's actually quite fun to watch the AI compete against each other. My problem is determining an effective way to prune moves from the tree. I attempted a trivial pruning method of:

```
 - - If the cell we're claiming is empty
 - - - If the neighbors of the cell we're claiming is empty
 - - - - If the neighbor's-neighbor is an enemy-owned cell
 - - - - - Prune this move

```

The idea above being, we don't want to claim a cell that could immediately result in the opponent `rush`ing towards us, claiming for themselves the cell we just claimed.

This didn't go well.

I'm a bit at a loss for a decent heuristic for pruning moves at this point. Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out `rush` that cell as soon as it's claimed. That is to say, if our opponent owns cell `(4,4)`, it wouldn't be ideal for us to choose `(4,2)` since it could wind up being immediately `rush`ed. But maybe it wouldn't hurt to start at the largest values and just test them out? I don't know.

Any help here is greatly appreciated.

# Answer
> I'm a bit at a loss for a decent heuristic for pruning moves at this point

You can start from the observation that for the side to move there is almost always a better alternative than doing nothing (at least in the first phase of the game, when there are many moves).

So you can try a **"null" move** (the side to play passes and lets the opponent get a free move): if the score of the subtree search (depth reduced by a `R` constant) is still high enough to cause a beta cutoff you can prune the tree.

The pseudo-code is something like:

```
switch_side_to_play()                                     // Null move
score = -ab_search(-beta, 1 - beta, depth - R - 1)
switch_side_to_play()

if (score >= beta )
  // return score (cutoff) or reduce the search depth

```

As every heuristic, **it sometimes fails**. This is an example from Chess but the same problem could happen in your game when there are only few moves available.

If White is to move, he will have to move Kd6, which results in stalemate, or move away from the pawn which loses it.

However if White could pass (null-move), Black would have to play Kc7 (White plays Ke7 and the pawn queens).

---

I'd start trying null move: if it works there is much to gain. If it doesn't work (Checkers / Othello are two well known examples), **ProbCut** heuristic would be a good alternative.

The general idea of ProbCut is to perform a shallow search. If the result is far outside the alpha-beta window you trust the search, otherwise you have to re-search to the full depth.

If you assume this relationship (linear model) between the value of a shallow search ($v'$) and the values of a full search ($v$):

$$v = a \cdot v' + b + \mathcal{E} $$

($\mathcal{E}$ is an error variable, normally distributed, with mean 0 and standard deviation $\sigma$)

Then the beta-cutoff condition of the alpha-beta algorithm ($v \ge \beta$) becomes:

$$ v′\ge \frac{Φ^{−1}(p) \cdot \sigma + \beta − b}{a} $$

(same for $\alpha$, see the linked paper for further details).

The nuisance is that you have to tune many parameters, but this is a very general pruning technique.

---

> Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out rush that cell as soon as it's claimed.

This is similar to captures in chess: you can take a piece but the opponent could recapture.

So a complex heuristic to evaluate the result of a sequence of captures on a square is a possibility, but also a simple heuristic like MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) is very effective.

You could try `highest remaining cell + sum of cells claimed by rush` or `highest remaining cell + sum of cells claimed by rush - (number of attacking cells) % 2`.

According to this heuristic the last move has a value of `9 + (1 + 10) - 1`. This is very coarse but it isn't for pruning, just for ordering.
> 1 votes

---
Tags: artificial-intelligence, heuristics, board-games
---


# Question
Title: Start / End-Point in TSP - How to consider in an algorithm
I moved my question from `Theoretical Computer Science` to this site - proposed by one of the users there - and I'm hoping don't be off-topic again.

At my university, I had chosen to write a term paper about `Inventory Routing Problem` (`IRP`). To get comfortable with this topic (I'm a software engineer), I started with some simpler problems like `Traveling Salesman Problem` (`TSP`) and afterwards with the `Vehicle Routing Problem` (`VRP`) which can be defined as simplified IRP problems.

To solve these kind of problems, I wrote an `Ant Colony System` algorithm with some adaption to the specific problem. But one thing I'm pretty unsure is how to deal with the start and end node of a TSP? Most literature have a strong constraint, that the depot (start/end node) has to be the same and is determined, which makes sense. But the algorithms (heuristics) just cover finding the shortest path. A lot of algorithms determines the starting point randomly. Are there any disadvantages if I define the starting point as fix? But the bigger question is can I add the last point (starting point) independently of the found route to calculate the total costs?

Let's say the algorithm find the cheapest way with `D -> 2 -> 3 -> 1 (-> D)` but recalculating these manually results in `D -> 2 -> 1 -> 3 -> D` because `1 -> 3 -> D`is faster than `3 -> 1 -> D`. But how I have to include a fixed ending point in my algorithm? I guess it's independent of which specific algorithm.

If you don't understand my question please leave a comment and I try to rewrite it =)

# Answer
The result of any algorithm for TSP is a *tour*, that is a *cycle* in the graph. When translating that answer into practice, you can pick any node as starting point without changing the cost of the tour at all.
> 1 votes

---
Tags: algorithms, traveling-salesman
---


# Question
Title: How is the problem of sorting in contiguous runs called?
I am having a bit of brain fail and I can't remeber the name of the following problem (so I can find some literature around it...).

> Given a sequence of values, sort it in a way that equal elements are compacted in runs (contiguous subsequences of identical elements).

For instance:

$$ \\{1, 2, 4, 2, 1, 3\\} \rightarrow \\{ 2, 2, 4, 3, 1, 1 \\} $$

The runs are not otherwise sorted -- only equality comparison is required, not ordering; and they're compacted (there should not be two different runs containing equal elements).

# Answer
> 1 votes
Gopan et al. seem to define a more general problem and call it *array partitioning* \[1\].

> The goals of array partitioning are twofold. First, we would like to isolate in separate groups \[...\] we partition an array so that each element whose index is equal to the value of any of the vari ables in the set is placed in a group by itself. \[...\]
>
> \[W\]e partition each array $A \in Array$ by grouping together elements of $A$ for which all partitioning functions in $\Pi\_A$ evaluate to the same values.

I have not dug into how their formal framework captures your problem and it may not even do so. Still, I think the general idea is close enough to use the word.

Come to think of it, Quicksort-style partitioning is related as well: you want to partition w.r.t. identify, in Quicksort we partition w.r.t. equivalence classes induced by some pivots.

---

1. A framework for numeric analysis of array operations by D. Gopan, T. Reps and M. Sagiv (2005) \[preprint\]

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


# Question
Title: Can I speed up Insertion Sort by using a tree for finding insertion positions?
I want to implement an insertionSort-algorithm. Let's say I have these pseudocode.

```
function insertionSort(F)
  for i <- 1 to n - 1 do
    j  <- findInsertPosition(F, i, 0, i - 1)
    insert(F, i, j)
  end for
end function

```

Now I want to implement the `findInsertPosition` function. Say I give this function my list, which is an array, and change this array into a tree, so that I can search iteratively in this tree for my element.

Would my complexity for the whole code be still maintained in $O(n \log n)$?

# Answer
> 1 votes
> Would my complexity for the whole code be still maintained in $O(n \log n)$?

Let's check where we're coming from: Insertion Sort runs in time $\Theta(n^2)$ (worst and average case) if you implement `findInsertionPosition` (`fIP`) with a simple loop that scans the array.

Second, let's check what we can possible achieve. Assume that `fIP` runs in time $O(1)$. We *still* get $\Theta(n^2)$ since `insert` alone takes times linear in `i` in each iteration (worst and average case), adding up to $\Theta(n^2)$.

Third, why use a tree? You can easily achieve running-time *logarithmic* in `i` for `fIP` (for a total of something in $\Theta(n \log n)$) by using binary search. That would still be dominated by the cumulative cost of `insert`, of course.

If you *did* use a tree, it would make the most sense to not throw it away between iterations; `fIP` would be obsolete. You would effectively have sorting by creating a search tree (which we don't really call Insertion Sort) but, yes, *that* would have running-time in $\Theta(n \log n)$, provided you use a balanced search tree.

In summary, no, it does not make sense to try and tweak Insertion Sort by using search trees.

---
Tags: algorithms, runtime-analysis, sorting, search-trees, arrays
---


# Question
Title: Shortest path from that passes through a set of edges once
Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big.

Slow solution: Finding shortest path from $A$ to each edge of $X$ and shortest path from each edge to $B$ in graph $G\setminus{X}$. Combining those paths and choosing the shortest one.

Can anyone think of a faster solution that doesn't require running Dijkstra's algorithm for each edge from $X$?

# Answer
> 2 votes
*Assumption:* Since you talk about Dijkstra, I assume you have non-negative edge weights.

Remember that Dijkstra already computes shortest paths to *all* other nodes. That is, after *two* runs -- one with $A$ and one with $B$ as starting node¹ -- you have shortest paths from $A$ to all nodes incident to $X$, and from $B$ to all nodes incident to $X$.

We just have to make sure that there are no edges from $X$ on these paths. The idea is to make edges from $X$ so expensive that choosing *all* other edges is better than picking just one edge from $X$. That actually pretty straight-forward to do.

Let $W = 1 + \sum\_{e \in E} w(e)$; then modify the weights so that

$\qquad\displaystyle w'(e) = \begin{cases} w(e), &e \not\in X;\\W + w(e), &e \in X.\end{cases}$

A shortest path w.r.t. $w'$ of weight $\<W$ is shortest w.r.t. $w$ when ignoring paths that hit $X$; if it has larger weight there is no path that avoids $X$ between the two nodes.

Now, if the shortest path from $A$ to $B$ you find by the two Dijkstra runs has weight $\<W$, it is one contender for the shortest path. In addition, you have to find the best pair of paths that connect $A$ and $B$ to different ends of an $X$-edge. Combine for all $e \in X$ the shortest paths to $A$ and $B$, and add the original weight $w(e)$.

Note that there are two pairs of paths for each such $e$! That is, we get $2|X|+1$ paths to chose to minimal one from². So that is an additional $\Theta(|X|)$ effort, which is dominated by the initial runs of Dijkstra.

In total, this solves your problem with two Dikjstra runs and one graph modification that can be performed in $\Theta(|E|)$, or even on-the-fly if your algorithm is implemented with nice abstractions.

---

1. This only works in *undirected* graphs. If your edges are directed, you need to perform the second run on an reversed copy of $G$.
2. If there is none with weight $\<W$ then the original graph doesn't have *any* path from $A$ to $B$ that hits $X$ at most once!

---

This answer saw heavy revision. While the ideas were all there from the start they were presented as two solutions, neither of which worked on its own. Credits to Draex\_ for picking the post apart!

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


# Question
Title: What does the number of bit of microprocessor mean?
Intel 8085 is a 8 bit processor whereas 8086 is a 16 bit processor,what does the number of bit specify?

# Answer
> 1 votes
How many bits wide its registers are: usually, its data registers (the ones which can load and store data and perform logical and arithmetical functions).

The 8086 has 16-bit data and address registers, and a 16-bit data path to external memory.

The 8088 has 16-bit data and address registers, but only an 8-bit data path to external memory. Because it is internally identical to the 8086, it is also considered to be a 16-bit processor.

The 8085 has 8-bit data registers and 16-bit address registers. The address registers (apart from SP) are made up of pairs of 8-bit data registers. The fact that it is possible to add one address register to another isn't enough to make the processor considered to be "16-bit".

# Answer
> 0 votes
This number indicates the width of the supported bus, and practically is the basic unit of the processors: the registers are (usually) in this size and all supported operations are defined (usually) on operands on this size.

---
Tags: computer-architecture
---


# Question
Title: Do functions with slower growth than inverse Ackermann appear in runtime bounds?
Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant inverse Ackermann term is ignored.

Are there any examples of known algorithms with running times that involve functions that grow fundamentally slower than inverse Ackermann (e.g. inverses of functions that are not equivalent to Ackermann under polynomial or exponential etc. transformations), that give the best-known worst-case time complexity for solving the underlying problem?

# Answer
Seth Pettie came up with an algorithm for computing the *sensitivity* of a minimum spanning tree in time $O(m\log \alpha(m,n))$, improving on an algorithm of Tarjan which computes the same in time $O(m\alpha(m,n))$. (Compare this to Chazelle's $O(m\alpha(m,n))$ algorithm for computing the minimum spanning tree itself.) The sensitivity problem asks to compute, for a given graph and a given minimum spanning tree, by how much each edge weight can change without changing the minimum spanning tree.

(Thanks to Tsvi Kopelowitz for this reference.)
> 9 votes

# Answer
The most comically slowly-growing function I've ever seriously seen used in a paper is $\alpha^\*(n)$, the number of times you have to apply the Ackermann inverse to drop $n$ to some fixed constant. It's used in this paper on the deque conjecture on splay trees.
> 5 votes

# Answer
When Alan Turing discovered the computer, there used to be several models for the computer proposed. Turing proved that some (3) of these models could simulate each other AND compute the Ackermann function, whereas the other models could simulate each other but not the Ackermann function (so they could not simulate the 3). Therefore, these 3 models (Turing Machine, von Neumann and one I don't know), were chosen as the architecture for a computer. This does not mean the Ackermann function is the limit of the computer, but I suppose it's hard science. I'm not aware of any computable functions that grow faster than the Ackermann function.

Now, I don't think there's a practical problem that matches your question, but perhaps we can construct one. We need to put constraints on the input though. Since we can't use O(n), we cannot check the whole input. In fact, we cannot even check the length of the input as that would be O(log n). So, we need as first parameter a representation of the length of the rest of the input, for example c such that Ackermann(c) is the length of the input. Since this is also not suitable, we demand as first value in our input the parameter c, such that bb(c) is about the length of the input, where bb is the busy beaver function. This function is incomputable but bb(c) certainly exists. Then, the algorithm goes like:

```
for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

```

The purpose of the algorithm is to check that if c is the inverse of bb, if then the input length is greater than bb(c).

If there's a computable function that grows faster than the Ackermann function, I think we can use it's inverse to create an algorithm that answers your question on any input.
> -1 votes

---
Tags: reference-request, algorithm-analysis, time-complexity, runtime-analysis
---


# Question
Title: How to calculate IV, EV and optimal k for K-means?
Could someone explain how to calculate the following 3 evaluative properties:

* Intercluster Variability (IV) - How different are the data points within the same cluster
* Extracluster Variability (EV) - How different are the data points that are in distinct clusters
* Optimum value of k

The third one I believe is by min EV/IV

Anyway please advise.

# Answer
> 3 votes
$C$ is a cluster, $c$ is centroid, $d$ is provided distance function, $\delta$ is Dirac measure, $x$ is element.
$IV = \sum \limits\_C \sum \limits\_{x \in C} d(x, c)$ *meaning* for each cluster calculate the sum of distances from it's centroid, and sum the results.

$EV = \frac{1}{N} \sum \limits\_i \sum \limits\_j\delta(C(x\_i) \ne C(x\_j))d(x\_i, x\_j)$ *meaning* sum the distances between elements from different clusters and divide the result by number of elements.
One possibility for optimal $k$ is to minimize $\frac{IV}{EV}$. But there are some other techniques of determining optimal number of clusters or referenced from there eight methods of finding $k$. In fact I would not state that any given method is better, preferable or can be determined blindly in advance, this is the part where you should define your optimum that makes sense to you, your data and outcome of what you use clusters for.

# Answer
> 3 votes
## How to get the optimal value for $k$?

You have to define a measure for optimiality. The problem with that is that with bigger $k$ most measures become smaller (better). One measure which is independent from $k$ is the silhouette coefficient:

Let $C = (C\_1, \dots, C\_k)$ be the clusters. Then:

* Average distance between an object $o$ and other objects in the same cluster: $$a(o) = \frac{1}{|C(o)|} \sum\_{p \in C(o)} dist(o, p)$$
* Average distance to the next cluster: $$b(o) = \min\_{C\_i \in \text{Cluster} \setminus C(o)}(\frac{1}{C\_i}) \sum\_{p\in C\_i} \sum\_{p \in C\_i} \text{dist}(o, p)$$
* Silhouette of an object: $$s(o) = \begin{cases}0 &\text{if } a(o) = 0, \text{i.e. } |C\_i|=1\\ \frac{b(o)-a(o)}{\max(a(o), b(o))} &\text{otherwise}\end{cases}$$
* Silhouette of a clustering $C$: $$\text{silh}(C) = \frac{1}{|C|} \sum\_{C\_i \in C} \frac{1}{|C\_i|} \sum\_{o \in C\_i} s(o)$$

You can see that $s(o) \in \[-1, 1\]$ and $\text{silh}(C) \in \[-1, 1\]$. Higher is better. Smaller than 0 is very bad.

Now you can start with $k=1$ and increase $k$ until $\text{silh}(C)$ gets smaller again.

However, there are alternatives to $k$-means clustering:

# Answer
> 0 votes
There isn't an optimum value for k, all you can do is use one which is not too bad! To do so (it's a maths approach), I use a PCA (principal components analysis) which gives me the proportion of variance explained by each axis of the eigen vectors. Suppose you have 10 variables and you see that 4 axis explained 90% of the variance, then you can set k to 4.

---
Tags: optimization, machine-learning, statistics, cluster, clustering
---


# Question
Title: Concurrency: Is it order-independability or interruptibility of tasks?
After researching concurrency I am unable to discern if it is either of these specifically or it encapsulates both?

I was also wondering if someone could provide some programming applications/real world examples I am struggling to grasp the concepts entirely and it feels like every where I look people have different understandings.

Just two re-define the two concepts I believe it to be:

1. Order independent: There is 3 Tasks A, B and C they need to be completed for the application to finalize, and are able to be completed in any order.
2. Interruptible: Tasks are able to be halted mid processing in order to complete part of one of the other tasks.

Point 2 I am most uncertain about how is this advantageous for a serial application? I am guessing it would be to do with user input/bypassing locks or waits caused by requiring further information so other tasks can be completed.

NOTE: I am trying to apply these in a context outside of parallelism.

# Answer
Concurrency is working with tasks that may run simultaneously. In my experience, when this term is used, the main focus is on *correctness*: making sure a system works as intended.

One way of doing that is to impose additional constraints on the system and ensure that they are always met. Order independence and interruptability are examples of two such constraints. You may want them to hold for your concurrent system. But they are not required properties of concurrent systems in general: for many concurrent systems, they do not hold and do not need to hold.

For instance, in MySQL, you can configure to what extent you want your transactions to be isolated, with full serializability (order independence) as the highest level.
> 2 votes

---
Tags: concurrency
---


# Question
Title: Wikipedia does not list insertion complexity for arrays - why?
Wikipedia does not list insertion complexity for arrays in the list of linked-list implementations.

Is this because insertion operations are not defined on the array ADT?

# Answer
> 1 votes
The array is a fixed-size data structure, and insertions would change its size. Thus they are impossible, which is why Wikipedia says "N/A" for the insertion complexity.

A dynamic array *can* have its size changed, which is why complexities are given in that column.

---
Tags: data-structures, arrays
---


# Question
Title: What type of an algorithm is being used for directory structure scanning?
So after learning about DFS and BFS yesterday in my class I was curious as to how is scanning on various file system being done. I spent quite a bit of time trying to look for some references on the web, but so far I have failed in doing so. I'm assuming that either DFS or BFS are behind the core "scanning" in some file systems.

There's also Dijkstra's algorithm but as I'm not even sure if file system is a weighted or unweighted tree (ie. number of files being the weight or file size) it's hard to say if it's useful or not because I believe that BFS would be better than Dijkstra if it's unweighted tree.

I hope that someone could clear this up as there just isn't anything specific about it on the web.

# Answer
For most file systems, a directory lists its entries in a certain order, so reading ("scanning") an individual directory will return its entries in that order.

But when it comes to scanning whole directory structures, there is no such thing as "core scanning": there isn't a common implementation for that.

I think depth-first is more popular; e.g. *GNU find* only supports depth-first scanning. This may be due to depth-first scanning consuming less memory on average; it can't be due to breath-first search being harder to implement, as it's just a matter of treating your list of files to visit as a queue rather than a stack.
> 5 votes

---
Tags: operating-systems, search-algorithms, filesystems
---


# Question
Title: Why do we not combine random number generators?
There are many applications where a pseudo random number generator is used. So people implement one that they think is great only to find later that it's flawed. Something like this happened with the Javascript random number generator recently. RandU much earlier too. There are also issues of inappropriate initial seeding for something like the Twister.

I cannot find examples of anyone combining two or more families of generators with the usual xor operator. If there is sufficient computer power to run things like java.SecureRandom or Twister implementations, why do people not combine them? ISAAC xor XORShift xor RandU should be a fairly good example, and where you can see the weakness of a single generator being mitigated by the others. It should also help with the distribution of numbers into higher dimensions as the intrinsic algorithms are totally different. Is there some fundamental principle that they shouldn't be combined?

If you were to build a true random number generator, people would probably advise that you combine two or more sources of entropy. Is my example different?

I'm excluding the common example of several linear feedback shift registers working together as they're from the same family.

# Answer
> 8 votes
IIRC (and this is from memory), the 1955 Rand bestseller A Million Random Digits did something like this. Before computers were cheap, people picked random numbers out of this book.

The authors generated random bits with electronic noise, but that turned out to be biassed (it's hard to make a flipflop spent exactly equal times on the flip and the flop). However, combining bits made the distribution much more uniform.

# Answer
> 45 votes
Sure, you can combine PRNGs like this, if you want, assuming they are seeded independently. However, it will be slower and it probably won't solve the most pressing problems that people have.

In practice, if you have a requirement for a very high-quality PRNG, you use a well-vetted cryptographic-strength PRNG and you seed it with true entropy. If you do this, your most likely failure mode is not a problem with the PRNG algorithm itself; the most likely failure mode is lack of adequate entropy (or maybe implementation errors). Xor-ing multiple PRNGs doesn't help with this failure mode. So, if you want a very high-quality PRNG, there's probably little point in xor-ing them.

Alternatively, if you want a statistical PRNG that's good enough for simulation purposes, typically the #1 concern is either speed (generate pseudorandom numbers really fast) or simplicity (don't want to spend much development time on researching or implementing it). Xor-ing slows down the PRNG and makes it more complex, so it doesn't address the primary needs in that context, either.

As long as you exhibit reasonable care and competence, standard PRNGs are more than good enough, so there's really no reason why we need anything fancier (no need for xor-ing). If you don't have even minimal levels of care or competence, you're probably not going to choose something complex like xor-ing, and the best way to improve things is to focus on more care and competence in the selection of the PRNG rather than on xor-ing.

*Bottom line*: Basically, the xor trick doesn't solve the problems people usually actually have when using PRNGs.

# Answer
> 17 votes
In fact, something of a breakthrough has just been announced by doing precisely this.

University of Texas computer science professor David Zuckerman and PhD student Eshan Chattopadhyay found that a "high-quality" random number could be generated by combining two "low-quality" random sources.

Here's their paper: Explicit Two-Source Extractors and Resilient Functions

# Answer
> 8 votes
Suppose that $X\_1,\ldots,X\_n$ is a pseudorandom binary sequence. That is, each $X\_i$ is a random variable supported on $\\{0,1\\}$, and the variables $X\_1,\ldots,X\_n$ are not necessarily independent. We can think of this sequence being generated in the following way: first we sample a uniformly random key $K$, and then use some function $f(K)$ to generate the pseudorandom sequence.

How do we measure how good the pseudorandom sequence $X\_1,\ldots,X\_n$ is? While it is possible to measure how good a particular realization is (say using Kolmogorov complexity), here I will concentrate on measures which depend on the entire distribution of the random variable $(X\_1,\ldots,X\_n)$. One such example is entropy, but we will only require two properties of our measure $L$: (a larger $L(\cdot)$ means a more random sequence)

* If $y\_1,\ldots,y\_n$ is a *deterministic* sequence (i.e., a fixed sequence) then $L(X\_1 \oplus y\_1, \ldots, X\_n \oplus y\_n) = L(X\_1,\ldots,X\_n)$.
* If $\vec{X^0},\vec{X^1}$ are two independent pseudorandom sequences, $T \in \\{0,1\\}$ is an independent random bit, and $\vec{Z} = \vec{X^T}$, then $L(\vec{Z}) \geq \min(\vec{X^0},\vec{X^1})$.

The first property means that the measure is invariant under flipping the $i$th bit. The second property means that if we mix two distributions $\vec{X},\vec{Y}$, then the result is at least as good as the worse one.

Any reasonable randomness measure will satisfy the first property. The second property is satisfied by most popular measures such as entropy $H$ and min-entropy $H\_\infty$.

We can now state and prove a theorem showing that XORing two pseudorandom sequences is always a good idea.

**Theorem.** Let $\vec{X},\vec{Y}$ be two independent pseudorandom sequences of the same length, and let $L$ be an admissible randomness measure (one satisfying the two conditions above). Then $$ L(\vec{X} \oplus \vec{Y}) \geq \max(L(X),L(Y)). $$

**Proof.** Suppose $L(X) \geq L(Y)$. Then $X \oplus Y$ is a mixture of the distributions $X \oplus y$, mixed according to the distribution of $Y$. Since $L(X \oplus y) = L(X)$ and a mixture is at least as good as the worst distribution being mixed, we obtain $L(X \oplus Y) \geq L(X)$. $~\square$

What this theorem means is that if you XOR two pseudorandom sequences generated using two *independent* keys, the result is always at least as good as the better sequence being XORed, with respect to any admissible randomness measure.

In practice, in order to use two independent keys, we probably expand one key to two keys in a pseudorandom fashion. The two keys are then not independent. However, if we use an "expensive" way to expand the one key into two keys, we expect the resulting two keys to "look" independent, and so for the theorem to hold "morally". In theoretical cryptography there are ways of making this statement precise.

---

Should we, then, XOR two pseudorandom number generators? If we are not restricted by speed, then that's certainly a good idea. But in practice we have a speed limit. We can then ask the following question. Suppose that we are given two PRNGs, each with a parameter $T$ that controls the running time (and so the strength) of the generator. For example, $T$ could be the length of an LFSR, or the number of rounds. Suppose we use one PRNG with parameter $T\_1$, the other with parameter $T\_2$, and XOR the result. We can assume that $T\_1 + T\_2 = t$, so that the total running time is constant. What is the best choice of $T\_1,T\_2$? Here there is a tradeoff which is hard to answer in general. It may be that the setting $(t/2,t/2)$ is much worse than either $(t,0)$ or $(0,t)$.

The best advice here is to stick to a popular PRNG which is considered strong. If you can spare more time for generating your sequence, XOR several copies, using independent keys (or keys generated by expanding a single key using an expensive PRNG).

# Answer
> 5 votes
I'll give this a shot, since I'm sufficiently disturbed by the advice given in some of the other answers.

Let $\vec{X},\vec{Y}$ be infinite bit sequences generated by two RNGs (not necessarily PRNGs which are deterministic once initial state is known), and we're considering the possibility of using the sequence $\vec{X} \oplus \vec{Y}$ with the hope of improving behavior in some sense. There are lots of different ways in which $\vec{X} \oplus \vec{Y}$ could be considered better or worse compared to each of $\vec{X}$ and $\vec{Y}$; here are a small handful that I believe are meaningful, useful, and consistent with normal usage of the words "better" and "worse":

* (0) Probability of true randomness of the sequence increases or decreases
* (1) Probability of observable non-randomness increases or decreases (with respect to some observer applying some given amount of scrutiny, presumably)
* (2) Severity/obviousness of observable non-randomness increases or decreases.

First let's think about (0), which is the only one of the three that has any hope of being made precise. Notice that if, in fact, either of the two input RNGs really is truly random, unbiased, and independent of the other, then the XOR result will be truly random and unbiased as well. With that in mind, consider the case when you believe $\vec{X},\vec{Y}$ to be truly random unbiased isolated bit streams, but you're not completely sure. If $\varepsilon\_X,\varepsilon\_Y$ are the respective probabilities that you're wrong about each of them, then the probability that $\vec{X} \oplus \vec{Y}$ is not-truly-random is then $\leq \varepsilon\_X \varepsilon\_Y \lt min\\{\varepsilon\_X,\varepsilon\_Y\\}$, in fact *much* less since $\varepsilon\_X,\varepsilon\_Y$ are assumed very close to 0 ("you believe them to be truly random"). And in fact it's even better than that, when we also take into account the possibility of $\vec{X},\vec{Y}$ being truly independent even when neither is truly random: $$ \begin{eqnarray\*} Pr(\vec{X} \oplus \vec{Y} \mathrm{\ not\ truly\ random}) \leq \min\\{&Pr(\vec{X} \mathrm{\ not\ truly\ random}), \\ &Pr(\vec{Y} \mathrm{\ not\ truly\ random}), \\ &Pr(\vec{X},\vec{Y} \mathrm{\ dependent})\\}. \end{eqnarray\*} $$ Therefore we can conclude that in sense (0), XOR can't hurt, and could potentially help a lot.

However, (0) isn't interesting for PRNGs, since in the case of PRNGs none of the sequences in question have any chance of being truly random.

Therefore for this question, which is in fact about PRNGs, we must be talking about something like (1) or (2). Since those are in terms of properties and quantities like "observable", "severe", "obvious", "apparent", we're now talking about Kolmogorov complexity, and I'm not going to try to make that precise. But I will go so far as to make the hopefully uncontroversial assertion that, by such a measure, "01100110..." (period=4) is worse than "01010101..." (period=2) which is worse than "00000000..." (constant).

Now, one might guess that (1) and (2) will follow the same trend as (0), and that therefore the conclusion "XOR can't hurt" might still hold. However, note the significant possibility that neither $\vec{X}$ nor $\vec{Y}$ was observably non-random, but that correlations between them cause $\vec{X} \oplus \vec{Y}$ to be observably non-random. The most severe case of this, of course, is when $\vec{X} = \vec{Y}$ (or $\vec{X} = \mathrm{not}(\vec{Y})$), in which case $\vec{X} \oplus \vec{Y}$ is constant, the worst of all possible outcomes; in general, it's easy to see that, regardless of how good $\vec{X}$ and $\vec{Y}$ are, $\vec{X}$ and $\vec{Y}$ need to be "close" to independent in order for their xor to be not-observably-nonrandom. In fact, being not-observably-dependent can reasonably be defined as $\vec{X} \oplus \vec{Y}$ being not-observably-nonrandom.

Such surprise dependence turns out to be a really big problem.

---

## An example of what goes wrong

The question states "I'm excluding the common example of several linear feedback shift registers working together as they're from the same family". But I'm going to exclude that exclusion for the time being, in order to give a very simple clear real-life example of the kind of thing that can go wrong with XORing.

My example will be an old implementation of rand() that was on some version of Unix circa 1983. IIRC, this implementation of the rand() function had the following properties:

* the value of each call to rand() was 15 pseudo-random bits, that is, an integer in range \[0, 32767).
* successive return values alternated even-odd-even-odd; that is, the least-significant-bit alternated 0-1-0-1...
* the next-to-least-significant bit had period 4, the next after that had period 8, ... so the highest-order bit had period $2^{15}$.
* therefore the sequence of 15-bit return values of rand() was periodic with period $2^{15}$.

I've been unable to locate the original source code, but I'm guessing from piecing together a couple of posts from in https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A that it did precisely the following (C code), which agrees with my memory of the properties above:

```
#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

```

As one might imagine, trying to use this rand() in various ways led to an assortment of disappointments.

For example, at one point I tried simulating a sequence of random coin flips by repeatedly taking:

```
rand() & 1

```

i.e. the least significant bit. The result was simple alternation heads-tails-heads-tails. That was hard to believe at first (must be a bug in my program!), but after I convinced myself it was true, I tried using the next-least-significant bit instead. That's not much better, as noted earlier-- that bit is periodic with period 4. Continuing to explore successively higher bits revealed the pattern I noted earlier: that is, each next higher-order bit had twice the period of the previous, so in this respect the highest-order bit was the most useful of all of them. Note however that there was no black-and-white threshold "bit $i$ is useful, bit $i-1$ is not useful" here; all we can really say is the numbered bit positions had varying degrees of usefulness/uselessness.

I also tried things like scrambling the results further, or XORing together values returned from multiple calls to rand(). XORing pairs of successive rand() values was a disaster, of course-- it resulted in all odd numbers! For my purposes (namely producing an "apparently random" sequence of coin flips), the constant-parity result of the XOR was even worse than the alternating even-odd behavior of the original.

A slight variation puts this into the original framework: that is, let $\vec{X}$ be the sequence of 15-bit values returned by rand() with a given seed $s\_X$, and $\vec{Y}$ the sequence from a different seed $s\_Y$. Again, $\vec{X} \oplus \vec{Y}$ will be a sequence of either all-even or all-odd numbers, which is worse than the original alternating even/odd behavior.

In other words, this is an example where XOR made things worse in the sense of (1) and (2), by any reasonable interpretation. It's worse in several other ways as well:

* (3) The XORed least-significant-bit is obviously biased, i.e. has unequal frequencies of 0's and 1's, unlike any numbered bit position in either of the inputs which are all unbiased.
* (4) In fact, for *every* bit position, there are pairs of seeds for which that bit position is biased in the XOR result, and for every pair of seeds, there are (at least 5) bit positions that are biased in the XOR result.
* (5) The period of the entire sequence of 15-bit values in the XOR result is either 1 or $2^{14}$, compared to $2^{15}$ for the originals.

None of (3),(4),(5) is obvious, but they are all easily verifiable.

---

Finally, let's consider re-introducing the prohibition of PRNGs from the same family. The problem here, I think, is that it's never really clear whether two PRNGs are "from the same family", until/unless someone starts using the XOR and notices (or an attacker notices) things got worse in the sense of (1) and (2), i.e. until non-random patterns in the output cross the threshold from not-noticed to noticed/embarrassing/disastrous, and at that point it's too late.

I'm alarmed by other answers here which give unqualified advice "XOR can't hurt" on the basis of theoretical measures which appear to me to do a poor job of modelling what most people consider to be "good" and "bad" about PRNGs in real life. That advice is contradicted by clear and blatant examples in which XOR makes things worse, such the rand() example given above. While it's conceivable that relatively "strong" PRNGs could consistently display the opposite behavior when XORed to that of the toy PRNG that was rand(), thereby making XOR a good idea for them, I've seen no evidence in that direction, theoretical or empirical, so it seems unreasonable to me to assume that happens.

Personally, having been bitten by surprise by XORing rand()s in my youth, and by countless other assorted surprise correlations throughout my life, I have little reason to think the outcome will be different if I try similar tactics again. That is why I, personally, would be very reluctant to XOR together multiple PRNGs unless very extensive analysis and vetting has been done to give me some confidence that it might be safe to do so for the particular RNGs in question. As a potential cure for when I have low confidence in one or more of the individual PRNGs, XORing them is unlikely to increase my confidence, so I'm unlikely to use it for such a purpose. I imagine the answer to your question is that this is a widely held sentiment.

# Answer
> 0 votes
*DISCLAIMER: This answer is strictly about "We are we not doing it" and not "here's mathematical proof why it can or can't work". I don't claim that XOR introduces (or not) any cryptographic vulnerabilities. My point is only that experience shows us that even simplest schemes almost always introduce unforeseen consequences - and this is why we avoid them.*

"Randomness" is just a tip of the iceberg when it comes to RNGs and PRNGs. There are other qualities that are important, eg uniformity.

Imagine a common dice which is quite good RNG on it's own. But now let's say you need a 1-5 range instead of 1-6. First thing that comes to mind is to simply erase the 6 face and replace it with an extra 1. The "randomness" remains (results are still truly random), however uniformity suffers greatly: now 1 is twice as likely as other outcomes.

Combining results from multiple RNGs is a similarly slippery slope. Eg. simple adding 2 dice throws completely wipes out any uniformity, as "7" is now 6 times more likely than "2" or "12". I agree that XOR looks better than addition at first glance, but in PRNGs nothing turns out as it looks at first glance.

This is why we tend to stick to known implementations - because someone spent loads of time and money into researching them and all the shortcomings are well known, understood and can be worked around. When you roll out your own, you potentially create vulnerabilities and you should put in similar effort to prove it. As the dice addition example shows, combining can be not much different from creating a new one from scratch.

Security is a chain, as strong as it's weakest component. A rule of thumb in security: **whenever you combine 2 things, you usually get a sum of flaws, not a sum of strengths.**

---
Tags: pseudo-random-generators, random-number-generator
---


# Question
Title: How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?
I have to prove that if L \<=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP.

I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N that decides L1. Then I tried to build a NTM NN that accepts when both D and N accept on some input w.

Now,did I really prove that intersection between L1 and L2 is in NP by constructing NTM NN? Thx in advance

# Answer
You can prove something more, intersection of two NP languages is also in NP.

Suppose you have polynomial time non-deterministic turing machines $M\_1$ for $L\_1$ and $M\_2$ for $L\_2$. We can modify $M\_1$ as follows: Whenever any non-deterministic thread of $M\_1$ accepts input string, say $w$, we run $M\_2$ on $w$, if $M\_2$ then accepts $w$, accept the input, otherwise reject.

The resulting machine is polynomial time non-deterministic.
> 1 votes

---
Tags: complexity-theory, turing-machines, np
---


# Question
Title: Both shared-memory and distributed-memory
As you see in the following picture its a shared-memory architecture which has been modeled in a form of **complete graph**. Why we can consider the following architecture (which is a complete graph) **both** as **shared-memory** and **distributed-memory** architecture?

I know it seems to be an distributed-memory architecture but can we say that if we consider local memory of one of the processor as shared-memory for other ones(I mean the shared-memory is located in one of the processor) then we can consider it as shared-memory architecture not distributed?

# Answer
A couple of points, but in general the diagram doesn't provide enough information to make any real conclusions.

First, this isn't the typical layout for shared memory architecture. Typically shared memory architecture has a single, shared bank of memory that all processors access. This diagram does not show that type of architecture.

See here:

Second (with regard to not having enough information), the memory isn't shown in this diagram. We don't know whether the processors are accessing memory directly, or just communicating with other processors who in effect access their own private memory. In this case this would be distributed memory architecture. In another case, where a single address space is shared for access to all memory, then this would be distributed shared memory architecture.
> 3 votes

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


# Question
Title: Computing losing positions in modified Wythoff's game efficiently
> Wythoff's game is as follows: there are two players $A$ and $B$ ( $A$ being the first player ) and there are $2$ piles of stones. When his turn a player can remove one or more stones from anyone pile or same number of stones from both the piles. A player unable to make a move loses. Also it is assumed that both the players play optimally.

As mentioned in the link the losing configurations $(n\_k,m\_k)$ ( $n\_k$ stones in one pile and $m\_k$ stones in another ) are given by $$ n\_k = \lfloor( k\*\phi) \rfloor$$ $$ m\_k = \lfloor( k\*\phi^2) \rfloor$$ where $k$ is any natural number ( and $n\_k \le m\_k$ ) and $\phi=\frac{1+\sqrt{5}}{2}$. For example $\\{1,2\\}$ ( two stones in one pile and one stone in another ) is a losing position.

**Modification to Wythoff's game"**

In this modified game instead of ${\it2}$ piles there are ${\it 3}$ piles. And when his turn a player can move one or more stones from anyone pile or same number of stones from any $2$ piles or same number of stones from all the $3$ piles.
How do I compute the losing positions for this modified game efficiently ? The inefficient way of course is to find the grundy number of each configuration $\\{a,b,c\\}$. This method is inefficient because I want to calculate number of losing positions given that number of stones in each pile can be between $1$ and $1000$.

This is a project Euler question ( stone game ). I would appreciate hints only.

# Answer
There is no closed form for $n=3$ piles. But one can solve the question efficiently using dynamic programming.
> 0 votes

---
Tags: number-theory, game-theory
---


# Question
Title: Are all pseudo-random number generators ultimately periodic?
Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end?

By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence...

And pseudo-random means algorithmic/mathematical generation of random numbers...

# Answer
All pseudorandom generators that don't rely on outside randomness *and use a bounded amount of memory* are necessarily ultimately periodic since they have finite state. You can think of them as huge deterministic finite automata which have special "output" states in which they give their output. All finite automata are eventually periodic, and so all pseudorandom generators produce eventually periodic output.

However, the period length can be enormous. For example, a PRNG with a cryptographic state of 128 bits might only cycle once every $2^{128}$ bits of output, and so even if outputting one bit every nanosecond, the solar system will be dead ere the PRNG repeats.

If the PRNG is allowed to use an unbounded amount of memory (which isn't realistic) then it can, for example, output the binary expansion of $\sqrt{2}$, which we know isn't eventually periodic (since $\sqrt{2}$ is irrational).
> 39 votes

# Answer
PRNGs are state-machines. If they're based only in internal input (in contrast to Poker Stars RNG which is a combination of hardware and software, seeding itself continuously from... sound samples) you'll get (C, S1,...) where C is the current (or previous) value and S1,... could be a set of states:

If there are possible N values (since the memory is bounded) of C and you iterate N+1 times, you will hit the same value for C at least twice. If you iterate 2N+1 times, you will hit the same value for C at least 3 times.

Let T = (Ct, S1t, S2t) be a certain state (current value and other states).
Let M = #{values for S1}X{values for S2}X{...} be the cardinal of possible states combinations (again: since the memory is bounded).

If you iterate NM+1 times the algoritm, you'll reach at least twice the same state (Ct, S1t, S2t, ...), thus generating the same output value and the same following state sequence than the first time, and so becoming periodic.
> 7 votes

# Answer
Simple example of pseudo-random sequence that is not periodic: concatenate together the binary representations of all positive integers, in order:

```
110111001011101111000...

```

(Prepend a "." and it's called the binary Champernowne constant.)

Of course this isn't very high quality as far as pseudo-random sequences go, but it demonstrates that it's possible without using much memory.

In this example, the memory needed to store the state is theoretically unbounded; however it grows very slowly (compared to, say, the memory needed to compute digits of $\pi$ or of $\sqrt{2}$). Likewise for the time needed to generate each bit.

The unbounded memory requirement isn't a problem for a turing machine, and it's probably not a problem in practice, either, since the growth is so slow, but it depends on what you intend to use this thing for.

For instance, if all you're doing is actually generating bits in sequence, then you can easily generate arbitrarily many bits of this aperiodic sequence, on a real computer, without ever running out of memory in the lifetime of the universe. However for that use case aperiodicity has no advantage over simply having a very large period such as $2^{128}$, which won't be reached in the lifetime of the universe either. So, not much difference from the point of view of "normal" usage.

The differentiator, I suppose, is if you want to do things like derive other PRNGs from your PRNG, say by taking a subsequence at regular intervals. If you start with the aperiodic PRNG, you'll get an aperiodic result no matter what period you sample at, whereas if you start with a PRNG of period $2^{128}$, you'll start running into trouble if the sampling period is sufficiently large.
> 6 votes

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


# Question
Title: reinforcement learning in gridworld with subgoals
Andrew Ng, Daishi Harada, Stuart Russell published a conference paper entitled *Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping*.

There is a specific example there that I am extremely curious/interested about. It is in Figure 2(a) of the paper:

It is about a 5x5 gridworld with start and goal states in opposite corners. The catch is, the agent must learn to go from start to end BY VISITING specific subgoals 1,2,3,4 IN ORDER.

Has anyone seen/understood the code for this? I want to know how the reward function/shaping is given in this kind of problem.

I am interested to know how the flow of this modification to the grid world is written.

# Answer
> 0 votes
The subgoals are encoded in external rules to determine if a reward is given and in what amount. The creation of the rules and the used features is done manually by experts. There is no algorithm which calculates the reward function by itself.

---
Tags: machine-learning, reinforcement-learning
---


title: ordered uniform distribution

text:
# Question
Title: ordered uniform distribution
We are given $n$ objects with individual weights $w\_1 , w\_2 , \ldots , w\_n$ and $m$ buckets in which these objects are to be inserted but in order. Here order means if object $i$ goes in bucket $m\_i$ and if object $j$ goes in bucket $m\_j$ then if $i \< j$ then $m\_i \le m\_j$. Objective of the problem is the minimize the weight (sum of weight of objects in the bucket) of the bucket which has the maximum weight (amongst all buckets) in such a distribution.

# Answer
Here is a solution for the *decision version* of your problem, where you give all bins a maximum total weight they can hold.

You go through your objects in order and assign them to the bins. There is no reason to move one object to the next bin if it fits into the actual bin. So always fill the current bin as much as possible before go over to the next bin. This greedy strategy will always be optimal.

You can now turn your decision problem into an optimization problem. For example with the technique called **parametric search**.
> 0 votes

---
Tags: algorithms, optimization, mathematical-programming, packing
---


# Question
Title: Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)
I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says:

> For all ε \> 0, DTIME(O(n)) = DTIME( (1+ε) n).

Now I'm confused with this corollary and Rosenberg's result (p87 in the same book):

> DTIME(n) ≠ DTIME(2n).

Why can we not use the corollary to show that DTIME(n) = DTIME(2n)?

# Answer
$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for *some* constant implicit in $O$, in other words, it is the *union* of the $\mathrm{DTIME}(cn)$ for all $c\>0$. That this union is, in fact, equal to $\mathrm{DTIME}(cn)$ for *any* given $c\>1$ (i.e., $1+\varepsilon$) means that all the $\mathrm{DTIME}(cn)$ for $c\>1$ are equal, it does not say anything about $\mathrm{DTIME}(n)$, so there is no contradiction with the fact that $\mathrm{DTIME}(n)\neq \mathrm{DTIME}(2n)$ (although the results could have been stated in a clearer way).
> 10 votes

# Answer
In a purely mathematical sense, if n = 0, than DTIME(n) DOES = DTIME(2n), because 0 multiplied by any number = 0. So, if n = 0, DTIME(n) = DTIME(2n).

I dont know if this helps, but I hope it does.
> -2 votes

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


# Question
Title: Is a PDA's stack size linear bounded in input size?
I was thinking as follows: At each step, a PDA can put arbitrary many symbols onto the stack. But this number is constant for every individual PDA, so it can't be more than, say, $k$ symbols per step. Using only regular transitions, the stack can rise to maximally (more or less) $kn$ symbols in a run on an input sized $n$.

But what about $\epsilon$-transitions? Is there a simple argument why their maximum number should as well be independent of the input size?

So, in short: Is a PDA's stack size linear in the input size?

# Answer
> 4 votes
No. In NPDAs, you can have cycles of $\varepsilon$-transitions that add symbols to the stack. Thus the stack content can be unbounded.

Proving that CFL ⊆ CSL via automata is tough; the trusted route via grammars seems advised.

---
Tags: automata, pushdown-automata
---


# Question
Title: Longest path in a cyclic, directed and weighted graph
I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights.

In my research so far I have found out that you need to generate `-G` from graph `G` and then run a shortest path algorithm on it to find the longest path in `G`. Of course this won't work if `-G` contains negative cycles. But that's excatly what I need to do. Consider following graph (which I created quickly in paint..):

The red letters are just there for identification. The red numbers are the value of the vertex and the blue numbers are the edge weights. The edge weights are generated with the following formula:

$$ Weight = \frac{destination}{source} $$

I am looking for the longest path from `A` to `F` \- but the longest **simple** path. That means that a vertex must not be visited more than once. By simply looking at it I can see that it is `A - B - E - F`. But if I tried to generate `-G` and then run the Bellman-Ford algorithm on it it would fail because there would be negative cycles like `B - E - D - B`.

I am aware that it is not possible if you look for paths in which a vertex can be visited more than once. But if you look for simple paths only, is it still not possible?

# Answer
> 3 votes
Longest Path is NP-hard; the reduction from Hamiltonian Path is almost trivial.

That means that we do not know any algorithm with even polynomial running-time. You have to compromise.

Of course, the problem is easier for special classes of graphs, for instance both undirected and directed acyclic graphs.

---
Tags: algorithms, graphs
---


# Question
Title: Is it possible to entangle more than 2 qubits? If so, is it useful?
With 2 qubits, there are 4 ways to entangle the qubits - the four maximally entangled two-qubit Bell states, of which one is $1/\sqrt{2}(|00\rangle + |11\rangle)$.

Is it possible to entangle more than two qubits together? If so, is there any practical use to doing so?

# Answer
> 3 votes
Ok, entanglement just clicked for me and totally makes sense.

Yes it is completely possible to entangle more than two qubits!

Entanglement is a fancy word with a really simple meaning.

In quantum computing, you can modify the probabilities of values being read.

If you have two qubits, normally there is some probability for each of the possible states: reading a 0 for each qubit, reading a 1 for each qubit, reading a 0 for qubit a and a 1 for qubit b, and reading a 1 for qubit a and a 0 for qubit b.

When you modify probabilities such that any of these probabilities drop to zero, it limits the possibilities of what can happen when you measure the qubits.

Most specifically, in the two qubit case, you could eliminate the situations where they disagree (states $|01\rangle$ and $|10\rangle$), and make it a 50/50 chance between the states of them both being on, or both being off.

Now, they have NO CHANCE of disagreeing when you read their values.

Who knows how reality "implements" this situation, since distance doesn't matter, but there you go... it's pretty darn simple.

A very simple 3 qubit entanglement would be this: $|000\rangle$, or this: $1/\sqrt{2}(|000\rangle + |111\rangle)$

# Answer
> 1 votes
Shor gave a pretty good and short introduction to quantum computation in his 1996 paper, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.

> Consider a system with n components, each of which can have two states. Whereas in classical physics, a complete description of the state of this system requires only n bits, in quantum physics, a complete description of the state of this system requires $2^n − 1$ complex numbers. To be more precise, the state of the quantum system is a point in a $2^n$-dimensional vector space. For each of the $2^n$ possible classical positions of the components, there is a basis state of this vector space which we represent, for example, by $|011 · · · 0\rangle$ meaning that the first bit is 0, the second bit is 1, and so on. Here, the ket notation $|x\rangle$ means that x is a (pure) quantum state.

The idea of quantum computation is that it is done on qubits that are entangled (hence the state of the quantum system is a point in a $2^n$-dimensional vector space).

You'd probably also find Richard Jozsa's 1997 paper, Entanglement and Quantum Computation interesting:

> **Abstract**: We argue that entanglement is the essential non-classical ingredient which provides the computational speed-up in quantum algorithms as compared to algorithms based on the processes of classical physics.

Here is an extract from it

> All of the quantum algorithms utilise the process of computation by quantum parallelism \[8\]. This refers to a quantum computer’s capability to carry out many computations simultaneously in superposition if the input is set up in a suitable superposition of classically distinct inputs. Thus one might conclude that it is superposition that is at the root of the quantum computational speedup. However closer examination will show that entanglement is the essential feature rather than just superposition itself. Note that entanglement may be viewed as a special kind of superposition – superposition in the presence of a product structure on the state space – which arises from the system being made up of several subsystems. In our considerations these are the qubits comprising the computer. An entangled state is then a superposition of product states which cannot be expressed as a single product state.

# Answer
> 1 votes
Yes, you can entangle any number of qubits. The classic example is the generalised GHZ (Greenberger–Horne–Zeilinger) state which is given by: $$\frac{|0^n \rangle + |1^n\rangle}{\sqrt{2}}$$

As for applications, an interesting application is in Quantum Secret Sharing.

---
Tags: quantum-computing
---


# Question
Title: What happens to quantum algorithms such as BB84 if P=NP
Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible).

The BB84 algorithm is based on the idea that by observing a quantum state, one has to (in quantum theory) disturb that state. This makes them efficient against eavesdropping.

Are quantum algorithms based on BB84 also subject to the hypothesis that P=NP? Or do they remain unaffected by the hypothesis?

# Answer
BB84 is simply a key exchange procedure. This procedure remains secure unless someone can figure out how to observe a quantum phenomenon without changing it, whether or not $P=NP$ will not change this. If the vulnerability of the algorithm was in key transmission, then it is safe if it uses BB84. If it is however somewhere else in the algorithm, then no matter how the key is transmitted it will be vulnerable. So really it depends on the algorithm and the exposed vulnerability. Most algorithms that could be broken by a drastic reduction in run time however are public key algorithms, private key algorithms are much more secure, however the key exchange is the risky part and usually uses some form of public key based encryption. With BB84 however the key exchange becomes relatively safe. So for the most part, the algorithms that would use BB84 are not vulnerable unless the key can be discovered, which requires breaking BB84 and therefor changing the modern understanding of physics. Unfortunately the infrastructure is not yet in place for BB84 to be realistically implemented.
> 4 votes

# Answer
BB84 is *unconditionally secure* under the assumed threat model. This means that no assumption is made on the computational power of your adversary and therefore it is irrelevant whether P=NP or not.

Of course, implementing the protocol on actual hardware brings all sorts of other difficulties and vulnerabilities, but in the idealised mathematical model it is not breakable.

To contrast this with the classical case - classical key distribution can attain at best *computational security*, which means that your adversary is guaranteed to recover the key, but he may be under a severe computational disadvantage and thus would need a lot of time to do it.
> 2 votes

---
Tags: complexity-theory, cryptography, quantum-computing, p-vs-np
---


# Question
Title: Generally, does the time it takes to compute (n mod m) depend on the size of n?
Example: Suppose I have a number *a* with 100 decimal digits, *b* with 200 decimal digits, and *m* with 10 decimal digits.

Would the speed of the computation *a mod m* vary greatly from *b mod m* because of the size of *a* vs *b*?

# Answer
> 2 votes
Yes. You are doing long division. Whatever method you use, you will lose you a roughly constant number of digits per step, so there will be twice as many (well, about $\frac{190}{90}$ times as many) steps for $b$ as for $a$.

# Answer
> 0 votes
In general it does, however, for certain special cases it will not.

A simple example is when $m$ is a power of 2. Then, the reminder is exactly the last $\log m$ bits of $n$, regardless of the size of $n$.

---
Tags: algorithm-analysis, runtime-analysis, arithmetic
---


title: Linearity of Expectation

text:
# Question
Title: Linearity of Expectation
I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set cover problem.

One of the problem set questions is a basic probability question and is as follows:

You ask ten of your friends to give you one dollar (coin) each so that you can buy your favourite pizza.

When you reach the pizza place you realize that it's closed. So you return the coins to your friends by giving each of them a random coin.

1) How likely is that each of them gets the coin they put back?

2) How many of them will get in expectation the coin they put back? (Try to prove this elegantly using techniques discussed in the course)Define the random variables you use.

3) Now suppose that you take one coin to buy a coffee somewhere else. You redistribute the others dollar coins giving each of your friends one coin chosen uniformly at random. How many of your friends will get in expectation the coin they put back?

I've solved the first two parts and I'm thinking for the third part that I should define a random variable Xi that represents whether or not persion i get the coin back that she put in and E\[Xi\] is the probability that she gets it back.

The probability that she gets it back is 9 / 10 * 1 / 10 = 9 / 100. There's a 9 / 10 chance that her coin was not the coin that I bought coffee with and a 1 / 10 chance that she picks her coin or is left out as there are 9 coins for 10 remaining people.

Taking X as the number of folks that get their coins back I have

E\[X\] = sum(E\[Xi\]) over all persons E\[X\] = 90 / 100 = .9 people are expected to get their coin back.

Is my reasoning sound here? If not, can somebody show me the error of my ways?

Thanks so much,

Stead

# Answer
Your approach looks good. Let's just write it clearly. Let's look at $E\[X\_1\]$.

With probability $1/10$ the first coin was used to buy the coffee, thus the value is $X\_1=0$.

With probability $9/10$ we are back in the situation of part II (we can add a new "Gold" coin - the party that gets this coin will not get his dollar back), so the expectation of this case is just like in Part II.

Adding both cases (with the appropriate weight) should solve your question, for $X\_1$, and by the linearity of expectations, and since all parties are symmetric, the answer is $10 E\[X\_1\]$.
> 0 votes

---
Tags: algorithm-analysis
---


# Question
Title: Are there specific rules for programming languages applicable to Quantum Computers?
What would be the requirements for programming languages that are used for quantum computers? Do standard procedural languages with their constructs be sufficient, and succinctly capture the computing capabilities of a Quantum Computer? To illustrate, languages such as Assembler would most likely be closest to the hardware, and the programmer programs to the Assemblers' specifications. **CSP** is an example of specification for concurrent processes. Are there any formalisms such as **CSP** for quantum computers, or even languages such as Assembly for quantum computers?

# Answer
> 2 votes
We probably don't yet know enough about the landscape of practical quantum computing devices to lay down the kinds of concrete specifications you're asking for. It also seems to me that there's a big gap between what Assembly Languages and a formalism like CSP brings to the table. So, this question probably has different answers at different levels of hardware and software abstraction.

What all that being said, "A Layered Software Architecture for Quantum Computing Design Tools" by Svore et. al lays out a framework that I believe cuts across what you're getting it. It's simply a proposal though, not a specification per se. The authors do lay out some of the challenges faced when designing quantum computing design tools and programming languages and I think address what you're looking for. The previously mentioned Liquid language seems to be an an attempt and working off this framework.

From what I've seen, quantum programming systems typically to work by providing a universal set of elementary gates for quantum circuits and possibly some higher-level primitives for common quantum algorithm components like the Quantum Fourier Transform. I believe Svore, et. al. refer to this layer as Quantum Assembly. For example, the two-qubit CNot gate and arbitrary single qubit unitaries are universal for quantum computation. The ability to lay out circuits from these primitives would provide you with the ability to express an arbitrary quantum computation.

I'd hesitate to call this assembly in the sense that we know it from classical computing as it corresponds to a set of primitives from a low-level abstract model of quantum computation and not to an abstract or concrete instruction set. Going back to my first comment, it's not clear that we're even sure what kind of quantum instruction set is best at this point.

# Answer
> 2 votes
In terms of the general requirements that a quantum programming language should satisfy, I recommend reading the excellent paper Quantum Computation: from a Programmer's Perspective by Valiron.

The current state of the art for quantum programming languages is Quipper. Its website has plenty of information about it including popular news articles, research papers, documentation and even video. I recommend reading Programming the quantum future.

In the next few years there will be some very exciting developments surrounding Quipper. There is a big research project funded by the US Department of Defense which is aiming to extend Quipper with a dependent type system and in addition there will be work on developing quantum domain theory with the goal of providing Quipper with a denotational semantics and even more!

---
Tags: programming-languages, quantum-computing
---