# Question
Title: Kernelization trick, for neural networks
I've been learning about neural networks and SVMs. The tutorials I've read have emphasized how important kernelization is, for SVMs. Without a kernel function, SVMs are just a linear classifier. With kernelization, SVMs can also incorporate non-linear features, which makes them a more powerful classifier.

It looks to me like one could also apply kernelization to neural networks, but none of the tutorials on neural networks I've seen have mentioned this. Do people commonly use the kernel trick with neural networks? I presume someone must have experimented with it to see if it makes a big difference. Does kernelization help neural networks as much as it helps SVMs? Why or why not?

(I can imagine several ways to incorporate the kernel trick into neural networks. One way would be to use a suitable kernel function to preprocess the input, a vector in $\mathbb{R}^n$, into a higher-dimensional input, a vector in $\mathbb{R}^{m}$ for $m\ge n$. For multiple-layer neural nets, another alternative would be to apply a kernel function at each level of the neural network.)

# Answer
I think you might be confusing the terminology in a way that is making the issue confusing. SVMs work by defining a linear decision boundary, i.e., a hyperplane. We can define this hyperplane in terms of inner products between the points. Therefore, if we define this inner product to be in some high-dimensional, or even infinite dimensional space, what looks like a hyperplane in this new space is a not necessary linear in the original feature space. So everything is still linear, the only thing we've done is to implicitly (via the new inner-product) embed the points in some higher dimensional space. Maybe you already know all this.

There are 2 issues to consider with respect to neural networks. The first was brought up by @Yuval Filmus, because of the hidden layer neural networks depend on more than just the inner products between the points. If you remove the hidden layer, you just have something like logistic regression, of which there are kernelized versions. Maybe there is a way to get around this, but I don't see it.

Secondly, you mention preprocessing the input by projecting into a higher, but not infinite, dimensional space. Neural networks define a decision surface and this surface is not constrained to be linear. This means the gain from projecting the points into a higher dimensional space will be different, i.e., it may make it easier to find a good set of weights, but we haven't necessarily made our model any more powerful. This follows from the Universal approximation theorem that tells us given a large enough number of hidden units we can approximate any function (under some restrictions). This last statement is rather vacuous and I kind of hate to mention it. By not telling you anything about how to find the right weights it doesn't bring much to the table from an application perspective.
> 6 votes

# Answer
The kernel trick is possible for SVMs because of a special property of the learning process for SVMs. Neural networks don't seem to have that property (as far as I can tell).

Let $x\_1,\dots,x\_n \in \mathbb{R}^d$ be the points in the training set. Normally, you'd expect that a machine learning algorithm would look at the values of the $x\_i$'s. However, the SVM learning process has a rather remarkable property. It doesn't need to know the values of the $x\_i$'s. It is sufficient to be able to compute $x\_i \cdot x\_j$ for any desired pair of input points (i.e., to compute the dot-product for any pair of input vectors of your choice); that's all the SVM learning process needs.

This special property of the SVM learning process allows us to use the kernel trick. We can define a kernel function $K$ so that $K(x\_i,x\_j)$ is the dot-product of some non-linear transformation of the inputs. If we're transforming the input vectors via a nonlinear transformation $\phi : \mathbb{R}^d \to \mathbb{R}^m$ (for some $m \> d$), then we define $K(x\_i,x\_j) = \phi(x\_i) \cdot \phi(x\_j)$. The next cool property is that, for some nonlinear transformations $\phi$, you can compute $K(x\_i,x\_j)$ more efficiently than computing $\phi(x\_i),\phi(x\_j)$ explicitly and then computing their dot-product; you can compute $K(x\_i,x\_j)$ in $O(d)$ time (say) rather than $O(m)$ time.

Unfortunately, neural networks don't seem to have any way to take advantage of this cool trick, because the learning process for neural networks seems to depend upon more than just the values $x\_i \cdot x\_j$ (or $K(x\_i,x\_j)$); it requires the full values of all the $x\_i$'s. So, while we can indeed pre-transform the inputs to the nonlinear network via some nonlinear function if we want, there doesn't seem to be any way to use the kernel trick to make this more efficient, like we can do for SVMs.
> 2 votes

# Answer
I would like to share some observations I have made. Input dimension: 144. I have trained a neural network, and during training, the output of the hidden layers were given as input for logistic regression, and the mean value of loss function after fitting the model was plotted.

We can see that with increase in layer size, the features, or the output of the hidden layers are becoming linearly separable. While this is the purpose of learning the **kernelised feature vector**, neural network seems to be doing this internally.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: Can we build computer without instruction pointer register (PC/IP)?
I am studying computer architectures in university and my teacher asked me if we can create a computer without PC/IP register?

# Answer
One possible thought could be a data-flow architecture.

Here the various processing elements are wired together to implement the desired algorithm and rather than an IP register, each processing element (add, subtract, multiply, and, or, compare etc) acts when data is presented.

This sort of things is mostly seen today in fast algorithms embedded in FPGAs. I understand, but have no direct info, that crypto-currency miners are designed along these lines.

So, is this still a computer? Well. oddly enough, a popular way to program these machines uses "C" source code to describe what needs to be done and a sophisticated compiler to design the data-flow machine needed to get the job done.

On a similar note, the LabView programming environment presents a similar model with interconnected elements driven by the data and not an instruction address concept.
> 2 votes

# Answer
It's been done. In some early computers (Bendix G-15 for example) every instruction contained the address of the next instruction.

This odd architectural choice was made because the main memory was a magnetic drum, and reading memory had to wait for the drum to rotate to the correct position. It was important to place the next instruction where it could be read as soon as the current instruction finished execution.
> 1 votes

---
Tags: computer-architecture
---


title: Predication execution

text:
# Question
Title: Predication execution
I was studying branch prediction & predication execution and faced a trouble..

I'm not quite sure whether I understood the concept of predication but based on what I have learned it is taking both taken and not taken at the same time.

For example, let's assume we have 'if' and 'else' each filled with 3 instructions.

For branch prediction, if prediction is correct, we won't have any loss in performance. But if prediction is wrong, there's a waste of 3 instructions.

For predication, either right or wrong, we will have waste of 3 instructions. Then what is the use of predication?

Branch prediction has an accuracy over 90%(I don't know if this only applies to branches with many instructions that can learn from history).

If so, we have a low chance of wasting.

But even besides that, only when prediction accuracy is 0%, branch prediction will be same as predication.

SO where am I getting wrong?

# Answer
> 4 votes
The cost of a branch misprediction depends on the depth and width of the pipeline and not the amount of code guarded by a condition. A processor keeps fetching and decoding down the wrong path until the branch is resolved and the correct target determined. In a two-wide processor with five stage before branch resolution (a "moderate performance design", say two instruction fetch stages, a decode stage, a register read stage, and an execute stage with a branch resolving at the end of the execution stage), a mispredicted branch could lose up to nine instruction execution opportunities:

```
br+w1       IF IF ID RR EX
w2+w3          IF IF ID RR EX
w4+w5             IF IF ID RR EX
w6+w7                IF IF ID RR EX
w8+w9                   IF IF ID RR EX
c1+c2                      IF IF ID RR EX

```

In most real code, two consecutive instructions would not always be able to execute in parallel, so the actual lost performance would be lower. (If the branch was the second instruction of a pair, only 8 instruction execution opportunities would be lost.)

In a fully predicated ISA, the predicated form could also have one less instruction (a branch instruction might include a comparison that would have to be provided as a separate instruction to provide a predicate but often normal instruction results provide a predicate).

Another consideration is that predication avoids fetch redirection. Some implementations have had a one cycle taken branch fetch penalty; for a two-wide processor, this would allow two predicated instructions to execute "for free".

(Out-of-order execution complicates the tradeoffs in providing and using predication. Predication turns an instruction with two dynamic sources into one with three dynamic sources, so the scheduler has to monitor the availability of an additional source (the predicate). In addition, predication converts a control hazard (which can often be bypassed using prediction) into a data hazard (if the predicate is not available, the instruction will not execute and its dependencies cannot execute). In theory, predicates can be predicted just as branch direction is predicted with the prediction only used if the data hazard is expected to introduce excessive slow-down, but this requires both a confidence estimate for the prediction and an estimate of the costs for using and not using the prediction when the prediction is right and when it is wrong.)

Furthermore, not all branches are equally predictable. Some branches approach fifty percent predictability. It is even possible to *always* mispredict (e.g., with two-bit counters initially at weakly wrong for the first encounter and a branch that alternates between taken and not-taken), though this is a rare occurrence.

Predication of nested conditions can also exponentially increase the number of executed instructions. Branch prediction would choose one path for a switch statement; complete predication would follow all the paths.

Another factor is that processing extra instructions can be relatively inexpensive if the processor has otherwise idle resources. E.g., if one path is stalled waiting for the result of a long latency instruction (or cannot fully utilize available execution width), (predicated) instructions from the other path may be able to execute "for free" (power and other costs would still apply).

Predication also makes more sense with vector/SIMD operations where per-element predication can facilitate the use vector operations that would otherwise need to be executed in a scalar fashion. (Even without predication, one can use bitwise SIMD operations to select operands, choosing between the true operand and the identity value for the operation.)

# Answer
> 3 votes
Many modern processors have predicated instructions, for example the CMOVE (conditional move) on x86 processors, lots of predicated instructions on ARM 32 bits, and a lot fewer instructions on ARM 64 bit.

When these instructions are executed, there is no branching at all. For example, a conditional move "move register A to register B if a condition is true" is just a normal instruction, modifying register B (just like adding 0 to B "modifies" it), with register A as a dependency, and with a condition code register as an additional dependency. An ordinary instruction, just like "add register A to register B", just with one more input.

So it's just one instruction. And there is no branch, which will make your code run a lot faster. Modern processors can run two, three or sometimes four instructions per cycle, and branching interferes with that. Let's say you have code "if condition then X = expression1 else X = espression2". If these expressions are not too complicated, then you can calculate them both, and use a CMOVE to pick the right result. Often there is so much parallelism available that calculating two expressions takes no longer than calculating one, and you avoid branches, and importantly you avoid branch prediction that could go wrong.

Take "if x \> 0 then x = x - 1 else x = y+2". You can generate the instructions:

```
compare x with 0, subtract 1 from x, add tmp = y+2
conditional move tmp to x if not greater

```

There's a good chance that the first three instructions are performed in one cycle, and the conditional move in another cycle. Two cycles, plus you could have more instructions slotted in that run in parallel. Compare that to

```
compare x with 0, branch if it is not greater
subtract 1 from x and branch
add x = y + 2

```

This will always have problems with branch prediction and most likely run slower.

# Answer
> 1 votes
Performance improvement is possible because the fetching of the predicted instructions happens at the same time as executing the current instruction. If you guess right, fetching the next instruction was free.

---
Tags: computer-architecture, mips
---


# Question
Title: Async Distributed Algorithm Time Complexity
In theory of distributed systems, I understand message complexity and time complexity are common performance measures, with the first being the number of messages sent in the overall execution of the algorithm, and the time being the number of "steps" it takes to complete the algorithm.

My question is, with asynchronous distributed algorithms, where we assume that at least one message is received and processed per step, how can the time complexity differ from the message complexity? If I have to send m messages to complete the algorithm, it seems to me the worst case time complexity would be $m$, sending one message per time step. For example, the time complexity of an async flood algorithm is $O(n)$ while the message complexity is $O(m)$. Why is the time complexity not $O(m)$ too? Here $m$ is the number of edges and $n$ is the number of vertices. Same goes for constructing a rooted spanning tree.

Again, this is for async systems where messages don't have to be received in parallel.

# Answer
In a distributed system, messages can be sent in parallel. Vertex #1 can send a message at the same time as vertex #2 is sending a message. So, the total amount of time to complete the algorithm might be much less than the total number of messages sent.
> 1 votes

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


# Question
Title: Kolmogorov complexity of a sequence of n bits with k ones
Let Program P be :"Generate, in lexicographic order, all sequences with k ones and n bit length; Of these sequences, print the ith sequence."

Apparently the length of this program is $\log(n) + \log(\binom{n}{k}) + c$ where $c$ is a constant. Where $i$ can be represented in $\log(n)$ bits and k in $\log(\binom{n}{k})$ bits. Why does the length of the program not take into account that we will be generating all of these sequences in lexicographic order, does the length of the sequences and the number of sequences not depend on $n$. Don't you have to hold those in an array? Does that not take space?

Thank you.

# Answer
> 1 votes
In Kolmogorov complexity, our measure of complexity is *program length*. We don't care about the resource consumption of the program (unless we're interested in resource-bounded Kolmogorov complexity). Given $n$ and $k$, a program can generate all $n$-bit strings of weight $k$, so there is no need to store the list itself as part of the program.

The formula you quote and the explanation you give seem mistaken. In order to use the program you mention to generate a specific vector, we need to give it as input $n,k,i$. It takes $K(n) \le \log n + O(\log\log n)$ bits to encode $n$ itself. Given $n$, we can encode $k$ in $\lceil \log n \rceil$ bits, and $i$ in $\lceil \log \binom{n}{k} \rceil$ bits. Overall, we obtain that the Kolmogorov complexity is at most $$ 2\log n + \log \binom{n}{k} + O(\log\log n). $$

---
Tags: kolmogorov-complexity
---


# Question
Title: Understanding the closed form derivation on the function f(n/3) + n^2 +3
I have the function:

$$ f(n) = \begin {cases} 4 & , n = 1 \\ f(\frac{n}{3}) + n^2 -3 & , n \ge2 \end {cases} $$

The given solutions shows the unwinding of the function as follows:

Assuming $ n \ge 2$

$$f(n) = f\bigg(\frac{n}{3}\bigg) + n^2 - 3$$ $$ = \bigg\[f\bigg(\frac{n}{3}\bigg) + \bigg(\frac{n}{3}\bigg)^2 -3\bigg\] + n^2 -3$$ $$ = f\bigg(\frac{n}{3^2}\bigg) + n^2 \bigg(\frac{1}{9} + 1\bigg) -6$$ $$ = \bigg\[f\bigg(\frac{n}{3^3}\bigg) + \bigg(\frac{n}{3}\bigg)^3 -3\bigg\] + n^2\bigg(\frac{1}{9} + 1\bigg) -6$$ $$ = f\bigg(\frac{n}{3^3}\bigg) + n^2 \bigg(\frac{1}{81} + \frac{1}{9} + 1\bigg) -6$$

Where I get lost are the last two lines of the unwinding because I do not understand where the $(\frac{n}{3})^3$ becomes to $n^2(\frac{1}{81} + \frac{1}{9} + 1)$.

*Question is taken from UofT CSC236 Tutorial 6*

# Answer
> 1 votes
The real question is where $\left(\frac{n}{3}\right)^3$ comes form. If you look at the formula, you see that it really should have been $\left(\frac{n}{3^2}\right)^2$.

The morale here is that people make mistakes. Calculations you see in tutorial, in lecture notes, and even in textbooks, are not infallible. When something seems to be amiss, try to understand what calculation is being done, and then try to reproduce it on your own. The mistake may disappear, as in this case, or may persist, in which case there might be a more serious issue in the mathematical development; unfortunately, this also sometimes happens. We are only humans, after all.

---
Tags: runtime-analysis
---


# Question
Title: A Special Case of Multiple Choice Knapsack Problem: Is it NP-hard?
The multiple choice knapsack problem (MCKP) can be defined as follows:

MCKP is known to be NP-hard in general. I have a special case of MCKP for which

* $N\_i=\\{1,2,\cdots,|N\_i|\\}$, for all $1\leqslant i\leqslant k$ ;
* $p\_{ij}=j$, for all $1\leqslant i\leqslant k$ and for all $1\leqslant j\leqslant|N\_i|$; and
* $w\_{i1}\<w\_{i2}\<\cdots\<w\_{i|N\_i|}$, for all $1\leqslant i\leqslant k$.

My question is: Can we solve this special case of MCKP in polytime? (Or, is this special case of MCKP NP-hard?)

# Answer
There is a dynamic programming solution.

Let $f(i, V)$ be the minimum weight to achieve value $V$ while only the first $i$ classes (i.e. $N\_1,\ldots,N\_i$) are considered, then according to the item to be chosen in $N\_{i+1}$, we have

$$ f(i+1,V)=\min\_{0\le j\le |N\_i|}w\_{ij}+f(i,V-j), $$

where $w\_{i0}$ is defined to be 0. Now you can compute $f(n,1),\ldots,f(n,\sum\_{i=1}^n |N\_i|)$ to get the first $j$ such that $f(n,j)\le W$, then this $j$ is an optimal value for your original problem.

This algorithm runs in $$ O\left(\left(\sum\_{i=1}^n |N\_i|\right)^2\right). $$

This is polytime because the input length is $\Theta\left(\sum\_{i=1}^n |N\_i|\right)$.
> 2 votes

---
Tags: algorithms, np-complete, np-hard, knapsack-problems
---


title: Beginner question in Java

text:
# Question
Title: Beginner question in Java
I am just starting to study Java and was wondering why the following code

if(x\>2) x\*=2; if(x\>4)x=0; System.out.println(x);

returns 0 for any value of x greater than 2. For example, when x=3, why would 6 not be returned?

# Answer
Let me rewrite your program in pseudocode:

1. If $x \> 2$ then $x \gets 2x$.
2. If $x \> 4$ then $x \gets 0$.
3. Print $x$.

Let us denote the value of $x$ at the beginning of line $i$ by $x\_i$. If $x\_1 \> 2$ then the condition $x \> 2$ in line 1 holds, and so $x\_2 = 2x\_1$. But then $x\_2 = 2x\_1 \> 2 \cdot 2 = 4$, and so the condition $x \> 4$ in line 2 holds. As a consequence, $x\_3 = 0$, and so line 3 prints 0.
> 0 votes

---
Tags: java
---


# Question
Title: Use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound
how to use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound. this is a algorithm of my class home work,but i dont know how to solve it.

# Answer
> 1 votes
Let's assume that $n$ is a power of 2 (otherwise the recurrence isn't really defined all the way), with a base case at $n=1$. Then $$ \begin{align\*} T(n) &= n^2 + 4T(n/2) \\ &= n^2 + 4(n/2)^2 + 16T(n/4) \\ &= n^2 + 4(n/2)^2 + 16(n/4)^2 + 64T(n/8) \\ &= \cdots \end{align\*} $$ Note that $n^2 = 4(n/2)^2 = 16(n/4)^2$. If $n = 2^m$ then after $m$ steps we will reach $4^mT(n/2^m) = 4^mT(1)$, with $m$ copies of $n^2$ tagging along. Therefore $$ T(n) = mn^2 + 4^mT(1) = n^2\log\_2 n + n^2 T(1). $$

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


# Question
Title: what does "vector" mean in computer science?
I am trying to understand how computers work under the hood, and I came across following sentence.

"Computer technology is based on electronic circuits able to process **vectors** of 0's and 1's. For that reason all data are encoded by strings of 0's and 1's."

So does the vector mean normal string/number 0 and 1?

Thank you

# Answer
Vector here is essentially the same as *string*, *sequence*, or *array*, with the possible connotation of having fixed length.

Here is another way to express the same idea:

> Computer hardware operates on bits. Therefore we have to encode all data in bits before a computer can process it.
> 2 votes

---
Tags: binary
---


# Question
Title: A way to convert a binary tree into a grid
Wondering if there is a way to convert a binary tree into a grid such as this:

```
                    a
                  /   \
                 b     c
                / \   / \
               d   e f   g

                    or

                 d--b--e
                    |
                    a
                    |
                 f--c--g

                    to

                 d--b--e
                 |  |  |
                 y--a--x
                 |  |  |
                 f--c--g

```

An arbitrary sized binary tree. I'm not super familiar with binary tree properties so I am not sure if this would even be possible or if edge cases would prevent it from being possible.

# Answer
A vertex in the grid has $O(d)$ vertices at distance $d$ from it. In contrast, the complete binary tree of height $h$ as $2^h$ vertices at distance $h$ from the root. Therefore there is no isometric embedding of arbitrary binary trees in the grid. Similar considerations show that there is also no embedding of bounded distortion (in which distances increase by at most a constant factor).
> 2 votes

---
Tags: trees, lattices
---


# Question
Title: Find the minimum path to every vertex using Bellman-Ford
I was studying the chapter 24 of the CLRS and got to the following question:

> **24.1-5** $\star$ Let $G=(V,E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb{R}$. Give an $O(VE)$-time algorithm to find, for each vertex $v \in V$, the value $\delta^{\*}(v) = \min\_{u \in V}\\{\delta(u,v)\\}$.

From what I understood, he wants an algorithm to find the shortest path beginning in any $u \in V-\\{s\\}$ to every vertex $v \in V$. So, this algorithm would return one shortest path for each vertex in $V$ in $O(|V||E|)$. I couldn't come with any other answer besides using an All-Pairs Shortest Paths algorithm and choosing the paths with less value for each vertex. But, as this chapter is about the Bellman-Ford, this is probably some modification from the original algorithm.

If someone could point me in the right direction, I would really appreciate.

# Answer
> 2 votes
The algorithm is very similar to Bellman-Ford algorithm except that for each vertex $v$, you maintain $\delta^\*(v)$, while in Bellman-Ford algorithm you maintain the length of shortest path from a certain source to $v$.

The correctness of the proof is also similar to that of Bellman-Ford algorithm. More specifically, you prove the following lemma by mathematical induction.

> *Lemma.* After $i$ repetitions of for loop:
>
> * If $\mathrm{Distance}(u)$ is not infinity, it is equal to the length of some path from to $u$;
> * If there is a path to $u$ with at most $i$ edges, then $\mathrm{Distance}(u)$ is at most the length of the shortest path to $u$ with at most $i$ edges.

# Answer
> 2 votes
You are not parsing this right. The text of the exercise uses $\delta$ implicitly; traditionally $\delta(uv)$ in the context of graph theory stands for the minimum distance metric. Since the exercise makes perfect sense assuming this definition, I will go along with it.

What the problem asks you to do, in other words, is to compute a function $\delta^\*(v)$, defined on all $v \in V$ as the minimum weight $x$ such that there exists a node $u$ for which $\delta(uv) = x$.

I will outline a sketch of the solution, leaving the details to you.

First of all, observe that $\delta^\*(v) \le 0$ since $\delta(vv) = 0$. Furthermore, by subadditivity of $\delta$, it is easy to verify that $\delta^\*(v) \le \delta^\*(w) + \delta(vw)$.

Construct the transpose graph $G^T = (V, \\{(u, v) \mid (v, u) \in E\\})$. Computing $\delta^\*$ on $G$ is equivalent to computing $\delta^{\*T}(v) = \min\_{u\in V} \\{ \delta(vu) \\}$ on $G^T$.

First, assume that $G^T$ has no negative-weight cycles, we will deal with this case later. If there are no negative-weight cycles, the shortest paths are acyclic, therefore we can use our second observation from above to compute $\delta^{\*T}$ as follows:

* For all $v \in V$ set $\delta^{\*T}(v) =0$.
* For $i := 0$ to $|V|-1$ use each edge $uv \in |E|$ to "relax" $\delta^{\*T}(u).$

The above procedure yields a correct result for all nodes of $G^T$ that don't reach any negative cycle. Nodes that *do* reach a negative cycle should be labelled by $-\infty$. We have to find all such nodes to complete our algorithm.

In order to do that,

* Compute $G^{SCC}$, the graph of the strongly connected components of $G$. Each negative cycle must be entirely included in one of those components.
* Run Bellman-Ford on each component to find those which contain negative cycles. Note that the total running time of this step is $O(|V||E|)$ because, assuming the $i$-th connected component has nodes $V\_i$ and edges $E\_i$, the inequality: $\sum |V\_i||E\_i| \le \sum|V\_i| \sum|E\_i| = |V||E|$ holds by Cauchy-Schwarz.
* A node $u$ reaches $v$ in $G^T$ if and only if the equivalence class of $v$ reaches the equivalence class of $u$ in $G^{SCC}$: use a reachability algorithm to find all those nodes.

Piecing together the two parts yields a solution to the original question.

---
Tags: algorithms, graphs, shortest-path
---


title: Loop termination - Loop invariant

text:
# Question
Title: Loop termination - Loop invariant
```
(x >= 0 && y >= 0)
q = 0;
r = x;
while ( r >=y ) {
  r = r - y;
  q = q + 1;
}
(x = q*y +r) && (r >= 0) && (r < y)

```

For this what if y = 0 ?

If y = 0, then r stays at r inside the while loop, which makes r \>= y true always. So it doesn't seem to terminate.

So I think, for pre-condition, doesn't it have to be (y \> 0) to make sure this program terminates ?

# Answer
As mentioned in the comments, it depends on whether you care about *partial correctness* or *total correctness*.

Partial correctness requires that, if the program starts from any state satisfying the preconditions, and *if* the program terminates in a final state, then such final state satisfies the postcondition.

Total correctness requires that, if the program starts from any state satisfying the preconditions, *then* the program terminates in a final state, which satisfies the postcondition.

Only total correctness requires termination, partial correctness does not.

The Hoare logic rules for program statements are roughly the same, except for `while` loops. In partial correctness, the `while` rule requires to find a suitable invariant property. In total correctness, the rule requires both the invariant property and the *variant*: this is a strictly decreasing, natural valued function of the state (roughly, providing an upper bound on the number of loops).

If your rules have no variant, but only deal with the invariant, they are meant to be used to prove partial correctness, only.
> 1 votes

---
Tags: loops, loop-invariants, hoare-logic
---


# Question
Title: How do you know if a language accepted by a DFA is $Σ^*$?
I know that a language that is input into a DFA (call it $X$) is regular just by being accepted by it, but given that it is accepted, how can one figure out that $L = Σ^\*$? In other words, what does a DFA that accepts anything from $Σ^\*$ even look like? When I learnt about DFAs, it was always under the context that $L(X)⊆ Σ^\*$.

I get that this must be a DFA that accepts any input from $Σ^\*$, but I have trouble wrapping my head around it. This is all of course assuming that $Σ$ is any finite set.

# Answer
You don't input a language to a DFA. Each time you run the machine, the input is just a string. The language accepted by the DFA is the set of inputs that cause it to end in an accepting state (called a final state by some authors). Therefore, the automaton accepts $\Sigma^\*$ if every possible input leads to an accepting state.

So, to decide if an automaton accepts $\Sigma^\*$, you need to check if every input does indeed lead to an accepting state.
> 5 votes

# Answer
if a language accepted by a DFA is Σ∗ then every state of dfa is accepting

if all states of a dfa are accepting then they are equivalent to each other so we can use the state minimisation algorithm to minimise the automata

if the minimised automata consist of just 1 state it either accepts every string or rejects every string

source:https://math.stackexchange.com/questions/773683/decide-whether-dfa-accepts-all-strings
> 2 votes

---
Tags: finite-automata, decision-problem
---


title: predication, branch prediction question

text:
# Question
Title: predication, branch prediction question
I have a question about predication and branch prediction.

I've emailed my professor regarding this and he replied me that predication has a less instructions than branch prediction.

So I tried making an example of my on but I'm not sure if this is right..

I've assumed for predication it has 'if' and 'else' each having 100 instructions. Then either right or wrong, it will waste 100 instructions.

For prediction(since this has more instructions), I've assumed it has 'if' and 'else' each having 300 instructions doing exactly the same thing as the predication above.

My questions is..

1. Is it even possible to make 300 instructions to 100??
2. In above case, if predication has to win over the benefit of branch prediction, accuracy of prediction should be below 66.6%. (300\*0.3333=100) Is this correct?
3. If so, when deciding which would be better off than which, does it has to be based on accuracy of a prediction or the size? Reason why I am mentioning size is because during the lecture, I remember my professor saying "use predication in small size loops..."

Thanks in advance..

# Answer
You are absolutely, completely on the wrong path here.

Predicated instructions are used to avoid branching. A predicated instruction avoids the cost of a branch plus possible penalty for a mispredicted branch.

If you have 100 instructions on the if and the else side, then you would need 200 predicated instructions instead of 100 unpredicated instructions to save a branch and possible mispredicted branch penalty. 200 vs. 100. That's not going to save you anything.

What on earth makes you think you would have 200 predicated instructions, and 300 unpredicated instructions on each path? I'd say you are completely misunderstanding what your professor is saying there.

I strongly suggest that you download an Intel or ARM instruction manual and study what predicated instructions are doing, because right now I have the impression that you are operating blindly without any understanding.

Maybe it would help if you wrote down how you would (in an assembly language of your choice, or an invented one) translate "if x \> 0 then y = 1 else z = 2" using a conditional branch, and using predicated instructions.
> 1 votes

---
Tags: computer-architecture, mips
---


title: Basis sets for combinator calculus

text:
# Question
Title: Basis sets for combinator calculus
It is well known that the S and K combinators form a basis set for combinator calculus, in the sense that all other combinators can be expressed in terms of them. There is also Curry's B, C, K, W basis, which has the same property. There must be an infinite number of such bases, but I don't know of any others.

I am aware that there are a number of single-combinator bases, such as the Iota combinator and the various others constructed/reviewed by Fokker. However, these are "improper" combinators, meaning that they are expressed in terms of other combinators rather than pure abstractions.1 For the purposes of this question I'm interested only in basis sets composed of proper combinators.

Does there also exist a study of the other possible basis sets? Ideal would be something along the lines of Wolfram's study of various other models of computation, in which the various combinations are studied systematically. In particular, I'm interested in whether simple examples of the following things are known:

* A minimal basis set that includes the I combinator. (I'm using "minimal" to mean that if you remove any member it stops being a basis, so the SKI basis would not count.)
* A minimal basis set that includes the Y combinator, or the $\omega$ combinator (aka mockingbird)

Any other information about other possible bases for combinatory logic besides S, K and B, C, K, W would be really helpful.

As a broader point, I'm interested in the study of the combinatory calculus as a purely *mechanical* system, i.e. as a set of transformation rules on binary trees with labelled nodes, which need not be given any particular semantic interpretation. Any pointers towards resources that take this approach would be greatly appreciated. (*To Mock a Mockingbird* takes this approach but gives an incomplete presentation, whereas Barendregt's *the Lambda Calculus* is very much tied to semantics, making it hard for me to extract the purely mechanical aspects that I'm interested in.)

1To be precise: in lambda calculus a proper combinator is an expression of the form $(\lambda.x\_1x\_2\dots P(x\_1,x\_2,\dots))$, where $P(x\_1,x\_2,\dots)$ only has $x\_1$, $x\_2$ etc. as free variables, and does not contain any abstractions. So for example, $(\lambda x y z. x(z z))$ is a proper combinator, but $(\lambda x. x(\lambda y.y) )$ is not, because it contains $x$ applied to a lambda term.

# Answer
It's easy to make other bases by switching out the combinators from one basis with ones that do something similar. For example, starting with BCKW, you can switch $C$ for $T = (\lambda x y. y x)$ (since both switch terms around) and $W$ for $\omega = (\lambda x. x x)$ (since both duplicate things). You know this is still a basis because you can recover $C$ and $W$ from it: $C = B(T(B B T))(B B T)$ and $W = C(B \omega(B B T))$.
> 2 votes

# Answer
Any set of combinators that contains a cancellative combinator (like K), a composing combinator (like B), a permuting combinator (like C), a duplicative combinator (like W) and the identity combinator I is a basis. If the I combinator happens to be derived from your four other combinators, then those four alone suffice.

This means that something like B,T,M,K,I, where Tab=ba and Ma=aa, is also a basis. Indeed, B,T,M,K suffices, since I may be derived from B,T,M,K (this is not easy to prove; the proof is to first derive S from B,T,M and then take I=SKK.)
> 2 votes

---
Tags: lambda-calculus, combinatory-logic
---


title: Can ropes (AVL trees) be interned?

text:
# Question
Title: Can ropes (AVL trees) be interned?
Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?

---

I recently implemented a rope data structure in Lua as an AVL tree.

However, I realized a since the ropes are not interned, they can't be used efficiently as keys in a dictionary. (Lua walks over all new strings made by concatenation or slicing in order to intern them, making these $\Theta(n)$ operations, but guarantees fast dictionary lookup by only comparing addresses)

Can AVL tree ropes (or another type of balanced tree) be interned in a similar fashion in *better* than $O(n)$ time? Can fast interning be proved impossible?

Below is what I have thought of so far. I haven't found any resources about interning non-string data structures.

* *Hashing*: You can efficiently determine the hash value of a concatenation or a slice with extra bookkeeping for some hash schemes (like Java's). However, you can't guarantee there are no collisions in these hashes (and actually their slicability/concateability can make them very easy to attack).
* *Normalizing*: There are many different shapes that AVL trees with identical contents can take on. I could try to pick one special form for each size and designate it as the "canonical" form. When new trees are made when concatenating or slicing, *in addition* to balancing the tree, we reshape it to its canonical form. Naively this should not be efficient, because the vast majority of forms for a given size are $O(n)$ edits away from any particular canonical form. However, maybe if all subtrees are given some particular form, canonicalizing can be made efficient.

I tried the obvious perfectly-balanced tree as the canonical shape, but I couldn't make an efficient way to concatenate these. Another version I considered was "as left leaning as possible" but this had the same result.

# Answer
I'll present two candidate solutions.

# Solution #1: Associative hashing

Yes. You can associate a hash value with the contents of any binary tree data structure (including a rope). The basic idea is that you augment each node of the tree to store a hash value. The hash for a node is $H(h\_1,\dots,h\_k,x)$ where $h\_1,\dots,h\_k$ are the hashes on its $k$ children and where $x$ is the value stored in the node. In this way, any time you update a node, you can update its hash (and all of its ancestors' hashes) in $O(\log n)$ time. Since all operations take $O(\log n)$ time anyway, this doesn't increase the asymptotic time of the basic tree operations. Now the hash value at the root of the tree summarizes the contents of the entire tree, so can be used as the index into a hash table. Basically, you use that hash value instead of using the address of the object.

You don't need to worry about hash collisions. With a good hash function, hash collisions are sufficiently rare to not be worth worrying about. And if you're using a hashtable, you always have the possibility of hash collisions, so you need a good hash function in any case.

The big shortcoming of this approach is that it doesn't take care of normalization; the hash value reflects both the contents of the nodes as well as the structure of the tree, so if you have two trees with the same contents but with a different structure, they will end up with a different hash value. However, you can fix that up by a clever choice of the hash function. In particular, I suggest you use an *associative hash function*, which is a function $H$ and a binary operation $\cdot$ where $H(x) \cdot H(y) = H(x,y)$. Now you can use $h\_1 \cdot H(x) \cdot h\_2$ as the hash value for a node, where $h\_1,h\_2$ are the hashes of its two children and $x$ is the value stored in this node. In this way the hash value at the root will be equal to what you'd get if you concatenated all of the values at all of the nodes (in infix order), then hashed them. So now the hash value of the tree depends only on the contents of the tree, not on its structure.

Where do you find an associative hash function? They take some cleverness to construct, but one option is to let $H$ denote the $SL\_2(\mathbb{F})$-based hash function in https://crypto.stackexchange.com/a/17936/351 and $\cdot$ represent matrix multiplication.

With this technique, my construction is now normalizing as well, and it should be efficient.

# Solution #2: SeqHash

A possible alternative would be to use the SeqHash data structure from the following paper:

VerSum: Verifiable Computations Over Large Public Logs. Jelle van den Hooff, M. Frans Kaashoek, and Nickolai Zeldovich. CCS 2014.

This data structure lets you store a sequence of characters in a deterministic tree-based data structure. In particular, it provides a hash of the data in the data structure that is normalizing (because the data structure is deterministic). It also provides $O((\log n)^2)$ time insertion, deletion, concatenation, and lookup into the data structure. It's not a rope, but it might be a possible alternative to a rope that meets your interning requirements.

Related: see also Canonical representation of finite maps on non-overlapping finite rational intervals.
> 2 votes

---
Tags: data-structures, strings, search-trees
---


# Question
Title: Variant of the knapsack problem and box stacking
I'm facing a problem described as follows:

You are given a set of $n$ types of rectangular 3-D boxes, where the i-th box has height $h\_i$, width $w\_i$, depth $d\_i$ and value $v\_i$. You want to create a stack of boxes with a height limit $H$ and maximize the sum of the values, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each larger or equal than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. You are also allowed to use multiple instances of the same type of boxes.

I realized that it is a combination of the knapsack problem and the box stacking problem with small variations. I tried to solve it using the knapsack algorithm adding the box stacking restrictions, but I'm not getting the right results. Does anyone know a similar problem or could indicate me an algorithm? I have to implement it using dynamic programming.

# Answer
This is a good dynamic programming exercise. Here's a hint.

> Let $f(i)$ denote the maximum height that can be achieved if you have the $i$th box at the bottom. Can you find a recursive relation to let you compute $f$ in a recursive fashion?

Think about that one. If you get stuck, here's another hint:

> Oops, you'll probably discover that doesn't quite seem to work. What additional information would we like to know about the box at the bottom, to enable you to find a recursive relation? You might need to add an extra parameter to $f$, so it becomes $f(i,\text{something})$ -- what should you put as the "something"?

If you can answer those hints, you should be very close to finding a dynamic programming algorithm for the problem.
> 2 votes

---
Tags: dynamic-programming
---


# Question
Title: NP-complete problem with a polynomial number of yes-instances?
I have the impression that for every NP-complete problem, for infinitely many input sizes $n$, the number of yes-instances over all possible inputs of size $n$, is (at least) exponential in $n$.

Is this true? Can it be proven (probably only under the assumption that $P\neq NP$)? Or can we, maybe artificially, find a problem where for all (large enough) $n$, the number of yes-instances is at most polynomial in $n$?

My reasoning is basically that given a yes-instance for 3-SAT, we can identify the literal in each clause that makes it true and replace another variable in the clause with yet another variable, without changing that it's satisfiable. Since we could do that with each clause, it leads to an exponential number of yes-instances. The same holds for many other problems such as hamiltonian path: we can freely change edges that are not on the path. I then vagely reason that since reducibility is involved where in some way solutions must be kept, it must hold for all NP-complete problems.

It seems also to hold for the maybe NP-intermediate problem of graph isomorphism (where we can freely apply the same changes to both graphs if we know the mapping). I wonder if it also holds for integer factorization.

# Answer
A language with only polynomially many yes-instances is called sparse. Mahaney's theorem states that if any NP-complete language is sparse, then P = NP. Since most people expect that P $\ne$ NP, it seems unlikely that there exists a NP-complete language with only polynomially many yes-instances.

It's a separate question whether the number of yes-instances is exponential. (One could imagine that the number of yes-instances might be more than polynomial but less exponential.) The Berman-Hartmanis conjecture is relevant here; it implies that all NP-complete problems have exponentially many yes-instances. The conjecture remains an open problem.
> 20 votes

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


# Question
Title: Hoare-Logic: Requirements for imperfect data types
Theoretically, Hoare-Logic let's one prove the correctness of an algorithm, given pre- and post-condition.

However, as far as I've seen it so far, one idealizes his data-types to a mathematical set like $\mathbb{N}$ or $\mathbb{R}$.

So, even though the logic might be sound in Hoare-calculus, the discrepancies between the data types used and the data types modeled can still fail the result (e.g. Overflow for Integers).

Therefore, the question is:
Which additional conditions have to be met (after each step of the algorithm?) to accomodate for the imperfect data types actually used?

# Answer
> 3 votes
No, when using Hoare logic properly, you make sure to account for integer overflow etc. and model the full semantics of the programming language.

It *is* possible to use Hoare logic along the lines you suggest, but the problem with that is that it invalidates all guarantees you might have hoped for. Since the whole point of Hoare logic is to obtain guarantees, that seems rather counterproductive.

So if you are using Hoare logic for serious verification, you make sure that the Hoare triples accurately represent all elements of the language semantics, including integer overflow (if relevant). For instance, part of the verification task might be to prove that integer overflow cannot happen; if you don't do that, then the Hoare triples need to account for that possibility.

---
Tags: hoare-logic
---


# Question
Title: Choose minimum subset of edges in tree that connects all important nodes
Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$.

We want to choose subset of edges of the tree such that:

* For each two important nodes at least one edge of the path between them will be choosen
* The sum of the subset of edges will be minimized

Note that we only need to find the sum of the edges in the subset, not the edges in the subset.

For example if we have the tree with the edges $(1, 2) \text{ weight = 3}, (1,3) \text{ weight = 10}$ And our important nodes are: $2, 3$. We should chose only the edge $(1,2)$

# Answer
> 1 votes
Note this is equivalently finding edges with minimum sum of weights such that their removal leaves each important node in a separate component, which is called minimum multiway cut problem.

This problem is NP-hard in general graph, while Chopra, Sunil, and Mendu R. Rao developed a polynomial time algorithm for tree in 1991 \[1\].

---

<sub>\[1\] Chopra, Sunil, and Mendu R. Rao. "On the multiway cut polyhedron." *Networks* 21.1 (1991): 51-89.</sub>

---
Tags: algorithms, graphs, optimization, trees
---


title: How does a Trie work?

text:
# Question
Title: How does a Trie work?
Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree.

The problem though is that after reading everything I think I could read from Wikipedia to blog articles and even Stack Exchange answers I couldn't wrap my head on how this is implemented. Maybe it's simpler than I think but I'm looking at it from the wrong perspective, no idea.

So let's take this HTTP request:

```
GET /hello HTTP/1.1
Host: www.stackoverflow.com
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Accept: */*

```

With a Trie are you going to iterate on GET, then "/" then "hello" then "HTTP" then "1.1" etc until you get to the end of the request with matches or does it work differently than this?

```
               root
           /  /   \  \
         GET POST PUT DELETE
         /
       "/"
       ...
       /
    "HTTP"
      /
     "1"
     /  \
   "0" "1"

```

I have a hunch that that's not exactly the case because it has the potential to lock a loop or function where it's executed in, or waste resources if event'ed. Given the fact that this solution is considered when the HTTP routing itself becomes a problem it must work differently?

# Answer
At it's core a trie is a tree-shaped deterministic finite state machine (no loops, no merges). They work best when you have a preset number of keywords to search for.

The root is the start state and the leaves are all final states but each with its own action.

However for parsing the http optimally one wouldn't use a pure trie. BEcause the input is mostly freeform you are better off using a custom state machine.
> 2 votes

# Answer
A trie is the complete decision tree, character after character, corresponding to the acceptance of a string among a set of strings.

For instance for the set `{abc, aa, cdf}`, the root node accepts `{a, c}`. Then the son `a` accepts `{a, b}` and the son `c` accepts `{d}`. And so on.

In the simplest implementation, the sons of a node are linked to by an array of pointers (one per character in the alphabet). So this representation is heavy, but extremely efficient in terms of running time.
> 0 votes

---
Tags: data-structures, trees, information-retrieval
---


# Question
Title: Sub-Graph Isomorphism for graphs with multiple edge types and multiple node types
I found that there are algorithms like VFlib and LAD filtering for subgraph isomorphism with one edge type. For multiple node types,one idea could be color all node types with the same type and use colored sub-graph isomorphism which is available for VFlib. I was wondering is there any algo specifically for multiple edge types or should I modify existing algo to check for edge types also?

# Answer
> 1 votes
You can replace each edge $(u,v)$ with two edges $(u,t\_0)$ and $(t\_0,v)$ where $t\_0$ is a new vertex (a different one for each edge you replace), and then color the vertex $t\_0$ based on the type of the edge $(u,v)$.

---
Tags: graph-isomorphism
---


# Question
Title: Generate numeric or string ID for a sequence of elements
How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter.

Example:
`[41,1001,32]` should generate the same ID as `[32,1001,41]`
`[41,1001,32, 5]` should be different.

Elements could be hundreds where each individual ID can be a 4/5-digit number.

I thought about sorting, concatenate and Hash/Compress the string, but are there gonna be a lot of collisions ?

Any ideas would be much appreciated.

# Answer
> 2 votes
If you don't care about the length of the id, sort the list and use that as the id.

If you do care about its length, sort the list and then use the SHA256 hash of the sorted list as the id. It is believed to be infeasible to find collisions for SHA256, so you shouldn't have to worry about collisions. If you find one, publish it and you'll be famous (briefly).

---
Tags: data-compression, pseudo-random-generators, hashing
---


# Question
Title: Modified Counting Inversions problem using divide and conquer
> Given an array $A$, find the number of pairs $(i, j)$, such that $ i \> j$ and $A\[i\] \ge A\[j\]$.

This is a modified version of the famous problem of *Counting Inversions*, only in this version it allows the elements to be equal as well. I have an algorithm for the classical counting inversions problem implemented, so i´d like to know if it can be adapted to solve this version. Thanks ahead.

Link to the algorithm (written in C++):

https://repl.it/@MateusBuarque/CountingInversion

# Answer
> 1 votes
Hint:

> Can you count the number of pairs $(i,j)$ such that $A\[i\]=A\[j\]$?

---
Tags: algorithms, arrays, counting
---


# Question
Title: sequence of problems that take $\Theta(n^k)$ for increasing $k$?
Do we know an infinite sequence of decision problems where the most efficient algorithm for each problem takes $\Theta(n^k)$ time, where $k$ increases unboundedly?

Suppose for example that we would know that finding a k-clique takes $\Theta(n^k)$, then this sequence could be {1-clique, 2-clique, 3-clique, ...}. However, perhaps there are more efficient algorithms for k-clique, so this answer is incorrect.

EDIT:

* By the Time Hierarchy Theorem (which includes "P does not collapse to DTIME($n^k$) for any fixed $k$"), such a sequence should exist.
* After some discussions in the comments, common NP problems are not good candidates. If it takes only $O(n)$ time to check a certificate (or $O(n^c)$, where $c$ is a constant independent of $k$), it would imply that $P\neq NP$

# Answer
You leave the computational model open. I will assume that the question refers to random access machines (RAMs), as that is customary when one asks for the actual exponent in polynomial time.

Let $P\_k$ be the set of (encodings of) RAMs $M$, such that $M$ halts in at most $|M|^k$ steps using at most the initial $|M|^k$ memory cells. A universal RAM can solve $P\_k$ in $O(n^k)$.

On the other hand, $P\_k$ is the universal problem for $DTIME(n^k)$ (in the RAM model and under linear time reductions). As a special case of the RAM version of the time hierachy theorem, a simple diagonalization shows that all algorithms for $P\_k$ have running time $\Omega(n^k)$. Thus the complexity of $P\_k$ is $\Theta(n^k)$ as asked.

The tightness heavily relies on the computational model. The Turing machine version of the time hierarchy theorem has a $\log n$ gap. Let $P'\_k$ be the set of (encodings of) Turing machines $M$, such that $M$ halts in at most $\frac{|M|^k}{\log n}$ steps. Then $P'\_k$ can be solved in $n^k$ time by a universal Turing machine and all algorithms have running time $\Omega(\frac{n^k}{\log n})$. I suspect this is the best one can do.

\[EDIT\]

In a comment, you ask for more *conventional* problems, like graph problems or logic.

First, let me point out how $k$-Clique (as suggested in the answer) does not seem like a good candidate. If we could prove that $k$-Clique requires time $\Omega(n^k)$ (or $\Omega(n^{f(k)})$ for some unbounded $f$), we have implied that Clique is not in P. And thus that P is different from NP. That is not likely to be easy. The same holds for slices of any other problem that we know to be in NP, or in some other classes like PSPACE that are unknown to be different from P.

Every problem can be rephrased as a graph problem, by encoding the input as a graph. I don't know if you would call a graph version of $P\_k$ conventional. I wouldn't call it natural.

As for logic, I can provide an example. It is not boolean logic however, and there is a gap between the lower and upper bound. The example is based on the Immerman-Vardi theorem. Let $\mathcal L$ be first-order logic extended by least-fixed-point operators. Let ${\mathcal L}^k$ denote the fragment where only $k$ first-order variables are allowed. It is permitted to re-use variables, so the restriction is that each subformula has at most $k$ free variables. The Problem $M\_k$ is the model-checking problem for ${\mathcal L}^k$, that is on input of a formula $\varphi\in{\mathcal L}^k$ and a structure $\mathfrak A$ of matching vocabulary, the task is to decide whether $\mathfrak A\models\varphi$, that is whether $\varphi$ is true in $\mathfrak A$.

$M\_k$ can be solved in time $O(n^{2k+1})$. On the other hand, for some constant $c$, $M\_{3k+c}$ is hard for $DTIME(n^k)$ (where we also require an $n^k$ bound on the contents of memory cells). I believe $c=2$ suffices. From diagonalization we obtain that $M\_{3k+c}$ requires time $\Omega(n^k)$, so $M\_k$ requires time $\Omega(n^{\frac{k-c}3})$. The bound is not tight in the sense of $\Theta(n^{k'})$ for some $k'$, but at least we have $n^{\Theta(k)}$.
> 3 votes

---
Tags: complexity-theory, decision-problem, polynomial-time
---


# Question
Title: Number of calls with length 2 array in quick-sort
I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion:

$$T\_N = \frac{1}{N}\sum\_{k=1}^N\left(T\_{k-1}+N\_{N-k}\right) = \frac{N+1}{N}T\_{N-1} = \frac{N+1}{3}.$$

Where $T\_0 = T\_1 = 0, T\_2 = 1$. But:

\begin{align\*} T\_3 &= 1/3(1 + 1) &= 2/3\\ T\_4 &= 1/4(2/3 + 1 + 1 + 2/3) &= 5/6\\ T\_5 &= 1/5 (5/4 + 2/3 + 2 + 2/3 + 5/4) &= 7/6\\ T\_6 &= 1/6(7/6 + 5/6 + (1+2/3) + (1+2/3) + 5/6 + 7/6) &= 11/9 \end{align\*}

The results are different. How to do it right?

EDIT: The code for quick-sort in question is:

```
void quicksort(int[] a, int lo, int hi)
{
  if (hi <= lo) return;
  int i = lo-1, j = hi;
  int t, v = a[hi];
  while (true) {
    while (a[++i] < v) ;
    while (v < a[--j]) if (j == lo) break;
    if (i >= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
  }
  t = a[i]; a[i] = a[hi]; a[hi] = t;
  quicksort(a, lo, i-1);
  quicksort(a, i+1, hi);
}

```

# Answer
> 1 votes
First, note that you can write your recurrence as $$ T\_N = \frac{2}{N}\sum\_{i=0}^{N-1} T\_i. $$ Consider now the generating function $$ T(x) = \sum\_{N=0}^\infty T\_N x^N. $$ We calculate $$ \frac{T(x)}{1-x} = \sum\_{N=0}^\infty \sum\_{i=0}^N T\_i x^N = \frac{1}{2} \sum\_{N=2}^\infty (N+1)T\_{N+1}x^N = \frac{1}{2} \sum\_{N=3}^\infty NT\_Nx^{N-1}. $$ On the other hand, $$ \frac{d}{dx} T(x) = \sum\_{N=0}^\infty NT\_Nx^{n-1}. $$ We conclude that $T(x)$ satisfies the differential equation $$ \frac{d}{dx} T(x) = \frac{2T(x)}{1-x} + 2x. $$ Additionally, $T(0) = 0$. Plugging this into Wolfram alpha, we obtain the solution $$ T(x) = \frac{x^2(3x^2-8x+6)}{6(1-x)^2}. $$ Using $1/(1-x)^2 = \sum\_{N=0}^\infty (N+1)x^N$, we obtain for $N \geq 3$ that $$ T\_N = \frac{6(N-1)-8(N-2)+3(N-3)}{6} = \frac{N+1}{6}. $$

---

Having computed the solution by brute force, it is easy to prove by induction. Suppose that $N \geq 3$. Then $$ T\_N = \frac{2}{N} \sum\_{i=0}^{N-1} T\_i = \frac{2}{N} \left(1 + \sum\_{i=3}^{N-1} \frac{i+1}{6}\right) = \frac{2}{N} \left(1 + \frac{(N-3)(N+4)}{12} \right) = \frac{N+1}{6}. $$

---
Tags: recursion, quicksort
---


title: From $P=NP$ to $NP=NL$

text:
# Question
Title: From $P=NP$ to $NP=NL$
Does $P=NP$ implies $3SAT$ reduces to $2SAT$?

If so then from $2SAT$ is $NL$-complete can we conclude $NP=NL$?

# Answer
> 1 votes
Yes and no.

If P=NP, then every problem in NP, in particular 3SAT, can be solved in polynomial time. Hence it reduces to every nontrivial problem (and 2SAT is nontrivial) using polynomial time reductions. Which are the reductions in the definition of NP-hardness.

NL, on the other hand, is not closed under polynomial time reductions (unless NL=P), as these can use polynomial space (exceeding logarithmic space). That is why for the definition of NL-hardness, logspace reductions are used. Hence neither can we conclude that 3SAT is in NL, nor that NL=NP.

# Answer
> 0 votes
Such implication is currently unknown.

One immediate consequence of $\mathsf{P=NP\Rightarrow NL=NP}$ is that $\mathsf{P\neq PSPACE}$ unconditionally, since otherwise you have $\mathsf{NL=P=NP=PSPACE}$, contradicting the space hierarchy theorem. Note that in order to conclude $\mathsf{NP=NL}$ from a reduction between 3SAT and 2SAT, the reduction has to be limited to logarithmic space.

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


# Question
Title: Construct a grammar over {$a,b$} whose language is {${a^mb^ia^n | i = m+n}$}
I am a little confused on how to approach this problem. I am unsure how to construct both parts of the grammar using a context-free grammar.

This is as far as I got, but this will end up producing a's inside of the group of b's and a's. I'm not sure how to add the second group of a's to the right of the b's.

$S \rightarrow aSb \ | \ A$

$A \rightarrow bAa \ | \ λ$

This language should produce strings like

$abba, aabbba, aaaabbbbbbaa$

# Answer
You must handle aXb and bYa sequences seperately.
$\\S \rightarrow \ XY\ |\ \epsilon \ \\ X\rightarrow \ aXb\ | \ \epsilon \\ Y\rightarrow \ bYa\ | \ \epsilon$
> 0 votes

---
Tags: context-free
---


title: Simple majority classifier question

text:
# Question
Title: Simple majority classifier question
one of my training questions for my exam is the following one:

> Suppose you are testing a new algorithm on a data set consisting of 100 positive and 100 negative examples. You plan to use leave-one-out cross-validation (i.e. 200-fold cross-validation) and compare your algorithm to a baseline function, a simple majority classifier. Given a set of training data, the majority classifier always outputs the class that is in the majority in the training set, regardless of the input. You expect the majority classifier to achieve about 50% classification accuracy, but to your surprise, it scores zero every time. Why?

My only solution about it is that the training data is inverse to the real data. But I'm not sure about my answer. May anybody help me?

Regards,

Patrick

# Answer
> 1 votes
You have 100 examples of the positive class and 100 examples of the negative class.

Now you do:

```
examples = "List of all 200 examples"
accuracies = Empty list
for(i=0; i<|examples|; i++) {
    one = examples[i]
    training = examples \ {one}

    # !!!!!!!!!!!!!!!!!!!!!!!!!
    majority_clf = get majority in training. This is the other class than the class of "one"
    # !!!!!!!!!!!!!!!!!!!!!!

    accuracies.append(majority_clf.predict(one) == class(one))
}
overall_accuracy = sum(accuracies) / |accuracies|

```

# Answer
> 0 votes
Let me try to answer this question with a dummy example that might help you build the intuition. Lets say we have a set of data in the form (xi, yi) with just 10 rows. 5 rows are labeled as 1 and the other ones as 0. Just like in the exercise.

Now, on LOOCV we must extract the first (x1, y1) as the test set and leave the rest as the training set. Assuming that y1 = 1, this means that in this iteration, the training set will have more classes if type yi = 0 than yi = 1, because we took one yi = 1 and we placed it as the test set.

for this iteration, the Majority classifier will be a zero (0) while the test set will be a one (1). They will always be different!

If we run all the "n" iterations, the LOOCV we will have basically the same problem where the test set != majority classifier, in every case, causing the final performance score to be zero (between the LOOCV and the majority classifier). because they will never match.

Hope this helps.

---
Tags: machine-learning, classification
---


# Question
Title: How do you proceed if your milp is not solvable
We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical).

We went with a very simple aproach (make a cube person x visit x Time and add constraints from here on). Our solution works well if the problem is solvable.

Our customer needs a solution with alternative options if the problem is not solvable, for example "here is a possible solution with X more people" or "a solution with 2 hours more worktime".

Our initial thoughts were to extend our people / time cube by a given number of cells and then add high penalty values to our goal function for these values.

Does anyone have a better idea / knows what is common practice?

# Answer
> 4 votes
It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following:

# Precision

Typical solvers report solutions as "optimal" using gap parameters specifying relative and absolute differences. Take this CPLEX parameter as an example: https://www.ibm.com/support/knowledgecenter/SSSA5P\_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html

You can use this in two ways:

### Sanity tests

If you don't know if your problem is solvable in practice, i.e., constraints are not contradictory in a non-obvious way, just set the precision to lowest possible value and try to solve the problem. The solver should just find anything meeting the constraints practically ignoring the cost function.

Next, when you know that the problem is solvable, you can tighten the constraints. In your example you mention the number of people, first you can start with $x+10$ and if it works you then decrease it to $x+5$ and so on. By doing so you can easily estimate which set of parameters and constraints you can further optimize.

### Practical precision

The question is whether you need the highest possible precision or maybe you can bend the rules and consider using less "optimal" solution. This can highly speed up the calculations, i.e., in my problems I was able to find the solution in seconds instead of hours by switching gap from $0.0001$ to $0.01$ in Gurobi.

# Hard constraints and soft constraints

Common approach is to change some of the constraints to constraints with penalty. For instance, instead of saying that $x \< 10$ you say that $x - p \< 10$ where $p \ge 0$. Next, you add $p$ to your cost function with big negative multiplier. Such a variable splitting can help finding solutions in case of infeasibility, what's more, if you report the solutions during calculations you can use them to get better approximations of the constraints you can drop to get better results. It looks like this is something you already considered and this is a common approach.

# Presolve

Depending on the type of your problem, you may be able to divide it into multiple phases and calculate the solutions in parallel. Using this method with "sanity tests" method mentioned above you can still have some solution in case when your most wanted model is not feasible.

Example: if you are optimizing for two "realms" (like number of people and number of tasks), try to set some value manually and optimize the other value for that case. By doing this you make the model much easier so you can calculate multiple of them.

# Simplify the model

It sounds easy but in fact can be very hard. Make sure that you don't perform unnecessary difficult operations (like calculating GCD or multiplying variables). Look for easier formulations including constraints moved to cost function (i.e, instead of calculating the minimum of a set and them maximizing it with the cost function, use min-max trick). Make sure that you have smallest possible domains (especially for so-called "big $M$" variables). Also, check your floating point precision.

# Just deal with it

Sometimes you just can't mitigate it, after all it might not be solvable in any acceptable time. You can consider calculating different problem (i.e., completely different approach) or use different algorithm at all (neural nets, simulated annealing etc).

---
Tags: linear-programming, integer-programming, constraint-programming
---


# Question
Title: predication execution, branch prediction
Below is a paragraph from a book.

> In an ordinary superscalar processor, we would use branch prediction to guess which of the given instructions is to be executed, and go down that path. If the processor guesses wrong, the pipeline must be flushed.
>
> Predication execute all of instructions and once the values of the predicate registers are known, commit only the results of the valid instructions. Thus we make use of additional parallel execution units to avoid the delays due to pipeline flushing.

So each predication and branch prediction has disadvantage each. For predication, we have to WAIT until the values of the predicate registers are known. For branch prediction, if prediction is wrong, the pipeline must be flushed which will cause a DELAY. Seems like both predication and branch prediction needs delay.. But to me.. prediction has a chance to avoid delays when prediction is correct leading to conclusion that prediction is better..Predication always needs waiting.

So how do I tell which one is better?? Under what circumstance should I use predication and branch prediction?

Thank you in advance.

# Answer
The quote from the book doesn't describe how predicated instructions work today. It says that predicated instructions are "executed but only committed if the condition is true". But that would be exactly what branch prediction does, and would lead to exactly the same problems.

Instead, a predicated instruction is implemented as an ordinary instruction which just has one more input. It is *always* executed and *always* committed, just the effect of the instruction depends on a condition flag. That means all the mechanism to accelerate execution, out of order execution etc. can be used.
> 1 votes

# Answer
That's not how it works. Modern processors use branch prediction regardless; it's not something you get to choose. When you write a program in assembly language, you get to choose whether to use predicated instructions or not, but branch prediction is not something you choose to use or not use.

Whether it's faster to implement a specific algorithm using predicated instructions or with conditional jumps depends on the specific algorithm and code and architecture. Usually the only way to tell is to try both and measure their performance on a realistic benchmark. It's certainly not something where there is a general answer; it all depends.
> 0 votes

---
Tags: cpu, cpu-pipelines
---


# Question
Title: if traveling salesman problem is decidable in polynomial time, can an actual solution be proposed in polynomial time?
I'm asking because it seems that P problems refer to decision problems rather than actually propose a solution.

# Answer
If you have available a TSP decision oracle -- that is, a function that answers questions of the form "Does directed graph $G$ have a TSP tour of length at most $k$?" in constant time -- then the following algorithm will allow you to construct an actual TSP tour using $O(|E|)$ calls to the oracle, and $O(|E|^2)$ time overall:

1. Run a binary search on $k$, calling the decision oracle at each step, to determine $OPT$, the minimal tour length of the original graph $G$. (If necessary, the absence of any Hamiltonian cycle at all can be first tested for by calling the oracle with a very large threshold -- e.g., equal to the sum of all edge weights.)
2. If $G$ contains 3 or fewer edges, then stop. (These must form a triangle.)
3. Choose an arbitrary vertex $u$ in $G$.
4. For each out-edge $uv$ in $G$:
    * Create a new graph $G'$, which is the same as $G$ except that the edge $uv$ has been collapsed (specifically: delete vertices $u$ and $v$ and all edges they are incident on, and create a new vertex $x$ that has all of $u$'s incoming edges and all of $v$'s outgoing edges).
    * Run the decision oracle on $G'$ with the length threshold $OPT-w(uv)$.
    * If the answer is YES, then some optimal solution to $G$ contains the edge $uv$: Replace $G$ with $G'$ and $OPT$ with $OPT-w(uv)$ and go to 2.
    * If the answer is NO, then no optimal solution to $G$ contains the edge $uv$: Delete $uv$ from $G$, and continue iterating through other out-edges of $u$ in $G$.

The iterations in the loop beginning at step 4 execute at most $|E|-3$ times. How quickly the graph modification steps (edge collapsing, edge deletion) in each iteration can be performed probably depends on the graph representation used, but they can certainly be done in $O(|E|)$ time each, for $O(|E|^2)$ time overall, which is enough to show the algorithm is polynomial. (Can anyone think of faster $O(|V|)$ or even $O(|1|)$ ways to perform these modifications?)

The above runs on a *directed* graph $G$. If you have an undirected graph, you can first turn each undirected edge into a pair of opposite-facing directed edges having the same weight, and then run the algorithm as before.
> 3 votes

# Answer
Optimization version and decision version could be exchanged (binary search). That's why only decision version is studied.
> 0 votes

---
Tags: complexity-theory, p-vs-np, traveling-salesman
---


title: Virtual Memory and processes

text:
# Question
Title: Virtual Memory and processes
In a Operating System, who decides which parts of a program (or task) has to be stored in the virtual memory and which in the RAM ?

# Answer
> 1 votes
The application itself gets to decide what it wants in virtual memory (within some restrictions). By default that will be the code it run and the memory it uses. The application can also request files to be mapped into memory, or that memory gets shared with another application.

Then the kernel will decide which parts of virtual memory are loaded in RAM based on various factors like: how much ram is available; how much is needed by other processes; how recently a region of virtual memory was accessed, ...

---
Tags: operating-systems, memory-management
---


# Question
Title: Pascal FOR loop with context free gramar
In Pascal For-do loops, there is a rule stating that one cannot modify the counter variable inside the body of the loop.

To exemplify the rule, take the following Pascal `for-do`, which **is not valid**, since the counter variable is being modified inside the loop's body:

```
for i := 0 to 10 do i := i + 1;

```

My question is: *Is possible to express this rule using context-free grammars?*

# Answer
The answer depends on how you represent variables.

* If there are an infinite number of variable names, the answer is no.
* If there are a finite number of variable names, the answer is "yes but you never would in practice".

Here's some informal arguments for that:

For the first case, there must be some set of non-terminals which represent valid loop bodies. And for each variable, there must be a non-terminal where you can refer to that variable, and one where you can't. Because of loop nesting, this must be true for any combination of any number of variables i.e. we need a distinct non-terminal for each of an infinite combinations of allowed and not allowed variables.

But, then we have an infinite number of non-terminals, which is not allowed in a context-free grammar.

This is basically because of the "context free" part of CFG. Knowing which variables are allowed and aren't is context, which our grammars are free of.

In the case of a finite number of allowed variables, you basically model it like I said above, with a different non-terminal for each combination of variables. So in terms of computability/expressibility, you you *can* do it with a context free grammar, in the same way you *can* model your computer and its 8GB of RAM with a finite automaton. Doing so will explode quickly, and it's not the way you want to do things.
> 7 votes

# Answer
The task of a context free grammar is to generate valid strings that are in a context free language. Context free languages, being 'context free', are generally used in syntax analysis part of compilers. It's just out of their scope to check for semantics.

Consider an analogy with English language, the statement "He is a girl", is completely valid in terms of syntax,(Pronoun-verb-noun is a valid English construct), however it does not make any sense semantically.

Such cases are out of scope or power of context free grammars which is why context sensitive grammars(and even more complex grammars exist).
> 1 votes

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


title: Allocating memory via Buddy Allocation

text:
# Question
Title: Allocating memory via Buddy Allocation
I'm trying to learn buddy allocation and whilst I think I understand the basics of it, there is one problem exercise with which I'm struggling with.

So I have an 8K block and I'm using buddy allocation trying to always allocate to the **leftmost** free memory area.. and I need to allocate a 5K memory block.

Do I split the 4K block into two 2K blocks, and take (from the left) the 1k, 2k, 2k blocks, or do I split the middle 2k block into two 1k blocks and take the 4k and the first 1k block from the right? Or do i simply take the 2k and 4k blocks that I have now?

Or is this type of allocation simply not possible if I need to make use of the whole 8k block (since the first 1k block is being used)?

# Answer
None of the above. First, block sizes are rounded up to the nearest power of 2. If you try to allocate an object of length 5K, it will first round that up to 8K. Next, it will try to find a free block of size 8K. In your example, you'll need to look at larger blocks -- the 1K, 2K, and 4K blocks are too small. You'd better hope there is another 8K block (not shown) that is free, or an even larger block that is free and can be split up to create a 8K block.
> 0 votes

---
Tags: memory-allocation
---


title: Why is this function computable

text:
# Question
Title: Why is this function computable
I'm struggling to understand why this function is computable. This is the requirement:

Consider the following program P, written in a pseudo-C language:

```
P:
{
    int x, y, z;
    read (x, y, z);
    while (x != y)
    {
       x = x - y;
       z = z + y;
    }
    write z;
}

```

Let $f(x, y, z)$ be the function computed by P. Is the following function g computable?

$g(x, y, z) = \begin{cases} 1 & f(x,y,z)\ halts \\ 0 & else \end{cases} $

Whenever I encounter a problem like this, I try to imagine a program that does exactly what $g$ does. In this case, a `P2` program that checks if $f(x,y,z)$ halts.

Now, P halts if, basically, $x\>y \ and \ y=1 $ or $x=y$ (there are probably more cases). In the other cases, P would just remain in the `while` loop, so $f$ is **not total**.

But how would `P2` return $0$ if P wouldn't even halt? P2 would have to wait, and never return 0, so for some values the function is not computable, and x,y,z isn't always computable.

What am I *thinking* wrong here?

# Answer
You can check that P halts iff $x = ty$ for some integer $t \geq 1$. Hence $g(x,y,z)$ is just the following function: $$ g(x,y,z) = \begin{cases} 1 & \text{ if $x = ty$ for some integer $t \geq 1$}, \\ 0 & \text{ otherwise.} \end{cases} $$ Given integers $x,y$, it is not hard to check whether $x = ty$ for some integer $t \geq 1$. Hence $g$ is computable (even in polynomial time!).
> 3 votes

---
Tags: computability
---


# Question
Title: Finding the length of the longest increasing path in a matrix
**Problem:**

Given a matrix, find the length of the longest increasing path. We can move up, down, left, or right.

**Example:**

$$ \begin{pmatrix} 1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7 \end{pmatrix} $$

Output: 7

Longest path is 1, 2, 3, 4, 5, 6, 7

**Question:**

I am not sure if this post is relevant to this site. I having some trouble coming up with a system to solve this problem. I am not too advanced with programming, I am more of a mathematician by trade but I know some stuff about data structure and algorithms.

If possible, an ideal answer for me would be a step by step guide in solving this problem. My initial thought was to find the smallest number in the $(i, j)$ position and start with the first $(i,j)$ position that was found. Then check up, down, left, right to see which number is larger. But then I thought okay what if there are more than 1 position that is larger? I am pretty stuck with this so any help would be useful.

I found solutions to this online but reading other peoples code is nauseating and I don't find it useful at all.

# Answer
Here is an $O(nm \log nm)$ solution, where $n,m$ are the dimensions of the matrix. Later we improve it to an optimal $O(nm)$ solution.

Let $A\[i\_1j\_1\],\ldots,A\[i\_{nm}j\_{nm}\]$ be the entries of $A$ in non-decreasing order; the indices $i\_tj\_t$ can be computed in time $O(nm\log nm)$. We will compute a new matrix $B$ with the same dimensions such that $B\[ij\]$ is the length of the longest increasing part ending at $A\[ij\]$. We compute the entries of $B$ in the order $B\[i\_1j\_1\],\ldots,B\[i\_{nm}j\_{nm}\]$, using the formula $$ B\[ij\] = 1 + \max\_{\substack{i'j' \sim ij \\ A\[i'j'\] \< A\[ij\]}} B\[i'j'\], $$ where $i'j' \sim ij$ means that $A\[i'j'\]$ is a neighbor of $A\[ij\]$, and we set $B\[ij\] = 1$ if the maximum is over the empty set.

The answer is simply the maximum entry of $B$. You can find an actual longest increasing sequence by starting with a maximum entry of $B$, say equal to $\ell$, finding a neighbor equal to $\ell-1$, then a neighbor equal to $\ell-2$, and so on until hitting a neighbor equal to $1$. This gives you a longest increasing sequence in reverse order.

As an example, consider your matrix $$ A = \begin{pmatrix} 1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7 \end{pmatrix}. $$ We can order the entries as follows (there are many possible orders, since the entries are not distinct): $$ A\[1,1\],A\[1,2\],A\[2,1\],A\[2,2\],A\[3,2\],A\[1,3\],A\[2,3\],A\[3,1\],\\A\[3,3\],A\[1,4\],A\[2,4\],A\[3,4\],A\[4,1\],A\[4,2\],A\[4,3\],A\[4,4\]. $$ We now compute $B$ in the same order: $$ \begin{pmatrix} 1& & & \\ & & & \\ & & & \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2& & \\ & & & \\ & & & \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2& & \\ 2& & & \\ & & & \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2& & \\ 2&1& & \\ & & & \\ & & & \end{pmatrix}, \\ \begin{pmatrix} 1&2& & \\ 2&1& & \\ &1& & \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2&3& \\ 2&1& & \\ &1& & \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2&3& \\ 2&1&2& \\ &1& & \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2&3& \\ 2&1&2& \\ 3&1& & \\ & & & \end{pmatrix}, \\ \begin{pmatrix} 1&2&3& \\ 2&1&2& \\ 3&1&3& \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2&3&4\\ 2&1&2& \\ 3&1&3& \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2&3&4\\ 2&1&2&3\\ 3&1&3& \\ & & & \end{pmatrix}, \begin{pmatrix} 1&2&3&4\\ 2&1&2&3\\ 3&1&3&4\\ & & & \end{pmatrix}, \\ \begin{pmatrix} 1&2&3&4\\ 2&1&2&3\\ 3&1&3&4\\ 4& & & \end{pmatrix}, \begin{pmatrix} 1&2&3&4\\ 2&1&2&3\\ 3&1&3&4\\ 4&5& & \end{pmatrix}, \begin{pmatrix} 1&2&3&4\\ 2&1&2&3\\ 3&1&3&4\\ 4&5&6& \end{pmatrix}, \begin{pmatrix} 1&2&3&4\\ 2&1&2&3\\ 3&1&3&4\\ 4&5&6&7 \end{pmatrix}. $$ We conclude that the answer is $7$. Retracing our steps, we highlight the following path in $B$, which corresponds to the longest increasing sequence in $A$ (accidentally, having exactly the same values): $$ \begin{pmatrix} 1& & & \\ 2& & & \\ 3& & & \\ 4&5&6&7 \end{pmatrix}. $$

---

We can implement essentially the same solution in time $O(nm)$ using DFS. We go over the entries of $B$ in some arbitrary order, attempting to use the same recurrence formula we had before: $$ B\[ij\] = 1 + \max\_{\substack{i'j' \sim ij \\ A\[i'j'\] \< A\[ij\]}} B\[i'j'\]. $$ If we are trying to access an entry $B\[i'j'\]$ which hasn't already been computed we compute it recursively. Conversely, once an entry $B\[ij\]$ has been computed, there is no need to compute it again.

This can be implemented using the following pseudocode:

```
compute-B-matrix:
  initialize B to be empty
  for 1 <= i <= n and 1 <= j <= m:
     if B[i,j] is empty, call compute-entry(i,j)

compute-entry(i,j):
  let S = { neighbors (i',j') of (i,j) such that A[i',j'] < A[i,j] }
  if S is empty:
     set B[i,j] = 1
  if S is non-empty:
    for every (i',j') in S:
      if B[i',j'] is empty, call compute-entry(i',j')
    set B[i,j] = 1 + max({ B[i',j'] : (i',j') in S })

```

This solution essentially amounts to computing a topological ordering of a digraph naturally associated with $A$. Details left to the reader.
> 2 votes

---
Tags: algorithms, data-structures, dynamic-programming
---


title: Imaginary numbers and negative zero

text:
# Question
Title: Imaginary numbers and negative zero
I've been studying the low-level hardware implementations of floating point numbers and doing an exercise to design a custom floating point implementation.

I know that being able to represent negative zero is important for some purposes, but ran across a curious question.

Complex numbers are generally represented by two fp numbers. Is there any use in being able to represent negative zero on the imaginary line? Does anybody use this for anything?

# Answer
Yes, there is a usage for the negative imaginary zero. But first, I will say something about the negative zero in general.

## Why have a negative zero?

First of all, the main reason to have a signed zero for floating points is that floating points have only limited precision and we often want to distinguish the following cases of a real number $x$, represented by a floating point:

* $x\geq 0$, which we will denote by $+0$.
* $x\<0$, which we will denoted by $-0$.

As we cannot distinguish between these cases ordinarily in our floating point representation when $|x|$ is smaller than the floating point precision, we need a special notation for this. We want to distinguish between these two almost $0$ numbers, as this difference can be 'enlarged' with the appropriate function: when we have defined $1/0=\infty$ (we work with the extended reals) we have $+0={-0}$, but $1/{-0}={-\infty}\neq +\infty = 1/{+0}$.

## The negative imaginary zero

For the following, consider a complex number $z=x+i\cdot y$, with $x$ the *real part* and $y$ the *imaginary part*, represented by a floating point for $x$ and another floating point for $y$.

One important application where we want to distinguish between $-0$ and $+0$ is when computing the inverse elementary functions (i.e. $\ln(z), \sqrt{z}, \arcsin(z)$) for the complex numbers. All these functions are defined in terms of $\ln(z)$, the complex logarithm.

I won't go into the details why, but this function is discontinuous on the whole negative real number line: $\ln(x + i\cdot +0)\neq \ln(x+i\cdot{-0})$ for all $x\leq 0$, this is half-line known as the *branch cut* of the complex logarithm. (Note that we also want to know the sign of $x$ here to see whether are 'on' this line in the first place!)

For example, we have $-4+i0 = -4 - i0$, but $2i=\sqrt{-4+i0 }\neq \sqrt{-4-i0}=-2i$. So, we need to distinguishing between $+i0$ and $-i0$ to know on which 'side' of the branch cut we are to compute the complex logarithm $\ln(x)$ and all other inverses of elementary functions defined from it. For more on this topic, see these notes by Prof. W. Kahan.
> 6 votes

---
Tags: floating-point, number-formats
---


# Question
Title: How do computers synchronize their clocks with the standard time
I'd like to know how clock synchronization is done on computers, I've read this wikipedia article however it didn't give me exactly what I was looking for, I'll outline the problem I'd like answered:

My computer has the current time stored inside it which is maintained by a clock however this clock is subject to clock drift so it is nessisary to synchronize my computers time occasionally. Say my computer would like to do such a synchronization, then it would need to make a request to some time keeping server. This server would then respond to my computer with the correct time however there would be an inaccuracy due to the fact that the servers response would not be received immediately. My computer could attempt to estimate the travel time for the response however this is bound to be inaccurate. For this reason I suspect that GPS is used to synchronize time on computers. I'd imagine this is done by having the computer receive the time directly from the satellite and synchronize based on that.

I'd like to know if this is correct, if not, how is time synchronization done? Thanks

# Answer
> 4 votes
The Network Time Protocol (NTP) uses a rather simple basis, it assumes that the roundtrip time is divided equally between up and down delays after server processing is subtracted.

NTP keeps 4 timestamps per poll: client send $t\_0$, server receive $t\_1$, server send $t\_2$ and client receive $t\_3$. Server timestamps being in the server's clock and client timestamps being in the client's clock (that possibly needs adjusting).

Then the offset from one clock to the other is

$$\theta = \frac{(t\_1-t\_0)+(t\_2-t\_3)}{2}$$

The client will do statistical analysis to average out the delta and filter out outliers (filtering out excessive roundtrips for example) before adjusting the clock.

It is possible to use GPS to synchronize

---
Tags: clocks
---


title: Optimal data structure for sorted list

text:
# Question
Title: Optimal data structure for sorted list
Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)".

Even though B-trees are a generalization of BSTs, I have not seen much of anything say they are used to create ordered data structures. Wondering if programming languages could/should B-plus trees to create a sorted array, or does it use BSTs. So part of the question is, can B-trees, and B-plus trees be used to create associative arrays and sorted arrays and other list data structures (or should they). The other part of the question is which data structure is optimal for all three sorted list operations (search, insert, delete).

I have heard of skip lists as well, but don't understand them yet. I haven't implemented any sort of BST so I don't have a great deal of knowledge about them but I roughly understand how they work. I have read B-plus trees are best for disk storage solutions (not sure exactly why) because high fanout / low depth. But I am more wondering for purely in-memory sorted arrays, what is the optimal data structure for maintaining it:

* Binary Search Tree
* Red-Black Tree
* B-Tree
* B-Plus Tree
* Skip list
* Other

# Answer
> 3 votes
Yes, B-trees and B+ trees can be used to create a sorted array or other ordered data structure.

There is no one data structure that we can call "optimal". There are a variety of data structures that have various tradeoffs. Their performance has some similarities, and which one you choose depends on the specific situation (whether you want an in-memory data structure or an on-disk data structure, how important ease of programming is, how important worst-case vs average-case performance is, and many other considerations). So, I would be reluctant to pick any one of them as "optimal".

---
Tags: data-structures, trees, search-trees
---


title: How to prove Landauer's principle

text:
# Question
Title: How to prove Landauer's principle
I have some questions about energy emitted when one bit of information is processed.

Landauer's principle states the minimum possible amount of energy required to erase one bit of information is `k T ln2` Considering this,

* How this formula is found? In terms of energy and memory unit, what is the processing cost per bit for normal and reverse operations respectively?

# Answer
> 4 votes
(This is a cross-posted answer from Physics Stack Exchange)

The simple answer would be: consider a physical system that can be in two states. Its thermodynamic entropy is $k\_B \log(2)$ due to this. When you erase the bit, then you have a definite microstate and the entropy is zero. Since entropy cannot decrease it has to go somewhere, and this means it needs to be transferred to the environment that has temperature T, giving us a cost $k\_B T\log(2)$.

This is the simplified version of a slightly dodgy derivation (note how I facilely equated thermodynamic entropy with information entropy without justification and did not specify how erasure happened or the entropy got moved around). Once can do this more rigorously, like in this paper.

Also, it is worth pointing out it is a misconception that the cost has to be paid in energy. If you have an empty computer memory you can just swap the erased bit for a fresh zero reversibly. But empty computer memory is in a sense a heat reservoir at absolute zero but with very limited capacity (it will eventually run out). It is possible to show that the cost can be paid using other conserved quantities like spin. It is just that in practice we tend to move entropy around by dumping it as waste heat in a cool outside heat bath.

(Landauer's original paper)

---
Tags: entropy, reversible-computing
---


title: Query Super Type and Subtype in Mysql

text:
# Question
Title: Query Super Type and Subtype in Mysql
Assuming I have a schema depicted in the image , showing relationships(specialization) between Staffs, Academic Staffs and Non Academic Staffs. Is it possible to have a query that retrieves the department and level if the staff is an academic staff or state and unit if it is a non academic staff based on type attribute in the staff entity?

# Answer
For MS-SQL (MySQL should be very similar):

http://sqlfiddle.com/#!18/4f530/1

Schema:

`CREATE TABLE Staff(
 id int PRIMARY KEY NOT NULL,
 type varchar(45)
)
CREATE TABLE Acad(
 id int PRIMARY KEY NOT NULL,
 dep varchar(45)
)
CREATE TABLE Non(
 id int PRIMARY KEY NOT NULL,
 unit varchar(45)
)
INSERT INTO Staff(id, type) Values (1, 'acad'), (2, 'non')
INSERT INTO Acad Values (1, 'department')
INSERT INTO Non Values (2, 'unit')`

Query:

`SELECT *
FROM Staff S
LEFT JOIN Acad A ON S.id = A.id AND s.type = 'acad'
LEFT JOIN Non N ON S.id = N.id AND s.type = 'non'`

I don't think you can get anything conceptually better without using T-SQL (loops and dynamic code generation).
> 0 votes

---
Tags: database-theory, databases, relational-algebra
---


# Question
Title: How can i solve the recurrence $T(n)=2T(n-2)+n\log n$
What would be the solution of the following recurrence? $$T(n) = 2T(n-2) + n\log n.$$

I've managed to get:

$$T(n) = 2^{n/2}T(0)+\sum\_{i=0}^{n/2} 2^i (n-2i) \log(n-2i). $$

The sum cannot be easily bounded for estimating the recurrence, because part of it increases while the other part decreases as the index grows.

# Answer
> 2 votes
**Hint:**

Let $n=2m$.

$$T(2m)=2T(2m-2)+2m\log(2m)$$

or

$$T'(m)=2T'(m-1)+2m\log(2m)$$

which has the classical form.

# Answer
> 1 votes
Let $S(m) = T(2m)/2^m$. Then $$ S(m) = \frac{T(2m)}{2^m} = \frac{2T(2m-2) + (2m)\log(2m)}{2^m} = S(m-1) + \frac{m\log(2m)}{2^{m-1}}. $$ It follows that $$ S(m) = S(0) + \sum\_{t=1}^m \frac{t\log(2t)}{2^{t-1}}. $$ If we extend the sum on the right to infinity, then we get a convergent series. In other words, $S(m) = \Theta(1)$, and so $T(n) = \Theta(2^{n/2})$.

---
Tags: recurrence-relation
---


# Question
Title: What is the computational complexity of k bit subset sum problem?
The *k bit subset sum* problem is:

**Input:**

$(S, k, b)$ where $S$ is multi set of positive integers encoded in binary (base 2), $k$ is also positive integer encoded in binary (base 2) and $b$ is **bit** (binary digit) so that always $b\in\\{0,1\\}$.

**Output:**

**True** if exists subset sum of $S$ whose $k$ bit (binary digit) equals to $b$.

**False** if does not exist subset sum of $S$ whose $k$ bit (binary digit) equals to $b$.

# Answer
> 2 votes
I'm assuming that when $k=1$, the $k$th bit is the LSB.

If $b = 0$ then the answer is always positive, since you can take the sum of the empty subset.

If $b = 1$ and one of the numbers has its $k$th bit equal to $1$ then the answer is positive, so we can assume that all $k$th bits are equal to $0$. Reduce all numbers modulo $2^k$. Since originally the $k$th bits were $0$, all numbers are less than $2^{k-1}$. If the sum of all numbers is less than $2^{k-1}$, then clearly the answer is negative. If the sum of all numbers is at least $2^{k-1}$, arrange them in some arbitrary order $x\_1,x\_2,\ldots$, and sum them one by one until reaching the first sum $s\_i = x\_1 + \cdots + x\_i$ which is at least $2^{k-1}$. Since $s\_{i-1} \< 2^{k-1}$ and $x\_i \< 2^{k-1}$, we see that $s\_i \< 2^k$. Thus the $k$th bit of $s\_i$ is $1$. Hence the answer is positive.

Summarizing, here is our algorithm:

* If $b = 0$, answer True.
* If $b = 1$ and there exists a number whose $k$th bit is $1$, answer True.
* If $b = 1$ and all $k$th bits are $0$, reduce the input modulo $2^k$, and answer True if the sum of all reduced numbers is at least $2^{k-1}$.

---
Tags: complexity-theory
---


# Question
Title: What does Arora mean by 'computational history'?
In Arora's paper, he wrote,

> Papadimitriou and Yannakakis also noted that the classical style of reduction (Cook-Levin-Karp \[41, 99, 85\]) relies on representing a computational history by a combinatorial problem. A computational history is a very non-robust object, since even changing a bit in it can affect its correctness. This nonrobustness lay at the root of the difficulty in proving inapproximability results.

What does he mean by this statement? In particular: what does it mean by 'computational history', and 'representing a computational history by a combinatorial problem'?

I conjecture that: \[it is\] a very non-robust object, he means that computation could make many many errors. So, in the last statement in the paragraph, maybe he means nonrobustness \[the ability to make many errors\] lay at the root of the difficulty in proving inapproximability.

Could someone tell me how nonrobustness exists in Karp/Levin reduction?

# Answer
> 4 votes
The computational history consists of the contents of the tape of the Turing machine after each step. These are the variables in the SAT instance produced by the Cook-Levin theorem, which is the combinatorial problem which represents the computational history.

This representation is fragile in the sense that even when the SAT instance is unsatisfiable, we may be able to satisfy almost all of its clauses - say, all but a constant number. This is because the reduction in the Cook-Levin theorem is very local: if we flip a single bit in the computational history, then this falsifies only a small number of clauses. In contrast, the PCP theorem guarantees that the SAT instance is either satisfiable or at most 99% of its clauses can be satisfied, and this implies a hardness of approximation result for MAX-SAT.

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