# Question
Title: How does an automaton model a computer or something else?
1. An automaton, as I have seen so far, is used to tell **if a string belongs to the language that the automaton recognizes**. This is determined by the final state of the automaton running on the string as an input. I wonder what role the output of the automaton plays here for this decision problem?
2. I saw that an automaton (e.g. a Turing machine) can model **a computer**. A computer takes a program (which can solve any problem, such as evaluating a function, optimizing a function, searching for something, ...)as an input, and outputs what the program asks the computer to do. So when an automaton models a computer, what do the inputs, outputs, states and transition/output rules of the automaton represent?
3. Some also said that an automaton models **an algorithm**. My understanding is that an algorithm is informally a sequence of instructions ( I can't find the formal definition for an algorithm, and wonder what it is), while an automaton has a set of rules for transition and output. So I wonder how to understand that an automaton models an algorithm?

1 seems to be just a special case of 2, since the decision problem is just a kind of problem that a computer can solve.

Regarding 2 and 3, if an automaton models a computer and a program is its input, since a program represents an algorithm, isn't an algorithm an input to an automaton instead? Thanks.

# Answer
> 6 votes
The impetus behind all of this comes from trying to define a mathematically rigorous model of what "computation" means. Alan Turing did this in 1936 by defining a definition of a simple abstract machine that seemed to be sufficient to describe everything that we'd call computation, a device we now call a Turing Machine.

Over the years, people have investigated other models of computation that were restricted in what they could do and discovered that these simpler models were also interesting in themselves. This eventually lead to what we might call the standard introduction to computability theory, as follows.

**Finite Automata**. Starting with this model, we have a finite collection of **states** and define transitions from one state to another depending on the current character being read in an input string. Some of these states are designated as **final** states and the convention is that if the automaton is in a final state after reading all the characters of the input, we say that the automaton **accepts** the input string.

**(Important Digression): Languages and problems**. Starting with a machine that can determine whether a string is or is not in a particular language, we can transform this task into a task of solving a problem. For instance, we might want to solve the problem "given nonnegative integers $n$ and $m$ are they both even or both odd?" It's not hard to see that this is equivalent to "can we make a finite automaton that accepts all and only strings in the language $L\_1=\\{a^nb^m \mid a\equiv b\pmod 2\\}$, where $a^nb^m$ is the string of $n$ copies of $a$ followed by $m$ copies of $b$. It turns out that a finite automaton can be built to do this. The point here is that any computational problem can be turned into a language recognition problem, where the language is effectively an encoding of the possible solutions. In other words, the language $$ \\{(0, 0), (0, 2), (0, 4),\dots, (2, 0), (2, 4), \dots, (1, 1), (1, 3), \dots,\\} $$ can, suitably coded, be recognized by a FA

**Other Automata**. It happens that finite automata can't recognize solutions to all problems. For example, a FA (finite automaton) can't recognize the language $L\_2=\\{a^nb^n\mid n\ge 0\\}$, in other words, it isn't powerful enough to determine whether two nonnegative integers $n, m$ are equal. If we modify our FA model by including a stack where we can push or pop symbols depending on the input string (as well as change to another state), then this new model (a **pushdown automaton** or PDA, as it's known) can recognize the language $L\_2$ and also the language $L\_3=\\{a^nb^mc^{n+m}\\}$, so a PDA can determine whether two numbers sum to another. It happens, though, that PDAs aren't powerful enough to do the same for products. We can continue this process, adding enhancements to each abstract model of computation, and get a hierarchy of increasingly more powerful machines. The exciting part is that this hierarchy quickly comes to an end.

**Turing Machines**. If we take a FA and add to it an arbitrary long list (called a **tape**) initially containing the input and allow moves where the current state and the current contents of an element in the list determine the next state, what we write in the current list element, and whether we move one position forward or backward in the list, we have Turing's 1936 abstract machine, a **Turing Machine**, or TM. This simple device is extremely powerful: it can add, subtract, multiply, divide, move data to a different location on the tape, compare two chunks of data and base its actions on the results of the comparison, and do things like compute prime numbers and give the $n$-th digit of $\pi$. In fact, it can do everything that modern computers can do and more, since, being an abstract machine, it has an arbitrarily large amount of "memory" on its tape, potentially vastly larger than the number of elementary particles in the universe.

**Things to do With TMs**. With this model, we can perform all the tasks we're used to:

* *Implement Functions*. We can build a TM that, say, computes square roots: given two numbers on its tape, like "3.1416#7", we can define the moves of a TM to produce the square root of the input, 3.1416, to seven digits of precision, so at the end of its calculations, the tape would contain "1.7724559". This is just an **algorithm**: a finite sequence of steps in some model that produces a result according to our specifications.
* *Language recognizers (and problem solvers)*. We could design a TM that recognizes the language of primes: $L\_4=\\{2,3,5,7,11,13,17,19, \dots\\}$: given an input tape initially containing an integer $P$, this machine could determine if $P\in L\_4$, namely if $P$ is the decimal representation of a prime number.
* *Programmable Computers*. It's even possible to design a **universal TM** which takes a suitably coded description of a TM, $\langle M\rangle$ (perhaps by a listing of its move rules), and an input $X$ and simulate the action of $M$ on input $x$, which of course exactly what a real-world computer plus compiler does.

---

**Remarks and Consequences**

Fully fleshed out, this narrative has a flow, from simple machines to, ultimately, a machine that's more powerful than any modern physical computer. The narrative doesn't stop there, though. The **Church-Turing Thesis** says that *anything* that we would agree falls under our definition of "computation" can be accomplished by a TM. In other words, the Church-Turing Thesis is a confident bet that not only are TMs more powerful than any modern computer, but that they can accomplish *anything* we'd call computation on any future computer.

It gets even better, though. Since the (uncountable) infinity of possible functions from the integers to themselves is vastly larger than the (countable) infinity of possible Turing Machines, it means that *there are lots of tasks that TMs (and hence computers) cannot do*. That might not be a real-world problem, since the functions that TMs can't compute are in a very real sense undescribable, but there are also plenty of seemingly programmable tasks that TMs (and hence computers) cannot do. For example, "given a listing of a program and an input for that program, can we always determine whether that program will eventually halt when given that input?" Professional programmers would love such a tool, but it is provably impossible to construct a program to determine, for all program listings and inputs, whether that program will perhaps enter an infinite loop or not. Similarly, there is no hope of determining, in all cases, whether a given program will behave according to some set of specifications. So our fascinating narrative has a sad ending: **there are (infinitely many) tasks computers will never be able to do**.

# Answer
> 4 votes
What you seem to be talking about is a deterministic finite automata (DFA). A DFA has no output. It either accepts or doesn't accept its input. In other words, they only give yes/no answers.

A Turing Machine (TM) is a generalization of a DFA that is equipped with infinite memory (as opposed to the mere constant memory of the DFA). A TM is more powerful than a DFA. TMs *are* algorithms: they take an input, and produce an output (or loop infinitely, as it may be). While usually in complexity theory we also think of TMs as only providing yes/no answers, they can easily be modified to also give an output string.

A Turing Machine is *not* a computer. They are equivalent in power to the computers we use everyday, but are *much* simpler. They are a model of computation, that is used by theorists when discussing the theory of computation. The states and transition function have no simple direct analogue in a real-life computer.

A Turing Machine can *model* a computer, and not just one algorithm, because there is a Universal TM (actually, there are many) that takes another TM as its input and simulates it. That is, a Universal TM is *programmable* in the everyday sense of the word.

You should really read an introductory book on the Theory of Computation (the one by Sipser is excellent) if you want to understand these concepts fully. You seem to have some definitions muddled.

---
Tags: automata, computation-models
---


title: Can every DCFG be converted to DGNF?

text:
# Question
Title: Can every DCFG be converted to DGNF?
I know you can convert every context-free grammar into Greibach normal form grammar.

But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?

# Answer
> 4 votes
If by deterministic GNF you mean as a deterministic grammar that is also GNF then yes, here is the paper. Normal forms of deterministic grammars

> It is shown that every strict deterministic language may be given a strict deterministic grammar which is also in Greibach normal form.

EDIT Here is a paper outlining the technique to do the conversion Strict deterministic grammars and Greibach normal form

---
Tags: context-free, formal-grammars, normal-forms
---


# Question
Title: Why do low fitness individuals have a chance to survive to the next generation?
I am currently reading and watching about genetic algorithm and I find it very interesting (I haven't had the chance to study it while I was at the university).

I understand that mutations are based on probability (randomness is the root of evolution) but I don't get why survival is.

From what I understand, an individual $I$ having a fitness $F(i)$ such as for another individual $J$ having a fitness $F(j)$ we have $F(i) \> F(j)$, then $I$ has a better probability than $J$ to survive to the next generation.

Probability implies that $J$ *may* survive and $I$ *may* not (with "bad luck"). I don't understand why this is good at all? If $I$ would **always** survive the selection, what would go wrong in the algorithm? My guess is that the algorithm would be similar to a greedy algorithm but I am not sure.

# Answer
The main idea is that by allowing suboptimal individuals to survive, you can switch from one "peak" in the evolutionary landscape to another through a sequence of small incremental mutations. On the other hand, if you only are allowed to go uphill it requires a gigantic and massively unlikely mutation to switch peaks.

Here is a diagram showing the difference:

Practically, this globalization property is the main sellling point of evolutionary algorithms - if you just want to find a local maxima there exist more efficient specialized techniques. (eg., L-BFGS with finite difference gradient and line search)

In the real world of biological evolution, allowing suboptimal individuals to survive creates robustness when the evolutionary landscape changes. If everyone is concentrated at a peak, then if that peak becomes a valley the whole population dies (eg., dinosaurs were the most fit species until there was an asteroid strike and the evolutionary landscape changed). On the other hand, if there is some diversity in the population then when the landscape changes some will survive.
> 35 votes

# Answer
Nick Alger's answer is very good, but I'm going to make it a little more mathematical with one example method, the Metropolis-Hastings method.

The scenario that I'm going to explore is that you have a population of one. You propose a mutation from state $i$ to state $j$ with probability $Q(i,j)$, and we also impose the condition that $Q(i,j) = Q(j,i)$. We will also assume that $F(i)\>0$ for all $i$; if you have zero fitness in your model, you can fix this by adding a small epsilon everywhere.

We will accept a transition from $i$ to $j$ with probability:

$$\min\left(1, \frac{F(j)}{F(i)}\right)$$

In other words, if $j$ is more fit, we always take it, but if $j$ is less fit, we take it with probability $\frac{F(j)}{F(i)}$, otherwise we try again until we accept a mutation.

Now we'd like to explore $P(i,j)$, the actual probability that we transition from $i$ to $j$.

Clearly it's:

$$P(i,j) = Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$$

Let's suppose that $F(j) \ge F(i)$. Then $\min\left(1, \frac{F(j)}{F(i)}\right)$ = 1, and so:

$$F(i) P(i,j)$$ $$= F(i) Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$$ $$= F(i) Q(i,j)$$ $$= Q(j,i) min\left(1, \frac{F(i)}{F(j)}\right) F(j)$$ $$= F(j) P(j,i)$$

Running the argument backwards, and also examining the trivial case where $i=j$, you can see that for all $i$ and $j$:

$$F(i) P(i,j) = F(j) P(j,i)$$

This is remarkable for a few reasons.

The transition probability is independent of $Q$. Of course, it may take us a while to end up in the attractor, and it may take us a while to accept a mutation. Once we do, the transition probability is entirely dependent on $F$, and not on $Q$.

Summing over all $i$ gives:

$$\sum\_i F(i) P(i,j) = \sum\_i F(j) P(j,i)$$

Clearly $P(j,i)$ must sum to $1$ if you sum over all $i$ (that is, the transition probabilities out of one state must sum to $1$), so you get:

$$F(j) = \sum\_i F(i) P(i,j)$$

That is, $F$ is the (unnormalised) probability density function for which states the method chooses. You are not only guaranteed to explore the whole landscape, you do so in proportion to how "fit" each state is.

Of course, this is only one example out of many; as I noted below, it happens to be a method which is very easy to explain. You typically use a GA not to explore a pdf, but to find an extremum, and you can relax some of the conditions in that case and still guarantee eventual convergence with high probability.
> 13 votes

# Answer
The advantage of using a GA is that you are able to explore broader search spaces by following paths which come from potentially worse candidates. There should be worse candidates making it through in order to explore these different areas of the search, not many but definitely a few. If you start taking only the very best every time you remove this exploration aspect of the algorithm and it becomes more of a hill climber. Also only selecting the best constantly may lead to premature convergence.
> 7 votes

# Answer
Actually, selection algorithms take both approaches. One way is what you suggested and the other is that individuals with higher fitness are selected and those with lower ones are not.

The approach you pick for selection is also tailored to the problem you are trying to model. In an experiment back in school, we were trying to evolve card players by having them play games against each other (i.e. tournament selection). In such a scenario, we could very well just always favor $I$ over $J$ (from your example) because the 'luck' aspect is already in the game itself. Even if $F(i) \> F(j)$ for any two $I$ and $J$, in any given round, purely by the way hands were dealt and how others played, $J$ could have won the round and thus we could end up with $F(j) \> F(i)$. Keep in mind that a population is often large enough that one can afford to lose some good individuals and on the whole, it will not matter as much.

Since GAs are modeled around real-world evolution, when probabilistic distributions are used, they are primarily modeled around how real communities evolve in which sometimes individuals with lower fitness may survive whereas individuals with higher fitness may not (a crude analogy: car accidents, natural disasters etc. :-)).
> 6 votes

# Answer
its very simple, from one pov: sometimes higher-fitness "child" solutions can be born of lower-fitness "parent" solutions via either crossover or mutation (that actually is a lot of the theory of genetic algorithms). so in general one wants to seek/carry the higher-fitness solutions but too much emphasis on keeping/breeding only high-fitness solutions can lead to getting stuck in local minima and not searching the large "evolutionary landscape". actually one can make the "higher fitness cutoff" for survival as strict or lax as one wishes & experiment with how it affects quality of the final solution. both too-strict or too-lax cutoff strategies will lead to inferior final solutions. of course all this has some relationship to real biological evolution. there its more "environmental pressure/resource scarcity" that affects survival, and there it can be cyclical.
> 0 votes

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: Finding the kth element of a permutation
Is there a way to generate a random permutation of the numbers 1 to *N* such that I can find the *k*-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) compute the elements 1..*k-1*?

# Answer
> 1 votes
## Problem statement

Your question is unclear, but here is how I interpret it:

> Input: a positive integer $n$, and $k$ distinct values $x\_1,\dots,x\_k \in \\{1,2,\dots,n\\}$ Output: the values $\pi(x\_1),\pi(x\_2),\dots,\pi(x\_k)$, where $\pi$ is a random permutation on $\\{1,2,\dots,n\\}$

You are looking for an efficient algorithm to solve this problem.

## An efficient solution

If that is indeed what you are looking for, there is a very efficient way to solve this problem. Basically, all you need to do is randomly choose $k$ distinct integers from the set $\\{1,2,\dots,n\\}$. This is sampling *without* replacement. Here is a simple algorithm:

* Initialize $S$ to be the empty set.
* For $i=1,2,\dots,k$:

+ Pick $r$ uniformly at random from $\\{1,2,\dots,n\\}$. If $r\in S$, pick a new $r$ (and keep repeating until $r \notin S$).
    + Set $x\_i$ to $r$, and add $r$ to $S$.

You can use any number of data structures for storing the set $S$; it could be a bitvector of length $n$, or a hashtable. (A bitvector is probably better if $k$ is not too much smaller than $n$, say $k \ge n/64$ or so; a hashtable is probably more efficient if $k$ is small compared to $n$.)

## Performance analysis

If $k \le n/2$, the expected running time is linear in $n$, so this is very efficient.

If $k \ge n/2$, there are better algorithms. For instance, once you reach $i \ge n/2$, then rather than choosely uniformly, you can choose uniformly at random from $\overline{S}$ (the complement of $S$). If you use the right data structures, you can make the expected running time be linear in $n$. (Basically, once $i\ge n/2$, you compute $\overline{S}$ and throw away $S$. In each step, you choose a random element of $\overline{S}$, then remove it from $\overline{S}$. Choosing a random element of a set can be done in $O(1)$ expected time.)

# Answer
> -1 votes
If you rank all the n! Permutaions in some order, such as the lexicographic order, then you can unrank a number to a permutation. The procedure is simple. So given a random number in \[1..n!\], you can compute a random permutation.

---
Tags: permutations, randomness
---


title: CFL, pumping lemma

text:
# Question
Title: CFL, pumping lemma
I have difficulty with proving that the language $ L = \\{ a^p b^q | p \ge 1 , q \ge 1 , p \ge q^2 \vee q \ge p^2\\}$

$ w = uvxyz $

I've chosen word $ w = a^{N^2} b^N $ where $ N $ is a constant from pumping lemma and I proved cases where a $ v,y $ is entirely in $ a $ and $ v,y $ is entirely in $ b $ , but how to prove case where $ v \in a $ and $ y \in b $ ? I think that the word $ w = a^{N^2} b^N $ isn't good, but I have no idea which one will be better.

Edit after comments

After comments, my solution is :

$ w = a^{n^2} b^N $ and $ w = uvxyz $ , so $ v = a^p $ and $ y = b^q $ where $ 1 \leq p + q \leq N $ After pumping i-times I get $ w\_i = a^{n^2 + ip} b^{N+iq} $

so to prove that this word isn't in language I should choose i such as regardless of N,p,q it won't be true $ N^2 + ip \ge (N+iq)^2 $

$ N^2 + ip \ge N^2 + 2Niq + i^2q^2 $

$ ip \ge 2Niq + i^2q^2 $

for i = 1

$ p \ge 2Nq + q^2 $ which isn't true because $ 1 \leq p + q \leq N $

Is this correct ?

# Answer
This answer is taken from the question (the user was unable to post as an answer at the time).

After comments, my solution is :

$ w = a^{n^2} b^N $ and $ w = uvxyz $ , so $ v = a^p $ and $ y = b^q $ where $ 1 \leq p + q \leq N $ After pumping i-times I get $ w\_i = a^{n^2 + ip} b^{N+iq} $

so to prove that this word isn't in language I should choose i such as regardless of N,p,q it won't be true $ N^2 + ip \ge (N+iq)^2 $

$ N^2 + ip \ge N^2 + 2Niq + i^2q^2 $

$ ip \ge 2Niq + i^2q^2 $

for i = 1

$ p \ge 2Nq + q^2 $ which isn't true because $ 1 \leq p + q \leq N $

Is this correct ?
> 0 votes

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


title: Explanation of the complexity of a loop

text:
# Question
Title: Explanation of the complexity of a loop
I am confused on the following:
In the following trivial code:

```
for (int i = 0; i < n; i++) {
  for(int j = i + 1; j < n; j++) {
     for(int k = j + 1; k < n; k++) {
          //some code here
     }
   }
}

```

I know that the complexity is `N^3`. But I am confused on some details.
The outer loop is executed N times.
The inner loop I thought that it was executed N\*(N-1) times but when I tested with a small example of `n=5` it is executed actually `N*(N-1)/2` times. And the inner most loop I am lost on how the exact number of times it is executed. I originally thought that it is executed `N(N-1)(N-2)` but this is wrong again by using a small n the numbers don't work out.
So my question is:
1) Can someone help me understand how the exact complexity is calculated on this trivial example?
2) What is the usual process? Do we select some small numbers and try to derive a formula or what?

# Answer
You are right that the outer-loop is executed $N$ times, and you are almost right regarding the inner loop. Observe that the inner-loop does not loop the same amount of times at every iteration of the outer-loop. In particular, it will first loop $N-1$ times when $i = 0$, then it will loop $N-2$ times when $i = 1$, $N-3$ times when $i = 2$, and so forth. Therefore, the inner-loop is executed $(N-1) + (N-2) + \ldots + 1 + 0$ times which is the following well known summation: $$\sum\_{i=0}^{N-1}i = \frac{(N-1)\cdot N}{2}$$

A similar argument can be made to show what the runtime of the inner-most-loop is. In particular, you will get a similar type of summation.

In general, you will model the loops as summations, and simply evaluate the sum. In your example, you will have that: $$T(N) = \sum\_{i = 0}^{N-1}{\sum\_{j = i+1}^{N-1}\sum\_{k=j+1}^{N-1}}O(1)$$ and evaluating this will give you your $O(N^3)$ answer. Remember that the goal is to "count" the number of primitive operations by the algorithm in question.
> 2 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, loops
---


# Question
Title: Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?
This question is related to my previous question:

Looking for a set implementation with small memory footprint

I'm looking for information about **combined** data structures, which can efficiently represent a set S of non-intersecting sub-intervals of the given integer interval `[0, MAX)` with the single operation:

* **testAndInsert(min, max)** \- test if the interval `[min, max]` intersects with any of already existing intervals in the `S`; if no intersections are found, then insert the interval `[min, max]` into the set `S`, potentially merging it with one or two neighbor intervals; return success, if and only if the insertion was done.

I'm asking about **combined** data structures, because it looks like we have two evident choices - linked data structures (for example, various binary trees) and array-based data structures (bitmaps). However, both of them have their own shortages:

* Balanced binary trees will have O(log(n)) time complexity and look good, when number of intervals in the `S` is much less than the `MAX`. However each node of the tree will take at least 16 bytes (for links) on 64-bit machine. For example, if we represent all odd integers in the interval \[0, 1000), then we'll need 8000 bytes only for links.
* Bitmaps will have O(1) time complexity, but take constant memory, which depends only on the `MAX`. Representation of all the odd integers in the interval \[0, 1000) needs only 125 bytes. However, when the `MAX` is large and the number of existing intervals is much less than the `MAX`, then most of the memory, taken by the bitmap, will be wasted.

I'm not actually focused on the time complexity - something between O(1) and O(log(n)) is acceptable, but in real situations the memory footprint of the data structure plays a very important role. If machine begins swapping because of lack of memory, then even O(1) data structure will work for ages.

Are there any data structures, which could automatically adapt themselves to the size of the `S` in this problem? For example, when we start with the empty `S` (no intervals at all), the data structure is linked, then it becomes array-based (piece by piece?), then it probably switches to storage of the `S` complement (free space is small) and becomes linked again?

P.S.: I know about the Boost ICL interval set and use it now, but I'm interested in other possible approaches.

# Answer
Here is one space-efficient memory-hierarchy-aware in-memory data structure that might be a reasonable choice. The data structure is a binary search tree with 16-byte nodes.

Each node is either an internal node or a leaf node:

* An internal node points to two children. It has a value $v$, a left child $\ell$, and a right child $r$. All integers $\le v$ are in the left child; integers $\>v$ are in the right child.
* A leaf node holds a run-length encoding of a bitmap. Notice that an interval has a very short run-length encoding, so this is slightly more general than storing an interval in each leaf (it is a hybrid somewhere between a binary tree of intervals and a binary tree of bitmaps).

Each node of the tree is responsible for some interval of integer values $\[s..t\]$. The root is responsible for $\[0..\text{MAX}-1\]$. For an internal node containing the value $v$, its left child is responsible for $\[s..v\]$ and its right child is responsible for $\[v+1..t\]$. A leaf that is responsible for $\[s..t\]$ has a run-length encoding of the bitmap for the integers in the interval $\[s..t\]$.

How do we pack each node into 16 bytes?

* I'll assume the tree contains at most $2^{32}$ nodes in the tree. Therefore, each node can be referred to by a 32-bit label. We'll have an array $A$ of nodes, and the node with label $i$ will be stored at $A\[i\]$. With this optimization, each child pointer can be stored in 32 bits (rather than 8 bytes for a 64-bit pointer). Note that the restriction to $2^{32}$ nodes is not very restrictive; unless your machine has more than 64 GB of RAM, you couldn't fit anything larger in memory anyway.
* I'll assume that $\text{MAX} \le 2^{64}$.
* The first bit of the node will indicate whether it is an internal node or a leaf node, leaving 127 bits for the rest.
* Internal nodes: We need 64 bits for the two child pointers. That leaves us 63 bits for the value $v$. We'll store the value $v$ as an offset within the interval for that node. In other words, if the internal node is responsible for the interval $\[s..t\]$, then we'll store $v$ as the value $v-s$. (We know $v \in \[s..t\]$, so it follows that $v-s$ is a non-negative integer.) A 63-bit unsigned int is plenty for this offset. (If we wanted to use an offset that is larger than will fit in a 63-bit unsigned int, then we just split the range artificially. Since $\text{MAX} \le 2^{64}$, this will impose at most one or two extra splits at/near the root.)
* Leaf nodes: We have 127 bits for the run-length encoding of the bitmap corresponding to the interval $\[s..t\]$. We can use any convenient run-length encoding. If the run-length encoding of the bitmap does not fit within 127 bits, we split the interval: we turn it into an internal node with two children.

If you know something about the typical distribution of lengths of runs (i.e., the lengths of intervals, the lengths of the gaps between intervals), you can choose a run-length encoding that is optimized for that distribution. Otherwise, you can use any convenient generic run-length encoding scheme (e.g., recursive Rice-Golomb encoding); see also this Wikipedia page on compressed bitmaps.

Notice that we don't store $s$ or $t$ in each node, but that's OK. The interval $\[s..t\]$ for a particular node is determined by the path that we took to reach that node. As we traverse down from the root, we can keep track of the interval $\[s..t\]$ and update it each time we follow a child pointer.

If you wanted, you could combine with this with some sort of self-balancing binary tree scheme )or a self-optimizing binary tree, such as a splay tree), but it might not be necessary in practice, depending upon the access pattern in your application, and it definitely adds complexity.
> 2 votes

---
Tags: data-structures, trees, space-complexity
---


# Question
Title: Need Help Reducing Subset Sum to Show a Problem is NP-Complete
I want to show that the following problem is NP-Complete:

For a set of vectors $v\_1,\ldots,v\_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \\{v\_1,\ldots,v\_n\\}$, such that $S$ has $k$ elements and all coordinates in the vector $\sum\limits\_{x\in S} v\_x$ are powers of two?

I'm quite certain that establishing a reduction from a known NP-Complete problem: the Knapsack Problem, Subset Sum or Vector Subset Sum (see section 4.3 here) to this problem is the correct way to approach this problem, but I'm having difficulty figuring out how to exactly construct the reduction.

Concerning Subset Sum with a set $S$ and an integer $n$, I've tried taking one of the integer compositions of $n$, then splitting it up into its binary representation, and using that to dictate a desired vector. Then I would construct vectors $v\_1,\ldots,v\_n$ from the elements of $S$. But how do I create the input $k$?

One of the main issues here is that Subset Sum with a fixed subset size is not NP-complete. How do I work around that? Moreover, one of the trickier aspects of the problem is generalizing subset sum such that success is reported if some subset sums to *any* power of two. I don't see how not to appeal to multiple sub-instances of subset sum...

Is this the right approach? (If not, how should I do it?) What am I missing? How do I prove this?

# Answer
Here are some hints:

1. Focus on the case $d = 1$.
2. Given a target $T$ in SUBSET-SUM, we can change it to a target $T'$ by adding the number $T' - T$; this should work if $T'$ is sufficiently large.
3. Given a SUBSET-SUM without constraints on the size of the subset, we can get an equivalent problem with such a constraint by adding a suitable number of zeroes to the (multi)set.

If we insist on a set, we need to do more cunning in 3.
> 4 votes

# Answer
**Hint #1**: focus on $d=1$, as Yuval suggests.

**Hint #2**: suppose we're given an instance of the subset-sum problem, i.e., we're given some integers $x\_1,x\_2,\dots,x\_n$.

Now suppose we let $v\_1=42x\_1$, ..., $v\_n = 42x\_n$. Think about whether there is a subset of $\\{v\_1,\dots,v\_n\\}$ that sums to a power of two. When does that happen? What's the condition under which $\\{v\_1,\dots,v\_n\\}$ has a subset that sums to a power of two?

The answer looks unhelpful, but notice that $42$ is arbitrary. What if we replace $42$ with some other constant $c$, and then ask the same question? Can you find some other constant $c$ (instead of $42$) where the condition when $\\{v\_1,\dots,v\_n\\}$ has a subset that sums to a power of two is more convenient?

**Hint #3**: to start with, I suggest you artificially consider $0$ to be a power of two (even though I know it isn't really a power of two) and you ignore the constraint on the size of the subset. Once you can solve that variation, I suggest you go back to the original problem: a slight tweak to your construction should take care of them.

**Reminder**: Don't forget to attribute all your sources, when you write up the solution to your exercise. Your teachers read the Internet too. :-)
> 2 votes

---
Tags: complexity-theory, np-complete, reductions, proof-techniques
---


title: Can someone explain LazySelect?

text:
# Question
Title: Can someone explain LazySelect?
The LazySelect algorithm is given in these slides as follows.

We have a set $S$ of $n = 2k$ distinct numbers and want to find the $k$th smallest element.

1. Let $R$ be a set of $n^{3/4}$ elements chosen uniformly at random with replacement from $S$.
2. Sort $R$ and find $a$ and $b$ such that $\mathrm{rank}\_R(a) = kn^{-1/4} – sqrt(n)$ and $\mathrm{rank}\_R(b) = kn^{-1/4} + sqrt(n)$, where $\mathrm{rank}\_X(x) = t$ if $x$ is the $t$th smallest element in $X$.
3. Compute $\mathrm{rank}\_S(a)$ and $\mathrm{rank}\_S(b)$: Output `FAIL` if $k \< \mathrm{rank}\_S(a)$ or $k \> \mathrm{rank}\_S(b)$.
4. Let $P = \\{i \in S\mid a\le y\le b\\}$: Output `FAIL` if $|P| \ge 4n^{3/4}$.
5. Return the $(k - \mathrm{rank}\_S(a) + 1)$th smallest element from $P$.

Can someone explain the intuition behind the algorithm in a way that is more detailed and easier to understand than the slides above?

# Answer
$\DeclareMathOperator{\rank}{rank}$Given a set $S$ of $n = 2k$ elements, the algorithm is aimed at finding the median of $S$ in linear time, with high probability. The idea is to find two elements $a,b \in S$ with $\rank(a) \leq k \leq \rank(b)$ and $\Delta = \rank(b) - \rank(a)$ as small as possible. Given such elements, we can find the median in time $O(n + \Delta\log\Delta)$ as follows:

1. Determine $\rank(a)$ in time $O(n)$.
2. Compute the list $P = \\{ x \in S : a \leq x \leq b \\}$ in time $O(n)$.
3. Sort $P$ in time $O(\Delta\log\Delta)$.
4. Output the element $x \in P$ of rank $\rank\_P(x) = k - \rank(a)$ in time $O(1)$.

How do we find such elements $a,b$? The idea is to sample a smaller list $R$ which contains a $p$ fraction of the elements of $S$, for suitable $p$. An element $x \in R$ of rank $r$ in $S$ will have rank in the range $pr \pm c\sqrt{pr}$ in $R$ with probability $1-e^{-O(c^2)}$ (due to a Chernoff bound). In particular, if we the elements $a,b$ ranked $pk - c\sqrt{pk}$ and $pk + c\sqrt{pk}$ in $R$, respectively, then $\rank(a) \leq k \leq \rank(b)$ with probability $1 - e^{-O(c^2)}$. The size of the corresponding list $P$ will be roughly $$ \Delta \approx p^{-1} (\rank\_R(b) - \rank\_R(a)) = 2c\sqrt{n/p}. $$ We can find the elements $a,b$ by sorting the list $R$, which takes time $O(pn \log(pn))$. In total, the algorithm looks like this:

1. Sample a set $R$ by putting each element with probability $p$.
2. Sort $R$ in time $O(pn \log n)$.
3. Find the elements $a,b$ ranked $pk-c\sqrt{pk}$ and $pk+c\sqrt{pk}$ in $R$.
4. Proceed as before.

The total running time is $$ O(pn\log n + n + c\sqrt{n/p}\log n). $$ In order for this to be $O(n)$, we need $$ \Omega(c^2 \log^2 n/n) \leq p \leq O(1/\log n). $$ For the algorithm to succeed with high probability $1 - o(1)$, we need $c = \omega(1)$. One setting which satisfies all these constraints is $p = n^{-1/4}$ and $c = n^{1/8}$, the choice taken in the slides.
> 8 votes

---
Tags: algorithms, randomized-algorithms, randomness
---


# Question
Title: Finding the private key in BB84 quantum cryptography
I'm trying to teach myself Quantum Cryptography for an exam I have soon, and I came across the following question:

> To establish a common key, Alice and Bob analyse a sequence of 20 photon pairs. Alice measures the photon sequence: $$1\\:1\\:0\\:1\\:0 \qquad 0\\:0\\:0\\:1\\:0 \qquad 1\\:0\\:1\\:0\\:1 \qquad 0\\:1\\:1\\:0\\:1$$ using the random series of detection bases: $$\otimes \oplus \oplus \otimes\otimes \qquad \otimes \oplus \oplus \otimes \otimes \qquad \oplus \otimes \oplus \oplus \oplus \qquad \oplus \oplus \otimes \otimes \oplus$$ while Bob is analysing the photons using the following sequence: $$⊗⊕⊗⊗⊗ \qquad ⊕⊗⊕⊕⊗ \qquad ⊗⊗⊕⊗⊕ \qquad ⊕⊗⊕⊗⊕$$ Hence find the sifted data set they get as an encryption key as in BB84.

Examining all the cases when the detection bases were the same and discarding the bits when they were not; we find that the encryption key is:

$$111\\:000\\:011\\:101$$

Is this the right key?

---

Note: I apologise if this is in the wrong forum, I'm only really familiar with Math.SE, SO and EE.SE so feel free to migrate this if it's more appropriate elsewhere

# Answer
> 1 votes
The first stage of the BB84 protocol involves throwing away any measurements where the measurements were performed with a different basis. After throwing those away, we are left with the following binary sequence:

$$11 10 0 0 01 10 01.$$

However, in the BB84 protocol as it was originally published, this is not the final key. There are several subsequent steps that are performed after this.

In the second stage, Alice and Bob check whether they both got approximately the same sequence, by comparing a randomly chosen subset of this sequence. If there are too many errors (differences between Alice's string and Bob's string) in those randomly selected positions, then they declare it a failure and go back to the beginning and start over.

In the third stage, a privacy amplification protocol is applied to the remaining bits, to derive a key that Alice and Bob can use.

Consequently, in the real BB84 protocol, the final key is *not* $111000011101$. That's just the output of the first stage. The final key is the output of the third stage.

However, I don't know what they taught you in your class. I'd hope that they taught you all three stages, but if they only taught you the first stage, then you'd get a different answer than if they taught you the full protocol. Therefore, we can't really tell what the right answer to your exam might have been. If you want to know about that, I suggest you contact your instructor.

---
Tags: cryptography, quantum-computing
---


# Question
Title: Can you reduce a precedence graph or do *all* relevant nodes need to be connected
Let's say we have the following simple transaction-schedule:

```
 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

```

T1 comes before T2, so in the precedence graph, we draw an arrow from T1 to T2. T2 comes before T3, so we draw an arrow from T2 to T3.

My question is: *is it also necessary to draw an arrow from T1 to T3?* T1 comes before T3, and the definition of a precedence graph says nothing about not drawing a line from Tx to Ty if there is some arbitrary Tz inbetween.

On the other hand, T1 -\> T2 -\> T3 implies T1 -\> T3, and as the graph gets larger things will get a bit messy. Is it okay to 'reduce' a precedence graph?

If the answer to the above question is yes, here is a follow up - consider the following schedule:

```
 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

```

In the precedence graph, for the operations on x we draw an arrow from T1 to T2, for y an arrow from T1 to T3, and for z an arrow from T2 to T3. Would you be allowed to omit the arrow 'caused' by element z?

# Answer
> 4 votes
Yes it is necessary.

According to the definition of precedence graph, a directed edge $T\_i \longrightarrow T\_j$ is created if one of the operations in $T\_i$ appears in the schedule before some *conflicting* operation in $T\_j$.

It is clear from the definition that we have to consider every two transactions separately : $T\_1$and $T\_2$, $T\_1$and $T\_3$ and $T\_2$ and $T\_3$.

```
 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

```

So an edge $T\_1 \longrightarrow T\_3$ is necessary because w(x) in $T\_1$ and w(x) in $T\_3$ are two *conflicting¹* operations.

```
 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

```

For this schedule there will be three edges in the precedence graph:$T\_1 \longrightarrow T\_2$, $T\_1 \longrightarrow T\_3$ and $T\_2 \longrightarrow T\_3$.

---

1.Two operations are conflicting, if they are of different transactions, upon the same datum (data item), and at least one of them is write.

# Answer
> -1 votes
Whether it is necessary to include the edge $T\_1 \to T\_3$ depends upon how you plan to use the graph and what properties you want it to have.

In many applications, it is not necessary to include the edge $T\_1 \to T\_3$, since it is already implied by other edges. For instance, the set of schedules that are consistent with this graph (i.e., the set of topological sorts of the graph) will be the same whether you use a dag $G$, the transitive reduction of $G$, or the transitive closure of $G$.

The answer might depend upon what your definition of a "precedence graph" is. If you are using the phrase informally, then it is up to you to define what graph you want to use. On the other hand, if you are using "precedence graph" as a formally defined term, as defined "in the concurrency control literature", that definition states that you should include an edge from $u$ to $v$ if (1) $u$ must precede $v$, and (2) $u$ conflicts with $v$. Thus, if $T\_1$ conflicts with $T\_3$, then you should include the edge $T\_1 \to T\_3$ (assuming you want to use that definition); if it doesn't conflict, don't include that edge. In your example, it does conflict, so yes, you must include the edge $T\_1 \to T\_3$ if you want to use that definition of precedence graph.

---
Tags: database-theory, precedence-graph
---


title: Randomized Algorithm with matrices

text:
# Question
Title: Randomized Algorithm with matrices
We have two computers, Comp1 and Comp2, which hold binary matrices A and B of size $n\times n$.

We want to check if the matrices of the computers are identical except for exactly 1 entry.

Comp1 has to send $O(n\log^2n)$ bits to Comp2 and Comp2 should return 0 or 1 (for "no" and "yes" respectively) for the answer.

If the matrices differ by exactly 1 entry, Comp2 will answer 1 ("yes") always.

If they don't differ by exactly 1 entry, Comp2 will answer 0 in probability of at least $1/2$.

Both computers can make any manipulation of their matrix before sending a message. Comp1 of course doesn't have to send a part of its matrix. It can send an answer of computation on its matrix, and Comp2 can make also any calculation it wants before answering.

I've tried to solve it but whatever I tried it failed.

# Answer
Let's start by assuming that we have two bit vectors $A,B$ of size $m$ instead of two matrices – the matrix structure is unhelpful.

Let $w \in \\{\pm1\\}^m$ be chosen randomly, and let $\varphi = x \mapsto \langle x,w \rangle \pmod{3}$. If $A,B$ differ on the coordinates in $S$ then $$ \varphi(A) - \varphi(B) = \sum\_{i \in S} (A\_i - B\_i) w\_i \pmod{3}. $$ The distribution of this is the same as the distribution of $$ \Delta = \sum\_{i \in S} w\_i \pmod{3}. $$ Suppose $s = |S|$. In order to compute the distribution of $\Delta$, let $\omega$ be a primitive third root of unity, and consider $$ \left(\frac{\omega + \omega^{-1}}{2}\right)^s = \frac{(-1)^s}{2^s} = \left(\frac{1}{3} + \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \omega^0 + \left(\frac{2}{3} - \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \frac{\omega + \omega^{-1}}{2}. $$ For concreteness, here is the probability that $\Delta = 0$ for $s = 0,1,2,\ldots$: $$ 1,0,\frac{1}{2},\frac{1}{4},\ldots $$ These probabilities tend to $1/3$ exponentially fast, alternately being above and below it. In particular, if $s = 1$ then $\Pr\[\Delta = 0\] = 0$, and otherwise $\Pr\[\Delta = 0\] \geq 1/4$.

This suggests the following algorithm, in the case in which the two computers are allowed shared randomness:

1. Both computers extract $k$ random functionals $\varphi\_1,\ldots,\varphi\_k$ from the common randomness.
2. Computer 1 sends $\varphi\_1(A),\ldots,\varphi\_k(A)$ to Computer 2.
3. Computer 2 computes $\varphi\_1(B),\ldots,\varphi\_k(B)$, and outputs Yes if $\varphi\_i(A) \neq \varphi\_i(B)$ for all $1 \leq i \leq k$.

If the two vectors differ in exactly one location, then Computer 2 always outputs Yes. Otherwise, it outputs No with probability at least $1 - (3/4)^k$. Choosing $k = 3$, we get $1 - (3/4)^3 \> 1/2$.

What if the computers are not allowed shared randomness? A standard trick allows us to simulate shared randomness using an overhead of $O(\log m)$. In total, the communication complexity is $O(\log m)$.
> 3 votes

# Answer
Hint: take a look at the standard randomized protocol for EQ (checking whether Alice and Bob have exactly the same string). You can use it to help you solve your problem.

Meta-hint: Review the material in your textbook and lecture notes carefully before beginning the homework. Often the homework is chosen so that, if you do that, you'll have a huge leg up on solving the problems.
> 0 votes

---
Tags: algorithms, randomized-algorithms, randomness
---


# Question
Title: Can we quantify how close a partially correct programs is to being correct?
I know that there is something called partial correctness, but I was wondering if there was a way to tell how close a semi-correct program is to a fully correct program.

For example, if you had a sorting program that almost completely sorts an array, could you use Hoare logic to determine how close it is to getting the correct answer? One way to do this would be to make the precondition a series of and statements and see how many of these statements the weakest precondition, resulting from the postcondition being propagated through the program, would be able to imply.

However, this method seems to be very crude. Is there any other way to do something like this?

# Answer
Partial correctness does not mean that not all statements of a specification are met by an algorithm. Have a look at the Wikipedia article about correctness:

**Partial correctness** of an algorithm means that it returns the correct answer if it terminates.

**Total correctness** means that is it additionally guaranteed that the algorithm terminates.

Such a proof of termination can e.g. be done by a **loop variant**: To proof that a loop terminates we show that an integer expression is decreased in the loop body and that the expression stays always non-negative. Then the loop can be only iterated a finite number of times. The B-Method uses such integer variants in its while loops. An alternative for an integer expression would be a finite set where in each iteration an element is removed.

**Example**: A simple algorithm to initialise an array of size n with 0:

```
i := 0
while i<n do
  x[i] := 0
  i := i+1
done

```

Partial correctness can be proven by using a loop invariant ("all elements of x in `0..i` are 0", `0<=i`, `i<=n`). One must show that the invariant is fulfilled when entering the loop and after each iteration. After the loop we know that the invariant is fulfilled and the loop condition not (`i>=n` together with the loop invariant implies that `i=n`, that again implies "all elements of x in `0..n` are 0"). Even if we forget the line `i := i+1`, we could prove the partial correctness of the algorithm, i.e. the array will be filled with 0 after termination. The problem would be that it does not terminate.

Termination can be shown by choosing `n-i` as a variant. With the invariant `i<=n` it can be proven that the variant is always non-negative and `n-i` is decreased (by increasing i) in every iteration. Thus the loop must terminate. Together with partial correctness, total correctness is shown.
> 5 votes

# Answer
## In a nutshell:

Partial correctness is an issue of termination, not ot correctness of what is computed. A function is partially correct with respect to a specification iff whatever it computes is correct, when it terminates. This idea can be extended to the computation of incomplete (partial) answers. Whatever is computed of the answer is correct, but the program may at some point go into a non-terminating loop, possibly without having computed all of the answer. Partial answers are approximations of complete answers.

This approximation structure is a partial order, which is the basic concept of Scott's semantics domains,and it can actually be used to answer another interpretation of the question. Can we measure a distance between a correct answer and a not quite correct one, such as having one element of an array that is wrong (rather than unknown). One way to define such a distance is to consider the approximation ordering, and relate the two incompatible answers (the correct one and the incorrect one) to the best partial answer that is an approximation of both. This issue is quickly looked at from the point of view of numerical analysis, where precision analysis is essential, and of some other areas.

This second point is actually explored in a second answer to the question, as I did not realize at first that the two answers could have a connection. But both answers are quite long, and I did not feel wise to merge them when I realized the connection.

## A first simple view of partial correctness

**There is no such thing as being (partially) correct in an absolute sense**. A program is correct if it meets a specification, however given. The specification may be another program, or a logical statement, or whatever can be formalized. The specification must somehow include information on when the program terminates, possibly always (which is actually assumed in most definitions, so that nothing more complex needs to be said). *Actually the domain may be restricted in the specification to the part where termination is expected, so that termination is always expected*, which may justify assuming termination in the whole domain in the usual definition (wikipedia and wikipedia). This in turn imposes an implicit assumption on any specification, which may be, or may not be, so convenient.

**A program $P$ is correct with respect to a specification $S$ iff it terminates whenever the specification says it should, and with a result that meets the specification. It is partially correct iff it sometimes does not terminate where the specification says it should, but always gives a correct result when terminating.**

As a consequence, *a program that never terminates is partially correct with respect to any specification*.

I chose a slightly extended definition also because *it corresponds precisely to the notion of approximation in Scott's semantic domains*, such as used in denotational semantics. A Scott domain includes a partial order corresponding precisely to th the idea of partial correctness (the two uses of the word "partial" are somewhat unrelated). A function $F$ is and approximation of a function $G$ is $G$ terminates whenever $F$ terminates, and both give then the same result. So $G$ may give a result when $F$ does not. And we can say that $F$ is partially correct with respect to $G$, or that $F$ approximate $G$, or $F\sqsubseteq G$.

These ideas are essential to define the semantics of functions with loop (or recursion) as the limit of an infinite set of functions without loop or recursion. See for example wikipedia, or a very informal presentation on SE.

Standard Hoare logic will work only to prove partial correctness, and need to be extended to address termination properties, hence to address total correctness (see wikipedia). There are implemented examples of such specific extensions.

Proving total correctness amounts to proving partial correctness and termination. Hoare logic is quite appropriate for partial correctness. Proving termination requires usually a proof by induction (recurrence) which is the natural approach to proving things in Scott's semantics (as the semantics itself is defined that way, inductively). The answer by danielp shows how such an induction can complement a proof in Hoare's logic.

As to quantifying partial correctness, assuming you still want to do so, it could be by somehow identifying the parts of the domain where the program does or does not terminate, or some properties of those parts.

## Extension to complex results, applied to the sorting example.

Actually, the issue can be a bit more complex, when you consider complex answers, such as data structures (which is the case when sorting arrays). The specification could require the computation of two answers (i.e., a pair), and for some parts of the input domain an actual program could find one element of the pair, but not terminate while computing the other, in other cases find only the other element, or find both, or find none. This is still approximation in Scott sense, and such a program is partially correct.

More generally, the idea of approximation in the Scott sense applies to data as well as to program. For that, informally, you need the concept of an unknown answer (not yet computed, possibly never known if its computation does not terminate). It is usually represented by the symbol $\perp$. The pair $(\perp,36)$ approximates $(25,36)$. What you get on a program that delivers the 36 part and then does not terminate can be represented by $(\perp,36)$.

**How can this be applied to a program that sorts arrays of five integers?** Suppose you write a program SORT5 that runs in parallel to your main application (I am trying to make things realistic), and is supposed to sort such an array for the application. The program SORT5 is supposed to store its result in some array provided by the application, and it can do so separately for each element, as soon as it knows where to place it. It first looks for the largest and the smallest, and stores them at both ends, then it tries to do a recursion (or whatever), but has a bug that sends it into an infinite loop without any further results. The main application still gets a partial answer. If the array to be sorted was $\[25, 36, 3, 9, 12\]$, the answer provided is $\[3,\perp,\perp,\perp,36\]$ instead of $\[3,9,12,25,36\]$. Whatever is provided is correct, and the rest is not computed, so that you have only **part of the answer**. You thus have an approximation of the desired result. If you can prove that that is always the case, then your buggy program SORT5 that does not terminate is still partially correct with respect to the specification of a sort program.

**A partially correct program can be useful.** It could be that you did not really need sorting, but only the largest and smallest element. In that case the fact that your sort program SORT5 does not terminate and is only partially correct will not matter, and you application will work and hopefully terminate with a correct answer.

But who will stop your rogue sorting algorithm that will go on wasting computing power? There are computation strategies (lazy evaluation), that will not run a subprogram when more information on its result is not currently needed. So after you got the largest and smallest element, the program SORT5 would be on hold until other elements are asked for.

In this case, of course, there could be a way of quantifying the partial correctness. However I am not sure it would be very useful.

In this context, is necessary to revise a bit the definition, which I am doing somewhat informally:

**A program P is partially correct with respect to a specification S iff it gives a complete answer that meets the specification before terminating, or provides part of an answer that meets the specification before going into a non terminating computation that provides no further part of the answer.**

Then, *a program that never terminates, and produces no part of result, is partially correct with respect to any specification.*

Note that this definition leaves out a program that keeps computing, ever producing new parts of the answer. But since it does not produce infinitesimals (I do not know that this could make computational sense), it is actually computing an infinite answer.

These techniques can actually be very fruitful to formalize the semantics of computation of infinite object (only for very patient users), such as the exact decimal (or binary) representation of the value of $\pi$, or infinite lists. There are other interesting applications. But this is far from the initial question, and that is why I am leaving it out.
> 4 votes

# Answer
Quantifying the correctness of programs is actually a pretty hot topic in the context of formal methods, nowadays. Instead of posting a list of references, you may start here¹ (full version here) and continue from the references. Disclosure: this paper is a work of mine.

A brief summary of this work: we introduce a specification formalism that augments linear temporal logic by a set of "quality functions". These functions are chosen by the designer, thus giving the designer the ability to define quality as he pleases.

We show that model-checking for this logic is in PSPACE. Using the appropriate quality functions, you can measure e.g. the distance of an array from a sorted one.

---

1. Formalizing and reasoning about quality by S. Almagor, U. Boker and O. Kupferman (2013)
> 2 votes

# Answer
In principle it is possible to express this condition using something like Hoare logic, but it's not clear it will be very useful or practical to do so.

Consider a function $f$ in your program, with one argument. Suppose we have a predicate $P(x,y)$, expressing the condition that $y$ is the correct answer to the input $x$, i.e., if $f$ produces output $y$ on input $x$ then this output is correct. Also suppose we have a predicate $Q(y,y')$ expressing that the answers $y$ and $y'$ are close to each other. Define the predicate $R(x,y')$ by

$$R(x,y') \equiv \exists y . P(x,y) \land Q(y,y').$$

Then $R(x,y')$ expresses the condition you want, i.e., that $y'$ is close to the correct answer to the input $x$.

In your example, $P(x,y)$ could express the statement that $y$ is a sorted version of $x$, and $Q(y,y')$ could express some distance metric on lists (e.g., that $y'$ can be obtained from $y$ by a small number of transpositions).

Now that's just the problem of specification. There is a separate problem of verification, i.e., verifying that a function $f$ meets the spec $R$. The verification problem might be ugly and difficult in practice. And, verifying whether an implementation of a function meets a particular spec is undecidable in general, as jmite states. So, as always in verification, you're always dealing with undecidability (e.g., incompleteness).
> 1 votes

# Answer
## Incorrectness

*I wrote a first answer about partial correctness, which has a precise technical meaning. I thought better to separate this other answer which I initially though to be technically very different. It turns out not to be quite true, but both answers are long enough, so I thought better not to merge them*

Apparently it seem that the OP is more interested in an idea of programs that are partly incorrect, of finding answers that incorrect in some respect, though, I guess, hopefully not too far of being correct.

There are actually two way you may want to consider closeness to correct for a function:

* whether computed answers have correct aand incorrect parts, or
* whether they are sometimes correct, and sometimes incorrect.

But these two aspects can be combined. If you manage to define something like a distance between values in the answer set, you can then try to extend that into a distance between functions that is, extremely informally, some kind of integral of the distance of their result for every point of their domain, or some other function of the incorrectness for every point of the domain.

Then the issue may be to determine if the distance between the completely correct function and the programmed one does not exceed some fixed threshold, or whether the error on the result of applying the function does not exceed for each domain point a threshold that may be related to this domain point.

These techniques may also be useful to do computation as correct as possible, with data that is in some sense not correct to begin with, such as experimental results. When the degree of incorrectness can be evaluated or hypothesized, this can help keep track of its effect on computation.

This is probably very dependent on the kind of data you are computing on.

I believe there is already such a theory for numerical computing, and is often applied for technical work, but I know little of it. Elementary aspects are often taught in physics courses.

Much **numerical computation** deals with real numbers. It cannot be exact (correct) because computer use only approximations of real numbers (there is a concept of computing with exact real arithmetics, but it is a very different topic, very much related theoretically to partial correctness). Aproximations in numerical computation cause small errors (rounding errors) that can propagate, and sometimes grow out of hand. Hence numericians have developed techniques to analyse their programs and evaluate how close the answer is to the correct result. They actually design their algorithms so as to minimize the computational errors, in addition to the other usual criteria, because the order of some operations may have a profound influence on the the size of the error being propagated.

These techniques are also important because they often have to deal with **physical data** that is itself only "close to correct", i.e. given with some approximation. Handling the errors on the input together with computational errors, and their propagation is, I believe, the object of significant research in the field of Numerical Analysis. But I am no expert. Some program will compute both the approximate result and an error interval around it where the correct answer is to be found. This compounds both the physical measurement errors and the numerical computation errors.

However, while this was essentially unavoidable in numerical mathematics dealing with reals (a continuous set of values), there no similar built-in limitation on **symbolic computation**, hence no obvious incentive, a priori, to develop similar techniques. Furthermore, it may not be obvious to do it.

Still, a close look at error handling techniques in parsing and natural language processing show that they actually use a similar conceptual view, even in a purely symbolic context.

The answer of Shaull seems to indicate that one may be interested in such approximation ideas in **software engineering**, but I am not sure it deals with the same concepts. I have not read his paper and I have read little of the litterature on this topic, and the answer gives no hint of the techniques he may be considering.

It may be a very different idea, since software engineering is much concerned with measuring how buggy the sofware may be, but inadvertantly buggy. I know that some statistical analyses show that various parameters that can be measured on a program are statistically related to the quality of the program, it maintainability and the likelihood of bugs.

The ides of approximate answers in numerical analysis (for example) is not a matter of bugs, but of handling the limitations of physical measurements, as well as the limitations of computing (which is inherently countable) when it is used to deal with reals (which are uncountable). If it is a bug, that is the fault of our universe, not of programmers.

## Attempting to unify the issues: partial correctness and incorrectness measurement

The following is purely speculative, and an indication of work that could be done. I would suspect that at least some of it has been done already (I did not search thoroughly). But I do not recall reading about it and cannot give proper references. *The description is only a sketch, and it is likely that much of it should be refined or made more precise, including the choice of definitions. I cannot garantee anything that I have not fully worked out mathematically (and even then ... :).*

There is published litterature on real number computation based on definitions of real numbers approximations that organizes them in a Scott domain. Approximating reals with intervals is certainly a way to do it, and that is one proper way of developping a theory of computability over the reals. My guess is that it must have already been done, and it offers a good basis for a semantics theory, and for analysing real number crunching programs together with an assessment of the precision of the result as described above. (I did not have the opportunity to ask a specialist).

Now this may be a hint on what to do with symbolic computation, or with computation over the integers, to get a notion of approximately correct computation, espcially in the presence of complex data, i.e. the use of data structures.

The basic idea is the same as for real, use a concept of approximation and organize your computation domain (the values you compute with) as a Scoot domain. However, it will need to be something like a lattice, where two elements must have a greatest lower bound (glb or meet) as well as a least upper bound (lub or join). In the numerical case, the glb corresponds to the smallest interval containing 2 other intervals, and the lub to interval intersection.

Taking our sorting example from the first answer, sorting an array of 5 numbers $\[25, 36, 3, 9, 12\]$, we could consider all partial arrays as a lattice, and have:

* $lub(\[3,\perp,\perp,\perp,36\], \[\perp,9,\perp,\perp,36\])=\[3,9,\perp,\perp,36\]$
* $glb(\[3,\perp,\perp,\perp,36\], \[7,9,\perp,\perp,36\])=\[\perp,\perp,\perp,\perp,36\]$

Now, if you define a notion of distance in the order structure, then you can define the distance between two possible answers as the sum of their distances to their *glb* (or some other symmetrical and monotonically increasing function of these two distances).

If the domain does not have *glb*, you can take the distances according to each of the lower bounds (actually only the maximal elements of the set of lower bounds), and consider the smallest such distance (or possibly some other function of the distances of maximum elements, with adequate properties).

The inportant point is to have a tractable definition of correctness distance over the data you manipulate.

Then, this notion of distance can then be extended to mesuring distances between functions, which should be an answer to the question asked. I am not sure how much extra mathematical aparatus is needed, since some form of integration (in the calculus sense) may be needed.

A cursory search of the web about these issues yielded the following paper: "Towards Computing Distances between Programs via Scott Domains" which is already 15 years old. It should provide a better mathematical background. But I found it after writing this answer.

This problem can possibly be adressed with other logic, but I suspect it is much more an issue for the concept of approximation within domains of values. There are other ways to build them than the one described above for arrays. Defining approximations to data could be part of the definition of an abstract data-type, or of a class in OO programming.

<sub>Note: I did not expect this connection with my previous answer. hence the two separate answers.</sub>
> 1 votes

---
Tags: formal-methods, software-verification, program-correctness
---


# Question
Title: Partial Range Query on Inverted File with Combined Index
I am currently reading Multidimensional and Metric Data Structures by Hanan Samet for fun. The combined index is discussed on page 5-6. I do understand it in the sense that the inverted file itself is an index, and then we extrapolate another index by lexicographically ordering the attribute.

So, given a record with four attributes (Name, X, Y, Z), that is, the name and three dimensional point in space. If I created the inverted file such that it maps Name to the X,Y,Z attributes, then we can create another index by lexicographically ordering the attributes X,Y,Z. The possible orders would be XYZ, YXZ ZYX.

Do we order by the values of XYZ in the inverted file at all? Does the index of lexicographically ordered XYZ attributes point to the inverted index, which thus makes it combined?

Any help is greatly appreciated!

# Answer
> 1 votes
I don't think you've got the idea for an inverted file quite right. If there are three attributes (`X`, `Y`, and `Z`), the natural approach is to have *three* inverted lists:

* The first list maps from the value of `X` to the record (or from the value of `X` to the `Name`, if the `Name` is unique for each record and is how the record is identified).
* The second list maps from the value of `Y` to the record (or from the value of `Y` to the `Name`, if the `Name` is unique for each record).
* The third list maps from the value of `Z` to the record (or from the value of `Z` to the `Name`, if the `Name` is unique for each record).

So, if there are three attributes, we might end up with three inverted files.

See Figure 1.2 in the book for an example of an inverted file.

---

Now for the idea of a *combined index*. A combined index for the attribute ordering XYZ would be a sorted list of records, where the sort order works as follows:

* If two records differ in their X attribute, then order them by the value of their X attribute (and ignore their Y,Z attributes).
* If two records have the same X attribute but differ in their Y attribute, then order them by the value of their Y attribute (ignoring their Z attribute).
* If two records have the same X and Y attributes but differ in their Z attribute, then order them by the value of their Z attribute.

This is known as lexicographic order, where the attributes are taken in the order X,Y,Z. You can think of this as XYZ-lexicographic order. Once we sort using this particular order, we get a combined index for the attribute ordering XYZ.

Of course we could also form a combined index for other attribute orderings as well. We might form multiple combined indices, each with a different attribute ordering. The order in each combined index is different. If there are $n$ attributes, we could have up to $n!$ different combined indices, corresponding to the $n!$ different permutations (orderings) on the $n$ attributes. Nothing says we have to store all of those possible combined indices; we could store just one of them, or some of them, or all of them, or none of them.

---

A combined index is different from an inverted file.

However, you might notice that if you have a combined index for attribute order XYZ, then this obviates the need for an inverted file for attribute X, since you can use the combined index for XYZ in any place where you would have wanted an inverted file for X.

---

This is all explained pretty clearly in the book you cited. I recommend you work through the example in Figures 1.1 and 1.2 in the book, to better understand inverted lists.

---
Tags: data-structures, combinatorics, databases, structured-data
---


# Question
Title: Algorithm: Dimension increase in 1D representation of Square Matrix
Consider the matrix with dimension $m \times m$:

$$ M = \begin{array}{cc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array} $$

Its 1-D representation: $$ M^\* = \begin{array}{cc} 1 & 1 & 1 && 0 & 1 & 1 && 1 & 0 & 1\end{array}$$

Now, another dimension added, so that the matrix becomes:

$$ N = \begin{array}{cc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} $$

$$ N^\* = \begin{array}{cc} 1 & 1 & 1 & 0 && 0 & 1 & 1 & 0 && 1 & 0 & 1 & 0 && 0 & 0 & 0 & 1\end{array}$$

**Update**
The data structure can be any linear data structure (Array, Single LL, Double LL) not necessarily contiguously linear. The goal is to dynamically add or remove dimensions from the Matrix with least number of operations.

The best I can think of is to repopulate $N^\*$ in $\theta(N^2)$ every time a new dimension is added.

# Answer
> 6 votes
There is a simple solution, but it requires a different 1D representation of your matrix $M$. You suppose it is stored in an arbitrarily long 1D array $A$, so that new elements can be added.

Then the elements of the matrix $M$ are stored such that: $M\[i,j\]$ is stored in $A\[k\]$ with $k=(j-1)^2+i$ if $i\leq j$ and $k=i^2-j+1$ otherwise.

Other similar formulae are also possible.

The idea is to stores in order the successives layers of increased matrix size starting with the $1\times 1$ matrix.

Storing order of a $3\times3$ matrix is described here, each element of the matrix being its index in $A$. The first index $i$ is the line index of matrix $M$ representation:

> 1 2 5
> 4 3 6
> 9 8 7

When you increase the size $m$ of the matrix, you only have to add the new layer at the end, i.e. add the representation of the last row and last column at the end of the used part of array $A$. The cost is linear in $m$.

**Explanation**

The initial version of the question asked for a linear data structure, without explicitly allowing for linked-lists, which I do not consider more linear than anything else, the memory having generally a linear address space. Hence I assumed the idea was to use, as efficiently as possible, a one dimensional array $A$, without trying to mimic pointers.

I started looking for an efficient way to store (and retrieve) the elements $M(i,j)$ of the matrix $M$ in $A$, so that extending the matrix with an extra dimensional layer for the highest values of the indices, could be done cheaply ... the cheapest being to add the new layer right at the end of the existing matrix, so that the cost would be no more than the number of elements to be copied.

To do that, while keeping a uniform indexing scheme requires to have done it uniformly, starting from the $1\times 1$ matrix. The question being somewhat imprecise regarding constraints, I assumed that keeping each line in one contiguous piece is not really required.

The placement of the elements of matrix $M$ in the linear array $A$ is illustrated by the above $3\times 3$ matrix, where each element has the value of its index in $A$.

This organization is such that the index in $A$ of an element $M(i,j)$ of the matrix $M$ does not depend on the size of $M$, but only on $i$ and $j$. Taking $p=max(i,j)$, the placement in $A$ of the upper-lefmost submatrix of $M$ of size $p$ is independent of the rest of the matrix $M$. The element $M(i,j)$ is either on the rightmost column of that submatrix if $i\leq j$, or on its last line otherwise. Furthermore, the first $(p-1)^2$ elements of array $A$ are already used to store the upper-left submatrix of size $p-1$. One uses the next $2p-1$ elements of the $p^{th}$ row and $p^{th}$ column, which contain element $M(i,j)$. This can be done in different ways, and the proposed formula stores these $2p-1$ elements in top-down and right-to-left order.

*Note: the first version of the formulae used $p=max(i,j)$ explicitly to compute the squares, a remnant of my initial search for a solution. But @WeaklyTyped remarked rightly that the test comparing $i$ and $j$ does the job, allowing to replace $p$ by $i$ or $j$, according to the test result.*

**Actual use of the representation**

One characteristic of this representation is that it preserves random access (access time is constant and independent of indices and matrix size), which is not usually the case with list representations. However it does not require multiplication for indexing the array $A$, since only addition and integer squares are needed. Integer squares can be memorized in a linear array, or can be computed with addition only if successive square values are needed in a loop, for example to read a line or a column of the matrix, using the formula $(p+1)^2=p^2+2p+1$.

But, as usual, the usefulness of such a representation is highly dependant on the operations needed and their frequency.

*Note: this representation was found independently, but it may have been used before. Pointers to the literature are welcome.*

## A better solution with pointers

(*Added July 1st 2014, after the answer was accepted*)

The layer approach described in the previous algorithm seems more effective than most pointer based representations for two reasons:

* given $i$ an $j$, it allows access of element $M\[i,j\]$ in constant time;
* it has no overhead in space for storing pointers (not to mention possibly greater garbage collection costs).

However, the last statement is not completely true. We chose to use an array $A$ of "sufficient" length because that initially (in the first version of the question) seemed a given constraint. But, if we relax that constraint, it is clear that it is a costly solution in space since the array $A$ must have a size sufficient to store the largest version of the matrix $M$ that may be used.

Actually, there is something absurd about the solution presented above, if it is to be more than an intellectual exercise (but the context and motivations of the question were not given). If the array $A$ has the maximum size that will ever be needed, why not simply code the maximum sized matrix in it, and use at any time only the indices that are actually needed, given the current matrix size $m$?

Since pointers are (now) allowed, this is a good motivation for attempting to get the benefits of the solution presented above, without its absurd drawback.

The idea is quite simple: keep the layer structure presented above, but store the layers separately, rather than contiguously in the same array.

So a matrix $M$ of size $m$ is implemented as $m$ arrays $L\_p$ with $1\leq p\leq m$, each $L\_p$ having $2p-1$ elements corresponding to the elements $M\[i,j\]$ of $M$ such that $max(i,j)=p$.

In order to access $M\[i,j\]$, one only has to compute $p=max(i,j)$ to locate $L\_p$, and then index appropriately with $i$ or $j$ inside $L\_p$ to get the right element. Actually, as in the first algorithm above, it may be faster just to have two cases based on a comparison between $i$ and $j$. I do not get into the detailed formulae, that are somewhat obvious to work out.

However this require an extra structure to find a pointer to $L\_p$ when $p$ is known.

Three obvious ideas come to mind:

* The first idea is to use an **array of links** to the $L\_p$ layers, which is indexed by $p$. The drawback is that the size of the array must be the maximum possible value for $m$, but that is not as bad as the maximum values for $m^2$. The advantage is that accessing any element $M\[i,j\]$ will still be in constant time.
* The second idea is to use a **linked list**, which avoids the constant size array. However, the list has to be followed sequentially to get the right layer $L\_p$. Hence accessing any element $M\[i,j\]$ will on the average be in linear time with respect to the current size $m$. Note that, with this solution, it is better to access the list from the end corresponding to the largest value of $p$. Firstly, that is where layers are added or removed. Secondly, assuming that all elements of $M$ have equal chance of beeing accessed, the probability of finding an element in layer $L\_p$ is proportional to $(2p-1)/m^2)$, hence a higher probability for higher values of $p$. Indeed, accessing the list from the higher value of $p$ is on average twice as fast as accessing from the lower values of $p$ (proof left as an exercise). But access is linear in $m$ in both cases.
* In order to reduce access time, the accessing structure can be a **balanced tree**. The size of the tree is linear in $m$, as it is with a simple list, but the time complexity of finding the right $L\_p$ is now logarithmic in $m$, hence also for accessing an element $M\[i,j\]$. While building this balanced tree, it is better to give to each $L\_p$ a weight proportional to $2p-1$ to account for its probability of being the right layer. However, I have not checked how much of a difference it makes.

But actually, trying to build a sophisticated balanced tree is probably self-defeating sophistication, because it may have to be maintained, and it may require more computation to be explored. A better solution is probably a widely branching tree that is walked very simply by indexation.

## Using a tree of indexing arrays

(I have no idea whether this has an official name in textbooks)

The nodes of the tree are arrays of length $2^d$, so that we can build a balanced tree with nodes of degree $2^d$. The leaf nodes are arrays of pointers to matrix layers, and the other nodes are arrays of pointers to other arrays (or nothing). Without going into details, given a layer number $p$, The binary representation of $p$ is cut into chunks of size $d$ which are used as indices for the arrays while walking down the tree to find the layer $L\_p$. With a value for $d$ of 3 or 4, this should give simple and fast access for matrices of significant size.

# Answer
> 2 votes
You can use two linked lists. The first one holds the matrix entries and the second one points to the entries that are endpoints of rows. To add a new dimension, scan the second list and insert the elements of the new dimension next to the positions recorded in the second list (update the second list on the fly). Once you reach the end of the second list, continue inserting the remaining elements of the new dimension and at the end, record a pointer to the last element added (in the second list).

Say your matrix looks like:

```
1 0
2 0

```

The lists would like like:

```
L1: 1 <-> 0 <-> 2 <-> 0.
L2: position 2 <-> position 4.

```

Adding a new dimension (say `-1 -2 -3 -4 -5`):

First position is 2, so add element -1 next to position 2, resultant list looks like:

```
1 <-> 0 <-> -1 <-> 2 <-> 0.

```

Update second list: Position 2 is now 3 so second list looks like:

```
L2: position 3 <-> position 4.

```

Move to next position (which is position 4) and do the same. After operation, lists would look like:

```
L1: 1 <-> 0 <-> -1 <-> 2 <-> 0 <-> -2.
L2: position 3 <-> position 6.

```

We reached the end of list 2 so go on and add the remaining elements to the end of first list. First list now looks like:

```
L1: 1 <-> 0 <-> -1 <-> 2 <-> 0 <-> -2 <-> -3 <-> -4 <-> -5.

```

Last, record position of last element added:

```
L2: position 3 <-> position 6 <-> position 9.

```

In an actual implementation, you would be manipulating pointers rather than integer positions. This solution preserves the row major ordering of the entries.

---
Tags: algorithms, matrices
---


# Question
Title: Why can't configuration counting decide undecideable problems?
I know it might sound like a silly question, I just can't get my head around it...

I just read that $DSPACE(f(n))\subseteq DTIME(n\cdot 2^{O(f(n))})$.
The proof for it relies heavily on the fact that for a given $L\in DSPACE(f(n))$, the turing machine $M\_L$ (which decides $L$ while consuming no more than $p(|x|)$ memory space for some polynomial $p$ and input $x$), under the assumption that it **decides** $L$, cannot have the same exact configuration twice (otherwise it's stuck in an infinite loop), and therefore, we can bound the runtime of $M\_L$ by counting the number of possible configurations, which is $n\cdot 2^{O(f(n))}$.
The thing is this;
If ($M\_L$ decides $L$) $\Rightarrow$ (There are no two similar configurations in $M\_L$)
Why doesn't (There are two similar configurations in $M\_L$) $\Rightarrow$ ($M\_L$ won't decide $L$)?
Why can't configuration counting decide $A\_{TM}$, for example? ($A\_{TM}=\left\\{(M,w)|M(w)=ACCEPT \right\\}$)

# Answer
Configuration counting can certainly detect infinite loops. But only if space is bounded. A TM could write non-repeating nonsense on the tape and never get caught.
> 4 votes

---
Tags: undecidability
---


title: What does "non-pathological data" mean?

text:
# Question
Title: What does "non-pathological data" mean?
I took an algorithms class on Coursera. The professor in the video about hash tables said that

> What's true is that for non-pathological data, you will get constant time operations in a properly implemented hash table.

What does "non-pathological data" mean? Can you give some examples?

# Answer
Pathological data is supposed to be data that makes things go wrong in some way for your intended computation. It can be called *pathological* when it is rare enough in actual uses, so that things work OK most of the time. This can sometimes be made mathematically more precise (for example with probabilities), but the use of the word pathological in often informal.

For example, tomato salad and ketchup are excellent food, except for pathological people, meaning those people who are allergic to tomatoes. It can actually kill in some cases. But people allergic to tomatoes are very rare so that tomato dishes are considered excellent, except in pathological cases.

There are many algorithms that, while having a worst case complexity above the optimal one, are on the average as good or better than worst case optimal algorithm. If you compare quicksort and merge sort, quicksort is time $O(n^2)$ while merge sort is $O(n \lg n)$ in the worst case. But people will often use quicksort, because they both are time $O(n \lg n)$ on average, and the space complexity is $O(\lg n)$ for quicksort and $O(n)$ for merge sort.

The fact that quicksort is as good on average may be attributed to the fact that the $O(n^2)$ time complexity actually occurs only on pathological (implying bad but rare) cases.
> 15 votes

# Answer
Pathological data is data that will make the algorithm perform bad. For hash tables, pathological data is data that causes collisions. That of course depends on the hash function being used.

For example, if your hash function adds the characters together: `hash("abcd") = 'a' + 'b' + 'c' + 'd'`. Then pathological data looks like:

`{"abcd", "dcba", "cbda", ...}`. Any permutation of `"abcd"` will hash to the same position so you will end up with a linked list which you were trying to avoid in the first place.

Non-pathological data is data that is not pathological.
> 11 votes

# Answer
another way to think about this: hash keys are like separate "bins" that contain the data. one would expect/hope that the data is evenly distributed between all the bins, "balanced". for nonpathological data each bin has/contains roughly the same amount of data. if the data is pathological (wrt key hashing algorithm), it all "piles up" in fewer bins, and some bins have far less. this is inefficient because the lookup time increases (and efficiency decreases/converges to that of looking up an unsorted list) when the bins are filled larger. note that merely changing the key hashing algorithm could turn the data from "pathological" to "non pathological" or vice versa, hence the importance of the hashing algorithm.

also there are many other algorithms for which the distinction of "pathlogical vs nonpathological" might be applied, with basically the "pathological" data making the algorithm perform in worse case (eg the concept is also used with sorting algorithms). as you can see its a statistical concept. also for the same problem, data that is "pathological" for one algorithm might not be "pathlogical" for another. etc.
> -1 votes

---
Tags: hash-tables
---


# Question
Title: Is finding negative cycle vertices NP complete?
I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in this answer too. But then while googling I found another Stack Overflow question it is proved that finding negative cycle vertices are NP complete. So what is it actually?

# Answer
Your question is very unclear.

There is a tremendous difference between: (a) print out one example of a negative cycle, if one exists, (b) print out all negative cycles.

The former can be done in polynomial time using Bellman-Ford. The latter cannot, as there could be exponentially many cycles, so it could take exponential time. (The latter is not NP-complete, as the problem is not even in NP.)

The solution you link to is solving problem (a).
> 1 votes

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


# Question
Title: How do learn the most important nodes in a tree?
I have a list of 20000 words and how often they appeared in a set of 500 newspaper articles. I am trying to build a stemmer which chops off suffuxes from each words, so `walked`, `walking`, `walks` are the same word.

---

In English, the Porter Stemmer is a rule-based system where you repeatedly chop off suffixes:

```
    CONNECTIONS
    CONNECTION
    CONNECT

```

I am concerned if I do this for my collection of **Spanish** words and articles, I may not have a complete list of rules or it may be prone to other forms of error. So I had proposed to *learn* the suffixes.

Right now, I just count the appearances of each suffixed up to 4 letters. Here is the result the most common last letter in my vocabulary list:

```
 u'a': 58189
 u'd': 3183
 u'e': 62971
 u'i': 1725
 u'l': 26374
 u'n': 37823
 u'o': 46786
 u'r': 16833
 u's': 57396
 u'u': 2639
 u'y': 2212
 u'z': 1968
 u'\xe1': 1813
 u'\xf3': 6722

```

The last letters `a` and `o` are obvious things to stem since they indicate masculine and feminine. However `o` could also be the 1st person singular of a verb. `a` could be the 3rd person singular.

`e` and `s` are also obvious choices to stem. Let's look at the last 4 letters:

```
 u'ados': 1826,
 u'ales': 1633,
 u'ando': 1291,
 u'ante': 1062,
 u'aron': 1027,
 u'ci\xf3n': 5355,
 u'ente': 3084,
 u'ento': 1690,
 u'erto': 1061,
 u'idad': 1749,
 u'ncia': 1362,
 u'ntes': 1511,
 u'ones': 2845,
 u'ores': 1050,
 u'si\xf3n': 1127

```

These are very common Spanish suffixes, appearing more than 1000 times in my corpus. Should I stem them?

---

How do I choose a data set which handles the suffixes of different sizes and decides which ones are the most "significant" ?

# Answer
> 2 votes
The first thing you need to consider is that stemming rules are language-specific - a stemmer for the English language will not work for Spanish.

That being said, there is already an implementation which you can use, it's called Snowball and it already has a Spanish stemmer you can use.

The only thing you need to figure out is how you want to install and use it - how you feed it the raw data and what you want to do with the output (store it somewhere, run post-processing on it etc.). There's no point in trying to reinvent the wheel. I've used Snowball and successfully written a Romanian stemmer back in the day (about seven years ago) and I must warn you it's not easy to do it from scratch even when you have all the tools (I had Snowball and the stemmer Dana Cojocaru wrote back then, but I wanted to do it on my own).

Best of luck in your endeavors!

# Answer
> 1 votes
Do you WANT to use machine learning?

Because the simplest solution that comes to mind is to use a word net or dictionary and build an aggregation list based on common definitions. A lot of people worked very hard to catalogue and taxonomize the whole language, so why not use that?

If you decide to go for machine learning you might still need the entire dictionary for training, because your sample set is so small. So the only thing you could gain from ML would be the ability to parse hypothetical constructs that are invalid anyways, and probably wouldn't be used by a serious publication anyways.

---
Tags: data-structures, machine-learning, trees, strings, natural-language-processing
---


# Question
Title: Can a Boolean circuit be considered an algorithm?
Can a Boolean circuit by itself be considered an algorithm (a single step algorithm if you like)? For instance say you have a simple tree circuit with two AND gates as the input gates feeding a single OR gate for a depth two circuit. Now change the AND gates to XOR gates, is it correct to say that I now have a different algorithm for any given input?

# Answer
> 0 votes
Look at the formal definition of algorithm:

* Algorithms works in discrete time, (step by step), defining computational states for each input.
* Algorithms must be independent of its implementation, and each state must be formally described using first-order structures.
* Transitions from one state to another must take a finite and fixed number of terms in the current state.

Circuits works naturally in this way, so you can make an algorithm from here using high-level descriptions (flow charts, pseudocode) or formal descriptions and of course the implementation will be a circuit.

# Answer
> 4 votes
Have a look at Turing-completeness and the Church-Turing thesis (CT). Basically, CT is saying that everything that is computable, is computable on a Turing machine. Many different models of computation are known to be equivalent to the Turing machine. Even if you are considering something esoteric you came up with yourself, if what you have is Turing-complete, you can claim that you really do have an algorithm.

A circuit is a *non-uniform model of computation*, meaning that different size circuit compute things for different size inputs. A Turing machine on the other hand is a uniform model, so it's used for all input lengths. Given a Turing machine, one can construct a Boolean circuit that is able to simulate all its computation if we put a bound on the Turing machine's memory. Also, given a circuit, we can build a Turing machine that simulates the circuit.

# Answer
> 1 votes
I don't think so, because when we think of algorithms (say as Turing machines), they allow the input to be any size. However, a family of circuits can $\mathcal C = \\{C\_n \ | \ n \in \mathbb N\\}$, where we run $C\_n$ on inputs of size $n$, can be said to be an algorithm.

---
Tags: algorithms, terminology, circuits
---


title: Solve recurrence relations

text:
# Question
Title: Solve recurrence relations
> **A)** Solve this recurrence where $T(0)=0$ and write it in O-notation: $T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$

So, I started to calculate:

> $T(1)=2(0)+c=c$
>
> $T(2)=1(0+c)+c=2c$

and so on, which gives me that $T(n)=nc$

This I can prove by induction: $(n-1) \rightarrow n$

> $T(n)= {2 \over n} (0+c+2c+...+(n-1)c)+c = {2 \over n} (c{(n-1)n \over 2} )+c = nc$

Which gives me $O(n)$ (since $c$ is a constant). Am I right with this?

---

> **B)** For $T(n)=kT({n \over k})+ckn$ find the closed form for the function $T(n)=f(c,k,n)$ (I don't know what does this mean) and write it in $\mathcal O$-notation. If you had the algorithm working with $k=2$, $k=3$ or $k=4$ which one would you choose?

I'm stuck with this problem. With the help of the master theorem, I would get $log\_k k = 1$ which would give $\mathcal O(n \log n)$ but how to find the closed form?

# Answer
> 5 votes
To make life simple, assume $T(1)=1$. If we look at this just for integral powers of $k$, i.e. $n=k^m$ for some $k \in \mathbb Z$, we have, by definition, $$ T(k^m)=kT(k^{m-1})+ck\cdot k^m $$ We can repeatedly substitute into the recurrence to get: $$\begin{align} T(k^m)&=k\cdot{\color{red}{T(k^{m-1})}}+ck\cdot k^m\\ &=k\cdot{\color{red}{\[k\cdot T(k^{m-2})+ck\cdot k^{m-1}\]}}+ck\cdot k^m \\ &= k^2\cdot T(k^{m-2})+2ck\cdot k^m\\ &= k^3\cdot T(k^{m-3})+3ck\cdot k^m\\ &= k^4\cdot T(k^{m-4})+4ck\cdot k^m \end{align}$$ and in general we have $$ T(k^m) = k^j\cdot T(k^{m-j})+jck\cdot k^m $$ which could be formally proved by induction.

The whole point of this *iterative expansion*, as it's known, is to drive the $T(\cdot)$ on the right side to a value we know, namely $T(1)$, so we'll let $j=m$ to obtain $$ T(k^m) = k^m\cdot T(k^0)+mck\cdot k^m=k^m\cdot T(1)+mck\cdot k^m=k^m+mck\cdot k^m $$ Finally, since we assumed that $n=k^m$, we have $m=\log\_kn$ and the expression above becomes: $$ T(n)=n+ckn\log\_k n=n(1+ck\log\_kn) $$

For the next part, presumably you're being asked which of $k=2, 3, 4$ will make $T(\cdot)$ smallest. For example, which is eventually smaller, $2\log\_2n$ or $3\log\_3n$? You should be able to answer this with a modicum of effort.

# Answer
> 6 votes
This is similar to the recurrence arising in the analysis of Quicksort, search for "quicksort analysis" to get lots of results.

An easy road is to write: \begin{align} (n + 1) T(n + 1) &= 2 \sum\_{0 \le k \le n} T(k) + (n + 1) c \\ n T(n) &= 2 \sum\_{0 \le k \le n - 1} T(k) + n c \end{align} Subtract to get: $$ (n + 1) T(n + 1) - (n + 2) T(n) = c $$ This is a linear recurrence of the first order. Divide by $(n + 1) (n + 2)$ to get: \begin{align} \frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1} &= \frac{c}{(n + 1) (n + 2)} \\ \sum\_{0 \le k \le n - 1} \left( \frac{T(k + 1)}{k + 2} - \frac{T(k)}{k + 1} \right) &= c \sum\_{0 \le k \le n - 1} \frac{1}{(k + 1) (k + 2)} \\ \frac{T(n)}{n + 1} - T(0) &= c \sum\_{1 \le k \le n} \left( \frac{1}{k} - \frac{1}{k + 1} \right) \\ &= c \left( 1 - \frac{1}{n + 1} \right) \\ &= c \frac{n}{n + 1} \\ T(n) &= T(0) (n + 1) + c n \end{align}

---
Tags: recurrence-relation, check-my-answer
---