# Question
Title: Minimum number of adjacent swaps needed to sort a circle of elements
I have been thinking about some problems in combinatorics and I came across a problem I'm having trouble with.

Suppose you have a list $L$ of length $n$ (wlog the elements of the list are 1,2,3,...,n) and you want to sort it circularly (meaning \[3,1,2\] is sorted) with swaps of adjacent elements, but you are also allowed to consider the first and last elements as adjacent. What is the minimal number of swaps required?

The way to think about this, I think, is to consider the elements of $L$ arranged around a circle, in order. There are $n$ ways to do this, each with a different element at the top. What I want to do is just arrange $L$ in each way, sort it while counting the swaps, then take the minimum.

The problem I have is that elements of the list don't stay fixed: for example I can move 1 into the correct place, but when I move 2 into the correct place, I might move it past 1, which would mess up the position of 1. I am not really sure this is a good idea, since I'm not sure where the "correct place" of an element is, since any place around the circle could be correct.

Another idea I have is to fix 1 and sort the circle around 1 (i.e. I move 2 into place relative to 1, then 3 and so on). Then do it for 2 and so on, then take the minimum of the number of swaps I did while fixing each element. But is it true that this gives the optimal sequence of swaps?

This doesn't seem like an efficient solution either, since I am actually doing swaps on a list rather than some clever calculation. I know that the number of swaps in e.g. bubble sort is the number of inversions in the list. Is there a similar calculation I can do for circular lists?

# Answer
> 0 votes
Suppose we have two lists $L$ and $M$ of length $n$. They are identified as circular lists if and only if, when you write out $(L\_1 \ldots L\_n)$ and $(M\_1 \ldots M\_n)$, they give the same permutation, when considered as an element of $S\_n$.

We can consider the graph $\Gamma$ with vertex set $(123\ldots n)^{S\_n}$ (that is, the $n$-cycles in $S\_n$). $\Gamma$ has an edge $(v, w)$ iff there is a transposition of adjacent elements (adjacent when we write $v$ down as $(v\_1, \ldots, v\_n)$) taking $v$ to $w$. This is well-defined since the only different way to write a cycle is by cyclically permuting it - the adjacent elements stay adjacent.

Given a circular list $L$, the problem is now finding the distance in $\Gamma$ from $L$ to $(1\ldots n)$.

To actually compute this, I used the GAP algebra system. We can take some steps to define the edges in a nicer way.

Let $G = S\_n$. $G$ acts on the vertex set $V$:

$$\sigma \cdot (v\_k)\_{k=1}^n = (v\_{\sigma(k)})\_{k=1}^n$$

Also notice there is one vertex orbit, since any vertex can be relabelled to any other vertex.

Using this, we can define the group action in GAP:

```
G := SymmetricGroup(n);
ncycle := PermList(Concatenation([2..n], [1]));
all_ncycles := ncycle^G;
action := function(cycle, g)
    list := WritePermAsList(cycle);
    result := [1..n];
    for i in [1..n] do
        result[i] := list[i^g];
    od;
    return WriteListAsPerm(result);
end;

```

where `WritePermAsList` just writes e.g. the permutation `(1,2)` as the list `[1,2]` and so on.

Now we have the action, we can define a graph `Gamma` with vertex set $V$ with `NullGraph` and use `AddEdgeOrbit` to add all edges corresponding to the permutations we want to allow. In this case, we want to allow permutations of the form $(i\\;i+1)$ and $(1 \\; n)$. So we do `AddEdgeOrbit(Gamma, [1, 1^Permutation(sigma, ncycles, action)])` for each `sigma` we want to allow.

Now computing the answer to the question I asked: "What is the minimal number of swaps required \[to sort $L$\]?" is just `Distance(Gamma, 1, i)` where `i` is the vertex representing our circular list $L$ since 1 represents $(1\ldots n)$ in our graph and we want to sort meaning get to $(1\ldots n)$.

I think this method isn't even that bad since I only really need this for small (length less than 10) lists. The simple structure of the graph means that we don't actually need to store all that much information about it (certainly we don't need to keep a huge list of vertices and edges in memory).

There are probably more insights about how to reduce this problem to something else, but this was good enough for me.

# Answer
> -1 votes
Even if you want to sort circularly, you definitely need a point of reference. Deciding where it should be implies you'll need to look around. If you don't want to look at every position, you can try skipping the pre-sorted intervals and sort the blocks rather than the individual elements. Notice this doesn't remove the circularity problem, it just reduces input size.

To be honest, looking at this problem gets me more tempted to show that as long as you have an answer with exactly one inversion, then you point of reference does not matter, than trying to show there is an optimal point to choose.

---
Tags: algorithms, sorting
---


# Question
Title: Complexity/Hardness of a generalization of an Inclusion/Exclusion problem
I would appreciate some help in determining the complexity/hardness of an inclusion/exclusion problem described in Wikipedia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion\_principle#A\_generalization

Namely, given a family of subsets $A\_1$, $A\_2$, ..., $A\_n$ of a universal set $S$, I need to calculate the number of elements of $S$ which appear in exactly some fixed $m$ of these sets.

Would that be #P?

Thank you.

# Answer
For each element in $S$, count the number of times it is a member of $A\_i$, $1\le i\le n$. If that number is $m$, we add 1 to the tally. The final tally is what we wanted.

The above algorithm takes $O(tn)$ time if the computational cost to check membership is $O(1)$. It takes $O(ttn)$ time if the computational cost to check membership proportional to the size of the set, which is at most $t$.

So you can see the problem is in $P$. It has nothing to do with that general inclusion–exclusion principle.
> 2 votes

---
Tags: complexity-theory, probability-theory
---


# Question
Title: How do we show $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$ in lambda calculus?
How do we show $$\lambda x . x (\lambda y .y) \equiv\_{\alpha} \lambda y.y (\lambda x . x)$$?

I was going through the slides here and it asked to do the above but by page 16 of the slides we have not defined what lambda applications are suppose to be. Thus is remained complete unclear because I don't know what the syntax:

$$\lambda x . x (\lambda y .y)$$

means. Can someone clarify to me how to proof this rigurously using alpha-conversion et al?

---

i.e. without using $\beta$ equivalence which is the application rule I assume.

# Answer
> 2 votes
The two terms are in the same $\alpha$-equivalence class. In lamba calculus, we can rename bound symbols without changing the meaning of the term. $\lambda x.x$ and $\lambda y.y$ both mean "a function that takes one input and returns it". A variable is bound by the first matching lambda above it in the term-tree.
We often $\alpha$-rename bound variables before $\beta$-reduction to make sure unbound variables do not get caputured after the reduction step.

---

To answer your question:

$$\lambda x . x (\lambda y .y) \equiv\_{\alpha} \lambda x.x (\lambda x'.x')$$ (rename bound $y$)
$$\equiv\_{\alpha} \lambda y.y (\lambda x'.x')$$ (rename bound $x$) $$\equiv\_{\alpha} \lambda y.y (\lambda x.x)$$ (rename bound $x'$)
This gives us $\lambda x . x (\lambda y .y) \equiv\_{\alpha} \lambda y.y (\lambda x.x)$

---
Tags: programming-languages, lambda-calculus, functional-programming
---


# Question
Title: Find all edges in a tree whose removal doesn't separate color classes
Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a *separator* if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use Farach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Also, for the reference, there’s $O(n \log n)$ approach to solve this task, which doesn’t seem to be optimizable. Let’s store in the vertice the count of all vertices of each color (now the edge is separator if in subtree there’re either no occurrences, or all occurrences of each color), but it’s a quadratic solution. Now we use small-to-large approach (merge these arrays to the one that belongs to the largest child, and pass the reference to that array to the parent), and it becomes $O(n \log n)$.

# Answer
## A useful lemma

First, root the tree arbitrarily if necessary, and orient all edges towards the root.

Denote by $b(v)$ the number of colours that appear at least once in the subtree rooted at $v$, and by $e(v)$ the number of colours that are completely contained in the subtree rooted at $v$. The following lemma is key to efficiently finding all separators:

**Lemma:** The edge from $v$ to its parent is a separator iff $b(v) = e(v)$.

**Proof sketch:** The direction "the edge from $v$ to its parent is a separator $\implies b(v) = e(v)$" is easy to see: some number $k$ of colours appear in their entirety in the subtree rooted at $v$, so it must be that $b(v) = e(v) = k$. The converse can be shown by induction on the number of colours in the entire tree, but intuitively, if we perform a series of steps, in each of which we insert a set of vertices of a fresh colour into the entire tree, then every step that adds a colour that is completely contained in the subtree rooted at $v$ increases both $b(v)$ and $e(v)$ by 1, every step that adds a colour that appears both inside and outside this subtree increases just $b(v)$ by 1, and there is no way to increase *just* $e(v)$, so it is impossible to recover the state $b(v) = e(v)$ while an incompletely contained colour remains in the subtree.

## Computing $b(\cdot)$ and $e(\cdot)$ using deltas

Define $b^+(v)$ to be the number of colours that appear at $v$ but nowhere else in the subtree below it. Clearly $b(v) = b^+(v) + \sum\_{u \in \\{u: (u,v)\in E\\}} b(u)$, which we can compute in a single bottom-up pass over $T$ if we can compute $b^+(v)$ for each vertex. Notice that $b^+(v)$ is either 1 or 0, since the only colour that can possibly contribute is the colour of $v$ itself.

Similarly define $e^+(v)$ to be the number of colours that are completely contained in the subtree rooted at $v$, but not in any proper subtree. Clearly $e(v) = e^+(v) + \sum\_{u \in \\{u: (u,v)\in E\\}} e(u)$. Notice that, unlike for $b^+(v)$, $e^+(v)$ can be larger than 1, since a vertex can be the LCA of multiple colours.

## Computing $b^+(\cdot)$ efficiently

Perform a bottom-up depth-first traversal, using an array $s$ of $N$ flags to keep track of whether or not a colour has been seen in any of the child subtrees. Specifically:

* Initially, set every element of $s$ to false.
* On entry to a vertex $v$ having colour $c(v)$:
    + Set $s\[c(v)\]$ to false.
    + Recurse to process all children.
    + If $s\[c(v)\]$ is still false, then colour $c(v)$ appears at $v$ but nowhere below it, so set $b^+(v) = 1$. Otherwise set $b^+(v) = 0$.
    + Set $s\[c(v)\]$ to true.

## Computing $e^+(\cdot)$ efficiently

Every colour $c$ for which $LCA(c) = v$ contributes 1 to the value of $e^+(v)$. Thus it suffices to calculate the LCA for each colour, and increase a counter at the corresponding vertex each time.

The total number of LCA computations is $O(N)$, since the colours partition the tree vertices, and the LCA of a set of vertices $\\{v\_1, v\_2, \dots\\}$ can be computed as $LCA(v\_1, LCA(v\_2, LCA(\dots)))$. Using Farach-Colton and Bender's LCA algorithm, after $O(N)$ preprocessing each LCA can be computed in constant time, for $O(N)$ computation of all $e^+(\cdot)$ values overall.

## Final pass

A final bottom-up pass computes $b(v)$ and $e(v)$ for each vertex $v$ from $b^+(v)$ and $e^+(v)$ and the values of $b(v)$ and $e(v)$ of child subtrees as outlined above. At each vertex $v$, test whether $b(v) = e(v)$, and if so output the edge leading from $v$ to its parent as a separator. This takes constant time per tree edge, so $O(N)$ overall, making the entire algorithm $O(N)$-time.
> 4 votes

---
Tags: algorithms, graphs
---


# Question
Title: Recursively edit 2-D array using backtracking
I have a 2-D array which contain 3 types of elements:

* **C (Contaminant)**
* **R (Rock)**
* **W (Water)**

The rule is that:

> **contaminant can seep through water but not through rocks.**

---

Let's say I have the following input array:

```
WWWRW
CRRRR
RWWRW
WWWRR
WRRWC

```

So the cells which have `'C'` as their value in the above array can contaminate in the same row and same column if water is present.

So the output would like something like this:

```
CCCRW
CRRRR
RWWRW
WWWRR
WRRCC

```

I know I have to solve this using via backtracking and recursion, but I am not able to come up with an apt algorithm to do so.

Any help will be hugely appreciated.

# Answer
> 1 votes
The following algorithm would be my first attempt.

1. Initialize a 2D array $A$ with given characters, 'C', 'W' or 'R'.
2. Loop $m+n-2$ times.
    * In each loop, iterate over all cells of $A$. For each cell, check whether it is 'C'. If yes, change all of it neighbors that are 'W' to 'C'. Otherwise, do nothing.

Here is an illustration of the step 2 on the example given in the question, where after 3 loops the situation will not change any more although we have specified 5+5-2=8 loops. Looping $m+n-2$ times guarantees that all contaminated elements will be found although the situation should become stable earlier in general. (In fact, the number of times needed is the longest Manhattan distance from a water cell that will be contaminated to the nearest cell that is contaminated initially.) $m+n-2$ is chosen here just for its simplicity.

```
WWWRW     CWWRW     CCWRW     CCCRW              CCCRW
CRRRR     CRRRR     CRRRR     CRRRR              CRRRR
RWWRW ->  RWWRW  -> RWWRW  -> RWWRW  -> (stable) RWWRW
WWWRR     WWWRR     WWWRR     WWWRR              WWWRR
WRRWC     WRRCC     WRRCC     WRRCC              WRRCC

```

Once the above simple and sound algorithm has been working well, we can consider a couple of improvements.

* Once we have checked a cell with value 'C', we will mark it as 'V' after we have changed its neighbors. In each loop, we will ignore cells with value 'V'.
* We can use a queue to list the cells to be checked. Cells that are changed to 'C' will be appended to the queue. Once the queue is empty, the algorithm stops.

---

> I know I have to solve this using via backtracking and recursion.

Not necessarily.

The technique used in the above algorithm is looping simply. Or nested loops to advance the frontier of contaminants. You can imagine the contaminants are spreading to their immediate neighbors uniformly by one tick of time. Ticks of time correspond to the outer loop while all contaminant correspond to the inner loop.

---
Tags: recursion, backtracking
---


title: Converting CFG from GNF to CNF

text:
# Question
Title: Converting CFG from GNF to CNF
I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is there an established way of carrying out such conversion?

# Answer
> 0 votes
You can just apply the usual procedure that converts any context-free grammar (CFG) to Chomsky normal form (CNF), since a CFG in Greibach normal form (GNF) is still a CFG.

In the case of GNF, the task is, in fact, easier. All you need is to apply the following two rules repeatedly, as described by Wikipedia, until there is no nonsolitary terminals nor more than 2 nonterminals on the right-hand sides of the production rules.

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


# Question
Title: Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops?
Say I have 3 simple tasks, to find the min, the max, and the average of an array of numbers.

A modular approach would be to write one function for each, thus iterating over the array thrice. However, that seems wasteful when all the information can be collected in a single iteration.

I understand that both approaches take `3n` time but am wondering if one approach is better than the other in the general case and why.

# Answer
> 1 votes
Collecting the information in a single iteration would be way better, but you'll only notice the difference if your array contains a large number of numbers. On a small scale, it just won't make a difference.

# Answer
> 0 votes
You can use a function to compute all of them. You can find in this post the implementation of `min` and `max` with each other using `3n/2 - 2` comparison instead of `2n`. Also, summing the values in the meanwhile of iterating over the whole of the data. It's the minimum number of iteration and comparison over data.

# Answer
> 0 votes
Usually you should do whatever code is more readable. If you need to find min, max, and sum or average, then having a single function that does exactly what it needs to do is the simplest and most readable approach. It's all in one place. If I need to check what the function does, I don't have to hunt around in different places. So usually, you should have one function.

If performance is more important than readability, then you should also have one function. You will read n array elements instead of 3n. You can determine min and max simultaneously with 1.5n comparison instead of 2n. On multi-issue CPUs where performance is limited by latency, you have 1x latency instead of 3x latency, so your code could be up to 3 times faster.

---
Tags: time-complexity, loops
---


# Question
Title: Minimum spanning tree such that one edge can be minimised
During a computer coding exam, I have encountered such a problem.

Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the vertexes such that the sum of the lengths of the edges is minimal, provided that you may subtract any one edge of your choice in the tree by the positive number D and reduce the weight of that edge to max(0, weight-D)?

I know that Kruskal's and Prim's algorithm can all be used to solve the first part of the problem, the minimum spanning tree, and I can do it. However, I have been struggling hard for the second part, as I don't know how to minimise the weight of the tree given the number D.

# Answer
> 2 votes
In the following, I assume the set of all feasible solutions is the set $\\{(T,uv):T$ is a not necessarily minimum spanning tree of $G$ and $uv$ is a distinguished edge in $T\\}$, with the cost of a particular solution $(T,uv)$ being the sum of the edges in $T$ minus $\min(D,w(uv))$.

Let $(T, uv)$ be an optimal solution to the problem you describe, having weight $\sum\_{xy \in E(T)} w(xy) - s$, where $s = \min(D, w(uv))$. There are two possibilities:

1. Every MST of $G$ contains at least one edge of weight $\ge s$.
2. At least one MST of $G$ contains no edge of weight $\ge s$.

## Case 1

For case 1, we can take any MST $T'$, find an edge in it with weight at least $s$ (since we know by assumption that this exists), and produce a solution having weight at most $\sum\_{xy \in E(T')} w(xy) - s$. This is at most the weight $\sum\_{xy \in E(T)} w(xy) - s$ of the optimal solution $(T, uv)$, since $\sum\_{xy \in E(T')} w(xy) \le \sum\_{ab \in E(T)} w(ab)$ for any tree $T$ by definition of the MST. That means that for case 1, we can never miss an optimal solution by considering only MSTs.

## Case 2

For case 2, consider the edge $uv$ in $T$, which has weight at least $s$. Let the vertices on one side of this edge be $A$, and the vertices on the other side $B$. By assumption, there exists an MST in which every edge has weight strictly less than $s$. In particular, this MST must contain an edge $u'v'$ between the vertex sets $A$ and $B$ having weight strictly less than $s$, since otherwise the MST would be disconnected -- a contradiction.

Suppose $w(uv) \> D$. Then the original solution $(T, uv)$ has weight $X - D$, with $X$ being the weight of the entire tree $T$, while the solution formed by replacing $uv$ with $u'v'$ has weight $X - w(uv) \< X - D$. This contradicts optimality of $(T, uv)$, so it must be that in fact $w(uv) \le D$, in which case both the original and new solutions have weight $X - w(uv)$. Thus the new solution has weight equal to the old solution, but now falls into case 1 above.

## Wrapping up

Since there are only two possible cases for an optimal solution, and in both cases an MST can always be found that leads to a solution that is just as good, it always suffices to find an MST.

The final step is to choose an edge in the MST to minimise. Clearly it is always optimal to choose the heaviest edge in the MST.

# Answer
> 0 votes
We have the following lemma.

**Minimality of all weights of a minimum spanning tree (MST).** Let $G$ be a weighted graph with $n$ vertices. $T$ is a minimum spanning tree of $G$ with edge weights $$w\_1 \le w\_2 \le ... \le w\_{n-1}.$$ $T'$ is a spanning tree of $G$ with edge weights: $$w'\_1 \le w'\_2 \le ... \le w'\_{n-1}.$$ Then $w\_i \le w'\_i$ for all $i$.

For a proof, you can check my answer to the question *Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?*.

---

The solution to your problem is simple.

1. Find $T$, an MST by Kruskal's or Prim's algorithm.
2. Subtract $D$ from the heaviest edge of $T$ unless it weigh less than $D$, in which case change its weight to 0.
3. Return the total weight of $T$.

---

Proof of the correctness of the algorithm.

Consider the function $s$, $s(w)=w-D$ if $w\ge D$ and $s(w)=0$ otherwise. Then $s(w)$ is a nondecreasing function. In particular, $s(w\_{n-1})\le s(w\_{n-1}')$.

---

Note, the above answer works regardless in which way we can interpret "what is the minimum spanning tree between the vertices such that the sum of the lengths of the edges is minimal, provided that you may subtract any one edge of your choice in the tree," as discussed in the comment below that happened before this minor update of this answer, where the algorithm stays the same.

---
Tags: graphs, greedy-algorithms, minimum-spanning-tree, prims-algorithm
---


# Question
Title: Minimum Spanning Tree with one particular edge minimised(continued)
I have recently encountered a coding problem, specifically, the CCC problem S4.

In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each and every home to one another. However, the tree is not the minimum spanning tree. You may use an enhancer, in exact words, with power D, to reduce the weight of one edge to what is **max(0,weight-D)**. You have a number of days to make the given spanning tree a minimum spanning tree. During these days, you may deactivate any edge of the given spanning tree, and activate another edge of your choice. It does not matter if the tree is not a spanning tree in the process, however, at the end, it should be. You also want to minimize the amount of days you need to do this.

I have been struggling with the problem for a long time, and I cannot find any solution. I am able to find the minimum spanning tree, but I am struggling with the implementation of the enhancer.

I would appreciate any help to my problem, and sample codes will be even better.

I asked a similar question here as well: Minimum spanning tree such that one edge can be minimised

# Answer
> 1 votes
Run Kruskal's algorithm on the weighted graphs of all buildings as vertices and all pipes with original costs as edges with weights, with the following modification. When we are going to select the next edge (pipe) whose weight (cost) is minimum among the available edges, we choose one among the active pipes first if there is such a pipe.

At end of the algorithm, we obtain a minimum spanning tree $T$ with weights $w\_1\le\cdots w\_{N-2}\le w\_{N-1}=m$. The number of days needed to implement $T$ as the new active pipes, denoted $p$, is the number of pipes in $T$ that are not currently active.

With the enhancer used, the total minimal cost becomes $w\_1+w\_2+\cdots+w\_{N-2}+s(w\_{N-1})$, where $s$ is the function such that $s(w)=0$ for $w\le D$ and $s(w)=w-D$ otherwise. That formula is shown in the linked question and its answers.

Can we reduce the number of days from $p$ to $p-1$?

**Claim 1.** If $D\le m$, then the number of days cannot be reduced to $p-1$.

The proof of claim is left to readers as a (not immediate) exercise.

So let us run Kruskal's algorithm again from scratch, with a further modification. Immediately after we have tried selecting all pipes of cost $m$ that were active (there might be none of them), we will continue to try selecting all pipes that cost more than $m$ but no more than $D$ one by one. If it is successful at least once, that is, if such a pipe will connect two disconnected components, then we will include it in the plan and we will reduce the required days by one to $p-1$. Otherwise, the required days is $p$.

---
Tags: graphs, greedy-algorithms, minimum-spanning-tree, prims-algorithm
---


# Question
Title: Small space hash functions that are weakly but not strongly universal
This is a follow up to this this question about weakly universal hash functions

A family of hash functions $H\_w$ is said to be *weakly universal* if for all $x \ne y$ :

$$P\_{h \in H\_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow \[m\]$ is chosen uniformly from the family $H$ and we assume $|U| \> m$.

A family of hash functions $H\_s$ is said to be *strongly universal* if for all $x \ne y$ and $k, \ell \in \[m\]$:

$$P\_{h \in H\_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

I previously asked for an example of a hash function family which is weakly universal but not strongly universal. The very nice answer was:

> Take $U = \[m+1\]$, and consider the functions $h\_i$, for $i \in \[m\]$, given by $$ h\_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \> \text{if } x = m+1. \end{cases} $$ The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.

For arbitrary $|U|$, it seems that in order to represent a single hash function in practice you would need to store a lookup table of size $|U|$ to ensure that the hashed values are independent and truly random. Then for every key, you would look up its random value in the vast lookup table to compute the hash function.

Is there a hash function family where the hash functions require constant or log space that achieves the same result of being weakly but not strongly universal? In other words, are there any practical hash function families that are weakly not but strongly universal?

# Answer
Let $H$ be a family of strongly universal hash functions from $U$ to $\[m\]$. Construct a new family of hash functions from $U \cup \\{x\\} \to \[m\]$ by extending all functions $h \in H$ with $h(x) = 1$. The family is weakly universal since $h(u)$ is distributed uniformly for every $u \in U$, but it is clearly not strongly universal.
> 3 votes

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


# Question
Title: Is this problem hard? Finding all the subsets of size k from a sequence of n numbers
I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of size n.

However, I am not sure whether this can be done in polynomial time or not.

# Answer
> 3 votes
For fixed $k$, the running time is polynomial, but if $k$ is part of the input, the running time is not polynomial. The number of such subsets is ${n \choose k}$, which is very roughly like $n^k$. Thus, if $k$ is fixed to something like 3, this becomes $O(n^3)$ -- polynomial. However, if $k$ is part of the input, the running time is exponential in $k$.

---
Tags: algorithms, time-complexity, np-hard
---


title: Mildly context-sensitive grammar

text:
# Question
Title: Mildly context-sensitive grammar
Consider a context-sensitive grammar $G$, such that all the productions of $G$ have the form $A\to \alpha$ or $Ab \to \alpha b$ (in other words, the left context is always empty and the right context is either empty or consists of just one terminal).

Is the language defined by such a grammar necessarily context-free ?

In all the toy examples I considered, the original context-sensitive grammar can be enlarged into an equivalent context-free one.

# Answer
> 4 votes
You could have written a paper based on your discovery had you been researching this problem many years ago.

In fact, the paper *Terminal Context in Context-Sensitive Grammars* by Ronald V. Book, 1972 mentioned by Yuval proved the following theorem, edited slightly for the sake of current question.

> Theorem 2. If $G$ is a context-sensitive grammar with terminals $\Sigma$, non-terminals $N$ such that every non-context-free rule is of the form $\alpha Z\beta \to \alpha\gamma \beta$ where $\alpha\in\Sigma^\*$, $\beta\in\Sigma^\*$ and $Z\in N$, then $L(G)$ is context-free.

The grammar in the question is the special case of the grammar in the theorem above where $\alpha$ is the empty string and $\beta$ is either the empty string or a terminal.

Check that paper for a proof of the theorem as well as more insight on how to force context-sensitive grammars to be context-free. (You can probably publish a paper if you could solve the conjecture at the end of that paper.)

---

Here is one exercise that is within easy reach.

**Exercise 1.** If $G$ is a context-free grammar except one rule, which is of form $Aa\to Ba$, where $a$ is a terminal and $A$ and $B$ are two non-terminals, then $L(G)$ is context-free.

---
Tags: context-free, context-sensitive
---


# Question
Title: partial (and non deterministic) functions in dependently typed lambda calculus
A partial function is one, that that is only defined on a part of its domain. Haskell gives examples: https://wiki.haskell.org/Partial\_functions

My end goal is to express types

$$ \prod\_{D:\mathcal{U}} D \qquad\qquad\qquad\qquad \prod\_{\mathcal{A}:\mathfrak{A}} \mathcal{L}(\mathcal{A}) $$

* The first type should simply represent sort of (polymorphic) choice functions which accecpt a type and return an element of that Type.
* The second is assuming, that I can express the Type of Automata $\mathfrak{A}$ as well as the language $\mathcal{L}(\mathcal{A})$ accepted by automaton $\mathcal{A}$. Given an Automaton a function with the given pitype should Select a word accepted by it.

As far as I understand, in a basic dependently typed lambda calculus, both types suffer from the same problem: Their elements can never be introduced. Neither is it possible to select an element from the type $\bot$ nor select a word accepted by an automaton that doesn't accept any words.

I was wondering, if partial functions may be a solution to that problem. But how are partial functions are represented in a typed lambda calculus? An easy way I can imagine would be to be to create expressions, that allow the introduction of partial functions, such that there simply are no computation rules for undefined inputs.

So my questions are:

* Does that make any sence, and is it common to solve this kind of problem that way? Is there good literature?
* If the approach seems legit, is it possible to distinguish partial function types $A \rightharpoonup B$ from regular ones $A \to B$?

Note on the purpose: To be honest, I haven't formalized automata in any calculus, since for now I mostly would like to steal the concept and notation of dependent types and use them in my work to get across a concept. But if what i will do isn't completely bogus, it would maybe at least leave open a possibility to formalize things later.

A choice function of type $\prod\_{D:\mathcal{U}} D$ is meant to represent user input - which should be non deterministic .. so there would also be no congruence)

* *Bonus question*: Can non-deterministic functions be represented in a calculus such that this may be expressed?

# Answer
> 3 votes
It is possible to take a typed lambda calculus and add general recursion or fixed points. See for instance Plotkin's PCF, or HOFL in Winskel's formal semantics book.

In that way, one keeps the type system but introduces partiality. This is a very common approach for Turing complete typed programming languages.

Of course, now the logic associated to the calculus via Curry-Howard is no longer consistent, since every type is inhabited (by non terminating terms). This is not a serious problem for programming.

If wanted, in the type system one could distinguish between terms involving general recursion (which might not terminate), and terms involving no recursion or some known-to-be-terminating one, like (higher-order) primitive recursion. Note that this will not separate the programs between "halting" and "non-halting", which is undecidable, but only between "statically known to halt" and "statically unknown to halt -- they might or might not".

I have not thought much about that, but intuitively a non-termination monad would fit nicely in such type system. With a non-deterministic monad, one can also address non-deterministic functions.

A final comment: after reading the question, I am actually more concerned about the posted automaton-based example than termination. With dependent types, one can use the $\Pi$-type of a selection function (as the one which was posted), which given an automaton return one of the accepted strings (or a "empty-language" token). However, let's keep in mind that when a dependent type system checks a term against such $\Pi$-type, the term must contain the recipe to generate the string, as well as *a proof* that such string is accepted by the automaton. The posted question, in my view, seems to forget about that -- as if the type system could check any algorithm correct (in the sense of returning an accepted string). This is not possible.

# Answer
> 0 votes
There is nothing that prevents dependent types from declaring:

$$T: a \rightarrow a \rightarrow bool$$

If you can then prove, or if you assume:

$$\forall x,y,z(T(x,y) \wedge T(x,z)\Rightarrow y=z)$$

You then know that $T$ is a partial function. You can then use a maybe type and define:

$$T(x,y) \Rightarrow t(x) = \mathbb{just}(y)$$

$$\neg \exists y T(x,y) \Rightarrow t(x) = \mathbb{nothing}$$

Which gives you a function of signature:

$$t:a \rightarrow \mathbb{maybe}\\,a$$

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


# Question
Title: Recognizer to check if the language of a Turing machine contains a finite subset
Let $B = \\{ 123 \\}$.

Note that $B$ is finite.

Let $L = \left \\{ \left\langle M \right\rangle | M \text{ is a Turing machine such that } B \subseteq L(M) \right\\}$.

Is it sufficient to show that $L$ is recognizable by checking if $M$ accepts on input $123$, and therefore $\left\langle M \right\rangle \in L$?

# Answer
Yes, it is sufficient.

$\langle M \rangle \in L \Longleftrightarrow B\subseteq L(M) \Longleftrightarrow M\text{ accepts all strings in }B \Longleftrightarrow M\text{ accepts }123$.
> 1 votes

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


# Question
Title: Let u and v be two strings. What about the reverse order of their concatenaited string?
let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?

**Note:** The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.

# Answer
> 2 votes
No, $(u\cdot v)^R\not=u^R\cdot v^R$ more often than not.

For example, if $u$ is the string $race$ and $v$ is the string $car$. Then $$(u\cdot v)^R=(racecar)^R=racecar$$ while $$u^R\cdot v^R=(race)^R(car)^R=ecarrac.$$

---

Here are a few related exercises. All variables stand for strings.

**Exercise 1**. If $u$ or $v$ is the empty word, then $(u\cdot v)^R=u^R\cdot v^R$.

**Exercise 2**. If $u$ or $v$ are words of length 1 such that $(u\cdot v)^R=u^R\cdot v^R$. Then $u=v$.

**Exercise 3**. If $u=u^R$ and $v=v^R$, can we guarantee $(u\cdot v)^R=u^R\cdot v^R$?

**Exercise 4**. Prove that $(u\cdot v)^R=v^R\cdot u^R$.

---
Tags: formal-languages, regular-languages, strings
---


# Question
Title: Appreciation of the 5 state process model
I'm starting out in an Operating Systems module. I have a few understanding questions to think about, which will not be gone through in class.

A process state model is an abstraction (or model) which is used to explain what can happen to a process. Give a state of the process, it tells you what is the next allowed states and what causes the process to be in that state, and so on. A model is only at a certain level of abstraction. In this question, we will be focusing on the 5-state process model from the lecture.

(a) Is it possible for a process to never go to Terminated state. If so, give 3 possible scenarios when this can occur. If not, explain your reasoning.

(b) Suppose a process is in terminated state. Discuss whether you should be able to check at any time if a process is in terminated state at all times. Are there any implications?

**5 state process model**

I have attempted to answer all these questions, but because of their theoretical nature, I think there might be a lot more dimensions to these.

a) I think it is not possible for a process to never go to termination, given enough time, because there are multiple ways a kill() or exit() command can be called, depending on their policy and mechanism in the operating system?

b)

I think it is important because a process in termination state still holds some data and requires the OS to do some cleanup. A process might not be running for other reasons other than termination, it could be in a blocked state without any IO activity or just be inside the ready state.

> Can someone check my understanding on these questions? Thanks.

# Answer
> 2 votes
a) A process does not necessarily have to terminate, it only reaches the terminated state if it `exit`s voluntarily. If a process has no exit statement (e.g. a server), it would never reach the terminated state unless killed by the OS. Other ways for a process to never reach termination include not being scheduled when ready because some other process with higher priority is always scheduled before it (starvation), or being stuck in the blocked state waiting for some resource but never getting it, for example, trying to obtain a lock (deadlock/livelock).

b) If we cannot check wether the process has reached the terminated state or not, we can never free up its resources (stack, data, process table entry). It is important for the OS to be able to tell what state a process is in for the scheduler to work properly. If a child process terminates and reaches the 'Z' state, the operating system needs to have this information when it tries to pick a process to schedule. This prevents processes that no longer need CPU time from being scheduled. If the OS did not have this state information available at all times, the implications would be wasting memory space and CPU time.

I suggest reading up on the wiki for the `exit`, `wait` and `fork` syscalls for better understanding :)

---
Tags: terminology, operating-systems, process-scheduling
---


# Question
Title: Proof of correctness of algorithms (induction)
I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and proving their formulas I can do it, I have no problem understanding why it is correct. When I get a loop on the other hand, I cannot even get started. I have a hard time combining the Loop invariant (also finding it) and the proof.

For example the following is a complete mystery (i tried reading a few similar questions on SO, but I still don't get it)

```
function multiply(y, z)
    if z = 0 then return(0) else
    return(multiply(cy, ⌊z/c⌋) + y · (z mod c))

```

I understand that I am asking a lot, but is it possible for someone to try to explain it step by step ? I am learning the book on my own, this is not a homework and I am not trying to cheat on anything, I just do not understand it.

# Answer
> 3 votes
> how do I include the `if else` statement in the proof?

In this example, the `if` statement describes the basic case and the `else` statement describes the inductive step.

Induction on $z$.

*Basis:* $z = 0$.

$$ \text{multiply}(y,z) = 0 = y \times 0. $$

*Induction Hypothesis:* Suppose that this algorithm is true when $0 \< z \< k$. Note that we use strong induction (wiki).

*Inductive Step:* $z = k$.

\begin{align} \forall c\>0 : \text{multiply}(y,z) &= \text{multiply}(cy, \lfloor \frac{z}{c} \rfloor) + y \cdot (z \text{ mod } c) \\ &= cy\cdot\left\lfloor \frac{z} {c}\right\rfloor+y\cdot (z \text{ mod } c) \\ &= yz. \end{align}

# Answer
> 2 votes
Expanding on hengxin's succinct answer, this is my understanding of how each step is achieved.

We do the inductive step on $z = k$. This means that in the first invocation of $multiply(y, z)$, $z$ is in fact $k$.

$ \text{multiply}(y,z) = \text{multiply}(cy, \lfloor \frac{z}{c} \rfloor) + y \cdot (z \text{ mod } c) $

The first term is $multiply(cy, \lfloor \frac{z}{c} \rfloor)$, in which $\lfloor \frac{z}{c} \rfloor$ is really $\lfloor \frac{k}{c} \rfloor$, and $\frac{k}{c} \< k$. From our inductive assumption that $multiply(y, z) = yz$ for all $0 \< z \< k$ therefor follows that we can assume that $multiply(cy, \lfloor \frac{z}{c} \rfloor) = cy \cdot \lfloor \frac{z}{c} \rfloor$, and so we get:

$ = cy\cdot\left\lfloor \frac{z} {c}\right\rfloor+y\cdot (z \text{ mod } c) $

We can now break out $y$ from the terms:

$ =y \cdot \left(c\cdot\left\lfloor \frac{z} {c}\right\rfloor+ (z \text{ mod } c)\right) $

Lastly, because $c\cdot\left\lfloor \frac{z} {c}\right\rfloor$ removes the remainder of $\frac{z}{c}$ from $z$ and $z \text{ mod } c$ adds it back again, the expression in the parens can be re-written as $\left(c\cdot\left\lfloor \frac{z} {c}\right\rfloor+ (z \text{ mod } c)\right) = z$, which means we get:

$ =yz $

---
Tags: algorithms, correctness-proof, induction, loop-invariants
---


# Question
Title: How does treewidth behave under graph minor operations?
It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq\_m G$), the treewidth of H is smaller than or equal to that of G.

Minors of a graph are created through the operations of (1) vertex deletion, (2) edge deletion and (3) edge contraction. I am curious as to whether one can bound the decrease in treewidth when applying any single operation from (1)-(3). Of particular interest for me is the question whether said decrease can always be bounded by some constant.

# Answer
The decrease in tree width of any of the three operations will be 0 or 1. The proof is simple (I will take the case of the vertex deletion).

Let $G$ be the original graph and $G' = G - v$ be the graph obtained by deleting $v$.

Let $T'$ be an optimal tree decomposition of $G'$, with $\text{tw}(G') = w'$.

Now, construct $T$ from $T'$ by adding $v$ to every bag of $T'$. Clearly, $T$ is a tree decomposition for $G$ with width $\text{tw}(G) \leq \text{tw}(T) = 1 + \text{tw}(G') = 1 + w'$.
> 4 votes

---
Tags: graphs, discrete-mathematics, treewidth
---


# Question
Title: Proof of QuickSort algorithm correctness
Recently I’ve studied QuickSort and understood its general idea.

Basically, we do the following:

1. Pick an element from the array (no matter which one and how in this context)
2. Rearrange elements in the array so that elements less than the pivot are placed prior to it (in the left part of the array), and ones that are greater than the pivot are placed after it (in the right part).
3. Apply these procedures to the left and right parts of the array.

Everything looks quite clear, but my question is: **why** does it eventually sorts the entire array?

I’ve read lots of articles about the QuickSort, but none of them provides a clear *proof that algorithm does really work in a way they describe*. So I’m looking for such a proof.

I realize that:

* Array of one element (i.e with length 1) is already sorted.
* After any partition the pivot is placed on it’s final position.

So what’s the proof of the fact that after applying QuickSort procedure to a given array of length N its elements will be ordered after a procedure completes?

P.S. I’ve seen several proofs based on mathematical induction. Unfortunately, I’m not familiar with it yet, so I’m primarily looking for non-induction proof.

Here they are:

# Answer
> 1 votes
First, you need to write down your algorithm that you call "Quicksort" precisely. The devil is in the detail, and if your code doesn't get the details right, then it won't sort correctly (or you won't be able to prove that it sorts).

And then you need to use complete induction: Take the induction statement S(N) "My algorithm will sort any subarray with n ≤ N items correctly". The more obvious statement S'(N) "My algorithm will sort any subarray with N items correctly" isn't strong enough.

Next you prove S(1): If the array has 0 or 1 elements, does your algorithm sort it correctly? Most implementations will check that there are two or more elements as their very first step, and subarrays with 0 or 1 elements are sorted, so this should be no problem.

Then you need to prove that S(N) implies S(N+1). If S(N) is true, then any subarray of size n ≤ N will be sorted correctly, so only the case of an array with N+1 elements needs to be handled. Here you have to prove that one Quicksort step will divide an array of N+1 into two subarrays of size ≤ N, with each element of the left subarray \<= each element of the right subarray, and no overlap.

PS You will always end up with an induction proof, more or less disguised. For example: Assume there is an array that doesn’t get sorted correctly by Quicksort. If there is *any* array, then there must be a smallest array that doesn’t get sorted. Take that array, pick the pivot and create two sub arrays, a left one and a right one. Sort both sub arrays with Quicksort. Since they are both smaller than the smallest array that isn’t sorted correctly, they will be sorted correctly. So Quicksort works.

That’s a property of the integers: if a set of positive integers is not empty, then it has a smallest element. Take the set of all sizes of arrays that are not correctly sorted by Quicksort. If that set is not empty, then it has a smallest element, and therefore there is a smallest array that cannot be sorted. And then you prove that the smallest array that cannot be sorted can indeed be sorted, so your assumption that some array cannot be sorted was wrong.

# Answer
> 0 votes
I'm not sure you actually need induction (in the sense that we try to prove $P(n+1)$ assuming $P(n)$) for the quicksort proof.

Let $(a\_i)\_{0 \leq i \leq n}$ be your initial array. Let $(a\_{q(i)})\_{0 \leq i \leq n}$ be the sorted array.

In order to prove that quicksort correctly sorted the array, we have to prove that for every pair of elements $a\_i$, $a\_j$ such that $a\_i \< a\_j$, we have $q(i) \< q(j)$.

For that, you need to show that:

1. If $a\_i \< a\_j$, $a\_i$ and $a\_j$ will eventually find themselves on different sides of a pivot (with $a\_i$ to the left and $a\_j$ to the right).
2. Once two elements are on different sides of a pivot, their respective order stays the same until the end of the algorithm.

---
Tags: algorithms, sorting, correctness-proof, induction, quicksort
---


# Question
Title: A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))
Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\mathbf{CFL}$ (context-free languages). And also the open problem $\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$ is not so famous as the "analogous" problem: "$\mathbf{P} =^{?} \mathbf{NP}$".

Well, is there really such an analogy:?

1. Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE(O(n))}$ (like $\mathbf{NP}$ complete languages)?
2. Moreover: Is there a language $L$ in $\mathbf{CSL}$ which is "complete" in the following sense: if we can prove that $L$ is in $\mathbf{DSPACE(O(n))}$ we get that $\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$?
3. (Maybe just a matter of opinion) Are both problems on the same level of difficulty?

# Answer
> 8 votes
The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$, and so $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ implies the well-known conjecture $\mathsf{L} \neq \mathsf{NL}$.

The conjecture $\mathsf{L} \neq \mathsf{NL}$ is considered (by some) to be more approachable than the conjecture $\mathsf{P} \neq \mathsf{NP}$. I'm not sure many people have an opinion on the conjecture $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$.

The bigger picture here is whether Savitch's theorem, which states that $\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$ for reasonable $t(n) \geq \log n$, is tight. While $\mathsf{NPSPACE} = \mathsf{PSPACE}$, I think that most people believe that $\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$. On the other hand, I'm not sure that people believe that $t(n)^2$ is the optimal blowup; perhaps a smaller exponent also works, at least in some cases. See for example a recent arXiv paper, *The parameterized space complexity of model-checking bounded variable first-order logic*, by Yijia Chen, Michael Elberfeld, and Moritz Müller.

# Answer
> 1 votes
1. Yes, there are **CSL** complete languages under **DSPACE(O(n))** reductions. Basically still a variant of directed reachability, which can be restricted to acyclic reachability if desired.
2. Yes, see 1.
3. You mean, is the question **DSPACE(O(n))=?NSPACE(O(n))** on the same level of difficulty as the question **P=?NP**? Well, we have good reasons to believe that **P** is a strict subset of **NP**, but I am not aware of similarly well worked out reasons to believe that **DSPACE(O(n))** is a strict subset of **NSPACE(O(n))**. Let me focus on the easier question $\mathsf{L} \stackrel?= \mathsf{NL}$. Random walks are "not bad" for exploring (with respect to reachability) the undirected graphs associated with **SL**. The obvious trivial analogous random walk on a directed graph will fail badly at exploring a directed graph (with respect to reachability). But maybe there are other similar randomized ways to explore a directed graph (or a layered acyclic graph). Based on Savitch's theorem, I would even guess that there are such ways, if we are willing to save a changing set of $O(\log n)$ positions within the directed graph during the random exploration process. And then the challenge would be to understand whether saving fewer than $O(\log n)$ positions won't allow good randomized exploration.

Even after understanding whether we should believe $\mathsf{L} \neq \mathsf{NL}$, proving it will likely be just as impossible as proving $\mathsf{P} \neq \mathsf{NP}$. Ryan Williams gives one explicit reason and says:

> Beyond that, I know of no particular reason to believe it is "hard to prove" other than the observation that many people have tried and none have succeeded yet.

to answer Is ALogTime != PH hard to prove (and unknown)? Lance Fortnow basically brought up the question and still disagrees. My own lesson was:

> This means that the statement "ALogTime != PH" is exactly the place where the difficulties for proving separation results start. It may be noted that this statement is actually equivalent to "ALogTime != NP", since "ALogTime = NP" would imply "P=NP=PH".

# Answer
> 1 votes
Adding to the other answers, there is a notion of reducibility and completeness for the CSL vs. DCSL problem, namely log-lin reducibility, and there are quite natural CSL-complete problems. For example, the inequivalence problem for regular expressions. Here is a very similar question to yours, together with an answer providing further background and references: https://cstheory.stackexchange.com/questions/1905/completeness-and-context-sensitive-languages

# Answer
> -1 votes
$SAT$ is in $NTIME(n) \subseteq DSPACE(n)$. Under the assumption of $L = P$, then $NP$ is strictly contained in $DSPACE(n)$ since we can transform polynomial time reductions into logarithmic space reductions and $DSPACE(n)$ is closed under logarithmic space reductions. They are not equal due to the Hierarchy Theorem. However, when $L = NL$ then $DSPACE(n) = NSPACE(n)$ as result of applying the padding argument. Since $L = NL$ when $L = P$ then $NP$ is strictly contained in $NSPACE(n)$. However, $CSL = NSPACE(n)$ and thus $CSL \neq NP$ and hence, there could not be the case that some $CSL-complete$ problem is in $NP$ because that would imply a contradiction with $CSL \neq NP$ that we obtained after assuming $L = P$.

In addition, you could see a possible attempt of proving $L = P$ here:

https://hal.archives-ouvertes.fr/hal-01999029

---
Tags: complexity-theory, np-complete, space-complexity, context-sensitive
---


# Question
Title: An algorithm to drop low-priority items from a heap-based priority queue
I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap all items whose priority is too low.)

It is easy to make an algorithm that walks the heap level by level from bottom up, comparing the item weights to the threshold value and doing dropping-and-swapping. It will turn out to be extremely inefficient though if, for example, all items in the heap need to be dropped.

It looks better to start by finding an item at the bottom level that is heavier than the threshold value and walk upwards from it until finding the highest element that needs to be dropped. Then the whole sub-heap under that element needs to be dropped. The space taken up by this sub-heap can be filled with elements moved from one or two bottom levels that are not in this sub-heap, and the sub-heap can be rebuilt. However, this method does not look perfect either, as most likely the dropped sub-heap will be filled with elements some of which need to be dropped too.

Are there any efficient or well-studied algorithms for this?

# Answer
> 2 votes
Let $n$ denote the size of the min-heap. It's easy to do this in linear time, i.e., $O(n)$ time: walk through the heap, copying over only the items that are below the threshold into an array; then call MakeHeap to turn it into a heap.

I would be surprised if you can do better than this, in asymptotic worst-case running time. For instance, any approach that involves scanning all items at the bottom layer will necessarily take at least linear time, i.e., at least $\Omega(n)$ time. And if there is any item in the bottom layer that you don't examine, then in at least some cases you won't be able to tell whether it needs to be included or not. So I suspect it may be possible to construct an adversarial argument that shows that at least $\Omega(n)$ time is needed -- though I don't know for sure.

Alternatively, one could consider the running time as a function of the output size. Let $m$ denote the size of the output, i.e., the number of elements that are above the threshold. Then it is easy to achieve $O(m)$ running time, by doing a top-down recursive pre-order traversal of the min-heap (think of it as a binary tree), truncating the traversal at each internal node that is above the threshold. The running time is $O(m)$ since you only visit a node if it is included in the output or if it is an immediate descendant of a node included in the output; since each node has at most 2 descendants, this means that the number of nodes visited is at most $3m$, i.e., $O(m)$. This is clearly optimal, as a function of output size: any algorithm that produces $m$ outputs has to take at least $\Omega(m)$ time, just to write out the output.

---
Tags: algorithms, data-structures, heaps, priority-queues, comparison
---


# Question
Title: Byzantine generals problem with signed messages (Lamport)
I have some trouble understanding Lamport's paper about the Byzantine generals problem when it comes to signed messages. He showed that, with signed messages, the number of generals must be at least $m+2$ to tolerate $m$ malicious units\faults (for fewer generals, the problem is vacuous).If that's fulfilled it's guaranteed that the loyal generals make the same decision.

Now, I read a lot of papers where at least $2m+1$ generals are needed. The argument in these papers is that the loyal generals have to outnumber the malicious ones to make a majority vote (to get not only the same but the right result). But why isn't it sufficient to have $n \ge m+3$ with three loyal generals for majority vote?

Moreover, if $2m+1$ generals are needed for the majority vote, how can that work with three generals and one traitor? In both cases I need $m+2=3$ and $2m+1=3$ generals and (from what I understand) then I can only agree on the same but not on the correct value (majority vote with two loyal entities?).

I know that I have an error of reasoning here, but I really don't get it. Maybe someone can help me with that problem?

# Answer
Maybe this is what confuses you -- mixing the byzantine *agreement* problem (broadcast: where there is one transmitter and multiple receivers) and the byzantine *consensus* (where every party starts with an input, and if all have the same input, this should also be their output). The bound of at most half traitors stems from the consensus requirement.

Say we have $n$ generals, out of which $t$ are traitors and $\ell=n-t$ are loyal. Assume general $i$ holds the input bit $b\_i$

Now assume they all perform a distributed majority vote protocol. *Is the protocol guaranteed to succeed?* This questions is actually not a well defined. The success of the protocol can be interpreted in two different ways:

1. All loyal generals output the same answer: $MAJ ( b\_1, \ldots, b\_n)$
2. All loyal generals output the same answer: $MAJ (L)$ where $L=\\{b\_i \mid $ general $i$ is loyal$\\}$.

Note that using Lamport's result you mentioned, if $n\>t+2$ then all the loyal parties are guaranteed to output the same output even if the traitors misbehave and don't follow the protocol, but which output do they output? Assume $\ell=3$ as you suggest, and assume they all hold the input $0$. The "traitors" can still force the loyal generals to output "1": they just set their input to $1$ and *behave honestly*! Remember that the loyal parties don't know who is loyal and who isn't (or even if there are traitors at all -- maybe everyone is loyal). From their point of view, there are $t$ votes for "1" and only 3 votes for "0", and since everybody behaves as supposed by the protocol -- the output must be 1! This suits interpretation number (1) above.

Thus, interpretation number (2) above makes sense only for the case where setting the input of the traitors does not affect the majority. A special case is the *consensus* problem: if all the $\ell$ parties hold (say) "0", we want to guarantee that they all outputs a 0. Of course, if $t\>\ell$ then the simple "attack" described above will work. So we need $t\<\ell$, or equivalently, $$n=t+\ell \ge t+(t+1)=2t+1.$$

In the most general case of byzantine major-vote, the loyal parties may be split (e.g., $\lfloor \ell/2\rfloor$ votes vs. $\lceil \ell/2\rceil$ votes). In this case, even a single traitor (playing honestly) can determine the result by himself.
> 2 votes

# Answer
According to the paper  Generally speaking, Byzantine consensus considers the problem of reaching agreement among a group of n parties, among which up to f can have Byzantine faults and perform arbitrarily. There exist a few variant formulations for the Byzantine consensus problem. Two theoretical formulations are "Byzantine broadcast" and "Byzantine consensus". In Byzantine broadcast, there is a designated sender who tries to broadcast a value. In Byzantine agreement, every party holds an initial input value.
> 1 votes

---
Tags: distributed-systems, communication-protocols, fault-tolerance
---


# Question
Title: k-center algorithm in one-dimensional space
I'm aware of the general k-center approximation algorithm, but my professor (**this is a question from a CS class**) says that in a one-dimensional space, the problem can be solved (optimal solution found, not an approximation) in `O(n^2)` polynomial time without depending on `k` or using dynamic programming.

A general description of the k-center problem: Given a set of nodes in an n-dimensional space, cluster them into `k` clusters such that the "radius" of each cluster (distance from furthest node to its center node) is minimized. A more formal and detailed description can be found at http://en.wikipedia.org/wiki/Metric\_k-center

As you might expect, I can't figure out how this is possible. The part currently causing me problems is how the runtime can not rely on `k`.

The nature of the problem causes me to try to step through the nodes on a sort of number line and try to find points to put boundaries, marking off the edges of each cluster that way. But this would require a runtime based on `k`.

The `O(n^2)` runtime though makes me think it might involve filling out an `nxn` array with the distance between two nodes in each entry.

Any explanation on how this is works or tips on how to figure it out would be very helpful.

# Answer
First,

> There exist optimal solutions in which each cluster consists of a contiguous sequence of points in the real line.

Any other optimal solutions can be transformed into the cases above. In the following, we focus on the optimal solutions of the kind above.

---

The complexity of the following "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.

The case for $k=1$ is easy. Denote the optimal solution to $k=1$ in $n$ points by $R\_{n,1}$.

Let $R(n,k)$ be the optimal solution for the problem of $k$-center in the first $n$ points. For convenience, define $R(n,k) = 0$ if $k \ge n$ (This is reasonable because we can choose each point as the center of the cluster consisting of only itself).

For general $k \> 1$, we consider all the cases according to the number (denoted $m$) of points that are assigned to the last cluster (that is, the last cluster contains a contiguous sequence of the rightmost $m$ points).

$$R(n,k) = \min\_{0 \le m \le n} \\{ R(n-m, k-1) + R\_{m,1} \\}$$

The complexity of the "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.

---

**Note:** This paper \[1\] gives an $O(n \log n)$ time algorithm.

---

\[1\] Efficient Algorithms for the One-Dimensional $k$-Center Problem. arXiv, 2014.
> 1 votes

# Answer
Hint: In algorithms, if you're not sure how to solve the problem, sometimes it is helpful to look at a scaled down version of the problem. I suggest you start by looking at the version of the problem where $k=1$. I suspect you'll find that the problem is super-easy, when $k=1$ and you are on the 1-D line.

Next, see if you can solve it for $k=2$. I think you'll find that case is pretty easy, too, using the ideas you got from the $k=1$ case.

The obvious next step is to generalize to arbitrary $k$.
> 0 votes

# Answer
Take a look at Jenks natural breaks which are designed to partition a 1D scalar space. You can found a scala implementation of it here.
> 0 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Easy instances of the coloring problem on graphs with degree at most 4
Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.

In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?

# Answer
> 4 votes
You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".

But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.

# Answer
> 2 votes
As the other answer states, any class that is already easy to color can obviously be additionally restricted to bounded-degree graphs. But if you are looking for restrictions that only yield easily colored graphs in *combination* with the bounded-degree restriction, that also works.

For example: We know that graphs with bounded degree $d$ can be greedily colored with $d+1$ colors. But that by itself isn't optimal, since there are graphs in that class that can be colored with even fewer colors.

One way to fix that is by only considering the subclass of bounded-degree graphs that also need *at least* $d+1$ colors, ensuring that the greedy coloring is also the optimal one. So for example, the subclass of graphs of degree 4 that contain a 5-clique.

(Edit: There's also something called Brooks' theorem, which says that unless the graph really does contain such a 5-clique, it will actually be 4-colorable. But I can't see if it also says that this coloring can be found in polynomial time.)

---
Tags: complexity-theory, graphs, colorings
---


# Question
Title: Proof of undecideability that one state is reached before another
I'm trying to show that, for a deterministic Turing machine $M=(Q,\Gamma,\Sigma,\delta,q\_0)$, the language $K$, which includes all of the words $w \in \Sigma^\ast$ where the calculation of $M$ on $w$ pass on the state $q$ before reaching $q'$, but if $q'$ is never reached then $w$ is not in $K$, is both recursively enumerable and undecidable.

I am thinking that this could be solved by a reduction of the Halting problem, but I do not know how to proceed.

Reducing the Halting problem to this problem would mean that a machine $M$ with data $w$ will halt on $w$ iff a machine $M'$ with data $w$ that first passes state $q$ then $q'$. I see that if we were to associate $q$ in $M'$ with $q\_0$ in $M$ and $q'$ in $M'$ with $q\_f$ in $M$ we could associate part of the problem with the halting problem, but how can the condition "$q\_f$ must not be reached first" be included?

# Answer
> 2 votes
Let us follow the hint given by Yuval.

**What is the halting problem?**

It is the problem of accepting the following language.

$$\text{HALT}= \\{⟨M, w⟩ : M \text{ is a TM and }M\text{ will halt on input } w\\}$$

**What is the current problem?**

It is the problem of accepting the following language.

$$\begin{align} \text{One}&\text{StateBeforeAnother} = \\{⟨M, q, q',w⟩: M\text{ is a TM} \\\&\wedge q\text{ and } q'\text{ are two states of }M \\ &\wedge \left(M \text{ will reach } q' \text{ on input } w\right.\\ &\vee M \left.\text{ will reach } q \text{ before reaching } q' \text{ on input } w \right)\\} \end{align}$$

**How to define $\text{HALT}$ in a way similar to how $\text{OneStateBeforeAnother}$ is defined?**

The idea is that if we can formulate $\text{HALT}$ in a way similar to the way $\text{OneStateBeforeAnother}$ is defined, then we might reduce the former to the latter.

$M$ halts on input $w$ means $M$ reaches a halt state on input $w$. $\text{OneStateBeforeAnother}$ is about $M$ reaches $q$ and then $q'$.

Let us try brute pattern matching.

* Let $q$ be a halt state. $M$ reaches $q$, the halt state and then reaches $q'$. That cannot happen since the halt state is the last state. Sigh!
* Let $q'$ be a halt state. $M$ reaches $q$ and then reaches $q'$, the halt state. That makes sense. What is $q$ then? How about letting $q$ be the initial state of $M$?

Great, we have just found the following reduction, where $q\_0$ is the initial state of $M$ and $q'$ is the halt state of $M$ on input $w$.

$$⟨M, w⟩\in\text{HALT} \to ⟨M, q\_0, q',w⟩\in\text{OneStateBeforeAnother}$$

Wait, this is not a well-defined reduction as $q'$ cannot be known at the time of reduction since it depends on how $M$ runs on input $w$, the undecidable halting problem!

I will leave you to conquer the problem above, how to require $q'$ to be a halt state without dependence to $M$ and $w$.

---
Tags: reductions, undecidability
---


# Question
Title: Length of shortest codeword in Huffman encoding
Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1?

I thought of 2 cases where this might be true, but they're not exactly proofs -

Case 1: There is only one character which occurs more than 1/3rd of the time. In this case, a good huffman encoding scheme will ensure that this character corresponds to a single-character encoding, because there are no competing characters. Even though there may be characters that occur with high probability (but still less than 0.33), they must have length greater than 1 to ensure the prefix-free nature of the encoding.

Case 2: There are multiple characters that occur more than 33% of the time. We can also make the stronger assertion that in this case, there can only be at most 2 such characters. This can be further subdivided into cases where 1) there are a total of 2 characters in the encoding scheme, and 2) where there are more than 2 characters in the scheme. In case 1), both the characters can correspond to a single-character encoding scheme (0 and 1 for each respectively). In case 2), at most 1 of the 2 largely prevalent/frequent characters must have an encoding of length of 1 (since we're considering a good huffman encoding scheme) while the other n-1 characters have a length of at least 2.

I'm afraid that this is not the right approach. Could someone please help me out?

# Answer
> 2 votes
Consider the distribution $\Pr\[a\]=0.34,\Pr\[b\]=\Pr\[c\]=\Pr\[d\]=0.22$.

Huffman's algorithm will first merge (say) $c$ and $d$ to create the symbol $cd$ with probability $0.44$. It will then merge $a$ and $b$ to create the symbol $ab$ with probability $0.56$. Finally, it will merge the remaining symbols.

All codewords thus have length 2.

You can check that the same example works up to $\Pr\[a\] = 0.4$ (we need $\Pr\[a\] \leq 2\Pr\[b\] = (2/3)(1-\Pr\[a\])$). What if $\Pr\[a\] \> 0.4$? Consider the time at which Huffman's algorithm merges $a$ with some symbol $X$ (which may be composed of several original symbols). If $a$ and $X$ are the only symbols, then $a$ will be encoded using a symbol of length 1. Otherwise, there is some other symbol $Y$ of probability at least $\max(\Pr\[a\],\Pr\[X\]) \> 0.4$. We see that $a,X,Y$ must be the only remaining symbols, and furthermore $\Pr\[a\] \> \Pr\[X\]$ (otherwise there would 3 symbols whose probability exceeds 0.4).

Suppose that $Y$ was obtained by merging two other symbols $Z,W$. At that point, since $X$ itself or one of its constituents wasn't merged, we must have $\Pr\[X\] \geq \max(\Pr\[Z\],\Pr\[W\]) \geq \Pr\[Y\]/2$. But $\Pr\[Y\] \> 0.4$ and so $\Pr\[X\] \> 0.2$, and so the probabilities sum up to more than 1. This contradiction shows that $Y$ is an original symbol, and so in this case there is a codeword of length 1.

Concluding, the threshold for guaranteeing a codeword of length 1 is 0.4.

---
Tags: greedy-algorithms, huffman-coding
---


# Question
Title: Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$
I'm being asked the following

> Find a language $L$, such that $L \notin \mathbf{P}$, but $L^\* \in \mathbf{P}$

For the $L \notin \mathbf{P}$-part I have to show that there is no polynomial Turing Machine that could accept $L$.

I've been struggling with this problem for quite a while, so I would appreciate any help with it.

My attempt:

Let

$$L = \\{0, 1\\} \cup \\{0^i| M\_i\text{ does not accept }\langle M\_i \rangle\\}$$

Then $L^\* = \\{0, 1\\}^\*$. Since this language is regular, we can defined a TM that works on the word $w$ in just a single pass $\implies$ TM runs in $O(|w|) = O(n) \implies L^\* \in \mathbf{P}$.

I take this $L$ as example because it seems to me easier to show that $L \notin \mathbf{P}$ by proving that indeed there is no MT that accepts $L$ than showing that it is not accepted by any polynomial MT. To prove the former I was thinking about applying a diagolization argument on $L$.

Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked, so maybe there is a more straightforward way.

Thanks!

# Answer
> Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked

That looks like an excellent approach. Proving something stronger is sometimes easier1 and usually useful.

What's particularly nice about your template for $L$ is that it opens up new questions about what happens if you generalise to $L = A \cup B$ where $A$ and $B$ are in different complexity classes and $B \subset A^\*$. The extreme of $A$ regular and $B$ undecidable is good enough, but you could also consider $B \in NP^c$, $B \in EXP^c$, maybe specific context-free $A$, ... Perhaps it would be an interesting question to ask how *close* they can be to each other while still getting some kind of separation. If you enjoy this kind of thing, there may be a mini research project in it.

---

1 This is particularly true of proofs by induction, where proving a tight bound often makes the inductive step work where a loose bound wouldn't.
> 3 votes

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


title: How to train this neural network?

text:
# Question
Title: How to train this neural network?
I seek the neural network (NN) which satisfies the 100 equations (i=1,2...100)

$\sum\_{j=1}^{2000} NN(A\_{ij},B\_{ij},C\_{ij})=Q\_i$.

Where A,B,C are 100x2000 matrices

So I know Q, A, B and C How can one find the NN? (ie train it using this data) I have a second datset to test it on. I also have MATLAB neural network toolbox, but that is not a necessity for me to use that.

# Answer
> 3 votes
Let $w$ denote the weights of the neural network. Define the objective function $\Psi$ by

$$\Psi(w) = \sum\_i \left(\left(\sum\_j NN\_w(A\_{ij},B\_{ij},C\_{ij})\right) - Q\_i\right)^2.$$

Then, find $w$ that minimizes $\Psi(w)$ using gradient descent. You can find the gradient of $\Psi(w)$ using backpropagation through the neural network. You can use all the standard methods for speeding up training of neural networks: stochastic gradient descent, Adam or momentum or Adagrad, etc.

This is very similar to training neural networks for regression problems. The only difference here is that you are summing the output of the neural network on multiple inputs. It is straightforward to adjust the objective function to take that into account, as shown above.

---
Tags: neural-networks
---


# Question
Title: Determinant computation is equivalent to matrix powering
It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.

https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf

Does anybody why is this the case?

# Answer
It states that matrix powering is **computationaly** equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $\mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by *James R. Bunch and John E. Hopcroft*
> 2 votes

# Answer
Look at the paper by Stephen Cook (numbered $\[3\]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).
> 1 votes

---
Tags: complexity-theory, matrices
---


# Question
Title: Why c_f (u, v) = f (v, u) if f (v, u) not in E?
From page8 of the slide, I think $E$ is all the edges in the graph $G$. But why is $c\_f (u, v) = f (v, u)$ if $f (v, u)$ is not in $E$? Why do we care about edge that is not in $E$?

# Answer
There is a significant typo on that slide.

"$c\_f (u, v) = f (v, u)$ if $f (v, u)$ not in $E$" should have been "$c\_f (u, v) = f (v, u)$ if $(u, v)$ not in $E$" or, what is equivalent, "$c\_f (u, v) = f (v, u)$ if $(v, u)$ is in $E$".

> Why do we care about edge that is not in $E$?

In fact, we care only edge $(u,v)$ if either $(u,v)$ is in $E$ or $(v,u)$ is in $E$. If $(v,u)$ is in $E$, it appears that we care about $(u,v)$, an edge that is not in $E$.

The reason can be seen by looking at the specific example in those slides written by Vincent Maccio.

The flow in the above network is not the maximum flow, 6. However, there is no path from $s$ to $t$. How about adding a flow of 2 along the edges along the edges $s\to 2\to1\to3\to t$? This flow is **apparently invalid** since the only capacity between 1 and 2 are from 1 to 2 instead of from 2 to 1. However, if we consider the net effect of all flows on the edge between 1 and 2, it is effectively 0 as we had a flow of 2 from 1 to 2. So the combinations of all flows, including the apparently illegal flow are in fact valid.

Now the problem is how we can find that apparently invalid but actually valid and helpful additional flow. We did it by a stroke of luck or a flash of intelligence. The systemic way is to adjust the remaining capacities on possible more edges. In the example, we can add an edge from 2 to 1 of capacity 2, which will enable the algorithmic search for additional valid flow. That is, since directed edge (2,1) is not in $E$ (the directed edge (1,2) is in $E$), we would like to add edge (2,1) with capacity the flow through (1,2). That is " Why $c\_f (u, v) = f (v, u)$ if $(u, v)$ not in $E$."

For more information, check the slides and related materials on the web.
> 1 votes

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


# Question
Title: What's the worst case complexity of Robert W. Floyd's cycle detection algorithm?
**Givens**. I understand Floyd's algorithm can determine the length $\lambda$ of the loop and the length $m$ of the tail. The hare will not necessarily catch the tortoise on the first cycle, but it is guaranteed to catch it after a number $k$ of cycles, where $k$ is a natural number.

**Question**. Given I know these facts, how can I deduce the worst case complexity of the algorithm?

**An answer that seems fallacious**. For the tortoise and the hare to meet, they both need to be in the cycle. This will occur certainly after $\mu + \lambda$ iterations. Once the tortoise is in the cycle, the distance between the tortoise and the hare diminishes by one at each iteration. Yuval Filmus' answer shows that they meet in the cycle in an index that's a multiple of $\lambda$. Therefore, after they're both in the cycle, after $\lambda$ iterations (in the worst case) they must have reduced their distance to zero --- because the largest distance between them in the cycle is $\lambda$. But how do I know the hare didn't jump the tortoise? This argument doesn't seem very good.

# Answer
*(Adapted from a StackOverflow answer.)*

The tortoise arrives at the loop on iteration $\mu$. Since the hare moves faster, it is already in the loop. From the hare's perspective, the tortoise is now some distance ahead of it, and that distance is certainly less than $\lambda$.

Since the hare gets one step closer to the tortoise on each iteration, it will catch up in less than $\lambda$ more iterations, for a worst-case total of $\mu+\lambda-1$.

It is impossible for the hare to pass the tortoise without them both occupying the same spot. Suppose the hare is one step behind. Then, on the next iteration they will be on the same spot. If, on the other hand, the hare is more than one step behind, it will still be behind after the next iteration because it only gets one step closer.

Yuval's proof is much more precise and mathematical, and is certainly correct. But this simple explanation seems to have a certain intuitive value.
> 2 votes

# Answer
In this answer, I show that $x\_i = x\_{2i}$ iff $i \geq \mu$ and $i$ is a multiple of $\lambda$. In particular, this will happen for some index $i$ in the range $\\{\mu,\ldots,\mu+\lambda-1\\}$. This shows that the algorithm runs in time $O(\mu + \lambda)$.
> 2 votes

---
Tags: time-complexity
---


title: Algorithm for modified knapsack problem

text:
# Question
Title: Algorithm for modified knapsack problem
We have $n$-players in a game. We have a population of players we can choose from. Each player score is a normally distributed random variable and each player has a cost to add to the team. We are limited to $n$-players and the total cost must be less than or equal to $m$.

The total score for a team is calculated as the sum of all of the individual player's score on that team. Our goal is to maximize the expected team score while staying under our allowed player weight and number of players.

Now, suppose that in this game we drop the score of the player that has the lowest score on the team and do not consider it in the total team score.

Does a deterministic algorithm exist that will allow us to reach the optimal solution?

# Answer
> 2 votes
Let $X\_1,\dots,X\_n$ denote the scores of the individual members of the team. Then the score $Y$ of the team is given by

$$Y = X\_1 + \dots + X\_n - \min(X\_1,\dots,X\_n).$$

So, by linearity of expectation, the expected value of the score of the team will be

$$\mathbb{E}\[Y\] = \mathbb{E}\[X\_1\] + \dots + \mathbb{E}\[X\_n\] - \mathbb{E}\[\min(X\_1,\dots,X\_n)\].$$

This suggests a natural approach. Given a candidate list of members of the team, calculate the expected team score $\mathbb{E}\[Y\]$ using this formula. Try all possibilities for the list of team members, compute the expected team score for each, and pick the one that has the highest expected team score.

The biggest challenge is to evaluate the above formula for a particular list of team members. It is easy to evaluate $\mathbb{E}\[X\_i\]$, but evaluating $\mathbb{E}\[\min(X\_1,\dots,X\_n)\]$ where $X\_1,\dots,X\_n$ are independent Gaussian random variables is challenging. This is an order statistic, and there are various techniques for approximating its expected value. One is to numerically estimate a certain integral. Another is to use the approximation $-\Phi^{-1}({n-0.375 \over n+0.25})$, where $\Phi$ is the cdf of the normal distribution. See J.P. Royston, Expected Normal Order Statistics (Exact and Approximate), Journal of The Royal Statistical Society Series C (Applied Statistics), vol 31 no 2, pp.161-165. There may be better algorithms; hopefully this gives you the technical terms to use for searching.

---
Tags: algorithms, knapsack-problems
---


title: Last digit of polynomial value

text:
# Question
Title: Last digit of polynomial value
There is a simple-looking problem.

Given *integer* coefficients $c\_{0}, c\_{1}, c\_{2}, \dots, c\_{n - 1}$ of polynomial $$ p(x) = c\_{0} + c\_{1} x + c\_{2} x^{2} + \dots + c\_{n - 1} x^{n - 1} $$ and *integer* value $x$, find last digit of polynomial value at point $x$, or, equivalently, $p(x) \mod 10$.

My approach was to use Horner's rule for $p(x)$:

$$ c\_{0} + c\_{1} x + \dots + c\_{n - 1} x^{n - 1} = c\_{0} + x \left( c\_{1} + x \left( c\_{2} + x \left( c\_{3} + \dots + x \left( c\_{n - 2} + x c\_{n - 1} \right) \dots \right) \right) \right) ,$$

but for every multiplication we take current value modulo 10. Here is a Python function implementing this algorithm.

```
def solve(c, x):
    xmod = x % 10
    value = c[-1] % 10
    for i in range(len(c) - 2, -1, -1):
        value = (value * xmod + c[i]) % 10
    return value

```

Are there better algorithms in sense of computational complexity (i.e. faster)?

# Answer
### Remainder modulo 10 instead of last digit

What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10.

For simplicity, we will compute the value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The idea and algorithm in this answer can be adapted easily if 10 is replaced by another number.)

### Periodicity of the remainders of powers

The remainder of $x, x^2, x^3, x^4, \cdots$ are periodical for any integer $x$. Let $r(n)$ be remainder of $n$.

* $r(x^k)=0$ if $r(x)=0$
* $r(x^k)=1$ if $r(x)=1$
* $r(x^k)=x$ if $r(x)=5,6$
* $r(x^k)=r(x^{k+2})$ if $r(x)=9$
* $r(x^k)=r(x^{k+4})$ if $r(x)=2,3,4,7,8$

$k$ goes over all positive integers if $r(x)=0,2,4,5,6,8$. $k$ goes over all nonnegative integers if $r(x)=1,3,7,9$.

### Algorithm

Because of the periodicity, we can reduce the number of multiplication to at most 4 and the number of modulo operation to 2 without increasing the number of additions.

Here is the algorithm in Python, which should speak for itself. Note for a list `lst`, `lst[s::g]` means the subsequence `lst[s], lst[s+g], lst[s+2*g], ...` all the way to the end.

```
# c = [c_0, c_1, ..., c_{n-1}]
# remainder([3,12,5], 2) is 7
def remainder(c, x):
    x = x % 10

    if x == 0:
        return c[0] % 10
    if x == 1:
        return sum(c) % 10
    if x == 5 or x == 6:
        return (c[0] + sum(c[1:]) * x) % 10
    if x == 9:
        return (sum(c[::2]) + 9 * sum(c[1::2])) % 10
    if x == 2:
        return (c[0] + 2 * sum(c[1::4]) + 4 * sum(c[2::4]) + 8 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10
    if x == 3:
        return (sum(c[::4]) + 3 * sum(c[1::4]) + 9 * sum(c[2::4]) + 7 * sum(c[3::4])) % 10
    if x == 4:
        return (c[0] + 4 * sum(c[1::2]) + 6 * sum(c[2::2])) % 10
    if x == 7:
        return (sum(c[::4]) + 7 * sum(c[1::4]) + 9 * sum(c[2::4]) + 3 * sum(c[3::4])) % 10
    if x == 8:
        return (c[0] + 8 * sum(c[1::4]) + 4 * sum(c[2::4]) + 2 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10

```

If `remainder(c,x)` will be called repeatedly for the same polynomial `c`, then we can precompute table `d[i]`, where `d[i] = remainder(c,i)` for `i` from 0 to 9. Then for that polynomial c, we can return `d[x%10]` given `x` in $O(1)$ time.

We can also cache the result on the fly. This can be done nicely by returning a closure that computes each result fully at most once. That is linear time the first time and constant time later on for numbers with the same remainders.

```
# For example, r = remainder([3,12,5]); print(r(2)); print(r(2));
def remainder(c):
    d = [None] * 10

    def remainder_c(x):
        x = x % 10

        if x == 0:
            return d[0] if d[0] else c[0] % 10
        if x == 1:
            return d[1] if d[1] else sum(c) % 10
        if x == 5 or x == 6:
            return d[x] if d[x] else (c[0] + sum(c[1:]) * x) % 10
        if x == 9:
            return d[9] if d[9] else (sum(c[::2]) + 9 * sum(c[1::2])) % 10
        if x == 2:
            return d[2] if d[2] else (c[0] + 2 * sum(c[1::4]) + 4 * sum(c[2::4]) + 8 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10
        if x == 3:
            return d[3] if d[3] else (sum(c[::4]) + 3 * sum(c[1::4]) + 9 * sum(c[2::4]) + 7 * sum(c[3::4])) % 10
        if x == 4:
            return d[4] if d[4] else (c[0] + 4 * sum(c[1::2]) + 6 * sum(c[2::2])) % 10
        if x == 7:
            return d[7] if d[7] else (sum(c[::4]) + 7 * sum(c[1::4]) + 9 * sum(c[2::4]) + 3 * sum(c[3::4])) % 10
        if x == 8:
            return d[8] if d[8] else (c[0] + 8 * sum(c[1::4]) + 4 * sum(c[2::4]) + 2 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10

    return remainder_c

```

There are further micro-tuning for various special situations.

If you are interested in parallel algorithm, you can check Estrin's scheme that can speed up the computation.
> 4 votes

---
Tags: polynomials, modular-arithmetic, multiplication
---


# Question
Title: Number of computations for multiplication
I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:

> A startling discovery was made about multiplication itself in the thesis of S.A. Cook \[3\], which uses a result of A.L. Toom, as discussed in Knuth \[4\]. Consider the ordinary algorithm for multiplying decimal numbers: for two n-digit numbers this employs n-squared one-digit products. It is usually supposed that this is minimal. But suppose we write the numbers in two halves, so that the product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}. (The left-shift operation is considered to have negligible cost.) Then one can verify that
>
> N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).
>
> This involves only three half-length multiplications, instead of the four that one might suppose were needed. For large n, the reduction can obviously be reapplied over and over to the smaller numbers. The price is a growing number of additions. By compounding this and other ideas, Cook showed that for any e and large enough n, multiplication requires less than n\*(1-e) products, instead of the expected n-squared.

I got stuck when I read `stands for multiplying by 10 ...` because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.

Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.

# Answer
It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6\cdot10^2=600$. All he's doing is shifting a decimal number to the left.
> 4 votes

# Answer
From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)
> 4 votes

---
Tags: complexity-theory, multiplication
---


# Question
Title: Would Schmidhuber's theories of everything be capable of performing hypercomputation?
Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of computable physical laws. His work was based on Zuse's thesis.

This hypothesis would be inside the domain of Digital Physics, a group of hypothetical models that propose that the universe is analogous to a computer or an automata.

(https://en.wikipedia.org/wiki/Digital\_physics)

In 2000, he expanded this work by combining Ray Solomonoff's theory of inductive inference with the assumption that quickly computable universes are more likely than others. This work on digital physics also led to limit-computable generalizations of algorithmic information or Kolmogorov complexity and the concept of Super Omegas, which are limit-computable numbers that are even more random (in a certain sense) than Gregory Chaitin's number of wisdom Omega.

So since Chaitin's constant (https://en.wikipedia.org/wiki/Chaitin%27s\_constant) would allow hypercomputation if it existed in the pysics of the universe, would then Schmidhuber's hypothesis be able to perform hypercomputation? Also, in the hytpercomputation wikipedia entry (https://en.wikipedia.org/wiki/Hypercomputation) it says (In "eventually correct" systems):

> A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π and of every other computable real, but still excludes all noncomputable reals. Traditional Turing machines cannot edit their previous outputs; generalized Turing machines, as defined by Jürgen Schmidhuber, can. He defines the constructively describable symbol sequences as those that have a finite, non-halting program running on a generalized Turing machine, such that any output symbol eventually converges; that is, it does not change any more after some finite initial time interval. Due to limitations first exhibited by Kurt Gödel (1931), it may be impossible to predict the convergence time itself by a halting program, otherwise the halting problem could be solved. Schmidhuber uses this approach to define the set of formally describable or constructively computable universes or constructive theories of everything. Generalized Turing machines can eventually converge to a correct solution of the halting problem by evaluating a Specker sequence.

And also, Super-recursive algorithms are closely related to hypercomputation, and super recursive algorithm is just one way of defining hypercomputation. In super-recursive algorithms wikipedia entry (https://en.wikipedia.org/wiki/Super-recursive\_algorithm), Schmidhuber's model is included as a super-recursive algorithm-based model

So, knowing all of this, then, would Schmidhuber's hypothetical universes be based on hypercomputation?

# Answer
If the hypothesis is that we live in a universe whose physics are computed by a Turing machine, then hypercomputation is trivially impossible in our universe.

The constants you're taking about are limits of computable numbers. If all you have is a computer you can't produce such a number in finite time.

It sounds like you're taking two different things named after the same mathematician and assuming they're somehow connected when they're not.

(Disclaimer: I'm going off the information in the question alone.)
> 1 votes

---
Tags: turing-machines, halting-problem, real-numbers, hypercomputation
---


title: D flip flop : How does it work in depth

text:
# Question
Title: D flip flop : How does it work in depth
I'm coming to you today because I have some trouble to understand how works **D flip flop** in depth. Two weeks ago we started at school learning sequential logic and so register and everything that come with. We saw how to build a **D flip flop** using **RS Asynchronous flip flop** like this one :

Then we made a synchronous version of this one using two **AND logic gate** (one per input) and a clock input. The D flip flop we made is only a RS Asynchronous using only one input linked to S, and the NOT linked to R. Just like this :

And as I wrote it works on HIGH LEVEL. So to make any shift register based on this it is impossible. So I decided to go my own way and I ended with something like this :

I was conviced that it's the good way. It works on falling edge so it's perfect for shift register. And then my teacher told me that we couldn't use any gate on clock (in my case I use a NOT gate). But he can't tell me clearly how to do a D flip flop working on rising or falling edge. Even if Logisim (the software I use to simulate circuits) there is a D flip flop where you can make it working on Rising, falling edge or even at high or low level. So my main question is : **What is the good way to make a D flip flop working or RISING or FALLING edge if we can't use a single gate on clock ? And why can't we use gate on clock ?**

# Answer
> 1 votes
With the answer I got, and after I searched in Electrical engineering. I think I was both wrong and right. In fact it looks like we "can" use gate on clock signal theoretically, but in practice as Alain Merigot said (don't know how to mention) it can cause some trouble.

> The problem with gates is that you cannot master their traversal time (that depends on tech, temperature, etc) and relative traversal time on several gates can create unwanted spikes.
>
> On a clock, this can lead to real problems.

I still don't know how to create a **D flip flop** without using gate on clock signal and I think it requires way more knowledge I have to manage it. I now have my answer thank to people who helped me !

P.S : I don't know if there's a way to "close" a question.

Edit : "I still don't know how to create a **D flip flop** without using gate" -\> D flip flop working on rising/falling edge.

# Answer
> 3 votes
Here's a big hint, and then I'll let you work out the rest for yourself. Because we want cs.SE to be a collection of questions and answers, please post your solution as an answer.

Edge-triggered D flip flops are generally done using the "two RS flip flop" design that you have. You got that right. Reading from left to right, I'm going to call these RS flip flops "stage 1" and "stage 2".

Before the transition "happens", stage 1 should load the data. The effect of the transition is to make stage 1 hold its data and make stage 2 load its data from the output of stage 1.

So to create a D flip flop that is triggered on the *rising* edge:

* When the clock is *low*, stage 1 should *load* its data and stage 2 should *hold* its data.
* When the the clock is *high*, and stage 2 should *load* its data and stage 1 should *hold* its data.

The effect of this is that the transition from low to high shifts the result from stage 1 to stage 2.

Conversely, to create a D flip flop that is triggered on the *falling* edge, stage 1 should load when the clock is *high*, and stage 2 should load when the clock is *low*.

Now can you implement that?

Incidentally, I don't understand your teacher's requirement "we couldn't use any gate on clock". When you realise digital circuits in CMOS or NMOS, clock fanout is a large practical issue. Besides, you only get inverting gates, so putting gates on clock lines is normal and expected.

Nonetheless, perhaps they meant you to use de Morgan's laws to reduce the gate count?

---
Tags: logic, sequential-circuit
---