# Question
Title: What is the common terminology to refer to the nth ancestor of a tree root?
Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a tree's subtrees.

For example,

> ### Definition
>
> As a data type, a tree has a value and children, and **the children are themselves trees**; \[...\] Due to the use of references to trees in the linked tree data structure, trees are often discussed implicitly assuming that they are being represented **by references to the root node**, as this is often how they are actually implemented.

And also,

> ### Terminology.
>
> "The **height of a node is the length of the longest downward path to a leaf from that node.** The height of the root is the height of the tree. \[...\] **The root node has depth zero**..."

The former implies subtree n could be refered to as the nth decendant of root or the nth tree. Can I be sure subtree only refers to decendants and not other branches at the same distance from root?

The latter refers to the height counting from the root (0). Again, height sounds uncommon to me. As in, *"Please refer to the nodes at height 4 to see..."* Since a tree is commonly displayed from the root branching downward, I'm predisposed to bias against the term *height* versus my preferred notion of *depth*.

# Answer
Commonly used phrases include,

* "vertex at height $h$",
* "vertex at depth $d$",
* "vertex at distance $d$ from the root".

"Subtree $n$" doesn't make any sense, except as the $n$th element in some enumeration of subtrees.

By the way, I'd avoid using $n$ for anything other than the number of vertices in the graph. That bit of notation is so standard in graph theory that it's confusing for the reader to have $n$ mean anything else.
> 0 votes

---
Tags: graphs, terminology, trees
---


title: Perceptron learning rule doesn't work

text:
# Question
Title: Perceptron learning rule doesn't work
i'm a little bit lost ... can you help me ?

So I have this table of date (each row give a point with its group)

So i took a random weight let's say : \[1, -2\] H = 1 if n =\< 0 0 otherwise

a= H(\[1,-2\]\[6,3\]) = H(0) = 1 but the target output is 0 ... so we have to update the weight: w -\> w - p = \[5 , -5\] . Next :

a= H(\[5,-5\]\[3,3\]= H(0)=1 the problem is : there the target output is 1 so we don't have to update the weight , but that's strange because the \[5 -5\] vector doesn't draw a linear separation between the 2 groups ...

Thanks for your help ? :)

# Answer
I think you're mixing up the weight vector $w$ and the actual hyperplane defining the decision boundary. The way to interpret $w$ is as a vector which is orthogonal to any vector lying on the hyperplane. See these slides for some visualization.

As you've said, the decision is defined by $1$ if $w\_1 x + w\_2 y \> 0$ and $0$ otherwise. So to find the actual hyperplane (decision boundary) we can just solve for the place where the decision changes, which is at $0$. Using your $w$ we have $$ \begin{align\*} w\_1 x + w\_2 y &= 0\\ \implies 5 x + -5y &= 0\\ \implies x &= y. \end{align\*} $$ So the decision boundary is given by the line $y = x$. Plotting this with your points we see that this $w$ does indeed define a separating hyperplane.
> 4 votes

# Answer
If you're confused by the algorithm, the wikipedia article on Perceptron has some easy to understand Python code and an example to help guide you through calculations.
> 1 votes

---
Tags: algorithms, machine-learning, neural-networks
---


# Question
Title: How many size $s$ circuits from $\{0, 1\}^n \to \{0, 1\}$ are there?
For simplicity, we can assume that only NAND gates are allowed. An asymptotically correct solution is all I really need.

Thanks!

# Answer
> 2 votes
Hint: Each of the $s$ gates is connected to two other gates or inputs, for a total of $(s+n)^2$ possibilities. This gives a rough upper bound which isn't tight, but is good enough for many purposes, for example to show that some functions require circuits of size $\Omega(2^n/n)$. See Steurer's notes, for example.

---
Tags: combinatorics, circuits
---


# Question
Title: Traveling Salesman: how to use a lower bound?
Let me preface this question by giving some helpful background material.

I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the solution the algorithm would attain by making greedy choices as an upper bound, and comparing this bound to the current best solution. If the bound attained using this heuristic is better than the cost of the best known solution, we continue exploring the partial solution. Otherwise, we prune and discard. Note that the greedy solution attained is always valid.

The above link mentions a method for finding a global lower bound. This is fairly intuitive: for each node, we add to the bound the sum of the two minimum cost edges to other nodes (representing the cheapest in/out edges, if you will) and divide by two to avoid double counting. The solution implied by this global bound is almost never a valid solution but instead gives a hard limit on the lowest cost we could ever hope to attain.

Here's how I'm currently trying to calculate a local lower bound (a lower bound for a partial solution) with cost $C(S)$.

* Set `bound` to the current accumulated cost, $C(S)$
* For each unvisited node, add to `bound` the sum of the two least cost edges, making sure that the edges selected don't lead to a node already visited
* return `bound/2`

Here's my question: How is the above solution different from the greedy bound? Maybe a better lower bound would be to add to `bound` the sum of the two least cost edges, paying **no attention to whether these edges lead to nodes already visited**. Also, how do I actually use this bound to prune the search space? Do I compare the local lower bound computed for a partial solution with the global lower bound, pruning if $L(S) \< GL$ or if $L(S) \> C(B)$, or if $L(S) \> L(B)$? (here $GL$ corresponds to the global lower bound; $L(S)$ computes the local lower bound on a partial solution; $C(B)$ represents the trip cost on the best known solution; $L(B)$ is the lower bound on the best solution). Also, how will $L(S)$ ever be less than the global lower bound (i.e. an infeasible solution) if we only ever use (valid) edges to cities we haven't yet visited?

Comments and suggestions on using this lower bound as well as its efficacy would be very much appreciated. Thank you.

# Answer
You want a bound that depends upon the partial choices made so far. So, I suggest you compute a bound that is based upon (1) the sum of the edges in the part you've chosen already, plus (2) a greedy bound for the remaining unvisited nodes (for each node, sum of the two least cost edges, divided by two); or something like this. This will be different from the greedy bound applied to the entire graph, because of part (1).
> 2 votes

---
Tags: complexity-theory, optimization, lower-bounds, traveling-salesman, branch-and-bound
---


# Question
Title: Can Java be accurately described as statically and dynamically typed?
Java seems to be categorized as a statically-typed language\[1\], but I'm wondering if it would be accurate to describe it as generally statically-typed but having some dynamic typing because of the run-time type checks performed when downcasts are performed.

# Answer
> 2 votes
Yes, that would be accurate. Also, array writes involve a runtime type check, to deal with problems associated with covariant array types.

---
Tags: terminology, programming-languages, typing, type-checking
---


title: "Grammar inference" for 2-D images

text:
# Question
Title: "Grammar inference" for 2-D images
Others have studied the following question: given a set of words $w\_1,w\_2,\dots \in \Sigma^\*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in some sense, and is as small as possible. In the special case where we have a single word $w \in \Sigma^\*$, if the grammar generates exactly the word $w$, we can think of this as a compression algorithm that compresses the word $w$ to the grammar produced by this inference algorithm. Of course, each word is a one-dimensional sequence of symbols.

Now consider a two-dimensional array of symbols, say an array $A\[1\ldots m, 1\ldots n\]$ where each $A\[i,j\] \in \Sigma$. Is there any corresponding algorithm that could be used to find a grammar of some sort that generates $A$? Could this be used as a compression algorithm for compressing images, i.e., one that compresses a two-dimensional image to its corresponding grammar?

I'm not even sure what kind of grammar would be suitable. Is there an analog of regular or context-free grammars that generates a two-dimensional output instead of a one-dimensional output? I've done some searching, and haven't found anything obvious.

* Of course we could linearize the image, by concatenating the rows of the array, to get a one-dimensional sequence, and then apply any of the above techniques -- but this does not preserve locality. In other words, elements that are vertically adjacent will no longer be near each other after this transformation. So this transformation does not seem useful.
* Perhaps we could build a quad-tree over the array and then consider tree automata over that quad-tree? Is there a grammar inference algorithm for such tree automata over quad-trees?
* Alternatively, it seems like there might be a natural extension of context-free grammars to two-dimensional output: just make the right-hand side of each rule be a two-dimensional array of terminals and non-terminals of arbitrary size, and then apply the obvious generation algorithm. Do such grammars have a standard name? Is there a grammar inference algorithm for such grammars?

# Answer
I'm researching related ideas using context-free grammars at the moment, so I might be able to give you some things to think about by describing the approach I've taken (which is just one approach).

Firstly, I use rules that describe the production of multisets and not sequences (or trees in fact). So whereas a conventional production rule:

$s \rightarrow abc$

would produce the (ordered) string 'abc', the rule below would produce an unordered set of the same symbols

$s \rightarrow \\{a, b, c\\}$

In such a grammar non-terminal symbols can operate as variables in the same way as sequential grammars, e.g.:

$ s \rightarrow \\{X, c\\}\\ X \rightarrow \\{b, a\\} $

Now, going back to 2D images. Perhaps surprisingly, it turns out you can encode an image as an (unordered) collection of non-terminal symbols, each producing a (unordered) multi set that describes each pixel. In your question you describe a set of terminal symbols that describes that possible values of each pixel, let's say $\Sigma=\\{0,1\\}$. I'm going to add to that 2 terminal symbols $x$ and $y$, each of which representing an offset of 1 pixel from the origin on each axis, so $\Sigma=\\{0,1, x, y\\}$.

Now consider the pixel $A\[2,2\] = 1$. This can be encoded in the grammar scheme I describe using a multi set production:

$p \rightarrow \\{x, x, y, y, 1\\}$

So, you could encode a whole image this way. It's easy to imagine the amount of bloat you'd get in such a grammar. However, it is possible to compress the whole grammar by using a hierarchy of production rules that can be inferred. For example, take the derivation of the point $A\[18, 9\]=1$

Instead of:

$p \rightarrow \\{x, \text{(repeat 17 more times)}, y, \text{(repeat 8 more times)}, 1\\}$

you can have:

$p \rightarrow \\{D, A, G, y, 1\\}\\ A \rightarrow \\{x, x\\}\\ B \rightarrow \\{A, A\\}\\ C \rightarrow \\{B, B\\}\\ D \rightarrow \\{C, C\\}\\ E \rightarrow \\{y, y\\}\\ F \rightarrow \\{E, E\\}\\ G \rightarrow \\{F, F\\}\\ $

With of course the non-terminals $A$ to $G$ being reused to describe multiple points. So actually something that looks like it would be hideously inefficient can be compressed very efficiently. It is possible to easily infer such a grammar from a series of points (this is the subject of my research), using similar techniques as normal sequential grammar inference.

The cool feature of this type of grammar is it is possible for the grammar to encode complex patterns that are non-sequential (in this case graphical) in nature.

This is all a work in progress but it might help you with your problem.
> 1 votes

---
Tags: formal-languages, formal-grammars, tree-grammars
---


# Question
Title: Compression technique exploiting common similarities
I asked this on StackOverflow, but it was determined more appropriate to post here.

So it goes like this..

For people concerned about users having slow connections and timeout issues, it is known that it can't be just always solved with minification, latency reduction etc..

I'll try to keep this question as short as possible, however retaining clarity where possible.

I've thought about a technique to further reduce uncompressable files (like mp3 and mp4), bear with me please.

What if we could skip chunks/bits/frames of a file being similar and rebuild them locally? Ok, let's explain it with a short example.

Assume you have many files in your computer, and that 3 of them are videos with a knife and a guy with blue eyes non-evenly spread over many frames. You go to this site and there's a post.. this post features a video of a serial killer's life. It is totally unrelated to the videos you have on your pc, except for the killer's knife, and the victim he kills having blue eyes.

What we could do here, is, remotely and locally make the videos (in this case) have "metadata blocks" about the most frequent frames and do a bidirectional check. If the two happen to have the same/similar blocks, the remote server just sends the new blocks, and, we rebuild the missing ones locally.

Like this:

```
Remote file =
    MetadataBlock:
        knife:
            from (minute 3.12) to (minute 3.59)
                and from (minute 4.40) to (minute 5.20)
        blue eyes:
            from (minute 0.06) to (minute 0.60)
                and from (minute 1.20) to (minute 1.30)
                and from (minute 6.50) to (minute 6.58)

Local file =
    MetadataBlock:
        knife:
            from (minute 8.00) to (minute 8.20)
                and from (minute 40.00) to (minute 40.02)
                and from (minute 42.00) to (minute 42.50)
        blue eyes:
            from (minute 3.05) to (minute 3.15)
                and from (minute 6.08) to (minute 7.40)

Local file.knife.total = 1.12 minutes

Local file.blue_eyes.total = 1.42 minutes

FileTotal = Local file.knife.total + Local file.blue_eyes.total

FileTotal (2.54) * 3 / 1.5 = 5.08 minutes

```

---

Remote server remove the blue eyes and knife bits/frames, appending instructions to build them locally from MetadataBlock.

As soon as the file is received, the os reads the instructions and execute them like:

*"Replace MetadataBlock(from(knife.minutes)) with local file 1 MetadataBlock(from(knife.minutes))"*

, the same goes for other metadata blocks such as blue eyes, black hair, shirt color etc..

Is a technique like, or similar to this feasible, or just pure utopia?

# Answer
> 2 votes
Of course it is possible.
For example, you could define the trailer of a movie as the sequence of movie sequences it shows plus the trailer-specific overhead it uses. If the movie itself is at hand when you want to watch the trailer, then everything goes well.

Yet in general...either you would have to add tons of metadata to each file (e.g. "contains sequences in which blue-eyed guy fiddles around with a knife"), thus increasing all files significantly, or you would have to run some pattern-matching algorithms over all your movie database. And your file will be very context-dependent, i.e. if one of the files you rely on changes, then all hell breaks loose. That does not sound practical to me.

Note that most lossless compression techniques also share patterns that appear across different files. So if you gzip a set of very similar mp3s, then some notable compression should happen.

---
Tags: data-compression, video
---


# Question
Title: Canonical infinitely ambiguous languages
In an article I am currently reading the grammar

**S → SS | a | ε**

is being described as canonical infinitely ambiguous. The infinitely ambiguous part I have no problem recognizing, but does "canonical" mean? Does it mean "typical", "standard example" etc.?

# Answer
> 1 votes
I think your understanding the use of "canonical" here as "standard example" is correct; similarly, grammars for parenthesis matching or palindromes are canonical examples for context-free grammars, generally.

---
Tags: formal-languages, terminology
---


# Question
Title: Unknown notation "$e^T$" in a machine learning paper
I'm trying to understand the material in "A Dual Coordinate Descent Method for Large-scale Linear SVM" by Hsieh et. al. (link to paper) There is an equation for the Dual form of an unconstrained optimisation problem,

$$ f(\mathbf{\alpha})=\dfrac{1}{2}\mathbf{\alpha}^T\bar{Q}\alpha-e^T\alpha $$

I don't understand what the $\mathbf{e}^T$ means, it's not explained in the surronding text, so I assume it's just some common notation. Later in the paper $\mathbf{e}\_i$ is defined as $\mathbf{e}\_i=\[0,\ldots,1,0,\ldots,0\]^T$, so maybe it's some sort of selector term? Not sure if this second mention is even related.

Please may someone explain to be what the $\mathbf{e}^T$ bit is doing in this formula? Thank you for your time.

# Answer
> 9 votes
The superscript $T$ is the *transpose* operation. The vector $e$ is probably the constant one vector, though this is not standard notation and so it would be mentioned in the definitions part of the paper. Overall, $e^T\alpha = \langle e,\alpha \rangle = \sum\_i \alpha\_i$.

# Answer
> 3 votes
Although it has already been answered, I would just like to point out that the answer is definitely correct. On the bottom left column of page 12 the authors state "$e$ is the vector of ones".

---
Tags: terminology, machine-learning, optimization
---


# Question
Title: Compression of non-adjacent structure using grammar
I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string and use recursive substitution with non-terminal symbols to achieve compression.

What I'm wondering is whether there are classes of grammar and inference methods that are able to exploit sequential patterns that are based on non-adjacent co occurrence.

Take the following input sequence:

> XaXbXcYaYbYcZaZbZc

No two adjacent symbols co-occur more than once anywhere here, so the sequential compression techniques I mention will not compress this string any further, however there is a clear pattern to the sequence and it must be compressible. How is it possible to do so?

# Answer
**Note**: *This answer was written based on the description of Sequitur in wikipedia which is apparently grossly simplified, compared to another description I read in a more technical paper "Detecting Sequential Structure" by Nevill-Manning and Witten. Some of the techniques they use on strings (encoding w.r.t. immediate context) seem very similar to the ones I suggest for AS trees below. It seems however that this paper aims at identifying general grammar structures rather than simple compression of a given string. Hence I am not sure what is the reference to be used when replying to the question asked.*

Asked in such a general way, the answer is most probably yes, there must be "a class grammars and inference methods that are able to exploit sequential patterns that are based on non-adjacent co occurrence". At least some such patterns, if you introduce appropriate operators. For example a distributive operator could handle your example. But we will try it below with context-free rules.

The question is more to determine which ones might be interesting in providing significantly better compression, and **in what context**, as it is most likely that they will be more costly in general, at least during compression.

However, a first remark to be made is that considering the grammar currently used as context-free (CF) is correct, but somewhat a misleading statement as they are a very small subset of CF grammars, since they do not use recursion.

So one question is whether a more powerful grammatical formalism will make a difference when recursion is removed from it. Is it really a grammatical issue, or something else, since the number of strings in the language will always be one?

Another point is that CF grammars can already handle non-adjacent co-occurrences, at least some types of such co-occurrences. There are designed for that. The problem the question raises sometimes lies with the inference method rather than with the grammatical formalism.

You state that the existing algorithms look for *adjacent* digrams. I have no idea whether they do only this, So I am assuming you are right. But CF-ness does not require such adjacency. If can match parentheses independently of what occurs in between. If you allow for non adjacent digrams, you can get parenthesizing which CF grammars handle very well. For example (considereing actually a trigram), if you consider HTML text, you could encode

```
    ... <script ..u.. > ..v.. </script> ...

```

with the rule:

```
    S -->  <script $1 > $2  </script>

```

and rewrite the string as

```
    ... S ..u.. ) ..v.. ) ...

```

where the closing parenthesis is a reserved symbol not in the text, common to all such discontinuous digrams or trigrams.

Of course, this assumes that you have an algorithm (actually a CF parser) to detect which closing elements go with the opening ones, when encoding the original string.

Having a unique closing parenthesis for all such rules may actually give some extra compression.

Whether that will buy you much more compression is a different issue. It is most likely that algorithms are kept simple because added sophistication will have diminishing returns, but not diminishing costs.

*(The following is a natural extension of the above, though not a direct answer to the question)*

More generally, some formal documents obey the constraints of a known grammatical structure. For example a program may be represented as an astract-syntax tree (AST). Then one way of encoding it is to start from the AST to first represent it as a big formula in prefix notation, which does away with all the keywords to begin with. Furthermore, you can save on the encoding size of operators (syntactic constructs) as the operators permitted in a given context are often only a small subset of all the syntactic operators of the language. Hence the operator encoding can be chosen with respect to this limiting context, reducing the number of necessary bits. This technique dates back to the 1970-ies.

This idea of using parenthesized context to reduce the size of some encoding symbols could possibly be used in the string oriented case as the HTML example above (which actually encodes a tree structure).

**Compressing (?) the given example with our suggested extension**

The string to be compressed is

```
    XaXbXcYaYbYcZaZbZc

```

Create the rule

```
    S --> $1 $2 $1 $3 $1 $4

```

It allows to represent XaXbXcY as SX)a)b)c). Note that, being a common symbol, the ")" will be encoded with few bits. It can even be omitted if the length of an argument is fixed. The whole string becomes: SX)a)b)c)SY)a)b)c)SZ)a)b)c)
Then create as usual:

```
    A --> )a)b)c)
    B --> AS

```

and the given string can be coded as:

```
    SXBYBZA

```

Of course, such a compression technique must be used only when the given pattern is frequent enough to justify the cost of creating the rules. On such a small example, the cost exceeds the benefit.

Note that this encoding imposes some constraints on the use order of rules for decoding, so that arguments are passed correctly to the rules. The idea is to avoid that the non-terminal of a non-adjacent rule misappropriate the wrong closing parentheses. One way is to make sure that the substrings used as arguments no longer contain non-terminals.

It seems difficult to proceed differently if multiple constituents have to be reinserted in distinct parts of the string.
> 1 votes

# Answer
Grammar-based compression (context-free) is alwasy looking for repetitions and is blind for other "patterns"..
In your example "XaXbXcYaYbYcZaZbZc" a position based compression should be more senseful. For example the following "position rules" are generating your string..

> i=0,1,2:
> pos(X)=1+2i
> pos(Y)=pos(X)+6
> pos(Z)=pos(Y)+6
> pos(a)=2+6i
> pos(b)=pos(a)+2
> pos(c)=pos(b)+2

Rules like that can be stored efficiently and they are easy to decompress.
(In general the best compression is not computable since the so-called Kolmogorov-complexity is not computable. It is always a question of the type of compression..)
> 1 votes

# Answer
Your aims in this case are a bit contradictory. Note that the patterns you are trying to compress are inherently context-sensitive, but you are trying to do so with context-free grammars.
> 0 votes

---
Tags: formal-languages, formal-grammars, data-compression
---


# Question
Title: If $\log xy=\log x+\log y$ then why multiplication is harder than addition?
Someone told me that the $\log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $\log x+\log y$ since $\log xy=\log x+\log y$. How this can make the calculation easier? Maybe from a mathematician point of view but what about a computer scientist's point of view?

If it makes the calcualtion easier then why people do not use it to simplify the complexity of the multiplication algorithms?

From my own thinking, this transformation makes the calculation more difficult. How can we calculate the $\log x$ and $\exp x$ functions in a computer?

Am I right? Any suggestions please? Thank you for your time.

# Answer
> If $\log xy = \log x + \log y$ then why is multiplication harder than addition?

That's not a fair comparison: you're not comparing like with like. If you, instead, phrase it as "If $xy = \exp(\log x + \log y)$ then why is multiplication harder than addition?" then the answer is obvious. Multiplication, done that way, is harder than addition because doing addition just involves doing addition, whereas multiplication involves doing addition, taking logs twice and exponentiating.

> How can we calculate the $\log x$ and $\exp x$ functions in a computer?

The main methods are to either use something like a Taylor series or table look-up and interpolation. Taylor series express functions as sums, e.g., $\exp x = \sum\_{i=0}^{\infty} x^i/i!$. Add up as many terms as you need to get the desired level of accuracy – note that this involves many additions and many multiplications. Table look-up and interpolation is essentially the same way that paper log tables work. To calculate, say, $\log 4.3$, you'd look up $\log 4$ and $\log 5$ and approximate $\log 4.3$ as being three-tenths of the way between them. (In reality, the table would have more decimal places.) This involves a few additions and multiplications, and a lot of memory.
> 5 votes

# Answer
Logarithms were used to make computation easier at a time when computers were not available. Even in the twentieth century, when mechanical machines became available to do arithmetics with much precision, they remained so expensive, and often cumbersome, that most people did not use them. The mechanical hand held calculator doing the four arithmetic operations did not appears before the end of the second world war (this machine, called the Curta, was actually designed in a concentration camp, which saved some lives). Since most calculations did not require too much precision, many people simply used slide rules, or tables of logarithms. The typical cartoon of a scientist or engineer whould show him with the slide rule in his front pocket.

I am old enough that I did not have hand calculators at school (computers still used more space than my classroom). What I had was a slide-rule, which is based on logarithms. It did not give a very high precision (at best something like $10^3$, i.e., 3 decimal digits), but it was invaluable to do problems in physics. Numbers were read directly on the slide rule, that essentially can add lengths.

For more précision, we would use tables stored in books. That gave 4 digits, plus one with interpolation (as I recall). We also has direct table for logarithms of trigonometric functions.

This was well organized, and the cost of computing logs and exponentials with the tables was nothing compared to the savings of not doing multiplications by hand. It was actually free, with direct reading of graduations, on the slide-rule.

This was not a mathematician viewpoint, but a physicist viewpoint, or that of any person having to do much calculation involving multiplications, such as astronomers, or people mapping the land (which probably took several centuries).

I did not check, but I would guess that numerical algorithmic design at the time must have been much influenced by the idea of minimizing translation to and from logarithms. I would guess we were told in class to be careful about that.

Considerable effort was also spend in building very precise tables. By hand, of course, at least until mechanical arithmetic machines became available. According to wikipedia, despite a large number of earlier prototypes, the calculator industry did not start before the middle of the 19th century.

This all started with the invention of logarithm by John Napier at the beginning of the seventeenth century. His contact with astronomer Tycho Brahe who was at the time mapping very accurately the motion of celestial bodies (so that Kepler and Newton would have the data for the work that made them famous), and other such person, may not have been foreign to his invention of this most remarkable computation tool.

The fact that logarithms can make multiplication easy was certainly one very important factor in the development of science and technology for nearly 3 centuries. But not knowing exactly who used it and when, I cannot make a more precise statement.
> 6 votes

---
Tags: algorithms, complexity-theory, reference-request, education
---


# Question
Title: How do you describe a language that is generated by Context Free Grammer
I am familiar with describing Regular Expressions but when it comes to describing CFG I get confused. Do you describe it in words like you would regular expressions or do you do something like this ?

this is the CFG I am trying to describe

```
S -> SS
S -> XXX
X -> aX| Xa| b

```

I was thinking something like this

```
S-> SS
  ->XXXS
  ->aXXXs
  ->abXXS
  ->abXXS
  ->abXAXS
  ->abbaXS
  ->abbabS
  ->abbabS
  ->abbabXXX
  ->abbabbXX
  ->abbabbbX
  ->abbabbbb
  ->abbabbbb

```

# Answer
Hint: How many $b$s are there in each word generated by this grammar?

Guidance: What is the language generated by $X$? What is the language generated by $XXX$? What is the language generated by $S$?
> 1 votes

---
Tags: context-free
---


# Question
Title: Construct a digraph given its in-degree and out-degree distribution
Could anyone help me with this algorithmic problem:

Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph can allow self loops but not parallel edges.

Here's an example:

```
Vertex A: in=1 out=1
Vertex B: int=2 out=2

```

For which we can construct this graph:

```
A => B
B => A
B => B

```

Here's another example:

```
Vertex A: in=0 out=1
Vertex B: in=1 out=1

```

Here, we obviously cannot construct such graph.

I have been scratching my head around this problem. For an undirected graph, there exist a simple algorithm to solve this problem but I cannot find any way to derive a solution for directed graphs.

I have the intuition that we could find a matching algorithm in the bipartite graph representing the in and out edges of the graph and where each out-edge would be matched to an in-edge.

However the usual approach can produce a graph with parallel edges.

For example 1, a valid solution could be:

```
A- A+: A => A
B- B+: B => B
B- B+: B => B

```

Which is not a valid graph.

Also, please note that I am more interested in determining if a valid solution exists. It's not necessary to provide or construct such solution.

# Answer
The following remarks are taken from a paper by Berger. I assume that you don't allow parallel loops.

The idea is to frame the problem on bipartite graphs. One side of the bipartition consists of the "inside" of vertices, the other of the "outside". Each vertex $v$ has two copies $v\_-,v\_+$, and we want $d(v\_-)$ to be the indegree of $v$, $d(v\_+)$ to be the outdegree of $v$. The existence of such a bipartite graph is the the focus of the Gale–Ryser theorem, which gives an efficient algorithm.

A similar criterion for the case in which loops are forbidden also exists, see Berger's paper quoted above.
> 5 votes

---
Tags: algorithms, graphs
---


# Question
Title: Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$?
Is it possible that $\mathsf{P} \not = \mathsf{NP}$ and the cardinality of $\mathsf{P}$ is the same as the cardinality of $\mathsf{NP}$? Or does $\mathsf{P} \not = \mathsf{NP}$ mean that $\mathsf{P}$ and $\mathsf{NP}$ must have different cardinalities?

# Answer
> 78 votes
It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\\{n\\}$ for $n \in \mathbb{N}$ are in P), we get that P and NP are both countable.

# Answer
> 2 votes
If you are concerned about the size of two sets P and NP, the size of both these sets is infinite and equal.

If these two sets are equal, then their size is equal as well. If they are not equal, since they are countable then their cardinality is equal to the cardinality of natural numbers and equal.

So, in either case, their cardinality is equal.

# Answer
> 0 votes
I work in mathematics mainly and have only a bit of familiarity with this type of problem. However, set theory is one of my favorite areas of study, and this seems to be a set theory question.

So, to begin with, both P and NP are countably infinite as others have pointed out before. So, it does not make sense to discuss the cardinality of P and NP any further.

However, in general:

Set inequality does not inform one about the size of a set. Take for instance, $A=\\{1,2,3\\}$ and $B=\\{4,5,6\\}$. $A\neq B$, but $|A|=|B|$. Consider also, $C=\\{1,2,3\\}$ and $D=\\{4,5\\}$. $C\neq D$, and $|C|\neq|D|$.

However, by definition, set equality does inform us about cardinality. If $A=B$, then $|A|=|B|$. Consider the case of $A=\\{1,2,3\\}$ and $B=\\{1,2,3\\}$. $A=B$, and $|A|=|B|$.

If two sets are countably infinite, then they share the same cardinality. P and NP are both countably infinite, so that pretty much sums that up.

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


title: NTIME(f) subset of DSPACE(f)

text:
# Question
Title: NTIME(f) subset of DSPACE(f)
As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$?

Can anyone point me to a proof or outline it here? Thanks!

# Answer
> 5 votes
Here is an expanded version of Igor Shinkar's comment. The simplest way to simulate a non-deterministic machine running in time $f(n)$ and space $s(n) \leq f(n)$ uses $s(n) + 2f(n) + O(1)$ space. We enumerate over all possible coin tosses, simulating the original machine on each of them; this requires space $f(n)$ for storing the coin tosses, and $s(n)$ space for simulating the actual machine. There is a slight difficulty here: when the coin tosses are "read" by the (original) machine, we need to mark somehow where we are in the sequence of coin tosses; we can use an additional bit per coin toss. It is probably possible to optimize this even further.

If we're careful, we might be able to get something even better, since in each run of the program, the total number of coin tosses and the total space used add together to at most $f(n)$. I suspect it's possible to run the simulation in $(1+o(1))f(n)$ space. Perhaps we will need to assume something like $f(n) = \Omega(\log n)$ for that.

As Igor mentions, usually resource-bounded classes are only defined "up to big O", so that the result, which uses space $O(f(n))$, is still in $\mathrm{DSPACE}(f(n))$.

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


# Question
Title: Minimum path between two vertices passing through a given set exactly once
Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P\_1, P\_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P\_i\in A$ that minimizes $\mathrm{dist}(S, P\_i) + \mathrm{dist}(D, P\_i)$? In addition, the overall path from $S$ to $D$ should contain only one node from the set $A$. What is an efficient algorithm for this? I don't want to go with brute-force approach.

# Answer
The following answers the variant which requires passing through the set *exactly* once.

Make two copies of the graph. Remove all edges incident to two vertices of $A$. Orient all edges incident to $A$ in the first copy toward $A$, and all edges incident to $A$ in the second copy from $A$; other edges are bidirectional. Connect both copies of each vertex in $A$ with a zero-weight edge going from the first copy to the second copy. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

Using Dijkstra's algorithm, the complexity of this approach is $O(E+V\log V)$. In comparison, the trivial algorithm that tests all vertices in $|A|$ one at a time needs to run Dijkstra's algorithm $|A|$ times, unless the graph is unweighted, in which case one can use BFS instead in time $O(E|A|)$.

---

Here is an alternative solution, using only undirected graphs. Start by deleting all edges inside $A$. Add $M$ to the weight of all other edges incident to $A$, where $M$ is larger than the sum of all weights in the graph. Run Dijkstra's algorithm twice to find the shortest path between $S$ and any vertex in $A$, and between $T$ and any vertex in $A$; in both cases, the shortest path passes through no other vertex in $A$, due to our adjustment of the weights. Now go over all vertices $A$ and find the shortest path from $S$ to $T$ via a vertex in $A$.

This algorithm also runs in time $O(E+V\log V)$.

---

The following answers the variant which requires passing through the set *at least* once.

Make two copies of the graph. Connect both copies of each vertex in $A$ with an edge of zero weight. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

The complexity is $O(E+V\log V)$, or $O(E+V)$ if the original graph is unweighted (in this case, we modify the construction so that the parallel $A$-edges have unit weight; this is harmless in terms of computing the shortest path).
> 5 votes

# Answer
One way of doing this would be reducing it to |A| shortest path problems. Every shortest path would be on the subgraph G - A + {Pi} for a Pi. This will give minimum \[ distance(S, Pi) + distance(D, Pi) \] for that Pi. Choose the Pi for which the shortest path is minimum.

EDIT: As @collapsar pointed out, this will only work if distance(S, Pi) does not include nodes in A-{Pi}. Not the answer you were looking for but it might give some ideas.
> 1 votes

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


# Question
Title: Boosting algorithms: Confusion between "weak classifiers" versus "number of boosting rounds"
I've been reading up on boosting algorithms.

I understand that the main crux of the algorithm is to build weak classifiers that are slightly better than random guessing, and then to add them up so that we end up with a strong classifier. This is done via "boosting rounds".

With different papers using different variables, like *k*, *n*, *m*, etc, it's gotten a bit confusing.

I just want to confirm, if I run a boosting algorithm for, say 150 rounds, is that equivalent to saying that I'm training 150 *weak classifiers*? I mean, is a weak classifier the output of one boosting round?

# Answer
I went back to the original paper from the literature by Schapire (http://www.cs.utah.edu/~piyush/teaching/brief\_intro\_boosting.pdf) and it does sound like a weak classifier is the output of a boosting round. Consider how the output of the overall classifier is $$H(x)= \text{sign}\left(\sum\_{t=1}^T\alpha\_th\_t(x)\right)$$ which is expressing a threshold for the sum of $T$ weak classifiers.
> 1 votes

---
Tags: algorithms, classification
---


# Question
Title: How to optimally seperate a student body?
Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with students from Group 2.

I was thinking about creating a source node *s*, and creating a node for each person ($p\_i$) - followed by hooking up the *s* to each $p\_i$. Then I would create, another series of nodes for each person ($q\_i$) and hook up each $p\_i$ to each $q\_i$ if $p\_i$ **doesn't** want to work with $q\_i$. Then, I would hook up each $q\_i$ to a terminal node *t*. Each of the edges would have weight 1.

I was thinking about running Edmonds–Karp on it. Now, the solution would yield the maximum bipartite matching of the group (see e.g. here). For each active arc from $p\_i$ to $q\_i$ in the final diagram, I would separate those two students.

However, I have a bad taste in my mouth after running this algorithm; the bad taste stems from modeling the instance with respect to my intention: If I maximize the complement (the desire not to work with someone), do I really minimize the desire of students to work with each other across the two groups?

If my hunch is correct (in that I'm wrong), please point me in the right direction.

# Answer
> 0 votes
It sounds like you have properly reduced the maximum bipartite matching problem to the maximum flow problem, all you need is the reasoning to convince yourself why it is true. You are worried about the complement, so let's consider that. Remember that there is a duality among the minimum cut problem and the maximum flow problem so in finding the minimum cut you will equivalently find the maximum flow. For the definition of minimum cut:

> a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge whose cut set has the smallest number of edges (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.

The minimum cut for the graph you have constructed will have the smallest number of edges since all the weights are uniform and therefore the smallest number of people from the two sets who want to work togethers given that:

$w(p\_i, q\_j) = 1 \Leftrightarrow$ person $p\_i$ does not want to work with person $q\_j$

---
Tags: algorithms, optimization, polynomial-time, bipartite-matching
---


# Question
Title: Computing the intersection of two NPDA where it is possible
Apropois to Raphael's suggestion on Intersection of two NPDAs:

Let $A\_1$ and $A\_2$ NPDA for context-free languages $L\_1$ and $L\_2$, respectively. Assuming that we know that $L = L\_1 \cap L\_2$ is context-free, can we (effectively) construct NPDA $A$ for $L$?

Any type of algorithm would be acceptable, but the more practical the better.

# Answer
I *think* this is possible for the subclass of CFLs that are permutation-invariant with a binary alphabet.

These correspond to type $\langle 1,1\rangle$ quantifier languages comparing the cardinalities of two sets. \[1\] characterizes such languages accepted by DPDA by the equivalent semilinear sets, and states at the end that quantifier languages accepted by NPDA are finite boolean combinations of such languages accepted by DPDA.

A theorem of van Benthem (\[2\]) says that pushdown automata accept type $\langle 1,1\rangle$ quantifiers definable in Presburger arithmetic (i.e. defined by semilinear sets). So, if you get two languages that are non-deterministic CFLs (using the first paper to know you have such examples), their intersection should also be a CFL by this theorem.

The semilinear set which is their intersection might be a bit difficult to compute... but, if you have that, \[3\] (pgs.11-12) give an algorithm for creating an NPDA accepting the language based on the generators of the corresponding semilinear set.

\[1\] Makoto Kanazawa. Monadic quantiers recognized by deterministic push- down automata. In Proceedings of the 19th Amsterdam Colloquium, pages 139-146, 2013.

\[2\] Johann van Benthem. Essays in Logical Semantics. Studies in Linguistics and Philosophy Volume 29, 1986, pp 151-176.

\[3\] Marcin Mostowski. Computational semantics for monadic quantiers. Journal of Applied Non-Classical Logics, 8(1-2):107-121, 1998.
> 6 votes

---
Tags: computability, automata, pushdown-automata
---


# Question
Title: Can we move quantifiers to the left in predicate logic?
Say I have part of a query in the form: ∃xa(...)∧∃xb(...)∧∃xc(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ∃xa,xb,xc(...∧...∧...) - i.e. compacting all the existential quantifiers into one and 'anding' their domains together?

For example, if I have the query:

would it be correct (albeit unwieldy) to write it as:

{ xpid | ∃xpname,xcolor,xsid,xsname,xaddress,xcost,ysid,ysname,yaddress,ycost( PARTS(xpid,xpname,xcolor) ∧ SUPPLIERS(xsid,xsname,xaddress... (and then the rest of the query)

# Answer
> 3 votes
If all the quantified variables are distinct, then you can safely move all quantifiers to the left. This is the only obstruction to this procedure. You can always ensure that all quantified variables are distinct by renaming them. For example, starting with $$(\forall x P(x)) \lor (\forall x Q(x)),$$ we first rename the second variable to $y$, $$(\forall x P(x)) \lor (\forall y Q(y)),$$ and then move the quantifiers to the left, $$ \forall x \forall y (P(x) \lor Q(y)). $$ This is equivalent to the original formula.

# Answer
> 6 votes
You are looking for prenex normal form in which all quantifiers "come first".

It exists for every first-order formula but you have to take care when transforming; multiple quantifiers may use the same variable (name) in the original formula, but they may not in the normal form.

---
Tags: logic, first-order-logic, normal-forms
---


# Question
Title: Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language
I have always had a hard time making sense of infinities.

Example: the language $L = \\{ \epsilon , 01, 0011, 000111, 00001111, ... \\}$ is not DFA acceptable because a machine capable of accepting it would require an infinite amount of states.

I can draw a DFA with ellipses in the middle to represent it's expansion. I can prove that:

For all strings x in L, using a machine M = mentioned DFA, under some finite expansion, I can accept all strings y in L, such that $|y| \leq |x|$ and such that M has $|x| + 2$ states and such that all strings in compliment(L) are not accepted by M.

All of those machines are finite.

The problem that prevents me from making the leap to claim that L is then DFA acceptable, is that I need to prove that there exists a largest string in L, but there is no largest string in L.

Anyways, I know this sounds stupid because knowing what is proven about convergence and divergence, I should be able to make mathematical sense of this. The problem is that no matter how much I know about infinity, I still do not think that what is said about convergence and divergence seems logical. I always have this feeling that something is wrong.

So I guess I just wonder how I can look at it so that it makes more sense.

In short, when a DFA needs a state for each character of a string in order to accept the string, and the language is an infinite set of strings whose enumeration could be represented as a sequence of strings increasing in length, how is it that a DFA needs an infinite amount of states to accept all of those strings, given each string is finite?

# Answer
> 3 votes
Look at your general procedure: given a language $L$ and integer $n$ build a DFA that properly recognizes any string $x \in L$ with $|x| \leq n$. Note that the language you selected is not special, *any* language can be represented by a sequences of DFAs with one for each $n$. To see this, just build a tree DFA with $|\Sigma|^{n + 1}$ states with a state for every possible string of length $\leq n$ marking the ones in $L$ as accept states and the ones not in $L$ as reject states and then minimizing. (If you want an even simpler example, then note than for any $L = \cup\_{x \in L} \\{x\\}$ and every $\\{x\\}$ is recognized by a DFA with $|x| + 1$ states)

The whole point of DFAs is that it is a finite object that recognizes an infinite object. In fact, this is the whole point of computer science in general: Turing Machines are a different kind of finite object that recognizes (or encode) a different (larger) set of infinite objects. This means that for a language to be recognized, you need a single machine that works for all strings in that language.

What you have shown is that $L\_n = L \cap \Sigma^{ \leq n}$ is recognized by a DFA, but these are just finite languages and every finite language is recognized by some DFA. However, regular languages are not closed under *infinite* union (in fact, very few things of interest to computer scientists are closed under arbitrary infinite unions), so the simple fact that $L = \cup\_{n = 1}^{\infty} L\_n$ does not imply anything about $L$.

# Answer
> 1 votes
You are confusing *potential infinity* and *actual infinity*. An "arbitrary" natural number (that is, a *variable* storing a natural number) is *unbounded*, since while being finite, it could be arbitrarily large. The *set* of natural numbers itself is *infinite*.

As another example, consider the set of prime numbers. Each prime number is finite and you can just write it down, but can you give me a list of all prime numbers? The description $\\{2,3,5,7,11,13,17,19,23,\ldots\\}$ isn't good enough for me, since I don't know what the dots *signify*. In need a *rule* that tells me when a number is prime or not.

Regular languages are the same: they specify a rule of a special kind that tells you what binary strings are in the language. If you don't like binary strings, you can always think of them as numbers: given any positive integer, take its binary notation and remove the leading 1. Using this encoding, the set of prime numbers is $$ \\{ 0, 1, 01, 11, 011, 101, 111, 0111, \ldots \\} $$ Can you see the pattern? The pattern is apparent from the *meaning* of the strings, once I point out that all the numbers encoded by these strings are prime. But this description is complicated – a child might not be able to follow it. But a child could understand "a string with two $0$s". You can think of a DFA as instructions for a child. The instructions have to be very simple, so simple indeed that they aren't fancy enough even to describe the set $\\{ 0^n 1^n : n \geq 0 \\}$.

---
Tags: automata, finite-automata
---


title: How to enumerate a product set?

text:
# Question
Title: How to enumerate a product set?
I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X\_1 \ldots, X\_d$ of elements. I would then like for it to output a list of the elements in the product set $X\_1 \times \cdots \times X\_d$.

I can't use nested for-loops because $d$ can vary so I wouldn't know how many to nest. I'm sure there's a totally standard solution to this problem, but I don't know enough to search for it successfully either here on online.

For what it's worth, here's one dumb solution I came up with. Let $b$ be the maximum cardinality of the sets $X\_i$. Then run a single loop for $n$ running from $0$ to $b^d$; for each $n$, write it in base $b$ and use the $i^{\rm th}$ digit to read off the element of $X\_i$ corresponding to that digit (and ignore if any of those digits are too big for the cardinality of the corresponding set). This will work, but feels like a pretty stupid solution.

What's the standard way of doing this?

# Answer
> 3 votes
There is a legitimate mathematical question here: find an encoding or $X\_1\times X\_2\times\cdots\times X\_d$. The idea is to use *mixed base*. As you note, if all sets have cardinality $b$, then you can use base $d$ encoding. If the sets have different cardinalities, then you use a mixed base approach. Suppose $|X\_i| = b\_i$. The choice of elements $c\_i \in X\_i$ (say $0 \leq c\_i \< b\_i$) can be encoded as follows: $$ c\_1 + b\_1 c\_2 + b\_1 b\_2 c\_3 + \cdots + b\_1 b\_2 \cdots b\_{d-1} c\_d. $$ Every number in the range $0$ to $b\_1 b\_2 \cdots b\_d - 1$ encodes a unique choice of element from $X\_1\times X\_2\times\cdots\times X\_d$.

---

There is also a programming question here: how to generate the list. The idea is to use a generalization of a *binary counter*, familiar for students of amortized complexity. There is an array $c$ of length $d$, where $c\_i$ is going to encode a choice of element in $X\_i$. At each step, we update this "counter" by increasing it by 1. We start by increasing $c\_1$ by 1. If $c\_1 \< b\_1$, everything is fine. Otherwise, there is carry: we set $c\_1 = 0$, and increase $c\_2$ by 1. And so on. The resulting sequence is a lexicographically ordered list of elements in $X\_1\times X\_2\times\cdots\times X\_d$. The amortized complexity per step (assuming $b\_i \> 1$ for all $i$) is $O(1)$.

Notice the similarity between the encoding in the first half and the algorithm in the second half.

# Answer
> 2 votes
You stated that you can do nested loops like

```
for x1 in X1 {
  ...
    for xd in Xd {
      output [x1, ..., xd]
    }
}

```

if dimension $d$ is known. This exact thing does not work with arbitrary $d$, of course, but you can do essentially the same thing using recursion; you just nest by calling recursively. This works because all for loops have the same form.

```
cartesian(X) = cartesianHelper(X,0)

cartesianHelper(X,i) {
  if ( X.size <= i ) {
    return []
  }
  else {
    result = []

    rest = cartesianHelper(X, i+1)
    foreach ( x in X[i] ) {
      foreach ( list in rest ) {
        result.add(x ++ list)
      }
    }

    return result
  }
}

```

I assume that the sets $X\_i$ are given in an array or a similar data structure.

Note that such things are much neater to express in function languages.

# Answer
> 1 votes
**Recursion/Iteration**

The Cartesian product of $d$ sets can be defined inductively by first taking the product of the last $d-1$ sets: $X\_2,\dots,X\_d$ and then taking the product of the result and the first set $X\_1$. So all you need is a procedure to multiply tow sets.

**A different method**

This method works only if the cardinalities are pairwise relatively prime (as Yuval pointed out). Let $n = card(X\_1)\times\dots\times card(X\_d)$. Allocate a $n\times d$ array to host the elements of the tuples and do the following for every row $i$: copy the elements of $X\_i$ and put them on row $i$ of the array. Keep doing this until the row is full. You'll end up generating all tuples in the product set.

*Example* Say we want to compute $\\{1,2\\}\times \\{1,2,3\\}\times\\{1\\}$. We allocate a $6\times 3$ array.

```
. . .
. . .
. . .
. . .
. . .
. . .

```

copy the elements of $\\{1,2\\}$ on the first row until it's full.

```
1 . .
2 . .
1 . .
2 . .
1 . .
2 . .

```

Do the same to the other rows. The result is:

```
1 1 1
2 2 1
1 3 1
2 1 1
1 2 1
2 3 1

```

This takes $\cal O(nd)$.

---
Tags: algorithms, combinatorics, sets
---


# Question
Title: Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$
I met a recurrence equation for my algorithm $$ f(n) = 2\cdot \left( f(n-1) + f(\frac{n}{2}) \right)$$ with $f(1)=1$, $f(2)=4$, $f(3)=10$.

I guess it is $\Theta((2+\epsilon)^n)$, where $\epsilon$ ban be arbitrarily close to 0. I want to have an asymptotic formula of $f(n)$. I do not know how to prove or disprove my guess.

# Answer
> 4 votes
For concreteness, let's assume that your recurrence is really $$ f(n) = 2f(n-1) + f(\lfloor n/2 \rfloor) + f(\lceil n/2 \rceil). $$ Define $g(n) = f(n)/2^n$. Then $$ g(n) = g(n-1) + 2^{\lfloor n/2 \rfloor + 1 - n} g(\lfloor n/2 \rfloor) + 2^{\lceil n/2 \rceil + 1 - n} g(\lceil n/2 \rceil). $$ In particular, $$ g(n) \leq (1 + 2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}) g(n-1). $$ Taking logarithms, $$ \log g(n) \leq \log g(n-1) + O(2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}). $$ We conclude that $$ \log g(n) \leq O(1) + O(1) \sum\_{m=c}^n \[2^{\lfloor m/2 \rfloor + 1 - m} + 2^{\lceil m/2 \rceil + 1 - m}\] = O(1), $$ where $c$ is some arbitrary starting point. Therefore $\log g(n)$, and so $g(n)$, is bounded. Since clearly $g(n)$ is monotone increasing, we deduce that $g(n)$ tends to some constant $C$. We conclude that $$ f(n) \sim C 2^n. $$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Proving that a word is *not* generated by a context-free grammar
I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF...

How did they get the answer so that ab is in the language and aaaa is not in the language here ?

```
S -> aSb |ab

ab     Yes
aaaa   No
aabb   Yes

```

edit: is `aaaa No` because it has b in `aSb` and `ab` is yes because obviously `ab` is there in `aSb |ab`

also `aabb` is in the language because of `aSb` cause you would add same amount of `a's` and `b's` to both sides

# Answer
> 8 votes
Let's assume you want to show that some word $w$ of length $n$ is not in the language generated by some grammar context-free $G$.

You can solve the problem algorithmically. There are two approaches:

1. Enumerate all strings in $L(G)$ of length at most $n$. In order to do that,

* transform the grammar in Chomsky normal form and
    * enumerate all derivations with at most $n$ rule applications.

This works since every rule application adds one terminal symbol in CNF (there are no $\varepsilon$-rules). If your original grammar has this property (as does the one in your question), you can skip the transformation in CNF.

This is tractable for small $n$ and/or grammars with few words per length. As soon as $L(G)$ grows fast with $n$, it breaks down.
2. Parse $w$, for instance with the CYK algorithm. This runs in time $\Theta(n^3)$ and feasible for most grammars and inputs of reasonable size.

Clearly, the latter is the better option in an algorithmic mindset, but the former might be prudent if you have to make a quick decision given a short word in an exam-like situation.

# Answer
> 5 votes
The easiest way to show that $aaaa$ is *not* in the grammar is to prove that in every word generated by the grammar, the number of $a$s is equal to the number of $b$s. You can prove it by induction on the number of derivation rules used, using the fact that in each derivation rule the number of $a$s is equal to the number of $b$s.

If you are more ambitious, you can prove in the same way that in every word generated by the grammar, all the $a$s precede all the $b$s. Both these results put together show that the language generated by the grammar is *contained* in $\\{a^n b^n : n \geq 0\\}$. Again using induction, you can show that the empty word is not generated by the grammar. So the language is contained in $\\{a^n b^n : n \geq 1\\}$. On the other hand, induction on $n$ shows that all of these words can be generated by the grammar. We have shown that the language generated by the grammar is $\\{a^nb^n : n \geq 1\\}$.

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


# Question
Title: How do people measure performance overhead?
How do people measure performance overhead? Whenever someone is bragging about how their program or application performs better than another, they talk about particular measurements, eg time, performance etc.

Whilst I understand how time to perform a task can be calculated, I cannot understand how performance is measured, and I can't find out thought Google.

Are there multiple ways? Are they all accepted or do people have issues with certain methods?

# Answer
The meaning of overhead is usually an additional expense occurring in addition to normal cost (whatever normal cost may be).

In the case of program, you may talk of overhead if it is run under conditions such that it will cost more than it normally should, in time or in memory usually, but it could be some other measure.

For example, at a time when compilers did not produce very good code, compiled programs code size or execution time was compared with programs handwritten in machine code. The quality of the compiler was measured by the overhead of the generated code compared to a similar program written in machine code. The overhead could be defined by the ratio of the two costs, or by the percentage to be added.

An overhead of 20% in code size meant that the compiled programhad a machine code version 20% larger than the hanwritten one. An overhead of 20% in speed meant that the compiled program took 20% more time to execute. An overhead of 20% in memory meant that the compiled program required 20% more memory to execute.

Nowadays, compilers are quite good and this kind of overhead would probably be negative. Compilers make the better code.

In the case of a virtual machine, you can have a program that run directly on the hardware, or runs under the control of a virtual machine that hides (and protect) somewhat the hardware. Running on a virtual machine will slow the program, and the variation in running time is the overhead (extra time cost) caused by the virtual machine. You just measure the time taken by the same program running in both situations, and you determine the percentage of additional time required when running in a virtual machine. It may depend on the type of application you use to test the overhead of the virtual machine.

Overhead is a measure of extra cost. It applies to devices or programs or procedure that cause an extra cost (but usually provide an extra servive).

You could also measure the time overhead incurred by your programs when you reduce the available real memory.

Overhead is a way of comparing two related performances, intended to achive the same result, separately measured.

Does this clarify things for you?
> 3 votes

---
Tags: algorithms, terminology, performance
---


# Question
Title: Show L is not context free using the CFL pumping lemma
I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$

So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 \> m$. We can decompose $z = a^mb^{m+1}c^{2m}$ to $z = uvwxy$ for $|vwx| \le m$ and $|vx| \ge 1$.

I am confused about what cases to consider to show this is not context free?

# Answer
> 2 votes
The idea is to look where the portion $vwx$ of $z$ can be in the string. Since the length of $vwx$ is restricted it makes it so there are not too many cases to consider. First is to consider when $vwx$ will be entirely in one letter. So it may be entirely in $a$, $b$ or $c$. So when you pump up or down you will only be affecting that portion. Then it is possible for it to span over two letters but not all three. If $v$ or $x$ is itself across two letters then pumping up will create an equal amount of letters but will be out of order. Another case is if $v$ is only $a$ and $x$ is only $b$ or similarly for $b$ and $c$. Try coming up with the contradictions for all these cases.

---
Tags: context-free, formal-grammars, pumping-lemma
---


# Question
Title: Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?
Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation closure is most often presented by demonstrating the NFA. I'm just curious whether this is out there somewhere

# Answer
A full specification of the construction of a finite automaton for regular substitution is given by Algorithm 4.2.7 of \[1\] (with a several-page proof of correctness). Tedious indeed!

\[1\] Meduna, Alexander. Automata and languages: theory and applications Springer, 2000.
> 0 votes

# Answer
There is a simple proof using automata. Suppose the original language is $L$, and we are substituting $R\_a$ for $a$ (for each $a \in \Sigma$). Starting with an automaton for $L$, replace each edge $(x,y)$ annotated $a$ with a copy of an automaton $A\_a$ for $R\_a$, connecting $x$ to the starting state of $A\_a$ with an $\epsilon$-edge, and connecting each accepting state of $A\_a$ (which is not accepting any more in the new automaton) to $y$ with an $\epsilon$-edge.
> 6 votes

# Answer
I would think that, given that there are contructive methods to pass from one definition to another, about all methods used to prove these things may be considered constructive.

Regarding NFA, if $R\_a$ is the DFA for the regular set substituted to $a$, then you remove any $a$-transition from state $p$ to state $q$ of you original automaton, and replace it by an $\epsilon$-transition from $p$ to the initial state of $R\_a$ and $\epsilon$-transitions from the final states of $R\_a$ to $q$. You must simply be careful to use a different copy of $R\_a$ for each $a$-transition, which entails renaming all the states of $R\_a$.

**Remarks** (following a comment by sjmc)

Theorists need nearly none of these proofs specific to regular sets. They use general proofs regarding full trios and full AFls (abstract families of languages). Since the family of regular sets is a full trio (which does have to be proved with some constructions), actually even a full AFL, it inherits a whole canned collection of closure properties that have been proved for all members of these families.

Explicit constructions are usually very simple for regular sets, so that anyone with a tiny bit of experience in building automata can imagine them. But they can also be tedious when you go into details. Hence they are "left as an exercise" for whoever needs them.

The proof based on regular expressions is probably the most interesting because of its architecture based on an interpretation of a formal term algebra, built on some operators corresponding to closure properties of regular sets: union, concatenation, Kleene star, and on a set of constants corresponding to the alphabet. Regular set are then a specific interpretation (morphism) of this algebra,associating each term (i.e., regular expression) with a set of strings on the alphabet, and each operator with the corresponding operations on sets of strings. The interest of this approach is that substitution of a variable by a term is a standard operation in term algebras that stays within the algebra, and can thus be interpreted in the same domain. Hence the closure.
> 4 votes

---
Tags: formal-languages, reference-request, finite-automata, closure-properties
---


# Question
Title: How do I mathematically express a set generated using two loop variables within a single for loop?
I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration.

For example, assuming `n` is previously defined and holds some positive integer, how I would I represent the set printed by this for-loop in mathematical notation?

```
// prints a set of multiples (n previously defined)
for (int j=n, k=n; k>=0; j++, k--) {
  cout << (n-j)*(n-k) << endl;
}

```

Forgive my crudeness, but I'm thinking *something* along the lines of:

$\left \\{ \left ( n-j \right ) \cdot \left ( n-k \right )\forall j \left \\{ n, n+1, ..., 2n \right \\} \forall k \left \\{ n, n-1, ..., 0 \right \\}\right \\}$

I'm lost. Should I even be using $\forall$ in this context? Any guidance is greatly appreciated!

# Answer
You attempt is basically correct, assuming that the `for`-loop is short for nested loops. You'd usually write it like

$\qquad\displaystyle\\{ (n-j)(n-k) \mid j \in \\{n, \dots, 2n\\}, k \in \\{n, \dots, 0\\}\\}$.

Now we note that we can write

* $k$ instead of $n-k$ (in the code, reverse the direction of the `for`-loop) and
* $-j$ with $j \in \\{0, \dots, n\\}$ instead of $n-j$ with $j \in \\{n, \dots, 2n\\}$ (do you see why?).

So we get

$\qquad \displaystyle \\{ -jk \mid j, k \in \\{0, \dots, n\\}\\}$.

---

If, on the other hand, the `for`-loop is supposed to step `j` and `k` simultaneously, building all combinations is not what happens. Then, you'd have

$\qquad\displaystyle \\{ (n-j)(n-k) \mid (j,k) \in \\{ (n,n), \dots, (2n,0) \\} \\} $

which we can rewrite by noting that

* $j \in \\{n, \dots, 2n\\} \iff (n-j) \in \\{0, -n\\}$ and
* $k \in \\{n, \dots, 0\\} \iff (n-k) \in \\{0, n\\}$ and

to

$\qquad\displaystyle \\{ -jk \mid (j,k) \in \\{(0,0), \dots, (n,-n)\\} \\}$.

But now $j$ and $k$ only differ by the sign, so we can rewrite using only one variable:

$\qquad\displaystyle \\{ -x^2 \mid x \in \\{0, \dots, n\\}\\}$.
> 3 votes

# Answer
If you go and execute the program you wrote you will get the sequence $0, -1, -4, -9, -16, \dots$. The program prints the first $n+1$ squares negated. In set theory, one would write $$\\{-x^2:0\le x \le n\\}$$.
> 1 votes

# Answer
In your pseudocode it seems to me like you are enumerating the set $$\\{0\cdot 0,-1\cdot1,\ldots,-n\cdot n\\}=\\{-i^2\mid 0\leq i\leq n\\}$$ In your mathematical set notation you seem to be making the set $$\bigcup\limits\_{i=0}^n\\{i\cdot -j\mid 0\leq j\leq n\\}$$ If you only have one for loop then you may only have one dependent variable (the first case) and you therefore only need a single $\forall$ quantifier in your description of the set.
> 0 votes

---
Tags: terminology, discrete-mathematics, sets
---


title: Find a CFG for a language

text:
# Question
Title: Find a CFG for a language
In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y \> x$, $z \> w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p b^p)(b^q a^q)(a^r b^r)$.

I've had a go at it, and have come up with

* S -\> A
* A -\> aAbB | ab
* B -\> bBaC | ba
* C -\> aCb | ab

This language will give me equal $a$'s and $b$'s. The reason I've chained the productions together is that since $x,y,z,w$ can't be 0, when one production is done, the others must be done as well (that was my thinking). However, I can't help but be worried about order. Even the smallest production won't come out as in the order "abab". Is it possible to construct a CFG that imposes order and memory? Or do I have to go to a PDA then CFG? Or is it irrelevant?

# Answer
The hint is another way of describing the same language. For the two languages to be the same, one must have: $x=p$, $y=p+q$, $z=q+r$, and $w=r$. Notice that these do satisfy the constraints $y\gt x, z\gt w$ and $x+z=y+w$ provided that $q,r\gt 0$. Now the structure of the hint language makes it easy to write a grammar.

$S \to ABA$

$A \to aAb|ab$

$B \to bBa|ba$
> 1 votes

# Answer
I don't understand what you mean by "chained the productions together" or "imposes order and memory" in your final paragraph.

However, the grammar you give does not work: If you apply the first rule for $A$ multiple times, you will end up with $aa\ldots aaAbBbB\ldots bBbB$ and each $B$ will yield at least one $a$, thus resulting in a word with too many switches from $a$ to $b$ and back.

What you can do is start with $S \rightarrow ABC$ and then have rules that generate the 3 subwords given in the hint from $A$, $B$, and $C$.
> 1 votes

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


# Question
Title: How is Dynamic programming different from Brute force
I was reading up on Dynamic Programming when I came across the following quote

> A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. Therefore, we can roughly think of dynamic programming as an **intelligent, brute-force method that enables us to go through all possible solutions to pick the best one**. If the scope of the problem is such that going through all possible solutions is possible and fast enough, dynamic programming guarantees finding the optimal solution

The following example was given

> For example, let's say that you have to get from point A to point B as fast as possible, in a given city, during rush hour. A dynamic programming algorithm will look into the entire traffic report, looking into all possible combinations of roads you might take, and will only then tell you which way is the fastest. Of course, you might have to wait for a while until the algorithm finishes, and only then can you start driving. The path you will take will be the fastest one (assuming that nothing changed in the external environment)

Brute Force is trying every possible solution before deciding on the best solution .

How is Dynamic Programming different from Brute Force if it also **goes through all possible solutions before picking the best one** , the only difference i see is that Dynamic Programming takes into account the additional factors ( traffic conditions in this case).

Am i correct to say that Dynamic Programming is a subset of Brute Force method ??

# Answer
> A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution.

This statement is just plain wrong.

Dynamic programming recurrences *do* (often) consider all possible ways to split the given problem instance into smaller instances according to some scheme. However, it will not combine *all* solutions to all partial problems with each other and pick the best -- it combines only *optimal* partial solutions (and picks the best out of those).

The fact that this yield an optimal solution for the original problem is not trivial and does, in fact, only hold for *some* problems. Namely those that fulfill the Bellman principle of optimality (one of the most fishy, misunderstood "definitions" that are regularly quoted). See here for some more thoughts on that.

As a concrete example, consider the Bellman-Ford algorithm on a complete graph $K\_n$ with unit weights: it only ever considers paths of length one and two (i.e. $\Theta(n^2)$ many) because *those using one edge are all optimal*. But there are infinitely many solutions if you don't bound the maximum number of edges allowed, and still $\gg (n-1)!$ many if you allow every node to be used only once. So clearly, Bellman-Ford -- a dynamic programming algorithm -- does *not* perform a brute-force search.
> 17 votes

# Answer
Dynamic Programming is clever as it **reuses** computation, while brute force doesn't. Suppose to solve, f(6), you need to solve 2 sub-problems which both call f(3). The brute force method will calculate f(3) twice thereby wasting effort while dynamic programming will call it once, save the result in case future computations need to use it. In many problems, dynamic improves the exponential complexity of brute force to polynomial complexity.
> 9 votes

# Answer
The distinction the Wikipedia article might be trying to make is between three types of algorithms:

1. Algorithms which go over all possible solutions, choosing the optimal one.
2. Algorithms which go over a subset of all possible solutions, chosen so that the optimal solution belongs to the subset.
3. Algorithms which go over a subset of all possible solution, without the guarantee that the optimal solution belongs to the subset.

The first two types of algorithms produce the optimal solution, while the third type aims to produce a "good" solution rather than an optimal solution. In my opinion, the distinction between the first two kinds is not so clear cut.

Let me start by giving simple examples for all three types of algorithms, in the context of shortest path (the example you give).

1. Try all possible paths. This is known as *brute force*.
2. Try all possible paths, keeping track of the minimum solution so far. Whenever the current path you are constructing is more expensive than the minimum solution so far, abandon it and choose another one (we imagine that the distance is computed on a segment-by-segment basis). This is called *pruning*.
3. Look at the map, consider a few paths, and choose the best one among them. This is an algorithm for a human rather than a computer.

These examples are rather crude, and perhaps don't paint a very accurate picture. Pruning is crucial in many situations, for example in computer chess. If you're curious, look up the A<sup>*</sup> algorithm, which is actually used for shortest path.

Dynamic programming is a technique for speeding up significantly the brute force algorithm. It is somewhat misleading, however, to think of it this way. It is an algorithmic technique for solving optimization problems. You can implement pruning in the context of dynamic programming.

In the case of shortest path, here is one version of dynamic programming. We compute inductively the shortest path from the starting point to any other point of significance in the map *using $t$ segments*. Given the data for a certain $t$, we can compute the data for $t+1$ by enumerating over the last "hop" in any path from the starting point to any other point. When $t$ is large enough, we will have found the shortest path from the starting point to any other point. This is much more efficient than brute force, though not as efficient as some other dynamic programming algorithms.
> 3 votes

# Answer
Dynamic programming is much faster than brute force. Brute force may take exponential time, while dynamic programming is typically much faster.

The analogy to brute force is a very loose one. Dynamic programming is not a magic silver bullet that lets you take any brute force algorithm you want and make it efficient.
> 0 votes

# Answer
This is straightforward. Dynamic programming is a "search strategy" which uses additional factors to narrow down a search. If there is no solution in the search space, dynamic programming *will* (typically) do a search through every element of the search space. But that does not mean that it is a brute force search.
> -2 votes

# Answer
The statement that dynamic programming is intelligent brute force is correct, but a bit difficult to understand with that phrasing. The point of dynamic programming is generally to take a problem and break it into smaller pieces in an intelligent way. After you've done that, you will be using brute force to solve each small piece, and then you will be using brute force again to combine the pieces into a final solution. So while you could definitely say that dynamic programming is a type of brute force solution, the trick lies in how you use that brute force.
> -2 votes

---
Tags: algorithms, terminology, optimization, dynamic-programming
---


# Question
Title: NP Problem definition – verifiable on DFA vs. solvable on NFA
So in complexity theory, I've run across different definitions for NP problems --

* Decision problems where a solution can be *verified* by a **DFA** in polynomial time
* Decision problems where a solution can be *found* by an **NFA** in polynomial time

Is there one of the above that is generally more accepted as the "go-to" definition in the academic community? If so, is there a reason? (If these "definitions" are incorrect – please feel free to correct me).

To me, the second definition makes more sense intuitively.

# Answer
First, let me correct you: instead of a DFA there should be a *deterministic Turing machine running in polynomial time*, and instead of an NFA there should be a *non-deterministic Turing machine running in polynomial time*.

As you mention, both definitions are equivalent, and for this reason there is no single "go to" definition – you can use whatever definition is more appropriate in any single case.

Any formal development of complexity theory would necessitate picking one of these and then showing that the other is equivalent, but this is best left to the developers of these formal frameworks.

There are in fact many variants of Turing machines, so there are more than two definitions of NP. Even more equivalent definitions are provided by other models of computation such as RAM machines. Since all these definitions result in the same complexity class, they are all equally well definitions of NP.
> 3 votes

---
Tags: complexity-theory, np
---


# Question
Title: Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial
I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of polynomials over $\text{GF}(2)$, and (2) reducing the result modulo an irreducible polynomial. We use the "standard" bitstring representation of polynomials, i.e. $x^3+x+1 = \[1011\]$.

The paper gives an algorithm for calculation of the remainder polynomial on page 16 in Algorithm 3. However, I'm having trouble understanding the reduction algorithm on pages 16-17 (Algorithm 4). Essentially, I think we need Algorithm 4 for larger fields when our or partial results don't fit 128 bits anymore. They give an example for multiplication of two polynomials in $\text{GF}(2^{128})$.

> Where do the "magic constants" 63, 62, and 57 for right shifts, and the "magic constants" 1, 2, and 7 for left shifts come from?

For example, how does one generalize the algorithm for smaller fields, say $\text{GF}(2^{32})$? Would the corresponding shift values then be 15, 14, 9 and 1, 2, 7?

> In the final step 4, the algorithm tells you to "XOR $\[E\_1:E\_0\]$, $\[F\_1:F\_0\]$, and $\[G\_1:G\_0\]$ with each other and $\[X\_3:D\]$".

Why do we do this? As far as I can see, the result of this XOR operation is neither stored anywhere nor used anywhere. Is it somehow used for computing $\[H\_1 : H\_0\]$?

# Answer
The Galois field $GF(2^{128})$ has many different "concrete" representations. One popular representation is using polynomials in $GF(2)\[x\]$ (i.e. with coefficients in $GF(2)$) modulo some irreducible polynomial of degree $128$, say $x^{128}+x^7+x^2+x^1+x^0$. The magic constants $7,2,1,0$ come from this particular irreducible polynomial. You don't see $0$ since there is no need to shift by $0$. Similarly, the magic constants $57,62,63,64$ are the complements of the constants above with respect to $64$. Again, you don't need to shift by $64$ since the registers are $64$ bits wide. If we had used some other irreducible polynomial, the constants would have been different.

Regarding step 4, $\[H\_1:H\_0\]$ results from XORing $\[E\_1:E\_0\],\[F\_1:F\_0\],\[G\_1:G\_0\],\[X\_3:D\]$. This implements the operation of MODing by $x^{128} + x^7 + x^2 + x^1 + x^0$. The idea is that modulo this polynomial, $x^{128} = x^7+x^2+x^1+^0$; addition here is XOR. The different summands corresponds to these different monomials – see if you can find the correspondence.
> 7 votes

# Answer
For completeness, I'll flesh out Yuval's answer a bit more through an example of multiplication of two polynomials $A$ and $B$ in $\text{GF}(2^{16})$. Let $$A = \[0001|1100|1110\] = x^8 + x^7 + x^6 + x^3 + x^2 + x,$$ and $$B = \[0100|0101|0111\] = x^{10} + x^6 + x^4 + x^2 + x + 1.$$ The multiplication of $A$ and $B$ over $\text{GF}(2)$ is then $$C = \[0000|0000|0000|0111 | 0101|0010|0000|1010\].$$

We then compute for $\text{GF}(2^{16})$ the polynomial $$q^+ = x^{32}+x^{21}+x^{19}+x^{18}+x^{16}+x^{10}+x^6+x^4+1.$$ We now want to multiply $q^+$ with the high bits of $C$, and keep the 32 highest bits of this computation for later processing. For this purpose, we use Algorithm 4 (Step 1-2). Let us denote $C$ by $\[X\_3:X\_2:X\_1:X\_0\]$, where each $X\_i$ is 8 bits long. We then right shift $X\_3$ with 28, 26, 22, 16, 14, 13, and finally with 11. So we have altogether 7 "temporary variables", and we XOR them with $X\_2$. This results in $111\_2$, which is what we wanted.

For the lower part of the product of the next step, notice that we get the left shifts from $g^\*$, which is defined on page 16.
> 4 votes

---
Tags: algorithms, integers, polynomials, multiplication
---


title: Unique keys in a binary search tree

text:
# Question
Title: Unique keys in a binary search tree
I'm studying for my finals and I can across this statement.

"For a fixed set of (unique) keys, any binary search tree containing those keys can be converted to any other BST on the same set of keys via a sequence of left- and/or right- rotations."

I'm interested in a proof. Does anyone know any references?

# Answer
> 2 votes
Here's a short method of transforming a BST $T\_1$ into any other BST $T\_2$ on the same set of keys, taken from notes written by Doug Hogan at Penn State:

> Define the *right spine* of a BST as the root and all descendants of the root that are reachable by following only right pointers from the root. A *right-linear chain* is a BST that has all n nodes in the right spine.
>
> Let $T'$ be the (unique) right-linear chain of $n$ keys. Let $r = (r\_1, r\_2, ..., r\_k)$ be a sequence of right rotations that transforms $T\_1$ into $T'$, and let $r' = (r'\_1, r'\_2, ...,r'\_{k'})$ be a sequence of right rotations that transforms $T\_2$ to $T'$. We know there exist sequences $r$ and $r'$ with $k, k' \leq n-1$, since a right rotation adds exactly one node to the right spine. For each right rotation $r'\_i$ let $l'\_i$ be the corresponding left rotation. Then, the sequence $(r\_1, r\_2, ..., r\_k,l'\_{k'},l'\_{k'-1}, ..., l'\_2, l'\_1)$ transforms $T\_1$ to $T\_2$ in at most $2n-2$ rotations.

...and here's another explanation, which gives a nice recursive algorithm.

Google search terms: `binary search tree transform rotation proof`.

---
Tags: algorithms, algorithm-analysis, binary-trees
---


title: What are these special strings called?

text:
# Question
Title: What are these special strings called?
Is there any specific name for strings of data that have well defined format ? For example URLS, domain names, IP Addresses, Email addresses, File Paths etc. are all having well defined delimiters and data formats. What are these special strings in general called ?

# Answer
> 4 votes
Any set of strings is a (formal) language. That's probably not what you mean since you have quite specific restrictions in mind.

Many standardised string formates are defined by regular expressions what makes the respective sets of strings they admit regular languages. Note that some examples are actually finite languages (IPs).

In then end, it depends on what you mean by "well defined". *Any* set of strings is well-defined. Anything more will depend on the kind of specification you give, and then the language will (sort of) inherit the specification's "name".

# Answer
> 2 votes
These strings are called, if I may say, *standard notations*.

They are all defined in standard documents, some of which are sometimes updated, replaced by newer ones. When the Internet is concerned, many of these documents are produced by the Internet Engineering Task Force (IETF) under the strange name of "Request for Comments" (RFC). The syntax is usually given by context-free grammars, sometimes extended with regular expressions, in some appropriate notation (even though these formats are often regular languages).

URLS are defined in RFC 1738 (complemented by RFC 3986)

URLs are actually a very complex, and somewhat open, format, described syntactically in section 5 of RFC 1738. The definition make use of other standardized formats.

For example, Email addresses are defined by RFC 822, and this definition is used in the definition of URls such as "mailto:xxx@yyy"

Regarding file paths, you have definitions, notations, and semantics that are specific to operating systems. But there is also an internet wide notation and semantics that is part of the definition of URLs in RFC 1738.

Regarding domain names, the oldest non obsolete RFC defining them is RFC 1035. Their accepted syntax in URLs is defined in section 5 of RFC 1738.

Similarly IP addresses are currently standardized by RFC 1918 for IPv4 and RFC 2460 for IPv6, and the syntax is used for URLs.

When looking for such a definition, adding "RFC" to the keywords will usually get you faster to the right place (when Internet is concerned).

And in case you worry about electricity shortage, there is also a standard format, and the corresponding RFC, to send mail by homing pigeon. See RFC 1149.

---
Tags: terminology, strings
---


# Question
Title: Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality
The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and physics requires the tiling to satisfy one more condition:

The tiling should satisfy some proportionality, say, Tile 1 should appear with frequency 1/16, Tile 2 with frequency 9/16, Tile 3 with 6/16, Tile 4 with frequency 0...

The most important decision problem is the following: Could a given set of Tile tile a grid of size NxN satisfying the frequency constraint within a error of +-epsilon.

For example: could the set {Tile 1, Tile 2, Tile 3, Tile 4} tile the NxN grid with frequency 1/16+-0.01, 9/16+-0.01, 6/16+-0.01, 0+-0.01 respectively....

From one of my previous post:

Algorithms for NP complete problem

I realize the decision problem of tiling without such constraint could be modeled by SAT... With this constraint the problem becomes ridiculously difficult and I eagerly seek for solutions towards this finite decidable problem.... (we could forget epsilon for a moment if the problem with epsilon is too hard)...

So here is the question: how do we model this problem in MIP or SAT or any other optimization algorithm?

For more detail why this problem is practical in material science and physics, see my previous post:

coloring in lattice

reference for wang tile

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

P.S. this is a bounty question from mathoverflow without yet a applicable solution...

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

# Answer
> 1 votes
Use a SAT solver that also allows you to express pseudo-Boolean constraints.

Encoding the verification of the existence of the tiling of an NxN grid as a CNF formula is straightforward. Each grid position will have a set of variables associated with it of which only one will be set true if a particular tile occupies that position. Add clauses that force exactly one of each set of variables to be set true. Add other clauses that demand grid neighbors be the correct sort of tile out of the available choices.

The epsilon requirement means requiring that only a fixed number of the grid position variables for each tile type be set true, or that the number set be within a certain range. This is complicated by the fact that the naive expression of such constraints in CNF takes a number of clauses exponential in the number of variables involved. There are more efficient encodings that involve adder and comparison circuits, but a solver that accepts pseudo-Boolean constraints directly will either work without such encodings or will save you the trouble of creating these circuit encodings yourself.

---
Tags: complexity-theory, optimization, logic, satisfiability
---


# Question
Title: How to check if two sequences of setoid members are mutual rotations?
Real world background: There are 2 independent sources of polygon definitions, with arbitrary parameters. Meaning each source has it's own floating point precision, starting point and orientation of vertices.

The problem is to find an algorithm, that would receive those 2 polygon definitions and by a certain margin declare them equal or not. If a cutting machine would receive those 2 inputs, would it cut out the same shapes? (Which is btw. the real motivation behind the problem.)

E.g.: If

> polygonA = ( (1.0001, 1.0002), (2.0000, 1.0001), (1.5001, 1.9998) )
>
> polygonB = ( (1.9998, 0.9999), (0.9999, 1.0002), (1.5002, 2.0001) )

and there is precision margin of 0.001 (i.e. 1 mm) then `polygonA` would be equal to `polygonB`.

This problem can formally formulated as follows:

## Task and terminology

Assume we have a set $X$ and two sequences $S\_1 = (a\_1, a\_2, \ldots,a\_n)$ and $S\_2 = (b\_1, b\_2, \ldots,b\_n)$, where $a\_i \in X, b\_i \in X, \forall i \in \[1..n\]$.

We define, that two sequences are *congruent* and denote them $S\_1 \cong S\_2$ if $\exists k,l \in \[1..n\]$ such that $a\_{k+i \pmod{n}}=b\_{l+i \pmod{n}}, \forall i \in \[1..n\]$. (Plainly said, they would define the same cycle.) If $S\_1 \cong S\_2$ then we say that $S\_1$ is a *rotation* of $S\_2$ and vice-versa.

The task is to find an algorithm that determines if $S\_1 \cong S\_2$.

## Problem

In the case that $X$ is a **total order set** the task can be solved quite easily with a linear algorithm. (Finding a lexicographical extremum of all rotations for both sequences and then comparing those extrema.)

The question is, is there linear algorithm if $X$ is a **setoid**? I.e. members of $X$ can be checked only for equivalence. If not, does at least exist an algorithm with a better complexity than brute force?

# Answer
It might depend on $n$. If $n$ is prime then the following algorithm works in linear time. Compare $a\_1$ to all elements in $a$ and to all elements in $b$. The resulting $a\_1$ patterns must be congruent, and if they are, then they are congruent uniquely. Once you know the shift, it is easy to check whether the original sequences are congruent.

When $n$ is composite then you might run into trouble since there are several shifts possible. Still, it seems possible but messy to get a linear or quasilinear time algorithm.
> 1 votes

---
Tags: algorithms, discrete-mathematics
---


title: Showing that DNF VALID is coNP-hard

text:
# Question
Title: Showing that DNF VALID is coNP-hard
I'm trying to understand/show that DNF VALID is coNP-hard. I have given an algorithm for the complement of DNF VALID and shown that this is in NP (since the complement of a language in NP is in coNP), but I'm really struggling to show that DNF VALID is coNP-hard.

> The complement of DNF VALID = {ϕ | ϕ is not in DNF OR ϕ is falsifiable}

A simple algorithm for the complement of DNF VALID:

```
On a non-deterministic TM M: "on input ϕ (boolean formula):
 1. Scan through ϕ and check whether ϕ is on DNF.
      If it is, accept,
      if not, continue to step 2.
 2. Non-deterministically choose a valuation for ϕ
 3. If ϕ is falsifiable accept, if not, reject

```

To show that DNF VALID is coNP-hard I think that I need to show that a language that is NP-complete can be reduced in polynomial time to the complement of DNF VALID, but I'm not sure with which language to choose, and I could really use some help on how to go forth with the reduction.

# Answer
A formula $\varphi$ in DNF is valid if and only if $\neg\varphi$ in CNF is unsatisfiable. Since CNF-SAT is NP-complete, it follows that DNF-VAL is coNP-complete. You are right that you need to show an NP-complete language can be reduced in polynomial time to the complement of DNF-VAL. Since this complement is just CNF-SAT, try reducing SAT to CNF-SAT.

There are a lot of proofs of this reduction around; this one\[1\] looks good if you just want to see an answer.

\[1\] Howell, Rod. "SAT-CNF Is NP-complete." (2000).
> 0 votes

---
Tags: complexity-theory, reductions, co-np
---