# Question
Title: what could be more efficient way for this problem?
So I'm trying to solve this problem and I came up with a brute force solution. I was wondering how can i make it more efficient ?

Problem: Suppose i have resources and integer that denotes at what time it was used in an array. Now we have a variable 'window' = 3. I need to find the resource which was accessed the most in a particular window ( 3 in this case ). Example

```
{
  "r1": [1,8,3,2,5,6,4]
  "r2": [1,3,5,6,2]
}

```

Output

```
resource 1 and the count is 4. because between window 3 to 6 it was accessed 4 times

```

My solution is I would sort every resources and loop over every resource window and then have another loop which runs on the next element. I would count if the element falls in window and maintain a max count variable as well. I think the time complexity would be `n^2 * log n + (n*m)` (please correct me if i'm wrong) because i will have to sort each resources ( n) and go over m elements ( m is length of resource list)

# Answer
You can use the sliding window technique (also known as "Two Pointers") to traverse the array in $O(N)$.

Here's a full working C++ code.

```
#include <bits/stdc++.h>
using namespace std;

int count(const int window, vector<int> resource) {
  sort(resource.begin(), resource.end());

  int ans = 0;

  for (int i = 0, j = 0; i < resource.size(); i++) {
    for (; j < resource.size(); j++) {
      int diff = j - i + 1;
      if (resource[j] - resource[i] > window) break;
      ans = max(ans, diff);
    }
  }

  return ans;
}

int main() {
  int window = 3;

  cout << count(window, vector<int>{1, 8, 3, 2, 5, 6, 4}) << endl;
  cout << count(window, vector<int>{1, 3, 5, 6, 2}) << endl;
  cout << count(window, vector<int>{1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 7}) << endl;
  cout << count(1, vector<int>{1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 7}) << endl;
}

```

Output is:

```
4
3
14
10

```

I'm not sure if this is what you were looking for. The last value outputted is 10 because of the `1, 1, 1, 1, 1, 1, 2, 2, 2, 2`. This algorithm considers that sequence to be in a window of 1. If you need to change that, some tweaks would be needed.

The total complexity for each independent resource is $O(N \log N)$ because of the sort.

Also, since every resource has to be processed independently with this algorithm, you can execute them in parallel (several threads) and then join all the results. This will improve the runtime a bit.
> 1 votes

---
Tags: algorithms, data-structures, arrays
---


title: Is the following language in RE?

text:
# Question
Title: Is the following language in RE?
Given a language $A \in RE$, is the following language also in $RE$? $$ L\_{10}^{A} = \\{ \langle M \rangle : \lvert A \cap L(M) \rvert \geq 10 \\} $$ Where $L(M) = \\{x \in \\{0, 1 \\}^\* \mid M \text{ accepts } x \\}$.

(I've managed to prove that if $A \in R$ then $L\_{10}^A \notin R$ necessarily with a reduction from $HALTING$.)

While my intuition says it is in $RE$, I haven't been able to construct a turing machine that recognizes $L\_{10}^{A}$ nor define a reduction from it to another language in $RE$.

And another challenge:

For every language $A \in RE$, show that there exists a language $B\_A \in R$ such that for all $x \in \\{0, 1 \\}^\*$ we have $$x \in A \iff \exists y \in \\{0, 1\\}^\* : (x, y) \in B\_A$$

All help with these two problems will be greatly appreciated.

Thanks.

# Answer
$L^A\_{10}$ is recursively enumerable. In particular, since $A$ is recursively enumerable, there is a Turing Machine $M\_A$ that accepts $A$.

Let $M^t$ (resp. $M\_A^t$) denote a Turing machine that simulates the first $t$ steps of $M$ (resp. $M\_A$). If $M$ (resp. $M\_A$) does not halt within $t$ steps, then $M^t$ (resp. $M\_A^t$) halts and rejects.

For every $M$, $|A \cap L(M)| \ge 10$ if and only if there is some $T$ such that $|L(M\_A^T) \cap L(M^T)| \ge 10$. Then you can accept $L^A\_{10}$ as follows:

1. Start with $t=1$ and $c=0$;
2. Enumerate all words of length at most $t$ and, for each such word $x$:

* Run $M\_A^t$ on $x$;
* Run $M^t$ on $x$;
* If $x$ is accepted by both $M\_A^t$ and $M^t$, increment $c$ by $1$.
* If $c \ge 10$ halt and accept.

3. Double $t$, set $c=0$, and repeat from point 2.

In particular, the above Turing machine accepts $M$ when $t \ge \max\\{T, \ell\\}$, were $\ell$ is the length of the the tenth shortest word in $L(M\_A^t) \cap L(M^t)$.

---

Regarding your second problem: let $M$ be a Turing machine that accepts $A$ and, for any word $x \in A$, let $t\_x$ be the number of step executed by $M$ on input $x$.

Define $B\_A = \\{ (x, 0^{t\_x}) \mid x \in A \\}$, where $0^{t\_x}$ denotes the word consisting of $t\_x$ zeros. To decide whether $(x, y) \in B\_A$ it suffices to simulate $M$ for (up to) $|y|$ steps. If $M$ takes exactly $y$ steps to accept, then accept. Otherwise reject.
> 2 votes

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


# Question
Title: Which artificial neural network model can I use when trying to predict gene expression?
I need help choosing a model for my data. I have 50 genes that I need to test for their expression levels. I was thinking of implementing either an SVM or a multilayer perceptron model where the output can be on a scale of 0-1 to show the expression level of each gene. The input data is from single-cell transcriptomic datasets. Can I use either of these models? Which model is better and how? If not, can you please suggest some other models that better fit the data?

# Answer
You can use any model you want. The answer in machine learning is normally that you have to try each of them out and see how they work; it's usually hard to know in advance what is going to work and what won't. That is the only way to know which will work best.

If you can find published papers in the literature that have tried to solve this problem or a similar problem, you can look at what they did and get some ideas, but if you can't, then you just need to try different approaches and see how well each works.

If you want to predict whether the gene is expressed or not, you are looking for binary classification, and either a SVM or a neural network with a binary softmax output layer.

If you want to predict the degree of expression (from 0-1), then you have a regression problem, and you may need a slightly different technique. You haven't given enough details about the meaning of the output or about the training data you have available, so it's hard to make a recommendation, but one possible option is a neural network with a sigmoid function at the output.
> 1 votes

---
Tags: machine-learning, neural-networks, bioinformatics
---


# Question
Title: Context Sensitive Grammar for $x \# x^R \# x$
This language is given.

$L = \\{\\; x \\# x^R \\# x \mid x\in \\{a,b\\}^\*\\;\\}$

I have to figure out a context sensitive grammar for it.

I've tried several rules already but it's hard to make a copy of the first part and also get it in the last with the reversed part in the middle.

# Answer
> 1 votes
#### A context-sensitive grammar

$$\begin{aligned} S&\to AS\alpha\alpha \mid BS\beta\beta \mid \\#T & & (1)\\ A\alpha&\to\alpha A &&(2)\\ B\alpha&\to\alpha B &&(3)\\ A\beta&\to\beta A &&(4)\\ B\beta&\to\beta B &&(5)\\ T\alpha\alpha&\to ATA&&(6)\\ T\beta\beta&\to BTB&&(7)\\ A&\to a&&(8)\\ B&\to b&&(9)\\ T&\to\\# &&(10)\\ \end{aligned}$$

OK, I am lying. Except context-free rules $1$, $8$, $9$, $10$, none of the rules are allowed in a context-sensitive grammar.

However, those rules are non-contracting. They can be transformed methodically to context-sensitive rules as shown here. Hence, we can say the non-contracting grammar above represents a context-sensitive grammar.

#### The idea to generate $L$: blowup, move and change

An effective approach is to design grammar rules in the following order.

1. Blow up the initial symbol to include the field separators and enough placeholders.
2. Move the placeholders to the appropriate destinations.
3. At destinations, change placeholders to wanted symbols.

Employ new symbols as well as left-and/or-right context to ensure orderly derivations and no unintended derivations.

Suppose we have derived $\chi\\#\chi^RT\chi$ for some string $\chi$ consisting of $A$s and $B$s. Here is how we can extend $\chi$ in $\chi\\#\chi^RT\chi$ to $A\chi$.

1. Surround it by $\color{blue}{A}\cdots\color{blue}{\alpha\alpha}$ so that we will derive $\color{blue}{A}\chi\\#\chi^RT\chi\color{blue}{\alpha\alpha}$.
2. Move $\color{red}{\alpha\alpha}$ towards $T$ to obtain ${A}\chi\\#\chi^RT\color{red}{\alpha\alpha}\chi$
3. Change $T\alpha\alpha$ to $ATA$. We have derived $A\chi\\#(A\chi)^RTA\chi$.

Similarly, we can extend $\chi$ to $B\chi$

#### The technique, $XY\to YX$

This production rule enables $Y$ to move left when $X$ is to the left of it at the time of derivation.

Although $XY\to YX$ is not a context-sensitive rule, the same generation effect can be realized by the following four context-sensitive rules, where $U$ and $V$ are two new non-terminals.
$\quad XY\to XU$
$\quad XU\to VU$
$\quad VU\to VX$
$\quad VX\to YX$

This technique is used in rule $2$, $3$, $4$, $5$, which enables $\alpha$ and $\beta$ to move left towards $T$, so that they will be changed by rule $6$ and $7$ to $A$ and $B$ respectively.

#### The real context-sensitive grammar

Here is the solution proper.

$$\begin{aligned} S&\to AS\alpha\alpha \mid BS\beta\beta \mid \\#T &\quad & (1)\\ A\alpha&\to A\alpha\_A &&(2.1)\\ A\alpha\_A&\to\alpha\alpha\_A &&(2.2)\\ \alpha\alpha\_A&\to A\alpha &&(2.3)\\ B\alpha&\to B\alpha\_B &&(3.1)\\ B\alpha\_B&\to\alpha\alpha\_B &&(3.2)\\ \alpha\alpha\_B&\to\alpha B &&(3.3)\\ A\beta&\to A\beta\_A &&(4.1)\\ A\beta\_A&\to\beta\beta\_A &&(4.2)\\ \beta\beta\_A&\to\beta A &&(4.3)\\ B\beta&\to B\beta\_B &&(5.1)\\ B\beta\_B&\to\beta\beta\_B &&(5.2)\\ \beta\beta\_B&\to\beta B &&(5.3)\\ T\alpha \alpha&\to T\alpha\_T\alpha &&(6.1)\\ T\alpha\_T\alpha &\to A\alpha\_T \alpha &&(6.2)\\ A\alpha\_T \alpha&\to A\alpha\_TA &&(6.3)\\ A\alpha\_T A&\to ATA &&(6.4)\\ T\beta \beta&\to T\beta\_T\beta &&(7.1)\\ T\beta\_T\beta &\to B\beta\_T \beta &&(7.2)\\ B\beta\_T \beta&\to B\beta\_TB &&(7.3)\\ B\beta\_T B&\to BTB &&(7.4)\\ A&\to a&&(8)\\ B&\to b&&(9)\\ T&\to\\# &&(10)\\ \end{aligned}$$

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


# Question
Title: Lagrange Multipliers and Hard Margin SVMs
With hard margin support vector machines (SVMs), it suffices to find the critical points of the Lagrangian $L = \frac{1}{2}||\theta||^2 - \sum\_{n=1}^{N} \alpha\_n (y^{(n)} (\vec{\theta}^T\vec{x}^{(n)} + \theta\_0) - 1)$ over all $ \alpha\_n$, where $\vec{\theta}^T\vec{x}^{(n)} + \theta\_0 = 0$ is the seperating hyperplane, $y^{(n)}$ is the label (1 or -1), and there are $N$ data points.

I don't have much of a background in optimization, however, so I wanted to ask for methods that are commonly used to solve this optimization problem. Since $\alpha\_n$ are unknown, for example, I wasn't sure how we could use gradient descent here, since we cannot compute the derivative numerically given unknown $\alpha\_n$.

# Answer
The Lagrange multipliers $\alpha\_i$ are *also* unknowns. You may not ultimately need the values, but you do need to solve for them.

Think of $L$ as a function of the unknown variables:

$$L(\theta\_0, \ldots, \theta\_N, \alpha\_1, \ldots, \alpha\_N)$$

The stationary points of $L$ are the points where $\nabla L = \vec{0}$. That means *all* of the partial derivatives are zero:

$$\begin{eqnarray\*}\frac{\partial L}{\partial \theta\_0} & = & 0 \\ & \vdots & \\ \frac{\partial L}{\partial \theta\_N} & = & 0 \\ \frac{\partial L}{\partial \alpha\_1} & = & 0 \\ & \vdots & \\ \frac{\partial L}{\partial \alpha\_N} & = & 0 \end{eqnarray\*}$$

So while you have $2N+1$ unknowns, you also have $2N+1$ equations.

To understand why this works, take look at what the extra equations mean. This:

$$0 = \frac{\partial L}{\partial \alpha\_i} = y^{(i)} \left( \vec{\theta}^T \vec{x}^{(i)} + \theta\_0 \right) - 1$$

Is precisely this:

$$y^{(i)} \left( \vec{\theta}^T \vec{x}^{(i)} + \theta\_0 \right) = 1$$

...and *that* equation should look familiar to you. The "extra" equations that you need to solve for are precisely the equality constraints on your optimisation problem.
> 1 votes

---
Tags: optimization, machine-learning, svm
---


title: Addition in Lambda calculus

text:
# Question
Title: Addition in Lambda calculus
Found this term for a supposed 'adder' in lambda calculus.

```
λabcd.ac(bcd)

```

Although I know about alpha-conversion and beta-reduction and all that stuff, I don't know how to apply it. All the examples I could find always put in real numbers (like "3" and "5") but strictly speaking, if we want to abide by the rules of lambda calculus, numbers should be represented by lambda-terms too, right? Elsewhere I saw them defined recursively like this:

`3 = λab.a(a(a(b))),`

`5 = λab.a(a(a(a(a(b)))))`.

I have a hard time linking the concept of "repeatedly applying a value to itself" to anything i already know. What does that even mean? Why is it equivalent to adding? **Why *does* the above term add anything?**

**Looking for a step-by-step explanation that shows the adder "in action" and how it actually works.**

# Answer
So... I'm not going to completely answer your question by showing the adder to you in action, but here's some intuition as to why it works.

Natural numbers can be defined recursively:

* $0$ is a natural number.
* If $n$ is a natural number, then $S(n)$ is a natural number, where $S$ is the successor function.

The lambda expression $\lambda s. \lambda z. s(s(s(z)))$ is an "abstracted" version of $S(S(S(0)))$, using Church encoding. The only difference between this and the recursive definition above is that a caller needs to supply the successor function and the zero.

What does it mean to "supply" a zero? Well, you can put anything you like there, *even another number*. So if you took, say, $S(S(0))$ and "replaced" the zero with $S(S(S(0)))$, you would be basically adding $2$ and $3$.

Or, to put it another way:

$$\mathit{add}\\,m\\,n = \lambda s. \lambda z. m\\,s\\,(n\\,s\\,z)$$

Do you see what's going on here? You are supplying $m$ with the same successor function, but giving it a different zero, namely, $(n\\,s\\,z)$.

Finally:

$$\mathit{add} = \lambda m. \lambda n. \lambda s. \lambda z. m\\,s\\,(n\\,s\\,z)$$

On a final note, I suspect that using meaningful names for your variables is half the battle here. Understanding what each variable means helps a lot.

As an exercise, now try implementing multiplication. The idea is that to multiply $m$ by $n$, you "supply" $n$ as the successor function rather than the zero.
> 3 votes

---
Tags: lambda-calculus, functional-programming, arithmetic
---


# Question
Title: Satisfiability of bounded assignment of input variables to CNF formula
Consider a CNF formula $F$ such that all the literals in every clause must be negative ( here is an example : $F$ = ($\bar{x\_{1}}$ $\wedge$ $\bar{x\_{2}}$) $\vee$ ($\bar{x\_{3}}$ $\wedge$ $\bar{x\_{4}}$ $\wedge$ $\bar{x\_{5}}$) would be a valid formula where as $F$ = ($x\_{1}$ $\vee$ $\bar{x\_{3}}$ ) would not be a valid formula $F$ . It is known that this type of formula is satisfiable given you can set every variable to 0 , which will satisfy all the clauses . However, what if you received a positive integer $i$ and were asked if you could assign at most $i$ variables to a value of 0.

I know $F$ would still be satisfiable, and I know this would be NP-Complete. However, I am having difficulty reducing set cover to this problem in order to prove NP-completeness. I know that there being negations everywhere would result in the same number ( but inverted ) of truth assignments that would lead to satisfiability compared to if there were not any in the first place. Maybe trying to reduce set-cover to this problem is a dead end? Let me know what you think.

# Answer
The choice of set cover might not be ideal. Let us rephrase the problem. You get a set of $m$ cluases $C\_1, \dots C\_m$ each consists of negative variables only. You need to find a set of $k$ variables that intersects each of these clauses (the variables that you would assign the value $0$. Clearly this corresponds to the hitting set problem defined as follows:

**The hitting set problem**

Given a family of $m$ sets $\mathcal{F} = \\{S\_1, \dots S\_m\\}$ over a ground set $U$. Is there a set of at most $k$ elements that have a non empty intersection with each of the sets in $\mathcal{F}$.

This problem is also NP-complete.
> 1 votes

---
Tags: algorithms, complexity-theory, satisfiability, discrete-mathematics
---


# Question
Title: Partition data into two sets of the same size such that the sum of the average distances is maximized
Say I have a set of strings $S=\\{s\_1, s\_2, ..., s\_N\\}$, and I want to partition $S$ into two sets $S\_1$ and $S\_2$ equally, i.e., $||S\_1|-|S\_2||\leq1$.

Define the difference of a set as $$Diff(S\_k)=\frac{\displaystyle{\sum\_{s\_i,s\_j\in S\_k} d(s\_i,s\_j)}}{\displaystyle{|S\_k|\choose 2}}$$

where $d(s\_i,s\_j)$ is a custom distance function that calculates the 'distance' between two strings, satisfying $d(s\_i,s\_j)=d(s\_j,s\_i)$.

The objective is to find a partition of $S$ that maximize $Diff(S\_1)+Diff(S\_2)$, assuming we already have $d(s\_i,s\_j)$ for $s\_i,s\_j\in S$.

Are there any (heuristic) algorithms that I can use to achieve the objective? Or maybe this problem can be generalized to some known problem with loose constraints?

# Answer
Let us call this problem $P$. Assuming we can choose the fucntion $d$ freely, this problem is NP-hard. I willl show a proof sketch for the case where $N$ is even. This already implies that the problem in general is NP-hard. The proof is a reduction from the **balanced cut problem**.

Let us define the function $\operatorname{Diff}'(S\_k) = \sum\limits\_{s\_i, s\_j \in S\_k} d(s\_i, s\_j)$. Let $P'$ be the same problem defined over $\operatorname{Diff}'$ instead of $\operatorname{Diff}$, i.e. the goal is to find a partition that maximizes $\operatorname{Diff}'(S\_1) + \operatorname{Diff}'(S\_2)$. Claerly, for an even value of $N$, a solution $(S\_1, S\_2)$ is optimal for $P$ if and only if it is optimal for $P'$, since $|S\_1| = |S\_2|$, and hence the problems $P$ and $P'$ are equivalent. We now procede with the problem $P'$.

It is quite easy to reduce the balanced cut problem (defined below) to this problem. Intuitively, let us represent the input as a complete weighted graph, where the strings correspond to vertices and the function $d$ correspond to the weight of the edges. Our goal is to partition the vertices of this graph into two sets $(S\_1, S\_2)$ in a way that maximizes the total sum of weights of edges in both induced subgraphs $G\[S\_1\]$ and $G\[S\_2\]$. This is equivalent to minimizing the weight of the cut $(S\_1, S\_2)$, since each edge belongs to either one of the induced subgraphs or is a cut edge. Hence, we aim to find a partition of the vertices into two sets of equal sizes in a way that minimizes the weight of the cut. That is exatly the definition of the weighted balanced cut problem.

```
Balanced cut problem
Input: An undirected graph $G$.
Asked: A partition of $V(G)$ into two sets $(S_1, S_2)$ of equal sizes,
minimizing the size of the cut $(S_1, S_2)$.

```

This problem is NP-hard, and hence, the weighted version as well. Now it is not hard to reduce the weighted version of this problem to $P'$. Given a graph $G$ with a weight function $w$, we first add all missing edges as edges with weight zero. Now we build a string $s\_v$ for each vertex $v$ and set $d(s\_u, s\_v) = w(u, v)$ for w the given weight function of $G$. Cearly this instance of $P'$ admits a parition of weight $k$ if and only if $G$ admits a balanced cut of cost $W - k$, where $W = \sum\_{e \in E(G)} w(e)$.
> 2 votes

---
Tags: algorithms, heuristics, partitions
---


# Question
Title: Prove Language Is Undeciable Using Diagonalization
I was given the following problem and told it has to be solved using diagonalization. However, I am confused as to why diagonalization would be the solution. Would the answer not be since L is infinite it has uncountably many subsets. Since there are only countably many decidable languages, some subset of L must be undecidable.

**Problem:** We know that for Σ = {0, 1}, there are uncountably many languages over Σ. Is this also true for the languages over the unary alphabet {1}? Give a proof from scratch (not using known theorems).

# Answer
> 1 votes
Your proof is roughly correct, indeed showing that |Power(L)| is uncountably infinite is usually done via diagonalization. Here, L is the set of strings over the unary alphabet, and a language is any subset of L.

Suppose for contradiction that |P(L)| was denumerable. Then we can create an infinite array indexed on the rows by the members of P(L) and indexed on the columns by the members of L. Now we can add a 0 or a 1 for each cell depending on whether or not a string is inside a subset... Can you complete the proof?

---
Tags: complexity-theory, turing-machines, undecidability, diagonalization
---


# Question
Title: 3-colouring with a bounded amount of colors
The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for a polynomial time algorithm to check if the graph $G$ admits a 3-colouring where the first color is only used at most $k$ times or where any color is used at most $k$ times?

# Answer
If the graph has $k$ vertices, any color cannot be used more than $k$ times, so I'm not sure I see the problem here.

If the limitation is an input of the problem, then the problem becomes harder, not easier, so it is still $\mathsf{NP}$-complete.
> 2 votes

---
Tags: algorithms, complexity-theory, runtime-analysis, discrete-mathematics, algorithm-design
---


# Question
Title: Turing recognizability and Reduction Mapping on pairs of related Turing machines
I am interested in computation and I am lost on undecidability and reductions. I have the following two problems I am stuck on.

Let us call 2 Turing machines related if there is an input $w$ on which both halt (after finitely many steps). Let $h(M )$ be the set of inputs on which the TM $M$ halts.

Show that the problem $\text{RELATED} = \\{\langle M1, M2\rangle \mid h(M1) \cap h(M2) \neq \emptyset\\}$ is Turing recognizable.

Assume, you know that the halting problem $H$ is undecidable. Show that the problem $\text{RELATED}$ is undecidable. Show this result by defining an appropriate mapping reduction $g$.

# Answer
> 1 votes
To show $\mbox{RELATED} \in \mathsf{RE}$, you can enumerate all pairs $\langle w,t \rangle \in \Sigma^\* \times \mathbb{Z}^+$ in dovetail fashion. For each pair check whether both $M\_1$ and $M\_2$ halt on $w$ within $t$ steps.

Given $x \in \Sigma^\*$, you can compute a description of a Turing machine $M\_x$ that halts if and only if its input is $x$. Since $\langle T, x \rangle \in H \iff \langle T, M\_x\rangle \in \mbox{RELATED}$, we must have $\mbox{RELATED} \not\in \mathsf{R}$.

---
Tags: complexity-theory, turing-machines, reductions, undecidability, turing-recognizable
---


# Question
Title: Dijkstra's algorithm for edge weights in range 0, ..., W
Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range 0, ..., W, where W is a relatively small number. How can I modify that algorithm so that it takes time just O((|V| + |E|) logW) and relatively easy implement that in C/C++?

# Answer
> 3 votes
This is the algorithm I know of that is $\mathcal{O}(|E| + W|V|)$. Some things to note:

* $C$ is defined as the maximum cost of any shortest path that leaves $s$ (the source). It is at most $W|V|$.
* Each $L\[i\]$ is a doubly-linked list. The $L\[i\]$ keep track of all vertices that are currently at distance $i$ from the source.
* $d\[v\]$ is the shortest distance (so far) from the source to vertex $v$

Each edge and vertex of the graph will be visited only once, and the outer loop runs in time $\mathcal{O}(C)$, therefore the complexity of the algorithm is $\mathcal{O}(|E| + |V| + C)$. Since $C \leq W|V|$, this reduces to $\mathcal{O}(|E| + W|V|)$.

---

```
L[i] <- {}, 0 <= i <= C
L[inf] <- {}
L[0] <- {s}

for v in V do
    push v into L[inf]
    d[v] <- inf
end

d[s] <- 0
p <- 0
while p < C do
    while L[p] != {} do
        pop v from L[p]
        for (v, u) with d[u] > d[v] + w(v, u) do
            remove u from L[d[u]]
            d[u] <- d[v] + w(v, u)
            push u in L[d[u]]
        end
    end
    p <- p + 1
end

```

# Answer
> 2 votes
The standard Dijkstra's algorithm uses a priority queue whose elements are vertices, and where the priority of a vertex $v$ is the current estimate of the distance $d\[v\]$. The priority queue might contain a maximum of $|V|$ vertices at any point in time. If you use a heap as your priority queue, the running time of each operation on a priority queue is logarithmic in the number of items in the queue, so each priority queue operation might take $O(\lg |V|)$ time and the total running time is $O((|V|+|E|)\lg |V|)$.

In your situation where the weights are integers from $1..W$, we can get the running time down to $O((|V|+|E|)\lg W)$. The basic approach will be to ensure that the priority queue contains no more than $W$ elements at any point in time. Thus, the running time of each operation on the priority queue will be $O(\lg W)$, and we will attain the desired running time.

How do we keep the size of the priority queue down to $\le W$ at all points in time? Easy: instead of a queue of vertices, we will have a queue of buckets. Each bucket contains a set of vertices that all have the same distance estimate, and the priority of a bucket is that distance estimate. In particular, for each vertex $v$ that would be in the queue in standard Dijkstra's algorithm, our modified algorithm will have a bucket for the integer $d\[v\]$. The bucket for the integer $i$ will contain a linked list of all vertices $v$ such that $d\[v\]=i$ and such that $v$ would be in the queue right now in standard Dijkstra's algorithm.

Now I claim that, in standard Dijkstra's algorithm, the set of values of $d\[v\]$ (taken over the vertices $v$ in the queue at any point of time) contains at most $W$ distinct values. Why? Well, at any point in time, there is some integer $\alpha$ such that we have assigned a final distance value to all vertices of distance at most $\alpha$ from the source. The queue contains vertices that are one edge away from one of those finalized vertices. Consequently, the distance estimate for any vertex in the queue has to be somewhere in the range $\alpha+1 \ldots \alpha+W$. Since all distances are integers, this means there are at most $W$ possible distance estimates in the queue at any point in time. Therefore, our modified algorithm will have at most $W$ different buckets in its queue, and each operation on the queue will take at most $O(\lg W)$ time.

To make this work, we'll have to make one other change: instead of implementing the priority queue as a heap, we'll implement it as a balanced binary search tree, using the distance as the key. A balanced binary search tree supports all of the standard priority queue operations (including extract-min); it is useful here because when we want to insert a node into the queue, we must first find its corresponding bucket, which is something that can be done in $O(\lg W)$ time using a balanced binary search tree.

This algorithm is almost easier to implement than to describe.....

# Answer
> 0 votes
we denote the last popmin weight is D ,so at any time the keys in priority queue are in range of {D, D+1, \ldots, D+C} (because D has just been updated, we denote the pop vertical as v ,then v may relax some vertical adjacent to it denote as v, because the distance from the source to v is D and the edge weight is less than C so the new distance from source to v at most is D+C )

we use priority queue the same as before, and the priority queue element is bucket. By our analysis,the max number of elements in the priority queue is C+1

now we analyze some operations in this datastructure

> popmin:because the max number of elements in the priority queue is C+1,so popmin takes O(\log(C+1))
>
> insert&update: because the max number of elements in the priority queue is C+1,so insert&update takes O(\log(C+1))

and we find the Dijkstra algorithm take update |E| rounds ,each update takes O(\log(C+1)) ,so in all the update tales O(|E|\*O(\log(C+1)))

and find min |V| takes rounds,each popmin takes O(\log(C+1)) ,so in all the update tales O(|V|\*O(\log(C+1)))

so this algorithm in all takes O(|E|\*O(\log(C+1)))+O(|V|\*O(\log(C+1)))=O(\log (C+1)(|V|+|E|))=O((\log C)(|V|+|E|))

---
Tags: algorithms, algorithm-analysis, data-structures, shortest-path, weighted-graphs
---


# Question
Title: Polytime algorithm for SUBSET-SUM assuming P=NP
In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in polynomial time and runs forever if the answer is "no". It can be obviously fixed to give "no" in exponential time (just to run exponential algorithm if the first one is running for too long).

But can we explicitly describe an "honest" algorithm, which solves (and I mean, really solves) SUBSET-SUM (or any other NP-complete problem) in polynomial time assuming P=NP?

By "honest" and "really solves" I mean that the algorithm meets the classical definitions for a polynomial-time algorithm, i.e., here should exist constants $C\_1, C\_2$ such that at any input $x$ algorithm would terminate in no more than $C\_1 \cdot |x|^{C\_2}$ steps and output "yes" if $x \in $ SUBSET-SUM and "no" otherwise. The Wikipedia algorithm does not satisfy the first condition, so it doesn't "really solve" the problem.

# Answer
I can half-answer this, but I believe the deeper question you are getting at is something I am in the process of learning better :)

The algorithm on wikipedia, call it W, is based on the idea: rather than guess at certificates why not just guess at the deterministic P algorithm D itself? This is expensive, but since it is independent of the input it is O(1) (if such an algorithm exists). The algorithm actually always decides even if P != NP, because there is of course a series of "brute force" programs that print out just one possible certificate then halt, so W can fall back to a very slow brute force.

The problem is that you actually have no way to *verify* the program it returns to you. You may imagine running W and find it seems to prefer a certain program, but you may find that on larger input it eventually finds a flaw in that program and moves on. It may seem to settle on an algorithm that seems to be $n^7$ but later on find a mistake in it and switch to an $n^{2000}$ algorithm. You will never know when it has found the "right" one.

This is actually the same idea used in the proof of the Karp-Lipton theorem: given enough computation power you can use it to just start guessing entire classes of programs and verify that they work (the proof is exactly, "guess a program, and verify that it works, then use it", which takes a bit of computational power - more than NP - to pull off.)

I am not aware of theory regarding how complicated a solution can be, but perhaps someone more knowledgeable can answer.

The more concrete scenario in the P=NP reality is that someone *actually* constructs an algorithm to any NP-complete problem, such as SAT.

I think you asked a good question and I'm curious how to fill in the gaps in my answer, regarding how W may be analyzed and made more useful in semi-practice.
> 3 votes

# Answer
I. previously posted another answer (a long time ago), but it had flaws, so I've deleted it.

I gave some extra thought to your question (and Wikipedia's polynomial-time semi-algorithm).

I'll argue here in a similar way to the argument in the 2nd paragraph of @djechlin.

The semi-algorithm there (let's call it W) is an honest semi-algorithm because it shows that actual Cw1 and Cw2 exist (even though it can't show its actual values):

due to the assumption of P==NP, there exists some semi-algorithm (let's call it X), a poly-time semi-algorithm, solving any NP-complete algo (such as SSP)

Even though you don't know X, you can:

* try each and every number of steps K; and
* run each and every program, with an index M lower than K on S for K steps (program are enumerable).

(this is the W presented in Wikipedia)

Since X exists and is a semi-algorithm it has a finite length, so its index is a finite number (b bits long).

If there's a solution for S, X will find it in a polynomial number of X-steps.

As @djechlin states, the number of W-steps, finally, depends on:

* number of X-steps (polynomial on the size of S), and
* index of X (independent of S)

As such, the index-of-X is O(1) with respect to the size of S.

***So, W is a poly-time semi-algorithm.***

***That time complexity being: (2ˆb - 1) * (Cx1 + Cx2 * size(S))ˆ2***

You might try, at most:

* (2ˆb - 1) programs,

and run each, at most, for:

* K-steps, from 1 up to the complexity of X (second term)

Using 1 + 2 + ... + n == 1/2 * n * (n + 1) ~ O(nˆ2)

Of course, you don't know Cx1, Cx2, b, but they are proven to exist.

With this, you can see that W is an honest semi-algorithm.

You don't have to look further.

The only caveat is that X and W are semi-algorithms, they answer yes in poly-time when there's a solution and might not halt for S without a solution. But that's already part of the definition of P==NP. The X in the demonstration of P==NP is required to be a semi-algorithm (only has to "accept" a given language in poly-time).

This was quite long, so it should be improved (presented in a more elegant way).

I hope this is correct and clear enough.
> 0 votes

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


# Question
Title: Dividing a binomial heap to 3 equal-sized binomial heaps
Given a binomial heap of $n$ nodes (where $n$ divides by 3), how can I split the heap to three binomial heaps with an equal number of nodes (every heap contains $n/3$ nodes). The time complexity needs to be $O(\log n)$.

# Answer
> 0 votes
Is this a hw assignment? -hint split the linked list into two parts (N/3) +(2N/3) then the 2N/3 to N/3 + N/3

N/3 - represent in binary so you could find out what to extract

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: Prove/Refute that $L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language
I was solving some exercises about CFL from past years' homework and faced this question.

***Question:*** Given the language $L=\\{w \\# x^R \ | \ x\ is\ a\ substring\ of\ w\\}$, prove/refute if it's regular language. If you proved it's regular then provide NFA and a regular expression that describes it. Otherwise, provide CFG and PDA for it.

***My Answer:*** I think that the language is not regular but couldn't prove it so I provided CFG and PDA for it.

If anyone can tell whether the language is regular or not and therefore provide proof for that I'll be grateful.

# Answer
> 3 votes
Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Consider the word $a^p\\#a^p \in L$. By the pumping lemma there is some $1 \le k \le p$ such that $a^{p-k}a^{ki}\\#a^p \in L$ for all choices of a non-negative integer $i$. Choosing $i=0$ yields $a^{p-k}\\#a^p \in L$, which is a contradiction since $(a^p)^R = a^p$ is not a substring of $a^{p-k}$.

---
Tags: formal-languages, regular-languages, context-free, formal-grammars, pushdown-automata
---


# Question
Title: Constructing product automaton with conjunctive conditions
The question was to construct a DFA which accepts the language $$\\{ x \in \\{0,1\\}^\* \mid x\text{ starts with a }0\text{ and has at most one }1\\}$$

So I first constructed DFA for '$x$ starts with a $0$' and a DFA for 'has at most one $1$' then I tried getting the product automaton of these, but the quiz says the automaton should not accept the string "" (empty string). Does that mean I just change $q\_0p\_0$ from accept state to normal state? or have I done something more wrong?

# Answer
> 2 votes
The "DFA for 'has at most one $1$-symbol'" in the question is not correct. It accepts $101$, $0101$, etc.

The right one should be like the following.

---

In the product automaton, you should label state $p\_iq\_j$ as accept state iff both $p\_i$ and $q\_j$ are accept states in their original automaton respectively, since the condition for string $x$ to be in the language is " ... *and* ...".

If the condition been "... or ...", then you should label state $p\_iq\_j$ as accept state iff at least one of $p\_i$ and $q\_j$ is an accept state in its original automaton.

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


# Question
Title: Inapproximability of an optimization problem
Suppose we have an optimization problem $\mathcal{P}$ that we should cover all points with $k$ disjoint rectangles in the plane and we should optimize a distance function over each rectangles . Now, suppose there is a $\mathcal{P}'$ that just need cover all points in the plane with $k$ disjoint rectangles.

Already proved that $\mathcal{P}'$ is NP-Hard and there is no constant factor approximation algorithm for $\mathcal{P}'$. Can we conclude that $\mathcal{P}$ has no constant factor approximation algorithm? Why?

**I think as follow:**

$\mathcal{P}$ is at least hard as $\mathcal{P}'$ so if there is a constant factor approximation algorithm for $\mathcal{P}$ then for each feasible solution $\mathcal{I}$ of $\mathcal{P}$, then $\mathcal{I}$ is a solution for decision version of $\mathcal{P}'$ hence we solve decision version of $\mathcal{P}'$ in polynomial time and hence $P=NP$. Finally, we conclude that $\mathcal{P}$ has no constant factor approximation algorithm.

# Answer
Here is a similar example. Let $\mathcal{Q}$ be the problem of maximizing the number of satisfied clauses in an input CNF given that the assignment is the FALSE assignment. Let $\mathcal{Q'}$ be the problem of maximizing the number of satisfied clauses in an input CNF, without any other constraints. It is known that $\mathcal{Q'}$ has no PTAS (unless P=NP). Does it follow that $\mathcal{Q}$ has no PTAS?
> 0 votes

---
Tags: complexity-theory, approximation
---


title: CNF clause to 3-SAT

text:
# Question
Title: CNF clause to 3-SAT
How to transform a k-SAT CNF clause into a combination of 2-SAT and/or 3-SAT (1-SAT) clauses? $k\>3$

Example 5-SAT: $$ Q = \neg A \lor B \lor C \lor D \lor E $$ $$ \\; \\; = (X0 \lor X2 \lor X3) \land (Y1 \lor Y2 \lor Y3) \land \\; ... $$

Do I have to apply Tseytin transformation? How? Could you resolve my example, please?

---

EDIT From this answer. Thanks to Yuval Filmus

**For simplicity: $\bar{x}$ is equivalent to $\neg x$ and $|$ is equivalent to $\lor$**

**1-SAT**: Introduce 2 literals and cover the conjunction of all their combinations, to make sure at least one of these clauses is false if the original literal is. $$(A) = (A|m|n) \land (A|m|\bar{n}) \land (A|\bar{m}|n) \land (A|\bar{m}|\bar{n})$$ Idea: we add 2 variables m, n

**2-SAT**: Introduce 1 variable, and cover both its possible values. $$(A|B) = (A|B|m) \land (A|B|\bar{m})$$ Idea: we add 1 variable m

**3-SAT**: These are already in 3-SAT friendly form $$(A|B|C)$$

**k-SAT (k\<3)**: Split the literals into the first and the last pair, and work on all the single ones in between - as an example: $$(a|b|c|...|y|z) = (a|b|A) \land (\bar{A}|c|B) \land (\bar{B}|d|C) \land ...\land (~V|x|W) \land (~W|y|z)$$

Idea: we add k-3 variables. For 5-SAT, 2 new variables.

If I take my example, it gives: $$ Q = \bar{A} | B | C | D | E $$ $$ Q = (\bar{A} | B | ...) \land ... \land (...| D | E) $$ $$ = (\bar{A} | B | m) \land (\bar{m}| C | n) \land (\bar{n}| D | E) $$ with m and n, two new variables.

Could you give me more explanations about the k-SAT reduction. I don't really understand why it works.

# Answer
We can express the clause $x\_1 \lor x\_2 \lor \cdots \lor x\_n$ as the following conjunction of 3-clauses: $$ (x\_1 \lor x\_2 \lor y\_2) \land (\lnot y\_2 \lor x\_3 \lor y\_3) \land (\lnot y\_3 \lor x\_4 \lor y\_4) \land \cdots \land (\lnot y\_{n-2} \lor x\_{n-1} \lor x\_n), $$ where different $y$ variables are used for each clause.

To see that the two are equivalent (with respect to satisfiability), it suffices to check that $C\_1 \lor C\_2$ is equivalent to $(C\_1 \land y) \lor (C\_2 \land \lnot y)$. Suppose first that $C\_1 \lor C\_2$ is satisfied. If it is satisfied due to a literal in $C\_1$, we can set $y$ to be false and satisfy $(C\_1 \land y) \lor (C\_2 \land \lnot y)$. Similarly, if $C\_1 \lor C\_2$ is satisfied due to a literal in $C\_2$, we can set $y$ to true. For the other direction, suppose that $(C\_1 \land y) \lor (C\_2 \land \lnot y)$ is satisfied. If $y$ is false then $C\_1$ must be satisfied, and if $y$ is true then $C\_2$ must be satisfied. In both cases, $C\_1 \lor C\_2$ is satisfied.
> 1 votes

---
Tags: 3-sat
---


# Question
Title: Bisecting Intervals of floating point numbers containing 0 and infinity fairly
It is seldom considered that floating points are not evenly distributed in the real number line. I've been working with interval arithmetic and noticed when bisecting $\[a,b\]$ on the real number line into $\[a,(a+b)/2\]$ and $\[(a+b)/2,b\]$ starting from $\[-1.3552646593344489\*10^{308} ,0\]$ until $a,b$ are neighboring floats takes way more steps when you always pick the interval containing $-10$ and way fewer steps if you always pick the interval containing $-10^{305}$. This is because taking the average of two floating point (fp) numbers with differing exponents divides a floating interval in sub intervals which contain a very different number of floats.

Given two interval boundaries $(a,b)$ how do i calculate a fp number $m$ such that between $a$ and $m$ there are nearly as many fp numbers as between $m$ and $b$ given that $a,b$ can have different signs or have values from $\\{-\infty,\infty\\}$?

A design for 64 bit floating point numbers would be welcome. Please document your design decisions so i can reimplement those for other precisions. Note that when dividing interval boxes the unevenness gets amplified exponentially with the number of dimensions so i am to trade speed for getting a better $m$.

### Implementation that works if the signs of $a,b$ are the same

I am already aware of Implementations like `_middle(x1::Float64, x2::Float64)` but it doesn't calculate the correct points if signs of $a$ and $b$ differ or if atleast one of them is infinite. Infinity should be treated as a floating point number one step larger then the largest finite floating point number.

### Test cases

* The midpoint of $\[-\infty,\infty\]$ should be 0.
* The midpoint of $\[1.7976931348623155\*10^{308},\infty\]$ (the second largest finite float and `prevfloat(prevfloat(Inf))` ) should be 1.7976931348623157e308 (the largest finite float and `prevfloat(Inf)`).
* The midpoint of $\[-\infty,1.7976931348623155\*10^{308}\]$ should be -5.0e-324 (the largest negative float and `prevfloat(0.0)`).
* The midpoint of $\[0.0, \infty\]$ should be 1.5.
* The midpoint of $\[-5.0\*10^{-320}, 1.0\*10^{-318}\]$ should be $4.75\*10^{-319}$.
* The midpoint of $\[-5.0\*10^{-315}, 1.000004\*10^{-318}\]$ should be $-2.4995\*10^{-315}$.

### Red Herring

The publication How do you compute the midpoint of an interval? compares different numerical approaches to divide in a $\frac{a+b}{2}$ way which doesn't have the property i require.

# Answer
> 1 votes
One approach is to enumerate all numeric floating-point encodings for a given floating-point type, then find the enumeration that is half-way between the enumerations of the two source operands. This answer assumes the use of a platform that uses IEEE-754 floating-point types and twos-complement integers.

The bit pattern of a floating-point operand itself can provide the desired enumeration. For example, for a `double` operand in IEEE-754 `binary64` format, we copy the bits to a 64-bit unsigned integer, then reinterpret that as a signed 64-bit integer. However, before we re-interpret as a signed integer, we must take care of negative operands by reflecting them such negative zero is mapped onto positive zero, and negative infinity maps to a negative integer large in magnitude.

Now all possible numerical floating-point operands are contiguously enumerated in numerical order as a signed integer. If we do this for both source operands, then compute the average of the two enumerations, the resulting enumeration represents the desired midpoint. This midpoint is first transformed into an unsigned 64-bit integer, again reflecting negative operands. The unsigned 64-bit integer is copied to a `double` in IEEE-754 `binary64` format.

The ISO-C program below implements the above algorithm. One caveat: Because IEEE-754 bindings are optional in C, not all compilers may handle `-0.0` as a number distinct from `0.0`; this may require at minimum compiling with the strictest floating-point setting of the compiler (e.g. `-fp-model:strict`). Alternative ways of constructing `FP64_NEG_ZERO` as an unsigned integer of same size as the floating-point type with only its most-significant bit set are possible, of course.

```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <float.h>
#include <limits.h>
#include <math.h>

#define MORE_EFFICIENT  (1)

#if MORE_EFFICIENT
/* Henry S. Warren Jr., "Hacker's Delight 2nd ed.", Addison-Wesley 2013, p. 19 */

/* arithmetic right shift by 1 bit */
int64_t asr1 (int64_t x)
{
    return (x & ~1) / 2;
}

/* compute average of signed integers w/o overflow in intermediate computation*/
int64_t avg (int64_t x, int64_t y)
{
    int64_t t = (x & y) + asr1 (x ^ y);
    return t + (int64_t)(((uint64_t)t >> 63) & (x ^ y));
}

#else // MORE_EFFICIENT

/* compute average of signed integers w/o overflow in intermediate computation*/
int64_t avg (int64_t a, int64_t b)
{
    int64_t r;
    if ((a < 0) == (b < 0)) {
        r = a / 2 + b / 2 + (a % 2 + b % 2) / 2;
    } else {
        r = (a + b) / 2;
    }
    return r;
}
#endif // MORE_EFFICIENT

/* reinterpret bit pattern of IEEE-754 'binary64' as unsigned 64-bit integer */
uint64_t double_as_uint64 (double a)
{
    uint64_t r;
    memcpy (&r, &a, sizeof r);
    return r;
}

/* reinterpret bit pattern of unsigned 64-bit integer as IEEE-754 'binary64' */
double uint64_as_double (uint64_t a)
{
    double r;
    memcpy (&r, &a, sizeof r);
    return r;
}

/* map an IEEE-754 'binary64' encoding to its enumeration position */
int64_t double_to_enumeration (double a)
{
    const uint64_t FP64_NEG_ZERO = double_as_uint64 (-0.0);
    uint64_t t = double_as_uint64 (a);
    if ((int64_t)t < 0) {
        t = FP64_NEG_ZERO - t;
    }
    return (int64_t)t;
}

/* map enumeration position to IEEE-754 'binary64' encoding */
double enumeration_to_double (int64_t a)
{
    const uint64_t FP64_NEG_ZERO = double_as_uint64 (-0.0);
    uint64_t t = a;
    if (a < 0) {
        t = FP64_NEG_ZERO - t;
    }
    return uint64_as_double (t);
}

/* find midpoint between two IEEE-754 'binary64' numbers a and b, such that
   there is as equal a number of discrete encodings as possible between a
   and the midpoint, and the midpoint and b.
*/
double midpoint (double a, double b)
{
    int64_t ia = double_to_enumeration (a);
    int64_t ib = double_to_enumeration (b);
    int64_t midpoint_i = avg (ia, ib);
    return enumeration_to_double (midpoint_i);
}

/* try test cases from question */
int main (void)
{
    double lb [6] = {
        -INFINITY,
        1.7976931348623155e308,
        -INFINITY,
        0.0,
        -5.0e-320,
        -5.0e-315
    };
    double ub [6] = {
        INFINITY,
        INFINITY,
        1.7976931348623155e308,
        INFINITY,
        1.0e-318,
        1.000004e-318
    };

    printf ("midpoint of % 23.16e and % 23.16e is % 23.16e\n", lb[0], ub[0], midpoint (lb[0], ub[0]));
    printf ("midpoint of % 23.16e and % 23.16e is % 23.16e\n", lb[1], ub[1], midpoint (lb[1], ub[1]));
    printf ("midpoint of % 23.16e and % 23.16e is % 23.16e\n", lb[2], ub[2], midpoint (lb[2], ub[2]));
    printf ("midpoint of % 23.16e and % 23.16e is % 23.16e\n", lb[3], ub[3], midpoint (lb[3], ub[3]));
    printf ("midpoint of % 23.16e and % 23.16e is % 23.16e\n", lb[4], ub[4], midpoint (lb[4], ub[4]));
    printf ("midpoint of % 23.16e and % 23.16e is % 23.16e\n", lb[5], ub[5], midpoint (lb[5], ub[5]));

    return EXIT_SUCCESS;
}

```

The program's output should look similar to this:

```
midpoint of -1.#INF000000000000e+000 and  1.#INF000000000000e+000 is  0.0000000000000000e+000
midpoint of  1.7976931348623155e+308 and  1.#INF000000000000e+000 is  1.7976931348623157e+308
midpoint of -1.#INF000000000000e+000 and  1.7976931348623155e+308 is -4.9406564584124654e-324
midpoint of  0.0000000000000000e+000 and  1.#INF000000000000e+000 is  1.5000000000000000e+000
midpoint of -4.9999443359134150e-320 and  9.9999874849559983e-319 is  4.7499965256823284e-319
midpoint of -5.0000000022897320e-315 and  1.0000036891520582e-318 is -2.4994999993002900e-315

```

---
Tags: approximation, floating-point, numerical-algorithms, intervals
---


# Question
Title: Solve $T(n) = \frac78T(\frac78n) + \frac78n$
The recurrent function $T(n) = \frac78T\left(\frac78n\right)+\frac78n$ where $T(1) = 0$ and $n = \left(\frac87\right)^k$ represents the running time of an algorithm. How can I find a more simple form (depending only on n) of this function? I kept replacing $T\left(\frac78n\right)$ and $T\left(\frac78\times\frac78n\right)$ etc ... with its value but I don't seem to have any pattern.

# Answer
> 1 votes
You can show that $\frac78n\leqslant T(n) \leqslant n\sum\limits\_{i = 1}^{+\infty}\left(\frac78\right)^i = 7n$.

# Answer
> 0 votes
Let $S(k) = T((8/7)^k)$. Then $S(0) = 0$ and $$ S(k+1) = \frac{7}{8} S(k) + \left(\frac{8}{7}\right)^k. $$ Unrolling, we get \begin{align} S(k) &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} S(k-1) \\ &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} \left(\frac{8}{7}\right)^{k-2} + \left(\frac{7}{8}\right)^2 S(k-2) \\ &= \cdots \\ &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} \left(\frac{8}{7}\right)^{k-2} + \left(\frac{7}{8}\right)^2 \left(\frac{8}{7}\right)^{k-3} + \cdots + \left(\frac{7}{8}\right)^k S(0) \\ &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} \left(\frac{8}{7}\right)^{k-2} + \left(\frac{7}{8}\right)^2 \left(\frac{8}{7}\right)^{k-3} + \cdots + \left(\frac{7}{8}\right)^{k-1} \\ &= \left(\frac{8}{7}\right)^{k-1} \left\[ 1 + \left(\frac{7}{8}\right)^2 + \cdots + \left(\frac{7}{8}\right)^{2(k-1)} \right\] \\ &= \left(\frac{8}{7}\right)^{k-1} \frac{1-\left(\frac{7}{8}\right)^{2k}}{1-\left(\frac{7}{8}\right)^2} \\ &= \frac{64}{15} \left(\frac{8}{7}\right)^{k-1} - \frac{64}{15} \left(\frac{7}{8}\right)^{k+1}. \end{align} If $n = (8/7)^k$, then this gives $$ T(n) = \frac{56}{15} n - \frac{56}{15} \frac{1}{n}. $$

# Answer
> 0 votes
Regarding the recurrence

$$ T\left( n\right) = c T\left(\frac{a}{b}n \right) + f(n) $$

with $\\{a,b,n\\}\in \mathbb{N}^+$, $a,b$ relative primes, $c\in \mathbb{R}$. Considering now $n = b^m q$ with $\\{q,m\\}\in \mathbb{N}^+$ and $q \not|\\; b$, the path from $n = b^m q$ to extinction is

$$ \\{b^m q, b^{m-1}a q,\cdots, b^{m-k}a^k q,\cdots,b a^{m-1}q,a^m q\\} $$

so calling now $T(a^m q)= T\_{q\_0}$ we have

$$ T(b^m q) = c^m T\_{q\_0}+\sum\_{k=1}^{k=m}c^{m-k}f(a^{m-k}b^k q) $$

now making $\lambda=\frac ab$ and with $T\_{q\_0}=0$ analyzing

$$ \lim\_{n\to\infty}\frac{T(n)}{n}=\lim\_{m\to\infty}\frac{T(b^mq)}{b^m q} = \lim\_{m\to\infty}\frac{1-\lambda^{2m}}{1-\lambda^2}\lambda $$

but here $\lambda=\frac ab\lt 1$ so

$$ \lim\_{n\to\infty}\frac{T(n)}{n}=\frac{\lambda}{1-\lambda^2} = \frac{56}{15} $$

---
Tags: recurrence-relation
---


# Question
Title: Why does sorting a collection have O(n log n) complexity?
Reading through https://developer.apple.com/documentation/swift/array/1688499-sort, it states "Complexity: O(n log n), where n is the length of the collection," but I don't have an intuition for why this exactly this is.

# Answer
> 3 votes
The question of why the algorithm implemented by *that particular* function requires time $O(n \log n)$ should be asked to whoever wrote that function (in the documentation they do not mention any particular algorithm).

That said, there are several comparison-based sorting algorithms that require $O(n \log n)$ comparisons (and hence $O(n \log n)$ time to sort elements that can be compared in $O(1)$ time). See, for example, Heapsort or Mergesort.

If you are confused about why sorting cannot be done (asymptotically) faster, then notice that the function you referenced implements some (unspecified) comparison-based sorting algorithm. There is a lower bound of $\Omega(n \log n)$ on the number of comparisons required by *any* comparison-based sorting algorithm. Essentially, since the algorithm needs to be able to output all $n!$ permutations of the input list, it needs to branch at least $\log n! = \Omega(n \log n)$ times.

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: The difference between halting and accepting in a Turing machine in this context
I've read some articles in this forum, e.g. there were professional claimed that a Turing machine does not accept a language but it recognizes it. I respect that but I found the phrase "a language is accepted by a machine" is actually used in the Peter Linz's book. So here I'd rather not touch the choice of words problem if possible, but focusing on the concept of accepting and halting.

Below is my question:

I use the textbook "an introduction to formal languages and automata", 6th edition by Peter Linz.

In Definition 11.2, it seems that a Turing machine "M accepts language L" and "M halts on string w" are different things? Why does the author specifically distinguish these two concepts? Does it mean that they are different?

But if we check Definition 9.3, it says that if M accepts L (L accepted by M) then it eventually reaches a final state qf. For a final state, my understanding is that it means M halts on w, right? In this regard, aren't accepting and halting the same idea?

Are accepting and halting different concepts? Or is there an example that it arrives in qf but does not halt? Thanks.

# Answer
A Turing Machine halts if it either accepts or rejects. For any given input, a TM may loop, accept or reject. So there is certainly a difference between halting and accepting, viz. accepting always implies halting but not vice versa.

I'm guessing here that $\square$ is shorthand for the reject state.

As for your earlier comment: a language is recognizable iff it is recursively enumerable iff a Turing Machine accepts it.
> 2 votes

# Answer
"$M$ accepts language $L$" and "$M$ halts on string $w$" are different things, because $w$ and $L$ are different things. Acceptance is about $M$'s behavior on arbitrary strings.

While this is a trivial answer to a trivial question, you also (implicitly or explicitly) ask some nontrivial questions:

1. Can acceptance be defined in terms of halting?
2. Why doesn't it seem to happen in this textbook?
3. Do different textbooks disagree on these matters?
4. Are accepting a language and recognizing a language the same thing?

Let's take them in turn.

**1. Can acceptance be defined in terms of halting?**

Yes, it can. My textbook (*Elements of the Theory of Computation*, by Lewis & Papadimitriou) does so (p. 179):

> We say that a Turing Machine $M$ accepts a string $w$ if $M$ halts on input $w$. Thus $M$ accepts a language $L$ if and only if $L = \\{w \mid M$ accepts $w \\}$.

**2. Why doesn't it seem to happen in this textbook?**

We'd have to ask the author, but I fear the answer is: this particular set of definitions doesn't happen to do so, and it does the job. More on that below.

**3. Do different textbooks disagree on these matters?**

Absolutely. Different articles and textbooks use may different definitions, to the extent that the same statement may be true according to one textbook and false according to another.

So in this case, we need to know exactly what is meant by a *Turing Machine* and *halting*.

Generally speaking, halting is either defined as

* reaching a configuration in which no further transition is possible, or
* reaching a configuration in which the state belongs to one or more states specially marked as "final"

In my textbook, a Turing Machine has a *total* transition function that relates each possible (state, tape symbol) pair to exactly one (state, action) pair, where an action either specifies a tape symbol to write, or to move left, or to move right.

Because the transition function is total, the first notion of halting cannot be used: the machine would never halt on any input. Consequently, the definition includes a special halting state, $h$, outside the domain of the transition function: while it can be a destination state of transitions, no transitions are defined for it. Halting is defined as reaching a configuration in which the current state is $h$. With this definition, this is equivalent to defining halting as reaching a configuration in which no further transitions are possible.

In your textbook, a Turing Machine has a *partial* transition function that relates each possible (state, tape symbol) pair to at most one (state, symbol, action) triplet, where the symbol is written, and the action is to move left, or to move right.

The function is partial, so the first notion of halting could be used. Is it?

This is where your textbook starts to confuse me. It still includes a set of "final states" $F$ into the definition of a Turing Machine. Then, it says:

> Eventually, the whole process may terminate, which we achieve in a Turing machine by putting it into a **halt state**. A Turing machine is said to halt whenever it reaches a configuration for which δ is not defined; this is possible because δ is a partial function. In fact, we will assume that no transitions are defined for any final state, so the Turing machine will halt whenever it enters a final state.

But, professor ...

* You say you assume this, but your definition doesn't.
* Even when you assume this, your Turing machines may still halt in non-final states, unless your transition function is required to be total on non-final states. But you never mention or require this.

As we shall see, this is intentional.

So *final states* and *halt states* are not the same thing:

* *halt states* are states in which the Turing machine may possibly halt;
* in some (or all) of them, it will *always* halt;
* some (or all) of those are "final states".

This is a consistent definition, but an abuse of language. We would expect the set of final states to be the set of states in which the machine may, and will, halt. It isn't always, in this case. Hence my confusion, and yours.

Definition 9.2 (above) then goes on to define a machine accepting a string as the machine reaching a final state with that string as input. As we've seen, with these definitions, this is *not* the same thing as the machine halting on that string.

While this definition of acceptance is horribly confusing and inconsistent with other textbooks, it is internally consistent. However, I feel the textbook goes off the rails when discussing *loops*.

First, it introduces the concept, suggesting that an infinite loop is a sequence of transitions in which the exact same configuration is reached for a second time, causing the exact same sequence of transitions to repeat infinitely often.

It reinforces this by saying:

> Example 9.3 shows the possibility that a Turing machine will never halt, proceeding in an endless loop from which it cannot escape. This situation plays a fundamental role in the discussion of Turing machines, so we use a special notation for it. We will represent it by indicating that, starting from the initial configuration $x\_1 q x\_2$, the machine goes into a loop and never halts.

It then adds:

> Definition 9.3 tells us what must happen when w ∈ L(M). It says nothing about the outcome for any other input. When w is not in L(M), one of two things can happen: The machine can halt in a nonfinal state or it can enter an infinite loop and never halt. Any string for which M does not halt is by definition not in L(M).

We've already seen that this definition of acceptance is needlessly confusing; but what it says about infinite loops is plainly *wrong*.

It is *not* the case that all Turing machines will either halt or enter into an infinite loop on every input. It is fundamental to the computational power of Turing machines that many of them do neither, and instead, proceed endlessly without ever going into an infinite loop.

The author can weasel his way out of this by saying that he never actually provides a definition of what it means for a machine to loop on a given input. He can say: what I meant to say is that the machine doesn't halt on that input.

(I'm not picking on this because prof. Linz is particularly bad in this regard; I am because he is not. Nonstandard definitions and sloppy wording are very common in computer science. The field is rife with mathematicians in the best Von Neumann tradition: you're not supposed to make sense of the words they use, you're supposed to follow the definitions and make sense of the math. Plenty of mathematicians and IT persons consider words to be arbitrary placeholders; as long as the math makes sense, or the story makes sense, they don't care what things are called. It pays to bear this in mind when studying computer science related topics. Always look at the definitions. Never trust stories without definitions. Also bear in mind that definitions for terms may not actually correspond to the way the same words are used in the text.

In this particular case, Linz acceptance makes sense because it is equivalent to Lewis & Papademetriou acceptance: given a Linz TM Linz-accepting a language, one can construct an L&P TM L&P-accepting the same language, and vice versa.)

**4. Are accepting a language and recognizing a language the same thing?**

It depends on one's definition of *recognizing*. What ultimately matters is the fundamental difference between a Turing machine merely *accepting* a language and a Turing machine *deciding* a language.

As prof. Linz emphasizes, when a Turing machine accepts a language, it halts on every input belonging to that language, but it may not halt on input that doesn't. A language for which such a Turing machine exists is called *semi-decidable*.

When a Turing machine decides a language, it halts on every input, and somehow points out whether or not it belongs to the language. A language for which such a Turing machine exists is called *decidable*, or *recursive*. Not all semi-decidable languages are decidable.

The Linz and L&P textbooks have different ways of formalizing this difference; what matters is that they make the distinction clear.
> 1 votes

# Answer
The key here is that it says it "halts on **every** input $w$ in $\Sigma^+$". If it's possible that the TM may not halt in **some** of the input, then it's not recursive. Why is it possible? Because the input $w$ comes from all possible strings ($\Sigma^+$), not just those strings that will arrive in the accept state ($L$).

In other words, the TM should always halt (and end in accept state) if the input comes from $L$, this is the first part of the requirement. The second part is about when the input is coming from all possible strings. The TM should halt in all of these.
> 0 votes

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


# Question
Title: Prove that $L=\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \}$ is CFL
I've faced a question in my homework, I was able to solve it but not as desired.

***Question:*** Given the language $L=\\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \\}$, Prove that it's a CFL (***Note:*** it can be solved without using CFG or PDA).

***My Answer:*** I provided the CFG: $$S\rightarrow 0T11\\T\rightarrow 000T111\ |\ \varepsilon$$

***Explanation:*** The reason I did this that as I see the language consists of the words $(011,000011111,000000011111111,\dots)$ meaning that $(\\#\_0\ mod\ 3=1 \ and\ \\#\_1=\\#\_0+1)$.

I think my solution is true but still, I'm curious how can I solve it without using CFG or CFL, I tend to think that it can be done by using closure properties of CFLs along with pre-learned CFLs.

***Note:*** I've learned that the below language is CFL: $$\\{0^n1^n\ :\ n\in \mathbb{N} \\}$$ I don't know if it really helps.

If anyone can provide a solution even though using CFLs that he isn't sure I learned or not, I'll be thankful.

# Answer
The data given in your question are perfectly enough to construct the required solution.

The main observation is that we must start from the known CFL-s and use the closures to obtain the given $L$. So, we start from $\\{0^n 1^n\\,|\\,n\in\mathbb{N}\\}$ with no restriction on $n$. Then we use the intersection with a regular language, that can be easily constructed by you given your observation on the constraint $4n + 2 = 6k$. And finally, we concatenate the result with the other regular language (which is also, of course, CFL), namely, $\\{1\\}$. As a result, we obtain your language $L$. QED

The opposite direction does not work, though. If we take the language $L$ and concatenate it with the language, i.e. $1^\*$, we will obtain the regular language, but that proves nothing about the initial language $L$. The simple example is the language $L' = \\{ww\\,|\\,w\in\\{a,b\\}^+\\}$ concatenated with $L''=\\{a,b\\}^\*$ on both sides. Every word in the alphabet $\\{a,b\\}$ of length no less than 4 contains a square subword (a subword of the form $ww$), thus the language $L'' L' L''$ is regular. But the initial language $L'$ is not even context-free.

Thus, the reasoning works in the direction "given a known CFL, construct the target language using closures", not vice versa.
> 2 votes

# Answer
The language $L\_1 = \\{0^n1u\mid \exists k: 4n+2=6k, u\in \\{0,1\\}^\*\\}$ is regular. There exists a DFA with 4 states recognizing it (proof left to you).

As you have stated, the language $L\_2 = \\{0^n1^n\mid n\geqslant 0\\}$ is CFL.

Then $L = L\_1\cap L\_2\\{1\\}$ is an intersection of a regular language and a CFL, hence is CFL.
> 2 votes

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


# Question
Title: What properties must a string satisfy to be a possible output of the Burrows-Wheeler transform?
The Buttows-Wheeler transform is a function that takes a string $S$ to a new string $S'$ and an index $I$. The new string $S'$ is always an anagram (rearrangement) of the input string $S$.

However, if I pick a random string $S'$ and index $I$, the inverse Burrows-Wheeler transform usually fails. For example, if $S'$ is `"QUICK"`, the (intuitive, block-sorting) inverse method results in the following block:

```
CQCQC
IKUIK
KUIKU
QCQCQ
UIKUI

```

Clearly, none of the rows is an anagram of `"QUICK"`, no matter the choice of $I$.

What properties must the string $S'$ satisfy so that the block contains at least one anagram of $S'$? (I suspect that if one of them is an anagram, they all are, but I don’t know how to prove it.)

# Answer
> 2 votes
Consider a string with repeats of a letter, for example `BANANA`. The forward transform will create this block:

```
ABANAN
ANABAN
ANANAB
BANANA
NABANA
NANABA

```

Now imagine we label every occurrence of `A` with `1`, `2` or `3` depending on which `A` in the original word it is.

Observe that the `A`’s in the leftmost column are in the same order as in the rightmost column. This is because they are both sorted by whatever text comes after them in the original string.

Now imagine we take an arbitrary string $S'$ of length $n$ and label the letters in alphabetical order, but identical letters in order of occurrence. For example, for BANANA the labeling would be:

```
BANANA
415263

AAABNN  (sorted)
123456

```

This list of digits from $1$ to $n$ can be interpreted as a permutation (rearrangement).

In order to be a possible output of the Burrows-Wheeler transform, the string $S'$ must have *one* of the following properties:

1. all letters in the string are the same; or
2. the permutation is a full cycle (i.e. it has order $n$).

For example, the word “QUICK” does not work because Q and C form a separate cycle from the rest of the letters:

By contrast, “QUIKC” works because the permutation of letters now forms a single complete cycle:

This property of $S'$ is necessary because without it, the inverse BWT couldn’t reconstruct the string $S$: instead of visiting every character, it would visit only the characters contained in one of the cycles (and visit them multiple times).

This property of $S'$ is also sufficient because once it is met, the inverse BWT can be performed on it to produce a string $S\_i$ (with any index $i \in \left\\{0..n-1\right\\}$). The result of this is a string which will reconstitute $S'$ when run through BWT again.

---
Tags: algorithms, strings, data-compression
---


# Question
Title: If A reduces to B and B reduces to C, does that mean A reduces to C?
If A is in the class P, B is NP-complete, and C is not in the class NP. And A reduces to B and B reduces to C. Which statements are true?

1. A is in the class NP.
2. A reduces to C.
3. If S is a candidate solution to an instance I for problem A, we can check in polynomial time if S is indeed a solution.
4. C is NP-hard.

I think 3 is correct because A is in class P, and 4 is correct because All NP-hard problems are not in NP. I am not sure about 1 and 2

# Answer
I assume you are talking about polynomial-time many-one reductions. I will denote $\leqslant\_m^p$ these reductions.

1. $A\in \mathsf{NP}$ because $\mathsf{P}\subset \mathsf{NP}$. This result does not depend on $B$ and $C$;
2. $A\leqslant\_m^p C$ because $\leqslant\_m^p$ is a transitive relation (proof left to you);
3. This is correct, $A\in \mathsf{NP}$ (see first point);
4. $B$ is $\mathsf{NP}$-complete and $B\leqslant\_m^p C$. Since $\leqslant\_m^p$ is transitive and given the definition of hardness and completude, $C$ is $\mathsf{NP}$-hard.

All four statements are true.
> 1 votes

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


# Question
Title: When to stop training a back propagation algorithm based on the MSE?
I have a fully connected neural network that consists of 3 inputs + bias, 4 neuron hidden layer, and 2 layer output, I am using the sigmoid activation function on the hidden layer only and use the backpropagation algorithm. I am using the following training data:

```
[ 0.50,  1.00, 0.75, 1],
[ 1.00,  0.50, 0.75, 1],
[ 1.00,  1.00, 1.00, 1],
[-0.01,  0.50, 0.25, 1],
[ 0.50, -0.25, 0.13, 1],
[ 0.01,  0.02, 0.05, 1]

```

with the following target outputs

```
[1, 0],
[1, 0],
[1, 0],
[0, 1],
[0, 1],
[0, 1]

```

I want to understand when I should be stopping the training of data, I've read a few scientific/academic articles mentioning not to overfit or underfit the number of iterations (epochs) you have. However, I am struggling to know when.

The graph I get after 1000 epochs showing the mean square error and root square error rates:

**If someone can tell me / give me some advice on the optimal amount of epochs for my neural network. Or if I could be linked some more academic or scientific articles talking about this issue, it would be great!**

# Answer
> 2 votes
If you have already split your data into three sets (i.e. training, validation and testing), then it is useful to track the training loss and validation loss for each epoch. The number of epochs is like any other hyperparameter you have to tune. A classic situation of overfitting occurs when your training accuracy keeps increasing while your validation accuracy remains the same (or in some cases even starts falling). The point at which your validation accuracy stops showing improvement compared to your training accuracy is when you should stop.

---
Tags: algorithms, machine-learning, artificial-intelligence, python
---


title: Difference between this grammar

text:
# Question
Title: Difference between this grammar
I was reading a book and there is a part in which they use this grammar
$$ X \rightarrow xY $$ $$ Y \rightarrow yZ $$ $$ Z \rightarrow z$$ $$ Z \rightarrow \lambda $$

and other times they use this other one $$ X \rightarrow xyz $$ $$ X \rightarrow x $$

It mentions that both are equivalent but I don't understand why it is preferable to use the first grammar than the second grammar. Could you help me, please?

# Answer
> 2 votes
Let us assume a variant of your example, one that indeed has a pair of equivalent grammars.

$X\to x \mid xyz$

$X\to x Y \hspace{1cm} Y\to yz \mid \varepsilon$

Here the second grammar is preferable to the first one in the context of parsing. It is obtained by a process called left factoring, which is one of the tricks to make a grammar LL(1).

# Answer
> 1 votes
They are not equivalent. Consider the string `xy`. With the first grammar, the string can be generated.

$$ X \rightarrow xY \rightarrow xyZ \rightarrow xy $$ However, with the second grammar, it cannot be generated given the two rules.

---
Tags: automata, finite-automata, cellular-automata
---


title: Integer/prime factorization to 3 SAT

text:
# Question
Title: Integer/prime factorization to 3 SAT
So essentially as the title says, I just want to understand how its done. I have a light idea from my own research, but its failing at one point, and I feel it maybe due to crucial point missing in my understanding.

My understanding is to form a multiplication circuit of 2 n-bit variables, so for ex. X0 x1 .. xn and also y0 y1 ... yn, and the output of this multiplication circuit should be put into a bit wise comparator circuit, with our number that we want to factor which is of size 2N bits. Then follows that we turn this circuit to sat through the tseitan transformation, and from there to 3sat.

Now here comes my problem, I don't understand how that could get me the factors of the number. I understand that a Satisfiable instance at most will let me know that this number is prime, since there is two number x and y, that when multiplied result in my number, but what are they? And what about the other numbers? Am I missing something or what am I misunderstanding?

Thank you

# Answer
> 1 votes
> I understand that a Satisfiable instance at most will let me know that this number is prime

It's the other way around: if the instance is satisfiable, then the number of interest (let's call it $Q$) is *not* prime, and $x$ and $y$ are non-trivial divisors of $Q$. $Q = x \cdot y$ by definition. If there is no solution to that equation, then the instance is unsatisfiable. $x$ and $y$ need not be *factors* of $Q$ because they're not necessarily prime. When a SAT instance is satisfiable, you normally, at least in practice, get a specific valuation as proof, from which you can read off the values of $x$ and $y$. Even if you don't get that, you can find them by binary search: force the first bit to False and see whether the result is still satisfiable, etc.

Unfortunately with this exact set-up, using two n-bit variables and a 2n-bit $Q$, an unsatisfiable instance does not in general prove that $Q$ is prime, because $Q$ could be of the form $2P$ (with $P$ a prime), then there is a solution to $Q = x \cdot y$ but not in such a way that $x$ and $y$ both fit in n bits because $P$ would be $2n-1$ bits and there is no other factorization of $Q$. But you could make some assumptions about the factors or make one of the variables bigger.

# Answer
> 0 votes
You have to go back to the proof that factorisation is in NP: Problem: Given n \>= 2, find a sequence n1, n2, … such that n is the product of the $n\_k$ and each $n\_k$ is a prime.

The “hint” that you need to check in polynomial time is the list of the $N\_k$, plus for each one a proof that it is indeed prime. For example, 30 = 3 * 10 is not a correct factorisation.

And you need to turn both the product check and the primality tests into a 3 SAT instance.

(PS. It is now known that primality can be proven in polynomial time. But verifying primality given a proof is much easier).

---
Tags: satisfiability, 3-sat, primes, factoring
---


# Question
Title: If every 2 languages are that have Polynomial reduction have LOG SPACE reduction does L=P?
If every 2 languages $A,B$ that have Polynomial reduction $A\<\_pB$ have LOG SPACE reduction $A\<\_LB$, does $\mathsf{L}=\mathsf{P}$?

# Answer
> 1 votes
The answer is yes. We know that L is included in P (hierarchy of languages) We'll show that P is included in L:

Let A be Polynomial and B L We can reduce A to B Polynomialy (hierarchy) Thus we can reduce A to B LogSPACE hence A is included in B as required

---
Tags: complexity-theory
---


# Question
Title: Partitions with subsets of limited cardinality
Is there a way to compute the number of partitions such that each set in the partition has a cardinality lower or equal to two? If yes, is there also an efficient algorithm to compute these partitions?

# Answer
For a set with $n$ values, the number of possible "partitions" $P(n)$ will follow the recurrence: $$P(n)=P(n-1)+(n-1)\cdot P(n-2)$$ Since for the first subset in the partition, you can choose either it to contain only the first element (leaving $n-1$ elements that also have to be partitioned), or choose it to contain the first element, and another one of the other $n-1$ element (leaving $n-2$ elements for the recurrence).

Now, you can try to solve the recurrence and find a closed form if you like to.
> 2 votes

---
Tags: partitions
---


# Question
Title: Divide and Conquer to identify a knight from n people
So I am doing an exercise in which there are $n$ people who are either knight or rogue, more than $\frac{n}{2}$ are knights. You are a princess and would like to marry a knight and do not want to accidentally marry a rogue.

You can select any pair of the $n$ people to make them point out each other's identity. The knight will always tell the truth, while the rogue may or may not. If there are two rogues being interrogated, they **may** say each other is good to deceive you.

How can I design an efficient algorithm for the princess to find out a knight?

My attempt:

So I can pit one person j against the other $n-1$ persons to find out if j is knight or rogue. There are $k \> \frac{n}{2}$ knights, and $r \leq \frac{n}{2}-1$ rogues.

If j is a knight, then he will be pitted against $k-1$ other knights and $r$ rogues. So there are $\geq \frac{n}{2}$ cases in which both say the other person is knight, and there will be $\leq \frac{n}{2} - 1$ cases that at least 1 person is accused of being a rogue.

If j is a rogue, then j will be pitted against $k$ knights and $r-1$ other rogues, resulting in $k$ cases of at least one rogue accusation, and at most $r-1$ cases of both being said to be knight (as the 2 rogues may or may not team up to deceive the princess).

Looking at the distribution of cases "both say the other is knight" and "at least one rogue accusation", we can identity if the person being examined is a knight or rogue.

If I am to brute force, then I can do $O(n)$ queries for each person, giving $O(n^2)$ time.

But I am uncertain how to do divide and conquer here.

I can eliminate dividing naively into $\frac{n}{2}$ sizes, because the distribution of knights and rogues will no longer follow the initial more than $\frac{n}{2}$ knights.

One idea I have is, initially pick one person j and do the pairing with $n-1$ others to see if he is knight or rogue. If he is knight then we're done. If he is rogue, then we can know which in the previous results must be rogues. The other person in the cases of "both knights" must be rogue. Also, in the cases of "one knight one rogue", those who say j is knight are lying and must be rogues.

So we select the ones who are either a rogue that didn't lie, or a knight, and recurse on them.

The worst case would be that every rogue does not lie.

What are you thoughts on this? Thank you!

# Answer
> 10 votes
#### An efficient algorithm using stack

1. Initialize an empty stack.
2. For each person $p$ in the given people:
    * If the stack is empty, push $p$ to the stack.
    * Otherwise, pit $p$ against the person at the top of the stack.
        + If both say the other one is a knight, either both are knights or both are rogues. Push $p$ to the stack.
        + Otherwise, at least one of them is a rogue. Pop the stack once.
3. Return the person at the top of the stack.

---

The time-complexity of the algorithm is $O(n)$.
The space-complexity of the algorithm is $O(1)$ if we can reuse the input array as a stack.

#### Two Exercises

**Exercise 1** (easy). Explain why all people in stack at the end are knights.

**Exercise 2** (easy). Suppose the number of knights is equal to the number of rogues instead. Show that it is impossible to find a knight for sure in the worst case.

# Answer
> 8 votes
Our princess proceeds as follows:

* she asks her suitors to form up on a line
* starting from the left, she asks each person about the virtue of their neighbour (and vice versa)
    + if there is an accusation of rogueness
        - she sends both of them away
        - if there are people on either side of the gap, they are now neighbors. She will investigate them next as she continues her walk along the line.
    + everyone to her left is of equal virtue. If that's more than half of the people remaining, these must be the knights, and she can pick any of them

It easy to see that this process eliminates at least as many rogues as knights, thereby maintaining the honest majority.

It also easy to see that this process is efficient: With every question, the number of people to the right of the princess decreases by one. The princess will therefore ask at most n-1 questions.

# Answer
> 3 votes
This can be solved efficiently with the Boyer-Moore majority algorithm. Everyone casts a vote on the candidate currently occupying the hot seat. When the count reaches zero, the candidate is evicted and the next one takes the seat. The algorithm takes constant space and N-1 tests maximum.

```
def find_knight(candidates):
    victor = None
    count = 0
    for candidate in candidates:
        # Take the seat if empty. Set counter to 1 because
        # the candidate presumably supports himself.
        if count = 0:
            victor = candidate
            count = 1
        # Otherwise upvote or downvote the sitting candidate.
        elif supports(candidate, victor):
            count += 1
        else:
            count -= 1
    return victor

```

# Answer
> 2 votes
Here is a divide-and-conquer algorithm that performs 2N tests maximum. At each stage we perform N tests and eliminate at least half of the candidates.

```
def find_knight(candidates):
    # No solution if there are no candidates.
    if len(candidates) == 0:
        return None
    # Set one aside if there is an odd number of candidates.
    if len(candidates) % 2:
        unpaired = candidates.pop()
    # Divide the candidates into N/2 pairs and ask them about each
    # other. Eliminate both if they accuse each other, else keep one.
    remaining = []
    for i in range(len(candidates) // 2):
        a = candidates[2*i]
        b = candidates[2*i+1]
        if supports(a, b) and supports(b, a):
            remaining.append(a)
    # Recursive call, might return no solution if we
    # set aside a real knight (and only then).
    solution = find_knight(remaining)
    if solution is None:
        solution = unpaired
    return solution

```

To prove correctness, prove that:

1. If knights make up at least half of the candidates before elimination, this also holds after elimination.
2. If there is an odd number of candidates after elimination, there are strictly more knights.
3. If we set the unpaired candidate aside, knights still make up at least half of the remaining candidates.
4. If there are equally many knights and rogue, there might be no solution.
5. If there is no solution, the one we set aside must have been a knight.

# Answer
> 0 votes
Given are m people, all either knight or rogue, and more knights than rogues. We want to find one knight (one is enough). We want to do this with the minimum amount of questions, and the rogues will try to make us ask as many questions as possible.

First an observation: If the number of knights and rogues is the same, then we can't determine a knight by asking people whether others are knights or rogues. That's because the rogues will try to hide their identity by always lying about someone else's identity; they will always claim that another knight is a rogue, and that another rogue is a knight. This means, if we changed every single person's identity from knight to rogue or from rogue to knight simultaneously, then we would get the exact same answers, but whoever we picked as a knight would now be a rogue. So it is necessary that we have more knights than rogues and must not do anything that changes things. And it means that if only two persons are left, they are both knights (a rogue + more knights than rogues requires at least three).

Assume m = 2n+1. There are at least n+1 knights. Let L be the last person. We ask the first 2n whether L is a knight. A knight will get at least n "yes" votes (n votes from the other n knights, and possibly votes from one or more rogues). A rogue will get less than n "yes" votes, because the n+1 knights will all say L is a rogue. So once we got n "yes" votes, L is a knight and we are done. If we get fewer than n "yes" votes, then L is a rogue and can be removed. At that point we can also remove everyone who claimed that L was a knight, because they lied and must be rogues.

How will rogues vote so we need to ask the largest amount of questions? If L is a knight, we *know* this will be found, as soon as n knights have been asked, or earlier if some rogues claim he is a knight. So the rogues will all claim L is a rogue, delaying the decision until we asked the n-th knight.

If L is a rogue, that will also be found out, but it will not end the problem. We know L is rogue as soon as n+1 people claimed he is rogue. But everyone who claims L is a knight will out himself as a rogue. So best case, we know L is rogue after asking n+1 people who claim this. If k rogues claim L is a knight, we need to ask n+1+k people to know L is rogue, but k people will now be known to be rogue and can be removed. That gives us additional information that could be used in the next round: We will know that the number of knights exceeds the rogues by k+1, which makes it easier. The rogues will avoid giving us the extra information, so they will all claim L is rogue and L is identified after asking n+1 people. We then have an even m.

We know have 2n persons. It was suggested to line them all up and ask each what his neighbour is, and if anyone says the neighbour is rogue, then one of them must be rogue and we remove them both from the game. However, the rogues don't like this, so they will always claim the next person is a knight. If we have n knights followed by n rogues, only one person will claim the next one in the line is a rogue. Instead we arrange them in n pairs and ask each in the pair what the other is.

If a pair is a knight and a rogue, one or both will answer "rogue", and we know that one is a rogue - we remove both. Otherwise, two knights or two rogues will both claim that the other is a knight. Once done, we have k pairs left over both claiming they are both knights, but they will both be knights, or both rogues.

We remove one from each pair. We will have half the knights and half the rogues of before, so again more knights than rogues. Unless the total is 2 or less, we ask them all again. Here the worst case is that all pairs are either both knights or both rogues, so in 2n questions we have reduced the problem to finding a knight amount n people using n steps.

So in the worst case, we need 3n questions to remove the number of candidates from 2n to n. If we pick the pairs at random, there is a 50% chance that there is exactly one rogue in the pair, and a 25% that we know there is a rogue after the first question. So on average the number of people gets reduced to n/2 (n people in pairs of two knights or two rogues, and half removed later) after 2.75 questions; but then rogues will try to make sure that an the number of people remaining is odd. If there are say 100 pairs of two knights or two rogues, the last pair of two rogues will claim they are both rogues - leaving 99 instead of 100 people.

---
Tags: algorithms, divide-and-conquer
---


title: Efficiency of UDP protocol

text:
# Question
Title: Efficiency of UDP protocol
When 54 bytes of data is transferred using the UDP protocol, the efficiency is? (In per cent)

IN UDP, the maximum datagram size can be $2^{16}-1 \\, bytes$

Now to this, 8 Bytes of UDP header is included and this together must fit within $65535\\, bytes$ IPv4 packet limit(Including 20B IP Header size).

So, maximum data that we can send in 1 UDP datagram-\> $65535-8-20=65507\\,Bytes$

We could have sent this amount of data, but we are actually sending 54 Bytes, so the efficiency of the protocol is $\frac{54}{65507} \times 100(\\,in\\,\\%)$

Am I correct?

# Answer
We are not sending a full packet, so there is no need to consider the maximum size of a packet when calculating. The efficiency is usually expressed as the ratio of the "data we want to send" to all the data being sent, which in your case would give:

effieciency = (54/(54+28))\*100% ~ 66%

We would have to consider the maximum size of the packet when calculating the maximum efficiency of a UDP protocol, which describes a case scenario where a full packet is sent.
> 1 votes

---
Tags: computer-networks
---


# Question
Title: I require assistance in proving this language as not regular
I'm trying to prove that L = {$0^n1^m0^n | m,n \>= 1$} in NOT regular but I am struggling with the demostration process.

I know the conditions are that:

* $|y| \> 0$; $'y'$ can't be empty
* $|xy| \<= p$(word/string length)
* for all $i$ \> 0, $xy^iz$ must be in L

Lets choose the string $s = 0^p10^p$.

The first condition states that: $y = 0^k$ for $k \> 0$

Being $x$ and $y$ composed of zeros such that complies with the second condition.

At $i = 0$, the string should be in L, thus $xy^0z = xz = 0^{p-k}10^p$ but $y$ can't be empty, right?

**From now on, I get lost in the demostration and require help to properly prove it is not regular.**

# Answer
First of all, the empty pump matters (in fact, sometimes the empty pump, e.g. the case $i=0$ is the simplest way to prove the non-regularity). Thus, the third condition is actually *"for all $i\geq 0$ $x y^i z\in L$"*. The condition *"$y$ can't be empty"* is not about the iterations number (e.g. the string $y^i$), it states that the word $y$ itself is not empty. Otherwise, every language is trivially pumped if we choose $y=\varepsilon$ and the lemma is meaningless.

Thus, your proof is correct, using the empty pump. If you do not like the case $i=0$, you may choose $i=2$ and get another word $0^{p+k}10^p\notin L$, but imo your choice is nice enough.

The only imprecise part is about the order of the applications of 1st and 2nd conditions. If you do not apply the condition $|xy|\leq p$ to the word $0^p 1 0^p$, you cannot know in advance that $y$ consists of zeros. There are many non-empty subwords of $0^p 1 0^p$ containing also $1$. The condition $|y|\>0$ determines that $y=0^{k}$, $k\>0$ only after the second condition determines that $y\in 0^\*$.
> 2 votes

---
Tags: formal-languages, regular-languages, automata, finite-automata, pumping-lemma
---


title: What's wrong in this network topology?

text:
# Question
Title: What's wrong in this network topology?
> What are the six mistakes that were made in the configuration of the following network?

I could only find 3. Since the subnet on the left has `192.168.10.33` as HostMin and `192.168.10.38` as HostMax, `Host A4` and `Host A5` cannot be in this subnet. `Subnet A` should also have the IP `292.168.10.0` because it's a network address.

I can't seem to be able to find the other 3, what am I missing?

# Answer
On a quick overview, I can find the following problems:

1. The IP address `192.168.10.32` for interface `eth1` of the router is the network address for Subnet A `192.168.10.32/29`. While this generally works, there are some really ancient RFCs that prohibit the use of network addresses for hosts. Typically, the address of a router is either the first or the last host address in a network, in this case either `192.168.10.33` or `192.168.10.38`.
2. The same applies to the IP address `192.168.12.0` for interface `eth2` of the router, which is the network address of Subnet B `192.168.12.0/23`. Traditionally, the router address would either be `192.168.12.1` or `192.168.13.254`.
3. The IP address `192.168.13.0` for interface `eth0` of the router is within Subnet B `192.168.12.0/23`. Presumably, this is supposed to be the upstream interface to the rest of the world and would thus be in some public subnet, a DMZ, a transit subnet, or maybe an RFC 3021 Point-to-Point /31 subnet.
4. The EUI-48 MAC address of Switch B `00-11-27-82-H3-E6` is not a valid hexadecimal number representation. Hexadecimal number representation only uses the symbols `0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`, `a` / `A`, `b` / `B`, `c` / `C`, `d` / `D`, `e` / `E`, and `f` / `F`.
5. The IP address `192.168.10.39` of Host A4 is the broadcast address for Subnet A `192.168.10.32/29`. Broadcast addresses must not be used for hosts.
6. The IP address `192.168.10.40` of Host A5 is outside Subnet A `192.168.10.32/29`.
> 2 votes

---
Tags: computer-networks, network-topology, network-analysis
---


# Question
Title: Prove that EXIST = {$<M>$:There exists a string $w ∈ Σ*$ such that $M$ halts on $w$} is undecidable
This is a question by my professor Z. Luria in my Computability course.

My first approach was to try and prove it by contradiction, assuming that EXIST is decidable and using the algorithm that decides EXIST to decide HALT which leads to contradiction - but I didn't managed to do so.

Then I tried to prove by Reduction from HALT to EXIST but I fail to define the reduction function.

My main issue with both approaches is that the two Machines receives two different things (and not for example two machines or a machine and a word $w$)

It seems like a rather easy reduction/proof by I'm new to this subject

# Answer
Given a Turing machine $T$ and a input word $x$, you can compute the description of a Turing machine $M\_T^x$ that ignores its input, rewrites the tape to contain $x$, and then simulates $T$.

Now, either $M\_T^x$ halts for all input words $w$, or it doesn't halt for any. Moreover, $M\_T^x$ halts if and only if $T$ halts with input $x$, i.e., $M\_T^x \in \mathsf{EXIST} \iff \langle T, x\rangle \in \mathsf{HALT}$.

Since $\mathsf{HALT}$ is indecidable, so is $\mathsf{EXIST}$.
> 1 votes

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


# Question
Title: Is there a version of the boolean satisfiability problem that has NC complexity?
Boolean satisfiability problem (SAT) is NP-complete by Cook–Levin theorem. (wiki)

Horn-satisfiability – given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the boolean satisfiability problem. It is also P-complete. P-complete problems lie outside NC and so cannot be effectively parallelized. (wiki)

Is there a version of the boolean satisfiability problem that has NC complexity?

# Answer
Allender, Bauland, Immerman, Schnoor and Vollmer showed in their paper The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem that every Boolean constraint satisfaction problem with a finite number of allowed constraints is either in $\mathsf{coNLOGTIME}$ or it is complete for one of the following classes: $\mathsf{NP}, \mathsf{P}, \mathsf{\oplus L}, \mathsf{NL}, \mathsf{L}$ (with respect to $\mathsf{AC^0}$ reductions).
> 2 votes

---
Tags: complexity-theory, time-complexity, satisfiability
---


# Question
Title: Generating a recursive descent parser for grammar having Kleene star
From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar:

\begin{align} &E \to E+T \mid T \\ &T \to T\cdot F \mid F \\ &F \to F^\* \mid a \mid b \end{align}

I actually changed this to:

\begin{align} &E \to TE' \\ &T \to +TE' \mid \epsilon \\ &T \to F\cdot T' \\ &T \to \cdot FT' \mid \epsilon \\ &F \to aF' \mid bF' \\ &F' \to ^\*F' \mid \epsilon \end{align}

This is done using the left-recursion elimination formula.

But then I have a doubt about whether it is correct or not, because the last $F$ transition cannot now generate $abb$, which it was able to generate. And if it is still able to do that, I would love to know, how?

Another transition that I tried for $F$ was:

\begin{align} &F \to G^\* \mid G \\ &G \to a \mid b \end{align}

This was done to remove the left recursion without using any formula.

But then I realized that it made the last transition nondeterministic.

Then I tried changing it by using the left-recursion elimination formula on $F \to G^\* \mid G$, making it:

\begin{align} &F \to GF' \\ &F' \to ^\*F' \mid \epsilon \\ &G \to a \mid b \end{align}

And now I am all confused!

# Answer
I don't know that there is a "standard" way to do left recursion elimination from Kleene star. But this is one obvious translation:

$$\begin{eqnarray\*}F & \rightarrow & F^\*\\,|\\, a \\,| \\,b \\ & & \Downarrow \\ F & \rightarrow & a F\\,|\\,b F\\,|\\,\epsilon\end{eqnarray\*}$$
> 1 votes

# Answer
```
here is code:
F -> W F | ϵ
W -> a|b|F

```
> 0 votes

---
Tags: context-free, formal-grammars, compilers, parsers, left-recursion
---