# Question
Title: Do lossless compression algorithms reduce entropy?
According to Wikipedia:

> Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter include redundancy in language structure or statistical properties relating to the occurrence frequencies of letter or word pairs, triplets etc.

So entropy is a measure of the amount of information contained in a message. Entropy coders are used to losslessy compress such a message to the minimum number of bits needed to represent it (entropy). To me this looks like a perfect entropy encoder would be all that is needed to losslessy compress a message as much as possible.

Many compression algorithms however use steps before entropy coding to supposedly reduce the entropy of the message.

According to german Wikipedia

> Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, die Entropie der Daten zu verringern.

In english:

> Entropy coders are frequently combined with other encoders. Previous steps serve to reduce the entropy of the data.

i.e. bzip2 uses the Burrows-Wheeler-Transform followed by a Move-To-Front-Transform before applying entropy coding (Huffman coding in this case).

Do these steps really reduce the entropy of the message, which would imply reducing the amount of information contained in the message? This seems contradictory to me, since that would mean that information was lost during compression, preventing lossless decompression. Or do they merely transform the message to improve the efficiency of the entropy coding algorithm? Or does entropy not correspond directly to the amount of information in the message?

# Answer
A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon entropy stipulates that it only applies when, as Wikipedia puts it, "information due to independent events is additive."

In other words, independent events must be *statistically* independent. If they aren't, then you have to find a representation of the data that defines events in ways that make them truly independent. Otherwise, you will overestimate the entropy.

To put it yet another way, Shannon entropy only applies to true probability distributions, and not to random processes in general. For concrete examples of processes that don't fit the assumptions of Shannon entropy, consider...

### Markov processes

A Markov process generates a series of events in which the most recent event is sampled from a distribution that depends on one or more previous events. Obviously a huge number of real-world phenomena are better modeled as Markov processes than as discrete, independent probability distributions. For example: the text you're reading right now!

The naively calculated Shannon entropy rate of a Markov process will always be greater than or equal to the *true* entropy rate of the process. To get the true entropy of the process, you need to take into account the statistical dependence between events. In simple cases, the formula for that looks like this:

$$ H(\mathcal{S}) = - \sum\_i p\_i \sum\_j \ p\_i (j) \log p\_i (j) $$

This can also be represented like so:

$$ H(Y) = - \sum\_{ij} \mu\_i P\_{ij} \log P\_{ij} $$

Again quoting Wikipedia, here "$\mu\_i$ is the asymptotic distribution of the chain" -- that is, the overall probability that a given event will occur over a long horizon.

This is all a complicated way of saying that even when you can calculate the overall probability of a given event, certain *sequences* of events are more likely than others to be generated by a Markov process. So for example, the following three strings of English words are increasingly less likely:

* They ran to the tree
* The tree ran to they
* Tree the they to ran

But Shannon entropy will assess all three strings as equally likely. The Markov process entropy takes the difference into account, and as a result, it assigns a lower entropy rate to the process.

### Entropy rates are model-dependent

If you zoom way out, here's the big picture: the entropy rate of a given sequence of events from an unknown source is model-dependent. You'll assign a different entropy rate to a particular series of events depending on how you model the process that generated them.

And very frequently, your model of the process isn't going to be quite correct. This isn't a simple or easy to solve problem. In fact, in general, it is impossible to assign a *true* entropy rate to a sufficiently long and complex sequence of events if you don't know what the true underlying process is. This is a central result in algorithmic information theory.

What it means in practice is that given an unknown source of sequences of events, different models will yield different entropies, and it's impossible to know which is correct in the long run -- although the one that assigns the lowest entropy is probably the best.
> 40 votes

# Answer
No, if the algorithm is lossless no steps in the compression sequence can reduce its entropy - otherwise it would not be able to be decompressed/decoded. However, the additional entropy may be stored in 'out-of-band' information - such as the list that needs to be maintained in order to decode the move-to-front transform.
> 12 votes

# Answer
They reduce the *apparent* entropy inherent in the structure of the original message. Or in other words they tune the message to make use of the strengths of the next stages of compression.

One simple example would be replacing the name in the end tags of xml with a special symbol. You can perfectly recreate the original xml from that but the compressor doesn't have to include the full name again in that place.

A more real-world example is png compression. It's entropy compressor is DEFLATE, which is a combination of Lempel-Ziff and Huffman. This means that it works best with values and patterns that repeat often. Most adjacent pixels tend to be similar colors. So each row is assigned a filter which turn the original pixel values into a differential encoding. This way the values that end up encoded by DEFLATE are mostly close to 0. In the extreme case this will turn a smooth gradient from all different values into a single value throughout the row which the LZ portion or DEFLATE makes very quick work of.
> 6 votes

# Answer
Entropy coders do not compress the message to the minimum number of bits needed to represent it. I know it's tempting to think that, but it's not what they do. They aren't magic and they can't achieve that.

Instead, they do something a bit less magical -- but still useful. Suppose for the moment that we knew that each character of the message was chosen independently from some distribution. Then it would be possible to build a lossless compression algorithm that optimally compresses the messages. These algorithms are called entropy encoders.

Now real messages usually don't have that independence property. For instance, if you see a Q, it's likely that the next letter is a U. And so on. It is still possible to apply an entropy encoder algorithm to a real message, where each character isn't chosen independently of the rest. The algorithm will still be lossless, it can still be used for compression, and in practice, it will still often shorten the length of the message. However, it doesn't shorten it to the minimum possible length. It doesn't compress the message to something whose length is equal to the entropy of the message; it compresses it less than that.

Once you realize this property of entropy encoders, then the paradox evaporates.

In general, any lossless step never reduces the entropy of the message. However, it might put the message into a form where some other compression algorithm is more effective, so it might still be useful (on average) in practice.
> 6 votes

# Answer
The word "Entropy" if often used a bit loosely, to refer to two different things:

* The "total amount of information" in a message or system
* The information "density", or how tightly the information is packed.

OP's quote of the Wikipedia's entry for https://en.wikipedia.org/wiki/Entropy\_(information\_theory) refers to the first:

```
Shannon's entropy measures the information contained in a message

```

But (at least when I'm writing this) the same article starts with:

```
Information entropy is the average rate at which information is produced by a stochastic source of data.

```

So one is an amount and one is a rate (similar to distance vs. speed). These are sometimes called "extensive" and "intensive" properties (see https://en.wikipedia.org/wiki/Intensive\_and\_extensive\_properties#Extensive\_properties).

A classic example of the distinction is Paul Revere's famous lantern signal: "one if by land, and two if by sea". 1 bit of total information (if we ignore the "none if I haven't gotten to North Church yet" case). If Paul added another set of lanterns in each window of the building, that would be '''redundant''': no more information, so the same "total" or "extensive" entropy; but much more message length, so much lower "intensive" entropy.

If he starts that way but changes to use only one set of lanterns, that's "lossless compression" like in OP's question. The "extensive" entropy is the same, but the "intensive" entropy" is different: Because the number of lanterns in the 2nd window is highly correlated with how many you've seen in the first, the redundant message is more predictable, or less random, so has much lower intensive entropy.

There are two other important things to remember:

* First, we typically don't know the "true" entropy of a system in either sense. A naive bystander doesn't know whether "3 lanterns" would be different message, or whether signals in different window are redundant or not. If Paul makes his ride a habit, we can count and see whether the windows always match each other. But maybe we just haven't watched long enough to see the rare (and probably important!) exceptions.
* Second, it matters how you measure. Consider trying to estimate how much is communicated by each successive letter of text (that's a rate, so "intensive" entropy, also sometimes called "relative entropy"):

+ If you just notice that people send text around in 8-bit units, your first "estimate" might be 8 bits per letter.
    + If you count the number of distinct letters being used, you'd estimate log2(26), or 4.7 bits per letter (a bit higher if you consider spaces, case, etc).
    + If you consider that "e" is a better bet for "next letter" than "z", you'll measure letter frequencies and get around 4.14 (see http://people.seas.harvard.edu/~jones/cscie129/papers/stanford\_info\_paper/entropy\_of\_english\_9.htm).
    + If you count letter-pairs you'll pick up on patterns like "qu", "th", etc., and get around 3.56.
    + If you count sequences of up to around 5 letters, you'll get still lower values, and as a bonus you can pretty reliably distinguish what human language the text is in).
    + If you're as hard-core and clever as N. G. Burton and J. C. R. Licklider in "Long-Range Constraints in the Statistical Structure of Printed English" (American Journal of Psychology 68(1955)), you can get up to sequences of 10,0000 letters in a row, and find yet another entropy value.

But of course, messages can (and do) have many patterns that aren't modelled by such n-gram methods, so the "true" entropy is lower still.

If you model a theoretical infinite source with perfectly random Zipfian distribution of tokens, you can calculate the extensive and intensive entropy it would have, which turns out to depend only on the number of possible distinct tokens. Graphs of what each type of entropy looks like as that number increases, are in \[http://www.derose.net/steve/writings/dissertation/Diss.0.html\]. The two behave quite differently:

Hope that helps or is at least interesting...
> 2 votes

# Answer
I suspect the wording in the German Wikipedia is mistaken. Compressors increase the entropy. That is to say, not the overall entropy, but the entropy **per bit**: the information density. E.g. some run-length encoding and dictionary scheme is applied to condense the data. Now the same information is packed into fewer bits, so each bit carries more information. The subsequent Huffman coding does a little more of the same; it's just another layer of compression.
> 1 votes

---
Tags: information-theory, data-compression, entropy
---


title: Why it is not a Huffman code

text:
# Question
Title: Why it is not a Huffman code
I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was:

$\\{00,01,10,110\\}$

This code is not Huffman becuase it has just one codeword of maximum length whereas there should be two as a minimum.

Next, the one I hava a problem in proving:

$\\{01,10\\}$

Why this code is not a Huffman code?

# Answer
> 0 votes
(**Minimum number of codewords**) (Binary complete) Huffman code of maximal code length $n$ must have at least $n+1$ codewords.

The maximal code length of codewords $\\{01, 10\\}$ is 2. However, there are only two codewords. So those codewords is not a Huffman code.

---

(**Exercise.**) Prove the claim of the minimum number of codewords of Huffman code.

# Answer
> 0 votes
A Huffman code is defined by two properties:

1. No code is a prefix of another code.
2. If you add up $2^{-k}$, where k is the length of each code, then the total is 1.

In your second case, you have two codes of length 2. If you add $2^{-2}$ twice, the sum is 1/2, not 1. Actually, in your first example the sum is 7/8ths.

To make the sum 1, the number of codes with maximum length must be even. (If you have n codes of maximum length k, they add up to $n \cdot 2^{-k}$. If n is odd you can't get rid of the $2^{-k}$ and the sum cannot be 1). You prove Apass-Jack's claim with complete induction.

---
Tags: information-theory, entropy, huffman-coding
---


# Question
Title: Reducing linear programming to positive linear programming
Suppose we have an oracle that solves problems of the form

\begin{align\*} \text{maximize} ~~ & c^T x \\ \text{subject to} ~~ & A x = b, x\geq 0 \end{align\*}

when $c\geq 0$ (all coefficients in the maximization target are non-negative).

Can it be used to efficiently solve general linear programs?

FAILED ATTEMPT #1: replace each variable $x\_i$ that appears with a negative coefficient in $c^T x$, with another variable $y\_i := - x\_i$. Unfortunately, this $y\_i$ does not satisfy the non-negativity constraint.

FAILED ATTEMPT #2: Ensure that all elements in $b$ are non-positive (multiplying the equation by -1 if necessary). Then create the dual LP:

\begin{align\*} \text{maximize} ~~ & - b^T y \\ \text{subject to} ~~ & A^T y \geq c \end{align\*}

Here, all the coefficients in the objective are non-negative. However, this form does not match the form that the oracle can solve, since the constraints are not equational constraints and the variables $y$ are unbounded.

# Answer
> 5 votes
You can add a variable $y$ and a linear equality $y=c^Tx+c\_0$ for some $c\_0$. Then, the original problem is equivalent to maximizing $y$ in the new system.

Except for the condition $y\geq 0$. That is where $c\_0$ comes in. We need to make $c\_0$ large enough that for *some* feasible $x$ (that is $Ax=b$ and $x\geq 0$ hold) we have $c^Tx+c\_0\geq 0$. In that case it does not matter that non-negativity cuts away parts of the feasible space. The optimal value is still the same.

So how to choose $c\_0$? I am not an expert in linear optimization. Is finding some feasible $x\_0$ easier than finding one that maximizes the objective function? If so, we can take $c\_0$ to be $-c^Tx\_0$.

If the given coefficients are rationals, there is another way. First, let us establish that the polytope of feasible $x$ has vertices (unless it is empty): Let $p$ be a point in a minimum-dimensional boundary cell of said polytope. For contradiction, assume that the dimension of this cell is $\geq 1$. Then, there is a different point $q$ in the same cell. As the cell has minimum dimension, it is unbounded, so points of the form $r=p+t(q-p)$ are in the same cell and thus in the polytope. As $q-p\not=0$, some such $r$ have negative coordinates, contradicting the polytope condition $r\geq 0$.

Now, make all coefficients of $A$ and $b$ integer by multiplying with the common denominator. Let $n$ be the dimension (the length of the vector $c$) and let $M$ be the maximum absolute value of any coefficient of $A$, $b$, or $c$. Then we can bound the coordinates of any vertex of the feasible polytope by $n!\cdot M^n$. Thus, choose $c\_0:=n\cdot n!\cdot M^{n+1}$.

\[EDIT\]

Yet another approach, in case you are willing to call the oracle multiple times: First, try the above with $c\_0=0$. If you get a solution or the answer "unbounded", you are fine. If the answer is "unsolvable", you need to find out if there are solutions with negative objective function. Hence, set $z=-c^T$ and maximize $z$ instead. If you get a solution, you can use it as $x\_0$. If you get "unsolvable" again, you are done as well. The last case is the answer "unbounded". Then, you need to try out ever larger $c\_0$ (for few oracle calls, use a fast-growing function; the Ackermann function may do) until you get a solution.

# Answer
> -1 votes
You can replace a variable x that has no restriction to be positive with two variables $x^+ - x^-$ where both $x^+$ and $x^-$ are restricted to be positive. All their coefficients will be identical except that they have the opposite sign.

In the simplex algorithm, it is always possible to put only one of these into the basis. Actually, you can avoid any additional calculations by just keeping track whether any basis variable is currently positive or negative.

---
Tags: linear-programming
---


# Question
Title: Is There An Established Way To Send Code Over a Network?
Let's say I have two computers on a network. I want to write code in some language on machine A, send the code in an efficient way over a network, and run the code on machine B. It seems to me that this would be inherently slow and would run into a bundle of problems (not having required dependencies) but perhaps some work has already been done on this problem? Is there any known processes or systems that already do this?

# Answer
From memory Java applets and COM components could do this (But mostly discontinued due to security reasons) The approach was mostly based on a pull strategy. That is Machine B pulled code from Machine A and then executed in Machine B.

OS and application updates (e.g. Windows Update) also do this approach. They download the update from a different machine and execute locally.
> 1 votes

---
Tags: distributed-systems
---


# Question
Title: Word-hyphenation algorithm for monospaced fonts
I have seen a few standard hyphenation algorithms for non-monospaced fonts, where you are free to squeeze and separate words and letters, but I haven't seen any related to monospaced fonts specifically. Wondering if there are any good resources on the topic. Such as how to best properties to use when hyphenating a monospaced word, etc.

# Answer
I assume you are asking about algorithms to decide where to split lines when formatting paragraphs, not about algorithms for deciding where it is legal to insert hyphens into a word?

All algorithms for this kind of problem go back to Knuth, Donald E.; Plass, Michael F. (1981), "Breaking paragraphs into lines", Software: Practice and Experience 11 (11): 1119–1184, doi:10.1002/spe.4380111102, which is also described in this entry on tex.stackexchange: https://tex.stackexchange.com/a/109818/28084.

The key is to *define an objective function* and then come up with an efficient algorithm for optimizing the objective function. Cormen, Leiserson, Rivest, and Stein, *Introduction to Algorithms*, 3/e, 2009 gives a super-simplified version in problem 15-4 (page 405) that asks you to minimize the objective function "sum of cubes of number of extra spaces required on each line" using an efficient dynamic programming formulation.

In Knuth and Plass they demonstrate that a bunch of variants of the objective function (including adding a linear penalty for each hyphenation break that is added, and accounting for the extra space consumed by the hyphen) don't require you to go beyond the efficient dynamic programming formulation.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Removing max number of edges while keeping minimum distances
Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there are two types of edges - black and red. The black edges are in the form (1,x) where x is a vertex and red edges can be any pair (x,y) .My question is how can I find the maximum number of black edges I can remove so that the minimal distance from 1 to any other vertex is preserved?

# Answer
> 1 votes
Your graph has no negative edges, then you can do a full exploration using Dijkstra algorithm starting from node 1. You stop when you have explored all nodes. Just record every black edges you cross.

An important point is, when you have several equal distances on a step, always give priority to red edges.

---
Tags: algorithms, graphs
---


# Question
Title: How does the equation for min heap array indexing work?
I've been reading about min heaps, currently looking at this article, and I am very confused by something.

The article makes the following statement:

> If a given node is located at index 'x' in the array, its left child exists at index = 2x, and its right child exists at index = 2x + 1. Each node's parent exists at index = x / 2 (rounded down).

It gives this example:

This min heap is represented in the array `[100, 19, 36, 17, 3, 25, 1, 2, 7]`.

But this doesn't jive with the preceding statement about indexing. `36` can be found at index `2`, and `2 * 2` is `4`. But index `4` is 3-- the right child of the 19 node, not the left child of the 36 node.

What am I missing here?

# Answer
Start indexing at $1$, then everything will be fine.

Want to start at $0$? That is no problem, but one has to adjust the formula's. Children of $x$ can be found at $2x+1$ and $2x+2$.
> 2 votes

---
Tags: heaps
---


# Question
Title: Proof of the master thorem case with floors and b = 2
This question is related to my previous one.

Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b \> 1$ and $f(n) = \Theta(n^{\log\_ba})$. Then $T(n) = n^{\log\_ba} + \sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1} a^{j}f(n\_j) = n^{\log\_ba} + g(n)$. It should be proved that $g(n) = \Omega(n^{\log\_ba}logn)$.

It's seems not to be a difficult problem as there is the proof of the similar one (for the upper bound and a presence of the ceiling operation in recursive calls) in the *Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein*. But I found it becomes more difficult to deal with if $b=2$:

$n\_j = \begin{cases} n, & \text{if j = 0} \\ \lfloor n\_{j-1}/b \rfloor, & \text{if j \> 0} \end{cases}$

$n\_j \geq n/b^{j} - \sum\_{i=0}^{j-1}1/b^{i} \geq n/b^{j} - \sum\_{i=0}^{\infty}1/b^{i} = n/b^{j} - b/(b-1)$

By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1}a^{j}(\frac{n}{b^{j}} - \frac{b}{b-1})^{log\_ba} =$

$c n^{log\_ba}\sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1}(1-\frac{b^{j}}{n}\frac{b}{b-1})^{log\_ba} \geq$ //where $\frac{b^{j}}{n} \le 1$

$c n^{log\_ba}\sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1}(1-\frac{b^{\lfloor log\_bn \lfloor -1 }}{n}\frac{b}{b-1})^{log\_ba} = $

$c n^{log\_ba}\sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1}(1-\frac{b^{\lfloor log\_bn \lfloor }}{n}\frac{1}{b-1})^{log\_ba} \geq$

$c n^{log\_ba}\sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1}(1-\frac{1}{b-1})^{log\_ba}$

Note iff $b = 2$ than $(1-\frac{1}{b-1})^{log\_ba} = 0$ and can not be denoted as an allowable constant in terms of $\Omega$ (it must be a positive one).

I tried to prove that particular case in another way, if $n\_j \geq \frac{n}{2^{j}} - (2 - \frac{1}{2^{j-1}})$ (it is the sum of the geometric progression without the limit) but finally failed because of the same issue.

# Answer
In fact, let $b=1.5$, we will have $(1-\frac{1}{b-1})\<0$, in which case $(1-\frac{1}{b-1})^{\log\_ba}$ does not even make much sense!

The problem can be traced to when the following too-relaxing relaxation was made.

$$1-\frac{b^{j}}{n}\frac{b}{b-1} \geq 1-\frac{b^{\lfloor \log\_bn \rfloor -1 }}{n}\frac{b}{b-1}$$

---

Can we find $\Theta(\log n)$ times when the left side is greater than, for example, $\frac12$? That should be enough to generate the factor $\log n$ needed.

Let us solve the following equation for the index $j$. $$1-\frac{b^{j}}{n}\frac{b}{b-1} \gt \frac12$$ We get $$j \lt \log\_b\left(\frac{n(b-1)}{2b}\right)=\log\_bn-\log\_b\frac{2b}{b-1}=\frac{\log n}{\log b}-c\_0$$ where constant $c\_0=\log\_b\frac{2b}{b-1}$.

The above should be enough to set you moving for a complete proof, although there might be a couple of other minor technicalities ahead.
> 1 votes

---
Tags: algorithm-analysis, master-theorem
---


title: How to measure "sortedness"

text:
# Question
Title: How to measure "sortedness"
I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean it's basically as far as possible from being either sorted or reverse sorted.

# Answer
> 35 votes
No, it depends on your application. The measures of sortedness are often refered to as *measures of disorder*, which are functions from $N^{\<N}$ to $\mathbb{R}$, where $N^{\<N}$ is the collection of all finite sequences of distinct nonnegative integers. The survey by Estivill-Castro and Wood \[1\] lists and discusses 11 different measures of disorder in the context of adaptive sorting algorithms.

The number of inversions might work for some cases, but is sometimes insufficient. An example given in \[1\] is the sequence

$$\langle \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n, 1, \ldots, \lfloor n/2 \rfloor \rangle$$

that has a quadratic number of inversions, but only consists of two ascending runs. It is nearly sorted, but this is not captured by inversions.

---

\[1\] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.

# Answer
> 10 votes
Mannila \[1\] axiomatizes presortedness (with a focus on comparison-based algorithms) as follows (paraphrasing).

> Let $\Sigma$ a totally ordered set. Then a mapping $m$ from $\Sigma^{\star}$ (the sequences of distinct elements from $\Sigma$) to the naturals is a *measure of presortedness* if it satisfies below conditions.
>
> 1. If $X \in \Sigma^{\star}$ is sorted then $m(X) = 0$.
> 2. If $X,Y \in \Sigma^{\star}$ with $X = x\_1 \dots x\_n$, $Y = y\_1 \dots y\_n$ and $x\_i \< x\_i \iff y\_i \< y\_j$ for all $i,j \in \[1..n\]$, then $m(X) = m(Y)$.
> 3. If $X$ is a subsequence of $Y \in \Sigma^{\star}$, then $m(X) \leq m(Y)$.
> 4. If $x\_i \< y\_j$ for all $i \in \[1..|X|\]$ and $j \in \[1..|Y|\]$ for some $X,Y \in \Sigma^{\star}$, then $m(X \cdot Y) \leq m(X) + m(Y)$.
> 5. $m(a \cdot X) \leq |X| + m(X)$ for all $X \in \Sigma^{\star}$ and $a \in E \setminus X$.

Examples of such measures are the

* number of inversions,
* number of swaps,
* the number of elements that are not left-to-right maxima, and
* the length of a longest increasing subsequence (subtracted from the input length).

Note that random distributions using these measures have been defined, i.e. such that make sequences that are more/less sorted more or less likely. These are called *Ewens-like* distributions \[2, Ch. 4-5; 3, Example 12; 4\], a special case of which is the so-called *Mallows* distribution. The weights are parametric in a constant $\theta \> 0$ and fulfill

$\qquad\displaystyle \operatorname{Pr}(X) = \frac{\theta^{\\,m(X)}}{\sum\_{Y \in \Sigma^{\star} \cap \Sigma^{|X|}} \theta^{\\,m(Y)}} $.

Note how $\theta = 1$ defines the uniform distribution (for all $m$).

Since it is possible to sample permutations w.r.t. these measures efficiently, this body of work can be useful in practice when benchmarking sorting algorithms.

---

1. Measures of Presortedness and Optimal Sorting Algorithms by H. Mannila (1985)
2. Logarithmic combinatorial structures: a probabilistic approach by R. Arratia, A.D. Barbour and S. Tavaré (2003)
3. On adding a list of numbers (and other one-dependent determinantal processes) by A. Borodin, P. Diaconis and J. Fulman (2010)
4. Ewens-like distributions and Analysis of Algorithms by N. Auger et al. (2016)

# Answer
> 6 votes
I have my own definition of "sortedness" of a sequence.

**Given any sequence \[a,b,c,…\] we compare it with the sorted sequence containing the same elements, count number of matches and divide it by the number of elements in the sequence.**

For example, given sequence `[5,1,2,3,4]` we proceed as follows:

1) sort the sequence: `[1,2,3,4,5]`

2) compare the sorted sequence with the original by moving it one position at a time and counting the maximal number of matches:

```
        [5,1,2,3,4]
[1,2,3,4,5]                            one match

        [5,1,2,3,4]
  [1,2,3,4,5]                          no matches

        [5,1,2,3,4]
    [1,2,3,4,5]                        no matches

        [5,1,2,3,4]
      [1,2,3,4,5]                      no matches

        [5,1,2,3,4]
        [1,2,3,4,5]                    no matches

        [5,1,2,3,4]
          [1,2,3,4,5]                  4 matches

        [5,1,2,3,4]
            [1,2,3,4,5]                no matches

                ...

         [5,1,2,3,4]
                 [1,2,3,4,5]            no matches

```

3) The maximal number of matches is 4, we can calculate the "sortedness" as 4/5 = 0.8.

Sortedness of a sorted sequence would be 1, and sortedness of a sequence with elements placed in reversed order would be 1/n.

The idea behind this definition is to estimate the minimal amount of work we would need to do to convert any sequence to the sorted sequence. In the example above we need to move just one element, the 5 (there are many ways, but moving 5 is the most efficient). When the elements would be placed in reversed order, we would need to move 4 elements. And when the sequence were sorted, no work is needed.

I hope my definition makes sense.

# Answer
> 0 votes
If you need something quick and dirty (summation signs scare me) I wrote a super easy disorder function in C++ for a Class named Array which generates int arrays filled with randomly generated numbers:

```
void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

```

Function simply compares the value in each element to the index of the element + 1 so that an array in reverse order has a disorder value of 1, and a sorted array has a disorder value of 0. Not sophisticated, but working.

Michael

---
Tags: algorithms, algorithm-analysis, sorting, arrays
---


title: N subsets with a given sum?

text:
# Question
Title: N subsets with a given sum?
How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?

¹⁾ Not as in $P$, I just want something smarter than $O(n^{|S|})$.

---

**Ex.** Let’s say we want $n=3$ subsets with the sum of $K=3$ chosen from $S=\[1,1,1,2,2,2\]$.

The correct solution is $\[1,2\], \[1,2\], \[1,2\]$.

---

**Ex.** Let’s say we want $n=2$ subsets with the sum of $K=5$ chosen from $S=\[5,4,3,2,2,2,2,1\]$.

One correct solution is $\[5\], \[1,4\]$.

Another one would be $\[2,2,1\], \[2,3\]$.

---

Etc. Just *a* correct solution, regardless of which one.

# Answer
> 2 votes
Let us define a predicate
$$T(i,k\_1,...,k\_n)\in\\{True, False\\}$$ Where $T(i,k\_1,...,k\_n)$ means "using the $i$ first values of $S$, we can find $n$ disjoint subsets with sums $k\_1, ... k\_n$".
The answer you are looking for is $T(|S|,K,..,K)$ where $K$ appears $n$ times.
We have the following recurrence formula : $$T(i,k\_1,...,k\_n) = \left\\{ \begin{matrix} T(i-1,k\_1,...,k\_n) & \text{// we don't use value $x\_i$} \\ \vee T(i-1,k\_1-x\_i,...,k\_n) \text{ if $x\_i \geq k\_1$} &\text{// we put value $x\_i$ in set 1}\\ \vdots \\ \vee T(i-1,k\_1,...,k\_n-x\_i) \text{ if $x\_i \geq k\_n$} &\text{// we put value $x\_i$ in set n}\\ \end{matrix}\right.$$ This formula is a big boolean "or", I don't know how I could make it look better.
We also the following initialisation : $\forall i, T(i,0,...,0) = True$.
You can see it as a big $n+1$-dimensional array, where the first dimension has length $|S|$, and the others have length $K$, which gives $O(K^n|S|)$ values. In that array, all the values can be computed from the other values in time $O(n)$ (the big "or" is over $n+1$ values).
Therefore, the worst case complexity is $O(nK^n|S|)$.

About implementation, it might be easier to do with recursively with memorization. However, you're gonna blow up the stack really fast, so you might want to think of something iterative.

To get the actual values in each set, run a backtracking algorithm once you have that truth array.

# Answer
> 2 votes
This problem is strongly NP-hard because it generalizes the 3-Partition problem. That means that it has no efficient (polynomial-time) algorithm, unless P=NP.

# Answer
> -1 votes
Assuming the subsets are disjoint, we first assume we have a blackbox algorithm `SUBSET`, which given a set $S = \[x\_1, x\_2, x\_3,...x\_n\]$ and an integer $k$, will return a set $T$ such that $T$ is a subset of $S$, i.e $T \subset S$. Given a number $n$, which will be the number of subsets we want to generate, the algorithm is as follows.

```
ret = {}
(While n > 0)
     T = SUBSET(S,k)
     ret.add(T)
     S = S / T
     n -= 1
return ret

```

In this snippet, I assume $S$ is the initial subset, $k$ is the desired sum, and $n$ is the number of subsets we want. Each time we calculate a subset, we calculate the set difference of $S$ and $T$ and set the resulting set equal to $S$, essentially removing the element of $T$ from $S$. Now, for the implementation of `SUBSET`, if you go with the dynamic programming approach, you can achieve a runtime of $O(xnk)$, where $n = |S|$. More info on the dynamic solution can be found here. https://en.wikipedia.org/wiki/Subset\_sum\_problem#Polynomial\_time\_approximate\_algorithm. If you really want to optimize the runtime of SUBSET, the fastest algorithm I could find is outlined in this paper https://arxiv.org/abs/1507.02318, although it may not be practical to implement. If you're looking for a polynomial time algorithm, then I'm afraid you're out of luck since this problem reduces to `SUBSET`, which is an NP-Complete problem.

---
Tags: sets, subset-sum
---


# Question
Title: Bachmair and Ganzinger, ordering of equations
Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', page 4, defines an order on equations. (This is an arcane piece of machinery but a critical one in the overall attempt to get to the point where equations can be applied in one direction, thereby dramatically improving the performance of automated reasoning on problems involving equality.)

If $s \succ t \succ u$

Let $s\approx t$ have the multiset representation $\\{\\{s\\},\\{t\\}\\}$

Let $s\not\approx t$ have the multiset representation $\\{\\{s,\bot\\},\\{t,\bot\\}\\}$ where $\bot$ is a new symbol such that every existing symbol is greater than $\bot$.

Then $s\not\approx u \succ s\approx t$ even though $t \succ u$.

... wait, how? Sure, $s\not\approx u$ also contains a couple of occurrences of $\bot$, but what of that? $t \succ u \succ \bot$, so the comparison should be decided by $t$ vs. $u$; $\bot$ should not have enough weight to tip the balance, so to speak.

What am I missing?

(I have seen later writing that gives $s\not\approx t$ the multiset representation $\\{\\{s,s\\},\\{t,t\\}\\}$, and I see how this solves the problem, but I don't see how it is solved in the original version.)

# Answer
> 1 votes
A short answer to your question is to use the definition of multiset extension of a partial ordering.

We have the following:

1. Let $M = \\{s,\bot\\}$ and $N=\\{s\\}$. We have $M\succ M$ since $M(\bot) \> N(\bot)$ and there does not exist $x$ such that $N(x)\> M(x)$.
2. Let $M=\\{\\{s,\bot\\},\\{u,\bot\\}\\}$ and $N=\\{\\{s\\},\\{t\\}\\}$. We have $M(\\{s,\bot\\})\>N(\\{s,\bot\\})$ and by (1) $\\{s,\bot\\}\succ\\{s\\}$. Therefore $M\succ N$.

It would be interesting to see examples where the two ways of extending an ordering on equations to clauses disagree and discuss how that might affect the properties or performance of a rewrite-based prover.

---
Tags: logic, first-order-logic, automated-theorem-proving
---


# Question
Title: Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?
My book states that the language $$L\_1 = \\{a^nb^n\mid n\geq 1\\}$$ is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really imagine how this grammar should not be applicable or why it shouldn't be a valid type 3 grammar: $$S \to aS \mid bS \mid b\\,.$$

For my understanding this grammar produces the language in question and also fulfils the type 3 criteria.

# Answer
> 2 votes
$S\Rightarrow bS\Rightarrow baS\Rightarrow bab$.

However, $bab$ is not $a^nb^n$ for any $n$.

---

(**Exercise.**) Is the following grammar a grammar for $L\_1$?

$S \to Sa \mid Sb \mid a$

# Answer
> 1 votes
Your grammar produces every possible string that ends in $b$.

The proof that $\\{a^nb^n\mid n\geq 1\\}$ is not regular is standard and can be found in any textbook – use the pumping lemma, Myhill–Nerode or one of the other characterizations of regular languages.

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


title: What is the complement of a language?

text:
# Question
Title: What is the complement of a language?
If given any language L, how do I find the complement of said language?

I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-recognizable if the complement of that language, $\overline{L}$, is recognizable.

But given a specific language, I have a hard time figuring out what the actual complement is, and can thus not figure out if that complement is recognizable. An example problem is:

> Is the following language co-recognizable?
> $L$ = {$\<M\>$ | $M$ is a turing machine, and $1010 \notin{L(M)}$}

# Answer
Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything *not* in the set.

In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume $\\{0,1\\}$.

So in this case, the complement of that language is:

> The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.

Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.
> 11 votes

---
Tags: computability
---


title: Proccess scheduling arrival time

text:
# Question
Title: Proccess scheduling arrival time
If I have a set of processes, let's say 9 and I know the burst time and the waiting time for SJF algorithm and also know that processes arrive in groups of 3 processes at M1 moment, M2 moment, M3 moment (M1, M2 and M3 are given), how can I decide at what moment each process will arrive?

# Answer
> 0 votes
What are their execution time and possible start time and finish times? For each process time, its execution time is $\text{TAT}-\text{WT}$. Its start time should be WT plus one of 0, 12 and 24. Its finish time should be TAT plus one of 0, 12, 24.

$$ \begin{array}{|c|c|c|c|c|} \hline \text{Process} & \text{WT} & \text{TAT}&\text{Execution Time} & \text{Start Time} & \text{Finish Time} \\\hline P1 & 6 & 15 &9 & 6, 18, 30 & 15, 27, 39 \\\hline P2 & 3 & 6 &3 & 3, 15, 27 & 6, 18, 30 \\\hline P3 & 63 & 84 & 21 & 63, 75, 87&84, 96, 108 \\\hline P4 & 0 & 6 & 6 & 0& 6\\\hline P5 & 24 & 36 & 12 & 24, 36, 48& 36, 48, 60\\\hline P6 & 7 & 15 & 8 & 7, 19, 31 & 15, 27, 39\\\hline P7 & 24 & 39 & 13 & 24, 36, 48 & 39, 51, 63\\\hline P8 & 6 & 12 & 6 & 6, 18, 30 & 12, 24, 36\\\hline P9 & 3 & 7 & 4 & 3, 15, 27 &7, 19, 31\\\hline \end{array} $$

What can we say about start times and finish times?

* The start time of any process except the first process must be the finish time of another process.
* The finish time of any process except the last process must be the start time of another process.

What does it mean by SJF? It means among all jobs that have been queued/submitted, the shortest job will be executed first.

So our task is to select 10 numbers $0, 6, \cdots$ from the column "Start time" and "Finish Time" so that

* each number must appear in column "Start Time" and column "Finish Time", except the first number 0, which only appears in column "Start Time" and the last number, which only appears in column "Finish time".
* The sequence starts with 0, 6 since, as you have observed, the first process started at 0 and ended with at 6.
* For the initial numbers that are not greater than 12, their successive differences should become bigger and bigger. For the next segment of numbers that are not greater than 24, their successive differences should become bigger and bigger. For the last four numbers, their successive differences should become bigger and bigger.

There should be enough hint to set you moving again.

Just in case you are still stuck, move your mouse over the following to reveal the spoiler.

> Check the column "Finish Time". Which process must finish last? Then which process' finish time could be the last process' start time? Then which process' finish time could be that process' start time? And so on.
> It turns out the condition SJF is not needed at all. This problem can be solved as long as the processes are executed one after another.
> On the other hand, SJF can be helpful. The three processes with longest execution time, P3, P5 and P7 must be the last three jobs since all of them started later than 24. Since SJF, $P5\prec P7\prec P3$.

---
Tags: scheduling, process-scheduling
---


# Question
Title: Doubt regarding foreign key and referential integrity
I am studying database from Database System Concepts.

The author was explaining foreign keys and referential integrity with the help of following schemas:

$$ instructor(\underline{ID},\space name,\space dept\text\_name,\space salary)$$ $$ course(\underline{course\text\_id},\space title, \space dept\text\_name,\space credits) $$ $$ department(\underline{dept\text\_name}, \space building,\space budget)$$ $$ section(\underline{course\text\_id,\space sec\text\_id,\space semester,\space year},\space building,\space room\text\_no,\space time\text\_slot\text\_id) $$ $$ teaches(\underline{ID,\space course\text\_id, \space sec\text\_id,\space semester, \space year})$$

The primary keys are underlined.

The relation $section$ is used so that each course could be offered multiple times, across different semesters, or even within a semester.

Foreign key was explained with the help of schemas $instructor$ and $department$. The attribute $dept\text\_name$ in in $instructor$ is a foreign key from $instructor$ referencing $department$.

**It need not be the case that all** **$dept\text\_name$ values are referenced by $instructor$ relation.**

Referential integrity constraint was explained with the help of $section$ and $teaches$ schema.

If a section exists for a course it must be taught by at least one instructor(it could be taught by more than one instructor)

So **all** the combinations of $(course\text\_id,\space sec\text\_id,\space semester, \space year)$ that appear in $section$ relation must also appear in $teaches$ relation.

But we cannot declare a foreign key from $section$ to $teaches$ since multiple instructors could teach a single section.

We could define a foreign key from $teaches$ to $section$.

Since we could form a referential integrity constraint from $instructor$ to $department$ by using foreign key but without foreign key we have referential integrity constraint from $section$ to $teaches$.

So how is referential integrity different from foreign key constraints?

Also if you know some free resources that could clear database concepts please share.

# Answer
In general the “referential integrity constraint” is a constraint that states that a foreign key **must** always be equal to some primary key of a tuple in the referred relation (so establishing a correspondence between a tuple in the first relation and another (and only one) in the other relation. If the constraint is violated, that is if the value of the foreign key of a tuple is not equal to the value of the primary key of another tuple, this means that the foreign key has lost its integrity, since it “does not refer anything”, like a “dangling reference” in a programming language.

It is a duty of the Database Management System to enforce this constraint, and prevent any violation of it through some policy, that can be specified by the database administrator (“on delete cascade, no action”, etc.)

In the book that you cited, it is in fact said that:

> a referential integrity constraint requires that the values appearing in specified attributes of any tuple in the referencing relation also appear in specified attributes of at least one tuple in the referenced relation.

The comment related to the example explains that, even if, according to the rules of the university, each `section` should be taught by at least one instructor, it is not possible to express such constraint in the database designed, since it is not possible to define the attributes of `section` as foreign key for the relation `teaches` (since they do not form a primary key in such relation).

Note that this depends on the fact that the only way to represent a 1-n relationship between two sets of data in the Relational Data Model is to use a foreign key in the relation where there is only one element (at maximum) in the other relation, not vice-versa. So the foreign key is from `teaches` to `section`, since a tuple in `teaches` can be related only to one tuple in `section`.
> 1 votes

---
Tags: database-theory, databases, relational-algebra
---


# Question
Title: Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?
For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

My attempt to prove this was using a contradiction argument, supposing there was a common edge across 2 different min-cuts. Also, there is an edge in one min-cut that does not exist in the other, and idem for the other cut. Name these e1 and e2.

I managed to prove that the common edge must be an edge on a path between an end-point of e1 and one of e2.

There is a figure I drew to understand the situation better:

# Answer
> 1 votes
> Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?

There is no "why" here since 2 different edge minimum-cuts in an undirected multigraph can have one edge in common.

Here is an example. Edge set $\\{AB,AC\\}$ is a minimum cut. Edge set $\\{AB,BC\\}$ is another minimum cut. They have edge AB in common.

> For the proof of a maximum of $\binom n2$ min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

I do not think we need that (non)-fact. The random contract algorithm will find each min-cut with a probability of no less than $\frac1{\binom n2}$. Since that algorithm only find one min-cut each time, there are at most $\binom n2$ min-cuts.

---

Here are several exercises to enhance our understanding of the intersection of two min-cuts.

(**Exercise 1**). Find an undirected multigraph in which 2 different edge minimum-cuts have 2 edges in common.

(**Exercise 2**). Find an undirected simple graph in which 2 different edge minimum-cuts have 2 edges in common.

(**Exercise 3**). Given a positive integer $n$, find an undirected simple graph in which 2 different edge minimum-cuts have $n$ edges in common.

---
Tags: graphs, combinatorics, probabilistic-algorithms, minimum-cuts
---


# Question
Title: Convert NURBS curve into Cubic Bezier Curve
From this:

> Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials.

I don't understand what it means, and don't yet know if it really means that there is absolutely no way to convert a NURBS curve into a cubic bezier curve (or spline, since I think bezier splines are multiple bezier curves connected together). I get confused because I also read this:

> No matter it is Uniform or Non-uniform, NURBS is just made by one or a bunch of Bezier curve; and if you bear with me, what you need to know about NURBS math is just the Bezier-series-equations.

Even just saw this:

> NURBS curve can always be converted to piecewise Bézier by repeated knot-insertion.

So some say it's possible, others not.

If it is true that you *can't* model NURBS with Bezier curves, then I would like to know why rational functions and polynomials can't be morphed into one another, at least at a high level (what is preventing the transformation between the two). In that case I would also like to know if there is a way to *approximate* a NURBS curve with Bezier curves, even though you lose some precision or the curve changes slightly. I would then just like to know how much you lose when approximating a NURBS curve with a Bezier curve, and what the algorithm or technique is called so I can further explore how to do it. If there is a standard algorithm for accomplishing this, that would be cool to know instead too.

# Answer
I assume that your cubic spline is non-rational, meaning $w$ = 1, then this is in general true that exact conversion is not possible. NURBS are rational, so you can model conics, say circle whereas Bézier cannot. There is special case: rational Bézier curve, which could be used in place of NURBS.

This simply means that you can draw circle, and only approximate it with Bézier.

To approximate, it depends on degree of curve: least squares method is stable and fast for low degrees, but fails (error is not equal along curve and huge) for higher degrees. Another idea is like in de Casteljau, recursively subdivide curve and use piecewise approximation. This idea generates lots of points and is numerically less stable than least squares.

For general NURBS of order 6+, approximation technique must be of order at least 6+, but it converges slowly.

In any case, finding Bézier curve through points from NURBS is way to go.

Another option is lossless conversion from NURBS to piecewise Rational B-Splines (URBS) (after conversion these are uniform, but no precision is lost), then via Boehm algorithm or Greville points convert B-spline to R-Bézier (here again, nothing is lost) and then project it to NR-Bézier (approximation, i.e. https://ieeexplore.ieee.org/document/6658158 or https://arxiv.org/pdf/1212.3385.pdf, here conics are lost).

Errors are seen about five-six places after decimal point for nasty splines (these that cannot be exactly recovered, as oposed to nice, which are wxact), so for any drawing purpose it is not visible, unless this is for milling machine, but hey, CNC supports (G-code G02) arcs anyway.
> 4 votes

---
Tags: algorithms, computational-geometry, graphics, topology, digital-curve
---


# Question
Title: Is there an existing algorithm for this type of sorting?
This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted books, and must quickly sort them into alphabetical order.

A number of commenters pointed out that a far more practical method for real-life sorting would be to take the first letter of each book and put it into 26 different piles (an A pile, a B pile, down to a Z pile.) Then use a conventional sorting method (insertion / quick sort etc.) for each of the 26 sub-piles (which would contain around 50 books each, assuming a roughly even distribution of letters. Or you could repeat the same process if the sub-pile is significantly large, sorting the As into ABs, ACs, ADs and so on.

Is there a name of this kind of sorting algorithm?

# Answer
This is called *bucket sort*: split your data range into $k$ "buckets" ($O(k)$), put the data into the buckets ($O(n)$), sort each bucket (however you like), then concatenate all the buckets ($O(k)$). If the sorting is faster than $O(n \log n)$, then the whole algorithm runs faster than any comparison-based sort possibly could!

The problem is that it depends on the distribution of the data. If 99% of your book titles start with `A`, this gives no real benefit at all! And it doesn't work on data that can't be divided into buckets.

A variation of this, "radix sort", is basically the same except in binary (and with some extra recursion). It runs in $O(wn)$, where $w$ is the bit length of your data (the "word size").
> 2 votes

---
Tags: algorithms, sorting
---


title: What is happening during "table walk"?

text:
# Question
Title: What is happening during "table walk"?
I am trying to understand what is a table walk. I have found when it occurs - whenever there is a TLB miss. If no descriptor is found – TLB miss occurs and further behavior depends on the implementation of a paging unit. (TLB - Translation look aside buffer)

But i still do not understand what exactly happens during table walk.

# Answer
> 4 votes
In present computers, the processor manipulates virtual addresses that are generated by the compiler, but the real physical address is determined at run time by the OS.

To do that, memory is organized in pages. Typical page size is 4kB (2^12bytes). To translate from virtual addresses to physical addresses, an address is considered as having two fields: address of a byte within a page (12 bits displacement) and page address (the remaining high order bits). Translation consists to replace virtual page address in he processor by physical address, with respect to a table generated at process creation by the OS (page table).

The problem is that these table can be *HUGE*. With 64bits virtual addresses (as in present processors), this page address have (64-12)bits (for 4kB pages) and a page table will hold 2^52 page addresses. This is an insane size (~10^18B) largely above most computer physical memory size. Fortunately, these tables are mostly empty and only a small part of potential virtual addresses have a physical translation.

To cope with that, page tables are multi level. Virtual addresses are split in fields addressing the successive table levels. For instance, with a 4kB page, and 64bits (8B) addresses, it is possible to store 512(2^9) addresses per page. The first 9 high order bits select an address within a page, that will give the address of a new page holding 512 page address. The next 9 high order bits select a new page, and so on.

If a page address is 52 bits in at most 6 steps, we can get the final physical page address corresponding to a logical page address.

This "page walk" or "table walk" is a complex process that requires several memory accesses and that must be done for *every* memory access.

To reduce the translation time, the TLB memorize recent correspondences between virtual and phys page addresses. If the physical translation of a virtual address is in the TLB, it is immediately available.

And if translation is not in the TLB, it is recreated by table walk. TLB misses (and table walk) are very expensive. If all the page tables are already copied to cache memory, it will require some tens of cycles. But if the TLB miss also implies cache misses, the time will be measured by hundreds of cycles.

There are several good tutorials on these problems. Look for instance at the wikepedia page that give good graphical illustrations of table walk. https://en.wikipedia.org/wiki/Page\_table

---
Tags: computer-architecture
---


title: Ketama hash explanation

text:
# Question
Title: Ketama hash explanation
(I originally posted this on stackoverflow but thought it would be a better fit here)

I'm trying to understand the Ketama hash code used in consistent hashing.

link and snippet below:

```
public static Long md5HashingAlg(String key) {
    MessageDigest md5 = null;
    try {
        md5 = MessageDigest.getInstance("MD5");
    } catch (NoSuchAlgorithmException e) {
        log.error("++++ no md5 algorythm found");
        throw new IllegalStateException("++++ no md5 algorythm found");
    }
    md5.reset();
    md5.update(key.getBytes());
    byte[] bKey = md5.digest();
    long res = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF);

    return res;
}

```

I think I understand what the code is doing, but I don't get why they're doing it. Particularly, I'm wondering why:

1. the code discards the least significant 8 bytes of the 16-byte MD5 and uses only the first four (bKey\[0\] through bKey\[3\]).
2. the code "flips" the significant bytes meaning that, of the 4 bytes from 1., the least significant now become the most significant (at least that's what I understand happens from the `& 0xff`s and left shifts).

I also came across another piece of code that uses the same logic as above, but in addition performs an `& 0xffffffffL` on the result to "truncate to 32-bits".

link and snippet:

```
case KETAMA_HASH:
    byte[] bKey = computeMd5(k);
    rv = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8)
        | (bKey[0] & 0xFF);
    break;
    default:
    assert false;
}

return rv & 0xffffffffL; /* Truncate to 32-bits */

```

Could someone help me understand the rationale behind picking these particular bytes and re-arranging them in this particular fashion?

# Answer
> 4 votes
This is simply a way to generate 32-bit hash for the string. Assuming that MD5 is a good cryptographic hash function, it doesn't matter which bits you take from the hash and in which order you arrange them (as long as they are different bits). The behavior of the bits should be equally unpredictable.

There's no explanation, why exactly 32 bits are required, though my guess is that it enables the use of simple integer types in the code.

---
Tags: hashing
---


# Question
Title: What is the difference between R precision and precision at K?
I am trying to understand the difference between these two but it looks like as if they are calculated the same way. What is the difference?

R precision:

> R precision is the precision at the Rth position in the ranking of results for a query that has R relevant documents.

Precision at K:

> Precision at K is calculate for only K documents. Documents ranked lower than K are ignored.

# Answer
**R-Precision**

R-Precision is defined as $\frac{r}{R}$, which is the ratio between all the relevant documents retrieved until the rank that equals the number of relevant documents you have in your collection in total ($r$), to the total number of relevant documents in your collection $R$.

Suppose in your collection there are 100 documents in total, 30 of which are relevant ($R = 30$), the rest irrelevant. So you retrieve the first 30 documents (because 30 are relevant in total in your collection) and, say, 10 of them are relevant ($r = 10$). Your R-Precision is then $\frac{10}{30} = \frac{1}{3}$.

**Precision@K**

Precision@K is defined as the precision at rank $k$, which is more intuitive if you know about the definition of precision itself. Suppose your system retrieves 10 documents, where the relevant ones are at ranks ${1,3,6,7,9}$ and you want to know how 'well' your system does until rank 5 ('well' depends on the objective of your system of course but here we'll say we want high precision at low ranks). So you compute your *Precision@5*, which is the ratio of the number of relevant documents until (including) rank 5 to the total number of documents until $k$ (this number is $k$ itself). Your Precision@K where $K = 5$ is therefore $\frac{2}{5}$.

Youc an see that R-Precision is a measure that allows for assessment of your entire system whereas Precision@K really only takes the documents until $K$ into account. Depending on what you want to measure, either of them may be suitable.
> 15 votes

# Answer
In addition to what @simonst told, I'm gonna add these:

### Disadvantage of Precision@K:

Precision at K has this disadvantage that the total number of relevant documents in the collection has a strong influence on this metric.
For example, a perfect system, could only achieve a precision@20 of 0.4, if there were only 8 documents relevant to an information need.

---

### R-Precision solves that issue:

Actually R-Precision is the same as **Precision@X** where **X** is the total number of relevant documents in the collection. A perfect system could score 1 for each query, if R-Precision is used.
> 5 votes

---
Tags: information-retrieval
---


# Question
Title: Time complexity of this solution to N-queens problem
I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of them). The relevant code is briefed below.

```
bool isSafe(int board[N][N], int row, int col)
{
    int i, j;

    /* Check this row on left side */
    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    /* Check upper diagonal on left side */
    for (i=row, j=col; i>=0 && j>=0; i--, j--)
        if (board[i][j])
            return false;

    /* Check lower diagonal on left side */
    for (i=row, j=col; j>=0 && i<N; i++, j--)
        if (board[i][j])
            return false;

    return true;
}

/* A recursive utility function to solve N
   Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
    /* base case: If all queens are placed
      then return true */
    if (col >= N)
        return true;

    /* Consider this column and try placing
       this queen in all rows one by one */
    for (int i = 0; i < N; i++)
    {
        /* Check if queen can be placed on
          board[i][col] */
        if ( isSafe(board, i, col) )
        {
            /* Place this queen in board[i][col] */
            board[i][col] = 1;

            /* recur to place rest of the queens */
            if ( solveNQUtil(board, col + 1) )
                return true;

            /* If placing queen in board[i][col]
               doesn't lead to a solution, then
               remove queen from board[i][col] */
            board[i][col] = 0; // BACKTRACK
        }
    }

     /* If queen can not be place in any row in
        this colum col  then return false */
    return false;
}

/* This function solves the N Queen problem using
   Backtracking. It mainly uses solveNQUtil() to
   solve the problem. It returns false if queens
   cannot be placed, otherwise return true and
   prints placement of queens in the form of 1s.
   Please note that there may be more than one
   solutions, this function prints one  of the
   feasible solutions.*/
bool solveNQ()
{
    int board[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    if ( solveNQUtil(board, 0) == false )
    {
      printf("Solution does not exist");
      return false;
    }

    printSolution(board);
    return true;
}

```

From what I can tell, the recurrence is `T(n) = n*T(n-1) + N*n`, which leads to `O((n+1)!)`. When one more recursive call is made, at least one more `isSafe()` should return false. So the number of recursive calls decreases by at least 1 each time. And for the overhead in `isSafe()`, since `col` rows has been filled already, there are at most `min(col, N-col+1)` iterations of `for (i = 0; i < col; i++)`. But the `for` loop in `solveNQUtil()` runs a fixed number of `N`. That's why `N*n` exists.

But many people argue that N-queen runs `O(n!)` with recurrence `T(n)= n*(T(n-1) + O(n))`, such as here and comment on geeksforgeeks. So I start doubting myself.. surely `O((n+1)!) != O(n!)`.

Could anyone here throw some light on this? Have been struggling with it for a while.

# Answer
> 2 votes
Your analysis would be reasonable for rooks, but not for queens. For example, in the second row there are not n-1 possible positions, but n-2 in two cases and n-3 in most cases. Now big-O provides an upper bound, but it is an upper bound that vastly overestimates the effort needed.

---
Tags: algorithms, algorithm-analysis, asymptotics, search-algorithms, backtracking
---


# Question
Title: How to find the angle of an arc to draw graphic
I would like to draw an arc from a specific point to a goal point, during the process of drawing a larger path. I would like to do it using bezier curves, which aren't adequate for modeling circular arcs, but these equations found here seem to potentially estimate the arc pretty well (I can't tell if these equations correctly implement the circular arc using cubic Bezier curves (yet), but it seems like a good start). Here is the equations from that link.

```
start coordinate = {
  x: R,
  y: 0
}

control point 1 = {
  x: R,
  y: R * 4/3 * tan( phi / 4)
}

control point 2 = {
  x: R * ( cos(phi) + 4/3 * tan( phi/4 ) * sin(phi) ),
  y: R * ( sin(phi) - 4/3 * tan( phi/4 ) * cos(phi) ),
}

end coordinate = {
  x: R * cos(phi),
  y: R * sin(phi)
}

```

So let's say I start with a drawing of a path composed of some stuff, in this case just a few connected line segments (doesn't matter what they are):

Then what we want to do next, *from the current point we left off at*, is draw an arc. This is what that arc might look like:

You can see that there is a *center* where we can draw a radius, and a goal point where the arc ends (so it doesn't complete a whole circle).

My question is, how to determine the angle `phi` (in the equation above). That way I can use the equation. I am not sure what my current orientation is, if it is all relative to a global coordinate space or what. This is for traditional graphics. So need to figure that part out. Let's say it is a global coordinate space and not relative to the direction I moved along the path. Then this would be the angle:

I don't know, I'm already confused. So somehow I need to figure out some angle, which I'm not sure what to do. From there I think I could figure out the rest. Any help would be appreciated.

After the radius is found, then these equations above would take my simple circular arc, and turn it into a cubic Bezier equation so hopefully it could be drawn in an environment that only supports that and not arcs.

# Answer
> 0 votes
I think you have to determine the center C of your circle first. From your drawing, I suppose you want the last black segment to be tangeantial to the circle. Let say this last segment coordinates are P0 (x0, y0) and P1 (x1, y1).

Then the vector is:

```
vy = y1-y0
vx = x1-x0
with norm vr = sqrt(vy²+vx²)

```

And the vector **vc** from P1 to C is (2 choices depending on orientation):

```
vcy = +R*vx/vr or -R*vx/vr
vcx = -R*vy/vr or +R*vy/vr

```

then you obtain C coordinates (cx, cy) applying **vc** to P1. Now, your rotation angle phi must be expressed in the Cxy frame whatever the curve equation you use. The translation from (X, Y) in Cxy to (x, y) in Oxy is:

```
y = Y+cy
x = X+cx

```

Now about Bezier cubic curves, the equations you give assume you are starting at theta0=0 which is not the case on your figure. You can compute the starting angle with arctan2 (implemented on most of languages):

```
theta0 = arctan(-vcy, -vcx)

```

Then to plot a large angle arc with Bezier you actually have to cut it in small angle curves (let's say 30° max). So cut the (theta0, theta0+phi) angle into several (a, b) angles. NB: phi is negative on your figure (clockwise).

For every (a, b) angle, your Bezier cubic curve equation in Oxy frame is then:

```
K= 4/3 * tan( (b-a)/ 4)

start : y = cy+R*sin(a)
        x = cx+R*cos(a)

cp1 : y = cy+R*(sin(a)+K*cos(a))
      x = cx+R*(cos(a)-K*sin(a))

cp2 : y = cy+R*sin(b)- K*cos(b))
      x = cx+R*cos(b)+ K*sin(b))

end : y = cy+R*sin(b)
      x = cx+R*cos(b)

```

I did not not check these equations, I hope there is no mistake in.

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


# Question
Title: Confusion about proof of undecidability of REGULAR TM in Sipser's book
in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR\_TM which is described as follows :

`REGULAR_TM = { <M> | M is a Turing machine and L(M) is regular language }.` Well, Sipser says that this is an undecidable language since we cannot have a decider to decide this language. Because if we could, we could create a TM that decides ATM which we know previously that is undecidable. so this could cause a contradiction. Here is the proof from this book :

Proof. We let R be a TM that decides REGULAR\_TM and construct TM S to decide ATM. Then S works in the following manner.

S = "On input `<M, w>`, where M is a TM and w is a string:

1. Construct the following TM M2.

M2 = "On input x:

```
  1. If x has the form 0^n 1^n, accept.

  2. If x does not have this form, run M on input w and accept if M accepts w."

```
2. Run R on input `<M2>`.
3. If R accepts, accept; if R rejects, reject."

Now my question is, is this kind of constrcuting a TM S correct? the part that is really confusing me is the part that says "run M on input w and accept if M accepts w". this is the whole question for Atm. If we could answer that question why we need a machine M2 to feed it into the R and output the result of R. We just "run M on w".

Also for some languages that \[we know\] are decidable we can have the same argument and conclude that it is not decidable.

----- EDIT -----

Ok. let me explain my confusion a little bit different. consider language A\_DFA :

```
A_DFA = { <B, w> | B is a DFA that accepts w }

```

We know it is decidable (Proof in the textbook). so we reduce ATM to A\_DFA.

PROOF. let R be Turing machine that decides A\_DFA. we construct TM S to decide ATM. then S works in the following manner :

S = "On input `<M, w>` where M is a TM and w is a string:

1. Construct the following DFA D:

DFA D has only one state q0 which is also the start state. all arrows come back to q0 itself. if M accepts w add q0 to F. (F is the set of final states.)
2. Run R on `<D, w>`
3. accept if R accepts; reject if R rejects.

---

It is interesting that I kind of understood the problem of my own work when I was writing the proof of reduction of ATM to A\_DFA. I write it so that if it is true others can learn if it is wrong others will correct it!

I think that because M2 in the first proof is a Turing machine we CAN say that if "M accepts w". (we somehow embedded the work of "if M accepts w" into M2 without actually running M on w). but in my own proof of ATM -\> A\_DFA the problem is that we cannot construct DFA D without actually running M on w. so we cannot construct D. That's the reason why the first proof is true and my proof is wrong.

# Answer
> 0 votes
A universal Turing machine accepts a machine $M$ and an input $x$, and simulates the run of $M$ on $x$.

* If $M$ halts on $x$, the universal Turing machine will also halt, and will output the state of $M$ at the end of computation.
* If $M$ doesn't halt on $x$, the universal Turing machine will also not halt.

This is what the machine $M\_2$ does on step 2. It simulates $M$ on $w$, and may or may not halt. What a universal Turing machine cannot accomplish is solve the halting problem, that is, given $M$ and $x$, do some computation *which always terminates*, and answer whether $M$ halts on $x$ or not. Instead, it simulates $M$ on $x$, and halts iff $M$ halts on $x$.

We shouldn't be able to tell whether an arbitrary machine $M$ halts on an arbitrary $w$ or not. The reduction translates this question into the question whether $L(M\_2)$ is regular. Since the former question is undecidable, so is the latter one.

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


# Question
Title: Transforming a byte with a subset of a small, fixed set of values and xor into any other value
If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, each affecting a single bit 0x80, 0x40, ... 0x01: every possible value is represented by some combination of operations from any given starting point.

But, clearly there are *other* sets of eight values which achieve this. For example 0b1xxxxxxx, 0b01xxxxxx, 0b001xxxxx, 0b0001xxxx, 0b00001xxx, 0b000001xx, 0b0000001x, 0b00000001 clearly satisfy these criteria and are a relatively large set of such values (as the x's can be distinct). (Proof: use the first value to get the msb correct then the second to get the second-msb correct, etc).

However, some sets clearly do *not* have this property, for three bits 0b101, 0b110 and 0b011, for example, clearly do not as every operation preserves parity.

I am interested in various aspects of the above property from a practical standpoint for a numerical computational model. I am not a theoretical computer scientist, but have studied these things in the last century, so I am vaguely aware that what I need to look at may amount to groups, Galois Fields, LFSRs, etc.

Could someone point me in the right direction so that my learning can be more directed than random flailing around textbooks and wikipedia? Just some signposts as to the names of the relevant fields of study, the great theorems/problems/categories and their names, the useful techniques, etc, would be fine.

# Answer
You have recalled the correct category, "linear-algebra".

Let us see how we can interpret xor in the terms of linear-algebra. Here is the computation rules for xor. $$0\oplus0=0$$ $$0\oplus1=1$$ $$1\oplus0=1$$ $$1\oplus1=0$$ If we consider 0 and 1 as the zero element and the unit element of the binary field $\Bbb F\_2$, the simplest finite field, then we can see $\oplus$ is none other than the addition in $\Bbb F\_2$. $$0+0=0$$ $$0+1=1$$ $$1+0=1$$ $$1+1=0$$

That means, if we xor a string of 3 bits to another string of 3 bits, we are actually adding two vectors $\vec a$ and $\vec b$ in the three-dimensional linear space $\Bbb F\_2^3,$ $$\vec a+\vec b=\vec c$$ For example, $(0,1,0) + (1,1,0)=(1,0,0)$.

If we fix the second vector, the addition by the second vector is a linear transformation from $\Bbb F\_2^3$ to $\Bbb F\_2^3$. All these transformations form a 3-dimensional linear space over $\Bbb F\_2$ with basis $$\\{\text{addition by (1,0,0)}, \text{ addition by } (0,1,0), \text{ addition by (0,0,1)}\\}.$$ Given a set of vector in $\Bbb F\_2^3$, all combinations of the additions by those vectors can transform any vector to another vector if and only those vectors are linearly independent.

For example, "three bits 0b101, 0b110 and 0b011" "do not have this property" because, $(1,0,1)+(1,1,0)+(0,1,1)=(0,0,0)$ in $\Bbb F\_2^3$, i.e, those three vectors are not linearly independent.

---

Here is a counting exercise.

(**Exercise**) Show the number of sets of such strings of 3 bits is $(2^3-1)\*(2^3-2)\*(2^3-2^2) = 168.$ In general the number of set of such string of n bits is $(2^n-1)(2^n-2)\cdots(2^n-2^{n-1}).$
> 5 votes

# Answer
You need the eight values to be linearly independent so they form a basis of the space $\\{0,1\\}^8$.
> 3 votes

---
Tags: linear-algebra, group-theory
---


# Question
Title: When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$
Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then why do even use $ |E| = \Theta (|V|^2)$?, understand that $\Theta$ is the correct(tightest) bound in asymptomatic notation. It seems to me that $|E| = \Theta (|V|^2)$ can never happen, so why do we use it?

# Answer
> 4 votes
Note that asymptotic bounds only apply to *infinite sequences*.

In this case, $|E| = \Theta(|V|^2)$ applies to an implicit infinite sequence of graphs $G\_i=(V\_i,E\_i)$, meaning that there are two positive constants $c,c'$ such that, $c\cdot|V\_i|^2 \leq |E\_i| \leq c'\cdot|V\_i|^2$ whenever $i$ is large enough.

This constraint can be satisfied. For every $i\in \mathbb N$, take $G\_i$ to be the complete graph on $\\{1,\ldots, i\\}$. Hence, $G\_i$ has exactly $i\cdot(i-1)/2$ edges. For large enough $i$, we have $$ \frac{1}{4}i^2 \leq \frac{i\cdot(i-1)}{2} \leq \frac{1}{2}i^2 $$ So, we can say that $|E| = \Theta(|V|^2)$.

Another sequence could be constructed taking "almost complete" graphs, where we remove one edge from each complete graph $G\_i$ in the previous sequence. This would still satisfy the bound.

We could even remove, say, $100\*i$ edges from each $G\_i$ (when possible) and still satisfy the bound. This is because we only care about $|E\_i|$ growing with "quadratic speed".

# Answer
> 3 votes
You're absolutely right that $\Theta$ is the tightest asymptotic bound. But it's still asymptotic, and that means that we don't care about constant factors or terms of lower degree: when $n$ (or $v$ or whatever) gets big enough, the smaller terms become negligible.

In this case, $\frac{v(v-1)}{2} = \frac{1}{2} v^2 + \frac{-1}{2} v$. So removing the constant factors and lower terms leaves us with $v^2$.

---
Tags: graphs, asymptotics
---


# Question
Title: Does the Paxos algorithm use failure detectors?
Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?

# Answer
In short, the "plain" Paxos algorithm does not use failure detectors, but it can be augmented with failure detectors. Furthermore, the "plain" Paxos algorithm does not fully solve the problem of consensus.

To answer this question more in detail, we first define "the consensus problem". An algorithm "solves" the problem of consensus if it guarantees that the following properties are satisfied:

* Termination (or liveness, or progress): all non-faulty processes eventually decide on a value
* Agreement (or consistency, or safety): all processes that decide do so on the same value
* Validity (or non-triviality): the value that has been decided must have proposed by some process

The "plain" Paxos guarantees that agreement and validity are always satisfied, that is, if you use Paxos to solve consensus, then you will never get as a result processes that decide on different values or that decide on values that have never been proposed.

However, "plain" Paxos does not guarantee termination, that is, if you use "plain" Paxos, then it is possible that processes will never decide on a value. This problem can be (partially) circumvented by using using "leader election", that is, you elect a leader (which must be a proposer in the "plain" Paxos algorithm) which coordinates the proposals. However, the leader can also fail. This failure of the leader can e.g. be detected using failure detectors (which, in practice, may be implemented as "timeouts"). Therefore, Paxos can use failure detectors. But I won't dwell more on this topic.

In conclusion, "plain" Paxos does **not** fully solve the problem of consensus, because it does not guarantee "progress".
> 1 votes

---
Tags: algorithms, distributed-systems
---


title: What is a genuine atomic multicast?

text:
# Question
Title: What is a genuine atomic multicast?
What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?

# Answer
> 1 votes
Atomic multicast is a generalisation of atomic broadcast. In atomic multicast, there are $M \geq 1$ groups of processes $\Gamma = \\{ G\_1, G\_2, \dots, G\_M \\}$, where $G\_i$ is a non-empty group. The groups are usually defined to be non-overlapping or disjoint, that is, groups do not have processes in common. A message $m$ can be sent to one or more groups. The destination groups of a message $m$ are usually defined to be the groups inside the set $m.dst$, that is, m will be delivered by all processes inside the groups which are inside the set $m.dst$. Atomic broadcast is a special case of atomic multicast, where there is only one group which contains all processes.

To be more precise, let us more formally define the atomic multicast (AM) problem. An AM is a reliable multicast, which also requires a "total order" property to be satisfied. Let us first defined a reliable multicast.

A reliable multicast (RM) is defined in terms of two primitive operations, often denoted by R-multicast(m, m.dst) and R-deliver, where $m.dst$ is the set of groups to which $m$ is multicast. R-multicast is used to reliably multicast, that is, to send message $m$ to the groups in $m.dst$, and R-deliver is used to reliably deliver the message $m$ once it has been received by those same groups.

These primitive operations, R-multicast and R-deliver, and, in general, any algorithm which implements RM must satisfy 3 properties:

1. **Validity**: If a correct process multicasts $m$, then all correct processes that belong to a group of $m.dst$ deliver $m$
2. **Uniform Agreement**: If a process delivers a message m, then all correct processes that belong to a group of $m.dst$ deliver $m$
3. **Uniform Integrity**: A process $p$ delivers a message $m$ at most once and only if the group of $p$ is in $m.dst$ and some process has previously multicast $m$.

In addition to these 3 properties, the atomic multicast problem also requires the following property to be satisfied

4. **Local total order**: If processes $p$ and $q$ both deliver messages $m$ and $m'$ and $m.dst = {m'}.dst$, then $p$ delivers $m$ before $m'$ if and only if $q$ delivers $m$ before $m'$.

In other words, if the destination groups of the messages $m$ and $m'$ are the same and there are two processes which deliver both $m$ and $m'$, then they must deliver these messages in the same order (or in "total order").

In reality, there are other "total order" properties: for example, there is the "global total order" property. An atomic multicast problem defined in terms of the "global total order" property is different than the atomic multicast problem defined in terms of the "local total order" property. See section 2.2 of the paper "Fault-tolerant Genuine Atomic Multicast" by Carole Delporte-Gallet and Hugues Fauconnier for more details.

I stated that an atomic multicast is a generalization of an atomic broadcast. However, an atomic broadcast can actually be used to implement an atomic multicast. More specifically, to do that, we can atomically broadcast the messages and then only the groups inside $m.dst$ would atomically deliver $m$. However, this would send $m$ to all groups in the system, even though they may not be in $m.dst$. In other words, if we implemented an atomic multicast using the modified version of the atomic broadcast algorithm just explained, all groups and processes in the system would be involved. This implementation would be as costly as the implementation of an atomic broadcast algorithm. We want to avoid this!

A **genuine atomic multicast** algorithm is an algorithm which solves the atomic multicast problem where only the sender of the message $m$ and the processes in destination groups ($m.dst$) are "concerned" by (or involved in) the atomic multicast of the message $m$.

Thus the adjective "genuine" is associated with the algorithms which solve the atomic multicast problem and not with the problem itself.

---
Tags: algorithms, distributed-systems
---


title: fixing a slightly broken BST tree

text:
# Question
Title: fixing a slightly broken BST tree
I'm stuck on this question, a BST is slightly broken only if there is a node with value x in which :

there is at least one value less than x on its right branch or atleast one value greater than x on its left branch.

for example :

```
                3
               / \
             10   5
             /\   /\
            8 15 4  7

```

suggest an algorithm which will fix the tree also it should keep its original shape and same values, at worst case $O(n)$, where $n$ is the number of values.

I know it is possible to fix it and keep same shape but I can't seem to find the an algorithm that is at worst case $O(n)$.

# Answer
The problem must have said that there is **at most one node** such that, if its value is $x$, "there is at least one value less than $x$ on its right branch or at least one value greater than $x$ on its left branch". Otherwise, any binary tree could be "a slightly broken BST tree". It is not possible to construct a BST in $O(n)$ from random $n$ values in general.

Here is the explanation for an $O(n)$ algorithm.

First, as you should have observed, we can concentrate on the subtree with the broken node as the root. Let us assume that the root of the tree is the broken node.

Perform in-order traversal on the left subtree to list all values in the left subtree. Perform in-order traversal on the right subtree to list all values in the right subtree. Merge these two ordered list. Insert the value of broken node. Now we get all values in an ordered list.

Now traverse the whole tree in-order. In other usual situations we will print its value when we visit a node. Instead, we will replace the values of nodes using the successive values in that ordered list when we visit the nodes.

It is clear that each step above takes $O(n)$ time.
> 0 votes

---
Tags: binary-search-trees
---


# Question
Title: What's the difference between cache miss penalty and latency to memory?
Can I say that cache miss penalty includes latency to memory? My current understanding is that cache miss penalty is the time moving data from the layer closer to main memory to it. But I'm not sure about what's the meaning of latency to memory? If they're not the same what's the overlapping part?

# Answer
> 1 votes
"Cache miss penalty" would be the extra time that is spent because of the cache miss.

Let's say your L1 cache has 5 cycles access time, and L2 cache has 23 cycles access time. That doesn't tell us enough yet.

A clever implementation might immediately detect that there is a cache miss, and send the data from the L2 cache simultaneously to the L1 cache and to whoever wanted the data. So without cache miss it might take 5 cycles, with cache miss 23 cycles. So you have 23 cycles latency for the L2 cache, but only 18 cycles miss penalty.

A less clever implementation might try the L1 cache first, then 5 cycles later start accessing L2 cache, put the data into L1 cache 23 cycles later, start the L1 cache access all over, and deliver the data another 5 cycles later. Total time 33 cycles, minus the 5 cycles without cache miss, so a 28 cycle miss penalty.

---
Tags: cpu-cache
---


# Question
Title: What is the Big-Ω of the following function?
For the following function:

$$ \sum\_{n=1}^{2n}x+x^2 $$

It is easy to see the (tightest) Big-Oh is $O(n^3)$, but I am not so sure about the Big-Omega. Here is my attempt:

$$ \sum\_{n=1}^{2n}x+x^2 $$ $$ \geq \sum\_{n=1}^{2n}x^2 $$

But not sure how to continue. Also, does tightest Big-Ω always equal tightest Big-Oh?

EDIT: The way I worked out the Big-Oh is shown below:

$$ \sum\_{n=1}^{2n}x+x^2 $$ $$ \leq \sum\_{n=1}^{2n}x^2+x^2 $$ $$ = \sum\_{n=1}^{2n}2x^2 $$ $$ \leq 2n ( 2(2n)^2) $$ $$ = 8n^3 $$

Therefore the Big-Oh is $O(n^3)$.

# Answer
$$\begin{align} \sum\_{x=1}^{2n}(x+x^2) \gt \sum\_{x=1}^{2n}x^2 \gt \sum\_{x=n+1}^{2n}x^2\gt\sum\_{x=n+1}^{2n}n^2= n^3 \end{align} $$

So the function is $\Omega(n^3)$. You have shown it is $O(n^3)$. So the function is $\Theta(n^3)$.

Although $n^3$, the asymptotic lower bound ignoring a constant factor is the same as the asymptotic upper bound ignoring a constant factor in the current case, it is not always true because some functions fluctuate. For example, $$f(n)=\begin{cases}1 \quad \text {when }n\text{ is odd,}\\ n \quad \text{when }n\text{ is even.}\end{cases}$$ $f(n)=O(n)$ and $f(n)=\Omega(1)$. Both bounds are tightest.

---

**Exercise.** Show that $$\sum\_{x=1}^{m}(x+x^2)=\frac{m(m+1)(m+2)}{3}$$
> 3 votes

---
Tags: asymptotics
---


# Question
Title: Normal form after decomposition of a relation
I came across a text recently which claims that if we perform a lossless decomposition of a relation R into smaller relations R1 and R2, and if R is in 3NF, both R1 and R2 are 3NF.

I felt a bit suspicious regarding this claim, but couldn't find anything to prove this statement wrong.

Am I correct in thinking that this statement doesn't hold all the time, or Am I wrong? It would be really helpful if someone can correct me if I am wrong?

Thanks in advance!

# Answer
I think you are wrong.

Here is a rough sketch of a proof (by contradiction) that the original claim is true.

Suppose that the claim is false: this means that R1 or R2 (or both) are not in 3NF. Without loss of generality, suppose that R1 is not in 3NF. This means that, among all the dependencies holding in R1, there is at least a dependency X → A in which X is not a superkey (and so it is neither a candidate key) *and* the attribute A is not prime.

Now consider the definition of lossless decomposition: for each possible *valid* istance r of R, we have that r = πT1(r) ⨝ πT2(r), where T1 are the attributes of R1 and T2 are the attributes of R2.

This means that each valid instance of R1 is a projection on the attributes T1 of some valid instance of R. But this implies that if X → A is valid in an instance r1 of R1, it will be also valid in an instance r of R obtained by joining r1 with some instance of R2 (because, for the definition of join, the tuples of r1 will appear in r unchanged, possibly repeated).

So this means that X → A is also valid in R, contradicting the initial hypothesis that R is in 3NF.
> 1 votes

---
Tags: database-theory, normal-forms, relational-calculus, functional-dependencies
---


# Question
Title: RAM BSS model based (or its variant) computer recognizing Boolean languages
Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or its variants?(A variant could be to allow comparison. Or a RAM/BSS with weaker assumptions).

# Answer
> 1 votes
Christine Gaßsner studied the question you are asking. These papers seem relevant, but you should have a look at her list of publications (DBLP):

1. The Separation of Relativized Versions of P and DNP for the Ring of the Reals. J. UCS 16(18): 2563-2568 (2010)
2. Oracles and Relativizations of the P =? NP Question for Several Structures. J. UCS 15(6): 1186-1205 (2009)
3. Relativizations of the P =? DNP Question for the BSS Model

You seem to be asking a basic question, namely: can BSS RAM machines recognize *any* boolean languages? Well, a BSS machine always has some kind of comparison operator, at the very least $\<$ on real numbers. We can use it to decide equality of $0$ and $1$, from which it follows that a BSS machine can recognize *at least* all the languages that an ordinary RAM machine can. The more interesting question is whether it can do *more* than that, or perhaps more efficiently.

---
Tags: complexity-theory, formal-languages, turing-machines
---


title: Is {wxw^r} a regular language?

text:
# Question
Title: Is {wxw^r} a regular language?
Is $\\{ WxW^{\mathrm{R}} \mid W,x\in\\{0,1\\}^+\\}$ a regular language? If so, why?

The notation $W^{\mathrm{R}}$ means the reverse string of $W$?

If we consider the best answer in this solution, if the language is regular, then its FA should reject all strings not in the language. However, a string such as 0110100 would also be accepted by the FA, since it compares only the starting and end characters! Please explain.

# Answer
* $W^R$ means the reverse string of $W$.
* You are right about the DFA. If a DFA $A$ accepts the language $L$ then it rejects all the words that are not in $L$. But the word $\sigma = 0110100$ is in the language!. Consider $W=0$ and $x=11010$.
* As G.Bach eloquently stated in his comment(a very interesting property of the language):

$$\\{WxW^R : W,x\in \\{0,1\\}^+\\} = \\{WxW : W\in\\{0,1\\} , x\in \\{0,1\\}^+\\}$$

**¿Why?**

Because there is little restriction to $x$. We can consider that $x$ is almost the whole word with the exception of the first and the last symbol(because in the original language $|W|\>0$). The reverse string of any word with unitary size is the same word. So words like:

$$\sigma\_1 = 01110000$$ $$\sigma\_2 = 11111101$$

Are in the language. All that matter is the first and the last symbol. This language is very interesting because it appears to be irregular at the first sight.
> 6 votes

# Answer
Sure !! this is a **Regular Language**
Language : **Start & End with same Symbol**.

**eg;** W: 000111 WR : 111000

WxWR : ***0** 0011111100 **0***

---

First & Last symbol of language is W & WR respectively & remaining is in x. You can check any input for W, the language hold the properties Start & End with same Symbol.
> 1 votes

# Answer
it's a tricky question but quite simpe one when you know the logic...

say **w = 100, x= 101 =\> wr= 001**

the complete string wxwr will be 100101001

now what we can do here is extend x in both direction so it consumes parts of w and wr leaving only the starting and ending symbol now **x = 0010100 and w,wr = 1**;

**so simply the problem is reduced to string starting and ending with same symbol, now a DFA can be constructed.**

**so yes this is a regular language.**
> 0 votes

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


title: Applying minimax tree to this array

text:
# Question
Title: Applying minimax tree to this array
Please tell me how I should apply minimax algorithm to the array $$ 15, 12, 14, 16, 11, 13$$ and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)

# Answer
Minimax is actually applied on a 2D matrix like:

```
3  5  6  13  8
7  9  2  4   6
4  12 15 16  10

```

Generally, you have a choice to do, let say it corresponds to one of the columns in the exemple (5 choices). And there is an unpredictable choice (random, opponent choice ...), the row in the example (3 choices). Minimax minimizes the risks by assuming this unpredictable choice will be the worst for you.

In the example, you first compute the minimum on all colums:

```
3 5 2 4 6

```

So you finally pick the 5th choice, which guarantees at least 6.

In your problem you have 1 dimension, then minimax has no sense on it. Or you can degenerate it saying there is no unpredictable variable and just pick the maximum.
> 0 votes

---
Tags: algorithms, arrays
---


# Question
Title: Difference between stable marriage problem and assignment problem
What is the difference between the stable marriage problem and an assignment problem? Both refer to a matching problem in general but what is their specific difference? I can see clear differences in the implementation but do not see any related to the motivation. Both aim at assigning a man to a female - both approaches take into account preferences.

# Answer
> 3 votes
The main difference is the optimization goal.

In classical assignement problem, there is a fitness/cost function to maximize/minimize. Each assignement possibility has a weight and you only sum up all these weights to get the best global result. Only the overall result matters even if it means some individual assignements have a very bad fitness/cost.

In the stable marriage problem, it is the opposite. You do not care about the overall optimality. You just want to guarantee that it does not exist a "male" and a "female" that would both be "happier" together rather than with their assigned partner.

The idea behind the word "stable" is that if such a couple exists, they will tend to get together breaking your initial assignement.

An exemple: two "males" A and B and two "females" C and D

```
A loves hardly C (weight 10) and not D (weight 1)
B loves a little more C (weight 3) than D (weight 2)
C loves a little more B (weight 3) than A (weight 2)
D loves hardly B (weight 10) and not A (weight 1)

```

In assignement problem, you clearly put A&C and B&D to get a fitness score of 24. But this is not a stable marriage as B and C would rather like to be together. A&D and B&C is a stable marriage but only has a fitness score of 8.

---
Tags: assignment-problem
---


title: calculation of Transitive Closure

text:
# Question
Title: calculation of Transitive Closure
This question is not from homework, but rather as preparation for the test:

The calculation of place-in is a calculation in which the algorithm does not need space beyond the output size (beyond beyond a fixed space complexity). Show how, given a graph (E, V = G), the transitive closure can be calculated in-place in the calculation of G * = (V, E \*)

I tried to represent the graph using a adjacency matrix. what is the next step?

# Answer
Show that you can calculate the transitive closure by an algorithm that only modifies values in this matrix and perhaps some fixed number of variables declared in the code. (A fixed amount of storage "doesn't count".)

Which intermediate results would you compute?
> 0 votes

# Answer
The transitive closure of a graph $G = (V,E)$ is $G^{+} = (V,E \cup E')$, where $E'$ is a (possibly empty) set of additional edges which represent the transitive paths. That is, the set of edges in $G^+$ is a superset of the set of edges in $G$.

Moreover, suppose you have a graph $G = (V,E)$, and find a new edge $e$ that isn't in $G$ but is in $G^+$. Then the new graph $G' = (V, E \cup \\{ e \\})$ has the useful property that $G^+ = G'^+$. That is

It's worth proving both of these results; it's not hard.

From this, it seems like you should be able to construct $G^+$ from $G$ by just adding edges. Once you have added an edge, you have effectively constructed a new graph $G'$ such that $G \subseteq G' \subseteq G^+$.

How would you find new edges to add? And when should such an algorithm terminate?
> 0 votes

---
Tags: algorithms, graphs
---