title: IP Fragmentation

text:
# Question
Title: IP Fragmentation
I have an IPv4 packet, 3523 byte of information Data a MTU (maximum transmission unit) of 516 (496 byte + 20 byte IP header), also an TCP header with 20 byte.

How does this result is created from the above information? I always come out at 51 byte Information data for the last package.

3523-(496\*7) = 51

Maybe someone can shed some light on this.

# Answer
> 3 votes
The IP packet has to include the TCP headers in its payload.

Hence we find additional 20 bytes, beyond the 3523 bytes of the sent data (the TCP payload). The total 3543 byes then get fragmented as usual.

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Alternative way of proving a language is $NP$
I would like to show a language $A$ is in $NP$.

I can find a TM for $A$, but I wanted to try a different approach and see if it is correct.

Let $B$ be a known problem in $NP$. If I show a polynomial time reduction $A \leq B$, will this imply $A\in NP$?

I believe it will, but I am not 100% sure.

# Answer
It depends on exactly what kind of reduction you're using. Assuming that you mean a polynomial-time many-one reduction (also called "mapping reductions") then, yes, if $A$ reduces to $B$ and $B\in\mathrm{NP}$, then $A\in\mathrm{NP}$, also. This was probably proven to you when you started to study reductions between $\mathrm{NP}$ problems.

If you mean polynomial-time Turing reduction, it's an open problem whether $A\in\mathrm{NP}$. This corresponds to the question of whether $\mathrm{NP} = \mathrm{P^{NP}}$.

If you don't know what kind of reduction you mean, you should check with your teacher, but it's probably many-one reductions. Those are the ones that are most commonly used with respect to problems in $\mathrm{NP}$.
> 2 votes

---
Tags: reductions, np
---


# Question
Title: How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?
The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d\_{ij}^{(k)}$ and $d\_{ij}^{(k-1)}$ in each time.

But in this case, we can't track actual shortest path with knowledge only two $d$ tables. It requires whole table.

There is a nice solution: Johnson's algorithm reduce both time and space complexity. (Especailly space complexity is $O(V^2)$) .

But I want to know can we apply simliar trick to Floyd-Warshall algorithm as Divide and Conquer trick in Sequence Alignment problem.

The crux part of Divide and Conquer trick in Sequence Alignment is 'we can reverse recursive relation into center'.

But in recursive relation in Floyd-Warshall algorithm, its recursive relation seems to be it has no such property.

Is there any other technique to apply such reducing space complexity that can track actual shortest path?

Edit: Also I want to retain time complexity $O(V^{(3+\epsilon)})$.

# Answer
> 2 votes
For each $i,j$ keep track of the last $k$ for which the value $d\_{ij}^{(k)}$ was changed. That must be the highest value on the shortest path from $i$ to $j$. The actual path can be retrieved recursively.

Added. A simpler solution. Keep track of array $n\_{ij}$ of vertices, giving the *next* vertex on the shortest path from $i$ to $j$. Whenever $d\_{ij}^{(k)}$ changes, $n\_{ij}$ is set to $n\_{ik}$.

# Answer
> 0 votes
```
Function FloydWarshall(G = (V, E))
  set d[s][t] := infty for all s, t in V
  set parent[s][t] := null for all s, t in V
  foreach vertex u in V do
    d[u][u] := 0
  foreach edge e = (u, v) in E do
    d[u][v] := c(e)
    parent[u][v] := u
  for k := 1 to n do
    foreach vertex s in V do
      foreach vertex t in V do
        if d[s][k] + d[k][t] < d[s][t] then
          d[s][t] := d[s][k] + d[k][t]
          parent[s][t] := parent[k][t]
  return (d, parent)

```

Time complexity: $O\left(n^3\right)$
Space complexity: $O\left(n^2\right)$

---
Tags: algorithms, shortest-path, efficiency, space-analysis
---


# Question
Title: Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?
As the title states. Let's say we have a set of inputs that define a tree structure. Is it possible to construct an automaton that can perform depth-first search on this data that is not Turing-complete? If so, can we state that the ability to do DFS a sufficient proof of Turing-completeness?

For the purpose of the question, you can have some leeway about how the data is represented. As long as you can come up with a combination of a tree representation and an automaton that can DFS it that is less than Turing-complete, that's good enough. If it simplifies anything, you can make assumptions about the nature of the tree (e.g. binary or not), but a more generalizable answer would be preferred.

# Answer
> 1 votes
Most functions you'll ever deal with in practice are *primitive recursive*, a model of computation that is properly less powerful than TMs.

More specifically, the problem from the question can be implemented on *linear-bounded automata* (LBA), a model of computation that is equivalent with context-sensitive grammars -- properly less powerful than TMs.

# Answer
> 0 votes
No, the ability to do DFS does not imply Turing-completeness.

Fix some encoding of trees as strings. Consider a Turing machine $M$ that has the following properties:

* if its input doesn't code the pair of a string $x$ and a tree $T$, $M$ rejects;
* on input $x,T$, $M$ performs DFS on $T$; it accepts if it finds $x$ in the tree and rejects, otherwise.

Now, consider the singleton set $\\{M\\}$. This is a model of computation (i.e., a set of objects and a description of what functions those objects compute) which can perform DFS but it can't do anything else, so it's not Turing-complete.

# Answer
> 0 votes
You are asking two different questions:

1)Is the ability to do depth first search a proof of Turing Completeness?

2)Can we write a non-TC automaton that does DFS?

*As for the first question*, **I don't think that ability to do DFS somehow relates to a power of computation**. DFS is just an algorithm, while Turing machine is a model of computation. In other word algorithm is different concept from the model of computation. Algorithm is a set of instructions, while a computation model is a means to run/implement this algorithm on. For example, you can consider finite automata, or push down automata which are less powerful than Turing machines and so are not Turing-complete.

*As for the second question*. I am not sure but I think it is impossible to do DFS on a model which is not as powerful as Turing machines.

---
Tags: search-algorithms, computation-models, turing-completeness
---


# Question
Title: Estimating probability from generative model
Assume that we have access to a generative model $G$, that takes as input a state-action pair $(s,a)$ and outputs a sample consisting of a successor state-observation pair $(s',o)$, that is, $(s',o)\sim G(s,a)$.

It can be assumed that the states, actions, and observations all take on a finite number of values (can be positive integers).

Is it possible to use the generative model to estimate the probability $P(o|s,s',a)$?

---

**My thoughts**:

Fix $s\_0,a\_0,s\_0'$.

> 1. Generate $(s',o)\sim G(s\_0,a\_0)$
> 2. If $s'=s\_0'$, add a particle to bin $b(o)$
> 3. Return to step 1

Continue the above three steps for $M$ runs so that we have $M$ particles in different bins (each bin corresponding to an observation we have seen so far). Now how do we convert the set of particles to probabilities?

# Answer
> 1 votes
Think of this as estimating a probability of some outcome, based on observations of many trials. Suppose we flip a coin 1000 times, and it comes up heads 327 times. What is your best estimate for the probability that the next flip will come up heads? $0.327$, right? You get that by dividing the number of heads by the number of trials.

What if you rolled a six-sized die 1000 times, and it came up a "one" 327 times? What is your best estimate for the probability that it comes up "one"? The same thing -- $0.327$, right?

It's the same here. Each time that you generate $(s',o)$ and find that $s'=s'\_0$, think of that as a trial -- the outcome of the trial is the observed value of $o$. (Ignore all iterations where $s' \ne s'\_0$; they're not even a trial.) So, if you have a particular bin, say the bin corresponding to $o=1$, then you count the number of trials where you observed that $o$ was $1$, and divide by the total number of trials. That's your estimate for the desired probability.

---
Tags: probability-theory
---


# Question
Title: Maximize entrywise 1-norm of matrix product
I have $8$ sets $E\_1, \ldots, E\_8$, each one of size $256$, whose elements are $4\times 4$ matrices of (nonnegative) integers. I'd like to design an algorithm to find:

$$\underset{M\_1 \in E\_1, \ldots, M\_8 \in E\_8}{\max} ||M\_1 \times \ldots \times M\_8||\_1$$

where:

$$||M||\_1=\sum\_{i=1}^4\sum\_{j=1}^4 M\_{i,j}$$

A reasonable time complexity might be approximately $2^{32}$ (time complexity of the naive algorithm is $2^{79}$).

My first idea would be to look for interpretations in various mathematic fields:

* geometry: matrix product in an euclidian space.
* probability: it reminds me of Markov chains (but the $M\_i$ are not normalized).

Is there any known work about this?

# Answer
Here's one approach, where we prune the set of candidates we examine based on the best combination seen so far. I don't know how well it will work; you'll probably have to implement and try it to find out.

Suppose we have two sets $S\_1,S\_2$ of matrices, and we want to find $M\_1 \in S\_1, M\_2 \in S\_2$ that maximizes $\\|M\_1 \times M\_2\\|\_1$. Here's a plausible approach. First, sort the matrices in each set by decreasing value of $\\|\cdot\\|\_1$ norm. At each stage, we'll keep track of the largest value of $\\|M\_1 \times M\_2\\|\_1$; let $\ell$ denote that largest-seen-so-far value. We'll exploit the inequality

$$\\|M\_1 \times M\_2\\|\_1 \le \\|M\_1\\|\_1 \times \\|M\_2\\|\_1$$

to prune the set of combinations we need to test. In particular, we'll enumerate matrices $M\_1 \in S\_1$ in order of decreasing $\\|\cdot\\|\_1$ value. For a fixed $M\_1$, only need to examine matrices $M\_2 \in S\_2$ such that $\\|M\_2\\|\_1 \> \ell/\\|M\_1\\|\_1$ (thanks to the above inequality, there's no point in examining the other candidates for $M\_2$). For each candidate pair, we'll compute the value of $\\|M\_1 \times M\_2\\|\_1$ and update $\ell$ if it is larger than any seen so far.

In this way, we obtain the following algorithm:

* Set $\ell := -\infty$.
* For each $M\_1 \in S\_1$, in decreasing order of $\\|\cdot\\|\_1$ norm:

+ For each $M\_2 \in S\_2$, in decreasing order of $\\|\cdot\\|\_1$ norm:

    - If $\\|M\_2\\|\_1 \le \ell/\\|M\_1\\|\_1$, break out of the inner loop and go on to the next iteration of the outer loop.
        - Otherwise, if $\\|M\_1 \times M\_2\\|\_1 \> \ell$, set $\ell := \\|M\_1 \times M\_2\\|\_1$.

What's the running time of this approach, if $S\_1$ and $S\_2$ are each of size $n$? I don't know. At worst, it is $O(n^2)$, but one could hope that it might be significantly better -- if we're very lucky, it'll be more likely $O(n \log n)$ (to sort the two sets).

How do we apply this to your problem? Naively, we can set

$$\begin{align\*} S\_1 &= \\{M\_1 \times M\_2 \times M\_3 \times M\_4 : M\_i \in E\_i\\}\\ S\_2 &= \\{M\_5\times M\_6 \times M\_7 \times M\_8 : M\_i \in E\_i\\} \end{align\*}$$

and then apply the above algorithm. Here $|S\_1|=|S\_2|=2^{32}$, so if we're very lucky, this might be efficient enough to apply to your situation.

With a bit more sophistication and implementation complexity, you might be able to apply this recursively. The above procedure gives a way to enumerate products $M\_1 \times M\_2$ in decreasing order of $\\|M\_1 \times M\_2\\|\_1$, given a set of candidates for $M\_1,M\_2$. So, you could apply that to $E\_1 \times E\_2$ and $E\_3 \times E\_4$ to find $S-1 = E\_1 \times E\_2 \times E\_3 \times E\_4$, etc. You could also use some kind of iterative deepening, to only enumerate combinations such that the norm of their product exceeds some lower bound, and gradually decrease the lower bound as needed.
> 1 votes

---
Tags: algorithms, markov-chains
---


# Question
Title: Find all intervals that are contained in a query interval
Given a set of intervals $S = I\_1, ..., I\_n$, what is the fastest way to find all intervals of $S$ that are completely contained in an interval $I\_\text{query}$? It should also support incremental (dynamic) insertion of new intervals to $S$.

Interval trees are not suitable for this, since they are designed to query overlapping intervals. Similarly, segment trees are designed to query all intervals that contain a query point.

A solution would be to use an interval tree to find overlapping intervals, then use linear search and eliminate those from the results that are outside of the specified query interval.

Is there any better/faster solution for this?

# Answer
You were too quick to reject interval trees and segment trees. You can search an segment tree for all intervals that are contained in a query interval $q=\[\ell\_q,u\_q\]$, using a straightforward recursive procedure:

Any node $v$ of a segment tree has a corresponding interval $\text{Int}(v)$. Do a recursive search of the tree, except that you only visit nodes $v$ such that $\text{Int}(v)$ overlaps $q$. Each such node stores a list of intervals from $S$. For each such node, if $\text{Int}(v)$ is contained in $q$, check all of the intervals stored with $v$ is contained in $q$.

That's all you need to do. Just because a data structure is designed to support one kind of operation doesn't mean it's unable to support other operations, too.

That said, one challenge with segment trees is that it's not clear how to update them dynamically (to add new intervals).

---

I think similar ideas can also be applied to interval trees, too. The root of an interval tree has a value $x$. Now do a case analysis:

* If $x$ is to the left of $q$ (i.e., $x \< \ell\_q$), then you only need to look at intervals that are completely to the right of $x$, so you just recurse to the right child of the root.
* If $x$ is to the right of $q$ (i.e., $x \> u\_q$), then you only need to look at intervals that are completely to the left of $x$, so you just recurse to the left child of the root.
* If $x \in q$ (i.e., $\ell\_q \le x \le u\_q$), then you recurse to the left child and output all matches found there; recurse to the right child and output all matches found there; and finally, find all intervals that contain $x$ and are contained in $q$. The latter can be done by scanning the list of intervals associated with the root (which is a list of intervals that contain $x$), to see which meet your condition.

---

I suspect there might be other approaches as well. For instance, you could build a $k$-d tree, with $k=2$ dimensions, where the interval $\[\ell,u\]$ is represented as the point $(\ell,u)$. Then given a query interval $q=\[\ell\_q,u\_q\]$, you want to do a range search to find all points $(x,y)$ such that $x \ge \ell\_q$ and $y \le u\_q$. That should be a straightforward recursive search in a $k$-d tree. Or, you could build a quadtree.
> 2 votes

---
Tags: data-structures, trees, search-algorithms, search-problem, intervals
---


# Question
Title: Return destinations for an expression-oriented programming language
I am designing a programming language and I want to give everything the ability to return a value. For example, if I use a block as a right-hand side value, I can assign it to a lvalue:

```
sum := {
    if (a < 0) { a := -a; }
    if (b < 0) { b := -b; }
    return a + b;
};

```

Also, if and while statements could return a value, and there is no need for something like a ternary operator then.

After a bit of research, I have found that Rust is capable of doing this. And this is great for language design, because it significantly reduces the number of language constructs needed. You don't really need a do-while loop, as that's just a while loop with a braced condition:

```
do {
    foo();
} while (a > 0);

```

Is equivalent to:

```
while {
    foo();
    return a > 0;
}{}

```

Also, with ignored variable bindings, you can create continue and break statements for loops:

```
// Break
_ := while (a > 0) {
    if (a == 5) {
        return ();  // Empty tuple
    }
    a += 1;
};
// Continue
while (a > 0) { _ := {
    if (a == 5) {
        return ();  // Empty tuple
    }
    a += 1;
};}

```

I like the idea of having less language constructs, because the language is expressive enough to do this without labeling and goto statements.

But as I was thinking about this, two things popped into my head:

1. Are these just very abstract lambda expressions?
2. How could the 'return destination' be labeled so we can return from a very nested expression even right out to the function? I think I would probably need some extra notation for that.

# Answer
1) In a sense, yes. Guy Steele wrote the "Lambda papers", where he reduced many different constructs to lambda expressions, in a compositional way. He used the lambda abstractions of Scheme for this, but the construction is general.

2) You should read about continuation passing style. Scheme, for instance, uses "call with current continuation" `call/cc` to achieve what you describe: "returning" from a deeply nested location.

`call/cc` is probably not the most convenient notation, but it works, and can be used with any expression. E.g.

```
(call/cc (lambda (k)
  (+ 1 (if (some-condition) 10 (k 2)))

```

Above, if the condition is true, the `if` evaluates to 10, which is added to 1, so that the whole result is 11. If it is false, `(k 2)` is evaluated, "returning" to the point `call/cc` was used with result `2`. Note that this skips the `(+ 1 ..)` part. You can nest `call/cc` arbitrarily, providing many "return points" as wanted.
> 4 votes

---
Tags: programming-languages, language-design
---


# Question
Title: I do not know if my algorithm complexity is $P$, $NP$ or $NP-hard$?
I developed an algorithm but just not sure what is the complexity of the algorithm. I provide a brief description of it below:

"For $N$ user case, there are $B(N)$ Decision Variables. $B(N)$ is Bell Number, for those of you who are not familiar with Bell Numbers please be noted that $B(N)$ grows exponentially with $N$. In every turn, I have to choose the minimum Decision Variable among all of the Decision Variables and do a certain action accordingly."

I know that sorting problem is considered a Polynomial $(P)$ problem. But I am confused if my algorithm is considered $P$ or $NP$ or $NP-hard$ since the number of decision variables that are being sorted grows exponentially with $N$.

# Answer
Your question is somewhat malformed because **P** and **NP** are classes of problems, not algorithms. For example, as you state, the *problem* of sorting is in **P**. However, that doesn't mean that *every* sorting algorithm runs in polynomial time. For example, the well-known joke algorithm bogosort sorts lists by trying every possible permutation until it finds one that is sorted. It has running time approximately $n!$, which is far from polynomial. If a problem has polynomial time complexity, that means that there exists an algorithm that solves it in polynomial time, but it doesn't mean that all algorithms for the problem are that efficient.

It's not possible to say what the complexity of your problem is, or what the running time of your algorithm is, because you haven't given a precise description of either. The fact that it involves choosing a "best" set from some exponentially large set doesn't necessarily mean the problem has to have exponential time complexity: there could be a smart way of picking the best set without considering all the options. For example, there are polynomial-time algorithms for finding the shortest path between two points in a graph, even though there may be exponentially many paths.
> 3 votes

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


# Question
Title: Find X contiguous segments in a range of integers
I've been struggling with the following problem: how do I find all possible sub-ranges in a range of integers where each segment is at least length 1, and I specify the total number of segments? A couple examples:

```
segments=2, range=(0,5)
> [0,1],[2,5]
> [0,2],[3,5]
> [0,3],[4,5]

segments=3, range=(0,8)
> [0,1],[2,3],[4,8]
> [0,1],[2,4],[5,8]
> [0,1],[2,5],[6,8]
> [0,1],[2,6],[7,8]
> [0,2],[3,4],[5,8]
> [0,2],[3,5],[6,8]
> [0,2],[3,6],[7,8]
> [0,3],[4,5],[6,8]
> [0,3],[4,6],[7,8]
> [0,4],[5,6],[7,8]

```

This feels like a recursion problem because I need to iterate over a varible number of for-loops, but I don't see how to make it work.

# Answer
> 1 votes
Here's a quick piece of pseudo-code off the top of my head.

Given maximum value **m** and number of non-empty segments **n**, do so:

> Call Helper(Empty List \[passed by reference\], Empty List \[copied before passing or passed by copy\], 0, m, n)

The helper function takes as input:

1. a reference to the output list of lists,
2. a list of segments to append more segments to
3. the lower bound or starting value
4. the upper bound or stopping value
5. the number of segments

```
function Helper(L, S, l, u, n):
  If n = 1 then append to L the list S.append(l, u)
  Else:
    For each t from l+1 up to u-n *inclusive*:
      Make a copy of S into S'
      Append to S' the pair (s, t)
      Call Helper(L, S', t+1, u, n-1)

```

As you can see, the only "trick" was perhaps just figuring that out you should use a helper function with more arguments to aid the recursion. Of course, different solutions may be possible.

A note here. It should be possible to change the implementation above slightly (e.g., using return values as opposed to passing L by reference) that one can memoize the result of each call for a given triple (l, u, n). Such a DP approach seems to me like it may make the program be significantly faster on large input. I assume this sort of problem has much sharing to be exploited using a DP approach.

# Answer
> 0 votes
Hint 1. Splitting a range into $k$ segments is the same as selecting the $k-1$ break-points between segments.

Hint 2. As you proceed through the list of elements, the next element is either part of the current segment or part of the next one.

---
Tags: algorithms, recursion
---


# Question
Title: Multiple Knapsack using Dynamic Programming
**Def MKP (Multiple Knapsack Problem):** Given a set of n items and a set of m bags (m \<= n), with

* pj: profit of item j
* wj: weight of item j
* ci: capacity of bag i

select m disjoint subsets of items so that the total profit of the selected items is a maximum, and each subset can be assigned to a different bag whose capacity is no less than the total weight of items in the subset.

---

I'm wondering if there is a reasonable way of solving MKP using DP. I get the point in 0-1 Knapsack Problem. The recurrence is quite straightforward, add item/ not add item.

`dp[item][capacity] = max{
 value[item] + dp[item - 1][capacity - weight[item]],
 dp[item - 1][capacity]}`

However, I cannot see how to get an recurrence equation for the MKP. Should I extend the recurrence equation to "add item bag 1/ not add item bag 1/ add item bag 2/ not add item bag 2" and so on and so forth? It does not seem a good approach as the number of bags becomes larger and larger.

# Answer
When all values are 1 and all capacities the same, this is the bin-packing problem, which is *Strongly* NP-Complete. Therefore, a sensible DP solution is probably not possible unless P=NP.

For very small m, say m=3, you can do:

`dp[item][capacity1][capacity2][capacity3] = max{
 value[item] + dp[item - 1][capacity1 - weight[item]][capacity2][capacity3],
 value[item] + dp[item - 1][capacity1][capacity2 - weight[item]][capacity3],
 value[item] + dp[item - 1][capacity1][capacity2][capacity3 - weight[item]],
 dp[item - 1][capacity1][capacity2][capacity3]}`
> 3 votes

---
Tags: np-complete, dynamic-programming, np-hard, knapsack-problems
---


# Question
Title: Does NP mean verifiable in polynomial time or solvable in polynomial time?
Is NP defined as *verifiable* in polynomial time, or *solvable* in polynomial time? Verifiable meaning that the solution can be checked in polynomial time, and solvable meaning that the solution can be found in polynomial time?

# Answer
> 1 votes
NP is a class of problems whose solution is **verifiable** in polynomial time on a *deterministic* Turing machine. Alternatively, NP is a class of problems whose solution is **solvable** in polynomial time on a *nondeterministic* Turing machine.

Please look here.

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


# Question
Title: Could a quantum computer perform linear algebra faster than a classical computer?
Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has anyone created a quantum algorithm for linear algebra, and what is it's running time? In theory, an operation such as matrix-matrix multiplication is highly parallelizable, however in practice it requires a lot of work to implement parallel matrix-matrix multiplication that runs quickly. Would a quantum computer provide any practical advantage?

# Answer
> 3 votes
Here are some pointers:

# Answer
> 1 votes
**Mathematical model with matrix**

The HHL algorithm can be found in the already mentioned links, let's implement it on a quantum computer. We want to solve a system of linear equations $ A|x\> = |b\>$ From this $ |x\> = A^{-1} |b\> $

With matrix $ A = \begin{bmatrix} 1.5 & 0.5 \\ 0.5 & 1.5 \end{bmatrix} $ and input $ b = \begin{bmatrix} 1 \\ 0 \end{bmatrix} $

$ A^{-1} . |b\> = \begin{bmatrix} 0.75 \\ -0.25 \end{bmatrix} $

**Quantum circuit design**

We use the quantumcircuit in arXiv 1302.1210 with 2 qubits,one qubit with input b. The second qubit is a ancilla bit and a one on the output means output is ready.  The circuit uses a PEA circuit (gate R) as input and an inverse PEA circuit at the output. Phase estimation or PEA is used to decompose the quantum state of |b\> in a particular basis and the eigenvalues of A are stored in an eigenvalue register. Rotation gate R(y) transforms with an angle depending on the value in the eigenvalue register. Then we run a PEA in reverse to uncompute the eigenvalue and find the answer. In the quantumcomputer, only the possibility of finding a 1 or 0 can be measured.

**Gate parameters**

R is the matrix of eigenvectors of matrix A and Rdagger is it's transpose. From the Matrix A we find the eigenvalues $ \lambda\_{1} = 1 \\; \lambda\_{2} = 2 $ The rotation angle of the Y rotation gate is determinded by the ratio of eigenvalues. Rotation angle $ \theta = -2arccos \dfrac{\lambda\_{1}}{\lambda\_{2}} \\\$

$ \theta = -2arccos(1/2)= -2\dfrac{\pi}{3} $. Implement this circuit in the IBM quantumcomputer with the link to the circuit:

quantumexperience.ng.bluemix.net/qx/editor?codeId=9da9d545772273118671911e1078ac42

---
Tags: time-complexity, quantum-computing, linear-algebra
---


# Question
Title: Can literals in functional languages be thought of as functions from the empty type?
A while ago, I think on Stack Overflow, I saw someone say that Haskell literals can be thought of as functions that don't operate on anything. This makes sense to me but I remember someone else vehemently disagreeing with him.

If I understand correctly, all values in primitive types, or at least those in `Bool`, are type constructors, and type constructors are a special kind of function into the type. Since values like `2.87`, `True`, or `'f'` don't have any parameters passed to them it seems like it wouldn't effect the semantics of the language whether you think of them just as elements of their type or a functions from a type containing nothing into their type that always returns their value. Is there anything wrong with thinking of literals in this way?

# Answer
Let's start in a total language like Agda. Then, as gallais states, this only makes sense if by "empty type" you mean the unit type, i.e. the 0-ary tuple, which has exactly one value. The empty type can be thought of as a 0-case sum type, and has no values at all. In Agda, you can easily prove that `Unit -> A` is isomorphic to `A`. In that sense, you can consider them the same, though they still aren't literally the same. I can't, for example, do a case analysis on a `Unit -> Bool` nor can I apply `True : Bool` to anything as a function.

The story for Haskell is quite different. `() -> A` and `A` are semantically non-isomorphic types. In particular, `() -> ()` has four values, while `()` has only 2. The four *observationally distinct* values are `undefined`, `\_ -> undefined`, `\x -> x`, `\_ -> ()`. So `()` isn't actually a unit type, in the sense that there is exactly one function into `()`. (In Agda, on the other hand, we can prove that if `x : Unit` and `y : Unit`, then they are equal \[definitionally so if we define `Unit` with the `record` syntax as opposed to the `data` syntax\]. That means, `Unit` has only one value. Further, we can prove that `Unit` and `A -> Unit` are isomorphic for any `A`.)

In fact, an "empty" type like `Void` defined as `data Void` is closer to being a unit type in this sense. `Void` has only one value, but `Void -> Void` still has two. In fact, *every* function type `A -> B`, has at least two observationally distinct values, namely `undefined` and `\_ -> undefined`. Therefore, Haskell has no true unit or void type.

A lot of this is due to Haskell being a non-strict language and is exasperated by the existence of `seq` (and its equivalents). For example, the distinction between `undefined` and `\_ -> undefined` can only be seen with `seq`. If we eliminated `seq` and its equivalents from Haskell, then `Void` would serve as a unit type, though, ironically, still not as an empty type.

Usually, when people talk about such things in Haskell, they are tacitly pretending that Haskell is a better behaved language than it is. That is, they are assuming bottoms don't exist for their purposes, i.e. that you're working in a total language like Agda. For the purposes of designing your code, this is usually adequate; it's not common that we care about or expect bottoms. These distinctions can become important if we're doing something like circular programming, or if safety guarantees of our program rely on these properties, e.g. a function can never be called if it has an empty type as its domain.
> 10 votes

---
Tags: type-theory, functional-programming
---


# Question
Title: How to develop an $O(N)$ algorithm solve the 2-sum problem?
Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\\{-3,-2,0,2,3,4\\}$, the number of pairs sum to zero is $2$.

Let $N$ be the number of elements in the input array. If I use binary search to find the additive inverse for an element in the array, the order is $O(\log N)$. If I traverse all the elements in the set, then the order is $O(N\log N)$.

> How to find an algorithm which is of order $O(N)$?

# Answer
> 13 votes
Let $A$ be the sorted input array. Keep two pointers $l$ and $r$ that go through the elements in $A$. The pointer $l$ will go through the "left part" of $A$, that is the negative integers. The pointer $r$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $0 \notin A$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $A$.

```
COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l])
     --left;
   else
     ++right;

```

It is obvious the algorithm takes $O(N)$ time.

# Answer
> -1 votes
The simplest approach, by my understanding, seems to be to use a Hash-Table, H = {a\[0\] = true, .. , a\[n-1\] = true}. This Hash-Table can be built in O(n) time. Once the Hash-Table is built, iterate through A\[0,..,n-1\] and check if H\[-1\*a\[i\]\] exists. If it does, increment a counter by 1, and return the final result. This is clearly O(n).

# Answer
> -1 votes
Note that we can lookup a value in a Python set in constant time.

```
def twoSum(data):
    count = 0
    nums = set()
    for num in data:
        if (num * -1) in nums:
            count += 1
        nums.add(num)
    return count

```

---
Tags: algorithms
---


# Question
Title: What is the practical purpose of an epsilon NFA?
If for every $\epsilon$-NFA their exists an equivalent NFA what is the purpose of ever using an $\epsilon$-NFA? I am having trouble understanding what the practical purpose of using one would be.

# Answer
Purely convenience. It's like, in a programming language, why have `for` loops, if every `for` loop could alternatively be written as a `while` loop? Convenience. It's sometimes convenient to be able to use epsilon-transitions, when defining NFAs. For instance, when converting a regexp to a NFA, the construction is arguably a bit simpler (easier to understand) if you allow yourself to use epsilon-transitions.
> 4 votes

# Answer
Given a regular expression constructing an equivalent NFA with epsilon is easier than constructing equivalent DFA. Also given two DFAs you can easily construct NFAs with epsilon moves accept concatenation, intersection, union, and Kleene closure of the languages. Look here for example.
> 2 votes

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


# Question
Title: Cook-Levin theorem proof's requirement of $\phi_{cell}$
I'm trying to understand the Cook-Levin theorem proof, as it attempts to create a polynomial-time reduction from any `NP` problem to `SAT` (as presented in the book by Michael Sipser).

Most requirements are absolutely clear, but I don't understand why the $\phi\_{cell}$ formula is required.

Of course, a tableau with improper values, such that fails $\phi\_{cell}$, is broken and therefore will not "translate" correctly to the original NP problem on the other side of the reduction. We can easily "break" a tablaue by putting a $q\_{accept}$ somewhere where it shouldn't, and the machine's language will change.

But I seem to miss something basic. A reduction says that if A reduces to B, then for each $w\in\Sigma^\* $, $w\in A$ iff $f(w)\in B$.

The $f(w)$ part may be the "broken" tableau, but can we really call it $f(w)$? After all, such broken tableaus are never in the image of $f$.

So, why do we care about them?

# Answer
We are building a reduction from problem Q (some problem in NP) to SAT. To do that, we construct a function $f$ that maps an instance of Q to an instance of SAT. In other words, if $w$ is an instance of Q, then $f(w)$ is a formula in CNF form. (Recall that SAT is a decision problem whose instances are CNF formulas.) Let's call that formula $\varphi$. We'll remember that $\varphi$ depends on $w$.

What is the formula $\varphi$? A formula is something that takes any assignment $x$ and assigns a truth value to it, namely $\varphi(x)$. The way the reduction works, we interpret $x$ as a tableau, and $\varphi$ is defined so that $\varphi(x)$ will be true if $x$ is a valid tableau for the input $w$ (a valid computation of a non-deterministic Turing machine for problem $Q$ when run on input $w$).

So, $f(w)$ is not the tableau itself. $f(w)$ is a formula that accepts valid tableaus.

Then, once we have defined $f$ (i.e., $\varphi$), we prove the following property: $\varphi$ will have a satisfying assignment if and only if $w$ is a yes-instance for problem Q.

For this to work out, the formula needs to include terms that ensure that any satisfying assignment to $\varphi$ is a valid tableau. If you left that part out, you wouldn't be able to prove the property mentioned above, so $f$ wouldn't be a correct reduction.
> 2 votes

# Answer
> ...but I don't understand why the $\phi\_{cell}$ formula is required.

The tableau for $N$ in the Sipser's proof represents a single branch of the computation of $N$. The formula $\phi\_{cell} \wedge \phi\_{start} \wedge \phi\_{move} \wedge \phi\_{accept}$ in fact kind of seeks for a branch that leads to an accept state. It is true (there is a true-assignment of the variables of this formula) if and only if there is a computation branch that accepts the input.

The proof introduces one variable $x\_{i,j,s}$ for each tape cell $cell\[i,j\]$ so that $x\_{i,j,s}$ is *true* if and only if $cell\[i,j\] = s$, that is, $cell\[i,j\]$ contains the symbol $s$.

Now, the idea behind using $\phi\_{cell}$ is to require each cell during computation contain only and only a single symbol (you cannot write two different symbols on a cell at the same time), and contain at least one symbol of the alphabet.

But I don't understand what you exactly confused about the reduction. The proof is about how an arbitrary $NP$ decision problem $A$ can be converted to the corresponding $SAT$ problem by generating a formula $\phi\_{cell} \wedge \phi\_{start} \wedge \phi\_{move} \wedge \phi\_{accept}$ which is satisfied if only if $A$ has output $yes$.
> 2 votes

---
Tags: complexity-theory, formal-languages
---


# Question
Title: I'm looking for a construct that is to semantic-analysis what NFA/DFA are to scanning and DPDA is to parsing
What maps to Semantic Analysis the way automata like *Finite State Machines* and *Pushdown automatons* map to Lexing and Parsing?

A couple of years ago I came across a paper that presented such a construct; I don't remember much about the paper to be useful, but here's what I **think** I remember:

1. I think the paper was from the late 80s or early 90s,
2. The construct had/employed a double-ended queue,
3. Elements were replaced in the queue until the replacement rules could no longer be applied \[and replacements were longer sequences than what they replaced\],
4. The paper mentioned that while it mapped to the Semantic Analysis, it was somewhat unwieldy to use.

Any help locating this paper would be most welcome, as would info on other constructs mapping to Semantic Analysis.

Thank you.

# Answer
Repeated substring string replacement is Turing complete.

To emulate a Turing machine you can use the following:

The current string encodes the tape with a new symbol $\\$$ followed by an encoding of the current state inserted before the position where the current head is. The allowed replacements can be encoded by taking each transition $\delta(n, b) = (m, c, N|L|R)$ by creating the replacement rules to replace $a\\$nb$ with $a\\$mc$ $\\$mac$ or $ac\\$m$ for not moving the head or moving it left or right where a is every symbol in the alphabet.
> 1 votes

---
Tags: automata, compilers, semantics, research
---


# Question
Title: Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $
> Determine whether the following language is decidable, recognizable but not decidable, co-recognizable but not decidable or neither recognizable nor co-recognizable. Prove your answer. $$L=\left\\{ \left\langle M\right\rangle |M\text{ is a TM and }A\_{TM}\leq\mathcal{L}\left(M\right)\right\\} $$

\[Where $\mathcal{L}(M)$ is the set of words accepted by $M$ and $A\_{TM}\leq L$ if there is a mapping reduction from $A\_{TM}$ to $L$\]

So if I understand correctly the question is whether the set of all $\mathcal{RE}$-hard languages is recognizable/co-recognizable. It seems an easy corollary of Rice's theorem that it is not decidable, and my intuition tells me it is neither recognizable nor co-recognizable but I'm having issues contradicting any reductions.

My approach was, to show it is not recognizable, to assume it is and therefore there is a reduction $L\leq A\_{TM}$, where given a TM $M$ recognizing it we would run $M(\<M\>)$ where I hoped to get some diagonalization argument, but I failed.

Edit: I was able to show that $L\not\in co\mathcal{RE}$, using a reduction $A\_{TM,\varepsilon}\leq L$. Given an encoding of a Turing machine $\left\langle M\right\rangle$ define $f\left(\left\langle M\right\rangle \right)$ to be the Turing machine which on input $\left\langle M',w\right\rangle$ :

For $i$ from $1$ to $\infty$:

* Run $\left\langle M',w\right\rangle$ for $i$ steps.
* Run $\left\langle M,\varepsilon\right\rangle$ for $i$ steps.
* Accept if both accepted.

I wasn't able to modify this to show $L$ is not recognizable though, wanted to do a similar reduction using $\overline{A\_{TM,\varepsilon}}$, but I have issues either getting a recognizable language when $M$ doesn't halt, as the "common" method of running for $|w|$ steps only produces decidable languages.

# Answer
The reduction you suggest can be a bit simplified, by running the machines serially rather than "in parallel". That is, First check if $M$ accepts $\epsilon$, and if it does, run $M'$ on $w'$.

Your idea is to make sure that if $M$ accepts $\epsilon$, then the language of $f(\langle M\rangle)$ is $A\_{TM}$, and otherwise it's empty.

We can do a similar thing to show that the language is not in RE, but it requires a bit more subtlety:

We show that $A\_{\overline{TM,\epsilon}}\le\_m L$ as follows. Given $\langle M \rangle$, the reduction outputs a machine $f(\langle M \rangle)$, which on input $\langle M',w' \rangle$ works as follows:

1. Simulate the run of $M$ on $\epsilon$ for $|\langle M',w' \rangle|$ steps.
2. If $M$ does not accept $\epsilon$ during that simulation, simulate $M'$ on $w'$ and answer whatever it answers.
3. Otherwise, if $M$ accepts $\epsilon$ during that simulation, reject.

Now, the crux of the construction is in step 1, where we simulate for a finite number of steps, but this number depends on the input, so it can grow arbitrarily large.

What we get is that if $M$ does not accept $\epsilon$, then we'll always get to step 2, so $L(f(\langle M\rangle))=A\_{TM}$, and all is well.

However, if $M$ does accept $\epsilon$, then we get something a bit strange - for some small inputs, it may still be the case that we'll get to step 2. But for large enough inputs, we'll get to step 3. This means that $L(f(\langle M\rangle))$, so clearly there is no reduction from $A\_{TM}$ to it, and we're done.
> 1 votes

---
Tags: computability, reductions, decision-problem, semi-decidability
---


title: warm/neutral/cool tone of one image

text:
# Question
Title: warm/neutral/cool tone of one image
I wanna determine whether an image belongs to warm/neutral/cool tone. I find Kelvin color temperature to calculate the average temperature of an image over all piexls. But the result seems not good. Can anybody point in the right direction to determine the tone of one image?

# Answer
I would like to point that determining the color temperature of the image is still an open problem.

If you convert the RGB image to CIE XYZ Tristimulus color then calculate normalized chromacity to get the temperature, it works for pixel, kinda, it is a lot of effort to simply feed it a mean. Indeed it cannot work. The average over all pixels gives artificial color (if you do it over RGB it is not even chromacity preserving).

Whenever it is possible use CIE RGB (it is physical based color space, using the actual human sensitivity to colors) or some color space naturaly separating hue and lightness like HSL.

* perform image segmentation or alternatively perform edge detection and subtract edges from reduced image
* take from results only big enough blobs - this is arbitrary and depends on the image resolution, but more than 50 pixels is good default value. Blobs are segments of the image with small inner variance - they pixels are similar to each other, not varying too much in intensity and chromacity.
* Calculate the average of blobs in the HSL space. Take into account the area and assign greater weights to bigger blobs (if blob spans over 200px it will be better perceived than 4x50px).
* take into account the placement of the blob (calculate how far it is from the center)
the the center is weight 1, slightly decreases to suddenly drop. This weights reflect what is better exposed (assuming that there are no important features at the corners, but it is safe to assume that the main focal points are in the center).
* take this weighted areas (blobs) average them in HSL space and now calculate color temperature \- sorry for obvious link but the equations are ok. This method performs quite good experimentaly, some parameters should be adjusted per type of image, sorry I do not remember exact parameterts (proven to give good results experimentally).

Unfortunately your task must be heavily modified to reflect how people perceive images, how they neglect the color of edges (which give quite big boost RGB-wise). What they focus at and how they remember. By the way, the reception of the image tone is a bit skewed by the represented objects - the attraction makes the tone warmer while repulsion makes it colder.

So please take a look at awesome articles:
> 2 votes

---
Tags: image-processing, colorings
---


# Question
Title: Validity of list of articulation points in a graph after a node is deleted
Say I have a bidirectional graph `G` and I have the list of articulation points and bridges of this graph. Say, the list of articulation points is `ap[]` and the list of bridges are `bridges[]`. Now, if I remove a node which does not belong to the list of `ap[]`, meaning, this node is not an articulation point and deleting this node will not divide the nodes of this graph into different connected components. Now, do I have to update the list of the articulation points `ap[]`? I mean after deleting the node, is it possible that some more node(s) in the graph will become articulation points? The same question is for the list of bridges. If I remove an edge which is not a bridge in the graph, after deleting it, is it possible that some more existing edge(s) will become bridge?

# Answer
> 1 votes
Yes and yes. Look at this graph:

* $V=\\{1,2,3,4\\}$
* $E=\\{\\{1,2\\},\\{2,3\\},\\{3,4\\},\\{4,1\\}\\}$

There is neither articulation point nor bridge. But if you delete any node/edge...

---
Tags: graphs
---


# Question
Title: What is the difference between control flow graph & interprocedural control flow graph?
I am doing research on control flow analysis on aspect oriented programs and I found in some papers an interprocedural approach for doing control flow analysis on others call graph or control flow graph. Is there a real difference between control flow graphs and interprocedural control flow graphs?

# Answer
CFG (Control Flow Graph): representing control flow for a single procedure
IPCFG (Inter-Procedural Control Flow Graph): representing control flow for a program

source: http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf
> 3 votes

---
Tags: terminology, algorithm-analysis, programming-languages
---


title: Conflict Detection Algorithm

text:
# Question
Title: Conflict Detection Algorithm
I have been trying to come up with a better algorithm that detects conflicts in the scenarios below.

Let's say we have 4 dancers. We pair them up and find out which ones can dance together. So, we have the dancer # combination and whether they can dance together or not.

```
(1,2) True
(1,3) True
(1,4) False
(2,3) True
(2,4) False
(3,4) False

```

At the end of the day, I want to know which group of dancers I can group together.

A group can only be formed when all of the dancers within the group can dance with each other AND no dancer outside the group can dance with any dancer in the group.

For example, group A can be formed with dancers {1,2,3} because they call can dance with each other (i.e. (1,2), (2,3), and (1,3) are True) AND no dancer outside the group can dance with them (i.e. 4 is outside the group and (1,4),(2,4),(3,4) are all false).

Now, if we change:

```
(2,4) -> True

```

grouping changes quite a bit. I can no longer group 1,2 and 3 together because even though (1,2), (1,3) and (2,3) are all True, there is a dancer (#4) that can dance with 2 (i.e. (2,4) is True).

Now, can we group 1 and 3? No. Even though (1,3) is True, there would be one dancer outside the group that CAN dance with either 1 or 3 (i.e. (2,3) and (1,2) are True).

I came up with an algorithm that simply uses some non-sophisticated logic, but I was wondering if one can frame this problem in terms of a CS or Math problem, and whether something similar has been formally solved already.

If it helps you visualize this, you can draw rectangles or circles where they overlap if they can dance together.

# Answer
> 1 votes
Your dancers are vertices of a graph, and there is an edge between two dancers if they are compatible. A set of dancers is a component if there's what you might call a "chain of compatibility" between every pair of them: that is, every pair of dancers is either compatible or you can come up with a sequence such as "Alice is compatible with Bob, Bob is compatible with Charlotte and Charlotte is compatible with Daniel" to get between them. A group of dancers who are all compatible with each other are a clique.

What you're looking for is a component that is also a clique. These are easy to find because you can use a greedy strategy. Suppose we want to know if a particular dancer (say, Alice) is in one of these groups. We grow a set of dancers as follows. Initially, the set is just Alice. Then, we keep adding dancers to the set if they're compatible with anybody inside the set. When we can't add anyone, we've found the component. So now, we just need to check that the component is a clique: that is, everybody within the component is compatible with everybody else.

You can do this more efficiently by checking for being a clique as you add new dancers. Again, start with just Alice. Then define a set of newcomers to be all people who are compatible with somebody in the set we've built so far. If any of those people are incompatible with each other or with somebody who's already in the set, Alice isn't part of a group; otherwise, add all the newcomers to the set and select the next set of newcomers.

---
Tags: algorithms, search-algorithms, decision-problem
---


title: Reduction from Clique-6 to Clique-3

text:
# Question
Title: Reduction from Clique-6 to Clique-3
Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices.

Let us define the problem $Clique-k$ as follows: $$\\{ \langle G \rangle \mid G \text{ is an undirected graph that contains a clique of size } k\\}$$

---

**Question:** Find a reduction $f$ from $Clique-6$ to $Clique-3$ such that $f$'s input is a graph $G$ with $n$ vertices, $f(G)$ is a graph with $O(n^2)$ vertices, and $$G \in Clique-6 \Leftrightarrow f(G) \in Clique-3$$

The required time complexity for the computation of $f$ is $O(n^4)$.

I am not sure how to approach this problem, and would be thankful if someone can provide insights \ directions to the solution.

# Answer
Create a new graph whose vertices are pairs of vertices in the original graph (optimization: 2-cliques, i.e. edges, in the original graph), and whose edges correspond to 4-cliques. The new graph has a 3-clique iff the original graph has a 6-clique (why?).
> 4 votes

---
Tags: complexity-theory, reductions, clique
---


# Question
Title: Why do we need increase_key procedure in max priority queue?
Since if I want to increase the priority of a specific node, how do I find the node without linear searching it.

I need to pass the index to this function, which is in a way a bottleneck. So the question is, how can I avoid it? Or exactly this data structure doesn't provide any solution for this problem?

Link: web.cse.ohio-state.edu/~lai.1/2331/4.heapsort.pdf | Chapter 5: Priority Queues

# Answer
> 3 votes
In some algorithms, you'll be able to remember the index.

In others, you might need a separate data structure (e.g., a hash table) that maps from the node to its index. When you insert a node into the priority queue, you also add it to that mapping. When you need to know a node's index (e.g.,to call increase\_key), you look it up in that mapping.

# Answer
> 1 votes
In general CLRS case, yes, you need to search the array to find the element whose key (priority) has to be changed. Searching in binary heap is a $O(n)$ operation so it is a linear search.

What CLRS does not mention is that even with a linear search you cannot necessarily locate your candidate. In an integer array, the only information the elements have is their key - their priority. The array elements do not know their domain identifier - (say) EMPLOYEE\_ID or PROCESS\_ID. If all the elements have unique priority key then the search is fruitful, otherwise with multiple items with equal priority the linear search fails. The solution is to either have an `array of structs` or a `2D array` with one column for priority code, another for its domain identifier.

Point is - what is in CLRS is a bare minimum implementation. You got to augment the system anyway.

Take an example of cpu process scheduling using priority queue. Each process has a PID and Priority. Lets say we have a ready queue of $n$ processes. We iteratively pick the process with highest priority, remove from queue and process it - rinse and repeat. Each iteration takes $O(1+ log(n))$ time. How rare is when a processes priority is changed? Assuming *very* rare - in cpu terms, we may take an occasional hit of linear search among a thousand elements.

But if the priority change is *very frequent* \- in cpu terms, or the linear search space is very large then we do have to augment the system with some additional data structure. Now D.W.'s answer comes to play. You have to maintain a mapping between the PID of the process and its index in the array. With this approach, as you correctly point out, you need to keep the hash table in sync with the heap. To do this consider these two implications:

1. You need to tag each entry in the heap with PID anyway - ie. use an array of structs or a 2D array or something like that.
2. Whenever you "use" your queue by extracting the top item, the heap reorganizes itself by shifting roughly $log(n)$ items within the array. That is why cost of extraction is $O(logn)$. Now note that for each of these elements moved in the array, you got to update the item's tag in the hash table too. So for one extraction, the cost doubles. You got to move $log(n)$ items *and* update the hash table for each of them.

In extracting all $n$ items, we are now taking an additional $n$ times $log(n)$ hit in updating the hash table. This entire $nlogn$ expense will remain unused until someone needs to perform a search. What if during the entire lifespan of the activity, (say) we performed $k$ searches against $k$ calls to `increase_key`. Without the augmentation we would have to pay $O(nk)$ for $k$ linear searches over $n$ elements. Question is do we pay an upfront price of $nlogn$ or pay $nk$ as we go?

Evidently, in cases when $(nk \< nlogn) =\> (k \< logn)$, linear search is not that bad either. This is an engineering design decision.

---
Tags: algorithms, data-structures, priority-queues
---


# Question
Title: What would be a decent threshold for classification problem?
I'm using machine-learning algorithms to solve binary classification problem (i.e. classification can be 'good' or 'bad'). I'm using `SVM` based algorithms, `LibLinear` in particular. When I get a classification result, sometimes, the probability estimations over the result are pretty low. For example, I get a classification 'good' with probability of 52% - those kind of results I rather throw away or maybe classify them as 'unknown'.

**EDITED - by D.W.'s suggestion**

Just to be more clear about it, my output is not only the classification 'good' or 'bad', I also get the confidence level (in %). For example, If I'm the weather guy, I'm reporting that tomorrow it will be raining, and I'm 52% positive at my forecast. In this case, I'm sure you won't take your umbrella when you leave home tomorrow, right? So in those cases where my model does not have a high confidence level I throw away this prediction and don't count it in my estimations.

Unfortunately, I can't find articles regarding thresholding the probability estimations...

Does anyone have an idea what is a normal threshold that I can set over the probability estimations? or at least can refer me to a few articles about it?

# Answer
There is no universal answer. Instead, it depends on your application. What counts as useful *for your application*? That determines what should count as a useful or good-enough machine learning algorithm. What counts as useful will vary widely from application to application; some applications require 99.99% accuracy, others might be happy with 52% accuracy.

In practice, there are also multiple ways to define accuracy. If you expect that (in the ground truth) half of the objects should be classified 'good' and half as 'bad', then the obvious accuracy measure suffices, i.e., counting what fraction of instances your classifier outputs the correct answer. However, if 'good' objects are a lot more common than 'bad' objects, or if the penalty for mis-classifying a 'good' object as 'bad' is very different from the penalty for mis-classifying a 'bad' object as 'good', then you might want to measure accuracy differently. The best measure of accuracy is again application-dependent; there is no single universal answer.
> 3 votes

# Answer
If your method is reasonable, then there is a correlation between your confidence and accuracy rates---when your confidence is higher so is your accuracy. Then, get some sample from the true distribution to use as a gold standard. Now study the mentioned correlation. What is the threshold of confidence at which you start to lose accuracy?
> 2 votes

# Answer
For each class you will have a gain $G$ for getting a prediction correct and a loss $L$ for getting a prediction wrong. You solve for probability p using the equation $Gp - L(1-p) = 0$ to get $p$ for which any confidence below should not be scored i.e. $G = 70, L=10, p = 12.5\\%$. Each class will have a different threshold.
> 0 votes

---
Tags: machine-learning, probabilistic-algorithms, statistics, classification
---


# Question
Title: Correctness of following algorithm for 3-QCNF?
Let I have 3-QCNF formula.

Classic recursive algorithm for TQBF takes exponential time. However, following divide & conquer modification allows to do it in quadratic time (not sure about correctness, and that's the question).

```
ctr = 0

for i = 0..n

    Step 1. Take i'th clause, find E-quantified variable inside it.
    If can't, return 'NO'. Otherwise, if it's the clause containing 3
    variables, choose that variable v.

    Step 2. Find all 3-clauses with variable v. Move them from formula Ф
    to formula f_i. Reduce n (length of formula Ф) by number of moved
    clauses.

    Step 3. Copy f_i to f'_i.

    Step 4. Put v = 1 in f_i. Get 2-QCNF.

    Step 5. Put v = 0 in f'_i. Get 2-QCNF.

    Step 6. If f_i and f'_i have same clauses, move them to Ф.
    Increase n by number of moved clauses.

    Step 7. ctr = ctr + 1

for i = 0..ctr

    Step 1. Solve 2-QCNF Ф'^f_i. //Ф' is changed Ф.

    Step 2. Solve 2-QCNF Ф'^f'_i.

    Step 3. If both are false, return 'NO'.

return 'YES'

```

Notes:

Algorithm represents 3-QCNF as $\mathsf{\Phi = TAUT-CNF \land \Phi'(2-QCNF) \land (f\_i(2-QCNF) \lor f'\_i(2-QCNF))\land\ ..}$

Trivially, formula is false if TAUT-CNF contains clauses.

So, if TAUT-CNF has no clauses, formula is represented this way:

$\mathsf{\Phi' \land (f\_i \lor f'\_i)\land\ ...\ =((\Phi'\land f\_i)\lor(\Phi'\land f'\_i))\land\ ...}$

The question: have I violated any logical rule in my algorithm?

# Answer
> 1 votes
Your code ignores quantification levels. Formulas prefixed with $\exists{x\_1}\forall{x\_2}$ are not supposed to be evaluated the same way as those prefixed with $\forall{x\_1}\exists{x\_2}$. Your code treats them the same, moving one existential quantifier ahead of all the other quantifiers in each of your 2-QBF subformulas.

---
Tags: algorithms, satisfiability
---


# Question
Title: Go-Back-N ARQ Protocol Throughput Question
I am an undergraduate studying Data Coms and Networking and this question about go-back-N ARQ popped up that I am struggling to get my head around and cant find anything similar online. Any help at all would be greatly appreciated.

The only thing I have at all is that throughput could be defined by (Packet bits + overhead)/N. Is this at all on the right path?

QUESTION Consider the Go-Back-N ARQ protocol with N=5 and 4 bits used for sequence numbering. The user data frame is 3000 bits long where 100 bits are overhead for header and error check, etc. The frame transmission rate is 2Mbps. Assume that the medium does not reorder the frames. The outstanding frames will be retransmitted when the sending window becomes empty. The probability that a data frame would be received without any errors is 0.3.

i) What is the effective data transmission rate of this protocol?

ii) Suppose that at time t, the receiver is waiting for an information frame with binary sequence number 1001. What is the possible sequence number Slast in binary inside the sender’s window at time t? Justify your answer.

# Answer
Window size Ws is 5. the time to transmit one frame is: tf=3000/2 Mbps=1.5ms As the frame may be received in error with probability 0.7, each frame need to be transmitted 10/3 times on average. Then the time needed for successfully transmitting one frame is

tf+7/3\*Wstf=

38/3\*tf=19ms.

The effective rate is (3000-100)/19ms=152.6kbps. ii) 1001 in binary is 9 in decimal. Frame 8 must have be received by the receiver and the ACK has been sent back to the sender. Therefore, frame 3 must not be included in sender’s window. As frame 9 hasn’t been received yet, 9 must be greater than or equal to Slast. Therefore, Slast can be any of these: 4 to 9 in decimal. Orin binary, 0100, 0101, 0110, 0111, 1000, 1001.
> 0 votes

---
Tags: computer-networks
---


title: Does my Algorithm Qualify as MergeSort?

text:
# Question
Title: Does my Algorithm Qualify as MergeSort?
I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "version" of the algorithm from there.

I did this with MergeSort recently, and I got an algorithm that for what I can tell *works* but I'm not sure it runs in O(nlogn) time like MergeSort does. Here's my code, it's in Python:

```
def mergeSortAlgorithm(x):

    listOfLists = []

    for i in range(len(x)):
        temp = [x[i]]
        listOfLists.append(temp)                          #I first put every item in the array into
                                                      #its own list, within a larger list -> divide step

                                                      #so long as there is more than one sorted list, then we need to keep merging
    while(len(listOfLists) != 1):
        j = 0

                                                      #for every pair of lists in the list of lists, we need to merge them
        while(j < len(listOfLists)-1):
            tempList = merge(listOfLists[j], listOfLists[j+1])
            listOfLists[j] = tempList
            del listOfLists[j+1]                          #I shift the new list to index j, and delete the second list from the now-merged pair at index j+1
            j = j+1                                       #increment the value of j, basically a counter
        print(listOfLists)

    print(listOfLists[0], "is sorted!")

def merge(a, b):                                          #function to merge two lists in order
    newList = []
    count1, count2 = 0, 0

                                                      #basically, walk through each list, adding whichever element is smallest
    while((count1 < len(a)) and (count2 < len(b))):

        if(a[count1] > b[count2]):
            newList.append(b[count2])
            count2 = count2 + 1                           #update the counter along b

        elif(a[count1] < b[count2]):
            newList.append(a[count1])
            count1 = count1 + 1                           #update the counter along a

        elif(a[count1] == b[count2]):                     #if they're equal, add the value from a first
            newList.append(a[count1])
            newList.append(b[count2])
            count1, count2 = count1 + 1, count2 + 1       #update the counter on each

    if(count1 < len(a)):                                  #if the while loop exited with left-over values in a, add them
        for f in range(count1, len(a)):
            newList.append(a[f])
    elif(count2 < len(b)):                                #do the same for b - the values are already in order so you're good
        for k in range(count2, len(b)):
            newList.append(b[k])

    return newList

```

The algorithm correctly sorts what I give it, but I'm thinking that the runtime is more like $O(\log n\cdot \log n\cdot n)$ because the outer while loop in mergeSortAlgorithm() will do $\log n$ passes, as will the inner while loop, and the merge() algorithm will take in total $n$ operations.

Is that right? If so, in what respect does my algorithm differentiate from MergeSort? (i.e. where am I going wrong?)

Thanks so much for your help, please let me know if you have further questions I can help explain.

# Answer
I agree in principle with the comment suggesting that a recursive implementation would be simpler to analyze, and the other comment mentioning that there is no "legal" definition of such an algorithm like merge sort.

However, I think you've done yourself a favor (in terms of your learning objectives) by attempting to implement this bottom-up (rather than top-down), iterative (rather than recursive) merge sort, which is essentially what you have above. I think this shows good understanding on your side. Perhaps you can attempt to implement an in-place version, rather than creating a *newList* (etc.).

Typically, you would divide the input into two equal parts, sort each, and then merge. Instead, you start "at the leaves" and progress up the chain -- merging singletons, then merging pairs, then merging pairs of four items, etc. Each iteration of your loop "looks like" a particular depth-level in the recursive tree of typical merge sort.

That said, your *del*ete-based approach isn't the most suited for arrays (which, it seems, CPythons lists are under the hood -- a Google search found this) at all in terms of cost. You should be able to fix this, but when doing so, be careful to handle non-power-of-two input sizes.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


title: Static hash tables

text:
# Question
Title: Static hash tables
Assume one wants to store $1000$ distinct integers of $5$ digits in a hash table that is defined once for all (the intent is to hard-code it).

We have some freedom to change its behavior by changing the number of buckets and/or the hashing function.

Is there a theory that can help minimize the worst-case or average-case lookup time, in the same way you can optimize a binary search tree ?

I am more after a practical solution, meaning that accesses to the optimal table should be truly faster than with a table built without care.

---

The space requirement is a reasonable constant factor, say $2$ or $3$ times the number of integers. An array of $100000$ slots would be out of question.

# Answer
It is always possible to build a static hash table which has guaranteed O(1) lookup time, provided you allow O(N) empty slots.

For example, a cuckoo hash table will give you a definite found or not found indication with at most two entries examined. Unfortunately, it requires that half the entries in the table be empty to provide this guarantee, so 1000 entries would need a table of 2000 words -- or perhaps 2048 to make hash computations cheaper. There is no additional overhead, since there are no chain links or anything of the sort.

If two words per entry is too much, you can explore the trade-off between the constant number of cells which need to be examined and the density of the table. For example, if you allow each slot to hold two values, you can increase the hash-table density to about 80%, but the number of comparisons to determine where and whether an entry is in the table increases to maximum four instead of two. With four hash functions instead of two and one entry per slot, you can increase the density to 99%, but now you might need to compute up to four hash values as well as doing the four comparisons.

In practice, the hash function for a cuckoo hash can be quite simple (eg. three products xor'd together and a shift, or even simpler if you are prepared to try more possibilities during table construction) and the table can be built in expected time O(N) (and with a reasonably small constant).

Since the discovery of cuckoo hashing, a number of similar datastructures have been invented with the same O(1) guarantee, generally allowing a larger density (and thus a smaller space overhead), but again at the cost of an increased (but constant) number of probes. In general, the approach is to attempt to store the candidate matches consecutively to take advantage of modern CPUs memory caches and potential compare parallelism. If that fits your use case, you might want to look at hopscotch hashing.

If you are willing to expend more time constructing the static table, you could use a perfect hash, which requires only one lookup because it is collision-free. The more time you are willing to spend, the smaller a table you will be able to construct. While it is possible to find a hash which allows 100% utilization of the hash table, the hash function itself needs some storage which is O(N) with a very small constant (a few bits per entry in the table.)
> 4 votes

# Answer
You can use the (minimal) perfect hash function, which is like in your case static (because dynamic insertions / deletions require rehashing), so there is no collision resolution - there are none. The only problem is to find one, but with $n = 1000$ you may brute force it, or use existing software like CMPH or gperf.

There is one worth reading Near-Optimal Space Perfect Hashing Algorithms.

Since you didn't give the space requirement, when the hash is not minimal it is far easier to find.
> 4 votes

---
Tags: data-structures, hash-tables
---


# Question
Title: Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$
Note: this is from JeffE's Algorithms notes on Recurrences, page 5.

(1). So we define the recurrence $T(n) = \sqrt{n}T(\sqrt{n})+n$ without any base case. Now I understand that for most recurrences, since we're looking for asymptotic bounds, the base case wouldn't matter. But in this case, I don't even see where we could define the base case. Is there any number we are guaranteed to hit as we keep taking square roots starting from any integer Do we just define $T(n) = a$ for $n\<b$, for some reals $a$, $b$?

(2). On page 7, Erickson gets that the number of layers in the recursion tree L will satisfy $n^{{2}^{-L}} = 2$. Where is this coming from? I have no idea. I see that the number of leaves in the tree should sum to $\sqrt(n)\sqrt(n) = n$, but I have no idea where to go from there.

Any help is appreciated!

Notes I'm looking at: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

# Answer
You should really be asking a third question: what happens if $n$ isn't a perfect square. The answer to this question is that the actual recurrence should have $T(\lfloor \sqrt{n} \rfloor)$ or $T(\lceil \sqrt{n} \rceil)$ instead of $T(\sqrt{n})$, though in the analysis we will only consider inputs which are "recursive" squares.

Regarding your first question, there can be more than one base case. For example, perhaps $T(n) = 1$ for all $n \leq 100$. You are guaranteed to eventually hit this base case. In this case, as in most cases, the exact form of the base case doesn't affect the big Theta asymptotics (but it does affect the hidden constant).

Finally, regarding your second question, suppose that your base case specifies $T(n)$ for $n \leq C$. The recursion tree (which is a particular interpretation of some features of the recurrence) has the following form:

* The root is one instance of size $n$.
* The root has $\sqrt{n}$ children which are instances of size $\sqrt{n}$.
* Each node at depth 1 has $\sqrt{\sqrt{n}} = n^{1/4}$ children which are instances of size $\sqrt{\sqrt{n}} = n^{1/8}$.
* More generally, a node at depth $d$ is an instance of size $n^{1/2^d}$. You can prove this by induction by checking the case $d = 0$ (where $n^{1/2^d} = n$) and calculating $\sqrt{n^{1/2^d}} = n^{1/2^{d+1}}$.

The recursion terminates when the instance has size at most $C$, and this happens when $n^{1/2^d} \leq C$. At the point that this happens, we have $n^{1/2^{d-1}} \> C$ (assuming $n \> C$), and so $\sqrt{C} \< n^{1/2^d} \leq C$. Taking the logarithm, $\frac{1}{2} \log C \< \frac{\log n}{2^d} \< \log C$ and so $\frac{\log n}{2^d} = \Theta(1)$, implying $2^d = \Theta(\log n)$. We can conclude that $d \approx \log\log n$. This is the number of layers in the tree. Jeff uses $C = 2$, which is how he gets his particular formula.
> 7 votes

# Answer
Answering your first question. Alternative to using the upper bound and lower bound to achieve a base case, one option is that you could assume the form of $n$.

Take, for example, the mergesort recursion:

$$T(n) = 2c \cdot T\left( \frac{n}{2} \right) + c \cdot n $$

Clearly, most $n$ will not divide evenly into integers. It is then pretty common to assume that $n$ is of the form: $$ n = 2^k \quad\quad k \in \mathbb{N}$$

This implies every $n$ is a positive power of $2$, thus resolving our base case always to $1$. Alternatively we could make the base case $c$ instead of $1$ by assuming $n$ is of the form: $$ n = c \cdot 2^k \quad\quad k \in \mathbb{N}, c \in \mathbb{N}^+$$

We can apply this to our recurrence:

$$T(n) = \sqrt{n} \cdot T\left(\sqrt{n}\right) + n$$

Assume $n$ is of the form: $$n = c^{2^k} \quad \quad k \in \mathbb{N}, c \in \mathbb{N}^+$$ Then the base case will always resolve to a constant $c$.

Now if you can prove it under this assumption, you could then go on to make a proof for $n$ values that do *not* have this form. One approach would be by attempting to bound it by the next highest (or lowest) $n$ that *does* have that form.
> 4 votes

---
Tags: recurrence-relation
---


# Question
Title: Addition modulo 2 notation (Quantum Computing)
I am studying Quantum Computing using the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang. I am confused by the meaning of the $\oplus$ (addition modulo 2) symbol in the notation.

Given a starting state $|\psi\rangle|\phi\rangle$ and a unitary gate $U$ such that $U|\psi\rangle|\phi\rangle = |\psi\rangle|\phi \oplus f(\psi)\rangle$. What does in this case $\oplus$ mean, in the general case for $|f(\psi)\rangle = \alpha\_0 |0\rangle + \alpha\_1|1\rangle$ and $|\phi\rangle = \beta\_1 |0\rangle + \beta\_2 |1\rangle$?

# Answer
The question is about the general case, but the purpose of U can be explained more clearly with an example. You can find in the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang an example about period finding. Then the Unitary gate with the same definition $ U|\psi\rangle|\phi\rangle = |\psi\rangle|\phi \oplus f(\psi)\rangle $ is used in an algorithm with output r or repetition rate with f(x) = x + r. In this case and for the most algorithms in quantum computers, the addition modulo addition is used for the purpose its name implies. It is a binary operation for adding two numbers with a XOR operation or with the CNOT quantum gate.

It is used in the period finding algorithms for its property to recognize the same output value with two different input values. Suppose we have a function $ f(x) = f(x \oplus s) $ with s is an fixed binary string 101. For x = 000 and x = 101 the result is the same in both cases. So you can find similar values in a periodic function
> 0 votes

# Answer
The definition shows how $U$ is defined on the standard basis (that is, when $\psi$ and $\phi$ are pure states). You can extend it to general states in a linear way.

Two more comments:

* $\psi$ could be one qubit, but it could also be longer.
* $f$ is probably a *deterministic* function.
> 0 votes

---
Tags: quantum-computing, notation
---


# Question
Title: In asymptotic notation how to prove that $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$
I have to prove that $$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$ The functions are non-negative.

**Clarification**: $$\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$ it means $$\mathcal{O}(f(n)+g(n))\subseteq\mathcal{O}(f(n))\land\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n)+g(n))$$

I try to explain my argument, i want to get on one side $f(n)+g(n)\in\mathcal{O}(f(n))$ and on the other: $f(n)\in\mathcal{O}(f(n)+g(n))$ in order to conclude that $\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$ true.

I start with the hypothesis:

$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\iff g(n)\in\mathcal{O}(f(n))$ $\iff(\exists c\_1\in\mathbb{R}\_{\>0},n\_0\in\mathbb{N}:g(n)\leq c\_1f(n),\forall n\geq n\_0) \implies$ $\\{$adding $f(n)$ to both members of the inequality$\\}$ $(\exists c\_1\in\mathbb{R}\_{\>0},n\_0\in\mathbb{N}:g(n)+f(n)\leq c\_1f(n)+f(n),\forall n\geq n\_0)\implies\quad(\exists c\_1\in\mathbb{R}\_{\>0},n\_0\in\mathbb{N}:g(n)+f(n)\leq (c\_1+1)f(n),\forall n\geq n\_0)\implies \\{\textrm{taking}\quad c\_1^{'}=(c\_1+1)\\}\quad (\exists c\_1^{'}\in\mathbb{R}\_{\>0},n\_0\in\mathbb{N}:g(n)+f(n)\leq c\_1^{'}f(n),\forall n\geq n\_0)\iff \\{by\quad definition\quad of \quad Oh-big \quad order\\}\quad f(n)+g(n)\in\mathcal{O}(f(n))$

Now to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ start from the trivial proposition: $\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))$:

$\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))\iff f(n)\in\mathcal{O}(f(n))\iff(\exists c\_2\in\mathbb{R}\_{\>0}, n\_0\in\mathbb{N}:f(n)\leq c\_2f(n),\forall n\geq n\_0)\implies$ $\\{$adding $g(n)$ to right member of inequality$\\}\quad (\exists c\_2\in\mathbb{R}\_{\>0}, n\_0\in\mathbb{N}:f(n)\leq c\_2f(n)+g(n),\forall n\geq n\_0)$

At this point I'm stuck I don't know how to continue in order to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ to finish then the proof...

Thanks to everyone who read this :)

# Answer
I think you are pretty much done.

$$ g(n) \ge 0 \implies f(n) \le f(n) + g(n), \quad \forall n \in \mathbb{N} $$

So pick $c = 1 \in \mathbb{R}^+$ and $n\_0 = 1 \in \mathbb{N}$, then $$ f(n) \le c\cdot(f(n) + g(n)), \quad \forall n\ge n\_0 $$
> 2 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Demonstration that EXP is closed under union complementation and concatenation
How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?

# Answer
> 2 votes
By definition $EXP = \bigcup\_{k\in N}{DTIME\big(2^{n^k}\big)}$.

Let $L\_1, L\_2 \in EXP$. Then $L\_1 \in DTIME\big(2^{n^m}\big)$ and $L\_2 \in DTIME\big(2^{n^k}\big)$ for some $k,m \in N$.

So for a string $w$ checking $w \in L\_1 \cup L\_2$ takes $2^{n^m} + 2^{n^k}$ time which is $O(2^{n^l})$ where $l = max(m,k)$. So $L\_1 \cup L\_2 \in DTIME\big(2^{n^l}\big)$ and hence in $EXP$.

Let $w$ be a string of length $t$. Then checking $w \in L\_1L\_2$ takes $t(2^{n^m} + 2^{n^k})$ since for strings $u$ and $v$ such that $w=uv$ we check $w \in L\_1$ and $v \in L\_2$ $t+1$ times since there are $t$ different prefixes and suffixes of $w$. Assuming $l = max(m,k)$ we have $t2^{n^l}$ running time which is less than $2^t2^{n^l} = 2^{t + n^l}$ which belongs to $EXP$.

Finally, checking $w \in L\_1$ takes $O(2^{n^m})$ times so the Turing machine halts with "no" if $w \in L\_1$, with "yes" otherwise. Thus $\overline{L}\_1^{} \in EXP$.

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


# Question
Title: Deciding on decidability of a problem and reducing it to halting problem if not decidable
Given are two following languages:

$L\_1 = \\{ w\\#x \hspace{1mm} | \hspace{1mm} w,x \in \\{0, 1\\}^\* \text{ where } M\_w \text{ with input } x \text{ visits each of its states at least once} \\}$

$L\_2 = \\{ w\\#x \hspace{1mm} | \hspace{1mm} w,x \in \\{0, 1\\}^\* \text{ where } M\_w \text{ with input } x \text{ does not visit at least one of its states} \\}$

Are the languages decidable/undecidable/semi-decidable?

The intuition tells me that both languages cannot be decidable, for the simple reason that if any of them ends up in a loop, it can never be decided whether all states were visited. Is my way of thinking correct in both cases?

I would also say that $L\_1$ is semi-decidable - in case all states were visited after some finite number of steps, we could decide the language and if not, we still won't be able to say anything about it.
Is it possible to reduce the halting problem to this problem to prove that it's not decidable?

Thank you!

# Answer
The first language is semidecidable while the second one is not semidecidable.

**Claim 1:** $L\_1 = \\{ w\\#x \hspace{1mm} | \hspace{1mm} w,x \in \\{0, 1\\}^\* \text{ where } M\_w \text{ with input } x \text{ visits each of its states at least once} \\}$ is semidecidable.
**Proof:** On input $w\\#x$ Simply simulate $M\_w$ on $x$ and count the number of visited states. If the counter reaches $|Q|$ then ACCEPT. This shows $L\_1$ is semidecidable/RE.
**Claim 2:** $L\_2 = \\{ w\\#x \hspace{1mm} | \hspace{1mm} w,x \in \\{0, 1\\}^\* \text{ where } M\_w \text{ with input } x \text{ does not visit at least one of its states} \\}$ **is not** semidecidable.
**Proof:** Let $L\_2$ be semidecidable. Then since $\overline{L}\_1 = L\_2$, i.e., $L\_1$ and $L\_2$ are complement of each other, $L\_1$ (and so $L\_2$) is decidable. In this case we can reduce the Halting problem to $L\_1$ as following. Let $M$ be a Turing machine deciding $L\_1$. We construct a Turing machine that decides the Halting problem. On input $w\\#x$ we modify $M\_w$ so that when $M$ halts, it first traverses all other states and then halts. We could do it by changing the ACCEPT state to a normal state, introducing a new ACCEPT state, and adding the following new transitions $$\delta(q\_1, a) = q\_2, \dots, \delta(q\_n, a) = q\_{new-accept}$$ where $a$ is a new alphabet symbol and when the modified $M\_w$ is at the state $q\_{old-accept}$ it first writes $a$ on the tape and enters the state $q\_1$ (without moving the head, i.e, the head always reads $a$). Similarly for the the REJECT state. Thus $M\_w(x)$ halts if and only if $M\_w$ visits all states, which is decidable by $M$.
> 1 votes

---
Tags: turing-machines, undecidability, semi-decidability
---


# Question
Title: Implementing abduction over first order theories
I am interested in implementing abduction over a full first order theory ie it may be non-Horn. (Aside: Almost all the references I've seen for abduction operate over Horn theories eg "Modeling Abduction over Acyclic First-Order Logic Horn Theories in Answer Set Programming: Preliminary Experiments". Is there a reason for this other than lack of minimal hypotheses?) Are there frameworks that might be suitably modified for my purposes? Alternatively, does anyone know of a way of coaxing a SMT solver into perhaps giving me something close to what I need?

thanks!

# Answer
You could use an SMT solver inside a counterexample-guided inductive synthesis loop to learn an expression that fits. The paper below does something similar. If you aren't interested in finding the weakest expression, you could save on computational costs by using templates.

* Albarghouthi, Aws, Isil Dillig, and Arie Gurfinkel. "Maximal specification synthesis." ACM SIGPLAN Notices. Vol. 51. No. 1. ACM, 2016.
> 2 votes

---
Tags: first-order-logic, reasoning
---


# Question
Title: Can the height of a binary search tree be less than that of a red-black tree?
This is a question from the book Algorithms by Robert Sedgewick and Kevin Wayne.

"Find a sequence of keys to insert into a BST and into a red-black BST such that the height of the BST is less than the height of the red-black BST, or prove that no such sequence is possible."

I think that in most cases, if not all, the height of a RBT is less than the height of a BST because the RBT ensures balance. However, is it possible for the height of a BST to be less than the height of a RBT? If so, how? Else, how to prove it?

# Answer
> 2 votes
The fact that a red-black tree is balanced just means that if it contains $n$ nodes then its depth is $O(\log n)$. There is no requirement for the depth to be optimal (i.e. $\lceil \log\_2 (n+1) \rceil-1$), only for it to be optimal up to constants. Therefore it is definitely possible for a red-black tree to be deeper than some other binary search tree.

The advantage of balanced trees is that they are guaranteed to be balanced even after operations on the data structure. Since the running time of operations is usually linear in the depth, it is enough for the depth to be $O(\log n)$ rather than the optimal $\approx \log\_2 n$.

# Answer
> 1 votes
It is possible.

One example is the sequence of keys: 5 1 10 15 6 0

I'm considering the left-leaning red-black BSTs since that is the data structure used on Sedgewick and Wayne's book.

## Sequence of insertions on a BST:

```
Insert  5     5

        1     5
            1

       10     5
            1   10

       15     5
            1   10
                 15

        6     5
            1    10
                6  15

        0     5
            1    10
           0    6  15

```

Height: 2

## Sequence of insertions on a Red-black BST:

```
Insert  5       (B)5

        1        (B)5
               (R)1

       10         (B)5
               (R)1  (R)10

       10         (R)5
               (B)1  (B)10

       10         (B)5
               (B)1  (B)10

       15         (B)5
              (B)1  (B)10
                      (R)15

       15         (B)5
              (B)1    (B)15
                    (R)10

       6           (B)5
              (B)1      (B)15
                      (R)10
                    (R)6

       6            (B)5
              (B)1      (B)10
                      (R)6  (R)15

       6            (B)5
              (B)1      (R)10
                      (B)6  (B)15

       6           (B)10
               (R)5      (B)15
           (B)1   (B)6

       0           (B)10
               (R)5      (B)15
           (B)1   (B)6
         (R)0

```

Height: 3

---
Tags: binary-trees
---


title: Is regular expression syntax regular?

text:
# Question
Title: Is regular expression syntax regular?
Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular?

My guess is that the original syntax (concat, | and \*) is, but the Perl-style syntax is not (backtracking). As the newer syntax recognises non regular languages they must also generate non regular languages. If a DFA could recognise a non regular language then there would be a problem...

# Answer
> 2 votes
Both "original syntax" and PCRE's syntax is not regular. You need parenthesis to override operator precedence, which puts your syntax language into the territory of context free languages.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Partitioning a Number on the basis of an equation
I have an equation $x = 3a+4b+2c+4d$, where $a$, $b$, $c$ and $d$ are nonnegative integers such that $a+b+c+d=5$. What algorithm can I use to calculate maximum value of $x$?

# Answer
> 1 votes
Non-negative means that they can be 0. So set everything to $0$ except $b$ and $d$ because they have the highest coefficient.

$x=3\*0+4b+2\*0+4d$ and $0+b+0+d=5$

$x=4b+4d$ and $b+d=5$

$x=4(b+d)$ and $b+d=5$

$x = 4\*5 = 20$

# Answer
> 0 votes
Your problem is a special case of the integer programming problem which is known to be NP-complete. One possible approximation is branch-and-bound algorithm. However, if you have only 4 variables $a,b,c,d$ and and **additional constraint such as** $a,b,c,d \geq const$, then why not try brute force? In case $const =0$ you would have only $6^4 = 1296$ possibilities.

---
Tags: algorithms
---


# Question
Title: Trying to detect recurring events at certain intervals, e.g. daily, weeekly, monthly, annually
I don't have much experience with ML but am looking for some guidance on where I should start.

I have timestamp data mapped to a certain category, e.g. travel, food, groceries, etc.

Judging by some other posts and answers, would it be correct to break the data into these intervals (day, week, month, year) and then try to detect patterns across the intervals? Are there any particular approaches or algorithms I should investigate first? Thanks!

# Answer
> 1 votes
Given an event type and a sequence of times at which it has occurred, there are several ways to check whether it seems to recur periodically.

One simple approach is to look at the interarrival times (the time between each occurrence and the previous occurrence), and histogram those; if it is periodic, you'll see a sharp peak in the histogram.

Another approach is to use autocorrelation to detect periodicity. See, e.g., https://en.wikipedia.org/wiki/Autocorrelation. The Fourier transform can be useful here.

---
Tags: machine-learning, pattern-recognition
---


# Question
Title: Why is adding log probabilities faster than multiplying probabilities?
To frame the question, in computer science often we want to calculate the product of several probabilities:

```
P(A,B,C) = P(A) * P(B) * P(C)

```

The simplest approach is simply to multiply these numbers, and that is what I was going to do. However, my boss said it's better to add the log of the probabilities:

```
log(P(A,B,C)) = log(P(A)) + log(P(B)) + log(P(C))

```

This gives the log probability, but we can get the probability afterwards if necessary:

```
P(A,B,C) = e^log(P(A,B,C))

```

Log addition is considered better for two reasons:

1. It prevents "underflow" whereby the product of probabilities is so small that it gets rounded to zero. This can often be a risk since probabilities are often very small.
2. It is faster because many computer architectures can perform addition more quickly than multiplication.

**My question** is about the second point. This is how I have seen it described, but it doesn't take into account the added cost of getting the log! We should be comparing "cost of log + cost of addition" to "cost of multiplication". Is it still smaller after taking that into account?

Also, the Wikipedia page (*Log probability*) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?

# Answer
> 17 votes
> Also, the Wikipedia page (https://en.wikipedia.org/wiki/Log\_probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

If you just want to compute $P(A\_1)\ldots P(A\_n)$ once, then you are right. You will have to compute $n$ logarithms and $n-1$ additions, whereas the naive method requires $n-1$ multiplications.

However, it is very common that you want to answer queries of the form:

> Compute $\prod\_{i \in I} P(A\_i)$ for some subset $I$ of $\\{1, \ldots n\\}$.

In that case, you can preprocess your data to compute all $\log P(A\_i)$ only once, and answer each query by doing $|I|$ additions.

> Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?

This is a broader question. In general it is (probably?) harder to compute multiplication than addition. Computing $a+b$ is linear in the size of $a$ and $b$ (using the trivial algorithm), whereas we currently don't know how to compute $a\times b$ with the same time complexity (check the best algorithms here).

Of course there is no definitive answer: for instance if you deal with integers only and you multiply by powers of $2$, then you should rather compare shift with add operations.

Nevertheless this is a reasonable statement on all common computer architectures: multiplication on floating-point numbers will be slower than addition.

# Answer
> 4 votes
By "incurred once" it probably means that if you have $N$ probabilities $p\_1,...p\_N$ then you switch to log space only once by taking logs of each $p\_i$, perform probability multiplications in the log space by adding them (which is less time consuming), and then switch back to your initial space using exponentiation.

If the number of operation is only slightly greater than $N$ then I think there is no meaning of switching to the log space (from the performance point of view). However, if the number of operations is too many , then I think it is worth switching to the log space. For example, say you have 50 variables, and your computation involves 1000 multiplications. Then I think you should work in log space.

Finally, addition is faster than multiplication not because of machine architecture. Addition is inherently faster than multiplication. In terms of complexity, it takes $O(n)$ (linear) time to perform addition of two $n$-bit integers, while multiplication takes $O(n^2)$ (quadratic) time.

By the way, this idea is similar to the Montgomery modular multiplication, where multiplications are performed in the Montgomery form which is quite faster than usual multiplication and then reduction.

---
Tags: algorithm-analysis, probability-theory
---


# Question
Title: How to teach random number generator algorithms?
How can I teach random number generator algorithms? I'd like to show how seeding makes randomization closer to truly random.

Details of the task to be given are as follows:

> Code should read a text file. The file has random words (one word on each line). This is the dataset from which words will be selected randomly.

I am unsure of how to explain the difference between deterministic randomization and non-deterministic randomization using the above example.

# Answer
> 0 votes
So much depends on the language or library you are using. If the tool you are using allows feeding a specific seed I would start by demonstrating how using the same seed gives the same set of random numbers each time. If not and the tool uses the system time as the seed, as many do, then create several random data sets if a very tight look and show how they are the same.

This cre3ating several random sets in a tight loop is something students often do by accident BTW. It gives them no end of trouble as they see identical numbers for all of them.

Then demonstrate how the same code gives different (from the first example) random numbers when used with a different seed.

With your example, using a random number from the same seed would return the same word every time. Using a time based seed should normally return a different word each time.

BTW random.org is a useful/interesting site on the topic. They go into some detail on random and pseudo-random numbers at https://www.random.org/randomness/

---
Tags: algorithms
---


# Question
Title: Application of Brent's Cycle Detection Algorithm
I would like to find cycles in a finite length list of numbers where there is no function:

xn = f(xn-1).

For example, in the list:

3, 12, 11, 46, 1034, 23, 12, 11, 46, 1034, 5

x0 = 3, x1 = 12, etc. and the cycle starts at x1 with a length of 4.

There is a Java implementation of Brent's Cycle Algorithm here which includes some sample data with the expected output.

```
Brent Cycle Algorithm Test

Enter size of list
9

Enter f(x)
6 6 0 1 4 3 3 4 2

Enter x0
8

First 9 elements in sequence :
8 2 0 6 3 1 6 3 1 6

Length of cycle : 3
Position : 4

```

Here you can see that x0 = 8 and that the 8th entry in the entered list is 2 (using a zero based index), which when used as an index gives 0, which when used as an index gives 6 and so on producing the first 9 elements in the sequence 8, 2, 0, 6, etc.

My problem (likely due to my lack of understanding about the purpose or use of Brent's Algorithm) is that the numbers in the list I provided (3, 12, 11, 46, etc.) cannot be used as indexes (indicies?) to access the next number in the list. In other words, there is no f(x) such that xn = f(xn-1).

Does this put Brent's Algorithm out of reach for my application? Maybe there's a simple modification to Brent's Algorithm that hasn't occurred to me.

# Answer
If the numbers in the list are stored in memory as a list, you can just use a hashtable to look for duplicates, or you can sort them and then look for duplicates.

Brent's algorithm is primarily useful in situations where you don't want to store all of the numbers in memory, because the memory cost would be too high -- but that doesn't apply if you have a list with the numbers, because then you're already committed to storing all the numbers in memory.
> 2 votes

---
Tags: algorithms
---