# Question
Title: Please explain linear programming as seen for this load balancing problem
I have at hand a linear program related to load balancing. However I have no idea what this is and wikipedia gives me something too simplified/abstract to be useful.

I wonder if someone can explain the basic lingo used in the formulation of the linear program. The goal of the program is of course to introduce the maximum amount of load capable on the lightest loaded machine.

Let

* $p\_i$ be load of processor $i$
* $L$ be our load to be distributed
* $x\_i$ be the fraction of load $L$ distributed to processor $i$
* $\gamma$ be the minimum of final load after distribution of $L$

Then solve:

$$max\_{x,\gamma} \gamma$$

subject to $\gamma \underline 1 \leq p + xL$, $\underline 1'x = 1, x \geq 0$, $\underline 1$ is the one vector

Some confusions:

* How do you physically characterize the load of a processor, is it equivalent to CPU utilization? i.e. what can I do to find out what the load of my processor is currently having
* How is the fraction of load $L$ to be distributed determined?
* If $\gamma$ is the minimum final load after L, then why do we maximize it? wouldn't that be equivalent to maximize the left over work to be done?

# Answer
> 3 votes
> How do you physically characterize the load of a processor, is it equivalent to CPU utilization?

The program is modelling load like this. Whether you feel it's a good way to model load, and whether you can think of any real version of load that works like this is a separate issue.

You are running a storage facility for water. The key "facts" about water are:

1. It's just water and all water is the same. If I ask you to store a litre of water for me and I come back for it a week later, I don't care if you give me back exactly the same molecules of water: I just want you to give me a litre of water. (Economists call a substance with this property "fungible".)
2. Water is infinitely subdivisible. If I give you a litre of water, you can split it into any number of smaller quantities, without restriction. (Atoms? Shmatoms!)

OK. In your water storage facility, you have $n$ tanks, each of which can hold an unbounded amount of water (you were sure you only needed one such tank, but the TankCorp salesman was very persuasive). At any particular time, the $i$th tank contains $p\_i$ litres of water. A new customer has just arrived with $L$ litres and you need to decide if you can store that and, if so, what is the best way of doing that.

You'll put $x\_i$ litres of water in each of your tanks. You can choose the value of each $x\_i$ however you want but, if you accept the customer, you must store all of his water, which means you must have $\sum\_i x\_i = L$. Also, TankCorp tanks do occasionally burst so you want to fill the tanks as evenly as possible so that, if a tank does burst, you know it won't be a super-full one: you want the loads in the tanks to be balanced. This is achieved by making the emptiest tank as full as possible. Why? Because the total amount of water in all the tanks is fixed so, if one tank has less water in it, you can always make the quantities more equal by taking water from a very full tank and transfering it to the emptiest one.

Your job is to pick values for the $x\_i$ to satisfy these constraints. Note that if, at the start of the day, each of your tanks is empty, then the solution is trivial: you just set $x\_i = L/n$ for each $i$ and each tank contains the same amount of water.

OK, that's the model. You can use it to represent any kind of load that resembles the idealized water I described: it must be arbitrarily subdivisible (you can split it between your servers however you want) and fungible (your client don't care which server does any fraction of the work). Literally speaking, that's nothing at all, but we can get a good approximation if we replace "infinitely subdivisible" by "subdivisible a lot". For example, suppose you're running a web server cluster. You can't literally divide a burst of a thousand requests between the machines in your cluster in *any* fraction ("I'll do 4.7 requests on server 1, ...") you want but you can divide it into any number of thousandths, which is close enough.

> i.e. what can I do to find out what the load of my processor is currently having?

I'm not sure what you mean. This isn't a system for measuring load, it's a system for assigning fractions of jobs to servers so that each server will have about the same load.

> How is the fraction of load $L$ to be distributed determined?

By solving the program! (I.e., choosing values for the $x\_i$ that satisfy the constraints.)

> If $\gamma$ is the minimum final load after $L$, then why do we maximize it? Wouldn't that be equivalent to maximize the left over work to be done?

No, because the total work to be done is fixed. Maximizing the least-busy server means that there's less work for the busiest server to do, so you finish as soon as possible.

---
Tags: terminology, linear-programming, modelling
---


# Question
Title: If the list lengths are m and n, why does the merge take O(m+n) operations?
If I have two sorted lists.

```
list A => 1 -> 2 -> 4 -> 11 -> 31
list B => 2 -> 31 -> 54

```

Now what should be the order of (sorted) merge and why?

According to the rule, If the list lengths are m and n, the merge takes $O(m+n)$ operations, the order should be $O(5 + 3)$. Am I right?

I would appreciate if someone help me out in understanding it.

# Answer
You are asking:

> Now what should be the order of merge and why?

First of all, we need to fix the merging algorithm. I'll assume the canonical one, i.e.

```
merge(A, B) {
  if ( A.size == 0 ) {
    return B
  }
  if ( B.size == 0 ) {
    return A
  }

  if ( A.head <= B.head ) {
    return A.head + merge(A.tail, B)
  }
  else {
    return B.head + merge(A, B.tail)
  }
}

```

Now you propose two lists:

```
A = 1 -> 2 -> 4 -> 11 -> 31
B = 2 -> 31 -> 54

```

So just execute the algorithm and count operations! I'll assume that you only want to count the comparison `A.head <= B.head`. A compacted trace of the algorithm is (unfolding the recursion)

```
C =
A = 1 -> 2 -> 4 -> 11 -> 31
B = 2 -> 31 -> 54

C = 1
A = 2 -> 4 -> 11 -> 31
B = 2 -> 31 -> 54

C = 1 -> 2
A = 4 -> 11 -> 31
B = 2 -> 31 -> 54

C = 1 -> 2 -> 2
A = 4 -> 11 -> 31
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4
A = 11 -> 31
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4 -> 11
A = 31
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4 -> 11 -> 31
A =
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4 -> 11 -> 31 -> 31 -> 54
A =
B =

```

So you see it took seven recursive calls (plus the main call), and six comparisons. You can easily swap the parameters and do the same; you'll get seven comparisons. So the order you have is slightly better. Do you see why?

> It's advantageous if one of the lists runs empty early.

Note that the order of comparison and whether you use `<=` or `<` is crucial here; other choices may make the other order better.

Having worked through this example, you are ready to think about what the worst case inputs are.

> Two lists of length $m$ and $n$ that run empty at the same time.

And then you execute the algorithm symbolically and count the number of steps necessary.

> If you can never append more than one element when the other list is empty (`return A` resp. `return B`), you had to have had $n + m - 1$ recursive calls up to that point, one for each element, since you only ever pick *one* element per recursive call. Plus the last call, that's a total of n+m recursive calls.
> Since every call *does* merge at least one element, there can be no more than $n+m$ recursive calls, so this is indeed the worst case.

Now you observe that each recursive call takes time $O(1)$, assuming a suitable list representation (in particular with $O(1)$-time `size`), and you are done.

This is not rocket science, by the way; it's rater mechanic, in fact, as our reference question explains. As an exercise, you can carry over the analysis to a more typical iterative implementation of `merge`.
> 6 votes

# Answer
O(5+3) technically is same as O(1).

What that means is that given a list of 5 elements and another containing 3 elements, they can be merged in constant time.

This is because the input size is a constant (viz. 8).

Even if you were to merge two lists of size million each, the time complexity of the resulting algorithm would still be O(1). This is because the input size is a constant.

The big O notation is helpful only when you are interested to know how the time complexity of algorithm varies with varying input size.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, linked-lists
---


# Question
Title: Why does a color video compress better than a black and white video?
It was asked in an exam why a color video compress better than a black and white (grayscale) video using MPEG but can't find anything explaining it.

In other words, we would apparently get a better compression ratio when compressing color videos than when compressing BW videos.

# Answer
Human eye is very sensitive to luminance change and order of magnitude less sensitive to chrominance change.
MPEG under the hood is based on JPEG transform, so you have 8x8 blocks of DCT.
It blurs a bit the whole block approximating it. Colour space changes to YUV or YCbCr, to encode two channels of colour and one of luminance.
Luminance (grayscale if it was colour) is not compressed as much as new created two colours. These colours are fitted more loosely than luminance.
The most heavy tricks are in colour space and luminance is preserved with lower compression (and less stages).

If you have BW frame it cannot be dealt with high compression as this faster degrades quality. MPEG was not created to deal with BW data. Origins of this codec are from times when grayscale tv was appended colour on top of existing frame.
Here I mean origins, not the same scheme as bandwidth was smaller at this time, I am referring to colour space and compression over chrominance.

MPEG popular scheme is 4:2:2 which encodes four parts of luminance (BW) and two times two colour parts. Colour is encoded as differences, because there are two channels and three colours.
So simply 50% of data is well preserved luminance and 50% are three colours with higher compression ratio. Compressed better means greater ratio of original vs processed channel.
Luminance takes (taking it simple as luminance is part of these colours) roughly equal space as colour info.

Different codecs are using different strategies, I referred to MPEG, not some new mixed schemes.
> 8 votes

---
Tags: algorithms, image-processing, data-compression, video
---


title: Why does this sort algorithm work?

text:
# Question
Title: Why does this sort algorithm work?
The following O(n^2) sorting algorithm works but I can't figure out why.

```
array a // length n, indexed 0 to n-1

for ( i = 0; i < n; i++)
   for ( j = 0; j < n; j++)
       if(a[i]<=a[j])
            swap(a[i],a[j]);

```

It seems it is not bubble sort as after a single iteration neither the minimum or maximum is in place. (And also it needs n^2 comparisons instead of n\*(n-1)/2)

How would you prove this algorithm sorts ? How is this sort algorithm called?

An execution of the sort for the example :

```
initial target
194600925
592040703
20865352
814014281
792862803

target after iteration 0
814014281
194600925
20865352
592040703
792862803

target after iteration 1
194600925
814014281
20865352
592040703
792862803

target after iteration 2
20865352
194600925
814014281
592040703
792862803

target after iteration 3
20865352
194600925
592040703
814014281
792862803

target after iteration 4
20865352
194600925
592040703
792862803
814014281

```

# Answer
It is a variant of bubble sort, however the endpoints of the array shift throughout the progress of the algorithm.

In particular it maintains the following invariant:

> at the end of the $i$-th iteration, the elements in indices $1..i$ are sorted.

At the first step it finds the maximal element and puts it in index 1. (prefix length =1). Then, at every iteration $i$ it adds the element in position $i$ to the prefix, and performs a (degenerate) bubble sort on the first $i$ indices. This bubble sort takes only one step since except for the one new element, the other $i-1$ elements are already sorted. The maximal element will now be at position $i$. The length of the sorted prefix keeps increasing at every iteration until the entire array is sorted.

I don't know if this sorting approach has a name. It looks like a type of insertion sort.
> 12 votes

# Answer
Let the array $a$ be indexed from $0$ to $n-1$ with elements $a\[0\]a\[1\]...a\[n-1\]$.

What the *for loop* does : Starting from index $0$ to $n-1$, for every such index $i$ it traverses the whole array from index $0$ to $n-1$ and during traversal it swaps the current element at index $t$ being traversed with $a\[i\]$ if $a\[i\]\le a\[t\]$ and continues the traversal (with $a\[i\]$ changed).

What is happening :

Iteration for index $0$ : The maximum element comes at index $0$ .

Now the algorithm *behaves* as **insertion sort** for iteration $1$ to $n-1$ but with redundant comparisons during the array traversal for each iteration.

Every comparison after index $i-1$ made during "iteration for index $i$" is redundant since the maximum element should already be at index $i-1$ due to previous iteration resulting in no further swapping in current iteration.
> 6 votes

# Answer
The redundant comparisons cloud the picture. It becomes much more clear what is happening if you focus on just the right portion.

We can ignore any case where i=j, comparing a position to itself doesn't matter.

The first pass with i=0 puts the largest value in a\[0\]. After that each pass will keep moving the largest value into a\[i\]. Any further comparison where j\>i will always fail, because a\[i\] will already be the largest. We can ignore any case where j\>i.

The key is to focus on what's happening when j\<i.

For each pass of i, consider the sublist from a\[0\] to a\[i\].

The first pass, i=0, our sublist is just a\[0\]. The first pass puts the largest element in a\[0\]. A list with just one element is inherently "sorted".

The second pass, i=1, our sublist is a\[0\] to a\[1\]. a\[0\] is the largest value, a\[1\] holds some new value to consider. The new value is always smaller, and always gets swapped to the bottom at a\[0\]. Our sublist a\[0\] to a\[1\] is sorted.

The third pass, i=2, our sublist is a\[0\] to a\[2\]. a\[0\] to a\[1\] is sorted, a\[2\] holds some new value to consider. The smallest value of our sublist is either a\[0\], or the new value at a\[2\]. The smallest value goes into a\[0\]. Then the next smallest value goes into a\[1\]. This pushes the largest value up into a\[2\]. Our sublist a\[0 to 2\] is sorted.

When i=3, the same thing happens. A new value enters the picture a\[3\]. Any values smaller than a\[3\] are left unaffected at the bottom, then a\[3\] gets inserted, and anything larger than a\[3\] gets bumped up one position. The sublist a\[0 to 3\] is now sorted, with the absolutely largest value in a\[3\].

Each pass of i brings in one new value, inserting it to make a sorted sublist from a\[0\] to a\[i\]. The last pass of i brings in the final value, and our sorted sublist fills the entire list.
> 1 votes

---
Tags: algorithms, sorting, correctness-proof
---


# Question
Title: Analysis of sorting Algorithm with probably wrong comparator?
**It is an interesting question from an Interview, I failed it.**

An array has $n$ different elements $\[A\_1, A\_2, \ldots, A\_n\]$ (random order).

We have a comparator $C$, ***but it has a probability p to return correct results.***

Now we use $C$ to implement sorting algorithm (any kind, bubble, quick etc..)

After sorting we have $\[A\_{i\_1}, A\_{i\_2}, \ldots, A\_{i\_n}\]$ **(It could be wrong)**

Now given a number $m$ ($m \< n$), the question is as follows:

1. What is Expectation of size $S$ of Intersection between $\\{A\_1, A\_2, \ldots, A\_m \\}$ and $\\{A\_{i\_1}, A\_{i\_2}, \ldots, A\_{i\_m} \\}$, in other words, what is $E\[S\]$?
2. Any relationship among $m$, $n$ and $p$ ?
3. If we use different sorting algorithm, how will $E\[S\]$ change?

My idea is as follows:

1. When $m=n$, $E\[S\] = n$, **surely**
2. When $m=n-1$, $E\[S\] = n-1+P(A\_n \text{ in } A\_{i\_n})$

I dont know how to complete the answer but I thought it could be solved through induction.. **Any simulation methods would also be fine I think.**

# Answer
> 1 votes
The question seems ill-defined. A faulty/probabilistic comparator will have a radically different impact on different sort algorithms. Each algorithm will have a different, and potentially very complex, analysis.

One possibly interesting note is that you will get exactly reverse sort order when p=0. When p=0.5 the result will be unbiased on ascending vs descending, but the resulting permutations will not be equally likely.

---
Tags: algorithms, combinatorics, sorting, probability-theory, randomized-algorithms
---


title: Why is the star property important

text:
# Question
Title: Why is the star property important
According to the Bell-Lapadula model, write access is only to Subject $S$ on object $O$ provided if: $L(S) \leq L(O)$ where $L$ is the clearance level for $S$ and classification for $O$. This seams counter intuitive. Are there any attacks that this protects against and what other benefits are presented by it?

# Answer
This equation expresses a **confidentiality** property. There are two ways of looking at it: what does it permit and what does it prevent.

* **Prevented**: writing secure information to an insecure place.
* **Permitted**: writing insecure information to a secure place.

Clearly, the former is good, otherwise, for example, your PIN number (secure) could become accessible to untrusted third parties.

From a security perspective, the former is safe, because no secure information is leaked. It allows cases such as where you report your daily activities (insecure) to your manager (trusted).

One concern you may have is that writing insecure information to a secure place could lead to problems. These problems would be related to **integrity**. An integrity violation occurs when bad data from an untrusted source is written into a secure variable. If the data isn't checked for validity, it could mess up programs running securely.
> 2 votes

# Answer
If you write the code of the electronic lock of your house under your doormat, it's quite risky : Something which should be only in a secure area, like your memory, is now also in an unsecure area.

But if you write it in your bank safe box, it's ok, because it is at least as difficult to learn the code from this very secure area than from your memory (with torture for instance).
> 0 votes

---
Tags: security
---


# Question
Title: prove that minimal number of comparisons to find median among five elements is 5
I would like to prove that we need at least five comparisons to find median amoung five numbers.

And my proposition: Let's consider tree of comparisons. There are at least $5 \cdot {4\choose 2} = 30$ possiblities, so in our tree we have at least $30$ leaves. So what is minimal height of this tree when we have at least $30$ leaves. (height is number of comparisons).
So $$height \ge \log\_2(30) \> 4$$ Hence, $height \ge 5$.

Is it correct proof ?

# Answer
Your proof is correct. But I don't think 5 comparisons is achievable. Here is the algorithm that finds the median in 6 comparisons.

1. Sort the first two pairs. \[ *2 comparisons*\]
2. Order the pairs w.r.t. their respective larger element. \[ *1 comparison*\]

Call the result $\[a,b,c,d,e\]$; we know $a\<b\<d$ and $c\<d$. Now there are 3 elements less than $d$, hence $d$ can't be the median( i.e. $3^{rd}$element of the sorted array)
3. WLOG say $c\<e$ and $a\<b$ (known already). Order the pairs w.r.t. their respective larger element. WLOG $a\<b\<e$ and $c\<e$. Compare $c$ & $b$, greater one is the median. \[ *3 comparisons* \- 1 for $c$ & $e$, 1 for ordering the pairs and 1 for $b$ & $c$ \]

Hence, total number of comparisons is equal to 6.

Idea taken from here .
> 4 votes

# Answer
The proof is correct as you are calculating lower bound for median of 5 elements. But this is data dependent, so it is not number of compares algorithm needs to find median. This is one of instances.

Unless you are happy to know that there are such cases...

But to derive algorithm that works always you have to compute upper bound on this, to have algorithm (that always works). Minimal number independent of order of elements to find median of five elements is six.

Try it yourself. Take 5 numbers, let it be 1,2,3,4,5, permute them and draw trees of comparisons. In fact there are instances with five compares, but you will find instances of six, and this upper bound is interesting.

You might be also interested in this: http://www.cs.hut.fi/~cessu/selection/
> 1 votes

---
Tags: selection-problem, comparison
---


# Question
Title: Chomsky NF or Greibach NF benefits for LR parser?
Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind:

* total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating action table),
* the size of action/goto table (in total)
* is there any "side-effect" of removing some of shift-reduce conflicts

?

# Answer
> 1 votes
The point of generating a parser (usually) is to *parse*: "Analyse (a string or text) into logical syntactic components" (some online dictionary). That's different from simply recognizing that a text is a member of a language. A given language has a variety of grammars which will recognize its sentences, but typically there is a specific grammar which defines the "logical syntactic components" and their relationship to each other, as in the above definition. In real-world applications -- compilers, for example -- one expects an output which is more interesting than simply "the input is/is not a valid program".

In some cases, it is possible to recover the original parse tree from the parse tree generated by parsing a transformed grammar. (This is true for CNF, with the usual transformation strategy.) In other cases (such as GNF, as far as I know), it is annoyingly difficult, making such a transformation of limited use for parsing (as opposed to recognition).

Also, not all grammar transformations preserve LR(k)-ness. In particular, the usual CNF transformation involves refactoring of every production into a series of rules with precisely two non-terminals. This often has the effect of converting an LR(1) grammar into a grammar which is not LR(k) for any k. So that's not much help, either.

---
Tags: context-free, formal-grammars, parsers, lr-k
---


# Question
Title: Data types for storing arbitrarily much information
I've heard that YouTube had a problem with the view count on Gangnam style since the number of views exceeded the variable byte size.

What's the problem with creating really large variables? Why does it end with `unsigned long`, for example? Can you create bigger and bigger variables to hold more and more bytes? Is there any reason why programmers don't just use a really big variable for everything?

# Answer
Yes, you can create bigger and bigger variables to store big integer. There are many libraries that provide that functionality. For example BigInteger in Java. The problem with using big integer is that it makes program slower as more instructions are required to perform operations such as addition. Moreover, using a bigger representation will consumes more memory.
> 6 votes

# Answer
> What's the problem with creating really large variables?

The problem that it takes space. You need to put this "large large" variable somewhere in your memory. Say there are 81M videos stored on YouTube, multiply this by the amount of bytes you spend on this large-large variable, and you get a huge waste. Almost all the videos (i.e., all but one) can work fine with 4-8 bytes for their watch counter, so why keep 1KB (say) for every watch counter? That's throwing away 81GB of space for no good reason!

Creating a variable-size variable (as suggested in Tushar's answer) is also an option, but then the overhead becomes time. Instead of having a simple register that holds this data, whose handling takes $\ll 10$ clock cycles per operation, a variable-size one may take $\>10$ and even $\>100$ clocks to handle per operation. Why waste this time, when only a small fraction of the vidoes hit the 1B watches?
> 6 votes

# Answer
Look up *arbitrary precision arithmetic*. You can store the "digits" of a number in a variable sized data structure, like a linked list.

Several languages have arbitrary precision integers as their default integer type (Scheme and Mathematica come to mind). Other languages provide arbitrary precision integers through libraries.
> 4 votes

---
Tags: memory-management, arithmetic
---


# Question
Title: Is there a formal CS definition of VCS and file versions?
I don't know whether it was a joke, but once I read what was referred to as a formal definition of a file in a versioning system such as git, hg or svn. It was something like a mathematical object like a homeomorphism. Was that a joke or is there really computer science theory about versioning systems and the mathematics of VCS?

# Answer
You're thinking of a tweet by Isaac Wolkerstorfer (@agnoster):

> git gets easier once you get the basic idea that branches are homeomorphic endofunctors mapping submanifolds of a Hilbert space.

Unfortunately, it's a joke. As the author wrote on Quora:

> It was intended as firmly tongue-in-cheek. I actually love git, and I think its complexity is greatly overblown. At the same time, I'm sympathetic to the fact that advice from git gurus to novices can end up sounding like inscrutable gibberish.
>
> It's not intended to have any deeper meaning. Attempts to analyze it in this fashion should be futile, but due to a bug in reality, you can actually make any sufficiently hand-wavy statement fit if you try hard enough.

This has been discussed on Programmers Stack Exchange and on Mathematics Stack Exchange.

---

Joke aside, there has been work of formalizing version control. One effort that allies theory and practice is the work on **patch theory** by David Roundy on Darcs. The main objective of the theory is to model merging and, in particular, conflict resolution. The Darcs wiki has an introduction to the theory and a few pointers as well as a bibliography (unmaintained so outdated if you want a recent view on the subject, but it does list a 2009 survey paper by Petr Baudiš) and a list of talks (which includes more recent material). There's also a wikibook. One seminal paper is *A Principled Approach to Version Control* by Andres Löh, Wouter Swierstra and Daan Leijen3.

Patch theory does lead to a categorical model, which has been more recently explored in *A Categorical Theory of Patches* by Samuel Mimram and Cinzia Di Giusto and *Homotopical Patch Theory* by Carlo Angiuli, Ed Morehouse, Daniel R. Licata and Robert Harper. In Mimram and Di Giusto's work, the model has files as objects and patches as morphisms. I think that makes merging a branch a functor — an endofunctor if you're working in a single repository. “Homeomorphic endofunctor” doesn't make sense to me. With homotopy theory involved, submanifolds of a Hilbert space might not be so far out...
> 11 votes

# Answer
Of course there is a mathematical formalism for version control systems. There is a mathematical formalism for virtually every algorithm in CS. There are *multiple* formalisms for many. There is not a 1-1 relationship between formalisms and the systems they model. The models can range from simple to complex. Here is an example for VCS/SCM also by Swierstra, not cited yet.

SCM also has a lot of similarities to the concept of "parallel universes/ timelines" and time travel sometimes used in science fiction. It captures the state of the evolving system at different times or "snapshots". There are "branches" and "merges". See also timelines.
> 3 votes

---
Tags: terminology, reference-request
---


title: Page management in OS kernels

text:
# Question
Title: Page management in OS kernels
I looked at some old OS theory books of mine and noticed that one glaring omission in all of these OS books is how to actually keep track of physical pages that are free (i.e. algorithms for actually implementing the free list). I know pretty well how userland memory allocators work, but a big difference with physical page allocation is that fragmentation of physical pages shouldn't be an issue, since the page table can just pick and choose the physical pages without having to care about whether they are contiguous or not. Since avoiding fragmentation is one of the main concerns of userland allocators, it seems like physical page allocation is fundamentally a different problem. I guess that this is not completely accurate if one wants to support superpages to reduce pressure on the TLB.

My question: What are techniques are used in modern high-performance kernels for this problem? Also, does this problem become significantly more complicated in NUMA systems?

# Answer
Page frame management is conceptually very simple; all you really need is a linked list. However, there are two main factors which complicate things:

* DMA. DMA is one of the few things that might need a physical buffer larger than a page in size. In addition, there are legacy devices to contend with; on x86, for example, 32-bit devices can only do DMA from physical addresses below the 4G limit. For ISA it's even worse.
* Cache colouring, which is an extremely important optimisation.

Most operating systems use surprisingly simple techniques.

Windows, for example, just uses a bunch of linked lists (or at least it did, last time anyone said anything about it). It's hard to say since we can't see the source code, but there are probably N\*M linked lists where N is the number of possible states a page can be in (e.g. in-use, free, waiting to be paged out) and M is the number of colours.

Linux famously uses a buddy allocator to manage physical pages, which is only slightly more complicated than a bunch of linked lists when you think about it.

Probably the most sophisticated management scheme that has been documented extensively is that of Solaris. See Bonwick & Adams, *Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources*, USENIX 2001. There is also an extended discussion in the book *Solaris Internals*. The Solaris slab allocator goes to a lot of trouble to avoid lock contention, cache thrashing, and the like, and also can tune its implementation for different data types as needed.

What's interesting is that Solaris uses the same memory allocator to handle page frames that it uses to handle kernel objects, by nesting slab allocators inside slab allocators. The paper is definitely worth a read.
> 5 votes

---
Tags: operating-systems, memory-management, virtual-memory
---


# Question
Title: Which research languages have a stronger typesystem than Haskell and why?
Here I read that:

> Haskell definitely does not have the most advanced type system (not even close if you count research languages) but out of all languages that are actually used in production Haskell is probably at the top.

So I am asking two things:

1. which research languages have more powerful type systems than Haskell;
2. what do they improve.

I am just a programmer, so I don't know many mathematical objects used in type theory, please provide gentle explanations if you can.

# Answer
> 30 votes
The question is somewhat problematic, since it relies on a subjective definition of "better."

Dependently-typed languages such as Agda, Idris, and Coq have a stronger type system than Haskell. This means, you can use the types in these languages to prove strictly more properties about your code than in Haskell. That is, there are more incorrect programs that will be caught.

However, this comes at a price: type inference, and testing whether any values of a given type exist, are no longer possible. This means for these languages, you need to explicitly annotate your code with types. Essentially this boils down to writing your own correctness proofs for your code.

So are these languages "better" than Haskell? They can check advanced proofs of correctness for your code, but they can't automatically prove properties about your code the way Haskell can.

Another research language that is "better" than Haskell is LiquidHaskell. This is basically Haskell with refinement types bolted on top, parsed from special comments.

Refinement types allow you you refine types with properties. For example, instead of having an `Int`, you can specify `{i : Int | i > 0}`, giving the type of all positive integers. Type inference is decidable with refinement types, but you can't prove nearly as many correctness properties with them as you can with dependent types.

There are other refinement type systems out there, but I'm not terribly familiar with any of them.

# Answer
> 10 votes
The ML family of languages (StandardML, OCaml) arise from a similar tradition as Haskell and therefore have similar type systems. They are not exactly the same as Haskell, though, and some of their features might suit you better (there is no such thing as an *objectively better* type system because type systems in programming languages exist to help *humans*). Here are some features of OCaml that Haskell either does not have (but might have a corresponding similar concept), or Haskell does have but done differently:

1. Polymorphic variants.
2. Objects with depth subtyping and classes.
3. Functors, which are maps between modules (Haskell has modules), and even first-class modules

And please, there is no need to turn this into an ML-Haskell shootout, or else I will start linking to Bob Harper's blog posts ;-)

# Answer
> 9 votes
The research language Clean has a better type system than Haskell, because it has uniqueness types. The ideas behind uniqueness types are closely related to linear logic, which is closer to the resource limited "real world" than classical logic.

The anti-research language Rust also has a type system with unique features that are closer to the "real world" than classical pure type systems. Most of the ideas which influenced the type system have been published completely independent of Rust long before it even existed. But the way these old ideas are put together is unique, and would also deserve real research publications, even if known loopholes and inconsistencies exist.

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


# Question
Title: Efficiently partition tree into clusters of similar diameter
I am looking for a way to split a tree into $k$ clusters so that the cluster with largest diameter is as small as possible. All edges have the same length. I'm hoping for an algorithm that can handle arbitrary trees (with arbitrary branching factor), not just binary trees.

# Answer
Your problem is equivalent to the following:

Input: a tree $T$, an integer $r$ (the radius)
Find: a set $S$ of $k$ vertices, such that every vertex in the tree is at distance $\le r$ from one of the vertices in $S$; or failure if no such set exists

Why is this equivalent? Well, if you have such a set $S$, then you immediately can find $k$ clusters of diameter $\le 2r$ (for each $s \in S$, you get a cluster of nodes that are at distance $\le r$ from $s$). Conversely, if you have $k$ clusters of diameter $\le 2r$, then you can find such a set $S$: given a cluster, pick a pair of nodes $x,y$ in the cluster that maximizes $d(x,y)$; then find a shortest path from $x$ to $y$, and let $s$ be a node halfway along that shortest path; then one can prove every node in the cluster is at distance $\le r$ from $s$. So, if you can solve the above problem, then linear search or binary search on $r$ will find the smallest such diameter.

---

The best algorithm I can find for this problem is the trivial $O(n^{k+1})$ algorithm: enumerate all subsets of size $k$, and test each to see whether it satisfies all the requirements. The number of sets you must enumerate is $C(n,k) = O(n^k)$, and given a candidate set you can test whether it is valid in $O(n)$ time. Unfortunately, for modest or large values of $k$, this will be totally impractical.

As an optimization, you can let $S'$ be the set of vertices that are at height $\ge r$. (The height of a vertex $v$ is the length of the longest downward path from $v$ to a leaf; in other words, the height of a leaf is $0$, and the height of an internal node is one more than the height of its highest child.) Then, you only need to enumerate subsets of $S'$ of size $k$. In practice, this might provide a significant improvement, even though asymptotically it might not make much of a difference to the worst-case running time.

I don't know whether it is possible to do better, or whether a polynomial-time algorithm exists. I think the problem can be solved in polynomial time for binary trees using dynamic programming, but you want to handle arbitrary trees, and I don't know what happens in that case.
> 3 votes

# Answer
# An algorithm for the equivalent problem denoted by D.W. :

## The problem :

Input: a tree $T$, an integer $r$ (the radius)
Find: a set $S$ of $k$ vertices, such that every vertex in the tree is at distance $\le r$ from one of the vertices in $S$; or failure if no such set exists

## The algorithm :

1. Sort the nodes by decreasing depth using a BFS.
2. Pick the first one (a leaf).
3. Go up in the tree to its $r^{th}$ ancester (the parent of the parent ... of the leaf) and add this ancester to $S$. The parent of the root is the root itself.
4. Remove (both from the tree and from the sorted container) all the nodes covered by this new cluster center.
5. If none of the nodes are remaining then return $S$. Else, if $|S| = k$ then return failure.
6. Go to 2.

## Correctness :

Since the algorithm adds at most $k$ centers and since a node can not be removed if it is not covered by a center, the algorithm returns a failure when it has to return a failure.

Then, when it has to return a solution. The size of $S$ is still increasing and will reach $k$, so it's enough to prove by reccurence that $S$ is always a subset of a solution, while the algorithm is running.

At the beginning $S$ is empty and a solution exists by hypothesis. Then, assume that, at some point in the algorithm, $S$ is a subset of a solution $S^\*$. Let's prove that we can still reach a solution after adding a new center in $S$.

Let $u$ be the node chosen in the step 2. Let $v$ be the node chosen in the step 3, $v$ is the next center which will be added. Whatever are the centers in $S^\*$, $u$ has to be covered by at least one of them, let's denote it $w$. The centers selected before don't cover $u$, else $u$ would not be still in the tree. Thus $w$ is in the remaining nodes and not in $S$ and there is only 2 cases :

If $w$ is a descendant of $v$, since $v$ has the max depth among the remaining nodes, $w$ cover a subset of the remaining nodes which are covered by $v$. Thus $( S^\* \setminus \\{ w \\} ) \cup \\{ v \\}$ is also a solution and we can reach it from $S \cup \\{ v \\}$ since $S \cup \\{ v \\} \subset ( S^\* \setminus \\{ w \\} ) \cup \\{ v \\}$.

Else, $w$ is further from $u$ than $v$, so the distance between $u$ and $w$ is longer than $r$ and $w$ is too far for covering $u$, it's absurd.

Hence the reccurence holds and we can conclude that the greedy choice of the centers lead to a solution that the algorithm returns.

## Complexity

Linear : the step 1 is a BFS and then each node is seen and removed once at most. Including the binary search on $r$, we get an $O(n \log n)$ algorithm for the problem of the question.

In addition, the height is an upper bound for the minimal $r$, hence for trees which have $O(\log n)$ height we have a $O(n \log \log n)$ algorithm for the problem of the question.
> 1 votes

---
Tags: algorithms, trees, cluster
---


# Question
Title: find the actual size of an object from pixel coordinates
I am quite new to vision and OpenCV, so forgive me if this is a stupid question but I have got really confused.

My aim is to detect an object in an image and estimate its actual size. Assume for now I only want length and width, not depth. Lets say I can detect the object, find its size(length and width) in pixels and I have both the intrinsic and extrinsic parameters of the camera.

The documentation of camera calibration as I understand says that the intrinsic and extrinsic camera parameters can be used to transform from camera coordinate system to world coordinate system. So this should mean converting from pixel coordinates to real coordinates right? And so I should be able to use pixel size and these params to find the real size?

But, say the object is photographed at different depth (distance from camera), then its size would come out different using above method. So.....what does it mean transforming from camera to world coordinates?

Any kind of explaination/links/help would be highly appreciated.

# Answer
> 2 votes
Unfortunately you can't estimate the real size of an object from an image, since you do not know the distance of the object to the camera.

Geometric Camera Calibration gives you the ability to project a 3D world point onto your image but you can not project a 2D image point into the world without knowing its depth.

# Answer
> 1 votes
Even if you have object photographed at different depths, you still have to measure your distance of taking snapshots, and theoreticaly move along the line (at least try) for consecutive snapshots. Even better if you can take it from at least three positions.

Take a look: https://photo.stackexchange.com/questions/40981/what-is-the-relationship-between-size-of-object-with-distance

You have to calibrate camera: http://www.aishack.in/tutorials/calibrating-camera-theory/
Fix distortions: http://aishack.in/tutorials/major-physical-defects-cameras/ http://www.aishack.in/tutorials/calibrating-undistorting-opencv-oh-yeah/

Theoretically you can measure object from two pictures from different distances (in one line), but when it comes to combination of every possible distortion, shifts and so on, this is only rough estimate of 2D contour.

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


# Question
Title: Average case algorithm analysis using Kolmogorov Incompressibility Method
The Incompressibility Method is said to simplify the analysis of algorithms for the average case. From what I understand, this is because there is no need to compute all of the possible combinations of input for that algorithm and then derive an average complexity. Instead, a single incompressible string is taken as the input. As an incompressible string is typical, we can assume that this input can act as an accurate approximation of the average case.

I am lost in regard to actually applying the Incompressibility Method to an algorithm. As an aside, I am not a mathematician, but think that this theory has practical applications in everyday programming.

Ultimately, I would like to learn how I can deduce the average case of any given algorithm, be it trivial or complex. Could somebody please demonstrate to me how the method can be applied to a simple algorithm? For instance, given an input string S, store all of the unique characters in S, then print each one individually:

```
void uniqueChars(String s) {
    char[] chars = chars[ s.length() ]
    int free_idx = 0;

    for (int i = 0; i < s.length(); i++) {
       if (! s[i] in chars) {
          chars[free_idx] = s[i]
          free_idx++;
       }
    }

    for (int i = 0; i < chars.length(); i++) {
        print (chars[i])
    }
}

```

Assume a linear search for checking whether the array contains an element.

The above code snippet is only for the sake of argument. Better algorithms by which the theory can be demonstrated are acceptable, of course.

I asked this question on StackOverflow (https://stackoverflow.com/q/24619383/3813812) back in July, 2014, and have received a few helpful comments but not a definite answer. As one of the commenters pointed out, this question is better suited for Computer Science StackExchange, so I ask here today.

Some literature that I have reviewed includes:

1. An Introduction to Kolmogorov Complexity and Its Applications, by Ming Li and Paul M.B. Vitányi
2. https://www.cs.duke.edu/~reif/courses/complectures/Li/KC-Lecture1.pdf
3. http://www.detectingdesign.com/PDF%20Files/Kolmogorov%20Complexity%202.pdf

Among a few other resources that I do not have links to on hand.

If my understanding of the applicability of Kolmogorov complexity is inaccurate or what I ask is impractical, I would appreciate a statement with regard to the fact.

# Answer
> 4 votes
The idea of the incompressibility method is that an incompressible input satisfies certain properties that can be helpful in the analysis. In your case, the complexity of the algorithm depends on how many characters appear in the string. When processing the $k$th character, the "running time" (or rather its proxy, the number of comparisons when checking the list) is $\approx \alpha\_k/2$ comparisons on average, where $\alpha\_k$ is the number of different characters that have been seen so far. In order to estimate $\alpha\_k$, note that we can encode the first $k$ characters using roughly $8\alpha\_k + k\log \alpha\_k$ bits, and we deduce that $8\alpha\_k + k\log\_2 \alpha\_k \geq 8k$. Hence unless $k$ is very small, $\alpha\_k$ has to be very close to $256$, and we can deduce that there are on average $128$ comparisons per character. We can use the inequality to determine how large $k$ needs to be, and also what happens when $k$ is small.

The reason we are trying to count the exact complexity in the case of your algorithm is that its worst-case and best-case running times are both $\Theta(n)$. We used incompressibility to estimate $\alpha\_k$, which can also be estimated directly using probabilistic methods, but the incompressibility calculation is probably simpler. Still, incompressibility doesn't obviate the need to analyze the algorithm probabilistically – it just makes the analysis more tractable in some cases.

# Answer
> 1 votes
As a further comment (but slightly longer than an actual comment) on the accepted answer:

1. **Kolmogorov Complexity** (or **Algorithmic Complexity**) deals with **optimal descriptions of "strings"** (in the general sense of *strings as sequences of symbols*)
2. A string is (sufficiently) **incompressible** or (sufficiently) **algorithmicaly random** if its (algorithmic) description (kolmogorov comlplexity **K**) is **not less than its (literal) size**. In other words **the optimal description of the string, is the string itself**.
3. **Major result of the theory is that most strings are (algorithmicaly) random (or typical)** (which is also related to other areas like Goedel's Theorems, through Chaitin's work)
4. **Kolmogorov Complexity** is related to **Probabilistic (or Shannon) Entropy**, in fact Entropy is an upper bound on KC. And this relates analysis based on descriptive complexity to probabilistic-based analysis. They can be inter-changeable.
5. Sometimes it might be easier to use probabilisrtic analysis, others descriptive complexity (views of the same lets say)

So in the light of the above, assuming an algorithmicaly random input to an algorithm, one asumes the following:

1. The input is **typical**, thus the analysis describes **average-case scenario** (point 3 above)
2. The input **size is related in certain way to its probability** (point 2 above)
3. One can pass **from algorithmic view to probabilistic view** (point 4 above)

---
Tags: algorithm-analysis, kolmogorov-complexity
---


# Question
Title: Can systems that prevent double-spending (e.g. crypto-currencies) be used to attach other unique data?
The Bitcoin-solution can be described as "\[...\] a solution to the double-spending problem using a peer-to-peer network. (official Bitcoin paper, PDF, abstract, first page).

Now I wonder if a similar technology can be used to collect, send and receive other data with the goal to create "unique content". That is data that you either have or you don't have (like a physical object).

A follow-up question is if these objects can be only created by a central instance but once distributed there is no control from this central instance anymore. Like real money: It gets minted but once it is public you don't have to register every cash transaction with the your state.

One application could be a digital trading card game where you either have a "card" or not. You can either trade new cards directly with other humans or you get (buy) new ones from the creator who holds the monopoly over creating and releasing cards.

Did I miss anything in the crypto-currency tech that prevents this scenario?

# Answer
> 7 votes
In theory, yes, a peer-to-peer validation network could be used to enforce any unique content (not just money) *assuming a sufficiently large validation network.*

"Sufficiently large" is the catch. Bitcoin validates transactions by having the network nodes "vote" on the transaction's validity. According to Satoshi's proposal:

> The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.

Getting enough honest nodes into your validation network that no amount of compromised or attacker nodes can affect validation would be very hard. You would also probably want these nodes to be controlled by a large number of people. With a large number of nodes and a small number of controllers, it would be easier to compromise significant portions of the network and it would also reduce trust in the network since, despite the number of nodes, the control is still only in the hands of a few. Bitcoin (and all of the other cryptocurrencies that I am familiar with, which admittedly, isn't a lot) accomplished this by incentivizing its validators; Bitcoins are periodically awarded to the "miners" who solve the proof of work problems in the transactions. This also happens to be a convenient way to introduce new Bitcoins.

However, this would be particularly difficult for the digital trading card scenario you mentioned, since that kind of service would likely only appeal to a niche audience. Even if you incentivized by awarding cards, there might not be enough individuals interested in operating validation nodes.

A scheme where a central authority issues the money (or other content) might not fare much better, since, in practice, the central authority would probably either end up controlling or having material influence over a large portion of the network. Remember that the Bitcoin *network* issues coins, not the Bitcoin devs or any other single person or small group of people.

The take-home is that if you can get enough people to participate in the validation network, then you should be able to defend the uniqueness of any information (money isn't special in this regard). However, getting enough people to participate would probably be incredibly difficult.

# Answer
> 4 votes
Yes to both of your questions. Both are those are feasible. At least, the second one is certainly feasible; to the extent that I understand the first scenario, I believe that's possible too.

There are even existing systems that do something like this. For instance, Namecoin is a system for registering domain names that uses a Bitcoin-like blockchain. Only one person can own a domain name at a time, so it has the "uniqueness" aspect you are getting at.

One could easily support a system where a central authority mints digital tokens, e.g., to indicate who has a particular trading card. Then, digital tokens can be traded online, using a Bitcoin-like blockchain to record the transactions.

The general term of art for this broad area is altcoin or cryptocurrency. There are many Bitcoin-inspired cryptocurrencies: see Wikipedia's list or this list.

From a fundamental computer science perspective, Bitcoin solves the distributed consensus problem: it records a sequence of transactions, ensures that these are consistent according to some rules (e.g., no double-spending, can only spend coins that are currently yours), enables anyone to add additional transactions, and ensures that everyone in the world sees the same view of the database of transactions.

However, there *are* some non-trivial challenges to extending Bitcoin to your particular case. Bitcoin is a sophisticated mechanism that relies upon a clever allocation of incentives. The security of Bitcoin relies upon people to do "mining", as this is what enables appending to the blockchain and prevents forking of the bitcoin. Bitcoin creates an incentive for mining through its proof-of-work-based "lottery": miners who successfully add a new block to the end of the blockchain are given a small reward, a small fraction of a Bitcoin. This works because Bitcoin is used for a currency. If you used Bitcoin for, e.g., centrally-assigned trading cards, it's not clear how you would design the system to provide an incentive for mining. So that aspect of the system design would need careful thought and consideration.

---
Tags: cryptography, computer-games, peer-to-peer
---


# Question
Title: prove sufficient number of comparisons for the merge problem
It is given two subsequences. Their length are following: $2$ and $5$.
I can show that lower bound of comparisons is $5$. My problem is that I can't show that $5$ is sufficient number of comparisons to merge these subsequences.
In order to show lower bound I use tree of comparisons (number of leaves is $21$, so height is at least $5$).
However, when it comes to proof of sufficient number of comparison I have no idea. The only idea that comes to my mind is following:
Let our subsequences will be: $(a, b)$ and $(c, d, e, f, g)$. Let say, that we must use $k$ comparisons to find place for $a$, where $k\le 5$. Now, because of fact that $b\ge a$ we must do at most $5-k$ additional comparisons. Thus, $5-k+k=5$.
What about this proof ? Maybe you have other approach?

# Answer
> 4 votes
You asked about what approach to take, so I'll explain the general approach to take for this kind of problem.

The way to prove that 5 comparisons are sufficient is to exhibit a specific algorithm for merging these two sequences, and prove that your algorithm uses no more than 5 comparisons (no matter what the input is).

So, here's the approach I'd suggest for you, as your next step. Flesh out the algorithm that you have in mind. You seem to have an idea in mind, but take it the rest of the way: actually write down some pseudocode. Then, once you've written it down, try to analyze/upper-bound the number of comparisons your algorithm uses. See if you can prove that it uses at most 5 comparisons. (Try it on some example inputs if you need, to spot a pattern.) If you have proven that it correctly merges the two subsequences and you have proven it will never use more than 5 comparisons, you've proven that 5 comparisons are enough.

On the other hand, if you can't prove that (maybe your algorithm might take more than 5 comparisons on some inputs), you can't conclude anything -- you'll need to keep trying to find another algorithm.

---
Tags: correctness-proof, comparison
---


# Question
Title: How fast can we find all Four-Square combinations that sum to N?
A question was asked at Stack Overflow here:

> Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$.

This question is of course related to Bachet's Conjecture in number theory (sometimes called Lagrange's Four Square Theorem because of his proof). There are some papers that discuss how to find a single solution, but I have been unable to find anything that talks about how fast we can find *all* solutions for a particular $N$ (that is, all *combinations*, not all *permutations*).

I have been thinking about it quite a bit and it seems to me that it can be solved in $O(N)$ time and space, where $N$ is the desired sum. However, lacking any prior information on the subject, I am not sure if that is a significant claim on my part or just a trivial, obvious or already known result.

So, the question then is, how fast can we find all of the Four-Square Sums for a given $N$?

---

OK, here's the (nearly) $O(N)$ algorithm that I was thinking of. First two supporting functions, a nearest integer square root function:

```
// The nearest integer whose square is less than or equal to N
public int SquRt(int N) {
    return (int) Math.Sqrt((double) N);
}

```

And a function to return all TwoSquare pairs summing from 0 to N:

```
// Returns a list of all sums of two squares less than or equal to N, in order.
public List<List<int[]>> TwoSquareSumsLessThan(int N) {
    // Make the index array
    List<int[]>[] Sum2Sqs = new List<int[]>[N + 1];

    // Get the base square root, which is the maximum possible root value
    int baseRt = SquRt(N);
    for (int i = baseRt; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            int sum = (i * i) + (j * j);
            if (sum > N) {
                break;
            } else {
                // Make the new pair
                int[] sumPair = { i, j };
                // Get the sumList entry
                List<int[]> sumLst;
                if (Sum2Sqs[sum] == null) {
                    // make it if we need to
                    sumLst = new List<int[]>();
                    Sum2Sqs[sum] = sumLst;
                } else {
                    sumLst = Sum2Sqs[sum];
                }

                // Add the pair to the correct list
                sumLst.Add(sumPair);
            }
        }
    }

    // Collapse the index array down to a sequential list
    List<List<int[]>> result = new List<List<int[]>>();
    for (int nn = 0; nn <= N; nn++) {
        if (Sum2Sqs[nn] != null)
            result.Add(Sum2Sqs[nn]);
    }

    return result;
}

```

Finally, the algorithm itself:

```
// Return a list of all integer quads (a,b,c,d), where:
//      a^2 + b^2 + c^2 + d^2 = N,
// and  a >= b >= c >= d,
// and  a,b,c,d >= 0
public List<int[]> FindAllFourSquares(int N) {
    // get all two-square sums <= N, in descending order
    List<List<int[]>> Sqr2s = TwoSquareSumsLessThan(N);

    // Cross the descending list of two-square sums <= N with
    // the same list in ascending order, using a Merge-Match
    // algorithm to find all combinations of pairs of two-square
    // sums that add up to N
    List<int[]> hiList, loList;
    int[] hp, lp;
    int hiSum, loSum;
    List<int[]> results = new List<int[]>();
    int prevHi = -1, prevLo = -1;

    // Set the Merge sources to the highest and lowest entries in the list
    int hi = Sqr2s.Count - 1;
    int lo = 0;

    //  Merge until done ..
    while (hi >= lo) {
        // check to see if the points have moved
        if (hi != prevHi) {
            hiList = Sqr2s[hi];
            hp = hiList[0];     // these lists cannot be empty
            hiSum = hp[0] * hp[0] + hp[1] * hp[1];
            prevHi = hi;
        }

        if (lo != prevLo) {
            loList = Sqr2s[lo];
            lp = loList[0];     // these lists cannot be empty
            loSum = lp[0] * lp[0] + lp[1] * lp[1];
            prevLo = lo;
        }

        // Do the two entries' sums together add up to N?
        if (hiSum + loSum == N) {
            // they add up, so cross the two sum-lists over each other
            foreach (int[] hiPair in hiList) {
                foreach (int[] loPair in loList) {
                    // Make a new 4-tuple and fill it
                    int[] quad = new int[4];
                    quad[0] = hiPair[0];
                    quad[1] = hiPair[1];
                    quad[2] = loPair[0];
                    quad[3] = loPair[1];

                    // Only keep those cases where the tuple is already sorted
                    //(Otherwise it's a duplicate entry)
                    if (quad[1] >= quad[2]) { // (only need to check this one case, the others are implicit)
                        results.Add(quad);
                    }

                    // (there's a special case where all values of the 4-tuple are equal
                    // that should be handled to prevent duplicate entries, but I'm
                    // skipping it for now)
                }
            }

            // Both the HI and LO points must be moved after a Match
            hi--;
            lo++;
        } else if (hiSum + loSum < N) {
            lo++; // too low, so must increase the LO point
        } else { // must be > N
            hi--;   // too high, so must decrease the HI point
        }
    }

    return results;
}

```

As I said before, it should be pretty close to $O(N)$. However, as Yuval Filmus points out, as the number of Four Square solutions to N can be of order $N.ln(ln(N))$, then this algorithim could not be less than that.

# Answer
Juho's algorithm can be improved to an $O(N)$ algorithm using meet-in-the-middle. Go over all pairs $A,B \leq \sqrt{N}$; for each pair such that $M=A^2+B^2 \leq N$, store $(A,B)$ in some array $T$ of length $N$ (each position $M$ could contain several pairs, which might be stored in a linked list). Now go over pairs $M,N-M$ such that the corresponding cells in $T$ are non-empty.

This way we get an implicit representation of all quadruples. If we want to list all of them, then we can't do any better than $\Omega(N\log\log N)$, since Jacobi's four square theorem shows that (for odd $N$) the number of representations is $8\sigma(N)$, and there are infinitely many integers such that $\sigma(N) \geq (e^\gamma - \epsilon) N\log\log N$ (see Grönwall's theorem).

In order to get less trivial algorithms, one can try to factor $N$ over the appropriate quaternion ring, since we know that the representations as sums of two squares correspond (in some sense) to these factorizations, through Lagrange's four-square identity. We would still need to find all representations of any relevant prime.
> 16 votes

# Answer
The obvious algorithm that runs in quadratic time enumerates all tuples $A,B,C,D \leq \sqrt\[\]{N}$. This can be done in four loops, so the total time complexity becomes $O(N^2)$. It also clearly enumerates all solutions.

As relating algorithms, Rabin and Shallit \[1\] present two randomized algorithms for decomposing integers as sum of squares. For two squares, they give a $O(\log^2 n)$ expected time algorithm. For four squares, they give a $O(\log^2 n \log \log n)$ expected time algorithm. Note that the algorithms don't give you *all* the solutions, but merely just one.

---

\[1\] M. O. Rabin, J. O. Shallit, *Randomized Algorithms in Number Theory*, Communications on Pure and Applied Mathematics 39 (1986), no. S1, pp. S239–S256.
> 5 votes

# Answer
The number of solutions is exactly $8\sum d$, where $d$ goes over all divisors of $n$ which are not multiples of 4. This is a theorem of Jacobi.
> -2 votes

---
Tags: complexity-theory, time-complexity, number-theory, enumeration
---


# Question
Title: Move tokens from s to t as fast as possible
Let $G=(V, E)$ be an unweighted and undirected graph, and $s, t \in E$.

The problems starts with $n$ tokens on $s$.

The goal is to move theses tokens to $t$ in a minimum of rounds with these rules :

* Each token can be moved up to once per round (a movement being when you transfer the token from $v$ the vertex that holds it, to $w \in N\_G(v)$).
* Each vertex $v \in V\backslash \left\\{s, t\right\\}$ can hold at most one token ($s$ and $t$ are unconstrained).

So far, what I've thought to is :

* If $N\_G(s)=0$ or $N\_G(t)=0$, it is not possible.
* If $N\_G(s)=1$ or $N\_G(t)=1$, you can just apply a BFS from $s$ to find the shortest path, then transfer every token one by one trough this path.
* If $N\_G(s) \geq 2$ and $N\_G(t) \geq 2$ you can apply a maximum flow algorithm on $G$ with $1$ as capacity for every edge. If the maximum flow is $1$ then you can apply a BFS and transfer every token through this path again. However if the maximum flow is $\geq 2$, then I don't really see what to do (having a maximum flow $\geq 2$ doesn't even guarantee there are multiple paths as nodes can hold at most $1$ token, while max flow tests only for edges, and even if there are multiple paths in some cases it can be better to use only the shortest path - e. g. for $2$ tokens if you have to paths but one is at least to edges longer -).

Does this problem have a name? What topic of graph theory does it belongs to? Are there efficient algorithms to solve it?

# Answer
> 1 votes
Menger's theorem states that the maximum number of $s$-$t$ (internally) vertex-disjoint paths is equal to the minimum size of an $s$-$t$ vertex cut. Let the common value be $m$. Then it can be shown that the asymptotic number of rounds required is $n/m + O(1)$.

Using the vertex disjoint paths, we can route $n$ tokens in $n/m + O(1)$ rounds, where the constant depends on the graph $G$ (but not on $n$). This gives an upper bound.

On the other hand, every token must pass through the vertex cut, and at most $m$ can do so at any given round, so routing $n$ tokens takes at least $n/m$ rounds. (For each token, there must be a first time at which it reaches a vertex in the cut. Each such time can repeat at most $m$ times, since at most $m$ vertices of the cut can be occupied at any given time. So the number of rounds is at least $n/m$.) This gives a matching lower bound.

From these two bounds, we deduce that the asymptotic number of rounds required is $n/m + O(1)$.

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


# Question
Title: If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?
I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can be solved in polynomial time.

My question is: does this proof also hold the other way? I.e. if an exponential lower bound for an NP-complete problem is proved, would that mean that no problems in NP can be solved in polynomial time?

# Answer
Not quite. If there's an exponential lower bound for a NP-complete problem, then it follows that no NP-complete problem can be solved in polynomial time. However, there will be some other NP problems (which aren't NP-complete) that can be solved in polynomial time.

If there's an exponential lower bound for any NP problem, then it follows that P != NP. In particular, an exponential lower bound for some problem means that the problem is not in P. So, if you have an exponential lower bound for some NP problem, that means the problem is in NP but not in P -- which means NP contains a problem that is not in P -- which means that NP != P.

It might help to recall that NP is a *set* of problems (the set of all search problems where YES answers have a polynomial-size witness that can be verified in polynomial time). Similarly, P is a *set* of problems (the set of all search problems that can be solved in polynomial time). So, if you've found one element of NP that is not an element of P, you can immediately conclude that those two sets are not the same sets.

Or, to put it another way: your second paragraph is the contrapositive of the statement in the first paragraph. If there is a NP problem with a non-polynomial lower bound, then not every problem in NP can be solved in polynomial time. If not every problem in NP can be solved in polynomial time, then it follows that no polynomial-time algorithm can be found for any NP-complete problem.

See What is the definition of P, NP, NP-complete and NP-hard? for more background.
> 5 votes

# Answer
Just to add the simple counter example, even if $P \neq NP$, we still have $P \subset NP$, so every problem in $P$ is also an $NP$-problem, and can be, by definition, solved in polynomial time.
> 1 votes

---
Tags: complexity-theory, np-complete, decision-problem, lower-bounds, p-vs-np
---


# Question
Title: time complexity analysis of recurrence relation
I am not able to solve time complexity analysis of this recurrence relation: T(n)=3T(n/2)+n^2.I want to find time complexity analysis of this recurrence relation without using masters theorem could you please help me to do so.

# Answer
> 1 votes
Imagine your recurrence as a tree. It has a height of $log\_2(n)$ since your input size $n$ is divided by $2$ every time.

The cost for a node on the $ith$-level is $(\frac{n}{2^i})^2$.

On the $ith$-level there are $3^i$ nodes.

The cost for that level (whithout considering the childnodes) ist therefore $3^i\*(\frac{n}{2^i})^2$

The overall cost is the sum of the cost for each level that is $\sum\_{i=0}^{log\_2(n)} (3^i\*(\frac{n}{2^i})^2) = \sum\_{i=0}^{log\_2(n)} (3^i\*\frac{n^2}{2^{2i}}) = n^2\*\sum\_{i=0}^{log\_2(n)} (\frac{3^i}{2^{2i}}) = n^2\*\sum\_{i=0}^{log\_2(n)} (\frac{3^i}{4^{i}}) = n^2\*\sum\_{i=0}^{log\_2(n)} (\frac{3}{4})^i$.

Which you can now solve with a formula for a geometric series that gives you $4n^2-3^{log\_2(n)+1}$

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Simplifying an upper O-bound in two variables
I have an algorithm that depends on two input sizes n and m. The complexity breaks down to the following equation:

$\frac{nm - 1}{n-1} = O(?)$

Is Big-O of the Formula $O(mn)$ or $O(m)$ because $n$ cancels out? Thank you in advance!

PS: I know that if $O(m)$ is the upper bound $O(mn)$ is an upper bound too, I want to find the tightest.

# Answer
> 5 votes
I assume that $n\ge 2$, which implies $1/(n-1)\le 2/n$. Then

$$ \frac{nm-1}{n-1} \le \frac{nm}{n-1} \le 2 \frac{nm}{n} \le 2m. $$

Thus your expression is bounded by $O(m)$.

# Answer
> 5 votes
Since we know nothing about the connection of $n$ and $m$ as the input size tends to infinity, we can only derive rough bounds.

Call your term

$\qquad f(n,m) = \frac{n}{n-1} \cdot m - \frac{1}{n-1}$.

Assuming $n \> 1$, we have

$\qquad f(n,m) \leq 2m - \frac{1}{n-1}$

and

$\qquad f(n,m) \geq m - \frac{1}{n-1} $.

Therefore, $f(m,n) \in \Theta(m)$ as $n,m \to \infty$.

Note how very lucky you are here. It is usually *not* possible to get rid of one variable for such bounds without knowing how the two variables relate. In particular, make sure you understand why we can not just say "$n/(n-1) \to 1$, so $f(n,m) \sim m$".
*Hint:* What if $m/n \sim 1/\sqrt{n}$?

For more on asymptotics in two variables see e.g. here and here.

---
Tags: asymptotics, landau-notation
---


title: Encircling randomly distributed points

text:
# Question
Title: Encircling randomly distributed points
I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will allow me to find the radii for the circles that cover as many points as possible, subject to the constraints that:

* the radii are bounded (maximum radius $r\_{max}$)
* circles cannot intersect/overlap.

My approach so far was to compute a rank 3 tensor. Start from a definition: a point is denied by a circle, if the circle, by taking another point, causes that the point cannot be covered by any of the remaining circles without violating the constraints. The size of tha tensor is $C \times P \times P$, where $C$ is the number of circles, and $P$ is the number of points. I initialize it with zeros. I then check whether if circle c takes point p, point p' is denied, which I signify in the tensor by setting the appropriate value to 1. From this data I'm trying to deduce whether it's worth trying to encircle a point, e.g. if a point is denied by many points, it probably means that it's a distant, isolated point, or that denying point form a cluster. I didn't manage to find a way that would allow me to make general any statements though.

Any ideas how to extend my approach / any suggestions to do it differently would be most welcome!

# Answer
> 1 votes
Okay, I think I have the solution to this one. It exploits the constraint (no overlaps) and the fact, that even a complex, multiple overlap problem, can actully be seen as a bunch of pairwise confilcts - at the end of the day no two circles can overlap.

Here is how it goes: Find all points that can be covered by by a given circle and sotre these. Find the furthest point distance and set the radius of the circle to be that distance. Now we probably have some overlaps. Create a priority queue and enter all the overlaping circles into the queue. The index of the queue is:

(distance from the furthest point) - (distance from the second furthest point).

Then we descrease the radius of the circle with the highest index so that now it's the distance to the second furthest point. Delete the circle from the queue, update the index and re-enter the circle into the queue if it still overlaps with any of the remainging circles. Keep repeating untill there is no more overlap in the system.

The solution is optimal, since the price for retracting the radius is constant (leaving out one point) and the gain is variable (and maximized by teh use of a priority queue).

# Answer
> -1 votes
How about using the convex hull approach and then calculating the centroid of the points that comprise the hull. The distance from the centroid to the furthest point on the hull should give the radius of the smallest circle with the centroid as its center that encompasses all other given points. Here's my algorithm for getting the points on the convex hull (credit Andrew's Monotone Chain algorithm)

```
# +ve for counter-clockwise rotation
# -ve for clockwise rotation
# 0 for collinear
def cross_prod(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points):
    points = sorted(set(points))
    lower = upper = []
    for p in points:
        while len(lower) >= 2 and cross_prod(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in points[::-1]:
        while len(upper) >= 2 and cross_prod(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return sorted(set(lower[:-1] + upper[:-1]))

```

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


# Question
Title: Do we want largest or smallest priority in the A* algorithm?
On this site http://algs4.cs.princeton.edu/25applications/ is described A\* algothihm this way

> The A\* algorithm is a problem-solving process where we put the start configuration on the priority queue, then do the following until reaching the goal: remove **the highest-priority configuration** and add to the queue all configurations that can be reached from that with one move (excluding the one just removed).

But in the programming assignment specification (http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html) is written next

> delete from the priority queue the search node with **the minimum priority**.

I don't understand why on the booksite is written to remove the highest-priority configuration but in the assignment is written to remove the lowest-priority configuration. Please could you explain me it? Maybe they thinks about "priority" or "configuration" in different meaning?

# Answer
It's just two ways of saying the same thing. High priority means most urgent but is often represented by low numbers – my "number-one priority" is the most urgent thing on my to-do list. Perhaps it would be clearer if people used phrases like "lowest priority value" or even "highest priority (lowest priority value)". It's often inconvenient to reformulate the algorithm to make high priority correspond to big numbers. For example, if I decide that "priority 10" means the most important thing on my to-do list, that kind of limits my lists to ten items, unless I want to number them 10, 9, ..., 1, 0, -1, -2, ..., which seems a bit silly.

Similar confusion comes up in other settings where smaller numbers represent bigger or higher things. For example, in photography, aperture is measured in f-stops but a higher f-number means a smaller aperture.
> 3 votes

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


# Question
Title: Schedule two trains whose tracks overlap so they don't crash
I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve.

Recently I was asked this question and did not even know what algorithmic technique to use to answer it!

There are two trains, which run between stations and share a portion of track. For instance train 1 runs between stations A B C D E F G H and train 2 runs between stations I J K B C D E F L M so the trains share the track between B C D. At each end of the track the train turns around and goes the other way on its track. The trains go from station to station in 1 unit time. I need to prevent the trains from crashing head on on the shared track, I have the power to stop either train at any station and restart it again when I please.

How can I solve this problem without using a ton of if else clauses, what CS principles should I be using here?

**edit**

Some background, the first solution I wrote was just a simple check to see if the other train was on the shared track before sending the other train out. That seemed ad hoc to me and I'm sure it did to the company I interviewed for as well.

I figure there must be an algorithm or at least a school of thought for this type of problem, after all how do they build extensible systems for managing shared runway space at an airport, or managing traffic flow at stop lights.

My intuition is that this is a very introductory problem to a school of thought in computational problem solving I have not yet encountered.

I might be wrong, but could anybody clear the air for me?

# Answer
If you calculate the cycle, as there are only two trains and distance between every station is one, you could simply run them in order and appoint wait in some station to avoid crash.

If you have to implement some unfortunate events (first one stops for some reason, reschedule it to run on itd own time).

With two trains it will work without problems.

Otherwise use semaphores (it fits even literally ;)

There is no explicitly given synchronisation problem, so nasty trick works.
> 0 votes

# Answer
A related and well studied area is threading/multiprocessing. Your initial solution is a simple lock; the critical section of tracks can only be used by one train at a time. To extend this while avoiding deadlocks (two trains waiting in each other) or starvation (a train waits forever), you would want to use some more sophisticated locking mechanism and scheduler.
> 0 votes

---
Tags: algorithms, scheduling, algorithm-design
---


# Question
Title: Is determining if there is a prime in an interval known to be in P or NP-complete?
I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the overall decision problem of: (Does there exists a prime in an interval?) is in P. (There were a lot of answers to that post that I did not read so I apologize if this question is a duplicate or unnecessary).

On the one hand, if the interval is large enough (for example $\[N,2N\]$) then something like Bertrand's Postulate applies and there is definitely a prime in this interval. However, I also know that there are arbitrarily large gaps between two primes (for example $\[N!,N!+ N\]$.

Even if the decision problem is in P I don't see how the corresponding search problem is also tractable because, then we may not be able to draw on the same properties regarding the known distribution of primes when performing binary search.

# Answer
> 20 votes
So your problem is as follows:

Input: integers $\ell,u$
Question: does there exist a prime in $\[\ell,u\]$?

As far as I know, it is not known whether that problem is in P or not.

Here's what I do know:

* Primality testing (given a single number, test whether it is prime) is in P, so if the range is small enough, you can exhaustively test each number in the range to see whether it is prime -- but this does not lead to a general algorithm.
* If Cramer's conjecture is true, then the problem is in P. Cramer's conjecture says that the gap between consecutive primes near $n$ is $O((\log n)^2)$, so the following algorithm will be in P: iterate through the numbers $\ell,\ell+1,\ell+2,\ell+3,\dots$, testing each whether it is prime; if you find one that is prime, stop immediately with a yes answer; if you hit $u$, stop with a no answer. Cramer's conjecture tells us that you'll stop after most $O((\log \ell)^2)$ primality-tests, so that algorithm will run in polynomial time.

Unfortunately, the known results on prime gaps don't seem strong enough to prove unconditionally that the problem is in P.
* Here is another simple algorithm: repeatedly pick a random integer $r$ from $\[\ell,u\]$, and test whether it is prime. Stop if you find a prime, or if you've tried every integer in $\[\ell,u\]$ and none were prime. Heuristically, we should expect this to be efficient in practice. The prime number theorem tells us that if you randomly choose number in the vicinity of $u$, the probability it is prime will be about $1/\log n$. Thus, heuristically, we should expect that after about $O(\log u)$ iterations, you'll typically find a prime and stop, if one exists. On the other hand, due to the coupon collector's problem, if there is no prime in the range $\[\ell,u\]$, you'll stop after about $O((u-l) \log(u-l))$ iterations. So, if we had a good upper bound on the size of the longest gap between prime numbers, this would imply that the problem is in BPP. Even without such an upper bound, it follows that random problem instances are easy.
* Probably one can apply sieving methods to improve the running time in practice (e.g., to avoid doing any primality testing on numbers that are divisible by a small prime). I don't know whether this can be shown to lead to any asymptotic improvement.
* Due to these techniques, the problem is probably easy in practice.
* Due to the above remarks, I personally doubt that the problem is NP-complete.

---
Tags: complexity-theory, np, polynomial-time, primes
---


# Question
Title: Have non-regular language classes of infinite words been studied?
For regular languages we have $\omega$-regular languages which extend them to infinite words.

Are there such extensions for CFG's, CSG's and recursively enumerable languages?

# Answer
We have the following MSO characterization of regular nested word languages:

> Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two unary predicates call and return, linear successor and the matching relation ↝.

The recommended reference on Nested Words and Visibly Pushdown Languages treats infinite words in section 8. Nested $\omega$-Words, and shows that the MSO characterization carries over:

> **Theorem 8.4** (MSO characterization of $\omega$-languages). A language $L$ of nested $\omega$-words over $\Sigma$ is regular iff there is an MSO sentence $\varphi$ over $\Sigma$ that defines $L$.

Because often deterministic CFGs are actually visibly pushdown languages, this covers a huge portion of the practically relevant CFGs. Moreover, this even provides a context where considering $\omega$-languages is practically relevant, as explained in the same section of the reference.
> 4 votes

---
Tags: formal-languages, context-free, reference-request, context-sensitive
---


# Question
Title: Delivery Algorithm - Find shortest paths
Given -

* A center(lat=x,lng=y) 'C' from which a delivery boy makes a round trip.
* A delivery boy has a bag which may contain at the most 10 boxes to deliver.
* A set of points Di (lat=xi,lng=yi) around 'C' where the delivery has to be done. D=number of Di & 1\<=D\<=10
* Each Di either belongs to time window(30 minutes) W1 or W2 where W1 is something like 11-30 am to 12 pm and W2 like 12 pm to 12-30 pm
* Each delivery has to meet an SLA (service level agreement). Eg- If the order O1 at drop point D1 belongs to W1 then it must be delivered within W1 window.

**Task** \- Find the shortest time path such that the delivery boy meets SLA for maximum number of orders. The best path is the one where SLA is met for all orders..

I think it will be better if I start with a couple of variations.. Use these variations in dry runs and gather some data for each of the variations..

**What I am looking for** \- Any other cues/variations that I can use.. The greedy approach is already up and running. I am gathering real time data to measure its performance..

**CLARIFICATIONS**

**If SLA's can't be met, do the deliveries still need to be made?** \- Yes, in those cases the best algorithm will be the one with minimum SLA breaches..followed by minimum time..

**Are there algorithm constraints/metrics (I.E. execution speed, memory used,etc) that must be considered?** \- Speed - not so much an issue - even if it takes 1 minute to run algo its ok, memory - it may take upto 0.5 gb.. Also if it turns out to be very compute intensive.. I can buy a new machine for running this algo..

**Will you need to scale up beyond the relatively small inputs stated** \- NO. The delivery boys capacity is fixed. It may at the most become 15 (from 10 earlier)

# Answer
A max of 10-15 orders is small enough that you might be able to brute force it. While this would exceed your execution time limit, it might be worth doing so on a small number of problems in order to compare algorithms absolutely rather than relatively. Alternatively, you might be able to find precomputed benchmarks for this problem.

In general, I'm personally found of restricting routing problems to a Deluaney triangulation. It's fast to calculate and has a Euclidean minimum spanning tree (MSP) as a subset. It won't have any route crossings (like those removed by a 2-opt).

However, the SLA constraint may work against that. E.G. Say that the you have found an optimal TSP solution (a locally optimal solution) for W1, but it can only service k out of n orders in time. In that case the globally optimal solution may require delaying the last (n-k) orders in W1 and going to the clostest order in W2. There's no reason to expect this W1 to W2 switch-over arch to be in a DT over all the sites. Furthermore, if your time windows don't overlap, there's no reason to visit W2 site during the W1 phase.

So then, I'd find a MSP for each subset of order sites (W1 & W2). On W1, apply Christofide's algorithm to get a Hamiltonian cycle. Find the start node, call it S1, & remove its longest arc in the cycle to get a Hamiltonian path through all of W1 - call this P1.

Next, compute the travel time & check for broken SLAs on P1. Eject the site that yeilds the biggest time savings until all remaining SLAs on P1 are valid.

Find the clostest point in W2 to the last site in P1 - call this S2.

On W2, apply Christofide's. Find S2 & remove its longest arc in the cycle to get a path through all of W2.

Recompute the travel time for P1 + P2 & check for broken SLAs on P2. Eject the site that yeilds the biggest time savings until all remaining SLAs on P2 are valid.

Finally, let W3 be all the previously ejected sites. Find the clostest point in W3 to the last site in P2 - call this S3. Find a MSP on W3, apply christofides, find the S3 & remove its longest arc in the cycle to get a path.

Solution is concatenation of P1, P2, P3, S1. Clearly, there are cases where this won't give the optimal answer, but it should scale well & has known bounds on the sub-problems which might help in determining its overall bounds.
> 3 votes

# Answer
Let's focus on the case where you try to figure out whether there is a way to meet the requirements without any SLA violation. This problem can be solved by solving at most 10 Hamiltonian path problems, then combining their solutions appropriately.

First, let's focus on the first time window. For each $i$ such that $D\_i$ must be visited during the first window, find the shortest path that starts at $C$ and ends at $D\_i$ and delivers every order that is scheduled to appear in the first window. This is a Hamiltonian path problem, so can be solved using standard methods (e.g., branch-and-bound, ILP, etc.). In particular, you build a graph with one vertex per $D\_j$ such that $D\_j$ must occur in the first window plus one vertex for $C$, where the length of the edge from $v$ to $w$ is equal to the time it takes to travel from $v$ to $w$, then you find the shortest Hamiltonian path from $C$ to $D\_i$. Let $\ell(C,D\_i)$ be the length of the shortest such path.

Next, focus on the second time window. Build a graph with one vertex for $C$ plus one vertex for each $D\_j$ such that you have to deliver to $D\_j$ in the second time window. Let $\ell(D\_j,C)$ be the length of the shortest Hamiltonian path in this graph from $D\_j$ to $C$, i.e., the shortest path that starts at $D\_j$ and ends at $C$ and visits every vertex in the second graph.

Finally, we'll look at all ways to piece together a Hamiltonian path for the first graph and a Hamiltonian path for the second graph. In particular, if $D\_i$ is a delivery location for the first time window and $D\_j$ is a delivery location for the second time window, the cost of the shortest path $C \to \dots \to D\_i \to D\_j \to \dots \to C$ that visits every location will be $\ell(C,D\_i) + \text{wt}(D\_i,D\_j) + \ell(D\_j,C)$ (where $\text{wt}(D\_i,D\_j)$ is the time it takes to get from $D\_i$ to $D\_j$).

So, compute the minimum of $\ell(C,D\_i) + \text{wt}(D\_i,D\_j) + \ell(D\_j,C)$ over all $i,j$ such that $D\_i$ is in the first time window and $j$ is in the second time window. This gives you the shortest path that starts at $C$, visits every delivery location once and within the right time window, and ends at $C$. In other words, it gives you the shortest path that meets all your requirements and doesn't violate any order's SLA.

Given how small each of the graphs will be, you should easily be able to solve each of those 10 Hamiltonian path problems -- it should be very fast. There are many known techniques for solving Hamiltonian path problems, from exhaustive enumeration to branch-and-bound to integer linear programming (ILP).

This only handles the case of no SLA violations, and it assumes the delivery person never needs to return to the center $C$ (his bag is large enough to store all of the boxes).

If it's not possible to solve the problem with no SLA violations, you can probably extend this to find the best solution that minimizes the number of SLA violations with a bit more work, by adapting these techniques. As a simple trick, you could check whether it's possible to solve the problem with only one SLA violation by iterating over all possibilities for which order to skip (solving the resulting problem by deleting that one order and then looking for a way to handle all the remaining orders with no other SLA violations). It's probably possible to generalize to an arbitrary number of SLA violations by a clever use of dynamic programming, but if you expect it to be rare to need to violate the SLA by more than one or two orders, it might not be necessary to develop the more sophisticated algorithms to handle the general case.
> 2 votes

---
Tags: algorithms, shortest-path, greedy-algorithms
---


# Question
Title: Regular expression - every b preceded and followed by an even number of a's
I'm trying to write a regular expression over the alphabet $\\{a, b\\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s.

I think the regular expression should include something like $((aa)^\*b(aa)^\*)^\*$ but I don't know how to extend it in order to get to the correct form. Can anyone help me by providing a step-by-step solution?

# Answer
The answer you already have covers almost all the cases: any time there's a $b$, there need to be an even number of $a$'s, so that covers all words containing a $b$.

However, there's an edge case where there are no $b$'s in your word, so you need to union your language with the case where the word has no $b$'s.

$((aa)^\*b(aa)^\*)^\* \cup a^\*$ should fit your final answer.
> 3 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: How does the operating system set up memory boundaries?
Is there a hardware interrupt that is pre-configured by the OS or something? Try to keep the answer on the scale of a register or so.

Are some special preparatory signals sent across the bridges to the hardware to make boundaries?

# Answer
> 3 votes
How memory boundaries work depends on the system, but the most common method is a memory management unit (MMU) or a memory protection unit (MPU). Whenever the CPU makes a memory access, the address is analyzed by the MPU or MMU. An MPU either allows or forbid the access; an MMU is more powerful and translates the virtual address passed by the processor into a physical address used by the memory controller.

When the access is denied, this triggers a kind of interrupt (not necessarily an actual interrupt because it often comes from inside the CPU; the vocabulary depends on the architecture but it's often called *trap* or *exception*). Other than that, no interrupts are involved.

On most architectures, the MMU is part of the CPU. So MMU configuration does not involve any “signals sent across the bridges” (did you mean the *buses*?).

The MPU/MMU acts based on tables. The CPU sets the tables, generally by setting a register which contains a pointer to the main table. The operating system normally modifies the table whenever a context switch between tasks occurs or a task allocates or frees memory.

---
Tags: computer-architecture, memory-management, memory-access
---


# Question
Title: How to practically measure entropy of a file?
I'm trying to measure now much non redundant (actual) information my file contains. Some call this the amount of entropy.

Of course there is the standard p(x) log{p(x)}, but I think that Shannon was only considering it from the point of view of transmitting though a channel. Hence the formula requires a block size (say in bits, 8 typically). For a large file, this calculation is fairly useless, ignoring short to long distance correlations between symbols.

There are binary tree and Ziv-Lempel methods, but these seem highly academic in nature.

Compressibility is also regarded as a measure of entropy, but there seems to be no lower limit as to the degree of compression. For my file hiss.wav,

* original hiss.wav = 5.2 MB
* entropy via the Shannon formula = 4.6 MB
* hiss.zip = 4.6 MB
* hiss.7z = 4.2 MB
* hiss.wav.fp8 = 3.3 MB

Is there some reasonably practicable method of measuring how much entropy exists within hiss.wav?

# Answer
Entropy is a feature of a *random variable*. A given file has zero entropy, since it is constant. Entropy makes sense in many situation in which there is no channel, and you can apply it to a random ensemble of, say, WAV files, generated from a given source. In this case, your $x$ is the *entire* WAV file.

The actual WAV file (excluding the header) can be thought of being generated by some Markovian source. This source produces sounds amplitudes ("samples") in a sequence, each one depending on the ones preceding it. After running the process for very long, the entropy of each sample (more accurately, the conditional entropy given the preceding samples) gets very close to some limiting value, which we define to be the entropy of the source. The entropy of $N$ samples is $N$ times that number (in the limit; again, more accurately, we are measuring the conditional entropy). Lempel and Ziv showed that if the sample entropy is $H$ bits, then their algorithm compresses $N$ samples to $HN + o(N)$ bits, with high probability (the probability is over the samples). Lempel–Ziv compression is quite popular in practice, used for example in the popular `gzip` format.

Due to this result of Lempel and Ziv, the entropy of a source can be approximated by compressing a long sequence of samples using the Lempel–Ziv algorithm. This doesn't estimate the entropy of the specific samples, which is not a well-defined concept (a constant sequence has zero entropy), but rather the entropy of the source generating it.

A related concept is *algorithmic entropy*, also known as *Kolmogorov complexity*. It is the length of the shortest program generating your file. This quantity does make sense for an individual file. In the case of a file generated by a random source, the Lempel–Ziv theorem shows that the algorithmic entropy of a file is bounded, with high probability, by its Shannon entropy. Unfortunately, algorithmic entropy isn't computable, so it's more of a theoretical concept.

To complete the picture, I suggest reading Shannon's paper on Prediction and entropy of printed English for a different approach to estimating the entropy of a source.
> 9 votes

---
Tags: entropy
---


# Question
Title: Best data structure for high dimensional nearest neighbor search
I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I've read that in general, all space-partitioning data structures tends to perform exhaustive search with high dimensional data.

Additionally, there are two important facts to be considered (ordered by relevance):

* **Precision:** The nearest neighbors must be found (not approximations).
* **Speed:** The search must be as fast as possible. (The time to create the data structure isn't really important).

So, I need some advice about:

1. The data structure to perform kNN.
2. If it will be better to use an aNN (approximate nearest neighbor) approach, setting it as accurate as possible?.

# Answer
> 1 votes
Here is a closely related question (although different enough that I wouldn't call this a duplicate): https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data

As you said, all known structures degrade to linear search as the dimension grows. More specifically, the efficiency degrades as the dimension approached the number of points in the feature space (binary search doesn't help with two points, K-D trees are useless on three points, etc.).

However, if the time to create the data structure does not matter *at all,* you can create a complete graph with sorted edge lists. That is, every node keeps track of its neighbors in nearness order. This would take $O(n^2 \log n)$ time to create, but would give you the kNN of any point in $O(1)$.

---
Tags: data-structures, approximation, efficiency, nearest-neighbour
---