# Question
Title: 3-COL with a restriction on a number of vertices colored with a particular color
If I modify a 3-COL problem (with colors A, B, C) in a way that I now demand that at most, say, 50 vertices may be colored with color A, does the problem still remain NP-complete?

I've been thinking of a reduction from a standard 3-COL, but there is no way that I can solve a standard 3-colorability using the problem described above; I'd have to cut the graph into smaller pieces. Other NP-complete problems I know of, like independence set, have a parameter and in my problem there is a fixed number instead of a parameter. So this got me thinking, that maybe such a problem could be solved in P-time, but this doesn't make sense as I could probably replace 50 with any other number.

So this is simpler than asking whether there is a 3-COL such that at most k vertices receive color A, but still quite hard in general I think.

Am I correct?

# Answer
> 4 votes
For a fixed parameter like 50, the problem can be solved in "polynomial time": guess which vertices to color A, then solving a 2-coloring problem for the remaining vertices. The running time will be something like $O(|V|^{52})$, since there are $O(|V|^{50})$ ways to choose a set of at most 50 vertices; and 2-coloring can be solved in $O(|V|+|E|)=O(|V|^2)$ time.

Of course, this solution is solely of theoretical interest. An algorithm whose running time is $O(|V|^{52})$ is technically polynomial-time, but it's completely and totally infeasible in practice for any interesting graph.

In contrast, if the parameter 50 is part of the input, then the problem remains NP-hard (consider what happens when you pass in $|V|$ as the value of this input; then you have the standard 3-COL problem). This highlights the difference between a value that is fixed vs is an input to the problem.

Perhaps a simpler example to illustrate that difference is vertex cover: vertex cover is NP-complete, but if I ask you whether there exists a vertex cover of size $\le 50$, that can be done in polynomial time, for similar reasons -- the running time will be $O(|V|^{50})$ or so. In particular, if you want to know whether there exists a vertex cover of size $\le k$, that can be done in $O(|V|^k)$ time. When $k$ is a fixed constant, this is polynomial time; but when $k$ is part of the input, then this is exponential time (it is $\ge 2^k$).

# Answer
> 2 votes
If at most 50 vertices can be colored A, then the problem is in $\mathsf{P}$. Indeed, there are $O(n^{50})$ possibilities for the set of vertices colored A. Go over all such choices in which these vertices are an independent set, delete them, and check whether the remaining graph is bipartite.

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


# Question
Title: How to prove a set has infinite cardinality?
Set S is a set consisting of all string of one or more a or b such as "a, b, ab, ba, abb, bba..." and how to prove set S is a infinity set.

I have tried proving set S as one to one corresponding to natural number set in binary form. like a = 0, b = 1. However, I am stuck in proving it since there are more than one "1", "01" = "1", same as other numbers.

# Answer
A general way of showing this is *proof by contradiction*.

1. Assume (towards a contradiction) that the given set $S$ is finite, i.e.

$\qquad S = \\{s\_1, \dots, s\_n\\}$.
2. Show that there is an element $s \in S$ but for which $s \neq s\_i$ for all $i \in \[1..n\]$.

One way to do this is to *construct* $s$ from $s\_1, \dots, s\_n$ explicity; that would be an instance of a *diagonal argument*.
3. Above step provides a contradiction, hence the assumption must be false: $S$ does not have this form.

**Important:** This *only* works if you make no assumptions whatsoever about the $s\_i$ and $n$ (beyond what you know about $S$ already). If you do, you have not argued against *all* finite candidates for $S$.

### Example

Show that $\mathbb{N}$ is infinite.

> Assume the opposite. Then, $\mathbb{N} = \\{n\_1, \dots, n\_N\\}$ for some $N$. Let $n = \max \mathbb{N}$. Then, by the definition of the natural numbers, $n+1 \in \mathbb{N}$ as well. But that contradicts that $n$ is the largest number in $\mathbb{N}$; the assumption must be false.
> 5 votes

# Answer
You can prove that a set is infinite simply by demonstrating two things:

* For a given *n*, it has at least one element of length *n*.
* If it has an element of maximum finite length, then you can construct a longer element (thereby disproving that an element of maximum finite length).

In essence, this demonstrates that the a subset, consisting of a, aa, aaa, . . . is infinite. This latter clearly maps to the integers.
> 4 votes

# Answer
A general method is to show that $S$ has an infinite subset.

That is, you show that there is $A \subseteq S$ for which you already know that $|A| = \infty$.

### Example

Show that $\mathbb{Z}$ (or $\mathbb{Q}$, $\mathbb{R}$, ...) is infinite.

> We already know that $\mathbb{N}$ is infinite (see my other answer). Hence, $\mathbb{Z} \supsetneq \mathbb{N}$ is also infinite.
> 3 votes

# Answer
A general way of showing that a set $S$ is infinite is giving a one-to-one map from $S$ to a proper subset of $S$. For example, the map $f(n) = 2n$, mapping the integers bijectively to the even integers, shows that there are infinitely many integers.
> 3 votes

# Answer
There is a nice bijection between finite strings over the alphabet $\\{1,2\\}$ and the non-negative integers. The mapping is $$ f(x\_{n-1} \ldots x\_0) = \sum\_{i=0}^{n-1} x\_i 2^i. $$ The first few strings according to this bijection are $$ \epsilon, 1, 2, 11, 12, 21, 22, 111, \ldots $$ The same idea works for the alphabet $\\{1,\ldots,d\\}$: $$ f\_d(x\_{n-1} \ldots x\_0) = \sum\_{i=0}^{n-1} x\_i d^i. $$
> 0 votes

---
Tags: proof-techniques, sets
---


# Question
Title: Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space
Assuming you have a balanced tree, without parent-pointers, with $n$ nodes, and a height $H = \mathcal O(\log n)$.

I know you can traverse the tree in level order in $\mathcal O(n)$ time using a queue. However, even in a balanced tree, the queue can grow to $\mathcal O(n)$ in size.

So the best I came up with is essentially to in/pre/post order traverse the tree in $H$ passes, one for each level in the tree, and simply filter the visits to the level for that pass. This gives an algorithm with $\mathcal O(n\cdot H ) = \mathcal O(n \log n)$ runtime and $\mathcal O(H) = \mathcal O(\log n)$ space.

The question is:

1. is there a algorithm for traversing a balanced tree without parent-pointers in *linear-time*, and logarithmic space?
2. Or at least, in $\mathcal o(n\log n)$ time and $\mathcal O(\log n)$ space (i.e a better result than my naive algorithm).
3. Or more generally, linear time, but sub-linear space?

Also, no cheating, you cannot alter the tree :)

# Answer
Let's start by considering the case of a full tree (depth $\lg n$, contains exactly $n$ leaves, where $n$ is a power of two). It's possible to build an algorithm for this case with space complexity $O(\lg n)$ and total running time $O(n)$.

In particular, Hendrik Jan describes an elegant algorithm whose running time is $O(n)$. Let me flesh out the details. Consider a $\lg n$-bit counter, whose value is stored in binary, and that supports one operation: Increment (adds one to the counter). How many bits needed to be flipped by each invocation of the Increment operation? The answer is $\lg n$ in the worst case (when you increment from $0111 \cdots 1$ to $1000 \cdots 0$), but a standard analysis shows that the amortized number of bit-flips is $O(1)$ -- the amortized analysis is a standard exercise in many algorithms textbooks.

Note that you can treat any bit-string $x$ of length $\le \lg n$ bits as a specification of a path from the root of the tree to some node $n(x)$ ($0$ means go left; $1$ means go right; the most significant bit is the first branch taken in the path; the least significant bit is the last branch). Suppose the $\lg n$ bits stored in the counter are denoted $b\_1,\dots,b\_{\lg k}$. Treat the bit-string stored in the counter as a specification of a path to a leaf. Also, for each index $i$, store a pointer to the node $n(b\_1 \cdots b\_i)$, i.e., the node reached by following the path that corresponds to the first $i$ bits in the counter (the $i$ most significant bits). This takes $O(\lg n)$ space.

Now we're going to repeatedly increment the counter, and update the pointers. We only need to update a pointer when its corresponding bit flips: e.g., if $b\_i$ changes, we'll need to update the pointer $n(b\_1 \cdots b\_i)$. This update can be done in $O(1)$ time, by using the pointer to $n(b\_1 \cdots b\_{i-1})$ and then looking at its left or right child (depending on whether $b\_i=0$ or $b\_i=1$ after the update). Importantly, whenever bit $i$ flips, so do all of the bits $i,i+1,i+2,\dots,\lg n$, so all of the pointers will be updated as necessary. Thus, at every point in time all $\lg n$ pointers are correct.

What's the running time? We only update a pointer when its corresponding bit changes. Each time we update a pointer, we do $O(1)$ work. Therefore, the total number of operations is equal to the total number of bits that have changed, as we increment the counter from $1$ to $n$. But now it's a standard result that the amortized running time of the Increment operation is $O(1)$ bit flips: i.e., you can increment the counter $n$ times, at the cost of a total of $O(n)$ bit flips. Therefore, the running time of this algorithm is $O(n)$, and the space complexity is $O(\lg n)$. The constants hidden by the big-O notation are relatively small: e.g., the total number of bit flips is $\le 2n$, so you'll follow about $2n$ child pointers, and you only need space for $\lg n$ pointers.

---

What if the tree is not full? In other words, maybe the tree has $n$ leaves and depth $c \lg n$. Then a bunch of subtrees are missing. However, I think it is possible to just skip over them as you increment the counter. Therefore, it looks to me like the total running time should remain $O(n)$ for this case, and the space complexity will be $O(\lg n)$. I confess I haven't checked the details of this part carefully, but it looks like it should work out.
> 2 votes

---
Tags: algorithms, data-structures, trees, graph-traversal
---


# Question
Title: Updating an AVL Tree Based On Balance Factors
I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it?

Background:

Let the balance factor of a node be defined by $\left| height(\text{right sub tree}) - height(\text{left sub tree}) \right|$.

Questions:

1. **Give the balance factor for the nodes in slides 27-30 (given below)**
2. **Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?**

Here are the relevant slides:

# Answer
I will answer the second question.

> Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?

Yes, actually that's the whole idea behind the avl tree. All balance factors are always in range \[-1, 1\], so you need only two extra bits per node to store it.

After insertion you simply climb up the tree and update balance factors:

* decrease if the left sub-tree became higher,
* increase if the right sub-tree became higher,
* retrace the tree if the balance factor becomes -2 or 2 (this can be achieved by local rotations on the tree),
* if balance factor becomes 0, then the tree became balanced and no further work is required.

For more details check wikipedia page.

If you need more mathematical analysis on how the balance factors change after local rotations, check my question/answer here.
> 3 votes

---
Tags: binary-trees, trees, search-trees
---


# Question
Title: How did it happen that Algol 60 was an improvement on its successors?
The original statement referred to by this question is:

> The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration of ALGOL 60. Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors.

(From the appendix of a very readable report on programming language design by C. A. R. Hoare. I read that report because I wanted to ask this question, not the other way round. Reading that report made it clear to me that the original statement is even more true than I thought when I decided to ask this question.)

The intention of this question is to better understand the sociological and political aspects of the events, not the detailed technical merits. The politically accepted successors of Algol 60 (at the time) like Algol 68, PL/I or Ada were badly feature bloated, while really improved successors like Algol W or Simula were never widely used. The surviving members of the Algol language family seem to prefer naming Pascal as their great-grandfather instead of Algol, even so Pascal seems to be just another descendant of Algol. (C or Smalltalk are not descendants of Algol, because their syntax and underlying principles are too different. C++ on the other hand might be considered as a legitimate descendant of Simula, embodying many of the same underlying principles, adopting the C syntax and legacy only for political reasons to avoid the fate of the Algol like languages.)

An account of the history of types in programming languages made me realize that even the type system of Algol 60 was still quite unfinished. It seems that it would have been easy to just finish the type system and fix some other minor annoying details for the next revision of the language. But instead... ??? Most of my math books use Algol for their pseudocode, and it looks much nicer than the C pseudocode in the few books that don't use Algol. So I always wondered why Algol actually died.

# Answer
I always felt like the reason is expressed by Alan Kay in his OOPSLA 1997 keynote, when he talks about Dijkstra's paper. I am not taking sides here but the tension expressed there seems to be prevalent in politics of CS, when it comes to Europe vs America. Algol represents European way of doing CS, and really most of the code was written in America. So no one really wrote any big system in Algol, thus it died.

But, I am an outsider to both cultures so, take this with a huge grain of salt. Also I know that Algol 60 designers included American computer scientists as well. All in all, this is just how I feel about it, no strong arguments here.
> 3 votes

# Answer
I remember a mathematician in the nineteen sixties said to me that the ALGOL60 Report could be read and understood in the time of consuming a couple of cups of coffee in an afternoon. But look at the ALGOL68 Report and the latest version of the ISO PL/I standard! What a big difference! To program well in practice, one should be able to competently consult these official documents in cases of need. I am quite sure that even today the majority of those having studied CS in the universities wouldn't find the said two documents an easy reading. On the other hand, at least decades ago, a large number of programmers in practice aren't CS graduates.
> 2 votes

# Answer
It is probably hard to accurately answer a question about history, especially without access to the proper sources. Not sure whether this answer is primarily opinion based, or rather just guesswork.

This article about the history of Algol contains some interesting information, that the Algol committee was unable to form a consensus, and ended with a minority report and the adoption of Algol 68 basically accepting the proposal by Adriaan van Wijngaarden.

However, the Dutch wikipedia article on Adriaan van Wijngaarden says

> Hij stond tevens aan het hoofd van de werkgroep die de programmeertaal Algol-68 ontwikkelde.

and the German wikipedia article on Adriaan van Wijngaarden says

> Durch seine Arbeit als Leiter des ALGOL-68-Komitees leistete van Wijngaarden einen profunden, wenngleich erst spät beachteten, Beitrag zum Gebiet des Entwurfs, der Definition und der Beschreibung von Programmiersprachen.

So both article claim that he was actually the head of the working group that developed the programming language Algol-68. This puts the fact that the committee was unable to form a consensus, and that it adopted the language that he proposed into a more dubious light.
> 2 votes

---
Tags: programming-languages, history, language-design
---


title: AVL Trees Height-Balance Property

text:
# Question
Title: AVL Trees Height-Balance Property
An AVL tree is one that satisfies the *height-balance property* which states that: For every position p of T, the heights of the children of p differ by at most 1.

Below is an example AVL tree. However, I've highlighted a node whose child's height would imply that their difference is not at most 1.

Can someone explain to me what I am missing?

# Answer
The nodes you are highlighting are a node and its child. The promise is that the heights of *siblings* don't differ by more than $1$. In other words, the promise is that for every node $p$, the heights of the children of $p$ differ by at most $1$ *from each other*.
> 3 votes

# Answer
From wikipedia:

The balance property of AVL trees is defined in terms of the "balance factor", which is calculated as

balance factor = height(left sub tree) - height(right sub tree)

So, you should not compare parent with its child, only the left and right children.
> 2 votes

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


# Question
Title: How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar
Say I have the following grammar:

```
E  -> TE'
E' -> +TE'| -TE' | λ
T  -> (E) |  id

```

I need to build the finite state machine with the LR(0) items,

But I know in order to do this I have to remove the λ.

How to I accomplish this ?

Also, after I have the SLR(1) table, how to I prove is valid ?

Thanks, I'm studying for an exam, and I'm stuck here :(

# Answer
1. Find all nullable variables. In this case only E' is nullable.
2. Let me illustrate the second step with an example:

Replace a production A -\> BCD with a family of productions like this (assuming B, C & D are nullable):

```
A -> BCD | BC | BD | CD | B | C | D

```
3. Delete all the productions with the empty string as the right-hand side.

With all that in mind we get:

```
E  -> TE' | T
E' -> +TE'| -TE' | +T | -T
T  -> (E) |  id

```
> 2 votes

---
Tags: finite-automata, formal-grammars, lr-k
---


# Question
Title: Loop variant for a while loop that occasionally doesn't decrease?
I'm working on practice problems for a test I have, and every example of loop variant decreased with every iteration of the loop. On this one, the values remain the same when a \< b. My attempts also got me a loop variant that has a chance of a negative since occasionally a becomes larger than b and vice versa. Any advice on attempting to find and prove the loop variant for this question?

```
def mystery(a,b):
# Precondition: a >= 0 and b >= 0
while a >= 0 and b >= 0:
    if a < b:
        a, b = b, a
    else:
        a = a - 1
return a

```

EDIT: For anyone who is interested in this question, my best solution is as follows.

$$f\_{1} = a + 2b + 1$$

# Answer
Just a hint for now, since this is a practice problem: consider a lexicographic combination of orders.

In some more detail: Suppose you have two maps $f\_1:S\to D\_1$ and $f\_2:S\to D\_2$ from your program states $S$ into well-founded ordered domains $(D\_1,\le\_1)$ and $(D\_2,\le\_2)$. The lexicographic combination of $\le\_1$ and $\le\_2$ is the order $\le$ on $D\_1\times D\_2$ given by $(x\_1,y\_1)\le(x\_2,y\_2)$ iff either $x\_1\le\_1x\_2$, or $x\_1=x\_2,y\_1\le\_2y\_2$. It is also well-founded.

So if $f\_1,f\_2$ are such that

* $f\_1$ never increases, and
* whenever $f\_1$ does not decrease, $f\_2$ does,

then the map $(f\_1,f\_2):S\to D\_1\times D\_2$ is a variant proving termination.
> 7 votes

# Answer
Here is an approach involving only one mapping: $$ f = (a+1) \cdot (b+1) + (b - a) $$ Simple case analysis can show that $f$ always decreases as you go through the loop.
> 1 votes

---
Tags: algorithms, loops, loop-invariants
---


# Question
Title: DFA complement: DFA on $\{a,b\}$ that accepts string where the numbers of $a$s not multiple of n
I'm trying to understand how to create a DFA on the language $\\{a,b\\}$ that accepts strings where the number of $a$s is **not** a multiple of n.

Creating a DFA with no. of $a$s divisible by $n$ is easy. One simply makes $n$ states such that the string ends into the accept state per every $n$ of e.g. $a$s.

I've figured out that the set of "natural numbers not divisible by $n$" can be found by considering all $k$ such that $k=nm+j$, $0≤j\<n$.

I haven't been able to figure out how to translate this to a DFA. It's implicative that "not divisible" is a complement of "divisible".

# Answer
What about your "divisible" automaton and changing the accept states?
> 1 votes

# Answer
Build a DFA $A$ accepting strings with the number of $a$s divisible by $n$: $$A = (Q,\Sigma,\delta,q\_0,F).$$

Now you want to make a DFA accepting the complement of the language of A: $C(L(A)) = \Sigma^\*-L(A)$.

To do that take the complement of the final states of the original DFA: $$A' = (Q,\Sigma,\delta,q\_0,F'),$$ where $F' = Q-F$

**Update**

Let's prove $L(A') = C(L(A))$:

1) If $s \in L(A')$ then $\hat{\delta}(q\_0,s) \in F'$, where $\hat{\delta}$ is the extended transition function. Since $F' = Q-F$, it means that $\hat{\delta}(q\_0,s) \not \in F$, hence $s \not \in L(A)$, thus $s \in C(L(A))$.

2) If $s \in C(L(A))$, then $s \not \in L(A)$, so $\hat{\delta}(q\_0,s) \not \in F$. Therefore $\hat{\delta}(q\_0,s) \in F'$. But it means $s \in L(A')$.

That's pretty much all.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Prove or disprove NP-Completeness: An optimal ordering problem
Consider assigning a single object to $n$ potential receivers. It can only be assigned to one person.

For each receiver $k$, there is a value of profit $v\_k$ and a probability $p\_k$. Fix an ordering of the receivers, then for the $i$th receiver he accept the object with probability $p\_i$, if he does, we gain a value $v\_i$; if he doesn't, consider the next person in the ordering.

Then the expected value we gain is

$E(V)=p\_1v\_1+(1-p\_1)p\_2v\_2+\cdots +(1-p\_1)(1-p\_2)\cdots (1-p\_{n-1})p\_nv\_n$

It can be easily seen: to maximize the expected value we gain, the ordering should be in the decrease of the $v$.

But since passing through the potential receivers the object defects the value of it, the $i$th receiver has a parameter $w\_i$ where $w\_1\>w\_2\>\cdots\>w\_n$.

$v\_k$ is assigned to each person $k$, and $w\_i$ is assigned to the $i$th person in the ordering. For example if the $3$rd person in the ordering is person $5$, then he has $v\_5$ and $w\_3$.

so the expected value changes to

$E(v)=p\_1w\_1v\_1+(1-p\_1)p\_2w\_2v\_2+\cdots+(1-p\_1)(1-p\_2)\cdots(1-p\_{n-1})p\_nw\_nv\_n$

Is there a polynomial algorithm to give an optimal ordering that maximizes the expected value? Or should this be NP-Complete?

Any hint is appreciated. Thanks in advance.

# Answer
> 2 votes
I think your question is better written as follows (to avoid ambiguity): Find an order $\mathbf{s}=(s\_1,s\_2,...s\_n)$ (that is, a permutation of $(1,...,n)$) such that $$ E\_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p\_{s\_1}w\_1v\_{s\_1}+(1-p\_{s\_1})p\_{s\_2}w\_2v\_{s\_2}+\cdots+\left\[\prod\_{j=1}^{n-1}(1-p\_{s\_j})\right\]p\_{s\_n}w\_nv\_{s\_n}. $$ is maximized, where $w\_i$ is the positive weight for the expected achievable value at the $i^{th}$ stage, $\mathbf{v}=\\{v\_1,v\_2,\ldots,v\_n\\}$ and $\mathbf{p}=\\{p\_1,p\_2,\ldots,p\_n\\}$ are the positive profits and the probabilities associated with the $n$ receivers. If $w\_i$ is a linearly decreasing function, say, if $w\_i=1-i\tau$, the objective function becomes:

$$ E\_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p\_{s\_1}(1-\tau)v\_{s\_1}+(1-p\_{s\_1})p\_{s\_2}(1-2\tau)v\_{s\_2}+\cdots+\left\[\prod\_{j=1}^{n-1}(1-p\_{s\_j})\right\]p\_{s\_n}(1-n\tau)v\_{s\_n}. $$

Now, let us consider the following two orders which differ only in the $(i-1)^{th}$ and the $i^{th}$ positions: $\mathbf{s}=\\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\\}$ and $\mathbf{\tilde{s}}=\\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\\}$. It is easy to show that

$$ E\_\mathbf{s}\>E\_\mathbf{\tilde{s}}\Leftrightarrow\frac{v\_1}{\frac{\tau}{\theta\_1}+w\_i }\>\frac{v\_2}{\frac{\tau}{\theta\_2}+w\_i }. $$ which (I believe) implies that the problem cannot be solved by a simple index policy (i.e., a sorting algorithm), because whether $\mathbf{s}=\\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\\}$ or $\mathbf{\tilde{s}}=\\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\\}$ is better really depends on $w\_i$ (or the stage number $i$).

Here is a paper Optimal wideband spectrum sensing order based on decision-making tree in cognitive radio, which gives an exact algorithm assuming $w\_i=1-i\tau$ and they claim that it runs in polynomial time $O(n^3)$, although the space complexity seems to be exponential.

I believe their algorithm holds for general monotonically decreasing $w\_i$ values (with respect to $i$).

However, it seems that they solve the problem by finding the optimum from a set of candidate sequences. The running time is assumed to be proportional to the size of this candidate set. In order to find this candidate set, a branch and bound approach is adopted, but the time needed to compute this candidate set is ignored. **So I double if their running time claim is valid.**. I would really appeciate it if someone can convince me that their $O(n^3)$ claim is valid (and so it only takes at most $O(n^3)$ time to find the candidate set)? or if the problem (with $w\_i=1-i\tau$) is actually np-hard? Thank you!

# Answer
> 1 votes
If you need to solve this in practice, I would guess that branch-and-bound might be pretty effective here -- at least, it'd be the first approach that I would try.

I would expect that the choice of the 1st receiver will have a much larger effect on $E(v)$ than the choice of the last receiver; and for all $i\<j$, the identity of the $i$th receiver will typically have a larger effect on $E(v)$ than the identity of the $j$th receiver. This suggests applying branch-and-bound techniques, where you first select who the 1st receiver will be (enumerate all possibilities), then you select the 2nd receiver, and so on.

This gives you a tree of depth $n$, with $n!$ leaves, corresponding to all $n!$ possible orderings. An internal node at depth $d$ represents a partial assignment, where you've selected who the first $d$ receivers will be but you haven't selected the rest. Notice that, given the identity of the first $d$ receives, you can compute lower and upper bounds on the value of $E(v)$. For example:

$$p\_1 w\_1 v\_1 + \dots + (1-p\_1)(1-p\_2) \cdots (1-p\_{d-1}) p\_d w\_d v\_d + \epsilon \le E(v)$$

and

$$E(v) \le p\_1 w\_1 v\_1 + \dots + (1-p\_1)(1-p\_2) \cdots (1-p\_{d-1}) p\_d w\_d v\_d + \delta,$$

where

$$\epsilon = (1-p\_1)(1-p\_2) \cdots (1-p\_d) p\_n w\_{d+1} v\_n$$ $$\Delta = (1-p\_1)(1-p\_2) \cdots (1-p\_d) (p\_{d+1} w\_{d+1} v\_{d+1} + \dots + p\_n w\_n v\_n),$$

where we've sorted the remaining $n-d$ possible receivers into order of decreasing value of $p\_i v\_i$. Now using these bounds, you can use branch-and-bound techniques to prune subtrees that are dominated by the current best solution, without needing to explore any node in the pruned subtree.

Given how the first few receivers make the biggest impact on $E(v)$, and this procedure chooses the first few receivers first, I suspect you might be able to prune many subtrees, and branch-and-bound might often be very efficient on real-world instances of this problem. Of course, there are no guarantees. Even if this works well in practice, the worst-case complexity of this approach is probably still exponential. And to find out whether it *does* work well in practice or not, you'd have to implement it and try it out.

I realize this doesn't tell you the worst-case complexity of the problem. For instance, it doesn't you whether this problem is NP-complete or not. For that, you'd have to look for some other ideas.

# Answer
> 1 votes
If the weighting function $w\_i$ is an exponentially decreasing function of $i$, that is, if $w\_i=e^{-i\tau}$, then the problem can be solved in $O(n\log{n})$ time. In this case, the objective function becomes:

$$ E\_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p\_{s\_1}e^{-\tau}v\_{s\_1}+(1-p\_{s\_1})p\_{s\_2}e^{-2\tau}v\_{s\_2}+\cdots+\left\[\prod\_{j=1}^{n-1}(1-p\_{s\_j})\right\]p\_{s\_n}e^{-n\tau}v\_{s\_n}. $$

Now, let us consider the expected values associated with $\mathbf{s}=\\{1,2\\}$ and $\mathbf{\tilde{s}}=\\{2,1\\}$. We have:

$$ E\_\mathbf{s}=p\_1e^{-\tau}v\_1+(1-p\_1)p\_2e^{-2\tau}v\_2 $$

and

$$ E\_\mathbf{\tilde{s}}=p\_2e^{-\tau}v\_2+(1-p\_2)p\_1e^{-2\tau}v\_1. $$

It is easy to show that

$$ E\_\mathbf{s}\>E\_\mathbf{\tilde{s}}\Leftrightarrow\frac{p\_1v\_1}{e^\tau-1+p\_1}\>\frac{p\_2v\_2}{e^\tau-1+p\_2}. $$

This pairwise exchange argument can be easily generalized to $n\>2$ cases. That is, the optimal order $\mathbf{s}^\*=\\{s^\*\_1,s^\*\_2,\ldots,s^\*\_n\\}$ is the one such that the following chain of inequalities holds:

$$ \frac{p\_{s^\*\_1}v\_{s^\*\_1}}{e^\tau-1+p\_{s^\*\_1}}\>\frac{p\_{s^\*\_2}v\_{s^\*\_2}}{e^\tau-1+p\_{s^\*\_2}}\>\cdots\>\frac{p\_{s^\*\_n}v\_{s^\*\_n}}{e^\tau-1+p\_{s^\*\_n}} $$ which can be found using a sorting algorithm in $O(n\log{n})$ time.

For reference, see equation (2) in The Present Value Issue in a Sequential Selection Problem (you can set the costs $c\_i$ to zero).

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


# Question
Title: Confused by extremely high autocorrelation
I have the following python code

```
x = [100.0 for _ in range(1000)]
for i in range(1, len(x)):
     x[i] = x[i-1] + (2*randint(0, 1)-1)*step_size
import numpy as np
print np.corrcoef(x[:-1], x[1:])

```

I am getting extremely high correlation values, over 99.9%, more precisely

```
[[ 1.          0.99785636]
 [ 0.99785636  1.        ]]

```

Does anyone know what's going on? How can I get such large autocorrelation? Can anybody help me get better intuition and understanding of this?

# Answer
Most of the values of the random walk $x$ are large ($\omega(1)$) with high probability. Therefore the difference between $x\_i$ and $x\_{i+1}$, which is $\pm 1$, is small. So the random walk correlates well with itself.

You can get results even closer to $1$ if you start your random walk from some position far away from the origin. Try it out!
> 1 votes

---
Tags: machine-learning, randomness, statistics
---


# Question
Title: Solving recurrences by substitution method: why can I introduce new constants?
I am solving an exercise from the book of Cormen et al. (*Introduction To Algorithms*). The task is:

> Show that solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O(\lg n)$

So, by big-O definition I need to prove that, for some $c$,

$$T(n) \le c\lg n\\,.$$

My take on it was: $$\begin{align\*} T(n) &\leq c\lg(\lceil n/2\rceil) + 1 \\ &\< c\lg(n/2 + 1) + 1 \\ &= c\lg(n+2) - c + 1\\,. \end{align\*}$$ As this doesn't seem satisfactory I looked up a solution and the author after getting to the same stage as me decided to introduce a new arbitrary constant $d$: $$\begin{align\*} T(n) &\le c\lg(\lceil n/2-d\rceil) + 1 \\ &\< c\lg(n/2+1-d) + 1 \\ &\< c\lg((n-2d+2)/2) + 1 \\ &= c\lg(n-2d+2) - c + 1 \\ &= c\lg(n-d-(d-2)) - c + 1\\,. \end{align\*}$$

And now, for $d \ge 2$, $c \ge 1$ and $n \> d$,

$$c\lg(n-d-(d-2)) - c + 1 \le c\lg(n-d)\\,.$$

What I don't understand is how does it prove that $T(n) \le c\lg n$? Cormen et al. make a big point that you have to prove the *exact form of the inductive hypothesis* which in this case was $T(n) \le c\lg n$. They then go on to show example similar to one above.

How is that the exact form of the inductive hypothesis? This doesn't seem to fit the big-O definition. When can I omit constants or cheat them away? When is it wrong?

# Answer
> 1 votes
I am guessing that the book wants you to proof the stronger hypothesis $T(n) \leq c\log( n -d)$ which implies $T(n) \leq c log(n)$ is also true ( because $n \geq n -d$ for $d\geq 0$. )

---
Tags: algorithm-analysis, proof-techniques, recurrence-relation
---


# Question
Title: Is there a decidable problem which has a proof that it cannot be proved to have a particular deciding Turing machine?
I came across the question Is there an algorithm that provably exists although we don't know what it is? I was able to follow the example "Given an integer $n\ge0$ is there a run of $n$ or more consecutive 7s in the decimal expansion of $\pi?$" given in one of the answers. The answer shows that the problem in example is decidable although we don't know which is the correct algorithm. Let $P$ be a problem which is decidable, we know that for some for some finite integer $k \> 1$ one of the Turing machines $M\_1,M\_2,..,M\_k$ decides the problem, but we don't know which of them exactly is the decider. Is it possible that $P$ has a finite proof which tells us that it is not possible to prove exactly which of the machines is the decider ? Or is it always, that the proof exists proving that exactly one of the machines is the decider but we don't know it ?
I am not even sure if my question makes sense. I could make changes or remove the question if it does not not. Sorry for the vague definition of a proof.

# Answer
Let us examine the following language:

$x\in L \iff ZFC \hspace{1mm} \text{is consistent}$.

Clearly, $L$ is decidable, and is decided by either the constant 1 or 0 machines.

Proofs from ZFC for the statements "$M\_0$ decides $L$", "$M\_1$ decides $L$" cannot exist (if ZFC is consistent), since any of those would imply a proof from ZFC about its own consistency (see Godels's second incompleteness).

Note that i can however, provide a proof that the following machine $M$ decides $L$:

Given input $x$, check if there exists a proof for the consistency of ZFC, of length$\le |x|$. If such proof is found, return 0, otherwise return 1.

If ZFC is consistent, the above machine outputs 1 for all $x$. If it isn't, we also have a proof that the above machine decides $L$ (An inconsistent system can prove any statement). The problem is that i cant prove whether or not $M$ computes the constant 1 function.
> 2 votes

---
Tags: computability, logic, incompleteness
---


# Question
Title: How to read a DFA for digit summation that uses carry bits?
I'm looking to understand how can one graph the following DFA given its mathematical definition.

Take for example this (from \[1\], p. 107):

* **Set of States**: $Q = \\{q\_{\langle carry=0\rangle}, q\_{\langle carry=1 \rangle}\\}$
* **Alphabet**: $\Sigma = \\{\langle x\_{i}, y\_{i}\rangle \mid x\_{i},y\_{i}\in\[0..9\] \\}$
* **Start State**: $s = q\_{\langle carry=0\rangle}$
* **Transition Function**: $\delta(q\_{\langle carry=c\rangle}, \langle x\_{i}, y\_{i}\rangle) = \langle q\_{\langle carry=c'\rangle}, z\_{i}\rangle$ where $c'$ is the high order digit of $x\_{i} + y\_{i} + c$ and $z\_{i}$ is the low order digit.

How does one read the required no. of states and the edges with their symbols?

**References**

1. J. Edmonds, *How to Think About Algorithms*, Cambridge University Press, 2008.

# Answer
The problem here is not really in the implementation of the DFA, but in understanding what the DFA is doing. With those who have access to the text, careful reading of the algorithm preceding it should give a deal of understanding.

From the perspective of the DFA, it has two states, as listed in the **Set of States**, the symbols on the transitions are pairs of numbers, i.e. each "symbol" is written as five characters (for our understanding, we could encode them any sensible way we wanted of course).

The tuple as the right hand side of the transition function is unusual (and as far as I can seem undefined in the text). What is actually represented here is a finite state transducer, which are essentially equivalent to a DFA, but get to produce a symbol of output at each transition. So the $z\_{i}$ is what gets written to the *output tape* that normally doesn't exist. It also doesn't have an accept state, as the output is no longer yes or no, but whatever is written on the tape.

Now, to understand the construction in full, we need to understand what it's trying to do - add two decimal numbers. It does this digit by digit (from right to left). At each individual addition (digits $x\_{i}$ and $y\_{i}$), there might be a carry digit, which needs to be remembered for the next addition.

When two decimal digits are added, there are only two possible carries: $0$ or $1$. If we already have a carry, this is still true (the limit cases are $x\_{i} = y\_{i} = c = 0$ and $x\_{i} = y\_{i} = 9$, $c = 1$). To put this another way, the output of adding two decimal digits and a carry bit is a two digit number $c' z\_{i}$, where $c'$ is the carry bit for the next addition and $z\_{i}$ is the decimal output digit.

To give an example of the result, here's the transducer for the binary case. Each transition gives the two input digits, the output digit and target state of the transition. Remember that each transition implicitly includes the carry bit in the addition:
> 2 votes

# Answer
$Q$ is the set of states. Therefore, the number of states is exactly the cardinality of $Q$, i.e., $|Q|$.

Each transition corresponds to an edge. If $\delta(q,x)=q'$, then there is an edge from state $q$ to state $q'$ on input symbol $x$, so you draw an arrow from $q$ to $q'$ and label it with $x$.
> 0 votes

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


# Question
Title: What is the difference between regular trees and phylogenetic trees in terms of graph theory?
If I am not mistaken, a tree is any graph that does not contain cycles.

However, I am currently taking a bioinformatics course where we deal a lot with algorithms on phylogenetic trees. Usually you are given a phylogenetic tree with $n$ leafs, and then you run some algorithm that can do something trivial like simple traversing of the tree, and then you get a $O(n)$ time bound, without saying anything about the number of internal nodes.

However given a regular tree with $n$ leafs, the total number of internal nodes can be infinite.

For example the following is a tree with one leaf (two if you consider it to be rooted) and infinite number of internal nodes:

So what are phylogenetic trees that you can express the running time of various algorithms in terms of the number of leafs, even though your algorithm actually traverses the entire phylogenetic tree?

# Answer
> 3 votes
Phylogenetic trees are usually "full binary trees", that is rooted trees in which every internal node has exactly two children. A full binary tree having $n$ leaves has exactly $2n-1$ nodes.

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


# Question
Title: Fill in objects that pop out from background?
I need some help with a program that will fill in objects that pop out from the background. For example I have this picture and would like to get an output like this.  I don't know how to do this though (obviously otherwise I wouldn't be asking). And I was wondering if there was some way of filling in objects that don't match the background. The only other thing is that the background isn't always going to be white for example the background could be a blue blanket with a brown dog on it. In that picture it would fill the dog in Black. The last thing about this is that the object that will be filled in will always be centered in the image.

# Answer
Here is one simple approach:

Step 1. Find the background color. (This is an entire topic in its own right, so if you're not sure how to do this, ask a separate question about it.)

Step 2. Binarize the image so that all pixels whose color is close to the background color are white, and all pixels whose color is not similar to the background color are black. This will get you a rough approximation to what you want, but there might be holes in the middle of the black shape (e.g., if the cat was wearing a white collar).

Step 3. Apply a suitable morphological operator, e.g., the closing operator.

This approach will have some limitations, e.g., if the background is not flat but rather has shading or a gradient, but it is simple to implement and try.

If the simple approach I outlined above is not sufficient, the broad problem area you are looking at is image segmentation; you should check out the techniques that have been developed in the literature. There are many, many methods for image segmentation that you could explore. For instance, you could look at methods based upon graph cuts.
> 2 votes

---
Tags: algorithms, image-processing
---


title: Why the extra state in this automaton?

text:
# Question
Title: Why the extra state in this automaton?
Why does the following DFA have (to have) the state $b\_4$?

Shouldn't states $b\_1,b\_2,b\_3$ already cover "exactly two 1s"? Wouldn't state $b\_4$ mean "more than two 1s", even if it doesn't trigger an accept state?

# Answer
> 7 votes
$b\_4$ is what is called a *trap state*, that is, a state that exists just so that all possible transitions are explicitly represented, even those that do not lead to a final state.

It doesn't change the language that is being defined, and can be omitted for the sake of brevity.

# Answer
> 2 votes
b4 exists to cover the entire alphabet (\[0,1\], in this case) for each state. While this is not strictly necessary, it is a hot topic of discussion in the field.

By showing the complete graph, it is more obvious that a third '1' in your input string permanently moves you out of the 'accept' state b3.

# Answer
> 2 votes
The formal definition of a DFA is $M = (Q, \Sigma, \delta, q\_0, F)$, were $Q$ is the finite set of states, $\Sigma$ is the alphabet, $\delta$ is the transition function, $q\_0 \in Q$ is the start state, and $F \subseteq Q$ is the set of final states. Note that $\delta \colon Q \times \Sigma \to Q$ is specified to be a *function*, i.e., it has to be defined for all states and symbols. The graphical depiction of the DFA is complete in this sense with $b\_4$. Often such *dead states* are just omitted in the sake of clarity of the diagram, the reader is surely capable of adding them if required.

# Answer
> 0 votes
Answering your question I have to say(sadly) that it depend. It depends on the definition of DFA that you are using because it appears to not be concensus in a unique definition.

For example I use the definition of the DFA where $\delta$ is a function. The next question is: Is $\delta$ a total function or a partial function?

Personally when I use the term function I am refering to total functions by default. But someone can disagree with me. More importantly when I studied the definition of a DFA my teacher told me that $\delta$ is a total function.

Summarizing I use a particular definition of a DFA where the $b\_4$ state have to exist. I can skip drawing it for the sake of laziness or clarity, but I know it exist.

Finally to answer your question more precisely we have to know what definition of DFA you use.

**Wouldn't state b4 mean "more than two 1s", even if it doesn't trigger an accept state?**

The state $b\_4$ means that if a word $\sigma$ have more than two "1" it will never reach an accepting state so $\sigma\notin L = \\{w\\,|\\, \text{contains exactly two ones}\\}$.

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


# Question
Title: Intersection of Turing-recognizable language and regular language
True or false: An intersection of a Turing-recognizable and a regular language is always Turing-decidable.

This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.

Is that not correct?

# Answer
> 3 votes
> I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.

There are two confusions here.

First, your seamless switch from "decidable languages" to "recognizable" makes it sound as if you think that decidable and recognizable are the same thing: they're not.

Second, you're confusing the concept of the set of regular languages being a subset of the set of decidable languages with the concept of a particular regular language being a subset of a particular decidable language. Saying that the regular languages are a subset of the decidable languages (which is true) is just saying that every regular language is decidable: this is true. However, that doesn't tell you that every regular language is a subset of every decidable language: it tells you that every regular language *is* a decidable language. For example, consider $L\_1 = \\{a^n\mid n\geq 0\\}$ and $L\_2 = \\{a^n\mid n\text{ is prime}\\}$. $L\_1$ is regular and $L\_2$ is decidable but $L\_1\not\subseteq L\_2$. But the fact that $L\_1$ is regular does tell you that $L\_1$ is also decidable.

Putting these two things together gives us the following.

1. If you intersect the set of regular languages with the set of recognizable languages, you get the set of languages $$\\{L\mid L \text{ is regular and }L\text{ is recognizable}\\}\\,.$$ Since every regular language is recognizable, this is just the set of regular languages.
2. If you intersect an individual regular language $L\_1$ with an individual recognizable language $L\_2$, you get the set of words $$\\{w\mid w\in L\_1\text{ and }w\in L\_2\\}\\,.$$ You can prove that this is recognizable (write a recognizer for it!) but it's not necessarily decidable or regular.

# Answer
> 8 votes
A recognizable language is not necessarily decidable. If you intersect such a language with $\Sigma^\*$ it doesn't suddenly become decidable.

# Answer
> 4 votes
The intersection is a subset of a decidable set, but so is every language. After all, the language of all strings over a given alphabet is trivially decidable (the decider always says "yes"), and any language is a subset of the language of all strings over its alphabet.

---
Tags: turing-machines, regular-languages, automata
---


# Question
Title: Closure properties of finite state transducers
> Given $T\_1, T\_2\colon \Sigma^\* \to \Gamma^\*$ ($\Gamma$ is output alphabet), let $\Delta(T\_1, T\_2)$ consist of all input strings $w \in Σ^\*$ where $T\_1(w) \neq T\_2(w)$. Prove that FSTs are not closed under this operation $\Delta(T\_1,T\_2)$.

What I have tried is to create two FSTs $T\_1, T\_2$ (as 5 tuple functions of form $(Q, \Sigma, \Gamma, \delta, s, γ)$ where $\Sigma$ - input symbols, $\Gamma$ - output symbols, $δ\colon Q \times \Sigma → Q$ transition function, to prove that the language $S = \\{ w \mid T\_1(w) \neq T\_2(w) \\}$ is not regular. I am having trouble creating the two FSTs. Especially defining the transition functions for the two FSTs. Any help with this is appreciated.Pretty much what I am trying to prove is there are two FST's $T\_1$ and $T\_2$ such that the language $L = \\{w \mid T\_1(w) \ne T\_2(w)\\}$ is not regular. To prove this, what I want to do is create the two FST's $T\_1$ and $T\_2$. I am not sure on how to define a 6-tuple FST. Especially coming up with the transition functions for the two FSTs

# Answer
> 2 votes
It is probably a better idea first to concentrate on the complement, i.e., the equality language $\\{ w\in \Sigma^\* \mid T\_1(w) = T\_2(w) \\}$.

Also, simple FST's will do, as even for morphisms $h\_i: \\{a,b\\} \to \\{1\\}^\*$, $\\{ x\in \\{a,b\\}^\* \mid h\_1(x) = h\_2(x) \\}$ need not be regular.

And I want to add that it has been shown that $\Delta(T\_1,T\_2)$ is always context-free.

---
Tags: automata, finite-automata, closure-properties, transducers
---


title: What terms type systems exclude?

text:
# Question
Title: What terms type systems exclude?
I understand type systems like the simply typed lambda calculus, system F and the calculus of constructions include a different subset of all lambda terms. But what, precisely, are the terms each of those systems include/exclude? Is it possible to express the intuition behind the criteria with words?

# Answer
> 5 votes
In the **simply-typed lambda calculus**, the type of a function must be fully specified, even when it's irrelevant. A trivial example is the identity function: in the lambda calculus, it's $\lambda x.x$; in the simply-typed lambda calculus, there isn't a single identity function but rather a family of identity functions $\lambda x:T. x$ for every type $T$. This means that the simply-typed lambda calculus has no polymorphism. If you think about data structures, more concrete examples come up — you can't write, say, a generic function like list reversal, you have to write it all over again for each type of list elements. You can't even write basic primitives like `nil` and `cons`, only typed-indexed primitives $\texttt{nil}\_T$ and $\texttt{cons}\_T$.

To give a concrete example in the pure lambda-calculus (without constants), natural numbers can be encoded as Church numerals in the untyped lambda calculus: $$\begin{align} 0 &= \lambda f. \lambda x. x \\ 1 &= \lambda f. \lambda x. f x \\ 2 &= \lambda f. \lambda x. f (f x) \\ &\ldots \end{align}$$ In the simply-typed lambda calculs, there is a separate family of Church numerals for each type: $$\begin{align} 0\_T &= \lambda f : T\to T. \lambda x : T. x \\ 1\_T &= \lambda f : T\to T. \lambda x : T. f x \\ 2\_T &= \lambda f : T\to T. \lambda x : T. f (f x) \\ &\ldots \end{align}$$ You can't compose Church numerals of different types, which makes it difficult to use the same number for different things.

In the **Hindley-Milner type system** (which I'm including because it's an important step), polymorphic functions are possible, but with restrictions. Hindley-Milner requires a new syntactic form in addition to variables, application and abstraction: the let binding $\texttt{let } x = M \texttt{ in } N$. If all or part of the type of $M$ is irrelevant then it can be left as a variable, and the variable $x$ has not a type but a *type scheme* of the form $\forall \alpha\_1,\ldots,\alpha\_k, T$ where the $\alpha\_i$ are type variables and the type expression $T$ can contain these variables. For example, it is possible to define the identity function once and for all: $$ \texttt{let } \texttt{id} : (\forall \alpha, \alpha\to\alpha) = (\lambda x:\alpha. x) \texttt{ in } \ldots $$ Similarly one can define Church numerals and (more practically) data structure manipulation (e.g. of lists, arrays, etc.) without having to duplicate the definitions for every type of element.

This form of polymorphism is known as parametric polymorphism; HM does not allow functions to behave differently depending on the types of their arguments. This allows proving properties of programs, such as “a function of type $\forall \alpha, \texttt{list}(\alpha) \to \texttt{int}$ only depends on the length of the list and not on the value of the elements”. This is known as “theorems for free” after the famous paper by Phil Wadler. An example of a practically useful function that cannot be expressed in HM is $\ge : \forall \alpha, \alpha \to \alpha \to \texttt{bool}$ which defines a total order — by parametricity, any such function is consant or non-terminating. More generally, HM cannot express ad hoc polymorphism (also known as generic programming in type theoretist circles, but beware that “generics” means parametric polymorphism in OOP circles).

In **System F**, functions can be parametrically polymorphic with no restrictions. Any lambda term can have universal quantifiers on types, which removes the distinction between $\lambda$ and $\texttt{let}$. Ad hoc polymorphism is still impossible (parametricity results still hold). System F allows more polymorphism than HM, at the expense of type inference (which is relatively easy for HM, and undecidable in System F).

Above I gave examples of programs that can't be expressed in HM and can't be expressed in System F either. Let me now give examples of programs that can be expressed in System F but not in HM. Simple examples are a bit more subtle. One simple example is the lambda term $\lambda x. x \\, x$. What does it take to type it? In order for $\lambda x:T. x\\,x$ to be well-typed, $T$ must satisfy the equations $T = T\_1 \to T\_2$ (for the occurrence of $x$ in function position) and $T\_1 = T$ (for the occurrence of $x$ in application position). In Hindley-Milner, this is impossible, because types have a simple tree structure and a type satisfying these equations would have to be infinite. In System F, this term can be typed by breaking the recursion with a type abstraction: $$ \Delta\_F = \lambda x: (\forall \alpha, \alpha\to\alpha). x \\, (\forall \alpha, \alpha\to\alpha) \\, x $$ While this may look of theoretical interest only, this is of highly practical interest when generalized to data structures. The term $\Delta$ condenses the wish for a single object to behave in a polymorphic way. System F, unlike HM, can express objects with polymorphic methods.

Besides ad hoc polymorphism, an important class of terms that still cannot be typed in System F is non-terminating functions. While $\Delta = \lambda x. x \\, x$ can be typed in System F, the “utmost” non-terminating term $\Delta \Delta$ cannot be typed.

System F expands the simply-typed lambda calculus by adding terms depending on types. Other directions for expansion are types depending on types, and types depending on terms. These three dimensions for expansion are known as the Barendregt cube or lambda cube. (This should actually be a hypercube, but the lambda calculus itself is built on terms depending on terms, and the half of the hypercube that doesn't have terms depending on terms isn't studied often.)

Types depending on types allow generic data structures to be defined. For example, although HM is sufficient to write polymorphic functions on lists, defining a `list` type operator requires more than a basic Hindley-Milner or System F type system: it requires the ability to parametrize the types of lists by the type of their elements.

Types depending on terms are known as dependent types. Dependent types are very powerful, at the expense of making type checking more difficult and requiring often large annotations. An example of constraint that requires dependent types is tracking array lengths through a type family $\texttt{array} : \mathsf{Type} \to \mathbb{N} \to \mathsf{Type}$, allowing the typing of functions such as $$ \texttt{concatenate}\_T : \forall n:\mathbb{N}, \forall m:\mathbb{N}, \texttt{array}\\,T\\,n \to \texttt{array}\\,T\\,m \to \texttt{array}\\,T\\,(n+m) $$

The calculus of constructions includes all possible abstractions (terms depending on terms or types, types depending on terms or types). Even in the calculus of constructions, neither ad hoc polymorphism nor non-terminating functions are possible.

# Answer
> 2 votes
One such excluded term is the $Y$ combinator: $ (\lambda f . (\lambda x . f (x x) (\lambda y . f (y y))$. Intuition says that that this has type $(a \rightarrow a) \rightarrow a$, but the intermediate terms can't be assigned proper type values using Hindley-Milner types (I'm not sure about more powerful systems).

The intuition I have for what terms are excluded is: terms which would result in a type-error, and terms which wouldn't result in a type error, but for which the proof that there is no error can't be expressed in the type system.

For example, the term $(\lambda f . (f \ 3) + (f\ False))(\lambda x . 5)$ can be evaluated without any type errors. With higher-rank types, we can give the first function the type $(\forall a \to Int ) \to Int$, and the second one type $\forall a \to Int$, and the program will typecheck. But in normal Hindley-Miller types, there's no way to express that that the parameter $f$ takes any type to an $Int$, so this term is excluded.

In general, it has to do with the expressiveness of the type system, and it's ability to prove whether a program is safe. I also suspect that Godel's results come into play here: there are statements which are true that cannot be proven. I'm willing to bet that in many cases, these correspond to untyped lambda terms which are type-safe, but for which no proof of safety exists in stronger type systems.

---
Tags: type-theory, functional-programming
---


title: Value returned by recursive function

text:
# Question
Title: Value returned by recursive function
(pseudocode)

```
f(x,y,z)
{
    if (x < y)
    {
        return 1 + f(x + 1, y, z)
    }
    else if (y < z)
    {
        return 2 + f(x, y + 1, z)
    }
    else
    {
        return z
    }
}

```

The function call `f(12,14,20)` returns $40$. Why is this the case? As the final statement is `return z`, should it not simply return $20$, which would be the value of $z$ at which the recursion stops - $(20,20,20)$?

How does one go about analysing such a function?

# Answer
Here's what goes on; there are three different cases:

1. If $x\<y$, you pass from $(x,y,z)$ to $(x+1, y, z)$ and add 1 to the eventually returned result.
2. If $x\ge y$ and $y\<z$, you pass from $(x,y,z)$ to $(x,y+1, z)$ and add 2 to the result.
3. If $x\ge y$ and $y\ge z$ you return z (plus all the additions you made in cases (1) and (2).

Suppose, for simplicity's sake, we start with $(2,4,6)$. First, we're in case (1), so we pass from $(2,4,6)$ to $(3,4,6)$ and add 1. We then pass to $(4,4,6)$, adding another 1 and pass to case (2). In general, we'll add $1\cdot(y-x)$ in this case.

Now we alternate between case (2) and case (1). In this example, we'll go from $(4,4,6)$ to $(4, 5,6)$ (case 2) and add 2 and then from $(4,5,6)$ (case 1), add 1, and go to $(5,5,6)$, so we've gone from $(4,4,6)$ to $(5,5,6)$ and added 3. Another case (2), case (1) will get us to $(6,6,6)$ In general, we'll add $3\cdot(z-y)$ in this case.

Finally, we arrive at $(6,6,6)$ and find ourselves in case (3) where we return 6 plus the adds we made earlier, namely 2 to get from $(2,4,6)$ to $(4,4,6)$, 6 more to get from $(4,4,6)$ to $(6,6,6)$ for a grand total of $f(2,4,6)=2+6+6=14$.

In general, when $x\le y\le z$ we'll have $$ f(x,y,z)=1\cdot(y-x)+3\cdot(z-y)+z=4z-2y-x $$

It's not hard to establish similar results in the cases where $x,y,z$ aren't sorted in increasing order.

\[By the way, $f(12,14,20)=4\cdot20-2\cdot14-12=80-28-12=40$.\]
> 4 votes

# Answer
D.W. has included a general method for tracing recursive calls in a code, in his answer. Or as Rick Decker has pointed you can also try to solve the recurrence relation. Adding to what they have explained, I would like to point that while tracing or keeping track of the recursive calls in general you may want to take the aid of stacks ( that is how recursion is implemented in programming languages ). I will try to show how it helps in your example.

```
( 20 20 20 ) | 20  |
( 19 20 20 ) |  1  |
( 19 19 20 ) |  2  |
( 18 19 20 ) |  1  |
( 18 18 20 ) |  2  |
( 17 18 20 ) |  1  |
( 17 17 20 ) |  2  |
( 16 17 20 ) |  1  |
( 16 16 20 ) |  2  |
( 15 16 20 ) |  1  |
( 15 15 20 ) |  2  |
( 14 15 20 ) |  1  |
( 14 14 20 ) |  2  |
( 13 14 20 ) |  1  |
( 12 14 20 ) |  1  |

(x,y,z)      | value to be added while returning |

```

In the above figure, the stack grows from bottom to top. The left hand side represents the `x,y,z` triplet, that is the arguments of the recursive calls. The right hand side is the stack in the figure. It's elements are **what you have to add to the answer you get from the next recursive call** . I might not be able to put it in good language. An example might help. Initially you are at the bottom `12,14,20`, from here you call the function again with arguments `13,14,20`. Once you have an answer from `13,14,20` you will add `1` ( because you are doing `1 + f(13,14,20)` ) to whatever you received from the call with arguments `13,14,20` and return it. Thus you push `1` into the stack. Likewise the stack is build from bottom to top. Once the call `20,20,20` you have to return value `20` ( that is the value of `z`, the else part of the code ) to the previous recursive call. From this point onward just start popping the stack , and when you pop an element add it to the element which is now at the top. This way you will get answer to be `40` in the end.
> 3 votes

# Answer
Here's one way to go about analysing this situation: "run" the code by hand, one step at a time. Build a table where you predict what the value of each variable will be at each step of execution. Then, run the program in a debugger and see what the actual values are at each step. Use this to identify the first step where your predictions don't match the actual values.

This will let you identify a single statement in the code that you don't understand: a single statement where you know the value of all variables before executing that statement, and where you know the value afterwards, and where your prediction for the value afterwards doesn't match the actual values. This lets you narrow down exactly where you went wrong. Often, once you've done that, it will become easier to see or hypothesize what might be wrong with your understand.

With this approach, you can construct a "minimal working example": a minimal program that behaves differently from what you'd expect. Your minimal working example will be a three-line program, where the first line sets the value of all the variables, the second line is the single line you identified above, and the third line prints out the value of one of the variables. Identifying a minimal working example is a key debugging skill.

(To elaborate, when I talk about "running" the code by hand one step at a time, here's what I mean. This means tracing through through the sequence of recursive calls one-by-one, and tracing through the execution of each line of code one line at a time.)
> 2 votes

---
Tags: recursion
---


# Question
Title: Converting sets into regular expressions
In my book:

* The set `{abb, a, b, bba}` is said to be converted into regular expression `abb + a + b + bba`.
* The set `{01, 10}` to regular expression `01 + 10`

Does the `+`'s here represent concatenation or union?

# Answer
> 4 votes
We don't quite convert a set to a regular expression. Rather, we give a regular expression for a *language* (i.e., a regular expression which defines the same language). For example, a regular expression for the language $\\{01,10\\}$ is $01+10$, and a regular expression for the language $\\{abb,a,b,bba\\}$ is $a+b+abb+bba$. There can be other regular expressions. For example, another regular expression for the second language is $a(\epsilon+bb) + b(\epsilon+ba)$.

Regarding the syntax of regular expressions, this should be explained in your book.

---
Tags: regular-expressions, notation
---


# Question
Title: if $\delta(q, a) = q$ for all symbols $a$, show that $\delta^* (q, w) = q$ is true for all strings $w$
> Let $A$ be a DFA and $q$ a particular state of $A$, such that $\delta(q, a) = q$ for all input symbols $a$. Show by induction on the length of input that for all strings $w$, $\delta^\* (q, w) = q$.

I'm completely new to the subject. But this is what I have done. Can someone please tell me if this is the correct solution?

For the basis of the induction $|w|=1$, $\delta (q,a)=a$ is already correct by definition.

Let $n = |w|$, the number of symbols in the string $w$. Let $\delta^\*(q,w)=q$ be true for some $n \gt 1$ (hypothesis of induction). Now I should prove it for $n+1$ using the hypothesis of induction. Let $z=wa$.

$$ \delta^\*(q,z) = \delta^\*(q,wa) $$

It follows that: $$ \delta^\*(q,wa) = \delta^\*(\delta^\*(q,w),a) $$

From the hypothesis, I know that $\delta^\*(q,w)=q$, so if I substitute this in the above equation:

$$ \delta^\*(q,a) $$

and this is equal to $q$ according to the base case. So, I conclude that $\delta^\*(q,w)=q$ is true for every $n$.

Is the above so-called "solution" correct?

# Answer
By popular request, here is what the proof could look like:

> By induction over the length of $w$. Assume $\delta(q,a)=q$ for all $a$. Take any $w$. There are two cases:
>
> 1. If $|w|=0$ then $w=\epsilon$ (the empty word). Now the definition of $\delta^\*$ has "$\delta^\*(q,\epsilon)=q$" without any assumption on $\delta$ or $q$. We thus have $\delta^\*(q,w)=q$ in this first case.
> 2. If $|w|\>0$ then $w$ is some $w'a$ and $|w'|\<|w|$. Now $\delta^\*(q,w)=\delta^\*(q,w'a)=\delta(\delta^\*(q,w'),a)$ by definition of $\delta^\*$. Since $|w'|\<|w|$ we have $\delta^\*(q,w')=q$ by induction hypothesis. Finally $\delta^\*(q,w)=\delta(q,a)$, which is $q$ by the assumption. We have proved the required conclusion in this second case too.
>
> All cases have been covered. The proof is complete.
>
> Note that the two cases can be considered in any order we like. And that we do not use that $|w'|=|w|-1$, just that $|w'|\<|w|$.

As you can see, the above proof uses the same arguments as in your solution, and at the same places. It is slightly more rigorous on the quantifications ("take any $w$" is a "$\forall w$" and "$w$ is some $w'a$" is a "$\exists w'\exists a:w=w'a$") and their nesting ($w'$ and $a$ depend on $w$).

It is the kind of proof I'd love to get from a bright student beginning automata theory. But it is too pedantic and pedestrian for experts who, in their own papers, will usually just state the conclusion as obvious from the assumption. They may even not state the conclusion at all and use it anyway.
> 5 votes

---
Tags: automata, finite-automata, proof-techniques
---


title: Help with building a NFA automaton

text:
# Question
Title: Help with building a NFA automaton
$\Sigma=\\{a,b\\}$, $L=\\{w\in \Sigma^\* \Big| |w|=3n+5m, \ n,m\ge 0 \\}$.
I need to build NFA automaton for $L$....

Now, I try it for hours but I don't have any idea how to solve it.
I know that any $x\ge 8$ can be written as $3n+5m, \ n,m\ge 0 $ So, the automaton accepts any word the her length is 8 or higher, but it doesn't accepts words at length: 1,2,4,7.
One more rule: $|Q|=5$....

Can you help me please and guide me how should I solve it?
Because I don't have any idea so far...
Any automaton that I make accepts some of the words in the forbidden length...

Thank you!

# Answer
> 2 votes
Just a hint:

If the requirement was to count the length $3n$, the NFA was simple, and could be done with 3 states. Similarly, if you only needed the $5m$ part, an easy 5-state NFA could do this.

Now think how to "combine" these two NFAs, one on top of the other. Use $\epsilon$-moves to go from the end of one, to the start of the another. Because you need $|Q|=5$, you will have to overload the meaning of 3 states so they serve both the $3n$ and the $5m$ machines.

Another hint that may be helpful: make $q\_0$ accepting (and the only accepting state).

Good Luck.

# Answer
> 1 votes
Hiding in here is the classic postage stamp problem: Given a collection of 3-cent and 5-cent stamps, what amount of postage can you make? You can clearly make 0, 3, 5, 6, 8, 9, and 10. Since you can make 8, 9, and 10, you can make any larger amount by adding 3-cent stamps. For example, from 8, 9, 10, you can make 11 (= 3 + 8), 12 (= 3 + 9), 13 (= 3 + 10) and it's easy to see that you can continue this process to make any amount greater than or equal to 8.

Now the DFA is easy: Have nine states, $q\_0, q\_1, \dotsc,q\_9$ where $q\_i$ "remembers" that you've seen a string of length $i$ so far. The transitions will be $\delta(q\_i, a) = \delta(q\_i, b) = q\_{i+1}$ for $i=0,\dotsc, 8$ and $\delta(q\_8, a) = \delta(q\_8, b) = q\_8$. The final states will be $q\_0, q\_3, q\_5, q\_6, q\_8$.

---
Tags: regular-languages, automata
---


# Question
Title: Reduction from deciders of the universal to deciders of the empty language
$ALL\_{TM} = \\{\langle M\rangle | \\; M$ is $TM$ and $L(M)=\Sigma^\*\\}$
$E\_{TM} = \\{\langle M\rangle | \\; M$ is $TM$ and $L(M)=\emptyset\\}$

I can't find reduction of $ALL\_{TM}$ to $E\_{TM}$. But I can't proof that it does not exist. Is there is such a reduction?

# Answer
> 2 votes
The point to note is if you can reduce $L\_1$ to $L\_2$ then the same reduction/mapping can be used to see that $\overline{L\_1}$ is reducible to $\overline{L\_2}$. The following is the proof, avoid if you just needed the hint.
Now we know $E\_{TM}$ is not Turing recognizable but $\overline{E\_{TM}}$ is. Secondly we know $\overline{ALL\_{TM}}$ is not Turing recognizable . So say if $ALL\_{TM}$ is reducible to $E\_{TM}$, then it would mean $\overline{ALL\_{TM}}$ is reducible to $\overline{E\_{TM}}$, and as $\overline{E\_{TM}}$ is Turing recognizable $\overline{ALL\_{TM}}$ would become Turing recognizable which is a contradiction.

---
Tags: computability, reductions
---


# Question
Title: How to design a PDA for the language of words with s a's, t b's and s⋅t c's?
I have the language

$\qquad L=\\{ a^s b^t c^m \mid s,t,m \\; \in \\; \mathbb{N^{+}} \text{ and } t\<4, s \cdot t=m\\}$.

How do I go about designing a PDA for it ?

I can't figure out a way to deal with $m$.

# Answer
The problem was: how to remember the amount of b and use it to count number of c. Well I guess I was lucky since there were only 3 possible cases. t=1, t=2 and t=3.

Here is my solution:

It might not be optimal, feel free to propose changes or better solutions.
> 1 votes

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


# Question
Title: Secondary Storage in Von Neumann Achitecture
For an assignment, I need to draw a diagram of Von Neumann architecture, and explain each part of it.

All the diagrams and explanations I've seen have a distinct "Memory" block that holds both the code and the program data of running processes. What I can't find information on however is if this memory refers to only primary memory (like RAM), or if it also includes secondary memory (like a SSD or HDD).

Does Von Neumann Architecture specifically refer to only primary memory, or does it also include secondary storage?

I'd also like to know if I'm using any terminology incorrectly above.

# Answer
The von Neumann architecture concerns only memory and CPU, not peripherals or devices. Storage, such as a hard disk or SSD, is typically a device, and thus is outside the scope of what's normally shown in the von Neumann architecture. Thus, in a picture of the von Neumann architecture, the block labelled "memory" should be understood to refer to RAM -- not hard disk or SSD.

In particular, in the von Neumann architecture, the CPU can access memory through a bus (the memory bus). In real computers, typically the memory bus cannot be used to read or write the hard drive; there's a separate path for accessing devices like the hard drive. (That's from the perspective of the architecture/hardware level. However, the lines can admittedly start to get blurred a bit from the user application's perspective, given memory-mapped devices, virtual memory, and demand paging.)
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Proof that dead code cannot be detected by compilers
I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter, but it has me stumped so I might use it as an example instead.

```
public class DeadCode {
  public static void main(String[] args) {
     return;
     System.out.println("This line won't print.");
  }
}

```

In the program above, it's obvious that the print statement will never execute because of the `return`. Compilers sometimes give warnings or errors about dead code. For example, the above code will not compile in Java. The javac compiler, however, will not detect all instances of dead code in every program. How would I prove that no compiler can do so?

# Answer
It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this:

```
Run M on input x;
print "Finished running input";

```

If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run forever, then we need to keep the print statement. Thus, if we have a dead-code remover, it also lets us solve the Halting Problem, so we know there can be no such dead-code remover.

The way we get around this is by "conservative approximation." So, in my Turing Machine example above, we can assume that running M on x might finish, so we play it safe and don't remove the print statement. In your example, we know that no matter which functions do or don't halt, that there's no way we will reach that print statement.

Usually, this is done by constructing a "control-flow graph". We make simplifying assumptions, such as "the end of a while loop is connected to the beginning and the statement after", even if it runs forever or runs only once and doesn't visit both. Similarly, we assume that an if-statement can reach all of its branches, even if in reality some are never used. These kinds of simplifications allow us to remove "obviously dead code" like the example you give, while remaining decidable.

To clarify a few confusions from the comments:

1. > Nitpick: for fixed M, this is always decidable. M has to be the input

As Raphael says, in my example, we consider the Turing Machine as an input. The idea is that, if we had a perfect DCE algorithm, we would be able to construct the code snippet I give *for any Turing Machine*, and having a DCE would solve the halting problem.
2. > not convinced. return as a blunt statement in a no-branch straight forward execution is not hard to decide. (and my compiler tells me it is capable of figuring this out)

For the issue njzk2 raises: you are absolutely right, in this case you can determine that there is no way a statement after the return can be reached. This is because it's simple enough that we can describe its unreachability using control-flow graph constraints (i.e. there are no outgoing edges out of a return statement). But there is no perfect dead code eliminator, which eliminates all unused code.
3. > I don't take input-dependent proof for a proof. If there exists such kind of user input that can allow the code to be finite, it's correct for the compiler to assume that following branch is not dead. I can't see what are all these upvotes for, it's both obvious (eg. endless stdin) and wrong.

For TomášZato: it's not really an input dependent proof. Rather, interpret it as a "forall". It works as follows: assume we have a perfect DCE algorithm. If you give me an arbitrary Turing Machine M and input x, I can use my DCE algorithm to determine whether M halts, by constructing the code snippet above and seeing if the print-statement is removed. This technique, of leaving a parameter arbitrary to prove a forall-statement, is common in math and logic.

I don't fully understand TomášZato's point about code being finite. Surely the code is finite, but a perfect DCE algorithm must apply to all code, which is an infinte set. Likewise, while the code-itself is finite, the potential sets of input are infinte, as is the potential running-time of the code.

As for considering the final branch not-dead: it is safe in terms of the "conservative approximation" I talk about, but it's not enough to detect all instances of dead code as the OP asks for.

Consider code like this:

```
while (true)
  print "Hello"
print "goodbye"

```

Clearly we can remove `print "goodbye"` without changing the behavior of the program. Thus, it is dead code. But if there's a different function call instead of `(true)` in the `while` condition, then we don't know if we can remove it or not, leading to the undecidability.

Note that I am not coming up with this on my own. It is a well known result in the theory of compilers. It's discussed in The Tiger Book. (You might be able to see where they talk about in in Google books.
> 57 votes

# Answer
This is a twist on jmite's answer that circumvents the potential confusion about non-termination. I'll give a program that always halts itself, may have dead code but we can not (always) algorithmically decide if it has.

Consider the following class of inputs for the dead-code identifier:

```
simulateMx(n) {
  simulate TM M on input x for n steps
  if M did halt
    return 0
  else
    return 1
}

```

Since `M` and `x` are fixed, `simulateMs` has dead code with `return 0` if and only if `M` does not halt on `x`.

This immediately gives us a reduction from the halting problem to dead-code checking: given TM $M$ as halting-problem instance, create above program with `x` the code of $M$ -- it has dead code if and only if $M$ does not halt on its own code.

Hence, dead-code checking is not computable.

In case you are unfamiliar with reduction as a proof technique in this context, I recommend our reference material.
> 14 votes

# Answer
A simple way to demonstrate this kind of property without getting bogged into details is to use the following lemma:

**Lemma:** For any compiler C for a Turing-complete language, there exists a function `undecidable_but_true()` which takes no arguments and returns the boolean true, such that C cannot predict whether `undecidable_but_true()` returns true or false.

Note that the function depends on the compiler. Given a function `undecidable_but_true1()`, a compiler can always be augmented with the knowledge of whether this function returns true or false; but there is always some other function `undecidable_but_true2()` that won't be covered.

**Proof:** by Rice's theorem, the property “this function returns true” is undecidable. Therefore any static analysis algorithm is unable to decide this property for all possible functions.

**Corollary:** Given a compiler C, the following program contains dead code which cannot be detected:

```
if (!undecidable_but_true()) {
    do_stuff();
}

```

---

A note about Java: the Java language mandates that compilers reject certain programs that contain unreachable code, while sensibly mandating that code is provided at all reachable points (e.g. control flow in a non-void function must end with a `return` statement). The language specifies exactly how the unreachable code analysis is performed; if it didn't then it would be impossible to write portable programs. Given a program of the form

```
some_method () {
    <code whose continuation is unreachable>
    // is throw InternalError() needed here?
}

```

it is necessary to specify in which cases the unreachable code must be followed by some other code and in which cases it must not be followed by any code. An example of a Java program that contains code that is unreachable, but not in a way that Java compilers are allowed to notice, comes up in Java 101:

```
String day_of_week(int n) {
    switch (n % 7) {
    case 0: return "Sunday";
    case 1: case -6: return "Monday";
    …
    case 6: case -1: return "Saturday";
    }
    // return or throw is required here, even though this point is unreachable
}

```
> 5 votes

# Answer
jmite's answer applies to whether the program will ever exit a calculation--just because it's infinite I wouldn't call the code after it dead.

However, there's another approach: A problem for which there is an answer but it's unknown:

```
public void Demo()
{
  if (Chess.Evaluate(new Chessboard(), int.MaxValue) != 0)
    MessageBox.Show("Chess is unfair!");
  else
    MessageBox.Show("Chess is fair!");
}

public class chess
{
  public Int64 Evaluate(Chessboard Board, int SearchDepth)
  {
  ...
  }
}

```

This routine without a doubt **does** contain dead code--the function will return an answer that executes one path but not the other. Good luck finding it, though! My memory is no theoretical computer can solve this within the lifespan of the universe.

In more detail:

The `Evaluate()` function computes which side wins a chess games if both sides play perfectly (with maximum search depth).

Chess evaluators normally look ahead at every possible move some specified depth and then attempt to score the board at that point (sometimes expanding certain branches farther as looking halfway through an exchange or the like can produce a very skewed perception.) Since the actual maximum depth is 17695 half-moves the search is exhaustive, it will traverse every possible chess game. Since all the games end there's no issue of trying to decide how good a position each board is (and thus no reason to look at the board evaluation logic--it will never be called), the result is either a win, a loss or a draw. If the result is a draw the game is fair, if the result is not a draw it's an unfair game. To expand it a bit we get:

```
public Int64 Evaluate(Chessboard Board, int SearchDepth)
{
  foreach (ChessMove Move in Board.GetPossibleMoves())
    {
      Chessboard NewBoard = Board.MakeMove(Move);
      if (NewBoard.Checkmate()) return int.MaxValue;
      if (NewBoard.Draw()) return 0;
      if (SearchDepth == 0) return NewBoard.Score();
      return -Evaluate(NewBoard, SearchDepth - 1);
    }
}

```

Note, also, that it will be virtually impossible for the compiler to realize that Chessboard.Score() is dead code. A knowledge of the rules of chess allows us humans to figure this out but to figure this out you have to know that MakeMove can never increase the piece count and that Chessboard.Draw() will return true if the piece count remains static for too long.

Note that the search depth is in half-moves, not whole moves. This is normal for this sort of AI routine as it's an O(x^n) routine--adding one more search ply has a major effect on how long it takes to run.
> 3 votes

# Answer
I think in a computing course, the notion of dead code is interesting in the context of understanding the difference between compile time and run time!

A compiler can determine when you've got code that can in no compile-time scenario ever be traversed, but it cannot do so for runtime. a simple while-loop with user input for the loop-break test shows that.

If a compiler could actually determine runtime dead code (i.e. discern Turing complete) then there's an argument that the code never needs be run, because the job's already done!

If nothing else, the existence of code that passes compile-time dead code checks illustrates the need for pragmatic bounds-checking on inputs and general coding hygiene (in the real world of real projects.)
> -3 votes

---
Tags: computability, proof-techniques, compilers
---


# Question
Title: How to solve $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$?
How do I solve the recurrence relation $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$, for constant $k$?

I am told that the answer does not depend on $k$.

# Answer
Suppose that the base case ensures that $T(n) \geq 0$. Clearly $T(n) \geq n$. On the other hand, guessing that $T(n) \leq Cn$, an inductive proof would work as long as $$ n + C(n/2 + n/4 + \cdots + n/2^k) \leq Cn. $$ Now the left-hand side is at most $n(1 + C(1-1/2^k))$, so we would need $C$ to satisfy $$ 1 + (1-1/2^k)C \leq C. $$ In other words, $1 \leq C/2^k$, and so we can choose $C \geq 2^k$. Concluding, we have shown that $T(n) = \Theta(n)$. While this is true for every *finite* $k$, the hidden constant depends on $k$ and on the initial conditions.

---

The case in which $k$ is unbounded – let's say goes all the way to $\lfloor \log\_2 n \rfloor$ – is more interesting. In this case we guess a solution of the form $T(n) \approx nf(n)$. The function $f(n)$ has to satisfy the recurrence $$ f(n) = 1 + \frac{f(n/2)}{2} + \frac{f(n/4)}{4} + \cdots. $$ A reasonable guess is $f(n) = \log\_b n$, under which the right-hand side reads $$ 1 + \frac{\log\_b n - \log\_b 2}{2} + \frac{\log\_b n - 2\log\_b 2}{4} + \cdots = \log\_b n - \kappa + o(1), $$ where the constant $\kappa$ equals $$ \kappa = 1 - \sum\_{m \geq 1} \frac{m}{2^m} \log\_b 2 = 1 - 2\log\_b 2. $$ Choosing $b=4$, we see that $T(n) \approx n \log\_4 n$, and certainly $T(n) = \Theta(n\log n)$.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Decidability of checking an antiderivative?
Let's suppose I have two functions $F$ and $G$ and I'm interested in determining whether

$$F(x) = \int G(x)dx.$$

Let's suppose that my functions are composed of elementary functions (polynomials, exponentials, logs, and trigonometric functions), but not, say, Taylor series.

Is this problem decidable? If not, it is it semidecidable?

(I'm asking because I'm teaching a class on computability and a student asked me if a TM could help you integrate a function whose integral was not currently known. I suspect that the functions we don't know how to integrate are more properly functions whose integral can't be expressed as a combination of the above elementary functions rather than functions for which we don't actually know the integral, but that got me thinking about whether the general problem of checking integrals was decidable.)

# Answer
The short answer to your question is "no". Richardson's theorem and its later extensions basically state that as soon as you include the elementary trigonometric functions, the problem of deciding if $f(x) = 0$ (and hence if $f(x) = g(x)$, since this is the same as $f(x) - g(x) = 0$) is unsolvable.

What's interesting about this is that the first-order theory of real closed fields is decidable. Intuitively, the reason why adding trigonometric functions makes the first-order system undecidable is because you can construct the integers via $\\{ x \in R : \sin(\pi x) = 0 \\}$, and the theory of the integers is undecidable.

Whether or not the theory of real closed fields with $e^x$ is decidable is a fairly famous open problem.

Even more interesting that this is that if you had an oracle which "solved" the constant problem (i.e. an oracle which can tell you if $f(x) = 0$ or not), then integration of elementary functions in finite terms is decidable, and a practical algorithm is known. So given $G(x)$, we could find $F(x)$ or know that there is no elementary integral of $G$ in finite terms.
> 9 votes

# Answer
Your problem seems to reduce the following simpler question:

Given two functions $F,G$ in class of functions, do we have $F(x)=G(x)$ for all $x$? (In other words, do they have the same value everywhere?)

I don't know whether this is decidable, for this class of functions. If it is, then your problem should be decidable as well.

---

For your problem, a general approach is: symbolically differentiate $F(x)$ to get $F'(x)$, then check whether we have $F'(x)=G(x)$ for all $x$.

So the key step is the symbolic differentiation. Let's work out how to do that in more detail. We can define the class of allowable functions recursively:

$$\newcommand{\or}{\\;\vert\\;} F(x) ::= c \or x \or e^x \or \log(x) \or \sin(x) \or \cos(x) \or \tan(x) \or F\_1(x) + F\_2(x) \or F\_1(x) \times F\_2(x) \or F\_1(x)/F\_2(x) \or F\_1(F\_2(x))$$

where $c$ ranges over constants and $F,F\_1,F\_2$ range over functions.

It is then possible to devise a recursive algorithm for symbolically differentiating this class of functions, using the standard rules of calculus (e.g., the chain rule, etc.). In particular, we can handle every case above, and show recursively that the derivative can be expressed symbolically as a function within this class. For instance:

* If $F(x)=c$, $F'(x)=0$.
* If $F(x)=x$, $F'(x)=1$.
* If $F(x)=e^x$, $F'(x)=e^x$.
* If $F(x)=\log(x)$, $F'(x)=1/x$.
* If $F(x)=\sin(x)$, $F'(x)=\cos(x)$.
* If $F(x)=\tan(x)$, $F'(x)=1 + (\tan(x))^2$.
* If $F(x)=F\_1(x)+F\_2(x)$, $F'(x)=F'\_1(x)+F'\_2(x)$.
* If $F(x)=F\_1(x) \times F\_2(x)$, $F'(x)=F'\_1(x) F\_2(x) +F\_1(x) F'\_2(x)$.
* If $F(x) = F\_1(F\_2(x))$, $F'(x) = F'\_1(F\_2(x)) F'\_2(x)$ (chain rule).

And so on. In each case, if $F(x)$ is in the class of allowable functions, then so is $F'(x)$, and you can recursively work out a symbolic expression for $F'(x)$ -- this is known as symbolic differentiation.

Finally, all that remains is to check whether $F'(x)=G(x)$ for all $x$. That's the problem I mention at the top of my answer.

---

There's a simple method for checking whether two functions are identically equal that I'd expect to work pretty well in practice. The algorithm is this: repeatedly pick a random value of $x$, and check whether $F(x)=G(x)$ holds for that value of $x$. If it holds with equality for many randomly chosen $x$, then output "they are identically equal". If you find any $x$ for which $F(x)\ne G(x)$, then output "they are different".

There is no guarantee that this will work, but for many classes of functions, the output of this procedure will be correct with high probability. In particular, suppose we have some distribution on $x$ represented by the random variable $X$ and some $\epsilon\>0$ such that $\Pr\[F(X)=0\] \ge \epsilon$ holds for all $F$ in the class. Suppose moreover that the class of allowable functions is closed under subtraction (as your class is). Then it follows that $r$ rounds of the above procedure gives the wrong answer with probability at most $(1-\epsilon)^r$.

Also, if there is a randomized procedure for polynomial equality testing, then the problem is decidable.

It remains to ask whether such a result holds for your particular class of functions. The statement above probably won't hold. However, if we lucky, perhaps we might be able to prove something like the following:

For all $s \in \mathbb{N}$, maybe we can find a distribution on real numbers, i.e., a random variable $X\_s$, and a constant $\epsilon\_s \> 0$, such that such that $\Pr\[F(X)=0\]$ holds for all functions $F$ that are in your class and have "size" at most $s$.

If this is true, then it will follow that there is a randomized algorithm for polynomial equality testing and thus your problem is decidable.
> 7 votes

---
Tags: computability, undecidability, mathematical-analysis, computer-algebra
---


title: Constant Shaving on known algorithms

text:
# Question
Title: Constant Shaving on known algorithms
Some problems such as sorting have famous complexity lower bounds (ex: $O(n \log (n))$ in this case) but I feel that doesn't totally remove the possibility of improving algorithms by shaving constants. Are there any really non trival, perhaps not practical sorts, that have excellent constant performance? For example do there exist algorithms that say achieve $\frac{1}{2} n \log(n)$ number of comparisons as opposed to say mergesorts $1.44 n \log(n)$, and can this leading constant, be reduced arbitrarily low?

It oculd be the case these algorithms have running time

$$ 0.0001 n \log(n) + 9^{\text{Graham's Numbers}}n + \pi^{\pi^\pi} $$

But I am still curious if non trivial reduction of constants exists, or if someone has proven tight bounds on what the constants must be.

# Answer
> 4 votes
Let's suppose that you want to do comparison-based sorting of $n$ distinct elements.

You can interpret the problem in terms of information theory. You want to discover which permutation the sequence is currently in. That is, you need to discover a number between $1$ and $n!$.

The comparison operator gives you one bit of information. But to discover a number between $1$ and $n!$, you need at least $\log\_2 n!$ bits of information. Therefore, you need at least $\log\_2 n!$ comparisons.

By Stirling's approximation:

$$\log\_2 n! = n \log\_2 n - \frac{n}{\ln 2} + O(\log n)$$

This is the number of comparisons you *need*. You cannot do better than this. For any comparison-based sort which takes $k n \log\_2 n + o(n \log n)$ comparisons, $k \ge 1$. In particular, there is no comparison-based sort which uses $\frac{1}{2} n \log\_2 n$ comparisons.

So no, you can't reduce constants arbitrarily.

We usually don't do this kind of analysis for time complexity, because in practice, "time" depends on many factors like the compiler settings, the CPU architecture, the laws of physics, and so on. However, it becomes very important when analysing space complexity; we do measure time in physical units ("this program will take three hours to run"), but we don't typically measure space the same way ("I need a cubic metre of disk").

---
Tags: algorithms, sorting, efficiency
---


# Question
Title: Are compilers able to detect alternating accesses to arrays and interleave them in memory?
Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this:

```
// int[] a,b
int sum = 0;
for(int i = 0; i < n; i++)
{
  sum += a[i] + b[i];
}

```

With the usual sequential array storage, `a[i]` and `b[i]` may be far away from each other in memory. Therefore, I think a good compiler optimization would detect that `a[i]` and `b[i]` are always accesses at the "same" time, and store the arrays interleaved, that is `a[0] b[0] a[1] b[1] ...` so that one memory access may retrieve both `a[i]` and `b[i]`.

# Answer
> 11 votes
Some work has been done that matches your description. For instance:

* Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V. Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings.

describes a such an optimization.

# Answer
> 1 votes
The short answer in this case is that Memory Level Parallelism is usually sufficient to cover multiple separate memory blocks in a loop like this; interleaving into a single stream would actually slow the process down. Many caching and external memory algorithms assume some degree of parallelism like this.

The longer, more theoretical answer is that caching is like a number of aspects of program execution that seem easy but prove to be hard to predict in general. For instance, a cache block might only need to be fetched if a given process halts; a compiler that could predict that would be interesting to say the least.

The simpler case of optimizing a known sequence of accesses (without the need to predict them) is itself NP-hard:

> In particular, suppose one is given a sequence of memory accesses and one has to place the data in the memory so as to minimize the number of cache misses for this sequence. We show that if P ≠ NP, then one cannot efficiently approximate the optimal solution even up to a very liberal approximation ratio.

Petrank and Rawitz, *The hardness of cache conscious data placement*

# Answer
> -1 votes
Your example is not complete, the arrays are not declared anywhere, nor are they initialised anywhere.

I suspect in a general programming context this sort of optimisation would be "more trouble than it's worth". Most arrays are accessed from more than one place so a compiler would often have to guess which place was the most important. Also many arrays would not be able to be modified in this way because they pass over compilation unit boundries either as parameters to functions or as global variables. Finally it would make debug information more complex.

---
Tags: compilers, arrays, program-optimization, memory-management
---