# Question
Title: What is the minimum number of bytes required to store the sum of two primitive integers?
# Motivation

An informal way word this question is,

> How would re-do some of the weird promotion rules in languages descended from **C**, like **C#** or **Java**. The goal would as to minimize human bewilderment when you add a signed integer (element of $\mathbb{Z}$) to an unsigned integer (an element of $\mathbb{N}$) ..

However, we really want the engage the math side of things to answer this question, with the minimum amount of computer programming jargon.

---

# More Details

In several of the programming languages inspired by **C** have some unexpected behavior when you add a natural number to a negative integer.

In **C** we have something like $(+20) + (-4) = 97128371823$ instead of $(+20) + (-4) = (+16)$.

We sometimes get very strange results with **C** and some of the programming languages compiled into **C**.

Alternatively worded, when you add an `unsigned` and a `signed` together, the output is ***not*** usually what the programmer expected.

Under-the-hood, integers are stored in 8 bits, or 16 bits, or 32 bits, etc... If 8 bits is not enough space, a person can write code "*promote*" the 8-bit integer to a 16 bit integer.

The following are three of the **C++** primitive types:

| Black Board Bold | type name | number of bytes | can be a negative number? |
| --- | --- | --- | --- |
| $\mathbb{N}$ | `unsigned` | ***n*** | **no** |
| $\mathbb{Z}$ | `long` | ***2n*** | **yes** |
| $\mathbb{Z}$ | `signed` | ***n*** | **yes** |

When adding a signed 8 bit number to an unsigned 8 bit number we could store the result in a 16 bit signed number.

I have written assembly language before, and I am familiar with the difficulties, don't worry too much about the computer programming aspects of the problem.

---

# Was there a Question in there somewhere?

An answer to this question is a mathematical description of a function named $\mathcal{add}$ (for "*addition*"), which takes two ***primitive specifications*** as input and outputs a new ***primitive specification*** the minimum number of bits required to store the two ***primitive specifications*** added together in the worst case.

## Definition of a ***intspec***

> We define a ***primitive specification*** $p$ to be be an ordered pair $(p.sign, p.bits)$ such that
>
> * $p.sign$ is something like a string taken from the set $\\{\mathtt{ℤ}, \mathtt{ℕ}\\}$
> * $p.bits$ is a number of bits.

If there is a plus sign, it is unsigned.

If there is a minus sign, the specification is for signed numbers.

---

## Examples of a ***primitive specification***

---

### Example One

$p\_{1} (ℤ, 8)$.

$p\_{1}$ is said to be `unsigned` because it represents a natural number taken from $\mathbb{N}$

$p\_{1}$ represents positive integers stored in 8 bits.

These integers range from $0$ to $+256$

---

### Example Two

$p\_{2} = (ℕ, 8)$.

a ***signed*** integer stored in 8 bits using the two's compliment system.

$p\_{2}$ is a specification for primitive integers ranging from $-128$ to $+127$

In general, `signed` data-types range from $(-1)\*2^{n-1}$ to $(-1) + (+1)\*2^{n-1}$ where $n$ is the number of bits.

---

# The $\mathcal{add}$ Function

An answer to this question is an algebraic formula for the $\mathcal{add}$ function such that for any two ***intspecs*** $p\_{1}, p\_{2}$ we have $\mathcal{add}(p\_{1}, p\_{2})$ equal to the minimum number of bits required to store a number stored using primitive specification $p\_{1}$ and primitive specification $p\_{2}$.

In other words, $\mathcal{add}(p\_{1}, p\_{2})$ is a new integer specification containing the minimum number of bits required to add two integers such that the integers are stored using different encoding schemes.

* `(signed)` \+ `(signed)` will output a signed two's compliment number.
* `(signed)` \+ `(unsigned)` will output a signed two's compliment number.
* `(unsigned)` \+ `(unsigned)` will output an unsigned number.

Let $p\_{1} = (ℤ, 8)$. `unsigned` $p\_{1}$ ranges from $0$ to $+256$

Let $p\_{2} = (ℕ, 8)$. `signed` $p\_{2}$ ranges from $-128$ to $+127$

Consider the worst-case scenarios for adding the two.

In the mathematical sense, output should range from $-128$ to $+383$.

$\mathcal{add}(p\_{1}, p\_{2}) = (ℤ, 9)$

The output is signed ($ℤ$) and ranges from $-512$ to $+511$.

There are $9$ bits.

$(-1)\*2^{9} = -512$

$(-1)+(+1)\*2^{9} = +511$

---

# In general, what is a mostly algebraic formula for $\mathcal{add}(p\_{1}, p\_{2})$?

We want to know what would have to happen when you add a signed integer to an unsigned integer so that the result is what a mathematician would like to see, not an unexpected result.

We want $(+20) + (-4) = (+16)$, as it should be, instead of ugly non-sense such as $(+20) + (-4) = 97128371823$

# Answer
C is not designed with a principle of minimal bewilderment, so you'd be talking about a very different language. (I suppose you could say that C was designed, more or less, to be a portable assembly language, or a step above assembly language.)

If you care about minimal bewilderment, use bigints, like Python.
> 0 votes

# Answer
Signed is from $-2^{b-1}$ to $2^{b-1}-1$ and unsigned from $0$ to $2^b-1$.

Hence assuming the same $b$ for both operands

* signed + signed: $-2^b$ to $2^b-2$, takes $b+1$ bits, signed
* signed + unsigned: $-2^{b-1}$ to $3\cdot2^{b-1}-2$, takes $b+2$ bits, signed
* unsigned + unsigned: $0$ to $2^{b+1}-2$, takes $b+1$ bits, unsigned

\[Two's complement convention assumed\]

---

Homogeneous addition fits naturally with the numerical representation and is supported natively by the processors, possibly with an overflow bit. Heterogeneous addition is wonky.
> 0 votes

---
Tags: encoding-scheme, storage
---


# Question
Title: How to construct a carry-lookahead adder of the optimal $O(n)$ size
**Problem (TL;DR)**: I'd like to know how to construct a CLA adder that has $O(n)$ size and $O(\log n)$ depth using only fan-in 2 AND gates and XOR gates, as suggested in this answer and this answer.

**Settings and motivation**: I am doing a research project where we need to add or subtract two $n$ bit strings in 2's completement representation. Specifically, I am working in the area of secure multiparty computation, where generally we express a function that we want to securely compute as a boolean circuit, and use some off-the-shelf "compiler" to "compile" such circuit into a secure protocol that can be executed between the parties without leaking information.

In our work, we care about two things: communication complexity and round complexity. It turns out that the aforementioned compiler requires $O(1)$ communication and $O(1)$ rounds to compute an AND gate and no communication or round to compute an XOR gate. We are only allowed to use these two types of gates but they are universal. Therefore, the communication complexity scales roughly with the size of the circuit and the round scales roughly with the depth of the circuit.

**Constraints**: Only fan-in 2 AND gates and XOR gates can be used.

**My attempts**: I understand how to do it in $O(\log n)$ depth, but the problem is that my carry-lookahead unit is too large in size, specifically, it is $O(n^2)$. I am looking at the following carry-lookahead formula from Wikipedia.

To compute $C\_i$, we need to (at least) compute the $i$ OR's, which are just AND gates in disguise. Therefore, even we can compute the individual summands in constant size, it does not seem that I can get better than $O(n^2/2)$ because of the OR's. This implies that we must reuse computation in some clever way, and I've tried the work-efficient parallel prefixsum network or a segment-tree, none of which allowed me to cut these OR's or even just evaluates the individual summands efficiently.

I must be lacking some crucial insights here, after all, these expressions looks so temptingly recursive, but I've tried everything I can think of. I would appreciate either a fully worked-out solution or just a hint. Thanks for the helps in advance.

# Answer
> 2 votes
Actually, upon working on this problem for a bit more time, I discovered one method to build a size $O(n)$ and depth $O(\log n)$ CLA circuit. The key ingredient is the work-efficient parallel prefixsum network, e.g., as seen in the Blelloch scan. There, it is shown that using any associative binary operators in place of the normal addition, the prefixsum (using this binary operator) can be computed with a network of size $O(n)$ and depth $O(\log n)$.

Consider the problem at hand, we want to compute the following efficiently

If we define a function $f\_{a, b}(x) := a + bx$, then we can write the above as $$\begin{aligned} C\_1 &= f\_{G\_0, P\_0}(C\_0), \\ C\_2 = f\_{G\_1, P\_1}(C\_1) &= (f\_{G\_1, P\_1} \circ f\_{G\_0, P\_0})(C\_0), \\ C\_3 = f\_{G\_2, P\_2}(C\_2) &= (f\_{G\_2, P\_2} \circ f\_{G\_1, P\_1} \circ f\_{G\_0, P\_0})(C\_0), \\ C\_4 = f\_{G\_3, P\_3}(C\_3) &= (f\_{G\_4, P\_4} \circ f\_{G\_2, P\_2} \circ f\_{G\_1, P\_1} \circ f\_{G\_0, P\_0})(C\_0).\end{aligned}$$

If we let $\circ$ be the function composition operator defined by $f\_{a,b}(x) \circ f\_{c,d}(x) = f\_{c+ad, bd}(x)$, then it is easy to check that this operator is associative. We can either argue that it is so because function composition is in general associative, or explicitly check it as follows: $$(f\_{a,b} \circ f\_{c,d}) \circ f\_{e,f} = f\_{c+ad, bd} \circ f\_{e,f} = f\_{e+cf+adf, bdf},$$ $$f\_{a,b} \circ (f\_{c,d} \circ f\_{e,f}) = f\_{a,b} \circ f\_{e+cf, df} = f\_{e+cf+adf,bdf}.$$

Therefore, if we take our array to be $\[f\_{G\_0, P\_0}, f\_{G\_1, P\_1}, f\_{G\_2,P\_2}, f\_{G\_3,P\_3}\]$, taking the prefixsum on this array gives us an array $\[\bigcirc\_{i=0}^{k} f\_{G\_i, P\_i}\]$ for $0 \leq k \leq 3$, where $\bigcirc$ denotes repeated composition. Now, we only need to apply each item of this array to $C\_0$ to get the array $\[C\_1, C\_2, C\_3, C\_4\]$. This completes the construction.

The Blelloch scan network guarantees us that we can implement the above prefixsum with $O(sn)$ size and $O(d\log n )$ depth, where $s$ and $d$ are the size and depth of the gate computing the composition, respectively. However, the composition only involves 2 AND gates and 1 OR gate, so its size and depth are both $O(1)$. Since the above easily generalize to any $n$ beyond $4$, we conclude that a $n$-bit CLA adder can be implemented with $O(n)$ size and $O(\log n)$ depth.

---
Tags: circuits, boolean-complexity
---


# Question
Title: How can a $P(n)$ run in polynomial time if it calls $R(m)$ which has exponential time
We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $R(m)$, which runs in exponential time in m. Thankfully, P is still correct when we replace each call to $Q(m)$ with a call to $R(m)$ instead. Which of the following can we definitely say about the modified version of P?

(a) $P(n)$ still runs in polynomial time in $n$.

(b) $P(n)$ requires exponential time in $n$.

(c) $P(n)$ runs in polynomial time in $n$ if the number of calls made to Q is proportional to $log n$

(d) $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m)$, $m ≤ log n$.

The answer here is: (d)

Their reasoning: If $m ≤ log n$ for each call to $Q$ with argument $m$, then the running time of $R(m)$ is exponential in $m$ but polynomial in $n$. Since the number of calls to $Q$ originally (and $R$ after the modification) is a polynomial in $n$, the overall running time of $P$ is polynomial. None of the other options definitively hold

I don't understand how they reached that conclusion: Since $R(m)$ is exponential, calling it even once would result into exponential time and since $R(m)$ is a sub-routine to $P(n)$, how can they say that "running time of $R(m)$ is exponential in m but polynomial in $n$"

I am totally confused by this, i can understand reductions ( Theory of computation ), my assumption was according to programming if we call an exponential function inside a polynomial function. The overall complexity would be exponential since that is the bottle-neck

Can someone shed a light on how to approach these problems?

# Answer
> 1 votes
If $R(n)$ is exponential in $n$, $R(\log n)$ is polynomial in $n$.

E.g. $$T(n)=4^n\to T(\log\_2n)=4^{\log\_2n}=n^2.$$

# Answer
> 0 votes
If $R(m)$ runs in exponential time in $m$, that means that the running time of $R(m)$ is, informally, something like $O(2^m)$. More formally, its running time is $O(c^m)$ for some constant $c$.

Now plug in $m=\log n$, simplify, and see what conclusions you can draw about the running time as a function of $n$.

---
Tags: complexity-theory, reductions, polynomial-time-reductions
---


# Question
Title: Logics for multi-agent and distributed systems and algorithms
The various temporal logics are particularly suitable for the specification and verification of concurrent computer programs. Are there logics that are particularly suitable for the specification and verification of multi-agent and distributed systems and algorithms? Or are the temporal logics used as-is for these purposes as well?

# Answer
TLA+ is commonly used for verification of distributed algorithms. I've seen it actively used by researchers and industry engineers/architects.
> 1 votes

---
Tags: distributed-systems, concurrency, temporal-logic
---


# Question
Title: An efficient algorithm to find a shortest cycle including a specific vertex
We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$.

We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle.

This answer on SO explains why neither BFS or DFS work. However, I still think that DFS could be helpful in finding a minimun such cycle. Is there a way to make it work?

# Answer
You can find the shortest cycle that contains $v$ by running BFS from $v$, and stopping at the first time that $v$ is reached again (or if BFS terminated without reaching $v$).

An important property of BFS is that if it runs from vertex $v$, then every vertex $s$, when it is first reached, then the path that was found from $v$ to $s$ is minimal. Thus, reaching $v$ from $v$ with BFS finds the shortest path from $v$ to itself, namely the shortest cycle that contains $v$.
> 9 votes

# Answer
How can you reach from v to v using bfs? And bfs gives wrong ans for the graph-\> 1 2 2 3 2 4 3 4 given that special vertex is 1. Here BFS will tell that there is a cycle but that cycle does not includes special vertex 1.
> -1 votes

---
Tags: algorithms, graphs, search-algorithms
---


# Question
Title: What is the maximum inverse pairs will I have when I build a heap?
Suppose that I have 7 different integers stored in an array. Among those arrange- ments that can be viewed as a min heap, what is the maximum number of inverse pairs within the array?

# Answer
If you have $7$ (or rather $2^{n}-1$) arbitrary numbers, then brute force is the way to go. However, there are some observations if you construct a heap with all distinct numbers in the range $1 ... 2^{n}-1$.

Intuitively(for the lack of a rigorous mathematical proof), a min heap formed by inserting in *reverse postorder* or *converse preorder* traversal of the numbers $1 ... 2^{n}-1$ sorted in ascending order should give the maximum number of inversions. Example

It is easy to see that at every level, the **rightmost** element, will not have inversions. For the remaining elements, visually, the inversions would look something like this

i.e. every element is paired up with all elements of remaining subtrees of height $h-i$ for a heap having height $h$ and a level $i$. From here an expression for the no. of inversions can be derived. We simply sum up the inversions at each level, for all levels. $$no\\;of\\;elements\\;at\\;level\\;i = no\\;of\\;subtrees\\;of\\;height\\;h-i = 2^{i}$$ $$no\\;of\\;elements\\;in\\;a\\;complete\\;binary\\;tree\\;of\\;height\\;h = 2^{h+1}-1$$ $$no\\;of\\;inversions\\;at\\;level\\;i = (2^{h-i+1}-1)\*\sum\_{k=1}^{2^{i}-1}k$$ $$total\\;no\\;of\\;inversions = \sum\_{i=1}^{h}(2^{h-i+1}-1)\*\sum\_{k=1}^{2^{i}-1}k$$

Further simplification of the expression can be done, i'd say this form preserves the "meaning" of the expression in a way.

Substituting $h=2$, we get $9$ as the no. of inversions for heap having elements $1...7$, which can be verified by counting the number of inversions(coloured links except black) in the picture above.
> 2 votes

# Answer
By exhaustive search, $\[1, 5, 2, 7, 6, 4, 3\]$ has $9$ inversions.
> 1 votes

---
Tags: heaps
---


# Question
Title: Loop Invariant Code Motion not tagging an expression correctly
I was reading the LICM section of the book Advanced Compiler Design and Implementation and found me questioning why the expression `d = -c` wasn't tagged as invariant.

It isn't hard to see that `c = 2` is invariant given its operand is a constant. Then, since `d = -c` is taking an invariant operand, then `d` also should be invariant.

What point am I missing here?

# Answer
The comment by Rinkesh is correct. The expression $-c$ is loop-invariant (and can be constant-propagated to the value $-2$), but the assignment $d \leftarrow -c$ is not because the assignment in block B4 might execute instead.

If you're still not convinced, try converting it to static single assignment (SSA) form.
> 1 votes

---
Tags: optimization, compilers
---


# Question
Title: System of equalities and inequalities is NP-hard using a reduction from 3COLORING
We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2, ..., xn. The problem is to decide whether there exists an assignment to x1, x2, ..., xn that satisfies all the constraints simultaneously. I need to show that the following problem is NP-hard by reducing from the **3COLORING** problem.

For example:

x1 \+ x2 ≤ 1

x1 ≥ 0

x2 ≥ 0

4x1x2 ≥ 1

is solvable if I choose x1 = x2 =1/2.

I'm have some issue in coming up with a valid reduce from 3coloring to this. If any one of you can provide me some tips that would be extremely helpful.

# Answer
> 2 votes
You can express any boolean formula using a (polynomial-size) system of quadratic equalities. Indeed you can force a variable $x$ to be binary by writing $x^2 = x$, and you can force a binary variable $z$ to be the NAND of two binary variables $x$ and $y$ by writing $z = 1 - xy$ (recall that NAND is a universal operation. Anyway it is easy to come up with explicit formulas for AND, OR, and NOTs).

Then you just need to write a (polynomial-size) boolean formula that is satisfied if and only if the input instance of graph 3 coloring is a yes-instance. This should be straightforward.

---
Tags: complexity-theory, np-complete, reductions, np-hard, 3-sat
---


# Question
Title: Concrete example of a set with a lower degree of unsolvability
Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've seen the proof that such sets exist (the book Gems of Theoretical Computer Science has a chapter on this), the proof works by (a bit artificially) constructing Turing incomparable sets. So far, I haven't seen an example of a concrete "natural" example of an undecidable set below the Halting problem, which I would like to find.

Here are some notes on Post's problem, with a proof idea of its solution.

My first attempt at coming up with such a set would be to consider somethin like A = {BB(n) : n $\in$ Halt}, because, even if I am supplied with A as an oracle, I can't seem to use it to know if n is in Halt without computing BB(n), which is an uncomputable function (the busy beaver function), but I'm a bit stuck trying to just prove that it is undecidable.

So my question is: do you know examples of concrete undecidable sets, with a lower degree of unsolvability than the Hating problem?

Thanks in advance

# Answer
First, let me show that your proposed $A$ is equivalent to the halting problem after all. Let $a\_n$ be the $n$th element of $A$ by size; we have $a\_n\ge BB(n)$, and so $A$ computes a function dominating $BB$. Since any function dominating $BB$ computes $0'$, we get $A\ge\_T0'$. More generally, any infinite subset of $ran(BB)$ will compute $0'$.

In fact, there are currently no known examples of "natural" sets of intermediate degree, let alone r.e. ones. There are also very few candidate examples, and we have general results ruling out any "too-robust" such constructions. For example, see Lachlan, *Uniform enumeration operations* or Downey/Shore, *There is no degree invariant half-jump*. I've also written about this in more detail at MSE.
> 2 votes

---
Tags: turing-machines, computability, reductions, halting-problem, turing-completeness
---


# Question
Title: Transformation Function: Gonzalez and Woods
I have been reading Image Processing from Gonzalez and Woods and in the chapter Image Transformation I have come across this equation

$$ T \left(u, v\right) = \sum\_{x=0}^{M-1} { \sum\_{y=0}^{N-1} { f \left(x, y\right) \\, r \left(x, y, u, v\right) } } \\,. $$

I am unable to understand this mathematical notation. Any help will be highly appreciated. Thanks

# Answer
> 1 votes
Those ${\sum}\text{-signs}$ specify sigma notation. They're basically like `for` loops where you keep summing up the value specified in the body.

The equation, $$ T \left(u, v\right) = \sum\_{x=0}^{M-1} { \sum\_{y=0}^{N-1} { f \left(x, y\right) \\, r \left(x, y, u, v\right) } } \\,, $$

translates into:

```
public double T(double u, double v)
{
    var sum = 0.0;

    for (int x=0; x <= M-1; ++x)
    {
        for (int y=0; y <= N-1; ++y)
        {
            sum = sum + (f(x, y) * r(x, y, u, v));
        }
    }

    return sum;
}

```

---

In other words, it defines some function, $T \left(u, v\right) ,$ that takes two input variables: $u$ and $v .$ You also need to know two other functions: $f \left(x, y\right)$ and $r\left(x, y, u, v\right) ,$ which means you'll need at least 2 more equations.

Then:

1. Start with a starting total value of $0 .$
2. Set $x$ to $0 .$
3. Set $y$ to $0 .$
4. Calculate $f\left(x, y\right) r\left(x, y, u, v\right) ,$ then add this value to the total.

* On the first evaluation, $x=0$ and $y=0 ,$ so that's $f\left(0, 0\right) r\left(0, 0, u, v\right) .$
5. Increment $y .$

* If it's still less-than-or-equal-to $N - 1 ,$ then go back to Step (4).
6. Increment $x .$

* If it's still less-than-or-equal-to $M - 1 ,$ then go back to Step (3).
7. The final total is the calculated value for $T \left(u, v\right) .$

# Answer
> 0 votes
With $M=3,N=2$, the expression expands to

$$\begin{align}T(u,v)= &f(0,0)\\,r(0,0,u,v)+f(0,1)\\,r(0,1,u,v)+\\ &f(1,0)\\,r(1,0,u,v)+f(1,1)\\,r(0,1,u,v)+\\ &f(2,0)\\,r(2,0,u,v)+f(2,1)\\,r(0,1,u,v)\end{align}.$$

$f$ denotes an image (bidimensional array of pixel values), $T$ is the image transformed to another bidimensional array and $r$ is some function that defines the transformation.

For example, the Discrete Fourier Transform corresponds to

$$r(x,y,u,v):=e^{i(\omega\_xxu+\omega\_yyv)}.$$

Such transformations are obviously linear with respect to $f$.

---
Tags: notation, digital-image-processing
---


# Question
Title: Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$
**Preliminaries**. Let $n,m,p \in \mathbb{N}$ with $n,m,p \> 1$. We allow that $p$ could be large but still bounded by a function of $n$: $p = O(2^n)$. Let our alphabet be $\Sigma = \\{0,1\\}$, with non-empty languages $ L\_1,L\_2,...L\_p \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. The other preliminaries are the same as the previous question:

> We follow the standard definition for deterministic finite-state automata except that we allow the state-transition function $\delta$ to be a partial function. In other words, an FSM has a finite number of states with transitions between them. We define the *depth* of a state $s$ as the length of the shortest path from the start state (at depth zero) to $s$.
>
> A state $q$ is considered *accessible* if there is a path from the start state to $q$. A state $q$ is called *co-accessible* if there is a path from $q$ to a final state. Finally, an automaton is called *trim* if all its states are both accessible and co-accessible. This is defined here.

**Question 1**: Consider the minimal trim finite-state automaton $A$ for the language $(L\_1 \cup L\_2) \circ L'$. We observe that this language is also finite. Can we conclude that the number of states in $A$ at level $n$ is 1?

**Question 2**: Consider the minimal trim finite-state automaton $B$ for the language $(L\_1 \cup L\_2 \cup \ldots \cup L\_p) \circ L'$. We observe that this language is also finite. Can we conclude that the number of states in $B$ at level $n$ is 1?

**Argument**: If we let $L = L\_1 \cup L\_2 \cup \ldots \cup L\_p$, the argument is similar: All the strings in $L$ are in the same equivalence class for the Myhill-Nerode congruence for $L \circ L'$, since there is no distinguishing extension for any two strings in $L \in \Sigma^n$. All strings not in $L$ will land in the sink state, which is trimmed out of the minimal trim automaton. Could the proof offered in the previous question work here as well?

**Question 3**: How does the number of states at level $n$ change if we drop the stipulation that these automata be trim and let $\delta$ be a total function?

# Answer
Yes, and yes. This follows from the result in your prior question, letting $L = L\_1 \cup L\_2$ or $L = L\_1 \cup \dots \cup L\_p$.
> 1 votes

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


# Question
Title: What is the order of items being popped and pushed from a stack?
```
    public static void reverseFirstK(Queue<Integer> q, int k) {
       LinkedList<Integer> stack = new LinkedList<>();
       for (int i = 0; i < k; i++) {
            stack.push(q.remove());
        }
        System.out.println(q);
        System.out.println(stack);
        while (!stack.isEmpty()) {
            q.add(stack.pop());
        }
        System.out.println(q);
        for (int i = 0; i < q.size() - k; i++) {
            q.add(q.remove());
        }
        System.out.println(q);
    }
}

```

I was asked to write a program that given a value k and a queue of elements reverses the order of the first k elements of the queue, leaving the other elements in the same relative order. Through trial and error I arrived at the right code, although I don't get why it works.

For the sake of lucidity let the original queue be \[10, 20, 30, 40, 50, 60, 70, 80, 90\]. After the first for loop queue = \[50, 60, 70, 80, 90\] and stack = \[40, 30, 20, 10\]. Why is stack =/= \[10,20,30,40\]? My thought process was remove() removes the first element of the queue, and that push added elements to the end of a stack. So the steps would look something like

1. queue = \[20, 30, 40, 50, 60, 70, 80, 90\],

stack = \[10\]

2. queue = \[30, 40, 50, 60, 70, 80, 90\]

stack = \[10, 20\]

3. queue = \[40, 50, 60, 70, 80, 90\] stack = \[10, 20, 30\]

etc.

Then after the while loop, the queue is \[50, 60, 70, 80, 90, 40, 30, 20, 10\]. What I don't understand here is why is the queue not \[50, 60, 70, 80, 90, 10, 20, 30, 40\] here? My thought process was that pop() removes elements from the end of the stack, and add adds elements to the end of a queue. So the steps would look something like

1. Stack: \[50, 60, 70, 80, 90\] Queue: \[40, 30, 20, 10\]
2. Stack: \[50, 60, 70, 80, 90, 10\] Queue: \[40, 30, 20\]
3. Stack: \[50, 60, 70, 80, 90, 10, 20\] Queue: \[40, 30\] etc.

I would really appreciate some clarification on this.

# Answer
> 0 votes
If you put {int i = 1; i \< 4; i++} into this linked list, you should have:

```
head->1<->2<->3<->4<-tail

```

Now we can dequeue each element, in the case we use java and we use the .remove() function from the Linked List class, we'll take the head element every time - this essentially acts as a queue. The queue will not act to rearrange any of the integers that we put in. We can look at the following to see what putting a queue into a stack would look like. For our purposes, we'll use the same linked list I created:

```
Linked List: head->1<->2<->3<->4<-tail
Stack: head->null

Linked List: head->2<->3<->4<-tail
Stack.push(LinkedList.remove())
Stack: head->1

Linked List: head->3<->4<-tail
Stack.push(LinkedList.remove())
Stack: head->2->1

Linked List: head->4<-tail
Stack.push(LinkedList.remove())
Stack: head->3->2->1

Linked List: head->dummy node<-tail
Stack.push(LinkedList.remove())
Stack: head->4->3->2->1

```

Now let's pop this stack we have: head-\>4-\>3-\>2-\>1. stack.pop() = 4 -\> stack.pop() = 3 -\> stack.pop() = 2 -\> stack.pop() = 1. 4,3,2,1 is the order. Putting a for loop in a queue doesn't do anything if you're just going to dump the queue into the stack.

It's important to note that queues *do not* rearrange data. If you wanted your data to be in original order using a stack, you can use two stacks - put whatever data into one stack and pop it to another stack.

data -\> push to stack1 -\> pop this data and it will be reversed compared to the original; push the data to stack2 -\> pop this data and it will be in its original order.

\[edit\] Just read your comment about how you're confused on what LIFO and FIFO mean:

For first in first out \[FIFO\], we use the queue data structure. We can think of restaurants, the first person to order - unless they order something extravagant - will generally be the first person to get their food and the last person to order food will be the last person to get their food; however, that person will eventually be the first person to order relatively to all orders in the queue.

For last in first out \[LIFO\], the stack data structure, think of a pile of plates at the buffet. The plate on top is always the last plate that was put on. Although it is the last plate, it is the first out.

# Answer
> 0 votes
The result of the stack you observed is based on how the `push()`operation of the LinkedList is implemented in Java, which appears to be the language of your code. If you follow the link, you will see that the **top** is the **front/head** of the LinkedList, hence you get as result `[40, 30, 20, 10]` and not `[10, 20, 30, 40]`.

Of course, you *can have your own implementation* to enforce that the **back/tail** of the LinkedList to be the top and you will obtain `[10, 20, 30, 40]`. However, this should not change how elements are popped because like insert (push), removal (pop) should also be done at the top. So in your implementation where the tail is the top, elements will be removed from the tail, i.e. 40 will be removed first, then 30, and so on.

---
Tags: stacks, queues
---


# Question
Title: Universal lower bound of the multi message problem
The multi message problem is: Let there be an undirected graph $G = (V,E)$ with $n$ vertices, and let $r \in G$. The algorithm sends a message $M\_i$ of size $\Omega(\log(n))$ to each vertex $v\_i$ using the shortest path.

The cost of the problem is the sum of route length multiplied by the message size. Let denote the cost of the problem as $Comm(MM)$, when a graph $G$ is picked then $Comm(MM,G)$, and when a vertex $r$ of $G$ is picked then $Comm(MM,G, r)$.

I want to prove or disprove the following: For every Graph $G$, there exists a vertex $r$ in $G$ such that $Comm(MM,G, r) = \Omega(nd\log(n))$, where $D$ is the graph diameter.

My initial approach was to try and prove this claim, and I intended to use the central vertex of each graph. However, it didn't lead me anywhere.

Then, I did the following. There are vertices $u, w \in V$ such that $dist(u,w) = D$. Let's denote $w = v\_{D}$. So there is a vertex $v\_{D-1}$ such that $dist(u,v\_{D-1}) = D - 1$, and vertex $v\_{D-2}$ such that $dist(u,v\_{D-2}) = D - 2$, and so on until $v\_1$. But here I again got stuck, because I still don't know anything about the rest of the $n-D$ vertices.

I'm still not sure if I should prove or disprove this claim.

Help would be appreciated!

# Answer
The claim is correct. Let there be two vertices such that $\text{dist}(u, w) = D$. Note that for every vertex $v$ we know $\text{dist}(u, v) + \text{dist}(v, w) \geq D$ due to the triangle inequality. If we will sum this over all vertices $v$ we get $$ \sum\_{v}{\text{dist}(u, v)} + \sum\_v{\text{dist}(v, w)} \geq nD $$ This means at least one of $\sum\_{v}{\text{dist}(u, v)}$ or $\sum\_v{\text{dist}(v, w)}$ is greater than $\frac{nD}2$, and if you'll choose that one as $r$ you'll get a cost of $\Omega(nD \log(n))$.
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, distributed-systems, lower-bounds
---


# Question
Title: Compiler optimization pass joining identical function definitions together (or specializing them)
Consider this program transformation, *in any direction*, written in ANF:

```
let f = λx.a in                     let f = λx.a in
let g = λx.a in         <->         b[f/g]
b

```

In the above, `f` doesn't appear free in `a`, and both `f` and `g` appear free in `b` (so only `f` appears free in `b[f/g]`). Or course, this can be written in a CPS IR as well:

```
letfun f x k = a in                     letfun f a k = a in
letfun g x k = a in         <->         b[f/g]
b

```

Are there any papers on compilers which mention or study the above rules for optimization, *preferably* treating the IR as a rewriting system? Looking from left to right, this looks like *common subexpression elimination*, as I'm joining two equivalent function definitions into a single one, but I don't remember seeing this being applied to function definitions. Looking from right to left, this looks like *function specialization*, but I'm not sure where this been approached through rewriting. Though I'm most interested in ANF and CPS, any refereces with similar rules for SSA (joining or spliting equivalent functions or blocks) would be welcome as well.

# Answer
There's no reason why this can't be thought of as common subexpression elimination, except of course that it's made trickier by requiring some kind of $\alpha$-renaming.

Another way to think of this is as a *fold transformation*. This isn't "fold" like in Haskell, a specific iteration pattern over a list, but the opposite of "unfolding" (i.e. inlining).

Optimisations based on unfold/fold were (and probably still are) particularly popular in compilers for logic languages. See, for example: Seki (1993), *Unfold/fold transformation of general logic programs for the well-founded semantics*.

You can see the connection by thinking of it this way. Going from left to right is "fold" of the definition of `f`, and from right to left is "unfold" of the same definition:

```
let f = λx.a in                     let f = λx.a in
let g = λx.a in         <->         let g = f
b                                   in b

```

The reason why you probably haven't discovered this is that it's not usually thought of like common subexpression elimination, but rather a technique for partial evaluation. The "fold" transformation is how you generate recursive definitions.

Most proof assistants based on lambda calculus have a "fold" tactic.

For more information, see: Zhu (1994), *How powerful are folding/unfolding transformations?*
> 2 votes

---
Tags: reference-request, compilers, functional-programming
---


title: Design of opening structuring element

text:
# Question
Title: Design of opening structuring element
I want to find an appropriate structuring element so that only the indicated pixels (by X) are removed as a result of an opening operation, while all other image points remain unchanged. I know how to do opening operation but designing the kernel is very confusing. Is there a simple way to this by inspection?

# Answer
> 0 votes
If I am right, a structel made of the gray shape minus the two $X$ pixels will do. Erosion yields a single pixel, where the structel covers only gray pixels, and dilation will recreate the structel. \[Beware of the confusion with the dual.\]

---
Tags: computer-vision
---


# Question
Title: Does $\texttt{Oracle-SAT} \leq_T^P \texttt{SAT} \iff \texttt{P} \neq \texttt{NP}$, and is this possible?
The problem of Oracle-SAT is given below:

> Given oracle query access to some machine, $U$ that has $2^N$ inputs, determine if there is an input such that the machine accepts.

This is very similar to the regular SAT problem. The only alteration in SAT is that we are given the structure of the circuit; i.e. the CNF formula.

Oracle-SAT is clearly intractable, as we would need to examine all $2^N$ inputs. And SAT is thought to also be intractable, as $P \neq NP$.

Is it possible for Oracle-SAT to reduce to SAT? I am using the notion of Cook-reduction here. If we had an oracle that solved SAT, could we also solve Oracle-SAT in Polynomial time?

If it possible for Oracle-SAT to reduce to SAT, then this would imply $P \neq NP$, right?

# Answer
Oracle-SAT is not $\leq\_{\mathrm{T}}^P$-reducible to any formal language $L$. The reason is that any such reduction would only be able to query the oracle $U$ on a polynomial number of inputs, in addition to the queries made to $L$. If $U$ returns "no" for all the inputs it is asked about, the correct answer could still be either "yes" or "no", however, the entire computation performed by the reduction (with access to $L$) would act in the very same way regardless.
> 1 votes

---
Tags: turing-machines, p-vs-np, oracle-machines
---


# Question
Title: Are there NP COMPLETE problems that are "easy" in practice?
NP COMPLETE problems are hard in the worst case (assuming $P \neq NP$). What that means is that for every polynomial $p$, sufficiently large integer $n$, and algorithm $A$, there is an instance $x$ of size $n$ for which the algorithm takes more than $p(n)$ time. But this is *one instance* for every (sufficiently large) $n$. In principle, this could be the only hard instance for that value of $n$, and all other instances for that $n$ could be easy. So how hard are NP COMPLETE problems in practice?

I'll refine that question to: Are there NP COMPLETE problems that are somehow easy in practice?

The definition of "easy" is left open. One definition may be given by average-case complexity, another one could be given "smooth complexity", another could be given by Fixed Parameter Tractability, efficient approximability, polynomial-time solvability with an advice oracle, efficiency in practice without a mathematical definition etc. I'm hoping that by leaving the definition of "easy" open, I can get a wider range of answers. Any definition of "easy" should imply that the problem is easy "in real life" or "in practice". Also, don't assume I know any of that stuff I just listed in any detail.

# Answer
Honestly, SAT seems pretty easy in practice. SAT solvers are routinely used on instances with millions of variables that arise in model checking against formal specifications.
> 9 votes

# Answer
That a problem is NP-complete means just that the worst case is hard. It might well be that such worst cases are extremely rare, or just don't show up in the "usual" cases of interest, and that non-worst-cases instances are easy to solve.

To classify a problem as "usually easy" you'd have to specify the (distribution of the) inputs to consider, and check that the instances of interest are indeed (very often) easy. Both are very hard tasks, all you can do is to rely on avaliable experimental experience. Perhaps there are some NP-complete problems where it can be shown that all instances are equally hard, but I'm not aware of any.

For a somewhat off-topic example, the SIMPLEX algorithm is routinely used to solve huge linear programming problems. It turns out that the worst case of the algorithm is exponential --- but bad cases don't show up in practice, they seem to be extremely contorted.
> 4 votes

# Answer
Problems which are easy to approximate, like the Euclidean Traveling Salesman problem.

These are problems for which polynomial-time approximation scheme (PTAS) approximation algorithm do exist.

> A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε \> 0 and produces a solution that is within a factor 1 + ε of being optimal (or 1 – ε for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most (1 + ε)L, with L being the length of the shortest tour.
> 4 votes

# Answer
See this question: A greedy algorithm for the bottle filling problem

I added a proof that this problem is NP-complete. However, practical instances of the problem will usually be quite easy to solve; the proof transformed the knapsack problem into highly unusual instances of this problem.

PS. Why is this problem usually easy? Look at the link where the problem is described, and what people think of it. Look at the obvious method you would use to solve it. What will happen is that you could have a large problem, say size 10,000 (which is beyond hope for many NP-complete problems), you use the obvious method to solve it, and you will be left with an NP-complete problem - which usually has a *tiny* size, often size 1, unless the original problem is carefully constructed so that the NP-complete subproblem is large.
> 2 votes

---
Tags: complexity-theory, np-complete, average-case
---


# Question
Title: Unions of PSPACE-comlete problems that are PSPACE-complete?
Let $A,B\subsetneq\Sigma^\*$ be PSPACE-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^\*$ and $A\cup B\in\mathrm{PSPACE}$. Does it follow that $A\cup B$ is PSPACE-complete?

---

In general, is there a sufficient condition for the union of PSPACE-hard (or complete) problems to be PSPACE-hard (complete)?

# Answer
> 4 votes
> Let $A,B\subsetneq\Sigma^\*$ be $\text{PSPACE}$-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^\*$ and $A\cup B\in\text{PSPACE}$. Does it follow that $A\cup B$ is $\text{PSPACE}$-complete?

The condition "$A\cup B\in\text{PSPACE}$" is redundant since it is always true given that $A,B$ are $\text{PSPACE}$ problems.

It does not follow that $A\cup B$ is $\text{PSPACE}$-complete.
For example, let $A$ be a $\text{PSPACE}$-complete language. Let string $s\notin A$. Let $B=\overline A \setminus\\{s\\}$, which is a $\text{PSPACE}$-complete language. $A\cup B=\Sigma^\*\setminus\\{s\\}\not=\Sigma^\*$ is a language for which the membership problem can be determined in constant space (and constant time). $A\cup B$ is not $\text{PSPACE}$-complete.

---

I don't think people have established any sufficient condition for the union of $\text{PSPACE}$-hard (or complete) problems to be $\text{PSPACE}$-hard (complete) except the obvious ones.

Here is an obvious one. If $A$ is a $\text{PSPACE}$-complete language in which all strings start with $0$ while $B$ is a $\text{PSPACE}$-complete language in which all strings start with $1$, the $A\cup B$ is a $\text{PSPACE}$-complete language.

---
Tags: complexity-theory, space-complexity, complexity-classes
---


# Question
Title: Would edges with negative weights affect Prim's Algorithm?
I was studying graphs and it got me wondering if edges with negative weights affected the outcome of Prim's Algorithm in finding a minimum spanning tree. So would the Prim's algorithm still find a suitable MST unaffected by negative weights on the edges of the graph?

# Answer
If you add a sufficiently-large constant to every edge of your graph, large enough to make all the edges positive, would the algorithm perform any different on the original graph than it would on this increased-weight version?
> 2 votes

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


# Question
Title: Bundle diameter calculation algorithm with different wire sizes?
I would like to ask if anyone happens to know an algorithm or idea how to implement a way to calculate the bundle diameter given a multiple wires with different sizes. Something similar to graphical solution below

# Answer
Your problem is studied under the terminology of "**circle packing**." Specifically, packing unequal circles in a circle.

Beware that many resources that study 'circle packing' in a circle often consider just the problem of uniform-sized circles (as this problem is hard enough!) rather than your more general framework of unequal circles. See, for example, the Wikipedia page on circle packing: https://en.wikipedia.org/wiki/Circle\_packing This mostly refers to uniform circles in a circle, but it does link to a page on packing unequal spheres (which is different than just your circular cross-section).

Here is a presentation that surveys a number of algorithms/strategies for packing circles in bounded spaces: https://www.math.uwaterloo.ca/~ervrscay/talks/Jiang-AMMCS-CAIMS-2015.pdf

Here is a Python implementation of unequal circle packing in a circle: https://scipython.com/blog/packing-circles-in-a-circle/ This solution produces a set of random circles, so if you have a specific problem instance with your wire widths, you would use those as input instead of the randomly-generated circles it creates. The algorithm works by sorting the circles by their size and placing the largest circles first.
> 4 votes

---
Tags: algorithms
---


title: 4-regular graph without small cycles

text:
# Question
Title: 4-regular graph without small cycles
My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 4-regular graph that does not have small cycles. For example, I want to generate a 4-regular graph of size $O(k^c)$ that does not have any cycles of size $k$ or less ($k$ and $c$ are some positive integers, and $c$ is considerably small). I have thought of a cycle of size $O(k^c)$ to start with, and I can't quite figure out the other type of adjacency between the vertices (as all the vertices need to have another two vertices adjacent to them to make the graph 4-regular).

# Answer
When you say you want a graph without cycles of size $k$ (or less), you are asking for a graph with **girth** $k+1$. When restricting your interest to 4-regular graphs, since you are asking for an upper bound on the size of your graph, you would be interested in an $(r,g)$-cage, which is a $r$-regular graph of girth $g$ with as few vertices as possible.

In your case, you are asking about $(4,k+1)$-cages, and it seems you are asking if such things exist. It is known that $(r,g)$-cages exist for every $r \geq 2$ and $g \geq 3$. See: https://en.wikipedia.org/wiki/Cage\_(graph\_theory)

For example, the Robertson Graph:

is 4-regular and contains no cycles of size 4 or less and it is the smallest such graph with just 19 vertices.

See also: https://mathworld.wolfram.com/CageGraph.html for asymptotic upper and lower bounds for general $(r,g)$-cage sizes.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Can all LL(k) grammar can be recognized by LR(1)?
For context free languages, I wonder that if all LL(k) languages can be recognized by a LR(1) grammar?

# Answer
> 0 votes
Yes. See Language theoretic comparison of LL and LR grammars. In particular, https://cs.stackexchange.com/a/48/755 says $LL \subset LR(1)$, where $LL = \cup\_k LL(k)$, hence $LL(k) \subseteq LL \subset LR(1)$ for all $k$.

See also Does my grammar contradict LL ⊆ LR(1)?. Make sure to distinguish between a grammar vs the language accepted by the grammar.

---
Tags: compilers, parsers
---


# Question
Title: Minimal number of comparisons - sorting $6$ elements
I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ?

**Algorithm**
1. Sort $a\_1, a\_2, a\_3$ and $a\_4, a\_5, a\_6$.
Number of comparisons: $3+3=6$.
2. Merge two subarrays.
Number of comparisons: $3 + 3 - 2 = 4$.
Total number of comparisons: $6 + 4 = 10$.

# Answer
According to A036604, 10 comparisons are indeed optimal. The link probably contains a citation to a paper proving this.
> 0 votes

# Answer
TL-DR; $10$

Yes, you need to have possibility to ask up to $10$ questions to (comparison) sort an array of $6$ elements.

However, it is possible to create an optimal algorithm that will require no more than 10 questions in worst case, but in average **only** $9.57777$ questions (in $416$ cases $10$ comparisons, in $304$ cases only $9$).

Here is a decision tree for sorting 6 element arrays \[a,b,c,d,e,f\]. To make it more compressed. I assumed that already $a\<b$ , $c\<d$ and $e\<f$ has been asked (3 comparisons) and in case of false proper pair has been swapped:  As you can see, in addition to these 3 comparisons, we need up to 7 more, but often only 6 that gives us the $9.57777$ in average.
> 4 votes

---
Tags: algorithms, sorting, lower-bounds
---


# Question
Title: Recovering data from under sampled data streams
I’m trying to analyze a repeated data stream from a sensor. The data probably has events at the 100us scale, it occurs at a fairly random interval, and the signals are extremely similar. The problem is that I don’t have any sensors that have sub-millisecond refresh rates. The best I can do with what I have is about 1ms sensor reads.

So . . .

The idea is that if I sample a large number of event the chances are that the sampling ticks are falling on different sections of the signal. If this is true then a series of 10-20 events should give me the data that I need to reconstruct the signal. The signals repeat in a fairly random fashion and are very similar in each dataset so the chances are that each sampling run is gathering “pieces” of the total dataset.

Is there a name for this sort of procedure so that I can start to research how to do it? Are there algorithms or toolsets in the open source world to accomplish this task?

Right now I’m literally graphing the data on graph paper and overlaying the image. This is less than ideal . . .

# Answer
> 1 votes
If the events occur at random, unknown times, all you can get are random samples of the signal, and by collecting enough of them, the statistical distribution of the signal values.

If the signal is known to be monotonic, say increasing, with a neglectable falloff time, you can retrieve it by inverting the cumulative density function. Otherwise, the reconstruction does not seem possible.

# Answer
> 0 votes
It's not the same, but it reminds me of super-resolution.

---
Tags: sorting
---


# Question
Title: How does pre-training help with semantic segmentation with U-net
I am working with a u-net, a variation of the more commonly known fully convolutional network for semantic segmentation. For training a u-net, I was given the suggestion that I should use a pre-trained network. But, I'm not quite sure how this makes sense.

My understanding is, in pre-training, we freeze the network up to the final classifying layers from a pre-trained network and then, we initialize random weights for the classifying layers. Then, we take our new dataset and retrain the weights through the whole network. Basically, we don't have random initialized weights for the convolutional blocks.

Now, if I'm using something like the u-net which has a very unique structure, how exactly would I do this pre-training with something like vgg16? The only thing I can think of is to share the feature maps during the upsampling layers but that's about it and that's not really pre-trained weights.

# Answer
> 1 votes
The procedure you described is how to do fine-tuning of a network for object classification. There are two standard techniques: (1) freeze all but the last few layers, replace the last layers with new layers of the appropriate size and random weights, and train them; or (2) train all of the layers, starting from the weights of the pre-trained model as your initial weights, but use a very low learning rate. You can also do (1) then (2). See https://datascience.stackexchange.com/q/28383/8560 for a nice overview.

I'm not an expert on u-nets, but it appears they are used for image segmentation rather than object classification. Therefore, the same approach of freezing the last few layers probably isn't suitable here. You can still use method (2), i.e., fine-tuning using stochastic gradient descent with a very low learning rate. If your task is similar enough to the task the pre-trained network was trained for, that might be effective.

I can't see any way to use a pre-trained model for object classification (like VGG16), as they use a different architecture. Rather, you'd probably have to start with a pre-trained model for segmentation (i.e., a pre-trained U-net model). The U-net paper says that they make pre-trained models available on their website, which perhaps you could use as a starting point.

# Answer
> 0 votes
The pre-trained model is used as the encoder model within the U-Net.

For a high-level example, see this github below, in which pre-trained encoder is specified as input arg for the U-Net segmentation model. https://github.com/qubvel/segmentation\_models.pytorch

---
Tags: neural-networks
---


# Question
Title: Difference between paradigm and Algorithm in Machine Learning
Give a class $\mathcal{H}$ of predictors from the set X to $\\{0,1\\}$. Here each $h \in \mathcal{H}$ is a function from $h: X \longrightarrow \\{0,1\\}$. The Empirical Risk Minimization is defined as

$$ERM\_{\mathcal{H}} \in Arg min\_{h \in \mathcal{H}} (L\_s(h))$$ Where $S=\\{(x\_1,y\_1,\cdots,(x\_m,y\_m))\\}$ is a sample $L\_S(h)$ denotes the loss of hypothesis $h$ on the sample $S$.

The goal of the learner is to find an $h$ with as small loss as possible.

In the above it is paradigm not an algorithm. I am not getting the point why it is not referred as algorithm?

Link-

> Video Link

# Answer
A paradigm is an abstract concept. It is a general method useful to know to solve a problem or construct algorithms, but not a particular algorithm. In your example, the paradigm is to minimize the empirical risk. But it does not say how to perform the minimization concretely.
> 3 votes

---
Tags: algorithms, machine-learning
---


# Question
Title: Unstable nature of Lomuto partition scheme
In undergrad Quicksort implementation, Lomuto partitioning scheme is used. We are taught that Quicksort is an unstable partitioning algorithm which is cause of the extra swaps that occurs even when pivot is equal to the element at index j.

```
Lomuto-Partition(A, p, r)
    x = A[r]
    i = p - 1
    for j = p to r - 1
        if A[j] <= x
            i = i + 1
            swap( A[i], A[j] )
    swap( A[i + 1], A[r] )
    return i + 1

```

My question is what would happen if we remove the equality at the condition check ie instead have

```
Lomuto-Partition(A, p, r)
    x = A[r]
    i = p - 1
    for j = p to r - 1
        if A[j] < x
            i = i + 1
            swap( A[i], A[j] )
    swap( A[i + 1], A[r] )
    return i + 1

```

This should make it a stable implementation and would reduce the extra swaps needed. Or will it break the algorithm somehow?

# Answer
As @YuvalFilmus pointed out it still won't solve the problem. Even if we can avoid the extra swaps when elements are equal to the pivot, the last swap (A\[i+1\], A\[r\]) can result into the order getting changed as the pivot will be swapped into it's correct place.
> 1 votes

# Answer
The partitioning scheme is not stable because of this: it focuses on gathering elements lower than the pivot into a lower partition of the table. But as it is doing so, it kicks elements out of that lower partition to make room. It has nowhere to kick an element, other than by exchanging it with the element which is taking its place, coming from the unprocessed upper partition. While moving elements into the lower partition preserves their order, the moving of the elements out of the lower partition into the upper partition does not preserve their order. Doing that would require either external storage, or bulk moves within the upper partition (which would cause the partitioning to have $O(n^2)$ worst case behavior).

Example: suppose we have $\[6\_1, 2, 3, 7, 6\_2, 1, 6\_3, 5\]$. Suppose our pivot value is 5.

We begin with an empty lower partition, and compare $6\_1$ to $5$. Then compare $2$ to $5$. That element is lower so we swap it into the lower partition: $\[2| 6\_1, 3, 7, 6\_2, 1, 6\_3, 5\]$. The $6\_1$ is arbitrarily booted out to the position previously occupied by $2$.

Next, we continue: $3$ is lower than $3$, so we add it to the partition. Now we again boot the $6\_1$ out: $\[2, 3| 6\_1, 7, 6\_2, 1, 6\_3, 5\]$.

Now we keep going with $7$. That stays in the upper partition, since it is greater than 5. Likewise $6\_2$.

Then we get to the $1$. **Here the problem is seen.** 1 is less than the pivot 5, so we move it into the lower partition. To do that, we have to kick $6\_1$ out of the way again. We move it into the position occupied by 1. And, thus, stability is wrecked, because $6\_1$ has jumped over $6\_2$: $\[2, 3, 1| 7, 6\_2, 6\_1, 6\_3, 5\]$.
> 1 votes

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


# Question
Title: Generate clues to a puzzle so that it always has a solution
I have come across this question in an abstract reasoning test:

Each of the dots do something unique to the initial shape and is consistent for that column of dots. Assuming each of the functions the dots perform are independent to each other, how would I randomly generate a question like this in a way that is always solvable?

# Answer
> 1 votes
In some sense these questions are never solvable, because the problem is ill-defined. There always exists multiple candidate solutions that are consistent with the information provided. As such, a mathematician who is being pedantic might say these types of questions are lame.

Let me give you an analogy. I'm thinking of a sequence of integers that begins with 1, 2, 3, 4. What is the next number in the sequence?

If you said 5, then nope, you are wrong, that is not the next number I was thinking. Actually, I was thinking of the Ulam numbers, so the next number is 6, not 5.

Of course that question was silly. And for the same reason, the question you list is silly in the same way. It is possible to come up with multiple sets of geometric transforms that are consistent with the conditions in the "Base screen", but that lead to a different answer for "Question 1". Now some of those transforms might look rather convoluted or non-trivial, so maybe you would consider them unlikely or implausible, but to make that systematic, you need to have an assumption on what set of transformations are allowed, or a prior on which ones are likely -- and none of that is specified in the question.

So, the pedantic answer to your question is: you can't randomly generate a question like this in a way that is always solvable, because such questions are never solvable -- there are always multiple valid solutions.

---

I suspect you won't be happy with that answer. So, I'm going to give you an alternate approach that is an attempt to do something of the sort you're mentioning. But realize that it has limitations, because of the above discussion. One reasonable approach would be to start with a universe $U$ of allowed geometric transforms. You'll have to pick that universe: maybe it includes flipping the image left-right, flipping the image up-down, zooming in, zooming out, adding a horizontal line between the left-most and right-most points in the image, and so on -- you pick what's allowable. Now, generate a random candidate question by randomly picking a mapping from each dot to an element of $U$, and then randomly picking the "base screen" and "question 1". In other words, randomly generate the original figures, in each row randomly generate the on-off patterns for the dots, and compute the associated "final figures" for the "base screen". This will ensure that there exists at least one valid solution. Now, check that the solution is unique by exhaustively enumerating all possible mappings from the dots to elements of $U$, testing which ones are consistent with the "base screen", and for ones that are consistent with the base screen, computing the answer to "question 1". If there exists more than one valid answer to "question 1", then discard all of your choices and start over again.

---
Tags: algorithms
---


# Question
Title: Boolean constraints for a connected component of a graph
Suppose I have an undirected graph $G=(V,E)$, and boolean variables $x\_v$ (one for each vertex $v \in V$). These variables select a subset $S \subseteq V$ of vertices, namely the vertices $S=\\{v \mid x\_v\\}$ whose corresponding boolean variable is true.

I want to express the constraint that $S$ is connected, i.e., that the vertices selected by the $x\_v$'s form a connected component in $G$. How can I do that, in a way that can be used with a SAT solver or ILP solver?

Equivalently, this can be viewed as enforcing the constraint that all of the vertices in $S$ are reachable from each other, so this can be viewed as how to encode reachability constraints in SAT.

# Answer
> 1 votes
Here is one encoding. Introduce boolean variables $x\_{v,i}$, with the intended meaning that $x\_{v,i}$ is true if $v$ is selected and $v$ can by reached by a path of length $\le i$ from $s$ (where $s$ is some starting vertex).

You can force the $x\_{v,i}$'s to have the desired meaning, by adding the following constraints:

* Exactly one of the $x\_{v,0}$'s is true. For a SAT solver, this can be encoded using the methods in Encoding 1-out-of-n constraint for SAT solvers. An ILP solver can encode this directly.
* If $x\_{v,i}$ is true, then $x\_{v,i+1}$ is true. This can be enforced with the CNF clause $\neg x\_{v,i} \lor x\_{v,i+1}$ or the linear inequality $x\_{v,i} \le x\_{v,i+1}$.
* If $x\_{v,i+1}$ is true, then there is a $u$ such that $x\_{u,i}$ is true and either $u=v$ or $u$ is a neighbor of $v$. This can be enforced with the CNF clause $\neg x\_{v,i+1} \lor x\_{v,i} \lor x\_{u\_1,i} \lor \cdots \lor x\_{u\_k,i}$ where $u\_1,\dots,u\_k$ are the neighbors of $v$; or with the linear inequality $x\_{v,i+1} \le x\_{v,i} + x\_{u\_1,i} + \dots + x\_{u\_k,i}$.
* $x\_v = x\_{v,n}$ where $n=|V|$ is the number of vertices in the graph.

---
Tags: graphs, satisfiability, integer-programming, connected-components, connected
---


# Question
Title: A problem similar to the Packing problem
There are $n$ students want to order food online. They plan to eat pizza. Each student has several favorite toppings (such as mushrooms, onions, garlic, sausage, etc.). Each student wants to eat at least half a pizza, and the toppings on the pizza must be her/his favorite Assuming that each pizza can only add one topping, consider the following questions:

1. How many pizzas you can order to satisfy each student? Is it NP-hard or is there a polynomial time algorithm?
2. If each person eats at least one-third of the pizza, and the toppings on the pizza must be what she/he likes, how many pizzas you need to order to satisfy each student? Is it NP-hard or polynomial solvable?

I don't know how to model it, can someone help me?

# Answer
> 1 votes
In any scenario/students' choice of toppings, you don't have to order more than $n$ pizzas - each student picks one for themselves with one of their favorite topping.

Another observation - you will always have to order at least $\lceil\frac{n}{2}\rceil$ pizzas, because any student can eat no less than half a pizza. If there weren't any constraints on toppings, what you could do is divide students into groups of $2$ (with one group of size $1$ if $n$ is odd), and let each group order a pizza of their choosing. Note that you wouldn't be able to "move" any of the students to another (fully populated) group, because then they would have to divide their pizza into more parts than is allowed ($2$ in this case). Basically, this is the pigeonhole principle in action.

For example, if you had $n=5$ students and every one of them wanted garlic on their pizza, you *will* have to order at least $3$ pizzas (even though they will all be the same with garlic as a topping), but you never have to order more than $5$.

With added constraints on toppings, the number of pizzas may be larger than $\lceil\frac{n}{2}\rceil$, but as stated earlier, no greater than $n$.

If you had $n=2$ students, but one of them wanted only garlic, and the other one wanted sausage, you have to order $2$ pizzas to satisfy the constraints (even though $\lceil\frac{n}{2}\rceil=1\<2$)

Those observations lead to a formulation of the problem that focuses more on groups of students rather than pizzas themselves, since each group will have to order a distinct pizza anyway; the objective is to find a grouping of students that satisfies topping constraints (each group gets a pizza such that every member gets what they want) and minimizes the number of groups (which is equal to number of pizzas).

More formally:

*(Edit: added for accuracy)* Let $T = \\{t\_1, t\_2, ...\\}$ be a set of all possible toppings. (for example - $T=\\{mushrooms,onions,garlic,sausage\\}$).

Let $S=\\{S\_1, S\_2, ...,S\_n\\}$ be the family of non-empty sets of students' favorite toppings; $S\_i \in T$ (for example $S\_1=\\{garlic, onion\\}$);

Let $k$ be the maximum number of slices on a pizza (in your original problem, $k=2$, but we can generalize here);

Let $X=\\{X\_1, X\_2,...\\}$ be the family of groups of students (or a "grouping"). Each set $X\_i$ is a subset of $S$ (you can define $X$ alternatively as a partition of $S$).

Constraints:

$S\_i \neq \emptyset$ for each $S\_i \in S$ (everyone has at least one favorite topping).

$X\_i \cap X\_j = \emptyset$ for $X\_i, X\_j \in X$. (groups are disjoint).

$1 \le |X\_i| \le k$ for each $X\_i \in X$. (groups can't be empty, but also no larger than $k$).

$\bigcup\_{X\_i \in X} X\_i = S$ (no students are left out).

$\bigcap\_{S\_j \in X\_i} S\_j \neq \emptyset$ (each group has a common favorite topping).

We want to find a grouping $X$ that satisfies constraints listed above, such that $|X|$ is minimal:

$$(X=?) \implies (|X| \to min)$$

This model takes into account every constraint you listed. At first glance, the problem looks NP-hard with complexity of roughly $O(n!)$ (think of how many possible groupings there are: you can make $n \choose k$ different groups of size exactly $k$, there are at least $\lceil\frac{n}{2}\rceil$ different groups in a grouping, groups can be of different size, and so on...)

Unless there's some property of the problem I'm missing, you have to search the entire space of groupings to determine the best, hence the problem is computationally hard in the general case. Maybe that's not a problem for small values of $n$?

Also, if you *absolutely* need this problem to be modelled in terms of a classical problem, you can read about the hitting set problem (this is some material I found online that explains it). My first attempt of modelling your problem used the hitting set problem as a basis, but I ran into issues with constraints regarding $k$. What I found, though, is that the hitting set problem is equivalent to your problem if we don't concern ourselves about $k$ (so if a student can eat any amount of pizza to be happy). Since the hitting set problem is in itself NP-hard, I'm inclined to think that your variant (which has more constraints) is similarly complex as well.

***EDIT**: Why is the simpler version equivalent to the hitting set problem?*

We forget about constraints with $k$, that is - a student can now eat any amount of pizza (no matter if it's half of it, a third, or any fraction) to be satisfied. This allows for a simpler model:

$T = \\{t\_1, t\_2, ...\\}$ \- set of all possible toppings.

$S = \\{S\_1, S\_2, ..., S\_n\\}$ \- family of sets of preferred toppings, $S\_i \in T$.

$P = \\{p\_1, p\_2, ...\\}$ \- set of pizzas ordered. Let each element also $p\_i$ describe a topping of that pizza, so for example $p\_3=onion$. (note that each type of topping can be ordered only once and still satisfy constraints, because a pizza can be shared by an arbitrary number of students - there's no need to order two pizzas of the same topping).

We only have one constraint here:

$\forall S\_i : S\_i \cap P \neq \emptyset$ ($P$ intersects each set of student's choices; this guarantees that each student will find a pizza in $P$ that has one of their favorite toppings)

And our objective is minimizing $|P|$: $$(P=?) \implies (|P| \to min)$$

In short, we are finding the smallest set $P$ that has at least $1$ common element with every set $S\_i$, which is the formulation of the hitting set problem. There is no need to worry about dividing students into groups, because as long as each student can find a pizza they like in $P$, the solution is valid.

As I have written earlier, I didn't find a way to extend the simpler model to the variant where a student has to eat at least half a pizza, that's why in the original answer I opted for another approach, independent of the hitting set problem.

---
Tags: algorithms
---


title: SAT polynomial time

text:
# Question
Title: SAT polynomial time
Hi I understood it is not currently possible to solve SAT in polynomial time. Does this mean we can not currently solve an expression with n different boolean variables or with m different symbols in the expression in polynomial time with respect to n?

For example :

( A or B ) and ( not not A and B )

The different number of boolean variables here n is 2 but the number of symbols m is 13.

# Answer
In general, asymptotic complexity concerns itself with the size of the input. In this case, the number of input symbols. SAT is thus not polynomially solvable in the worst case as a function of the number of symbols.

It is also not polynomially solvable with respect to the number of unique variables. This is trivially so, as this is clearly upper bounded by the size of the input.

However, SAT *is* tractable in the special case that the number of unique variables is low. That is, it's Fixed Parameter Tractable with respect to that parameter. Indeed, we can try each assignment to the variables (of which there are an exponential amount w.r.t. the number of unique variables) and verify whether they satisfy the whole formula (which is linear in the size of the formula). Thus with $n$ unique variables and $m$ total symbols, SAT is solvable in O($2^n$m).
> 1 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, logic, satisfiability
---


# Question
Title: Merge K BST of N elements in total into a single RBT in O(N log K) time
I have the following question to solve;

> Given $K$ BST consisting of $N$ total elements, show how you can create a Red Black Tree in $O(N\log K)$ time.

I had the following idea but it falls on the last part of insertion into the red black tree;

Get an inorder scan of each BST (total of $O(N)$) into lists. From each list pick the smallest element (the min) and insert it along with the index of the list it originated from (the key-value pair `(value,list_index)`)into an auxiliary min-heap.
Extract the min value from the auxiliary heap and insert it into the RBT. Now take the next element from the `list_index` list and insert it into the heap.

So the building of the min-heap will take $O(K\log K)$ time ($K$ insertions into the min heap which at most will take $\log K$ time).
Extracting the min $N$ times will take $O(N\log K)$ time.
Inserting into the RBT $N$ times will take $O(N\log N)$ time \<-- This is the issue.

As I understand it - the first insertion will take $O(\log 1)$, the next $O(\log 2)$, etc. until we have inserted all $N$ elements - resulting in a total of $O(N\log N)$ instead of the desired $O(N\log K)$.

Anyone has any idea how to perform this in the wanted time or where my solution is wrong?

# Answer
Your idea of maintaining a min-heap of $K$ elements of the form `(value,list_index)` is great.

You "extract the min value from the auxiliary heap and insert it into the RBT". When you insert it into the RBT directly, you are not taking advantage of the information that it is the largest element so far. You are treating it just like an arbitrary element, which slows down your algorithm.

Initialize an empty list of capacity $N$. Append the extracted min value from the auxiliary heap to the list every time instead. The initialization and all $N$ appendments cost $O(N)$ time.

From the list at last, which is a sorted list of $N$ elements, we can build an RBT in $O(N)$ time. (In fact, given a sorted list of $N$ elements, we can build any given type of BST in $O(N)$ time. Or any type of BST that I know of).
> 0 votes

---
Tags: algorithms, time-complexity, binary-search-trees, red-black-trees
---


# Question
Title: Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier
For this question I figure we need to define a system of linear inequalities which I thought could be something like this :
a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X
a1x1 + a2x2 + ... + anxn ≤ b if (x1, x2, ..., xn) ∈ Y
I'm not sure whether this would be correct or how to continue the proof from here. Any help would be appreciated.

# Answer
Consider the system of inequations having the $a\_k$ and $b$ for unknowns.

$$\forall x\in X:\sum\_{k=1}^n x\_ka\_k-b\ge 0, \\\forall y\in Y:\sum\_{k=1}^n y\_ka\_k-b\< 0.$$

This system is made of a polynomial number of equations in $n+1$ unkonwns. By the Linear Feasibility, you can determine if the system has a solution in polynomial time.

And by its definition, a solution does constitute a linear classifier.
> 1 votes

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


# Question
Title: What is lambda caculus's "fix point combinators" corresponding to Turing Machine?
The lambda caculus equals to Turing Machine,so What is lambda caculus's "fix point combinators" corresponding to Turing Machine?

according to the paper \<Primitive Rec, Ackerman's Function, Decidable, Undeciable, and Beyond Exposition by William Gasarch\>,Turing Machine can:

The machine acts in discrete steps. At any one step it will read the symbol in the \tape square", see what state it is in, and do one of the following:

write a symbol on the tape square and change state, move the head one symbol to the left and change state, move the head one symbol to the right and change state. so what's the "fix point combinators" corresponding to?I think its 2 and 3:"the head can move left and right",it can "the head can move left and right",so it can loop,and "fix point combinators" support loop too

am I right?Thanks!

# Answer
> 4 votes
The lambda calculus is not "equal" to Turing machines. There is a correspondence, but it is not equality, it's one of simulation. You should not expect every aspect of one to have a corresponding counterpart in the other. For instance, it does not make sense to ask "what does the Turing machine head correspond to in lambda calculus?"

Having said that, there is a more high level correspondence. The fixpoint combinator implements *general recursion* in lambda calculus. In command-based languages the (vague) counter-part is *iteration*, i.e., `while` loop. And Turing machines are capable of iterating a sequence of actions. However, the correspondence beteween recursion and iteration goes beyond both Turing machines and lambda calculus, so it's not really an answer specific to your question.

---
Tags: turing-machines, computability, lambda-calculus, functional-programming
---


# Question
Title: Exactly what is the difference between Finite Automata and Transition Graphs?
I haven't found a good enough answer by googling. Here's what i know:

1. TG's can have more than one initial state
2. In TG's, Edges/transitions can be labelled with strings
3. In TG's, it is not necessary to show transitions for all letters

Notes:

* I am talking about plain TG's, not GTG's and DFA's only not NFA
* Only thing i know about NFA's is that each a state can have multiple transitions for the same letter, so please keep that in mind if hte answer invloves NFA's
* Links would be appreciated.

# Answer
Your nomenclature is highly nonstandard. It seems that "finite automata" are what are usually known as DFAs, whereas "transition graphs" are a special case of GNFAs in which the only regular expressions allowed are words; alternatively, they are like $\epsilon$-NFAs, only transitions can be marked by arbitrary words (rather than just words of length at most 1).

There are two differences between your FAs and your TGs:

1. FAs are deterministic: at each point in time, there is exactly one choice of which state to go to next. There is no such restriction on TGs. Moreover, whereas FAs have a unique initial state, TGs have an arbitrary number of initial states.
2. Transitions in FAs are labeled by symbols. In contrast, transitions in TGs are labeled by words.

These are exactly the differences that you listed.
> 1 votes

# Answer
TL;DR version: Your initial statement was accurate - I'll add some more clarity (hopefully) for people who come across this post later on:

The formal definition (from Daniel I.A. Cohen):

A **transition graph**, abbreviated TG, is a collection of three things:

1. A finite set of states, at least one of which is designated as the start state ( - ) and some (maybe none) of which are designated as final states ( + ) .
2. An alphabet I of possible input letters from which input strings are formed.
3. A finite set of transitions (edge labels) that show how to go from some states to some others, based on reading specified substrings of input letters (possibly even the null string ***lambda*** ).

I'll use **TG** to refer to **transition graphs** and use **FA** to refer to **finite automata**.

My notes on features of TGs:

* A TG can have multiple *start* states, while a FA cannot
* A TG can have ***lambda*** on an edge, while a FA cannot
* A TG can have an entire string on an edge, while a FA cannot
* A TG is non-deterministic; It can have multiple possible paths while following the input string. If even ONE of these paths leads to an accept state, the string is accepted.
* A TG can *crash* because its transition functions do not constitute **total functions**, which means functions that provide output for the entire domain of input (in other words, in a FA, you NEED to consider all possible input at each state - with a TG you do not.)

It is also important to note that any TG can be converted to a FA. Part of the underlying theory of Kleene's theorem is that if a TG exists, OR an FA exists, or a regular language exists for a language, then *they all have to exist*.

**Additional information:**

Transition Graphs are a relaxing of the notion of a finite automaton. It's a bit confusing, because the diagrams of machines in general are often called **state transition *diagrams***. But other authors (e.g., Lenz) refers to the diagrams (visuals) themselves as **transition graphs**.

However, the notion of a **Transition Graph (TG)** isn't "non-standard nomenclature" as has been suggested. It is probably less popular now, but this type of machine was originally discussed in *Finite Automata and the Representation of Events* by J. Myhill in 1957. It was made very popular in semi-modern times by Daniel I.A. Cohen's excellent (classic) book, *Introduction to Computer Theory*, specifically in chapter 6 (in the 2nd edition, 1997). Cohen was one of Alonzo Church's Ph.D. candidates, so I don't think this was just a matter of some no-named researcher trying to make a certain term or concept popular.
> 1 votes

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


# Question
Title: Ticket Dispenser algorithm and the size of the Ticket array
The following is a ticket Dispenser Mechanism, it's from the article:

"Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion By Robert Danek and Wojciech Golab" http://www.cs.toronto.edu/~rdanek/fcfs\_disc.pdf

```
shared variables:

Tickets: array[0..7N-1] of {INUSE, FREE } initially Tickets[0..(3N-1)] = FREE

and Tickets[3N..(7N-1)] = INUSE

lastTicket: 0..7N-1 initially 7N-1

private variables: ticket: 0..7N-1 uninitialized

```

```

Implementation of ObtainTicket():

45 first := lastTicket 46 i := 1 // Find upper bound on the smallest FREE ticket.

47 while i < 3N ( Tickets[(first + i) mod 7N] = INUSE do

48   i := min {3N, i x 2 } // Now do binary search to find the ticket.

49 last := first + i 50 while first < last do

51 midpoint := RoundDown[(first + last )/2]

52 if Tickets[midpoint mod 7N] = INUSE then

53 first := midpoint + 1

54 else

55 last := midpoint // At this point first = last holds.

56 ticket := first mod 7N

57 Tickets[ticket ] := INUSE

58 return ticket

```

```
Implementation of DoneWithTicket(): // Reset a ticket that was previously active.

59 Tickets[(ticket + 3N) mod 7N] := FREE

60 lastTicket := ticket

```

Why do we need 7N tickets and not 3N ?, it seems to suffice if every process can run this function and bypass us up to 3 times while process p is inside (It's Guaranteed according to the paper)

The 7N size is not explained in the paper whatsoever..

# Answer
> 0 votes
In the paper, it says:

> Specification 1.
>
> * a) The domain of tickets is the set of integers modulo mN for some integer m ≥ 3.
> * b) At any time, the set of tickets that are active is confined to some interval of fewer than mN/2 consecutive integers modulo mN.

According to their specification, the active tickets should be less than half the domain size. So if there are 3N active tickets, the next available integer $m$ that will ensure $3N$ is less than half of $mN$ is $m=7$.

---
Tags: algorithms, distributed-systems
---


# Question
Title: Is this path planning problem NP-complete?
Given N integers L1, L2, ... , Ln ,we have a robot that starts at (0,0) moves north on integer grid for L1 steps, then it either continues in its current direction or makes 90 degrees right turn then moves L2 steps and repeats for all Li.

Problem: Can the robot return to the origin?

# Answer
> 2 votes
Consider the following "DOUBLE-PARTITION" problem: given a set of $m$ positive integers $X = \\{ x\_1, x\_2, \dots, x\_m\\}$, can you partition $X$ into four sets $A,B,C,D$ such that $\sum\_{a \in A} a = \sum\_{b \in B} b$ and $\sum\_{c \in C} c = \sum\_{d \in D} d$?

There is a Karp reduction between DOUBLE-PARTITION and your problem: choose $n=4m$ and set $L\_i = 0$ if $i$ is not a multiple of $4$ and $L\_i = x\_{i/4}$ otherwise. Essentially, for every non-zero length $L\_i$, the robot can freely choose whether to travel $L\_i$ units north, south, east, or west. The sets $A,B,C$, and $D$ corresponds to the lengths of the movements along each of these directions.

Then you only need to show a Karp reduction between some NP-Hard problem and DOUBLE-PARTITION. You can use the classical PARTITION problem: given a set of positive integers $Y$, can you partition $Y$ into two sets $W,Z$ such that $\sum\_{w \in W} w= \sum\_{z \in Z} z$?

Consider the instance of DOUBLE-PARTITION where $X=Y$. If $A,B,C,D$ is a valid partition for this instance then $W = A \cup C$ and $Z = B \cup D$ is a valid partition for the PARTITION instance. Conversely, if $W,Z$ is a valid partition for the PARTITION instance, then $A=W$, $B=Z$, $C=D=\emptyset$ is a valid partition for the DOUBLE-PARTITION instance.

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


# Question
Title: Are there any countable sets that are not computably enumerable?
A set is *countable* if it has a bijection with the natural numbers, and is *computably enumerable (c.e.)* if there exists an algorithm that enumerates its members.

Any non-finite computably enumerable set must be countable since we can construct a bijection from the enumeration.

Are there any examples of countable sets that are not computably enumerable? That is, a bijection between this set and the natural numbers exists, but there is no algorithm that can compute this bijection.

# Answer
> 26 votes
> Are there any examples of countable sets that are not enumerable?

Yes. All subsets of the natural numbers are countable but not all of them are enumerable. (Proof: there are uncountably many different subsets of $\mathbb{N}$ but only countably many Turing machines that could act as enumerators.) So any subset of $\mathbb{N}$ that you already know is not recursively enumerable is an example – such as the set of all numbers coding Turing machines that halt for every input.

# Answer
> 19 votes
Yes, every undecidable (not semi-decidable) language has this property.

For example, consider the set $L = \\{(x,M) \mid M \text{ does not halt on input } x \\}$.

Suppose we have an algorithm that can enumerate the members of this set. If such an algorithm existed, we could use this to solve the halting problem with inputs $x,M$, with the following algorithm:

* Alternate between running machine $M$ for $n$ steps on $x$, and enumerating the $n$th member of $L$.

$M$ either halts, or does not halt on $x$. If it halts, eventually we will find an $n$ where we reach a halting state. If it doesn't halt, then eventually we will reach $(M,x)$ in our enumeration.

Thus we have a reduction, and we can conclude that no such enumeration exists.

Note that such enumerations can exist for semi-decidable problems. For example, you can enumerate the set of all halting machine-input pairs by enumerating all possible traces of all Turing Machine executions after $n$ steps, and filter out ones that do not end in a halting state.

# Answer
> 7 votes
In computability theory we deal with subsets of $\Sigma^\*$, where $\Sigma = \\{0,1\\}$. This language is countably infinite, and so any subset $L \subseteq \Sigma^\*$ is countable. Furthermore, there are many undecidable but recursively enumerable languages whose complements are not recursively enumerable. These languages are subset of $\Sigma^\*$ and hence are countable.

# Answer
> 1 votes
I want to give another concrete example. The set of encodings of always halting Turing machines $R$ is countable (since there are only countably many Turing machines, halting or non-halting). But $R$ itself is not computably enumerable.

Assume $R$ were computably enumerable. Then given index $i$ we can find the encoding of the always halting Turing machine $T\_i$ in $R = \\{T\_1, T\_2, \dots\\}$.

Let's define a Turing machine $D$ that accepts the i-th word if and only if $T\_i$ rejects it and rejects the i-th word if and only if $T\_i$ accepts it. This Turing machine $D$ is also an always halting Turing machine, since we can compute the i-th encoding of the always halting Turing machine $T\_i$ and simulate it on the i-th word. After $T\_i$ halts, we just reverse the decision of $T\_i$.

However, $D$ does not appear in the enumeration of always halting Turing machines $R$, since for each machine $T\_i$ it decides differently at least on the i-th input word. This is a contradiction and therefore the assumption that $R$ is computably enumerable is false.

So even when we focus on always halting Turing machines can we define a set that is countable but not computably enumerable.

---
Tags: computability, semi-decidability
---


# Question
Title: How to find the subsets S and T and the min-cut of this graph?
I get the residual graph by Ford-Fulkerson Algorithm:

I get that the minimum cut can be found by the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $S$, the rest of the nodes are called $T$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $S$ to a node in $T$.

So I think $S = \\{S, C, E\\}$, and $T = \\{T, A, B, D, F\\}$. But I found that what I found was not the minimum cut and two subsets I wanted. Why? Is my residual graph wrong?

# Answer
> 0 votes
As settled in the Question's comments:

The residual graph, as presented, is incomplete. The residual graph must include the non-zero reverse flow arcs. Then anything reachable from the source $S$ in that residual graph forms one part of the partition of the min cut.

---
Tags: graphs, network-flow, minimum-cuts, ford-fulkerson
---


# Question
Title: Number of steps of binary search given a stopping criterion
Reading a paper, I have found an algorithm that uses binary search to find a number between $0$ and $n\in\mathbb{N}$. The stopping criterion for this binary search is that $t\_2-t\_1\<\frac{1}{k^2}$ where $k\>=1$ is a natural number and $t\_2\>t\_1$. Then, it is said that the number of iterations of the binary search is at most $k\cdot{\text{log}\_{2}}(n)$. Why the number of iterations is $k\cdot{\text{log}\_{2}}(n)$?

# Answer
> 2 votes
After $m$ iterations, the interval size is

$$\frac{t\_2-t\_1}{2^m}=\frac{n}{2^m}.$$

This becomes smaller than $k^{-2}$ when

$$\frac{n+1}{2^m}\le\frac1{k^2}$$

or

$$m\ge\log\_2(k^2n)=2\log\_2(k)+\log\_2(n).$$

---
Tags: algorithms, algorithm-analysis, binary-search
---


# Question
Title: Decision version of optimization problems with polynomial-time approximation algorithms
Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$. Therefore, we can define a class of optimization problems "$P^O$", which is the class of all optimization problems whose corresponding decision problem is in $P$; and "$NPH^O$", which is the class of all optimization problems whose corresponding decision problem is NP-hard.

But, problems in $NPH^O$ are not equal in terms of approximation. To be concrete, assuming $P\neq NP$, we can partition $NPH^O$ into two non-empty subsets: the problems that have an FPTAS, and the problems that do not.

My question is: is there any parallel partition of the class of NP-hard *decision* problems? For example, assuming $P\neq NP$, is there a natural class $C$ of decision problems, such that $C^O$ is exactly the class of optimization problems that have an FPTAS?

(by "natural" I mean that $C$ can be defined as a class of decision problems, without referring to optimization problems).

# Answer
I did not find a class of decision problems that is equivalent to FPTAS, but I think FPTAS can be used to answer the following *partial* decision problem:

> Given a number $r$ and an approximation-accuracy $\epsilon\>0$:
>
> * If $OPT \leq r$, return "yes";
> * If $OPT \> r\cdot(1+\epsilon)$, return "no";
> * Otherwise, return either "yes" or "no".

Given an FPTAS, we can solve the decision problem as follows:

* If the value of the solution returned by the FPTAS is at most $r(1+\epsilon)$, return "yes";
* Otherwise, return "no".

I do not know if, given a solution to the decision problem, we can construct an FPTAS.
> 0 votes

---
Tags: optimization, approximation, decision-problem, complexity-classes
---


# Question
Title: Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)
I am seeking a linear-time algorithm to determine whether a directed acyclic graph (DAG) contains at least one pair of incomparable nodes.

Two nodes $u$, $v$ are said to be incomparable if there is neither a path from $u$ to $v$ nor a path from $v$ to $u$.

I can't see a linear solution to this. We can do a DFS for each pair $(u,v)$ and $(v,u)$ as in here. However, this approach does not lead to linear complexity.

The fact that it is a DAG hints topological order but is this useful?

Can this also be done with linear time complexity for directed cyclic graphs?

# Answer
Here is a linear-time algorithm that decides whether a DAG contains at least one incomparable pair of nodes.

1. Do a topological sorting with a linear algorithm. (Yes, topological sorting is very helpful!).
2. For each pair of adjacent nodes in the topological order obtained, check if there is an edge between them. If there isn't, return TRUE.
3. Return FALSE.

Why is this algorithm correct?
For a DAG, no incomparable pair of nodes is equivalent to the uniqueness of a topological order, which in turn is equivalent to a unique Hamiltonian path in the DAG.

---

In the general case of a directed graph, either acyclic or cyclic, here is a linear-time algorithm.

1. Compute the condensation of the given directed graph, which is a DAG. This can be done by, for example, Kosaraju and Sharir's algorithm.
2. Run the algorithm above on the DAG obtained. Return what it returns.

Why is this algorithm correct?
As Vladislav Bezhentsev commented, a pair of incomparable nodes exists in a directed graph iff it exists in a condensation of that graph.
> 6 votes

# Answer
Observe that if there exists a vertex $u$ that is incomparable with another vertex $v$ in a DAG, then $u$'s order in a topological sort can be changed with respect to $v$. Equivalently, $u$'s position in the topological order is not fixed. Hence, to answer your problem, you just have to find if there is a vertex with no fixed position in a topological sort.

I think you can look at this previously posted problem that asks about getting all vertices with fixed index in their topological ordering of a DAG. Its solution is a modified topological sort algorithm that runs in linear time.
> 4 votes

# Answer
Compute a topological ordering $(v\_1, v\_2, …, v\_n)$ of the DAG. Now consider the recursive following algorithm:

* if $n = 1$, then there are no incomparable pairs of vertices;
* if $(v\_1, v\_2)\notin E$, then $v\_1$ and $v\_2$ are incomparable (by definition of a topological ordering);
* otherwise, assume $n\geqslant 2$ and $(v\_1, v\_2) \in E$. If there exists a vertex $u$ such that $v\_1$ and $u$ are incomparable, then $v\_2$ and $u$ are incomparable (because there is no path from $u$ to $v\_2$, because $v\_2$ appears before $u$ in the topological ordering, and there is no path from $v\_2$ to $u$, otherwise there would be a path from $v\_1$ to $u$). That means that you can make a recursive call on $(v\_2, …, v\_n)$ to check if there is an incomparable pair of vertices.
> 4 votes

---
Tags: algorithms, dag, directed-graphs, topological-ordering
---


title: P/poly and dyadic oracle

text:
# Question
Title: P/poly and dyadic oracle
If we let a language *L* in {0,1}* be dyadic if for each x in *L*, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with a dyadic oracle. Is this the same as the class **P/poly**? If we start with some language L in **P/poly**, then we can use the advice string and the input x to generate a dyadic language, and then check various strings for each input x on the oracle to see if they are in our language to determine if x is in L. Is this the right idea? I also don't know how to approach the other direction. Do you need to create a circuit based on the queries to the oracle?

# Answer
Let $D \subseteq \\{0,1\\}^\*$ be the class of all dyadic languages. Then by $P^D$, we denote the class of languages decidable in polynomial time by a Turing machine with an oracle for a Dyadic language.

Given a dyadic string $x \in \\{0,1\\}^m$, denote by $B(x)$ the string $y$ such that $y\_i = x\_{2^i}$. Intuitively, you can think of $B(x)$ as "compressing" $x$ by removing all the $0$ indices in between the indices which are powers of $2$. Now given a dyadic language $L$, let $B(L) := \\{B(x) : x \in L\\}$.

**Claim:** $D \subseteq P\_{\text{poly}}$

**Proof** Let $L \in D$, and we describe a polynomial size circuit family $\\{C\_n\\}$ which computes $L$. Let $L\_n := \\{x \in L : |x| = n\\}$. Note that $B(L\_n) \subseteq \\{0,1\\}^{\log n}$, so the naive DNF circuit which computes it has size $\log n \cdot 2^{\log n} = n \log n$. Our circuit $C\_n$ simply wires $x\_i$ for which $i$ is a power of $2$ into the $i$th input for this naive DNF circuit for $B(L\_n)$.

It then follows that $P^D \subseteq P\_{\text{poly}}$.
> 0 votes

---
Tags: complexity-theory, turing-machines, complexity-classes, circuits, oracle-machines
---