title: Is this language recognizable?

text:
# Question
Title: Is this language recognizable?
Let $L = \\{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\\}$. I'm trying to determine whether $L$ is decidable.

I don't think it's even recognizable, but I'm not sure. Regardless, I think I can show it's undecidable. Suppose $L$ is decidable by machine $D$. Then we can construct machine $S$ that decides the accepting problem, i.e. $\mathrm{ACC} = \\{(M,w): M\text{ accepts }w\\}$, which is undecidable.

For $S$ on input $(M,w)$, construct machine $M'$ with input $x$ such that if $x \neq 1100$, then loop, and if $x = 1100$, run $M$ on $w$. If $M$ accepts, then $M'$ halts. Next, run machine $D$ on $M'$. If $M'$ halts, then $D$ accepts. Otherwise, $D$ rejects.

So, if $M$ accepts $w$, then $x=1100$ and $M'$ halts, so $D$ accepts. On the other hand, if $M$ does not accept $w$, then $M'$ loops (and does not accept anything), and $D$ rejects. But then $D$ decides $\mathrm{ACC}$, which is undecidable. Hence, $L$ is undecidable.

Am I on the right track?

# Answer
> 1 votes
To show that $L$ is not recognizable, you can reduce the complement of the halting problem to it. $\overline{\mathrm{HALT}}$ is not recognizable because, if a language and its complement are both recognizable, then they're both decidable, and we know that $\mathrm{HALT}$ isn't recursive.

Given a Turing machine $M$ and input $w$, you want to accept iff $M(w)$ loops. So construct the machine $M'$ which halts if its input is $1100$ and simulates $M(w)$, otherwise. If $M'\in L$, then $M'$ cannot halt on $0011$ or $1000$,<sup>*</sup> which means that $M(w)$ doesn't halt.

* It seems there's a typo in the question, which mentions $0011$ twice. Obviously, this doesn't make any real difference.

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


# Question
Title: How does hashed inverted page table work?
I understand hash function and inverted page table, but then the book I read describes something called hashed inverted page table (use hash to accelerate the finding because IPT is large), with TLB used. I don't understand why there is an arrow point to itself inside the hash table? Could anyone explain the mechanism?

>

# Answer
From your picture, one definitely see a hash table collision solution. If one carefully examine it, will see that the table uses itself to solve the collision, that is Open Addressing.

In open addressing, the collision can be resolved by many methods;

* Linear Probing
* Quadratic Probing
* Double hashing.

It might be Double Hashing or Quadratic Probing but the information is not enough to resolve.
> 2 votes

---
Tags: operating-systems, memory-management, hash-tables, paging
---


# Question
Title: Define a DFA that accepts all even length binary strings that don't contain the substring "111"?
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated!

# Answer
Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w \in \\{0,1\\}^\*$ or $\epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w \in \\{0,1\\}^\*$ or $1$.
and so on...

Now you can duplicate the states to have the following properties:
$A\_{even}$ means that so far you've read $w0$ for some $w \in \\{0,1\\}^\*$ or $\epsilon$, and you've read even number of letters.
$A\_{odd}$ means that so far you've read $w0$ for some $w \in \\{0,1\\}^\*$, and you've read odd number of letters ($\epsilon$ has even number of letters, so it's not included here).
$B\_{even}$ remembers that so far, you've read $w01$ for some $w \in \\{0,1\\}^\*$, and you've read even number of letters.
$B\_{odd}$ remembers that so far, you've read $w01$ for some $w \in \\{0,1\\}^\*$ or $1$, and you've read odd number of letters.

And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states

Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.
> 2 votes

---
Tags: finite-automata, discrete-mathematics
---


# Question
Title: Undirected graph with exponential number of simple cycles
Hey I am new to graph theory and this question has me stuck for hours.

What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n.

I was looking at complete graphs, but here's the catch: the total number of edges should be in theta of n.

Please help! I need to prove the correctness of such a graph but I can't find an example of the graph in the first place.

# Answer
> 4 votes
The Möbius ladder $M\_{2n}$, also called pizza graph, which has $2n$ vertices and $3n$ edges, have $2^n+n^2-n+1$ simple cycles. Here $n\ge3$.

The following two views of the Möbius ladder $M\_{16}$ is also taken from the same Wikipedia entry. Be careful that the central point on the pizza view is not a vertex of the graph. Here is an animation showing the transformation between the two views.

---

Exercise 1. (easy) Show there are at least $2^{n-1}$ simple cycles in $M\_{2n}$.

Exercise 2. Show there are $2^n+n^2-n+1$ simple cycles in $M\_{2n}$.

# Answer
> 5 votes
The graph below contains $3m+1$ vertices and at least $2^m$ simple cycles (illustration has $m=3$):

# Answer
> 3 votes
Any time you need to make an exponential number of things out of a linear number of parts, you should think "subsets": a set of size $k$ has $2^k$ subsets. In this case, the approach is to find a structure where you have a linear-sized set of choices and each subset of those choices leads to a different cycle.

In Yuval's example, you have a linear number of diamonds and, in each one, you can choose any subset of "left" vertices from the diamonds and put those in your cycle, giving exponentially many options.

In Apass.Jack's example, if you start going clockwise around the outside, you can use any odd-cardinality subset of the the radial edges to move back and forth between the outside and inside before arriving back at your start position. (If you uncrossed the two edges at the top, you'd need an even-cardinality subset of radial edges, instead.)

---
Tags: algorithms, graphs
---


# Question
Title: What is the meaning of max() in intro. to algorithms?
I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n\_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a})$ .

I'm confused regarding what **"max"** means in this context. The quadratic function is $an^2 + bn + c$ and the constants give are $c\_1 = a/4, c\_2 =7a/4$.

I'm thinking it might mean which ever of the parameters yields a larger value?

# Answer
> 1 votes
Yes, as confirmed by Gokul, $\max(p,q)$ just means the larger one of its two parameters, $p$ and $q$. It can also apply to more parameters such as $\max(p, q, r, s, t)$, where it means the largest of all 5 variables or values.

Its opposite is $\min$, which is used in the same way but means the smaller one of two values or the smallest one of all given values.

You might want to check the list of mathematical abbreviations the next time you get confused by some math abbreviations.

---
Tags: time-complexity, terminology, notation
---


# Question
Title: Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process
The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;(

Problem:

We implement a merge sort algorithm to sort $n$ items. The algorithm will divide the set into 2 roughly equal-size halves, and merge the 2 halves after each half set is recursively sorted. **Because the item comparison is complicated, the merge process takes $\theta(m\sqrt{m})$ steps for input size $m$**. What is the time complexity for this algorithm?

(a) $\theta{(n\log{n})}$
(b) $\theta{(n)}$
(c) $\theta{(n^2)}$
(d) $\theta{(n\sqrt{n})}$
(e) $\theta{(n\sqrt{n}\log{n})}$

# What I tried:

1. I know the merge sort normally can be written $S(n) = 2S(\frac{n}{2}) + n, S(1) = 1$, where the recursive function $S$ is the step cost of the merge sort for the size $n$.
2. But the problem specifies the step costs to merge is $\theta(n\sqrt{n})$, I have to rewrite it as $S(n) = 2S(\frac{n}{2}) + \theta(n\sqrt{n}) = 2S(\frac{n}{2}) + n\sqrt{n}$. I have no idea how to transform it into the general solution...

Please help me, I will learn a lot from this problem! Thanks :)

# Answer
> 3 votes
You are on the right track.

Now that we have the recurrence relation $$S(n) = 2S(\frac{n}{2}) + \Theta(n\sqrt{n}),$$ Applying the case three of the master theorem, where $a=2$, $b=2$, $\epsilon=\frac12$, we will have $S(n)= \Theta( n\sqrt n)$.

I was stretching a bit when we were applying the master theorem since the regularity condition, the existence of such $c\>0$ required for case three is not necessarily satisfied. What I really meant is that we can find two constant $0\<c\_1\<c\_2$ such that $c\_1n\sqrt n\le S(n)-2S(\frac n2) \le c\_2n\sqrt n$ for all $n$. Define $S\_1$ by $S\_1(n) = 2S\_1(\frac{n}{2}) + c\_1n\sqrt{n}$ and $S\_2$ by $S\_2(n) = 2S\_2(\frac{n}{2}) + c\_2 n\sqrt{n}$ with the same initial condition as $S$. Now we can apply case three of the master theorem to $S\_1$ and $S\_2$ to get the same $\Theta$ bound, since the regularity condition is satisfied with $1\>c=0.8\>\sqrt2/2$. Since $S\_1(n)\le S(n)\le S\_2(n)$, S(n) has the same $\Theta$ bound.

In case you have not learned/are not allowed to use the master theorem, you may have to more or less prove case three of the master theorem by yourself. You could find a proof, for example, in CLRS.

---
Tags: time-complexity, discrete-mathematics, mergesort
---


# Question
Title: Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?
Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

**My attempt:**

Lets $f(n)=g(n)=n$, then $f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$

But given answer is $O(n)$. Now sure where I have have committed mistake or if I am missing something. How it can be $O(n)$?

# Answer
> 4 votes
You have a fault in $f(n).g(n) = \Omega(n^2)$. Because, $g(n) = O(n)$ and you can't say $g(n)$ is $n$ or $\frac{1}{n^2}$ for example. Hence, we can't say nothing about $f(n).g(n)$. For more example: $$g(n) = \frac{1}{n}, f(n) = n \Rightarrow f(n).g(n) = \Theta(1)$$ $$g(n) = 1, f(n) = n \Rightarrow f(n).g(n) = \Theta(n)$$ $$g(n) = \frac{1}{n^2}, f(n) = n \Rightarrow f(n).g(n) = o(1) (\text{little-o})$$ $$g(n) = n, f(n) = n \Rightarrow f(n).g(n) = \Theta(n^2)$$

As we don't know about $f(n).g(n)$. However, we can say $f(n).g(n) + h(n) = \Omega(n)$ as $h(n) = \Theta(n)$ and $f(n).g(n) \geq 0$.

---
Tags: asymptotics
---


# Question
Title: Relation between Undecidable problems and NP-Hard
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.

And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)

# Answer
> 9 votes
I believe that this answer by Yuval Filmus all the questions you have asked.

> If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f\_i$ reduces SAT to $A$ in polytime, then $f\_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f\_i$ to get a polytime algorithm for SAT.
>
> We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f\_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f\_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.
>
> The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f\_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f\_i$ is infinite). We define $A$ on $f\_i(s)$ so that $s \in SAT$ iff $f\_i(s) \notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s \in A$ iff $|s| \in K$.
>
> By construction, no polytime $f\_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n \in K$ (for $n \geq 2$) by taking a majority of three strings of length $n$.

To summarize,

1. Halting problem is NP-hard.
2. If $P\ne NP$, not all undecidable problems are NP-hard.
3. If $P = NP$, all non-trivial sets are NP-hard.

The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.

> There is a problem which is both NP-hard and in coNP if and only if NP = coNP.
>
> If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.
>
> On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.
>
> The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.

So, assuming $NP \ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P \ne NP$).

# Answer
> 2 votes
Your second diagram seems to be claiming that (assuming $\mathrm{P}=\mathrm{NP}$), every $\mathrm{NP}$-hard problem that is not $\mathrm{NP}$-complete is undecidable. That's certainly not true. For example, by the time hierarchy theorem, we know that $\mathrm{NEXP}\supsetneq\mathrm{NP}$. $\mathrm{NEXP}$ is a set of decidable problems and it contains $\mathrm{NP}$-hard problems that are not in $\mathrm{NP}$.

---
Tags: complexity-theory, computability, undecidability, np-hard
---


# Question
Title: Time-space tradeoff for missing element problem
Here is a well-known problem.

Given an array $A\[1\dots n\]$ of positive integers, output the smallest positive integer not in the array.

The problem can be solved in $O(n)$ space and time: read the array, keep track in $O(n)$ space whether $1,2,\dots,n+1$ occured, scan for smallest element.

I noticed you can trade space for time. If you have $O(\frac{n}{k})$ memory only, you can do it in $k$ rounds and get time $O(k n)$. In a special case, there is obviously constant-space quadratic-time algorithm.

My question is:

> Is this the optimal tradeoff, i.e. does $\operatorname{time} \cdot \operatorname{space} = \Omega(n^2)$? In general, how does one prove such type of bounds?

Assume RAM model, with bounded arithmetic and random access to arrays in O(1).

Inspiration for this problem: time-space tradeoff for palindromes in one-tape model (see for example, here).

# Answer
> 2 votes
This can be done in $O(n \log n)$ word operations and $O(1)$ words of memory (respectively $O(n \log^2 n)$ time and $O(\log n)$ memory in bit-level RAM model). Indeed, the solution will be based on the following observation.

Say there are $n\_0$ even and $n\_1$ odd numbers in range $\[1, n + 1\]$ (so $n\_0 \approx n\_1$ and $n\_0 + n\_1 = n + 1$). Then there is $b \in \\{0, 1\\}$ such that there are at most $n\_b - 1$ values with parity $b$ in the input. Indeed, otherwise there are at least $n\_0$ even and at least $n\_1$ odd values in the input, meaning that there are at least $n\_0 + n\_1 = n + 1$ values in the input, contradiction (there are only $n$ of them). It means that we can continue searching for missing number only among the odd or even numbers only. The same algorithm can be applied to higher bits of binary notation as well.

So our algorithm will look like that:

1. Suppose that we already now that there are only $x$ values in the input with remainder modulo $2^b$ being equal to $r \in \[0, 2^b)$ but there are at least $x + 1$ numbers in range $\[1, n + 1\]$ that have remainder $r$ modulo $2^b$ (at the start we know that for sure for $b = 0, r = 0$).
2. Say there are $x\_0$ values in the input with remainder $r$ modulo $2^{b + 1}$ and $x\_1$ values in the input with remainder $r + 2^b$ modulo $2^{b + 1}$ (we can find these numbers in a single pass through the input). Clearly, $x\_0 + x\_1 = x$. Moreover, because there are at least $x + 1$ numbers in the input with remainder $r$ modulo $2^b$, at least one of the pairs $(r, b + 1), (r + 2^b, b + 1)$ satisfies the requirements of the step $1$.
3. We have found the missing number when $2^b \geqslant n + 1$: there is only one number in range $\[1, n + 1\]$ that may have remainder $r$ modulo $2^b$ ($r$ itself if it is in range), so there are at most zero values in the input that have such remainder. So $r$ is indeed missing.

Clearly, the algorithm halts in $O(\log n)$ steps, each of them needs $O(n)$ time (single pass over the input array). Moreover, only $O(1)$ words of memory are required.

# Answer
> 1 votes
If I understand your definitions, this can be done in linear time with constant space. This is obviously the lowest bound, because we need to at least read the entire input.

The answer given in this question satisfies.

It's impossible to run this with less time or space, and adding extra time or space is useless, so there's no space-time tradeoff here. (Observe that $n=O(n/k)$, so the tradeoff you observed doesn't hold asymptotically, in any case.)

In terms of your general question, I don't know of any nice theorems offhand which will help you prove space-time tradeoffs. This question seems to indicate that there isn't a (known) easy answer. Basically:

> Suppose some language is decidable in $t$ time (using some amount of space) and $s$ space (using some amount of time). Can we find $f,g$ such that $L$ is decidable by $M$ which runs in $f(t,s)$ time and $g(t,s)$ space?

is unknown, and a strong answer would solve a lot of open problems (most notably about SC), implying that no easy solution exists.

---

EDIT: Ok, with repetition (but I'm still assuming that with an input of size $n$ the maximum possible number is $n+1$).

Observe that our algorithm needs to be able to differentiate between at least $n$ possible answers. Suppose at each pass through the data we can get at most $k$ pieces of data. Then we will need $n/k$ passes to differentiate all answers. Assuming $k=n/s$ then we run in $\frac{n}{n/s}n=sn$ time. So I think this proves what you want.

The difficulty is in showing that each time through we get only $k$ bits. If you assume that our only legal operation is =, then we're good. However, if you allow more complex operations, then you'll be able to get more information.

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


# Question
Title: Understanding access and insertion time of arrays
Why do most implementations of arrays have constant access time and linear insertion time?

# Answer
> 3 votes
Because they are using the pointer to access to an index of the array, hence the access time is constant. Moreover, as indices of the array are stored beside each other (to access in constant time), insertion to the array needs to extend the allocated storage of the array to insert a value, and it needs to copy all values of the array to the newly allocated storage with size $n + 1$. Hence, insertion of the array is $O(n)$ in most of the implementations.

To know more about this, you can seek around "dynamic array" for constant access time and amortized $O(n)$ for $n$ insertion.

---
Tags: data-structures
---


# Question
Title: How does this use of "apply" in Coq work?
I'm working my way through software foundations. In the Chapter titled "Tactics", I'm able to prove this theorem in Coq:

> ```
> Theorem silly_ex :
>      (∀ n, evenb n = true → oddb (S n) = true) →
>      oddb 3 = true →
>      evenb 4 = true.
> Proof.
>   intros H1 H2. apply H2.
> Qed.
>
> ```

Even though I was able to get through the example, I don't understand how that is a solution. After performing `intros H1 H2` I'm left with proving that `evenb 4 = true`. The two hypotheses I have at this state are `H1 : forall n : nat, evenb n = true -> oddb (S n) = true` and `H2 : oddb 3 = true`.

How can `apply H2` solve this? Even knowing that 3 is odd doesn't fulfill the antecedent of the conditional.

# Answer
> 8 votes
You can ask Coq to show you its proof object. Before `Qed`, type `Show Proof.`

```
(fun (_ : forall n : nat, evenb n = true -> oddb (S n) = true)
   (H2 : oddb 3 = true) => H2)

```

As you can see, `H1` is not used at all, and the goal *is* `H2`.

It comes from the definition of `oddb` and `evenb`, the definition of `negb` and the definition of the natural numbers and the booleans.

> ```
> Definition oddb (n:nat) : bool := negb (evenb n).
>
> ```

* `oddb 3` is equal to `negb (evenb 3)` by the definition of `oddb` above.
* `evenb 3` is equal to `evenb (S (S (S O)))` by the definition of `3`. This is equal to `evenb (S O)` which is equal to `false` by the definition of `evenb`.
* Therefore `oddb 3 = negb false` which is in turn equal to `true` by the definition of `negb`.
* `evenb 4` is equal to `evenb (S (S (S (S O))))` by the definition of `4`. Applying the definition of `evenb` three shows that this is equal to `evenb (S (S O))`, to `evenb O`, and to `true`.

All of these equalities come from computation: if $x$ reduces to $y$ then $x$ is equal to $y$ — this is the most basic form of equality¹. The reductions above use the $\beta$ rule (applying a lambda term to an argument), the $\delta$ rule (replacing a name by its definition) and the $\iota$ rule (applying a recursive function `fix …` and simplifying pattern matching).

Coq has a large set of tactics to perform computations, though they're only needed in advanced cases. For example, after `intros H1 H2`, you can ask it to expand `evenb` and `oddb`, but do nothing else.

```
cbv delta.
cbv delta in H2.

```

Integers like `3` and `4` are syntactic sugar, not named constants. `3` is `S (S (S O))`, not just some term that reduces to it. If you want to see everything that's going on, turn off pretty-printing of notations.

```
Unset Printing Notations.

```

(Use `Set Printing Notations.` to turn them back on.)

You can watch the goal being reduced to its value.

```
cbn iota. cbn beta. cbn iota. cbn beta. cbn iota. cbn beta. cbn iota. cbn beta. cbn iota.

```

Of course you don't need to guide Coq so much, this is just if you want to see all the steps. You can simply ask Coq to compute as much as possible. Just after `intros H1 H2`, run

```
compute. compute in H2.

```

and you'll see that both `H2` and the goal simplify to `true = true`.

In this particular case there's no simpler way to go from `H2` to the goal than to fully calculate both. If you continue the tutorial a bit, you'll get to recursive proofs, where it's very common to have similar hypotheses and a similar goal, but with a variable instead of constants like `3`. There you would typically combine `H1` and `H2` together (but here `H1` is not particularly interesting — since you're proving something about `evenb`, you'd want the an implication of the form `oddb … -> evenb …` rather than `evenb … -> oddb …`).

¹ <sub> In a certain sense, it's the only form of equality. </sub>

---
Tags: coq
---


# Question
Title: Name for the tree formed after collapsing cycles
What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)? For instance, the digraph (given by an NFA; ignore edge labels please) below becomes a tree $\\{a,b,c,d\\}$ with edges $(a,b), (b,c), (b,d)$ via: \begin{eqnarray\*} a\mapsto&\text{the cycle }&S\_0,S\_1,S\_2,S\_3,S\_4,S\_5,S\_6,S\_7,S\_0 \\ b\mapsto &\text{the cycle }&S\_5,S\_6,S\_7,S\_8,S\_9,S\_{10},S\_{11},S\_{12},S\_5\\ c\mapsto &\text{the cycle }&S\_8,S\_9,S\_8\\ d\mapsto &\text{the cycle }&S\_{10},S\_{11},S\_{12},S\_{10} \end{eqnarray\*}

# Answer
For any given *undirected* graph $G$, the *cycle graph* $C(G)$ has vertices which correspond to the chordless cycles of $G$, and two distinct vertices of $C(G)$ are adjacent if and only if the corresponding chordless cycles have at least one edge in common. \[1\]

Judging from your example, you are interested in a similar notion for a directed graph.

\[1\] S.V. Gervacio. Cycle graphs. Lect. Notes Math. 1073, 279-293 (1984)
> 1 votes

---
Tags: graphs, automata, terminology
---


# Question
Title: Halting problem of TM which recognize recursive languages is undecidable?
I am preparing for an exam and I came across this question in one of the tests.

> Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)

The solution given says the statement its False.

But I think the statement is True. Halting problem in itself is undecidable. We can't determine whether the Turing Machine will halt or not.

The test series has a history of wrong answers that's why I am seeking an explanation even if I am wrong.

Edit: I was looking at the answers and I have trouble understanding the explanations. I know that 'By definition, recursive languages are decideable by Turing machines.' I will tell you how I breakdown the question. I am given a TM and told that this TM recognizes a recursive language. How do I know that the TM will halt?

# Answer
> 1 votes
By definition, recursive languages are decideable by Turing machines. Thus for recursive languages the TM will always halt.

# Answer
> 1 votes
If the task is to determine whether a given machine $M$ halts, when you already know that $M$s language is decidable then the answer is always "yes" because every TM that decides a language halts on every input (by definition of "to decide"). Hence, the halting problem on these kind of TMs is decidable.

However, if you want to determine whether the language $$A = \\{\langle M \rangle \mid L(M) \text{ is decidable}\\}$$ you can find an easy reduction that shows that $A$ is undecidable. I do not think this is the task but it was my first thought reading this question, so maybe it is still useful.

---
Tags: formal-languages, turing-machines, undecidability, compilers, turing-completeness
---


# Question
Title: Is it possible to write a program that calculates an algorithm's time complexity?
Title is self explanatory.

I have searched here on this site and haven't found any discussion about this.

Is it somehow related to Turing's Halting problem (which is undecidable)?

# Answer
> 4 votes
Yes, you are right. There is no program that can calculate all algorithms' time complexity.

More formally speaking, there is no Turing machine which, given any Turing machine $T$ and an input of length $n$, it can calculate a finite upper bound for the computation time that will be used by $T$ and that input in case that computation does halt, or infinity in case that computation does not halt. The reason is simple, as you have mentioned, there is no Turing machine that can decide whether an arbitrarily computation will run forever or not in the first place. In fact, we cannot algorithmically tell even whether a given Turing machine halts on the empty input.

Notice that a trivial time complexity of all algorithms is an upper bound of running forever for any input. There are also trivial lower bounds such as whether the computation will run for less than for 7 steps. Those trivial time complexities have to be excluded from our discussion so as to keep our discussion interesting.

We can ask refined questions. For example, does an arbitrary Turing machine run in time $O(1)$? It turns out this question is undecidable as well.

For more information, you may want to read *Verifying Time Complexity of Turing Machines* by David Gajser.

# Answer
> 1 votes
Yes, not possible. Halting problem can be reduced to this problem.

Let $L\_{com}=\\{\<M,n\>| M \ is \ a \ TM \ with\ n\ input \\}$ which is decided by $M\_{com}$. Then it can be shown that Halting Problem $D$ can be reduced to this problem.

Let $D = "On\ input\ \<M,w\>"$

* Encode/Map $w$ to unique number $n$ if $w$ is accepted by $M$ else make $n=-1$.
* Feed $\<M,n\>$ to $M\_{com}$, if complexity is positive accept otherwise reject.

Now, since we know Halting problem is undecidable and it is reducible to the problem of finding complexity of turing machine, the problem of finding complexity of turing machine is undecidable.

---
Tags: algorithms, complexity-theory, halting-problem
---


# Question
Title: Mean geodesic distance between two points in Delaunay Graph
If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes. I know that in a small world network, it is in O(log(N)), with N being the number of nodes.

Thank you!

# Answer
> 1 votes
As you have probably come to the right conclusion by now, for a Delaunay graph, the magnitude of the mean distance between two randomly chosen nodes depends on the particular configuration of the points.

Here is one extreme example. Let each one of the six sided of the triangulated honeycomb have $n$ edges. We will have $3n(n+1)+1$ points. The average distance between two nodes is $\Theta(n)$, which is $\Theta(\sqrt {3n(n+1)+1})$.

We can also consider the row of triangles just above the middle line in that honeycomb as a separate graph. It has $4n+1$ nodes. The average distance between two nodes is $\Theta(n)=\Theta(4n+1)$.

It is intuitive clear that for any given Delaunay graph of $N$ points, the mean distance between two nodes is between $\Theta(\sqrt{N})$ and $\Theta(N)$, which grows much faster than $O(\log(N))$, the mean distance between two nodes in a small-world network. That is one evidence why we call that kind of network small world!

---
Tags: graphs
---


title: n-DNF boolean formula k satisfiability

text:
# Question
Title: n-DNF boolean formula k satisfiability
Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0\<=k\<=2^n). Where input is infinite number of n tuples where repeating tuple is possible. For exampl. F(a,b) =ab + a'b. Input set is (11,00,11,01) and k=2. Answer is 3 here so decision says yes as 3\>k. Can i define this problem in more formal way and prove that it is np/npc/ anything else. I am looking for suggestions specially for infinite number of tuples. I am aware of npc and reduction stuffs but need help to classify this problem properly.

# Answer
Your problem can't be any easier than DNF-TAUTOLOGIES since that problem is produced by setting $k$ equal to $2^n$. Therefore your problem is NP-hard, just as DNF-TAUTOLOGIES is.
> 1 votes

---
Tags: complexity-theory, algorithm-analysis, np-complete, satisfiability
---


# Question
Title: What is the computational complexity of intuitionistic propositional logic?
Consider the decision problem: given formulas of propositional logic $\phi\_1, \ldots, \phi\_n, \psi$, determine whether $\phi\_1, \ldots, \phi\_n \vdash \psi$ intuitionistically. This problem is well-known to be decidable, for example using an algorithm derived from the LJT\* sequent calculus. I was wondering if the computational complexity of this problem is known.

Trivially, the complexity is polynomial-equivalent to the complexity of the intuitionistic tautology problem: $\phi\_1, \ldots, \phi\_n \vdash \psi$ if and only if $\phi\_1 \wedge \ldots \wedge \phi\_n \rightarrow \psi$ is a tautology; and conversely, $\phi$ is a tautology if and only if $\vdash \phi$. Certainly, the problem is co-NP-hard: as a corollary of the double-negation embedding, a formula $\phi$ is classically satisfiable if and only if $\lnot \phi$ is not a tautology of intuitionistic logic.

On the other hand, if I'm not mistaken, the problem is in PSPACE: the only rule of LJT\* which could possibly increase the total length of a proof context is in the first subgoal of $(\alpha, \beta \rightarrow \gamma, \Gamma \vdash \beta) \wedge (\gamma, \Gamma \vdash \delta) \implies (\alpha \rightarrow \beta) \rightarrow \gamma, \Gamma \vdash \delta$. But in that case, the second copy of $\beta$ should still be at most equal to the length of a formula in the original context.

(Also, since the Rieger-Nishimura lattice, the free Heyting algebra on one generator, has a simple computable description, the special case of this problem restricted to problems with a single atom would be in P. That would be a severe restriction, though.)

Beyond that, in a quick Google search, I didn't find any results directly on this problem, just a few papers where the abstracts seemed to indicate they were considering fragments of propositional logic. I also can't find any proof on my own which would refine the status. (For example, for all I know, it might be possible that whenever the sequent is not intuitionistically valid, there exists a Kripke model of polynomial size which demonstrates this - in which case the problem would be co-NP-complete. Or more generally, a Heyting algebra with a polynomial-size "description" would suffice. It's harder for me to imagine some way to reduce a problem such as QBF to an instance of this problem to prove it's PSPACE-complete, though I also can't entirely rule out the possibility.)

# Answer
A quick google search shows that the problem is PSPACE complete, a result apparently first proven by R. Statman.
> 3 votes

---
Tags: complexity-theory, propositional-logic
---


# Question
Title: Determine wether a set of sets contains a partition of a given set
Consider the following problem :

> Given a set of sets of integers, $\Sigma = \\{S\_i, i \in I\\}$, and a set G, determine wether $\Sigma$ contains a partition of G, i.e. a set $J \subseteq I$ such that $G = \bigsqcup\_{j\in J} S\_j$.

This problem is (if i'm not mistaken) in NP.

I'm trying to determine wether this problem is in P (Or maybe NP-complete).

* Do you know if this problem is treated anywhere in the litterature (Algorithm or NP Completeness) ?
* Do you know any problems that are close to this one ?

I have tried to design a polynomial algorithm for the problem, but nothing working so far.

# Answer
> 4 votes
Without loss of any really interesting aspect, we can assume that $S\_i\subseteq G$ for all $i\in I$. Otherwise, we can we can remove each $S\_i$ which is not a subset of $G$. This reduction step takes $O(ng)$ times, where $n=\sum\_{i\in I}|S\_i|$ and $g=|G|$.

Now that $S\_i\subseteq G$, this problem is the exact cover problem, which is one of Karp's 21 NP-complete problems. You can find all sort of information about it at its Wikipedia entry.

I have played briefly a game called Pentomino, which is an exact cover problem.

---
Tags: complexity-theory
---


# Question
Title: Approximation factor shorthand clarification
I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the *approximation factor*. I know that an approximation factor will give the factor within which the algorithm will perform with respect to the optimal solution. This is pretty easy to grasp for things like a 2-factor approximation. I've also seen other literature and lecture notes refer to $1-1/\epsilon$ when giving the probability and/or percentage of the optimal that will be returned (or, put another way, how "much" of the optimal an approximation algorithm will, well, approximate).

But I've seen some papers (like Linear-Time Approximation for Maximum Weight Matching) refer to a $1-\epsilon$ approximation ratio. For example:

> we give an algorithm that computes a (1 − ε)-approximate maximum weight matching

So my question is: are they referring to the $1-1/\epsilon$ ratio that I've been seeing elsewhere? Apologies if this is a simplistic question, I'm just getting starting in learning about these very-cool algorithms and am trying to get my head around which papers are presenting things that are extraordinary vs. not as competitive compared to the optimal solution. Thank you!

# Answer
> 2 votes
That article, Linear-Time Approximation for Maximum Weight Matching calls "a matching $\delta$-approximate, where $\delta \in \[0, 1\]$, if its weight is at least a factor $\delta$ of the optimum matching."

That $\delta$-approximate maximum weight is, in fact, similar to the 2-factor approximation that is easy for you to grasp. When the optimization problem is to minimize some (positive) quantity, such as the minimum traveling distance or minimum vertex cover, then a 2-factor approximate might appear. When the optimization problem is to maximize some (positive) quantity, such as the case here, then a $(1-\frac15)$-factor approximate might be expected.

You may want to take a look at the *performance guarantees of approximation algorithm* or even *what is a bicriteria approximation algorithm?*

---
Tags: algorithms, algorithm-analysis, approximation
---


# Question
Title: What is the optimal way to perform GCD chain operation?
**Matrix chain multiplication problem:-** Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming.

Similarly

**GCD chain operation is defined as:-** Given a set of $n$ integers, what is the most efficient way to find the gcd of all the elements?

The cost is the number of GCD(x,y) invocations done by a binary GCD algorithm.

**Basic attempt at solving the problem is:-** GCD$(a\_1,a\_2,a\_3,a\_4,\ldots a\_n)$

{

$k=GCD(a\_1,a\_2)$.

if ($k=1$)

return 1;

else

return $GCD(k,a\_3,a\_4\ldots a\_n)$;

}

In simple terms, it keeps finding the gcd of the smallest two among all the $n$ elements and then recurse, by replacing the two elements with their gcd which is at most the smallest element in the input.

---

Make suitable assumptions if necessary. For example you can assume that the integers are given in sorted order.

**Assume GCD is computed using a binary GCD algorithm** (other GCD algorithm is also fine) aka

$GCD(a,b)= GCD(a-b,b)$

$GCD(2a,2b)=2GCD(a,b)$

and $GCD(a,2b)=GCD(a,b)$ (if $a$ is odd)

GCD(75,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 3

GCD(125,25)=GCD(100,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 4

GCD(179,25)= GCD(154,25)=GCD(77,25)=GCD(52,25)=GCD(26,25)=GCD(1,25)=1

Number of steps is 6

---

A heuristic strategy mentioned in the basic attempt above is not optimal for the following example

GCD(25,75,125,179,181,225)

= GCD(GCD(25,75),125,179,181,225) (3 steps)

=GCD(GCD(25,125),179,181,225) (4 steps)

=GCD(GCD(25,179),181,225) (6 steps)

=1

This required 13 invocations of GCD(x,y) function.

But the optimal strategy would be to see that 179 and 181 have gcd 1 and therefore the solution is 1, which requires computing only 1 bivariate gcd.

GCD(179,181)=GCD(179,2)=GCD(179,1)=1

which takes 3 invocations of GCD(x,y) only

I am not sure if there exists an optimal way to do it, or maybe it is NP hard to find a solution which makes the least number of GCD(x,y) calls.

# Answer
> 1 votes
You are saying that you will perform n-1 gcd operations, unless you find k numbers with a gcd of 1 by performing k-1 gcd operations.

Since you don't know which set of numbers has a gcd of 1, you can't pick a set with gcd 1. Your total time depends on the data you have.

You can try to process small numbers first, because the gcd of small numbers tends to be calculated quicker than the gcd of large numbers.

The optimal strategy will not always lead to the best outcome. I put a deck of cards on the table, face down, and ask you to pick the ace of hearts. Do you think "pick the ace of hearts" is the optimal strategy? No, it isn't a strategy that you can enforce since you don't know which one is the ace of hearts.

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


# Question
Title: Must $x$ and $y$ be different in a statement of the form $\forall x \forall y \cdots$?
Given the following predicate formula $F$:

$$\forall x \forall y \[(\text{italian}(x) \Rightarrow (\text{winWC}(y) \Rightarrow \text{happy}(x))\]$$

I am having trouble understanding whether $x$ and $y$ must be different elements.

Also, I have been given the following statement:

> "Italians are happy if the Italian National team wins the world cup."

How can I prove that this is not equivalent to what is expressed by $F$? Should I bring both in CNF and then somehow argue they cannot be equivalent?

# Answer
For any formula $\varphi$ in which $x$ and $y$ are free variables, $\forall x \\\> \forall y \\\> \varphi$ quantifies over all possible values for $x$ and $y$. As a result, $x$ and $y$ *may* be different objects or they *may* be equal; for the statement to hold, $\varphi$ must hold in *both* cases.

Following this reasoning, a valid interpretation for your formula would be "an Italian is happy regardless of who wins the World Cup" (assuming "WC" stands for "World Cup"), with "Italian" standing for $x$ and "who" for $y$. Thus, $x$ is happy if they win the World Cup ($x = y$) but also happy if someone else does ($x \neq y$); hence "regardless".

---

The other statement can be expressed in predicate logic as follows: $$\forall x (\text{italian}(x) \to (\text{winWC}(x) \to \text{happy}(x)))$$

In fact, this evaluates to the same truth value as the first formula precisely when you pick the same values for $x$ and $y$.

Assuming the most reasonable domain (i.e., persons in the world) and interpretation in this setting, you could argue there is an Italian which is happy only if the Italian national team wins the World Cup and is unhappy otherwise. Pick this person as your value for $x$ and an arbitrary non-Italian (e.g., German) person for $y$; then the second formula evaluates to true under this variable assignment (since $\text{italian}(x)$ is true and $x$ is happy if $\text{winWC}(x)$, that is, the Italian national team wins), but the first evaluates to false (since $x$ is unhappy if $y$'s team, that is, the German national team wins).
> 2 votes

# Answer
For all means for *all*. If you want to say that "for all distinct $x$ and $y$ property $P$ holds", your formula needs to include a formula that enforces distinctness. $$\forall x\\,\forall y\\,(x\neq y\rightarrow P(x,y))\\,.$$ (Note: not $\forall x\\,\forall y\\,(x\neq y\land P(x,y))$, which is false because it's not true that $x=y$ for all $x$ and $y$ unless there's only one element in the domain.)

However, in your example, distinctness is probably implied by the intended semantics. I assume that $\mathrm{italian}(x)$ is true only if $x$ is an Italian person, and $\mathrm{winWC}(y)$ is true only if $y$ is a country that has won the World Cup. Since people and countries are different things, it will never be the case that $x=y$ when $\mathrm{italian}(x)$ and $\mathrm{winWC}(y)$ are both true.
> 1 votes

---
Tags: logic, first-order-logic, predicate-logic
---


title: Minimum Distance Spanning Tree Dijkstra

text:
# Question
Title: Minimum Distance Spanning Tree Dijkstra
I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below:

MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)}

Is my understanding correct? The total cost would be 49 (sum of the distance from the root for each node).

# Answer
> 2 votes
Like other have pointed out, it seems you are confused by the difference between a minimum spanning tree, and a shortest path tree.

A minimum spanning tree, is a tree such that it spans all vertices, and the sum of all edges is as minimum as possible.

A shortest path tree, is a rooted tree such that the distance between the root, and any other vertex is as minimum as possible. (That doesn't necessary mean that the sum of its edges has to be minimum as possible).

# Answer
> 1 votes
What you are computing is typically called a *shortest-path tree*; yours is rooted at $a$. Note that, in this example, the shortest-path tree rooted at $a$ is not unique. You could have taken the edge $(d, e)$ instead of $(a, e)$.

---
Tags: graph-traversal, minimum-spanning-tree, spanning-trees
---


title: Converse of halting problem

text:
# Question
Title: Converse of halting problem
It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is undecidable for some computing apparatus, then it is Turing-complete?

# Answer
Here's an artificial counterexample:

Define an apparatus "aTM" like a TM, except that any input word which does not start with the symbol $a$ is immediately rejected. For words which do start with $a$, the TM is run as usual (and can accept/reject as usual).

This is clearly not Turing complete since it can't recognize the language $\\{b\\}$, which is decidable by a TM. Still, the halting problem on aTMs is as hard as the halting problem for TMs.
> 2 votes

# Answer
You can think of weaker model for example finite-state automaton, or a turing machine with space bound of $O(n)$. this models are not turing-complete and can't decide halting problem.
> 0 votes

---
Tags: computability, halting-problem
---


title: Why isn't chess an impartial game?

text:
# Question
Title: Why isn't chess an impartial game?
In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games. To be impartial, a game must satisfy these conditions:

(1) The game is finite; i.e. there is a constant $c$ such that all games end in $c$ moves or fewer.

(2) There are no draws; either player 1 or player 2 wins.

(3) The rules of the game draw no distinction between the players. That is, given any position, if we switch the active player then the set of legal moves is still the same, and the player who wins the game under perfect play switches.

It is often said in introductory CGT resources (here for example) that a major class of games that violate condition (3) are those in which each player has their own piece set. For example, chess violates (3) because the white player can only move the white pieces and the black player can only move the black pieces, so if we switch the active player then the set of legal moves changes.

However, it seems to me that this problem can be circumvented by the following trick. Instead of defining a "position" as the locations of the white and black pieces, we define a position as the locations of the active player's pieces and the passive player's pieces. Now the conditions in (3) are satisfied.

This trick seems too simple to be original, though, and I have read in many places about how chess is a classic example of a partisan game. So what am I missing?

Aside: To circumvent (1) and (2), we need to modify chess in some reasonable way; i.e. forbid 3x repetition of a single position and declare stalemate to be a win for the stalemating player. But that's beside the point of my question.

---

Years-later edit since this question has gotten some random attention lately: neither of the answers really understood the point of the question (which is probably my fault for an unclear OP). My current understanding is that there is indeed a natural **isomorphism** between finite drawless chess and an impartial game, but impartiality is not a property that is always preserved under isomorphism, and my misunderstanding came from the assumption that it was.

# Answer
> 3 votes
Yes, I believe your changes turn chess into an impartial game. As you mention, stalemate and three-fold repetition can be dealt with by declaring loss.

Your trick decouples players (P1 and P2) from the player to move in the position (White or Black). If the two players play chess in isolation, then those two properties will be in perfect sync. The problem is that CGT allows combining games. Imagine adding chess and checkers. This means that every player on their turn picks either a chess move or a checkers move. Suppose P1 makes a chess move with White, and P2 makes a checkers move. Then P1 can make a chess move with Black! There is no longer a correspondence between the people and the colors on the board.

In a sense, your game has no fixed White and Black; we might as well say that White is always to move, and after each turn we rotate the board and swap colors. There is no real ownership of pieces. This clearly satisfies criterion (3).

I don't know the theory of partisan games, but it's clear that if you didn't remove the "partisanness" from chess, you could form a chess + checkers sum where you can move pieces with only one color.

If you identify a game by its graph of legal move histories, then your chess and normal chess are the same (modulo draws). If you think of the game as a set of rules, and consider games as "first class functions" that can be combined, then they are different.

# Answer
> 6 votes
Chess violates all three conditions, so I don't really understand what there is to ask.

(1) The game is not finite. Although the 50-move and threefold repetition rules *allow* a player to end the game under certain circumstances, they do not *oblige* the player to do so.

(2) The game has draws.

(3) As you have observed, the game definition distinguishes between the players. Your "active player" trick doesn't work because you've turned chess into a one-player game: the "active" player makes every move and the "inactive" player is a spectator.

# Answer
> 3 votes
*"To be impartial, a game must satisfy these three conditions".*

My understanding is that what makes a game impartial or partisan is purely a function of whether or not the same plays are available to both players.

Chess is partisan because there are black and white pieces, and players can only move their own color.

The other two conditions listed are not a categorization of impartial games, but a definition of a particular game being analyzed. (This can be very confusing to those outside this still woefully obscure, but very important, field.)

In most CGT papers, the scholars begin by defining "what is a game". It is meant to apply only to the specific game being analyzed, and is never meant to be taken as a general definition of games, or combinatorial games, in general.

Fraenkel provides a very clear definition of several aspects of combinatorial games here: Infinite cyclic impartial games

---

Note: I think the confusion here derives from how mathematicians define games in research papers: "A game is..." or "An impartial game is..." The idea is they are defining the term in regard to the game they are analyzing, and it's not meant to be universal definition. This creates a lot of confusion for people outside the field, and, having read widely on the subject, "impartial" as a general term is not well defined. (This terminological fuzziness is irrelevant in regard to the validity of the mathematical work, and seems only to be a taxonomic issue.)

# Answer
> 0 votes
It seems you're stuck on the idea that "indirecting" by alternating who is the active player somehow gets around restriction 3. One way to see that this is unlikely to be true is that the same trick "works" to get around restriction 3 for *every possible game*, meaning that restriction 3 is in fact not a real restriction at all, which prompts the question: Why would someone have included it in the definition in the first place? (We may as well add some more redundant restrictions to the definition, e.g.: "(4) The name of the game has an even or an odd number of letters".)

It could alternatively be that your trick works, *and* nobody in the field of combinatorial game theory so far noticed that condition 3 is completely redundant.

---
Tags: combinatorics, game-theory, board-games
---


title: Balanced based representation

text:
# Question
Title: Balanced based representation
I'm interested in balanced base $B$ representation for fixed point arithmetic. The paper *Fixed-point arithmetic in SHE schemes* (Costache, Smart, Vivek and Waller, in *Proceedings of 23rd International Conference on Selected Areas in Cryptography (SAC 2016)*, Springer *Lecture Notes in Computer Science*, vol. 10532, pp. 401–422, 2016; PDF) provides two examples using balanced based $B=3$. However, I don't understand the 2nd second representation, i.e. $$\frac{8}{3}=10.\bar{1} $$ where $\bar{1}=-1$. More generally speaking, I'm also interested in balanced form representation $B=5, 7$. I believe this should be a well-known problem, though I was not able to google it. Do you know some relevant literature to this?

# Answer
> 2 votes
$$\frac{8}{3}=3 - \frac13=1\cdot3^1 + 0\cdot3^0 +(-1)\cdot3^{-1}=(10.\bar{1})\_3$$

Since $\frac83$ is not equal to $\dfrac p{5^i}$ for any integer $p$ and $i$, it cannot be expressed as a fixed-point balanced base-5 number. Instead, infinite periodical fraction part has to be used, where $\bar2=-2$.

$$\frac{8}{3}=5-2+\frac{-2}5+\frac2{25}+\frac{-2}{125}+\frac2{625}+\frac{-2}{3125}+\frac2{15625}+\cdots=(1\bar2.\bar{2}2\bar{2}2\bar{2}2\cdots)\_5$$

Let us see it step by step.
$\frac{8}{3}\approx5$
$\frac{8}{3}-5=\frac{-7}3\approx -2$
$\frac{8}{3}-(5-2)=\frac{-1}3\approx \frac {-2}5$
$\frac{8}{3}-(5-2+\frac{-2}5)=\frac15\frac{1}3\approx \frac15\frac {2}5$
$\frac{8}{3}-(5-2+\frac{-2}5+\frac15\frac25)=\frac15\frac15\frac{-1}3\approx \frac15\frac15\frac {-2}5$
$\frac{8}{3}-(5-2+\frac{-2}5+\frac15\frac25+\frac15\frac15\frac{-2}5)=\frac15\frac15\frac15\frac{1}3\approx \frac15\frac15\frac15\frac {2}5$
$\frac{8}{3}-(5-2+\frac{-2}5+\frac15\frac25+\frac15\frac15\frac{-2}5+\frac15\frac15\frac15\frac25)=\frac15\frac15\frac15\frac15\frac{-1}3\approx \frac15\frac15\frac15\frac15\frac {-2}5$
$\vdots$

You can work out the the balanced base-7 number with periodical fraction for $\dfrac 83$.

For the case of base 3, you can take a look at balanced ternary at Wikipedia.

# Answer
> 2 votes
The expression $10.\overline{1}$ should be interpreted as follows: $$ 1 \cdot 3^1 + 0 \cdot 3^0 + (-1) \cdot 3^{-1} = 3 - \frac{1}{3} = \frac{8}{3}. $$ The interpretation of balanced base $b=2d+1$ is the same, with the digits ranging from $-d$ to $d$.

---
Tags: numeral-representations
---


# Question
Title: How to decrease the confidence of a Monte Carlo algorithm in its answer?
Recall that a Monte Carlo algorithm is $p$-correct if it outputs a correct answer with probability at least $p$. In the case of decision problems, where the answer is binary, repeating the MC algorithm can increase the confidence that a correct answer is obtained.

However, in the case where more than 1 possible answer is correct, this confidence can actually decrease. I'm wondering how many times $k$ does such an algorithm have to be run to obtain a confidence in the answer that is less than 50%.

Here's what I've done:

Suppose that $k=3$ and I have a 75%-correct MC algorithm that outputs 5 possible answers, 4 of which are right, and 1 is wrong. I think in this case, the 75% "correctness" of the algorithm is split between all possible right answers, such that each correct answer has a "probability" of 75%/4.

Suppose the right answers are $a, b, c, d$ and a wrong answer is $e$.

In this case, if I list all possible combinations of outputs of an MC algorithm that I run $k=3$ times, I get a list of tuples $(a, a, a)$, $(a, a, b)$... and so on, each of which is associated with a probability of occurring. So for instance $(a, a, a)$ has probability $(0.75/4)^3$ of occurring and $(a, a, e)$ has probability $(0.75/4)^2 * 0.25$.

So if I build a table associating each possible tuple to its probability of occurring, and sum the probabilities of all events where the algorithm would output the correct answer by majority voting (ties are split by choosing randomly), this should give me the final "confidence" of the algorithm. In this case, I get numbers around 0.65-0.75 (because of the randomness in tying splits).

However, I haven't been able to find a $k$ that gets this value to below 50%.

Any ideas if I'm doing something wrong? Help is much appreciated.

# Answer
> 1 votes
You can compute the probability that outcome $e$ is the unique plurality answer, when repeating the algorithm $k$ times, as follows: $$ \sum\_{\substack{a+b+c+d+e=k \\ a,b,c,d,e \geq 0 \\ e \> a,b,c,d}} \frac{n!}{a!b!c!d!e!} \left(\frac{1}{4}\right)^e \left(\frac{3}{16}\right)^{k-e}. $$ This can be computed explicitly. When $k = 70$, the probability is roughly $0.502$, and this is the minimal $k$ for which the probability exceeds $1/2$.

---
Tags: monte-carlo
---


title: Big O analysis trying to follow a logic

text:
# Question
Title: Big O analysis trying to follow a logic
Can someone please help me understand why(the derivation) "**and m = 2n+1 for each n.**"? I am trying to follow the logic of the solution provide while myself have a different approach. Here is my thinking (questions state below):

The inner for loop runs m times from 1 and the outer for loop runs n times from 1. Moreover, for each inner loop, m is increased by 2 based on previously additions and m starts at 1. With all these observations, plug in n = 1, print (j) get executed 3 times; n = 2, print(j) get executed 8 times. n = 3,print(j) get executed 15 times. We calculate the sequence to be 3,8, 15..... which has the closed form as 2 n +$ n^ 2$ . Or by asymptotic run time as Θ( $n^2$ )

```
  fun(n)
       m = 1
       for i = 1 to n
          m = m + 2
          for j = 1 to m
             Print(j)

```

Solution: The assignment m=1 takes constant time. The line m = m + 2 is run n many times, which takes Θ( n ) time. The inner print statement runs m many times, **and m = 2n + 1 for each n**. The total number of times the print statement runs is  Can someone please help me understand why(the derivation) "**and m = 2n+1 for each n.**"? How can we draw the connections with "the line m = m+2 is run m many times.." and "the inner print statement runs m many times" to get "and m = 2n+1 for each n."?

# Answer
> 0 votes
Possibly it's not for each $n$, but for each $i$.

First, try to calculate $m$ for each specific $i$:

```
 i | m
-------
 1 | 3
 2 | 5
 3 | 7
 4 | 9
   :
 n | 2n+1

```

$m$ increased by two for each loop of `for i = 1 to n`. Therefore $m = 2i+1$ for each $i$ in the loop.

And this is repeated from $i = 1$ to $i = n$, so in total,

$$ \sum\_{i=1}^n (2i + 1) = n^2 + 2n $$

---
Tags: complexity-theory, algorithm-analysis, asymptotics
---


title: Modular exponentiation in P

text:
# Question
Title: Modular exponentiation in P
I need to prove that the following language is in $\mathsf{P}$: $$ L = \\{\langle x,y,z,d \rangle : xˆy \equiv z \pmod{d}\\}.$$

I'm assuming I just have to prove with an algorithm or negate that it's part of NP. But I don't know how to do it with this mathematical formula.

# Answer
First of all, anything in $P$ is also in $NP$, so proving that it's not in $NP$ will be an exercise in futility. I'm also going to change your variable names a bit to make them clearer; the letters I use stand for **b**ase, **e**xponent, and **m**odulus.

What you seem to be looking for is a *modular exponentiation* algorithm. In other words, a way to compute $b^e \mod m$ in polynomial time. Several of these exist, but here's the simplest one I know of:

```
function modular_exponent(b, e, m):
    z ← 1
    b ← b % m
    for i ← 1..e:
        z ← (b × z) % m
    return z

```

The number of multiplications and modulus operations we do is linear in $e$, and the operands to those operations are never larger than $m$. So the runtime is $O(e (\log{m})^2)$ (assuming multiplication runs in log-squared and modulus runs in logarithmic time; in practice you can make this even a bit more efficient using something like Karatsuba multiplication, but that doesn't matter for this problem).

This is clearly a polynomial runtime, so the modular exponentiation decision problem ("for given $b, e, m, z$, is $b^e\cong{}z \mod m$?") is in $P$.
> 3 votes

---
Tags: complexity-theory, number-theory
---


# Question
Title: Complexity of a set partition derived problem
I am stuck at the complexity of the following problem: Given a multiset $S = \\{x\_1,..., x\_n\\}$ of $n$ integers and a natural number $k$. Can $S$ be partitioned into multisets $S\_1,... S\_j$ such that for all $S\_i \subseteq S$ there is $\sum\_{ s \in S\_i} s = k?$

I have found out that this may be somehow related to the EqualSubetSum Problem or the partition problem. But is this problem really $NP$-complete or exists a polynomial algorithm depending on $k$ and $n$ to decide this problem?

# Answer
> 2 votes
A set is a multiset (in which every element occurs once) and your partition problem can be used to find a subset of $S$ whose sum is $k$. \[Note 1\] So if there were a polynomial-time solution to your partition problem, it could easily be used to solve the subset sum problem in the same amount of time.

So the problem is NP-complete, but that doesn't stop it from having a *pseudo*-polynomial time solution. There are well-known DP algorithms to solve the subset sum problem which are polynomial in the *magnitude* of the inputs. Time complexity is always expressed as a function of the *size* of the inputs, as measured (for example) by the number of bits it takes to represent the input. The magnitude of a number is exponential in the size of the number (eg, a number represented in 100 bits could be as large as $2^{100}$). So time complexity polynomial in magnitude is still exponential in problem size.

In your problem, $n$ is a measure of problem size, whereas $k$ only measures numeric magnitude. So they are very different kinds of parameter.

Here's another longer explanation of pseudo-polynomial time in a StackOverflow answer.

---

### Notes

1. Let $S$ be a set for which we seek a subset whose sum is $k$. Without loss of generality, we can assume that $\Sigma S \le 2k$ (because a solution for $k' = \Sigma S - k$ leads directly to a solution for $k$ using the set difference from $S$.) If $\Sigma S = 2k$ then a solution to the multiset partition problem yields two solutions to the subset sum problem. Otherwise, we form the multiset $S' = S \cup \\{2k - \Sigma S\\}$. Obviously, $\Sigma S' = 2k$ and the element we added has a value less than $k$. We then compute the multiset partition of $\langle S', k\rangle$, which must be a partition into two pieces, at most one of which is a multiset (because there is at most one repeated element in $S'$, the one we added). If the first subset in the partition does not include the element we added, it is a solution to the original problem; otherwise, the second subset is.

Computing $\Sigma S$ and examining the result of the multiset partition solution are both linear time. So if the multiset partition algorithm were polynomial time, so would be the derived subset sum algorithm.

---
Tags: complexity-theory, partitions
---


# Question
Title: Turing Machine for $\{w\# w ' |$ where $w < w'$ lexicographically, and $w,w'\in \{0,1\}^* \}$
I am blocked with this question for a long time.

$L = \\{w\\# w ' |$ where $w \< w'$ lexicographically, and $w,w'\in \\{0,1\\}^\* \\}$

I am trying to find

1. A Deterministic Turing Machine for L.
2. A Non-Deterministic Turing Machine for L.

**Example**

* $01\\#111 \in L$ since $ w=01$ and $w=111$ and $01 \< 111$
* $1\\#011 \notin L$ since $ w=1$ and $w=011$ but $1 \not\< 011$

For the deterministic TM, I have an idea only when $|w|=|w'|$, it's only comparing $i^{th}$ symbol in the first string with $i^{th}$ symbol in the second string, but I don't know how to solve it when we have two different length.

Please help me in solving this.

**Note**
$w\<w'$ lexicographically. As example, $0\<1\<00\<01\<000\<001.........$
When length of string are same, we compare their $ASCII$ Value $(0\<1)$, from Left to Right $(00\<01)$, else string of shorter length is always less than large one $(1\<000)$.

# Answer
> 0 votes
Here is a sketch of a construction method of the TM:

* Compare bit by bit from the first bit to the last bit as normal. If equals, proceed to the next bit. Otherwise, it can decide the order.
* If the head of TM reaches the word separator $\\#$ or the blank symbol (say $\\$$ or something), finish the comparison. If both words end simultaneously (i.e. when $\left| w \right| = \left| w' \right|$), then $w = w'$. If not, the shorter word is less than the other in the lexicographic order.

This idea is the same for both a deterministic TM and a non-deterministic TM. Only a non-deterministic TM can compare bits in a non-deterministic way.

# Answer
> -1 votes
First, you can compute $|w|$ and $|w'|$. For the minimum between of them, proceed with your algorithm, comparing bit by bit. If they equal for all the bits, the longer one is the "greater" and then you can decide if the given word belongs to $L$.

---
Tags: formal-languages, turing-machines, automata, binary, comparison
---


# Question
Title: Multiple rounds of bipartite matching problem
I have a set of investors (say n), and a set of startups (say m). At the start, I have all the investors say either yes or no to the startup (which corresponds to whether they want to interact with them or not).

Now, I have to conduct a networking event of r rounds considering this scenario. In each round, I match investors with startups they want to meet (one investor with one startup). I want to conduct the rounds such that the sum of the startups they met, across all investors, is maximum.

Now, if r=1, this reduces to the maximum bipartite matching problem. Does anyone have any ideas on how to solve this for r\>1? I have been thinking along the lines of having the source and sink edge capacities to be r instead of 1, but I am unable to prove that this works.

# Answer
> 2 votes
You can solve this by a mild extension of the standard reduction to network flow: increase the weight of the edges touching the source and the sink to $r$. Any integer flow corresponds to a union of $r$ matchings:

* An integer flow corresponds to a bipartite graph of maximum degree $r$.
* We can complete this bipartite graph to an $r$-regular bipartite graph by adding vertices and edges:
    1. Add vertices so that both sides have the same number of vertices.
    2. If the graph is not $r$-regular, then there must be two vertices $x,y$ (one on each side) with degree less than $r$. Add $r$ new vertices $x\_1,\ldots,x\_r$ and $y\_1,\ldots,y\_r$ to each side (respectively), and connect all of them except $x\_1$ and $y\_1$. Connect $x$ to $y\_1$ and $y$ to $x\_1$. This reduces the overall deficiency of the graph $\sum\_v (r - \deg(v))$ by 1.
* Repeated applications of Hall's theorem shows that the new graph can be decomposed into $r$ perfect matchings.
* Restricting these matchings to the original vertices and edges, we obtain a union of $r$ matchings.

Schrijver mentions this problem in his Combinatorial Optimization (Vol 1):

> **Corollary 21.4b.** *Let $G = (V,E)$ be a bipartite graph and let $k \in \mathbb{Z}\_+$. Then the maximum size of the union of $k$ matchings is equal to the minimum value of $k|V \setminus X| + |E(X)|$ taken over $X \subseteq V$.*

This follows by an application of the min cut max flow theorem.

---
Tags: graphs, bipartite-matching
---


# Question
Title: Push two symbols to stack at once in a push down automata
I am pretty new to PDAs and I was solving a problem which asked to design a PDA for the following: $a^n b^{2n}$.

The transitions on the PDAs I've encountered so far have pushed only one symbol onto the stack at any time. Can we push two symbols? Eg: for every $a$ I encounter I push two symbols. Thus, the transition will be:

$\Delta(q\_0, a,0;000) \to \Delta(q\_0)$
where "$a,0;000$" indicates pushing two zeroes onto stack for every $a$ that it encounters.

# Answer
There are some options (from comments):

* By some definition of PDA, you can push a string $w \in \Gamma^\ast$, where $\Gamma$ is the stack alphabet. (from abc's comment)
* Even if you could push only one symbol per transition, you could modify your PDA to push the first -\> move to a new state -\> push the second -\> continue as usual. (from chi's comment)
* The third option is to use multiple stack symbols encoding different things. (from Raphael's comment)
> 3 votes

# Answer
Just push 2 *a* in the stack for each *a* you see on the input, then pop 1 *a* for each *b*.
> 0 votes

# Answer
Here, the number of $b$s is twice the number of $a$s, so we have to push the $a$s in stack first. Once we start encountering $b$s, we transition on the first $b$ (but put nothing on the stack, just move to next state). After reaching the second $b$, pop the top $a$ as we transition on that $b$.

$z(q\_0,a,z\_0)\to(q\_0,az\_0)$

$z(q\_0,a,a)\to(q\_0,aa)$

$z(q\_0,b,a)\to(q\_1,a)$

$z(q\_1,b,a)\to(q\_2,E)$

$z(q\_2,b,a)\to(q\_1,a)$

$z(q\_2,E,z\_0)\to(q\_f,z0)$
> -1 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Can product DFA for intersection of two disjoint languages be minimal?
I know that it isn't necessary that cross product automaton for two minimal DFAs be minimal, but according to my analysis, if two DFAs do not have any common string then their cross product of minimal DFAs would be minimal. What should I do to prove this?

# Answer
> 3 votes
No.

Counterexample:

Let alphabet $\Sigma = \left\\{ 0, 1 \right\\}$, languages $L\_1 = \left\\{ w0 \\,\middle|\\, w \in \Sigma^\ast \right\\}$ (i.e. the last digit is $0$), $L\_2 = \left\\{ w1 \\,\middle|\\, w \in \Sigma^\ast \right\\}$ (i.e. the last digit is $1$). Note that $L\_1 \cap L\_2 = \emptyset$.

Then the following DFAs $M\_1$ and $M\_2$ are minimal for $L\_1$ and $L\_2$ respectively:

And the cross product of $M\_1$ and $M\_2$ (for the intersection of languages) is:

But this is not minimal for the empty language. A minimal DFA for the language is:

In fact, cross-product DFA of $M\_1$ and $M\_2$ recognizes an intersection of languages $L(M\_1) \cap L(M\_2)$ (if a state of cross-product DFA is accepting when the original two states are both accepting on original DFAs). So in this case a generated cross-product DFA always recognizes the empty language. Since a minimal DFA for the empty language has only one state and cross-product DFA has ((#states of $M\_1$) × (#states of $M\_2$)) states, almost all cross-product DFAs are non-minimal.

Also, even though if you define a state of cross-product DFA is *accepting* when **either** of the original two states is accepting, the above $(L\_1, L\_2)$ is a counterexample. Since $L\_1 \cup L\_2 = \Sigma^\ast$, the minimal DFA has only one state.

# Answer
> 2 votes
No, the Cartesian product (a.k.a. cross product in the question) of two minimal automaton may not be minimal.

Here are two simple counterexamples.

Note that a DFA with only one state will either accept all words if its start state is also an accept state or accept no words otherwise.

Let alphabet $\Sigma = \left\\{ a\right\\}$. Let $E$ be a minimal DFA such that $L(E)$ is not empty nor all words. The number of states in $E$ must be greater than 1. Let $O$ be a minimal DFA such that $L(O)$ is the complement of $L(E)$. The number of states in $O$ must be greater than 1.

An automaton $P$ which is an Cartesian product automaton of $E$ and $O$ must have at least 2x2=4 states.

Suppose $P$ is constructed for the intersection of $L(E)$ and $L(O)$, i.e. the empty language. Its equivalent minimal DFA has 1 state, the start state, which is not an accept state.

Suppose $P$ is constructed for the union of $L(E)$ and $L(O)$, i.e., $\\{a\\}^\*$. its equivalent minimal DFA has 1 state, the start state, which is also an accept state.

---

Please note the Cartesian product automaton of two DFA is not defined uniquely usually since it is allowed to choose different sets of accept states. This is the implicit view as in the book *Introduction to the theory of computation* by Michael Sipser.

# Answer
> 1 votes
Let $Q\_A,Q\_B$ be the number of states in $A,B$, respectively. The number of states in the product automaton is $Q\_A Q\_B$. Since $L(A) \cap L(B) = \emptyset$, the minimal automaton for $L(A) \cap L(B) = \emptyset$ contains a single state. This can only happen if $Q\_A = Q\_B = 1$, in which case $A,B \in \\{ \emptyset, \Sigma^\* \\}$. We conclude that the product automaton is minimal exactly in the following three cases:

1. $A = B = \emptyset$.
2. $A = \emptyset$, $B = \Sigma^\*$.
3. $A = \Sigma^\*$, $B = \emptyset$.

---
Tags: finite-automata
---


# Question
Title: Direct edges of undirected graph so that all indegrees are even
Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even.

For example, consider a graph which has the edges 1-2, 1-3, 2-4, 3-4. We can direct it as 1→2, 1→3, 2←4, 3←4, so indegrees of 1,2,3,4 are respectively 0,2,2,0, which are all even.

Which method or algorithm is suited for least time complexity? M and N are between 1 and 100,000.

# Answer
Orient all edges in an arbitrary fashion, and add a $0/1$ variable $x\_{u,v}$ for each edge $(u,v)$, with the following meaning: $x\_{u,v} = 0$ means that we use the orientation $u \to v$, and $x\_{u,v} = 1$ means that we use the orientation $u \gets v$. The parity of the indegree of $u$ is equal to $$ \sum\_{(u,v) \in E} x\_{u,v} + \sum\_{(w,u) \in E} (1 + x\_{w,u}) \pmod{2}. $$ Let $p\_u$ be the parity of the number of edges of the form $(w,u)$. Then we can formulate the task as follows:

> Assign $0/1$ values to the edges so that the sum of weights of edges adjacent to $u$ is $p\_u$ (mod 2).

As an example, consider your sample graph, with edges $$ (1,2), (1,3), (2,4), (3,4). $$ We have $p\_1 = 0$, $p\_2 = 1$, $p\_3 = 1$, $p\_4 = 0$. We are looking for a solution (mod 2) of the following system: $$ \begin{align\*} &x\_{12} + x\_{13} = 0 \\ &x\_{12} + x\_{24} = 1 \\ &x\_{13} + x\_{34} = 1 \\ &x\_{24} + x\_{34} = 0 \end{align\*} $$

One such solution is $x\_{12} = x\_{13} = 0$, $x\_{24} = x\_{34} = 1$. This is exactly the solution that you describe.

If you sum all equations, then all the edges cancel, and you get $\sum\_u p\_u = 0 \pmod{2}$. This gives a necessary condition for the existence of a solution. It turns out that this condition is also sufficient, assuming the graph is connected (otherwise, you need a similar condition for each connected component). A solution can be found using linear algebra modulo 2.

This is related to the so-called *Tseitin contradictions* in proof complexity, which correspond to assignments of the weights $p\_u$ for which no solution exists.
> 3 votes

---
Tags: algorithms, graphs
---


title: Quotient in LOOP program

text:
# Question
Title: Quotient in LOOP program
I want to construct a LOOP-computable program for the integer division (quotient):

x = a DIV b

The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP\_(programming\_language)

I don't know how to do this without a while.

# Answer
The idea is to implement the following algorithm:

```
result = 0
while a >= 0:
  a = a - b
  result = result + 1
end while
return result - 1

```

As you mention, there is no `while`. However, since we have an a priori upper bound on the number of rounds, we can simulate the `while` as follows:

```
result = 0
repeat a + 1 times:
  if a >= 0:
    a = a - b
    result = result + 1
  end if
end repeat
return result - 1

```

It remains to implement the conditional and subtraction. In fact, you can't really implement the conditional, since all numbers are automatically non-negative. However, this is easy to fix by replacing the condition `a >= 0` with the condition `a > 0`. I'll let you work out the minor changes required to implement this change.
> 1 votes

# Answer
Look for the unique integer $x$ such that $b x \le a$ and $b(x+1) \> a$. With this approach, you don't need a WHILE statement.
> 1 votes

---
Tags: turing-machines, computability, loops, primitive-recursion
---


# Question
Title: Finding CNF of $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q)) $
I'm trying to find the CNF of the $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q))$, and afterwards proving it's validity. As i'm new to CNF i wanted to ensure i've found the right CNF before trying to move on, so for $(p \rightarrow q) \rightarrow p$:

the normal from is: $p \rightarrow q \wedge q \rightarrow p$

and it's valid?

# Answer
Your formula is incorrect as CNF. Conjunctive normal form (CNF) is a normal form like

$$ (a\_1 \vee \neg a\_2 \vee \dots \vee a\_n) \wedge (\neg b\_1 \vee \dots \vee b\_m) \wedge \dots \wedge (c\_1 \vee \dots \vee c\_l) $$

therefore a formula in CNF has only literals (i.e. atoms or negated atoms), $\wedge$, and $\vee$. It doesn't have $\to$.

If it's allowed to transform $p \to q$ to its equivalent formula $(\neg p) \vee q$, you can use this for the first step to convert a given formula to a CNF formula.
> 2 votes

---
Tags: logic, propositional-logic, normal-forms
---


# Question
Title: what is a shearlet/shearlet transform and how can i use it?
from what wikipedia says shearlet is a successor to wavelets(whatever that is) and that they are extremely good at representing complicated data efficiently. But neither wikipedia nor other articles that i found have any layman definition of shearlets in it. A layman definition would be great and algorithm to implement them on say images would be awesome and a python implementation would be godsend.

# Answer
> 2 votes
Shearlets are a family of basis functions. Cartesian coordinate systems have already made you familiar with orthonormal basis functions: scaling up a rightward- and an upward-pointing unit vector lets you express any (x, y) point in the plane.

Suppose you are Seurat, the pointillist, and you have a budget of 100 brushstrokes with which to express a monochromatic landscape. In addition to (x, y) information we can also give each stroke a radius `r`, for big blobs or fine dots. This is not too far away from a wavelet representation of the landscape.

Linear features like grass or tree limbs will be a poor fit for such a scheme, requiring many dots. Imagine replacing circles with ellipses of defined aspect ratio and orientation, `a` and `theta`, or in your case replacing them with parabolic shapes of defined narrowness and orientation. This is not too far away from a shearlet representation. It uses a shearing transform, rather than an angular rotation transform, as the math works out more conveniently that way. The rubber sheet deformation of shearing expresses the direction of each landscape feature, and resembles rotation. In fact, a sequence of three shears can rotate an image exactly.

For an implementation you should refer to https://github.com/stefanloock/pyshearlab or http://shearlab.org. Quoting the latter:

> ... shearlet systems are particularly well adapted to represent anisotropic features (such as curves) that are often crucial in multidimensional data. The resulting representation has proven well-suited for image processing tasks such as inpainting, denoising or image separation. ...
>
> Similiar to wavelet systems, shearlet systems are constructed by modifying generator functions. For wavelet systems, these functions are isotropically scaled and translated. While this is enough to provide an optimally sparse representation for an interesting class of 1D functions it fails to do so in higher dimensions. To compensate this shortcoming, the direction of the generator functions has to be varied. In shearlet theory, this is accomplished by shearing and anisotropic scaling.

---
Tags: approximation, data-compression
---


# Question
Title: What is the optimal way to solve the following optimization problem
You are given a function $F$, which can take one or more positive integer operands. Let $L=\\{a\_1,a\_2\ldots a\_n\\}$.

We need to compute the function $F(L)$ using the **least number** of transformations/steps. Computing $F(L)$ is not the main goal. Computing it in the fastest possible way is the goal.

**Following rules are allowed to be applied to this function.**

--\> If $L$ has only one element say $x$, then the $F(L) = x$;

--\> If all elements in $L$ are even then $F(L)=2F(L')$, where $L'$ contains all elements in $L$ divided by 2. For example $F(4,8,10)= 2\*F(2,4,5)$

--\> If some elements in $L$ are odd and some are even, then $F(L)=F(L')$, where $L'$ has same odd elements as L, but the even elements in $L$ are made odd by removing the factor 2. For example $F(6,9,20)=F(3,9,5)$

--\> If any of the integers in the list is 1, then $F(L)=1$;

--\> If two or more integers in $a\_1,a\_2\ldots a\_n$ are same, then we can remove the copies and keep only one of them. For example $F(4,5,6,5)=F(4,5,6)$

--\> For any pair $a\_i$ and $a\_j$ where($a\_i\<a\_j$), you can replace $a\_j$ with $a\_j-a\_i$

$F(4,7,8)=F(4,(7-4),8)=F(4,3,8)$

---

It is easy to notice that this process terminates, because at each step, either the value one of the operands is reduced or the number of operands is reduced.

**Given $L$ can there be a DP to optimize the number of operations needed to solve $F$, or is there a greedy strategy that is optimal or constant approximate of the optimal?**

For example

Consider the following instance

$F(15,30,45)$

Depending on your choice, you can compute this value in several ways.

\begin{align\*} F(15,30,45)& =F(15,30,45-30)=F(15,30,15)\\ & =F(15,30)\\ & =F(15,30-15)=F(15,15)\\ & =F(15)=15 \end{align\*}

which takes 4 iterations.

Another way is

\begin{align\*} F(15,30,45)& =F(15,30-15,45)=F(15,15,45)\\ & =F(15,45)\\ & =F(15,45-15)=F(15,30)\\ & =F(15,30/2)=F(15,15)\\ & =F(15)=15 \end{align\*}

which takes 5 iterations.

I want an algorithm which finds the optimal solution.

# Answer
> 1 votes
Yes, there is a simple way to compute $F$.

Proposition: $F(a\_1,a\_2\ldots a\_n)=\gcd (a\_1,a\_2\ldots a\_n)$, where $\gcd$ is the greatest common divisor.

Proof: I will leave it as an exercise. Hint, the replacement of $a\_j$ by $a\_j-a\_i$ whenever $a\_i\<a\_j$ is very powerful.

Here is a simple and efficient algorithm to compute $F(a\_1,a\_2\ldots a\_n)$.

* Let $r = a\_1$.
* Iterate $i$ through $2,3, \cdots, n$, setting $r$ to $\gcd(a\_i, r)$. Here $\gcd(a\_i,r)$ can be computed by any of your favorite GCD algorithms such as Euclidean algorithm or binary GCD algorithm.
* return $r$.

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


# Question
Title: Distribute repeated values into bins as evenly as possible
**Preface**

I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-hard).

After doing further research (because this is my bottleneck atm), I stumbled upon this similar question, but again, there's the assumption of the problem beeing np-hard and it's not exactly what I'm looking for. However, it seems the question is a better fit on this site, than SO (correct me if I'm wrong).

I'm pretty sure this can be solved "brute force" (aka optimal) with the correct algorithm in small time for the given constraints. More to that later.

**Problem**

I have a small set of repeating values e.g.

```
values = 10 x [18] (ten times the value 18); 5 x [30], 6 x [55]

```

of which I need to distribute as many as possible evenly across a fixed *number of bins* with a *maximum difference between the bins* (maximum difference between the sum of elements in the bins, see below).

*Constraints:*

The reason I think this can be brute forced are my constraints. I will never have a great number of bins (at the moment the maximum is 3, let's assume it might be 4 or 5 though). The maximum difference between the bins is atm fixed at 2, we can assume it stays there if that helps because I can set this arbitrarily if needed.

**Example**

For a small example, lets set `values = [[18,18,18,18,18],[30,30,30]]`, `number_of_bins = 2` and `max_difference_between_bins = 2`.

The algorithm to distribute them would be something along the lines

```
for remainder in range(0,8) #try distributing all packages first,
 # then one less, then two less, etc.
    generate possible distributions for values in bins
    add the distributions to check differences, if any difference
      # is below the threshhold of max max_difference_between_bins, break

```

Trying it out:

Remainder = 0

Distribute 5 times 18 into two bins:

```
(0,90),(18,72),(36,36),(72,18),(90,0)

```

Distribute 3 times 30 into two bins:

```
(0,90),(30,60),(60,30),(90,0)

```

See that the example is bad because it works out in the first run, anyways, adding them yields:

```
(0,90) -> (0,180),(30,150),(60,120),(90,90)
(18,72)-> (18,162),(48,132),(78,102)(108,72)
(36,36)-> (36,126),(66,96),(96,66)(126,36)
(72,18)-> (72,108),(102,78),(132,48),(162,18)
(90,0) -> (90,90),(120,60),(150,30),(180,0)

```

As you can see, half of them are obsolete because they are duplicates.

If there hadn't been a solution (90,90) this would then continue in the next run with trying the same for `values = [[18,18,18,18],[30,30,30]]` and `values = [[18,18,18,18,18],[30,30]]` and `remainder = [18]` or `remainder = [30]`.

**Runtime**

So for a really big example of say 70 values with 5 different sizes distributed across 3 bins, the possible solutions should be for the first run:

Say 50 values of the same size are distributed across 3 bins, then we get 50+3-1 over 3 = 1326 possibilites or 316251 for 5 bins (right?) (supposing the bins are differentiable, which they don't need to be, but then we would have to upscale later for the combination with the other values).

Distributing the other 20 with say 8, 5, 4, 3 values each thats 45, 21, 15, 10 values. Multiplicated, that's 190 million possibilities. However, most of those combinations can't possibly be a good solution. Some depth search or divide and conquer should be able to break them down.

Of course, those are then multiplied by 5 for the first run with a remainder of 1, by 120 for a run with a remainder of 2, etc. But those solutions can also be generated from the old solutions and again, it should be possible to go through only a fraction of them.

**Question**

Is basically, how do I get a solution for this in small time? Pseudocode or even python would be great, but not necessary, I can figure the coding out myself.

*We can make many assumptions for the number of different values and maximum number of values you want, so if you think the part about reducing it from 190 million times whatever solutions is too big, I'm fine with going down to, for example, maximum 3 bins, maximum 3 different values occuring a maximum of, say, 20 times together (so not 20 times this, 20 times that, but rather 10 times this, 5 times that, 5 times the other).*

# Answer
After an epiphany, I solved the problem myself now. To generate all solutions quite efficiently I have used the following algorithm:

> Find all groups of possible bins with any combination of occurences of the values smaller or equal to their maximum occurence that have a sum smaller than (the sum of all values divided by the number of bins + the maximum difference between bins).
>
> Bins include for example \[\],\[18\],\[18,18\],\[18,18,18\],\[30\],\[30,18\], etc.
>
> Calculate the sum of each bin.
>
> Combine only those bins with each other that have a sum that varies by less than the maximum difference.
>
> Chose all combinations as solutions where the number of values in all their bins equals the maximum number of values. if none, reduce maximum number of values and add a value to remainder.

Tested for 3 bins and up to like 50 values, runtime is almost instant in python.
> 0 votes

---
Tags: algorithms, optimization
---


title: Quick Sort - First Element As Pivot

text:
# Question
Title: Quick Sort - First Element As Pivot
I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot (15) into its appropriate position.

Example: \[15, -7, 22, 7, 21, 34, -13, 19\]

My understanding:

```
15, -7, 22, 7, 34, -13, 19
#   ^                   ^

```

Move left-pointer to first element larger than the pivot. 1 comparison (move to 22). Move right-pointer to first element smaller than the pivot. 1 comparison (move to -13).

```
15, -7, 22, 7, 34, -13, 19
#       ^           ^

```

Swap elements at the pointers (22, -13).

```
15, -7, -13, 7, 34, 22, -13, 19
#       ^           ^

```

Move left-pointer to first element larger than the pivot. 2 comparisons (move to 34). Unable to move right-pointer to first element smaller than the pivot (cannot past the left-pointer.

```
15, -7, -13, 7, 34, 22, -13, 19
#               ^   ^

```

Swap elements at the pointers (34, 22).

```
15, -7, -13, 7, 22, 34, -13, 19
#               ^   ^

```

This is where I am stuck. My understanding is that the pivot should then be swapped with 22, but that doesn't seem correct?

How do I move the pivot (15) into its appropriate position?

# Answer
> 2 votes
Usually, a random pivot is selected and moved to the first location. After swapping -13 and 22, your pointers should be on 7 and 34.

7 and 34 are correctly placed. Also 7 and 34 are adjacent, so time has come to put the pivot in its correct place.

array looks like this

*15, -7, -13, 7,* **34, 22, 19**

So now you know that all elements after 34 are greater than 15. So swap the first element before 34 with the pivot.

So array looks like

7, -7, -13, **15,** 34, 22, 19

Now all on left of 15 are lesser than 15 and all on right of 15 are greater than 15

---
Tags: sorting, quicksort
---


# Question
Title: Can two free variables in lambda calculus have different values?
I am studying lambda calculus for the first time and I was trying to do the reduction beta of the lambda term $(\lambda x.xy)y$. Can I assume that these two free variables $y$ are the same? Or do I need to rename the rightmost $y$?

# Answer
> 2 votes
$y$ is free in the term you have given, so it is indeed the same variable.

You would not have the same variable in case $y$ was bound by the lambda. That would be the case, for example, if the term were to be $(\lambda y.xy)y$; then the rightmost $y$ would be free, but the one in $xy$ would be bound by lambda and, hence, a different variable.

---
Tags: lambda-calculus
---


# Question
Title: Parser theory: How to systematically compute FOLLOW sets?
Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have computed the FIRST sets.

For the following grammar:

```
E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' |  ε
F -> (E) | id

```

I found that the FIRST sets are:

```
FIRST(E) = { (, id }
FIRST(E') = { + ,  ε }
FIRST(T) = { (, id }
FIRST(T') = { *,  ε }
FIRST(F) = { (, id }

```

When it comes to computing the FOLLOW sets, I am trying to use the following rules:

```
1. $ goes into the set FOLLOW(S) where S is the start symbol.
2. If A -> aBb, then (FIRST(b) - { ε }) is in FOLLOW(B).
3. If A -> aB then everything in FOLLOW(A) is in FOLLOW(B)
4. If A -> aBb and ε is in FIRST(b), then everything in FOLLOW(A) is in FOLLOW(B).

```

Obviously, the step I am most certain here is that

`FOLLOW(E)` contains `$`, based on rule 1. But everything after that, I seem to have a hard time following a pattern on how to systematically compute the FOLLOW sets. For example, to compute `FOLLOW(E)`, how are we supposed to approach this?

`E -> TE'`, looks like `A -> aB` , so everything in `FOLLOW(E)` is in `FOLLOW(E')`. Where to go from here? Do I compute `FOLLOW(E')`? Then going to `FOLLOW(E')`:

`E' -> + TE'`... looks like `A -> aBb`. Then that means `FIRST(E') - { ε }` is in `FOLLOW(T)`. So I do know that `{ + }` is in `FOLLOW(T)`.

As you can see, with the way I have interpreted this, I am going around all over the place computing the FOLLOW of another production. Ultimately, I end up losing track on what terminal symbols go into which follow set. :(

I am for sure misunderstanding something here.

What is the right approach/ordering to compute the FOLLOW sets?

# Answer
> 4 votes
The simple way to do it is the same as the simple way to compute FIRST sets, using a least fixed-point algorithm in which a set of inclusion rules are applied repeatedly until a fixed-point is reached:

1. Initialise all the sets to empty.
2. For every production in order, use the rules to add elements into the sets. (As a slight efficiency, rule 2 only needs to be applied on the first pass. I didn't apply that to the trace below.)
3. If any set was modified during step 2, do it again.

So, here are the productions in order (I added the missing $\*$ to $T'$, and inserted an augmented start rule $S$, which avoids the need for your special case rule 1):

$$\begin{align} S &\to E\\; $ \\ E &\to TE' \\ E' &\to +TE' \mid \epsilon \\ T &\to FT' \\ T' &\to \*FT' \mid \epsilon \\ F &\to (E) \mid id \end{align}$$

1. Set all the $FOLLOW$ sets to $\\{\\}$
2. First pass. I left out productions like $F\to id$ which don't match any of the rules. $$ \begin{array}{c|l|l} S \to E\\; $ &\text{Add }\\$\text{ to }FOLLOW(E) &FOLLOW(E) = \\{ \\$ \\}\\ E \to TE' &\text{Add }FIRST(E')-\\{\epsilon\\}\text{ to }FOLLOW(T) &FOLLOW(T) = \\{ + \\}\\ &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E') &FOLLOW(E') = \\{ \\$ \\}\\ &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T) &FOLLOW(T) = \\{ + \\$ \\}\\ E' \to +TE' &\text{Add }FIRST(E')-\\{\epsilon\\}\text{ to }FOLLOW(T) &\text{no change}\\ &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E') &\text{no change}\\ &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T) &\text{no change}\\ T \to FT' &\text{Add }FIRST(T')-\\{\epsilon\\}\text{ to }FOLLOW(F) &FOLLOW(F) = \\{ * \\}\\ &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T') &FOLLOW(T') = \\{ + \\$ \\}\\ T' \to \*FT' &\text{Add }FIRST(T')-\\{\epsilon\\}\text{ to }FOLLOW(F) &\text{no change}\\ &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T') &\text{no change}\\ &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F) &FOLLOW(F) = \\{ * + \\$\\}\\ F \to (E) &\text{Add })\text{ to }FOLLOW(E) &FOLLOW(E) = \\{ ) \\$\\}\\ \end{array} $$
3. There were various changes, so we repeat step 2.
4. (Step 2, second pass) $$\begin{array}{c|l|l} S \to E\\; $ &\text{Add }\\$\text{ to }FOLLOW(E) &\text{no change}\\ E \to TE' &\text{Add }FIRST(E')-\\{\epsilon\\}\text{ to }FOLLOW(T) &\text{no change}\\ &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E') &FOLLOW(E') = \\{ )\\$ \\}\\ &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T) &FOLLOW(T) = \\{ + )\\$ \\}\\ E' \to +TE' &\text{Add }FIRST(E')-\\{\epsilon\\}\text{ to }FOLLOW(T) &\text{no change}\\ &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E') &\text{no change}\\ &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T) &\text{no change}\\ T \to FT' &\text{Add }FIRST(T')-\\{\epsilon\\}\text{ to }FOLLOW(F) &\text{no change}\\ &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T') &FOLLOW(T') = \\{ + ) \\$ \\}\\ T' \to \*FT' &\text{Add }FIRST(T')-\\{\epsilon\\}\text{ to }FOLLOW(F) &\text{no change}\\ &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T') &\text{no change}\\ &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F) &FOLLOW(F) = \\{ * + ) \\$\\}\\ F \to (E) &\text{Add })\text{ to }FOLLOW(E) &\text{no change}\\ \end{array} $$
5. (step 3, second pass) There were some more changes. Once again.
6. (Step 2, third pass) $$\begin{array}{c|l|l} S \to E\\; $ &\text{Add }\\$\text{ to }FOLLOW(E) &\text{no change}\\ E \to TE' &\text{Add }FIRST(E')-\\{\epsilon\\}\text{ to }FOLLOW(T) &\text{no change}\\ &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E') &\text{no change}\\ &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T) &\text{no change}\\ E' \to +TE' &\text{Add }FIRST(E')-\\{\epsilon\\}\text{ to }FOLLOW(T) &\text{no change}\\ &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E') &\text{no change}\\ &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T) &\text{no change}\\ T \to FT' &\text{Add }FIRST(T')-\\{\epsilon\\}\text{ to }FOLLOW(F) &\text{no change}\\ &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T') &\text{no change}\\ T' \to \*FT' &\text{Add }FIRST(T')-\\{\epsilon\\}\text{ to }FOLLOW(F) &\text{no change}\\ &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T') &\text{no change}\\ &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F) &\text{no change}\\ F \to (E) &\text{Add })\text{ to }FOLLOW(E) &\text{no change}\\ \end{array} $$

So the $FOLLOW$ sets are: $$\begin{align} FOLLOW(S) &= \\{\\}\\ FOLLOW(E) &= \\{ )$ \\}\\ FOLLOW(E') &= \\{ )$\\}\\ FOLLOW(T) &= \\{ + ) $\\}\\ FOLLOW(T') &= \\{ + ) $\\}\\ FOLLOW(F) &= \\{ * + ) $ \\} \end{align} $$

That's a very simple grammar, of course. You might want to try it out with a more complicated one, although it is typical that it terminates after very few iterations and that many of the steps are obvious no-ops.

---
Tags: compilers, sets, parsers, syntax
---


# Question
Title: what is the Recent Nature Inspired Algorithm for Optimization?
I'm into designing a **recommender system** for movie database and for effective optimization.I suggested the idea of using particle swamp optimization ,but my professors need recent algorithms,can any one suggest ***recent nature inspired algorithms for optimization***.(After Cuckoo Search Optimization).

# Answer
This paper\[\[1\]\] recommends the following Swarm Intelligence algorithms:

> 1. Ant colony optimization
> 2. Bat algorithm
> 3. Cuckoo search
> 4. Firefly algorithm
> 5. Particle swarm optimization

\[1\]: "A Brief Review of Nature-Inspired Algorithms for Optimization"
> 3 votes

# Answer
You may want to check the IEEE Congress on Evolutionary Computation as new algorithms are published there every year. Not sure if the answer is still helpful though. You may check here link for the 2018 publications.
> 2 votes

# Answer
Recently, optimization algorithms are being suggested based on the network dynamics of a slime mold called *Physarum polycephalum*. For certain problems, these algorithms provably construct optimal solutions. Have a look into the following paper for further pointers.

Yahui Sun. Physarum-inspired Network Optimization: A Review. arXiv: 1712.02910
> 2 votes

---
Tags: algorithm-analysis, bio-inspired-computing
---