# Question
Title: Incomputable sets of low degree vs Rices theorem?
I have heard that there are sets that are not computable, but are lower in degree than the halting problem.

How does this not contradict Rice's theorem? Are there any concrete examples of such sets?

# Answer
This is not an answer, but way too long to be a comment. I just wanted to cite Robert I. Soare's *Recursively Enumerable Sets and Degrees*, Chapter V: *Simple Sets and Post's Problem*.

> **1: *Immune Sets, Simple Sets, and Post's Construction***
>
> The only r.e. degrees constructed so far are $\textbf{0}$ and $\textbf{0}'$. *Post's Problem* was to construct other r.e. degrees, i.e., to construct an r.e. set $A$ such that $\emptyset \lt\_\text{T} A \lt\_\text{T} \emptyset'$. *Post's Program* for constructing such a set $A$ was to ﬁnd some easily deﬁnable property on $\overline{A}$ (compatible with $A$ being nonrecursive) which guarantees incompleteness ($K \not\leq\_\text{T} A$).
>
> Recall (from Theorem II.4.5) that $K$ (and hence any creative set) has an inﬁnite r.e. set (and therefore inﬁnitely many inﬁnite r.e. sets) contained in its complement. Post's idea for constructing $A$ incomplete was to make $\overline{A}$ sufﬁciently "thin" with respect to containment of inﬁnite r.e. sets so that $\overline{K}$ could not be Turing reduced to $\overline{A}$.
>
> **1.1 Deﬁnition.** (i) A set is *immune* if it is infinite but contains no infinite r.e. set.
> (ii) A set $A$ is *simple* if $A$ is r.e. and $\overline{A}$ is immune.
>
> **1.2 Proposition.** If $A$ is simple then:
>
> (i) $A$ is not recursive;
> (ii) $A$ is not creative;
> (iii) $A$ is not $m$-complete (i.e., $K \not\leq\_m A$).
>
> Proof. (i) $\overline{A}$ cannot be r.e., since otherwise it contains an inﬁnite r.e. set (namely $\overline{A}$).
>
> (ii) The complement of a creative set does contain an inﬁnite r.e. set (by Theorem II.4.5).
>
> (iii) If $K \leq\_m A$, then $A$ is creative (by Corollary II.4.8). $\Box$
>
> **1.3 Theorem** (Post \[1944\]). There exists a simple set $S$.
>
> *Proof.* Let $A = \\{(e,x) \\;:\\; x \in W\_e \\;\\&\\; x \> 2e \\}$. Now $A$ is $\Sigma\_1$ and hence r.e. Let $\psi$ be any p.r. selector function for $A$ (in the sense of Theorem II.1.6) and let $S = \text{rng}\\; \psi$. (Intuitively, enumerate $W\_e$ until the ﬁrst element $\psi(e) \> 2e$ appears in $W\_e$, and then put $\psi(e)$ into $S$.) The following facts give the simplicity of $S$.
>
> (1) $S$ is r.e. ($S$ is the range or a p.r. function.)
>
> (2) $\overline{S}$ is inﬁnite. To see this, note that $S$ contains at most $e$ elements out of $\\{0,1,2,\dots,2e\\}$, namely $\psi(0),\psi(1), \dots, \psi(e-1)$. Hence $e + 1 \leq \text{card}(\overline{S} \upharpoonright (2e+1))$, so $\overline{S}$ is inﬁnite.
>
> (3) If $W\_e$, is inﬁnite, then $W\_e \cap S \neq \emptyset$, because $(e,x) \in A$ for some $x \> 2e$ and so $\psi(e)$ is deﬁned and $\psi(e) \in S \cap W\_e$. $\Box$
> 2 votes

---
Tags: turing-machines
---


# Question
Title: What is the intuition behind Strassen's Algorithm?
I came across **Strassen's algorithm** for matrix multiplication, which has time complexity $O(n^{2.81})$, significantly better than the naive $O(n^3)$. Of course, there have been several other improvements in matrix multiplication since Strassen, but my question is specific to this algorithm.

If you see the algorithm, you'll notice that 7 matrices $M\_1$ to $M\_7$ have been defined as intermediate computation steps, and the final matrix product can be expressed in terms of these. I understand how to verify this claim, and arrive at the expression for the desired time complexity, but **I'm unable to grasp the intuition behind this algorithm**, i.e. **why are the matrices $M\_1$ through $M\_7$ defined the way they are?**

Thank you!

# Answer
> 16 votes
The real answer to this question is that if you play with it long enough, you'll hit an algorithm requiring 7 multiplications – not necessarily the same as Strassen's, but an equivalent one, in a certain sense: it is known that all such algorithms are equivalent, as shown by de Groote in his 1978 paper, On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for 2 × 2-matrix multiplication.

There are many attempts in the literature to explain how one could come up with such an algorithm, for example:

Gideon Yuval shows how *you* could come up with Strassen's algorithm. The starting point is to convert matrix multiplication to the problem of computing a matrix-vector product: computing $$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \times \begin{pmatrix} e & f \\ g & h \end{pmatrix} $$ is the same as computing $$ \begin{pmatrix} a & 0 & b & 0 \\ 0 & a & 0 & b \\ c & 0 & c & 0 \\ 0 & d & 0 & d \end{pmatrix} \times \begin{pmatrix} e \\ f \\ g \\ h \end{pmatrix} $$ Suppose that we could write the matrix on the left as a sum $\ell\_1 M\_1 + \cdots + \ell\_7 M\_7$, where $\ell\_i$ is a linear combination of $a,b,c,d$ and $M\_i$ is a rank one matrix, say $M\_i = x\_i y\_i^T$. The product we are after is thus $$ \sum\_{i=1}^7 \ell\_i M\_i \begin{pmatrix} c\\d\\e\\f \end{pmatrix} = \sum\_{i=1}^7 \ell\_i x\_i y\_i^T \begin{pmatrix} c\\d\\e\\f \end{pmatrix} = \sum\_{i=1}^7 \ell\_i r\_i x\_i, $$ where $r\_i$ is a linear combination of $e,f,g,h$. This shows that each entry of the product matrix is some linear combination of the products $\ell\_i,r\_i$.

Let us now show how one could find the decomposition. We start by cancelling the top left and bottom right entries, in a way which avoids hitting zero entries: $$ \begin{pmatrix} a & 0 & b & 0 \\ 0 & a & 0 & b \\ c & 0 & d & 0 \\ 0 & c & 0 & d \end{pmatrix} = \begin{pmatrix} a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \\ a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \\ 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \end{pmatrix} + \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & a-d & 0 & b-d \\ c-a & 0 & d-a & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} $$ This results in a mess, which we try to fix by "flipping" the inner square: $$ \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & a-d & 0 & b-d \\ c-a & 0 & d-a & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & a-d & a-d & 0 \\ 0 & d-a & d-a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & d-a & b-d \\ c-a & a-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} $$ Since $d-a = (b-a)-(b-d)$ and $a-d = (c-d)-(c-a)$, it is easy to represent the last matrix as a sum of four rank one matrices: $$ \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & d-a & b-d \\ c-a & a-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & b-a & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & d-b & b-d \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & c-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ c-a & a-c & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$ In total, we obtain the following representation: $$ \begin{pmatrix} a & 0 & b & 0 \\ 0 & a & 0 & b \\ c & 0 & d & 0 \\ 0 & c & 0 & d \end{pmatrix} = \begin{pmatrix} a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \\ a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \\ 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & a-d & a-d & 0 \\ 0 & d-a & d-a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & b-a & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & d-b & b-d \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & c-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ c-a & a-c & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$

# Answer
> 5 votes
It’s reasonably obvious that if you can calculate a 2x2 matrix product with 7 multiplications and quite a few additions, you get an asymptotically faster algorithm. You need 8 products. But for example (a+b)\*(c+d) gives you the sum of four products with one multiplication.

So it *might* be possible to calculate many products with seven multiplications in such away that all the unwanted products cancel each other out. I don’t know how many products he tried that in the end didn’t work out.

---
Tags: algorithms, algorithm-analysis, matrix-multiplication
---


# Question
Title: Does DFS have better constants/complexity than Backtracking on a Graph?
I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step by step while DFS on a graph may directly jump some nodes backwards, is DFS a faster algorithm? If so, only in terms of constants or complexity wise?

Edit: Maybe the original writeup was a bit confusing. What I mean specifically is this.

DFS:

A normal implemetation of DFS should traverse the following tree in this manner A-\>B-\>C-\>D. This implies that the implementation for what we normally refer to as DFS visits each node exactly once, giving it a time complexity O(V) where V is the number of vertices.

By Backtracking, what I have in mind is this:

This I feel is a more bare bones approach where one step of backtracking actually goes to a parent node and explores its other children, instead of skipping over some parent nodes which had only one child (node B here) to begin with. This results in a traversal sequence of A-\>B-\>C-\>B-\>A-\>D. This particular example shows that this is always going to require more nodes to be visited than the standard DFS and hence the question.

# Answer
> 1 votes
When you explore a graph of $N$ vertices and $E$ edges, you basically need to store the visited vertices in a $N$ boolean array. But eventually (when you are interested in retrieving path and not only connection), you will use instead a $N$ bactrack array, containing for each vertex, the one that let you reach it (the parent vertex in the exploration tree).

Exploration methods BFS and DFS needs an extra storage for a queue of vertices to visit which size is $O(N)$. One can consider that the difference between BFS and DFS is just that they respectively use a FIFO and LIFO queue. Note that DFS algorithms often use a recursion hiding the additional storage.

Now, what you call "backtrack" is just a simpler way to do the DFS as you don't have a "todo" queue. When a vertex is fully explore, you just go back in the exploration tree. Of course, it is less efficient than DFS as you will run the exploration loop several times on some vertex. One can argue that it is slightly more efficient in space as you save the queue storage, but practically, this is negligible.

# Answer
> 0 votes
In DFS also the traversal sequence on the above graph will be A-\>B-\>C-\>B-\>A-\>D-\>A. It is just that it prints a node when it visits it first time and marks it as visited.

In this case, it'll print A B C but when it again visits B and A it ignores it as it is already visited.

Backtracking is a programming paradigm whereas DFS is an actual algorithm that uses backtracking to traverse the tree. Hope that helps.

---
Tags: graphs, time-complexity, graph-traversal, backtracking, depth-first-search
---


# Question
Title: Big-O of iterating through nested structure
While trying to understand complexity I run into an example of going through records organized in following way:

```
data = [
  {"name": "category1", "files": [{"name": "file1"}, {"name": "file2"}],
  {"name": "category2", "files": [{"name": "file3"}]
]

```

The task requires to go through all file records which is straight forward:

```
for category in data:
  for file in category["files"]:
    pass

```

It seems like complexity of this algorithm is O(n * m), where `n` is length of `data` and `m` is max length of `files` array in any of `data` records. But is O(n * m) only correct answer?

Because even there are two for-loops it still looks like iterating over a global array of file records organized in nested way. Is it legit to compare with iteration over different structure like that:

```
data = [
  ('category1', 'file1'),
  ('category1', 'file2'),
  ('category2', 'file3'),
]
for category, file in data:
  pass

```

...where complexity is obviously O(n), and `n` is a total number of records?

# Answer
A better bound on the complexity is $O(k)$, where $k$ is the total number of files.

A similar situation is encountered in algorithms for sparse matrices. Sparse matrices are stored as a list of all non-zero entries. The running time is often analyzed in term of the number of non-zero entries rather than the dimensions of the matrix. The reason is that matrices encountered in practice are often sparse (or can be sparsified), and we are interested in algorithms taking advantage of this.
> 2 votes

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


# Question
Title: How important is initial state for local search optimisation?
I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation.

I'm wondering how important the initial configuration is to the quality of solution achievable in a fixed time or, somewhat equivalently, how quickly a solution of a given quality can be reached.

So if I have a good heuristic or intuition for how to arrange things in the first place, is it helpful to devote some processing time to setting that up or is it all dominated by the effect of the local search process?

For example, in the Cartesian Travelling Salesman Problem (where we're working in a 2D plane and the cost of a journy is simply the straight-line distance) I might "feel" that a good route could roughly follow a clockwise sweep from the centre of the space. So I could use this to set my initial tour (i.e. order the nodes by their angle from the mean of all points). This intuition might be rubbish for certain instances and great for others, I was hoping to see a study where (let's say random TSP) instances had been solved by following a heuristic first state as opposed to a completely random (but legal) first state.

# Answer
A good initial state can often be helpful. I would guess that there is a significant chance that spending extra time to find a good initial state will be useful.

All we can say in general is that "it depends". It depends on the specific problem and the shape of the fitness landscape. If the problem has few or no local minima, the search might not be very sensitive to the initial state. If it has many local minima, the search might be very sensitive to the start state, and a good start state might help again. There are no universal answers that can be supplied.

Usually the only way to answer these questions is to try it and see. With heuristics, there aren't any provable guarantees and it's often hard to make many predictions based on theory or analysis.
> 3 votes

---
Tags: optimization, heuristics
---


# Question
Title: Is there an algorithm for reducing CNFs further?
I have a Boolean formula in conjunctive normal form (CNF)

$$(a\vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge (x \vee y)$$

I know that this can be simplified to $(a\vee b)\wedge (x \vee y)$.

1. Is there an algorithm to decide if a CNF is already in the reduced form or not?
2. Is there an algorithm that can do this reduction in an manner more efficient than comparing each pair of clauses to see if any pairing can be reduced? I wish to automate this reducing for any CNF and am looking for any algorithms that I can borrow/implement.

# Answer
> 2 votes
CNF minimization is hard; see https://cstheory.stackexchange.com/q/9839/5038. It is certainly NP-hard, and there is a sense in which it is "even harder".

One way to get some intuition why it is hard is that if the CNF is not satisfiable, then its reduced form is "False", whereas if it is satisfiable, its reduced form is something else. So, if you had an efficient way to find a reduced form, that would immediately give you a way to tell whether the CNF is satisfiable -- a task that we know is NP-hard.

See https://cstheory.stackexchange.com/q/9839/5038 and https://en.wikipedia.org/wiki/Logic\_optimization#Circuit\_minimization\_in\_Boolean\_algebra for some points into the literature on algorithms for this task.

---
Tags: algorithms, satisfiability, normal-forms, term-rewriting
---


# Question
Title: How is the space complexity O(LogN) for rangeSumBST problem
Recursive

```
class Solution {

    int ans;
    public int rangeSumBST(TreeNode root, int L, int R) {
        ans = 0;
        dfs(root, L, R);
        return ans;
    }

    public void dfs(TreeNode node, int L, int R) {
        if (node != null) {
            if (L <= node.val && node.val <= R)
                ans += node.val;
            if (L < node.val)
                dfs(node.left, L, R);
            if (node.val < R)
                dfs(node.right, L, R);
        }
    }
}

```

Iterative

```
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        int ans = 0;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (L <= node.val && node.val <= R)
                    ans += node.val;
                if (L < node.val)
                    stack.push(node.left);
                if (node.val < R)
                    stack.push(node.right);
            }
        }
        return ans;
    }
}

```

Source: https://leetcode.com/problems/range-sum-of-bst/solution/

Suppose `L` is `Integer.MIN_VALUE` and `R` is `Integer.MAX_VALUE`, then wouldn't it traverse through all the nodes. Since we need to check the worst case, shouldn't it be O(N) instead of O(logN)

# Answer
> 1 votes
The space complexity is the amount of space used, which is essentially the size of your call stack in your deepest line of recursion. The runtime is indeed $O(N)$ but the space complexity is $O(H)$ where H is the height of the tree.

Even following the link you provided, they state this:

---
Tags: trees, binary-trees, space-complexity, stacks
---


# Question
Title: Complexity of algorithm partitioning input into parts of size $n/100$ and $99n/100$
Merge sort always divides array of size $n$ into parts each of size $n/2$. It then merges these two parts. So its recurrence relation is $T(n)=2T(n/2) + O(n)$. What if there is an algorithm which is guaranteed to partition the array into two parts of sizes $n/100$ and $99n/100$? So its recurrence relation will be $T(n)=T(n/100)+T(99n/100)+O(n)$.

It feels like this relation is not as good as merge sort in terms of time. I think that such an algorithm's worst case time complexity should be between that of $O(n^2)$ and $O(n\log n)$.

I have two questions:

1. Is $n/2$ and $n/2$ partitioning the most optimal or $n/100$ and $99n/100$ partitioning also asymptotically optimal?
2. How to solve the recurrence relation $T(n)=T(n/100)+T(99n/100)+O(n)$?

# Answer
> 1 votes
The simplest way to answer this question is using the Akra–Bazzi theorem, a vast generalization of the Master theorem. Using the Akra–Bazzi theorem, you can show that the solution of the recurrence $T(n) = T(\alpha n) + T((1-\alpha) n) + O(n)$ is $T(n) = \Theta(n\log n)$ for all constant $\alpha \in (0,1)$.

You can also use a recursion tree. This is a tree in which the root is $n$, and any node whose value is $m \geq n\_0$ has two children labeled $\alpha m$ and $(1-\alpha) m$. The total cost of the algorithm is proportional to the sum of all values in the tree.

Suppose that $n$ is very large, and consider the first few levels of the tree:

* The first level consists of the root, labeled $n$.
* The second level consists of two nodes, labeled $\alpha n$ and $(1-\alpha) n$.
* The third level consists of four nodes, labeled $\alpha^2 n$, $\alpha(1-\alpha) n$, $\alpha(1-\alpha) n$, and $(1-\alpha)^2 n$.

You can see that the labels in each level sum to $n$. At some point this will stop happening because the tree has leaves when the value drops below $n\_0$, but the first $\min(\log\_{1/\alpha} (n/n\_0), \log\_{1/(1-\alpha)} (n/n\_0))$ are complete. In contrast, each level sums up to at most $n$, and there are at most $\max(\log\_{1/\alpha} (n/n\_0), \log\_{1/(1-\alpha)} (n/n\_0))$ levels. Putting the two together, we see that the complexity is $\Theta(n\log n)$.

---

With more effort we can find the dependence of the complexity on $\alpha$. For concreteness, let us assume that the recurrence is $T(n) = T(\alpha n) + T((1-\alpha) n) + n$, and consider $S(n) = T(n)/n\log n$, which satisfies the recurrence $$ S(n) = \frac{\alpha n \log (\alpha n)}{n \log n} S(\alpha n) + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} S((1-\alpha) n) + \frac{1}{\log n}. $$ Suppose that $S(n) \longrightarrow C$. Substituting $S(n) = C$ in the recurrence, we obtain \begin{align} C &= \frac{\alpha n \log (\alpha n)}{n \log n} C + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} C + \frac{1}{\log n} \\ &= \alpha C + (1-\alpha) C + \frac{\alpha \log \alpha C + (1-\alpha) \log (1-\alpha) C + 1}{\log n} \\ &= C + \frac{1 - h(\alpha) C}{\log n}, \end{align} where $h(\alpha)$ is the entropy function. Thus, if $S(n) \longrightarrow C$ then $C = 1/h(\alpha)$, which is indeed minimized when $\alpha = 1/2$ and symmetric with respect to $\alpha$ and $1-\alpha$.

Here is another way to see where $h(\alpha)$ is coming from. Consider a random element from the original array. With probability $\alpha$, it belongs to the first half of size $\alpha n$, and with probability $(1-\alpha)$ it belongs to the second half of size $(1-\alpha) n$. In this way, we can trace what happens to the element until it reaches a subarray of size $n\_0$ or less. The contribution of this element to the total complexity is the depth at which the terminal subarray is reached, so we are interested in the expected depth of this process.

Let $N\_t$ be the size of the subarray at time $t$. Thus $N\_0 = n$, and if $N\_t \geq n\_0$, then $N\_{t+1} = \alpha N\_t$ with probability $\alpha$, and $N\_{t+1} = (1-\alpha) N\_t$ with probability $(1-\alpha)$. It is easy to check that $\mathbb{E}\[\log (N\_t/N\_{t+1}))\] = h(\alpha)$. Since $\log(N\_t/N\_0) = \sum\_{s=0}^{t-1} \log(N\_{s-1}/N\_s)$, linearity of expectation shows that $\mathbb{E}\[\log (N\_t/n\_0)\] = t h(\alpha)$ (assuming the the process continues forever, even after reaching size $n\_0$), and so the expected time to hit a leaf is $\log(n/n\_0)/h(\alpha)$.

---
Tags: algorithm-analysis, divide-and-conquer
---


title: VC dimension of set of functions

text:
# Question
Title: VC dimension of set of functions
Let $\chi$ be an instance space and $H \in \\{0, 1\\}^\chi$ a class with finite VC-dimension. For each $x \in X$ we consider $z\_x\colon H \rightarrow \\{0, 1\\}$ s.t. $z\_x(h) = h(x), \forall h \in H$.

Let $Z = \\{z\_x:H\rightarrow\\{0,1\\}\mid x\in\chi\\}$. Is $\mathit{VCdim}(Z)\<2^{\mathit{VCdim}(H)+1}$?

---

The only thing that comes to mind when seeing this is the Sauer lemma, but that's related to the growth function and I don't see how to apply it here. Anyone got any idea on how to approach this?

# Answer
> 1 votes
This is a classical result of Assouad (Densité et dimension) about *dual VC dimension*.

Let $A$ be a binary matrix. The VC dimension of $A$ is the maximal size of a set $S$ of columns which are shattered, that is, all possible rows appear when we restrict $A$ to the columns in $S$. The dual VC dimension of $A$ is the VC dimension of $A^T$, the transpose of $A$.

Suppose that $A^T$ has VC dimension $2^{d+1}$. Then there is a set $S$ of $2^{d+1}$ rows of $A$ such that when we restrict $A$ to this set of rows, we see all possible columns. If we number the rows using binary numbers of length $d+1$, then in particular we see the following columns: for each $i$, there is a column which contains the $i$'th bit of the row index. For example, if $d=1$ then we see the following columns: $$ \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} $$ Therefore the VC dimension of $A$ is at least $d+1$.

If we take $d = \mathrm{VC}(A)$, then we deduce $\mathrm{VC}(A^T) \< 2^{\mathrm{VC}(A)+1}$.

---
Tags: vc-dimension
---


# Question
Title: Count minimum number of steps to destroy all blocks
Given a sequence of integers $A\_x$ of length $n$ such that $1 \leq A\_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the same value as the element we remove. We want to count the minimum number of steps to remove all elements.

For example, if our sequence is $\[1, 2, 2, 2, 2, 3, 3, 3, 1\]$, we can remove it in three steps: firstly we remove the twos, then we remove the threes, and on the end we remove the final two ones. Our sequence transforms as follow: $\[1, 2, 2, 2, 2, 3, 3, 3, 1\] \to \[1, 3, 3, 3, 1\] \to \[1, 1\]$.

I tried using Dynamic Programming to solve this problem, and my idea was to use $DP\[i\]\[j\]$ to represent the minimum steps to clear the interval $\[i, j\]$, however I'm not sure how to work out the transitions, and I'm stuck on the part that there can be some element in the middle of the interval which can be merge with the ends of the interval, and my DP relations cannot handle such cases.

# Answer
A very similar problem is the one of clearing the board in an instance of the Two-Dots that only has one column.

This is a single-player game played on a column of colored dots. A move consists of removing a contiguous group of at least two dots that all share the same color and then consolidating all remaining dots. The goal is to clear the column in the fewest number of moves.

A dynamic programming algorithm for this problem is devised in section 4.2.1 of this paper. As you suggest $C(i,j)$ is defined as the minimum number of moves needed to clear all (and only) the dots in rows $i$ through $j$.

Your problem has a couple of minor differneces:

1. A move always deletes a maximal (w.r.t. inclusion) monochromatic group of adjacent dots.
2. You can also remove a single "dot" if it doesn't match with any neighboring dot.

Here the constraint in 1) can be safely relaxed since it is the case that there is always an optimal solution for the Two-Dots problem that also satisfies such constraint.

To account for 2) you need to redefine $C(i,i) = 1$ (since a single dot can be removed with a single move) and and, for $i\<j$, $C(i,j) = \min \\{C\_1(i,j), C\_2(i,j), 1 + C(i+1,j) \\}$ where $C\_1$ and $C\_2$ are as in the paper and $1 + C(i+1, j)$ considers the case where the first dot is not matched with anything in an optimal solution.
> 1 votes

---
Tags: dynamic-programming, arrays
---


# Question
Title: Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}
I have the following question :

\begin{align} L\_2 = \\{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\ \text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\\} \end{align}

I know that $L\_2 \in$ NPC.

Show that $L\_2 \in$ NP is relatively easy, I'll skip that part.

I try to show that $L\_2 \in$ NPC using a reduction from VC $\leq\_p L\_2$ (VC is vertex cover which we know in its NPC)

I defined the following function $f$ :

$$f(G,k)=(a,k)$$

I thought of something like that for each node $i$ in $G$ will define a literal $x\_i$, and make it in 3DNF format, $a=\bigvee(x\_i \wedge x\_i \wedge x\_i)$ where $1 \leq i \leq n$ where $n$ is the number of nodes in $G$. We can define that following $z$ such that $z$ safifies exactly $k$ clauses, just give $'1'$ literal $x\_i$ such that the node $i$ is in the VC, and $'0'$ otherwise, so such $z$ exists.

So easy to see that $(G,k) \in$ VC $\implies (a,k) \in L\_2$ since we showed explicitly such $z$ that safifies exactly $k$ clauses.

But I'm not sure the other side holds $(G,k) \not\in$ VC $\implies (a,k)\not\in L\_2$ we given a graph that doesn't have VC in size $k$ but I think due to my building of a ($a=\bigvee(x\_i \wedge x\_i \wedge x\_i)$) we can find $z$ that safifies exactly $k$ clauses (actually we can find $z$ that safifies $x$ clauses where $1 \leq x \leq n$ where $n$ is number of nodes in $G$.

So my reduction doesn't hold?

# Answer
> 2 votes
The reason for why you are having problems is because your solution does not work. In particular, the problem is that your formula does not capture the VC problem statement. More precisely, the formula you build always has assignments satisfying $k$ clauses by just setting $k$ variables to true and the rest to false.

So let $G = (V, E)$ be a graph and $X \subseteq V$ be a VC in $G$. Then for any edge $vw \in E$ we must have $v \in X$ or $w \in X$, giving us 3 mutually exclusive possibilities (by essentially rewriting $v \vee w$ in DNF):

* $v \in X$ but $w \notin X$,
* $v \notin X$ but $w \in X$
* $v \in X$ and $w \in X$

Hence the edge $vw$ is covered by $X$ if and only if the formula $\psi(vw) = (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$ has exactly one satisfied clause (under the assignment corresponding to $X$).

Constructing such a formula for every edge and taking their disjunction, we get the DNF formula $$\psi^\text{VC}(G) = \bigvee\_{e \in E} \psi(e) = \bigvee\_{vw \in E} (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$$ and any assignment satisfying exactly $|E|$ clauses must be a VC of $G$. Now we need a way to encode the size of the VC into it all, for which we can reuse your idea. Define $$\psi(G) = \psi^\text{VC}(G) \vee \bigvee\_{v \in V} v$$ and note that the number of satisfied clauses in the second part is just given by the size of the set of vertices we select, so the total number of satisfied clauses under the assignment corresponding to some VC $X$ in $G$ is $|E| + |X|$.

There is only one problem remaining here. We could get an assignment not corresponding to a VC but including more vertices to satisfy the same number of clauses that a desired VC would. As a remedy, we can repeat the first formula some $|V| + 1$ times such that no matter how many vertices you chose, the total number of satisfied clauses will always be too low.

Hence we obtain the final formula $$\psi^\ast(G) = \bigvee\_{i = 1}^{|V| + 1} \psi^\text{VC}(G) \vee \bigvee\_{v \in V} v$$ and note that if $G$ has a VC $X$ then the corresponding assignment will satisfy exactly $(|V| + 1) \cdot |E| + |X|$ clauses of $\psi^\ast(G)$. For the reverse direction, let $\alpha$ be some assignment satisfying $(|V| + 1) \cdot |E| + k$ clauses of $\psi^\ast(G)$. Then $\alpha$ must represent a VC in G as otherwise, the number of satisfied clauses in the first part of $\psi^\ast(G)$ is at most $(|V| + 1) \cdot (|E| - 1) = |V| \cdot |E| + |E| - |V| - 1$ and as $\alpha$ can satisfy at most $|V|$ clauses in the second part, the total number of satisfied clauses will be at most $$(|V| + 1) \cdot (|E| - 1) + |V| = |V| \cdot |E| + |E| - 1 \< (|V| + 1) \cdot |E|$$ However, this implies that the total number of satisfied clauses in the first part must be exactly $(|V| + 1) \cdot |E|$ and thus exactly $k$ clauses of the second part are satisfied by $\alpha$, so $\alpha$ corresponds to a VC $X\_\alpha$ of size $k$ in $G$.

Note that for clarity I did not specify a $3$-DNF formula. However, as all clauses in $\psi^\ast(G)$ are of size at most $2$ you can just add redundant literals to the clauses to blow them up to size $3$ if need be.

I am not sure that this is the best way to do this, but it should work out. I omitted some details for brevity, please feel free to ask for additional clarifications if something is not clear to you :)

---
Tags: complexity-theory, np-complete, check-my-answer, polynomial-time-reductions
---


# Question
Title: For every imperative function, is there a functional counterpart with identical performance or even instructions?
Currently, I haven't learned about a functional language that can achieve the same performance as C/C++. And I have learned that some languages that favor functional programming to imperative programming, such as Scala and Rust, use imperative ways to implement their library functions for better efficiency.

So here comes my question, on today's comptuters that execute imperative instructions, is this a limitation of the compiler or functional programming itself? For every imperative function with no side effects, either in a language without GC such as C/C++/Rust/assembly or one with GC such as Java, is there a pure functional counterpart in Haskell, Scala, etc. that can be compiled to run with identical performance in time and space (not just asymptotic but exactly the same) or even to the same instructions, with an optimal functional compiler that utilizes all modern and even undiscovered optimization techniques such as tail recursion, laziness, static analysis, formal verification, and so on which I don't know about?

I am aware of the equivalence between λ-computable and Turing computable, but but I couldn't find an answer to this question online. If there is, please share a compiler example or a proof. If not, please explain why and show a counter-example. Or is this a non-trivial open question?

---

**Supplementary edits as suggested by Andrej Bauer:**

To be more specific, here are 2 examples that led into thinking about this question.

For example, tail recursion and accumulators can improve the performance of some recursive functions to be identical to an imperative implementation using `for`. In some cases they might even have the same instructions.

Another example is about laziness in Haskell. Laziness can help avoid unnecessary copying of data structures and make performance better. However, laziness leaves wrappings, closures, etc. in the runtime and still can't make the program as fast as an imperative implementation where there are no such things. So I am wondering whether such things can be statically removed before runtime during compilation.

**Supplementary edits as suggested by Nearoo:**

The question can also be stated in this way: is there a language that supports both pure functional programming and imperative programming, paired with an optimized compiler, in which every function with no side effects implemented imperatively can be replaced with one implemented purely functionally, at no cost of performance or even compiled to the same instructions?

# Answer
1. Performance is not a property of language, it is a property of specific programs within a language. Some languages might be very fast at some things and slow at others.

For example, Chez-Scheme can sometimes find performance comparable to C, not because the language is more efficient, but because defensive practices that programmers often use in C are less necessary in scheme.

Likewise, there are times when Haskell can do very efficient parallelism or concurrency, not because it is faster than C, but because the immutability guarantees of the language allow the programmer to avoid things like locks and other synchronization techniques.

And, performance varies from implementation to implementation. I can hand-roll a C interpreter, but it will certainly not be fast. C is not fast, GCC and Clang are.
2. What is considered a "functional" language? Every practical functional language has some facilities for mutable state: OCaml, Haskell, Scala, Lisp, Scheme, etc. Tail recursion gives something roughly equivalent to mutation inside of a for-loop. But when this is not enough, functional languages give the programmer access to mutable state. In the case of Haskell, this is controlled by the type system, so there is never *implicit mutable state*, but mutation is very much allowed and even encouraged in Haskell. Look at any Haskell code, and you will see the IO monad everywhere. Likewise, ML languages distinguish between types `T` and `ref T`, so you can tell by the types whether a variable is mutable or not.
3. There is no "optimal" compiler, thanks to Rice's theorem. All compilers, imperative or functional, are "best effort:" the use conservative approximations to optimize code.

If we had an optimal compiler, the answer would be that every program always ran using the most efficient instructions possible, and it wouldn't matter what language you coded your problem in. The optimal sequence of instructions computing a problem does not depend on the source language. But if we had this, then this compiler would compile every non-halting program into `while(0)`, which means we could detect non-halting programs, which is impossible.
4. For Turing Machines and the lambda calculus, I think it is fairly trivial to implement a lambda calculus interpreter for Turing Machines that is *asymptotically* equivalent to a universal Turing-machine. Big-O complexity isn't what people mean when they say "Functional languages are slow". Usually they are talking about constant overhead, which is very different. We don't have as good of ways to mathematically model this, so we usually just end up using experiments to measure precise performance.
> 8 votes

---
Tags: compilers, functional-programming, haskell, imperative-programming
---


# Question
Title: Randomly assign n elements to n agents such that each agent only knows its own element
### Problem

I'm working on an app that involves shuffling and distributing playing cards to players. As a challenge, I tried to solve this problem in a way that doesn't require a trusted intermediary.

In other terms, the task is to find a distributed algorithm that

* uniquely assigns $n$ agents numbers $1..n$
* allows each agent to know nothing about the assignment but its own
* when revealing the assignment, allows other players to verify the assignment

We also assume that knowing other's assignment is an advantage for each agent, and revealing its own prematurely a disadvantage. Agents are also assumed to be able to talk with each other in a way hidden from all other agents.

## Partial solution

The solution I came up with works only under the assumption that adversaries do not collaborate.

The idea is to create a set of $n$ nonces, and assign each agent exactly one nonce. The set is then passed from agent to agent in an agreed upon order, hidden from all others, until each agent received the set exactly once. Each time an agent receives the set, it swaps its nonce with a new one, memorizes the new nonce, and confirms receival of the set to the others. This entire procedure is done twice, at which point, all agents have received the set at least once after all other agents swapped their nonces, making it impossible to recognize and hence map the nonces to the other agents.

When the last agent receives the set the second time, it shares it with everyone, and all agents confirm to the others that their nonce is contained in the set. The agents then assign a number to each nonce in the set based on an agreed upon random seed, giving us the required unique assignment.

To allow ownership verification, instead of the nonces, agents put the hash value of their nonce on the set, revealing the actual nonce only when verification is required.

---

The problem with this solution is that if adversaries are allowed to collaborate, each time an adversary receives the set, they can compare their versions, identify changes and potentially derive which nonce belongs to other agents, allowing them to know what number got assigned to them.

All ideas are appreciated!

# Answer
> 2 votes
This problem is part of a set of problems known as Mental Poker.

There is an excellent and small article by Shamir, Rivest and Adleman that describe a practical way about how to implement such algorithm.

The abstract is gold:

> Can two potentially dishonest players play a fair game of poker without using any cards (e.g. over a phone)?
>
> This paper provides the following answers:
>
> 1. No. (Rigorous mathematical proof supplied.)
> 2. Yes.(Correct & complete protocol given.)

Basically, from an information-theoretic point of view, playing such a game is impossible without a trusted third party, but it is feasible to design a protocol using well-known hard to reverse cryptographic functions.

---

The algorithm will work as following:

Suppose you have $n$ nonces (numbers from $1$ to $n$). Each participant in the protocol has access to secret functions $e\_i$ and $d\_i$ which are used to encrypt and decrypt data. This functions should satisfy few properties, which we will analyze later.

The first participant is given the full set of nonces. It encrypts each nonce with its secret function $e\_1$, shuffles them randomly, and passes the resulting data to second participant.

Second participant will do the same, but in this case it doesn't have nonces, but a random permutation of the encrypted nonces. It will also encrypt each element with its own secret function $e\_2$ and shuffle the data again.

Then third participant, and so on, until all participants have shuffled and encrypted the data with its secret function.

Overall the setup process is:

```
data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

```

After this setup, each element of `data` are the nonces encrypted with all secret functions $e\_i$ in a random order unknown to any participant.

Notice that at this point is impossible for each participant to deduce each nonce without the help of other participants. And it is enough that one of the participants to shuffle the data completely random to remove any possible bias in the resulting order, independently if some malicious participant tries to bias the order.

Participant $i$-th is assigned the nonce at position $i$. To recover such nonce, participant $i$ asks each other participant $j \neq i$ to decrypt the value with its secret function $d\_j$ in turns. At the end participant $i$ will have its nonce only encrypted with its own secret function $e\_i$ so it can recover it using $d\_i$.

Recovering nonce $i$:

```
nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

```

At the end of this procedure each participant knows its own nonce, but no other participant know anything about it.

After using this values for your current problem a player can claim they are really in control of such nonce, by either publishing the secrets functions $e\_i$ and $d\_i$, so everyone can compute locally all the values, or decrypting the value `data[i]` after the first step but before the second step, publishing and then using this value as the input in the second step to fully decrypt it.

The functions $e\_i$ and $d\_i$ should have the following properties:

1. $e\_i(x)$ is the encrypted version of a message $x$ under key $i$,
2. $d\_i(e\_i(x)) = x$ for all messages $x$ and keys $i$,
3. $e\_i(e\_j(x)) = e\_j(e\_i(x))$ for all messages $x$ and keys $i$ and $j$,
4. Given $x$ and $e\_i(x)$ it is computationally impossible for a cryptanalyst to derive $i$, for all $x$ and $i$,
5. Given any messages $x$ and $y$, it is computationally impossible to find keys $i$ and $j$ such that $e\_i(x) = e\_j(y)$.

As stated in the paper, most of this assumptions are somehow common except for property 3), which tells the encryption functions must commute.

They propose a simple encryption scheme that satisfies these properties. Let's say all participants agree on some large prime number $P$ (it is ok if it fixed in the protocol). And each participant secretly choose a random number $k\_i$ such that $gcd(k\_i, P - 1) = 1$. Let's say $q\_i$ is such value that $k\_i \cdot q\_i \equiv 1 \mod(P -1)$. Then participant $i$ can use secret functions:

$$e\_i(x) = x^{k\_i} \mod(P)$$ $$d\_i(y) = y^{q\_i} \mod(P)$$

Some caveats about this algorithm: Participants can't cheat in such a way that colluding benefits them in learning the nonce about the other peer (unless of course $n-1$ participants collude, and only one nonce is remaining). However, malicious participants can attack the protocol by no participating, effectively stalling the dealing process, since a lot of actions are required from each participants while they are dealing the nonces. They can also produce gibberish, but this can be mitigated extending the protocol to detect which participant was the culprit and penalizing such participant at a higher level.

---

I implemented this algorithm for a poker game in NEAR blockchain. You can see the code in rust here. Notice there isn't any trusted third party in a blockchain, but there is a trusted computing environment which all participants can use as a mechanism to run this protocol.

---
Tags: distributed-systems
---


title: Can $n = O(n^2)$?

text:
# Question
Title: Can $n = O(n^2)$?
I'm reading Data Structures and Algorithms by Goodrich. The explanation that he gives for Big Oh notation is given below:

> Let $f(n)$ and $g(n)$ be functions mapping positive integers to positive real numbers. We say that $f(n)$ is $O(g(n))$ if there is a real constant $c \> 0$ and integer constant $n\_0\geq1$ such that $|f(n)| \leq cg(n)$, for $n\geq n\_0$. This definition is referred to as the "big-oh" notation, and is sometimes pronounced as "$f(n)$ is big-oh of $g(n)$".

If I understood this definition right, it would mean that I can say; for a function $f(n) = n$ then $n$ is big-oh of $n^2$ because $n \leq 1\cdot n^2$ for any $n\_0$. But, that is not accurate because big-oh notation for a function '$n$' is $O(n)$. What am I missing here? Would it be accurate for me to say that '$n$' is big-oh of $n^2$?

# Answer
The statement $n = O(n^2)$ is true. There is nothing wrong with it. Maybe you're thinking of the Theta notation.
> 1 votes

# Answer
Firstly let me bring little more exactness. In sentence

> If I understood this definition right, it would mean that I can say; for a function $f(n) = n$ then $n$ is big-oh of $n^2$ because $n \leq 1\cdot n^2$ for any $n\_0$.

is used "any $n\_0$", but in definition of $O$ we have $\exists n\_0$ \- existence is essential.

To clear your doubts, hope, will be helpful, if you look at $O(n)$ as set of functions. $O(n^2)$ is also set of functions, but more wide. So $O(n) \subset O(n^2)$. And of course as $f(n)=n \in O(n)$, then also $f(n)=n \in O(n^2)$.

By the way, we can say, than for any $k\geqslant 2, k \in \mathbb{N}$ is true $f(n)=n \in O(n^k)$, but this is not more accurate in sense, that we went to more wide set of functions $O(n) \subset O(n^k)$. Most accurate for $n$, in this sense, is $O(n)$.
> 1 votes

---
Tags: algorithms, asymptotics, big-o-notation
---


# Question
Title: How to calculate the runtime of a following code?
Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code?

```
for (int i=0; i<list.length; i++) {
    for (int j=0; j<list.length; j++) {
        for (int k=0; k<list.length; k++) {
            if (k%2==0) {
               list[i] += list[j];
            } else {
               list[i] += list[k];
            }
       }
   }
}

```

From my understanding, I'm thinking it's something like O(n^3) because the statement is executive n times for every i?

# Answer
If I understand correctly, that you denote $n$=list.length and are calculating amount of "list\[i\] +=" operation. Then of course, as it is triple loop, then for $n$ times fixed "i" from first loop you take $n$ times "j" from second loop and $n$ times "k" from most inner, third, loop. So operation "list\[i\] +=" will be fulfilled exactly $n^3$ times. Now knowing, that $n^3 \in O(n^3)$ you can state that complexity for whole snippet is $O(n^3)$ .
> 1 votes

---
Tags: runtime-analysis, big-o-notation, java
---


# Question
Title: Sum rule for Big-O with equal complexity-functions?
One property of the Big-O-notation is the sum rule, which states that when I have two functions $f\_1$ and $f\_2$ and their corresponding complexity functions are $g\_1$ and $g\_2$, then the combined complexity is $f\_1 + f\_2 = O(\max(g\_1, g\_2))$.

But what do we pick if both complexity-functions are equal? E.g., if $f\_1(n)$ is the sorting of an array and $\_f2(m)$ as well, then the complexities are $O(n\log(n))$ and $O(m\log(m))$. Applying the rule would be $O(\max(n\log(n), m\log(m)))$. I think that picking any of those would yield a valid but very unintuitive estimation as you would drop one variable. Besides that, it's not clear which one to pick.

Is it the case that you are not supposed to use the rule when there are multiple variables involved?

# Answer
It depends on if some variables on dependent on another, or if they are given as parameters in the problem. For example, in many graph-related problems, $n$ can be the number of vertices, and $m$ can be the number of edges. In this case, $m$ can be as large as $O(n^2)$. So in the general case, say if we have an algorithm whose first phase runs in $O(n)$ and second phase runs in $O(m)$, we just add the two terms together and do not attempt to simplify --- the final runtime is $O(n+m)$.

In terms of several variables given as parameters that aren't necessarily related: eaving multiple variables inside the final equation is standard, e.g. I can say that multiplying an $m\times n$ matrix and an $n\times p$ matrix takes $O(mnp)$-time using schoolbook multiplication, or solving the knapsack problem takes $O(nt)$-time where $n$ is the number of items and $t$ is the target sum.

In special cases like planar graphs and other sparse graphs, we know that $m=O(n)$, so we can safely substitute $n$ in place of $m$ in the final running time for simplification.

As a digression, this illustrates why on sparse graphs (where $m=O(n)$) one would prefer to use Dijktra's in a loop for all-pairs shortest path (in contrast to a transitive-closure based algorithm like Floyd-Warshall); since now Dijkstra runs in $O(m \log n) = O(n \log n)$, the overall complexity for using Dijkstra's in a loop becomes $O(n^2 \log n)$, which is better than Floyd-Warshall. By contrast, note that Dijkstra's runs in $m \log n$ for the general case, which means on dense graphs where $m=O(n^2)$, it becomes less efficient than Floyd-Warshall in terms of worst-case running time.

In other cases, there can be variables aren't even polynomially bounded by a given parameter --- take the knapsack example above, where $t$ can be exponential in $n$.
> 3 votes

# Answer
There is no general answer. By the way, if you want to simplify the $O(\max(n\log(n), m\log(m)))$, you can rewrite it as as $O((n+m) \log(n+m))$.

Moreover, if $g\_1$ and $g\_2$ are eqaul and increasing functions, you can write $O(g\_1(n+m))$ instead of $O(\max(g\_1(n), g\_2(m)))$.
> 1 votes

# Answer
By definition $O(g)$ should be always defined variable and limit point with respect to is considering $O$. For example in $O(n^3), n \to \infty$ variable is $n$ and limit point $\infty$. In $O(x^3), x \to 0$ variable is $x$ and limit point $0$.

So when we write $f=O(g)$, then formally we mean some variable and some limit point. For example $f(n)=O(g(n)), n \to \infty$ is exact record. Note, that record $f(m)=O(g(m)), m \to \infty$ means exactly same as previous sentence.

When we are speaking about property $f\_1 + f\_2 = O(\max(g\_1, g\_2))$, then here also should be stated some variable(s) and some limit point. So exact record should be something like $$f\_1(n) + f\_2(n) = O(\max(g\_1, g\_2)(n)), n \to \infty$$ Or we need more clarification with respect to variables, assuming limit point $\infty$.
> 0 votes

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


# Question
Title: How to draw the heap for an array in Java?
I have an assignment to draw the heap after an ArrayList and a LinkedList is created.

```
public static void main(String[] args) {
     List list = new ArrayList();
     list.add(0);
     list.add(1);
     list.add(1);
     list.add(2);
}

```

and

```
public static void main(String[] args) {
     List list = new LinkedList();
    list.add(0);
     list.add(1);
     list.add(1);
     list.add(2);
}

```

So far I have a tree set up for \[0, 1, 1, 2\] so that it just goes down like a tree from 0, 1 and 1, then 2. But I don't know if that's correct and if it'd be different for the ArrayList and LinkedList.

# Answer
Heap is an almost complete binary tree. So if you're planning to construct the tree you can just start by filling the values in the tree from top to down and left to right ie, proceed by filling nodes levelwise.

Arraylist or linked list doesn't matter here because both stored the level order traversal of the tree.

Ex. list.add(0), list.add(1), list.add(1), list.add(2), list.add(3), list.add(5)

```
                              0
                            /    \
                           1      1
                           / \     /
                         2   3  5

```
> 0 votes

---
Tags: binary-trees, heaps, stacks, java
---


# Question
Title: How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?
A semaphore is a variable that, apart from initialization is accessed through only two standard atomic operations wait(s) and signal(s).

```
wait(S){
    while S <= 0
    ; //no-op
    s--;
}

signal(S){
    s++;
}

```

The function $wait()$ is an atomic operation which means that either it is executed in its entirety or it is not executed. Let us suppose that we call $wait(a)$ upon a semaphore variable $a$. And let us assume the initial value is $0$. This means the criterion for the while loop is satisfied and it goes into a while loop. It can only come out of the while loop if the value of the semaphore $a$ is $\gt$ 0. This can occur, if some process sets the value of $a$ to $1$ by calling $signal(a)$. But since $wait()$ and $signal()$ are atomic operations and since we have already entered into the busy waiting while loop in $wait()$ when the value of $a$ was $0$, isn't this loop supposed to run indefinitely since its atomic? How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?

# Answer
> 2 votes
Your assertion that `wait()` and `signal()` are atomic is incorrect. The increment/decrement to `s` within the functions (`s++`, `s--`), are what's atomic.

That being said, what you have given here is only one possible *implementation* of a semaphore. An OS may or may not implement semaphores in this way, and they probably will choose a more efficient implementation. What's more important is to grasp the semantics of a semaphore, which you seem to understand correctly.

# Answer
> 1 votes
Semaphore do not work the way you have described. They are more like shared variables. So even inside the loop S can get modifies and the first process will come out of the loop. Note it is not same as while(1){}; .

# Answer
> 0 votes
The definition of `wait()` as given by you is very simplest. The checking of value of `S` (`S<=0`) and its possible modification (`S--`) must be performed without interruption. If you write `wait()` function as you have written here then, when a process has found that `S>0` and it is going to modify `S` (`S--`) then it can stop between checking value of `S` (`S<=0`) and its possible modification (`S--`). If this happens mutual exclusion will not be satisfied. Also, if a process finds that `S<=0`, it has to simply busy wait and other process should be allowed to enter `signal()` and increment `S`. You will need to add few lines in your code to handle such situations.

---
Tags: operating-systems, concurrency
---


# Question
Title: Can we improve internet speed by serializing timestamps?
If we (scientists) came up with a way of representing numerical timestamps as letters hence reducing the number of bytes needed to represent timestamps, would that mean an improvement in internet speed as less data needs to be serialized?

# Answer
> 4 votes
If we restrict ourselves to the 52 letters from the Latin alphabet that are commonly used in English (i.e. we exclude letters like *ï* as seen in words like *naïve*), then we need 6 bits to encode each letter.

However, in 6 bits, we can encode *64* different numbers.

That means our encoding using letters is only 81.25% as dense as the encoding using numbers.

This is actually the *best case* scenario. Most protocols are octet-oriented, so we have to pad our representation to a full octet boundary. That means that a single letter will be encoded in 8 bits. A single letter can express 52 timestamps, but 8 bits can express 256 numbers.

We could try to find an alphabet with 64 letters (or even better 256 letters), then the representation using letters would be as good as the representation using numbers … but why go through all the trouble of representing timestamps (which, after all, *are* numbers) as letters, then at the other side of the transmission turn them back into numbers again when simply representing them as numbers is in the worst case just as efficient as when using letters and in the best and average case is significantly more efficient?

After all, computers and networks can only process and transport numbers, so whatever representation using letters you find, you will have to represent *that* representation using numbers again, and this representation *cannot be* more efficient than the original one.

Basically, you start off with a timestamp, which is a number, you need to end with a timestamp at the other end, which is a number, and the network can only transport numbers.

Your proposal looks like this:

1. Encode the number as letters
2. Encode the letters as a number
3. Transmit the number
4. Decode the number as letters
5. Decode the letter as a number

Whereas what we are doing today is:

1. Transmit the number

Which is more efficient.

# Answer
> 2 votes
No, because we already know how to represent timestamps (or any other data) in a variety of ways: in binary, in hex, in base64. Probably only a miniscule fraction of all Internet data is timestamps, so reducing the number of bytes used to transmit timestamps will make only a miniscule difference on overall Internet speed.

---
Tags: computer-networks
---


# Question
Title: Intuitive explanation on why stochastic encoding performs better in channel coding
I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can achieve nearly 0 probability of error when using $O( \log \log M)$ bits, where $M$ is the total number of messages. Instead, deterministic encoding would require us to use at least $O(\log M)$ bits instead.

Can anyone give an intuitive explanation of why stochastic encoding is so effective? One possible idea which opposes the result is that the stochastic code would result in many possible codes for a single message which should make it more difficult for the decoder as the codes are now more 'tightly packed', i.e., there are many more valid codes possible for the same number of bits transmitted.

# Answer
Well, I think you are conflating two things. It is correct that in a lot of settings probabilistic encoding (e.g., Polar Codes, Convolutional Codes, LDPC Codes) \[assuming you know a good model for the noise process of the channel\] does much better than algebraic coding, intuitively because channels have memory and block codes ignore that memory.

However, Ahlswede's Identification Problem is quite different. It is NOT a traditional channel coding problem There is a good review here

The author states

> In the problem of identification via channels, introduced by Ahlswede and Dueck the receiver is **only interested in testing whether a particular message was sent, but the encoder does not know which message the decoder wants**. Errors are now considered in terms of false alarm and missed identification. It turns out that for this case, one can design systems such that the number of different messages one can identify grows **doubly exponentially with the blocklength**. The trick is that each message can map into a list of codewords and the encoder selects one randomly. As long as the fraction of the pairwise overlap of these lists is small, the error probabilities will be small
> 0 votes

---
Tags: information-theory, coding-theory, encoding-scheme
---


# Question
Title: If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?
I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we call it a contradiction and declare the language is not context free or do we say there is no contradiction?

If its the former, it will declare (a)^n(b)^n as non-context free using Pumping Lemma even though we know its a context free language, since some of the cases will not obey the 3 conditions at the same time.

Edit:

By cases, I mean v and y's existence in different parts of the string. In a string `aaaaabbbbb`, either v or y could fully be in `a`, partially be in `a and b` or fully be in `b`. ( Assuming you break the string into S = uvxyz where v and y are the repeating pieces)

# Answer
This is a common question regarding pumping lemmas, and it is completely answered by carefully understanding the quantifiers in the lemma.

The lemma itself says the following:

> For every CFL $L$, there exists a constant $p$ such that for every word $w\in L$, if $|w|\>p$, then there exist words $u,v,x,y,z$ such that $w=uvxyz$, and (1) $|vxy|\le p$, (2) $|vy|\ge 1$, (3) for every $i\ge 0$, $uv^ixy^iz\in L$.

Now, the typical usage of the lemma is by contradiction, so we have a language $L$ which we suspect to be not a CFL, and we show the negation of the lemma (read this carefully, and see how we negate the formulation of the lemma):

> For every constant $p$, there exists a word $w\in L$ with $|w|\>p$, such that for every decomposition $w=uvxyz$, if (1) and (2) hold, then there exists $i\ge 0$ such that $uv^ixy^iz\notin L$.

As you can see, in order to apply the lemma, we can choose the word $w$, but we are given $u,v,x,y,z$. Then, we assume that cases (1) and (2) hold, and deduce that (3) doesn't hold. It is really important to understand which elements we can choose, and which we need to be given without choice. These correspond to existential/universal quantification.
> 1 votes

---
Tags: automata, context-free, pumping-lemma
---


title: "pure" explanation of Reed-Solomon?

text:
# Question
Title: "pure" explanation of Reed-Solomon?
I encountered two applications of RS codes - one in group testing, and another time someone said that a solution to an interview question was using it. But when I search for explanations, it's all about the cracks in the CD disks and such. Is there a good source that puts the math first?

# Answer
Jon Hall's coding theory notes, available online here are quite good. See Chapter 5.

In addition, see Blahut's text *Algebraic Codes for Data Transmission* where more focus on decoding algorithms is present.
> 1 votes

---
Tags: coding-theory
---


# Question
Title: How can I efficiently construct a CFG from a language
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n \<= m + 3}.

So m can be infinitely bigger than n but n can only be up to 3 more bigger than m and they can be the same. I have no idea how to make a CFG for this.

What I came up with was:

```
S -> AB | _
A -> a | aa | aaa | C | _
C -> aC | a | _
B -> bB | b | _

```

But I think this is not even close...

Any help/tips/advice would be much appreciated!

# Answer
> 2 votes
The best way is to learn is to look at examples, and see how they work.

One of the simplest "real" context-free languages is $\\{\\; a^mb^n \mid n = m \\;\\}$

Its grammar is $S\to aSb\mid \varepsilon$.

Now add in steps, the extra 3, and the more than ...

$\\{\\; a^mb^n \mid n = m+3 \\;\\}$

$\\{\\; a^mb^n \mid n \le m+3 \\;\\}$

# Answer
> 1 votes
I'll explain my thought process behind thinking about this problem here:

-\> With inequalities, I first think at the equality constraint. So I assume n = m+3

-\> Now, n is always 3 more than m.

-\> I split the problem further. I think to myself okay, let's have one production handle equal production of a and b.

-\> How many more b's do we need after this? ( 3! )

-\> I include that in the start symbol.

-\> To end it, I know, n = m+3 is not a hard rule. It is \<= . So, I make another production that produces infinite number of B's.

Grammar:

```
S -> Abbb
A -> aAb | B
B -> bB | e   ( e is lambda or epsilon )

```

---
Tags: regular-languages, automata, finite-automata, context-free, pushdown-automata
---


# Question
Title: Time complexity of pairs in array double loop
I know, that the following is: **O(n^2)**,

```
int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

```

But, should something like `count = count + 1;` be taken into account? For predicting or making up a complex time equation, or using sum notation,

```
n + n-1 + n-2 + n-3 + (…) + 1

```

# Answer
> 2 votes
It's well known task "Checking for Duplicates" and you can found it for example in Tim Roughgarden - Algorithms Illuminated\_ Part 1\_ The Basics-(2017) 42 page. Let me say, that as here so in book taking last index "i" as $n=$"array.length()" have no sense, because then index "j" runs out of borders. But this do not affect our counting.

As always main is to choose operation for count - here its "count = count + 1". Obviously best case, i.e. least amount of operations, is $0$. And worse case, i.e. maximal amount of operations, is sum (I correct it accordingly taking index "i" up $n-1$) brought by you $T(n)=1+2+\cdots+(n-1)=\frac{n(n-1)}{2}$ (we consider case $n\geqslant 2$).

Now, because $\frac{n(n-1)}{2} \leqslant \frac{n\cdot 2n}{2}=n^2$, it's easy to conclude, that worse case $T(n) \in O(n^2)$.

# Answer
> 2 votes
The time complexity of an algorithm depends on the model of computation. Algorithms are usually analyzed in the RAM machine, in which basic operations on machine words (such as assignment, arithmetic and comparison) cost $O(1)$. A machine word has length $O(\log n)$, where $n$ is the size of the input.

In your case, the size of the input is at least $n$ (defined to be the length of `array`), and so `count` fits in a single machine word. Each of the basic operations in the algorithm cost $O(1)$, and so the overall time complexity is $\Theta(n^2)$, since the algorithm executes this many basic operations.

---
Tags: time-complexity, asymptotics, big-o-notation
---


# Question
Title: Course teaching time complexities in real life systems
Having mis-read What course in CS deals with the study of RAM, CPU, Storage? I now wonder what course in CS deals with time and space complexities including GPUs, CPU caches in multiple levels, seek times on hard disk vs. SSDs, and bandwidth to disk and RAM.

I was taught the big O-notation but it never took into account that I might have a GPU with 100s of cores, or a limited amount of extremely fast cache, or a harddisk that is has a high bandwidth, but a high seek time.

Which class teaches this extended version of algorithm time complexities, which takes real world limitations into account?

# Answer
I don't think these things are usually treated as a single topic in either research or education, but there are quite a few adjacent topics that are relevant. I'll list some here, starting with...

## I/O-complexity

One perspective on the algorithmic analysis of computer storage, memory and caches is the field of I/O-complexity or external memory algorithms. These lecture notes from a course by Mark de Berg are a good introduction (in Part II). Note that this perspective assumes an abstract I/O model that has a two layer memory hierarchy (a small and fast internal memory and a big but slow external memory), which of course is a simplified version of what a modern computer has. Still, this perspective makes it possible to design efficient algorithms for dealing with massive data (think running an algorithm on an array/matrix a few ten GB big, or more!).

Another advantage of treating "external memory" only in the abstract means that we only need to design one algorithm to deal with both SSD's, hard-disks, or even a slow internet connection, as long as we are satisfied with treating our external memory as a monolithic blob. There are many other tricks you may want to try in practice, but this is highly dependent on your specific machine or operating system.

## Operating Systems

Okay, but what if I really want to know how to use multiple cache layers, how to ensure seeking goes efficiently on my hard-disk, or how to play nice with my OS's paging? These topics (among others) are usually treated in a course called "Operating systems". Another aspect that frequently is the focus of such a course is concurrency (e.g. how does your OS manage to run all those processes "at the same time"? ), and dealing with multiple processes and threads programmatically. Some mild form of parallelism may also be covered.

## Parallelism

So, what about those 100s of computing cores? Making use of those things to compute efficiently is known as *parallelism* and courses with that word in their title are common. There are quite a few models there to use in the analysis of parallel algorithms, the PRAM model is common. Again, this is an abstract model that may or may not allow you to use the full power of your expensive GPU (or arrays of relative cost-efficient Sony Playstation 3 cores. Cryptanalystist are a rare breed of "mostly theoretical" computer scientists that actually have use of massive computation power, see these slides of Dan Bernstein on some thoughts of using GPU's for crypto).

However, unless you have a very extreme needs for high performance computing, "using GPUs" in practice usually means using one of the APIs/frameworks designed to use them, like OpenGL. There are courses called *computer graphics* or something similar that teach how to work with these APIs.

Speaking of high performance computing, this is a field of its own, a bit on the intersection of parallel and distributed computing. (see also this answer for the difference between distributed computing, concurrency, and parallelism)

I should also mention that there are also courses on *databases* that go beyond just teaching how to use them and also teach how all those operations are implemented efficiently.

## But nobody will teach you *this one simple trick*!

We've already covered quite some courses, certainly enough to fill a few semesters, but you may have already gathered from the multiple caveats above that there's always a manner of *tricks* that simply depend too much on the specifics of your setup that there's no good reason to teach it, or do theoretical research on. Still, having the knowledge of the courses above at least should give you a good idea on when it might be a good idea to depend on some strange trick, or whether there actually is a well-understood way to solve your problem. One interesting trick is to compress everything and make it fit in main memory. (see also the video explaining how their entire system works)
> 1 votes

---
Tags: algorithm-analysis, computer-architecture, storage
---


# Question
Title: Independent sets into which all the vertices of the graph can be split
How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?

# Answer
This is Mirsky's theorem, a sort of dual of Dilworth's theorem. Dilworth's theorem is a standard result in the combinatorics of posets.
> 1 votes

---
Tags: algorithms, graphs, matching
---


# Question
Title: What does a kernel of size n,n^2 ,... mean?
So according to Wikipedia,

> In the Notation of \[Flum and Grohe (2006)\], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^\*$ and a function $\kappa:\Sigma^\*\to N$, the parameterization. The ''parameter'' of an instance $x$ is the number $\kappa(x)$. A '''kernelization''' for a parameterized problem $L$ is an algorithm that takes an instance $x$ with parameter $k$ and maps it in polynomial time to an instance $y$ such that
>
> * $x$ is in $L$ if and only if $y$ is in $L$ and
> * the size of $y$ is bounded by a computable function $f$ in $k$. Note that in this notation, the bound on the size of $y$ implies that the parameter of $y$ is also bounded by a function in $k$.
>
> The function $f$ is often referred to as the size of the kernel. If $f=k^{O(1)}$, it is said that $L$ admits a polynomial kernel. Similarly, for $f={O(k)}$, the problem admits linear kernel. '''

Stupid question, but since the parameter can be anything can't you just define the parameter to be really large and then you always have linear kernel?

# Answer
> 1 votes
The point of investigating a parametrized problem is that we hope or assume that the parameter will be fairly small or even bounded by a known small constant in some particular case you encounter in practice. In that case, algorithms with FPT could be called efficient.

So yes, you can definitely pick an arbitrary parameter that will be very large in practice, but then a linear kernel will probably not be useful, because you are measuring the wrong parameter.

As a side remark, this is not something specific to parametrized complexity. In any type of complexity, you must be careful that the thing your are investigating the complexity of is actually meaningful.

---
Tags: complexity-theory, decision-problem, parameterized-complexity
---


# Question
Title: What course in CS deals with the study of RAM, CPU, Storage?
I watched the Crash Course playlist of Computer Science. It was teaching about RAM, CPU, Storage etc but I felt it was way too fast and only people who have studied the course first hand understood it better.

So I wanted to ask what CS couse actually teaches the details of CPU, RAM and how it is build from the scratch with the help of Logic Gates.

# Answer
> 16 votes
The subject you're describing often goes under the names *computer architecture*, *computer systems*, *computer organization and design*, and the like. One example is Elements of computing systems, based on a course From Nand to Tetris originating in the Hebrew University. The Amazon page on the book links to other popular textbooks on the topic.

Generally speaking, this area is at the intersection of computer science and electrical engineering. Some aspects are much closer in spirit to electrical engineering, for example the physics behind memory and storage architectures. Other aspects, such as cache coherence algorithms and error-correcting codes, are more likely to be considered an integral part of both disciplines.

# Answer
> -1 votes
The basic concepts without gates goes under Operating Systems course, and with gates, clocks etc. goes under Digital Logic Design or (mostly) Microprocessors as I experienced.

---
Tags: cpu, memory-allocation, storage
---


# Question
Title: Populating a vector of numbers to expose an error in a function implementation
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect on specific inputs. In fact I might do this for all vector sizes under a certain size, but I would never enumerate all possible values, just all possible vector sizes.

It occurs to me however that it might be possible to populate the values of the vector such that I can still verify every possible vector under a certain size as long as I make a certain assumption about the implementation of the function under test.

Say I have a function $f : \mathbb{N}^n \to \mathbb{N}$ such that $f(x) = \sum\_{i=1}^nc\_i\prod\_{j=1}^n x\_j^{e\_{ij}}$ for some $e$ and $c$ such that $e\_{ij} \in \\{0,1\\}$ and $c\_i \in \\{0, 1\\}$. I want to see if this is equal to some known golden function $g$ but I'll have to manually work out $g$ for specific inputs. I belive it to be true that there exists an input $r$ such that $f(r)$ uniquely determines $f$. This makes testing to see if a particularly implementation of $f$ is the one we expect trivially easy.

for $n = 2$ the possible values of $f(3, 7)$ are the following: 0, 1, x = 3, y = 7, xy = 21, 2, 1+x = 4, 1+y = 8, 1+xy = 22, x+x = 6, x+y = 10, x+xy = 24, xy+xy = 42

So if I make the assumption that a partiuclar function I'm testing has the above from characterized by $c$ and $e$ then I only need one input to fully test an implementation of $f$.

A good heuristic for generating these inputs is to start with the first prime higher than the number of terms you have, and then try successively higher primes for each next input until you work out the few kinks that remain. The intuition is that no two products will be the same because you chose primes and that each unique product will be spaced out by so much eventually that the sums will also all be unique as well.

Is there an algorithm to generate an input to such a function that makes all possible such functions result in unique values? What if we're willing to be probabilistic in some sense such as "the expected output is *probably* unique for this input"? Are there other forms of functions for which this question has been studied?

# Answer
> 1 votes
## Multilinear polynomials

If you're willing to use probabilistic methods, I suggest using a randomized algorithm for polynomial identity testing.

You want to test whether $f(x)=g(x)$ holds for all $x$, where $f,g$ are multilinear oolynomials. This is an instance of the polynomial identity testing problem. There are effective randomized algorithms for polynomial identity testing.

To make this answer self-contained, I'll give you a brief overview of a reasonable algorithm. First, randomly pick a large prime $p$. Next, randomly pick $x=(x\_1,\dots,x\_n)$, with each element $x\_i$ chosen uniformly at random modulo $p$. Finally, check whether $p(x)\equiv g(x) \pmod p$. If no, then you know that your implementation is faulty. If yes, then your implementation has a good chance of being good. (In particular, a faulty implementation that computes some other multilinear polynomial has a low probability of going undetected, thanks to the Schwartz-Zipple lemma.) You can repeat this procedure multiple times for stronger guarantees.

This procedure assumes you can inspect the code of the algorithm and verify that it computes a multilinear polynomial, which seems to be something your question proposes that we can assume. If you have a complete black box and you have no knowledge whether it computes a multilinear polynomial or not, you can't get strong guarantees that $f$ will be correct everywhere: for instance, your implementation $f$ might be correct on all but one input where it is special-cased to outputs the wrong answer.

## More general cases

You might be interested in the theory of self-testing, pioneered by Blum, Luby, Rubinfeld and further developed by others. See, e.g., the following seminal paper:

Self-Testing/Correcting with Applications to Numerical Problems. Manual Blum, Michael Luby, Ronitt Rubinfeld. Journal of computer and system sciences, 47(3), 549-595.

They generalize your idea by considering testers that invoke the program-under-test multiple times; by allowing probabilistic tests, where there is a chance we fail to notice problems, but this probability can be controlled or bounded; and by allowing for self-correction, where we use the possibly-faulty program as a subroutine to construct an output that will be correct with high probability. Nonetheless, despite these generalizations, the class of functions that we know how to build efficient self-testers for is fairly limited, and we don't know how to do it for arbitrary functions.

---
Tags: combinatorics, discrete-mathematics, number-theory, probabilistic-algorithms, software-testing
---


# Question
Title: Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points
I’m attempting to write a heuristic for an implementation of A\* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a heuristic that does the following:

Given a set S containing N start coordinates and a set G containing N goal coordinates, calculate the minimum number of total unit translations of the start points required to move each start points to a goal point such that each goal point is covered. The difficulty is that it does not matter which goal point each start point ultimately lands on.

Here’s a 2d example: You're given a checkerboard with 8 pieces placed randomly on the board in locations specified in set S. G is defined as the set of 8 squares in the bottom row of the board (y=0). For each move, you're allowed to move one checker piece to an adjacent square. Calculate the minimum number of moves required to cover each spot in G with a piece.

I’ve played around with exhaustive solutions to this problem such as generating all the N! ways to arrange the pieces on the goal nodes and finding the distance for each, and I’ve also tried running a search algorithm to find the optimal paths, but these approaches seem too costly to be used as a good heuristic. It’s not so important that I’m able to calculated the actual correct minimum. If I could estimate it within a small margin of error and that error was relatively consistent regardless of the points in the two sets, that would be perfectly fine.

Is there a more efficient way to calculate this than the exhaustive method I tried? A more mathematical way? Or if not, is it possible to estimate it reliably?

# Answer
> 2 votes
How about:

1. Build a weighted complete bipartite graph where the left vertex set is $S$, the right vertex set is $G$, and the weight of the edge between $s \in S$ and $g \in G$ is the 3-D Manhattan distance from $s$ to $g$.
2. Solve the assignment problem for this graph.

This finds the exact minimum. It does unfortunately take about $O(n^3)$ for a typical network flow algorithm, though.

---
Tags: graphs, search-algorithms, heuristics, group-theory
---


# Question
Title: Lambda calculus simplification excercise
Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem.

(λx.λy.yx)z (λw.w) I am lost with this.

if anyone could lead me in the right direction that would be much appreciated

# Answer
It is better to remind ourselves the Lambda calculus precedence rules first. See https://stackoverflow.com/q/4794330/9939883 for better details about precedence.

Application has higher precedence than Abstraction. Application is left associateive and Abstraction is right associative.

```
(λx.λy.y x) z (λw.w)

```

Since application has higher precedence,

```
(λx.λy.(y x)) z (λw.w)

```

Since application is left associative

```
= ((λx.λy.(y x)) z) (λw.w)

```

Applying repeated abstractions

```
= (λy.(y z)) (λw.w)

= (λw.w) z

= z

```
> 3 votes

---
Tags: logic, lambda-calculus
---


title: Maximal vs maximum matchings

text:
# Question
Title: Maximal vs maximum matchings
Let $M\_1$ be an inclusion-maximal matching in $G$ (that is, there is no matching which strictly contains it), and $M\_2$ a maximum-size matching in $G$. How to prove that $|M\_2| \le 2|M\_1|$?

# Answer
Since $M\_1$ is maximal, every edge in $M\_2$ must share a vertex with an edge of $M\_1$. You take it from here.
> 0 votes

---
Tags: algorithms, graphs, matching
---


# Question
Title: Why is it hard to show that the euclidean Steiner tree problem is in NP?
I read that for the euclidean Steiner tree problem it is known that it is NP-hard, but not known whether it is in NP or not. \[Wikipedia\]

Shouldn't the euclidean version obviously be in NP since the metric Steiner tree problem is in NP and a non-deterministic TM that decides the metric Steiner tree problem could also decide the Euclidean Steiner tree problem? Or am I missing something that could make the Euclidean version inherently more difficult/different?

# Answer
> 3 votes
I'm guessing the difficulty lies in the fact that euclidean distance is involved, and we don't know if comparing sums of integrer square roots is in NP.

The problem is the following: for integers $a\_1, \ldots a\_n$ and $b\_1, \ldots b\_m$, is $\sum\sqrt{a\_i} \< \sum\sqrt{b\_j}$?

This is not known to be in NP and is a major barrier in adapting a lot of computational geometry algorithms from the Real-RAM model to Word-RAM.

---
Tags: complexity-theory, minimum-spanning-tree, euclidean-distance
---


# Question
Title: $f(x) = \sqrt{x^{2}+1}-1$ (Loss of Significance)
Let us say that I want to compute $f(x) = \sqrt{x^{2}+1}-1$ for small values of $x$ in a Marc-32 architecture. I can avoid loss of significance by rewriting the function

$$f(x)=\left(\sqrt{x^{2}+1}-1\right)\left(\frac{\sqrt{x^{2}+1}+1}{\sqrt{x^{2}+1}+1}\right)=\frac{x^{2}}{\sqrt{x^{2}+1}+1}$$

Even though I can solve the problem, I do not know/understand why the solution has avoid the loss of significance?

# Answer
Assume that due to rounding errors, when you try to calculate the square root of $x^2 + 1$ you actually get the square root plus $\epsilon$ for some small $\epsilon$. Assume that $\epsilon = 10^{-10}$ and $x = 10^{-6}$. Perform the calculations and write down the results.
> 1 votes

---
Tags: numerical-algorithms, error-estimation
---


# Question
Title: Finding the most frequent element assuming $\Theta(n)$ frequency
We know \[Ben-Or 1983\] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(n \log(n))$ time to find the most frequent element (assuming the domain of the array elements is not small).

But what happens when you know that there's an element with frequency at least $\alpha \cdot n$? Can you then decide the problem, or determine what the element is, in linear time (in $n$, not necessarily in $1/\alpha$) and deterministically?

# Answer
Here is an algorithm for all $0\<\alpha\leq 1$. I'm assuming your data can be ordered and that comparing two elements is done in constant time.

Run a few levels of the quick-sort recursion (choosing the pivot optimally in linear time with the Median of Medians algorithm) until you have partitioned the elements into "buckets" $B\_1,\ldots, B\_m$ each of size $\frac{\alpha n}{4} \leq |B\_i| \leq \frac{\alpha n}{2}$, where all elements in $B\_i$ are smaller or equal to all elements in $B\_{i+1}$. This will take $O(n\log(1/\alpha))$ time.

Now notice that because the relative majority element $e$ is present at least $\alpha n$ times and each bucket has at most $\frac{\alpha n}{2}$ elements, the majority element needs to fill at least one of the buckets completely. Thus $e$ is also the first element in some bucket.

Notice also that there are at most $4/\alpha$ buckets as each bucket contains at least $\frac{\alpha n}{4}$ elements. Thus you can pick the first element in each bucket, and choose the element with maximum frequency among those in $O(n/\alpha)$ time.

Thus, you can find that relative majority element $e$ in $O(n\log(1/\alpha) + n/\alpha) = O(n/\alpha)$ time.
> 2 votes

# Answer
Very partial answer: At least for $\alpha \> 0.5$, yes.

1. $\text{candidate}$ \<- (null value), $\text{count}$ \<- 0
2. For each element $x$ in the array

1. If $x = \text{candidate}$ then

    1. increment $\text{count}$
    2. else

    1. If $\text{count} = 0$

        1. $\text{candidate} \leftarrow x$, $\text{count} \leftarrow 1$
        2. else

        1. decrement $\text{count}$

The candidate remaining at the end of the array is the majority element. A potential-function argument can show this to be the case (I was taught this in a teaser for an online algorithms class).

This can be extended to $\alpha = 0.5$ by first finding two distinct elements of the array, then running the above on the array without one of them, then on the array without the other, then finally checking the frequency of the values you get from those two runs.

But - such a trick will probably not work for lower $alpha$ values.
> 0 votes

---
Tags: algorithms, arrays, space-complexity, linear-complexity
---


title: Bible Verse division

text:
# Question
Title: Bible Verse division
I'm working on a project compiling various versions of the Bible into a dataset. For the most part versions separate verses discreetly. In some versions, however, verses are combined. Instead of verse 16, the marker will say 16-18. I wonder if, given I have a lot of other versions that separate them discretely, I can train an NLP model to separate those combined verses into discrete verses. I'm fairly new at deep learning, having done a few toy projects. I wonder how to think about this problem? What kind of problem is it? I think it might be similar to auto-punctuation problems and it seems the options there are seq2seq and classifier. This makes more sense to me as a classification problem, but maybe my inexperience is what drives me that direction. Can people suggest ways to think about this problem and resources I might use?

In answer to questions in the comment, I am dealing only with text, not images. An example might be like this:

Genesis 2, New Revised Standard Version:

> 5 when no plant of the field was yet in the earth and no herb of the field had yet sprung up—for the Lord God had not caused it to rain upon the earth, and there was no one to till the ground; 6 but a stream would rise from the earth, and water the whole face of the ground— 7 then the Lord God formed man from the dust of the ground, and breathed into his nostrils the breath of life; and the man became a living being.

Genesis 2, The message version:

> 5-7 At the time God made Earth and Heaven, before any grasses or shrubs had sprouted from the ground—God hadn’t yet sent rain on Earth, nor was there anyone around to work the ground (the whole Earth was watered by underground springs)—God formed Man out of dirt from the ground and blew into his nostrils the breath of life. The Man came alive—a living soul!

The goal then would be to divide the message version into discrete verses in the way that the NRSV is. Certainly, a part of the guide would be that a verse always ends in some kind of punctuation, though while necessary it is not sufficient to assign a distinct verse.

# Answer
In my opinion, this may be best approached as a sequence tagging problem, similar to part-of-speech tagging or named entity recognition. (So, this would be the seq2seq option, rather than regular classification). For example, think about it as trying to decide for each token, whether it is the start of a new verse or not.

The advantage of the sequence tagging approach compared to regular classification (at least when using some kind of neural architecture) is that you do not have to predetermine the length of the context taken into account for each distinct tagging decision.

To be clear, the classification approach (e.g, take 20 tokens to the left and 20 tokens to the right and decide whether the middle token is a verse boundary) is also viable, but the sequence tagging approach seems the more natural choice for me.

A final thought on the problem: Are you sure that (any kind of) classification/tagging approach is the right place to start? You may also want to think about this in terms of an alignment problem where you try to figure out which sentences from message edition correspondent to the ones in the NRSV version. Verse segmentation then comes for free. Alignment problems have been studied extensively in statistical machine translation.
> 2 votes

---
Tags: machine-learning, natural-language-processing, classification
---


title: Unsigned/signed boolean

text:
# Question
Title: Unsigned/signed boolean
Answer is c). I understand that the expression evaluates to true but what does signed/unsigned have to do with booleans?

# Answer
> 2 votes
It means your book is either (a) misleading, (b) poorly worded, or (c) wrong.

Case (a) would be if the text is talking about how relational operators are implemented in CPU architecture. In many if not all architectures, performing a compare instruction sets processor flags for the output of both the signed and unsigned comparison, and then conditional jump instructions can be used to branch to different code based on the values of the different flags. The processor flags are single bits and you don't perform arithmetic on them; asking whether the flags are signed or unsigned is meaningless.

Cases (b) and (c) are if the text is talking about a specific programming language. This would almost certainly have to be C, based on the syntax and talking about comparisons returning integers.

Case (b) would be if the text is asking whether the *arguments* of the comparison are signed or unsigned. In C, expressions that mix signed and unsigned generally convert the arguments to unsigned first, so the comparison being performed is on two unsigned values. But this is very poor question wording (even though I strongly suspect this was the author's actual intention).

Case (c) would be if the text is asking whether the *result* of the comparison is signed or unsigned. The result of a comparison in C is a *signed* int. C11 (ISO/IEC 9899:201x) §6.5.8 Relational operators says:

> Each of the operators \< (less than), \> (greater than), \<= (less than or equal to), and \>= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false. The result has type int.

---
Tags: computer-architecture, numeral-representations
---


title: Example of Dependent Types?

text:
# Question
Title: Example of Dependent Types?
Say you have 3 objects, a global `MemoryStore`, which has an array of `MemorySlabCache` objects, and each `MemorySlabCache` has an array of `MemorySlab` objects. *Sort of* like this:

```
class MemoryStore {
  caches: Array<MemorySlabCache> = []
}

class MemorySlabCache {
  size: Integer
  slabs: Array<MemorySlab> = []
}

class MemorySlab {

}

```

But the thing is, this doesn't capture everything. It also needs to capture the fact that each `MemorySlabCache` has a size, which is used to tell what size the `MemorySlab` objects are it contains. So it's *more* like this:

```
class MemoryStore {
  caches: Array<MemorySlabCache> = []
}

class MemorySlabCache {
  size: Integer
  slabs: Array<MemorySlab<size>> = []
}

class MemorySlab<size: Integer> {

}

```

Then we create our caches:

```
let 4bytes = new MemorySlabCache(size: 4)
let 8bytes = new MemorySlabCache(size: 8)
...
let 32bytes = new MemorySlabCache(size: 32)
...
store.caches.push(4bytes, 8bytes, ..., 32bytes, ...)

```

Does this count as a "dependent type", *"a type whose definition depends on a value"*? Since the type of the `Array<MemorySlab<size>>` is dependent on the value assigned to the `size` field on `MemorySlabCache`. If not, what is this? What would make it into an example of dependent types?

# Answer
So, the answer is arguably "yes," this is an example of dependent types. However, the problem with a lot of simple examples that people create for this is that they don't demonstrate non-trivial aspects of dependent typing.

Arguably yours is better in this respect, because the type in question depends on an arbitrary value in `MemorySlabCache`. However, you never use a `MemorySlabCache` without a statically known value. So a more interesting example would be like:

```
let cacheSize = readInteger(stdin)
store.caches.push(new MemorySlabCache(cacheSize))

```

So, you allow the user to select a cache size at runtime, but the cache size is still recorded in the type, and the type checker statically ensures that all operations make sense with respect to the size, even though the size is not statically known (which is kind of another problem with your example; nothing in it shows how the tracked size matters subsequently).

A somewhat more minor problem is that integers are too easy a structure to 'fake' dependent types for, so examples with them end up under selling what might be feasible with genuine dependent types. For instance, Haskell with some extensions can encode even something similar to my runtime-cache-size example, even though it does not really have dependent types. You can have statically known type-level integers, and create a function that gives you back an appropriate value for a statically typed value based on a runtime integer. However, languages based on dependent type theory generally let types depend on values of arbitrary types, like function types. For these (and other related features), 'faking' is not really feasible.
> 4 votes

---
Tags: type-theory
---