# Question
Title: How to show that a "reversed" regular language is regular
I'm stuck on the following question:

"Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{R}$ is also accepted by some finite; $L^{R}$ consists of all words of $L$ reversed."

# Answer
So given a regular language $L$, we know (essentially by definition) that it is accepted by some finite automaton, so there's a finite set of states with appropriate transitions that take us from the starting state to the accepting state if and only if the input is a string in $L$. We can even insist that there's only one accepting state, to simplify things. Then, to accept the reverse language, all we need to do is reverse the direction of the transitions, change the start state to an accept state, and the accept state to the start state. Then we have a machine that is "backwards" compared to the original, and accepts the language $L^{R}$.
> 39 votes

# Answer
You have to show that you can always construct a finite automaton that accepts strings in $L^R$ given a finite automaton that accepts strings in $L$. Here is a procedure to do that.

1. Reverse all the links in the automaton
2. Add a new state (call it $q\_s$)
3. Draw a link labeled with $\epsilon$ from state $q\_s$ to every final state
4. Turn all the final states into normal states
5. Turn the initial state into a final state
6. Make $q\_s$ the initial state

Let's formalize all of this; we start by stating the theorem.

**Theorem.** If $L$ is a regular language, then so is $L^{R}$.

Let $A = (Q\_A, \Sigma\_A, \delta\_A, q\_A, F\_A)$ be a NFA and let $L = L(A)$. The $\epsilon$-NFA $A^{R}$ defined below accepts the language $L^{R}$.

1. $A^{R} = (Q\_A \cup \\{q\_s\\}, \Sigma\_A, \delta\_{A^R}, q\_s, \\{q\_A\\})$ and $q\_s \notin Q\_A$
2. $p \in \delta\_A(q, a) \iff q \in \delta\_{A^R}(p, a)$, where $a \in \Sigma\_A$ and $q, p \in Q\_A$
3. $\epsilon-closure(q\_s) = F\_A$

*Proof.* First, we prove the following statement: $\exists$ a path from $q$ to $p$ in $A$ labeled with $w$ if and only if $\exists$ a path from $p$ to $q$ in $A^R$ labeled with $w^R$ (the reverse of $w$) for $q, p \in Q\_A$. The proof is by induction on the length of $w$.

1. Base case: $|w| = 1$
Holds by definition of $\delta\_{A^R}$
2. Induction: assume the statement holds for words of length $\lt n$ and let $|w| = n$ and $w = xa$
Let $p \in \delta\_A^\*(q, w) = \delta\_A^\*(q, xa)$
We know that $\delta\_A^\*(q, xa) = \cup\_{p'}\delta\_A(p', a)$ $\forall p' \in \delta\_A^\*(q, x)$
$x$ and $a$ are words of fewer than $n$ symbols. By the induction hypothesis, $p' \in \delta\_{A^R}(p, a)$ and $q \in \delta\_{A^R}^\*(p', x^R)$. This implies that $q \in \delta\_{A^R}^\*(p, ax^R) \iff p \in \delta\_A^\*(q, xa)$.

Letting $q = q\_A$ and $p = s$ for some $s \in F\_A$ and substituting $w^R$ for $ax^R$ guarantees that $q \in \delta\_{A^R}^\*(s, w^R)$ $\forall s \in F\_A$. Since there is a path labeled with $\epsilon$ from $q\_s$ to every state in $F\_A$ (3. in the definition of $A^R$) and a path from every state in $F\_A$ to the state $q\_A$ labeled with $w^R$, then there is a path labeled with $\epsilon w^R = w^R$ from $q\_s$ to $q\_A$. This proves the theorem.

Notice that this proves that $(L^R)^R = L$ as well.

Please edit if there are any formatting errors or any flaws in my proof....
> 39 votes

# Answer
To add to the automata-based transformations described above, you can also prove that regular languages are closed under reversal by showing how to convert a regular expression for $L$ into a regular expression for $L^R$. To do so, we'll define a function $REV$ on regular expressions that accepts as input a regular expression $R$ for some language $L$, then produces a regular expression $R'$ for the language $L^R$. This is defined inductively on the structure of regular expressions:

1. $REV(\epsilon) = \epsilon$
2. $REV(\emptyset) = \emptyset$
3. $REV(a) = a$ for any $a \in \Sigma$
4. $REV(R\_1 R\_2) = REV(R\_2) REV(R\_1)$
5. $REV(R\_1 | R\_2) = REV(R\_1) | REV(R\_2)$
6. $REV(R\*) = REV(R)\*$
7. $REV((R)) = (REV(R))$

You can formally prove this construction correct as an exercise.

Hope this helps!
> 20 votes

# Answer
Using regular expressions, prove that if $L$ is a regular language then the \emph{reversal} of $L$, $L^R=\\{w^R: w\in L\\}$, is also regular. In particular, given a regular expression that describes $L$, show by induction how to convert it into a regular expression that describes $L^R$. Your proof should not make recourse to NFAs.

We will assume that we are given a regular expression that describes $L$. Let us first look at the concatination operator ($\circ$), and then we can move onto more advanced operators. So our cases of concatenation deal with the length of what is being concatenated. So first we will break all concatenations from $ab$ to $a\circ b$. When dealing with these break the components up as much as possible: $(ab \cup a)b \rightarrow (ab \cup a) \circ b$, but you cannot break associative order between different comprehensions of course.

When $\emptyset^R \rightarrow \emptyset$

When $s = \epsilon$, we have the empty string which is already reversed thus the mechanism does not change

When $s$ is just a letter, as in $s \in \Sigma$, the reversal is just that letter, $s$

When $s = \sigma$, we have a single constituent so we just reverse that constituent and thus $\sigma^R$

When $s = (\sigma\_0\sigma\_1...\sigma\_{k-1}\sigma\_k)$ where k is odd, we have a regular expression which can be written as $(\sigma\_0\circ\sigma\_1...\sigma\_{k-1}\circ\sigma\_k)$. The reversal of these even length strings is simple. Merely switch the 0 index with the k index. Then Switch the 1 index with k-1 index. Continue till the each element was switched once. Thus the last element is now the first in the reg ex, and the first is the last. The second to last is the second and the second is the second to last. Thus we have a reversed reg ex which will accept the reversed string (first letter is the last etc.) And of course we reverse each constituent. Thus we would get $(\sigma\_k^R\sigma\_{k-1}^R...\sigma\_{1}^R\sigma\_0^R)$

When $s = (\sigma\_0\sigma\_1...\sigma\_{k/2}...\sigma\_{k-1}\sigma\_k)$ where k is even, we have a regular expression generally which can be written as $(\sigma\_0\circ\sigma\_1...\sigma\_{k-1}\circ\sigma\_k)$. The reversal of these even length strings is simple. Merely switch the 0 index with the k index. Then Switch the 1 index with k-1 index. Continue till the each element was switched once, but the k/2 element (an integer because k is even). Thus the last element is now the first in the reg ex, and the first is the last. The second to last is the second and the second is the second to last. Thus we have a reversed reg ex which will accept the reversed string (first letter is the last etc.). And that middle letter. And of course we reverse each constituent. Thus we would get $(\sigma\_k^R\sigma\_{k-1}^R...\sigma\_{k/2}^R...\sigma\_{1}^R\sigma\_0^R)$

Okay the hard part is done. Let us look to the $\cup$ operator. This is merely a union of sets. So given two strings, $s\_1, s\_2$, the reverse of $s\_1 \cup s\_2$ is only $s\_1^R \cup s\_2^R$. The union will not change. And this makes sense. This will only add strings to a set. It does not matter which order they are added to the set, all that matters is that they are.

The kleene star operator is the same. It is merely adding strings to a set, not telling us how we should construt the string persay. So to reverse a kleene star of a string $s$, is only $((s^R)^\*)$. Reversal can just move through them.

Thus to reverse this $(((a\cup b) \circ (a))^\* \cup ((a\cup b) \circ (b))^\*)^R$ we simply follow the rules. To reverse the outer union we simply reverse its two components. To reverse this: $((a\cup b) \circ (a))^\*$ kleene star, we simply reverse what is inside it $\rightarrow (((a\cup b) \circ (a))^R)^\*$. Then to reverse a concatenation, we index and then switch greatest with least. So we start with $((a\cup b) \circ (a))^R$ and get $((a)^R \circ (a\cup b)^R)$. To reverse that single letter, we reach our base case and get $(a)^R \rightarrow (a)$. This process outlined above describes an inductive description of this change.
> 2 votes

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


# Question
Title: Proof that the regular languages are closed under string homomorphism
Where can I find a proof of this? Thanks!

# Answer
> 8 votes
First of all, homomorphism is a special case of substitution. Now define the homomorphism as a substitution $h$ that replaces each symbol $a$ in an alphabet $\Sigma$ for a string $h(a) \in \Gamma^\*$, where $\Gamma$ can be another alphabet (they can perfectly be the same). Formally the homomorphism $h(\epsilon) = \epsilon$ and for all strings in $ \Sigma^\*$, $$h(a\_1a\_2\ldots a\_n) = h(a\_1)h(a\_2)\ldots h(a\_n)$$

Then you are near to proving the closure. Try induction over the number of operands (unions, concatenations, stars) in the regular expression that represents the language $L$. Base step: $h(\epsilon)=\epsilon$ for all $a \in \Sigma^\*$, $h(a)$ is a string over $\Gamma^\*$ and $h(\emptyset) = \emptyset$. The induction hyphotesis says that if $L$ is regular, then $h(L)$ is regular. The inductive step has three cases: $L$ as a union of $A$ and $B$ ($A \cup B$), $L$ as the concatenation of $A$ and $B$ ($L=AB$) or $L = A^\*$. Then you should be able to finish the proof.

# Answer
> 6 votes
It is a special case of a more general result: rational subsets of monoids are closed under morphisms.

The set of *rational subsets* of a monoid $M$ is the smallest set of subsets of $M$ containing the finite subsets and closed under union, product and star. The product of two subsets $X$ and $Y$ of $M$ is the set $XY = \\{ xy \mid x \in X, y \in Y \\}$ and $X^\*$ is the submonoid generated by $X$.

Now if $f: M \rightarrow N$ is a monoid morphism and $R$ is a rational subset of $M$, then $f(R)$ is a rational subset of $N$. If further $f$ is surjective, then for each rational subset $S$ of $N$, there exists a rational subset $R$ of $M$ such that $f(R) = S$.

This is Proposition 2.2, p. 48 of the book by J. Berstel, Transductions and context-free languages, Teubner (1979). This book is out of print, but the first four chapters can be found here.

# Answer
> 3 votes
Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^\*$. Extend $\varphi$ to a function from $\Sigma^\* \rightarrow \Delta^\*$ such that: \begin{eqnarray\*} \varphi(\varepsilon) & = & \varepsilon \\ \varphi(w\sigma ) & = & \varphi(w)\varphi(\sigma ), \textrm{ for any } w \in \Sigma ^\*, \sigma \in \Sigma \end{eqnarray\*} Any function $\varphi:\Sigma^\* \rightarrow \Delta^\*$ defined in this way from a function $\varphi: \Sigma \rightarrow \Delta^\*$ is called a **homomorphism**. We can extend this definition to languages as follows: for any language $L$ and homomorphism $\varphi$, let $$\varphi(L)=\\{\varphi(w) : w\in L\\}.$$

If $L$ is a regular language, then we can construct a Regular Expression, $X$, for $L$. Now we must prove $\varphi(L)$ is regular, which means we must construct a Regular Expression $Y$ for $\varphi(L)$. Then we must prove that the set of strings accepted by $Y$ is a subset of those accepted by $\varphi(L)$, and the set of strings accepted by $\varphi(L)$ is a subset of those accepted by $Y$, thus proving they are equivilent.

Construct: First is our construction. The way that we will create our Regular Expression is simple. Apply $\varphi(L)$ to each symbol in $X$. This will give us the regular expression $Y$.

$Y \subseteq \varphi(L)$: We can easily see any string accepted by the regular expresion $Y$ must be in $\varphi(L)$. All accepted by $Y$ must first follow the original rules of $X$, but each symbol in $X$ has now been processed by $\varphi$ and thus each string accepted by $Y$ must be accepted by $\varphi(L)$.

$ \varphi(L) \subseteq Y$: Once again this is not that hard. All strings that are accepted by $\varphi(L)$ must first follow the regular expression $X$, but rather than use the old symbols, will have them put through $\varphi$ first. This is the definition of $Y$ so easy to see.

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


title: Reference for an undecidability proof

text:
# Question
Title: Reference for an undecidability proof
I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch".

With "from scratch" I mean that it does not use some other undecidable problem to prove some undecidability (which is the usual case), I cannot wrap my mind about how proving undecidability that way (without a previous proof) could be possible.

This question may be inspiring: An example of an easy to understand undecidable problem

Also, I know this is probably not very objective, but it is important to me, it should be something as simple as possible, hopefully enough so that even I can understand it.

# Answer
> 1 votes
to some degree all refs on the subject have a formidable inherent complexity due to the subject matter. however, here is a classic, highly accessible ref on Gödel's thm that may be helpful, written in "popular science" style by a philosopher & mathematics historian for a broad audience, breaking it down into intuitive everyday language.

here are some other similar but more technical refs that may be helpful

there are also many refs on Turing's halting problem. one worth mentioning, a step-by-step walkthrough/tour of the original proof, but which is very advanced due to retaining all the mathematical complexity/detail:

on the other hand most of the proof complexity of the halting problem is associated with the proof of the existence of the Universal TM, wikipedia has a pretty good outline. this can be understood as a simulation or emulation of one machine by another. therefore studying the theory of machine emulation (now quite frequently applied with video games) may be helpful.

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


# Question
Title: Are regular languages closed under inverse homomorphism?
Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^\*$. Extend $\varphi$ to a function from $\Sigma^\* \rightarrow \Delta^\*$ such that: \begin{eqnarray\*} \varphi(\varepsilon) & = & \varepsilon \\ \varphi(w\sigma ) & = & \varphi(w)\varphi(\sigma ), \textrm{ for any } w \in \Sigma ^\*, \sigma \in \Sigma \end{eqnarray\*} Any function $\varphi:\Sigma^\* \rightarrow \Delta^\*$ defined in this way from a function $\varphi: \Sigma \rightarrow \Delta^\*$ is called a **homomorphism**. We can extend this definition to languages as follows: for any language $L$ and homomorphism $\varphi$, let $$\varphi(L)=\\{\varphi(w) : w\in L\\}.$$

Are regular languages are closed under inverse homomorphism?

# Answer
> 9 votes
Yes, regular languages are closed under inverse homomorphism.

Here is a proof. We start with a DFA of $L$, $X$. To prove that $\varphi^{-1}(L)$ is regular, we will construct a DFA, $Y$ for $\varphi^{-1}(L)$.

$$ X = (Q,\Sigma,\delta\_X,q\_0,F)$$

So our construction will be as follows:

$$ Y = (Q,\Delta,\delta\_Y,q\_0,F)$$

Where:

$$\delta\_Y(q,w) = \hat{\delta\_X}(q,\varphi(w))$$

Or in other words, the transition in Y on w is the result of the sequences of transition that X makes on the string of symbols $\varphi(w)$. So all we need to do now is prove this transition. To do this we will induct on $|w|$. Our hypothesis being $\hat{\delta\_Y}(q,w) = \hat{\delta\_X}(q,\varphi(w))$.

**Base:** When $w = \epsilon$:

$$q\_0 = \delta\_Y(q\_0,\epsilon) = \delta\_X(q\_0,\varphi(\epsilon)) = \delta\_X(q\_0,\epsilon) = q\_0$$

**Inductive Step:** First let $w = \sigma s$:

$$\hat{\delta\_Y}(q\_0,w) = \hat{\delta\_Y}(\delta\_Y(q\_0,\sigma),s)$$

Then by our inductive hypothesis:

$$\hat{\delta\_Y}(\delta\_Y(q\_0,\sigma),s) = \hat{\delta\_Y}(\delta\_X(q\_0,\varphi(\sigma)),s)$$

Now by our DFA definition above:

$$\hat{\delta\_Y}(\delta\_X(q\_0,\varphi(\sigma)),s) = \hat{\delta\_X}(\delta\_X(q\_0,\varphi(\sigma)),\varphi(s))$$

Pulling the $\delta$ back in:

$$\hat{\delta\_X}(\delta\_X(q\_0,\varphi(\sigma)),\varphi(s)) = \hat{\delta\_X}(q\_0,\varphi(\sigma)\varphi(s))$$

Now by the definition of homomorphism:

$$\hat{\delta\_X}(q\_0,\varphi(\sigma)\varphi(s)) = \hat{\delta\_X}(q\_0,\varphi(\sigma s)) = \hat{\delta\_X}(q\_0,\varphi(w))$$

# Answer
> 7 votes
**Short algebraic proof**. Let $M$ be a monoid recognizing a language $L$ of $A^\*$. By definition, this means that there is a monoid homomorphism $\eta: A^\* \to M$ and a subset $P$ of $M$ such that $L = \eta^{-1}(P)$.

Let $\varphi: B^\* \to A^\*$ be a monoid homomorphism. Then $\eta \circ \varphi: B^\* \to M$ is also an homomorphism. Further, the equality $\varphi^{-1}(L) = \varphi^{-1}(\eta^{-1}(P)) = (\eta \circ \varphi)^{-1}(P)$ shows that the language $\varphi^{-1}(L)$ is also recognized by $M$.

Now a well-known result states that a language is regular if and only if it is recognized by some finite monoid. It follows immediately that if $L$ is regular, then $\varphi^{-1}(L)$ is also regular.

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


title: How do computers compute?

text:
# Question
Title: How do computers compute?
This is a kind of follow-up to a question I asked on superuser, where I asked for the definitions of a 'distinghuisable state' and a 'memory cell'. My questions where properly answered, but I was still confused about a certain matter.

I'm reading this little paper, and in particular these sentences:

> To perform useful computation, we need to irreversibly change distinguishable states of memory cell(s) .... So the energy required to write information into one binary memory bit is $E\_{bit}= k\_BT \ln2$

So my interpretation of this is that the author says that to compute, you need to change the state of bits ($ 0 \rightarrow 1$, $1 \rightarrow 0$) in order to compute.

But is that actually a reasonable statement? I'm not really interested in the rest of the paper, only this part. Do computers (I'm not talking about supercomputers, or future computers which use qubits and whatnot, but just your average computer) compute using bits with 2 dinstinghuisable states?

I actually was able to find this so-called 'SNL-expression' somewhere else, namely this pdf, on page 223; it's actually a part of MIT's ocw.

# Answer
> 6 votes
I'm not entirely sure if I understood the question the way it was intended, but what computers do is that they operate on electricity, so they don't have two discrete logical values $0$ and $1$ per se. What they do have is electricity with voltage, and they are made to operate as if there were two logical values $0$ and $1$ if the voltage at a gate is below a certain threshold (for $0$; for example, below 0.5mV) or above another threshold (for $1$, for example, above 2.5mV) with a reasonable distance between those two threshold values. Anything in between will give the processor undefined behaviour.

What processors then do is operate on the logical values $0$ and $1$ that were abstracted from the continuous voltages. The hardware implements functions using boolean logic, meaning functions of the kind $\\{0,1\\}^n \to \\{0,1\\}^m$. For an introduction to how these things are implemented in hardware, see for example the material found here. It starts out with boolean logic, and by chapter 4 p. 3 everything needed to build an adder (meaning a circuit that implements addition) has been explained. It's a total of 23 pages to read until then, so you can decide if you would like to spend the hour or two it takes to read through it (and another hour to reread for understanding).

The circuits that don't have a way to store values are called combinational circuits, and those are used to implement the most basic functions in hardware (for example, addition, multiplication, logical operations like OR, AND, XOR for binary vectors). Circuits that can store values are called sequential circuits, and they utilize techniques where the input of gates are interdependent, and the circuits have well defined stable states. For an introduction to that, see for example here. Don' be disappointed if you can't quickly grasp that - I for one had a bit of trouble with comprehending sequential circuits initially.

For a small summary on how circuits are built from the elemental building blocks called transistors, see for example here. It only summarizes the working of transistors without all the electromechanics that go into it. Basically a transistor has a source (input) where we can apply a voltage, a gate where we can apply a voltage to control whether the input is inverted or not, and a drain (output). Depending on what type of transistor we use, the gate allows transmission from source to drain if we apply a $0$ (for nMOS transistors) or a $1$ (for pMOS transistors) to the gate.

Note that all of this is actually not computer science related, it's electrical engineering. If you would like to find out more about circuits in depth, I would advise you to ask on electronics.SE.

# Answer
> 4 votes
I suggest you start by reading about reversible computing. In principle, if we could make sure that all of our computations were reversible, we could circumvent that physical limit. In principle, all computations can be made reversible by keeping track of extra information about the inputs or the states the computation went through.

In practice, there's a problem: to make computation reversible, we have to keep around extra useless garbage bits that exist only to enable reversibility. The more computation we do, the more these bits accumulate. Eventually, you're going to want to erase those bits (or somehow avoid storing them forever). At that point, you're going to incur the thermal cost, so we're back to a need to make irreversible changes, with the corresponding unavoidable energy costs.

There's a lot more one can say about this, and a lot of sophisticated thinking about the subject. I'm just scratching the surface, but the key phrase "reversible computing" should be enough to help you find additional literature and research and writing on this topic.

All of this is highly theoretical right now, as modern computing technology consumes much more power than the the lower bounds suggested by physics. At this point, the main barrier to reducing energy computation is engineering, not fundamental physical barriers. But you could imagine that if the engineering advances far enough, eventually (someday) the barrier to reducing energy costs further might be these sorts of physical limits.

---
Tags: entropy, memory-hardware
---


title: linklist and memory issues

text:
# Question
Title: linklist and memory issues
I have a doubly link-list like this

```
typedef struct Record
{
   int i;
   Record* next;
   Record* prev;
}Record;

```

I have over 5 trillions of records that I need to handle, now that I need to retrieve all of them and sort them out. If its size was small, I could borrow stl's vector or list to do the job but now that it is too huge, I have no idea how to save the object data before sorting is performed

my function prototype

```
void sortRec(Record**recToSort,bool bASC){}

```

# Answer
You should also have a look at External Sorting algorithms. This is another book on the subject Algorithms and Data Structures for External Memory
> 2 votes

# Answer
Assuming that the records are really stored in the disk, you can use radix sort. Divide you integer into bytes, and start with the lower-order byte. Open 256 new files, and start going over your database in order, sorting the files according to the lower-order byte. Then do it again with the next byte, this time reading your 256 files in order.

If memory is not at a premium, you could always allocate an array - that will actually be more memory-efficient than a linked list. (Why would you use a linked list for such a big array anyhow? The overhead is 200%.)
> 1 votes

# Answer
You can merge-sort a list in memory.

Let split(a)-\>(b,c) be a function that splits the list a so that approximately half the number of elements go into b and the rest goes into c. Time for split should be T(n).

Let merge(a,b)-\>c be a function that merges the two ordered list a and b into an ordered list c. Time for merge should be T(n).

Sorting can then be performed in O(n\*log(n)):

```
def sort(a):
    if len(a) <= 1:
        return a
    b, c = split(a)
    return merge(sort(b), sort(c))

```
> 1 votes

---
Tags: algorithms, data-structures, data-mining, linked-lists
---


# Question
Title: An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries
---

Is there an incremental directed graph data structure that has the following properties:

* Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-structures)
* The accessible DAG is kept as a transitive reduction (notwithstanding other helper data-structures)
* It should be optimized for a sparse graph (adjacency lists)
* It should condense cycles as they are introduced, keeps a mapping between equivalent vertices that are all replaced with one "representative" vertex
* Ability to quickly answer quickly ancestor/descendant/transitive/relationship queries (in $\mathcal{O}(1)$ or $\sim\mathcal{O}\left(\log \left|V\right|\right)$ time)
* Should support vertex, edge insertion, deletion would be nice too
* Mutable operations (such as insertion) should be as output-sensitive as possible; in other words, the complexity should depend as much as possible on how much the operation must change the graph
* Ability to record changes over an operation, if requested. Obviously this might necessarily increase the complexity, but the increase should be output-sensitive. Examples:
    + set of deleted vertices (due to condensation)
    + set of deleted edges (due to reduction)
    + set of new decendent relationships from $u$ ( example: $insert(G,u,v) \rightarrow \left\\{t ~|~ path(u,t)\in G'\wedge path(u,t)\not\in G\right\\}$ )
    + set of new ancestor relationships from $v$ ( example: $insert(G,u,v) \rightarrow \left\\{t ~|~ path(t,v)\in G'\wedge path(t,v)\not\in G\right\\}$ )

The closest I can find is here, implementation. I think you can build on this to do have most of the properties I list, but I am wondering if there is anything better/well known, or perhaps if there is a name for this problem.

---

**EDIT:**

### Related:

# Answer
Some keywords to help you search for related work: dynamic transitive closure, dynamic reachability problem, dynamic cycle detection. Because you want to allow both insertions and deletions, this is known as fully dynamic transitive closure.

Alternatively, you might want to consider whether there could be some structure in the particular graphs that arise in your setting that might help you build schemes that are faster than the general case.
> 5 votes

---
Tags: algorithms, data-structures, graphs, shortest-path, online-algorithms
---


# Question
Title: does godel's incompleteness theorem shed any light on dynamic vs typed languages?
I'm clojure user myself. I'm trying really hard to learn haskell and to better understand the type system. However, I feel that trying to 'type' everything is quite restrictive when the problem or the data is less defined.

I intuitively feel that godel's incompleteness theorem offers some insight into the typed/untyped debate. What are some simple problems that may trip up the typing system but not untyped ones?

---

According to http://en.wikipedia.org/wiki/Type\_theory. "The types of type theory were invented by Bertrand Russell in response to his discovery that Gottlob Frege's version of naive set theory was afflicted with Russell's paradox. This theory of types features prominently in Whitehead and Russell's Principia Mathematica. It avoids Russell's paradox by first creating a hierarchy of types, then assigning each mathematical (and possibly other) entity to a type. Objects of a given type are built exclusively from objects of preceding types (those lower in the hierarchy), thus preventing loops."

Godel's theorem invalidated Principia Mathematica. What consequence does it have on Type Theory.

# Answer
So, Godel's incompleteness theorem says, if I recall correctly, that any sufficiently powerful logical system cannot be both consistent and complete. A good type system is concsistent, so it must be incomplete, that is, it contains well-typed programs which will fail to compile.

In practice, this isn't often a problem. Why? Because type inference and type checking are two separate things. Type inference is usually undecidable, and involves taking an expression and determining its type. Most type inference algorithms are imperfect, that is, they can't always infer the type of an expression.

Type-checking, on the other hand, is easy. If you know the types of expressions in a program, it's dead easy to determine if it's well typed. So, all you have to do is, find the cases where the type inference engine needs help, explicitly tell it what the types are, and it's good to do the checking. This is why Haskell and ML still let you write signatures.

As DW says, any problem you can solve in Clojure you can solve in Haskell. A type checker doesn't change this at all. All a type checker does is, at compile time, finds things which could cause bugs at runtime.

For the most part, if it works on Clojure but not in Haskell, it means there will be a bug in your Clojure code. Dynamic typing is popular because you can write quickly, but dangerous because the compiler doesn't tell you when you mess up.
> 4 votes

# Answer
Haskell is Turing-complete. That means, any computation that can be expressed in Clojure, can also be expressed in Haskell (and vice versa). Consequently, there is no difference in the expressibility of the two languages. This remains true despite the type system.

I'm not aware of any insight that Godel's incompleteness theorem offers into whether statically typed languages are "better" than untyped languages (for some unspecified definition of "better").
> 5 votes

---
Tags: type-theory
---


# Question
Title: Drawbacks of repeating a single pattern matching procedure for many patterns
One naive approach in solving *multiple pattern matching* problem is to call *single pattern matching* procedure on each of the pattern.

There **must** be some drawbacks in this approach, given the variety of multiple pattern matching algorithms such as Aho Cornsick algorithm, which prove to be more efficient.

So what are the drawbacks on this straightforward yet naive approach? In what scenario is this algorithm doing unnecessary works?

# Answer
One common way of solving pattern matching problems is compiling a DFA that matches the pattern. If you have several patterns in mind, you can combine all of them into a single DFA, which will match all of them with a single pass, rather than one pass per pattern. On the flip side, the DFA could have many states and so might not fit into cache, which would cause a performance hit.
> 1 votes

# Answer
A simple case in which repeated pattern matching is inefficient would be if some patterns are prefixes of others. Many of the standard algorithms can efficiently report occurrences of a prefix of a pattern at no additional cost.
> 1 votes

---
Tags: algorithms, search-algorithms, strings, substrings
---


# Question
Title: Is the set of all valid C programs countable?
Is the set of all syntactically valid C programs countable or uncountable?

# Answer
Infinite. Countable. Given a length $l$, and a finite number of characters, $c$, we know that each length has only finitely many possible valid c codes $c^L$. We can easily make a bijection from the natural numbers to the lengths, and at each length we add only finite number of other valid code, thus countable.
> 2 votes

# Answer
Your compiler effectively solves the word problem for C along the way. Therefore, the language of all C programs is decidable. This directly implies that it is countable.

> For any decidable language, build your bijection with $\mathbb{N}$ like this: enumerate *all* strings according to a fixed order and without repetition. Check for each whether it is in the language using your decider. On input $n$, output the $n$-th string the decider accepts. For the other direction, just count the number of accepted strings until you reach the input string.
> 0 votes

---
Tags: formal-languages, programming-languages, uncountability
---


# Question
Title: One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP
Let $a$ one decision problem and $A$ one algorithm solving it in $O(n^k)$.

But, to construct $A\_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using certain general algorithm $R$ in $O(2^n)$.

Obiously, $A$ is polynomial (then, all $A\_n$ are in **P**) and $R$ is exponential.

We **can not** solve big instances because $R$ is not practical.

But, in practice, we will can solve big instances after a big effort computing $A\_n = R(n)$.

My question is twofold:

* How are such problems considered in theory? Have they been studied explicitly? Is there a particular case? some literature to read?
* How are such problems solved in practice? Have they been studied in general? Is there is a particular case? some literature to read?

# Answer
If the "thing" is polynomial-size, then it's in P/poly, a class that has been studied intensively, although this is a very interesting subclass of it which I don't believe been studied. If you have an algorithm that falls into this subclass, I believe theoretical computer scientists might be interested in it.

If the "thing" can be exponential size, then the "thing" could just be a table of all the answers for the instances of size $n$, so all algorithms in EXPTIME would fall into this class. And in fact, this class would be equal to EXPTIME, since the algorithm R followed by A is in EXPTIME.
> 7 votes

---
Tags: complexity-theory, decision-problem, np
---


# Question
Title: Number of 1 child nodes in a binary tree
Does anybody know how would I approach calculating the maximum number of 1 child nodes (nodes that have exactly 1 child) in a binary tree with n nodes. Please don't give me the actual answer as this is one of the homework problems, I would like to solve it by myself, but I simply don't know where to start. Any help is apreciated.

# Answer
> 1 votes
Try to construct a tree with a lot of 1-child nodes. Start with the root. Let's say the root has exactly one child. Let's say that that child itself has exactly one child, etc.

> So in a tree with $n$ nodes, you can arrange for all but one to have a single child. This means the maximum is at least $n-1$, and of course it's at most $n$. Finally, prove that the maximum isn't $n$: there has to be at least one leaf (0-child node).

---

I think the maximum over trees of a given depth is a little more interesting. What's the maximum number of 1-child nodes you can cram in a binary tree of depth $n$?

For depth $0$, there's a single leaf, so the maximum is $0$. For depth $1$, enumeration shows that the maximum is $1$. More generally, what tree shape maximizes the number of one-child nodes?

---
Tags: binary-trees
---


# Question
Title: How do you say when a language is Turing-complete only in a trivial way?
I didn't know how to ask this question before but now that I'm reading about typed lambda calculus I think I've got a better idea.

There is this answer to a question asking whether CSS is Turing complete or not (note that this question is NOT about CSS at all), which I consider is not (at least in certain way, and this "certain" is what my question below is about), even if you can simulate Rule 110 with it, which is proven to be Turing complete. My intuition behind it is that only an insignificant subset of what CSS can output can be the result of a calculation. You cannot perform any calculation on colors or sizes to be set to element's styles.

Now I found an even simpler example while reading about typed lambda calculus. This article's overview describes a lambda calculus that can use booleans. I noticed that, in addition to the untyped lambda calculus operations, there is the conditional operation (`if t1 then t2 else t3`), which makes perfect sense. Without this, you wouldn't be able to do anything with booleans, and I would go ahead and say is really not Turing complete, or at least that is Turing complete but only in a trivial way.

So my question is, if this typed lambda calculus with booleans wouldn't have that conditional operator, would you say is Turing complete? If not, why not, and if yes, how would you express the fact that you cannot do any operation at all on it's main type of data which is what you'd expect from any Turing complete language in a categorical, technical way such that is clear that the Turing completeness of the language is really meaningless?

The reason why I'm giving so much importance to this is because I was recently trying to create a small Turing complete language myself and while doing it, got to a point in which my language was Turing complete but only in this trivial way (wasn't as obvious as the boolean lambda calculus without conditionals above, though). If I would have asked "Is this language Turing complete?" I would have probably got "Yes" as an answer and I would've think I'm done creating my language. But I really was not. And when asking myself why am I still working on my language, I'd like to be able to state exactly what is that my language is missing.

# Answer
Untyped or simply-typed lambda-calculus is Turing-complete even with no booleans at all. Adding more stuff in the language, such as boolean constants and a boolean base types, cannot make the language less powerful, therefore it is still Turing-complete.

“Turing-complete” means that there is some “reasonable encoding” under which the language can express arbitrary computations. “Reasonable encoding” is not a formal notion; what it really means is that you must say what you consider to be computation, and how natural integers are to be encoded. For example, in the lambda-calculus, computation is beta reduction, and one possible encoding of natural integers is Church numerals.

In the simply-typed lambda calculs, there are no booleans as a built-in notion, but they can be encoded: $$\begin{align} \mathsf{true}\_\tau &:= \lambda x\colon\tau. \lambda y\colon\tau. x \\ \mathsf{false}\_\tau &:= \lambda x\colon\tau. \lambda y\colon\tau. x \\ \mathsf{ifthenelse}\_\tau &:= \lambda f\colon\tau. \lambda g\colon\tau. \lambda b\colon(\tau\rightarrow\tau\rightarrow\tau). b \\, f \\, g \\ \end{align}$$

The lambda calculus with boolean constants but no corresponding destructor¹ nor any way to encode it (such as a polymorphic equality construct) does lack expressive power in a sense, but only in that it is unable to distinguish between the two boolean values. It isn't the language's computational power which is at state, but the particular encoding of booleans as the boolean constants you picked: the boolean data structure is not implemented correctly. In fact, that language does not have any boolean data structures: it has constants that you chose to call “true” and “false”, but that doesn't make them booleans given the lack of a destructor.

Consider a variant where you define the following constructors and destructor: $$ \dfrac{}{\Gamma \vdash \mathsf{dog} : \mathsf{daisy}} \qquad \dfrac{}{\Gamma \vdash \mathsf{cat} : \mathsf{daisy}} \qquad \dfrac{\Gamma \vdash M : \mathsf{daisy} \quad \Gamma \vdash N\_0 : \tau \quad \Gamma \vdash N\_1 : \tau}{\Gamma \vdash \mathsf{cheese}(M, N\_0, N\_1) : \tau} \\ \dfrac{}{\Gamma \vdash \mathsf{true} : \mathsf{boolean}} \qquad \dfrac{}{\Gamma \vdash \mathsf{false} : \mathsf{boolean}} $$ and the following reduction rules: $$\begin{align} \mathsf{cheese}(\mathsf{dog},M,N) &\to M \\ \mathsf{cheese}(\mathsf{cat},M,N) &\to N \\ \end{align}$$

This language has an encoding of the booleans as the type $\mathsf{daisy}$, with $\mathsf{cat}$ and $\mathsf{dog}$ as the constructors and $\mathsf{cheese}$ as the destructor. The type $\mathsf{boolean}$ is not a boolean type: it's just some type that happens to have two values (which are undistinguishable).

A “typed lambda calculus with booleans \[without\] that conditional operator” is a Turing-complete language that doesn't have booleans.

¹ <sub> A destructor in a typed calculus is a term such that a type constructor appears in the premises of its typing rules but not in the type of its conclusion. If/then/else is a destructor for booleans. </sub>
> 3 votes

---
Tags: lambda-calculus, turing-completeness
---


# Question
Title: Performance of row- vs. column-wise matrix traversal
Scott Meyers describes here that traversing a symmetric matrix row-wise performes significantly better over traversing it column-wise - which is also significantly counter-intuitive.

The reasoning is connected with how the CPU-caches are utilized. But I do not really understand the explanation and I would like to get it because I think it is relevant to me.

Is it possible to put it in more simple terms for somebody not holding a PhD in computer architecture and lacking experience in hardware-level programming?

# Answer
In today's standard architectures, the cache uses what is called "spatial-locality". This is the intuitive idea that if you call some cell in the memory, it is likely that you will want to read cells that are "close by". Indeed, this is what happens when you read 1D arrays.

Now, consider how a matrix is represented in the memory: a 2D matrix is simply encoded as a 1D array, *row by row*. For example, the matrix $\left(\begin{array}{ll} 2, 3 \\4, 5\end{array}\right)$ is represented as $2,3,4,5$.

When you start reading the matrix in cell $(0,0)$, the CPU automatically caches the cells that are close by, which start by the first row (and if there is enough cache, may also go to the next row, etc).

If your algorithm works row-by-row, then the next call will be to an element still in this row, which is cached, so you will get a fast response. If, however, you call an element in a different row (albeit in the same column), you are more likely to get a cache miss, and you will need to fetch the correct cell from a higher memory.
> 5 votes

---
Tags: cpu-cache, performance
---


# Question
Title: Can I express 100 as a three-digit 9's complement number?
Reading the Appendix A (*Binary numbers*) of *Structured Computer organization* by Tanenbaum I've found this exercise:

> Signed decimal numbers consisting of $n$ digits can be represented in $n + 1$ digits without a sign. Positive numbers have $0$ as the leftmost digit. Negative numbers are formed by subtracting each digit from $9$. Thus the negative of $014725$ is $985274$. Such numbers are called **nine**’s complement numbers and are analogous to one’s complement binary numbers. Express the following as three-digit **nine**'s complement numbers: $6$. $-2$, $100$, $-14$, \[etc\].

Ok, it all works fine with $6$ for instance: using the given rule it is $006 \mapsto 993$. That makes sense: as Tanenbaum says this system for negative-value representation is similar to **one**'s complement: it has two different *zero* representation ($000$ and $999$) and it has negative possible value as much as the positive ones.

What I don't understand is how can $100$ fit in this scenario. To me, with 3 digits I ca only represent value in range $\[-900, 099\]$; moreover $100$ is *not* considered a *positive* number --it shoudl have a $0$ as leftmost digit.

Is there an error in Tanenbaum-exercise?, if not, where I'm wrong?

# Answer
Nine's complement representation involves a choice of the exact range of positive and negative numbers. It is natural to let the sign depend on the MSD (most significant digit). It is even more natural to declare that numbers starting with $0,1,2,3,4$ are positive, those starting with $5,6,7,8,9$ are negative. The range of three-digit numbers is then $-500$ to $499$ rather than $-900$ to $99$, and $100$ becomes representable. I suspect that this interpretation is what Tanenbaum intended.
> 1 votes

---
Tags: binary-arithmetic
---


# Question
Title: What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?
Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero one at a time what will be minimum number of operations (i.e multiplications) I will need. For example, for the matrix

$\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}$

the answer is two. For this example

$\begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$

the answer is two not three.

Any help to go for head start is appreciated.

# Answer
Hint: Reduce to bipartite vertex cover, which can be solved efficiently.
> 3 votes

---
Tags: algorithms, complexity-theory, graphs, data-structures, discrete-mathematics
---


# Question
Title: Regular expression for a string not containing a set of substrings
I'm trying to figure out how to build a regular expression for a language that doesn't contain strings that contain $101$ or $001$. The alphabet is defined as $\\{0, 1\\}$. I'm stuck on trying to figure out the DFA. Any help would be appreciated.

# Answer
**Hint.** Let $A = \\{0,1\\}$. A regular expression for the complement of your language $L$ is $A^\*(101 + 001)A^\* = A^\*A01A^\*$. Now, as Shaull reminded you, $L$ and its complement have the same minimal complete DFA, up to the final states. It is actually relatively small.

If you prefer, you could also take a purely combinatorial approach. Observe that the strings you want to avoid are $101$ and $001$. It means that if a word $u$ of $L$ contains the pattern $01$, then $01$ has to be a prefix of $u$. Now find a regular expression for the set of words not containing the pattern $01$ and from there you should be able to find a regular expression for $L$.
> 3 votes

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


title: Finding asymptotic time complexity

text:
# Question
Title: Finding asymptotic time complexity
So I'm studying for a midterm and my professor put out a sample exam with the answers, and I'm stuck on one of the questions.

The answer is `Big-O(n^2 log n)`

Could someone show me the steps necessary to go from regular time complexity to asymptotic time complexity?

# Answer
Informally:

There are two applicable rules here, wrt. a polynomial:

1. You can throw away the constant coefficients of each term.
2. The fastest growing term is the only one that matters, since as $n \rightarrow \infty$ (approaches infinity), the other terms will be insignificant.

So due to rule 1, $20n^2 + 2n^2\log n - 2n + 1$ becomes $n^2+n^2\log n - n + 1$.

Now, only the largest-growing term here will be significant. The other terms will be insignificant when $n \rightarrow \infty$. The two first terms are obviously much faster growing, since they have an exponent of $2$. The second term is faster than the first because it has a non-constant multiplier that is more than $1$ as $n$ approaches infinity; it will thus make the term grow faster. Thus the second term becomes the only one remaining.

Now for the math:

### How do we know we can throw away constants?

Because, let $f(x)$ be that term, then $af(x) \in \mathcal{O}\left(f(x)\right)$, where $a$ is a constant, not dependent on $x$. What this means, is that $f(x)$ will *grow at the same **rate*** as $af(x)$, (as $x \rightarrow \infty$), even if it will always be larger by a multiplicative constant. How can we prove this?

The definition of $f(x) \in g(x)$:

$$|f(x)| \le \\; M |g(x)|\text{ for all }x\>x\_0.$$

Where $M$ is some positive constant, and there exists some $M$ and $x\_0$ that makes this true.

So let's set $g(x)=f(x)$:

So the question becomes: Does there exist an $M \> 0$ and $x\_0$ such that this holds true?

$$|af(x)| \le \\; M |f(x)|\text{ for all }x\>x\_0.$$

The answer is simple: set $M=|a|$, then we get $|af(x)| \le \\; |af(x)|\text{ for all }x\>x\_0$, which is of course true, since they are actually equal. And since this is true, we get $af(x) \in \mathcal{O}\left(f(x)\right)$ as per the formal definition of big O notation.

### How do we know we only care about the fastest growing term in a polynomial?

See wikipedia section on properties of big O notation:

> If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example
>
> $f(n) = 9 \log n + 5 (\log n)^3 + 3n^2 + 2n^3 = O(n^3) \\,, \qquad\text{as } n\to\infty \\,\\!.$
>
> In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial.

To prove this, we need to prove that given two terms in a polynomial, if one grows as fast or faster than another, then the entire polynomial is as fast as the faster growing term. Formally:

$\left.f(x) + g(x) \in \mathcal{O}\left(f(x)\right) \vphantom{\Bigg|} \right| \_{g(x)\in \mathcal{O}\left(f(x)\right)}$

Translation: term $f(x)$ plus term $g(x)$ is as fast as $f(x)$ if $g(x)$ is bounded by $f(x)$ (bounded means: grows at most as fast as).

Proof of this statement:

$$ \begin{eqnarray} &&&\hspace{2pt}&\hphantom{(1)}&\hspace{1pt}& \\ \exists\_{x\_0,M\>0} ~ \left|f(x) + g(x)\right| &\stackrel{?}{\le}& M\left|f(x)\right| ~~~x\>x\_0 \text{ as } x\rightarrow \infty &&(1)&&\text{Reformulate question} \\ g(x) &\in& \mathcal{O}\left(f(x)\right) &&(2)&&\text{Given} \\ \exists\_{x\_{g0},M\_g\>0}~\left|g(x)\right|&\le&M\_g\left|f(x)\right| &&(3)&&\text{Restatement of (2)} \\ &&~~~x\>x\_{g0} \text{ as } x\rightarrow \infty \\ f(x) &\in& \mathcal{O}\left(f(x)\right) &&(4)&&\text{Reflexive} \\ \exists\_{x\_{f0}=0,M\_f=1}~\left|f(x)\right|&\le&M\_f\left|f(x)\right| &&(5)&&\genfrac {}{}{0}{}{\text{Restatement of (4) via}}{\text{def., choosing values}} \\ &&~~~x\>x\_{f0} \text{ as } x\rightarrow \infty \\ \exists\_{ \genfrac{}{}{0}{} {x\_{f0},x\_{g0}} {M\_f=1,M\_g\>0} } ~|f(x)|+|g(x)|&\le& M\_f\left|f(x)\right|+M\_g\left|f(x)\right| &&(6)&&\text{Adding (3), (5)} \\ && ~~~x\>\max\left(x\_{f0},x\_{g0}\right) \text{ as } x\rightarrow \infty \\ &\le& \left(M\_f+M\_g\right)\left|f(x)\right| &&(7)&&\text{Simplying (6)} \\ &&~~~x\>\max\left(x\_{f0},x\_{g0}\right) \text{ as } x\rightarrow \infty \\ |f(x)+g(x)| &\le&|f(x)| + |g(x)| &&(7.1)&&\text{Math} \\ \exists\_{ \genfrac{}{}{0}{} {x\_{0}=\max\left(x\_{g0},x\_{f0}\right)} {M=M\_f+M\_g} }~\left|f(x)+g(x)\right|&\le& M\left|f(x)\right| ~~~x\>x\_0\text{ as } x\rightarrow \infty &&(8)&&\text{Simplifying (7,7.1)} \\ M\_f &=& 1 &&(9)&&\text{Valid/chosen in (5)} \\ x\_{f0} &=& 0 &&(10)&&\text{Valid/chosen in (5)} \\ \exists\_{ \genfrac{}{}{0}{} {x\_{0}=\max\left(x\_{g0},0\right)} {M=1+M\_g} }~\left|f(x)+g(x)\right|&\le& M\left|f(x)\right| ~~~x\>x\_0\text{ as } x\rightarrow \infty &&(11)&&\text{Simplifying (8,9,10)} \end{eqnarray} $$

Thus we can construct a valid $M$ and $x\_0$ given a valid $M\_g$, and $x\_{g0}$, which we know exist, because $g(x)\in \mathcal{O}\left(f(x)\right)$ is given.
> 4 votes

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


title: CoNP and NPhard intersection

text:
# Question
Title: CoNP and NPhard intersection
Can a problem be both *NP-Hard* and *CoNP*?

Can a problem be both *NP* and *CoNP-Hard*?

# Answer
> 5 votes
There is a problem which is both NP-hard and in coNP if and only if NP = coNP.

If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.

On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.

The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.

---
Tags: complexity-theory
---


# Question
Title: Regular Expression as basis for creating this grammar
I made a right-linear grammar from a regular expression:

The alphabet is:

$Σ = \\{a, b, c\\} $

Regular expression:

$r = cc^{\*}(ba)^{\*}bb$

My solution, it seems a little too short like I'm leaving something out. Maybe someone can see where I went wrong on the right-linearity:

$ S \to cA $

$ A \to b a A | B | cA $

$ B \to bb $

# Answer
> 3 votes
$A \rightarrow ba \mid A \mid B \mid cA$

under this $bababaccc$ is also legal

---

You could try something like this...

$S \rightarrow cS|cA$

$A \rightarrow baA|B$

$B \rightarrow bb$

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


title: Segmentation and paging

text:
# Question
Title: Segmentation and paging
I am given a system with a segmented paging architecture. Both physical and virtual address spaces contain $2^{16}$ bytes each. The virtual address space is divided in $8$ equal size segments. The page table consist of $2$ byte page table entries.

---

## Question 1:

What is the minimum page size in bytes so that page table for a segment requires at most 1 page to store it?

### My interpretation:

There are $2^{16}$ virtual addresses. These are evenly divided between $8$ segments so each segment is $\frac{2^{16}}{2^3}=2^{13}$ bytes.

Now each segments will be divided into pages. Each page will be $2^n$ bytes. So there are $2^{13-n}$ pages (and page table entries) per segment. A page table entry is $2$ bytes long and page size is $2^n$. So $2^{n+1}$.

$2^{13-n} = 2^{n+1}$ gives $n = 6$. But the answer should be $n = 7$.

I know I made a mistake in page table entry as I didn't get the page table entry concept properly. Is that a f (f+d = memory address)? I am not getting page table entry. Please explain to me this concept.

---

## Question 2:

Assume that page size is $512$ bytes. Each page table entry contains (besides other information) $1$ valid bit, $3$ bits for page protection and $1$ dirty bit. How many bits are available in a page table entry for storing the aging information for the page?

### My way of thinking about the answer here:

$16$ bits for physical memory. Page size is $512$ bytes means $9$ bits required. That's $16-9= 7$ bits for a frame.

Now I'm stuck.

# Answer
### Answer to question 1:

If $2^n$ is the size of the page then there are $2^{13-n}$ pages.

We know that each page table entry is 2 bytes.

So size of the page table will be $2\times 2^{13-n}$ bytes because $2^{13-n}$ is the number of pages and each page has an entry in the page table.

They have given that page table takes at most one page to store.

So, $2\times 2^{13-n}=2^n \Rightarrow n=7$.

---

### Answer to question 2:

Each page table entry is two bytes which is $16$ bits so the remaining bits other than the valid bits (protection bits and the dirty bit) are $16-5=11$ bits.

Page size is $512=2^9$ bytes.

Physical address space $2^{16}$ bytes.

Number of bits required to represent a page is $16-9=7$ bits.

So, the available bits to store the aging information is $11-7=4$ bits.
> 2 votes

---
Tags: operating-systems, memory-management, virtual-memory, paging
---


title: Reducing states of a GTG

text:
# Question
Title: Reducing states of a GTG
I used this generalized transition graph with 3 states and got an equivalent generalized transition graph with 2 states:

GTG:

Equivalent with 2 states:

I'm not sure about the regular expressions linking the nodes $q0$ and $q2$, if someone can clarify where I may have gone wrong here.

# Answer
Actually the regular expressions from $q\_0$ to $q\_2$ and from $q\_2$ to $q\_0$ seem to be correct, but the loops around $q\_0$ and $q\_2$ are more questionable. Although they will lead to a correct answer, they could be simpler and I am not sure you applied the algorithm correctly.

If you want to be sure of your answer, I would recommend to use linear equations. This is exactly the same method, but it might be safer. In your case, you have the system \begin{align} X\_0 &= (a+b)X\_0 + (aa + b)X\_1 + ab^\*X\_2 \\ X\_1 &= X\_0 + ba X\_1 + bX\_2 \\ X\_2 &= (bb + a) X\_0 + aX\_1 + 1 \end{align} where $1$ denotes the empty word. You want to eleminate $X\_1$. To do this, rewrite the second equation as $X\_1 = baX\_1 + (X\_0 + bX\_2)$ and apply the general result that if $1 \notin K$, the unique solution to the equation $X = KX + L$ is $K^\*L$. In your case, you get $X\_1 = (ba)^\*(X\_0 + bX\_2)$. You now copy-paste this value of $X\_1$ in the two other equations *(and I really did it this way!)* to get \begin{align} X\_0 &= (a+b)X\_0 + (aa + b)(ba)^\*(X\_0 + bX\_2) + ab^\*X\_2 \\ X\_2 &= (bb + a) X\_0 + a(ba)^\*(X\_0 + bX\_2) + 1 \end{align} which leads to \begin{align} X\_0 &= (a+b+ (aa + b)(ba)^\*)X\_0 + ((aa + b)(ba)^\*b + ab^\*)X\_2 \\ X\_2 &= (bb + a + a(ba)^\*)X\_0 + a(ba)^\*bX\_2 + 1 \end{align} You can now recover the regular expressions if you wish: $q\_0 \xrightarrow{a+b+ (aa + b)(ba)^\*} q\_0$, $q\_0 \xrightarrow{(aa + b)(ba)^\*b + ab^\*} q\_2$, $q\_2 \xrightarrow{bb + a + a(ba)^\*} q\_0$, and $q\_2 \xrightarrow{a(ba)^\*b} q\_2$.

**A further simplification**. You may observe that in your original automaton, you have $q\_0 \xrightarrow{a+b} q\_0$. This implies that for any word $u$, there is a path $q\_0 \xrightarrow{u} q\_0$. It means that the transition $q\_0 \xrightarrow{a+b+ (aa + b)(ba)^\*} q\_0$ in the second automaton is redundant and could have been replaced by $q\_0 \xrightarrow{a+b} q\_0$.
> 2 votes

---
Tags: formal-languages, graphs, automata, formal-grammars
---


title: Solving a recurrence

text:
# Question
Title: Solving a recurrence
Can anyone give me some hint on solving $T(n) = T(\frac{n}{2} + \sqrt{n}) + n$, with any method, master method, substitution.... I have came up with this : $T(n) = T(\frac{(\sqrt{n} + 1)^{2} - 1}{2}) + n$ and then substituting $n = 2^{m}$ but things gets really messy !

any idea?

# Answer
Here sufficient base cases are not provided. If the recurrence is rewritten as follows $T(n)=T( \lfloor n/2+\sqrt{n} \rfloor)+n$, then, from an initial value $n\>4$, in a finite number of steps, one reachs the value $n=4$. In these conditions, we can use the Akra-Bazzi theorem, cf.

https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi\_method

Here $g(x)=x,a\_1=1,b\_1=1/2,h(x)=\sqrt{x}+O(1)$. Thus $p=0$ and $T(x)=\Theta(x)$.

Remark: as Yuval wrote, we can also use a recurrence. For instance, we try to prove that $T(n)\leq cn$. The condition to show is $c(n/2+\sqrt{n})+n\leq cn$, that is $c\>2$ and $n\geq \dfrac{4c^2}{(c-2)^2}$. We choose $c\geq 20$ and the considered inequality is true for $n\geq 5$. We must begin the recurrence, that is $T(4)\leq 4c$. Finally $c=\sup \\{20,T(4)/4\\}$.
> 1 votes

# Answer
Assuming that the end goal is to get an asymptotic bound on the time or space complexity of the algorithm that this recurrence relation represents, then start with $n = 4k^2$ s.t. $k \> 1$ and notice the following:

$T(4k^2) = T(2k^2 + 2k) + 4k^2$

$T(2k^2 + 2k) = T( k^2 + k + \sqrt{ 2k(k + 1) } ) + 2k^2 + 2k$

$T(k^2 + k + \sqrt{ 2k(k + 1) }) = T(\ldots) + k^2 + k + \sqrt{ 2k(k + 1) }$

Substituting backward

$T(4k^2) = 7k^2 + 3k + \sqrt{ 2k^2 +2k } + T(\ldots)$

Substituting the original value of $n$

$T(n) = \frac{7}{4} n + \frac{3}{2} \sqrt{n} + \sqrt{\frac{1}{2}n + \sqrt{n}} + T(...) $

Each successive term is an order smaller than the one prior and as we look at the asymptotic behavior, those smaller terms will vanish and the linear term will dominate, thus $\mathcal{O}(n)$.
> 3 votes

# Answer
Hint: You can prove inductively that $T(n) \leq Cn$ for an appropriate $C$. On the other hand, clearly $T(n) \geq n$.
> 1 votes

# Answer
The function $T$ is not defined over $\mathbb{N}$ because if $n$ is an integer, then $n/2+\sqrt{n}$ is not in general. Perhaps a floor function is missing in the definition. Assume that $T$ is defined on $(0,+\infty)$. Let $t\>4$. Then the sequence $u\_0=t,u\_{k+1}=u\_k/2+\sqrt{u\_k}$ is decreasing and tends to $4$. Thus $T(t)\>4+4+\cdots$ and $T(t)=+\infty$.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Is there a graph product that is multiplicative in independence number?
I know that Stable set cannot be approximated to constant factor. I saw a simple proof using OR product sometime back. I am unable to recall it. If anyone here knows what I am talking about could help fill my memory, that will be helpful.

Is there a graph product $\cdot$ such that $\alpha(G\cdot G)=\alpha(G)^2$ for all graphs $G$ and $G\cdot G$ the product of $G$ with itself?

I only need an answer to inapproximability to constant factor and I believe there is a one step proof for this.

If we had such a product, then we have $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\alpha(G)^k$. If $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)$ can be approximated to constant factor $\sigma\>0$, then $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\sigma\hat\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\alpha(G)^k$ and since $0\<\sqrt\[k\]{\sigma}\<\sigma$, we can get an approximation of $\alpha(G)$ that is better than $\sigma$ by $\sqrt\[k\]{\sigma\hat\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)}=\alpha(G)$.

# Answer
Consider $G = K\_2$, for which $\alpha(G)=1$. The only product defined in terms of subgraphs of $K\_4$ and for which $\alpha(G \times G) = 1$, is the strong product (⊠). This doesn't quite work, since $\alpha(C\_5 ⊠ C\_5) = 5$, which is not a perfect square.

However, denoting the lexicographic product by $\circ$, there is an easy proof due to Geller and Stahl that $\alpha(G \circ H) = \alpha(G)\alpha(H)$.

So you want the lexicographic product.
> 5 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Running Floyd-Warshall algorithm on graph with negative cost cycle
I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, or 1. Suppose that G is strongly connected, with at least one u-v path for every pair u,v of vertices, and that G may have a negative-cost cycle. How large can the final entries A\[i,j,n\] be, in absolute value (n denotes number of vertices). Choose the smallest number that is guaranteed to be a valid upper bound? There is the following answers:

1. +∞
2. n^2
3. n - 1
4. 2^n

I have ruled out 3. (n-1) and 1. (+∞) since if a graph has a negative cost cycle, the absolute final value of a path including a negative cycle can be increased further than n-1. The answer also cannot be +∞ since the algorithm stops after a finite number of steps. But I am having trouble between answers 2. and 4. I am more inclined to 4. since I have run some test cases, and final values seemed to comply to an exponential growth. But I cannot find a proof for it.

# Answer
> 4 votes
I think the answer is 4, and here is why.

Assume the graph is fully connected with all edges having weight of -1.

Now let's consider the three loops of Floyd-Warshall algorithm:

```
for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:

```

Since -2 is "shorter" than -1, after we finish k = 1, the weight for i -\> k = 1 -\> j is -2 for most i and j (exceptions would be i = k and j = k).

After we finish k = 2, the weight for i -\> k = 2 -\> j is -4 for most i and j. This is because i -\> 1 -\> 2 -\> 1 -\> j is the shortest, giving us -4.

And so on and so on for the exponential growth.

Floyd-Warshall algorithm does not guarantee that we will find a simple shortest path, that is, a path containing only one instance of each vertex.

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


title: Is this $\beta$-reduction well defined?

text:
# Question
Title: Is this $\beta$-reduction well defined?
Would it be possible to apply $(\lambda x.\lambda y. x)$ to the argument $y$? It seems to me that this must not be possible as it would give a different answer if applied to a constant, call it $\alpha$ and $y$. Namely:

$(\lambda x.\lambda y. x) \alpha = \alpha$

but

$(\lambda x.\lambda y. x)y = \lambda y.y$

I am afraid that I might be making considerable mistakes but this is only the case because I have been studying $\lambda$-calculus for just one day.

Thank you very much in advance for your comments and suggestions.

# Answer
Beta-reduction is only allowed when the argument does not contain any free variable that is bound in the function. So before you can beta-reduce $(\lambda x. \lambda y.x) y$, you must rename the bound variable $y$ using alpha-conversion.

Formally speaking, beta-reduction and equivalence are defined not over lambda terms, but over lambda terms modulo alpha-conversion. So by performing alpha-conversion, you are not changing the term.

$$ (\lambda x. \lambda y.x) y =\_\alpha (\lambda x. \lambda z.x) y \to\_\beta \lambda z.y $$

An alternative approach is to treat terms syntactically, and allow the beta-reduction, but perform the alpha-conversion as part of the substitution. The two approaches can be shown formally to be equivalent (for almost all uses of the lambda calculus, this is an unimportant presentation detail).

$$ (\lambda x. \lambda y.x) y \to\_\beta (\lambda y.x)\[x\leftarrow y\] =\_\alpha (\lambda z.x)\[x\leftarrow y\] = (\lambda x.y) $$
> 2 votes

---
Tags: programming-languages, lambda-calculus, term-rewriting, variable-binding
---


# Question
Title: Finding Statistical Signifigance for a Classifier
I recently did work in the area of machine learning for one of my jobs and was able to build a classifier which evaluated to an F score of 85%. I also have access to correctly and incorrectly classified instances. My boss would like to make sure my classifier is good and and test it for statistical significance. I'm not quite sure what he means by this. I have taken a course in statistics quite some time ago where I did hypothesis testing and stuff with confidence intervals. Do you think that's what he means or does he want me to compare it with other algorithms? I don't want to say what kind of data set I am working with but it's comparable to something such as predicting spam or ham for email messages.

Any help or guidance on this question would be greatly appreciated. I am pretty new to the area of computer science research. But am I right in saying that statistics are used quite a lot to evaluate these types of things?

Thank you!

# Answer
> 2 votes
You can take a look at McNemar's Test or a Bayesian Testing. If you are comparing two or more classifiers, you can perform a to evaluate their performances.

Evaluating learning is actually a pretty wide research topic. A good book to refer to would be Japkowicz-Shah. This is a really nice book on evaluating classifiers and performances. To get some idea about the topic, take a look at this ICMLA talk.

If this is a one time thing, get done with McNemar or Bayesian test, however if you continue to work in the field, do see the book.

P.S. ask you boss if he means any real stat tests (like those mentioned above). Once I was working on a classifier, my professor asked me to evaluate its performance, after a long period of pain and agony of cluelessness, it turned out he just wanted me to test it on other 'toy problems'.

---
Tags: machine-learning, statistics, classification
---


# Question
Title: Deriving the exact number of execution times
So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions.

Here's a screen cap:

The answer is `n^2(n+1)/2`.

I would appreciate a very simple walk through and/or a pointer to some good material.

# Answer
> 2 votes
Hint: Summation. Also note you can optionally reorder the (non-dependent) loops.

Spoiler (mouse over):

> So what you normally do: the inside of a nested loop will run the $\text{number of loops of the outer loop} \times \text{the number of loops of the inner loop}$. It can also be done with repeated addition of the number of loops of the inner loop (after all multiplication can be done with repeated addition). In this case, one of the inner loops is *dependent* on the outer loop, so you can't just multiply them. You must add it more "manually". If you do this, you will see something like this: $ 1 + 2 + 3 ... n $, this can be done with summation, which in this case $\sum\_{i=1}^n i = \frac {n\cdot\left(n+1\right)} {2}$. And multiplying the additional $\\#n$-loop loop (you can reorder $k$-loop to the outside to make this simpler, after that you can calculate the two inner-loops, $i$ and $j$) , you get $n\cdot\frac {n\cdot\left(n+1\right)} {2} =\frac {n^2\cdot\left(n+1\right)}{2}$.
>
> ---
>
> So step by step:
> 1. First let's decide the two outer loops: the outer loop, $i$ will run $n$ times.
> 2. The $j$ loop will run $1...i$ each time. The first time it will run $1$ time, then $2$ times, then $3$ ... finally $n$ times, totaling $1 + 2 + 3 + ... + n$ times. That means the $j$ loop will run a total of $\frac{n\cdot\left(n+1\right)}{2}$ times, after calculating the summation (see linked wikipedia page on summation).
> 3. For each time the $j$ loop runs, the $k$ loop will run $n$ times, thus we simply multiply the summation result by $n$ for $\frac{n^2\cdot\left(n+1\right)}{2}$.

# Answer
> 2 votes
Work it out from the inside out.

Let $P'''(i, j, k) =$ `cout << i << j << k << endl` and $T'''(i,j,k)$ be the number of times `cout << …` is executed during the execution of $P'''(i,j,k)$ when `i`$=i$, `j`$=j$ and `k`$=k$. As it happens, $T'''(i,j,k)$ does not depend on the value of any of the variables: $T'''(i,j,k) = 1$.

Let $P''(i,j) =$ `for k = 1 to n` $P'''(i,j,\mathtt{k})$ and $T''(i,j)$ be the number of times `cout << …` is executed during the execution of $P''(i,j)$ when `i`$=i$ and `j`$=j$. The number of times the instruction is executed during the execution of the loop is the sum of the number of times it is executed during each iteration. $$ \begin{align} T''(i,j) &= \sum\_{k=1}^n T'''(i,j,k) = T'''(i,j,1) + T'''(i,j,2) + \ldots + T'''(i,j,n) \\ &= \sum\_{k=1}^n 1 = n \end{align} $$

Let $P'(i) =$ `for j = 1 to i` $P\_(i,\mathtt{j})$ and define $T'(i)$ like before. $$ \begin{align} T'(i) &= \sum\_{j=1}^i T''(i,j) = \sum\_{j=1}^i n = i \cdot n \end{align} $$

Let $P =$ `for i = 1 to n` $P'(\mathtt{i})$ and define $T$ like before. $T$ is the number you're looking for. $$ \begin{align} T &= \sum\_{i=1}^n T'(i) = \sum\_{i=1}^n (i \cdot n) = n \sum\_{i=1}^n i = n \cdot \frac{n (n+1)}{2} \end{align} $$

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


# Question
Title: Equivalence relation Mathematical base In Computer science
I have this equivalence relation problem:

Let $R$ and $S$ be two equivalence relations on the same set $A$. Define a new relation $U$ such that $U(x,y) \leftrightarrow \[R(x,y) \text{ or } S(x,y)\]$. Is $U$ necessarily an equivalence relation?

I said that is was an equivalence relation because $U$ is only true if $R$ or $S$ is true, and only depends on one. I do not know know exactly how to explain it, or prove this. Should I use proof by contradiction to prove this and make the negated statement $!U(x,y) \leftrightarrow {!\[R(x,y) \text{ or } S(x,y)\]}$ and from this we can see that $U$ is an equivalence relation because the negation is saying that $R(x,y)$ or $S(x,y)$ isn't an equivalence when it actually is?

I am kind of stuck so any help is appreciated.

# Answer
In order to *prove* that $U$ is an equivalence relation, you need to use the definition: prove that $U$ is reflexive, symmetric and transitive. If you try to do that but it doesn't work, you can try to *disprove* the claim that $U$ is always an equivalence relation by giving a counterexample: equivalence relations $R$ and $S$ such that the corresponding $U$ isn't an equivalence relation (that is, it either isn't reflexive, isn't symmetric or isn't transitive); you can use your failed proof attempts to guide you in the construction.
> 4 votes

---
Tags: relational-algebra
---


# Question
Title: Writing a program to find polynomial $f(x)$ from $f(1)$ and $f(f(1))$
Let $f(x)=a\_0+a\_1x+a\_2x^2+\dots+a\_nx^n$, where $a\_i\ge0$ and $a\_i$ is integer.

Given $f(1)=p$ and $f(f(1))=q$, we have to find $a\_0$, $a\_1$, $a\_2$, $a\_3$, $\dots$, $a\_n$, where such $f(x)$ exists. Or we have to confirm if such $f(x)$ exists or if the polynomial is ambiguous e.g. for $p=1$ and $q=2$, no such $f(x)$ exists but for $p=1$ and $q=1$, $f(x)=1$, $f(x)=x^2$ both can be solution.

I have to write a program to do that. What should be my procedure?

# Answer
The conditions $f(1) = p$ and $f(p) = q$ imply the following two equations: $$ \begin{align} &\sum\_{i=0}^n a\_i = p, \\ &\sum\_{i=0}^n a\_i p^i = q. \end{align} $$ When $p \< 0$ or $p$ is not an integer, there are no solutions. When $p = 0$, the first equation implies that the polynomial must be $0$ and so $q = 0$. When $p = 1$, the equations imply that $p = q$, and the first equation implies that the solutions are the polynomials $1,x,\ldots,x^n$. From now on, we assume that $p \geq 2$.

Intuitively, the polynomial minimizing $\sum\_i a\_i$ under the second constraint above is obtained by writing $q$ in base $p$ notation (first $n$ digits) and putting the rest as a coefficient of $a\_n$. Denote this solution by $b\_0,\ldots,b\_n$. If $\sum\_i b\_i \> p$ then there is no solution. If $\sum\_i b\_i = p$ then we have found the unique solution. From now on, suppose that $\sum\_i b\_i \< p$; this implies that the base $p$ expansion of $q$ has length at most $n+1$.

The given equations imply more constraints. First of all, $q \geq p$. Second, since $p \equiv 1 \pmod{p-1}$, we must have $q \equiv p \pmod{p-1}$. Starting with the polynomial $g(x) = \sum\_{i=0}^n b\_i x^i$, we can increase $g(1)$ by applying the update $(b'\_{i+1},b'\_i) \gets (b\_{i+1} - \alpha,b\_i + p\alpha)$ (when $b\_{i+1} \geq \alpha$); this increases $g(1)$ by $\alpha(p-1)$. We can apply these updates systematically, moving the mass all the way to the polynomial $q$. Since $\sum\_i b\_i \< p \leq q$ and $q \equiv p \pmod{p-1}$, somewhere along the way we will find a (unique) polynomial satisfying both requirements above.

How do we perform this process algorithmically? We go over the indices from $b\_n$ to $b\_1$ in order. At each point, we subtract from $b\_i$ the maximal amount $\alpha$ which keeps the invariant $g(1) \leq p$. After processing $b\_1$, we should reach the desired polynomial. (We are basically looking at the base $p-1$ expansion of $p - g(1)$.)
> 3 votes

# Answer
If $p=1$, then the constraints are $f(1)=1=q$ which is easily solved depending on the value of $q$. Let's now assume $p \ge 2$. Suppose that $f(x) = \sum\_k a\_k x^k$ is a solution. Then $q = a\_0 + a\_1 p + a\_2 p^2 + \ldots + a\_n p^n$ where $n$ is the degree of $f$ ($a\_n \ne 0$).

For any $k \le n$, $a\_k \le \dfrac{q}{p^k}$. This gives a bound on each coefficient.

Since $p \gt 1$, this inequation also gives a bound for the degree of $f$: $1 \le a\_n \le \dfrac{q}{p^n}$ so $n \le \dfrac{\log(q)}{\log(p)}$.

This shows that there is only a finite number of candidate polynomials. You can then enumerate all possible solutions. First compute the maximum degree $n$ of $f$. Then loop over the possible degrees ($n$ to $0$). For each degree value $m$, loop over the possible values of $a\_m$; for each value of $a\_m$, loop over the possible values of $a\_{m-1}$, and so on. Maintain the partial sums $S\_k = a\_m p^m + \ldots + a\_k p^k$ and $R\_k = a\_m + \ldots + a\_k$; if either of these sums exceeds $q$ or $p$ respectively, abort this branch of the tree. When you get to $k=0$, the constraints on $f$ are $S\_1 + a\_0 = q$ and $R\_1 + a\_0 = p$, so check whether $S\_1 - R\_1 = q - p$.

I have no idea whether this approach is practical — there may be a significantly faster algorithm exploiting divisibility more.
> 2 votes

# Answer
You need a polynomial such that $f(1) = p$ and $f(p) = q$. This can be done as long as $p \neq 1$, $p, q \> 0$ and $\frac {q-p} {p-1} \> 0$ (or $p = q = 1$). In all cases a polynomial $ax^n+b$ is enough. Here $p^{n+1} \> q$. Note that no $n$ is too large.
> 0 votes

---
Tags: mathematical-programming, polynomials
---


# Question
Title: Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most
There are $n$ elements in a hash table of size $m \geq 2n$ which uses open addressing to avoid collisions.

The hash function was chosen randomly among a set of uniform functions. A set $H$ of hash-functions $h:U\to\\{0,\dots,m-1\\}$ is called uniform, if for every tuple of different keys $x,y \in U$ the number of hash-functions $h \in H$ with $h(x) = h(y)$ is $\frac{|H|}{m}$ at most.

Show that the propability that for $i = 1, 2, \dots,n$ the $i$-th insert operation needs more than $k$ attempts, is $2^{-k}$ at most.

This is an assignment, which I got as homework. What I already worked out:

The propability $p\_1$ for a collision is 0 of course for an empty table.

The propability $p\_i$ for a collision after k attempts should be $\frac{i - 1}{2n}\cdot k$ assuming that the table is filled with $i-1$ elements to this point and the tables size is $2n$ as worst case.

So I have $$ p\_i= \frac{i-1}{2n} \cdot k \leq 2^{-k}, $$

but I don't know where to go from here.

The method of open hashing used here simply iterates over different hash-functions until a free place is found (for example $h(x) = (x \bmod j) \bmod n$ with increasing prime numbers for $j$.

# Answer
Hint: Show that at a given value of $i$, the probability of failure of the $l$th attempt is at most $i/m \leq 1/2$ (perhaps using a union bound), and the events are independent for different attempts.
> 1 votes

---
Tags: algorithm-analysis, data-structures, hash-tables
---


title: DFA memory bandwidth

text:
# Question
Title: DFA memory bandwidth
When we talk about DFA, we say that each new character from the input requires one memory access. What does that mean?

This is what I think about this. Please tell me is this right? For example, I have a transition table stored for a certain regular expression in memory (RAM). Now, for each input character the CPU will fetch the whole transition table to find out the next state. In this way, we have just one memory access?

# Answer
> 3 votes
This is not how memory access works. For each character read, you need (1) to read the character, (2) to access the transition table at the appropriate state and character. In your case it seems that we're not counting (1), and so (2) is the single memory access. The *speed* of this access depends on how big the transition table is. If it is small enough to fit in cache (which is usually the case), then after several transitions, the entire transition table would be in cache and so would be accessed quickly. If it is too big, you will have cache misses and everything would be slower. But in both cases only the particular cell is accessed! However, data is stored in caches in chunks knows as *cache lines*, which could explain your confusion (cache lines are not big enough to hold the entire transition table). Note also that there are several levels of cache.

---
Tags: automata, finite-automata, memory-access
---


# Question
Title: What is the asymptotic runtime of this nested loop?
I am trying to analyse the runtime of this algorithm:

```
for(i=1; i < n; i++){
   for(j=1; j <= i; j++){
         statement1;
   }
}

```

Expanding the above loop into.

* First :

```
for(j=1; j <= 1; j++){
   statement1;          //complexity O(1)
}

```
* Second:

```
for(j=1; j <=2 ; j++){
   statement1;          //complexity O(2)
}

```

...

* n-th:

```
for(j=1; j <= n; j++){
   statement1;          //complexity O(n)
}

```

So the runtime of the loop should be

$\qquad \displaystyle O(1) + \dots + O(n) = O\Bigl(\frac{n(n+1)}{2}\Bigr) = O(n^2)$.

Can I reason like this, or what is the proper way to analyse nested `for`-loops?

# Answer
> 11 votes
The result is correct, but your reasoning is not. You can't mix big-oh with ellipses. It happens to work here because of extra conditions that happen to be true but that you haven't checked.

## Why summing big-ohs just doesn't work

Fundamentally, you are abusing notation. For example, it doesn't make much sense to write $O(1)$, $O(2)$, $O(3)$, etc. as if they were different things — after all, they all mean “bounded function”.

The definition of big-oh depends on some values that differ from one $O(…)$ to the next. When you write $O(1) + \ldots + O(n)$, the constants could be different in each term of the sum, and if they are, you can't say anything about the sum. $f(n) = O(g(n))$ means that there exists some threshold $N$ and some factor $C$ such that if $n \ge N$ then $f(n) \le C g(n)$. When you have a variable number of big-ohs like $O(f\_1) + \ldots + O(f\_n)$, each term of the sum has its own threshold and factor. Your reasoning assumes that the threshold and factor are the same, and it's true that in this example you can pick them to be the same, but it isn't true in general.

The first hurdle is what $O(1) + \ldots + O(n)$ actually means. This is a sum whose general term is $O(k)$: $O(1) + \ldots + O(n) = \sum\_{k=1}^n O(k)$. The general term of the sum could depend on both $k$ (the index into the sum) and $n$ (the number of terms)! Big-oh is defined in terms of a variable, it describes what happens when that variable approaches infinity. If you consider the general term as a function of $k$, then $O(k)$ means that there exists some threshold $K\_n$ and some factor $D\_n$ such that if $k \ge K\_n$ then $f\_k(n) \le D\_n k$. If you consider the general term as a function of $n$, then $O(k)$ means that the function is bounded for any given $k$, i.e. that there exists a bound $B$ such that $\forall n, f\_k(n) \le B\_k$.

To illustrate how the sum can get big under the first interpretation, consider the function $$ f'\_k(n) = 2^n k $$ For any given $n$, $f'\_k(n) \le D\_n k$ where $D\_n = 2^n$ so $f'\_k(n) = O(k)$ as a function of $k$. Yet the sum is $$ \sum\_{k=1}^n f'\_k(n) = f'\_1(n) + \ldots + f'\_n(n) = 2^n \cdot 1 + 2^n \cdot 2 \ldots + 2^n \cdot n = 2^n \cdot (1 + 2 + \ldots + n) = 2^n \frac{n(n+1)}{2}$$ which is not $O(n^2).

To illustrate how the sum can get big under the second interpretation, consider the function $$ f''\_k(n) = k^2 $$ The general term $f''\_k(n)$ is constant with respect to $n$, so it is $O(k)$ as $n$ goes to infinity (since $k$ is fixed, this is the same as writing $O(1)$). Yet the sum is $$ \sum\_{k=1}^n f''\_k(n) = f''\_1(n) + \ldots + f''\_n(n) = 1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6} $$ which is not $O(n^2)$.

## What actually works

Here, you have a special case which does make sense. It's not any sum of big-ohs — it's the same function every time: $$ f(1) + f(2) + \ldots + f(n) = \sum\_{k=1}^n f(k) $$ where $f(k) = O(k)$. Now we have a function of a single variable, which makes the analysis simpler. By the definition of big-oh, there is a threshold $N$ and a factor $C$ such that for all $k \ge N$, $f(k) \le C k$. Therefore, if $n \ge N$, then $$ \sum\_{k=1}^n f(k) = \sum\_{k=1}^{N-1} f(k) + \sum\_{k=N}^n f(k) \le \sum\_{k=1}^{N-1} f(k) + \sum\_{k=N}^n C k \le \sum\_{k=1}^{N-1} f(k) + C \frac{n(n+1) - N(N-1)}{2} $$ This last term is of the form $C n^2 + B n + A$, so it is $O(n^2)$ and thus $\sum\_{k=1}^n f(k) = O(n^2)$.

If $f$ is monotonically increasing (which is often but not always the case for complexity bounds), then there is an easier way to prove this: $$ \sum\_{k=1}^n f(k) \le \sum\_{k=1}^n f(n) = n f(n) $$ and since $f(n) = O(n)$, the sum is $O(n \cdot n) = O(n^2)$.

Note that we are taking the sum of the values of a function which is $O(n)$. This is crucially different from summing functions, each of which is $O(n)$.

## Application to a loop

Consider a loop

```
for i = 1 to n do
    /*do something*/

```

If the running time of `/*do something*/` does not depend on $n$, then we are in the case that works. For example, take your nested loop:

```
for i = 1 to n do
    for j = 1 to i do
        statement

```

Assuming that `statement` runs in constant time, the run time of the inner loop is $j$ which is $O(j)$. The run time of the outer loop is thus $O(n^2)$. Of course, you don't need to remark that $j = O(j)$ to see this — you could directly remark that $j \le n$ and therefore `statement` is executed at most $n$ times per run of the inner loop and thus at most $n^2$ times per run of the outer loop.

The general way to analyze the complexity of loops is by summing the complexity of the iterations. You cannot sum big-ohs, you need to write an actual mathematical expression. If the final desired result is a big-oh approximation, then you don't need to write an exact computation: it is enough to find an **upper bound for each term** and then calculate an **upper bound for the sum** of the upper bounds.

# Answer
> 10 votes
We have lots of questions about the time complexity of sums, and the answer is the same every time:

**Loops translate to sums.**¹

Every other shortcut *will* get you into trouble.

In your case, you seem to have identified `statement1` as (dominant) operation you want to count. So your nested loop

```
for ( i=1; i<n; i++ ) {
  for ( j=1; j<=i; j++ ) {
    statement1;
  }
}

```

translates quite literally to

$\qquad\displaystyle T(n) = \sum\_{i=1}^{n-1} \sum\_{j=1}^i c\_1 = \sum\_{i=1}^{n-1} i \cdot c\_1 = c\_1 \cdot \frac{(n-1)n}{2} \in \Theta(n^2)$.

Note the difference between $O$ and $\Theta$ and that you ignore the cost of maintaining the loop, i.e. initialising `i` resp. `j`, checking the condition and incrementing. Therefore, $T$ is not the *real* runtime function.

As an exercise, add the missing costs to above sum and evaluate it; does the result change? Why (not)?

---

1. Disclaimer: Some algorithms don't lend themselves well to this translation, e.g. Dijkstra or even breadth-first-search. In these cases, other approaches work better.

# Answer
> 3 votes
You are thinking to much.. use a simpler model. Also as @A.Schulz pointed out, your calculations are correct in way, but there's some abuse of notation.

> for(i=1;i \< n;i++) {
>
> . . . for(j=1;j\<=i;j++){
>
> . . . . . . statement1; } }

the first line (outer loop with $i$) takes $\theta(n)$ time, the second line (inner loop with $j$ ) also takes at-most $O(n)$ time.

So, the worst you could do is $\boxed{O(n^2) \text{ time}}$.

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


title: result after applying on delete cascade

text:
# Question
Title: result after applying on delete cascade
In this table B is foreign key referring to the primary key A with on delete cascade option.What will be the result after deleting (4,3) and how A:1 4 2 9 3 5 B:3 3 4 2 9 4

# Answer
> 0 votes
The result will be an empty table.

The steps are :

1. delete (4,3)
2. delete rows with B = 4 --\> (2,4), (5,4)
3. delete rows with B = 2, B = 5 --\> (9,2)
4. delete rows with B = 9 --\> (3,9)
5. delete rows with B = 3 --\> (1,3)

---
Tags: databases
---


# Question
Title: Derive a Context Free Grammar from a language
I am having challenges (in two phases) with creating a CFG.

1. Derive the CFG for the following language
2. Show parse trees for the strings *cacab* and *aacabbb* obtained from the grammar designed above.

I am getting a bit mixed up by the exercise especially because my CFG appears not to produce a parse tree.

Here is the language:

$$ L = \\{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \\} $$

So far my grammar looks as follows:

$$ \begin{align} S &\to Ab \mid Bb \mid Cb \mid b \\ A &\to aA \mid \epsilon \\ B &\to caB \mid \epsilon \\ C &\to bC \mid \epsilon \\ \end{align} $$

# Answer
You're on the right track: $A$ recognizes $a^\*$ (i.e. $\\{a^n \mid n \ge 0\\}$), $B$ recognizes $(ca)^\*$ and $C$ recognizes $b^\*$.

You need to assemble them correctly. $Ab | Bb | Cb | b$ recognizes words that are made of something recognized by $A$ followed by $b$, or of something recognized by $B$ followed by $b$, etc. A word in $L$ consists of a part that's recognized by $A$ followed by a part that's recognized by $B$, etc. So the pieces need to be concatenated together: $S\_1 \to ABCb$.

$S\_1$ recognizes $\\{a^n (ca)^m b^{p+1} \mid m,n,p \ge 0\\}$. This is too much: $L$ consists only of the words for which $n = p$ in this decomposition. Instead of defining $A$ and $C$ separately, you need to relate them. Whenever you put an $a$ on the left of the $B$ part, put a $b$ on the right. $$ \begin{align} S\_2 &\to B \\ S\_2 &\to a S\_2 b \\ \end{align} $$ This constraints the number of $a$'s on the left to be equal to the number of $b$'s on the right. The words in $L$ actually have one more $b$ on the right. One way to add that $b$ is to append it at the end: $$ S \to S\_2 b $$ Another approach is to tack on the $b$ to the end of the $B$ part. $S$ and $S'$ recognize the same language, with slightly different parse trees. $$ \begin{align} S' &\to B b \\ S' &\to a S' b \\ \end{align} $$

To construct the parse trees, work out where each rule is applied to recognize the sample words.
> 1 votes

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


title: Strassen's Algorithm proof

text:
# Question
Title: Strassen's Algorithm proof
I have been reading about the Strassen Algorithm for matrix multiplication.

As mentioned in Introduction to Algorithms by Cormen , the algorithm is not intuitive. However I am curious to know if there exists any rigorous mathematical proof of the algorithm and what actually went into the design of the algorithm.

I tried searching on Google and stackoverflow, but all links are only on comparing Strassen's approach to standard matrix multiplication approach or they elaborate on the procedure presented by the algorithm.

Note: The same question has been asked on https://stackoverflow.com/questions/19229454/strassens-algorithm-proof , but without any definite answers

# Answer
The main idea of the algorithm is to find a way to multiply two $n\times n$ matrices with less than $n^3$ "essential" multiplications (multiplications of two elements of the matrices). This forms part of a larger theory, algebraic complexity theory. Here are a few highlights:

1. Every algorithm for multiplying two matrices can be formulated (at a small loss) as a *bilinear algorithm*: you form some linear combinations $\alpha\_1,\ldots,\alpha\_k$ of entries of the first matrix, some linear combinations $\beta\_1,\ldots,\beta\_k$ of entries of the second matrix, compute $\gamma\_i = \alpha\_i \beta\_i$, and then every entry of the product matrix is a linear combination of the $\gamma\_i$.
2. This can be formulated as computing the *tensor rank* of the matrix multiplication tensor $\langle n,n,n \rangle = \sum\_{i=1}^n\sum\_{j=1}^n\sum\_{k=1}^n x\_{ij} y\_{jk} z\_{ik}$. The tensor rank is similar to the more familiar matrix rank, and corresponds to the number of "essential" multiplications ($k$ in the preceding example).
3. Any non-trivial bound on $\langle n,n,n \rangle$ for *any* $n$ translates to a non-trivial matrix multiplication algorithm for *all* $n$, via the same recursive approach as Strassen's algorithm (this approach is also known as *tensorization*). There are several extensions, culminating in Schönhage's *asymptotic sum inequality*.
4. The asymptotic sum inequality can handle identities involving disjoint sums of matrix tensors (in plain English, ways of multiplying several matrices at once using fewer "essential" multiplications than the trivial algorithm uses), and can even handle "approximate" identities (*border rank*). Strassen came up with another method (the *laser method*) that can handle non-disjoint sums, and this led to the Coppersmith-Winograd algorithm and its descendants, which is where things stand today.
> 6 votes

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


# Question
Title: How to reduce the number of crossing edges in a diagram?
I am working on a diagram editor. Diagrams display 2D shapes (*nodes*) connected with connectors (*edges*).

I'd like to add an operation that, given a selection of nodes, *"disentangles"* them: it repositions them to minimize the number of crossing edges, if possible (and it's OK if the edges will have to be drawn with bend points).

So I want a graph algorithm that, given a (*topological*) graph embedding and a subset of its nodes, modifies the embedding (its *topology*) on only those nodes so as to minimize the number of crossing edges.

From reading about apex graphs and browsing Cabello and Mohar (2013), I suppose this problem is NP-hard. So I'll be happy with a parametrized algorithm (e.g. on the number of crossing edges) that has a known, polynomial, time complexity for any given parameter value. This seems feasible, but I don't find it easy to come up with such an algorithm on my own.

Questions:

* Where do I look for such an algorithm?
* Does it exist?
* In existing software?
* Is there any significant practical experience with such an operation? (What looks good in theory may not be so good in practice, or vice versa.)

*(I am not sure where best to ask this question: here, on StackOverflow, or MathOverflow?)*

# Answer
Computing the absolute minimal crossing number is, as you observed, $\text{NP-hard}$. The process of drawing the graphs should be at least as hard as that.

The problem posed in the question is actually harder and more involved than the above. You are considering graph nodes of a certain size and shape while also bounding the size (area) of the result. In addition, a not yet determined notion of aesthetics is desired. Obviously we want a heuristic for this, which does not use the absolute minimum in the general case. The number of nodes encountered in such an application are likely not huge in the average case. Drawing the minimal edge crossing version of the graph may be feasible for small sizes.

**Resources:**
You may be interested in the following resources, particularly with the first:

There are plenty of other resources, too. These should help you get started.

**Additional Thoughts & Observations:**

Here is an idea to get around the issues concerning the shape and size of nodes. Given the graph (infinitely small nodes), expand each node while "pushing" or bending edges out of the way (ex. using splines while enforcing a limit on proximity). You need to do this with other edges and nodes that get in the way of it, which can start a chain reaction. Look into how an equilibriums can be efficiently computed (ex. molecular structures). If you cant get the shape of a node to the desired size, then scale the whole diagram.

A user might enjoy the results of a randomized algorithm. They could use your feature multiple times until they got something they liked. Avoid redundant computation in this case (no need to compute a crossing number again).
> 11 votes

---
Tags: algorithms, graphs, crossing-number
---


title: Counting in Automata theory

text:
# Question
Title: Counting in Automata theory
Is it possible to count in Automata theory?

I am begginer in Automata theory and I am trying to do some examples.

Currently I am working on a program that will recognise equal numbers of 0 and 1, but they are orderd in such manner that they are together, example: $$ 000111\rightarrow true \quad 0001111\rightarrow false \quad 00011 \rightarrow false \quad 010101\rightarrow false \quad $$ I am trying to figure out is there any possibility to count in Automation theory. If not can you please advise me how it would be possible to solve this assingment, because the only way for me is counting.

Thanks.

# Answer
> 5 votes
Well, it depends of the kind of automata you are using. Roughly speaking, finite automata can only count modulo $d$ for some fixed $d$: for instance, you can test whether a word contains an odd number of $0$ or whether its length is a multiple of $5$. For your problem, finite automata will not suffice and you need a more powerful model of automata, for instance a pushdown automaton.

---
Tags: automata
---


title: Maximizing length of subsequence

text:
# Question
Title: Maximizing length of subsequence
Given a sequence $(a)$ of lenght $n$, such $a\_1 = a\_n = 1$ and $a\_i \in \left \\{ -1, 1 \right\\}$.

We want to find a subsequence $(b) \subset (a)$ which statisfies the following conditions:

* The length of $(b)$, (let's call it $k$) is the largest possible
* $b\_k = b\_1 = 1$
* Each prefix sum $b\_1$, $b\_1+b\_2$, $b\_1+b\_2 + b\_3,\ \ldots\ , b\_1 + b\_2 + \ldots + b\_k$ is $\geq 0$.
* Each suffix sum $b\_k$, $b\_{k} + b\_{k-1}, b\_{k} + b\_{k-1} + b\_{k-2}, \ \ldots\ , b\_k + b\_{k-1} + \ldots + b\_1$ is $\geq 0$.
* Sum of $(b)$ is the biggest possible.

Is it possible to construct linear algorithm to solve it?

# Answer
> 2 votes
Yes.

Let $c\_0 = 0$ and $c\_i = \sum\_{j=1}^i a\_i$, (which can be done in linear time). Now the problem becomes -- find $0\le i \< k\le n$ such that for all $i\le j\<k$ we have $c\_i\le c\_j \le c\_k$ that maximizes $k-i$. This can be found in a single sweep. (I'll let you work out the details.)

For the problem actually asked: We want the longest subsequence that begins and ends with 1 and each of the prefix and suffix sums is nonnegative. First note that all $a\_i=1$ are included as including it will only increase the prefix and suffix sums. In particular $b\_1=a\_1$ and $b\_k=a\_n$. We can construct $(b)$ in two passes. First pass from $i=1$ to $n$ selecting every $a\_i$ such that either $a\_i = 1$ or $a\_i=-1$ and the prefix condition is not violated in our subsequence (we are greedily selecting everything subject to the prefix condition). Now pass backwards through the subsequence discarding elements that violate the suffix condition.

Note that since all of the $a\_i=1$ are in $(b)$ the sum of $(b)$ is just the count of $a\_i=b\_j=1$ minus the count of the $b\_j=-1$ and so is twice the count of $a\_i=1$ minus the length of $(b)$, a function of the length. So any other subsequence satisfying the conditions having the same length will have the same sum.

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