# Question
Title: Can we say DFA is more efficient than NFA?
I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it has only one outgoing edge & there will be no ambiguity. But in case of NFA we have to check all possible cases & that surely takes time. So can we say DFA is more efficient than NFA ?

But, my other part of brain is also thinking that NFA exists only in theory, so we cannot compare it's efficiency with DFA.

# Answer
There are two answers, depending on how you define efficient.

## Compactness of representation

*Telling more with less*: NFAs are more efficient.

Converting a DFA to an NFA is straightforward and does not increase the size of the representation.

However, there are regular languages for which the smallest DFA is exponentially bigger than the smallest NFA. A typical example is $(a|b)^\*b(a|b)^k$ for $k$ fixed.

## Computation

*Running it fast*: DFAs are more efficient.

The computers we use today are deterministic in nature. That makes them bad at dealing with non-determinism. There are two common ways of dealing deterministically with NFAs: backtracking on one side, which is rather costly, or keeping track of the active states, which means each transition will take up to $N$ times longer (where $N$ is the size of the NFA).
> 17 votes

# Answer
In terms of power, they are equivalent as you said and there is an algorithm (subset construction) for converting an NFA to an equivalent DFA. As you might tell from the algorithm's name, it constructs subsets of states of the NFA. If your NFA has $n$ states, the algorithm may output a DFA with $2^n$ states but that's an upper bound. Sometimes, the number of states does not change at all or even reduces. So in practice, it matters less as to which one to use.

DFA matching is linear in the size of the input string. NFA matching involves backtracking so NFAs do more work. Thus, DFAs are more efficient.
> 5 votes

# Answer
Just adding to answers above:

NFAs *can* be computationally more efficient than DFAs, in the sense that they can be simulated on a parallel processor.

BTW: I see people saying that NFAs can't exist in reality. I beg to differ. A computer with a large number of processors can run many tasks in parallel and can be considered as a nondeterministic machine. One could assign each branch of computation to a new processor and halt them all whenever one of them accepts.
> 3 votes

# Answer
If you use the *purely theoretical* "number of steps to accept/reject" measure, a DFA will always be cheaper than an NFA that uses $\epsilon$-transitions. For more complex automata such a measure will make a difference.
> 1 votes

# Answer
As others have noted, you have to define what "efficiency" means. In order to illustrate this, I give a reasonable model with a different answer.

Looking *only* at the automaton model(s), that is ignoring in particular how you would implement them on real machines, the obvious efficiency measure is "number of transitions taken on a (shortest) accepting run".

With respect to this measure, both automata models are *equivalent*, since both take exactly one transition per input symbol (w.l.o.g. we don't have $\varepsilon$-transitions). Note that the size of the considered automata does not factor in here.
> 1 votes

# Answer
Technically speaking a NFA is a more general concept then a DFA, since it is not required to use the nondeterminism. In other words: every DFA is a NFA. From this perspective there is for every language a NFA that is at least as efficient as the most efficient DFA, for whatever efficiency measure you favor.

Other than this I agree with Raphael that it depends very much what you mean with *efficiency* and on the implementation.
> 1 votes

# Answer
As we know about Automata i.e machine which can perform any action without any man power or without direct participation of man. eg: washing machine. Finite Automata means we know the sate of performing task by machine like 1 press ON 2 press OFF so there is only 2 states i.e called finite automata. Now come to DFA i.e deterministic Finite automata. formally mean we can easily determine states there is no ambiguity and informally it need only 1 transition allowed on 1 symbol. NFA: non deterministic finite automata. there is need more time to compute actual state and there is ambiguity andd informally says there is multiple allowed transition on 1 symbol. in the case of time to reach the destination NFA takes more time than DFA but NFA can load more data than DFA. * DFA and NFA has same power to recognize the string. thank you.. Deepali kaushik
> -4 votes

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


title: Width of a String/Line in an Image

text:
# Question
Title: Width of a String/Line in an Image
I have been looking for a method to find the width of a line.

I found the solution(link: http://www.mathworks.com/matlabcentral/answers/88645-average-width-of-lines),

"sum up the image to get the area, then skeletonize the image and sum up that image to get the total length.Then divide the area by the length."

Can anyone please explain the following? 1. what is summing up to get image area? 2. what is summing up skeletoniized image to get length? I did not get this.

I have to find the thickness of a string from a given image. I can take the image of any dimension and quality I want. How do i measure the thickness of a string? That is what I was trying to resemble as width of a line. Essentially, thickness of a string can be thought as width of a line, I think.

Moreover, I can not assign any unit to my measurement i.e., m/cm/mm. So I have to measure some sort of ratio to represent the thickness and reach a decision.

My outcome should be Yes or No based on the thickness. For example, if the thickness is greater that a certain value I would not take the string to process.

The string can be made of anything.

# Answer
> "sum up the image to get the area, then skeletonize the image and sum up that image to get the total length.Then divide the area by the length."

Input images is a binary image, thus either the pixel value will be zero(black pixel) or 255(while pixel).

Summing up the image gives the sum of all while pixels(black pixel are zero).

i.e., the area of whole white line

$Area = Sum/255$

After skeletonizing the image, the thick white lines become almost one pixel thick.

Summing it up will give the approximate length of the line.

Now, as we know the area occupied by the white line and length of the line.

Dividing them will result the **thickness of the line**.
> 2 votes

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


# Question
Title: What is the regular expression of this language?
$\Sigma = \\{0, 1\\}$

$L = \\{x$| $x \in \Sigma^\* $ $\\&$ $ \\#\_0(x) = 3$ $or$ $ \\#\_1(x) = 3 \\}$

What is the regular expression of this language?

At first I thought $r = (0+1)^\*0(0+1)^\*0(0+1)^\*0$ $ or$ $ $ $r = (0+1)^\*1(0+1)^\*1(0+1)^\*1$

And what is it's corresponding NFA/DFA?

I've been puzzled by this language and if it's regular for a while now.

# Answer
> 0 votes
Check RE and FA for finite automata construction.

It has to be regular since we can create Regular Expression for it.

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


title: CFG Equivalent of regular expressions

text:
# Question
Title: CFG Equivalent of regular expressions
So I was wondering something about the Chomsky hierarchy.

DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages.

Right-regular or left-regular grammars produce regular languages, while context-free grammars produce context-free languages.

Regular expressions represent regular languages - but is there a context-free equivalent? i.e. is there some additional term we could allow to appear in a regular expression such that regular expressions with that functionality now represent context-free languages?

# Answer
A (rather technical) answer, where star-operator is replaced by least fixed point (equivalent to recursive formulation as in CFG) is given by our cstheory cousins: Does there exist an extension of regular expressions that captures the context free languages?

The author (Neel Krishnaswami) of that answer does not know an original source of his construction, but a later comment by Tim Schaeffer refers to the 1973 book *Formal Languages* by Arto Salomaa. In chapter VI.11 Salomaa introduces *regular-like expressions*. That book might not be in your possession, but in turn refers to *A characterization of context-free languages*, Journal of Computer and System Sciences, 1973, by Jozef Gruska, which is open access.

The operator Gruska considers is the following, I loosely quote from his paper. Let $\sigma$ be a symbol and $L,L\_1$ be languages. The $\sigma$-substitution of $L\_1$ into $L$, denoted by $L \overset{\sigma}{\uparrow}L\_1$ is defined by

$$ L \overset{\sigma}{\uparrow}L\_1 = \\{ x\_0 y\_1x\_1 \dots x\_{k-1} y\_k x\_k \mid x\_0 \sigma x\_1 \dots x\_{k-1} \sigma x\_k\in L, \text{no $\sigma$ in }x\_i, y\_i\in L\_1 \\}.$$

After noting that he operation $\overset{\sigma}{\uparrow}$ is associative one defines the $\sigma$-iteration as

$$ L^\sigma = \\{z \mid z\in L \cup L\overset{\sigma}{\uparrow}L \cup L\overset{\sigma}{\uparrow}L\overset{\sigma}{\uparrow}L \cup \dots \text{ does not contain an occurrence of } \sigma \\}.$$

Note that if we have only a single variable, like $S\to aSbS \mid \lambda$ then this substitution closure $\\{aSbS, \lambda\\}^S$ is indeed the language generated by the grammar.
> 5 votes

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


# Question
Title: L ={a^n.b^n | n>=0} , what is difference between L^2 and L.L?
which option is correct? please explain why other are wrong if any one is correct

# Answer
> 0 votes
$L^2=L\cdot L$ by definition and $L\cdot L=\\{xy\mid x\in L\land y\in L\\}$. Can you use that to get the answer?

---
Tags: formal-languages
---


# Question
Title: What are some approaches to solve these classes of problems efficiently
Good day,

Please consider the following problem: 3 friends named Alice, Bob and Cindy have 3 food items (cheese, tomato, bread) in the fridge.

Each person has a particular numerical preference score (any positive number) for each food item.

It has been agreed upon that each person should take one and exactly one food item. (cheese bread and tomato can not be broken up to pieces)

we are interested in coming up with a matching that would maximising the total happiness.

Here is a concrete example:

```
Foods Vector: [Cheese, Tomato, Bread]

preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (4,3,3)
Bob   (2,4,5)
Cindy (5,1,3)

brute force: try all combos

//Cheese belongs to Alice, Tomato belongs to Bob, Bread belongs to Cindy...
total score for [Alice,Bob,Cindy]: 11

total score for [Alice,Cindy,Bob]: 8

total score for [Bob,Cindy,Alice]: 6

total score for [Bob,Alice,Cindy]: 8

total score for [Cindy,Bob,Alice]: 12

total score for [Cindy,Alice,Bob]: 13  //best solution

```

It looks like we should give Cheese to Cindy, Tomato to Alice, and Bread to Bob for the greater good of the republic.

Of course the naive brute force method is acceptable here because n=3, however if we have 100 people and 100 food items this method would be prohibitively expensive. it seems to me that n! will be the asymptotic complexity which is worse than exponential.

I attempted to relate this problem to other well known problems like knapsack or Interval scheduling with no success.

I would appreciate informed input on the type of this problem and if there are other approaches to find the optimal or good approximation solution in reasonable time.

I have come up with a greedy algorithm that can do well in some cases, here it is:

```
      Cheese  Tomato  Bread
Alice 4       3       3
Bob   2       4       5
Cindy 5       1       3

```

1- for each Person, find the Food among remaining foods that is preferred, assign that food to the person. 2- eliminate the chosen food from the list of available foods 3- repeat until you are left with the last person

in my going step by step it would look like this:

Step 1:

```
      Cheese  Tomato  Bread
Alice *4      -       -
Bob   -       4       5
Cindy -       1       3

```

Step 2:

```
      Cheese  Tomato  Bread
Alice *4      -       -
Bob   -       -       *5
Cindy -       1       -

```

Step 3:

```
      Cheese  Tomato  Bread
 Alice *4      -       -
 Bob   -       -       *5
 Cindy -       *1       -

```

This will take n steps as opposed to n!, and in this case gives us a reasonable answer (10) but in other situations the discrepancy between optimal solution and greedy solution is huge:

```
preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (3,2,1)
Bob   (9,1,2)
Cindy (5,0,9)

brute force: try all combos

total score for [Alice,Bob,Cindy]:   13

total score for [Alice,Cindy,Bob]:   5  //greedy!!!

total score for [Bob,Cindy,Alice]:   10

total score for [Bob,Alice,Cindy]:   20 //best

total score for [Cindy,Bob,Alice]:   7

total score for [Cindy,Alice,Bob]:   9

```

# Answer
This is an instance of the assignment problem. There are polynomial-time algorithms for solving the assignment problem, e.g., using the Hungarian algorithm (or other algorithms).
> 2 votes

---
Tags: algorithms, approximation
---


# Question
Title: Efficient algorithms for checking non-emptiness of the language of a Turing machine
I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?

# Answer
> 2 votes
The problem is undecidable. There are no algorithms for it, so there are no efficient algorithms.

# Answer
> 0 votes
I assume you are using the very same scheme that is used to simulate Nondeterministic Turing Machine on Deterministic one like here, which uses BFS.
In your case accepted string is found in the same manner, otherwise (like DFS) it would not halt. So essentialy the efficiency of time is bounded by such conversion and you cannot do better, because:

* the existence of polynomial time solution would be equivalent to $NTM$ -\> $DTM$ simulation which is the same as solving $P$ vs $NP$
* any heuristic is in the mean sense worse than BFS

The efficiency of memory might be decreased if you encode your TM (like UTM does) and in the every step use only one at the time (memory efficient, time inefficient). Algorithms like Branch and Bound (with indication that when no heuristic is available use DFS) cannot be used.

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


# Question
Title: Fundamental idea of this memory denial of service simulation using array copy?
I am just watching this lecture Computer Organization - Introduction And Basics where the lecturer mentions about using a simple code to demonstrate how memory denial of service can be simulated in DRAM by exploiting an optimzation DRAM Controller does internally. The optimization seems to be that DRAM Controller serves the same **row buffer** whenever possible for the instructions coming to the pipeline and so it can be exploited by sending instructions that use a very localized data giving it priority.

```
//initialize large arrays A and B

for(j=0; j<n; j++)
{
index = j*linesize;
A[index] = B[index]
}

```

I just wanted to understand the fundamental concept of this approach. The Lecturer says that the above code would copy an Array from `B` to `A`. However I am not sure how it actually would copy an Array from `B` to `A` because it doesn't seem to go over each index item.

My real doubt, assuming that this is just a simulation code which copies some part of `B` to `A` for demonstration purpose and that `linesize` is just a large value to make a `cache miss`, is if the central idea behind this something like:

a) chose an `index` that is **sufficiently** wide apart so that a `cache miss` happens

b) **yet** the memory is **close** enough for it to be in the same `row` for the memory controller to serve from the same `row buffer`

Which is needed to simulate this DoS (denial of service) scenario?

Quoting from the paper that explains this in depth Memory Performance Attacks - Denial Of Service In Multi Core Systems

> The arrays in stream are sized such that they are much larger than the L2 cache on a core. Each array consists of 2.5M 128-byte elements. Stream (Figure 3(a)) has very high row-buffer locality since consecutive cache misses almost always access the same row (limited only by the size of the row-buffer).

# Answer
> 2 votes
The idea is that this code does *not* copy the complete array, but due to the design of the memory hardware it takes just as much time as if it would. Reading and writing a single byte will move a whole cache line. So the code reading and writing does very little work, but causes the memory subsystem to perform a whole lot of work.

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


# Question
Title: Applying Master Theorem to: T(n) = T(n - 2) + n^2
I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation:

T(n) = T(n-2) + n^2

Am I wrong in thinking that I cannot apply Master Theorem to this equation? If it can be applied, I am unsure how, as the variable T(n-2) gives no value for "b" which would usually be used to solve with master theorem.

If it can be solved with Master Theorem, how would it be solved? If it cannot be, how would one go about solving this specific recurrence relation?

Thank you in advance for any help and clarification!

# Answer
Think about what the derivative of T is. If the difference between T (n) and T (n-2) is $n^2$ then the derivative T' (n) is about $n^2 / 2$ and T (n) is about $2/3 · n^3$.
> 3 votes

# Answer
Don't use the Master theorem for this recurrence. Instead, use guess-and-prove, expand a few times and spot the pattern, or express it as a summation.
> 2 votes

# Answer
If in the form:

$T(n) = aT(n-b)+f(n) ,\hspace{0.5cm} if \hspace{0.5cm}n\>1,\hspace{0.5cm}a\>0,\hspace{0.5cm}b\>0,\hspace{0.5cm}k\>=0$

and if $f(n)$ is $O(n^k)$ then

$T(n)=O(n^k) \hspace{0.5cm} if \hspace{0.5cm} a\<1$

$T(n)=O(n^{k+1}) \hspace{0.5cm} if \hspace{0.5cm} a=1$

$T(n)=O(n^k.a^{n/b}) \hspace{0.5cm} if \hspace{0.5cm} a\>1$
> 1 votes

# Answer
This: Solving Recurrence Relations 'Chip & Conquer' helped me solve the relation.
> -1 votes

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


# Question
Title: What kinds of problems are modeled by a recursive definition of a set of strings?
Given this definition:

> The set $\Sigma^\*$ of strings over the alphabet $\Sigma$ is defined recursively by:
> BASIS STEP: $\lambda \in \Sigma^\*$ (where $\lambda$ is the empty string)
> RECURSIVE STEP: If $w \in \Sigma^\*$ and $x \in \Sigma$ then $wx \in \Sigma^\*$

My understanding of this is that the subset $\Sigma^\*$ will expand with each iteration by what appears to be $|\Sigma|^n$ elements where $n$ is the number of iterations. So for example, given $\Sigma = \\{a,b,c\\}$ we have:

1. Base Case: $\Sigma^\* = \\{\lambda\\}$
2. Iteration 1: $\Sigma^\* = \\{\lambda,\lambda a, \lambda b, \lambda c\\}$
3. Iteration 2: $\Sigma^\* = \\{\lambda,\lambda a, \lambda b, \lambda c, \lambda aa, \lambda ab, \lambda ac, \lambda ba, \lambda bb, \lambda bc, \lambda ca, \lambda cb, \lambda cc \\}$

Etc.

If this is the correct interpretation of the data structure described by this recursion, what types of problems are structures like this used to study/prove in CS?

# Answer
> 3 votes
The definition you quote is a formal definition of strings which is particularly conducive to induction. There are many other ways to define strings, for example as sequences of letters, or more exactly as mappings $f\colon \\{1,\ldots,n\\} \to \Sigma$ for some $n \in \mathbb{N}$.

There are several different ways of understanding your definition, which is stated rather informally. The usual interpretation is as a *least fixed point*: $\Sigma^\*$ is the *least* set which contains $\lambda$, and for each $w \in \Sigma^\*$ and $\sigma \in \Sigma$, also $w\sigma \in \Sigma^\*$; here you should think of concatenation as some formal operation, which is perhaps more appropriate to write as (say) $(w.\sigma)$.

What is a *least fixed point*? In this case, it is the intersection of all sets satisfying the two conditions stated above. One can prove that in general, such sets can be constructed just in the way that you describe: start with the empty set, and repeatedly a closure operation $C$, which in this case is $$ S \to S \cup \\{\lambda\\} \cup \\{w\sigma : w \in S, \sigma \in \Sigma\\}. $$ Form a sequence $S\_0 = \emptyset$, $S\_1 = C(S\_0)$, $S\_2 = C(S\_1)$, and so on, and take ${\cal S} = \bigcup\_{n=0}^\infty S\_n$. It is not too hard to show that ${\cal S} = C({\cal S})$, and moreover ${\cal S}$ is the least fixed point.

Another way of thinking of these rules is as a proof system for demonstrating that a certain expression is in $\Sigma^\*$. We have an axiom $\begin{array}{c}\\\hline \lambda\end{array}$ and an inference rule $\begin{array}{c} w \\\hline w\sigma \end{array}$ valid for all $\sigma \in \Sigma$.

A third way is through induction: a property $P$ holds for all $\Sigma^\*$ if $P(\lambda)$ and for all $\sigma \in \Sigma$, $P(w) \longrightarrow P(w\sigma)$. This is how we usually use this definition.

Given this definition, it is possible to define operations on strings and to prove theorems on strings. For example, length is defined by $|\lambda| = 0$ and $|w\sigma| = |w| + 1$, and concatenation by $x::\lambda = x$ and $x::(w\sigma) = (x::w)\sigma$; it is straightforward to prove by induction (on $y$) that $|x::y| = |x| + |y|$.

This sort of definition is common in the more formal parts of computer science. Other parts will prefer the informal definition "$\Sigma^\*$ is the set of all words over $\Sigma$", or more explicitly, "$\Sigma^\*$ is the set of all finite sequences of elements of $\Sigma$".

---
Tags: strings, recursion, sets, mathematical-foundations, inductive-datatypes
---


# Question
Title: What is examples of languages to prove the inclusions between families of languages generated by matrix grammars?
$\lambda M\_{ac}$ = family of languages generated by matrix grammar with appearance checking and with erasing rules

$\lambda M$ = family of languages generated by matrix grammar without appearance checking and with erasing rules

$M\_{ac}$ = family of languages generated by matrix grammar with appearance checking and without erasing rules

$M$ = family of languages generated by matrix grammar without appearance checking and without erasing rules

$RE$ = family of recursive enumerable languages

It is stated in \[1\] that

(a) $\lambda M \subset \lambda M\_{ac} = RE$,

(b) $M \subset M\_{ac} \subset CS$,

(c) $M \subseteq \lambda M$.

$M\_{ac}$ can generate the language $L = \\{a^{2^m} : m \geq 0 \\}$, but $M$ probably cannot (if I'm not mistaken). Thus this yield the (b) above.

What are the examples of languages that can be used to prove the (a) and (c)?

Your shared wisdom, advice or hints are very appreciated.

\[1\] http://aleteya.cs.buap.mx/~jlavalle/papers/rewriting/tarraphd.pdf

# Answer
The paper you link (Grammars with Regulated Rewriting, Jürgen Dassow, manuscript, 2006) gives more hints. Look at Theorem 2. The four types of matrix grammars are equivalent to the (slightly more general) four classes of regularly controlled grammars.

The fact that grammars without appearance checking are strictly less powerful than those with ac seems to have been obtained by Hauschildt and Jantzen. It is a consequence that without ac the languages over a single letter alphabet are regular. Dassow: "*Since the known proofs for statement \[..\] use deep results from the theory of Petri nets \[..\] we omit a proof*".

This should prove strict inclusions in (a) and (b). The inclusion in (c) is perhaps not known to be strict? It is just inclusion in Theorem 1 (iii).

D. Hauschildt, M. Jantzen, Petri net algorithms in the theory of matrix grammars. Acta Informatica 31 (1994) 719–728. doi 10.1007/BF01178731

Abstract. This paper shows that the languages over a one-letter alphabet generated by context-free matrix grammars are always regular. Moreover we give a decision procedure for the question of whether a context-free matrix language is finite. Hereby we strengthen a result of \[Mäkinen, E.: On the generative capacity of context-free matrix grammars over one-letter alphabet 92\] and settle a number of open questions in \[Dassow, J., Pâun, G.: Regular rewriting in formal language theory 89\]. Both results are obtained by a reduction to Petri net problems.
> 4 votes

# Answer
To my knowledge, it is an open problem whether the inclusion (c) above is strict. Some (baby) steps toward solving this problem can be found in

"Toward Understanding the Generative Capacity of Erasing Rules in Matrix Grammars", IJFCS 2011, http://dx.doi.org/10.1142/S0129054111008118

"On Erasing Productions in Random Context Grammars", ICALP 2010, http://dx.doi.org/10.1007/978-3-642-14162-1\_15

"A Sufficient Condition for Erasing Productions to Be Avoidable", DLT 2011. http://link.springer.com/chapter/10.1007%2F978-3-642-22321-1\_39
> 5 votes

---
Tags: formal-grammars
---


title: Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

text:
# Question
Title: Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?
I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar:

$$ S \rightarrow Ac \\ S \rightarrow B \\ A \rightarrow aAbb \\ A \rightarrow abb \\ B \rightarrow aBb \\ B \rightarrow ab $$

Which generates the language $\\{a^nb^n\\}\cup\\{a^nb^{2n}c\\}$. He states that this language is clearly RL($k$), which is easy to see, and he proves that it cannot be LR($k$). But, in his proof, he states:

> The problem is, of course, the appearance of "c" at the extreme right.

So, my doubt is: if it wasn't for the extra "c", could the language be LR($k$)? He remarks that, *of course*, the problem is the "c", but I don't see how I could write an LR($k$) grammar for $\\{a^nb^n\\}\cup\\{a^nb^{2n}\\}$.

# Answer
> 2 votes
Propbably you should read the citation as: "The problem is that the c (which separates the two parts of the language) *is at the extreme right and not at the extreme left*, where we start parsing."

Therefore it is of no help (unlike the case where you start reading at the right), and therefore there is no LR-grammar for this language. Neither with the c nor without.

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


# Question
Title: How to efficiently determine whether a given ladder is valid?
At my local squash club, there is a ladder which works as follows.

1. At the beginning of the season we construct a table with the name of each member of the club on a separate line.
2. We then write the number of games won and the number of games played next to each name (in the form: player wins/games).

Thus at the beginning of the season the table looks like this:

```
Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0

```

Any two players may play a match, with one player winning. If the player nearest the bottom of the table wins, then the position of the players is switched. We then repeat step 2., updating the number of wins and games next to each player. For example, if Alice beats Billy, we have

```
Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0

```

These matches go on throughout the season and eventually result in players being listed in approximate strength order.

Unfortunately, the updating happens in a rather haphazard way, so mistakes are made. Below are some examples of invalid tables, that is, tables which could not be produced by correctly following the above steps for some starting order (we have forgotten the order we used at the beginning of the season) and sequence of matches and results:

```
Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0

Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0

Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1

```

Given a table, how can we efficiently determine whether it is valid? We could start by noting the following:

1. The order of the names doesn't matter, since we have forgotten the original starting order.
2. The total number of wins should be half the sum of the number of games played. (This shows that the first example above is invalid.)
3. Suppose the table is valid. Then there is a multigraph \- a graph admitting multiple edges but no loops - with each vertex corresponding to a player and each edge to a match played. Then the total number of games played by each player corresponds to the degree of the player's vertex in the multigraph. So if there's no multigraph with the appropriate vertex degrees, then the table must be invalid. For example, there is no multigraph with one vertex of degree one and one of degree three, so the second example is invalid. \[We can efficiently check for the existence of such a multigraph.\]

So we have two checks we can apply to start off with, but this still allows invalid tables, such as the third example. To see that this table is invalid, we can work backwards, exhausting all possible ways the table could have arisen.

I was wondering whether anyone can think of a polynomial time (in the number of players and the number of games) algorithm solving this decision problem?

# Answer
> 1 votes
This is not a complete answer. I give a simpler statement of the problem and some remarks.

We start with a graph where vertices are labeled with $\[n\]$.

We have an operation that adds a directed edge from $v$ to $u$ to the graph, and if $label(v)\<label(u)$ switches their labels.

Given a directed multi-graph $G$ with $n$ vertices and $e$ edges, check if it can be obtained using using the operation above.

It is easy to see that the problem is in $\mathsf{NP}$: a certificate is a (polynomial size) sequence of operations resulting in the $G$.

### Observation

It seems that we can assume without loss of generality that all edges to the last vertex are added at the end of the sequence and all edges from it are added at the start of the sequence. This can be generalized to other vertices. Assume that we have remove all vertices with labels larger than $label(v)$. All edges to $v$ are added at the end of the sequence and all edges from $v$ are added at the start of the sequence.

I think it should be possible to combined this observation with Havel-Hakimi to give a polynomial time algorithm.

# Answer
> 0 votes
I haven't solved the problem, but I have partial results, the statements of which are given below. I'll write up the proofs if anyone's interested.

*Proposition*. Suppose that the ladder (1) contains more than one player (2) contains an equal number of wins and losses; and (3) is such that each player has won at least one game and lost at least one game. Then the ladder is valid.

Let $W\_i$ be the number of wins of player $i$, $L\_i$ the number of losses of player $i$ and $R\_i$ the rank (where higher is better).

*Proposition (due to Fabio Parisi)*. If $L\_i=0$ and the ladder is valid, then $$W\_i \le \sum\_{k:R\_k \> R\_i, W\_k \> 0} (L\_k - 1)^+ + \sum\_{k:R\_k\<R\_i}L\_k,$$ and a corresponding bound holds for $L\_i$ in the case that $W\_i=0$.

---
Tags: algorithms, graphs
---


title: Finding all soldier wins

text:
# Question
Title: Finding all soldier wins
Consider the following game (see also this question):

One day a castle is attacked at sunrise (by surprise) by n soldiers.

Each soldier carries a canon and a rifle.

The castle has strength s.

On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points). After all the soldiers have fired, the castle sends dpw defenders to battle them.

In the ensuing days the castle and the soldiers battle it out following these rules:

1. All the soldiers fire first. A soldier can fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier can only shoot once). One shot at a defender kills him. One shot at the castle decreases its strength by 1.
2. Then each of the d defenders shoots at one soldier (and only one) killing him.
3. If the castle still has strength points (i.e. s\>0) it sends a new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.
4. Repeat 1 through 3 on each new day.
5. If all soldiers are killed by the defenders, the castle wins.
6. If there are zero defenders after the soldiers shoot and the castle strength is zero, the soldiers win.

The answer to this question gives the strategy the soldiers should follow to win in a minimum number of rounds.

If $$n\leq s\<2n, dpw\geq n, 2n\<dpw+s\<(\phi+1)n$$, the strategy that leads to a victory for the soldiers in the minimum number of rounds consists of the soldiers shooting only at the castle in the first and second days and destroying it, and from then on, the soldiers trade fire with the remaining defenders winning in a total of $2+\max(k,0)$ days, where $$k=\left\lceil\frac{\log\_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$

If $dpw\<n$, the soldiers can win in a minimum of $c+\max(k,0)$ days, where $$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$ and $$k = \left\lceil\frac{\log\_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$ In this case they shoot, in each round, at the defenders first then the castle for $c$ days which is the time it takes to destroy the castle.

What is an algorithm to find systematically all the strategies that lead to a win by the soldiers not just the minimum day strategy?

For example if $n=10, s=12, dpw=10$, there are 2 solutions in which the soldiers win: The first where the number of soldiers, defenders and castle strength goes like this (in 3 rounds)

> start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12
>
> round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2
>
> round2:'soldiers': 8, 'defenders': 2, 'castle-strength': 0
>
> round3:'soldiers': 8, 'defenders': 0, 'castle-strength': 0

and the second solution where it goes like this (4 rounds)

> start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12
>
> round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2
>
> round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 1
>
> round3:'soldiers': 6, 'defenders': 3, 'castle-strength': 0
>
> round4:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

(in the particular case where $dpw=n$, like in the example above, there is an infinite number of solutions as @rotia points out, where the 10 soldiers eliminate the 10 defenders in either the 3rd or 4th or 5th... round before destroying the castle)

# Answer
> 1 votes
In the case $n\leq s\<2n,dpw\geq n, 2n\<dpw+s\<(\phi+1)n$, a possible way of finding all soldiers wins is following this approach:

1. Have the soldiers attack only the castle in the first 2 days, then once destroyed attack the defenders on the subsequent days. This gives you the minimum number of days solution.
2. Have the soldiers attack the castle on the first day, then have $n-1$ of the soldiers attack the castle on the second day and $1$ of the soldiers attack the defenders on that second day. Finally destroy the castle on the third day and let the soldiers battle it out in the remainder of the days. This gives you the minimum number of days solution+1 (if there is one).
3. Have the soldiers attack the castle on the first day, then have $n-2$ of the soldiers attack the castle on the second day and $2$ of the soldiers attack the defenders on that second day. On the third day, the remaining soldiers but 1 attack the castle and the rest attack the defenders. Finally on the fourth day the remaining soldiers destroy the castle and let the soldiers battle it out in the remainder of the days. This gives you the minimum number of days solution+2 (if there is one).
4. etc
5. The basic idea of this approach is to consider the cases where the castle is destroyed on day 2, on day 3, on day 4, etc

For this to work well it would be useful to know not just the minimum number of days it takes for the soldiers to win but also the maximum number of days it takes. It might be possible to find this mathematically.

Also note that there are cases like this

solution 1 (3 rounds)

> start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14
>
> round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4
>
> round2:'soldiers': 6, 'defenders': 4, 'castle-strength': 0
>
> round3:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

solution 2 (5 rounds)

> start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14
>
> round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4
>
> round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 3
>
> round3:'soldiers': 4, 'defenders': 5, 'castle-strength': 0
>
> round4:'soldiers': 3, 'defenders': 1, 'castle-strength': 0
>
> round5:'soldiers': 3, 'defenders': 0, 'castle-strength': 0

i.e. there might be gaps (there is no solution in 4 rounds)

---
Tags: algorithms, optimization, search-algorithms, dynamic-programming, backtracking
---


# Question
Title: Checking membership in DFA with fixed length using AC1 circuit?
I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should be the way to go, but I always exceed the max size. Would really appreciate any help

# Answer
Let $T$ by a balanced binary tree with $n$ leaves, and label each internal node $v$ by the interval $I\_v$ consisting of the leaves below $v$. For each $v$ we will calculate the a two-place relation $R\_v(s,t)$ which checks whether $I\_v$ causes the automaton to move from $s$ to $t$. If $a,b$ are the two children of $v$, then $$ R\_v(s,t) = \bigvee\_u (R\_a(s,u) \land R\_b(u,t)). $$ For a leaf $f$, $R\_f(s,t) = \[\delta(s,x\_f) = t\]$, where $x\_f$ is the $f$th input, and $\delta$ is the transition function. If $r$ is the root of the tree then the final answer is $$ \bigvee\_{q \in F} R\_r(q\_0,q), $$ where $q\_0$ is the initial state and $F$ is the set of accepting states.

Each node of the tree uses $O(1)$ gates. Since the tree has $O(n)$ nodes, the circuit has size $O(n)$. It's also not difficult to check that it has depth $O(\log n)$. Moreover, the fan-in of each gate is constant (since the number of states is constant), and so this circuit is actually in $\mathsf{NC}^1$.

Note also that the construction works directly for NFAs.
> 1 votes

---
Tags: complexity-theory, finite-automata, decision-problem, circuits
---


# Question
Title: What is the amortized time complexity of inserting an element to this heap?
Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements into the heap?

I think that we have $T(n) = n \cdot n$ (which is an upper bound on the total cost of a sequence of n operations in the worst case), and then the amortized complexity according to one formula is $\frac{T(n)}{n} = \frac{n^2}{n} = n$.

But I think it is very wrong because it is very clear from intuition that I should get $\log(n)$ ... So how should I calculate this?

# Answer
> 0 votes
Two very different operations are happening here, the doubling of the heap with its copy, and the insertion operations themselves. It sounds like you are fine on the insertion operations (where amortized analysis isn't needed), but for the doubling of the heap, you need a bit more help.

I don't want to post an answer to what might be a homework problem, but for that part of the problem, it looks very similar to how dynamic arrays work. If you consider the amortized analysis for dynamic arrays, and then just add the heap insertion operations to that, you will get something that works for insertion into heaps that can grow.

---
Tags: algorithm-analysis, data-structures, runtime-analysis, heaps, amortized-analysis
---


# Question
Title: Is this probability distribution data structure already discovered?
**Problem formulation**

I have implemented an interesting probability distribution data structure: having $n$ elements $a\_1, a\_2, \dots, a\_n$ in the data structure with respective positive weights $w\_1, w\_2, \dots, w\_n \> 0$, upon request each $a\_i$ may be returned with probability $$\frac{w\_i}{\sum\_{j = 1}^n w\_j}.$$

A Java implementation of my data structure can be obtained here, yet I will specify the algorithm here textually:

There are two types of nodes, *relay* nodes and *leaf* nodes. The actual elements with their actual weights are stored in leaf nodes. What comes to relay nodes, we allow only those that have both children (the tree is binary). However, each relay node know how many leaves is there in the subtree starting from that very relay node; also each relay node knows the sum of weights of all its leaves.

Whenever adding a new element, we start traversing the tree from its root, and until we reach a leaf node, we choose that relay node, whose node count is smallest; this way it maintains a logarithmic height.

What comes to the removal of an element, the data structure maintains a hashtable mapping each element to its leaf node. So, first we get the leaf node, remove it, after which, we replace the parent relay node with the sibling leaf.

Whenever sampling an element, we start from root, and choose an appropriate relay node until we reach the appropriate leaf node, whose element we return.

All three basic operations seem to run in worst-case $\mathcal{O}(\log n)$, and my benchmarking supports the observation.

A simple visualization:

**Question**

Is this data structure already discovered? If yes, could you tell me the name of the paper that discusses it?

# Answer
This is a straightforward use of augmented data structures. I wouldn't expect it to be publishable on its own; it's more of an undergraduate exercise. So, I would expect that it's probably been thought of many times before by many people independently, but not necessarily written down in any particular research paper.

The idea of storing in the node of a tree the number of leaves under it is a completely standard idea in augmented data structures. So too is the idea of storing each node the sum of the values in the leaves under it. If you read some algorithms and data structures textbooks that describe augmented data structures, I'm sure you'll find examples of both of those motifs.
> 8 votes

# Answer
I might be misunderstanding this, but what functionality does the data structure provide? What is its goal? It seems like you have given a way to build a data structure, but I am unsure what functionality it provides other than perhaps the ability to answer questions about its own structure?

For something that looks similar, but is more static (no insertions or deletions, just a given number of elements with frequency counts or weights), a very well-known problem is to try to minimize the weighted sum of node depths in the tree. These are known as Huffman Trees, used to generate Huffman Codes for compressing data. The tree can be computed in $\Theta(n \lg n)$ time, or $\Theta(n)$ time if you have the weights in sorted order.
> 0 votes

---
Tags: algorithms, data-structures, reference-request
---


# Question
Title: Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem
I am really confused with this problem.

**Here's the problem:**

You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at the same place, but multiple arrows can point to the same place and arrows can start and end in the same place. The arrow from place $i$ points to place $a\[i-1\]$,($a$ being an array representing the game board with $N$ elements and $i$ is between $1$ and $N$, inclusive).There are $0$ to $N$ tokens,inclusive, placed in those places and that, in each round, move along the arrows from their current place. If two or more tokens are in the same place, then you lose that game. But if that doesn't happen for the $K$ rounds specified, then you win the game. There may be multiple ways to solve the problem, but Two ways are different if there is some $i$ such that at the beginning of the game place $i$ did contain a token in one case but not in the other. Count those ways and return their count modulo $1,000,000,007$.

The whole problem is confusing to me, but what really confuses me is that it states that the arrow that starts from $i$ goes to $a\[i-1\]$. How I understand it, for the first example,( $\\{1,2,3\\} \\;5$ Returns:$8$ ), if $a\[1\]=1$, $a\[2\]=2$, and $a\[3\]=3$, then $3$ maps to $2$ and $2$ maps to $1$, but then $1$ maps to $0$,(but point $0$ doesn't exist).

What would be more correct would be if $a\[0\]=1$, $a\[1\]=2$, and $a\[2\]=3$, but then all the points would map to themselves,(though it says in the example that the tokens don't move during the rounds).

I am probably way off, but I couldn't find many explanations, and the ones I found didn't make any sense to me, and I couldn't find many visual depictions either.

# Answer
> 1 votes
$a\[0\] = 1, a\[1\] = 2, a\[2\] = 3$.

"The arrow from place $i$ points to place $a\[i−1\]$"

So yes, all $3$ places in this sample point to themselves. It actually says in the explanation that "in each round each token will stay in the same place".

In the second sample, all three places point towards the first one.

In the third sample, you have a $2$-cycle: $1$ points to $2$ and vice-versa.

Is everything clear now?

---
Tags: graphs, dynamic-programming
---


# Question
Title: Amortised analysis of binary heap insert and delete-min
I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function.

We can assume, that insert is *O(logn)* and delete-min is *O(logn)* too.

The goal is to prove, that amortised price of insert is *O(logn)* and amortised price of delete-min is *O(1)*.

Can't figure out how to create a potential function.

```
POT.F = ?
INSERT c = logn + (something from 0 to xlogn)
DELETE-MIN c = logn + (something like -logn)

```

Could you guys help me? I've figure out so far that difference between potentials should be from *0* to *xlogn* so INSERT price would be *logn* and for *DELETE-MIN*, difference should be somewhere abour *-logn* to get constant price.

# Answer
First, for a bit of clarifying terminology: rather than proving an amortized insertion cost of $O(\lg n)$ and an amortized deletion cost of $O(1)$, you are using those amortized costs to prove something about the total cost of a sequence of insertions and deletions, starting with an empty heap. This might be a subtle distinction, but it is fairly important (at least to me). If you allow yourself to start from a non-empty heap, you would also need to allow yourself to start with a $\Theta(n \lg n)$ potential, or else the deletion amortized cost won't work. Or, if you were to add in an operation for the worst-case linear time build-heap operation, you would also need for that linear time operation to add $\Theta(n \lg n)$ to the potential function.

To use your desired amortized runtimes, each insertion has to prepay for a deletion to come later. So, for instance, when inserting into a heap of size $n$, you can pay for the actual insertion $O(\lg n)$, but your amortized cost will pay that plus an additional $O(\lg n)$ for the worst-case runtime of deleting from a heap of size $n+1$. Now, every time you delete from a non-empty heap? That deletion's actual cost has already been prepayed by a previous insertion's amortized cost. It costs 0 (amortized) to delete. The only deletions that you still need to pay for are the ones from an empty heap, for when your deletions outnumber prior insertions, and those cost $O(1)$.

While these bounds are fine to use for a proof of efficiency for a sequence of insertions and deletions, they are slightly odd, in that in real life, the deletions generally take expected $\Theta(\lg n)$ time, and insertions take expected $\Theta(1)$ time, for some reasonable definitions of operating on a random heap of size $n$.

While I have presented this in terms of "prepaying" (or the accounting method), in this case, just writing it down as a more formal equation directly transforms it into the potential function method. You will be able to prove that the potential of a heap with $n$ elements is at least $\sum\_{i=1}^n f(i)$ where $f(i)$ is the worst-case price to delete the min item from a heap if $i$ elements. You already start your question with a given $O(\lg i)$ bound on $f(i)$.
> 4 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, heaps, amortized-analysis
---


title: A modified version of two way DFA

text:
# Question
Title: A modified version of two way DFA
Following an exercise from Hopcroft-Ullman's Introduction to automata theory:

Let's define $k-MDFA$ as two way deterministic finite automaton with $k$ markers, similarly to two way $DFA$ but with ability to place (or pick up) a marker on the input cell currently under the head, but with limitation to placing at most $k$ markers at any time during computation, and with single cell only being able to hold at most 1 marker at any given time.

Formally, it's a tuple $A=(Q, \Sigma, \delta, s, F)$ where

* $Q$ is finite set of states
* $\Sigma$ is the input alphabet
* $\delta : Q \times (\Sigma \hspace{2pt}\cup \hspace{2pt} \\{\vdash, \dashv\\})\times \\{0,1\\} \rightarrow Q \times \\{\textbf{L,R}\\}\times \\{0,1\\}$ is the transition function
* $s$ is the initial state and $F$ is the set of accepting states

Input tape of the automaton for word $w \in \Sigma^\*$ is $\vdash w \dashv$.

Moreover the transition function satisfies $\delta(q,\vdash,m) = (q', R, m')$, $\hspace{2pt}\delta(q, \dashv, m) = (q', L, m')$ for all $q \in Q, \hspace{2pt} m \in \\{0,1\\}$ and for some $q' \in Q $ and $m' \in \\{0,1\\}$ (we do not allow automaton to leave the input).

If automaton attempts to place more than $k$ markers on the tape, the computation stops with rejection.

I have proved that $1-MDFA$ recognize exactly regular sets, but I can also show that with $2-MDFA$ I can recognize language $\\{ ww : w \in \Sigma^\*\\}$, which is not a context free language. The second fact is fairly simple - here's an outline of how such automaton would work:

1. Check parity of input's lenght
2. Locate the middle of input by placing markers at both ends of the word, and then moving them one step closer towards the middle alternatingly.
3. Place marker on the first cell of input and on first cell of second half of the input
4. Compare letters under markers, if they differ enter reject state, if they are same, move both markers 1 step to the left and repeat. If you are about to move right marker onto symbol $\dashv$ enter accept state.

As such, clearly languages recognized by $k-MDFA$ are not contained in $CFL$ for $k \geq 2$.

My questions are:

1. Does increasing the amount of markers increase the computation power of $k-MDFA$ for $k \geq 2$?
2. Does allowing nondeterminism increase computation power of $k-MDFA$?
3. Can $k-MDFA$ recognize all context-free languages? If so, what's the minimal $k$ capable of expressing $CFL$?

Any references are welcome, if the question shows ignorance in the subject, I apologise.

# Answer
> 3 votes
To answer your first question, see: Burkhard Monien, Two-way multihead automata over a one-letter alphabet. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1980) https://eudml.org/doc/92118

".. *we show that for languages over a one-letter alphabet two-way automata with $k+1$ heads are more powerful than two way automata with $k$ heads*."

This improves over a similar result of the same author and others for two-letter alphabets, one-way automata, or stepping from $k$ to $k+4$-heads, see the paper.

Also an interesting quote "*It is wellknown that SPACE(log n), the class of languages acceptable within space bound log n, is identical with the class of languages acceptable by two-way multihead automata*".

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


title: Why is b-tree search O(log n)?

text:
# Question
Title: Why is b-tree search O(log n)?
B-tree is a data structure, which looks like this:

If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need to go through several elements in the child-node to find its right child-node etc.

The point is, when I have $n$ elements in every node, then I have to go through all of them in the worst case. So, we have $O(n)$ complexity for searching in one node.

Then, we must go through all the levels of the structure, and they're $log\_m N$ of them, $m$ being the order of B-tree and $N$ the number of all elements in the tree. So here, we have $O(log N)$ complexity in the worst case.

Putting these information together, we should have $O(n) * O(log n) = O(n * log n)$ complexity.

But the complexity is just $O(log n)$ - why? What am I doing wrong?

# Answer
You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$.

Their height will be in the best case $\lceil log\_m(N + 1) \rceil$, and the worst case is height $\lceil log\_{\frac{m}{2}}(N)\rceil$ but there is also a saturation factor $d$, that you have not mentioned.
The height will be $O(log N)$, please notice that $m$ disappeared, because it effectively is multiplication by a constant.
Now at every node you have at most $m$ sorted elements, so you can perform binary search giving $log\_2(m)$, so the proper complexity is $O(log(N) * log(m))$.
Since $m \<\< N$, and what is more important, is that it does not depend on $N$, so it should not be mixed, or it might be given explicitly (with $m$ not $N$ or appearing $n$).
> 12 votes

# Answer
> The point is, when I have n elements in every node, then I have to go through all of them in the worst case. So, we have O(n) complexity for searching in one node.

No. You would do a binary search in the node, so the complexity of searching in a node is $O(log n)$, not $O(n)$.
> 2 votes

# Answer
Considering this as an order $m$ B-Tree, whether or not you take $m$ to be a constant, worst case search takes $\Theta(\lg N)$ total comparisons ($N$ values total). As is stated in another answer (as a newbie, I cannot comment on it yet), the height of the tree is about $\log\_m N = (\lg N)/(\lg m)$. Especially if you are taking $m$ to be variable, it is assumed that you will have a logarithmic search per node, order $O(\lg m)$. Multiplying those terms, $\log\_m N \cdot \lg m = ((\lg N) / (\lg m)) \cdot \lg m = \lg N$, you don't have to drop the $\lg m$ term using big-O, they really do cancel.

For most (but not all) analysis on external memory algorithms, page size is not treated as a constant. It isn't wrong to do so, but generally gives more information if you don't. One of the difficult things about external memory algorithms is that you are generally trying to optimize (at least) two different things at once: overall operations, and page accesses, which are so inefficient that you might want to minimize them even if it meant paying some extra in other operations. A B-Tree is so elegant because even when you consider page size as a variable, it is asymptotically optimal for operations on comparison based structures, and simultaneously optimizes for page accesses, $O(\lg\_m N)$ per search. Notice how uninteresting that last fact becomes if we just consider $m$ as a constant: of course for a $O(\lg N)$ operation search, it would use $O(\lg N)$ page references. $O(\lg\_m N)$ is much more informative.
> 2 votes

# Answer
If you have n elements in every node, that means the number of total elements are exponential to n.**In complexity analysis n is your total number of elements in the whole tree**, so if your tree is balanced there is no way that you would have n elements in any node.

Assume your tree in your question has 4 elements in every node. That means you have 16 nodes in total and in worst case you have to search through root and the node with the searched element ,which makes 4 elements in total, so your total N=16 and in your worst case you still inspect 4 elements, still ***O(logN)***.
> 0 votes

# Answer
You can have the *worst case* complexity O(n) if

1) the number of keys per node is unlimited, all the keys end up in one node and for some reason the tree is not rebalanced, and

2) the keys in one node are accessed sequentially, and not in some more efficient way.

That would be a **terrible** way to implement a B-tree, and even in this case, it's still only the worst case complexity. You are partially right though ;-)
> 0 votes

---
Tags: algorithm-analysis, data-structures, search-trees, balanced-search-trees
---


# Question
Title: Is the complement of { ww | ... } context-free?
Define the language $L$ as $L = \\{a, b\\}^\* - \\{ww\mid w \in \\{a, b\\}^\*\\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not?

I've tried to intersect $L$ with $a^\*b^\*a^\*b^\*$, but I still can't prove anything. I also looked at Parikh's theorem, but it doesn't help.

# Answer
> 39 votes
It's context-free. Here's the grammar:
$S \to A | B|AB|BA$
$A \to a|aAa|aAb|bAb|bAa$
$B \to b|aBa|aBb|bBb|bBa$

$A$ generates words of odd length with $a$ in the center. Same for $B$ and $b$.

I'll present a proof that this grammar is correct. Let $L = \\{a,b\\}^\* \setminus \\{ww \mid w \in \\{a,b\\}^\*\\}$ (the language in the question).

**Theorem.** $L = L(S)$. In other words, this grammar generates the language in the question.

*Proof.* This certainly holds for all odd-length words, since this grammar generates all odd-lengths words, as does $L$. So let's focus on even-length words.

Suppose $x \in L$ has even length. I'll show that $x \in L(G)$. In particular, I claim that $x$ can be written in the form $x=uv$, where both $u$ and $v$ have odd length and have different central letters. Thus $x$ can be derived from either $AB$ or $BA$ (according to whether $u$'s central letter is $a$ or $b$). Justification of claim: Let the $i$th letter of $x$ be denoted $x\_i$, so that $x = x\_1 x\_2 \cdots x\_n$. Then since $x$ is not in $\\{ww \mid w \in \\{a,b\\}^{n/2}\\}$, there must exist some index $i$ such that $x\_i \ne x\_{i+n/2}$. Consequently we can take $u = x\_1 \cdots x\_{2i-1}$ and $v = x\_{2i} \cdots x\_n$; the central letter of $u$ will be $x\_i$, and the central letter of $v$ will be $x\_{i+n/2}$, so by construction $u,v$ have different central letters.

Next suppose $x \in L(G)$ has even length. I'll show that we must have $x \in L$. If $x$ has even length, it must be derivable from either $AB$ or $BA$; without loss of generality, suppose it is derivable from $AB$, and $x=uv$ where $u$ is derivable from $A$ and $v$ is derivable from $B$. If $u,v$ have the same lengths, then we must have $u\ne v$ (since they have different central letters), so $x \notin \\{ww \mid w \in \\{a,b\\}^\*\\}$. So suppose $u,v$ have different lengths, say length $\ell$ and $n-\ell$ respectively. Then their central letters are $u\_{(\ell+1)/2}$ and $v\_{(n-\ell+1)/2}$. The fact that $u,v$ have different central letters means that $u\_{(\ell+1)/2} \ne v\_{(n-\ell+1)/2}$. Since $x=uv$, this means that $x\_{(\ell+1)/2} \ne x\_{(n+\ell+1)/2}$. If we attempt to decompose $x$ as $x=ww'$ where $w,w'$ have the same length, then we'll discover that $w\_{(\ell+1)/2} = x\_{(\ell+1)/2} \ne x\_{(n+\ell+1)/2} = w'\_{(\ell+1)/2}$, i.e., $w\ne w'$, so $x \notin \\{ww \mid w \in \\{a,b\\}^\*\\}$. In particular, it follows that $x \in L$.

# Answer
> 3 votes
This language is context free it was proved in the following paper:

Tomaszewski, Zach. "A Context-Free Grammar for a Repeated String." *Journal of Information and Computer Science*, 2012 (PDF).

The grammar is as follows: \begin{align\*} S&\to E\mid U\mid \epsilon\\ E&\to AB\mid BA\\ A&\to ZAZ\mid a\\ B&\to ZBZ\mid b\\ U&\to ZUZ\mid Z\\ Z&\to a\mid b \end{align\*}

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


# Question
Title: Is Terra the only system programming language able to compile code at runtime?
I stumbled across Terra last year, and the most similar language I can think of is Julia. Terra is inspired by and uses Lua for templating/metaprogramming instead of being derived from e.g. the Lisp or ML families, but like many JITted language implementations it blurs the line between compile-time and run-time.

Are there any other low-level (no VM, small runtime, etc.) programming languages I'm missing that can compile and run code at runtime (besides assembly)? Maybe Forth-likes, or Extempore's xtlang? Terra calls this (multi-)staged programming.

# Answer
**No.** So far the only ones I've found are pretty obscure/old, both variations of C:
> 1 votes

# Answer
Graphics programming languages like OpenGL and Metal often get compiled at runtime. Because at build time you don't even know what processor the code will run on, and the code to be compiled might itself be constructed at runtime.
> 0 votes

---
Tags: programming-languages, compilers, meta-programming
---


# Question
Title: Turing Completeness of System Which Randomly Fails to Complete Calculations
If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python implementation which, upon every variable assignment, with probability $\frac13$ decreased the value by $1$, with probability $\frac13$ increased the value by $1$ and otherwise kept the value constant, would it be Turing complete? This seems to be able to perform all of the calculations which Python is able to perform, just not reliably.

# Answer
> -1 votes
I've gone around and around on this one. It would seem that we've landed on "No, it would not be Turing Complete, although we might be able to approximate it with a bounded probability of error on either accuracy or returning in finite time."

In your post, you said "just not reliably"... that is, in fact, a crucial part of the definition. To be Turing-complete, we have to be able to exactly simulate a single taped Turing machine -- getting it right "sometimes" isn't any better than flipping a coin to determine if it's raining outside with "50% accuracy".

In the given example, you seem to suggest that the random failures only occur on assignment, not for other operations in the computer. Does this affect assignments performed by the programmer alone, or internal assignments performed as intermediate steps by the compiler? If it only affects assignments performed by the programmer, many programs could be written (in horrendously terrifying complexity and near impossible to debug) without creating and assigning any variables at all. In this case, I suppose it would be similar to a Turing tarpit.

If the programmer HAD to assign variables, they should be able to use something in the vein of the old Heinlein "Tell me 3 times", assigning the variable in an array repeatedly (say 100 times, or until 3 distinct values have been saved) and then use the median value (since all values are x, x-1, or x+1, the median *value*, not median result, must be the correct one). This would cut into performance HORRIBLY, but should, typically, arrive at correct values. (In fairness to @DavidRicherby, I concede that we cannot ensure both that we arrive at an answer and that it is correct with 100% certainty; for a look at how we could arrive at 3 distinct values without additional assignments, consider the following approach:

```
# function sum : x,y $\rightarrow$ z
var a = x + y;   // first assignment, may be x, x-1, or x+1
var b = x + y;
while (a == b)
  b = x + y;     // if this loop finishes, b is now distinct from a
var c = x + y;
while ((a == c) || (b == c))
  c = x + y;     // if this loop finishes, c is now distinct from a and b
if ((a < b) && (b < c))
  return b;
if ((b < a) && (a < c))
  return a;
// repeat for the other combinations; there should be 6 total if statements.

```

)

If the compiler can introduce intermediate assignment operations that the programmer did not that also suffer from this drawback (say, at the end of every elementary computation), or if there are other operations affected by this glitch (the killer one in my above example being the comparison operators), then we cannot simulate a Turing-complete language (or machine) at any speed -- we will only be right 1 out of every $3^n$ times on average, where $n$ is the number of operations we can't correct for.

**The Short Version of My Answer:**

I can try to check for errors internally myself in the midst of computation, which may or may not work depending on the details of your system. If I can't have or emulate a verifying system, then I cannot be Turing complete -- I'm just guessing at solutions.

Given that popular consensus is that such a verifying system implemented could not guarantee both returning in finite time AND returning an accurate answer, it would appear no, although we might be able to approximate it a reasonable percentage of the time.

---
Tags: turing-machines, computation-models, randomness, turing-completeness
---


# Question
Title: Use of sorting in counterexamples for equations
I came across a question which asked how sorting would help in searching for counterexamples to the conjecture that $$u^6 + v^6 + w^6 + x^6 + y^6 = z^6$$ has no non trivial solutions in integers.

The answer said to make two files containing values of $u^6 + v^6 + w^6 \pmod W$ and $z^6 - y^6 - x^6 \pmod W$. $W$ is the word size of the computer. Sort these, search for duplicates and go for further steps.

Can someone explain what these further steps would be in detail ?

# Answer
> 1 votes
You want to find solutions to $u^6 + v^6 + w^6 = z^6 - x^6 - y^6$. Obviously any solution would also have to be a solution modulo k, for every k. So the idea is to find the set of all possible values of $u^6 + v^6 + w^6$ modulo W, and the set of all possible values of $z^6 - x^6 - y^6$, and you need to find the elements that are common to both sets.

Question: What is the easiest way to check which elements two sets have in common? Answer: Sort the elements, that makes the search very easy.

The further steps: If you are lucky then both sets had few elements in common. So you can deduce values of u, v, w, x, y, z modulo W or modulo some other value. Which means you have reduced the search space. If there was a good amount of reduction, try different values instead of W. And at some point you start with an exhaustive search, but with fewer values needing to be searched.

---
Tags: sorting, number-theory
---


title: Decidability Turing Machines

text:
# Question
Title: Decidability Turing Machines
Let $\Sigma$ be an alphabet, and suppose that $A$, $B \subseteq \Sigma^\*$ are Turing recognizable languages where both $A \cup B$ and $A \cap B$ are decidable. Prove that $A$ is decidable.

Is this true? I have tried to prove it by considering the intersection and complement of the sets, but I think I am missing something.

# Answer
Given an $x$ (for which you want to check membership in $A$), I would start by checking if $x \in A \cap B$, which is possible, since $A \cap B$ is decidable. If $x \in A \cap B$ you also know that $x \in A$.

If $x \not\in A \cap B$, you can continue and ask whether $x \in A \cup B$.

If so, either $x \in A$ or $x \in B$. Since $A$ and $B$ are Turing recognizable, you can enumerate both sets in an interleaved fashion. Let $a\_i \in A$ and $b\_i \in B$ be the respective elements in the enumeration. Since $x \in A \cup B$, there is an $i$, such that $a\_i = x$ or $b\_i = x$, but not both. If $a\_i = x$, then $x \in A$, else $x \not\in A$.

If $x \not\in A\cup B$, then $x \not\in A$.
> 4 votes

---
Tags: computability
---


# Question
Title: Does there exist context-free grammar with words of length n^2 or n^3?
Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to substitute each $S$ with sequence of $S$'s of length $n$.

# Answer
> 10 votes
For a language $L$, let $N(L) = \\{|w| : w \in L\\}$, and let $U(L) = \\{1^n : n \in N(L)\\}$. Parikh's theorem shows that if $L$ is context-free then $U(L)$ is regular. In particular, since $\\{1^{n^2} : n \geq 0 \\}$ is not regular, no context-free language $L$ satisfies $N(L) = \\{n^2 : n \geq 0\\}$. In fact, no infinite context-free language $L$ even satisfies $N(L) \subseteq \\{n^2 : n \geq 0\\}$ (exercise).

# Answer
> 4 votes
Yuval's answer uses Parikh's theorem to show that if L is context-free then U(L) is regular, and then (implicitly) the pumping lemma for regular languages to show that U(L) is not regular.

The use of Parikh's theorem can be avoided using the pumping lemma for context-free languages.

If $L$ is infinite and context-free, then there is a word $uvwxy$ with $|vx|\>0$ such that $uv^kwx^ky \in L$ for all $k \ge 0$. So, $|uwy|+k|vx| \in N(L)$ for all $k$. Since $|vx| \ge 0$, this is an infinite arithmetic progression. In general, if $L$ is infinite, then $N(L)$ contains an infinite arithmetic progression (this is weaker than what we get from Parikh's theorem, which gives us that $N(L)$ is entirely made up of a finite union of arithmetic progressions).

The set $\\{n^c : n\ge 0\\}$ contains no infinite arithmetic progression when $c\>1$. Note that the gap between $n^c$ and $(n+1)^c$ grows to infinity, so at some point it must be larger than any given $b$, so if $a+kb= n^c$, then $n^c \< a+(k+1)b \< (n+1)^c$ for large enough $n$, so $\\{a+kb :k\ge0\\} \not\subseteq \\{n^c:n\ge 0\\}$.

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


# Question
Title: How to compare two objects for percentage of equivalence
I'm trying to create a nodeJS application. It allows users to rate a bunch of songs and it stores them in their user profiles. I use this information to compare them to other users, and try to find users with similar interests in songs, and I suggest them new songs based on that.

Each user profile basically looks like this

```
userID: [the userid of the user]
songs: [the list of songs that the user has rated]
ratings: [the corresponding ratings each user gave to the song]

```

Each **song** is represented by a **9 digit whole number** and each **rating** is a **whole number from 1 to 6**. Basically put, I have to compare one user to the rest of the users to determine which of them match this user the best. By match, I mean gave the same songs similar ratings. To do this, I created a simple algorithm.

```
Step 1) Create a list, in which each entry maps our target user to each of the other
        users.
Step 2) Now consider each entry, determine which songs both of the users have rated, and
        store those songs (along with the corresponding ratings each user gave them) in
        this entry itself
Step 3) Now iterate through each entry and perform the following operations

        a) let percentage = 0
        b) let num = [the number of songs that both users rated]
        c) iterate through each song (that both the users rated) and perform the
           following operations

                i)    determine the score our target user gave this song and store it in
                      variable a
                ii)   determing the score the other user gave this song and store it in
                      variable b
                iii)  map a and b to new values based on this
                        1 --> -3
                        2 --> -2
                        3 --> -1
                        4 -->  1
                        5 -->  2
                        6 -->  3
                iv)   now calculate sum as
                    sum = |a| + |b|
                    where || is the absolute values
                v)    now calculate degree as
                    degree = sum/2
                vi)   now if a * b is less than 0 then
                            calculate (percentage - degree) and store that value
                            again in percentage
                          if not then
                            calculate (percentage - degree) and store that value
                            again in percentage

        d) now  calculate (50 + (percentage / (6*num))*100) and store that value
           in this entry as match

Step 4) Now that I have my list of entries (along with the match between each pair
        of target user and other user) I sort the list in descending order of match
        and from that, I can determine which users have the closest match in taste by
        selecting from the first entries

```

Now for each user pair, I am completely neglecting the songs that one user rated and the other didn't, and that is okay for me.

There are several problems with this method though, the biggest one being that this algorithm is very time consuming for a large set of users (say around 1,000,000). And also that I have to load in all the users, every time I need to find a set of matching users for just 1 user. And I need to do this repeatedly for that user, to update his/her list.

Is there a way to make this more efficient? Can I assign a value to each user that takes into account all the songs that they rated, and use that number to compare the users? Is that even possible? I guess what I'm asking is, how can I compare and contrast this data, mathematically, to find similar users, efficiently. Also, can someone suggest a proper tag for this type of question?

**EDIT**

D.W. has suggested a solution, but how do I implement it? Can you provide more detail?

# Answer
One approach is to use low-rank matrix factorization to approximate the ratings matrix, then use a nearest neighbors data structure.

In particular, let $M$ be the $m \times n$ ratings matrix, where $M\_{ij}$ is the rating that user $i$ has provided to user $j$. Look for a $m\times r$ matrix $U$ and a $r \times n$ matrix $V$ such that $M$ is well-approximated by $UV$ (e.g., $||M-UV||$ is minimized, except that missing entries of $M$ are ignored).

Once you've done this, each user can be mapped to a $r$-dimensional vector that summarizes their scores. Store the set of all of these vectors in a data structure that supports nearest neighbor search, e.g., a k-d tree. If you have chosen $r$ small enough (e.g., 10 or so), then nearest neighbor search should be very efficient. This will let you find the users who are most similar to a given user, and thus make a recommendation (e.g., using the k-nearest neighbors classifier).

There are many other approaches you could use: read the extensive literature on recommender systems and collaborative filtering.

As far as your other issue:

> I have to load in all the users, every time I need to find a set of matching users for just 1 user

Keep the data structure in memory, rather than re-loading it into memory each time.
> 2 votes

---
Tags: algorithms, comparison, recommendation-systems
---


# Question
Title: Which object-oriented programming language is the closest to the untyped sigma-calculus?
I'm wondering which of the dynamic object-oriented (or prototype-oriented) languages (like JavaScript, Ruby, Python, etc.) can be considered as the closest to Abadi and Cardelli's untyped sigma calculus?

# Answer
JavaScript looks perfectly like untyped sigma calculus.

It supports first-class citizens, described in paper concepts in terms of prototypes, closures, clone (called split), (dynamic) method override, objects dynamic creation, extension, delegation, subsumption, object fragments and polymorphism (which is understatement in terms of this language). Essentially it supports every operation described in the paper.

Since it uses prototype based inheritance the update of methods is one of the basic operations in this model. It recently started to support hierarchical class inheritance (but it was not needed, since emulating any kind of hierarchical behavior is possible with very short code).

Origins of Cardelli work predates the creation of JavaScript, but also worth mentioning is that JavaScript description as general purpose any language emulator with very short code to support such was described by Don Knuth (which predates Cardelli work, no connection between Knuth paper and creation of JS was ever made in any direction, but both papers exactly describe the JS properties).

Other languages fail with method backups or dynamic method override. But this is not the case for other prototype based languages (at least the most populqr ones), which fully support $\varsigma\text{-calculus}$ (take for example "Self").
> 4 votes

---
Tags: programming-languages, object-oriented
---


# Question
Title: If the Clique-k Problem is in P, why not Clique as well?
I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?)

The general clique problem is defined as

$\text{CLIQUE} = \left\\{ (G, k) | G = (V, E) \in \mathcal{G} \land \exists V\_c \subseteq V . |V\_c| \geqslant k \land V\_c \text{ is clique in } G \right\\}$

A clique of a given size can be found in polynomial time, for instance by this code:

```
# Iterates over all nodes. If node has at least size -1 neighbours,
# compares neighbour's neighbours with neighbours.
def CLIQUE(graph, size):

    for node in graph.nodes:
        if degree(graph, node) >= size - 1:
            neighbours = graph.edges[node]
            intersection = neighbours.union(set(node))
            for neighbour in neighbours:
                print neighbour
                print graph.edges[neighbour].union(neighbour)
        intersection = intersection.intersection(graph.edges[neighbour].union(neighbour))
            print intersection
            if len(intersection) >= size:
                return True
    return False

```

(rest of the program)

```
class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = dict()

    def from_file(self, deffile):
        with open(deffile, 'r') as f:
            for line in f:
                n1, n2 = line.split()
                self.nodes.add(n1)
                self.nodes.add(n2)
                if n1 in self.edges:
                    self.edges[n1].add(n2)
                else:
                    self.edges[n1] = set(n2)
                if n2 not in self.edges:
                    self.edges[n2] = set()

def degree(graph, node):

    return len(graph.edges[node])

```

So, given that the clique problem is 'Is there q clique of at least size k in G' and the above code returns true once it finds a clique of (at least) k nodes and runs in $\mathcal{O}(n^2)$, as it compares every node with every other node in the worst case, I don't understand how that code does not do what the general clique problem does... because apparenrtly it does not, as it runs in polynomial time and the general clique problem does not.

# Answer
> 4 votes
It's a matter of logical quantifiers.

Consider this statement: "if every natural number $n$ is bounded above by a constant $c$, how come there is no constant $c$ that bounds every natural number $n$ by above?".

The above is an example where $\forall n.\ \exists c.\ \ldots$ does not imply $\exists c.\ \forall n.\ \ldots$. Indeed, in the former, we can choose $c$ **after** we see $n$, while in the latter we must do **before**, and we are unable to do that: whatever $c$ we choose, the statement becomes false for e.g. $n=c+1$.

To decide CLIQUE, once we take the instance $(G,k)$ to be checked, we can use an algorithm which runs on $O(n^c)$ for some $c$ -- but here we are choosing $c$ **after** we have seen $k$. This does not prove that CLIQUE is in P. For that, we would need to find a constant $c$, and an associated $O(n^c)$ algorithm, which would decide any instance $(G,k)$, whatever $k$ is. And this is much harder.

---
Tags: np-complete, polynomial-time, clique
---


# Question
Title: Should all internal node keys in B+ tree also be in the leaves?
I was reading about B+ tree insertion. The algorithm takes following form:

> 1. Insert the new node as the leaf node.
> 2. If the **leaf node overflows**, split the node and **copy** the middle element to the parent index node.
> 3. If the **index node overflows**, split that node and **move** the middle element to the parent index node.
>
> However, adding the new index value in the parent node may cause it, in turn, to split. In fact, all the nodes on the path from a leaf to the root may split when a new value is added to a leaf node. If the root node splits, the tree grows by one level.

Now the book asks to insert 33 in following tree of order 4:

I was guessing how those \[10,20,30\] occur to be the root node. Before performing first split while forming above tree, these \[10.20,30\] should be in some leaf and in any case they should be present in some leaf.

In other words I feel that all internal node keys should also be present in the leaves. However thats not the case with \[10,20,30\]. This is also inline with the fact that in B+ tree all data is present in the leaves, so all keys should be present in the leaves.

Another example on youtube also have 13 and 30 in the root node but not in any leaf.

Am I wrong with the fact that all internal node keys should also be in the leaves?

# Answer
> 3 votes
The internal keys come from values also stored in leaves, but if you allow deletions, the value could be deleted from the leaf after it is created and used in the internal node. Deleting the value from a leaf won't change any internal nodes, unless the leaf becomes underfilled. With the insertion you list, it *would* have the property you are thinking of if there were no deletions.

On the other hand, it is possible that the author wasn't thinking of either the property you name, nor the possibility of deletions, when making the question, and just used 10, 20, 30 as easy separators. For sure, I have written questions with mistakes before, and usually, even with a mistake in the question, it can usually be answered properly to see if the student understands the material (insertion in this case). If a student then asked me what your post asks? I would be pleased with their understanding of the material to notice this property.

---
Tags: graphs, trees, binary-trees, binary-search-trees
---


title: Online sorting without modifications

text:
# Question
Title: Online sorting without modifications
There is an array with $n$ places. There is a stream of $n$ unique numbers that arrive at a random order (permutation selected uniformly at random).

Whenever a number arrives, we must put it somewhere in the array, and we are not allowed to move it later. The goal is to have as many numbers as possible (in expectation) in their correct location in the final array. The "correct location" is defined as the location where it would appear if the numbers were sorted.

What is known about this problem? What is the best expected success rate, and what algorithm attains it?

Notes:

* A related question is: What is the fastest online sorting algorithm? . It discusses a situation in which items can be moved when new items arrive, and the goal is to minimize the running time.
* I am mainly interested in maximizing the expected number of the correct positions. However, it is also interesting if there is a way to improve the probability that all numbers are in the correct position, above O(1/n!)

# Answer
> 5 votes
Define a *configuration* to be a state of the array $A\[\]$ after receiving some of the numbers. Define a configuration to be *obviously wrong* if there exists indices $i\<j$ such that $A\[i\],A\[j\]$ have already been filled in with numbers such that $A\[i\]\>A\[j\]$.

## A randomized algorithm

Here is a natural algorithm: guess where to put each number uniformly at random, conditioned on the one constraint that you never place a number in an obviously wrong position.

The analysis of this approach seems pretty tricky. Based on some back-of-the-envelope estimates I conjecture that this attains a $\sim e^{-\Theta(n)}$ probability of placing all numbers in the correct position, which is better than the naive $1/n!$ algorithm. However I have no proof, so this could be wrong.

## A deterministic algorithm

Here's what I *can* show. Let's consider a variation on the above algorithm: when you receive each number, find the range of array indices that wouldn't be obviously wrong, and then place that number in the *exact middle* (median) of that range. This algorithm is now deterministic.

For this algorithm, I can show that the probability of placing all numbers in the correct position *is* asymptotically larger than $1/n!$. In particular, it is at least something like $1/2^{\Theta(n)}$. Here's a hand-wavy analysis. For simplicity, let's assume $n$ is one less than a power of two. Place all $n$ numbers in a complete binary search tree. Now consider all sequences where you enumerate all the numbers at depth $1$ in some order, then all the numbers at depth $2$ in some order, then all the numbers at depth $3$ in some order, and so on. A hand-wavy estimate suggests that there are something in the vicinity of $n!/2^{\Theta(n)}$ such sequences, i.e., a random permutation has very roughly a $1/2^{\Theta(n)}$ probability of having this form. Moreover, the second algorithm above *always* succeeds in placing every number in the correct position. Therefore, the second algorithm above achieves a success rate of something in the vicinity of $1/2^{\Theta(n)}$. In particular, the success rate is significantly larger than $1/n!$.

For values of $n = 2^i-1$, we can characterize the exact probability of being correct: letting $P(n)$ denote the probability that the second algorithm succeeds in placing every number in the correct position, we find

$$P(n) = {1 \over n} \times P(\lfloor n/2 \rfloor)^2,$$

because the first element needs to be the median, and then you have two problems of half the size (the subsequence of numbers smaller than the median has to be a sequence with the same property, and the same for the subsequence of numbers larger than the median). We have the base cases $P(1)=1$ and $P(3)=1/3$. This recurrence relation grows like $P(n) \sim 2^{-e/2 \cdot (n+1)}$. Here $e/2 \approx 1.359\ldots$, so $P(n)$ grows roughly like $2^{-1.36 n}$, and in particular, much faster than $1/n!$.

In particular, here's one way to analyze this recurrence relation. Let $Q(n) = -\lg P(n)$. Then we find

$$Q(n) = 2 Q(\lfloor n/2 \rfloor) + \lg n,$$

where $Q(1)=0$ and $Q(3) = \lg 3$. Letting $R(i) = Q(2^i-1)$, we find

$$R(i) = 2 R(i-1) + \lg(2^i - 1),$$

with base case $R(1)=0$. Expanding, we find

$$R(i) = 2^{i-1} \times \left(\lg(1) + {\lg 3 \over 2} + {\lg 7 \over 4} + {\lg 15 \over 8} + {\lg 31 \over 16} + \dots + {\lg (2^i-1) \over 2^{i-1}}\right).$$

Summing the series, we find that to an excellent approximation

$$R(i) \approx 2^{i-1} \times e.$$

Therefore, $Q(n) \approx e/2 \cdot (n+1)$ and $P(n) \approx 2^{-e/2 \cdot (n+1)}$.

Credits: My thanks to @Algorithms with Attitude for the recurrence relation and the idea of analyzing the probability in this way.

# Answer
> 1 votes
maybe the title of the question should be a little different, like "Online sorting with the lowest number of modifications of the position of a number".

If you do not have the distribution of the numbers, than you should try to estimate and update the number distribution according to the numbers that come. There are algorithms to create a distribution function according to some data set (the numbers received until now) https://www.mathworks.com/matlabcentral/answers/33917-how-do-i-determine-the-probability-distribution-of-data

Run the probability calculation algorithm after every number and then insert the new number accordingly in your array.

I have no idea where you should put the first number, probably in the middle.

---
Tags: reference-request, sorting, randomness, online-algorithms
---


# Question
Title: Benes (Fat Tree) Network for number of inputs/outputs that is not 2^n
I was reading about Benes Network construction in this book. Their construction is easy for a number of inputs and outputs that is an exponent of two.

However it seems to me that for a number of i/o that falls between $2^{n}$ and $2^{(n+1)}$ one has to construct a network with $2^{(n+1)}$ ports and leave many unattached, which is wasteful. Is there a synthesis method for Benes networks or maybe an alternative topology that has the same properties (re-arrangeable not blocking) for arbitrary number of I/O?

# Answer
> 2 votes
This paper \[1\] presents a method to construct arbitrarily sized benes networks using a recursive approach.

1. Arbitrary Size Benes Networks by Chihming Chang and Rami Melhem in *Parallel Processing Letters*, Volume 7, 1997

# Answer
> 3 votes
Wasting ports to achieve an exact number of terminals is a common attribute of staged networks (butterfly, benes, folded-clos, etc.). The mesh, torus, and flattened butterfly topologies are a bit better because each dimension can have a different width, but this results in having uneven bisection bandwidth along each dimensional cut. The HyperX topology is a generalization of the flattened butterfly that allows each dimension to be configured independently in terms of width and weight (number of links connecting each pair of routers). The paper describes an algorithm to find the "optimal" configuration given a requirement for system size, bisection bandwidth, and router radix. An implementation of this algorithm is here. Given the requirements, it finds a satisfactory topology configuration that minimize cost (like wasted ports).

---
Tags: computer-networks, network-topology
---


# Question
Title: I know the algorithms, but i still don't know how to approach the questions
I study Graphs Analysis by myself and i understood most of the material just fine. But, there is one huge problem with my approach that prevents me from solving tests. I don't know how to build new Graphs based on requirements and i'll give an examples:

Question: G = (V,E) is a directed graph with no cycles (DAG) and w: E-\>R for each edge. There is an efficient algorithm that in given vertices s and t in the graph it finds the minimum weight path contains with at least 3 edges. So far it great - i understand the question just fine.

Step 1: For each vertex v in V, we mark: v1 = (v, 1), v1 = (v, 2), v3 = (v, 3), v4 = (v, 4)

Given G = (V, E), we'll build new graph G'=(V',E') where: V'={v1, v2, v3, v4| for each v in V}

E' = {(v1, u2), (v2, u3), \____(1)\____}

for each (ui, vj) in E', w(e) = {w(u, v)| (u, v) in E and (ui, vj) in E'}

(1) = ?

**a. (v3, u4), (v4, u4)** \- the correct answer

b. (v3, u3)

c. (v3, u4),(v4, u3)

d. (v3, u4)

step 2: Apply DAG algorithm from s1.

step 3: return the weight of the path from s1 to t4.

I know how DAG works, but i don't know how to build the new graph in order to see it, how do i build the new graph?

i don't need to know what to do in every situation, i just don't know how to deal with it and build a new graph according the demands. The steps are derived from the question itself, but i didn't get the first step in the creation of the new graph. Why there is a need to create a new graph at all?

# Answer
Allright, if I read this correctly here is what I think it should do (Some parts are possibly missing or badly formatted, but the following should make sense):

You basically copy your graph 4 times into different *layers*. Let's call them L1,L2,L3,L4

In L1, the highest Layer, every connection from the original graph instead goes down to L2.

From L2 every connection goes to L3, and from L3 to L4

Finally L4 looks like your original graph.

So if you search for the shortest path between **u** and **v** with at least three edges, you start at **u in L1** and want to end at **v in L4**

Since you can only move down **1 layer at a time**, you need at least three edges to reach v.

Take this graph as an example:

Let's assume we want to move from the left to the right, and the upper connection is the

shortest one. Then the correct answer is still to move through every other node, because taking the shortcut uses too **few edges**.

If we convert this graph we obtain the following:

Here we want to reach the **bottom right** from the **top left**. As you can see, finding a solution in this graph, automatically gives us a solution with **at least three edges**.

Note: Sorry that the vertices are not labelled, could not figure out the text function in the drawing tool I used :/
> 0 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: Why "reduce to", not the other way around?
This action confuses me for a while. As you know, once we come up with a problem and we want to know how hard it is, we will do the "reduction". Intuitively, if we prove *problem B* is as hard as *problem A*, we can know the complexity boundary of *B*. But if *problem B* is harder than *A*, why we call the reduction process -- reduce *problem A* to *problem B*, not reduce *problem B* to *A*?

# Answer
> 5 votes
There are several different types of reduction, but generally, if we say we reduce problem A to problem B, it means something like: if we had a way to solve B, we could use that to solve A. Some reductions may allow to use B as a black box. Others might require that "yes" instances of A map to "yes" instances of B, and that "no" instances map as well. Or, it may be something simpler, like "hey, I already have a great solution to problem B, and now with just a simple transform, I can use it to solve problem A." In all forms, it implies something related to "we could solve A if we had solutions to B".

What that means has something to do with what is known. If B is an easy problem to solve, then A reducing to B tells us that solving A is no harder than solving B, plus doing the reduction from A to B. In that case, an easy reduction, to an easy problem, proves that A is easy.

On the other hand, especially in the context of hardness results, we would usually reduce a known difficult problem (A here) to B, and that would show that, because A is hard, but transforming an instance of A into B is easy, B must also be hard, because if B were easy, it would give a solution to the known A problem.

So basically, for an easy reduction from A to B, it proves 2 things: A is not harder than B, and B is not easier than A. Yes, those are the same thing, but usually, you only care about one of them, depending on whether you know A to be difficult, or B to be easy.

---
Tags: terminology, reductions
---


title: regular expression of star-height 1

text:
# Question
Title: regular expression of star-height 1
Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^\*(bb^\*aa^\*ba^\*)^\*$ ?

# Answer
> 4 votes
The language has star-height 2. Note that the language includes $R\_0=(ba^+ba^+)^\*$, but is disjoint from $R\_1=(ba^+ba^+)^\*ba^+$. Therefore, it suffices to show:

Claim: If $L$ has star-height 1 and $R\_0\subseteq L$, then $L\cap R\_1\ne\emptyset$.

Suppose $L$ has star-height 1. Then we can write $L=\bigcup\_{i=1}^m F\_{i,0}^\* w\_{i,1} F\_{i,1}^\* \cdots w\_{i,n} F\_{i,n}^\*$ for words $w\_{i,j}$ and finite sets $F\_{i,j}$.

We have $(ba^kba^k)^k\in R\_0\subseteq L$ for every $k$. For $k$ large enough, there is some $F\_{i,j}^\*$ that contributes at least three $b$'s. Let us choose $k$ so large that also $k\>|w|$ for any $w\in \bigcup\_{i,j} F\_{i,j}$.

Let $u$ be the factor with at least three $b$'s contributed by $F\_{i,j}^\*$. Then $u$ decomposes into factors $u\_1,\ldots,u\_m$ from $F\_{i,j}$. Now we can clearly pick one or two consecutive $u\_\ell$'s that together form a word $f\in a^+ba^+$. We can therefore repeat $f$ and obtain a word in $R\_1$.

Update: Tried to be clearer.

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


# Question
Title: Regular expressions and semi-linear sets
In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as:

$u\_0 + \langle u\_1, \dots, u\_m \rangle = \\{u\_0 + a\_1u\_1 + \dots + a\_mu\_m \mid a\_1, \dots, a\_m \in \mathbb{N}\\}$ where $u\_i$ are vectors of natural numbers.

and a semi-linear set as a union of finitely many linear sets. It goes on to say ''For every semilinear set $S \subset N^k$, it is not hard to construct a regular set $R \subset \Sigma^\*$ such that $\psi(R) = S$'' (where $\psi$ is the Parikh map, taking strings over an alphabet $\Sigma$ to vectors where the first entry is the number of the first letter, the second entry is the number of the second letter, etc. So $\psi(\\{a, ab, ba, aaa\\})) = \\{(1), (1, 1), (3)\\}$.)

I was trying to think why regular languages would be semi-linear instead of just linear, and it seems like the + (or) operation in regular expressions is to blame. Is this correct: are languages described by regular expressions which use only concatenation and $^\*$ linear?

# Answer
> 4 votes
Your claim is correct for a one letter alphabet $\Sigma = \\{a\\}$. We prove by induction that $\psi(r)$ is linear for every regular expression without addition. When $r = a$, $\psi(r) = 1$. When $r = r\_1 r\_2$, by the induction hypothesis $\psi(r\_1) = u\_0 + \sum\_i \mathbb{N} u\_i$ and $\psi(r\_2) = v\_0 + \sum\_j \mathbb{N} v\_j$, and so $\psi(r) = u\_0 + v\_0 + \sum\_i \mathbb{N} u\_i + \sum\_j \mathbb{N} v\_j$. When $r = r\_1^\*$, $\psi(r)$ is a subset of $\mathbb{N}$ closed under addition. Let $g = \operatorname{gcd}(\psi(r))$. Then $\psi(r)/g$ is a numerical semigroup, and so finitely generated, say $\psi(r)/g = \sum\_i \mathbb{N} u\_i$. So $\psi(r) = \sum\_i \mathbb{N} gu\_i$.

This argument doesn't quite work when $|\Sigma| \geq 2$, although there are some notions of GCD for multidimensional vectors, see for example this interesting presentation by Vadim Ponomarenko. Perhaps the argument above can be pushed through, or perhaps a different argument, which uses the fact that $\psi(r\_1)$ is linear, exists. It's also possible that the claim is wrong in this case.

# Answer
> 2 votes
The claim fails for two symbols. The Parikh image $M\subseteq \mathbb{N}\times\mathbb{N}$ of $(abb^\*)^\*$ is not linear:

It is easy to see that for every finitely generated submonoid $N$ of $M$, there is a $k\ge 0$ such that for every $(x,y)\in N$, we have $x\le ky$ and $y\le kx$. This, however, is not satisfied by $M$ itself, meaning $M$ is not finitely generated.

Now as a submonoid of $\mathbb{N}\times\mathbb{N}$, $M$ is linear iff it is finitely generated.

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