# Question
Title: Non-Deterministic FSA to Deterministic FSA, Two initial states
My method of conversion is by creating a reachable set tree and each set within the tree would represent the new states.

I have never dealt with FSAs that has 2 or more initial states. How do i create my reachable set tree with two or more states?

# Answer
> 0 votes
The powerset construction converts an NFA to a DFA. You then "optimize" the result by removing states which cannot be reachable from the start state. When the NFA has multiple starting states, you do exactly the same thing. The starting state of the new DFA is the state corresponding to the set of starting states in the NFA (compare that to the usual case, in which the starting state of the DFA is the signleton consisting of the starting state of the NFA).

Given a DFA, you can compute the set of reachable states iteratively: the starting state is reachable; any state which it points to is reachable; any state which these point to is reachable; and so on. (Technically, this is known as BFS. There are also other algorithms, such as DFS.)

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


# Question
Title: What aspects of linguistics are necessary or good for natural language processing?
What aspects of linguistics are necessary or good to know for natural language processing? What references do you recommend for studying those aspects? Thanks!

# Answer
> 3 votes
NLP is a big place, you might want to be more specific.

Within information retrieval, stemming is a linguistic idea that has become useful as a heuristic means of reducing vocabulary size. As a practitioner I learned about it from An Introduction to Information Retrieval.

# Answer
> 2 votes
It depends - generally, if you want to use or implement well known approaches or systems for some specific application, then you can get by without any linguistics, and if you want to improve state-of-art solutions, then you'd need at least a broad overview of general linguistics (things that apply to human lanuages as such), (non-CS) syntax theories, why POS-tags and phrase/dependency structures are chosen to be built that way, etc - but all the neccessary fragments tend to be taught as part of 'NLP courses', so you can get by with a single source and expect whoever is teaching that NLP course to gather up all the various domains.

Ah, and proper knowledge of your target languages - you can do quite a lot of stuff with foreign text you don't understand, but if you have some linguist available for every target language, then it is very useful.

# Answer
> 1 votes
There is no good answer to your question. Much depends on the kind of NLP you want to do. Do you want to do man-machine interfaces, information retrieval, syntax checkers, machine translation, data extraction from corpora? Do you want to process text or speech? Are you interested in ill formed sentences? Are you concerned with syntax or semantic processing? And so on ...

Now, your question is about "aspects of linguistics \[...\] necessary or good to know for natural language processing". Is statistics an aspect of linguistics? Is formal languages theory an aspect of linguistics? Or simply, is NLP an aspect of linguistics? If not, where is the border? Recall that formal language theory started with linguists such as Chomsky or Bar-Hillel.

My suggestion would be to study some of the systems that have been developed for NLP, at various stages of language processing, and it will force you to extend your knowledge of linguistics as you go along. Use call by need when you learn, especially if you do not know what is essential.

Another interesting kind of systems to study (which are also NLP topics) are system used to extract linguistic data from corpora, whether lexical, syntactic or semantic. This data will then be fed to your NLP systems to process actual texts for whatever purposes.

Statistics and formal languages are important to structure understanding, but they have to be motivated by linguistic considerations too. But if you start with linguistics, you may be bogged down into countless very specific studies.

# Answer
> 1 votes
The answer depends on what you want to do:

1. For speech recognition: Phonetics and phonology
2. For tagging and parsing: Morphology, syntax.
3. For language understanding: Semantics and pragmatics.

---
Tags: natural-language-processing
---


# Question
Title: Why is the class of recursively enumerable languages not closed under complementation?
I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed under complementation?

Explanation also says,

> This fails because $M$ only needs to halt if $w \in L(M)$ - doesn't have to say "no".

What does it mean?

# Answer
> 6 votes
The statement you quote is an argument why the proof for showing that $\mathrm{R}$ (the set of recursive languages) is closed against complement does not work for $\mathrm{RE}$ (the set of recursively enumerable languages). It's not a proof of the reverse in itself -- *another* proof may still work!

The problem is that flipping the result of a TM only works if you *get* a result; $\mathrm{RE}$ promises only an acceptor, not a decider, which may loop if the input is not in the language. Therefore, you can not flip properly; all you'd get is a machine that says "no" of the word is not the language but loops otherwise. That's a machine for $\mathrm{co\text{-}RE}$, not $\mathrm{RE}$.

As for why $\mathrm{RE}$ is not closed against complement, the site you link contains all the answers; let me reiterate.

1. If $L$ and $\overline{L}$ are both semi-decidable, then both are decidable.
2. Hence, if $\mathrm{RE}$ was closed against complement, we'd have $\mathrm{R} = \mathrm{RE}$.
3. But we know that $\mathrm{R} \subsetneq \mathrm{RE}$ (by witness of the halting problem), so this can't be true.

# Answer
> 0 votes
The class of recursively enumerable languages is not closed under complementation, because there are examples of recursively enumerable languages whose complement is not recursively enumerable. Those examples come from languages that are recursively enumerable, but not recursive.

One of those examples is the language $L=\\{(M, w) : M\ \text{is a Turing Machine and}\ w \in L(M)\\}$. This language is recognizable (and hence recursively enumerable), because you can always run Turing Machine $M$ with input $w$, and if $w \in L(M)$, $M$ will halt accepting $w$. It has been shown that this language ($L$) is not decidable.

Now, suppose that $\overline{L}$ (complement of $L$) were also recognizable, then $L$ becomes decidable, because we could use the recognizers for $L$ and for $\overline{L}$ to build a decider for $L$. But since we already now that $L$ is not decidable, then, $\overline{L}$ cannot be recognizable, and hence, the class of recursively enumerable languages is not closed under complementation.

---
Tags: computability, closure-properties, semi-decidability
---


# Question
Title: Are expert systems outdated, what are better alternatives to them, if any?
I need to link facts to actions through rules. If a person bought soup 10 times and he is coming at midday every day, then the system should link the fact that the person bought soup so many times, using the rule "person, consecutively buying soup 5 or more times within a month is going to buy soup with 90% confidence", to the conclusion that with 90% confidence today at midday, the same person will show up, ordering soup.

Above is an example of an expert system, however based on the research I've just done, it seems like expert systems have lost their popularity, which they had in 90s-00s. The only "popular" applications are business decision making and some medical systems. I am wondering if I should use expert systems or should I look into more "advanced" alternatives? What are the obvious disadvantages to using an expert system, besides the setup cost of conducting the research?

# Answer
> 5 votes
Expert systems went through a phase of increasing acceptance and then widespread recognition of their limitations (see Wikipedia). There are many references that consider cons e.g. Problems in expert system development (Kemp, 1993).

In more recent years recommendation systems have taken over some of the function you describe in recommending products to customers. A notable development or historical event was the Netflix contest for movie recommendations which led to a burst of innovation and interest in the area. Another aspect of your question involves learning patterns of human behavior and this can be done with ANNs and similar technology.

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: In Probabilistic Graphical Models, are Cliques and Clusters the same?
I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are the cliques and clusters the same?

# Answer
> 2 votes
A *clique* is a rigorously defined, exact part of a graph $G=(V,E)$;

$\qquad\displaystyle C \subseteq V \text{ is clique} \iff \\{ \\{u,v\\} \mid u,v \in C, u \neq v \\} \subseteq E$.

A *cluster* is more general, but also more nebulous. Here's what Wikipedia has to say:

> Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

So, a cluster also is a set of nodes that is "dense" in some sense, depending on the metric used. However, while is it always clear whether adding a note increases the size of a clique, it's not always clear from looking only at one cluster whether adding a node to it is better; the quality of a clustering is defined on the *whole* graph.

As the Wikipedia article shows, there are many notions of clustering. Cliques can be seen as one of them.

---
Tags: graphs, terminology, probability-theory
---


# Question
Title: If dynamically typed languages are truly statically typed, unityped languages, what is the (finite) type expression of the one type?
Some claim that dynamically typed languages are in reality statically typed, unityped languages. This would imply to me that this one type should be expressible as a static, finite type expression, so can anyone provide such an expression? You can make whatever assumptions you need to make about the base types in the language, but please make sure the language would support types of unbounded size, e.g., lists, recursive types. It would also be nice if it supported records and variants, but whatever helps to illustrate the point will work. I'm also assuming that the language will be required to support some form of sum type, right?

# Answer
This is entirely dependent on the language, and even on the implementation. The type would typically include entries for primitive functions, external library bindings (e.g. file handles), byte-compiled functions, etc. in addition to the data types of the language.

You can see a type like this in an interpreter for a dynamically-typed language written in a statically-typed language.

Here's an example of a type that's sufficient for a Logo value, showing that you don't need much to get started. Logo's values have a very simple structure: the only primitive type is the string, and the only structured type is the list. I use OCaml notation for the type.

```
 type logo_value =
   | Scalar of string
   | List of logo_value list

```

For example the logo value `[3 [4 5]]` is represented by the OCaml value `List [Scalar "3"; List [Scalar "4"; Scala "5"]]`

Here's an example of a type for an interpreter for a fragment of Scheme, again written in OCaml notation. Scheme is a larger language, with a range of primitive and structured types, functions as first-class values, and input/output objects.

```
type scheme_value =
  | Boolean of bool                (* #f, #t *)
  | Exact of Num.num               (* integers and rational numbers *)
  | Inexact of Complex.t           (* reals and complex numbers *)
  | Char of int                    (* Unicode characters *)
  | String of string               (* Strings (mutable, fixed-size) *)
  | Symbol of string               (* Symbols (immutable) *)
  | Cons of scheme_cons            (* Pair (mutable) *)
  | Vector of scheme_value array   (* Vectors (mutable, fixed-size) *)
  | Primitive of scheme_value list -> scheme_value   (* Primitive function *)
  | Lambda of string list * scheme_value             (* (argument names, body forms) *)
  | Port_in of in_channel          (* I/O port (input) *)
  | Port_out of out_channel        (* I/O port (output) *)
  | Eof                            (* (eof-object) *)
 and scheme_cons = {mutable car : scheme_value; mutable cdr : scheme_value}

```
> 8 votes

# Answer
Here is how Dana Scott and Christopher Strachey would have written the unique type. They called it a "domain".

$$ D = {\bf 1} + {\it Int} + {\it Bool} + {\it Char} + (D \times D) + (D \to D)$$

* The **1** is a singleton type, that of nil or null whatever.
* *Int* \- for integers
* *Bool* \- for booleans
* *Char* \- for characters
* $D \times D$ - for pairs of values
* $D \to D$ - for functions over values

We often call such a type a *universal domain*. It contains everything!

If you want lists, for example, just pick the subset represented by the equation

$$ L = {\bf 1} + (D \times L) $$
> 5 votes

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


# Question
Title: How to analyse the complexity of a problem with two or more size measures
Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers). has a search space of size $O(n^n * m^n)$. It is clear that this problem is exponential in $n$, whatsoever $m$ may be. My question: is this same problem polynomial in $m$? what are the assumptions if we can say that? is this way of complexity analysis correct?

# Answer
There's nothing wrong with your approach. You have a two-variable function with a known (almost, up to a multiplicative constant) upper bound. In that case, it's perfectly acceptable to take a "slice" through the function by holding one of the variables fixed and ask how the resulting one-variable function behaves. One does this sort of thing often, when, for example, we take the derivative of $f(x, y)$ with respect to $x$.
> 1 votes

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


# Question
Title: A variation of the graph coloring problem
Given a set of colors $M$ and a graph $G=(V,E)$. Allocate the colors to minimize the number edges with same color on the two vertices of the edge (i.e. minimize pairs of adjoining vertices with same color.).

This problem is different from standard coloring problem. Could someone please provide some literature where this problem is studied?

# Answer
> 3 votes
If $|M| = 2$, this is the max-cut problem.

---
Tags: graphs, reference-request, colorings
---


# Question
Title: Which part of the computer allocates memory in RAM?
When we declare a variable there will be a random part of memory will be allocated in RAM. Which component will allocate the memory? Is the processor or any other specific hardware doing the allocation?

# Answer
When you compile your program, the compiler sets up (relative) positions of memory areas for variables in each piece. The linker takes several separately compiled pieces and libraries, and creates an executable file, which lays out places for each variable. The executable file is loaded into the memory by a loader, which (under the control of the operating system) loads the program at a address in memory, asigning fixed memory positions to the layout given before.

Modern programming languages also allow you to define functions/procedures/blocks with local variables, which get asigned memory addresses at runtime. When the procedure/function is called or the block entered, memory is asigned to the variable; on exit the space is reclaimed.

But then again, modern operating systems use virtual memory, so the variables will be placed at fixed virtual addresses only... the operating system shuffles the memory areas around at will.

And just to muddy the waters a bit more, while analyzing your program the compiler might decide to have the value residing in different places (in memory or in a register) during the program, have several variables share the same space when they aren't used at the same time; or sometimes even get rid of the variable completely.
> 1 votes

# Answer
It is a combination of the standard C library (usually) and the operating system. No hardware is involved. Check out this answer on stackoverflow for more details.
> 2 votes

---
Tags: operating-systems, memory-management, memory-access, memory-hardware
---


# Question
Title: Complexities of basic operations of searching and sorting algorithms
Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is correct ? Please let me know if there is any error, I will correct it.

**Insertion Sort:**

* Average Case / Worst Case : $\Theta(n^2)$ ; happens when input is already sorted in descending order
* Best Case : $\Theta(n)$ ; when input is already sorted
* No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(n)$ in best case
* No. of swaps : $\Theta(n^2)$ in worst/average case & $0$ in Best case

**Selection Sort:**

* Average Case / Worst Case / Best Case: $\Theta(n^2)$
* No. of comparisons : $\Theta(n^2)$
* No. of swaps : $\Theta(n)$ in worst/average case & $0$ in best case At most the algorithm requires N swaps, once you swap an element into place, you never touch it again.

**Merge Sort :**

* Average Case / Worst Case / Best case : $\Theta(nlgn)$ ; doesn't matter at all whether the input is sorted or not
* No. of comparisons : $\Theta(n+m)$ in worst case & $\Theta(n)$ in best case ; assuming we are merging two array of size n & m where $n\<m$
* No. of swaps : No swaps ! \[but requires extra memory, not in-place sort\]

**Quick Sort:**

* Worst Case : $\Theta(n^2)$ ; happens input is already sorted
* Best Case : $\Theta(nlogn)$ ; when pivot divides array in exactly half
* No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(nlogn)$ in best case
* No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

**Bubble Sort:**

* Worst Case : $\Theta(n^2)$
* Best Case : $\Theta(n)$ ; on already sorted
* No. of comparisons : $\Theta(n^2)$ in worst case & best case
* No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

**Linear Search:**

* Worst Case : $\Theta(n)$ ; search key not present or last element
* Best Case : $\Theta(1)$ ; first element
* No. of comparisons : $\Theta(n)$ in worst case & $1$ in best case

**Binary Search:**

* Worst case/Average case : $\Theta(logn)$
* Best Case : $\Theta(1)$ ; when key is middle element
* No. of comparisons : $\Theta(logn)$ in worst/average case & $1$ in best case

---

1. I have considered only basic searching & sorting algorithms.
2. It is assumed above that sorting algorithms produce output in ascending order
3. Sources : The awesome CLRS and this Wiki

# Answer
For general algorithm of bubble sort worst case comparisons are $\Theta(n^2)$ But for special case algorithm where in you add a flag to indicate that there has been a swap in previous pass. If there were no swaps then we come out of the loop since array is already sorted. In this case comparisons are $n$ not 0.

For Quick sort you have mentioned that worst case swaps are $n^2$. Well worst case scenario for quick sort is when all elements are in sorted order thus there won't be any swaps so it should be zero.
> -2 votes

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


# Question
Title: Are loop counters spatially or temporally local?
Consider this nested loop:

```
for (i=0 to n)
   for(j=0 to n)
      for (k=0 to n)
         sum := sum +k
      end for
   end for
end for

```

Do `i`,`j` and `k` have temporal or spatial locality?

I've considered `j` and `k` as temporal since they are revisited again in the loop. But I'm confused about `i` as it does not match the definitions of temporal or spatial.

# Answer
> 2 votes
A set of variables has *temporal locality* if they are accessed within a relatively short period of time. `sum`, `k` and `n` are all accessed at every iteration of the inner loop; assuming that `n` is relatively large, `i` and `j` are not accessed frequently. So `sum`, `k` and `n` are temporally local, `j` could be considered temporally local with them but `i` probably isn't.

Variables have *spatial locality* if they are stored at addresses that are close together – e.g., close enough to be in the same cache line or, at least, the same page in memory. As such, spatial locality is a property of compiled code, not source code, so it's impossible to say what variables in the code are spatially local: a stupid compiler or memory manager could scatter them to the four corners of the address space. But one would hope that temporally local variables that are accessed repeatedly would be spatially local.

# Answer
> 0 votes
Well for your example let me put it in this way, imagine you have a Cache memory and main memory. code is in main memory now. you are running this code using Temporal locality of reference when your code will run the most frequent variables that are accessed are sum,k and n. these will be in cache for longer period of time since they are accessed in most of the time in the code. it is not the case that variable i,j wont be moved to cache they will be but if they are removed from cache they wont be brought back in until they are not accessed. so in short in case of temporal locality until you don't access wont be moved to cache memory.

If you are using Spatial locality of reference as soon as you read i, all variables will be moved to cache memory since we assume that they are stored one after the other. In spatial locality reference we assume that any thing near to what we are accessing will be accessed very soon so just grab what you see near by it and move to cache. how much to move depends on architecture.

---
Tags: terminology, algorithm-analysis
---


# Question
Title: Count numbers that can be generated by flipping bits according to position intervals
We have $M$ bits. $M\le10^5$ Also we have N ranges in the form $\[L,R\]$. $N\le10^5$ We can choose any range from the given ranges and flip all bits in our number from $L$ to $R$, both inclusive. We can apply each operation any number of times and in any order. We have to calculate the number of $M$ bit numbers that can be formed thus.

for Example if $N=3$ and our ranges are : $\[0,0\]$, $\[1,1\]$, $\[2,2\]$. Now if we need to find number of three bit numbers that can be formed using the above restrictions, our answer would be 8, since we can form everything from 0 to 7.

Example 2: if we have 3 bits and two ranges $\[0,1\]$, $\[1,2\]$, we can form $4$ distinct numbers : $0 (000)$, $3 (011)$, $6 (110)$ and $5 (101)$.

I was thinking of doing something like if we could just obtain the $i^{th}$ bit as $1$ after performing some operations we could simply take $2^X$ for all such bits and that many numbers can be formed. But this approach doesn't seem to work in general.

# Answer
Hint: For given $N$ and a range $\[L,H\]$, let $v \in \mathbb{Z}\_2^N$ be the characteristic vector of $\[L,H\]$, i.e. $v\_i = 1$ if $L \leq i \leq H$ and $v\_i = 0$ otherwise. Given a list of ranges $\[L\_j,H\_j\]$ and correspond vectors $v\_j$, how can you represent the characteristic vectors of all numbers reachable by the operations you mention? What is the relevant parameter?

Another hint: What happens if all $L\_i$ are distinct? How can you handle cases in which $L\_i = L\_j$ for some $i \neq j$? Try to reduce it to the former case.
> 3 votes

---
Tags: combinatorics
---


# Question
Title: Series where each term is square of previous
The problem statement is as follows:-

> In a court case, a judge cited a court of contempt and ordered a fine of $2 for first day. On subsequent days, the fine would be equal to the square of the previous day's fine. e.g. 2, 4, 16, 256 and so on. Find out:-
>
> a) What would be the fine on day $n$?
>
> b) How many days would it take the fine to reach $D$ dollars?

A big Oh answer would be appreciated.

# Answer
> 3 votes
As you say, the fine on day $n$ is $2^{2^n-1}$. To reach $D$, you need to solve the equation $2^{2^n-1}=D$, taking $\log$ we have $2^n-1=\log D$, rearranging and taking $\log$ again we get $n=\log(\log D+1)$.

If you want the answers in Big-O notation, you have $2^{2^n-1} =O(2^{2^n})$, and for the second part, $n=O(\log\log D)$.

---
Tags: recurrence-relation
---


# Question
Title: How are statistics being applied in computer science to evaluate accuracy in research claims?
I have noticed in my short academic life that many published papers in our area sometimes do not have much rigor regarding statistics. This is not just an assumption; I have heard professors say the same.

For example, in CS disciplines I see papers being published claiming that methodology X has been observed to be effective and this is proved by ANOVA and ANCOVA, however I see no references for other researchers evaluating that the necessary constraints have been observed. It somewhat feels like as soon as some 'complex function and name' appears, then that shows the researcher is using some highly credible method and approach that 'he must know what is he doing and it is fine if he does not describe the constraints', say, for that given distribution or approach, so that the community can evaluate it.

Sometimes, there are excuses for justifying the hypothesis with such a small sample size.

My question here is thusly posed as a student of CS disciplines as an aspirant to learn more about statistics: How do computer scientists approaches statistics?

This question might seems like I am asking what I have already explained, but that is my *opinion*. I might be wrong, or I might be focusing on a group of practitioners whereas other groups of CS researchers might be doing something else that follows better practices with respect to statistics rigor.

So specifically, what I want is "Our area is or is not into statistics because of the given facts (papers example, books, or another discussion article about this are fine)". @Patrick answer is closer to this.

# Answer
As a graduate student in computer science, who has exposure to research in fields other than computer science, and whose research group works in an area of computer science where statistics can be fruitfully applied, I can offer my experience; your mileage may vary.

In general, even the most well-meaning scientific research can fail to rigorously apply statistical analysis to results, and it is my experience that this does not always preclude papers including such poorly-analyzed results from being accepted for publication. The area in which my group operates is mainly in distributed computing and high-performance computer architecture. Often, research involves experimental designs the performance of which cannot easily be understood analytically in the required detail. As such, empirical results are often used as evidence for claims.

Clearly, experiments should be design - and results analyzed - in such a way as to provide some confidence that the results are statistically significant. Most of the time, this is not done, even in some of the most important venues. When statistical analysis is applied, it is almost never rigorous in any meaningful sense; the most one typically sees (and one is glad to see it!) is that an experiment was repeated *n* times, for some arbitrarily-chosen *n*, where typically $1 \< n \< 5$. The selection of error bars (if any are indicated) seems to be mainly a matter of personal preference or taste.

In summary, no, it's not just you; and it's not just software engineering. In general, based on my experience, several areas of computing research seem to err on the side of not doing enough. Indeed, it might be even be detrimental to the viability of a submitted paper to dwell on statistical considerations. That's not to say that I find the situation satisfactory; far from it. But these *are* my impressions. For instance, you may take a look at section 5 of this paper, which was presented at Supercomputing 2011, one of the most high-profile conferences in the area of high-performance computing. Specifically, take a look at some of the discussion of results in section 5, and see whether you arrive at the same conclusions that I do about the rigor of statistical analysis of experimental results.

More generally, this shortcoming may be symptomatic of a condition in some areas of computing to publish more papers rather than fewer, to target conferences rather than journals, and to emphasize incremental progress rather than significant and fundamental improvements in understanding. You might consult this article, which provides valuable insight along these lines.
> 12 votes

# Answer
Software engineering includes many features. Two of them are human factor and quality measure.

Let’s say I want to do productivity analysis. The data collection would be hard comparing to algorithm analysis because the data is about human productivity. Also the objective measure of quality is not easy to achieve.

10 lines of code per day for an avionics system versus 150 lines of code per day for an app on smart phones, which one has higher productivity and which one has better quality? And if both claim that they are using the same methodology? Comparing them is to compare apples and oranges.

Sometimes it is hard to achieve accurate measure of code efficiency. For example, I put in a bunch of unuseful variables and lots of lines of code for those variables, say for debugging purpose. This boosts my productivity at development stage. At the end, I take out all of them and I say I improve my code to achieve efficiency.

Later on, a researcher comes in and perform efficiency analysis. He might treat the above as noises and only concentrate on the final results. Some researchers pay attention to the noises. Then you are going to see articles with different conclusions.

Statistics is supposed to be a tool to assist the researchers in finding causes of issues. Many researchers use it to draw conclusions. This is what you have observed.

---

Some remarks above might lead the OP to think that I am against the usage of stats in software engineering. If so, I'd like to make myself clear.

I am not against stats. Stats analysis can tell you X *might* be true. But, that should not be the end of the research. The next task should be to find out if X is actually true and why. This is what I believe science is about - to find the truth.

Whether or not software engineering belongs to computer science is another issue.
> 2 votes

# Answer
Statistics is *hard*, and often counter-intuitive. Besides, the urge to "do one more experiment" to see if there is an effect (and stop when it shows up) is strong, specially if the experiments are costly (time, work, not just money). Also remember that publishing a paper on how the carefully set up, long and costly experiment shows *no* statistically significant relationship tends to be impossible.

Specially in software engineering there are many uncontrollable variables. To account for them you'd need many replications of the experiment, and you get resources to do one or at best two.
> 1 votes

# Answer
> My question here is thusly posed as a student of CS disciplines as an aspirant to learn more about statistics: How do computer scientists approaches statistics?

there are several questions above & some not the same as the title question & in some ways this question has an underlying faulty premise/misconception about some lack of connection between statistics and CS. the general question is about the interface of computer science and statistics.

there is a *vast, verging on intense overlap in some areas* and it is an increasing trend with the new strongly emerging field of big data. at some schools (eg even elite "Ivy League" schools) the CS degree is tightly coupled with the mathematics and *statistics* departments and some have a *joint major*. there is a very strong interconnection in the CS/statistical field of Machine Learning. also the relatively new field of bioinformatics has very strong CS+statistical grounding.

there is an entire field Computational statistics focused on the interface!

> Computational statistics, or statistical computing, is the interface between statistics and computer science. It is the area of computational science (or scientific computing) specific to the mathematical science of statistics. This area is also developing rapidly, leading to calls that a broader concept of computing should be taught as part of general statistical education.\[1\]

yes, agreed, as pointed out in the question, there are many CS papers that dont use statistics, including situations (such as evaluating empirical experiments) where it might be even highly applicable & relevant, but exactly the same can be said of many other scientific fields, eg mathematics, and even more applied fields like physics.

there are many ways to use/apply statistics, some less rigorous than others, and not all contexts call for full application of the very advanced aspects of statistics. for example just running multiple experiments and plotting error bars for statistical deviation (or even merely *averages!*) is a basic use of statistics. more rigorous uses include hypothesis testing, but there is a general observation in the field that many scientific papers do not do rigorous hypothesis testing even where it might be applicable.

also, this question is tagged with . this was my major, and a statistics class was *required* to pass to complete this degree at my school & to get an engineering-certified major (eg ABET), this is likely the case at many other universities. if one wants more applied and rigorous CS type principles such as applications of statistics, one can go the "software-engineering" route in education.
> -3 votes

---
Tags: software-engineering, empirical-research, statistics
---


# Question
Title: How can I quantify the number of swaps required for insertion sort?
Based on the Wikipedia implementation of insertion sort:

Given an input array $A$:

```
for i ← 1 to length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1

```

is there a way to quantify how many swaps are needed to sort the input list? It's $O(n^2)$, but I want a more precise bound. A perfectly sorted array clearly needs no swaps (so insertion sort is $\Omega(n)$), while a completely reversed array requires something on the order of $n^2$ swaps, but how do we quantify the number of swaps?

# Answer
It is a classic exercise to relate the running time of insertion sort to the number of *inversions* in the input. An *inversion* is a pair of indices $i \< j$ such that $A\[i\] \> A\[j\]$. The number of comparisons made by insertion sort when there are $I$ inversions is always between $I$ and $I+n-1$.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Prove Queue Automaton is equivalent to Turing Machine
A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end.

Actually I've proved that a 2-tape Turing Machine can simulate the DQA. Now I'm proving the DQA can simulate Turing Machine TM. Let the queue store all the input and the right-end symbol is the one being read. Suppose $a$ is the right-end symbol in the queue.

For the transition $\delta(q,a)=(r,b,L)$ in TM, it's easy to simulate. Just pull $a$ and push $b$. Now the right-end symbol would be the symbol on the left of $a$. It's like move the head in TM to the left.

My problem is I cannot find a way to simulate the transition $\delta(q,a)=(r,b,R)$. Since the symbol on the right of $a$ is actually the left-end symbol, how can I let this symbol move to the right-end? I spend several hours on this and I think answers on Internet are not very clear. Could anyone give me some hint?

# Answer
> 4 votes
It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\\#$) and place it on the left of the symbol under the head:

```
queue: 0100100#1  equivalent to tape: __0100100[1]___

```

Now you pop the symbols from the right and re-push them on the left but *with one symbol of delay* (you buffer one symbol *using the internal states*). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

```
queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)
queue:  0100101#  pop:1  buf:*
queue:  *0100101  pop:#  buf:1

```

When you pop $\\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head, and you can apply the corresponding transition:

\** if the transition says to write symbol $y$ and goto to $Right$ then you push $\\#$ and the $y$ on the left of the queue.

```
 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right
 queue:  0#*0100101   pop:   buf:
 queue:   0#*010010   pop:1  buf:
 queue:    0#*01001   pop:0  buf:1
 queue:    10#*0100   pop:1  buf:0
 ...

```

Then you continue the pop-push operations until you find again the $\\#$.

\** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

```
queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left
queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left
queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right
queue:  1#10*01001   pop:   buf:
...

```

The special symbol $\*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself. And if you want to be rigorous, you should also consider the special initial case in which the queue doesn't contain the head symbol #.

# Answer
> 1 votes
How do you simulate the tape? Place end/beginning marker in the queue, and see how you handle "move past end" (basically, replace "end of tape" by "space, end of tape" and redo the move you were trying to do).

---
Tags: turing-machines, automata, simulation
---


# Question
Title: What makes it so difficult to prove P =/≠ NP? — The subset sum issue
I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to prove that P = NP.

Let's take the subset sum problem, which is NP-complete. It says that given a set such as $\\{-7, -3, -2, 5, 8\\}$, we're able to find out if there exists a subset of this set summing to zero, within exponential time (and obviously check a solution, for instance $\\{-3, -2, 5\\}$ within polynomial time).

So if someone finds an polynomial-time algorithm for this task, he'll show that P = NP, right?

EDIT: I removed:

> Assuming, that opinions whether P = NP or P ≠ NP amongst computer scientists are about 1:1 (this site claims that they're ~ 52% and ~44% respectively)...

As the guys noticed in comments, it's wrong. I should say the proven cases are like 1:1.

Okay, so it gets more intuitive now. I mean, P ≠ NP actually seems to be 'more likely now':

However, assuming that there are still, say, 5-10% of formally educated people who believes that P = NP and the cited problem is not, say, the most complex one, how is that even possible that no one of them had found a polynomial-time algorithm yet OR (maybe more likely?) no one of their opponents proved that there's no such an algorithm? Or, does it also mean that (in terms of those people's opinions, again) the 'chances' of there being such an algorithm are like 1:1, too?

From my (maybe naive) point of view, the subset sum problem seems so simple to crack – at least for advanced computer scientists.

As you're probably aware of, searching in the Net would not help me much as I just can't deeper into this problem. I've got no such mathematical knowledge to even comprehend it more.

# Answer
> 3 votes
Many simple-seeming problems turn out to have solutions that are extremely complicated and deep. That's not a bad thing, in fact it's what keeps mathematics interesting. One of the best known examples is Fermat's Last Theorem, which states that the equation $x^n+y^n=z^n$ has no solution in positive integers $x, y, z$ whenever $n\ge 3$. One could hardly ask for a simpler problem, but despite the efforts of some of the brightest mathematicians it remained unsolved for *358 years*! On the plus side, three centuries of trying (and failing) to prove Fermat's Last Theorem led to the development of a lot of what's known as algebraic number theory.

Indeed, the subset sum problem is easy to state. Finding a poly-time solution, though, has turned out to be really hard, to the extent that no one has yet been able to demonstrate one. One could say, "Okay, I'll turn the problem around and show that there is no poly-time algorithm possible." Ugh! That sounds even worse: how could one establish that among the infinitely many algorithms to solve subset sum, there are none that run in time polynomial in the length of the instance to be solved?

I don't necessarily recommend this, but you could just try inventing an algorithm of your own that always finds the correct answer to subset sum. You'll almost certainly find, as others have, that no matter how much cleverness you throw at the problem, you'll fail to come up with a "fast enough" algorithm. That, at least, should disabuse you of the notion that simple questions should have simple solutions.

---
Tags: complexity-theory, np-complete, p-vs-np
---


# Question
Title: Applications for boolean logic operations in zero-one integer linear programming (ILP)
It is nice to know that every boolean formula can be expressed by zero-one integer programming by this answered question. But are there any applications?

To be more precise: Are there papers which use the existense of zero-one integer programming for boolean operations?

# Answer
> 2 votes
Yes, there are many applications. To find some, go to that question and look through the linked and related questions on the sidebar; that will already show you several applications. Next, do a search for the search term "ILP" on this site, and browse through the search results. You will find many examples of problems that can be solved with zero-one ILP using these techniques.

# Answer
> 1 votes
Forget specific applications, and just think about what a linear program is. You're optimising (either maximising or minimising) some linear combination of variables, subject to certain linear constraints.

So embedding boolean logic in the linear program should allow you to extend this to boolean constraints as well. Rather than just finding any old assignment of truth values which satisfies the boolean expression, this gives you a natural way to find an optimal assignment, for some reasonable definition of "optimal".

Now can you think of an application?

This doesn't use the exact embedding, but Appel and George, *Optimal Spilling for CISC Machines with Few Registers* (2000) is one good example of a real-world optimisation problem based around boolean constraints and a linear objective function.

---
Tags: logic, linear-programming, applied-theory
---


# Question
Title: In a BOINC project, how are responses checked for accuracy?
More specifically, how can project administrators be sure that the answers they receive from nodes are correct and not just simple calculations performed quickly and submitted as complete work units? As various cheating scandals have shown, people are not above stooping to low levels to get to the top of project points tables...

# Answer
> 1 votes
Part of the checking that is performed by the BOINC platform to avoid cheating is to send the same work units to different users, and then verify that the results are the same.

---
Tags: distributed-systems
---


# Question
Title: What is an algorithm for what I am trying to do?
I have an equation $y=2x^4-20x^2-50x$ within a range of -4 to 6

I already have an algorithim that tell me the y value when I plug in the $x$. It simply uses a loop.

What I am trying to do is determine what will be be the y max value and what $x$ corresponds to it. Is there some sort of loop or counter I can use. I am program this on SPARC machine but any sort of pseucode loop will be appreciated.

I tried to do the following

I have a counter

# Answer
You find the local maxima and minima by taking the derivative and setting it to 0. This leaves you with a non-linear equation $f'(x)=0$ to solve.

The easiest, and most reliable, way to find the zeros of a continuous non-linear equation, $g(x)=0$, is called the Bisection Method.

Find two points $x\_-$ and $x\_+$ where $g(x\_-) \< 0$ and $g(x\_+) \> 0$. (These are particularly easy to find for odd-degree polynomials, since there will always be at least one real root.)

Now evaluate $g(x\_\star)$ where $x\_\star = (x\_- + x\_+)/2$. If $g(x\_\star) \> 0$ then let $x\_+ = x\_\star$ and repeat. Else if $g(x\_\star) \< 0$ then let $x\_- = x\_\star$ and repeat.

Because you are interested in the range \[-4,6\] you also need to evaluate $f(-4)$ and $f(6)$, because the local maxima may not be inside the range. (Your function obviously has no finite global maximum. $f(10)$ is about 18000, and grows from there and $f(-10)$ is also about 18000 and grows from there.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Is this path finding problem in a 01-matrix NP-complete?
> **The problem:**
>
> *Input*: An $n \times n$ matrix of 0's and 1's, and a position *pos* of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$)
>
> *Output*:
>
> YES if there exists a path through **adjacent** matrix entries $\dagger$, starting at *pos*, covering each matrix entry with a 1 **exactly once**, and not covering the matrix entries with a 0.
>
> NO otherwise.

$\dagger$ a matrix entry is adjacent to the one immediately to its left, to the one immediately to its right, to the one immediately upwards and the one immediately below.

---

Informally, the matrix can be seen as a labyrinth where the 0's are walls, you start somewhere, and you have to walk through the whole maze without repeating any position.

Example input:

```
1100
1100
0000
0001
Pos: (1,1)

```

Corresponding output:

```
No (because you can't reach the position (4,4))

```

---

Is this problem NP-complete? If it is, what other NP-complete problem has been reduced to it? If it isn't, what approach can I use to design an efficient algorithm?

I think this is a particular case of the hamiltonian path problem (except that you have a fixed starting point). The graph can be constructed by taking the matrix entries with 1's as vertices. 2 vertices are adjacent iff their corresponding matrix entries are adjacent. So I think that reducing this problem to the hamiltonian path problem should be easy. Of course, to prove it is NP-complete, we would have to do the reduction backwards.

# Answer
> 1 votes
Your problem is to determine if there is a Hamiltonian path in a grid graph (an induced subgraph of a rectangular grid). This is **NP**-complete: see Itai, Papadimitriou and Szwarcfiter, *Hamilton Paths in Grid Graphs* (SIAM J. Comput., 11(4):676–686, 1982) PDF.

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


# Question
Title: Logic Question - Why is This an Implication?
I have a question about predicate logic. Suppose we have the following predicates:

$\text{Study}(x,y)$: x studies y

$\text{Comp}(x)$: x is a computing student

I want to encode the following sentence in predicate logic: "Some, but not all computer students study logic."

A potential answer is:

$$\exists x(\text{Comp}(x)\land \text{Study}(x,l))\land\neg \forall x(\text{Comp}(x)\implies \text{Study}(x,l))$$

Why is there an $\implies$ and not a $\land$? Is this formulation correct?

# Answer
Because $\neg\forall x\\,(\text{Comp}(x) \wedge \text{Study}(x,l))$ means "It is not true that every student is both a computing student and studying logic." In particular, that would be true if there is at least one student who is not a computing student, regardless of whether all computing students do or do not study logic.
> 4 votes

---
Tags: logic, first-order-logic, reasoning
---


# Question
Title: How to convert a Turing Machine program to a tiling using Wang Tiles?
This is a cross-post from a post on MathSE due to lack of answers.

To illustrate my question I provide the following example.

The website Online Turing Machine provides a Turing Machine simulator. The following program adds 1 to any binary number.

```
q0,1  =>  q0,1,>
q0,0  =>  q0,0,>
q0,_  =>  q1,_,<
q1,0  =>  q3,1,>
q1,1  =>  q1,0,<
q1,_  =>  q3,1,>

```

A program line has the following format:

```
state, character read => new state, character written, direction tape

```

In the program above q0 is the initial state and q3 is the accepting state.

In Tilings and Patterns by Gruenbaum and Shephard, 11.4 "Computing By Tiles" I read that it is possible to convert any turing machine program to a tiling of the plane using Wang tiles. The book contains an example tiling which calculates the Fibonacci numbers. The procedure, recipe, to convert a Turing machine program to a set of Wang tiles is not entirely clear to me.

**Question: What is the algorithm to convert a Turing Machine program line by line to a set of tiling of the plane using Wang Tiles?** And how does it work on the Turing machine in the given example?

Update:

Image is that of a Wang tile that adds 1 to a binary: 111 + 1 = 1000 where 1 is red, 0 is cyan. Aiming to generate tiles like this from any Turing Machine. First row 111, last row 1000.

# Answer
(partial answer) via wikipedia, the conversion/reduction of TMs to Wang tiling was 1st proven in this paper, & there are possibly later simplifications:

* Berger, R. (1966). "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66 (1966). (Coins the term "Wang tiles", and demonstrates the first aperiodic set of them).
> 3 votes

---
Tags: turing-machines, simulation, computation-models, tiling
---


# Question
Title: Creating a Deterministic Push Down Automaton
I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself.

PDA for language that accepts twice as many a's as b's.

It was commented that the PDA was not deterministic. So I'm wondering what exactly makes a PDA deterministic, for example, would you remove the epsilon transitions here to make it deterministic or what?

If somebody could convert this into a deterministic PDA and explain the steps to do so, I would appreciate it, I'm pretty lost when it comes to push down automata.

# Answer
> 7 votes
Just like any automaton, a PDA is nondeterministic if (and only if) the transition relation is not a function, that is there are configurations that have multiple possible succeeding configurations. If this is the case for reachable configurations, this means that a non-deterministic automaton has inputs for which there are multiple computations.

Here, the transition $(\varepsilon, Z0/Z0)$ to state three may be taken even though the word has not been completely read, that is in configurations of the form

$\qquad (\alpha 1 \beta, Z0)$

you can either take transition $(\beta\_1, Z0/\beta\_1Z0)$ or $(\varepsilon, Z0/Z0)$ -- the automaton is non-deterministic. Of course, taking the latter always leads to rejecting the input unless $\beta = \varepsilon$, Since there is no other nondeterminism, this implies that the automaton is unambiguous.

Converting an NPDA to a DPDA is not always possible; NPDA define a properly larger language class than DPDA. Given an NPDA, checking if an equivalent DPDA exists is undecidable. And even *if* there is one (and you know that) there is no algorithm to find it. That is to say, there is no general, algorithmic technique for that part of your question.

---
Tags: automata, pushdown-automata, nondeterminism
---


# Question
Title: More than one NFA accepting a given language
While going through certain problems. it seems that more than one NFA is possible for the given language. Is it so?

For example for drawing: NFA ending with 1 where $\Sigma=\\{0,1\\}$ is

and also we can draw one without 0 from the edge P to P!

Which one should be considered "more" correct?

# Answer
> 6 votes
There are many, many different NFAs accepting a particular language, or DFAs for that matter. You can just add branches that lead into dead ends at will, for example. Or add detours that give the same result as the main road, like in your automaton adding a new state $r$, with transitions from $p$ to $r$ on 1, and then from $r$ to $r$ on 0 and 1, and finally from $r$ to $q$ on 1.

In the given case, omitting the transition from $p$ to $p$ on 0 gives another language. You should convince yourself that the modified NFA doesn't accept anything containing zeros.

# Answer
> 2 votes
There is no notion of "more correct" so your inverted commas around "more" are well placed. An analogous question would be something like, "There are many different ways of writing a given program – which is 'most' correct?"

In theoretical terms, any automaton that accepts a language is as good as any other. The existence of an automaton means the language is regular; non-existence means it isn't.

In practical terms, there may be a preference for the automaton with the least number of states, since that requires less memory to implement.

For teaching purposes, there may be a preference for automata with simple structure and states whose "function" is easily described. For example, suppose you're asked to produce an automaton for $(a+b)^\*(ab)^+$. It's much easier to describe the three-state nondeterministic automaton that "guesses" when the $(a+b)^\*$ part of the string ends and then checks that the rest of the string matches $(ab)^+$ than it is to describe the corresponding deterministic automaton.

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


# Question
Title: Showing that the entropy of i.i.d. random variables is the sum of entropies
The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\\{\sigma\_{1},...,\sigma\_{k}\\}$) is given by
$H(Y)=-\sum\limits\_{i=1}^{k}P(Y=\sigma\_{i})\\;\log(P(Y=\sigma\_{i}))$.

For a second random variable $X=X\_{1}X\_{2}...X\_{n}$, where all $X\_{i}$'s are independent and equally distributed (each $X\_{i}$ is a copy of the same random variable $Y$), the following equation is known to be true:

> $H(X)=n\cdot H(Y)$

I want to prove this simple equation, where the outcomes from $Y$ are interpreted as symbols from an alphabet $\Sigma$ and therefore $X$ is the random variable for strings of length $n$ (based on the distribution of $Y$).

It is easy to see, that $P(X=w)=P(X=w\_{1}...w\_{n})=P(X\_{1}=w\_{1})\\;\cdot\\;...\\;\cdot\\; P(X\_{n}=w\_{n})=\prod\limits\_{i=1}^{n}P(Y=w\_{i})$
... but my approach to prove $H(X)=n\cdot H(Y)$ seems to be in a dead point
(every word $w$ has the form $w=w\_{1}...w\_{n}$ with $w\_{i}\in\Sigma$ and let $\large |w|\_{\sigma\_{i}}$ be the number of occurrences of $\sigma\_{i}$ in $w$):

$H(X)=-\sum\limits\_{w\in\Sigma^{n}}P(X=w)\\;\log(P(X=w))$
$=-\sum\limits\_{w\in\Sigma^{n}}\left(\prod\limits\_{i=1}^{n}P(Y=w\_{i})\right)\\;\log\left(\prod\limits\_{i=1}^{n}P(Y=w\_{i})\right)$
$=-\sum\limits\_{w\in\Sigma^{n}}\left(\prod\limits\_{i=1}^{n}P(Y=w\_{i})\right)\left(\sum\limits\_{i=1}^{n}\log\left(P(Y=w\_{i})\right)\right)$
$=-\sum\limits\_{w\in\Sigma^{n}}\left(\prod\limits\_{i=1}^{k}P(Y=\sigma\_{i})^{\large |w|\_{\sigma\_{i}}}\right)\left(\sum\limits\_{i=1}^{k}\large |w|\_{\sigma\_{i}}\normalsize \\;\log\left(P(Y=\sigma\_{i})\right)\right)$

So, I am able to change some indices from word length to the length of the alphabet, which is used in $H(Y)$. But what now? Any help?

# Answer
Your attempt at the proof does not take into account any natural order on $\Sigma^n$. While it may still work, it seems difficult.

A much easier proof can be given by induction over $n$. The base case is trivial ($H(X)=H(Y)$) for $X=Y$. Then, denote $X=X\_1\cdots X\_n$ and $X'=X\_1\cdots X\_{n-1}$, so you have

$$H(X=w)=-\sum\_{w\in\Sigma^{n-1}}\sum\_{\sigma\in \Sigma}Pr(X=w\sigma)\log Pr(X=w\sigma)$$ $$=-\sum\_{w\in\Sigma^{n-1}}\sum\_{\sigma\in \Sigma}Pr(X'=w)Pr(Y=\sigma)\log Pr(X'=w)Pr(Y=\sigma)=$$ $$=-\sum\_{w\in\Sigma^{n-1}}Pr(X'=w)\sum\_{\sigma\in \Sigma}Pr(Y=\sigma)(\log Pr(X'=w)+\log Pr(Y=\sigma))=$$ $$=-\sum\_{w\in\Sigma^{n-1}}Pr(X'=w)\left(\sum\_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(X'=w)+\sum\_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(Y=\sigma)\right)=$$ $$=-\sum\_{w\in\Sigma^{n-1}}Pr(X'=w)\log Pr(X'=w)\sum\_{\sigma\in \Sigma}Pr(Y=\sigma)+\sum\_{w\in \Sigma^{n-1}}Pr(X'=w)\sum\_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(Y=\sigma)=$$ $$=H(X')+H(Y)=(n-1)H(Y)+H(Y)=nH(Y)$$
> 4 votes

---
Tags: information-theory, entropy
---


# Question
Title: The minimization operator is an effective operator
Assume $\\{f\_i^{(n)}\\}\_{i=0}^\infty$ is a Gödel enumeration of the $\mu$-recursive functions of $n$ arguments, such that the $S^m\_n$ theorem and the universal function theorem hold. Denote the set of (total and partial) functions $\\{f:\mathbb N^k\to\mathbb N\ \\}$ by $\mathfrak F^k$

**Definition:** We call an operator $G:\mathfrak F^n\to\mathfrak F^k$ effective, if $(\forall j\in\mathbb N)(G(f^{(n)}\_j)=f^{(k)}\_{g(j)})$ for some total recursive function $g$.

**Claim:** The minimization operator $\mu:\mathfrak F^{k+1}\to\mathfrak F^k$ defined by $$\mu(f)(\overline x)=\mu y\[f(y,\overline x)=0\]=y\iff (f(y,\overline x)=0\land(\forall i\<y) (f(i,\overline x)\>0))$$ is an effective operator.

**Question:** How can I go about proving the statement? Hints are welcome.

**Thought:** By definition the $\mu$-recursive functions are closed with respect to the $\mu$-operator. Therefore, $\mu(f^{(k+1)}\_j)=f^{(k)}\_{h(j)}$, for some unique total function $h$. But why is $h$ a computable function?

Note that I would really like to stay within the Partial Recursive Functions Formalism. Pseudo code means nothing to me. I cannot read it. I am not familiar with most of the notation from the programming world. I would also prefer not go into Register Machine Formalisms.

# Answer
It's a direct application of the smn-theorem if you don't let the currying get in your way.

Since $\mu : \mathbb{N}^{k+1} \to \mathbb{N}$ is computable (by definition), there is $i \in \mathbb{N}$ so that

$\qquad\displaystyle \mu = f^{(k+1)}\_i$.

Now the smn-theorem asserts the existence of a recursive and total $g' : \mathbb{N}^2 \to \mathbb{N}$ with

$\qquad\displaystyle f^{(k+1)}\_i(x\_0, x\_1, \dots, x\_k) = f^{k}\_{g'(i,x\_0)}(x\_1, \dots, x\_k)$

for all $(x\_0,\dots,x\_k) \in \mathbb{N}^{k+1}$. Because $i$ is fixed, we get (again via smn-theorem) a recursive and total $g : \mathbb{N} \to \mathbb{N}$ with

$\qquad \mu(f,\overline{x}) = f^{(k+1)}\_i(f,\overline{x}) = f^{k}\_{g'(i,f)}(\overline{x}) = f^{k}\_{g(f)}(\overline{x})$

for all $\overline{x} \in \mathbb{N}^k$.
> 2 votes

# Answer
The best way to solve such problems is to understand what they amount to in *real* programming code. All the stuff about Gödel encoding is very mathy and fancy but uneccessary in this day and age.

We can think of Gödel codes of $\mu$-recursive functions as source code. The fact that an enumeration satisfies the smn theorems amounts to the fact that, given the source code of a function on $k$ arguments, we can calculate the source code of the same function with one of the arguments fixed to a particular value. The utm theorem just says that there is an intepreter for the source code.

An operator $G$ is *effective* if there is a program which converts the source code of a function $f$ to the source code of $G(f)$. This program must work for all valid inputs (is total). To see that the minimization operator is effective we thus have to write a program `p` which does the following:

* Input: source code $S$ of a function $f$
* Output: source code for the function $\bar{x} \mapsto \mu \\, y \[f(y,\bar{x}) = 0\]$

Our program converts some source code to some other source code. It should not try to minimize anything, or simulate $f$, or anything like that. At this point you should stop reading and do the exercise yourself, in whatever your favorite programming language is.

---

Really, stop reading and do it yourself.

---

Here is my solution:

```
def p(k, s):
    """Convert source code s of a function in k+1 arguments to a function in k arguments which
       minimizes in the first argument. We assume that the source code s for the function
       is given in the following form (had we chosen a more decent programming language,
       we could have used anonymous functions instead):

              "def f(x0, ..., xk):
                 <body of function>
              "

       The output is given as a source code of a function in the following format:

              "def f(x1, ..., xk):
                  <body of function>
              "
    """

    # The string "x1, ..., xk"
    xs = ", ".join(["x{0}".format(k) for k in range(1,k+1)])
    # The source code s indended by 4 characters
    s4 = "\n".join("    " + l for l in s.split("\n"))
    # Now we can generate the output
    return ("""def f({0}):
{1}
    y = 0
    while True:
       if f(y, {0}) == 0: return y
       else: y = y + 1
    """.format(xs, s4))

```

Our program `p` corresponds to a primitive recursive function because it contains only for loops with prescribed bounds (the `while True` is *not* part of our program because it is inside a string and so is really part of the source code that our program outputs).

Let us try an example:

```
## We look for the least y such that x <= 2 * y.

s = """def f(y,x):
   return (1 if x <= 2 * y else 0)
"""

t = p(1,s)

print(t)

```

The output printed is:

```
def f(x1):
    def f(y,x):
       return (1 if x <= 2 * y else 0)

    y = 0
    while True:
       if f(y, x1) == 0: return y
       else: y = y + 1

```
> 3 votes

---
Tags: computability, recursion, mu-calculus
---


title: Path finding under constraints

text:
# Question
Title: Path finding under constraints
Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the minimal weight of all paths from $b$ to $a$. How do you find two paths $l\_1,l\_2$ such that:

1. $l\_1=(a,v\_1,..,v\_n,b)$
2. $l\_2=(b,u\_1,..,u\_m,a)$
3. $w(l\_1) + w(l\_2)\leq 1.1(\alpha + \beta)$
4. From all the paths holding the above, bring to minimum the sum of weights on the edges $e=(u,v)\in l\_1$ such that $(v,u)\in l\_2$

Less formally, I want to find a path starting at $a$ ending with $b$ and returning to $a$ such that the path is not too long (at most 10% longer than the optimal solution) and tries to use as much as different roads as possible (if it used some road $(x,y)$ when going from $a$ to $b$ , it would try to avoid the road $(y,x)$ when going back to $a$)

# Answer
> 2 votes
One solution would be to use integer linear programming (ILP). This is not guaranteed to have a polynomial worst-case running time (ILP can take exponential time), but ILP solvers are pretty impressive, and for reasonable-sized graphs, this might just be an effective solution in practice.

For each edge $e \in E$, let $x\_e,y\_e,z\_e$ be integer variables with the constraint $0 \le x\_e \le 1$, $0 \le y\_e \le 1$, $0 \le z\_e \le 1$ (so that $x\_e,y\_ez\_e$ are forced to be either 0 or 1). The meaning of $x\_e=1$ is that $e$ is part of the path $l\_1$, and the meaning of $y\_e=1$ is that $e$ is part of $l\_2$, and the meaning of $z\_e$ is that $e$ is part of both $l\_1$ and $l\_2$.

Now introduce the following constraints:

* $\sum\_{(a,v) \in E} x\_{(a,v)} = 1$ (i.e., at least one of the edges out of $a$ must be selected in $l\_1$).
* $\sum\_{(v,b) \in E} x\_{(v,b)} = 1$ (i.e., $l\_1$ contains an edge into $b$).
* For each vertex $v \in V \setminus \\{a,b\\}$, $\sum\_{(u,v) \in E} x\_{(u,v)} = \sum\_{(v,w) \in E} x\_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
* $\sum\_{(b,v) \in E} y\_{(b,v)} = 1$ (i.e., $l\_2$ contains an edge out of $b$).
* $\sum\_{(v,a) \in E} y\_{(v,a)} = 1$ (i.e., $l\_1$ contains an edge into $a$).
* For each vertex $v \in V \setminus \\{a,b\\}$, $\sum\_{(u,v) \in E} y\_{(u,v)} = \sum\_{(v,w) \in E} y\_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
* $\sum\_{e \in E} w(e) (x\_e + y\_e) \le 1.1 (\alpha+\beta)$ (condition 3 in the question holds).
* For each $e \in E$, $z\_e \ge x\_e + y\_{-e} - 1$, $z\_e \le x\_e$, and $z\_e \le y\_{-e}$, where $-e$ is the reversal of the edge $e$ (i.e., if $e=(u,v)$, then $-e=(v,u)$). (This enforces that $z\_e = 1$ if and only if $x\_e = y\_{-e} = 1$.)

Now minimize $\sum\_{e \in E} w(e) z\_e$. This will minimize the total weight of the edges that are common to both $l\_1$ and $l\_2$.

# Answer
> -2 votes
You can use A\* to find the least cost path from a-\>b and b-\>a, and combine those paths.

To prefer unused edges when finding the path from b-\>a, you can increase the weight/cost of edges that were traversed in the path from a-\>b.

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


# Question
Title: Are there regular languages between every two non-regular languages?
I have a question regarding regular languages. Given that $L\_1$ and $L\_2$ are non-regular languages, can a regular language $L$ exist so it is a subset of $L\_2$ and $L\_1$ subset of $L$?

To be more specific:

$\qquad L\_1 \subset L \subset L\_2$

for $L\_1, L\_2$ non-regular Languages.

# Answer
**Hint**. Given any sets $A, B, C$ we have $A \cap C \subset C \subset B \cup C$.
> 3 votes

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


# Question
Title: Is equivalence of CFGs decidable for finite sets of grammars?
Is there a way to show that for all *finite* sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G\_1, G\_2 \in S$, we have that $M(G1,G2)$ terminates and answer yes if and only if $L(G\_1)=L(G\_2)$? Is that even true?

I know that this problem is in general undecidable, but I also know that a finite set is in general decidable. I just can't figure out how to determine the answer for this problem.

# Answer
A problem is decidable if there is a TM which decides instances of the problem.

Given two arbitrary CFGs $G\_1$ and $G\_2$, we know this for certain: either $L(G\_1) = L(G\_2)$, or $L(G\_1) \neq L(G\_2)$. Consider the first case: a TM that accepts on the input $(G\_1, G\_2)$ correctly decides this problem. Consider the second case: a TM that rejects on the input $(G\_1, G\_2)$ would be correct in that case.

Now, consider a finite set of grammars $\\{G\_1, G\_2, ..., G\_n\\}$. For any two grammars $G\_i$ and $G\_j$ in this set, we know that either $L(G\_i) = L(G\_j)$ or $L(G\_i) \neq L(G\_j)$.

Consider the following TMs:

TM #1:

```
if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then accept

```

TM #2:

```
if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then reject

```

...

TM #N

```
if input is (G_1, G_1) then reject
if input is (G_1, G_2) then reject
...
if input is (G_n, G_n) then reject

```

Each TM can either accept or reject for each of the $n^2$ (ordered) inputs; so there are $N = 2^{n^2}$ different TMs (as many as binary strings of length $n^2$).

One of these TMs is guaranteed to correctly decide your problem. I can't tell you which one, but one of these gives all the correct answers. Since there is a TM for your problem, it's decidable.
> 8 votes

# Answer
It is undecidable if two grammars generate the same language (see here), so this (more general) question is undecidable too.
> -1 votes

---
Tags: computability, undecidability
---


title: Which Type of Grammar is this?

text:
# Question
Title: Which Type of Grammar is this?
I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the parse table it had conflicts. Am I doing some thing wrong or is the answer given wrong?

My texbook defines:

> For LL(1) Grammar if there is left recursion or left factoring then that grammar is not LL(1) grammar if this applies to this grammar then it is not a LL(1) grammar

$E \to E+T \mid E$

$T \to T$#$F \mid F$

$F \to (E) \mid i$

I also have one more question: "Is there a Grammar which can be LL(1) but not LALR(1)"

# Answer
> 0 votes
There is left recursion in the grammar, so it isn't $LL(1)$.

The set of $LL(1)$ grammars is a proper subset of the $LR(1)$ grammars, see for example this summary, which incidentally also shows that $LL(1)$ isn't a subset of $LR(0)$. The first part is is intuitively easy to see, the $LL(k)$ parser has to decide looking only at the $k$ first symbols; the $LR(k)$ has the whole left hand side (and $k$ extra symbols) at its disposal.

# Answer
> -1 votes
If you want to test the grammer is LL(1).

First if you have left recursion it must be solve it .

Then the new output you want to calculate the first and follow to draw the table .

Then check if you don't have multiple entry in the table so this grammer is LL(1) else is not LL(1). Note in your grammer may be have error in writting it. plz check it.

**E→E+T∣T**

**T→T#F∣F**

**F→(E)∣i**

---
Tags: formal-grammars, compilers, parsing
---


title: Do Kleene star and complement commute?

text:
# Question
Title: Do Kleene star and complement commute?
I am having hard time solving the following problem.

> Are there any languages for which $$ \overline{L^\*} = (\overline{L})^\* $$

Assuming $\emptyset^\* = \emptyset$, if I consider $\Sigma = \\{a\\}$ and L = $\Sigma^\*$, I get that $L^\* = L$ and that $\overline{L^\*} = \emptyset$. For the right side I get $\overline{L} = \emptyset$ and $(\overline{L})^\* = \emptyset$. Thus, both sides are equal.

Is it true that $\emptyset^\* = \emptyset$?

# Answer
> 7 votes
Hint: The star of a language always contains the empty string. The complement of a language containing the empty string never does. With that in mind, look at the left and the right hand sides of your proposed equality.

# Answer
> 0 votes
Hint: I can think of an example in which both sides are $\emptyset$, and another one in which both are $\Sigma^\*$.

(This hint works only if you allow $\emptyset^\* = \emptyset$. That's the case if you define $L^\* = \bigcup\_{x \in L} x^\*$. The usual definition is $L^\* = \sum\_{n \geq 0} L^n$.)

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


# Question
Title: What type of math classes are good to take for computer science majors?
I am an undergraduate computer science student at Cal Poly (SLO) and I have some flexibility in which math courses I can take, but I don't know which math courses would be most beneficial. I have already taken a statistics/probability course and Calculus 3. My options are pretty flexible for a Mathematics/Statistics elective. What type of math is most useful to know for the field of computer science? I still don't know what type of career I would like, so general answers are okay; or some specific classes for specific career paths would be great too. Thanks!

# Answer
Discrete maths will be the first priority.

then number theory.
> 0 votes

---
Tags: education
---


# Question
Title: What Do Logical Operators In a Grammar Mean?
Is there a way to figure out what the following CFG accepts?

$\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid\\; \thicksim p \end{align}$

I'm confused by the boolean algebra symbols. I know the first is S or T, the second is T and F and the third is not p but I'm not sure how they affect the grammar itself.

# Answer
> 5 votes
A grammar *generates* a language, it doesn't accept it. Automata accept languages.

The whole point of gramars is that they are easily able to generate quite complex languages. Even regular languages (accepted by finite automata or denoted by regular expressions) can be very hard to describe in simple terms.

In this case, the grammar generates (a subset of) logical formulas, with connectives and ($\wedge$), or ($\vee$), and not ($\thicksim$).

# Answer
> -1 votes
This accepts all the expressions involving 1 variable, sum of products (minterms) expressions.

This grammar makes the priority of $\thicksim$ greater than $\wedge$ which is in turn greater than $\vee$, in this grammar, because if you generate the parse tree, $\thicksim$ will be at the leaves.

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


title: Appropriate minor to go with CS major

text:
# Question
Title: Appropriate minor to go with CS major
I thought this would be the best place for a question like this. Anyway, I was wondering what minor would go well with a Computer Science degree. I was considering a minor in math but I am not entirely sure if that could help out or not. I am currently a second semester freshman and I suppose that this is the best/latest time to decide. Open to many suggestions.

# Answer
> 1 votes
It depends on what you plan to do with your CS degree. If you plan to continue to graduate school, a math minor would certainly be helpful. If your interests turn out to be in hardware, and the courses are available, some courses in electrical engineering would be appropriate, as a minor or not.

On the other hand, if you plan to go straight to Real Life$^{\text{TM}}$, then the possible enhancements widen considerably. Math is still a strong contender, of course, but if, for example, you see yourself in, say, the IT department in banking or finance, a strong background in economics would also serve you well. If you are of an artistic bent and see yourself working for Pixar, a CS major and an art minor wouldn't hurt. These days, so many businesses are in some way or another computational in part, you should really be asking yourself "What do I like to do?" and then tailor your non-CS courses accordingly.

If you go the RL$^{\text{TM}}$ route, my experience with recruiters is that I've stopped asking "what courses should we offer our students to best prepare our graduates for work in your company?" because the answers are almost always "You're doing fine with your courses, but what we really want is people with an adequate technical background who can express their ideas orally and in writing and who have some idea about how the world works". Unless you're a *really* good writer and speaker, take some courses in writing and oral communication---it will be time well spent. If you go that way, get as broad an education as possible, since you'll eventually be making policy decisions for your company, rather than writing programs.

Finally, be open to all possibilities, since you can't know what opportunities that might open. A number of years ago, I heard from a CS major I had taught who had become a successful rodeo clown. Did he use his major? Nope. Was he happy with his life? It certainly appeared so. The single most important lesson I teach my students is, get a job you love, then you'll never have to "work" a day in your life. Best of luck.

# Answer
> 0 votes
This may depend upon your interests in CS itself.

* if you want to work in Theory, math is interesting
* if you want to work in Cryptography, you may want number theory or real analysis
* if you want to work on NLP or Computational linguistics, you may want to have linguistics
* if Game Theory , econ is cool
* $\vdots$

You see where I am going with this, right? So, basically your options are almost endless ...

---
Tags: education
---


# Question
Title: Why is log(n/p) asymptotically less than log(n)/log(p)
I'm trying to figure out which is better asymptotic complexity, $O(\log{\frac{n}{p}})$ or $O\left(\frac{\log{n}}{\log{p}}\right)$. $p$ is the amount of parallelism (i.e. number of cores), and $n$ is the problem size. When I plot them in Grapher.app with any constant value for $p$, the first looks better:

But when I try to work out the math it doesn't seem right:

$$ O(\log{\frac{n}{p}}) = O(\log{n} - \log{p}) $$

$O\left(\frac{\log{n}}{\log{p}}\right)$ seems like a better bound than the above since it divides by $\log{p}$ instead of just subtracting it. What am I missing?

# Answer
> 10 votes
I assume that $p \> 1$ (which is equivalent to $\log p \> 0$, otherwise we have negative-valued functions which are meaningless as complexity measures.

**For a given $p$**, $O\left(\frac{\log n}{\log p}\right) = O(\log n)$ since big oh isn't affected by multiplication by a positive constant.
$\log \frac{n}{p} = \log n - \log p$. Since $\log p = o(\log n)$, $O\left(\log \frac{n}{p}\right) = O(\log n)$.

So up to big-oh complexity (or big-theta, for the same reasons), these two classes are the same.

Your diagram doesn't show a visual difference: you need to bring the two curves to the same scale. One is $a \log n$ for some constant $a \> 0$, the other is $\log n + b$ for some constant $b$.

If you want to study the variation in $p$, then $O$ or $\Theta$ with respect to the variable $n$ are not good ways of modeling the complexity of your problem. You need more precise approximations that treat multiplicative constants as relevant. The complexity in $p$ is probably relevant to your problem, and is very different. I'm not familiar enouhg with parallelism to know whether it's the right measure to use here, this could warrant a separate question (with more information about what you're modeling). You're going to need express the complexity in terms of $n$ and $p$, and look at how *the variation in $p$* (not the complexity itself) behaves for large $n$.

---
Tags: asymptotics
---


title: VC dimension of complement

text:
# Question
Title: VC dimension of complement
Let $C\subseteq 2^X$ be a concept class over $X$ and let $\bar{C}:=\\{X\setminus c\mid c\in C\\}$ be the complement. Show that $VCdim(C)=VCdim(\bar{C})$.

Proof:

Let $d:=VC\_{dim}(C)$, then there exists $S\subseteq X$, $|S|=d$, s.t. $S$ is shattered by $C$.

Let $d':=VC\_{dim}(\bar{C})$, then there exists $S'\subseteq X$, $|S'|=d'$, s.t. $S'$ is shattered by $C$.

Show that $d\leq d'$ and $d' \leq d$. I know that a set $S$ is shattered by $C$ iff $\Pi\_C(S):=\\{c\cap S\mid c\in C\\}=2^S$, but I have no clue how to show the two sides. Can someone help me with that?

# Answer
First, observe that it is enough to prove that $d\le d'$. Then, the converse inequality follows from the fact that $\overline{\overline{C}}=C$, and by applying the initial argument to $\overline{C}$.

To prove the claim, we actually prove something stronger: we prove that if $C$ shatters $S$, then $\overline{C}$ also shatters $S$.

Let $S$ be a set that is shattered by $C$, and consider $\Pi\_{\overline{C}}(S)$. Let $T\subseteq S$, then there exists $c\in C$ such that $c\cap S=S\setminus T$ (since every subset of $S$ can be reached this way). Let $c'=X\setminus c\in \overline{C}$, then $c'\cup c=X$. Thus, $c'\cap S=T$. Therefore, $\Pi\_{C}(S)\subseteq\Pi\_{\overline{C}}(S)$. Applying the same argument to $\overline{C}$, we get $\Pi\_{\overline{C}}(S)\subseteq \Pi\_{\overline{\overline{C}}}(S)=\Pi\_{C}(S)$, and thus we have the equality we wanted, and we conclude the claim.
> 2 votes

---
Tags: machine-learning, vc-dimension
---


# Question
Title: What is the result of multiplying O(n) and Ω(n)?
If $f(x) = \Omega(n)$ and $g(x)= O(n)$, what would be the order of growth of $f(x) \cdot g(x)$ ?

First I figured it should $\Theta(n)$ , as two extremes would cancel each other and the order of growth will be same as $n$

But, where I came across this question, the answer given was $\Omega(n)$, and no proof was mentioned. Well, I didn't understand why, but intuitively I convinced myself as "you can't know for sure the upper limit of growth for $f(x) \cdot g(x)$ so you can't say it's $O(n)$, but you can be sure that it won't be lower than $\Omega(n)$"

Can someone help me in understanding this, in a more believable way?

# Answer
> 10 votes
Basically, without further information you know nothing about the asymptotic growth of $f \cdot g$.

Let's unfold the definitions:

$\qquad f \in \Omega(n) \implies f(n) \leq cn$ and

$\qquad g \in O(n) \implies g(n) \geq dn$

for some $c,d \in \mathbb{N}$ and $n$ greater than some constant.

Now it's clear that you get no bound on $g \cdot f$; you have no upper bound for one factor and no lower for the other. In fact, you can get arbitrarily slowly and fast growing results:

* For $f : n \mapsto n$ and $g\_k : n \mapsto n^{-k}$, we get $f \cdot g\_k : n \mapsto n^{-k+1}$. Note that the induced sequence of functions is properly decreasing in terms of asymptotic growth.
* For $f\_k : n \mapsto n^k$ and $g : n \mapsto n$, we get $f\_k \cdot g : n \mapsto n^{k+1}$. Note that the induced sequence of functions is properly increasing in terms of asymptotic growth.

If you restrict yourself to (eventually) non-decreasing functions -- that is $f,g \in \Omega(1)$ -- you get one of the missing bounds and thus $f \cdot g \in \Omega(n)$.

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


# Question
Title: Why can't you write the 2-paths problem as a max-flow problem?
This is a follow-up question to this. Consider the 2-paths problem:

> Given a directed graph $D=(V,A)$ and pairs of vertices $(s\_1,t\_1)$ and $(s\_2,t\_2)$, are there paths $P\_1 = (s\_1,\dots, t\_1)$ and $P\_2=(s\_2,\dots,t\_2)$ such that $P\_1$ and $P\_2$ are vertex-disjoint?

This problem has been shown to be NP-complete (references here). This struck me as unusual, because there seems to be a natural way to formulate this as a max flow problem:

* Add new vertices $s$ and $t$ to $D$.
* Add arcs $(s,s\_1),(s,s\_2),(t\_1,t),(t\_2,t)$.
* Let all vertices have capacity one (besides $s$ and $t$).

It seems to me that the max $s-t$ flow of this new graph (call it $D'$) should be two iff $D$ has those desired paths $P\_1$ and $P\_2$. Surely there must be some mistake here, because this seems to imply that an NP-complete problem can be solved in polytime. Where is the mistake?

# Answer
The proposed construction does find two vertex disjoint paths from s to t (if they exist). HOWEVER, the paths might be $P\_1=(s\_1,…,t\_2)$ and $P\_2=(s\_2,…,t\_1)$, which is not what we want.
> 8 votes

---
Tags: complexity-theory, graphs, network-flow
---


# Question
Title: Proving that {0^{2^k}} is not regular with the Myhill-Nerode theorem
My language is the repetition of 0 to a length that's a power of 2:

$L = \\{ 0^k \ni k=2^n, n \geq 1 \\}$

I want to know how to prove that this language is not regular. I have attempted the proof below, but think it may be incorrect due to my potentially wrong assumption that the Myhill-Nerode theorem allows me to break up a regular language in the following way:

$j, p = 2^h$ for 2 distinct values of $h$, $h \in \mathbb{N}$:

$a = 0^{j/2}$

$b = 0^{p/2}$

$c = 0^{j/2}$

$ac = 0^{j/2}0^{j/2} = 0^j$ is in my language since $j$ is of the form $2^n$

$bc = 0^{p/2}0^{j/2}$ is not guaranteed to be in my language for every $p$ and $j$, since $j \ne p$

Thus my language must not be regular since $ac$ is in it but $bc$ is not.

Did I apply the Myhill-Nerode correctly? If not, what do I need to change in my proof?

# Answer
> 2 votes
I'm not sure I follow your proof. To use Myhill-Nerode, you need to show that the number of equivalence classes under the indistinguishability relation $I\_L$ is infinite. What follows is how I would approach this; you're probably best qualified to compare this to what you've done to see whether your proof is relying on the same assumptions, making the same points, and reaching the same conclusions for the same reasons.

Consider the string $w = 0^{2^n + 1}$. This is not a string in $L$. To create a string that is in $L$ by appending to this string, we can append $0^{2^n-1}$, of length $s = 2^n - 1$. There is no other string $s'$ shorter than $s$ such that $ws' \in L$.

Therefore, we immediately have that $w = 0^{2^n + 1}$ and $w' = 0^{2^m + 1}$, $n \neq m$, are distinguishable strings with respect to the indistinguishability relation $I\_L$; they belong to different equivalence classes, since the set of strings we can append to $w$ to get a string in $L$ is different from the set of strings we can append to $w'$ to get a string in $L$ (recall that the shortest string in the first set is of length $2^n - 1$, whereas the shortest string in the second set has length $2^m - 1$).

Since $i$ and $j$ vary freely over the natural numbers, we must have an infinite number of equivalence classes over $I\_L$. Since the Myhill-Nerode theorem tells us that regular languages must have only a finite number of such equivalence classes (remember, each of these equivalence classes corresponds to a single state in a minimized DFA for the language), this language must not be regular.

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


# Question
Title: Possible to construct a probabilistic halting problem solver?
I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions.

So I was thinking, much in the way that some primality testers are probabilistic(they give you yes or no but have a chance to be wrong). Would it be possible to build a probabilistic halting problem solver? One that reports within a certain degree of error, whether a problem halts or not?

# Answer
It depends what you mean by "probabilistic". There are at least two interpretations. First, the algorithm has some probability of success for *every* input. Second, the algorithm succeeds on a certain *fraction* of inputs.

For the first interpretation, it is easy to rule out such an algorithm: probabilistic computation can be simulated (inefficiently but effectively) using deterministic computation, by trying all possible coin tosses.

For the second interpretation, we will have to work a bit harder. Suppose that your algorithm is guaranteed to work with an asymptotic success probability of $2/3$. That means that the fraction of inputs in $\[1,N\]$ for which it gives the correct answer is some $p\_N \to 2/3$. Now suppose you're interested in a certain program $P$. It seems that under a reasonable encoding of programs, you would be able to come up with a long stretch $\[M,10M\]$ (say) of programs equivalent to $P$. By taking $M$ large enough, it should be the case that by taking the majority vote on the answer of a "probabilistic" algorithm on all of these equivalent programs, you will be able to ascertain whether $P$ halts or not. This rules out even this interpretation of a "probabilistic" algorithm.
> 6 votes

---
Tags: probability-theory, halting-problem, probabilistic-algorithms
---


title: Why the given NFA is not possible

text:
# Question
Title: Why the given NFA is not possible
I am trying to construct NFA for all languages ending in 00.

I got this

and this

First one I could convert to DFA by subset construction and I got the correct DFA. For the second one I got the DFA by subset construction, but it is not the correct one since it couldn't accept strings like 100.

Is this beacuse, there is no non determinism in the second NFA? Or what is the general rule in drawing an NFA? We could always provide some form of non determinism?

# Answer
> 4 votes
The second NFA doesn't accept $100$. Make sure that you understand when an NFA accepts a given word. In this case, your NFA gets stuck at the very first character, since there is no transition labelled $1$ from the initial state.

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


title: Wave propagation in digital image

text:
# Question
Title: Wave propagation in digital image
I believe the following question in summary is: How to approximate Euclidean distance in a digital plane?

> When a pebble falls on a calm surface of water a circular wave propagates. I want to color the pixels with time to show this effect. So I discretize the time and in each time step, starting from the center, I color one pixel away in all directions. But this gives a square wave. I guess what is wrong is that I have approximated the Euclidean distance with the infinity norm.

How do I approximate Euclidean distance to get the a circular wave on the pixels? I don't want to measure the distance from each pixel to the center in each time slot. That will be very heavy. I am looking for a simple algorithm like coloring the next pixel adjacent to last colored pixel.

# Answer
Here's a trick that video game designers have used for years. A computationally cheaper approximation to Euclidean distance between two points $(x\_1, y\_1)$ and $(x\_2, y\_2)$ is to use $$ d=\max(|x\_1-x\_2|, |y\_1-y\_2|)+\min(|x\_1-x\_2|, |y\_1-y\_2|)/2 $$ The relative error between this and the Euclidean distance is no more than 11.8%, which might be good enough for your purposes.
> 4 votes

---
Tags: algorithms, computational-geometry, approximation
---


# Question
Title: Induction proof, base case not working but induction step works?
$1+3+5+...+(2n+3)=n^2+4n$

For this series using induction proof.

Base case 1,2,3,.. not working. But induction step works well.

Base case is not given in question.

# Answer
> 0 votes
First of all, the right hand side should be $n^2+4n+4$

You can find the generalized term for the left hand side is $2n-1$. Therefore,

$1+3+5+...+(2n-1)+(2n+1)+(2n+3)=n^2+4n+4$, which gives you:

$1+3+5+...+(2n-1)=n^2$.

Then you can apply the mathematical induction to prove it holds for every positive integer $n$.

# Answer
> 2 votes
A proof by induction requires that the base case holds and that the induction step works. If either doesn't work, then the proof is not valid.

It can definitely happen that the induction step works, but not the base case. If that never happened, we'd define induction without the base case.

Example: consider the property “for any integer $n$, in every heap of $n$ pebbles, there are $n+1$ pebbles”.

Proof of the induction step: Suppose that for some integer $n$, in every heap of $n$ pebbles, there are $n+1$ pebbles. The induction step requires us to prove that in every heap of $n+1$ pebbles, there are $(n+1)+1$ pebbles. To prove this, consider any heap of $n+1$ pebbles. Take one pebble from the heap; the heap now contains $n$ pebbles. By the induction hypothesis, that heap contains $n+1$ pebble. Put back the pebble that was taken off; the heap now contains $n+2$ pebbles, Q.E.D.

Of course the base case fails: in a heap of $0$ pebbles, there is not one pebble.

In the case of the summation $1+3+5+\ldots+(2n+3) \stackrel{?}{=} n^2 + 4n$, the inductive case consists of adding $2n+5$ on the left-hand side and $((n+1)^2 + 4(n+1)) - (n^2 + 4n) = 2n+4$ on the right-hand side. This in fact shows that the difference between the left-hand series and the right-hand series is a constant. To show that the two series are equal, you would need to prove that this constant is zero; this is what the base case would establish. However the base case is $1 + 3 \stackrel{?}{=} 0$; this shows that the difference between the left-hand series and the right-hand series is $4$. This gives you the correct formula: $1 + 3 + \ldots + (2n+3) = n^2 + 4n + 4$ (or equivalently $1 + 3 + \ldots + (2n+3) = (n+1)^2$), which you can prove by induction.

---
Tags: proof-techniques, induction
---


title: Total ordering of sets of fixed size

text:
# Question
Title: Total ordering of sets of fixed size
I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them):

```
{0, 1, 2} < {0, 1, 3}
          < {0, 2, 3}
          < {1, 2, 3}
          < {0, 1, 4}
          < {0, 2, 4}
          < {1, 2, 4}
          < {0, 3, 4}
          < {1, 3, 4}
          < {2, 3, 4}
          < {0, 1, 5}
          < ...

```

The sets are generated recursively: increase the highest number and reset all the other elements to the lowest possible numbers, then apply this algorithm recursively to the remaining numbers.

The position within this ordering is given by:

```
C(x[1], 1) + C(x[2], 2) + C(x[3], 3) + ...

```

where `x[i]` is the `i`-th element in the *sorted* set and `C(n, k)` is the binomial coefficient.

Does anyone know of a name for this kind of total ordering? Furthermore, what other common ways are there to order sets containing a fixed number of totally ordered elements?

# Answer
> 6 votes
This is just lexicographical order, but left to right (not right to left as usual).

---
Tags: combinatorics, sets, order-theory
---


# Question
Title: Why ⊢ for affirmative predicates and ⊨ for ¬negations?
I read a book which says that in Predicate Calculus, syntactic theorem proving is identical (complete and sound) with semantic entailment and this is very useful because it is easier to prove positive witnesses in natural deduction whereas when you seem to fail you better switch to semantic account to demonstrate a counter-example.

Particularly Logic in computer science says

> to show that Γ ⊢ψ is valid, we need to provide a proof of ψ from Γ. Yet, how can we show that ψ is not a consequence of Γ? Intuitively, this is harder; how can you possibly show that there is no proof of something? You would have to consider every ‘candidate’ proof and show it is not one. Thus, proof theory gives a ‘positive’ characterisation of the logic; it provides convincing evidence for assertions like ‘Γ ⊢ ψ is valid,’ but it is not very useful for establishing evidence for assertions of the form ‘Γ ⊢ φ is not valid.’
>
> Semantics, on the other hand, works in the opposite way. To show that ψ is not a consequence of Γ is the ‘easy’ bit: find a model in which all φ\_i are true, but ψ isn’t. Showing that ψ is a consequence of Γ, on the other hand, is harder in principle. For propositional logic, you need to show that every valuation (an assignment of truth values to all atoms involved) that makes all φ\_i true also makes ψ true. If there is a small number of valuations, this is not so bad. However, when we look at predicate logic, we will find that there are infinitely many valuations, called 'models' from hereon, to consider. Thus, in semantics we have a ‘negative’ characterisation of the logic. We find establishing assertions of the form ‘Γ ⊭ ψ’ (ψ is not a semantic entailment of all formulas in Γ) easier than establishing ‘Γ ⊨ ψ’(ψ is a semantic entailment of Γ), for in the former case we need only talk about one model, whereas in the latter we potentially have to talk about infinitely many. All this goes to show that it is important to study both proof theory and semantics. For example, if you are trying to show that ψ is not a consequence of Γ and you have a hard time doing that, you might want to change your strategy for a while by trying to prove the validity of Γ ⊢ ψ. If you find a proof, you know for sure that ψ is a consequence of Γ. If you can’t find a proof, then your attempts at proving it often provide insights which lead you to the construction of a counter example. The fact that proof theory and semantics for predicate logic are equivalent is amazing, but it does not stop them having separate roles in logic, each meriting close study.

I was sure that we can prove the opposite by proving ⊢ ¬ψ and wondered why do we need the entailment. Now I see that validity of the opposite has nothing to do with validity of affirmative statement. Thanks. What we need is the satisfaction of the ¬ψ, which says that there is a counterexample. We do not need the validity of ¬ψ. But why semantics instead of proof? Do you say that semantics is in patrimony of satisfaction whereas proof theory is dedicated to validity?

I have mistakenly thought that not being able to prove ψ means that ψ is absurd and, thus, you can prove ¬ψ. But, this seems not to be the case.

# Answer
> 15 votes
The answer is really in the first paragraph of the quoted text, so what I'm about to attempt is really a rephrasing of that.

Remember that $\Gamma \vdash \psi$ means that there exists a *formal* proof of $\psi$ (in the system from $\Gamma$ blah blah blah). That is, there's some way, starting from the axioms, to syntactically manipulate the symbols according to the rules of the system to end up with $\psi$.

On the other hand, $\Gamma \models \psi$ is a statement about the *semantics* of the system, i.e. the interpretation of what the symbols \`mean', so $\Gamma \models \psi$ when there's no interpretation that renders all of $\Gamma$ true and $\psi$ false.

So, back to the question. When we want to show that $\Gamma \vdash \psi$ is valid, a formal proof is very nice, because it has no dependence on the meaning (semantics) of the symbols, it is simply a consequence of the rules of the system. On the other hand, if we suspect $\Gamma \vdash \psi$ is not valid, it's very hard to give a formal proof - you would have to show that every possible route to a formal proof doesn't work, i.e. that no matter what potentially-very-convoluted order you apply the rules of the system in, starting from the members of $\Gamma$, you can't get to $\psi$. Just to reiterate, you would effectively have to consider every possible proof, and show that it didn't work.

Semantic entailment kind of works the other way around. To show that $\Gamma \models \psi$ is *not* valid, \`all' we need to find is some interpretation such that everything in $\Gamma$ is true, but $\psi$ is false - i.e. we just have to find that one counterexample. Showing that $\Gamma \models \psi$ *is* valid is the part that requires lots of cases - we have to show that $\psi$ holds for *every* interpretation for which everything in $\Gamma$ also holds.

---
Tags: terminology, logic, first-order-logic
---


title: Decidability Problem

text:
# Question
Title: Decidability Problem
given a turing machine M over the input alphabet $\Sigma $ , any state q of M and a word w $\epsilon\Sigma $\* , does the computation of M on w visit the state q ?

Is this problem decidable ?

# Answer
Let P(M,q,w) = "the computation of M on w visit q"

If we suppose P décidable, then the problem P' defined as :

P'(M,w) = w \in L(M)

is decidable.

Proof : This a decision procedure for P'. Let M be a machine and w a word. For each accepting state q of M, we run P(M,q,w). If the answer is "yes" for some q, we return "yes". Otherwise, we return "no".

Since it is well known that P' isn't decidable (Rice theorem), we conclude P isn't decidable.
> 3 votes

---
Tags: turing-machines, automata
---