# Question
Title: What is a "trap" in the context of system virtualization?
My professor's notes on system virtualization refer a lot to the term "trap", but don't seem to explicitly define it. I can't seem to find any definition on Google either, other than a small article on "trap-and-emulate". From context I sort of understand that trapping is 'catching' any operations that the virtual OS performs which it no longer has the privilege for (as it is now operating in restricted mode), and forwarding them to the hypervisor to be handled.

However could someone who has a more solid understanding of this give me a better definition?

(also I apologize for poor tagging, as there doesn't seem to be a relevant tag for virtual systems)

# Answer
> 5 votes
A trap is basically a localized exception/fault which occurs when the guest OS does not have the required privileges to run a particular instruction. Operating systems running on top of a virtual machine monitor (a hypervisor) do not know that they are running in the 'user' mode i.e. they can only execute a limited set of instructions, since they do not have full control over the bare-metal. So, when the operating system executes some privileged instructions (instructions which can only be run in the 'kernel' mode or some privileged mode), those instructions create a trap that goes into the hypervisor which then emulates the expected functionality of the OS. Note: that the hypervisor runs the commands and emulates it to the application in a VM, so that the application never knows that it is running in a VM.

Source: https://stonefly.com/blog/deep-dive-virtualization

---
Tags: terminology, operating-systems
---


title: 2D convolution: Flipping the kernel?

text:
# Question
Title: 2D convolution: Flipping the kernel?
Why do we need to flip the kernel in 2D convolution in the first place? What's the benefit of this? So, why can't we leave it unflipped? http://www.songho.ca/dsp/convolution/convolution2d\_example.html

input

kernel

output

"First, flip the kernel, which is the shaded box, in both horizontal and vertical direction"

# Answer
> 13 votes
If you do not flip the kernel, you simply obtain a different operation that is called cross correlation. When the filter is symmetric, like a Gaussian, or a Laplacian, convolution and correlation coincides. But when the filter is not symmetric, like a derivative, you get different results.

The reason why convolution is preferred over correlation is that it has nicer mathematical properties. In particular, convolution is associative, while correlation in general is not.

For a more technical explanation we need to go into the frequency domain. The main theorem of convolutions states that the Fourier tansform of the convolution $f\*g$ of two functions $f$ and $g$ is equal (up to a constant depending on the transformation) to the product of the Fourier transforms of the two functions. In symbols

$$ {\mathcal {F}}\\{f\*g\\}=k\cdot {\mathcal {F}}\\{f\\}\cdot {\mathcal {F}}\\{g\\}$$

where $\mathcal {F}$ is the Fourier transform. In the case of correlation, you would get multiplication by the complex conjugate, that is less nice, and in particular not associative.

Another interesting property of convolution is that convolving a kernel with a unit impulse (e.g. a matrix with a single 1 at its center and 0 otherwise), you get the kernel itself as a result. Correlation would flip the kernel, instead.

---
Tags: image-processing
---


# Question
Title: Why is Heapsort in O(n log n) if not all n operations take time log n?
let's consider that we already have constructed heap array.

so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap tree level decreases -\> **downheap** operation level decreases

but `nlogn` means each `n` nodes has `logn` operation. But not all nodes do `logn`**(original down heap operation level)** operation because of heap tree level decrease.

# Answer
> 0 votes
> $n \log n$ means each $n$ nodes has $\log n$ operation.

No, it does not. That's like saying:

> \\$100 means I sold 100 drinks for \\$1 each

Obviously, you could have sold any number of things as long as they add up to \\$100.

With algorithm costs it's the same. A sequence of operations taking "time" $\Theta(n \log n)$ means that the "time" costs of all the operations add up to something that behaves roughly like $n \log n$.

Once Landau terms enter the pickture, things get muddled. It's tempting to tread $\sum\_{i=1}^n O(\log i)$ in the same way as $\sum\_{i=1}^n \log i$, but the former sum doesn't really make sense. I recommend you read our reference questions on algorithm analysis and asymptotics to see how one can arrive at the final result here.

---
Tags: algorithm-analysis, runtime-analysis, sorting, heaps, heap-sort
---


# Question
Title: How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?
Why does (if so) the seperator $\\#$ is making a difference between the two languages ?

Let say:

$L=\\{ws : |w|=|s|\\, w,s\in \\{0,1\\}^{\*}, w \neq s \\}$

$L\_{\\#}=\\{w\\#s : |w|=|s|\\, w,s\in \\{0,1\\}^{\*}, w \neq s \\}$

Here is a proof and a grammer representing $L$ as a $CFL$

And below Im adding a proof for $L\_{\\#} \notin CFL$ :

Does the $\\#$ sign truly make a difference? if so, why is that ? and if not, which one of the proofs is wrong and where?

## Proof that $L\_{\\#} \notin CFL$ :

Assume by way of contradiction that $L ∈ CFL$. Let $p \> 0$ be the pumping constant for $L$ guaranteed by the pumping lemma for context-free languages. We consider the word $s = 0^{m}1^{p}\\#0^{p}1^{m}$ where $m=p!+p$ so $s ∈ L$. Since $|s| \> p$, according to the pumping lemma there exists a representation $s = uvxyz$, such that $|vy| \> 0$, $|vxy| ≤ p$ , and $uv^{j}xy^{j} z ∈ L$ for each $j ≥ 0$.

We get a contradiction by cases:

* If $v$ or $y$ contain $\\#$: Then for $i = 0$, we get that $uxz$ does not contain $\\#$, so $uxz \notin L$ in contradiction.
* If both $v$ and $y$ are left to $\\#$: Then for $i = 0$, we get that $uxz$ is of the form $w\\#x$, where $|w| \< |x|$, so $uxz \notin L$.
* If both $v$ and $y$ are right to $\\#$: Similar to the last case.
* If $v$ is left to $\\#$, $y$ is right to it, and $|v| \< |y|$: Then for $i = 0$, we get that $uxz$ is of the form $w\\#x$, where $|w| \> |x|$, so $uxz \notin L$.
* If $v$ is left to $\\#$, $y$ is right to it, and $|v| \> |y|$: Similar to the last case.
* If $v$ is left to $\\#$, $y$ is right to it, and $|v| = |y|$: This is the most interesting case. Since $|vxy| ≤ p$, $v$ must be contained in the $1^{p}$ part of $s$, and $y$ in the $0^{p}$ part. So it holds that $v = 1^{k}$ and $y = 0^{k}$ for the same $1 ≤ k ≤ p$ (in fact, it must be that $k \< p/2$). For each $j ≥ 0$, it holds that $uv^{j+1}xy^{j+1}z = 0^{m}1^{p+j·k}\\#0^{p+j·k}1^{m}$, so if it happens that $m = p + j · k$, then it holds that $uv^{j+1}xy^{j+1}z \notin L$ in contradiction. To achieve this, we must take $j = (m-p)/k$, which is valid only if $m − p$ is divisible by $k$. Recall that we chose $m = p + p!$, so $m − p = p!$, and $p!$ is divisible by any $1 ≤ k ≤ p$ as wanted.

# Answer
Your proof is correct, and I was wrong. It took me a while to nail down where my confusion was, but with Yuval's help I think I got it.

Let's consider the three languages

$\qquad\begin{align\*} &L\_= &\\!\\!\\!\\!\\!\\!\\!\\!\\! &= \\{ xy \mid |x| = |y|, x \neq y \\}, \\ &L\_{\\#} &\\!\\!\\!\\!\\!\\!\\!\\!\\! &= \\{ x\\#y \mid x \neq y \\},\ \text{and} \\ &L\_{=\\#} &\\!\\!\\!\\!\\!\\!\\!\\!\\! &= \\{ x\\#y \mid |x| = |y|, x \neq y \\}. \end{align\*}$

As we have seen here, $L\_=$ is context-free. The trick is, in the grammar, to generate symbols "on the right" but count them "on the left" later (or the other way around), making sure mismatching symbols appear at matching positions. The length condition is trivial since it reduces to even length.
You can construct an NPDA with a similar idea, using the stack to match the position.

$L\_\\#$ is also context-free. The proof is even simpler: the mismatching symbols appear the same distance away from the beginning resp. the separator. Unequal lengths can be checked separately; non-determinism "chooses" between the two options.

Now, as you show, $L\_{=\\#}$ is *not* context-free. Here is why the proofs for the other two languages break down.

1. In the grammar for $L\_=$, if we have to generate a separator in the middle we can not "reassign" symbols from "left" to "right".
2. Instead of "accept if lengths unequal *or* mismatch" we have to "accept if lengths equal *and* mismatch". Non-determinism can not help us with the *and*!

So what it boils down to, intuitively, is that conditions of the form "$x \neq y$" and "$|x| = |y|$" are both "context-free" in the sense that they can be checked with a stack, but not using finite control. Therefore, a PDA can do one but not both.

The PDA for $L\_=$ "cheats" since it does not *really* check these conditions for $x$ and $y$; it splits the word up in a different way. That's no longer possible if you have the separator.

---

*Addendum:* I boldly claimed that $L\_= \in \mathrm{CFL} \implies L\_{=\\#} \in \mathrm{CFL}$ because CFL is closed against inverse homomorphism. While it's true that $f(L\_{=\\#}) = L\_=$ with $f$ the identity except it deletes $\\#$, that is not relevant. $f^{-1}(L\_=) = L\_\\#$; nothing can be said about $L\_{=\\#}$.

---

*Addendum II:* Note that $L = \\{ x\\#y \mid |x| = |y| \\}$ is trivially context-free. Hence, with $L \cap L\_\\# = L\_{=\\#}$ we have a nice example for CFL not being closed against intersection.
> 9 votes

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


title: HALF CLIQUE - NP Complete Problem

text:
# Question
Title: HALF CLIQUE - NP Complete Problem
Let me start off by noting **this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please**. With that said, here is the problem I am looking at:

> Let HALF-CLIQUE = { $\langle G \rangle$ | $G$ is an undirected graph having a complete subgraph with at least $n/2$ nodes, where n is the number of nodes in $G$ }. Show that HALF-CLIQUE is NP-complete.

Also, I know the following:

* In terms of this problem a *clique*, is defined as an undirected subgraph of the input graph, wherein every two nodes are connected by an edge. A *$k$-clique* is a clique that contains $k$ nodes.
* According to our textbook, Michael Sipser's "*Introduction to the Theory of Computation*", pg 268, that the problem CLIQUE = {$\langle G,k\rangle$ | $G$ is an undirected graph with a $k$-clique} is in NP
* Furthermore, according to the same source (on pg 283) notes that CLIQUE is in NP-Complpete (thus also obviously in NP).

I think I have the kernel of an answer here, however I could use *some indication of what is wrong with it or any related points that might be relevant to an answer*. This is the general idea I have so far,

> Ok, I'd first note that a certificate would simply be a HALF-QLIQUE of $\text{size} \geq n/2$. Now it appears that what I would need to do is to create a verifier that is a polynomial time reduction from CLIQUE (which we know is NP-Complete) to HALF-CLIQUE. My idea would be that this would be done by creating a Turing machine which runs the turing machine verifier in the book for CLIQUE with the additional constraint for HALF-CLIQUE.

This sounds correct to me, but I don't really trust myself yet in this subject. Once again, I would like to remind everyone **this is a HOMEWORK PROBLEM** so please try to avoid answering the question. Any guidance which falls short of this would be most welcome!

# Answer
> 16 votes
Judging by your description and comments, you might be helped the best by an exact description on how reductions can be used to prove NP-completeness:

A problem is NP-complete iff it is in NP and it is NP-hard. This means that any proof of NP-completeness has two parts: a proof that the problem lies in NP and a proof that it is NP-hard.

For the first part, you have to show that YES-instances can be verified in polynomial time using some suitable certificate. Alternatively, you can show the problem can be solved in polynomial time by a non-deterministic Turing machine, but this is not usually done as mistakes are easily made.

In your case, this comes down to proving that for every graph with a $n/2$-clique, you can find some proof that there is indeed such a clique, such that, armed with such a proof, you can check in polynomial time that there is indeed such a clique.

For the second part, you have to show that the problem is NP-hard. This is in nearly all cases shown by proving that your problem is at least as hard as some other NP-hard problem. If HALF-CLIQUE is as least as hard as CLIQUE, it must also be NP-hard.

You do this by proving a reduction **FROM** CLIQUE, **TO** HALF-CLIQUE. You 'reduce' the problem, making it 'easier'. You say "Solving CLIQUE is hard, but I have proven that you only need to solve HALF-CLIQUE to solve CLIQUE". (many people, even experts, occasionally say this the wrong way around :))

There are different types of reductions: the reduction that is most commonly used is the one where you map instances of in this case CLIQUE to instances of HALF-CLIQUE whose size is at most polynomially larger, in polynomial time. This means that if we can solve HALF-CLIQUE, then we can also solve CLIQUE by chaining the algorithm and the reduction.

In other words, we must show that we can solve CLIQUE if we can solve HALF-CLIQUE. We do this by showing that for every instance for CLIQUE, we can design an instance of HALF-CLIQUE such that the instance of CLIQUE is a 'yes' instance iff the instance of HALF-CLIQUE is a 'yes' instance.

The proof therefore starts like this: given a graph $G=(V, E)$, I can create some graph $H=(V', E')$ such that $G$ contains a $k$-clique iff $H$ contains a $n/2$-clique. I'll leave this part to you (this is the part that requires creativity, the part that is about the specific problem at hand).

# Answer
> 8 votes
You seem a little lost. You want to show that HALF-CLIQUE $\ge$ CLIQUE, which means that you are looking for a poly-time algorithm that takes CLIQUE instances as the input and outputs HALF-CLIQUE instances with the property that "yes" inputs map to "yes"es and "no" inputs map to "no"s.

So, basically, the task is to take a graph $G$ and a number $k$ and output a new graph $H$ (and no number) so that $H$ has a clique on at least half of its vertices whenever $G$ has a clique of size $k$.

The spoiler below contains a hint on how to perform this reduction:

> Try to make $H$ by attaching (in some way) an appropriately sized clique to $G$, plus some number of vertices not connected to anything.

# Answer
> 0 votes
You can reduce from the vertex cover problem. If the complement graph of the given graph has a vertex cover less than n/2 nodes then this graph will have a clique of more than n/2 nodes that is it will be a half clique. Just state that it is difficult to solve the Vertex Cover problem so is this.

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


# Question
Title: Selection of pivot in quicksort partitioning of Hoare and Lomuto
There are two commonly mentioned partition methods:

```
algorithm lomuto_partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
    if A[j] ≤ pivot then
        i := i + 1
        swap A[i] with A[j]
swap A[i+1] with A[hi]
return i + 1

algorithm hoare_partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
    do
        i := i + 1
    while A[i] < pivot

    do
        j := j - 1
    while A[j] > pivot

    if i >= j then
        return j

    swap A[i] with A[j]

```

(excerpt from Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) \[1990\]. Introduction to Algorithms. MIT Press and McGraw-Hill. pp. 170–190.)

And it has been suggested that Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.

But why does Lomuto partitioning scheme use rightmost element(A\[hi\]) as pivot value and Hoare scheme use leftmost element (A\[lo\]) as pivot value?

It seems that there is no difference in number of comparisons or swaps and they will produce worst case behavior on already sorted arrays.

Is it just because they implemented and introduced them with rightmost element and leftmost element as pivot value respectively? Or is there a reason?

# Answer
As you now correctly, every arbitrary but fixed choice of pivot is equally bad; the cases are symmetric.

The difference is probably historical and may not exist in all write-ups of the algorithms.

Note that you have to change the `for`-loops if you switch from `hi` to `lo` or the other way around, but that is not a conceptual difference.
> 1 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: Misunderstanding of proof with transitivity of logspace reduction
I read a commonly known proof of transitivity of logspace reduction: *Lemma 6.*: http://www.cs.au.dk/~arnsfelt/CT10/scribenotes/lecture5.pdf . In this proof it is used following trick: Let some turing machine $M\_f$ for language $f$ compute only $j$-th bit of output. Ok, $M\_f$ is logspace machine, however tape with output can require $O(n)$ space. Hence, we can't get $j$-th bit in such easy way.

Where am I wrong ?

# Answer
$L\_f$, by definition, gives you the output of $f(x)$ for a single bit $j$. Note that we do not have to copy $x$, so we're only storing $bin(j)$ and the $j$-th bit of $f(x)$, which is in logarithmic space. Since $M\_f$ computes $L\_f$ with logarithmic space, we can simply get the $j$-th bit. This means that $M\_h$ can work in logspace in total, as it only asks and stores a single bit of input from $M\_f$ every time.
> 0 votes

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


# Question
Title: how to prove that every finite language is context-free?
I am trying to prove that every finite language is context-free, is there any type of way that I could do it effectively?

# Answer
> 2 votes
It's not hard to show that every finite language is regular. If you know that every regular language is also context-free, you're done.

# Answer
> -3 votes
Every finite language is Regular. ( Because we can construct a finite automata for it )

Every regular language is cf. ( Because regular language is subset of cf )

Hence proved.

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


# Question
Title: How is $ n^{log(n)} > n^c $ always for any c?
I was going through the questions in MIT quiz : Question 2 g and I found this

How is $ n^{log(n)} \> n^c $ always for any c ?

what if c \> log(n) ?

# Answer
> 3 votes
In these exercises, you are asked to compare functions only according to their asymptotic behavior.

In this case, $c$ is a constant function of $n$, while $\log(n)$ is a function of $n$ that approaches $+\infty$ when $n$ becomes large.

So, $c \> \log(n)$ can only hold for finitely many values of $n$.

---
Tags: asymptotics
---


# Question
Title: ignoring overflow in two's complement addition of numbers with different signs[specific case]
I understand the rule says that overflow cannot happen for two's complement addition of numbers with different signs, but do not understand why this specific case does not cause overflow:

```
 1001010
+0010101
--------
 1011111

```

Am I simply misunderstanding the actual rule or missing a step somewhere? Thanks in advance!

EDIT: removed an extra 1 in the result

# Answer
Okay, let's take a look at your example:

```
 1001010
+0010101
--------
 1011111

```

Your numbers here only have 7 bits, so we have a smaller range than we typically deal with. Nevertheless:

$1001010$ is

$-64 + 8 + 2$, which is $-54$.

$0010101$ is

$16 + 4 + 1$, which is $21$.

$21-54$ is $-33$. Let's see whether our answer matches up:

$1011111$ is

$-64+16+8+4+2+1$, which is $-33$.

An intuitive way to think about this is that the number space is divided entirely in half (with $0$ acting as a positive number). So, with the standard 8 bits, your numbers range from $-128$ to $127$. There is no positive number from within that set that you could add to a negative number from that set and get a number either above $127$ or below $-128$.
> 1 votes

---
Tags: discrete-mathematics, arithmetic
---


# Question
Title: Relation between type-checking decidability, typability decidability and strong normalization
Yo! This is probably a stupid question, however I've never seen it written down explicitly if, for instance, decidability of type-checking is equivalent to the strong normalization property. Therefore I'm asking this question to clarify all possible relations between type-checking, typability and strong normalization.

Let me explain my motivation. For type theories (I'm being intentionally vague here, but I'm interested mainly in dependent type theories), strong normalization is used to prove the decidability of type-checking. On the other side, any typed systems that I know that have one of these properties also have the other one. However I've never seen explicitly stated that strong normalization is equivalent to decidability of type-checking.

Analogously, to prove typability, one usually (maybe always), reduces a term to a normal form. However it's know that typability is not true for dependent type theories, whereas strong normalization may hold.

By decidability of type-checking, I mean that for any given type $A$, context $\Gamma$ and untyped term $a$, it's possible to decide in a finite number of steps whether $\Gamma \vdash a: A$ is true or not.

By decidability of typability, I mean that for any given untyped term $a$, it's possible to decide in a finite number of steps whether there exist a context $\Gamma$ and a type $A$ such that $\Gamma \vdash a: A$ is true.

1)**Is it true that decidability of type-checking is equivalent to every term being strongly normalizable?**

2)**More generally, what's the relation between decidability of type-checking, typability and strong normalization? Which one implies the other?**

Thanks in advance.

**EDIT**

Given the unsatisfaction regarding the level of generality of my question (which I was unaware of), I would like to delimit it only to Pure Type Systems. Of course, additional comments or counterexamples regarding other type theories will be of great utility.

# Answer
I'll give a more focused and technical answer to Martin's. If we're interested in dependent type theories, then neither direction is obvious, but both are generally assumed to hold. However the direction Decidable $\Rightarrow$ Normalizing is open, I believe, even for relatively well understood systems, though we do have partial results. This question explores some of the same issues.

More technically: a good technical framework for these questions is the setting of Pure Type Systems in which normalization *does* imply decidability of type checking. The result is folklore, but non-trivial, since a strategy for when to apply the conversion rule needs to be found. The obvious strategy is to normalize inferred types before all applications of the application rule. There are some subtleties even here, where the correctness of a natural (more efficient) strategy called *expansion postponment* was open for a while, but has been settled since.

There are type systems which are normalizing but undecidable, most notably the system with intersection types which types *exactly* the normalizing terms, and so must be undecidable (since otherwise it could be used to identify normalizing terms). It would be tempting to say here that the system is defective in the sense that it is not *type directed*, i.e. the terms do not contain enough information to figure out the type.

Now the converse, which would suggest non-normalizing systems are undecidable, is far from obvious: it was even open for a while for the famous $Type:Type$ system of Martin-Löf! This case was solved by giving an example of a looping combinator, which allows writing arbitrary computations.

However the general problem is still open for general pure type systems, though it is widely believed to be true, and some partial results have been shown in this direction, e.g. here.
> 13 votes

# Answer
(1) False. Counter example: Java, Scala, Haskell, ...

(2) No general relations hold, really depends on the details of the language/typing system. There is one exception: for sane languages and typing systems, I imagine that decidability of type inference (which I assume is what you mean by "typability") trivially implies type-checking. But I would not be surprised if one could concoct a crazy system where even that implication doesn't hold.
> 4 votes

---
Tags: type-theory, type-checking, type-inference
---


# Question
Title: How do you compute the time complexity of distributed algorithms?
How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(1)$ time due to the unreliability in the time it takes to pass messages. Since this approach is not practical at all, I am assuming that I have not understood it properly. Could someone please explain?

By impractical, I mean that I can simply solve any NP-Hard problem in distributed computing trivially in $\mathcal{O}(n^2)$ time by passing information throughout the network and then brute-forcing for the solution in $\mathcal{O}(1)$ time and this obviously seems stupid since in real life message passing shouldn't take more time than a brute-force solution over the search space.

# Answer
> 4 votes
You understood it right. The standard models of distributed computing typically assume that local computation is free. It follows that in the LOCAL model of distributed computing, you can solve any graph problem in time $O(n)$, and in the CONGEST model of distributed computing, you can solve any graph problem in time $O(m)$ by brute force; here $n$ is the number of nodes and $m$ is the number of edges.

However, we are not interested in such running times in these models. For example, for the LOCAL model, the key question is what can be solved e.g. in polylogarithmic time time, or $O(\log n)$ time, or $O(\log^\* n)$ time, or even $O(1)$ time. Now these are highly non-trivial questions even if you assume that local computation is free.

LOCAL and CONGEST are usually the wrong models if you are interested in studying e.g. NP-hard problems. However, if you consider "easy" problems (e.g. something that you can trivially solve in linear time with a centralised algorithm), then these models become much more interesting. Yes, of course you can find a maximal matching or a maximal independent set in **linear** time, but can you find it in **sublinear** time?

---

Here are the key definitions for reference:

* LOCAL model: running time = number of synchronous rounds until all nodes stop and announce their local outputs; in each round each node can send a message to each of its neighbours; the message size is unbounded; local computation is free.
* CONGEST model: as above, but messages are bounded to $O(\log n)$ bits.

# Answer
> 5 votes
Time complexity is always measured relative to some model. For example, the $\Theta(n \log n)$ bound on sorting is the number of comparisons performed. If comparisons are not constant time, then the total number of operations will be higher.

Because of the high variability, and the overall time taken, often distributed algorithms are measured in terms of the number of messages sent. So in your example, you'd only solve it in $O(n^2)$ time if you assume that there is no cost to sending messages. If you're sending each possibility to a node, a good model will incorporate that cost, and you won't get magically fast solutions to $NP$-hard problems.

Also, for parallel computing, you model (approximately) how many nodes you have. It's a safe-bet to assume that you don't have more than $O(\log n)$ nodes for an input of size $n$. You certainly won't be able to scale your nodes exponentially, so brute-forcing doesn't always work.

Often, the computation done in distributed algorithms is minimal, or the computational content itself is intense, but orthogonal to the distributed nature of the algorithm (i.e. the algorithm is written over some abstract, computationally intensive task). In these cases, you usually *only* care about the messages sent or some other cost metric, since you might never know how many steps your computation takes.

---
Tags: algorithm-analysis, runtime-analysis, distributed-systems
---


# Question
Title: Does there exist an equivalent arithmetic circuit for each computable function?
> Does there exist an equivalent arithmetic circuit for each computable function?

I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe the statement to be false.

What has made me curious is that I've read some theorems stating that a protocol (cryptograhy protocol theory) can compute any computable function, but then requires that the function should be specified as an arithmetic circuit.

# Answer
> 10 votes
Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions $f:\mathbb{F}^n\rightarrow\mathbb{F}$ of the form:

$$f(x\_1,...,x\_n)=\sum\limits\_{i\_1+...+i\_n\le d}\alpha \_{i\_1,...,i\_n}\cdot x\_1^{i\_1}x\_2^{i\_2}...x\_n^{i\_n}$$

where $\alpha \_{i\_1,...,i\_n}\in\mathbb{F}$ are the coefficients of the multivariate polynomial.

There are many computable functions that cannot be expressed as a polynomial, e.g. take $f:\mathbb{Q}\rightarrow\mathbb{Q}$ which is $1$ at $x=0$ and zero everywhere else. Since $f$ is non constant with an infinite number of zeros, it cannot be written as a univariate polynomial.

# Answer
> 15 votes
Any computable *boolean* function with a *fixed-length* input can be computed by an arithmetic circuit. Consider any boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$. Then there exists a multivariate polynomial $p(x\_1,\dots,x\_n)$ such that $f(x\_1,\dots,x\_n) = p(x\_1,\dots,x\_n)$ for all $x\_1,\dots,x\_n$, where arithmetic is done modulo two (i.e., over the field $\mathbb{F}\_2=\\{0,1\\}$). Now every multivariate polynomial can be computed by a an arithmetic circuit, so $f$ can be computed by an arithmetic circuit.

In some sense the restrictions to fixed-length inputs is unavoidable, as *any* circuit inherently has a fixed number of inputs and a fixed number of outputs. So once you decide to focus on boolean functions, then the statement you saw in the crypto literature is justified: any boolean function that can be computed by a circuit, can be computed by an arithmetic circuit. And, any computable boolean function can be computed by arithmetic circuits, where we understand "computed" to mean that there is a family of arithmetic circuits, one per input length (the non-uniform model; this is unavoidable if you want to compute using circuits, as any one circuit can only have a fixed input length).

---
Tags: computability, computation-models, cryptography, circuits, simulation
---


# Question
Title: Does there always exist a reduction between two NP-hard problems?
Let $A$ and $B$ be NP-hard problems. For all tuples $(A, B)$ does there exist a polynomial time reduction from $A$ to $B$ and from $B$ to $A$?

Context: I want to prove some problem is NP-hard. Can I pick any problem in NP-hard to reduce from?

# Answer
A decision problem $L$ is NP-hard when for every problem $H$ in NP, there is a polynomial-time reduction from $H$ to $L$. This is important because it does not necessarily go the other way, you can not say there is a polynomial time reduction from $L$ to $H$. This is because a problem can be NP-Hard and not be in NP. If $A$ and $B$ in your question are both not in NP then there may not be a reduction.
> 0 votes

---
Tags: reductions, np-hard
---


# Question
Title: Calculating fractions of accesses from various levels of memory? (L2 - Main)
I'm currently studying computer architectures module, and during the workshop I came a across a series of questions that I struggled to being to answer.

The question goes;

```
*You have an L1 data cache, L2 cache, and main memory. The hit rates and hit times for
each are:
50% hit rate, 2 cycle hit time to L1.
70% hit rate, 15 cycle hit time to L2.
100% hit rate, 200 cycle hit time to main memory.

```

What fraction of accesses are serviced from L2? From main memory?

My answer: (200\*0.7)/15 = 9.3

To be completely honest, I don't know how to approach these type's of questions, I'd be grateful if someone could point me to resources.

# Answer
> 1 votes
The order of accesses is L1 → L2 (→ L3) → main memory. The chance of missing is $1 - p$ where $p$ is the hit chance.

In order for an access to hit L2 cache, it must have missed the L1 cache, and hit the L2 cache. So the chance is $(1 - 0.5) \cdot 0.7 = 0.35$.

In order for an access to hit main memory, it must have missed the L1 cache, missed L2 cache and hit main memory. So the chance is $(1 - 0.5)\cdot (1 - 0.7) \cdot 1 = 0.15$.

---
Tags: cpu-cache, memory-access
---


title: Encode an ascii string in base 15

text:
# Question
Title: Encode an ascii string in base 15
How can I encode an ascii string in base 15?

In other words, I have the following characters available:

```
0123456789abcde

```

I have *no idea* how to do this. What do you suggest I do?

(If this is not on-topic, please migrate.)

# Answer
Let's take a different view angle.

The problem is not really about encoding something like "decimals numbers" 0..127 into base-15 (which is messy). It's about converting a base-127 string into base-15. If you can see it that way, then it's just the same principle as with converting from, say, base-16 (hex) to base-10 (decimal), or base-10 to base-2.
> 3 votes

---
Tags: strings, encoding-scheme
---


title: Center of a Cycle and Complete graph

text:
# Question
Title: Center of a Cycle and Complete graph
The center of a graph is the set of vertices with minimum eccentricity, so a $C\_n$ have the minimum eccentricity equals to $n$ and a $K\_n$ have the minimum eccentricity equals to $1$? Is valid that a center of a graph be the graph itself?

# Answer
> 0 votes
Let $G = (V, E)$ be a graph. If the eccentricity of each vertex $v \in V$ is $c$. Then the center of the graph is $V$, the set of all vertices of the graph $G$. Note that the center is **the set $V$ of vertices** not the graph $G$. In general the center of a graph $G = (V, E)$ is a subset of $V$.

---
Tags: graphs
---


title: Proof any CFG can be converted to GNF

text:
# Question
Title: Proof any CFG can be converted to GNF
I studied algorithm for converting grammars to GNF and was wondering about a proof that any CFG can be converted into GNF. I found this paper *\- ENGELFRIET, Joost. An Elementary Proof of Double Greibach Normal Form, 1992*, but I do not understand the proof at all.

Any CFG can be converted into CNF, so we try to prove that any grammar in CNF can be converted into GNF.

At first, a grammar **H** (not GNF, but can be easily converted into GNF by substitution and by removing rules containing empty string) is constructed from original CNF denoted **G** as follows:

> 1) for rules Y → a $$ A \rightarrow a\[Y,A\] $$ 2) for rules C → DQ $$ \[D, A\] \rightarrow Q\[C, A\] $$ 3) $$ \[A, A\] \rightarrow \epsilon $$

Than there are mentioned two statements about this new grammar. These statements are essential for the proof, because they show that the grammar H is equivalent to G. And I do not know why they are right:

> $$ (\[Y,A\] \rightarrow^\*\_H w) \iff (A \rightarrow ^\*\_G Y w) $$ and $$ (A \rightarrow^\*\_H w) \iff (A \rightarrow ^\*\_G w) $$

There is also written that these statements can be shown by induction. I tried to prove them but it seems to me that to prove one of them, I also need to prove the second. So I am stuck at cycle.

Could somebody please explain it to me?

# Answer
> 2 votes
The textbook proofs of Greibach NF I have seen, contain endless substitutions. This way to construct GrNF is much crisper.

The key is to understand what the nonterminal $\[Y,A\]$ actually represents. It means a derivation that has a leftward "backbone" which starts from $A$ and ends just *before* $Y$, as in the picture below.

Now the first production in $H$ can be explained as follows. If I start with $A$ and want to produce GrNF then I must generate a terminal. We choose to generate the leftmost terminal $a$ of the subtree under $A$. So, we produce $a$, but we still must find a derivation $\[Y,A\]$ of the form in the picture, where $Y$ is the nonterminal that actually produces $a$ using the available production $Y\to a$.

---
Tags: context-free, formal-grammars, normal-forms
---


title: Decision problems whose verifier is NP

text:
# Question
Title: Decision problems whose verifier is NP
We define $\mathbf P$ as the set of problems solvable in polynomial time. We define $\mathbf{NP}$ as the set of problems with a verifier $ \in \mathbf P$.

Is there a name for problems whose verifiers are $\in \mathbf {NP}$ (e.g., $\mathbf{N(NP)}$)? I can't see this being a very *useful* complexity class, but, for example we have that $\mathbf{NP} \neq \mathbf{N(NP)} \implies \mathbf{P} \neq \mathbf{NP}$, so it might be an area of research for that reason alone.

# Answer
> 3 votes
Suppose you had a problem such that for any $x \in L$, there was a verifier $v$ such that $v$ could be checked against $x$ by a nondeterministic polynomial time algorithm. For a valid $(x, v)$ pair, there is some verifier $v'$ such that it takes polynomial time to check $((x, v), v')$ is a correct verification.

But then, you could simply combine $(v, v')$ into a single witness, and run the check in deterministic polynomial time.

Thus, the class ${\bf N(NP)}$ you describe is really just equal to ${\bf NP}$.

# Answer
> 0 votes
If a problem has a verifier you can guess it with nondeterministic TM so it is automatically in NP.

---
Tags: complexity-theory, np, decision-problem, complexity-classes
---


# Question
Title: O(n) Palindromic Substring: Why is O(n^2) needed here?
I have been doing dynamic programming problems, and I came across a palindromic substring question. I answered it quickly, and found an $O(n)$ dynamic programming solution, but when I check the actual solution, I find that I should be getting an $O(n^2)$ result.

Can someone explain where I am going wrong/how this is not correct?

---

The problem reads: given string $x\_1,x\_2,\ldots,x\_n$, find the longest palindromic substring.

I write:

$$ T(i) = \text{max length palindromic substring ending at position }i\text{ in string }X $$

Then I write down the following subproblem (where $j$ is intended to be the letter right before the beginning of the palindrome ending at position $i$):

$$ \begin{align} \text{IF }x\_i = x\_j, \text{ where } &j = i - T(i-1)-1:\\ T(i) &= T(i - 1) + 2;\\ \text{ELSE IF} x\_i = x\_{i-1} \\ T(i) &= 2;\\ \text{ELSE } T(i) &=1; \end{align} $$

As far as I can tell, this is correct. In order to recover the palindrome, I record it in linked lists or whatever, and calculate the argmax of $T$.

---

Where am I going wrong?

# Answer
Consider the following string $$ dabacabac $$ When you go to compute $T(9)$ (using one indexing), you have $T(8) = 7$. But since $$ T(1) = d \neq c = T(9) $$ You will put $T(9) = 1$, when it should be $T(9) = 5$.
> 1 votes

---
Tags: dynamic-programming, substrings
---


# Question
Title: Lower limit on the number of check bits needed to correct single errors
I was going through Andrew S. Tannenbaum's computer networks book, and on page 206 of it, he has derived the number of check bits needed to correct single bit errors. The derivation goes as follows:

For m data bits, there are 2^m legal messages. Each of these messages has n illegal codewords at a distance on 1 from it. These are formed systematically by inverting each of the n-bit codeword formed from it. Thus, each of the 2^m legal messages requires n+1 bit patterns dedicated to it....

Can someone please explain the last line to me? For an n-bit codeword, we can only flip n bits to get illegal codewords. When does that additional 1 come from?

I am very new to coding theory, so please excuse if this is a very naive question.

Thanks!

# Answer
The comment by @gnasher is right. Moreover, if the code was $k$ error correcting with $m$ data bits, each of the $2^m$ legal messages would require $$ 1+n+\binom{n}{2}+\cdot+\binom{n}{k}=\sum\_{j=0}^k \binom{n}{j} $$ bit patterns dedicated to it, where $\binom{n}{j}$ is the number of words at Hamming distance $j$ from a given word.
> 1 votes

---
Tags: computer-networks, coding-theory, hamming-code
---


# Question
Title: Can Inverse of weights(1/weight,not negation) be used to find the longest path between two points by using dijkstra's algorithm?
Considering that there no cycles in the graph.

I have seen the posts where the negation of the weights is suggested and to use Bellman-ford. But I was wondering if the inverse is possible.

# Answer
Hint: take a graph with all weights equal 1.
> 4 votes

# Answer
Yes, this works for undirected acyclic graphs. Such a graph is a forest so there is exactly one path between two vertices in the same component. Since there is exactly one path, the shortest path is also the longest path, regardless of what weights you use.

For directed acyclic graphs, it fails for the reason that Eugene points out.
> 4 votes

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


# Question
Title: How many permutations for generating a specific binary search tree?
The keys 2, 4, 6, 7, and 8 have been inserted, one by one, in some unknown order, into an initially empty BST. The result is this BST:

There are 120 different permutations of the five keys, but not all of these would lead to this particular BST being built. How many of the permutations will generate this particular BST?

# Answer
> 2 votes
In a BST we can't say anything regarding the order of elements that are on separate sides of a node (e.g. 4 and 8, because they are on separate sides of node 6), however, we know that if a node is a parent of another node, it must have been inserted before it.

So 6 is always going to be the first element. Then either 4 or 7 can come (two choices). Then if we look at the remaining structure, 4/2 and 7/8 have exactly the same structure, so we can analyze just one.

Without loss of generality, assume we picked 4. Afterwards we can choose either 2 or 7 (two choices).

If we chose 2, no choice is left. However if we chose 7 either 2 or 8 can come next (two choices). Then we're left with no choice.

So the total number of permutations is $2(1 + 2) = 6$. The permutations are:

```
64278
64728
64782
67842
67428
67482

```

---
Tags: binary-search-trees
---


title: Display Counting Algorithm

text:
# Question
Title: Display Counting Algorithm
I am writing some firmware for a display that will take measurements and present them in real time on an LCD screen. I would like for the measurements to display as *smoothly* as possible... What I mean is that I am looking for a smooth animation sequence on the display, such that values don't jump from say 15.1 to 15.8... I'd like for the reading to look more natural, where maybe a sequence of values would be displayed as the value increased from 15.1 to 15.4, something like:

1. 15.1
2. 15.2
3. 15.3
4. 15.4

Before going and re-inventing the wheel, is there an algorithm that already describes what is going on here? I guess I would feel comfortable with treating these numbers as strings since that's how they will ultimately be sent to the display (as ASCII characters). Or it doesn't matter if they're treated as floating point numbers, because I can just convert them into strings before I send them to the display.

Also I'd like to add that for cases like 0.0625 to 0.1350... that the algorithm not count every single case in between the two numbers, pick maybe just 10 numbers between the two and display them.

Is there any algorithm that describes this process for the multiple cases as described above?

# Answer
> 0 votes
What you are looking for is called *interpolation*. If you want to interpolate between values $a$ and $b$, with $s$ steps, and $i$ is your current step (going from $\[0, s\]$, where $i=0$ is the start value and $i=s$ is the end value), then the interpolated value is:

$$a + i\frac{b-a}{s}$$

---
Tags: algorithms, counting
---


# Question
Title: R-Tree multipath search - remember the path?
R-Trees can take several paths to retrieve an item because of overlaps in data being indexed or index structure. However, if we run the same search many times on the same unmodified structure, can we remember the correct path and avoid taking the wrong path?

Maybe caching the correct path? But I'm not so sure that R-Tree implementations do this or that R-Trees fully loaded in memory do this either.

# Answer
Sure, you can cache the results of lookups into a R-tree (or any other data structure). Simply build a cache (e.g., a hashtable) where after each lookup into the R-tree, you update the cache; and before doing a lookup into the R-tree, check the cache first. You don't need to store the entire path in the cache: it's enough to just store the results of the search.

Whether this will improve performance or not will depend on your particular workload.
> 1 votes

---
Tags: trees, database-theory, databases
---


# Question
Title: Can someone explain why there are two summations here?
The following quote is from the book "The art of computer programming":

> (..) sentence would presumably be used only if either $j$ or $k$ (not both) has exterior significance.
>
> In most cases we will use notation (2) only when the sum is *finite* \- that is, when only a finite number of values $j$ satisfy $R(j)$ and have $a\_j \neq 0$. If an infinite sum is required, for example $$\sum\_{j=1}^{\infty} = \sum\_{j \geq 1}a\_j = a\_1 + a\_2 + a\_3+\cdots$$ with infinitely many nonzero terms, the techniques of calculus must be employed; the precise meaning of (2) is then $$\qquad\qquad \sum\_{R(j)} a\_j = \left(\lim\_{n\rightarrow\infty} \sum\_{R(j) \atop 0\leq j \leq n} a\_j\right) + \left(\lim\_{n\rightarrow\infty} \sum\_{R(j) \atop 0\leq j \leq n} a\_j\right),\qquad\qquad(3)$$
>
> (...)

And why are they exactly the same? I showed a math professor and he thinks they're labelled wrong but couldn't figure it out. I don't even get why there are two.

Sorry if the question isn't clear enough. I'm referring to the two infinite sums. As far as (2) is concerned he is only referring to what is on the left hand side of the equation with the two infinite sums. Its just a way of representing any possible series. So essentially my question is how does making any series go to infinity make two of them? Or am I misunderstanding?

Also I tried to post this in math stack exchange and it wouldn't let me so I came here since its from the book, the art of computer programming.

# Answer
> And why are they exactly the same? I showed a math professor and he thinks they're labelled wrong but couldn't figure it out. I don't even get why there are two.

When in doubt, check the book's errata (Page 4).

> $$ \sum\_{R(j)} a\_j = \Bigg( \lim\_{n\rightarrow \infty} \sum\_{\color{red}{{\substack{R(j)\\\-n\leq j\<0}}}} a\_j \Bigg ) + \Bigg(\lim\_{n\rightarrow \infty} \sum\_{{\substack{R(j)\\0\leq j\< n}}} a\_j \Bigg) $$

Because $R(j)$ is a relation involving $j$, so you must check whether it's satisfied for negative values as well.

The previous paragraph also has a typo:

> $$ \color{red}{\sum\_{j=1}^{\infty} a\_j} = \sum\_{j\geq 1} a\_j = a\_1 + a\_2 + a\_3 + \cdots $$
> 5 votes

---
Tags: mathematical-analysis
---


title: Counting islands in Boolean matrices

text:
# Question
Title: Counting islands in Boolean matrices
Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ entries.

The original question was to count the number of islands in a given matrix. The author described a recursive solution ($\mathcal{O}(nm)$ memory).

But I was unsuccessfully trying to find a streaming (left to right, and then down to the next row) solution that dynamically counts islands with $\mathcal{O}(m)$ or $\mathcal{O}(n)$ or $\mathcal{O}(n+m)$ memory (there are no limits for the time complexity). Is that possible? If not, how can I prove it?

---

A few examples of expected outputs for certain inputs for the `count` function:

$ count\begin{pmatrix} 010\\ 111\\ 010\\ \end{pmatrix} = 1; % count\begin{pmatrix} 101\\ 010\\ 101\\ \end{pmatrix} = 5; % count\begin{pmatrix} 111\\ 101\\ 111\\ \end{pmatrix} = 1; $

$ count\begin{pmatrix} 1111100\\ 1000101\\ 1010001\\ 1011111\\ \end{pmatrix} = 2$

$ count\begin{pmatrix} 101\\ 111\\ \end{pmatrix} = 1$

# Answer
> 4 votes
Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual complexity is $O(\min(m, n))$ memory. Processing time is $O(mn)$.

1. Initialization. Scan over the first row and find all connected substrings of that row. Assign each disjoint substring a unique positive id and save this as a vector which is zero where $X$ is zero and the unique positive id otherwise.
2. For each remaining row assign unique ids (never re-assign previous unique ids, make sure that your ids are strictly increasing) to substrings in that row again. View the previous row plus the current row as a $2$ by $m$ matrix, and any connected areas should be assigned to their minimum. As an example:

$$\begin{array}0010402220333300\\ 506607080009990\end{array} \rightarrow \begin{array}0010402220333300\\ 504402020003330\end{array}$$

There's no need to update the previous row for the correctness of this algorithm, only current one.

After that's done, find the set of all ids in the previous row that do not connect to the next row, **discarding duplicates**. Add the size of this set to your running counter of islands.

You can now discard the previous row and assign the current row to the previous row and move on.
3. To correctly handle the last row pretend there is another row of zeros at the bottom of $X$ and run step 2 again.

# Answer
> 6 votes
Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed by reducing set disjointness to your problem.

Suppose that Alice holds a binary vector $x\_1,\ldots,x\_n$ and Bob holds a binary vector $y\_1,\ldots,y\_n$, and they want to know whether there exists an index $i$ such that $x\_i=y\_i=1$. They run your algorithm for the $2\times(2n-1)$ matrix whose rows are $x\_1,0,x\_2,0,\ldots,0,x\_n$ and $y\_1,0,y\_2,0,\ldots,0,y\_n$. After the first row is read, Alice sends Bob $\sum\_i x\_i$ as well as the memory contents, so that Bob can complete the algorithm and compare $\sum\_i (x\_i+y\_i)$ to the number of connected components. If the two numbers match, the two vectors are disjoint (there is no index $i$), and vice versa. Since any protocol for set disjointness needs $\Omega(n)$ bits (even if it can err with a small constant probability), we deduce an $\Omega(n)$ lower bound, which holds even for randomized protocols which are allowed to err with some small constant probability.

We can improve on Orlp's solution by using noncrossing partitions. We read the matrix row by row. For each row, we remember which 1s are connected via paths going through preceding rows. The corresponding partition is noncrossing, and so can be encoded using $O(n)$ bits (since noncrossing partitions are counted by Catalan numbers, whose growth rate is exponential rather than factorial). When reading the following row, we maintain this representing, and increase a counter whenever all ends of some part are not connected to the current row (the counter takes an additional $O(\log n)$ bits). As in Orlp's solution, we add a final dummy row of zeroes to finish processing the matrix. This solution uses $O(n)$ bits, which is asymptotically optimal given our lower bound.

---
Tags: algorithms, matrices, counting, streaming-algorithm
---


# Question
Title: Optimizing for maximum intervals given a distance bound
Given an interval set $X = \\{(s\_1, e\_1), \dotsc, (s\_N, e\_N)\\}$ ordered such that $s\_i \leq s\_j$ and $e\_i \leq e\_j$ for all $i \< j$ and an integer $b$, I would like to find a maximum sized subset $X' \subseteq X$ such that $\text{end}(X') - \text{start}(X') \leq b$. Here the $\text{start}, \text{end}$ functions are defined to be the start position of the first interval and the end position of the final interval.

A simple $O(N^2)$ solution would be to set $b' = b + s\_i$ and scan all elements to see how many fit within the new bound $b'$. However, given the sorted structure of the problem it seems amenable to a fast solution.

First we can built an interval tree and perform the same set of queries as earlier, but result in an $O(N \log N)$ runtime.

I am curious if this is still suboptimal given that the data already are sorted. Is there a linear time dynamic programming solution?

# Answer
> 2 votes
A simple double pointer $O(n)$ linear scan suffices. Initialize $i = j = 1$.

1. Increment $j$ until the next step would make $e\_j - s\_i \> b$. Check if $j - i$ is better than the best found result, if yes, store $(i, j)$ (the boundaries of your subset).
2. Increment $i$. Terminate if we reached the end of the set.

The key observation here is that if a certain $j$ for $i$ is optimal, then for $i' = i+1$, it must be that $j' \geq j$, so we only ever have to scan forwards.

---
Tags: optimization
---


title: The longest path in a tree

text:
# Question
Title: The longest path in a tree
Help me demonstrate this or there is a counterexample?

Let $T(V,E)$ be a tree with $|T| \geq 2$ and a path $P{(u\_0,u\_1,u\_2,...,u\_n)}$. The longest path in a tree has $d(u\_0) = d(u\_n) = 1$.

# Answer
> 2 votes
I'm guessing that $d(v)$ is the degree of $v$, in which case this is fairly straightforward to prove. Here's some intuition: the *longest* path cannot end with a vertex of degree 2 or more, because then the extra neighbor could be used to lengthen the path. I'll leave the specifics of the proof to you.

---
Tags: graphs, trees
---


title: Interpolation Optimization Problem

text:
# Question
Title: Interpolation Optimization Problem
I will try to give the motivation behind this problem and later the math formality.
Given a grayscale image (1 Channel - M by N Matrix).
Someone marks some pixels as anchors.
Now, you need to interpolate the other pixels (Which are not anchors) by minimizing a given cost function s.t. the end result is an image which has the original image values at the anchors and interpolated values else were s.t. it minimizes the cost function.

Given an $M$ by $N$ matrix (A 1 channel image for that matter) $ I $.

Subset of the elements (Pixels) in the matrix are marked as reference and their location is a group marked as $ S $.

The optimization cost function is given by:

$$ \sum\_{\mathbf{r}} \left( E(\mathbf{r}) - \sum\_{\mathbf{s} \in N(\mathbf{r})} {w}\_{\mathbf{rs}} E(\mathbf{s}) \right)^2, \text{ s.t. } \forall p \in S \\; E(\mathbf{p}) = I(\mathbf{p})\\,, $$

where a bold letter $ \mathbf{p}, \mathbf{r}, \mathbf{s} $ means an element (Pixel) location.

The group $ N(r) $ is the neighborhood of $ \mathbf{r} $, which is size $ k $ namely, a $ k $ by $ k $ rectangle where $ \mathbf{r} $ is in the middle.

The weights $ {w}\_{\mathbf{rs}} $ are defined as following:

$$ {w}\_{\mathbf{rs}} \propto \exp\left(-\frac{(I(\mathbf{r}) - I(\mathbf{s}))^2}{2\sigma^2\_r} \right )\ \ \text{ s.t. } \sum\_{\mathbf{s} \in N(\mathbf{r})} w\_{\mathbf{rs}} = 1\\,. $$

Namely, the weights are normalized to 1 within the neighborhood. The variance is calculated on the matrix $ I $ in the neighborhood (You can assume it is given).

So the problem is to find a matrix $ E $ which is equal to $ I $ on all reference points and interpolates other places by bringing the cost function to minimum.

It looks like a weighted least squares per neighborhood (The inner brackets).

I couldn't formalize it (For the whole matrix) a way that can be easily calculated and solved in e.g. MATLAB. Is there a way to formalize it as classic Weighted LS problem?
Or any other form which using the classic tools will bring solution (Get the interpolated matrix)?

Could any one help with that?

P.S. I tried using the Weighted LS per neighborhood disregarding the rest didn't yield the expected results (Obviously).
Tried it just to see how far the real solution is from this naive solution.

# Answer
Using few tricks the equation can be transformed into classic Quadratic Programming problem:

$ E = \arg \max\_{E} \sum\_{\mathbf{r}} \left( E(\mathbf{r}) - \sum\_{\mathbf{s} \in N(\mathbf{r})} {w}\_{\mathbf{rs}} E(\mathbf{s}) \right)^2 $

Defining $ \mathbf{e} = vec \left ( E \right ) $, Namely vectorizing the matrix, and defining a matrix $ A $ defined the proper usage of the weights $ {w}\_{\mathbf{rs}} $, Namely put them in the correct entry at each row per pixel the above could be rewritten as:

$$ \mathbf{e} = \arg \max\_{\mathbf{e}} {\left ( \mathbf{e} - A\mathbf{e} \right ) }^{T} \left ( \mathbf{e} - A\mathbf{e} \right ) = \arg \max\_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) $$

Defining $ B = I - A $ yields:

$$ \mathbf{e} = \arg \max\_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) = \arg \max\_{\mathbf{e}} {\mathbf{e}}^{T} {B}^{T} B \mathbf{e} $$

Defining $ L = {B}^{T} B $ , namely $ L , is a Symmetric Positive Definite Matrix yields:

$$ \mathbf{e} = \arg \max\_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e} $$

Adding the equality constraints using $ C \mathbf{e} = \mathbf{t} $ where $ \mathbf{t} $ is vectorization of all "Reference Pixels"

All in all this yields a Classic Quadratic Programming problem given by:

$$ \mathbf{e} = \arg \max\_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e}, \\; s.t. \\; C \mathbf{e} = \mathbf{t} $$

Few notes:

1. The matrix $ L $ is Symmetric and Positive Definite matrix and usually sparse (Assuming "Small Neighborhood").
2. The matrix $ L $ wast built by the Matrix $ I - A $ which each row of it was normalized to be zero (Each row of $ A $ is normalized to 1 ).

Now two things are needed:

1. Optimized fast algorithm to solve this problem utilizing its properties.
2. Assuming the image is large, are the methods to solve this problem by blocks to avoid memory limits?
> 5 votes

# Answer
$\newcommand{\be}{\mathbf{e}}\newcommand{\bL}{\mathbf{L}}\newcommand{\bC}{\mathbf{C}}\newcommand{\bt}{\mathbf{t}}\newcommand{\bl}{\mathbf{λ}}$Given Roy's formulation, we can solve this exactly without the need to invoke a QP solver.

To see why, we can add the constraint into the objective function using a Lagrange multiplier. Formally, let $$f(\be, \bl) = \be' \bL \be + \bl'(\bC\be - \bt)$$ be the cost function for a given solution $\be, \bl$ where $\mathbf{x}'$ indicates the transpose of $\mathbf{x}$. Dispite this being a quadratic function of $\be$ and linear function of $\bl$ there exists a unique solution that can be found by solving a system of linear equations.

To see why, let's first compute the gradients. The gradients of our unknowns are given by$$\begin{align\*}\frac{\partial f}{\partial \be} &= 2\bL\be + \bC'\bl\\ \frac{\partial f}{\partial \bl} &= \bC\be - \bt.\end{align\*}$$ Now to optimize for each parameter we see this is another system of linear equations, $$\begin{bmatrix}2\bL & \bC' \\ \bC & \mathbf{0} \end{bmatrix}\begin{bmatrix}\be \\ \bl \end{bmatrix} = \begin{bmatrix}\mathbf{0} \\ \bt \end{bmatrix}$$

The unique solution (provided that $\bL$ and $\bC\bL^{-1}\bC'$ are non-singular) for $\be$ and $\bl$ are determined by $$\begin{align\*}\hat{\be} &= -\frac{1}{2} \bL^{-1}\bC'\bl\\ \hat{\bl} &= -2(\bC \bL^{-1} \bC')^{-1}\bt.\end{align\*}$$

Solving this system in practice may still be an issue, however modern linear algebra libraries, such as BLAS or MKL, have built-in parallelization that can drastically speed things up.
> 3 votes

# Answer
It sounds like you want inpainting, i.e., filling in missing parts of an image as best as possible (consistent with a cost function). There's a tremendous amount of research that's been done on schemes for inpainting. I suggest you start by reading up on the standard schemes for this. See also Photoshop's content-aware fill feature, which is another name for a similar functionality.

See also https://stackoverflow.com/q/8645515/781723 and https://stackoverflow.com/q/11338164/781723 and https://stackoverflow.com/q/2530449/781723

So, rather than trying to invent your own method for inpainting, you might want to try using an existing method for inpainting (for filling in the non-anchor pixel values). Since the inpainting problem has been studied so extensively in the literature, existing methods might perform better than anything you can invent in a few weeks.
> 0 votes

---
Tags: optimization
---


title: Grammar generating odd number of 1s

text:
# Question
Title: Grammar generating odd number of 1s
I have the language $L = \\{w ∈ \\{0, 1, 2\\}^∗ \mid \text{the number of 1s in $w$ is odd}\\}$.

I am stuck halfway through this process.

I have

$$ \begin{align\*} &A \to 0A \mid \epsilon \\ &B \to 2B \mid \epsilon \\ &C \to AB \mid BA \end{align\*} $$

This should take care of 0s and 2s.

Now I have this, but I'm not sure if this is right

$$ \begin{align\*} &X \to 1Y \mid Y1 \\ &Y \to YC1C1 \mid C \mid \epsilon \end{align\*} $$

# Answer
> 2 votes
I would split the language in a part that assures that the number of 1s is odd (like, one 1), and another part of the language that **maintains** that. Similar to induction. So the first step is to write

$$S \rightarrow A1A$$

This makes sure there is at least one $1$ in our grammar, and $A$ is must maintain that. Any number of $0$s or $2$s have no effect, as well as the empty string:

$$A \rightarrow 0A \mid A0$$ $$A \rightarrow 2A \mid A2$$ $$A \rightarrow \lambda$$

However, if $A$ contains a $1$, it must contain at least another one. How can we enforce this? Simple! We re-use $S$, which already enforces this:

$$A \rightarrow 1S\mid S1$$

Note that I made every rule symmetrical regarding order. This is not a good practice in general when writing grammars for actual parsing, as it leads to highly ambiguous grammars. However here the focus is on getting the requirements right, so having not to worry about order at all makes it a bit easier.

# Answer
> 2 votes
Here is a simpler approach, which converts a DFA to a grammar:

$$ \begin{align\*} &S\to 0S \mid 2S \mid 1A \\ &A\to 0A \mid 2A \mid 1S \mid \epsilon \end{align\*} $$

Here $S$ generates all strings with an odd number of 1s, and $A$ generates all strings with an even number of 1s. You can check that the grammar is unambiguous.

---
Tags: formal-grammars
---


# Question
Title: Which implementation for the Maclaurin Series for the cosine function is better?
*First, sorry if this post is off-topic. I consider it too analytic for stack overflow.*

> In Numerical Analysis subject I must explain which one is better (has less error). The recursive implementation seems to be better with the inputs I have used, but I don't know the reason.
>
> Can someone explain to me which one is better and why? Having in mind round-off error and loss of significance using doubles.

Iterative implementation:

$$\cos{x} = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \ ... \ + (-1)^n\frac{x^{2n}}{(2n)!}$$

Recursive implementation:

$$y\_{n+1} = (-1)^n$$ $$y\_{k} = \frac{y\_{k+1}x^2}{(2k)(2k-1)} + (-1)^{k-1}, \ \text{for} \ k=n,\ n-1,\ n-2,\ ... \ 1$$

# Answer
> 1 votes
The main problem with the iterative approach is that the terms of the series get smaller and smaller with increasing index, so if you sum terms from 1 up, you eventually end up adding values of very small magnitude to accumulated sums of much larger magnitude. When done using floating-point arithmetic, that's pretty much the same as simply discarding terms after some point. The recursive approach sums the same terms, but in reverse order, so all the small terms get a chance to accumulate into larger sums before the larger terms get added; this lets the smaller terms actually contribute to the final sum.

I suspect that the way the recursive approach builds up the larger factorials in small steps also helps produce more accurate sums.

---
Tags: numerical-analysis, error-estimation
---


title: Reduction from $L$ to $L_{TM}$

text:
# Question
Title: Reduction from $L$ to $L_{TM}$
> Let $L$ be the language of all the words with the shape $\<M\_1,M\_2,w\>$ such that $M\_1,M\_2$ are turing machines that accepts $w$, show that $L$ isn't decidable.

I thought to use reduction from $L\_{TM}=\\{\<M,w\>\mid M \text{ accepts } w\\}$

how can I defined the function $f$ ?

# Answer
> 1 votes
If $L$ were decidable, then you could make a decider for $A\_{TM}=\\{\langle M, w\rangle\mid M\text{ accepts }w\\}$ by deciding $\langle M, M, w\rangle$. We know, however that that's impossible, since $A\_{TM}$ is undecidable.

---
Tags: turing-machines, reductions
---


# Question
Title: What was the major breakthrough between Hoare-Floyd logic and Scott–Strachey semantics?
I'm reading through a commentary on Milner's "The use of machines to assist in rigorous proof" by Mike Gordon. In this paper, he explains how LCF was born from the ideas of denotational semantics by Dana Scott and Strachey.

It seems to me that Floyd-Hoare logic wasn't enough for developing LCF, but I'm not sure why this is the case. At the end, in Hoare logic we deal with program states that satisfy some precondition $P$ and that through a relation $r$ conform to some postcondition $Q$ and I can provide a formula for this. Wikipedia claims that denotational semantics:

> is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called denotations) that describe the meanings of expressions from the languages.

I'm familiar with some intuitions on how for instance recursion is modeled in this approach as a fixed point of some relation while in Hoare logic I didn't really remember dealing with recursion. Still both approaches seem to try to describe relations between inputs and outputs using mathematical relations.

**Question**

So what is it that made a difference between Hoare logic and denotational semantics? Does denotational semantics manage better some complexities of programs? If so, please illustrate with an example.

Maybe the following quote of Milner referring to denotational semantics is interesting to guide your answer:

> I could write down the syntax of a programming language in this logic and I could write the semantics in the logic.

# Answer
> 10 votes
I don't know why people didn't develop Hoare logics for lambda-calculi earlier. The first work to get this right was Honda et al's

A Compositional Program Logic for Polymorphic Higher-Order Functions

There were some earlier attempts before this, but they didn't quite nail the problem, for example: how do you denote the value of a functional program? What piece of syntax corresponds to the function space constructor? There are a couple of little things that need to be gotten right.

Let me speculate: maybe the main issue was that Hoare logic was typically concerned with stateful computation. If you combine state and higher-order functions, you immediately have to deal with aliasing, e.g. programs like

$$\lambda x^{\mathsf{Ref(Nat)}}.\lambda y^{\mathsf{Ref(Nat)}}.(x := !x+1; y := !y+1),$$ as well as local store and recursion through the store. These were only solved in the early 2000s in works like *An observationally complete program logic for imperative higher-order functions* (recursion through the store); *A logical analysis of aliasing in imperative higher-order functions* (aliasing), *Logical Reasoning for Higher-Order Functions with Local State* (full local store). At the same time Separation logic tackled the aliasing problem form a different angle.

This work has been implemented in Coq by A. Charguéraud in his work, and that is also used in the Javascript semantics now.

---
Tags: hoare-logic, automated-theorem-proving, denotational-semantics
---


# Question
Title: Looking for an "intuitive" regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$
Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \\{0,1\\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|\_1$ the number the symbol $1$ occurs in $w$ and by $|w|\_0$ the number the symbols $0$ occurs, then $$ L = \\{ w \in \Sigma^{\ast} \mid 2|w|\_1 + |w|\_0 \equiv 0 \pmod{3} \\}. $$ I know this language to be regular, as it is quite easy to give an automaton for it. I also got a (quite complicated) regular expression for it using an algorithm going from the automaton. But is there any regular expression that is easy in the sense that it gives some insight into why it is a regular expression for the language?

Not that for example for the language $\\{ w \mid |w|\_0 \equiv 0 \pmod{3} \\}$ it is quite easy to give a regular expression, it would be $1^{\ast}(01^{\ast}01^{\ast}01^{\ast})^{\ast}$, or for $\\{ w \mid |w| \equiv 0 \pmod{3} \\}$ as it would be $(\Sigma\Sigma\Sigma)^{\ast}$. But the above language somehow combines these conditions.

# Answer
> 5 votes
The automaton for that language is, as you say, extremely simple: it consists of a triangle, in which 0s move clockwise and 1s move counterclockwise:

A classic way to turn this into a regular expression is to eliminate states one at a time, converting transitions through each state into regular expressions. Eliminating state 2 is easy since there are no epsilon transitions or self-loops, so we end up with:

$$\begin{align}s0 \to s0&: 10 \\ s0 \to s1&: 0 + 11 \\ s1 \to s0&: 1 + 00 \\ s1 \to s1&: 01 \\ \end{align}$$

When we then eliminate state 1, we produce a relatively simple regular expression:

$$(10 + (0+11)(01)^\*(1+00))^\*$$

Is that regex intuitive? I guess that depends on your intuitions. $10$ and $01$ both have no effect on $2|w|\_1 + |w|\_0 \pmod{3}$; $0+11$ adds 1, and $1+00$ subtracts 1. So the regex definitely shows the path around the three possible values of $2|w|\_1 + |w|\_0 \pmod{3}$

# Answer
> 1 votes
To complement rici's answer, I just add a run of Kleene's algorithm, giving another regular expression (starting from his automaton):

\begin{align\*} R^{-1}\_{00} & = \varepsilon \\ R^{-1}\_{01} & = 0 \\ R^{-1}\_{02} & = 1 \\ R^{-1}\_{11} & = \varepsilon \\ R^{-1}\_{10} & = 1 \\ R^{-1}\_{12} & = 0 \\ R^{-1}\_{22} & = \varepsilon \\ R^{-1}\_{21} & = 1 \\ R^{-1}\_{20} & = 0 \end{align\*} and further: \begin{align\*} R^2\_{00} & = R\_{02}^1 (R\_{22}^1)^{\ast} R^1\_{20} | R\_{00}^1 \\ R^1\_{00} & = R\_{00}^0 (R\_{11}^0)^{\ast} R^0\_{10} | R\_{00}^0 = \varepsilon (10|\varepsilon)^{\ast} 1 | \varepsilon = (10)^{\ast} 1 | \varepsilon \\ R^0\_{00} & = R\_{00}^{-1} (R\_{00}^{-1})^{\ast} R\_{00}^{-1} | R\_{00}^{-1} = \varepsilon (\varepsilon)^{\ast}\varepsilon | \varepsilon = \varepsilon \\ R^0\_{11} & = R\_{10}^{-1} (R\_{00}^{-1})^{\ast} R\_{01}^{-1} | R\_{11}^{-1} = 1 (\varepsilon)^{\ast} 0 | \varepsilon = 10 | \varepsilon \\ R^0\_{10} & = R\_{10}^{-1} (R\_{00}^{-1})^{\ast} R\_{00}^{-1} | R\_{10}^{-1} = 1 (\varepsilon)^{\ast} \varepsilon | 1 = 1 \\ R^1\_{02} & = R^0\_{10} (R\_{11}^0)^{\ast} R\_{12}^0 | R\_{02}^0 = 1 ( 10|\varepsilon )^{\ast} (11 | 0) | 1 = ( 1 (10)^{\ast}(11 | 0)) | 1\\ R^0\_{12} & = R^{-1}\_{10} (R\_{00}^{-1})^{\ast} R\_{02}^{-1} | R\_{12}^{-1} = 1 (\varepsilon)^{\ast} 1 | 0 = 11 | 0 \\ R^0\_{02} & = R^{-1}\_{00} (R\_{00}^{-1})^{\ast} R\_{02}^{-1} | R\_{02}^{-1} = \varepsilon (\varepsilon)^{\ast} 1 | 1 = 1 \\ R^1\_{22} & = R^0\_{21} (R\_{11}^0)^{\ast} R\_{12}^0 | R\_{22}^0 = (00 | 1)(10|\varepsilon)^{\ast} (11|0) | (01|\varepsilon) = (00 | 1)(10)^{\ast} (11|0) | (01|\varepsilon) \\ R^0\_{22} & = R\_{20}^{-1} (R\_{00}^{-1})^{\ast} R\_{02}^{-1} | R\_{22}^{-1} = 0 (\varepsilon)^{\ast} 1 | \varepsilon = 01 | \varepsilon \\ R^0\_{21} & = R^{-1}\_{20} (R\_{00}^{-1})^{\ast} R\_{01}^{-1} | R\_{21}^{-1} = 0 (\varepsilon)^{\ast} 0 | 1 = 00 | 1 \\ R^1\_{20} & = R^0\_{21} (R\_{11}^0)^{\ast} R\_{10}^0 | R\_{20}^0 = (00|1)(10|\varepsilon)^{\ast} 1 | 0 = (00|1)(10)^{\ast}1 | 0 \\ R^0\_{20} & = R^{-1}\_{20}(R\_{00}^{-1})^{\ast} R\_{00}^{-1} | R\_{20}^{-1} = 0 (\varepsilon)^{\ast} \varepsilon | 0 = 0 \end{align\*} so we have all subterms to give the final answer $$ R\_{00}^2 = ( ( 1 (10)^{\ast}(11 | 0)) | 1 ) ( (00 | 1)(10)^{\ast} (11|0) | (01|\varepsilon) )^{\ast} ( (00|1)(10)^{\ast}1 | 0 ) | ( (10)^{\ast} 1 | \varepsilon ) $$ which is unfortunately much more complicated.

---
Tags: formal-languages, automata, regular-languages, regular-expressions
---


# Question
Title: Is $\{ aa^nb^n : n \ge 0 \}$ a non-regular language?
I know that $\\{a^nb^n : n\geq 0\\}$ is a non-regular language. Would adding another $a$ so that it is $\\{ a^{n+1}b^n : n \geq 0\\}$ change things? Would this still be a non-regular language?

# Answer
> 1 votes
You are asking if $a^{n+1}b^n$ is a regular language.

First try to think about the reason why $a^nb^n$ isn't regular.

What would make $n+1$ appearances of $a$ and then $n$ appearances of $b$ in the input different if you can't check $a^nb^n$?

What have you tried so far?

Check this reference https://www.cs.wcupa.edu/rkline/fcs/re-pump.html

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


# Question
Title: Prove a language $A_{PTM}$ is not BPP-Complete
I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer science professors about the problem and he proposed the following proof sketch:

*Proof (sketch):*

We know $A\_{TM} \le\_m A\_{PTM}$.

Construct a decider $D$ that given a Probabilistic Turing Machine $M$ and a string $x$, $D$ accepts if $M$ accepts $x$, and rejects otherwise. As $A\_{TM} \le\_m A\_{PTM}$, a solution to $A\_{PTM}$ would yield a solution to $A\_{TM}$. However, $A\_{TM}$ is not decidable, so therefore, $D$ cannot exist.

*End of Proof*

Where I am confused is how does this show $A\_{PTM}$ is not BPP-Complete? As an acceptance problem, I would think $A\_{PTM}$ is BPP-Hard, but I don't see how this shows it is not in BPP.

# Answer
To show that a language is not BPP-complete, it suffices to do one of the following:

* Show that the language is not in BPP.
* Show that the language is not BPP-hard.

Your language seems to be undecidable, and so in particular, not in BPP.
> 1 votes

---
Tags: turing-machines, proof-techniques, probability-theory
---


# Question
Title: How do I show that whether a PDA accepts some string w is decidable? or undecidable?
Currently studying for an Automata Theory final and can't find an answer to this question anywhere.

Can you simply let w = w!w and show that it is undecidable that way? Like this here: How do I show that whether a PDA accepts some string $\\{ w!w \mid w \in \\{ 0, 1 \\}^\*\\}$ is undecidable?

Or do I have to show decidability for arbitrary string w.

Thanks

# Answer
> 1 votes
Given a PDA and a string $w$, there are several algorithms that decide whether the PDA accepts $w$. In fact, for a fixed PDA, such algorithms run in time $O(|w|^3)$ or less. The most well-known algorithm is the CYK algorithm. Although CYK expects the language in the form of a context-free grammar rather than in the form of a PDA, there is an algorithm that converts a PDA to a context-free grammar generating the same language.

I expect every decent textbook on automata theory to contain a proof that the *acceptance problem* for PDAs (given a PDA and a string, determine whether it accepts the string) is decidable, say along the lines above.

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


title: Is $A_{PTM}$ a BPP-complete language?

text:
# Question
Title: Is $A_{PTM}$ a BPP-complete language?
The language $A\_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine.

$A\_{PTM}=$ { $\<M, x\> | M$ on input $x$ accepts with an error probability less than or equal to 1/3}

Basically, given a probabilistic Turing machine $P$ and string $x$, a decider $D$ simulates $P$ on $x$ and outputs accept if $P$ accepts on $x$, and rejects otherwise.

I claim $A\_{PTM}$ is BPP-hard because BPP is the class of languages which are accepted a success probability of at least $2/3$. If the PTM for any BPP language is given as an argument to the decider $D$, then it will output accept if the PTM it was passed accepts, and reject otherwise. I know this is far from a formal proof, but I am just trying to understand the idea. Is this correct?

# Answer
First, $A\_{PTM}$ as you defined it is not even decidable (so it isn't in BPP), since your simulation might not halt.

The naive attempt at a BPP complete language is:

$A\_{PTM}=\left\\{\left(\langle M\rangle,x, 1^t\right) \big| M \text{ accepts $x$ in $\le t$ steps with probability $\ge \frac{2}{3}$} \right\\}$.

Note that there is no notion of "error" in the definition of $A\_{PTM}$, as there are no right answers, you decide whether or not to include some triplet in your language.

You can show that $A\_{PTM}$ is indeed BPP-hard (I leave the reduction details for you). The problem is that we do not know if $A\_{PTM}\in \mathsf{BPP}$. Simply simulating $M$ on $x$ for $t$ steps and outputing its answer won't work. Imagine $M$ accepts $x$ after $t$ steps with probability $\frac{1}{2}$, then although $(M,x,t)\notin A\_{PTM}$, you accept it with probability $\frac{1}{2}$, while you should be accepting with probability $\le \frac{1}{3}$.

In fact, $A\_{PTM}$ is $\mathsf{PP}$ complete, so it is unlikely to lie in $\mathsf{BPP}$. The existence of complete problems for BPP is currently an open question in complexity. You can check this question from cs-theory, which talks about why it is harder to find complete problems for classes like BPP.
> 2 votes

---
Tags: proof-techniques, probabilistic-algorithms
---


# Question
Title: Why can we drop the superscripts in the Floyd Warshall algorithm?
In the lecture notes, our professor mentioned that we can take down the space taken by the FW algorithm from $O(n^3)$ to $O(n^2)$ by dropping all the superscripts in the matrices (i.e. use one $n\times n$ array $D$).

I just want to check my understanding, is it because by default $D^k=D^{k-1}$ except for the values $i,j$ where $d\_{ik}^{k-1}+d\_{kj}^{k-1}\<d\_{ij}^{k-1}$ where we set $d\_{ij}^k=d\_{ik}^{k-1}+d\_{kj}^{k-1}$ but in essence we are using the values in the $D^{k-1}$ matrix to update itself?

However, what if we change one value, say $d\_{i\_1j\_1}^k$ in the $kth$ iteration but then we need to reuse the value $d\_{i\_1j\_1}^{k-1}$ later on in the same $kth$ iteration, wouldn't it be lost?

# Answer
> 5 votes
Basically in iteration k no entry $d\_{ij}$ can change if $i=k$ or $j=k$. Since you update the entries in $D$ by considering $d\_{ik}$ and $d\_{kj}$ you can do all these updates in-place.

However there is an even simpler argument if you only want to show that the algorithm requires $O(n^2)$ space. At every iteration $k$ the values in $D^k$ only depend on the previous matrix $D^{k-1}$. Therefore it is enough to store the matrix $D^{k-1}$ of the previous iteration, use it to fill the next matrix $D^k$ and then you can safely discard $D^{k-1}$. So you only ever need to keep two matrices in memory and arrive at $O(n^2)$ space. Of course no sensible implementation would actually do this but it is enough to show the space bounds.

# Answer
> 1 votes
The reason is that the numbers $d\_{ik}$ and $d\_{kj}$ do not change when computing matrix $D^k$; distances either starting or ending in $k$ cannot be improved by looking for a path that travels via $k$ (or equivalently, $d\_{kk}=0$).

The right-hand side of the instructions of the algorithm only involve these numbers on the $k$-th row and column. The algorithm will not change them. The other numbers are recomputed but not used, so can be overwritten in $D^{k-1}$ to get $D^k$.

---
Tags: dynamic-programming, shortest-path
---


title: Optimal strategy for an abstract game

text:
# Question
Title: Optimal strategy for an abstract game
I've been given the following problem in an interview (that I've already failed to solve, not trying to cheat my way past): The game starts with a positive integer number $A\_0$. (E.g. $A\_0 = 1234$.) This number is converted to binary representation, and $N$ is the number of bits set to $1$. (E.g. $A\_0 = b100\ 1101\ 0010$, $N = 5.$)

*Player 1* chooses a number $B\_0$ lesser than $A\_0$. $B\_0$ must have only one bit set to 1. (E.g. $B\_0 = b10\ 0000\ 0000 = 512$.) Let $A\_1 = A\_0 - B\_0$. (E.g. $A\_1 = 1234-512 = 722 = b10 1101 0010$.) A move is **valid** if $B\_0$ satisfies the previous constraints, and if the number of bits set in $A\_1$ is still **equal to N**.

*Player 2* continues from $A\_1$ by choosing a valid $B\_1$, then *player 1* continues from $A\_2$, and so forth. A player loses if they have no valid moves left.

Assuming both players play optimally, determine the winning player using a reasonably efficient method. (In my problem definition, the constraints on this were that the program has to be able to deliver a solution for a few million input numbers that fit into a signed 32-bit integer.) That is, the solution doesn't need to be fully analytical.

---

My personal interest here is figuring out whether the expectation of me to have found and implemented the correct solution with no way feedback on correctness in the 120 minutes I was given was reasonable; or if this was one of those "let's see if they've seen this puzzle before" questions.

I'd failed because I chose to implement what seemed like a reasonable strategy, that gave me correct results for the few test cases that I've been given up front, wasted too much time making this run fast, and ended up handing in incorrect full output as my time ran out.

In retrospect I should've implemented a brute-force search and memorized partial solutions for small starting numbers, but hindsight is always 20/20. I'm curious however if there's a different common approach that eluded me as a flunkee.

# Answer
> 21 votes
Take a moment for yourself to realize that if we can only substract a power of two, and the popcount can't change we have to subtract $01$ in a position where the other number is $10$. The result of that is always $01$ in that position, and the number doesn't change anywhere else.

In other words, the game is a series of swaps of $10 \rightarrow 01$, and the game ends if all ones are on the right hand side. Note that it's impossible for this game to end early - you can not get stuck. You will always end up at a position where all zeroes are on the left, and all ones are on the right.

So the only determining factor in a game is how many swaps it takes to get to the state where all ones are on the right, and there is no winning or losing strategy. The parity of the number of swaps it takes is the only determining factor.

So how many swaps does it take? Note that $1$s can't cross eachother, so if we numbered them and tracked them through swaps they'd remain in the same order in the final state. Each swap brings them one closer to their final position.

So if the $i$th $1$ (counting from the right, the rightmost $1$ is the $0$th $1$) is in position $k$ from the right, it needs $k - i$ swaps to get to its correct position. This gives us an algorithm to count the amount of swaps required:

```
i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

```

We now can just look at the parity of `total` to see who wins. Time complexity is $O(\log n)$.

# Answer
> 6 votes
Note from @orlp's answer that we want the parity of the sum of the displacements from the start position to the end position. Let's annotate this:

```
       9876543210
       9 76 4  1    (positions at start)
start: 1011010010
end:   0000011111
            43210   (positions at end)

```

So we want

```
  ((1 - 0) + (4 - 1) + (6 - 2) + (7 - 3) + (9 - 4)) & 1
= ((1 + 4 + 6 + 7 + 9) - (0 + 1 + 2 + 3 + 4)) & 1
= ((1 + 0 + 0 + 1 + 1) - (0 + 1 + 0 + 1 + 0)) & 1

```

The first part is just the parity of the number of bits in the odd positions. You can mask that by taking the maximum unsigned integer, dividing by 0b11 and negating.

```
= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (0 + 1 + 0 + 1 + 0)) & 1

```

The second part is the parity of **half** the number of bits in `x`.

```
= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (bitcount(x) >> 1)) & 1

```

`bitcount` can either use the hardware `popcnt` instruction, or can be implemented manually utilizing that only either the last or second-to-last bit is needed, with fast reductions like this.

# Answer
> 5 votes
One way to solve such a problem is as follows:

* Find the solution for a few simple values using the "memoized brute-force" approach you are suggesting.
* Guess the answer (which positions are winning and which are losing).
* Try to prove your answer. If you succeed, great. Otherwise, try to find a counterexample, and use it to guess another answer. Here it could be helpful to solve a few more cases.

It is really hard to say how much time that takes. However, in interviews you are not necessarily expected to find the solution. Rather, the interviewers want to know how you *approached* solving the problem, and what progress you managed to make.

---
Tags: algorithms, optimization
---


title: Lower bound for co-NP

text:
# Question
Title: Lower bound for co-NP
Suppose someone will prove lower bound (for NTM) for co-NP, say exp(n/d) for some constant d. Would it in some way imply lower bound (for DTM) for NP?

Thank you

# Answer
> 2 votes
Yes. If you can decide all languages in NP on a DTM in polynomial time, then P = NP = co-NP, i.e., you can also decide all languages in co-NP on a DTM in polynomial time, basically by negating the output of the DTM. Taking the converse... if there exists a language $L$ in co-NP that can't be solved in polynomial time on a DTM, then there exists a language $L'$ in NP that can't be solved in polynomial time on a DTM (for instance, you can take $L'$ to be the complement of $L$).

---
Tags: complexity-theory
---


# Question
Title: Proof Check: The class L is closed under concatenation
I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation. The basic idea of my proof is this: given a word, to check if it's in $L\_1L\_2$, simply look at all possible $n+1$ ways to slice the word into 2 parts and check if the first part belongs to $L\_1$ and if the second belongs to $L\_2$.

Because both of the languages can be decided in logarithmic space, checking one after the other can also be done in logarithmic space.

Is my idea correct? Thanks.

# Answer
> 0 votes
The idea is correct, but the proof is not finished. It lacks an implementation on the Turing Machine, and sometimes that can be quite tricky. Given a "slice" how are the halves "marked" as belonging to the first and second part, so we can run the two subroutines for $L\_1$ and $L\_2$? How are the consecutive slices generated?

---
Tags: complexity-theory, formal-languages, turing-machines, closure-properties
---


# Question
Title: How a NTM guessing depends on the input?
After looking at the definition of nondeterministic TMs, it seems that, while guessing, the machine could go to at most $|Q|\times | \Gamma |$ configurations, being in a particular one.

However, if we look at several concrete NTMs, the guessing part depends on the size of the input, i.e. it's not bounded. For instance, let's take this machine finding Hamiltonian Path here: How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

A part of the algorithm says "Each number in this list is non-deterministically selected to be from 1 to x.", where x is the number of nodes of the graph(and we may have arbitrarily big number of nodes).

I know the answer is perhaps trivial, but I couldn't find it.

# Answer
Suppose that the input has length $n$, and suppose that the machine already knows $n$. In order to non-deterministically choose a number from 1 to $n$, it performs the following algorithm:

* Choose $m = \lceil \log\_2 n \rceil$ bits non-deterministically, and interpret them as a number $x$ from $0$ to $2^m-1$.
* Increase $x$ by one.
* Reject if $x \> n$.

The first step is implemented by a loop.
> 2 votes

---
Tags: algorithms, graphs, turing-machines, hamiltonian-path
---


title: Finding a loop invariant

text:
# Question
Title: Finding a loop invariant
the following pseudo code returns the nth Fibonacci number:

```
 if n = 0 then
    return 0
 a ← 1
 b ← 1
 for i = 1 to n − 1 do
     c ← b − i
     b ← c + a
     a ← c + 2*i + 1
 return b

```

I am trying to find any loop invariant for the variables a and b, (as i understand it has to be valid before and after the loop, but i can't seem to be able to come up with anything, except maybe `b >= i`, but I'm not sure that counts as an invariant). As far as I get it, simply saying `b = b - i + a` wouldn't really mean anything. Any help on the subject would be greatly appreciated.

# Answer
As we already know, the loop iteratively calculates the nth Fibonacci number, so it naturally follows that the loop invariant should contain $b = \mathsf{fib}(i)$ condition. But that is not sufficient for us, because the computation depends on the variable `a`, and we don't need `c`, because it is initialized in the loop body.

The line `b ← c + a` actually gives us a hint as to what the condition on `a` should we impose: after this line $b$ must be equal to $\mathsf{fib}(i+1)$. Now, from the expression for `c` and the expression $\mathsf{fib}(i+1) = \mathsf{fib}(i) + \mathsf{fib}(i-1)$ we easily obtain the condition for `a`: $a = \mathsf{i + fib(i-1)}$.

If we rewrite the for loop into an equivalent while loop, we'll get a loop invariant:

$$a = i + \mathsf{fib}(i-1) \wedge b = \mathsf{fib}(i) \wedge i \le n.$$

Here is how we can prove that the loop actually does the job:

```
{a = i + fib(i-1) /\ b = fib(i) /\ i <= n}
while i < n do
  {a = i + fib(i-1) /\ b = fib(i) /\ i < n}
  {a = i + fib(i-1) /\ b = fib(i) /\ b − i = fib(i) - i /\ i < n}
  c ← b − i
  {a = i + fib(i-1) /\ b = fib(i) /\ c = fib(i) - i /\ i < n}
  {a = i + fib(i-1) /\ c + a = (fib(i) - i) + (i + fib(i-1)) /\ c = fib(i) - i /\ i < n}
  {a = i + fib(i-1) /\ c + a = fib(i+1) /\ c = fib(i) - i /\ i < n}
  b ← c + a
  {a = i + fib(i-1) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {c + 2*i + 1 = fib(i) - i + 2*i + 1 /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {c + 2*i + 1 = fib(i) + (i+1) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  a ← c + 2*i + 1
  {a = (i+1) + fib(i) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {a = (i+1) + fib((i+1)-1) /\ b = fib(i+1) /\ (i+1)-1 < n}
  i ← i + 1
  {a = i + fib(i-1) /\ b = fib(i) /\ i <= n}
{a = i + fib(i-1) /\ b = fib(i) /\ i <= n /\ i >= n}
{a = i + fib(i-1) /\ b = fib(i) /\ i = n}
{b = fib(n)}

```
> 3 votes

---
Tags: loop-invariants
---


# Question
Title: Is a matching $M$ maximum iff the graph doesn't have an augmenting path wrt $M$?
> Berge's theorem: a matching $M$ is maximum if and only if the graph doesn't have an augmenting path with respect to $M$.

I don't understand this theorem. For instance the following matching is maximum but has an augmenting path, doesn't it?

The matching $M$ is in gold here and the augmenting path is the one in dotted lines.

# Answer
> 2 votes
An augmenting path must alternate between gold and black, *starting and ending with black edges*. In this way, if you replace the gold edges with the black edges, you obtain a larger matching. This argument shows that a matching can only be maximum if there is no augmenting path, and Berge's theorem states the inverse direction: if a matching has no augmenting path then it is maximum.

---
Tags: matching
---


# Question
Title: What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)
I'm reading the chapter on dynamic arrays in The Algorithm Design Manual book. Here is the excerpt from the book:

> Actually, we can efficiently enlarge arrays as we need them, through the miracle of dynamic arrays. Suppose we start with an array of size 1, and double its size from m to 2m each time we run out of space. This doubling process involves allocating a new contiguous array of size 2m, copying the contents of the old array to the lower half of the new one, and returning the space used by the old array to the storage allocation system. The apparent waste in this procedure involves the recopying of the old contents on each expansion. How many times might an element have to be recopied after a total of n insertions? Well, the first inserted element will have been recopied when the array expands after the first, second, fourth, eighth, . . . insertions. It will take log2 n doublings until the array gets to have n positions. However, most elements do not suffer much upheaval.
>
> **Indeed, the (n/2 + 1)st through nth elements will move at most once and might never have to move at all**. If half the elements move once, a quarter of the elements twice, and so on, the total number of movements M is given by
>
> Thus, each of the n elements move only two times on average, and the **total work of managing the dynamic array is the same O(n)** as it would have been if a single array of sufficient size had been allocated in advance!
>
> **The primary thing lost using dynamic arrays is the guarantee that each array access takes constant time in the worst case.** Now all the queries will be fast, except for those relatively few queries triggering array doubling. What we get instead is a promise that the nth array access will be completed quickly enough that the total effort expended so far will still be O(n). Such amortized guarantees arise frequently in the analysis of data structures.\]

I don't understand why (n/2 + 1)st through nth will move at most once and might never have to move at all and total work of managing the dynamic array. Can someone please explain?

Also, why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays?

# Answer
> 4 votes
All that matters is the equation you are quoting. Here is another way to see it. Suppose you have $n$ items. You push one item at a time to the end of an initially empty array. When the array reaches size $2^k$ for some $k\<\log\_2 n$, you reallocate the array to size $2^{k+1}$ and move all items between $0$ and $2^k-1$ to the new location. The total number of item moves is:

$$ M=1+2+2^2+\cdots+2^{\lfloor\log\_2n\rfloor}=2^{\lfloor\log\_2n\rfloor+1}-1\le2^{1+\log\_2n}-1=2n-1 $$

If you fill the array in a random order, the total number of item moves is bounded by $2n$, too. In all, the time complexity of filling an array of size $n$ is $O(n)$, no matter whether the array is dynamic or not.

> why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays

When you push an item to the end of an array of size $2^k$, you have to double the array and possibly copy $2^k$ existing items to a new location. This is not a constant-time operation. With dynamic array, each single operation is not always constant. However, such non-constant operations are so rare that the total number of operations to fill a dynamic array can still be $O(n)$.

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


# Question
Title: Data structure for testing all subsets of a query for membership
Is there a data structure that efficiently supports the following operations?

1. Add set
2. Query whether any subset of a set has been added.

This could be implemented with linear overhead by testing every added set during every query. Can it be implemented more efficiently? Small probabilities of false positives/negatives are acceptable (e.g. Bloom-filter style).

# Answer
Let's say all your sets are finite subsets of $\mathbb N$. Let $S\subseteq \mathcal P( \mathbb N)$ denote your set of sets.

You want two operations:

* $O\_1(S,s')$: For any $s'\subseteq \mathbb N$, add $s'$ to $S$
* $O\_2(S,s')$: For any $s'\subseteq \mathbb N$, is there some $s\in S$ so that $s\subseteq s'$?

---

Here are a few ideas to speed things up:

* You're going to test if a set if a subset of another a lot so you should probably keep the size $|s|$ of each set $s$ available in $O(1)$ so that when you need to test if $s\subseteq s'$, you start by checking if $|s|\le |s'|$ and if not, you can return false right away. And it you indeed have $|s|\le |s'|$, then you just run the normal slow test.
* Note that if you have $s\_1\in S$ and $s\_2\in S$, so that $s\_1\subseteq s\_2$, then if $s\_2\subseteq s'$, you also have $s\_1\subseteq s'$. So you don't need to keep $s\_2$ in $S$ for $O\_2$. So you can represent $S$ by a set of sets so that $s\in S$ and $s\subsetneq s'$ implies $s'\not \in S$. In other words, you only need to keep track of the sets in $S$ that are minimal for inclusion. This can be implemented pretty efficiently: When adding a set $s'$, for all sets $s\in S$ so that $|s|\le |s'|$ (ordered by increasing cardinal), if $s\subseteq s'$, then don't add $s'$ because it won't be minimal (or is already in $S$). Otherwise, add $s'$ and then among sets $s\in S$ so that $|s'|\<|s|$, remove those so that $s'\subseteq s$ (because they are no longer minimal).
* Keep a set $t$ that's equal to the union of all sets in $S$. Then, instead of running $O\_2(S,s')$, you can run $O\_2(S,s'\cap t)$ instead (because if for some $s\in S$, $s\subseteq s'$, then since $s\subseteq t$, $s\subseteq s'\cap t$ and, if $s\subseteq s'\cap t$, then $s\subseteq s'\cap t \subseteq s'$).

With these ideas in mind, I'd represent $S$ by a dictionnary (implemented as a doubly linked list of pairs $(key,value)$ with the keys in increasing order) $d$ so that $d(k)$ is a doubly linked list containing exactly the minimal (for inclusion) sets in $S$ of cardinal $k$.

```
O1(S,s')
  if O2(S,s')
    return
  if d(k) doesn't exist
    d(k) := new_doubly_linked_list()
  add(d(k),s')
  S.t := union(S.t, s')
  for each key k of d so that |s'|+1 <= k
    for s in d(k)
      if subset(s', s)
        remove s

_O2(S,s')
  for each key k of d so that k <= |s'|
    for s in d(k)
      if subset(s,s')
        return true
  return false

O2(S,s')
  return _O2(S,inter(S.t,s'))

```

(Notice that even though I didnd't do it explicitely in the code of `O1`, you can do a single traversal of the doubly linked list representing `d`)

I don't think this improves too much in the worst case but in average it should.
> 2 votes

---
Tags: data-structures
---