title: Similarity between two geometric shapes

text:
# Question
Title: Similarity between two geometric shapes
I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it?

I am looking for a method which provides a short distance in case of:

1. scaling;
2. rotation;
3. perhaps local scaling or rotation.

---

I see two possible solutions:

1. transform the shapes into **pixel-based matrices** (bitmap) and compute a Levenshtein distance (but without enough robustness in the distance, in case of rotation for instance);
2. transform the shapes into **graphs** and try to define a distance between them.

# Answer
> 2 votes
One approach would be to use SIFT (or SURF, or other similar methods) to align one object to the other to account for scaling and rotation, and then compute a pixelwise distance based on the aligned images.

The right algorithm to use for alignment will depend upon the nature of the 2D images. If they are natural-color photographs taken using a camera, SIFT, SURF, etc. might work well. If they are black-and-white geometric shapes like shown in the question, you might do better to use image moments (e.g., Hu moments) or some other approach.

---
Tags: algorithms, graphs, computational-geometry, computer-vision
---


title: Big Oh notation

text:
# Question
Title: Big Oh notation
I've recently learned about the Big Oh notation and heard that the following aren't true:

1. $f(n)\in O(f(n)^2)$.
2. Either $f(n)\in O(g(n))$ or $f(n)\in\Omega(g(n))$ or both.
3. $f(n)\in\omega(g(n))$ implies $\log(f(n)) = \omega(\log(g(n))$.

I'm trying to find a good counter-example for each but it's proving to be a bit challenging. What would be a good one for these?

# Answer
For (1), take $f(n) = 1/n$.

For (2), take $f(n) = \begin{cases} 1 & n \text{ even} \\ n & n \text{ odd} \end{cases}$ and $g(n) = \sqrt{n}$.

For (3), take $f(n) = n^2$ and $g(n) = n$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: what are the basic/typical/common mistakes in P=NP claims?
the P vs NP problem attracts a lot of attention, not all of it desirable, for a wide variety of reasons. there are many P=NP claims eg on this widely cited list maintained by mathematician Woegeorgi, P vs NP page. also, intermittently there are hot questions on SE sites related to P vs NP (eg recently \[2\],\[3\]) below, & there is even a `p-vs-np` tag on both cs.se () & tcs.se sites. the following is intended somewhat as a reference question.

> what are the basic/typical/common mistakes in P=NP claims?

\[1\] How not to solve P=NP?, cs.se
\[2\] P vs NP code exercise, codegolf.se
\[3\] Analogs of P vs NP in the history of mathematics MO.se

# Answer
Often, people claim to find a polytime algorithm for an NP-hard problem. A couple things could go wrong:

1. The algorithm does not return a correct answer.
2. The algorithm does not run in polytime.

An example of the first mistake is Ted Swart's LP formulations for TSP. They were of poly-size (and so could be solved in polytime with any polytime LP algorithm), but the formulations were not tight. (More info here.)

I have blogged about a particular case of the second mistake. The short story is that the proof of poly runtime "solved" a recurrence relation incorrectly.
> 4 votes

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Number of instances of SAT (boolean satisfiability) problems of size N?
I assume the size of an instance of the SAT problem is measured by its number of (Boolean) variables. What is total number of instances of SAT problems of size N?

I guess that amounts to counting the number of "distinct" formulas that can be formed by N boolean variables, using a normal form such as CNF or DNF.

Update: this question is partly answered for the 3SAT case: https://cstheory.stackexchange.com/q/2168/15553

and the number of distinct **clauses** is: $$ C = 2N \times 2(N-1) \times 2(N -2) / 3! = 4 N(N-1)(N-2)/3 $$

# Answer
If you consider 3-Conjunctive Normal Form (3CNF) (every clause has exactly three literals) and you allow clauses with repeated variables, then it is easy to see that using $N$ variables the number of different 3SAT clauses is $(2N)^3$ ($2N$ because every literal can appear unnegated or negated).

So the total number of distinct 3CNF formulas (without repeated clauses) is $2^{(2N)^3}$.

But be careful because the "size" of a 3CNF formula (e.g. considered as an input of a decision problem) is usually the size of its representation. For example, using alphabet $\Sigma = \\{0,...,9,\`\`,",-\\}$ the 3CNF formula $(x\_1\lor\bar{x}\_2\lor x\_3)\land (\lor x\_2 \lor \bar{x}\_3 \lor \bar{x}\_4)$ can be represented with the string:

```
1,-2,3,2,-3,-4

```

and its length is 14.
> 6 votes

# Answer
A clause is comprised of literals over **n** variables. Let us assume that an instance is a subset of *distinct* clauses. We can obviously calculate the number of instances as the powerset of clauses, but that requires us to first clarify what we consider a valid clause.

In general, each variable will either be *represented* by one or both of its literals, or else it will be *unrepresented*. If the variable is represented, it may be represented through the positive literal only, the negative literal only, or both. Since there are 4 possible cases for each variable, and **n** variables, there must be $4^n$ possible clauses. Excluding the null clause we have $4^n -1$ total clauses and, excluding the null instance, $2^{4^n - 1}-1$ possible instances.

Of course, clauses that contain both literals of any variable aren't particularly useful; each one is satisfied by every assignment. Since these clauses don't really add any constraints, let's restrict our attention to *constraining* clauses.

In doing so, we eliminate the possibility of any variable taking both its literals, so we're left with three possible cases per variable, or $3^n$ possible clauses. Excluding the null clause and null collection again, we have $2^{3^n - 1}-1$ possible instances.

For k-SAT, each clause has exactly k literals. Obviously, there are $n\choose k$ ways to select k variables. Since we need exactly k literals per clause, however, we can only represent each variable with its positive or negative literal only. Thus, there must be $2^k{n \choose k}$ k-clauses, and $2^{2^k{n \choose k}}-1$ instances of k-sat.

Finally, note that we can also determine how many instances contain exactly c clauses.

* For all possible clauses, excluding the null clause: ${4^n-1}\choose c$
* For constraining clauses: ${3^n-1} \choose c$
* For k-clauses: ${{2^k}{n\choose k}\choose c}$
> 5 votes

---
Tags: logic, satisfiability
---


# Question
Title: Prove that the set of all total functions is countable
I'm stuck on a theory/set proof question:

> $S$ is the set of all total functions $f : \\{0, 1\\} \to \mathbb{N}$ (natural numbers), prove that S is countable.

I have found a sample solution already but I do not understand what is going on.

Quoting from here:

> To show this, we define a mapping $g$ from $S$ to $N × N$ and show the mapping is a bijection.

1. Why must I prove *bijection* when the definition of countable (according to wikipedia) states "A set $S$ is called countable if there exists an *injective* function $f$ from $S$ to the natural numbers"?
2. Also why a bijection/injection from $S$ to $\mathbb{N} \times \mathbb{N}$ and not just $S$ to $\mathbb{N}$?

# Answer
> 1 votes
ad a) showing that $g$ is injective should suffice.

ad b) because it's easier. or put differently: how would you define an injective mapping $h: S \rightarrow \mathbb{N}$ ? it is feasible (eg. $f \rightarrow 2^{f(0)}\\,\*\\,3^{f(1)}$) but complicates matters unnecessarily ( to prove injectivity you'd have to exploit additional information eg. the unique prime factor decomposition of natural numbers ).

---
Tags: uncountability
---


# Question
Title: Minimal spanning tree with degree constraint
I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of minimal spanning tree in which the degree of vertex 1 is at most $k$ (we don't care about other vertices' degrees). We can assume that such a tree exists.

Can someone give an idea how to approach the solution?

What I've already tried:

1) I know how to find essential edges from vertex 1. We can use dfs and start from a random edge of vertex 1. When we return to vertex 1 we can check if this edge (another vertex 1 edge) has lower weight than the previous one. If yes, than the previous one is not essential.

2) After that I wanted to use Kruskal's algorithm (adding in the beginning of the algorithm all essential edges). But the problem is that sometimes we should not take an edge with minimal weight to construct the required tree.

For example: 9-node undirected graph, $k = 3$

```
(vertex1 vertex2 weight)
1 2 1
2 3 5
3 4 6
4 5 7
5 1 1
1 6 1
6 7 8
7 8 9
8 9 10
9 1 2

```

So essentials will be (1,2) and (1, 6) (or (1, 5) and (1,6)). Kruskal will take (1,5) (or (1,2)) anyway. And the weight will be 41, but the correct answer is 39. So I don't know how to use Kruskal's algorithm here.

(The same example visualized, vertex 1 = vertex A)

I thought that we may construct a minimal spanning tree without constraints and after that try to transform it to the required one, but I don't know how to do this (how to transform without brute force).

# Answer
> 3 votes
As D.W. suggested, you can start as follows:

* Temporarily delete vertex $1$.
* For each of the resulting connected components $C\_1, \dotsc, C\_m$ find a MST, using e.g. Kruskal's or Prim's algorithm.
* Re-add vertex $1$ and for each $C\_i$ add the cheapest edge between $1$ and $C\_i$.
* If $m=k$, you are done.

If $m\<k$, you can now do the following:

* For each edge $\\{1,v\_j\\}$ not yet added, determine the most expensive edge on the path from $1$ to $v\_j$ in the current tree. Call this edge $e\_j$ and compute $d\_j = \operatorname{cost}(e\_j) - \operatorname{cost}(\\{1,v\_j\\})$, the cost savings of replacing $e\_j$ by $\\{1,v\_j\\}$ in the spanning tree.
* Create a priority queue of the tuples $(v\_j, e\_j, d\_j)$, ordered by decreasing value of $d\_j$.
* As long as $\operatorname{deg}(1) \< k$ and the first value $d\_j \> 0$, consider the first tuple from the proority queue:
    + If $e\_j$ has already been removed, find the edge $e\_j$ and the value $d\_j$ corresponding to the current tree. Update the tuple and its position in the priority queue.
    + Otherwise replace $e\_j$ by $\\{1,v\_j\\}$ in the spanning tree and remove the tuple from the queue.

Finding $e\_j$ can be done in ${\cal O}(n)$, using e.g. a modified DFS. This makes the second phase ${\cal O}(n^2)$. Since Prim's algorithm is ${\cal O}(n^2)$ as well, this is also the running time for the complete algorithm.

# Answer
> 1 votes
One way to go is to try them all. 'them' meaning all $(\le k)$-subsets of edges connected to the root. You throw the other edges (connected to the root) away and run Kruskal then take the minimum over all of them. The number of times you invoke Kruskal is $\sum\_{i=1}^k {d \choose i}$, where $d=\text{deg}(1)$. A terrible algorithm for large values of $k$ but it's correct.

# Answer
> 0 votes
I think the following might help a little bit:

Imagine deleting the vertex $1$ from the graph and all edges incident to vertex $1$, then decomposing the resulting graph into connected components. It's easy to see that we need at least one edge from vertex $1$ to each of those connected components.

Let the resulting connected components be $C\_1,C\_2,\dots,C\_m$. If $m\>k$, the problem is not solvable. If $m=k$, the problem is trivial: for each $i$, you pick the lowest cost edge between vertex $1$ and component $C\_i$. If $m\<k$, you have some more work to do. In this case, we want to pick $n\_i$ edges from vertex $1$ to component $C\_i$, subject to the restriction that $1 \le n\_i$ for each $i$ and $n\_1+n\_2+\dots+n\_m \le k$.

At this point, I think you might be able to run Kruskal's algorithm, but taking care to ensure that those constraints will be satisfied, i.e., to make sure you're not taking yourself into a dead end. At each step, you choose the lightest edge that's allowable. To test whether an edge is allowable, look at the forest $F$ that would result if you add it to the forest so far. In $F$, count up the number of edges out of vertex $1$ that are in $F$, and count the number of connected components that haven't yet been connected to vertex $1$ (by $F$); if that exceeds $k$, then the edge you were considering isn't allowable and must be skipped over (choosing it would leave you stuck in a dead end). Of course, as always in Kruskal's algorithm, any edge that would create a cycle is not allowable, either. I think this might work. It's your exercise, so I'll let you check the details.

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


title: Verify the type of a lambda expression

text:
# Question
Title: Verify the type of a lambda expression
I need to verify the type for the lambda expression: $\lambda f.\lambda x.f (f x)$

My method gives me: $(a\rightarrow c)\rightarrow b\rightarrow c$

Im trying to define it in Haskell (on Hugs) like this:

```
h= \f x -> f (f x)

```

When i call the :type comamnd it gives me:

```
(a -> a) -> a -> a

```

Is mi function correctly defined in Haskell?, or my method gives me a wrong result?

# Answer
> 1 votes
Haskell is right.

I do not know whether your Haskell syntax is correct, though it looks plausible to me, but the Haskell typing is the right one.

Since $f$ is applied to the result of $f(x)$, $f$ must be of type $a\rightarrow a$, $a$ being the type of $x$.

---
Tags: lambda-calculus, type-theory
---


# Question
Title: Is it possible for a language and its complement to both be unrecognizable?
Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable?

If some other language $S$ and its complement $\overline{S}$ are both recognizable, then $S$ and $\overline{S}$ are decidable. If $\overline{S}$ is unrecognizable, then then $S$ is undecidable but still recognizable. Why do we ignore the idea that $S$ and $\overline{S}$ may both be unrecognizable? This implies that $\exists! s \in S \cup \overline{S} = \Sigma^\*$ on which no machine halts, otherwise I don't see why we cannot have $x,y \in \Sigma^\*$ and $x \neq y$ such that no machine halts on $x$ or $y$, where $x \in S$ and $y \in \overline{S}$.

Perhaps I am making a false assumption somewhere?

# Answer
> 13 votes
I'll write "corecognizable" as a shortcut for "complement of recognizable". There are countably many recognizable languages and countably many corecognizable languages. Therefore, there are uncountably many languages which are neither recognizable nor corecognizable.

# Answer
> 10 votes
It is completely possible for both $L$ and $\overline{L}$ to be unrecognizable. For example, for any unrecognizable $M$, the language $L = 0M + 1\overline{M}$ over $\Sigma = \\{0,1\\}$ has this property (why?).

---
Tags: computability, semi-decidability
---


# Question
Title: Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?
I am reading Prim's MST for the first time and wanted to implement the fast version of it .

$m$ - The number of edges in the graph

$n$ - The number of vertices in the graph

Here's the algorithm :

1) Create a Min Heap of size $V$ where $V$ is the number of vertices in the given graph. Every node of min heap contains vertex number and key value of the vertex.

2) Initialize Min Heap with first vertex as root (the key value assigned to first vertex is $0$ ). The key value assigned to all other vertices is $\infty$ .

3) While Min Heap is not empty, do following

…..a) Extract the min value node from Min Heap. Let the extracted vertex be u.

…..b) For every adjacent vertex $v$ of $u$, check if $v$ is in Min Heap (not yet included in MST). If $v$ is in Min Heap and its key value is more than weight of $u-v$, then update the key value of $v$ as weight of $u-v$.

Now my point is during implementation ( I am doing in C++) in step 3(b) I have to check whether the vertex is there in the heap or not . As we know , searching in a heap is done in $O(n)$ time . So in the main while loop which will run ( $n$ number of times ) although extract-min is $O(\log n)$ but the search ( whether $v$ is min heap or not takes time proportional to size of the heap ( although it is decreasing in each step ) .

So is it correct to say that the above algorithm is $O(m+n\log n)$

# Answer
In your step 3b, you have to carry out at most $\deg(u)$ many **decrease-key** key operation. Thus in total you need $\sum \deg(u) = 2m$ many **decrease-key** operations. A single decrease key runs in $O(1)$ amortized time (Fibonacci Heaps). Thus the total running time is $O(m+n\log n)$. If you are not using Fibonacci heaps the running time is slower. Something like $O(m \log n )$.

I do not see how you got to $O(m+n\log n)$ by following your arguments. Also its unclear how you can do all the **decrease-key** key operation for one step in $O(n)$ time.
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis, runtime-analysis
---


# Question
Title: Log-Space Reduction $CO-2Col \le_L USTCON$
I want to show that $CO-2Col \le\_L USTCON$ (Log-Space reduction)

## $USTCON$

> The $s-t$ connectivity problem for **undirected** graphs is called $USTCON$.
>
> \[Input\]: An undirected graph $G=(V,E)$, $s,t \in V$.
>
> \[Output\]: 1 iff $s$ is connected to $t$ in $G$.

---

## $CO-2Col$

> A graph is $2$-colorable if there is a way to color the vertices of $G$ with $2$ colors, such that for every edge the two vertices on the edge are colored differently. $CO-2Col$ is the following problem:
>
> \[Input\]: An undirected graph $G$.
>
> \[Output\]: 1 iff $G$ is NOT $2$-colorable.

---

My **solution** is for an input graph $G$ the reduction outputs $(G',s,t)$ where $s$ an arbitrary vertex of $G$, $t$ is one of its neighbours and $G'=G^2$ namely an edge $(u,v)\in E(G')$,iff there is $w \in V (w \ne u,v)$ such that $(u,w)\in E(G)$ and $(w,v)\in E(G)$.

$G$ is bipartite iff $G'$ is not connected (and $s$ and $t$ belongs to different parts).

But this only works when the input graph $G$ is **connected**.

A counter example: (if we choose s,t to be A,B)

How can I improve my reduction that it will work at the unconnected case? or maybe a new reduction is needed?

Thanks!

# Answer
Hint: Extend the input graph to a connected graph which is bipartite iff the original graph is bipartite.

If the original graph is *not* bipartite, then the new graph will a fortiori not be bipartite. The more difficult direction is ensuring that when the original *is* bipartite, the new edges do not render it non-bipartite. This property is satisfied as long as the edges that you introduce do not close an odd cycle.

Further hint: Take $n$ copies of your original graph (where $n$ is the number of vertices), and add a new vertex $s$. Connect $s$ to the $i$th vertex in the $i$th copy.
> 3 votes

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


title: Recurrence of T(n) = T(n/3) + T(2n/3)

text:
# Question
Title: Recurrence of T(n) = T(n/3) + T(2n/3)
I've searched online for this but I only seem to find answers for a similar equation:

```
T(n) = T(n/3) + T(2n/3) + cn

```

But the one I'm trying to solve is:

```
T(n) = T(n/3) + T(2n/3)

```

Base case: We can assume `T(a) = Theta(1)` for any constant `a`.

I've succeeded in proving (by induction) that `T(n) = O(n*log(n))`. I thought the answer should be `Theta(n*log(n))`, but I cannot prove that `T(n) = Omega(n*log(n))`.

So my question is - am I correct that the answer is `O(n*log(n))`, and NOT `Theta(n*log(n))`? IF that's true that would really be great...

If I'm wrong I will of course explain where I'm stuck in the induction process...

Thanks!

P.S. If you need to, please try to explain using induction, because I haven't learned all methods for solving these problems yet.

# Answer
> 1 votes
Hint: Suppose that $T(m) \leq Cm$ for all $m \< n$, and that $n$ is divisible by $3$. Then $$ T(n) = T(n/3) + T(2n/3) \leq C(n/3) + C(2n/3) = Cn. $$ Use this to obtain a good bound on $T(n)$ when $n$ is a power of $3$.

---
Tags: algorithm-analysis, data-structures, runtime-analysis, recurrence-relation
---


# Question
Title: Which data structure to use to solve equations?
Let's say I have two equations for a geometric object (a rectangle):

$\left\\{ \begin{array}{l} x \ge 0 \\ y \ge 0 \\ A \ge 0 \\ P \ge 0 \\ A = x\*y \\ P = 2\*x + 2\*y \end{array} \right.$

Now I would like to set the values of some variables, and compute the values of the other ones.

At first, I thought it could be done with simple tree transformations on the AST, but I realized that I was more or less building a full solver.

The easy case is when one side of the equality consists only of constant terms, as it consists of a simple recursive tree evaluation. But the interesting case is when there are several variable bound together in a subtree. For example, for $ (A,P)=(30,11)$ the solution is $(x,y)=(5,6)$ or $(6,5)$

Can arbitrary complex instances of this problem solved just with tree transformations ? Or do I need something more elaborate ?

# Answer
> Which data structure to use to solve equations?

I assume that we are talking about polynomial equations here, because I want to base my answer on a Gröbner basis method. The example problem given in the question contains equations, inequalities, variables and parameters. We can replace inequalities $f(x\_1,\ldots,x\_n) \geq 0$ by equations with slack variables $f(x\_1,\ldots,x\_n) - e^2 = 0$. We can convert parameters $P$ into variables by adding equations enforcing their value $P-11 = 0$. We can convert equations $f(x\_1,\ldots,x\_n)=g(x\_1,\ldots,x\_n)$ to the form $f(x\_1,\ldots,x\_n)-g(x\_1,\ldots,x\_n) = 0$.

$\left\\{ \begin{array}{r} A - 30 = 0\\ P - 11 = 0\\ x - e\_x^2 = 0\\ y - e\_y^2 = 0\\ A - e\_A^2 = 0\\ P - e\_P^2 = 0\\ x\*y - A = 0 \\ 2\*x + 2\*y - P = 0 \end{array} \right.$

Each equation can be represented as a list of its monomials and their coefficients. A monomial $M$ is a product $M=x\_1^{a\_1}\cdots x\_n^{a\_n}$, where the $a\_i$ are nonnegative integers. The vector $\[a\_1, \ldots ,a\_n\]$ is called the *exponent vector* of $M$. A monomial can be represented by its exponent vector. This statement and the preceding description assumes that we have already fixed an enumeration of the variables. There are certainly more efficient ways to store a single equation, but these are just optimizations.

> Can arbitrary complex instances of this problem solved just with tree transformations ?

It depends a bit on what we consider to be a tree transformation, and whether we mean by solved just the symbolic precomputation, or the entire solution process. A Gröbner basis method is able to transform the intial system into a triangular form, with respect to any admissible monomial order. In our case, we will probably want to use an elimination order such that the parameters are smaller than all other monomials, and the slack variables are bigger than all other monomials. The example system will then be transformed to

$\left\\{ \begin{array}{r} e\_x^2 - x = 0 \\ e\_y^2 - y = 0 \\ e\_A^2 - A = 0 \\ e\_P^2 - P = 0 \\ x + y - \frac{1}{2}P = 0 \\ y\*y - \frac{1}{2}P\*y + A = 0 \\ A - 30 = 0 \\ P - 11 = 0 \\ \end{array} \right.$

This would be the results of the preprocessing. We can now solve this system numerically by back substitution. So we set the parameters to $P=11$ and $A=30$, solve the quadratic equation for $y$, then get $x$ from the linear equation, and then check the positivity constraints for $P$, $A$, $y$ and $x$. There are two solutions for $y$, so we have to do part of this process twice.

The are only two operations used during the transformation. The first operation is to reduce a polynomial by other polynomials, that is $f$ is replaced by $f-\sum\_{g\in G}q\_gg$ where the $q\_g$ are polynomials. (This should actually be a *multivariate division* with respect to a monomial order.) The other operation is to add the S-polynomial of two polynomials. The S-polynomial of two polynomials $f$ and $g$ with leading terms $l\_f$ and $l\_g$ (with respect to a monomial order) is given by $\frac{a}{l\_f}f-\frac{a}{l\_g}g$, where $a$ is the least common multiple of the leading terms $l\_f$ and $l\_g$. In a certain sense, one can really call these operations tree transformations, because we just transform polynomials into other polynomials.

One interesting lesson for myself here was that adding the inequalities and parameters didn't really affect the outcome of the Gröbner basis method. We had to choose an appropriate elimination order for the monomial order. However, there are well know fill-in reduction strategies, and any sufficiently complete strategy would have automatically chosen an appropriate order. (The equation system can be seen as a bipartite graph between the variables and the equations, where a variable is connected to an equation if it occurs in the equation. This bipartite graph already contains enough information to determine an appropriate elimination order such that any harm which could be caused by the inequalities and parameters is avoided.)

> Or do I need something more elaborate ?

One major problem is the order in which to apply the transformations. This already starts with the determination of an appropriate monomial order, but doesn't end there. Some of the methods developed for the direct solution of sparse linear systems can also be applied here. In addition, the reduction to an univariate polynomial of high degree is also a bit dangerous, from a numerical robustness point of view.
> 1 votes

# Answer
Even so there might be no general (efficient, reliable, numerically robust, consistent) solution, problems like the one given in the question arise for many applications. The efficiency, robustness and consistency of the solution methods may have improved significantly over time, but even the imperfect, slow and inconsistent initial solution approaches were good enough for many "real world" use cases. I find the dissertation from 1999 about "reinventing" the kernel of the interactive geometry software Cinderella quite illuminating in this respect.

The methods used in the publication above are limited to geometrical constructions, but they remind me of homotopy continuation methods. This overview presentation also refers to some symbolic solution methods:

and the well known Newton-Raphson method. The wikipedia article on system of polynomial equations paints a similar picture.

Kyle Jones mentioned in a comment Z3 as a SMT solver that might be able to solve this kind of problem. Frankly, I don't have practical experience with any of these methods, and never even heard of Wu's method or SMT solvers before. But there exist solvers or libraries for nearly all the mentioned solution approaches, like PHCpack (written in Ada) for homotopy continuation methods and FGb for Gröbner basis computations.

---

I may later add another answer about how to specifically apply a Gröbner basis method to the example problem, but let me briefly show just the solution, to give a feeling how it works:

The system $\left\\{ \begin{array}{l} A = x\*y \\ P = 2\*x + 2\*y \end{array} \right.$ gets reduced to $\left\\{ \begin{array}{r} x + y - \frac{1}{2}P = 0 \\ y\*y - \frac{1}{2}P\*y + A = 0 \\ \end{array} \right.$. This system is in triangular form, and can be solved by back substitution. One obvious problem is that you still have to solve polynomial equations in a single variable. And already the two different solutions of quadratic equations can quickly lead to an explosion of the runtime, when you have a triangular system of $n$ quadratic equations. (Each equation has two different solutions as a function of the previously chosen solutions, so you have to try $2^n$ solutions in the worst case.)
> 0 votes

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


# Question
Title: Construct context free grammar from language
I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific:

$\lbrace 0^a1^b2^c3^d4^e5^f |a,b,c,d,e,f \geq 0$ and $a+b=d+e\rbrace$.

My thought process has only gone so far. I see that if you add a 0 you must add a 3 or 4, the same is if you add a 1. And for adding a 3 or 4 the case is very similar. My biggest troubles are due to the characters that lay between the pairs of 0s,1s,3s and 4s. I haven't been able to produce a serious attempt yet, but will post it as an edit if I do. Any help would be appreciated.

**Edit:** Here is a possible solution I have come to:

$S\rightarrow AB$

$A\rightarrow 0A4|C|D$

$B\rightarrow B5|\epsilon $

$C\rightarrow 0C3|E$

$D\rightarrow 1D4|E$

$E\rightarrow 1E3|F$

$F\rightarrow 2F|\epsilon$.

# Answer
> 2 votes
You are right, the point is having nonterminals that sheds 0 and 4, or 0 and 3, or 1 and 4, or 1 and 3, switching from one to the other to get the $0^1 1^b$ and corresponding $3^d 4^e$; once you have that, go to one that repeats to make $2^c$ in between. The $5^f$ is easy to append.

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


# Question
Title: Time - Complexity Convex Optimization and Eigen Decomposition
Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the improvement in speed by many factors!?

1. Minimizing a convex function $L(X)$ in one matrix variable with orthogonality constraints over the matrix-essentially in my case this ends up to solving an eigen-decomposition.
2. Minimizing the same convex function $L(X)$ with linear constraints in $X$.

I know that 2.) should be faster. But what is the direction of work I need to do- to compare the improvement in speed-especially in terms of using the fastest available eigen solver for 1.)-what would be the corresponding fastest approach to solve 2.)?

# Answer
Regarding the eigen-decomposition, often it is enough to just compute the first few eigenvalue/eigenvector pairs. In the case, Krylow-subspace methods can be blazingly fast.

For the convex minimization under linear constraints, the (preconditioned) Uzawa iteration is a typical Krylow-subspace method, which is often not bad. There exist probably more advanced algorithms for this problem now, but http://scicomp.stackexchange.com would be a better place to ask about these. Also Schur-complement methods, or just parameterization of the linear sub-space might work fine too. And in case the linear constraints is actually a bunch of linear inequalities, a state of the art linear/convex programming solver might be the way to go.
> 1 votes

---
Tags: algorithms, time-complexity, optimization, efficiency, linear-algebra
---


# Question
Title: How hard is it to factorize sum of two numbers
Say I have numbers with known factorizations $n = \prod \limits \_i p\_i ^{n\_i}$ and $m = \prod \limits \_i p\_i ^{m\_i}$ (where $p\_i$ is the $i$th prime).

How hard is it to factorize $m+n$? Is there a more intelligent algorithm than if factorizations of $m$ and $n$ were not known? Assume $n$ and $m$ coprime as it is trivial to make them so.

The fact that $m+n$ will share no factors with $n$ or $m$ seems very helpful for small numbers, but I doubt it offers much for large ones.

# Answer
There is currently no known (asymptotical) more intelligent algorithm (and it is also not expected that there should be one) than if factorizations of $m$ and $n$ were not known (assuming $m$ and $n$ to be coprime). Even the case where $2$ is a prime factor doesn't count, because checking some of the smallest prime numbers can be done without much effort anyway.
> 3 votes

---
Tags: complexity-theory, factoring
---


# Question
Title: how do I find a undecidable subset of a set that's decidable?
Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?

# Answer
> 3 votes
Hint: For every language $L$, the language $M = \\{ 1^{2x+1} : x \in L \\}$ is a subset of $S$.

---
Tags: turing-machines, undecidability
---


title: maximum bipartite matching

text:
# Question
Title: maximum bipartite matching
I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that ﬁnds a maximum-sized subset of the rooks such that if we leave this subset on the chessboard and remove all other rooks, then no two rooks attack one another. (Two rooks are said to attack one another if and only if they are either in the same row or in the same column with no other intervening rooks between them.)

My idea for solving this problem is to consider a bipartite graph (X,Y) where X is the rows in the chessboard and Y is the columns. if a row and column have a rook placed at their intersection, then there is an edge between the those vertices from x to y. This can be converted into a maximum flow network and the value of max flow is the max matching.

In order to find a polynomial time algorithm i can run maybe BFS.

I wanted to know that if i build my solution on this idea shall it be correct. Is there a better algorithm (polynomial in m and n)?

Any help is appreciated.

# Answer
> 2 votes
As you mention, your problem is finding a maximum matching in an unweighted bipartite graph. There are several polynomial time algorithms for solving this problem. You can read about some of them on the Wikipedia page.

---
Tags: network-flow, bipartite-matching
---


# Question
Title: Why does x86 has explicit register definitions, and RISC's doesn't?
For example, on x86, we have a set of general registers, each named to the function it carries out.

We have an Accumulator, which is a storage for a results of different fixed point operations, we have a Base register, which is used for addressing elements in the array, a Cycle register, which holds a incremented or decremented counter for cycles, we have a Data register, which can hold an operand for arithmetic operations, and many many others (like base and stack pointers, indexes, and etc.)

But on typical RISC architectures, like SH4, for example, you won't find such an explicit names for registers. On Sh4, for example, there's no explicit name for register, which must hold a stack pointer, so you can store it elsewhere upon your choice from 16 available registers. Same for arithmetic operations, and so on.

So why it is that?
It is simply a matter of design, choices, taken by Intel engineers, or some significant sign of RISC processors?

# Answer
The main historical trend that accounts for the change in instruction sets is the dropping cost of memory. The x86 instruction set derives from the 8080, which derived from the 8008. The 8008 was first sold in 1972, when the cost of memory was about US\\$0.05 per *bit*. 1 MByte would have cost about US\\$400000, and even a KByte cost about \\$400. Now you can get 4GB of DRAM for less than $40 (US\\$0.00000000125 per bit) so the price has dropped by a factor of about 40 million in 40 years. (I may have missed a decimal place somewhere, and it also doesn't account for inflation (another factor of 5 or 6). But you get the idea.)

Expensive memory meant you needed to try to make the instructions as small as possible. There are a couple of ways you can do that. One way is using variable length instructions. The 8008 and 8080 had 1 byte instructions. If an instruction needed immediate data, the constant would be stored in the following byte (or bytes for 16-bit constants in the 8080). So instructions could vary between 1 byte and 3 bytes.

Another is to make the register operands implicit. The 8008 and 8080 each had 8 registers, so to specify two source registers and a destination register would have consumed 9 bits (already more than a byte!) Instead of having three operands, you can try to get away with 2. Most x86 instructions have 2 operands, one is the destination and also one of the sources, while the other is a source. But you can do still better. By assuming that all arithmetic instructions use the accumulator register as both the first source and the destination you only need to specify a single source operand. Similarly if you assume that all the stack manipulation instructions work on a specific stack register you can get away with not specifying the register holding the stack pointer. Similarly with loop counter increments and tests you can get away with no register specifiers if you have a dedicated loop counter.

Instruction compression of this kind is good but it comes at a couple of costs. The most important cost is that the instructions are variable length and hard to decode. The 8080 took several cycles to decode each instruction. By the 1980s the cost of memory had come down considerably, and people started to realize that by making instructions easier to decode it would be easier to design high-performance pipelined processors. RISC instructions are designed to be easy to decode (and to not have more than one memory operation so that they can be pipelined).

Instruction set design still has a small effect, mainly seen in power consumption. In general the decoders on x86 machines consume more area, and also more power, per instruction decoded than do machines with RISC instruction sets. On the other hand the x86 power consumption can be reduced somewhat during tight loops by caching a small number of decoded instructions. Additionally the number of instructions to encode a program in x86 is about half that to encode the same program with a RISC instruction set, so the instruction fetch bandwidth (and thus the power consumption for instruction fetch) is a bit lower with x86 than it is with RISC instruction sets.
> 7 votes

# Answer
This comes from the misty prehistory of computing, when registers where one-purpose only. Remember that the i686 (and all previous ones of the line, i.e., i?86) contains an 8086 as a subset, and that one contains (almost) an 8080 as subset. Register names come from the use in the beginnings.

In contrast, RISC architectures were designed from scratch, with the explicit goal of *simple* (i.e., fast) instructions, and as *regular as possible* (all registers equivalent, all instructions can use any addressing mode, ...). Simple, regular instructions means simpler (faster) decoding, more uniform execution (everything takes almost the same time). This in turn means less circuitry for doing the above, can dedicate more silicon to registers.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?
I was wondering if this language is context-free:

$L = \\{ x \in \\{ 0, 1 \\}^\* : |x| = 2^n $ for some natural number n $\\}$

I know that this language is not regular because it fails the pumping lemma for regular languages but that does not necessarily mean it is not context-free. I'm not sure whether to use the pumping lemma for context-free languages to show that this is not context free or to provide context-free grammar to show that it is context free.

I've tried creating a context-free grammar to generate this language but ran into trouble which makes me believe that this language is not context-free, but I am still unsure.

If someone could point me in the right direction that would be greatly appreciated.

# Answer
> 6 votes
Suppose $L$ was context-free. Then $L \cap 0^\*$ were also context-free. Since $L \cap 0^\*$ is a unary language (a language over a unary alphabet, i.e., an alphabet of size $1$), Parikh's theorem states that it is context-free iff it is regular. As you mention, $L \cap 0^\*$ isn't regular, and so $L$ can't be context-free.

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


# Question
Title: Develop the context free grammar to match this language (puzzle)
This is a puzzle type question which asks to create a context-free grammar to match this language:

```
{ x#w | x,w are in {a,b}*, and w contains the reversal of x as a substring }

```

So some example strings to try: #, a#a, b#b, ab#ba, ab#aaabbba

Does anyone have any advice on how to get better at these types of problems? I am generally a good problem solver, but have trouble developing grammars for languages for some reason. I am completely stuck on this question. Here is my attempt:

```
S --> TR
T --> aTa | bTb | #R
R --> RR | 0 | 1 | empty

```

My guess is that we want to define the left side of the string in terms of the right side of the string.

Edit: As far as I can tell, the above answer seems to be correct now. Only took me an hour to figure out!

# Answer
> 1 votes
Consider the following grammar: $$ T \to aTa | bTb $$ It is not hard to check that $T \to^\* wTw^R$ for all $w \in \\{a,b\\}^\*$, where $w^R$ is the reverse of $w$.

The language we are aiming at is $\\{w\\#xw^Ry : w,x,y \in \\{a,b\\}^\*\\}$. We can take care of the $x$ part by providing a "leaf case" for $T$: $$ \begin{align\*} &T \to \\#R \\ &R \to aR|bR|\epsilon \end{align\*} $$ Similarly, to take care of the $y$ part, we can create a new start symbol $S$, and add the production $$ S \to TR $$ In total, we obtain the grammar $$ \begin{align\*} &S \to TR \\ &T \to aTa|bTb|\\#R \\ &R \to aR|bR|\epsilon \end{align\*} $$

# Answer
> 2 votes
```
X --> Xa | Xb | Y

Y --> aYa | bYb | #Z

Z --> Za | Zb | empty

```

Y is the part that handles the string reversal. X and Z handle junk to the right and left of the reversal of `x`.

---
Tags: context-free
---


# Question
Title: Why is there a 2n+1 comparison for a linear search algorithm?
Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of the integer that is evaluated as even.

How come the algorithm would have 2n+1 comparison?

I thought linear search would have n comparision because it is going through n elements. +1 comparison for the if statement. So that would make the algorithm O(n+1) comparison, no?. Where did the extra n come from?

Pseudo-code:

```
procedure last_even_loc(a1,a2,...,an:integers);
location = 0;
for i = 1 to n

    if (a_i = 0) (mod 2) then location = i

return location;

```

# Answer
```
procedure last_even_loc(a1,a2,...,an:integers)
1.location = 0;
2.for i = 1 to n
3.    if (a_i = 0) (mod 2) then location = i
4.return location;

```

statement 1 is executing only once. statemet 2 is executing total n+1 times. statement 3 is executing total n times. statement 4 is executing only once.

The running time of the algorithm is the sum of running time of all the statements executed.so running time=1+1+n+(n+1)=O(2n+3)=O(n).so there is total n+1+n=2n+1 comparisons(statement 2 and 3).
> 3 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis
---


title: Efficiently representing a set of sets

text:
# Question
Title: Efficiently representing a set of sets
(The question is an extension of this unanswered question on stackoverflow)

If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in a DAG instead of a tree that is even more compact.

However, if we have a set of sets (i.e. the order does not matter), there are a lot of possible tries that represent the same set of elements. An example can be found in the stackoverflow question I linked above.

**Edit:** For example, assume that we are given the following sets of integers.

```
{1,2,3,4,5}
{1,2,6,7}
{1,2,4,7}
{1,3,5,7}

```

Two possible representations are shown below (trie on the left, DAG on the right)

My questions are:

> 1. How hard is the problem of finding an optimal (i.e minimal) such trie?
> 2. Are there any fast algorithms for solving this problem?
> 3. If not, are there any fast algorithms that find "good" tries?
> 4. What about the DAG case?

In the scenario I have in mind there is an additional constraint that no set is a subset of another set.

Any link/paper that is even slightly relevant to any of the questions is helpful.

# Answer
> 3 votes
I suggest you start by looking at BDDs and ZDDs.

Your problem is similar to the problem of finding an optimal BDD.

I'll explain. Suppose we have sets $S\_1,\dots,S\_k$ over a universe $U$ containing $n$ items (so $S\_i \subseteq U$). A BDD is a finite-state automaton (a DAG) for recognizing the language of all of the allowed sets, where each set is presented to the finite-state automaton as the $n$-bit string that is the characteristic function of that set. In other words, given a total order on $U$, each set $S \subseteq U$ corresponds to a binary string $\[S\] \in \\{0,1\\}^n$: $\[S\]\_i=1$ if $S$ includes the $i$ element of $U$, otherwise not. (This order is known in the BDD literature as a "variable ordering".) Then define the language $L$ by $L=\\{\[S\_1\],\[S\_2\],\dots,\[S\_k\]\\}$. A BDD is a finite-state automaton that recognizes the language $L$.

Notice that you have the freedom of what "variable ordering" to choose. The choice of the variable ordering determines how each set is represented as a binary function, which can affect the size of the BDD. It is well-known that the problem of choosing the optimal variable ordering (the one that leads to the smallest BDD) is NP-hard. Nonetheless, there are various heuristics for trying to find a good variable ordering, and in real-world problems, they often work reasonably well.

So, your problem can be framed as the problem of choosing the optimal variable ordering to represent your sets as a BDD.

ZDDs are a variant of BDDs that are better in some circumstances. ZDDs are especially oriented at representing a set of sets, so they might be particularly helpful for your needs. ZDDs are especially handy if you need to represent a bunch of sets that are related to each other in some way; ZDDs provide a compact and efficient encoding for that situation.

# Answer
> 2 votes
I'm not 100% sure, but I'd guess it's at least NP-hard to find the best dag that represents your set of sets.
Essentially you're trying to find the best permutations of the given sets, to then apply a DAG-algorithm on those permutations. So it might be possible to find a reduction via Binary decision diagrams, for which it is known to be NP-hard to find the best ordering.

Similarly, if you consider your set of sets as a string $S$ and hope to find a nice CNF-grammar that generates $S$, then again you're at an NP-hard problem (finding the shortest CNF-grammar for a given string). Of course that does not consider the fact that you might need to consider different permutations of the sets, but that should only make things harder.

# Answer
> -1 votes
there is a close connection of the complexity of finding *optimal* DAGs as "compressions" of sets of sets (hypergraphs) to the P/Poly?=NP question sketched out here. basically/roughly speaking circuits are closely connected to DAGs and if one can find small circuits for sets-of-sets (hypergraphs) built out of NP complete patterns, one could "compress" those patterns into P-size computations. another close angle is that this is also related to hypergraph decompositions (via DAGs). more discussion in chat for anyone interested.

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


# Question
Title: Proving that context-free languages are closed under inserting symbols
This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation. This means basically that any context-free language which undergoes this operation would still be context-free.

> For a language $A$ which is a subset $\Sigma^\*$, define the language $A\_+$ as
>
> $\qquad\displaystyle A\_+ = \\{xyz | y\in \Sigma \wedge xz \in A\\}$.
>
> Prove that the set of context-free languages is closed under the $+$ operator.

So $A\_+$ contains all strings that can be obtained by inserting one symbol into a string in $A$. Show that the class of context-free languages is closed under the operation $+$ (i.e., show that if $A$ is context free, then $A\_+$ is also context free).

Note that this is not a homework question. Examples of closure proofs are sparse online and in my textbook.

First, let's think about the different ways to prove closure of CFLs:

1. Constructing a "template" Push Down Automata that can incorporate any other Push Down Automata and add on a part to the beginning, middle, or end of the PDA and still be able to accept the language accepted by the original CFL, with the new operation on it. Basically, if for any given PDA P, if a PDA P' can be created which accepts the language of P with the new operation (in our case, the "+" operator) performed on it, then that operation must be under closure.

Solving the problem in this manner is quite simple to think about. Imagine a PDA P which accepts strings from the CFL L. In application to our problem, this would be a PDA which can successfully read in the string 'xz', where x and z are simply any string conforming to our alphabet. The PDA P' would similarly have the ability to read xz, but each state of the PDA could have an additional self loop which reads the character in the string y.

I have selected the answer which I find to be most appropriate for this question. It simply involves using the "tempate PDA" strategy which I outline above; however, my construction did not achieve the goals of the new language (think about why before looking at the answer below).

# Answer
Two ways of proving this come to mind: using push-down automata and using grammars.

**Using push-down automata**

Consider a PDA for some context-free language. The idea is to modify the PDA so that it has to "swallow" one character at some arbitrary moment. Here we use the non-deterministic nature of PDAs. In order to implement this idea, duplicate the set of states of the PDA. Each set of states has the usual transitions, the initial state resides in the first set, and we retain the accepting states only in the second set. In addition, for each state $q$ we connect the copy of $q$ in the first set to its copy in the second set with an arc labelled $\Sigma$. This is the non-deterministic "swallowing" of one character.

**Using grammars**

We can do a similar thing using grammars. Consider a context-free grammar in Chomsky normal form for some language (the transformation is easier to describe for Chomsky normal form, but can also be done directly). Each non-terminal now comes in two flavors: unmarked $A$ and marked $A'$. The initial symbol is $S'$ (where $S$ is the initial symbol of the original grammar). For each transition $A \to BC$ we include the following transitions in the grammar: $$ \begin{align\*} &A \to BC \\ &A' \to B'C \\ &A' \to BC' \end{align\*} $$ For each transition $A \to a$ we include the following transitions in the grammar: $$ \begin{align\*} &A \to a \\ &A' \to \sigma a | a \sigma \text{ for every } \sigma \in \Sigma \end{align\*} $$ The marked version of each non-terminal codes that the extra character lies within the subtree generated by this non-terminal. The addition of the extra character itself is handled by the rules $A' \to \sigma a | a \sigma$.
> 1 votes

# Answer
**Using closure under GSM mappings**

Whenever possible, it may be faster to prove closure properties from other known closure properties, That is why there has been a systematic study of closure properties (see AFL, full AFL, trios, ...). This is somewhat developed in the Hopcroft-Ullman textbook, ed. 1978).

For this problem, the insertion of a single character from the alphabet in the strings of a language can be trivially performed by application of a GSM-mapping. Since CF languages (and many others) are closed under GSM-mapping, they are closed under the $+$ operator.

**If you do not know about GSM mappings**, you can do it with closure under intersection with regular sets, homomorphism and inverse homomorphism. That is actually how closure under GSM mapping is proved.

Assuming your original alphabet is called $\Sigma$, you create a new alphabet $\hat\Sigma=\\{\hat a \mid a\in \Sigma\\}$, i.e. a new set of symbols in 1-1 correspondance with $\Sigma$. Using the inverse of a homomorphism (that simply erases $\hat\Sigma$), you insert an arbitrary number of $\hat\Sigma$ symbols in the string. Then you intersect the result with the regular set $\\{w\in (\Sigma\cup\hat\Sigma)^\*\mid |w|\_{\hat\Sigma}=1\\}$, so as to allow the insertion of only one symbol from $\hat\Sigma$. Then you remove the hat with a homomorphism $\phi$ such that $\forall \hat a \in \hat\Sigma,\\, \phi(\hat a)= a$.
> 2 votes

---
Tags: formal-languages, context-free, closure-properties
---


title: Generation of random binary trees

text:
# Question
Title: Generation of random binary trees
Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that?

I attempted to do as follows: From a PRNG obtain n PRNs in \[0.0, 1.0) as (relative) frequencies of n symbols for generating a Huffman tree (used in data compression). But, if the PRNs used are uniform, then I think this would highly favour generation of those Huffman trees that are more flat and Huffman trees corresponding to widely different frequencies of the symbols would be highly suppressed in the generation process. If this is correct, how could one do better? Thanks in advance.

# Answer
Binary trees are counted by Catalan numbers: the number of "full" binary trees (each node has either 0 or 2 children) with $n$ leaves is $C\_{n-1}$. The Catalan numbers are given by an explicit formula, and also satisfy the recurrence $$ C\_{n+1} = \sum\_{i+j = n} C\_i C\_j, $$ which follows directly from the interpretation as counting binary trees. You can use this formula to decode a number in $\[0,C\_{n-1}) = \\{0,\ldots,C\_{n-1}-1\\}$ to a binary tree. If the index is chosen randomly, you obtain a random binary tree.

The decoding procedure is recursive. First, we partition $\[0,C\_{n-1})$ into intervals of lengths $C\_0 C\_{n-2}, C\_1 C\_{n-3}, \ldots, C\_{n-2} C\_0$. If the number falls in the interval of length $C\_i C\_j$, then the left subtree will have $i+1$ leaves, and the right subtree will have $j+1$ leaves. Within the interval, we have an index in the range $\[0,C\_i C\_j)$, which we decode to a pair of indices $x \in \[0,C\_i)$ and $y \in \[0,C\_j)$. We recursively compute which tree with $i+1$ leaves is encoded by $x$ and which tree with $j+1$ leaves is encoded by $y$. The recursion stops when $n = 1$, in which case the tree consists of just the root.
> 12 votes

# Answer
I have found an algorithm on p.16 of the book: L. Alonso, R. Schott, Random Generation of Trees, Kluwer, 1995. Note however that the C code for it on p.191-192 of the book is erroneous (from communication of the first author). (I have coded the algorithm in Python and included it in a program of my own: http://s13.zetaboards.com/Crypto/topic/7164646/1/)
> 1 votes

---
Tags: data-structures, sampling, random-graphs
---


# Question
Title: Lambda calculus: difference between contexts and evaluation contexts
Firstly, I'd like to say that my text below may contain errors, so feel free to point out any mistakes in my formulation of the question.

Consider an untyped lambda calculus with booleans and if-statements whose terms are given by this syntax:

```
 t ::= v | t t | if t t t | x
 v ::= \x.t | #t | #f

```

Contexts C in this case would be given according to this syntax:

```
C ::= [-] | \x. C | C t | t C | if C t t | if t C t | if t t C

```

Additionally, one could define evaluation contexts E according to this other syntax:

```
E ::= [-] | \x. E | v E | E t | if E t t

```

I split my question in three sub-points which I'd like to be addressed.

1. When are the two notions used? I know for example that evaluation contexts are used to define the semantics of the calculus, but the usage of contexts still somewhat eludes me. Also I'd like some confirmation of my knowledge here.
2. When is one to be preferred to the other and why?
3. Could you point to relevant articles that could help me sort out this matter?

# Answer
Context are used for many purposes, but typically to define congruences on programs. Evaluation contexts are a subset of contexts. They are typically used to define reduction relations. Let me give an example of each.

One formal way of defining program equality is to say two programs $M$ and $N$ are *contextually equal* they can replace each other in each context without a change of behaviour. We can define this as follows: $M$ and $N$ are contextually equal provided for all closing contexts $C\[\cdot\]$ for $M$ and $N$: $C\[M\] \Downarrow t$ if and only if $C\[N\] \Downarrow t$. We say a context is *closing for $M, N$* if neither $C\[M\]$ nor $C\[N\]$ have free variables. The expression $M \Downarrow t$ means that the program $M$ reduces in a finite number of steps to the value $t$. (As an aside, note that the definition of contextual equivalence is more involved for rich notions of computation, e.g. concurrent processes.)

In contrast, evaluation contexts are contexts that do not block evaluation. More precisely, an evaluation context is a term with a hole at the point where the next atomic reduction step must take place (or may take place for non-deterministic computation). So the following rule should hold for evaluation contexts: $$ \frac{M \rightarrow N}{E\[M\] \rightarrow E\[N\]} $$ As an example of using evaluation contexts, consider the reduction rules for call-by-value $\lambda$-calculus, where we do not reduce under $\lambda$. So even when $M \rightarrow N$, we don't have a reduction $\lambda x.M \rightarrow \lambda x.N$. This can easily be expressed with the general contextual rule above, together with a grammar for evaluation contexts that omits $\lambda$-expressions. Evaluation contexts were first used in The Revised Report On The Syntactic Theories of Sequential Control and State by Felleisen and Hieb.
> 15 votes

# Answer
A context is a syntactic notion. A context is a term with one hole in it. (Occasionally there are multi-hole contexts, the definition will be given clearly in that case.) The syntax of contexts is defined by taking the syntax of terms and allowing one subterm to be a hole $\[\]$ instead of a term. In BNF (I use the lambda-calculus as an example, without booleans and if statements which don't bring anything to the example.): $$ C ::= \[\] \mid x \mid t \\, C \mid C \\, t \mid \lambda x.C $$

Together with the definition of a context comes the definition of putting a term in a context. If $C\[\]$ is a context and $t$ is a term, then $C\[t\]$ is the term obtained by putting $t$ in the syntax tree where the hole $\[\]$ is in $C\[t\]$. This is basically a substitution where the variable is guaranteed to occur exactly once (but note that the “variable” that is substituted is a variable at the meta level, $\[\]$, not a variable in the lambda-calculus or other language of the terms $t$).

Contexts are used to formulate various definitions in semantics. A common example is that most notions of evaluation involve defining contexts in which evaluation can be performed. For example, consider the lambda-calculus. The fundamental notion of evaluation is given by the beta-reduction rule: $$ (\lambda x. M) \\, N \to\_\beta M \\{x\leftarrow N\\} $$ where $M \\{x\leftarrow N\\}$ is the substitution $x \mapsto N$ applied to $M$.

This isn't the complete definition of beta-reduction: given a term $t$, it can beta-reduce if there are subterms $M$ and $N$ and a variable $x$ such that $t = (\lambda x. M) \\, N$; but more generally $t$ can beta-reduce **if there is a subterm $t'$ such that $t' = (\lambda x. M) \\, N$**. Another way to express this is that $t$ can beta-reduce if there is a context $C$ and some terms $M$ and $N$ and a variable $x$ such that $t = C\[(\lambda x. M) \\, N\]$. When there is such a reduction, the right-hand side is $C\[M \\{x\leftarrow N\\}\]$. To use a formal notation, beta-reduction is defined by the following deduction rules: $$ \dfrac{}{(\lambda x. M) \\, N \to\_\beta M \\{x\leftarrow N\\}} (\beta) \qquad \dfrac{M \to\_\beta N}{C\[M\] \to\_\beta C\[N\]} (\gamma) $$ The same definition can be expressed by making all the kinds of contexts explicit: $$ \dfrac{}{(\lambda x. M) \\, N \to\_\beta M \\{x\leftarrow N\\}} (\beta) \\ \dfrac{M \to\_\beta N}{\lambda x. M \to\_\beta \lambda x. N} (C\_\lambda) \qquad \dfrac{M \to\_\beta N}{M \\, P \to\_\beta N \\, P} (C\_{@\lt}) \qquad \dfrac{M \to\_\beta N}{P \\, M \to\_\beta P \\, N} (C\_{@\gt}) $$

This definition yields beta-reduction, i.e. a notion of evaluation that allows reducing any subterm. Computations as performed in programming languages often don't allow reducing subterms inside functions: the reduction rule can only be applied at the toplevel, or on the left-hand side or right-hand side of an application. We can express this by defining a new kind of context which does not allow all syntactic forms: $$ D ::= \[\] \mid x \mid t \\, D \mid D \\, t $$ We can use this syntax to define the semantic notion of non-partial evaluation: $$ \dfrac{}{(\lambda x. M) \\, N \to\_{np} M \\{x\leftarrow N\\}} \qquad \dfrac{M \to\_{np} N}{D\[M\] \to\_{np} D\[N\]} $$ We could also present this definition by expanding it, like we did above for full beta reduction: $$ \dfrac{}{(\lambda x. M) \\, N \to\_{np} M \\{x\leftarrow N\\}} (\beta) \\ \dfrac{M \to\_{np} N}{M \\, P \to\_{np} N \\, P} (C\_{@\lt}) \qquad \dfrac{M \to\_{np} N}{P \\, M \to\_{np} P \\, N} (C\_{@\gt}) $$ $D$ would be called an evaluation context because it is used to define a notion of evaluation. An evaluation context isn't a special kind of context; rather, **calling it an evaluation context is a matter of what the context is used for**.

I'll give one more example of context. Let's define values $V$ according to the following syntax: $$ V ::= x V\_1 \ldots V\_n \mid \lambda x. M $$ Now let's define another kind of contexts: $$ E ::= \[\] \mid M \\, E \mid E \\, V $$ Compared with $D$ above, the hole can be on the function side of an application if the argument of the application is a value. Define then the following notion of reduction: $$ \dfrac{}{(\lambda x. M) \\, V \to\_{cbva} M \\{x\leftarrow V\\}} (\beta\_{cbva}) \qquad \dfrac{M \to\_\beta N}{E\[M\] \to\_{cbva} E\[N\]} (\gamma\_{cbva}) $$ With the restriction that the argument of the function must be a value in the first rule and that lambda abstractions are not contexts, we're defining a call-by-value evaluation strategy. With the further restriction that the argument is evaluated before the function, this is applicative order call by value.
> 15 votes

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


title: SAT reduction to prove NP completeness

text:
# Question
Title: SAT reduction to prove NP completeness
Suppose you have a set of binary strings of length n, the magnitude of a string is the number of 1's it has. and you want the program to return true if there is a string of length n that has a magnitude of \<= k and there is a index i for every y in the set string\[i\] = y\[i\] = 1 for all strings.

Example for n = 5, k = 3:

0 1 0 0 1

1 0 0 1 0

0 0 1 0 0

1 0 1 0 0

0 1 0 1 0

1 1 1 0 0 would be a solution to the above set.

# Answer
Let me restate your problem: given a collection $S\_1,\ldots,S\_m \subseteq \[n\]$, the problem is to decide whether there is a set $S \subseteq \[n\]$ of magnitude at most $k$ that "hits" every set $S\_i$, i.e., $S\_i \cap S \neq \emptyset$. This is the same as the classical problem *set cover*, which is known to be NP-complete. The corresponding set cover instance has $n$ sets over the ground set $\[m\]$, the $i$th set being $T\_i = \\{ j \in \[m\] : i \in S\_j \\}$. A set cover is the same as a choice of $S$.

(Answer to old version:) Your problem is in P. If $k = 0$ then the answer is always NO. If $k \geq 1$ then the answer is YES if and only if when you write your strings as rows in a matrix, then there is a column which consists only of $1$s. This is a condition which you can check in linear time (in the input size).
> 3 votes

---
Tags: np-complete, reductions
---


# Question
Title: How to make this recursive relationship nonrecursive?
I need to make a recursive relationship for a function `f(m, n)` nonrecursive to make it more efficient and succinct in my code.

I stumbled across an important recurrence relationship dealing with the number of vertices, edges, faces, and solids (m-polytopes) in an n-cube which is based off of a simpler algorithm for an n-simplex which uses Pascal's triangle:

For a simplex: nCm gives you the number of m-polytopes (m = 1 for points, 2 for lines, 3 for faces) in an n-simplex (1-simplex is a line, 2-simplex is a triangle, 3-simplex is a tetrahedron).

The pattern between the n-simplex m-polytopes and the n-cube m-polytopes are very similar:

```
Here is the n-cube up to 10
10-polytopes:
9-polytopes:                                                           1
8-polytopes:                                                     1    16
7-polytopes:                                               1    14   112
6-polytopes:                                         1    12    84   448
5-polytopes:                                   1    10    60   280  1120
4-polytopes:                             1     8    40   160   560  1792
3-polytopes:                       1     6    24    80   240   672  1792
2-polytopes:                 1     4    12    32    80   192   448  1024
1-polytopes:           1     2     4     8    16    32    64   128   256
Here is the n-simplex up to 10
10-polytopes:
9-polytopes:                                                           1
8-polytopes:                                                     1     9
7-polytopes:                                               1     8    36
6-polytopes:                                         1     7    28    84
5-polytopes:                                   1     6    21    56   126
4-polytopes:                             1     5    15    35    70   126
3-polytopes:                       1     4    10    20    35    56    84
2-polytopes:                 1     3     6    10    15    21    28    36
1-polytopes:     1     1     2     3     4     5     6     7     8     9

```

And here is the c code that generated that:

```
#include <stdio.h>

#define TOP 10

// nothing to see here
int factorial(int n)
{
    if (n < 2)
        return 1;
    else
        return n * factorial(n - 1);
}
// a recursive implementation for the number of
// m-polytopes in an n-cube
int ncubeRecursive(int n, int m)
{
    if (n == 0 && m == 0)
        return 1;
    else if(n < 0 || m < 0)
        return 0;
    else
    {
        return (ncubeRecursive(n - 1, m - 1) + 2 * ncubeRecursive(n - 1, m));
    }
}
// missing a nonrecursive algorithm
// YOUR JOB TO FIX THIS

// a recursive implementation for the number of
// m-polytopes in an n-simplex
int nsimplexRecursive(int n, int m)
{
    if (n == 0 && m == 0)
        return 1;
    else if(n < 0 || m < 0)
        return 0;
    else
    {
        return (nsimplexRecursive(n - 1, m - 1) + nsimplexRecursive(n - 1, m));
    }
}
// a nonrecursive algorithm
int nsimplexNonrecursive(int n, int m)
{
    return factorial(n)/(factorial(n - m) * factorial(m));
}

int main()
{
    printf("Here is the n-cube up to %i\n", TOP);
    for (int n = TOP; n > 0; --n)
    {
        printf("%i-polytopes:", n);
        for (int m = 0; m < TOP; ++m)
        {
            int val = ncubeRecursive(m, n);
            if (val == 0)
                printf("%6c", ' ');
            else
                printf("%6i", val);
        }
        printf("\n");
    }
    printf("Here is the n-simplex up to %i\n", TOP);
    for (int n = TOP; n > 0; --n)
    {
        printf("%i-polytopes:", n);
        for (int m = 0; m < TOP; ++m)
        {
            int val = nsimplexNonrecursive(m, n);
            if (val == 0)
                printf("%6c", ' ');
            else
                printf("%6i", val);
        }
        printf("\n");
    }

    return 0;
}

```

Does anyone here see a non-recursive pattern? I just don't know how to analyze a recursive relationship like this for a function that takes to inputs like `f(m, n)` instead of just `f(x)`.

# Answer
> 3 votes
For the $n$-cube, you are interested in A013609 (see the link), in which the following explicit formula is given: $$ f(m,n) = \binom{m}{n} 2^n. $$ (Your indexing could be slightly different.)

Tip: Whenever you have a recurrence relation and looking for a closed form, calculate a few entries and look it up in the OEIS. That's how I found the formula.

For the $n$-simplex, as you mention, this is just Pascal's triangle.

---
Tags: algorithms, combinatorics, computational-geometry, recurrence-relation
---


# Question
Title: Turing machine - infinite tape in one or two directions
I have seen turing machines beeing represented with tapes infinite in one, and in two directions. Is there any difference in the power of such turing machines, or are they basically equivalent? In my head I think they are equivalent, since I guess that there must be some way to represent the two-way infinite tape as a one-way infinite tape, but I can't seem to find a proof or example.

# Answer
> 15 votes
They are equivalent in computational power. Anything computable by one of these two kinds of Turing machines, is computable by the other kind. Let's look at how to simulate a Turing machine with a doubly infinite tape, on a Turing machine with a singly infinite tape.

The idea is to cut your doubly infinite tape in two, so that you have two singly infinite tapes, a left one and a right one, which you will ultimately merge. You may mark the ends with a tape location containing a special EOF symbol. You also duplicate your finite control, so that you have two identical finite state controls. You assume that you have a control passing device (see below), so that, when the left machine tries to go beyond the right end of its tape, it passes the control to the right machine, on its leftmost tape position (just before the left end of the right tape). And conversely, when attempting to pass the left end of the right tape.

Now, in order to distinguish the left and the right machines, we change the names of the states and the tape symbols, by indexing them with $R$ and $L$ respectively for the left and the right machine. And we change accordingly the transitions of the two machines so that they work as before.

Now we are ready to merge the two half-tapes, for example by folding the right one onto the left one. For that you flip over the right half tape, and you are careful to modify accordingly the transitions, exchanging right for left and left for right. Then you fuse the two half tapes into a single tape containing pairs of symbols, a left one and a right one, each component being possibly blank.

You modify again the transitions of both machines, so that the left (resp. right) transitions use and modify only the left (resp. right) parts of the pairs on the tape. Then you merge the control of the two machines by simple set union respectively for states, and for transitions.

You add a set of transitions for each existing state, so that when the tape symbol is EOF, it goes back to the previous tape location (the first non-EOF location) and the state changes to its chiral counterpart: if it is a left (resp. right) state, it changes to its right (resp. left) counterpart. That is the control passing device.

I may have forgotten a detail, but this is the general idea of the construction. The proof is left as an execise.

Of course, the initial tape (input) must be modified accordingly. But that can be made simple by placing the input (if finite) fully on the left side (the one that is not flipped over) of the tape cut.

Then you put away the screw driver as it may be dangerous for the kids.

PS I only showed that the doubly infinite tape can be simulated with a singly infinite tape. The converse seems too obvious.

---
Tags: turing-machines
---


# Question
Title: Can a context free grammar for $L$, generate a string not in $L$?
from Sipster's definition: Any language that can be generated by some context-free grammar (call it $G$) is called a context-free language (CFL). However, can $G$ generate strings that are not in the the language that recognizes $G$?

# Answer
By definition, the language generated by a grammar $G$ is the set of all strings generated by $G$. So a grammar generating a language $L$ can generate only words in $L$ (and conversely, it can generate all words in $L$).
> 5 votes

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


# Question
Title: What kind of model is used by 20 Questions?
Which kind of machine learning concept / model is used in 20 Questions?
Is this kind of thing best solved by a neural network?
Where I can read something about it?

# Answer
this is a large collaboratively edited database of conditional branches basically, but it is probably not so reliable unless humans review/correct its collection (not sure how much that is done). it uses some principles similar to binary search. it is also similar to expert systems except that its modifiable.

basically the answers to the questions serve as a "unique address" of the different objects in memory ie it can probably be modelled largely as a huge decision tree. it also has some rough similarity to a famous CS project called Cyc, part of the Symbolic AI school of thought, that attempted to categorize all human knowledge. 20Q has a FAQ here. another somewhat related/more recent technology in this area is rules engines.

as an example/single random sample of its reliability/coverage, picked "tv" as the object & it basically failed. also some of the guesses dont really seem to make sense, hence possibly a poor quality of "samples" collected from random web users who dont have much incentive to provide high quality responses (and might amuse themselves by not doing so).

```
You won!
Q30.  I am guessing that it is a Pikachu (Pokemon character)?
Right, Wrong, Close
29.     I guessed that it was a record (before CD's)? Wrong.
28.     Is it heavy? No.
27.     I guessed that it was a cartoon? Wrong.
26.     Do you make something with it? No.
25.     Is it smaller than a loaf of bread? No.
24.     Do you use it in cooking? No.
23.     I guessed that it was a model train? Wrong.
22.     Does it use electricity? Yes.
21.     Can it be played? No.
20.     I guessed that it was a hairdryer? Wrong.
19.     Was it used over 100 years ago? No.
18.     I guessed that it was an autoharp? Wrong.
17.     Do you use it in your home? Yes.
16.     Does it have a horn? No.
15.     Is it worth a lot of money? No.
14.     Is it larger than a pound of butter? Yes.
13.     Would you use it in the dark? No.
12.     Is it straight? No.
11.     Do you need batteries to use it? No.
10.     Can you put something into it? No.
9.      Is it larger than a microwave oven (or bread box)? No.
8.      Do you use it at work? No.
7.      Does it ring? No.
6.      Is it a root vegetable? No.
5.      Does it have buttons? Yes.
4.      Does it play music? Sometimes.
3.      Does it make noise? Yes.
2.      Is it used for entertainment? Yes.
1.      It is classified as Other.

```
> 2 votes

# Answer
You just play once with it, observe it, and you have the model. Try something non obvious, or simply cheat with answers.

**The game**: you think of something, and 20Q asks questions to find what it is.

They just collect the answers from the players. They have a collection of questions that are supposed to discriminate solutions. They ask questions to users, who chooses among 7 possible answers. Recall that with just 20 yes/no answers, you can discriminate 1 million different objects. And their questions have more answers that just two. The combinatorics of the answers will identify the right "something"to be guessed in the available collection. If the thing they are supposed to identify has not appeared before, they do not find it, recognize that they lost, ans ask what it is. Then it goes into the database, with all the user's answers to identify it the next time.

So they fail, but not twice on the same "something/someone/somewhere" to be guessed. Unless users give wrong answers to questions (the first time, or afterwards ...?).

It is probably slightly subtler, but I doubt it has much artificial intelligence, neural network or otherwise. A most elementary and simplistic form of machine learning, if one dares use the expression for it.

This is all pure guesswork from what I observed. No idea where you could read about it. Not sure there is anything worth reading anyway.
> 3 votes

---
Tags: machine-learning, neural-networks, data-mining
---


# Question
Title: Proving a language is context free by coming up with a context free grammar for the language
Let A and B be languages over $\sum$ = {0, 1, 2, 3}

Language A = {$(0U1)^a(1U2)^b(2U3)^c | a \geq b$}

Language B = {$(0U1)^a(1U2)^b(2U3)^c | a = c$}

Question: prove that A and B are context free

# Answer
The grammar for language B appears correct. But the grammar for language A is incorrect. This grammar will produce strings that are out of order and not in the language. Try:

$S\rightarrow AB$

$A\rightarrow (0U1)A|(0U1)A(1U2)|\epsilon$

$B\rightarrow (2U3)B|\epsilon$

My idea was to break it up into two sections and just deal with those.
> 2 votes

---
Tags: computation-models
---


title: Bankers algorithm - How does it work?

text:
# Question
Title: Bankers algorithm - How does it work?
I'm currently studying deadlocks and I'm trying to learn myself the bankers algorithm.

In this example my teacher goes to B first, then C and finally A.

He adds (I think) 2 (row b, Has) with 3 (free) and then gets the new Free value 5. After that he proceeds to row C where he adds 2 (row c, Has) with the free value 5 which gives us a new free value of 7.

After this he goes to the last row A and adds 3 to seven which gives him the free value of 10.

This does not cause a dead lock and I'm wondering why, Isn't he over the Max value of row A?

Here is another example in which the first image is included, but there is also one scenario when we get a dead lock. I don't really understand why since we still get 10 free like the rest of the examples.

Sorry if this is a bit confusing. I can simplify if its needed.

# Answer
> 2 votes
To understand this problem you have to understand the rules for the safety checks. I am not going to give a detailed explanation of these but you can go here to read more about it. I will try to give an explanation of why C request 1 is safe but A request 1 is not.

There is a value associated with a process and a resource called need. The need is an n-tuple where n is the number of different resources. In this case n is just 1. Calculating the need is just taking the max and subtracting the has for each resource. And there is a safety check that if no process has a need less than or equal to the n-tuple of available resources after a request then that request should be denied.

For C requests 1 it appears that the previous state is after B requests 1. In this C request 1 step we see A has a need (6), B has a need (1) and C has a need (4). Since there is only one resource the n-tuple of available resources is just (1) so this can be granted as B has a need of (1).

For A requests 1 the previous state is the initial state. We then calculate the need of A is (5), B is (2) and C is (5). And the resulting n-tuple of available resources is (1). There is no need which is less than or equal to this so we should reject it.

Be careful when reading more about the subject. The notation is often different, the letters A,B and C are often used to represent resources and p's will be used for processes. You will also be dealing with n-tuples of greater values.

---
Tags: algorithms, deadlocks
---


# Question
Title: Rule induction principles in Harper's PFPL
I have a few small questions about section 2.4 ("Rule induction") in Practical Foundations for Programming Languages (p. 19).

(1) In the rule induction principles for `nat`,

> To show P(a nat) whenever a nat, it is enough to show: (1) P(zero nat). (2) for every a, if (a nat and) P(a nat), then P(succ(a) nat).

why is the bracketed "(*a* `nat` and)" clause necessary (and similarly for `tree`)? This seems "natural" - we shouldn't need to prove things about syntactic entities that don't define `nat`s - but doesn't appear in the definition given of property *P* "respecting the rules" defining `nat`/`tree` (also on p. 19), which is how the rule induction principle is defined. In the proof of Lemma 2.1, the extra "*a* nat and" part has become part of the definition of the property *P* \- what's going on here?

(2) I don't understand the induction step of Lemma 2.1 (`succ(a) nat` implies `a nat`). If I were doing this proof, I'd just invert the rules for `nat` right away, or, using Harper's property *P*, say: If `succ(a)` is of form `succ(b)`, then by injectivity, `a` equals `b`, hence `b nat` as `a nat`, but injectivity hasn't been proven yet. It seems instead that Harper applies the induction hypothesis about `a` directly to `succ(a)` \- I must be missing something.

(3) In a more naive framework, Lemma 2.3 would just follow from sufficiency of the `= nat` relation rules ("inversion"), but I don't know how to write down a proof in this style. Why is induction even needed?

I'm sorry if these questions seem like nitpicking, but Martin-Löf/LF feels very foreign to me. If I squint and pretend I'm doing everything in a more "traditional" operational semantics, I can read other parts of the book (with slightly different proofs), but I feel I'm missing the point in doing so.

If these questions are too tedious to answer individually, are there other references on doing semantics in this style?

# Answer
> 2 votes
At the beginning of Section 2.4 the book explains that $\mathcal{P}(J)$ stands for a property of a *judgment* $J$. That is, the $\mathcal{P}$ in $\mathcal{P}(a\ \mathtt{nat})$ does *not* stand for a property of numbers, but a property of the judgment $a\ \mathtt{nat}$, which is the judgment that "$a$ is a number".

It just so happens that the inference rules for $a\ \mathtt{nat}$ precisely match those for numbers. Namely, the two rules defining the judgment $a\ \mathtt{nat}$ are $$\frac{ }{\mathtt{zero}\ \mathtt{nat}}$$ and $$\frac{a\ \mathtt{nat}}{\mathtt{succ}(a)\ \mathtt{nat}}.$$ Therefore, if we want to show that the *judgment* $a\ \mathtt{nat}$ has some property $\mathcal{P}$, then we need to show that the base case $\mathtt{zero}\ \mathtt{nat}$ has the property $\mathcal{P}$, and that whenever $\mathcal{P}(a\ \mathtt{nat})$ holds then $\mathcal{P}(\mathtt{succ}(a)\ \mathtt{nat})$ holds as well.

Or to put it the other way, the strange looking "$\mathtt{nat}$" is there because we are not talking about numbers, but about the judgments "expression $a$ satisfies the judgment $\mathtt{nat}$".

# Answer
> 1 votes
**Question 1**

The range of acceptable inputs for the property `P` is natural numbers, and therefore if a is not a natural number `P(a)` cannot be valid. Looking at it a different way, `P(J)` is true if and only if `P(J1)`,`P(J2)`,...,`P(Jn)` are all true. If `J1` isn't true (a isn't a natural number) then `P(J1)` cannot be true, and `P(J)` cannot be true either.

**Question 2**

The presentation of the proof is a little confusing. Our goal is to show that if `succ(a)` is true, then `a nat` is true as well. In order to prove this, the book defines a property `P(a nat)` so that if `a nat` is true and we can describe `a = succ(b)`, then `b nat` must be true as well. If we can prove this property, then P(a nat) is closed. Because we are now proving `P(a nat)`, we can proceed on the assumptions `a nat` and `a = succ(b)`.

Skipping the trivial case a = 0, if `succ(a) nat` and `a = succ(b)`, then `succ(succ(b)) nat`, which implies `succ(b) nat` which in turn implies `b nat`. Thus our property `P(a nat)` holds for each of the conditions, and is therefore closed.

**Question 3**

Suppose `succ(a1) = succ(a2) nat`. By Lemma 2.1, we know `a1 nat` and `a2 nat`, leading to `a1 = a2 nat`.

---
Tags: type-theory, semantics, induction, operational-semantics
---


# Question
Title: Calculate number of ways to color matrix using inclusion-exclusion principle
This was asked in a recent contest. The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same color. In other words, I want to count the number of different graph colorings of a grid graph: the graph of a $N \times M$ grid. The limits were $1 \le N,M \le 8$ and $1 \le K \le 1000000000$.

Is it possible to count the number of colors using the inclusion-exclusion principle, and if so, how? I saw another question that solves the special case (where $M=2$) using inclusion-exclusion, so I'm wondering if that kind of approach can be generalized here.

# Answer
> 1 votes
Not an answer, but related.

The number of colorings of a graph on $N$ vertices with $c$ colors is a polynomial of degree at most $N$ in $c$ known as the *chromatic polynomial*. As such, it can be calculated by evaluating it at $N+1$ points, say $c=0$ to $c=N$. Your program need $\binom{8+1}{2} = 36$ of these polynomial.

In some cases there are formulas for the chromatic polynomial, but in the case of grids it's an open question to find such a formula, see this question on math.se.

# Answer
> 1 votes
I would suggest you try using MINION, as suggested in the other question. It should be very simple to try and you might quickly find out whether it works or not.

Another possible approach might be to try dynamic programming. In particular, pick a column in the middle of the grid. Enumerate all possible ways to color that column. Then, count the number of ways to fill in the left half of the grid (recursively) and the number of ways to fill in the right half of the grid (again, recursing). You can use symmetry to reduce the number of ways to enumerate the middle column: for instance, if all of the colors in the middle column are distinct, then you only need to try one case (and multiply by $M!$); if there are only two distinct colors used in the middle column, you need to try $2^M$ cases; and so on. This seems like it might work for small enough grids. It'll explode as the grid size grows, but it's something you could try to see how well it scales.

---
Tags: graphs, combinatorics, counting, colorings
---


title: Print bottom view of a binary tree

text:
# Question
Title: Print bottom view of a binary tree
For a binary tree we define horizontal distance as follows:

```
    Horizontal distance(hd) of root = 0
    If you go left then hd = hd(of its parent)-1, and
    if you go right then hd = hd(of its parent)+1.

```

The bottom view of a tree then consists of all the nodes of the tree, where there is no node with the same `hd` and a greater level. (There may be multiple such nodes for a given value of `hd`. In this case all of them belong to the bottom view.) I'm looking for an algorithm that outputs the bottom view of a tree.

---

Examples:

Suppose the binary tree is:

```
         1
        /  \
       2    3
      / \  / \
     4   5 6  7
            \
             8

```

Bottom view of the tree is: 4 2 5 6 8 7

```
    Ok so for the first example,
    Horizontal distance of node with value 1: 0, level = 1
    Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
    Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
    Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
    Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
    Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
    Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
    Horizontal distance of node with value 8: 0 + 1 = 1, level = 4

    So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
    So for hd = -2, print 4
    for hd = -1, print 2
    for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
    for hd = 1, print 8
    for hd = 2, print 7

```

One more example for reference :

```
         1
      /     \
    2         3
   / \       / \
  4   5     6     7
 / \ / \   / \    / \
8  9 10 11 12 13 14 15

```

So the output for this will be : 8 4 9 10 12 5 6 11 13 14 7 15

```
Similarly for this example
hd of node with value 1: 0, , level = 1
hd of node with value 2: -1, level = 2
hd of node with value 3: 1, level = 2
hd of node with value 4: -2, level = 3
hd of node with value 5: 0, , level = 3
hd of node with value 6: 0, level = 3
hd of node with value 7: 2, level = 3
hd of node with value 8: -3, level = 4
hd of node with value 9: -1, level = 4
hd of node with value 10: -1, level = 4
hd of node with value 11: 1, level = 4
hd of node with value 12: -1, level = 4
hd of node with value 13: 1, level = 4
hd of node with value 14: 1, level = 4
hd of node with value 15: 3, level = 4

So, the output will be:
hd = -3, print 8
hd = -2, print 4
hd = -1, print 9 10 12
hd = 0, print 5 6
hd = 1, print 11 13 14
hd = 2, print 7
hd = 3, print 15

So the ouput will be:
8 4 9 10 12 5 6 11 13 14 7 15

```

---

I already know a method in which I can do it using a lot of extra space (a map, and a 1-D array for storing the level of the last element in that vertical line) and with time complexity of $O(N \log N)$. And this is the implementation of this method:

```
void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
{
     if(node == NULL)
             return;
     if(level == 1){
              if(lev[hd-min] == 0 || lev[hd-min] == l){
                      lev[hd-min] = l;
                      visited[hd-min].push_back(node->data);
              }
     }
     else if(level > 1)
     {
          printBottom(node->left, level-1, hd-1, min, visited, lev, l);
          printBottom(node->right, level-1, hd+1, min, visited, lev, l);
     }
}

int main()
{
    find the minimum and maximum values for hd via DFS

    int lev[max-min+1]; //lev[hd] contains the maximum level for which we have found nodes with this value of hd; initialized with 0's

    map < int, vector<int> > visited; //the nodes in the bottom view

    int h = height(root);

    for (int i=h; i>0; i--){
        printBottom(root, i, 0, min, visited, lev, i);
    }

    output visited
}

```

I am seeking help to do this in more optimized way, which used less space or time. Is there any other efficient method for this problem?

# Answer
First, you can get the time complexity down to ${\cal O}(n)$, while keeping the same space complexity. You can do this by filling `visited` in a single run of `printBottom`:

```
void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
         visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node
     }
     if(lev[hd-min] <= level){
         visited[hd-min].push_back(node->data);
     }
     printBottom(node->left, level+1, hd-1, min, visited, lev);
     printBottom(node->right, level+1, hd+1, min, visited, lev);
}

```

with the initial call `printBottom(root, 1, 0, min, visited, lev);`

If you insist on the nodes beig output in order of increasing value of `hd`, I don't think you can improve space consumption. However, if you allow a different order of output, you can get rid of `visited`, by first determining for each value of 'hd', which level should be output and then making another pass, printing the values that match:

```
void fillLev(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
     }
     fillLev(node->left, level+1, hd-1, min, lev);
     fillLev(node->right, level+1, hd+1, min, lev);
}
void printBottom(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] == level){
         cout << node->data;
     }
     printBottom(node->left, level+1, hd-1, min, lev);
     printBottom(node->right, level+1, hd+1, min, lev);
}

```

with calls `fillLev(root, 1, 0, min, lev);` and `printBottom(root, 1, 0, min, lev);`.
> 3 votes

---
Tags: algorithms, binary-trees
---


title: Is P closed under subwords?

text:
# Question
Title: Is P closed under subwords?
Given a language $L\subseteq \Sigma^\*$ in $P$, is the language

$subwords(L) = \\{v\in\Sigma^\* : \text{there exist } u,w\in \Sigma^\* \text{ with } uvw\in L\\}$

that consists of all subwords of words in $L$ also guaranteed to lie in $P$?

# Answer
> 1 votes
Hint: Let $L$ be the language consisting of a description of a Turing machine (bounded by $\\#$ on both sides) followed by a terminating computation (both description and computation are over $\\{0,1\\}$). What is the language $\mathit{subwords}(L) \cap \\#\Sigma^\*\\#$?

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


# Question
Title: Polynomial space complexity with exponential size witnesses
Define the complexity class $C$ to be the class of all languages that can be verified by a TM that has:

* Input tape: Read only, move in both directions.
* Witness tape: Read only, move only in one direction.
* Work tape: Read-Write, move in both directions.

The machine itself is deterministic (the guesses are the value of the witness tape). The space complexity is the size of the work tape, and is polynomial. We say the machine accepts an input if and only if there exists a setting for the witness tape, with which the machine accepts.

Prove: $C = \mathrm{PSPACE}$

Well, it's obvious that $\mathrm{PSPACE} \subset C$ since any TM $M$ can be converted into a TM $M'$ that simply ignores its witness tape and runs in the same space complexity as $M$.

However, I'm struggling with the other direction. The problem is that the witness can be exponential in the input and I can't see how we can enumerate over all witnesses using only polynomial space.

edit: I had a mistake, the witness tape can only be read in one direction.

# Answer
Hint: Use Savitch's theorem to show that PSPACE=NPSPACE.
> 1 votes

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


title: What is the Inversion Lemma

text:
# Question
Title: What is the Inversion Lemma
I am taking a programming languages course, and we have had to use the Inversion Lemma many times in our proofs of preservation. We have been given the Inversion Lemma in each of these examples, but is there a general statement of the inversion lemma that can be applied to any proof of preservation? Can someone write that out for me/explain it a little bit?

# Answer
> 3 votes
When you have a collection of rules, an inversion lemma lets you prove the premises of a rule from the conclusion. You can't just assume that inversion is true. You have to prove it by rule induction. However, classes will often give it to you because it is often tedious and easy to prove. The reason inversion doesn't always work is that there may be multiple rules which match the conclusion you are trying to use inversion on, and then you only know that the premises of one of those rules is true, but not which rule.

---
Tags: programming-languages, typing
---


title: O(f) vs O(f(n))

text:
# Question
Title: O(f) vs O(f(n))
I first learned about the Big O notation in an intro to Algorithms class. He showed us that function $g \in O(f(n))$
Afterwords in Discrete Math another Professor, without knowing of the first, told us that we should never do that and that it should be done as $g \in O(f)$ where g and f are functions. The question is which one of these is right, why, and if they both are, what is the difference?

# Answer
> 4 votes
There are two views on this, formal and pragmatic.

Formally, you always have $O(f(n)) = O(1)$ as long as $f : \mathbb{N} \to \mathbb{N}$ since $f(n)$ is just a number, i.e. a constant function. $O(f)$, on the other hand, does what you want.

However, you often want to indicate which variable goes to infinity¹. If you let $f : x \mapsto x^2$ and state

$\qquad\displaystyle 2n + k \in O(f)$,

which variable should identify with $x$? Writing

$\qquad\displaystyle 2n + k \in O(f(n))$

can be used (given mutual understanding) to clarify.

Personally, I'd propose to use

$\qquad\displaystyle 2n + k \in O(f)$ for $n \to \infty$

or

$\qquad\displaystyle 2n + k \in O\_n(f)$.

However, use of Landau notation is (sadly) not meant to be rigorous most of the time², but is instead used as a lazy shortcut.

---

1. Never mind that Landau notation gets into trouble when two independent variables are around, anyway.
2. Meaning that many people use it in a sloppy way. Not saying that that's a good thing. Many questions on this site are based in wrong understanding of terms that are founded in teachers promoting sloppiness in the name of (alleged) clarity (imho).

---
Tags: terminology, asymptotics, landau-notation
---