# Question
Title: Is there a data structure for efficiently searching a string that contains a given substring?
This question arose from a practical problem: given a set of texts, find one, which contains a given string (not word).

Let $S$ be a set of $n$ strings, and $l$ the length of the longest string in $S$. What will be the best data structure to efficiently search a string that contains a substring of length $k$ in $S$?

Sequential scan with Knuth–Morris–Pratt algorithm yields $O(n(l+k))$ searching complexity. I thought maybe something similar to tries exists.

# Answer
You can use a suffix tree, which is a compressed trie that allows you to store all possible suffixes from the strings in $S$. To search for a substring $q$, you can simply traverse the suffix tree from the root1 to the leaves, making comparisons with the edge keys (each of which represents one or more characters). If a branch does not exist in the tree, then $q$ is not a substring in $S$; otherwise, it is.

If you want to find out the exact string in $S$ that contains $q$, you can annotate the nodes of the suffix tree so that they contain this information (e.g., you can add a string number and a starting position). This is the idea generalized suffix trees are built upon.

The running time of this approach is $O(n \\: l)$ for the construction of the suffix tree, plus $O(k)$ for the substring search, for a total of $O(n \\:l + k)$.

---

1 Note that every substring of a string $T$ is the prefix of exactly one suffix of $T$. Therefore, substring search can always be performed starting at the root of a suffix tree.
> 4 votes

# Answer
You could append all of the $n$ strings together, and add an arbitrary character '\\$' not in the pattern to separate them. Then you could apply the Z algorithm on your original pattern and this new string to yield time complexity $O(nl+k)$ which is more efficient than your suggested $O(nl+nk)$.

Actually, you could still iterate with KMP for $O(nl+k)$ time, beceause the $k$ component is preprocessing the pattern you are trying to find. This only has to be done once, regardless of the number of strings you are checking.
> 6 votes

# Answer
The answer depends on the number of patterns, the total size of the strings $nl$, and how many times you expect the pattern to occur in each string.

* If you have a few patterns, a standard string matching algorithm such as KMP is sufficient.
* If you have many patterns at the same time, you should use an algorithm that preprocesses the patterns (e.g. Aho-Corasick).
* If you have even more patterns or the patterns come in multiple batches, you should preprocess the strings instead. The suffix tree is nice in theory, but it's slow and memory-hungry in practice. The suffix array works better, and the FM-index is a nice substitute if you don't have enough memory for the suffix array.
* If you have really many patterns in a single batch, you should preprocess both the strings and the patterns and match the resulting structures against each other. The basic idea is straightforward, but you'll have to do some work to get the details right.
* If you preprocess the strings and expect the patterns to have many occurrences in each string they match, you should augment the index (e.g. suffix array or FM-index) with a document retrieval structure.
* If you preprocess the strings and even the FM-index won't fit into memory, the string B-tree should work reasonably well.
> 3 votes

---
Tags: data-structures, search-algorithms, strings, exact-string-matching
---


# Question
Title: Creating a binomial heap from an array in Θ(n) time
I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert it to a binomial heap.

Does anyone know a method that can convert an array of numbers to a binomial heap in $\Theta(n)$ time? Wikipedia claims that insertion takes $O(1)$ amortized time but I need to refer to the worst case.

# Answer
$O(f(n))$ *amortized time* means that if we make $k$ consecutive operations, **total time** does not exceed $k \cdot cf(n)$ for a chosen positive constant $c\>0$.

In your case, each insertion is worst-case $O(\log n)$. However, they're amortized $O(1)$. It means that if you make $n$ consecutive insertions (that is, build a heap from an array), total time is bounded by $c \cdot n$ for some constant $c\>0$ - that is, the total time is $\Theta(n)$.

If you want to prove formally that the total time of constructing $n$-element heap is $\Theta(n)$:

* Denote $k$ as the current number of items in our heap (in the beginning, $k=0$).
* Write $k$ in binary; if its $i$-th bit is set, we have a binomial tree of size $2^i$.
* If you insert next element when there are already $k$ of them, you create a new tree of size $2^0$; if there was already a heap of size $2^0$, you merge them into a heap of size $2^1$; if there was already a heap of size $2^1$, you merge them and so on, until you find out there was no heap of size $2^t$ in a previous state. Time needed is thus proportional to the number of ones in the end of binary representation of $k$ (plus 1).
* Note that we make first heap for every $k$; we'll make the second heap for each odd $k$, third heap for each $k \equiv 3 \mod{4}$ and so on. It means that $i$-th operation inside "merge-heap" will be done roughly once in $\frac{n}{2^i}$ insertions.

Now note that number of (constant time) create-tree/merge-tree operations cannot exceed $$ \frac{n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} + \dots = 2n. $$

Thus, the total time for the algorithm "just make $n$ consecutive insertions" is $\Theta(n)$.
> 3 votes

# Answer
The answer given above by mnbvmar is fine. Just want to add one thing. Total number of create-tree/merge-tree operations cannot exceed $$\frac {n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} + \dots +\frac{n}{2^{\lfloor \log n\rfloor}}\\,.$$

Now we can rewrite the expression as $$ n \left(\frac {1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \dots +\frac{1}{2^{\lfloor \log n\rfloor}}\right)\\,.$$ The series inside the brackets **converges** to constant 2. So the running time of the algorithm is $O(n)$.
> 1 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, heaps, amortized-analysis
---


# Question
Title: Kolmogorov complexity of a sequence of prime numbers
> Let's say $p\_1, p\_2, p\_3, \ldots $ is the increasing sorted sequence of all prime numbers. Prove that there exists a constant $n\_0 \in \mathbb{N}$, so that for all $n \ge n\_0$: $$K(p\_n) \< \log\_2(p\_n) − 2.$$ Hint: Prime number theorem: $p\_n \in \Theta (n \ln n)$.

I think, I could have a program A, which generates $p\_n$ in $n\ln n$. I could just give A the index of my prime number and it would generate it.

Another idea of mine was to prove it by contradiction and assume the opposite is true but I can't really make that work. My biggest problem is that I can't find an upper limit to the representation of prime numbers and start from there. Normally I'd just use the factorization for integers…

Any help is appreciated!

# Answer
Since we can generate $p\_n$ given $n$, $K(p\_n) \leq K(n) + O(1) \leq \log\_2 n + O(1)$. The prime number theorem implies that $p\_n = \Theta(n\ln n)$, and so $\log\_2(p\_n) = \log\_2 n + \log\_2\log\_2 n \pm O(1)$. You take it from here.
> 3 votes

---
Tags: kolmogorov-complexity
---


title: Problem with Church numerals evaluation

text:
# Question
Title: Problem with Church numerals evaluation
I am trying to understand Church's Numerals for 4:

$$4 = \lambda f.\\, \lambda x.\\, f f f f x\\,.$$

This will be evaluated in the following order:

$$\lambda f.\\, \lambda x.\\, (f (f (f (f x) ) ) )\\,.$$

My question is why the function body will not evaluate left outer most, like

$$( ( ( ( (f f) f) f) f) x)\\,?$$

# Answer
> 5 votes
**Function application is not associative**. It may seem at first that this is valid because function composition is associative, but according to Wikipedia,

> Bracketing may be used and may be needed to disambiguate terms. For example, ${\lambda x.((\lambda x.x)x)}$ and ${(\lambda x.(\lambda x.x))x}$ denote different terms (although they coincidentally reduce to the same value). Here the first example defines a function that defines a function and returns the result of applying $x$ to the child-function (apply function then return), while the second example defines a function that returns a function for any input and then returns it on application of $x$ (return function then apply).

$\lambda f.\lambda x.((ff)f)x$ is a distinct lambda term from $\lambda f.\lambda x.(f(ff))x$.

# Answer
> 2 votes
The thing is, the church numeral for number 4 is $λf.λx.f(f(f(f(x))))$ \[ Wiki \].

It can not be evaluated either way, because we have function application, not composition. Also, it is **left** associative, not right, that's why we need the paretheses.

---
Tags: lambda-calculus
---


# Question
Title: Heap sort best case time - $\mathcal O(n)$?
It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ?
The argument here is, If my input has all the same keys, then every time I delete the root, I do not need to heapify, I just need to swap with the rightmost leaf.

Why is the above argument not valid ?

# Answer
Because the analysis is performed assuming that there is a strict total order on the keys. Therefore if you are sorting, for example, integers on their usual order, the lower bound applies only as long as each key is different. If you allow the order to not be strict then the analysis is not particularly interesting, your example is indeed a best case.

Observe that the assumption of a strict total order is actually a small cheat, because we are also implicitly assuming that all comparisons cost $\Theta(1)$. If we disallow repeated keys, then the number of different keys is not bound by a constant, which means that the key size is also not bound by a constant, in contradiction with the constant cost assumption for comparisons.
> 1 votes

# Answer
Big O is for measuring the worst case time complexity, and in this case it is $O(n)$. The best case is written as $\Omega$. Here is a paper describing the reasoning for the best case. We generally do not consider the case of having only identical elements in the list.
> 0 votes

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


# Question
Title: How to approach DFA construction with substring constraints?
We have to construct a DFA over the alphabet 0 and 1 for:

> Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

I haven't reached to regular expression in the book which I am using. I am currently in unit 2 and regular expressions is from unit 3.

# Answer
Use the state of the automaton to "remember" enough information about the string that you've seen so far to allow you to determine whether the string you've read is in the language. This is true essentially independently of the language you're trying to recognize.
> 2 votes

# Answer
Intuitively, DFAs are machines that perform some computation, their limitation is the fact that they must use no memory. But since the substring size is fixed and finite, we can certainly check whether a string belongs to the language with a memoryless computation.

We only need to keep track of the last four symbols we read, and if there are too many zeros among those, we immediately reject the string: you can model that with a non-accepting state that only has transitions to itself.

I leave the details to you.
> 2 votes

---
Tags: finite-automata, substrings
---


# Question
Title: How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?
I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively simple for basic regular expressions. However I can't seem to wrap my head around how to simulate backreferences, lookaheads, and lookbehinds.

From what I read in the purple dragon book I understood that to simulate a lookahead $r/s$ where the regular expression $r$ is matched if and only if the match is followed by a match of the regular expression $s$, you create a non-deterministic finite state automaton in which $/$ is replaced by $\varepsilon$. Is it possible to create a deterministic finite state automaton that does the same?

What about simulating negative lookaheads and lookbehinds? I would really appreciate it if you would link me to a resource which describes how to do this in detail.

# Answer
> 23 votes
First of all, backreferences can *not* be simulated by finite automata as they allow you to describe non-regular languages. For example, `([ab]^*)\1` matches $\\{ww \mid w \in \\{a,b\\}^\*\\}$, which is not even context-free.

Look-ahead and look-behind are nothing special in the world of finite automata as we only match *whole* inputs here. Therefore, the special semantic of "just check but don't consume" is meaningless; you just concatenate and/or intersect checking and consuming expressions and use the resulting automata. The idea is to check the look-ahead or look-behind expressions while you "consume" the input and store the result in a state.

When implementing regexps, you want to run the input through an automaton and get back start and end indices of matches. That is a very different task, so there is not really a construction for finite automata. You build your automaton as if the look-ahead or look-behind expression were consuming, and change your index storing resp. reporting accordingly.

Take, for instance, look-behinds. We can mimic the regexp semantics by executing the checking regexp concurrently to the implicitly consuming "match-all" regexp. only from states where the look-behind expression's automaton is in a final state can the automaton of the guarded expression be entered. For example, the regexp `/(?=c)[ab]+/` (assuming $\\{a,b,c\\}$ is the full alphabet) -- note that it translates to the regular expression $\\{a,b,c\\}^\*c\\{a,b\\}^+\\{a,b,c\\}^\*$ -- could be matched by

<sup>\[source\]</sup>

and you would have to

* store the current index as $i$ whenever you enter $q\_2$ (initially or from $q\_2$) and
* report a (maximum) match from $i$ to the current index ($-1$) whenever you hit (leave) $q\_2$.

Note how the left part of the automaton is the parallel automaton of the canonical automata for `[abc]*` and `c` (iterated), respectively.

Look-aheads can be dealt with similarly; you have to remember the index $i$ when you enter the "main" automaton, the index $j$ when you leave the main automaton and enter the look-ahead automaton and report a match from $i$ to $j$ only when you hit the look-ahead automaton's final state.

Note that non-determinism is inherent to this: main and look-ahead/-behind automaton might overlap, so you have to store all transitions between them in order to report the matching ones later, or backtrack.

# Answer
> 12 votes
The authoritative reference on the pragmatic issues behind implementing regex engines is a series of three blog posts by Russ Cox. As described there, since backreferences make your language non-regular, they are implemented using *backtracking*.

Lookaheads and lookbehinds, like many features of of regex pattern matching engines, don't quite fit into the paradigm of deciding whether or not a string is a member of a language or not. Rather with regexes we are usually searching for substrings within a larger string. The "matches" are substrings that are members of the language, and the return value is the beginning and end points of the substring within the larger string.

The point of lookaheads and lookbehinds is not so much to introduce the ability to match non-regular languages, but rather to adjust where the engine reports the begin and end points of the matched substring.

I'm relying on the description at http://www.regular-expressions.info/lookaround.html. The regex engines that support this feature (Perl, TCL, Python, Ruby, ...) all seem to be based on backtracking (i.e., they support a much larger set of languages than just the regular languages). They seem to be implementing this feature as a relatively "simple" extension of backtracking, rather than trying to construct real finite automata to perform the task.

## Positive Lookahead

The syntax for *positive lookahead* is `(?=`*regex*`)`. So for example `q(?=u)` matches `q` only if it is followed by `u`, but does not match the `u`. I imagine they implement this with a variation on backtracking. Create a FSM for the expression before the positive lookahead. When that matches remember where it ended and start a new FSM that represents the expression inside the positive lookahead. If that matches then you have a "match", but the match "ends" just before the position where the positive lookahead match began.

The only part of this that would be hard without backtracking is that you need to remember the point in the input where the lookahead starts and move your input tape back to this position after you are done with the match.

## Negative Lookahead

The syntax for *negative lookahead* is `(?!`*regex*`)`. So for example `q(?!u)` matches `q` only if it is not followed by `u`. This could be either a `q` followed by some other character, or a `q` at the very end of the string. I imagine this is implemented by creating an NFA for the lookahead expression, then succeeding only if the NFA fails to match the subsequent string.

If you want to do it without relying on backtracking you could negate the NFA of the lookahead expression, then treat it the same way you treat positive lookahead.

## Positive Lookbehind

The syntax for *positive lookbehind* is `(?<=`*regex*`)`. So, for example, `(?<=q)u` matches `u`, but only if it is preceded by `q`, but does not match the `q`. Apparently this is implemented as a complete hack where the regex engine actually backs up $n$ characters and tries to match *regex* against those $n$ characters. This means that *regex* must be such that it only matches strings of length $n$.

You might be able to implement this without backtracking by taking the intersection of "string that ends with *regex*" with whatever part of the regex that comes before the lookbehind operator. This is going to be tricky though, because the lookbehind *regex* might need to look further back than the current beginning of the input.

## Negative Lookbehind

The syntax for *negative lookbehind* is `(?<!`*regex*`)`. So, for example, `(?<!q)u` matches `u`, but only if it is not preceded by `q`. So it would match the `u` in `umbrella` and the `u` in `doubt`, but not the `u` in `quick`. Again, this seems to be done by calculating the length of *regex*, backing up that many characters, testing for the match with *regex*, but now failing the whole match if the lookbehind matches.

You might be able to implement this without backtracking by taking the negation of *regex* and then doing the same as you would do for positive lookbehind.

# Answer
> 6 votes
At least for backreferences, this is not possible. For example, the regex `(.*)\1` represents a language that is not regular. What that means is that it's impossible to create a finite automaton (deterministic or not) that would recognize this language. If you want to prove this formally, you can use the pumping lemma.

# Answer
> 5 votes
I've been looking into this myself, and you should be able to implement lookahead using an Alternating Finite Automaton. When you encounter lookahead, you nondeterministically run both the lookahead and the remainder of the expression, accepting only if *both* paths accept. You can convert an AFA to an NFA with reasonable blowup (and thus to a DFA), although I haven't verified that the obvious construction plays nicely with capture groups.

*Fixed-width* lookbehind should be perfectly possible without backtracking. Let *n* be the width. Starting from the point in your NFA where the lookbehind began, you'd split out states looking backward so that every path into the lookbehind ended with *n* characters worth of states that *only* went into the lookbehind. Then, add lookahead to the beginning of those states (and immediately compile the subgraph from AFA to NFA if desired).

Backreferences are, as others have mentioned, not regular, so they cannot be implemented by a finite automaton. In fact, they're NP-complete. In the implementation I'm working on, quick yes/no matching is paramount, so I chose not to implement backreferences at all.

---
Tags: automata, finite-automata, regular-expressions
---


title: Why it converts to T

text:
# Question
Title: Why it converts to T
The AND function in the lambda is:

```
and = (λ a. λ b. a b F)

```

I have following expression:

```
and T T

```

then the result will become `T` and I am asking me why?

When I do the beta reduction, then I understand, why I've got `T`:

```
(λ a . λ b . a b (λ x . λ y . y)) (λ x . λ y . x) (λ x . λ y . x)
(λ b . a b (λ x . λ y . y))[a →(λ x . λ y . x)] (λ x . λ y . x)
(λ b . (λ x . λ y . x) b (λ x . λ y . y)) (λ x . λ y . x)
((λ x . λ y . x) b (λ x . λ y . y))[b→(λ x . λ y . x)]
(λ x . λ y . x) (λ x . λ y . x) (λ x . λ y . y)
(λ y . x)[x →(λ x . λ y . x)] (λ x . λ y . y)
(λ y . (λ x . λ y . x)) (λ x . λ y . y)
(λ x . λ y . x)[y→(λ x . λ y . y)]
(λ x . λ y . x)
T

```

But when I shortened it like:

```
T T F

```

then I've got F, because:

```
T T F
T F
F

```

What am I interpreting wrong?

# Answer
> 4 votes
$T \equiv \lambda x. \lambda y. x$, which means it is a $\lambda$-function of two arguments, returning the first one, so $(T\ T\ F)$ $\beta$-reduces to $T$, which can be shown more formally as follows.

$$T\ T\ F \equiv (\lambda x. \lambda y. x)\ T\ F \to\_\beta (\lambda y. T)\ F \to\_\beta T$$

---
Tags: lambda-calculus
---


# Question
Title: End-Of-The-Line Augmented Problem of PPAD
Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line:

**End-Of-The-Line Problem:** $G$ is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. $G$ is specified by giving a polynomial-time computable function $f(v)$ (polynomial in the size of $v$) that returns the predecessor and successor (if they exist) of the vertex $v$. Given a vertex $s$ in $G$ with no predecessor, find a vertex $t≠s$ with no predecessor or no successor. (The input to the problem is the source vertex s and the function $f(v)$). In other words, we want any source or sink of the directed graph other than $s$.

Let's consider the slightly augmented version of End-Of-The-Line problem.

**End-Of-The-Line Augmented Problem:** The definition is same as for End-Of-The-Line expect that it's required to find not a vertex $t≠s$ with no predecessor or no successor, but the exact end of the path of the given source vertex $s$.

Intuitively, it seems like **End-Of-The-Line Augmented Problem** is not more in PPAD, just because it requires something more stronger than **End-Of-The-Line Problem**. How to show that **End-Of-The-Line Augmented Problem** is NP-hard?

# Answer
This question is answered in the original paper by Papadimitriou 1994 original paper (pdf). It turns out that the problem is not only **NP**-hard but also **PSPACE**-hard, this is theorem 2 on page 506.
> 5 votes

---
Tags: complexity-theory, graphs
---


title: Identify similar functions

text:
# Question
Title: Identify similar functions
I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and for each input $i$, $f(i) = g(i)$. Moreover, the two functions $f$ and $g$ could be implemented in a completely different way, e.g. different algorithms that solve the same problem.

In my opinion, clone detection could be useful, but I cannot compare both tokens or ASTs since the implementations are completely different. A semantic comparison could be a possible solution, but are there other techniques that I can use?

# Answer
The problem is not decidable (by reduction from the Halting problem), so there is no perfect algorithm that always terminates and always gives the correct answer. Therefore, you'll need to make some tradeoffs. That will depend on the specifics of your particular application, so it's hard to recommend a particular technique without knowing how you plan to use it.
> 3 votes

---
Tags: programming-languages, compilers, program-optimization, comparison
---


# Question
Title: Discrete assignment problem with penalties
I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods.

It's an single agent problem where we have to assign agent to perform exactly one task $j$ during each period $i$, i.e., $\sum\_{j=1}^n x\_{ij} = 1$ for $i=1,\ldots,m$ where $x\_{ij}=1$ if agent is assigned to task $j$ in period $i$ and $0$ otherwise.

We receive a reward of $c\_{ij}$ for performing task $j$ on period $i$. Additionally, there is a penalty $p$ each time the task changes between two consecutive periods. If during period $i$ we assign the agent to perform task $j$ and on $i+1$ the task $j^\prime$, we subtract the penalty $p$ from the total reward of all assignments.

We want to assign the agent in such way that the total profit $$\sum\_{i=1}^m \sum\_{j=1}^n x\_{ij} c\_{ij} - \text{penalties introduced by changing task between periods}$$

is maximized. I have been able to model this as an integer program with binary decision variables, but I was thinking maybe there is some other type of recursive algorithm (via dynamic programming) that could handle this problem also. Is this a known problem with solution methods present in literature? It seems like it could have already been studied, but I haven't been able to find a name for this kind of problem.

# Answer
Riley's answer is excellent. It is possible to improve the running time further to $O(mn)$ time, using dynamic programming. This saves a factor of $n$ in the running time.

Define $T\[i,j\]$ to be the total profit of the best assignment for times $i,i+1,\dots,m$, assuming that at time $i$ the agent is assigned to task $j$. We'll compute all of the $T\[i,j\]$ values, in order of decreasing $i$, using the following recurrence:

$$T\[i,j\] = c\_{ij} + \max(T\[i+1,j\], \max\\{T\[i+1,j'\] : 1 \le j \le n, j' \ne j\\} - p),$$

or equivalently,

$$T\[i,j\] = c\_{ij} + \max(T\[i+1,j\], \max\\{T\[i+1,j'\] : 1 \le j' \le n\\} - p).$$

Naively, it looks like filling in a single cell will take $O(n)$ time so computing all the $T\[i,j\]$ values will take $O(n^2)$ time. However, we can speed it up with a trick.

Define

$$M\[i\] = \max(T\[i,1\],\dots,T\[i,n\]).$$

We obtain the improved recurrence

$$T\[i,j\] = c\_{ij} + \max(T\[i+1,j\], M\[i+1\] - p).$$

We'll fill in the $T\[i,\cdot\]$ and $M\[i\]$ values simultaneously, in order of decreasing $i$. Once we've filled in $T\[i,1\],\dots,T\[i,n\]$, we can compute $M\[i\]$ in $O(n)$ time. Then, once we know $M\[i\]$, we can compute each $T\[i-1,j\]$ in $O(1)$ time using the improved recurrence, so we can compute $T\[i-1,1\],\dots,T\[i-1,n\]$ in $O(n)$ time once we know $M\[i\]$. Finally, $M\[1\]$ is the final answer to the problem.

In this way, we do $O(n)$ work per value of $i$, and there are $m$ values of $i$. Consequently, the total running time is $O(mn)$.
> 3 votes

# Answer
First, you can model the task management as a directed graph. Suppose you have a source node $a$, a sink node $b$, and $mn$ nodes, one for each task. We say that $v\_{ij}$ represents the $j$th task on the $i$th time period. The edges are as follows.

$$E=\\{(a,v\_{11}),(a,v\_{12}),\dots,(a,v\_{1n})\\}\cup\\\\{(v\_{ij},v\_{(i+1)j'})\vert 1\leq i\<m,1\leq j\leq n, 1\leq j'\leq n\\}\cup\\\\{(v\_{m1},b),(v\_{m2},b),\dots (v\_{mn},b)\\}$$

Basically, the source node connects to each task in the first time period, each combination of tasks in adjacent time periods are connected, and the tasks on the final time period are connected to the sink node. The weight of an edge $(v\_{ij},v\_{(i+1)j'})$ is $c\_{(i+1)j'}$ if $j=j'$ and $c\_{(i+1)j'}-p$ otherwise. The weight of an edge $(a,v\_{1j})$ is $c\_{1j}$, and the weight of an edge to the sink is $0$.

The goal is to find the maximum path from $a$ to $b$. Since this is a directed acyclic graph, this can be done in $O(V+E)$ time, according to GeeksforGeeks. There are $mn+2$ vertices and $(m-1)n^2+2n$ edges, so the overall time complexity is $O(mn^2)$.
> 2 votes

---
Tags: algorithms, optimization, dynamic-programming, integer-programming, assignment-problem
---


title: Non linear neural networks?

text:
# Question
Title: Non linear neural networks?
The activation of a perceptron style neuron is:

$DotProduct(Inputs, Weights)+Bias \> 0$

That is essentially classifying what side of a (hyper)plane a point is on (positive or negative side), like the below:

$DotProduct(Point, Normal)+D \> 0$

Looking at an N input, M layer perceptron network that has a single output can be seen as classifying a point as inside or outside some hyper shape.

But, it seems like all the tests are linear, and switching to sigmoid activation doesn't seem to add a whole lot of non linearity - like if you were visualizing this NN shape, even a sigmoid activated network would be mostly made up of planes, not curved surfaces.

On the other hand we have support vector machines as a machine learning tool, and using things like the "kernel trick" which can make a non linear classification of points for being inside or outside.

This makes me wonder, is there a version of neural networks that has more free form separation shape?

It seems like it would be possible to have a better performing neural network with fewer neurons and/or layers.

# Answer
> 2 votes
Sigmoid *does* add nonlinearity -- and the nonlinearity "builds" as you add more layers. Neural networks can recognize arbitrary decision boundaries (given enough neurons and enough layers).

I think your visualization of what the sigmoid activation does is a bit off. Take a look at http://playground.tensorflow.org/ and play with some of the tuning knobs to see the kinds of decision boundaries that can be achieved -- that site is a helpful way to get some intuition.

So, the answer to your question is: we don't need a separate version of neural networks. Standard neural networks already can support arbitrary decision boundary shapes.

---

\[ About the kernel trick: The kernel trick can be used here, but is possibly a bit more expensive than in the case of SVM's; for SVM's, there's a particular mathematical trick that avoids the need to generate all of the "extra features", but that trick is specific to SVM's. You can still construct derived features and add them to the feature vector before applying a neural network, though, if you want -- nothing prevents you from doing it. But the kernel trick isn't needed, because neural networks can learn non-linear functions. In contrast, without the kernel trick, SVMs can only learn linear decision boundaries, so it's needed more there. \]

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


# Question
Title: NeuroEvolution: NEAT algorithm innovation numbers
I have been reading up on the NeuronEvolution of Augmented Topologies and there's this little thing that's been bothering me. While reading Kenneth Stanley's Paper on NEAT I came on this figure here:

The innovation numbers go from 1,2,3,4,5,6 to 1,2,3,4,5,6,7 on the first mutation.

On the second one it goes from 1,2,3,4,5,6 to 1,2,3,4,5,6,8,9.

My question is why does it skip number 7 and goes straight up to 8 instead? I didn't find anything related to deleting innovation numbers.

Same thing on this second figure, how did Parent 1 lose 6,7 and where did the 8th gene go to in Parent 2?

# Answer
> 2 votes
Here is what I gathered from skimming the paper for just the figure.

Your first figure, which is the figure 3 in the paper, already has the answer in its caption:

> Figure 3: The two types of structural mutation in NEAT. Both types, adding a connection and adding a node, are illustrated with the connection genes of a network shown above their phenotypes. The top number in each genome is the innovation number of that gene. **The innovation numbers are historical markers that identify the original historical ancestor of each gene. New genes are assigned new increasingly higher numbers.** In adding a connection, a single new connection gene is added to the end of the genome and given the next available innovation number. In adding a new node, the connection gene being split is disabled, and two new connection genes are added to the end the genome. The new node is between the two new connections. A new node gene (not depicted) representing this new node is added to the genome as well.

In figure 3, it could be deduced that the *add connection mutation* (top half) occur preceding the *add node mutation* (buttom half).

* When the add connection mutation occurred, the lowest free innovation number was 7. And so the gene created at that moment was assigned the marker of 7.
* Later, when the add node mutation occurred, 2 new genes were created. And so they were assign the lowest free innovation number at the time which is 8 and 9.

The innovation number is not the indices of each gene inside the array representing a genome.

The innovation number is just a number permanently branded to each gene, telling us when the gene first occur. As if the **year number** when human first evolved a gene for hairless body were written down on the gene itself.

The uses of innovation is then explained around your latter figure, which is figure 4:

> The historical markings give NEAT a powerful new capability. The system now knows exactly which genes match up with which (Figure 4). When crossing over, the genes in both genomes with the same innovation numbers are lined up. \[...\] This way, historical markings allow NEAT to perform crossover using linear genomes with out the need for expensive topological analysis.

From this **I assumed** that innovation number are always ordered increasingly within a genome, but gaps in innovation numbers are allowed to occur within genome. The order is probably ensured simply by the fact that all operations done on genome was designed to not violate this within-genome ordering.

This makes sense because each gene can be thought of as an instruction to construct a graph. By keeping the instruction ordered by when it was introduced, it makes sure that reading instruction on genome from left to right makes sense chronologically.

---
Tags: machine-learning, neural-networks, genetic-algorithms, neural-computing
---


title: Breaking down CNF clauses

text:
# Question
Title: Breaking down CNF clauses
I have an assignment where i have to encode certain problem to conjunctive normal form so i can solve it by using SAT solver. I have been able to encode my problem correctly but the solver is quite slow and most likely the cause for this is the length of some clauses which i have.

So my question is:

How can one break down long clauses into smaller ones and therefore speed up the SAT solver, lets say i have following clause:

$ (x\_1 \vee x\_2 \vee x\_3 \vee ... \vee x\_n) $ where n can potentially be large number.

Is there any way to split this into smaller clauses which would be logically equivalent?

# Answer
The reason why the SAT solver is slow is unlikely to be the size of the clauses, but rather the hardness of the problem itself.

In any case, any instance of CNF-SAT can notoriously be transformed into an equisatisfiable formula with at most three literals per clause by replacing each clause in the form:

$$ ( x\_1 \vee x\_2 \vee \dots \vee x\_n) $$

with:

$$ (x\_1 \vee x\_2 \vee y\_1) \wedge (\neg y\_1 \vee x\_3 \vee y\_2) \wedge \dots \wedge (\neg y\_{n-4} \vee x\_{n-2} \vee y\_{n-3}) \wedge (\neg y\_{n-3} \vee x\_{n-1} \vee x\_n) $$

where $\\{y\_i\\}\_{i \in \mathbb{N}}$ are fresh variables.
> 4 votes

---
Tags: optimization, propositional-logic
---


# Question
Title: Bankers Algorithm-Is the system in safe state?
Could somebody please provide a step-through approach to solving the following problem using the Banker's Algorithm?

A system contains 10 units of resource class Ru. The resource requirements of three user processes P1, P2 and P3 are as follows

```
                      |   P1  |  P2  |   P3   |
Max Requirement       |   8   |  7   |   5    |
Current Allocation    |   3   |  1   |   3    |
Balance Requirement   |   5   |  6   |   2    |
New Request Made      |   1   |  0   |   0    |

```

Using Banker’s algorithm, determine if the projected allocation state is safe and whether the request of P1 will be granted or not.

My solution:

total recources :10 total allocation :7 available: 10 -7 = 3

```
Need
P1     5
P2     6
P3     2

3>2 so P3 can run now available is 6
6>5 so P1 can run now availabl 9
9>6 so P2 can run

```

System is safe state,Hence P1 will be granted.

But I'm not sure if my solution is true.

# Answer
> 3 votes
you can say there is no deadlock if there is a safe sequence for the completion, after $P1$ request is granted there must be a safe sequence where by which every process is completed.

```
After P1 request is granted
                      |   P1  |  P2  |   P3   |
Max Requirement       |   8   |  7   |   5    |
Current Allocation    |   4   |  1   |   3    |
Balance Requirement   |   4   |  6   |   2    |
now the resources left over are 10-4-1-3=2

```

so can we complete with 2 resources? any sequence is possible?

YES

if P3 is given 2 resources it will complete and release all the current allocated resources so our resource count becomes 5 , now we have 5 and we can complete P1 and get back 4 now our resource count is 9 and i need just 6 to complete P2 so a safe sequence is possible. so safe sequence will be

$P3 \rightarrow P1\rightarrow P2$

so $P1$ request is granted

# Answer
> 0 votes
First P3 will be granted as 3\>2 , after that the total no of available resource is 6

then P1 will be granted as 6\>5 , after that the total no of available resources is 9

then P2 will be granted as 9\>6 .

**So the safe sequence for the given problem is P3,P1,P2 .**

---
Tags: algorithms, operating-systems, deadlocks
---


# Question
Title: how to approximate a very complex optimal policy when the distance function is unknown
A policy $P$ is defined as a set of parameters. We want to know the optimal policy $O$, which certainly exists but unfortunately unknown.

$D(P)$ shows how far $P$ is from $O$. The function $D$ itself is unfortunately not known. However, $D(P) - D(Q)$ is known. That is, one can always know which among $P$ and $Q$ is closer to $O$.

What kind of approach can be done for such problem?

In my setting, a policy is in a form of a (convolutional) neural network. $D(P) - D(Q)$ is approximated by a simulation involving an agent with policy $P$ and an agent with policy $Q$. We repeatedly play a two-player game with a clear win/loss where $P$ plays against $Q$. The value of $D(P)-D(Q)$ is equal to the number of times $P$ wins against $Q$, divided by the number of games we play.

# Answer
Let me start with some basic material that covers the case where you know how to compute $D(P)$; then speculate on some methods that might be applicable to your particular situation, where we only know how to compute $D(P)-D(Q)$.

**Gradient descent.** One reasonable approach is to use *gradient descent* to optimize the parameters. If we have an objective function $\Phi(P)$ that tells us the penalty or loss associated with policy $P$, we use gradient descent to try to find parameters $P$ that minimize $\Phi(P)$. This requires that $\Phi(\cdot)$ be continuous and differentiable. Ideally, we'd have a way to compute the partial derivatives (the gradient) of $\Phi$ at any point; but if we don't, one possibility is to use standard methods to approximate the partial derivative, e.g.,

$${\partial \over \partial x} \Phi(P) = {\Phi(P+\epsilon x) - \Phi(P-\epsilon x) \over 2 \epsilon}.$$

**Stochastic gradient descent.** In your situation, stochastic gradient descent is an important optimization that provides significant speedups. The basic idea is that, if we can decompose the objective function as a sum

$$\Phi(P) = \sum\_i \Phi\_i(P),$$

then we can speed up gradient descent. In each step, we evaluate the gradient of $\Phi\_i$ (rather than of $\Phi$, as ordinary gradient descent would do) and take a small step in the direction given by that gradient. This can be a lot more efficient, if computing the gradient of $\Phi\_i$ is more efficient than computing the gradient of $\Phi$.

In your situation, $\Phi(P)$ is defined to be

$$\Phi(P) = \sum\_{i=1}^n {w\_i(P) \over n},$$

where $w\_i(P)$ is 1 if $P$ wins in the $i$th game and 0 otherwise. Therefore, $\Phi$ has the required form to allow you to apply stochastic gradient descent, and you can expect this method to give significant speedups. Effectively, you do only one game simulation per step of (stochastic) gradient descent rather than $n$ game simulations per step.

As a practical matter, there are many further improvements on stochastic gradient descent that are well-studied, including momentum, rmsprop, and many others. Personally, I'd recommend trying the Adam solver; it seems to be state of the art.

So if you knew how to compute $D(P)$, the above would give you a reasonable method for optimizing $P$: simply define $\Phi(P)=D(P)$ and then apply stochastic gradient descent. But you don't... so now we need a way to adjust.

**Your situation.** Your specific situation is more challenging, but there are still some avenues you could explore. For instance, here is one approach you could consider. Fix a reasonable policy $Q\_0$, and define

$$\Phi(P) = D(P) - D(Q\_0).$$

Apply stochastic gradient descent to try to minimize $\Phi(P)$, i.e., to find $P$ that makes $\Phi(P)$ small. Do that for a little while. Then, pick a new policy, call it $Q\_1$, and define

$$\Phi(P) = D(P) - D(Q\_1)$$

and continue iterating. Every so often, you replace $Q\_i$ with a new (better) policy $Q\_{i+1}$ that hopefully is closer to $O$. This might work.

How do you choose $Q\_{i+1}$? One way would be to let $Q\_{i+1}$ be the best policy seen so far. So, effectively, you are constantly trying to find a policy that beats the best policy seen so far. You'd need to tune how often you change $Q$ and play with some parameters.

**Caveats.** However, I suspect that if you're actually dealing with a two-player game, things won't be this simple. In particular, I suspect that your model of the situation is not accurate: that, for several reasons, the fraction of times that $P$ wins against $Q$ is not actually an estimator of $D(P)-D(Q)$.

* The relationship between "fraction of wins" vs $D(P)-D(Q)$ is probably not linear. For example, Magnus Carlsen (world chess champion; rated about 2800) will beat me 100% of the time in chess. He will presumably also beat Arnold Schwarzenegger (rated about 1500) 100% of the time. But Arnold will probably beat me 100% of the time, too, because I suck at chess. Letting $P\_M = $ Magnus Carlsen, $P\_A = $ Arnold Schwarzenegger, and $P\_D = $ me, it can't be simultaneously true that $D(P\_M)-D(P\_D)=1$, $D(P\_M)-D(P\_A)=1$, and $D(P\_A)-D(P\_D)=1$, yet that is what your assumption implies.
* Strategies usually aren't totally ordered. Sometimes we have situations where one strategy is especially effective against another strategy (more than you'd expect based on their overall strength). For instance, we can have situations where Alice usually beats Bob, Bob usually beats Charles, and Charles usually beats Alice. Your framework doesn't take this into account.

You'll probably need more sophisticated methods to deal with these challenges. For instance, one possibility is to build a small collection of different *baseline strategies* $Q\_1,Q\_2,\dots,Q\_k$. Then, evaluate $P$ according to how well it does against all of these: e.g., have $P$ play $n/k$ games against each $Q\_i$, count the total number of wins for $P$, and divide by $n$.

This leaves open the question of how you select the baseline strategies $Q\_1,\dots,Q\_k$. You might want each $Q\_i$ to be as strong as possible, but also want to have some diversity in the pool, so $Q\_i,Q\_j$ are as different as possible for all $i,j$. That requires a way to measure how similar two strategies $Q\_i,Q\_j$ are. One way might be to play a game between $P$ vs $Q\_i$; at each board position reached, compare how often $Q\_i$ would select the same move as $Q\_j$. To select a collection of baseline strategies, you could try to solve an optimization problem where you select among the s policies you've explored so far, while maximizing some objective function that rewards selecting strong strategies but penalizes similarity between selected strategies.

There are probably many challenges here, but hopefully this gives you some ideas you can try out.
> 1 votes

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


# Question
Title: Unique triangulation duals of simple polygons
Given a triangulation (without Steiner points) of a simple polygon $P$, one can consider the dual of this triangulation, which is defined as follows. We create a vertex for every triangle in our triangulation, and we connect two vertices if the corresponding triangles share an edge. The dual graph is known to be a tree with maximum degree three.

For my application, I am interested in the following. Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$. Here, the triangulation of $P$ may not be unique, but I require that the dual graph be unique.

This is certainly true when $T$ is a path, but becomes unclear when you have vertices of degree three.

# Answer
> Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$?

Yes. To show this, I will give a procedure to get the seemingly slightly stronger result\*:

> Given a tree $T$ with maximum degree three, construct a simple polygon $P$, such that the *unique triangulation* of $P$ (without Steiner points) has $T$ as its dual.

Start by creating an initial triangle $\Delta\_0$, representing some vertex $v\_0$ in $T$ and add $v\_0$ to the queue $Q$. Then, repeat the following until $Q$ is empty:

* Pop the top element, $v$, from the queue.
* For each neighboring vertex $w$ that for which we have not placed a triangle yet, choose a side $AB$ of triangle $\Delta\_v$ and a point $D$ inside the conical regions generated by the line through $AB$ and its neighboring segments, such that the triangle $\Delta ABD$ does not intersect any other triangles. (See figure below) Set $\Delta\_w\leftarrow\Delta ABD$ and add $w$ to $Q$.

This image gives an example of a possible polygon $P$ (left) for the given $T$ (right)

To see why this procedure works, first note that after creating a new triangle, the segments $AB$ and $AD$ generate a cone that has a non-empty region not-intersecting with the existing triangles (see also the earlier figure), so we can find a suitable point at every step and create a polygon.

Second, we have chosen the triangles such that line segment between $CD$ does not completely lie inside $P$. If there exists a corner-point $Q \notin \\{B,D\\}$ of the already placed triangles such that $DQ$ is fully in $P$, then it must lie inside the cones generated by $AD$ and $BD$. However, since the part of this cone that does not lie inside $\Delta ABD$ is contained in the cone generated by the earlier placed triangle, such a $Q$ exists only if there exists an analogous point for the earlier placed triangle. Since there does not exist such a point for the first triangle, this means there is no such point for any triangle we add.

This means that all pairs $(X,Y)$ of any corner point of $P$ for which the segment $XY$ is fully contained in $P$ is already in the constructed triangulation, so the triangulation is unique for $P$ (all triangulations add the same number of internal segments)

Note that the polygons constructed in this method tend to have rather sharp angles. I suspect arbitrary large graphs require polygons with arbitrary small angles, which could be a problem when drawing these polygons with finite precision.

<sub>\*: The difference is that, if we interpret 'unique' as up to isomorphism (which is consistent with uniqueness of triangulations and duals being different), we would be ok with a polygon having multiple triangulations that all have isomorphic duals. However, it is possible to 'attach' more triangles to those polygons to ensure some duals are no longer isomorphic.</sub>
> 2 votes

---
Tags: reference-request, computational-geometry
---


# Question
Title: Selecting a random 'bad' element from an array of $n$ values in $O(n)$ time and $O(1)$ space without knowing how many bad elements or where they are
I have an array of elements $A = \[x\_0, x\_1, \ldots, x\_n\]$, such that for some $0 \leq k \leq \frac{n}{2}$, there are $k$ 'bad' elements in $A$, but I don't know what indices they are at, or indeed, how many there are aside from the given bounds. I have a function which can, in $O(1)$ time, check if something is 'bad' or 'good'. As $A$ is an array, I have the ability to access any element of $A$ in $O(1)$ time if I know the index.

My goal is to devise a procedure which, in $O(n)$ time and $O(1)$ space, returns the index of a randomly-selected 'bad' element in $A$, or $-1$ if no such element exists. Any 'bad' element should have an equal chance of being selected. My current approach was something like this, assuming `coin` is a procedure that returns `0` or `1` with equal probability:

```
function randombad(A):
    result := -1
    for (i from 0 to (length(A) -1))
        if (A[i] is bad and result = -1)
            result := i
        else if (A[i] is bad)
            flip = coin()
            if (coin = 1)
                result := i
    return result

```

However, if $k \> 2$, this obviously gives later 'bad' elements a higher chance of being chosen, which is not what I want. Is there a way to do what I want without having to store every 'bad' element as I find them (which violates the $O(1)$ space constraint)?

# Answer
You can do better than $O(n)$ time: indeed $O(n/k)$ time and $O(1)$ space is achievable, with a perfectly uniform distribution on bad elements. Let me explain how, by starting with a simple strategy and building up to a solution that meets all of your requirements.

If we didn't have to deal with the possibility that no bad element exists, then a simple (but sub-optimal) method is to apply rejection sampling: repeatedly pick a random element, test if it is bad, and if it is bad, return it. In other words, you return the first bad element found.

If there is at least one bad element, this method is within a constant factor of optimal; the average running time is $O(n/k)$, and it uses only $O(1)$ space.

The big flaw with this simple approach is that if there are no bad elements, this algorithm runs forever. Fortunately, we can repair that with a simple fix, and at the same time improve running time to optimal.

Here's how. Pick a random permutation $\pi$ on $\\{1,\dots,n\\}$. Then, sequentially test $A\[\pi(1)\]$, $A\[\pi(2)\]$, ..., and return the first bad element you find. If you have tested all $n$ array elements and found no bad element, terminate and return -1.

This algorithm requires (on average) $\min(n/k,n)$ queries to the oracle, which is optimal -- you can't do better than that. The space requirement, apart from the time to store $\pi$, is $O(1)$. This also provides a perfectly uniform distribution on the set of bad points: because it is essentially a rejection sampling strategy, it is correct for the same reason that rejection sampling is.

At this point you might object that storing the permutation $\pi$ explicitly requires $O(n)$ space. You would be correct, but fortunately there is a fix to that: you can construct a pseudorandom permutation on $\\{1,\dots,n\\}$ with $O(1)$ space to store it, and $O(1)$ time to evaluate the permutation. See Lazily computing a random permutation of the positive integers and https://crypto.stackexchange.com/q/20035/351 and links there. Technically speaking, the space and time to evaluate the oracle is probably more like $O(\log n)$ than $O(1)$, but given that $n\le 2^{64}$ in practice, the difference might or might not be critical.

Caveat: This is an engineering-oriented answer. From a theoretical perspective, it's probably not fully satisfying. The use of a pseudorandom permutation means that the distribution on bad instances is not perfectly uniformly random; it is close to random (indistinguishable from random). Also, I haven't been fully-rigorous about the running time or space requirements for the pseudorandom permutation. Finally, the use of pseudorandom permutations relies on unproven assumptions (that certain crypto primitives are security). See the comments for more discussion of caveats.
> 3 votes

---
Tags: algorithms, arrays, randomized-algorithms
---


title: RSA Encryption Explanation

text:
# Question
Title: RSA Encryption Explanation
In Khan Academy's RSA Encryption 2 video, I can't understand how they have got from

$$m^e\bmod N\equiv c$$ to $$c^d\bmod N\equiv m\\,.$$

The transcript says,

> 01:39 some piece of information that makes it
> 01:41 easy to reverse the encryption
> 01:44 we need to raise $c$ to some other exponent, say $d$,
> 01:48 which will undo the original operation applied to $m$
> 01:51 and return the original message $m$.
> 01:54 So both operations together, is the same as
> 01:57 $m^e$ all raised to the power of $d$,
> 02:01 which is the same as $m^{e\times d}$.

The person says if we want to reverse the function to give us $m$ (the encrypted message), we simply have to raise $d$ to another exponent, $d$, and this reverses it.

Although I know this video isn't supposed to fully explain everything I don't understand how this is done. How can you just raise $c$ to some power and get the original message $m$. Is there some sort of proof or can someone explain it in more detail perhaps? By the way, I pretty much know nothing about encryption/ cryptography. I study CS at college (UK) AND was just watching due to curiousity.

# Answer
> 1 votes
What you have (after generating the keys):

$$ \gcd(p, q) = 1 $$ $$ N = pq $$ and a number $e$ and it's inverse $d$, modulo $\phi(N)$. That is: $$ ed \equiv 1 \pmod{\phi(N)}$$

---

Encryption: $$ c \equiv m^e \pmod{N}$$ Decryption: $$ m^\prime \equiv c^d \pmod{N} $$ $$ m^\prime \equiv (m^e)^d \equiv m^{ed} \pmod{N} $$

We don't yet if $m^\prime \equiv m$.

Well... you can use Euler's Theorem: $$ a^{\phi(N)} \equiv 1 \pmod{N}, \text{ if } \gcd(a,N) = 1. $$

Write $ed = 1 + k~\phi(N)$: $$ m^\prime \equiv m^{1+k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot m^{k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot \underbrace{m^{k\phi(N)}}\_{1} \pmod{N}$$

So $m^\prime \equiv m \pmod{N}$.

---
Tags: cryptography, encryption
---


# Question
Title: Understanding implemetation of the Toffoli gate using other gates
I have a system with three qubits as input and I want to demonstrate this equality:

where the left part of the equal is the circuit representation of the Toffoli gate where the first two lines are the control qubits and the third one is the target. On the right side we have the CNOT gate whose matrix representation is

$$ CNOT=\left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{array}\right)$$

T,S and H are the $\dfrac{\pi}{8}$ gate,phase gate and Hadamard gate, respectively, represented by the matrixes

$$H=\dfrac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1\\ 1 & -1 \end{array}\right), S=\left(\begin{array}{cc} 1 & 0\\ 0 & i \end{array}\right), T=\left(\begin{array}{cc} 1 & 0\\ 0 & exp(i\pi/4) \end{array}\right)$$

The Toffoli gate is supposed to do this

My problem is that I don't know how, given some input, for example, the three qubits in the state |1\>, the circuit acts on the input. For example, in the second control qubit there is a CNOT gate, so what I have to do is calculate the direct sum of |1\> and the qubit which is below it once it has passed through the H gate? This is, before the target qubit reach $T^{\dagger}$, we have the state $|1\>|1\oplus H|1\>\>=-\dfrac{1}{\sqrt{2}}|1\>(|0\>-|1\>)$

Is this correct?

# Answer
When applying quantum operations you always:

* Simplify everything down to individual self-contained cases.
* Apply the operation separately to each case.
* Recombine the answers.

So, in the case of applying a CNOT to the state $|1\rangle \otimes (H \cdot |1\rangle)$, you:

* Simplify things. We don't want that $H$ in the way. Apply it. The state is $|1\rangle \otimes (\frac{1}{\sqrt 2}|0\rangle - \frac{1}{\sqrt 2}|1\rangle)$.
* Separate things. Distribute the tensor product over the subtraction. The state is $\frac{1}{\sqrt 2}|1\rangle \otimes |0\rangle - \frac{1}{\sqrt 2}|1\rangle \otimes |1\rangle$. Or, for short, just $\frac{1}{\sqrt 2}|10\rangle - \frac{1}{\sqrt 2}|11\rangle$.
* Apply the operation separately to each case. If the second bit is our control, then in $|10\rangle$ the control isn't satisfied and nothing happens while in $|11\rangle$ the control is satisfied and we toggled to $|01\rangle$. Apply that to each part of $\frac{1}{\sqrt 2}|10\rangle - \frac{1}{\sqrt 2}|11\rangle$ and you end up with $\frac{1}{\sqrt 2}|10\rangle - \frac{1}{\sqrt 2}|01\rangle$.
* None of our output cases overlapped when being added together, so there's no need to combine anything.

You might get a sense of this by adding state displays to Quirk while it cycles through the inputs into your Toffoli circuit.
> 4 votes

---
Tags: quantum-computing
---


# Question
Title: Which one should I report as total network I/O bytes among Sum(InBound) or Sum(InBound + OutBound)?
I have a set of experiments with distributed environments.

I am planning to present a total network I/O bytes usage of the system for each run.

Which one should I report as total network I/O bytes among Sum(InBound Traffic) or Sum(InBound Traffic + OutBound Traffic)?

For example, say there are two machines A and B in my cluster server.

A sends 10 bytes to B.

B sends 15 bytes to A.

What is the total network I/O bytes? Is it 25 or 50 bytes?

# Answer
> 2 votes
I would suggest reporting the sum of both.

As a general principle, the best solution is to *define your metrics* in the report or paper where you write up your results. You should describe *what you measured* and *how you measured it*. This includes clarifying whether "total network I/O" includes both inbound+outbound traffic or only inbound traffic.

---
Tags: computer-networks, experimental-analysis
---


# Question
Title: Recurrence relation of the coin change problem
I'm trying to wrap my head around the coin change problem, where you try to find the total number of ways $N$ cents can be exchanged using $M$ coins $\\{C\_1, C\_2, ..., C\_m\\}$.

The recurrence relation is this:

I'm having difficulty understanding the 3rd line where it says `solution[i][j-v[i-1]]`. What exactly is this `v` they are talking about? I understand it's just the array index above the current one being worked on, but I still don't get what this `v` is. Can anybody explain please?

# Answer
> 8 votes
For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\\{C\_1, C\_2, ..., C\_m\\}$.

Whenever confronted with a new dynamic programming problem, you should always try to understand how optimal solutions are structured in terms of optimal solutions for smaller subproblems (cf. optimal substructure). This will help you come up with the recurrence relation. Note that, in dynamic programming, you take the solution for one or more subproblems (initially, the base cases) and extend them, repeating this extension iteratively until, eventually, you reach the solution for the original problem.

In the coin change problem (using your notation) a subproblem is of the form `solution[i][j]`, which means: you can make change for $j$ cents using the first $i$ coins from $V$. How have we arrived at this optimal solution (i.e., how have we extended a previously solved subproblem)? We may have brought one more coin from $V$ into the picture. How does this new coin extend the previous solution? Well, there are two possibilities: we have used this coin to make change or we haven't. We must add up these two cases (since both of them represent valid ways to make change):

* **Case 1 (the coin is not taken)**: when coin $i$ is not taken, the number of ways to make change for $j$ is exactly the same as it was before coin $i$ was even considered; that is, `solution[i-1][j]`.
* **Case 2 (the coin is taken)**: when coin $i$ is taken, your are *spending* its value; therefore, you must substract the value $C\_i$ to $j$. Now, the number of ways to make change is `solution[i][j-v[i]]` *.

The final recurrence is obtained by adding up these two cases:

`solution[i][j] = solution[i-1][j] + solution[i][j-v[i]]`

Observe that case 2 is not applicable when $j$ is smaller than the value of the $i$th coin (that is, when $j \< C\_i$), hence the distinction in the third and fourth lines of your recurrence.

---

**Footnote:**

* It will be `v[i-1]` if the array starts at index 0.

---
Tags: recurrence-relation, dynamic-programming, coin-change
---


# Question
Title: Is there a formalization of a general version of the sweep line algorithm? If not is it easy to derive?
A well known algorithm in computational geometry is the sweep plane algorithm. I've been trying to find if there's a general version of the sweep plane algorithm in $\mathbb{R}^n$, I don't need to implement it but I need to study how the general version would work.

If there's nothing you known in literature, how difficult is trying to formalize it?

I believe it could be formalized recursively (like sweeping hyper planes from dimension $n-1$ downto $2$. But I need to be sure.

Update:

I've been asked to elaborate a bit more...

In the best reference I know, the plane sweep is basically explained as "Imagine this plane that moves through event points, where something happens". The specific instance are almost 2D and 3D cases (involving problem like segments intersection, triangulation and voronoi diagrams), nothing is mentioned how the paradigm works in general.

# Answer
Perhaps this is too broad a question for a coherent answer, so let me first try to say something about line segment intersection, at least. The main reason the sweep-line algorithm is efficient is that we only have to worry about neighboring line segments. We can generalize this procedure to $\mathbb{R}^n$ by noting that if we sweep a line over a sub-plane of $\mathbb{R}^n$ (i.e. the projections of all segments from $\mathbb{R}^n$ on this plane), any intersecting segments in $\mathbb{R}^n$ cannot be 'separated' on this line by a segment that intersects neither of them (If such a segment exists, the segments would be separated by the $n-1$-dimensional hyper-plane orthogonal to the projected plane). So, we can in fact apply the $2D$ algorithm on some plane projection, with the only difference being that we test individual intersections in $\mathbb{R}^n$. (some non-general position edge-cases might get even nastier, but I think the general procedure still applies)

Now, for the sweep line paradigm in general:

I think the main algorithmic idea is that if we want to answer questions about objects in $\mathbb{R}^n$ that concern only their 'neighbor' objects (line segment intersection is the most clear, but Voronoi diagrams and even triangulation fit this description to a certain extent), it is efficient to only query for 'local' objects. To achieve this, sorting seems like a good idea. However, there is no clear method to sort points in $\mathbb{R}^n$ in an useful way, for $n\>1$ (I will explain why later\*), while sorting in $\mathbb R$ can be efficiently maintained, using binary search trees.

So, the sweep line algorithm attempts to solve this problem by sorting on the order in one direction, on the sweep line. The main thing that the algorithm has to do is to 'make up' for this simplification by traversing the space in a structured matter. Therefore, it makes little sense to use an $n-1$-dimensional hyper-plane to sweep the space with, as we cannot sort the projections on this plane.

Another idea is that the sweep line paradigm allows the algorithm to 'ignore' already visited points. While this is intuitive, I don't think that this idea is the key to efficiency. This idea leads to replacing $n^2$ by $\sum\_{i=0}^n i$, so it gives no asymptotic improvements.

So, I think that we have an answer to your statement:

> I believe it could be formalized recursively (like sweeping hyper planes from dimension $n−1$ downto $2$. But I need to be sure.

The sweep **line** paradigm uses a **line**\**, even in $\mathbb{R}^n$.

\*: Why can't we just use a lexicographical sort on a 2D-plane and call it a day? Recall why we sort: we want to find 'neighbors' of the objects since we don't need to compare non-neigbors. In $\mathbb{R}^n$, point $p$ being a neighbor of some point $q$ usually means that the (Euclidean) distance between them (in some direction) is minimal, i.e. there is no closer point $r$ 'in between them'. So, our order must be 'distance preserving'. This property is not satisfied by a lexicographical sort.

For example, draw a 4x4 grid of dots, choose to sort by row major or column major order, give them a number to indicate their rank and observe that some neighboring dots differ by 5, more than all other points in the same row/column! We can show that there is no (total) ordering on $\mathbb{R}^n$ that preserves 'neighbors' of points.

However, we must first make this more precise. Observe that an ordering of $\mathbb{R}^n$ is actually a function to some subset of $\mathbb{R}$! (You can also consider it a space-filling curve, the idea is similar) That is, given a total ordering on $\mathbb{R}^n$, there is a function $F : \mathbb{R}^n \rightarrow \mathbb R$ that completely characterizes it (I could make this more precise, but I feel that that's for another question). For a function $F$ (or *functional*, in this case) to be 'distance preserving', it means that there exists some $c\in \mathbb R$ such that $\\|Fx\\| = c\\|x\\|$ for all $x\in \mathbb{R}^n$. If $F$ is non-linear, it is not distance preserving (again, showing this is out of scope).

If $F$ is linear, our condition implies that it is an (linear scaling of an) orthogonal linear map (by definition, depending on your point of view), which means in particular that $F$ is of full rank. This means that $F$ cannot map from a subspace (the plane) to one of strictly lower dimension (a subset of $\mathbb R$). Therefore, there exists no distance preserving $F : \mathbb{R}^n \rightarrow \mathbb R$ and therefore no 'distance preserving' ordering of $\mathbb{R}^n$ for $n\>1$ exists. Finally, this means (here I'm making an 'informal leap') that there is no 'neighbor preserving' ordering on planes and hyper-planes.

\**The key part of the sweep line paradigm is the projection to a one-dimensional space to be able to use sorting, such as a line. This space does not have to be linear, however. Therefore, we can in some cases (line segment intersection is **not** such a case) do something similar with not a line, but with a curve (In the setting when our objects are lines, this curve needs to always intersect each line exactly once, so we cannot use a space-filling curve). This is called a *topological plane sweep*. See the lecture notes by David M. Mount for more information.
> 3 votes

---
Tags: algorithms, computational-geometry, algorithm-design
---


title: Lambda calculus application

text:
# Question
Title: Lambda calculus application
I have a function application:

```
E1 E2

```

Can someone please show me an example, how to execute function?

# Answer
If you have at least one abstraction just go on $\beta$-reducing. It just works like taking an input $x$ and computing $f(x)$.

$$ (\lambda x. x + 1)1$$ is an application.

$$ \[1/x\](x + 1)$$ $$ (1+1) \rightarrow\_\beta 2$$
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: Difference between beta reduction and substitution
I can not see the difference between beta reduction and substitution.

For example:

```
(+ x 1) [x -> 2]

```

Here I can do the substitution, replace the variable x through 2(lambda expression) and result is:

```
(+ 2 1)

```

An example of beta reduction:

```
(λ x. + x 1) 2

```

the result would be

```
+ 2 1

```

For me, there are no difference between them, but there is a rule, I can not substitute the lambda expression, when the metavariable is bound

```
(λ x. + x 1) [x -> 2] No possible to substitute it.

```

Only free variables can be substitute it.

What is the difference between the diction:

```
(λ x. + x 1) 2

```

and

```
(λ x. + x 1) [x -> 2]

```

# Answer
> 6 votes
The $\beta$ reduction is defined by using capture-avoidng substitution. That is,

$$ (\lambda x. M)N \longrightarrow\_\beta M\[x \mapsto N\] $$

So it's the definition. Under the $\beta$-equivalence, $(\lambda x. M)N \equiv\_\beta M\[x \mapsto N\]$, but syntactically, $(\lambda x. M)N \neq M\[x \mapsto N\]$.

Note that substitution is a meta-operation on $\lambda$-calculus terms (normally). A $\lambda$-calculus term $M$ is whether a variable $x$, a lambda abstraction $(\lambda x. M')$, or an application $M\_1 M\_2$. That's it. There is no substitution. Substitution is a map on $\lambda$-calculus terms. Therefore, for example, a term $({+}~x~y)\[x \mapsto z\]$ is **syntactically** equal to $({+}~z~y)$. There is no reduction. In contrast to this, $(\lambda x. {+}~x~y)~z$ is **not** syntactically equal to $({+}~z~y)$, although it can be reduced to $({+}~x~y)$.

---

Also, $(\lambda x. {+}~x~1)~2$ is different from $(\lambda x. {+}~x~1)\[x \mapsto 2\]$. The latter is equal to $(\lambda x. {+}~x~1)$.

---
Tags: lambda-calculus
---


# Question
Title: What other involutions are there besides xor?
There is a classic problem of finding the only number that occurs an odd number of times in a list. The solution is to xor everything and the result is the requested number.

The key properties used here are the involution of xor (i.e. a number's inverse is the same number) and the closure over integer range of the variable.

Now, are there any other operations that could be used for this? I could only find 1/x which, unfortunately, cannot be used due to precision erros.

# Answer
Roll your own.

Take an arbitrary bijection $f$ from the integers to integers. This is a permutation of the integers.

Then, take the conjugate of XOR ($\oplus$): $$ g(x,y) = f^{-1}(f(x) \oplus f(y)) $$ We then have $$ g(x,x) = f^{-1}(0) $$ which now acts as the "new zero" (neutral element) $$ g(x,f^{-1}(0)) = x $$ We also have that $g$ is associative and commutative $$ g(x,y) = g(y,z) \qquad g(g(x,y),z) = g(x,g(y,z)) $$ So, we still have an abelian group where $x^{-1}=x$. The trick on arrays mentioned by the OP still works.
> 7 votes

---
Tags: searching
---


# Question
Title: Counterexample to big-O claim looks wrong
> Let $T\_1(n) = O(f(n))$ and $T\_2(n) = O(f(n))$.
>
> Then $T\_1(n) / T\_2(n) = O(1)$ is a false statement. A counterexample is $T\_1(n) = n^2$, $T\_2(n) = n$, and $f(n) = n^2$.

I don't get this counterexample, if $T\_2(n) = n$, then $T\_2$ is $O(n)$ and not $O(n^2)$. (As indicated by $T\_2 = O(f(n))$ and $f(n) = n^2)$. Therefore, this doesn't look like a valid counterexample to me. Am I wrong?

# Answer
> 10 votes
The counterexample is fine. Any function that is $O(n)$ is also $O(n^2)$ – if a function's "smaller than" $n$, it's also "smaller than" $n^2$.

And note that even weaker statements are false. In fact, there is no function $g$ such that $T\_1,T\_2=O(f)$ implies that $T\_1(n)/T\_2(n)=O(g(n))$. For example, take $T\_1(n)=1$ and $T\_2(n)=1/g(n)^2$. So, now, $T\_1(n)/T\_2(n) = g(n)^2\neq O(g(n))$.

# Answer
> 1 votes
It's a trick question. There is a difference between O (f(n)) and $\Theta (f(n))$. The first one means "not greater than some constant times f (n)". The second means "not greater than some constant times f (n), but also not less than some other constant \> 0 times f (n)".

People often write O (f(n)) when they mean $\Theta (f(n))$. For example, if I say I can sort an array in O (n log n), that's fine. If I say that Heapsort takes $O (n^3)$, that's not untrue, but it will mislead many people. So if I say that $T\_2 (n) = n$ is $O (n^2)$ that is misleading you, but it is indeed true.

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


# Question
Title: Finding a class of graphs for which vertex coloring is NP-hard
We know that for general graphs vertex coloring problem/ minimum clique cover problem are NP-hard and for perfect graphs, they can be solved in polynomial time. There are classes of graphs which are perfect, e.g., bipartite graphs, chordal graphs, linear graphs, etc.

My question is that:

Are there any families of graphs that we know for them vertex coloring problem/ minimum clique cover problem are **NP-hard**? I appreciate if someone can give the name of some of them or any reference for them (in case they exist).

I have a problem and I want to show that it is hard and I want to find such a family of graphs and use them as an instance for my problem.

# Answer
> 1 votes
This PDF defines a graph for which solving a 3-SAT formula is equivalent to determining if the graph is 3-colorable. Finding the vertex coloring of these graphs would solve the 3-SAT problem, so the vertex coloring problem on these graphs is at least as hard as an NP-complete problem. Therefore, solving the vertex coloring problem on these graphs is NP-hard.

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


# Question
Title: Write through and write back cache policies
* There are Two Write Hit policies: Write Through and Write back
* There are Two Write miss policies: Write Allocate and No Write Allocate
* There are two memory access techniques: simultaneous and hierarchical access

Can any gentleman **PLEASE** write formulas for different combinations ?

I am having very important competitive exam that can change my life, and i am struggling with these methods badly.

---

For instance one may consider following example and please show me relevant modification of this example.
**Question** : In a certain system the main memory access time is 100 ns. The cache is 10 time faster than the main memory and uses the write though protocol. If the hit ratio for read request is 0.92 and 85% of the memory requests generated by the CPU are for read, the remaining being for write; then the average time consideration both read and write requests is

a) 14.62ns

b) 348.47ns

c) 29.62ns

d) 296.2ns

PS:- I know meaning or working of all techniques but don't know how can i drive formulas. Please do it, i really need that badly. It would be GREAT help.

Thnks in advance.

# Answer
When you want a general formula for a particular case, just derive it.

Let the main memory access time be $x$, and the cache access time be $y$. Let the hit ratio be $h$ and the fraction of requests that are reads be $p$.

Now, $$\begin{align}\text{Average access time}&=\text{Weighted average of read and write times}\\\&=\text{Fraction of reads}\times\text{Average read time}+\text{Fraction of writes}\times\text{Average write time}\tag1\end{align}$$

Let us now go through the read process. Firstly, there are two possibilites - a cache hit or a miss. If it is a hit, the cache access time is the total read time. If it is a miss, then the total read time is the sum of the time taken to access the cache and the time taken to access the memory. The fraction of hits is given by the hit ratio. Again, we take the weighted average.

$$\begin{align}\text{Average read time}&=\text{Fraction of hits}\times\text{Cache access time}+\text{Fraction of misses}\times(\text{Cache access time}+\text{Memory access time})\\ &=hy+(1-h)(x+y)\tag2\end{align}$$

Now, the writes. It is given that the write policy is the write through policy. This means that when a write is made, irrespective of a hit or a miss, memory is accessed as well. As the memory access time dominates over the cache access time, and the hit ratio for writes is not given, ignore the difference in the times of accessing just the memory and accessing the cache and the memory.

$$\begin{align}\text{Average write time}&=\text{Main memory access time}=x\tag3\end{align}$$

Combining $(1),(2),(3)$, we get, $$\begin{align}\text{Average access time}&=p\left\[hy+(1-h)(x+y)\right\]+(1-p)x\end{align}$$

Here, $p=0.85,h=0.92,x=100\text{ns},y=10\text{ns}$. Substituting, $$\begin{align}\text{Average access time}&=0.85\left\[0.92\times10+(1-0.92)(100)\right\]+(1-0.85)\times100\\ &=0.85\times17.2+15\\ &=29.62\text{ns}\end{align}$$

Similarly, you can attempt the other cases mentioned in your question.
> 1 votes

---
Tags: computer-architecture, memory-management, cpu-cache
---


title: Savitch's theorem and time relation

text:
# Question
Title: Savitch's theorem and time relation
We know that $NTIME(t(n)) \subseteq DSPACE(t(n))$ and we know - by Savitch's theorem - that $NSPACE(s(n)) \subseteq DSPACE(s^2(n))$.

By the space/time relation $(s(n) \leq t(n))$ I know that $NTIME(t(n)) \subseteq NSPACE(t(n))$, then by Savitch's theorem $NSPACE(t(n)) \subseteq DSPACE(t^2(n))$ and not $DSPACE(t(n))$, as stated above.

Where am I wrong?

# Answer
I believe you left out big-Os around those bounds.
In any case, $\\; \\{0\\} \subseteq \\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\\} \\;$ *and* $\\; \\{0\\} \subseteq \\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\\}$ , $\\;$ even though $\\: \\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\\} \neq \\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\\}$ .
> 0 votes

---
Tags: time-complexity
---


title: Beginner help with Arrays & Complexity

text:
# Question
Title: Beginner help with Arrays & Complexity
My goal is to create a method that gets an array that only has 1's and 0's in it, and then turns every number into the amount of 'steps' it is away from the closest 0, left or right.

So for example \[1\] - \[1\] - \[0\] - \[1\] - \[1\] - \[1\] - \[1\] - \[1\] - \[0\] - \[1\] would be \[2\] - \[1\] - \[0\] - \[1\] - \[2\] - \[3\] - \[2\] - \[1\] - \[0\] - \[1\]

I also need to do it as simple as possible in terms of time and space complexity.

I'm not sure how to make it count how far a certain spot is from a 0 if it's from the right of the 0, or if there's another 0 nearby I'm not sure how to make it count which one is closest.

I'm assuming two for loops are needed?

Made a sketch: no idea if it makes sense.

```
 for (int i=0; i<a.length; i++)
{

    for (int j=i; j<a.length; j++)
    {
     if (a[j]==0)
      {
       if (i<j)
         {
           a[i]=j-i;
         }
        if(j<i)
         {
           a[i]=i-j;
         }
       }
    }
 }

```

# Answer
Let's try to solve a simpler problem first:

**Given an array that only has 1's and 0's in it, the method turns every number into the amount of 'steps' it is away from the closest 0 to the left.**

Now this problem is easy. A simple solution is: traverse the array from left to right, keeping track of the distance from the last zero encountered and updating each element with the distance.

A simple code:

```
dist = INF
for(i=0;i<a.length;i++){
    if(a[i] == 0)
       dist = 0;
    else
       dist++;
    b[i] = dist;
}

```

Now once you have solved the simpler problem for closest 0 to the left, you can similarly solve the problem for closest 0 to the right. With these two solutions, you should be able to easily get a solution for the original problem (by taking a min of the two solutions).

The solution evidently has O(n) time complexity, and can be easily coded to use only O(1) space by carefully manipulating the updates in the original array only.
> 3 votes

# Answer
Just some hints that will tell you how to solve it efficiently:

If you know where the first zero is, then you know what numbers to write down at all positions before and up to that zero. For example, if a \[4\] is the first zero, then you know the numbers for positions 0, 1, 2, 3 and 4 (4, 3, 2, 1, 0). You don't know the number for position 5 at this point.

If you know where two consecutive zeroes are, then you know what numbers to write down at all positions from the first to the second of these two zeroes. For example, if there is a zero at a \[4\] and the next zero is at a \[9\] then you know all the numbers for positions 4 to 9 (0, 1, 2, 2, 1, 0).

And if you know the position of the last zero, then you know what numbers to write down at all positions from that zero to the end of the array.
> 2 votes

# Answer
Just iterate in each direction and track the distance from the last zero

You could get fancier with some back tracking to only go one direction but would not be much faster

2n is still O(n)

lastZero is the distance from the last zero

```
int[] result  //this store the answer / calculation
int lastZero = null
for(i = 0; i < len; i++)
{
    if(input[i] = 0)
    {
        lastZero = 0
        result[i] = 0
    }
    else if (lastZero != null)
    {
        lastZero++
        result[i] = lastZero
    }
}
//now go from right to left
lastZero = null
for(i = len - 1; i <= 0; i--)
{
    if(input[i] = 0)
    {
        lastZero = 0
    }
    else if (lastZero != null)
    {
        lastZero++
        if(result[i] > lastZero or result[i] = null)
           result[i] = lastZero
    }
}

```
> -2 votes

---
Tags: algorithms, arrays, algorithm-design
---


# Question
Title: What is the state of the art for k nearest neighbour search?
I'm not an computer scientist, but still use/have an algorithm to find the $k$ nearest neighbours from a cloud of $N$ points in $d$ (my case $d=3$) dimensional space using some distance measure (in my case Euclidean). I had some look at the literature and it appears that the standard is J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3:209–226, 1977, which is a root-first tree traversal on a kd tree. This algorithm has complexity $O(dk\log N)$ for each search (after the tree has been built at cost $O(dN\log N)$). I wonder whether this is still the state of the art.

The reason I'm asking is that my own algorithm is different (also using a tree) and has (I believe) average costs of $O(dk)$ per search (but still worst case $O(dk\log N)$), provided the query point is a member of the cloud. So I was wondering whether it's perhaps worth publishing.

# Answer
> 3 votes
It seems hard to imagine that your claimed running time is correct, for a method that works in an arbitrary number of dimensions. It sounds like you are claiming that your data structures works in an arbitrary number of dimensions ($n$), but the running time does not depend on the dimension ($n$). That seems unlikely; nearest neighbor search is known to be hard to solve in high dimensions (the so-called curse of dimensionality).

Alternatively, if you meant that your scheme works only in 3 dimensions, then that is an important caveat that needs to be mentioned. Being able to find the nearest neighbor in 3D in $O(1)$ time would be an impressive result; I'm not aware of any data structure that is known to have this worst-case running time.

Yes, a k-d tree is a standard data structure for this task, when you are working in 3 dimensions. There are also generalizations and related data structures; see metric trees, binary space partitioning trees and octrees. R-trees and R\*-trees can be used if the set of points are changing.

Without knowing how your algorithms works, it's hard to give a definitive answer whether it is worth publishing. To figure out, a good starting point would be to familiarize yourself with the published and known algorithms and see if your idea still seems to be better than all known schemes. If you're still not sure, make ask a new question here with the specifics of your algorithm and what your specific uncertainty is.

---
Tags: algorithms, reference-request, search-algorithms, nearest-neighbour
---


# Question
Title: Can every two languages in $RE$ be reduced?
If $L\_1,\\, L\_2 \in RE / R$, must there exist a (computable) many-one reduction between them?

I can prove that for every two languages in $R$ exists a reduction between them. A possible reduction $L\_3 \leq L\_4$ where $L\_3,\\, L\_4\in R$ goes as follows:

given an input $x$ to $L\_3$, run $M\_3$ (it's TM), if it accepted, return an input that is in $L\_4$. Else, return one that isn't (this works assuming $L\_4\neq \emptyset,\\, \Sigma^\*$).

The above idea will not work in $RE$ because $M\_3$ might not halt.

Is there a different way to construct a reduction $L\_1\leq L\_2$ where it us known that $L\_1,\\, L\_2\in RE / R$? Or is such a general reduction something that cannot be always achieved?

# Answer
> 2 votes
Consider the case $L\_2 = \emptyset$. This language is clearly recursively enumerable, but the only language which can be reduced to it is itself.

What is true, and follows directly from the definition, that two RE-complete languages reduce to one another.

---
Tags: formal-languages, turing-machines, reductions, undecidability
---


# Question
Title: Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$
How can i remove from a red/black tree a subtree whose root and its sibling are red, and their parent is black, in $O(\lg n)$ time, while keeping the red/black properties at the end of the process?

In other words: I have a black/red tree with $n$ nodes, a given black node $y$, and his two red children $x$ and $z$. How can I delete the subtree of $x$ in $O(\lg n)$ time, while keeping the red/black tree properties at the end of the process?

This is an homework question.

# Answer
The solution is to delete the sub-tree $x$ ($O(\lg n)$), then replace sub-tree $z$ instead of sub-tree $y$ ($O(1)$), then turn $z$ to black ($O(1)$), and finally insert $y$ as usual ($O(\lg n)$).
> 1 votes

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


# Question
Title: Is there a DFA that accepts no string, but has at least one final state?
Is there a DFA that accepts no string, but has at least one final state?

I think it would be possible to make a DFA that accepts no string only by creating no final states or by making sure that the final states are not accessible. But how can a state not be accessible if a DFA has all of its transitions defined?

# Answer
> 2 votes
Consider a 2-state DFA over the alphabet $\\{a\\}$ (single character alphabet) that accepts only the empty string:

In this DFA, state `0` is the start state, and also the only accepting state. Now, if state `1` were the start state (but state `0` still the only accepting state), what strings would this machine accept?

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


# Question
Title: How can a Turing machine write the description of the n-th Turing machine?
I am trying to interpret the following problem:

"Describe an algorithm for a Turing machine which receives the integer n as input and proceeds to write the description of the n-th Turing machine from the standard enumeration on its tape."

I am confused about how a Turing machine itself can represent another Turing machine (the n-th Turing machine).

# Answer
The question is probably assuming that there is some arbitrary but agreed-upon convention that specifies how to write a Turing machine description with the symbols of some alphabet. Since all Turing machines have by definition a finite description, all valid outputs will be finite strings.

The exercise itself is an ordinary combinatorics problem.
> 2 votes

---
Tags: turing-machines, computation-models
---


# Question
Title: An algorithm for comparing a DFA and a regular expression
Assuming I have an encoding of a DFA $\<M\>$ and a regular expression $\<r\>$, I'm interested in finding an algorithm for comparing whether or not $L(M)=L(r)$.

I have thought about converting $r$ into an NFA, and then converting the NFA to a DFA, but the problem is that this process may result in a totally different DFA.

Another idea I had was to convert the DFA to a regular expression. But with this idea, I have two problems: first is that I'm not sure how exactly is ut done, and second - even if I will succeed in doing so, I might again end up with a totally different regular expression (that has the same language, but written differently).

Obviously, a third approach would be to start looping all over $\Sigma^\*$, but this is an infinet process...

Does someone have a different idea or a way to improve my approaches to this problem?

I would like my algorithm to be able to both return "true" if $L(M)=L(r)$ and false otherwise (my third approach can only return false, but will never return true).

# Answer
> 1 votes
This technique I am going to describe works to compare two NFAs. Fortunately, you have mentioned that you know how to convert your regular expression into an NFA and it is trivial to convert your DFA into an NFA. (just treat the DFA as though it were an NFA)

Once you have your two NFAs, add two new symbols to your alphabet: $\\$\_1$ and $\\$\_2$. We're going to construct a larger NFA by combining the two NFAs that we have. Add a node (call it $\omega$), and add edges from every accepting node in the first NFA to node $\omega$ labeled with $\\$\_1$. Now add edges from every accepting node in the second NFA to node $\omega$ labeled with $\\$\_2$.

Now add another node (call it $\alpha$) and add epsilon-transition edges from $\alpha$ to the initial node in each NFA. (so $\alpha$ has only two edges leaving it). (alternatively, since some people don't like epsilon transitions, you can instead add to $\alpha$ all the outgoing edges of the initial nodes in each original NFA)

Now take this combined graph with the two extra nodes as an NFA: the initial node is $\alpha$, and the only accepting node in the combined graph is $\omega$.

Turn this NFA into a DFA. One side-effect of how we constructed edges into $\omega$ is that the DFA will have only a single accepting state. The two original languages will be identical if and only if in the DFA every edge going to this accepting node is labeled with both $\\$\_1$ and $\\$\_2$.

Essentially, what we did was form the languages: \begin{align} L\_1 &= \\{ w \ \\$\_1 \ | \ w \in L(M)\\} \\ L\_2 &= \\{ v \ \\$\_2 \ | \ v \in L(r)\\} \end{align} and then our combined NFA was the NFA for the language $L\_1 \cup L\_2$. The statement about the edges of the DFA says that there exists some set $A$ such that the language of our DFA is $$\\{a \ x \ | \ a \in A, x \in \\{\\$\_1, \\$\_2\\} \\}$$ But this implies that if you stripped the $\\$\_i$ symbols off the end of the strings in $L\_1$ and $L\_2$ you'd have the same language.

---

Incidentally, you can use this DFA for $L\_1 \cup L\_2$ to easily construct DFAs for $L(M) \cap L(r)$, for $L(M) \cup L(r)$, for $L(M) \setminus L(r)$, for $L(r) \setminus L(M)$, and for the symmetric difference of $L(M)$ and $L(r)$. The exact details are left as an exercise for the reader, but it involves examining nodes with outgoing edges labeled with one of the $\\$\_i$ symbols, labeling some of those nodes as accepting nodes, and then erasing all edges labeled with the $\\$\_i$ symbols.

(These won't necessarily be *minimal* DFAs, even if you minimized the DFA before erasing the $\\$\_i$ edges. You'll need to apply standard DFA minimization algorithms if you want that.)

---
Tags: automata, finite-automata, regular-expressions, simulation
---


title: Emptiness problem

text:
# Question
Title: Emptiness problem
I have some questions regarding the emptiness problem of Turing machines when we have a TM which accepts empty language, and we have to make sure that the TM does not accept any string. My questions are:

* in formal description of TM I have read that input alphabet can't be empty then how a machine can accept empty input?
* if we have a machine which accepts empty string then "how is it undecidable?" When we can simply reject any non-empty string?

If I got some concepts wrong or messed it up, kindly correct me.

# Answer
> 4 votes
You are confused on several accounts. The *language* of a Turing machine $T$ consists of all inputs $x$ such that when $T$ runs on $x$, it terminates in an accepting state. (There are several other equivalent definitions.) In particular, the language of a Turing machine can be empty no matter what the alphabet is. All it has to do is never terminate in an accepting state.

You are confusing the empty alphabet (which doesn't exist - we always require the alphabet to be non-empty), the empty string (which is the unique string of length 0), and the empty language (which contains no strings). In particular, the language consisting of the empty string *isn't* empty, since it contains the empty string.

The emptiness problem asks to decide, given a Turing machine $T$, whether the language of $T$ is empty or not. All you are given is the Turing machine itself. You aren't given "hints" like in your example. You can prove that the emptiness problem is undecidable. Indeed, it is even undecidable whether a given Turing machine accepts the empty string (we don't care about any other input).

---
Tags: turing-machines, undecidability
---


# Question
Title: Is there a known algorithm for computing the n-th Turing machine directly?
Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M\_1$ can be represented by 9,900,599 (\[0 0 halt\], where halt = 5 and the start and end of an instruction is 99). A standard enumeration consists of all possible Turing machines.

If given a number $n$, is there a known algorithm out there for producing the $n$th Turing machine ($M\_n$) in the standard enumeration?

# Answer
> 2 votes
Generate all strings in order, and keep track of which of them correspond to valid encodings. One you have seen the $n$th one, output it.

There are probably more efficient algorithms, but it depends on your exact encoding. Standard combinatorial enumeration techniques might suffice.

---
Tags: algorithms, turing-machines, computation-models, enumeration
---