# Question
Title: Regular set corresponding to regular language
I have just started learning regular expressions and I don't have anybody around me to help me building conceptions. So I rely on online mediums. My question is **whether every regular set corresponds a language**.

I had a regular expression $(0+10^\*)$ and I was trying to find the regular sets. My books suggests that $L=\\{0, 1, 10, 100, 1000, 10000,\ldots\\}$. But I was thinking why they did not consider the strings starting with $0$ and then only one $1$ and zero or more number of occurrences of $0$, like $010, 0100, 01000$ etc.

1. Aren't these strings belong to $L$?
2. Is this $L$ a language? (According to me, it is a language because it is the set of strings over $\\{0,1\\}$.

# Answer
> 1 votes
A regular language $L$, is a set over the alphabet $\Sigma$ (that is, $L\subseteq \Sigma^\*$) that has a regular expression that generates it. Therefore, by definition - any language of a regular expression is a regular language.

Regarding the language in question, $01$ for example is not generated by $(0+10^\*)$, since it is not $0$ and also is not generated by $10^\*$ (since it doesn't start with $1$). The same goes for any string starting with $0$, and has more than one letter in it.

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


# Question
Title: Why merge into the larger tree in union by rank
When we do union by rank we merge the smaller tree into the larger tree. I dont understand why we do this exactly?

# Answer
Imagine merging the larger tree into the smaller one. By doing this, you are guarantying that the new tree will have depth one more than the larger tree's depth. But, if you were to merge the smaller tree into the larger one - the increase in depth would occur only in the branches of the small tree, and since it is small it wont impact the depth (unless the smaller tree is the same size as the larger tree).

So to summarize - by doing this you ensure to create the lowest possible depth you can.

---

Try to run on some examples both cases (merging largest to smallest and merging smallest to largest) and see the differences for yourself
> 2 votes

---
Tags: union-find, rank
---


# Question
Title: Show that a language with union is not regular by using pumping lemma
Given the language $L:= { \\{ c^{2k} w \ \vert \ k \ge 1, \ w \in \\{a,b,c\\}^\* \ and \ \vert w\vert\_a \ = \ \vert w\vert\_b \\} \ \cup \ \\{ a,b \\}^\* }$

I'm really unsure how to even start because of the union.

I tried it with $w=a^nb^n$ but my correction said that it's pumpable because it is in $\\{ a,b \\}^\*$ which makes sense.

What would be a good word to start with? I guess there are several cases i need to show?

# Answer
> 1 votes
If $L$ was regular, so would be $L \cap c^+\Sigma^\* = \\{c^{2k}w\mid k\geq 1, w\in\\{a,b,c\\}^\* \text{ and }|w|\_a = |w|\_b\\}$.

That means that if you prove that this language is not regular, then $L$ cannot be regular too (that way, we got rid of the union).

Now you can take it from here with pumping lemma, starting from $c^2a^nb^n$!

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


title: Checking two properties of a tree

text:
# Question
Title: Checking two properties of a tree
I have the following definition:

A green-blue tree is a binary tree that follows the following properties:

* Each green node has only blue descendants.
* Every path that goes from a node to a leaf has the same number of blue nodes.

This is an example of a green-blue tree:

For the first part, we can ensure that every node has only blue descendants in $O(n)$, being $n$ the number of nodes. The algorithm could be as follows:

```
bool descendants_condition(node):
    if node == nullptr:
        return true
    if node.info == green;
        return descendants_condition(node->left) and
               descendants_condition(node->right);
    else:
        return only_blue_nodes(node->left) and
               only_blue_nodes(node->right);

```

For the second part, I'm trying to avoid checking every path from every node to the leafs. I have the following intuition:

* If a node is a leaf, the condition is satisfied
* If a node is not a leaf, we should have the same number of blue nodes in the right and in the left.

However, this is not enough for me, and I would like to see a proof of this condition.

# Answer
> 1 votes
This is **not** a proof for the statement (since the statement is incorrect if the tree is not balanced), but rather another way to think and solve the problem.

Notice that in any path from the root to a leaf, say $v\_1,\dots, v\_k$ we must have that the number of green nodes is **at most** $1$ (by the first property). Also, notice that the number of blue nodes in the path, is the depth of the leaf $v\_k$ minus either one or zero, depending on whether there was a green node in that path.

So, in order to count the number of blue nodes in a path you have to do the following two things:

1. Write at every leaf its depth (can be done in $O(n)$)
2. Write at every leaf whether there was a green node in the path from the root to it (think about it, it also can be done in $O(n)$)

Then finally you go through all leaves, calculate the number of blue nodes using this information, and make sure all leaves have the same value of it.

---
Tags: binary-trees
---


# Question
Title: Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular
> Let $\Sigma=\\{0,1\\}$ and $L$ be a regular language. Prove that $$Z(L) = \\{x \in \Sigma^\* : \exists w \in \Sigma^\* \ xww \in L \\}$$ is a regular language.

I tried to build a NFA based on the DFA that accepts $L$ but failed to do so. I don't know how to ensure the $\\, ww \\,$ part. Please advise.

# Answer
> 2 votes
Let $A = (Q, \delta, q\_0, F)$ a DFA that accepts $L$. For $q, q' \in Q$, define:

* $L\_{q,q'} = \\{u\in \Sigma^\*, \delta^\*(q, u) = q'\\}$;
* $L\_{q',F} = \\{u\in \Sigma^\*, \delta^\*(q', u) \in F\\}$.

It is quite easy (can you prove it?) to see that those languages are regular.

Now the language $\\{x\in \Sigma^\*\mid \exists w\in\Sigma^\*, xww\in L\\}$ can be written as: $$\bigcup\limits\_{q\in Q}L\_{q\_0,q}\cdot M(q)$$ Where $M(q) = \left\\{\begin{array}{rl}\emptyset&\text{if }\bigcup\limits\_{q'\in Q}L\_{q,q'}\cap L\_{q',F}=\emptyset\\\\{\varepsilon\\}&\text{otherwise}\end{array}\right.$

$M(q)$ is regular since it is either $\emptyset$ or $\\{\varepsilon\\}$, so that means that $Z(L)$ is regular.

# Answer
> 2 votes
The operator $Z(L) = \\{ x \mid xww\in L \text{ for some } w\\}$ takes strings from the original language $L$ but keeps only prefixes $x$ that are obtained by chopping a suffix of the form $ww$.

This is a special application of the right quotient operation: $L/K = \\{ x \mid xy\in L \text{ for some } y\in K\\}$.

It is known that the family of regular languages is closed under right quotient of *arbitrary* languages, see Show L1 /L2 is regular. For your problem take $K = \\{ww\mid w\in \Sigma^\*\\}$.

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


# Question
Title: If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$
Language $L$ is trivial if $L=\varnothing$ or $L=\Sigma^\*$. I'm trying to prove the following theorem:

> If $L\_1\in R$ and $L\_2$ is non-trivial language then $L\_1\leq L\_2$.

If $L\_2$ is non-trivial the $L\_2\neq\varnothing$ and $L\_2\neq\Sigma^\*$. If I want to prove that $L\_1\leq L\_2$, then I need to show that there exists $f:\Sigma^\*\to\Sigma^\*$ which is total, can be calculated by a Turing machine and follows: $\forall x\in\Sigma^\*$, $x\in L\_1$ iff $f(x)\in L\_2$. I also know that $L\_1\in R$ then there is a turing machine $M\_1$ that decides language $L\_1$. But how do I continue from here? How $f$ should look like?

# Answer
We know there are two $x\_1,x\_2\in \Sigma^\*$ such that $x\_1\in L\_2$ and $x\_2\notin L\_2$, since $L\_2$ is not trivial. Now, we will build the following reduction:

$f(x)=\cases{x\_1 & $x\in L(M\_1)=L\_1$ \\ x\_2 & otherwise}$

Notice that $f$ is computable: calculate $M\_1(x)$, and output either $x\_1$ or $x\_2$ according to the answer you got.
> 1 votes

---
Tags: computability, reductions
---


# Question
Title: Finding the language generated by this grammar
I'm having problems with this. Can someone help me please.

Find the language generated by this grammar over the alphabet $\\{0,1\\}$:

> $S\rightarrow BAB\mid CAB$
>
> $BA \rightarrow BC$
>
> $CA \rightarrow AAC$
>
> $CB \rightarrow AAB$
>
> $A\rightarrow 0$
>
> $B \rightarrow 1$

# Answer
Suppose the starting rule is $S\rightarrow CAB$. Then the only possible derivation is:

$$S\rightarrow CAB \rightarrow AACB \rightarrow AAAAB \rightarrow^\* 00001$$

That means that most of the work is done with the other starting rule. To find any derivated word, we can start by noting that the nonterminal symbol $C$ cannot be rewrited as a terminal symbol. It means that we can consider replacing $A$'s with $0$'s and $B$'s with $1$'s in words written with only $A$'s and $B$'s. Let's try to find some derivated words:

$$S\rightarrow BAB\rightarrow BCB\rightarrow BAAB\rightarrow BCAB\rightarrow BAACB$$

Now we can conclude that $101\in L$ and $1001\in L$ (because we reached $BAB$ and $BAAB$), but at $BAACB$, two rules are possible.

* $BAACB\rightarrow BAAAAB$ (so $100001\in L$)
* $BAACB \rightarrow BCACB$

Let's continue the the last derivation (taking shortcuts at the end):

$$BCACB\rightarrow BAACCB\rightarrow BAACAAB\rightarrow BAAAACAB\rightarrow BAAAAAACB\rightarrow BA^8B \rightarrow BCA^7B\rightarrow^\*BA^{14}CB\rightarrow^\*BA^{16}B$$ That means that $10^81\in L$ and $10^{16}1\in L$.

I think you can find a pattern from here to find the words of $L$ beginning with a $1$. The difficult part is showing that no other word is in $L$ than those ones.
> 0 votes

---
Tags: formal-languages, automata, finite-automata, formal-grammars, chomsky-hierarchy
---


title: How to prove that $L_{D}\leq L_{U}$?

text:
# Question
Title: How to prove that $L_{D}\leq L_{U}$?
I have the following two languages: $$ L\_{U}\triangleq\left\\{ \langle M,x\rangle\\,:\\,M\text{ accepts }x\right\\} ,L\_{D}\triangleq\left\\{ \langle M\rangle\\,:\\,M\text{ accepts }\langle M\rangle\right\\} $$ I'm trying to prove that $L\_{D}\leq L\_{U}$. For that I need to show that there exists $f\\,:\\,\Sigma^{\*}\to\Sigma^{\*}$ total, can be calculated by a Turing machine and follows: $\forall x\in\Sigma^\*$, $x\in L\_D$ iff $f(x)\in L\_U$.

Let there be $f\\,:\\,\Sigma^{\*}\to\Sigma^{\*}$ so $f\left(\langle M\rangle\right)=\langle M,M\rangle$. I have proved that $f$ is total and also follows the last condition. All that left to do is to prove that $f$ can be calculated by a Turing machine. How should I describe the steps of machine $M\_f$ on $\langle M\rangle$?

# Answer
> 0 votes
It is the turing machine that clones its input. If you want a description of this machine's operation, you may find this useful.

---
Tags: computability, reductions
---


# Question
Title: Is a Turing Machine a Well-formed formula?
Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me. But is it correct when we say that a Turing Machine is a WFF ?

# Answer
> 2 votes
Yes and no. Turing machines *aren't* WFF, but can be encoded as a WFF. The definition of TMs uses sets and functions (which aren't symbols in the alphabet), but its possible to create a one-to-one encoding from TMs to WFF. Usually, given a TM $M$, we refer to its encoding as $\langle M\rangle$.

---
Tags: formal-languages, turing-machines, logic
---


# Question
Title: Is there a complexity metric for finite state machines?
I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each Turing machine as one of the criteria to guide the evolution process.

However, I couldn't find any references as to a canonical complexity metric for FSMs. I imagine the metric would include some combination of the number of states, number of transitions, and number of input symbols, but I'm not sure how these would be combined appropriately into a normalized metric.

Is there a canonical (ideally normalized) complexity metric for finite state machines?

# Answer
Yes, there is a canonical complexity metric for finite state machines: the number of states. It's as simple as that.

The number of transitions or input symbols don't matter (for this standard, canonical metric). We don't use a normalized metric based on the combination of such values. We just count the number of states.
> 9 votes

# Answer
If you set aside the mathematical definition of complexity for FSMs (in @D.W.'s correct answer), from a systems engineering perspective, there is no agreed-upon algorithm or formula for measuring the complexity of any process. However there are a lot of good ideas for measuring complexity of computer programs in the references below. Look for mention of "McCabe cycolomatic complexity", "number of states/nodes", "number of transitions/edges", etc:

The last reference to "Halstead Complexity Measures" gives formulas for practical measures like **volume**, **difficulty**, and **effort** for any computer program (including FSMs). Halstead even proposed formulas to estimate the likely number of "Bugs Delivered."
> 4 votes

# Answer
In case your finite state machines are "programs" of some sort, and you want to obtain the simplest program, it may make sense to use the length of the program corresponding to the FSM as your complexity metric, for some hypothetical mapping of FSMs to programs: e.g., $$\text{numTransitions} \cdot (\log(\text{alphabetSize}) + \log(\text{numStates}))$$ could be reasonable, as each transition requires $O(\log(\text{alphabetSize}) + \log(\text{numStates}))$ bits to encode.
> 2 votes

# Answer
You could take the three-dimensional **vector** (states, transitions, symbols) as your measure of complexity.

* Disadvantage: you get incomparable levels of complexity.
* Advantage: you retain all the information.
> -1 votes

---
Tags: turing-machines, finite-automata
---


# Question
Title: Generate 3D "matrix" with Pandas, based on comparing two dataframes [Python]
Good morning everyone. I am working with Python and Pandas.

I have two DataFrames, of the following type:

```
df_C = pd.DataFrame(data=[[-3,-1,-1], [5,3,3], [3,3,1], [-1,-1,-3], [-3,-1,-1], [2,3,1], [1,1,1]], columns=['C1','C2','C3'])

   C1  C2  C3
0  -3  -1  -1
1   5   3   3
2   3   3   1
3  -1  -1  -3
4  -3  -1  -1
5   2   3   1
6   1   1   1

df_F = pd.DataFrame(data=[[-1,1,-1,-1,-1],[1,1,1,1,1],[1,1,1,-1,1],[1,-1,-1,-1,1],[-1,0,0,-1,-1],[1,1,1,-1,0],[1,1,-1,1,-1]], columns=['F1','F2','F3','F4','F5'])

   F1  F2  F3  F4  F5
0  -1   1  -1  -1  -1
1   1   1   1   1   1
2   1   1   1  -1   1
3   1  -1  -1  -1   1
4  -1   0   0  -1  -1
5   1   1   1  -1   0
6   1   1  -1   1  -1

```

I would like to be able to "cross" these two DataFrames, to generate or one in 3D, as follows:

The new data that is generated must compare the values of the **df\_F** with the values of the **df\_C**, taking into account the following:

* If both values are positive, generate 1
* If both values are negative, generate 1
* If one value is positive and the other negative, it generates 0
* If any of the values is zero, it generates None (NaN)

***True table***

Comparison of the data **df\_C** vs **df\_F**

```
df_C vs df_F = 3D
  +       +     1
  +       -     0
  +       0     None
  -       +     0
  -       -     1
  -       0     None
  0       +     None
  0       -     None
  0       0     None

```

You, who are experts in programming, could you please guide me, as I generate this matrix, I compare the values. I wish to do it with Pandas. *I have done it with loops (for) and conditions (if), but it is visually unpleasant* and I think that with Pandas it is more efficient and elegant.

Thank you.

# Answer
The first step is to observe that the relationship can be achieved by multiplication of signs. With `numpy.sign(x)` we get 0 if x is zero, 1 if positive and -1 if negative, since you check for sign equality, multiplication by the same sign value will always be 1, multiplication by 0 always yields 0 and multiplication by opposite signs yields -1.

```
import numpy as np
Cs = np.sign(df_C.values)
Fs = np.sign(df_F.values)

```

The next step is to make the correct kind of broadcast. Using `A[:, None]`, we introduce a new dimension after the first:

```
assert Cs[:, None].shape == (7, 1, 3)

```

So we will expand F with an additional dimension in the middle, so that we can do element wise multiplication of every value in the column of F with one value in the column of C. We also need to expand C, so that the last axis has just a single value.

```
F2 = Fs[:, None]
C2 = Cs[:,:, None]

```

Finally, we multiply and cache the intermediate values so that we can use `np.where` to replace 0 with None and -1 with 0. However, you should keep -1,0,1 as it uses less memory, avoids multiple copies and is easier to work with.

```
S = F2*C2
assert S.shape == (7,3,5)
S = np.where(S==0, None, S)
S = np.where(S==-1, 0, S)

```
> 1 votes

---
Tags: python
---


# Question
Title: $\epsilon$-approximation Sub-linear time monotonicity testing
I have the following exercise I have been staring at for several hours to no avail.

**Question:**

Testing the monotonicity of a function - the case of bits: Given a function $f: \[n\] \rightarrow \\{0,1\\}$ and a parameter $0 \< \epsilon \< 1$, show an algorithm that runs in $O(\frac{1}{poly(\epsilon)})$ queries to $f$, with the following behavior:

* if $f$ is monotone (i.e $\forall x, y \in \[n\]$ if $x \le y$ then $f(x) \le f(y)$, then the algorithm always outputs "yes"
* if $f$ is $\epsilon$ far from monotone, then the algorithm outputs "No" with probability at least $\frac {3}{4}$.

**Definition of $\epsilon$-far:**

A list $a$ is $\epsilon$-far from a list $b$, both of length $n$ iff they differ in more than $\epsilon n$ indices.

I will greatly appreciate help, and show my (stale) thought process.

---

## My thoughts:

Consider the following algorithms

**Alg1**

1. Pick a uniformly random position $i$ between $1$ and $n$.
2. let $v\_i$ be the value at position $i$ in the list.
3. Use binary search to look for the value $v\_i$ in the list.
4. If the binary search reported $i$ as the position of $v\_i$ then
5. return Yes
6. else
7. return No

which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, it returns "No" with probability at least $\epsilon$.

---

**Alg 2**

1. Let $ h \leftarrow \lceil \frac{2}{\epsilon} \rceil $
2. Execute $h$ independent copies of Alg1 on the input list.
3. If all the copies answer "Yes"
4. Return Yes
5. Else
6. Return No

which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, Algorithm 3 detects it is not sorted, with probability at least $\frac{2}{3}$

It is also proven to be of (query) complexity

$h lon(n) = \lceil \frac{2}{\epsilon} \rceil O(log(n)) = O(\epsilon ^{-1} log(n))$

---

## What to do with all that?

I thought I could use **Alg 2** for the case of the binary function $f$, and to find out if it is non-decreasing.

The problem is, binary search has too many queries.

So I have to skip the search, and probably use some kind of sampling.

---

Let's say I uniformly sample $k$ indices of the list, and later force $k=o(\frac{1}{\epsilon})$.
I will then test monotonicity on the sample, and return an answer accordingly.

I haven't the slightest idea if this holds the required probability constraint, or how to augment so it does.

I thought maybe it would make prooving easier if I were to use the number of indices in the sample, between the leftmost "1" to the rightmost "0" as a proxy for the probability bound, but this is as far as I went.

---

I will appreciate direction to this, or even a solution at this point.

# Answer
> 3 votes
Let $P$ denote the number of pairs of indices $i\<j$ such that $f(i)=1$ and $f(j)=0$, and let $C$ be the minimal number of flips required to make $f$ monotone. First, we show by induction on $n$ that for every function $f$ defined on $\[n\]$ it holds that $C^2\le 3P$.

Suppose that the claim holds for $n$ and let $f$ be a function defined on $\[n+1\]$. We denote by $C(n),P(n)$ the number of corrections and monotonicity violating pairs for $f|\_{\[n\]}$ correspondingly. Finally, let $w(n)$ denote the weight of $f$, i.e. $w(n)=\big|f^{-1}(\\{1\\})\cap\[n\]\big|$. Observe that if $f(n+1)=1$ then $C(n)=C(n+1)$ and the claim clearly holds, it thus suffices to focus on the $f(n+1)=0$ case. If $f(n+1)=0$ then $P(n+1)=P(n)+w(n)$ and $C(n+1)\le C(n)+1$. Applying the inductive hypothesis $C^2(n)\le 3P(n)$ we have:

$$C^2(n+1)\le C^2(n)+2C(n)+1\le 3P(n)+2C(n)+1=\\3P(n+1)+2(C(n)-w(n))- w(n)+1 \le 3P(n+1),$$

since $C(n)\le w(n)$ and $w(n)\ge 1$ (the claim is trivial for the constant zero function). This concludes the proof.

The above inequality yields a simple algorithm for testing monotonicity. Sample a pair $i\<j$ uniformly at random and answer "no" if $f(i)\>f(j)$. Let $q$ denote the probability that $i,j$ is such a pair, then $q\ge \frac{P}{n^2}\ge \frac{C^2}{3n^2}\ge \frac{\epsilon^2}{3}$. By repeating this procedure $\approx q^{-1}$ times, you obtain an $O\left(\frac{1}{\epsilon^2}\right)$ algorithm for separating the monotone from the $\epsilon$-far from monotone case.

---
Tags: algorithms, complexity-theory, sorting, approximation, streaming-algorithm
---


title: Find a repeated element in linear time

text:
# Question
Title: Find a repeated element in linear time
Given an array of $n$ elements, containing values in the range $\[1, n-1\] $ (assume $ n \> 1 $) this implies there is at least one repeated element. The problem is to get one of the repeated values in linear time on average.

My first try was to do something with the Partition scheme from Quicksort. However, I don't know how to address the following problem:

* We can divide the problem selecting a pivot, and then for each value $ \<= $ than the pivot, we know that they will be in the range $0..n/2 - 1$, and the following values $\>$ than the pivot, they will be in $n/2 + 1..n$.

I can't check both of those partitions, because the cost would be $O(n\log n)$ per Master Theorem.

The only way I think I can do it is only checking left or right, however, i.e., if the repeated element was in the left and I check the right, is going to be somewhat the same.

So my intuition is telling me that maybe, if I check first the left part for this condition, and after that, the right one in some recursive manner, this is going to give me a linear algorithm on average. Am I right or is there any better way to do it?

Edit: the divide and conquer approach is mandatory

# Answer
> 1 votes
If you choose $\frac{n}{2}$ as the pivot to do the partition, you just need then to continue the search in the half containing strictly more than $\frac{n}{2}$ elements.

That way you don't have to check both halves.

---
Tags: algorithms
---


# Question
Title: Solving a problem with instance of size $n$ in $O(n)$
Today I read the following text in CLRS:

> We say that an algorithm solves a concrete problem in time $O(T(n))$ if, when it is provided a problem instance $i$ of length $n = |i|$, the algorithm can produce the solution in $O(T(n))$ time

It is ambiguous for me, because if we consider a problem in which a number $n$ is given and we have to print $1$ for $n$ times, and our input is the number $n$ in binary format, our input has a size of $O(lg(n))$, and since we do an action $n$ times, the algorithm runs in $O(n)$, and since $O(n) = O(2^{lg(n)})$, the algorithm is exponential.

What am I doing wrong here?

# Answer
You are not doing anything wrong. Typically, you would want to consider the running time with respect to some variable defined in the question. In this case, you could either consider it to be linear in $n$, or to be exponential in the number of bits in the input.

When talking about formal algorithms in the context of turing machines, the running time is defined with respect to the size of the input (which in this case would result in an exponential algorithm).

In other contexts, the running time is usually calculated with respect to one of the following things:

1. Number of elements in the input list, if the problem's input is a list
2. The values given in the input (for example, $n$ in this case)
3. The size of the input in bits
> 1 votes

---
Tags: time-complexity, np-complete
---


# Question
Title: Regex for strings with even number of 1's and number of 0's divisible by 5
I was trying to build up this regex but I am having huge expressions but nothing generates the given regex. I tried to break up the regex as

1. $0$ multiple of five times and odd $1$'s
2. $0$ multiple of five times and even $1$'s

Bu this doesn't help me.
The regex I Found was $(00)^\*1(00)^\*1(00)^\*1(00)^\*1(00)^\*$. But in this way two $1$'s and five $0$'s cannot be generated.
Again $(11)^\*0(11)^\*0(11)^\*0(11)^\*0(11)^\*$ does not generate $5n$ times $0$'s for $n\ge 2$.
There are other possibilities and that too do not meet the regex.

Any help would be appreciated.

**P.s: I am at the very beginning in regex. So I am currently trying to avoid the method of conversion from finite automata to regular expressions.**

# Answer
> 1 votes
Your last idea is good, but insufficient. Also there is not the right number of zeros. Now let's try to decompose the problem:

Let's consider $L\_0=\\{1^i01^j01^k01^l01^m01^n,i+j+k+l+m+n \text{ is even}\\}$.

Your (corrected) idea was $e\_1 = (11)^\*0(11)^\*0(11)^\*0(11)^\*0(11)^\*0(11)^\*$, but this only generate words of $L\_0$ where $i, j, k, l, m, n$ are all even. You need now to consider other possibilities. For example, if $j$ and $m$ are odd and the rest are even, we get the regular expression: $$(11)^\*0(11)^\*10(11)^\*0(11)^\*0(11)^\*10(11)^\*$$ There are a total of $\binom{6}{0} + \binom{6}{2}+\binom{6}{4}+\binom{6}{6} = 32$ expressions to consider all possibilities (choice of an even number of indices that are odd among the 6).

The final regular expression will then be $\left(e\_1+e\_2+…+e\_{32}\right)$.

Now you need to do the same thing with a language $L\_1$ containg an odd number of $1$'s, and construct the regular expression for your language with both $L\_0$ and $L\_1$.

This sure is ugly as hell, but hey, it works! There may be a simpler way to write it, but I'm not so sure.

---
Tags: regular-expressions
---


# Question
Title: Algorithm to construct a parabola that hits a given target and avoids given boundaries
I'm working on a video game and I'm struggling with the math behind one of the enemies. The enemy is a grenade launcher mounted on a vertical rail, which can slide up and down, and lob a grenade at any angle with any amount of force. The grenade's path will be a parabola which must hit the player, but there are line segment boundaries in the way represented by their two endpoints which the parabola must avoid.

Here is a drawing:

What I'd like to do is calculate the equation for the parabola of the grenade which hits a target and misses all of the boundaries, from which I can figure out the position, angle, and force for the launcher to use. The parabola must be subject to these three constraints:

1. The parabola must pass through the target point $(x\_T, y\_T)$
2. The parabola must pass through the line segment $\overline{RS}$
3. For each boundary $\overline{EF}$, if the parabola passes through the segment, it must not happen between the line $\overline{RS}$ and the target point.

Depending on where the target is, there may be no solution, in which case I'd like it to return that information. If there is any solution there will be multiple; I would only need one.

## What I've tried so far:

We can represent the parabola as $y-y\_T=A(x-x\_T)^2+B(x-x\_T)$, which takes care of the first constraint, and means we need to find values for $A$ and $B$ that satisfy the other two constraints (we know $A$ must be negative because of the direction of gravity). Then for each boundary $\overline{EF}$ on the map, with endpoints $(x\_E,y\_E)$ and $(x\_F,y\_F)$, we can represent the boundary line as $(y\_E-y\_F)x+(x\_F-x\_E)y+(x\_E y\_F-x\_F y\_E)=0$. From that I can find the points of intersection between the line and the parabola, and make sure that for every boundary, the x-values of the points are either not between $x\_E$ and $x\_F$, or they are not between $x\_S$ and $x\_T$. This quickly becomes a nasty quadratic equation, which then creates a system of linear inequalities that I don't know how to solve. Can anyone think of a better way to approach the problem?

# Answer
> 1 votes
Consider an endpoint $(x\_E,y\_E)$ of an obstacle line segment. I'm going to assume for simplicity that if the projectile goes exactly through $(x\_E,y\_E)$, this is a legal trajectory, i.e., it's OK for a projectile to "just graze" the obstacle. (If that's not OK, it is easy to adjust the solution below to just miss the corner by a tiny amount $\epsilon$, or it is easy to adjust the size of each obstacle by $\epsilon$ in each direction.)

Let's define a "grazing constraint" as one of the following possibilities:

* If the point $E$ is a vertex of an obstacle (i.e., an endpoint of an obstacle line segment) or is $R$ or $S$, then "The parabola must go through $E$" is a grazing constraint.
* If $EF$ is an obstacle line segment, then "The parabola intersects $EF$ and is tangent to it" is a grazing constraint.

In this way, given $n$ obstacle line segments, we obtain $2n+2$ possible grazing constraints.

Now I make two claims:

Claim 1: Any two grazing constraints uniquely determine the parabola.

Proof: If both grazing constraints are of the "must go through E" type, then together with the target $T$, we have three points, and any three points uniquely define a parabola, i.e., given three points, there is a unique parabola that goes through those three points. A similar argument can be made if one or both of the grazing constraints are of the "tangent" type.

Claim 2: If there is any solution to your problem, there is a solution that satisfies two of the possible grazing constraints listed above.

(I don't have a proof for this claim.)

This immediately suggests a simple algorithm: enumerate over all pairs of grazing constraints, find the unique parabola that satisfies those two grazing constraints and goes through the target $T$, and check whether this parabola avoids all obstacles and intersects the starting line segment RS. You can check whether it avoids all obstacles by iterating over all obstacle line segments, and for each, finding the intersection using the method you described. If there is a valid solution to your problem, this method will find it.

The running time of this method will be something like $O(n^3)$, where $n$ is the number of obstacle line segments. I don't know if there is a more efficient method. There might well be.

---
Tags: algorithms, computational-geometry, algebra
---


# Question
Title: How to prove that EMPTY is not recursively enumerable?
I need to prove that the following language is not recursively enumerable, while its complement is recursively enumerable: $L := \\{w \in \\{0,1\\}^\* |$ TM $M$ with $w = \langle $ M $\rangle$ does not accept any input $\\}$.

Should I use a reduction from the halting problem in this case?

# Answer
> 1 votes
You can directly use the extension of Rice's theorem to prove that $L\notin RE$

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


# Question
Title: Edge exchange property of two Minimum Spanning Trees
Given an undirected graph `G` with weight on its edges and 2 `different` minimal spanning trees(MSTs): T, T'

Then I want to prove the following:

> For every edge `e` in T that's not in T', there is an edge `e'` in T' that's not in T such that if we replace `e` with `e'` in T (let's call it T\_new) then it's still a minimal spanning tree of `G`.

I think I am too close for finding the right algorithm but stuck a little:

1. I have proved that `weight(e)` must be exactly equal to `weight(e')`.
2. Since T is a tree, deleting e will result in 2 separated components, then for T\_new to be a tree it must use one of the edges connecting two vertices from those different components.

**But**, I wasn't able to know which edge `e'` exactly will work. Plus I wasn't able to prove that **always** there is such an edge (I just found some requirements for `e'` that is must satisfy).

Some notes: I know Kruskal algorithm, and familiar with an algorithm in which we can paint some edges in yellow and request it to generate minimal spanning trees with maximum yellow edges (In other words from all found minimal spanning trees return the one with maximum number of yellow edges)

# Answer
Here is a proof. Let $V$ be the vertices of $G$. $V$ are also the vertices of $T$ and the vertices of $T'$.

If $e$ is deleted from $T$, we will get two trees. Let the vertices of these two trees be $(V\_1, V\_2)$, which is a cut of $V$.

Since $T'$ is a tree, if we add $e$ to it, we will obtain a cycle. Since that cycle crosses $(V\_1, V\_2)$ at $e$, it must cross $(V\_1, V\_2)$ at another edge, say, $e'\in T'$.

* Since $T \setminus \\{e\\}\cup \\{e'\\}$ is a spanning tree of $G$ and $T$ is an MST, $\text{weight}(e) \le \text{weight}(e')$.
* Since $T' \setminus \\{e'\\}\cup \\{e\\}$ is a spanning tree of $G$ and $T'$ is an MST, $\text{weight}(e') \le \text{weight}(e)$.

So, $\text{weight}(e) = \text{weight}(e')$.

$T \setminus \\{e\\}\cup \\{e'\\}$, which is a spanning tree of the same weight as $T$, must be an MST of $G$. $\quad\checkmark$
> 7 votes

# Answer
Add an edge to a spanning tree and you have a cycle. Deleting any edge in that cycle results in a new spanning tree.
> -1 votes

---
Tags: algorithms, graphs, trees, minimum-spanning-tree
---


# Question
Title: Is this a general compression algorithm?
I'm aware that an algorithm that compresses every input doesn't exist (by the pigeonhole principle), however I tend to think about the problem sometimes and I came up with a (flawed, but why?) idea:

Suppose a file, or whatever it is that will be compressed. It can be represented with a number (we can actually invert the bits if the first binary digit of the file is one, and indicate whether we've flipped them or not, since computers work based on bytes, but that is detail) if we treat its bits as the base-2 representation of the number. Let such number be $n$.

It is computationally cheap ($O(\log{n})$) to find $floor(sqrt($n$))$.

We find $x\_1 = floor(sqrt(n))$ and then take $y\_1 = n - (floor(sqrt(n)))^2$. Then we do it again (this time, taking $floor(sqrt(y\_1))$, where $y\_1$ is the new value we obtained from the subtraction) and again until we have expressed $n$ as a sum of perfect squares, following that rule. Something like $x\_1^2 + x\_2^2 + ... + x\_w^2$. We know, since we are **at least** dividing $n$ by two every step, that $w$ is of order $\log(n)$.

Noting that $x^2$ is equal to the sum of the first x odd numbers, we then express the squares, logically, to better understand the idea, as shown in the image:

The first line of the image represents the first square obtained from the process, the second line represent the second square obtained and so on. A random representation was chosen just to illustrate, but imagine the polygon as being the representation of any number. If we are able to precisely determine the polygon for a given $n$, we know $n$. Notice once we represent the numbers this way, we can group them in the following order:

The first red rectangle is the product of ($1+3+5$) = $(3^2)$ by however many lines the rectangle occupies. The second one is the product of ($(1+3+5+7+9+11)-(1+3+5)$) = $(6^2 - 3^2)$ by however many lines the rectangle occupies, and so on. The green square, which represents the one (may or may not exist in a given $n$ representation), is a special case.

Abstracting a bit more, given the following image:

If we know the purple points, we know the figure and, thus, we know $n$. In order to specify the purple points, we need to specify the distances in blue and the distances in brown. The vertical side of the polygon is of order $O(\log(n))$, since it is related to how many initial squares we had. The vertical side, on the other hand, is of order $O(sqrt(n))$, since they're related to $sqrt(n)$ (the representation of the square root).

What is particularly interesting, however, is that by specifying this first purple point, we are able to, in fact, infer all the other purple points and all the other brown vertical distances, provided we have registered the purple horizontal distances. To see this, imagine we are in the first brown point. We then see the next horizontal distance and are able to know exactly the next vertical distance (and consequently the brown point); we know how the pattern continues. We know how many lines we have total, since we are able to "see" the first red rectangle (and the green square if we specified it or not). We further know that **the vertical distance between one point and the next point is always one**, due to the fact that no two lines are equal (since they represent different squares). Point is, given the basic representation of the first vertical distance, we know all the vertical distances.

Maybe it is possible to represent the first brown distance with fewer bytes increasing its exponent or tweaking it somehow. I had an idea in mind but I just realized it's flawed. And the blue distances would need to be represented (they can be taken as a new $n$ and all the process repeated again).

Also, it's worth noting that the the horizontal distances relate to the previous horizontal distances because when we made the squares for $n$, the subtraction $n - floor(sqrt(n))^2$ is taken as the new $n$, and is represented as $x\_m$, but $n - floor(sqrt(n))^2$ is always between $1$ and $2floor(sqrt(n)) - 2$ (if it were 0, it would be a perfect square, so great; if it were $2floor(sqrt(n)) - 1$, it could be integrated into $x\_m^2$, so it can never be that (nor greater than that)).

Anyhow, I am sorry if the explanation is a bit messy. I just had to share my ideas and ask whether it's worth implementing something related to the idea above in order to test it, or it is a waste of time. That is, if the approach is good (most likely, perhaps impossibly likely, as said in the beginning, to not be the case). Thanks! Edit: it is proven to be impossible to compress every input, what I meant to ask was whether this approach would be useful for most of the inputs or thoughts on the approach in general and why it doesn't work.

# Answer
At its core what you propose is splitting a number $n$ into two, a square part and a remainder:

$$s=\lfloor\sqrt{n}\rfloor, \quad\quad r=n - s^2$$

Encoding $s$ requires $\log\_2(s) = \log\_2\lfloor n^{1/2} \rfloor \approx \frac{1}{2}\log\_2 n$ bits. And as you said, $$1 \leq r \< 2s$$ thus we can say that in the worst case $r$ requires $\log\_2 r \approx \log\_2(2s) \approx 1 + \frac{1}{2}\log\_2 n$ bits to encode.

So in total we're actually roughly one bit worse off in the worst case. Note that the above is kind of sloppy, but should give you an intuition as to why it doesn't work. If you want to *prove* that it doesn't give you general compression, just use the pigeonhole principle - it's much simpler.
> 2 votes

# Answer
The information theoretic argument -- the so-called pigeon hole principle -- also shows that it is impossible to compress "most" inputs. You can only compress a minority inputs, and the fraction of successfully compressed inputs decreases with increased compression.

Suppose we were compressing bit sequences of length $N$. There are $2^N$ such sequences. As a very modest goal, we'll just compress the sequences by one bit, so that the compressed result has $N-1$ bits. But there are only $2^{N-1}$ different sequences of $N-1$ bits. So half of the original sequences cannot be represented with $N-1$ bits. Since we have to be able to represent any possible input, at least one of the $(N-1)$-bit sequences must be the prefix of longer encodings, and thus is not usable as a compressed code. So the number of compressed sequences must be less than half of the total number of possible inputs. And that's a compression system with miniscule compression.

An important aspect of the above is that bit sequences do not have an intrinsic length. If the sequence is variable-length, the length must somehow be encoded, adding to the length of the encoded sequence.

Or in a possibly more intuitive sense, you cannot encode a single number into a list of smaller numbers without also accounting for the commas (or whatever) which separate the numbers in the list. Without commas, you couldn't know whether 234 represented 23,4 or 2,3,4. So you can't say that the encoded list is just three digits long.
> 2 votes

---
Tags: discrete-mathematics, data-compression
---


title: Data compression with Turing Machine

text:
# Question
Title: Data compression with Turing Machine
For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best compression level? One can think about splitting data as small chunks and for each small chunk iterate all possible (de)compression codes to get best compression. Is there any research or existing algorithms, utilizing ideas like that?

# Answer
> 2 votes
Suppose the first byte of the compressed file indicates which decompression algorithm to use, and then you use that algorithm to decompress the rest. Sure, you could do that. Absolutely. Some compression formats already do exactly this.

That said, it's also possible to view this as a *single* decompression algorithm. The master algorithm looks at the first byte of the file and then branches to a subroutine that handles the rest of the file. That can be considered a single algorithm. So at a fundamental level there is no fundamental distinction that can be drawn.

# Answer
> 0 votes
DEFLATE the stock standard compression algorithm will do exactly that. There are 3 type of blocks differentiated by a 2 bit value at the start of each block:

1. the raw bytes for when the other two won't make it any smaller
2. compressed with a fixed huffman encoding when the custom tree would take too much space for what it would save
3. compressed with a supplied huffman encoding

The size of each block is free to choose the compressor as it sees fit.

# Answer
> 0 votes
It is possible to find a Turing machine program that generates a particular output and treat that as the compressed form of the output data given the description of the Turing machine.

This is a standard way to estimate the Kolmogorov Complexity using Levin's Coding Theorem Method (CTM). However, it is intractable for binary strings beyond a few bits (the ACSS package has a 13 bits database using a supercomputer).

As you mentioned, it is possible to break a long binary string down to blocks of e.g. 13 and then aggregate the program for each block that is a compressed representation of the data. This is called the Block Decomposition Method.

Check the resources on this site for more details: https://complexitycalculator.com/

---
Tags: turing-machines, data-compression
---


# Question
Title: Is a kind of reverse Kleene star of a context-free language context-free?
Recently I had a question on one of my assignments asking to prove or disprove the following:

Let $L$ be a language. If $L^\*$ is context-free then $L$ is context-free.

Now obviously this is false since we can take some non-context free language $L\_1$ and the alphabet $\Sigma$, then make $(L\_1 \cup \Sigma)^\* = \Sigma^\*$ is context-free and clearly $L\_1\cup \Sigma$ is not.

Now I was thinking about a similar problem but now with respect to the words in the language, and was wondering if it is true or not. If $C$ is a context-free language then $C'$ is a context-free language where $w\in C'$ if and only if $\\{w\\}^\*$ is contained in $C$.

My suspicion is that this is also false, but I can't come up with a counterexample. Somehow one needs to construct a CFL $C$ such that the subset of all the "periodic" words of $C$ together are not context-free.

# Answer
> 6 votes
Let me solve a simpler question first. Suppose we'd like to know

> If $C$ is context-free, must $F(C)=\\{w: ww \in C\\}$ be context-free?

The answer is no: $F(\\{a^i b^i c^j a^j b^k c^k\\})=\\{a^i b^i c^i\\}$.

---

As for the original problem, consider the context-free language that contains words of the form $\\{a^i b^i c^j d a^j b^k c^k d\\}$ or those which don't contain exactly two $d$'s.

Define $D=\\{w: w^\ast \subseteq C\\}$. Suppose $D$ is context-free. Then $E=D\cap a^\ast b^\ast c^\ast d$ is context-free.

I claim $E=\\{a^i b^i c^i d\\}$, which is not context-free. Suppose $w = a^i b^j c^k d$. We have $w \in E$ exactly if $w^n \in C$ for every $n$. This condition is clearly satisfied when $n \neq 2$, because $w^n$ will not have exactly two $d$'s. For $n=2$, $w w=a^i b^j c^k d a^i b^j c^k d\in C$ which is equivalent to $i=j=k$.

# Answer
> -1 votes
Take the language $L = \\{a^{n^2} \colon n \ge 1\\}$, it is easy to prove non-regular (and non-context-free). However, $L^\*$ is the language denoted by $a^\*$, which is regular (and thus context free).

---
Tags: context-free, kleene-star
---


# Question
Title: decidability about intersection of regular language and context free language
Is "Given a CFL L and a regular language R, is intersection of L and R an empty set?" decidable? What if we replace L with the complement of L? One of them is decidable and the other is not. For the one that is decidable, give an algorithm. For the other, give an undecidability proof.

For the first part "Given a CFL L and a regular language R, is intersection of L and R an empty set?", I have the following idea. I think it is decidable because an intersection of context-free language and regular language is context-free, and then we can build context-free grammar G from the langauge. For a given CFG G, checking whether the language(G) is empty or not is decidable.

But I have one thing that I'm not sure of. For given context-free language, how can a Turing machine build context-free grammar? As far as I know, there is no known procedure for doing this. If there is no general procedure for building context-free grammar, I think the above proof is invalid.

But I read a proof of theorem "Every context-free language is decidable" from Sipser textbook, and the proof says that for any arbitrary CFL A, we build a grammar G that recognizes A, and we have to include this description of G into our machine. I guess this could work because CFL is fixed, but the above machine needs to take any arbitrary CFL L and regular language R.

# Answer
> 1 votes
It is known that the intersection of a regular language and a context free one is context free. Besides, you can always take your regular language to be $\Sigma^\*$, so any context free language can be the result.

Then the question is if a given context free language is empty, which is easy to answer.

To ask if the complement of a context free language is empty is to ask if it is $\Sigma^\*$, which is undecidable.

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


# Question
Title: Regular expression for a binary string containing even number of 0's
To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it):

The regular expression for the above according to me should be $(1+01^\*0)^\*$ but elsewhere I have seen it can be $(1^\*01^\*01^\*)^\*$. Why is it different?

# Answer
There are (infinitely) many regular expressions for every regular language. Your approach gives you one (good job on a structured approach!), others give you others.

Consider, for instance, two distinct yet equivalent NFA translated using Thompson's construction.
> 1 votes

# Answer
(1∗01∗01∗)∗ is actually wrong because it doesn't handle a string consisting of all 1's
> 3 votes

# Answer
If you look at your DFA, you can repeat $1$ zero or more times ($1^\*$), then a $0$, then again $1$ zero or more times ($1^\*$), and a $0$ to finish at the final state, where again you can go $1$ zero or more times, in all $1^\* 0 1^\* 0 1^\*$; but the above game you can repeat at will, for $(1^\* 0 1^\* 0 1^\*)^\*$ in all.

"Hand translating" a DFA into a regular expression can be done in several ways, you could also take $(1^\* 0 1^\* 0)^\*$ to go to the final state, and only at the end handle possible final $1$s, for $(1^\* 0 1^\* 0)^\* 1^\*$
> 1 votes

# Answer
Both of the expression will give the same answer. (1+0)\* means any combination of 1 and 0 any number of times. So equivalently (1+01\*0)\* can be inferred. Which is the same as second expression.
> 0 votes

# Answer
This question was posted quite a long time ago. But I post the answer for any further help of desirous.

Both the answers are perhaps wrong. Your answer cannot generate $1010$ and the other cannot generate $1$. So what you may try is like this.

1. First construct regex for smallest even number of $0$'s which will be $R=00$. Now $1$ can be put anywhere any number of times in the $R$. So now $R$ will convert to $R=1^\*01^\*01^\*$. Now we construct regex for any even number of $0$. So we simply use the 'star' operator. and thus $R=(1^\*01^\*01^\*)^\*$. But notice that strings containing only $1$, i.e., no occurrence of $0$'s must be accepted by the automata because zero number of $0$'s is still acceptable since $0$ is also an even number but this regex is declining $1^\*$ to be accepted. So we just take union with $1$ and thus the final regex will be $R=(1+1^\*01^\*01^\*)^\*$.
2. Another answer could be $1^\*(01^\*01^\*)^\*$. I think in the second answer posted by the OP, there was a typo on behalf of the book writer by just misplacing $()$.
> 0 votes

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


# Question
Title: Prove that any algorithm that has sublinear time have a constant time complexity?
This exercise is taken from Goldreich's textbook of "Computational Complexity - A Conceptual Perspective", first ed., p.140.

> Exercise 4.3: Referring to any reasonable model of computation and assuming that the input length is not given explicitly, prove that any algorithm that has sub-linear time complexity actually has constant time complexity?

Here is the note given by Oded:

> Guideline: Consider the question of whether or not there exists an infinite set of strings S such that invoked on any input $x \in S$ the algorithm reads all of x. Note that if S is infinite then the algorithm cannot have sub-linear time complexity, and prove that if S is finite then the algorithm has constant time complexity.

For definition of sublinear time, see here.

This is how I show it: Since we strictly read less than the size of the input |x|, then it is necessarily that we read some of the input, let's say 1, 2, ..., k where k \< |x|. Since k is not part of the input, therefore time complexity of this algorithm is O(1). Is my conclusion right? If not, then why?

As you notice, I didn't use the hint since I didn't know how to show if S is finite, then the algorithm has a constant time.

# Answer
> 4 votes
I think to make this work we need to work in a model of computation where the input string is read sequentially. That is, in order to read the $i$'th character of the input string $S$, we first need to read characters number $1,2,\ldots,i-1$. In what follows I also assume that every substring of a valid input is a valid input (this in particular implies the fact that the length of the string cannot be explicitely encoded in, say, the first $O(\log n)$ bits of the input).

Let $S$ be the set of strings such that invoked on any input $x\in S$ the algorithm $A$ reads all of $x$. As the guideline suggests $S$ must be finite, as otherwise $A$ cannot be sublinear.

Now, let $k$ be the length of the longest string in $S$. I claim that $A$ never reads more than $k$ characters of its input. Indeed, suppose there is some input $x$ such that $A$ reads $k'\>k$ characters when invoked on $x$. Let $y$ be the string consisting of the first $k'$ characters in $x$ (this is where I use the assumption that every substring of a valid input is a valid input). Because $A$ reads only the first $k'$ characters when invoked on $x$ it cannot distinguish between $x$ and $y$. In particular, it also reads all $k'$ characters when invoked on $y$. Thus, $y\in S$ and $y$ is of size $k'\>k$, which contradicts the definition of $k$. We conclude that our assumption was wrong, and $A$ never reads more than $k$ characters of its input.

Because $A$ never reads more than $k$ characters of the input, it has a finite (constant) number of distinct possible executions. Thus, its worst-case time-complexity is also constant.

(I implicitly assumed a deterministic model of computation here, but it isn't hard to make the argument work under the presence of randomness, both for worst-case and expected time-complexity)

---
Tags: complexity-theory
---


# Question
Title: What is the strongest weaker version of the halts() function?
I was wondering about some questions related to the Halting problem. I might have not understood all the assumptions in it fully. Would you kindly help me, please?

I understand that the construction in the proof leads to a contradiction. My thoughts are:

* If one runs these theoretical programs in the real world, I would expect that the output of halts(f()) will oscillate between true and false with a frequency dependent on the processing speed. This all happens because the execution of f() is made dependent on the output of halts(f()). Self-referenced.
* Obviously there are programs which do not need to be run by a testing halts() function and they can be still decided if they halt or not. For example the following will obviously not halt and there are IDEs which already detect it:

while(true)

;
* Based on the previous 2 thoughts, can we state that there can be such halts() program that tells us if a program halts or not and oscillates between the two values only if the input program code takes the output of a halts(f()) function as an input in the inside?

Such halts() is still useful. Even if it cannot tells us a certain answer for a constructed, self-referenced pathological case.

Basically I am trying to figure out what is the strongest weaker version of the halts() function. What can we expect from it?

# Answer
> 1 votes
The gist of the argument is that the assumption that a one can write a function `halt(f)` that always halts and always answers correctly if `f` halts leads to a contradiction (by way of self-reference, applying it to a variant of itself), thus such function can't be written.

Sure, you can write functions that answer "Yes", "No", or "Don't know" (or even never stop) always correctly. Say we consider C programs only, it is (more of less) easy to check they are just a `main` function that doesn't include any loops, and so answer "Yes" for them, and "Don't know" for anything else. You can certainly refine the above a lot, and each refinement can in itself be further refined (if a program could identify the cases where all have to answer "Don't know", it'd know that for them the answer is "No" --just running the program would tell eventually if the answer is "Yes"). The point is there can't be a way to answer *all* cases correctly.

---
Tags: halting-problem
---


title: Greedy Algorithm: Optimal Substructure

text:
# Question
Title: Greedy Algorithm: Optimal Substructure
I don't have a CS degree but I have recently taken up studying algorithms very seriously.

I have been studying greedy and dynamic programming for days and I come across the below definition a lot, seems they all come from the same source, but I do not understand what it means, it is one of the vaguest definitions I have ever come across. I wonder if someone can please help me explain this.

e.g. I don't understand what they mean by `optimal solution`, what constitutes an optimal solution, how can I define it?

> In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem

# Answer
> 2 votes
Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.

To answer your question, let's look at a simple example, change-making problem:

> Given a set of integer values of coins $C = \\{c\_1, …, c\_n\\}$ and an amount $W$, what is the minimum number of coins to add-up to the amount $W$?

The classical greedy approach is the following:

```
While W > 0
   pick the largest coin c that is <= W
   W <- W - c

```

For example, with $C = \\{1, 2, 5\\}$ and $W = 13$, you will pick $5$, $5$, $2$ and $1$, and you can show that the minimum number of coins required is indeed $4$.

However, this algorithm does not always provide an **optimal solution**. For example, if $C = \\{1, 4, 5\\}$ and $W = 8$, the greedy algorithm will choose coins $5, 1, 1, 1$ when there is a solution $4, 4$ using less coins.

Back to the topic of your question, the change-making problem does not have an optimal substructure, unless you add some hypotheses on $C$

# Answer
> 1 votes
Usually, in the context of dynamic programming and optimization methods, we are interested in problems where we have to "find" some value which maximizes \ minimizes a certain function.

For example, take the following problem: You are a cashier in a shop, and a customer gave you an $n$-dollar bill (your country has bills of all kinds! very intriguing), for an item that costs only $k\<n$ dollars, and you want to give the customer correct change. However, your cashing station has only limited amount of bills of each type, and this information is given to you in a list with tuples of the form `(dollar value, number of dollars in cashing station)`. But, you also want to keep the number of bills in your station as large as possible, so you could give change to other customers as well.

In this problem, a "solution" would be a way to give change to the customer, and an "optimal solution" is a solution that also keeps as many bills as possible in the station

# Answer
> 1 votes
Check e.g. Jeff Erickson's Algorithms (warning, somewhat though going), it has a thorough chapter on greedy algorithms. He also warns that greedy algorithms very rarely give optimal results (The underlying problem has to have a *very* particular structure for them to work in all cases, see e.g. Jeremy Kun's "When Greedy Algorithms are Perfect". Sure, several very important algorithms are greedy algorithms.).

Greedy algorithms are attractive as a way to get approximate solutions, as they are usually simple to code and very fast, and they sometimes get good solutions (can be proved are within some reasonable factor of the optimal solution).

---
Tags: dynamic-programming, greedy-algorithms
---


# Question
Title: How to transform an Abstract Syntax Tree (AST) to an Abstract Binding Tree (ABT)? (for machine learning fo theorem proving)
I was reading the HOList paper that applies Graph Neural Networks (GNNs) to the HOL Light (HOList) data set and benchmark for ML for theorem proving. They describe their results etc but there is no code I can find or even pseudocde (algorithmic description) of how to transform an AST -\> ABT. How does one do this?

This seemed like a solved problem obviously so I wanted to avoid re-inventing the wheel - especially if something already existed that is probably optimized or takes care of nuanced of the process.

---

References:

# Answer
> 1 votes
Your referenced paper doesn't define the term "abstract binding trees"; where did you get that phrase? (I did not look at your other references; this paper was interesting enough by itself).

The paper does define a variety of transformations on ASTs by examples, but IMHO those examples are sufficient to define or least lookup the necessary algorithms.

What I interpret the paper as saying is, "(for our GNN-based theorem prover), you can use pure ASTs, or you can use a variety of variants which perform better because they take context into account".

If you work on compiling code, you already know the value of (semantic) context over a pure context-free parsing in validating program source text (and logical formulas are just a kind of programming text). I make this point brutally obvious here: Life After Parsing

They seem to define context in three different ways:

* bidirectional links between parent and child nodes. Having links going both directions allows context to be computed bottom up, and to have context flow from some children of a node, to be passed as context to other children. This sounds like the value one obtains by having an attribute grammar, which has synthesized properties and inherited properties. I didn't read the paper carefully enough to understand what information was being propagated up, or what was being propagated down, or even how their GNN accomplished this effect. Implementing this is rather trivial: one needs child links and parent links in the nodes.
* joining nodes in the AST that represent the same variable. What this is doing is taking into account scoping rules in the language, and amounts to replacing variable names by symbol table references. They argue that the type information associated with the symbols should be included, which you get for "free" if your symbol table includes type information, which any serious symbol table does. Implementing this requires that your AST processing machinery be augmented with symbol tables, and that the AST is processed to replace identifier nodes with symbol table entries (well, with the content of the appropriate symbol table entry). This is hard to do if your langauge is complex (e.g, symbol tables for C++ will make your head explode) you need an extremely organized attack to build/use these; this is part of the reason that building compiler front ends is hard. But for the HOL representations being used by the authors, the "symbol" tables are pretty simple and you can probably do this in an ad hoc way with a tree-scanning procedure.
* Merging common subtrees honoring variable type information into single trees. This is classically what common sub-expression elimination does. Its apparent value in this paper is that it can dramatically shrink the size of the tree and therefore the implied amount of work it takes to process the tree. (You can get an overly compressed tree for free if you use a GLR parser which produces maximally shared subforests which happen to also include expression trees, but you have to split out shared subtrees based on type information after the fact). I note this looks to me not so much as context usage but "merely" size reduction.

TLDR: The authors appear to implementing classic compiler front end building techniques and algorithms to convert ASTs into what amounts to Directed Acyclic Graphs that encode type information for different variables.

\[FWIW, a generalized AST-processing engine I build called DMS has: a) bidirectional links between parent and child nodes, b) shared subtrees via GLR parsing c) symbol table definition methods, d) attribute-grammar definition/execution which is easily used to scan ASTs to link leaves to symbol table entries. AFAICT, DMS sort of does everything this paper suggests doing. This is because you pretty much always need at least the results of all this to process any kind of AST in a semantically sensible way\].

HTH.

---
Tags: machine-learning, artificial-intelligence, neural-networks, automated-theorem-proving
---


# Question
Title: For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?
I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of `[nodex, nodey]`, `nodex<=nodey`. And also given that the range has exactly **k** nodes, **k** can be at most **n** ie. total number of nodes. The question asks what is the worst case time complexity of accessing all the **k** nodes in given range. According to my knowledge of Time-Complexiy analysis It must be `O(k*log(n))` since there are **k** elements and each element takes `O(log(n))` time in worst case ( since the tree is balanced ) this seems very plausible, However the answer seems to be `O(k + log(n))`, what am I doing wrong?

# Answer
One way to do it is to construct the tree containing those values:

1. Explore the BST until you find the root of a subtree that is between the bounds;
2. Explore the left part of the subtree, and trim branches on the left that have a root $\leqslant node\_x$;
3. Do the same thing on the right for roots $\geqslant node\_y$

Each of those steps are done in $O(\log n)$ since the BST is balanced. Once you have constructed the tree, just do a tree traversal (in-order for example) of it. This last step is indeed done in $O(k)$.
> 2 votes

---
Tags: time-complexity, big-o-notation, balanced-search-trees, binary-search-trees
---


# Question
Title: What benefits are obtained by allowing the occurrence of free variables and open terms in lambda calculus?
Because of the existence of free variables in lambda calculus, the evaluation of open terms (at least as outlined here) is more complicated relative to the evaluation of closed terms since the evaluator must ensure that the beta-reduction step uses capture-avoiding substitution, i.e., that the variables it substitutes into a term are not free variables of that term.

Combinatory logic can be seen as a subset of lambda calculus that only allows closed terms. Despite this, it is still Turing-complete, and can thus be used to compute everything that lambda calculus can. As such, what are the benefits of allowing free variables and open terms, and the disadvantages of disallowing them? On a related note, why does lambda calculus seem to be a more popular topic of study than combinatory logic despite the apparent shortcoming mentioned? Is the former somehow more relevant and useful to a larger variety of topics than the latter?

# Answer
A subterm of a closed term is not necessarily a closed term. A calculus of closed terms would have to model open terms as well anyway. Pretty much any definition on terms relies on induction over the structure of the terms, and to define something for closed terms of the form $\lambda x. M$, you need to define that thing for the open term $M$.

There are plenty of models of computation. What's the benefit of using combinator calculus when you can use Turing machines or Conway's game of life? Combinator calculus is a natural model of function application, but doesn't capture function definition. The lambda calculus, with variable names, models function definitions with variable names, which a core concept of most programming languages. For this reason, it's a more useful model of programming languages than combinator calculus.

The point of a theory is not just to be internally simple, it's also to be useful for reasoning.
> 8 votes

---
Tags: lambda-calculus, combinatory-logic, variable-binding
---


# Question
Title: How does the union of two machines which accept language of form $0^{mx+b}$ look like
I am doing Shai Simonson's course on Theory of computation. I am not able to understand part b of one of its problem sets.

> a. Prove that languages of form $0^{mx+b}$, where m and b are positive integer constants and x ranges from 0 to infinite, is regular.

> b. Give an example of a regular set over the alphabet {0} which is not of form $0^{mx+b}$.

In the solution set, for part b, it is given that union of machines which accept language of form $0^{mx+b}$ describes a regular set, but is not of form $0^{mx+b}$.

Q1. I want to understand of what form the union is?

Q2.And also, we are talking about union of finite number of machines, right? Because the union of all such machines(which is infinite) will not be regular. Am I correct?

Q3. I would also like to know is there any other example of a regular language which is not of the given form but is regular.

Q4. I also want to clarify what does set of the union of two such machines will look like. Will it be {$0^{2x\_1+3}$ $\bigcup$ $0^{7x\_2+4}$} or {$0^{2x+3}$ $\bigcup$ $0^{7x+4}$} i.e. will the $x's$ be different or same in both the machines. I think the two sets are independent so they should be different but still want to confirm.

# Answer
> 3 votes
1. It is written union of machines (I suppose here machine means finite automaton), but it is only an union of languages, i.e. the union of the languages accepted by said automata.
2. Indeed it should be finite otherwise it could be not regular. To prove this fact, for $k\in \mathbb{N}$, consider $L\_k = \\{0^{n(2k+3)},n\in\mathbb{N}\\}$, and $L = \bigcup\limits\_{k\in\mathbb{N}}L\_k$. Then $L$ is the set of words over the alphabet $\\{0\\}$ that have a length which is the multiple of an odd number greater than $2$. That means that the complement of $L$ is $\overline{L} = \\{0^{2^n}, n\in\mathbb{N}\\}$. Since $\overline{L}$ is not even context-free, then $L$ cannot be regular.
3. $L = \\{0^{2n}, n\in \mathbb{N}\\}\cup \\{0^{3n}, n\in\mathbb{N}\\}$ satisfy the condition. To prove it, suppose $L = \\{0^{an+b}, n\in\mathbb{N}\\}$. Since $\varepsilon \in L$, then it means that $b = 0$. Since $0^2\in L$, it means that $a\mid 2$. Since $0^3\in L$, it means that $a\mid 3$. We conclude that $a\mid\text{gcd}(2, 3) = 1$, so that $a = 1$. Since it is clear that $L \neq \\{0^n, n\in\mathbb{N}\\}$ (because $0^5\notin L$ for example), $L$ is regular and not of the said form.
4. There seems to be a bit of misunderstanding about the variable $x$ here… And to be precise and avoid any mistake, you should write $\\{0^{2x+3}, x\in\mathbb{N}\\}$ instead of just $0^{2x+3}$. That way you will understand that $x$ is just a free variable and it does not matter how you write it.

---
Tags: regular-languages
---


title: Is the following problem NP-Complete?

text:
# Question
Title: Is the following problem NP-Complete?
3SAT with the additional condition that exactly 1 or 3 literals must evaluate to 1.

# Answer
No. This problem is equivalent to XOR-3SAT, in which we interpret each clause as $x \oplus y \oplus z$, where $\oplus$ is the XOR operator, and ask whether it's possible to find values for all variables so that each clause is true. XOR-SAT can be solved in polynomial time using Gaussian elimination, with all arithmetic done modulo 2 (i.e., in the finite field $GF(2)$).
> 4 votes

# Answer
By Schafer's Dichotomy Theorem, if a clause is expressible as a system of linear equations over Zmod2, it is in P. Thus it would not be NP-Complete.
> 2 votes

---
Tags: satisfiability, 3-sat, constraint-satisfaction
---


# Question
Title: Is there computer for specify purpose that perform database task?
Is database server really really exist? i mean the server wasn't made by general purpose computer but that database device have their own hardware and architecture.

We know that good database server means good in shorting data.

So the database server i mean have hardware that only found inside it which general purpose computer doesn't have it.

So maybe the part hardware theres shorter directly with using logic gates and binary.

I feel every electricity through passing a logic gates have propagation delay. So thats mean less logic gates more faster.

So im not talking about software but a hardware architecture, yes it still need software and probably special OS too for it. It database only perform retrieve and saving data. If data found after shorting process, then it transfer data to general purpose computer.

# Answer
Tandem's NonStop system used custom hardware to ensure reliability, and was used for transaction processing, i.e., for highly reliable databases.
> 1 votes

---
Tags: databases
---


# Question
Title: Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?
Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.

In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells. (i.e., $|x| = O(n^2)$ or $|x| = O(m \log n)$).

Now I want to study the lower bound and the upper bound on the time/space complexity with respect to the number of vertices $n$. Suppose we have found the upper bound is $O(f(|x|))$ and lower bound $\Omega(g(|x|))$. Since $m = O(n^2)$ and $m = \Omega(n)$, we can only conclude that $$O(f(|x|)) = O(\max\\{f(n^2), f(m\log n) \\}) = O(f(n^2\log n))$$ and $$\Omega(g(|x|)) = \Omega(\min \\{g(n^2), g(m\log n)\\}) = \Omega(g(n\log n))$$ The gap become larger. It is not tight even $f = g$.

Is there way to solve my confusion?

Now I define the graph problem as a pair $(L', O)$ where for every instance $x'$ of $L'$, it is only encoded by the number of vertices, $O$ is an oracle whose valid input is a pair of vertices $(u,v)$, it returns 1 if $uv$ is an edge in the graph and it returns 0 otherwise. Can I solve my confusion by using this model? (However it seems that $|x'| = O(\log n)$ which is very small.)

# Answer
> 2 votes
I will try to lift some of the confusion you have.

Let $G$ be some graph, with $n$ vertices and $m$ edges. Then what is $|G|$? Lets say we encoded it as adjacency matrix, so it takes up $n^2$ space. Therefore, $f(|G|)=f(n^2)$ and $g(|G|)=g(n^2)$. There won't be a "gap" here.

What about if we encode it with $m\log(n)$ space? then we would have $|G|=m\log(n)$ and thus $f(|G|)=f(m\log(n))$ and $g(|G|)=g(m\log(n))$.

So what went wrong with your calculations? The difference here is that you used `max` once and `min` once to represent the same quantity. You probably did this to "give a bound" only, but notice the following interesting thing: why would we want `max`? we can always encode the graph in the smallest way possible, so essentially $|G|=\min \\{n^2,m\log(n)\\}$. Substitute this and get $g(|G|)=g(\min \\{n^2,m\log(n)\\})$. In the same way, $f(|G|)=f(\min \\{n^2,m\log(n)\\})$.

Notice I didn't give the bounds in terms of $\Omega$ and $O$, but we could. In any case, the transition $g(\min \\{n^2,m\log(n)\\})=\Omega(g(n\log(n)))$ is not strict, since there are many times that $\min \\{n^2,m\log(n)\\}\> n\log(n)$. The same goes with the transition $f(\min \\{n^2,m\log(n)\\})=O(f(n^2)))$ (making this a `min` automatically made the bound better).

I hope this helped you understand a bit more how the bounds behave with respect to the size of the graph and its different encodings.

---
Tags: complexity-theory, graphs, time-complexity, space-complexity
---


# Question
Title: Find palindrome in directed Graph where edges are either blue or red
This is the given task: Suppose you are given an arbitrary directed graph G in which each edge is colored either red or blue, along with two special vertices s and t.

Describe an algorithm that either computes a walk from s to t such that the pattern of red and blue edges along the walk is a palindrome, or correctly reports that no such walk exists.

I already know the solution involves DFS in some way but I don't know how to check if a palindromic path doesn't exist. Since it's not necessarily an acyclic graph there are infinitely many paths that can potentially form a palindrome. So how do I go about this problem?

# Answer
Here's a possible algorithm.

Construct a graph $G'$ with $|V|^2$ vertices where each vertex is labeled with the pair $(a, b)$ with $a, b$ being vertices in $G$. Then, construct all possible edges $(a, b) \to (c, d)$ in $G'$ where two edges $c \to a$ (note the order) and $b \to d$ exist in $G$ with the same color.

Then to find an odd-length palindrome you simply check if $(s, t)$ is reachable from any $(x, x)$ in $G'$. To find an even-length palindrome check if $(s, t)$ is reachable from any $(a, b)$ in $G'$ under the condition that $a \to b$ exists (regardless of color) in $G$.

---

The idea is to extend the palindrome from the middle out. The vertices $(l, r)$ in $G'$ represent the leftmost and rightmost symbol in our palindrome, and the way we constructed the edges in $G'$ corresponds to all valid ways to extend the palindrome.
> 2 votes

---
Tags: depth-first-search, directed-graphs
---


title: Count Sketch probability bound

text:
# Question
Title: Count Sketch probability bound
I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I tried to solve some of the exercises. However, exercise 5-3 is causing me some problems.

If we let $\hat{f}\_a$ denote the estimated frequency associated with a key $a$ and $f\_a$ be actual frequency associated with key $a$, then it can be show that $E\[\hat{f}\_a\]=f\_a$. Furthermore, for $j\in\[n\]$, we let $\mathbf{f}\_{-j}$ be the $(n-1)$ dimensional vector obtained by dropping the $i$th entry of frequency vector $\mathbf{f}.$ It can then be shown that $$ \text{Var}\[\hat{f}\_a\]=\frac{||\mathbf{f}\_{-a}||\_2^2}{k} $$ when we use the hash function $h : \[n\] \rightarrow \[k\]$. Thus, using Chebyshev's inequality, it can be shown that $$ \text{Pr}\[|\hat{f}\_a - f\_a| \geq \epsilon ||\mathbf{f}\_{-a}||\_2\] \leq \frac{1}{3} $$ for $k=\frac{3}{\epsilon^2}$.

In exercise 5-3, $\textbf{f}\_{-a}^{\text{res}(\ell)}$ denotes the $(n-1)$-dimensional vector obtained by setting the $\ell$ largest (by absolute value) entries to zero in $\mathbf{f}\_{-a}$. The exercise then essentially asks the reader to show that $$ \text{Pr}\[|\hat{f}\_a - f\_a| \geq \epsilon ||\mathbf{f}\_{-a}^{\text{res}(\ell)}||\_2\] \leq \frac{1}{3} $$ where $k=\frac{6}{\epsilon^2}$ and $\ell=1/\epsilon^2$. However, I don't know how to show that the inequality above holds. I have tried using Chebyshev's inequality, but I still can't seem to make it work. Any help would be appreciated.

# Answer
> 3 votes
$\newcommand{\norm}\[1\]{\left\lVert#1\right\rVert}$

Denote the support of $f$ by $f\_1\le f\_2\le...\le f\_s$. Given a frequency sequence $f$, denote by $E\_{f,a}$ the random variable $\hat{f}\_a$ where the stream frequencies are given by $f$ (the evaluation depends on the inner randomness of the sketch and the input stream).

The probability that the hash of one of the top $\ell=1/\epsilon^2$ elements collides with the hash of some given element $a$ is bounded by $\frac{\ell}{k}$ (union bound). Conditioning on the event that such a collision did not occur, the evaluation $\hat{f}\_a$ does not depend on the top $\ell$ entries, as they do not affect the hash entry of $a$. More formally, conditioned on the event $C=\bigcap\limits\_{i=0}^{\ell-1}\mathbb{1}\_{h\left(f\_{s-i}\right)\neq h(a)}$, $E\_{f,a}$ and $E\_{f^{res(\ell)},a}$ are equally distributed. This yields:

$$\Pr\left\[\left|\hat{f}\_a-f\_a\right|\ge \epsilon\norm{f\_{-a}^{res(\ell)}}\right\]= \Pr\[C\]\cdot \Pr\left\[\left|\hat{f}\_a-f\_a\right|\ge \epsilon\norm{f\_{-a}^{res(\ell)}}\big| C\right\]+\\ \left(1-\Pr\[C\]\right)\Pr\left\[\left|\hat{f}\_a-f\_a\right|\ge \epsilon\norm{f\_{-a}^{res(\ell)}} \big|\overline{C}\right\]\le\\ \Pr\left\[\left|\hat{f}\_a-f\_a\right|\ge \epsilon\norm{f\_{-a}^{res(\ell)}}\big| C\right\]+\frac{1}{6}$$

Since $E\_{f,a}, E\_{f^{res(\ell)},a}$ are equally distributed (conditioned on $C$), the left hand term equals $\Pr\left\[\left|\hat{f}\_a-f\_a\right|\ge \epsilon\norm{f\_{-a}}\right\]$, which you can bound by $1/6$ with your original result.

---
Tags: algorithms, algorithm-analysis, probability-theory, randomized-algorithms, hash
---


# Question
Title: How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem
**Task:**
A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, the 1/2 hamiltion path problem (1/2-HPP) asks for a path that visits exactly half of the nodes.
Show that: $HPP \le\_{P} 1/2-HPP$
**Question:** Can anyone give me a hint on how to prove $HPP \le\_{P} 1/2-HPP$

# Answer
> 0 votes
Double the graph size: make two clones of the input $G\_1,G\_2$ and now create the (not connected) graph $\hat G$ that will consist of the two clones $G\_1,G\_2$. Now a half-hamiltonian path in $\hat G$ is either going through all $G\_1$ or all $G\_2$ (but not both, since they are not connected) and thus would be a hamiltonian path in $G$.

# Answer
> 1 votes
You just need to add $n$ (where $n$ is the order of the graph) vertices with no additional edges.

---
Tags: complexity-theory, np, hamiltonian-path, polynomial-time-reductions
---


title: Describe regular expression

text:
# Question
Title: Describe regular expression
I am learning about regular expression, and trying to describe a regular expression for the language L

> $\qquad L = \\{a^i b^j c^k \mid i+j = k\\}$

What is the right approach and how to describe a regular expression like this?

# Answer
> 2 votes
It seems I didn't understand the question.

There is no regular expression for this language because it is not regular. You can prove it using the pumping lemma.

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


# Question
Title: Can preorder and postorder traversals be used on any type of trees?
I could not find an answer to the question directly by google.

I think this question is rather simple but I am not really sure about it.

Any advice is welcomed.

Thanks

# Answer
Well, yea. But you need to define formally what a "type of tree" could be. General trees, are described by the mathematical notion of a tree graph. Given some ordering on the nodes of the tree, and some definition of which node is the root of the tree, you can perform the "pre-order" and "post-order" traversals.

The algorithms that computes them are also very similar to the ones you are probably familiar with, with the small change that you need to iterate all children instead of just traversing on the two children (since the number of children isn't restricted here).

However, the in-order is not defined properly for trees without also defining a notion of what children are "to the left" of the root and what children are "to the right" of the root. When you give a formal definition to this idea as well, you can perform the in-order traversal as well.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Average time complexity of linear search
It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear). I have read several proofs, usually assuming either:

* that $i$ and the elements of $L$ take values in an infinite domain, in which case the probability of $i$ being is $L$ tends towards 0 and the algorithm will iterate over all elements.
* that $i$ is present exactly once in $L$, in which case the expectancy on the number of iterations is $(1 + 2 + … + n)/n \in O(n)$.

However, I would like to introduce the case where $i$ and the elements of $L$ take values in a finite domain of size $d$. Is this case studied somewhere? I have failed to find proof online, but I have found one that finds that the complexity is $O(d)$, and would like to know whether it is correct. I assume that each element of $L$ is a random value from $\[1..d\]$. I want the expectancy $E$ on the number of iterations of the linear search algorithm. I also assume that $L$ has infinite size, without loss of generality, I do not want to question the fact that linear search is $O(n)$ on average, it clearly is. My point is that linear search is both $O(n)$ AND $O(d)$. I have interest in the case where $d \ll n$.

At the first iteration, there is a $1/d$ probability that the sought element is found and the algorithm stops. In other cases, i.e. with a probability of $(d-1)/d$, the algorithm iterates. Recursively, I have $E = 1 + E\cdot(d-1)/d$, which boils down to $E=d$.

Also, this seems related to the fact that $\sum\_{n=0}^{\infty} \frac{n}{e^n} \in O(1)$, if the recursion is unrolled. My proof, however, seems almost too easy. Is there a fail somewhere?

# Answer
The right way to prove this is to use the notion of expected value.

Given an array $\[x\_1, …, x\_n\]$, an index $1\leqslant k \leqslant n$ and a value searched $1\leqslant i \leqslant d$, the probability that $x\_k = i$ is $\frac{1}{d}$.

Now what we want to calculate is the expected value of the first index $k$ such that $x\_k = i$. For that, we need to know the probability, for each index $k$, that $x\_k$ is the first value equal to $i$. This probability is $p\_k = \frac{1}{d}\left(1-\frac{1}{d}\right)^{k-1}$ (meaning that we did not encounter $i$ within indices $1…k-1$ but in index $k$).

The expected value is then $\sum\limits\_{k=1}^{n}kp\_k = \frac{1}{d}\sum\limits\_{k=1}^nk\left(\frac{d-1}{d}\right)^{k-1}\leq \frac{1}{d}\sum\limits\_{k=1}^{\infty}k\left(\frac{d-1}{d}\right)^{k-1}$.

We can show that this last quantity is equal to $\frac{1}{d}\frac{1}{\left(\frac{1}{d}\right)^2} = d$.

This indeed means that the average time complexity is $O(d)$.
> 1 votes

---
Tags: time-complexity, search-algorithms, check-my-answer, average-case
---


# Question
Title: Grammar for $L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}|i,j>0\}$
I'm supposed to write grammar for this language: $$L=\\{a^{i+1}b^{i}c^{2j}d^je^{2j}\mid i,j\>0\\}$$

This is what I have so far:

$$\begin{align} S &\to aXbY \\; \\ X &\to aXb \\;|\\; a \\ Y &\to ccYdE \\;|\\; ccdE \\ Ed &\to dE \\; \\ dE &\to dee \\; \\ eE &\to eee \\; \\ \end{align}$$

*Edit:*

Thank you for answers, I looked at the https://en.wikipedia.org/wiki/Noncontracting\_grammar#Example and edited my grammar:

Is this correct? Is it necessary to do $$\begin{align} Ed &\to dE \\; \\ dE &\to dee \\; \\ eE &\to eee \\; \\ \end{align}$$ or can I just do $$\begin{align} Ed &\to dee \\; \\ E &\to ee \\; \\ \end{align}$$

# Answer
Your answer is correct.

The alternative with $E\to ee$ is incorrect, as it might generate 'ee' in between 'd's. You must first shift all the E's to the end and only then make them into $ee$.

I would generate $cc$ and $ee$ together, and play with the $D$'s, i.e., $Y\to cc YD ee$, etc. This will be slightly more simple, though equivalent.
> 0 votes

---
Tags: formal-grammars
---


# Question
Title: Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $
I have to show that this language is not context free $\mathcal{L} = \\{ \omega \omega^R a^{|\omega|} : \omega \in \\{a,b\\}^\* \\} $, where the $R$ corresponds to the reverse. For this I will use the pumping motto for free context languages. I know how it works, but I have problems choosing the correct $ \sigma $, because when looking at the alternatives for $ vwx $, knowing that $ uv^kwx^kz$ has to be met, I can't get to something concrete, the $a^{| \omega |}$ makes me sick. Is there any other way to show that it is not context free? or that $ \sigma $ could occupy.

# Answer
The problem is not very hard if you break the proof of the pumped string not being in the language into cases. So let's work this out. $$L = \\{\omega \omega^Ra^{|\omega|}\\;| \\; \omega\in \\{a,b\\}^\*\\}$$

For every $n$, let us consider the string $\omega = a^nb^nb^na^na^{2n}$. You can check that this does belong to the language.

We are supposed to show that for any partition $\omega=uvwxy$, such that $$|vwx|\leq n \\;\mbox{and} \\; |vx|\geq 1$$ there exists $k$ such that $uv^kwx^ky \notin L$.

**Case1:** $v,x$ lie inside the first $a^n$. Since, $|vx|\geq 1$, we can see that for $k=0$, the resulting string will not be in $L$.

**Case2:** $v,x$ lie in the starting $a^nb^n$. You should notice that if you again pump the substrings with $k=0$, then the substring cannot be broken into $\omega\omega^R a^{|\omega|}$, because the count of $a$'s at the end remains the same, and we cannot have an $\omega$ of length $2n$ in the resultant string for it to happen.

**Case3:** $v,x$ lie inside the first $b^n$. Here, again, you can see how $k=0$ will pump the string outside the language.

The further cases are similar to what described above. Work it out for better understanding. Please let me know if you aren't comfortable with any part of this solution.

PS: The $a^{|\omega|}$ which makes you sick was the sole reason this language is not a CFL, XD.
> 1 votes

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


# Question
Title: How does asynchronous operations save time in I/O
I'm reading a book CLR via C# which says how Windows does asynchronous I/O:

> To read data from the file, ReadAsync internally allocates a Task object to represent the pending completion of the read operation. Then, ReadAsync calls Win32's ReadFile function (#1). ReadFile allocates its IRP (I/O Request Packet) and then passes it down to the Windows kernel (#3). Windows adds the IRP to the hard disk drive’s IRP queue (#4), but now, instead of blocking your thread, your thread is allowed to return to your code; your thread immediately returns from its call to ReadAsync (#5, #6, and #7). Now, of course, the IRP has not necessarily been processed yet, so you cannot have code after ReadAsync that attempts to access the bytes in the passed-in Byte\[\]. Using the task object, you can call ContinueWith to register a callback method that should execute when the task completes and then process the data in this callback method. Or, alternatively, you can use C#'s asynchronous function feature to simplify your code by allowing you to write it sequentially.

The author also describes a scenario of how asynchronous operations save time in I/O:

> let's say that your application wants to download 10 images from various websites and that it takes 5 seconds to download each image. If you perform this work synchronously (downloading one image after another), then it takes you 50 seconds to get the 10 images. However, if you use just one thread to initiate 10 asynchronous download operations, then all 10 are being performed concurrently and all 10 images will come back in just 5 seconds! That is, when performing multiple synchronous I/O operations, the time it takes to get all the results is the sum of the times required for each individual result. However, when performing multiple asynchronous I/O operations, the time it takes to get all the results is the time required to get the single worst-performing operation.

I don't understand how async operations can reduce the time from 50 seconds to 5 seconds. Let's change the NTFS Disk Driever to network adapter driver and change the read file async code to download file async code.

My understanding is, it is true that asynchronous operations allow fewer worker threads to handle incoming client's I/O requests, contrasted by synchronous operations, every I/O request need a worker thread to handle, and when the synchronous operation takes time to complete, the worker thread gets blocked too and therefore it cannot return to the thread pool to serve other requests. But for the network adapter driver, can still only complete one I/O operation one at a time.

For example, let's say the network adapter driver is handling the first I/O request (represented as an IRP queue) to download the first picture. Even though you use asynchronous operations, the worker thread that serves the first I/O request did return to the thread pool to serve the second I/O request, but the network adapter driver is still processing the first I/O request to download the first picture, so the second I/O request as an IRP is still queuing in the network adapter driver. The network adapter driver only handles the second IRP after the first one is completed, so the network adapter driver still serves the second I/O request after 5 seconds, and so on, so it still needs 50 seconds to download 10 pages. In other words, it is not worker threads blocking, it is the network adapter driver that's blocking.

so how can how async operations can reduce the time from 50 seconds to 5 seconds? Unless the network adapter driver itself is a small powerful computer that has multiple CPUs that can serve requests concurrently, but this is obviously not true, drivers like network adapter drivers are cheap devices, it can't be having expensive components like CPUs?

# Answer
Issuing the ten requests in parallel is unlikely to give you a tenfold speedup, but will usually give you some speedup. It depends on where the bottleneck is. If the images are 5 MB each and your Ethernet/WiFi connection can only transfer data at 1 MB/s, then your network card will essentially be tied up for 5 seconds per image, and issuing the requests in parallel probably won't help. If the images are 5 kB each and you have a gigabit fiber Internet connection, and the 5-second delay is due to the servers being very slow to respond, then your network card will be idle almost all of the time, and you may actually get all of the images back in 5 seconds total if you issue the requests in parallel.

The network card only sends and receives small isolated data packets, typically of about 1500 bytes. It doesn't understand the concept of a TCP or HTTP connection. When it's not sending or receiving packets related to one connection, it can send or receive packets related to another, even if the first connection is still open.

The book is wrong to assume that the 10 requests are perfectly parallelizable; usually that isn't the case. Also, the parallelism it's talking about has nothing to do with asynchronous I/O as such. You'd get the same speedup by starting 10 threads and issuing a blocking I/O call in each one. That might be a bit slower because of thread-creation overhead, but might also be faster because it uses more CPU cores if you have them. For the highest performance you have to create one thread per CPU core and use asynchronous I/O in all of them. NT has built-in support for that model through I/O completion ports.
> 3 votes

---
Tags: programming-languages, computer-networks
---


# Question
Title: Is quadratic nonresiduosity in $\textbf{NP}$?
The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an interactive proof system.

> Example 1: Let $Z\_m^\*$ denote the set of integers between $1$ and $m$ that are relatively prime with $m$. An element $a \in Z\_m^\*$ is a quadratic residue mod $n$ \[sic\] if $ a = x^2 \mod{m}$ for some $x \in Z\_m^\*$, else it is a quadratic nonresidue. Now let $L = \\{(m, x) | x \in \mathbb{Z}\_m^\* \text{is a quadratic nonresidue\\}}$. Notice that $L \in \textbf{NP}$: a prover needs only to compute the factorization of $m$ and send it to the verifier without any further interaction.

Given that $n$ is not defined in the context of the example, I assume this to be a typo and that the authors meant $m$. My question is about the last sentence. The authors provide no further detail afterwards about what the verifier would do with this factorization to verify quadratic nonresiduosity. In pursuit of more details, I cracked open Arora-Barak where the following treatment of the above is given in section 8.1 example 8.9.

> Here is another example for an interactive proof for a language not known to be in $\textbf{NP}$. We say that a number $a$ is a quadratic residue mod $p$ if there is another number $b$ such that $a \cong b^2 \mod{p}$. Such a $b$ is called the square root of $a \mod{p}$. ... the language QNR of pairs $(a, p)$ such that $p$ is a prime and $a$ is not a quadratic residue modulo $p$ has no natural short membership proof and is not known to be in $\textbf{NP}$. But it does have a simple interactive proof if the verifier is probabilistic.

Now if the language QNR described in Arora-Barak is not in $\textbf{NP}$, how could its "superset" the language $L$ described in the paper be in $\textbf{NP}$? If the paper is correct then we could easily construct a verifier which would prove that QNR is in $\textbf{NP}$: for any $(a, p)$ the certificate would consist of the certificate of the membership of $(p, a)$ in $L$ in addition to a certificate for the primality of $p$.

# Answer
> 4 votes
When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$.

When the modulus is a prime power $p^\alpha$, then you can do the same: I believe $x$ is a quadratic residue mod $p^\alpha$ iff $(x|p)=1$ or $0$. I believe this can be proven using Hensel lifting.

When the modulus is a number $n$ with known prime factorization $n=p\_1^{\alpha\_1} \cdots p\_k^{\alpha\_k}$, you can use the Chinese remainder theorem: $x$ is a quadratic residue mod $n$ iff it is a quadratic residue mod $p\_i$ for all prime factors $p\_i$ of $n$.

This means that quadratic nonresiduosity mod $n$ can be computed in polynomial time when the factorization of $n$ is known or given. This also means that, as far as I can see, the language QNR should be in NP: a natural certificate is a prime $p$ that divides $n$, and such that $(a|p)=-1$. The verifier can verify that $p$ is prime in polynomial time and compute the Legendre symbol $(a|p)$ in polynomial time. At least, that's how it seems to me.

I don't know why Arora-Barak say that QNR is not known to be NP. This makes me suspect that I may have misunderstood something, as they know way more about computational complexity than I do.

---
Tags: complexity-theory, np, modular-arithmetic, interactive-proof-systems
---