# Question
Title: Showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable
How would you go about showing that the language $L = \\{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \\}$ is decidable or undecidable?

Intuitively my thoughts are that you might be able to show that $\bar{L} = \\{\langle M, w \rangle\ |\ M$ moves left at most twice while computing $w \\}$ is undecidable as you wouldn't ever be able to definitively know if the machine will move left a third time so it would end up looping instead of rejecting. I don't know if that's on the right track though.

Thanks in advance!

# Answer
I strongly believe it is decidable, but I found it quite convoluted. I'll give a sketch of proof.

**Lemma**: Every Turing Machine that doesn't terminate either moves left at some point or is very silly.

Let $M\_\leftarrow$ be a TM that never moves left. If $M\_\leftarrow$ never moves left, we don't care about what it writes on the tape, because it can only ever read the last symbol it wrote. In particular, we may see $M\_\leftarrow$ as a finite transition system which set of states are the pairs $(q \in Q, \sigma \in \Sigma)$ where $q$ is the current state of $M\_\leftarrow$ and $\sigma$ is either the last symbol written by $M\_\leftarrow$ or the blank symbol if $M\_\leftarrow$ just moved to the right. Therefore, checking if the graph of the transition system is cyclic decides whether or not $M\_\leftarrow$ terminates, qed.

**Theorem**: $L$ is decidable.

Let $H$ be the problem of deciding whether or not a machine that never moves left terminates. By the lemma above, there exists a machine $M\_H$ that takes as input another machine $M$, some input $x$ and:

* if $M$ never moves left on input $x$, returns $\textsf{YES}$ if $M$ terminates and $\textsf{NO}$ otherwise,
* if $M$ on input $x$ moves left at some point, returns $\textsf{YES}$.

We will show that we can use $M\_H$ to construct a family of machines $M\_k$ that decides whether or not a machine moves left at least $k$ times. Let $\langle M, x \rangle$ be the input.

First of all, we have $M\_k$ construct a universal machine $U$, and use $U$ to compute $M\_H$ on input $M$. If the result is $\textsf{NO}$, it means that $M$ never moves left on input $x$: we accept $\langle M, x \rangle$. If the result is $\textsf{YES}$, it means that either $M$ terminates on input $x$ or moves left at some point.

We use $U$ to simulate $M$ on input $x$. After finitely many steps, either $M$ terminates or moves left. In the first case simply accept. If a left move happens, we save the current state of the tape, and return the result of $M\_{k-1}$ with the modified tape as input, which is by inductive hypothesis computable, qed.
> 1 votes

# Answer
It is decidable, and this is a *sketch* for an alternate proof (I leave out MANY details).

You can consider $\bar{ L } = \\{ \langle M, w \rangle \mid$ $M$ moves left at most 2 times on $ w \\}$, and prove that $\bar{L}$ is decidable.

To show that it is decidable, note that $M$ while scanning $w$ cannot go back and cross more than 2 symbols.

So while scanning symbol $a\_i$ at position $i$ of $w$ in state $q\_i$:

1. $M$ does more than 2 steps towards the left OR
2. $M$ after at most 5 steps moves right into position $i+1$ and enters a state that only depends on $a\_i,a\_{i-1},a\_{i-2}$

So you can build a DFA $D$ that is equivalent to $M$:

* the state of $M$, the content of the previous 2 cells $a\_{i-1}, a\_{i-2}$ are stored using internal states: in other words, the state of $D$ is identified by a triple:

$\langle q\_i, a\_{i-1}, a\_{i-2}\rangle \\;$ ($q\_i$ is a state of $M$)

* the transition table of $D$ is built in this way:

if the current symbol is $a\_i$, and the state is $\langle q\_i, a\_{i-1}, a\_{i-2} \rangle$ then simulate $M$ on string

$a\_{i-2} a\_{i-1} \[a\_i\]$ with head position $i$ and state $q\_i$

for at most 5 steps.

If $M$ moves left more than twice enter a special state of $D$ called $q\_R$, otherwise if $M$ moves right to position $i+1$, writing symbols $a\_{i-1}', a\_{i}'$ at positions $i-1,i$, and enters state $q\_j$, then the transition of $D$ will be:

$\delta(\langle q\_i, a\_{i-1}, a\_{i-2} \rangle, a\_i) \to \langle q\_j, a\_{i-1}', a\_{i}' \rangle$

For the special state $q\_R$ (which *is the only non-acceptance state*) simply set: $\delta( q\_R, a ) \to q\_R$

If for a pair $\langle q\_i, a\_{i-1}, a\_{i-2} \rangle, a\_i$ you find that $M$ halts, then the DFA can enter a special (accepting) state $q\_A$ in which $D$ ignores the rest of the input.

Finally you should also consider what happens at the end of $w$, i.e. consider the blank symbol $b$ as a tape symbol for $D$.

In this way you prove that $M$ on $w$ move left more than twice if and only if the DFA $D$ rejects the string $w \\; b^k$ (where $k$ is greater than the number of states of $D$) and thus is decidable.
> 0 votes

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


title: NP-hardness of an extention of 2 sat

text:
# Question
Title: NP-hardness of an extention of 2 sat
a 2 sat instance which is unsatisfiable and an integer k are given, decision problem is that: is it possible to delete k variables, also remove clauses contain them, in order to satisfy the 2-sat instance?? and optimization problem is that: find the minimum number of variables to remove to make the 2 sat instance satisfiable. I want to use reduction to show this problem is np-hard but I don't know which np-hard problem should be used. I appreciate if anyone could help me by the reduction or introduce me a reference (I searched but maybe I don't know the name of problem exactly)

please notice that this problem is different from maximum 2-sat, in this problem each clause can even contain one literal and we reduce 3-sat to show it is np-hard.

# Answer
> 1 votes
You can reduce from independent set. Given a graph, have a variable for each vertex, and for each edge, add the four clauses $$ x \lor y, x \lor \lnot y, \lnot x \lor y, \lnot x \lor \lnot y, $$ where $x,y$ are the variables corresponding to the vertices connected by the edge. I'll let you complete the proof.

# Answer
> 0 votes
I think the easiest approach is to model this problem as a sat problem.

Let K(x) mean that x is kept. Let C(K) be the number of literal for which K is true. Then any clause (a V b) from your original formula can be modeled as (a V b V K(a) V K(b)). Apply a reduction from 4-sat to 3-sat. You now have a problem that is a max 3-sat problem where you need to maximize C(K).

# Answer
> -1 votes
the problem which should be used is Odd Cycle Transversal

---
Tags: complexity-theory, np-hard, satisfiability, 3-sat, 2-sat
---


# Question
Title: What is the difference between consensus and mutual exclusion in Distributed Systems?
If we can achieve consensus, does it imply we can achieve mutual exclusion? Is there a difference?

Example : Paxos solves the consensus problem, can it also be used to solve mutual exclusion?

# Answer
If you have a consensus mechanism, then you can achieve consensus on who owns a critical section, and thus solve mutual exclusion. This is exactly what happens in, say, single-master distributed database systems when they are doing leader election to decide which machine will accept writes (this has to be mutually exclusive).

However, different algorithms for mutual exclusion provide different guarantees of progress in the presence of failures; those that are fully fault-tolerant are essentially equivalent to consensus; those that aren't, are weaker.
> 4 votes

# Answer
The mutual exclusion problem makes sense only when processors are scheduled fairly; otherwise, a processor halting in the critical section blocks the whole system. But, in a model with fair scheduling, both mutual exclusion and consensus are solvable with registers only, so it is not a good model to compare them.

Consensus is a single-use task: everybody proposes and decides a value once. For a meaningful comparison, let us specify mutual exclusion as a single-use task too. In single-use mutual exclusion, a unique processor must enter the critical section once, and that's it. This is equivalent to the test-and-set problem, where a unique processor must declare itself winner whereas all others declare themselves losers.

Now we can compare test-and-set and consensus: test-and-set has consensus power 2, which means that, in the wait-free model, it is strictly weaker than consensus when there are at least 3 processors.
> 1 votes

---
Tags: distributed-systems, mutual-exclusion
---


# Question
Title: Algorithm for finding 2 missing items in a stream of integers
I saw this post and wondered why the approach described in the accepted answer works. The same problem and solution is described a bit nicer here.

So let's say we receive a stream of $n-2$ pairwise different numbers $a\_1 + a\_2 + \cdots + a\_{n-2}$, from the set $\left\\{1,\dots,n\right\\}$. What I learned from the above post is that for the problem of finding 2 missing numbers $x$ and $y$, given a stream as described above, can be solved by finding the solution to the following system of equations:

\begin{alignat\*}{4} x+y & {}={} & \dfrac{n(n+1)}{2} - (a\_1 + a\_2 + \cdots + a\_{n-2}) \\ x^2 + y^2 & {}={} & \dfrac{n(n+1)(2n+1)}{6} - (a\_1^2 + a\_2^2 + \cdots + a\_{n-2}^2) \end{alignat\*}

Now it is easy to convert this into a single pass algorithm which supposedly returns the two missing numbers for a given stream.

How would one prove this algorithm's correctness? I think showing that the system must have exactly two solutions would be enough to prove correctness but I'm not sure how to approach this?

How can I convince myself (and others) that the algorithm is correct?

# Answer
> 1 votes
Suppose that $x + y = A$ and $x^2 + y^2 = B$. Then $$ xy = \frac{(x+y)^2 - (x^2+y^2)}{2} = \frac{A^2-B}{2}. $$ Consider now the polynomial $$ (t-x)(t-y) = t^2 - (x+y)t + xy = t^2-At + \frac{A^2-B}{2}. $$ The polynomial on the right has the two roots $x,y$.

If $x + y = z + w$ and $x^2 + y^2 = z^2 + w^2$ then both $x,y$ and $z,w$ are the two roots of the same polynomial, and so $\\{x,y\\} = \\{z,w\\}$.

---
Tags: algorithms, correctness-proof, streaming-algorithm
---


# Question
Title: What is the relationship between two definitions of Turing-computability of a partial function?
When one wants to know that whether a partial function $f \colon \Sigma^{\*} \supsetneq \mathrm{dom}(f) \rightarrow \Sigma^{\*}$ is Turing-computable, there are two methods that I think they are both useful.

1. We can define a total function $\bar{f}$ such that $$ \bar{f}(x) = \left\\{ \begin{aligned} &f(x),&x \in \mathrm{dom}(f) \\ &\bot,&x \not\in \mathrm{dom}(f) \\ \end{aligned} \right.$$ Thus, $f$ is Turing-computable if $\bar{f}$ is Turing-computable by a TM using $\bar{\Sigma} = \Sigma \cup \\{ \bot \\}$. (Some answers use this definition. see \[\] and \[\])
2. Let $M$ be a TM, and We say $f$ is Turing-computable by $M$ if $$M(x) = \left\\{ \begin{aligned} &f(x),&& x \in \mathrm{dom}(f) \\ &\bot,&&x \not\in \mathrm{dom}(f) \\ \end{aligned} \right.$$ where $M(x) = \bot$ means that $M$ never halts on $x$. (This definition is introduced in my books.)

These two definitions are not equivalent, since $M$ can computes some functions whose domain is Turing-recognizable instead of Turing-decidable in sense of definition 2.

I want know that is the definition 2 more powerful? In another word, if $f$ is Turing-computable in sense of definition 1, can we prove that it is also Turing-computable in sense of definition 2?

# Answer
> 2 votes
Definition 1 is incorrect. It does not define the notion of partial computable function correctly. Definition 2 is correct.

**Proposition:** *A partial function $f$ is computable according to your definition 1 if, and only if, it is a partial computable function whose domain $\mathrm{dom}(f)$ is a computably decidable set.*

*Proof.* Suppose $f$ is computable according to definition 1. Then for every $n \in \mathbb{N}$, we have $n \in \mathrm{dom}(f)$ if, and only if, $\bar{f}(n) \neq \bot$. So we can decide whether $n \in \mathrm{dom}(f)$.

Conversely, suppose $f$ is a partial computable function whose domain $\mathrm{dom}(f)$ is decidable. Then $\bar{f}$ is computable because we can compute it like this: given input $n$, if $n \in \mathrm{dom}(f)$ then output $\bot$, otherwise output $f(n)$. $\Box$

# Answer
> 0 votes
I am not sure why you think that Definition 2 could be more powerful. If one of the two is more powerful, then it's Definition 1 and in this case, I actually think that Definition 1 is more powerful.

If you have a Turing Machine M which computes a total function, it also means that M halts on all inputs. In your Definition 1, M would then never use the bottom symbol (sorry, I can't figure out how to type it!) except when processing one of the undefined inputs. Then you could simply modify such a Turing Machine to always check before terminating whether the output would be the bottom symbol or not, and in the latter case, to just run forever. Then the new Turing Machine would be exactly as needed in Definition 2.

The other direction on the other hand, is impossible. Just take any semi-decidable problem which is not decidable, for example the epsilon halting problem (the problem to decide whether a given Turing Machine holds on the empty word). There you have a Turing Machine which exactly computes the partial function which maps each halting Turing Machine to 1 and any other Turing Machine to that bottom symbol. But there is no total computable function which maps each halting Turing Machine to 1 and any other to the bottom symbol or any other symbol distinct from 1.

---
Tags: turing-machines, computable-analysis
---


# Question
Title: Given a language L what can we say about the decidability of whether this language is regular or not?
Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?

# Answer
> 15 votes
As quicksort notes in his comment, languages are infinite objects and it is not possible to feed them to Turing Machines.

So we must be content to consider classes of languages for which there eists a finite description. We can for instance consider the context-free languages and give as input the grammar for the language.

Unfortunately, even for context-free grammars it is undecidable whether their language is regular.

Bar-Hillel, Perles, Shamir. On formal properties of simple phrase structure grammars. (1961) doi 10.1524/stuf.1961.14.14.143

# Answer
> 0 votes
Contrary to the claims by Hendrik Jan and quicksort, the question makes perfect sense as asked. A Turing machine uses infinite tapes, so can we can indeed process an arbitrary language as input, written out on the input tape.

However, any finite prefix of the language tells us nothing about whether or not the language is regular. Thus, the problem is not decidable, and moreover, not even semi-decidable either way.

The best thing we can do is going through all regular languages (which we can effectively generate) and compare them to the input. This yields an algorithm that will say **not regular** infinitely often if and only if the language is indeed not regular. This is just a way of saying that *being regular* is a $\Pi^0\_2$-complete property of languages.

---
Tags: formal-grammars
---


# Question
Title: nlp: phonetic edit distance between a word and the closest of a set of words
Let's say someone is using Dragon Dictation, Google Speech, or some other free form dictation software (it will recognize anything they say to the best of its ability). I have some reasonably large set of words and I'm certain the speaker is trying to say one of these words. However, the voice recognition system is not perfect, so sometimes the voice recognition engine will spit out a word that is phonetically similar to what the user intended, but that is not in the set.

In other words, I have a word X, and a set of words Y. I want the member of Y which sounds the most like X.

I know that phonemes are the most basic sound unit of sound, so I've attempted to use CMU's Pronouncing dictionary to break X into phonemes, and use something similar to an edit distance algorithm to alter these phonemes until they match one of the members of Y. However, there are some huge issues:

1. There are at least 40 phonemes in CMU's system, which makes for a huge branching factor when you consider adding or replacing at any given position. I can't thoroughly search beyond three changes or so, which isn't sufficient.
2. Phonemes are perhaps too 'low-level' in the sense that there are many combinations of phonemes which are not words at all.

Building on complaint #2, I was thinking it would be nice to have a weighted graph of at least the most common words to other reasonably similar words, and I could run a search algorithm on this graph to find words in Y more quickly, and with a less explosive branching factor. Precomputing such a graph is on the table, as it could just be loaded at runtime.

Are there any sort of methods for doing this which exist currently? Or should I be thinking in a different direction?

# Answer
Building on the comments, there's something called the Needleman–Wunsch algorithm, for which you can find the lowest 'cost' alignment of two sequences (phonemes). You can get a good 'confusion cost matrix' by taking a normal confusion matrix and taking the log-odds of each confusion pair.

As long as your set of words is less than 33k or so, you should be able to find the lowest cost match in about a second or so. Multiply that by N if you multithread across N cores...

Full disclosure: not my ideas here, I got them from *Phonemic Similarity Metrics to Compare Pronunciation Methods* (Hixon, Schneider and Epstein, in *Interspeech 2011*).
> 5 votes

---
Tags: algorithms, graphs, search-algorithms, natural-language-processing
---


# Question
Title: Expected number of comparisons in a merge step?
I know that merging two sorted arrays takes worst case n comparisons. However, there will often be cases where one array is depleted before the other, letting us just append the remainder of one array to the combined sorted array. I've also read that merging takes the same amount of comparisons (wrt to n) to any input of size n. How is this represented in the mergesort recurrence relation and time complexity?

# Answer
I will answer your first question about the expected number of comparisons from a statistics/probability standpoint because I think it's rather interesting and non-obvious. Let's assume the input is random, both arrays to be merged are the same length ($n/2$), and the merging algorithm is the generic step by step compare and insert method.

Let $C(i)$ be the number of ways to merge the two arrays of length $n/2$ in $n/2 + i$ comparisons.

Clearly $C(0) = 2$ because this means we are doing exactly $n/2$ comparisons then appending the rest of one list to the end of the other. If we have two lists $A = \\{a\_1, a\_2, \ldots\\}$ and $B = \\{b\_1, b\_2, \ldots\\}$, then these merges would look like: $$\[a\_1, a\_2, \ldots, a\_{n/2}, b\_1, b\_2, \ldots, b\_{n/2}\]$$ or $$\[b\_1, b\_2, \ldots, b\_{n/2}, a\_1, a\_2, \ldots, a\_{n/2}\]$$

We then have $C(1)$ is the number of ways we can nest $b\_1$ within $\[a\_1, a\_2, \ldots a\_{n/2}\]$ (and the mirror of this, nesting $a\_1$ into $b\_{1\ldots n/2}$). This can be expressed similarly to the number of integer solutions to equations. We can insert $b\_1$ into $a\_{1\ldots n/2}$ in the following locations represented by the symbol $\diamond$: $$\[\diamond a\_1 \diamond a\_2 \diamond \ldots \diamond a\_{n/2 - 1} \diamond a\_{n/2}\]$$ It is **important** to note that we can not place $b\_1$ immediately after $a\_{n/2}$ as that will create a redundant count to what we already counted in $C(0)$. So this reduces our number of locations from $n/2$ to $n/2-1$ which we can choose from.

Let $n/2 = k$ for simplicity. We can express $C(i)$ as a combinatorial expression: $$C(i) = 2\binom{(k-1) + (i + 1) - 1}{(i+1) - 1} = 2\binom{k + i - 1}{i} = \frac{2(k+i - 1)!}{i!(k-1)!}$$

So we now have the total number ($N$) of possible merges is the total number of ways of choosing $n/2$ elements from a set of $n$. This can be seen easily if you imagine a skeleton array of length $n$, we then must select $n/2$ spots in this array to put one of our arrays being merged (and symmetrically the other array would be placed in the holes). We then have: $$N = \binom{n}{n/2} = \binom{2k}{k}$$ This is again clear to see when we sum the $C(i)$s: $$\begin{align} \sum\_{i=0}^{k-1} C(i) & = \sum\_{i = 0}^{k-1} 2 \binom{k + i - 1}{i}\\\\[0.5em\] & = 2\binom{2k - 1}{k - 1}\\\\[0.5em\] & = \frac{2(2k - 1)!}{k!(k-1)!}\\\\[0.5em\] & = \frac{2k}{2k}\cdot \frac{2(2k - 1)!}{k!(k-1)!}\\\\[0.5em\] & = \frac{(2k)!}{k!k!}\\\\[0.5em\] & = \binom{2k}{k} = \binom{n}{n/2} = N \end{align}$$

We then can find the probability of $k + i$ comparisons as: $$\begin{align} P\[X = k + i\] & = \frac{C(i)}{N}\\\\[0.5em\] & = 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1} \end{align}$$ Then it's easy to get the expected value: $$\begin{align} E\[X\] & = \sum\_{i = 0}^{k-1} (k + i) \cdot 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1}\\\\[0.5em\] & = \frac{2k^2}{k + 1}\\\\[0.5em\] & = \frac{n^2}{n + 2} \approx n -2 \end{align}$$ From this it's clear to see that the expected number of comparisons is pretty close to $n - 2$. In fact we can pull up a table to see how they compare: $$\begin{array}{|r|r|r|} \hline n & \lfloor n^2/(n+2) \rceil & n - 2\\ \hline 2 & 1 & 0\\ \hline 4 & 3 & 2\\ \hline 8 & 6 & 6\\ \hline 16 & 14 & 14\\ \hline 32 & 30 & 30\\ \hline 64 & 62 & 62\\ \hline 128 & 126 & 126\\ \hline 256 & 254 & 254\\ \hline 512 & 510 & 510\\ \hline 1024 & 1022 & 1022\\ \hline \end{array}$$ Another visual, here is the probability mass function of $x$ comparisons for merging into an array of size $1024$ (e.g. merging two arrays of size $512$):
> 2 votes

# Answer
Assuming that merging part copies two recursively sorted subarrays $A$ and $B$ each of size $n/2$ into a new array $C$, the total number of steps needed to copy both arrays is $n/2 + n/2 = n$. Even if one of the arrays is depleted before the other we still need to copy the rest of the array into $C$. Recall that in the RAM model the operations such as a comparison of two numbers, increment/decrement, accessing a single element of an array take $\Theta(1)$ time. So, even if you do not make $n$ comparisons but solely copy $n$ values from one location into another, it takes $\Theta(n)$ time.

The running time of the merge sort can be represented recursively as $$T(n) = 2T(n/2) + \Theta(n)$$ meaning "two times recursive call plus merging two arrays" or simply $$T(n) = 2T(n/2) + n$$ whose explicit form is $T(n) = n\log{n}$.

Unlike the Quicksort, the Mergesort always splits the array into two equal parts. This results in asymptotically equal worst and average running time which is $O(n\log{n})$. This Wikipedia article provides finer analysis for the number of comparisons in the worst case.
> 0 votes

---
Tags: algorithms, sorting, mergesort
---


# Question
Title: Dynamic Programming formulation for hotel problem
There are `n hotels` given at a0, a1, ..., an such that 0 \< a0 \< a1 \< ... \< an. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Moreover, you are required to complete your journey in exactly `d days` (i.e have to make `d-1` stops in between). If you travel `x miles` during a day, the cost for that day is `x^2`. You want to plan your trip so as to minimize the total cost - that is, the sum, over all travel days, of the daily cost. Find the optimal sequence of hotels at which to stop.

I came up with this dp solution:

Let `dp(i)` be the minimum cost such that the last stop is hotel i. Base case: `dp(0)=0`.

To compute dp(i), I consider all possible places `0<=k<i`, that we might have stopped before. Thus, the recurrence relation becomes:

```
for i=1;i<=n;i++
  dp(i)=inf
  prev(i)=undefined
  for k=0;k<i;k++
    if (dp(i)>dp(k)+(ai-ak)^2)
      dp(i) = dp(k)+(ai-ak)^2)
      prev(i) = k

```

How do we make sure that this algorithm takes exactly d stops?

# Answer
> 1 votes
For this problem, you should be using a two dimensional table where `dp(i,j)` is the minimum cost such that hotel `i` is reached in exactly `j` days.

If `i<j` there is no possible solution.

If `i=j` there is the solution where every hotel is visited.

If `i>j`, compare

* `dp(i-1,j-1) + (a(i) - a(i-1))^2`
* `dp(i-2,j-1) + (a(i) - a(i-2))^2`
* ... as long as `i-n>=j-1`

And pick the minimum.

To find the optimal sequence, either store the previous hotel visited in the table or go back through the table starting at `dp(n,d)`.

# Answer
> 1 votes
Start with yinnosanders algorithm, then try to get faster than $O (n^3)$ in typical cases:

With your cost model, travelling a total distance of x miles in d days costs at least $x^2 / d$. If you could stop anywhere you like, you would travel $a\_n / d$ miles every day.

First find a reasonably good set of stops: On each day, when there are d' days left, you pick the hotel whose distance is closest to the remaining distance, divided by d'. This gives you an upper limit L for the cost of the optimal journey.

Now jinnosanders suggests that you calculate dp(i,j). But first we calculate a lower limit for the cost of any journey that involves stopping at hotel i on day j: The cost would be lowest if you drove the same distance on each of the first j days, and the same distance on the remaining last days. The cost is at least $a\_i^2 \space/\space j\space+\space(a\_n - a\_i)^2/(d-j)$. If this cost is higher than the upper limit L for the best solution that we found earlier, then there is no need to calculate dp (i, j) and we set dp (i, j) = infinity instead.

We will have dp (j-1, j-1) ≥ dp (j, j-1) ≥ dp (j+1, j-1) ... so when we calculate dp (i, j), we stop when dp (i-n, j-1) = infinity. This should work considerably faster than O (n^3) in typical cases if the hotels are reasonably close to equidistant.

---
Tags: algorithms, dynamic-programming
---


# Question
Title: What are some undecidable problems for recursive languages?
When we say a class of languages is decidable we mean that the membership problem can be solved. However even though the membership problem is solvable for the class, there may exists some problems for the same class which are undecidable. For example Context free languages are decidable yet the problem of determining whether the language generated by context free grammar is unambiguous is undecidable.

I want to know some undecidable problems for recursive languages. Please don't problems related to context free and context sensitive language and then say that these languages are also recursive. The problems I want must be for only recursive languages and not for any proper subset of this class.

# Answer
For recursive languages, membership is decidable by definition, so most undecidable questions with regards to them will involve quantifiers. It's decidable to check if there's a given input is accepted, but it's undecidable to check whether a recursive language accepts any string, for example.

That said, questions like this are almost never phrased in terms of recursive languages, because there's representation of languages that captures exactly the recursive languages. Generally we represent languages as Turing Machines, but these characterize the recursively enumerable languages.

When it comes to RE, there's something called Rice's theorem,which says that *any* non trivial property of RE languages is undecidable. This holds for anything that's a property of the language itself, not just the specific representation.
> 2 votes

---
Tags: computability, undecidability
---


# Question
Title: How to convert this recursive algorithm to an iterative form?
Let us assume there's a folder structure as shown below: The letters a-d represent folders and the number 1-5 represent video files where for the file `n`, `size(n)=n`. So, 1 = 1MB, file 2 = 2MB, etc.

```
a
├── 1
├── b
│   ├── 2
│   └── 3
└── c
    ├── 4
    └── d
        └── 5

3 directories, 5 files

```

I want to write a script that takes as input a directory (e.g., `a`), and tells us the total video duration in that folder (iT=immediateTime) and the total video duration in that folder and all its sub-folders (tT=totalTime).

My pseudocode is:

```
function calcTime(dir)
{
    tT = iT = singleLevelCalcTime(dir);
    foreach(subdirectory in dir) {
        t+= calcTime(subdirectory);
    }
    echo iT;
    echo tT;
    return t;
}

```

Now, according to the Crunch-Turing thesis, essentially, every recursive function is mathematically proven to have an equivalent iterative version. My problem is I can't find any way to do this using just loops. I've read that explicit stacks (instead of the implicit ones generated by the nature of recursion) can solve this, but I can't figure out how.

For example, the first part of the algo is simple - `iT` can be calculated by the same method as in the original algorithm. Now, the program must enter each sub-directory and perform the same task again. However, without using recursion, I'd have to provide multiple levels of nested loops (unknown number of levels) to loop through each file/folder in each level. Please tell me where my approach is lacking. I can't really comprehend how to build an explicit stack that can solve this!

# Answer
You have to perform a visit of the directory graph, such as a DFS. Since the graph you're dealing with is a tree, you can use a tree traversal instead, which is conceptually identical but should be easier to implement.

Just a pedantic note: you don't need the Church thesis to say that every recursive function is Turing-computable, it can be proven formally.
> 1 votes

---
Tags: recursion, iteration
---


title: is this time complexity subexponential?

text:
# Question
Title: is this time complexity subexponential?
Is next time complexity sub-exponential?

$O(2^{N^{LOG2(1.5)}}/8)$

unformatted: O((2^N)^LOG2(1.5))/8) just in case I didn't format it properly.

# Answer
> 0 votes
It depends on how you define subexponential. The definition I generally use is:

$$\textsf{SUBEXP} = \bigcap\_{\varepsilon \> 0}\textsf{DTIME}(2^{n^\varepsilon})$$

However some authors define:

$$\textsf{SUBEXP} = \textsf{DTIME}(2^{o(n)})$$

Since your function is $2^{n^c}$ for some constant $c\<1$, it would be subexponential according to the second but not to the first.

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


# Question
Title: Proving union of 2 regular languages is regular
I have an exam tomorrow and the professor said that from the following two facts we should be able to show that the union of 2 regular languages is regular:

1. Given 2 regular languages, their intersection is regular
2. A compliment of a regular language is regular

I'm pretty confused on how I would get started with showing this. Can anybody please help me understand on how I would use those 2 facts to prove such a thing?

# Answer
> 3 votes
Use De Morgan rule $A\cup B = \overline{\overline{A} \cap \overline{B}}$.

Also you could prove it using DFA for $L\_1$ and $L\_2$ without using complement and intersection. The latter is systematic and can be easily implemented in one of your favorite programming languages. In other words, if you have DFA for $L\_1$ and $L\_2$ then you can construct the third DFA accepting $L\_1 \cup L\_2$.

# Answer
> 2 votes
You use the fact that each regular language has a corresponding regex, NFA and (total) DFA.

For the union you can do `regex_1|regex_2` where | is the choice operator. Or take the NFA of each and create a new NFA where the start has a $\epsilon$ transition to the start of each of the original NFAs

For the complement you take the total DFA (where every state has a transition for every character in $\Sigma$) and then set the new final states as $Q \setminus F$

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


# Question
Title: Complexity analysis of recurrence with multiple variables
To give background, there's two ways to multiply two complex numbers:

* Method A: requires 3 multiplications and 5 additions
* Method B: requires 4 multiplications and 2 additions

And it's given that multiplying two $m$ bit numbers is $O(m^2)$ and that adding two $m$ bit numbers is $O(m)$.

---

Now given a list of complex numbers, we can multiply them together using a divide and conquer algorithm that looks like this:

```
function divideAndConquer(list, i, j) {
  if (i === j) {
    return list[i]
  }
  const m = i + (j - i) / 2
  return methodA(divideAndConquer(list, i, m), divideAndConquer(list, m + 1, j))
}

```

My goal is to find the complexity of the divide and conquer algorithm using methods A and B respectively. Using method A as an example, we could say that

* List of size 1: $T(1) = 1$
* List of size 2: $T(2) = 3am^2 + 5bm$ where $a \> 0, b \> 0$

because with one number you don't do anything, and with two numbers you do 3 multiplications and 5 additions.

However, now my issue is that I'm not quite sure that for $T(n)$ what I have is right because while it's quite obvious that it'll be something like

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

I'm not really sure how to find out what $f(n)$ is because at each level $n$, $m$ will grow as a result of multiplication, meaning that $f(n) = 3am^2 + 5bm$ isn't accurate.

---

Essentially, the thing that confuses me is that there are two variables in play. The size of the list, $n$, and the size of the numbers in bits, $m$, that you're multiplying. So the heart of my question is really how do I solve a recurrence that has multiple variables? In this case $n$, and $m$.

# Answer
Since you know only $O$-bounds for the basic operations, you *can not* derive more precise bounds for $f$, nor $T$. Furthermore, if you *had* exact cost functions for the basic operations, solving divide-and-conquer recurrences exactly is very hard.

So, what the exercise authors probably want you to do is to say,

* $f \in \Theta(m^2)$ (assuming that the bound for multiplication is tight, which they probably wanted to imply but didn't express properly) in either case, and
* solve the schematic recurrence using the Master theorem (e.g. by substituting $f(m)$ with $m^2$).

You'll get out the correct $\Theta$ bound that way.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation
---


title: Monadic Second Order Logic for Dummies

text:
# Question
Title: Monadic Second Order Logic for Dummies
I am programmer with a grip on automata, but not on logic.

I read in papers that the two are very tightly related. Deterministic Finite Automata (DFA), Tree Automata and Visibly Pushdown Automata are all related to Monadic Second Order Logic (MSO). Although, I understand the automata and people (in papers) have tried to explain the relation to MSO to me, they always assume a strong background in logic and an understanding of MSO.

When I look at books and courses on logic, they mostly only handle first order logic, which seems pretty simple and consisting of only a few concepts: variables, or, and, not, implies, for all, exists, etc.

Can someone explain or point me to a resource that can explain:

1. What is second order logic in contrast to first order logic?
2. What is monadic vs non monadic logic?
3. Why is it important for a second order logic to be monadic to be decidable OR why is this the wrong question?
4. Why is monadic second order logic decidable?
5. The relation to at least DFAs?

If it is a resource it would be nice if it assumes that I am a programmer and not a logician. This means that I would like to understand how I would implement it as code, because until then math feels like magic to me ;)

Thank you for any help you can give me. I would really appreciate it.

# Answer
> 12 votes
> 1. What is second order logic in contrast to first order logic?
> 2. What is monadic vs non monadic logic?

Monadic second-order logic is first-order logic plus quantification over sets. So, as well as being able to say that there exists a domain element with some property ($\exists x\dots$), you can also say that there exists a *set* of domain elements with some property. So, for example, we can define 3-colourability of graphs by saying

\begin{align\*} \exists R\\,\exists G\\,\exists B\\, \big\[&\forall x\\,\big(x\in R\lor x\in G\lor x\in B\big)\\ &\land \neg\exists x\\,\big((x\in R\land x\in G) \lor (x\in G\land x\in B) \lor (x\in B\land x\in R)\big)\\ &\land \forall x\\,\forall y\\,\big(E(x,y)\rightarrow \neg \big((x\in R\land y\in R)\lor (x\in G\land y\in G)\\ &\qquad\qquad\qquad\qquad\qquad\quad\lor (x\in B\land y\in B)\big)\big)\big\]\\,. \end{align\*}

In words, there are colours red, green and blue such that

* every vertex has a colour
* and no vertex has two colours
* and, if there's an edge between two vertices, those two vertices don't have the same colour.

General second-order logic allows not just quantification over sets but also over arbitrary relations over the domain. Recall that a relation is a set of $k$-tuples over the domain, for some $k$. Sets are just unary relations: $k=1$ and a $1$-tuple is just an element of the domain.

> 3. Why is it important for a second order logic to be monadic to be decidable OR why is this the wrong question?
> 4. Why is monadic second order logic decidable?

Honestly, I don't remember the decidability issues. A key point is that full second-order logic lets you quantify into existence a linear order of the domain

\begin{align\*} \exists R\\,\forall x\\,\forall y\\,\forall z\\,\big\[&(R(x,y)\lor R(y,x)\big)\\ &\big((R(x,y)\land R(y,x))\rightarrow x=y\big)\\ &\big((R(x,y)\land R(y,z))\rightarrow R(x,z)\big)\big\]\\,. \end{align\*}

That is, there exists a binary relation that is total, antisymmetric and transitive, i.e., is a linear order on the domain $D$. That implicitly gives you a linear order on $D^n$ for any $n$, and you can use relations on $D^n$ for large enough $n$ to simulate a Turing machine tape. But, with monadic SO, you can't do any of these things.

(I guess that, if your domain is infinite, you probably need to specify in addition that the linear order is discrete and has a minimal element; then you know that it has an initial segment that's isomorphic to the natural numbers, and that should be enough.)

On finite inputs, the existential fragment of SO – formulas of the form $\exists R\_1\dots \exists R\_k\\,\varphi$, where the $R\_i$ are relation symbols and $\varphi$ is first-order – defines exactly **NP**. Full second-order logic defines exactly the polynomial hierarchy. This is exactly because of the ability to encode Turing machines and the fact that quantifying a fixed collection of relations gives you a polynomial amount of stuff to play with.

> 5. The relation to at least DFAs?

We can represent strings over some finite alphabet $\Sigma$ by relational structures. The vocabulary has a binary relation symbol $\leq$ that will be interpreted as a linear order, and a unany relation symbol $R\_a$ for each character $a\in\Sigma$. Each element of the domain is a character in the string, the linear order tells you what order the characters appear in and the relations $R\_a$ tell you what character appears in each position.

Now, suppose we have a DFA with $k$ states and let's assume we're dealing with finite strings, for now. We can write a formula that's broadly similar to the three-colourability formula above that says that our DFA accepts the string coded by its input. It says that there are sets (of domain elements, i.e., positions in the string) $Q\_1, \dots, Q\_k$, such that $Q\_i$ will be the set of positions in the string at which the automaton is in state $i$. So assert that:

* each position $j$ is in exactly one of $Q\_1, \dots, Q\_k$;
* the first position is in $Q\_1$ (assuming this is the start state);
* if the $j$th position is in $Q\_i$ then the $(j+1)$th position is in whatever state the automaton's transition function says it should be;
* the final position is in an accepting state.

If this formula is true, the automaton must accept the string; if it's false, the automaton must reject. For NFAs, we just say that each position is in at least one state and the final state is in at least one accepting state. For infinite inputs, we can code, e.g., the Büchi condition by saying "for all positions $j$ in the input, if $j$ is in an accepting state, there's some $j'\>j$ such that $j'$ is also in an accepting state.

Right now, I don't recall the proof of the converse (that everything definable in MSO can be recognized by an appropriate automaton). If I have time, I'll look that up and post a sketch.

**Conversely**, we can represent the meaning of MSO formulas by finite state automata inductively, following the construction of the automata. To do this we augment the alphabet of the automaton, by adding components that indicate the value of the free position variables $i$ and set variables $X$. If we read a string along the automaton we find exactly a single $1$ to indicate a certain postion $i$, and the positions in a set $X$ are marked likewise.

The basic formulas are $R\_a(i)$ for "position $i$ has symbol $a$", $i\in X$ for "$i$ is an element of $X$" and $i\<j$ for "position $i$ is before position $j$". These formulas can be represented by the following simple finite state automata (over the augmented alphabet suited for the formula):

More complicated formulas are constructed using the Boolean connectives $\lor, \lnot$ and the existential quantifiers $\exists i, \exists X$. The intended meaning of these operators are easily translated to languages as the language operators union $\cup$, complement ${}^c$ and *projection*, which is the operation that removes the corresponding component from the augmented alphabet. For union we have to pay some attention to the augmented alphabets in case the two parts of the formula do not agree on the set of free variables. Projection is simple, but it will change a deterministic automaton into a nondeterministic one.

---
Tags: automata, finite-automata, logic, coq, automated-theorem-proving
---


# Question
Title: prove(disprove) asymptotic exact bound (theta)
I want to prove (or disprove) that

$$\sum\_{i=1}^n\log\_2 i = \Theta(n\log\_2 n)\\,,$$

but I totally get stuck with this example. May someone help me with that.

# Answer
Asymptotically,

$$\frac{1}{4}n\log\_2n \< \frac{1}{2}n(\log\_2n-1) = \sum\_{i=\frac{n}{2}}^{n}\log\_2\frac{n}{2}\<\sum\_{i=1}^{n} \log\_2i \< \sum\_{i=1}^{n} \log\_2 n = n \log\_2 n\\,.$$
> 2 votes

# Answer
The LHS is $\log(n!)$, which is known, by Stirling's formula, to be asymptotic to $$\frac12\log(2\pi n)+n(\log(n) - 1).$$

You can conclude.
> 1 votes

---
Tags: asymptotics
---


title: Knapsack with an even number of items.

text:
# Question
Title: Knapsack with an even number of items.
I was asked in an interview to create a knapsack of only even items in n\*C time, c being the capacity, n being the number of items to choose from. I tried approaching it with a third dimension, where it would be of height n and signify at each ij whether the knapsack with these maxes contains even numbers or not, but I think its incorrect and I can't code it.

Any suggestions?

# Answer
> 3 votes
You can keep two tables with $n$ rows and $C$ columns:

$DP\_{even}$ that saves the best knapsack solution with an even number of itens. $DP\_{odd}$ that saves the best knapsack solution with an odd number of itens.

To fill $DP\_{even}$ you look at the previous best solution of $DP\_{odd}$ plus a new item, or of $DP\_{even}$ if you don't take the item: $$DP\_{even}\[i, j\] = max(DP\_{odd}\[i - 1,j - c\[i\]\] + v\[i\], DP\_{even}\[i - 1, j\]) $$ The same idea goes for $DP\_{odd}$ $$DP\_{odd}\[i, j\] = \max(DP\_{even}\[i - 1,j - c\[i\]\] + v\[i\], DP\_{odd}\[i - 1, j\]) $$

Your solution will be in $DP\_{even}\[n, C\]$

---
Tags: dynamic-programming
---


# Question
Title: In a Binary Search Tree what is the base of the log in this Big O notation
when discussing average time complexity as in this table.

**O (log n)**

I'm assuming it is 2 but wanted to verify. Also is it always 2 for these data structures?

I'm in the opinion that the base of the log is not considered a constant so it should be included in the Big O notation.

Whether or not is should be included. What is the actual value?

# Answer
> 1 votes
It doesn't matter what the base of the logarithm is. $\log\_a x = (\log\_bx)/\log\_b a$ so changing from one (constant) base to another just introduces a constant factor. Big-$O$ and related concepts don't care about constant factors.

The base of the log is absolutely a constant: the base used for the calculations might depend on the whim (or, more likely, convenience) of the person who did the analysis but it certainly doesn't depend on the input.

---
Tags: complexity-theory, data-structures
---


# Question
Title: Are the regular languages closed against injecting single letters?
Let $L$ an arbitrary regular language and

$\qquad L\_2 = \\{uav : uv \in L\\}$.

Am I correct to say that this language is not regular by saying:

$L$ has an even number of $a$'s. So $u$ and $v$ have an even number of $a$'s. However, $uav$ will have an odd number of $a$'s so $L\_2$ is not regular?

# Answer
> 4 votes
This language is regular. Let $M$ be a DFA accepting $L$ and assume it has a single initial and final state. We can construct a NFA accepting $L\_2$. We create two copies of $M$: $M\_1$ and $M\_2$. Let us denote the states of $M\_1$ as $q\_1, \dots, q\_n$ and the states of $M\_2$ as $p\_1, \dots, p\_n$. Note that these two DFA are isomorphic where $q\_i$ corresponds to $p\_i$. The initial state of the new automaton will be $q\_1$, and its accepting state will be the accepting state of $M\_2$ (so the accept state of $M\_1$ is no longer an accept state, and the initial state of $M\_2$ is no longer an initial state; in the new NFA, these are just normal states). Add new transitions $\delta(q\_i, a) = p\_i$ for each pair $(q\_i,p\_i)$. The resulting NFA accepts $L\_2$. You can think over it to prove it accepts $L\_2$; effectively, $M\_1$ is reading the $u$ part of the input and $M\_2$ is reading the $v$ part.

# Answer
> 4 votes
General approach if one wants to show that an operation on languages preserves regularity is to assume that the language $L$ is regular, and given as automaton/ expression/ grammar. Based on this representation build a new automaton/ expression/ grammar, and explain the new construct actually represents $L\_2$.

For instance, we can do so using **regular expressions**. See the answer *Showing Regular Languages are closed under removal of rightmost character for a related solution.

Let $\iota$ be the operator that inserts a single occurrence of the symbol $a$ into a language. We can transform a regular expression for $L$ into a regular expression for $L\_2$ by defining recursively

* $\iota(\varnothing) = \varnothing$
* $\iota(\varepsilon) = a$
* $\iota(\sigma) = a\sigma + \sigma a$
* $\iota(RS) = \iota(R)S + R\iota(S)$
* $\iota(R+S) = \iota(R) + \iota(S)$
* $\iota(R^\*) = R^\*\\;\iota(R) \\;R^\* + a$

Alternatively, here is a proof using **closure properties**. We know that the regular languages are closed under intersection (with regular languages) and under morphisms and inverse morphsims.

Let $c$ be a new symbol. Let $\varphi: \\{a,b,c\\}^\* \to \\{a,b\\}^\*$ be the morphism that deletes copies of $c$. Thus $\varphi^{-1}$ is the mapping that inserts copies of $c$ at arbitrary positions. Let $\psi: \\{a,b,c\\}^\* \to \\{a,b\\}^\*$ be the morphism that maps $a,c$ to $a$ and $b$ to $b$ (so it only changes the occurrences of $c$ into $a$. Finally let $K$ be the language over $\\{a,b,c\\}$ of all strings that contain exactly one occurrence of $c$.

Then $L\_2 = \psi(\varphi^{-1}(L)\cap M)$, and is regular whenever $L$ is regular. $\varphi^{-1}$ chooses the position of the extra $a$, $M$ verifies exactly one position was selected, and $\psi$ puts $a$ at the selected position.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: How logic programming (especially ASP) is related to the reasoning in (first-order) logic?
How logic programming (https://en.wikipedia.org/wiki/Logic\_programming, especially answer set programming) is related to the reasoning in the (first-order) logic? Maybe logic programming can be expressed using lambda calculus and then this connection between logic programming and logic and be exspressed as type of Curry-Howard isomorphism?

But maybe this connection can be established without this bypass?

Maybe such connection can not be established, as logical reasoning is monotonic (it just discovers consquences that are implicit in the initial premises), but logic programming is non-monotonic (it asserts new facts and knowledge). If so, then logic programming is generalization of logical reasoning and under what (syntactic) conditions logic program becomes set of logical formulas/logical theory?

# Answer
Logic programming is proof search for some logic. Traditionally, this is the Horn clause fragment of first-order logic. Languages like lambdaProlog extend this to (intuitionistic) hereditary Harrop formulas. There are also languages like Lolli, LolliMon, and Olli that work in fragments of linear logic (ordered linear logic in the last case). The concepts here are the notion of uniform proofs, focused proofs, and polarization, which lead to the concept of an abstract logic programming language.

The other way of thinking about logic programming that is more common via the Datalog path is as finite model theory. The idea there is simple: just calculate what the model would be, i.e. literally the sets of tuples for each relation. For Datalog (with or without *stratified* negation), this is relatively simple; there is a single minimal model.

When *non-stratified* negation is allowed, the situation gets quite a bit more complex. There is no longer a unique minimal model. There are two ways of dealing with this situation. One is to move to 3-valued models and for things like $q\leftarrow\neg q$ we can assign the truth-value $U$ to $q$ representing an "undefined" third truth-value. This leads to well-founded semantics. Given this 3-valued model, we can create a *set* of 2-valued models by considering all ways of assigning $T$ or $F$ to the "undefined" tuples excluding models with unfounded propositions which gives stable model semantics. The recent paper Founded Semantics and Constraint Semantics of Logic Rules gives a nice way of generalizing, organizing, and understanding these various semantics and the details of what "unfounded" means. Answer set programming is often conceptualized as stable model semantics. The XSB implementation of tabled logic programming is capable of handling non-stratified negation and producing a well-founded semantics which can then be fed into an answer set programming system leading to a significant performance gain over directly applying answer set programming.

Returning to proof search, what's happening in answer set programming can be partially thought of with respect to disjunctive logic programming. Typical logic programming languages do not allow disjunction in the head. That is, you can't prove $p\lor q$ except by proving $p$ or $q$. The issue is clear. Given the (disjunctive) logic program $p\lor q.$, should $?{-}\\,p$ succeed or not? More pointedly, what should be produced by $?{-}\\,t(X)$ where $t(1)\leftarrow p\land\neg q. t(2)\leftarrow q\land\neg p.$ is appended to the earlier program? Finally, append $r\leftarrow t(1)\land t(2).$ and ask if $?{-}\\,r$ holds. These examples illustrate that while we can find a model where $t(1)$ holds and a model where $t(2)$ holds, there's no model where both $t(1)$ and $t(2)$ hold. This can be related to the previous paragraph by noting the classical equivalence $p\lor q \equiv p \leftarrow \neg q$. In particular, the program $p\leftarrow\neg q. q\leftarrow\neg p.$ leads to both $p$ and $q$ being "undefined" in well-founded semantics and has two stable models, though this omits the model where *both* $p$ and $q$ hold. (One way to see why this happens is that there are implicitly completion rules that make the program look like $(p\leftrightarrow\neg q)\land(q\leftrightarrow\neg p)$.) In terms of proof search, there's simply no proof of $p$ from $p\lor q$. Via the soundness and completeness theorems of (classical) first-order logic, having a proof of some formula is equivalent to having it hold in all models. Answer set programming just enumerates the (stable) models. To see if answer set programming has *proven* something, you need to check to see if it's true in all the models the answer set program produces. Normal logic programming implicitly constructs a proof, so it can only talk about what holds in all models.

Finally, pure logic programming meaning logic programming omitting extra-logical features like cut (`!`), `assert`, `retract`, and others, is, as I said at the beginning, purely a matter of proof search. It does not "assert new facts and knowledge". It is *the process* of "discover\[ing\] consquences that are implicit in the initial premises". Most logic programming languages are restricted to a fragment of logic where this process is particularly amenable to computation. Indeed, they are often restricted to satisfy a much more stringent notion of "monotonicity" as is especially evident in Datalog. Datalog is usually implemented via forward chaining, which means starting from what is known and producing all immediate consequences. This is iterated until a fixed point is found. Monotonicity in this context means that once something is derived, you can never learn something later that will change your mind. Non-stratified uses of negation lead to non-monotonicity. For example, for the program $p\leftarrow\neg q. q\leftarrow\neg p.$, initially neither $p$ nor $q$ is true thus we may feel justified in deriving either or both of $p$ and $q$. If we pick both, then we scuttle our justification for picking either. Whichever we pick, we end up with a statement that isn't true in all models. Of course, in general there can be an arbitrary long chain of logic before we realize we're in this situation at which point we'll have already derived a bunch of things we should not have.
> 6 votes

---
Tags: logic, lambda-calculus, first-order-logic, curry-howard, answer-set-programming
---


# Question
Title: Bayesian updating for multivariate Gaussian
I am reading http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf and come across this slide

What has been confusing me boils down to showing that multivariate Gaussian is conjugate to itself given a Gaussian likelihood. I did quite a bit of searching on both this site and on Google and found the Kevin Murphy's slides showing the univariate case. I tried to generalize to the finite-dimension case but failed in matching the coefficients.

Can somebody help me in deriving the posterior form given the prior and the likelihood? Thank you!

# Answer
> 0 votes
Prior:

$$p\_0(\theta\_a) \varpropto \text{exp}(-\frac{1}{2}\theta\_{a}^{T} (\lambda I\_d)^{-1} \theta\_a) = \text{exp}(-\frac{1}{2} \frac{1}{\lambda}\theta\_{a}^{T} \theta\_a)$$

MLE: \begin{align\*} p(y\_{t,a} | \theta\_a) &= (2 \pi)^{\frac{n\_{t,a}}{2}} |\sum|^{\frac{1}{2}} \text{exp}(-\frac{1}{2} (y\_{t,a} - D\_{t,a} \theta\_{a})^{T} I\_{n\_{t,a}}^{-1} (y\_{t,a} - D\_{t,a} \theta\_a)) \\ & \varpropto \text{exp}(-\frac{1}{2}(y\_{t,a} - D\_{t,a} \theta\_{a})^{T} I\_{n\_{t,a}}^{-1} (y\_{t,a} - D\_{t,a} \theta\_a)) \end{align\*}

Hence, \begin{align\*} p\_{t,a}(\theta\_a) &\varpropto \text{exp}(-\frac{1}{2} \frac{1}{\lambda} \theta\_{a}^{T} \theta\_a) ~ \text{exp}(-\frac{1}{2}(y\_{t,a} - D\_{t,a} \theta\_{a})^{T} I\_{n\_{t,a}}^{-1} (y\_{t,a} - D\_{t,a} \theta\_a)) \\ &\varpropto \text{exp}(-\frac{1}{2} (\frac{1}{\lambda} \theta\_{a}^{T} \theta\_a + y\_{t,a}^{T} y\_{t,a} - y\_{t,a}^{T} D\_{t,a} \theta\_a - \theta\_{a}^{T} D\_{t,a}^{T} y\_{t,a} + \theta\_{a}^{T} D\_{t,a}^{T} D\_{t,a} \theta\_a)) \end{align\*}

By definition, we also have \begin{align\*} p\_{t,a}(\theta\_a) &\varpropto \text{exp}(-\frac{1}{2}(\theta\_a - \hat{\theta\_{a}})^{T} A\_{t,a} (\theta\_a - \hat{\theta\_a})) \\ &\varpropto \text{exp}(-\frac{1}{2}(\theta\_a^T A\_{t,a} \theta\_a - \theta\_a^T A\_{t,a} \hat{\theta\_a} - \hat{\theta\_a}^T A\_{t,a} \theta\_a + \hat{\theta}^T A\_{t,a} \hat{\theta})) \end{align\*}

And so we have \begin{align\*} \text{exp}(-\frac{1}{2} (\frac{1}{\lambda} \theta\_{a}^{T} \theta\_a + y\_{t,a}^{T} y\_{t,a} - y\_{t,a}^{T} D\_{t,a} \theta\_a - \theta\_{a}^{T} D\_{t,a}^{T} y\_{t,a} + \theta\_{a}^{T} D\_{t,a}^{T} D\_{t,a} \theta\_a)) &= \text{exp}(-\frac{1}{2}(\theta\_a^T A\_{t,a} \theta\_a - \theta\_a^T A\_{t,a} \hat{\theta\_a} - \hat{\theta\_a}^T A\_{t,a} \theta\_a + \hat{\theta}^T A\_{t,a} \hat{\theta})) \\ \frac{1}{\lambda} \theta\_{a}^{T} \theta\_a + y\_{t,a}^{T} y\_{t,a} - y\_{t,a}^{T} D\_{t,a} \theta\_a - \theta\_{a}^{T} D\_{t,a}^{T} y\_{t,a} + \theta\_{a}^{T} D\_{t,a}^{T} D\_{t,a} \theta\_a &= \theta\_a^T A\_{t,a} \theta\_a - \theta\_a^T A\_{t,a} \hat{\theta\_a} - \hat{\theta\_a}^T A\_{t,a} \theta\_a + \hat{\theta}^T A\_{t,a} \hat{\theta} \end{align\*}

Equating the "second coefficient" of $\theta\_a$ $$\theta\_a^{T} (\frac{1}{\lambda} I\_d)\theta\_a + \theta\_a^T D\_{t,a}^T D\_{t,a} \theta\_a = \theta\_a^T A\_{t,a} \theta\_a$$ Hence $A\_{t,a} = D\_{t,a}^T D\_{t,a} + \frac{1}{\lambda} I\_d$,

Similarly, equating the "first coefficient" of $\theta\_a$, we have $$\hat{\theta\_a}^T = A\_{t,a}^{-1} b\_{t,a}$$

---
Tags: machine-learning, artificial-intelligence, reinforcement-learning, bayesian-statistics
---


# Question
Title: Why is the complexity of the following code $O(n^4)$?
```
for i = 1 to n
    s = 0

    for j = 1 to i - 1
        s = s + j * (i - j + 1)

    r = s * s

```

I calculated the time complexity of this code to be of order $O(n^2)$, but my professor says it is actually $O(n^4)$ because of the statement $r = s * s$, as $s$ is dependent upon $j$ and $i$ which in turn are dependent on $n$. But don't we consider arithmetic operations to be $O(1)$?

Complexity calculation is a new concept to me, and it confuses me a lot. I would appreciate if someone posts a detailed answer which clears my confusion.

# Answer
There are two things that could be measured here. First, the time complexity of the code, which is to say the number of steps it takes to execute. In that case we have two possible metrics: (1) count each arithmetic operation as taking 1 unit of time. That's the one you're likely used to. In (2) we count the time an arithmetic operation takes as a function of the number of bits needed to express the operands.

The second possibility is to measure the magnitude of the result, $r$, as a function of $n$. It appears that your professor is looking for the second measure: express $r$ in terms of $n$. That, though, is a bit problematic, since $s$ is reset to zero at each iteration of the outer loop, so the final value of $r$ is just the result when $i=n$ which will be $O(n^6)$.

The upshot is that your calculation of the running time, $O(n^2)$ is the only one that makes any sense here. Ask your professor for clarification.
> 3 votes

---
Tags: time-complexity, asymptotics
---


title: Buses in a processor

text:
# Question
Title: Buses in a processor
I understand what address buses and data buses and control buses do, but...

Why does data not go to the keyboard controller, or come from the VDU output controller?

# Answer
> 2 votes
There are two main methods of doing IO (both obviously have variants, and both are often combined, some control information using the first method and the majority of the data using the second).

* One is communicating directly from the processor with the IO-device. In that case there is a data bus between the processor and the device.
* The other is going through memory. The processor write (or read) in memory at *well known* addresses and the device either monitor the memory accesses or use the first method to know that it has to process the data.

In my experience, keyboard controllers are often using the first method and display controllers are often using the first method for control information (which display mode for instance, or the *well known* address where to find the information to display) and the second method for the information to display (represented either as character code or as a bitmap)

---
Tags: computer-architecture, cpu
---


# Question
Title: Pumping lemma for context-free languages - Am I doing it right?
I have an exam coming up in three days, and there's a thing that I really need to be able to completely understand - that is, of-course, pumping lemmas for CFL. I know how to do prove that a regular language is not regular using PL, but for CFL it's a bit more variables, and I am not entirely sure how to split a string. Below, I will provide with an exercise and my attempt. I want to know, am I doing this correctly and if not, what do I need to do to make it correct? The exercise (although quite similar to the previous question I asked, that question was for regular language and not CFL - in short they are two different questions)

Show, using pumping lemma, that $L2 = ${ $ 0^m 1^k 2^n | n = km $} is not context-free

My attempt goes as following: If L2 is context-free, then there exist a constant $P$ such that $ S \in L2 $ and $|s|\ge P $ which implies that there exist strings uvxyz such that the following are satisfied:

$(1) uv^ixy^iz \in L2 $ for every $ i \ge 0 $

$(2) |vy| \> 0 $

$(3) |vxy| \le P$

We must first assume that $L2$ is context-free
$L2$ must have a Pumping length $P$
Must also take strings $0^P 1^P 2^{p^{2}} $ (since n = km)

There are 3 cases

case 1) VXY does not straddle a boundary, belongs to just one So we have $0^P 1^P 2^{P^{2}}$, let's split that into $UVXYZ$,

$U = 0^P$, $ V = 1^r $, $ X = 1^t $, $ Y = 1^{P-r-t}$, $Z= 2^{P^{2}} $
and then we select $i = 2$, which gives us
$uv^2xy^2z = 0^p 1^{2r} 1^t 1^{2p-2r-2t} 2^{p^{2}} = 0^p 1^{2p-t} 2^{p{^2}} \notin L2$

case 2) VXY straddles the first boundary;
like above, we split into $uvxyz$ where
$u = 0^r $
$v = 0^{p-r} 1^t $
$x = 1^r $
$y = 1^{p-t-r} $
$z = 2^{p{2}} $

if we, yet again, select $i = 2$

$uv^2xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{r} 1^{2p-2t-2r} 2^{p{2}} = 0^{2p-r} 1^{2p-r} 2^{p{2}} \notin L2 $

case 3) vxy straddles the second boundary;
again, like above we split the string into 5 parts $uvxyz$ where
$ u = 0^p $
$ v = 1^t $
$ x = 1^r $
$ y = 1^{p-t-r} 2^t$
$ z = 2^{p{2} - t} $

if we select $i = 2$
we get $uv^2xy^2z = 0^p 1^{2t} 1^r 1^{2p - 2t - 2r} 2^{2t} 2^{p{2}-t} = 0^p 1^{2p-r} 2^{p{2}+t} \notin L2$

Thus we have contradictions for all three cases, which concludes that the language is not context-free!

My general question is am I selecting a string correctly? I.e. does it have to satisfy $|vxy| \le p$ in-order for the $uv^ixy^iz $ where $ i = 2 $ to work? OR must $vxy$ be chosen so that the length is $\le p$? Have I missed cases?

Thank you in advance!

# Answer
Bascially your approach is correct. I have not checked every detail, but have a few remarks:

* you miss the cases where v or y include a border like v=0011; here pumping destroys the general structure of the word besides the number relations.
* case 1 would have to be done for the 0s and the 2s, too
> 1 votes

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


# Question
Title: Does instruction which control unit fetch contain both what to do and where to do (in which unit of processor)?
What instruction really means? I am facing problem in understanding it. If the instruction is to copy this and create a new file and place there so it seems it d doesn't need processing so what will control unit do?

# Answer
In *computer architecture* (the current tag, but I wonder if it is really adapted), an instruction is whatever the computer architect decide to be. It is the most basic bit string having a independent meaning. Some instructions may be quite simple (add two registers and put the result in the first one), some may be strange (provide the most significant bits of a constant value used in the next instruction) and the boundary between being one instruction or several may be not that clear (you could consider the previous example and the instruction which follow it as a single instruction).

I don't know any processor which provides instructions like the one you are describing. Those seems to me to be at the abstraction level of an operating system, not of a processor architecture. It could be that mainframes provide such instruction (in the channel control part), but even there my guess is that it would need to be the combination of several more basic instructions. That guess holds also for operating system.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: When does a type generalise another type?
In languages like Haskell, with a Hindley-Milner type system, when does a type $t$ generalise a type $u$? I use the definition: $t$ generalises $u$ iff $\forall\ v: v \text{ unifies with } u \rightarrow v \text{ unifies with } t$.

I have an algorithm that given these types returns a unifier if one exist. The unifier is an ordered list of assignments $v\_1 \mapsto t\_1, v\_2 \mapsto t\_2, \dots, v\_n \mapsto t\_n$ such that applying $v\_i := t\_i$ to both types for ascending $i$ results in two identical types.

For instance, the types $(a,a)$ and $(p,q)$ unify with the unifier $a \mapsto p, p \mapsto q$: after applying these assignments both types are $(q,q)$.

It should be possible to use the unifier to see if a type generalises another type, but I can't figure it out at the moment. I couldn't find an existing algorithm either.

Note: if there is an easier way, without using the unifier, that would be appreciated as well.

# Answer
> 4 votes
A pretty easy way to see if $t$ generalizes $u$ if **$u$ matches $t$**:

replace all variables in $u$ by (fresh) constants, written $u\_c$, and check if $u\_c$ unifies with $t$.

If so, then there is a substitution $\sigma$ such that $t\sigma\equiv u$ which means by definition that $t$ is more general than $u$.

As mentioned in the comments, if $\mathrm{mgu}(t,u)$ succeeds and returns a substitution $\tau$, then $u$ matches $t$ iff $u\tau\equiv u$ up to variable renaming.

Note: Pattern matching is usually best implemented independently from unification, as it is simpler in general. In particular it isn't necessary to actually replace variables with constants in $u$. Beware of non-linearities in $t$ though: $\alpha\rightarrow \alpha$ does **not** match $\mathrm{int}\rightarrow\mathrm{bool}$!

# Answer
> 1 votes
The accepted answer is very good, but the below is easier to implement and, I believe, correct as well:

* Make groups of the assigned variables such that variables that will be rewritten to the same type are in the same group.
* For all groups, verify:

+ There is at most one variable from the right-hand type in the group.
    + If there is a variable from the left-hand type in the group, there may not be any non-variables in the group.

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


# Question
Title: What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)?
An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that $$\left( \bar{M}, M \right) \in R \Leftrightarrow \bar{M} = M^O$$

Given an OTM $\bar{M}$, how to find the TM $M$ such that $(\bar{M},M) \in R$?

Given a TM $M$, how to find the OTM $\bar{M}$ such that $(\bar{M},M) \in R$?

By using the definition of the OTM in wiki, In my opinion, $$\bar{\Gamma} = \Gamma,~\bar{q}\_{start} = q\_{start},~\bar{q}\_{accept} = q\_{accept}, \bar{q}\_{reject} = q\_{reject} $$ and $$Q\_{0} = Q \cup\\{ q\_{query} , q\_{response}\\}$$ I have no idea about the relation between $\bar{\delta}$ and $\delta$. And what about the non-deterministic OTMs and NDTMs?

# Answer
First of all the question is not very meaningful, indeed an OTM must "know" that it has such capability and use it in a proper manner. A nice way to compare $M$ and $M^O$ "syntactically" is to think that also $M$ is an oracle machine, but its oracle gives a constant (or identity) answer for every query.

Such a model makes the relation between $M$ and $\bar{M}$ trivial.

Indeed, without loss of generality, you can assume that an OTM has a special state $q\_{query}$ and a special tape called the *Query Tape*.

Whenever $M^O$ enters the state $q\_{query}$ the oracle reads the content of the Query Tape, erases it, and writes on it the answer (usually a $0$ or $1$)

But without loss of generality you can also assume that $M$ has an extra tape.

With this model the relation between $\bar{M}$ and $M$ is simply:

$$M = \bar{M}\\; !!!$$

( $\delta = \bar{\delta}, \Sigma = \bar{\Sigma}, Q = \bar{Q}, Q\_f = \bar{Q\_f}, q\_{s} = \bar{q\_{s}}, \Gamma = \bar{\Gamma}$ )

in other words also $M$ is equipped with $q\_{query}$ but when $M$ enters it nothing happens to the content of the extra tape.

As commented below, it should be clear (see also quicksort's answer) that an OTM could be much more powerful than a standard TM (e.g. it could solve the Halting problem), so in some (many:-) cases given an OTM $M^O$ you cannot build an equivalent TM. My answer is only an help to understand the way you can compare an OTM with a TM "syntactically" (I don't know a better term) which - I thought- was the aim of your question.
> 2 votes

# Answer
The definition of $R$ you gave above doesn't make much sense, it looks like you're trying to build an equivalent TM that doesn't use the oracle, but the point of an oracle machine is to provide the TM with capabilities it wouldn't normally have.

For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

If all the oracles you are using are oracles for decidable languages such as those used in complexity theory, then you can obviously simulate them (just construct a universal Turing Machine and use it to carry out the computation), but that's besides the point because it interferes with time/space complexity.

Nondeterministic oracle machines are exactly the same, the nondeterministic part is the transition function, queries to the oracle are treated as though they were a single computational step that magically happens, it is completely orthogonal to nondeterminism.
> 2 votes

---
Tags: turing-machines, nondeterminism, oracle-machines
---


# Question
Title: $m/p$-equivalence holds after union with an arbitrary finite language
**Problem 1:** Let $A,B$ be languages over some alphabet $\Sigma$, if $A \equiv\_m B$, then for every finite language $C$, $A \cup C \equiv\_m B \cup C$.

**Problem 2:** Problem 1 but using polynomial time reductions.

**Note:** $A \equiv\_m B$ means $A \leq\_m B$ and $B \leq\_m A$, same for $\equiv\_p$. Every finite language can be decided in polynomial time.

By hypothesis, we have reductions $f$ from $A$ to $B$ and $g$ from $B$ to $A$, the obvious choice for a reduction from $A \cup C$ to $B \cup C$ would be: $$h(w) := \begin{cases} w &\text{ if } w \in C\\ f(w) &\text{ if } w \notin C \end{cases},$$ with this definition it follows that if $w \in A \cup B \Rightarrow h(w) \in B \cup C$, however, if $w \notin A \cup C$ I can't say that $h(w) = f(w)\notin B \cup C$, at most, $f(w) \notin B$.

My idea was to redefine $h$ like this:$$h(w) := \begin{cases} w &\text{if } w \in C\\ f(w) &\text{if } w \notin C \land f(w) \notin C\\ X(w) &\text{if } w \notin C \land f(w) \in C \end{cases},$$ where $X(w)$ must lie in $B \cup C$ when $w \in A \backslash C$, and outside $B \cup C$ when $w \notin A \cup C$. The problem now is how to define the mapping $X$, I can't ask whether $w \in A$ or not because $A$ may not be decidable (or decidable in polynomial time for problem 2) and here I'm stuck.

Can't see how to define $X$ without making questions about being in $A$ or $B$, those questions should be avoided because a $TM$ computing $h$ might loop forever. I'm starting to think that the problem needs some hypothesis like $A,B$ being decidable/decidable in polynomial time languages (the problem seems sound to me though, I can't find counterexamples to it).

# Answer
Hint: You could prove that $A\cup C\equiv\_p A$. For both directions, try functions in the form $$h(w)=\left\\{\begin{array}{ll}w & w\notin C\\ \textrm{something hardwired} & w\in C.\end{array}\right.$$
> 2 votes

---
Tags: complexity-theory, formal-languages, turing-machines, reductions, polynomial-time
---


title: Find a subset in constant many queries

text:
# Question
Title: Find a subset in constant many queries
Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

* **Input**: A black box of monic polynomial $f(x) \in\mathbb{S}\[x\]$ of degree $d$.
* **Question :** $\mathbb{S} \subseteq \mathbb{Z}$, unbounded from both sides

Here $\mathbb{S} \subseteq \mathbb{Z} $ is an interval unbounded from both sides. For example interval $(-b,\infty\]$, where $b$ is any fixed value and this interval is bounded from left side. I am allowed to make only constant many queries to oracle. I want to find such an subset $\mathbb{S}$.

**Unbounded interval:** An interval is said to be left-bounded or right-bounded if there is some real number that is, respectively, smaller than or larger than all its elements. An interval is said to be bounded if it is both left- and right-bounded; and is said to be unbounded otherwise

Please give a reference to material also if possible. If anything is not clear please ask in the comments I will try clear it.

**Motivation :** Find a polynomial in two or three queries

# Answer
If you don't know any bounds on the coefficients beforehand, then you cannot give them any bound without $d$ queries. Suppose you have made queries of $f(x)$ on $x=x\_1,\ldots,x\_{d-1}$, and claim that the coefficients of $f(x)$ are all at least $-b$. However, a different monic polynomial $f(x)-N(x-x\_1)\cdots(x-x\_{d-1})$ has the same evaluation on all the $d-1$ queries, and when $N$ is large enough the coefficient of $x^{d-1}$ in this polynomial must be smaller than $-b$, leading to a contradiction.
> 4 votes

---
Tags: algorithms, complexity-theory, lower-bounds
---


# Question
Title: Limited sort: is this a well-known problem?
I came up with a problem, and I'm having trouble finding existing work on it. I'm not sure if there is a polynomial-time solution for it. Is this a well-known problem (or equivalent to one)?

We define a function `limited_sort(input, n) -> output` that takes an array of comparable elements `input` and an integer `n` and returns `output` which is a permutation of `input` such that that no element in `output` is more than `n` spaces from its original position in `input`. `output` is the permutation that has the lowest number of inversions (subsequent elements `a, b` such that `a > b`) out of all such permutations (if there are multiple minimal permutations, `output` is the lexicographically lowest of them).

For example, `limited_sort([4, 1, 0, 2, 3], 2)` returns `[0, 1, 4, 2, 3]`, which has 1 inversion (`4, 2`). 0 inversions is not possible because you'd have to fully sort the list, and the element "4" would move 4 spaces which is not allowed. `[4, 0, 1, 2, 3]` is also valid with 1 inversion but it's lexicographically higher than `[0, 1, 4, 2, 3]`.

Is there a solution that is polynomial-time in both `n` and `L` (the length of `input`)?

# Answer
I think absolutely minimising the number of inversions makes this very hard. If you just say "I want an array that is a bit better sorted, without moving any item by more than n positions": Fill a heap with the first n+1 array elements. Then remove the smallest element in the heap and put it into the first array position, unless there is an array element in the heap that would end up moving too far. Add the next array element to the heap and repeat. Obviously stop adding elements to the heap when you run out of elements.

This will find \[0, 1, 4, 2, 3\] in your example.
> 1 votes

---
Tags: complexity-theory, sorting
---


# Question
Title: Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent
Show that for any leaf v in a binary search tree, if u is the parent of v, then either key\[v\] is the largest key in the tree smaller than key\[u\], or key\[v\] is the smallest key in the tree larger than key\[u\].

I don't understand "key\[v\] is the largest key in the tree smaller than key\[u\]" and "key\[v\] is the smallest key in the tree larger than key\[u\]." Can someone help explain the problem to me?

# Answer
**In Order** traversal sorts key in an ascending order. If $u$ is the parent of leaf $v$ then $v$ is either left or right child of $u$. If $v$ is left child then $key\[v\]\leq key\[u\]$ which implies $key\[v\]$ is the largest key in the tree smaller than $key\[u\]$. Similar intuition follows if $v$ is right child.
> 1 votes

---
Tags: trees, binary-trees
---


# Question
Title: Labeling a limited number of points on the screen
I have a map with up to thousands of points on it.

Now I want to label those points on the screen. But this would only make sense for a limited number of points and the label of points close by should not overlap with others.

What would be a way to go about this to not cover the screen with labels?

# Answer
> 3 votes
Aggregate your data, the setting is in 2D, the number of points is small for clustering, and it will solve the task.

You can use k-means, where $k$ will denote number of labels shown on the screen. Putting labels in place of centroids will with high probability give you good place for labels. If this is not good enough you can refine the placement using iterative method on selected labels by treating them as springs with constraint on minimal distance or solving NLP (Natural Label Placement).

Alternatively you can use dbscan algorithm with $\epsilon$ greater than the size of maximal label, this will give you advantage with no refinement needed but in return you lose control over number of labels displayed.

For more in-depth analysis I recommend the doctoral dissertation Automated Label Placement in Theory and Practice by Alexander Wolff.

There are other approaches like *Unaligned Collision Avoidance* or simulation by flock where the avoiding/pushing is set greater than labels size. This unfortunately will need more tweaking.

---
Tags: algorithms, graphics
---


# Question
Title: Algorithm to find the mode in a unimodal array
I am given the following problem in an Algorithms class:

> Assume that you are given an array A\[1 . . . n\] of distinct numbers. You are told that the sequence of numbers in the array is unimodal, in other words, there is an index i such that the sequence A\[1 . . . i\] is increasing (A\[j\] \< A\[j + 1\] for 1 ≤ j \< i), and the sequence A\[i . . . n\] is decreasing. The index i is called the mode of A. Give an O(log n) algorithm that find the mode of A

I have written this draft solution as my solution but I want to make sure that this is an acceptable CORRECT solution.

My Algorithm:

```
FIND_MODE(A)
n = A.length
if n == 1
    return 1

mid = floor(n/2)
if A[mid] < A[mid+ 1]
    return FIND_MODE(A[1 … mid])
else
    return mid + FIND_MODE(A[mid+1 … n])

```

Is it this acceptable and correct pseudocode algorithm?

Is it correct that this is a Big-O(log n) algorithm?

# Answer
Almost correct. Just a small correction. It should be

```
if A[mid] > a[mid+1]

```

If two consecutive elements are increasing then they are in the increasing portion of the array, so the mode is to the right. Hence the correction.
> 4 votes

# Answer
There's a neat, provably "optimal" (in some sense) algorithm for this problem in Structure and interpretation of computer programs (free online version) by Abelson and Sussman. It involves partitioning the line in two pieces in a ratio $\phi$. I am not sure where the original algorithm came from in the literature, but maybe someone else can cite it.
> 1 votes

# Answer
Prologue:

```
Let L be a list of integers.
Let L[p : q] be an nonempty slice, i.e., 0 ≤ p < q ≤ len(L).
We say that L[p : q] is unimodal iff there is a natural number m such that

(a) p≤m<q;
(b) L[p : m + 1] strictly increasing;
(c) L[m : q] is strictly decreasing.

Furthermore, such a number m, if it exists, is call the mode of L[p : q].

Since L is the same as L[0 : len(L)], we also say that L is unimodal if L[0 : len(L)] is unimodal.

```

Algorithm:

```
def Mode(A,p,q):

if p+1==q:
   return A[p]
else:
   m=⌊p+q⌋ 2

ifA[m−1]<A[m]:
   return Mode(A,m,q)
else:
   return Mode(A,p,m)

```

Proof of Correctness:

Let P(n) denote the assertion that if A is a list of integers, 0 ≤ p \< q ≤ len(A), A\[p : q\] is unimodal, and n = q − p, then M ax(A, p, q) terminates and returns the maximum element of A\[p : q\].

Note that we are using q − p (length of the slice being considered) as size of input.

We prove that for all integers n ∈ N, n ≥ 1, P (n) holds.

**Base Case**: Let n = 1. Then q − p = 1, or equivalently, p + 1 = q. Thus A\[p : q\] is a slice of one element, and A\[p\] is its maximum element.

By Line 2, A\[p\] is returned as wanted.

**Induction Step**: Let n ∈ N,n \> 1. Suppose for all j ∈ N, 1 ≤ j \< n,P(j) holds. \[IH\]

**WTP**: P(n) holds.

Since q − p = n \> 1, Lines 4-8 run. There are two cases to consider.

*Case 1: A\[m − 1\] \< A\[m\].*

Then by Line 6, Max(A,m,q) is called and returned.

By Line 4 and Hint 2, p \< m \< q, and so 1 ≤ q − m \< q − p.

By the IH, M ax(A, m, q) terminates and returns the maximum element of A\[m : q\].

Since A\[m − 1\] \< A\[m\], the mode of A\[p : q\] must equal the mode of A\[m : q\].

So the maximum element of A\[p : q\] equals the maximum element of A\[m : q\]. Therefore M ax(A, p, q) terminates and returns the maximum element of A\[p : q\], as wanted.

*Case 2: A\[m − 1\] \> A\[m\]:*

Similar to Case 1; left as an exercise.
> 0 votes

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


# Question
Title: Terminology - Ensemble or Bag of classifiers?
I am working on a classification problem. My algorithm involves splitting the data into several subsets based on a specific feature (e.g. number of XX) then training a classifier on each of these subsets. At test time, the incoming data will be passed to one of the trained classifiers depending this number of XX.

Would such a system be called an ensemble of classifiers or a bag of classifiers ?

# Answer
> 1 votes
No, this isn't bagging. It could perhaps be called an ensemble of classifiers (see https://en.wikipedia.org/wiki/Ensemble\_learning) but the most effective description will probably be to just describe what you are doing along the lines you listed in the question. A "name" is primarily useful as a short way to describe what you are doing. Some techniques are used so commonly that they have an accepted "name". What you are doing isn't standard and might not have any well-known "name", but that's OK -- you can describe what you are doing in a sentence or two, so just do that.

---
Tags: machine-learning
---


# Question
Title: Creating a numbered list, divided into types, without need for shifting or re-ordering - is this a re-occuring problem
My question is not for a solution to the problem, though I do need to put thought into it but rather my question is if this conceptual problem has a name or has been addressed at already in computer science.

I want to create a list of numbered defines, each uniquely mapped, and divided into groups based on type. The goal is a design that does not require renumbering or shifting when reaching the end of the previously allotted space for a certain type. An example may help

```
    // Dogs (1 to 3 available)
    define DOG_1            1
    ....
    define DOG_3            3

    // Cats (4 to 6 available)
    define CAT_4            4
    ....
    define CAT_6            6

    // Pigs (7 to 10 available)
    define PIG_7            7
    ...
    define PIG_10           10

```

Now if I want to add space for more dogs it requires shifting etc.

This problem seems similar to something found in memory allocation/fragmentation. I want to find literature that addresses the problem if it exists.

Thanks, Godrick

# Answer
> 1 votes
You might be looking for an enum. See https://en.wikipedia.org/wiki/Enumerated\_type.

---
Tags: storage, ordering
---


title: Indexing a random permutation

text:
# Question
Title: Indexing a random permutation
I am curious if there exists a method for specifying a permutation $F\_k: X \to X$ with a small(ish) $k$.

Something that comes very close to my goal is a block cipher, say AES. But block ciphers have fixed block size (e.g. 64, 128 bits), and I want something with parameterizable (and smaller) "block size" $\log\_2 |X|$. I also don't need many characteristics of block ciphers (e.g. $k$ secrecy, etc.), only the permutation part.

Something else that is quite close is the Lehmer code. However, this takes into consideration all possible permutations $|X|!$, and would need the index (or "key") $k$ to be as large as $|X| \log\_2 |X|$. I am happy with only $K \<\< |X|!$ possible permutations (so long as $K$ is "big enough").

# Answer
> 2 votes
You can build a block cipher with any desired block size, using a method called "format preserving encryption". The block size doesn't have to be limited to 64 bits or 128 bits. This will provide a reasonable solution to your problem.

See Bijective algorithm(s) that can shuffle a range of numbers back and forth, Pseudo random, unqiue integer numbers in a given range, Invertible function that randomizes order, Efficiently generating a uniformly random list of unique integers in a range, Lazily computing a random permutation of the positive integers.

# Answer
> 1 votes
If you don't want to use $|X|\log|X|$ bits you have to specify which permutations you want. Since that's up to you, basically any reasonable method works. For example you can pick $F\_k$ to be the $k$-th permutation in lexicographic order and just cut off $k$ whereever you want.

---
Tags: randomness, cryptography, permutations
---


# Question
Title: Cannot find paper: All k nearest neighbors search in N*log(N) using distance indices for log(N) support points
I remember reading a paper about finding k nearest neighbors for all N multi-dimensional objects in the set.

I've tries to find it again many times, but have failed so far.

The algorithm was as follows:

1. Each object is assigned a sorted queue of nears neighbors (maximum size is k). Let's assume that $k \< log(N)$
2. Each time you calculate $distance(A, B)$ try to add A into B's neighbor list and vise versa.
3. Choose $log(N)$ support objects (say, first $log(N)$ objects out of $N$). (Or maybe that was $sqrt(N)$)
4. For each support, build the distance-based index containing all N objects
5. After the index construction, every object has a candidate list of k nearest neighbors. All real nearest neighbors are not further than the furthest neighbor in the candidate list - candidate neighbor radius.
6. For each point we use triangle inequality and current neighbor radius to constrain the distances between a candidate point and the support points: $|dist(candidate\_i, support\_j) - dist(point, support\_j)| \<= radius$. We efficiently extract the candidates that fall in radius-based ranges for all support points.
7. We calculate the distances for those candidates and update the nearest-neighbor lists for both the current point and the candidate points.
8. As we process more points, the neighbor lists become "tighter" - the radius, the distance to the furthest neighbor decreases with each update of the list.
9. Tighter constraints mean that the candidate lists become smaller and smaller after each processed point and leading to total run time of $N\*log(N)$.

So, why do I need the paper again? First of all, several people have asked me for it and I was surprised I cannot find it again. More importantly, it did not work well for me. This might be caused by a bad choice of the support objects. I remember nothing about the selection process.

# Answer
> 2 votes
Found the paper finally. Not sure I've read exactly the same paper (maybe I read some SO or SE answer or some other paper that inspired/was inspired by this paper). Nethertheless, the algorithm is exactly the same.

A Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces by Edgar Chávez and Karina Figueroa and Gonzalo Navarro. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.9299 http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A580FE7BF3251BC23DB793E3B1DFDF64?doi=10.1.1.21.9299&rep=rep1&type=pdf

---
Tags: nearest-neighbour
---


# Question
Title: What is the relationship between minimum sized vertex covers and complete graphs?
What is the relationship between the sizes of minimum sized vertex covers and complete graphs?

# Answer
> 2 votes
The size of minimum vertex cover in a complete graph $K\_n$ (on $n$ vertices for $n \> 1$) is equal to $n-1$.

It is easier to understand using the fact that minimum vertex covers correspond to the complements of maximum independent vertex sets. In a complete graph $K\_n$ the maximum independent set is clearly has only one vertex and so the size of a minimum vertex cover is equal to $|V| - \text{ size of maximum independent vertex set} = n-1$.

# Answer
> 2 votes
A set of vertices is a vertex cover iff its complement is an independent set.

Indeed, a set $S$ is a vertex cover if for all edges $(x,y)$, either $x \in S$ or $y \in S$.

Conversely, a set $S$ is an independent set if for all edges $(x,y)$, either $x \notin S$ or $y \notin S$.

Despite this strong relation between minimum vertex cover and maximum independent set, in some sense maximum independent set is much harder: while minimum vertex cover has several 2-approximation algorithms, it is NP-hard to approximate maximum independent set to within $n^{1-\epsilon}$.

Finally, let me mention that a set of vertices is an independent set in a graph iff it is a clique in the complement graph (formed by replacing edges by non-edges and vice versa). This gives a relation between minimum vertex cover and maximum clique on the complement graph.

---
Tags: graphs, clique
---


title: How one epoch completes in Perceptron?

text:
# Question
Title: How one epoch completes in Perceptron?
I am confusing on completing one epoch, I am using Single Layer Feed Forward neural Network approach. Lets suppose i have a data of OR Gate:

```
X1  X2   Target
0   0    0
0   1    1
1   0    1
1   1    1

```

Now we initialize weights (w1 and w2 with 0) and bias 1, it satisfy our first condition `0 0 0` with delta rule (T-O=0) but when we use same weight and same bias with `0 1 1` this row not satisfy with (w1 = 0 , w2 = 0, b= 1) so we change our weight and bias values, now my question is:

We changed value on 2nd row, now we have new weight values and bias value, do we need to check the third row which is `1 0 1` with new weight and bias value or with old one which is (*w1=0, w2=0, b=1*) ? and if we check 2nd row 3rd row and 4th row with new values and it satisfy 2nd 3rd and 4th row with new value, does this complete our 1st epoch ? but how because we didn't check the first row with new value.

# Answer
> We changed value on 2nd row, now we have new weight values and bias value, do we need to check the third row which is `1 0 1` with new weight and bias value or with old one which is (*w1=0, w2=0, b=1*) ?

The Perceptron processes one example at a time. The weights are **immediately** applied and subsequently updated (if the prediction is not correct).

> if we check 2nd row 3rd row and 4th row with new values and it satisfy 2nd 3rd and 4th row with new value, does this complete our 1st epoch?

Applying the learning rule to each example in the training set is called an **epoch**.

Finishing an epoch doesn't mean that the perceptron converges to zero training error (it's typical to run multiple epochs).

For example, given:

```
(X1)--\
       \
        \ W1
         \
(X2)--W2--+-Y---O
         /
        / B
       /
 (1)--/

```

with:

$$Y = W\_1 \cdot X\_1 + W\_2 \cdot X\_2 + B$$

$$ O = \begin{cases} 0 & \text{if $Y \le 0$} \\ 1 & \text{if $Y \> 0$} \end{cases} $$

$$\delta = Target - O$$

$$\Delta W = \epsilon \cdot \delta \cdot O$$

If $\epsilon = 1$ and $W\_1 = W\_2 = B = 0$:

```
X1  X2  Target   W1    W2     B     Y  O  Delta   W1'   W2'     B'
 0   0     0      0     0     0     0  0      0    0     0      0
 0   1     1      0     0     0     0  0      1    0     1      1  <-error
 1   0     1      0     1     1     1  1      0    0     1      1
 1   1     1      0     1     1     2  1      0    0     1      1
--------- END OF EPOCH 1 / NOT CONVERGED ------------------------
 0   0     0      0     1     1     1  1     -1    0     1      0  <-error
 0   1     1      0     1     0     1  1      0    0     1      0
 1   0     1      0     1     0     0  0      1    1     1      1  <-error
 1   1     1      1     1     1     3  1      0    1     1      1
--------- END OF EPOCH 2 / NOT CONVERGED ------------------------
 ...
--------- END OF EPOCH 3 / NOT CONVERGED ------------------------
 ...                                                              NO ERROR
--------- END OF EPOCH 4 / CONVERGED ----------------------------

```
> 3 votes

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


# Question
Title: What does it mean to add up O-terms with different variables?
Is this true? O(n) + O(k) =O(n+k).I have searched for it ,the answers were quite ambiguous and I couldn't find a good explanation.

# Answer
> 2 votes
Yes, this is true.

The LHS means that for some $N$, $M$ and some constants $c\_n,c\_k$,

$$n\ge N,k\ge M\implies f(n,k)\le c\_nn+c\_kk.$$

The RHS means that for some $N'$, $M'$ and some constant $c$,

$$n\ge N',k\ge M'\implies f(n,k)\le c(n+k).$$

These two statements are equivalent if you take $c\leftarrow\max(c\_n,c\_k),N'\leftarrow N,M'\leftarrow M$ one way and $c\_n=c\_k\leftarrow c,N\leftarrow N',M \leftarrow M'$ the other.

# Answer
> 2 votes
Without further context, the equation

$\qquad O(n) + O(k) = O(n+k)$

is ambiguous and therefore rather meaningless. I'll explain why.

First, recall that Landau notation defines *sets*. The definition commonly used in CS is, with $f : \mathbb{N} \to \mathbb{R}\_{\>0}$,

$\qquad O(f) = \\{ g : \mathbb{N} \to \mathbb{R}\_{\>0} \mid \exists\\, c \> 0, n\_0 \geq 0.\ \forall\\, n \geq n\_0.\ g(n) \leq cf(n) \\}$.

Note how $n$ is a *bound* variable inside the set expression. It's only a label for the *abstract* parameter of the mathematical functions. Therefore,

$\qquad O(n) = O(k)$.

Note how, with this definition, it's completely unclear what $O(n + k)$ is supposed to mean. That is not (only) an oversight in the definition; as referenced here and here, there simply is no rigorous definition that does all we want. The use of multi-parameter $O$ in the literature is usually sloppy, if not to say wrong, and only to be read in a hand-waving kind of way.

Now, in algorithm analysis such terms do not appear on paper on their own. Say, $n$ is the number of nodes of the input graph, and $k$ its diameter. Then, we may perform two subroutines, one that runs in time $O(n)$ (it doesn't depend on the diameter), and the other runs in time $O(k)$ (it doesn't depend on the number of nodes). Then, we sort of understand what $O(n + k)$ is *supposed* to mean.

Now, back to your original expression. The question is, what's variable and what's constant? To make the point, consider $O(n + k^2)$ instead. We can read it as

* $O(n)$ if $k$ is constant,
* $O(k^2)$ if $n$ is constant, and
* unsimplified (with unclear meaning) if neither is constant.

To make this explicit, I write $O\_x$ to imply that $x$ is the variable used in the definition of $O$ here. In the above example, we get

* $O\_n(n + k^2) = O\_n(n) = O\_x(x)$,
* $O\_k(n+k^2) = O\_k(k^2) = O\_x(x^2)$, and
* $O\_{n,k}(n + k^2) =\ ?$.

Here we immediately see that the three are different things!

Now we have notation to write down what we really mean in our setting:

$\qquad O\_{n,k}(n) + O\_{n,k}(k) = O\_{n,k}(n + k)$.

Here, $n$ and $k$ are both independent variables!
(Let's ignore for a moment that $O\_{x, y}$ is not defined by the definition I give at the top; it's inherently single-parameter. We're hand-waving, as I said.)
Note how this is different from

$\quad O\_n(n) + O\_k(k) \neq O\_{n,k}(n+k)$,

which is what just inserting the definiton of $O$ in the straight-forward way would give you.

While the "result" read as a two-variable $O$-term doesn't have a lot of meaning on its own, we can use it as a stepping stone! Once we fix a functional relationship between $n$ and $k$ -- we may investigate $k \sim n$ vs $n \sim \log n$ vs $k = 10$, for instance -- we get back to single-variable $O$ which is perfectly well-defined.

This is not a mathematically rigorous approach, but if we don't accidentally "simplify" away terms in the hand-wavy two-parameter world that we shouldn't, inserting the functional relationship afterwards gives the same result as doing the whole analysis with it in mind -- it's just a substituion. Some care has to be taken.

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