# Question
Title: Showing that the set of TMs which visit the starting state twice on the empty input is undecidable
I'm trying to prove that

$L\_1=\\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q\_0 \text{ at least twice on } \varepsilon\\} \notin R$.

I'm not sure whether to reduce the halting problem to it or not. I tried to construct a new machine $M'$ for $(\langle M \rangle,w)$, such that $M'$ visits $q\_0$ twice, iff $M$ halts on $w$. This is specific $q\_0$ given to me, but I didn't come to any smart construction, which would yield the requested. Maybe it's easier to show that it's $RE$ and not $coRE$? It is obvious that it's in $RE$, and I need to show that $L\_2^{c}$ is not in $RE$.

What should I do?

# Answer
Don't make this more complicated than it is. Instead of giving you a full solutions, I will give you a partial solution, which should allow you to work out the details by yourself:

Every TM be turned into a TM that visits its initial state exactly once. To do so, introduce a new state $q^'\_0$, which will be the new start state. Then add a $\varepsilon$-transition from $q^'\_0$ to $q\_0$. This is the only way to "leave" the state $q'\_0$.

For this modified machine, a accepting run visits the initial state once, and ends in the accepting state. What is left to do is to modify the machine further, such that it jumps back to $q^'\_0$, after the machine was in the accepting state. But you have to assure that when $q^'\_0$ is visited the second time, you will jump to a new accepting state. But it's not difficult to record how often you visited a state.

If you want that another state is visited twice, then you can always made a detour in the beginning that visits this state (you record that the machine is in "detour" mode be writing a flag on a special tape). Than you reroute the normal computation, such that if it should visit the requested state it visits a copy of this state. Finally, when accepting, you jump back to the requested state. Conceptually, this is not very different to relabeling the states.
> 1 votes

---
Tags: turing-machines, reductions, undecidability, halting-problem
---


# Question
Title: How to implement simulation on two LTSs?
Does any one know how to implement the simulation relation on two labelled transition systems (LTS)?

I know how to do it for branching bi-simulation. The signature refinement theorem is used for that purpose which has the time complexity of $O(n^3)$ on cyclic LTSs. Is the signature refinement technique useful for simulation also?

Is there any binary relation called branching simulation? Any idea how to implement it?

What I would like to do is to write a program such that:

* Input: Given two labelled transition systems with silent steps
* Output1: Does one simulates the other one?
* Output2: Are they bisimilar?
* Output3: Are they branching bisimilar?
* Output4: Does one branching simulate the other one?

The following illustrates the definitions of the above relations:

1. simulate: An LTS ($L\_1$) simulates another LTS ($L\_2$) if there exists a binary relation $R$ over the states of the two transition systems such that every transition of $L\_2$ can be matched by a transition of $L\_1$. Note that simulation is not an equivalence relation.
2. bisimilar: An LTS ($L\_1$) and an LTS ($L\_2$) are said to be bisimular if there exists a relation $R$ between the states of these transition systems such that both $R$ and $R^{-1}$ are simulations. Note that bisimularity is an equivalence relation.
3. branching bisimilarity: is same as bisimilarity but transition systems may have silent steps. Those silent steps ($\tau$ actions) that do not change the behavior of the process are eliminated. Note that branching bisimilarity is an equivalence relation.
4. branching similarity: I actually have never seen the definition of branching similarity in any context, but it should be the same as similarity. However, the transition systems may have the silent steps.

The paper Distributed Branching Bisimulation Reduction of State Spaces by S. Blom and S. Orzan explains an algorithm to reduce the size of an LTS with respect to branching bisimilarity. The signature refinement theorem is used for that purpose. How it works is roughly as follows:

the algorithm starts by constructing a partition (a set of blocks) of states and terminates once the partition is stable. In a stable partition, two states are branching bisimilar if they belong to the same block.

The above algorithm can also be used to verify whether two LTSs are branching bisimilar or bisimilar. How it works is as follows:

Let LTS, $L\_3 = L\_1 \cup L\_2$, then if after branching reduction, using the above algorithm, the initial states of $L\_1$ and $L\_2$ both belong to the same block then they are branching bisimular. The above algorithm has time complexity $O(n^3)$ and space complexity $O(n^2)$.

Question: How can I do the same with branching simulate and simulate relations?

# Answer
> 3 votes
If you have doubts about whether a certain type of relation exists, a good place to search is Rob van Glabbeek's extensive catalogue of such relations. That article is a bit dated by now, but still extremely comprehensive.

There are several papers on the algorithmic aspect. I would suggest the one below.

This paper provides a design-pattern for implementing partition-refinement style algorithms for checking bisimulation and simulation. The later sections of the paper are quite algorithmic. You could contact the authors and ask about their implementation.

You asked about branching and not stuttering, but I think the contents of the above paper are very related to what you want.

There are some implementations that may help your study.

1. The Edinburgh Concurrency Workbench
2. The Concurrency Workbench of the New Century
3. Concurrency Workbench, Aalborg Edition

All the tools above implement checking equivalences of processes with respect to preorders; the third one is more recent and is also offered online.

---
Tags: automata, formal-methods, process-algebras
---


# Question
Title: Micro-optimisation for edit distance computation: is it valid?
On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:

```
if s[i] = t[j] then
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

```

As you can see, the algorithm *always* chooses the value from the upper-left neighbour if there is a match, saving some memory accesses, ALU operations and comparisons.

However, deletion (or insertion) may result in a *smaller* value, thus the algorithm is locally incorrect, i.e. it breaks with the optimality criterion. But maybe the mistake does not change the end result -- it might be cancelled out.

Is this micro-optimisation valid, and why (not)?

# Answer
> 6 votes
I don't think that the algorithm is flawed. If two strings are matched, we compare first its last two characters (and then recurse). If they are the same, we can match them to get an optimal alignment. For example, consider the strings `test` and `testat`. If you don't match the two last `t`s, than one of the `t`s remains unmatched, since otherwise your matching would look like this:

This is impossible, since the arrows are not allowed to "cross". The matched `t` induces several inserts (green boxes in the figure), as depicted on the left:

But then you can simply find an equally good alignment, depicted on the right. In both cases you match a `t` and you have two inserts.

The argument for a substitution of one of the last `t`s is the same. So if you substitute one of the last `t`s, then you can instead match the last two t, and get a better alignment (see the picture).

---
Tags: algorithms, dynamic-programming, string-metrics, correctness-proof, program-optimization
---


title: Time complexity formula of nested loops

text:
# Question
Title: Time complexity formula of nested loops
I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.

```
int length = input.length();
for (int i = 0; i < length - 1; i++) {
    for (int j = i + 1; j < length; j++) {
        System.out.println(input.substring(i,j));
    }
}

```

"In each iteration, the outer loop executes $\frac{n^{2}-(2i-1)n-i+i^{2}}{2}$ operations from the inner loop for $i = 0, \ldots, n-1$."

Can someone please explain this to me step by step?

I believe the formula above was obtained by using Gauss' formula for adding numbers... I think...

# Answer
Your intuition is correct, the work is in identifying the things you're adding together.

The first bit is that printing a string of length $m$ takes $m$ operations, so the

```
System.out.println(input.substring(i,j));
```

line takes $j-i$ operations. (A side note here is that this code is in Java, unless I'm very much mistaken, and the `substring(start, end)` method gives the substring beginning at index `start` and ending at `end-1`)

So then at each iteration of the outer loop, we're printing a bunch of substrings, starting with a string of length one (just the character at index $i$) and ending with the substring that starts at $i$ and goes to the end of the string `input`.

To put that a dash more mathematically we're printing strings of length $1, 2, \ldots, n-i$. As the number of operations required to print a string is the same as its length, we're doing $\sum\_{k=1}^{n-i}k$ operations. Substituting Gauss's formula for this sum, we get that the number of operations is equal to: $$ \frac{(n-i)(n-i+1)}{2} $$

Then multiplying everything out gives the formula you have in your slides.
> 4 votes

# Answer
Let's work from the outside in.

```
for (int i = 0; i < length - 1; i++) {

```

Clearly, this loop is executed $n = \mathtt{length}-1$ times, so we get $\sum\_{i=0}^{n-1} \dots$ where $\dots$ stands for the time needed by the loop's body (for iteration $i$). Inside, we have

```
for (int j = i + 1; j < length; j++) {

```

which we can translate similarly, obtaining $\sum\_{i=0}^{n-1} \sum\_{j = i+1}^{n} \dots$. Last but not least, the innermost operation

```
    System.out.println(input.substring(i,j));

```

is apparently assumed to take $j-i$ steps (one operation per character).

Putting everything together, we get

$\qquad \begin{align} T(n) &= \sum\_{i=0}^{n-1} \sum\_{j = i+1}^{n} j - i \\ &= \sum\_{i=0}^{n-1} \left\[\left(\sum\_{j = i+1}^{n} j\right) - (n-i)i\right\] \\ &= \sum\_{i=0}^{n-1} \left\[\left(\sum\_{j = 1}^{n} j - \sum\_{j = 1}^{i} j\right) - (n-i)i\right\] \\ &= \sum\_{i=0}^{n-1} \left\[\left(\frac{n(n+1)}{2} - \frac{i(i+1)}{2}\right) - (n-i)i\right\] \\ &= \sum\_{i=0}^{n-1} \left\[ \frac{n^2 - (2i - 1)n + i^2 - i}{2}\right\] \end{align}$

The term in brackets is what you are looking for.

The whole sum can be evaluated using Gauss' formula and its sibling for summand $i^2$:

$\qquad \begin{align} 2T(n) &= \sum\_{i=0}^{n-1} n^2 - \sum\_{i=0}^{n-1} 2in + \sum\_{i=0}^{n-1} n + \sum\_{i=0}^{n-1} i^2 - \sum\_{i=0}^{n-1} i \\ &= n^3 - 2n \cdot \sum\_{i=0}^{n-1} i + n^2 + \sum\_{i=0}^{n-1} i^2 - \sum\_{i=0}^{n-1} i \\ &= n^3 - n^2(n-1) + n^2 + \frac{(n-1)n(2n - 1)}{6} - \frac{n(n-1)}{2} \\ &= \frac{12n^2 + 2n^3 - 3n^2 + n - 3n^2 + 3n}{6} \\ &= \frac{2n^3 + 6n^2 + 4n}{6} \end{align}$

which immediately yields

$\qquad \displaystyle T(n) = \frac{n^3 + 3n^2 + 2n}{6}$.
> 3 votes

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


title: Problem with the definition of P

text:
# Question
Title: Problem with the definition of P
In *"Introduction to Algorithms: 3rd Edition"* there is Theorem 34.2, which states

> $P = \\{ L \mid L \text{ is accepted by a polynomial-time algorithm} \\}$

*"Accepted in polynomial-time"* is defined by:

> $L$ is accepted in polynomial time by an algorithm $A$ if it is accepted by $A$ and if in addition there exists a constant $k$ such that for any length-n string $x\in L$, algorithm $A$ accepts $x$ in time $O(n^k)$.

*"Accepted"* is defined by:

> The language accepted by an algorithm $A$ is the set of strings $L = \\{ x \in \\{0,1\\}^\* \mid A(x) = 1 \\}$, that is, the set of strings that the algorithm accepts.

But what if we take $k = 0$, and algorithm $A(\cdot) = 1$, which just returns 1 for everything? Wouldn't that mean, that $P$ is just class of all languages?

# Answer
No this means, that the language $L$ that contains all possible words ($L=\Sigma^\*$) is in $P$. In other words, no matter what your input is, the algorithm accepts. And the corresponding language is of course (trivially) decidable in polynomial time.

To clarify things: A language is a set of words (the words are considered as encodings of the yes-instances of a problem). A complexity class is a set of languages - so it is a set of sets. When a language $L$ contains all possible words, it doesn't mean that a complexity class that contains $L$, contains all languages.
> 10 votes

---
Tags: complexity-theory, terminology, time-complexity, polynomial-time
---


# Question
Title: Examples of undecidable problems whose intersection is decidable
I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the language accepted by a given pushdown automaton $M$ has that property. Clearly $P$ and $\lnot P$ are undecidable (for a given $M$) but $P \cap \lnot P$ is trivially decidable (it is always false).

I wonder if there are any "real life" examples which do not make use of the "trick" above? When I say "real life" I do not necessarily mean problems which people come across in their day to day life, I mean examples where we do not take a problem and it's complement. It would be interesting (to me) if there are examples where the intersection is not trivially decidable.

# Answer
So here is a example, which is probably not as *nice* as you wanted it to be, but less trivial than the one you have mentioned.

Let $L\_1,L\_2\subset \\{a,b,c\\}^\*$ be two undecidable languages, and $L\_3\subseteq \\{a,b,c\\}^\*$ a decidable language. We define

**\begin{align} L\_A&:=\\{a\\,w \mid w\in L\_1\\} \cup \\{c\\,w \mid w\in L\_3\\}, \\ L\_B&:=\\{b\\,w \mid w\in L\_2\\} \cup \\{c\\,w \mid w\in L\_3\\} .\\ \end{align}**

Clearly, both $L\_A$ and $L\_B$ are not decidable, however their nonempty intersection $$ L\_A\cap L\_B =\\{c\\,w \mid w\in L\_3\\}$$ is decidable.
> 7 votes

---
Tags: reference-request, undecidability, decision-problem
---


# Question
Title: Why can L3 caches hold only shared blocks?
In a recent CACM article \[1\], the authors present a way to improve scalability of shared and coherent caches. The core ingredient is assuming the caches are *inclusive*, that is higher-level caches (e.g. L3, one global cache) contain all blocks which are stored in their descendant lower-level caches (e.g. L1, one cache per core).

Typically, higher-level caches are larger than their respective descendant caches together. For instance, some models of the Intel Core i7 series with four cores have an 8MB shared cache (L3) and 256KB private caches (L2), that is the shared cache can hold eight times as many blocks as the private caches in total.

This seems to suggest that whenever the shared cache has to evict a block (in order to load a new block) it can find a block that is shared with none of the private caches² (pigeon-hole principle). However, the authors write:

> \[We\] can potentially eliminate all recalls, but only if the associativity, or number of places in which a specific block may be cached, of the shared cache exceeds the aggregate associativity of the private caches. With sufficient associativity, \[the shared cache\] is guaranteed to find a nonshared block \[...\]. Without this worst-case associativity, a pathological cluster of misses could lead to a situation in which all blocks in a set of the shared cache are truly shared.

How is this possible, that is how can, say, 1MB cover 8MB? Clearly I miss some detail of how such cache hierarchies work. What does "associativity" mean here? "number of places in which a specific block may be cached" is not clear; I can only come up with the interpretation that a block can be stored multiple times in each cache, but that would make no sense at all. What would such a "pathological cluster of misses" look like?

---

1. Why On-Chip Cache Coherence is Here to Stay by M. M. K. Martin, M. D. Hill, D. J. Sorin (2012)
2. Assuming the shared caches knows which blocks are shared where. This can be achieved by explicit eviction notifications and tracking bit, which is also discussed in \[1\].

# Answer
Perhaps I can shed some light on associativity. These caches aren't just open blocks of memory, so don't think of them as some kind of generic container. Each block of memory has a real address (whether this is physical or virtual doesn't matter, just assume it is a fixed address). At each level of cache this memory can only be cached at very specific locations in the cache.

For example, memory address X can be stored in the L1 cache at location Y0. This is a direct mapping. But suppose it can also be stored at location Y1, then it is 2-way associative (which is fairly common). Being storable in N-locations makes it N-way associative. When the chip chooses a cache location it checks only these N places -- it does not scan the entire cache (which would be too slow/complicated).

This should clarify what they mean by saying the shared cache must have an aggregate higher associativity than the lower caches. So if L1 is 2-way, L2 is 4-way, and there are 4 processors, they shared cache must be \> 24-way associative (I don't have the article, but this sounds like what they mean). This follows then, that at least one of these shared locations must not be cached in any of the private caches.

I can't say for sure what their "pathological" case is, but I can explain a common one, one that can affect things like binary search. Say the L1 cache is 1-way associative and 4KB in size. The locations where memory can be stored is likely a simple mod of the address (X mod 4K). Say then you have a large block of data which is a power of 2 (which is common). In a binary search you always chop the size in half, so a search on a 256K block would have you check address 128K, 64K, 32K, 16K, 8K, 4K, and the lower. But you should see a problem here. Those first 6 addresses all map to the exact same cache location. So each access requires an eviction and load, despite you accessing only a tiny amount of memory.
> 8 votes

---
Tags: terminology, computer-architecture, cpu-cache, shared-memory
---


# Question
Title: How to prove every well-balanced orientation of an Eulerian graph is Eulerian?
I'm trying to prove that every well-balanced orientation of an Eulerian graph is Eulerian.

I want to prove it by showing that for any two vertices $u$ and $v$, their local arc connectivities coincide, that is

$\qquad \displaystyle P\_D'(u,v)=P\_D'(v,u)$

for every well-balanced orientation of an Eulerian graph. How can I do this?

# Answer
Your statement follows from Corollary 1 in

L Lovász, *Connectivity in digraphs*, Journal of Combinatorial Theory, Series B, Volume 15, Issue 2, October 1973, Pages 174-177

The Corollary says, that if you have a vertex $u$, and for every other vertex $v$ the number of edge-disjoint paths from $u$ to $v$ equals the number of edge-disjoint paths from $v$ to $u$, then we have $\text{indegree}(u)=\text{outdegree}(u)$. Since the statement is true for every vertex of the graph, the orientation is Eulerian.

The proof of the corollary and its corresponding theorem is rather technical, but self-contained, and needs less than two pages.
> 5 votes

---
Tags: graphs
---


title: Smoothing in Naive Bayes model

text:
# Question
Title: Smoothing in Naive Bayes model
A Naive Bayes predictor makes its predictions using this formula:

$$P(Y=y|X=x) = \alpha P(Y=y)\prod\_i P(X\_i=x\_i|Y=y)$$

where $\alpha$ is a normalizing factor. This requires estimating the parameters $P(X\_i=x\_i|Y=y)$ from the data. If we do this with $k$-smoothing, then we get the estimate

$$\hat{P}(X\_i=x\_i|Y=y) = \frac{\\#\\{X\_i=x\_i,Y=y\\} + k}{\\#\\{Y=y\\}+n\_ik}$$

where there are $n\_i$ possible values for $X\_i$. I'm fine with this. However, for the prior, we have

$$\hat{P}(Y=y) = \frac{\\#\\{Y=y\\}}{N}$$

where there are $N$ examples in the data set. Why don't we also smooth the prior? Or rather, *do* we smooth the prior? If so, what smoothing parameter do we choose? It seems slightly silly to also choose $k$, since we're doing a different calculation. Is there a consensus? Or does it not matter too much?

# Answer
The typical reason for smoothing in the first place is to handle cases where $\\#\\{X\_i = x\_i | Y = y\\} = 0$. If this wasn't done, we would always get $P(Y=y|X=x) = 0$ whenever this was the case.

This happens when, for example, classifying text documents you encounter a word that wasn't in your training data, or just didn't appear in some particular class.

On the other hand, in the case of the class prior probability, $P(Y = y)$, this situation should not occur. If it did this would mean you are trying to assign objects to classes which didn't even appear in the training data.

Also, I've never encountered the term $k$-smoothing. Laplace or Additive smoothing is much more common.
> 5 votes

---
Tags: machine-learning, probability-theory, statistics
---


title: Running time of CDCL compared to DPLL

text:
# Question
Title: Running time of CDCL compared to DPLL
What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy for DPLL?

# Answer
Both CDCL and DPLL need exponential time in the worst case. I am not sure if it can be proved that CDCL is always faster than DPLL on every instance, but there is *major* empirical data suggesting it dominates. For a nice, short overview see the presentation *Boolean Satisfiability Solving: Past, Present & Future* by Joao Marques-Silva. He also has quite a few related talks online, see here.

CDCL is *the* dominating solver among all modern solvers. I would claim CDCL does indeed always dominate, and that is because it's basically a DPLL-based procedure, but with additional enhancements. It uses information gained during the search, restart strategies, special data structures, and so on.

There are instances that make all the known DPLL-like algorithms run in exponential time. For example, Alekhnovich et al. \[1\] exhibit such a family of 3-SAT instances. For more information on satisfiability, both theoretical and practical, I think one of the best sources are the *Handbook of Satisfiability* \[2\] and the regular *International Conferences on Theory and Applications of Satisfiability Testing*, known as SAT.

---

\[1\] Alekhnovich, M., Hirsch, E., and Itykson, D. Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. JAR, 35(1-3), 51-72, 2005.

\[2\] Biere, A., Heule, M., van Maaren, H. and Walsh, T. (Eds.). Handbook of Satisfiability. IOS Press, 2009.
> 6 votes

---
Tags: complexity-theory, time-complexity, efficiency, satisfiability, sat-solvers
---


# Question
Title: What if the electricity goes off while a file is being renamed?
Suppose I'm renaming a file and the electricity goes off right in the middle. Naively, it looks like the file could be in some “half-renamed” state. Maybe the name would have half the old name and half the new name. Or maybe the file could disappear altogether because it no longer exists under the old name but it doesn't exist yet under the new name.

How can a filesystem protect against loss of power while a file is renamed? Are these just theoretical techniques or are they used in practice?

# Answer
Most filesystems and filesystem implementations are designed to be resistant to a loss of power. When you rename a file, with most operating systems, you can expect to always see the file either under its old name or under its new name. If there is any intermediate stage where the file is so to speak half-renamed, the operating system will hide it from you, even if the machine crashes at a bad time. Renaming a file (with most filesystems) is an atomic operation.

The precise method for ensuring atomicity varies from filesystem to filesystem and may also depend on other system components such as the storage hardware and the disk driver. In this answer I'll describe some common techniques at a high level. If you look at an actual filesystem implementation, you're likely to find that things are a lot more complicated.

Most storage media guarantees that writes are atomic at the level of a block. A typical block size is 512 bytes. This is often guaranteed by the disk firmware. Here are some common techniques for noticing or preventing data corruption due to a power failure:

* One possibility to protect against power failures is to have a small power reserve that is sufficient to complete the writing of the current block.
* Another method is that the disk stores the block content followed by a checksum of the block: if the new content of the block is only half-written, the checksum will be wrong, and the block content is lost but the operating system will not re-read bad data.
* A third method is to maintain a dirty bit: flip it from 0 to 1, do the actual write, then flip the bit back to 0, so that if the dirty bit is 0 then the block content is known to be good.

Let's assume for a moment that the file name is stored entirely within one block. Then what the filesystem driver needs to do to rename the file is to update that block with the new name.

* If the storage medium guarantees that block writes are atomic, then the filesystem driver simply writes the new block content. If the write goes through, the file will have its new name; if a power failure happens, the file will retain its old name, meaning that the power failure effectively happened before the instruction to rename the file was carried out.
* If writing a block may damage it, the filesystem driver creates a new block with the new name. Once that block has been successfully created, the filesystem driver updates the “parent” block that contains the location of the block containing the name to reflect the new location. The location of the parent block must be updated in its parent and so on.
Such a chain has to stop somewhere. One way to stop is to have a block with two possible locations L1 and L2. Maintain a version number for the block, stored inside the block. Increment the version number each time the block is written. At any time, whichever of L1 and L2 has the highest version number is the real location.

In general renaming a file may involve rewriting several blocks. The filesystem must take care in which order these blocks are written. For efficiency, it is often useful to reorder writes. This is often a consequence of caching and buffering: blocks are not actually written to disk each time they are modified, but kept in memory for a little time in case they are modified again. Another reason to reorder writes is that it's more efficient to group consecutive writes together (write block 42 then 43 then 44, even though 43 was modified first, then 42 then 44). The management of this reordering is a very complex part of typical filesystems, because it is very important for both correctness and performance.

One method that is used by many modern filesystems is journaling (in the database world, this is called a log). In addition to the actual data blocks, the filesystem maintains a list of operations that it performs. These operations are stored in strict chronological order. The journal consists of a list of records such as “rename the file from *oldname* to *newname*, affecting blocks B1, B2 and B3”. If a power failure interrupts the writing of a journal record, the operation hasn't taken place. The information in the journal duplicates the data which is written as performance permits. If the data isn't written at its final location due to a power failure, the operating system performs a journal replay at boot time: it reads the journal entries, checks whether each operation has taken place and performs the operation if necessary. The operating system also periodically marks journal entries as completed once it knows that the data has been successfully written. In many filesystems, this allows old journal entries to be erased, so that the journal keeps to a fixed size. There are even filesystems that consist solely of a journal, so that a file is defined by pointers to older journal entries that write its contents — this isn't very common though.
> 6 votes

# Answer
Search for something called a "Journaling File System", of which variants are used on many popular operating systems.

The basics of a journaling system are:

1. Record intended change to the journal
2. Make the change

This provides basic corruptiong protection in the case of any kind of failure (including the power being lost). If an interruption happens prior/during to Step 1 it is simply as though the operation never took place. If it happens prior or during to 2, the system can simply replay what was recorded in 1 at a later time.

There's a bit of book-keeping here. You may wish to check the ext4 filesystem as a concrete example (though I think it is quite advanced, perhaps something simpler does exist).

RAID is a related concept, but their error correction modes are more dedicated to the loss of a particular node. In this case the drives are capable of rebuilding despite the lost node. Likely the individual disks/logical array still use a form a journaling. You can dig further here for RAID or under the generic term "forward error correction" (FEC).
> 4 votes

---
Tags: operating-systems, filesystems, fault-tolerance
---


title: What is the novelty in MapReduce?

text:
# Question
Title: What is the novelty in MapReduce?
A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! \[1\]

The name is reminiscent of `map` and `reduce` in functional programming, but when I read (Wikipedia)

> **Map step:** The master node takes the input, divides it into smaller sub-problems, and distributes them to worker nodes. A worker node may do this again in turn, leading to a multi-level tree structure. The worker node processes the smaller problem, and passes the answer back to its master node.
>
> **Reduce step:** The master node then collects the answers to all the sub-problems and combines them in some way to form the output – the answer to the problem it was originally trying to solve.

or \[2\]

> **Internals of MAP:** \[...\] MAP splits up the input value into words. \[...\] MAP is meant to associate each given key/value pair of the input with potentially many intermediate key/value pairs.
>
> **Internals of REDUCE:** \[...\] \[REDUCE\] performs imperative aggregation (say, reduction): take many values, and reduce them to a single value.

I can not help but think: this is divide & conquer (in the sense of Mergesort), plain and simple! So, is there (conceptual) novelty in MapReduce somewhere, or is it just a new implementation of old ideas useful in certain scenarios?

---

1. US Patent 7,650,331: "System and method for efficient large-scale data processing " (2010)
2. Google’s MapReduce programming model — Revisited by R. Lämmel (2007)

# Answer
> 49 votes
> I can not help but think: this is divide & conquer, plain and simple!

M/R is not divide & conquer. It does not involve the repeated application of an algorithm to a smaller subset of the previous input. It's a pipeline (a function specified as a composition of simpler functions) where pipeline stages are alternating map and reduce operations. Different stages can perform different operations.

---

> So, is there (conceptual) novelty in MapReduce somewhere, or is it just a new implementation of old ideas useful in certain scenarios?

MapReduce does not break new ground in the theory of computation -- it does not show a new way of decomposing a problem into simpler operations. It does show that particular simpler operations are practical for a particular class of problem.

---

The MapReduce paper's contribution was

1. evaluating a pipeline of two well understood orthogonal operators that can be distributed efficiently and fault-tolerantly on a particular problem: creating a text index of large corpus
2. benchmarking map-reduce on that problem to show how much data is transferred between nodes and how latency differences in stages affect overall latency
3. showing how to make the system fault tolerant so machine failures during computation can be compensated for automatically
4. identifying specific useful implementation choices and optimizations

Some of the critiques fall into these classes:

1. "Map/reduce does not break new ground in theory of computation." True. The original paper's contribution was that these well-understood operators with a specific set of optimizations had been successfully used to solve real problems more easily and fault-tolerantly than one-off solutions.
2. "This distributed computation doesn't easily decompose into map & reduce operations". Fair enough, but many do.
3. "A pipeline of n map/reduce stages require latency proportional to the number of reduce steps of the pipeline before any results are produced." Probably true. The reduce operator does have to receive all its input before it can produce a complete output.
4. "Map/reduce is overkill for this use-case." Maybe. When engineers find a shiny new hammer, they tend to go looking for anything that looks like a nail. That doesn't mean that the hammer isn't a well-made tool for a certain niche.
5. "Map/reduce is a poor replacement for a relational DB." True. If a relational DB scales to your data-set then wonderful for you -- you have options.

# Answer
> 22 votes
**EDIT** (March 2014) I should say that I have since worked more on algorithms for MapReduce-type models of computation, and I feel like I was being overly negative. The Divide-Compress-Conquer technique I talk about below is surprisingly versatile, and can be the basis of algorithms which I think are non-trivial and interesting.

---

Let me offer an answer that will be much inferior to Mike's in terms of comprehensiveness, but from a model of computation/algorithmic theory standpoint.

*Why there is excitement*: MapReduce interleaves parallel and sequential computation; each processor has access to a nontrivial chunk (e.g. $O(n^\epsilon)$) of the input and can perform a nontrivial operation on it; that is very much unlike PRAM models and seems like an interesting idea that might lead to new algorithmic techniques. In particular, some problems can be solved in few (constant in input size) rounds of computation, while no nontrivial problem can be solved in PRAM in $o(\log n)$ time.

*Why the model is getting slightly frustrating for me*: The only algorithmic technique that seems to work to get $O(1)$ rounds algorithms and is somewhat new is the following

* Partition the problem instance (often randomly)
* Do some computation on each partition in parallel and represent the result of the computation **compactly**
* Combine all the compactly represented subproblem solutions on a single processor and finish the computation there

Very simple example of the technique: compute the sum of $n$ numbers. Each processor has $O(\sqrt{n})$ of the array, and computes the sum of that portion. Then all the $\sqrt{n}$ sums can be combined on a single processor to compute the total sum. A slightly more interesting exercise is to compute all prefix sums this way (of course in that case the output has to be represented in a distributed way). Or compute a spanning tree of a dense graph.

Now, I think this actually is an interesting twist on divide and conquer, the twist being that after the divide stage you need to compress subproblem solutions so that a single processor can conquer. However, this really seems to be the only technique we've come up with so far. It fails on problems with sparse graphs, like sparse connectivity for example. Contrast this with the streaming model, which led to a wealth of new ideas, like the ingenuous sampling algorithm of Flajolet and Martin, the deterministic pairing algorithm of Misra and Gries, the power of simple sketching techniques, etc.

As a programming paradigm, map reduce has been very successful. My comments regard map reduce as an interesting model of computation. Good theoretical models are a little bit odd. If they follow reality too closely they are unwieldy, but more importantly, (to borrow a term from machine learning) theorems proved for models which are too specific do not generalize, i.e. do not hold in other models. That's why we want to abstract away as much detail as possible, while still leaving enough to challenge us to come up with novel algorithms. Finally, those new ideas should be able to eventually find their way back to the real world. PRAM is one unrealistic model which led to interesting ideas but those ideas proved to be rarely applicable to real world parallel computation. On the other hand, streaming is also unrealistic, but it inspired algorithmic ideas which are actually employed in the real world. See count-min sketch. Sketching techniques are in fact also used in systems based on map reduce.

# Answer
> 6 votes
I fully agree with you. From a conceptual perspective, there is nothing really new: Map/Reduce was originally known in Parallel Computing as a data-flow programming model. However, from a practical point of view, Map/Reduce as proposed by Google and with the subsequent open-source implementations has also fueled Cloud Computing and is now quite popular for very simple parallel decompositions and processing. Of course, it is not well suited for anything else requiring complex domain or functional decompositions.

# Answer
> 3 votes
I think you've hit the nail on the head with your comment.

It's not true that in any functional language maps can be parallelized - the language must be pure. (I believe Haskell is the only vaguely mainstream purely functional language. Lisp, OCaml and Scala are all non-pure.)

We've known about the benefits of pure code since even before timesharing, when engineers first pipelined their processors. So how come no one uses a pure language?

It's really, really, really hard. Programming in a pure language often feels like programming with both hands tied behind your back.

What MR does is relax the purity constraint somewhat, and provide a framework for other pieces (like the shuffle phase) making it quite easy to write distributable code for a large fraction of problems.

I think you were hoping for an answer like "It proves this important sub-lemma of $NC=P$" and I don't think it does anything of the sort. What it does do is show that a class of problems known to be distributable are "easily" distributable - whether that's a "revolution" in your opinion probably depends on how much time you've spent debugging distributed code in a pre-Map/Reduce world.

---
Tags: algorithms, distributed-systems, parallel-computing, algorithm-design
---


# Question
Title: Measuring entropy for a table (e.g., SQL results)
We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of the benchmark. However, the results often contain a lot of redundancy, so just counting results seems coarse.

Consider the following table containing results for a query like "*for the US, give me its states and its car manufacturers*":

```
================================
|| ?us_state | ?us_car_manu   ||
||============================||
|| Alabama   | Chrysler       ||
|| Alaska    | Chrysler       ||
|| ...         ...            ||
|| Wyoming   | Chrysler       ||
|| Alabama   | General Motors ||
|| Alaska    | General Motors ||
|| ...         ...            ||
|| Wyoming   | General Motors ||
|| Alabama   | Ford           ||
|| Alaska    | Ford           ||
|| ...         ...            ||
|| Wyoming   | Ford           ||
===============================

```

All 200 (50 × 4) results are of course unique. However, given that there is an inherent Cartesian product, the number of results flatters the amount of "information content" or "entropy" of the table: every additional car manufacturer adds fifty results for the fifty US states. (Again, this is just an example; I'm not interested in better ways to represent or run this particular query.)

As such, we're looking for a metric that will give an indication as to the (loosely speaking) redundancy-free content in the table for better comparison of *content* across different results for different queries. Other result tables may contain a mix of different types of Cartesian products (e.g., consider generalising the query to any country, where each country itself has its own product of states and car manufacturers, etc.).

Currently we're working off a simple metric which just counts unique term–position combinations: for the above example, the metric gives 50 + 4 = 54. This may be sufficient for comparison, but is not sensitive to the combination of terms for individual results.

Thanks to Wikipedia, I'm aware of—but not familiar with—the notion of entropy in information theory. However, I'm unclear on how the concept of entropy could be applied to this use-case. (I'm not interested in the entropy of the result strings; each term can be considered a "symbol".) Roughly speaking, each query variable could be considered as a free variable with the result terms in that column providing a set of possible outcomes and their frequency of occurrence being used as a probability mass function. This way I could compute the Shannon entropy for each column. But thereafter, I don't know how columns can be combined, or how tuples or results can be considered ... if a notion of conditional entropy would be better, etc.

And so ...

> Does anyone have pointers to related material on the measure of entropy/redundancy/etc. in tables or similar structures?
>
> Otherwise, does anyone have any ideas on how to use Shannon entropy in a convincing way for tabular data?

# Answer
> 1 votes
Information-theoretic approach to database dependency theory has long history; here is couple of references:

---
Tags: reference-request, information-theory, data-compression, database-theory, entropy
---


title: What is known about coRL and RL?

text:
# Question
Title: What is known about coRL and RL?
Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$.

Are they the same class?

What are $\mathsf{coRL}$'s relation to $\mathsf{NL}$, $\mathsf{P}$?

# Answer
By definition, $ \mathsf{RL} $ is a subset of $ \mathsf{NL} $, and so $ \mathsf{coRL} $ is a subset of $ \mathsf{coNL} $.

Since $ \mathsf{NL} = \mathsf{coNL} $, $ \mathsf{coRL} $ is also subset of $ \mathsf{NL} $.

Moreover, $ \mathsf{NL} \subseteq \mathsf{P} $.

Please also note that although it is widely believed to be true, whether $ \mathsf{RL} \subseteq \mathsf{L} $ is still an open problem, and so is whether $ \mathsf{coRL} \subseteq \mathsf{L} $. (The obviuos relation is $ \mathsf{L} \subseteq \mathsf{RL} \cap \mathsf{coRL} $.)
> 8 votes

---
Tags: complexity-theory, complexity-classes, probabilistic-algorithms
---


title: 3CF 3-conjunctive form satisfiability

text:
# Question
Title: 3CF 3-conjunctive form satisfiability
I am self studying discrete math and I am going through MIT Mathematics for CS lecture notes but they do not have solutions available. I got stuck at Problem 3.14 (pages 64-65 of this document). The problem is about the construction, given an arbitrary propositional formula $F$, of a proposition $C(F)$ such that:

* $C(F)$ is in 3-conjunctive form (3CF), i.e. it is a conjunction of disjunctions of at most literals (a literal is a variable or a negation of a variable);
* $C(F)$ has at most 24 times as many occurrences of variables as $F$;
* $C(F)$ is satisfiable iff $F$ is.

The idea is to introduce a new variable for each operator that occurs in $F$. For example, given $$ F\_1 = ((P \oplus Q) \oplus R) \vee (\neg P \wedge S)) $$ assign $X\_1, X\_2, O, A$ to the 4 operators in $F\_1$, and define four *constraining formulas*: $$ \begin{align\*} C\_1^1 &= X\_1 \Leftrightarrow (P \oplus Q) \\ C\_1^2 &= X\_2 \Leftrightarrow (X\_1 \oplus R) \\ C\_1^3 &= A \Leftrightarrow (\neg P \wedge S) \\ C\_1^4 &= O \Leftrightarrow (X\_2 \oplus A) \\ \end{align\*} $$ and $C\_1 = C\_1^1 \wedge C\_1^2 \wedge C\_1^3 \wedge C\_1^4 \wedge O$.

The questions are:

1. Why is $C\_1$ satisfiable iff $F\_1$ is satisfiable?
2. Why is each constraining formula equivalent to a 3CF formula with at most 24 occurrences of variables?
3. Generalize from the example to construct $C(F)$ for an arbitrary formula $F$.

For question 1, I don't see why $X\_1$ is satisfiable.

I think question 2 is wrong, beacuse you can form a 3CF formula with at most 24 occurrences of variables, only if you have a 3-conjunctive **normal** form but here the author only says 3 conjunctive form.

(For 3CNF, 8 different triple terms can be formed using 3 variables with a total of 24 variables, For 3CF, 26 different single,double and triple terms can be formed with a total of ? variables.)

No idea about question 3.

# Answer
First of all, I assume that $C\_1^4 \equiv O \iff (X\_2 \lor A)$ in accordance to $F\_1$. Second, note that 3CF as defined in the exercise is equivalent to 3CNF. In the following, I will denote with $\phi\_X$ the subformula of the given formula $F$ which has been assigned new variable $X$ by the construction. For example, $\phi\_A=(\lnot P \land S)$ and $\phi\_O = F\_1$. $\renewcommand{\models}{\mathop{|\\!\\!\\!=}}\newcommand{\rmodels}{\mathop{=\\!\\!\\!|}} \newcommand{\semeq}{\models\\!\rmodels}$

## Satisfaction equivalence

> I don't see why $X\_1$ is satisfiable

$X\_1$ is a single variable and thus trivially satisfiable (by setting it to $1$). The $C\_1^i$ essentially take apart $F\_1$ operator by operator, introducing new variables that have to evaluate to the same truth values as their respective subformulae. Using $\\{O\\}$ as clause of $C\_1$ guarantees the statement, essentially (as "$O \semeq F\_1$", given $C\_1$).

### Proof

Assume $F\_1$ is satisfiable and let $\psi$ be a satisfying valuation of the variables. Construct $\psi'$ by extending $\psi$ with $\psi'(X) = \psi(\phi\_{X})$ for $X \in \\{X\_1,X\_2,A,O\\}$. As a consequence, $\psi'$ satisfies all $C\_i^1$. Because $\psi(F\_1)=1$ by assumption, we have chosen $\psi'(O)=1$. Therefore, $\psi'(C\_1)=1$.

Conversely, assume $C\_1$ is satisfiable and let $\psi$ a satisfying valuation. Clearly, $\psi(O)=1$ and $\psi(C\_1^4)=1$. Therefore, $\psi(\psi\_O)=1$. Because $\psi\_O=F\_1$, we are done -- $\psi$ satisfies $F\_1$. In order to be rigorous, we would have to iterate this argument top-down, following the structure of $F\_1$, to unfold $X\_2$ and then $X\_1$ (in the general case, we would need a structural induction here).

## Size restriction

The constraining formulae all have the same form and are small (three literals, two operators). You can transform those into equivalent 3CF formulae *locally*, i.e. ignoring the others. This conversion always yields formulae with at most 24 literals, that is at most 8 clauses. This can be shown by dull calculation.

### Details

The general form of a contraining formula is $A \iff (A \circ B)$ for $\circ$ some logical operator. Let us transform it into 3CF using laws and rules of boolean algebra.

$\qquad \begin{align} C^i &\equiv X \iff (A \circ B) \\ &\semeq\ \[X \land (A \circ B)\] \lor \[\lnot X \land \lnot(A \circ B)\] \\ &\semeq\ \[\lnot X \lor (A \circ B)\] \land \[ X \lor \lnot(A \circ B)\] \end{align}$

Now, for $\circ = \land$, we use both distributive and associative law resp. De Morgan's rule:

$\qquad \begin{align} C^i &\semeq\ \[\lnot X \lor (A \land B)\] \land \[ X \lor \lnot(A \land B)\] \\ &\semeq\ \[\lnot X \lor A\] \land \[\lnot X \lor B\] \land \[ X \lor \lnot A \lor \lnot B\] \end{align}$

This has three clauses (after padding with redundant literals, nine literals). For $\circ \in \\{\lor, \to\\}$¹ this works exactly the same way. You can proceed similarly for other choices of $\circ$, such as $\oplus$ or $\iff$, depending on which operators are allowed in your setting.

## Generalisation

This is just a matter of writing down what the example does in general terms. Let $F$ an arbitrary propositional formula, w.l.o.g. without "negation chains"². Now do the following.

$\quad$ Let $i=0$.
$\quad$ Until $F$ is a literal, do
$\qquad$ Increase $i$ by one.
$\qquad$ Pick a subformula of $F$ of the form $L\_1 \circ L\_2 = \phi$ with $L\_1,L\_2$ literals.
$\qquad$ Let $C^i \equiv X\_i \iff (L\_1 \circ L\_2)$.
$\qquad$ Replace $\phi$ with $X\_i$ in $F$.
$\quad$ For all $j=1,\dots,i$, convert $C^j$ into 3CF by finite case distinction.
$\quad$ Return $\[F \lor F \lor F\] \land \bigwedge\_{j=1}^{i} C^j$.

Note that $F = X\_i$ after the loop. For intuition and implementation purposes, think of a formula as a tree: operators are inner nodes, leaves are literals. Above algorithm iteratively contracts subtrees of height two into leaves, collecting the $C^j$ as "mapping" from new variable to the removed subtree along the way.

---

1. Remember $A \to B \semeq \lnot A \lor B$.
2. We can always use $\lnot \lnot A \semeq A$.
> 3 votes

---
Tags: logic, satisfiability, 3-sat, normal-forms
---


# Question
Title: name matching algorithms from partial input
There are a lot of algorithms out there that solve this particular problem. My main problem is in trying to understand how they work; where to start. Most of the algorithms are academic in nature.

There is a master list of product names. We feed in an input file into the program with product names, but the names of the products may be partial or incomplete. We would need to match the correct product from the master list.

There are solutions like clustering algorithms, naive-bayes, etc. But I am looking at some working examples to actually understand the concept. Would want to review the computations step-by-step for a small model.

# Answer
A cheap but possibly low-precision, low-recall way is to compute something similar to Soundex or Metaphone codes for your product names and candidates. This only really accounts for misspellings, and even then not reliably or in a principled way. But it's cheap to compute.

Alternatively, for a language-independent approach, consider computing the edit distance between each candidate and all the database entries, and return the cheapest match that's under some threshold. There's worked examples of how the Levenshtein distance is computed on the Wiki page.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Seeking "gold standard" to evaluate accuracy of network clustering algorithm
I'm currently looking at network clustering algorithms (we're currently looking at both directed and undirected, unweighted networks). The algorithms we've tried produce visually nice clusters. However, we would like to evaluate them against some "gold standard" -- a collection of networks in which the clusters have already been identified (and are more-or-less regarded as *the* clusters by the complex network's research community).

> **Question**: What are the gold standards for network clustering algorithms? Where can I access them?

# Answer
> 2 votes
There are a couple of test sets mentioned in Stochastic blockmodels and community structure in networks by Karrer and Newman. One of them is the Karate Club Network, which is rather small, and the other is the Political Blog Network which is bigger. As far as I know, there is no gold-standard for testing clustering algorithms.

---
Tags: algorithms, data-sets, network-topology
---


title: Is the set of minimal DFA decidable?

text:
# Question
Title: Is the set of minimal DFA decidable?
Let $\mathrm{MIN}\_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}\_{\mathrm{DFA}}$ then for every other DFA $B$ with less states than $A$, $L(A)\ne L(B)$ holds. I'm trying to figure out how come that $\mathrm{MIN}\_{\mathrm{DFA}} \in R$? How come it is decidable?

What is about this kind of DFAs that is easy to decide?

# Answer
Given two DFAs $A,B$, it is decidable (even efficient!) whether $L(A) = L(B)$: use the product construction to get a DFA for $L(A) \triangle L(B)$, and now use reachability analysis.

In order to determine whether $A$ is a minimal DFA, one can just try all DFAs $B$ with less states, looking for one satisfying $L(A) = L(B)$. Alternatively, there are algorithms for minimizing DFAs which are vastly more efficient than that approach. They are even more efficient if all you want to know is whether the DFA is minimal or not.
> 9 votes

---
Tags: formal-languages, computability, automata, finite-automata
---


# Question
Title: Run time of product of polynomially bounded numbers
Let $M$ denote a set of $n$ positive integers, each less than $n^c$.

What is the runtime of computing $\prod\_{m \in M} m$ with a deterministic Turing machine?

# Answer
> 3 votes
Computing the product sequentially, we need to perform $n-1$ multiplications of numbers of size $O(C^n n^{cn})$, for some constant $C$ corresponding to the constant in $O(n^c)$. Using algorithms for fast integer multiplication, each of these requires $\tilde{O}(C\log n + cn \log n) = \tilde{O}\_c(n)$, so in total the time is $\tilde{O}\_c(n^2)$ (the $\tilde{O}$ hides logarithmic factors).

---
Tags: algorithms, time-complexity, integers
---


# Question
Title: Arithmetic expressions grammar transformation
In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions:

```
E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v

```

which is quite bad, because it's ambiguous and left-recursive. So he starts from removing the left recursion from it, and his result is as such:

```
E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

```

But I can't figure out how did he get to this result. When I try to remove the left recursion myself, I'm doing it the following way:

1. Firs, I group together the productions which doesn't have left recursion in one group, and other (left-recursive) in another group:

```
E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
E --> v | "(" E ")" | "-" E
```
2. Next, I name them and factor for easier manipulations:

```
E --> E B E  // L-recursive; B stands for "Binary operator"
E --> P  // not L-recursive; P stands for "Primary Expression"
P --> v | "(" E ")" | U E   // U stands for "Unary operator"
B --> "+" | "-" | "*" | "/" | "^"
P --> "-"
```

Now I need to deal only with the first two productions, which are now easier to deal with.
3. I rewrite those first two productions by starting from the non-L-recursive production (which is simply `P`, the Primary expression) and following it by the optional Tail `T`, which I define as the rest of the original production less the first left-recursive nonterminal (that is, just `B E`) followed by the Tail `T`, **or** which could be empty:

```
E --> P T
T --> B E T |
```

(note the empty alternative for the tail).
4. These two productions I can now rewrite in EBNF like this:

```
E --> P {B E}
```

which is nearly what the author get, but I have `E` instead of `P` there inside the zero-or-more repetition pattern (the Tail). The other productions I get quite the same as he have got:

```
P --> v | "(" E ")" | U E
B -> "+" | "-" | "*" | "/" | "^"
U -> "-"
```

but here too I have `E` instead of `P` in the first production for `P`.

So, my question is: What am I missing? What algebraic transformation on the syntax I need to proceed now to get the same exact form as the autor gets? I tried substitutions for `E`, but it only leads me into loops. I suspect that I need somehow to substitute `P` for `E`, but I don't know any legal transformation to justify it. Maybe you know what's the last missing step?

# Answer
The missing step:

```
E --> P T
T --> B E T |

```

rewrite E in T:

```
E --> P T
T --> B P T T |

```

Simplify T:

```
E --> P T
T --> B P T |

```

Equivalent to:

```
E --> P T
T --> {B P}

```

And there you are.
> 8 votes

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


title: Factor a grammar

text:
# Question
Title: Factor a grammar
Consider the context free grammar:

$\qquad \begin{align} \mathrm{bill} &\to \mathrm{items}\ \mathrm{total}\ \mathrm{vat} \\ \mathrm{items} &\to \mathrm{item} \mid \mathrm{item}\ \mathrm{items} \\ \mathrm{item} &\to name\ \mathrm{price} \mid name\ \mathrm{quantity}\ \mathrm{price} \\ \mathrm{quantity} &\to integer \\ \mathrm{price} &\to integer \\ \mathrm{total} &\to integer \mid TOTAL\ \mathrm{price} \\ \mathrm{vat} &\to VAT\ \mathrm{price} \end{align}$

How do I factor the grammar?

This was asked in a past exam, and I don't know how to get started.

Also, if you have any links that could help me understand this more it would be much appreciated!

# Answer
> 3 votes
To factor a grammar you need to check the alternatives of productions (those separated by `|`) whether they have some common symbols in sequence. For example, whether they have a common prefix (that is, whether they start with the same symbol). Join together as many subsequet common symbols (common factors) as you can, and put the rest into parentheses. For example, look at the productions for `item`:

```
item --> NAME price | NAME quantity price

```

You can rewrite all alternatives one below the other to better see the common prefix:

```
item --> NAME price
item --> NAME quantity price

```

Now you can see that they both start with `NAME`, and they both end with `price`. The only difference is the presence of the middle term `quantity`, which seems to be optional:

```
item --> NAME () price
item --> NAME (quantity) price

```

So you can rewrite it like this, making a new production for the contents of the parenthesis:

```
item --> NAME optionalQuantity price

```

and the new symbol `optionalQuantity` you've just introduced can be equal to what? The `quantity` or just nothing. So you write it down this way:

```
optionalQuantity --> quantity
optionalQuantity -->

```

As you can see, the last production for `optionalQuantity` is empty. This form is sometimes called *erasure*, because it can "erase" its own symbol from other productions (could be replaced by nothing at all). If you're allowed to use EBNF, you can write all the above three productions as such:

```
item --> NAME quantity? price

```

The question mark after `quantity` means that it could be omitted (it's optional). Then you don't need a separate productions for `optionalQuantity`.

You can apply the same technique for `items` production:

```
items --> item | item items

```

When you rewrite the alternatives separately, you can see, they both start with `item`, and then there's an optional `items` again:

```
items --> item
items --> item items

```

or with parentheses around symbols which are not common:

```
items --> item ()
items --> item (items)

```

so in EBNF you could write it just like:

```
items --> item items?

```

or in plain context-free grammar as:

```
items    --> item optItems
optItems --> items
optItems -->

```

And then the syntax is factored. But notice what the above syntax really says: It says that `items` is just one `item`, which optionally could be followed by more items. In EBNF you could express it shorter like this:

```
items --> item item*

```

where star after `item` means that it could be repeated zero or more times. But it could be rewritten even further, because one followed by zero or more is the same as one or more. So you can express it more shortly as:

```
items --> item+

```

where `+` means "one or more".

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


title: Compression of domain names

text:
# Question
Title: Compression of domain names
I am curious as to how one might *very compactly* compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or domain name (U-label) consists of a string of Unicode characters, typically constrained to one language depending on the top-level domain (e.g. Greek letters under `.gr`), which is encoded into an ASCII string beginning with `xn--` (the corresponding A-label).

One can build data models not only from the formal requirements that

* each non-Unicode label be a string matching `^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$`;
* each A-label be a string matching `^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$`; and
* the total length of the entire domain (A-labels and non-IDN labels concatenated with '.' delimiters) not exceed 255 characters

but also from various heuristics, including:

* lower-order U-labels are often lexically, syntactically and semantically valid phrases in some natural language including proper nouns and numerals (unpunctuated except hyphen, stripped of whitespace and folded per Nameprep), with a preference for shorter phrases; and
* higher-order labels are drawn from a dictionary of SLDs and TLDs and provide context for predicting which natural language is used in the lower-order labels.

I fear that achieving good compression of such short strings will be difficult without considering these specific features of the data and, furthermore, that existing libraries will produce unnecessary overhead in order to accomodate their more general use cases.

Reading Matt Mahoney's online book Data Compression Explained, it is clear that a number of existing techniques could be employed to take advantage of the above (and/or other) modelling assumptions which ought to result in far superior compression versus less specific tools.

By way of context, this question is an offshoot from a previous one on SO.

---

**Initial thoughts**

It strikes me that this problem is an excellent candidate for offline training and I envisage a compressed data format along the following lines:

* A Huffman coding of the "public suffix", with probabilities drawn from some published source of domain registration or traffic volumes;
* A Huffman coding of which (natural language) model is used for the remaining U-labels, with probabilities drawn from some published source of domain registration or traffic volumes given context of the domain suffix;
* Apply some dictionary-based transforms from the specified natural language model; and
* An arithmetic coding of each character in the U-labels, with probabilities drawn from contextually adaptive natural language models derived from offline training (and perhaps online too, although I suspect the data may well be too short to provide any meaningful insight?).

# Answer
> 0 votes
Huffman coding is optimal for letters and can certainly be adapted to sequences. For instance, if the sequence "ab" results in fewer bits than the bits for "a" and "b", then simply add it to the tree ...and so on.

...you can also probably use some simple library which does that all for you with near optimal performances, so that you won't gain much using your custom made super fancy compression algorithm.

---
Tags: algorithms, strings, natural-language-processing, data-compression
---


# Question
Title: A hash function with predicted collisions
As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with *predicted* collisions? In other words, a hash function that collides for some known set of possible inputs and avoids collisions for other input values. To state the problem simpler:

Let $A$ be some set of strings. Define a function $f$ such that $f(x\_i) \rightarrow y\_i$ with $y\_i \neq y\_j$ for all $i,j \notin A$ with $i \neq j$, and otherwise $f(x\_i) \rightarrow y$ where $y \notin \\{y\_i \mid i \notin A\\}$ is constant.

Is it possible? In addition, is it possible for performance of such a hash function *not* to depend on the size of $A$?

# Answer
> 5 votes
Generally the collisions in a hash function are, in a way, what winds up improving the running time.

This is because running time (or size, or insertion time) is generally defined in terms of worst-case input. If you use an algorithm without any randomness or hash, you need to deal with the worst case. For example, finding duplicate elements in an array has an $\Omega(n\log n)$ in the comparison model, same as sorting. But if you just hash the values, you can determine whether or not there's a duplicate in $O(n)$ time and space with a small probability of error. Determining a hash function that wouldn't collide, eliminating the possibility of error, has to take $\Omega(n\log n)$ time. (You may notice that these are, in a way, the same problem--though of course hashed values generally belong to a smaller universe and the comparison model may not be appropriate).

That said, there are some ways to take advantage of the ways hash functions collide. One is locally sensitive hash functions, in which elements with small differences (i.e. normal distance functions for points) hash to the same value. Recently I've been reading this paper(1), which I found really easy to read, and shows some good, intuitive applications for how a locally sensitive hash function can be used to solve seemingly difficult problems--in this case the nearest neighbor problem with small probability of error.

Incidentally, the space advantage of possible collisions is how bloom filters work, a data structure that allows you to store elements of a set, each in space smaller than their actual size. They are a constant factor away from optimal, and the upper and lower bounds demonstrate the tradeoff between error and space.

(1) Neylon, T. A locally sensitive hash for real vectors. SODA2010.

---
Tags: cryptography, hash
---


title: Proof that $a^{n^2}$ is not regular

text:
# Question
Title: Proof that $a^{n^2}$ is not regular
> Show that $L=\\{a^{n^2} | n \geq 0\\}$ is not regular

Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me. I tried to look if I get some contradiction by using the pumping lemma for regular languages and I worked it out like this:

> Suppose $L$ is regular. Then there must be a natural number $m$ for all words $z$ in $L$ with length $|z| \geq m$ and there exists a decomposition $z = uvw, |uv| \leq m, |v| \> 0$, so that $u(v^i)w$ is in the language for any $i \geq 0$.
>
> Consider the string $a^{m^2}$.
>
> Then $uv = a^{k^2} = a^{x+y}$, for some $k \leq m$ and $x = (k-1)^2$.
> Then $v = a^y = a^{2k-1}$.
>
> Let $i = 2$. Then $u(v^2)w = a^{x+2y}$. But $\sqrt{x+2y}$ is not necessarily a natural number -\> Contradiction! Hence, $L$ can not be regular.

Well, I know that this way is unnecessarily complicated and you can prove it differently (I already know the most simple solution). But my question here is: Is my proof valid as well or does it contain any flaw? Is it formally correct?

I appreciate any feedback! Thanks!

# Answer
You can't deduce that $uv = a^{k^2}$, all that the pumping lemma gives you is that $|uv| \leq m$. Not all numbers less than $m$ are squares. Not only that, but even supposing that $uv = a^{k^2}$, there is no reason to assume that $v = a^{2k-1}$; all the pumping lemma gives you is that $v$ is non-empty. Finally, in order to get a contradiction, it is not enough that $x + 2y$ *need not* be a square, it *must not* be a square! Since $x$ and $x+y$ are adjacent squares, it is actually case that $x + 2y$ is not a square.
> 8 votes

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Are generational garbage collectors inherently cache-friendly?
A typical generational garbage collector keeps recently allocated data in a separate memory region. In typical programs, a lot of data is short-lived, so collecting young garbage (a minor GC cycle) frequently and collecting old garbage infrequently is a good compromise between memory overhead and time spent doing GC.

Intuitively, the benefit of a generational garbage collector compared with a single-region collector should increase as the latency ratio of main memory relative to cache increases, because the data in the young region is accessed often and kept all in one place. Do experimental results corroborate this intuition?

# Answer
> 19 votes
Here are a few papers that talk about the cache implications of generational garbage collectors:

From what I can gather, the primary issue is that garbage collected systems trade off space in memory to avoid up front collection. The same thing applies to cache memory. As you suggested, the things in the first generation are most likely going to be sitting in cache, and so their allocation and collection will be much faster than something in main memory, or paged out to disk. The main issue is the size of the first generation with respect to the size of your cache. If your cache fills up before the first generation does, then you start to lose those benefits as the misses start piling up.

# Answer
> 10 votes
There is a very tricky aspect of all garbage collectors that might be glossed over in some descriptions, and that is the "full scan" or "full collect". Periodically, randomly, intermittently they must scan all objects. generational collectors are better at postponing the full scan and minimizing its duration, but it is still required.

The generational collector will focus on what is sometimes called the "nursery" space, but it will eventually/inevitably have to collect on the "older" generation space, causing a full scan of memory.

This full scan is incompatible with almost all memory caching and (especially!) virtualization schemes in the sense that almost all memory caching/virtualization schemes will/must fail badly in any performance improvement in this case.

So the key answer to this question is how often the full scan is triggered, and how "bad" its effect is when it happens, and if it can be tolerated. this boils down to a more an application-dependent property/question.

In other words for "most" of the operation of the collector, a cache will probably help it (the cache and the "young" nursery space will generally overlap!), but there is a periodic, intermittent, eventual, inevitable, heavy, maybe even "massive" \[degrading\] spike in performance when the "old generation" space is full-collected and the cache "hit rate" will degrade to very bad as many objects outside of it are all fetched in a tight loop by the full scan/collect cycle. In other words, an inescapable periodic discontinuity (where statistical estimates/averages/trends of performance etc are misleading and inapplicable).

What is now emerging are some new collection systems that are designed to mesh with the underlying memory management systems (caching/virtualization). it does appear that historical approaches that completely decouple the separate systems of memory collection, caching, and virtualization will not perform as well as approaches that combine/integrate/address all three aspects together.

See eg cache aware garbage collection by Zhou and Demsky.

---
Tags: programming-languages, computer-architecture, cpu-cache, garbage-collection
---


# Question
Title: Is it possible to find the nth term  of a Fibonacci sequence using a definitive for loop?
I'm using the book Introduction to Computer Science by John Zelle and at the end of Chapter 3 (Computing with numbers), I'm asked to find the nth term of a Fibonacci sequence presumably using a definitive for loop, as no other decision structure has been introduced yet.

Is this possible? I've tried everything I could think of.

\**I know how to solve it using if statements and such. But the book hasn't yet covered decision structures, yet it asks me to find the nth term(given by the user). So I can only presume to know how to do this using "for" loops as this is all that has been covered so far

# Answer
If it is only the third chapter, I doubt the authors have covered dynamic programming, but I will illustrate what is going on when a for loop is used to compute the $n^\text{th}$ Fibonacci number, $F\_n$.

Recall the definition, $$F\_n = \begin{cases} 0 & n = 0\\ 1 & n = 1\\ F\_{n-1} + F\_{n - 2} & \text{otherwise} \end{cases}$$

We could naively compute this using a recursive function defined in Python as,

```
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

```

However by recomputing the same sub-problem many times, this function requires exponential time to compute (illustrated below)!

There is a fix, though. We can use dynamic programming to do "smarter" recursion and keep our previous results around. This way, we don't need to recompute $F\_i$. Our function call "tree" will collapse to a list and and will compute $F\_n$ from the "bottom-up".

```
def fib2(n):
    if n < 2:
        return n
    else:
        if not results[n]:
            results[n] = fib2(n - 1) + fib2(n - 2)
        return results[n]

```

Now we have our $O(n)$ time algorithm to compute $F\_n$, but if you notice, we require $O(n)$ additional space (one spot in the array for each $F\_i$). This can be cut down to $O(1)$ additional space because each $F\_i$ requires only two other fibonacci numbers, namely $F\_{i-1}$ and $F\_{i-2}$.

```
def fib3(n):
    if n < 2:
        return n
    f_0 = 0
    f_1 = 1
    f_n = 0
    for _ in range(n - 1):
        f_n = f_0 + f_1
        f_0 = f_1
        f_1 = f_n

    return f_n

```
> 11 votes

# Answer
If you only have to use a for loop that iterates until it finds the n-th Fibonacci number, you could use something like this:

```
int fib(int n)
{
    int p = 0;
    int c = 1;
    int r = 0; // The result is initialized to 0 (undefined).
    for (int i = 0; i < n; i++)
    {
        r = p + c; // Produce next number in the sequence.
        p = c;     // Save previous number.
        c = r;     // Save current number.
    }

    return r;
}

```

**NOTE**

In the solution above, I assume that the Fibonacci sequence is 1 1 2 3 5 8 13 ... and that n has the range 1, 2, 3, ... Since under these assumptions there is no Fibonacci number for n \< 1, the function returns a 0 for n \< 1 to indicate that the input parameter is out of range (see Tom's suggestions in the comments below).
> 10 votes

---
Tags: algorithms, imperative-programming
---


# Question
Title: For a Turing Machine $M_1$, how is the set of machines $M_2$ which are "shorter" than $M_1$ and which accept the same language decidable?
I wonder how come that the following language is in $\mathrm R$.

$L\_{M\_1}=\Bigl\\{\langle M\_2\rangle \\;\Big|\\;\\; M\_2 \text{ is a TM, and } L(M\_1)=L(M\_2), \text{ and } |\langle M\_1\rangle| \> | \langle M\_2 \rangle| \Bigr\\} $

(I know that it's in $\mathrm R$ since there's an answer for this multi-choice question, but without explanation).

I immediately thought that the $L\_{M\_1} \notin \textrm{co-RE} \cup \textrm{RE}$ since we know that checking if two machines accept the same language is really not decidable, I came to think: is it immediate "False", but it can't be since there's a lot of Turing machines who accepts the same answer and have different codings.

Thanks!

# Answer
$L\_{M\_1}$ is in $R$ simply because the number of machine descriptions smaller than a given machine description is finite and any finite language is in $R$.
> 14 votes

---
Tags: computability, undecidability
---


# Question
Title: Where to get graphs to test my search algorithms against?
I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc.

At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'm looking for either

1. graphs used in benchmarks;
2. graphs of real world cities (or a way to download that kind of info off google maps, or any other kind of source, if possible).

I'd like those sources to either have or allow me to easily create frontiers such that I can try my algorithms for different sized sets of graphs, if possible.

I'm looking for simple solutions, as I'd prefer not to be diverted from main goal (compare a set of different algorithms), so I'd need a quick way to convert that graph data into my own format (basically, a set of connected `(x, y)` points).

To be more concrete, what I'm looking for are 2D cyclic graphs. If those graphs reflect real world city streets (taking into consideration one-way streets, two-way streets, etc, better yet!).

# Answer
> 17 votes
Search the inter-webs.

SNAP is a set of networks hosted by a prof at Stanford. Several real world examples in a variety of settings.

Net Wiki is hosted by a UNC math prof., again several links to real datasets as well as links to other data resources.

OpenFlights Has airports and routes between them (spatial network).

OpenStreetMap user edited network of roads for most of the world. You can also download subsets (e.g. just roads in Ohio, or just highways in North America). Format is in xml, not super easy to parse, but its a real world ~2d cyclic network.

There are several other resources as well, you'll just have to dig a little.

# Answer
> 2 votes
I've been visiting all the links provided by Nick. They do look wonderful indeed and I have added all those sites to my bookmarks. Hope that the following link especially designed to test search algorithms suits your needs as well:

Pathfinding Benchmarks by Nathan Sturtevant. It contains various maps from different video games and also other artificial benchmakrs such as mazes and graphs with random obstacles.

If you are, in particular, interested in this sort of domains, then you might want to take part in the Grid-Based Path Planning Competition next year (the results of the first edition of the competition are available at GPPC 2012)

Cheers,

---
Tags: algorithms, graphs, data-sets, benchmarking
---


# Question
Title: How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$?
I'd like your help with proving that the language $$L=\\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \\}$$ is decidable iff $\mathrm{P}=\mathrm{NP}$.

If $\mathrm{P}=\mathrm{NP}$, I get that it's the language of empty Turing machines. So $L$ is a $\text{co-RE}$ problem — but that's not what's being asked, so I got confused.

I know that in order to show $\mathrm{P}=\mathrm{NP}$, I need to show problem which it's $\mathrm{NPC}$ and $\mathrm{P}$ as well.

Any help? Thanks!

# Answer
> 9 votes
There are two cases to consider.

1. Assume that $\text{P=NP}$. Then $L=\\{\langle M\rangle \mid L(M)\in \emptyset\\}=\emptyset$. The empty language is decidable; as no word belongs to it, it is trivial to decide whether a word belongs to it or not.
2. Assume that $\text{P}\neq\text{NP}$. Now your result follows directly from Rice's theorem.

---
Tags: computability, undecidability, p-vs-np
---


# Question
Title: Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?
Let $F = \\{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\\}$. I need to decide whether *F* is decidable or recursively enumerable. I think it's decidable, but I don't know how to prove it.

**My thoughts**

This "50 steps" part immediate turns the **R** sign for me. If it was for specific input it would be decidable. However, here it's for every input. Checking it for infinite inputs makes me think that the problem is **co-RE**, *i.e.* its complement is acceptable.

Perhaps, I can check the configurations and see that all configurations after 50 steps don't lead to accept state- how do I do that?

# Answer
> 22 votes
Let's consider the more general problem of machines which stop after at most $N$ steps, for some $N \geqslant 1$. (The following is a substantial simplifcation of a previous version of this answer, but is effectively equivalent.)

As swegi remarks in an earlier response, if the machine stops after at most $N$ steps, then only the cells $0,1,\ldots,N-1$ on the tape are significant. Then it suffices to simulate the machine $M$ on *all input strings* of the form $x \in \Sigma^N$, of which there are a finite number.

* If any of these simulations fail to enter a halting state by the $N^{\text{th}}\\:\\!$ transition, this indicates that any input string starting with $x$ is one for which the machine does not stop within the first $N$ steps.
* If all of these simulations halt by the $N^{\text{th}}\\:\\!$ transition, then $M$ halts within $N$ steps on all inputs of any length (of which the substring of length $N$ is all that it ever acts on).

# Answer
> 5 votes
If $M$ stops in no more than 50 steps, than the positions $M$ can reach on the normally infinite tape are limited. Thus the infinite tape can be simulated by a finite one. This means that the tape can be simulated by a finite automaton. It follows that a turing machine $M$ that stops in no more than 50 steps is bisimilar to some finite automaton $M'$.

Let $Q$ be the set of states of $M$, $F \subset Q$ the set of accepting states and $\Gamma$ be the alphabet. Then we build the set of states $Q'$ of $M'$ as follows: $Q' = \\{ \langle n, q, s, p, a\rangle \\, | n \in \\{0,...,50\\} \\, q \in Q, s \in \Gamma, p \in \\{-50,...,50\\}, a \equiv q \in F\\}$ where $p$ is the position of the read/write head above the tape. We can restrict the position to $\\{-50,...,50\\}$ because the number of allowed computing steps limits the number of reachable positions.

Having a state $\langle n, q, s, p, a\rangle$ of the finite automaton $M'$ then means that we are at state $q$ of the original automaton, with $s$ on the tape at position $p$ where also the read/write head is positioned, after the $n$-th computing step. The state is an accepting one if $a \equiv true$.

Transforming the transition relation of a concrete turing machine is a little more work but not necessary for the original question, because it is enough to show that the state space is finite (and thus we can just test each input with a length of at most 50 symbols on each such automaton). The idea is to build a new transition relation that goes from a state $\langle n, q, s, p, a \rangle$ to a state $\langle n+1, q', s', p', a'\rangle$ in the $n$-th computing step iff the transition $\langle q, s, p\rangle \rightarrow \langle q', s', p'\rangle$ was in the original transition relation.

---
Tags: computability, undecidability
---


title: How to show a set is $\Pi_2$ complete

text:
# Question
Title: How to show a set is $\Pi_2$ complete
How can I prove that a set is complete for $\Pi\_2$ complete? Can you give me an example proof? Say for $All\_{TM}$ = Turing machines whose accepted language is all strings?

# Answer
> 3 votes
To show that the language is $\Pi^0\_2$ complete you have to show two things:

1. The language is $\Pi^0\_2$
2. Every $\Pi^0\_2$ language is many-one reducible to your language

To show that your language is $\Pi^0\_2$, informally, you need to know two things: (1) quantifiers over strings count the same as quantifiers over numbers, and (2) the predicate $P(M,\sigma)$ = "machine $M$ accepts string $\sigma$" is $\Sigma^0\_1$. Your language is a universal quantifier in front of that $\Sigma^0\_1$ relation, so it is $\Pi^0\_2$.

To show that an arbitrary $\Pi^0\_2$ language is many-one reducible to yours, it's easiest to show that some other language that you know is $\Pi^0\_2$ complete is many-one reducible to your language. The details of that will depend on what languages you already know to be $\Pi^0\_2$ complete. If you don't know any, then it helps to know that every $\Pi^0\_2$ language is definable by a formula of the form $(\forall \sigma)(\exists \tau) R(\sigma,\tau)$ where $R$ is computable.

---
Tags: computability
---


# Question
Title: How to compute linear recurrence using matrix with fraction coefficients?
What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for the $n$th Motzkin number is defined as following:

$\qquad \displaystyle \begin{align} M\_{n+1} &= M\_n + \sum\_{i=0}^{n-1} M\_iM\_{n-1-i} \\ &= \frac{2n+3}{n+3}M\_n + \frac{3n}{n+3}M\_{n-1} \end{align}$

My initial approach is to use the second formula which is obviously faster, but the problem I ran into is the division since modular arithmetic rule doesn't apply.

```
void generate_motzkin_numbers() {
    motzkin[0] = 1;
    motzkin[1] = 1;
    ull m0 = 1;
    ull m1 = 1;
    ull numerator;
    ull denominator;
    for (int i = 2; i <= MAX_NUMBERS; ++i) {
        numerator = (((2*i + 1)*m1 + 3*(i - 1)*m0)) % MODULO;
        denominator = (i + 2);
        motzkin[i] = numerator/denominator;
        m0 = m1;
        m1 = motzkin[i];
    }
}

```

Then I tried the second formula, but the running time is horribly slow because the summation:

```
void generate_motzkin_numbers_nested_recurrence() {
    mm[0] = 1;
    mm[1] = 1;
    mm[2] = 2;
    mm[3] = 4;
    mm[4] = 9;
    ull result;
    for (int i = 5; i <= MAX_NUMBERS; ++i) {
        result = mm[i - 1];
        for (int k = 0; k <= (i - 2); ++k) {
            result = (result + ((mm[k] * mm[i - 2 - k]) % MODULO)) % MODULO;
        }
        mm[i] = result;
    }
}

```

Next, I'm thinking of using matrix form which eventually can be speed up using exponentiation squaring technique, in other words $M\_{n+1}$ can be computed as follows: $$M\_{n+1} = \begin{bmatrix} \dfrac{2n+3}{n+3} & \dfrac{3n}{n+3} \\ 1 & 0\end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1\end{bmatrix}$$ With exponentiation by squaring, this method running time is $O(\log(n))$ which I guess the fastest way possible, where `MAX_NUMBERS = 10,000`. Unfortunately, again the division with modular is killing me. After apply the modulo to the numerator, the division is no longer accurate. So my question is, is there another technique to compute this recurrence modulo a number? I'm think of a dynamic programming approach for the summation, but I still think it's not as fast as this method. Any ideas or suggestions would be greatly appreciated.

# Answer
Your matrix formulation doesn't work- you need to use different $n$s in the matrices.

One idea to rescue your original approach is as follows. First, factor $10^{14} + 7 = 98794607 \times 1012201$ (only the second factor is prime). It is enough to compute $M\_n$ modulo the two factors. The first factor is smaller than $2^{32}$, so you can store the first $10000$ Motzkin numbers modulo it using only 40KB. The second factor is prime and larger than $10003$, so you can use modular division, in which you multiply with the inverse (see here for how to calculate the inverse). This only works since $n+3$ will actually have an inverse, and that's why we factored $10^{14} + 7$.
> 4 votes

---
Tags: algorithms, recurrence-relation, efficiency, integers
---


# Question
Title: Connection between castability and convexity
I am wondering if there are any connection between convex polygon and castable object? What can we say about castability of the object if we know that the object is convex polygon and vice versa.

Let's gather together few basic things that we have to know.

> The object is castable if it can removed from the mold.
>
> The polyhedron P can be removed from its mold by a translation in direction $\vec{d}$ if and only if $\vec{d}$ makes an angle of at least $90^{\circ}$ with the outward normal of all ordinary facets of P.

For a arbitrary object testing for castability has time complexity $O(n^2)$. In my opinion, for a convex polygon if could be improved to linear time, because for every new top facet we should test that the vector $\vec{d}$ makes an angle at least $90^{\circ}$ with outward normal not of all but only of two adjacent ordinary facets of P.

If this is true at least we have improvement in testing for castability in case of convex polygon.

We else can we state about castability and convexity. Especially interesting to know, if castability tells us something about convexity.

# Answer
> 5 votes
This is a proper answer but feel free to correct me I think I did not get the right definitions. This is why I begin with simple facts that should be checked first.

I suppose your are talking about $\vec v$-castability of a "open" polyhedron.

1. Indeed it seems that no "closed" polyhedron is $\vec v$-castable.
2. For every $\vec v$, a convex "closed" polyhedron can always be cut into two "open" parts among a plane of normal $\vec v$ that are $\vec v$-castable and $(-\vec v)$-castable.
3. The test of $\vec v$-castability is in $O(n)$ (even if is not convex)
4. The problem (Is there a $\vec v$ s.t. $P$ is $\vec v$-castable?) seems to be linearly reducible to the convex hull, which is in $O(n\log n)$:

1. First consider each outward normal $\vec{n\_i}$ into a point of the unit sphere.
    2. Compute $H$ the convex hull of these points.
    3. If the origin $0$ is in $H$ then for all $\vec v$, $P$ is not $\vec v$-castable.
    4. If the origin $0$ is not in $H$ then let $\vec v$ be the vector starting at the projection of $0$ on $H$ and ending at $0$. The vector $\vec v$ defines a half-space containing none of the $\vec{n\_i}$ meaning that $(\vec v, \vec{n\_i})\>90°$.
    5. If the origin $0$ is on the surface of $H$, just take the normal of $H$ in $0$ for $\vec v$.

not in the convex hull iff there exists $\vec v$ such that

1. If $P$ is convex and "open" (whatever it means), then you only need its "frontier" and the corresponding orientation. You apply the same algorithm as above on the frontier (plus the orientation vector) reducing the complexity. For a polygon it becomes in $O(1)$ if you already know the two segments on the frontier.

Hope this helps.

# Answer
> 1 votes
From Moldable and Castable Polygons by Rappaport and Rosenbloom (1994). Given the vertices of the polygon in clockwise order, 2-moldability can be determined in O(n) time, 2-castability can be determined in O(n log n) time.

---
Tags: complexity-theory, time-complexity, computational-geometry
---


# Question
Title: Introduction into first order logic verification
I am trying to teach myself different approaches to software verification. I have read some articles. As far as I learned, propositional logic with temporal generally uses model checking with SAT solvers (in ongoing - reactive systems), but what about first order Logic with temporal? Does it use theorem provers? Or can it also use SAT?

Any pointers to books or articles for beginners in this matter is much appreciated.

# Answer
> 10 votes
First order logic is undecidable, so SAT solving does not really help. That said, techniques exist for bounded model checking of first order formulas. This means that only a fixed number of objects can be considered when trying to determine whether the formula is true or false. Clearly, this is not complete, but if a counter-example is found, then it truly is a counter-example.

The tool Alloy is one tool that allows models to be described in first-order logic (though the surface syntax is based on relationally described models) and uses bounded model checking to find solutions. A SAT solver is used under the hood. One alloy extension allows models with a temporal character, though technically it does not support temporal logic.

If you wish to explore further, for example, to verify program correctness, then you can look at program verification tools. These are generally based on Hoare logic (for reasoning about pre- and post-conditions), possibly extended with Separation logic (for reasoning about heaps). These logics are generally undecidable, so a certain amount of interaction between the human and the verification tool is required. Some example tools are:

# Answer
> 11 votes
After reading your question the only way I could see and had enough knowledge to tie the topics together was to give a hi-level set of articles that drill down from software verification ending up with trying to unite model checking and theorem proving. Hopefully my comment did that:

Take a look at Software verification then Formal verification then Model checking and Formal Software Verification: Model Checking and Theorem Proving

Dave has given a good answer for which I cannot do much more justice to the first part of the question than Dave had done, since I am also new to this.

Since this is your first question at an SE site, the reason I did not give an answer but a comment is because here an answer cannot be just a set of links, but must give a written answer and use links in support of the answer; thus a comment instead of an answer.

With regards to:

> Any pointers to books or articles for beginners in this matter is much appreciated.

Books I would suggest and use are:

At present I cannot expand more on theorem proving because I am still learning the pro/cons and differences of each one, but the ones I am focusing in are

* HOL Light because of the book by John Harrison.
* Coq because it is based on Calculus of constructions
* Isabelle because it is based on higher-order unification.

These proof assistants also typically have book(s), are current, popular, open-source, maintained, and have active support communities.

Note: I used worldcat.org to reference the books, but you can review them using Amazon's look inside feature.

---
Tags: reference-request, logic, formal-methods, sat-solvers, software-verification
---


title: Advanced placement CS A Exam

text:
# Question
Title: Advanced placement CS A Exam
What would be the standard topics covered in an 'Advanced Placement Computer Science A' test? Is there any good study reference someone can share?

**Edit: Answer**

An adjustment for my search term returned a Wikipedia page just for this type of exam and the AB version.

# Answer
I used the following book as a resource material and it was pretty good:

> Barron's AP Computer Science A

You can see the book preview there along with the contents.
> 2 votes

# Answer
The Litvin book is also pretty good, as is the Princeton Guide. I have had APCS students use all 3 and wind up nickeling the test.
> 0 votes

---
Tags: reference-request, education
---