# Question
Title: Can we call deterministic equivalent of all NFA to be finite
Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we always call the deterministic equivalent to be a finite automata just by saying that as n is finite 2^n will also be finite even though the actual memory will be very large or is there some limitation?

# Answer
> Finite automata is defined as a simple machine having small memory.

In fact, they are *not* defined in this way. You can look up the actual definition on Wikipedia. Even as an informal definition, the adjective *small* is inappropriate here — in fact, DFAs and NFAs have *constant* memory.

You are using the letter $n$ to represent the number of states in a finite automaton. The letter $n$ is usually reserved for the input length. *The number of states in a finite automaton doesn't depend on the length of the input.* On the contrary, the number of states is fixed ahead of time, and the finite automaton then uses exactly the same number of states for any input, of any length. Perhaps it will be less confusing if you use a different symbol, say $m$.

> ... the actual memory will be large ...

In theoretical computer science, there are no arbitrary constants thrown around. Today, $2^{50}$ bytes of memory can be considered large, but next year it might be $2^{60}$ bytes of memory. The same theory should account for both. In theoretical computer science, the formal meaning of *large* (or, more accurately, super-constant), is "tending to infinity with $n$", where $n$ is the input length. Finite automata use a fixed amount of memory which is independent of the input length, and so they never use a *large* amount of memory, as far as theorists are concerned.

In practice, some automata are too big to actually implement. But this is a practical restriction rather than a restriction on the actual definition.
> 3 votes

---
Tags: automata, finite-automata, nondeterminism
---


title: Time complexity of Rabin-Karp algorithm

text:
# Question
Title: Time complexity of Rabin-Karp algorithm
> **$n$ : length of text T**
>
> **$m$ : length of pattern P**

When I study Rabin-Karp algorithm, I learned the best case of this algorithm is $\theta(n-m+1)$. Because if a hashed number is too small to modulo by some other number.

But when I'm talking with my friends about this best complexity, I was very curios that does above theta notation can be represented by $\theta(n)$ if $n$ is asymptotic to infinity?

First time, it was reasonable to me that $\theta(n)=\theta(n-m+1)$ is correct because it is asymptotic notation. But if $m$ is always $n-1$, can we use $\theta(n)$ in this situation? I'm confusing about notation concept and what I'm curious is below question.

> What is the right time complexity notation of Rabin-Karp algorithm?
>
> $\theta(n)$ or $\theta(n-m+1)$?

# Answer
The running time you quote isn't correct. If $n = m$ then it takes $\Omega(n)$ to verify that $T = P$. The best case running time of *any* string matching algorithm is $\Omega(m)$, since this is how long it takes to verify a match. Perhaps you are disregarding the time it takes to compute the hashes.

Ignoring all of this, let us suppose that we are considering an algorithm whose running time is $\Theta(n-m+1)$, where $m \leq n$ are two parameters. As your example makes clear, this is *not* the same as $\Theta(n)$, since if $m$ is close to $n$ then $n-m+1$ is much smaller than $n$. Generally speaking, an asymptotic expression depending on two parameters cannot be reduced to an asymptotic expression depending on only one of them.

In practice, often $m$ is itself a known function of $n$, and this can be used to reduce $\Theta(n-m+1)$ to an asymptotic expression depending on a single parameter. For example, if $m = n/2$ then $\Theta(n-m+1) = \Theta(n)$, whereas if $m = n$, then $\Theta(n-m+1) = \Theta(1)$.
> 2 votes

# Answer
Rabin-Karp algo consists of two steps:

* hash first m symbols of input and the pattern, which takes $\theta(m)$
* check first n-m+1 positions of the file comparing hashes of next m chars at each position to the pattern hash, which takes $\theta(n-m+1)$

Most probably, your source mentioned only the second step complexity.
> 1 votes

---
Tags: algorithms, asymptotics, string-matching
---


# Question
Title: Software code generation from the (operational) semantics - reference request for automatic programming
Are there research trends that try to research code generation directly from the (operational or some other kind of) semantics? One can imagine cognitive architecture that discovers and reasons about the tasks that the software should do and constructs the operational semantics of some program. And later there should be only one additional small system that generates software code from the semantics for the execution on well established platforms.

In such a way one can avoid the uncertain and rigorous path that goes through discovery and generation of formal specification that requires rigorous reasoning (sometimes undecidable, sometimes exponentially hard). Use of cognitive architecture and generation of the operational semantics (or some other semantics) allow one to do approximate, uncertain reasoning which cancels undecidability or exponentiality by discovery of additional axioms or shortcuts.

This is reference request question. Of course, I can use Google, but my experience is that computer science often names the research themes and terms differently than I have them imagined firstly and there is no reliable semantic search. So - reference request is necessary.

# Answer
> 2 votes
I haven't seen anything on this but the closest I could find is Evolving Algebras:

In that mini course there are several papers outlining different aspects and applications of the Evolving Algebra. From one of them:

> In 1988 Yuri Gurevich has discovered the notion of evolving algebra in an attempt to sharpen Turing's thesis by complexity theoretic considerations (see \[22\]). Through numerous case studies (see \[4\] for an annotated list which is complete up to 1994) it has become clear since then that using the notion of evolving algebras one can develop a powerful and elegant specication methodology which has a huge yet unexplored potential for industrial applications. In this report we are going to explain the basic concepts of this approach to the design and analysis of complex systems and illustrate its salient features through a challenging example from real life.

They also talk about successive refinement and hierarchical modeling.

Maybe if you could describe more on what you're trying to accomplish with the code generation part that would be helpful. It sounds like you are wondering about generating/forming a verified program from cognitive reasoning somehow, automatically generating the operational semantics. I haven't seen anything on that.

---
Tags: reference-request, formal-methods, operational-semantics, code-generation
---


# Question
Title: Can I make last part of counting sort become to be starting from lowest index?
Counting sort is originally like below code.

```
for (int i = 0; i <= 5; i++) c[i] = 0;
for (int i = 1; i <= 8; i++) c[a[i]]++;
for (int i = 1; i <= 5; i++) c[i] = c[i] + c[i - 1];
for (int i = 8; i >= 1; i--) {
    b[c[a[i]]] = a[i];
    c[a[i]]--;
}

```

In the above, last for loop iterates from last index because of stability of counting sort.

But, I want to iterate from first index 1 as well as maintaining the stability of sorting.

I'm trying and thinking lots of time, I cannot do. How can I do?

# Answer
Prior to the last loop, `c[i]` holds the index of last element of bucket `i` plus 1. It's why when you use `c[i]` to address items in bucket `i` you need to go back. But `c[i-1]` contains index of the first element of bucket `i`, so you can just use it... except that you need index for bucket 0 too.

So the simplest way is to modify third cycle making it to write **initial** index of bucket i to `c[i]`. It may be done f.e. with extra temporary (note that `i` in revised loop starts from 0):

```
sum = 0;
for (int i = 0; i <= 5; i++)
{
    sum += c[i];
    c[i] = sum - c[i];
}

```

Note that since indexes in `b` starts from 1, you need to pre-increment `c[a[i]]` in new version of last loop (if indexes in `b` should go from 0, do post-increment instead):

```
for (int i = 1; i <= 8; i++)
{
    c[a[i]]++;
    b[c[a[i]]] = a[i];
}

```
> 0 votes

---
Tags: sorting, counting
---


# Question
Title: Understanding Binary Search for Kth Smallest element in an Array
The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 cause we needed to adjust the mid value based on the start and end of our range. The thing I just can't seem to wrap my head around is why does it work? The numbers in the array are unsorted and not contiguous,duplicates may exist so why does reducing the search space in our range based on countless or countequal give us the correct answer? Can someone give some intuition or simple explanation to why this works?

# Answer
Let me start by recalling the question:

> Given an unsorted array of $n$ elements in the range $1,\ldots,m$, find the $k$th smallest element in $O(n\log m)$ time and $O(1)$ case.

Calling the array $A$, the idea is to perform binary search on the array $B$ of length $m$ in which $B\[i\]$ is the number of elements in $A$ which are at most $i$. If $B\[i\] \geq k$ but $B\[i-1\] \< k$ (assuming $B\[0\] = 0$), then $i$ is the $k$th smallest element. We can find $i$ using binary search.

Instead of computing the array $B$ ahead of time, we have "oracle access" to it: we can compute any given entry in time $O(n)$ by going over the entire array $A$. This is the algorithm you link to.
> 4 votes

---
Tags: algorithms, algorithm-analysis, search-algorithms, searching, binary-search
---


# Question
Title: How much time would be needed to compute an algorithm with time complexity $O(n^k)$?
How much time would be needed to compute a minimum k-cut, which has time complexity $O(n^k)$ on a graph with $n=5000$ and $k=30$? Consider using a basic 2GHz and 8GB RAM laptop.

Please explain also the process of how to compute the answer.

# Answer
An algorithm has time complexity $O(n^k)$ if there exists a constant $C\>0$ such that the number of operations that the algorithm performs in the RAM model on an input of length $n$ is at most $Cn^k$.

There are several reasons why this doesn't allow you to determine how much time the algorithm will take on a given machine for a given value of $n$:

* $Cn^k$ is only an upper bound.
* We don't know the value of $C$.
* Your machine differs from the abstract model of computation used to analyze the algorithm.

Therefore the only way to really know how much time a certain algorithm would take is to code it and empirically measure its running time.

What good is asymptotic analysis, then? The abstract machine is a reasonable model of real computers, so it is likely that the running time will scale like $n^k$ (assuming $O(n^k)$ is a tight upper bound). If $k$ is large, then likely the algorithm isn't practical. So asymptotic analysis allows you to compare different algorithms on paper rather than in practice. Of course, sometimes this comparison will result in the wrong conclusion. This is the case for fast matrix multiplication, for instance.
> 5 votes

# Answer
Let's make the unrealistic assumption that each step of your algorithm takes in your machine just one cpu cycle. That means that each step takes 0.5 ns. In the worst case the running time will be $5 \cdot 10^{-10} \cdot (5 \cdot 10^3)^{30} s \approx 4.7\cdot 10^{101}$ seconds which is about $1.5\cdot 10^{85}$ billion years or about **$10^{84}$ times the life of universe**. So I wouldn't suggest to actually measure it. The only hope is for average case the algorithm to be asymptotically more efficient, but I don't know much of this algorithm to help you further.
> 1 votes

# Answer
You can't really say how long it will take. Look at Curious\_Dim's answer, which is not at all unrealistic. However, I have a different algorithm that has a different result and the same asymptotic behaviour:

"Given n items, first apply a O(n) algorithm which keeps at most n/10000 items, and then calculate a minimum k-cut for these items". Same asymptotic behaviour, but with a time constant that is smaller by a factor $10^{120}$. So for n = 5,000 the runtime is practically zero..
> 1 votes

---
Tags: time-complexity
---


title: How to find the class of a problem?

text:
# Question
Title: How to find the class of a problem?
I've learnt about complexity classes but my knowledge doesn't seem to help much when I am given a problem and need to decide it's complexity.

Here is the problem at hand: A set of weights with the same dimensions but with different densities have to be ordered on a plank (on a straight line). The length of the plank is not enough to put everything in one line so you'd have to stack weights on top of each other. There are $n$ weights and there's space only for $m$, $m\<n$ weights on the plank. The weight of each object is given.

The target is to stack weights such that the weights are spread across the plank as smoothly as possible. The following figure shows a sample (possible) solution for n=11 weights each having weight w1 to w11 and m=5.

The smoothness of the weight distribution is calculated by finding the average of all weights and summing up the deviation from this value at each spot.

Now definitely this is a combinatorial problem. And it is definitely a 'yes' 'no' answerable problem.

It seems to me that it's not in NP. Because given a solution, there is no way of saying in polynomial time that it's the correct answer. Is this right?

If so, does that mean it is in NP hard?

How can I really find which class it belongs to.

I'd appreciate it if anybody could help me with this problem.

# Answer
> 3 votes
You have described an optimization problem, namely, find the arrangement that minimizes the average deviation from the mean. The decision version of this problem is, given an input to your problem and a value $T$, whether there exists an arrangement whose average deviation is at most $T$. This problem is in NP.

Whether it is NP-hard or not is for you to ponder. Combinatorial problems in NP tend to be either NP-hard or in P, so you should simultaneously try to prove that your problem is NP-hard via reduction from a known NP-hard problem, or to find an efficient algorithm for your problem.

---
Tags: complexity-theory
---


title: A Language Belonges to PSPACE

text:
# Question
Title: A Language Belonges to PSPACE
> Let $A,B$ be two languages, for which we know:
>
> * $A \in PSPACE$
> * $A\le\_LB$
>
> Can we conclude from the above that $B \in PSPACE$ ?

I think the answer is no, however I don't know how to prove it. I guess I have to write a reduction that proves otherwise, but how?

Thank you!

# Answer
> 2 votes
No. Note that given languages $A,B$ and a reduction $A\le\_L B$, you get that $B$ is at least as hard as $A$, but that's about it.

You can contradict the above statement with the following extreme:

Take $A = \\{0\\}$, then $A\in \text{PSPACE}$, and take $B= H\_{TM}\cup\\{0\\}$.

Define $f$ to be the following reduction $A \le\_L H\_{TM}\cup\\{0\\}$ (we can assume that $1\notin H\_{TM}$):

$$f(0) = 0$$ $$\forall x\in \Sigma^\*\setminus\\{0\\} . f(x)=1$$.

Clearly $f$ works in logarithmic space, but $B$ is clearly not in $\text{PSPACE}$. In fact, it isn't even in $\text{R}$.

---
Tags: complexity-theory, reductions, space-complexity
---


# Question
Title: Exponential time local search heuristics for Weighted MAX-CUT-Flip
I have read multiple times \[Theorem 5.15, 1\]\[End of page 2, 2\] that local search heuristics for $\textsf{Weighted Max-Cut}$ with $\textsf{Flip}$ neighbourhood takes an exponential time in some cases.

In particular, the problem is as follows. Given a partition $(V1,V2)$, its neighbours are partitions which can be obtained by moving one vertex from $V1$ to $V2$, or from $V2$ to $V1$. Such neighbourhood is polynomial in size. At each step algorithm chooses the neighbour with highest value strictly greater than that of the current partition (o/w, it is locally optimal and so the algorithm terminates).

I am asking for a weighted graph and an initial partition of the vertices such that the above local heuristics would need exponential number of iterations to get to a local optimum.

I have not seen a single concrete example.

**References**

\[1\] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM J. Comput., 20(1):56–87, February 1991.

\[2\] Lecture notes: https://courses.engr.illinois.edu/cs598csc/sp2011/lectures/lecture\_12.pdf

# Answer
> 2 votes
Check out the paper: On the Power of Nodes of Degree Four in the Local Max-Cut Problem - Burkhard Monien and Tobias Tscheuschner.

In the paper they take a sub-graph of size 5 constructed from two types of vertices (they call them type-1 vertices and type-3 vertices). Then they build a graph from n sub-graphs concatenated, and show a specific initial start of the max-cut algorithm. In this initial start, there would be an exponential number of flips until the local optima would be obtained.

---
Tags: complexity-theory, runtime-analysis
---


# Question
Title: Question regarding Hoare's partitioning scheme and a slight modification to it
This is the pseudocode on wikipedia for Hoare's partitioning scheme:

```
algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot   //Question here

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

```

This code finds an inversion and swaps it. Now, the problem of partitioning about a pivot is to divide an array such that all elements \<= pivot fall in one partition, and all elements \> pivot fall in the other.

My question is simple: why not use `while a[i] <= pivot` ?

As far as I can tell, it will work correctly, infact it would align better with the previous definition of partitioning.

If it does work, the big question is why wasn't it used in the original paper? It makes more sense and seems to be slightly faster as well (less number of swaps required).

Infact, while we're on the subject: would it be incorrect to also use `while A[j] >= pivot` that could further reduce the number of swaps.

I know that if I'm too worried about multiple elements repeating I should use 3 way partitioning, but I'm curious about how this algorithm would work nonetheless.

# Answer
> 1 votes
> Why not use `while a[i] <= pivot` ?

You could. It's arbitrary. Either way will work fine. We just have to choose one of those two choices. They both have the same asymptotic running time.

# Answer
> 1 votes
The code you cited will find first element `>=pivot` at left and first element `<=pivot` at right and swap them. So, after partitioning, left part will include elements `<=pivot` and right part will include elements `>=pivot`, i.e. elements `=pivot` may end up in any part. In particular, original `a[lo]` element will end up as `a[hi]`.

Now you should see the catch! If you will replace first comparison to `A[i] <= pivot`, the `a[lo]` element will never be moved and used time and again as the threshold in the left recursive calls! At least if `partition` is followed by simplest recursive calls to qsort:

```
qsort(lo,hi):
    if (lo>=hi) exit
    j = partition(lo,hi)
    qsort(lo,j)
    qsort(j+1,hi)

```

In this case, with proper implementation of the partition algorithm that puts everything `<=pivot` to the left part, you will just get nice infinite recursion.

Now, while we are here, let's consider 3 remaining possibilities:

* allow `<=pivot` on the left and `>=pivot` on the right: the same. `a[lo]` will remain in its place, and in the left recursive call all elements are `<=pivot` so they all be placed in the left part again.
* put `<pivot` to the left and `>=pivot` to the right: if ALL elements `=pivot` you will end up in infinite recursion.
* allow only `<pivot` on the left and only `>pivot` on the right, so elements `=pivot` on each occurence will be moved into opposite part. If at least one swapping occured, both parts are no more empty. If any of remaining elements is `<=pivot`, it will happen. If all remaining elements `>pivot`, then logic of returning `j` will effectively put first element into the left partition (even without any swapping!), and the rest into the right one.

So, it seems that their strange code is the only one that guarantees termination of sorting when combined with oversimplified `qsort` driver. It also shuffles `a[lo]` elements on each pass so you get enough chances to get non-quadratic behavior.

Note that this code is still not entirely correct, it should be:

```
    do
        j := j - 1

        if i >= j then
            return j

    while A[j] > pivot

```

---
Tags: sorting, correctness-proof, quicksort, partitions
---


# Question
Title: How to resolve issue of circular definition for an `If` statement
I am trying to define an `If` statement, but am stuck because the definition/implementation of `If` is circular from what I have tried. For example, here is one definition:

```
class If {
  provide: Condition
  provide: TrueBlock
  body:
    If (Condition) {
      call(TrueBlock)
    }
}

```

You can then use it like this:

```
If (true) {
  Something()
}

```

But the thing is, the definition itself uses `If` to define it:

```
class If {
  ...
    If (Condition) {
      call(TrueBlock)
    }
}

```

The only other way I can think of defining it is by saying that an `If` statement is an "atomic statement", and so it doesn't have an implementation. (The compiler or whatever would then have special instructions to treat it uniquely).

```
class If {
  provide: Condition
  provide: TrueBlock
}

```

That would be the whole definition of `If`. No *implementation* required.

Wondering if this is sort of the right approach to this problem. The problem being that you can't really *implement* an `If` statement without resorting to using `If` itself. And so you define it as atomic.

# Answer
One general rule of Turing completeness is that you need some form of conditional branching built into your model. A Turing machine, for example, can transition to a new state based on what it sees on the tape. Programming-language-wise, a while loop works, as does an infinite loop with a conditional break statement, or if and goto.

As such, if you have no form of conditional branching built into your model already, you can't create one out of nowhere—if your model isn't Turing complete, you'll need to add something else from outside to the model to make it so.

An "atomic" if statement will do the trick, certainly, as will something like Lisp's conditional. But whatever it is, it'll have to be implemented by the compiler or interpreter, rather than being created within the language itself.
> 4 votes

---
Tags: programming-languages
---


# Question
Title: Knapsack problem with diminishing prices
I wonder if the knapsack problem with diminishing prices is already studied? The problem is similar to the regular knapsack problem, except the price of each item is a decreasing function of the total size of the already selected items.

Given $n$ items each with size $s\_i$ and price $v\_i(s)$, where $s$ is the total size of the already selected items, a size limit $S$ and a total price $V$, we want to find a sequence of items $\langle e\_1,\cdots,e\_k \rangle$ so that $\sum\_{i=1}^k s\_{e\_i} \le S$ and $\sum\_{i=1}^k v\_{e\_i}(\sum\_{j=1}^{i-1}s\_{e\_j})\ge V$.

The problem is obviously at least as hard as the regular Knapsack problem (i.e., weakly NP-hard). I wonder if the problem is any harder? Can the dynamic programming solution for the regular problem be used for this problem as well.

# Answer
Consider the special case where $V\_i\le v\_i(s)\< V\_i+\epsilon$ such that $\epsilon$ is a very small positive constant, then your problem is equivalent to the regular knapsack problem where item $i$ has price/value $V\_i$. So your problem is still NP-hard.
> 1 votes

---
Tags: algorithms, complexity-theory, combinatorics, knapsack-problems
---


# Question
Title: How to efficiently select the initial node to start a search in a Skip Graph
Checked out a few papers on Skip Graphs:

All of the insertion/deletion algorithms assume that you have selected a start node to begin the search. However, it is not described how the start node is selected. In doing some initial exploration into how to do this, I start thinking in terms of the following:

```
level1nodechunk1 = count next node node node ....
level1nodechunk2 = count next node node node ....
...

```

Basically, a level is just a bunch of nodes:

```
node node node ...

```

If you are to randomly select a starting node, and they are not contiguous in memory, then you have to navigate your way there. So instead of going one node at a time, I group it into chunks for the particular level, and specify the `count` and `next` so you can jump ahead to the next one if desired.

So say you generate a random number `x = random num between 0 and totalnodecount`. Say it is 20 and each level chunk has 5 nodes. Then you would do:

```
level1nodechunk1 = [count] [next] (5)
level1nodechunk2 = [count] [next] (5 + 5 = 10)
level1nodechunk3 = [count] [next] (10 + 5 = 15)
level1nodechunk4 = count next node node node node [node5]

```

You would jump over chunks 1-3 and get to chunk 4, see it has 5 contiguous nodes, and jump to that one. So it's just ~5 instructions instead of 20 (one per node) roughly.

But the problem is if you have 1 billion nodes. Then if each one is only 5 nodes, then you have 200 million chunks, so ~200 million instructions. So maybe you make the chunks to be 10,000 nodes each, that's still 100,000 instructions to find the start node.

I'm wondering how they do this efficiently.

If all the nodes were contiguous then it would be easy, $O(1)$ lookup by index. If you hardcode a chunk count so we only have say 20 chunks, no matter how many nodes, then you have to account for the worst case of lets say 1 billion nodes. So that means each chunk is 50 million nodes. But if you have only currently used 10 nodes out of 1 billion, then that's tons of wasted memory reserved.

The only other thing I can think of is that the start node is always the actual first node in the lowest level of the skip graph, then you navigate to the top-level for that node and work your way back down.

IIRC, the reason to "randomly" select a start node is to prevent hotspots.

Another possible solution is to cycle through the level 0 nodes. Basically:

1. Start at the start level 0 node.
2. Cache the next node it points to as the future start node.
3. Next query, the start node is that cached node. Then set next node to its pointer, etc.

But that would give preference to the first nodes more than the last (i.e. it's not random).

# Answer
> 2 votes
First, the skip graph is a distributed data structure. There is no reason to use it in a single machine context.

For a singly-linked skip *list* (on a single machine), you would start at the beginning. This is trivial to find; you just hold a pointer to the first node. For a doubly-linked skip list, you could start at any node, though unless you had some cursor-like abstraction, you'd presumably start at the beginning for most operations anyway.

A skip *graph* is effectively a collection of *doubly*-linked skip lists that share structure. There is no need to start at the beginning. This allows the machine on which to initiate an operation to be chosen arbitrarily. In a public peer-to-peer context, you are usually only aware of one or a few machines. In a data-center context, usually a load balancer will choose the machine.

A machine will generally host many nodes of the skip graph. It's not clear to me how much it matters to pick a local node at random. Typically, only some of the nodes will be connected to nodes on other machines, so picking any other node is the same as picking one of these as far as spreading load between the machines. Nevertheless, if you wanted to pick randomly from the local nodes there are a variety of approaches. Since you are only concerned about local nodes, you are free to use any non-distributed data structure to keep track of them. For example, a size-balanced tree would work. You would pick a number between 0 and the number of local nodes, and then do a rank query on a size-balanced tree containing (pointers to) the local nodes. Alternatively, you could probably get something close to a uniform distribution on average by assuming that the any one of the local portions of the skip lists making up the local portion of the skip graph is perfectly "balanced". This lets you estimate how many nodes you are skipping when you traverse a link at a given level which lets you do an approximate rank query directly against (the local portion of) the skip graph. Neither of these approaches is likely to affect the asymptotic complexity of any operation.

---
Tags: algorithms, graphs, data-structures, optimization
---


# Question
Title: How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?
I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help.

The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should choose which symbols to mark.

I tried with all the first $N$ $a$s (and also other combinations), but then for $v=a^j$ and $x=a^j$ (and $w=b^{N+1}$) pumping doesn't get a string out of $L$. My idea is that I should involve both $a$s and $b$s between the marked symbols and somehow force the pumping for both, but I don't know how.

# Answer
Let $N$ be the constant of the Pumping Lemma for CFL.

Let be $z=a^N b^{N+1} a^N b^{N+1}$.

let's analyze some of the possible decompositions of $z$ in $uvwxy$:

(note that $vx$ has always at least one symbol)

1. $u=\epsilon$, $v=a^\*$, $w=a^\*$, $x=a^\*$, $y=b^{N+1} a^N b^{N+1}$. just pumping once we get a string out of $L$.
2. $u=a^\*$, $v=a^\*$, $w=a^\*$, $x=a^\*$, $y=b^{N+1} a^N b^{N+1}$. same as above.
3. $u=a^\*$, $v=a^\*$, $w=a^\*$, $x=a^\*b^\*$, $y=b^\* a^N b^{N+1}$. same.
4. $u=a^\*$, $v=a^\*$, $w=a^\*$, $x=b^\*$, $y=b^\* a^N b^{N+1}$. same.
5. $u=a^\*$, $v=a^\*$, $w=a^\*b^\*$, $x=b^\*a^\*$, $y=a^\* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $\>N$.
6. $u=a^\*$, $v=a^\*$, $w=a^\*b^{N+1}$, $x=a^\*$, $y=a^\* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $\>N$.
7. $u=a^\*$, $v=a^\*$, $w=b^{N+1}$, $x=a^\*$, $y=a^\* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $\>N$.
8. $...$

Anyway the problematic case is 7. because it could be $u=a^k$, $v=a^j$, $w=b^{N+1}$, $x=a^j$, $y=a^kb^{N+1}$ with $k+j=N$, so that pumping doesn't push $z$ out of $L$. But again, it can't happen otherwise we would have $\mid vwx\mid \>N$, which is not possible and it is guaranteed by the lemma.
> 2 votes

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


title: Regularity under set difference

text:
# Question
Title: Regularity under set difference
Let L be a regular language. Then $\Sigma^{\*} \backslash L^{\*} = (\Sigma^{\*} \backslash L)^{\*}$

How do I prove it is wrong?

# Answer
For instance, take $\Sigma=\\{a,b\\}$ and $L=\\{a\\}$.

Then, $L^\*=\\{\epsilon,a,aa,\ldots\\}$ and $\Sigma^\*\setminus L^\*$ comprises any word except those made by only $a$s. In other terms, those words containing at least one $b$.

Instead $(\Sigma^\*\setminus L)$ comprises any words except $a$ (this includes $aa$, for instance). So, $(\Sigma^\*\setminus L)^\*$ comprises all concatenations of words which are not $a$. Well, this is the same set of words: all the words except $a$.

Concluding, it is easy to see that $aa$ belongs to the latter set but not the first one.

---

Not only we can find a counterexample, but we can even prove that the equation is false whatever $L$ is! Indeed, the empty word $\epsilon \in (\Sigma^\*\setminus L)^\* \setminus (\Sigma^\*\setminus L^\*)$ is a wtiness to their difference.
> 1 votes

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


# Question
Title: What the heck is a memory channel "CS bus"?
While I was reading about memory architecture from the CMSC 22200's Lecture 17 of University of Chicago, I got stuck on determining the meaning of the word "CS" used for describing a bus as part of memory channel:

However I didn't find any additional source pointing out that bus. And furthermore, I found on different reference that:

> The memory channel is made up of a data bus and an address/comm and bus.

So, I don't know from where they got the information about the "CS bus"? And what is it exactly?

# Answer
> 3 votes
I think it is the "Chip Select" part which is mentioned at slide 26.

It probably selects whether to use the chip on the front or in the back.

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Why analysis of Aloha protocol uses Poisson distribution?
Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial distribution that is approximated by Poisson because $n$ (number of users) is large and $p$ (transmission probability) is close to zero?

# Answer
IMO, the biggest reason is that Poisson distribution is more tractable *mathematically*. Some experimental studies claim that it does follow Poisson. However, there are also other experimental studies show that it does *not*.

*Mathematically*, Poisson distribution can be viewed as the approximation of binomial distribution under certain conditions. However, it is not the rationale behind the Aloha protocol.

As a mathematical model, you should consider your own scenario carefully and decide whether to use it or not.
> 3 votes

# Answer
Usually, the Poisson distribution is chosen because the process is assumed to be memoryless.

Suppose that a packet just arrived. The arrival time for the next packet has a certain distribution of probability. Now, suppose that after observing the system for some time interval we saw no new packet. In some cases, it is reasonable to assume that this observation did not change the probability distribution at all: that is, observing no packet for a while does not make new packet more likely or less likely to arrive soon. This is called the memoryless property.

Under these assumptions, one can prove that the arrival time for the next packet must be distributed according to the Exponential distribution. Further, if we fix a time interval, the number of packets which will arrive within the interval is distributed accoring to the Poisson distribution.
> 1 votes

---
Tags: probability-theory, computer-networks, performance
---


# Question
Title: Understanding application of Arden's theorem to find regular expression
I learnt Ardens theorem and its usage as follows:

> **Ardens Theorem**
> Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a unique solution that is $R = QP^\*$

Using Ardens theorem (source):

> **Using Arden's theorem to find regular expression**
> 1. For getting the regular expression for the automata we first create equations of the given form for all the states
> $q\_1 = q\_1w\_{11} + q\_2w\_{21 }+ … + q\_nw\_{n1} + \epsilon$ ($q\_1$ is the initial state)
> $q\_2 = q\_1w\_{12} + q\_2w\_{22} + … + q\_nw\_{n2}$
> :
> $q\_n = q\_1w\_{1n} + q\_2w\_{2n} + … + q\_nw\_{nn}$
> where $w\_{ij}$ is the regular expression representing the set of labels of edges from $q\_i$ to $q\_j$ 2. Note: for parallel edges there will be that many expressions for that state in the expression. 4. Solve these equations to get the equation for $q\_i$ in terms of $w\_{ij}$ and that expression is the required solution, where $q\_i$ is a final state. 3. Ignore trap states while doing above.

I feel $R=Q+RP$ is equivalent to left linear grammar production $R\rightarrow Q | RP$. But I dont know whether I should call $R=Q+RP$ as left linear grammar. But I understand the theorem also holds for right linear grammar (if you allow me to call it that for convenience) production also; i.e.

> $R = Q + PR$ has a unique solution $R = QP^\*$

Now I have came across two problems, one which uses right linear grammar, other using left linear grammar.

> **Problem 1 (Using right linear grammar)**
> Given:
> $\Sigma=\\{0,1\\}$
> $X\_0=1X\_1$
> $X\_1=0X\_1+1X\_2$
> $X\_2=0X\_1+\\{\lambda\\}$
> Give the regular expression representing strings in $X\_0$.
>
> **Solution 1 using Arden's theorem**
> $X\_1=0X\_1+1X\_2$
> $=0X\_1+1(0X\_1+\lambda)$
> $=0X\_1+10X\_1+1)$
> $=(0+10)X\_1+1$
> $=(0+10)^\*1$ (By Arden's theorem)
> $X\_0=1X\_1$
> $=1(0+10)^\*1$
>
> **Solution 2 by drawing automaton**
> The automaton can be drawn for given equations as follows:
> Regular expression for automaton = answer for the given question $=1(0+10)^\*1$

---

> **Problem 2 (using left linear grammar)**
> Given:
> $\Sigma = \\{a,b\\}$
> $X\_0=\epsilon + X\_0b$
> $X\_1=X\_0a+X\_1b+X\_2a+X\_3a$
> $X\_2=X\_1a+X\_2b+X\_3b$
> Give regular expression for $X\_1\cup X\_2$
>
> **Solution 1 using Arden's theorem**
> was not given. So I tried to solve myself. First thing I noticed was that I can fully ignore $X\_3$ as its equation was not given. I felt its unreachable state which is somewhat backed by solution given below using automaton (but the steps listed above in application of Arden's theorem only talks about trap state in last step, not unreachable state). But I was not able to solve this using Ardens theorem. So, I analysed the equations. In problem 1, $X\_2$ is defined in terms of $X\_1$. So we were able to put value of $X\_2$ in $X\_1$. So we were able to get $X\_1$ in terms $X\_1$ itself which can be reduced to regular expression using Arden's theorem. That doesn't seem to be the case here, as $X\_1$ and $X\_2$ are defined in terms of each other.
>
> **Solution 2 by drawing automaton**
> The automaton can be drawn for given equations as follows:
> Regular expression for automaton = answer for the given question $=b^\*a(a+b)^\*$

After going through all these, I have bunch of related questions:

1. **Which is the initial state?**
"Using Arden's theorem" section says $q\_1$ is initial state and $q\_1$ has $\epsilon$. So I feel that the variable which has $\epsilon$ added (ORed) to its equation, is starting state.
2. **Which is final state?**
Again "Using Arden's theorem" section says we solve for final state. So I suppose the variable for which we have been asked to solve for in the question, turns out to be the final state. Right? (Problem 1 asks to solve for $X\_0$, so the solution 1 for problem 1 solves for $X\_0$. Problem 2 asks to solve for $X\_1\cup X\_2$ and in solution 2 of problem 2, $X\_1$ and $X\_2$ are depicted as final state.)
3. **How do I solve problem 2 which using Arden's theorem?**
Problem 2 asks for solution of union $X\_1\cup X\_2$. What does it means to solve for union of two variables in the context of Arden's theorem? How can I solve it?
4. **Is it right to draw automatons the way they have drawn?**
In problem 1, each equation gives transition (in automaton) going out of the state corresponding to the variable on LHS. In problem 2, each equation gives transition (in automaton) coming inside the state corresponding to the variable on LHS. Is this right to do?
5. **Which one is trap state (and unreachable)?**
Is it correct to interpret variable for which no equation is given as a trap state? For example in problem 2 (left linear), equation is given for $X\_3$, so it turned out to be unreachable state. But if such variable (for which no equation is given) was given in problem 1 (right linear), I guess, it would have been trap state (no transition emitting out from the state corresponding to that variable). Can we ignore both?

# Answer
Well, all doubts rose because standard reference (Ullman and Peter Linz) books I have, do not speak anything about Arden's theorem. I learnt it from some online resources earlier.

I have another book from local publication which have this topic (poor theory but good number of examples). I should have checked it earlier. But being local publication, I barely check it. Anyways, trying to answer my own questions:

1. I was correct with the fact that the variable having $+\epsilon$ in its equation corresponds to the initial state.
2. I was correct with the fact that the variables for which the question asks to solve is indeed the final state.
3. I will give the full solution after answering 5th question
4. I dont feel drawing automaton in the way they have done is wrong. They makes sense, does conform with regular expressions formed by Arden's method. Its just that finding right linear examples in some sources and left linear examples in other sources confused me. No source explained me both. So was anxious whats correct or both correct. Turns out that both are just fine.
5. The point I made about trap state and unreachable state makes sense to me now and feels correct.

**Answer to question 3 - solving problem 2**

$X\_0=\epsilon + X\_0b$ ...equation(1)
$X\_1=X\_0a+X\_1b+X\_2a+X\_3a$ ...equation(2)
$X\_2=X\_1a+X\_2b+X\_3b$ ...equation(3)

$X\_3$ is unreachable. So deleting it from both equation (2) and (3).

$X\_1=X\_0a+X\_1b+X\_2a$ ...equation(4)
$X\_2=X\_1a+X\_2b$ ...equation(5)

Applying Arden's theorem to equation(1), we get

$X\_0=\epsilon b^\*=b^\*$ ...equation(6)

Substituting value of $X\_0$ from equation(6) in equation (4), we get

$X\_1=b^\*a+X\_1b+X\_2a$ ...equation(7)

Applying Arden's theorem to equation(3), we get

$X\_2=X\_1ab^\*$ ...equation(8)

Putting value of $X\_2$ from equation(8) to equation(7), we get,

$X\_1=b^\*a+X\_1b+X\_1ab^\*a$
$X\_1=b^\*a+X\_1(b+ab^\*a)$
$X\_1=b^\*a(b+ab^\*a)^\*$ ...equation(9)

Applying Arden's theorem to equation(2), we get

$X\_1=(b^\*a+X\_2a)b^\*$ ...equation(10)

Putting equation(10) in equation(5),

$X\_2=(b^\*a+X\_2a)b^\*a+X\_2b$
$=b^\*ab^\*a+X\_2ab^\*a+X\_2b$
$=b^\*ab^\*a+X\_2(ab^\*a+b)$

Applying Ardent's theorem, we get

$X\_2=b^\*ab^\*a(ab^\*a+b)^\*$ ...equation(11)

Desired solution $=X\_1+X\_2$

Applying newly found values from equation(9) and (11), we get,

$X\_1+X\_2=b^\*a(b+ab^\*a)^\*+b^\*ab^\*a(ab^\*a+b)^\*$

> **That's it how far I am able to reach. I still need to know if Arden's theorem can reduce this regular expression to $b^\*a(a+b)^\*$. Or I have to explicitly apply regex identities. If yes, I am unable to do it and reduce that long regular expression to $b^\*a(a+b)^\*$. Can someone help?**

All I have done is to check some more examples from that book (book explained theory poorly but have a lot of examples) by local publication and I have come up with opinions which I feel are correct. Of course I am still a bit hesitant to say I am fully confident about above as I have not checked any reference book explaining the same in detail. Will love if anyone points out any mistake.
> 1 votes

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


# Question
Title: Why must a Turing Machine that Repeats the Same Configuration Twice be in an Infinite Loop?
I have seen the following statement, and I don't quite understand the reasoning behind it:

> If a Turing machine repeats the same configuration twice, it must be in an infinite loop.

I thought that a $TM$ can be in a state $q\_1$, with the tape on the left 000 and on the right 111. Let's say it moves right and then left, staying in the same state; aren't we in the same configuration?

# Answer
This is because the transition function $\delta$ of a TM is deterministic. If the configuration is the same, then the arguments of $\delta$ are also the same, resulting in an infinite loop. Formally, this can be proved like @gnasher729 does.

Let's consider your example. If your $TM$ moves like the following,

$$ (q\_1, \dots00\[0\]111\dots) \xrightarrow{q\_1, \text{right}} (q\_1, \dots000\[1\]11\dots) \xrightarrow{q\_1, \text{left}} (q\_1, \dots00\[0\]111\dots) $$

then the last step equals the first one, which means an infinite loop.
> 14 votes

# Answer
If your Turing Machine is in some state X after n steps, and again in the exact same state X after n+m steps, then it will repeat exactly the same actions from step n+m that it executed at step n, and after step n+2m it will be in state X again, same after step n+3m, n+4m and so on. So you are in an infinite loop.

Your example was a case where you reached the same state again after two steps, so m=2.
> 7 votes

# Answer
A version of @nekketsuu 's answer with no symbols, arrows or Greek:

A machine's configuration determines what it does next (and inductively, determines its entire future). Thus if what happens after a certain configuration is that you reach it again with some more steps, this will go on happening again and again to no end.

This is true for any *deterministic* machine: Turning machine, (Deterministic) Finite Automaton, (Deteriministic) Stack Automaton etc.
> 5 votes

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


# Question
Title: Finding all edges on any shortest path between two nodes
Given a directed weighted graph with non-negative weights, how can I find all edges that are a part of any of the shortest paths from vertex X to Y?

In the example below the yellow edges are the solution for finding the shortest path between A and D (note that other examples may have more than one path).

I know how to find all *nodes* that are a part of a shortest path so I thought that all edges that sit between two nodes which are both on a shortest path means that the edge between them is also a part of the shortest path, but that is not true.

Any ideas would be appreciated.

# Answer
Off the top of my head, you could do this. (Let's say you want to find all edges on a shortest path from $s$ to $t$.)

* Run an All-Points Shortest Path (APSP) algorithm to store the shortest-path distances from every node to every other node
* For every edge $a \rightarrow b$ in the graph:
    + Add up the distance from the $s$ to $a$, and the weight of the edge, and the distance from $b$ to $t$
    + Compare this sum to the distance from $s$ to $t$
    + If it's the same, this edge is part of a shortest path

This runs in $\Theta(E)$ plus the time for the APSP, which is $\Theta(V^3)$ using Floyd-Warshall. The space complexity is $\Theta(E)$ for the final results plus $\Theta(V^2)$ for the APSP.

EDIT: D.W. has pointed out an even more efficient algorithm. Instead of using APSP, use SSSP and SDSP (Single Source/Destination Shortest Path) once each, since you only need the distance from $s$ to everything, and from everything to $t$. This reduces the additional space to $\Theta(V)$, and the time to $\Theta(E+V \log V)$ using Dijkstra (assuming there are no cycles of negative weight).
> 10 votes

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


title: Stacking Boxes in topological order

text:
# Question
Title: Stacking Boxes in topological order
recently i was solving a programming question on uva judge Stacking boxes
link to the problem : https://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&category=3&page=show\_problem&problem=39
EXPLANATION PART
consider a box with n-dimension and there are k different boxes with n dimension each
so the task is simple we have two insert one box into another and we have to find maximum number of boxes which can be inserted one after the another rotation is also allowed around different axis
for example there are 4 box with 2 dimension
5 2
1 1
5 8
3 2
so the boxes 1 can be rotated and can be inserted into 3 and 2 can be inserted into 1 so the maximum is 3
i have a question that why topological ordering works here why not normal sorting works what i did was first i sorted all the edges of one boxes in increasing order and then sorted all the boxes in increasing order based on their first index and after that i calculated the longest increasing subsequence

# Answer
Standard sorting algorithms assume a *total ordering*: given any two elements, the first is either greater than, equal to, or less than the second. (And this relationship has a few other useful properties, like transitivity.)

However, what you have here is only a *partial ordering*. Given two boxes, the first might fit into the second, or the second might fit into the first, or they might be the same size…or, neither might fit inside the other. (10, 1) and (2, 5) fall into this last category.

Standard sorting algorithms will choke on this. But topological sorting only needs a partial ordering, and is also more efficient (running in linear time instead of linearithmic). So it's the right tool for the job here.
> 0 votes

---
Tags: graphs
---


title: Detecting isthmuses on digital curves

text:
# Question
Title: Detecting isthmuses on digital curves
Consider a digital curve, i.e. a sequence of points at integer coordinates, with unit taxicab distance between them.

I want to find the isthmuses, i.e. sections of the curve that are close to each other (within a fixed threshold), though the indexes ("curvilinear" abscissa) differ by a large amount. For a curve of length $L$, there are $O(L^2)$ inter-pixel differences, but the size of the answer does not exceed $O(L)$.

Can you advise an efficient procedure ?

---

**Update:**

I believe that the following approach might be effective: we can sort the points on their $x$ abscissa using histogram sort, in time $\Theta(L)$, while keeping the corresponding index with them. Then for any point $(x\_0,y\_0)$, the possible close neighbors are found in the range $x\_0-D\le x\le x\_0+D$.

Assuming that a vertical line hits the curve $I$ times on average (for ordinary curves, $I$ will be a little more than $2$), the total effort will be at worse $O(LDI)$. Given that the intersections are found on the curves and change little from column to column, I suspect that by some incremental process, the dependency on $D$ could be lowered. Maybe also an auxiliary sort on $y$ can help.

# Answer
> 3 votes
Divide the image up into evenly sized grid cells. Have one hash bucket per grid cell, and hash each point on the curve into the grid cell it falls in. Sort all of the elements in each grid cell / bucket by the order of their abscissa. Then, you can iterate over all of the non-empty grid cells, and for each, iterate over their sorted list to look for an instance of a large gap. Each isthmus will correspond to a pair of adjacent elements in the sorted list that have a large difference in their abscissa.

You should probably do this do this four times: once with the original grid; again with that grid moved by one-half to the right; again with it moved one-half down; and again with it moved one-half to the right and one-half down. If you use grid cells of side length $2D$, then this ensures that if the distance of the isthmus is $\le D$, it will be detected during one of these four iterations.

---
Tags: algorithms, discrete-mathematics, digital-curve
---


# Question
Title: Computing a histogram with the number of extant values not known in advance
(This may be more fitting for CSTheory, I'm not sure.)

I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for the following problem:

## Unknown-Number-of-Bins Histogram

**Inputs:**

* An array of integers $a$, of length $n$.

**Outputs:**

* An array of integers $\text{bins}$ of length $m \<= n$.
* An array of unsigned integers $\text{counts}$, also of length $m$.

**Output Requirements:**

* For every $i \in \\{0...m-1\\}$ it must be the case that

$\bigl|\bigl\\{ j \in \\{0...n-1\\} \mid a\_j = \text{bins}\_i \bigr\\}\bigr|$ $ = \text{counts}\_i$

In other words, $\text{bins}$ and $\text{counts}$ constitute a histogram of $a$, with one bin for every unique value in $a$.
* It is **not** required for $\text{bins}$ or $\text{counts}$ to be sorted.

**Other Notes:**

* Complexity is considered as a function of **both $n$ and $m$**.
* Low time complexity is required both asymptotically and for relatively low values of $m$ - but it is *not* required for low values of $n$.
* No hiding monstrosities in the $\mathop{O}(\cdot)$ constants please! This should be usable in practice.
* A parallel(izable) approach? You are most welcome :-)
* Low space complexity is a plus.
* Deterministic algorithms preferred, and barring that, go easy on those coin flips.

Clearly, there are many way to go about this, some very straightforward, e.g. "sort the input, then build a sorted histogram in a single pass", in $\mathop{O}(n \log{n})$ time. Of course I'm interested in something better....

# Answer
> 3 votes
Often, in order to improve a sorting-based algorithm from $O(n\log n)$ to $O(n)$, one can use hash tables. In this case, you would use a hash table of size $O(n)$. Each entry of the hash table would store an integer and its count. The entire algorithm would now run in expected time $O(n)$.

# Answer
> 1 votes
The problem seems poorly posed. In particular, the following seems to be a trivial solution: choose the bins in advance so that one bin covers the entire array and the remaining $m-1$ bins will not have any elements in them. For instance, you could scan the array once to find the smallest and largest elements of the input array, $\alpha$ and $\beta$; then make one bin cover $\[\alpha,\beta\]$, and the remaining $m-1$ bins cover other intervals that don't overlap with the input (e.g., $\[\beta+1,\beta+2\]$, $\[\beta+3,\beta+4\]$, ...). Now it is easy to output the counts: the bin $\[\alpha,\beta\]$ has count $n$, and the remaining bins have count 0.

This trivial solution runs in $O(n)$ time. It is parallelizable, deterministic, and has no nasty constants hidden in the big-O notation. The space complexity is $O(1)$. You can even make it a streaming algorithm. However, it's probably not very *useful* in practice.

If this is not what you wanted, then it looks like your set of requirements were not stated precisely enough.

# Answer
> 0 votes
Not a great solution, but an improvement - it seems - over @YuvalFilmus' approach:

* Gradually guess the value of m, increasing by a constant factor each time (say by 2);
* For every guess m', use an $O(m')$-bucket hash table (perhaps it would need to be $\Omega(m' \log(m'))$ considering the union-bound on the requirement of the hashing going well).
* Start computing the histogram, while also summing up hash bucket sizes; if you get a hash bucket that's too large (say \> $c\_1 \log(m)$), or the average bucket size is too large ($\> c\_2$) then clear the hash table and proceed to the next guess.

This should do the trick with a hash table with O(m log(m)) buckets, and average bucket length below $c\_2$ - so the time complexity would be $O\left(n + m \log^2(m)\right)$ and the space complexity $O(m \log(m))$. I'm not absolutely sure about te choice of the extra log factor - perhaps we can make do with less than that.

However, I really don't like this solution as something to use in practice. It feels like the artificial construct of a theoretician...

---
Tags: algorithms, combinatorics, integers, counting
---


# Question
Title: Polynomial by the size of the output and the input
I wounder why the complexity of algorithms always depend on the size of the input, but not on the size of the output.

For example, in a problem that I have solve, the size of the input is exponentially smaller than the size of output. In addition, the complexity of the algorithm is polynomial by the size of the output, and pseudo-polynomial by the size of the input.

I think that in such case, the complexity of algorithm is said to be "polynomial", but I am not sure about it.

What are your opinion?

# Answer
> 1 votes
> I wonder why the complexity of algorithms \[does not\] depend on the size of \[...\] the output.

But it does!

The size of the input is often used as a trivial lower bound on the running time ("you need to write the output"). So trivial, indeed, that it's rarely talked about in introductory courses. There, the output is usally not the dominating factor so it's not interesting to discuss is further.

Think about what that would mean on the intuitive: an algorithm that writes more bits than it takes time to compute them. That doesn't seem very efficient in itself; maybe your output encoding is bad.

That said, you do on occasion encounter runtime analyses where characteristics of the output appear in the determined bounds. Search and enumeration algorithms, for instance, can admit non-trivial bounds the separate them from brute force ("I don't have to check all candidates, but only at most three times the number of those I want to find").

# Answer
> 0 votes
It doesn't always depend on input size. In the subject of Kolmogorov complexity and other information theory problems (using computability theory to describe how much information is in data) the relevant counting is often in reference to the output instead. Example, a string of length $n$ which can be output by a Turing Machine given an input of length $\log n$ would be a demonstration of the output having been compressed to a modest amount of information which when given as input produces the desired output. Your "zip file" if you like. Evidently the definition here prefers one begin with the output size and model the possible input sizes. For example, a string is Kolmogorov-random if it takes a longer string of input to produce the output.

---
Tags: time-complexity
---


title: Parse Trees and Operator Precedence

text:
# Question
Title: Parse Trees and Operator Precedence
I have the following basic BNF grammar:

```
<A>   -->  <id>  = <E>
<id>  -->  A | B | C | D | F
<E> --> <E> + <T> | <T>
<T> --> <T> * <F> | <F>
<F> --> <E> | <id>

```

Operator (\*) should have higher precedence over (+). However, see this statement:

```
A = A + B + C + D * F

```

The leftmost derivation (and parse tree) indicate the opposite! i.e., (+) has higher precedence than (\*) since it will show up lower in the parse tree!

What am I missing here?

# Answer
> 1 votes
Due to the path

```
<E>  ->  <T>  ->  <F>  ->  <id>,

```

you can completely circumvent the "check" for whether there are `*`.

Think about it in a bottom up manner: only if there's no `*` nearby can you parse a `+`.

---
Tags: formal-grammars
---


# Question
Title: How to find splitting point in [0,1] to maximize sum of sign function?
Given two $n$-number arrays $a\_1, a\_2, \ldots,a\_n \in \[0,1\] $ and $b\_1, b\_2, \ldots,b\_n \in \[0,1\] $. We would like to find the real number $x^{\*} \in (0,1)$ s.t:

$x^{\*} =\arg\max\_{x} \sum\_{i=1}^n \mathrm{sgn} \big( (a\_i-x) (b\_i -x)\big) $

Where $\mathrm{sgn} = 1 $ if $x \geq 0$ and $\mathrm{sgn} = -1$ if $x \< 0$

This question raised from my research work. I am looking for an efficient way to determine value of $x$.

# Answer
WLOG, let $a\_i \< b\_i$. Then $(a\_1 - x)(b\_i - x) \geq 0$ when $x \leq a\_i \vee x \geq b\_i$.

Keep a list of intervals $I$. For each $a\_i , b\_i$ add $(0, a\_i\]$ and $\[b\_i, 1)$ to the intervals. Now you just find point $x$ such that it lies within the most intervals in $I$.
> 2 votes

---
Tags: optimization, combinatorics
---


# Question
Title: Find coverage for plane from half-planes
The document (see pic. below) states that it is possible to find a cover of the plane by a subset of 3 half-planes. It proposes to use linear programming for this. How to formulate such a program?

The original document can be found here: On the Separation of a Polyhedron from Its Single-Part Mold.

EDIT: For clarity: i need to understand how can i use LP to find subcoverage of size 3 from coverage of bigger size.

# Answer
> 2 votes
I believe the connection between Helly's theorem and linear programming stems from this paper:

> Amenta, Nina. "Helly-type theorems and generalized linear programming." *Discrete & Computational Geometry* 12, no. 3 (1994): 241-261. (Springer link.)

This arose from Nina Amenta's Ph.D. thesis (PDF download), under the direction of Raimund Seidel.

---
Tags: computational-geometry, linear-programming
---


# Question
Title: Both a language and its complement are not context free
Is there a language $L \subseteq \\{a\\}^\*$ such that both $L$ and its complement are not context free?

# Answer
Yes, there is. Consider the language $L = \\{a^p \mid p \text{ is prime}\\}$ which is not contextfree, neither is its complement. Both statements are very easy to check via Pumping-Lemma.
> 2 votes

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


title: Is De Bruijn Graph Hyper-cube?

text:
# Question
Title: Is De Bruijn Graph Hyper-cube?
I do not know if I miss something in the definition of a hyper-cube, but as far as I understand, Hyper-cube graphs have 2^n vertices and if written in binary form, "one-bit difference" strings of numbers are linked with an edge.

From this definition, De Bruijn graph does not look like it is a hyper-cube, because 000 and 010 for example, are not adjacent.

# Answer
> 7 votes
No. I was writing an answer based on vertex and edge counts, but then I realised that there's a simpler argument: the de Bruijn graph of strings of length $n$ over an alphabet of $m$ symbols has $m$ self-loops, whereas a hypercube has none.

---
Tags: graphs
---


title: Asymptotic Time Analysis for BFS Tree

text:
# Question
Title: Asymptotic Time Analysis for BFS Tree
Suppose I want to broadcast from my root to all the nodes in a BFS tree. What is the time complexity of this process? I know that it is suppose to be proportional to the depth of the tree, like O(Depth). A more formal way of saying this could be O(Diameter) or maybe O(Radius of the Root) if you want to be more specific.

However, these parameters do not provide any insight. O(Depth) or O(Diameter) could be O(n) if the tree were a line. Since BFS is not guaranteeing a balanced tree or a binary tree or whatever, it does not give any topological clue to me.

Should I say O(n) then? Or should I say O(Depth) to give a more precise answer?

# Answer
> 1 votes
You can say whatever you want as long as it is accurate. Both $O(n)$ and $O(\text{Depth})$ are accurate, so you can say either one. $O(\text{Depth})$ is more descriptive, since $\text{Depth} \le n$ always holds.

I don't know why you don't think it provides any insight; I think it does provide some potentially useful information.

---
Tags: graphs, time-complexity
---


title: P vs NP problem (Student example)

text:
# Question
Title: P vs NP problem (Student example)
Hello dear stackexchangers,

I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-vs-np-problem

> Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

I understand the problem, but in order for the finder to prove he solve the problem, if we take 100 students from 400, how many "incompatible" pairs and how many combinations of 100 students without these pairs should be proposed and generated in order to make something really "probing"? In a polynomial way of course.

Because the statement is not really clear about it, in my humble opinion.

Sincerely yours

# Answer
Formally, this is a special case of the "$k$-independent set problem", and can be stated as follows:

> Given a graph with 400 vertices, can you pick 100 vertices such that no two of them are adjacent?

(A "graph" is a set of vertices (students) and edges (students who are incompatible). Two vertices are "adjacent" if there is an edge between them (they're incompatible).)

You can find easy solutions for some groups of students: for instance, if there are no incompatibilities at all, any choice of 100 students will work. But the difficult problem is solving this *in general*, coming up with an algorithm that can solve it for *any* selection of $k$ students from a group of $n$, with a "polynomial runtime" (which basically means it can be solved reasonably quickly even for large values of $n$).

"Proving" that the problem is solved involves a formal mathematical proof, a way of demonstrating that your algorithm works for any group of students, no matter what the incompatibilities are, no matter how many there are, and takes only polynomial time to run.

Examples won't work as a proof, because no matter how many examples you show, it's always possible that your algorithm would fail on the next one you haven't tried.

If you're actually interested in approaching this problem, the formal problem description explains it more thoroughly. (You will need some mathematical background though.)
> 6 votes

---
Tags: complexity-theory, np, p-vs-np
---


title: Virutalization of peripheral device

text:
# Question
Title: Virutalization of peripheral device
I have this question to answer: "Please shortly explain how an interface virtualizes a peripheral device to the CPU."

I don't really understand what the question is asking for. I know the theory behind virtual memory. I understand that a harddisk can be seen as a peripheral device.

Could the theory behind virtual memory be what the question is asking for or did I totally misunderstand it?

# Answer
"Virtualization" is a broad term that means abstracting away details of the device, and providing a more generic/abstract/higher-level interface or view of the device. Sometimes it involves pretending that you have a simpler virtual device (with simple commands) instead of the complex physical peripheral you actually have (with its messy interface).

See, e.g., https://en.wikipedia.org/wiki/Storage\_virtualization, https://en.wikipedia.org/wiki/I/O\_virtualization, https://en.wikipedia.org/wiki/Virtualization, https://en.wikipedia.org/wiki/Virtual\_file\_system, https://en.wikipedia.org/wiki/Virtual\_disk, https://en.wikipedia.org/wiki/Data\_virtualization.
> 1 votes

---
Tags: computer-architecture, cpu, virtual-memory
---


# Question
Title: How many different strongly connected graphs can be created given n nodes?
Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ending nodes should be considered redundant and not contribute to the total.

For example, if $n$ is 2, we can create only one strongly connected graph, (the 2-cycle.) But if $n$ is 3 then we can create 18 different graphs: 2 with 3 edges, 9 with 4 edges, all 6 with 5 edges and the complete 3-graph.

Is there a known general formula for computing this number for a given $n$?

# Answer
> 2 votes
This is A003030. Everything known about this sequence is listed there.

---
Tags: graphs, combinatorics
---


title: Left quotient finite automata

text:
# Question
Title: Left quotient finite automata
This is very unclear to me. I understand what the left quotient is, however, can someone explain this:

A={0,101} B=01,10,001}

then how is A\B={1,01}

I mean where are these strings extracted from? I dont see them in A. How can I appeand 01 to anything is B to get something in B?

# Answer
By definition, $A \backslash B$ is the set of all strings $x$ such that $ax \in B$ for some $a \in A$. In our case, $1 \in A \backslash B$ since $01 \in B$ and $0 \in A$, and $01 \in A \backslash B$ since $001 \in B$ and $0 \in A$.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Is Loop Invariant Proof a form of Induction?
As far as I see, what computer scientists refer to as loop invariant proofs are exact replicas of induction proof. Is it true? Can I state that loop invariant proof implies an induction? Is there a theoretical difference?

# Answer
Good question. I think yes, a loop invariant proof implies induction. However, it also deals with the termination step which is outside of the scope of induction. So a loop invariant contains an induction proof, but goes beyond that, and so an induction proof does not do all that a loop invariant proof does.

> (1) Here, showing that the invariant holds before the first iteration is like the base case, and showing that the invariant holds from iteration to iteration is like the inductive step.

---

---

---
> 2 votes

---
Tags: proof-techniques, correctness-proof, induction, loop-invariants
---


# Question
Title: Where do you exactly use data structures?
I know what data structures is, How it works & importance of it. I just have some doubts on where do we actually use it.

When **database can do filtering, fetching, sorting efficiently**, Why we need to use data structures in db data?

I was working on a project which uses Cassandra database. In that I'd to filter data based on two fields. The two fields are indexed. But I can't filter it as it will force me to use **Allow filtering** but It's not a recommended one.

In this case I thought to **fetch rows filtered by one *indexed column*** & **rest by our program** (Java/Python etc) so we need to use better data structure here. ***Is this a correct approach?*** If not what's the solution for these kind of problems?

Let's assume *I've **billions of list of string data in a db table***, I want to use it for *autocomplete* for that it's better to use ***tries data structure***, How can I do this? fetch all data into memory and process?

If my approach is wrong, Are data structures mainly used for ***in memory*** data?

# Answer
> 1 votes
This is a broad question but will attempt to answer.

From my understanding of your question, you have billions of strings which you want to use for autocomplete.

The way most typical autocomplete examples work is you load the entire set of strings into memory and build a trie. That works well for small datasets like the list of countries, or a small list of tags.

Searching for how google implements its autocomplete doesn't return any results, but that would be sort of what you're asking I'd think.

What I imagine is slow in your current implementation is, you have billions of rows in your database, with a column containing the string of interest. Then you are just doing a `LIKE` search to match substrings. So it has to scan every string in the billions of records, which is very slow.

The (typical relational) database won't offer you much support here.

One solution to this problem is to use a "full text search database" such as Lucene. The problem this solves is indexing. Another related index that might help is an inverted index. An inverted index might use a B+tree for indexing the terms (words perhaps) in documents (or strings in your case). But this just means it will match individual terms/words, not complete sentences or exact substring matches like the `LIKE` query will do.

So you have to decide how you want your autocomplete to work. If they can search for exact strings in the text, then the best solution is probably to create a gigantic trie for all the strings. If the trie doesn't fit into main memory, as probably is your case, then you could potentially try creating a string b-tree data structure instead of a trie. This is better as an on-disk data structure. If instead they can search for tokens/terms/words like a keyword search, then you can use an inverted index B-tree, such as with Lucene. Either way you will need another data structure on top of the relational database, and probably one that efficiently works with a file system.

---
Tags: algorithms, data-structures, databases, big-data
---


title: How to model and solve this problem?

text:
# Question
Title: How to model and solve this problem?
I have a matrix $P \in M\_n(\mathbb N)$, where

$$ P = \begin{bmatrix} 0 & P\_{12} & \ldots & P\_{1n}\\ P\_{21} & 0 & \ldots & P\_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ P\_{n1} & P\_{n2} & \ldots & 0 \end{bmatrix}$$

with $P\_{ii} = 0$ for all $i \in \\{1,2,\dots,n\\}$. I need to find matrices $A, B \in M\_n(\mathbb N)$ that satisfy $A + B = P$ and that satisfy the following constraints

$$\forall i\in \[\\!\[ 1,n\]\\!\] \sum\_{k=1}^{n} A\_{ik} = \sum\_{k=1}^{n} A\_{ki}$$

such that $\sum\_{i=1}^{n} \sum\_{k=1}^{n} A\_{ik}$ is **maximized**.

I need to implement an algorithm to solve this problem. On my input data I have approximately: $ n = 16 $ and $ \sum\_{i=1}^{n}\sum\_{k=1}^{n} P\_{ik} = 60000 $ so the brute-force approach is out of question. I don't know what could be a good approximation algorithm so my current approach is to reduce the problem to a binary integer programming problem and then apply Branch-and-Cut but I have serious doubt on it effectiveness for this specific problem.

Finding the optimal solution in polynomial time would be perfect (not sure if it's possible), but I can satisfy myself with a good approximation algorithm. Not having a strong background in CS I'm a bit confused, help would be greatly appreciated !

# Answer
Choose a modelling language, like JuMP, and solve it as a MILP.

An attempt I made with CPLEX solves a random instance ( $n=16$, $max(P)=60000$ ) to optimality almost instantly.

I've implemented the following

$$ max(z)$$ $$ z = \sum\_{i=1}^n\sum\_{k=1}^n A(i,k) $$

$$ \sum\_{k=1}^n A(i,k) =\sum\_{k=1}^n A(k,i)\quad \forall i \in \[1,n\]$$ $$ A(i,k) + B(i,k) = P(i,k)\quad \forall (i,k) \in \[1,n\] \times \[1,n\]$$

$$A\in\[0,max(P)-1\]^{n\times n}\subset\mathbb{Z}^{n\times n}$$ $$B\in\[0,max(P)-1\]^{n\times n}\subset\mathbb{Z}^{n\times n}$$
> 2 votes

# Answer
Barring an optimal solution, you could choose $A\_{ij}= \min(P\_{ij}, P\_{ji})$. This is guaranteed to follow the constraints, except it will not always maximize the matrix $A$.
> 0 votes

---
Tags: optimization, combinatorics, integer-programming
---


# Question
Title: What's the difference between Process Context and Process Control Block?
I know that Process Context is something that is stored when a process is preempted, containing all the necessary info to restart the process at a later time.

I also know that the Process Control Block(PCB) contains all the necessary attributes of the process.

So, does that mean that the Process Context is a part of the PCB? Or is it the other way around? Or are these separate all together? Please help me understand where one ends and the other begins - as well as how they're used together.

What exactly is a process boundary?

Also, how is the PCB affected during a context switch (if at all)?

# Answer
> 4 votes
I think you are confusing the concepts of threads and processes.

**Threads (aka tasks)**
Processes do not get pre-empted, only threads get pre-empted.
A process can contain one or more threads which may run concurrently and/or time-sliced.
As long as there are current threads in the process (some or all of which made be paused) it is said to be running. When the last thread ends the process terminates. When a process is terminated forcibly by the operating system all its threads are terminated as well.

**Process control block**
The `Process Control Block` is the collection of information needed to define a process. In modern OS'es processes are (more or less) isolated and run in their own memory space.
The term `process control block` is not actually in use by any operating system and the various info needed to control a process is not actually stored in a single structure, as such the term is not all that helpful.

**Threads are confined to a process**
All threads inherit their properties from the process and have little room to alter these. It is the programmer's responsibility to make sure threads do not step on each others toes. Unlike processes there is no isolation between threads inside a process other than a dedicated stack and thread local storage.

**Thread context**
A thread context is **not** part of the PCB.
A thread context is simply a dumb of the current machine state (mostly CPU registers) before the thread was interrupted, in additon every thread gets its own dedicated stack and thread local storage.
The context a thread runs under can only be understood in terms of the process state (as defined in the PCB).
E.g. memory addresses inside process X do not make sense outside that process.

**Process isolation**
I've never heard of `process boundary`. I'm assuming you mean `process isolation`.
Every process runs in its own virtual address space and gets access to virtual resources (such as the screen) in such a way that one process cannot access the resources of another process.
In most operating systems this isolation is imperfect and resources in use by other applications can be easily accessed especially when processes have been started with equivalent attributes (e.g. same user id).

> how is the PCB affected during a context switch (if at all)?

The PCB is not affected by a thread context switch.

# Answer
> 0 votes
As you described these are different things.

A Process Context is a run-time information of a particular process at any given time. It's all information needed for OS to restore a suspended process. It's basically CPU registers and process stack. But it's highly dependent on CPU architecture.

A Process Control Block is a group of information about a process for its life time. It includes but not limited to an ID, process relationship (children and parents), privileges, accounting, etc. These are more dependent to what OS provides than CPU architecture.

A process control block is a concept; meaning that you can implement however you want. It can certainly include a region for a process context.

However it's odd to say the other way around: "a process context includes a process control block". Because you don't need to save a process control block on every process switch.

---
Tags: operating-systems
---


# Question
Title: Has the concept of using a hand checked simple theorem prover to validate more complex theorem provers been explored before?
More specifically, has anyone used a chain of theorem provers to validate a highly evolved theorem prover, starting with a very simple hand checked prover such that each new theorem prover is used to validate a somewhat more complex theorem prover, rinse repeat?

This would be something along the lines of induction, I guess. In that you'd have just as much confidence in the complex prover at the end as the hand checked prover you started with.

If it has been explored (wouldn't be surprised), a pointer towards more resources would be welcome.

# Answer
> 3 votes
Not that I know of. A more typical architecture is to decompose the theorem prover into a *prover* plus a *proof checker*. Then only the proof checker needs to be validated. If proofs are expressed in a simple enough language, then the proof checker might be extremely simple. All of the smarts can go into the prover (which tries various strategies to try to find a valid proof), but it doesn't need to be validated, since its output will always be checked by the proof checker.

---
Tags: automated-theorem-proving
---


title: Automatically merging relational data

text:
# Question
Title: Automatically merging relational data
# Background

Semiautomated file merging is a critical part of version control systems (all the ones I've used anyway!). This is usually accomplished on textual source code without the tool understanding the underlying language – although semantic merging also exists.

I'm interested in whether merging *relational* data has been researched, and what the findings have been.

Specifically, I'm imagining that a single relational database is "forked" in to two (or more) independent copies. That independent changes are made to these copies, and that we then want to recombine these databases in to one again, which reflects the changes in each.

# What this question isn't

I'm not asking a question about specific technologies here, although that would be interesting. I'm definitely not asking about SQL based technology sepecificaly. I'm also specifically interested in relational data, and *not* tree data like XML, JSON, or ASTs, etc.

I'm also not asking about integrating heterogeneous databases or information stores, which seems to be the subject of Data integration. For the purposes of this question, it can be assumed that the databases will have the same schema and this doesn't change.

# Some ideas about how this might work

Relational data is, basically, sets. Sets, in principle, have (several) sensible merge semantics, even when the common base isn't known, such as for a commutative replicated datatype set.

There are obviously some basic issues, such as generating identities. If identities are simple incrementing numbers, then these become extremely hard to merge. This problem seems to be solved by using globally unique identifiers.

Incrementing identifiers seems to be a specific case of a more general problem. It is an example of inserting a new fact in to the database that has been derived from the current state of the database.

In general, I suspect that any fact added to the database that is derived from the existing facts in the database, rather than simply new information collected from the outside world, is a potential source of difficulty during a merge. I wonder if this is a huge problem, or one that can be avoided for the most part by something like normalisation?

For example: if we adjust a balance by looking up the current balance and adding or decrementing, then this is hard or impossible to merge. However, if we store individual increments and decrements, this information is trivial to merge. When we need the balance, we should compute it from the data we've got.

Problems also arise for integrity constraints. Following naive set merging, a primary key may no longer be a primary key. However, it seems like it might be possible to automatically determine where this could happen from the database schema, and then have the user choose a resolution scheme, or default to some sensible one if such a schema exists. Note: it is possible to keep an audit, show conflicts as they arise, and have a user revert a decision later, as is done with version control systems.

# Answer
> 2 votes
> I'm interested in whether merging relational data has been researched, and what the findings have been.

Here are several papers mainly on the tree-to-tree editing problem. A lot of good stuff is related to XML documents.

A record in a database can be considered a simple tree of just a single row of children (the fields) or perhaps extending to the relations the record points to. With that you can do tree diffing/merging using the techniques outlined in these papers, and adding to it any column-specific string diffing techniques.

You could then add extra database-specific heuristics to the diffing system to make it more useful. For example, you have the extra metadata of the schema of the database, which provides a lot of information.

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


# Question
Title: Are there (highly) restricted process calculi? Perhaps similar to formal grammar?
I've started to read about process calculi (such as CSP and π-calculus). It seems to me that they are extremely general and can represent pretty much any concurrent system, many of which will be unable to "make progress".

I wondered if there were much more restrictive formalisms for describing concurrent processes? Perhaps something close to formal languages augmented with a parallel composition (a kind of tensor product of the joined languages) might work quite well? Maybe, in particular a Parsing expression grammar.

Process calculi seem to generally have a concept of channels on which synchronous messages are exchanged. The set of allowable messages are known as the alphabet of a process, and it seems analogous to the symbol set of a formal language (you'd need to augment the symbols with a send and a receive label).

The possible traces of a process calculus would be analogous to the possible strings of a language.

So, **the actual questions**: is there something like this in the research literature? Thanks!

# Answer
> 2 votes
> I wondered if there were much more restrictive formalisms for describing concurrent processes?

Petri nets are IMO more restrictive than the process calculus and such. They are state-transition systems, which are pretty much like formal grammars (like parsing expression grammars). They all boil down to states and rules / transitions. Petri nets include parallel composition.

---
Tags: reference-request, formal-grammars, process-algebras
---


# Question
Title: Merge a set of strings based on overlaps
I have a set of strings that are slices of a single, longer string. It is not guaranteed, however, that any two strings from this set must overlap: only that all of them together overlap. I want to reconstruct the original longer string.

For example, suppose the longer string is LGHFDJGHSJGHDFKSJBSFSHJKADGHS. The slices might be FKSJBSFS, JKADGHS, LGHFDJGHS, SFSHJKA and GHSJGHDFK. I need an algorithm to reconstruct the original LGHFDJGHSJGHDFKSJBSFSHJKADGHS.

I understand that this algorithm may be somewhat probabilistic: given any two strings, the probability that they overlap by pure chance is $\frac{2}{n}$ where $n$ is the size of the alphabet used. I want to find the "best" overlapping longer string.

So far I've asked around and I've been told to look into suffix trees and de Bruijn graphs. I have done so but I can't see how I can apply them to solve this problem. Any help would be appreciated.

# Answer
> 2 votes
This is the DNA sequence assembly problem, an algorithms problem that has been well studied in the literature. You can apparently find entire courses on the subject. In general, the problem is NP-hard. However, there are many algorithms that seem to work well in practice; greedy assembly is one very simple approach, but there are many others.

---
Tags: algorithms, graphs, strings
---


# Question
Title: What is the difference between a scripting language and a normal programming language?
What is the difference between programming language and a scripting language? For example, consider C versus Perl.

Is the only difference that scripting languages require only the interpreter and don't require compile and linking?

# Answer
> 23 votes
I think the difference has a lot more to do with the intended use of the language.

For example, Python is interpreted, and doesn't require compiling and linking, as is Prolog. I would classify both of these as programming languges.

Programming langauges are meant for writing software. They are designed to manage large projects. They can probably call programs, read files, etc., but might not be quite as good at that as a scripting language.

Scripting langauges aren't meant for large-scale software development. Their syntax, features, library, etc. are focused more around accomplishing small tasks quickly. This means they are sometimes more "hackish" than programming langauges, and might not have all of the same nice features. They're designed to make commonly performed tasks, like iterating through a bunch of files or performing sysadmin tasks, to be automated.

For example, Bash doesn't do arithmetic nicely, which would probably make writing large-scale software in it a nightmare.

As a kind of benchmark: I would never write a music player in perl, even though I probably could. Likewise, I would never try to use C++ to rename all the files in a given folder.

This line is becoming blurrier and blurrier. JavaScript, by definition a "scripting" langauge, is increasingly used to develop "web apps" which are more in the realm of software. Likewise, Python initially fit many of the traits of a scripting language but is seeing more and more sofware developed using Python as the primary platform.

# Answer
> 8 votes
The classic article on scripting languages is John K. Ousterhout's Scripting: Higher-level programming for the 21st Century, published in Computer 31 (3), 1998. He drew a distinction between scripting languages, on the one hand, and system programming languages on the other.

Ousterhout characterized *system programming languages* as having evolved to replace machine languages for programming. They hide tedious details like register assignment and subroutine calling sequences, provide simple constructs for writing loops and other common control-flow idioms, and enforce a typing discipline. They are usually implemented by an (ahead-of-time) compiler. These languages are meant for writing software from the ground up. Examples are C, C++, and Java.

In contrast, scripting languages, according to Ousterhout, start from the premise that there already are useful programs out there, usually written in system programming languages. Scripting languages, like Perl, Python, Tcl, Visual Basic, and the Unix shells, provide tools for combining these existing programs into new programs. Ousterhout characterized scripting languages as "typeless" (including what many call dynamic typing), and as emphasizing rapid development; they are usually implemented by interpreters.

Now, one must be careful not to assume that a single author's conceptual model is authoritative. Even though we computer scientists like to pretend we are mathematicians giving precise definitions to all terms, in practice most computing terminology is socially constructed with fuzzy and heterogeneous meanings; there is a rough consensus in a very high level about most terms, but details often depend on who is writing. Thus, take his article, my answer, and all the other answers here with a large heap of salt.

I would personally dispute the existence of a "normal" programming language, as you phrase it in your question. However, I think the concept you are trying to convey corresponds roughly to Ousterhout's system programming languages.

# Answer
> 3 votes
All scripting languages are also programming languages. The converse is not true. Languages that "require only the interpreter" are interpreted languages (as opposed to a compiled language -- note that some languages, such as Java, fall into both categories).

A language being categorized as a scripting language implies that it is useful as a "glue" language. Scripts do not tend to be full-featured programs, but instead fill in the gaps between other pieces of software.

Scripts are usually used to connect multiple programs together, to perform menial tasks very quickly/easily, or even in an embedded environment where performance and safety concerns have been abstracted to a lower level language. Scripting languages emphasis tends to be on reducing development time, hence the reason most are interpreted and very high level.

# Answer
> 1 votes
Set 'scripting languages' is subset of set 'programming languages'. The difference between C and Perl is difference between system programming language and application language and between interpreted language and compiled language.

System programming languages are low-level and oriented toward memory management, predictable IO and so on. Application languages are oriented toward quick resolution of higher-level problems, like 'read setting from file , open socket and process requests according settings'.

Thus, application languages tend to be much higher-level, then system languages, i.e. provide great amount of built-in abstraction and helper facilities and often adds automatic memory management of some sort.

Programs in compiled languages are processed to some code completely before program execution. Scripting languages are translated dynamically in process of execution and often include facilities for dynamic code generation and including files with source code.

Thus, all scripting languages are application languages, but opposite is not true. System languages are always compiled languages, as scripting languages usually include features, that are not pragmatic to implement in terms of the language itself. Note, however, that scripting(interpreted)/compiled difference is more about implementation: for some languages both types of implementations may exist, as for haskell.

# Answer
> 1 votes
A difference I haven't yet seen mentioned is that when used as intended, the execution time of most scripts will be dominated by "macroscopic" operations, and the performance of microscopic operations will not have a significant effect on overall execution time. For example, if a ray-tracing animation program might include a scripting language with a "render image" statement, a script to produce 240 frames of animation might spend four hours in the "render image" statement, and a total of four seconds doing everything else. Even if one were to speed up everything outside the rendering engine by a factor of a million, that would have less effect on overall performance than speeding up the rendering engine by 0.1%.

# Answer
> 1 votes
Others have covered attributes that tend to be associated with scripting languages and with non-scripting languages. That's helpful for getting a feeling about what people mean when they use the term "scripting language", but I feel it's more important to understand that **there is simply no neatly defined boundary:** Two knowledgeable people could disagree about whether a particular language X is a scripting language. The term "scripting language" nevertheless has utility because there is broad agreement about languages that are far inside, or far outside, the boundary.

Compare "family car" vs. "sportscar", or "magazine" vs. "newspaper". I daresay that it would be difficult to come up with a 100% reliable rule to differentiate every family car from every sportscar that is generalisable (meaning that it does not basically amount to enumerating all existing cars in each category) and at least potentially objective (meaning it would be acceptable to everybody). But these terms are still useful in practice, because although there are some cases that are hard to decide, many cars are clearly in one category and not the other.

---
Tags: programming-languages
---


title: Pure type systems and let-expressions

text:
# Question
Title: Pure type systems and let-expressions
I can not find any simple and detailed source of how to add non-recursive let-expressions to pure type systems.

The best I found is the Henk paper by Simon Peyton Jones, but his explanation of this point is very brief.

Can someone link some references about this topic (source code is accepted)?

**EDIT**

The `let` I want to add has the following syntax:

```
let x : T = M in N

```

where `x` is the variable name, `T` is its type, `M` is the expression with which all free occurrences of `x` in expression `N` will be replaced. It can only introduce nested definitions, so recursion is impossible.

In untyped lambda calculus it is syntactic sugar. By analogy it should be equivalent to `(λ(x : T) -> N) M`, but as you know this conversion does not type-check in PTS, so new type rules must be included.

# Answer
> 4 votes
There is a definite dearth of literature on how to add let bindings to PTSes or dependently typed systems, though I do seem to recall this reference:

Paolo Severi, Pure Type Systems with Definitions.

From a theoretical perspective, you want to have the intuitive rule:

$$\frac{\Gamma\vdash t\[M/x\] : A\[M/x\]\qquad \Gamma\vdash M:B}{\Gamma\vdash\mbox{let}\ x :B :=M\ \mbox{in}\ t\ :\ A} $$

But this doesn't help explain much about how to perform type checking and conversion, which is a quite subtle subject.

---
Tags: reference-request, type-theory
---


# Question
Title: Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?
For example: This looks like a context free grammar: → → | → | → | c

but it can be reduced to this regular language: → | → | → | c

I want to know if it is possible or not and why

# Answer
It is not possible: it is undecidable whether a context-free grammar describes a regular language. For a proof, see e.g. *Undecidable Problems for Context-free Grammars* by Hendrik-Jan Hoogeboom.
> 3 votes

---
Tags: turing-machines, formal-grammars, chomsky-hierarchy
---


title: Prove that EXPtime contains PSPACE

text:
# Question
Title: Prove that EXPtime contains PSPACE
How to prove that "EXPtime contains PSPACE"?

# Answer
> 3 votes
Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let $x$ be the input (length $n$) of $M$, and $f(x)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the proposition of $A \in EXPTIME$?

---
Tags: complexity-theory
---