# Question
Title: Polynomial time reducibility is an equivalence relation
How do I prove the following statement?

> The relation $≤\_p$ (polynomial time reduction) is an equivalence relation.

# Answer
> 2 votes
A polynomial-time reduction from $A$ to $B$ is a polynomial-time computable function $f$ that maps an instance $x$ of a problem (language) $A$ to an instance $f(x)$ of a problem $B$ such that $x \in A \iff f(x) \in B$.

Polynomial-time (Karp) reductions are reflexive (since $A \le\_p A$), as it follows by choosing $f(x) = x$.

Polynomial-time reductions are transitive, i.e, if $A \le\_p B$ and $B \le\_p C$ then $A \le\_p C$ by choosing $f = h \circ g$, where $g$ (resp. $h$) is a polynomial-time computable function such that $x \in A \iff g(x) \in B$ (resp. $x \in B \iff h(x) \in C)$.

However, Polynomial-time reductions are **not** symmetric. That is, it is not true that $A \le\_p B \implies B \le\_p A$. Consider for example a binary alphabet, $A = \\{0,1\\}^\*$, and $B = \\{0\\}$. The function $f(x) =0$ is a valid polynomial-time reduction from $A$ to $B$ but there is no polynomial-time reduction from $B$ to $A$.

---
Tags: polynomial-time-reductions
---


title: Hardness of boolean functions

text:
# Question
Title: Hardness of boolean functions
For a boolean function $f:\\{0,1\\}^n\longrightarrow\\{0,1\\}$, $H\_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C\_n$ of size $H\_{avg}(f)(n)$, $Pr\_{x\in U\_n}\[C\_n(x)=f(x)\]\<1/2+\epsilon$, $\epsilon \>0$.

Similarly, for a boolean function $f:\\{0,1\\}^n\longrightarrow\\{0,1\\}$, $H\_{wrs}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the worst case hardness, if $\forall$ circuit $C\_n$ of size $H\_{wrs}(f)(n)$, $Pr\_{x\in U\_n}\[C\_n(x)=f(x)\]\<1$.

This I know from the definition of average and worst case hardness. My question is what is the motivation behind these definitions. Can anyone help?

# Answer
In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$.

In the worst case, you want the circuit to succeed in computing the function for all inputs, so you want to say that $f$ is at least $H(n)$ worst case hard if any circuit of size $\le H(n)$ disagrees with $f$ on at least one input in $\\{0,1\\}^n$.
> 2 votes

---
Tags: circuits, lower-bounds, pseudo-random-generators
---


# Question
Title: SMO, Random forest and Bayes net algorithms: why does Random forest perform better?
I analyzed a dataset using those 3 different algorithms. As I can see, Random forest performs better in most cases. My dataset is composed of 4000 instances of two classes (class A 2000 elements, class B 2000 elements). I use 207 metrics to classify the instances, but I also use the first 20 or 10 best metrics for InformationGain. My question is: why sometimes an algorithm performs better than another one (in this case I'm only comparing this 3). I read about them but I would like to have a complete scenario of why in some case RF is better than Bayes net and why sometimes is the opposite. And why SMO is always worst than the other two, in my experiences. Thank you so much!

# Answer
In machine learning, there's often no clear "why" or "reason" we can point to. These are different methods, which implicitly embed different biases or different priors or different assumptions, and thus will work better in different situations.
> 0 votes

---
Tags: algorithms, algorithm-analysis, machine-learning, decision-tree, bayesian-statistics
---


title: How to avoid drawing dense maps?

text:
# Question
Title: How to avoid drawing dense maps?
The problem I have in hand is like drawing Google Maps by myself, in particular, roads. When my map scale is huge, I face no problem, but when I zoom out there are too many things to draw -- sure, I can rank the elements, and for example draw only important roads (like highways), but at given scale there will be always some case, when the road has so many intersections and turns, and instead of nice drawing I will get ugly blob.

So I would like to simplify it, yet not in misleading way. I would like to avoid drawing dense map (part of it).

* is there official name of this problem/algorithm for it?
* if there is special case for maps?

And if there is nothing anything "official" -- how to tackle this problem?

# Answer
You could smooth the path of the road by fitting a spline to it (or some other curve), with parameters chosen based on the zoom level to ensure that it follows a smooth path on the screen.
> 1 votes

---
Tags: algorithms, graph-drawing
---


title: Is arithmetic turing complete?

text:
# Question
Title: Is arithmetic turing complete?
Maybe my question doesn't make sense, because I lack some more thorough understanding, but I was curious if arithmetic was Turing complete?

As I understand it, a "model of computation" is a mechanism where you can compute outputs from inputs. Thus a "computation" is just a mapping from inputs to outputs.

So if say the universe of possible inputs and outputs is: 1 and 2. This would be all possible computations:

```
1 -> 1
1 -> 2
1 -> 1,2
1 -> 2,1
2 -> 1
2 -> 2
2 -> 1,2
2 -> 2,1
1,2 -> 1
1,2 -> 2
1,2 -> 1,2
1,2 -> 2,1
2,1 -> 1
2,1 -> 2
2,1 -> 1,2
2,1 -> 2,1

```

Now, I think this isn't even technically the full set, because the full set would be infinite, since I could have repeated inputs and outputs like `1,1 -> 2,2,1,1`. But at least this is the general gist which I understand.

And in my "model of computation", I should be able to say, apply the computation X to some inputs, where X is one of the above mapping, and get back the corresponding outputs.

So from this, I understand that the Turing Model is proven to be able to map all inputs to outputs over the universe of non complex numbers.

So my question is, would arithmetic be Turing Complete in its ability to map inputs to outputs? Or is there some mappings that can not be formulated using arithmetic, but can using the Turing model?

# Answer
It depends what you mean by "arithmetic".

It's a fairly well-known result that Peano arithmetic (PA) is powerful enough to model Turing machines.

There are other models of arithmetic, such as Presburger arithmetic (which is strictly weaker; it's essentially PA without multiplication) and real closed fields with a partial order, which are known to be decidable.
> 2 votes

# Answer
PA represents the same relations that TMs accept.

The Arithmetic you learned in elementary school forms the individual functions and expressions of a programming language. For example, you can assign variable A the value of 1+1 e.g. $A=1+1; in the PHP programming language. Arithmetic tells us that A now equals 2.

However, a Turing Complete (every) Programming Language also provides commands to execute a series of statements in an order that depends on the values of variables. We can say: if $A\>1 $B=$A+1; This means that is variable A has a value greater than 1 then variable B will be given the value of 1 more than A.

By using these control commands in conjunction with assignment commands, we can calculate functions far beyond addition, subtraction, multiplication and divisions. We can generate prime numbers, for example.

With the addition of control commands, we have a Turing Complete programming language. We also have the possibility of a program going in circles forever - until we manually stop it. Alan Turing proved in 1937 (13 years before electronic computers were invented) that we can't always tell if a given program will end up going in circles forever.

I am sure you never got into an infinite loop performing Arithmetic assignments in school. But you also probably didn't generate prime numbers either.

So that is the trade-off. Just Arithmetic alone calculates simple things, like the cost of supper. But if you want to delve into more complex matters that involve Arithmetic functions, you'll have to use a complete Programming Language - and you'd better be careful.

A computer is like a powerful car. It can take you to the beach in a few minutes, but it can also take you off a cliff.

Drive safely!
> 0 votes

---
Tags: computation-models, arithmetic, turing-completeness
---


# Question
Title: Exact definition of average time complexity?
Now I'm from a mathematical background, and I found CS people's definition of average time complexity a bit... confusing, to say the least.

Here is a definition that I feel comfortable with:

Consider a set $A$ of finite elements, with each $a\in A$ indicating individual input cases. There exists a function $T(a)\mapsto t\in\mathbb{N}$, i.e., *running time* for individual cases. Now we can define the average running time of input set to be simply $$\overline{T}(A)=\frac{\sum\limits\_{a\in A}T(a)}{\\#A},$$ where $\\#A$ denotes *number of elements* in $A$. For example, in QuickSort, we let $A\_n=\\{\text{array of $n$ unsorted integers}\\}=\mathbb{Z}^n$.

But now we have to do an additional step. An integer can take on an *infinite* set of values, so we naturally consider the memory constraint and instead confine each integer $i$ to be $L\le i\le U$. Now $\\#(A\_n)=(U-L+1)^n$, and we have a clearly defined $T(\cdot)$, and we can try to figure out $\overline{T}(A\_n)$, although this is a *very* tough combinatorics problem.

We can also consider $i$ to be a bounded real number, with the modification $\\#(A\_n)=\mu\_{\text{Le}}(A\_n)=(U-L)^n$, and $$ \overline{T}(A\_n)=\frac{1}{(U-L)^n}\int\limits\_{a\in A\_n}T(a)\\,\mathrm{d}\mu\_{\text{Le}}. $$

What CS people did instead, is stating $T(a) \le T(\text{head})+T(\text{tail})+cn$ for some $c$, then simply averaging $T(\text{head})$ and $T(\text{tail})$ for varying head or tail lengths. This is stating implicitly somehow varying head (or tail) lengths are "equally likely", with out even considering the constraint that makes $A\_n$ finite. This is like saying you can pick an odd number from the set of all integers at "$50\\%$ probability" without even bothering to define what this "probability" means!

So how is this average time complexity rigorously defined over an infinite, countable number of cases?

If average time complexity is dependent on a set of rules of translating clearly defined recursion to what is essentially an intuitive ad-hoc definition each time, how can we define average time complexity for arbitrary code?

# Answer
> 14 votes
Here is the definition of average-case time complexity of an algorithm:

> Let $T(x)$ be the running time of some algorithm $A$ on input $x$. For every $n$, let $\mu\_n$ be a distribution on inputs of length $n$. The *average-case* or *expected time complexity* of $A$ on inputs of length $n$ is $$T\_{\mathit{avg}}(n) := \mathbb{E}\_{x \sim \mu\_n} T(x). $$

As you can see, in order to talk about average-case complexity, *you have to specify a distribution*. In the definition above I have alluded to the common case in which the complexity is parameterized by input length, but we could also have more parameters, or no parameters at all.

For comparison-based sorting algorithms, we usually consider the following distribution $\mu\_n$: the uniform distribution on all $n!$ permutations of $1,\ldots,n$. However, we would obtain *exactly* the same notion of average-case complexity (for comparison-based algorithms) if instead we pick *any* atom-less distribution $\mu$, and define $\mu\_n$ to consist of $n$ iid copies of $\mu$.

Unfortunately, no distribution on the integers is atom-less. This creates a problem, since if we generate $n$ iid copies of a distribution $\mu$ with atoms, then there is positive probability that the generated elements are not distinct. While comparison-based sorting algorithms can certainly handle this case, the situation becomes much less clean since the average-case time complexity now depends on $\mu$.

Finally, you seem to be quoting a quite informal average-case complexity analysis of quicksort. You can find rigorous analysis of the average-case complexity of quicksort (in fact, two different ones) in lecture notes of Avrim Blum.

# Answer
> 0 votes
As expected value of random variable.

1. Donald E.Knuth The Art of Computer Programming, volume 1, 1997, page 98, Chapter 1, section 1.2.10.
2. Tim Roughgarden — Algorithms Illuminated, Part 1, page 190.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Optimal algorithm to distinguish given black box access
This is a variant of this question. Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. Assume that $D$ and $U$ are far apart in total variation distance, ie, \begin{equation} d\_{\text{TV}}(D, U) \geq \frac{2}{3}. \end{equation}

We are not given an explicit description of $D$: we are only given black-box access, ie, we are only given a sampling device that can sample from $D$. Consider a sample $z \in \\{0, 1\\}^{n}$, taken from either $D$ or $U$. We want to know which one is the case and to do that, we consider polynomial-time algorithms that use the sampling device. I am looking for a single optimal deterministic algorithm that works optimally for all $D$.

Let $A$ be this optimal algorithm. For each $D$, our algorithm $A$ is optimal in the sense that

$$ \Pr\_{z \sim D} \[A(z) = 1\] \geq \frac{3}{4}, \\ \Pr\_{z \sim U} \[A(z) = 0\] \geq \frac{3}{4}, $$

Output $1$ is interpreted as "the sample comes from $D$, and output $0$ is interpreted as "the sample comes from $U$."

Let $A$ use the black-box sampling device a polynomial number of times (at most) and get samples $z\_{1}, z\_{2}, \ldots, z\_{k}$ from $D$, for some polynomial $k$. My intuition is that, if this best algorithm decides that $z$ indeed came from $D$, then it must be true that $z\_{i} = z$ for at least one $i \in \[k\]$. In other words, since we know nothing about $D$ or its support, we have to "see" $z$ at least once in the samples we collect from $D$ to ascertain that $z$ indeed came from $D$. How do I mathematically formalize this statement?

Also, does this same intuition hold if we are given a polynomial number of samples as input (taken from either $D$ or $U$) instead of just one and are also given access to a black-box sampler for $D$?

# Answer
You need $\Omega(2^n)$ samples in order to accomplish your task.

Consider an algorithm that gets $m$ samples from $D$ and then another sample, either from $D$ or from $U$, and has to guess which it is. Its input thus consists of $m+1$ samples $X\_1,\ldots,X\_m,Y$.

We will generate the distribution $D$ at random by choosing a random set $V \subseteq \\{0,1\\}^n$ of size $2^{n-2}$ and letting $D$ be a uniform sample from $V$. Note that $d\_{\mathrm{TV}}(D,U) = 3/4$.

Consider now the following two distributions:

* Distribution $\mathcal{D}$: Choose $D$ at random as above. Generate $m+1$ samples from $D$.
* Distribution $\mathcal{U}$: Choose $D$ at random as above. Generate $m$ samples from $D$ and one sample from $U$.

Let $S$ be the set of vectors appearing in the first $m$ samples. We can describe the distribution of the final sample as follows:

* Distribution $\mathcal{D}$: With probability $|S|/2^{n-2}$, output a random element in $S$ (each one is output with probability $1/2^{n-2}$). Otherwise, output a random element not in $S$.
* Distribution $\mathcal{U}$: Output a random element.

To see where the alternative description of $\mathcal{D}$ comes from, notice that given $S$, the conditional distribution of $V$ is a random set of size $2^{n-2}$ containing $S$. When sampling a random element from $V$, we have a probability of $|S|/2^{n-2}$ to choose one of the elements from $S$, with probability $1/2^{n-2}$ each. Otherwise, we choose an element from $V \setminus S$, which given the distribution of $V$, is just a random element not in $S$.

This shows that the TV distance between the two distributions is $$ \mathbb{E}\left\[|S|(1/2^{n-2} - 1/2^n)\right\] \< \frac{m}{2^{n-2}}. $$ In particular, any algorithm whatsoever will behave almost the same in both cases unless $m = \Omega(2^n)$. Indeed, your algorithm $A$ satisfies $$ \Pr\_{\mathcal{D}}\[A=1\] - \Pr\_{\mathcal{U}}\[A=1\] \geq \frac{3}{4} - \frac{1}{4} = \frac{1}{2}, $$ showing that the variation distance between $\mathcal{D}$ and $\mathcal{U}$ is at least $1/2$. This is only possible if $m/2^{n-2} \geq 1/2$, that is, if $m \geq 2^{n-3}$.
> 1 votes

---
Tags: algorithms, probability-theory
---


# Question
Title: Minimum sum of squared Euclidean distance between two arrays
**Question:**
Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$.
I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the following optimization problem:$$d(Y,X') = \sum\_{j=1}^{k}(y\_{j}-x'\_{j})^{2}$$ And $X'$ is a subset of $X$ of size $k$, $y\_{j} \text{ and } x'\_{j}$ is element in $Y$ and $X'$. I would like to find the subset of $X$, to reach the minimum of $d(Y,X')$.
Note that $X'$ could have $k!$ numbers of arrangements, so its order is totally unknown.

---

What I have came up with so far:
I would like to approach it using Dynamic Programming, and I think I would first compute the squared distance between each element in $Y$ and $X$, but I'm having trouble in determining what is the subproblem and how to solve ths using DP. Thank you!

**Update**: The $X'$ could be sorted, which means we could aim at finding a sorted subset of $X$.

# Answer
for m' = 0 to m for k' = max(0, m-m') to min(m', k) Take the problem of the first m' items of X and the first k' items of Y. Find the value of the smallest sum, and whether X\[m'\] is in that sum.

The optimal subset of the first m' items of X is either the best subset of the first m'-1 items of X matching the first k' items of Y, or the best subset of the first m'-1 items of X matching the first k'-1 items of Y, with X\[m'\] and Y\[k'\] added.

Note that sets and subsets are not sorted. If you want the indexes in arbitrary order, sorting X and Y first should work.
> 1 votes

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


# Question
Title: Compression Bounds - Determine and Visualize for hypothesis vs VC dimension
I want to visualize or calculate the compression bounds for hypothesis classes. I learnt how to figure out the VC dimension. Let's say I define two hypothesis class. For example: $$ H\_k = \\{h ∈ (0,1)\_X \mid |h^{−1}(1)| ≤ k\\} $$

and $$ H\_{decst} = \\{h^i\_a \mid a ∈ R, i ∈ (1,2)\\}, \text{ where } h^i\_a((x1,x2)) = 1\[x\_i ≤ a\]. $$

For VC dimension, I showed The VC dimension of $H\_{decst}$ is 2. We can shatter the two points $x\_1 = (2,0)$ and $x\_2 = (0, 2)$ with the four functions $h\_{0.5}, h\_{1.5}, h\_{1.5}, h\_{2.5}$.

Also, It is not hard to see that $H\_k$ shatters any set $C ⊆ N$ of size $k$, but no larger set, since the all-1 labeling can not be realized on more than $k$ points with $H\_k$. Thus, the VC-dimension of $H\_k$ is $k$.

Similarly, I want to figure out the compression bounds for $H\_k$ and $H\_{decst}$.

# Answer
> 1 votes
Generally, every class of finite VC dimension admits to a (exponential size in the dimension) compression scheme. This was an open question resolved a few years ago by Shay and Amir in this paper. However, this is an overkill for your question, since $H\_k$ obviously has a $k$-comprresion scheme (only keep the samples labeled $1$, of which there are at most $k$, and the reconstruction is zero everywhere else).

$H\_{desct}$ can be compressed to two samples, given $\left((a\_i,b\_i),y\_i\right)\_{i=1}^n$, we know that either there exists $j$ such $\forall i\in\[n\]: y\_i=\mathbb{1}\_{a\_i\le a\_j}$ or there exists $j$ such that $\forall i\in\[n\] : y\_i=\mathbb{1}\_{b\_i\le b\_j}$. The compression keeps $(a\_j,b\_j)$ and one more sample $(a\_{j'},b\_{j'})$ to indicate the correct coordinate of the threshold, e.g. if the former condition holds and $\forall i\in\[n\]: y\_i=\mathbb{1}\_{a\_i\le a\_j}$ then pick $j'$ such that $y\_{j'}\neq y\_j$ (so $y\_{j'}=0)$ and $b\_{j'}\<b\_j$ (this allows us to reconstruct the function $\mathbb{1}\_{x\_1\le a\_j}$ from the two samples). If no such $j'$ exists then $\mathbb{1}\_{x\_2\le b\_j}$ is also a consistent hypothesis, and our compression can keep only one sample.

---
Tags: learning-theory
---


title: Right most set bit O(log N)

text:
# Question
Title: Right most set bit O(log N)
I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used.

```
public static int getFirstSetBitPos(int n){
    int counter = 0;
    while (n > 0){
        if ((n&1) == 1){
            return counter + 1;
        }
        n >>= 1;
        counter ++;
    }
    return 0;
}

```

The problem asks to solve it in a time complexity of O(logN), and my code is O(N). When I looked at the editorial, it had this solution.

```
// Java Code for Position of rightmost set bit
class GFG {

    public static int getFirstSetBitPos(int n)
    {
        return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
    }

    // Drive code
    public static void main(String[] args)
    {
        int n = 12;
        System.out.println(getFirstSetBitPos(n));
    }
}
// This code is contributed by Arnav Kr. Mandal

```

I don't understand this `return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;` I would appreciate if someone could explain.

I am new to programming and an aspiring competitive programmer.

# Answer
Questions about programming are off-topic, however there are a few computer science questions hidden in here: what `n & -n` does, and how floating point is represented.

The `n & -n` operation isolates the rightmost bit of a word in two's complement arithmetic. This is a very useful operation to know about.

Consider, for example, the following 8-bit word:

```
10010000

```

You can find the two's complement of this by taking the logical not of all the bits:

```
01101111

```

And then adding 1:

```
01110000

```

If you then take the logical and of this with the original word, you get:

```
00010000

```

This is the rightmost set bit of the original word. Please try a few examples for yourself to understand how this operation works.

Once you understand that, the rest is simply calculating base-2 logarithm of this number, essentially finding the highest/leftmost set bit, using an unnecessarily complicated method:

$$\log\_2 x = \frac{\log\_{10} x}{\log\_{10} 2}$$

Quite apart from the fact that this is going to raise a floating point exception if you pass it zero (because what's $\log 0$?), and quite apart from the fact that the computational complexity of `Math.log10` is not specified in the Java standard, floating-point numbers are stored in scientific notation in base-2 internally. The number $128.0$, for example, is stored as $1.0 \times 2^7$. So this is just an overly-complex way of extracting the exponent field of a floating-point number:

```
public static int getFirstSetBitPos(int n)
{
    return (int)Math.getExponent((float)(n & -n)) + 1;
}

```

The idea that you were probably supposed to have, however, is to use some kind of binary search. For a 32-bit integer, for example, you can tell if there is a set bit in the lowest-order 16 bits using a logical and with an appropriate mask:

```
(n & 0xFFFF) == 0

```

If there is a bit set in this range, then the answer to your question, the "find first set" of a number, is between 0 and 15, otherwise it's between 16 and 31. Either way, you have halved the search space. Turning this into an algorithm is left as an exercise.
> 3 votes

# Answer
I used @Pseudonym and @greybeard suggestions and came up with this solution.

```
public static int getFirstSetBitPos(int n){
    if (n == 0) return 0;
    if (n%2 == 1) return 1;
    return Integer.numberOfTrailingZeros((int) ((n & -n)+1) & n) + 1;
}

```
> 1 votes

---
Tags: algorithms, bit-manipulation
---


# Question
Title: How can I find this code block's execution time t(n) and big O notation?
Hello I am a CSE student and this question was in my homework.

```
double fact(long i)
{
if (i==1 || i==0) return i;
else return i*fact(i-1);
}

funcQ2()
{
for (i=1; i<=n; i++)
sum=sum+log(fact(i));
}

```

I thought it is O(n^2) but can the bottom function's log function call make it O(n^3)? I am not sure

Thanks in advance

# Answer
`fact(n)` runs at $O(n)$.

So, each iteration of `funcQ2` runs at $O(i)$, assuming `log` runs at constant time. (There are several algorithms to calculate the log)

Then the question turns into calculating $\sum\_{i=1}^n O(i)$, and the answer is $O(n^2)$.

Now suppose your `log(n)` runs at time $O(f(n))$.

Then the answer to your question should be $\sum\_{i=1}^n O(f(i))$. You should calculate that on your own as I don't know the $f$.
> 0 votes

---
Tags: big-o-notation, loops
---


title: Cut edge and cut vertices

text:
# Question
Title: Cut edge and cut vertices
> If $e = \\{u, v\\}$ is a cut edge with $\deg(u)$ and $\deg(v)$ both at least 2, then $u$ and $v$ are cut vertices.

I want to prove or disprove this statement, but don't know how to proceed. I do know what goes wrong when one of the degrees is smaller than 2.

# Answer
Let $G=(V,E)$. By symmetry it suffices to show that $u$ must be a cut-vertex.

Let $C$ be the set of vertices in the connected component of $G-(u,v)$ containing $u$. Clearly $v \not\in C$.

Let $x$ be a neighbor of $u$ distinct from $v$. Since $(x,u) \in E \setminus \\{(u,v)\\}$, we must have $x \in C$ and hence $x$ is disconnected from $v$ in $G-(u,v)$.

Since $G-u$ is a subgraph of $G-(u,v)$ containing both $u$ and $v$, $x$ must be disconnected from $v$ in $G-(u,v)$. The claim follows by noticing that $x$ was connected to $v$ in $G$.
> 0 votes

---
Tags: graphs
---


# Question
Title: Why does an inverted page table keep a chain of pages per frame when it can only store one of such pages?
I'm currently dealing with inverted page tables and how they work. If I understood correctly, an IPT is a table that maps a frame number to a PID and page number. The way this works is by having a hash function map a tuple (PID, page\_number) to (frame\_number). If the entry of the table given by the frame number contains (PID, page), then we have a hit. Because a hash function can map multiple inputs to one output, we have to keep a chain of pages for each frame (according to my lecture notes).

Why does an inverted page table keep a linked list of pages per frame? Only one page can be loaded into a single frame at a time, how does this make sense? To me this seems more an issue similar to that of direct-mapped caching, where you have to throw out the previous block to make place for a new block.

# Answer
> 1 votes
Hash functions can have collisions, and you need to resolve the collisions. If two (PID, page\_number) pairs map to the same row, only one can be stored there, and you need to have a mechanism to find the other one.

You can use page tables to map multiple virtual addresses (pages) to the same physical address (frame). For instance, this may be used to support shared memory, copy-on-write, on-demand zeroing for memory allocation, and more.

---
Tags: operating-systems, memory-hardware
---


# Question
Title: Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints
I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N\[V'\]=V$, $∀v'∈V '\[∃r∈R ($path($r', v'$)$)\]$ that minimizes the sum of vertex weights in $V'$. Note the path must contain only vertices in $V'$.

In other words, all roots must be in $V'$, the closed neighborhood of $V'$ must include all vertices in the original graph and every vertex in $V'$ needs to have a path to a root.

I have constructed a naive algorithm that takes the powerset of $V$ and checks for each subset if it satisfies the 3 constraints. The first constraint is trivial, the second requires the algorithm to compare the union of $V'$ with $V$, and the third one is done by using DFS (only adding vertices to *discovered* if they are in $V'$.

I was thinking I could convert the vertex-weighted undirected graph to a edge-weighted directed graph and then run Chu-liu/Edmonds' algorithm to find a minimal spanning arborescence. I tried converting the graph by adding $v'$ for each $v$ in $V$, with an edge $(v,v')$ with the vertex weight. All outgoing vertices from $v$ will now be outgoing from $v'$. The problem is that these auxiliary vertices don't need to be included in the MSA, but Chu-liu/Edmonds' algorithm will include them.

Actual question: Is there a better way to convert the graph, so that I can use this approach, or should I go for another (maybe even easier) approach?

# Answer
Without loss of generality we can assume the graph is connected. (If not, decompose it into connected components, and solve the problem separately on each component.) Since it is connected, every vertex has a path to every other, so we can ignore the requirement to have a path to a root.

So your problem becomes: given $R$, find a minimum dominating set $V'$ that contains $R$. This is NP-complete; indeed, the special case where $R=\emptyset$ is the standard dominating set problem, which is NP-complete, so your problem is, too.

If you need to solve your problem in practice, you could apply any of the standard techniques for dominating set or set cover. For instance, you could use an approximation algorithm or greedy heuristic to get an approximate solution; or you could use a SAT solver or ILP solver to get an exact solution and hope that it terminates in a reasonable amount of time on your specific problem instances.
> 0 votes

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: What is the computational class of a pushdown automaton with real values?
Say there is a push-down automaton, in this example I'll use a Deadfish-like set:

`+: increase x by 1`

`0: set x to 0`

`ln: set x to ln(x) <-- real valued result`

With x being an infinite precision real-valued variable, does this allow said machine to have more power than if it was operating on integers? Or am I misunderstanding something?

# Answer
> 0 votes
Since none of your instructions can influence the behavior of the pushdown automaton (they can only influence the value of $x$), this does not change which languages the pushdown automaton can accept.

---
Tags: pushdown-automata, complexity-classes, turing-completeness, real-numbers
---


# Question
Title: How can I make the variance of a multiple sum of set of fixed number of variables minimum?
Here is the problem:

There are $MN$ people, where there are $M\>1$ seeds and $N\>0$ people are in each seed. We have to make $N$ teams of $M$ people where everyone in the team have different seeds. Each person have their own value; values are positive integers. Assume there are no two people with same values.

For two distinct seeds $I$ and $J$, we say $I\<J$ if for all $x\in I$ and $y\in J$, $x\<y$ holds. It is guaranteed that for any two distinct seeds $I$ and $J$ in the problem, $I\<J$ or $J\<I$ holds. In other words, we can set $M$ seeds $I\_1,I\_2,\cdots,I\_M$ in the problem to satisfy $I\_1\<I\_2\<\cdots\<I\_M$.

I am interested in two versions of this problem:

1. There are no paired people. This means in process of making $N$ teams, there is no restriction except given above.
2. There may be some paired people. This means a set of paired people that cannot be split is given, so that if a team contains one person from some pair, the team should also contain the other person from that pair. It is provided that every pair contains exactly two people from different seeds.

For each version, the task is to design an algorithm to make the variance of the sum of values of people in each team to be minimum.

Since this problem is NP (complete?), I would accept heuristics. I hope that the heuristic method gives the solution with variance at most $25\\%$ larger than the optimal solution, as I don't want to harm the balance of the team.

Could you please give an algorithm or heuristic that can solve this problem? Also, adding a time complexity would be highly appreciated!

# Answer
> 1 votes
If you're willing to replace 'variance' with 'max minus min' (spread), then you could formulate this as an instance of integer linear programming and apply an off-the-shelf ILP solver. There is no guarantee that it finds an optimal solution in a reasonable amount of time, but if you're lucky, it might complete without taking too long; or if you stop it early, you might get a decent solution.

To formulate this as an instance of ILP, add zero-or-one variables $x\_{i,j}$, with the intended meaning that $x\_{i,j}=1$ means that person $i$ is assigned to team $j$. Each requirement in the problem statement can be expressed as a linear inequality; for instance, the requirement that everyone in a team has a different can be expressed by inequalities of the form $x\_{i,j} + x\_{i',j} \le 1$ for each pair $i,i'$ of people from the same seed.

To minimize the spread, introduce variables $\ell,u$. Let $v\_i$ denote the value of person $i$ (this is a constant, not a variable). Add linear inequalities $\ell \le \sum\_i x\_{i,j} v\_i \le u$ for each team $j$. Finally, minimize $u-\ell$, subject to the inequalities above.

If you want to use the variance, this becomes a mixed-integer quadratic program instead of a mixed-integer linear program, and I think quadratic programs are significantly harder.

---
Tags: algorithms, heuristics
---


# Question
Title: Efficient algorithm for sorting objects by key that values are range from 0 to 100
Can you help me with sorting algorithm implementation for objects of `Student` type by `rating` field. This field (`rating`) value can be any number from `0` to `100`. Can I do the sort in-place?

# Answer
Let $A\[0 \dots, n-1\]$ be the elements to be sorted. A possible strategy that requires $O(n)$ time and $O(1)$ additional memory is:

* count, for each possible key $k$, the number of elements in $A$ with key $k$, in $O(n)$ time;
* for each $k$ compute the intervals of indices of $A$ in which elements with key $k$ must lie (in $O(1)$ time);
* Scan the input array a place each element in the correct interval. This can be done by swapping the considered element with any element that was already in that interval, taking care to not swap that element back.

A possible implementation is the following:

* Initialize an array $C\[0, \dots, 100\]$. Initially all entries of $C$ are $0$.
* For each $i=0, \dots, n-1$: increment $C\[k\]$ where $k$ is the key of $A\[i\]$.
* For $k=0, \dots, 101$, let $P\[k\]=\sum\_{j=0}^{k-1} C\[j\]$; At this point we know that an element with key $k$ needs to end up in some $A\[i\]$ with $P\[k\] \le i \< P\[k+1\]$. Notice that, for $k\>0$, $P\[k\] = P\[k-1\] + C\[k-1\]$.
* Let $i=0$.
* While $i\<n$:
    + Let $k$ be the key of $A\[i\]$.
    + If $i \not\in \[P\[k\], P\[k+1\])$
        - Decrement $C\[k\]$
        - Swap $A\[i\]$ with $A\[P\[k\]+C\[k\]\]$
    + Else
        - Increment $i$
> 2 votes

---
Tags: sorting
---


title: oone exmple in hash topics?

text:
# Question
Title: oone exmple in hash topics?
Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is the order of probability $ z \geq c \log n$? $C$ is constant here.

Answer: $O(1/n^c)$

How this this is can be achieved?

I think this is same with this question:

Source: introduction to algorithm CLRS Page 652 Ex.11-C

# Answer
Let $A\_n\subseteq \\{0,1\\}^{\log n}$ denote the set of binary strings of length $\log n$ with at least $c\log n$ trailing zeros on the right (here I assume that $\log n$ in an integer and $0\le c\le 1$). Note that $|A\_n|=2^{\log n -\lceil c\log n\rceil}\le 2^{(1-c)\log n}$. Since $H:\\{0,1\\}^{\log n}\rightarrow \\{0,1\\}^{\log n}$ is a one to one function, $\Pr\_{x\sim U\_{\log n}}\left\[H(x)\in A\_n\right\]=\frac{|A\_n|}{2^{\log n}}\le\frac{1}{n^c}$, where $U\_k$ is the uniform distribution over $\\{0,1\\}^k$.
> 2 votes

---
Tags: algorithms, data-structures, probability-theory, hash, hashing
---


# Question
Title: Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?
I thought they did, but recently I tried to express $3^n$ as $k \times 2^n + o(2^n)$ for some constant $k$ but wasn't able to. All I found was $3^n = (\frac{3}{2})^n 2^n$. What am I misunderstanding here?

I suppose my question applies to $log\_c(n) = O(log\_2(n))$ as well.

# Answer
Additionally to already answered in user5876164's comment let me say, that you cannot express $3^n=k \times 2^n+o(2^n)$, because if we assume it for some $k$, then we obtain: $\left(\frac{3}{2}\right)^n=k+o(1)$, which is impossible, as $\left(\frac{3}{2}\right)^n \to \infty$.
> 1 votes

---
Tags: complexity-theory, big-o-notation
---


# Question
Title: Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)?
Hello I solved this leetcode https://leetcode.com/problems/tree-diameter/ question reserved for people who pay the subscription.

The question:

> Given an undirected tree (tree is not disjoint), return its diameter: the number of edges in a longest path in that tree.
>
> The tree is given as an array of edges where edges\[i\] = \[u, v\] is a bidirectional edge between nodes u and v. Each node has labels in the set {0, 1, ..., edges.length}.

So the "easy" way to solve it is to start a dfs at each node in the tree and keep track of the longest path seen so far, which would be `O(n^2)`. Given `n = number of vertexes` in the graph.

However I came up with the below solution that does the job in `O(n)`, I was able to come up with it by going through examples on a piece of paper and then coded it and it passed all the tests, but I can't figure out why it formally works, can anyone help me prove it is correct ?

Here is my code:

```
   def treeDiameter(self, edges: List[List[int]]) -> int:
    def dfs(graph, vertex, prev, maximums):
        for neighboor in graph[vertex]:
            if neighboor != prev:
                tmp = 1 + dfs(graph, neighboor, vertex, maximums)
                if tmp > maximums[vertex][0]:
                    maximums[vertex][1] = maximums[vertex][0]
                    maximums[vertex][0] = tmp
                elif tmp > maximums[vertex][1]:
                    maximums[vertex][1] = tmp
        return maximums[vertex][0]

    graph = collections.defaultdict(list)
    for vertex1, vertex2 in edges:
        graph[vertex1].append(vertex2)
        graph[vertex2].append(vertex1)

    maximums = [[0, 0] for _ in range(len(edges) + 1)]
    dfs(graph, 0, None, maximums)

    res = 0
    for max1, max2 in maximums:
        res = max(res, max1 + max2)
    return res

```

The way I came up with this is I realized if I start my dfs at a node that is on the longest path, then the longest path is equal to the sum of the two longest pathes (because it is a tree there are no cycles) out of this node (which is why I store the two longest pathes `max1, max2` out of a node in the `maximums` array) --\> but what I fail to see is why that works in all cases.

# Answer
> 1 votes
I think this might help. Copied from https://stackoverflow.com/questions/20010472/proof-of-correctness-algorithm-for-diameter-of-a-tree-in-graph-theory.

Let s, t be a maximally distant pair. Let u be the arbitrary vertex. We have a schematic like,

```
    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t

```

where x is the junction of s, t, u (i.e. the unique vertex that lies on each of the three paths between these vertices).

Suppose that v is a vertex maximally distant from u. If the schematic now looks like

```
    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

```

then

d(s, t) = d(s, x) + d(x, t) \<= d(s, x) + d(x, v) = d(s, v), where the inequality holds because d(u, t) = d(u, x) + d(x, t) and d(u, v) = d(u, x) + d(x, v). There is a symmetric case where v attaches between s and x instead of between x and t.

The other case looks like

```
    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

```

Now,

d(u, s) \<= d(u, v) \<= d(u, x) + d(x, v) d(u, t) \<= d(u, v) \<= d(u, x) + d(x, v)

d(s, t) = d(s, x) + d(x, t) = d(u, s) + d(u, t) - 2 d(u, x) \<= 2 d(x, v)

2 d(s, t) \<= d(s, t) + 2 d(x, v) = d(s, x) + d(x, v) + d(v, x) + d(x, t) = d(v, s) + d(v, t), so max(d(v, s), d(v, t)) \>= d(s, t) by an averaging argument, and v belongs to a maximally distant pair.

**PS: I saw many answers after searching the question. I do not have enough repuation to comment otherwise I would have done so.**

# Answer
> 0 votes
I think this is actually a much more natural algorithm than the "standard" one involving two BFSes, linked by nitangle :)

One way to interpret it: The $i$-th entry in `maximums` stores the lengths of the two longest paths emanating from vertex $i$ that (a) have distinct second vertices and (b) avoid a specific vertex (namely, $i$'s parent in the DFS). **The sum of these two lengths is the length of the longest path that has vertex $i$ as its "highest point",** if we imagine picking up the tree by the DFS root (vertex 0), and recursing "down" to a vertex's children.

Since every path in a tree has a "highest point" -- including the overall longest path -- taking the maximum over all $n$ of these maxima will find the overall longest path.

Another note: It's not necessary to store the complete set of per-vertex maximum pairs in an array and then look for the overall maximum among them at the end -- it would suffice to compute, within each call to `dfs()`, that vertex's maximum pair, and then once all that vertex's children are processed, update a global maximum if this pair beats the incumbent solution. This reduces the additional space usage, though not asymptotically (since if the tree is a path and the root is one of its endpoints, $O(n)$ space will still be needed for the `dfs()` stack frames).

---
Tags: algorithms, graphs, proof-techniques, correctness-proof, depth-first-search
---


# Question
Title: Can a trend of android phones slowing down after 2-3 years of usage be attributed to the low durability of RISC CPU used in them?
Laptops, PCs (don't consider Apple products here) have processors that are mainly built on x86 and their life cycle is of the order of 5-10 years.

Or the frequent changing of smartphones has a perception/psychological side of it and not the durability issues of the hardware?

# Answer
Android phones slow down because the *software* applications are rapidly changing. More features get added, and this makes the software consume more memory (RAM) and CPU time. Software keeps getting updated and each update results in it requiring more resources. In response to this, smartphone manufactures have increased the capabilities of the hardware they manufacture. RAM, CPU Frequency, number of cores are increased, and this increases the performance. Thanks to Moore's law, the hardware capabilities and performance tend to be increased without any noticeable increase in cost.

One more reason why smartphones need to be changed continuously is because the Operating System gets updated. Google and Apple allows users to update their Operating Systems by using the same phone only a limited number of times. After this limit, users have no other choice but to buy a new phone to use the newer operating systems. As the support of applications on older models of smartphones gets dropped, the user has no other choice but to upgrade to newer phones. This is known as **planned obsolescence**.

For x86, a similar phenomenon is observed, especially in Windows based laptops. As Windows keeps getting updated, you will observe that the laptop gets slower. This problem can be solved to some extent by increasing the RAM (which is not possible in the case of smartphones). For PCs, you can upgrade the CPU, GPU, RAM and storage, so they tend to be used the longest. For PCs, the Operating System can also be easily changed, and a lighter operating system can be used, which improves the performance.
> 2 votes

---
Tags: computer-architecture, cpu
---


title: Modified topological sort

text:
# Question
Title: Modified topological sort
I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways.

Let's define a "task" $T\_k$ to be a tuple $(a\_k, b\_k, C)$, where $a\_k$ is the amount of active time spent on a task, $b\_k$ the inactive time, and $C$ a set of child tasks that cannot begin until this task is fully complete. For a given task, while I'm actively working on it I cannot do anything else. However, during the inactive period the task continues without my supervision and I can go do some other non-dependent task.

A good example is washing clothes: I might need $a\_k = 5$ to load a washing machine, but then while the cycle runs ($b\_k = 40$) I can go do something else with those 40 minutes. However, the tasks listed in $C$ cannot start until both the active and inactive parts have completed. So, using my existing example, I cannot run the dry cycle on my clothes until I've both loaded the washing machine and waited for the cycle to end.

So, given a set of tasks $T$ a question you could ask is: "What's the fastest I could complete a set of tasks?". In a way this is a topological sort, but there's also some weighting in there that I'm not sure how to navigate with existing topological sort algorithms. Perhaps there is a greedy way to pick the next node?

My question is this:

* Is there an algorithm to solve this problem (that isn't brute-force enumeration of course)
* Does this problem fall into an exist realm of research that I could investigate? Are there any introductory articles you could point me to?

# Answer
Topological sorting would work if all $b\_k$'s were zero. Here is a way that takes into account the $b\_k$'s. Build a dag where each vertex is a task and there are edges from each task to its child tasks. Then, use the following algorithm:

* Out of all sinks (vertices with out-degree zero), find the one whose $b\_k$ value is smallest. Output it, then delete it and all edges into it.
* Repeat, until all vertices have been output.

I believe this will output an optimal schedule, in reverse order (last task first).
> 0 votes

---
Tags: sorting, greedy-algorithms, topological-ordering
---


# Question
Title: splitting of people betwen groups with group prioritiy list per person
Looking for an algorithm for splitting a list of people (S) into groups (G), |S| \<= |G|, more than one person wants to be in a certain group. Every person has a monotone ranking from highest (most desired) to lowest of all the groups. Using this list I want to find the "best matching". "best matching" is when you maximize the "score of the matching". "score of the matching" is the sum of the group rankings of the people that got matched with the group, i.e. summing the ranking that the people gave to the group which was chosen for them.

I'm also interested in ideas for other "fairness" values for maximization.

# Answer
> 0 votes
If you want to maximize the sum of the scores for each participant, this is an instance of the assignment problem; use the Hungarian algorithm, or any other algorithm for computing a maximum matching.

You might also be interested in stable marriage algorithms, which have a different notion of fairness.

---
Tags: algorithms, matching
---


# Question
Title: Describe a turing machine that accepts Language L = {www| w is {a,b}*}
I know that for the language ww, the TM can zig zag across the tape and match symbols to see if the strings are equivalent by first finding the midpoint of the string. However I am lost on how the TM can find out where in www the repeated strings start and stop. I can find midpoint but how do I get one third or two thirds of the string. Any tips to get me started?

# Answer
> 0 votes
Let $\ell$ be the length of the input. You can assume w.l.o.g. that $\ell=3k$ for some integer $k$. If this is not the case (which can be easily checked by your TM), then the answer is trivial.

The problem boils down to finding $k$. In order to do so you can use the following strategy:

1. "mark" the two rightmost unmarked tape cells;
2. "mark" the leftmost unmarked cell;
3. If the cell immediately to the right of the current head position is marked, then you are done since the head must be in position $k$. Otherwise, repeat from step 1.

# Answer
> 0 votes
Steven suggested one solution. I've already tried something similar, basically you need to find the word *w* at the beginning. Then you check the whole input.
You outlined a difficult problem. You may find out over time, but here is a link where it is written in abbreviated form and also with a graph.

https://www.geeksforgeeks.org/turing-machine-for-language-www-w-a-b/

---
Tags: turing-machines
---


title: Memory Invalidation and Misses

text:
# Question
Title: Memory Invalidation and Misses
Assume this particular architecture of a machine. Say we have 4 processors and each processor has its private L1 cache and shared L2 cache. Now if we write to an address in one of the private cache's of the L1 cache then we Invalidate the blocks in the other private cache which contains the same address. Say P0(processor 0) reads an address 100 and so the block containing it say B0 gets stored in the private cache of P0 and as well as in the shared L2 cache. Now say P2 writes to the location 100. So we need to invalidate the block B0 from the private cache of P0. Now if P0 wants to read from address 100 again it will suffer a miss in its private cache, but will it get HIT or MISS in the L2 cache?

I think it will get HIT. Can anyone confirm.

# Answer
It will be HIT in the L2 cache as you have guessed it because L2 cache maintains a directory or a bit vector which tells in which of the private caches the modified state of the block is in. So when L1 of P0 requests it for the second time, L2 will supply the latest modified block.
> 0 votes

---
Tags: computer-architecture
---


title: Time complexity of $a^{n^b}; a,b>1$

text:
# Question
Title: Time complexity of $a^{n^b}; a,b>1$
What ist the time complexitiy of an algorithm with the running time of $a^{n^b}; a,b\>1$? And how is it compared to factorial complexity O(n!)?

# Answer
Let's consider $n!\<e\left( \frac{n}{2} \right)^n=e^{n\ln n+1-n\ln2}$. On other hand $a^{n^b}=e^{n^b \ln a}$. Now we should compare $(n\ln n+1-n\ln2)$ to $n^b \ln a$, where right member wins, when $a,b\>1$: $$\frac{n\ln n+1-n\ln2}{n^b \ln a}\to 0$$
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$
This problem is from an exercise sheet so it would be nice if you could guide me to the solution.

The problem: For $ k \in \mathbb{N}\setminus\\{0\\}$ let $$L\_k = \\{x1y | x \in \\{0, 1\\}^\*, y \in \\{0, 1\\}^{k-1}\\}$$ be the set of words with have at the k-last Position a 1.

(a) How many Myhill-Nerode-equivalence classes does $L\_k$ have? Prove your answer.

(b) Construct an minimal DFA for $L\_2$ from the equivalence classes.

(c) How many states does a minimal NFA for $L\_k$ have? Prove your answer.

What I have:

a) I am pretty clueless, how to approach this problem. I tried to find classes for $k=1, k=2, k=3$ from which I think the amount as a function of k would be $2^k$. But I don't know how to continue.

b) Is pretty easy in comparision, I just added it for the sake of completeness.

c) I think with a) this would be much easier. Because the minimal amount of states is equivalent to the amount of NM classes. But for that I first need a).

Thank you in advance for any advice!

# Answer
> 1 votes
First, I think you have to review the Myhill Nerode Theorem and its relationship to the states of finite automata. You seem to think the number of equivalence classes is the same as the number of states in the minimal NFA, but it's actually the same as the number of states in the minimal DFA.

As a side note, minimization of NFAs is apparently much trickier than minimization of DFAs, so in an introductory formal languages class, you're not going to hear much about minimal NFAs (except in cases like this, where it's straight forward).

So this means it's parts (a) and (b) that are closely related.

As this is a worksheet question, I'll try to only give a guiding hint, rather than a straight-out answer.

The key thing (at least in my opinion) is to realise that each language $L\_{k}$ is that it is only really concerned with the last $k$ symbols in the string. So the number of equivalence classes is closely related to this, and the proof that the obvious guess here works is informed by this observation.

This same observation is what gives the minimal DFA (unsurprisingly, as the equivalence classes exactly correspond to the states!). As the DFA doesn't know when the end of the string is coming up, one way you can think of it is as a little sliding window algorithm, and you should be able to relate the states, transitions and equivalence classes in terms of moving this window along one symbol.

To get the minimal NFA, lean on the nondeterminism. What is the piece of information that the DFA doesn't have that you can just nondeterministically guess?

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


# Question
Title: single circuit simulating multiple Turing machines
You can simulate polynomial time Turing machines with polynomial size circuits, can you simulate multiple poly time TMs with a single poly size circuit?

# Answer
> 2 votes
In a trivial sense, no, because circuits have a fixed input size. To compute the same function as a Turing machine, you need an infinite family of circuits, one for each input size. So a single circuit can't even "simulate" one Turing machine.

So let's restrict ourselves then to inputs just of size $n$, then the question is just are there two Turing machines that compute the same output for every input of size $n$? Well sure, no problem.

Moving back to the family of circuits, fix an infinite family, one circuit for each possible size. Are there two Turing machines that compute the same function for every input size as this circuit family? Again, sure, any two Turing machines with the same language can be paired up with the same family of circuits.

The polynomial bounds even behave nicely (even if they're different polynomials).

Note that this doesn't necessarily hold together once you actually start to think about how to get the family of circuits, and imposing uniformity conditions, but given the question, you're not up to that bit yet.

---
Tags: complexity-theory, turing-machines, circuits, simulation
---


title: Fixed Point Combinator Turing proof

text:
# Question
Title: Fixed Point Combinator Turing proof
I have to proof that Turing's combinator is a fixed point operator, but I can't get it. I tried this:

\begin{align\*} Vg &= (UU)g = ((\lambda f.\lambda x.x(ffx)) (\lambda f.\lambda x.x(ffx)))g = (\lambda x.x((\lambda f.\lambda x.x(ffx))(\lambda f.\lambda x.x(ffx))x))g\\ &= g((\lambda f.\lambda x.x(ffx))(\lambda f.\lambda x.x(ffx))x)g \\\&= g(UUx)g = gVxg \end{align\*} The problem is that I'm getting an extra $x$ at the final. Did I make a mistake while doing beta reduction?

Any help will be appreciated.

# Answer
Your second $\beta$ reduction is wrong.

After the first reduction, you (should) have $(\lambda x.x (U U x)) g$, so after the second you have $g (U U g)$ as required, but you haven't substituted the second $x$ correctly, leaving both it and the $g$ that the function is applied to, giving you $g (U U x) g$, though you have substituted the first $x$ correctly.
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit?
In a code, I saw someone use:

`n&(n-1)` to get the least significant bit of `n` ⇒ 101000 will return 1000

`n&(-n)` to remove the lsb from `n` ⇒ 101000 will return 100000.

This sounds magical to me. Is there any proof for these?

Thanks a lot!

# Answer
For $n=0b101000$ we have $n-1=0b100111$, so $n \\& (n-1)=0b100000$.

As to the second, then knowing $-n=\sim n+1$ we have $-n= 0b10111 +1 = 0b11000$ so $n \\& (-n)= 0b101000 \\& 0b11000= 0b1000$.

**Addition for general proof**.

1. Let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a\_m+ \cdots + 2^k a\_k$, where $m \geqslant k$.Then $$n \\& (-n) = 2^k$$ proof: as we know $-n=\sim n+1$. So, first step, $\sim n$, gives inversion for each bit. Hence in bits lower then $k$ we will have ones and in bit $k$ we will have zero. Now adding $1$ gives all zeros in bits lower then $k$ and in bit $k$ we again have one, but all upper bits are reversed. So $-n$ have in all bits more then $k$ reversed values with respect to $n$, which gives result.
2. Again let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a\_m+ \cdots + 2^k a\_k$, where $m \geqslant k$. If we consider $n-1$, then we get zero in $k$-th bit. So $n$ and $n-1$ have different coefficient only for bit $k$. This gives, that in $n \\& (n-1)$ we have all coefficients same as in $n$ besides $k$-th bit is zero.
> 2 votes

---
Tags: bit-manipulation
---


# Question
Title: Is this possible that quantum computer will be able to violate the Church thesis?
After reading Church's thesis, and godelization theory, it seems everything is futile, is this really true, all the machines we are making machine which is same as before, bounded to not solve halting problems, in more simple terms **can quantum computer do anything that a Turing machine can't?**

PS: In book named Elements of theory of computation first edition, you will find Godelization otherwise it is redacted since second edition reason unknown but chapter 5 named Church Thesis is highly altered since second edition.

# Answer
> 3 votes
No. A classical computer can compute anything a quantum computer can do, given long enough. There are simple methods of simulation that cause an exponential slowdown, which suffices to show that if it is decidable on a quantum computer, it is decidable on a classical computer. (We don't know whether the there might be other faster ways of simulating a quantum computer on a classical computer, but that doesn't affect decidability.)

# Answer
> 1 votes
As far as we know right now, no. Quantum computation makes some problems tractable that are currently intractable for classical computers, but problems that are theoretically impossible for classical Turing machines remain impossible for quantum computers as we understand them. Intractable, meaning the computation would take too long for the result to be useful. Impossible meaning literally not possible.

Computing something outside what's possible for a Turing machine enters the realm of hypercomputation, but that's not quite what quantum computers do.

---
Tags: turing-machines
---


# Question
Title: Ensure a vertex has the highest flow in max-flow algorithm
Let's suppose we have a supplier, sorting facilities, shipping companies and a target warehouse.

We produce n packages of the product, and each goes to a different sorting facility (so every facility receives exactly one package).

A sorting facility then passes the processed product to a shipping company, each sorting facility is only connected to a limited number of shipping companies, meaning that It can only use a limited subset of all shippers to deliver the product to the warehouse.

Now, the company owner's brother runs shipping company A and the owner really want's to help his brother start up his bussiness.
We need to ensure that all packages are delivered, but company must A deliver most of them - so It's a max flow problem with a requirement, that vertex corresponding to company A has the highest flow of all the shipping companies vertices.

Here Is a sample graph representation I have came up with. Vertex 0 is the supplier, vertices 1-6 are the sorting facilities, vertices 7-10 are the shipping companies, and 11 is the warehouse.

Now, assuming vertex 7 is the owner's brother's company, we want to get a maximum flow in this graph such that flow through 7 is greater than flow through 8, 9 or 10

How can this graph (or any of the max-flows algorithms) be modified to ensure, that the requirement holds for vertex 7?

# Answer
Add auxiliary nodes 8a, 9a, 10a between nodes 8, 9, 10 and node 11, so that for example we have 8 -\> 8a -\> 11. Set all the capacities on the (8 -\> 8a, 9 -\> 9a, and 10 -\> 10a) edges to $c = 0$, and run max flow. If there is a solution (if the maximum flow through the graph is equal to the number $n$ of packages to be shipped) then congratulations - we are done. Otherwise, set the capacities to $c = 1$, and go again. And so on until you find the smallest capacity $c^\*$ such that the maximum flow is $n$. If the flow through vertex 7 is larger than this capacity $c^\*$ then we have a solution, but if not there is no solution. If you continue to increase up to $c = n$ and there is no solution, then the original problem has no solution.

---

As requested by D.W. I will elaborate on the correctness and efficiency of this solution. The simple method of increasing $c$ by $1$ each time to find $c^\*$ can be improved by binary searching instead: as $c$ increases the maximum flow will also increase up to $n$, and therefore we can binary search on the possible values of $c$ in order to find the smallest $c^\*$ such that the maximum flow is $n$. This improves the number of calls to a max-flow subroutine from $n$ to $\log n$.

In order to show correctness I will set up some more notation. In any allocation of flow to the graph, let $f\_0$ be the flow through the special warehouse, and $f\_1, \ldots, f\_k$ the flow through the other warehouses. We will call an allocation of flow "feasible" if $f\_0 + f\_1 + \cdots + f\_k = n$ and $f\_0 \> f\_i$ for all $i = 1, \ldots, k$ and "infeasible" otherwise.

Suppose there is no feasible flow. Then no matter how we set $c$ in our algorithm, it will never find a feasible flow either (introducing capacities to vertices only limits the set of solutions). Therefore the algorithm gets the correct answer in this case.

Suppose there is a feasible flow. Out of all possible feasible flows, choose one which minimises $c' = \max\_{i = 1, \ldots, k} f\_i$. Then there is no feasible flow where $f\_i \< c'$ for all $i$, and there is a feasible flow where $f\_i \leq c'$ for all $i$, and hence our algorithm will arrive at $c^\* = c'$. However, the algorithm may not arrive at the same flows: in particular if $g\_0, g\_1, \ldots, g\_k$ are the flows found by the algorithm, we are guaranteed that $g\_i \leq c'$ for all $i = 1, \ldots, k$, but we may not have $g\_0 \> g\_i$ for all $i$.

I think this is a problem with the algorithm actually: it finds $c^\* = c'$ correctly, but needs some help in order to figure out whether flow through the special node can be made strictly larger. There are some things you could do with the residual graph here, or you could use a reduction to a circulation problem with lower bounds on capacities: use the algorithm above, but as a final step introduce the constraint that the flow through the special node must be at least $c^\* + 1$, and check for a solution.
> 0 votes

---
Tags: algorithms, network-flow
---


# Question
Title: Inductive proof for the Bubblesort algorithm
I'm studying Algorithms and Data Structures from *The Algorithm Design Manual* and I'm having a hard time going through the exercises. Specifically, the proofs are a bit hard and not really explained in the book(It only gives two proof exmaples).

```
Prove the correctness of the following sorting algorithm.
    Bubblesort(A)
        for i from n to 1
            for j from 1 to i − 1
                if (A[j] > A[j + 1])
                    swap the values of A[j] and A[j + 1]

```

I would really appreciate if you could help me with an inductive (or any kind of proof I don't really know) for this exercise.

# Answer
> 2 votes
**What is a Proof of Correctness:**

Algorithms are identified with **pre-conditions** and **post-conditions**. The pre-conditions are assumptions you make about the algorithm's inputs. Post-conditions describe what we want the algorithm to have accomplished once it terminates.

For an algorithm to be considered "partially correct", whenever the pre-conditions hold, the post-conditions must follow. For it to be considered "totally correct", it must be partially correct and *halt*, i.e. take a finite number of steps.

Pre and post-conditions are something one specifies about an algorithm, not something one proves about it. A typical precondition for a sorting algorithm might be "A\[1...n\] is an array of integers". A typical postcondition might be "A\[1...n\] is a sorted array of integers with the same values it had before the algorithm was executed".

That's a lot of formalism to get out of the way before we even talk about the problem, but it's important to be rigorous.

**Showing `Bubblesort` is correct**

To show `Bubblesort` is correct, we should show that the post-conditions follow assuming the pre-conditions hold. Total correctness will follow since `Bubblesort` trivially halts.

**Loop Invariants**

This is something you see everywhere in proofs of correctness that have loops. Instead of talking about the whole algorithm "at once", it's useful to come up with something that will be true for each iteration of the loop. This often lends itself to an inductive argument. The loop invariant you want to come up with is something that will help you conclude what you want to conclude at the end of the day - that A\[1...n\] is sorted once we terminate.

Here's what I came up with to that end. For any iteration $i$ of the outer loop: For any $a \in \\{1,...,n\\}$:

**If** there is a $b \in \\{1,...,n\\}$ such that $a\>b$ but $A\[a\]\<A\[b\]$ at the start of the iteration, then at some point in the inner loop, $A\[a\]$ and $A\[a-1\]$ will swap. Similarly, if there is a $b\>a$ such that $A\[a\]\>A\[b\]$, then $A\[b\]$ and $A\[b+1\]$ will have swap at some point in the inner loop.

**Else**, $A\[a\]$ won't change.

To prove this, it would be helpful to first show that whenever an $a$ satisfies the conditions in the "If" part, $a \leq i$ is true. This lemma could use an inductive argument. By the way this is one (possible clunky) way of coming up with the invariants, you might have a more concise way of phrasing what you need. I haven't written the full proof so I might have inefficiencies up there.

**Wrapping Up**

Once you show the loop invariants above are true, we can use them to conclude that $A\[1..n\]$ comes out the other end a sorted list of integers. Let $A\[1..n\]$ refer to the original list, and $A'\[1...n\]$ refer to the modified list. Let $a \in \\{1,...,n\\}$ be arbitrary, and let $c \in \\{1,...,n\\}$ be a correct sorted index of $A\[a\]$ in $A\[1..n\]$, i.e. $c$ is the index $A\[a\]$ should be at in a sorted version of $A$. We want to show that $A'\[c\]=A\[a\]$.

If $a$ was already in it's correct position in $A\[1..n\]$ (i.e. $a=c$) then we're done, because this means for any $b \< a$, $A\[b\]\<A\[a\]$, thus the swap condition in the inner loop will never be satisfied, meaning $A'\[a\]=A\[a\]$. Otherwise, either there exists some $b\<a$ such that $A\[b\] \> A\[a\]$, or some $b\>a$ such that $A\[b\]\<A\[a\]$. In either case, the loop invariants tell us that $A\[a\]$ will move at least one step in the correct direction after each outer-loop iteration. The maximum distance between $a$ and $c$ is $n-1$, and since the "Else" of the loop invariant essentially tells us that $A\[a\]$ will stop moving when $a=c$, we can say that $A\[a\]$ will get to index $c$ and stop, so $A'\[c\]=A\[a\]$ as required.

That's the gist of it, I left out the proofs of the invariants, and there might be other gaps in my response. Hopefully you can fill those in. Sorry for the long answer.

---
Tags: algorithms
---


# Question
Title: Time complexity of a machine which combines Insertion Sort and Quicksort
Given a machine that sorts an array of length $n$ with the following algorithm:

1. Sort first $2\sqrt{n} + 1$ elements of array with **Insertion Sort**.(Check Insertion Sort)
2. Select the median of the whole array (after its first $2\sqrt{n} + 1$ length part is sorted from step 1) as the pivot then partition the array.(Check Quicksort)
3. Do both above steps for both partitions resulted from step 2 in a recursive way.

**Suggest a recursive function that computes the time complexity of the above machine in its worst case.**

$\rule{17.5cm}{0.4pt}$

As I see it's somehow a mixture of **Quicksort** and **Insertion sort** and every time the machine wants to quick sort a partition of length n we are sure that first $2\sqrt{n} + 1$ elements are sorted. we know:

* Quicksorting a sorted array of length n is from $O(n\log n$) and Insertion sorting it is from $O(n)$.
* worst case of both Quicksort and Insertion sort is $O(n^2)$.

# Answer
> 0 votes
The worst case for Quicksort happens when each partitioning divides an array of size n into sub arrays of size 1 and n-1. In your case, is that possible? Why isn’t it possible? What is the worst outcome of partitioning if the pivot is the median of 2k numbers? So what is the worst case in your algorithm?

---
Tags: algorithms, time-complexity, algorithm-analysis, sorting, quicksort
---


# Question
Title: Can one find an algorithm whose running time is larger than Ackermann's function?
Is there an example of an algorithm whose time complexity is strictly larger than Ackermann's function?

# Answer
$A(n,n)$ is computable. So a trivial algorithm with complexity $O(A(n,n)^2)$ is the following:

1. Compute $x = A(n,n)$.
2. Loop $x^2$ times, doing nothing.
> 2 votes

---
Tags: runtime-analysis
---


title: Is NP in NP/Poly?

text:
# Question
Title: Is NP in NP/Poly?
The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice function only adds power; however, I'm having a hard time understanding NP/poly's containment of NP from the angle of the definition below of NP/poly:

A nondeterministic circuit has two inputs x,y. The circuit C accepts x iff there exists y such that C(x,y) = 1. The size of the circuit is measured as a function of |x|. **NP/poly** is the set of languages decided by polynomial size non-deterministic circuits.

A nondeterministic Turing machine has two inputs w,c. A verifier V accepts w iff there exists a certificate c such that V(w,c) = 1. The length of computation is measured as a function of |w|. **NP** is the set of languages decided by a nondeterministic Turing machine that runs in polynomial time.

From the verifier angle, for a couple reasons it is hard to see how a single circuit of poly size could implement a verifier for an NP problem for all the words of a given length.

1. For example. let's say an NP language has an exponential number of yes instances of a given length all with various certificates. Let's say we consider those certificates that are descriptions of the accepting branches of a non-deterministic Turing machine that correctly decide each w of the given length--how could a **single** poly size circuit simulate all these (possibly exponential number of) c's (solution paths) on their respective w's to see if the verifier works?
2. A circuit can only have a single size input and for each size of input there is only one circuit in the circuit family; yet, for a given word w of length b there are an infinte number of c's that are poly|w| that are potential certificates--how can the single circuit for inputs of length b accept on all the different certificates for the w's of length b when their lengths are variable?

Looking for some help on how I'm thinking about this wrong, thank you!

# Answer
> 2 votes
A language $L$ is in $\mathsf{NP}$ if there exists a polynomial $p$ and a deterministic Turing machine $T$, running in polynomial time, such that:

> $x \in L$ if and only if there exists $y$ of length $p(|x|)$ such that $T(x,y) = 1$.

Usually we assume that $|y| \leq p(|x|)$, but we can get this version using a simple padding argument, which slightly increases $p$. For example, we could encode $y$ as follows: $0^{p(|x|)-|y|}1y$. This always has length $p(|x|)+1$. (We also obtain a new witness $0^{p(|x|)+1}$ which corresponds to no $y$, which $T$ can just immediately reject.)

For every $n$, we can construct a polynomial size circuit $C\_n$ on $n + p(n)$ inputs such that for every $x$ of length $n$ and $y$ of length $p(n)$, we have $C\_n(x,y) = T(x,y)$. A similar construction appears in Cook's theorem, for example. This shows that $\mathsf{NP} \subseteq \mathsf{NP/{poly}}$.

---
Tags: turing-machines, np, nondeterminism, circuits, simulation
---


# Question
Title: Time estimation for successful brute force attack
If I have a password =

> "passwordPASSWORD"

and the time it takes to encrypt the password successfully is:

> 353259.545 nano seconds

is there a formula that can work out the time taken to successfully conduct a brute force attack on the password?

I was thinking:

> AvrgTimeToEncrypt^PasswordType x PasswordLength ?

# Answer
> 1 votes
Passwords are not encrypted they are hashed with proper password hashing algorithms like Scrypt, PBKDF2, or better Argon2, the last is the winner of the 2015 password hashing competition.

I would like to assume that you use one of the above, however, the time that you measured implies the opposite. At least, you used an iteration count as little as possible.

The attackers are not like you - and they will never be - to check a single candidate password one at a time. They like to use as much as possible parallelization. See hashcat as a good example. CPUs, GPUs, ASICs, and FPGAs can be combined to find the target. Simple hashing can be searched massively in parallel even in a single GPU.

Therefore we need to mitigate these attacks as much as possible. The proper password hashing algorithms are memory-hard functions to prevent the massive parallelization and they have iteration count to increase the timing. With these, the attacker's massive parallelization is prevented and the search timing is crippled. Usually, the work factor is adjusted for the user's perspective so that the user does not wait so much for a login. For example, 400K iteration is for PBKDF2 may enough.

> I was thinking:
>
> > AvrgTimeToEncrypt^PasswordType x PasswordLength ?

Once we forced the attacker to a single run on the single CPU thread, or one in a GPU, etc. we can talk about the timings a bit more precisely.

Let formalize as;

* $\mathcal{S}$ as the password space.
* $t$ is the execution time of a machine to test a given password hash and candidate from $\mathcal{S}$. (we use a uniform approach here, the timing will be different in a CPU, GPU).
* $c$ is the number of machines that the attacker can use.

Now the search time of the space $\mathcal{S}$ is

$$ \frac{|S|}{t \cdot c}$$

---
Tags: cryptography
---


# Question
Title: Deterministic algorithms for computational distance between distributions
Computational distance between sequences of distributions $\\{X\_i\\}\_{i \in \mathbb{N}}$ and $\\{Y\_i\\}\_{i \in \mathbb{N}}$ can be defined as the maximum, over all probabilistic polynomial time algorithms $A$, of $$ \left|\underset{x \sim X\_{n}}{\mathsf{Pr}}(A(x) = 1) - \underset{x \sim Y\_{n}}{\mathsf{Pr}}(A(x) = 1)\right|, $$

for each $n \in \mathbb{N}$. We can, very similarly, define computational indistinguishability to be when the computational distance is a negligible function of $n$. Here is my question: can we use a deterministic polynomial-time algorithm in place of a probabilistic one without loss of generality? Can we say that the maximum computational distance is achieved by a deterministic algorithm? Will this algorithm be non-uniform?

# Answer
Hint:

> Every randomized algorithm $A(x)$ can be expressed as a deterministic algorithm $A(x;r)$ where $r$ is randomly chosen. Now what can you say about the value of that absolute difference for different choices of $r$? What would you like to be able to say about it?
> 1 votes

---
Tags: algorithms, probability-theory
---


title: Can you build a solver from a verifier?

text:
# Question
Title: Can you build a solver from a verifier?
Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or generate / get back the language L itself?

At a glance, the answer seems to be yes--you could just try every word, certificate pair; however, there is a part I'm not sure about with this process: sure there are only a finite number of words of each size, but there are an infinte number of words that are poly|w| for any given size |w| that are potential certificates. So, without the certificates, you could be trying different strings as the second input for the same word as first input forever to no avail.

Thanks!

# Answer
> 2 votes
Having a verifier for a language in *general* is known as semidecidability, which is actually weaker than decidability. So in general, the answer is no, we can't build a decider for $L$.

But if the verifier is ***efficient*** (i.e., $L \in $ **NP**), then indeed $L$ is decidable, and your argument is pretty close for why that is.

Let's say we have an efficient verifier $V(x,c)$.

Given an $x \in \Sigma^\*$, the "certificate space" is $C=\\{c \in \Sigma^\* \mid |c| \leq p\_L(|x|)\\}$, where $p\_L$ is a polynomial. That means the certificate space is actually finite. $x \in L$ if and only if there exists a $c \in C$ such that $V(x,c)$ accepts. So indeed we can just check every possible certificate for a *given* input $x$ to construct a decider for $L$.

In fact with a bit more work you can show that $L \in$ **EXP**, meaning $L$ is decidable in exponential time.

---
Tags: turing-machines, data-compression, semi-decidability
---


# Question
Title: What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.

Here is the problem: ***A company is in the process of reducing its office space and wishes to find the path that will minimize double-rent costs during the transition period.***

**Constraints:**

* There are 200 teams in the company (team = indivisible unit). Teams are of different sizes ranging from 10 to 500 individuals.
* The start and end locations for each team are given.
* There are 250 office locations initially (1 per team), 150 will ultimately be removed and 100 will be added. The 100 remaining locations may see a change in occupant, and there will/can be empty locations at any time period.
* The transition period is of 24 time-periods (months), however, teams do not need to move every month, and should move only when new buildings are added. Teams may move 0, 1, 2 or 3 times during the 24 month time-span
* Locations are added at different time periods. Once a building is added, monthly rent starts to be charged.
* Locations which are removed have leases ending at different time periods, but leases can be terminated early for a set fee.

**Cost function to minimize:**

$$C = \sum\_{t=0}^{24}\left (M(F\_{t},F\_{t-1}) + DR\left (F\_{t} \right ) +T(F\_{t})\right)$$

with:

* $M(F\_{t},F\_{t-1})$ the cost of moving teams from one location to another between 2 subsequent time periods, here moving cost per team is an arbitrary constant.
* $DR\left (F\_{t} \right )$ the cost of double-rents for the footprint at time *t*. If at time *t*, a team's start and end locations are available, **only the rent of the team's start location is counted for computation of double rent**.
* $T(F\_{t})$ the total of early lease termination fees at a time period. Early lease termination fees depend on each location.

**Options explored:**

I have started exploring different tracks to answer this problem, namely :

1. Create a graph with every possible permutation at every time step and then find the shortest path using a tree search algorithm. However, the large number of teams, locations and time periods define an immense number of permutations hence I am pretty sure I cannot list all possible trajectories.
2. I am thinking of using a classical Solver-type tool in Python to find optimal path, however, I fear the number of variables may be too large.

My research also led me to potential methods in the fields of Dynamic Programming, Integer Programming, Branch & Bound.

Is there a clear algorithm or manner to address this that comes to mind ?

**Edit :** I forgot to mention that teams may move 0, 1, 2 or 3 times during the 24 month time-span.

# Answer
> 1 votes
This kind of scheduling problem might fall within the area of operations research.

I would suggest using integer linear programming. You can formulate this as an instance of ILP, and then solve with an off-the-shelf ILP solver (e.g., Gurobi or CPLEX).

I'll outline a way you could formulate this as an instance of ILP. We'll let $\ell$ range over locations, $t$ over teams, and $i$ over months (time periods). Introduce the following zero-or-one variables:

* $x\_{t,\ell,i}=1$ if team $t$ is at location $\ell$ during month $i$.
* $s\_{\ell,i}=1$ if you start renting the location $\ell$ at the start of month $i$.
* $e\_{\ell,i}=1$ if you terminate (end) renting the location $\ell$ at the end of month $i$.
* $a\_{\ell,i}=1$ if location $\ell$ is available for use during month $i$.
* $m\_{t,i}=1$ if team $t$ moves at the end of month $i$ to a new location.

Then all of your constraints can be expressed as linear inequalities:

* $\sum\_{\ell} x\_{t,\ell,i}=1$: each time has a home somewhere in each month.
* $x\_{t,\ell,1}=1$ if $\ell$ is the starting location for team $t$; $x\_{t,\ell,24}=1$ if $\ell$ is the ending location for team $t$.
* $s\_{\ell,1}=1$ if $\ell$ is one of the original 250 locations. $s\_{\ell,1}=0$ if $\ell$ is not one of the original 250 locations.
* $a\_{\ell,i} = s\_{\ell,1} + \dots + s\_{\ell,i} - (e\_{\ell,1} + \dots + e\_{\ell,i-1})$.
* $x\_{t,\ell,i} - m\_{t,i} \le x\_{t,\ell,i+1} \le x\_{t,\ell,i} + m\_{t,i}$.
* $\sum\_t x\_{t,\ell,i} \le a\_{\ell,i}$.

Now the cost is a sum of the moving costs (a linear function of the $m$'s), the rent costs (a linear function of the $a$'s), and the early termination fees (a linear function of the $e$'s), so the cost is a linear function of the variables. Thus, you have an ILP instance, which you can give to an ILP solver and ask it to find the optimal solution -- or the best solution it can find within a set time bound. You'll have about $350\times 200 \times 24$ variables, i.e., about 1.6M variables, which is large but not necessarily infeasible.

---
Tags: algorithms, optimization, dynamic-programming, linear-programming, integer-programming
---


title: Choosing the right function

text:
# Question
Title: Choosing the right function
I'm trying to hash integers `n = 4k`(0,4,8,12,16...) into an array of linked lists of size 4 (chaining). What is a good hasing function that guarantees a good distribution of the keys? that means to use all indexes of the array from 0 to 3.

# Answer
No hash function can *guarantee* a good distribution. All you can do is finding a hash function that will usually create a good distribution.

The table size is quite important for this: If the table size is a prime p, then just using n modulo p as the hash value is usually quite good. Note that in your case, 4 is not a prime. Actually all your values are multiples of the table size. And if you has pointers for example, then it is quite possible that all pointers are multiples of 8 or 16, so having a table size of 4, 8 or 16 is not clever.

Obviously if your integers are multiples of 4, but with all four possible values modulo 16 being equally minded, then (n / 4) modulo 4 would work quite well. But in general, you should avoid an unfortunate table size like the one you have.
> 1 votes

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


title: Are "pipes" puzzles NP-hard?

text:
# Question
Title: Are "pipes" puzzles NP-hard?
Is the decision version (i.e. does a solution exist) of this puzzle NP-hard (for an nxn puzzle)? It feels like it has very local strategies which allow easily solving the instances, but it's not obvious to me that these generalize to larger puzzles. The rules are as follows:

1. Each tile has exits on some of its edges
2. Each tile may be rotated but not flipped
3. All tiles must form a single component in solution where two adjacent are connected if both of them have exits touching
4. All exits must be connected to an exit on the other tile they face

It's very easy to see that brute force requires exponential time, but constructing a gadget to show that this puzzle is NP-hard seems quite difficult.

# Answer
> In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles. Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.

It is tough to be a plumber. Král, Daniel; Majerech, Vladan; Sgall, Jirí; Tichy, Tomass; Woeginger, Gerhard. In: Theoretical computer science, Vol. 313, No. 3, 2004, p. 474-484.

https://doi.org/10.1016/j.tcs.2002.12.002
> 2 votes

---
Tags: np-hard
---


# Question
Title: Does there exist standardized language-agnostic data structure notation?
I wonder if there exists language-agnostic data structure notation. Preferably a standard, allowing to describe data structures and basic data types. e.g. something like a subset of `WebIDL`.

A motivation is to describe data structures (a model) in a way that is standardized and language-agnostic. Then have a set of mappings of those data structures into various representations (`XML`, `JSON`, `YAML`)

# Answer
In terms of notation:

* Isn't XSD exactly what you are looking for? (barring all the "severe criticism" ...). Also not sure if you are looking for a notation convenient to hand-write, that's certainly NOT XML :-).
* Typedefs and preserves seem to have more of a mathematical basis, perhaps closer to what you are looking for. A related HN thread.

I suspect you already know a lot of these projects, usually the focus is in serialization:

Investigating this space I found Arrow, "a language-independent columnar memory format" for sharing memory between programs, with libraries for a dozen of languages. Turns out it uses flatbuffers under the hood.

Now that I came up with this list and I suspect you may be familiar with a lot of them, perhaps will be useful to know in which way the thing you are looking for is different. I think the keyword "**notation**" on your question is the key.

Cheers!
> 3 votes

---
Tags: data-structures, notation
---


# Question
Title: Can PDA accept only by final state without finish reading input?
I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the input is read fully or not).

I can guess PDA with the new definition of acceptance is less powerful, and easy to see every language accepted by this PDA is accepted by some PDA with the conventional definition. But, can anyone give some idea how to show some languages are not accepted by the new PDA?

# Answer
> 1 votes
Prefixes. How would you accept both $a$ and $aa$ ?

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


title: any one can prove following inequality?

text:
# Question
Title: any one can prove following inequality?
are for every $\alpha \in N $ , $ \frac{1}{\alpha-2} \geq \frac{1}{\alpha}+\frac{1}{\alpha-1}$?

# Answer
> 3 votes
That inequality is not defined for $\alpha = 0, 1, 2$. For $\alpha \> 2$ you have:

$$ \frac{1}{\alpha-2} - \frac{1}{\alpha-1} - \frac{1}{\alpha} = \frac{\alpha(\alpha-1)-\alpha(\alpha-2)-(\alpha-1)(\alpha-2)}{\alpha(\alpha-1)(\alpha-2)} $$

Clearly the denominator is always positive. Regarding the numerator: $$ \alpha(\alpha-1)-\alpha(\alpha-2)-(\alpha-1)(\alpha-2) = \alpha(\alpha-1-\alpha+2) - (\alpha-1)(\alpha-2) =\\ \alpha - (\alpha-1)(\alpha-2) = \alpha - \alpha^2 + 2\alpha + \alpha -2= -\alpha^2 + 4\alpha - 2, $$ which is negative as soon as $\alpha \ge 4$. In fact, your inequality is only true for $\alpha=3$.

---
Tags: discrete-mathematics
---


# Question
Title: Relationship between inductive families and type-returning functions
Dependently typed languages such as Agda support inductive families, also called indexed datatypes, which allow type parameters to vary between constructors. This can be used to define a set of relations between types, which can be used to constrain existentials. For example, we can capture the relation

$$\begin{align\*} \mathsf{Unit} &\longmapsto \mathsf{Bool}\\ \mathsf{Nat} &\longmapsto \mathsf{Int} \end{align\*}$$

in the following Agda type:

```
data Link : Set → Set → Set where
  link-a : Link ⊤ Bool
  link-b : Link ℕ ℤ

```

We can then define a type `Tie` that pairs a value of type `Link A B` with a function `A → B`:

```
data Tie (L : Set → Set → Set) : Set₁ where
  tie : ∀ {A B} → L A B → (A → B) → Tie L

```

Just for further illustration, here are a few examples of working with these types:

```
tie₁ : Tie Link
tie₁ = tie link-a λ tt → true

tie₂ : Tie Link
tie₂ = tie link-b λ n → + n

app-tie : Tie Link → ℕ → Bool ⊎ ℤ
app-tie (tie link-a f) _ = inj₁ (f tt)
app-tie (tie link-b f) n = inj₂ (f n)

```

This is a useful technique, and this pattern is common in languages like Haskell (where inductive families correspond to GADTs). However, in Agda, the construction is somewhat awkward, as `Tie` belongs to `Set₁` rather than `Set` due to the need to existentially embed `A B : Set` in the `tie` constructor.

I find this unsatisfying, as a simple rearranging of our types allows a definition of `Tie` that belongs to `Set`. Instead of defining `Link` as an inductive family, we define it as a combination of an index and a type-returning function:

```
data LinkI : Set where
  link-a′ : LinkI
  link-b′ : LinkI

Link′ : LinkI → Set × Set
Link′ link-a′ = ⊤ ,′ Bool
Link′ link-b′ = ℕ ,′ ℤ

```

Now we can define a version of `Tie` that contains no types and therefore belongs to `Set`:

```
data Tie′ {I : Set} (L : I → Set × Set) : Set where
  tie′ : (i : I) → uncurry′ Morphism (L i) → Tie′ L

```

At first blush, we seem to be able to do all the same things with this formulation:

```
tie′₁ : Tie′ Link′
tie′₁ = tie′ link-a′ λ tt → true

tie′₂ : Tie′ Link′
tie′₂ = tie′ link-b′ λ n → + n

app-tie′ : Tie′ Link′ → ℕ → Bool ⊎ ℤ
app-tie′ (tie′ link-a′ f) _ = inj₁ (f tt)
app-tie′ (tie′ link-b′ f) n = inj₂ (f n)

```

However, this indirect encoding is annoying to work with. Seeing as the transformation is entirely mechanical, intuitively it seems we *ought* to be able to somehow achieve `Tie Link : Set` while retaining `Link` as an indexed type, but it isn’t clear to me that this is actually possible.

Given the above context, my question is threefold:

1. Are `Tie` and `Tie′` meaningfully distinct, in the sense that `Tie` allows doing things that `Tie′` does not? If so, what?
2. One can argue that `tie` does in fact contain `A B : Set` while `tie` does not, so `Tie` must surely belong to `Set₁`. But the types `A` and `B` can always be easily reconstructed from `Link A B`, so surely they don’t *need* to be stored, in a similar sense to that described in Inductive families need not store their indices. Is this reasoning flawed, or is this simply an implementation infelicity?
3. Has the relationship between these two constructions been treated explicitly in any existing literature?

# Answer
> 4 votes
As mentioned by Andrej, this is an instance of transporting along an equivalence of families and display maps. In this specific case, we have an equivalence of graphs and relations.

```
open import Function
open import Data.Product
open import Relation.Binary.PropositionalEquality
open import Level renaming (zero to lzero; suc to lsuc)

-- type of relations on a set
Rel : ∀{i j} → Set i → Set (i ⊔ lsuc j)
Rel {i}{j} V = V → V → Set j

-- type of graphs with set of vertices V
record Graph {i j}(V : Set i) : Set (i ⊔ lsuc j) where
  field
    E   : Set j   -- edges
    src : E → V   -- source vertex
    tgt : E → V   -- target vertex
open Graph

Rel→Graph : ∀ {i j V} → Rel {i}{j} V → Graph {i}{i ⊔ j} V
Rel→Graph R = record {
  E   = ∃₂ λ s t → R s t ;
  src = proj₁ ;
  tgt = proj₁ ∘ proj₂ }

Graph→Rel : ∀ {i j V} → Graph {i}{j} V → Rel {i}{i ⊔ j} V
Graph→Rel {V} G s t = ∃ λ e → (G .src e ≡ s) × (G .tgt e ≡ t)

```

Note that we can only define the round-tripping functions if `i ≤ j`, since then the output `i ⊔ j` level becomes `j`, and the trip is well-typed. Your `Link` definition does not fit into this, but it's possible to just redefine it as `Link : Set → Set → Set₁` without loss of generality (as the two definitions are equivalent).

If the levels check out, we can show that round-tripping in both directions yields equivalent relations and graphs respectively. We don't need to know anything about the internals of the relations and graphs involved; this equivalence always holds.

Your transformation makes use of the fact that the set of edges for the graph is equivalent to a small set, since the relation only has two possible edges.

```
open import Data.Unit
open import Data.Bool
open import Data.Integer
open import Data.Nat

data Link : Set → Set → Set where
  link-a : Link ⊤ Bool
  link-b : Link ℕ ℤ

-- the graph of Link
Link' : Graph Set
Link' = Rel→Graph Link

-- an equivalent graph with smaller edges
Link'' : Graph Set
Link'' = record {
  E   = Bool ;
  src = λ {false → ⊤; true → ℕ} ;
  tgt = λ {false → Bool; true → ℤ} }

```

Now, anything which depends on an edge only needs to depend on a `Bool`. In particular, `Tie' Link'' : Set`.

```
record Tie {j} (R : Rel {_}{j} Set) : Set (lsuc j) where
  field
    E   : ∃₂ λ A B → R A B
    fun : proj₁ E → proj₁ (proj₂ E)

record Tie' {j} (G : Graph {_}{j} Set) : Set j where
  field
    E   : G .E
    fun : G .src E → G .tgt E

```

The equivalence of graphs and relations generalizes to relations of any arity, and also to multiple relations of arbitrary arities, where relations can be indexed over other relations. In general, the equivalence says that for each telescope of dependent n-ary relations, there is a direct category $C$ such that the telescope is equivalent to the set of functors from $C$ to $\textbf{Set}$.

In the case of graphs, $C$ has two objects and two arrows between them, going in the same direction, so a functor $F : \[C,\textbf{Set}\]$ consists of two sets $V,E$ and two functions $src, tgt : E \rightarrow V$, so we can see that every $F$ is a graph.

> Are `Tie` and `Tie′` meaningfully distinct, in the sense that `Tie` allows doing things that `Tie′` does not?

They are equivalent, we get one from the other by transporting the parameter along the graph-relation equivalence.

> Seeing as the transformation is entirely mechanical, intuitively it seems we ought to be able to somehow achieve `Tie Link : Set` while retaining `Link` as an indexed type, but it isn’t clear to me that this is actually possible.

If we're working in cubical Agda, the graph-relation equivalence can be proven using univalence. Then, every possible construction which depends on a relation can be transported to another which depends on a graph. Additionally, everything which depends on `Link` can be transported to depend on `Rel→Graph Link`. So at least this part works completely automatically.

However, the resizing part is not automatic, i.e. we have to prove that `Rel→Graph Link` is equivalent to `Link''` with the small set of edges. It is not true in general that the set of edges for a relation is smaller than the set of vertices. Probably it's possible to have a conservative algorithm which tries to find such resizings, I don't think it has been researched.

> ... in a similar sense to that described in Inductive families need not store their indices. Is this reasoning flawed, or is this simply an implementation infelicity?

The technique in "Inductive types need not store their indices" is related but not exactly the same thing. In that paper, the transformation is a bit more restricted & specific thing, as there the point is to convert an inductive type family to a purely recursive one. The family-display map translation can be also used to get rid of indices, but that works in a "non-algorithmic" and different way. A classic example is vectors.

Let's have `Vec A : ℕ → Set`. We have an equivalence between `ℕ → Set` and `Σ Set λ A → (A → ℕ)` (as another case of the family-display map equivalence).

```
open import Data.Vec
-- Vec : Set → ℕ → Set

Vec' : Set → Σ Set λ A → (A → ℕ)
Vec' A = ∃ (Vec A) , proj₁

```

But now we can notice that `∃ (Vec A)`, the so-called "total" type (analogous to the type of edges previously) is equivalent to `List A`.

```
open import Data.List

Vec'' : Set → (∃ λ A → A → ℕ)
Vec'' A = List A , Data.List.length

```

Now, we can convert back to the family version with the generic equivalence:

```
Vec''' : Set → ℕ → Set
Vec''' A n = ∃ λ (l : List A) → Data.List.length l ≡ n

```

Which is a definition of vectors which does not store indices. But this is more like a hint, and this de-indexing does not work in a mechanical way, unlike the "need not store indices" technique.

> Has the relationship between these two constructions been treated explicitly in any existing literature?

I don't know of any reference which is exclusively about this equivalence, but it's commonly featured in category theory and type theory (or math in general). The two definitions of graphs is a classic example. There's also the equivalence of indexed categories (family version) and fibrations (display map).

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