# Question
Title: How to find efficiently the minimum modification to avoid close consecutive numbers?
I have an array of sorted numbers:

```
arr = [-0.1, 0.0, 0.5, 0.8, 1.2]

```

I want the difference (`dist` below) between consecutive numbers for that array to be above or equal a given threshold. For example, if threshold is 0.25:

```
dist = [0.1, 0.5, 0.3, 0.4] # must be >=0.25 for all elements

```

`arr[0]` and `arr[1]` are too close to each other, so one of them must be modified. In this case the desired array would be:

```
valid_array = [-0.25, 0.0, 0.5, 0.8, 1.2] # all elements distance >= threshold

```

In order to obtain `valid_array`, I want to modify the **minimum amount of elements** in `arr`. So I substract 0.15 from `arr[0]` rather than, say, substract 0.1 from `arr[0]` and add 0.05 to `arr[1]`:

```
[-0.2, 0.05, 0.5, 0.8, 1.2]

```

Previous array is also valid, but we have modified 2 elements rather than one. In order to obtain `valid_array`, I already have a brute force solution which works fine, but it is quite slow for large arrays. My questions are:

What is the time complexity of that brute force solution?

Does a more efficient algorithm even exist?

# Edit

First, I need to clarify what I mean by difference, which I define the same way as in here, so `out[n] = a[n+1] - a[n]`. The fact that all elements in that difference must be above (or equal) threshold implies that `valid_array` is also sorted.

Second, the number of modifications (which must be minimized) is obtained by comparing elementwise the original `arr` and `valid_array`

# Answer
Here is an algorithm that returns the minimum amount of elements that need to be modified. It is about as simple as possible and as fast as possible. Its time complexity is $O(n)$, where $n$ is the size of input array.

```
def minimize(arr, threshold):
    size = len(arr)

    # keep[i] or modify[i] is the minimal number of modification
    # needed on arr[0:(i+1)], keeping or modifying the i-th
    # element respectively, so that any two consecutive numbers
    # in arr[0:(i+1)] are greater than `threshold` apart.
    keep = [0] * size
    modify = [0] * size

    for i in range(1, size):
        modify[i] = min(keep[i - 1], modify[i - 1]) + 1

        if abs(arr[i] - arr[i - 1]) >= threshold:
            keep[i] = min(keep[i - 1], modify[i - 1])
        else:
            keep[i] = modify[i - 1]

    return min(keep[-1], modify[-1])

```

The criticall observation is that if a number at a certain index has been modified, we can consider it has been modified so wildly it will be more than `threshold` away from any of its neighbours, whether those neighbours will be modified or not.
> 1 votes

---
Tags: algorithms, runtime-analysis, dynamic-programming, arrays
---


# Question
Title: Representing chained XOR operations as linear inequalities
I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met:

$x\_1 \oplus x\_2 \oplus \cdots \oplus x\_n = 1$

where $\oplus$ is the binary *xor* operator.

The answer to this question shows how to represent $y = x\_1 \oplus x\_2$ with linear inequalities. In an answer to this question there is an attempt to generalize the representation to more than two inputs, but the two answers seem to be inconsistent, since the latter doesn't even use inequalities.

So, the question is: how can I represent $y = x\_1 \oplus x\_2 \oplus \cdots \oplus x\_n$ as set of linear inequalities?

# Answer
Introducing another integer variable $t$, you can express the condition $x\_1 \oplus x\_2 \oplus \cdots \oplus x\_n = 1$ as in the following canonical form. $$x\_1 + x\_2 + \dots + x\_n - 2t \le 1$$ $$- x\_1 - x\_2 - \dots - x\_n + 2t \le -1$$ $$(x\_1, x\_2, \cdots, x\_n) \le (1,1,\cdots,1)$$ $$(x\_1, x\_2, \cdots, x\_n, t) \ge \mathbf 0$$ $$(x\_1, x\_2, \cdots, x\_n, t) \in \Bbb Z^{n+1}$$ You can also replace the first two inequalities by the following equality. $$x\_1 + x\_2 + \dots + x\_n - 2t = 1$$ In other words, you can actually eliminate one of $x\_1, x\_2, \cdots, x\_n$ by replacing it with $t$.

Note $t$ is an integer not bounded from above. However, you can also bounded it by the following inequality, which is implied by the existing inequalities.

$$0\le t\le \lceil \frac{n}2\rceil-1$$

---

The idea is that $x\_1 \oplus x\_2 \oplus \cdots \oplus x\_n = 1$ if and only if the number of $x\_i$'s that are 1 is odd. This answer is essentially the same as the answer you mentioned.
> 1 votes

---
Tags: boolean-algebra, linear-algebra, integer-programming, xor
---


title: Are non-regular languages decidable?

text:
# Question
Title: Are non-regular languages decidable?
Given a language L, I've shown that L is not regular. Can I conclude that it is not decidable or are there non-regular languages that are decidable?

# Answer
> 4 votes
Context-free languages are not regular but decidable; on the other hand recursively enumerable languages are not regular and only semi-decidable. So sadly only knowing about the non-regularity of a language does not help with determining its decidability.

---
Tags: computability
---


# Question
Title: Efficient way to find matching date ranges?
We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate set of 1000 of these. But a linear search is exponentially expensive.

So is there an algorithm that is more efficient? (For data related to a single date, using the date as the key of a hashmap works, but not much help when there is a pair of dates.)

(The source of the problem is my commercial work where there are a large number of date ranged payments that need to be matched with another large set of date ranged payments. And the environment the code runs in applies hard limits to how much CPU time can be consumed.)

# Answer
> 2 votes
Your question is not clear.

I am assuming you have 1000 date intervals in some set $A$ and another 1000 in set $B$ and you wish to find which intervals in $B$ lie completely inside some interval in $A$.

For an interval \[x,y\] in $B$, search points $x$ and $y$ in the segment tree built on $A$ and find sets that overlap.

Look up Segment tree.

Its stores line segments with starting point and end point. You can modify it to store start date and end date.

https://en.wikipedia.org/wiki/Segment\_tree

# Answer
> 1 votes
Following VK1's link reveals a further link to:

https://en.wikipedia.org/wiki/Interval\_tree

that seems like a better match to the problem as the date ranges are not consecutive so there are gaps. A quick Google reveals and implementation too:

https://github.com/charcuterie/interval-tree/blob/master/src/datastructures/IntervalTree.java

---
Tags: search-algorithms, search-trees, search-problem
---


title: Minimum finger search tree complexity

text:
# Question
Title: Minimum finger search tree complexity
Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $k$-smallest key in the entire tree. I can do this by "climbing" up the tree's left branch, comparing x with the current key. As long as

> (x \> curr.key) && (x \> curr.parent.key)

I keep climbing up, but once the second condition is violated, I slide down to the current right-subtree, and from there on it's just a standard BST search.

The claim is that the **worst case** complexity is always $O(\log k)$, for any $k$. But I can't convince myself this is accurate: if x is larger than the tree's root's key (the median, or equivalently $k \> {n\over 2}$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ \- and only then I can find x in depth of $O(\log k)$.

Am I looking at this the wrong way?

# Answer
Yes, you might be looking it the wrong way.

> If $x$ is larger than the tree's root's key (the median, or equivalently $k\>n/2$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ \- and only then I can find $x$ in depth of $O(\log k)$.

First, let us be accurate. The root's key may not be the median, although it sits roughly in the middle.

Let $r$ be the root node. Let $n$ be the number of nodes in the whole tree and $n\_l$ be the number of nodes in the left subtree of $r$. Let $h\_l$ be the height of that subtree and $h$ be the height of the tree, so $h\le h\_l+2$ since an AVL tree is height balanced.

Suppose $x$ is larger than the root's key. That means $$n\_l \< k \le n.$$ We also have, according to the properties of an AVL tree. $$\log\_2 (n+1)\le h \le h\_l+2 \le c\log\_2(n\_l+2)+b +2\lt c\log\_2(k+2)+b +2$$ where $c\approx 1.44$, $b\approx -0.328$. So, for all $k\ge3$, $$\log\_2(n)\le2\log\_2(k)$$

So if you have traversed the entire (height) of the left branch in order find the $k$-th smallest element, you will use $O(\log n) = O(\log k)$ steps.

In fact, if we only look at the subtree whose root is the highest node that we will climb to in search of the $k$-th smallest element, we have just proved that the worst case complexity is always $O(\log k)$
> 0 votes

---
Tags: time-complexity, balanced-search-trees
---


# Question
Title: Avoiding overflow in computing the ratio of two large numbers
Is there a trick for computing the expression $x + (exp(x)-x)/(exp(2\*x) + 1)$ while avoiding an overflow? Currently, computation seems to fail for any $x \geq 710$, presumably because computing $exp(2\*x)$ leads to an overflow. The expression as such never produces particularly large numbers, but exponentiation seems to cause problems.

I'm working in R, but the same problem occurs in C++ as well.

If there is no trick for computing it, I'd be just as happy using another non-negative monotonic function which is nearly linear for $x \> 10$.

# Answer
> 3 votes
Yes, when $x\ge355$, computing $e^{2x}$ as a double-precision float in IEEE 754-1985 standard, leads to an overflow.

$$x + \frac{e^x-x}{e^{2x} + 1}= x + e^{-x} - \frac{x+e^{-x}}{e^{2x} + 1}\approx x+ e^{-x}$$

The difference between the two sides of the approximate sign is smaller than the minimal positive number in IEEE 754-1985 standard, $2^{−1022} \approx 2.225×10^{−308}$, when $x\>367.2$.

So, once $x\>367.2$, you can just use $x+e^{-x}$ instead.

---
Tags: numerical-analysis
---


# Question
Title: Can repeated runs of a Las Vegas algorithm equate to a better Las Vegas algorithm?
Let's say I have a Las Vegas algorithm $L$ for some problem $P$, which runs in $n^3$ steps with 50% likelihood. My friend asks me for an algorithm for $P$ that runs in $n^3$ steps with 75% likelihood. My intuition says, "No problem! I'll just run $L$ once, and if it doesn't return after $n^3$ steps, I'll terminate it. Then, I'll run it again. The likelihood that it fails to return after $n^3$ steps twice in a row is only 25%."

Is my intuition correct? I know that if it's running twice, that's technically $2n^3$ and that would be subsumed by big-O notation. Maybe the problem that was posed to me was not carefully worded enough...

# Answer
Monte Carlo and Las Vegas algorithms are equivalent and this question is more naturally asked in terms of the former so I will pretend you asked about Monte Carlo.

Any Monte Carlo algorithm can be run multiple (say, a constant number of) times to amplify the probability of success while slowing down the algorithm. And in fact you can achieve any fixed probability of success $\< 1$ while slowing down by a constant factor.

Where you "cheat" is that you adopt the convention of ignoring the constant factor in run time while simultaneously caring about the constant probability of success. As the probability can be freely adjusted by multiplying run time by a constant, caring about its particular value is equivalent to caring about the constant factor in run time so big O is inappropriate in this situation.
> 1 votes

# Answer
Depends on what you mean by “better”. There is always a compromise between cost and the quality of the results. Accepting higher cost for higher quality does not make it a better algorithm in my book.

I would say that a “better” algorithm is one that produces equal quality at lower cost, or better quality at the same cost.
> 0 votes

---
Tags: algorithms, randomized-algorithms
---


# Question
Title: Language that fulfills pumping lemma but is not in RE
I am supposed to find a language $$L\subseteq \Sigma ^\*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given constraint, I've only shown that a certain language satisfies a given one. Not wanting to waste a bunch of time guessing some languages and prooving that they meet my criteria, I am looking for a hint on how to start.

# Answer
> 4 votes
## Usual pumping lemma

Here is an answer when we are talking about the usual pumping lemma for regular languages that is taught in most introductory courses of computation theory.

Let alphabet $\Sigma=\\{0,1\\}$. Let $L$ be a non-recursively enumerable language over $\Sigma$. For example, $L$ can be the complement language of a semi-decidable but not decidable language such as $\overline{\\{ \langle M \rangle \mid \text{ $M$ halt on empty input}\\}}.$

Let $L'=\\{00w\mid w\in L\\}\cup\\{01w\mid w\not\in L\\} $. Then both $L'$ and $\overline {L'}$ are non-recursively enumerable languages.

Let $F=\\{ 1w \mid w\in L' \\} \cup \\{ 1^kw \mid k\neq 1, w\in \Sigma^\* \\}$, following the construction in an answer by Hendrik Jan. Then $F$ is not in RE and not in coRE since its first part is not in RE and not in coRE while its second part is regular. It satisfies the usual pumping lemma for regular languages, since its second part is regular while its first part can be pumped down and up "into" its second part by choosing the first 1 to pump.

## General pumping lemma

Here is an answer when we are talking about the general (or generalized) pumping lemma for regular languages.

Let alphabet $\Sigma\_4=\\{0,1,2,3\\}$. Let $D$ be the finite language whose words are of length 3 and having a duplicate character. (In fact, $D$ has $4+4\times3\times3=40$ words.) Let $P=\Sigma\_4^\*\bullet D\bullet\Sigma\_4^\*$, the languages of all words that contain a substring in $D$. $P$ is a regular language. Any language over $\Sigma\_4$ that contains $P$ satisfies the general pumping lemma.

Let $N$ be a language that is not in RE and not in coRE. For example, we can select language $L'$ constructed in previous section. Then $G=P\cup N$ is a language not in RE and not in coRE that satisfies the general pumping lemma.

---

Here are several exercises that readers can do so as to fill the gaps in the above sections.

Exercise 1. Show the class of non-recursively enumerable languages is closed under concatenation with a fixed string at the front.

Exercise 2. Show the class of non-recursively enumerable languages is closed under union with a regular language.

Exercise 3. Show any language over $\Sigma\_4$ that contains $P$ satisfies the general pumping lemma.

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


# Question
Title: Variant of interval scheduling (multiple machines with given availability)
I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks cannot be performed at the same time by the same machine. I am trying to maximize the number of scheduled tasks.

More formally, we are given $m$ intervals $\[B\_i, E\_i\]$ (the machines) and $t$ tasks $\[b\_i, e\_i\]$. We must output $m$ lists $\[i\_1, i\_2, ..., i\_{k\_j}\]$ such that for each $1 \leq j \leq m$, $B\_j \leq b\_{i\_1} \leq e\_{i\_1} \leq b\_{i\_2} \leq ... \leq e\_{i\_{k\_j}} \leq E\_j$, all the elements of the lists are distinct and $\sum\_{j = 1}^m k\_j$ is maximal (ideally t).

I thought about the greedy algorithm consisting on scheduling first the task that finishes the earliest, on the compatible machine whose last task finishes the latest (we consider every machine has at first a task finishing at the beginning of its working interval). However, this idea doesn't work, how we can see considering the instance of the problem where we have two machines, working on the intervals (0, 3) and (1, 4), with the tasks (1, 3) and (2, 4).
This way of selecting the machine on which we schedule the task is however not so stupid, and prevents other problems (the algorithm works if we are allowed to exchange the end of the working interval of the machines).

Is there a fast algorithm to solve this or is it a hard problem ?

# Answer
Let us call $n$ the number of intervals and $m$ the number of available machines.

There is an algorithm by Brucker and Nordmann running in time essentially $O(n^{m-1})$. Thus for any constant $m$, the problem admits a polynomial time algorithm. The authors claim that the algorithm is practical up to $m=5$ machines.

When $m$ is not constant, the problem appears to be hard, however I do not know whether the version you stated is NP-hard. In this case, Faigle, Kern and Nawijn show that by a simple greedy algorithm you can schedule at least *half* of the intervals scheduled in an optimal solution. This is the overview of their algorithm, that they call $G$ (the jobs are denoted by $I\_1,I\_2,\ldots,I\_n$, and are considered ordered by their left endpoints):

> $G$ places $I\_t$ on a free feasible machine if such a machine is available. Otherwise $G$ tries to replace a job $I\_v$ by $I\_t$ on a feasible machine with the goal to reduce the maximal remaining processing time. If neither action is possible, $G$ discards $I\_t$.
> 1 votes

---
Tags: algorithms, combinatorics, scheduling
---


title: np-complete proof, turing reduction

text:
# Question
Title: np-complete proof, turing reduction
I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know :

* A-\> B
* A-\> C
* C -\> B

A-\> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for B. I know that A belongs to NP, B and C are NP-complete. Moreover I can write an algorithm for A with a quadratic number of calls to C. can I deduce something about the complexity of A?

# Answer
> 2 votes
You know that:

1. A belongs to NP
2. B is NP-Complete
3. C is NP-Complete
4. If A accepts given word then B accepts this word as well
5. If we can solve C - we can solve A.

To prove that A is NP-Complete you need to prove that it belongs to NP (which is given to us) and that any problem from NP can be reduced to it (so that it is NP-Hard). To show the second one you need to show a reduction from an NP-Complete problem to A.

The last (5th) of our information basically means you have a polynomial reduction from A to C which is no surprise, since A is in NP and C is NP-Complete (meaning, among others, that every NP problem can be reduced to it, including A). This doesn't give you much about A (it only confirms that A is no harder than C).

The 4th information gives us knowledge like this: if some word belongs to A it also belongs to B, but there are some possible words that belong to B but not to A. In other words, A is a subset of B. This does not gives us much about A either, because A could belong to P only and still be a subset of B (as NP "contains" P).

In my opinion, if I understood this well, this information is not sufficient to say more about the complexity of A.

# Answer
> 1 votes
Let A = "Answer NO for everything", and all condition satisfy. Therefore we know nothing more about A

---
Tags: complexity-theory, np-complete, reductions, turing-completeness
---


title: Parallel Algorithm for Data Averaging

text:
# Question
Title: Parallel Algorithm for Data Averaging
I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all V1, V2 and V3 present in the list with K.

If anyone can think of something it would be much appreciated.

Thanks, Harris Mirza

# Answer
> 1 votes
The role of three values $V\_1, V\_2$ and $V\_3$ isn't clear for me, but anyway:

* Step 1. Sort the original list **in parallel** by key $K$ \- you'll get a list of records $(K, V\_1, V\_2, V\_2)$, where all the records with the same key are stored together in "buckets".
* Step 2. Process each bucket concurrently, calculating all the averages.

There are many parallel sorting algorithms, you can choose one depending on your computational model.

---
Tags: algorithms, parallel-computing, lists, dictionaries
---


# Question
Title: Do these answers work even when we change the values?
So I know that these are both true, but if I change the values would they still be true? Do these statements hold for any value?

A) Suppose f is a flow of value 50 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 50.

Suppose we were using 100 or maybe 75 instead of 50. Is this still true?

B) Suppose f is a flow of value 100 from s to t in a flow network G and there is an s-t cut of capacity 100. Then there are no s --\> t paths in the residual graph Gf.

If we use 80, 60, 20 and so on is this still true? What about for odd numbers?

# Answer
> 0 votes
The value of any $st$-flow is at most the value of any $st$-cut, and they are equal if and only if the flow value is maximized and the cut value is minimized. Thus, statement (A) is false since $f$ isn't necessarily a maximum flow (since you claim (A) is true, maybe you forgot to mention that $f$ is a maximum flow, or you meant to say that the value of the cut is *at least* 50?). Statement (B) is true, since if there is a flow and cut of equal value, then the flow is a maximum flow and the residual graph has no path from $s$ to $t$.

Of course, the actual values don't matter. Only the relationship between the flow value and cut value is relevant.

---
Tags: graphs, network-flow
---


# Question
Title: Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification
I provided my answers in the "answer your own question" bit.

I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though?

---

a) Suppose f is a flow of value 50 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 50.

b) Suppose f is a flow of value 100 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 100.

---

c) Suppose f is a flow of value 20 from s to t in a flow network G and there is an s-t cut of capacity 20. Then there are no s --\> t paths in the residual graph Gf.

d)Suppose f is a flow of value 100 from s to t in a flow network G and there is an s-t cut of capacity 100. Then there are no s --\> t paths in the residual graph Gf.

---

e) Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the total capacity leaving the source s.

f) Let G be a directed graph with n nodes and edge weights that might be negative, but no negative cycles. The shortest path from node s to node t has at most n-1 edges.

I think this is true. I know that there is no negative cycle, so the shortest path will not have any loop. But I'm not really sure how I know this...like how did we logic that out

g) P!=NP True. This is just a fact. But worth noting it has neither been proved nor disproved?

# Answer
## Condensed A/B and C/D into two general t/f statments with explanations:

A/ B Suppose f is a flow of some value X from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to X.

## This is FALSE. HOWEVER, if the flow were maximum, then the amount of max-flow is equal to size of min-cut making it TRUE

C/D Suppose f is a flow of some value X from s to t in a flow network G and there is an s-t cut of capacity X. Then there are no s --\> t paths in the residual graph Gf.

## TRUE. Once the max-flow is computed then there is not path from s to t in the residual graph.

e) Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the total capacity leaving the source s.

## TRUE because FF algorithm estimates every possible path from s to t and since every path from s to t will have minimum capacity of 2, FF will take half amount of iteration i.e. C/2 iteration to compute result.

f) Let G be a directed graph with n nodes and edge weights that might be negative, but no negative cycles. The shortest path from node s to node t has at most n-1 edges.

## TRUE

g) P!=NP

TRUE(?)
> 0 votes

---
Tags: graphs, shortest-path, network-flow, weighted-graphs, minimum-cuts
---


# Question
Title: How to count stores in cache analysis of matrix multiplication
I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out.

For **ijk** iteration, my slides say that there are 2 loads and 0 stores.

```
for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
   sum = 0.0;
   for (k=0; k<n; k++)
     sum += a[i][k] * b[k][j];
   c[i][j] = sum;
  }
}

```

Similarly, for **kij** iteration, my slides say that there are 2 loads and 1 store.

```
for (k=0; k<n; k++) {
 for (i=0; i<n; i++) {
  r = a[i][k];
  for (j=0; j<n; j++)
   c[i][j] += r * b[k][j];
 }
}

```

And for **jki** iteration, my slides say that there are 2 loads and 1 store.

```
for (j=0; j<n; j++) {
 for (k=0; k<n; k++) {
   r = b[k][j];
   for (i=0; i<n; i++)
    c[i][j] += a[i][k] * r;
 }
}

```

I believe the loads are counted in each case when data is referred to by calling arr\[x\]\[x\] on the right hand side of the arithmetic evaluation, which would make two in each case. But how are the stores counted?

# Answer
> 1 votes
It appears that the analysis assumes that integer variables are stored in registers, whereas array elements have to be loaded from and stored to memory. The point you've missed is that the statemnt `X += Y` requires reading `X` and then writing the new value of `X`.

```
sum += a[i][k] * b[k][j];

```

This **load**s `a[i][k]`, **load**s `b[k][j]`, multiplies them, reads `sum`, adds `sum` and the product and writes the result to `sum`. Two loads, no stores.

```
c[i][j] += r * b[k][j];

```

This **load**s `b[k][j]`, reads `r`, multiplies them, **load**s `c[i][j]`, adds the product to it and **store**s the new value of `c[i][j]`. Two loads, one store.

```
c[i][j] += a[i][k] * r;

```

This is essentially the same as the previous case.

---
Tags: computer-architecture, arrays, cpu-cache, matrix
---


# Question
Title: Determining properties of linear code from generator matrix
I have a problem in error-correcting codes.

Say we have a generator matrix of a linear binary code

$$g=\begin{pmatrix} 10011 \\ 01101 \end{pmatrix} $$

> Q1: How many different codeword do we have? How many code bits can the code correct?

Say the generator matrix of a $(6,2)$ binary code is $$g=\begin{pmatrix} 101001\\ 011111 \end{pmatrix}$$

> Q2: How many errors can it guarantee to detect?

My try:

For Q1:

The way I find the number of codeword is count the number of rows in $g$ and raise it as a power to 2. So the answer is $2^2=4$.

For detecting and correcting I’m not sure, should I find the hamming distance and subtract 1?

I hope someone can explain to me how I can find the number bits I can detect and correct.

# Answer
If the minimal distance is $d$, then

* Up to $d-1$ errors can be detected. This means that if a sent codeword is modified by flipping at least one and up to $d-1$ bits, then the receiver can tell that some bits were flipped.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping at least one and up to $d-1$ bits. Since $1 \leq d\_H(w,w') \< d$ (where $d\_H$ is Hamming distance), we see that $w'$ is not a codeword (since the distance between any two different codewords is always at least $d$), and so we can detect that errors have occurred.

* Up to $\lfloor \frac{d-1}{2} \rfloor$ can be corrected. This means that if a sent codeword is modified by flipping at most $\lfloor \frac{d-1}{2} \rfloor$ bits, then the original codeword can be recovered.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping up to $\lfloor \frac{d-1}{2} \rfloor$ bits. I claim that $w$ is the *unique* codeword at distance at most $\lfloor \frac{d-1}{2} \rfloor$ from $w'$. Indeed, if $z$ were another such codeword then $$ d\_H(w,z) \leq d\_H(w,w') + d\_H(w',z) \leq 2 \lfloor \tfrac{d-1}{2} \rfloor \< d, $$ contrary to the definition of minimal distance.
> 0 votes

---
Tags: error-correcting-codes
---


# Question
Title: Does this algorithm correctly compute the chromatic number of a graph?
```
int ChromaticNumber(Graph G)
{
    for (int i = 0; i < G.Vertices.size(); ++i)
    {
        //initialize vertex color to 1
        ++G.Vertices[i].Color;
        bool Match = true;

        //loop while there is an adjacent vertex with the same color
        while (Match)
        {
            Match = false;
            for (int j = 0; j < G.Vertices[i].Edges.size(); ++j)
            {
                //get adjacent vertex
                int AdjacentVertex = G.Vertices[i].Edges[j];

                //if an adjacent vertex has the same color, increment the
                //current vertex's color
                if (G.Vertices[i].Color == G.Vertices[AdjacentVertex].Color)
                {
                    ++G.Vertices[i].Color;
                    Match = true;
                }
            }
        }
    }

    int MaxColor = 0;

    //loop to determine the largest color value
    for (int i = 0; i < G.Vertices.size(); ++i)
        if (G.Vertices[i].Color > MaxColor)
            MaxColor = G.Vertices[i].Color;

    return MaxColor;
}

```

# Answer
Your algorithm is known as greedy coloring. Wikipedia describes the following bipartite graph, on which the algorithm performs particularly badly:

* Vertices: $x\_1,y\_1,\ldots,x\_n,y\_n$.
* Edges: $x\_i$ is connected to $y\_j$ whenever $i \neq j$.
* Greedy coloring: $1, 1, 2, 2, \ldots, n, n$.

The greedy coloring uses $n$ colors, while the graph is bipartite and so 2-colorable.
> 2 votes

---
Tags: graphs, correctness-proof
---


title: Running time in FPT

text:
# Question
Title: Running time in FPT
For a certain parameter $k$, is the algorithm with the running time of $O(k.n^{\log{n}})$ in class $FPT$? I would appreciate if you can kindly guide me through.

# Answer
No, a running time like $f(k)n^{g(n,k)}$ is not suitable for any non-constant function $g$.

$\mathrm{FPT}$ is the class of problems computable in time $O(f(k)\cdot n^{c})$ for some *fixed* $c \in \mathbb{N}$. The "fixed" is very important, much the same as $\mathrm{P}$ is the class of problems computable in time $O(n^{c})$ for some fixed $c$ \- you don't get to even have a small non-constant function (such as $n^{\log n}$) in the exponent and still be in $\mathrm{P}$.
> 4 votes

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


# Question
Title: How prefix property of language affects the PDA
I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this fact:

* In PDA we have two modes of accepting the language, which are "empty stack method" and "final state acceptance method".
* Language accepted by both of these modes in PDA (NPDA) are equal, but in DPDA language accepted by "final state method" \> "empty stack method" (strictly).
* Thirdly we know that those "deterministic context-free language" having prefix property can not be accepted by "empty stack". An example is $L = \\{ a^n \mid n\>0 \\}$. So for these languages, we need final state method of DPDA.

Now my doubt is that if every DPDA is NPDA then the language accepted by both of the modes should be same in DPDA. I think that I am missing something here because individually all of the above result are ok, but when put sequentially they seems to cause a contradiction.

# Answer
The root of your problem is in the second statement:

> Language accepted by both of these modes in PDA (NPDA) are equal.

I'm not sure what you mean by that. You might mean the following false statement:

> The language accepted by a PDA using the empty state acceptance condition is the same as the language accepted by the *same* PDA using the final state acceptance condition.

The true statement is the following:

> If a language is accepted by some PDA using the empty stack acceptance condition, then it is accepted by a different PDA using the final state acceptance condition; and vice versa.

This involves two conversions: from an "empty stack" PDA to a "final state" PDA, and vice versa. The first conversion preserves determinism, the second doesn't. In other words, if we apply the first conversion to an "empty stack" DPDA, then we get a "final state" DPDA. But if we apply the second conversion to a "final state" DPDA, we get an "empty stack" NPDA which is in general not deterministic.

The same statement can be stated differently:

> The set of languages accepted by "empty stack" PDAs is the same as the set of languages accepted by "final state" PDAs.

The same doesn't hold for DPDAs, though it is true that the set of languages accepted by "empty stack" DPDAs is a subset of the set of languages accepted by "final state" PDAs.
> 2 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: Graphs in space efficient representation
Let $G$ be a graph such that $V$ denotes a vertex set and $E$ is an edge set of the graph $G$. Let us consider that for the input graph $G$ it is the case that $|E| \le O(|V| \log |V|)$. Given a graph $G$, I want to answer whether $(u,v) \in E$. If the input graph is given by adjacency representation then I can answer whether $(u,v) \in E$ in $O(\log |V|)$ time with space complexity $O(|V| \log |V|)$.

Space complexity refers to the space taken by input in words. One word means $O(\log |V|)$ bits.

**Question:** Does there exists a representation of graph $G$ such that I can answer whether $(u,v) \in E$ in $o(\log |V|)$ time with space complexity $O(|V|)$?

# Answer
> 1 votes
Farzan and Monroe, Succinct Representations of Arbitrary Graphs, give such a representation with *constant* query time. See their Theorem 8.

---
Tags: data-structures, space-complexity
---


# Question
Title: Why do we have to make variables unique when evaluating $\lambda$-calculus?
I'm studying $\lambda$-calculus and came across a problem that I'm not sure how to understand. More specifically, it's about evaluating $\lambda$-calculus expressions using $\beta$-reduction.

I was taught that the basic steps for performing $\beta$-reduction are to

> 1. Find reducible expressions in the form of ($\lambda x.$$e\_1$) $e\_2$.
> 2. Rewrite the expression by substituting every free occurrence of $x$ in $e\_1$ with $e\_2$.

I've solved some exercise problems which seemed fairly simple to understand, but came across one that I couldn't understand the answer.

The expression in question is ($\lambda x.$($\lambda y.x$)) $y$, and after following the rules above I ended up with the result of $\lambda y.y$ after replacing the free occurrence of $x$ with $y$ in $\lambda y.x$. However, the correct answer seems to be $\lambda y.x$.

The rationale that I've been able to find is that before applying $\beta$-reduction, we have to change variables to be "unique."

Could someone explain the reasoning behind this for me please?

# Answer
> 2 votes
When performing a $\beta$-reduction, there are cases in which an $\alpha$-conversion is needed first; otherwise, the $\beta$-reduction fails to preserve semantics. This is here the case: you are replacing the free variable $x$ with $e\_2$ and $e\_2$ contains free variables which are bound within $e\_1$.

You can easily see why the semantics are not preserved: $(\lambda y.y)$ and $(\lambda y.x)$ are not equivalent expressions because $(\lambda y.y)z = z$ but $(\lambda y.x)z = x$. In order to preserve the semantics, you first need to perform an $\alpha$-conversion on $(\lambda y.x)$ so as to replace $y$ with something else which is not free in $e\_2$ (thus achieving "uniqueness"—though IMO such a term should be frowned upon here).

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


# Question
Title: Why are threads called the unit of dispatch?
Threads called the "unit of dispatch" but what does that mean? I was looking over the web and two operating systems books but I can't find the answer. It seems that processes are defined by two characteristics: resource ownership and scheduling/execution. I understand that threads are within processes, and that there must be at least one thread. Can someone explain this to me please?

# Answer
> 0 votes
Threads are called the unit of dispatch because they are part of the process in almost all cases.Also they have states and priorities on the basis of which we can apply specific scheduling algorithm for process scheduling.

# Answer
> 2 votes
"Unit of dispatch" just means "the thing that gets scheduled."

---
Tags: operating-systems, process-scheduling, threads
---


# Question
Title: Is Datalog negation and the built-in predicate $ \neq $ similar?
I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking that using the predicate $ \neq $ would solve those problems but then I see the following:

p(X) :- r(X) & ¬q(X).

q(X) :- r(X) & ¬p(X).

The problem is this has 2 minimal models and if I'm not mistaken so does this:

p(X) :- r(X) & q(Y) & X $ \neq $ Y.

q(X) :- r(X) & p(Y) & X $ \neq $ Y.

Is there an equivalence between these 2 operators? If so, did I miss it or is it not mentioned that it's unsafe to use $ \neq $ with recursion?

# Answer
There was a misunderstanding in regards to the evaluation algorithm/minimal model.

The derivation of new values is atomic e.g.:

step 1:

* **p** = {}
* **q** = {}

step 2:

* **p** = **r**
* **q** = **r**

In step 2 **p** and **q** only see the value that each other had at step 1(the old value). I thought **p** and **q** would have access to the value of the current step and thus, the order of evaluation would produce different results.

To answer the question:

p(X) :- r(X) & q(Y) & X ≠ Y.

q(X) :- r(X) & p(Y) & X ≠ Y.

only has one minimal model: **p** = **r** and **q** = **r**.
> 1 votes

---
Tags: database-theory, relational-algebra, fixed-point, datalog
---


# Question
Title: Types of reductions and associated definitions of hardness
Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M\_{A}$ and the oracle for $B$ be $O\_{B}$. The types of reductions:

* Turing reduction: $M\_{A}$ can make multiple queries to $O\_{B}$.
* Karp reduction: Also called "polynomial time Turing reduction": The input to $O\_{B}$ must be constructed in polytime. Moreover, the number of queries to $O\_{B}$ must be bounded by a polynomial. In this case: $P^{A} = P^{B}$.
* Many-one Turing reduction: $M\_{A}$ can make only one query to $O\_{B}$, during its the last step. Hence the oracle response cannot be modified. However, the time taken to constructed the input to $O\_{B}$ need not be bounded by a polynomial. Equivalently: ($\leq\_{m}$ denoting many-one reduction)

> $A \leq\_{m} B$ if $\exists$ a computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.
* Cook reduction: Also called "polynomial time many-one reduction": A many-one reduction where the time taken to construct an input to $O\_{B}$ must be bounded by a polynomial. Equivalently: ($\leq^{p}\_{m}$ denoting many-one reduction)

> $A \leq^p\_{m} B$ if $\exists$ a *poly-time* computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.
* Parsimonious reduction: Also called "polynomial time one-one reduction": A Cook reduction where every instance of $A$ mapped to a unique instance of $B$. Equivalently: ($\leq^{p}\_{1}$ denoting parsimonious reduction)

> $A \leq^p\_{1} B$ if $\exists$ a *poly-time* computable bijection $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

These reductions preserve the number of solutions. Hence $\\#M\_{A} = \\#O\_{B}$.

We can define more types of reductions by bounding the number of oracle queries, but leaving those out, could someone kindly tell me if I have gotten the nomenclature for the different types of reductions used, correctly. Are NP-complete problems defined with respect Cook reduction or parsimonious reduction? Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

If I am not wrong, the class #P-Complete is defined with respect to Karp reductions.

# Answer
Your definition of parsimonious reductions is incorrect. You are confusing it with polynomial-time one-one reductions which is a special case of Karp reductions. They don't preserve the number of "solutions". Please see this answer for more about reductions considering the number of certificates.

The rest seems fine although it is usually better to view them in a two dimensional chart:

* the complexity of reduction: computable, polynomial time, logarithmic space, etc.
* type of access: Turing, many-one, one-one, etc.

> Are NP-complete problems defined with respect Cook reduction or parsimonious reduction?

$\mathsf{NP}$ hardness and completeness are defined w.r.t. Karp reductions (polytime many-one), not Cook nor parsimonious reductions.

> Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

Take the complement of SAT, it is complete for $\mathsf{NP}$ under Cook reductions, it is not believed to be complete for $\mathsf{NP}$ under Karp reductions. Karp reductions include polytime one-one reductions.

> the class #P-Complete is defined with respect to Karp reductions

Note that $\mathsf{\\#P}$ is not class of decisions problems, it is a class of function computation problems. Its hardness and completeness are usually defined w.r.t. Cook reductions (polytime Turing). See e.g. Arora and Barak, page 346.
> 7 votes

# Answer
The definition of Karp reduction is incorrect. A Karp reduction is a polynomial-time Turing reduction in which the oracle $O\_B$ is called exactly once, during the reductions last step.
> 1 votes

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


# Question
Title: Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time
I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\\{0, 1\\}^n$ in polynomial time.

Additionally, all of the coefficients of $A$ are in $\\{-1, 0, 1\\}$, but I couldn't find a way to use that.

The trivial case is if the (matrix $A$ of the) system is invertible, there is only one solution, it is easy to check whether all of them belong to $\\{0,1\\}$.

However, if you have infinitely many solutions, and $k$ free variable, I can't find a way to do better than check all the $2^k$ possibilities.

* Do you know any algorithm to do so in polynomial time ?

I also tried to do a reduction from SAT (or some variant with n clauses and n variables in each clause, to show that it is NP complete), but because of the fact that we have $Ax = b$ and not $Ax \geq b$, I couldn't do that either.

* Do you have a reduction to show that this problem is NP complete ?

# Answer
1-IN-3SAT is the following problem: given a collection of 3-clauses (just like 3SAT), decide whether there is a truth assignment which satisfies exactly one literal in each clause. 1-IN-3SAT is known to be NP-complete, see for example here. You can reduce 1-IN-3SAT to your problem – I'll let you work out the details.
> 1 votes

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


title: Distinct Minimum Weight Spanning Trees

text:
# Question
Title: Distinct Minimum Weight Spanning Trees
I am trying to find the total number of **distinct minimum weight spanning trees(MWST)** in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider Isomorphic trees(if it is present) as a single minimum weight spanning tree or not while counting the distinct MWSTs because graph is unlabeled.

For example, If I have a graph as :

Now, I have to find the Total number of **distinct minimum weight spanning trees(MWST)** in the above weighted graph.

I got total $3\times2 =6 $ possibilities of MWSTs but I also found the possibility of Isomorphic trees in these total $6$ MWSTs because graph is unlabeled. For example,the below $2$ MWSTs are Isomorphic in nature for the above given graph.

Similarly , If I have a simple, weighted, undirected and unlabeled graph as :

Now, I got total $2^{2} \times 2^{4} = 64$ MWSTs but If I consider Isomorphism property in a graph then I am getting 2 Isomorphic Trees as :

So, If I consider the possibility of many Isomorphic trees like above in the given graph then total number of **distinct MWSTs** will be less than $6$ and $64$ in the above 2 cases respectively. But I am not sure whether it is correct or not.

So, My doubt is :- While counting the total number of **distinct** **MWSTs** in an **unlabeled weighted graph**, Should I have to consider Isomorphic MWSTs as a single minimum weight spanning tree or not ?

# Answer
> 1 votes
There could be a few reasonable answers.

The simplest answer is that there are 6 minimum weight spanning trees (MSTs) in the first case and 64 MSTs in the second case. Look, the fact that you have said the same numbers and I can understand you perfectly means that interpretation makes some sense. Indeed, a strict definition/procedure can be given to yield those two numbers, although I will not be doing that here.

Let me proceed with another natural and interesting approach according to the conditions. How can we count distinct distinct MSTs of a given unlabelled weighted graph $G$? Here is one reasonable procedure. Initially we have counted 0 MST. Now someone will present to us the MSTs **one at a time** together with $G$ to us. Every information that is available should be presented to us accurately, including whether two vertices are connected and what is the weight of each edge and which edge is selected as part of the current MST. How these information will be presented can be arbitrary. Vertices can be labelled arbitrarily. The order of edges presented can be arbitrary. If drawn graphically, the shape of each edge and the location of the each vertex can be arbitrary. Etc. Whenever we can be confident that we are seeing a new MST, we will increase the count by 1. Using this approach, which is probably what you meant by considering "isomorphic MWSTs as a single minimum weight spanning tree", we will count 3 MSTs for the first graph and 20 MSTs for the second graph.

In practice, the second approach is too difficult for us to come up with results that we can understand or that could be beautiful. So, while I like the second approach very much as a challenge, I would suggest that you go with the first approach in a casual setting.

Note that there are a few ambiguities inherent in the question that needs to be defined formally (a.k.a. rigorously) before we can agree what is the way to count. For example, what does it mean by an "unlabelled weighted tree"? Do we require that the same weight be assigned to all edges that could be mapped to each other under an graph isomorphism (which happens to be the cases here)? How will we distinguish two "unlabelled weighted" trees? These questions should have been answered before we can count the number of distinct MSTs in a definitive way.

---
Tags: algorithms, graphs
---


title: What is the point in hashing a value?

text:
# Question
Title: What is the point in hashing a value?
I apologise if this is not the right place for this question... I didn't want to ask on Stackoverflow or CodeReview as it will closed in minutes as "too broad".

A client of mine is writing an API that takes a piece of personal-identifying information as the parameter in the URL, and has asked that the value is hashed using SHA512.

Normally when I deal with anything that involves personal information in this way, I'd **encrypt** it using a shared private key... but I'm really fuzzy on the whole idea of hashing.

My understanding of hashing was effectively...

* take the input value and create a hash from it
* when checking the value, create a hash from the new input value and compare them

What I'm struggling to understand (and I don't want to ask the client and show my ignorance) is **how** does the client take the hashed value and turn it back into the original input value?

And in particular, if the client can convert the hash back to the original input, what is stopping anybody else doing it?

And if other people **can** convert it back, what's the point in hashing it in the first place?

---

**Update**

After speak to the client, the answer (as many of you guessed) is that they are storing the hash of the PII in their database, and doing a match-search against the value I will be sending through.

# Answer
The purpose of a hash in this scenario to be able to uniquely identify an entity. It's not strictly unique, only probabilistically unique.

Hashes are not reversible functions, so your client can't know the data that was encoded with it. It could be guessed by brute force and maybe some know attacks to the hash assuming the type/format of data is known, but in principle is not reversible).

So process A (system or organization) A can work with the facts of the entity uniquely identified by the hash without knowing the personal identity value. Process A can then pass the processed information back to process B, that knows the personal identity value and then can combine the information given to Process A and the information it already has and carry out another processing.

The advantage in this case from a security perspective is that you have less security issues as process A (system or organization) will never has access to that personal identity. Even if A is hacked, the personal data is safe\*.
> 13 votes

# Answer
The whole point of (cryptographically secure) hashing is that you can't recover the original from the hash.

Technically, it's impossible anyway, since there are only $2^{512}$ different values the hash can take, but there are many more than $2^{512}$ possible documents. This means many different documents will produce the same hash value. However, $2^{512}$ is a huge number, so it's very difficult to generate a document that will have a specific hash value.
> 3 votes

# Answer
Besides being used to obfuscate sensitive information, hashes are also used in data lookups where the expected use case is random access, rather than sequential reading.

After all, while computers can often spread data out evenly if designed to, humans tend to generate some very clumpy data. For example, Smith is the most popular last name in the US, so finding a specific person with that name is harder than finding someone with a less common last name, if your data is indexed on last names.

The ideal hash algorithms for creating these types of hashmaps are not cryptographically secure; simply great at spreading data across the available key space, and fast to use. Any security, such as being unable to re-assemble the plaintext from the hash value, is secondary.

Now, in this particular case, SHA-2 512 is one of the worst options to use. SHA-2 is slow on purpose. In cryptographic hashing, this is a feature... but not so great in creating hashmaps. The keyspace is also huge; well beyond what anyone would want to use in their index, and like all hash algorithms, does not guarantee to avoid all collisions; so the software will need to recognize collisions and still be able to serve up the appropriate data.

That is, data indexed on a hash does not use the hash alone as its key. The hashmap's key includes the plaintext portion of the key, as well... The hash portion just gets you in close to the data that you want, and it's usually trivial to pick the exact data from there, rather than a sequential scan through millions of Smiths.

From a security standpoint, this question raises a couple of "smells." SHA-2 is used primarily for message digests; as part of a step to make sure that a message had not been tampered with while in transit. (Of course, you need a way to keep the digest from being tampered with, as well, which is why digital signatures require public key cryptography, and unencrypted HMACs are often given through side channels.)

Using any hash without random salt opens your data up to rainbow table attacks... These are typically only useful for short plaintexts, such as passwords, social security numbers, telephone numbers, and names. Since the hashes are being shared in the URL, it sounds like your client is most definitely not using random salts.

A random salt *could* be implemented in this case, but if done wrong would be susceptible to replay attacks. There is nothing sensitive about sharing the salt, just as there's nothing sensitive about the hash value itself, outside of brute force attempts. However, once a request has been made with a particular salt/plaintext combination, additional requests for that resource using that combination should be avoided.

The most secure way, though, and the current industry standard, is to do away with hashes entirely in the URL, and use a robust authentication and authorization system. Note that authentication and authorization are two distinct things, even though they're related, and should be treated as such. Use TLS. Redirect all non-secure HTTP requests to HTTPS, always. (Certs are free. There is no excuse. Even for your static-HTML-only blog; use TLS.)

And finally, if you need to get a resource where the URI shouldn't reveal anything about the content, use a nonce. Make sure you throw it away when it's been used... and make sure you've authenticated them AND checked their authorization when the user is using the nonce.

You can't just sprinkle hashes around an application and call it secure.
> 1 votes

---
Tags: hash, encryption
---


title: Longest cycle contained in two cycles

text:
# Question
Title: Longest cycle contained in two cycles
Is the following problem NP-complete? (I assume yes).

> **Input:** $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are **not** a part of the input).
>
> **Question:** Is there a simple cycle in $G$ with length greater than $k$?

Obviously the problem is in NP and the maximum degree in $G$ is $\leq 4$, but that doesn't seem to help.

# Answer
A reduction attempt ....

Reduction from Hamiltonian path on digraph $G = (V,E)$ with max degree 3 which is NPC \[G&J\]

* ignore the direction of the edges, and using a first depth (undirected) scan from an arbitrary node, divide the edges of $G$ in two sets of distinct (undirected) paths (red and green in the figures);
* join the red paths adding extra "linking nodes" (purple nodes in the figure B) and make an undirected red circuit; join the green paths adding extra "linking nodes" (purple nodes in the figure) and make an undirected green circuit;
* transform each original node $b \in V$ of indegree 1 and outdegree 2 (figure C), adding $k$ yellow nodes on the inbound *red* edge $a\to b$, and adding $k$ yellow nodes on the first outbound *red* edge $b \to c$; finally add $k$ yellow nodes "towards" the second outbound *green* edge $b \to d$ using a "wrapped" path around $b$ that touches the outermost yellow nodes of the red edges (figure D).

In the resulting graph all the $3k$ yellow nodes can be traversed by a simple path only in the two ways showed in figure E and figure F, which correspond to the two valid traversals of the original node $b \in V$; informally if an edge towards the extra "linking" purple node is used, $k$ yellow nodes cannot be traversed.

* transform each original node of V of indegree 2 and outdegree 1 in a similar way

Picking a large enough $k \gg |V| $, the result graph $G'$ has an simple path of length greater than $3k(|V|-1)$ if and only if the original graph $G$ has an Hamiltonian path (of length $|V|-1$)

The larger picture can be downloaded here
> 2 votes

# Answer
Inspired by Vor's answer, I want to give a simpler one.

Start with Hamiltonian cycle problem for grid graphs problem which was proven hard by Itai.

It can be easily seen that edge set of a grid graph can be partitioned into 2 disjoint subsets: horizontal and vertical.

So now, we need to weave all horizontal ones into one simple cycle, and weave all vertical ones into another simple cycle.

This is very easy task: for vertical ones, sweep from leftmost to rightmost, just connect any vertical gaps, then connect consecutive x-coordinated vertical line, then connect the lowest leftmost vertex with the highest rightmost vertex. Do similarly for horizontal edges.

Note that the obtained graph is still simple, undirected and satisfies requirement. It is simple because at the last steps of vertical phase and horizontal phase, we deal with two different vertex pairs.

Now, do a similar trick as Vor did. At each vertex, for each of its original incident edge, add $k$ new vertices. As usual, $k$ ahouls be large enough. Lastly, the length of a genuine Hamiltonian cycle should be $2k|V|$. But of course, it is not hamiltonian of the obtained graph.
> 0 votes

---
Tags: graphs, np-complete, decision-problem
---


title: Number of divisors of a number - in NP?

text:
# Question
Title: Number of divisors of a number - in NP?
I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP.

The input (m,n) is in binary.

The non-deterministic Turing machine for the language would be:

1) Guess the prime factors of m.

2) Verify that ∏i(di+1)=n.

The problem is that I can't find a way to factorize in polynomial time (in the input) the number m.

If stage 1 takes m steps then it would be m=2 ^ log(m) and the whole algorithm would run in exponential time.

How can I prove that verifying that m has exactly n divisors is in NP ? Perhaps not via factorization but somehow else. I've run out of ideas.

# Answer
A number with k binary digits has at most k prime factors. That's because the smallest number with k prime factors is 2^k.

So given a number m with k binary digits you can easily be given a list of the prime factors of m. You can check that the product of these prime factors is indeed m in polynomial time easily. You can easily calculate the number of factors from the prime factors in polynomial time.

But what you also need to do is that the purported list of prime factors is actually a list of primes. Here comes another theorem that shows for every prime p, there is an easily verifiable proof that p is indeed a prime.

The oracle should contain a list of the prime factors, and for every item in the list an oracle for proving that it is prime.

For being in NP, there is *absolutely no need* that you are able to provide the oracle in polynomial time. You only need to be able to check it in polynomial time.
> 1 votes

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


# Question
Title: Is it decidable that a context free language contains a given regular language?
I've been asked to solve this problem, but I'm completely stuck now.

> Is the set $\\{G \in\text{CFG} \mid L(G)\supseteq L(A) \\}$ where A is DFA fixed beforehand decidable?

I know I've to find a reduction, and as a hint they told me that it is related to Acceptance Problem or Post Correspondence Problem, or probably with Non-empty Intersection problem ( $\\{\langle G1, G2\rangle \in \text{CFG} \times \text{CFG} \mid L(G1) \cap L(G2) \not= \emptyset\\}$), which are undecidable.

I've been reading about these problems for hours, and reading about reductions from these problems to others trying to find any idea, but I'm stuck.

I'd really appreciate any help, whether some hints or the answer.

# Answer
> 0 votes
It depends on $A$.

As Hendrik pointed out, it is undecidable whether $L(G)\supseteq\Delta^∗$ for a context-free grammar $G$ with alphabet $\Delta$, $|\Delta|\>1$: Is equivalence of a CFG and an RG undecidable?".

When the alphabet is unary, it is always decidable since a context-free language defined over a one-letter alphabet is regular and the problem of containment of regular languages is decidable.

It is trivially decidable whether $L(G)\supseteq\emptyset$ since the answer is always yes. In fact, it is decidable whether $L(G)$ contains a given finite language since the membership question for a context-free language is decidable because of CYK algorithm or any CFL parsing algorithm.

# Answer
> 1 votes
Indeed, it is undecidable whether a context-free grammar generates all strings over its alphabet. But I guess you want to know how such a result is obtained.

The classical result "undecidable $L(G) = \Delta^\*$ for CFG $G$" was obtained by Bar-Hillel, Perles and Shamir in 1961 using a coding of Turing Machine computations. They showed that the set of strings that where *not* codings of valid TM computations form a context-free language. Of course if there are no valid computations then that language is $\Delta^\*$.

You can do the same with codings of solutions of the Post Correspondence Problem. Given set of pairs $(u\_1,v\_1), \dots, (u\_n,v\_n)$ you can code PCP "solutions" as strings $u\_{i\_1}\dots u\_{i\_k}\\#v^R\_{i\_k}\dots v^R\_{i\_1}$ such that both sides are equal (or rather, mirror image).

Argue that the non-solutions form a context-free language.

---
Tags: formal-languages, context-free, reductions, undecidability, decision-problem
---


# Question
Title: With a halting oracle, can tell whether something will have finite output?
A program can have finite output, yet still not halt. Example:

```
1: output "Yolo"
2: output ""
3: go to step 2

```

This only ever outputs "Yolo", despite never halting.

Is there some way, with a halting oracle, to determine whether a program will have infinite output or not?

Bonus: If not, what would be the Turing Degree of a machine capable of such a feat?

# Answer
It's not clear what specific computational model you use. If you're using Turing Machines, then having a finite output is equivalent to having a finite number of distinct configurations (assuming that you're not allowed to "erase" the tape).

So we're considering the language of all TMs $M$ such that $M$ has a finite number of configurations when run on the empty input. Clearly this is Turing recognizable - simulate the machine and accept if it halts or repeats a configuration. Thus, the problem is in RE.

It's also very simple to show that it's not in coRE by a reduction from $A\_{TM}$. So we conclude that the problem is in RE\coRE.

Now, given a halting-problem oracle, the problem is decidable: Given a TM $M$, modify it to a machine $M'$ such that $M'$ simulates $M$ and records the configurations, and if a configuration is repeated,or if $M$ halts, then $M'$ halts. Now simply run the oracle on $M'$.
> 3 votes

# Answer
# 2?

Turing2-\>Model:

```
IsHalt(
    while(i-th char ever appear) i++;
)

```

Model-\>Turing2:

```
Parallelly foreach i in Positive Integer {
    Run the tested program, with "Will turing machine P halt?" written into "Will P halt in i steps?"
    print "lol"
} // Won't work if it tries to find a non-halting program from run-longer program list, which won't halt but halt for each i

```
> 0 votes

---
Tags: turing-machines, halting-problem, oracle-machines
---


title: Does $\Sigma^* \cdot a^nb^n=\Sigma^*$

text:
# Question
Title: Does $\Sigma^* \cdot a^nb^n=\Sigma^*$
Is it true to say that $\Sigma^\* \cdot$ {$a^nb^n: n\>=0$} = $\Sigma^\*$

Becuase if we take $\Sigma^\*$ and concatenate it to {$a^nb^n: n\>=0$} we don't get any "new" words than those we had in $\Sigma^\*$ in the first place.

# Answer
> 2 votes
Yes if $\Sigma \supseteq \\{a, b\\}$. To show the equality, let's show one is a subset of the other, and vice versa.

* $\Sigma^\ast \cdot \left\\{ a^n b^n \middle| n \geq 0 \right\\} \subseteq \Sigma^\ast$ holds, because for any word $w \in \Sigma^\ast \cdot \left\\{ a^n b^n \middle| n \geq 0 \right\\}$, we know $w = u a^n b^n$ for $u \in \Sigma^\ast$, therefore $w \in \Sigma^\ast$ since $\Sigma \supseteq \\{a, b\\}$.
* $\Sigma^\ast \cdot \left\\{ a^n b^n \middle| n \geq 0 \right\\} \supseteq \Sigma^\ast$ holds, because

$$ \Sigma^\ast \cdot \left\\{ a^n b^n \middle| n \geq 0 \right\\} \supseteq \Sigma^\ast \cdot \\{ a^0 b^0 \\} = \Sigma^\ast \cdot \\{ \varepsilon \\} = \Sigma^\ast $$

where $\varepsilon$ is the empty word.

---
Tags: formal-languages
---


title: why can not NPDA is equal to DPDA?

text:
# Question
Title: why can not NPDA is equal to DPDA?
I have recently read that turing machine can be remodeled to perform as PDA now, i have a question that since DTM = NDTM ( non deterministic Turing machine) then every DTM can remodeled to be NDTM thus taking same analogy to PDA , we have DPDA = DTM( remodeled) = NDTM = NPDA thus creating DPDA = PDA . there is no debate on the fact that DPDA != NPDA. but the above relation is contradiction this. further,like we have TM- as deterministic by default , PDA - as non deterministic by deafult , then what about LBA? and FA?, like is there any same deafault criteria associated with LBA and FA ?

# Answer
> 2 votes
The set of languages that can be accepted by DPDA is not equal to NPDA. For example we can accept the following language using NPDA but there is no DPDA which can accept it.

$$L = \\{ww^R\\;| \\; w\in\\{0,1\\}^\*\\}.$$

Why DPDA can't accept $L$? Because D in DPDA stands for Determinism. That is DPDA can not decide in nondeterministic way where is the middle of input string (for accepting $ww^R$ it should find its middle first! check it one time!). So Class of languages NPDA can accept is bigger than DPDA.

Note that Turing machine is very powerful model. You don't have power of Deterministic Turing machine in DPDA to simulate its nondeterministic version.

# Answer
> 1 votes
The other answers have already covered why NPDAs are strictly more computationally powerful than DPDAs (and even yourself said "there is no debate" about it). Let me then address what seems to be the root of your misunderstanding (judging from the comments).

You propounded a (D)PDA can simulate a DTM by manipulating the TM's work tape as a stack. Indeed, you can push the symbols in the TM tape as the read/write head moves to the *right* and thus save them in the stack. The problem arises when the head moves back to the *left*. When doing so, the PDA is forced the pop those symbols, and they are then deleted *for good*. Even if you try to save them within the PDA's state, you can only save a constant number of symbols, whereas TMs (or even LBAs) are allowed to use at least as much space as the input length (i.e., an unbounded amount of space).

It is relevant to note, however, a (D)PDA with *two* stacks does suffice to simulate a TM. The reason for this is closely linked to the above reasoning: When the head moves back to the left, you pop the symbols from that stack, but *save them in the other one*.

# Answer
> 0 votes
As we know that NPDA and DPDA are not equivalent in their power. NPDA can accept the context free languages but DPDA cannot.So, every language accepted by DPDA can also be accepteded by NPDA but vice versa is not true.And I don't think NPDA always simulate NDTM because TM can accept recursively enumerable languages but PDA is only limited to Context free languages.

---
Tags: automata, pushdown-automata, computation-models
---


# Question
Title: Is $\{ 0^p1^q0^r \mid p \neq r \}$ context-free?
> Consider the following languages:
>
> $$ \begin{align\*} L\_1 &= \\{ 0^p 1^q 0^r \mid p,q,r \ge 0 \\}, \\ L\_2 &= \\{ 0^p 1^q 0^r \mid p,q,r \ge 0, \\; p \neq r \\}. \end{align\*} $$
>
> Which one of the following statements is false?
>
> A. $L\_2$ is context-free.
>
> B. $L\_1 \cap L\_2$ is context-free.
>
> C. $\overline{L\_2}$ is recursive.
>
> D. $\overline{L\_1}$ is context-free but not regular.

Doesn't the following show that $L\_2$ is context-free, and so option A should be false as well?

Assume $L\_2$ is context-free. Consider the string $w = 0100 \in L\_2$. Breaking $w$ into $w= uvxyz$, where $u = \epsilon$, $v = 0$, $x = 1$, $y = \epsilon$, $z = 00$, according to the pumping lemma (with $p=r=2$), $uv^2xy^2z = 00100 \in L\_2$, which is false.

# Answer
The mistake in your proof is that the pumping lemma says that such a division (w=uvxyz) exists.
So in order to say $L\_2$ is not context free, you have to show that for every division, you get a contradiction.

In your example we can use this division:
$u=01, \\, v=00, \\, x=\epsilon, \\, y=\epsilon , z=\epsilon$
So for every $n \geq 0$:
$uv^nxy^nz=01(00)^n \in L\_2$
> 1 votes

---
Tags: context-free
---


# Question
Title: Shortest path with a start vertex that touches all nodes at least once with repeats allowed
I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I believe). Maybe I am over thinking this though? I'm not looking for the fastest solution, but I fear a brute-force algorithm may take an extremely long time to perform this on a undirected graph with say 30 nodes. I'm personally trying to figure out on a video game the fastest way to traverse through every spawn point of a monster on a given zone (with a start point of course) so I can find him faster. I've already constructed a graph and figured out the distances assuming a complete graph. I guess on my part, one way to reduce the run time of such an algorithm is to remove realistically what edges wouldn't and probably wouldn't be included in a optimal path. I assume adding lots of constraints could help too. Might anyone know if there's a specific name for this problem, or if there is a simpler approach aside from just the standard brute-force? Thank you!

# Answer
> 5 votes
Your problem is just a TSP in disguise.

## 1. Dealing with "visit each node at least once"

First, compute a modified distance matrix $D(i,j)$, $i,j=1,...,n$ using an all-pairs shortest path algorithm, such as the Floyd-Warshall algorithm. That is, you want $D(i,j)$ to be the shortest path length from node $i$ to node $j$. Using Floyd-Warshall you also compute a matrix $S(i,j)$ that gives the successor of $i$ on the shortest path from $i$ to $j$.

Now apply a TSP algorithm to the distance matrix $D$. This will give you a tour $T$ that goes through each node exactly once. You now expand each step of $T$ into a shortest path (you can do this using the matrix $S$). That is, if some step of $T$ goes from $i$ to $j$, you expand it into the shortest path from $i$ to $j$. Concatenating all these paths gives a tour $T'$ that visits each node at least once, with possible repeats. If $T$ is optimal for $D$, then $T'$ must be optimal for the original graph.

## 2. Dealing with "the tour does not need to return to the starting node"

Preprocess your graph as follows. Add a dummy node, node 0, such that the distance from 0 to the starting node $s$ is 0 and the distance from node 0 to any other node is $M := n \cdot \max\_{i,j} D(i,j)$.

Now find a TSP tour on the modified graph using your TSP algorithm of choice. Because the value of $M$ is so large, any optimal TSP tour will be of the form $$ 0, s, \pi(1), ..., \pi(n-1), 0$$ where $\pi$ is some permutation of the nodes excluding the start node and node 0. Then the sequence $s, \pi(1), \ldots, \pi(n-1)$ represents your solution.

## 3. Exact vs heuristic

You can use any algorithm for the symmetric TSP problem. If $n$ is about 30, you will probably not be able to apply an exact (= optimal) TSP algorithm such as the Held-Karp dynamic programming algorithm. A very simple yet reasonable heuristic you might want to try is 2-OPT, which is straightforward to program. A branch-and-bound approach might also work well in practice.

---
Tags: graphs, shortest-path, graph-traversal
---


# Question
Title: When is relation in 3NF but not in BCNF?
A book by Korth et al. defines BCNF as follows:

> A relation schema $R$ is in BCNF with respect to a set F of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, where $α⊆R$ and $β⊆R$, at least one of the following holds:
>
> * $α→β$ is a trivial functional dependency (that is, $β⊆α$).
> * $α$ is a superkey for schema $R$.

It then defines 3NF as follows:

> A relation schema $R$ is in third normal form with respect to a set $F$ of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, where $α⊆R$ and $β⊆R$, at least one of the following holds:
>
> * $α→β$ is a trivial functional dependency.
> * $α$ is a superkey for $R$.
> * Each attribute $A$ in $β-α$ is contained in a candidate key for $R$

So 3NF definition adds an additional 3rd condition to the BCNF definition: "Each attribute $A$ in $β-α$ is contained in a candidate key for $R$". I think we can correctly interpret this condition as $β-α$ are key attributes.

Now I was thinking about which relations are in 3NF but not in BCNF. Clearly the relation which contains the dependency that satisfies this 3rd condition can be in 3NF but not in BCNF.

The book gives following example:

> The schema *dept\_advisor* : {*s\_ID, i\_ID, dept\_name*} with FDs
>
> * *i\_ID $→$ dept\_name*
> * *s\_ID, dept\_name $→$ i\_ID*
>
> Here, first FD is non trivial. Also *i\_ID* is not a super key. Hence schema is not in BCNF. Now *dept\_name* is a part of the candidate key (*s\_ID,dept\_name*). Hence, *dept\_advisor* is in 3NF.

Now I came across following statement on this site, which I think I have also read in the book:

> 3NF states that all data in a table must depend only on that table’s "primary key", and not on any other field in the table. At first glance it would seem that BCNF and 3NF are the same thing. However, in some rare cases it does happen that a 3NF table is not BCNF-compliant. This may happen in tables with two or more overlapping composite candidate keys.

I have two doubts:

* What does it imply by using "primary key" in first sentence. Cant there be two or more candidate keys in a 3NF relation with some FDs involving one CK and remaining FDs involving other CK. This must not be the case due to the last sentence in above paragraph, which is source of 2nd doubt below. But then why use "primary key"? Should the sentence rather be "3NF states that all data in a table must depend only on that table’s candidate keys or better to say superkey"?
* From definitions of 3NF and BCNF, what I felt is the relation which is in 3NF but not in BCNF should be the one having FD following 3rd condition of 3NF definition and there can be no other situation which can lead to non-BCNF but 3NF relation. If so, how is "two or more overlapping composite candidate keys" (as stated in last sentence of above paragraph) is equivalent to/lead to such FD? Or to put in different way, where are overlapping composite candidate keys in above example of *dept\_advisor*?

Am I thinking stupidly? Am I giving unnecessary importance to these points and are in fact senseless?

# Answer
> 1 votes
> "*I think we can correctly interpret this condition as β−α are key attributes.*"

No. β−α is a *set* of attributes. What that statement is saying is,

*Every attribute in that set is part of some (at least one) candidate key for the relation*.

Also, if by 'key' attribute, you mean an attribute that is a superkey, i.e., an attribute whose value uniquely determines the tuple, then NO, every element in β−α is NOT a key attribute. It is just a prime attribute (in other words, part of some candidate key).

For example, if we write your schema as:

> Dept\_advisor : {A, B, C},

then the FD's can be written as:

1. **B → C** (α = {B}, β = {C}, β−α = {C} - {B} = {C})
2. **AC → B** (α = {A, C}, β = {B}, β−α = {B} - {A, C} = {B})

Here, **\[1\]** is neither a trivial dependency nor is **α** (here, B) a superkey of the relation. In other words, *none* of the two conditions for BCNF hold for this FD. For BCNF, you need *all* the FD's to satisfy *at least one* of the two conditions, but here you have *one* FD which satisfies *none*. So this schema is not in BCNF. You got this right.

Now, testing it for 3NF, you can confirm that both **\[1\]** and **\[2\]** satisfy *at least one* of the 3 conditions for 3NF. **\[2\]** satisfies the 2nd condition (α = {A,C} is a superkey), so we are good so far. **\[1\]** does not satisfy any of the first two conditions, which are also the conditions for BCNF. But, it does satisfy the third condition, i.e., each attribute in β−α (here, only one attribute, namely **B**) is part of some candidate key.

What candidate key is that, you ask? You can easily find one.

Take {A, B}. It is a candidate key because you have the FD B → C, which means {A, B} → {A, B, C} gives all the attributes of the relation, which means it is a superkey. But no proper subset of {A, B}, i.e., neither A nor B alone, are superkeys themselves. In other words, neither {A} → {A, B, C}, nor {B} → {A, B, C}. So yes, you got this one right too, but for the wrong reasons.

As for the other statement, about 3NF tables being dependent only on the "primary key", you are better off just ignoring it and sticking to the definition and trying to understand and use it correctly.

---
Tags: database-theory, normal-forms
---


# Question
Title: Identifying Coffman conditions in a given situation with deadlock
Let's suppose there are N processes and we have the following code:

```
atomic <int> c = 0;
semaphore b = 0;

proc P(i){
   ...
   if(c.getAndInc() < N - 1){
      b.wait();
   }
   else{
      b.signal();
   }
   ...
}

```

A deadlock will occur as N - 2 processes will be blocked by $ b.wait() $. I'm trying to identify how the Circular wait condition holds, being a necessary condition as it is.

(Circular wait means that "A set $\\{ P\_0, P\_1, ..., P\_n \\}$ of waiting processes must exist such that $P\_0$ is waiting for a resource held by $P\_1$, $P\_1$ is waiting for a resource held by $P\_2$, ..., $P\_{n-1}$ is waiting for a resource held by $P\_n$, and $P\_n$ is waiting for a resource held by $P\_0$". This quote is from the book "Operating System Concepts", by Silberschatz, Galvin and Gagne.)

In other words, as there is deadlock, the circular wait condition must hold, but I just don't see it. Is there anything I am misunderstanding?

Thanks!

# Answer
Considering the definition of circularity you exposed, it is important to highlight that ownership is not implemented in semaphores (it is for mutexes). So, in a way, each task is waiting for each other because each one has the possibility to "release" (i.e. perform a post to the semaphore since it starts from $0$) the resource (only if the condition inside the "if" is not satisfied). Extending this approach, also the task itself has the possibility to post to the semaphore. Moreover, note that the deadlock is present when $N\>2$.
> 1 votes

---
Tags: concurrency
---


title: Every vertex cover is a dominating set

text:
# Question
Title: Every vertex cover is a dominating set
> Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set.

Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)$ is a subset $S$ subset of $V$ such that every vertex is either in $S$ or has a neighbor in $S$.

I know that a vertex cover is always going to be a dominating set because a vertex cover set is such that every edge has a vertex in the set, which means that a vertex not in the set (so on the other end of the edge) must have a neighbor in the set in order for all edges to be covered...

I just don't know how to write this as a proof.

# Answer
Here is a correct version of your result:

> If a graph contains no isolated vertices, then every vertex cover is a dominating set.

For the proof, let $G$ be a graph with no isolated vertices, and let $S$ be a vertex cover. In order to show that $S$ is a dominating set, we need to show that every vertex not in $S$ has a neighbor in $S$. Suppose therefore that $v \notin S$. Since $G$ has no isolated vertices, $v$ has some neighbor $u$. Since $S$ is a vertex cover, it must contain one of $v,u$. Since $v \notin S$, necessarily $u \in S$. Therefore $v$ has a neighbor $u \in S$.

A stronger version of this result states that the condition of having no isolated vertices is tight.

> Let us call a graph *good* if every vertex cover is a dominating set.
>
> A graph is good iff it contains no isolated vertices.

We already saw one direction. Now suppose $G$ is a graph containing some isolated vertex $v$. Take an arbitrary vertex cover $S$. Since $v$ is isolated, $S \setminus \\{v\\}$ is also a vertex cover, but it is not a dominating set, since $S \setminus \\{v\\}$ doesn't contain $v$ or any of its neighbors (since it has none!).
> 1 votes

---
Tags: graphs, set-cover
---


# Question
Title: Does every infinite context free language contain an infinite regular subset?
Can someone explain to me if this is true or not?

# Answer
> 2 votes
No.

A counterexample is simply $E=\\{a^nb^n\mid n\ge0\\}$, the classic context-free language that is not regular.

For the sake of contradiction, suppose $E$ has an infinite regular subset $S$. So $S$ satisfies the pumping lemma for regular languages. Suppose $p\ge1$ is a pumping length of $S$. Since $S$ is infinite, $w=a^mb^m \in S$ for some $m\ge p$. Since $|w|=2m\gt p$, $w$ can be written as $w=xyz$, satisfying the following conditions:

* $|y| \geq 1$
* $|xy|\leq p$
* $\forall n\geq 0$, $xy^{n}z\in S$

Since $|xy|\le p$ and $w$ starts with at least $p$ $a$'s, $y=a^k$ for some $k\ge1$. Since $xz=xy^0z$ has less $a$'s than $b$'s, $xz\not\in S$. This contradiction shows that $S$ is not regular. That is, no infinite subset of $E$ is regular.

What we just showed above is the fact that given any language, if every word in it cannot be pumped as in the pumping lemma for regular languages, then that language does not contain an infinite regular subset.

---

Here is a related exercise.

**Exercise.** A language is called prefix-closed if all prefixes of every string in the language are also in the language. Let $P$ be an infinite, prefix-closed, context-free language. Show that $P$ contains an infinite regular subset.

---
Tags: regular-languages, context-free
---


title: When are you supposed to eta-reduce?

text:
# Question
Title: When are you supposed to eta-reduce?
Wikipedia lists the following algorithm for normalizing a lambda calculus term $t$:

* If $t$ is not in head normal form, beta reduce the beta redex in the head position to get $t'$. Then normalize $t'$ to get $t''$. $t''$ is the normal form of $t$.
* If $t$ is in head normal form, normalize each of its subterms to get $t'$. $t'$ is the normal form of $t$.

The implied base case is if $t$ is in head normal form but has no subterms, in which case it is in normal form already. If $t$ has a normal form, the above algorithm is guaranteed to find it.

The problem I'm having is that it does not seem that the algorithm ever eta-reduces.

For example given the algorithm normalizes $\lambda y.\lambda x.y x$ to itself (since it is already in head normal form, and $x$ is also in head normal form). It should normalize to $\lambda y. y$ though.

It seems apparent that you need to add eta-reduction steps at *some point*. The problem is I'm not sure where to put them and preserve the property that the algorithm is guaranteed to find the normal form.

When and where do you eta-reduce to achieve this?

# Answer
> 4 votes
Here are some crucial properties about $\beta$ and $\eta$ reductions that explain the strategies for computing normal forms.

We write $\rightarrow\_\beta, \rightarrow\_\eta$ for a single step of $\beta$ resp. $\eta$, $\rightarrow^\*\_{\beta},\rightarrow^\*\_\eta$ for 0 or more steps, and $\rightarrow^{\mathrm{hd}}\_\beta$ for *head* $\beta$-reductions.

> Lemma 1: If $t\rightarrow^\*\_\beta t'\rightarrow^{\mathrm{hd}}\_\beta t''$, then there is some $u$ such that $$ t\rightarrow^{\mathrm{hd}}\_\beta u\rightarrow^\*\_\beta t''$$

So head reduction can always be done right up front, and they always must happen, i.e. they can never "disappear" after a (non-head) $\beta$ reduction. A more subtle result (that relies on this one) is that if there *is* a normal form, then starting with the head reductions is a complete *strategy* to find it.

> Lemma 2: If $t\rightarrow\_\eta t' \rightarrow^\*\_\beta t''$ then there is some $u$ such that $$ t\rightarrow^\*\_\beta u\rightarrow^\*\_\eta t''$$

That is, $\eta$ reductions can be "postponed", though they may disappear, e.g. as in $(\lambda x. t\ x)\ u$.

Finally:

> Lemma 3: if $t$ is a $\beta$ normal form, and $t\rightarrow\_\eta t'$, then $t'$ is also a $\beta$ normal form.

These 2 lemmas imply that it never hurts to push all the $\eta$ reductions to the very end. So simply adding to the $\beta$ normalization strategy: "And then $\eta$ normalize" is a strategy for finding $\beta\eta$ normal forms.

# Answer
> 3 votes
$\eta$ conversion is not a mean to reduce a term to $\beta$-normal form, but a tool to show equivalence regarding the (future) application; to express that 2 terms “are the same function”; that they will reduce to the same term when applied to arbitrary term(s).

If you want to also do $\eta$ conversions, you can do it anytime because you still have the same term (application-wise) after performing it. Having $\eta$ conversion in the theory will not enrich nor deplete the theory regarding existence of $\beta$($\eta$)-normal forms.

---
Tags: algorithms, lambda-calculus, functional-programming, normal-forms, term-rewriting
---


# Question
Title: Why whenever a caller or client modifies a library collection class, all iterators are made invalid?
Whenever a caller or client modifies a library collection class, all iterators are made invalid (with the exception of the iterator through which the change was made, in the case of remove). Give a reason for this rule in the case of an array list (using a dynamically sized array, in which an iterator has a pointer to the array) and in the case of list (using linked list nodes, in which case the iterator points to one or more list nodes).

# Answer
> 1 votes
The question is "why".

There are two problems: First, you would have to define how an iterator that doesn't become invalid would change if the underlying container changes. That will be an interesting problem. Some languages have iterators that can iterate through hash tables, enumerating all (key, value) pairs in some order. Now imagine you insert an item into the hash table, the number of items becomes too large, and the whole hash table is re-hashed, and you need to define how the iterator is modified in a meaningful way.

Second, if the iterators need to stay valid, you need to keep track somehow which iterators are involved with which underlying container. That's not too difficult, but costs time and space. Together with the first problem, it's much easier to just declare any iterator as undefined after a change.

PS. If you copy / paste this as an answer to a homework question, your teacher will most likely trace it back to this post.

---
Tags: java
---


# Question
Title: if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free
I am having a hard time understanding if this would be true or false, can someone point me in the right direction?

# Answer
> 2 votes
One way to deal with this kind of problems is to check some easy and extreme cases. Also, you would like to have a few concrete instances of the concepts involved. You should try to construct simple counterexamples with the instances. If you have found just one counterexample, great, you have found the answer. If you cannot found counterexamples by various constructions, you might have gained some understanding why it might be correct. You may have to repeat a few times.

What are some instances of non-context-free languages? Here is one. $\\{0^{n^2}\mid n\ge1\\}$. Or another one $\\{1^{n^2}\mid n\ge 1\\}$. Or another one $\\{0^{n^2+1}\mid n\ge1\\}$. How about their intersections?

In general, a condition that stipulates the type of the intersection of two languages is a very weak restriction to each of the languages. There are a lot of room for each of them to vary without changing their intersection.

---

Interested readers can enjoy the following simple exercises. $L\_1$ and $L\_2$ are are assumed to be over the same alphabet for all exercises.

Exercise 1. If $L\_1 \cap L\_2$ is finite, must at least one of them be finite?

Exercise 2. If $L\_1 \cap L\_2$ is regular, must at least one of them be regular?

Exercise 3. If $L\_1 \cap L\_2$ is context sensitive, must at least one of them be context sensitive?

Exercise 4. If $L\_1 \cap L\_2$ is decidable, must at least one of them be decidable?

Exercise 5. Raise a similar question.

# Answer
> 0 votes
This is not an answer, I can't comment.

However, think about this questions:

If $L\_1$ and $L\_2$ are context free then $L\_1∩L\_2$ is context free? And what if $L\_2$ is a regular language?

By the way, explain where you are stuck and your attempt to solve this problem.

---
Tags: regular-languages, context-free, closure-properties
---


# Question
Title: Regular expression for words containing single 1 and even number of 0s
What would be a regular expression for the language of words containing a single 1 and an even number of 0s?

# Answer
If a word contains exactly one 1 and an even number of zeroes, then we can decompose it in one of two different ways:

1. An even number of 0s, followed by 1, followed by an even number of 0s.
2. An odd number of 0s, followed by 1, followed by an odd number of 0s.

You take it from here.
> 3 votes

---
Tags: regular-expressions
---


# Question
Title: After how many iterations will an integer circle back to 0 in Python?
If this question is completely garbage I apologize because I am new to CS and haven't understood at how programming languages (Python specifically) work.

I was reading about how in a standard two-byte representation of a number, if one was to increment 65,536 times, the integer would wrap back to one. Would this case occur in Python, and if so at what number would this occur?

Edit: I read a little bit further into this and it seems that after an increment, programming languages seem to redefine the value. Would this prevent this from occur

# Answer
> 0 votes
Your question is about python, but let me make it more general. Integers are represented in three major ways in modern computers:

1. Unsigned integers of a fixed number of bits.
2. Signed integers of a fixed number of bits.
3. Bignums, also known by various other names such as multiple precision integers.

The first two exhibit the wrap-around behavior. The third doesn't.

Python uses three different representations for integers:

1. Small integers are stored as "constants".
2. Integers which fit into a signed machine word (*plain integers*) are stored as such.
3. Larger integers (*long integers*) are stored as bignums.

This is described in the python documentation.

Plain integers are automatically promoted to long integers if need be. Therefore the wrapping around behavior does not happen.

On a 64-bit system, $2^{63}-1$ is the largest plain integer:

```
>>> (2**62-1)*2+1
9223372036854775807
>>> 2**63
9223372036854775808L

```

Note the suffix `L`, which indicates a long integer.

---
Tags: python
---


# Question
Title: Karp reduction from NP-hard problem to unknown problem
If I know that problem $A$ is NP-hard, but know nothing of problem $B$ and I know that the following Karp reduction is true:

$$A \to B \\, .$$

Is it correct to conclude that $B$ must also be NP-hard?

# Answer
Short answer, yes. I won't provide an actual proof (you probably saw one in class), but rather, a sort of mnemonic that helps if this comes up on an exam.

A Karp reduction is also known as a *polynomial-time reduction*. If you can reduce from $A$ to $B$, that means if I give you a subroutine that solves $B$, you can build an algorithm to solve $A$, which does at most polynomial-time work and then calls the $B$ subroutine to get the answer.

The question is now, if you can reduce from $A$ to $B$, and $A$ is $NP$-hard, then is $B$ $NP$-hard?

Assume it isn't. In other words, assume $B$ can be solved in polynomial time. Then that means $A$ can be solved in polynomial time: run the polynomial-time reduction, call $B$ which takes polynomial time, and you have a solution to $A$ in polynomial time. We've proven $P = NP$ and earned a million dollars!

Since we haven't proven anything of the sort, our assumption must be false. In other words, $B$ must be NP-hard.

(Now, this would be a formal proof if $P \neq NP$ were a known result. But it isn't. So while this is good enough to remember on an exam, and the fact that $B$ must be $NP$-hard is in fact true, I haven't actually given a full proof of that fact.)
> 1 votes

---
Tags: reductions, np-hard
---


title: Reduce ATM to REGULAR_TM

text:
# Question
Title: Reduce ATM to REGULAR_TM
Consider $\mathsf{REGULAR\_{TM}} = \\{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\\}$.

Let $S$ be the following algorithm, which solves $\mathsf{A\_{TM}}$: “On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string:

1. Construct the following TM $M\_2$:

$M\_2$ = “On input $x$:

1. If $x$ has the form $0^n 1^n$, accept.
    2. If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$.”
2. Run $R$ (a machine solving $\mathsf{REGULAR\_{TM}}$) on input $\langle M\_2 \rangle$.
3. If $R$ accepts, accept; if $R$ rejects, reject.”

I am trying to understand this proof, but I am really confused with step 1 of $M\_2$.

The book says "$M\_2$ works by automatically accepting all strings in $\\{0^n1^n \mid n ≥ 0\\}$. In addition, if $M$ accepts $w$, $M\_2$ accepts all other strings."

But I don't understand how could $M\_2$ accept all strings. If $x$ is not of the form $0^n 1^n$ and $M$ does not accept $$, wouldn't $L( M\_2 )$ be empty?. Or can we assume there are many different $x$ as an input to $M\_2$?

# Answer
First, note that $M$ and $w$ in $M\_2$ are fixed. So whatever is the input, $M$ always *accepts* or *rejects* $w$. Second, note that $M\_2$ is not built to run.

Then:

You want to map $\<M,w\>$ to a regular language $L$ if and only if $M$ *accepts* $w$. Fix $L$, in that case you choose $\Sigma^\*$. However, if $M$ *rejects* $w$ you don't want $L$ regular (otherwise $R$ will accepts), so you choose $L'\subset L$ such that $L' = \\{0^n1^n\\}$ which is not regular.

Now you have two cases:

1) if $M$ *rejects* $w$, then $M\_2$ will accepts ***only*** the strings of the form $0^n1^n$, then $R$ will reject.

2) if $M$ *accepts* $w$, then $M\_2$ will accepts all the strings of the form $0^n1^n$ and all other strings in $\Sigma^\*-0^n1^n$, so $R$ will accept.

However in poor words, it consists to map an "yes istance" of $\<M,w\>$ to a ***single*** "yes instance" of $L$. Let me do an example:

You want to prove that $L=\\{M |\ if\ M\ accepts\ w\ then\ M\ accepts\ flip(w) \\}$, where $flip(w)$ is the bitwise of all the string $w$ (For example if $w$ = $100$ then $flip(w) = 011$.), is undecidable with a reduction from $A\_{tm}$.

Suppose $L$ is decidable, then exists a $TM$ $R$ that decides $L$. So we can build a new $TM$ $S$ that decides $A\_{tm}$.

We will doing something like this:

> $S$ on input $\<M,w\>$: "build a new $TM$ where $M$ and $w$ are constants. Call it $N\_{\<M,w\>}$, then run $R$ on input $N\_{\<M,w\>}$ and do what $R$ does."

Inside $N\_{\<M,w\>}$ we have our reduction. Take in mind we want this:

> $M$ accepts $w$ ***if and only if*** $R$ accepts $L(N\_{\<M,w\>})$

First, we fix $L(N\_{\<M,w\>})$ = $\\{100,011\\}$ (This is just an "yes instance" of $L(N\_{\<M,w\>})$

Now our $N\_{\<M,w\>}$

> ***$N\_{\<M,w\>}$ on input $x$:***
>
> ***if $x$ = $100$ then accepts***
>
> ***else if $x$=011 then run $M$ on $w$ and do what $M$ does.***

Then "run" $R$ on $N\_{\<M,w\>}$ and $S$ will accept if $R$ does:

if $M$ rejects $w$, the only string could be accepted by $N\_{\<M,w\>}$ is $100$ then both $R$ and $S$ will reject.

Otherwise if $M$ accepts $w$, $N\_{\<M,w\>}$ will accept both $100$ and $011$ then both $R$ and $S$ will accept.

So $S$ can decide $A\_{TM}$ which is impossible, the "error" was to suppose the existance of $R$.
> 1 votes

---
Tags: turing-machines, computability, reductions, undecidability
---


title: Tree with alternating types of nodes

text:
# Question
Title: Tree with alternating types of nodes
Suppose that I have a tree where each node is either of type `A` or type `B`.

Nodes of type `A` have outgoing edges only to nodes of type `B` and vice versa.

Is there a name/term for this kind of a tree?

A concrete example of such a tree would be the state tree of a 2 player game (like tic-tac-toe) which has alternating levels of states where it's `X`'s turn or `Y`'s turn.

# Answer
> 1 votes
Such a tree would be *2-colored*.

Note that all trees are *2-colorable*; a *2-colored* tree is just one where the coloring's already happened.

# Answer
> 0 votes
All trees (and forests) can be 2-colored. However there are even additional kinds (e.g. with balancing conditions).

Is every acyclic graph 2-colorable?

---
Tags: terminology, trees
---