title: Path to formal methods

text:
# Question
Title: Path to formal methods
It is not uncommon to see students starting their PhDs with only a limited background in mathematics and the formal aspects of computer science. Obviously it will be very difficult for such students to become theoretical computer scientists, but it would be good if they could become savvy with using formal methods and reading papers that contain formal methods.

> What is a good short term path that starting PhD students could follow to gain the expose required to get them reading papers involving formal methods and eventually writing papers that use such formal methods?

In terms of context, I'm thinking more in terms of Theory B and formal verification as the kinds of things that they should learn, but also classical TCS topics such as automata theory.

# Answer
> 15 votes
In the preface of his book “Mathematical Discovery, On Understanding, Learning, and Teaching Problems Solving” George Pólya writes:

> Solving problems is a practical art, like swimming, or skiing, or playing the piano: you can learn it only be imitation and practice. This book cannot offer you a magic key that opens all the doors and solves all the problems, but it offers you good examples for imitation and many opportunities for practice: if you wish to learn swimming you have to go into the water, and if you wish to become a problem solver you have to solve problems.

I think there is no short path, especially for reaching the state of writing papers. It requires practice, a lot of it.

Some pointers:

If “limited background in mathematics and the formal aspects” means “has never conceived a proof and written it down” then something like this might be a start.

If something on the Theoretical Computer Science Cheat Sheet makes the student feel uneasy, then a refresher course of the according branch of mathematics would be advisable.

There are many sources for mathematical writing: The lecture notes of the 1978 Stanford University CS209 course perhaps. Or this article by Paul Halmos.

# Answer
> 10 votes
Formal methods such as Z, B, TLA, CafeObj heavily rely on set theory, logic, category theory, lambda calculus, and automata for modelling the concepts of types, data, and computation.

You can either jump into a comprehensive monograph such as Logics of Specification Languages, by Dines Bjørner and Martin C. Henson eds., Monographs in Theoretical Computer Science, Springer Verlag, 2008 and learn as you need from, and use references cited there. Or learn one topic a a time:

1. Set theory
2. Mathematical logic
3. Temporal logic
4. Universal algebra
5. Lambda calculus
6. Category theory

# Answer
> 6 votes
I really think "formal" methods are not a very good idea for educational purposes. For that matter, programming a computer is a "formal" method. Does it succeed as an educational tool?

What is needed is understanding, intuition, and the ability to deal with abstraction. Formal methods hinder all that. Rather, they promote trial and error, hacking, pattern matching, imitation, focusing on syntax. The list goes on and on.

Any piece of rigorous mathematics will teach people how to reason correctly. The simpler the domain, the better it is. All I learnt about reasoning I learnt in high school when I did Euclidean Geometry seriously. Calculus and linear algebra in the University did the rest.

Another attractive alternative is philosophical logic, where they teach people how to think about statements and understand what is the information content and what is a consequence of what. They do that without drowning the students in symbols.

If you take stock of all the top Computer Scientists, you would be amazed how many of them have formal training in philosophy. We are losing all that now because philosophy students now think of Computer Science as a mundane subject. Getting our students to learn some philosophy could counter that to some extent. Get them to work through Bertrand Russell's History of Western Philosophy. That will do wonders.

If they work in programming language theory, you can also have them read Quine, whom I regard as the "god father" of denotational semantics. (Quine was essentially doing denotational semantics of natural language in Word and Object, which was a huge source of inspiration for Christopher Strachey. But this book is quite hard going.) The edited collection Quintessence is a nice source of Quine's ideas for a beginner.

\[Note added: One advantage of philosophy over mathematics is that the students get to see *debate*, i.e., they get to see the "right" argument and the "wrong" argument and see the experts demolish the wrong ones. In mathematics, one never gets to see a wrong argument, which limits its educational value.\]

---
Tags: formal-methods, education
---


# Question
Title: Words that have the same right- and left-associative product
I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting:

> Give a non deterministic finite automaton accepting all the strings that have the same value when evaluated left to right as right to left by multiplying according to the following table:
>
> $\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c &a \end{array}$

So if we have the string $abc$,
the product from left to right is $(a \times b) \times c=a \times c=c$ and
the product from right to left is $a \times (b \times c)=a \times b=a$

So $abc$ should not be acceptable for the automata. To me its obvious that any string $aa^\*$ or $bb^\*$ or $cc^\*$ is an aceptable string (their right and left evaluation work on the same partial strings). It is easy to give an NFA that describes the left to right evaluation but the problem is that if the machine try to compute the *right to left* evaluation I think it needs to know the length of the string (so infinite memory is necessary).

So how can a non deterministic automata evaluate from right to left in order to compare with the left to right evaluation?

# Answer
The first trick here is to think of the multiplication table as the transition table of an automaton $A$ with each state representing a letter in your multiplication table, but not worrying about acceptance yet. So the letters on the left and in the body of the table are actually states -- it would be more accurate to write them as $q\_a, q\_b, q\_c$, but I won't. The letters across the top are inputs.

Then construct the automaton $A\_T$ ("$T$" for transpose) for *reverse multiplication* by transposing $A$:

$\qquad \displaystyle\begin{array}{c|ccc} A\_T & a & b & c \\ \hline a & a & c & b \\ b & a & a & c \\ c & c & b & a \end{array}$

So $A(abc)$ takes you to state $c$, and likewise $A\_T(cba)$ moves into state $a$ of $A\_T$, as you note.

However, $A\_T$ assumes you are going right-to-left, and we still want to go left-to-right. So the second trick is to *reverse the automaton* (not the multiplication, which would just get us back were we started), by reversing all the arrows, which leads to a non-deterministic automaton $A\_{TR}$ given by the transition table below, with subsets indicated by concatenated letters to keep the chicken scratching down, so $ac$ is really $\\{a,c\\}$. (hope I got it all right -- seems to work).

$\qquad \displaystyle\begin{array}{c|ccc} A\_{TR} & a & b & c \\ \hline a & ab & b & c \\ b & ∅ & c & a \\ c & c & a & b \\ \hline ab & ab & bc & ac \\ bc & c & ac & abc \\ ac & abc & ab & bc \\ abc & abc & abc & abc \\ ∅ & ∅ & ∅ & ∅ \end{array}$

You can interpret this as a non-deterministic automaton with only the three rows above the line or a determinized version with all 8 rows.

Finally, the machine to solve the problem is the cross-product automaton of the original $A$ and $A\_{TR}$, that is $A \times A\_{TR}$ to perform the intersection behavior of the two automata (we don't need $A\_T$ any more). $A \times A\_{TR}$ has states that are pairs like $\langle a,ac\rangle$. The transition function runs $A$ and $A\_{TR}$ independently. A single start state $\langle 1,1 \rangle$ goes into $\langle a,a \rangle$ under input $a$, into $\langle b,b \rangle$ under input $b$, etc.

Accepting states in the non-deterministic version are $\langle a,a \rangle$ etc. In the deterministic version, accepting states are pairs in which the first component is $\in$ of the second component set, such as $\langle a,a \rangle$ or $\langle b,bc \rangle$.

$A \times A\_{TR}$ augmented and determinized as shown has $25=3\cdot 8+1$ states, so forgive me if I don't write it out in detail. But the non-deterministic version has only $10=3\cdot 3+1$ states.
> 7 votes

# Answer
$(\ast)$ If $L$ is a regular language, then $L^R$, the language consisting of the *reverse* of all words in $L$, is also regular. Take this as an exercise.

How does this help us solve the problem? Let $L\_a,L\_b,L\_c$ be the languages consisting of all strings that evaluate to $a,b,c$ when evaluating from left to right. The language you're interested in is $$ (L\_a \cap L\_a^R) \cup (L\_b \cap L\_b^R) \cup (L\_c \cap L\_c^R). $$ This shows that if you know how to prove $(\ast)$, then you can construct an NFA for the language in question.

In fact, if you use the *idea* of the proof of $(\ast)$, then you can probably just go ahead and construct the automaton. So let's consider this. In particular, let's try to construct an NFA for $L\_a^R$, the language of all strings that evaluate to $a$ when evaluated from right to left.

The idea is this. Suppose that the first letter you see is $b$. Then the rest of the string must evaluate to $b$ (since $bx = a$ implies $x = b$). Similar reasoning applies when the first letter is $c$. When the first letter is $a$, however, the rest can evaluate to either $a$ or $b$, or be null. With an NFA, we can guess (and later verify our guess).

This hint should give you enough to think about, and hopefully solve the problem.
> 8 votes

# Answer
Cute.

First, build an automaton that computes the product from left to right. Easy! Put a transition $\overrightarrow x \xrightarrow{\\;y\\;} \overrightarrow z$ whenever $x \cdot y = z$. There are three states $\\{\overrightarrow a,\overrightarrow b,\overrightarrow c\\}$ representing the three possible products. Start in a fourth state $\overrightarrow 1$ with $\overrightarrow 1 \xrightarrow{\\;x\\;} \overrightarrow x$ for all $x$. The final state is $\overrightarrow x$ if and only if the product of the input word from left to right is $x$.

Now let's build an automaton that computes the product from right to left. This one will be non-deterministic. How do we do that? Simple… To go in the other direction, **just reverse everything**: the arrows and the direction of the product.

> Where we had before $\overrightarrow{x} \xrightarrow{\\;y\\;} \overrightarrow{x \cdot y\\:}$, we now take $\overleftarrow{x \cdot y\\:} \xleftarrow{\\;x\\;} \overleftarrow{y}$: when we consume the word from left to right, we go from a product to its right-hand factor. Or, in other words, $\overleftarrow{x} \xleftarrow{\\;y\\;} \overleftarrow{y \cdot x\\:}$.

Add a disconnected node $\overleftarrow 1$ for the sake of the empty word. All nodes are initial.

Now we need to compute both paths together, so we take the product of the two automata: $(\overrightarrow{x\_1}, \overleftarrow{x\_2}) \xrightarrow{\\;y\\;} (\overrightarrow{z\_1}, \overleftarrow{z\_2})$ iff $\overrightarrow{x\_1} \xrightarrow{\\;y\\;} \overrightarrow{z\_1}$ and $\overleftarrow{x\_2} \xrightarrow{\\;y\\;} \overleftarrow{z\_2}$. Let the four states $(\overrightarrow 1, \overleftarrow x)$ be initial, and the four states $(\overrightarrow x, \overleftarrow x)$ be final. A word is recognized by this non-deterministic automaton iff its product from left to right and its product from right to left are the same $x$.
> 6 votes

# Answer
It seems that your main problem is utilising nondeterminism, so let me elaborate on that.

> The basic idea the others utilise is that a nondeterministic machine can *guess* the final result.

Let us consider your small example $abc$ and Gilles' construction idea. The automaton "computing" the right-to-left product *guesses* the result in the beginning and *verifies* it. So there are three possibilities:

* Guess $a$: As the first symol is $a$, the rl-product of $bc$ must have been $a$ or $b$.
    + Guess $a$: As the second symbol is $b$, the last symbol must have been $b$.
        - (Guess $b$:) It is $c$, so don't accept.
    + Guess $b$: As the second symbol is $b$, the last symbol must have been $c$.
        - (Guess $c$:) It is indeed $c$, so we accept.
* Guess $b$: As the first symol is $a$, this is not possible, so don't accept.
* Guess $c$: As the first symol is $a$, the rl-product of $bc$ must have been $c$
    + (Guess $c$:) As the second symbol is $b$, the last symbol must have been $a$
        - (Guess $a$:) It is $c$, so don't accept.

As you can see, the NFA is able to guess and check every possible computation *bottom-up*. Because the accepted language is defined as the set of strings that is accepted *by at least one run*, all non-accepting runs on the input are ignored; the NFA "always guesses right".

Now it is easy for this NFA to remember its first choice until the end. If it accepts, it can compare the remembered symbol to the lr-product (deterministically) obtained in parallel (how language intersection relates to NFA is surely covered in Ullman/Hopcroft, and any other basic textbook).
> 5 votes

---
Tags: formal-languages, automata, regular-languages, finite-automata, nondeterminism
---


# Question
Title: Complexity of finding the largest $m$ numbers in an array of size $n$
What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ time. Any comments regarding the proof itself, or the style (i.e. my ideas may be clear but the presentation not).

The original question:

> Given $n$ numbers, find the largest $m \leq n$ among them in time $o(n \log n)$. You may not assume anything else about $m$.

My answer:

1. Sort the first $m$ elements of the array. This takes $O(1)$ time, as this is totally dependent on $m$, not $n$.
2. Store them in a linked list (maintaining the sorted order). This also takes $O(1)$ time, for the same reason as above.
3. For every other element in the array, test if it is greater than the least element of the linked list. This takes $O(n)$ time as $n$ comparisons must be done.
4. If the number is in fact greater, then delete the first element of the linked list (the lowest one) and insert the new number in the location that would keep the list in sorted order. This takes $O(1)$ time because it is bounded by a constant ($m$) above as the list does not grow.
5. Therefore, the total complexity for the algorithm is $O(n)$.

I am aware that using a red-black tree as opposed to linked list is more efficient in constant terms (as the constant upper bound is $O(m\cdot \log\_2(m))$ as opposed to $m$ and the problem of keeping a pointer to the lowest element of the tree (to facilitate the comparisons) is eminently doable, it just didn't occur to me at the time.

What is my proof missing? Is there a more standard way of presenting it (even if it is incorrect)?

# Answer
Here is an $O(n)$ algorithm solving the problem.

1. Use the worst-case $O(n)$ *selection* algorithm to determine the $n-m+1$-th order statistics. Let $k$ be this number, which is the smallest of the $m$ largest numbers we are trying to determine.
2. Now partition the array around the pivot $k$ using the QuickSort *partition* function. This step takes $O(n)$ too.
3. Output the $m$ largest numbers: these are given by $k$ and all of the numbers in the upper subarray generated by partition in step 2.
> 17 votes

# Answer
Your algorithm takes $\Theta(n + mn)$ time. I suspect that your professor is looking for something that takes $O(n+ n\log m)$ time, which should be possible, maybe by using a heap...

The source of your disagreement with the professor is that he or she doesn't appear to think $m$ is a constant, despite how the question is worded. If it's not, then $\Theta(m)$ is a lot worse than $\Theta(\log m)$.
> 5 votes

# Answer
**Correctness**
Missing from your presentation is the loop invariant to establish correctness: you maintain the largest $m$ elements encountered so far in a linked list. Thus, by the end of your algorithm, you have tested *all* the elements, and so you have the largest $m$ elements in the array. Your algorithm is still correct, but stating the purpose of the linked list at the beginning of the description makes its correctness more explicit.

**Running Time**
$log\_{10}( 10 \mbox{ billion}) = 10$, (with base 2, it's about ~33) which is a heck of a lot smaller than 10 million. In the example given, $m$ is many times larger than $\log n$, and so I don't think you can safely assume that $m$ is constant.

You should provide an algorithm that is $o(n \log n)$ as long as $m = o(n)$. Replacing your linked-list and linear search with a balanced binary search tree or a min-heap will achieve this run-time: $O(m \log m + n \log m) = O(n \log m) = o(n \log n)$. (assuming $m = o(n)$, otherwise your run-time is $\Theta(n \log n)$)

In case you're not familiar with the notation, the intuition behind $o(n \log n)$ is $\< O(n \log n)$, but see the corresponding question on cs.SE for details of the notation.
> 1 votes

---
Tags: algorithms, time-complexity, runtime-analysis
---


# Question
Title: Find the longest path from root to leaf in a tree
I have a tree (in the graph theory sense), such as the following example:

This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length assigned to it.

My question is, how to find the longest path starting at the root and ending at any of the leaves? The brute-force approach is to check all the root-leaf paths and taking the one with maximal length, but I would prefer a more efficient algorithm if there is one.

# Answer
> 15 votes
Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with `LongestPath(root)` will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

```
 LongestPath(node)
   If node is a leaf, return (node,0)
   If node is not a leaf:
    For each edge (node,length,next):
       Let (p,l) = LongestPath(next)
       Let (path,len) = (p++[next], l + length)
    Return element (path,len) from previous step with largest value len

```

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.

---
Tags: algorithms, graphs
---


title: Requirements for emulation

text:
# Question
Title: Requirements for emulation
What are the complete specifications that must be documented in order to ensure the correct execution of a particular program written in Java? For instance, if one were archiving a program for long-term preservation, and no testing or porting would be done.

I need to be able to compile and execute the Java program. Thus preserving the byte code or capturing the whole thing as a VMware image are excluded. The JVM could be saved as a VMware image though, and compiled libraries that are linked to the compiled code are OK, too. However, if there are dependencies on the OS, the architecture of the machine executing the JVM, the networking environment, external libraries, specification of the Java version used, etc. etc. these must all be listed. Some tech leaders in Dig Pres claim that any program written in Java will be executable "forever". How to do it?

# Answer
> 5 votes
Hoeven et al. studied the problem of digital preservation through emulation:

*... Digital preservation does not end with the careful storage of digital objects. In order to keep these objects accessible, a continuous effort towards the development of strategies for permanent access is required ....*

They ended up with a modular emulation model and the need of an Universal Virtual Machine (UVM):

*... The basis of the modular emulation model is founded on the Universal Virtual Machine (UVM). The UVM is a platform- and time-independent layer on top of the underlying future host platform. As a result, programs that are developed for the UVM will continue to work even if the host platform changes. It not only consists of a general purpose processor and memory, but also offers additional functionality for input and output (I/O) communication with peripheral devices (like keyboard, storage, graphics, networking) between host and target platform. This will be provided by the interface layer.*

.. and started the "Dioscuri project": a modular emulator for digital preservation. **Not surprisingly, they chose Java to implement it**:

*... Java has been chosen as programming language. The main reason is its possibility to run Java code on a large variety of computer platforms using the Java Virtual Machine (JVM) without the need to recompile the source code. Recompilation is a risk factor since program code is adapted to a specific underlying computer platform. Although today’s compilers are very advanced, it can still result in different functionality of the same emulator compiled for different platforms. By avoiding this step, the emulator will be more stable and portable. Using the JVM instead provides similar results to the use of a UVM as discussed above....*

The papers:

**EDIT**: the last changelog of the Dioscuri project is dated: 19-Jan-2011 ... so - perhaps - a new project/research should be started: *"How to preserve the digital preservation tools?"* :-D :-D

**EDIT 2**: just my personal opinion: if the Java program does useful things, humanity will preserve it without the need of any efforts by its author :-)

---
Tags: operating-systems, computer-architecture, digital-preservation
---


# Question
Title: Is it better to store the magnitude of an arbitrary-precision number in BigEndian or LittleEndian order in an integer array?
I'm implementing a class which provides arbitrary-precision arithmetic (also called "bignum", "BigInteger", etc.).

My questions is about a practical implementation detail:

I'm wondering if there is a significant difference in implementation and computational complexity between an implementation which stores the magnitude in an integer array in BigEndian order vs. LittleEndian order.

My data structure is basically:

```
class BigInt
  val signum: Int
  val magnitude: Array[Int] // two-complement (unsigned)

```

Supported operations are for instance:

+, -, * (Long multiplication, Karatsuba, Cook3, Schönhage-Strassen), /, squaring Conversion to other number types Comparison, equality, representation as a String

*The implementation is immutable, so every operation will return a new value and will not change the any existing.*

Feel free to ask for clarifications!

# Answer
> 5 votes
You are replacing `magnitude[i]` by `magnitude[SZ-i]`. That won't have any effect on complexity nor ease of implementation. Depending on the way simplifications occur, one or the other could have slightly less index adjustments, but I won't dare a guess which. Little endian seems slightly more in line with the usual presentations of the algorithms (for instance in TAOCP), big endian had a more intuitive representation of the number in memory, but that's an opinion more than a fact.

If you look at memory access patterns, there was a time when cache prefiller handled better increasing consecutive accesses (which would have favored little endian), but nowadays, I don't think it still make a difference at least on workstation and server processors.

So I don't think there is a compelling argument to choose BE over LE or ortherwise. Take the one which make you more at ease.

# Answer
> 3 votes
In terms of computational complexity, and even in terms of significant differences in running time, it doesn't matter. Pick one.

From a software engineering perspective, having recently debugged bignum code on architectures with different endiannesses, I've found a big-endian representation easier to work with because I can read numbers straight out of a hexadecimal memory dump (i.e. when I see `000700123456789abc` in a memory dump, I can copy-paste `123456789abc` to check the value in a calculator). This is not a compelling argument, and only applies if your debugging tools aren't capable of recognizing bignums as such.

---
Tags: data-structures, arrays
---


# Question
Title: "Dense" regular expressions generate $\Sigma^*$?
Here's a conjecture for regular expressions:

> For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^\*| = 2$
>
> **Conjecture:** If $|R| \> 1$ and $L(R)$ contains every string of length $|R|$ or less, then $L(R) = \Sigma^\*$.

That is, if $L(R)$ is 'dense' up to $R$'s length, then $R$ actually generates everything.

Some things that may be relevant:

1. Only a small part of $R$ is needed to generate all strings. For example in binary, $R = (0 \cup 1)^\* \cup S$ will work for any $S$.
2. There needs to be a Kleene star in $R$ at some point. If there isn't, it will miss some string of size less than $|R|$.

It would be nice to see a proof or counterexample. Is there some case where it's obviously wrong that I missed? Has anyone seen this (or something similar) before?

# Answer
Your conjecture is disproved by Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang in their paper "Regular Expressions: New Results and Open Problems". While the paper is not available on-line, a talk is.

In the paper, they define the measure $|\mathrm{alph}(R)|$, which is the number of symbols in $R$, *not counting $\epsilon$ or $\emptyset$*. However, $\emptyset$ can be eliminated from every expression not generating the empty language, and the expression can be "cleaned up" so that the number of $\epsilon$ it contains is at most $|\mathrm{alph}(R)|$ (Lemma on page 10 of the talk).

In page 51, for every $n \geq 3$ they construct a regular expression of size $O(n)$ over $\\{0,1\\}$ which generates all strings of size at most $\Omega(2^n n)$, but doesn't generate all strings. Note that "size" here is both in your sense and theirs, since we're using big-O notation. They also pose an open question to find the best dependence between the two parameters.
> 35 votes

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


# Question
Title: Chomsky normal form and regular languages
I'd love your help with the following question:

> Let $G$ be context free grammar in the **Chomksy normal form** with $k$ variables.
>
> Is the language $B = \\{ w \in L(G) : |w| \>2^k \\}$ regular ?

What is it about the amount of variables and the Chomsky normal form that is supposed to help me solve this question? I tried to look it up on the web, but besides information about the special form itself, I didn't find an answer to my question.

The answer for the question is that $B$ might be regular.

# Answer
Assuming that $B$ is regular, then $L(G)=B \cup \lbrace w \in L(G) \mid \vert w \vert \leq 2^k \rbrace$ is also regular because the union of a finite number of regular languages is regular (especially, $k$ is a constant as the number of variables in the Chomsky normal form).

This can not be true in general because there are context free languages which are not regular.
> 11 votes

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


# Question
Title: Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$
I would like your help with the following question:

> Let $L$ be a language, and operator $A(L)=\\{\\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\\,\\}$ where $x^R$ is the reversed string of $x$. Which of the following statements are correct?
>
> 1. If $L$ is regular so $A(L)$ is regular.
> 2. If $L$ is a CFL which is not regular then $A(L)$ is CFL which is not regular.
> 3. If $L$ is a CFL which is not regular, then $A(L)$ is a CFL which may or may not be regular.
> 4. If $L$ is not a CFL then $A(L)$ is not CFL.

What does the fact that $|w|\< 2007$ help me with the decision? For (2) I can choose $O^n1^n$ and I get that $0^n1^{2n}0^{2n}1^n$, which is not regular, but for (3),(4) I can't find an examples to refute it. The answer is 3, but I can't understand why, since $A(L)= ww^R \circ w$ but $ww^R$ is not regular.

# Answer
> 11 votes
Since $|w| \< 2007$, the number of strings like $ww^Rw$ is finite. So $A(L)$ is finite for all $L$ and is hence regular.

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


title: Finding a worst case of heap sort

text:
# Question
Title: Finding a worst case of heap sort
I'm working on problem H in the ACM ICPC 2004–2005 Northeastern European contest.

The problem is basically to find the worst case that produces a maximal number of exchanges in the algorithm (sift down) to build the heap.

* Input: Input ﬁle contains $n$ ($1 \le n \le 50{,}000$).
* Output: Output the array containing $n$ different integer numbers from $1$ to $n$, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible.

Sample input: `6`
Corresponding output: `6 5 3 2 4 1`

And the basics outputs:

```
[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 3, 2, 1]
[6, 5, 3, 4, 1, 2]

```

# Answer
> 4 votes
Given the worst-case for $n$, we can construct the worst-case for $n+1$ as follows: we do a 'swap cycle' as follows: we take $n+1$, put it in $a\[0\]$, and we swap $a\[0\]$ with the maximal element of its children, which is $a\[1\]$ or $a\[2\]$, which we again swap with the maximum element of its children and so on, until we leave the $n$-element heap, at which point we put that last element at the $n+1$-th position.

An example: the worst-case for $n=5$ is $\[5, 4, 3, 2, 1\]$. We swap in 6 which creates the heap $\[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1\]$, after which we end up with 2, which we insert at the end: $\[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1, \textbf{2}\]$.

The above method works by induction: we start from the worst result for $n-1$ elements and perform a sift-down operation in reverse, maximizing the number of swaps it has to do ($\lfloor\log(n)\rfloor$ swaps). You can't do more swaps than this, so you maximize the number of swaps after the first extract-min operation, after which you are left with exactly the worst-case for $n-1$ elements for the next extract-min operation. This implies that the number of swaps is indeed maximal.

Note that this method gives different results than you have gotten:

```
[1]
[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 1, 3, 2]
[6, 5, 1, 4, 2, 3]
[7, 6, 1, 5, 2, 4, 3]
[8, 7, 1, 6, 2, 4, 3, 5]
[9, 8, 1, 7, 2, 4, 3, 6, 5]
[10, 9, 1, 8, 2, 4, 3, 7, 5 ,6]

```

However, both solutions are correct:

```
[5, 4, 1, 3, 2]
[2, 4, 1, 3| 5]
[4, 2, 1, 3| 5]
[4, 3, 1, 2| 5]
[2, 3, 1| 4, 5]
[3, 2, 1| 4, 5]

[5, 4, 3, 2, 1]
[1, 4, 3, 2| 5]
[4, 1, 3, 2| 5]
[4, 2, 3, 1| 5]
[1, 2, 3| 4, 5]
[3, 2, 1| 4, 5]

[6, 5, 1, 4, 2, 3]
[3, 5, 1, 4, 2| 6]
[5, 3, 1, 4, 2| 6]
[5, 4, 1, 3, 2| 6]
[2, 4, 1, 3| 5, 6]
[4, 2, 1, 3| 5, 6]
[4, 3, 1, 2| 5, 6]
[2, 3, 1| 4, 5, 6]
[3, 2, 1| 4, 5, 6]

[6, 5, 3, 4, 1, 2]
[2, 5, 3, 4, 1| 6]
[5, 2, 3, 4, 1| 6]
[5, 4, 3, 2, 1| 6]
[1, 4, 3, 2| 5, 6]
[4, 1, 3, 2| 5, 6]
[4, 2, 3, 1| 5, 6]
[1, 2, 3| 4, 5, 6]
[3, 2, 1| 4, 5, 6]

```

---
Tags: algorithms, data-structures, algorithm-analysis, sorting
---


# Question
Title: Complexity of checking whether linear equations have a positive solution
Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $\<n$. What is the complexiy to check whether it has a solution $x$ such that all entries of $x$ are stricly greater than 0 (namely, $x$ is a positive vector)? Of course, one can use Gauss elimination, but this seems not to be optimal.

# Answer
> 14 votes
First, this can be solved by linear programming. Let $x\_1$, $x\_2$, $\ldots$, $x\_n$ be your variables. The linear program that solves your question is then

$\max t$
subject to
$t \leq x\_i$, for $i=1 ... n$,
$Ax = 0$.

If the maximum is 0, then there is no positive solution. If the maximum is $\infty$ (i.e., the linear program is *unbounded*) then there is a positive solution.

---

Second, using standard transformations on linear programs, the feasibility problem for an arbitrary linear program with strict inequalities can be reduced to your problem. We start with the feasibility problem

Does there exist $x$ such that
$A x \ 0$ to make everything homogeneous. So for the $k$th equation, we now have

$a\_{k,1} x\_1 + \ldots + a\_{k,n} x\_n - b\_k x\_{n+1} \< 0$.

This gives an equivalent problem on a new matrix $A'$:

Does there exist $x$ such that
$A'x \< 0$ ?

Next, we can turn the inequalities into equations by adding some variables $y\_i$ and requiring that $y\_i \> 0$. The $k$th equation on the new problem turns into

$a'\_{k,1} x\_1 + \ldots + a'\_{k,n} x\_n + a'\_{k,n+1} x\_{n+1} +y\_k = 0$.

Finally, we want to allow all the variables to be positive. How we do this? For every variable $x\_i$ with an arbitrary sign, we replace $x\_i$ by $z\_i - w\_i$, and require $z\_i\>0$, $w\_i \> 0$.

The feasibility problem is essentially as hard as an arbitrary linear programming problem, so in general there won't be any easier way to solve your problem than using linear programming.

---
Tags: algorithms, complexity-theory, linear-algebra
---


# Question
Title: Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED
NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really a TSP variant, but I put it due to lack of a better definition of the problem.

This problem was originally posted on StackOverflow, but I was told that this would be a better place. I got one pointer, which converted the problem from non-metric to a metric one.

So..

Suppose I am going on a hiking trip with n points of interest. These points are all connected by hiking trails. I have a map showing all trails with their distances, giving me a directed graph.

My problem is how to approximate a tour that starts at a point A and visits all n points of interest, while ending the tour anywhere but the point where I started and I want the tour to be as short as possible.

Due to the nature of hiking, I figured this would sadly not be a symmetric problem (or can I convert my asymmetric graph to a symmetric one?), since going from high to low altitude is obviously easier than the other way around.

Since there are no restrictions regarding how many times I visit each point, as long as I visit all of them, it does not matter if the shortest path from a to d goes through b and c. Is this enough to say that triangle inequality holds and thus I have a metric problem?

I believe my problem is easier than TSP, so those algorithms do not fit this problem. I thought about using a minimum spanning tree, but I have a hard time applying it to this problem, which under the circumstances, should be a metric asymmetric directed graph?

What I really want are some pointers as to how I can come up with an approximation algorithm that will find a near optimal tour through all n points

# Answer
I don't know how to solve your problem or show its NP-Hardness but you can find all pair shortest path to convert your graph to metric one, just replace $e\_{a,b}$ with shortest path from a→b and if there isn't edge between $a,b$ add new edge with shortest path weight, now you can run some approximation for TSP to find approximation for your problem, as I know best approximation for TSP is currently $O({\log n \over \log{ \log n}})$. Base idea is using Held-Karp relaxation and finding special spanning tree then using method like Christofides algorithm. (it has some new definitions like Thin tree, ... which makes it harder than other methods for asymmetric case), you can also use known $O(\log n)$ approximations. Also I thought about your problem to approximate it with a minimum cycle cover, but I couldn't get good result. If I found anything I'll update this answer.
> 3 votes

---
Tags: algorithms, complexity-theory, graphs, approximation
---


# Question
Title: Closure against right quotient with a fixed language
I'd really love your help with the following:

For *any* fixed $L\_2$ I need to decide whether there is closure under the following operators:

1. $A\_r(L)=\\{x \mid \exists y \in L\_2 : xy \in L\\}$
2. $A\_l(L)=\\{x \mid \exists y \in L : xy \in L\_2\\}$.

The relevant options are:

1. Regular languages are closed under $A\_l$ resp. $A\_r$, for any language $L\_2$
2. For some languages $L\_2$, regular languages are closed under $A\_l$ resp. $A\_r$, and for some languages $L\_2$, regular languages are not closed under $A\_l$ resp. $A\_r$.

I believed that the answer for (1) should be (2), because when I get a word in $w \in L$ and $w=xy$ I can build an automaton that can guess where $x$ turning to $y$, but then it needs to verify that $y$ belongs to $L\_2$ and if it won't be regular, how would it do that?
The answer for that is (1).

What should I do in order to analyze those operators correctly and to determine if the regular languages are closed under them or not?

# Answer
To answer these question, we need allow **any** $L\_2$. So let's think that $L\_2$ is a very complex language (say, some undecidable language.)

---

Lets start from the easy question: $A\_l(L)$ (question part 2). Take $L\_2$ to be undecidable, and $L=\\{\varepsilon\\}$. What happens?

(moral: Always check the "extremes": empty $L$, $L=\\{\varepsilon\\}$ and $L=\Sigma^\*$...)

---

Now for $A\_r$. This is a great question (usually bonus question in Final/Homeworks). Indeed, **regular languages are closed under $A\_r$** for **any** language $L\_2$. Even undecidable $L\_2$. Cool, right?

So how can we build an automaton for $A\_r(L)$ if there is no machine that accepts $L\_2$?

Here comes the magic of "abstract thinking",i.e., **existential proof**. If someone gives us $L\_2$ we can use this information to show that there **exists** some automaton to solve $A(L)$. Now the details.

We start from the automaton of $L$ (call is $DFA\_L$). Assume that after processing $x$ we end up in a state $q$. We need to accept if there exists $y\in L\_2$ such that if we continue from $q$ processing $y$ we will end up in a final state of $DFA\_L$. There is no machine that can tell us if $y$ is in $L\_2$, but we can make $q$ a final state of $DFA\_{A\_L}$ if the above condition holds, i.e., if there exists some $y\in L\_2$ such that if we start at $q$ and process $y$ we end up in a final state of $DFA\_L$.

so to build $DFA\_{A\_L}$ we examine each one of the states of $DFA\_L$ and make each state $q$ an accepting state if we can take some $y\in L\_2$ and this $y$ will lead us from $q$ to an accepting state of $DFA\_L$.

So ok, $L\_2$ is infinite, and we might have no computer to list all the words in $L\_2$, but all of this doesn't matter... the above automaton is well-defined, even if I can't draw it to you state by state. Magic.
> 12 votes

# Answer
*I'm not sure if you are looking for an answer to the problem or not, so I don't provide it directly. (I can if you want it, though.)*

You asked:

> What should I do in order to analyze those operators correctly and to determine if the regular languages are closed under them or not?

Your starting approach is a good one. As with all "open" theory questions, you should get an intuitive feel for whether it is true or not. Usually this is by trying examples (both common and edge-case) or investigating special cases (e.g. what if $L\_2$ is regular? context-free?). For this problem, you need to develop some guess as to whether you can build an automaton/regex for the operators or not. After that:

* If you think that you can, you need to be able to construct this automaton/regex for any regular input language $L$.
* If you think that you cannot, you would typically find example languages $L$ and $L\_2$ such that $A\_x$ is not closed.

(and if one approach isn't working, you can always try the other.)

---

For the problem itself:

These both are the right quotient operator. (I believe left quotient involves leaving the postfix instead of the prefix.) The difference between the two is that $A\_l(L) = L\_2 / L$ while $A\_r(L) = L / L\_2$, where $L\_2$ is fixed in both cases.

You have some intuition about $A\_r$, so here's something to think about for $A\_l$: $A\_l$ gives a modified version of $L\_2$. Since $L\_2$ could be nonregular, is it possible for $A\_l$ to leave $L\_2$ unchanged? If so, then $A\_l$ is not regular in that case. Otherwise, we will have to argue that $A\_l$ **makes** $L\_2$ regular in all cases.
> 7 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Is $A=\{ w \in \{a,b,c\}^* \mid \#_a(w)+ 2\#_b(w) = 3\#_c(w)\}$ a CFG?
I wonder whether the following language is a context free language: $$A = \\{w \in \\{a,b,c\\}^\* \mid \\#\_a(w) + 2\\#\_b(w) = 3\\#c(w)\\}$$ where $\\#\_x(w)$ is the number of occurrences of $x$ in $w$. I can't find any word that would be useful to refute by the pumping lemma, on the other hand I haven't been able to find a context free grammar generating it. It looks like it has to remember more than one PDA can handle.

What do you say?

# Answer
Yes, $A$ is a CFL. Use the context free language (with the notation $|x|\_0$ meaning what you have as #0's in $x$):

$B=\\{x\in \\{0,1\\}^\*:3\cdot|x|\_0=|x|\_1\\}$

and the morphism $f:\\{a,b,c\\}^\*\rightarrow\\{0,1\\}^\*:$ $ f(a)=0, f(b)=00, f(c)=1$

so that

$A=f^{-1}(B)$.

Since the CFL's are closed under inverse morphism, $A$ is a CFL.

The proof that $B$ is a CFL is a bit tricky. Let's do it for the simpler case $C=\\{x:|x|\_0=|x|\_1\\}$, which can fairly easily be generalized to work for $B$ (or use another morphism).

Design a PDA which keeps track of $|x|\_0-|x|\_1$ at all points of the input, using the stack to keep track of the difference, having read $x$. The PDA accepts only when that difference is zero, that is, the stack is empty. The idea is to push a $0$ on seeing a $0$ on the input string, and pop a $0$ when seeing a $1$ in the input. The problem is that difference might go negative at times, and you can't pop an empty stack. In that case, however, the PDA goes into another mode (a different set of states) where it pushes a $1$ on seeing an input of $1$ and pops a $1$ on seeing an input of $0$. So the second mode handles the negative case. It alternates between the two modes, accepting only if the stack if totally empty, that is, in-between the modes.

Or, you can do it with the grammar: $S\rightarrow 0S1|1S0|SS|\epsilon$. That clearly generates only strings of C, but proving that it generates all of $C$ is a bit involved, but here's a sketch, by induction on string length.

An *isosymbolic* string $x$ (that is $|x|\_0 = |x|\_1$) could be null, in which case the $\epsilon$ production applies giving the basis of the induction. Otherwise $x$ either starts and ends in different symbols (one end $0$ and the other end $1$), or the same symbol (both $0$ or both $1$). In the not-equal case, the last production to apply is either the $0S1$ or the $1S0$ production, allowing us to strip off the first and last symbols, getting a shorter isosymbolic string, so the induction applies.

In the equal case, as with the PDA, we keep track of $|y|\_0-|y|\_1$ as we move from left to right through prefixes $y$ of $x$. If the first and last symbols of $x$ are the same, it's fairly easy to see that that expression must be zero somewhere in the interior of the string. For example, if $x$ starts and ends with $0$, then after the first symbol the difference is $+1$ and before the last symbol it is $-1$, so it must have crossed zero in the interior. Split the string in two at that spot (reversing the $SS$ production) and the two halves, both shorter than $x$, are both isosymbolic. So the induction works there too, and we are done.
> 10 votes

# Answer
All an automaton has to remember is the balance of the equation: $\\#\_a + 2 \\#\_b - 3 \\#c$. It can do this by maintaining a unary counter on the stack, using two symbols `-` and `+`:

* On encountering $a$, pop `-` if possible, otherwise push `+`.
* On encountering $b$, pop two `-` if possible, otherwise pop `-` and push `+` if possible, otherwise push `++`.
* On encountering $c$, pop three `+` if possible, or pop `++` and push `-`, or pop `+` and push `--`, or push `---` (so that there is never both a `+` and a `-` on the stack).

The automaton accepts the input only if the stack is empty.

To build a grammar, decompose each word in $A$ into disconnected groups such that the letter that pushes a symbol is grouped with the letter that pops it. (“Group” is to be taken in the intuitive sense, this has nothing to do with the mathematical concept.) For example (each color represents a different group):
$\quad \color{red}{aa}\color{blue}{abc}\color{red}{ca}\color{magenta}{cab} $
$\quad \color{red}{b}\color{blue}{abc}\color{red}{ac}\color{magenta}{acaa} $
$\quad \color{red}{a}\color{blue}{abc}\color{red}{cacaab} $
$\quad \color{red}{b}\color{blue}{abc}\color{red}{cb}\color{magenta}{cab}\color{red}{aca} $
$\quad \color{red}{bcbcb} $

Between the elements of a group, what you have is an element of $A$ (since it brings the balance back to where it was). Furthermore, there are only a finite number of possible groups if you decompose as much as possible, because the length of each group is at most the least common multiple of the coefficients of the equation ($\mathrm{lcm}(1,2,3)=6$): if there was a longer group, you could find a decomposable subgroup inside it. This leads to the following grammar, which expresses that a word in $A$ is the group that it starts with with words in $A$ interspersed at any point:

$$\begin{align\*} S ::=& \epsilon \\ |& a \\,S\\, a \\,S\\, a \\,S\\, c \\,S\\, \\ |& a \\,S\\, b \\,S\\, c \\,S\\, \\ |& b \\,S\\, b \\,S\\, b \\,S\\, c \\,S\\, c \\,S\\, \\ |& b \\,S\\, a \\,S\\, c \\,S\\, \\ |& \ldots & \text{(all permutations of \\(a,b,c\\) above)} \\ \end{align\*}$$

This approach generalizes to any (one) linear equation between the number of occurrences of various letters.
> 7 votes

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


# Question
Title: Scott-continuous functions: an alternative definition
I'm really struggling with this property:

> Let $X,Y$ be coherence spaces and $f: Cl(X) \rightarrow Cl(Y)$ be a monotone function. $f$ is continuous if and only if $f(\bigcup\_{x\in D} x)=\bigcup\_{x \in D}f(x)$, for all $D \subseteq Cl(X)$ such that $D$ is a directed set.
>
> **Directed set** is defined thus: $D \subseteq $ POSET$ $ is a directed set iff $ \forall x, x' \in D$ $ \exists z \in D $ such $ x \subseteq z$ and $x' \subseteq z$.
> $Cl(X) $stands for cliques of X: $\\{x \subseteq |X| \mid a,b \in x \Rightarrow a$ coherent $b \\}$.

Many books give that as a definition of **Scott-continuous functions**, but unluckly not my teacher. He gave us this definition of continuous:

> $f : Cl(X) \rightarrow Cl(Y)$ is continuous iff it is monotone and $\forall x \in Cl(X), \forall b \in f(x), \exists x\_0 \subseteq\_{fin} x, b \in f(x\_0)$,
> where **monotone** is defined as: $f$ is monotone iff $a \subseteq b \Rightarrow f(a) \subseteq f(b)$

This is the proposed proof I have, but I can't understand the last equation.

**Proof of $f$ continuous implies $f(\bigcup D)=\bigcup f(D)$**:
Let $b \in f(\bigcup D)$. By the definition of continuity, $\exists x\_0 \subset\_{fin} x \mid b \in f(x\_0)$. Note that $x\_0$ is the union of $\\{ x\_i \mid x\_i \in D\\}$.
If $D$ is direct then: $\exists z \in D \mid x\_i \subseteq z$ then $x\_0 \subseteq z$. By the definition of monotony, $f(x\_0)\subseteq f(z)$ so $b \in f(z)$ ***(???)*** $\subseteq \bigcup f(D)$. And even that is true we should show that $\bigcup f(D) = f(\bigcup D)$, not just $\subseteq$.

The proof of the other implication is even worse so I can't write it here... Can you explain to me how the proof can work?

# Answer
The definition of continuity used by your teacher is the nicer one. It tells you pretty concretely what continuity means.

Suppose $b \in f(x)$. That means that given all the information of $x$, possibly an infinite set of tokens (atoms), the function produces some element that has the atomic piece of information $b$. (It could have other information too, but we are not concerned with that at the moment.) Your teacher's definition says that it is not necessary to look at all the infinite information of $x$ in order to produce the output information $b$. Some finite subset of $x$ is enough to produce it.

(Melvin Fitting's book "Computability theory, semantics and logic programming", Oxford, 1987, calls this property *compactness* and defines a continuous function as being monotone and compact.)

This is the *essence* of continuity. To get some finite amount of information about the output of a function, you only need a finite amount of information about the input. The output produced by the function for an infinite input is obtained by piecing together the information it produces for all *finite* approximations of the infinite input. In other words, you don't get any magical jump in going from the finite approximations to their infinite union. Whatever you get at infinity, you should already get at some finite stage.

The standard equation $f(\bigcup\_{x \in D} x) = \bigcup\_{x \in D} f(x)$ is pretty to look at, but it doesn't tell you all the intuition I have explained above. However, mathematically, it is equivalent to your teacher's definition.

To show that $\bigcup\_{x \in D} f(x) \subseteq f(\bigcup\_{x \in D} x)$, it is enough to show that $f(x)$ is included in $f(\bigcup\_{x \in D} x)$, for each $x \in D$. But that follows directly from monotonicity of $f$ because $x \subseteq \bigcup\_{x \in D} x$. So, this is the "easy" direction.

The other direction, proved by your teacher, is the interesting one: $f(\bigcup\_{x \in D} x) \subseteq \bigcup\_{x \in D} f(x)$. To see this, use the intuition I have mentioned above. Any atomic piece of information $b$ in the left hand side comes from some finite approximation of the input: $x\_0 \subseteq\_{fin} \bigcup\_{x \in D} x$. That is, $b \in f(x\_0)$. Since $x\_0$ is finite and it is included in the union of the directed set, there must be something in the directed set that is larger than $x\_0$, perhaps $x\_0$ itself. Call that element $z$. By monotonicity, $f(x\_0) \subseteq f(z)$. So, $b \in f(z)$. Since $z \in D$, $f(z) \subseteq \bigcup\_{x \in D} f(x)$. So, now $b$ is seen to be in the right hand side too. QED.

As you have noted, showing that your teacher's continuity implies the pretty equation is the easy bit. The harder bit is to show that the pretty equation, despite looking like it is not saying very much, really does say everything in your teacher's definition.
> 12 votes

# Answer
It occurred to me belatedly, after I wrote the last response, that the teacher's definition of continuity that I was explaining in my response is the *topological* notion of continuity. The *algebraic* formulation of continuity that is usually mentioned in Computer Science text books hides all the topological intuitions. (In fact, Dana Scott has often written that he has deliberately avoided topological formulations because Computer Scientists are not familiar with it.)

The linkage between the algebraic and topological formulations is called *Stone duality*, and it is now becoming increasingly clear that this linkage itself is extremely important for Computer Science.

For a conceptual exposition of these connections (and a lot more), See Abramsky's Information, processes and games.
> 4 votes

---
Tags: terminology, programming-languages, semantics
---


# Question
Title: Techniques/tools for constructing hard instances of a puzzle game
> Are there techniques and/or software tools that can be used to construct hard instances of a simple puzzle game (or a simple planning problem)?

With "hard" I mean that any solution of the instance is "long" with respect to the input size.

What I have in mind:

* model the puzzle game using a constraint programming language (or even STRIPS);
* the tool starts with assigning some random values to the model parameters to construct an instance;
* solve the instance and if solutions are "easy" (shorter than a fixed length) or no solution is found in a specified amount of time, try to adjust it using some heuristics (or other techniques such as GA or simulated annealing).

# Answer
> 4 votes
As I understand it, the problem you are interested in is **Bounded PlanSAT** which asks whether there is a solution of length $k$ or less. **PlanSAT** on the other hand asks whether there exists *any* plan than solves the problem. **Bounded PlanSAT** is, for example, decidable even if we add function symbols to our language and thus make the number of states infinite. Both of these decision problems are indeed in $\text{PSPACE}$.

As for your problem of generating hard instances (meaning *long* solutions), one approach could be GRAPHPLAN which uses a data structure called the *planning graph*. Now, the planning problem asks if we can reach a goal state $G$ from the initial state $S\_0$. Suppose we are given a tree of all possible actions from the initial state to successor states, and their successors, and so on. Indexed appropriately, we could answer the question of "is $G$ reachable from $S\_0$?" just by looking it up. This is naturally impractical, since the tree is of exponential size. The planning graph is a polynomial-size approximation to this tree that can be constructed quickly.

The planning graph can't answer for sure whether $G$ is reachable from $S\_0$, but it can estimate how many steps it takes to reach $G$. The estimate is always correct when it reports $G$ is not reachable, and it never overestimates the number of steps. Hence it is an admissible heuristic.

I agree this is perhaps not exactly what you are looking for. Nevertheless this way, one does not have to actually solve the instance. I don't think solve time is a particularly useful measure of hardness. For some solvers, some instances are easy. For some solvers, they are hard. In this sense, something like *long* solutions seem like a good measure of hardness.

Another thing that crossed my mind was the fact that classical planning can be represented as a constraint problem (SAT/CSP, see for example SATPLAN). If translated as SAT for example, one can use all the tools available in that domain. You might be interested for example in the question Measuring the difficulty of SAT instances. As for directly generating an instance of planning that has a solution of length more than $k$, I don't know the answer to.

By the way, if you want to solve instances in practice, Helmert (2001) analyzes many classes of planning problems and notes that constraint-based approaches such as GRAPHPLAN and SATPLAN are best for $\text{NP}$-hard domains while search-based approaches do better in domains where feasible solutions can be found without backtracking. Both have problems in domains with many objects because they must create many actions. One can also check out the International Planning Competition (IPC), similar to the SAT competition(s).

---
Tags: algorithms
---


# Question
Title: Master theorem and constants independent of $n$
I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version):

$$T(n)=4T(n/2)+O(r)$$

$r$ is independent of $n$. Case 1 of the Master theorem applies and tells us that $T(n)=O(n^2)$.

However, this hides a constant dependent on $r$ in the big-oh notation: our recurrence has depth $O(\log\_2 n)$ so at the final level we have $O(4^{\log\_2 n})=O(n^2)$ subproblems, each of which takes $O(r)$ time to be handled. This means the actual running time is $O(n^2 r)$ (or worse: this analysis only talks about the lowest level).

This is my actual recursion:

$$T(n)=r^2T(n/r)+O(nr^2)$$

Is there a method similar to the Master theorem for these kinds of recursions?

# Answer
> 7 votes
Use a recursion tree (otherwise known as the *proof* of the Master Theorem). I'll assume here that $r\>1$, since otherwise the recurrence never bottoms out.

* The root of the recursion tree for $T(n)$ has value $nr^2$.
* The root has $r^2$ children, each with value $(n/r)r^2 = nr$. Thus, the total value of all children is $nr^3$.
* Each child has $r^2$ children of its own, each with value $(n/r^2)r^2 = n$. Thus, the total value of all grandchildren of the root is $nr^4$.
* An easy induction argument implies that for any integer $\ell\ge 0$, the root has $r^{2\ell}$ descendants at level $\ell$, each with value $(n/r^\ell)r^2 = nr^{2-\ell}$. Thus, the total value of all nodes at level $\ell$ is $r^{2\ell} \cdot nr^{2-\ell} = nr^{2+\ell}$.
* The level sums $T(n) = nr^2 + nr^3 + \cdots + nr^{2+\ell} + \cdots$ form an *increasing* geometric series, so (for big-Oh purposes) only the *deepest* level matters.
* The recursion reaches its base case when $n/r^\ell = 1$, or equivalently, when $\ell = \log\_r n$.
* The total value of all nodes at that level is $nr^{2+\ell} = nr^{2+\log\_r n} = n^2r^2$.
* We conclude that $T(n) = O(r^2 n^2)$.

These notes describe the recursion tree method in more detail, with *lots* of examples.

Equivalently, define $S(n) = T(n)/r^2$, so that $S(n) = r^2 T(n/r) + n$, and then use the Master theorem to solve for $S(n)$. But that would require remembering the Master theorem, which I don't.

---
Tags: algorithm-analysis, asymptotics, recurrence-relation, mathematical-analysis, master-theorem
---


title: Running time - Linked Lists Polynomial

text:
# Question
Title: Running time - Linked Lists Polynomial
I have developed two algorithms and now they are asking me to find their running time. The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are *addition* and *multiplication*.

In general for lists the running for these two operations are ($x,y$ are the lists lengths):

* Addition: Time $O(x+y)$, space $O(x+y)$
* Multiplication: Time $O(xy \log(xy))$, space $O(xy)$

Can someone help me to find the running times of my algorithms? I think for the first algorithm it is like stated above $O(x+y)$, for the second one I have two nested loops and two lists so it should be $O(xy)$, but why the $O(xy \log(xy))$ above?

These are the algorithms I developed (in Pseudocode):

```
 PolynomialAdd(Poly1, Poly2):
 Degree := MaxDegree(Poly1.head, Poly2.head);
 while (Degree >=0) do:
      Node1 := Poly1.head;
      while (Node1 IS NOT NIL) do:
         if(Node1.Deg = Degree) then break;
         else Node1 = Node1.next;
      Node2 := Poly2.head;
      while (Node2 IS NOT NIL) do:
         if(Node2.Deg = Degree) then break;
         else Node2 = Node2.next;
      if (Node1 IS NOT NIL AND Node2 IS NOT NIL) then
         PolyResult.insertTerm( Node1.Coeff + Node2.Coeff, Node1.Deg);
      else if (Node1 IS NOT NIL) then
         PolyResult.insertTerm(Node1.Coeff, Node1.Deg);
      else if (Node2 IS NOT NIL) then
         PolyResult.insertTerm(Node2.Coeff, Node2.Deg);
      Degree := Degree – 1;
 return PolyResult;

 PolynomialMul(Poly1, Poly2):
 Node1 := Poly1.head;
 while (Node1 IS NOT NIL) do:
      Node2 = Poly2.head;
      while (Node2 IS NOT NIL) do:
           PolyResult.insertTerm(Node1.Coeff * Node2.Coeff,
                              Node1.Deg + Node1.Deg);
           Node2 = Node2.next;
      Node1 = Node1.next;
 return PolyResult;

```

`InsertTerm` inserts the term in the correct place depending on the degree of the term.

```
 InsertTerm(Coeff, Deg):
 NewNode.Coeff := Coeff;
 NewNode.Deg := Deg;
 if List.head = NIL then
    List.head := NewNode;
 else if NewNode.Deg > List.head.Deg then
    NewNode.next := List.head;
    List.head := NewNode;
 else if NewNode.Deg = List.head.Deg then
    AddCoeff(NewNode, List.head);
 else
    Go through the List till find the same Degree and summing up the coefficient OR
    adding a new Term in the right position if Degree not present;

```

# Answer
> 3 votes
The running time of the `InsertTerm` subroutine is $\Theta(n)$ where $n$ is the number of terms in the polynomial, and this is the worst-case complexity as well as the average-case complexity absent any information about the monomial being inserted.

The outer loop of `PolynomialAdd` runs `MaxDegree(Poly1.head, Poly2.head)` times. Inside each iteration, the inner loops search for a node with the right degrees in each polynomial. For terms of degrees that are absent from the monomial, or present near the end of the monomial, the running time of the inner loop is $\Theta(n)$ where $n$ is the number of terms in the respective monomial. The running time of `InsertTerm` has been discussed above; here all I need to know is that its $\Theta(n)$. Hence the running time of `PolynomialAdd` is $\Theta(\max(x,y) \cdot (x + y))$ where $x$ and $y$ are the number of terms in the polynomials `Poly1` and `Poly2` respectively.

The number of calls to `InsertTerm` in `PolynomialMul` is clearly $xy$, since the outer loop always runs $x$ times and the inner loop always runs $y$ times. I assume that `Node1.Deg + Node1.Deg` is a typo and you really meant `Node1.Deg + Node2.Deg`. I won't give a full proof here, but intuitively speaking, this is going back and forth inside the result list, and so on average the time spent in `insertTerm` is about half the length of the list: $\Theta(x+y)$. Therefore the running time of `PolynomialMul` is $\Theta(x\\,y\\,(x+y))$.

It is possible to implement polynomial addition and multiplication with faster running times, but you'll need to improve your code. The core idea is that you waste a lot of time in `InsertTerm`, inserting at random positions in the result list. Instead, arrange to construct the result list in order: first the lowest-degree term at the end of the list, then the previous term, etc. (Alternatively, if you find it easier, construct the list in the other order, starting with the highest-degree term and maintaining a pointer to the `next` pointer in the last node). Furthermore, do not traverse the arguments again on each iteration through the loop: in addition, iterate over the two arguments simultaneously; in multiplication, where you need to combine terms of different degrees, remember where you stopped so you can start again from the same point.

# Answer
> 1 votes
The multiplication algorithm has a characteristic of $O(\log(n))$ because the actual multiply operation can be divided into separate sub problems, "multiply". But, the complexity becomes worse when you have to go through the entire result list again in the "insertTerm" subroutine which is called in the inner while loop of the nested loops. That makes the data count $n^n$ and the complexity becomes $O(\log(n^n))$ which is equivalent to $O(n\log(n))$.

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


# Question
Title: What is the difference between classical crypto and post-quantum crypto?
Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be needed to change?

# Answer
Summary of this paper providing a (partial) answer.

There are two kinds of traditional public-key cryptographic methods: those based on integer factorization, and those based on the discrete logarithm, including elliptic-curve-based methods. These models are believed to be hard in the classical models, but have been shown that neither is hard in the quantum model.

Although Grover developed a quantum algorithm providing quadratic speedup for searching, Bennet, Bernstein, Brassard and Vazirani showed that the quantum model couldn't allow exponential speedup for search problems. This suggests symmetric encryption algorithms, one-way functions and cryptographic hashes should resist quantum-based attacks. The focus, then, should be on developing secure public-key methods.

Lamport signatures may provide a one-time signature mechanism secure against quantum attacks. Lattice problems may form the basis for public-key methods which are resistant to quantum attacks; in particular, the NP-Hard shortest-vector and closest-vector problems are attractive. For both the classical and quantum models, these problems are believed to be hard for lattices of high dimension. The NTRU family of cryptographic algorithms, based on lattice problems, may provide a practical means of achieving public-key cryptography resistant to quantum attacks. Another problem which might serve as a basis for secure public key methods is the syndrome decoding problem. The McEliece encryption system is based on this problem, and variants may provide a way forward.
> 6 votes

# Answer
I'm by no means an expert (or even close to that) on the topic, but from what I know:

Classical cryptography depends on the intractability of factoring (or the discrete log problem). However, factoring is not believed to be NP-complete, and it is indeed solvable in polynomial time by quantum computers. So any cryptography that depends on those operations would break (which is every kind of cryptography used out there that I know of).

Quantum cryptography depends on quantum mechanics, and it's *theoretically impossible* to break it. It's not a matter of time at all -- it's simply based on randomness, and the fact that a state collapses upon being measured, so without the appropriate information, your *best* choice is to simply 'guess' the message... which is useless.
> 0 votes

---
Tags: reference-request, cryptography, quantum-computing
---


title: Reduction rule for IF?

text:
# Question
Title: Reduction rule for IF?
I'm working through Simon Peyton Jones' "The Implementation of Functional Programming Languages" and on page 20 I see:

```
IF TRUE ((λp.p) 3) ↔ IF TRUE 3         (per β red)   (1)
                   ↔ (λx.IF TRUE 3 x)  (per η red)   (2)
                   ↔ (λx.3)                          (3)

```

Step 1 to 2 is explained as η-conversion. But from 2 to 3 it says "The final step is the reduction rule for IF." I'm not sure what this reduction rule is.

# Answer
The reduction rule you ask for is the usual one for IF statements. It consists of two computation rules and one context rule:

> * $\text{IF TRUE}$ $a$ $b$ $\to$ $a$
> * $\text{IF FALSE}$ $a$ $b$ $\to$ $b$
> * $\dfrac{a\to a'}{\text{IF}~a\ b\ c\to \text{IF}~a'\ b\ c}$

In both the call-by-value (strict) and call-by-need (lazy) settings, both $a$ and $b$ can be arbitrary expressions. They need not be values.

Rules of this kind, that reduce specific functions (here `IF`), are often called delta rules.

Now, the reason step (2) above is necessary is so that the reduction rules for $\text{IF}$ can apply. $\text{IF}$ requires 3 arguments, but in the original term it has only two, so cannot be reduced. ($\text{IF}$ is being partially applied, just like any function in Haskell. This means that only part of its arguments need to be supplied.) The use of $\eta$-expansion provides the additional argument, without changing the semantics.
> 10 votes

---
Tags: logic, programming-languages, lambda-calculus, term-rewriting, operational-semantics
---


# Question
Title: Example of Soundness & Completeness of Inference
Is the following example correct about whether an *inference* algorithm is *sound* and *complete*?

Suppose we have needles a, b, c in a haystack, and have also an inference algorithm that is designed to find needles.

* *sound* \- Only needles a, b and c are obtained.
* *complete* \- Needles a, b and c are obtained. Other hay may also be obtained.

# Answer
You have almost got it right, but your definition of soundness is not quite right, *or perhaps too subtle.*

I would say that the inference algorithm is sound if *everything returned is a needle* (hence some needles may be missed) and complete if *all needles are returned* (hence some hay may be returned too).
> 11 votes

---
Tags: logic
---


# Question
Title: Restricted version of the Clique problem?
Consider the following version of the Clique problem where the input is of size $n$ and we're asked to find a clique of size $k$. The restriction is that the decision procedure cannot change the input graph into any other representation and cannot use any other representation to compute its answer, other than $\log(n^k)$ extra bits beyond the input graph. The extra bits can be used for example in the brute-force algorithm to keep track of the status of the exhaustive search for a clique, but the decision procedure is welcome to use them in any other way that still decides the problem.

Is anything known at this point about the complexity of this? Has any work been done on other restrictions of Clique, and if so, could you direct me to such work?

# Answer
This sounds like you are asking whether or not the NP-complete clique problem can be solved in logarithmic space. Using Turing machines, one tape is read only and stores the input graph. The other tape is bounded so that there's $c \lg n$ space available for some constant $c$. The class of problems solvable in this model is known as $L$, deterministic logarithmic space. (See wikipedia or in the complexity zoo)

It is unknown whether $\mathrm{CLIQUE} \in L$, but a positive answer would imply that $P = NP$, so you (almost surely?) won't find an answer. $L \subseteq P \subseteq NP$ and $\mathrm{CLIQUE} \in L$ implies $\mathrm{CLIQUE} \in P$, which implies $P = NP$.

---

*Edit in case I misinterpreted the problem:*

If you intend that the $k$ in $ \lg n^k = k \lg n $ is the same as the clique size $k$ (i.e. the amount of memory scales with input $k$), then there's a simple brute force algorithm: you can loop through all possible sets of $k$ nodes and check if they form a $k$-clique. A starting point for searching for better solutions might be the references of \[1\].

---

\[1\] Virginia Vassilevska, "Efficient algorithms for clique problems" pdf link
> 5 votes

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


# Question
Title: Can a program language be malleable enough to allow programs to extend language semantics
With reference to features in languages like ruby (and javascript), which allow a programmer to extend/override classes any time after defining it (including classes like String), is it theoretically feasible to design a language which can allow programs to later on extend its semantics.

ex: Ruby does not allow multiple inheritance, yet can I extend/override the default language behaviour to allow an implementation of multiple inheritance.

Are there any other languages which allow this? Is this actually a subject of concern for language designers? Looking at the choice of using ruby for building rails framework for web application development, such languages may be very powerful to allow designing frameworks(or DSLs) for wide variety of applications.

# Answer
Converge has some pretty impressive meta-programming facilities.

> At a simple level, this can be seen as a macro-like facility, although it is more powerful than most existing macro facilities as arbitrary code can be run at compile-time. Using this, one can interact with the compiler, and generate code safely and easily as ITrees (a.k.a. abstract syntax trees).

which is a step up from Scheme's hygienic macros that allow referentially transparent macro definitions.

Mechanisms like quasiliterals have allowed constructing and destructuring of parse trees in other languages, but those are more often used for interacting with domain-specific languages (DSLs) instead of self-modification.

---

Newspeak's reflection allow exceptions to be implemented as library code.

> ## 7.6 Exception Handling
>
> Because Newspeak provides reflective access (7.2) to the activation records(3.6), exception handling is purely a library issue. The platform will provide a standard library that supports throwing, catching and resuming exceptions, much as in Smalltalk.

---

Perligata:Romana demonstrates how an entirely new syntax can be skinned onto a language.

> This paper describes a Perl module -- Lingua::Romana::Perligata -- that makes it possible to write Perl programs in Latin.

---

Arguably not semantically significant, PyPy is an interpreter generator for languages whose semantics are specified in a highly statically-analyzable subset of Python, and they use it to experiment with new language constructs in Python like adding thunks to the language.

---

Also of interest might be Ometa.

> This dissertation focuses on experimentation in computer science. In particular, I will show that new programming languages and constructs designed specifically to support experimentation can substantially simplify the jobs of researchers and programmers alike.
>
> I present work that addresses two very different kinds of experimentation. The ﬁrst aims to help programming language researchers experiment with their ideas, by making it easier for them to prototype new programming languages and extensions to existing languages. The other investigates experimentation as a programming paradigm, by enabling programs themselves to experiment with different actions and possibilities— in other words, it is an attempt to provide language support for what if...? or possible worlds reasoning.

Alex Warth's dissertation demonstrates using an Ometa to define significantly new semantics (transactional semantics via worlds) in JavaScript+Ometa.
> 13 votes

# Answer
"Is it theoretically feasible?\*

Of course, it is. One can always write an interpreter in a language ($L$) for another language ($S$), and write programs in the new language. People do not often do this because it might involve a lot of work to write such an interpreter and there will be a performance hit (a factor of 10-100) for the additional layer of interpretation.

Both the problems have solutions. The language $L$ can be designed with powerful metaprogramming facilities so that it is easy to implement interpreters. Languages like Scheme have this.

One can implement a partial evaluator so that the interpreter can be turned into a compiler (from $S$ to $L$). Then you don't get the performance hit because the additional interpretation layer is eliminated.

The new language might still run slowly if its run-time model is significantly different from the implementation language. In that case, bits of the interpreter will show up in the translated code and it will continue to run slow. However, if the new language is mostly the same as the original language, with only a few tweaks, then it should be possible to eliminate most of the interpreter bits in the target code by careful tuning of partial evaluation. Then the performance hit will be there for only the new features.

In effect, this is the "virtualization" technology for programming languages.
> 8 votes

# Answer
Historically, Lisp was the first major programming language to introduce metaprogramming facilities. Lisp's macro system allows the programmer to define new control structures, new data templates, etc. For example, the Common Lisp Object System can be defined entirely with macros above a core language that knows nothing about objects or classes. The macro system also allows the definition of domain-specific languages.

Ruby got a lot of inspiration from Lisp, including its capacity for reflectivity and metaprogramming. A lot of dynamically-typed languages have taken inspiration from Lisp in this respect. (Static typing complicates things, because many extensions do not fit in the original type system.)
> 7 votes

# Answer
Not yet mentioned in the answers/comments:

the survey:

**Abstract:** Extensible languages are programming languages which allow a user to modify or add syntax, and associate the new syntactic forms with semantics. What are these languages good for? What kinds of features are easy to add, and which are not? Are they powerful enough to be taken seriously? In this survey we will attempt to answer such questions as we consider procedural, object-oriented, functional, and general-purpose extensible languages. We are primarily interested in expressive power (regular, context-free), associated caveats (unhy- gienic, ambiguity) and ease of use of the various mechanisms.

and

**Abstract:** The ability to extend a language with new syntactic forms is a powerful tool. A sufficiently flexible macro system allows programmers to build from a common base towards a language designed specifically for their problem domain. However, macro facilities that are integrated, capable, and at the same time simple enough to be widely used have been limited to the Lisp family of languages to date. In this paper we introduce a macro facility, called the Java Syntactic Extender (JSE), with the superior power and ease of use of Lisp macro systems, but for Java, a language with a more conventional algebraic syntax. ...
> 4 votes

---
Tags: programming-languages, semantics
---


# Question
Title: How Do Common Pathfinding Algorithms Compare To Human Process
This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A\*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar?

# Answer
> 6 votes
Humans tend to choose not strictly optimal, but close to shortest solutions. So you'll need to look at fuzzy (approximate) algorithms, not at A\*.

The closest algorithm to human thinking I've aware of is a *Contaction hierarchies* on par with a *Reach* pruning algorithm. When I need to find a path between A and B on the map, I do a quick overview, taking into account if there is crossing river or something else and looking for some general ways and then adding details that could shorten path.

# Answer
> 4 votes
Here you are a number of considerations. The first two are taken from the **wonderful** PhD by Andreas Junghanns (now back to Industry in Berlin, Germany and happy to count him among my friends :) ):

**Breadth-First Search**: If you are just standing in front of a furniture and something valuable (say a coin, or a ring) falls and goes beneath the furniture, so that you cannot see it, then you wave your hand slightly starting from the point where you saw the object dissapearing. If you do not find it you go a little bit further and proceed this way until either you find it or you loose your patience. That is exactly **breadth-first search** in action: first, you consider all the unknown locations at depth 1, then at depth 2 and so on.

**Depth-First Search**: when looking for something that is remotely located to your surroundings you never choose the aforementioned algorithm and instead you commit to a direction. An example is Cristobal Colon committing to the west when seeking a route to the Indians. Well, he was wrong but we know that nowadays. Imagine Colon trying a breadth-first search and moving along a spiral from Burgos where the contract between the Reyes Católicos and Colon was signed. Instead he pointed to a given direction without ever backtracking.

Another example from one of my professors at the University (José Cuena, who already passed away) regards **bidirectional search**: engineers, when building tunnels in mountains start from both ends simultaneously and end when they meet somewhere in the middle. The reason is simple, if they start just from one end it is very likely that there will be a huge deviation in the other end. Starting from both ends simultaneously minimizes the deviation in the meeting point.

Now, even in the case of A$^\*$ let me recall the same considerations I make to my students:

* The *open list* is just the list of open possibilities awaiting to be considered. All humans do this though we are not as good as computers remembering things.
* The *closed list* just serves to avoid circular reasoning or continuing reasoning from a point that we already considered before. This happens if you are reasoning at loud voice and you repeat something. Then, someone will realize and will immediately tell you "hey man, you already said that before"

A very interesting question somehow addressed by others is whether humans can run any algorithm and (even more interesting from my point of view) whether these algorithms (or, in general, the way we build Artificial Intelligence) mimic our natural intelligent procedures.

# Answer
> -2 votes
Have you watched a child learning to navigate a room? You have to tell them, "Go around the table. *AROUND*".

Human path planning is a grab bag of heuristics, some innate and some learned. Lookahead is probably fixed to a small number, certainly not a general recursion like A\*.

---
Tags: algorithms, graphs, artificial-intelligence
---


title: Shortest Path on an Undirected Graph?

text:
# Question
Title: Shortest Path on an Undirected Graph?
So I thought this (though somewhat basic) question belonged here:

Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving through the graph involves moving three spaces forward and one space to either right or left (similar to how a chess knight moves across a board).

Given a fixed beginning node, how would one find the shortest path to any other node on the board?

I imagined that there would only be an edge between nodes that are viable moves. So, given this information, I would want to find the shortest path from a starting node to an ending node.

My initial thought was that each edge is weighted with weight 1. However, the graph is undirected, so Djikstras would not be an ideal fit. Therefore, I decided to do it using an altered form of a depth first search.

However, I couldn't for the life of me visualize how to get the shortest path using the search.

Another thing I tried was putting the graph in tree form with the starting node as the root, and then selecting the shallowest (lowest row number) result that gave me the desired end node... this worked, but was incredibly inefficient, and thus would not work for a larger graph.

Does anyone have any ideas that might point me in the right direction on this one?

Thank you very much.

(I tried to put in a visualization of the graph, but was unable to due to my low reputation)

# Answer
If the edges in the graph only represent valid moves between certain positions, using Dijkstra's would work just fine. However as the graph is unweighted it would be overkill. A simple breadth-first-search will give the optimal answer.
> 19 votes

# Answer
Nicholas already provided a perfect answer. However, let me address your original attempt to use depth-first search.

First, either Dijkstra (which works fine with unweighted nodes as noted by Nicholas Mancuso) or breadth-first search incur in exponential waste of your memory. Their advantage, however, is that they never re-expand any nodes while they are guaranteed to find optimal solutions. Unfortunately, their limitation is quite important and they should not be expected to scale up reasonably.

If you want to solve large instances of your problem use **Iterative-Deepening Depth-First** search (IDFS). Just issue a depth-first search from your start state with a maximum depth set to a specific threshold, $d\_{max}$. If you have not found the solution, then increment the depth of the last iteration by a fixed constant $k$. Thus, in the $i$-th iteration, a depth-first search is launched at depth $d\_{max} + i\times k$ (with the first iteration being numbered 0). If $d\_{max}=k=1$ then you are guaranteed to find the optimal solution while using memory linear in the depth of the solution.

Well, you might be thinking that re-expanding nodes is a rather bad idea. Not at all! This is what guarantees a linear consumption of memory while the iteration dominating the overall running time is just the last one so that it can be proven that this algorithm incurs in an overhead of $\frac{b}{b-1}$ with $b$ being the effective branching factor, and this is clearly a very small penalty worth taking into account when facing hard problems.

Cheers,
> 13 votes

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


# Question
Title: Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?
How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.

$A(L)= \\{ w\_1w\_2: |w\_1|=|w\_2|$ and $w\_1, w\_2^R \in L \\}$, where $x^R$ is the reversed form of $x$.

I understand that since $L$ is regular so does $L^R$.also on my way for a CFG I can reach $w\_1$ by the CFG of $L$ concatenation with the one of $L^R$ for making $w\_2$. so far I have a CFG, but what promises me that $|w\_1|=|w\_2|$? how can I generate a grammar that will also keep that in addition to the other conditions?

# Answer
You can show that it is decided by a PDA.

Check if the input string up to $i$th symbol is in $L$ while pushing them to the stack. Then check if the rest of the string is also in $L^R$ while poping one symbol from the stack for each symbol you read. (Note that if $L$ is a regular language so is $L^R$ and memberships in $L$ and $L^R$ can be checked without by DFAs, i.e. no stack is needed for that part.)

You can guess $i$ nondeterministically.
> 7 votes

# Answer
Let $A'(L)= \\{ w\_1 \sharp w\_2: |w\_1|=|w\_2|$ and $w\_1, w\_2^R \in L \\}$ where $\sharp$ is a new symbol.

$A'(L)$ is the intersection of context-free language $\\{ w\_1 \sharp w\_2: |w\_1|=|w\_2|\\}$ and regular $L\sharp L^R$, therefore it is context-free. $A(L)$ is a homomorphic image of $A'(L)$, so it is context-free as well.

I prefer this proof to others as it is "higher-level".
> 8 votes

# Answer
You can prove it's context-free by providing a PDA that accepts it (and proving the PDA works, typically by construction).

A PDA could work as follows. Read symbols and count them using the stack. Nondeterministically determine when you've read half the symbols. If what you've seen so far isn't in the regular language, crash or otherwise reject. Otherwise, read the same number of symbols you previously read. If what you read the second time around is in the reverse of the regular language, accept. To formally produce the machine construction, you just need DFAs for the language and its reverse, a way to connect them, and a way to count using a stack.
> 5 votes

# Answer
As $L$ is regular, it is generated by a right-linear grammar for which all rules have the form $A \to aB$, $A \to a$ or $A \to \varepsilon$ (showing this is an easy exercise). So without loss of generality, we assume that $G=(N,T,\delta,S)$ with $\mathcal{L}(G)=L$ has this form.

Now we construct a new grammar that generates $A(L)$. The idea is to "execute" the grammar two times in parallel; because every rule generates at most one terminal, we can achieve the $|w\_1|=|w\_2|$ requirement. As for $w\_2^R \in L$, that should be easy to transfer from the proof that $\mathrm{REG}$ is closed against reversal (if done via grammars).

> Formally, we construct $G'=(N',T,\delta', (S,S))$ with
> * $N' = N \times N$
> * $\delta'$ is defined by
> $\quad$ - $(A\_1,A\_2) \to\_{\delta'} a\_1(B\_1,B\_2)a\_2 \quad \Longleftrightarrow \quad A\_1 \to\_\delta a\_1B\_1 \wedge A\_2 \to\_\delta a\_2B\_2$,
> $\quad$ - $(A\_1,A\_2) \to\_{\delta'} a\_1a\_2 \quad \Longleftrightarrow \quad A\_1 \to\_\delta a\_1 \wedge A\_2 \to\_\delta a\_2$,
> $\quad$ - $(A\_1,A\_2) \to\_{\delta'} \varepsilon \quad \Longleftrightarrow \quad A\_1 \to\_\delta \varepsilon \wedge A\_2 \to\_\delta \varepsilon$
> Proof of correctness works via induction over word length resp. number of derivation steps.
> 3 votes

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


# Question
Title: Maximise sum of "non-overlapping" numbers in square array - help with proof
A question was posted on Stack Overflow asking for an algorithm to solve this problem:

> I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The subset will consist of n elements, where one and only one element is taken from each row and from each column of A. The output should provide a solution (B) such that the sum of the elements that make up B is the maximum possible value, given these constraints (eg. 25 in the example below). If multiple instances of B are found (ie. different solutions which give the same maximum sum) the solution for B which has the largest minimum element should be selected.
>
> B could also be a selection matrix which is nxn, but where only the n desired elements are non-zero.
>
> For example: if A =
>
> ```
> |5 4 3 2 1|
> |4 3 2 1 5|
> |3 2 1 5 4|
> |2 1 5 4 3|
> |1 5 4 3 2|
>
> ```
>
> =\> B would be
>
> ```
>  |5 5 5 5 5|
>
> ```

I proposed a dynamic programming solution which I suspect is as efficient as any solution is going to get. I've copy-pasted my proposed algorithm below.

---

* Let $A$ be a square array of $n$ by $n$ numbers.
* Let $A\_{i,j}$ denote the element of $A$ in the `i`th row and `j`th column.
* Let $S( i\_1:i\_2, j\_1:j\_2 )$ denote the optimal sum of non-overlapping numbers for a square subarray of $A$ containing the intersection of rows $i\_1$ to $i\_2$ and columns $j\_1$ to $j\_2$.

Then the optimal sum of non-overlapping numbers is denoted `S( 1:n , 1:n )` and is given as follows:

$$S( 1:n , 1:n ) = \max \left \\{ \begin{array}{l} S( 2:n , 2:n ) + A\_{1,1} \\ S( 2:n , 1:n-1 ) + A\_{1,n} \\ S( 1:n-1 , 2:n ) + A\_{n,1} \\ S( 1:n-1 , 1:n-1 ) + A\_{n,n} \\ \end{array} \right.$$

```
Note that S( i:i, j:j ) is simply Aij.

```

That is, the optimal sum for a square array of size `n` can be determined by separately computing the optimal sum for each of the four sub-arrays of size `n-1`, and then maximising the sum of the sub-array and the element that was "left out".

```
S for |# # # #|
      |# # # #|
      |# # # #|
      |# # # #|

Is the best of the sums S for:

|#      |      |      #|      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |      #|       |#      |

```

---

This is a very elegant algorithm and I strongly suspect that it is correct, but I can't come up with a way to **prove** it is correct.

The main difficulty I am having it proving that the problem displays optimal substructure. I believe that if the four potential choices in each calculation are the *only* four choices, then this is enough to show optimal substructure. That is, I need to prove that this:

```
|   #    |
| #   # #|
| #   # #|
| #   # #|

```

Is not a valid solution, either because it's impossible (i.e. proof by contradiction) or because this possibility is already accounted for by one of the four "`n-1` square" variations.

Can anyone point out any flaws in my algorithm, or provide a proof that it really does work?

# Answer
Actually, I don't believe your proposed solution is correct. An example where you might need this case

```
|   #    |
| #   # #|
| #   # #|
| #   # #|

```

might be

```
| 1 2 1 1|
| 2 1 1 1|
| 1 1 1 2|
| 1 1 2 1|

```

The optimal solution consists of all 2s, while there are only 1s in the corners; therefore, you cannot find an optimal solution just by starting at the corners.
> 7 votes

# Answer
This problem can be solved by maximum matching algorithm in weighted bipartite graph, such as Kuhn-Munkres algorithm or minimum cost flow algorithm.

Imagine a bipartite graph $G$, whose two disjoint point sets are $A$ and $B$. Each vertex $a\_i \in A$ corresponds to a row, and each vertex $b\_j \in B$ corresponds to a column. The weight of edge $E\_{i,j}$ between $a\_i$ and $b\_j$ is $M\_{i, j}$, the $j$-th element of $i$-th row of the matrix. The weighted max matching of this graph corresponds to a solution to your problem.

To break the tie, you have to find the value of max weighted matching at first. Let the value be $W\_{max}$. Then you should sort all the elements in matrix $M$ and make a binary search on it. When testing the value $m$, i.e., whether there is a max matching whose minimum element is no less than $m$, you should modify all $M\_{i, j}$ to $-\infty$ if $M\_{i, j} \< m$ and find the max matching $W\_{max}'$ in the modified matrix $M'$. $W\_{max}' = W\_{max}$ iff there is a solution whose min elements in no less than $m$.
> 5 votes

---
Tags: algorithms, dynamic-programming, check-my-algorithm
---


# Question
Title: All soldiers should shoot at the same time
When I was a student, I saw a problem in a digital systems/logic design textbook, about N soldiers standing in a row, and want to shoot at the same time. A more difficult version of the problem was that the soldiers stand in a general network instead of a row. I am sure this is a classical problem, but I cannot remember its name. Can you remind me?

# Answer
The problem is known as Firing squad synchronization problem. The problem itself, is strictly related to *finite state automata*. Here, each soldier is a finite automaton; you know that the next state of each soldier depends on its current state and the current states of its two neighbors (except for the first and last soldier). The first soldier in this setting can be though of as the soldiers general who is in charge of starting the attack. The last soldier knows it is the last one. No global communication is available; however, a global clock can be used to synchronize the state transitions of the soldiers. The problem require designing a soldier automaton whose goal is for all soldiers to enter the "SHOOT" state on exactly the same clock tick. By the way, the problem can be solved in $\Theta(n)$ time for $n$ soldiers.
> 21 votes

---
Tags: algorithms, distributed-systems, clocks
---


# Question
Title: Mapping Reductions to Complement of A$_{TM}$
I have a general question about mapping reductions. I have seen several examples of reducing functions to $A\_{TM}$

where $A\_{TM} = \\{\langle M, w \rangle : \text{ For } M \text{ is a turing machine which accepts string } w\\}$

which is great for proving undecidability. But say I want to prove unrecognizability instead. That is, I want to use the corollary that given $A \le\_{m} B$, if $A$ is unrecognizable then $B$ is unrecognizable.

So for any arbitrary unrecognizable language $C$ which can be reduced to $\overline{A\_{TM}}$ (any example language would suffice for sake of example), how can I reduce $\overline{A\_{TM}} \le\_{m} C$?

For simplicity, suffice to merely consider TM in $\overline{A\_{TM}}$.

**EDIT**

For clarification, $\overline{A\_{TM}} = \\{ \langle M, w \rangle : M \text{ is a turing machine which does not accept string } w \\}$

# Answer
Let's take $L\_{\emptyset}=\\{ \langle M \rangle \mid L(M) = \emptyset \\}$, that is, all the machines that accept no word (i.e., whose language is empty).

Now we show the reduction $\overline{A\_{TM}} \le L\_\emptyset$. The reduction is done by taking an input $(\langle M \rangle,w)$ of $\overline{A\_{TM}}$ and converting it into an input ${\langle \tilde M \rangle}$ for $L\_\emptyset$ such that

$$(\langle M \rangle,w) \in \overline{A\_{TM}} \quad\text{ iff }\quad \langle \tilde M \rangle \in L\_{\emptyset}$$

Given $(\langle M \rangle,w)$ we can construct $\tilde M$ in th following way. $\tilde M$ on input y does the following:

1. deletes the tape
2. writes $w$ on the tape
3. runs $M$ on $w$, and performs the same (if $M$ accepts, $\tilde M$ accepts as well).

Convince yourself it is possible to construct the coding of $\tilde M$ from the coding of $M$ and from $w$. Now let's verify that this reduction is valid:

* If $(\langle M \rangle,w) \in \overline{A\_{TM}}$ then $M$ either rejects or doesn't halt. If so, then also $\tilde M$ doesn't accept $y$, for any input $y$. This means $L(\tilde M) = \emptyset$ thus $\langle \tilde M \rangle \in L\_{\emptyset}$.
* If $(\langle M \rangle,w) \notin \overline{A\_{TM}}$ then $M$ accepts $w$, thus $\tilde M$ accepts $y$ (for every $y$). It follows that $L(\tilde M)=\Sigma^\*$ which implies that $\langle \tilde M \rangle \notin L\_{\emptyset}$.

The "iff" condition holds and we successfully mapped an input of $\overline{A\_{TM}}$ into an input of $L\_\emptyset$. In this case we say we reduced $\overline{A\_{TM}}$ to $L\_\emptyset$. That is, if we can solve $L\_\emptyset$, we can also solve $\overline{A\_{TM}}$ by first converting the input and then running the algorithm that solves $L\_\emptyset$ on the converted input.
> 10 votes

# Answer
You cannot show, for an arbitrary unrecognizable language $C$, that $\overline{A\_{TM}} \leq\_m C$. If $\overline{A\_{TM}} \leq\_m C$ then in particular the Turing degree of $C$ is greater than or equal to the Turing degree of $\overline{A\_{TM}}$, because many-one reducibility implies Turing reducibility. The Turing degree of $\overline{A\_{TM}}$ is $0'$, the same as the Turing degree of $A\_{TM}$. There are plenty of unrecognizable languages whose Turing degree is incomparable with $0'$ (neither greater nor less than $0'$).

The example that Ran G. gave works because $L\_\emptyset$ in particular is $m$-equivalent to $\overline{A\_{TM}}$. There is a general phenomenon that most "natural" problems tend to be comparable with each other in $m$-degree. But if you look at arbitrary problems this is no longer true.
> 6 votes

---
Tags: computability, proof-techniques, reductions
---