# Question
Title: Can an alphabet be extended in a reduction proof? (with sample problem)
So I am working on solving a problem on whether following language is decideable:

> $L = \\{n \in \mathbb{N} \mid M\_n$ never freezes (for any input)$\\}$, where $n$ is the Gödel-number of a Turing machine.

The model for Turing machines that we use operates on a one-side-unbounded tape, so "freezing" in this context means going "out-of-bounds" on the other side of the tape. We also define a Turing machine as the tuple $(K,\Sigma,\delta,s)$, where $K$ is the set of states, $\delta$ is the transition function and $s$ is the starting state ($\notin K$).

Now I have an idea on how to prove it is not decideable by reduction, but it requires me to construct a new DTM which operates on a new alphabet $\Sigma' := \Sigma \cup \\{§\\}$, and assume that $§ \notin \Sigma$. (where $\Sigma$ is the alphabet of the machine $M\_n$)

My idea is as follows: We prove that $L^c=\\{n\in\mathbb{N}\mid M\_n $freezes for at least one input$\\}$ is undecideable. For that, we construct a DTM $Extend$ which takes $n$ as input. $Extend$ modifies the $n$ so that we get a new machine that operates exactly as $M\_n$ would, except with the following tweaks:

1. For any (state,letter) pair with the $\delta$ function value $\delta(q,\sigma)=(h,\sigma')$ (where h is the halting state), we replace the function value with $(q\_{|K|+1},\sigma')$ (so now the machine never halts on its own)
2. Introduce a new state $q\_{|K|+1}$, where $\delta(q\_{|K|+1},\sigma)=(q\_{|K|+1},\sigma)$ (so if this state is reached the TM goes into an infinite loop).
3. We introduce a new letter to the alphabet, let's say '$§$', and set it so that $\delta(q,§)=(h,\\#)$ (where # is the blank symbol) (so it only halts if any point it reads '$§$') All of these are turing-computable steps (if we look at $\delta$ as a table of values for every (state,letter) pair (finite), it's the same as going through the table once, changing values as necessary, adding a row and adding a column).

Now we create a new DTM $M\_j$ which works as follows (on input $n$): $\>Extend \to L\_{\\#} \to S\_R \to L \to § \to R \to R\_{\\#}$, where $L\_{\\#}, R\_{\\#}$ is a TM which goes left or right respectively until it encounters a blank, and $S\_R$ is a TM which shifts the word to the right of it by a blank (so $s,\underline{\\#}w\\# \vdash^\*\_{S\_R}h,\\#\underline{\\#}w\\#$). So $M\_j(w)$ works as follows: $s,\\#n\underline{\\#} \vdash^\*\_{M\_j} h,§\\#n\_{Extend}\underline{\\#}$

We know that the set $\mathcal{E}=\\{ n\in\mathbb{N} \mid M\_n$ accepts $\emptyset \\}$ is in $\text{co-RE}$. This means $\mathcal{E}^c = \\{ j\in \mathbb{N} \mid M\_j$ accepts at least one input $\\}$ is recursively enumerable, but not decideable. Since our new DTM $M\_j$ only accepts iff $n$ would freeze for at least one input, this means that $n\in L^c \Leftrightarrow j\in \mathcal{E}^c$ and the reduction proof would be complete.

But again, I am not sure if the transformation of $n$ I made (by introducing the letter '$§$' to $\Sigma$) is allowed. Can someone clarify this for me?

# Answer
> 1 votes
A (computable) reduction from problem P to problem Q is a (computable) function that takes an instance of P to an instance of Q. In your case $P=\mathcal{E}^c$ and $Q = L^c$. So your reduction is "legal" (that is, conforms to the definition of reduction) if it takes an instance of $\mathcal{E}^c$ to an instance of $L^c$. That's all a function has to do in order to be a reduction.

(In principle there is no such thing as an *instance of a problem* – every string over the appropriate alphabet is an instance. But let's ignore this small issue.)

---
Tags: computability, turing-machines, reductions, undecidability, proof-techniques
---


# Question
Title: Trouble Understanding a Remark about Beta-Reduction in the Lambda Calculus
From page 15 of *Lambda Calculus and Combinators an Introduction*:

> **Note 1.34** If $M \equiv aM\_1 \ldots M\_n$ where $a$ is an atom, and $M \triangleright\_\beta N$, then $N$ must have form
>
> $$ N \equiv a N\_1 \ldots N\_n $$
>
> where $M\_i \triangleright\_\beta N\_i$ for $i = 1, \ldots, n$. To see this, note that $M$ is really
>
> $$ (( \ldots ((aM\_1)M\_2) \ldots)M\_n) $$
>
> when its parentheses are fully shown; hence each $\beta$-redex in $M$ must be in $M\_i$. Also the same holds for each subterm $\lambda x. P$ whose bound variable might be changed in the reduction of$M$.

**Question:** Why is the following not a counter-example?

First let $M\_1 = m\_1 m\_2 m\_3$ for atomic constants $m\_1$, $m\_2$, $m\_3$. Then let $N\_1 = m\_1$ and $N\_2 = m\_2 m\_3$. Then:

$$ aM\_1 \equiv a (m\_1 m\_2 m\_3) \equiv (((am\_1)m\_2)m\_3) \equiv ((a m\_1)m\_2 m\_3) \triangleright\_\beta a N\_1 N\_2 $$

Here, if I am correct, then we have a case where

$$ a M\_1 \triangleright\_\beta a N\_1 N\_2 $$

which seems to contradict the note.

# Answer
> 3 votes
Application in the lambda calculus is not associative. $m\_1 m\_2 m\_3$ means $(m\_1 m\_2) m\_3$ and is **not** equal to $m\_1 (m\_2 m\_3)$. So the second equality you state doesn't hold. $$a(m\_1 m\_2 m\_3) \neq ((a m\_1) m\_2) m\_3$$ Further $$a N\_1 N\_2 = (a m\_1)(m\_2 m\_3) \neq (a m\_1) m\_2 m\_3 = ((a m\_1) m\_2) m\_3$$

---
Tags: lambda-calculus
---


# Question
Title: Is O(|A| + |B|) the size of the union of two synchronized DFAs A and B?
In general, the size of the DFA resulting from the union of two DFAs A and B is O(|A|.|B|) in the worst case (usually the product construction is used to compute the union).

Let's consider the class of 'synchronized DFAs' as the class of DFAs having a synchronizing word : https://en.wikipedia.org/wiki/Synchronizing\_word

After looking at some examples of synchronized DFAs A and B, it seems possible to always build a synchronized DFA for the UNION of A and B with a size O(|A| + |B|) in the worst case.

Does anybody have any information, proof or paper about the union of two synchronized DFAs in O(|A| + |B|) ?

Many thanks, Luz

# Answer
> 5 votes
Your conjecture is wrong. Consider the following languages:

* $L\_1$ is the language of words over $\\{a,b,c\\}$ such that the number of $b$s after the last $a$ is a multiple of $x$.
* $L\_2$ is the language of words over $\\{a,b,c\\}$ such that the number of $c$s after the last $a$ is a multiple of $y$.

The minimal DFA of $L\_1$ contains $x$ states, and that of $L\_2$ contains $y$ states. Both DFAs have $a$ as a synchronizing word. The minimal DFA for $L\_1\cup L\_2$ contains $xy$ states (and also has $a$ as a synchronizing word).

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


# Question
Title: Does quicksort for increasing order work faster if the input set is more decreasing sorted?
In CLRS's Introduction to Algorithms,

> The following procedure implements quicksort:
>
> ```
> QUICKSORT(A; p; r)
> 1 if p < r
> 2 q D PARTITION(A; p; r)
> 3 QUICKSORT(A; p; q-1)
> 4 QUICKSORT(A; q+1; r)
>
> ```
>
> To sort an entire array A, the initial call is QUICKSORT(A; 1; A.length). The key to the algorithm is the PARTITION procedure, which rearranges the subarray A\[p..r\] in place.
>
> ```
> PARTITION(A; p; r)
> 1 x = A[r]
> 2 i = p - 1
> 3 for j = p to r - 1
> 4     if A[j] <=   x
> 5         i = i + 1
> 6         exchange A[i] with A[j]
> 7 exchange A[i+1]  with A[r]
> 8 return i +1
>
> ```

The quicksort algorithm sorts a set in **increasing** order, where the pivot is chosen to be the last element in the current array.

I am trying to figure out the worse case and best case to the algorithm.

But I am more interested in whether quicksort will be faster, if the input set is originally more close to the final sorted result. In the concern, I guess the choice of pivot may not matters.

After some thought, the following questions make me think that quicksort will be slower if the input set is more close to the final sorted result.

Is it correct that

* when the input set is already in **decreasing** order, the assignments and exchanges in the for loop in PARTITION will be skipped?
* Does quicksort work faster when the input set is already more sorted in **decreasing** order?

Thanks.

# Answer
First, this is not the Quicksort that we all know and love, but some rather strange version of it, so your results cannot be applied to what is usually called Quicksort.

If the array is already in descending order, your version (unlike the original Quicksort) will not do any exchanges in the first partitioning. So the partitioning will be fast. However, it makes practically no progress; only one element is moved to its right position, and you will have about $n^2 / 2$ comparisons in total, which is about the worst case possible.

An array in ascending order is even worse, since you will do $n^2/2$ comparisons, plus $n^2/2 exchange operations.
> 1 votes

# Answer
This may not answer your question, but it is a bit more information than belongs in a comment.

In theory, you seem to have answered your own question. :)

In practice, well what have you tried?

The fact of the matter is that it's difficult to determine, really ***it depends***.

I would suggest that CPUs are complicated and predicting where speedups will occur is often counter intuitive. It often depends on the trade-offs between memory usage and computational load. Even more adversely, we have little control over what code our compilers will emit or what they are optimizing for and finally we have zero control over how the CPU will decide to optimize what it is trying to do. The best we can do is understand as much of the process as we can research and learn about and from there make educated guesses about how to proceed.

This article gives a good in-depth analysis, for example, of one of the cornerstones of algorithmic search. Admittedly not what you're looking for, but it was close at hand and it will give you a better sense of the arena in which you struggle. For the reasons in that article, many advanced implementations take a high-level and multi-tiered approach to problem solving, relaxing rules when they matter least, relying on special CPU instructions when they are available and otherwise attempting to cover as much territory as possible to give the best results all-around for a given problem. Often times that can get murky and far from trivial.

Many programmers prefer to stick with approaches that are easier to understand and code. I remember seeing an algorithm ( forgive a lack of an example here ) I believe one of Chazelle's which has been above the radar for a decade, yet no implementation exists - not even one by him.

I hope this helps to clarify part of the problem for you. And much luck in your quest!
> 0 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: How can I write this simple function in mathematical notation?
```
POINTS_TABLE = [3, 5, 7, 1]

function score(answer) {
  result = 0
  for i in 0..4
    result += POINTS_TABLE[answer[i]]
  return result
}

answer = [1, 2, 1, 0]

s = score(answer)

```

The sum performed is 5 + 7 + 5 + 3 = 20. It uses the values from the input as the indexes to read from the POINTS\_TABLE.

This is the style of the answer I'm trying to work out: \begin{equation} score(answer) = \sum\_{i=1}POINTS\\\_TABLE\_{answer\_i} \end{equation}

# Answer
While you are free to use whatever notation you want, as long as you explain it, it seems that the simplest solution here would be

> $$ score(answer) = \sum\_{i=0}^3 POINTS\\\_TABLE\[answer\[i\]\] $$

This should be self-explanatory in most circumstances.
> 2 votes

---
Tags: notation, mathematical-foundations
---


# Question
Title: Context free grammer for $L = \{a^i b^j a^n b^m \mid i + j = n + m\}$
Find a CFG for the following language:

$$L = \\{a^i b^j a^n b^m \mid i + j = n + m\\}$$

I'm not sure how I can do that context free. I know that I have to borrow one char from the left group for each char from the right group. but not sure how.

# Answer
The idea is to use non-terminals $X\_{\alpha\beta}$, where $\alpha,\beta \in \\{a,b\\}$, that support the production $X\_{\alpha\beta} \to \alpha X\_{\alpha\beta} \beta$. You have to combine them somehow so that you obtain the language $L$, but I'll leave the details to you.
> 2 votes

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


# Question
Title: Recursive type encoding on System F (and other pure type systems)
I am studying pure type systems, particularly the calculus of constructions, and trying to use an encoding for recursive types on it, which, according to Philip Wadler, is possible. As an example, I'm using the Morte Haskell library to encode Scott numerals as given by Cardelli.

A summary of the encoding is as such: given a (positive) recursive type...

$$\mu X.F\ X$$

...we may encode it as a type on System F as...

$$Lfix\ X.F\ X\ =\ \Lambda X.(F\ X\rightarrow X)\rightarrow X$$

...or, using pure type systems' notation (with an explicit $F$)...

$$Lfix\ =\ \Pi F: \*\rightarrow\*.\Pi X: \*.(F\ X\rightarrow X)\rightarrow X$$

...since $F$ is a type constructor ($\*$ is the type of types).

In order to encode such, we need to declare three functions, $fold$, $in$ and $out$, according to Wadler, and used by Cardelli on the encoding for Scott numerals.

> fold : All X. (F X -\> X) -\> T -\> X
>
> fold = \X. \k: F X -\> X. \t:T. t X k
>
> in : F T -\> T
>
> in = \s: F T. \X. \k: F X -\> X. k (F (fold X k) s).

(Where $T$ is $Lfix\ X. F\ X$.)

It's trivial to write the $fold$ function as given. But when trying to write the $in$ function, it doesn't seem to typecheck. The expression $(fold\ X\ k)$ has type $T\rightarrow X$, and $(F\ (fold\ X\ k)\ s)$ should be of type $F\ X$. Then we infer that $F$ should be of type $(T\rightarrow X)\rightarrow F\ T\rightarrow F\ X$ (looks like a `fmap`). This doesn't typecheck, because `F` is a type constructor (of type $\*\rightarrow\*$).

This doesn't look like a typo... am I missing something?

# Answer
> 8 votes
There is a convention in category theory that the same symbol is used for a type constructor and the map function over that type constructor. Hence, if f : X -\> Y then F f : F X -\> F Y.

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


# Question
Title: What is the advantage of leaf trees vs. node trees?
In the book "Advanced Data Structures", Chapter 2 ("Search Trees"), the author, Peter Braß, mentions two versions of binary trees (**emphases** in the quoted text are mine):

> "...two different models of search trees, either of which can be combined with much of the following material, **but one of which is strongly preferable**.
>
> If we compare in each node the query key with the key contained in the node and follow the left branch if the query key is smaller and the right branch if the query key is larger, then what happens if they are equal? The two models of search trees are as follows:
>
> 1. Take left branch if query key is smaller than node key; otherwise take the right branch, until you reach a leaf of the tree. The keys in the interior node of the tree are only for comparison; all the objects are in the leaves.
> 2. Take left branch if query key is smaller than node key; take the right branch if the query key is larger than the node key; and take the object contained in the node if they are equal."

The author calls these Model 1 and Model 2 respectively. A figure from the book gives an example of each:

The author talks some more about the difference between these types of trees, including

1. The maximum number of keys each type can store as a function of height h ($2^h$ vs. $2^{h+1}-1$ respectively in model 1 and 2 respectively)
2. The number of comparisons on the key while traversing an interior node (1 vs 2 respectively)
3. Each key appearing up to two times in a tree (once in an interior node and once as a leaf node) in model 1 vs the key appearing exactly once in model 2.

He then says:

> Model 2 became the preferred textbook version because in most textbooks the distinction between object and its key is not made: the key is the object. Then it becomes unnatural to duplicate the key in the tree structure. **But in all real applications, the distinction between key and object is quite important. One almost never wishes to keep track of just a set of numbers; the numbers are normally associated with some further information, which is often much larger than the key itself.**
>
> In some literature, where this distinction is made, trees of model 1 are called leaf trees and trees of model 2 are called node trees (Nievergelt and Wong 1973). **Our preferred model of search tree is model 1**, and we will use it for all structures but the splay tree (which necessarily follows model 2).

(Please make note of the emphasised bits.)

My understanding of what the author is talking about is that in practice the key itself is not the ultimate object of search, and in fact one wants to associate a (possibly large or variable sized) record with each key, so the question is how one can efficiently associate this record with the key. His solution is the Model 1 tree. Looking at his implementation of the structure that defines a Model 1 node (technically this is C code - the posting of which I suspect doesn't bode well for questions posted on this site - but hopefully my question is language-agnostic and applies to the "pointer-machine model" in general):

```
typedef struct tr_n_t {key_t      key;
                   struct tr_n_t   *left;
                   struct tr_n_t  *right;
               /* possibly additional information */
                         } tree_node_t;

```

Now the way a leaf node is identified is when the `right` pointer is `NULL` (more language-agnostically, a pointer that does not point to any valid memory object), and the left pointer then points to the stored record. (Again at the risk of talking about implementation-specific stuff, one would be expected to do some kind of type casting at this point to retrieve the actual object.)

My question is: ***can we not get the same effect from a Model 2 tree simply by including a pointer to the associated record as an additional piece of information (i.e. in addition to the key, and left and right pointers) in each node?***

What am I missing?

\[The author does mention an implementation-related advantage of Model 1 that I can accept: that the structure of a model 1 tree is more regular than a model 2 tree, because in the former an interior node always has both left and right subtrees, whereas in the latter an interior node might be missing a left or right subtree. But I do not get the other advantage he claims.\]

# Answer
You don't quote the reasoning of P. Braß, if he gives any, so we can only guess.

I would like to distinguish two cases.

1. Data are stored as values, i.e. in place.
2. Data are stored by reference.

In the first case, the size of the "inner" tree would blow up arbitrarily. For every step in the search, we would have to load a potentially big node into the cache. That would increase the real cost of the search considerably (and arbitrarily, depending on the data type)! In such a scenario, using type 1 is indeed preferable as the search data structure itself contains only the information needed for performing the search.

In the second case -- which is the default in reference-based languages like e.g. Java -- this effect is present but minor: instead of two pointers, every node stores three. In such a scenario, I would prefer type 2 because it requires less storage in total.

---

*Implementation-related side note:* If you assign data (references) to inner nodes, they probably have some generic type `Node<T: Comparable>` (in modern languages). That means that the compiler may not be able optimize the search code as much as it could if the exact type were statically known. The specifics depend on the language, type system and compiler, though.
> 3 votes

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


# Question
Title: What does it mean to "strengthen the precondition and weaken the postcondition" in Hoare logic?
Having learned a rough summary of Hoare logic (i.e. learning just the basic concept of Hoare triples and a few of the rules) I kept seeing a statement along these lines:

> The rule of consquence allows us to strengthen the precondition and weaken the postcondition. (paraphrased)

1. What does it actually mean to *strengthen the precondition* and to *weaken the postcondition*?
2. Is *and* used in its strict logical meaning in this sense, i.e. if we apply the rule of consequence we will always do *both*? Or can it be read as allowing us to choose to strengthen the precondition or weaken the postcondition?

I get the (very basic) idea of the rule, but this statement implies the rule can be applied for a strategic reason that isn't clearly explained.

Thanks.

# Answer
> 8 votes
Condition $A$ is *stronger than* condition $B$ if $A$ implies $B$. That is, if $B$ holds in all situations in which $A$ holds. Conversely, if $A$ is stronger than $B$, then $B$ is weaker than $A$. Note that, from the definition, $A$ is stronger and weaker than itself, since $A$ implies $A$. (We might prefer to say "at least as strong as" instead of "stronger than" but I guess that gets convoluted and it's easier to just remember "stronger than" really means "at least as strong as".)

So, to strengthen a condition is to replace it with a stronger one; to weaken a condition is to replace it with a weaker one. Because a condition is always stronger and weaker than itself, the phrase "strengthen the precondition and weaken the postcondition" does indeed mean that we can leave one (or even both!) of them unchanged.

# Answer
> 2 votes
The consequence rule is a necessary${}^\*$ piece of glue we typically apply in a few select situations around loops.

1. We're trying to prove $\\{\psi\\}\mathbf{while}~g~\mathbf{do}~P~\mathbf{od}\\{\phi\\}$ but the standard rule $$\frac{\\{I\land g\\}P\\{I\\}}{\\{I\\}\mathbf{while}~g~\mathbf{do}~P~\mathbf{od}\\{I\land\neg g\\}}$$ where $I$ is our loop invariant doesn't quite fit because the $\psi$ and $\phi$ typically don't mention local variables such as counters used to control the loop. But those are crucial to express $I$. So we use the consequence rule, having to show $\psi\Rightarrow I$ and $I\land\neg g\Rightarrow\phi$ to link up with the outside.
2. When proving the hypothesis of the rule above, we work our way up backwards through the body $P$ of the while loop, from the invariant $I$ which we want to hold again at the end of the body all the way to the beginning of the body, where we arrive at an assertion $K$. But we know already what assertion we want to hold there: $I\land g$. Typically the two assertions are not the same but if we have a good invariant, then we'd at least be in a position to prove the implication $I\land g\Rightarrow K$, which allows us to use the consequence rule once again as glue.
3. Initialisation code such as $x := 0; i := n$ is usually present to remove the dependence on a precondition such as $x=0\land i=n$, yet, Hoare logic without consequence rule only gives us $0=0\land n=n$ as precondition $\psi$ in $\\{\psi\\}x := 0; i := n\\{x=0\land i=n\\}$. Yes, I agree that this isn't exciting but technically we need to bridge the purely syntactic gap between the intended precondition $\mathit{True}$ and the semantically equivalent $0=0\land n=n$. Note that in the previous two cases we had bridge semantic gaps.

${}^\*$ This is a mathematical "necessary" in the sense that Hoare logic without the consequence rule fails to prove many semantically valid Hoare triples the Hoare logic with it manages to prove.

---
Tags: correctness-proof, semantics, hoare-logic
---


# Question
Title: Find grammar for the following language: $\{ a^{m_1}ba^{m_2}b\dots a^{m_k}bca^n \mid m_j = n \text{ for some } 1 \le j \le k \}$
I need to Find grammar for the following language: $\\{ a^{m\_1}ba^{m\_2}b\dots a^{m\_k}bca^n \mid m\_j = n \text{ for some } 1 \le j \le k \\}$.

can someone help me to solve it? I am not sure how to start.

# Answer
First try to understand the form of the strings in the language. If $m\_j=n$ then strings are of the form $\dots a^n b \dots c a^n$. What is on the place of the dots?
> 3 votes

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


# Question
Title: How can i fill shelves with products so that I have the maximum amount of sales?
I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales possibility I know on those shelves. My problem is, according to my instructions the max sales possibility changes according to the shelf height and the product's position on the shelf. More specifically, it says that the product position at the beginning of the shelf have a max sales possibility that is 30% reduced from those at the end, that the max sales possibility appears at the 4rth shelf and the highest and lowest have 30% of the max. I would really appreciate any help you can give me as my background is not on computer science and I'm pretty lost. I've tried searching for information on bin packing problems but I haven't found anything that matches.

# Answer
> 1 votes
You'd need to give an exact specification of the problem, but we can do something. It sounds that every item can in principle be placed anywhere, but has a different value depending on where it is placed. It's not quite clear how "value" and "max sales possibility" interact, that's for you to figure out.

I'd try to find a "profit" per item, which will depend on its shelf location. What's even more important is "profit per meter". Since the profit changes by the same percentage for all items, you want to put all items with "high profit per meter" to positions where their profit isn't removed.

A "greedy" algorithm would start by sorting all items by profit per meter. Then you put the items sorted by profit per meter into the high-value places first. That gives you a decent solution.

You will have unused space left, so you will try to improve things by putting items there that fit better. Say you had a meter high value space and put a 60cm item there and don't have anything to use the leftover 40cm, then maybe placing a 100cm item would be better. That's reasonably similar to bin packing.

You can be pretty sure that the problem is NP-complete, which means in layman's terms that neither you nor anyone else will be able to find an optimal solution in reasonable time, so you try to find a good solution instead.

---
Tags: optimization, greedy-algorithms, knapsack-problems, packing
---


# Question
Title: How to simulate a parallel computer (with certain number of processors) on a serial computer
I am a novice to parallel computing. I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor. I know the basics of GAs and I know how to design a GA algorithm to solve the TSP. I thought that this could be an example of an "embarassingly parallel" problem in the sense that I could assign each processor a fixed number of chromosomes (i. e, potential solutions, with solution meaning a given sequence of cities to be visited as specified by the chromosome) with the task of calculating the objective function for each of the assigned chromosomes. In this case, the objective function for a given chromosome is the inverse of the total distance described by that chromosome. The task of performing crossover and mutation would be carried out by a master processor. If this is a valid or reasonable way of parallelizing the problem, then there's no need for inter-processor communication during the objective function evaluation step and I can hardly see this as a truly parallel problem. Since minimum communication is needed, wouldn't the speed scale with the number of processors? What would we learn from such a simulation that we don't already know? I'll be grateful for any thoughtful answers.

# Answer
> 4 votes
The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard. Genetic algorithms can get a good solution more quickly than NP-hard time, but there's no guarantee that you'll find an actual optimal solution. This can be a good trade-off if you're programming, say, a driving-direction app, but it doesn't get around the NP-hard issue since it doesn't reliably solve the actual NP-hard problem.

Note that genetic algorithms are stochastic (probabilistic). It's entirely possible that you could guess the exact best solution on the first go, or that you'd never guess it after a billion years.

> I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor.

As others have said, this will cause your program to run slower than if you hadn't split it up. Parallel solution techniques are inefficient compared to single-threaded solution techniques; the only reason that we use them is to leverage additional processors. If you don't actually take advantage of additional processors, you pay the cost for it without enjoying the benefit.

That said, almost all modern computers have multiple cores, even cell phones and tablets. In the paragraph above, "processor" refers to a processing unit, which single CPU's have multiple instances of. Your computer probably has at least 2 if it's a laptop or 4 if it's a desktop.

Also, note that processors often claim to have twice as many "logical cores". When doing numerical problems, you mostly just care about physical cores; ignore the additional logical cores. With Intel processors, this means ignore Hyper-Threading. With AMD processors, this often means dividing their claimed count by two, since I think that they share floating-point units (FPU) between cores. Those extra logical cores are useful in common computer tasks where there are thread waits and such, but they're usually harmful in scientific computing.

> Since minimum communication is needed, wouldn't the speed scale with the number of processors?

Ideally, if you get 100% parallelization efficiency, total speed is equal to the speed of each of the individual processors working individually, combined. Lots of things detract from that ideal, including communication time.

As much as possible, you want to split the problem up into large chunks that a processor can focus on, then combine those chunks at the end, or at least infrequently.

Too much communication will actually make a bunch of processors working together slower than a single one working alone. For example, consider

```
return a + b + c + d;  // Single-threaded calculation

```

If you split this up into

```
half1 = worker1.Add(a, b);
half2 = worker2.Add(c, d);
return half1 + half2;

```

, your program will run ***much*** slower than in the first case, despite using multiple cores. The problem is even calling other threads costs far more than simply adding the numbers together, so you've slowed the program down by a huge factor as soon as you do the first worker call.

The trick to remember is that you want to call workers only when you have a lot of work for them to do while the current thread does a lot of work itself. If that doesn't hold, then it's more efficient to just do the work in the current thread.

> What would we learn from such a simulation that we don't already know?

Nothing, really. This is a common homework problem in many college classes on optimization, so it's been done hundreds of thousands of times before. I'm assuming that this is part of one of your homework problem sets.

### Conclusion

If you're in college, you may have access to a good version of Visual Studio through Microsoft Imagine (previously called DreamSpark). If not, you can download Visual Studio 2015 Community (noting that 2017's in RC right now).

If you use C# in Visual Studio, it should be pretty straightforward to create your parallel genetic algorithm optimizer for the traveling salesman problem. Since your PC's probably already multi-core, you can take advantage of the speed up from it. But, even if it's not multi-core, you can still do multi-threaded runs, and the OS will interleave the threads to simulate a multi-core process.

# Answer
> 1 votes
I'll have to make some assumptions here. It seems you have a problem where some amount of work X could be distributed on practically any number of processors, while some other work Y needs to run on one processor only. And you have a single processor and want information about the behavior on n processors.

You don't really have to simulate a system with n processors. And if you could, the thing that you cannot simulate is the time behaviour. But all you really have to do is measure the time that each task takes, figure out dependencies (where one task cannot continue running until another task has finished), and you should be able to figure out all you want.

# Answer
> -2 votes
At the following paper \[1\] they are talking about some cloud simulators, and comparing them with a Raspberry Pi cluster. Basically they are saying that a Raspberry Pi cluster is the cheapest way to have a system with more than 1 CPU. They also saying that cloud simulators are not reflecting to the real network traffic.

So, regarding your question, even if you have a simulator you will not even get close to a cluster machine.

I would suggest you at first, to try threaded parallelism, and if you believe that is worth it, you can buy time at a bigger machine, and work with process parallelism. You can also try process parallelism on multi-core CPUs and then move to a bigger machine.

\[1\] Fung P.T., White D.R., Jouet S., Singer J., Pezaros D.P., "The Glasgow Raspberry Pi Cloud: A Scale Model for Cloud Computing Infrastructures," icdcsw, pp.108-112, 2013 IEEE 33rd International Conference on Distributed Computing Systems Workshops (ICDCSW), 2013

PS: Can you post the algorithm your going to use?

---
Tags: algorithms, parallel-computing, traveling-salesman
---


title: What's a uniform shuffle?

text:
# Question
Title: What's a uniform shuffle?
What does it mean exactly a "uniform shuffle" algorithm ?

Is this method considered a uniform shuffle ?

```
public void shuffle(Comparable[] a) {
    int n = a.length;
    int k, j;
    for (int i = 0; i < n; i++) {
        k = StdRandom.uniform(n); // k in [0, n-1]
        j = StdRandom.uniform(n); // j in [0, n-1]
        exch(a, j, k);
    }
}

```

# Answer
A **uniform shuffle** of a table $a = \[a\_0, ..., a\_{n-1}\]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible rearrangements of $n$ elements and you need to pick one of them uniformly at random.

Many methods for shuffling *seem* uniform to people but are not and so it is common to see them implemented badly. For instance, shuffling by repeatedly exchanging two randomly chosen elements, as in the question, is not uniform and is also wasteful, as it generates twice as many random numbers as necessary.

A simple algorithm for a uniform shuffle is this:

```
import random
def shuffle(a):
    n = len(a)
    for i in range(n-1):
        j = random.randint(i, n-1)
        (a[i], a[j]) = (a[j], a[i])

```

This works in time $\Theta(n)$ as follows: assuming $a\_0, ..., a\_{i-1}$ are already shuffled, randomly select an element $a\_j$ among the remaining $a\_i, ..., a\_{n-1}$ and exchange it with $a\_i$.

To see that the result is uniformly shuffled, observe that initially every element has $\frac{1}{n}$ chance to land in place $0$ and $\frac{n-1}{n}$ to land in one of the remaining places $1, \ldots, n-1$. Therefore place $0$ is uniformly shuffled. In the next step, every element has probability $\frac{1}{n-1} \cdot \frac{n-1}{n}$ to land in place $1$, because this happens when it is not placed at 0 (probabilty $\frac{n-1}{n}$) *and* it is selected to be at place 1 (probability $\frac{1}{n-1}$). We may proceed inductively: an element lands in place $i$ with probability $$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \frac{n-3}{n-2} \cdot \cdots \cdot \frac{n-i}{n-i+1} \cdot \frac{1}{n-i} = \frac{1}{n}.$$ The first $i$ factors arise for an element *not* being placed anywhere among places $0, \ldots, i-1$, and the last one for it being chosen to be placed at $i$.
> 16 votes

# Answer
As Andrej explains in his answer, a random shuffle consists of applying a uniformly random permutation on the input, or equivalent. Your algorithm, in contrast, applies $n$ random transpositions. This cannot possible produce an *exact* random shuffle, since the probability of each resulting permutation is of the form $A/n^{2n}$, which cannot equal $1/n!$.

However, if you continue to perform random transpositions, eventually you will reach a distribution which is very close to that of a random shuffle. How many exactly are needed? Diaconis and Shahshahani \[1\] showed that $(1/2)n\log n + \omega(n)$. After performing that many random transpositions, you reach a distribution which is $o(1)$-close to uniformly random (in an appropriate sense).

More accurately, if you perform $(1/2)n\log n + f(n)$ transpositions then the resulting sequence of distributions (one for each $n$) is $o(1)$-close to uniformly random if and only if $f(n) = \omega(n)$.

---

1. Generating a random permutation with random transpositions by P. Diaconis and M. Shahshahani (1981)
> 7 votes

# Answer
This is a shuffle similar to what you have. If you go through the permutations you will find some shuffles are favored.

```
for (i is 1 to n)
  Swap i with random position between 1 and n

```

This was actually a error on a poker sitepoker site

It does not produce a uniform distribution
Consider all possible random

```
for (i is 1 to n)
    for (j is 1 to n)
         Swap i with j

```

This is just a simple 1, 2, 3.

```
permutation   count
312           4
321           4
123           4
231           5
213           5
132           5

```

It considers more flops / swaps than required and does not even have a uniform distribution.

Fisher Yates is considered uniform and efficient
> 0 votes

---
Tags: algorithms, terminology, permutations, sampling, randomness
---


# Question
Title: Steps to convert regular expressions directly to regular grammars and vice versa
I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars):

Then I came across many examples that claimed to use these rules to prepare regular grammars from given regex. However I was not able to understand how they are actually using these rules, as they directly gave final regular grammar for given regex. So I decided to try some examples step by step and find whats going on.

Below is one such examples which tries to step by step find RLG and LLG for regex $0^\*(1(0+1))^\*$. At each step, same color is used to match part of regex getting translated into corresponding part in grammar.

**Preparing RLG**

Notice that rule in first table says $e^\*$ gets translated to RLG productions taking form $S\rightarrow eS | \epsilon$. However in example above, we can see that, to emulate * in regex, we have to put $\epsilon$ in step 2 (green color) as indicated by the rule, but also need to add bunch of other stuff in step 4 (blue color), which are not directly indicated by the rule (though somewhat intuitive extension of the rule).

**Preparing LLG**

While preparing LLG also, we can see that, to emulate * in regex, we have to put $\epsilon$ (green colored) in step 1 as indicated by the rule, but also need to add bunch of other stuff in step 2 (green colored), which are not directly indicated by the rule (though again somewhat intuitive extension of the rule).

Apart from star closure, there are many stuff that I dont find straight forward or at least requiring extra awareness (that cannot be easily put in step-by-step procedure) while preparing grammar. For example, while preparing RLG, to emulate $0^\*$, I can do $S\rightarrow 0S|\epsilon$ as indicated by first table. But in above example, I have to remain extra aware that there is something more $((1(0+1))^\*)$ after $0^\*$ which forces me to put $A$ in $S\rightarrow 0S | A | \epsilon$ production in step 2. Other facts I should be aware of:

* While preparing RLG, I should start from left of the regex
* While preparing LLG, I should start from right of the regex

I observed many more such small points which all I need to be aware at each step of preparing grammar. It makes me feel fuzzy.

Am I going correct with this at all? Is there any book which discuss regex to regular grammar direct conversion, giving clear step by step procedure? Or there is simply no such procedure and I am unnecessarily trying to make it up from examples?

# Answer
> 4 votes
As (briefly) indicated by Raphael in a comment, the only difference between an NFA and a linear grammar is formatting. You can use any algorithm which converts a regular expression to an NFA, and produce a right or left linear grammar instead of the NFA, simply by changing the way you produce output.

Specifically, when you are producing an NFA (with any algorithm) you will perform a series of steps of the form "Add a transition labeled $a$ between $P$ and $Q$", where $a$ is either a terminal or $\varepsilon$, and $P$ and $Q$ are states. To "directly" produce a right linear grammar, implement the above step by producing the production $P\to a Q$ if $a$ is a terminal, or $P\to Q$ if $a$ is *ε*. Also, implement the step "Mark $Q$ as a final (accepting) state" by outputting the production $Q\to\varepsilon$. (Alternatively, don't put $Q$ in the productions produced for transitions, if you know in advance that $Q$ is a final state.)

If you want to produce a left linear grammar, you need to work with incoming transitions instead of outgoing transitions; for the $a$-transition from $P$ to $Q$, write $Q\to P a$ unless $P$ is the start state, in which case you just use $Q\to a$. (Again, ε transitions are handled by omitting $a$.)

If the unit productions bother you, use an algorithm which produce an *ε*-free NFA, or produce the NFA and then do an *ε* closure to eliminate the *ε* transitions before printing out the grammar.

Any correct regular expression to linear grammar algorithm will be some version of the above procedure (since you could produce the transition table instead of the grammar by once again changing the print format).

---
Tags: regular-languages, formal-grammars, regular-expressions, simulation
---


# Question
Title: What purpose do the leaves in a range trees serve?
I'm getting into algorithms and I came upon range trees. What confuses me is the leaves in a range tree, since for example:

When you remove the leaves:

It's just a regular BST. And, every implementation I see of a range tree/range searching, for example, doesn't put the points in the leaves like in the first image.

So, why do depictions of range trees show all the points in the leaves when that would double the amount of space required? Is it just for visualization purposes, or does it represent the output? Is a range tree just a BST with a range query? This may seem nitpicky, but it really confuses me. Graphic source: graphics.stanford.edu/courses/cs428-03-spring/03Talks/Range.pdf It isn't unique to this specific example. It's seen here: cs.uu.nl/docs/vakken/ga/slides5b.pdf and here:cs.umd.edu/~meesh/cmsc420/ContentBook/FormalNotes/MountNotes/…, even though they seem to just use regular BSTs and don't seem to put the leaves in the nodes

EDIT: It's probably just for visual purposes: http://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf

# Answer
The Range Tree is made from the input array. The array is sorted and then the tree is built. This means that in the standard construction we have started with the array, this may indicate the leaves. And this BST comes from the sorted array, so there is no point in changing it to e.g. self-balancing trees in the standard case and if there are modifications to the points, the self-balanced trees would perform worse (with very complicated implementation for rotations).

But the Range Tree can be more dimensional, them the leaves represent more dimensions, which leads to several decisions: are these actually pointers or integers (as in example)? Do we want to save memory? Are internal nodes used somewhere else to perform destructive operations?
If the footprint really matters, using integers is a good idea, if there are more dimensions or the integers are cheaper than pointers (to me integers are twice cheaper) this design would be better. So if you add pointers instead of the integers it gets heavier, also the ranges might be smaller, so the savings are bigger.

Also like Raphael pointed it looks like in-order traversal, so it may be right thread in the tree as well.

It may also be for illustratory purposes as you indicated.

Please take a look at the Range trees lecture from Marc ban Kreveld.
> 2 votes

# Answer
I can only guess at the intentions of whoever came up with that graphic, but here is an observation.

The leaves always point to the next node you have to visit in an in-order traversal. Therefore, if implemented as pointers (so they don't take up any extra space!), you can traverse the tree in in-order without a stack. You'll have to mark nodes as visited, though, so I'm not too sure where the big advantage is.

Note that, sometimes, textbook authors pick a particular flavor of things so they fit better with something they do later in the book, or for didactic reasons. The choices don't always make sense outside of the context, and neither do they have to.
> 1 votes

# Answer
It's probably just for visual purposes, since actually doing what the first diagram does would effectively double the amount of space needed, really, unnecessarily and there are other deficiencies of such a design compared to regular BSTs with a range query. It is probably just for visualization purposes,(as seen here:http://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf ), and the leaves aren't actually constructed like that.
> 0 votes

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


title: Algorithm to minimize an expression

text:
# Question
Title: Algorithm to minimize an expression
If I have a constraint like $y\_1 + y\_2 +\dots + y\_n = k$ for positive integers $y\_i$, how would I minimize $$\quad\frac{x\_1 }{ y\_1} + \frac{x\_2 }{ y\_2} + \frac{x\_3 }{ y\_3} + \dots + \frac{x\_n }{ y\_n}$$ if all of the $x\_i$ are given?

One can assume that $n\le5\cdot10^5$ and $k\le10^{12}$.

# Answer
For $n=2$ there is a solution:

Minimize $f(y) = x\_1/y\_1 + x\_2/(k-y\_1)$, it is convex for $y\_1 \>0$ so you can find derivative, solve it for $=0$ and get the solution in reals, then check floor and ceil.

For general $n$ rounding needs more investigation. The only thing I'll mention that the real solution is something like $y\_i = k \cdot \frac{\sqrt{x\_i}}{\sum\limits\_i {\sqrt{x\_i}}}$, from the lagrangian. Then you do the $\max (1, \lfloor y\_i \rfloor)$ and use other deeper results or greedy discussed to reach the sun to be exactly $k$.

UPD: Using greedy after this step, it will take time at most $n$ steps, resulting in $O(n)$ time. Reminder: add 1 to the $y\_i$ where the difference $ \frac{x\_i}{y\_i} - \frac{x\_i}{y\_i+1}$ is maximized. Store this differences using priority queue to reuse calculations.
> -2 votes

---
Tags: algorithms
---


# Question
Title: Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?
The wikipedia page *Powerset construction* says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input".

I understand that the author wants to say that the smallest DFA equivalent to this NFA needs at least $2^n$ states.

But I can find a very much smaller DFA equivalent to this NFA just below:

Is Wikipedia wrong? Or am I? (which is much more likely)

# Answer
> 10 votes
The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000.

A DFA doesn't know how much input is left, so the property "the fourth character *from the end*" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each possible combination of the last four characters, so 2^4 states. If you look hard at the DFA the Wikipedia gives you should be able to figure out which of the states stores which combination of characters.

# Answer
> 8 votes
You can prove the lower bound on the number of states using Myhill-Nerode theory.

Suppose that we are given a language $L$, in this case the language over $\\{0,1\\}$ of words in which the $n$th last symbol is $1$. We say that two words $x,y$ (over the same alphabet) are *equivalent* if for all words $z$, $xz \in L$ iff $yz \in L$. It is easy to check that if two words $x,y$ are not equivalent, then $\delta(q\_0,x) \neq \delta(q\_0,y)$ for every DFA for $L$. In particular, if we can find $N$ pairwise inequivalent words, then it follows that every DFA for $L$ must contain at least $N$ states.

For our language $L$, I claim that the set of $2^n$ words of length exactly $n$ are pairwise inequivalent. Indeed, suppose that $x \neq y$ are two words of length $n$. Then $x\_i \neq y\_i$ for some $i$, say $x\_i = 0$ and $y\_i = 1$ (without loss of generality). Then $x0^{i-1} \notin L$ whereas $y0^{i-1} \in L$, since in both cases the $n$th symbol from the end is $x\_i$ or $y\_i$. Thus every DFA for $L$ must contain at least $2^n$ states.

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


title: Height of data structures

text:
# Question
Title: Height of data structures
Why the height complexity of a data structure, generally expressed in terms of $\log n$, do not contain a ceiling or floor ?

# Answer
> 2 votes
Asymptotically, $\log n$ and $\lfloor \log n \rfloor$ (or $\lceil \log n \rceil$) are the same: a function is $\Theta(\log n)$ iff it is $\Theta(\lfloor \log n \rfloor)$. Therefore there is no need for floor or ceiling.

---
Tags: data-structures, balanced-search-trees
---


# Question
Title: Is it possible to turn an eulerian NFA into a linear size DFA?
In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states.

But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n into a DFA of size at most O(n) ?

If so, does it hold also for a NFAs whose graph is strongly connected ?

I would appreciate some counter example, proof or any reference to research papers dealing with this problem.

Many thanks, Luz

# Answer
> 3 votes
I don't think so.

Suppose you could. Then you can also do this:

* Take any NFA $\mathcal A$ with alphabet $\Sigma$, states $Q$, transitions $\Delta$, initial states $I$ and final / acception states $F$.
* Add transitions to make the graph eulerian in the following way. Take any enumeration of the transition $p\_i\overset{a\_i}{\to}q\_i$. For each $i$, add a transition $q\_i\overset{b\_i}{\to}p\_{i+1}$ where $b\_i$ is a new letter (and the indices are modulo the number of transitions). Note that you add $|\Delta|$ letters and transitions so this transformation is linear.
* Add transitions to make the graph strongly connected in the following way. Take any enumeration of the states $s\_j$. Add a new letter $c$. For each $j$, add a transition $s\_i\overset{c}{\to}s\_{i+1}$. In other words, add a Hamiltonian cycle using only the new letter $c$. Note that this transformation adds $1$ letter and $|Q|$ transitions so it's linear.
* Use your magic procedure to build a new deterministic automaton $\mathcal B'$ so that it recognizes the same language as $\mathcal A'$ (the modified automaton) and $|\mathcal B'|=O(|\mathcal A|)$.
* Remove added letters ($b\_i$ for each $i$ and $c$) and all transitions using them. Call the new automaton $\mathcal B$.

Since $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^\* $ (because if you don't use the new letters, then you're taking a path that already existed), and similarly $\mathcal L (\mathcal B) = \mathcal L (\mathcal B')\cap \Sigma^\* $, we have $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^\*=\mathcal L (\mathcal B')\cap \Sigma^\*=\mathcal L (\mathcal B)$ with $\mathcal B$ a DFA so that $|\mathcal B|=O(|\mathcal A|)$.

But this can not be because of the usual counterexample where the size of the corresponding DFA is of exponential size. To get an explicit counterexample, you can apply the procedure to that counterexample.

---
Tags: automata, finite-automata, nondeterminism, eulerian-paths, connected
---


# Question
Title: Why don't compilers automatically insert deallocations?
In languages like C, the programmer is expected to insert calls to free. Why doesn't the compiler do this automatically? Humans do it in a reasonable amount of time(ignoring bugs), so it is not impossible.

EDIT: For future reference, here is another discussion that has an interesting example.

# Answer
> 87 votes
Because it's undecidable whether the program will use the memory again. This means that no algorithm can correctly determine when to call `free()` in all cases, which means that any compiler that tried to do this would necessarily produce some programs with memory leaks and/or some programs that continued to use memory that had been freed. Even if you ensured that your compiler never did the second one and allowed the programmer to insert calls to `free()` to fix those bugs, knowing when to call `free()` for that compiler would be even harder than knowing when to call `free()` when using a compiler that didn't try to help.

# Answer
> 59 votes
As David Richerby rightly noted, the problem is undecidable in general. Object liveness is a global property of the program, and may in general depend on the inputs to the program.

Even precise *dynamic* garbage collection is an undecidable problem! All real-world garbage collectors use reachability as a conservative approximation to whether or not an allocated object will be needed in the future. It's a good approximation, but it's an approximation nonetheless.

But that's only true in general. One of the most notorious cop-outs in the computer science business is "it's impossible in general, therefore we can't do anything". On the contrary, there are many cases where it's possible to make some headway.

Implementations based on reference counting are very close to "the compiler inserting deallocations" such that it's hard to tell the difference. LLVM's automatic reference counting (used in Objective-C and Swift) is a famous example.

Region inference and compile-time garbage collection are current active research areas. It turns out to be much easier in declarative languages like ML and Mercury, where you can't modify an object after it's created.

Now, on the topic of humans, there are three main ways that humans manage allocation lifetimes manually:

1. By understanding the program and the problem. Humans can put objects with similar lifetimes in the same allocation object, for example. Compilers and garbage collectors must infer this, but humans have more precise information.
2. By selectively using nonlocal book-keeping (e.g. reference counting) or other special allocation techniques (e.g. zones) only when needed. Again, a human can know this where a compiler must infer it.
3. Badly. Everyone knows of real-world deployed programs that have slow leaks, after all. Or if they don't, sometimes programs and internal APIs need to be restructured around memory lifetimes, decreasing reusability and modularity.

# Answer
> 30 votes
## It's an incompleteness problem, not an undecidability problem

While it's true that the optimal placement of deallocation statements is undecidable, that's simply not the issue here. Since it's undecidable for both humans and compilers, it's impossible to always knowingly select the optimal deallocation placement, regardless of whether it's a manual or automatic process. And since no one's perfect, a sufficiently advanced compiler should be able to out-perform humans at guessing approximately optimal placements. So, ***undecidability isn't why we need explicit deallocation statements***.

There are cases in which external knowledge informs deallocation statement placement. Removing those statements is then equivalent to removing part of the operational logic, and asking a compiler to automatically generate that logic is equivalent to asking it to guess what you're thinking.

For example, say that you're writing a Read-Evaluate-Print-Loop (REPL): the user types in a command, and your program executes it. The user can allocate/deallocate memory by typing commands into your REPL. Your source code would specify what the REPL should do for each possible user command, including deallocation when the user types in the command for it.

But if C source code doesn't provide an explicit command for deallocation, then the compiler would need to infer that it should perform the dellocation when the user inputs the appropriate command into the REPL. Is that command "deallocate", "free", or something else? The compiler has no way of knowing what you want the command to be. Even if you program in logic to look for that command word and the REPL finds it, the compiler has no way of knowing that it should respond to it with deallocation unless you explicitly tell it to in the source code.

***tl;dr*** The problem is C source code doesn't provide the compiler with external knowledge. Undecidability isn't the issue because it's there whether the process is manual or automated.

# Answer
> 24 votes
Currently, none of the posted answers are fully correct. It's not impossible to do this, but adding that feature would restrict mermory allocation patterns.

> Why don't compilers automatically insert deallocations?

1. Some do. (I'll explain later.)
2. Trivially, you can call `free()` just before the program exits. But there's an implied need in your question to call `free()` as soon as possible.
3. The problem of when to call `free()` in any C program as soon as the memory is unreachable is undecidable, i.e. for any algorithm providing the answer in finite time, there is a case it does not cover. This -- and many other undecidabilities of arbitrary programs -- can be proved from the Halting Problem.
4. An undecidable problem cannot always be solved in finite time by any algorithm, whether a compiler or a human.
5. Humans (try to) write in a *subset* of C programs that *can* be verified for memory correctness by their algorithm (themselves).
6. Some languages accomplish #1 by building #5 into the compiler. They don't allow programs with arbitrary uses of memory allocation, but rather a decidable subset of them. Forth and Rust are two examples of languages that have more restrictive memory allocation than C's `malloc()`, that can (1) detect if a program is written outside of their decidable set (2) insert deallocations automatically.

# Answer
> 10 votes
"Humans do it, so it's not impossible" is a well-known fallacy. We do not necessarily understand (let alone control) the things that we create - money is a common example. We tend to overestimate (sometimes dramatically) our chances of success in technological matters, especially when human factors seem to be absent.

**Human performance in computer programming is very poor**, and the study of computer science (lacking in many professional education programs) helps understanding why this problem does not have a simple fix. We may some day, perhaps not too far away, be replaced by artificial intelligence on the job. Even then, there will not be a general algorithm that gets deallocation right, automatically, all the time.

# Answer
> 9 votes
The issue is mostly a historic artifact, not an impossibility of implementation.

The way most C compilers build code is so that the compiler only sees each source file at a time; it never sees the whole program at once. When one source file calls a function from another source file or a library, all the compiler sees is the header file with the return type of the function, not the actual code of the function. This means when there is a function that returns a pointer, the compiler has no way to tell if the memory that the pointer is pointing to needs to be freed or not. The information to decide that is not shown to the compiler at that point in time. A human programmer, on the other side, is free to look up the source code of the function or the documentation to find out what needs to be done with the pointer.

If you look into more modern low-level languages like C++11 or Rust you'll find that they mostly solved the issue by making memory ownership explicit in the type of the pointer. In C++ you would use a `unique_ptr<T>` instead of a plain `T*` to hold memory and the `unique_ptr<T>` makes sure that the memory gets freed when the object reaches the end of the scope, unlike the plain `T*`. The programmer can hand the memory from one `unique_ptr<T>` to another, but there can only ever be one `unique_ptr<T>` pointing at the memory. So it is always clear who owns the memory and when it needs to be freed.

C++, for backward compatibility reasons, still allows old style manual memory management and thus the creation of bugs or ways to circumvent the protection of a `unique_ptr<T>`. Rust is even more strict in that it enforces memory ownership rules via compiler errors.

As for undecidability, the halting problem and the like, yes, if you stick to C semantics it is not possible to decide for all programs when the memory should be freed. However for most actual programs, not academic exercises or buggy software, it absolutely would be possible to decide when to free and when not to. That's after all the only reason why human can figure out when to free or not in the first place.

# Answer
> 9 votes
The lack of automatic memory management is a feature of the language.

C is not supposed to be a tool for writing software easily. It is a tool for making the computer do whatever you tell it to do. That includes allocating and deallocating memory at the moment of your choosing. C is a low-level language you use when you want to control the computer precisely, or when you want to do things in a different way than what the language/standard library designers expected.

# Answer
> 6 votes
Other answers have focussed on whether it is possible to do garbage collection, some details of how it's done, and some of the problems.

One issue which hasn't yet been covered though is the inevitable delay in garbage collection. In C, when a programmer calls free(), that memory is immediately available for reuse. (In theory at least!) So a programmer can free their 100MB structure, allocate another 100MB structure a millisecond later, and expect the overall memory usage to remain the same.

This is not true with garbage collection. Garbage-collected systems have some delay in returning unused memory to the heap, and this can be significant. If your 100MB structure goes out of scope, and a millisecond later your program sets up another 100MB structure, you can reasonably expect your system to be using 200MB for a short period. That "short period" may be milliseconds or seconds depending on the system, but there is still a delay.

If you're running on a PC with gigs of RAM and virtual memory, of course you'll probably never notice this. If you're running on a system with more limited resources though (say, an embedded system or a phone), this is something you need to take seriously. This is not just theoretical - I have personally seen this create problems (as in crashing the device kind of problems) when working on a WinCE system using the .NET Compact Framework and developing in C#.

# Answer
> 4 votes
The question presumes a deallocation is something the programmer is supposed to deduce from other parts of the source code. It's not. ***"At this point in the program, memory reference FOO isn't useful anymore"* is information only known in the mind of the programmer** until it's encoded into (in procedural languages) a deallocation statement.

It's not theoretically different from any other line of code. Why don't compilers automatically insert *"At this point in the program, check register BAR for input"* or *"if function call returns nonzero, exit current subroutine"*? From the compiler's point of view the reason is "incompleteness", as shown in this answer. But any program suffers from incompleteness when the programmer hasn't told it everything he knows.

In real life, deallocations are grunt work or boilerplate; our brains fill them in automatically and grumble about it, and the sentiment "the compiler could do it just as well or better" is true. In theory, however, that is not the case, although fortunately other languages give us more choice of theory.

# Answer
> 4 votes
What *is* done: There is garbage collection, and there are compilers using reference counting (Objective-C, Swift). Those that do reference counting need help from the programmer by avoiding strong reference cycles.

The *real* answer to the "why" is that compiler writers haven't figured out a way that is good enough and fast enough to make it usable in a compiler. Since compiler writers are usually quite smart you could conclude that it is very, very hard to find a way that is good enough and fast enough.

One of the reasons that it is very, very hard is of course that it is undecidable. In computer science, when we talk about "decidability" we mean "making the right decision". Human programmers can of course easily decide where to deallocate memory, because they are not limited to *correct* decisions. And they often make decisions that are wrong.

# Answer
> 3 votes
> In languages like C, the programmer is expected to insert calls to free. Why doesn't the compiler do this automatically?

# Because the lifetime of a memory block is the programmer's decision, not the compiler's.

That's it. This is the design of C. Compiler cannot know what was the intention of allocating a memory block. Humans can do it, because they do know the purpose of every memory block and when this purpose is served so it can be freed. That's part of the design of the program being written.

C is low-level language, so instances of passing a block of your memory to another process or even to another processor are quite frequent. In extreme case, a programmer may intentionally allocate a chunk of memory and never use it again just to put memory pressure on other parts of the system. Compiler has no way of knowing if the block is still needed.

# Answer
> 0 votes
> In languages like C, the programmer is expected to insert calls to free. Why doesn't the compiler do this automatically?

In C and many other languages, there is indeed a facility to make the compiler do the equivalent of this in those cases in which it is clear at compile time when it should be done: use of automatic-duration variables (i.e. ordinary local variables). The compiler is responsible for arranging for sufficient space for such variables, and for releasing that space when their (well-defined) lifetime ends.

With variable-length arrays being a C feature since C99, automatic-duration objects serve, in principle, substantially all the functions in C that dynamically-allocated objects of computable duration do. In practice, of course, C *implementations* may place significant practical limits on the use of VLAs -- i.e. their size may be limited as a result of being allocated on the stack -- but this is an implementation consideration, not a language design consideration.

Those objects whose intended usage precludes giving them automatic duration are precisely those whose lifetime cannot be determined at compile time.

---
Tags: compilers, memory-management, garbage-collection
---


# Question
Title: Prove (non-)recursiveness of a set of Turing Machines defined by behavior
I have a list of problems which I don't know how to prove (non-)recursive (save, I think, for the first), where $\mathcal{M}\_n$ is the Turing-Machine with the Gödel-number $n$:

$\mathcal{R}=\left\\{n:\mathcal{M}\_n\text{ does not move right for any input.}\right\\}$

$\mathcal{R}\_\mathcal{S}=\left\\{n:\mathcal{M}\_n\text{ does not move right past the starting position for any input.}\right\\}$

$\mathcal{S}=\left\\{n:\mathcal{M}\_n\text{ does not hang for any input.}\right\\}$

Note: The model used within this question is one with a one-side-unbounded tape with the bound being on the left end, thus "hangs" means trying to move off the left end of the tape; the Turing-machine starts right of the input and has three options per step: writing or moving left or right, so no movement is necessary for a step.

I already researched and tried to find solutions of my own, but as Rice's theorem is not applicable, I failed at finding a direct proof of undecidability or proof by reduction (as I cannot think of a way to reduce any known undecidable problem to any of these); research includes:

None of my own ideas worked out, thus I have little to show for; I had a vague idea of reducing $\mathcal{S}$ to $\mathcal{R}\_\mathcal{S}$ by flipping the input (as well as the movements of the Turing Machine); the main problems are that I have no solution for $\mathcal{S}$ (although I expect it to be non-recursive), and a reduction would need to use an unbounded tape, which may (or may not) break the problem.

Thus, any help (or hint at methodology) would be greatly appreciated.

# Answer
> 3 votes
$\boxed{\mathcal R}$

**Idea**: If you never move right, you have a regular behaviour. And you can move right iff a "state" in which you can move right is reachable while following this regular behaviour.

**Solution:**

> **$\mathcal R$ is decidable**

**Proof:**

> Let $\mathcal M$ be a TM with states $Q$ and tape alphabet $\Gamma$. Build the following automaton:
> \- States: $Q\times (\Gamma \sqcup \\{?\\})$ where the right component is whatever is on the tape at the current position (we write $?$ if it is whatever was there at the very beginning, and $a$ if we wrote an $a$ there)
> \- Transitions:
> $\hspace{0.5em}$ - $(p, a)\overset{a}{\to}(q,?)$ if the TM can read $a$ while in state $p$ and move left
> $\hspace{0.5em}$ - $(p, a)\overset{\varepsilon}{\to}(q,b)$ if the MT can write a $b$ and move to state $q$ if it's in state $p$ and reads an $a$
> $\hspace{0.5em}$ - $(p, ?)\overset{\varepsilon}{\to}(p,b)$ (because since we just moved left and never moved right, replacing the letter at that position on the tape by anything wouldn't change the execution until that point).
> \- The initial states are $(q\_i, ?)$ where $q\_i$ is an initial state of the TM.
> Then in this automaton, a state $(p,a)$ is accessible iff there is a run in the TM so that gets in a state where the TM is in state $p$ and is about to read an $a$ on the tape. So you just have to check if there is an accessible state $(p,a)$ in this automaton so that the TM can read an $a$ while in state $p$ and move right.

---

$\boxed{\mathcal S}$

**Idea:** Halting for all inputs is "For all input, there is an execution that halts" which is more complicated than the halting problem "Given this input, there is an execution that halts".

**Solution:**

> **$\mathcal S$ is undecidable**

**Proof:**

> Take a TM $\mathcal M$ and an input $w$. Build a new TM $\mathcal M'$ that erases its input, writes $w$ and then runs $\mathcal M$.
> $\mathcal M'$ halts on all inputs
> (iff $\mathcal M'$ halts on some input)
> iff $\mathcal M$ halts on input $w$
> So your problem is undecidable because the halting problem can be reduced to it.

# Answer
> 0 votes
(partial answer)

I think that the complement of the halting problem (on empty tape) reduces to $\mathcal{S}$.

Given a TM $M$, we craft another TM $N$ as follows. Without hanging, we simulate $M$ on the empty tape. Note that, when $M$ moves left and hangs, $N$ does not have to move left and hang (it's only simulating that!), so we can perform the simulation without ever hanging, whatever $M$ does. If $M$ diverges, $N$ diverges without hanging. If instead $M$ halts, then $N$ proceeds in moving left until it hangs.

We have $\\#M \not\in HALT \iff \\#N \in \mathcal{S}$.

---

For $\mathcal{R}\_{S}$, the trick of flipping the tape you mention does not seem to work to me. $\mathcal{S}$ allows an unbounded tape (in one direction), which remains unbounded when flipped, when $\mathcal{R}\_{S}$ instead bounds the tape.

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


title: Is this language regular or not?

text:
# Question
Title: Is this language regular or not?
$$L = \big\\{ (0^{m^2})^\* \ \big \vert \ m \ge 1 \big\\}\\,.$$

I've given answer as regular but i am not sure. How? Please explain.

# Answer
Hint. Consider $m=1$ and the question answers itself.
> 5 votes

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


title: shortest distance vs shortest path

text:
# Question
Title: shortest distance vs shortest path
This question might be redundant but I want to verify my understanding further. Suppose I have this linear directed graph:

$$S \overset{2}{\to} A \overset{1}{\to} B \overset{3}{\to} E \overset{1}\to D.$$

Here, $S$ is the source, $D$ is the target, and numbers indicate to edge weight:

1. When taking about shortest *path*, do we only count the **number** of edges? So in this example, shortest paths from $S$ to $D$ is 4.
2. Thus, when taking about shortest *distance*, we find the sum of the edges weights. So in this example, shortest distance from $S$ to $D$ is 7.

The reason why I elaborate this question using example is that I've seen plently of answers when I google this question but it seems they treat the work path and distance in similar way which is counting the number of edges (hops).

# Answer
> 5 votes
If it is ambiguous (as in this case), a well-written text should indicate what it means. If it doesn't, you might have to guess. Sometimes people are sloppy or imprecise, or rely on you to infer what they mean from context. There's certainly no guarantee that people will use language the way you describe -- it's not a standard assumption you can make.

In a graph *without* weights on the edges, the situation is clear, and we will use "shortest path" to mean the path with the fewest edges, and use "distance" to mean the number of edges. In such a graph, the notion of *number of edges* and *sum of edge weights* coincides (since we assume each edge has weight 1), so there's no distinction to draw. Thus, in that situation, we'd use the two words similarly.

In a graph *with* weights (lengths) on the edges, the most common situation is probably to use "shortest" path to mean the path with the smallest sum of edge weights, and use "distance" to refer to the length (sum of edge weights) of the shortest path. In other words, when there are weights (lengths) on the edges, the most common situation is that we never refer to anything involving the number of edges on the path.

But sometimes we have a graph with weights (lengths) on the edges, and we want to talk about two different distance metrics: the *number* of edges on the path, and the *sum* of the weights on the edges on the path. Then it's anyone's guess what terminology people will use; I don't think there's any accepted standard. In this situation, I think you have to hope that the writer defines their terms, or try to infer their meaning from context.

# Answer
> 2 votes
**Bottom line:** the only way to know is to look at how the resource (e.g., book) you are reading defines these concepts.

Typically, when talking about a *path*, we mean just that, i.e., a sequence of arcs and vertices. Every path has a *length*, which is defined as the sum of the weights of its arcs. When we talk about *distance*, it is the shortest length of any path between two vertices. Here, if arcs have no weight, it can be assumed they all have weight 1. In other words, we can count the number of arcs as you say.

---
Tags: graphs
---


# Question
Title: Confused between turing-completeness and universal approximation - are they related?
I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem".

The context here is deep neural nets: So, consider two types of networks: a recurrent neural net, (RNN), and a feedforward net, say a pure convolutional neural net (CNN).

I understand that the RNN is turing complete. I also know that a CNN is a universal approximator, but is NOT turing complete.

What I am trying to understand is the link between universal approximation, and turing-completeness: Is there a link? Why is a CNN a universal approximator but NOT turing complete? Does a machine being turing-complete automatically make it a universal approximator? Trying to uncouple the two concepts.

Thanks!

# Answer
A CNN can approximate a function on a *fixed* number of input variables, say $n$ of them. The set of functions on $n$ input variables isn't "Turing-complete". For instance, a boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$ is always computable, as it can be computed by a program that just hardcodes the truth-table of $f$; and the set of such functions is not "Turing-complete".

Complication: CNN's *actually* approximate continuous functions $f:\mathbb{R}^n \to \mathbb{R}$... but a similar point remains (at least if the input is bounded).

Turing-completeness isn't really connected to universal approximation. For one thing: Turing-completeness talks about languages, which are subsets of $\\{0,1\\}^\*$ and thus refers to discrete entities. Universal approximations talks about functions $f:\mathbb{R}^n \to \mathbb{R}$, and thus refers to continuous entities.

To qualify for "universal approximation", it's enough to be able to approximate all functions of $n$ variables (for each function, there exists a neural network that approximates it), so it talks about functions on inputs of *bounded* length. Turing-completeness requires the ability to compute all computable functions, which is a set of functions that has no fixed upper limit on the number of variables, i.e., it is a set of functions on inputs of *unbounded* length. Universal approximation could thus, in some sense, be considered "weaker" than Turing-completeness (though strictly speaking they are incomparable; neither implies the other).
> 5 votes

---
Tags: turing-machines, approximation, neural-networks, recursion, turing-completeness
---


# Question
Title: print the nodes of an immutable single-linked list in reverse order
Assume you have a single-linked list of length n. The list is immutable. A node `node` has a method `next` and `node.next()` returns a reference to the successor of `node`. `node.print()` prints the value of node `node` or does some other stuff, such etails don't matter.

Is it possible to print the nodes of the list in reverse order in linear time using only a constant amount of space?

---

Details:

For the last element of a list `next` points to a special node named `NIL` that represents the end of a list. For `NIL` `next()` and `print()` are not defined.

The following simple pseudocode program prints the nodes in the order of the list. `FIRST_NODE` points to the first node of the list. Variable names that store references to nodes are prefixed by 'node\_'.

```
node_current=FIRST_NODE
while node_current!=NIL
    node_current.print()
node_nurrent=node_current.next()

```

This algorithm calls of the medthod `next` n-times and there is one variable that can hold a reference to a node.

To print the k-th node of the list one can traverse the list from the start node to the k-th node in k steps. So to print the list in reverse order the following algorithm works

```
node_first=FIRST_NODE
node_last=NIL
while node_last!=node_first
    node_current=node_first
    while node_current!=node_last:
        node_previous=node_current
        node_current=node_current.next()
    node_previous.print()
    node_last=node_previous

```

It needs about $\frac{n^2}{2}$ calls of method next and needs 4 variables that can hold a reference to a node: node\_first (the first node of the list), node\_last (the last node that was printed), node\_current (the node that is currently investigated) , node\_previous (the predecessor of node\_current)

It can be shown that there are algorithms that need about $O(n^{\frac{1}{k}})$ space and $O(n)$ time for an arbitrary choosen k from {2,3,4,...} to print a single-linked list in reversed order. It is also possible to do this in $O(\log n)$ space and $O(n \log n)$ time. This can be found here

Can one do this better?

**My question:** Is there an algorithm with $O(1)$ space complexity and $O(n)$ time complexity that prints such a list in reverse order?

---

Please note that the definition of the problem excludes an algorithm that prints a list in reversed order in linear time with $O(1)$ space for node references while changing the references of the list:

The list is traversed form start to end and the references are reversed during this traversal: the reference from a node to its successor is overwritten by a reverence to its predecessot. If on arrives at the and of the list is straersed form the former end (which is now the start) to the former start (which is now the end) and the nodes are printed.

# Answer
That no such algorithm exists is a classical result attributed to Paterson and Hewitt, though they offer no proof. Swamy and Savage do offer a proof, determining the optimal running time as a function of the memory usage $p$ (number of pointers, roughly) when $p = O(\log n)$, showing that it is $\Theta(pn^{1+1/p})$. In particular, if $p$ is constant then the optimal running time is $\omega(n)$.
> 3 votes

# Answer
No, there is no such algorithm. This is proved in Theorem 2 of "Almost Optimal Hash Sequence Traversal" by Coppersmith and Jakobsson.
> 3 votes

---
Tags: data-structures
---


# Question
Title: Why do BNF specifications of C-like languages define expressions in terms of seemingly unrelated parent expressions?
Backus-Naur Form specifications for the grammars of languages like like C or C++ build up expressions with counter-intuitive definitions. For instance, a multiplication expression like

```
5 * 3

```

is also a `logical-or-expression` and an `equality-expression` and a bunch of other things it doesn't actually look like, because the grammar makes it an:

* `expression`
    + consisting of an `assignment-expression`
        - consisting of a `conditional-expression`
            * consisting of a `logical-or-expression`
                + consisting of a `logical-and-expression`
                    - consisting of an `inclusive-or-expression`
                        * consisting of an `exclusive-or-expression`
                            + consisting of an `and-expression`
                                - consisting of an `equality-expression`
                                    * consisting of a `relational-expression`
                                        + consisting of a `shift-expression`
                                            - consisting of an `additive-expression`
                                                * consisting a `multiplicative-expression`.

A snippet from the grammar looks like:

```
<exclusive-or-expression> ::= <and-expression>
                            | <exclusive-or-expression> ^ <and-expression>
<and-expression> ::= <equality-expression>
                   | <and-expression> & <equality-expression>
<equality-expression> ::= <relational-expression>
                        | <equality-expression> == <relational-expression>
                        | <equality-expression> != <relational-expression>

```

So if I were to write a parser that just followed these productions, I'd end up having to interpret the expression `5 * 3` 12 different ways, e.g. by making it an instance of a MultiplicativeExpression class which derives from AdditiveExpression... all the way up to a base Expression class. And that seems very wasteful, since those classes would implement adding, AND-ing, OR-ing, etc. but would simply no-op for the single-term case.

By comparison, the Wikipedia example of BNF makes more sense:

```
<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL>
              | <personal-part> <name-part>
<personal-part> ::= <initial> "." | <first-name>
...

```

The Wikipedia example reads like "a postal address consists of a \[...\]", whereas C-like language grammars read more like "a \[...\] can be treated as an expression". Why are C-like language grammars so "polymorphic"?

# Answer
> 2 votes
> Why are C-like language grammars so "polymorphic"?

Because that's the way algebra works :-).

The arguments to (for example) a relational expression could be shifts or sums or products (or, for that matter, variables or constants, to say nothing of a variety of unary operator expressions), and all combinations are possible. So you could write out all nine possibilities (and then sixteen possibilities for equality expressions, etc.) (not counting the unary/base possibilities) but the quadratic explosion gets annoying. It's easier to consider each precedence level to include all the more tightly-binding levels as well.

I wouldn't call this polymorphism, really, although you might implement the expression type from a base `Expression` and individual derived types for each operator. The semantic value of every `*-expression` production is then a derived type of `Expression`, and it is not *semantically* necessary to know which one; the production labels are no longer needed.

# Answer
> 1 votes
Context-free derivations are trees. Used to represent the syntactic structure of the sentences of a concrete language - hierarchically, as they must - they give rise to somewhat arbitrary taxonomies of substructures, that are not always intuitive (as your example shows), but better than using just letters or symbols.

This is a problem of knowledge representation, which is an art of compromise. Large hierarchies are often problematic in that way. When you think about how awkward it can get for a computational language (or a file system), remember that in the taxonomy of mammals, the hippopotamus and the blue whale are close cousins.

---
Tags: formal-grammars, programming-languages
---


# Question
Title: Modified Max Product dynamic solution very inefficient
The modified max product problem is as follows: given integer string $z\_1\ldots z\_n$, and an integer $k \leq n - 1$, what is the maximum product that can be formed by placing $k$ multiply signs in between the numbers, in the best possible configuration.

This has ${n-1 \choose k-1} = \frac{n!}{(n-k)!k!}$ configurations...so if $k$ is somewhere around $n/2$, then it should be a very large search space...so maybe some complexity makes sense. However, I think I screwed up (aside from any indexing errors).

I have an $O(n^5)$ algorithm...

```
maxprod(z,n,k):
    for i = 1 to n:
        for j = 1 to n:
            T(i,j,0) = Z[i ... j] as an integer

    for s = 2 to n:
        for i = 1 to n - s:
            let j = i + s-1

            for a = max(0,k-n-s-1) to s-1: (all sizes of a)

                T(i,j,a) = max(...

                    for v = i to j: (splitting i and j)
                        for b = max(0,a-(j-v-1)) to min (a-1,v-1):
                            T(i,v,b)*T(v+1,j,a-1-b)
                  )
    Return T(1,n,k)

```

And I created it using a recursion,

$ T(i,j,a) = \mathop{max}\\{T(i,v,b)\times T(v+1,j,a-1-b)\\} $

Where $v$ is varied from $i$ to $j$ and $b$ is varied from the minimum value it needs to be to the max it can be (for the multiplies needed in the substring such that exactly $k$ multiplies are used).

Is this even properly implemented? Is there a faster solution? Where am I going wrong? For some reason, I am struggling with dynamic programming...(only three or four dp problems solved so far though).

But then, I am thinking: I only do a max across two dimensions, inside the three for loops necessary to fill out a 3d array. This is essentially the fastest I can possibly do it in terms of $O(.)$ with my recursion. Where am I screwing up, conceptually? This problem can't be as difficult as I made it...

# Answer
Why do you split it in the middle? Multiplication is associative so you don't have to do that. Considering only the last multiply sign would be fine. Here's a simpler recursion: $T(1,j,a)=\max\\{T(1,v,a-1)\times T(v+1,j,0)\\}$. I use the same symbols as yours so you can see the difference. The first dimension is useless so the table is actually an $n \times k$ array. Each function call takes $O(n)$, so the complexity is $O(n^2k)$.
> 1 votes

---
Tags: dynamic-programming
---


# Question
Title: Is a bitstring easier to compress if it has lower Kolmogorov complexity?
I have two bitstrings that are 100 bits long. Bitstring A has a Kolmogorov complexity (KC) of 90 and bitstring B has a KC of 10. Intuitively, I think bitstring B is probably easier to compress than bitstring A.

"Easier to compress" means a larger proportion of 100 bit bitstrings with B's KC can be compressed by a standard compression algorithm, than bitstrings with A's KC.

What I mean is that B probably has much more regularity that can be exploited by a compression algorithm such as Lempel-Ziv, whereas A is probably much more random and irregular.

Is this intuition correct? If so, how is this relation quantified? Can I say B is 9 times as likely to be compressible than A?

# Answer
I think your intuition is not correct. We can't effectively reason over the space of all programs, even all programs up to a given size (e.g. 90 for A and 10 for b) and it's not certain what the units are in your given KC measures for B and A.

As a simple example, imagine a program B that decompressed a highly compressible message and then encrypted it using some cipher and a hardcoded key. And imagine a different program A that simply output a hardcoded random string of the same length as the one produced in B. Given a long enough output, you could make K(output(B)) \<\< K(output(A)), but both would be highly uncompressible without having the decryption key for B available.

What you're talking about sounds something like this: https://en.wikipedia.org/wiki/Algorithmic\_probability. It is uncomputable, but if you are willing to e.g. limit the execution time of programs and randomly sample from random programs, you can start to analyze very simple examples.
> 2 votes

---
Tags: data-compression, kolmogorov-complexity
---


# Question
Title: When will deadlock occur in this producer-consumer code
I was reading about Producer Consumer problem from Operating Systems by William Stallings where following code was given:

```
+----------------------------------------------------+-------------------------------------------------------+
|               Producer                             |             Consumer                                  |
+------------------------------------------------------------------------------------------------------------+
| 1  int n;                                          | 1  void consumer()                                    |
| 2  binary_semaphore mx = 1, delay = 0;             | 2  {  semWaitB(delay);  //wait till first data item   |
| 3  void producer()                                 | 3                       //is produced                 |
| 4  {                                               | 4     while (true)                                    |
| 5     while (true)                                 | 5     {                                               |
| 6     {                                            | 6        semWaitB(mx); //continue if producer is not  |
| 7        produce();                                | 7                      //producing                    |
| 8        semWaitB(mx);  //continue if consumer     | 8        take();                                      |
| 9                       //is not consuming         | 9        n--;                                         |
| 10        append();                                | 10        semSignalB(mx);//signal done with consuming |
| 11        n++;                                     | 11        consume();                                  |
| 12        if (n==1) semSignalB(delay);  //unblocks | 12        if (n==0) semWaitB(delay);  //block self if |
| 13                                      //consumer | 13                                    //no data item  |
| 14        semSignalB(mx);  //signal done with      | 14     }                                              |
| 15                         //producing             | 15  }                                                 |
| 16     }                                           | 16  void main()                                       |
| 17  }                                              | 17  {  n = 0;                                         |
|                                                    | 18     parbegin (producer, consumer);                 |
|                                                    | 19  }                                                 |
+----------------------------------------------------+-------------------------------------------------------+

```

It then says that (referring to the line numbers in table below):

> If consumer exhaust buffer setting n to 0 (line 8), producer has incremented it to 1 (line 11 of table), before consumer checking n and waiting on line 14. Line 14 should have blocked consumer since buffer was exhausted, but it did not, since producer incremented n meanwhile. Worst, consumer can immediately run again to consume non existent item to reduce n to -1 (line 20)

Then it says:

> We cannot move the conditional statement inside the critical section as this could lead to deadlock (e.g. after line 8 of above table).

It continues to give different solution.

But I am not able to understand how it will lead to the deadlock. Considering following modified consumer code:

```
1  void consumer()
2  {  semWaitB(delay);  //wait till first data item
3                       //is produced
4     while (true)
5     {
6        semWaitB(mx); //continue if producer is not
7                      //producing
8        take();
9        n--;
10        if (n==0) semWaitB(delay);  //block self if
11                                    //no data item
12        semSignalB(mx);//signal done with consuming
13        consume();
14     }
15  }
16  void main()
17  {  n = 0;
18     parbegin (producer, consumer);
19  }

```

I came up with following:

As you can see, at the end, the values of mx, n and delay are reset to the ones before start. So how this could lead to deadlock? (In fact I feel this could be precise solution.)

# Answer
> 2 votes
It will be caused as follows:

Both processes blocked at the end, hence deadlocked.

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


# Question
Title: Are Perceptrons the neural network equivalence of Linear and Logistic Regression?
am I right in the assumption that both linear and logistic regression algorithms can be represented as the simplest form of neural networks,a perceptron, which consists of a two layers, an Input and an output, that combines all the input each with it's own respective weight to produces a prediction or classification polynomial?

if this is the case, is anything achievable by Linear or Logistic Regression is also achievable by a perceptron?

# Answer
Yes, logistic regression can be viewed as a simple neural network with multiple inputs, a single neuron, a single output, and using the logistic function as the activation function.

No, linear regression is not a form of a neural network (a neural network would have a activation function; but there's nothing like that present in linear regression).
> 3 votes

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


# Question
Title: Eliminating ambiguity when referring to complexity in cases of multiple parameters and/or multiple results
When looking through a few questions at StackOverflow¹ that all ask for algorithms to select *k* distinct random numbers out of *N*, **I've become confused about how to compare the answers in terms of time and space complexity.**

* each algorithm has two parameters, *N* and *k*
* and returns *k* elements

In terms of Big O notation, all the algorithms worth speaking of are *O(N)* overall.

But there are still major differences between them:

* Some require *~k* steps while others *~N*
* Some can return elements one by one while others only return them all at the end.
* Most require all the *k* (or even *N*) elements to be present in memory at once, but some are able to return each one in sequence and discard it.

**Now to unambiguously put these distinctions when describing each algorithm's complexity?** More specifically, I'm interested in **the standard way it is done in formal papers** so as not to reinvent the wheel.

---

¹https://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1/16097246, https://stackoverflow.com/questions/158716/how-do-you-efficiently-generate-a-list-of-k-non-repeating-integers-between-0-and-n, https://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values, https://stackoverflow.com/questions/54059/efficiently-selecting-a-set-of-random-elements-from-a-linked-list

# Answer
> 2 votes
You can report:

* The running time (e.g., $O(k)$ vs $O(n)$),
* The space requirements (e.g., $O(1)$, $O(k)$, etc.), and
* Whether the algorithm is a streaming (online) algorithm or a batch algorithm. A batch algorithm returns the entire answer at once. A streaming or online algorithm returns numbers one at a time. You might also be interested in the notion of "delay"; for instance, a $O(\log n)$ delay algorithm returns algorithms one at a time, taking at most $O(\log n)$ steps (running time) to output each number.

Since there are two variables here, $n$ and $k$, if you report a running time like $O(k)$, it may be helpful to mention explicitly that the constant is independent of $n$.

Formal papers aren't always as formal as you might think. They'll use standard notation and terminology where they exist, but if standard notions don't cover it, they'll just use the English language to describe the situation, or they may introduce some new terminology and provide a definition for it. That's the great thing about human language: it provides a way to express arbitrary new concepts, even ones we don't already have a pre-existing standard name for.

---
Tags: time-complexity, asymptotics, space-complexity
---