title: Algorithm for Graph merge and recompute

text:
# Question
Title: Algorithm for Graph merge and recompute
I want to construct a complete graph where each node is connected to every other node. The link between the nodes give a distance function (does not follow triangle inequality) between them. What I require is to merge the closest nodes, (bounded by a threshold) into a single node and recompute the graph each time, recursively. This is because if two nodes are merged, then all the links connected to the new node has to be updated with the newly computed distance for the new edge. Since its a complete graph this would be an expensive operation.

I would have a large number of nodes with $N\*(N-1)/2$ links for $N$ nodes , and $N=60$ or more , What I want to do is to reduce this complete graph into clusters of sub graphs with low intra node distance, yet with a relatively high distance between the subgraphs. So,How can I go about solving this problem?

This is like applying the graph partitioning techniques to complete graphs.

One of the solutions is this paper which proposes the normalized cut criterion for partitioning the graph minimizing normalized cuts on graphs which is clearly NP-complete,Is there a practically efficient way and what are the recent developments to achieve this?

So what I want is an efficient solution to the above problem which is not NP complete ? Since this problem is NP Complete , answers using randomization or approximation methods would be welcome

# Answer
> 1 votes
I suggest you start by reading about standard clustering algorithms and methods for clustering. You could start with Wikipedia: cluster analysis and hierarchical clustering, then move on to textbooks or online resources. Especially, check out hierarchical clustering to see if any of its methods might do what you want.

It sounds like you're not quite sure what you want. So, if you learn more about standard clustering methods, you might be in a better position to formulate a narrower, more focused question -- or if you're lucky, maybe you'll find a solution you're happy with.

---
Tags: algorithms, graphs
---


# Question
Title: Differences between Fuzzy C-Means and EM
When clustering a set of data points, what exactly are the differences between Fuzzy C-Means (aka Soft K-Means) and Expectation Maximization?

In slide 30 and 32 of this lecture I found, it says that Soft K-Means is a special case of EM in Soft K-Means only the means are re-estimated and not the covariance matrix, why's that and what are the advantages / disadvantages? How does covariance matrix affect the outcomes of EM?

Another question about these two algorithms: When they converge, all the data points will be hard-assigned to a particular cluster if the probability of it being in the said cluster is highest, right?

# Answer
> 4 votes
The difference between the two schemes is the model of the clusters. Fuzzy C-means and K-means model their clusters as circles (spheres in n-dimensional space), EM-clustering models the clusters as probability density functions (PDFs). In Euclidean space, the latter can have elliptical shapes (using Gaussian PDFs), determined by their covariance matrices.

Thus the difference is that the assignment criterion for K-means is the distance to a centroid whereas the criterion for the EM-algorithm is the probability of a data point given the PDF of the cluster center.

The cluster centers in K-means are hard-assigned, in Fuzzy C-means they are not; but it is rather simple to get a hard decision by, as you stated, taking the cluster with the highest probability/smallest distance for a given data point.

---
Tags: algorithms, terminology, algorithm-analysis, machine-learning, statistics
---


# Question
Title: Designing a DFA that accepts strings such that nth character from last satisfies condition
*This is a homework question, so I am only looking for hints.*

I got a question in an assignment which states :

> Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}

I have been at this for a few hours now, and I think that designing such a DFA is not possible. However, I am not sure how to move forward in this direction to write up a somewhat formal proof.

So, what should I try to do to prove or disprove my hypothesis?

# Answer
> 6 votes
I first made the NFA and then converted it to a DFA. I ended up with a total of 16 states. I thought that I had probably done something wrong as I ended up with a very large number of states, so I then followed what J.-E. Pin suggested.

I first created a NFA that checks for the last character satisfying a condition and converted it to a DFA. I then repeated this for the second last and third last characters.

What I noticed was that, the number of states in the resulting DFA was $2^n$, where $n$ is the number of states in the equivalent NFA (excluding the initial state) or the position of the character to be checked from the end.

So, if I understand this correctly, the DFA is checking all the possible strings on the input alphabet for the last $n$ characters.

---

So, to answer my own questions :

> I have been at this for a few hours now, and I think that designing such a DFA is not possible.

It is.

> So, what should I try to do to prove or disprove my hypothesis?

Make a NFA and convert it to a DFA.

# Answer
> 7 votes
Hint: Your language can be described by the regular expression $\\{0,1\\}^\*1\\{0,1\\}^3$.

Another hint: Your DFA can remember the last $4$ characters (and maintain that information). You will also need states to handle the case in which less than $4$ characters have been seen so far.

# Answer
> 6 votes
Another hint: Try first to solve the same problem for the first character from the end, then the second character from the end. It is easier and you may get some intuition from there.

# Answer
> 3 votes
As mentioned before, you don't need a NFA, you can quite easily design a DFA as follows. The DFA is the tuple $(Q,I,F,\delta)$ with :

* $Q = \\{0,1,\*\\}^4$ : a state "remember" the 4 last character read, the $\*$ is for cases with less than 4 characters read.
* $I = (\*,\*,\*,\*)$
* $F = \\{ (a,b,c,d) : a = 1 \\}$
* $\delta((a,b,c,d), e) = (b,c,d,e)$

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


title: Comparing sets of vectors

text:
# Question
Title: Comparing sets of vectors
If $u,v \in \mathbb{R}^d$ are two $d$-dimensional vectors, say that $u\le v$ if $u\_i \le v\_i$ for all $i=1,\dots,d$. In other words, comparisons on vectors will be pointwise.

Let $S,T$ be two subsets of $\mathbb{N}^d$ of size $m$. Is there an efficient way to test whether there exists $s\in S, t \in T$ such that $s\le t$? The naive algorithm does $m^2$ comparisons between vectors; is there a more efficient algorithm?

If $d=1$, this is very easy: we simply find the smallest element in $S$ and the largest element in $T$, which can be done with $O(m)$ comparisons. But already when $d=2$, it seems much harder. Any ideas?

# Answer
> 2 votes
In the case $d=2$, it is possible in $O(n \log n)$ time. First, sort the input elements on their first component. Then, use a recursive divide&conquer strategy: if a pair of comparable elements exist, then either:

1. Both elements are contained in the first half of the list
2. Both elements are contained in the second half of the list
3. A pair can be formed by taking on element from the first half and one from the second half

Cases 1 and 2 can be solved by recursion. Case 3 can be solved by finding the element from the first half with the lowest second component and finding the element with the highest second component from the right list.

It is possible to implement the divide&conquer strategy in $O(n)$ time so the time complexity is dominated by presorting the list, taking $O(n \log n)$ time.

When going to $d=3$, a similar strategy might be possible, but the third case is harder: given two sets of 2-dimensional vectors $A,B$ it requires finding $a\in A,b\in B$ such that $a\leq b$.

Edit: the following paper may be relevant, it computes for each vector how many vectors are ranked lower in less than quadratic time. http://www.cs.uiuc.edu/class/fa05/cs473ug/hw/p214-bentley.pdf

---
Tags: algorithms, data-structures, computational-geometry, linear-algebra
---


title: DFA - Equivalence classes

text:
# Question
Title: DFA - Equivalence classes
I am preparing for my exam in formal languages and I need some help with one question from one old exam.

I know that the number of equivalence classes of some regular language L, is the number of states of the minimal DFA for that language.

But how do I give a DFA for one of the equivalence classes ?

Thanks in advance

# Answer
An elaborate hint: recall that the proof of the Myhill-Nerode theorem works (in one direction) by constructing a DFA for a language, given its equivalence classes.

In the constructed DFA (i.e the minimal DFA), each state corresponds to an equivalence class. We then set the accepting states to be those that correspond to equivalence classes that are contained in the language.

Now, suppose you create the DFA for the equivalence classes of $L$, without knowing in advance which equivalence classes are in L, and which aren't. If you choose one particular class, and set the state that corresponds to it to be accepting, then the language of the DFA is exactly that equivalence class, which is what you wanted.

Indeed, the property of the minimal DFA is that for every two words $w,w'$, the runs of the DFA on $w$ and on $w'$ end in the same state iff $w\equiv\_L w'$.

Observe that you may end up with a DFA that is not minimal for the equivalence class.
> 3 votes

# Answer
The first thing you have to do is to minimize the given DFA -- or verify that it is already minimal, it happens sometimes. I am sure you have seen this algorithm in your course. This first step will give you the minimal automaton of L, which as Shaull reminded you, can be formally defined as follows. Denote by $\[u\]$ the $\equiv\_L$-class of a word $u$. Then the minimal automaton of $L$ is $\mathcal{A}\_L = (Q, \Sigma, \cdot, \[\varepsilon\], F)$ where $Q = \\{\ \[u\] \mid u \in \Sigma^\*\ \\}$, $F = \\{\ \[u\] \mid u \in L\ \\}$ and for each letter $a \in \Sigma$, $\[u\] \cdot a = \[ua\]$.

Now a hint for your question. What is the language accepted by $\mathcal{A}\_u = (Q, \Sigma, \cdot, \[\varepsilon\], \\{\[u\]\\})$, obtained from $\mathcal{A}\_L$ by taking only $\[u\]$ as final state?
> 3 votes

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


title: Classification of 2d arrays of outlines

text:
# Question
Title: Classification of 2d arrays of outlines
I am not experienced in machine learning but I have been looking at the Python toolklit `scikit-learn`. I have thousands of mammograms and I have written an algorithm to find the outline of the images. I have some cases where the outline of the mammogram is not correct. I would like to be able to take these thousands of outlines of mammograms that are arrays (of different lengths) of the x and y coordinates of the edge and to classify them. This would allow me to find the outliers and also possibly allow me to categorise the images. Does a clustering algorithm exists that would allow me to do this?

Edit 1:

Expected outline

Unwanted outline

# Answer
> 3 votes
It's hard for me to tell, but it sounds like you want to automatically detect the mammograms where the outline is incorrect. I'm assuming the desired outline is the perimeter of some convex region in the image.

I'm not sure whether clustering is going to be the ideal approach here. The first approach that comes to mind for me is something like this: we might want to build a classifier $C$ that accepts an image $I$ and a point $(x,y)$ as input and outputs either 0 or 1 according to whether $(x,y)$ is considered inside the region. As features, you might include at least the following:

* the grayscale intensity of $I(x,y)$, i.e., the darkness of the pixel at location $(x,y)$ in $I$.
* the grayscale intensity of the neighborhood of $(x,y)$ in $I$. This could be computed as the intensity of $I'(x,y)$, where $I'$ is the result of applying a Gaussian blur to $I$.
* for each line $\ell$ that's part of the outline you were given for $I$, the value of $f(\ell,(x,y))$, where you define $f(\ell,(x,y))$ to be $1$ or $0$ depending on which side of $\ell$ the point $(x,y)$ is on. For uniformity, you might choose a common orientation where one side of $\ell$ is towards the "inside" of the convex region given by the outline, and then let $f(\ell,(x,y))=1$ if $(x,y)$ is on that side of $\ell$ and let it be $0$ if $(x,y)$ is on the opposite side.
* for each line $\ell'$ that's part of the edges you detected by applying an edge detector to $I$, the value of $f(\ell,(x,y))$.

Given these features, or some other suitable features of your choice, you might try to build a classifier $C$ by training on thousands of mammograms where you have ground truth (where you know what the correct outline is); for each such mammogram image $I$, you might pick a few hundred points $(x,y)$ at random, and then train on the resulting hundreds of thousands of inputs to $C$. Since you know ground truth, you'll know what the desired/correct value for $C(I,(x,y))$ is, so you can apply supervised learning to try to infer a classifier $C$.

Once you've built a classifier $C$, you might then apply it to every new mammogram in your test set to try to infer the correct outline.

I don't know whether this will be effective in practice, nor whether it solves the problem you want to solve, but this is the first thing that springs to mind for me.

---
Tags: machine-learning, data-mining
---


# Question
Title: Difference between free and global variables
Is there any difference between free variable and global variable? Or they are just synonyms? In which situations I should use one or another?

# Answer
> 9 votes
They don't play in the same category.

The notion of *free variable* is relative to a scope. If a variable is present in a term (i.e. a subprogram) and its scope is larger than this term, then the variable is said to be *free* in that term.

A *global variable* is one whose scope is the whole program, or the whole file, or the whole module, or whatever scope is called “global” in the programming language you're considering.

# Answer
> 4 votes
According to Wikipedia, Free variables and bound variables,

> The term *free variable* refers to variables used in a function that are not local variables nor parameters of that function. The term *non-local variable* is often a synonym in this context.

Now Wikipedia, Non-local variable states:

> In programming language theory, a *non-local variable* is a variable that is not defined in the local scope. While the term can refer to *global* variables, it is primarily used in the context of nested and anonymous functions where some variables can be neither in the local nor the global scope.

The last quote is from Wikipedia, Global variable:

> In computer programming, a *global* variable is a variable that is accessible in every scope (unless shadowed).

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


# Question
Title: Is the DPLL algorithm complexity in terms of # of clauses or # of variables?
I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?

# Answer
In the papers I've read the time complexity of DPLL is expressed in terms of the number of variables in the CNF formula. Using the number of clauses is inappropriate in general because it is known that random k-SAT instances go through an easy-hard-easy transition if you fix the number of variables and increase the number of clauses. The solution space goes from underconstrained to overconstrained as the number of clauses increases with the hard instances clustering between those extremes.
> 4 votes

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


title: Tag system variant

text:
# Question
Title: Tag system variant
Is there an "official" name for this slight variant of the well known Tag System model of computation, and/or has it been used somewhere?

* a finite alphabet of symbols $\Sigma$
* a halt symbol $H$
* an ordered set of production rules: $$P\_i: \alpha\_i \rightarrow \beta\_i, \quad \alpha\_i \in \Sigma^+, \beta\_i \in \Sigma^\* \cup \\{H\\}$$
* the input $w$ is a string in $\Sigma^+$

The computation is:

1. find the first production rule $P\_i$ for which $w = \alpha\_i v$;
2. replace $w = \alpha\_i v$ with $v\beta\_i$ (i.e. delete the prefix $\alpha\_i$ and append $\beta\_i$)
3. halt when no production is found or $\beta\_i = H$

This model differs from a tag system because 1) $\alpha\_i$ is a string and not a single symbol, 2) the number of characters deleted from the prefix is not fixed.

It can easily simulate a $m$-tag system in "real-time" (for every rule $x \rightarrow P(x)$ of the m-tag system add production rules $xv \rightarrow P(x)$, $v \in |\Sigma|^{m-1}$) and therefore it can efficiently simulate a Turing machine.

# Answer
> 2 votes
That's a Post canonical system in normal form, tweaked slightly to incorporate a halt symbol, and to require application of only the first applicable production rule.

---
Tags: reference-request, computation-models
---


# Question
Title: How good are current AI researchers at simulating complex, first-person emotional states?
I just read that IBM's Watson would have a hard time answering questions like "tell me about your first kiss." If you asked a modern, state-of-the-art chatbot questions like "tell me about a song that means a lot to you and why" or "tell me about a time when you felt vulnerable" would the chatbot be able to answer in ways that would fool non-experts into thinking that it was human? Are questions like this good candidates for the Turing test?

I am not asking a philosophical question about if it is POSSIBLE to generate an AI that could represent a complex internal emotional state. I am asking: given the state-of-the-art research in 2013: how close are current researchers to generating AI that could pass the Turing test?

# Answer
> 1 votes
Great Question! One area to look into is Cognitive Architectures. These are computer programs that solve AI problems by modeling how humans think and feel (emotion). Here is a brief overview.

Prior to the mid-1980s the study of AI was concerned with creating general intelligent systems modeled after flexible human thinking (Fahlman, 2012). Researchers in AI used findings in cognitive psychology to guide their work.

Currently, there has been a shift away from this approach. The current trend in AI research is towards solving problems with “knowledge-lean” statistical methods which are data intensive and learn less efficiently than humans. (Langley, 2012). Thus, the AI field has shifted away from human-like models and toward "ideal" models.

However, a few AI researches still focus on creating intelligent systems modeled after the way humans think. These researches work with Cognitive Architectures--Computer programs modeled after humans. The Office of Navel Research's Human Computer Interaction lab is actively working to create intelligent agents that can interact with humans.

I believe that the study of Cognitive Architectures is an interesting area of research for investigating how to create human-like systems.

Fahlman, S. E. (2012). Beyone Idiot-Savant AI. Advances in Cognitive Systems 1, 15-21.

Langley, P. (2012). Intelligent behavior in humans and machines. Advances in Cognitive Systems 2, 3-12.

Taatgen, N. A. (1999). Learning without limits. From Problem Solving towards a Unified Theory of Learning(dissertation). Groningen: Rijksuniversiteit Groningen.

http://www.onr.navy.mil/en/Science-Technology/Departments/Code-34/All-Programs/human-bioengineered-systems-341/Human-Robot-Interaction.aspx

# Answer
> 0 votes
there are several different questions here.

yes, questions/topics relating to emotional states in the chatbot or the human conversing with it are those that would tend to trip up chatbots.

a good semi-scientific benchmark for research in this area is the Loebner contest/competition. it somewhat a mix of serious research and informal gaming.

a nice article/overview on the competition was published a few yrs ago in the Atlantic, Mind vs machine.

another area where there is a combination of ongoing research, application, and innovation is the field of gaming, and "NPCs" or "non player characters". one of the more advanced/notable games from recent years with a theme of simulating emotional states of the agents in the game is the Sims written by Will Wright.

> how close are current researchers to generating AI that could pass the Turing test?

there is no definitive answer here, only opinion, conjecture, speculation, and science fiction, and some disconnected research. at heart the question asks to predict the future. the short answer is that nobody really knows how far away this milestone is or if it is even scientifically achievable (although the question of machine intelligence on the level of human intelligence is probably a scientific question, subject to study, experiment, evolutionary and/or revolutionary advances etc, rather than a philosophical one as you indicate).

---
Tags: artificial-intelligence
---


# Question
Title: Prove correctness of recursive Fibonacci algorithm, using proof by induction
I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction.

Here is my recursive version of an algorithm to compute Fibonacci numbers:

```
Fibonacci(n):
    if n = 0 then     // base case
        return 0
    elseif n = 1 then // base case
        return 1
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2)
    endif

```

How can I prove the correctness of this algorithm by induction?

# Answer
> 5 votes
(Seems like it may be a duplicate, but the "Related" questions don't seem to be too close, with the possible exception of "this one)

The proof is by induction on $n$. Consider the cases $n = 0$ and $n = 1$. In these cases, the algorithm presented returns $0$ and $1$, which may as well be the 0th and 1st Fibonacci numbers (assuming a reasonable definition of Fibonacci numbers for which these values are correct).

Now, assume that the algorithm returns the correct Fibonacci number for all $n$ (i.e., the nth Fibonacci number) for all $n \leq k$ where $k \geq 1$.

We must show that the algorithm returns the correct value for $k+1$, i.e., the (k+1)th Fibonacci number. By the induction hypothesis, $k \geq 1$, so we are in the `else` case. We return `Fibonacci(k) + Fibonacci(k-1)` in this case. By the induction hypothesis, we know that `Fibonacci(k)` will evaluate to the kth Fibonacci number, and `Fibonacci(k-1)` will evaluate to the (k-1)th Fibonacci number. By definition, the (k+1)th Fibonacci number equals the sum of the kth and (k-1)th Fibonacci numbers, so we have that the algorithm returns the (k+1)th Fibonacci number on input $k+1$.

The proof of the claim follows by induction on $n$.

# Answer
> 5 votes
**Claim:** The algorithm, *Fibonacci(n)* is correct

(Proof by Strong Induction)

**Base Case:** for inputs $0$ and $1$, the algorithm returns $0$ and $1$ respectively. So this is Correct.

**Induction Hypothesis:** *Fibonacci(k)* is correct **for all values of $k \leq n$**, where $n,k\in \mathbb{N}$

**Inductive Step:**

1. let *Fibonacci(k)* be true **for all values until $n$**
2. From IH, we know *Fibonacci(k)* correctly computes $F\_k$ and *Fibonacci(k-1)* correctly computes $F\_{k-1}$
3. So, $$ \begin{align\*} \text{Fibonacci(k+1)} &= \text{Fibonacci(k) + Fibonacci(k-1)} \\ &\text{(by definition of the Fibonacci function)} \\ \\ &= F\_k + F\_{k-1} & \\ \\ &= F\_{k+1} \\ &\text{(By definition of Fibonacci numbers)}\\ \end{align\*} $$
4. Thus by rules of mathematical Inducion, *Fibonacci(n)* always returns the correct result for all values of $n$.

---
Tags: algorithms, algorithm-analysis, correctness-proof, induction
---


# Question
Title: DFA drawing for binary string with substrings of minimum length 3 with at least two zeroes in each substring
In trying to gain a better understanding of finite state machines, I stumbled across this idea and have been confused as to how to approach this case in terms of a DFA.

> The set of binary strings of length at least 3 where every substring of length 3 contains at least two 0s.

So in other words, something like 100100010 should be in the language (L) for this DFA but something like 11001010 would not be in the language.

I know that you can start off by writing/drawing smaller DFAs for the substrings that are the pattern 000, 010, 100, 001, etc, but I cannot seem to get a hold of how it should look all together.

Any help in understanding this would be appreciated.

# Answer
> 3 votes
The condition that all words have length $\geqslant 3$ makes the computation of the minimal DFA much more difficult. Thus let us first consider the language $$ K = \\{ u \in A^\* \mid \text{every substring of length 3 of $u$ contains at least two $0$} \\} $$ where $A = \\{0,1\\}$. The forbidden patterns of the words of $K$ are $11$ and $101$, so that $K$ is the complement of the language $A^\*(11 + 101)A^\*$. But there is a nicer way to write $K$, using the comment of Luke Mathieson. Indeed, apart from the last two letters, every $1$ has to be followed by two $0$. This leads to the regular expression $K = (0 + 100)^\*(\varepsilon + 1 + 10)$. I let you compute the minimal DFA of $K$ which has only three states (plus a sink state if you want a complete DFA).

Now $L = A^3A^\* \cap K$ and you can use standard algorithms to get its minimal DFA (9 states, 10 if you count the sink state).

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


# Question
Title: Approximability of the edge-disjoint shortest paths problem
In the *edge-disjoint paths problem* (EDP), we are given a (possibly directed) graph $G=(V,E)$, and a set of distinct source-sink pairs $\\{ (s\_i,t\_i) \mid 1 \leq i \leq k \\}$, and we want to maximize the number of pairs that can be simultaneously connected in an edge-disjoint manner. When we add the constraint that the paths need to be *shortest paths*, we get the *edge-disjoint shortest paths* (EDSP) problem.

According to \[1\], the EDSP problem is hard for a graph with unit edge lengths, even when the graph is planar. Furthermore, it claims this is so for both directed and undirected graphs.

> What is known about the approximability of the EDSP problem?

I'm especially interested in results for undirected graphs. In \[2\], the authors seem to only consider variants of the EDP problem, but not the EDSP problem. Further following the references, it seems like the EDP problem has been studied extensively.

---

\[1\] Eilam-Tzoreff, Tali. "The disjoint shortest paths problem." Discrete applied mathematics 85.2 (1998): 113-138.

\[2\] Guruswami, Venkatesan, et al. "Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems." Journal of Computer and System Sciences 67.3 (2003): 473-496.

# Answer
> 1 votes
**Below, we will assume there is exactly one shortest path between every pair of vertices.** The following will also work for the case where $O(\log n)$ pairs of vertices have $O(1)$ shortest paths between them.

For each pair $\\{s\_i , t\_i\\}$ let the shortest path be $P\_i$, $\forall i \in \\{0,1\ldots k\\}$. The shortest path can be found in polynomial time. Let us number the edges $e\_1, e\_2, \ldots e\_q$. Let the maximum number of pairs $\\{s\_i , t\_i\\}$ for which there exist disjoint-shortest paths be $\text{OPT}$.

Now, we reduce this problem to an optimization problem.

Define a matrix $A\_{k\times q}$ such that $A\_{ij} = 1 \text{ if } e\_j \in P\_i$.

$$ \text{OPT} = \max \sum\_{i=1}^k x\_i \quad \\ \text{s.t } Ax \leq \mathbf{1}\_{n\times 1} \\ x \in \\{0,1\\} $$

Let the optimal fractional solution for the above problem be $\text{OPT}\_{\text{LP}}$ and $\text{OPT}\_{\text{LP}} \geq \text{OPT}$. The above LP has an integrality gap of $O(\log k)$. Therefore, $O(\log k) \cdot \text{OPT}\_{\text{IP}} \geq \text{OPT}\_{\text{LP}}$. Thus $ O(\log k) \cdot \text{OPT}\_{\text{IP}} \geq \text{OPT}$. Hence we obtain a $O(\log k)$ approximation algorithm.

The proof for the integrality gap result can be found in **Vazirani's "Approximation Algorithms", chapter 20. Multicut in General Graphs.**

---
Tags: algorithms, reference-request, shortest-path, approximation
---


# Question
Title: Is changing or appending data an idempotent operation?
As far as I know idempotent operation is a operation that can be applied many times with the same effect. Also I learnt recently that updating a tuple in a database is also idempotent. I thought that an idempotent operation was like a read-only stateless call (thanks to HTTP world with its famous `GET` request example). So, is changing data in a file (or database) idempotent? Is appending (extending) data in file/database idempotent? Why?

# Answer
An operation $O$ is idempotent if $O(O(x)) = O(x)$. For example, if you update record $R$ to value $T$ and then again update record $R$ to value $T$, then it's the same as if you updated only once. But if you append $T$ to record $R$ twice, it's not the same as appending only once.
> 4 votes

# Answer
As mentioned, an operation $O$ is idempotent if $O(O(x))=O(x)$ for any $x$. The important thing to realize is **what is the domain**, what are the possible values of $x$, and **what are the things we're comparing with the $=$ sign**.

In mathematics, there is usually no mutability, we're comparing elements constructed over some mathematical structure.

In (imperative) programming, what changes is the *state* of a program. So our domain is the set of all possible states of a program. You can thing of such a state a snapshot of the content of all the program's memory, CPU registers etc. In this context, an operation is something that changes a state of the program into another. By $O(x)$ we mean *the state of the program that we get by running $O$ from state $x$*.

Now we see what it means that an operation is idempotent. It is a piece of code that changes program's state in such a way that if we run the operation twice, we get the same state as if we run it only once. Most typical idempotent operation is setting a variable to some given value (or updating a database record etc.). Calling

```
// call O twice
var := value;
var := value;

```

is the same as

```
// call O once
var := value;

```

because the second time we call the operation, the state doesn't change (no matter what the original state was) - we know the value is already there.
> 2 votes

---
Tags: terminology, programming-languages, functional-programming
---


# Question
Title: Ideal number of participants for evaluation of development approach / software architecture
For my thesis, I have created a development approach (consisting of schemes, an application template and prototype code) that should make it easier to develop and adapt applications for a specific platform.

I have conducted interviews with developers of that platform to evaluate my approach. There have been 5 interviewees so far and the feedback that I got from them is sufficient for my scope, I would say.

However, in my thesis I would like to justify my decision that 5 evaluators are enough. Is there any scientific research or paper that suggests a certain number of evaluators for such a rather theoretical approach?

I know Nielsen's work about heuristic usability evaluation which says that with 5 participants, you discover around 75% of all problems in *software usability / UI testing*.

But as I said, my approach is no specific software product that has to be evaluated, but only the model itself, which is why I'm looking for research in that area.

# Answer
> 5 votes
"Is there any scientific research or paper that suggests a certain number of evaluators for such a rather theoretical approach?"

There is a statistical method to calculate the correct sample size for an experiment.
This method is called a "power analysis" \[1\]. It calculates the minimum sample size needed to verify that an experiment's results are statistically significant. This approach assumes that you have at least two groups. A control group and an experimental group (i.e. control group uses the platform without your modifications, experimental group uses the platform with your modifications).

Thus, while there is a scientific process to calculate the correct sample size this approach is probably overkill for your study. Nielsen \[2\] states that heuristic evaluation is just a "cheap and quick" method for easy evaluation. As such, I believe you can justify a sample size of 5 by citing Nielsen. However, if you do want to standardize your evaluation process and use a statistical approach I encourage you to look into power analysis.

You may be interested in this online tool for calculating power.

---

1. http://en.wikipedia.org/wiki/Statistical\_power
2. http://www.nngroup.com/topic/heuristic-evaluation/

---
Tags: reference-request, software-engineering, empirical-research
---


title: How to decribe an action with STRIPS?

text:
# Question
Title: How to decribe an action with STRIPS?
The state space is decribed with 3 boolean variables $p,q$ and $r$ (so we have 8 states total). We have an action, let's say $a$. Action $a$ can be executed when $p=\text{False}$ and $q=\text{True}$ and the result is $p=\text{True}$, $q=\text{False}$ and $r=\text{False}$

How can we describe this action with STRIPS? My problem is this: since it isn't allowed on STRIPS to have negative literals, how can I describe it? For example, $\text{precondition}(a) = \\{ \neg p,q \\}$.

# Answer
An instance of propositional STRIPS planning is a quadruple $\langle P,O,I,G \rangle$

* $P$ is the set of atomic ground formulas;
* $O$ is the set of *operators* (actions); an operator $a \in O$ has the form $Pre \Rightarrow Post$, where $Pre$ is a satisfiable conjuction of positive ($a^+$) and negative *preconditions* ($a^-$) of the operator; $Post$ is a satisfiable conjunction of positive ($a\_+$) and negative ($a\_-$) *postconditions* of the operator ($a\_+$ is called the *add list*, $a\_-$ is called the *delete list*);
* $I \subseteq P$ is the *initial state*;
* $G = \langle G\_+, G\_- \rangle$, called the *goals*, is a satisfiable conjunction of positive and negative conjunctions;
* the state $S$ is a subset of $P$.

The result of applying operator (action) $a$ on state $S$ is:

* $(S \cup a\_+) \setminus a\_-\quad$ if $a^+ \subseteq S$ and $S \cap a^- = \emptyset$
* $S$ otherwise

In your example simply set: $$a^+ = \\{q\\}, \quad a^- = \\{p\\}$$ $$a\_+ = \\{p\\}, \quad a\_- = \\{q,r\\}$$

For a formal definition and a nice computational complexity characterizations of STRIPS with various constraints on the preconditions/postconditions see: The Computational Complexity of Propositional STRIPS Planning (1994), by Tom Bylander.
> 3 votes

---
Tags: artificial-intelligence
---


# Question
Title: Example of existence proof in dependent typing?
I understand that $\Pi$ types are generalizations of functions and can be interpreted similar to $\forall$ in logic. I also know that $\Sigma$ types are generalizations of tuples and can be interpreted similar to $\exists$ in logic. But whereas I find it easy to imagine $\Pi$ type examples by thinking in Haskell, I am having a hard time thinking of good examples of $\Sigma$ types. Is there a particular "canonical" $\Sigma$ type that gives a good indication of how it can be interpreted as existence when the type is thought of as a proof?

# Answer
$\Sigma$-types in Haskell appear in various places. Because Haskell is not dependently typed, they often reduce to the non-dependent version of $\Sigma$-types, which are just Cartesian products. So whenever you see an ordered pair, or a record, that is a simple case of a $\Sigma$-type.

At the level of a modules there can be dependencies and so we get actual $\Sigma$-types. For instance, a module which defines a type $T$ and then a value $f$ of type $T \to T$ has the kind $\Sigma\_{T : \mathrm{Type}} (T \to T)$. (The module should *hide* the definition of $T$ in order for this to actually be the case.) Observe that this is a "large" dependent sum because it ranges over "all Haskell types $T$" so I refer to it as a "kind". In fact, the theory of modules is based on the observation that hiding bits of a program behind a layer of abstraction is precisely the same as forming a dependent sum.

Haskell has existential types. These are like depenent sums of the kind I mentioned above. Namely, an existential type

```
data Calf = forall t . Bull t => Cow(t)

```

is just a confusing way of writing $$\mathtt{Calf} = \textstyle \sum\_{t : \mathtt{Bull}} Cow(t).$$ Strangely, the "forall" keywords indicates the fact that there *exists* a type $t$ of class $\mathtt{Bull}$ such that $F(t)$. Perhaps some Haskellites can explain the logic behind the notation to me.
> 5 votes

# Answer
Well, how about the proof that every number is zero or has a predecessor? It turns into a function which takes as input an integer, and as output returns either a proof that it is zero, or the predecessor, and a proof that it is indeed the predecessor.

In Coq:

```
Fixpoint pred (n : nat): {n = 0} + {exists m, S m = n} :=
match n with
| 0 => left (eq_refl 0)
| S m => right (ex_intro _ m (eq_refl (S m)))
end.

Eval compute in (pred 12).
> right (ex_intro (fun m : nat => S m = 12) 11 eq_refl)

```

In Coq, $\\{\\\_\\}+\\{\\\_\\}$ is the `Either` type of Haskell, and `exists` is just $\Sigma$. You can see that the function matches on the integer, and returns the proof of $0 = 0$ in the first branch, and the pair $(m, p)$ where $p$ is a proof of $m+1 = n$ in the other branch (`ex_intro` is just a special pair constructor for `exists`. The predecessor of 12 is correctly computed to be 11 in the following call.
> 4 votes

---
Tags: type-theory, dependent-types
---


# Question
Title: Time complexity of a triple nested for loop for ThreeSum problem
I am new to Algorithms and am currently confused about the running time of the ThreeSum program. If we look at ThreeSum's count function:

```
public static int count(int[] a) {
  int N     = a.length;
  int count = 0;

  for (int i = 0; i < N; i++) <-- A
    for (int j = i + 1; j < N; j++) <-- B
      for (int k = j + 1; k < N; k++) <-- C
        // check each triple
        if (a[i] + a[j] + a[k] == 0)
          count++;
  // loop i = 0; j = i+1; k = j+1 so that we get each triple just once

  return count;
  }

```

I understand that `int N = a.length` means that its frequency is 1 as the statement only runs once and that `count++`'s frequency is x as it depends on input however with nested for loops. I understand that say `A`'s frequency is $N$ (as it is repeated `N` times) but then I get a bit confused.

It seems to be that for each nested loop, the other loop has to run which makes sense so `B`'s frequency is $N^2$ but then in the book it says that B's frequency is $N^2/2$ and C is $N^3/6$ (where I would have assumed $N^2$ and $N^3$) where is the "$/2$" and "$/6$" coming from?

Any help is appreciated, thanks. Sorry for the lengthy question!

# Answer
The second loop runs only on $j \> i$. Only (roughly) half of the pairs $(i,j)$ between $0$ and $N-1$ satisfy $j \> i$. Similarly, the third loop runs only on $k \> j \> i$, and only (roughly) $1/3!$ of the triples $(i,j,k)$ satisfy that condition.

If you want to be more accurate, $B$ runs this many times $$ \sum\_{i=0}^{N-1} (N-i-1) = \sum\_{i=0}^{N-1} i = \frac{i(i-1)}{2}. $$ I'll leave you the calculation for $C$.
> 2 votes

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


# Question
Title: Difficulty in understanding an approach to SPOJ $d$-query problem
I was trying to solve this problem on SPOJ:

> Given a sequence of $n$ numbers $a\_1, a\_2, \ldots, a\_n$ and a number of $d$-queries. A $d$-query is a pair $(i, j)$, $(1 \leq i \leq j \leq n)$. For each $d$-query $(i, j)$, you have to return the number of distinct elements in the subsequence $a\_i, a\_{i+1}, \ldots, a\_j$.

Specifically, the input to the problem is as follows.

* Line 1: $n$, where $1 \leq n \leq 30000$
* Line 2: $n$ numbers $a\_1, a\_2, \ldots, a\_n$, where $1 \leq a\_i \leq 10^6$
* Line 3: $q$, the number of $d$-queries, where $1 \leq q \leq 200000$
* Finally, $q$ lines, where each line contains 2 numbers $i, j$ representing a $d$-query, where $1 \leq i \leq j \leq n$.

But after a few hours of trying to solve it, I googled for a possible hint. I found one approach described here by user irancoldfusion:

> First I thought a good O(n ^ 2 + q log q) would pass, but it didn't run in time. Then, I thought of the idea below which I haven't implemented yet:
>
> The result of a query \[a, b\] is number of integers whose last occurrence in \[1, b\] is \>= a.
>
> Let's have two kinds of events: QueryEvent and NumberEvent. First we read whole input and sort all events, the key for QueryEvents are their end (i.e. b for query \[a, b\]), and for NumberEvents the key is their position in array.
>
> We also have a segment tree which answers the queries of kind: how many elements are at position range \[x, y\]. Initially the tree is empty.
>
> Then we process events in order: \+ When we meet a NumberEvent: 1. If number has occurred before at position p, we remove p from segment tree. 2. We add position of number to the segment tree. \+ When we meet a QueryEvent: \- Query the segment tree, and find the answer.
>
> The overall time complexity of algorithm is O( (n + q) log n + (n + q) log (n + q) )

But I am not able to understand it properly. Can anybody help me in understanding the approach. I want to understand how are the positions inserted and deleted from the tree. That is, what does the segment tree hold, say for an interval.

# Answer
> 2 votes
(This answer is no longer very interesting, now that the question has been corrected to clarify that $1 \le a\_i \le 10^6$ instead of $1 \le a\_i \le 106$.)

This can be solved in $10^6(n+q)$ operations.

First, build a table $T\[\cdot,\cdot\]$, where $T\[j,x\]$ is the index of the last occurrence of the number $x$ among $a\_1,a\_2,\dots,a\_j$. In other words,

$$T\[j,x\] = \max \\{i : a\_i=x \wedge 1\le i\le j\\}.$$

This table can be built in $10^6n$ steps.

Next, you should be able to see how to answer a query $(i,j)$ quickly, by doing some lookups into the $T$ table. I'll let you work out the details so you can have the fun of solving the problem.

---
Tags: algorithms
---


title: How does facial recognition work?

text:
# Question
Title: How does facial recognition work?
I'm interested in learning about how facial recognition works. I'm especially interested in the algorithms or approach that is used. What are the leading methods for facial recognition? Is there a good overview or source to learn about a few of the most widely used algorithms for facial recognition? What would be the best handful of research papers to read first?

# Answer
The simplest Face Recognition 101 would be run a PCA on the data, followed by a K-nearest neighbor classification.

but now there are more advanced techniques that you pick along, it might be using "better" classifiers like SVMs or Neural Networks or apply Bayesian learning, but then, as you move up the knowledge tree, you will realize you need your data itself to be more robust.. so you will then want to learn about about SIFT and other techniques.

One of the nice places you can start looking for papers and algorithms is face-reg

Have fun learning :)
> 6 votes

---
Tags: reference-request, computer-vision, pattern-recognition, facial-recognition
---


# Question
Title: Is there a name for the class of operations containing prefix, suffix, etc?
I'm currently doing some research on operations on languages, specifically prefix, suffix, infix and outfix.

For example, for a language $L$, the prefix set of $L$ is:

$pref(L) = \\{x \mid xy \in L, y \in \Sigma^\* \\}$

Infix is

$inf(L) = \\{w \mid xwy \in L, x,y \in \Sigma^\* \\}$

and outfix is:

$outf(L) = \\{xy \mid xwy \in L, w \in \Sigma^\* \\}$

I'm wondering, is there a name for the "class" of operations which contains all of these? I think I might have seen "bitfix" used in a paper somewhere, but it seems to mean something different.

# Answer
In natural languages, at least, the term is affix.
> 2 votes

# Answer
The closure of those operations (in fact, just the closure of "outfix") gives you arbitrary **subsequences**.
> 1 votes

# Answer
The prefix and suffix operations can be expressed in terms of right- resp. left-quotients:

$\qquad \operatorname{pref(L)} = L / \Sigma^\*$ and

$\qquad \operatorname{suff(L)} = L \backslash \Sigma^\*$.

Similarly, one could define "inner" and "outer" quotients like this:

$\qquad L\_1 \mathbin{\bot} L\_2 = \\{ w \mid xwy \in L\_1, xy \in L\_2 \\}$ and

$\qquad L\_1 \mathbin{\top} L\_2 = \\{ xy \mid xwy \in L\_1, w \in L\_2 \\}$.

Your infix and outfix reduce to these notions by taking $L\_2 = \Sigma^\*$.

I did make these up right now, but I think calling this class of operations *quotients* would be resonable and consistent with generalisations of prefix and suffix.
> 1 votes

# Answer
Sorry, do not recall a name for this common concept.

But we can come up with ideas nevertheless. I would call the notion "regular selections". Prefix selects letters from a string according to $1^\*0^\*$, infix according to $0^\*1^\*0^\*$. If you like that, then your research should also include the selection of even positions $(01)^\* + (01)^\*0$.
> 0 votes

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


# Question
Title: How do I find if a programming language is infinite or finite?
I know that in an infinite language there are infinite number of strings. I want to know what type of the languages are C, C++ and JAVA? I can have infinite number of variables in all these languages, so I think all these languages are infinite. Please correct me if I am wrong.

# Answer
An infinite number of potential identifiers results in an infinite language, but this is a "boring" feature with this consequence, because you can do without. We know that two variables are sufficient to compute any Turing computable function, so this is not the crucial part; I'll assume we use only finitely many variables.

Even then, ignoring real-world constraints such as finite memory, programming languages are -- of course -- infinite languages. Consider the following class of programs:

```
def m(x) {
  x++
  x++
  ...
  x++
  return x
}

```

It is clear that you can have as many statements as you want (never mind that, depending on the semantics, it might be that only finitely many of them run without error).

Why do I say "of course"? Well, usually programming languages are supposed to be Turing complete (again, assuming infinite memory). There are infinitely many functions that are Turing computable -- consider only $f\_i(x) = i$ for $i \in \mathbb{N}$ -- so we *must* have infinitely many programs.

It is even so that typical programming languages have infinitely many programs for *any single (computable) function*! Consider, for instance, $f\_1$ and all implementations of the form

```
def f1(x) {
  x++
  x++
  ...
  x++
  return 1
}

```

If you think about it, you can do stuff like that -- inserting "meaningless" statements -- in any program written in any language.
> 2 votes

# Answer
A language is infinite if and only if it contains arbitrarily long strings. In other word, a language is finite if and only if there is an upper bound on the length of its strings. (Prove it; it's easy. The key assumption is that the language is over a finite alphabet.)

There are several possible definitions for what a language like C means in terms of sets of strings. A reasonable definition would be to consider the set of translation units (that's the C name for an individual source file) that are syntactically correct, but the specification of the C language isn't worded in this way — the closest formal way of stating this is that a C program would be one whose behavior during phase 7 of the translation is defined. Even that is ambiguous since C implementations are allowed to reject programs at compilation time if they provably have no correct execution on that particular implementation. Another possible definition is the set of programs whose semantics is well-defined on all implementations (no undefined behavior).

Continuing the example of C, the standard allows implementations to have limits on many things, including the significant length of an identifier (C99 implementations are allowed to ignore all characters in an identifier after the 63rd), the line length (C99 implementations are allowed to reject source lines longer than 4095 characters), and the length of a string literal (also at 4095 characters). However as far as I know there is no limit on the length of a translation unit, nor any limit on the number of instructions in a block. So you can put as many `x++;` lines in a function as you like. Or you can simply have as many empty lines as you like — that's enough to show that C is infinite.

Most programming languages are similarly defined with no maximum length on the source file, so they are infinite.
> 1 votes

---
Tags: formal-languages, computability
---


# Question
Title: Does a proof using the well-ordering principle need a base case?
For proofs by well-ordering principle the general template is to consider the negation of some predicate $P(n)$. Then assume the set of all elements that fulfill $\lnot P(n)$, i.e.

$\qquad N = \\{ n \mid \lnot P(n) \\}$

has a smallest element according to WOP, say $m = \min N$, and if we manage to prove that there is another element $m' \in N$ that is less than $m$ that also negates then we contradict our assumption that $m$ is the smallest element.

My question is that should we be proving some sort of a base case as well for the above mentioned template. As in proving that for some base case, $P(\mathrm{base})$ is true?

# Answer
In the Wiki page,

> In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element.

Pay attention to the word **non-empty**.

Consider the negation of P(n). Before you assume the set that satisfying P(n) is false has a smallest element m, you already assume that the set is non-empty. You prove that there is another element that is less than m. This contradicts the assumption that the set is non-empty. Thus, the set is empty which means P(n) is true.
> 4 votes

# Answer
This is not an induction proof, but a proof by contradiction.

**Goal:** Proof that $P(n)$ for all $n \in X$.

**Strategy:** Assume towards a contradiction the contrary, i.e. there is non-empty $N \subseteq X$ so that for all $n \in N$, $P(n)$ does not hold. Then, as you describe, pick $m = \min N$ -- this is not an *assumption* as such, but a *choice*¹ -- and derive that there is $m' \< m$ with $m' \in N$, which contradicts the choice of $m$. Hence, the assumption that there is such $N \neq \emptyset$ can not hold and the claim must be true.

---

1. It requires, of course, that the base set $X$ is well-ordered.
> 2 votes

# Answer
A typical example is show `gcd(a,b) = min { ma+nb > 0: integers m,n }`.

By Well-Ordering-Principle this set has a least element **x**. One check's it's the GCD.

The GCD certainly divides **x**. If it did not divide **a** or **b** we could run division algorithm and the remainder would be a smaller number in this set.

We've basically shown the Euclidean algorithm terminates at some point (using WOP), which is the GCD.

---

Invoking WOP is like the "base case" and checking that **x** satisfies your properties of interest can be compared to "induction".

---

The outline for using WOP is

* Let's prove P(n) for all n by consider the set where P(n) is **false**
* As a subset of natural numbers there is a **least positive number** m where P(m) is false
* Prove there's a **smaller** number m' \< m where P(m') is still false

Well Ordering Principle and Induction are equivalent even though they feel different.
> -1 votes

---
Tags: proof-techniques
---


# Question
Title: What is the trade off in converting a DFA into a NFA?
When a DFA is converted into an equivalent NFA, the NFA gives more convenience to many yes/no kind of problems (such as a word belong to a language or not?). I want to know in general at what price this convenience is achieved?

# Answer
A deterministic finite state automaton (DFA) is in fact a non-deterministic finite automaton (NFA) where the transition function only maps to singelton sets.

Recall that from the first principles that the transition function, $\delta$, in a DFA is defined as $$ \delta: Q\*E \rightarrow Q,$$ whereas for an NFA it is $$ \delta: Q\*E \rightarrow \mathcal{P}(Q)$$

This means that you can (intuitively) think of a DFA as a *"special type of"* NFA.
> 4 votes

# Answer
It may be difficult to get an answer you like because given a DFA it is hard to find an equivalent NFA that has fewer states. If all you know is the DFA, you are going to have to work extremely hard to get any equivalent NFA other than the DFA itself.

Suppose, however, that you do have an equivalent NFA and DFA where the NFA is smaller than the DFA. (Perhaps because you had the NFA in the first place, and used the Rabin-Scott powerset construction algorithm to find the equivalent DFA.) Given an NFA over $M$ symbols with $N\_{\mathrm{NFA}}$ states, and an equivalent DFA with $N\_{\mathrm{DFA}}$ states, and $N\_{\mathrm{NFA}} \leq N\_{\mathrm{DFA}}$, the DFA will be cheaper to simulate than the NFA.

For the DFA the current state is an integer $j \in N\_{\mathrm{DFA}}$. You keep a table with $M N\_{\mathrm{DFA}}$ entries where the $i$ + $jM$th entry in the table gives you the next-state transition from state $j$ on symbol $i$. The lookup is $O(1)$.

For the NFA the current state is a *set* $J \subseteq N\_{\mathrm{NFA}}$, and is typically represented with an $N\_{\mathrm{NFA}}$ bit vector. (A $1$ at position $j$ in the vector means that $j$ is a member of the current state.) Your state transition is much more expensive. For each element $j\_k$ in the current state set you need to look up the (possibly $N\_{\mathrm{NFA}}$ element) next state set, and then union together all the results of the lookups. Perhaps there is an algorithm for doing this faster than $O(N\_{\mathrm{NFA}}^2)$, but I don't know it off hand.

There's a memoization based optimization that is typically performed during NFA simulation (you keep a cache that maps a hash of the current state and the current symbol to its next state, so that if you get that state/symbol pair again in the future you get the next state in $O(1)$), but this doesn't change the worst case bounds.
> 4 votes

# Answer
I assume you mean converting a DFA to a smaller NFA that actually uses the nondeterminism.

If your machine uses nondeterminism, it's more difficult to simulate in on a deterministic computer. You have to keep track of all possible computation states, since your computer can't "guess" the correct nondeterministic transition like the NFA would. This basically amounts to converting your NFA back to a DFA with (exponentially) more states.
> 1 votes

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


# Question
Title: What exactly can finite-state machines not do?
I know finite-state machines can be used to solve yes/no kind of problems, such as finding whether a word is in language or not. Can somebody tell me exactly what FSM cannot do and why?

# Answer
The answer depends on what you mean by FSM.

If by FSM you mean finite automaton, then there's a lot that it can't do. As others have pointed out, you can't remember more than a constant amount of information using a finite automaton; the memory must be encoded in the state. This means you can't do things like recognize $a^nb^n$, since you'd need to remember how many $a$ symbols you've seen, which is not possible unless you have an arbitrary amount of memory. The pumping lemma for regular languages and, especially, the Myhill-Nerode theorem offer insight into the kinds of things that can and cannot be done.

If by FSM you mean any automaton formalism which is limited to using finitely many states, then Turing machines are among the most computationally capable FSM models available. Indeed, anything which is effectively computable is computable by a Turing machine, according to the Church-Turing thesis. However, there are still limitations to what a Turing machine can decide: there are problems it cannot answer, such as the halting problem.

Models which aren't limited to a finite number of states aren't particularly interesting for a few reasons, most prominent of which are the following: they are of limited practical importance since we cannot construct real computers with infinitely many configurations; any language can be recognized in such a model by mapping strings in the language to unique accepting states, and strings not in the language to unique non-accepting states.
> 9 votes

# Answer
Finite state machines can recognize regular languages. The canonical example for a language that can't be recognized by such an automaton is $L=\\{a^nb^n\\,|\\, n\in \mathbb{N}\\}$.

Depending on your exact definition of finite state machine, the model also includes things like timed automata, and Moore automata which are more powerful.
> 4 votes

# Answer
It cannot even recognize palindromes and context free languages. I think you'll like this article that gives formal proofs and talks about limitations of FSM.

Also this is a very good article on Limitations of Computing. Since you are talking about FSMs, I think the topics here will interest you too.
> 1 votes

# Answer
FSM doesn't have memory, It can't remember the things unlike Push Down Automata (i.e nothing but a FSM with Memory).Anything which require memory can't accepted by FSM.
> -1 votes

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


title: Closing shapes at non-endpoints

text:
# Question
Title: Closing shapes at non-endpoints
Consider how one would represent the following image in vector graphics:

Pretty simple, right? The entire shape can be represented by a single path element.

But suppose additionally that you want to color the heart at the top red. The path element is an open shape, so trying to fill it results in an appropriately red heart but also implementation-dependent bleeding between the spiral endpoints.

Obviously, one could just draw the heart and the spiral tails as separate elements, but then the vector graphics representation no longer mirrors how a human being would draw the same image, and makes it more difficult to manipulate as a single object. One needs a way to communicate to the computer that two particular path segments within the larger path intersect in such a manner that they close a sub-shape.

Is there a vector graphics format capable of doing this? More relevantly, how is it implemented and are there any papers on it?

# Answer
> 0 votes
If we are not given the region to fill and have to figure that out for ourselves, one simple heuristic is:

* We're probably looking for a closed, bounded region. If the region is unbounded (it connects to the edges of the frame), it's probably not the one we're looking for.

So, you could compute connected components and look for a bounded component.

In your example, this means: look just at the white pixels, and consider two white pixels to be connected to each other if they are adjacent. Now compute the connected components of the resulting set. In your picture, there are 7 connected components, but only one of them is bounded (it does not intersect the top edge, bottom edge, right edge, or left edge of the picture). Therefore, that's probably the one that we want to fill. If you follow this heuristic, it does indeed fill the heart shape.

If there are multiple components that are all bounded (have no intersection with any of the edges), then this heuristic fails and some interaction with the user is required to determine which component the user wanted to fill. But that's probably unavoidable. Your problem statement is ambiguous and does not give us enough information to disambiguate which was desired, so it's not surprising that this might require user interaction in some cases. After all, the computer can't read our minds....

# Answer
> 1 votes
In CAD systems this is done

* On user side
    + find intersection of two curves
    + split curves by their intersection
    + make closed path to form a polygon
    + fill polygon
    + you can still group separated line into one line and operate with it as previously, change in internal logic (math core side) will be hidden from you
* On math core side
    + choose appropriate method of intersection of curves based on the type of the curves
    + do intersection either by exact intersection if lines types support this (eg straight lines) or by numerical method (usually iterative) in other cases (eg when you have splines underlying)
    + create new curves based on existent edges of lines and on the found intersection point
    + an so on

---
Tags: computational-geometry, graphics
---


# Question
Title: Finding two words of lengths that are relatively prime in a regular language?
Given a regular language $L$ over a unary alphabet $\Sigma = \\{ a \\}$.

How to decide whether there are two words $w,w' \in L$ such that the length of $w$ is relatively prime to the length of $w'$ ?

# Answer
Consider a minimal DFA for $L$. Each state in the DFA has one outgoing edge, so the DFA looks like a path entering a cycle. That means that $W = \\{ n : a^n \in L \\}$ is eventually periodic: for some $k,l$, for all $n \geq k$ it holds that $n \in W$ iff $n + l \in W$. We are now left with a problem in number theory, which I leave for you to ponder. (Try a few examples to see when an eventually periodic $W$ can fail to satisfy the property you're looking for.)
> 2 votes

---
Tags: regular-languages, finite-automata, decision-problem
---


# Question
Title: Why does stable matching without Gale-Shapely takes n! steps
There are n men and n women. I am unable to understand how stable matching done by simply searching through all the matchings takes n! steps i.e., I cannot figure out why there are n! matchings possible.

# Answer
> 4 votes
Suppose that the group of men is $m\_1,\ldots,m\_n$ and the group of women is $w\_1,\ldots,w\_n$. Suppose that man $m\_i$ is matched to woman $w\_{c\_i}$. Then the matching can be described by the sequence $c\_1,\ldots,c\_n$. Each $c\_i$ is in $\\{1,\ldots,n\\}$, and $c\_i \neq c\_j$ for $i \neq j$. So $c\_1,\ldots,c\_n$ is a permutation of $\\{1,\ldots,n\\}$, of which there are $n!$.

# Answer
> 2 votes
@Yuval Filmus's answer is perfect.

another way to is think of it the as the following problem:

> *in how many ways can n men sit on n chairs?*

(think of chairs analogous to women, the "chairs" do not move.. it's the men who keep shifting here)..

so it's basically just any valid permutations among them... and that's $n!$

---
Tags: algorithms
---


# Question
Title: Finding asymptotically tight bounds $\Theta$ of two procedures
I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this:

```
public static int c(int n) {
    int i, j, s = 0;
    if (n > 1) {
        for(i = 0; i < n; i*=2) {
            for(j = n; j > 0; j/=2) {
                s++;
            }
            s+=c(n-2);
        }
    }
}

```

Now I have set the following recurrence equation: $T(n)=\log\_2n\*T(n-2)+\Theta(\log\_2n)$

Now the height of the recurrence tree is $n/2$ so the $T(n) = n/2 * (\log\_2n+\log\_2n)=\Theta(n\*\log\_2n)$

The next procedure is this:

```
public static int d(int n, int m) {
    int i, j, k, ss = 0;
    if (n > 1) {
        for(i = 0; i < n; i++) {
            for(j = i; j > n; j+=2) {
                ss+=(i+1)-2*j+m;
            }
        }
        for(k=0; k<8; k++) {
            ss+=d(n/2, m/(k+1))
        }
    }
    return ss;
}

```

Again I have set this equation: $T(n, m)=8\*T(n/2, m/(k+1))+\Theta(n^2)$

Now I think the $m$ parameter is not important because it is not used in for loop as a counter. Where $n/2$ gives us a recurrence tree of height $\log\_2n$. So we get this: $T(n, m) = 8 * \log\_2n\*n^2=\Theta(n^2)$

I know that recurrence equations that I have set up are probably right, while the I am not sure about next steps.

# Answer
Note that the first algorithm never terminates for $n\>1$; it starts with $i=0$ and multiplies $i$ by $2$ in every iteration of the outer loop, so we never get $i \geq n$. I'll assume we start with $i=1$ instead.

---

I have some problems with your approach.

1. What are you counting? Why?
2. Where do the $\Theta$-terms in the recurrences come from? Don't you know better?
3. Your $\Theta$-"arithmetic" is flawed. Please check your definitions and maybe our related reference questions.

To give you something to work with, let's look at your first algorithm. I say we count arithmetic operations and comparisons because they seem to be the most numerous (no other operations occur in the inner loop). Each loop translates to a sum, so we get

$\qquad\displaystyle T\_c(n) = \sum\_{i=0}^{\lfloor \log\_2(n) \rfloor} 4 + T\_c(n-2) + \sum\_{j=0}^{\lceil \log\_2(n) \rceil} 3$

and $T\_c(0) = T\_c(1) = 0$. You have to solve this recurrence; note that it contains a bit more detail than yours. If you throw such detail away, you should be very certain that this is justified (which is why professors do it all the time when appropriate). Such certainty comes only with practice, so you should work a few cases through rigorously.

First, you should simplify the sums. For the purpose of obtaining $\Theta$-bounds, you can work with upper and lower bounds on the recurrence. For instance, consider

$\qquad\displaystyle T\_c^\leq(n) = (\log\_2(n) + 1) \cdot (4 + T\_c^\leq(n-2) + 3(\log\_2(n) + 2))$ and

$\qquad\displaystyle T\_c^\geq(n) = (\log\_2(n) - 1) \cdot (4 + T\_c^\geq(n-2) + 3\log\_2(n))$

with the same anchors. If you get the same $\Theta$-bounds (or compatible $O$- and $\Omega$-bounds) from these, you have by $T\_c^\geq(n) \leq T\_c(n) \leq T\_c^\leq(n)$ and squeeze theorem a $\Theta$-bound for your original recurrence.

Strategies for solving recurrences are already exhibited in detail in our reference question, so I'll leave that part to you.
> 3 votes

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


# Question
Title: Confusing equivalence $\Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$
Let $B$ be a recursive enumerable set and $B = W\_n$, where $W\_n = \\{x \in \mathbb N \mid \Phi(x,n)\downarrow\\}$ and $\Phi^{(n)}(x\_1, \ldots, x\_n, y)$ is the value of the function at the terminal snaphot.

There is a definition that leaves me really confused: $$n \in W\_n \Leftrightarrow \Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$$

the thing is we know that $\text{HALT}$ is not computable, therefore is is *undefined* so how is it possible that it is equivalent to $\Phi(n,n)\downarrow$ which is actually a defined function? What am I missing here?

# Answer
The function HALT is perfectly defined, it's just not computable - there is no program that computes it. Similarly, $\Phi(n,n) \downarrow$ is not a condition that can be computed by a program. The situation is asymmetric: if $\Phi(n,n) \downarrow$ then a program can verify that, but in the other case you're at loss. This is because HALT is recursively enumerable (partially computable).
> 2 votes

---
Tags: computability, halting-problem
---


# Question
Title: What's wrong with my beta reduction of pred c_0 on Church numerals?
I'm trying to calculate $\text{pred}\\, c\_0$, where $\text{pred}$ is the previous church encoded number and $c\_0$ is the number $0$ ($\lambda s. \lambda z. z$).

The formula for $\text{pred}$ is $\lambda n. \lambda s. \lambda z. n (\lambda g. \lambda h. h (g s))(\lambda u.z)(\lambda v.v)$

My $\beta$ reduction looks like this so far (I've underlined the function and the applied parameter)

$$ \text{pred}\\, c\_0 \to \lambda s. \lambda z. c\_0 \underline{(\lambda g. \lambda h. h (g s))}\text{ }\underline{(\lambda u.z)}(\lambda v.v) \to $$

$$\lambda s. \lambda z. c\_0 (\lambda h. h (\underline{(\lambda u.z)}\text{ } \underline{s}))(\lambda v.v) \to$$

$$\lambda s. \lambda z. c\_0 \underline{(\lambda h. h z)}\text{ }\underline{(\lambda v.v)} \to$$

$$\lambda s. \lambda z. \underline{c\_0}\text{ } \underline{z} \to$$

$$\lambda s. \lambda z. (???)$$

# Answer
> 2 votes
$$ \mathrm{pred}\\, c\_0 \to \lambda s. \lambda z. c\_0 \underline{(\lambda g. \lambda h. h (g s))} \\; \underline{(\lambda u.z)}(\lambda v.v) $$

Nope, that's not a redex.

You have a term of the form $c\_0 M N P$. That's $c\_0 M N$ applied to $P$. It could be parenthesised as $((c\_0 M) N) P$. This is how lambda calculus encodes functions with multiple arguments: by applying the function to one argument, and then applying the result to the next argument, and so on. Since this construction is very common, parentheses are omitted: function application associates to the left.

Once you expand the abbreviations, there is only one redex in $\mathrm{pred}\\,c\_o$, which is $(\lambda n. \[\]) c\_0$. This is very intuitive: $\mathrm{pred}$ is a function that takes a numeral as an argument, and the first thing you to to kick off the calculation is to apply the function to the numeral.

---
Tags: lambda-calculus, church-numerals
---


# Question
Title: Solution for a combinatorial minimization problem
Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality $p \le {a \choose b}$. Is there a closed form solution (can be approximate as well/doesn't have to be exact) for that combinatorial optimization problem?

# Answer
G. Bach noticed that the best choice for $b$ is $\lfloor a/2 \rfloor$, and furthermore this choice gives the maximal binomial coefficient. The easiest way to see this is to consider the ratio of two adjacent binomial coefficients: $$ \frac{\binom{a}{b}}{\binom{a}{b+1}} = \frac{b+1}{a-b}.$$ Therefore $\binom{a}{b} \leq \binom{a}{b+1}$ iff $b+1 \leq a-b$ iff $2b+1 \leq a$, and we get the desired result.

The binomial theorem states that $$ \sum\_{b=0}^a \binom{a}{b} = 2^a, $$ hence $$ \frac{2^a}{a+1} \leq \binom{a}{\lfloor a/2 \rfloor} \leq 2^a. $$ (The correct order of magnitude, $\Theta(2^a/\sqrt{a})$, can be found using Stirling's approximation.) Therefore the optimal $a$ satisfies the following inequalities: $$ \frac{2^{a-1}}{a} \< p \leq 2^a. $$ Therefore $a \geq \log\_2 p$. On the other hand, when $p \geq 4$, $a \geq 2$, and so $a - \log\_2 a \geq a/2$ (since $a-\log\_2 a$ is monotone and $2 - \log\_2 2 = 2/2$). Therefore for $p \geq 4$, $$ 2p\log\_2 (2p) \> 2\frac{2^{a-1}}{a} (a - \log\_2 a) \> 2^{a-1}.$$ We conclude that $$ \log\_2 p \leq a \< \log\_2 p + 1 + \log\_2 \log\_2 (2p). $$ Therefore the binary search that G. Bach mentions takes only $O(\log\log\log p)$ steps.

If all we want is an asymptotic expression, then since $\binom{a}{\lfloor a/2 \rfloor} = \Theta(2^a/\sqrt{a})$, approximately we have $2^a/\sqrt{a} = Cp$, and so $a = \log\_2 p + \Theta(\log\_2\log\_2 p)$. More terms can be obtained by taking more terms in Stirling's approximation. For example, we can find a constant $A$ such that $a = \log\_2 p + A\log\_2\log\_2 p + o(\log\_2\log\_2 p)$.
> 6 votes

# Answer
For any $a$ we have

$\text{max}\\,\\{\binom{a}{b}\\} = \binom{a}{\lceil a/2 \rceil}$

since the binomial grows towards "the middle" and afterwards declines again (a proof for that is not difficult and probably easy to look up if need be).

So what you want is the minimal $a$ such that $p \leq \binom{a}{\lceil a/2 \rceil}$. Let's expand that term:

\begin{align} p &\leq \binom{a}{\lceil a/2 \rceil} = \frac{\prod\_{i = \lceil a/2 \rceil}^{a}i}{\lfloor a/2 \rfloor!} \qquad (\*) \iff \\ p \cdot \lfloor a/2 \rfloor! &\leq \prod\_{i = \lceil a/2 \rceil}^{a}i \end{align}

If that is any help, the product on the right hand side is also called the "falling factorial" and usually denoted as

\begin{align} \prod\_{i = \lceil a/2 \rceil}^{a}i = (a)\_{\lfloor a/2 \rfloor} \end{align}

where the "index" is the number of factors in the factorial.

Now this is where it gets a bit tricky, since this doesn't really give us a polynomial in $a$; the exponents of the factorial on the left hand side and the falling factorial on the right hand side - if we rewrite them as "polynomials" - depend on $a$ instead of being constants, so we can't just use some algorithm to find the roots of those polynomials. What we can do, however, is do a sort of binary search. We can use the inequation $(\*)$ and do a search over $a$; start out with $a = 1$, check whether the inequation holds; after each iteration, go $a := a \cdot 2$ until $(\*)$ holds; call that first $a$ for which it holds $a\_{max}$. Then do a binary search over $\[\frac{a\_{max}}{2}; a\_{max}\]$ to find the smallest $a$ for which $(\*)$ holds.

No idea whether there's a closed form or what the complexity of the above would be, though.
> 4 votes

---
Tags: optimization, combinatorics
---


title: The Power of Randomized Reduction

text:
# Question
Title: The Power of Randomized Reduction
I try to figure out **a redundant power of two-sided error randomized Karp - reduction.**

It's well known fact and it is relatively hard to show that BPP is reducible by a one-sided error randomized Karp-reduction to coRP (in case of promise problem).

Without delving into details it make sense that the combination of the one - sided error probability of the reduction and the one-sided error probability of coRP leads to two-sided error probability of BPP. Of course the proof of that is not so intuitive.

The question it is possible by two-sided error randomized Karp-reduction to reduce BPP to some constant set in P? In the light of the power of one - sided randomized Karp - reduction, it make sense that two-sided randomized Karp - reduction is strong enough to reduce BPP to constant set, but how to show it formally?

**Addendum:**

**BPP** is the set of the problems that is solvable in polynomial time by two-sided error randomized algorithm, so as a result of two - sided error randomized algorithm we will get some output, them the problem in BPP can be reduced to problem P by two-sided error randomized Karp - reduction in sense that reduction is allowed to make error on both sides. Does it mean that two - sided error randomized reduction will justify the two-sided error that was made by the algorithm in solving the problem in BPP?

# Answer
> 1 votes
We can think of a BPP algorithm $A$ for a language $L$ as accepting two inputs, the real input $x$ and a random string $r$, whose length is polynomial in $x$. Now take the Boolean circuit evaluation problem, which is P-complete. Since $A(x,r) \in P$, we can reduce $A$ to this problem, substituting random $r$. Then if $x \in L$ then the reduction yields a YES instance with probability at least $2/3$, and if $x \notin L$ then it yields a NO instance with probability at least $2/3$.

---
Tags: complexity-theory, reductions, randomized-algorithms
---


# Question
Title: Concatenation among different language types
I am trying to figure out the result of the concatenation among different language types (regular, context free, ...). I think the result strongly depends on the nature of the languages which will be concatenated, but I have some doubts on determining the category the result belongs to. Maybe troughout an example it will be easier to solve all my doubts and let you understand better the nature of my question. For instance, let $L = \left \\{ 0^{n}\cdot 1^{n} \mid n \geq 0 \right \\}$ and $L^{R} = \left \\{ 1^{n}\cdot 0^{n} \mid n \geq 0 \right \\}$

Those two languages are obviosly not regular (it's easy to apply the Pumping Lemma here) but what happens if I define this result language $L{}' = L \cdot \left \\{ 0, 1 \right \\}^{\*} \cdot L^{R}$

I think it should be still not regular, since we can apply again the pumping lemma by letting be $p$ the length of the pumping and $w=0^{p}1^{2p}0^{p}$, w is in $L'$. The contination is easily.

But is it good to consider that w of $L'$?

# Answer
> 1 votes
The language $L'$ contains all possible strings, and so it is in particular regular. This is because the empty word is in $L$, and so $L\cdot \\{0,1\\}^\* \cdot L^R$ contains $\\{0,1\\}^\*$. If you "proved" that it's not regular using the pumping lemma, you have made a mistake applying it. Try to find it; this will lead to better understanding of the pumping lemma.

---
Tags: formal-languages, regular-languages, context-free, pumping-lemma
---


title: Complete graph invariant

text:
# Question
Title: Complete graph invariant
Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph is a complete invariant for graph isomorphism (i.e. that multiset uniquely identifies a graph up to isomorphism)?

# Answer
The answer is no. A counterexample is given by the following two graphs both having $(-1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1) $ as the multiset that you describe.

If you want to play further, you can use the following Sage program that found them

```
def tupleDet(G):
    A = G.am()
    L =  []
    for sub in subsets(range(G.order())):
        D = A.matrix_from_rows_and_columns(sub,sub)
        L.append(D.det())

    return tuple(sorted(L))

def search(n):
    d= {}
    for G in graphs.nauty_geng(str(n)):
        des = tupleDet(G)
        if des in d:
            print G.graph6_string(), d[des]
            return
        else:
            d[des] = G.graph6_string()

```
> 5 votes

# Answer
Let $A$ be the adjacency matrix of the graph and let $A\_{ij}$ be its minors. It is known then $(A^{-1})\_{ij} = (-1)^{i+j} \det A\_{ji}/\det A$. So the original graph can be recovered from your data. (The determinants of the cofactors determine $A^{-1}$, and so $A$, up to a constant factor, and (unless the graph is empty) there is a unique choice that leads to a $0,1$ inverse.)

Suppose first that the collection of determinants of principal minors is ordered. Take any graph with a non-trivial automorphism (e.g. a square), and consider two different isomorphic representations. These will have different invariants but be isomorphic.

Suppose next that the collection of determinants of principal minors is not ordered. Any two isospectral graphs with the same number of edges will have the same invariants up to sign (i.e. the same collection of absolute values of determinants of cofactors) since they have the same overall determinant and the same number of $0$s and $1$s. So probably if you try several pairs you'll find one where the unordered invariants are exactly the same.
> 0 votes

---
Tags: graphs, graph-isomorphism
---


# Question
Title: Is CS more like software and CE more like hardware?
At my university, a degree is "Computer Science and Engineering" but at US universities I understand that the degrees are different so what is the fundamental difference? Is computer engineering lower level like hardware and operating systems while computer science is more like language technologies?

# Answer
> 1 votes
There's a fine line between the two. Because they both have some very similar ativities. But i'd say Computer Science is Software focused, the study of the science of computers while Computer Engineering is the application of the science of computers.

# Answer
> 2 votes
This is actually an easy one, particularly if you just want to see some meaningful distinction drawn by an organization people listen to. Consider the ACM/IEEE guidelines on computing curricula.

The differences between Computer Science and Computer Engineering can be seen when comparing the respective bodies of knowledge:

Computer Science (2008)

* Discrete Structures, 43 core hours
* Programming Fundamentals, 47 core hours
* Algorithms and Complexity, 31 core hours
* Architecture and Organization, 36 core hours
* Operating Systems, 18 core hours
* Net-Centric Computing, 15 core hours
* Programming Languages, 21 core hours
* Human-Computer Interaction, 8 core hours
* Graphics and Visual Computing, 3 core hours
* Intelligent Systems, 10 core hours
* Information Management, 11 core hours
* Social and Professional Issues, 16 core hours
* Software Engineering, 31 core hours
* Computational Science, no core hours

The total core hours for CS add up to 290 hours.

Computer Engineering (2004)

* Algorithms, 30 core hours
* Computer Architecture and Organization, 63 core hours
* Computer Systems Engineering, 18 core hours
* Circuits and Signals, 43 core hours
* Database Systems, 5 core hours
* Digital Logic, 57 core hours
* Digital Signal Processing, 17 core hours
* Electronics, 40 core hours
* Embedded Systems, 20 core hours
* Human-Computer Interaction, 8 core hours
* Computer Networks, 21 core hours
* Operating Systems, 20 core hours
* Programming Fundamentals, 39 core hours
* Social and Professional Issues, 16 core hours
* Software Engineering, 13 core hours
* VLSI Design and Fabrication, 10 core hours
* Discrete Structures, 33 core hours
* Probability and Statistics, 33 core hours

The total core hours for CmpE add up to 486.

A fair way to compare the two might be to find a percentage makeup based on the above curricula. The conclusion would seem to be that CS is at or above CmpE in subjects they have in common, and has fewer other subjects, whereas CmpE is lower in common areas to both programs, but has more subjects not studied in CS, mostly related to EE. This seems to be consistent with the distinction I normally draw, so I'm happy with the overall result of the analysis, but you might draw your own conclusions.

---
Tags: terminology, education
---


title: How hard is factoring a complex number?

text:
# Question
Title: How hard is factoring a complex number?
Given complex number $C=a+ib$, I want to find two complex numbers $C\_1=x+iy$ and $C\_2=z+iw$ such that $C=C\_1\*C\_2$ (a,b,x,y, z and w are all non zero integers). This problem is at least as hard as Integer factoring. Prime complex number has one as its only factor.

Does this problem reduce to integer factoring? Is it NP-hard?

# Answer
> 4 votes
If $C = \prod\_i C\_i$ is a prime factorization of $C$ then $N(C) = \prod\_i N(C\_i)$, where $N(\alpha + \beta i) = \alpha^2 + \beta^2$. Furthermore, $\pi$ is prime if either (i) $N(\pi) = 2$, (ii) $N(\pi) = 4a+1$ is prime, (iii) $N(\pi) = (4a+3)^2$ is the square of a prime. So factoring $C$ reduces to factoring $N(C)$.

---
Tags: complexity-theory, number-theory, factoring
---


title: Showing NP-hardness of HALF-SAT

text:
# Question
Title: Showing NP-hardness of HALF-SAT
Yesterday I wrote my undergraduate exam in complexity theory. I had to leave off one question, which bugs me since then. Consider: $$ HALF-SAT = \\{ \varphi \mid \varphi \text{ is a formula which is satisfied by at least half of all assignments }\\} $$ I'd like to know how I can prove NP-hardness.

FWIW, here's what I figured out:

1. HALF-SAT is *probably* not $\in$ NP, at least in no verifiable way I can think of (not really relevant to the question)
2. SAT $\preceq$ HALF-SAT doesn't work, at least not by just adding clauses with new variables, doesn't change satisfiable-assignments/arbitrary-assignments ratio
3. TAUT $\preceq$ HALF-SAT via $\varphi \mapsto \varphi \wedge x\_{new}$, but that's coNP-hardness (together with NP-hardness this further lets me assume 1., intuitively)

And no, this has nothing to do with the problem you find via googling "HALF-SAT".

# Answer
Hint: Take a new variable $x$ and add it to all clauses. This shows that HALF-SAT' is NP-hard, where HALF-SAT' differs from HALF-SAT by strengthening "at least half" to "more than half". HALF-SAT is similar.

The $P$-closure of HALF-SAT' (and HALF-SAT) forms the complexity class $PP$.
> 8 votes

# Answer
A possible reduction from SAT is the following. Assume given formula $\varphi$ has variables $x\_1,\dots,x\_n$ we map $\varphi$ to $$ (\varphi\land y)\lor\left(\overline y\land\bigvee\_{i=1}^nx\_i\right). $$

1. If $\varphi\notin\textrm{SAT}$, then the left part is always false. The right part is satisfiable for $y=0$ getting $2^n-1$ solutions. Hence $f(\varphi)\notin\textrm{HALF-SAT}$.
2. If $\varphi\in\textrm{SAT}$, then for assignments setting $y=1$ we get $c\>0$ satisfying assignments for the left part. If $y=0$ we still get the $2^n-1$ many satisfying assignments. Hence all in all we get $2^n-1+c\>2^n$ satisfying assignments which implies $f(\varphi)\in\textrm{HALF-SAT}$.

As this problem is also PP-complete the coNP- and NP-hardness directly follow as PP is closed under complement. However the direct reduction from SAT seem to be quite interesting for me.
> 3 votes

---
Tags: complexity-theory, reductions, np-hard
---


title: Determine if this language is regular

text:
# Question
Title: Determine if this language is regular
Let $L = \\{xyx \mid \text{ for some }x,y \in \\{0,1\\}^+\\}$. Is this language regular?

So I was trying to construct a DFA, but I don't how to do this with this language.

# Answer
You can indeed use the pumping lemma to answer this. Assume $L$ is regular, and let $p$ be its pumping length. Let $w = 0^p1 \cdot 1 \cdot 0^p1 \in L$. By the pumping lemma (well, a strong form of it), you can pump from the first $p$ letters, and obtain $w' = 0^{q}1\cdot 1 \cdot 0^p1$ with $q\neq p$, hence $w'\not\in L$.

@Gilles: This came after an even number of cups of coffee :-).
> 4 votes

# Answer
Recall that the Myhill-Nerode indistinguishability relation $\sim\_L$ is defined on the set $\\{0,1\\}^{\*}$ of all inputs as $u \sim\_L v$ iff for all $w$, $uw \in L \Leftrightarrow vw \in L$. The Myhill-Nerode Theorem states that $\sim\_L$ has finitely many blocks iff $L$ is regular.

Let $\alpha\_i = 1^i0^i1$ for each $i\ge 1$. I claim that $\[\alpha\_i\]\_{\sim\_L} = \[\alpha\_j\]\_{\sim\_L} \Rightarrow i = j$. Hence $\\{\[\alpha\_i\] \mid i=1,2,\dots\\}$ forms an infinite subset of the blocks of $\sim\_L$. Therefore $\sim\_L$ must have infinitely many distinct blocks, so $L$ cannot be regular.

To prove the claim, suppose that $\[\alpha\_i\]\_{\sim\_L} = \[\alpha\_j\]\_{\sim\_L}$ for some $i,j \ge 1$. Then $\alpha\_i \sim\_L \alpha\_j$, so for any suffix $w$, $1^i0^i1w \in L \Leftrightarrow 1^j0^j1w \in L$. In particular this must hold for $w=1^j0^j$, and since $1^j0^j11^j0^j \in L$, it must hold that $1^i0^i11^j0^j \in L$. Hence $i=j$.

(Finding an infinite subset that worked required an odd number of cups of tea. But using Myhill-Nerode means not having to remember the various pumping lemmas.)

*Edit 2015-10-28:* was answering the question about $\\{xyx\mid x\in\\{0,1\\}^{+},y\in\\{0,1\\}^{\*}\\}$, now fixed.
> 5 votes

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


# Question
Title: Difference between approximation scheme and approximation algorithm?
What is the difference between approximation schemes and approximation algorithms?
Why do we study approximation schemes?

# Answer
> 10 votes
In theoretical computer science, an approximation algorithm is an algorithm that guarantees a certain approximation ratio $\rho$, and an approximation scheme is a (uniform) collection of algorithms that guarantees several different approximation ratios. Since the collection is uniform (all the algorithms look the same but with different parameters), you can also think of an approximation scheme as an algorithm with an auxiliary parameter $\rho$ which then guarantees an approximation ratio of $\rho$; the close $\rho$ is to $1$, the harder the algorithm would have to work, and not all $\rho$ are valid inputs. For example, usually you need $\rho \neq 1$. If the scheme works for $\rho$ arbitrarily close to $1$, and furthermore the scheme is polynomial time (for each $\rho$ separately), then it is a *polynomial time approximation scheme* (PTAS).

# Answer
> 4 votes
There is no real difference between approximation "schemes" and "algorithms". The first is in my experience used when talking about algorithms that provide abitrarily good approximations, the second is used for algorithms with a constant or worse approximation factor.

We study approximation algorithms because some problems are infeasible to solve exactly. Take for example the Traveling Salesman problem, where you want to find a shortest tour that visits each city in a country exactly once. Solving it exactly is NP-hard, but finding a solution that is at most 3/2 times as long as the shortest one is fairly easy.

---
Tags: algorithms, terminology, approximation
---


# Question
Title: Linear Programming: algorithm to check if ratios can be combined with n bottles to equal a given ratio
Say you have n bottles. each with a ratio of $(a\_i: b\_i: c\_i)$. ($a\_i/(a\_i+b\_i+c\_i),\cdots$ swap out the numerator for $b\_i$ and $c\_i$ respectively).

Now you are given a ratio of $(a:b:c)$. Use Linear programming to find an efficient algorithm to this problem. If it's yes, you can output the parts of bottles that gave you the answer. (e.g. 2 parts from one bottle, 1 part from another bottles.)

So it's not clear how to do this. One of my first thoughts was to make a variable $z = \sum(\alpha\_i\*(a\_i,b\_i,c\_i)) - (a,b,c)$. This, I'm thinking could be the objective function we minimize.

Not sure if this works. Or if it does, where to go from here. Also, I'm not sure if I can have the alphas in the thing I'm trying to minimize. What am I supposed to do with these alphas.

Not sure what it means by algorithm either. That is, even if I could set up the problem as a linear problem, not sure what the algorithm would be.

# Answer
I don't know what class this is for, and how much linear programming you are learning in it, so I don't really know what you need.

One way to do it: assuming $a\_i + b\_i + c\_i = 1, \ \forall i$, use the linear program:

$$ \max x$$

such that

$$\eqalign{ \sum\_i a\_i \lambda\_i &= a,\\ \sum\_i b\_i \lambda\_i &= b,\\ \sum\_i c\_i \lambda\_i &= c, \\ \lambda \_i -x &\geq 0 \quad \forall i. }$$

If there is a solution with $x \geq 0$, then you're done. Why? If $x \geq 0$, then there is a set of positive $\lambda\_i$ satisfying the first three equations above: $\sum\_i a\_i \lambda\_i = a$. The $\lambda\_i$ give you the proportions with which to mix the bottles. If one of the $\lambda\_i$ were less than $0$, then this would tell you to add a negative amount from that bottle, yielding an unphysical "solution". If there is no solution of the linear program with $x \geq 0$, then no combination will give the proportions $a:b:c$, as that would give a solution to the linear program with $x \geq 0$.
> 4 votes

---
Tags: linear-programming
---


# Question
Title: Which redexes are there in $\lambda s. \lambda z. (\lambda u. z)(\lambda v. v)$? How to substitute arguments?
I'm having difficulties understanding lambda calculus, specially identifying what's a redex. Which redexes are there in $\lambda s. \lambda z. (\lambda u. z)(\lambda v. v)$?

The book uses $(\lambda u. z) \[u \to (\lambda v. v)\]$,

but isn't $(\lambda s. \lambda z. (\lambda u. z))\[s \to (\lambda v. v)\]$ valid too?

# Answer
> 1 votes
You must learn how to put in parentheses and then it will be easier to figure out what is what. In the above case, we first put in parentheses: $$\lambda s . (\lambda z . ((\lambda u. z) (\lambda v . v))).$$ This is the only correct way to put back parentheses. For instance, this is wrong $$(\lambda s . (\lambda z . (\lambda u . z))) (\lambda v . v)$$ Why is it wrong? Because the rules for writing expressions without parentheses say that when you see $\lambda x . \cdots$ that means that $\lambda x$ binds the whole expression. For instance $\lambda x . x (\lambda y . y)$ is the same as $\lambda x . (x (\lambda y . y))$ and is *diffrerent* from $(\lambda x . x) (\lambda y . y)$.

If this is not resolving your dilemma you have to explain *why* you think that the other redex is valid.

---
Tags: lambda-calculus
---


# Question
Title: Using a computer algebra system to optimize mathematical expressions
This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, theoretically and/or practically, to find the form that has the fewest operations. The next step would be to prefer operations that are faster (ie. multiply instead of divide). Lastly, to find a form that maximizes extraction of repetitive subexpressions, so that the subexpressions can be evaluated once and substituted for potentially significant performance gains. Has any research been done in this area? Thanks.

# Answer
> 2 votes
This doesn't completely answer your question, but you ask if research has been done on this.

This is an area called Symbolic Algebra. I'm sure there are many such research groups, but here is one:

https://www.scg.uwaterloo.ca/

They're the group at Waterloo which developed the Maple software (similar to Mathematica).

# Answer
> 1 votes
That sounds like the principles of compilers. They're designed to do such things. On the other hand, **computational science** is the field that studies optimizations for algorithms in order to do less operations, minimize rounding errors and so on.

http://en.wikipedia.org/wiki/Computational\_science

# Answer
> 1 votes
Check out any compiler book, they give an overview of what a compiler does. Just keep in mind that the simplistic algorithms described (and the not too complex cases they handle) are *far* from what is today's state of the art.

"Optimizing" expressions (or any code) is most of the time counter-productive: It takes up your (valuable) time doing the changes, testing them, and keeping them up to date when the program changes (and you *know* you won't understand a line of the program in a week's time, so an afternoon goes by while you wrap your head around it next time), all to shave off a bit of (inexpensive) computer time. If it really reduces execution time... today's compilers are much better at doing the kinds of changes you propose than you will ever be, such modifications are rarely applicable (most expresisons are very simple), and finally experience has shown time and again that programmers are ***terrible*** at guessing what parts of their programs are worth trying to make faster.

# Answer
> 1 votes
A google search of computer algebra optimization brings up a few hits that look promising. I can vouch for the effectiveness of this approach in reducing the number of operations required for matrix multiplication where:

* there are complex patterns in the matrix
* the cost of the factorization can be amortized over many subsequent multiplications.

What I did was quite simple so I was able to write the CAS myself. If you do it yourself a compact language such as Scala is helpful. More complicated problems would probably be better solved using a properly designed CAS. Many are able to generate code in more conventional computer languages for numerical execution.

Of course compilers do a little of this already, but there are lots of optimisations that they miss in large problems.

On a related point, I've often wondered if an approach like this could be used in query optimization, using set theory.

---
Tags: optimization, computer-algebra
---


# Question
Title: How to decide the scope of the following lambda expression?
I am having a difficulty in deciding the scope of the left-most lambda in the following expression.

```
λx.x(λuv.v)(λab.a)(λcd.c)

```

I have learnt that we should put brackets in such a way that the scope of lambda will be maximum. So arrived at candidate- answer 1, below.

On the other hand, since the expression `(λuv.v)(λab.a)(λcd.c)` does not contain any x, if we put brackets as in answer 2, still we are not changing the scope, right?

But I know that these two answers are not equivalent. So which one is the correct one?

The two candidate answers are:

1. `λx.(x(λuv.v)(λab.a)(λcd.c))`
2. `(λx.x)(λuv.v)(λab.a)(λcd.c)`

I came up with this confusion through the tutorial: A Tutorial Introduction to the Lambda Calculus by Raul Rojas. There, in page 6, ~T is given as `λx.x(λuv.v)(λab.a)(λcd.c)`. If we apply brackets as in my answer-1, we will not be able to evaluate ~T to F.

# Answer
The correct answer is:

> (λx.x (λuv.v) (λab.a) (λcd.c))

If I add in parethenese to disambiguate application, it becomes.

> (λx.((x (λuv.v)) (λab.a)) (λcd.c))
> 2 votes

# Answer
Sorry reviving this question, but I think there are parenthesis missing on the tutorial. It should be

$$\neg T = (\lambda x. x (\lambda uv. v)(\lambda ab. a))(\lambda cd. c)$$

On the book we have $$\neg T = \lambda x. x (\lambda uv. v)(\lambda ab. a)(\lambda cd. c)$$ but that will evaluate to $T$ as the first redex to be processed will be $(\lambda uv. v)(\lambda ab. a)$

I'm a newbie here, so veterans, please check if I'm not mistaken!
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: Is $L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $ regular?
Suppose we have some regular language $L$, then can we say that $$L\_{half} = \\{w : \text{for some } z \in L, x \in \Sigma^\*, z = wx \wedge |w| = |x| \\} $$ is also regular?

I have a 'feeling' that it is, but I can't sketch a proof for it.

# Answer
> 10 votes
Yes, the language is regular: Consider a DFA A such that $L(A)=L$ Now, assume that you know, somehow, that when given a word $w$, the run of $A$ will end up in state $q$.

All you need to check now is that there is a run of $A$ on some word of length $|w|$ that gets from $q$ to an accepting state. This can be done by using the product automaton $A\times A$, where the first component acts exactly like $A$, and the second acts like $A$, but starts from state $q$ and ignores the input - that is, for each letter it nondeterministically goes anywhere that $A$ can go. Then, a run is accepting if the first component ends up in $q$, and the second component ends in an accepting state.

Finally, you can drop the assumption by taking $|Q|$ copies of this construction, where each copy "guesses" in which state $A$ will end up in. You end up with a nondeterministic construction of size $|Q|^3$

---
Tags: regular-languages, automata
---