title: Maximum Equal Sum K Subsequences

text:
# Question
Title: Maximum Equal Sum K Subsequences
Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum. Example:

```
A = [1, 2, 3, 4, 6] & K = 2
Maximum Sum Subsequence = 8 = [2, 6] & [1, 3, 4]

If, K = 3 and A = [1, 2, 3, 4, 6, 8, 9]
Maximum Sum Subsequence = 11 = [9, 2] & [8, 3] & [6, 4, 1]

```

It is not necessary that all the elements of the array need to be a part of the subsequences but each element can only be part of 1 subsequence.

I tried a brute force approach with Knapsack but that doesnt work. Any better approaches or optimizations?

# Answer
> 3 votes
This problem is NP-complete by reduction to the given subset sum problem, which asks if there is a subset $S$ from a set with a certain sum $n$.

Suppose we are given such an instance and that your problem can be efficiently solved. Then we can transform the instance by making $S' = S \cup \\{x, x - n\\}$ for some sufficiently large $x$ and solving your problem to find the $K = 2$ maximum equal subsequence sums. Then iff the answer includes $x$ and $x - n$ there is a subset that sums to $n$ and we efficiently solved the given subset sum problem.

---
Tags: algorithms, dynamic-programming, arrays, subset-sum
---


# Question
Title: Using 4-SUM to improve Subset Sum $O(2^{n/2})$ runtime
I read k-Sum $k \geq 3$ can be solved in $\approx O(n^{k/2})$

If this is right, why do not have a subset sum solver with a time complexity $O(2^{n/4})$ or better?

That is, enumerating all the subsets from 4 splits, then apply 4-sum to find if some of the four partial lists add up to the target value?

# Answer
> 4 votes
Work through the math; you are off by a factor of two. Also, you might be confusing yourself by using the same letter $n$ for two different things.

Suppose we have a list of $N$ numbers. You are proposing to split that into four chunks, where each chunk has $N/4$ numbers. Enumerating all of the subsets of a single chunk takes $O(2^{N/4})$ time. Now, you have a 4-sum problem where you are working 4 lists each containing $M=2^{N/4}$ items. This 4-sum problem can be solved in $O(M^{k/2}) = O(M^{4/2}) = O(M^2)$, and $M^2 = 2^{N/2}$, so your proposed algorithm runs in $O(2^{N/2})$ time.

There *is* an algorithm for subset-sum that runs in time $O(2^{N/2})$ and space $O(2^{N/4})$. The algorithm is due to Schroeppel and Shamir. However, it's running time is still $O(2^{N/2})$, not $O(2^{N/4})$.

I don't think there is any known subset-sum algorithm whose running time is non-trivially better than $O(2^{N/2})$. Blum, Kalai, and Wasserman have solved a related problem in subexponential time, but it's a different problem.

---
Tags: algorithms, time-complexity
---


# Question
Title: Finding if the given language is regular or not
I have the language $$L = \\{a^mb^nc^o| \\, m + n + o \> 5\\}$$

where $m,n,o$ are non-negative integers.

I have to find whether the language is regular or not.

My attempt:

I feel it should be non regular. For it to be regular, we'd have to keep track of how many $a's$, $b's$ and $c's$ we have seen. But the problem is that there can be infinitely many values of $a$, $b$ and $c$ for the given constraint, and we can't "remember" that number with finitely many states.

On the other hand, I also think that if we take the complement of the language i.e

$$L = \\{a^mb^nc^o| \\, m + n + o \<= 5\\}$$ We know that this is regular because there are finite number of solutions for the constraint. Now, since regular languages are closed under complement, we can say the former is also regular.

Which one of these methods is correct? I tried to prove it using Pumping Lemma, but to no avail.

# Answer
> 3 votes
$L$ is regular.

Here is a proof as hinted by your second method, which points out that we may take advantage of the fact that regular languages are closed under complement. Another useful fact is regular languages is closed under intersection. Let $F=\\{a^mb^nc^o| m,n,o\in\Bbb Z\_{\ge 0}, m+n+o\le 5\\}$. As a finite language, $F$ is regular. Let $H = \\{a^mb^nc^o| m,n,o\in\Bbb Z\_{\ge 0}\\}$. As expressed by the regular expression $a\*b\*c\*$, $H$ is regular. Since $L= H\cap\overline F$, $L$ is regular.

We can also see that $L$ is regular by the following one-line regular expression that expresses $L$. It is wrapped into multiple lines for easier reading.

$ ((a\\{6,\\}|a\\{5,\\}b+|a\\{4,\\}b\\{2,\\}|a\\{3,\\}b\\{3,\\}|a\\{2,\\}b\\{4,\\}|a+b\\{5,\\})c\*)|\\ ((a\\{5,\\}|a\\{4,\\}b+|a\\{3,\\}b\\{2,\\}|a\\{2,\\}b\\{3,\\}|a+b\\{4,\\}|b\\{5,\\})c+)|\\ ((a\\{4,\\}|a\\{3,\\}b+|a\\{2,\\}b\\{2,\\}|a+b\\{3,\\}|b\\{4,\\})c\\{2,\\})|\\ ((a\\{3,\\}|a\\{2,\\}b+|a+b\\{2,\\}|b\\{3,\\})c\\{3,\\})|\\ ((a\\{2,\\}|a+b+|b\\{2,\\})c\\{4,\\})|\\ (a+|b+)c\\{5,\\}|\\ c\\{6,\\} $

Now that we have shown $L$ is a regular, the first method must be incorrect. In fact, we do not have to keep track of how many a′s, b′s and c′s we have seen. All we need is to make sure that the total number of them is greater than 5. There is a difference between these two requirements.

---

By the same argument, we can see easily that for any integer $k$, $L\_k = \\{a^mb^nc^o|m,n,o\in\Bbb Z\_{\ge0},\\,m + n + o \> k\\}$ is a regular language.

Here is another similar fact. For any integer $s$ and $t$, $L\_{s,t}=\\{a^mb^nc^od^p|m,n,o,p\in\Bbb Z\_{\ge0},\\,m + o \> s, n+p \>t\\}$ is a regular language.

# Answer
> 3 votes
Your intuition should be that the language is regular. You don't need complete knowledge of the numbers of $a$s, $b$s and $c$s. You can count them off as "Zero, one, two, three, four, five, more-than-five-and-I-don't-care-by-how-much" which is a finite amount of information.

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


# Question
Title: Defining a graph decision problem not in NP
I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the input small (i.e. supplying the graph structure using a small amount of memory) so that when properties of the graph are checked, the time taken is larger than polynomial on the size of the input (and so taking problems that are in P into NP, and problems that are in NP into NEXP).

What I was wondering is whether you could do something similar but by suppliying the graph in a "standard" way (i.e. adjacency matrix), but then asking a question with a "large" answer. For instance would the following problem not be in NP?

Given a graph G = (V,E), of size n, does it contain 2^n distinct paths of size n?

To me it feels like a a certificate could not be checked in polynomial time, and so this problem cannot be in NP. I was wondering if anyone has thought of something similar, or whether there is something you could check in polynomial time that would answer this question without explicitly listing out 2^n paths.

Any input is greatly appreciated. Thanks!!

# Answer
Problems of the type "Count the number of \[object\]", where "\[object\]" is something that can be verified in polynomial time, are essentially what defines the class $\\#P$ ($\textrm{Sharp-}P$). $\\#P$ is the counting variant of $NP$.

As pointed out by @D.W., the problem you picked just so happens to be in $P$, but if you had picked some other problem (such as counting *simple* paths) it would have been $\\#P$-complete.

If you take a $\\#P$-complete counting problem, then the decision-counting variant ("are there at least $x$ many objects \[...\]") can not be in $NP$, unless the polynomial hierarchy collapses. This follows by Toda's theorem, which states that $PH\subseteq P^{\\#P}$. If such a decision-counting problem would be in $NP$, we could use a polynomial number of calls to an $NP$ oracle to compute the exact number (by binary search). Thus $P^{\\#P}$ would be equal to $P^{NP}$ and the polynomial hierarchy collapses.
> 3 votes

# Answer
It depends on the particular problem. The specific problem you mentioned can be solved in polynomial time: if $M$ is the adjacency matrix of the graph, then $\sum\_{i,j} (M^n)\_{i,j}$ counts the number of distinct paths of length $n$, where $M^n$ is the $n$th power of the matrix. (Here I am assuming the paths need not be simple.) This illustrates the difficulty of proving lower bounds. Just because one algorithm takes exponential time doesn't necessarily mean that all possible algorithms will take exponential time.
> 1 votes

# Answer
Succinct graphs typically work by describing the graph in some "programmatic" way, e.g., by giving an automaton or logical formula which accepts the string "$x,y$" iff there's an edge $xy$ in the graph.

If you don't mind unnatural problems, you can stick with adjacency matrices or lists and get hard problems by encoding strings as graphs. For example, you could code the string $001011$ as

```
o          o     o  o    o
|\         |     |  |   / \
| o--o--o--o--o--o--o--o   o
|/                      \ /
o                        o

```

where the triangle and square distinguish the two ends of the string so you know which direction to read it. Now, any language over $\\{0,1\\}^\*$ is a graph problem, so you can just pick any problem known not to be in **NP** (e.g., something **NEXP**-complete) and code it a graphs.
> 0 votes

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


# Question
Title: Stablishing termination of the construction of infinite stream with ranking functions
I'm working with Turing's paradigm to prove termination of programs by annotating functions with ranking functions and I encounter the following example:

```
def zeros: Stream[Int] = 0 #:: zeros

```

This is Scala syntax for contructing a stream made of an infinite number of zeros. In this case, the evaluation terminates but there is no (evident) measure that would prove it so?

Does this mean that the ranking functions paradigm is limited? Or is there a function stablishing termination of `zeros`?

* Turing, A. Checking a large routine. In Report of a Conference on High Speed Automatic Calculating Machines, 1949.

# Answer
I think Turing's method is probably fine, but you are mistaken about why exactly the code you wrote, "terminates."

First, note that this is not really (written as) a function at all. It is a self-referential value. And the reason the program terminates even though it's defined in it is that the program does not attempt to evaluate it fully. In this case, perhaps it would be all right, because a sufficiently smart evaluator would notice that there is a loop in the pointer structure, but there are other examples where that would not be sufficient.

So, these infinite structures are not something that you prove 'terminate' by showing they can be labelled by some finite size. Instead, they are not evaluated at all until something else demands to see the structure, and then they are unfolded as needed. This sort of structure is sometimes called, "coinductive," whereas the Turing methodology you're talking about is related to induction.

However, there is a property related to termination for coinductive things. For termination of inductive definitions, we label inputs with natural numbers (say), and ensure that this number decreases for recursive calls, which ensures termination. For coinductive definitions, we consider things like `#::` to increase size, and we want to ensure that the size of the *result* is *bigger* than the size of any recursive references. This ensures that we are incrementally producing more of the value after a finite amount of work, and this is referred to as the definition being, "productive."

The reason we care about this property is that we assume the parts of the program that cause the unfolding of the infinite values can only demand finite portions of them. If you can only look at a finite portion of a potentially infinite value, and the pieces each take a finite amount of time to produce, the overall computation terminates.

But, there is also a way to apply a more Turing-like methodology to this, and it is to recognize that streams could be implemented as functions. `Stream[Int]` is the same, in a way, as `Natural => Int`, where you ask for the value of the stream at a particular index, and it returns the value. And in this representation, productivity corresponds to the termination of the function for every natural number. In this case it's easy, because the function is `x => 0`, but other examples could require more sophisticated arguments.
> 5 votes

---
Tags: functional-programming, software-verification, termination
---


# Question
Title: Finding recurrence equation for a variant of insertion sort
I have a variant of Insertion sort (recursive version) that we call split insertion sort because there are two kinds of input. The input array has both numbers and alphabets, hence we have to sort them as two different arrays one for numbers and other one for alphabets. What would be the recurrence equatiuon for this variant of insertion sort

# Answer
> 1 votes
Insertion sort works as follows: At iteration $i$, we have $A\[1\ldots(i-1)\] $ sorted. So, the idea is to grab $A\[i\]$ and find the right position in $A\[1\ldots(i-1)\]$. Worst case would be for $A\[i\]$ to sit in the first position of $A\[1\ldots(i-1)\] $. Translating this to recursions, you will have \begin{align} T(n) &= T(n-1) + n\\ &=T(n-2) + n-1 + n \\ &= \vdots \\ &=T(n-k) + \sum\_{i=0}^k (n - i) \end{align} Algorithm terminates at $k = n$, i.e. we shall get $$T(n) = T(0) + \sum\_{i=0}^n (n - i)$$ where $T(0) = O(1)$. So, upon a change of variable, we get $$T(n) = \sum\_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$$

---
Tags: algorithm-analysis, runtime-analysis, sorting, recursion
---


# Question
Title: Count number of the ways to fill a N-lengthed binary string
From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more than $K$.

For $N \le 2\times 10^6$, my approach is to using DP. `dp[N][K][2]` is the number of ways to fill string of length $N$ with the current $1$'s consecutive sequence length is $K$ and last parameter is to tell whether the current string contains the $1$'s consective sequence of length $K$.

This would work if N is small enough but the constraints of this problem is : $1 \le N \le 10^{10}, 0 \le K \le 50$.

The approach I need is obviously Matrix Exponentiation so I can solve it in $O(\log N \times ?)$. Storing every possible binary strings of length K is not possible ($2^M$). Can anyone provide the solution of the problem? Or at least some hints

# Answer
Construct a DFA for your language (without the length $N$ restriction). It should contain $S = O(K)$ states. Consider the corresponding $S \times S$ matrix $A$, in which $A(s,t)$ is the number of characters that cause the DFA to move from state $s$ to state $t$. Let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then the number of words of length $N$ is $xA^Ny$. You can compute $A^N$ quickly using matrix exponentiation.
> 1 votes

---
Tags: algorithms, dynamic-programming, combinatorics, counting
---


title: Big O notation for Sorting Algorithm

text:
# Question
Title: Big O notation for Sorting Algorithm
I am interested to know whether the time complexity of following algorithm is $O(n^2)$ or $O(n\log n)$.

Here is the implementation:

```
public class HelloWorld
{

 public static void main(String[] args)
 {

    Hello hw = new Hello();
    int[] n = {2,3,4,52,5,63,0,664,2,2,56,68,8};
    hw.sortUsingDLLWODup(n);
 }
}

public class Node
{
   public int value;
public Node next;
public Node prev;
public Node(int v) {
    value = v;
}
}

public class Hello
{

public void sortUsingDLLWODup(int[] n) {

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0;i<n.length;i++) {
if(max<n[i])max = n[i];
if(min>n[i])min = n[i];
}

Node root = new Node(min);
Node end = new Node(max);
root.next = end;
end.prev = root;

for(int i = 0;i<n.length;i++)
{
    Node current = root;
    while(n[i]>current.value && current!=null) {
        current = current.next;
    }
    if(current!=null&&current.value>n[i]) {
        Node temp = current.prev;
        Node newNode = new Node(n[i]);
        temp.next = newNode;
        newNode.prev = temp;
        newNode.next = current;
        current.prev = newNode;
    }
}
Node test = root;
while(test!=null){

System.out.println(test.value);
test = test.next;
  }
}
}

```

# Answer
> 2 votes
You will have $O(n^2)$ in worst case. Actually what you do is really close to insertion sort. Worst case is attained when you got the array in decreasing order.

\begin{align} T(n) &= T(n-1) + n\\ &=T(n-2) + n-1 + n \\ &= \vdots \\ &=T(n-k) + \sum\_{i=0}^k (n - i) \end{align} Algorithm terminates at $k = n$, i.e. we shall get $$T(n) = T(0) + \sum\_{i=0}^n (n - i)$$ where $T(0) = O(1)$. So, upon a change of variable, we get $$T(n) = \sum\_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$$

# Answer
> 1 votes
The worst case will be $O(n^2)$ for the situation where each inserted number is greater than the previous number. This situation can be seen with an input array of ${1,2,3,4,5...10}$. You insert $1$, which must be compared with the min node and max node you set. Therefore, this is $2$ comparisons. The next number, $2$, must be compared with every number in the array since it will be the second largest number (next to the MAX\_VALUE node). This comparisons increase for the next number $3$ for the same reason.

Thus, the number of comparisons you have is effectively $2+3+4..+n+n+1 = n(n-1)/2 = O(n^2)$.

# Answer
> 1 votes
The worst case will occur when the elements of your array are already sorted i.e. already in ascending order.

Let the sequence be {1,2,3,4,5,6}. So initially the list will be like 1 -\> 6 , since we are fixing the min and max elements. Now first taking in account the comparisons for non min and non max elements i.e. 2,3,4,5.

1. For 2, we will have two comparisons (one with 1 and one with 6). Now with insertion of 2, the list becomes 1 -\> 2 -\> 6.
2. For 3, we will have three comparisons (with 1, 2 and 6). Now the list is 1 -\> 2 -\> 3 -\> 6.
3. Similarly for 4, we will have four comparisons and for 5 we will have five comparisons.

Now let us take in account the comparisons for min and max element. Since your algorithm makes comparison for them as well (which can certainly be optimized as you need not check for min and max elements).

The comparison count for min element is one, when we compare 1 with 1 itself. The comparison count for max element is n.length (length of the array) because we will need to compare it with each element in the list and with itself.

So, generalizing the number of comparisons and taking len = n.length, we have:

> $$\sum\_{i=1}^{len} i = len^2$$

So worst case complexity will be $O(len^2)$ where len is the length of the array to sort.

---
Tags: algorithms, algorithm-analysis, sorting
---


# Question
Title: Justification behind this heuristic in SMA*+
I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA\*+). In short, the authors propose a limited-memory version of A\* where we cull nodes if we are out of memory, to re-expand them later on.

To do this they choose the *worst node* to cull. And they propose a heuristic to maximize to choose what is considered the *worst node*:

> For example, a culling heuristic based on the ratio between f-cost and depth, given as $c(n) = f(n) / \ln(d(n) + e)$, where $e$ is Euler’s number, can improve performance on problems with many similar f-costs, if we can reasonably assume that the goal has a high depth.

A quick reminder, $f(n) = g(n) + h(n)$ where $g(n)$ is the cost to reach node $n$ and $h(n)$ is the heuristic to estimate the distance from $n$ to the goal node. $d(n)$ is the depth of the node.

The authors don't further elaborate on this. Is there some logical justification I'm missing for the formula $c(n)$, in particular the natural logarithm and adding $e$ to $d(n)$?

# Answer
From what I can tell the function $c(n)$ was just chosen as a reasonably simple trade-off between f-cost and depth.

It appears that $e$ is added to simply have the denominator $\ln(d(n) + e)$ always be $\geq 1$ and prevent $\ln(0)$.
> 1 votes

---
Tags: search-algorithms, heuristics
---


# Question
Title: What mathematical terminology exists for "embellished trees"?
I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology.

My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in the answer.

Say you have a particular Abstract Syntax Tree. Now you also have some editor that allows you to annotate arbitrary nodes in the tree by hand. For example to either highlight nodes, or tie particular textual annotations to nodes ("comments").

The datatypes that allow you to store the information as produced by this editor are somehow "embellished versions" of the original datatype for the AST. E.g. for each node we now have a node that also knows whether it is highlighted or not, and recursively contains such nodes. Values from such datatypes have at least the property that you can throw away the annotations and end up with the original tree.

There is also some notion of "coupling" between the embellished AST's nodes and the "underlying AST"'s nodes, i.e. we can always point at the "source" for any embellished node. This is also to say: if there are two ways of embellishing, we can connect them.

What is the proper framework to (generally) think about this?

# Answer
> 3 votes
A good framework for reasoning about this is research on "ornaments" which were introduced by Conor McBride here: https://personal.cis.strath.ac.uk/conor.mcbride/pub/OAAO/Ornament.pdf .

The idea of ornamentation is that you start with a simple algebraic data type and then you have a separate "ornamented" version of it where the constructors might have more information, which is especially useful in dependently typed programming because a lot of times you want to "adjoin" invariants to a datatype. For more on this, there is another article in the JFP: https://josh-hs-ko.github.io/manuscripts/JFP17.pdf

However, it seems like you are not interested in dependent type theory and have noticed that ornaments arise naturally in everyday programming. For that I would recommend reading about the work on using ornaments in OCaml, specifically this paper (http://pauillac.inria.fr/~remy/ornaments/mlorn-2017-09.pdf) which also has a tutorial for the library here: http://pauillac.inria.fr/~remy/ornaments/ocamlorn/doc/tutorial.html

# Answer
> 2 votes
I think I have heard the term "decorated trees" often but this is more a folklore term than a "framework".

---
Tags: terminology, functional-programming, category-theory
---


# Question
Title: Can a processor without stack pointer registers, have a subroutine calls and interrupts?
Suppose a processor does not have any stack pointer registers, which of the following statements is true?

1. It cannot have subroutine call instruction
2. It cannot have nested subroutines call
3. Interrupts are not possible
4. All subroutine calls and interrupts are possible

====================================================================

I think answer is 2.

Reason- Because in nested subroutine calls, we push old subroutines into stack and point most recent call with stack pointer.

Please, explain which is the correct option. According to book the answer is 1.

# Answer
The Control Data Cyber series had no stack pointer, but it had a Pascal compiler. Seymour Cray says your book is wrong. (The Subroutine Call instruction that this computer isn’t supposed to have would store the return address into the location after the instruction it branched to, forming an instruction that could be used to jump back to the caller). If your instructor doesn’t know who Seymour Cray is then they shouldn’t be teaching.

And there were microprocessors that handled interrupts by switching to a second set of registers. So the answer would be 4.
> 4 votes

# Answer
Depends on how exactly you define "stack pointer", "subroutine" and "nested subroutine" (I presume the latter means recursion).

If you disallow recursion you don't need a stack. To store your local variables and parameters you instead statically allocate space for them. They basically become globals. As long as you don't need to enter the same subroutine again there will be no problem.

And when you call the subroutine you pass along the return address as a (hidden) parameter and instead of return you jump to that return address. Stack-based `call` and `ret` instructions do this automatically pushing the next instruction address to the stack followed by jump and popping the return address followed by the jump resp.

Interrupts are in the same boat, except for how to automatically forward the resume address to the handler. One way is to hardcode a memory location or register for that.
> 2 votes

---
Tags: computer-architecture, stacks
---


# Question
Title: The notion of PAC in approximation algorithms
In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is there a way to generalize this idea for approximation algorithms? What I thought of:
Given a language $L \subseteq \\{0,1\\}^\*$, a confidence parameter $\delta\in\[0,1\]$, an error parameter $\epsilon \> 0$, and a distribution $D$ over $L$, the algorithm $A$ is a PAC algorithm for $L$ if with probability at least 1 - $\delta$ it holds that $\text{ERR}(A,D)\leq \epsilon$, where $\text{ERR}(A,D) := \Pr\_{x\text{~}D}(A \text{ answers wrong on } x)$.
One drawback of this definition is the following: suppose $L$ is a countable infinite set, and let $l\_1, l\_2,...,l\_k,...$ be some enumeration of the elements of $L$. Since $D$ is a probability distribution over $L$, $\sum\_{i}D(l\_i) = 1$, and hence there must be some index $k$ such that $\sum\_{j\>k} D(l\_j) \<\epsilon$.
The algorithm $A$ can be defined as: remember the answers of the first $k$ words. When receiving $w \in \\{0,1\\}^\*$ check if $w$ is saved (and if so answer correctly). Otherwise, answer "0".
Clearly this algorithm is a PAC by the above definition, but not a clever one.
Is there a way to define PAC algorithm for a formal language? Or: can we use the theory of machine learning in the theory of approximation algorithms?

# Answer
> 0 votes
Approximation algorithms don't make sense here, because here the output of the algorithm is 0 or 1. (0 represents "the input is not in $L$", 1 represents "the input is in $L$".) Approximation algorithms are useful when the output is a continuous variable, as then we can ask for the algorithm to output something that is close to the correct answer, but the concept is not useful when talking about algorithms that output a boolean.

Also, in your proposed definition, once you have fixed an algorithm $A$ and a distribution $D$ over $L$, the condition $ERR(A,D) \le \epsilon$ is either true or false. It's not an event that you can assign a probability to. So, it doesn't make sense to ask it to hold with probability at least $1-\delta$.

---
Tags: complexity-theory, machine-learning, approximation
---


# Question
Title: Does this excerpt from the linear probing Wikipedia page make an assumption?
Here is the excerpt from the linear probing page at Wikipedia.

> *To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and continuing to the adjacent cells h(x) + 1, h(x) + 2, ..., until finding either an empty cell or a cell whose stored key is x. If a cell containing the key is found, the search returns the value from that cell. **Otherwise, if an empty cell is found, the key cannot be in the table, because it would have been placed in that cell in preference to any later cell that has not yet been searched. In this case, the search returns as its result that the key is not present in the dictionary**.*

Does this assume that the linear probing function let's say P(x) is the same for insertion and searching? Must your linear probing function be consistent throughout the hash table? Is there a combination of linear probing functions that work best together?

# Answer
Yes, it is assumed that probing sequences are identical during the search and insertion. In theory you could use a different probing sequence (e. g. check h(x) index first, then h(x) + 2, and only then h(x) + 1), but it doesn't make any sense - you are better off always using the same sequence to have the minimal expected number of probes.
> 1 votes

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


title: Can we do 4-sum algorithm in O(n^2)?

text:
# Question
Title: Can we do 4-sum algorithm in O(n^2)?
this is related to the following question:

Generalised 3SUM (k-SUM) problem?

Without loss of generality, let's only consider even $k$, or just $k=4$.

My question is, after summing all pairs of numbers, is it necessary to sort the list of sums? I understand we could use two pointers from left and right to sandwich the two pairs in $O(n^2)$ time, but the sorting requires $O(n^2\log(n))$ time.

If we use a hashmap to store the sums as key and their corresponding index pairs as value, then all operations can run in $O(n^2)$ time.

Am I missing something in that post or is it true for even $k$, $k$-sum can run in $O(n^{k/2})$ time?

Thanks!

# Answer
> 4 votes
You are right, but Jeff's answer in the link you provided works in the "linear decision tree model". You cannot use hashing in that model.

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity, hash
---


# Question
Title: Trie traversal to maximise XOR in a tree but with a condition
Input:I am provided with x and y.

x is a 32 bit non negative integer and y is some node-id of the tree.

So, I built a trie with 32-bit non negative integer values which are the keys associated with each node-id of the tree (DAG). Now, if I am asked to find the a node, whose key XOR x is maximum. This can be easily be done in O(log n) just by traversing the trie.

Now here is the extra condition:

I want to find the key on the node in the path from root to that node y, for which x XOR (key) is maximum. How can we find this out efficiently? Preferably in O(log n).

# Answer
> 1 votes
You can simply use persistent tries.

Let $T\[x\]$ denote a trie containing all keys in the path from root to $x$, assume $y$ is a child of $x$, $T\[y\]$ can be constructed in $O(\log U)$ time from $T\[x\]$, where $U=2^{32}$. This is trivial even if you use normal tries; but the key point is "persistent" data structures enable you to store all $T\[\cdot\]$ at the same time. As an intuition, notice that when we construct $T\[y\]$ from $T\[x\]$, only $O(\log U)$ nodes in $T\[x\]$ changes.

---
Tags: algorithms, complexity-theory, graphs, trees
---


# Question
Title: Is binary-search really required in Chan's convex hull algorithm?
I have a little doubt about Chan's algorithm.

From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q\_i$. The goal of the second phase is to compute $m$ points $\\{p\_1 ... p\_K\\}$. On $i$-th iteration the candidate $p\_i$ is chosen among $\\{q\_1 ... q\_K\\}$, where $q\_j \in \mathcal{CH}(Q\_j)$ is a point such that every other point of $\mathcal{CH}(Q\_i)$ lies to the left of line $p\_{i - 1}q\_j$.

According to the Wikipedia page, each point $\\{q\_1 ... q\_K\\}$ of set is searched in $\mathcal{O}(\log m)$ using binary search, which is the main reason that whole second phase takes $\mathcal{O}(Kh + Kh \log m)$, where $h$ is the size of resulting convex hull (which is unknown at the beginning).

I doubt that it is necessary to perform this binary search for every candidate-point $q\_i$ on each iteration. I get that, when we just start with $p\_0$, there's no other way to do this. What about the following iterations? As I think of it, on each iteration the point $q\_i$ either stays the same or it changes to one of the successive point of $Q\_i$ in ccw-order. And one point cannot become a candidate more than twice (or even once?). If that is the case, why can't we use $K$-pointer technique and just set $q\_i \leftarrow q\_{i + 1}$ while $q\_i$ is not a tangent line for current iteration. There shouldn't be more than $2m$ candidate changes for each $Q\_i$ for all $m$ iterations. Wouldn't the resulting complexity $\mathcal{O}(Kh + Km)$ be better than $\mathcal{O}(Kh + Kh\log m)$?

And some pictures that aren't on wiki page to give a better idea of this second phase. The first one shows what are the candidates.

And the second one should provide an intuition about choosing $q\_i$ for the next iterations.

# Answer
I think this is correct... see 2. Chan’s Algorithm p4, Remark.

> *Remark.* Using a more clever search strategy instead of many binary searches one can handle the conquer phase in $O(n)$ time. However, this is irrelevant as far as the asymptotic runtime is concerned, given that already the divide step takes $O(n \log H)$ time.

Anyway, the complexity is bounded by the divide phase.
> 2 votes

---
Tags: algorithms, algorithm-analysis, computational-geometry, convex-hull
---


# Question
Title: Why does existence of predecessor imply adequacy of a numeral system?
I encountered this result when working with $\lambda$-calculus (so every element I mention here was a $\lambda$-expression there \[1\]), but I will express everything with, more understandable to broader audience, notions of functions.

## Intro

**Definition 1**
A *numeral system* is a sequence $d = d\_0,d\_1,\ldots$ such that there exist functions $S$ (successor) and $isZ$ (test for zero) such that $$S(d\_n) = d\_{n+1},$$ $$isZ(d\_0) = T,\ \ isZ(d\_{n+1}) = F.$$ where $T$ and $F$ are notions of true and false.

**Definition 2**
A numeric function $\varphi : \mathbb{N}^p \to \mathbb{N}$ is *definable with respect to $d$* if there exists $f$ such that $$\forall (n\_1,\ldots,n\_p)\in \mathbb{N}^p\ \ f(d\_{n\_1},\ldots,d\_{n\_p}) = d\_{\varphi(n\_1,\ldots,n\_p)}.$$

**Definition 3**
A numeral system $d$ is *adequate* if and only if all partial recursive functions are definable with respect to $d$.

## My question (intro)

**Proposition 1** *(Proposition 6.4.3 in \[1\])*
Let $d$ be a numeral system. $d$ is adequate if and only if there exists $P$ (predecessor) such that $$\forall n \in \mathbb{N}\ \ P(d\_{n+1}) = d\_n.$$

For the $\Rightarrow$ direction, it is sufficient to observe that predecessor is a partial recursive function. Specifically, it is a primitive recursion of zero function and first coordinate projection.

**My question**
How would one prove a $\Leftarrow$ direction? How is it even possible to have such a powerful result, that existence of one function leads to definability of all partial recursive functions?

---

\[1\] Hendrik Pieter Barendregt, *The Lambda Calculus*, 1984.

# Answer
> 4 votes
Recall that the set of partial recursive functions $\mathcal{R}$ is defined inductively by the following rules:

* (zero) $\dfrac{}{\zeta : n \mapsto 0 \in \mathcal{R}}$
* (successor) $\dfrac{}{\sigma : n \mapsto n + 1 \in \mathcal{R}}$
* (projection) $\dfrac{}{\Pi\_m^i : (n\_1, \cdots n\_m) \mapsto n\_i \in \mathcal{R}}$
* (composition) $\dfrac{\chi : \mathbb{N}^m \to \mathbb{N}, \psi\_i : \mathbb{N}^k \to \mathbb{N} \in \mathcal{R} }{\phi : (n\_1, \cdots n\_k) \mapsto \chi(\psi\_1(n\_1, \cdots, n\_k), \cdots \psi\_m(n\_1, \cdots, n\_k)) \in \mathcal{R}}$
* (primitive recursion) $\dfrac{\chi : \mathbb{N}^m \to \mathbb{N}, \psi : \mathbb{N}^{n+2} \to \mathbb{N} \in \mathcal{R} }{\phi : (k,n\_1, \cdots n\_m) \mapsto \begin{cases} \chi(n\_1, \cdots n\_m) & \text{ if } k=0 \\ \psi(\phi(k-1, n\_1, \cdots, n\_m),k-1, n\_1 \cdots n\_m ) & \text{ if } k \> 0\\ \end{cases} \in \mathcal{R}}$
* (minimalization) $\dfrac{\chi : \mathbb{N}^{m+1} \to \mathbb{N} \in \mathcal{R} }{\phi : (n\_1, \cdots n\_m) \mapsto k \text{, the least integer with } \chi(k,n\_1, \cdots n\_m) =0 \in \mathcal{R}}$

So we will prove the result by structural induction on $\mathcal{R}$.

* Initial functions.

It is clear that $\zeta$ is defined by $\lambda x. d\_0$, $\sigma$ by $S$, and $\Pi\_m^i$ by $\lambda x\_1 \cdots x\_m . x\_i$.

* Composition

Suppose $\chi$ is defined by $f$ and $\psi\_i$ by $g\_i$.

Let $h$ be the term $\lambda x\_1 \cdots x\_k.f (g\_1x\_1 \cdots x\_k) \cdots (g\_mx\_1 \cdots x\_k)$. Then $h$ defines the function $\phi : (n\_1, \cdots n\_k) \mapsto \chi(\psi\_1(\vec{n}), \cdots \psi\_m(\vec{n}))$

* Primitive recursion.

Suppose $\chi$ is defined by $f$ and $\psi$ by $g$.

Let's define the combinator $\textbf{r} = \lambda nfg.isZ\\:n\\:f\\:(g \\:(P\\:n))$, with the property that:

$$ \textbf{r} \\: d\_n \\:f \\: g = \begin{cases} f & \text{ if } n = 0 \\ g \\: (d\_{n-1}) & \text{ if } n \> 0 \end{cases} $$

Now let $h$ be the term $\textbf{y} \\: (\lambda s y x\_1 \cdots x\_m . \textbf{r} \\: y(f x\_1\cdots x\_m)(\lambda z.g (s z x\_1 \cdots x\_m)z x\_1 \cdots x\_m )$. Then $h$ defines $\phi: (k,n\_1, \cdots n\_m) \mapsto \begin{cases} \chi(n\_1, \cdots n\_m) & \text{ if } k=0 \\ \psi(\phi(k-1, n\_1, \cdots, n\_m),k-1, n\_1 \cdots n\_m ) & \text{ if } k \> 0\\ \end{cases}$.

* Minimalization

Suppose $\chi$ is defined by $f.

Let $g$ be the term $\textbf{y} (\lambda syx\_1 \cdots x\_m.isZ \\: (f\\: y\\: x\_1\cdots x\_m) \\: y\\: (s\\: (S \\: y)\\: x\_1 \cdots x\_m))$. Then take $h$ to be the term $g \\: d\_0$, and $h$ defines the function $\phi : (n\_1, \cdots n\_m) \mapsto k \text{, the least integer with } \chi(k,n\_1, \cdots n\_m) =0$.

By induction, every function in $\mathcal{R}$ is definable.

(I leave the proving the fact that the terms $h$ define the stated functions as an exercise!)

---
Tags: computability, lambda-calculus, numeral-representations
---


# Question
Title: Bisimulations: Proof that the following LTS are not bisimilar
I have the two LTS (labeled transition system) as seen in the following picture:  And the book is telling me that between those two LTS, their $1$ and $1'$ are non-bisimilar.

So I tried to get a bisimilation starting from the pair $\\{\\{1,1'\\}\\}$ by continuously extending it whenever I found a conflict, ending up with: $$\\{ \\{1,1'\\} ,\\{2,2'\\},\\{3,3'\\},\\{2,4'\\},\\{4,3'\\},\\{3,5'\\},\\{4,5'\\} \\}$$

Finally, to check whether it truly was a bisimilation, I checked for each pair each node, and asserted that all possible pairs of derivatives were part of the set.

I am arriving that they are a bisimilation - is the crux in the $a$'s and $b$'s?
(They didn't really explain what it means)

# Answer
The left diagram has a b and the right diagram has a c. Thus, the pair $(2,4')$ does not satisfy the conditions required to be a bisimulation. In particular, the book is correct that those two systems are not bisimilar.
> 2 votes

---
Tags: coinduction
---


# Question
Title: Can Multiprocessor Systems Implement Both Temporal Multithreading and Simultaneous Multithreading?
I am aware that multiprocessor systems often implement simultaneous multithreading in order to allow multiple threads to run on different CPUs. I am also aware that uni-core systems often implement temporal multithreading (fine-grained/preemptive or coarse-grained/cooperative) to allow for a more efficient use of the CPU through the use of context switches.

However, I am curious **whether it is possible (or logical) to have a simultaneously multithreaded system also allow for the time-sharing between threads on each CPU**, which is prevalent in temporal multithreading systems.

# Answer
> 0 votes
Sure. You can simultaneously run multiple threads on different CPUs in parallel; and also a single CPU can context switch between threads (i.e., both what you are calling simultaneous multithreading + temporal multithreading). Nothing prevents it.

---
Tags: concurrency, parallel-computing, threads, multi-tasking
---


# Question
Title: Could a Van Emde Boas tree be used for storing matrices?
I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix.

I was wondering if vEB trees could be used to such purpose as well. At the end of the day the dynamic set to be stored would be the pairs $(i,j)$ in lexicographic order. If $MN$ is the size of the matrix a vEB tree would allow the access to a specific entry in time $O(log(log(MN))$ which isn't bad, though the space requirement doesn't change, but maybe with some improvements something interesting could come out.

Is there some research in this direction? I quickly looked up on google doesn't seem anything specific comes out.

Thank you

# Answer
> 2 votes
Yes you are right; but actually I think what you need is a hash table, which supports insert, delete and find in O(1) (although it requires some randomization).

Of course, you can replace a hash table by a VEB tree, when the elements are integers. However, if you want to optimize the space usage, you still need hashing when constructing the VEB tree. Luckily, there's some data structure called Y-fast trie that supports operations similar to VEB tree, but only needs linear space, and is deterministic.

---
Tags: trees, matrices, numerical-algorithms
---


title: Closest Pair Algorithm

text:
# Question
Title: Closest Pair Algorithm
I want to find the most optimal algorithm for finding closest ordered pairs and link them.

For example: Go thru the vector, one by one

For each one set the next according to a set of various conditions

For example, something like:

A B X C Y Z D

First we will link A to B Then when we have a look at B, we will link B to C Next when we consider X, we will link X to Y Next when we consider C, we will link C to D ... and so on

Currently someone has completed this task with some nested loops that are genuinely sub-par and it completes in O(n^2) time. Not to mention it doesn't work. What might be a better algorithm?

Here is what the current algorithm is:

```
for(i in list)
  while (i and j) is not linked
     increment j
  if j is not the end
     while ++j is not the end
       if link exists (i and j)
       break
     end while
     set link i to j
  end if
end for

```

I was going to write my own but I have a feeling I've seen this problem before at university and there was a simple solution to it..? Can anyone point me in the right direction please?

# Answer
An alternative approach could be

1. Scan the vector and insert all elements into a self-balancing BST (AVL or Red-Black Tree etc etc, your pick) along with its index in the vector. $Node := (Value,VectorIndex)$
2. Then you have two choices

* Scan the vector again, and for each element, search for it in the BST, and find its successor. Link the element and its successor in the vector.
    * Do an inorder traversal of the BST and for every pair of consecutive nodes visited in the BST, link their corresponding elements in the vector.

Either way, step 1 and 2 each take $O(n\space log \space n)$, hence the total algorithm ends up with a time complexity of $O(n \space log \space n)$ and space complexity of $O(n)$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Counting number of perfect squares in an subarrays
A sequence is good if the bitwise AND of all its elements is a perfect square.

So counting number of "good" sequences, in a subarray .
For example : in \[1, 2, 3\]
There are 6 sub-sequences:

So there are 3 "good" sequences
Can you suggest an efficient approach to count them ?

# Answer
> 1 votes
Take random 64 bit integers. What are the chances that the AND of the first ten has more than one bit set? So for random numbers, I’d say the count is close to n^2 / 2, and it takes cn operations for small n to count them all.

If $x=0$ or $x=4^k$ then x is a square, and x AND y is a square for any y. So if the AND of the first five numbers for example is one of these squares, then the AND of the first six, seven, eight, ..., n numbers is a square. Here's a simple algorithm:

```
total = 0
for 1 ≤ i ≤ n
    x = (all bits set)
    for i ≤ j ≤ n
        x = x AND a[j]
        if x = 0 or x = 4^k for some k
            total += n - j + 1
            break from for loop for j
        else if x is a square
            total += 1

```

This works well when the numbers are random. To improve for the worst case (for example alternating between 2 and 3, where this simple algorithm would take quadratic time), calculate the AND of groups of 2, 4, 8, 16, 32 etc. numbers, and observe that when calculating the AND of say a million 64 bit numbers, there will only be 64 different values. This is slightly complicated but not hard to implement if you are really interested in the solution.

# Answer
> 1 votes
Let the sequence be $a\_1,\cdots,a\_n$, and let $A\_{i,j}=a\_i\text{ and }\cdots\text{ and }a\_j$. Assume each $a\_i$ has at most $w$(e.g. $w=32$) bits. Fix $i$ and let $j\geq i$ varies, $A\_{i,j}$ has at most $w'\leq w+1$ different possible values $A\_{i,j\_1},\cdots,A\_{i,j\_{w'}}$. For each distinct value we record the leftmost $j$ that generates it.

In $O(w)$ time we can compute the set of distinct values (as well as the corresponding range of $j$) of $A\_{i-1,j}$ from $A\_{i,j}$. Using this observation, we should be able to find an $O(nw)$ time algorithm.

---
Tags: algorithms, time-complexity, subsequences
---


# Question
Title: liskov substitution principle seems to have two conventional meanings
This is a question about the semantics of the name, rather than about the principle itself. What is the Liskov Substitution Principle (LSP)?

LSP seems to have two meanings in the literature I've seen. One statement is the rule that determines whether one function type is a subtype of another? I.e, A-\>Y is a subtype of B-\>X, if B is a subtype of A and Y is a subtype of X. The other statement is that in an object oriented language, a method in subclasses should be element of the subtype of the type of the method in the parent class.

The principle that B\<:A, X\<:Y implies A-\>X \<: B-\>Y was a known principle well before the name "Liskov Substitution Principle" was ever coined. I have found references to this principle from the early 80s.

For example, https://cl-su-ai.cddddr.org/msg04614.html, here is an email from 1987 where the author describes what he calls "PROBLEM II". It is the definition and justification for the definition of arrow types described above. Furthermore, this presentation, http://www.softwarepreservation.org/projects/LISP/crisp\_ibm370\_sdc/CRISP-talk.pdf, claims it was known in the early 1970s.

# Answer
> 4 votes
I don't think either of these is the Liskov substitution principle. My understanding of the principle is that for $S$ to be a subtype of $T$, it must be the case that we can substitute a value of type $S$ anywhere a value of type $T$ is required without compromising the correctness of our program.

Now, the subtyping rule for functions is probably a sufficient condition for the Liskov principle to be satisfied, as long as functions are sufficiently abstract. But this is not "the" principle, because it says nothing about anything that isn't functions.

Also, this page argues that subclassing in most OOP languages is insufficient to ensure the Liskov principle is satisfied. That is, it only ensures that the principle is satisfied with respect to other simple, declared subtyping relationships like you mentioned. It does not ensure that implicit invariants are respected, and indeed, it is possible to violate these invariants in a subclass. So the Liskov principle would say that sometimes sub-*class* does not imply sub-*type*.

It's probably also possible for this second argument to apply to "functions" in a language as well (although it would be pretty unsatisfactory), in which case the Liskov principle would not validate the induced subtyping rule.

---
Tags: type-theory, history
---


# Question
Title: Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$
I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$.

The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that runs in $s(n)$ space can have as a combination of the number of states, head positions, and contents of the tape, but I do not see how this number is arrived at.

Can someone explain?

# Answer
Suppose that $M$ is a deterministic Turing machine that runs in space $s(n)$ and halts on all inputs. We show below that $M$ has $U(n) = 2^{O(s(n))}$ many configurations. I claim that if $M$ doesn't halt within $U(n)$ steps, then it never halts; since we assumed that $M$ always halts, this means that it always halts within $U(n)$ steps. To see the claim, let $\sigma\_0,\ldots,\sigma\_{U(n)}$ be the configurations after $0,\ldots,U(n)$ steps. Since there are only $U(n)$ different configurations but $U(n)+1$ many $\sigma\_i$'s, there must be $i\<j$ such that $\sigma\_i = \sigma\_j$. Therefore starting at $\sigma\_i$, the machine will repeatedly go through the configurations $\sigma\_i,\ldots,\sigma\_{j-1}$, and in particular, will never halt.

It remains to count the number of configurations. Suppose that $M$ has $Q$ states, $C$ tapes, and tape alphabet $\Sigma$. We can describe a configuration of $M$ by specifying the state ($Q$ options), the head locations ($s(n)^C$), and the tape contents (at most $|\Sigma|^{Cs(n)}$; in these bounds we used the fact that at most $s(n)$ cells are used in each tape. In total, the number of configurations is at most $$ U(n) = Q s(n)^C |\Sigma|^{Cs(n)}. $$ You can show that $U(n) = 2^{O(s(n))}$ using standard manipulations, completing the proof.
> 1 votes

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


# Question
Title: How can I efficiently generate the shortest list of arguments for the range() function that will generate a given list of integers?
I ran into an interesting problem at work when trying to generate the inputs for an API given the expected output. I've tried to formalize and anonymize the problem below. I've been trying to design a fast algorithm that works here but I'm a little stuck. Thanks in advance for the help! I'm not an experienced question writer so please feel free to edit this to make it clearer. I'll do my best to answer any clarifying questions.

# Background

In python 2.7, the `range` function takes 3 arguments (start, stop, and step) and returns a list of integers.

> The full form returns a list of plain integers \[start, start + step, start + 2 * step, ...\]. If step is positive, the last element is the largest start + i * step less than stop; if step is negative, the last element is the smallest start + i * step greater than stop.

Documentation

## Examples

```
>>> range(0, 30, 5)
[0, 5, 10, 15, 20, 25]
>>> range(0, 10, 3)
[0, 3, 6, 9]

```

---

# Problem

Given a list of positive integers, I, generate a list of 3-tuples that when fed into the `range()` function that will generate the same set of integers as I. The answer list must be the minimum possible length. If more than one minimum length solution exists, return any of the solutions.

### Examples

```
Input: [1, 2, 3]
Output: [(1, 4, 1)]

Input: [1, 2, 3, 5, 7, 9]
Output: [(1, 4, 1), (5, 10, 2)] or [(1, 10, 2), (2, 3, 1)]

Input: [1, 2, 4, 5, 6, 11, 12, 13]
Output: [(1, 3, 1), (4, 7, 1), (11, 14, 1)]

```

# Answer
I'm assuming the input does not have duplicates, e.g. not `[1, 2, 2, 5]`.

---

No, an efficient (polynomial time) algorithm does not exist to our best knowledge, as per *"Covering a set with arithmetic progressions is NP-complete"* by *Lenwood S.Health*.

But we can make a recursive algorithm regardless, it will just be exponential time as our input grows.

Note that the first element not covered by previous ranges must be the start of the next range. Furthermore, you can always cover at least two elements with each range. And even better, the second element you choose to cover with a range also fully determines that range. The stop condition doesn't really matter - you'd just stop when the next element generated wouldn't be in the set.

With this information you can write a recursive algorithm (which assumes `l` is given sorted):

```
def cover_ap(l):
    if not l: return []
    if len(l) == 1: return [(l[0], l[0])]

    candidates = []
    a = l[0]
    for b in l[1:]:
        ap = [a, b]
        step = b - a
        k = b + step
        while step > 0 and k in l:
            ap.append(k)
            k += step
        stop = ap[-1] + 1

        remain = sorted(set(l) - set(ap))
        candidates.append([(a, stop, step)] + cover_ap(remain))

    return min(candidates, key=len)

```
> 3 votes

---
Tags: algorithms, time-complexity, subsequences
---


# Question
Title: Polynomial Complexity (Relative to the Size of the Input)
I came across the following statement:

"Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial."

I suppose it has something to do with the notion of polynomiality in terms of the input. All three variables are given as input. I am still not sure why it wouldn't be polynomial if $b$ was as big as $n$.

We could say $O(n + mn)^3)$ then which would be dominated by $O((mn)^3)$ for $m \geq 0$. It is even given, that $m \leq n$ which means that we can say $O(n^6)$ as worst case.

Now I would say this is certainly polynomial, because our solution is of the form $O(n^c)$ with $c \in \mathbb{R}$ which means that it is polynomial in the size of $n$.

What am I missing here?

# Answer
> 2 votes
The statement meant to say that "if b is **asymptotically** smaller than n" i.e. $b=o(n) \space or \space b=O(n)$.
If $b$ was asymptotically larger than $n$, i.e. $b=\omega (n) \space or \space b=\Omega(n)$, then the complexity would become, $O(b^3)$, i.e. not polynomial in $n$.
For example, lets consider two cases.

1. $b$ is asymptotically smaller than $n$, i.e. $b=O(n)$. $$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$ $$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$ We know that $b=O(n) \implies bn=O(n^2),\space bn^2=O(n^3) \space and \space b^2n=O(n^3). $
From this, we can conclude that, $m^3b^3=O(3nm^2b^2)$, $3nm^2b^2=O(3n^2mb)$, and $3n^2mb = O(n^3)$. $$\implies O((n+mb)^3)=O(n^3)$$
2. $b$ is asymptotically larger than $n$, i.e. $b=\Omega(n) \space or \space n=O(b)$. $$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$ $$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$ We know that $n=O(b) \implies nb=O(b^2),\space nb^2=O(b^3) \space and \space n^2b=O(b^3). $
From this, we can conclude that, $n^3=O(3n^2mb)$, $3n^2mb=O(3nm^2b^2)$, and $3nm^2b^2 = O(b^3)$. $$\implies O((n+mb)^3)=O(b^3)$$

In your approach, assuming $b$ to be **numerically** smaller than $n$ would lead to correct analysis. But what the statement means is that $b$ is **asymptotically** smaller than $n$. Like, $b=log(n) \space or \space b=\sqrt{n} \space or \space b=log(log(n))$

---
Tags: complexity-theory, polynomial-time
---


title: What does ∈ mean in the exponent?

text:
# Question
Title: What does ∈ mean in the exponent?
I'm having troubles understanding the following proof: $$ \begin{align\*} &\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log\_a(n) \\ &\Longrightarrow \ln(a(n)) = \log\_2(e)\ln^2(n) \ll n^{0.01} = \ln(d(n)) \\ &\Longrightarrow a(n) \ll d(n) \end{align\*} $$ The topic is Big O comparisons. The proof is about $a(n)= n^{\log\_2 n}$ and $d(n) = e^{n^{0.01}}$. The proof is very heavy in mathematical notation. I'm not sure what ∈ means in the example. I know that it denotes set membership in a more usual case, but have never seen it in the exponential position.

# Answer
That's not $\in$ but $\epsilon$: that is, a lowercase Greek letter epsilon. It's normally written $\varepsilon$ instead for clarity, but this author chose to use the "lunate" form for unknown reasons.

In this case, epsilon is being used as a shorthand for "an arbitrarily small but positive real number". This should probably be explained in the proof, but it's a fairly common shorthand in mathematics (for example, delta-epsilon proofs, floating-point epsilon…).

In other words, it's saying that the log of $n$ is always asymptotically smaller than $n$ raised to any positive power. In the next line it substitutes in a definite value, 0.01, for epsilon.
> 4 votes

# Answer
It's a variable name, like any other. In your property you could rename it to (e.g.) $b$, turning $$\forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log\_a(n)$$ into $$\forall b \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^b \gg \log\_a(n)$$

That's it.

---

Why calling it $\epsilon$, then, instead of a more common variable name?

In maths, it is common to call such variable $\epsilon$ when you could restrict its range to any positive interval $(0,x)$ with $x\>0$ and get a completely equivalent statement, no matter how small the interval is. That is, instead of proving $\forall b \in \mathbb{R}^+$ we could only prove $\forall b \in (0,10^{-8})$ and that would be just as good. Indeed, once it is proven for the small interval, it's easy to extend the result to all positive reals.

In a nutshell it conveys the idea that "only small positive values actually matter".

This is a sort-of implicit statement which is suggested every time $\epsilon$ is used. You can safely neglect this "hint" to the reader, and take the statement as it is.
> 0 votes

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


# Question
Title: Does this "reference" problem have a name?
I have the following problem which I think is so common that I expect it to have an official name (and standard algorithm of course). The situation is as follows: I receive distinct items (A...E in the below sketch) one after the other. Each item has a relation which can generally be termed "descendance" or "family" and is in itself anonymous - the only requirement is that an item can only belong to one family and that it must somehow be possible to distinguish the families. Items keep coming in and are referenced to their own family (like A and B in step 1), but sometimes an item can change the situation for other items already received: see the second step of the sketch: a connection in C points back to A and B and revokes their original descendances and points them to the family of C. Such connections are transitive, which can be seen in step 3: the connection between E and C also converts the descendance of A and B to the new family of E.

The task I need to solve is to keep the descendance relation correct for all items. It may look trivial but the solution that I am looking for should be O(n), n == number of items. Is there a name (and most likely a different description) of the problem in literature?

# Answer
This is **disjoint-set data structure**.

Here is the summary at Wikipedia. I put the statement about time-complexity in bold font to emphasize its efficiency.

> In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. **It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set.** In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

There are many tutorials for this data structures on the web, such as the one at TopCoder and the one at GeeksforGeeks.
> 3 votes

---
Tags: algorithms, data-structures, reference-request
---


title: Find the language an NFA recognizes

text:
# Question
Title: Find the language an NFA recognizes
For example, I have an NFA $A\_n$ with alphabet $\Sigma = \\{0, 1\\}$.

The language recognized by this NFA is known to be $\\{u1v\ |\ u, v \in \Sigma^\*, |v| = n − 1\\}$.

I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q\_1$, plus the $q\_n$ toward $s$. I know without the edge $q\_n \rightarrow s$, the answer should be $\\{0,1\\}^\* \cdot 1 \cdot \\{0,1\\}^{n-1}$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?

# Answer
> 5 votes
The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.

# Answer
> 2 votes
Let $r=\\{0,1\\}^{\*}\cdot1\cdot\\{0,1\\}^{n-1}$, be the RegularExpression representing the path $s$ to $q\_n$.

Now including the transition from $q\_n$ to $s$, $r$ becomes $R=r\cdot(\\{0,1\\}\cdot r)^{\*}$. In $r$, the starting $\\{0,1\\}^{\*}$ is the superset of $r$'s ending $\\{0,1\\}^{n-1}$.

That is, $\\{0,1\\}^{n-1} \in \\{0,1\\}^{\*}, \forall n \ge 1$
$\\{0,1\\} = \\{0,1\\}^{2-1} \space \implies \\{0,1\\} \in \\{0,1\\}^{\*}$.

This means that in $R$, ending of the every $r$ concatenates with $\\{0,1\\}$ inside the brackets of $R$ to becomes $\\{0,1\\}^{n}$. Now this overlaps with $\\{0,1\\}^{\*}$ from the start of $r$ to become $\\{0,1\\}^{\*}$. This becomes recursive and eats up the entire regular expression.
$\implies \space R = r \space and \space R=R\cdot(\\{0,1\\}\cdot R)^{\*}$

Hence, $R=\\{0,1\\}^{\*}\cdot 1 \cdot \\{0,1\\}^{n-1}$.

**Note**
You can alternatively prove this by expanding and rearranging $R=r\cdot(\\{0,1\\}\cdot r)^{\*}$.

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


# Question
Title: Algorithm and Formalism for Most Remote Vertices
In the graph below, **N** and **M** are most remote, and **H** is also an extremum.

Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the subject? Does an algorithm exist for finding the most remote edges of a graph?

Please note that I am not asking you to invent an algorithm, but I'm asking for information.

# Answer
One way to formulate your problem is well known as **finding the diameter of a graph** as the following description in Wikipedia.

> The diameter $d$ d of a graph is the maximum eccentricity of any vertex in the graph. That is, $d$ is the greatest distance between any pair of vertices or, alternatively, $d=\max\_{v\in V}\epsilon (v)$. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.
>
> A peripheral vertex in a graph of diameter $d$ is one that is distance $d$ from some other vertex—that is, a vertex that achieves the diameter. Formally, $v$ is peripheral if $\epsilon (v)=d$.

Similarly to the way we talk about the diameter of a circle, the term "diameter of a graph" is overloaded. It can also mean, although less frequently, any shortest path between any two vertices whose length is equal to the maximum eccentricity.

**If the graph is a tree, there is an algorithm that finds its diameter using only two BFS scans**. Choose an arbitrary vertex $v$. Do a breadth first search from $v$ that finds a vertex that is farthest away from $v$. Call the vertex $u$. Do another BFS from $u$ that finds a vertex that is farthest away from $u$. Call the vertex $u'$. The distance between $u$ and $u'$ is the diameter of the graph.

**In a general graph, many algorithms can be used to to find the diameter of a graph**. Please check this CS StackExchange question and answer, where most algorithms are in fact designed to solve the all-pairs-shortest-path problem.

In the example graph given in the question, the distance between $N$ and $M$, 9, is the diameter. In fact, $N$ and $M$ are the only two peripheral vertices in that graph. (OP calls peripheral vertices as most remote). However, $H$ is not a peripheral vertex, since the furthest distance from any vertex to $H$ is only 8. ($H$ is not a pseudo-peripheral vertex, either.)

We could **define an extremum of a graph as a vertex whose eccentricity is not smaller than the eccentricity of any of its neighbors**. We could also **define a strong extremum of a graph as a vertex whose distance to any vertex $v$ is not smaller than the distance from any of its neighbors to $v$**. Every peripheral vertices is an extremum and every strong extremum is an extremum. We can recall a leaf vertex of a graph means a vertex of degree 1. Every leaf is a strong extremum. Note that **$H$ is a leaf**. All those algorithms that compute all-pairs-shortest-paths can be adapted easily to find all (strong) extremum vertices as well. A simple degree-counting algorithm will find all leaves of a graph. (Please note this definition of "extremum" might not be standard at all. As far as I have tried, I have not found a single article that defines that concept. Well, I can only check probably a negligible number of articles among a myriad of them. There is probably some existing term for it in papers about social network.)
> 2 votes

---
Tags: graphs
---


# Question
Title: How to know if a code is Huffman or not without having the probability of each codeword?
I am new to Huffman coding and I find myself facing a lot of confusion as to how to determine if a code is Huffman or not without having the probabilities associated to each codeword. I know one way is look at whether or not the code is prefix. If not, then it's not a Huffman code. If yes, then we need to check if it gives the shortest possible length, *but we don't know the probabilities*. How do we ensure the code guarantees the shortest possible length in such case? To illustrate my question, let us look at the following two examples:

> ### Example 1: $\\{00,01,10,110\\}$
>
> The code is a prefix code, but is the length minimal? I mean it's a bit unusual for me to see Huffman code for $4$ symbols that does not have one-bit codeword for one of its symbol (the symbol with highest probability), but them I thought maybe the first three symbols are equally probable. As such, I tried to find the Huffman code for $\\{0.33,0.33,0.33,0.01\\}$ and got $\\{00,01,10,11\\}$ with different orders (depending on the usage of $0,1$ or $1,0$ in the tree). This led me to thinking that the code under investigation might not be Huffman, yet I am still not sure.
>
> ### Example 2: $\\{01, 10\\}$
>
> Again another unusual prefix code as the obvious choice (and the one with minimal length) for two symbols would be $\\{0, 1\\}$. But could it be the case that $\\{01, 10\\}$ can possibly give a minimal length? I can *not* see any possible probabilities in which this is the case, thus I believe this is *not* a Huffman code.

Am I on the right track? Does there exist an *actual* method to check whether or nor a code is Huffman without having the probabilities?

# Answer
> 4 votes
If you have a Huffman code, and the codes have lengths $l\_i$, then the sum over $2^{-l\_i}$ must be equal to 1. In your case, that sum is 1/4 + 1/4 + 1/4 + 1/8 = 7/8 \< 1, therefore not a Huffman code. You can replace the code 110 with 11.

(I am quite sure you can prove that for any prefix code, the sum is ≤ 1. And I'm quite sure you can prove that if the sum is less than 1, then there is some bit that you can remove from some code with the code remaining a prefix code, and since there is a finite number of bits to remove, the sum must become 1 eventually).

# Answer
> 2 votes
When a frequency tree is built for a message upon its characters, the leaf nodes of the tree are the characters composing the message with their frequency and internal nodes just have a frequency sum of all its descendents.
**The characteristic property of frequency trees for Huffman encoding is that, all internal nodes have exactly two children.**

For your example 1, $\\{00,01,10,110\\}$, the frequency tree would be something like this (forgive me for how the tree looks like. Subtrees are denoted by + and the first subtree is the left subtree and the second is the right subtree):

```
(root)
+ (0)
|  + (0) (leaf)
|  + (1) (leaf)
+ (1)
   + (0) (leaf)
   + (1)
      + (0) (leaf)

```

The subtree $\\{root,1,1\\}$ has one child, not two. Hence, such a prefix code can not be a Huffman encoding for any message. Similarly for example two, subtrees $\\{root,0\\}$ and $\\{root,1\\}$ have exactly one child.

---
Tags: huffman-coding
---


# Question
Title: Which is the fastest method for calculating exact square root of a integer of 200-500 digit number?
I wanted to know is there any algorithm / function / process through which I can calculate square root of a very large integer number. I wants to know current state of the research in this field.

No approximate methods please.

# Answer
> 4 votes
It seems a bit surprising that you did not find the Wikipedia article on integer square root where the Newton's algorithm is described in detail.

Here is the implementation in Python:

```
def integer_sqrt(n):
    """Compute the integer square root of n, or None if n is not a perfect square."""
    x = n // 2
    while True:
        y = (x + n // x) // 2
        if abs(x - y) < 2: break
        x = y
    return (x if x * x == n else None)

```

This takes about 0.018 seconds for a 1000 digit number on my MacBook Air. It's not clear why you're asking for the particular range between 200 and 500 digits, but I think you should be able to go on from here, especially if you take the time to read the Wikipedia page.

You may also be interested in the Rosetta Code integer roots page, where you can find fast implementations of integer root algorithms in many languages.

By the way, I just googled "integer square root" to find all of this, except I wrote the Python code.

# Answer
> 0 votes
That’s quite trivial. First, you use Newton iteration to get the square root of 1/x, which doubles the number of correct digits in each step and uses only multiplications. Multiply the result by x, then calculate the square to see if x equals a square.

No research needed, it’s all quite simple and public knowledge.

You found a website that advises you to use the Newton method for f(x) = x^2 - 612 to find the square root of 612. Use the Newton method for f(x) = 1/x^2 - 612 and you find the square root of 1/612 *without any divisions*, multiply by 612 and you have the square root of 612.

If you double the precision for each iteration step and use trivial O (n^2) multiplication, it takes $O (n^2)$ with a very small constant factor. If you use FFT for the multiplication (for large n, say a million digits), I'd say $O (n log^2 n)$

With your 100 digit example, double precision gives you a first approximation to $x^{1/2}$ with 15 digit precision, two iterations using 30 and 60 bit precision give you a solution with about 60 digits precision, you round that to the nearest integer and calculate the square with 100 digits precision and you're done. The last step is usually not needed if your result is far enough away from an integer.

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


# Question
Title: Can area-partitioning lose included points due to floating point precision?
I'm currently partitioning a big area $A$ into $n$ areas $B\_i$ such that $$\bigcup\_{i=1}^n B\_i = A$$

I have geo-coordinates which I know are in $A$ (also with the finite precision of floats).

Obviously, for every point $p$ in $A$ there has to be an area $B\_i$ such that the point is in $B\_i$. Formally:

$$p \in A \Rightarrow \exists i: p \in B\_i$$

But due to floating point precision, I wonder if it could happen that for all $B\_i$ the `B_i.intersects(p)` method returns false. Formally:

$$\forall i: \neg B\_i.\texttt{intersects}(p)$$

All areas are polygons and neighboring polygons share some points which define the polygons.

If the answer is yes, then an example would be good. It would be awesome if one could also quantify the probability of this.

(In my current case, I use shapely.)

# Answer
This is a problem for anyone making graphics cards: To draw an area, it will usually be split into triangles, and for many drawing methods it is important that every point is drawn exactly once.

At some point you'll have use an algorithm that decides whether a point x is on or above a line l, and at some other point you'll have an algorithm that decides whether x is below the line l. For good results, you need to design this algorithm carefully so it is guaranteed to say "YES" once and "NO" once. It doesn't matter too much whether the result is correct (not saying YES when the point is actually just a tiny bit below the curve), what's important is that the answer is "YES" exactly once and not twice.
> 1 votes

# Answer
Yes it is possible.

For example, look at this C code.

```
#include <stdio.h>

int main ()
 {
  float a=10.3346714;
  float b=10.3346711;
  printf("a=%.15f\nb=%.15f\n",a,b);
 }

```

It outputs the following upon execution.

> a=10.334671020507812
> b=10.334671020507812

Lets say your area $A$ was defined as $\\{ -10.3346714 \lt x \lt 10.3346714, -20.6693428 \lt y \lt 20.6693428\\}$
and it is divided into two equal regions by the line $x=0$
Lets call these two regions $B\_{left},B\_{right}$.
Now we have our point $p = (10.3346711,2.0000000)$.
From a purely mathematical point of view, we can see that $p \in A\space and \space p \in B\_{right}$.
But if a computer were to perform this check using floating point numbers, for the region $B\_{right}$, i.e $p \in B\_{right}$, it would do so by comparing $p$ with the rightmost boundary of $B\_{right}$ like $10.3346711\lt10.3346714$, which would be false, since both floating point numbers are the same when stored in memory.
The same would happen for checking $p \in A$. Which means $p \notin A \space and \space p \notin B\_{right}$ (Atleast as per the computer).

**Note**
This check would fail only if $p$ lies very close to the boundary of $A$. Other interior points would ultimately reside on either sides of a boundary i.e. in either regions around a boundary.
> -1 votes

---
Tags: computational-geometry, floating-point
---


# Question
Title: How to construct the found path in bidirectional search
I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (closed lists). How can I get the solution (path from the start to the goal), when I find that a state that is checked by one of the searches is in the closed list of the other?

EDIT

Here are the explanations from the book: *"Bidirectional search is implemented by having one or both of the searches check each node before it is expanded to see if it is in the fringe of the other search tree; if so, a solution has been found... Checking a node for membership in the other search tree can be done in constant time with a hash table..."*

Some pages before: *"A node is a boolkkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world... two different nodes can contain the same world state, if that state is generated via two different search paths."* So from that I conclude that if nodes are kept in the hash tables than a node from the BFS started from the start node would not match a node constructed from the other BFS started from the goal node.

And later in general Graph search algorithm the states are stored in the closed list, not the nodes, but it seems to me that even that the states are saved in the hash tables after that the nodes are retrieved from there.

# Answer
Let me give this question a try. I am not sure I do fully understand it so I was considering to post a comment but in the end, I preferred to try an explanation. Hope it helps!

Raphael already suggested a solution (so I voted up his comment) which works even if you only store states instead of nodes. To make it clear:

* **states**: those in the original problem. These are unique
* **nodes**: those enumerated by your search algorithm (bidirectional breadth-first search in your case). As stated in your book "*two different nodes can contain the same world state, if that state is generated via two different search paths*" so that it is very likely to have more nodes than states (since the former distinguish states by the different paths ---which can be exponentially large--- that lead to the same state).

Obviously, the path from the start state $s$ to the target $t$ is computed by concatenating the paths from $s$ to $n$ and from $n$ to $t$ where $n$ is the node that was found in the hash table of the opposite search.

Now, assuming you are using a consistent-heuristic function (a heuristic function $h (n)$ is said to be consistent if and only if it satisfies the triangular inequality $h(n) \leq c(n,m) + h(m)$ where $c(n,m)$ is the cost of the operator from node $n$ to one of its offsprings $m$) or no heuristic function at all (so that your BFS is a blind search) let me suggest the following procedure:

Let me assume wlg that $n$ was generated by the forward search (i.e., from the start state $s$) and that it was found in the hash table of the backward search (i.e., the one issued from the goal node). In this case it suffices to expand the node $n$ and to select *any* descendant that appears also in the hash table of the backward search. You can do this since you are storing all states (instead of nodes) in both hash tables. No matter of the difference between nodes and states, if you generated $n$ in the backward search (which results from the fact that it is stored in the hash table) it had to be done via one of its parents which can be recovered now as one of its descendants (assuming you are traversing undirected graphs, otherwise just apply the inverse operators to recover the parents). Acting like this you will eventually get to the target node.

The same mechanism applies to the forward search ---i.e., no need to store with each node its path to the start node, just use the closed list implemented as a hash table. Reverse the path obtained in the previous paragraph, concatenate them and there you are a solution path.

If you are not using a consistent heuristic function, then you should store along each node in the hash table its value $g(n)$ ---i.e., the cost of the path from its corresponding root node, either $s$ or $t$. Doing so, the previous procedure is just slightly modified by selecting the parent (now generated as a successor) whose $g$ value is $g(n)-1$. However, this is not even necessary in case you are seeking (as it seems) any path from $s$ to $t$.

Bidirectional search is one of the most intriguing "paradigms" in heuristic search. Noone has already found a simple way that makes it as efficient as in the case of blind search (where it is clearly a winner).

Hope this helps,
> 4 votes

# Answer
Just have a dictionary storing where each node came from. So each time you expand a node, you mark all its neighbors that the neighbor came from node.
eg breadcrumbs\[neighbor\] = node

Then when you reach the goal, you just loop through your dictionary back to the start.
> 0 votes

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


# Question
Title: An algorithm to turn descending order into ascending order, but why correct?
Why is this sort algorithm correct? Many thanks!

# Task:

Suppose all elements in an array with length $n = 2^m$ are in descending order: $a\_1 \> a\_2 \> ... \> a\_n$, we need to turn them into ascending order.

# Algorithm:

For each step from $1$ to $m$:

1. Swap each adjacent (odd index, even index) pair into ascending order, so that: $a\_1 \le a\_2, a\_3 \le a\_4, ... , a\_{n-1} \le a\_n$
2. Move all elements with odd index to the front of those with even index, so $a\_1, a\_2, a\_3, a\_4, ..., a\_{n - 1}, a\_n$ turns to : $a\_1, a\_3, ..., a\_{n - 1}, a\_2, a\_4, ..., a\_n$

# Example:

Sort result after each step with $n = 8$:

\[0\] 8 7 6 5 4 3 2 1
\[1\] 7 5 3 1 8 6 4 2
\[2\] 5 1 6 2 7 3 8 4
\[3\] 1 2 3 4 5 6 7 8

# Code:

```
#include <stdlib.h>

void swap(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void magic_sort(int *arr, int *result, int n)
{
    int half = n >> 1;
    int i;

    /* Swap adjacent (odd index, even index) pair into ascending order */
    for (i = 1; i <= n; i += 2)
    {
        if (arr[i] > arr[i + 1])swap(arr, i, i + 1);
    }

    /* Move all elements with odd index to front half */
    for (i = 1; i <= n; i += 2)
    {
        result[(i + 1) / 2] = arr[i];
    }

    /* Move all elements with even index to tail half */
    for (i = 2; i <= n; i += 2)
    {
        result[half + i / 2] = arr[i];
    }

    for (i = 1; i <= n; i++)
    {
        arr[i] = result[i];
    }
}

int main()
{
    int m = 3;
    int n = 1 << m;
    int *arr = (int *)malloc(sizeof(*arr) * (n + 1));
    int *result = (int *)malloc(sizeof(*arr) * (n + 1));
    int step, i;

    printf("[%d] ", 0);

    for (i = 1; i <= n; i++)
    {
        arr[i] = n + 1 - i;

        printf("%d ", arr[i]);
    }

    printf("\n");

    for (step = 0; step < m; step++)
    {
        magic_sort(arr, result, n);

        printf("[%d] ", step + 1);

        for (i = 1; i <= n; i++)
        {
            printf("%d ", arr[i]);
        }

        printf("\n");
    }

    free(arr);
    free(result);

    return 0;
}

```

# Answer
This is an interesting algorithm.

## Conventions

**Array indexes start with 0. Note this convention is different from the convention used in the question.** This convention helps us see what is going on more easily.

All arrays have length $n=2^m$ for some positive integer $m$.

Given any array $b\_0, b\_1, b\_2, b\_3,\cdots, b\_{n - 2}, b\_{n-1}$, the magic shuffle $M$ maps it to the array $b\_1, b\_3, \cdots, b\_{n-1}, b\_0, b\_2, \cdots, b\_{n-2}.$ Please note that I avoid using the term "sort" since this algorithm is hardly about sorting.

Let $A\_0$ be the array $a\_0, a\_1, \cdots, a\_{n-1}$ (that is, $A\_0\[i\]=a\_i$). Define $A\_k$ recursively by $A\_{k+1}= M(A\_k)$.

## Claim: $A\_m$ is the reverse of $A\_0$, which is $a\_{n-1}, a\_{n-2}, \cdots, a\_0$.

**Proof of the claim.** For an array $B$, we can check by the definition of the magic shuffle, $$M(B)\[i\] = \begin{cases} B\[2i+1\] & \text{ if }i\lt 2^{m-1},\\ B\[2(i-2^{m-1})\]&\text{ if } i\ge 2^{m-1}.\end{cases}$$

For an integer $i=i\_{m-1}2^{m-1} + i\_{m-2}2^{m-2} + \cdots + i\_12 + i\_0$, where $i\_t\in\\{0,1\\}$, let $(i\_{m-1}i\_{m-2}\cdots i\_1i\_0)\_2$ be its representation in base 2. We can easily check that

$$M(B)\[(i\_{m-1}i\_{m-2}i\_{m-3}\cdots i\_1i\_0)\_2\] = B\[(i\_{m-2}i\_{m-3}\cdots i\_1i\_0\overline{i\_{m-1}})\_2\]$$ where $\overline{x}=1-x$ for $x=0,1$. So we have $$A\_1\[i\] = M(A\_0)\[i\] = A\_0\[(i\_{m-2}i\_{m-3}\cdots i\_1i\_0\overline{i\_{m-1}})\_2\]$$ $$A\_2\[i\] = M(A\_1)\[i\] = A\_1\[(i\_{m-2}i\_{m-3}\cdots i\_1i\_0\overline{i\_{m-1}})\_2\] = A\_0\[(i\_{m-3}\cdots i\_1i\_0\overline{i\_{m-1}}\overline{i\_{m-2}})\_2\]$$ $$\cdots$$ $$A\_{m-1}\[i\] = M(A\_{m-2})\[i\] = A\_{m-2}\[(i\_{m-2}i\_{m-3}\cdots i\_1i\_0\overline{i\_{m-1}})\_2\] = A\_0\[(i\_0\overline{i\_{m-1}}\overline{i\_{m-2}}\cdots\overline{i\_2}\overline{i\_1})\_2\]$$ $$A\_m\[i\] = M(A\_{m-1})\[i\] = A\_{m-1}\[(i\_{m-2}i\_{m-3}\cdots i\_1i\_0\overline{i\_{m-1}})\_2\] = A\_0\[(\overline{i\_{m-1}}\overline{i\_{m-2}}\cdots\overline{i\_2}\overline{i\_1}\overline{i\_0})\_2\]$$

Since $i + (\overline{i\_{m-1}}\overline{i\_{m-2}}\cdots\overline{i\_1}\overline{i\_0})\_2 = (\overline1\overline1\cdots\overline1\overline1)\_2 = n-1$, we have proved the claim.

## An exercise

Let $a\_0, a\_1, \cdots, a\_{n-1}$ be an array of length $n=2^m$ for some positive integer $m$. For each step from 1 to m, repeat the following shuffle. For each term in the front half of the array, insert right before it the $n/2$-th term after it. Here is the result array after each shuffle for $n=16$.

```
[0]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
[1]  9  1 10  2 11  3 12  4 13  5 14  6 15  7 16  8
[2] 13  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4
[3] 15 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2
[4] 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

```

Show that we will obtain the initial array reversed in the end of $m$ shuffles.

If you consider the array as a deck of cards, then this shuffle is the (perfect) in (riffle) shuffle. In particular, if you repeat 10 in shuffles on a deck of 32 cards, you will end up with the deck of cards in its original order.
> 2 votes

# Answer
## Notations

**Array indexes start with 1 as in the question.**

Fix some positive integer $m$ such that $n=2^m$.

Given any array $b\_1, b\_2,b\_3,b\_4\cdots, b\_{n - 1}, b\_n$, the magic shuffle $M$ rearrangement it to the array $b\_2, b\_4, \cdots, b\_{n}, b\_1, b\_3, \cdots, b\_{n-1}.$

Let $A\_0$ be the initial array $a\_1, a\_2, \cdots, a\_{n}$ (that is, $A\_0\[i\]=a\_i$). Define $A\_k$ recursively by $A\_{k+1}= M(A\_k)$.

Let "%" be the modulus operator with positive divisor as defined in Python/Java/C/C++/C#.

---

## Lemma: for an array $B$, $M(B)\[i\] = B\[(2i)\\%(n+1)\]$

Proof: please verify by the definition of the magic shuffle.

## Claim: $A\_k\[i\]=A\_0\[(2^ki)\\%(n+1)\]$ for any nonnegative integer $k$.

Proof: the claim is obviously true for $k=0$. If the claim is true for $k$, then $$\begin{align} A\_{k+1}\[i\]&=M(A\_k)\[i\]=A\_k\[(2i)\\%(n+1)\]\\ &=A\_0\[(2^k(2i)\\%(n+1))\\%(n+1)\]=A\_0\[(2^{k+1}i)\\%(n+1)\] \end{align}$$ Hence by mathematical induction on $k$, the claim is true.

## Corallay: $A\_m$ is $a\_n, a\_{n-1}, \cdots, a\_1$, the reverse of $A\_0$.

Proof: $A\_m\[i\]=A\_0\[(2^mi)\\%(n+1)\]=A\_0\[((n+1 -1)i)\\%(n+1)\]=A\_0\[n+1-i\]$.

---

## An exercise

Can you generalize this phenomenon to $n=3^m, 4^m, 5^m,\cdots$?
> 1 votes

---
Tags: sorting
---


# Question
Title: how to deduce a function subtype rule from a given function type definition
This question relates to liskov substitution principle seems to have two conventional meanings but is really a different question, so I'm posing it as a new question.

I'm doing a bit of research into an old language, Common Lisp, which defines function-type as follows: An object `f` is of type `(function (A) Y)` if every call `(f x)` is semantically equivalent to `(the Y (f (the A x)))`.

"`the`" is a special operator which specifies that the value returned by the form is of the specified type.

My question is whether this definition of function-type is enough to derive subtype rules, and type intersection/union/complement rules?

For example if `f` is both `(function (A) Y)` and simultaneously of type `(function (B) X)`, then can we say from the definition that `f` is of type `(function ((and A B)) (and Y X))`, or perhaps can we say that it is `(function ((or A B)) (and X Y))`?

The language (specified in the mid 1980s) specifies that the intersection rule, but not the complement nor the union rules. The intersection of two function types is the former `(function ((and A B)) (and Y X))`, which might surprise some people. I'm wondering

1. Whether this intersection rule follows from the definition?
2. Whether the rule is a contradiction?
3. Can we also derive the complement and union rules from the definition?
4. Can we derive a subtype rule? I.e., if `f` is in `(function (A) Y)`, then `f` is also in `(function (B) X)` if ...what....?

With regard to (4) we would like to say that if $Y \subset X$ and $B \subset A$, then $(A\to Y) \subset (B\to X)$, but that would violate the intersection rule.

# Answer
> 1 votes
The intersection rule should be derivable, but it isn't purely a subtyping rule. Basically we reason as follows (I've translated into a notation that's a bit more familiar to me):

* I'm presuming that subtyping says $A \cap B \subseteq A \subseteq A \cup B$
* Subtyping means that $f : (A \to Y) \cap (B \to X)$ leads to both $f : A \to Y$ and $f : B \to X$
* If $f : A \to Y$, it is then the case that $x : A ⊢ f \\; x : Y$. But subtyping $A \cap B \subseteq A$ means that $x : A \cap B ⊢ f \\; x : Y$ follows.
* The same argument means that $f : B \to X$ leads to $x : A \cap B ⊢ f \\; x : X$
* These two judgments together lead to $x : A \cap B ⊢ f \\; x : X \cap Y$
* This leads back to $f : A \cap B \to X \cap Y$

Another way to specify this is that $f : (A \to X) \cap (A \to Y)$ leads to $f : A \to X \cap Y$. Subtyping allows us to broaden the original $A$ and $B$ to the common $A \cap B$, and then apply this intersection rule. But the intersection rule isn't subtyping, it is the rule for deducing that something has an intersection type via two separate deductions.

Pure subtyping can allow you to go from $f : A \to Y$ to $f : A \cap B \to X \cup Y$. Note that this is refining the input and broadening the output, and we could do each individually.

For union types, there is an opposite sort of rule. $f : (A \to Y) \cap (B \to Y)$ leads to $f : A \cup B \to Y$. So, if you can map both $A$ values and $B$ values to $Y$ values, you can map their union to $Y$ values. However, note that this doesn't allow us to deduce your rule with a union. Instead, we can only get from $f : (A \to Y) \cap (B \to X)$ to $f : A \cup B \to X \cup Y$, because this time we can broaden the result type of both functions and apply the union rule.

But, there is no way (I think) to get to $f : A \cup B \to X \cap Y$, which makes sense if you think about it. Just because we know that $f$ takes $A$ values to $Y$ values and $B$ values to $X$ values doesn't imply that it takes *all* $B$ values to $Y$ values and $A$ values to $X$ values, which is what that specification says.

So, to sum up:

1. The rule is derivable (with some standard assumptions, I think).
2. The rule is not a contradiction.
3. We can derive *a* union rule, but not the one you wrote. And I'm unsure what 'complement' rule you're talking about.
4. Subtyping works as usual, but it is not the only basis for the intersection/union rules.

Edit: Here's a summary of the rules that I believe hold, as I think it might lead you less astray than the long stuff above:

$$(A \to Y) \cap (B \to X) \subseteq (A \cap B) \to (X \cap Y)$$ $$(A \to Y) \cap (B \to Y) \cong A \cup B \to Y$$ $$(A \to X) \cap (A \to Y) \cong A \to X \cap Y$$

In particular, note that the first relationship is subtyping, not equivalence. The intersection of the function types carries more information than the function between intersection types. If the lisp documentation you're looking at says those are *the same*, it's wrong. Consider, just because we know that a function takes $A \cap B$ to $X \cap Y$ doesn't tell us anything about what it takes $A - B$ to. However, if it's merely saying that knowing $f$ has the first two types, we can conclude it also has the third type, that is correct.

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


# Question
Title: How earliest that the data TLB (Translation Lookaside Buffer) can be accessed in an instruction execution pipeline?
In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is:

1. List item before effective address calculation has started
2. during effective address calculation
3. after effective address calculation has completed
4. after data cache lookup has completed

=====================================================================

I think answer is 3.

Reason- Virtual address is given for TLB look up. TLB -Translation Lookaside Buffer, here Lookaside means during Address translation (from Virtual to Physical). But virtual address must be there before we look into TLB.

Please, explain which is the correct option. According to book the answer is 2. I think that option 2, is wrong as it is explaining for physical address resolution and not for effective address calculation.

# Answer
> 5 votes
Often the effective address is the sum of a small constant and a value from a register. Not always, so this trick does not always apply. The trick then is to make a gamble: access the TLB based on just the value from the register, in parallel with adding the offset to it. Usually the small offset won't change the page being accessed, if that works out then you might have the result from the TLB a cycle earlier. Of course there needs to be a check afterwards to see if the upper bits of the virtual address didn't change, and if it fails the TLB access has to be re-done.

There is even a patent for this, with way more detail: Guess mechanism for faster address calculation in a pipelined microprocessor

---
Tags: computer-architecture, virtual-memory, cpu-pipelines
---


# Question
Title: Knapsack-type problem where the objective function is a ratio
I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole while staying within a total cost constraint. Specifically, the problem is:

```
Maximize [sum(v_i*x_i)/sum(c_i*x_i)]
Subject to sum(c_i*x_i) <= C and x in {0,1}
Where v_i = payoff from initiative i, c_i = cost of initiative i, and x_i = 0/1 decision to select investment i or not

```

I understand that if the objective function in such a problem is just a sum then it is a 0/1 knapsack problem. If the function is a ratio as in this case, is there a specific name for this kind of a problem, or a recommended algorithm for solving it?

# Answer
> 1 votes
I can't refer you to literature on this subject, but I did come up with a strategy to solve it.

Do the regular dynamic programming approach to solve simply maximizing $\sum v\_ix\_i$. In that approach you end up with an array $m\[i, c\]$ which is the maximum value you can reach with cost less than or equal to $c$ using items up to $i$.

Then simply do a $O(C)$ loop to find the best possible $\frac{m\[n, c\]}c$ for each $c$ where $n$ is the number of items.

---
Tags: optimization, knapsack-problems
---


title: Vertex cover with covering radius 2

text:
# Question
Title: Vertex cover with covering radius 2
Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?

A vertex included in this vertex cover variant will cover every edge incident to it and every edge incident to some edge incident to it. Hence, we call this variant a vertex cover with covering radius 2.

What is the computational complexity of this problem?

# Answer
> 5 votes
It is still NP-complete. It is easy to see it is in NP. To prove its NP-completeness, we reduce the standard vertex cover problem to this problem.

Given an instance $G=(V,E)$ of vertex cover problem, we construct a new graph $G'$ based on $G$ as follows.

1. For each edge $(u,v)\in E$, split it into three edges $(u,u\_v)$, $(u\_v, v\_u)$, $(v\_u,v)$ where $u\_v$ and $v\_u$ are newly added vertices.
2. For each vertex $v\in V$, add three edges $(v,v\_1),(v\_1,v\_2),(v\_2,v\_3)$, where $v\_1,v\_2$ and $v\_3$ are newly added vertices.

Now we assert that $G$ has a vertex cover of size $k$ if and only if $G'$ has a vertex cover with radius 2 and of size $k+|V|$.

If $G$ has a vertex cover of size $k$, then this vertex cover as well as $v\_1$'s for all $v\in V$ makes up a vertex cover of $G'$ with radius 2.

On the other hand, assume $G'$ has a vertex cover $C'$ with radius 2 and of size $k+|V|$. Note for each $v\in V$, since $(v\_2,v\_3)$ is covered, at least one of $v\_1,v\_2$ and $v\_3$ should be included in $C'$. We can assume $v\_1$ is always included and $v\_2,v\_3$ are never included in $C'$. Now the rest $k$ vertices are of either the form $u$ or the form $u\_v$ where $u,v\in V$. Let $$C=\\{u\in V\mid u\in C'\text{ or }u\_v\in C'\text{ for some }v\\}.$$

Note for each $(u,v)\in E$, $(u\_v,v\_u)$ is covered by $C'$, then at least one of $u, u\_v, v\_u, v$ is included in $C'$, which means either $u$ or $v$ is inclulded in $C$. Hence $C$ is a vertex cover of $G$, which has size no more than $k$.

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


# Question
Title: Proving equivalency of regular expressions
x,y are regular expressions, prove this: (xy+x)$^\*$x = x(yx+x)$^\*$\* (\* in this expression is kleene star)

I am looking for a method that is applicable to prove such questions. I know that proof needs to show that:

1) (xy+x)$^\*$x =\> x(yx+x)$^\*$

2) x(yx+x)$^\*$ =\> (xy+x)$^\*$x

My attempt is like this:

1) (xy+x)$^\*$x =

= x(y+epsilon)$^\*$x by pulling x out -the x on the left is the one pulled out

= x(yx+x)$^\*$ by distributing the last x

2) x(yx+x)$^\*$

= x(y+epsilon)$^\*$x by pulling the x out -the right x is the one pulled out

= (xy+x)$^\*$x by distributing the first x

Does this make sense? Thanks!

# Answer
Conceptually, the simplest approach is:

1. Convert both regular expressions to NFA.
2. Determinise both NFA.
3. Minimize both DFA.
4. The regular expressions are equivalent if and only if the minimal DFA are isomorphic.

The requisite algorithms and theorems are taught in (about) every introducory class to formal languages resp. automata and can be found in (every) textbook on the topic. In fact, the point of this exercise probably *was* to come up with this approach, combining results from the course. Sorry for spoiling it.
> 1 votes

---
Tags: formal-languages, regular-expressions
---


# Question
Title: Sorting Algorithm which prevents strings with at least one identical char from being next to each other
Imagine this Table:

All combinations represented in the table (1,2 ; 1,3 ; 1,4 ; etc.) are stored as strings in an array with a total of (n^2-n)/2 elements (combinations).

I'm looking for an algorithm that sorts the elements so no number of a combination is next to a combination with the same number in it.

For example a sorted array with n=5: {1,2 ; 3,4 ; 5,1 ; 2,3 ; 5,4 ; 1,3 ; 2,5 ; 4,1 ; 3,5 ; 4,2}

Of course this algorithm would only work with n \> 4.

# Answer
> 0 votes
Think of this like a chess board. Visit all of the white squares first (in a left-to-right, top-to-bottom scan). Then visit all of the black squares (in a similar order).

---
Tags: algorithms, sorting, arrays
---