# Question
Title: What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?
I am currently studying the paper Primes is in P and have a question regarding 5 section of this paper. Line 1 of the algorithm (on page 3) requires the following operation to be performed

```
if (n = a^b for some natural numbers a and b), output 'composite'

```

I have attempted to deduce the complexity of this line and have deduced the following. Assuming $n \geq 2$, $b$ must be bounded above by $\lceil \log\_2 (n) \rceil$. Thus, if there exists $a,b \in \mathbb{N}$ such that $a^b = n$ then $n^\frac{1}{b}$ must be an integer. Thus, to test whether such values of $a$ and $b$ exist, we must check whether $$ n^\frac{1}{x} $$ is an integer for each $2 \leq x \leq \lceil \log\_2 (n) \rceil$. This requires a maximum of $\lfloor \log\_2 (n) \rfloor$ operations to be performed, so the complexity of this step (according to my likely incorrect analysis) would be $O(\log\_2 (n))$.

However, on page 6 of the paper it says that the complexity of this step is $O^\sim (\log^3(n))$. Why is this?

Note that this question regards the specific complexity of this operation, rather than simply verifying that it is doable in polynomial time (which was done here).

# Answer
The complexity very much depends on whether you are looking at the worst case, or at the average case when you choose n at random.

To find whether $n^{1/b}$ is an integer, you could pre-calculate the set of possible integers $(a^b) \mod k$ for various k, and check whether $n \mod k$ is among those values - if not then $n^{1/b}$ is not an integer. If n is chosen at random, then this will eliminate many cases very quickly.

You can numerically calculate $n^{1/b}$ and check if it is an integer. If you calculate this value with (log n / b + 20) bits precision, and n was chosen at random, then your chance is 99.9999% that you can prove it is not an integer - this will fail if the result *is* an integer or close to one. There is a clever method doing the calculation using quadratically convergent Newton iteration involving only multiplications and additions / subtractions. Since only the last step requires the full precision, and the calculation involves raising numbers to powers b which is done in log b multiplications, this can be done in $O ({(\log n)^2 \over b^2} * \log b)$ steps using naive multiplication, and $O ((\log n / b) * \log (\log n / b) * \log b)$ using FFT. For random n, most of the time this is all that is needed.

It is possible that we find $n^{1/b}$ rounded to the nearest integer and cannot prove that $n^{1/b}$ is not an integer. In these cases we may have to calculate $a^b$. Again, only the final product needs full precision, so this is done in $O(log^2 n)$ using naive multiplication, or $O (log n log log n) using FFT.
> 2 votes

# Answer
It is true that the search for $b$ leads to a loop with $O(\log n)$ iterations. But for a given $b$ you also have to find the corresponding $a$. So, how much time do we need for that?

I would try binary search. With $k:=\frac{\log n}b$, observe that the number of digits of $a$ is $O(k)$. So is the number of iterations of the binary search. Raising a candidate $a$ to the $b$-th power requires a loop of length $O(\log b)$. In the $i$-th iteration of said loop, we are muliplying $2^ik$-bit numbers. Which can be done in $O(2^ik\log(2^ik)\log\log(2^ik))$ time. Let's bound that as $O(2^ik(i+\log k)\log\log\log n)$. The full loop of length $O(\log b)$ then takes $O(bk(\log b+\log k)\log\log\log n)$ time. The binary search thus takes time $O(bk^2(\log b+\log k)\log\log\log n)$, which we bound by $O((\log n)^2\frac1b\log\log n\log\log\log n)$. The loop involving $b$ means summing $\frac1b$ up to $\log n$ resulting in $O(\log\log n)$.

So the overall running time is $O((\log n)^2(\log\log n)^2\log\log\log n)$. Which gives a better upper bound than $O((\log n)^3)$ but is also messier. Maybe the paper assumed a less sophisticated multiplication algorithm. Or maybe they deliberately traded bound tightness for simplicity. (Which, by the way, I may also have done above with regard to sums of lesser terms. For example, for summing I bounded $\log\log(2^ik)$ by $\log\log(2^{\log b}k)$.)
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, primes
---


# Question
Title: Construct a pushdown automaton for $\{a^{2n}b^{3n}|n\ge0\}$
My idea is to (not formal) push an 'a' when we see an a, nondeterministically guess when n a's were seen from the input word, go to the next state. From there, when we see an a, push 2 'a's into the stack and again guess when n a's were seen (now there should be 3n 'a's in the stack) and go to the final state, where if we see a b, we pop from the stack. So the stack will be empty in the last state iff we saw 3n b's.
The problem that with this line of thought we can construct an automaton for$\\{a^{n}b^{n}c^n|n\ge0\\}$. So where am i wrong in this thinking?

# Answer
Your PDA accepts the language $$ \\{a^{i+j} b^{i+2j} : i,j \geq 0 \\}, $$ which is different from the one you are interested in. In fact, you can show that it equals $$ \\{a^kb^\ell : k \leq \ell \leq 2k \\}. $$
> 1 votes

---
Tags: automata, context-free, pushdown-automata
---


# Question
Title: Getting negative cycle using Bellman Ford
I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name it.

How can I get the actual path $v1, v2, \ldots vk, v1$ of the cycle?

After applying the standard algorithm we already did $n-1$ iterations and no further improvement should be possible. If we can still lower the distance to a node, a negative cycle exists.

My idea is: Since we know the edge that can still improve the path and we know the predecessor of each node, we can trace our way back from that edge until we meet it again. Now we should have our cycle.

Sadly, I did not find any paper that tells me if this is correct. So, does it actually work like that?

**Edit:** This example proofs that my idea is wrong. Given the following graph, we run Bellman-Ford from node $1$.

We process edges in the order $a, b, c, d$. After $n-1$ iterations we get **node distances:**
$1: -5$
$2: -30$
$3: -15$

and **parent table:**
$1$ has parent $3$
$2$ has parent $3$
$3$ has parent $2$

Now, doing the $n$th iteration we see that the distance of node $1$ can still be improved using edge $a$. So we know that a negative cycle exists and $a$ is part of it.

But, by tracing our way back through the parent table, we get stuck in another negative cycle $c, d$ and never meet $a$ again.

How can we solve this problem?

# Answer
You are right for the most part. Just one more addition. When you go back the predecessor chain when trying to find the cycle, you stop when you either reach the starting vertex $v\_1$ or any other vertex that has already been seen in the predecessor chain that you have seen so far. Basically, you stop and output vertices whenever you detect a cycle when going backwards using the predecessors.

As for papers, a simple Google search yields Xiuzhen Huang: *Negative-Weight Cycle Algorithms*. As a bonus, they also list another algorithm for finding negative weight cycles that are *not* reachable from the source vertex $s$.
> 17 votes

# Answer
Your example does not contradict your idea. Indeed you have found a negative cycle. I think the idea your example illustrates is that the source vertex might not be a node in the negative cycle.
> 0 votes

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


# Question
Title: A tree which each node selected as a root results in a different topology?
Show that, for every n \>= 7, there exists a tree of n non-labeled nodes such that picking each of the n nodes as a root results in a different rooted tree.

# Answer
Here is a hint. If the tree has size $\> 1$ it will have to have a vertex with degree $\ge 3$ as otherwise it would be in a line and the two ends would be equivalent. So consider a tree with a vertex having 3 branches out of it. The branches will have to have different lengths or the end vertices of equal length branches would be equivalent.

What's the smallest number of vertices in a tree of that form? Can you see how to expand the tree maintaining the required property?

---

Also note that this approach proves that the sizes of trees having the mentioned property are 1 and $\ge 7$.
> 2 votes

---
Tags: graphs, trees
---


# Question
Title: The relationship between degree and the number of leaves of a tree?
What is the relationship between $\text{deg}(T)$ and the number of leaves of $T$, if $T$ is a tree?

# Answer
> 0 votes
As you said the degree of a tree, probably $T$ is a rooted tree. Hence, the relation between the number of leaves $n$ is $\text{deg}(T) \leq n$, as each child of the root is terminated to at least one leaf

---
Tags: graphs, trees, network-topology
---


title: Scheduling Algorithm for Video Player

text:
# Question
Title: Scheduling Algorithm for Video Player
**Background:**
In a nutshell. I coded a video player application (on linux). I used a proprietary library/API, with this, video and audio frames comes with well defined format. After decoding (via API), I call scheduling() function for video and audio frames and library does the rest. For argument sake I oversimplified the example.

Now let's say we switched to open source API (like Libav) with this I have everything similar as before except scheduling functions.

**The Question:**

***Short Version:***
I need help to devise a scheduling algorithm to use in my video player.

***Long Version:***
I have video frames and audio frames with timestamps (can be converted to wallclock time via a simple function). Naive approach I did was, rendering frames same order immediately as they arrive. This looks like working but overtime lips sync problem occurs (as expected). I don't quite get it what scheduling function I used before actually doing and since these are closed source (comes as pre-compiled) I can't check it.

**Notes:**
The original function takes these parameters (if these give some idea/help):

`theFrame` in frame to display
`displayTime` in time at which to display the frame in `timeScale` units
`displayDuration` in duration for which to display the frame in `timeScale` units
`timeScale` in time scale for `displayTime` and `displayDuration`

I have all of this parameters/values for each frame.

**Update:**
*What is a scheduling algorithm supposed to do?*
What I know is, Scheduling algorithm buffers frames and outputs (video or audio) on scheduled time.

*What are its outputs?*
Audio and video uses different function but basically does same thing. It outputs video or audio. Simplest terms you see the video and hear audio on the player application thanks to this function correctly in sync.

*What are the requirements?*
1) Frame to output (video or audio). i.e. YUV Frame Buffer or a PCM packet for audio.
2) Timestamp (stamped on encoder side). i.e. 64bit signed integer, after simple conversion function gives a wall clock kinda time (HH:MM:SS.ms).
3) Timing information (stream time\_base and frame duration) i.e. time\_base for video : 1(num)/50(den=framerate), duration is tricky let's say it's 1/framerate secs (20 ms in this example)

*What is the "overtime lips sync problem"?*
Video and audio goes out of sync. In other words, video and audio doesn't match anymore.

What I'm asking is a generic logic for a Scheduling Algorithm, I don't wanna bore with you with details, so I kept is simple.

**Let me ask different way:**

Think I have a file (like a SRT subtitle file) it has text on every line and timestamp. And I wanna print it on linux terminal line by line according to it's timestamps.

My naive thinking will be:
1) Start a timer when program starts, load the file (SRT) on the memory.
2) Parse lines and timestamps.
3) Find the line with (in the SRT) closest to our timer and print it.
4) Repeat step (3) until EOF

In my original question/problem, I can't load whole media file, it can be a live stream or very big file. I can only buffer few seconds worth of frames (i.e. 25 frames (each for video or audio)).

So what should I do ?

# Answer
> 1 votes
If frames are stored in order:

Read the next frame. Delay until the time when you are supposed to display it. Display it. Repeat.

If the timestamp is in the past, you can either display that frame now and immediately read the next frame, or you can drop that frame and display the next frame.

If frames are not stored in order:

Store the frames in a priority queue, with the time when it is supposed to be displayed as the key. Then, repeat the following: extract the next frame from the priority queue (a DeleteMin operation), wait until the time when you are supposed to display it, display it, then repeat.

Or, just sort the frames by the time when they are supposed to appear and apply the simple algorithm at the beginning of my answer.

---
Tags: scheduling, video
---


# Question
Title: Explicit algorithms and algorithms involving unknowns
Let's assume the you have two algorithms for computing some single but complicated number (e.g., the Ramsey number $R(5,5)$). Both are provided as high-level, half-formal textbook descriptions.

1. The first algorithm, by means of some textual reformatting and filling in the usual gaps in high-level reasoning, can be easily (say, within several days of coding) turned into a (relatively large) computer program in some imperative programming language, including that of Turing machines (provided appropriate tooling support, of course).
2. The second algorithm can almost be turned into code in some imperative programming language, except there are some unknown constants (e.g., the algorithm contains an assignment "$x := c^2$", where $c$ is nonconstructively defined by Theorem 5.19.38, which says $\exists\\,c\in \mathbb{N}\colon\dots$). In the best case, this algorithm has some merits such as creating a connection to some other area of mathematics, and in the worst case, this algorithm is simply "'print $r$;', where $r$ is the constant $R(5,5)$". We know that the second algorithm solves our task, i.e., that a Turing machine corresponding to our high-level description exists, but we don't know some part of this algorithm *exactly*.

**In mathematical writing**, how do you call these algorithms when you provide the reader with them? I mean, how do you distinguish between them? Do you say explicit/nonexplicit? Effective/noneffective? Any other pair of terms?

# Answer
Personally, I would call the first one an algorithm, and I would call the second a non-constructive proof of the existence of an algorithm. But it probably doesn't matter all that much what you call it, exactly, as long as you are explicit and clear about what you mean.

Related: https://en.wikipedia.org/wiki/Non-constructive\_algorithm\_existence\_proofs, https://cstheory.stackexchange.com/q/12162/5038.
> 2 votes

---
Tags: algorithms, terminology
---


# Question
Title: Is writing a compiler for a compact language easier?
I am contemplating the project of writing a compiler. I am wondering if, aside from the availability of easy google results, it is easier to write a compiler for a more explicit/verbose language such as ada, compared to a very compact language such as APL, for example.

I should add that i am especially interested in whole-program optimization.

Edit: my question boils down to "do highly abstracted symbols/keywords (as in APL, where a single operator represents a function) make it easier to write a compiler, or is a language with a more traditional syntax (where a function includes a variety of operators) easier?"

# Answer
> 7 votes
In almost every case, the more compact languages like APL will be harder write a compiler for:

* On the front end (parser), in the worst case, you have a ton bunch of special cases for your symbols in your parser, and in the best case, you treat them as generic symbols, in which case you're in the exact same parsing position as a language that has
* In the back-end, with type checking, optimizers, etc., you either treat your symbols as standard library functions, in which case you're in the *exact* same place as a more verbose language, or you treat them as parts of the language, in which case you will have a bunch of special cases in your type checker, code generation, etc.

In general, compilers are easiest for smaller languages. This is why most languages feature *syntactic sugar*, where some features are translated into a subset of your original language at compile time (for example, eliminating for-loops by turning them into while-loops). Many languages also keep code-generation and optimization simpler by compiling their language into a smaller *intermediate language* after parsing or type checking, then optimizing and compiling that language into machine code.

> I should add that i am especially interested in whole-program optimization.

Syntax will not influence this *in the slightest*. Parsing is generally the least interesting part of writing a compiler, since there's many solutions for parsing, and once you have things into an Abstract Syntax Tree, what concrete syntax you used is entirely irrelevant. That is, two languages that parse to isomorphic ASTs will be exactly the same for difficulty to optimize.

The only case where having a more compact language could help optimization is if you have a bunch of special cases of known optimizations (e.g. fusion rules) for your operators, but you could just as easily write special cases for standard library functions of a more verbose language.

# Answer
> 0 votes
Writing compiler for simple language like Lisp or APL, is simpler. First, you have to deal with less amount of syntax rules. Second, you have to develop code generators for less types of AST nodes. APL is particularly easy - it have only a few rules, and most of the code generation is just sequential function calls since it has no operation priorities.

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


# Question
Title: Data structure or algorithm for quickly finding differences between strings
I have an array of 100,000 strings, all of length $k$. I want to compare each string to every other string to see if any two strings differ by 1 character. Right now, as I add each string to the array, I'm checking it against every string already in the array, which has a time complexity of $\frac{n(n-1)}{2} k$.

Is there a data structure or algorithm that can compare strings to each other faster than what I'm already doing?

Some additional information:

* Order matters: `abcde` and `xbcde` differ by 1 character, while `abcde` and `edcba` differ by 4 characters.
* For each pair of strings that differ by one character, I will be removing one of those strings from the array.
* Right now, I'm looking for strings that differ by only 1 character, but it would be nice if that 1 character difference could be increased to, say, 2, 3, or 4 characters. However, in this case, I think efficiency is more important than the ability to increase the character-difference limit.
* $k$ is usually in the range of 20-40.

# Answer
> 12 votes
It's possible to achieve $O(nk \log k)$ worst-case running time.

Let's start simple. If you care about an easy to implement solution that will be efficient on many inputs, but not all, here is a simple, pragmatic, easy to implement solution that many suffice in practice for many situations. It does fall back to quadratic running time in the worst case, though.

Take each string and store it in a hashtable, keyed on the first half of the string. Then, iterate over the hashtable buckets. For each pair of strings in the same bucket, check whether they differ in 1 character (i.e., check whether their second half differs in 1 character).

Then, take each string and store it in a hashtable, this time keyed on the *second* half of the string. Again check each pair of strings in the same bucket.

Assuming the strings are well-distributed, the running time will likely be about $O(nk)$. Moreover, if there exists a pair of strings that differ by 1 character, it will be found during one of the two passes (since they differ by only 1 character, that differing character must be in either the first or second half of the string, so the second or first half of the string must be the same). However, in the worst case (e.g., if all strings start or end with the same $k/2$ characters), this degrades to $O(n^2 k)$ running time, so its worst-case running time is not an improvement on brute force.

As a performance optimization, if any bucket has too many strings in it, you can repeat the same process recursively to look for a pair that differ by one character. The recursive invocation will be on strings of length $k/2$.

If you care about worst-case running time:

With the above performance optimization I believe the worst-case running time is $O(nk \log k)$.

# Answer
> 15 votes
My solution is similar to j\_random\_hacker's but uses only a single hash set.

I would create a hash set of strings. For each string in the input, add to the set $k$ strings. In each of these strings replace one of the letters with a special character, not found in any of the strings. While you add them, check that they are not already in the set. If they are then you have two strings that only differ by (at most) one character.

An example with strings 'abc', 'adc'

For abc we add '\*bc', 'a\*c' and 'ab\*'

For adc we add '\*dc', 'a\*c' and 'ad\*'

When we add 'a\*c' the second time we notice it is already in the set, so we know that there are two strings that only differ by one letter.

The total running time of this algorithm is $O(n\*k^2)$. This is because we create $k$ new strings for all $n$ strings in the input. For each of those strings we need to calculate the hash, which typically takes $O(k)$ time.

Storing all the strings takes $O(n\*k^2)$ space.

**Further improvements**

We can improve the algorithm further by not storing the modified strings directly but instead storing an object with a reference to the original string and the index of the character that is masked. This way we do not need to create all of the strings and we only need $O(n\*k)$ space to store all of the objects.

You will need to implement a custom hash function for the objects. We can take the Java implementation as an example, see the java documentation. The java hashCode multiplies the unicode value of each character with $31^{k-i}$ (with $k$ the string length and $i$ the one-based index of the character. Note that each altered string only differs by one character from the original. We can easily compute the contribution of that character to the hash code. We can subtract that and add our masking character instead. This takes $O(1)$ to compute. This allows us to bring the total running time down to $O(n\*k)$

# Answer
> 7 votes
I would make $k$ hashtables $H\_1, \dots, H\_k$, each of which has a $(k-1)$-length string as the key and a list of numbers (string IDs) as the value. The hashtable $H\_i$ will contain all strings processed so far *but with the character at position $i$ deleted*. For example, if $k=6$, then $H\_3\[ABDEF\]$ will contain a list of all strings seen so far that have the pattern $AB\cdot DEF$, where $\cdot$ means "any character". Then to process the $j$-th input string $s\_j$:

1. For each $i$ in the range 1 to $k$:
    * Form string $s\_j'$ by deleting the $i$-th character from $s\_j$.
    * Look up $H\_i\[s\_j'\]$. Every string ID here identifies an original string that is either equal to $s$, or differs at position $i$ only. Output these as matches for string $s\_j$. (If you wish to exclude exact duplicates, make the value type of the hashtables a (string ID, deleted character) pair, so that you can test for those that have had the same character deleted as we just deleted from $s\_j$.)
    * Insert $j$ into $H\_i$ for future queries to use.

If we store each hash key explicitly, then we must use $O(nk^2)$ space and thus have time complexity at least that. But as described by Simon Prins, it's possible to represent a series of modifications to a string (in his case described as changing single characters to `*`, in mine as deletions) implicitly in such a way that all $k$ hash keys for a particular string need just $O(k)$ space, leading to $O(nk)$ space overall, and opening the possibility of $O(nk)$ time too. To achieve this time complexity, we need a way to compute the hashes for all $k$ variations of a length-$k$ string in $O(k)$ time: for example, this can be done using polynomial hashes, as suggested by D.W. (and this is likely much better than simply XORing the deleted character with the hash for the original string).

Simon Prins's implicit representation trick also means that the "deletion" of each character is not actually performed, so we can use the usual array-based representation of a string without a performance penalty (rather than linked lists as I had originally suggested).

# Answer
> 2 votes
Here is a more robust hashtable approach than the polynomial-hash method. First generate $k$ random positive integers $r\_{1..k}$ that are coprime to the hashtable size $M$. Namely, $0 \le r\_i \< M$. Then hash each string $x\_{1..k}$ to $(\sum\_{i=1}^k x\_i r\_i ) \bmod M$. There is almost nothing an adversary can do to cause very uneven collisions, since you generate $r\_{1..k}$ on run-time and so as $k$ increases the maximum probability of collision of any given pair of distinct strings goes quickly to $1/M$. It is also obvious how to compute in $O(k)$ time all the possible hashes for each string with one character changed.

If you really want to guarantee uniform hashing, you can generate one random natural number $r(i,c)$ less than $M$ for each pair $(i,c)$ for $i$ from $1$ to $k$ and for each character $c$, and then hash each string $x\_{1..k}$ to $(\sum\_{i=1}^k r(i,x\_i) ) \bmod M$. Then the probability of collision of any given pair of distinct strings is exactly $1/M$. This approach is better if your character set is relatively small compared to $n$.

# Answer
> 2 votes
A lot of the algorithms posted here use quite a bit of space on hash tables. Here's an $O(1)$ auxiliary storage $O((n \lg n) \cdot k^2)$ runtime simple algorithm.

The trick is to use $C\_k(a, b)$, which is a comparator between two values $a$ and $b$ that returns true if $a \< b$ (lexicographically) while ignoring the $k$th character. Then algorithm is as follows.

First, simply sort the strings regularly and do a linear scan to remove any duplicates.

Then, for each $k$:

1. Sort the strings with $C\_k$ as comparator.
2. Strings that differ only in $k$ are now adjacent and can be detected in a linear scan.

# Answer
> 1 votes
Two strings of length *k*, differing in one character, share a prefix of length *l* and a suffix of length *m* such that *k=l+m+1*.

The answer by Simon Prins encodes this by storing all prefix/suffix combinations explicitly, i.e. `abc` becomes `*bc`, `a*c` and `ab*`. That's k=3, l=0,1,2 and m=2,1,0.

As valarMorghulis points out, you can organize words in a prefix tree. There's also the very similar suffix tree. It's fairly easy to augment the tree with the number of leaf nodes below each prefix or suffix; this can be updated in O(k) when inserting a new word.

The reason you want these sibling counts is so you know, given a new word, whether you want to enumerate all strings with the same prefix or whether to enumerate all strings with the same suffix. E.g. for "abc" as input, the possible prefixes are "", "a" and "ab", while the corresponding suffixes are "bc", "c" and "". As it obvious, for short suffixes it's better to enumerate siblings in the prefix tree and vice versa.

As @einpoklum points out, it's certainly possible that all strings share the same *k/2* prefix. That's not a problem for this approach; the prefix tree will be linear up to depth k/2 with each node up to k/2 depth being the ancestor of 100.000 leaf nodes. As a result, the suffix tree will be used up to (k/2-1) depth, which is good because the strings have to differ in their suffixes given that they share prefixes.

\[edit\] As an optimization, once you've determined the shortest unique prefix of a string, you know that *if* there's one different character, it must be the last character of the prefix, and you'd have found the near-duplicate when checking a prefix that was one shorter. So if "abcde" has a shortest unique prefix "abc", that means there are other strings that start with "ab?" but not with "abc". I.e. if they'd differ in only one character, that would be that third character. You don't need to check for "abc?e" anymore.

By the same logic, if you would find that "cde" is a unique shortest suffix, then you know you need to check only the length-2 "ab" prefix and not length 1 or 3 prefixes.

Note that this method works only for exactly one character differences and does not generalize to 2 character differences, it relies one one character being the separation between identical prefixes and identical suffixes.

# Answer
> 1 votes
Storing strings in buckets is a good way (there are already different answers outlining this).

An alternative solution could be to store strings in a *sorted* list. The trick is to sort by a locality-sensitive hashing algorithm. This is a hash algorithm which yields similar results when the input is similar\[1\].

Each time you want to investigate a string, you could calculate its hash and lookup the position of that hash in your sorted list (taking $O(log(n))$ for arrays or $O(n)$ for linked lists). If you find that the neighbours (considering all close neighbours, not only those with an index of +/- 1) of that position are similar (off by one character) you found your match. If there are no similar strings, you can insert the new string at the position you found (which takes $O(1)$ for linked lists and $O(n)$ for arrays).

One possible locality-sensitive hashing algorithm could be Nilsimsa (with open source implementation available for example in python).

\[1\]: Note that often hash algorithms, like SHA1, are designed for the opposite: producing greatly differing hashes for similar, but not equal inputs.

Disclaimer: To be honest, I would personally implement one of the nested/tree-organized bucket-solutions for a production application. However, the sorted list idea struck me as an interesting alternative. Note that this algorithm highly depends on the choosen hash algorithm. Nilsimsa is one algorithm I found - there are many more though (for example TLSH, Ssdeep and Sdhash). I haven't verified that Nilsimsa works with my outlined algorithm.

# Answer
> 1 votes
One could achieve the solution in $O(nk+ n^2)$ time and $O(nk)$ space using enhanced suffix arrays (Suffix array along with the LCP array) that allows constant time LCP (Longest Common Prefix) query (i.e. Given two indices of a string, what is the length of the longest prefix of the suffixes starting at those indices). Here, we could take advantage of the fact that all strings are of equal length. Specifically,

1. Build the enhanced suffix array of all the $n$ strings concatenated together. Let $X = x\_1.x\_2.x\_3 .... x\_n$ where $x\_i, \forall 1 \le i \le n $ is a string in the collection. Build the suffix array and LCP array for $X$.
2. Now each $x\_i$ starts at position $(i-1)k$ in the zero-based indexing. For each string $x\_i$, take LCP with each of the string $x\_j$ such that $j\<i$. If LCP goes beyond the end of $x\_j$ then $x\_i = x\_j$. Otherwise, there is a mismatch (say $x\_i\[p\] \ne x\_j\[p\]$); in this case take another LCP starting at the corresponding positions following the mismatch. If the second LCP goes beyond the end of $x\_j$ then $x\_i$ and $x\_j$ differ by only one character; otherwise there are more than one mismatches.

```
for (i=2; i<= n; ++i){
    i_pos = (i-1)k;
    for (j=1; j < i; ++j){
        j_pos = (j-1)k;
        lcp_len = LCP (i_pos, j_pos);
        if (lcp_len < k) { // mismatch
            if (lcp_len == k-1) { // mismatch at the last position
            // Output the pair (i, j)
            }
            else {
              second_lcp_len = LCP (i_pos+lcp_len+1, j_pos+lcp_len+1);
              if (lcp_len+second_lcp_len>=k-1) { // second lcp goes beyond
                // Output the pair(i, j)
              }
            }
        }
    }
}

```

You could use SDSL library to build the suffix array in compressed form and answer the LCP queries.

***Analysis:*** Building the enhanced suffix array is linear in the length of $X$ i.e. $O(nk)$. Each LCP query takes constant time. Thus, querying time is $O(n^2)$.

***Generalisation:*** This approach can also be generalised to more than one mismatches. In general, running time is $O(nk + qn^2)$ where $q$ is the number of allowed mismatches.

If you wish to remove a string from the collection, instead of checking every $j\<i$, you could keep a list of only 'valid' $j$.

# Answer
> 1 votes
One improvement to all the solutions proposed. They all require $O(nk)$ memory in the worst case. You can reduce it by computing hashes of strings with `*` instead each character, i.e. `*bcde`, `a*cde`... and processing at each pass only variants with hash value in certain integer range. F.e. with even hash values in the first pass, and odd hash values in the second one.

You can also use this approach to split the work among multiple CPU/GPU cores.

# Answer
> 0 votes
This is a short version of @SimonPrins' answer not involving hashes.

Assuming none of your strings contain an asterisk:

1. Create a list of size $nk$ where each of your strings occurs in $k$ variations, each having one letter replaced by an asterisk (runtime $\mathcal{O}(nk^2)$)
2. Sort that list (runtime $\mathcal{O}(nk^2\log nk)$)
3. Check for duplicates by comparing subsequent entries of the sorted list (runtime $\mathcal{O}(nk^2)$)

An alternative solution with implicit usage of hashes in Python (can't resist the beauty):

```
def has_almost_repeats(strings,k):
    variations = [s[:i-1]+'*'+s[i+1:] for s in strings for i in range(k)]
    return len(set(variations))==k*len(strings)

```

# Answer
> 0 votes
I work everyday on inventing and optimizing algos, so if you need every last bit of performance, that is the plan:

* Check with `*` in each position independently, i.e. instead of single job processing `n*k` string variants - start `k` independent jobs each checking `n` strings. You can spread these `k` jobs among multiple CPU/GPU cores. This is especially important if you are going to check 2+ char diffs. Smaller job size will also improve cache locality, which by itself can make program 10x faster.
* If you are going to use hash tables, use your own implementation employing linear probing and ~50% load factor. It's fast and pretty easy to implement. Or use an existing implementation with open addressing. STL hash tables are slow due to use of separate chaining.
* You may try to prefilter data using 3-state Bloom filter (distinguishing 0/1/1+ occurrences) as proposed by @AlexReynolds.
* For each i from 0 to k-1 run the following job:
    + Generate 8-byte structs containing 4-5 byte hash of each string (with `*` at i-th position) and string index, and then either sort them or build hash table from these records.

For sorting, you may try the following combo:

* first pass is MSD radix sort in 64-256 ways employing TLB trick
* second pass is MSD radix sort in 256-1024 ways w/o TLB trick (64K ways total)
* third pass is insertion sort to fix remaining inconsistencies

# Answer
> 0 votes
Here is my take on 2+ mismatches finder. Note that in this post I consider each string as circular, f.e. substring of length 2 at index `k-1` consists of symbol `str[k-1]` followed by `str[0]`. And substring of length 2 at index `-1` is the same!

If we have `M` mismatches between two strings of length `k`, they have matching substring with length at least $mlen(k,M) = \lceil{k/M}\rceil-1$ since, in the worst case, mismatched symbols split (circular) string into `M` equal-sized segments. F.e. with `k=20` and `M=4` the "worst" match may have the pattern `abcd*efgh*ijkl*mnop*`.

Now, the algorithm for searching all mismatches up to `M` symbols among strings of `k` symbols:

* for each i from 0 to k-1
    + split all strings into groups by `str[i..i+L-1]`, where `L = mlen(k,M)`. F.e. if `L=4` and you have alphabet of only 4 symbols (from DNA), this will make 256 groups.
    + Groups smaller than ~100 strings can be checked with brute-force algorithm
    + For larger groups, we should perform secondary division:
        - Remove from every string in the group `L` symbols we already matched
        - for each j from i-L+1 to k-L-1
            * split all strings into groups by `str[i..i+L1-1]`, where `L1 = mlen(k-L,M)`. F.e. if `k=20, M=4, alphabet of 4 symbols`, so `L=4` and `L1=3`, this will make 64 groups.
            * the rest is left as exercise for the reader :D

Why we don't start `j` from 0? Because we already made these groups with the same value of `i`, so job with `j<=i-L` will be exactly equivalent to job with i and j values swapped.

Further optimizations:

* At every position, also consider strings `str[i..i+L-2] & str[i+L]`. This only doubles amount of jobs created, but allows to increase `L` by 1 (if my math is correct). So, f.e. instead of 256 groups, you will split data into 1024 groups.
* If some $L\[i\]$ becomes too small, we can always use the `*` trick: for each i in in `0..k-1`, remove i'th symbol from each string and create job searching for `M-1` mismatches in those strings of length `k-1`.

---
Tags: algorithms, data-structures, program-optimization, comparison
---


# Question
Title: What are good resources for self teaching parallel/concurrent/multithreaded programming techniques?
I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use in {insert specific technology}.

# Answer
> 1 votes
IMHO the best way to learn parallelism/concurrency is to learn how it is done in FP languages and then look for the ways to do the same in {your beloved one}. My own list:

---
Tags: reference-request, parallel-computing, concurrency
---


# Question
Title: Testing graph property on enumerated graphs
I wanted to verify some graph properties on all possible graph enumerations (or graphs satisfying certain properties). There is a list of all the graphs upto 10 vertices here, but that is not sufficient for my use.

So I had two questions:

1. Which would be the most user friendly and RAM efficient program/library to work with graphs, if I already have the graph with me.
2. What would be an easy and efficient way to generate graphs satisfying certian conditions. I tried to search about Nauty over net but it is difficult to find a tutorial.

# Answer
If you need to generate graphs, you can look at nauty: this is useful if you want to check whether a claim holds for all $n$-vertex graphs up to some small $n$. If you fancy planar graphs, you can have a look at plantri. I would not be surprised if you don't find tutorials, since this type of software is usually intended for professional researchers (but generally speaking, you should have little trouble in compiling and running if you are familiar with the typical Unix-like software).

To answer question 2, you can find online (via the nauty homepage, for instance) collections of small graphs with certain properties. House of Graphs is also pretty nice, but not exhaustive. If the properties you care about are exotic enough, you will have to come up with your own generator and/or just discard the graphs that don't satisfy your property from some collection of all small graphs.

To answer question 1, again, if you need efficiency, it will hard to beat something like nauty and its many utility programs. These are quite well-optimized and thoroughly used pieces of software. If you insist on more user friendliness at the expense of efficiency, I can recommend Mathematica. More generally, it is often the case you will have to write your own programs to strike the right balance between usability and efficiency.

There are also automated systems for suggesting conjectures, particularly in graph theory. One system I have successfully used is GraPHedron \[1\], but note that the system is currently unavailable. There are similar systems out there, and you should find pointers from \[1\] and the later papers that cite it.

---

\[1\] Mélot, Hadrien. "Facet defining inequalities among graph invariants: the system GraPHedron." Discrete Applied Mathematics 156.10 (2008): 1875-1891.
> 2 votes

---
Tags: graphs, enumeration
---


# Question
Title: Proof of the undecidability of the Halting Problem
I'm having trouble understanding the proof of the undecidability of the Halting Problem.

If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ for both $a$ and $b$?

Why can't we feed $H()$ with $P$ and some arbitrary input, say, $x$?

# Answer
> 29 votes
The proof aims to find a contradiction. You have to understand what the contradiction derived is, in order to understand why $P$ is used as an input to itself. The contradiction is, informally: if we have a machine H(a, b) that decides "a accepts b", then we can construct a machine that accepts machines that do not accept themselves. (Read that a few times until you get it.) The machine shown in the picture – let's call it $M$ – $M(P) = $ does $P$ not accept $\langle P \rangle$?

The contradiction happens when you ask: does $M$ accept $\langle M \rangle$? Try to work out the two options to see how there is a contradiction.

$M$ accepts $\langle M \rangle$ if and only if $M$ does not accept $\langle M \rangle$; this is clearly a contradiction.

This is why it is essential for the proof to run $P$ on itself not some arbitrary input. This is a common theme in impossibility proofs known as diagonal arguments.

# Answer
> 44 votes
Ignore the picture for a moment; we'll get to it shortly. The program $H(a, b)$ is supposed to be a halt tester: when we give $H$ an input of a program $a$ (think of $a$ as the listing of a program) and anything at all for $b$, $H(a, b)$ acts as follows

1. If the program represented by $a$ halts when given $b$ as input, $H(a, b)$ will answer "yes". On the other hand, if the program described by $a$ runs forever when given input $b$ then $H(a, b)$ will answer "no".
2. Importantly, program $H$ will always halt and give the correct answer for *any* pairs $(a, b)$.

The argument that $H$ is impossible to build relies on the action of a particular "perverse" program, $P$, one which uses $H$ as a subroutine. $P$ takes as its input a listing of any program, $x$, and does the following:

```
P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

```

It's not hard to see that

> $P(x)$ will halt if and only if the program $x$ will run forever when given its own description as an input.

So far so good: $P$ will certainly be a program *as long as* its subroutine $H$ is a program.

Now return to the picture. What happens if $P$ is given *its own description* as input? The picture describes just that scenario: Let $p$ be the description of program $P$, then, substituting into the highlighted part above, we'll have

> $P(p)$ will halt if and only if the program $P(p)$ will run forever.

Clearly, this paradoxical behavior is impossible, so we're forced to the conclusion that the subroutine $H$ cannot be a halt tester, since it fails in the one case, where it's given $(p, p)$ as input. There might be other cases where $H$ works as it should, but since $H$ fails in at least one situation, it cannot be a complete halt tester, as required.

# Answer
> 9 votes
Try a prettier proof with animations. And since ansewrs should contain more than just a link to a site, here's the answer to your question.

First, let us recall how the proof of non-existence of the Halting oracle works. We prove that given any candidate `H` for a Halting oracle, there is a program `P` and an input `a` for which `H` fails to predict correctly what `P(a)` does.

**Theorem:** Let `H` be any program which takes *two* inputs and always returns either `halt` or `loop`. Then there exists a program `Q` and an input `a` such that `Q(a)` halts if, and only if, `H(Q,a)` returns `loop`.

*Proof.* Consider the program

```
program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

```

Let`Q = P` and `a = P`. Either `H(Q,a) = halt` or `H(Q,a) = loop`:

* if `H(Q,a) = halt` then `Q(a)` (which is just `P(P)`) runs forever by the definition of `P`.
* if `H(Q,a) = loop` then `Q(a)` halt by the definitoin of `P`.

*QED*

You asked why we considered `H(P,P)` instead of `H(P,X)` for some other `X`. The obvious answer is "because `H(P,P)` is what makes the proof work"! If you used `H(P,X)` for some arbitrary `X`, then you would get stuck. Indeed, the proof would then look like this:

*Broken proof.* Consider the program

```
program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

```

Let`Q = P` and `a = X` for some arbitrary `X`. Either `H(Q,X) = halt` or `H(Q,X) = loop`:

* suppose `H(Q,X) = halt` then we cannot tell what `P(X)` does, because whether `P(X)` halts depends on what `H(X,X)` returns. We are stuck. However, if we knew that `P(X)` and `X(X)` are the same, we could make progress. (So, we really should take `X = P`).
* if `H(Q,a) = loop` then we are stuck again, and we would be unstuck if `X = P`.

*No QED.*

I hope this shows that we must consider `H(P,P)` in order to make our idea work.

# Answer
> 4 votes
The upshot of the proof is this analogy:

*If a person $P$ claims s/he$\_{(P)}$ can recognize the sentiment of every person $P^{\prime}$ when s/he$\_{(P^{\prime})}$ sees something, then ask the claimant $P$ to emulate the **opposite** of that sentiment in everyone s/he$\_{(P)}$ sees. And then put her/him$\_{(P)}$ in front of a mirror. S/he$\_{(P)}$ will just not know what sentiment to express*.

The subscripts $\_{(P)}$ and $\_{(P^{\prime})}$ are used to disambiguate the pronouns.

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


# Question
Title: Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori
Given N items you want to put into a tree, think very generally here like a phone tree, and your goal is to keep the tree from getting "too wide" and "too deep". How many children (K) do you put at each node?

I seem to recall hearing of some proof, many years ago, K was best when set to Euler's number. Therefore in real applications if you must choose a single number you pick 3 children and the tree should end up closely balanced between depth and width. In other words, binary trees tend to be too deep, and 5-trees are "too wide".

Some searching of the 'net and reading some tree designs on Wikipedia has not proved fruitful but perhaps I am dreaming up a false memory?

# Answer
> 3 votes
This sounds as follows.

* The **answer** is that the optimal number of children in a tree is $e$. What was "optimal" in the **question**?

One such question is as follows.

* Let us construct a tree of $N$ nodes. Imagine we arrange them into a perfect $K$-ary tree with $L$ levels of internal vertices. When we search over such tree, assume that the worst case is that we visit $K$ vertices in each of the $L$ internal levels, making the search $O (K \cdot L)$. What is the optimal $K$ as $N$ tends to infinity?

Here, we select $K$, and then $L$ is computed as $log\_K N$.

When we think about it a bit, here is an arithmetic rephrase.

* We have a number $N$. We want to express some integer $M \ge N$ as a product of integers $S\_1 \cdot S\_2 \cdots S\_L$ so that the sum $S\_1 + S\_2 + \ldots + S\_L$ is minimal possible. When $N$ tends to infinity, what will be the sequence $\\{S\\}$?

The values $S\_1, S\_2, \ldots, S\_L$ are the number of children at levels $1, 2, \ldots, L$, respectively. If we had a perfect $K$-ary tree, all our $S\_i$ would be equal to $K$, but we lifted the restriction that they are all equal: the essence of the solution remains the same.

When we don't insist that $N$ and $S\_i$ are integers, after performing some basic calculus, we can see that the optimal answer is to pick all $S\_i$ close to $e$. Note that the closest integer to $e$ is $3$. So for the integer version, the optimal answers turn out to be of the following forms: $$(3 \cdot 3 \cdots 3)$$ $$(3 \cdot 3 \cdots 3) \cdot 2$$ $$(3 \cdot 3 \cdots 3) \cdot 2 \cdot 2$$

# Answer
> 0 votes
I found this paper that talks about size-balance k-ary trees. Maybe you'll find it helpful.

Paper citation:

CHA, S. (2012). On Complete and Size Balanced k-ary Tree Integer Sequences. *INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND INFORMATICS,* *6*(2), 8-8. Retrieved April 14, 2015, from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.352.3650&rep=rep1&type=pdf

# Answer
> 0 votes
If we want to have same depth as width in the menu system, we will want to have a tree with $K$ nodes in each menu, and have have $K$ depth. If all the data resides on leaves then we need to solve $K^K \geq n \> (K-1)^{K-1}$. We can solve this using Lambert function. Solving $x^x = y$.

---
Tags: data-structures, trees
---


# Question
Title: What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?
> For language $L$, we have $\forall\varepsilon \> 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$?

It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $L\in\mathcal{O}(\lg(n))$ or $L\in\mathcal{O}(\mathrm{polylog}(n))$?

# Answer
Define $$A := \bigcap\_{\varepsilon \> 0} O(n^\varepsilon) = \bigcap\_{i \in \mathbb{N}} O(n^\frac{1}{i}).$$ This complexity class is analogous to $$B := \bigcap\_{i \in \mathbb{N}} \Omega(n^i),$$ the class of super-polynomial functions, in the sense that if $f$ is strictly increasing, $f \in A \Leftrightarrow f^{-1} \in B$. There isn't a "nice" description of $B$ so you wouldn't expect a "nice" description of $A$.

Note that $e^\sqrt\[i\]{n} \in B$ so $\log^i n \in A$.
> 3 votes

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


# Question
Title: Meaning of $\mu t$ terms in dependent type theory
What is the meaning of the term $\mu t$ in the type theory formalized in this paper (section 2.1, page 2)?

# Answer
> 3 votes
The term `μ t` is the application of a closure `μ` to a term `t`. Similar to how `t t'` is the application of a term `t` to `t'`.

---
Tags: type-theory, dependent-types
---


# Question
Title: What is the current state of the art in solving the halting problem?
Yes, I know it's uncomputable in the general case. What I want to know is what *special* cases have been solved, and if there is work ongoing on finding or developing more of them.

To be a little more explicit about the sort of thing I'm looking for, total functional language compilers have to approximate the halting problem, proving that your source code terminates or saying it can't thus prove it. Idris, as far as I can tell, just uses a "one argument must be structurally smaller on each recursive call" primitive-recursion checker\*; Isabelle is more sophisticated, with

```
datatype rosetree = Rose "'a rosetree list"

primrec rosemap :: "('a => 'b) => 'a rosetree => 'b rosetree" where
  "rosemap f (Rose as) = Rose (map (rosemap f) as)"

```

compiling fine despite the intermediate `map` on the recursive calls. Isabelle's `fun` mechanism seems even more powerful in terms of proving termination (although I can't think of a short, simple example for that off the top of my head).

Basically: how do these work? Are there papers or textbooks about the algorithms involved somewhere? Is finding heuristics for the halting problem a current research subject?

\*If I'm wrong about this, please do let me know about that, too.

# Answer
> 1 votes
The question as asked is indeed very broad. I give a brief answer here: What are some comparative studies on program termination verification tools?, but that really barely scratches the surface.

I do have several remarks:

* In general, once must distinguish between **whole program analyses**, which are powerful, but do not scale very well for realistic development, and **modular analyses** which are weaker, but have hope of being integrated in a development environment. Isabelle and Idris both take this approach. As a side note, I'm not sure if this Fuhs *et al* paper corresponds to the "out of the box" termination check for Isabelle, but it might be enlightening in terms of what the state of the art is.
* Termination of higher-order typed programs is difficult, because it involves subtle interactions between the type system features, the inductive types involved, and the "guard condition" required for function definitions. The more complicated the termination check, the less trustworthy the system, since consistency depends on it! These slides by Barras go into some of the nasty details for the Coq system.
* Termination for higher-order systems with side effects (references) is particularly nasty. In particular, types are not enough anymore, even in the absence of recursion, see e.g. Landin's knot.

---
Tags: algorithm-analysis, computability, halting-problem
---


# Question
Title: Identifying/equating constants in a term rewrite system
Suppose we have a term rewrite system $\mathcal{R} = (R, \Sigma)$ with basic rewrite rules $R$ over a signature $\Sigma$. Suppose also that this rewrite system $\mathcal{R}$ is confluent and terminating, and that each constant symbol of $\Sigma$ is a normal form with respect to $\mathcal{R}$.

Now suppose that we want to identify/equate some of the constants of $\Sigma$. For example, if we have two constants $c, d$ in the signature $\Sigma$, then we may want to 'merge' $c$ and $d$ into a single constant $e$ (thereby obtaining a new signature $\Sigma'$ that is the same as $\Sigma$ except that $c$ and $d$ have been replaced by $e$), and then modify the basic rewrite rules in $R$ accordingly (by replacing all occurrences of $c$ and $d$ by $e$).

If we identify/equate some constants of $\Sigma$ in this way, and then modify the rules in $R$ accordingly, so that we obtain a slightly modified term rewrite system $\mathcal{R}' = (R', \Sigma')$, is there any way to prove that $\mathcal{R}'$ will still be confluent and terminating?

Obviously, if $R$ has a rule like $c \to d$ and we merge $c$ and $d$ into the single constant $e$, then this rule will become the rule $e \to e$, and so the resulting system will not be terminating. But this is why I assumed that each constant of $\Sigma$ is a normal form with respect to $\mathcal{R}$ (so that $R$ will not have rules like $c \to d$).

# Answer
> 2 votes
Counterexample:

$f(c) \rightarrow f(d)$

In general, there are some modularity theorems for termination and confluence that may apply if, e.g. your constants do not appear at all in any rule.

There are probably some weaker assumptions that can make this work though.

---
Tags: normal-forms, term-rewriting, termination
---


# Question
Title: How to reach data segment from global pointer in MIPS?
The global pointer is initialized to 01x10008000. The data segment starts at 0x1000000.

I want to load the first word found in the data segment. So I place 0x8000 in the address field of lw.

lw $a0, 8000hex(\\$gp)

Apparently 0x8000 in binary is 1000 0000 0000 0000 which is a negative number because the sign bit is 1.

This is the logic my professor provides so that we reach the start of the data segment by subtracting.

But if you convert all the other numbers to binary they also have 1 as the sign bit. So are they all negative?

# Answer
> 0 votes
As Yuval Filmus said, addresses are unsigned.

---
Tags: computer-architecture, mips
---


title: How to find MST for each source

text:
# Question
Title: How to find MST for each source
Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost. The image bellow is an example of a possible solution for that map, then the output of the algorithm should be two trees with the edges of those trees.  If there is only one factory a possible solution would be using Kruskal's algorithm to find the MST with this factory as source.

¿Is there any algorithm to do so? ¿How would a modification of Kruskal's work?

\[EDIT\] I need to find the minimum cost tree from factories to shops but given that there is more than one factory may have unconnected trees as optimal solution.

\[EDIT 2\] If an edge is used twice that cost counts only once.

# Answer
> 1 votes
Here is a slight modification of Kruskal's algorithm which can solve this.

Sort all edges by non-decreasing weight. Maintain a disjoint set union to track which vertices are connected, as usual. Consider the edges one by one in the resulting order. If an edge connects two vertices which are already connected, we drop it, as usual.

**The difference** is as follows: if an edge connects two components such that each already contains a factory, such edge would contribute nothing to our network, so we also drop it.

If an edge connects two components, and at least one of them does not contain a factory, we take the edge and update the disjoint set union, as usual.

---

Another view with the same result is as follows. Make an auxiliary vertex, the *super-factory*. Add an edge of weight 0 from the *super-factory* to each of the real factories. Run Kruskal algorithm on this new graph.

First thing, it will take all our added edges with weight 0. If the original graph also had such edges, let the algorithm start with our newly added edges. We can do it since the total cost does not depend on the ordering of same-weight edges.

Now, the original condition “each shop must be connected to a factory” got translated to “each shop must be connected to the *super-factory*”, which is equivalent to just “all vertices must be connected”, which in turn is exactly what Kruskal algorithm will do for us.

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


# Question
Title: What is the complexity of comparing point sequences?
Given two sorted arrays of floating point numbers $X$ and $Y$, we can define the S-distance as follows. The S-distance is defined as the minimum cost associated with the transformation of one point pattern $X$ into a pattern $Y$ by deleting, adding, and moving points (that is adding a constant to all points). The cost of a transformation is:

$$p\_d|X\_{delete}| + p\_a|X\_{add}| + p\_m d$$

where $p\_a$, $p\_d$ and $p\_m$ are parameters and $X\_{delete}$ and $X\_{add}$ are subsets of $X$ that are deleted and added. $|X\_{delete}|$, for example, is the number of elements in $|X\_{delete}|$ and not the sum of the values. $d$ is the value that we are adding to all the points in the sequence $X$.

For example, say $X = (1,2,3)$ and $Y = (2,4)$ then one possible transformation of $X$ into $Y$ has cost $p\_d + p\_m$ as we can delete $2$ from $X$ and then increase both the points in $X$ by $1$ to make $(2,4)$ (so $d = 1$).

By adding a point I mean inserting a new point into the array.

I am trying to work out what the complexity of computing this distance is. It is not obvious to me how to do this by dynamic programming for example.

---

@Gassa gives a solution using $O(n^2)$ hash function calls. Is there a simple dynamic programming (or other) solution that doesn't require any hash function calls at all?

# Answer
Here's a start: an upper bound is $O(n^3)$.

Note that we need either $0$ or $1$ moves: any two moves could be expressed as one. Furthermore, this one move is commutative with all other operations: it may occur at any point in time, the end result will still be the same.

Barring some degenerate cases, consider one point $X\_i$ which does not get deleted and moves into $Y\_j$. There are a total of $n^2$ such possibilities. For each fixed $i$ and $j$, first, we know whether we need a move, and second, for all other points, we can establish which $X\_u$ move into which $Y\_v$ in $O(n)$. For example, put all $Y\_v$ in a hash table in $O(n)$, iterate over all $X\_u$ and search for them in the hash table in $O(n)$ total.

---

Here's a speedup to $O(n^2)$.

Consider all possible $n^2$ move distances: each "$X\_i$ to $Y\_j$" produces a distance. Some of the distances may turn out to be the same. In your example of $X = (1, 2, 3)$ and $Y = (2, 4)$, the $X\_1 \to Y\_1$ and $X\_3 \to Y\_2$ produce the same distance of $2$. So, in the end, each distance will have several pairs associated with it.

Now, we will need all $X\_i$ to be different, and all $Y\_j$ to be different. Then, if a distance $d$ has $r$ pairs associated with it, all $X\_i$ in these pairs are pairwise different, and all $Y\_j$ in these pairs are also pairwise different. It means that, when we move points by distance $d$, we will have $r$ matching points, and all other points will be non-matching, so will have to be deleted from $\\{X\\}$ or inserted into $\\{Y\\}$, respectively.

So, implementation-wise, maintain a hash map which maps a distance to the number of times we encountered such distance. Iterate over all pairs of "$X\_i$ to $Y\_j$" and fill the map, in $O(n^2)$ total. Now iterate the map and find the minimum cost, also in $O(n^2)$ total. For a distance $d$, when the number of pairs with such distance is $r (d)$, the cost is the sum of the following:

* $p\_m$ if $d$ is nonzero, or $0$ if $d$ is zero;
* $p\_d \cdot (l\_X - r (d))$, where $l\_X$ is the length of $\\{X\\}$;
* $p\_a \cdot (l\_Y - r (d))$, where $l\_Y$ is the length of $\\{Y\\}$.

It may be possible to handle the case when the sequences can contain equal elements, but the details look cumbersome.

---

All this assumes $O(1)$ performance of hash sets and hash maps. If that is a problem, at the very least, we can add logarithms and use tree sets and tree maps, respectively.

Also, the solution does not address precision loss for floating point operations. For example, the implementation may use integers, by multiplying the given floating point values values by a constant.
> 3 votes

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


title: $MIN_{NFA}$ is PSPACE complete

text:
# Question
Title: $MIN_{NFA}$ is PSPACE complete
The problem is taken out of Theory of Computational Complexity:

Now, I think I've successfully proven that $ALL\_{NFA} = \\{(A) : A$ is an NFA and $ L(A) = \Sigma^\*\\} \leq\_p MIN\_{NFA}$. Which implies that $MIN\_{NFA}$ is PSPACE hard, as the latter is itself.

However I'm stuck proving this problem is in PSPACE - I've thought of defining a nondeterministic Turing Machine, that takes an NFA and a natural number $n$ as input, and on each branch of the computation creates a NFA with number of states less than or equal to $n$. This machine will go on to compare the resulting NFA (in each branch) to the given one (this problem is itself in PSPACE, but I've yet to prove it myself).

However it seems to me the above idea may use more than poly. time, as we may have to keep track of the transition function of each NFA; whose image is in the power set of its states.

Any assistance?

# Answer
For a fixed alphabet, you can describe an NFA with $n$ states using $O(n^2)$ bits. Now, given a DFA $M$ and an integer $n$ (encoded in binary), we consider two cases:

1. $M$ has at most $n$ states. In this case, there exists an NFA for $L(M)$ having at most $n$ states.
2. $M$ has more than $n$ states. In this case, the input length is $\Omega(n)$ bits, and so we can guess an NFA with $n$ states in polynomial space.
> 1 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Fast, stable, almost in-place radix and merge sorts
I've developed LSD radix sort algorithm that is

* stable,
* about as fast as the classic LSD radix sort,
* require only $O(\sqrt{RN})$ extra space when we sort into R buckets.

The same technique also allows to perform stable, efficient, almost in-place merge & quick sorts; as well as stable almost inplace merge/partition operations; and also applicable to some other list processing algorithms.

I describe it in my answer to this question. I believe that the proposed modifications to classic algorithms has important practical value. Other known techniques for (almost) in-place stable sort:

* WikiSort and GrailSort that have even smaller memory requirements but seems to perform more data moves than the simple mergesort
* highly theoretical in-place stable sorts that doesn't even pretend to have practical usefulness

EDIT: I've found this technique described 4 years ago in section 3.2.3 of paper A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort

# Answer
Here is description of the proposed algorithm.

The algorithm is further improvement of the one proposed in Parallel radix sort with virtual memory and write-combining. They implemented fastest parallel LSD radix sort that avoids the counting pass by using "indefinite" space for output buckets. Each bucket allocs space on-demand using hardware paged memory support. A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort took this idea further, proposing software implementation of the paged memory, that allows to perform stable radix/merge/quick sort using only $O(\sqrt{NR})$ extra memory.

Basic operations of radix, merge and quick sort have something in common:

* radix sort pass: read from 1 stream and write into R streams
* merge: read from R streams and write into 1 stream
* partition: read from 1 stream and write into R streams

Each of these operations process its input and output streams in strictly sequential manner. On every step, input plus output streams contain exactly N elements total - we neither produce nor consume any data items, but only move them between streams. This allows to implement in-place list-processing versions of these algorithms that don't move any data at all and only modify `next` list pointers. And this brings us to idea that we can perform these operations on array in-place, allocating only a little more space to perform home-made memory management of the array space.

To accomplish that, we split input and output streams into fixed-size pages and maintain list of pages in the each stream. When an input stream consumed all data on a page - this page is moved into the freepage list. When output stream needs more space - it allocs a page from the freepage list. Each stream may have incomplete first and last page, so in the worst case we may have `2*R*PAGESIZE` unused items at any given moment - it's the extra space we need to alloc in addition to the page management structures. It's easy to find that the optimal PAGESIZE is $O(\sqrt{N/R})$ and the entire extra memory usage is $O(\sqrt{NR})$.

A few concrete examples:

* 2-way sorting of 1 million 8-byte items, i.e. **8 MB**: we need 4 extra pages and can fit page number into 16 bits. 2 KB pages are optimal, and we need **16 KB** of extra space total.
* 256-way sorting of the **same array**: we need 512 extra pages, while page number still fits into 16 bits. 256 byte pages are optimal, and we need **192 KB** of extra space total. It's 2% of 8 MB, which is the largest proportion among these examples.
* 2-way sorting of 128 millions 8-byte items, i.e. **1 GB**: we need 4 extra pages, and page number still fits into 16 bits. 32 KB pages are optimal, and we need **192 KB** of extra space total. You may note that the two later cases has the same `R*N` and hence the same memory requirements.
* 256-way sorting of the **same array**: we need 512 extra pages, and page number finally requires full 32 bits. 4 KB pages are optimal, and we need **3 MB** of extra space total.

TL;DR: sorting more than 1 MB of data usually requires less than 10% extra space, and the proportion reduces as datasize grows.

# Algorithm: utility functions

Let's define data structures for our memory manager:

```
// Number of items per page
const int PAGESIZE = 1024; // just for example

const int PAGE_COUNT = N/PAGESIZE;

// next_page[page] is either -1 (meaning EOF)
// or index of the next page in the same stream
int next_page[PAGE_COUNT];

// Input and output streams
StreamDescriptor in_streams[R];
StreamDescriptor out_streams[R];

struct StreamDescriptor
{
    int first_page;
    int first_element;  // index of first element on the first page
    int last_page;
    int last_element;  // index of last element on the last page + 1
    // all pages between the first and last ones are fully populated
};

```

Here is the "memory manager" which allows to alloc new pages for output streams and release pages consumed from input streams:

```
// head of the available pages LIFO queue
int first_available_page;

int AllocPage()
{
    int page = first_available_page;
    assert(page != -1);
    first_available_page = next_page[first_available_page];
    return page;
}

void ReleasePage(int page)
{
    next_page[page] = first_available_page;
    first_available_page = page;
}

// Main data storage (holding N elements) provided by the caller
T* MainArray;

// Extra memory allocated for temporary data storage
T* ExtraPages;

// Return address of given memory page
T* Page (int page)
{
    if (page < PAGE_COUNT)
        return MainArray + PAGESIZE*page;
    else
        return ExtraPages + PAGESIZE*(page - PAGE_COUNT);
}

```

And these operations read item from given input stream and write item into given output stream:

```
T get_next_item (int input_stream)
{
    StreamDescriptor s = in_streams[input_stream];
    if (s.first_page == s.last_page  &&  s.first_element == s.last_element)
    {
        ReleasePage(s.first_page);
        return EOF;
    }
    if (s.first_element == PAGESIZE)
    {
        int next = next_page[s.first_page];
        ReleasePage(s.first_page);
        if (next == -1)
            return EOF;
        s.first_page = next;
        s.first_element = 0;
    }
    return Page(s.first_page)[s.first_element++];
}

void put_item (int output_stream, T item)
{
    StreamDescriptor s = out_streams[output_stream];
    if (s.last_element == PAGESIZE)
    {
        int next = AllocPage();
        next_page[s.last_page] = next;
        s.last_page = next;
        s.last_element = 0;
    }
    Page(s.last_page)[s.last_element++] = item;
}

```

# Algorithm: LSD radix sort

Initialization depends on the amount of input and output streams. For example, prior to first pass of LSD sort we do the following:

```
void LsdRadixSort (T* data_to_sort, int N)
{
    MainArray = data_to_sort;
    ExtraPages = new T[2*R*PAGESIZE];

    // Setup first input stream as containing the entire MainArray contents
    in_streams[0].first_page = 0;
    in_streams[0].first_element = 0;
    in_streams[0].last_page = PAGE_COUNT-1;
    in_streams[0].last_element = N % PAGESIZE;

    for (int i=0; i<PAGE_COUNT-1; i++)
        next_page[i] = i+1;
    next_page[PAGE_COUNT-1] = -1;

    // Alloc one initial page for each outstream
    for (int i=0; i<R; i++)
    {
        int page = PAGE_COUNT+i;
        out_streams[i].first_page = page;
        out_streams[i].first_element = 0;
        out_streams[i].last_page = page;
        out_streams[i].last_element = 0;
    }

    first_available_page = -1;

    ...
}

```

Prior to second and following passes of LSD sort, we perform this:

```
// Make old out_streams new in_streams
for (int i=0; i<R; i++)
{
    in_streams[i] = out_streams[i];
}

cur_input_stream = 0;

// Alloc one initial page for each outstream
for (int i=0; i<R; i++)
{
    int page = AllocPage();
    out_streams[i].first_page = page;
    out_streams[i].first_element = 0;
    out_streams[i].last_page = page;
    out_streams[i].last_element = 0;
}

```

In the first pass, data should be read with `get_next_item(0)` calls until it returns EOF. On the second and following passes, data should be read using the following procedure, also up to EOF:

```
// Enumerate contents of all input streams in order
T get_next_item_2nd()
{
    if (cur_input_stream >= R)
        return EOF;

    T item = get_next_item(cur_input_stream);
    if (item==EOF)
    {
        ++cur_input_stream;
        return get_next_item_2nd();
    }

    return item;
}

```

One pass of LSD radix sort:

```
void one_pass(int pass)
{
    for(;;)
    {
        T item  =  pass==1? get_next_item(0) : get_next_item_2nd();
        if (item==EOF)
            break;
        int bucket = calc_bucket(item,pass);
        put_item(bucket,item);
    }
}

```

# Algorithm: reordering data

Once sorting is finished, the caller may either read data in sorted order using the same get\_next\_item\_2nd() procedure, or data may be placed in proper order in original array.

Reordering requires two steps:

1. compact data into single stream, removing "holes"
2. move each page of the compacted stream into right place

For the first step, we can just append to the first stream contents of remaining streams:

```
// Make old out_streams new in_streams (except for the first one)
for (int i=1; i<R; i++)
{
    in_streams[i] = out_streams[i];
}

cur_input_stream = 1;

// Move data from all streams into the first one
for(;;)
{
    T item = get_next_item_2nd();
    if (item==EOF)
        break;
    put_item(0,item);
}

```

For the second step, we start with enumerating pages in the single stream remaining, and marking all other (i.e. free) pages with -1:

```
// final_place and next_page are the same array used in different roles
int* const final_place = next_page;

int page_i = out_streams[0].first_page;

for (int i=0; i<PAGE_COUNT; i++)
{
    int next = next_page[page_i];
    final_place[page_i] = i;
    page_i = next;
}

while (first_available_page != -1)
{
    int next = next_page[first_available_page];
    final_place[first_available_page] = -1;
    first_available_page = next;
}

```

From this point on, `final_place[pg]` is a page where current contents of page `pg` should be finally placed, or -1 for a page whose contents is garbage and so can be overwritten. Now all that remains is the classic "move them all to their final places" algorithm:

```
for (int i=0; i<PAGE_COUNT+2*R; i++)
{
    int page = i;

    while (final_place[page] != -1  &&  final_place[page] != page)
    {
        mem_exchange( Page(page), Page(final_place[page]), PAGESIZE*sizeof(T));
        std::swap( final_place[page], final_place[final_place[page]]);
    }
}

```
> 1 votes

---
Tags: algorithms, algorithm-analysis, sorting, space-complexity, radix-sort
---


# Question
Title: How CompCert "proves" different things in its codebase
In order to understand examples of formal proofs, I am interested in how CompCert applies "proof" techniques. Specifically, I am wondering what a particular example is of something CompCert "proves" in their GitHub repo, so I can get a grasp of how proofs are applied in practice (to something that is somewhat familiar, compiler technology). I have had some minimal experience with Coq so I should be able to follow along. I also have some experience with x86, so perhaps something in the x86 folder would be a good example. Or perhaps something directly to do with the C language (such as Clight), or with memory.

In x86/Asm.v, they have several `Inductive` definitions, which I think is a proof in itself. For example:

```
Inductive ireg: Type :=
  | RAX | RBX | RCX | RDX | RSI | RDI | RBP | RSP
  | R8  | R9  | R10 | R11 | R12 | R13 | R14 | R15.

Inductive instruction: Type :=
  ...

```

Then they have some `Definition` definitions:

```
Definition code := list instruction.

Definition is_label (lbl: label) (instr: instruction) : bool :=
  match instr with
  | Plabel lbl' => if peq lbl lbl' then true else false
  | _ => false
  end.

```

Wondering if this is also a "proof" of some sort since (I think) it is some sort of *type*.

They also have `Lemma` definitions, where the *explicit* proofs are:

```
Lemma is_label_correct:
  forall lbl instr,
  if **is_label** lbl instr then instr = Plabel lbl else instr  Plabel lbl.
Proof.
  intros.  destruct instr; simpl; try discriminate.
  case (peq lbl l); intro; congruence.
Qed.
```

I understand about Coq tactics, but haven't actually written any proofs myself so don't have applied knowledge.

So here we have `Inductive` is used in a `Definition` which is used in a `Lemma`. And then it looks like that lemma is used by other lemmas:

```
Lemma transl_code_label:
  forall lbl f c ep tc,
  transl_code f c ep = OK tc ->
  match Mach.find_label lbl c with
  | None => find_label lbl tc = None
  | Some c' => exists tc', find_label lbl tc = Some tc' /\ transl_code f c' false = OK tc'
  end.
Proof.
  induction c; simpl; intros.
  inv H. auto.
  monadInv H. rewrite (transl_instr_label' lbl _ _ _ _ _ EQ0).
  generalize (**Mach.is_label_correct** lbl a).
  destruct (**Mach.is_label** lbl a); intros.
  subst a. simpl in EQ. exists x; auto.
  eapply IHc; eauto.
Qed.
```

In this question I am wondering what a proof consists of in CompCert, given some example like the above. I would like to be able to know what I need to write a proof for my own software, by first knowing what CompCert is actually "proving", and how they are "proving it". It seems that there are *types* (Inductive and Definition), and then *proofs* (Lemma and Proof). Not sure if the Inductive/Definition things are proofs in and of themselves. Proofs traditionally are essentially just derivation trees of applying rules, but I'm not exactly sure if that is what is happening here. It seems the Coq tactics are just creating a derivation tree, correct me if I'm wrong. Then the lemma/proof is just a derivation tree (a bunch of rules applied) down to the "axioms" (definitions and inductive types). The fact that there could be an electronics error isn't accounted for (I don't think), so the proof is really of a "pure" system in some sense. So practical proofs are applied to pure systems that make some assumptions about the environment.

In the end, I'm wondering, the kind of "proof system" CompCert is. What is making it a good system of formal proofs. Knowing that, I would be able to apply "proofs" to stuff outside of CompCert but in other programming contexts. Also wondering if there is some sort of "specification" that CompCert is formally verified against, or if it is just the "model" (as in the model in model checking vs. specification).

# Answer
I am not very sure what you are asking, and I am also not sure that you have the background to understand CompCert. It seems that you are still confused by some basic concepts in Coq.

I would suggest you start with Software Foundations. Most of your questions would be answered there.

But, basically:

* `Definition` and `Fixpoint` are like OCaml's `let` and `let rec`, respectively. They are used to define values and functions (and, of course, propositions).
* `Inductive` is like `type` in OCaml, or `datatype` in SML. They are used to define algebraic data types (or "inference rules").
* `Prop` is the sort of propositions, so `Definition` and `Inductive` that return `Prop`s are defining propositions (i.e., "proof rules"). The `Definition` and `Inductive`s are not themselves proofs.
* `Lemma`, `Theorem`, `Corollary`, etc...are used for proofs.
* Coq is based on the Curry-Howard correspondence: a proof of the proposition $A \rightarrow B$ is a function that takes something of type $A$ and produces something of type $B$, a proof by induction corresponds to a recursive function, etc. A proof of $A = B$ is obtained by transforming both sides and applying the only constructor of the type $=$, which is `Refl of x * x` (not Coq syntax, but you should get it). So, all proofs by tactic actually expand into programs!
* In other words, Coq tactics are just another style of programming. You *can* use `Definition` and/or `Fixpoint` to write proofs, or use `Proof` to write programs. Of course, you *should* not do so; but you can.
* CompCert is indeed proved against a formal specification. Which one? The official C programming language specification! Of course, you can't really prove anything against the text of the specification, so they encoded the specification in Coq using `Definition`s and `Inductive`s.

In *Software Foundations*, there are examples of verifying a few toy interpreters and some toy programs, as well as more serious examples of verifying algorithms like red-black tree insertions and graph coloring. It does a pretty good job of explaining what and how to prove when you are writing programs in Coq. I would suggest that you start from there.
> 6 votes

---
Tags: proof-techniques, type-theory, software-verification, coq
---


# Question
Title: Proving the equivalence of an LTL and a CTL formula
For a lecture I am attending, we have to prove that

$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \big(a \textsf{U} (b \land \square a)\big).$$

That is, we need to prove that for the CTL formula $\forall \big(a \textsf{U} (b \land \forall \square a)\big)$, the LTL formula $\big(a \textsf{U} (b \land \square a)\big)$ is equivalent to it. I know how I would go about trying to disprove it, that is, by providing a transition system that fulfils one but not the other, but I am at a complete loss about how to prove something like this.

Note that we use $\square$ instead of $\textsf{G}$.

Edit:

I managed to prove $$\big(a\textsf{U}(b\land\square a) \big) \equiv \square a \land \lozenge b$$ if that's any help.

# Answer
First, it is important to understand what the statement

$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \big(a \textsf{U} (b \land \square a)\big)$$

means. Hear LTL is interpreted over a transition system, and the semantics then is that *all* paths of the system satisfy the LTL formula. This is tightly connected to the CTL operator $\forall$.

Lets use the equivalence you have shown and prove $$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \square a \land \lozenge b$$

To prove the statement, first take a transition system $\mathcal{T}$ that satisfies $\forall \big(a \textsf{U} (b \land \forall \square a)\big)$ and show that it satisfies $\square a \land \lozenge b$. Take arbitrary path $p$ of $\mathcal{T}$. By the CTL semantics you know that $p$ satisfies the path formula $\big(a \textsf{U} (b \land \forall \square a)\big)$. It will have a prefix labeled by $a$ and the state $s$ at the end of this prefix will satisfy the state formula $b \land \square a$. Thus *all* possible paths starting in $s$ are globally labeled by $a$. In particular, the suffix of the part $p$ we are considering will be labeled by $a$ globally. Also the state $s$ is labeled by $b$. Thus we can conclude that the path $p$ satisfies $\square a \land \lozenge b$.

The other direction is similar. Assume that all paths of $\mathcal{T}$ satisfy $\square a \land \lozenge b$ and show for arbitrary path $p$ of $\mathcal{T}$ that it satisfies $a \textsf{U}(b \land \forall \square a)$. It will be labeled by $b$ at some point, and as all paths of $\mathcal{T}$ are labeled by $a$ globally, in particular all suffixes of $p$ are. So the state on the path $p$ that is labeled by $b$ satisfies the state formula $b \land \forall \square a$.

There is an interesting result connected to your question: let $\varphi$ be a CTL formula. If the property $\varphi$ is definable by an LTL formula (i.e. there exists an LTL formula $\psi$ such that $\varphi \equiv \psi$), then the LTL formula you get by simply deleting all path quantifiers in $\varphi$ is equivalent to $\psi$. See the discussion in Equivalence preserving operator from CTL\* to LTL.
> 0 votes

---
Tags: linear-temporal-logic, computation-tree-logic
---


# Question
Title: Simple example for Higher Order Abstract Syntax (λ-tree syntax)
I am reading https://www.cs.cmu.edu/~fp/papers/pldi88.pdf and https://en.wikipedia.org/wiki/Higher-order\_abstract\_syntax for trying to understand encoding of linear logic using HOAS into Coq. But I still cannot grasp whats going on? Is there simple concrete example available for using HOAS? E.g. exmaple in concrete syntax, example of abstract syntax and example of encoding in HOAS? Or maybe there is available good in-depth explanation of HOAS with multiple examples?

# Answer
Well, this is a bit broad but the basic idea is the following. In First-order abstract syntax (FOAS) we model lambda terms following their syntax tree. E.g., in Coq we would write

```
(* FOAS *)
Definition variable := string .
Inductive term: Set :=
  | var: variable -> term
  | app: term -> term -> term
  | lam: variable -> term -> term
.

Definition example: term := lam "x" (app (var "x") (var "x")) .

```

Note how we model $\lambda x. xx$ by storing the name `"x"` explicitly. In a sense, a lambda is represented as a pair `(variable name, body)`.

In FOAS we need to carefully handle alpha-conversion and capture-avoiding substitutions.

In HOAS, we model lambdas as functions, not pairs, exploiting the functions in the host language.

```
(* HOAS *)
Inductive term: Set :=
  | var: variable -> term    (* vars are usually removed in HOAS *)
  | app: term -> term -> term
  | lam: (term -> term) -> term

Definition example: term = lam (fun x: term => app x x) .

```

(Note that this won't type check in Coq since it does not use positive recursion, as Mario Carneiro points out below. Still, you get the idea.)

No need to handle alpha-conversion (or substitutions) here since the name `"x"` is no longer stored in the term.

What we lose in HOAS is the ability to dissect the term representation (e.g. structural induction on the syntax tree) as easily as we could in FOAS.
> 4 votes

---
Tags: programming-languages, syntax, syntax-trees
---


# Question
Title: Reduction from an assignment problem to an independent set problem: NP-hard
The problem I have is as follows: I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$ The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C are incidents and the $n$ edges from $V$ to $C$ are the travel times from the vehicle to the incidents. Now the incidents occur at a certain time and due to that not all incidents can be assigned to the vehicle. Every incident induces a set $D\_i$ that consist of incidents that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle: $D\_i = \\{k|\text{incidents $k$ that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle}\\}$ Out of the sets $D\_1, \dots , D\_n$ a 'Forbidden Incident' Graph $G=(C,E)$ can be constructed where an edge $(h,i)\in E$ if ($i \in D\_h$ or $h \in D\_i$). See the following figure as an example: Forbidden Incidents Graph

So the problem is: Give a set of incidents, is this set an independent set in the forbidden incident graph? It is known that an Independent Set problem is NP-hard. Now I aim to proof the conjecture that this problem is also NP-hard.

**So I want to find a reduction from my problem to the independent set problem.**

**Any hints?**

# Answer
If you want to show that your problem is NP hard, your reduction should go in the other direction. You have to show: $\exists L \in NPH: L \le\_M yourProblem$ where $NPH$ is the Set of NP-hard languages.

Your try looks like you wan't to reduce from your problem to Independent Set.
> 2 votes

# Answer
As Tomet pointed out, your reduction is in the wrong direction.

But there is a more fundamental problem (which is something to be cheerful about if your underlying goal is to solve the problem efficiently): If, as you say, the set of incidents is *given*, then checking if they form an independent set in the forbidden incidents set is trivial: All you need to do is check whether any pair of them corresponds to an edge in the graph. This is $O(n^2)$ time for $n$ incidents.
> 1 votes

---
Tags: reductions, np-hard, assignment-problem
---


# Question
Title: What is the difference between Big O and Theta notation in terms of inputs?
In Coreman , it's written :

> The $O(n^2)$ bound on worst-case running time of insertion sort also applies to its running time on every input. The $\Theta(n^2)$ bound on the worst-case running time of insertion sort,however, does not imply $\Theta(n^2)$ bound on the running time of insertion sort on every input.

So, is there any difference between the two notations in terms of input? If so, then why does it use $\Theta(n^2)$ in worst case running time of insertion sort?

# Answer
It is important to understand the distinction between asymptotic bounds on time complexity, and the consideration of best, average, and worst-case performance. Many who are new to the subject tend to associate an $O$-bound as always indicating worst-case performance, but the best-case performance of an algorithm will always have an $O$-bound, just as the worst-case performance will always have an $\Omega$-bound.

I would like to add to Raphael's answer with an analogy.

Imagine that you live in a mountain town, where it snows fairly often. Your only means of transportation is a 20-year-old car that has seen better days. On most days, the car performs quite well, and you have no issues getting to where you need to go. However, on days when it snows, you are sometimes unable to get it out of the driveway. Even when you can get it out of the driveway, it does not function as well as it does on days when it is not snowing.

In this situation, it is clear that the worst possible performance ($O$) in the worst possible scenario is going to be the worst possible performance ($O$) for the car in any scenario! If this weren't the case, then how could it be the worst possible scenario? However, determining the best possible performance ($\Omega$) in the worst possible scenario tells you nothing about how the car performs in the best or average case. It is the same with insertion sort. (It is important to note though that for some algorithms, the $O$ and $\Omega$-bounds are actually the same in all cases).

Once you understand that insertion sort is $O(n^2)$ in all cases *because* it is $O(n^2)$ in the worst case yet it is $\Omega(n)$ in all cases *despite* being $\Omega(n^2)$ in the worst case, you will understand what the authors mean in that excerpt.
> 3 votes

# Answer
The best case runtime of insertion sort is linear, i.e. $\Theta(n)$. Therefore, there is no $\Theta(n^2)$ bound on all inputs, since that would require $\Omega(n^2)$ on all inputs.

This is just one example proving that while $O$-bounds on the worst-case translate to all-case, but $\Omega$-bounds (and therewith $\Theta$-bounds) do not. (Which is, of course, the point in the text.) You can also investigate this mathematically by unfolding the definitions.
> 3 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Reversible computation and no cloning theorem in quantum computing
I am having a problem in understanding a conflict between reversibility in quantum computation and the No cloning theorem. Given a function f, we construct the reversible version of f by adding additional input and output wires to the circuit for f, possibly outputting junk bits. We then "copy" the output to another register to not to lose the output information using CNOT gates. But doesn't this contradict the No Cloning Theorem? We cannot copy the state of a quantum bit. Can we?

# Answer
No-cloning theorem refers to creation of independent copies of a qubit. With CNOT gates you’ll only create mirrors.

For instance, if you have $\alpha \left| 0 \right\> + \beta \left| 1 \right\>$ and measure it, you’ll get 0 with probability $p\_a=|\alpha|^2$ and 1 with $p\_b=|\beta|^2$. Now if you clone this qubit and measure both, you should get 00 with probability $p\_a^2$, 01 with $p\_a p\_b$, 10 with $p\_b p\_a$ and 11 with $p\_b^2$.

Mirroring with CNOT gives a different picture: 00 with $p\_a$, 11 with $p\_b$ and zero probability for 01 and 10.
> 3 votes

---
Tags: quantum-computing, reversible-computing
---


title: Careful 5COLOR NP hardness

text:
# Question
Title: Careful 5COLOR NP hardness
Given the following definition of Careful 5COLORING:

> A 5-coloring is careful if the colors assigned to adjacent vertices are not only distinct, but differ by more than 1(mod 5)

how would a reasonable reduction to prove NP hardness work? Suggestion is to reduce from standard 5COLOR, but I am not able to find a correct one.

I have tried reducing from an instance $G$ of the standard 5COLOR as suggested creating one extra vertex between every edge in $G$. That is, let $\\{u,v\\}$ be an edge in $G$, create a new vertex $w$ and add edges $\\{u,w\\}$ and $\\{w,v\\}$. Fix the color of every new vertex to the same color, for example 3. This results in a new graph $H$.

When proving "$G$ is 5COLORABLE iff $H$ is carefully 5COLORABLE", I can prove the first $G$ is 5COLORABLE $\rightarrow$ $H$ is carefully 5COLORABLE since $H$ actually requires only 3 colors (if every new vertex is colored as 3, I only need colors 1 and 5 for the original vertexes in $G$).

On the other hand, the proof doesn't work since there are instances where $G$ isn't 5COLORABLE but $H$ is carefully 5COLORABLE. This has led me to believe my reduction is wrong.

# Answer
> 2 votes
There is a dichotomy theorem that covers this. For a graph $H$, let $P\_H$ be the following problem: On input of graph $G$, decide whether there is a homomorphism from $G$ to $H$. A homomorphism is a function that maps vertices of $G$ to vertices of $H$ in such a way that edges of $G$ are mapped to edges of $H$.

Observe how $5$-colouring is $P\_{K\_5}$, where $K\_5$ is the complete graph with $5$ vertices: The only constraint for a homomorphism to $K\_5$ is that the endpoints of edges are mapped to different vertices. Furthermore, careful $5$-colouring is $P\_{C\_5}$, where $C\_5$ is a cycle of length $5$. (To see how that works out, let the vertices of said cycle be in the order $0,2,4,1,3$.)

Now the theorem states that:

1. If $H$ is bipartite, then $P\_H$ is in PTIME.
2. If $H$ is not bipartite, then $P\_H$ is NP-complete.

If you still want a reduction from $5$-colouring, I suggest to look for a suitable gadget. The gadget should be a graph $I$ with two special vertices $v$ and $w$, such that

1. There is no careful $5$-colouring of $I$ that assigns the same colour to $v$ and $w$.
2. For all colours $c$ and $d$ such that $c\not=d$, there is a careful $5$-colouring of $I$ that assigns $c$ to $v$ and $d$ to $w$.

Then, for a reduction you would replace every edge with a copy of $I$.

\[EDIT\]

Wikipedia has the following reference for the dichotomy theorem:

Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110

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


title: Linked List fundamental concepts

text:
# Question
Title: Linked List fundamental concepts
I am trying to understand the basics of Linked List. The definition of my LinkedList class is as follows:

```
public class ListNode {
 int val;
 ListNode next;
 ListNode(int x) { val = x; }

```

Now I am facing a problem. My code is as follows:

```
ListNode dummy = new ListNode(0);
dummy.next =  head;
ListNode prev = dummy;
ListNode slow = head;
head.next = null;
prev.next = slow;

ListNode temp = slow.next;
prev.next = temp;

System.out.println(dummy.next); //comes out null

```

Why is it coming out as null? dummy.next was pointing to head and I only changed slow and prev?

Can we use slow and head interchangeably? If yes, then why does this happen?

```
// head points to a Linked list starting from 1 in 1 -> 2 -> 3
ListNode curr = head;

while(curr.next!= null){
    curr= curr.next;
}

System.out.println(curr);
System.out.println(head); //these are different and head does not change

```

# Answer
This has nothing to do with linked lists and everything to do with *references* (see also *pointers*). When you assign a mutable object to a variable, the variable holds a *reference* to the actual object: its memory address. If you assign the same object to two different variables, they both reference the same object; both variables internally hold the same memory address (and changing its members will change the underlying object). But when you then reassign one of those variables, that one now points to a different object again.
> 1 votes

---
Tags: memory-access, linked-lists, java
---


title: Exponential Time Classification

text:
# Question
Title: Exponential Time Classification
If I have a list of length 'n' where each element is a successive power of 2 would an algorithm that simply prints each element decremented to 1 be classified as exponential time?

```
print([2,4,8,16]) #operations:1
print([1,4,8,16]) #operations:2
print([1,3,8,16]) #operations:3
print([1,2,8,16]) #operations:4
print([1,1,8,16])  #operations:5
print([1,1,7,16])  #operations:6
print([1,1,6,16])  #operations:7
print([1,1,..,16]) #operations+=1
print([..])       #operations+=1
print([1,1,1,1])  #operations: 2**(n+1)-2 :: O(2**n)?

```

Does one add the number of operations or the complexity of each operation?

Is the complexity O(2\**n) or is it O(1)\*(2\**(n+1)-2) reducing to constant time: O(1)?

If the complexity is constant time would I need each operation to be O(2\**n) for the algorithm to be classified as exponential time? O(2\**n)\*(2\**(n+1)-2) reducing to O(2\**n) or would it reduce to double exponential time: O(2\**(2\**n))?

Here is some python code for such a naive algorithm:

```
orig_lst=[2,4,8,16]
out_lst=orig_lst[:]
ops=0
n=len(out_lst)
for ind,el in enumerate(out_lst):
    for dec in range(el,0,-1):
        ops+=1
        out_lst[ind]=dec
print(orig_lst,"->",out_lst,"number of operations:",2**(n+1)-2,"==",ops)

```

Which prints: "\[2, 4, 8, 16\] -\> \[1, 1, 1, 1\] number of operations: 30 == 30"

# Answer
> 2 votes
> Does one add the number of operations or the complexity of each operation?

This is a good question! And the answer is, "it depends".

In any model of computation, some type of operation is considered "fundamental", and this operation is considered to run in $O(1)$. For example, some models consider multiplication to be fundamental. But others consider multiplication exponential in the number of bits.

No matter what, though, your algorithm is going to be doing $2^n$ decrement operations on the last element of the list, so it's always going to be $\Omega(2^n)$ (where the omega means "at least", as opposed to omicron's "at most").

> Is the complexity `O(2**n)` or is it `O(1)*(2**(n+1)-2)` reducing to constant time: O(1)?

I'm not sure I understand this part of the question. $O(1) \times (2^{n+1}-2)$ is $O(2^n)$, not $O(1)$.

However, your time complexity certainly isn't double-exponential. As you noted, you're doing $2^{n+1}-2$ decrement operations, so if you consider decrement to be constant, the total time is $O(2^{n+1}-2) = O(2^n)$.

Even if you did an additional $O(2^n)$ operation for each decrement, the time complexity would only be $O(2^n) \times O(2^n) = O(2^{2n})$.

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