# Question
Title: How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?
I understand the textbook explanation of how to use dynamic programming to find the minimum edit distance between 2 strings but how do we get to pick the 2nd string?

I don't think the entire dictionary is compared as sometimes the difference is either in the middle or the end. I assume that in the end, what is suggested is the string that has the minimum edit distance after creating a certain number of $n \times m$ tables, where $n$ is the typed string length and $m$ is that of the other words that may be close.

# Answer
> 25 votes
**Yes, the entire dictionary is compared against each word. This can be fast by using a trie and an algorithm similar to Levenshtein's.**

I have built my own spelling corrector that checks words against a dictionary of about 1 million words and 12.5 million word-pairs (for basic word usage checking). It takes about 0.7 milliseconds to check a single word and provide corrective suggestions based on these two dictionaries. I'm sure it could be significantly faster; I stopped optimizing once it became fast enough for my purposes, which was to check a few paragraphs in under 1 second.

Several of the other answers have hinted toward how spelling and grammar checkers/correctors work, but let's put all the pieces together and see how we could build our own fast spelling corrector.

Disclaimer: I don't know if this is how Microsoft and Google actually do it, but it works very well for my needs.

# How to build a spelling corrector

I started from this excellent article by Peter Norvig. It's worth a read if you're serious about implementing your own spelling corrector, but the most important insight is the use of Bayes' Theorem to decompose the question into independent parts. Let's start by actually stating our goal.

Goal: given the user typed word $w$, find and rank the most likely possibilities for what the user actually meant to type, $c$ ("candidate"). In other words, for each $c$ in our list of 1 million candidates, we are looking for the probability that the user wanted to type each $c$ when they actually typed $w$. Norvig's insight is to use Bayes' theorem to turn this into manageable independent sub-problems:

$$ P(c|w) = \frac{P(c)P(w|c)}{P(w)} $$

Where:

$P(c|w)$ = the probability the user meant $c$ when they actually typed $w$ (our goal)

$P(c)$ = the probability of typing $c$. This is simply a measure of the frequency of the candidate word in our **language model**. For example, in English, P("the") is larger than P("thaw").

$P(w|c)$ = The probability that the user would type $w$ when they meant $c$. This is our **error model**. For example, the probability the user would type "thew" when they meant "thaw" is probably higher than typing "thew" when they really meant "the".

$P(w)$ = The probability of typing $w$. We're simply not interested in any cases where $w$ was not typed, because we observe that it was. Therefore this value is basically 1 (or at least constant) for our purposes and we divide it out.

Since we're just trying to rank suggestions relative to each other, I'm not going to worry about making sure the probabilities actually add up to 1.

**Levenshtein distance is an error model**. We could say that that $P(w|c)$ = $Levenshtein(w,c)$ and we get a perfectly serviceable error model. It might even be the best we can do in some cases, e.g. if we're trying to reconstruct English text that was sent over a noisy line that caused essentially random insertion, deletion, and replacement errors. However, for a human typist, we can do better by taking into account common language-specific errors. For instance, accidentally replacing an "e" with an "a" is much more likely than with an "m". As gnasher729 pointed out, we could also take the user's keyboard layout into account.

## Generating Candidate Words

Now we can get to the heart of your question: how do we generate candidates to check? Every word in our dictionary is a candidate! If we try to do this with a naïve brute-force approach, we can think of some obvious waste. For instance, we shouldn't need to fully evaluate the word "continuations" if we've already evaluated "continuation"; this hints that a Trie (or "prefix tree") might help us here. We also probably shouldn't be comparing the "s" in "continuations" against the "y" in "specificity"; surely we know by that point that neither is a good substitute for the other! This hints that we can significantly cull down our search for candidates if we keep track of compounding error while doing our search.

So our steps are:

**Step 1. Organize your dictionary into a giant trie**

Let's say our dictionary consists of the 12 words shown below. The corresponding trie is shown to the right. We also want to keep track of which nodes are word endings, which I've given a solid blue color:

Even with 1 million words, this data structure is only a few hundred megabytes and fits easily into memory. (The n-grams are the memory hogs!)

**Step 2. Calculate compounding error while searching for suggestions**

Let's say the user writes "saken", and we want to suggest corrections from this dictionary. We keep a list of 3-tuples containing the following information:

1. Where we are in the word
2. Where we are in the trie
3. The total compounded error so far

This list starts with one entry: (first letter, root of trie, 0), as shown below.

Until we have an empty list, we loop over every element in the list. If it's a valid word (that is, the trie pointer is pointing to a node marked "end-of-word"), we return it as a possible suggestion, along with its error. Then (valid word or not) we remove it from our list and use it as a new seed to continue to populate the list.

Given a starting 3-tuple as a seed, we add new elements to the list differently for each type of error (insertion, deletion, and substitution). For instance, when checking for substitution errors, we add an element for every child of our current trie node, with additional error based on the letters being substituted (taking into account surrounding letters as well). This is illustrated below for the "a" node, but we do the same for every other child. Of course, substituting "s" for "s" gets an error value of 0.

We always have a single possible insertion error, which is the letter we're currently on. In that case, the word-pointer moves forward, but the trie-pointer stays where it is. Deletions are the opposite: the word-pointer stays where it is, while the trie-pointer moves forward (to every child).

Here's an example traversal with mixed errors. Here we are considering the possibility that the user accidentally typed "s" instead of "t", then correctly typed "a", then accidentally inserted a "k", then accidentally type "e" when they meant to type "k". In reality, only the last row would be left in our list, but the others are left for illustration.

If we're using a simple Levenshtein distance error model, then our total error so far is 3.

Of course it's more likely that the user actually did mean "ke" at this point, but our job right now is to simply enumerate and score all the possible ways $w$ could have been typed instead of $c$.

**Step 3. Stop traversing your trie if the error gets too large**

Now that we're calculating errors as we're generating suggestions, we can simply refuse to add a new 3-tuple to our list if the total error is too high (notice the error never decreases). That culls entire branches of the trie from future traversal and keeps our search narrowly focused.

In fact a rather small limit works well here if errors are reasonably independently distributed (an example where they're not is keyboard off-by-one errors like gnasher729 demonstrated, but you could make a custom error type with its own traversal logic for this). If I have a 5% chance of making a single typo in a 6-letter word, I probably have about a (5%)^2 = 0.25% chance of making two typos in that same word. Therefore an error limit of about 3 is good enough in practice (with Levenshtein distance; obviously this depends on your error model), and significantly reduces your search space.

Another way you can cull your search is by only ever considering the shortest path (error-wise) to a given suggestion. If you implement this, you'll find you get lots of cases where the same word is being suggested via many different paths, and you really only need to keep one as your next seed.

Once you have your list of suggestions, you already have $P(w|c)$ calculated for each, so you simply need to look up $P(w)$ and you're done! In my implementation, this all happens in about 0.7 milliseconds (700 microseconds) per word, including an additional step where I account for the frequency of the word appearing next to its neighbors. There are lots of parameters you can tune to your needs, and probably lots of other ways to make this faster.

# Answer
> 19 votes
Companies with search engines (e.g. Microsoft or Google) don't always directly search for the string with the smallest Levenshtein distance. They have a huge database of search queries, from which they have developed a huge database of commonly misspelled/mistyped variants, and what word the user probably meant to type instead.

They also have a huge corpus of text, and can use this to (for example) predict which word is most likely to come next based on what you've typed so far, or to assist with autocompletion. The set of likely words is much smaller than the set of possible words.

Don't underestimate the value of understanding exactly how real humans misspell or mistype things. For example, when you misspell something, you rarely get the first letter wrong, unless it's an ambiguous letter such as a vowel or "c" vs "k".

With all that said, let's assume that you're not doing any of that, and just want to find a string with edit distance as close as possible. The general idea is to find a set of candidate words first (e.g. all words within a certain edit distance, or all words with promising sub-matches), and then use some kind of finer-grained metric to decide which member of the set to suggest.

A simple approach is to use a trie, such as a ternary search trie. Another option is to combine k-mer matches.

# Answer
> 8 votes
I just tried and found that the spelling checker on my phone finds a perfectly fine replacement for “gekki wirkd”. Look at your keyboard, and it is obvious.

A good spelling checker does much better than using Levenshtein distance. For example it will use keyboard distance, assuming your fingers typed the wrong letter. It knows grammar. It knows which words tend to follow which other words.

It knows which words are rarely used. Like “wether” which is a perfectly fine English word but very likely not the one you wanted. It will know where to use there, their or they’re if it’s clever. I actually typed “its clever” and the spelling checker fixed it.

All in all, writing a good spelling checker will take you ages of full time work.

# Answer
> 2 votes
There are many ways to organize data to optimize queries.

Regarding text search the classical way is to build a Suffix Tree. This allows to perform searchs in a big text with the time proportional to the *pattern length*, instead of the text length.

You can think about a Suffix Tree as some sort of database that performs pattern queries really fast.

The companies you mentioned wont use a classical Suffix Tree, they are probably using some more complicated, distributed proprietary data structures in order to optimize the lookups, however the point remains the same:

they trade time for space, so the have pre-build indexes/data structures/DBs that make typical search queries really fast.

Moreover they also cache a lot of search queries, so common queries don't actually have to really search the database.

The same is true for keyboards, they can take a dictionary with all English words and organize it so that when you type they can easily find the closest matches, and maybe sort them by how frequently they are used... no need to compute any form of edit distance at all.

# Answer
> 0 votes
The Damerau-Levenshtein distance metric is a function that measures a distance between two strings, A and B, and, importantly, satisifes (quoting from Wikipedia)

1. the distance from A to B is zero if and only if A and B are the same point,
2. the distance between two distinct points is positive,
3. the distance from A to B is the same as the distance from B to A, and
4. the distance from A to B is less than or equal to the distance from A to B via any third point C.

This makes it ideal for consumption in a number of data-structures that are optimized for searching metric spaces.

For instance, the Burkhard-Keller tree is well suited for nearest-neighbor type searches in metric spaces and make for speedy retrieval of neighbors without comparison to the entire lexicon.

---
Tags: algorithms, strings, edit-distance
---


# Question
Title: What does 'single sequential computer' mean?
I'm from a non-technical background. (Mentioning this for the convenience of explanation w.r.t intelligibility)

Book Name - "Introduction to Algorithms"

Authors - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

# Answer
Single means that they are talking about only one computer. Sequential means that they are not considering computers that can execute multiple instructions in parallel (as an example think of computers with multiple processors or processor cores).
> 1 votes

---
Tags: computer-architecture
---


title: A question about euclidean graph

text:
# Question
Title: A question about euclidean graph
I have an Euclidean graph $G$, but i should changes the weight of some edge of $G$ to $+\infty$. My problem is, after this change, $G$ remain Euclidean graph or not?

# Answer
The page you linked has the following definition:

> A Euclidean graph is a graph in which the vertices represent points in the plane, and the edges are assigned lengths equal to the Euclidean distance between those points

Since the distance between any pair of points in the plane is always finite, it follows that no euclidean graph can have infinite edge weights.
> 1 votes

---
Tags: algorithms, graphs
---


title: Existence of infinite unique FSAs

text:
# Question
Title: Existence of infinite unique FSAs
It is reasonably simple to show that there are an infinite number of different finite state automata that can be constructed, but has it been proven if there is an infinite number of unique finite state automata? Meaning no automata that recognize the same language.

I asked my professor and he didn't know, and I haven't been able to find anything about it online.

# Answer
Sure. You can easily find an automaton that recognizes the language $\\{a\\}$, and one that recognizes the language $\\{aa\\}$, and one that recognizes the language $\\{aaa\\}$. You can probably see where I'm going from here...
> 2 votes

# Answer
There is no language $L$ that has a 'unique' automaton. For this language $L$ there is however a unique *minimal* automaton, this is a consequence of the Myhill-Nerode theorem.

From the minimal automaton for $L$ we can construct an infinite amount of different non-minimal automaton for the same language $L$ by simply adding states. If adding unreachable states does not convince you, we could also add states that share the same equivalence class in the same Myhill-Nerode relation.
> 0 votes

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


# Question
Title: How does clients observe different replicas and stale data even if the replicas include same set of updates?
I am studying about gossip architecture. This is gossip architecture-:

Gossip architecture provides 2 guarentees-:

1)Each client gets consistent service over time(meaning even if clients use different RMs, the returned data reflects the updates seen by client as of now)

2. Relaxed consistency between replicas-: All RMs eventually receive all updates and apply updates with ordering guarentee.

But here is the confusion.

It also says-:

> Two clients may observe different replicas even though replicas include same set of updates, ana client may observe stale data.

How can 2 clients observe different replicas when replicas include same set of updates and ordering is guarenteed?

As per my inituition, it is probably because since the consistency is relaxed so at that moment, all replicas don't have same set of updates.

And may be that's why clients observe stale data. Am I correct?

# Answer
**this is not an definite answer, but more like an educated guess, so please be sceptical**

this link has some thoughts about *partial ordering* and what vector clocks can actually do: https://scattered-thoughts.net/writing/causal-ordering/.

From what I see - partial ordering is ordering that does not (cannot?) order all events, just some. A replica can have several updates which are not ordered, i.e., it cannot say in which order they arrived.

The clients (or FEs) communicate their last timestamp `prev`, e.g., `prev_1` and `prev_2`. Some updates on the replica can potentially be ordered with respect to each prev, i.e., some updates are newer than prev\_1 and some than prev\_2. But you cannot say whether prev\_1 is newer than prev\_2 or the respective updates are newer than each other. Thus when two clients provide two different values of prev, replicas may return different updates.

Example: Let's say variable x had a value `x_0` at some time t\_0 (in vector clock values) on all replicas. Client 1 connects to replica 1 and updates x to value x\_i. Around the same (human) time\[1\] client 2 connects to replica 2 and updates x to x\_j. Each event gets assigned a timestamp in update id. Let's call them t\_i and t\_j. Then client 3 changes x\_i to x\_ii, which is assigned a timestamp t\_ii, while client 4 changes x\_j to x\_jj at timestamp t\_jj.

Eventually, all updates reach all replicas. Each replica can say that `t_jj` happened after `t_j` and `t_j` happened after `t_0`, i.e., `x_jj` is newer than `x_j` which is newer than `x_0`. The replica can say that `t_ii` \> `t_i` \> `t_0`, i.e., `x_ii` is newer than `x_i`. But it can't say whether `x_ii` is newer than `x_jj` or vice versa.

Now clients 1 and 2 go to the same replica and request a value. Client 1 provides his last timestamp `t_i` and client 2 provides his last timestamp `t_j`. Then replica should give client 1 a value `x_ii`, since it is newer than `t_i` and client 2 a value `x_jj`, since it is newer than `t_j`.

I think the same logic happens if there are clients 4 and 5 who asked two different replicas, each one knew only about x\_i/x\_j respectively. Once all updates reach all replicas these 2 clients will also get different values based on timestamps they provide.

\[1\] read as, the updates about x\_1 did not reach other replica
> -1 votes

---
Tags: distributed-systems
---


# Question
Title: Had Conway's Game of Life or any C-A been demonstrated to generate non-repeating pattern?
As we know, Conway's Game of Life is Turing-complete. And Turing-complete systems can be used to calculate irrational numbers such as $\sqrt{2}$, $\pi$, $e$, etc. which have non-repeating digits.

So it might be natural to reach the conclusion that Conway's Game of Life can be used to generate non-repeating digits.

To limit the scope of this question and not make it open-ended and opinion-based, I'll be asking: has there been research on cellular automata:

* generating infinite non-repeating patterns,
* by programming it to carry out computation similar to square root and base-2 logarithm over fixed-point numbers? (these computations are the easiest I've thought of that can be carried out on fixed-point numbers with sufficient numericall accuracy)

# Answer
Rule 110 is a cellular automaton that is Turing complete, hence it can generate non-repeating patterns. Since it is Turing complete it can certainly compute the square root of a fixed-point number.
> 1 votes

---
Tags: turing-completeness, cellular-automata
---


# Question
Title: Recursive Bijections Between Countably Infinite Sets
The textbook I am currently studying (*Introduction to Kolmogorov Complexity and Its Applications* by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers to a total recursive function (i.e. a computable function which is defined for all arguments).

Consider two countably infinite sets $\mathcal{S}, \mathcal{T}$ and a bijection $F: \mathcal{S} \to \mathcal{T}.$

**Question 1:** Since $F$ must be defined for all arguments, does this mean that any computable bijection must be total recursive and not partial recursive?

**Question 2:** Are there bijections between two countably infinite sets that are *not* recursive?

The answer to the first question seems to me to be yes. However I am much more unsure about the second. However, the use of the term 'recursive bijection' seems to imply to me that there must be bijections that are not recursive.

# Answer
A) This depends on how you've set things up. If, eg, you have $\mathcal{S}$, $\mathcal{T}$ as subsets of $\mathbb{N}$, then a computable (recursive) bijection $F : \mathcal{S} \to \mathcal{T}$ needs to be only defined on $\mathcal{S}$, not on all of $\mathbb{N}$.

B) A straight-forward example would be $G : \mathbb{N} \to \mathbb{N}$ where $G(2n) = 2n$ if $n \in H$, $G(2n+1) = 2n+1$ if $n \in H$, $G(2n) = 2n+1$ if $n \notin H$ and $G(2n+1) = 2n$ if $n \notin H$. Here $H$ denotes the Halting problem.

If you want an example where there is no computable bijection at all, consider $\mathbb{N}$ and $\mathbb{N} \setminus H$. It is a standard exercise to show that there cannot be any computable surjection $s : \mathbb{N} \to (\mathbb{N} \setminus H)$.
> 1 votes

---
Tags: computability, recursion
---


# Question
Title: How to get the numbers in the Sieve of Eratosthenes with wheel factorisation?
I'd like some help with figuring out the algorithm for the Sieve of Eratosthenes with wheel factorisation. Specifically, I need help figuring out if it's possible to convert between an index and the number its supposed to represent (or between an index and a spoke and turn pair), and if it is, how it'd be done. For more context, the way I'm thinking of implementing the algorithm would involve:

* Obtaining some seed primes from an implementation of the sieve without wheel factorisation (aka, the simple sieve) and calculating their product to obtain the modulus.
* Using a list of booleans (assume all indexing/numbering terminology I use are 0 based) to somehow represent numbers and their primality. The list's elements' values will be their primality and their indices will somehow be converted to and from the numbers.

The numbers the list will represent will only be the numbers \>= the modulus (the primes \< modulus will just be computed using the simple sieve) and are in the spokes of the wheel (aka columns of the table) that contain the numbers which are potentially prime, which would be determined by determining the prime numbers (using the simple sieve) in the first turn of the wheel (aka, the first row, or the one after the initial row). E.g., with seed primes 2 and 3, the spokes with potential primes would be the ones containing 7 and 11 in their first turn.

The current spoke, turn and index values will be tracked.

Currently, I can convert between the actual number and a pair of spoke and turn values, but my problem is that I'm not sure how I'd convert to and from an index in the list to the number that it's supposed to represent (or otherwise between an index and a spoke-turn pair). The reason why I want to convert between the number and index (or spoke-turn pair and index) is that there is a part of the simple sieve algorithm which involves iterating through the list starting from the index representing the square of the current prime by the current prime's multiples, which I'd also like to do in the version with wheel factorisation.

Is it even possible to do it this way, or would the list have to represent all the numbers instead of excluding the numbers that are obviously not prime (i.e., with seeds 2 and 3, these would be in spokes containing 6, 8, 9 and 10 in the first turn)? If not, how should I try to implement the sieve with wheel factorisation instead?

# Answer
I really dislike the “spokes” and “wheels”, they just make things confusing.

I assume the Sieve of Eratosthenes is understood.

Let S be a set of primes, usually a small set of small primes. No prime is divisible by an element of S, except the members of S itself. We can therefore try to create a sieve that excludes all multiples of elements of S

Let P be the product of the elements of S. If we test whether kP + j is divisible by an element of S is independent on k and only depends on j, 0 \<= j \< P.

Let Q be the product of the elements of S minus 1. For example if S = { 2, 3, 5, 7 } then P = 2 * 3 * 5 * 7 = 210, and S = 1 * 2 * 4 * 6 = 48. It is reasonably obvious that k\*P + j is not divisible by an element of S for exactly Q out of the P possible values for j. Let M be the set of values j, 0 \<= j \< P, which are not divisible by elements of S.

We now create a sieve, but not using 1 bit per integer, but Q bits for every group of P integers. Only Q bits corresponding to the numbers in M need to be stored, because if j is not in M then kP + j is composite (with the exception of the elements of S).

Given an integer p, we write p = kP + j, 0 \<= j \< P. To check if p is a prime, we use a table of length P which maps j to an index I if j is the I-th element of M, starting with 0, and to -1 if j is not in M. If I \< 0 then p is not a prime, unless P is in S. otherwise, but #i in the k-th group of P bits is set if and only if p is a prime.

A bit position 0 \<= I \< Q is translated to I using another table of length Q. The I-th bit in the k-the group of bits corresponds to the integer k\*P + j, where j is found by taking the I-th entry in the second table.

As an example. with S = { 2, 3, 5 }, P = 30, Q = 8, M = { 1, 7, 11, 13, 17, 29, 23, 29 }, the second lookup table is \[ 1, 7, 11, 13, 17, 19, 23 29 \] and the first table is \[-1. 0, -1, -1, -1, -1, -1, 1, -1, -1, -1, 2, -1, 3, -1, -1, -1, 4, -1, 5, -1, 1, -1, 6, -1, -1, -1, -1, -, 7\].

To build the sieve, for numbers from 0 to nP - 1, we create a table with n groups of Q bits. The bit corresponding to 1 is cleared, all other bits are set. Multiples of elements if S need not be removed.
> 1 votes

---
Tags: algorithms, number-theory, primes
---


# Question
Title: Pandemic board game - find all possible next 4 actions
I hope I am asking this on the right community.

I am building an Artificial Intelligence to play the board game Pandemic. The AI uses a Monte Carlo algorithm. After implementing the game rules and the AI, it works as expected (very poorly, but it works).

I figured the main problem the current algorithm has is the action dispersion. In Pandemic, each player is allowed up to 4 actions. The number of possible actions is usually between 10 and 100. The current algorithm run 1000 Monte Carlo simulations to chose to the best next action, perform the action and start again. This results in a lot of useless simulation as, if the AI play the action A, it will consider playing the action !A.

I think it would be much more efficient to compute all the valuable series a 4 actions, as there are usually less than 50 efficient/valuable series of 4 actions to play. But my current implementation is way to slow and memory inefficient.

Here is a recap of the rules (simplified):

* there are 48 cities on the board, each city having between 3 to 5 neighbours. The graph is always the same.
* part of the disease spreading mechanism is between 0 and 3 cubes on each city
* a player has between 0 and 7 city card in his hand
* a player moves between cities

The possible actions are:

* MOVE: the player moves from the city he is in to a neighbour city
* HEAL: the player removes one cube from the city he is in
* CHARTER FLIGHT: if the player has the card of the city he is in, he can discard it to move to any other city
* DIRECT FLIGHT: the player can discard any card from its hand to move to the card's city
* SHARE KNOWLEDGE: the player can give or take the card of the city he is in to/from another player in the same city
* BUILD: the player can discard the card of the city he is in to build a Research Center
* MOVE BETWEEN RESEARCH CENTER: if there is a research center in the city the player is in, he can move to any other research center

**Implementation** The implementation need to run very fast and require low memory, in order for the Monte Carlo simulation to run smoothly. It should only keep the series of 4 actions that have different and valuable results:

* if two series of 4 actions have the same effect except that one requires to discard a card, then the second series must be ignored
* if a series of 4 actions has an effect strictly inferior to the effect of another series, then the first series must be ignored.

I am looking for help regarding the strategy to use to determine all the valuable series of 4 actions, and any algorithm/implementation idea that could improve on my current work.

***What I tried so far***

**The direct approach** Given an action perform all next possible actions on a duplicated game state, store the resulting game states and only keep the series of 4 actions that have different output. Unfortunately, this requires to clone the game state too many times. Plus, it is not optimised: if the first two actions have the same output, there is no need to explore both branches.

**The direct approach optimised** For each action, evaluate the state of the board. Only keep the action that have different outputs. Do it again for each output. This is slightly better, but the game state duplication is still a problem.

**The loop between all possible actions approach** Pre-build the list of all possible series of 4 actions, independently of the board state. Loop through the list and remove series of 4 actions that are not playable. It was too slow, as without game state constraint there are around 1 billion possible series of 4 actions.

**The cancel approach** Similar to the direct approach, but instead of duplicating the game state before performing an action, we perform the action explore the branch, and then cancel it to try another branch. It was a bit better than the other approach, but it's impossible to cut useless branches before reaching the end.

**The delta approach** Each action is associated with a Delta object. When performing two actions the Delta of the 2 actions are added. Only series of 4 actions with different Delta are kept. This solves the game state duplication issue, but is slower to run as in order to make sure that before exploring a branch we need to make sure that after applying the delta of the previous actions to the game state, the branch's action is playable.

**The goal approach** Not yet implemented. It would determine each positive action available on the board (HEAL, BUILD, SHARE KNOWLEDGE) and try to build a series of 4 actions doing those.

# Answer
> 2 votes
Without more details, I think it is important to precise that Pandemic is 2-4 players cooperative game. Players are allowed to discuss about strategy and share any information (even if the rules are ambigous on the possibility to share card in hand information). Moreover to achieve victory efficiently, players have to trade cards which is hard without coordination.

## Type of AI

So first of all, you have to be clear on what you expect for your AI:

* **Global AI**: The AI play for all players and then have no need to predict another player turn. This is the simplest to implement.
* **Independant equivalent AI** : this is nearly the same but with a different paradigm. Every player is managed by a different bot. But they can predict perfectly any other turn.
* **Independant AI** : this is probably your objective as it let a human player participate. But there is a need to predict what it would do or to simulate communication.

## Evaluation function

Now let's talk about the algorithm begining by the evaluation function. As you said, you have to compute the game state resulting of any action you may do. Then to evaluate it to give a score to every action sequence and chose the best.

Computing the full new state may be indeed very time/space consuming. You may probably work with "delta" to the initial state. you have to be able to run you evaluation function on this "delta" state to get a "delta" score.

A tip to treat the 4-action sequence is to first determine all accessible position and their cost in action/card. Then decide what is the best to do with the remaining actions.

Having a good evaluation function is the most important of any game AI. It needs experience and abstraction of the game to model which state changes are likely to lead to victory or defeat. Unfortunatly, Pandemic is a very hard and complex game and you might need experience on simpler games to design a proper evaluation function.

## Prediction algorithm

As you said, if you limit the computation to your 4 next actions, there is no sense to use MCTS. But to have better prediction, you can compute the state resulting of the next players and the random issues.

Generally the depth of the analysis depends on the time you accept to spend to it. Then, optimizing your state computation (with "delta" for instance) let you go far deeper in analysis.

An important feature is to "prune" any unefficient branch as soon as possible. This is typically what you mean with "if two series of 4 actions have the same effect except that one requires to discard a card, then the second series must be ignored". In fact you have to express this feature in term of state score.

Knowing well Pandemic game, I would expect that a decent AI has to predict at least the next turn of every other player. As you can expect, it is no worth to spend a full turn of 4 actions to do the thing that the next player will do in 1 action.

## My advice

Start simple, build a 2 players global AI and assume random card draws are totally predictable. Improve your capacity to do "delta" on state, your MCTS and overall your evaluation function.

## Sequence management

The idea is to first compute all positions in range (a BFS is perfect for this). The "range cost" is expressed in "card(C)/action(A)". A "1C2A" range is actually worse than a "0C2A" range but you may consider 2 ranges if you have for instance "1C1A" and "0C2A".

Thus you have to build a 4-actions sequence, so you have to consider all positions you can go to in 4 actions. On these positions, you will either: \- end you turn (if you used the 4 actions for instance) \- do an useful action (cure, trade, build)

In the first case, you won't move again as it would be equivalent to another direct move of your initial position list. But if you do an action, you may have a subsequent move(/action) needing a 2nd depth level in your exploration tree but with a lower range.

Let's take a simple example. You are at position "O" in this graph:

"B1" \<= "A1" \<= "O" =\> "A2" =\> "B2" =\> "C2" =\> "D2"

There are possible actions only on O (cure), A1 (2 cures), B2 (trade) and C2 (build).

So your first level tree is \[(pos, remaining actions)\]:

**(O, 4), (A1, 3), (A2, 3), (B1, 2), (B2, 2), (C2, 1), (D2, 0)**

if you stay at O, you will at least do an action which is cure before moving again. And you may build the subtree

**(O, 3), (A1, 2), (A2, 2), (B1, 1), (B2, 1), (C2, 0)**

if you go to A2, you won't move again because there is no action to do here and any accessible position is already considered in tree. So you may directly compute the delta score of this state with the delta position of your marker.

If you go to A1, you will do either 1 cure, with a remaining subtree **(A1, 2), (B1, 1), (O, 1), (A2, 0)**, either 2 cures with a remaining subtree **(A1, 1), (B1, 0), (O, 0)**

and so on... Also note that there is no point to use charter (use the card of the origin point to anyway) to go on a position where you can perform no action. It will limit the tree size.

# Answer
> 1 votes
You didn't explain how your solution today works, so it's hard to give any concrete pointers. But more generally, in a Monte Carlo solution, you'll take random steps all the way to a terminal state (win/loss). As you explore more and more nodes, you can start to focus more on promising ones, by having them be more likely to be selected.

In pandemic there are lots of moves that move you closer to a win, but not all the way. You might need to have some kind of heuristic that will also weight nodes higher, e.g. if they have cured *one* disease, that node should probably be more likely to produce a win over where no diseases have been cured.

Also, very specific for pandemic is the deck/stack handling. After a e.g. Epidemic is drawn, the infection discard deck is shuffled *on top* of the draw deck. This is very important to take into consideration when descending into draw nodes of the game tree. E.g. you should only sample from the cards that were placed at the top, not from the whole deck!

---
Tags: algorithms, optimization, board-games, monte-carlo
---


# Question
Title: Learn a system of linear inequalities given solutions
Instead of finding a solution to a system of linear inequalities (`Ax + b >= 0`), I want to find *any* system of linear inequalities that satisfy a set of feasible points and does not satisfy a set of infeasible points. As the image shows, I am given points (either a bunch together or one by one) labelled with in/out, yes/no, or similar binary attribute to know if it should be within the system or not, and I want to find lines that separate these.

There should be some inductive method to fit any number of linear inequalities to satisfy these points. It's important that the output is a system of linear inequalities so it can be used as input into linear programming solvers to find new solutions. I've looked into SVM's but the model seams just to be a hyperplane. Maybe it is for use. A one-layer neural network should do the trick but then the number of lines must be set from start.

There are a few things to add to this problem.

1. We want to keep as few lines as possible, or, we want to assume as little as possible of the "true" data set we do not yet fully know of (as any machine learning algorithm does).
2. For the same reason as 1, we'd like to keep the lines as much "in between" the true and false points (just as SVM's)

# Answer
> 4 votes
I suspect that you can just compute the convex hull of the set of feasible points and, for each edge of the hull, write down the equation of the semi-plane that includes all feasible points and such that the line on its boundary is an extension of the edge segment.

In your example:

---
Tags: machine-learning, linear-programming
---


# Question
Title: If $(h_2(k),m) = 1$ then $h_1(k)+ih_2(k) \bmod{m}$ is a permutation of $0,\ldots,m-1$
The following question appears in Introduction to Algorithms (CLRS):

> Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h\_1(k) + ih\_2(k)) \bmod{m} $. Show that the probe sequence $\langle h(k, 0), h(k, 1), \dots , h(k, m - 1) \rangle$ is a permutation of the slot sequence $(0, 1, \dots , m-1)$ if and only if $h\_2(k) $ is relatively prime to $m$. (Hint: See Greatest Common Divisor (GCD)).

Double hash function uses two hash functions, given that $h(k, i) = (h\_i(k) + ih\_2(k)) \bmod{m} $, such that integer $i$ is $i=0, \dots, m-1$ when we probe in case of collision, so we start first with $i=0$, if there is a collision, then $i=1$ and so on until we find an empty slot. The key $k$ is an integer.

**Attempt**: Relatively prime and co-prime is same thing. So if $h\_2(k) $ is relatively prime to $m$, then $\gcd(h\_2(k), m) = 1$. So, if $h\_2(k)$ and $h\_2(k)$ and $m$ are always co-prime to each other, we can see we always get a number between $h\_2(k) \bmod{m}$ that is in slots $(0, \dots, m-1)$. If $h\_2(k)$ is not relatively prime to $m$, then for the probe sequence $\langle h(k, 0), h(k, 1), \dots , h(k, m - 1)\rangle$, we might get two elements in the probe sequence that are identical to each other. This is how I approached it, so I am not sure how that will prove that $\langle h(k, 0), h(k, 1), \cdots , h(k, m - 1) \rangle$ is a permutation of $(0, 1, \dots , m-1)$ anyway.

# Answer
> 1 votes
Let's write your question more succinctly:

> Let $m \geq 1$ and $a,b$ be integers. The set $S = \\{ a+ib \bmod{m} : 0 \leq i \leq m-1 \\}$ consists of the integers $0,\ldots,m-1$ iff $b$ is relatively prime to $m$.

Note that $S$ consists of the integers $0,\ldots,m-1$ iff the values $a+ib \bmod{m}$ are all distinct.

Suppose first that $b$ is not relatively prime to $m$. This means that we can find $c \> 1$ that divides both $b$ and $m$. It follows that $a \bmod{m} = a + (m/c)b \bmod{m}$, since $(m/c)b$ is a multiple of $m$. Since $1 \leq m/c \leq m-1$, this shows that $S$ contains fewer than $m$ distinct values.

Now suppose that $b$ is relatively prime to $m$. Assume, by way of contradiction, that not all values in $S$ are distinct, say $a+ib \bmod{m} = a+jb \bmod{m}$ for some $i \< j$. Then $(j-i)b \bmod{m} = 0$, where $1 \leq j-i \leq m-1$. This means that $(j-i)b$ is a multiple of $m$. Since $b$ is relatively prime to $m$, this implies that $j-i$ is a multiple of $m$, which is impossible since $1 \leq j-i \leq m-1$.

---
Tags: hash, hash-tables, hashing
---


title: Steps that guarantee exiting a maze

text:
# Question
Title: Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting the maze? I'm looking for a single sequence of commands that will work no matter where in the maze you start from.

Assume that if our partner is given the "move right" command when there's a wall on the right, he will simply stay where he is.

In other words, we're given a maze, and we must choose a sequence of commands. Then, our partner will be placed somewhere in the maze and will follow the sequence of commands we've chosen in advance. We want this sequence to ensure our partner will escape, no matter where our partner was initially placed. Note that the allowable commands do not have any conditional statements, so they cannot follow a different sequence depending on your partner is.

Is there a polynomial-time algorithm to construct such a sequence, given a description of the maze?

Yuval Filmus mentions this is a special case of a synchronizing word problem, and might be related to universal traversal sequences. I also found a paper that seems relevant:

The Simultaneous Maze Solving Problem. Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Unfortunately for general graphs this appears to be a unsolved problem, but I'm wondering if there might be a good algorithm for this specific case. I came up with a candidate approach: Label every position with the number of minimum steps it requires to exit, and keep track of every agent in the maze. It might be possible to do a A\* search this way.

# Answer
One optimal solution for this problem is A\* with iterative deepening (IDA\*) as described in the accepted answer to my puzzle. I am not sure whether IDA\* is a polynomial-time algorithm in general, but the following sheds some light.
> 0 votes

# Answer
An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $A^\*$ (A-star) algorithm, it was originally designed for just such tasks).
> -5 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Visits sequence evaluator in attribute grammar
I am failing to understand the "visits sequence evaluator in attribute grammar". Is it an order on instantiated tree nodes where on each visit to a node we evaluate a particular node and we may end up visiting a node more than once. Is it correct?

There are two paper that describe the visit sequence evaluator:

# Answer
> 1 votes
You don't evaluate nodes in an attribute grammar. You evaluate attributes. At a given node there may be zero or more attributes to evaluate, and they don't necessarily get evaluated on the same visit to the node. So the evaluator may indeed need to visit nodes multiple times.

This theoretical structure corresponds to compilers which do multiple passes over the parse tree. But it also could also apply to an attribute evaluation sequence in which nodes are visited twice: once before their children (in order to compute inherited attributes) and again after their children (in order to compute synthesized attributes). Or multiple times, if some attribute needs to be synthesized from one child before being inherited by a different one. (Whether you count that as multiple visits or not is somewhat dependent on what you think a "visit" is. But it certainly affects how the evaluation code is ordered in the visitor function.)

There is a whole chapter devoted to syntax-directed translation in the dragon book, for what it's worth.

---
Tags: attribute-grammars
---


# Question
Title: How to prove time complexity for this algo?
I have an intuition that this algorithm should have o(n) time complexity but I cannot prove it rigorously.

The question is as follows: Suppose you have an n×n 2-dimensional array A such that each row of the matrix consists of some number of 0s followed by some number of 1s. Describe a method for finding the row with the maximum number of 1s in it. What is the running time of your method? Is it possible to do it in o(n) time? If yes, prove it.

My approach:

The pseudocode is as follows: considering a 0-indexed array

```
col=n-1
while(a[0][col]!=0 and col>=0) col--;
for row in 1...n:
    while(a[row][col]!=0 and col>=0) col--;
    if(col==0) break;

```

Now I can say that from the perspective of moving along column, we are moving only O(n) steps, so complexity is O(n). But I cannot prove it properly. Please help.

# Answer
Your intuition is a great starting point. To formalize this, consider denoting by $F(n)$ the number of times the `col--` happens, or equivalently, the total time you waste in the `while` loops.

Notice, that `col` starts with the value of $n$, and can go down to **up to** $0$ with "jumps" of $1$. Its important that we **never** pass $0$, since it now means the total number of times `col--` can ever happen is at most $n$. Thus, $F(n)=O(n)$.

Now, consider the rest of the code. You have to account for the `for` loop, but notice we already counter the `while` loop that is in it with the value of $F(n)$, so we need to calculate the complexity only for any other operations. But clearly, they don't cost us more than $O(n)$ total, and hence we can say that the algorithm has $O(n)$ run-time.

---

I believe this should be formal *enough*. If you want to be even more formal, consider:

1. Actually proving that `col` never goes lower than $0$
2. Writing line numbers in the algorithm, and explaining the total cost of each line (using the same methods as in this proof)
> 2 votes

# Answer
Maybe you could show that these lines last for $O(n)$

```
col=n-1
while(a[0][col]!=0 and col>=0) col--;

```

And the following lines last for another $O(n)$

```
for row in 1...n:
    while(a[row][col]!=0 and col>=0) col--;
    if(col==0) break;

```

And $O(n) + O(n)$ is indeed $O(n)$

The perspective of moving along column is correct, where $n$ is the number of columns
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Why does the BOM consist of two bytes instead of one for example in encoding utf-16
Why does the BOM consist of two bytes instead of one for example in encoding utf-16? Information about the order of bytes can be easily saved on just one byte. Is it because it would be good for the sum of coded bytes to be even?

# Answer
> 6 votes
The BOM started out as an encoding trick. It was not part of Unicode, it was something that people discovered and cleverly (ab)used.

Basically, they found the U+FEFF *Zero width non-breaking space* character. Now, what does a space character that has a width of zero and does not induce a linebreak do at the very beginning of a document? Well, absolutely nothing! Adding a U+FEFF ZWNBSP to the beginning of your document will not change anything about how that document is rendered.

And they also found that the code point U+FFFE (which you would decode this as, if you decoded UTF-16 "the wrong way round") was not assigned. (U+FFFE0000, which is what you would get from reading UTF-32 the wrong way round, is simply illegal. Codepoints can only be maximal 21 bits long.)

So, what this means is that when you add U+FEFF to the beginning of your UTF-16 (or UTF-32) encoded document, then:

* If you read it back with the correct Byte Order, it does nothing.
* If you read it back with the wrong Byte Order, it is a non-existing character (or not a code point at all).

Therefore, it allows you to add a code point to the beginning of the document to detect the Byte Order in a way that works 100% of the time and does not alter the meaning of your document. It is also 100% backwards-compatible. In fact, it is more than backwards-compatible: it actually works as designed even with software that doesn't even know about this trick!

It was only later, after this trick had been widely used for many years that the Unicode Consortium made it official, in three ways:

* They explicitly specified that the code point U+FEFF *as the first code point of a document* is a Byte Order Mark. When not at the beginning of the document, it is still a ZWNBSP.
* They explicitly specified that U+FFFE will never be assigned, and is reserved for Byte Order Detection.
* They deprecated U+FEFF ZWNBSP in favor of U+2060 *Word Joiner*. New documents that have an U+FEFF somewhere in the document other than as the first code point should no longer be created. U+2060 should be used instead.

So, the reason why the Byte Order Mark is a valid Unicode character and not some kind of special flag, is that it was introduced with maximum backwards-compatibility as a clever hack: adding a BOM to a document will *never* change it, and you don't need to do *anything* to add BOM detection to existing software: if it can open the document at all, the byte order is correct, and if the byte order is incorrect, it is guaranteed to fail.

If, on the other hand, you try to add a special one-octet signature, then all UTF-16 and UTF-32 reader software in the entire world has to be updated to recognize and process this signature. Because if the software does not know about this signature, it will simply try to decode the signature as the first octet of the first code point, and the first octet of the first code point as the second octet of the first code point, and further decode the entire document shifted by one octet. In other words: adding the BOM would completely *destroy* any document, unless every single piece of software in the entire world that deals with Unicode is updated before the first document with a BOM gets produced.

However, going back to the very beginning, and to your original question:

> Why does the BOM consist of two bytes

It seems that you have a *fundamental* misunderstanding here: the BOM *does not* consist of two bytes. It consists of *one character*.

It's just that in UTF-16, each code point gets encoded as two *octets*. (To be fully precise: a byte does not have to be 8 bits wide, so we should talk about octets here, not bytes.) Note that in UTF-32, for example, the BOM is not 2 octets but 4 (`0000FEFF` or `FFFE0000`), again, because that's just how code points are encoded in UTF-32.

Note that the BOM is sometimes used even in cases where it is not necessary: for example, UTF-8 has no problems with byte order, since it fully defines it as part of the specification. The same applies to some more obscure formats such as UTF-1, UTF-5, UTF-6, UTF-7, UTF-7,5, UTF-EBCDIC, and so on. Here, a BOM is still sometimes used as a *Unicode signature*, i.e. to signal to a text processor that the document is encoded using a particular transfer encoding.

However, the use as a *Unicode signature* is generally discouraged, as is use of a BOM in cases where byte order can be specified by metadata (e.g. the `charset` parameter in HTTP), is fixed by some specification (e.g. filenames in Windows are always UTF-16LE, no BOM necessary), or can be deduced from the document (JSON does not need a BOM and in fact does not need a charset parameter either, you can always tell by reading the first 4 octets whether it is UTF-8, UTF-16LE, UTF-16BE, UTF-32LE, or UTF-32BE; actually, BOMs are forbidden and charset parameters are discouraged and useless).

# Answer
> 2 votes
There is no guarantee that a file has a Byte Order Marker. For example, JSON documents don't need one at all, no matter what the encoding is (as a little puzzle, figure out how you can determine which Unicode encoding a JSON document is using).

Now if you KNOW there is a single byte BOM, that's easy. But what do you do if you don't know? If the first character in your file just matches the single byte BOM by chance? You're stuck.

Another problem is that you couldn't store data with a single byte BOM into an array of 16 bit integers. That's a bit awful.

# Answer
> 2 votes
In addition to what Jörg W Mittag said:

The Unicode Consortium isn't in the business of defining file formats. I think the original standard didn't even define any encoding of Unicode as a sequence of bytes – that was an implementation detail.

In a sane world, there wouldn't be any need for something like the BOM, because the format of the character data would be determined by metadata provided by the sender and understood by the receiver. But nothing in the software world ever works. Half of the time there's no metadata, and half of the time that there is metadata, it's wrong.

The BOM is the result of the Unicode Consortium trying to deal with a real-world problem while clinging to some semblance of the idea that they're just standardizing a character encoding and not every aspect of text processing.

# Answer
> 1 votes
In UTF-16, information is encoded in units of 2 bytes. Every symbol is encoded using either one unit or two units. BOM uses one unit.

---
Tags: encoding-scheme, binary
---


title: Solving permutation Mastermind

text:
# Question
Title: Solving permutation Mastermind
*This question is inspired by a recent (imo bad) TV show in German television.*

Given two finite sets $A$ and $B$ of same size (representing two groups of people) and a bijective map $m \colon A \to B$ which is unknown (representing a matching).

We also define an oracle $o \colon (A \to B) \to \mathbb N$ which yields for a bijective map $f \colon A \to B$ on how many elements $a \in A$ $f$ agrees with $m$.

Given the following algorithm:

```
r = 1
while True:
  Pick a bijective map f: A -> B
  c = o(f)
  if c == |A|:
    return r
  r = r + 1

```

What is the best strategy to pick $f$?

---

Additionally given a function

$$ check \colon A \times B \to \mathbb B, (a, b) \mapsto \begin{cases} True, & \text{if }m(a) = b \\ False, & \text{else}\end{cases} $$

that might be queried once while picking $f$ in the above algorithm. What's the best strategy now?

# Answer
Your question belongs to the genre of Mastermind puzzles.

In classical generalized Mastermind, the goal is to find a string $x \in \\{1,\ldots,k\\}^n$ using adaptive queries of the following type: given $y \in \\{1,\ldots,k\\}^n$, you are given the number of black pegs (number of positions $i$ such that $x\_i = y\_i$) and the number of white pegs (remove all positions counted by black pegs from both strings; if the number of pegs of color $c$ are $a\_c,b\_c$, respectively, then output $\sum\_c \min(a\_c,b\_c)$). The goal is to minimize the worst-case number of queries.

In your case, $k = n$, the string $x$ has no repetitions, and you are only given access to the number of black pegs ("black-peg only"). In fact, in your setting, you can determine the number of white pegs from the number of black pegs (they sum to $n$), so the restriction to black pegs only is immaterial.

Since there are $2^{\Omega(n \log n)}$ many permutations and each query has $2^{O(\log n)}$ possible answers, there is a trivial $\Omega(n)$ lower bound on the worst-case number of queries. Martinsson and Su, Mastermind with a linear number of queries, give a matching algorithm which uses $O(n)$ queries.

Glazik, Jäger, Schiemann and Srivastav, Bounds for the static permutation Mastermind game, showed that if you have to choose all queries ahead of time, then $\Omega(n\log n)$ queries are required. Larcher, Martinsson and Steger, Solving static permutation Mastermind using $O(n\log n)$ queries, give a matching strategy which uses $O(n\log n)$ non-adaptive queries.

The information-theoretic lower bound in the adaptive setting implies that "most" permutations require $\Omega(n)$ queries, in the sense that any algorithm must use $\Omega(n)$ queries for at least a $p$-fraction of permutations, for any constant $p$. Therefore the average-case complexity is also $\Theta(n)$ in the adaptive setting. I don't know whether the lower bound in the static setting similarly extends.

It seems hopeless to determine *the* optimal strategy (except for small $n$), though perhaps it is possible to determine the leading term (rather than just its rate of growth). Your additional free query does not affect the asymptotics, and so has no effect on the results above.
> 3 votes

---
Tags: algorithms
---


# Question
Title: What are the essential differences and similarities among "data", "Information" and "knowledge" in the context of Computer Science?
The terms "data", "information" and "knowledge" are quite interchangeably used in Computer Science. Strictly speaking, they do carry a very different meaning. I want to know their precise meanings and their context and usage.

According to my limited experience, data is simply "raw fact and figures" whereas information is "meaningful data" and knowledge is information via which one can predict the unknown or infer something new. Please correct me if I am wrong.

# Answer
> 2 votes
All are main topics in Information Science.

**Information**

a) needs Human Being, without Human Being no Information

b) Information can be stored in Data for Computer

**Data**

a) stored Information

b) makes possible that Information can be retrieved by computer as machines

c) can be dead (stored for computer) or living (inside the human Being or any other living organism)

**Knowledge**

Is that Information wich is stored inside Human Being. The biological neuronal organs are Human Nerves and Brain. Philosophical name for it Human Memory.

# Answer
> 1 votes
You're description is pretty accurate. There is no formal definition or precise meaning coming from a high level. There are only formal definitions in specific fields such as information theory for Information (bits) and knowledge such as in cognitive architectures. Data doesn't have a precise meaning either, haven't seen a formal model of that in any case.

---
Tags: database-theory, databases, knowledge-representation
---


# Question
Title: Can you diagonalize a language out of CSL?
In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we could use the LBA and the finite countable set of possible configurations to diagonalize a TM out of this set or something along those lines.

# Answer
This is accomplished by the nondeterministic space hierarchy theory, given that CSL is the same as $\mathsf{NSPACE}(n)$.
> 4 votes

---
Tags: formal-languages, computability, context-sensitive, diagonalization
---


title: Quadratic probing variant scheme

text:
# Question
Title: Quadratic probing variant scheme
Suppose that we are given a key $k$ to search for in a hash table with positions $0, 1, \dots , m-1$, and suppose that we have a hash function $h$ mapping the key space into the set $\\{0, 1, \dots , m-1 \\}$. The search scheme is as follows:

1. Compute the value $i \gets h(k)$, and set $j \gets 0$.
2. Probe in position $i$ for the desired key $k$. If you find it, or if this position is empty, terminate the search.
3. Set $j \gets (j + 1)\bmod{m}$ and $ i \gets (i+j)\bmod{m}$, and return to step 2.

**Question**: Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants $c\_1, c\_2$ for the equation: $$h(k,i) = (h(k) + c\_1i+c\_2i^2) \bmod{m}, \text{ where } i=0,\dots, m-1$$ and $h(k) = k \bmod {m}$.

**Attempt**:

What we did here is to consider $j$ as a for loop and substitute in $i$:

$$i\_0 = h(k), j\_0 = 0$$

If we did not find the item and the termination case is not fulfilled, we probe:

$$i\_1 = h(k) + j\_0 = h(k), j\_1 = j\_0 + 1 = 1$$

If we did not find the item and the termination case is not fulfilled, we probe:

\begin{gather} i\_2 = h(k) + j\_1 = h(k) + 1, j\_2 = j\_1 + 1 = 2 \\ \vdots \\ i\_i = h(k) + j\_1 = h(k) + 1 + \cdots + (i-1), j\_i = i \end{gather}

**Problem**: Now I realized that sequence $1 + \dots + (i-1)$ gives quadratic term, but it's not from $i=0, \dots, i$ so that I can sum all values as one term is missing, which is the $i$th term. What do you think please?

**Problem 2**: Prove that this algorithm examines every table position in the worst case. I would like to ask you here about general approach to solve this question not detailed solution. So, here it's sufficient as I understood to show that for two probing sequences, we won't end up in the same slot and that guarantees that we will examine every single slot in the hash table. Could you please explain if this approach sounds right for you and what would you propose in this case please?

# Answer
> 2 votes
The $i$'th value probed by your algorithm (counting from $1$) is $$ h(k) + 1 + \cdots + i-1 \equiv h(k) + \frac{i(i-1)}{2} \equiv h(k) - \frac{1}{2} i + \frac{1}{2} i^2 \pmod{m}, $$ which is of the required form.

In order to show that you examine every table position in the worst case, you need to show that for each $j \in \\{0,\ldots,m-1\\}$ there exists $i \geq 0$ such that $\frac{i(i-1)}{2} \equiv j \pmod{m}$. This happens to be the case iff $m$ is a power of 2.

Indeed, suppose first that $m$ is odd, and consider the sequence $h(0,0),\ldots,h(0,m-1)$. We have $$ h(0,i) = \frac{i(i-1)}{2} \equiv \frac{(m-i)(m-i+1)}{2} = h(0,m+1-i) \pmod{m}, $$ and so the sequence is palindromic. Since $h(0,i)$ only depends on $i \bmod{m}$, this implies that $h(0,i)$ only goes over $\frac{m+1}{2}$ different values.

If $m$ is not a power of 2, then it has some odd factor $m' \> 1$. If $h(0,i)$ went over all values in $\\{0,\ldots,m-1\\}$, then $h(0,i) \bmod{m'}$ would have gone over all values in $\\{0,\ldots,m'-1\\}$, which we have seen above to be false.

Conversely, suppose that $m$ is a power of 2. If $0 \leq i \< j \< m$ then $$ h(0,j) - h(0,i) \equiv (1 + \cdots + j) - (1 + \cdots + i) \equiv (i+1) + \cdots + j \equiv \frac{(j-i)(i+j+1)}{2} \pmod{m}. $$ Exactly one of $j-i,i+j+1$ is even. Moreover, $1 \leq j-i \leq m-1$ and $2 \leq i+j+1 \leq 2m-2$. Hence after division by 2, none of these can be a multiple of $m$. Thus $h(0,0),\ldots,h(0,m-1)$ are all different, and so they go over all possible values.

---
Tags: algorithms, hash
---


# Question
Title: Is possible applying virtual memory with cloud disk (cloud storage) instead of local disk (SSD/HDD)?
I heard concept of virtual memory is using disk to save temporary progress or data instruction (temporary data). About temporary data, it's main job of physical memory (RAM) so that's mean virtual memory is helping main job of physical memory.

Virtual memory work in software level and hardware level. Even though my major is focus to hardware (Computer System) but i'm still not sure how it works. As far i know, virtual memory is handled by Memory Management Unit in hardware level. While in software level it handled by OS that maybe applying contigous method or non-contigous.

We know that when applying virtual memory the computer using local storage/disk like SSD. SSD is match for virtual memory since R/W speed of SSD is faster than HDD. But how about applying virtual memory with cloud disk instead of local disk? Then it will be interested. We can assume the speed of internet is good enough. I notice i can mount my local PC to google drive, so that's mean can i use them as virtual memory?

# Answer
> 1 votes
Thirty years ago Sun Microsystems was selling diskless workstations that accessed all mass storage (root, user directories, virtual memory / swap) over 10Mbit Ethernet, which is considerably slower than high-speed Internet connections today. Those machines even bootstrapped themselves over the network. So it is certainly possible to have swap disks exist and function in the cloud. Assuming you have a block-level interface to such storage (e.g. a SAN and local support), it should also be straightforward to set up. I struggle to imagine a situation where such a setup would be desirable today, however.

---
Tags: virtual-memory
---


title: Asymptotics of $(6^n-1000)/(2^n+1)$

text:
# Question
Title: Asymptotics of $(6^n-1000)/(2^n+1)$
If $f(n) = 5n^2 + 3n + 7$ can be written as $\Theta(n^2)$, then how to write the following in $\Theta$-notation: $$ \frac{6^n - 1000}{2^n + 1}. $$

# Answer
Each (eventually positive) function is its own $\Theta$; so if you denote your function by $g(n)$, then certainly $g(n) = \Theta(g(n))$.

Usually, what we mean by finding the $\Theta$-complexity of a function $g(n)$ is finding a *simple* function $h(n)$ such that $g(n) = \Theta(h(n))$. In your case, it is not hard to check that $g(n) = \Theta(3^n)$. Indeed, for large $n$ we have $6^n - 1000 \approx 6^n$ and $2^n + 1 \approx 2^n$, hence your expression is roughly equal to $6^n/2^n = 3^n$. This can be made more precise: $$ \frac{6^n - 1000}{2^n + 1} \sim 3^n, $$ in the sense that the ratio of both expressions tends to $1$ as $n \to \infty$.
> 6 votes

# Answer
Since $n\to \infty$ you are free to show $$\frac{6^n - 1000}{2^n + 1}$$ as

$$\Theta\left(\left(\frac{6}{2}\right)^n\right)$$

that means

$$\Theta\left(\left(3\right)^n\right).$$
> 0 votes

---
Tags: asymptotics
---


# Question
Title: How can you apply dynamic connectivity problem to digital photos?
I started learning DSA recently and I came across the Dynamic Connectivity Problem. One of the listed real-world applications of the Dynamic Connectivity Problem is "pixels in digital photos." How do you apply it to photos? What is it used for?

I can understand its usage in a social network or a network of computers but what is its application in digital photos?

# Answer
> 1 votes
The problem manifests when maintaining connectivity data either in edges or objects within the image. For machine vision you might want to increase the reliability of an edge detection algorithm by examining the image at multiple brightness and contrast levels and seeing whether previously edge correlations are reinforced or weakened.

For a series of related images, e.g. video, you might want to track pixel connectivity between images as an aid to compressing the video stream. Compression is essentially the elimination of redundant encodings of data, and tracking which nearby pixels are similar is a necessary first step for some algorithms.

---
Tags: algorithms, digital-image-processing
---


# Question
Title: What is the entropy of an unordered list?
I'm trying to compress *unordered* lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :)

Each integer is 6-digits, so representing such a list naively, let's say we'll allocate a fixed 20 bits per integer, stored in whichever order they happen to be present in, though again, order is irrelevant to the task at hand. For 1,000 integers, that's 1,000 * 20 bits, or 20kb. Baseline established.

Now for the Shannon entropy, we start with:

$$H(x) = -\sum\_{i=1}^n{P(x\_i) \log\_2P(x\_i)}$$

The total set of available integers is the set of all 6-digit integers, or 1,000,000, so $P(x = int)$ for any given choice of $int$ is $\frac{1}{1,000,000}$. Plug it in:

$$H(x) = -\sum\_{i=1}^{1,000,000}{\frac{1}{1,000,000} \log\_2\frac{1}{1,000,000}} = { \log\_21,000,000} = 19.93 \ \textrm{bits}$$

We're back at 20 bits, given that $\log\_2(\textrm{max\_value})$ is how we got 20 bits in the first place. Of course, multiplying by 1,000, we get 20kb again.

This is provably not the true entropy of the list, because one fairly trivial compression scheme is to sort the list, then subtract each element from the next and encode the list as the first integer in the set and the differences between each integer and the one before it.

In that way, this:

$\[123456, 192939, 201202, 203204, 500500\]$

Becomes this, where the longer the list above, the denser the set, and the better the compression:

$\[123456, 69483, 8263, 2002, 297296\]$

If we can trivially compress down to smaller than the entropy, then that pretty clearly proves the calculated entropy is not actually the entropy.

If fact, given that all the differences are guaranteed to have a sum less than 1,000,000, otherwise our last value wouldn't fit in 6 digits, the differences between integers will be $\frac{1,000,000}{\textrm{num\_integers}}$ on average, requiring $\log\_2\frac{1,000,000}{\textrm{num\_integers}}$ bits to store. This compression scheme will compress 1,000 integers down to $1,000 * \log\_2\frac{1,000,000}{1,000} = 9.97 \ \textrm{kilobits}$, setting that as the upper bound on entropy.

**Now that we've shown that applying Shannon's formula in the way I did does not give us the entropy of an unordered list, what does?**

# Answer
> 3 votes
There are $\binom{10^6}{n}$ sets consisting of $n$ distinct 6-digit integers. If you choose such a set at random, then you get a random variable whose entropy is $\log\_2 \binom{10^6}{n}$. This means that you can encode such a set using $\lceil \log\_2 \binom{10^6}{n} \rceil$ many bits. You can obtain such an encoding using ranking/unranking of combinations, see for example this link.

# Answer
> 1 votes
The problem with your first entropy argument is that you're counting each permutation separately, even though you don't care about preserving the order. In particular, every list of $1000$ distinct elements is counted $1000!$ times, so your entropy is too high by around $\frac{1}{1000}\log\_2 1000! \approx 8.5$ bits per element.

The problem with your second argument is that it doesn't follow from the fact that the average value of the differences is $k$ that they can be stored in $\log\_2 k$ bits. If the differences were equidistributed across the range 0-2000 then the average difference would be 1000, but they would require around 11 bits to store, not 10. The distribution is more likely to be Poisson than flat, but you'll still find that the best encoding uses more than 10 bits.

Yuval Filmus's counting is correct if the elements are all distinct. If duplicates are allowed then the count is slightly larger: $\binom{10^6+n-1}{n}$.

---
Tags: sets, information-theory, data-compression, entropy
---


# Question
Title: Is this a mistake in the textbook? Fundamentals of Database Systems 7th ed
> **Aggregation** is an abstraction concept for building composite objects from their component objects. ... the possibility of combining objects that are related by a particular relationship instance into a higher-level aggregate object. This is sometimes useful when the higher-level aggregate object is itself to be related to another object. We call the relationship between the primitive objects and their aggregate object **IS-A-PART-OF**; the inverse is called **IS-A-COMPONENT-OF**. UML provides for all three types of aggregation.

Here in the last sentence "the inverse is called **IS-A-COMPONENT-OF**" is a mistake?. Are "IS-A-COMPONENT-OF" and "IS-A-PART-OF" the same thing? If so what should we call an inverse?

# Answer
> 0 votes
Looks like `IS-A-COMPONENT-OF` is a typo for `IS-COMPOSED-OF`. Except for the former being there & in the index, the 6th doesn't use either of those names.

**PS**

They mean (re `IS-A-PART-OF` & `IS-COMPOSED-OF` \[sic\]) that for the ordered-tuple notion of binary relation (defined as obviously suggested by the variable names),

```
forall part, composite ,
        IS-A-PART-OF(part, composite)
    iff IS-COMPOSED-OF(composite, part)

```

For the unordered tuple notion of binary relation you have one relation (defined as obviously suggested by the attribute names) that you could reasonably call by either name. But a notion of an "inverse" for such a relation involves picking an order for attributes. (Like using functional dependencies that hold.)

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


# Question
Title: Prove: A connected graph contains an Eulerian cycle iff every vertex has even degree
Recently, I am reading the book \[1\]. I am trying to solve the following problem:

> **1.3 Proving Euler's claim.** Euler didn't actually prove that having vertices with even degree is sufficient for a connected graph to be Eulerian--he simply stated that it is obvious. This lack of rigor was common among 18th century mathematicians. The first real proof was given by Carl Hierholzer more than 100 years later. To reconstruct it, first show that if every vertex has even degree, we can cover the graph with a set of cycles such that every edge appears exactly once. Then consider combining cycles with moves like those in Figure 1.8.

---

The following is my attempt to solve the problem:

Let $G$ be a connected graph and every vertex of $G$ has even degree. Let $N\_V$ be the number of vertices in $G$. Let $d\_i$ be the degree of the $i$th vertex for $i = 1, ..., N\_V$. Then $$ d\_i = 2 n\_i \tag{1} $$ for some positive integer $n\_i$, $i = 1, ..., N\_V$. Therefore, by walking on the edges of $G$, we can walk to and leave the $i$th vertex for $n\_i$ times, with each edge being walked on exactly once. Then I don't know how to continue...

I also go to the Internet and find Carl Hierholzer's paper \[2\]. However, it is written neither in English nor Chinese (my mother language), so I can't read it.

Note: It is not my homework. I am just interested in solving this problem.

## References

\[1\] C. Moore and S. Mertens, *The Nature of Computation*, Oxford University Press, 2015.

\[2\] C. Hierholzer. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. *Mathematische Annalen*, **6**:30-32, 1873.

# Answer
> 1 votes
I don't know German either, but here are some of my thoughts based on the hint given.

Case 1: all vertices have even degree.

Take an arbitrary cycle and remove it. In the new graph (not necessarily connected) all the vertices will still have even degree. Repeat this process until all the edges have been eliminated. Glue all the cycles in the way described in the book.

It might not be apparent that such a cycle would exist for any graph in case 1. So we can prove it by contradiction. If the converse was true, there would exist a vertex such that no cycle can pass through it. This would imply that if we cut off one edge that connects such vertex, the new graph would no longer be connected, which is not true given the assumption that every vertex has even degree.

Case 2: Exactly two vertices have odd degree. Find a path connecting the two vertices and remove it, and we are back to case 1.

---
Tags: graphs
---


# Question
Title: What is the intuition behind working of hamming codes
I am trying to understand hamming codes for single bit error correction. I understood all the things like hamming distance , k bit error detection and all basics for hamming codes. Also, I know the algorithm for error correction using hamming codes. I have read many answers from different stackexchange sites and also I fear that this question may be marked as duplicated. But I am not satisfied, I just know a procedure and don't know the intuition behind the idea.

Let's say we need to send a 4-bit message for which three parity bits will be used. Now the sequence will be `p1 p2 m3 p4 m5 m6 m7` and my instructor is saying that `p1` will be responsible for detecting errors in bits `( 1 , 3 , 5 , 7 )` , `p2` for `( 2 , 3 , 6 , 7 )` and `p4` for `( 4 , 5 , 6 , 7 )`. Why is it so?

Why only $2^n$ position bits are selected for parity? How to visualize its working?

# Answer
> 3 votes
Hamming codes are designed to correct a single error. A valid codeword $p\_1 p\_2 m\_3 p\_4 m\_5 m\_6 m\_7$ satisfies the constraints \begin{align} &p\_1 \oplus m\_3 \oplus m\_5 \oplus m\_7 = 0 \\ &p\_2 \oplus m\_3 \oplus m\_6 \oplus m\_7 = 0 \\ &p\_4 \oplus m\_5 \oplus m\_6 \oplus m\_7 = 0 \end{align} (This is arranged simply by choosing $p\_1 = m\_3 \oplus m\_5 \oplus m\_7$, and similarly for $p\_2,p\_4$).

If a single error occurs in one of the positions $1,3,5,7$, then the first parity check will fail. Similarly, if a single error occurs in one of the positions $2,3,6,7$ then the second parity check will fail, and if a single error occurs in one of the positions $4,5,6,7$ then the third parity check will fail. Each single error is associated with a different pattern of failed parity checks, and this allows us to locate the error and correct it.

More generally, a Hamming code of length $2^n-1$ has $2^n-n-1$ message bits and $n$ parity checks, and is able to detect and correct one error. These parameters are optimal, in the sense that if a code has $m$ message bits, $n$ parity checks and is able to correct one error, then $m \leq 2^n - n - 1$. To see this, let $w\_1,\ldots,w\_{2^m}$ be all possible codewords. Let $B(w\_i)$ consists of $w\_i$ together with all words obtained by flipping a single bit. Given a word in $B(w\_i)$, we can detect whether any error occurred, and if so, fix it, recovering $w\_i$. This shows that the balls $B(w\_i)$ are disjoint from one another. Each one contains $1 + (m + n)$ words, and so the union of all balls contains $2^m (1 + m + n)$ words. Since every word has length $m + n$, the number of possible words is $2^{m + n}$, resulting in the inequality $$ 2^m (1 + m + n) \leq 2^{m + n}, $$ or $1 + m + n \leq 2^n$, that is, $m \leq 2^n - n - 1$.

For general $n$, the parity checks of Hamming codes are constructed as follows. Number the positions of the bits from $1$ to $2^n-1$, and think of them as words of length $n$ over $\\{0,1\\}$ different from $0\cdots0$. For $i = 0,\ldots,n-1$, we have a parity check stating that the XOR of all bits at indices $\ell \in \\{0,1\\}^n$ satisfying $\ell\_i = 1$. We choose indices $2^0,2^1,\ldots,2^{n-1}$ as parity bits (the analogs of $p\_1,p\_2,p\_4$ above), and the rest as message bits. We can calculate the parity bits from the message bits as above.

If we start with a codeword and flip the bit at position $\ell$, then the $i$th parity check will fail iff $\ell\_i = 1$. This enables us to correct the error, since its position is spelled out by the parity checks.

---
Tags: hamming-code, hamming-distance
---


title: VCdim of concentric circles

text:
# Question
Title: VCdim of concentric circles
I have researched this topic in the last time, but no usefull results for me. So I'm here and I please you to help me with the following problem:

What is $VCdim$($\mathcal{H}$), where $\mathcal{H}$ is the class of concentric circles centred in origin in the 2D plane?

# Answer
You haven't explained what you mean by *circle*. Let me consider three possible interpretations:

1. The set of points at distance *exactly* $r$ from the origin, for some $r$.
2. The set of points at distance *at most* $r$ from the origin, for some $r$.
3. The set of points at distance *less than* $r$ from the origin, for some $r$.

In all cases, it is easy to see that the concept class shatters any single point except, possibly, the origin. In contrast, we can show that no set of two points is shattered, and so the VC dimension is 1. Indeed, if $x,y$ are at the same distance from the origin and $C$ is an origin-centered circle, then $x \in C$ iff $y \in C$, and so $\\{x,y\\}$ is not shattered. If $x$ is closer to the origin from $y$, then in case 1, no origin-centered circle contains both, and in the other two cases, no origin-centered circle contains $y$ but not $x$; in all cases, $\\{x,y\\}$ is not shattered.
> 1 votes

---
Tags: machine-learning, vc-dimension
---


# Question
Title: Turing machines which halt after updating a cell for the second or third time
We say that a Turing machine is *fragile*, if it halts after changing the symbol of one of the tape cells for the third time. Is it true that every language that is solvable on a Turing machine will be solvable on a fragile Turing machine?

What can we say about Turing machines which stop after changing the symbol of one of the tape cells for the *second* time?

# Answer
If the Turing machine is allowed to update each cell twice (or even once, see Hendrik Jan's comment), then you can use the following strategy to simulate an arbitrary Turing machine $T$ using a fragile Turing machine $T'$. For each step of $T$, the contents of the tape of $T$ will appear in some part of the tape of $T'$, with the head position highlighted. To simulate a step of $T$, the machine $T'$ copies the current contents of the tape of $T$ to the right of the current position, while modifying it in the process to implement the step of $T$. If implemented carefully, each cell is only updated twice.
> 2 votes

---
Tags: turing-machines, computability
---


# Question
Title: Consequences of a polytime algorithm for a decision problem reducible to 3SAT
If there is a polynomial time algorithm for a decision problem $A$, which is m-reducible to 3SAT, and 3SAT is NP-complete, does this prove that P=NP?

# Answer
> 3 votes
The problem $A = \emptyset$ is polytime reducible to 3SAT (using a reduction running in constant time), and can be solved in polynomial time.

More generally, any problem in P is polytime reducible to 3SAT and can be solved in polynomial time.

---
Tags: np-complete, np, complexity-classes
---


# Question
Title: In search of finding an idea that work in $o(n^3)$
Suppose given an array $A\[1..n^2\]$ that contains positives real values. Also we have a black box that have two input numbers $a,b$ and return true or false, also i know that, for any input, the black box return true for at least one pair. The goal is, we find two vales $a,b\in A$ such that $a+b$ minimized also the black box return true. Note that, each time i use the black box, it cost will be $O(n^2)$.

A simple brute force algorithm is as follow:

We check number of ways choose two numbers from $A$ (i.e. $\binom{n^2}{2}$) and give them to black box. The running time will be $O(n^6)$ that isn't efficient.

Are there an idea that work in $o(n^3)$? Or proof that show us the lower bound $\Omega(n^3)$?

# Answer
You didn't specify if $a$ and $b$ can be the same element or if the black box is allowed to return different answers on inputs $a,b$ and $b,a$ therefore I'm going to conservatively assume that the both the above things are not allowed.

Let $m=n^2$. You need at least $\frac{m(m-1)}{2} - 1 = \Omega(m^2) = \Omega(n^4)$ queries to the black box in the worst case. If this was not the case then it is possible that: (i) all values in $A$ are distinct, and (ii) all the answer from all the queried pairs were "false". Since there are at least two distinct unordered pairs of unqueried elements, your algorithm cannot decide which of them to return.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Finding maximum clique given, for each edge, union of all cliques containing it
For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U\_{e}$ of the edges of all cliques that contain $e$.

Can we determine, in polynomial time, for a given edge $e\_{0}\in E$, the size of the maximum clique that contains $e\_{0}$?

# Answer
> 1 votes
The sets $U\_e$ can be computed in polynomial time. In fact, if $e = \\{x,y\\}$, then $U\_e$ consists of the following edges:

* $\\{x,y\\}$
* For each $z$ such that $x,y,z$ is a clique, the edges $\\{x,z\\},\\{y,z\\}$.
* For each $z,w$ such that $x,y,z,w$ is a clique, the edge $\\{z,w\\}$.

To see this, note first that $U\_e$ contains all of these edges by definition. Conversely, let $e'$ be some edge in $U\_e$. There are three possibilities:

* $e' = \\{x,y\\}$.
* $e' = \\{x,z\\}$ for some $z \neq y$ (the case $e' = \\{y,z\\}$ for some $z \neq x$ is similar). In this case, there is some clique containing both edges $\\{x,y\\}$ and $\\{x,z\\}$. This clique contains the vertices $x,y,z$, and in particular, $x,y,z$ is a clique.
* $e' = \\{z,w\\}$ for some $z,w \neq x,y$. In this case, there is some clique containing both edges $\\{x,y\\}$ and $\\{z,w\\}$. The clique contains the vertices $x,y,z,w$, and in particular, $x,y,z,w$ is a clique.

Finally, notice that the size of the maximum clique containing the edge $\\{x,y\\}$ is the two plus size of the maximum clique in the subgraph of $G$ induced by the common neighbors of $x$ and $y$. Conversely, given a graph $H$, we can adjoin two new vertices $x$ and $y$ connected to one another and to the rest of the vertices, obtaining a graph $G$ in which the size of the maximum clique containing $x$ and $y$ is two plus the size of the original graph $H$.

Putting everything together, we see that your problem is solvable in polynomial time iff P=NP.

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


# Question
Title: One-tape Turing machine for doubling words (strings)
I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape Turing machine that give exactly XX as its output? For example, X=abba, XX=abbaabba. Thank you in advance for consideration.

# Answer
> 1 votes
Design a Turing machine $T$ that takes as an input a word with an unique occurrence of the "@" symbol and shifts all symbols after "@" one position to their left (thus overwriting "@" and replacing the last symbol of the word with the blank symbol).

This can be done by finding the end of the input word, setting the machine state to store the "blank" symbol, moving to the left, and then iteratively performing the following step:

* simultaneously store the current symbol in the machine state, write the stored symbol on the current cell of the tape, and move left.

The above repeats until the read symbol is "@". When that happens the stored symbol is written in place of "@" and the machine halts.

Compose the Turing machine you already designed with $T$.

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


# Question
Title: Minimum spanning tree where weights of edges are intersecting sets
Given Graph $G=(V, E)$, where each edge in $E$ is assigned a "weight" as a set of elements. $w(e) = S\_e \ \forall e \in E$.

Find a subset $E' \subset E$ such that it spans $G$, i.e., $E'$ connects all pairs of nodes $n\_1, n\_2 \in V$ through some path, such that its "total weight", the size of the union of all of its member's weights is minimized:

$$\min\_{E'} \ \ w(E') = \left|\bigcup\_e S\_e\right|$$

# Answer
The problem is NP-hard even when all sets have at most (or exactly) one element. This can be seen by a reduction from (the decision version of) vertex cover. Given graph $H$, you can build the graph $G=(V,E)$ by starting with a graph containing a single vertex $s$ and doing the following for each $e=(u,v)$ of $H$:

* Add three new vertices to $G$ namely $x\_e, y\_e$ and $z\_e$.
* Add the edge $(y\_e, x\_e)$ with "weight" $S\_{(y\_e, x\_e)}=\\{u\\}$.
* Add the edge $(y\_e, z\_e)$ with "weight" $S\_{(y\_e, z\_e)}=\\{v\\}$.
* Add the edges $(s, x\_e)$ and $(s, z\_e)$, both with "weight" $\emptyset$.

Let $E'$ be an optimal solution to your problem on $G$. I clam that $S=\bigcup\_{e \in E'} S\_e$ is a vertex cover of $H$. Indeed, suppose that there is some edge $e=(u,v)$ of $H$ that is not covered by $S$. This means that $\\{u,v\\} \cap S = \emptyset$ implying $(y\_e, x\_e) \not\in E'$ and $(y\_e, z\_e) \not \in E'$. Since $(y\_e, x\_e)$ and $(y\_e, z\_e)$ are the only edges incident to $y\_e$ in $G$, we conclude that $E'$ does not induce a spanning tree of $G$.

On the other hand, if $S$ is a vertex cover for $H$ then there exists a solution $E'$ to your problem with measure at most $|S|$. Simply select $E'$ as any spanning tree of the the subgraph of $G$ induced by the union of (i) all the edges incident to $s$, and (ii) all edges $e=(y\_e, u)$ with $S\_e \cap S \neq \emptyset$.

Here is an example (solid vertices form a vertex cover of $H$, bold edges induce a MST of $G$).

If you want all sets to have cardinality $1$ you can change the "weight" of the edges $(s, x\_e)$ and $(s, z\_e)$ from $\emptyset$ to $\\{s\\}$ and slightly modify the above arguments.
> 3 votes

---
Tags: optimization, sets, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Efficient random sampling from large discrete distribution
I have a random variable $X$ that can take finite values in $\\{X\_1, ..., X\_n\\}$ with probabilities $\\{p\_1,..., p\_n\\}$. Is there a computationally efficient way to sample a number from this set? My problem is that $n$ is very large $2^{1000}$. Also the distribution is quite arbitrary - not uniform or something nice.

**Context:** The probabilities are the path probabilities of a 2 state Markov Chain. So in time period $n$, there are $2^n$ paths and I need to sample 100 paths from this set when $n = 1000$

# Answer
> 1 votes
If the probabilities are arbitrary I don't think you can get away with using less than $\Omega(n)$ space. Then there are solutions that use $O(n)$ space, require $O(n)$ preprocessing time, and can return an element selected according to the distribution in constant time.

Have a look at the Alias method.

---
Tags: time-complexity, statistics, sampling
---


# Question
Title: Are there problems in NP that do not reduce in polynomial time to any problem in NP?
As the title says: are there problems in $\mathbf{NP}$ that **do not reduce** in polynomial time to any problem in $\mathbf{NP}$?

# Answer
I understand the question as asking for the truth value of the proposition $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP}, A \not\le\_p B$, where $\le\_p$ denotes Karp reducibility.

Then the answer is no since, $\forall A \in \mathsf{B}$ we can pick $B=A$ and the choose the identity function as the Karp reduction from $A$ to $B$. In other words every problem in $\mathsf{NP}$ is Karp-reducible to itself.

Even if you want $A$ and $B$ to be distinct then the answer is still no. Formally, we want to know the truth value of $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP} \setminus \\{A\\}, A \not\le\_p B$.

Indeed, for $\forall A \in \mathsf{NP}$, there exists some $B \in \mathsf{NP} \setminus \\{A\\}$ such that $A \le\_p B$. Let $\sigma \in \Sigma$. An example of such $B$ is $\\{ \sigma x \mid x \in A \\}$, and the corresponding Karp reduction is $f(x) = \sigma x$.
> 11 votes

# Answer
The definition of the class **NP-hard** is that a problem is NP-hard if every problem in NP can be reduced to it in polynomial time.

The definition of the class **NP-complete** is just the problems that are NP-hard which are also themselves members of NP.

Therefore, since there exist members of NP-complete, the answer to your question is no, there are no problems in NP which cannot be reduced to any other problem in NP in polynomial.

In fact you can pick any one of those NP-complete problems, and there is no NP problem that cannot be reduced to that single problem of your choice.
> 3 votes

# Answer
Only NPC (NP-Complete) problems have such property they're reducible to each other in polynomial time, and a solution can be verified in polynomial time.

-For example, how can you transform a sorting instance into a Minimum Spanning Tree instance (both in P)?! Doesn't even make sense

You can search and find huge material on NPC, however this can give you a brief on the big picture

https://youtu.be/EeACNt50Wf4

A clarifying Venn diagram

Sometimes NPC are called the *Hardest Problems* as compared to those in NP-Hard

Remarks:

1-I removed the medium Venn diagram, I'm very sorry it contained wrong info, factorization, primality are considered NP-Hard in the no. of bits in the number; here is an example of a problem (IsPrime?) where verifying the correctness of a solution have the same complexity as finding the solution

2- While I was searching for a Venn diagram image to put, I found there are previous answers in the group

How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

What is the definition of P, NP, NP-complete and NP-hard?

From MIT lecture 2020 on complexity classes, you can watch from min44 https://youtu.be/JbafQJx1CIA

I understand that other answers address the question from the *Theory of Computation* point of view not from *Algorithms Design & Analysis*; however I still believe, at least from my view, that it's different in meaning whether they're (NP) each independently polynomial reducible to *an easy instance of an NP-Hard problem* or to each other, only NPC problems have that property otherwise why stated separately???

& If factorization was in P there would have been no RSA at all & many other things. It's claimed polynomial only thru Quantum Computing.
> -4 votes

---
Tags: np, polynomial-time
---


# Question
Title: What is the regular expression for the language, {w | w does not contain the substring 11}
{w | w does not contain the substring 11}

What I am thinking: $(0^\* 1 0^\* )^\*$ Is anything wrong with my expression?

Thanks in advance for your help!

# Answer
$0^\*$ will generate any number of repetitions of $0$, and will also generate the empty string $\epsilon$.

So, the problem with your expression is that $11$ is also accepted, since we can write it as $$11=(\epsilon 1\epsilon) (\epsilon 1 \epsilon)\in (0^\*10^\*)(0^\*10^\*)\subseteq(0^\*10^\*)^\*$$ To fix this problem, use the $0^+$ operator instead, which acts just like $0^\*$ except that it doesn't generate $\epsilon$. Or, if you don't want to use it, you can explicitly write $00^\*$ instead since $0^+=00^\*$

---

Additionally, you will need only one $0^+$ and not two of them (since then it means you won't generate $0$ for example). Think about where it should go!

---

Also, as @Janmar pointed out in the comments, you will also want to include words that contain $0$'s but no $1$'s. Its not hard to do, so I believe you wont need my help doing it
> 2 votes

---
Tags: complexity-theory, computability, finite-automata, regular-expressions
---


# Question
Title: Formal proof of existence of equivalent parse tree for each derivation
Where I can find formal proof of there exists an equivalent parse tree for each derivation? There is a lot of informal proof of equivalency on the internet but I need formal proof to reference it in a paper.

# Answer
Proposition 6.11

*Full manuscript*: https://www.cis.upenn.edu/~jean/gbooks/tocnotes.html

> Definition 3.11.2: Given a context-free grammar $G = (V, \Sigma, P, \> S)$, for any $A \in N$, if $\pi: A \stackrel{n}{\implies} \alpha$ is a derivation in $G$, we construct an *A-derivation tree* $t\_\pi$ with yield $\alpha$ as follows.
>
> 1. if $n = 0$, then $t\_\pi$ is the one-node tree such that $dom(t\_{\pi}) = \\{ \epsilon \\}$ and $t\_{\pi}(\epsilon) = A$
> 2. if $A \stackrel{n-1}{\implies} \lambda B \rho$ and if $t\_1$ is the A-derivation tree with yield $\lambda B \rho$ associated with the derivation $A \stackrel{n-1}{\implies} \lambda B \rho$, and if $t\_2$ is the tree associated with the production $B \rightarrow \gamma$ that is, if $\gamma = X\_1 \dots X\_n$,
>
> then $dom(t\_2) = \\{ \epsilon, 1, \dots, k \\}$, $t\_2(\epsilon) = B$, and $t\_2(i) = X\_i$ or all $i$, $1 \leq i \leq k$, of if $\gamma = \epsilon$
>
> then $dom(t\_2) = \\{ \epsilon, 1 \\}$, $t\_2(\epsilon) = B$, and $t\_2(1) = \epsilon$,
>
> then $t\_{\pi} = t\_1\[u \gets t\_2\]$, where $u$ is the address of the leaf labeled $B$ in $t\_1$.
>
> The tree $t\_{\pi}$ is the *A-derivation tree associated* with the derivation $A \stackrel{n-1}{\implies} \alpha$.

>
> 0 votes

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


# Question
Title: Topological sort where some nodes can't come in between two other nodes
I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node X or node Y. In other words, Y \< X OR Z \< Y.

I've thought about several approaches to this, but can't find a solution. Maybe I can turn every NonBetween relation into "regular edges" and then do a standard topological sort?

Have you heard of any similar problem or solution to this?

# Answer
> 1 votes
The decision version of your problem of deciding whether the DAG contains such an order is NP-complete, even if all (X,Y,Z)s are disjoint. It is proven in Appendix B in \[1\].

\[1\] Guttmann, W., & Maucher, M. (2006). Constrained ordering.

# Answer
> -1 votes
EDIT: As pointed out in the comments this doesn't work!

Copy your graph into $G'$ and for every triple of nodes $(u,v,w)$, if NotBetween$(u,v,w)$ then add the edges $v\rightarrow u$ and $w\rightarrow v$ to $G'$ (if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph $G'$ is a valid topo sort for $G$ respecting NotBetween.

This is clearly $O(V^3)$ because you can implement this with 3 nested loops, then resulting graph has at most $O(V^2)$ edges, and the topological sort of $G'$ will take time $O(V^2)$.

If your relation NotBetween is not a black box and actually has some "known shape" you might be able to skip some triples and do better.

---
Tags: algorithms, graphs, np-hard, combinatorics, open-problem
---