# Question
Title: $ADD = {x=y+z}$ with $x, y, z$ binary integers, and $x$ is the sum of $y$ and $z$. Pumping lemma to show that $ADD$ is not regular
Consider the alphabet $\Sigma = \\{0, 1, +, =\\}$ and the language $ADD = \\{x=y+z|x,y$ are binary integers $x$ is the sum of $y$ and $z$ $\\}$.

This is the (informal) solution I came up with (not sure about its correctness). Using the pumping lemma:

Take $s= 1^p=0+1^p$, $s \in ADD$. $s$ can be divided into three parts so that $s=xyz.$ The pumping lemma says that $|xy| \leq p$ and $|y| \> 0$ so $y$ must be in the first $p$ $1's$. Choose $i=0$. Then the equation is false, so the languge $ADD$ is not regular. $\square$

Even though I think this is correct, in the answers they use the string $1^p=10^{p-1}+1^{p-1}$ which is also a correct pick, is mine just another correct pick?

# Answer
Your answer has a slight omission: If perchance $y$ is of length $p$ (note: $x$ is permitted to be empty), then choosing $i=0$ leaves one with, not a false equation, but no equation (the string begins with '='). But of course the conclusion is the same. You can avoid that nit by choosing $i=2$ (say) instead of $i=0$.

And yes, I think yours is just another correct pick.
> 0 votes

---
Tags: finite-automata, pumping-lemma, check-my-answer
---


# Question
Title: p constant in pumping lemma for regular languages
We have a language

$L = \\{ a^{n^{2}}, n \< 12\\}$ We have to find minimum constant P for pumping lemma.

What does p represent here? I thought p in pumping lemma represent number of states , yet the right answer is $p \>= 122$ , i would understand if it was $p \<= 122$.

So for example it would be correct when $p = 155$. But how could we create such automat with 155 states?

# Answer
> 2 votes
The key here is that $L$ is *a finite language*. Therefore it can be recognized by a DFA which has no cycles - in this case, a chain of 122 states, numbered 1 through 122, with transitions on $a$ from each state $i$ to state $i+1$ \[except for a loop on $a$ from state 122 to itself\], with states 1, 4, 9, ..., 121 being final. For P=122, this automaton satisfies the Pumping Lemma - i.e all strings in $L$ of length at least P can be pumped - in a purely vacuous sense, *because there are no strings in $L$ of length at least P*.

# Answer
> -1 votes
From Wikipedia:

> for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y zero or more times are still in L.

So p has to be equal or greater than number of states. If you choose a word w with length \< number of states, you will have no cycles in the path from initial state to final state determined by w, and then you can't find (for every division of w in xyz, with |xy|\<=p and |y|\>=1) a substring y which you can remove from w (or multiply as many times as you want) obtaining a new word w' in L.

---
Tags: automata, finite-automata, pumping-lemma
---


# Question
Title: O(n) sorting array by value - get indexes
I am in search of a linear-time sorting algorithm that is capable of returning an array B of indices A, sorted on the value of the corresponding element of A.

**For example:**

* Input = \[2, 6, 8, 9, 1, 7, 0\]
* Output = \[6, 4, 0, 1, 5, 2, 3\]

**Things I have tried:**

Storing the index and value in one number, using something like this:

```
long number = value << 16 | index;

```

And then applying Countingsort. This however did not work since the JVM couldn't handle an array of ~ 2 million elements. (= the highest "number" value).

The logical solution to that problem was put everything in a map, but I was unsure whether it would still be linear..

# Answer
*Every problem can be solved with yet another indirection:*

First create B as an array of self-indexes - i.e set B\[i\] = i for all i. Next create a 'comparator' object around A, which compares integers i and j by actually comparing A\[i\] with A\[j\]. Now sort B using this comparator.
> 1 votes

# Answer
You included radix sort as a tag. Assuming you write your own radix sort program, it could first sort an array of indices I\[\] according to values in A\[\]. For your example for A, the result would be:

```
A[] = {2, 6, 8, 9, 1, 7, 0}
I[] = {2, 3, 5, 6, 1, 4, 0}

```

In your example, B\[\] is the rank of A. To convert the sorted indices into a rank use something like:

```
for(i = 0; i < n; i++)
    B[I[i]] = i;

```

which will result in:

```
B[] = {6, 4, 0, 1, 5, 2, 3}

```

The entire process would be linear in time.
> 0 votes

# Answer
Assuming you can sort the elements in A in linear time (e.g. they're smallish integers), you can produce an array of indices by sorting tuples of $(a,i)$ where $a$ in an element from A and $i$ is its index

```
index_sort(A):
    B = []
    for i in 0 to length(A):
        append (A[i],i) to B
    sort B in linear time, considering only the first component of the tuples for the ordering
    C = []
    for i in 0 to length(A):
        let (a,j) = B[i]
        append j to C
    return C

```
> -1 votes

---
Tags: algorithms, sorting, radix-sort
---


title: Find Minimum number of platforms

text:
# Question
Title: Find Minimum number of platforms
The questions is as follows with the answer:

> **Q)** Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to wait for another train to vacate the platform. The question basically means calculate the maximum number of trains that would be present in the platform at any given time.
>
> **Answer**
>
> Sort the arrival time and sort the departure time, keep a count initialized to 0. compare the first element of the arrival time with the first of departure, increase the value of count if the value at current Index at arrival is less than the value index at departure and increment the arrival index, and vice versa. Keep the maximum count that you see.

**MY PROBLEM:** I have tried hard but I am not able to get why to sort both arrival and departure timings? As a train is single entity and you sort arrival and departure separately how can we know which train arrival matches with its departure? I am facing the same problem in closest pair problem as why to sort x points and y points separately.

# Answer
The answer is very simple: try to construct an algorithm which *doesn't* sort both arrival and departure times, and see if that's possible. If so, then there is an alternative algorithm which indeed doesn't requiring both times. Otherwise, you will understand why this is necessary.

The intuitive explanation of why we sort both arrival and departure times is that we are actually sorting all *events*. There are two types of events, arrival and departure, and we want to process them as they happen. We don't care about matching departure times with arrival times – that is, for our algorithm to work, we don't need to know which train is involved, only that a train has arrived or has left the station.

This actually suggests a way to restate the algorithm you describe. Sort all events according to time. Now go over them in order of increasing time (we assume for simplicity that all times are distinct). Keep a counter of the number of trains in station. When processing an arrival event, increase the counter; when processing a departure event, decrease the counter. Keep track of the maximal value of the counter.

The algorithm you describe instead sorts the arrival and departure times separately, and then performs an online merge (same algorithm as in merge sort for merging two sorted lists). I don't know why they described the algorithm this way rather than the way I described it.
> 1 votes

# Answer
* Create a single timeline in which an arrival is a +1 and a departure is a -1 (train)
* Then sort on that single time
* Your don't really care which train is at the station but rather *a* train
* When a train arrives +1
* When a train depart -1
* Keep a running total of the trains at the platform / station

If have

```
arrival depart
1       3
2       4

```

Then at time 2 there will 2 trains at the station
And at time 3 then will be 1 train at the station
Must sort on arrival/depart to sync on the two events

I am not good with pseudocode

```
foreach (stop in schedule)
{
    timeline.add(stop.station, +1, stop.arrivalTime)
    timeline.add(stop.station, -1, stop.Departure time)
}

int maxTrains = 0
int trains = 0
foreach (tlStop in in timeline.where(tlStop.station = x).orderby(tlStop.time))
{
    trains += tlStop.arriveDepart
    if(maxTrains < trains)
       maxTrains = trains
}

```
> -1 votes

---
Tags: algorithms, sorting, scheduling
---


# Question
Title: Writing a regular grammar for a regex of decimals
So I've got the regex `/[1-9][0-9]*(\.[0-9]*[1-9])?/` and I'm trying to write a **regular grammar** for it.

I started off like this:

```
S ∶≔ EAB
A ∶≔ DA | ε
B ∶≔ .AE | ε
D ∶≔ 0 | 1 |  2 | 3 |  4 | 5 |  6 | 7 |  8 | 9
E ∶≔ 1 | 2 |  3 | 4 |  5 | 6 |  7 | 8 |  9

```

But I realised that this does not follow Chomsky's rules for regular grammars. So I was wondering how could I adapt this logic into proper notation.

Thanks!

**EDIT:** So below is the NDFA generated from the regex above:

# Answer
Regular grammars (of the right-regular variety) are essentially equivalent to NFAs, in the sense that they include roughly the same information. Once you convert your regular expression to an NFA, you can easily construct from it a right-regular grammar.

What doesn't seem possible is adapting your logic to construct a regular grammar. Unfortunately, there is no simple way to convert an arbitrary context-free grammar to a regular one; indeed, it is undecidable to determine whether a given context-free grammar corresponds to a regular language.
> 1 votes

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


# Question
Title: How to uniquely encode a vector of non-increasing positive integers
Given a vector of positive integers $A=\[a\_1, \cdots, a\_n\]$, where $\sum\_{1 \leq i \leq n}a\_i = n(n-1)$ and $a\_i \geq a\_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the following conditions,

1. The result of encoding is unique, i.e. the encoding of two different vectors cannot be the same.
2. The result of encoding has the same order as the dot-product of A with the vector $\[1, \cdots, n\]$, i.e., $A \cdot \[1, \cdots, n\] \> A' \cdot \[1, \cdots, n\] \Rightarrow e(A)\>e(A')$.

I was wondering if such encoding exists. I tried a couple of options such as $e(A)=A \cdot \[2^1, \cdots, 2^n\]$, but it did not work. I am not sure if considering an irrational number such as Euler's instead of 2 would work, i.e. $e(A)=A \cdot \[e^1, \cdots, e^n\]$.

**P.S.** Of course, one way is using prime numbers, but this way is computationally very expensive and I want to avoid that. So, I prefer a way that does not involve calculating prime numbers and such computationally-intensive values.

# Answer
Define $\[b\_1,\dots,b\_n\]$ by $b\_i = a\_i - a\_{i-1}$ for $i\>1$ and $b\_1 = a\_1-1$. Then $\[b\_1,\dots,b\_n\]$ is a sequence of non-negative integers.

Pick any unique encoding of such sequences, call it $e^\*$, with the property that the output of $e^\*(\[b\_1,\dots,b\_n\])$ is an integer in the range $0..M-1$ for some $M$.

Finally, define an encoding $e$ as follows:

$$e(\[a\_1,\dots,a\_n\]) = M \times \[a\_1,\dots,a\_n\] \cdot \[1,2,\dots,n\] + e^\*(\[b\_1,\dots,b\_n\])$$

where $\[b\_1,\dots,b\_n\]$ is defined as above. Then the encoding $e$ satisfies both of your conditions. Encodings are unique (this follows from the uniqueness property of $e^\*$). Also it satisfies the ordering property (this follows since $0 \le e^\*(\cdots) \< M$).
> 1 votes

---
Tags: integers, encoding-scheme
---


# Question
Title: Floor or Ceiling when getting results for N after doing Big O and Big Theta?
I'm working on my data structures homework and proving Big O and Big Theta for a couple questions. After choosing my values for C and getting to the end I'm left with the fraction 1/300 for $N\_0$ for both Big O and Big Theta. I understood from lecture that we actually take the ceiling of the fraction for Big O, making it 1. My question is, do I also take the ceiling of Big Theta, or would it be the floor? Since Big Theta is a lower-bound.

# Answer
The reason we take floor or ceiling at all in this context is that the definition asks for an *integer* $N\_0$. Now the definitions of big $O$ and big $\Theta$ are both of the form

> There exists a real constant $C \> 0$ and an integer constant $N\_0$ such that for all $n \geq N\_0$, the following holds: ...

Let us denote what should hold by $P(n)$. If you have shown that $P(n)$ holds for all $n \geq N\_0$, then it follows that it holds for all $n \geq \lceil N\_0 \rceil$ as well, since if $n \geq \lceil N\_0 \rceil$ then also $n \geq N\_0$. It doesn't necessarily follow that $P(n)$ holds for all $n \geq \lfloor N\_0 \rfloor$, since if $N\_0$ is not an integer, $\lfloor N\_0 \rfloor \not \geq N\_0$.
> 1 votes

---
Tags: asymptotics
---


title: Is DFA a Moore machine or not?

text:
# Question
Title: Is DFA a Moore machine or not?
I understand the difference between DFA (has finite set of accept states, and doesn't have output function, nor output alphabet) and Moore Machine (doesn't have accept states, but has output for every state). But when implementing DFA in programming language, it always generates output. That is, if it last state was accept then it returns TRUE, to indicate that string was in the language. And if the last state was not accept then it returns FALSE. Thus DFA has output function $G\colon Q \to A$, where $Q$ are finite set of states, and $A = \\{TRUE, FALSE\\}$

So my question is: doesn't that make DFA a Moore Machine?

# Answer
> 2 votes
Imagine a system `S1->S2->S3(final)`.

* DFA transition rules are `(S1,a,S2)` and `(S2,b,S3)`.
* Moore machine rules are `(S1,(a,1),S2)` and `(S2,(b,2),S3)`.

For the input `'ab'`,

* DFA will output `'ab'->TRUE`
* Moore machine will output `'a'->1`, `'b'->2`.

As you can see, DFA doesn't output at each stage. Independent of the input length, you have one output. However, for the Moore machine, size(input)=size(output). Since the input-output relations differ, you cannot conclude that a DFA is a Moore machine.

# Answer
> 1 votes
A Moore machine outputs a symbol after reading *each* input symbol. See its formal definition. In contrast, a DFA "outputs" only once, and its output can only be binary.

More generally, different types of mathematical objects are not described by dictionary-style definitions, but rather by formal definitions.

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


# Question
Title: Question on the definition of computable function and non-terminating behaviour
For example on wikipedia a function $f : \mathbb N^k \to \mathbb N$ is defined to be computable, if there exists an algorithm (in form of a Turing machine, as an $\mu$-recursive function or maybe a C++ programm) such that the following holds:

* If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory
* If $f(x)$ is undefined, then the program never terminates on the input x.

My question concerns the second item, the requirement that for elements $x \notin \operatorname{dom}(f)$ we require the program to end up in an endless loop. But more natural to me would be simply to leave the behaviour unspecified in this case (i.e. just require item 1).

Like for example consider the following quite artificial function: $$ f(n) := \left\\{ \begin{array}{ll} n^2 & \mbox{ if } n \equiv 0 \pmod{2} \\ \mbox{undefined} & \mbox{ otherwise }. \end{array}\right. $$ Then intuitively I would say some programming squaring its argument would compute $f : \mathbb N \to \mathbb N$, but not to the above definition as this programm would also give a result on all $n \notin \operatorname{dom}(f)$.

From a theoretical point of view this could be fixed if $\mbox{dom}(f)$ is decidable (or semi-decidable, in which case the infinite loop would be given by definition that each query $x \in \operatorname{dom}(f)$ should end up in an infinite loop by the definition of semi-decidable), as we simply query if the argument is in $\operatorname{dom}(f)$, and if yes proceed with our algorithm, and if not just enter some idle endless loop.

From another point of view discarding item two above would be easier in proofs, as the case if $f(x)$ is undefined does not needs to be considered. But I can image that someone wants a relationship that the algorithms terminates exactly if $f$ is defined. But does this makes any difference? What would be lost if we just use item one above as the defintion of computability, i.e. $f : \mathbb N^k \to \mathbb N$ is computable, iff there exists an algorithm that computes the correct result if $f(x)$ is defined.

# Answer
> 4 votes
The short answer is that: this part of Wikipedia's explanation kinda sucks. Hey, it happens. Wikipedia is pretty good, but it's not perfect.

The relevant part of the Wikipedia article says:

> Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function $f : \mathbb{N}^k \to \mathbb{N}$ can be calculated if and only if there exists a computer program with the following properties:
>
> 1. If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory.
> 2. If $f(x)$ is undefined, then the program never terminates on the input $x$.

The second sentence is not strictly wrong (that sentence *does* say that "a partial function can be calculated if...") but it sure seems misleading to include that sentence in an article on computable functions, as computable functions are required to be total functions. Also, the combination of those two sentences leaves the wrong impression as it omits the requirement that $f$ be a total function.

Advice: if you're reading something in Wikipedia that seems confusing or doesn't seem quite right, check another source. Check a good textbook -- they are a more definitive source for the precise definition of mathematical concepts.

# Answer
> 3 votes
A computable function is always a *total* function. The definition you mention is that of a *partial* function. A computable function is defined on *all* inputs, and any algorithm for it has to halt on *all* inputs.

Partial functions show up in computability theory exactly because Turing machines can never halt. But computable functions are functions which are computed by Turing machines that *always* halt.

---
Tags: computability, turing-machines
---


# Question
Title: Does integer programming $\in$ NP imply $NP=CoNP$?
Although it is relatively simple to see that integer linear programming is NP-hard, whether it lies in NP is a bit harder. Therefore, I'm wondering whether the following reasoning shows that $ILP\in NP$ implies $NP=CoNP$.

To be precise, I am considering the decision variant of ILP over a non-unary input encoding, so the problem is: given an integer matrix $A$; an integer vector $b$, does there exist an integer vector $y \in Z\_n$ with $Ay \leq b$?

The main issue here is that if we take such an $y$ as NP-certificate, it might be of exponential size in terms of the input, but this of course does not mean a certificate cannot exist.

My idea was that if we assume ILP in NP, we can use a discrete version of the Farkas lemma (see here) to transform an ILP instance with the answer NO to an ILP instance with the answer YES, which then would imply that ILP is in coNP. So we get an NP-complete problem in coNP, which implies that $NP=coNP$. Since most people think $NP\neq coNP$, this is 'evidence' for ILP not being in NP.

However, I'm not sure if my reasoning is correct. In particular, does this 'discrete Farkas lemma' work in polynomial time and create an ILP of polynomial size of the original one?

# Answer
The notion of duality suggested by the discrete Farkas lemma found in Lasserre's paper does not correspond to an integer program. There is a notion of duality for integer programs (see for example here), but strong duality does not hold, so I doubt it can be used along the lines you suggest.
> 5 votes

# Answer
The decision problem version of integer linear programming is known to be in NP. In particular, determining whether an integer linear program has a feasible solution is in NP. It is known that if an integer linear program has a feasible solution, then it has a feasible solution whose length (in bits) is at most a polynomial in the length (in bits) of the input. See, e.g., https://cstheory.stackexchange.com/q/34337/5038.

Consequently, it is unlikely that "integer programming $\in$ NP implies NP=CoNP". If it did (and you found a proof of that fact), you would have found a proof that NP=CoNP.
> 6 votes

---
Tags: complexity-theory, np-complete, np, integer-programming, co-np
---


title: Two-way Hash Functions

text:
# Question
Title: Two-way Hash Functions
While I'm aware most (good) hash functions are one-way (or at least mostly so), I'm wondering if there's any construct (not necessarily called a hash function) which behaves in many ways like a hash function, but can be easily reversed.

For example, a function $f$ takes an arbitrary string $x$ and maps it to $y$, where $|y| = c$ for some constant $c$ (i.e. $y$ is always the same length), and collisions are infrequent, so in general, $f(x) = y$.

In this case, I'm wondering if it's possible to construct a function $f$ matching the criteria above, but where $f^{-1}(y) = x$ is as easily calculable as $f(x) = y$, in a computational complexity sense.

In the case of collisions, where $\forall x \in S$, $f(x) = y$, $f^{-1}(y)$ might give you either the entire set $S$, some subset of $S$, or even a single element from $S$

In the case that this is not theoretically possible, possibly due to the fact that $f$ allows strings of arbitrary lengths and $|y| = c$, so infinite collisions must occur(?), then what if we only allow $|x| \< C$, such that the number of possible collisions are finite?

Obviously, you wouldn't use this kind of function for anything security related, but it might be useful for something like reverse image searching?

# Answer
> 7 votes
Yes, this is possible. Here are two examples of such a function.

One function is $f(x)=x$. This has *no* collisions, and the function is easy to invert.

Here is another function: define $f(x) = x$ if $x$ is 256 bits long, otherwise $f(x) = \operatorname{SHA256}(x)$. Then it is very hard to find collisions for $f$ (since SHA256 is collision-resistant). At the same time, given $y$, it is easy to find an $x$ such that $f(x)=y$, so we might be willing to say that $f^{-1}(y)$ is easily computable. To put it another way, given $y=f(x)$ where we are told $y$ but not told $x$, it is easy to find $x'$ such that $f(x')=y$. The catch is that $x'$ might be different from the original $x$.

# Answer
> 3 votes
In addition to everything that others have said: any *cipher* is an invertible "hash" function. And there are standard ways to construct them; one common way of turning a one-way function into an invertible function is to use a Feistel network.

They're quite useful in practice. See, for example, this question from a few years ago.

# Answer
> 2 votes
A function can only have an inverse if the range is at least as large as the domain. One important property of hash functions is that they map their input to a much smaller output. Therefore every output has many different inputs mapped to it.

While you could in principle invert simple hash functions (in the sense of finding all possible preimages efficiently, where efficiency is measured per preimage generated), there will be a great many of them – infinitely many, in case the function accepts arbitrarily long inputs – so this won't be too useful.

# Answer
> 2 votes
You can create any such mapping function if you don't have any constraints. Your input range can be large, but your data might be sparse, so you can have a mapping that converts the input into a domain with a smaller range, and it is quite possible that it doesn't have collisions (especially in image domain).

For image domain, for example, most of the histogram processing techniques (i.e. gamma correction) can be considered as reversible mapping functions of pixel values.

It all boils down to your mapping function being one-to-one, so that it is reversible.

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


# Question
Title: Approaches to the size constrained weighted set cover problem
I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$. Assuming this is a pretty straight-forward variation of weighted set cover I ended up quite confused with only one, also rather recent paper by Golab et al. \[1\].

Am I missing something here?

\[1\] Golab, Korn, Li, Saha and Srivastava, *Size-constrained weighted set cover*. In \_Proceedings of 31st International Conference on Data Engineering (ICDE), pp. 879–890. IEEE, 2015. IEEE Digital Library; author PDF.

# Answer
> 2 votes
The problem is in P and can be solved in $O(m^k)$ time, where $m$ is the number of sets to select from. For this reason, it is fundamentally different from standard set cover (which is NP-hard) and might not have been studied as much in the complexity theory literature.

---
Tags: optimization, combinatorics, set-cover
---


title: Question of DFA closure properties?

text:
# Question
Title: Question of DFA closure properties?
I have some question about DFA Language properties.

Does closure under intersection and complementation imply closure under union?

Does closure under intersection and union imply closure under complementation?

Thank you

# Answer
> Does closure under intersection and complementation imply closure under union?

This is immediate from De Morgan's laws.

> Does closure under intersection and union imply closure under complementation?

This one is slightly trickier. The answer is no.

Both intersection and union are what is called "monotone". That means that, if you make $X$ or $Y$ bigger then $X\cup Y$ and $X\cap Y$ can't get smaller. By induction, you can prove that any operator defined using only intersections and unions must also be monotone. But complement is not monotone: when you make $X$ bigger, its complement definitely gets smaller. So complement cannot be defined using only intersection and union.
> 3 votes

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Regular expression for the strings without a particular substring
How can we design a regular expressions without particular substrings. The goal of this is to create language `L` which won't contain a particular substring (i.e. 110)

for the case of a regular expression without substring $110$, I Was thinking of: $\require{cancel}\cancel{(101)^\*+}(010)^\*+(10)^\*+(\cancel{1}1)^\*+(\cancel{0}0)^\*+(01)^\*$ but is that over excessive?

Then for example, I crossed out (101)\* because obviously if you have two of those 101101, a subset of that will be 110, which we don't want.

### Notes:

Question has been edited since it gained attention in the past few days. Also see comment for justification.

# Answer
> 9 votes
I did the following multistep technique.

Step 1: make a DFA that accepts all strings with "110". I am able to construct a DFA that accepts all strings with substring "110" and has just 4 states.

Step 2: Flip all the accepting states to non-accepting and all the non-accepting states to accepting. This page at Old Dominion describes the technique quite succinctly. This creates a DFA that accepts the language you want.

Step 3: Now you need to convert the DFA back to a regular expression. As @Alejandro Sazo mentioned there is a proof that this is possible. But you need an algorithm. This paper by Christoph Neumann describes three different techniques. The easiest one is the "state removal technique." You remove a state and replace all the edges between states that were connected to the removed state with edges *labeled with regular expressions.* As you reduce in this way you eventually get to a regular expression for the whole DFA. (Note that Figure 4 in the paper I linked is not quite right. The self-loop on state $q\_j$ should have the regular expression "c e* **b**", not "c e* **d**".)

By going through this process it became clear that: the language you are going to need to solve for this particular problem has the property that once you have seen the sub-string "11" then you can never see another "0".

# Answer
> 7 votes
Here is a *long* answer: create the automata $M$ that recognizes the substring $110$, then create it's complement $\bar{M}$ and translate it into a regular expression. Fortunately this is possible thanks to the theorem:

> If $L = L(M)$ is the lenguage recognized by a DFA $M$, then exists a regular expresion R such that $L = L(R)$

The answer is *long* because the number of steps (build $M$, build $\bar{M}$, create RE). In fact you may need to minimize the DFA before build the RE.

# Answer
> 5 votes
If your question is to find a regular expression for strings that avoid $110$ then a possible answer is $(0+10)^\*1^\*$ as computed by ChesterX. The intuition is clear: after two $1$'s we can only add $1$'s, so that can only happen at the end. Otherwise we are "safe" if we accompany every $1$ by a $0$.

If you question is how to find a regular expression for the expression avoiding subword $w$ in general, then follow the course set by Alajandro and Wandering Logic: (1) make a "linear" nondeterministic FSA for $\Sigma^\* w \Sigma^\*$, (2) determinize (3) complement (4) construct expression by successive state removal.

Here I want to make two remarks.

First, in general the determinization of a FSA can result in a exponentional blow-up in size. Fortunately in this setting this will not happen. The automata obtained are related to the construction of a patternmatching automaton due to Knuth-Morris-Prat.

Second, although the automaton will not explode in size, its structure can be nontrivial.

An example of both observations is given below. The automaton for pattern $11011010$ in both nondeterministic and deterministic versions. For the DFA I have cheated a little. For state $8\*$ we find by the usual algorithm a large set of states, all accepting. That an easily be summarixed by this single state (which becomes useless after complementation).

# Answer
> 0 votes
I used jFlap to draw the DFA.

Then using jFlap again, got the RegEx as : $(0+10)^\*(\lambda+1+111^\*)$

# Answer
> -6 votes
I don't know the real logic but as per my understanding... It is clearly work on the logic of don't accept the 110 .. so it means whenever you got the substring like 110 ... At that time you must be not at a " Final state" so as per the above fig mentioned by my friend it is clear that after accepting the 0 in q2 state we not reach at final state it means ..We not get the final state so system generate error or ignore this type of no to accept ...And our aim to remove or not generate the string which contain 110 is clearly satisfy..

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


# Question
Title: Algorithm: How to find the number of independent sets in a tree?
I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent sets in a tree? The tree is n-ary.

# Answer
Let $T$ be the tree. For every $n\in T$, we indicate the number of independent sets in the subtree of $T$ rooted in $n$ that contain $n$ with $A(n)$, and the number of independent sets that do not contain $n$ with $B(n)$.

The following recursive relations hold:

$$ \left \\{ \begin{array}{r c l} A(n) & = & \prod\_{m \in Adj\[n\]}B(m) \\ B(n) & = & \prod\_{m \in Adj\[n\]}A(m) +B(m) \end{array} \right . $$

Notice that we are using a constant number of memoization cells for each node of $T$. Interestingly enough, if $T$ is a line tree of $k$ nodes, the answer is exactly the $k$-th Fibonacci number.
> 2 votes

---
Tags: algorithms, graphs, trees
---


# Question
Title: If $L\in\mathrm{NP}$ is $\mathrm{coNP}$-complete, then $\mathrm{coNP}=\mathrm{NP}$
The problem in the title is to be proven, and while proving $\mathrm{coNP}\subset\mathrm{NP}$ is rather clear given the assumptions (see below), I fail to see a way to prove $\mathrm{NP}\subset\mathrm{coNP}$.

My main idea is to prove that $L$ is also $\mathrm{NP}$-complete (or rather $\mathrm{NP}$-hard, as it is in $\mathrm{NP}$), but I don't really see a possibility to prove this, as it is not sufficient that a subset of $\mathrm{NP}$ is reducible to $L$; thus I would be very thankful for some idea for a proof.

***Addendum 1:***

I am aware of if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$, but in this source only the obvious implication is proven.

***Addendum 2*** \- My proof of the first subset-relation:

All languages $K\in\mathrm{coNP}$ are reducible to the $\mathrm{coNP}$-complete language $L$, thus if $L\in\mathrm{NP}$ every $K$ is reducible to a language in $\mathrm{NP}$ and the implication $K\in\mathrm{coNP}\Rightarrow K\in\mathrm{NP}$, and thus $\mathrm{coNP}\subset\mathrm{NP}$, holds.

# Answer
> 1 votes
$\newcommand{\co}{\mathsf{co}\text{-}}$

Let $A\subseteq \Sigma^\*$ be some class of languages. Saying $\co{A}\subseteq A$ means that $A$ is closed under complement, and this is equivalent to $\co{A}=A$.

To show the other direction, $A\subseteq \co{A}$, let $L\in A$ be some language in the class $A$. $\overline{L}\in \co{A}$, and since we know $\co{A}\subseteq A$, we have $\overline{L}\in A$, which means $L\in \co{A}$.

---
Tags: time-complexity, proof-techniques, np
---


# Question
Title: Intuitive explanation of neutral / normal form in lambda calculus
It is possible to distinguish Normal terms which don't contain beta redex as a sub-expression, from others like so

```
data WithBound a = Var | Other a

data Normal a
  = Neutral (Neutral a)
  | Abstract (Normal (WithBound a))

data Neutral a
  = Variable a
  | Apply (Neutral a) (Normal a)

```

Is there any intuitive explanation as to why this property would hold ? It might be entirely self-evident somehow after you look at it long enough but it does not prompt straight out to me as of now.

# Answer
> 8 votes
I can reassure you that this property is not immediately self-evident. In trying to describe/enumerate the set of normal forms, the main observation required is the following:

* Abstraction preserves normal forms: if $t$ is normal, than so is $\lambda x.t$.
* Application does **not** preserve normal forms: if $t$ and $u$ are normal, $t\ u$ may contain a redex!

We want to characterize the normal forms **for which we can not create redexes when performing applications**. Obviously, this occurs iff $t$ is a $\lambda$-abstraction. In particular, we can take $u$ to be anything we want, so long as it is in normal form.

For $t$, we need either a variable or an application, itself already in normal form. This allows a convenient recursive definition for $t$, which we will call *neutral*: $$t=x$$ or $$t=t\_1\ t\_2$$ with $t\_2$ any normal form, and $t\_1\ t\_2$ also in normal form, i.e. $t\_1$ also a neutral term.

But this is exactly your definition of `Neutral`!

One can carry out this process further to characterize exactly the normalizing (resp. strongly normalizing) terms, if we furthermore allow *weak head expansions*.

---
Tags: lambda-calculus, term-rewriting
---


# Question
Title: Do computers actually use carry-lookahead adders?
There are plenty of details about carry lookahead adders such as Kogge-Stone, Lander-Fischer, etc. in college CS courses. They are described as "common in the industry". However, I can't find any evidence (aside from maybe the Manchester carry chain) from recent times that they are actually used anywhere specifically. A Google search only returns pages of journals and academic research. At most, hypothetical implementations are given.

My question is, are there any specific places/implementations carry-lookahead adders are used? Or are they irrelevant to the real world?

# Answer
This is a straightforward question with a very complex answer.

First off, some background.

Real-world VLSI design is an extremely technical field which features a constantly-changing balance of tradeoffs. The time that a circuit takes to calculate an answer is rarely the only important factor. There's also power draw and physical area, plus a bunch of factors which reveal that the circuits you're designing are actually analogue (e.g. wire resistance, parasitic capacitance). All of these are important in a real circuit and may impact which design is chosen.

Secondly, you have to consider the entire life-cycle of a project. An adder which is appropriate for a VLSI realisation may not be appropriate for an FPGA realisation. If the design is going to go through a phase being tested on an FPGA... you get the picture.

Thirdly, not every adder is made equal. On a typical CPU, there are lots of adders hanging around which do different tasks; there are probably several integer ALUs, a floating point mantissa adder, an adder which does address calculation, an adder which calculates branch targets, and so on. That's not counting the carry-save adders that you find in modern multiplication units. Each has its own peculiarities and constraints.

Branch target calculation, for example, typically involves adding a small constant to a full word, which suggests a different adder design from one which adds two full words together. Similarly, floating point addition requires a post-addition rounding step which might take less than a cycle, so there's no reason why you couldn't steal the rest of the cycle to finish off the addition.

Lastly, and perhaps most importantly, the big players (e.g. Intel, AMD, NVIDIA) are fairly tight-lipped about low-level implementation details for obvious reasons, unless they think they can get a paper and/or patent out of it. Even then, you often can't be sure what they actually did without reverse-engineering.

Having said that, there are a few things we know.

The key thing you need to realise is that carry-lookahead methods are building blocks, and not necessarily methods in themselves. An analogy might be in order here.

If you think about algorithms classes, you probably learned a bunch of sorting algorithms such as quick sort, merge sort, insertion sort, and so on. In the real world, if sorting is a performance bottleneck, any decent engineer would think of these as primitive building blocks from which a "real" sort can be constructed.

The sort algorithm from the GNU C++ standard library, for example, uses quick sort, using insertion sort when the intervals get small enough. However, if after a few passes it looks like the quick sort partitioning has hit pathological behaviour, it falls back to heap sort. That's three different sort algorithms to make one industrial-strength sort.

The same is true of adder circuits. It is known, for example, that the Pentium 4 integer unit used a Han-Carlson adder, which is a mix of Kogge-Stone and Brent-Kung. (Han-Carlson is especially interesting, because it's a "sweet spot" in the tradeoff between propagation delay and die area which also being quite power-efficient.) It often pays to use a mix of several methods.

"Pure" carry-lookahead adders are still very much the norm in synthesised circuits (e.g. if you feed a Verilog "+" operator to Cadence or Synopsys), when it comes to hand design, modern high-end CPUs with their superscalar out-of-order execution engines seem to be moving towards a slightly different design for their integer units.

Speculative adders are circuits which have extremely low propagation delay, but only work correctly some of the time (95% of the time is typical), and it's possible to tell with very little logic whether the speculative adder returns the correct result or not. So the idea is to do a speculative addition and half of a carry-lookahead addition in parallel, in one cycle. If the speculative adder returned the correct answer, the instruction is done. Otherwise, stall the pipeline and do the other half of the accurate addition.

Because you know that the slow path will take two cycles, the designers could use a more space and power-efficient method even if it would be too slow for general use.
> 18 votes

# Answer
Yes, many computers use carry-lookahead adders. I've reverse-engineered some old microprocessors and I can give some examples.

The ALU on the Intel 8008 (their first 8-bit processor) included a large carry-lookahead circuit implemented with dynamic logic. This circuit took up about as much die space as the ALU itself. Carry lookahead is shown on the 8008 datasheet, figure 3. I haven't seen any other 1970s processors with carry-lookahead for the ALU, so the 8008 is a bit unusual in this regard.

The 6502 uses primitive carry-lookahead for the program counter (PC) incrementer. It detects if there will be a carry from the lower byte of the PC and uses this to increment the upper byte. This reduces ripple carry from potentially 16 bits to 8 bits. The 6502's ALU uses ripple carry, although the carry logic is inverted for alternating bits, which cuts an inverter out of the path and makes it slightly faster.

The Z-80 has a 16-bit incrementer/decrementer used for PC updates, inc/dec instructions, and a loop counter. It uses a carry-skip structure so carries are computed for groups of two bits. In addition, it uses some carry-lookahead to generate the carry from bits 0-7, 7-11, and 12-14. Other carries are computed with ripple carry (details). The Z-80's ALU, surprisingly, is 4 bits, so each 8-bit operation does two passes through the ALU.

The 8085, on the other hand, uses ripple carry for its 16-bit incrementer/decrementer. But like the 6502, it gets a bit of speedup by inverting the carry logic in alternating bits.

The ARM-1 has a 32-bit ALU with no carry-lookahead, just ripple carry. It also uses the trick of inverting the carry in alternating bits.

In the minicomputer world, many processors were built from the well-known 74181 4-bit ALU chip, which had internal carry lookahead. Examples include the Data General Nova, the Xerox Alto, the VAX-11/780 and the TI-990. (See longer Wikipedia list.) Some of these used ripple carry between each 4-bit chip and some uses the 74182 carry lookahead chip for full lookahead.

To summarize, different microprocessors use a variety of carry techniques depending on their performance goals and what operations are on the critical path. The ALU can use full carry-lookahead (like the 8008) or can even be half-sized (like the Z-80). The incrementer can be a performance problem because it is typically 16 bits in an 8-bit processor, resulting in twice the ripple delay. The incrementer can have ripple carry (8085), one carry lookahead (6502) or several carry lookahead stages (Z-80).
> 7 votes

---
Tags: computer-architecture
---


# Question
Title: How did early computers handle variable word length?
So quoting from the book: A History of Modern Computing (History of Computing)

> The introduction of reliable core memory made it practical to fetch data in sets of bits, rather than one bit at a time. That meant a block size or word length, of from 30 to 50 bits.
>
> Business-oriented computers could use shorter word length or a variable word length.
>
> IBM 1401 used an extra bit appended to each coded character to indicate whether or not it was the last one of a word.
>
> The 702 used a special character that signified that the end was reached.

I am not sure if I understand how variable word length works for any of these computers mentioned above.

For the case of IBM1401, what is meant by a 'coded character' and how can a single bit give the information that the end of a word is reached? (Assuming the computer runs on binary..?)

And for 702, what is meant by a 'special character'?

# Answer
> 3 votes
I've recently programmed an IBM 1401, so I can explain how its variable length words work.

For the motivation, remember that the IBM 1401 was a low-cost ($2500/month) 1960's computer for business applications on punched cards, for example payroll processing or inventory processing. The 1401 typically reads a file of punched cards, where each card holds fixed-length fields for one data record. The computer does some processing on each card, and prints out a report on the line printer, with fixed-length fields. Thus, it is convenient if the computer can easily manipulate fields of characters or numbers where each field has an arbitrary but fixed length.

The 1401's variable-width words are how it supports fixed-length fields. The programmer initializes the field lengths at the beginning of the program. Then a single "move" instruction will move a string field, regardless of how long it is. You don't need to loop over each character; the processor does that automatically. And you can add two numbers with a single "add" instruction, whether a 2-digit number or a 40-digit number. This is efficient, saves very expensive program memory, and is a good match for card-based applications.

Now, for the 1401's implementation of variable-length words (or fields). The IBM 1401 uses 6-bit characters (coded in BCDIC, precursor to EBCDIC), holding a text character or a decimal digit. (Note that the 1401 did decimal arithmetic, which worked well for business applications.) Each location in core memory has an additional "word mark" bit, which you can think of as a "metadata" bit. The programmer sets the word mark bit on the leftmost (high-order) character in a field. An instruction will typically process an entire field from right to left, until it hits a word mark, and then stops.

The important thing is that word marks aren't part of the 6-bit character. When you read a card, move a field, or so forth, the word marks are unchanged. Thus, the programmer can initialize the word marks once (with special word mark instructions), and then they stay put while you process the data.

Word marks are also used in the 1401 for variable-length instructions (1 to 7 characters), with a word mark after each instruction. One puzzle is that word marks aren't stored on the punched card, so how can you read in a program from cards? The solution is that when you load a program, you're actually loading and running a loader program that inserts the word marks as necessary for the program you actually want to run.

There is no limit on the size of a 1401 word, other than memory size. As a test, I created two 1000-digit numbers and multiplied them with a single "multiply" instruction. The computer churned away for literally a minute on this one instruction before generating the result.

The 1401 Reference Manual is online and provides more information, in case you didn't get enough here.

# Answer
> 1 votes
A "coded character" is merely a character representing code (not data).

The concept of a bit marking the end of a word is still in use today, in the UTF-8 encoding. Simply said, if the bit is set, it marks the end of a word; if not the next character also belongs to the word.

A special "end of word" character is what we use in English, where the end of a word is marked by a space character.

---
Tags: computer-architecture, history
---


# Question
Title: Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$
Let me define first Halting problem $(\mathsf{HP\text{}})$.

**Given** : $(M , x)$, $M$ is a turing machine and $x$ is a input binary string to turing machine $M$.

**Decide** : Does $M$ halt on string $x$?

I tried to reduce $\mathsf{SAT\text{}}$ instance to $\mathsf{HP\text{}}$ in polynomial time. Let $\phi$ be a instance of $\mathsf{SAT\text{}}$ and define a map $\mathsf{T\text{}} \colon \mathbb \phi \to\mathbb M$. If $\phi$ is satisfiable (means true) then turing machine $M$ will halt on string $x$ and if $\phi$ is not satisfiable (means false) then turing machine $M$ will not halt on string $x$.

I don't know whether the map $\mathsf{T\text{}}$ right or wrong. So my question is how to define a map and to compute this map in polynomial time?

# Answer
Given a SAT formula $\varphi$, construct a Turing machine which iterates over all truth assignments for $\varphi$, and so determines if $\varphi$ is satisfiable or not. If it is, it halts. If it isn't, it doesn't halt (gets into an infinite loop).

As is apparent, in the same way we can show that the halting problem is coNP-hard (by reversing the decision rule at the end). Indeed, in the very same way we can show that the halting problem is hard for many other classes – in fact, for all classes defined by time or space constraints (deterministic, non-deterministic or randomized).

NP is the "length- and time-bounded" version of the halting problem, or rather, of $\Sigma\_1$. The class $\Sigma\_1$ consists of all predicates $P$ such that $$ P(x) \leftrightarrow \exists y \\, \Pi(x,y), $$ where $\Pi$ is a computable predicate. NP is defined in a very similar way, by adding two restrictions:

1. $y$ has to be polynomially bounded (in $x$).
2. $\Pi$ has to be computable in polynomial time.

If you like this sort of thing, there is an entire field dedicated to this point of view, called Bounded Arithmetic.
> 4 votes

---
Tags: complexity-theory, computability, turing-machines, reductions, np-hard
---


# Question
Title: Why do Computers use Hex Number System at assembly language?
Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? Why it looked so beneficial to them?

# Answer
> 6 votes
Computers don't use the hexadecimal number system for assembly language. Assembly language, or rather machine code, uses base 256 (typically): instructions are encoded in units of *bytes*. When displaying machine code, it is customary to use octal or hexadecimal. The reason is that in many cases, the byte is further subdivided into bitstrings, and identifying these bitstrings is easier when using a base which is a power of 2. Hexdecimal is particularly compact since each byte can be encoded using exactly two hexadecimal digits.

# Answer
> 3 votes
The simplest reason is that, the computer does not see this, it only sees the binary. This really just aids the programer. Binary is a mess to look at, octal does not usually work since an octal number is three bits and historically computers have been using 16,32,64 bit instruction sets, none of which are divisible by 3, leaving hex as the best choice.

# Answer
> 1 votes
Note that using octal vs hexadecimal is mostly a matter of programming and documentation, rather than the computer itself. (Apart from, say, a front panel display with hex digits.)

Octal was popular with programmers until about the 1970s, when hexadecimal pretty much took over. Octal has the advantages of using normal digits (no letters) and being simpler to work with (e.g. addition), although it's slightly less dense than hexadecimal.

The huge advantage of hexadecimal is when you're working with a 16-bit (or larger) machine, since the bytes break into hexadecimal cleanly. In hexadecimal, ASCII "A" is 41 and "B" is 42, so a word with "AB" is 4142. Reversing the bytes gives 4241. Octal, on the other hand, is a huge pain. "A" is 101 and "B" is 102, but word "AB" is not 101102 but inconveniently 40502 and "BA" is 41101 - it's hard to pull the bytes out of the word. Thus, hexadecimal rapidly became popular as 16- and 32-bit machines became common. (I'm working with a 16-bit Xerox Alto (1973) that used octal for everything, and it's a big pain.)

One interesting historical note is that Intel's processors from the 8008 through x86 have an instruction set designed around octal, but it's entirely documented in hexadecimal. If you look at opcodes in octal, the instruction structure becomes clearly visible (details).

Another historical note is Unix and C show strong octal influence, for example the *od* octal dump command, the use of octal in the *tr* command, C octal escape sequences, octal file permissions, etc.

# Answer
> -2 votes
Hexidecimal (TM copyright IBM) is a notation. It incorporates a familiar numeric system, the Binary Coded Decimal (BCD) of 10 symbols 0-9 in a 4 bit representation system, the remaining 6 values of the 16 possible combinations are represented by a,b,c,d,e,f or A,B,C,D,E,f respectively. In this fashion a 'nibble' of 4 bits can conviently represent all the possible values in a simple notation.

---
Tags: time-complexity, computer-architecture, mathematical-analysis, memory-hardware, computer-algebra
---


# Question
Title: Running time for Testing Polygonal Neighbours for Intersection or Inclusion
I was reading this paper by Shamos, M.I, on "Geometric Intersection Problems" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.9983&rep=rep1&type=pdf) , and was trying to understand it's Theorem 6, which says " Whether any two of N convex k-gons intersect can be determined in O(N(k+log N log k)) time."

I was stucked on the point 3 (Inclusion and intersection tests), in which the author says that " When a polygon is inserted, it ,it must be tested against its immediate neighbors for inclusion or intersection. **As we have seen before, each such test can be done in O(k) time.** "

I do not understand how is that possible. Theorem 5 of the same paper states that determining an intersection of two k-gons takes O(k log k) time.

If the author is talking about something else, then I didn't get that.
Any help appreciated.
Thanks.
Moon

# Answer
In the paper you reference, Theorem 5 is a claim about simple polygons, where Theorem 6 deals with *convex* polygons, which are a special kind of simple polygons.

The 'As we have seen before, ...' refers to this line: 'As we have seen before, each such test can be done in $O(k)$ time.$^8$', where $8$ references another paper.

However, even though I do not know why you are reading this paper, I'd advise against it. This paper is pretty old and the main result (the $n\log n$ segment intersection algorithm) has been both improved upon and better explained by other sources. If you did not have an introductory course on computational geometry or something similar, I advise you to look at a computational geometry /algorithmic geometry textbook or lecture notes first.
> 2 votes

---
Tags: time-complexity, asymptotics, computational-geometry, polygons
---


# Question
Title: How generate n equidistant points in a n-1 dimensional space
As said, i want to build a program to generate n equidistant points in an euclidian space. From what i know

* 1d : all couple of points
* 2d : all equilateral triangles
* 3d : all equilateral tetrahedra
* up to 3d : i suppose it's called an equilateral hypertriangle

So my problem is as follow, in a n-1 euclidian space, giving a defined point build the n-1 other in order to have an equilateral hypertriangle with a distant d between each points.

I suppose that we can start as follow with for example a 3d space.

* p1 = (x1,y1,z1) fixed
* p2 = (x2,y2,z2)
* p3 = (x3,y3,z3)
* p4 = (x4,y4,z4)
* d

We start to fix p2 knowing d and p1

* $d²=(x\_1-x\_2)^2 + (y\_1-y\_2)^2 + (z\_1-z\_2)^2$

We have 3 variables x2,y2,z2. We can fix randomly two of them and determine the third without problem.

Then for the second point we have now 2 equations to defined it :

* $d²=(x\_1-x\_3)^2 + (y\_1-y\_3)^2 + (z\_1-z\_3)^2$
* $d²=(x\_2-x\_3)^2 + (y\_2-y\_3)^2 + (z\_2-z\_3)^2$

As previous, i presume that we can fix 2 variables to determine the third.

For the last point we now have 3 equations which defined it.

So for a n-1 dimensional space we have n-1 equation to defined the last point.

I don't know how to solve this kind of system composed of quadratic equation with one variable and if the process which consist to fix n-1 dimension to determine the last one lead to an equidistant hypertriangle. Moreover it exist maybe others methods with an smaller complexity and easier to implement.

I hope i was clear enough and i thank you for your help.

# Answer
I assume we are working in $\mathbb{R}^n$.

First of all, observe that one regular $n-$simplex effectively determines all the others. In fact, if $S\_1, S\_2$ are two sets of points in $\mathbb{R}^n$ that satisfy the regularity condition, then they can be obtained from each other by composing at most an isometry and an homothetic transformation of the affine space (the converse is also true).

Therefore, it is sufficient to construct an unitary $n-$simplex centered in the origin. We visualize each vertex of the simplex $v\_1, v\_2, \dots v\_{n+1}$ as an element of the real $n$-dimensional vector space.

Consider two vertices $v\_1, v\_2$ of the simplex, let $O$ be the origin and $\pi$ be the plane passing through $v\_1, v\_2, O$. The angle $\vartheta =\angle v\_1 O v\_2$ is exactly $\arccos (-1/n)$. To prove that, we observe that:

$$ 0 = \left \\| \sum\_{i} v\_i \right \\|^2 = (n+1) + 2 \cos\vartheta \binom{n+1}{2} $$

We deduce that the following hold:

* $\forall i \quad \\| v\_i \\| = 1$
* $\forall i \neq j \quad \left \langle v\_i, v\_j\right \rangle = -1/n$

We may assume without loss of generality that $v\_1, v\_2$ lie on the same line, that $v\_3$ lies on the same plane as the others and so on (in general, that for each $k$, $v\_1, v\_2, \dots v\_k$ lie on the same subspace of $\mathbb{R}^n$ with dimension $k$). Therefore, we may write the vectors by coordinates as follows:

$$ \begin{array}{r c l} \begin{array}{r} v\_1 \\ v\_2 \\ \cdots \\ v\_{n+1} \end{array} & \begin{array}{r} = \\ = \\ \\ = \end{array} & \begin{array}{c c c c c c} (x\_{1,1} & 0 & 0 & 0 & \dots & 0)^T \\ (x\_{2,1} & x\_{2,2} & 0 & 0 & \dots & 0)^T \\ \\ (x\_{n+1, 1} & x\_{n+1, 2} & x\_{n+1, 3} & x\_{n+1, 4} & \dots & x\_{n+1, n+1})^T \\ \end{array} \end{array} $$

The first equation uniquely determines $x\_{1,1}$ and the second all the $x\_{m,1}$. Now we use again the first to compute $x\_{2,2}$ and with the second we determine all the remaining $x\_{2, m}$.

Continuing the procedure in a similar fashion computes the coordinate values of all the vertices.
> 9 votes

# Answer
You can make n-1 equidistant points by using the unit vectors along each of the axis aka. (1, 0, 0, 0, ..., 0); (0, 1, 0, 0, ..., 0); (0, 0, 1, 0, ..., 0); etc., The last nth point will be along the 1, 1, 1, ..., 1 direction.

Then you can use a scale to set the distance between the points from $ \sqrt 2$ to $d$ and a translate to move one of the points to the fixed point
> 6 votes

---
Tags: computational-geometry
---


# Question
Title: Why is the Mean Time To Failure of multiple disks calculated via division and not multiplication?
I am reading about disk redudancy.
I read the following:

> Suppose that the mean time to failure of a disk is 100,000 hours. Then the mean time to failure of some disk in an array of 100 disks will be 100,000/100 = 1000 hours

I don't understand this. Why isn't it 100,000^100 instead?
Then the same textbook says in the next paragraph concerning 2 mirrored disks:

> If the mean time to failure of a single disk is 100,000 hours and the mean time to repair is 10 hours then the mean time to data loss is (100,000^2)/2\*100

Now here it multiplies for the 2 disks but before the MTTF was divided.

Can anyone please help me figure out how we calculate this.
In case it matters the text book is Database Concepts from Silberschatz 4th edition paragraph 11.3.1 (Improvement of reliability via redundancy) page 403

# Answer
Think of it this way. A single disk fails on average after $100,000$ hours. Now you have $100$ disks. How long before one of them fails? It will almost certainly take much less than $100,000$ hours for the *first* to fail, and much more than $100,000$ hours for the *last* to fail. (This of course depends on the distribution of failures, which is assumed to be exponential here.)

Here is another example: if you keep throwing one die, it will show $6$ after an average of $6$ throws. Now suppose that you throw two dice. How long do you expect to wait until some $6$ shows up? Certainly less than $6$ throws. (In fact, $36/11 \approx 3.27$ throws on average.)

In the second example, you need both disks to fail in order for data loss to occur. Not only this, but you also want both failure "events" to be within $10$ hours of each, since otherwise the system will recover after repairing the faulty disk. Hopefully the book explains the calculation somewhere, if not, the book is useless and you should tell your instructor to use a different one (perhaps with less pictures but more content, and not $n$th edition, prepared to finance the publisher's new yacht).
> 8 votes

# Answer
I think this problem is interesting. So I want to provide a explanation, and I think it will help me understand it better.

The die example Yuval provides is interesting. Because the distribution is known and very simple. Let P(k) be the probability of 6 shown in the kth try but not before the kth try.

$P(k=1) = \frac{1}{6}$;

$P(k=2) = (1-\frac{1}{6}) * \frac{1}{6} $;

$P(k) = (1-\frac{1}{6})^{(k-1)} * \frac{1}{6} $;

So the expected number of try that we can see 6 is

$\Sigma\_{k=1}^{k=\infty} kP(k)=k(1-\frac{1}{6})^{(k-1)}\*\frac{1}{6} = 6.$

If we throw two dies at the same time and let P(k) be the probability of 6 shown in the kth try but not before the kth try. Then:

$P(k=1) = 1 - (1-\frac{1}{6})^2 = 1 - \frac{25}{36} = \frac{11}{36}$

$P(k=2) = (1 - \frac{1}{6})^2 * (1 - (1 - \frac{1}{6})^2) = \frac{25}{36}\*\frac{11}{36}$

$P(k) = (\frac{25}{36})^{k-1}\*\frac{11}{36}$

so expected number of try that we can see 6 is:

$\Sigma\_{k=1}^{k=\infty}kP(k) = \frac{36}{11}$

The sum equation could derived from this formula.

$\Sigma\_{k=1}^{k=\infty} kx^{k-1} = \frac{1}{(1-x)^2}\ for\ x\>0\ and\ x \< 1.$

If we doesn't know the distribution of the events, we could roughly estimate the value. For the die problem, we know that every 6 tries will produce one 6. So if we throw 2 at the same time. Every 6 tries will produce two 6. So the rate of 6 happening is 2 / 6 = 1/ 3. 1/rate = 3. So roughly every 3 tries produce a 6. 3 is very close to $\frac{36}{11}$.

In the case of 100 drives. The mean time to failure of a disk is 100,000 hours, if we assume that the drive will definitely fail before 100,000 hours. So within 100,000 hours, we would have 100 failed drives. In average every $\frac{100,000}{100}$ hours we will have a failed drive, so we can assume the first failed drive will appear before $\frac{100,000}{100}$ hours.

For the two disk mirrored case, we assume A disk and B disk. In order to lose data, A and B need to be failed at the same time. if A is already failed and within 100,000 hours B disk will fail, then data will be lost. The other case is B is already failed and within 100,000 hours A will fail and then data will be lost.

For the first case, A disk is failed for 100 hours every 100,000 hours. so in order to make B to fail, it will need 100,000^2 / 100 hours. Because the other case, the time is reduced to 100,000^2/(2\*100)
> 2 votes

---
Tags: operating-systems, computer-architecture, database-theory, reliability
---


# Question
Title: What is the smallest $n$ such that $BB(n) > $Graham's number?
BB represents the busy beaver function here. Do we even have any idea of what order of magnitude $n$ would have? Is it possibly around 10, or more like 1000?

# Answer
> 3 votes
If I recall correctly it started with $n = 64$, then $n = 25$ shortly after that with $n=23$, $n = 22$ and now $n = 19$.

---
Tags: turing-machines, busy-beaver
---


# Question
Title: Partial recursive function with no total recursive extension
We define a partial recursive function $f:\\{0,1\\}^\* \longrightarrow \\{0,1\\}^\*$ to be *semi-good* if we can define a total recursive function $g:\\{0,1\\}^\* \longrightarrow \\{0,1\\}^\*$ from $f$, such for all $x \in \\{0,1\\}^\*$ either $f(x) = g(x)$ or $f(x)\uparrow$.

Now I want to prove that there exists a partial recursive function that is not semi-good.

I must make a partial recursive function that is not semi-good for example $f\_1$ ,but my problem is that I must show that I can not define any total recursive function $g:\\{0,1\\}^\* \longrightarrow \\{0,1\\}^\*$ from $f\_1$.

I don't have any idea how can I show this. Can I use the fact that a specific language like $L$ is not recursive so its characteristic function $\mathcal{X}\_L$ is not total recursive function? How can I make the partial function from this fact?

# Answer
Take the function that interprets its input as the description of a Turing machine, and outputs the number of steps it takes the machine to halt, if it halts, and is undefined otherwise. This function is clearly partially computable, but it has no computable extension, since you could use any such extension to solve the halting problem (why?).

Exercise for the reader: convert this construction to a *Boolean* function.
> 8 votes

---
Tags: computability, semi-decidability
---


# Question
Title: Is this variant of set cover NP-complete?
Let's say we have a universe $U$ of $n$ elements and a collection $S$ of $m$ subsets of $U$, i.e., $S=\\{S\_1,\ldots,S\_m\\}$, and a positive integer $k$. If I ask "is there a set cover of $U$ of size $k$ or less", then this is NP-complete.

Now suppose that I add the following:

1. $|S\_1| \gt |S\_2| \gt \ldots \gt |S\_m|$.

Is this still NP-complete?

I guess that, given 1., we know that the sets $S\_i$ are all distinct and then the only cover for $U$ is $S$ but I am not sure about this.

# Answer
> 3 votes
As quicksort comments, you can convert any set cover instance to your special case by adding dummy elements. Take a large enough pool of dummy elements, and put all of it into a new set $S\_1$. Then add subsets of $S\_1$ to the other sets to satisfy your cardinality condition, taking care to leave some of them out. Every solution has to take $S\_1$, and otherwise it just has to be a solution to the original problem.

This is of course not a formal reduction - this is left to the reader.

---
Tags: np-complete, set-cover
---


# Question
Title: Context-sensitive grammars without permutation rules
Permutation rules are called those which are of the form $AB\Rightarrow^\*BA$1. It is also proven that permutation rules expand context-free grammars and allow them produce non-context-free languages.

My question is: are any examples of **context-sensitive grammars**, which doesn't contain any permutation rules but still able to produce **non-context-free languages**?

1) Book, R.V. International Journal of Computer and Information Sciences (1973) 2: 129. doi:10.1007/BF00976059. More generally permutation rules have form of $Y\_1 \dots Y\_m\rightarrow Y\_{\pi\_1}\dots Y\_{\pi\_m}$, where $\pi$ is some permutation of $\\{1\dots m\\}$.

# Answer
> 1 votes
You have the Koruda normal form in mind. It is indeed often useful, in particular in simulation LBAs.

However, many definitions of CSGs (including Chomsky's) are different; they require rules to have the form

$\qquad \alpha A \beta \to \alpha \gamma \beta$.

You can see how this precludes "permutation rules".

Obtain a concrete grammar by applying the simulation you find in a proof that KNF is equivalent to the classical definition.

# Answer
> 0 votes
Perhaps this might not directly answer your question, but I know of a very innocent grammatical concept that moves context-free grammars outside the context-free language area.

Start with a context-free grammar, and apply productions in the usual way, **except** that always two adjacent non-terminals are rewritten. This mode of rewriting grammars was proposed by Kleijn and Rozenberg. The proof that such languages are outside context-free was given in "Concerning two-adjacent context-free languages" by Dahlhaus and Gaifman (1985, Open Archive at Elsevier Theoretical Computer Science). Their paper is a little technical and studies the connection to E0L-languages (that have parallel derivation steps), but I found a concrete example.

They propose the following grammar for $\\{b^{4k}\mid k\ge 1\\}$ when used in 2-adjacent mode (Lemma 2.3).

$S\to bABb$, $S\to bb$, $A\to bA$, $B\to bB$, $A\to b$, $B\to b$

So, note that as context-sensitive (or better non-contracting/monotonic grammar) we would translate this as all pairs of productions, like $SA \to bABb\\,bA $, but strictly speaking these rules are not permutation rules.

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: Is the complement of a Max Prefix Sum a Min Suffix Sum?
Given an array `A` of `n` real numbers, are the maximum prefix sum and minimum suffix sum (and vice-versa) of A complements?

I.e. Given `A[1..n]` and its maximum prefix subarray `P[1..i]`, is its minimum suffix subarray `S[j..n]` where `i+1 = j`?

Or stated another way, is `sum(A) = maxPrefixSum(A) + minSuffixSum(A)` true?

*For an array of only negative numbers, let's assume that `P` is empty and `maxPrefixSum(A) = 0`. Similar logic applies in the opposite case.*

# Answer
It depends on whether the maximum prefix and minimum suffix are unique. Consider for example the array $0$ — you can easily find a counterexample to your claim. Suppose therefore that $\sum\_{i \leq j \leq k} A\[j\] \neq 0$ for all $i \leq k$. Let now $j$ maximize $\sum\_{i=1}^j A\[i\]$, and let $k$ minimize $\sum\_{i=k+1}^n A\[i\]$. We want to show that $j=k$. Otherwise, there are two cases:

1. If $j \< k$, let $S = \sum\_{i=j}^{k-1} A\[i\]$. By assumption $S \neq 0$. If $S \> 0$ then $\sum\_{i=1}^{k-1} A\[i\] \> \sum\_{i=1}^j A\[i\]$, and otherwise $\sum\_{i=j+1}^n A\[i\] \< \sum\_{i=k+1}^n A\[i\]$.
2. If $j \> k$, let $S = \sum\_{i=k}^{j-1} A\[i\]$. By assumption $S \neq 0$. If $S \< 0$ then $\sum\_{i=1}^{k-1} A\[i\] \> \sum\_{i=1}^j A\[i\]$, and otherwise $\sum\_{i=j+1}^n A\[i\] \< \sum\_{i=k+1}^n A\[i\]$.
> 1 votes

---
Tags: arrays, maximum-subarray
---


# Question
Title: Can every r.e. set be obtained by repeated function application?
Is below statement true?

$\forall L \in r.e. \\,\\, \\, \exists f:\\{0,1\\}^\* \longrightarrow \\{0,1\\}^\* \\, , \exists x\in \\{0,1\\}^\* \\; s.t \\, \\, L = \\{x,f(x),f(f(x)),..\\} $ .

My guess is no and I tried to prove this with cantor diagonalization.If we suppose that $L\_i$ has this property so $L\_i = \\{x\_i,f\_i(x\_i),f\_i(f\_i(x\_i)),...\\}$,now I want to make $L$ that doesn't have above property $L = \\{x\_k \in \\{0,1\\}^\* | \nexists i \\; x\_k \in L\_i\\}$,How can I prove that it is in $r.e$?

# Answer
> 0 votes
Since $L$ is r.e., there is a computable program $\varphi$ that enumerates it, say in the order $$ x\_1,x\_2,x\_3,x\_4,\ldots $$ Suppose I give you $x\_n$, can you find $x\_{n+1}$ using $\varphi$? Can you use this to solve your question?

---
Tags: computability
---


# Question
Title: How do I define a language from a grammar?
Given an alphabet $ Λ = \\{a, b, c\\}$, I have the following grammar:

$$ S -\> aSb | aAb $$ $$ A -\> aaA | aBb $$ $$ B -\> Bbb | c $$

Which method should I use to write the definition of the language?

# Answer
This one is very simple because it has a very downward flow to it. For example, $S$ has non-terminals $S$ and $A$, and once you go to $A$, you can never get back to $S$. So we use this fact to just work through incrementally.

---

Our language started with $a^nXb^n$ for S where X is some other language, then we got to A and get $a^n(aa)^mXb^n$, then finally $a^n(aa)^{m+1}c(bb)^sb^{n+1}=a^{n+2m+1}cb^{n+2s+1}$ where $n,m,s \in \mathbb{N} \setminus{0}$
> 0 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: How can I prove that a cryptography algorithm is a pseudo-random number generator?
I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not?

Is there some principles I have to be based on while proving prgs?

# Answer
We don't know how to prove that a cryptographic PRNG exists. There are some candidate constructions, but they have not been proved to work. There are some results of the form "if X exists then so does a cryptographic PRNG", where X is some other cryptographic primitive, and the PRNG can be constructed explicitly from X. However, none of these other cryptographic primitives are known to exist. A particularly intriguing open question is to construct such a primitive which works merely under the assumption that P differs from NP.

On the other hand, proving that a generator is not a PRNG is much easier. You just need to give a distinguisher which has a non-negligible advantage in comparing the output of the generator to truly random output (as in the definition of a cryptographic PRNG).
> 4 votes

# Answer
You look for published tests that true random numbers pass, and check whether your generator passes those tests.

For example, if your generator produces real numbers in \[0, 1), and you generate 1,000,000 numbers, then for every interval \[0, 0.01), \[0.01, 0.02) etc. there should be about 10,000 numbers in that interval. But not exactly, someone good at statistics will be able to tell you how far random numbers would deviate from "exactly 10,000 in each interval". So you would take the numbers produced by your generator and check them against that statistics.

That's a simple test. A good pseudo-random number generator would have consecutive numbers generated be independent of each other. Take three consecutive random numbers. They will be arranged in one of six possible numerical orders (a \< b \< c, a \< c \< b etc. ). Generate a 1,000,000 random numbers, with 999,998 triples, so each numerical order should be present about 166,666 times (again with some reasonable deviation). Check your generator against that.

PS. Yuval Films mentioned "cryptographic PRNG"s. That's a whole different beast. Usually random number generators are used for example for simulations; say to simulate a million cars driving through Los Angeles and what happens if we change traffic lights. If you use a PRNG to draw lotto numbers for real, then you need a PRNG that cannot be predicted, even if an attacker knows exactly how the random number generator is implemented, and has gazillions of previous numbers produced by the generator - you wouldn't want anyone to be able to predict the next lottery numbers. Depending on the application, being a cryptographic PRNG is either absolutely essential or of no value whatsoever.
> 1 votes

---
Tags: algorithms, proof-techniques, correctness-proof, randomness, pseudo-random-generators
---


title: Finding Permutations with Exclusions

text:
# Question
Title: Finding Permutations with Exclusions
Recently, I was given a puzzle by a friend of mine, which has 6 pieces. Giddy to try it out, I took it apart without batting an eye to follow what I was removing or moving or sliding.

I've been struggling with this puzzle for over a year and a half now, and so thought I would write an algorithm that would list all the possible orientations or possibilities of pieces.

To make it more general, I numbered each piece 1 though 6. But, each piece can be rotated and placed, so I extended this to 1 through 12. So now each piece has two numbers, 1 and 12 is one piece, 2 and 11, 3 and 10, etc... Now to the root of my question:

Is it even possible to write a recursive algorithm to display all possible permutations of the 12 (6) pieces such that if piece 1 is used, 12 cannot, and so forth. Reason I ask is because if this were recursive, we wont know what we picked above (unless we keep running down in the recursion tree our last picked items) so that we can skip others.

Or, even better, would it be better to write a non recursive function?

Just as a note: **I am not looking for code, per se.** Pseudo code or concepts, or pointers would be so grateful and helpful.

Relevant References :

The Math behind *Combinations* with Restrictions

The Math behind Permutations with Restrictions

*Just as a note: Seeing as this may come up; I know the number to this solution is massive, but I've already written functions that tell me if a said permutation can even be played on the board (do certain blocks collide), if at least one block is moveable (we won't want gridlock), and if the placement of blocks conforms to the size of the puzzle enclosure. All this will, hopefully, eliminate quite a bunch, and let me try by hand the remaining games.*

# Answer
Generate all permutations of 1,...,6 (outer loop below), and all binary numbers of length 6 (inner loop below), then combine each permutation in the first set with each one from the second set:

```
for π in permutations(1,...,6):
    for x in 000000,...,111111:
        output C(π[1],x[1]),...,C(π[6],x[6])

```

where $C(n,0) = n$, $C(n,1) = 13 - n$.
> 2 votes

---
Tags: algorithms, recursion, permutations
---


title: Layered Structures

text:
# Question
Title: Layered Structures
I'm trying to check how general and valid protocol suite system ( layered structure ) are.

Does anyone know if radio communication ( broadcast ) via AM or FM , for instance can be viewed in the light of a layered structure ( for example, the OSI model ) as operating at least in one or more in layers ? Maybe could it be fair to say it operates only in the physical layer ?

Now suppose i have a really simple communication system between me and another guy and we implement communication digitally, with error-correcting ( but no signaling like in telephone and also not anything else apart from channel-coding and transmission through the channel) ...

Could it be fair to say that our communication system has only the physical layer ? Or would the communication system to require some protocol for the physical layer ? What would mean a protocol for a really simple physical layer ( like point-to-point one i described in the last example ) ?

I'm just trying to see if we can think about ANY communication system as operating in a layered structure ( like OSI ).

# Answer
> 2 votes
Pretty much any communication system can be modelled to some degree within the 7-layer model, though the choice of the layers in the OSI model was clearly aimed at computer networking.

Any system must have a physical layer because communication necessarily requires moving information through space and that is inherently physical. The physical layer deals with the problem of getting a chunk of data (a packet, a byte, whatever) from sender to receiver, not necessarily reliably, and all communication systems must have that.

Beyond the physical layer, things get a bit vague for things that aren't close analogues of computer networking. In your broadcast radio example, you could argue that the error-correcting codes used in digital radio are a basic datalink layer or you could argue that, since there's no mechanism for the receiver to request retransmission of lost packets or to acknowledge receipt, there is no reliable communication so there is no datalink. I'd probably go with the latter: the error correction is nice an' all that but, if a packet's bust, it's bust and you ain't never gonna see it again.

Your second example's a little unclear to me as you don't state whether you're doing anything to establish reliable communication, such as acknowledgments and retransmit requests to ensure that the data gets through. You certainly need some kind of physical layer protocol because you need to agree a meaning for the behaviour of the medium (e.g., this kind of modulation of the radio wave means 0 or this voltage on the wire means 1). If you build anything on top of how to code and decode packets, that's a higher layer in the model.

# Answer
> -1 votes
every communication system is build on layer architechture. beacause each comm. model need data link layer to identify local host and the upper layyer working as well

https://youtu.be/GOsfcYhqisY

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Minimum number of edges for $n$ vertex graph to be connected
I was reading about connectedness of a graph where I came across following points:

> * The $n$ vertex graph with the maximal number of edges that is still disconnected is $K\_{n-1}$ (complete graph with $n-1$ vertices) with an additional vertex, which has $\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$ edges.
> * Adding any additional edge must connect the graph. So the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$.

I am ok with the first point but not with the second point. The minimum number of edges for $n$ vertex graph to be connected should be $n-1$. Then how does that second point makes sense? How does the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$? Was the text trying to say something else? Is $\frac{(n-1)(n-2)}{2}+1$ number characterizes/pertains to some other condition on the graph?

# Answer
Likely they mean that if a graph has as *at least* $f(n) = {n-1 \choose 2}+1$ edges, then it is connected. For instance, $f(5) = 7$, and any 5-vertex graph is connected with 7 edges. However, as you observe, it would also be connected with a smaller number of edges (that is, with $n-1 = 5-1 = 4$ edges).
> 1 votes

---
Tags: graphs
---


title: Spacial access methods and z-order

text:
# Question
Title: Spacial access methods and z-order
I'm relatively familiar with spacial access methods and related data-structure such as Kd-trees and R-trees, but there is a related issue which I don't remember having seen mentioned when reading on that subject.

I'm concerned with the 2 dimension case. Programs manipulating shapes often sort overlapping shapes in z-order, giving a predictable behavior. Querying a data structure for a range access usually provides the shapes in the region in an order not guaranteed to respect the z-order. It is obviously possible to sort the result, but are there some data-structure allowing to avoid that step? Especially when z-order is considered important only for overlapping shapes.

# Answer
> 2 votes
First of all, Kd-trees are data-structures for a number of points, while your problem is considered with shapes. Although you can (and we will) represent the shapes as points in a higher dimensional space in some way, querying shapes is an important special case over arbitrary points. I don't see why Z-orders would be interesting for points, so we really want a data-structure for shapes. R-trees store rectangles, but if you are interested in finding intersections of query regions with non-rectangular shapes, R-trees probably aren't very helpful.

Since a general shape is not so clearly enough, I will consider searching for a range in a set of $n$ simple polygons, this should be sufficient for most cases. Querying this structure with a 2D range (that is, an orthogonal rectangle) for shapes can mean two different things:

* Find all polygons fully contained in an orthogonal query rectangle.
* Find all polygons intersecting an orthogonal query rectangle.

## Polygons fully contained in an orthogonal query rectangle

For the first query, note that a polygon is fully contained in a rectangle if and only if its rectangular bounding box is fully contained inside the query rectangle. So, we can search for the bounding boxes of the shapes. To do this, we represent the bounding box of every shape $s$ as a tuple of the bottom left and upper right corner $(p\_s, q\_s)$. I denote the $x$\- and $y$-coordinates of a point using brackets, e.g. $p\[x\]$. We want to find all $s$ such that $p\_r \leq p\_s$ and $q\_r \leq q\_s$ for a query rectangle $r$. We can use a 4D version of your favorite point range query data structure (Kd,R,Range,etc.-tree) to find all those rectangles in $O(\log^3 n + k)$ time, were $k$ is the amount of rectangles reported, and use $O(n\log^3 n)$ storage for the data-structure. You can actually reduce the storage to $O(n\log^2 n)$, using a 2D-Range tree on the points $p\_s$ and 'linking' this tree to a priority search tree for the $q\_s$ coordinate (since we only have to search in positive direction on the second coordinate). However, Range trees tend to have large coefficients in practice, so you should probably stick to the trees you're familiar with.

## Polygons intersecting an orthogonal query rectangle

For the second type of query on points, finding all polygons intersecting an orthogonal query rectangle, searching for intersecting bounding boxes may lead to a lot bounding boxes where the polygon does not actually intersect the query rectangle, so we need another representation. If we represent all polygons by the $m$ segments of their boundaries, we use a Windowing query to find the segments in $O(log^2 m + i)$, where $i$ is the amount of segments found, using a $O(m\log m)$ size data-structure.

However, we missed the polygons that contain our query rectangle, as we only looked for boundary intersections. We can check this by storing the bounding boxes of all polygons in 2 'chained' segment trees (similar to creating from 2D-range trees from BST's) and query for the bounding boxes that contain endpoints of the query rectangle. This has a query time of $O(\log n + k)$ and uses $O(n\log n )$ storage, but this is dominated by the other part, as $n\leq m$ and $k \leq i$.

## Now, for z-orders...

First, to summarize, we now have algorithms to solve the following problems with the following bounds:

* Finding all polygons fully contained in an orthogonal query rectangle takes $O(\log^3 n + k)$ time and $O(n\log^3 n)$ space, where $n$ is the total number of polygons and $k$ is the number of polygons reported.
* Finding all polygons intersecting an orthogonal query rectangle takes $O(\log^2 m + i)$ time and $O(m\log m)$ space, where $m$ is the total number of polygon segments and $i$ is the number of segments of the polygons reported.

Now, I feel that I can finally consider the z-order. I will assume we want to query for shapes fully contained in our rectangle, since the reasoning and conclusion is similar for the other case.

I do not know why you need the objects sorted on z-order, but I assume you want to iterate over all reported shapes in their z-order (If this is not what you want, there might be a far better method than sorting)

If we query as discussed and sort the found rectangles, we get a running time of $O(\log^3 n + k\log k)$. Generally, $k$ is small compared to $n$, so the additional log factor does not do that much so you might as well sort. In fact, $n\log n$ is usually the best you can get for an geometric algorithm that is not a variant of point location/range search.

If $k$ is not small compared to $n$, you're probably better of not running all this complicated range searching and just run the trivial $O(n)$-algorithm that traverses *all* shapes in their z-order, while checking in constant time if it is in your query range. (I ignore sorting *all* shapes, as you only need to do that once)

## Tldr;+Conclusion

If range searching is your problem, sorting probably isn't and if sorting is your problem, range searching probably isn't.

Although there are probably cases where they both are problem (e.g. zooming in maps), getting a good solution for this case could be rather tricky. I hope that if you learned anything from this answer, it is that range searching can already be quite a tricky business, so I'll leave it at this for now. It might be interesting to look if this specific topic has some useful literature.

# Answer
> 2 votes
I know two data structures that return results in z-order without further sorting.

The CritBit-Tree is a binary prefix sharing tree. If you interleave the coordinates to get a single key, the result is a z-ordered query result. Bit interleaving is straight forward for integer values, but also possible with floating point values (with some caveats). A multidimensional implementation is available here (also includes floating-point interleaving).

The PH-Tree is a z-ordered tree, essentially a CritBit tree that splits in every node in all dimensions, like a quadtree.

For lower dimensions I would recommend the CritBit, but for higher dimensions (\>5 dimensions?) I would recommend the PH-Tree. The PH-Tree also supports rectangle data, while the critbit only supports point data. Essentially PH-Tree is performance wise comparable to an R\*Tree, sometimes worse, sometimes better.

EDIT: For a recent academic reference, see also the paper about z-ordered traversal in hypercubes: "Efficient Z-Ordered Traversal of Hypercube Indexes"

---
Tags: data-structures, computational-geometry
---


title: Bogo sort on NDTM

text:
# Question
Title: Bogo sort on NDTM
As we know on NDTM all the **possible solutions** for a given problem **is verified** the similar kind of work is done in bogo sort sequentially.

*So in future if an NDTM will be there. can we say it will be using bogo sort for sorting?*

# Answer
> 2 votes
Sure, bogosort is efficient on a nondeterministic Turing machine.

But there is no known way to implement a nondeterministic Turing machine so the answer to any question of the form "If we have a physical nondeterministic, will it do X?$ is the same as "If I become pope, will X happen?" The answer is almost certainly "yes" because false implies anything.

---
Tags: sorting, nondeterminism
---


# Question
Title: Does "not regular" imply "acceptor needs memory"?
Regular Languages, by definition, can be accepted by finite automata, which do not have memory. But if I know that a language is not regular, does that imply that any mechanism that recognizes the language must have memory?

# Answer
> 3 votes
Every language $L \subseteq X^{\ast}$ for $X$ a finite alphabet could be accepted by the following (in general infinite) "automaton" (in the usual notation as "alphabet, states, start state, transition relation and final states") $$ \mathcal A = (X, Q, L, \delta, F) $$ with $Q := \\{ L/w : w \in X^{\ast} \\}$, $\delta(L/w, u) := L/(wu)$ and $F := \\{ L/w : \varepsilon \in L/w \\}$, where $$ L/w := \\{ u \in X^{\ast} \mid wu \in L \\} $$ is the quotient of the language (i.e. we take away prefixes from words in $L$). The set of quotients could be regarded as the states, or the memory. Which is finite if $L$ is regular (and more this construction gives a minimal finite automaton), and is infinite if $L$ is not regular (for example consider $L = \\{ a^n b^n \mid n \ge 1 \\}$ over $X = \\{a,b\\}$).

So in short in this (somehow canonical) model even a regular language has some kind of memory (a state which signalizes some property of the string being processed), but the crucial property is that we can get along with finitely many (memory) states, whereas in the non-regular case in this model we always need an "unbounded" memory/states.

---
Tags: formal-languages, automata, computation-models
---


# Question
Title: What is the literature on a sparse matrix encoding of rose trees?
I have 'discovered' a way to encode rose trees (see e.g. What are the applications of Rose trees? ) as a sparse matrix: if you have a node *n* with ID *i* and parent ID *p,* then you place *n* in the matrix at coordinates (row, column) of (*p*, *i*). This makes it easy to:

* Get a node by its ID and parent ID (single lookup of the matrix)
* Get all children of a node ID (lookup a matrix row)
* Prune and graft subtrees (change the coordinates of the subtree root)

Now I'm thinking that I can't be the first person to have thought of this. Can anyone point me to any literature which discuss this encoding?

# Answer
> 2 votes
In view of rose tree being just a special case of a graph, the matrix representation you mentioned is simply the *adjacency matrix representation of directed graph*. Your particular encoding takes the rose tree's edge to always be directed consistently either from parent to child or child to parent.

Questions about rose tree in this encoding thus can be researched easily by looking up results about adjacency matrix representation of directed tree graph.

Relevant notions are:

* get all leaves of subtree -\> reachability
* graft tree -\> wedge sum

---
Tags: data-structures, trees, sparse-matrices
---


# Question
Title: In cycle stealing mode, Does CPU gets blocked for 1 cycle or blocked till DMA transfer completion?
In cycle stealing mode, is CPU idle during data transfer between peripheral devices or idle only for 1 cycle ( during shifting of bus controls ) ? Because I'm unable to understand these lines.

> The DMA module is transferring characters at the rate of 1200 characters per second. or **one every 833 microsecond**. The DMA therefore steals every 833rd cycle.

Now, I think these lines make sense only if we assume CPU is blocked for 1 cycle not during 833microsecond(during DMA transfer). Please anyone help me where I'm wrong or am I missing something.

# Answer
> 3 votes
The CPU doesn't stay idle at all. It just gives the control of the data Bus to the DMA for 1 memory cycle . DMA transfers the data in this cycle which is consistent with it's transfer rate. Meanwhile the CPU can perform operations which do not involve the memory bus (by the means of cache memory and registers). In the scenario which you have presented assuming each instruction takes 1 cycle to complete , every 833rd instruction will have to wait for the DMA to complete its operation.

---
Tags: computer-architecture, cpu
---


# Question
Title: How can I make k nearest neighbor queries fast on unit hypersphere?
I have $m$ points $D = \\{x\_1, \dots, x\_m\\}$ with $x\_i \in \mathbb{R}^n$. After some preprocessing / building up data structures for those points, I get $T$ queries $y\_i \in \mathbb{R}^n$ with $i=1, \dots, T$. Each query comes at a time and independently. The datastructures for the queries should not be modified by the past queries. After receiving an query $y\_i$, the $k$ nearest neighbors

$$NN\_k(y\_i) \subset D \text{ with } |NN\_k(y\_i)| = k \text{ and }$$ $$\forall x\_a \in NN\_k(y\_i) \forall x\_b \in D \setminus NN\_k(y\_i) : \\|x\_a - y\_j\\|\_2 \leq \\|x\_b - y\_j\\|\_2$$

All points $x\_i$ and all queries $y\_j$ are on the unit hypersphere, so $\\|x\_i\\|\_2 = \\|y\_i\\|\_2 = 1$.

How do I process those queries fast?

## Limits

To get a feeling for what matters, here are some orders of magnitude:

* $100 \leq n \leq 1000$: Dimension of points
* $m \geq 100\\,000$: Candidates
* $T \geq 10\\,000\\,000$: Number of queries
* $3 \leq k \leq 20$: Expected number of returned points
* Reasonable memory consumption (e.g. less than 2GB for the data structure)

The query time for a single brute force approach is in $\mathcal{O}(m \cdot n)$ as it just compares every candidate point in $D$ with the query and stores the closest $k$ of them.

## Misc

I've just implemented this with Python (see code).

* `k=5, n=128, m=100000, T=100: 0.56s per query.` (Brute force approach)

That is actually much better than I expected. However, I guess this could be an order of magnitude faster with a good data structure / smarter algorithm. I wrote the Python script in a way which should make it easy to run your own experiments on your tests, if you like.

# Answer
> 1 votes
As a rule of thumb, when the number of dimensions $n$ is less than about 10, fancy data structures (like k-d trees) work well; when the number of dimensions is greater than about 30, fancy data structures typically perform poorly and may be no better than a brute-force linear scan. Wikipedia lists a similar rule of thumb: if $m \gg 2^n$ (where $m$ is the number of points in the data structure and $n$ is the number of dimensions), then k-d trees work well, otherwise they won't. Exceptions exist, e.g., where your data is "structured" and non-random, but this is probably a good first guideline.

In your example, the number of dimensions is at least 100. Therefore, I wouldn't expect any of the fancy data structures (k-d trees, M-trees, etc.) to be better than the simple linear scan.

Essentially, you are suffering from the curse of dimensionality.

You mention that your points are all on the surface of the hypersphere. Unfortunately, this doesn't help much. Heuristically, points on the surface of a $n$-dimensional hypersphere are a lot like points in a $n-1$-dimensional space.

# Answer
> 0 votes
Points of an high-dimensional metric space may efficiently be indexed by an M-tree. An in-depth discussion of the data structure and of your problem may be found in this paper.

---
Tags: nearest-neighbour
---


# Question
Title: Is unary language with polynomial power context sensitive?
I suppose that $\Sigma = \\{a\\}$.

Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \\{a^{p(n)} \\; | \\; n \in \mathbb{N}\\}$ is a context sensitive language.

It seems that it is a context sensitive language. I guess making LBA or context sensitive grammar is not easy for this language. Can I prove this with closure property of CSL for example like complement? Can any one help me to prove for instance $L\_1 = \\{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\\}$ is context sensitive. Maybe I can get an idea from this to prove my first question.

# Answer
> -1 votes
Not true for linear polynomials. E.g let $p(n)$ be $3n+2$, then L is generated by the regular grammar 'S --\> aaaS | aa'. *\[unless you mean 'at most context-sensitive', not 'exactly context-sensitive'\]*

The Pumping Lemmas for both regular and context-free grammars seem to imply that any language over a 1-letter alphabet can be decomposed into a (not necessarily disjoint) union of sub-languages corresponding to linear polynomials. If the set of linear polynomials in question can be made finite (which I suspect must be true, but I can't prove or disprove off the top of my head *\[and I am not sure it even matters\]*), then any higher-degree polynomial must take on values not achieved by any polynomial in the linear set, in which case such languages must be at least context-sensitive.

Also: A strategy for building a context-sensitive grammar for a polynomial language over one alphabet is to construct a sequence of $k$ sub-grammars, each of which takes $m$ consecutive $a$'s and transforms it into $b\_km+c\_k$ consecutive $a$s for some constants $b\_k$, $c\_k$ *\[think "Horner's Method"\]* and then 'cascades' to the next sub-grammar.

So if you mean 'at most context-sensitive', then yes.

---
Tags: formal-languages, context-sensitive
---