# Question
Title: Few questions about Mergesort and Recirsion algorithms
1. Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted.
2. How to use recursive algorithm to find the least element of a finite list of unsorted numbers where repetitions of number is allowed.
3. How can Mergesort calls itself n^2 times on a list with n numbers.
4. Is it true if the input list has only 3 numbers, then Mergesort does not need the merging step.
5. Can we find number of elements in a finite list with a recursive algorithm.

Little explanations will be helpful to understand, thank you.

# Answer
It'll be hard to understand numbers 3 and 4 until you're solid on the others. I'd suggest looking closely at the definition of recursion. A solid understanding of recursion is crucial to a lot of computer science.

But for answers, if it helps at all:

> Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted.

```
def greatest(list):
    first = list[0]
    remaining = list[1:]
    if remaining exists:
        return max(first, greatest(remaining))
    else:
        return first

```

> How to use recursive algorithm to find the least element of a finite list of unsorted numbers where repetitions of number is allowed.

Exactly the same as above, but use `min` instead of `max`.

> How can Mergesort calls itself n^2 times on a list with n numbers.

It doesn't. Mergesort runs in $O(n \log n)$. Are you thinking of Quicksort?

> Is it true if the input list has only 3 numbers, then Mergesort does not need the merging step.

Depends on your implementation. The simple cases of algorithms, when $n$ is so far, tend not to be interesting—but have a lot of potential for bugs. So if I were writing Mergesort, I'd start with something like "if you have less than five numbers, do it by brute force (which is $O(1)$ since we have an upper bound on $n$)".

> Can we find number of elements in a finite list with a recursive algorithm.

```
def count_elements(list):
    if list does not exist: return 0
    return 1 + count_elements(list[1:])

```
> 1 votes

---
Tags: algorithm-analysis, sorting, recursion
---


# Question
Title: Why the given statement can't be expressed using predicates and quantifiers in the way described in details?
Suppose there is a statement -

> Some students in this class has visited Mexico.

Solution given is: considering the universe of discourse for the variable $x$ consists of all the people. Our solution becomes $\exists{x}\[S(x)\land{M(X)}\]$ where the predicate $S(x)$ tells $x$ is a student in the class and $M(x)$ tells $x$ has visited Mexico.

The solution also tells $\exists{x}\[S(x)\implies{M(X)}\]$ **is wrong because this expression is true when there is not someone in the class.** So the statement can't be described in this way.

My questions is that only - What's wrong in giving true when there is not someone in the class (or true even when the someone is not student) ? Why exactly can't the statement be expressed using implication?

# Answer
Rephrasing that second version back into English:

> There exists a person $x$, such that *if* $x$ is a student, *then* $x$ has gone to Mexico.

If there exists **anyone who's not a student**, this ends up being true. "*If* false *then* \[anything\]" is always true, so when "$x$ is a student" is false, "*if* $x$ is a student, *then* $x$ has gone to Mexico" is true—*whether or not* $x$ has gone to Mexico.

What you want is:

> There exists a person $x$, such that $x$ is a student, and $x$ has gone to Mexico.

That is indeed what the first given solution means.
> 1 votes

---
Tags: first-order-logic
---


# Question
Title: Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort
I was *convinced* that my idea for a solution to sort $k$ sorted lists into one list would work with a 'variation' on MergeSort. I was told this would not work and had to use Heapsort, but didn't get any explanation or intuition behind it. (I believe the assumption is that each of the $k$ lists had size $\frac{n}{k}$)

Essentially, my intuition behind using Mergesort was that we have $n$ total elements, but all the steps below height $\log k$ in our recursion tree had already been solved. So at height $\log k$ each list is of size $\frac{n}{k}$, so we perform $\frac{n}{k}$ comparisons and $2\frac{n}{k}$ inserts (to form a new list from the two $\frac{n}{k}$ lists) $k$ times in total, which seems to be on the scale of $O(n)$.

We are now one step up on the recursion tree with $\frac{k}{2}$ lists and we will eventually perform $O(n)$ operations $\log k$ times.

Can anyone provide insight as to why this intuition is wrong? Or if right, how I should go about formally proving it?

# Answer
> 4 votes
I would structure a formal proof of the runtime of your strategy as follows (This is, in structure, very similar to what you already wrote, but does not refer to omitted steps of an imaginary run of Mergesort.):

Arrange the $k$ lists as the leaves of an (almost) complete binary tree. Each internal node of the tree represents the merging of the two lists in its children. Clearly this tree has a height of $\lceil\log k\rceil$.

In this structure, the merges on each level of the tree combined will process each element exactly once.\[1\] Thus, they take a combined time in $\cal O(n)$. Adding up over all levels of the tree gives a runtime in $\cal O(n\log k)$.

Note that this argument does not require the lists to be of similar size.

Depending on the audience you may be required to elaborate some more on the $\cal O(n)$ bound. This can be done similar to the reasoning in the question:

Merging two lists with size $n\_1$ and $n\_2$ takes $n\_1+n\_2$ inserts and (in the worst case) $n\_1+n\_2-1$ comparisons. Thus, if we perform $i$ merges on a combined total of $n$ elements, they take $n$ inserts and (in the worst case) $n-i$ comparisons.

---

\[1\] If $k$ is not a power of $2$, the lowest level processes only a subset of the elements. Obviously the bound still holds for this case.

# Answer
> 0 votes
Like I have solved here, you can mathematical arrive at the solution using recurrence relation alone mere by changing base conditions. Assuming at the bottom all leaves are of the size $\frac{n}{k}$,

$T(n) = T(n/2) + \theta(n); \ n\> \frac{n}{k}$

and, $T(\frac{n}{k})= \theta(1)$

By solving above equation we get,

$T(n)=log\_2n+nlog\_2k$

---
Tags: algorithms, sorting
---


# Question
Title: Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?
I came across this problem in *Tim Roughgarden*'s course on *Coursera*:

> In this problem you are given as input a graph $T=(V,E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A perfect matching of $T$ is a subset $F \subseteq E$ of edges such that every vertex $v \in V$ is the endpoint of exactly one edge of $F$. Equivalently, $F$ matches each vertex of $T$ with exactly one other vertex of $T$. For example, a path graph has a perfect matching if and only if it has an even number of vertices.
>
> Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it. (The two algorithms differ only in the choice of $v$ in line 5.)

Algorithm **A**:

```
While T has at least one vertex:
  If T has no edges:
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with maximum degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

```

Algorithm **B**:

```
While T has at least one vertex:
  If T has no edges:
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with minimum non-zero degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

```

Now, the answer key says:

> Algorithm $A$ can fail, for example, on a three-hop path. Correctness of algorithm $B$ can be proved by induction on the number of vertices in $T$. Note that the tree property is used to argue that there must be a vertex with degree $1$; if there is a perfect matching, it must include the edge incident to this vertex.

However, I think I found a counter-example which shows that Algorithm **B** may not be correct. Am I missing something? Consider the following graph (say $T$):

If we follow **B**:

**Step 1:** Let $v=3$ (all vertices have the same degree) and $e=(2,3)$. Remove $e$ along with vertices $3$ and $2$.

**Step 2:** Let $v=1$ and $e=(0,1)$. Remove $e$ along with vertices $0$ and $1$.

**Step 3:** No vertices are left. Hence we get the output: "T has a perfect matching."

But clearly, our original graph was not a perfect matching as all the nodes were of degree $3$.

**Note:** I assumed that *ties* are meant to be broken arbitrarily by the algorithm.

# Answer
> 3 votes
"Consider the following two algorithms that attempt to decide whether or not a given **tree** has a perfect matching". Your graph is NOT a tree as it has a cycle $0, 1, 2, 0$.

Furthermore, your graph does have a perfect matching. In fact, the edges $(2,3)$ and $(0,1)$ obtained by your step 1, 2 and 3 is a perfect matching. And hence, it is not true that "our original graph was not a perfect matching as all the nodes were of degree 3". Plenty of graphs whose nodes are all of degree 3 have a perfect matching.

# Answer
> 1 votes
The algorithms are understated: When a vertex is deleted, *all* edges incident to that vertex are also deleted, otherwise we're left with dangling edges.

Consider the path tree $ A - B - C - D $. Algo A chooses vertex $ B $, and say, edge $ (B, C) $. After deleting vertices $ B $ and $ C $, and all the edges, we're left with vertices $ A $ and $ D $ with no edges. Algo A halts, and incorrectly declares that $ T $ doesn't have perfect matching (it does, $ \\{ (A, B ), (C, D) \\} $).

Lets prove the correctness of algo B by induction. For $ \lvert V \rvert = 1 $, it correctly identifies that $ T $ doesn't have perfect matching. For $ \lvert V \rvert = 2 $, it correctly identifies that $ T $ has perfect matching. Clearly, for $ T $ to have perfect matching, $ \lvert V \rvert $ must be even. Assume algo B works for $ \lvert V \rvert = k $. Let us add a new vertex $ v $ and a new edge $ (v, w) $ to $ T $, where $ w $ is some existing vertex in $ T $. Clearly, for $ T $ to have perfect matching, it must include edge $ (v, w) $ (since that's the only way to match vertex $ v $). By construction, algo B picks $ v $ and removes edge $ (v, w) $ in some iteration, leaving $ \lvert V \rvert = k - 1 $, which by inductive hypothesis, is correctly solved by algo B.

Therefore, algo B is correct.

The solutions to the other questions from the course are available on my blog.

---
Tags: algorithms, graphs, greedy-algorithms, matching
---


# Question
Title: Is NPSPACE also closed under polynomial-time reduction and under log-space reduction?
The complexity classes P, NP, and PSPACE are closed under polynomial-time reduction.

The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction.

I wonder if NPSPACE is also closed under polynomial-time reduction and/or under log-space reduction.

# Answer
> 1 votes
Closed under polynomial-time: Let $A \leq\_P B$ and $B \in NPSPACE$. This means there is a polynomial time computable function $f$ such that $x \in A \iff f(x) \in B$. Using this we can construct a NDTM $N$ which decides $x \in A$ using polynomial space.

```
N(x)
 y = f(x)
 return B(y)
end

```

Since $f$ is computable in polynomial time, it uses at most polynomial space. $B$, too, uses polynomial space, since $B \in NPSPACE$, and so $N$ uses at most polynomial space. This proves that $A \in NPSPACE$.

# Answer
> 2 votes
Savitch's theorem implies that NPSPACE is equal to PSPACE, and so it is closed under polynomial time reductions.

---
Tags: complexity-theory, reductions, complexity-classes
---


title: How to reduce 3-COLOR to 42-COLOR?

text:
# Question
Title: How to reduce 3-COLOR to 42-COLOR?
The requirement is that two adjacent vertices have different colors, and max. 42 colors.

I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes complicated.

Is it similar to $ k\text{-COLOR} $ for any $k$?

# Answer
For an instance of 3-COLOR, try to add a complete graph of size $k-3$, and add an edge between each new vertex and each old vertex. Now you can prove the new graph is $k$-colorable iff the old graph is 3-colorable.
> 5 votes

---
Tags: graphs, np-complete, reductions, colorings
---


# Question
Title: Regular expression over alphabet A = {0 , 1, 2} for words that contain at least one 0 and don't contain 11
I got that I can get (1) followed by not (1) like this $$ (0+2)^\*1(0+2)^\* $$ From this point I'm actually stuck. I can't set the (0) to be somewhere in expression. The only expressions I get are ambiguous (where I can get the same word different ways from regex) and quite long. Is there more elegant and right way to write this expression? Thanks!

# Answer
Well, we know our word contains a $0$, so let's start with that:

$$0$$

Now let's assume that that $0$ is the first $0$ in the word. Then there may be arbitrary $1$s and $2$s before it, but $11$ is not allowed, thus $1$ must be followed by either a $2$ or by our zero:

$$(2 + 12)^\*(10 + 0)$$

Now at the end we can have arbitrary characters, except for $11$. Thus each $1$ must be followed by a $0$ or $2$, or be at the end of the word:

$$(2 + 12)^\*(10 + 0)(0 + 2 + 10 + 12)^\*(1 + \lambda)$$

Here $\lambda$ is the empty string. If that isn't acceptable, we can distribute over the concatenation:

$$(2 + 12)^\*(10 + 0)((0 + 2 + 10 + 12)^\*1 + (0 + 2 + 10 + 12)^\*)$$

Or alternatively we turn our logic around:

$$(2 + 12)^\*(10 + 0)(1 + \lambda)(0 + 2 + 01 + 21)^\*$$

And then distribute over the earlier concatenation:

$$(2 + 12)^\*(101 + 01 + 10 + 0)(0 + 2 + 01 + 21)^\*$$

These are all unambiguous, by the trick of recognizing a *first* zero, rather than the existence of an arbitrary one.
> 1 votes

---
Tags: regular-expressions
---


title: Normal form of relation R

text:
# Question
Title: Normal form of relation R
It is given that for a relation R all the attributes of the relation appear in some of the candidate keys. It is also given that there is only one compound candidate key which exists for a relation, all the other candidate keys are simple candidate keys. What can be said about the normal form of R?

In my opinion, since all the attributes are part of some candidate attribute, it is surely in 3NF. But I am not sure if we can extend our reasoning to claim that R in also in BCNF(as claimed by the solution).

Can anyone please help me out why R can be said to be in BCNF normal form?

Thanks in advance!

# Answer
If you bring the functional dependencies of R in a canonical form, you can have only dependencies in which the right part is constituted only by a single attribute, which is prime, so we are sure that the relation is in 3NF. More, we can divide those dependencies into three sets:

1. The dependencies where the LHS is a single attribute candidate key;
2. Those where the LHS is the (only) compound candidate key;
3. Those where the LHS is a strict subset of the compound candidate key.

The first two kinds of dependencies are compatible with the BCNF, while the third one is not.

It is easy to show that the last set is empty. In fact, if there were a dependency X -\> A, with X a strict subset of the compound candidate key, since A is a candidate key, that is determines all the other attributes, then also X determines all the other attributes, and so it is a candidate key. But this is a contradiction with the hypothesis, so no dependency X -\> A where is X is not a superkey can exists, and the BCNF is surely satisfied.
> 1 votes

---
Tags: database-theory, normal-forms, relational-algebra, relational-calculus
---


# Question
Title: Number of contiguous subsequences summing to a given target
I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$.

For example, if $A = \\{2,5,6,-1\\}$ and $k = 5$ then the answer is $2$, since both $5$ and $6,-1$ sum to $5$.

# Answer
Here is a simple randomized $O(n)$ time algorithm. We start by rephrasing your problem slightly. Suppose that the original array is $a\_1,\ldots,a\_n$. Form a new array $b\_0,\ldots,b\_n$ containing the running sums of the previous array: $$ b\_0 = 0, \qquad b\_i = a\_1 + \cdots + a\_i. $$ Notice that $a\_i + \cdots + a\_j = b\_j - b\_{i-1}$. Therefore we can rephrase the problem as follows:

> Given an array $b\_0,\ldots,b\_n$ and a target $t$, find the number of pairs $i\<j$ such that $b\_j = b\_i + t$.

As an example, if $A = 2,5,6,-1$ then $B=0,2,7,13,12$, and for $t=5$ we get two solutions: $7 - 2 = 12 - 7 = 5$.

The idea now is very simple: we scan $B$ from left to right, and for each $b\_j$, we count the number of values $b\_j-t$ which have occurred previously, storing them using a hash table.

1. Initialize the count of solutions: $N \gets 0$.
2. Initialize a hash table $H$ containing a single entry: $H\[b\_0\] \gets 1$.
3. For $j = 1,\ldots,n$:

* If $b\_j - t \in H$, let $N \gets N + H\[b\_j - t\]$.
* If $b\_j \notin H$, let $H\[b\_j\] \gets 1$, and otherwise let $H\[b\_j\] \gets H\[b\_j\] + 1$.

1. Return $N$.

The same algorithm can be implemented in deterministic $O(n\log n)$ time using a self-balancing binary search tree.

**Optimization:**

We can remove the use of running sums array. Mainly we just need the sum so far value.

1. Initialize the count of solutions: $N \gets 0$.
2. Initialize the sum so far : $S \gets 0$.
3. Initialize a hash table $H$ containing a single entry: $H\[0\] \gets 1$.
4. For $j = 1,\ldots,n$:

* $S \gets S + a\_j$.
* If $S - t \in H$, let $N \gets N + H\[S - t\]$.
* If $S \notin H$, let $H\[S\] \gets 1$, and otherwise let $H\[S\] \gets H\[S\] + 1$.

1. Return $N$.
> 4 votes

---
Tags: data-structures, dynamic-programming, subsequences
---


# Question
Title: Is $L = a^{n}b^{n+m}c^{m} | n,m \geq 0$ a context free or a recursive language?
My initial thought is that L can't be context free since I can use the pumping lemma. I also don't think a grammar can be generated since it needs to keep track of the number of c's and a's. However, I'm having a hard time coming up with an algorithm for this language.

# Answer
Here's a hint:

1. Could you make a grammar for $a^nb^n$, $n\ge 0$?
2. Could you make a grammar for $b^mc^m$, $m\ge 0$?
3. Could you make a production that concatenates the languages in (1) and (2) above?
> 3 votes

---
Tags: context-free
---


# Question
Title: How to analyze the worst case of weighted quick-union method on union-find
Here is exercise 1.5.15 in *Algorithms* 4th Edition by Robert Sedgewick and Kevin Wayne.

> Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial coefficients. Compute the average depth of a node in a worst-case tree with $k = 2^n$ nodes.

Here are my questions:

1) What is the worst-case tree for weighted quick union?

2) How I compute the average depth of a node in this worst-case tree with $2^n$ nodes?

I tried to show through induction that the number of nodes at each level for the worst-case tree in weighted quick-union are binomial coefficients (the first level has $\frac{1!}{0!(1-0)!} = 1$ node). From there I tried to think about how, generally, there are at most $\frac{n!}{r!(n-r)!}$ nodes at the next level. However, I'm unable to think of reasons as to how this makes sense.

Any help with this question is appreciated.

# Answer
> 1 votes
We will use without a proof the following claim that appears in the "Weighted quick-union analysis" of section "1.5 CASE STUDY: UNION-FIND" of the book.

**Claim of (strong) worst case**: the worst case for weighted quick-union happens when the sizes of the trees to be merged by union() are always equal (and a power of 2).

Define tree $W\_n$ recursively. $W\_0$ is the tree with one node whose component root is itself. $W\_{n+1}$ is the tree obtained by combining two $W\_n$ using the union procedure. According to the above claim, a worse case is $W\_n$ for some $n$. Let $D(T)$ be the average depth of a node in a rooted tree $T$.

(**Structure of $W\_n$**) $W\_n$ has $2^n$ nodes in total and $\binom ni$ nodes at level $i$ for $0\le i\le n$. $D(W\_n)=n/2$.

Proof. The base case when $n=0$ and $n=1$ is easy.

Suppose it is true when $n=k$. $W\_{k+1}$ is the join of two $W\_{k}$. WLOG, let us say one of them is at the left and its root is selected as the root of $W\_{k+1}$ during the join. Note that depths of all nodes in the left $W\_k$ remains the same after the join while depths of all nodes in the right $W\_k$ are increased by 1 after the join. So, $$ D(W\_{k+1})=\frac12 D(W\_k) + \frac12 (D(W\_k)+1) = \frac12(\frac k2+(\frac k2 +1))= \frac {k+1}2$$ $W\_{k+1}$ has one root at level 0 and one node at level $k+1$, which was the unique node at level $k$ of the right $W\_k$. The nodes in $W\_{k+1}$ at level $i$ come from the nodes in the left $W\_k$ at level $i$ and the nodes in the right $W\_k$ at level $i-1$, so the number of them is $$\binom ki+\binom k{i-1}=\binom {k+1}i,$$ for all $0\<i\le k$. Proof is done.

---

For completeness, let us define a reasonable version of worst cases. As the above, let $D(T)$ be the average depth of a node in a rooted tree $T$. Let $I$ be a quick-find implementation of the union-find data structure, such as (naive) quick-find or weighted quick-find.

**A definition of general worst cases**. Given implementation $I$, the worst case of $I$ with $k$ nodes is a rooted tree $T$ with $k$ nodes such that the average depth of nodes in $T$ is the largest among all trees obtained by $I$ on $k$ nodes.

Let us define $\mathcal W\_k$ recursively as follows. $\mathcal W\_0$ is the rooted tree with a single node. $\mathcal W\_{2^n+m}$ is the tree obtained by combining $\mathcal W\_{2^n}$ and $\mathcal W\_m$ using the weighted union procedure, for $n\ge0$ and $1\le m\le 2^n$.

(Another version of exercise 1.5.15) Show that any worst case of weighted quick-union is $\mathcal W\_{k}$ for some $k$. Compute $D(\mathcal W\_{2^n})$.

(Sameness of worst cases) Let $\mathcal A\_k$ be the tree obtained by weight quick-union on $k$ nodes using the most accesses. Show that $\mathcal A\_k$ is the same as $\mathcal W\_k$.

# Answer
> 1 votes
This is just a note for myself in the future, in case anyone else out their ends up getting stumped by this problem. This answer expands off of @Apass.Jack's answer.

To prove that each level has a binomial coefficient, we use induction. The base case of $n=1$ is ${1 \choose 0}$ is 1. $n$ represents the height of the nodes while the $0$ is just an arbitrary level of the tree. Now, assume that at each level the number of nodes is ${n \choose i}$ where $0 \le i \< n$ for a tree $T\_n$. When we combine 2 trees of size $2^n$ (let's call them $T\_1$ or $T\_2$), then one of them is chosen to point to the root and the other is chosen to become the root. Let's say that the root of $T\_1$ is chosen to point to $T\_2$. If this is the case, the depth of each nodes increases by 1. That means, in a sense, each node is "pushed" down the tree to the next level below. Now, if, by the inductive hypothesis, we have ${n \choose i}$ nodes at each level of $T\_2$. However, for each level $i$ in the $T\_1$, the number of nodes at is equivalent to the previous level in $T\_1$, $i-1$. Therefore, for each level $i$ in $T\_1$ connected to $T\_2$, the number of nodes is ${n \choose i-1}$. So, if we count the number of nodes on each level, it's just the sum of the number of nodes at each level of $T\_2$ and then the number of nodes at each level of $T\_1$ connected to $T\_2$. So, the number of nodes is ${n \choose i} + {n \choose i-1} = {n+1 \choose i}$. This fits the form of the inductive hypothesis; therefore it is proven.

---
Tags: algorithms, data-structures, union-find
---


# Question
Title: Is the set of context free grammars that generate all words in co-RE?
Is $\\{\langle G \rangle | L(G) = \sum^{\star}\\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.

# Answer
For $A = \\{\langle G \rangle \mid L(G) \neq \Sigma^\ast\\}$ this procedure, returns "yes" iff there is a word $w \notin L(G)$ for a given grammar encoding $\langle G \rangle$ and never halts otherwise:

1. Assume the input encodes a context-free grammar $G$. Otherwise, accept the input if it is not an encoding of a context-free grammar. (Note, however, that we can always assume that every string encodes some dummy grammar, e.g. $(\\{S\\}, \\{a\\}, \\{S \to \varepsilon\\}, S)$).
2. Convert $G$ in Chomsky normal form $G'$.
3. For each $w \in \Sigma^\ast$:
Check whether there exists a derivation in $G'$. Note that for a grammar in Chomsky normal form a derivation of a word $w$ has length $ \leq 2 |w|$, so you only have to check finitely many for each word. If such an derivation does not exists, return "yes", otherwise continue with next word.

Thus, $A$ is recursively enumerable and $A^C = \\{\langle G \rangle \mid L(G) = \Sigma^\ast\\}$ is co-RE.
> 0 votes

---
Tags: formal-languages, turing-machines, context-free, semi-decidability
---


# Question
Title: Token Scanner for programming Language(Lexical Analysis)
This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them.

The Question is : Do i have to convert the entire given DFA to an ε-NFA(which will result in more states),add the keywords(with ε transitions too)and then convert back to a DFA or i just have to add the keywords so that the DFA becomes an NFA and then convert back to a DFA

# Answer
> 1 votes
There's a common misunderstanding about why many construction algorithms (and most notably Thompson's) use ε-NFAs. It's not because it's *necessary* to do so, and it's not because it's *efficient* to do so.

Thompson's construction has the following advantages:

* It's recursive on the structure of the regular expression.
* It's easy to convince yourself that the construction is correct.
* It's straightforward to incorporate certain extensions (e.g. the LEX lookahead operator "/").

Real-world implementations of regular expressions, even if they are based on Thompson's construction, typically optimise a dozen or so common base cases (e.g. Kleene closure of a character set; `[a-zA-Z0-9_]*` expands to something much bigger than it needs to be), saving Thompson's rules for higher levels.

---
Tags: compilers, lexical-analysis
---


# Question
Title: Minimum spanning tree of a connected induced subgraph
I'm doing an online course in which I'm struggling with the following multiple-choice question:

> Suppose $ T $ is a minimum spanning tree of the connected graph $ G $. Let $ H $ be a connected induced subgraph of $ G $. (I.e., $ H $ is obtained from $ G $ by taking some subset $ S \subseteq V $ of vertices, and taking all edges of $ E $ that have both endpoints in $ \> S $. Also, assume $ H $ is connected.) Which of the following is true about the edges of $ T $ that lie in $ H $? You can assume that edge costs are distinct, if you wish. \[Choose the strongest true statement.\]
>
> * For every $ G $ and $ H $, these edges form a minimum spanning tree of $ H $
> * For every $ G $ and $ H $, these edges are contained in some minimum spanning tree of $ H $
> * For every $ G $ and $ H $ and spanning tree $ T\_H $ of $ H $, at least one of these edges is missing from $ T\_H $
> * For every $ G $ and $ H $, these edges form a spanning tree (but not necessary minimum-cost) of $ H $

I don't understand why option 4 is not correct; the hint given is as follows:

> Suppose *G* is a triangle and *H* is an edge.

Suppose that *G* is a triangle with nodes 1, 2, and 3, all connected, and we choose the subgraph *H* from nodes 1 and 2, thus including only the edge (1,2). That edge then forms a minimum spanning tree of those two nodes, no?

Incidentally, the answer

> For every *G* and *H*, these edges for a minimum spanning tree of *H*

is also incorrect.

# Answer
Suppose that $G$ is the triangle on $\\{1,2,3\\}$ (with arbitrary edge weights), that $T$ is $\\{\\{1,2\\},\\{1,3\\}\\}$ (without loss of generality), and consider $H = \\{\\{2,3\\}\\}$, which is induced by $S = \\{2,3\\}$. No edges of $T$ lie in $H$, and in particular these edges do not constitute a spanning tree of $H$.
> 1 votes

# Answer
Consider a triangle graph $ G = C \xleftarrow{3} A \xrightarrow{1} B \xrightarrow{1} C; \therefore T = {(A, B), (B, C)} $. If $ H = {(A, C)}, T \cap H = \emptyset $, which rules out the options claiming $ T \cap H $ forms a spanning tree.

These edges are contained in some minimum spanning tree of $ H $. To prove it, let's establish the *Light-Edge Property* of a MST.

*Light-Edge Property: Let G = (V, E) be a connected undirected weighted graph with distinct edge weights. For any cut of G, the minimum weight edge that crosses the cut is in the minimum spanning tree T of G.*

Proof: Suppose $ e(v, w) \in E, e \notin T $ be the minimum weight edge. If we take a cut $ (A, B) \text{ s.t. } v \in A, w \in B $, then there must be another edge $ e' \in T, e' \neq e $ that connects $ v $ and $ w $ (since by definition $ T $ is a connected subgraph). Let $ T' = T - \\{e'\\} \cup \\{e\\} $; since, $ weight(e') \> weight(e), weight(T') \< weight(T) $. Since $ T $ is a MST, this brings us to a contradiction, and hence $ e \notin T $ cannot be true.

Back to the original question, suppose $ T' $ be a MST of $ H $ and an edge $ e \in T \cap H, e \notin T' $. Arguing on the same lines as the *Light-Edge Property*, we can show that this contradicts the assumption $ T $ is a MST, and $ e $ must be in $ T' $. Since $ e $ is an arbitrary edge, all edges in $ T \cap H $ must be included in $ T' $.

The solutions to the other questions from the course are available on my blog.
> 0 votes

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


# Question
Title: Regular expressions and 'capturing parentheses' with 'backreferences'
We know that regular expressions (RE) are implemented with finite automata (FA). In some language (like JavaScript) in RE there are features like 'capturing parenthesis' with 'backreferences':

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular\_Expressions#special-capturing-parentheses

*(x) Matches 'x' and remembers the match, as the following example shows. The parentheses are called capturing parentheses. The '(foo)' and '(bar)' in the pattern /(foo) (bar) \1 \2/ match and remember the first two words in the string "foo bar foo bar". The \1 and \2 in the pattern match the string's last two words.*

I want to know if this pattern `/(foo) (bar) \1 \2/` is in fact a RE according the definition of RE that we have in theoretical formal language or it is something more powerful. And if it is so I would like to know if this kind of feature is implemented also with FA or in another way (in particualr how it is implemented).

# Answer
> 8 votes
The RE in the Automata Theory are equivalent to FA, but for the programming languages (regexp) this is no longer true.

The regular expressions in the programming languages (like PCRE) are far more powerfull than Regular Expressions (type 3) in the Automata Theory.

The matching parenthesis is neither regular nor context-free, it is a context-sensitive feature. But the RegExp from the question does not fully support Type 2 or Type 1.

The bracket matching is not implemented via FA. In case of PCRE it is implemented by guessing and backtracking.

Take a look at Perl Monks description about PCRE.

# Answer
> 9 votes
These extended notions of regular expressions capture more than just the regular languages. For example, `([ab]*)\1` matches the language $\\{ww\mid w\in\\{a,b\\}^\*\\}$, which isn't regular and isn't even context-free (Example 2.38 of Sipser, *Introduction to the Theory of Computation*, 3rd edition).

"Regular" expressions that don't match regular langauges can't be translated to finite automata, since finite automata match only the regular languages. A side-effect of this is that many libraries don't even try to compile to automata, which can lead to extremely slow matching, even when a "regular" expression is a true regular expression. Russ Cox wrote an excellent article about this, which goes into a lot of the history, too.

# Answer
> 8 votes
The answers are probably answering what you're *intending* to ask, but not what you're asking.

> I want to know if this pattern `/(foo) (bar) \1 \2/` is in fact a RE according the definition of RE that we have in theoretical formal language or it is something more powerful. And if it is so I would like to know if this kind of feature is implemented also with FA or in another way (in particualr how it is implemented).

In fact this **is** a regular expression that can be implemented with a finite automaton, because `\1` is *guaranteed* to evaluate to `foo` and `\2` is *guaranteed* to evaluate to `bar`.

Therefore a regex engine could use this fact to actually create a finite automaton that exactly describes the language you proposed.

However, if you make any captures *conditional*, then this may become false, as others have mentioned.

(Note that I say you ***may*** have trouble, because a language like `/(a(aa|aa)|(aa|aa)a)\1\2/` can *still* be described via a FA. I only gave you a necessary condition, not a sufficient one. **Edit:** It just occurred to me that having a conditional is neither necessary nor sufficient, as `/(a*)\1/` can also be turned into a finite automaton whereas `/(ab*)\1/` cannot. So I guess it was just a rule of thumb.)

# Answer
> 0 votes
Certain regex implementation does not build a DFA. For example, `java.util.regex` OpenJDK implementation does not. As a result, its matching time is slower than DFA compiled implementation like dk.brics.automaton. Yet the later does not support capturing group as a result of underlying implementation.

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


title: Reducing 3SAT to MAX-3SAT

text:
# Question
Title: Reducing 3SAT to MAX-3SAT
I have the following problem:

> Consider the MAX-3-SAT problem: given a Boolean function in Conjunctive Normal Form (CNF) determine the maximum number of clauses that can be satisfied. Prove that this problem is NP-hard.

I know that I'd have to reduce 3-SAT to MAX-3SAT, but I'm pretty lost on how that would work. The related decision problem I figured would be, given clauses and a number k, is there an assignment satisfying at least k of the clauses?

# Answer
Hint: You have a 3SAT formula $\varphi$ in CNF with $n$ clauses and a maximal $m \le n$ number of clauses can be satisfied. What happens if $m \< n$? And what about $m = n$?
> 1 votes

---
Tags: complexity-theory, reductions, satisfiability
---


# Question
Title: Is this a valid induction proof example ?
Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH( suppose a root of rank k has at least $2^k$ vertices in its tree )is a valid one since it just repeating the statement that we are trying to prove ? What about the induction step?(Then a root ... in its tree.)

How should we add more information to make easy to follow and more convincing?

# Answer
This is a perfect example of a sloppily written induction proof. Of course the induction hypothesis is not only repeating the proof's statement; otherwise, it would not qualify as a proof *at all* since it would be assuming the statement is true regardless of the ensuing argument. What is meant, instead, is that $k$ is then *fixed* and the induction step is conducted for this particular choice of $k$.

The following proof structure is more elegant and IMO much easier to follow (esp. for beginners):

* Induction basis: \[...\]
* Induction step: let $k$ be given.
Induction hypothesis (IH): let \[statement you are trying to prove\] be true for $k$.
Then \[ensuing reasoning which shows the statement is true for $k + 1$ by making use of IH\].

This makes it explicit for which $k$ the hypothesis should hold as well as what statement it is exactly that we are trying to prove in the induction step.
> 1 votes

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


# Question
Title: Overflow rule in two's complement arithmetic
In the book by William Stallings the overflow rule overflow rule for 2's complement addition is stated as follows:

> **Overflow rule:** If two numbers are added, and they are both positive or both negative, then overflow occurs if and only if the result has the opposite sign.

Then the book gives the following examples:

**Doubts:**

1. If two numbers with the same sign are added, shouldn't the result have the same sign? How can the result have an opposite sign (e.g., $+1+2=+3$ and $-1-2=-3$)?
2. Point 1 is reflected in the examples (d), (e) and (f). An overflow seem to occur in all of them (though the word "Overflow" is not printed in example (d)), but the sign of the result is the same as that of operands.

# Answer
> 2 votes
1. Yes, if we are talking about *integers*. In two's complement representation with length $n$ you can only represent the integers between $-2^{n-1}$ and $2^{n-1} - 1$ (both bounds inclusive). Thus, the addition operation is *not the same* as the one over the integers—it is not even a proper operation because of overflows, which are left undefined; since it is a completely different operation, other rules apply (as I expect to have been previously mentioned in the book's text).
2. Do not mistake "overflow" for the result having a 1 carry at the left end. In example (b), for instance, the result of addition has such a carry, but it is truncated back to 4 bits, hence producing a correct result; the same happens in (d). However, an overflow occurs in both (e) and (f) because then the result is outside the representation range for 4-bit two's complement, that is, between $-2^{4-1} = -8$ and $2^{4-1} - 1 = 7$.

---
Tags: arithmetic, number-formats, numeral-representations
---


# Question
Title: Lambda Calculus - Call-by-name AND call-by-value reduction
I have been tasked with reducing the following lambda expression:

> (λpq.pqp)(λab.a)(λab.b)

using call-by-name and call-by-value reduction strategies.

**Call-by-name**

strategy: Left-most, outermost redex first but no reduction under lambda.

Step 1) alpha-equivalence

> (λpq.pqp)(λab.a)(λcd.d)

Step 2) Reduction - using the redex (λpq.pqp)(λab.a)

> (λq.(λab.a)q(λab.a)(λcd.d)

Step 3) - substitute (λcd.d) for q

> (λab.a)(λcd.d)(λab.a)

Step 4) - substitute (λcd.d) for a

> (λb.(λcd.d))(λab.a)

Step 5) - substitute (λab.a) for b

> (λcd.d) -\> (λab.b)

*Which gives the same result if you were to use normal order instead.*

**Call-by-value**

strategy: Right-most, innermost redex first but no reduction under lambda

Step 1) alpha-equivalence

> (λpq.pqp)(λab.a)(λcd.d)

Step 2) substitute (λab.a) for c

> (λpq.pqp)(λd.d)

Step 3) substitute (λpq.pqp) for d

> (λpq.pqp)

# Answer
> 6 votes
You misunderstood call-by-value and are doing it backwards, i.e., you are substituting functions into arguments, instead of the other way around. Call-by-value and call-by-name both use the same rules of reduction, but in different places and in a different order.

In your case the call-by-value and call-by-name do not differ, because the arguments are already reduced.

Here is an example, where the difference matters. Reduce

```
(λpq.pqp)((λab.a)(λcd.d))

```

Note that this is different from your examples bacause of the extra parantheses that I put in.

Call-by-name:

```
(λpq.pqp)((λab.a)(λcd.d)) ➝
λq.((λab.a)(λcd.d))q((λab.a)(λcd.d)) ➝
λq.((λab.a)(λcd.d))q((λab.a)(λcd.d)) ➝
λq.(λb.(λcd.d))q((λab.a)(λcd.d)) ➝
λq.(λcd.d)((λab.a)(λcd.d)) ➝
λq.(λd.d)

```

Call-by-value:

```
(λpq.pqp)((λab.a)(λcd.d)) ➝
(λpq.pqp)(λb.(λcd.d)) ➝
(λpq.pqp)(λb.(λcd.d)) ➝
λq.(λbcd.d)q(λbcd.d) ➝
λq.(λcd.d)(λbcd.d) ➝
λq.(λd.d)

```

The difference is that in call-by-value you normalize the argument before you substitute it for the bound variable.

---
Tags: turing-machines, lambda-calculus
---


# Question
Title: Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$
> Give a context-free grammar for the following language: $\\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \\}$

So far, this is the solution that I have been able to come up with, though I am not sure how accurate it is:

$$\begin{align\*} S &\to aSa \mid X \\ X &\to bX \mid a \mid \varepsilon \end{align\*}$$

I worked this out from outside first, which gives me the first and last a's and then used the second rule to get the b's or a's after.

The reason I came up with that answer, I thought the grammer need to start and end with "a" and then have b's in between those a's.

So for each letter with different power we need to have a rule? That is, for $a^i$ we need a rule and for the $n$ power we need another one ?

# Answer
> 2 votes
You could break down the language into simpler parts, e.g., you can generate languages separately for $a^i$ and $b^na^n$, then concatenate them in the end (we know that CFG's are closed under concatenation).

In your case, you can do

> A $\rightarrow$ aA | $\epsilon$

to generate $a^i$, and

> B $\rightarrow$ bBa | $\epsilon$

to generate $b^na^n$, then concatenate by doing:

> S $\rightarrow$ AB

# Answer
> 1 votes
You have created a grammar for $\\{ a^i b^k a^j \mid i, k \in \mathbb{N}\_0, j \in \\{ i, i + 1 \\} \\}$, which is not what you wanted.

Hint: Try to generate the a's and b's for the $b^n a^n$ part *simultaneously*.

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


title: Sorting n element using Fibonacci Heap

text:
# Question
Title: Sorting n element using Fibonacci Heap
How can I design a sorting algorithm of n elements using a Fibonacci Heap?

Will it be a flavoured version of heap-sort where I replace the heap data-structure with Fibonacci Heap?

Your help is appreciated

# Answer
Designing a sorting algorithm based on the Fibonacci Heap is the same as the Heap Sort; Build the Fibonacci-Heap, Extract Minimum.

From the Wikipedia;

> Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.

The data size should be very long to achieve better than the heap sort, but this time you may turn into external sort.

And, remember, for comparison based sorting algorithm, we have $\Omega(n \log n)$ as lower bound.
> 1 votes

---
Tags: sorting, heaps
---


# Question
Title: Finding the longest path in an undirected node-weighted tree
I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the sum of the weights of the nodes in the path is maximum). There's no restriction on what node the path starts or ends.

I have a possible algorithm, but I am not sure it works and I am looking for a proof. Here it is:

1)Select an arbitrary node u and run DFS(u) to find the maximum weight simple path that starts at u. Let (u, v) be this path.

2)Run DFS(v) to find the maximum weight simple path that starts at v. Let this path be (v, z).

Then (v, z) is a simple path of maximum weight. This algorithm is linear in the size of the graph. Can anyone tell me if it works, and if so, give a proof?

Note: The Longest Path Problem is NP-Hard for a general graph with cycles. However, I only consider trees here.

# Answer
> 2 votes
No, your algorithm does not work sometimes.

Here is a counterexample. Let graph $G$ have five weighted nodes, $A\mapsto 1$, $B\mapsto -1$, $C\mapsto 0$, $D\mapsto 1$, $E\mapsto 1$. There are four edges, $AB$, $BC$, $CD$ and $CE$.

Let us run your algorithm.

1. Select node $B$ and run DFS($A$). We may get the maximum weight simple path $B, A$, whose weight is 0.
2. Run DFS($A$), we may find the maximum weight simple path that starts at $A$, which is $A, B, C, D$, whose weight is 1. That path is returned.

However, the simple path with the maximum weight is actually $D,C,E$ whose weight is $2$.

---
Tags: algorithms, graphs
---


# Question
Title: Strassen algorithm for matrix multiplication complexity analysis
I see everywhere that the recursive equation for the complexity of Strassen alg is: $$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me. The parameter $n$ is supposed to be the size of the input, but it seems that here it is one dimension of a matrix while the input size is actually $n^2$. Also, each matrix of the input is divided to 4 sub matrices so it seems the recursive equation should be $$T(n) = 7T(\tfrac{n}{4}) + O(n).$$

# Answer
It's true that the parameter $n$ usually denotes the size of the input, but this is not always the case. For square matrix multiplication, $n$ denotes the number of rows (or columns). For graphs, $n$ often denotes the number of vertices, and $m$ the number of edges. For algorithms on Boolean functions, $n$ denotes the number of inputs, though the truth table itself has size $2^n$. There are many other examples.
> 13 votes

# Answer
It's back to the size of the matrix. Suppose the original matrix is $n\times n$. Hence we will consider $T(n)$ as a computation of two matrix with size of $n\times n$. When we divide the original matrix to 4 part, size of each part is $\frac{n}{2}\times \frac{n}{2}$. Hence, the computation cost of multiplication of two matrices with this size is $T(\frac{n}{2})$.
> 5 votes

# Answer
Time complexity is *often* based on the input size, but it is not an absolute requirement. In this case, for the multiplication of n x n matrices, it seems most natural to count the number of operations based on n, not on the problem size n x n.
> 0 votes

---
Tags: algorithms, complexity-theory, divide-and-conquer, matrix
---


# Question
Title: Some explanations needed about Negation in Gentzen's Natural Deduction rules
I'm beginning to have an understanding thanks to some videos relating to "Proposition as Types". But, I don't come from a theoretical CS background, so maybe I'm blocked probably a bit by notation...

Given that I have understood, Conjunction, Disjunction, Implication,

I'm stumbling on Negation:

```
intro:
[A]
 /\
---
¬ A

elim:
A ¬A    /\
----   ---- .
 /\     D

```

It comes from an extract of the Gentzen paper during a P. Wadler talk Proposition as Types, and I'm stuck by the meaning of the symbol resembling `/\`. What is this symbol called, and what is the meaning ?

Moreover, I have no clue about that `D` (which was not introduced) and `.` in:

```
 /\
---- .
 D

```

Is it anything related to `_|_` bottom in Haskell, or else the `Void` empty type?

All those missing pieces makes me unable to grasp the meaning and how to apply these rules.

**EDIT**: I was also having difficulties with the Universal Introduction rule and this video covers the topic.

# Answer
> 1 votes
I'm guessing your first rule is:

> \begin{align\*} &\[A\]\\ &~~\vdots\\ &~\bot\\ &\overline{\lnot A}\qquad (I\lnot) \end{align\*}

This means that in order to derive $\lnot A$ one must first assume $A$ (that is $\[A\]$) and derive a contradiction ($\bot$), the dots between mean a finite number of steps.

> $$ \frac{A \quad \lnot A}{D} \qquad (E\lnot) $$

This latter rule with $D$ seems to be ex falso quodlibet, since:

$$ \frac{A \quad \lnot A}{\bot} \qquad (E\lnot) $$

therefore:

$$ \frac{\bot}{D} $$

it says that you can derive anything (some $D$) from a contradiction.

Those $(I\circ)$ and $(E\circ)$, where $\circ$ is some operation mean Introduction-Elimination rules. In Gentzen's formulations all rules come in pairs.

---
Tags: natural-deduction
---


# Question
Title: Nondeterministic automaton accepting only words whose first letter is identical to their next to last letter
I was asked this question and could not come to the correct answer:

> Let $L$ be the language of all words over $\\{a,b\\}$ where the first letter is identical to the letter that is next to last. (Pay attention – every word with length 2 is in the language.)
>
> Sketch a nondeterministic automaton that accepts this language.

Any help would be appreciated.

# Answer
Hint: you want to make states $x/y/z$ which mean that $x$ is the first symbol of the word, $y$ is the second to last symbol seen, and $z$ is the last symbol seen.

I will show you half of the final machine, the one for words starting with $a$. Note that "!a" here means any symbol not equal to a, or no symbol at all.
> 2 votes

---
Tags: automata
---


# Question
Title: Which one of these two sets is computably enumerable?
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.

1. {M : |L(M)| \<= 330}
2. {M : |L(M)| \>= 330}

I don't quite understand what this question is asking. Does the first question mean M accepts at most 330 inputs?

---

My thoughts:

1. co-CE
2. CE (Construct a M to check the input, if \>= 330 inputs are accepted, halt)

I am not sure if I am correct, and can I prove the first question is not CE by decribing TM may never halt?

# Answer
As Rick commented, the first question is asking whether the set of Turing machines that recognize no more 330 strings is computably enumerable. Similarly, the second question is asking whether the set of Turing machines that recognize no less 330 strings is computably enumerable.

Let us show that second set is computably enumerable using dovetailing. Let $M\_1, M\_2, \cdots$ list all Turing machines. Let $w\_1, w\_2,\cdots$ list all words over the alphabet. We can build a Turing machine using the universal Turing machine to run the following procedure.

* for i from 1 to infinity:
    + for j from 1 to i:
        - let string\_count be 0
        - for k from 1 to i:
            * run $M\_j$ with input $w\_k$ up to $i$ steps. If it is found $M\_j$ accepts $w\_k$, add 1 to the string\_count. If string\_count is no less than 330, append $M\_j$ to the output tape.

It is clear that every Turing machine that accepts no less than 330 strings will be added to the list at some point of time. Although each of them may be listed many times, that does not matter. Also only that kind of machines will be included in the list. So we have shown that the second set is computably enumerable.

Rice's theorem tells us the second set, which is $$\\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is no less than } 330 \\}$$ is undecidable. Since it is computably enumerable, its complement (relative to the decidable problem whether a string encodes a Turing machine) $$\\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is less than } 330 \\}$$ cannot be computably enumerable. Well, the size of that number 330 does not affect our argument here. If we change it to 331, we see that the first set is not computably enumerable.
> 4 votes

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


title: PCP with commutative alphabet

text:
# Question
Title: PCP with commutative alphabet
Post's Correspondence Problem is known to be undecidable. A variant of PCP, namely PCP with partially commutative alphabets is also known to be undecidable. Is the following variant also known to be undecidable?

**PCP with commutative alphabet.** Given and alphabet $\Sigma = \\{a\_1, a\_2, \ldots, a\_K\\}$ and $2N$ sequences $\gamma\_1, \gamma\_2, \ldots, \gamma\_N, \delta\_1, \delta\_2, \ldots, \delta\_N \in \Sigma^\*$. Determine if there is a sequence of integers $\\{i\_j\\}\_{j=1}^M$ such that for each $1 \leq j \leq M$, $i\_j \in \\{1, 2, \ldots, N\\}$ and for each $1 \leq m \leq K$,

$\\#(a\_m, \gamma\_{i\_1} \gamma\_{i\_2} \ldots \gamma{i\_M}) = \\#(a\_m, \delta\_{i\_1} \delta\_{i\_2} \ldots \delta\_{i\_M})$ where $\\#(a, w)$ denotes the number of occurences of the symbol $a$ in the string $w$.

Notice why I used the term "commutative" for the alphabet: the order of the symbols in the strings does not matter; only the counts need to be equal.

In general, is any variant of (unbounded) PCP with commutative alphabet known to be decidable or undecidable?

# Answer
Let $\gamma\_{ij},\delta\_{ij}$ be the number of characters $\sigma\_j$ in $\gamma\_i,\delta\_i$ (respectively). Then the PCP instance has a solution if there exist non-negative integers $a\_1,\ldots,a\_N,b\_1,\ldots,b\_N$ such that for all $j \in \\{1,\ldots,K\\}$, $$ \sum\_{i=1}^N a\_i \gamma\_{ij} = \sum\_{i=1}^N b\_i \delta\_{ij}. $$

While integer programming is hard in the general case, in this case we can solve it using linear programming in polynomial time. I claim that the program above has a solution in non-negative integers iff it has a solution in non-negative *reals*. One direction is obvious. In the other direction, suppose that the linear program corresponding to the integer program above (replacing non-negative integers with non-negative reals) is feasible. Then there is a solution for the program above in the non-negative *rationals* (every vertex of the polytope would do). Multiplying this solution by a common denominator, we obtain a solution of the original integer program.
> 3 votes

---
Tags: undecidability
---


# Question
Title: More complicated resources than time and space complexity
The wikipedia page on computational resources states that there are many different resources that have been defined:

> In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
>
> The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, **but many more complicated resources have been defined.\[citation needed\]**

Unfortunately, this claim doesn't have a citation.

**What are these more complicated resources that have been defined?**

* I can imagine something like parallel processes used?
* the wikipedia talk page talks about communication bandwidth: e.g. network bandwidth, and memory busses. ( this seems fairly "processor-dependent"? Not sure if there is a theoretical analysis of this).

# Answer
It is interesting that claim, "many more complicated resources have been defined" has been present since the very first version of that Wikipedia page created in 2006, whose accompanying comment is "start article (will have to finish later, lightning storm)". That page is created by Wikipedia user Creidieki. That claim has never been explained on that page.

What are these more complicated resources that have been defined?

Here are some computation resources that may or may not be more complicated. Some of them may seen as variations of the computation time and memory space.

We could also think of some more outlandish ones. How can we measure the complexity of lambda calculus reasonably? Could priority be considered as computation resource as well?

In addition to the resources that are needed to run algorithms to solve problems, We can also examine the resources or even techniques that are needed to build the computation machines.

In summary, we can check the list of complexity classes in Wikipedia or Complexity Zoo to find various computation resources that are considered in complexity analysis. Hopefully, this answer have given you a rough idea how diverse and interesting the computation resources and the complexity classes are.
> 5 votes

---
Tags: complexity-theory
---


# Question
Title: Write a routine to print the numbers 1 to 6 and back to 1 again without using any loops
Can anyone help with this question? I currently have this solution that prints

> 1 2 3 4 5 6

but I'm having trouble going back down to 1.

```
public class noLoop{

     public static void main(String []args){
        noLoop(6);
     }

     public static void noLoop(int n) {

         if (n == 0) {
             return;
         }

         else {
             noLoop(n-1);
             System.out.println(n);
         }
     }
}

```

# Answer
> 0 votes
As I understand, this problem is NOT about just printing "1 2 3 4 5 6 6 5 4 3 2 1" or "1 2 3 4 5 6 5 4 3 2 1". The number 6 is just to give an example of an integer.

Since noLoop is not successful, it is only natural to use a second recursion method. So noLoop and noLoop2 will do the job.

If you have to use one recursion method, an extra parameter such as `StringBuilder result` might be needed to store what we got so far. That is how noLoop3 comes. (Another way is to use a static variable instead of the extra parameter. I will let you to figure that out.)

```
public class NoLoop {
    public static void main(String[] args) {
        noLoop(6);
        noLoop2(6 - 1);

        StringBuilder sb = new StringBuilder();
        noLoop3(6, sb);
        System.out.println(sb);
    }

    public static void noLoop(int n) {
        if (n > 0) {
            noLoop(n - 1);
            System.out.println(n);
        }
    }

    public static void noLoop2(int n) {
        if (n > 0) {
            System.out.println(n);
            noLoop2(n - 1);
        }
    }

    public static void noLoop3(int n, StringBuilder result ) {
        if (n > 0) {
            result.insert(0, n).append(n);
            noLoop3(n - 1, result);
        }
    }
}

```

By the way, this question borders on programming, which is off-topic here. Please consider posting this kind of question to Stackoverflow later on.

# Answer
> 3 votes
```
public class Foo {
    public static void main(String[] java_is_silly) {
        System.out.print("1 2 3 4 5 6 5 4 3 2 1");
    }
}

```

# Answer
> -1 votes
This is clearly a Computer Science problem to demonstrate functional programming and recursion. It needs action on the head and tail of recursion and a middle exit.

Those who only program without applying Computer Science would not approach it that way and would get poor marks from me!

```
// Recursion demonstration in Java
class NoLoop
{
    public static void main(String [] args)
    {
        doit(1);
        System.out.println();
    }

    static void doit(int i)
    {
      System.out.print(i + " ");
      if (i >= 6) return;
      doit(i+1);
      System.out.print(i + " ");
    }
}

```

---
Tags: recursion, java
---


title: Dijkstra’s shortest path algorithm

text:
# Question
Title: Dijkstra’s shortest path algorithm
I'm learning about **single source shortest path algorithms** and need to clarify few doubts-

1. Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers.
2. Does Dijkstra’s assumes that the graph searched by it is free of cycles.
3. Relaxing an edge is same as setting its weight to 0.
4. Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.
5. Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.

# Answer
> 1. Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers?

Dijkstra’s shortest path algorithm works for non-negative numbers. The Bellman-Ford algorithm works in the general case, i.e. works for the negative numbers, too.

> 2. Does Dijkstra’s assumes that the graph searched by it is free of cycles.

In an undirected graph, If there is no cycle, it is a Tree, not necessarily rooted. The paths are unique. Dijkstra’s algorithm can work with cycles.

You probably mean that free of negative cycles; If there is a negative cycle and the source can reach it, then the cost of path has not defined.

> 3. Relaxing an edge is same as setting its weight to 0.

Relaxation is historical naming, the correct name is *tighten*. Relaxation tests an edge wheater in can improve the current estimate of a node.

> 4. Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.

Actually, it yields the shortest paths tree with their values, the running time is $\mathcal{O}((V+E)\log V).$ If you look at the algorithm, it considers only the current neighbors while constructing the shortest path tree. The bottleneck is the extract-min operation on the Heap. For a theoretical speed up, one can use Fibonacci Heaps that yield $\mathcal{O}(V \log V + E)$

During the relaxation process, the predecessors updated only if there is a need for relaxation. When the Dijkstra's algorithm finishes, the shortest path tree is ready.

> 5. Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.

Remember, Dijkstra's algorithm can find one-to-all shortest path if the Graph is weighted and directed. It doesn't care where the map is taken as long as it is modeled as a Graph. However, if the graph is an actual map and/or there is also a heuristic distance information one can achieve better than Dijkstra's algorithm, see A\* and this comparison article Engineering Route Planning Algorithms.
> 1 votes

---
Tags: algorithms, algorithm-analysis, shortest-path
---


# Question
Title: Which one of the following string is DCFL
Is odd length pallindrome DCFL or NCFL?

## Like

1) $L=\\{w1w^R\mid w \in \\{0, 1\\}^\*\\}$

## or

2) $S\rightarrow aSa\mid bSb\mid a$

## or

## Suppose odd length String like

3)$S\rightarrow aSa\mid bSb\mid aSb\mid bSa\mid a\mid b$

We get information about even length palindrome, that it can never be DCFL, but what about odd length?

# Answer
Hint: The DCFL among the three alternatives is not only a DCFL, it is a *regular* language.

(Recall that the regular languages form a subset of the DCFLs.)

Hint no. 2: The other two alternatives are essentially the same language, only over different alphabets.
> 1 votes

---
Tags: automata
---


# Question
Title: Efficiency/Redundancy in Chomsky normal form
I have a context-free grammar with the following production rules, $S$ being the start symbol:

$$\begin{align\*} S &\to AB \\ A &\to a \\ B &\to a\end{align\*}$$

Is this in Chomsky normal form?

My problem is I thought CNF is supposed to be an efficient way to write a grammar, yet the grammar is not efficient in the sense that we can clean its rules as follows:

$$\begin{align\*}S &\to AA\\ A &\to a\end{align\*}$$

# Answer
*Both* grammars are in CNF. One of the possible rule formats for CNF is $A \to BC$, where $A$, $B$, and $C$ are non-terminals, but it is not necessary for them to be different from another. Hence, in your case, $S \to AA$ is also a valid rule for CNF.

I should add CNF has nothing to do with an "efficient" way to write a grammar (however you should define that; if you simply mean the description is shorter, then counterexamples abound). Rather, CNF is useful when employing techniques such as the CYK algorithm.
> 0 votes

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


# Question
Title: How to give a context free grammar for any given language ie: a^n (ba)^m a^n
i am trying to understand Context free grammar and generate a CFG for any given language.

when you're given a language , what is the best way to generate a CFG from it? are there any steps to follow to help you create a CFG for any language? is there ways of breaking down the language to make it simpler so that it helps you generate the CFG.

for example if i was given **L={a^n (ba)^m a^n | n,m \>=0 }**

does that mean i need to have equal number of a's on both side, and have zero or more ba in between the a's ?

S---\> aSa |ε

X---\> baX |ε

any helps is appreciated.

# Answer
The reference question "How to prove that a language is context-free?" has some examples to build a context-free grammar using a simple toolbox. As is mentioned there one needs a "nesting structure" to make this work.

You ask about the difference between language like $L\_1 = \\{ab^na^nc \mid \dots \\}$ and $L\_2 = \\{a^n (ab)^m a^n \mid \dots \\}$. In both cases the parts that are iterated the same $n$ number of times have to be generated in parallel. Productions like $Y\to b Y a$ are good for that.

In case of $L\_1$ the $a\dots c$ pair is around the repeat $b^nc^n$ and can be generated before $S\to a X c$, but also independently as $S\to AXC, A\to a, C\to c$ . In case of $L\_2$ the $(ab)^m$ is inside the repeat $a^n\dots a^n$ and has to be generated after, like your own solution $S\to aSa, S\to X, X\to abX\mid \varepsilon$.
> 0 votes

---
Tags: context-free
---


# Question
Title: Resource Reservation: No Greedy Approach?
I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only active if they have all requested resources.

Instance: A set of processes P, a set of resources R, the set of resource requests for each process, and an int k. Question: Is it possible to allocate resources so that at least k processes are active at the same time?

My initial inclination was that a greedy approach makes sense here. Sort the jobs in increasing order of number of resources requested, then allocate resources to processes until all resources are allocated or all processes have been attempted to be scheduled, as below:

```
procedure reserve_resources(P, R, k):
  int jobs_active = 0;
  Order processes in ascending order of number of resources requested;
  for each process:
    if (all of the processes' requested resources are available):
      allocate resources to that process;
      jobs_active++;
    end if;
  end for;

  if (jobs_active >= k):
    return "YES";
  else:
    return "NO";
  end if;
end procedure;

```

I've come across an answer for this problem which shows NP-completeness by reducing Independent Set to this resource reservation problem. For the IS instance G = (V, E), it makes the set of resources equal to E, the set of process equal to V, and any edge incident to an vertex is a resource requested by that process. If k processes have disjoint resource requests, then the vertices corresponding to those processes form an independent set.

This reduction makes sense to me and I know that IS is NP. I believe that P != NP, and I certainly don't think I've just proven the opposite while working on homework in my undergrad algorithms class. But I also can't find a counterexample to the algorithm I've presented. My question is, where does this algorithm fail?

# Answer
> 2 votes
Your algorithm is correct when all resources are interchangeable. For example, the resources are 100 memory units.

However, it may not return the right result when the resources are not of the same kind. One way to find a counterexample is to search for counterexample of the greedy algorithm on the maximum independent set is to, uh, search online. One counterexample I found is the following, where vertex $C$ is selected first.

.

User j\_random\_walker proposed the following strategy to figure out a counterexample, where the tip in the last statement is added by me.

> Figure out how to force your algorithm make the "wrong" choice in the first step: Since your algorithm always chooses the process with the fewest resource requests first, that means you have to design the problem instance so that this choice can only lead to suboptimal solutions. Work backwards to discover constraints: Clearly if the optimal solution has all 2 processes, then they can't have any conflicts, so any order of choosing them will give the same answer. So the smallest counterexample must have at least 3 processes. *We will not consider processes that only request one resource; it cannot be wrong to included those processes.*

Here is the smallest counterexample on which the greedy algorithm might fail, which has 3 processes and 4 resources. Process $P$ requests resources $a$ and $b$. Process $Q$ request $a$ and $c$. Process $R$ request $b$ and $d$. When the greedy algorithm select $P$ first, it cannot select any more process.

---

Exercise. Find a counterexample on which the greedy algorithm will always fail.

---
Tags: graphs, np-complete, reductions
---


# Question
Title: Find shortest path that goes through at least 5 red edges
Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges are colored in red (let's say that the rest are colored in blue).

I want to find an efficient algorithm that find the shortest path between $s$ and $t$ that goes through at least 5 different red edges.

Notice that going more than once through the same red edge is still considered as going through 1 red edge in the path.

One idea that I had was creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$. That means that if we go through some red edge $e$, then the path will "move" to a variation of $G$ where $e$ is colored in blue and all the rest is the same.

However in this solution I will have to copy each node and each edge around 400 times. This will result in the same complexity asymptotically, but with such a big constant it seems really not efficient.

Another idea, was to somehow build the new graphs "on the run" of Bellman-Ford algorithm, but I don't really know how to do it.

I'll appreciate some help.

# Answer
> 4 votes
What about reducing the problem first ?

UPDATED with more details :

1. Build 2 node subsets:

* Vs contains s and the 10 reached nodes of the red edges (called a1, a2, ..., a10 hereafter). This is a 11 nodes set.
    * Vt contains t and the 10 sources nodes of the red edges (called b1, b2, ..., b10 hereafter). This is another 11 nodes set.
2. Build a distance matrix M from Vs to Vt (11x11)
3. Do 11 Dijksta explorations, one starting from any node of Vs to reach all nodes of Vt. So you get 11 shortest distances to report in the matrix M. The diagonal terms are irrelevant (s-\>t or ak-\>bk).
4. For each row of M, add wi (the weight of the red edge) to all elements (0 for s row). This is the price of crossing the red edge.
5. Build an new graph G' with 11 nodes. node N0 for s&t and nodes Nk for each red edge (ak & bk). Then create all edges using matrix entry: w(Ni -\> Nj) = M\[i\]\[j\].
6. Now your initial problem is equivalent to find a loop of 6 nodes containing N0 in G'. Use any method to test all combinatoric for instance Apass.Jack one. This step in NP complete.

# Answer
> 2 votes
Here is the golden rule of dynamic programming. Adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. In other words, when you cannot move from smaller subproblems to a larger subproblem because of a missing condition, add another parameter to represent that condition.

What is the extra condition here? At least 5 different red edges out of the given 10 edges have to be included in the path. Since there are 10 edges, we will add 10 parameters. Since each parameter has only two values, included or not\_included, we can use one number to represent the value of those 10 parameters. That is, a number $0\le s\le 1023$, $$ s = s\_0 + s\_12+s\_22^2+s\_32^3+s\_42^4+s\_52^5+s\_62^6+s\_72^7+s\_82^8+s\_92^9$$ where $s\_i=1$ if the path does include $i$-th red edge and $s\_i=0$ otherwise.

What is the subproblem here? Find the length of shortest path with signature $s$ between two vertices, where $s=(s\_0,s\_1, \cdots, s\_9)\in \\{0,1\\}^{10}$.

If there is no negative-weighted edges, a straightforward adaptation of Dijkstra's algorithm starting from $s$ will work for these subproblems. The answer will be the minimum among the shortest path with signature $a$ between $s$ and $t$ where at least 5 bits of $a$ are set to 1.

If there are negative-weighted edges, we will consider adapt the Floyd–Warshall algorithm. The details will not be included in this answer.

Note that the above suggestion only leads to the weight (length?) of shortest path. To find the actually path, we have to add another parameter to record the previous node that leads to the current shortest path of certain signature.

---

What Yuval suggested in his comment should be, I believe, essentially the same as what I have abstracted as the golden rule of dynamic programming. In fact, this answer is roughly to confirm the idea in the question, "creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$". Hopefully the implementation here together with some bit twiddling might be easier and faster.

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


# Question
Title: Grover algorithm when element not present in the array/database
I've been reading about the Grover algorithm for finding elements in an unstructured database by the means of quantum computing, and even done some exercises.

What I don't understand (and can't find anywhere) is what is supposed to happen if the element is NOT present in the database. The oracle would never flip any qubit, and then I don't know what would happen with the inversion about the mean operator. Would the algorithm keep iterating forever?

# Answer
> 0 votes
The most basic version of Grover's algorithm has a fixed number of iterations and assumes there is one marked item. If there is no marked item instead of one marked item, you will do those iterations but then get a random answer.

As mentioned in the wikipedia article on Grover's algorithm, the algorithm can be extended to work when there are an unknown number of marked items while still running in $O(\sqrt{N})$ time. There's just more details to work out.

---
Tags: quantum-computing
---


# Question
Title: What is an example of a decidable language?
I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?

# Answer
> 3 votes
No.

As an example of a language that is decidable but does not have a context-free grammar is the language over the decimal digits that only contains the prime numbers.

# Answer
> 1 votes
$\\{a^nb^nc^n \ |\ n\geq 0\\}$ is one of the most famous non context-free languages. Consequently, it is also non regular. It is clearly decidable.

---
Tags: formal-languages, regular-languages, context-free, decision-problem
---


# Question
Title: In a kernel, what are "global constructors"?
I am a beginner developing kernels (though I have developed several Hello World programs in C and C++). I frequently see reference being made to **global constructors** (e.g., osdev https://wiki.osdev.org/Calling\_Global\_Constructors), but I have not been able to find a clear definition or in it.

Could someone please guide me to the correct definition? I know they are called before the kernel, but I am having trouble understanding why.

The kernel of which I take the example, is this: https://github.com/AlgorithMan-de/wyoos/commit/7eb9f8a1d5089cf7587e553e601c42db34dc94a2

in the linker.ld file, have this code:

```
  .data  :
  {
  start_ctors = .;
  KEEP(*( .init_array ));
  KEEP(*(SORT_BY_INIT_PRIORITY( .init_array.* )));
  end_ctors = .;

  *(.data)
  }

```

in the kernel.c file, have this code:

```
typedef void (*constructor)();
extern "C" constructor start_ctors;
extern "C" constructor end_ctors;
extern "C" void callConstructors()
{
  for(constructor* i = &start_ctors; i != &end_ctors; i++)
     (*i)();
}

```

# Answer
> 2 votes
The link you provided has a clear definition:

> This tutorial discusses how to correctly invoke global constructors, such as those on global C++ objects. These are supposed to have run before your main function, which is why the program entry point is normally a function called \_start.

In most OSs, there is a step where the process' memory is filled with its initial values. For C code, that is typically sufficient. However, sometimes you want to execute some code *before* `main()`, which is your official entry point. For example, in C++, you need to be able to call the constructor of all global objects before `main()` is invoked.

To resolve this, and any other run-time activities which must be done before `main()`, each system provides some way to execute a function before main. The article mentions that some treat it as a simple array of function pointers, but some compilers will obscure it and hide it.

The key takeaway is that these are handled before the *entry point* of your program.

---
Tags: operating-systems, os-kernel, c
---


# Question
Title: Evaluation of $\beta$-Reduction with Parentheses in $\lambda$-Calculus
I'm studying $\lambda$-calculus, and had a question regarding an exercise I came across. I understand that $\lambda$-calculus uses three main strategies of evaluation, but I'm having trouble applying it. Specifically $\beta$-reduction.

For example, for $1 + 2$:

\begin{align} 1 + 2 & = \lambda n.\lambda m.\lambda s. \lambda z. m\ s\ (n\ s\ z)\ 1\ 2 \\ & = \lambda s. \lambda z.\ 2\ s\ (1\ s\ z) \\ & = \lambda s. \lambda z.\ 2\ s\ ((\lambda s. \lambda z.s\ z)\ s\ z) \\ & = \lambda s. \lambda z.\ 2\ s \ (s\ z) \\ & = \lambda s. \lambda z.(\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z) \\ & = \lambda s. \lambda z.s\ (s\ (s\ z)) \\ & = 3 \end{align}

The particular part that I'm having trouble understanding is the $\beta$-reduction at the last step before deriving the final $\lambda$ expression. More specifically, how $\lambda s.\lambda z. (s\ (s\ z))\ s\ (s\ z)$ reduces to $s\ (s\ (s\ z))$.

My understanding is that in order to perform $\beta$-reduction, we need to identify redexes of the form $(\lambda x.e\_1)\ e\_2$. Using this understanding, my initial approach would be:

\begin{align} \lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z) & = \[\lambda s. \lambda z. (s\ (s\ z))\ s\]\_{redex}\ (s\ z) \\ & = \lambda z. (s\ (s\ z))\ (s\ z) \\ & = \[\lambda z. (s\ (s\ z))\ s\]\_{redex}\ z \\ & = s\ (s\ (s\ z)) \end{align} Is my approach correct? If so, is it valid for me to drop the parentheses arbitrarily as I did in the third line?

# Answer
You are missing one important pair of parentheses, around an expression for $2$. It should be $$\bigl(\lambda s. \lambda z. (s\ (s\ z))\bigr)\ s\ (s\ z)$$ Then we reduce by replacing $s$ with $s$ and $z$ with $(s\ z)$, obtaining $$(s\ (s\ (s\ z)))$$

---

On the other hand, $\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z)$ doesn’t reduce any further because it has no redex. It is just a $\lambda$-abstraction with variables $s,z$ and body $(s\ (s\ z))\ s\ (s\ z)$. Abstraction always goes as far right as possible.

---

Generally, when we have a *name* for expression (e.g. $2$, $myexp$,...) within some larger expression, we must surround it with parentheses when we expand it to its true lambda form, to avoid confusion regarding applications.
Just like you did with $1$ in the third row.

You can explore $\lambda$-calculus reductions, test your ideas and see how various expressions are implemented with this interpreter.
> 3 votes

---
Tags: reductions, lambda-calculus
---


# Question
Title: Keywords/terminology for using "extra" information in search problems?
I am trying to find references on a particular idea, but I don't know which keywords to use in a google search.

the idea is: as an example, consider graph search. maybe the problem is: find a path from node $X$ to node $Y$. We can consider two versions of this problem:

1. For any node $n$, we can query only the information: which other nodes are connected to it?
2. For any node $n$, we can *additionally* query the information: what is the "airplane distance" between $n$ and $Y$.

Clearly, if we have the additional information from (2), we can construct a larger set of possible search algorithms, in particular, ones that are faster.

**My question is: What terminology/keywords do I need to search to read about this phenomenon that some search algorithms have more "heuristic" information at their disposal than others, and can therefore employ better search heuristics?**

# Answer
> 1 votes
Such search algorithms would generally be called **informed search algorithms** (or methods, techniques, etc.), or simply **heuristic search algorithms**. We might also call them **guided search algorithms**.

An example would be A\* search, which uses precisely what you call "airplane distance" (more commonly referred to as the straight-line distance) as a heuristic.

**Best-first search** techniques would be somewhat closely-related, but they may have a slightly different meaning (they may, for example, use statistics / information gathered earlier during the same process for guidance during a later part of the search process, rather than heuristic domain knowledge given a priori).

---
Tags: terminology, search-algorithms
---


# Question
Title: Does this sorting algorithm already exist? And if so, what is its name?
I created this algorithm off the top of my head this morning. It has one loop, therefore it has a time complexity of O(n) and only stores two variable during loop so it has a space complexity O(1) time. Please correct me if the last statement is wrong. I looked online and I don't see other sorting algorithms that look like mine nor have the complexity I just mentioned. In short, did I just create a new sorting algorithm or does this sorting algorithm already exist? And if it already exists, what is its name (i.e. what type of sorting algo is it)?

```
def sort_algo(lst):
    mid = len(lst) // 2
    left = 0
    right = len(lst) -1
    nextup = left + 1
    nextdown = right - 1

    while left < right or right > left:
        if lst[left] >= lst[mid]:
            lst[left], lst[mid] = lst[mid], lst[left]

        if lst[left] > 0:
            if lst[left] > lst[nextup]:
                lst[left], lst[nextup] = lst[nextup], lst[left]

        if lst[right] <= lst[mid]:
            lst[right], lst[mid] = lst[mid], lst[right]

        if lst[right] < lst[nextdown]:
            lst[right], lst[nextdown] = lst[nextdown], lst[right]

        left += 1
        right -= 1

    print(lst)

sort_algo([7,2,1,6,8])
sort_algo([2,1,3,4,5])
sort_algo([2,1,3,9,4])
sort_algo([20,1,13,50,4])

```

# Answer
Unfortunately, this has no name—because it doesn't work. Pontus provided a good test case.

```
lst = [2, 1, 3, 4, 5]
sort_algo(lst)
print(lst)

```

> \[2, 1, 3, 4, 5\]

It's been mathematically proven that comparison-based sorting algorithms (that is, sorting algorithms based on comparing elements against each other, rather than exploiting certain clever tricks) can **never** do better than $O(n \log n)$ time. Even if you use the clever tricks, you can't do better than $O(wn)$ time, where $w$ is related to the size of the values. (For radix sort, the classic "exploiting clever tricks" algorithm, $w$ is a constant which must be larger than the log of the largest element in the data set.)

---

EDIT: Your change to the algorithm makes it work on that test case, so here's a new one to break it.

> \[6, 5, 4, 3, 2, 1\] → \[3, 2, 1, 5, 4, 6\]
> 4 votes

---
Tags: algorithms, python
---


# Question
Title: Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q*r-s/(q*r)$
I found a question.

> Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q\*r-s/(q\*r)$

**My attempt**:

> $t\_1 = q\*r$
> $t\_2 = s/t\_1$
> $t\_3 = p + t\_1$
> $t\_4 = t\_3 - t\_2$

So, I got $4$ variables but their answer is $5$. Am I missing something? Where I am being wrong?

# Answer
You used the optimisation of calculating q * r only once. Maybe someone considered that "cheating" and is insisting that it must be calculated twice. I wouldn't agree with that at all, but it would explain the different answers.
> 2 votes

---
Tags: compilers
---


# Question
Title: Is there a generally accepted name for creating types that select a subset of other types?
**Tl;Dr;**

Given:

```
type A = { int: foo, int: bar }
type B = select foo from A

```
* What is the name of the typing relationship between A and B?
* What is the name of the operation of deriving type B from type A?

---

## Long Version

When we talk of subtyping in programming we typically think of it in terms of whether a new subtype B of a type A is able to substitute for A. However, when you think of it in terms of implementation what you are actually saying is that B can do everything that A can. Typically B does more. It might implement the interface and add new fields and methods of its own. So despite 'sub' sounding like 'subset' the relationship is more like the subtype enriching the supertype. We derive the subtype from the supertype. I'm curious about deriving a new type by selecting a subset instead.

Consider two structures:

```
A = { int: foo, int: bar }
B = { int: foo }

```

The fields of B are a subset of the fields of A.

Is there a proper name for this relationship? I would say **A includes B**.

You could implement A by embedding an instance of B. As in:

```
C = { B, int: bar }

```

In a language like Go, C is the same as A. In other languages you need to reference B to get to foo. i.e. *C.B.foo* rather than *C.foo*

Another kind of subset relation is subranging. For instance limiting a integer to a range of 0-10.

```
Q = int
P = int[0..10]

```

P is a subset of Q as before. You can still say Q includes P. subranges are a special case of refinement types.

The main language I can think of where creating subsets is central is SQL. We could define B as:

```
B = select foo from A

```

So selection is probably a better term to use than "sub-setting"? B is not a subtype of A is it cannot be used as a substitute for A. A is a subtype of B because it can be. So B is a supertype of A. I think this misses the essential distinction that we are deriving B from A rather than the other way around. i.e. the process has a direction:

```
B = f(A) , where f = selection and B is a supertype of A

```

vs

```
subtype = g(supertype), where g is derivation/inheritance.

```

We also have intersection types which combine two types by producing the subset they have in common. SQL does this with joins. Unification in prolog has a similar effect. Selection is via intersection with a second type. You could view selecting the fields as constructing a set of selectors and which is then intersected with the original set. I'm not sure this is the correct way to look at it though. selection and intersection are not the same. An intersection ignores fields that are not common a selection operation should treat that as an error.

There is also destructuring (assignment) as in:

```
let x = { 10, 1 }
{y, z} = x

```

But this has to do with values more than types and the isomorphism between a structure and a generic tuple.

My question is:

* Is there a generally accepted name for this kind of 'selection'?
* What would you call a type system supporting this kind of relationship?

Bonus discussion questions:

* Why is 'selection' not more common in general purpose programming languages as opposed to query languages? Surely they complement each other well?
* Are there any interesting languages supporting this? How successful is the feature? (linq is very successful in C# for example)

# Answer
First, the field-subset model of subtyping, while uncommon in OO languages, is common in PL theory for modelling subtyping. It's often called **row subtyping**.

I'm not sure if there's a *general* name for all the other things you've described, but I think the closest fit is **refinement types**, which come in many flavours.

* Liquid types refine types by a boolean predicate, i.e. you can make a type which contains all values from another type satisfying a certain predicate. For example, you could have $\\{ i : Int \mid 0 \< i \< 10 \\}$ as a refinement of $Int$.
* Datasort Refinements are similar to liquid types, but they constrain a type by the *shape* of its values. So, you can refine $(List\ Int)$ to $ T = Cons(Int, Cons(Int, List))$, and $T$ is then the type of all $Int$-containing lists of length 2 or more.

More generally, Set-theoretic types describe a system where can form types using intersection, union, and negation operations on existing types. Here, there *is* a close correspondence between subtyping and the subset-relationship between values in a type.

A general comment is that I think you need to be careful distinguishing *terms* from *types*. While you're describing sensible operations on types, the SQL example and the Prolog unification example are both operations on *terms*, and not on types, so they're really something different from what you're describing.

I don't think destructuring assingment has anything to do with the other things, it's just a shorthand for pattern-matching, either where there's only one case, or where we throw an error in all but one case.

### Bonus Discussion

Why is this not common? Type-checking is performed often, and adding too many features makes it undecidable. The refinement-types I listed above depend on SMT-solvers for typechecking, since they require solving logical constraints.

Are there langauges that support these? The main ones I can think of are Liquid Haskell and Dependent ML. I'm not sure how often they show up in an object-oriented context, because these are areas under active research, and functional languages are generally faster to incorporate bleeding-edge ideas from PL research.
> 1 votes

---
Tags: programming-languages, type-theory
---


# Question
Title: Why hasn't functional programming researched dynamic trees?
Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging dictionaries ("A Simple Mergeable Dictionary" by Adam Karczmarz),

By dynamic trees I refer to the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Few efforts have been published within the functional programming research area since.

1. Edward Kmett implemented a version of the ST trees mostly as a translation of the C++ counterpart, see Link-cut trees.
2. Chris Okasaki wrote a limited implementation of the Splay trees in his renowned book "Purely functional data structures".
3. Ralf Hinze and Ross Paterson introduced a functional data structure called 2-3 finger trees but with somewhat different aim from that of original definition of dynamic trees.

Implementation (and perhaps performance) of dynamic trees are divided according to three approaches:

1. Linearization, where ET trees (Euler tour) play a great role. Not found a purely functional study.
2. Path-decomposition, where ST trees are the flagship, just found the Kmett's version.
3. Tree contraction, where Top trees, topology trees and RC trees are the players. Not found a purely functional study.

Purely functional analysis and implementation can be found on Splay, AVL, red-black tree, but those are NOT dynamic trees. The former are considered the shadow (also called virtual or auxiliary) data structure of the latter.

So, my question is:

What are the reasons (drawbacks, weaknesses) for the Functional Programming research community not to take part into the dynamic trees data structure?

# Answer
"In computer science, functional programming is a programming paradigm. A style of building the structure and elements of computer programs that treats computation as the evaluation of mathematical functions and avoids changing state and mutable data." - Wikipedia

"changing state and mutable data" in other words "dynamic".

So your question is a bit like asking why left isn't right.
> -1 votes

---
Tags: data-structures, trees, functional-programming
---


# Question
Title: Minimal set of subintervals that 'covers' any subinterval in K subintervals
I have a big interval $I = \[a, b\]$ of size n.

I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most $K$ subintervals - specifficaly I'm interested in $K = 3, K=5$ only, but general solution would be interesting too.

In other words, for any subinterval $i$ of $I$ I want to take at most $K$ (3, 5) elements of $S$ to get $i$. So if $i = \[2, 28\]$, one can take for example $\[2, 10\], \[10, 20\], \[20, 28\]$, if such subintervals exists in $S$ and $K=3$.

I've come up with solutions that are in $O(n^2)$ where $n = |I|$, but that is the same as naive approach of taking all the subintervals. I can get to about $1/K$ of that by having intervals of size $m$ to generate also the $K$ bigger intervals, but it seems it is in the spirit of the puzzle to have asymptotically better solution than $O(n^2)$, at least for $K=5$.

# Answer
Let's consider the case $K = 2$. Given an interval $\[1,n\]$ of length $n$, we can construct the required set as follows:

* If $n = 1$, take the entire interval.
* Otherwise, let $m = \lfloor n/2 \rfloor$, and take the following intervals:
    1. A solution for $\[1,m\]$.
    2. A solution for $\[m+1,n\]$.
    3. All intervals of the form $\[i,m\]$.
    4. All intervals of the form $\[m,j\]$.

Denoting by $A(n)$ the number of intervals constructed in this way, we get the recurrence $$ A(n) = A(\lfloor n/2 \rfloor) + A(\lceil n/2 \rceil) + n, $$ with initial value $A(1) = 1$. The solution of this recurrence is $A(n) = \Theta(n\log n)$.

Now let us proceed to prove a matching lower bound. Let $\ell\_i = 2^i-1$, and let $I$ be the maximum value such that $\ell\_i \leq n/2$; note that $I = \Theta(\log n)$. For each $1 \leq i \leq I$, consider the $n/2$ intervals $\[1,\ell\_i\],\ldots,\[n/2,n/2+\ell\_i-1\]$ of length $\ell\_i$. Each of these is the union of at most two intervals in $S$, one touching the left endpoint and one the right endpoint (possibly the same one). One of these intervals must have size at least $2^{i-1} \> \ell\_{i-1}$. In total, this gives a collection of $n/2$ intervals in $S$ of length between $\ell\_{i-1}+1$ and $\ell\_i$; each such interval is repeated at most twice (since one of its endpoints is a matching endpoint of one of the original $n/2$ intervals). This shows that $S$ must contain at least $n/4$ intervals of size between $\ell\_{i-1}+1$ and $\ell\_i$, and so $\Omega(nI) = \Omega(n\log n)$ overall.

---

Here is a better construction for $K=4$. Divide the interval $\[1,n\]$ into $m=n/\log n$ subintervals $I\_1,\ldots,I\_m$ of length $\log n$. We construct the required set as follows:

* Apply the construction recursively inside each $I\_i$.
* Every prefix and suffix of each $I\_i$, $2n$ intervals in total.
* The $K=2$ construction applied to $\[1,m\]$ and then blown up to $I\_1,\ldots,I\_m$ by replacing each interval $\[i,j\]$ to $I\_i,\ldots,I\_j$.

Let us first show that we can cover each interval $I$ using at most 4 intervals in the set. If $I \subseteq I\_i$ for some $i$, then this is clear. Otherwise, suppose that $I \subseteq I\_i \cup \cdots \cup I\_j$, where $i$ is maximal and $j$ is minimal. So $I$ consists of a suffix of $I\_i$, all the intervals $I\_{i+1},\ldots,I\_{j-1}$ (if any), and a prefix of $I\_j$. We can cover the middle part using 2 intervals, and the two ends using 2 more intervals, for a total of 4.

Let us denote by $B(n)$ the number of intervals used in this construction. This quantity satisfies the recurrence $$ B(n) = \frac{n}{\log n} B(\log n) + O(n). $$ Opening this up, we get $$ B(n) = O(n) + \frac{n}{\log n} O(\log n) + \frac{n}{\log n} \frac{\log n}{\log \log n} O(\log \log n) + \cdots, $$ where the hidden constant is the same for all big O’s. The number of summands is $\log^\* n$ (which is the number of $\log$s you have to apply to $n$ to reduce it below some constant), and so $$ B(n) = O(n\log^\* n). $$ We can repeat this construction once again, for $K=6$, to get the inverse of one level higher on the Ackermann hierarchy. Perhaps in this way we can get a set of $O(n)$ intervals for $K=\omega(1)$ growing extremely slowly (inverse Ackermann); verifying this would require a slightly more careful analysis.
> 1 votes

---
Tags: sets, intervals
---


title: Time Complexity and graphs

text:
# Question
Title: Time Complexity and graphs
I'm learning graphs these days and need to clear few doubts-

1. Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1).
2. What is the efficient way to find out the degree of the specified vertex in an undirected graph (V,E)? I'm thinking of O(|E|)?
3. What is the efficient way to find degrees of all vertices in an undirected graph (V,E)? I'm think of O(|V||E|)
4. if |E| ≥ |V| can I say grapgh will be have guaranteed Euler circuit?
5. Is it possible to find slope of a straight line in O(1)time given the X and Y coordinates of n points on the line?

# Answer
1. Yes, anything that has constant input could be done in $O(1)$. Howether if the coordinates have size more than $O(1)$ than you will not be able to even read them in time.
2. That depends on your representation of the graph and what operations do you count. If you assume that you read the whole graph in some way and then find the needed degree, the complexity will be $O(|V| + |E|)$ if your representation is an edge list, $O(|V|^2)$ if it is an adjacency matrix. If you assume that you already have some representation of the graph in memory you can find the degree in $O(|V|)$ if you have the adjacency matrix.
3. You can do it in $O(|V| + |E|)$, start with an empty graph (all the degrees are zero) and add the edges one by one. When you add an edge to the graph only two vertices change their degrees.
4. No, consider the graph $K\_4$ (complete graph on $4$ vertices). All the degrees in it are odd so it does not have even en Euler path.
5. If you want to read the coordinates it takes $O(n)$ operations, so no.
> 3 votes

# Answer
Just adding to what @Artur said: You only need 2 points to find the slope of a straight line, even if you're given more, so that's `O(1)` for me...
> 0 votes

---
Tags: algorithms, graphs, time-complexity, eulerian-paths
---