# Question
Title: How can we minimize the total distance of cross pairs in an array
Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized.

The first thought would be to choose pairs with the minimum difference and so on. But it turns out the correct algorithm is to sort them and them pair accordingly.

Any ideas on how to prove that the latter algorithm correctly minimizes the sum of differences?

# Answer
> 2 votes
Let's follow Karolis's suggestion. Consider any solution with pairs $(a,b)$ and $(A,B)$ with $a \leq A$ and $B \leq b$, and write $A = a + \delta$, $B = b - \epsilon$. If we instead pair them $(a,B),(A,b)$, then instead of $|a-b|+|A-B|$ we get $|a-B|+|A-b|$. So we want to show $$ |a-b|+|A-B| \geq |a-B|+|A-b|. $$ Substitute the expressions for $A,B$: $$ |a-b| + |a-b+\delta+\epsilon| \geq |a-b+\epsilon| + |a-b+\delta|. $$ In terms of $C = a-b$, this is $$ |C| + |C+\delta+\epsilon| \geq |C+\epsilon| + |C+\delta|. $$ Rearranging, this is the same as $$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$ So we need to look at the function $D \mapsto |D+\epsilon| - |D|$, whose values are $$ |D+\epsilon| - |D| = \begin{cases} \epsilon & D \geq 0, \\ 2D+\epsilon & -\epsilon \leq D \leq 0, \\ -\epsilon & D \leq -\epsilon \end{cases} $$ We see that this is an increasing function of $D$, and so $C+\delta \geq C$ implies the inequality we want, $$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$

---
Tags: algorithms, algorithm-analysis, optimization, correctness-proof, permutations
---


title: Recurrence relation in 2 variables

text:
# Question
Title: Recurrence relation in 2 variables
When analyzing an algorithm, the following recurrence relation popped up:

$T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$

where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$.

By applying the Master Theorem inductively, for any particular $d$, it holds that $T(n,d)=O(n (\log{n})^d)$. However, it does not necessarily hold that $T(n,d)=O(n (\log{n})^d)$ because the constant hidden by the $O$-notation depends on the value of $d$.

I was hoping that the technically incorrect bound given by repeated application of the master theorem would be good enough. It turns out that this is actually a terrible, terrible bound. The actual values of $T(n,d)$ are orders of magnitude lower from what the asymptotic bound would predict. Does anyone know how to get a better bound?

# Answer
Suppose $T(n,d) = 2T(n/2,d) + T(n,d-1) + dn$, that $T(1,d) = d$, that $T(n,1) = n\log n$, and that $n$ is a power of $2$. Then $$ T(n,d) = dn\log n + T(n,d-1) + 2T(n/2,d-1) + \dots + nT(1,d-1). $$ In particular, $$ \begin{align\*} T(n,2) &= 2n\log n + n\sum\_{i=0}^{\log n} i \\ &\approx 2n\log n + \tfrac{1}{2}n\log^2n, \\ T(n,3) &\approx 3n\log n + 2n\sum\_{i=0}^{\log n} i + \tfrac{1}{2}n \sum\_{i=0}^{\log n} i^2 \\ &\approx 3 n\log n + n\log^2 n + \tfrac{1}{6} \log^3 n, \end{align\*} $$ and so on. More generally, we can think of $T(n,d)$ as a degree $d$ polynomial of the form $n\sum\_{i=1}^d c\_{d,i} \log^d n$. The coefficients are given by $c\_{d,1} = d$ and $c\_{d,i+1} = c\_{d,i}/(i+1)$. Unrolling the recurrence, we obtain $$ T(n,d) \approx n \sum\_{i=1}^d \frac{d+1-i}{i!} \log^d n. $$ In particular, $$ T(n,d) = \frac{1}{d!} n\log^d n + O(n\log^{d-1} n). $$
> 4 votes

---
Tags: time-complexity, asymptotics, recurrence-relation
---


# Question
Title: CFL not closed under intersection while Turing Decidable are
It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not.

Does not Turing Decidable engulf all CFLs?

# Answer
Yes, all CFLs are Turing-decidable but a subset of an intersection-closed class of languages is not necessarily intersection-closed. CFLs and Turing-decidable languages are just one example of this. In fact, this is not an unusual situation:

**Theorem.** Let $\mathcal{L}$ be an intersection-closed class of languages containing languages $L\_1$ and $L\_2$ such that $L\_1\cap L\_2\neq L\_1$ and $L\_1\cap L\_2\neq L\_2$. There is a class $\mathcal{L}'\subset\mathcal{L}$ that is not intersection-closed.

*Proof*. Just take $\mathcal{L}' = \mathcal{L}\setminus \\{L\_1\cap L\_2\\}$. $\mathcal{L}'$ contains $L\_1$ and $L\_2$ but does not contain their intersection, by construction. $\quad\Box$

The simplest possible example is the class of languages $C = \big\\{\emptyset, \\{a\\}, \\{b\\}\big\\}$. This is closed under intersection but the subclass $C' = \big\\{\\{a\\}, \\{b\\}\big\\}$ is not, since $\\{a\\}\cap\\{b\\}=\emptyset\notin C'$.

Conversely, a superset of an intersection-closed class of languages is not necessarily intersection-closed. Here's an example. Let $\mathcal{R}$ be the class of all Turing-decidable languages. Fix some coding of Turing machines and let $H$ be the language of codings of all Turing machines that halt when given empty input. It is well known that $H$ is undecidable, so $H\notin\mathcal{R}$. I claim that $\mathcal{R}' = \mathcal{R}\cup\\{H\\}$ is not closed under intersections. To see this, let $h$ be any string in $H$ (for example, $h$ could be the coding of some program that just loops for all input). The language $L = \\{w\mid w\neq h\\}$ is clearly in $\mathcal{R}$. $L\cap H\neq H$, since $h\in H$ but $h\notin L\cap H$. And $L\cap H\notin\mathcal{R}$ since the language of all Turing machines except for $h$ that halt when given empty input is also undecidable. Therefore, $\mathcal{R}'$ is not closed under intersections, since $L\in\mathcal{R}'$, $H\in\mathcal{R}'$ but $L\cap H\notin\mathcal{R}'$.
> 4 votes

---
Tags: formal-languages, context-free, turing-machines, closure-properties, decision-problem
---


# Question
Title: Proving the correctness of an algorithm, which computes the connectivity of a directed graph
Let $G=(V,E)$ be a directed graph. The **connectivity** of a graph is the defined as the cardinality of a smallest separator of $G$. A **separator** of $G$ is a subset $U$ of $V$, such that $G-U$ is not strongly connected.

Why does the following algorithm compute the connectivity of a graph correctly?

\begin{equation} \begin{split} &\text{Connectivity}(\text{graph }G=(V,E)) \\ &\\;\\;\\;\\;01\text{:}\\;\\;k=\infty \\ &\\;\\;\\;\\;02\text{:}\\;\\;\text{for }i=1,\ldots,|V| \\ &\\;\\;\\;\\;03\text{:}\\;\\;\\{\\ &\\;\\;\\;\\;04\text{:}\\;\\;\\;\\;\\;\\;\text{for each }v\in V\\ &\\;\\;\\;\\;05\text{:}\\;\\;\\;\\;\\;\\;\\{\\ &\\;\\;\\;\\;06\text{:}\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\text{compute a minimum }v\_i,v\text{-seperator }U\_{v\_i,v}\\ &\\;\\;\\;\\;07\text{:}\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;k=\min\left\\{k,\left|U\_{v\_i,v}\right|\right\\}\\ &\\;\\;\\;\\;08\text{:}\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\text{if }(i\>k+1) \text{ return }k\\ &\\;\\;\\;\\;09\text{:}\\;\\;\\ &\\;\\;\\;\\;10\text{:}\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\text{compute a minimum }v,v\_i\text{-seperator }U\_{v,v\_i}\\ &\\;\\;\\;\\;11\text{:}\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;k=\min\left\\{k,\left|U\_{v,v\_i}\right|\right\\}\\ &\\;\\;\\;\\;12\text{:}\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\text{if }(i\>k+1) \text{ return }k\\ &\\;\\;\\;\\;13\text{:}\\;\\;\\;\\;\\;\\;\\}\\ &\\;\\;\\;\\;14\text{:}\\;\\;\\} \end{split} \end{equation}

More precisely, why can we return $k$ in line 08 (resp. 12) without concerning the other $u,v$-seperators?

# Answer
Suppose that the algorithm is incorrect. We can slightly modify the algorithm by moving lines 8,12 just after the inner loop. If the algorithm returns $k$ incorrectly at the end of step $i$, then there must exist vertices $v\_s,v\_t$, for $s,t\>i$, and a set $S$ of size $k-1$ not containing $v\_s,v\_t$, such that after removing $S$ there is no path from $v\_s$ to $v\_t$. I claim that $v\_1,\ldots,v\_i \in S$: if $v\_j \notin S$ for some $j \leq i$, then since $S$ does not disconnect $v\_j$ from any other vertex, we would have a path $v\_s \to v\_j \to v\_t$. Since $v\_1,\ldots,v\_i \in S$, in particular $|S| \geq i$. Stated differently, $k-1 \geq i$. So if $i \> k-1$, this is impossible.

My proof, if correct, shows that you can actually use the weaker condition $i \> k-1$ in lines 8,12.
> 1 votes

---
Tags: algorithms, graphs, correctness-proof
---


# Question
Title: How to find the cost of pseudocode with a nested loop and a nested if statement?
How can I find the cost of pseudocode with a nested loop and a nested if statement?

On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I found. I took a guess, but I don't know what the time would be for the inner code fragments.

I am especially unsure what the code segments inside the if statement would be because the if statement doesn't always occur.

# Answer
> 2 votes
## Big O analysis

The answer is O(n^2).

Good strategy for working this out is eliminate all constant time operations (unless it is a return / break that will change the loop), as everything will always be at least O(1).

This means you can eliminate everything inside the if, as well as the if. So you are left with a simple nested loop running over n

Hence O(n^2)

## Cost analysis

You always assume worst case (unless explicitly told otherwise). Therefore assume if statement will be true and statements will run every loop (as there can exist a sorting order where this is true), so your statements will have the same cost as your loop

# Answer
> 2 votes
For this particular snippet of code, the answer is that *it doesn't matter* that the if statement is only entered "sometimes". If the if statement is entered, then you only do a constant amount of additional work. This is asymptotically equivalent to even evaluating if the if statement should be entered or not. Whether you enter or not is immaterial.

If the code inside were more complex, then you could naively construct an upper bound by assuming it *always* enters the block. It may be the case that this actually produces an "incorrect" (too loose) bound, but for sufficiently complex code one may require an entire paper to prove that a block is only entered a small number of times. Or, worst of all, it may in fact be impossible to prove when it is entered. Therefore as a first pass, it would be good enough to assume it's always entered. In practice, the result you get is often tight, or "tight enough". Otherwise, you better start busting out some serious proofs.

Anyway, for this particular snippet, the runtime of the code becomes the result of the sum you've expressed. Thankfully, this is is an exceedingly common sum which we all take the result of for granted. Here it is plugged into wolfram. The answer is something vaguely complex that there are various proofs of, but the key point is that its dominant factor is $n^2$, which is all we ever care about in asymptotics. Therefore this code runs in $O(n^2)$.

You could have also achieved this bound using similar reasoning I applied to the if statement: be lazy, and assume the worst. In this case, the inner loop does the most iterations when $i=1$. So let's just assume that it's always the case. Then that loop always goes from $1$ to $n$, and the two loops combined do $n\*n = O(n^2)$ work. Hey look, that's the same bound. Awesome.

It's easy to get bogged down in minor details with asymptotics, but you should generally try to be as "lazy" as possible to keep your analysis sane. Often (especially as you work with more examples), you will have an intuition for what the answer will be, or at least a target for how good it *needs* to be. Always start with the naivest, laziest upper bound you can think of (as long as it is indeed "upper"), and if it's "good enough", just stop there.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Applications of Depth-First Spanning Tree
I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that make use of the depth-first spanning tree?

# Answer
You can find bridges, i.e. edges whose removal causes the graph to separate into disconnected components.

Assuming connected, undirected graphs, the key insight is that a tree edge $e = (v,w)$ ($v$ being the father of $w$ in the tree) is a bridge if and only if there is no backwards edge¹ connecting $w$ or a successor of $w$ with an ancestor of $w$ (in the search tree). If there *were* such an edge, $e$ could not be a bridge as it's part of a cycle.

By augmenting the depth-first search algorithm in a suitable way, we can do these checks along the road and thus get an $O(n + m)$ algorithm.

---

1. There can be no forward and cross edges!
> 2 votes

# Answer
Tarjan linear time algorithm for articulation vertex (cut vertex). See http://en.wikipedia.org/wiki/Biconnected\_component
> 2 votes

---
Tags: algorithms, graphs, graph-traversal, spanning-trees
---


# Question
Title: How many times an empty 4-cycle can be counted in an undirected graph?
I have an undirected graph where each node is labelled with an integer key and I'm asked to detect every *simple* 4-cycle, which can be seen as an empty square (i.e. the two opposite nodes of the cycle have not to be connected).

I know the labels of a generic square in the graph can be permuted in $4! = 24$ ways, but on his paper (pages 33-36) Cohen states that the symmetric group $S\_4$ has $S\_4 = 8$ elements, and this should allow me to focus only on $24/8 = 3$ distinct cases.

I don't understand this last point. Well, I know he probably means that the suqare has $8$ isometries (four reflections and four rotations), but I don't understand why this leads to the three cases in Figure 7 of the paper.

Thank you.

# Answer
For each set $\\{a,b,c,d\\}$ of four vertices, there are three possible squares: $a-b-c-d$, $a-b-d-c$ and $a-c-b-d$. This is $|S\_4|/|D\_4|$, where $S\_4$ is the symmetric group on four points, and $D\_4$ is the *dihedral* group, the group of symmetries of a square.

Hear a *square* is a set of edges forming a square. So the squares are really $\\{\\{a,b\\},\\{b,c\\},\\{c,d\\},\\{a,d\\}\\}$, $\\{\\{a,b\\},\\{b,d\\},\\{c,d\\},\\{a,c\\}\\}$ and $\\{\\{a,c\\},\\{b,c\\},\\{b,d\\},\\{a,d\\}\\}$. You can check that all are distinct. *Every* square on $a,b,c,d$ is one of these — try finding any other one. We know that this list is exhaustive because of the computation $|S\_4|/|D\_4| = 3$.
> 2 votes

---
Tags: graphs
---


title: Palindromes and linear grammars

text:
# Question
Title: Palindromes and linear grammars
Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?

# Answer
Consider Post correspondence problem (PCP). If $\alpha\_1 \dots \alpha\_n$ and $\beta\_1 \dots \beta\_n$ are the words of PCP, then $S \to \alpha\_iS\beta\_i^r$ and $S \to \\#$ where $\\#$ is a symbol not in any of $\alpha\_i, \beta\_i$ and $s^r$ is the string $s$ reversed, gives a grammar $G$ such that if $G$ generates a palindrome, then the corresponding instance of PCP has a solution. PCP is RE though.
> 6 votes

---
Tags: formal-languages, undecidability
---


# Question
Title: why is this computational method by Knuth "effective" and "powerful"?
This is a follow-up question regarding Knuth's one formulation of the concept of an algorithm here. I am asking it here because I do not have enough reputation to post a comment to that question. To make my question self-contained, here it goes.

Knuth introduces the following formulation which "restrict the notion of algorithm so that only elementary operations are involved", (copied from the above mentioned question):

> Let $A$ be a finite set of letters. Let $A^\*$ be the set of all strings in $A$ (the set of all ordered sequences $x\_1$ $x\_2$ ... $x\_n$ where $n \ge 0$ and $x\_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^\*$ . Now let $N$ be a non-negative integer and Q (the state) be the set of all $(\sigma, j)$, where $\sigma$ is in $A^\*$ and j is an integer $0 \le j \le N$; let $I$ (the input) be the subset of Q with $j=0$ and let $\Omega$ (the output) be the subset with $j = N$. If $\theta$ and $\sigma$ are strings in $A^\*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta\_j$, $\phi\_j$ and the integers $a\_j$, $b\_j$ for $0 \le j \le N$:
>
> * $f((\sigma, j)) = (\sigma, a\_j)$ if $\theta\_j$ does not occur in $\sigma$
> * $f((\sigma, j)) = (\alpha \phi\_j \omega, b\_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta\_j \omega$
> * $f((\sigma,N)) = (\sigma, N)$

He describes this formulation as effective and powerful.

My questions are:

1. What is the purpose of $\alpha$ being the "shortest possible string for which $\sigma = \alpha \theta\_j \omega$?
2. Why is it so powerful? For example, if we are doing repeated multiplication (say compute $x^{10}$ given some $x \in I$), the string replacement values $\phi\_j$ have to be predefined without knowing the value of $x$; but it seems that $\phi\_j$ would have to depend on the specific value of $x$. So how does it really work?

Clearly I am missing something. Any help would be appreciated!

# Answer
You have packed several questions into your post, but it sounds like your main question is: how do we know that this is "powerful enough to do anything we can do by hand"?

The answer is: strictly speaking, we don't. But because this is enough to express anything that can be computed on a Turing machine, we strongly expect this will be enough to express any feasible computation. See the Church-Turing thesis for a detailed explanation of this belief/hypothesis/conjecture and why it appears to be reasonable.
> 1 votes

# Answer
1. It's necessary to have some restriction such as "$\alpha$ is shortest possible string for which $\sigma = \alpha \theta\_j \omega$" so the algorithm is unambiguous, because it's possible for $\theta\_j$ to appear at multiple locations in $\sigma$.
2. After seeing Knuth's answer to exercise 1.1.8, I see how something like $x^k$ can be computed this way. Below is my rather cumbersome approach.

Let $A = \\{a,b,c,d,e,t\\}$ and $N=10$.

Given $x,k$ where $x\>0$ and $k \ge 0$, the input will be $a^xb^k$ ($2^3$ would have input $aabbb$), and output will be the string $c^{x^k}$ ($x^k$ number of $c$'s. empty string denotes 1).

\begin{array}{cccccc} j & \theta\_j & \phi\_j & b\_j & a\_j & \text{comments}\\ 0 & b & (\text{empty}) & 1 & 9 & \text{remove one $b$. if no $b$, done.} \\ 1 & c & c & 3 & 2 & \text{if first time (no $c$'s), add $c$. else expand} \\ 2 & a & tc & 2 & 8 & \text{add a $c$ for each $a$} \\ 3 & a & t & 4 & 6 & \text{for each $a$, add in $c$ amount of $d$'s} \\ 4 & c & ed & 4 & 5 & \text{for each c, add in a $d$} \\ 5 & e & c & 5 & 3 & \text{change $e$ back to $c$} \\ 6 & c & (\text{empty}) & 6 & 7 & \text{clean up. remove all $c$'s} \\ 7 & d & c & 7 & 8 & \text{clean up. change all $d$'s back to $c$'s}\\ 8 & t & a & 8 & 0 & \text{clean up. change $t$'s to $a$'s}\\ 9 & a & (\text{empty}) & 9 & 10 & \text{remove all $a$'s. return} \end{array}
> 3 votes

# Answer
am skimming your questions & their answers on this subj but basically Knuth seems to be creating a rather involved representation of what Hopcroft & Ullman & others have called/defined less complexly an "instantaneous description" of the machine state.

the basic idea is that the entire *current execution* state of the machine including the head position can be encoded as a string, where the string contains the *machine table* state as a symbol embedded along with the tape symbols, and the sequence of TM operations over time can be represented as what is also called a "computational tableau" or a sequence of these strings, transformed by a single TM operation. his basic point is that operations which construct a computational tableau (via string transformations) are Turing complete. not sure of his details but that would be his justification for calling it "effective and powerful".

this is a picture from wikipedia showing a "computational tableau". the underline under a symbol indicates the head position, and note a new set of "composite" symbols "input/output symbol plus underline" can be added to represent it. the ID is the 2nd & 3rd columns encoded as a single string:

test http://upload.wikimedia.org/wikipedia/en/f/f9/State\_diagram\_3\_state\_busy\_beaver\_4\_.JPG
> 1 votes

---
Tags: computation-models
---


# Question
Title: Without using pumping lemma, can we determine if $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?
Without using pumping lemma, can we prove $A =\\{ww \mid w \in \\{0,1\\}^\* \\}$ is non regular?

Is $L= \\{w \mid w \in \\{0,1\\}^\* \\}$ non regular? I'm thinking of using concatenation to prove the former isn't regular. If L is non regular then so is LL

# Answer
Your idea (while interesting) is unlikely to work for two reasons:

1. How would you express $A$ as a concatenation of a language with itself?
2. If $L$ is non-regular, it may still be the case that $LL$ is regular. See this post: Is $A$ regular if $A^{2}$ is regular?

You could prove it using the Myhill-Nerode theorem - show that there are infinitely many equivalence classes. Or you could simply use a pumping argument without the lemma. That is, follow the proof of the lemma for this particular language.
> 12 votes

# Answer
If you can't or don't want to use the pumping lemma, you can always fall back on the pigeonhole principle.

We will prove that $A = \\{ww \mid w \in \\{0,1\\}^\* \\}$ cannot be the language accepted by any DFA, which means that it isn't regular.

In particular, let $\rm M$ be a DFA with $k \< 2^n$ states, and consider the set $P = \\{w \mid w \in \\{0,1\\}^n \\}$. Since $P$ has $2^n \> k$ members, it follows from the pigeonhole principle that there exists a pair of distinct words $w\_1, w\_2 \in P$ such that $\rm M$ is in the same state after reading either $w\_1$ or $w\_2$.

But this implies that, if $\rm M$ accepts the string $w\_1 w\_1 \in A$, it must also accept the string $w\_2 w\_1 \notin A$. Thus, $A$ cannot be the language accepted by $\rm M$. Since this holds for *any* DFA $\rm M$, it follows that $A$ is not a regular language.
> 8 votes

# Answer
You can use the incompressibility method to bypass the pumping lemma. I can't find a reference, but the sketch of the proof is something like this:

Let $w$ be a large and incompressible bitstring (Kolmogorov complexity tells us that $w$ exists). Assume for a contradiction that A is regular. Simulate the DFA that accepts $ww$. At the moment that the DFA has read the last symbol of the first copy, 'pause' it and store the whole DFA, plus its current state and the length of the string $|w|$. This can be done in a fixed number of bits for the DFA and a logarithmic term $O(\log|w|)$. Since $w$ is the only string of length $|w|$ that the DFA accepts from this state, it is a description of $w$ in fewer bits than $|w|$ (because we can choose $w$ any length). This is impossible, so it proves that $ww$ cannot be accepted by a DFA.

\[Edited after Yuval's comments\]
> 4 votes

# Answer
Let $X = \\{0^n1 \mid n \in \mathbb{N}\\}$, and observe that each member is uniquely determined from its length.

Consider two strings $x\_1, x\_2 \in X$ where $x\_1 \ne x\_2$. Then clearly $x\_1 x\_1 \in A$ and $x\_2 x\_1 \not \in A$ (since $x\_1$ and $x\_2$ have different lengths, either $x\_2 x\_1$ has odd length or the first half ends with a $0$ but the second half ends with a $1$). In other words, $x\_1$ is a witness that $x\_1$ and $x\_2$ belong to different classes of the Myhill-Nerode equivalence relation.

Since any two unequal strings in $X$ belong to different equivalence classes and there's an infinite number of strings in $X$, the language $A$ has an infinite number of equivalence classes. By the Myhill-Nerode theorem, $A$ cannot be regular.

---

This feed nicely into a proof based on the pumping lemma: assume that $A$ is regular, and let $p$ be given such that $\forall s \in A: |s| \ge p \Rightarrow (\exists x, y, z: s = xyz \land |xy| \le p \land |y| \ge 1 \land \forall i \in \mathbb{N}: xy^iz \in A)$. In particular, let $s = w^2$ where $w = 0^p1$. Then, by the pumping lemma you could remove a zero from the first copy of $w$, or insert any number of zeros, and still have a member of $A$. This is not true, so $A$ is not regular.

---

The intuition in both proofs is the same: to recognize that the second half of $s$ equals the first half, you have to remember the entire first half. But there are at least as many distinct first halves as there are members of $\mathbb{N}$, so no *finite* memory automaton can do that.
> 2 votes

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


# Question
Title: Minimum number of states in DFA accepting strings where the numbers of a and b are divisible by X and Y respectively?
While studying automata theory a typical problem that I face is of the following type:

> Constructing a DFA with minimum number of states for all strings over $\\{a,b\\}$ which have number of $a$’s divisible by $X$ and number of $b$’s divisible by $Y$ (where $X$ and $Y$ are some positive integer values).

Is there some standard way of solving such problems?

I looked it up over the net and most people seem to have an idea that minimum number of states will be $X \cdot Y$. I don't think that is right. I constructed a DFA with 15 states for $X = 6$ and $Y = 8$.

Also along a similar line suppose the problem is changed slightly and we are given "number of $a$'s mod $X$ = $P$ and number of $b$'s mod $Y$ = $Q$".

I believe this type of problem will also have a similar solution as the above problem. Only difference will be in the final states of the two machines. Can someone please confirm whether I am right about this?

# Answer
I think the minimum number of states *is* $X\cdot Y$. In particular, for $X=6$ and $Y=8$, I think 48 states are required.

One can prove this using Myhill-Nerode. The equivalence class (in Myhill-Nerode) of string $s$ is uniquely determined by the pair $\langle n\_a(s) \bmod X, n\_b(s) \bmod Y \rangle$, where $n\_a(s)$ counts the number of $a$'s in $s$, and $n\_b(s)$ the number of $b$'s. Two different equivalence classes $\langle i,j \rangle$, $\langle i',j' \rangle$ can be separated by the suffix $a^{X-i} b^{Y-j}$, since that'll take the former to an accepting state and the latter to a non-accepting state (if $i \ne i'$ or $j \ne j'$). This gives us $X \cdot Y$ different equivalence classes, so any DFA accepting this language must have at least $X \cdot Y$ states.

Are you sure you can do it in 15 states, for $X=6$ and $Y=8$? Is it possible you might have made a mistake somewhere in your DFA?
> 6 votes

# Answer
You could use the Myhill–Nerode theorem to find the minimum number of states, that is equal to the number of the equivalence classes.
> 2 votes

# Answer
A technique that is particularly helpful in problems like the ones you've given is to construct the cartesian product of two finite automata. (The relevant part of the link starts at slide 26.) In your situation, you'll construct two FA, one, $M\_1$, for the language $$ L\_1 = \\{a^k \mid k\equiv 0\pmod X\\}\quad\text{i.e, strings of $a$s with length a multiple of $X$} $$ One such machine will have $X$ states, $p\_n,\ (0\le n \< X)$, each corresponding to the situation where the number of $a$s seen so far is congruent to $n\bmod X$. It's clear that the transitions in $M\_1$ will be $\delta(p\_n, a) = p\_{n+1 \pmod X}$.

In a similar way, construct another FA, $M\_2$ for the language $$ L\_2 = \\{b^k \mid k\equiv 0\pmod Y\\}\quad\text{i.e, strings of $b$s with length a multiple of $Y$} $$ As above, denote the states of $M\_2$ by $q\_n,\ (0\le n \< Y)$ with transitions defined to be $\delta(q\_n, a) = q\_{n+1 \pmod Y}$.

Now here's where the product construction comes in. Make a new FA whose states are pairs of states $(p\_i, q\_j)$ each component of which acts like the ones in $M\_1$ and $M\_2$. In other words, we'll have $X\cdot Y$ such pairs, with transitions $$\begin{align} \delta((p\_i, q\_j), a) &= (p\_{i+1\pmod X}, q\_j) \\ \delta((p\_i, q\_j), b) &= (p\_i, q\_{j+1\pmod X}) \end{align}$$ For example, with $X=2, Y=3$ the product machine will have 6 states, $(0,0),(0,1),(0,1),(1,0),(1,1),(1,2)$, and if we happen to be in state $(1,1)$ and see input $abb$ our transitions will be $$ (0, 1)\stackrel{a}{\longrightarrow}(1, 1)\stackrel{b}{\longrightarrow}(1, 2)\stackrel{b}{\longrightarrow}(1, 0) $$ Now what should the final state of this machine be? In your first example, it's easy to see that it should be $(0,0)$, namely when we've seen an input where the number of $a$s is divisible by $X$ and the number of $b$s is divisible by $Y$. Similarly, in your second example, the final state should be $(P, Q)$.

\[It's worth noting that the construction of this product machine, $M\_1\times M\_2$, works for any FA $M\_1, M\_2$ and, by suitably choosing the final states, can be used to construct machines for the union, intersection, and difference of any regular languages.\]
> 2 votes

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


# Question
Title: minimizing the summed cardinality of set unions
this optimization problem, I am working on, is kind of making me crazy. ;)

Given is a list `o` of sets (with finite cardinality) of strictly positive integer values (Z\>0), e.g.:

```
o_without_sizes =
[ {1, 2, 3, 4}
, {5, 6}
, {2, 3, 4, 5}
, {5, 6, 7}
, {7, 8}
. {9} ]

```

Every set has a name `n` (also in Z\>0, but only for identification) and a fixed independent size value `s` (also in Z\>0), e.g.:

```
type O = [(Name, Size, Values)]
o =
[ (1, 2, {1, 2, 3, 4})
, (2, 1, {5, 6})
, (3, 2, {2, 3, 4, 5})
, (4, 3, {5, 6, 7})
, (5, 2, {7, 8})
. (6, 1, {9}) ]

```

These sets are to be combined to unions `b` of a maximum size value sum `h (>= max s, that means that no set has a size making it too big to fit into a single union)`, e.g. 4.

The goal is to find the `b` so that the sum of cadinalities of the unions in it is as small as possible. here is a bad `b`:

```
size:   3,  cardinality:   6,   sets: [1,2]  ,  values: [1,2,3,4,5,6]
size:   2,  cardinality:   4,   sets: [3]    ,  values: [2,3,4,5]
size:   3,  cardinality:   3,   sets: [4]    ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  16

```

and the optimum `b` for this example:

```
size:   4,  cardinality:   5,   sets: [3,1]  ,  values: [1,2,3,4,5]
size:   4,  cardinality:   3,   sets: [2,4]  ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  11

```

Until now I only implemented a naive brute force solution (Haskell code): http://lpaste.net/7204008959806537728

I was hoping to find a dynamic programming solution like it exists for the (Z\>0) 0-1 knapsack problem, but did not yet succeed. Is my problem perhaps NP-hard? If so, is it many-one-reducible to SAT or something? Or is there a good approximation?

Of course, if there exists a known efficient optimal algorithm, it would be awesome if you could enlighten me. :)

# Answer
Apparently, your problem is NP-complete (thanks FrankW), so we cannot expect a polynomial-time solution.

Nonetheless, if you are forced to do the best you can in practice, you might try formulating this as an integer linear programming (ILP) problem. You can introduce integer zero-or-one variables $x\_{i,j}$, with the intended meaning that $x\_{i,j}=1$ if set $j$ is present in the $i$th union, and $x\_{i,j}=0$ otherwise. This intended meaning can be enforced by adding constraints $0 \le x\_{i,j} \le 1$ and

$$\sum\_j \text{size}(j) x\_{i,j} \le h \forall i,$$

$$\sum\_i x\_{i,j} \le 1 \forall j.$$

Now you introduce zero-or-one variables $y\_{i,j}$, with the intended meaning that $y\_{i,k}=1$ if the $i$th union includes the integer $k$, and $y\_{i,k}=0$ otherwise. This intended meaning can be enforced by adding constraints $0 \le y\_{i,k} \le 1$, and for each set $j$ that contains the integer $k$, we add the constraint

$$y\_{i,k} \ge x\_{i,j} \forall i.$$

Also, for each $i,k$, we add the constraint

$$y\_{i,k} \le \sum\_j x\_{i,j}$$

where the sum ranges over all sets that contain the integer $k$.

Then you maximize the objective function

$$\sum\_{i,k} y\_{i,k}.$$

The solution to this ILP instance will give you the optimal solution to your optimization problem.
> 3 votes

# Answer
Your problem is NP-complete. We show this by reducing Partition to it.

In Partition you are given a set of numbers $a\_1, \ldots, a\_k$ and have to decide, if this set can be partitioned into two sets that sum up to the same value.

We map an instance of Partition to your problem by introducing for each $a\_i$ the set $(i, a\_i, \\{1\\})$. Set the maximum size to $\frac 12\sum\_{i=1}^ka\_i$. The original instance can be partitioned if and only if the resulting one can be united to cardinality sum 2.
> 3 votes

---
Tags: algorithms, np-complete, optimization, dynamic-programming, np-hard
---


# Question
Title: A flawed theorem about regular languages
I am struggling with this question for a very long time and just can't find the flaw. So I am given a false Theorem:

> The language $\\{awwa \mid w \in \\{a,b\\}^\* \\}$ is regular.

Well, that part is obvious, we can prove that the language is not regular using the pumping lemma.

The question I am asked is to find the flaw in the "proof" for this theorem:

> Let
>
> $\qquad L\_1 = \\{ aw \mid w \in \\{a,b\\}^\* \\}$
>
> $\qquad L\_1^R = \\{ wa \mid w \in \\{a,b\\}^\* \\}$
>
> Let $L\_2 = L\_1 L\_1^R = \\{ awwa \mid w \in \\{a,b\\}^\*\\}$ be even-length palindromes that begin and end with an $a$. Since $L\_1$ is regular, and the class of regular languages is closed under reversal and concatenation, we conclude $L\_2$ is also regular.

Can you find the flaw? I could build a DFA for $L\_1$ and $L\_1^R$, so I know they are regular. And regular languages are closed under reversal and concatenation.

But, however, $L\_2$ is still not regular, so where is the mistake in the "proof"?

# Answer
The concatenation of $L\_1$ and $L\_1^{\mathrm{R}}$ is not $\\{awwa\mid w\in\\{a,b\\}^\*\\}$.
> 2 votes

# Answer
Remember that for some languages $L\_1$, $L\_2$, $LL = \\{uv \\;\colon\\; u \in L\_1,\\;v \in L\_2\\}$. Back to your question, is it the case that for every $au \in L\_1$ and $va \in L\_1^R$ that $auva$ is an even length palindrome that begins and ends with $a$?
> 1 votes

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


# Question
Title: Does NP-Complete imply non-satisfiability?
I've seen a lot of text concerning the first NP-Complete problem, Boolean Satisfiability. I guess I'm confused concerning the language.

It sounds to me as though the problem could be difficult to compute (hence the NP-complete), however it still might be satisfiable. As in, there *exists* a satisfying mapping of literals. We can't necessarily compute it easily, but it's out there.

In fact, I would guess that the two adjectives really have no relation to each other. But, when working with problems, I am often asked to see whether a set of clauses is satisfiable. Does that mean, *Can we compute a satisfying mapping?* And by extension, does NP-complete imply that a given CNF setup is unsatisfiable?

# Answer
You're confusing languages and instances of them. A 3SAT *formula* could be either satisfiable or unsatisfiable. The 3SAT *problem* is to decide whether a given 3SAT formula is satisfiable. The 3SAT *language* is the set of all encodings of satisfiable 3SAT formulas. Only the 3SAT language is NP-complete. NP-completeness is a property of languages, not of their instances. If every 3SAT formula were satisfiable (or every one were unsatisfiable) then 3SAT (the language) would be very easy.
> 7 votes

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


# Question
Title: How does worst-fit memory allocation react when encountering contiguous empty memory blocks?
So I have a problem understanding how the worst-fit protocol for memory allocation reacts to contiguous blocks of empty memory. None of the examples I have found address this possibility.

For example, say you have the following blocks (where 'O' stands for occupied block and 'E' stands for empty block) and are to allocate 10 MB via the worst-fit algorithm:

```
------------------------------------------------------------
|10 MB O | 40 MB E | 10 MB O | 20 MB E | 30 MB E | 10 MB O |
------------------------------------------------------------
----0---------1---------2---------3---------4---------5-----

```

My question is does the worst-fit algorithm select block one leaving behind a 30 MB hole in block 1, or does it select block 3 leaving behind a cumulative 40 MB hole between blocks 3 and 4?

# Answer
> 1 votes
You have to assume that the blocks are what they are; if they can be coalesced into larger blocks, then this has already happened (ergo, perhaps the blocks that you have before you are not in fact adjacent in memory; they are an abstract list!) So, in short, there is no cumulative hole which spans multiple blocks.

So worst fit just walks the list of free blocks that it knows about and finds the largest block and takes from there.

# Answer
> 0 votes
I think as per definition of Worst-Fit Algorithm : It will directly go to select the largest block and i.e. Block 1 of 40 MB.

As Worst Fit Algorithm says that the largest memory block will be occupied first and leaving behind the remaining vacated space.

# Answer
> 0 votes
There are two strategies one could use when allocating/deallocating memory. Let's concentrate on deallocating memory. One could simply add a previously used block to the list of free blocks. As in your example, that leads eventually to perhaps having plenty of space to allocate another block, which the OS simply wouldn't see. The other strategy, known as coalescing, is to modify the deallocation routine so that when a block is to be freed, to check its left and right neighbors and make a single larger free block by merging it with any free neighbors. In this strategy, it's often useful to include pointers in each block, pointing to the left and right neighbors. Any good operating systems text will have further details.

---
Tags: algorithms, operating-systems, memory-allocation
---


# Question
Title: When do type systems start needing a logic engine?
I've noticed that some languages include a logic engine as part of their type system (e.g. Shen, Typed Clojure).

Other languages have a much more direct type checking algorithm (e.g. Haskell / Hindley-Milner).

What specific features of a type system make it necessary to include a logic engine?

# Answer
> 7 votes
I'm not sure where you would draw the line between "direct type checker" and "logic engine". In a deep sense every type checker for a modern type system is a theorem prover (or proof-checker; more on this in a moment). The theorem to be proven is "the program is well-typed", or "this function has type X".

Modern type systems and their checking/inference algorithms tend to be specified in terms of logic; typically intuitionistic typed logic (a.k.a. Martin-Löf theory). If you have a look at, say, the paper for the standard Hindley-Milner type inference algorithm \[1\], you'll see that it's specified abstractly in terms of logic. Let-polymorphism also relies on the Robinson unification algorithm, famously used in Prolog.

I'm going to go out on a limb here and suggest that the degree to which a type inference algorithm resembles a "logic engine" (however you define it) depends on how "decidable" the rules are, and how much "inference" you need to do (as opposed to merely "checking"). The type system of the simply-typed lambda calculus is intuitionistic logic (and I do mean it really is the same thing; this is the famous Curry-Howard correspondence), so you'd think that any type checker for that system is a "logic engine" in any reasonable sense. But because you only need to "check" rather than "infer", it's a proof checker rather than a theorem prover.

The standard introductory reference on this topic is TaPL \[2\]. If you're at all interested in this topic, it's well worth a read; any well-stocked university library should have a copy.

---

1. Principal type-schemes for functional programs by Damas and Milner (1982).
2. Types and Programming Languages by Benjamin C. Pierce.

---
Tags: programming-languages, compilers, type-theory
---


# Question
Title: TM for $0^{5^n}$. Describing a turing machine that decides the language consisting of all strings of zeroes whose length is a power of 5
I am trying to describe a TM that decides the language $A=\\{0^{5^n} \mid n\ge0\\}$.
I know how to do this for $0^{2^n}$, marking off every other 0 in each pass. In my case would it work marking off every fifth 0 in each pass? It would reject if there are an even number of 0s. Every pass reduces the number of 0's by a fifth until there are no more 0s.

# Answer
I'm gonna guess you're in s.datta's class? I am not sure if this is correct but I tried to cross off 4 0's each time instead of 1. It's like multiplying by 0.2 or the inverse operation of \*5)

1\*5 = 5
5\*5 = 25
25\*5 = 125
125\*0.2 = 25
25\*0.2 = 5
5\*0.2 = 1

Edit: formatting
> 1 votes

# Answer
Your idea is correct. Essentially what you're doing in each pass is checking that the number of $0$s is a multiple of 5. If it is, you make another pass and if it's not you reject. Here's what happens to the tape when $n=2$: $$\begin{align} \text{Initial: } & \mathtt{0000000000000000000000000} \\ \text{After pass 1: } & \mathtt{xxxx0xxxx0xxxx0xxxx0xxxx0}&\text{a multiple of five zeros, so continue} \\ \text{After pass 2: } & \mathtt{xxxxxxxxxxxxxxxxxxxxxxxx0}&\text{okay so far}\\ \text{After pass 3: } & \mathtt{xxxxxxxxxxxxxxxxxxxxxxxx0}&\text{done} \end{align}$$

The idea here is to stop when there's a single zero, since, of course $5^0=1$, so $0^{5^0}=0^1=0\in A$. As usual, there are some further details to deal with, but your idea is correct.
> 1 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: branch prediction buffer - 5 stage integer MIPS
will you recommend use of branch prediction buffers for 5 stage integer MIPS pipeline. Does this increase the efficiency or not?

# Answer
> 2 votes
Given a scalar 5-stage pipeline with a branch delay slot (and branch resolution in the decode stage) like the MIPS R2000, branch prediction would have almost no benefit since a branch would usually be resolved before the next instruction address is needed. This simple pipeline also has no support of speculative execution or fetching ahead. (A branch predictor might improve performance for such a simple pipeline if the branch could not be resolved in the decode stage because the dependent data was not yet available, e.g., a data cache miss, *and* the branch target was an instruction cache miss. In that uncommon case, a branch predictor would allow prefetching of the branch target.)

A simple 5-stage pipeline *without* a branch delay slot or with the branch direction or target resolved in the execute stage (rather than in the decode stage) could benefit from branch prediction. If the front-end of the pipeline was decoupled from the back-end of the pipeline (buffering instructions to allow the front-end to fetch ahead), then branch prediction would allow the buffer to be kept full which would then allow some latency in instruction cache misses to be hidden.

It might also be possible to use index and way prediction to keep the instruction cache access latency down to one cycle (i.e., without such branch prediction instruction fetch would be two cycles making a 6-stage pipeline) while increasing associativity and perhaps size (with associated increase in hit rate); but such complexity would probably not be worthwhile for such an otherwise simple design.

---
Tags: computer-architecture
---


# Question
Title: showing that the pair of Finite Automata are equivalent
Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have.

These are pairs of FA's. Set theory formula in here is `(L1' + L2)' + (L2' + L2)'`

Conclusion:

> Both machines (FA1'+FA2)' and (FA2+FA1)' has no final states. (FA1'+FA2)' to have a final state, the machine (FA1'+FA2)' must have no final state. The exact same thing half of the formula. Clearly, if we added these machines together we would get a machine with nine state and no final state. Because there is no final state, it accepts no words and two languages L1 and L2 ar equivalent.
>
> So the two regular expressions defame the same language and equivalent.

Am I in the right direction ?

# Answer
> 4 votes
Your approach works. You are effectively showing that the *symmetric difference* $L(FA\_1) \Delta L(FA\_2)$ is empty, hence $L(FA\_1) = L(FA\_2)$.

A more direct, automaton-level approach would be to build the following *product automaton* $A = (Q, \Sigma, \delta, q\_0, F)$:

* $Q = Q\_1 \times Q\_2$
* $\delta((q\_1, q\_2), a) = (\delta(q\_1, a), \delta(q\_2, a)) \ \forall (q\_1, q\_2) \in Q, a \in \Sigma$
* $q\_0 = (q\_{0,1}, q\_{0,2})$
* $F = \\{(q\_1, q\_2) \in Q \mid q\_1 \in F\_1 \Leftrightarrow q\_2 \in F\_2\\}$

Intuitively, you keep in mind the current state in both $FA\_1$ and $FA\_2$. Initially, the current states are the respective initial states $q\_{0,1}$ and $q\_{0,2}$. Then, for each input symbol $a$, you move to the respective successor in each automaton, and note the successor state (the combination of the two successor states as a pair). Of course you only draw the state for each combination only once. You can proceed either breadth-first (considering all input symbols for one product state before moving on to a newly introduced state) or depth-first (always continue with the newly introduced state and backtracking if all product successor already existed).

Note that this way you might not have to construct the full product set $Q\_1 \times Q\_2$, as you automatically prune unreachable states (you don't ever introduce them). However, the product automaton in your example will have no more than 6 states anyway, so it is rather small.

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


title: Proving 2P2N SAT is NP-Complete

text:
# Question
Title: Proving 2P2N SAT is NP-Complete
I hope I named this CNF Boolean sentence the correct way. The way I see it, a 2P2N is where each literal appears twice (or at most twice, but we can say twice without loss of generality).

I am trying to prove it is Satisfiable. How do I do this? Do I need to try to reduce it to 3-SAT (might need some help doing that as well). Or is there another method of proving satisfiability?

# Answer
> 3 votes
So here is my take on this. You reduce 3SAT (or SAT, the 3-literal limit does not make anything easier here) to 2P2N in the following way:

As noted above, you cannot easily add variables with an enforced equivalent truth mapping as existing ones (specifying $x \Leftrightarrow y$ in CNF requires 1 positive any 1 negative literal of each $x$ and $y$, so you cannot extend this to an arbitrary number of "copies"). At least not directly: $(x \Leftrightarrow y) \wedge (y \Leftrightarrow z) \wedge (z \Leftrightarrow w)$ will leave you with no free literals for $y$ and $z$. However, an equivalent to the above is $(x \Rightarrow y) \wedge (y \Rightarrow z) \wedge (z \Rightarrow w) \wedge (w \Rightarrow x)$ (note that $x \Rightarrow y \equiv \overline{x} \vee y$). Hence, this "chain" requires you to use up your two positive, two negative literals for your existing variable $x$, but leaves you with one *free* negative respectively positive literals for each of $y$, $z$ and $w$. These you can use to replace any occurences of $x$ or $\overline{x}$.

# Answer
> 0 votes
Might have gotten this wrong, in the end, but here's my attempt.

Proving it's NP-complete is a two step process: 1) Prove it's in NP (obvious, it's an SAT problem) 2) Prove it's NP-hard by reducing it to 3SAT

Think about a given 3SAT problem, we'll assume it has literals that appear more than twice (otherwise what's the point). For any literal that appears too often, we just swap out a new variable with an identical Truth mapping to it and its compliment. Do this for every variable until all literals only appear at most twice. It is just as hard to solve as 3SAT at that point.

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


# Question
Title: Time complexity of 8-queen, by placeing one by one without attack
I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack.

One approach to achieve goal state is to "add a queen to any square in the leftmost empty column such that it is not attacked by any other queen". And this approach will have a state space of 2057 (also wondering: How to compute this?)

What is the time complexity if I am using Depth First search algorithm (which I think is the most suitable one)? How about the space complexity?

I am puzzled because the brunching of the search tree is reducing greatly when goes deep. $O(8^8)$ looks too much for time complexity, even for worst case.

# Answer
Let's tackle your questions one by one:

1. *State space:* I have no idea where you got this number from. The state space is ostensibly $\binom{64}{8} \approx 2^{48}/8! \approx 2^{32}$.
2. *Your approach:* What backtracking is involved here? Your algorithm as stated could either succeed or not, but it will do so very fast.
3. *Time complexity:* It is in general difficult to estimate the time it takes a backtracking algorithm to find a solution. You can try to estimate the total time it takes to go over the entire space in various ways, for example you can estimate the branching factor at each step.
4. *Space complexity:* Backtracking algorithms have very small space complexity. You're basically keeping track of one partial solution.
5. *The estimate $O(8^8)$:* Actually $8^8 = 2^{24}$ is very small. You can probably go over this search space in under a second on a modern computer.
> 2 votes

---
Tags: time-complexity, search-problem, board-games
---


# Question
Title: Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors
We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers.

The algorithm was:

> Given an array A of length n:
>
> 1. Make a flag array B of length n and initialize it with zeroes with $n$ computers.
> 2. Compare every 2 elements and write 1 in B at the index of the minimum with $n^2$ computers.
> 3. Find the index with the 0 in A with $n$ computers.

The lecturer teased us it could be done with $\frac{n}{\log n}$ computers and with $\log n$ time complexity.

After a lot of thinking I couldn't figure out how to do it. Any idea?

# Answer
> 9 votes
Divide your original array into $n/\log n$ blocks of length $\log n$. Put each processor in charge of each block, and find the maximum using the usual algorithm in time $\log n$. We now need to compute the maximum of an array of length $n/\log n$. Pair up the elements and compute the pairwise maxima to reduce the size of the array by a half. Repeat it $\log n$ times to find the maximum of the entire array.

The same idea also shows that you can compute the maximum in parallel in constant time using $n^{1+\epsilon}$ computers for every $\epsilon \> 0$. (Exercise.)

---
Tags: algorithms, search-algorithms, parallel-computing
---


title: Finding the minterm expression of F + G

text:
# Question
Title: Finding the minterm expression of F + G
I have a question that asks me to find the minterm expression of two functions added together. The two functions in this case are

F = `m(0,4,5,6)`

G = `m(0,3,6,7)`

At the moment my reasoning is that the minterm expression of F + G would be the combined minterms of each function, taking out any repetition. So the result would be:

H = `m(0,3,4,5,6,7)`

but I feel the problem *cant* be that simple, this obviously isn't the correct solution. Would finding the solution require me to break up the minterm expressions of each function back into their variable, **then** add them together and simplify? Thank you for any input

# Answer
Here is my interpretation of your notation. The function $F = m(0,4,5,6)$ is in fact $$ F = (x \land y \land z) \lor (\bar{x} \land y \land z) \lor (\bar{x} \land y \land \bar{z}) \lor (\bar{x} \land \bar{y} \land z). $$ (Perhaps positive and negative literals are switched, and possibly I am reading the bits in reverse order.)

The notation $F+G$ just means $F \lor G$. In that case, $m(S) + m(T) = m(S \cup T)$. Similarly, if $FG$ means $F \land G$, then $m(S)m(T) = m(S \cap T)$. Finally, the negation of $m(S)$ is $m(\bar{S})$. Basically, $m(S)$ is the function which is true on the truth assignments in $S$, so we can identify it with $S$. Boolean operations on functions correspond to boolean operations on sets.
> 0 votes

---
Tags: logic
---


# Question
Title: What is the possible number of states in the DFA of intersection of two given FA?
> Consider a DFA over $a,b$ accepting all strings having number of $a$ 's divible by 6 and number of $b$ 's divisble by 8. What is the minimum number of states in the resultant DFA ?

This problem can be solved by assuming 2 DFAs. One accepting the number of $a$ 's divible by 6 and the other accepting with number of $b$ 's divisble by 8. And then taking intersection of them. So what will be the number of states in the resultant DFA?

I tried drawing the DFA accepting all strings having number of $a$ 's divible by 3 and number of $b$ 's divisble by 3, and found it to have 3x3 (9) states. Can I asssume the reuslt to be 48 states for this case? Can it be inferred that the for string accepting number of $a$ 's divible by $m$ and number of $b$ 's divisble by $n$ , there will be $mn$ states? Or I need to draw it by hand? Or anything other? Any subtle hint will be very helpful.

# Answer
> 4 votes
The product construction shows that if $L\_1$ is accepted by a DFA having $n\_1$ states and $L\_2$ is accepted by a DFA having $n\_2$ states then $L\_1 \cap L\_2$ is accepted by a DFA having $n\_1n\_2$ states; browse back to the product construction to understand why. The resulting DFA need not be minimal even if the DFAs for $L\_1$ and $L\_2$ were (a trivial example is given by $L\_1 = L\_2$, assuming $n\_1\>1$). In your case, this means that if you can find a DFA for $\\{w : 6\mid \\#\_a(w)\\}$ having six states and one for $\\{w : 8\mid \\#\_b(w)\\}$ having eight states, then you can find a DFA for the intersection having 48 states.

Is this DFA minimal? You can use the Myhill–Nerode criterion to show that indeed it is: the 48 words $\\{ a^i b^j : 0 \leq i \< 6, \\; 0 \leq j \< 8 \\}$ are pairwise incomparable.

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


# Question
Title: Definition of “infix” in formal languages
I've got a simple question:

Let's say we have the following definition of a language over some alphabet: $L = \\{w \mid w \text{ contains the infix } aab\\}$

Does that mean $aab \in L$? or does "$aab$" have to be "wrapped" on both sides by other letters?

# Answer
Yes, if $A$ is the alphabet, then $L = A^\*aabA^\*$.

Now, what about terminology? Lothaire in the first chapter of his book *Combinatorics on words* gives the following definitions. A word $v \in A^\*$ is said to be a *factor* of a word $x \in A^\*$ if there exist words $u, w \in A^\*$ such that $x = uvw$. A factor is *proper* if $v \not= x$.

In my opinion, the word *infix* is also perfectly fine, since it gives a natural counterpart to *prefix* and *suffix*. Terms involving "sub" like *subword* and *substring* are also frequently used in the literature. I personally prefer to follow Lothaire and say that a word $v \in A^\*$ is a *subword* of a word $x \in A^\*$ if $v = a\_1a\_2 \cdots a\_n$ (where $a\_i \in A$ and $n \geqslant 0$) and there exist $y\_0, ..., y\_n \in A^\*$ such that $x = y\_0a\_1y\_1a\_2 \cdots a\_ny\_n$. This definition makes the term *subword* a synonym of *subsequence*, which I find quite natural.

Anyway, with so many different terminology around, it is not a bad idea to remind the reader of precise definitions if there is any risk of ambiguity...
> 2 votes

---
Tags: formal-languages, terminology
---


title: Simplification of CFG

text:
# Question
Title: Simplification of CFG
Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft.

The grammar goes as follows

S-\> aAa | aBC

A -\> aS | bD

B - \> aBa | b

C-\> abb | DD

D -\> aDa

In the explanation that follows, we eliminate D obviously, but the removal of C still baffles me. As D is non generating, but C is both generating and reachable. So why delete C?

The resultant grammar is shown as

S-\>aAa

A-\>aS

B-\>aBa | b

Here is the link to the photo of the page in the book just in case

Page 240:

Page 241:

# Answer
C isn't Part of the grammar recursion. As it expands to Terminals only, it is artificial in the Sense That it is only used for notational convenience while it is unnecessary for expressing the CFG.

The simplified grammar obviously contains a typo, as no words containing `b` are derivable contradicting `S -> aBC -> abC -> ababb` which the original grammar allows.

The first rule should probably read `S -> aAa | aBabb`.
> 1 votes

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


# Question
Title: How to deal with questions having two or more asymptotic notations
The following was asked as part of a homework assignment and I am not asking for the solution to these but rather tips or resources on how to solve this and similar questions,

Let $f(n)$ and $g(n)$ be two functions from $\mathbb{N}^+$ to $\mathbb{R}^+$. Prove or disprove the following assertions. To disprove, you only need to give a counter example for functions $f(n)$ and/or $g(n)$ which make the assertion false. Consider the following.

$$\Omega(\Theta(f(n))) = \Omega(f(n))$$

According to me the answer is false in this case, my reasoning is that whenever we say $f(n)=\Theta(g(n))$ we are saying that $f(n)$ will always lie between the limits of $g(n)$. Here, let's say $x(n) = \Theta(f(n))$ so it will always lie between the function $f(n)$ then we take $\Omega(x(n))$ which would mean that $y(n)$ will always be greater than $x(n)$, and on the right hand side we compare it to some $a(n)$ which is equal $\Omega(f(n))$ meaning that $a(n)$ will always be greater than $f(n)$. Hence we cannot say correctly if the relation will hold, it may or may not be true.

Is this the correct way of looking at the problem, is there a better way to solve these questions?

# Answer
> 5 votes
No, this is not the right way to think about this question. To get you on the right track notice that $f(n) \in \Theta(f(n))$ no matter what. This should give you the right intuition. However, you can't prove equality with just one function taken from $\Theta(f(n))$ you have to consider an arbitrary function.

If you work through carefully (I won't give you the step-by-step since active learning is important), you will see that $\Omega(\Theta(f(n))) = \Omega(f(n))$. To test your understanding after you figure this out, make sure that you can also show that $\Omega(O(f(n))) \neq \Omega(f(n))$.

The intuition you should keep in mind (that you have to make rigorous by carefully understanding this table) is that $\Omega$ is kind of like $\geq$, $O$ is kind of like $\leq$ (for lower case of both, make them strict inequalities), and $\Theta$ is kind of like $=$. But this is only heuristic intuition. Make it precise on your own, and see if you can find any weird functions that might serve as counter-examples.

# Answer
> 0 votes
I take an exception to the problem on which the question is based. The Landau notations should really be interpreted as *set* relations, i.e., one should really write $f(n) \in O(g)$. Or, as Knuth explains, the right hand side is a "crudification" of the left hand side. As sets, this makes no sense at all.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Why classes implicitly derive from only the Object Class?
I do not have any argument opposing why we need only a single universal class. However why not we have two universal classes, say an Object and an AntiObject Class. In nature and in science we find the concept of duality - like Energy & Dark Energy; Male & Female; Plus & Minus; Multiply & Divide; Electrons & Protons; Integration & Derivation; and in set theory. There are so many examples of dualism that it is a philosophy in itself. In programming itself we see Anti-Patterns which helps us to perform work in contrast to how we use Design patterns. I am not sure, but the usefulness of this duality concept may lie in creating garbage collectors that create AntiObjects that combine with free or loose Objects to destruct themselves, thereby releasing memory. Or may be AntiObjects work along with Objects to create a self-modifying programming language - that allows us to create a safe self modifying code, do evolutionary computing using genetic programming, do hiding of code to prevent reverse engineering.

We call it object-oriented programming. Is that a limiting factor or is there something fundamental I am missing in understanding the formation of programming languages?

# Answer
This is only an answer to answer the question in the title.

Languages such as Java have every class deriving from Object for two reasons.

Firstly, to increase the amount of polymorphism available. This was particularly required before generics were added to the language. Without Object, collection classes would be impossible to write in a useful fashion.

Secondly, there are many methods that classes are expected to have or are useful, and these are collected in Object. By ensuring that all classes inherit from Object, all classes will implement the same minimal interface.

As mentioned in a comment, C++ does not have a class like Object. C++ is in many ways untyped, so the issues I mention above are not applicable. Also, C++ templates provide a lot of polymorphism and are used to implement collections.
> 10 votes

# Answer
I think the accepted answer covers pretty much the original question, but I would like to supplement it (if I may) slightly by throwing in (quite informally) a few ideas regarding the secondary questions.

From an inheritance point of view, nothing prevents the class hierarchy to have several roots. As it has been pointed out by other peoples, C++, as well as many OO languages don't constraint expressiveness to a single root ancestor class.

However, from a *type theoretic* point of view (recall that inheritance and subtyping are not the same thing, so I am probably stepping out of the frame of the main question here), a single "top" supertype can make a lot of sense (depending on the type theory of course). For instance, in OCaml, there is a common supertype to all objects (whether class instances, or immediate objects), written `< >` to denote that the object type is empty, i.e. doesn't accept any message. This seems indeed the most general object type we can define, since we cannot remove anything from it to make it more general. Hence, in this conception of object types, there is necessarily a supertype to all object.

Regarding the dual of the root object, scala sports a class called `Nothing`, which curiously is also empty, and is the subtype of every other classes. It cannot be instantiated, but holds enough useful semantic to implement the empty list, which is called `Nil`, and is equal to `List[Nothing]` (as pointed out in comments, it is possible that programmer never directly use that value in most case, making it seemingly not as useful as it is). `Nothing` could be considered a dual of the root type - called `Any` in scala, however these types not only cover classes, but also primitives types, so that everything can be upcasted to `Any`, for instance.
> 3 votes

# Answer
The ability to define collections that can hold arbitrary kinds of things, without needing to define different methods for different kinds of things, is very useful. Templates in C++ make it possible for a single source file to define collection types that can hold many different kinds of things, but the compiler will have to duplicate the code for every different kind of thing in the collection. If instead one defines almost all of the types in the system to derive from a single type, then a collection which can hold references to things of that type will be able to hold references to things of almost any type.

This approach does have a limitation, however, which is that it blurs the distinctions between values and entities. A reference which encapsulates a value by identifying some particular object can be replaced with a reference to a copy of that object without altering its semantics. A reference which is used to identify an entity, however, cannot be replaced in such fashion. Either the entity itself will be something that can't be copied (e.g. if it represents a connection to something in the real world) or the entity may encapsulate *the set of references that exist to it*. A key thing to note is that objects behave as values when either they cannot change or only one reference exists to them, and they behave like entities when multiple references exist.

Blurring the distinction between values and entities makes it difficult for collection types to know whether they should regard their contents as values or entities; this in turn limits the ability of collections to implement things like `equals` or `clone` in useful fashion. Languages which make a stronger type/entity distinction can have collections do more things automatically than languages which do not, but the distinctions add some complexity, which language designers may or may not feel is justified by the benefits.
> 1 votes

---
Tags: programming-languages, type-theory, object-oriented
---


# Question
Title: Why Instruction Decode and Register Read are in the same stage of MIPS pipeline
Why are instruction decoding and register read are combined in single stage of a 5-stage MIPS-pipeline, even though they serve two different operation?

# Answer
> 3 votes
Instruction Decode and Register Read are done in parallel on that stage in order to prevent needing to wait on either to complete. There's no reason not to do this since they are both known at that point in time for the MIPS-Pipeline, and since they will most likely be needed for the next step (Execution Cycle).

By "no reason", I mean that you would effectively be using more power while separating them (as mentioned in the comments below). You would also be adding a whole extra stage in that case, as the stage before (Instruction Fetch) is what actually gets the information for ID and RR, and adding it to the stage after would not work because that stage requires both. Thus the only way to do it would be to add the stage in-between the ID stage and EX stage, which would add a whole extra cycle to every operation, which would obviously result in slow downs overall.

If you're interested in reading more about this, I'd recommend this textbook I'm using for a class (Computer Architecture: A Quantitative Approach by John Hennessy and David Patterson). It's got a pretty handy reference for MIPS especially from what I've read so far and it's where I pulled this information from.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: About trap states when converting DFA to regular expression
If we were to have a trap state in a DFA and we are converting it to a regular expression, how exactly would I incorporate that into the regex? Let's say our language only accepts a\*, and my DFA has a start state/final state with a *a* loop, and once I get a *b* it goes into a trap. Would the regex simply be *a** meaning we ignore the *b*?

# Answer
> 2 votes
Yes, since the automaton can never accept after reading a $b$.

---
Tags: regular-expressions
---


# Question
Title: the height of a tree given n nodes and a condition
I came across a question on which I got totally stuck :( a sort of homework question)

A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?

```
a) log_2 n
b) log_{4/3} n
c) log_3 {n}
d) log_{3/2} n

```

I cant imagine to solve this one. Intuitive based answer is most welcome.

# Answer
> 3 votes
The height of a tree is 1 + the height of its highest subtree. Which way of distributing the nodes to the subtrees will allow you to maximize that parameter?

> Put $\frac 13 n$ nodes into the left tree and $\frac 23 n$ into the right one (or vice versa).

If you apply this recursively, what do you get for the height?

> You get the recurrence $h(1) = 1$, $h(n) = 1 + h(\frac 23 n)$, $n\>1$. This solves to
> $h(n) = 1+\log\_{\frac 32}n$.

---
Tags: combinatorics, trees, discrete-mathematics
---


# Question
Title: Recurrence $T(n) = 2T(\sqrt{n}) + \log n$
So I have a question for the recurrence $T(n) = 2T(\sqrt{n}) + \log n$. We are to use substitution method to figure out the solution. This is an example problem (not a exercise problem) in my book (*Introduction to Algorithms*, Third Edition pg. 86). I'm having a hard time understanding how they rename $m = \log n$.

They then get the new equation $T(2^m) = 2T(2^{m/2}) + m$. I see that turning the $m = \log n$ into $2^m = 2^{\log n}$ and using the property $a^{\log b} = b^{\log a}$ so you get $2^m = n^{\log 2}$ which goes to $2^m = n$ and hence $\sqrt{n} = 2^{m/2}$.

My question is, how do you know to guess to substitute $m$ for $\log n$?

# Answer
> 1 votes
Since you know how to solve recurrence equations of the form $S(n) = \alpha S(n/\beta) + f(n)$, you want to transform the given recurrence into this form. You notice that $\log \sqrt{n} = \frac{1}{2}\log n$, so $m = \log n$ is a good substitution.

More generally, there are no rules on how to solve recurrence relations (or anything in mathematics). Having seen the Master theorem, you know what to do when you have a recurrence of the form $S(n) = \alpha S(n/\beta) + f(n)$. Having seen this example, you know (a) what to do when you have a recurrence $T(n) = \alpha T(n^\beta) + f(n)$, and (b) it is a good idea to try to reduce a general recurrence to one of the form $S(n) = \alpha S(n/\beta) + f(n)$ by using an appropriate substitution.

As you get deeper into the subject (if you choose to do so), you will learn more tricks that will help you solve problems. Yet sometimes a new trick will be necessary. When all else fails, you just try a lot of things with your recurrence. Hopefully, after a while a winning direction will emerge. This is called (mathematical) *research*.

---
Tags: recurrence-relation
---


title: Recognizing Horn clauses

text:
# Question
Title: Recognizing Horn clauses
I am currently studying model theory and I am trying to decide if a clause is a Horn Clause. I know that a Horn Clause is a clause with at most one positive literal, but there are some clauses that it is not easy to decide whether they are Horn or not.

E.g.,

```
(P->Q)->W

```

Is there any way to decide whether this clause is Horn or not, or do I have to make further calculations in order to bring it to a Disjunction form?

# Answer
Let's start with some definitions:

1. A *literal* is either a variable (a *positive* literal) or the negation of a variable (a *negative* literal).
2. A *clause* is a formula which is equivalent to a disjunction of literals.
3. A *Horn clause* is a formula which is equivalent to a disjunction of literals, at most one of which is positive.

Your formula $(P \to Q) \to W$ is not equivalent to a disjunction of literals. Indeed, if it were, since it depends on all variables $P,Q,W$, it would have exactly one falsifying assignment (with respect to $P,Q,W$). Yet it has three: $(P,Q,W)=(F,F,F),(F,T,F),(T,T,F)$. So it is not a clause, and in particular not a Horn clause.
> 5 votes

---
Tags: logic, artificial-intelligence, boolean-algebra
---


title: How to solve recurrences involving log?

text:
# Question
Title: How to solve recurrences involving log?
For example,

$T(n) = \log {n} \cdot T(\frac{n}{\log{n}}) + \Theta(n)$

I tried using the substitution method with $ n = 2^m $, but that got me nowhere, since it still ends up with a $m$ *and* $2^m$. The recurrence tree method also becomes rather complicated. Is there a general approach to follow to solve such recurrences?

# Answer
Define a sequence $n\_0 = n$, $n\_{t+1} = n\_t/\log n\_t$. Assuming that the underlying constant in $\Theta(n)$ is $1$, we get $$ \begin{align\*} T(n) &= \log n\_0 T(\tfrac{n\_0}{\log n\_0}) + n\_0 \\ &= \log n\_0 \log n\_1 T(\tfrac{n\_1}{\log n\_1}) + n\_0 + n\_1 \log n\_0 \\ &= \log n\_0 \log n\_1 \log n\_2 T(\tfrac{n\_2}{\log n\_2}) + n\_0 + n\_1 \log n\_0 + n\_2 \log n\_1 \log n\_0 \\ &= \cdots \end{align\*} $$ Now $n\_{t+1} \log n\_t = n\_t$, and so $n\_1\log n\_0 = n\_0$, $n\_2\log n\_1\log n\_0 = n\_1\log n\_0 = n\_0$, and so on.

Suppose now that the starting condition of your recurrence is $T(x) = 1$ for $x \leq 1$, and let $\ell+1$ be the minimal index such that $n\_{\ell+1} \leq 1$. Then $$ T(n) = \log n\_0 \log n\_1 \cdots \log n\_\ell + (\ell + 1) n. $$ In fact, $\log n\_0\cdots n\_\ell n\_{\ell+1} = n$, and clearly $n\_{\ell+1} = \Omega(1)$, showing that $T(n) = (\ell + O(1))n$.

It remains to estimate $\ell$. Clearly $n\_t \geq n/\log^t n$, and so $\ell \geq \log n/\log\log n$. For the other direction, notice that when $t \leq \log n/2\log\log n$, we have $n\_t \geq \sqrt{n}$, and so $n\_t \leq n/(\log n/2)^t$. This shows that $n\_{\log n/2\log\log n} \leq \sqrt{n} 2^{\log n/2\log\log n} \leq n^{0.51}$ for $n$ larger than some constant $C$. Repeating the same argument, $n\_{\log n/2\log\log n + \log n^{0.51}/2\log\log n^{0.51}} \leq n^{0.51^2}$ for $n^{0.51} \geq C$. Notice that $\log n^{0.51}/2\log\log n^{0.51} \leq 0.52\log n/2\log\log n$, for $n$ larger than some constant $C'$. Repeating this argument $k = O(\log\log n)$ times, we get that for $t = \log n/(2\log\log n) (1 + 0.52 + 0.52^2 + \dots) = O(\log n/\log\log n)$ we have $n\_t = n^{0.51^k} = O(1)$. This shows that $\ell = \Theta(\log n/\log \log n)$, and so $$ T(n) = \Theta(n\tfrac{\log n}{\log\log n}). $$
> 3 votes

---
Tags: asymptotics, recurrence-relation
---


title: Logspace Transducer

text:
# Question
Title: Logspace Transducer
I know that a logspace transducer is a deterministic Turing machine that enables us to use log-space complexity. I do not understand though why that is correct. Whatever algorithms can be implemented in that machine are automatically of log-space complexity? Why is that?

# Answer
> 3 votes
A logspace transducer is a function which can be computation in logarithmic space (in terms of input size). This is just the definition. One important property of logspace transducers is that the composition of two logspace transducers is another logspace transducer; this is not as trivial as it looks.

P-completeness is defined with respect to logspace reductions. In other words, the many-one reductions considered are logspace transducers. Compare this with the definition of NP-completeness, in which the many-one reductions are polytime. The reason we have to restrict the power of the reductions (from polytime to logspace) is that every problem in P is trivially P-complete with respect to polytime reductions (exercise).

The composition property of logspace transducers is important for the following theorem: if $L$ is P-complete and $L$ reduces to $M$, then $M$ is P-complete. If you follow the proof carefully, you will see that it is crucial that the composition of two logspace transducers is another logspace transducer.

---
Tags: turing-machines, space-complexity
---


title: Recurrence Problem $T(n) = 3T(n/3) + n$

text:
# Question
Title: Recurrence Problem $T(n) = 3T(n/3) + n$
My question here is dealing with the residual that I get. We are trying to prove $T(n) = 3T(n/3) + n$ is $O(n\*\log n)$. So where I get is $T(n) \le cn\[\log n - \log 3\] + n$. So my residual is $-cn\log 3 + n$. So if I minus it I get $-(cn\log 3 -n) \ge 0$ right? How do I figure out what values of c & n are? Do I use the base case? And as long as my negative residual is greater than 0 then my desire is correct because as n grows large then the residual doesn't matter?

# Answer
You are trying to prove $T(n)\le c\cdot n\log n$. Substituting in the equation, you get the recursive structure as $T(n)\le c\cdot n\log n-\left(c\cdot n\log 3-n\right)$. Since $\log 3 \>0,$ even for $c=1$, the residual will be greater than $0$. This is exactly what you wanted. You don't need to take any base case because if the equation $T(n)\le c\cdot n\log n$ is true for $c=1$, it is also true for $c\>1$.

Finally, your residual is correct.
> 0 votes

# Answer
Please remember the definition of O(n\*logn), if there's a c's value exist, the proposition is right.

In your case, you can assign the c with the value with is less than 1/(log3), and your answer is right.

Anyway, I think this kind of method to solve complexity-theory problem is not quite easy, you may try other methods, such as "recursion tree" or master theorem.
> 0 votes

---
Tags: recurrence-relation
---


# Question
Title: How to use Artificial Intelligence in Computer Chess
In some (historical) papers, chess has been referred to as the drosophila of artificial intelligence. While I suppose that in current research, the mere application of a search algorithm is at best *advanced computer science*, I believe that there are still area's where can apply (and practice) AI-techniques.

A simple example would be *opening book learning* where one can *teach* the program whether to use or to not use certain moves in the opening because the program is unsuited to certain types of position. We can use a form of re-inforcement learning and automate this: I suppose I could play the program against itself and increase the probability of winning lines and decrease the probability of losing lines.

The more complex example is to use a learning *evaluation* function (for example, one could tweak the values of *piece-square tables*). However, I'm thinking:

* given all the noise due to there being an enormous amount of realistic positions (as opposed to the amount of realistic opening lines)
* and with the cost (duration) of a computer chess game, and the need to play loads.

How can one do this effectively? (or should I look at other techniques, for example neural networks.)

# Answer
> 16 votes
The whole state space for chess is enormous - it can be roughly estimated as 1043 (Shannon number (Shannon, 1950), (Wikipedia)).

The idea you present - Reinforcement Learning agents playing with each other to learn the game - was successfully applied to Backgammon - TD-Gammon (Tesauro, 1995), (Chapter in Reinforcement Learning by Sutton&Barto). It also used Neural Networks to estimate game's value function. This problem is however much simpler, as number of states in Backgammon is significantly smaller than in chess, namely: 18,528,584,051,601,162,496 (Backgammon Forum Archive thread).

If you, however, would end the game after few initial moves and aim only to learn "good openings" you could succeed with analogous approach. The main problem would be to evaluate the game after the opening game, which seems hard. Just a similarity measure to the established positions after well known openings is not enough, because position can be far from them if opponent would make a stupid move (so it wouldn't be because of learning agent's mistake, so the position even if "incorrect" should be evaluated as a good outcome).

References:

# Answer
> 3 votes
I am pretty sure that any possible (or weird) method of AI or ML in textbooks has been tried and pretty much failed compared to simple brute force.

My personal perspective is that chess per se is of no interest to modern AI any more... Simply, because *it is solved*: by just using a modern computer and brute force. So, I don't feel that there is a need to create an "intelligent" system to solve it more efficiently (works just fine in my cell phone), and I believe that there isn't even the need for some unknown and more "intelligent" approach to exist.

# Answer
> 2 votes
I think it's worth noting that in order to determine how to tackle an AI problem you must define it. Whether it is *Fully Observable* or *Partially Observable*, and whether it is *Deterministic* or *Stochastic*/Chance.

Chess is Fully Observable, (unlike Backgammon, Monopoly or Poker for example) It is also Deterministic (like Checkers, and Go for example) Lastly, adversaries exist and because of that when determining next best move it is useful to use **Adversarial Search** type of algorithms such as MiniMax. Classifying a problem can help us determine what kind of search algorithm we'd want to apply. And in case of chess, Adversarial Search would be fit.

Minimax in particular has a

Time Complexity is $O(b^n)$

Space complexity of $O(bm)$ (depth-first)

So in case of chess, b would be 35, and m would be 100 There are ways around it or strategies for making it more efficient, like alpha-beta cutoff.

---
Tags: artificial-intelligence, board-games
---


# Question
Title: Selection of parameters for genetic algorithm
How can one select the proper number of parameters for a genetic algorithm to model a given system?

For example, say you want to optimize production of cars, and you have 1,000 measurements of hourly efficiency at various tasks for each of 1,000 different employees. So, you have 1,000,000 data points. Most of these are likely to be weakly correlated to the overall efficiency of your factory, but not *so* weakly that you can say they are irrelevant with statistical confidence. How do you go about picking inputs for your GA so that you don't have 1,000,000+ degrees of freedom, resulting in very slow convergence or no convergence at all?

Specifically, what are the algorithms one could use to pre-select or selectively eliminate features?

One approach I have used myself in this scenario is to evolve the parameter selection itself, so I might have parents like `{a,b,c}`, `{b,d,e,q,x,y,z}`, and so on. I would then mutate the children to add or drop features. This works well for a few dozen features. But the problem is that it is inefficient if there is a large number of degrees of freedom. In that case, you are looking at `10^n` combinations (in the example above, `10^1,000,000`), which makes some pre-filtering of features critical to get any kind of useful performance.

# Answer
First of all - the example doesn't seem well suited because you would probably use some regression or classical ML methods to solve this. Secondly - you are referring to a general problem of *feature selection* (Kira, Rendell, 1992) or *attribute selection* (Hall, Holmes, 2003) or *variable selection* (Guyon, Elisseeff, 2003) or *variable subset selection* (Stecking, Schebesch, 2005) or *feature extraction* (Hillion, Masson, Roux, 1988) or *dimensionality reduction* (Roweis, Saul, 200) or *state abstraction* (Amarel, 1968). This problem is relevant not only to genetic algorithms but for almost all machine learning techniques when dealing with high dimensional data.

Three cases can be distinguished here: the last instance of this problem known as *state abstraction* is usually related to process modelling (which suits your example, but not the GA context). The first three, i.e. *feature selection*, *attribute selection* or *variable selection* seem to be most relevant when taking your question literally. In this context a common solution is the mRMR approach (Peng, Long, Ding, 2005). From my experience it doesn't always work well with continuous data - however, mutual information can be substituted with other coefficients, like correlation for example. Another possible approach is to use cross-validation (Picard, Cook, 1984) for this. You can have multiple models each using different features, and by means of model selection with cross-validation techniques you choose the best model, which gives you the information on which features work best for the given task.

The *feature extraction* and *dimensionality reduction* cases allow to not only select initial features, but also their combinations. A well-known example solution for this case is the PCA algorithm (Pearson, 1901), which produces the optimal, in terms of explained variance, set of features being linear combinations of input features.

Also note, that there are many models that handle feature extraction task by themselves. Some examples are: Growing Neural Gas Network (Fritzke, 1995), LASSO (Tibshirani, 2011), RFE SVM (Zeng, Chen, Tao, 2009), Decision Trees (Quinlan, 1986).

References:
> 11 votes

# Answer
I have never done this before, and obviously don't have access to said data, but a potentially good way to do this would be through clustering. For each employee, we have an n-dimensional vector, where each dimension cooresponds to a different task. Then, we can use clustering to group "similar" employees together; however, this is going to be solely dependent on your data, ie it's quite possible that given only 1000 employees that clustering will yield groups of employees that aren't really all that related, and so while we may get a reduction in population, it may be at the expense of information loss.
> 3 votes

---
Tags: genetic-algorithms
---


# Question
Title: When should I move beyond k nearest neighbour
For many machine learning projects that we do, we start with the k Nearest Neighbour classifier. This is an ideal starting classifier as we usually have sufficient time to calculate all distances and the number of parameters is limited (k, distance metric and weighting)

However, this has often the effect that we stick with the knn classifier as later in the project there is no room for switching to another classifier. What would be good reason to try a new classifier. Obvious ones are memory and time restraints, but are there cases when another classifier can actually improve the accuracy?

# Answer
k-NN generalizes in a very restrictive sense. It simply uses smoothness priors (or continuity assumption). This assumption implies that patterns that are close in feature space are most likely belong to the same class. No functional regularity in pattern distribution can be recovered by k-NN.

Thus, it requires representative training samples, which can be extremely large especially in cases of highly dimensional feature spaces. Worse, these samples can be unavailable. Consequently, it cannot learn invariants. If patterns can be subjected to some transformations without changing their labels, and training sample doesn't contain patterns transformed in all admissible ways, k-NN will never recognize transformed patterns that were not presented during training. This is true, e.g., for shifted or rotated images, if they are not represented in some invariant form before running k-NN. k-NN cannot even abstract from irrelevant features.

Another somewhat artificial example is following. Imagine that pattern belonging to different classes distributed periodically (e.g. in accordance with sine - if it is less than 0, then patterns belong to one class, and it is greater, then patterns belong to another class). Training set is finite. So, it will be located in a finite region. Outside this region recognition error will be 50%. One can imagine the logistic regression with periodic basis functions that will perform much better in this case. Other methods will be able to learn other regularities in pattern distributions and extrapolate well.

So, if one suspect that available data set is not representative, and invariance to some transformations of patterns should be achieved, then this is the case, in which one should move beyond k-NN.
> 3 votes

# Answer
kNN is useful for large data samples

However it's disadvantages are:

1. Biased by value of k.
2. Computation Complexity
3. Memory Limitation
4. Being a supervised learning lazy algorithm
5. Easily fooled by irrelevant attributes.
6. Prediction accuracy can quickly degrade when number of attributes increase.

It's usually only effective if the training data is large, and training is very fast.
> 3 votes

# Answer
If you would be constrained by computational complexity, decision trees (Quinal, 1986) are hard to beat (especially when a framework offers direct conversion of DT model to a bunch of `if` statements - like Accord.NET).

For high dimensional data the notion of distance, on which k-NN is based, becomes worthless (Kriegel, Kröger, Zimek, 2009) (also: Wikipedia article). So other classifiers, like SVM (Corter, Vapnik, 1995) or Random Forests (Breiman, 2001), might perform better.

References:
> 3 votes

---
Tags: neural-networks, classification
---


# Question
Title: Recognizing waterways in an aerial photo -- polygons from edge detection images
I am trying to recognize waterways from aerial photographs (say from Google Maps). Local governments often have GIS data that says where the waterways (and roads, buildings etc) are, but the water data in them is often somewhat inaccurate, and we might be able to improve them using aerial imagery. So we have some data already that isn't always to be trusted.

I know how to do some basic image processing on the data (unfortunately I don't have sample images to show here yet, I'm trying to imagine how I could do this, no working code yet):

* I can collect some set of color values using bits of waterway in images, and figure out which pixels are closest to these colors, possibly also for other types of feature (grass, roads, buildings etc). If I set a threshold on which pixels are "close enough", I get a set of pixels that are probably waterways (but there will be a lot of noise).
* I can turn the image into grayscale and use a standard edge detection algorithm to figure out where the edges are. Again, this gives me a set of pixels of like boundaries, but there will be noise and edges will be too think and/or have gaps.

What I want to have as output is a set of *polygons* that outline the probable waterways.

Intuitively I'd like to use the detected edges to create polygons, and the colour information to decide which of them are water, possibly making use of the government data we already have.

Is there a known way to get from the result of an edge detection algorithm to a nice set of closed polygons? Or any other tips on how to attack this problem, if there's a better way?

# Answer
> 7 votes
This is hard to do with color information alone. Color variations between (or even within) aerial and satellite imagery can be huge. Ideally you will want hyperspectral or at least infrared imagery (see this paper).

Assuming your edge detection can snap to pixel boundaries, you can take each pixel's borders as a closed polygon and union them together to form a polygon (depending on your union implementation you may end up with a polygon with inner rings or holes) or a collection of polygons. The Java Topology Suite and other computational geometry implementations can make this much easier for you. If you want to use sub-pixel boundaries you will need to be very careful that you have a good epsilon value set so you can snap edges that are very close but not exactly touching.

If you want to take the edges and combine them yourself you will want to build a graph of intersecting edges and implement code that traverses the graph (e.g. counter-clockwise) to find where it closes in on itself to form a polygon. This is how some of the union implementations of polygons works.

---
Tags: image-processing
---


# Question
Title: What is the relation between correlation and causation in machine learning?
It is a well-known fact that "Correlation doesn't equal causation", but machine learning seems to be almost entirely based on correlation. I'm working on a system to estimate the performance of students on questions based on their past performances. Unlike other tasks, like Google search, this doesn't seem like the kind of system that can be easily gamed - so causation isn't really relevant in that regard.

Clearly, if we want to do experiments to optimise the system, we will have to care about the correlation/causation distinction. But, from the point of view of just building a system to pick questions that are likely to be of the appropriate difficulty level, does this distinction have any importance?

# Answer
Not all of AI works on correlation, Bayesian Belief Networks are built around the probability that A causes B.

> I'm working on a system to estimate the performance of students on questions based on their past performances.

I don't think you need causation for this. A past performance does not cause a current performance. Answering on an early question does not cause an answer on a later question.

> But from the point of view of just building a system to pick questions that are likely to be of the appropriate difficulty level - does this distinction have any importance?

No, not for your example. I think correlation (or even simple extrapolation) would solve your problem very well. Assign a difficulty score to each of the questions and then feed questions to the students in increasingly difficult levels (which is how most exams work) and then when the student starts getting them wrong, you can wind back the difficulty. That's a feedback algorithm that is similar to the error minimisation performed on a neuron in a multi-layered perceptron. The non-trivial piece of input spaces like this is deciding what a difficult question is!

A better example of causation in AI would be:

> My car is slowing down. My accelerator is on the floor. There is not much noise. There are lights on the dashboard. What is the probability that I've run out of fuel?

In this case, running out of fuel has caused the car to slow down. This is precisely the sort of problem that Bayesian Belief Networks solve.
> 11 votes

# Answer
> machine learning seems to be almost entirely based on correlation

I don't think so, not in general at least. For example, the main assumption for ML algorithms in terms of PAC analysis and VC dimension analysis, is that training/testing data come from the same distribution that future data will.

So in your system, you would have to assume, that each student imposes some kind of conditional probability distribution that generates answers to particular types of questions on particular topics. Another, and more problematic assumption you have to make, is that this distribution doesn't change (or doesn't change fast).
> 6 votes

# Answer
In addition to the other answers, there's an interesting topic - if you're manually selecting features, you might want to think about 'coincidental correlation' to reduce overfitting, i.e., avoiding features that somehow happen to be correlated in your training data but wouldn't/shouldn't be correlated in the general case - that there is no causal relation whatsoever.

As a crude example, let's suppose that you take a data table of historical exam results and try to predict fail/pass criteria; you simply include all available data fields as features, and that the table happens to have the students birthday as well. Now, there may well be a valid correlation in the training data that students born on 12th february almost always pass and students born on 13th february almost always fail... but since there is no causal relationship, that should be excluded.

In real life it's a bit more subtle, but it helps to distinguish correlations that fit your data to valid signals that should be learned form; and correlations that are simply patterns caused by random noise in your training set.
> 2 votes

# Answer
I agree with the prior answers.

If, however, you're interested in looking at correlation/causation in general, two items you might want to look at are:

* Pearl (yes, that Pearl) has produced one of very few decent books on it.
* Reinforcement Learning, and the multi armed bandit problem are all based around an actor trying to infer optimal courses of action in an unknown environment - i.e. they must learn which 'actions' will give them the best 'reward', and so implicitly tease out causal relationships.
> 2 votes

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