# Question
Title: Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square
Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)

Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.

Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.

# Answer
> 6 votes
In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$. Then we have $N + B^2 = A^2$. Thus $N = A^2 - B^2 = (A - B) \cdot (A + B)$.

What's left is to look at the pairs of divisors of $N$. If $N = X \cdot Y$, we have $A - B = X$ and $A + B = Y$. So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.

The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization. Looks like one is not easier or harder than the other. In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$. So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.

Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is. *(Link suggested by Apass.Jack)*

# Answer
> 3 votes
This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.

Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.

This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.

The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.

---
Tags: algorithms
---


# Question
Title: Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular?
I've been asked to write a DFA for:

$\\{xy\mid x, y \in \Sigma^\*\text{ and }x\text{ contains more }a\text{’s than }y\\}$ where $\Sigma=\\{a,b\\}$.

I don't believe this is possible. Can anyone confirm if this is not a regular language so that I'm not wasting my time if I'm correct.

# Edit

Thinking again, while it's impossible to track exactly how many $a$'s are in $x$ or $y$ respectively, we know $x$ must have the number of $a\>0$ at the very least and that the number of $a$'s in the string cannot be 2 since the condition of 'more' $a$'s has to be satisfied. Can you just write a DFA accepting strings with inputs containing 1 $a$, and 3+ $a$'s to satisfy the language?

# Answer
Since the language does not specify what $x$ and $y$ are, you can always let $y=\varepsilon$, i.e., the empty string, then the language only requires $x$ to contain at least 1 $a$. So equivalently, the language is

$\\{x\in\Sigma^\*\mid x\text{ contains at least 1 }a\\}$.

Now it is easy to build a DFA to accept this language.
> 2 votes

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


# Question
Title: Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?
I have been searching for proofs that show that $EQ\_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form:

> Construct a TM $M$ which recognizes the complement of $EQ\_{CFG}$, M = "On input ⟨G,H⟩":
>
> 1. For each string $x \in \Sigma^\*$ in ***lexicographic order***:
> 2. Test whether x ∈ L(G) and whether x ∈ L(H), using the algorithm for $A\_{CFG}$ .
> 3. If one of the tests accepts and the other rejects, accept; otherwise, continue.”

(From: http://cobweb.cs.uga.edu/~potter/theory/6\_reducibility.pdf)

Isn't this proof incorrect?

Say that my language is $\Sigma=\\{a,b\\}$ and that I have $L(G\_1) = \\{b\\}$ and $L(G\_2) = {bb}$. $M$ should accept $\langle G\_1, G\_2\rangle$ since $L(G\_1) \neq L(G\_2)$. But if we run $M$ with $\langle G\_1, G\_2\rangle$ the TM will first generate $x=a$, which isn't in either languages so the machine will go back to step 1 and then generate $x=aa$, then $x=aaa$ and so on forever. The machine will never get to $x=b$. Hence, the machine will loop on input that it should accept. Therefore $M$ isn't a Turing recognizer.

Would the proof be correct if step 1 instead would state "For each string $x \in \Sigma^\*$, *ordered by increasing size and then* lexicographic order:"? This should generate strings in the following order: $x=a$, $x=b$, $x=aa$, $x=ab$, $x=ba$, $x=bb$, $x=aaa$, and so on. So in the case above $M$ would reject when $x=b$.

# Answer
In this context, *lexicographic order* means:

* First order by length.
* Within each length, order lexicographically.

You're saying that the proof is incorrect, but in fact it is only inaccurate in that the order is not quite the lexicographic order. I would say that the proof has a small mistake, but is otherwise correct.

One often encounters such small issues in intricate mathematical arguments. Instead of immediately declaring failure when you run upon such a difficulty, you should try to see if the argument can be fixed by making small adjustments. You're not in a trial, acting as a prosecutor. Rather, you should believe the author that she had some valid proof in mind, but perhaps was a bit sloppy when trying to express her thoughts on paper. It's a cooperative game, in which you are trying to make the proof work rather than try to break it.
> 3 votes

---
Tags: turing-machines, context-free, check-my-answer
---


# Question
Title: Find an element in sorted 2D-array (matrix)
Given an $N\times N$ array, where elements are decreasing in every row and every column.

What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it does not exist in the array?

# Answer
(Copied from a post on StackOverflow)

Here's a simple approach:

1. Start at the bottom-left corner.
2. If the target is less than that value, it must be above us, so **move up one**.
3. Otherwise we know that the target can't be in that column, so **move right one**.
4. Goto 2.

For an `NxM` array, this runs in `O(N+M)`. I think it would be difficult to do better. :)

---

**Edit:** Lots of good discussion. I was talking about the general case above; clearly, if `N` or `M` are small, you could use a binary search approach to do this in something approaching logarithmic time.

Here are some details, for those who are curious:

## History

This simple algorithm is called a Saddleback Search. It's been around for a while, and it is optimal when `N == M`. Some references:

However, when `N < M`, intuition suggests that binary search should be able to do better than `O(N+M)`: For example, when `N == 1`, a pure binary search will run in logarithmic rather than linear time.

## Worst-case bound

Richard Bird examined this intuition that binary search could improve the Saddleback algorithm in a 2006 paper:

Using a rather unusual conversational technique, Bird shows us that for `N <= M`, this problem has a lower bound of `Ω(N * log(M/N))`. This bound make sense, as it gives us linear performance when `N == M` and logarithmic performance when `N == 1`.

## Algorithms for rectangular arrays

One approach that uses a row-by-row binary search looks like this:

1. Start with a rectangular array where `N < M`. Let's say `N` is rows and `M` is columns.
2. Do a binary search on the middle row for `value`. If we find it, we're done.
3. Otherwise we've found an adjacent pair of numbers `s` and `g`, where `s < value < g`.
4. The rectangle of numbers above and to the left of `s` is less than `value`, so we can eliminate it.
5. The rectangle below and to the right of `g` is greater than `value`, so we can eliminate it.
6. Go to step (2) for each of the two remaining rectangles.

In terms of worst-case complexity, this algorithm does `log(M)` work to eliminate half the possible solutions, and then recursively calls itself twice on two smaller problems. We do have to repeat a smaller version of that `log(M)` work for every row, **but if the number of rows is small compared to the number of columns, then being able to eliminate all of those columns in logarithmic time starts to become worthwhile**.

This gives the algorithm a complexity of `T(N,M) = log(M) + 2 * T(M/2, N/2)`, which Bird shows to be `O(N * log(M/N))`.

Another approach posted by Craig Gidney describes an algorithm similar the approach above: it examines a row at a time using a step size of `M/N`. His analysis shows that this results in `O(N * log(M/N))` performance as well.

## Performance Comparison

Big-O analysis is all well and good, but how well do these approaches work in practice? The chart below examines four algorithms for increasingly "square" arrays:

(The "naive" algorithm simply searches every element of the array. The "recursive" algorithm is described above. The "hybrid" algorithm is an implementation of Gidney's algorithm. For each array size, performance was measured by timing each algorithm over fixed set of 1,000,000 randomly-generated arrays.)

Some notable points:

* As expected, the "binary search" algorithms offer the best performance on rectangular arrays and the Saddleback algorithm works the best on square arrays.
* The Saddleback algorithm performs worse than the "naive" algorithm for 1-d arrays, presumably because it does multiple comparisons on each item.
* The performance hit that the "binary search" algorithms take on square arrays is presumably due to the overhead of running repeated binary searches.

## Summary

Clever use of binary search can provide `O(N * log(M/N)` performance for both rectangular and square arrays. The `O(N + M)` "saddleback" algorithm is much simpler, but suffers from performance degradation as arrays become increasingly rectangular.
> 3 votes

---
Tags: algorithms, matrices, search-problem
---


# Question
Title: Computing Cardinality of Sumsets using Convolutions and FFT
I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?

# Answer
Here is a sketch of the main ideas. Let $S,T \subseteq \mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset

$$S+T = \\{s+t \mid s \in S, t \in T\\}.$$

Let $\chi\_S$ represent the characteristic vector of a set $S$. Then

$$\chi\_{S+T} = \chi\_S * \chi\_T,$$

where $\*$ is a convolution operator.

The Fourier transform $\mathcal{F}$ has the property that

$$\mathcal{F}(f\*g) = \mathcal{F}(f) \times \mathcal{F}(g),$$

where $\times$ represents pointwise multiplication of functions. Therefore,

$$\mathcal{F}(\chi\_{S+T}) = \mathcal{F}(\chi\_S) \times \mathcal{F}(\chi\_T),$$

and in particular,

$$\chi\_{S+T} = \mathcal{F}^{-1}(\mathcal{F}(\chi\_S) \times \mathcal{F}(\chi\_T)).$$

This gives us a method to compute $S+T$. We can compute the characteristic vector $\chi\_{S+T}$ for the multiset $S+T$ by computing $\mathcal{F}(\chi\_S)$, the Fourier transform of the characteristic vector for $S$, and $\mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result. Each of these steps can be implemented efficiently using the Fast Fourier transform. The end result will be $\chi\_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.

The overall running time will be $O(n \log n)$, where $n$ is an upper bound on the largest element of $S,T$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Implementation of QuickSort to handle duplicates
I have this past year question based on the following scenario:

When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we recursively QuickSort those values on the left and those values on the right. Make the necessary changes to the partition method to achieve that.

Here is the implementation of Quicksort, written in Java. I will not include the code in the main page because it seems that this site requests for description of pseudocode rather than actual code, even if the code is very “simple”.

In particular, this quicksort implementation is similar to the typical one, but choses its pivot on the left of the array.

I have some basic understanding of the quicksort algorithm based on the actual code, but a lot of times I have to break down the code myself to understand it. Whenever I am given pseudocode hints to understand the algorithm\[and to be honest I don’t know sometimes whether a hint is a very obvious one or a rather implicit one\], I somehow cannot appreciate the “magic” behind the pseudocode.

My understanding of this implementation of quicksort is that the array has to be iterated to make 2 regions of low and high values, while we dynamically decide on where to put the pivot, call it position X, which in this implementation is chosen to be the leftmost element of the input array. If this position X is dynamically decided, how exactly do you “group elements equal to pivot” to middle, and how exactly does it adhere to the principles behind the typical algorithm?

Do inform me if more information is required or the formatting of the question doesn't adhere to the standards here.

# Answer
> 7 votes
The simple implementation idea is to separate the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot.

In pseudocode, the algorithm looks like the following.

```
algorithm quicksort(A, lo, hi):
    if lo < hi then
        p ← pivot(A, lo, hi)
        left, right ← three-way-partition(A, p, lo, hi)

        quicksort(A, lo, left - 1)
        quicksort(A, right, hi)

```

The partition procedure looks like the following.

```
procedure three-way-partition(A, pivot, lo, hi):
    l ← lo
    r ← lo
    u ← hi

    while r ≤ u:
        if A[r] < pivot:
            swap A[l] and A[r]
            l ← l + 1
            r ← r + 1
        else if A[r] > pivot:
            swap A[r] and A[u]
            u ← u - 1
        else: // the element is equal to pivot
            r ← r + 1
    return l, r

```

It uses three indices l, r and u (left, right, and upper bound), maintaining the following invariant in the while loop.

* `lo ≤ l ≤ r ≤ u ≤ hi`
* the elements with index in `[lo, l)` are smaller to the pivot.
* the elements with index in `[l, r)` are equal to the pivot.
* the elements with index in `[r, u]` are not examined yet.
* the elements with index in `(u, hi]` are greater than the pivot.

There are a few minor variants. The above should be enough for you to understand what is going on.

---
Tags: algorithms, sorting, quicksort, algorithm-design
---


# Question
Title: Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?
Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.

We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking out one row and column, and then taking the determinant of that sub-matrix.

Let's call that determinant t (i.e. there are t possible spanning trees in total).

What is the quickest known algorithm such that its input is G and it's output is one of t possible spanning trees of G (where each spanning tree has as close to $\frac{1}{t}$ chance of being selected as possible)?

Here's the algorithm I'm using currently.

---

Definitions:

$V\_{visited}$ - vertices already traversed

$E\_{visited}$ - edges already traversed

$V\_C$ - V \ V\_visited (i.e. vertices in V but not in $V\_{visited}$)

N($V\_{visited}$) - the set of all vertices v in $V\_C$ such that an edge exists between v and some vertex in $V\_{visited}$

---

Algorithm:

* sample $v\_0$ from V randomly
* add $v\_0$ to $V\_{visited}$
* sample $v\_1$ from N($V\_{visited}$) randomly
* add ($v\_0$, $v\_1$) to $E\_{visited}$
* sample $v\_2$ from N($V\_{visited}$) randomly
* add ($v\_\*$, $v\_2$) to $E\_{visited}$ (where $v\_\*$ is a randomly chosen from $v\_2$'s neighbors in $V\_{visited}$)

...

* sample $v\_{|V| - 1}$ (the second to last vertex in V) randomly
* add ($v\_\*$, $v\_{|V| - 1}$) to $E\_{visited}$ (where $v\_\*$ is a randomly chosen from $v\_{|V| - 1}$'s neighbors in $V\_{visited}$)
* sample $v\_{|V|}$ (the last vertex in V)
* add (v\*, $v\_{|V|}$) to $E\_{visited}$ (where $v\_\*$ is a randomly chosen from $v\_{|V|}$'s neighbors in $V\_{visited}$)

Now $V\_{visited}$ and $E\_{visited}$ represents a random spanning tree of G.

---

Is this the most efficient way of getting a random spanning tree? Is there a more efficient way? (Bonus points if it's parallelizable.)

# Answer
> 3 votes
I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $n^3$, but in practical usage it often runs much faster, I believe typically $n log(n)$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not accurately sample randomly, one simple counter-example would be a star graph with an extra edge.

At the start, you have one visited vertex, and one exploring vertex (both randomly chosen). You start a random walk from the exploring vertex, until you hit a visited vertex. When the random walk makes a loop, you delete the loop from your walk, and carry on. When you hit a visited vertex, you append the vertices of your current walk to the visited vertices, and save the edges of the walk to the tree you will return. Then, you choose a new exploring vertex, and do another random walk, repeating until all vertices are visited vertices.

Here's a paper on Wilson's Algorithm and it's predecessor, the Aldous-Broder Algorithm. (which is worse in practice usually)

---
Tags: graphs, algorithm-analysis, randomized-algorithms, random-graphs
---


# Question
Title: Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP]
I am trying to figure out the time complexity of a heuristical algorithm used to solve the Travelling Salesman Problem in a more efficient way than by brute force, ($\theta(n!)$ or similar)

1. The first step is to **compute Kruskal's Minimum Spanning Tree**, which to my best knowledge is of $\theta(E+V)$, where E is the number of edges of the graph, and V the number of vertices.
2. Next, the algorithm finds a **minimum-length pairwise matching** of the odd degree vertices from the result of the MST graph. Min pairwise matching can solved in $\theta (V'logV')$, where $V'$ represents the vertices that are of odd deg.

My question is, **what is the overall time complexity of my Heuristical Algorithm**, is it the sum of the two time complexities of **1** and **2**?

For further reading on the heuristical algo, consult http://web.mit.edu/urban\_or\_book/www/book/chapter6/6.4.6.html

Thanks,

# Answer
> 3 votes
Any algorithm that first does $A$ of work and then $B$ of work will have done a total of $A+B$ of work. It doesn't matter what the algorithm is, or what $A$ or $B$ are.

You might be getting confused by steps that look complicated and/or by the fact that $A$ and $B$ are expressed in terms of $\Theta$. For this reason and in general, it is a good idea to try to compute $A+B$ as well as possible, and then finally expressing the sum in terms of Big Oh. Otherwise, you run the risk of performing voodoo, and not really understanding what $\Theta$ means.

---
Tags: algorithms, graphs, time-complexity, heuristics, traveling-salesman
---


title: What's after EXPSPACE?

text:
# Question
Title: What's after EXPSPACE?
As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE.

Thinking about this question, I came up with a couple thoughts of my own:

1. Maybe EXPSPACE = the set of all Recursively Enumerable problems, i.e. $\Delta\_1$ in the arithmetical hierarchy. In this case, the rest of the arithmetical hierarchy would come after EXPSPACE.
2. Maybe there are problems with space requirements that need to be described by non-computatable functions. For example, take the Busy Beaver function, $BB(n)$, which returns the maximum number of steps an $n$-state Turing Machine could take before halting. $BB$ grows faster than any computable function -- so if a problem required $BB(n)$ space to solve, maybe that would put it in a complexity class after EXPSPACE? In other words, maybe after EXPSPACE there is one or more sets of problems that require a non-computable amount of space to solve.

# Answer
> 7 votes
EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).

The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$. If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE. So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE. And so on. There is an infinite hierarchy of complexity classes, each bigger than the previous.

This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).

---
Tags: complexity-theory, computability, decision-problem, space-complexity
---


title: LTL to Büchi automaton, deterministic?

text:
# Question
Title: LTL to Büchi automaton, deterministic?
I know it is possible to convert LTL formulas to Büchi automatons. But is it possible to convert a LTL formula to a **deterministic** Büchi automaton? Are there formulas that can't be converted to a deterministic Büchi automaton, then why not? Do you have examples for that case?

# Answer
There are languages that are representable by an LTL formula but by no deterministic Büchi automaton (DBA). Thus a translation from LTL to DBA cannot exist. An example is the formula $\mathbf{F}\mathbf{G} a$, which states that from some moment on $a$ has to hold forever. A nondeterministic Büchi automaton can guess when this moment occurs.

No deterministic Büchi automaton can accept the corresponding language. To see this, assume that there is a DBA for the language and note that when reading only $a$ an accepting state must be visited at some point. After visiting the accepting state, let the next symbol of the input word be $b$, and then $a$ again until another accepting state is reached. Such a state must be reached again eventually, as $a^\* b a^{\omega}$ is part of the language. By iterating this idea a word can be constructed that is not in the language but nevertheless is accepted by the automaton, which contradicts the assumption.
> 3 votes

---
Tags: automata, logic, linear-temporal-logic
---


# Question
Title: What is the name of the domain or theoretical problem of transmitting game states in an online game
For example, in chess (or any online game), you broadcast the game state to other players at certain times (every n-milliseconds or after a move is made). Thereupon, a player's game client renders the game state in a format suitable for human interaction.

I want to do additional research on the design/transmission of multiplayer video game states, but my ignorance of the terminology is frustrating my research efforts.

What role or documented theoretical problem describes this specific piece of game system architecture?

# Answer
I'm not sure there is a single "name" for this non-trivial situation -- not every situation you will run into will have a single "name" or terminology for that situation -- but there are multiple topics and concepts that seem relevant:

* As Draconis mentions, serialization or pickling are relevant for how to convert a complex data structure in memory into a sequence of bits that can be sent to another party.
* Data synchronization and file synchronization may also be relevant; there are techniques that may be useful if the data structure representing game state changes slowly, as then it may be more efficient to send only the changes to the other parties without having to repeatedly send the current state. You might enjoy reading about rsync and mosh.
* Video games may use various methods for lag compensation that are worth knowing about.

Stack Exchange has an entire site for game development. I suggest spending some quality time there perusing questions that seem related, to get a taste of some of the methods, concepts, and techniques that are relevant.
> 1 votes

---
Tags: computer-networks, computer-games
---


# Question
Title: Autocorrect algorithm - How to implement a decent "apostrophe & elision" feature?
**shorter version of the original question** (as requests in comments)

What is the algorithm to handle missing apostrophe as it is done in auto-correct feature of Android virtual keyboard?

(If it helps / makes sense, feel free to give info about how such feature handles the detection and 2 words being written without any space between them?)

I need this in French where this happens much more than in English.

**Example**

```
Jai -> J'ai ('I have' in French)

```

**Regex could be part of the solution?**

Here are some regex to recognize the beginning of some (french) words, but these do **generate way too many false positive candidates**

```
\b(c)(h?[aeiou])
\b(j)(h?[aeiou])
\b(n)(h?[aeiou])
\b(m)(h?[aeiou])
\b(t)(h?[aeiou])
\b(s)(h?[aeiou])
\b(l)(h?[aeiou])
\b(d)(h?[aeiou])
\b(qu)(h?[aeiou])

```

**Note:**
For sake of completeness, I alreay have the 2 remaining simple cases already covered in the dictionary xml file

```
<word src="sil">s'il</word>
<word src="sils">s'ils</word>

```

---

Keeping original question for reference purposes:

**Context**

Using the opensource AnyosftKeyboard keayboard provider app, I would like to add an "elision/apostrophe" feature to make it aware of missing apostrophe in typed word and add it in the frame of its autocorrect feature.

**A word about apostrophe & elision**

"The apostrophe in French is used to replace a final vowel which is not pronounced because the next word also start with a vowel or silent “h”. The removing of a final silent vowel is called the ELISION.

In written French, elision takes place only with the following words : ce, je, ne, me, te, se, le, la, de, que, and si (only with “il” and “ils”)."

Source, where you can read more for some examples:
https://frenchforenglishhindispeakers.wordpress.com/2012/09/25/lapostrophe/

**Example**

```
He is my friend -> Ce est mon ami (incorrect)
'Ce' is followed by 'est' -> elision (deletion) of the 'e' of 'Ce')
                -> C'est mon ami (correct)

```

**Goal**

Given the former example, I would like to implement a feature that would detect

```
Cest

```

and replace it by

```
C'est

```

That would allow the user to type faster by just ignoring apostrophe.
This behavior is already implemented in default Android keyboard

**Questions**

1 - What would be a proper algorithm to implement this "apostrophe & elison" feature?
2 - How is this feature implemented in Android keyboard(s)?

**PS**

I am not sure if this is the right place to ask such question. If not, please let me know where I should ask it. Thanks.

# Answer
You've asked two questions: about what algorithm can be used, and how it is implemented in Android. Only the former is on-topic here, so I'll answer the former. (Also, our guidelines are that you should generally ask only one question per post.)

---

Suppose French has the rule that the two words "X Y" are always replaced by an elided single-word replacement if X is one of ce, je, ne, me, te, se, le, la, de, que, or si and if Y starts with a vowel or silent "h". I don't know French well enough to know if this is indeed the rule, so I'll assume that's how French works.

To suggest elisions, you could precompute a mini-dictionary of all words Y that start with a vowel or silent "h". Then, it is easy to search all text entered to see whether it contains a pair of words of the form "X Y" where X is one of ce, je, ne, me, te, se, le, la, de, que, or si and Y is in the mini-dictionary. If you find such a pair, then you can programmatically generate the correct elision and automatically suggest it. This should be straightforward to implement.

Precomputing the mini-dictionary should be feasible. It should be easy to find a dictionary of all valid French words and identify which ones start with a vowel and which ones start with an "h". The trickiest bit is you'll need a way to identify all French words that start with a silent "h". I don't know enough about French to know whether there's a clever way to do that. However, a brute-force method is probably sufficient: I expect it would be sufficient to do it manually (list all words that start with a "h" and identify which have a silent "h"), or crowdsource it (something like Amazon Mechnical Turk, targeted at native French speakers). This only needs to be done once, so generating the mini-dictionary should be feasible.

---

I'll also mention a complementary method that's probably also worth adopting. Compute the list of all elisions, as above (by iterating over all valid pairs "X Y" that will trigger elision, then programmatically computing the correct elision). Then, add each possible elided form listed above to your spelling dictionary. In other words, extend your dictionary to include all valid elisions that can ever be encountered. This may be a useful supplement to the method above, as it will help detect typos when people try to type in the elided form but make a small mistake.

These two methods are complementary. In particular, if someone types the unelided form (e.g., "Ce est"), the first method above will auto-suggest correcting that to the elided form ("C'est"). And, if someone tries to type the elided form but makes a typo (e.g., "C'ext"), the second method will auto-suggest how to correct the typo ("C'est"). You can decide whether both of those problems are important to solve, or whether you only want to solve one of these two problems, and use that to determine which of these methods to implement.
> 1 votes

---
Tags: algorithms, program-optimization
---


# Question
Title: How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle?
I have been presented a set of FridgeIQ by a friend and she has planted an idea in my head.

FridgeIQ is a geometric disection puzzle consisting of 16 polygonal tiles as seen in the terrible picture near the bottom of this post

The shapes of the tiles are based on a square grid with the occasional diagonal across one of the grid fields. The total area of all the tiles is 40 such grid units. Each tile is identified by a single unique letter.

In the box comes a set of challenges, each giving a subset of the tiles and a shape to create. For example one challenge is: "construct a square using the tiles BDQSYJN". Which I have done in that picture and I have some left-over tiles that were not part of that particular challenge.

In addition to the standard challenges my friend has presented me with an extra set of target shapes which finally are the point of this question. I have attached another picture showing one of them in solved state.

These extra challenges all use the complete tile set, so their total area is 40 units, and they all have fourfold mirror-symmetry. Not all of them are as simple like the one in the picture, some have a hole or holes, but they are all connected.

I shall call these shapes "snowflakes" because they in a way resemble decorative snowflakes cut out of folded paper to generate the symmetries. Especially the ones with holes.

I have been asking myself: How many such shapes with these constraints are there that can actually be made from the given tiles?

Snowflakes per se there are infinitely man. But I believe the set of connected ones with finite area made only of half-unit triangles must be finite. Propably enormous, but finite. The solveable ones are a subset of those.

What would be a good algorithm to generate them? I do not expect there to be an efficient way, nor do I believe the universe has enough time left to actually make them all. But I would love to find at least some new ones.

Here's some unfinished thoughts so far:

As a first step I have built a simple recursive-backtracking solver that reproduced my manual solutions (and found loads of alternative ones). So even if it would be terribly inefficient I could just generate snowflake-shapes at will and use my solver to check them.

I have been thinking that it would suffice to generate one eighth of the shape, one half-quadrant, with a total area of 10 units. Symmetry provides the rest. Note that the solution does not have the same symmetry when considering individual tiles, only when the complete shape is taken into account.

To generate candidate shapes I could just put 20 half-unit-triangles into the half-quadrant. Hopefully in some systematic fashion. Most of those arrangements will not be compact enough and be unsolvable, though. And without a good idea for weeding them out their numbers are absolutely intractable.

Another approach would be to just generate combinations of the tiles and check them for symmetry. Again the algorithm would have to favour symmetric layouts or the exploding combinatorics mean I can never hope to find even a single new layout.

Any ideas? Keywords for searches and/or pointers to literature are also appreciated.

Thank you very much.

# Answer
SAT solvers are my favorite "big sledgehammer" to apply to this kind of problem, so let me describe how you could use a SAT solver for this problem.

Let's constrain the shape to fit within a 15x15 grid (say), and express the problem of finding a valid shape as a SAT problem. It gets a bit messy, so you'll have to be willing to tolerate that, but the approach is powerful. Introduce boolean variables $x\_{i,j,k}$, with the intended meaning that $x\_{i,j,k,r}=1$ means that we rotate tile $k$ into orientation $r$ and then put its upper-left corner in the grid cell at coordinates $(i,j)$. We'll now write down some boolean formulas that characterize what it means for this to be a valid snowflake.

There a bunch of requirements to count as a valid snowflake; I'll sketch how to express each one as a boolean formula:

* *Each tile must be used exactly once.* In other words, for each $k$, exactly one of the $x\_{i,j,k,r}$'s must be true; this is is a one-out-of-n constraint. See Encoding 1-out-of-n constraint for SAT solvers for some techniques for encoding this as a boolean formula (or if you use Z3, see https://stackoverflow.com/q/43081929/781723).
* *The shape must be symmetric.* To help check this, let's introduce auxiliary boolean variables $y\_{i,j}$, with the intended meaning that $y\_{i,j}=1$ means that the grid cell at coordinates $(i,j)$ is covered by some tile. It is easy to express $y\_{i,j}$ as a logical-or of a subset of the $x$'s (namely, all the $x\_{i',j',k,r}$ such that placing tile $k$ in orientation $r$ at position $(i',j')$ will also cover $(i,j)$; knowing the shape of each tile, you can precompute all such $x$'s; there will be 160 of them). Moreover, let's require this to have fourfold symmetry around the origin. That means $y\_{i,j} = y\_{-i,j} = y\_{i,-j} = y\_{-i,-j}$ holds for all $i,j$.
* *No two pieces overlap.* This involves a bunch of constraints of the form $(\neg x\_{i,j,k,r}) \lor (\neg x\_{i',j',k',r'})$, for all $i,j,k,r,i',j',k,k',r,r'$ such that placing tile $k$ at coordinates $(i,j)$ in orientation $r$ would overlap with placing tile $k'$ at coordinates $(i',j')$ in orientation $r'$. (This can be easily precomputed based on the shape of tiles $k$ and $k'$.)

This gives you a bunch of boolean formulas. Write down the conjunction of all of them, and then feed it to an off-the-shelf SAT solver and ask the SAT solver to find a satisfying solution for you. This will then correspond to a snowflake.

For implementing this stuff, I find Z3 a very convenient API to a SAT solver.

This will find one snowflake. What if you want multiple of them? There is a straightforward way to generate multiple solutions: after you have found one solution, you generate what's called a "blocking clause" and add it to the list of constraints (i.e., conjoin it to the formula). The "blocking clause" just says "not that one I already know of". For instance, if you already have a satisfying assignment that assigns values $c\_{i,j,k,r}$ to each $x\_{i,j,k,r}$, then the blocking clause is the formula $\lor\_{i,j,k,r} (x\_{i,j,k,r} \ne c\_{i,j,k,r})$. You can repeat this to obtain multiple solutions: each time you find another solution, you generate another blocking clause, add it to the formula, and apply the SAT solver again. Some SAT solvers even have special support for incrementally adding additional constraints that is more efficient than starting the search from scratch, though that might not be necessary.

Well, that's the idea, anyway. But here I have to confess that I lied. There is one requirement that I've left out so far: connectivity. You said you want each snowflake to be connected. That's messier to implement in a boolean formula, though also possible. The crude hack is to generate many candidate snowflakes as above, check each for connectivity, and keep only the connected ones. However, this might not work very well. So, let me describe how to encode the connectivity constraint in SAT. Beware; it gets messy, so hold onto your hat.

*The shape must be connected.* The main idea will be to pick a particular grid cell, require that it be present, and require that every other covered grid cell be connected to it. Let's say we require that the grid cell at the origin $(0,0)$ be covered. Then we can introduce auxiliary variables $z\_{i,j,s}$, with the intended meaning that $z\_{i,j,s}=1$ means that grid cell $(i,j)$ can be reached by starting at the origin and then taking $s$ steps across adjacent covered grid cells. This constraint can be encoded in SAT by noting

$$z\_{i,j,s} = y\_{i,j} \land (z\_{i-1,j,s-1} \lor z\_{i,j-1,s-1} \lor z\_{i+1,j,s-1} \lor z\_{i,j+1,s-1}).$$

We'll adopt the convention that $z\_{i,j,0}=1$, and if $(i,j)$ is outside of the 15x15 bounding box then by convention $y\_{i,j,s}=z\_{i,j,s}=0$ (we don't introduce extra variables for that, we just replace those terms with "false").

Finally, for each $i,j$, we add the constraint that $y\_{i,j} \implies \lor\_{s=0}^{39} z\_{i,j,s}$. This ensures that every covered cell is reachable. (Note that if it is reachable, it is reachable in at most 39 steps, so we only need to go up that high. In practice, I suspect that 19 or even 9 are probably large enough.)

That ensures connectivity. However, there's a potential catch: this requires everything to be connected to the origin, so it only generates snowflakes that cover the origin. We also want snowflakes that have a hole at the origin. I think you can fix this by iterating over all possibilities for the 'anchor point' (one grid cell that you'll require to be covered and require everything to be connected to), and solving the SAT instance for each possible anchor point. (To avoid duplicates, if you like you can add additional constraints to ensure disjointness of solutions. For instance, solve one SAT system where you require $(0,0)$ to be covered and everything to be connected to $(0,0)$; solve another where you require $(0,1)$ to be covered and everything to be connected to $(0,1)$ and you require $(0,0)$ to be uncovered; another where you require $(0,2)$ to be covered and everything to be connected to $(0,2)$ and you require $(0,0)$ and $(0,1)$ to be uncovered; and so on.)

Lastly, in the above I assumed that your shapes are collections of squares, i.e., they either completely cover a grid cell or don't touch it at all. Of course, this isn't valid for your tiles, due to those diagonal pieces. So, I suggest that after breaking down the 15x15 region into 225 small squares, you break down each square into four triangles. Then, instead of using the $y$'s to record which grid squares are covered, you'll need to adjust the definition of the $y$'s and the above formulas to record which triangles are covered. Everything should go through with some straightforward adjustments.

Phew. I told you it would get messy. The basic idea here is that we are taking each of the conditions for a shape to count as a valid snowflake, writing them down in boolean logic, and then letting the SAT solver find solutions that meet all of those requirements. SAT solvers today are amazing and contain clever and powerful strategies to automatically find solutions that meet your requirements. Researchers have spent decades coming up with better algorithms and improving the engineering of the tools; you can't hope to duplicate that, so rather than trying, you can build on all of their work and apply it to your specific situation.
> 2 votes

---
Tags: np-hard, tiling
---


# Question
Title: Is there any Boosting algorithm with closed-form solutions?
My goal is to formulate the learning and generalization phases of any Boosting algorithm as a matrix-vector operation.

Through Google, I found a good pdf (\*) describing several boosting algorithms but the author Marco Cusumano-Towner only hints and doesn't explain how to recast the boosting algorithms (GradientBoost, Adaboost, QuadBoost) using matrix operations.

My question is:

Can I formulate a boosting algorithm as a regression, a game or a linear programming and arrive at closed-form solution which uses only matrix operations?

(\*) Boosting with log-loss

# Answer
> 3 votes
Basically: no. Boosting is a "meta-method". If you have a weak learner (an algorithm for learning), it is a way of taking advantage of that weak learner algorithm iteratively to do better at learning some concept than the weak learner would do on its own.

Many/most weak learners don't have a closed-form solution for the model they build; instead, their learning algorithm may fundamentally rely upon iterative methods, optimization algorithms, or other techniques. As a result, boosting with such a weak learner won't have a closed-form solution, either.

---
Tags: machine-learning
---


title: Transforming TM with useless state(s)

text:
# Question
Title: Transforming TM with useless state(s)
I'm new to Computation Theory and trying to figure out the undecidability problems. Last night, I came up with the language of TM with a useless state:

> $\text{USELESS\_TM} = \\{ \langle M, q \rangle\mid q\text{ is a useless state in TM }M\\}$

where q is a state that M never enters on any input *w*. The problem is simply defined as: "determining whether a Turing machine has any useless states".

The question wanted me to show that this language is undecidable using a reduction argument. I thought it would be logical to reduce *EMPTY\_TM* to *USELESS\_TM*, and using contradiction show that if *USELESS\_TM* is decidable, then *EMPTY\_TM* will be decidable (which we know it's not).

I wanted to step a little bit forward in grasping the concepts of *USELESS\_TM*. Is it possible to modify this Turing Machine to another TM M without useless states in such a way that *L(USELESS) = L(M)*? I thought about just removing the useless states, as the machine never gets into those states, so the language won't change. But, is there another way by like modifying a TM's definition to ensure that it has no useless states?

---

**UPDATE** . I borrowed the first example from Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Problems 5.13 --Textbook

# Answer
> 5 votes
This question is refreshing. Answers are given in the headers below.

---

### There exists a Turing machine (TM) without useless states that accepts the same language as an arbitrary given TM.

Let TM $M=⟨Q,\Gamma, b,\Sigma, \delta, q\_0, F⟩$ where $$\delta: (Q\setminus F)\times \Gamma\not\to Q\times\Gamma\times\\{L,R\\}$$ is the transition function, where $L$ is left shift, $R$ is the right shift. For each state $q\in Q$, $q$ is either useful (reachable) or useless (non-reachable). Let $Q'$ be the set of all useful states. Let $\delta'$ be the restriction of $\delta$ on $(Q'\setminus F)\times \Gamma$. Then we can check $M'=⟨Q',\Gamma, b,\Sigma, \delta, q\_0, F\cap Q'⟩$ is a well-defined TM without useless states that accepts the same language as $M$.

Intuitively, $M'$ is simply $M$ with all useless states removed.

---

Exercise 3.19 indicates none of the following two languages is decidable. $$\text{USELESS\_STATES}=\\{⟨M, g⟩\mid M \text{ is a TM with a useless state } g \\}$$ $$\\{⟨M, M'⟩\mid M \text{ is a TM and }M'\text{ is defined based on M as above} \\}$$

---

### No algorithm can produce a TM without useless states that accepts the same language as an arbitrary given TM.

For the sake of contradiction, suppose there is a such an algorithm $A$.

Let $M$ be a given TM. Applying $A$, we can construct another TM $M'$ without useless states that accepts the same language as $M$.

What is $F'$, the set of final states (a.k.a. accepting states) of $M'$?

* If $F'$ is empty, then $M'$ never accepts any word. That is, $L(M')$ is empty.
* If $F'$ is not empty, then $M'$ does accept some word since the states in $F'$ are reachable. That is, $L(M')$ is not empty.

Just by checking whether $F$ is empty or not, we will know whether $L(M')$ is empty or not. Since $L(M')$ is the same as $L(M)$, we will also know whether $L(M)$ is empty or not. Hence, we can decide whether $L(M)$ is empty or not.

However, it is well-known that it is undecidable to determine whether an arbitrary given TM accepts no words or not. This is a contradiction.

What we have used in the proof above is the following obvious property of TMs without useless states. Such a TM accepts at least one word if and only if it has at least one final state.

Intuitively, there is no algorithm to determine whether a final state in a TM is useless or not.

---

Here are two easy related exercise.

**Exercise 1.** Show the following language is not decidable. $$\\{⟨M⟩\mid M \text{ is a TM that accepts no words}\\}$$

**Exercise 2.** Show the following language is not decidable. $$\\{⟨M, M'⟩\mid M \text{ is a TM and }\\ M' \text{ is a TM without useless states such that } L(M)=L(M')\\}$$

---
Tags: turing-machines
---


# Question
Title: Placing items into compatible bucket types to find an optimal total value
Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a bucket type iff the item is able to be inserted into a bucket of that type. The goal is to insert the items into the buckets such that the total value of the inserted items is highest.

For example:

```
Items:
compatible with       | value
A,B,C                 | 17.641
A,B,C                 | 14.821
A,B                   | 14.274
A,B                   | 13.755
A,B                   | 12.240
A,B                   | 12.240
B,C                   | 11.960
A,B                   | 10.270
A,B,C                 | 9.958
A,B,C                 | 8.552

Buckets:
bucket type           | capacity
A                     | 2
B                     | 3
C                     | 4

Solution:
bucket                | values
A                     | 17.641, 12.240
B                     | 14.274, 13.755, 12.240
C                     | 11.960, 9.958, 8.552, 14.821

```

Is this problem a special case of any existing problems? I am finding it hard to envision an algorithm to solve it, but I feel that a good solution would require passing over the item list multiple times and maintaining a queue of best matches for each bucket type.

What would be the wost-case complexity of the resulting algorithm? Could a situation with 5 bucket types and 30 items explode in computational expense?

# Answer
You can formalize this problem as a minimum-cost flow problem.

You construct the graph as follows.

* First construct a source vertex $s$ and a sink vertex $t$.
* For each item $i$, add a vertex $u\_i$ and add an edge from $s$ to $u\_i$ with capacity 1 and with cost equal to the negation of the value of item $i$.
* For each bucket $j$, add a vertex $v\_j$ and add an edge from $v\_j$ to $t$ with capacity equal to the capacity of bucket $j$ and with cost 0.
* If item $i$ is compatible with bucket $j$, add an edge from $u\_i$ to $v\_j$ with capacity 1 and with cost 0.

Now you can use some polynomial time algorithm (for example, the cycle canceling algorithm) to find an integral solution of the minimum-cost flow problem. This integral solution then shows how you assign the items: if there is a flow 1 on $(u\_i, v\_j)$, then assign item $i$ to bucket $j$.
> 3 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Why in Declarative Programming variables are not reassigned?
I've read that a Declarative language is called "stateless". This means that we can imagine that internally every variable is a constant variable, and it never get reassigned ( in contrast with what usually happens in procedural programming). How can this work?

# Answer
This isn't as exotic as it sounds, and you can do it in a procedural language fairly easily. The basic idea is just that instead of changing a value you just have a function return a new value. For instance, instead of something like

```
string read()
{
  string s = '';

  while((string c = getchar()) != '\n')
  {
    s += c;
  }

  return s;
}

```

you could write something like

```
string read()
{
  string c = getchar();

  if(c == '\n')
  {
    return '';
  }
  else
  {
    return c + read();
  }
}

```

See how no variable ever gets reassigned here?

There are some subtleties here that I'm not going into, but I just wanted to illustrate that the idea is not that farfetched.
> 2 votes

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


# Question
Title: Rigorous error bounds for eigenvalue solvers
I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them. I need a validation that the results are correct up to an error of at most $10^{-3}$.

Very specifically I want to ask if there is a rigorous error-analysis involving rounding errors up to machine precision in each step.

More generally: Are there other practical algorithms for eigenvalues with such a rigorous error analysis.

# Answer
It might suffice to ask the solver to give you both the eigenvalue $\lambda$ and the corresponding eigenvector $v$. Then you can verify for yourself how much error there is. Note that if $\lambda$ is the eigenvalue corresponding to eigenvector $v$, for matrix $M$, then we have $Mv=\lambda v$. So if you know $M$ and $v$ exactly, and you have a claim that $\hat{\lambda}$ is within $\epsilon$ of the true eigenvalue $\lambda$, it suffices to check that

$$(\hat{\lambda}-\epsilon)v \le Mv \le (\hat{\lambda}+\epsilon)v$$

where $\le$ is to be interpreted separately for each index, i.e., you should check that $(\hat{\lambda}-\epsilon)v\_i \le (Mv)\_i \le (\hat{\lambda}+\epsilon)v\_i$ holds for each index.

If there is some error in the eigenvector $\hat{v}$ returned by the solver, then there is the possibility that the above check might fail, even if $\hat{\lambda}$ is indeed a true eigenvalue of the matrix. I don't know whether there's a nice way to adapt the above calculation to address this issue. If the operator norm $\\|M\\|\_1$ is small, then it might work to check that

$$(\hat{\lambda}-\epsilon)\hat{v}\_i -c \le M\hat{v} \le (\hat{\lambda}+\epsilon)\hat{v} + c$$

where $c = \\|M - \hat{\lambda} \text{Id}\\|\_1 \times c'$ and $c'$ is an upper bound on the amount of error in $v$ (measured in $L\_1$ distance) that you're willing to tolerate. I'm not sure if this is exactly right; there might be issues in this last criterion, so check it yourself before believing in it.
> 2 votes

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


title: Does any CPU not contain an ALU?

text:
# Question
Title: Does any CPU not contain an ALU?
Is there any kind of CPU which doesn't contain an ALU ?

# Answer
> 7 votes
If the CPU (Central Processing Unit) does any processing, it will do either Arithmetic or Logic operations... in a sense, *some* form of ALU is the core of the CPU.

# Answer
> 5 votes
A CPU is not a microprocessor. So if you look at early mechanical computers such as Konrad Zuse's Z3 and Charles Babbage's mechanical computer, those were computers with a CPU that was not a microprocessor and did not have an ALU.

John von Neumann proposed the ALU concept in 1945, there were functional computers before that e.g. Zuse's Z3 that did not have an ALU.

If you want to look more closely at a spec design for a modern FPGA ALU design, please have a look at my ALU (done in Quartus), that is built from primitives.

# Answer
> 4 votes
Yes! See the Wikipedia page for Turing Machine. A Turing Machine is a state machine with a pointer that can move left or right on an "infinite" tape (representing memory.) There is a picture on the Wikipedia page of a Turing machine implemented with Lego. The foundation of Computability Theory is the Church-Turing Thesis, which states that a Turing Machine is as capable as any other computer. You can *simulate* a computer with an ALU on a Turing Machine if you want to.

If you are worried that the operations of moving left and right on a tape might be too similar to increment and decrement operations that an ALU might do, then see http://esolangs.org/wiki/BitBitJump. They show how you can implement a universal turing machine with a machine that does nothing but bit copies (which are doing a form of self-modifying code.)

# Answer
> 4 votes
ALU-less computers are certainly possible.

The 1 Square Inch TTL CPU project on hackaday.io by roelh is able to circumvent the need for an ALU using lookup tables! Furthermore, the project also says the HP9100 calculator uses a similar technique.

> THERE IS NO ALU
>
> NO ALU... I could have programmed a small PIC or AVR as ALU (Wikipedia: ALU), but that's cheating. With the current microcode version, the only arithmetic that it can do is compare bytes and address items in a table. And the hardware won't allow much more.
>
> For incrementing or decrementing a byte, lookup-tables are set up that contain an incremented or decremented version of the lower 8 address bits. Now the processor can increment or decrement a byte. Nothing more is needed to do arithmetic !
>
> This was also done in the legendary HP9100 programmable calculator that was introduced in 1968. It worked with transistors and diodes, not a single digital IC ! The story behind this calculator is amazing, and can be read on hp9825.com. People have tried to reverse-engineer the diode-transistor logic and came to the conclusion that the hardware of the machine could only increment or decrement digits (described by Tony Duell). Yet it could calculate with high-precision floating point numbers, including logarithms and trigonometry, at high speed. More info about the HP9100 can be found in the HP journal 1968-09.

# Answer
> 0 votes
Superscalar processors have several execution units which often are not equivalent. I'd not be surprised if there has been some design where the repartition of responsibilities between the execution units was such that none of them would merit the name ALU for some definitions of the term.

---
Tags: computer-architecture
---


# Question
Title: Machine code: How can an OS prevent user-level programs from accessing each other's memory?
Okay, I’ve done a lot of research on this, but I can’t seem to wrap my head around it. Essentially, the question is as follows: How can an operating system prevent a machine instruction from a user-level program (Firefox, Word, etc.) from accessing memory locations that it isn’t supposed to access?

Here’s what I think I understand so far: Machine code, as you would for example find it in a .exe file after building your C/C++ program, is a sequence of binary instructions. These instructions can run directly on the CPU (assuming that the program was compiled for that CPU’s instruction set, e.g. x86). So, you don’t technically need an operating system to “run a program” in a broader sense – which isn’t surprising, since an operating system is just a program itself. Also, the CPU doesn’t work in terms of “programs” or “processes”, but in terms of individual instructions.

Now, if we do have an operating system (e.g. Windows), part of its job is to assign an encapsulated memory segment to each running user-level program (e.g. Firefox, Word, my own C++ program, …), and to make sure that they can’t read/corrupt each other’s memory.

This is where things get fuzzy for me. If I were to write my own operating system (or other bare-metal program), I would need to be able to use machine instructions to read/write to and from any existing location in the entire memory, right? So, how does an operating system make sure that no user-level program sends such instructions to the CPU on its own, without “asking the OS for permission” to access a certain memory location?

I would actually love to learn more on the entire topic of going from high-level code to machine instructions. For instance, I would also like to understand what user-level program threads and OS-level processes look like on bare-metal, etc. So, if anyone could point me to a good resource, that would be highly appreciated. Nonetheless, this isn’t the core of my post, just a side note.

# Answer
The key is Virtual Memory.

There might be many ways to do this, but the reigning one across most OSes (\*nix or Windowses alike) is Virtual Memory. And it needs CPU support, which is given in x86 by the MMU (Memory Management Unit) and in which I'll base my examples further on.

The secret is: no user-level process has access to the whole CPU. x86 has four *rings* of execution, and certain CPU opcodes (instructions) execute only within the appropriate *ring*. *Ring 0* is for the kernel (the heart of the OS), and *ring 3* is for user-level processes (rings 1 and 2 are most often not used, and if used, it's usually for virtualisation purposes -- out of the scope of this answer). If you execute an instruction within the wrong ring, the CPU faults to the kernel. Hence, if a process tries to execute a privilege instruction, when the CPU is on *ring 3* mode, the CPU itself stops that process and gives control to the kernel, which will usually kill that process. Only the kernel can change the ring mode.

The secret-key for memory protection is that, all memory accesses, unless executed within the kernel's *ring 0* (and perhaps even within that ring mode, but that's not relevant for this discussion, as we're talking only about user processes, not the kernel), need to go through the MMU, which will translate the memory address of the process to that which the kernel has actually given.

So two different processes can access a memory cell by the same address, say, *0x45b3c1*, whatever. In reality, the MMU will translate real-time each process's request to what the kernel says it should be.

For this, the kernel prepares page tables, which you can imagine as a "`map<void*, void*>`" (forgive my over-simplification here, and try to imagine the crazy optimisations needed), of what the process actually has. And it prepares tables only for what the process previously said it would use. If the process asks for an address that hasn't previously asked the kernel to prepare a table for him, then the CPU says this process got nuts and in reference of this process, it signals the infamous SEGFAULT to the kernel, which will decide what to do next.

I know that this is sort of self-promotion, but I just recently wrote a lot about this topic and even gave a talk at my company, in case the link is welcomed I'd like to share: https://www.farfromready.com/malloc-alone-a-story-of-the-computers-memory/
> 2 votes

# Answer
**Interpretation**

A program is a file - so are pictures and text documents.

You can choose how to perceive the contents of these files. A good way to perceive each of these is as code in a language. To understand the code, it needs to be interpreted by an interpreter.

There are numerous ways to design an interpreter:

* Substitution
* Denotational
* Big-Step
* Small-Step

*Substitution*

Essential the interpreter rewrites the program into a simpler form. Much like when you *rewrite* `2 * 5` as `10`.

*Denotational*

Here the OS has a known safe function that it executes whenever it sees a particular instruction in the code.

The benefits here are that this function can have numerous safety checks and security measures.

*Big-Step*

A Big Step interpreter risks being wrong/non-terminating in order to resolve operations.

Non-Deterministic Finite State Machines fall into this category, as they can be wrong and have to back-track, or have to track each potential solution simultaneously.

The benefit to this approach is that the interpreter can finish the program in one of three top-level states:

* The program ran and succeeded
* The program ran but failed
* The program was wrong

*Small-Step*

The code is composed of discrete and finite steps. The job of the interpreter is to track the effects produced by the code.

**Running Untrusted Code**

The job of the OS is to run this untrusted code in such a way that none of the other applications are adversely affected (roughly).

So the OS literally interprets the program, and updates a model of the state of that program.

At this point the OS does have a choice in how it interprets the program. It could for example be Denotational when loading the program, and "rewrite" every instruction. It will already need to do this to bind dynamic-link-addresses, but the concept can be expanded to include all instructions.

* all "safe" instructions are rewritten (copied) as themselves
* any "unsafe" instruction can be
    + substituted for an OS interrupt that fulfils the intention securely
    + substituted for a sequence of "safe" instructions
    + cause the program to be rejected and never run.

At the end of this process is a rewritten program which is "safe" at the per instruction level. This doesn't mean that the program cannot exploit hardware flaws, just that no "bad" instructions were found.

The OS could us Substitution to interpret patterns of instructions - particularly vulnerable sequences. These could be replaced with a more secure code pattern that achieves the same outcomes.

This will protect against some well known issues, but comes at the cost of having to analyse the code. This is a lot harder for languages (like machine languages) which are built to take advantage of small-step semantics.

The OS could use Big-Step interpretation, though generally this occurs in the hardware itself. Generally the CPU operates so quickly that memory is slow. It often pays to evaluate a tree of paths simultaneously and pick the correct path from the tree when the results from the relevant branch checks come back.

Of course these hardware implementations are not necessarily safe. The recent Spectre and Meltdown exploits highlight this, the fixes across the variants for many processors/work-loads caused slowdowns by 10-30%. The difference between using Big-Step semantics provided through hardware, and the software interpretation required to replace them, or make them safe.

Finally the OS can apply small-step semantics. This could be achieved by emulating a machine, and updating the state on that emulation appropriately. However this is slow, the OS could take advantage of the fact that the Processor is a real world example of that machine.

This relies on trusting the program/processor enough that either the program will behave well (even if the hardware could allow sneaky sneaky operations), or that the processor will tell the OS when the program misbehaves. Usually it is a balance of these two extremes with the OS interpreting the program enough to be satisfied that it is not out-right bad news, and the OS using the controls that the processors gives it to prevent certain instructions from being executed.

Most Processors have:

* a Virtual Memory Table which maps the virtual memory space of a process to the physical memory address. The memory access instructions use it to map from process memory to physical memory, with missing entries causing an OS interrupt. The OS then is only needed when dealing with non-memory resident pages, and unallocated memory. The processor itself does not allow access to the other physical memory locations.
* Security levels that enable/disable certain instructions. A program running within that processor will cause a OS interrupt if it executes a privileged instruction and its security level isn't correct. It is then up to the OS as to how to handle this privileged behaviour.
> 0 votes

# Answer
The simple solution is that the processor has different modes where the CPU has different capabilities. For example : The OS runs in mode 0. In mode 0 an application can set up memory protection for others, and start applications running in mode 1. In mode 1 the processor fails if you try to use one of the instructions that change memory protection or the current mode. The mode 0 program can also set a timer which will give control back to the operatin system after some time.
> 0 votes

---
Tags: memory-management, virtual-memory
---


# Question
Title: what the mean and median filters with an n x n kernel (neighborhood) do to the grey-levels of the image?
* sorry i haven't found a good title for these three questions i'm wondering if someone could give me explaination with proof (if possible ) of these three questions :

1. Given a grey-level image stored as a rectangular array of grey-level values, describe what the mean and median filters with an n x n kernel (neighborhood) do to the grey-levels of the image?
    2. Describe the visual effect on an image of the mean and median filters. What happens when the size n of the neighborhood increases ?
    3. Explain what are Gaussian noise and salt-and-pepper noise. Which type of filter is suitable for removing each type of noise ?

# Answer
1. For each pixel in the original image, a 2n-1 x 2n-1 convolution matrix is centered on it and multiplied with the surrounding greyscale values, element-wise.
2. Mean and median filters result in an image blur, with the amount of blur increasing as n is increased.
3. Gaussian noise follows a normal distribution (the probability of a pixel changing by a certain value follows this distribution). Salt and pepper noise sometimes occurs from pixels being randomly set to near either their maximum (salt) or minimum (pepper) values. A mean filter might be more appropriate for gaussian noise, whereas a median filter helps ignore significant outliers (salt and pepper).
> 2 votes

---
Tags: computer-vision, image-processing
---


title: Is $\sum_{i=1}^n i \in \Theta(n^2)$?

text:
# Question
Title: Is $\sum_{i=1}^n i \in \Theta(n^2)$?
Please help me understand on how to prove or disprove the following. I have been practicing and doing others which are ok, but with this sum, it is rather confusing.

> $$\sum\_{i=1}^n i \in \Theta(n^2). $$

# Answer
> 2 votes
Here is the computer science approach to answering this question.

On the one hand, we have $$ \sum\_{i=1}^n i \leq \sum\_{i=1}^n n = n^2. $$ On the other hand, we have $$ \sum\_{i=1}^n i \geq \sum\_{i=\lfloor n/2 \rfloor}^n \lfloor n/2 \rfloor = \lfloor n/2 \rfloor \lceil n/2 \rceil \geq (n/2)^2 - 1/4, $$ since when $n$ is odd, $\lfloor n/2 \rfloor \lceil n/2 \rceil = (n/2-1/2)(n/2+1/2)$.

---
Tags: asymptotics
---


title: Is this a proper LL(1) Grammar?

text:
# Question
Title: Is this a proper LL(1) Grammar?
Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) parsers - mostly from papers from different colleges. They tend to use the same examples and I've never been a fan of abstracting through notation, so I'm almost positive I have the syntax incorrect.

The input is very trivial:

```
header>rows>h-row>a|b

main>rows>m-row>qs|d
qs>qs-row>qa|qu

footer>rows>f-row>a|b

```

And this is the grammar definition:

```
S -> aBC
B -> op
C -> a

```

First:

```
S: [a]
B: [>, |, /]
C: [a]

```

Follow:

```
S: $
C: $
B: C | S

```

# Answer
> 3 votes
It's a perfectly valid grammar, and it's certainly LL(1). But since it only generates three sentences, it's probably not what you are looking for.

The three sentences:

```
a < a
a | a
a / a

```

**For precision**: As written, it's not quite correct. In order to achieve what I imagine you meant by the FIRST sets, you'd actually need to he a bit more precise. Instead of using $op$, you write:

$$\begin{align}B& \to \mathbb{\<}\\ B&\to\text{|}\\ B&\to\text{/} \end{align}$$

Alternatively, you could define $op$ as the three possible operators, as above, and leave $B\to op$.

**Also**: $FOLLOW$ sets (like $FIRST$ sets) are sets of *terminals*. So $S$ and $C$ are not going to be found in any $FOLLOW$ set. $FOLLOW(B)$ is $\\{a\\}$.

---
Tags: formal-grammars, compilers, parsers, interpreters, ll-k
---


# Question
Title: Finding max value algorithm with subset comparison
I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison.

The intuitive algorithm would be comparing them linearly: compare two items, compare the biggest with the next one, repeat. That would give us a total of $N-1$ comparisons.

Since I couldn't come up with anything, I want to know if there is some algorithm to do this more efficiently (making fewer comparisons), taking advantage of subset comparison being allowed.

# Answer
Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:

* If one of the sets is bigger than the other, we say that its sum is larger.
* If the two sets have equal size, we say that their sums are equal.

We can represent each comparison as a vector of length $n$: the comparison $\sum\_{i \in A} w\_i \gtrless \sum\_{i \in B} w\_i?$ (where $w\_i$ are the weights) corresponds to the vector $1\_A - 1\_B$, i.e., the vector having value $1$ at the $A$-coordinates, having value $-1$ at the $B$-coordinates, and having value $0$ elsewhere.

Let $\mathbf{x}\_1,\ldots,\mathbf{x}\_m$ denote the vectors corresponding to comparisons of sets of equal size (so $m \< n-1$), and let $\mathbf{1}$ be the constant $1$ vector. Since $m+1 \< n$, there is a non-zero vector $\mathbf{v}$ orthogonal to all of $\mathbf{x}\_1,\ldots,\mathbf{x}\_m,\mathbf{1}$. We can assume that $|v\_i| \leq 1$ for all $i$.

Consider the vector $\mathbf{w}\_\delta = \mathbf{1} + \delta \mathbf{v}$, where $|\delta| \< 1/n$. It is not hard to check that $\mathbf{w}\_\delta$ is consistent with our replies to the algorithm. Yet $\mathbf{w}\_\delta$ and $\mathbf{w}\_{-\delta}$ have different maximal values, so the algorithm will make a mistake on at least one of them.

This argument even works when we are allowed to ask arbitrary queries of the form $\operatorname{sgn}(\sum\_i x\_i w\_i)$.
> 2 votes

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


# Question
Title: Have I proved $\sum_{i=1}^{\lg n} 2^{i-1} = \Theta(n\lg n)$?
I have an exercise problem and don't know why its answer is like this. $$ \sum\_{i=1}^{\lg n} 2^{i-1} \in \Theta(2^{\lg n}) = \Theta(n). $$

Regarding this equation, I think it would be, $$ \sum\_{i=1}^{\lg n} 2^{i-1} \in \Theta(\lg n \cdot 2^{\lg n}) = \Theta(\lg n \cdot n), $$ with the proof, $$ \sum\_{i=1}^{g(n)}f(i) \le \sum\_{i=1}^{g(n)}f(g(n)) = g(n)\cdot f(g(n)). $$

My thought with this question, $ f(n) = 2^{i-1} $ and $ g(n)= \lg n $. Then result would be $ \lg n \cdot 2^{\lg n - 1} $.

Can anyone point out where I made a mistake? (I am not asking grading mine, but tell me where I mis-think)

# Answer
Your argument shows that $$ \sum\_{i=1}^{\lg n} 2^{i-1} = O(n\lg n). $$ It doesn't show the matching lower bound, which is actually false.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: What is the avantage of having memory mapped I/O?
I can't make out what is the avantage of it comparing with the port designed I/O

Is it faster? Is it more reliable? Is it cheaper?

# Answer
> 4 votes
There are many advantages to memory mapped I/O

1. Access: Memory mapped devices use the same instructions/addressing modes as regular memory. These map well into high level languages allowing device drivers to manipulate devices without the need to drop down into assembly language to use special I/O instructions.
2. Security: As memory addressed devices, memory management hardware can be used to control access to those devices. Generally, I/O instructions are "wide open" in privileged modes allowing a driver to access any I/O mapped device, even those that it should not.
3. Flexibility: Almost without exception, the processor instructions available for memory are more varied and versatile than those for I/O mapped. With memory, load/store instructions are supplemented with various monodic (inc/dec/etc) and dyadic (add/sub/etc) operators. Special I/O mode instructions are generally limited to load/store. This typically gives the compiler a better shot at creating better code (ignoring the whole RISC/CISC debate for now).

Support for special I/O mapping is generally a legacy issue. The x86 for example is (on some level) compatible all the way back to the 8008.

Very old processors often included I/O mapped device support because the memory address space was so small (often 65,536 bytes or less) that I/O addressing provided a way to preserve memory address space for actual memory.

Modern processors have larger (4G or larger) address spaces so that this is no longer an issue.

# Answer
> 0 votes
If you rely on port io you drive up the pin count. Memory mapping provides a more flexible method in the design. They're really two very different things with different intentions. Ports are generally speaking extensions of the processor that map to specific functions. A memory map is a extension that allows access. It's more abstract. At least until you put something into the map. :)

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


# Question
Title: Show: "Checking no solution for system of linear equations with integer variables and coefficients" $\in \mathbf{NP}$
I've been struggling for a while trying to solve this problem:

Show that the following problem is in $\mathbf{NP}$:

> Check that a system of linear equations with $m$ integer variables and integer coefficients has no solution.

---

Let $L = \\{\langle A, b \rangle\ |\ A \in \mathbb{Z}^m\times\mathbb{Z}^m\text{ and }Ax = b\text{ has no solution for }x \in \mathbb{Z}^{m} \\}$

(please, feel free to correct if anywhere I'm wrong)

For showing that a language is in $\mathbf{NP}$ we have to construct a Turing Machine, indicating what we have chosen as certificate. If the TM is nondeterministic, then nondeterministically we pick a certificate and check the condition. If it is deterministic, we pass the certificate as one of the parameters (of the two parameters TM. The other parameter is, in this case, the pair $\langle A, b \rangle$).

I'm having trouble trying to choose the appropriate certificate.

My approaches:

1) Certificate: a vector $x \in \mathbb{Z}^{m}$, such that doesn't solve $Ax = b$. *Issue*: We would have to try every possible $x$ to show that $\nexists$ such vector for which solution may exist...

2) Certificate: Rank of $A$. if the $\mathrm{rank} A \neq m$, then the system has no solution and we $Accept$. *Issue*: doesn't necessarily mean that $x \in \mathbb{Z}^{m}$.

3) Consider $\overline{L} = \\{\langle A, b \rangle\ |\ A \in \mathbb{Z}\times\mathbb{Z}\text{ and }Ax = b\text{ has a solution for }x \in \mathbb{Z}^{m} \\}$.

Showing that the system **has a solution** seems easier than showing that there is no one. I guess the certificate has to be a vector $x \in \mathbb{Z}^{m}$, for which the $Ax = b$ is satisfied. Then, if I'm not mistaking, constructing a polynomial-time deterministic TM for $\overline{L}$ is straight forward. The thing is that this will show that $\overline{L} \in \mathbf{NP}$. This implies that $L \in$ co-$\mathbf{NP}$.

So showing that $L \in \mathbf{NP}$ would be equivalent to showing that co-$\mathbf{NP} = \mathbf{NP}$??

# Answer
There is a polynomial time algorithm that determines whether a system of linear equations over the integers has a solution. The algorithm uses Hermite normal form, which can be computed in polynomial time. See lecture notes of Swastik Kopparty: Hermite normal form and finding integer solutions.

Your proof that your problem is in coNP is incomplete, since you haven't shown that the witness has polynomial size. Assuming you did manage to show it, all this implies is that the problem is in coNP, not that it is coNP-hard. There's absolutely no issue for a problem to be in both NP and coNP. Indeed, every problem in P is also in NP and coNP. If you can put a problem in both NP and coNP, then this *suggests* that it might actually be in P, though it is conjectured that $\mathsf{P} \subsetneq \mathsf{NP} \cap \mathsf{coNP}$. One problem which might lie in the middle is (a decision version of) integer factorization.
> 3 votes

---
Tags: turing-machines, np, decision-problem, complexity-classes
---


# Question
Title: Decision problem that can be verified but not run in n^2 time
A much much weaker idea similar to the P=NP question, is there a decision problem that can be verified in $O(n^2)$ time, but it can be proven that there is no algorithm that decides it $O(n^2)$ time?

# Answer
> 5 votes
The answer depends a lot on the model of computation.

On one extreme: in the decision tree model, many lower bounds can be proven. For instance, consider the 3SUM problem. You can verify an alleged solution to the 3SUM problem in $O(n)$ time, but it's conjectured that no algorithm can solve the 3SUM problem in $O(n^{2-\epsilon})$ time for any $\epsilon\>0$. One can prove this holds in some version of the algebraic decision tree model; one can prove that any algorithm to solve it in this model must take $\Omega(n^2)$ time. This provides a gap of $O(n^2)$ vs $O(n)$ for solving vs verifying solutions, *if* the verifier is limited to the algebraic decision tree model. This is a pretty limited result; in this case, the model means that we're restricting attention to algorithms of a particular form. So, it doesn't rule out the possibility of some other algorithm (that does something weird) being faster.

On the other extreme: if we allow arbitrary (non-uniform) boolean circuits, then there is no explicitly stated function $f$ on $n$ bits where we can currently prove that every circuit for computing $f$ needs $\ge 3.1n$ gates. In other words, this is saying that we have no clue how to prove lower bounds for circuits. Roughly speaking, we have no known result of a problem where we can prove that solving it requires circuits of size $\omega(n)$. See, e.g., https://cstheory.stackexchange.com/a/8005/5038 and https://cstheory.stackexchange.com/q/21400/5038. So, given our current state of knowledge, we have no hope of proving a result like that if the model of computation is unrestricted boolean circuits.

---
Tags: time-complexity
---


# Question
Title: Reducing 3SAT to a Set Splitting Problem
I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S\_1, S\_2,...,S\_m$ of these items I want a yes or no answer based upon the fact if it is possible to color the items red and blue so that each set $S\_i$ contains at least one red item and at least one blue item.

I know this this problem is in NP and it is fairly simple to prove (at least that is what I think).

I actually want to prove that the problem is NP hard by reduction from 3SAT. I want to be able to convert an instance of 3SAT into an instance of the aforementioned set-splitting such that a yes instance of 3SAT get mapped to a yes instance of set-splitting and vice versa.

I have a basic intuition about how I can do this: given a 3SAT formula $f$ on $n$ variables I will create $2n+1$ items. One to denote each $x\_i$ one for each $\overline{x\_i}$ and an extra item. I am not quite sure how to proceed beyond this basic intuition. This might be a gap in my understanding of the problem. Is this the right way to approach this? If so, how can I use this intuition to actually prove that this is NP hard by way of reduction from 3SAT?

Thank you!

# Answer
Your problem is a generalization of NAE-SAT, an NP-complete version of SAT (see for example David Witmer's lecture notes in which we want each clause to have at least one satisfied literal and at least one falsified literal.

In order to convert NAE-SAT to your problem, identify literals with items, have a set per clause, and also have a set per variable, forcing the two literals to get opposite colors. Details left to you.
> 3 votes

---
Tags: np-complete, np-hard, np, decision-problem
---


title: avl trees rotations question

text:
# Question
Title: avl trees rotations question
As you can see in this tree its unbalanced at the root with a balanced factor of $-2$. You can also perform a Right left rotation or a Right Right rotation. Which do you have to pick in this case?

# Answer
Apparently, you want to rebalance the AVL tree.

You can either do a simple left rotation or a right-left rotation.

I prefer not to mention right-right rotation since that term is misleading and ambiguous.

You can visualize what is happening. Go to AVL tree visualization, a page created by David Galles. Insert 2, 1, 4, 3, 5 in that order. Now look closely when you delete 1.
> 2 votes

---
Tags: binary-search-trees, avl-trees
---


# Question
Title: Why cannot we enumerate all Turing machines that have no fixed point?
The language

$$ L\_1 = \\{w \in \\{0, 1\\}^\ast \mid \exists x \in \\{0, 1\\}^\ast\colon M\_w(x) = x\\} $$

<sub>($w$ is an encoding of a DTM, $M\_w$ is the respective DTM.)</sub>

is not decidable, according to Rice's theorem. However, it is recursively enumerable: an NTM simply chooses an $x$ for which the condition is fulfilled non-deterministically.

Consider the very similar language

$$ L\_2 = \\{w \in \\{0, 1\\}^\ast \mid \exists x \in \\{0, 1\\}^\ast\colon M\_w(x) \neq x\\} $$

Rice's theorem argues that this is undecidable, but neither is it semi-decidable according to my sources.

Why can't we argue for $L\_2$ as we did for $L\_1$, stating that an NTM chooses the input $x$ non-deterministically, the condition is fulfilled, $L\_2 \in \mathsf{RE}$?

The proof that $L\_2 \not\in \mathsf{RE}$ performs the reduction $\overline H \leq L\_2$, where $H$ is the halting problem. I understand this proof by reduction, but to me, it seems contradictory to the argument for recursive enumerability I give above.

# Answer
Because we cannot find, given a NTM $N$ and an input $x$, whether $N$ fulfills the condition $N(x)\not= x$ in any given finite amount of time. More precisely, we cannot enumerate all pairs $(N,x)$ such that $N(x)\not= x$, although we can enumerate all pairs $(N,x)$ such that $N$ halts on $x$ and $N(x)\not= x$.

---

Think for a moment. When can you consider $(N,x)$ fulfills the requirement $N(x)\not=x$?

* We run $N$ with input $x$ for some time and it stops. If it does not output $x$, great, we have found one.
* We run $N$ with input $x$. However $N$ does not stop yet. It seems $N$ just won't stop. We want very much to say $(N,x)$ does not fulfill that requirement; however, **there is no moment we can be sure of that**. $N$ is just running at all times. If we conclude $(N,x)$ does fulfill the requirement at some moment, it can happen $N$ will stop at the next moment, outputting $x$. Because of this possibility, we will **never** add $(N,x)$ when $N$ never stops on input $x$, even though $(N,x)$ does satisfy the requirement.

Note this is vastly different from the other case. When can we consider $(N,x)$ fulfils the requirement $N(x)=x$?

* We run $N$ with input $x$ for some time and it stops. If it does output $x$, great, we have found one.
* We run $N$ with input $x$. However $N$ does not stop yet. Fine, we just do not consider $(N,x)$ fulfils the requirement yet. Continue running $N$.

---

You might argue that NTM $N$ can guess $x$ such that $N(x)$ will halt and output $y\not=x$. So we will find one such $N$. There is no problem in that.

However, consider the case when $N$ never stops on every input. Now, imagine the exact moment you consider that $N$ fulfills the condition that $N(x)\not= x$ for some $x$, using any algorithm. **What is known to you at that moment?** All you know is that $N$ has not stopped yet on any input. That, however, does not exclude the possibility that $N$ might stop later on for all inputs along all paths, always outputting the input. We can never exclude that possibility, forever. (More precisely, we can exclude that possibility for some $N$ for some inputs. However, there is no algorithm can determine that possibility for all $N$.)

> If I chose a DTM in place of an NTM to run $M\_w(x)$ for all possible inputs, it would be game over if $M\_w(x)$ didn't halt because that would prevent subsequent runs of $M\_w(x)$ with different $x$es.

It would also be game over if $M\_w(x)$ will not halt for all $x$. Your $NTM$ will be running forever without ever outputting anything. That $(M,x)$ is in $L\_2$ but your algorithm cannot claim it is in $L\_2$ since there is no moment when the algorithm is able to claim that.

---

The explanation above is meant to be a way to understand the situation. A rigorous proof is still needed to confirm the conclusion mathematically (or "compute sciencely"). Since you have known a rigorous proof, I will not provide one here.
> 2 votes

# Answer
The NTM can recognize, not determine (because if no such $x$ exists, the NTM would not halt), $M\_w(x)=x$, because if such an $x$ exists, the NTM would halt finally (and accept $\langle M\_w, x\rangle$).

The NTM cannot recognize $M\_w(x)\neq x$, because even if such an $x$ exists, the NTM may not halt.

If you change $L\_2$ to $\\{w \in \\{0, 1\\}^\ast \mid \exists x \in \\{0, 1\\}^\ast\colon \color{red}{M\_w(x)\text{ halts }}\text{and } M\_w(x) \neq x\\}$, then it becomes recognizable.
> 1 votes

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


# Question
Title: Can map-reduce speed up the count-min-sketch algorithm?
Is there any possibility of improvement in the result of count-min-sketch algorithm if we will use Map Reduce approach? Improvement in performance can be in terms of accuracy, time complexity or the work done needed.

# Answer
> 1 votes
yes. section 3.2 from here.

> A key feature of the operations which manipulate the sketch is that they are largely oblivious to the current state of the data structure. That is, the updates to the sketch do not require inspection of the current state. This means that data structure is highly suitable for parallelization and distributed computation. Firstly, each row of the sketch is updated independently of others, so the sketch can be partitioned row-wise among threads on a single machine. But more than this, one can build sketches of different subsets of the data (after agreeing on the same parameters w, d and set of hash functions to use), and these sketches can be combined to give the sketch of the union of the data. Sketch combination is straightforward: given sketch arrays of size w × d, they are combined by summing them up, entry-wise. This implies that sketches can be a useful tool in large scale data analysis, within a distributed model such as MapReduce. Each machine can build and “emit” a sketch of its local data, and these can then be combined at a single machine (i.e. a single reducer simply sums up all the sketches, entry-wise) to generate the sketch of a potentially huge collection of data. This approach can be dramatically more efficient in terms of network communication (and hence time and other resources) than the solution of computing exact counts for each item, and filtering out the low counts.

---
Tags: algorithms, online-algorithms, mapreduce
---


title: Why language is not regular

text:
# Question
Title: Why language is not regular
Taken from site "Geeks For Geeks". The lemma: "A concatenation of pattern(regular) and a non-pattern(not-regular) is also not regular language."

example: $\left \\{L={a^{n}b^{2m}|n\geq 1,m\geq 1} \right \\}$

I think I managed to build dfa (q2 is an accepting state) for language. perhaps I'm wrong...

# Answer
Yes, you are absolutely right. GeeksforGeeks is just wrong in this case.

Your analysis is correct. The language $L=\\{a^n b^{2m} \mid n \ge 1, m \ge 1\\}$ certainly *is* regular. Your DFA seems fine. I don't know why the GeeksforGeeks article claims it is not; but in any case they are wrong. It's a strange example; even by their own notions of what counts as a "regular pattern", $b^{2m}$ is a "regular pattern", so I don't know why they are giving that example.

Even if we try to look at better examples, the claim is still wrong. For instance, consider the language

$$L = \\{a^n a^p \mid n \ge 0, p \text{ is prime}\\}.$$

This language is described by the concatenation of a "regular pattern" and a "non-regular pattern", so that article claims it should be not regular -- but they're wrong. In fact, $L$ is regular, as $L = \\{a^m \mid m \ge 2\\}$.

This whole notion of a "regular pattern" and "non-regular pattern" in that article is pretty much baloney. I realize what they're trying to do -- they're trying to look for a shortcut to quickly tell whether a language is regular based on the syntax of the description of the language -- but those proposed rules are not a reliable way to tell whether a language is regular or not, and the notion of a "regular pattern" is not well-defined. That's not a standard concept -- it's just something someone on the Internet made up. At best, it is a way to form a quick guess at whether a language is regular or non-regular -- but I would recommend always following that up by proving your guess is correct, as their proposed rules are a bit dodgy.

Perhaps a lesson is to rely on primary sources, like well-regarded textbooks, and don't trust too much what you read on the Internet.
> 6 votes

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


# Question
Title: Selection of dates respecting delay constraints
I encountered an issue at work that can be derived approximatively to this problem.

Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) possible triggering times per day.

I have to select exactly 5 times per day (between 00:00 a.m. and 12:00 p.m) to respect the following constraints:

* a minimum delay between two selections (for instance 2 hours)
* a maximum delay between two selections (for instance 10 hours)

The delay between the last selection of the day and the first of the next day also has to be considered for constraints.

I need an algorithm that find one solution or if there is no solution.

Until now, I did not have the constraint on the maximum delay. Thus, I solved it greedily, day after day, picking the soonest possible date until 5 times are selected. At any moment if no times was available for the day, the problem had no solution.

So does this maximum delay constraint make the problem NP-complete ? Or is there a polynomial algorithm that can solve it ?

# Answer
This can be solved in polynomial time using dynamic programming.

We'll build up an array $A$. The meaning of the array is as follows: if $t$ is a time on day $d$ and $i \in \\{1,2,3,4,5\\}$, then $A\[t,i\]=1$ means that it's possible to build a schedule for days $1..d$ that ends at time $t$ and obeys all the constraints (minimum delay $\ge$ 2 hours, maximum delay $\le$ 10 hours, exactly 5 times chosen on days $1..d-1$ and exactly $i$ times chosen on day $d$).

Note that, once you've filled in $A\[1..t-1,1..5\]$, you can fill in $A\[t,1..5\]$ via a simple recurrence relationship: e.g.,

$$A\[t,1\] = \lor\_{t'} A\[t',5\]$$

where $t'$ ranges over all times that are on the day before $t$, and that fall at least 2 hours before and at most 10 hours before $t$; and

$$A\[t,i\] = \lor\_{t''} A\[t'',i-1\] \text{ for } i=2,3,4,5$$

where $t''$ ranges over all times that are on the same day as $t$ but before $t$, and that fall at least 2 hours before and at most 10 hours before $t$.

Thus, you can fill in the array $A$ entry-by-entry, in order of increasing $t$. This will give a linear-time algorithm for finding a valid schedule that meets your constraints.
> 1 votes

---
Tags: algorithms, optimization, constraint-satisfaction
---


# Question
Title: Efficient algorithm to replace list of integers with nearest bigger element
The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of `toString()`.

> Given an unsorted list of integers, design a O(n) algorithm to transform the list such that the integers are replaced by the next bigger integer on their right. If there is no bigger integer on its right, the integer remains the same.
>
> For example \[2,1,4,5,3,6,7,9,4,8\] becomes \[4,4,5,6,6,7,9,9,8,8\].

I have come out with an algorithm after a long time, but a recent test case reveals that my algorithm doesn't cover all cases. Here is my attempt written in Java. Can anyone suggest the algorithm for this problem?

# Answer
The issue is how to find "the next bigger integer on their right", which sounds like a stack operation.

Here is the algorithm in its essence.

1. Create an empty stack.
2. Iterate over the given list of integers from left to right.
    1. Push the current integer to the stack.
    2. While the top of the stack is smaller than the next integer in the list, replace the integer in the list that corresponds to the top of the stack by that next integer in the list followed by popping the stack.

The idea of the algorithm is to let the stack store the integers for which we have not found their next bigger integers yet, in the natural order in which they have been examined. Those integers will be strictly decreasing.

---

In the actual implementation, in order to locate the integer in the given list that corresponds to the top of the stack, the indices of the integers should be stored in the stack instead of the integer themselves.

Here is code in Python:

```
l = [2, 1, 4, 5, 3, 6, 7, 9, 4, 8, 5, 1 ,3, 8]
s = []
for i in range(len(l) - 1):
    s.append(i)
    while s and l[i + 1] > l[s[-1]]:
        l[s.pop()] = l[i + 1]
print(l)

```

For readers who does not use Python, `s[-1]` is the last element of the list `s`.

---

Since each index of the given list is appended once and popped at most once and the last index is not even included, the time-complexity of the algorithm is $O(n)$, where $n$ is the length of the given list.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?
Is the following true or false? Why?

Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq\_{p} X$.

# Answer
The statement is: If a problem $P$ is $\mathbf{NP}$-hard, then there is a reduction from $\text{FALSIFIABLE}$ to $P$. ($\text{FALSIFIABLE}$ being the set of formulas for which there is an assignment which makes the formula false; this is trivially equal to the complement of $\text{TAUT}$.)

**This statement is correct.**

Why? Simply because $\text{FALSIFIABLE}$ is $\mathbf{NP}$-complete. You can prove this exactly the same way $\text{SAT}$ is proven to be $\mathbf{NP}$-complete, only inverting the truth values "true" and "false" (i.e., instead of searching for an assignment which makes the formula true, you search for an assignment which makes the formula false). This is not at all surprising; it is basically the duality principle of Boolean algebra.
> 2 votes

---
Tags: complexity-theory, reductions, np-hard, polynomial-time
---