# Question
Title: Intersection of context free with regular languages
The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context free but not regular.

The language generated by such an intersection has strings that are accepted both by a PDA *and* a DFA. Since it is accepted by a DFA, shouldn't it be a regular language? Plus, if the intersection is regular, it also implies context free, since all regular languages are also context free.

Can someone explain to me why the language obtained by such an intersection is not regular?

# Answer
If $L$ is context-free then there is a PDA $\mathscr{P}$ that accepts it. If $M$ is regular then there is a DFA $\mathscr{F}$ that accepts it. The intersection language consists of the words that are recognized by $\mathscr{P}$ and $\mathscr{F}$.

Any word that is in the intersection is accepted by $\mathscr{F}$, but not all words that are accepted by $\mathscr{F}$ are in the intersection: only those that are also accepted by $\mathscr{P}$.

The cross product proof consists of constructing an automaton $\mathscr{P} \otimes \mathscr{F}$ which contains the mechanics of both $\mathscr{P}$ and $\mathscr{F}$, and which accepts only words for which both sides accept. The cross-product automaton is a PDA (and therefore the recognized language is context-free) — intuitively, because the cross product with an $n$-state DFA consists of taking $n$ copies of $\mathscr{P}$ and adding $(q,a,\[q\])$ arrows between matching states in $\mathscr{P}$ where the DFA has $a$ arrows. The result is not a finite automaton in general (not even a non-deterministic one) because the $\mathscr{P}$ part relies on the stack and this reliance does not go away in $\mathscr{P} \otimes \mathscr{F}$ in general.

A trivial example is that $\mathscr{A}^\*$ is regular, and if $L$ is context-free but not regular then $L \cap \mathscr{A}^\* = L$ is context-free but not regular.
> 21 votes

---
Tags: regular-languages, context-free, finite-automata, formal-grammars
---


# Question
Title: does a DFA converted from NFA always contain 2^Q states?
when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states? or if some sub-sets are unreachable then they are not included in it?

# Answer
As per suggestion, I'm posting this as an answer.

Any DFA already is an NFA. Determinizing it will not change the number of states it has, so there are NFA that do not have fewer states than the equivalent minimal DFA.

Maybe also a non-trivial example:

Take the NFA with states $\\{q\_o, q\_1\\}$, alphabet $\Sigma = \\{a\\}$, initial state $q\_0$, transitions $\delta(q\_0, a) = \\{q\_0,q\_1\\}$ and final state $q\_1$. It generates the same language as the DFA with the same set of states and alphabet, but transitions $\delta(q\_0,a)=q\_1$ and $\delta(q\_1,a)=q\_1$.
> 6 votes

# Answer
The answer to the question depends on its precise meaning.

> when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always yield a deterministic automaton of that size even when the original automaton is deterministic.

> or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached). (PS. I forgot to mark the final states in the gray part)
> 6 votes

# Answer
this is a theoretical question under study/research by some with some related research literature. a general way to study this question is in the form, given particular NFAs, how big are the corresponding (minimized) DFAs? this is sometimes referred to as "blowup" when the corresponding DFA has many more states than the NFA. can something be said about the form of NFAs that do or dont "blow up"? note that NFAs can be given in non-minimized form. there is some complexity theoretical study of this question. see eg:

see eg lemma 1 that shows that there exist NFA-DFA pairs for which "exponential blowup" is guaranteed.

another way to view this is in the opposite direction, that a NFA can be like a compression algorithm for a DFA because for some DFAs an equivalent NFA is much smaller, and the NFA-DFA conversion can be like a decompression algorithm. however searching for the smallest NFA equivalent to a DFA is PSpace complete.

there is also a natural empirical approach to study this question by creating random NFAs and seeing how they "blow up" when converted to DFAs, and finding parameters of the NFA that contribute to that "blow up".
> 0 votes

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


# Question
Title: Prove the existence of regular $C$ so that: $A \prec C \prec B $
Given $A,B$ regular languages with $A \prec B$. Prove the existence of $C\in L\_{\text{regular}}$ so that: $A \prec C \prec B$.

Here, $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite.

I tried to go for: $C=\overline{B} \cup A$ and some other options but it didn't work out.

# Answer
Hint: Note that $B \setminus A$ is regular by closure properties of $\mathsf{REG}$.

> Since $B \setminus A$ is also infinite, you can find an infinite language $D \in \mathsf{REG}$ so that $D \prec B \setminus A$.
> 5 votes

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


# Question
Title: Is there a DFA with $k+2$ states which its reverse has $2^k$ states
I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states.
I am trying to find an example of such a DFA, any help?

# Answer
> 5 votes
This is related to the usual NFA to DFA complexity problem. Strings over $\\{a,b\\}$ such that the $k$-th letter is an $a$.

Precise bounds for a general alphabet $\Sigma$ are given by @AntonTrunov. Then again the minimal DFA for the language has $k+2$ states, whereas the reversal needs $\frac{|\Sigma|^k-1}{|\Sigma|-1}+1$ states, assuming $|\Sigma|\>1$.

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


title: Decision Problem Algorithm

text:
# Question
Title: Decision Problem Algorithm
I have a question: Every Decision problem has a method, turing machine or algorithm to solve it? If the answer is not, Could show me any example?

# Answer
> 3 votes
A decision problem has a yes/no answer. If such a problem has an algorithm then it is called "decidable". So you are looking for undecidable problems. Happy googling.

---
Tags: decision-problem
---


# Question
Title: In cache-oblivious algorithms, how is recursive reduction of data performed?
From wikipedia:

"Typically, a cache-oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into cache, regardless of the cache size."

(Is this recursive subdivision manual, or automated? Assuming automated...)

In what way must one produce code in order for it to be suitable for reduction to a cache-oblivious form? Does this rely on the specific implementation of recursive reduction applicable in one's given case?

Another way of putting the question is, would I need to write my code in a special way in order for some automated parser to run through the code and optimise it for cache-oblivious access?

P.S. I'm trying to get a handle on how to approach writing code for practical optimisation using the methods noted in the literature.

# Answer
> 1 votes
From the paper entitled "Cache-Oblivious Mesh Layouts" (Yoon et al):

> The cache miss ratio function (CMRF), pl, is a function that relates the cache miss ratio to an edge span, l. The CMRF always lies within the interval \[0;1\]; it is exactly 0 when there are no cache misses, and equals 1 when every access results in a cache miss. We alter the layouts using a local permutation that reorders a small subset of the vertices. The local permutation changes the edge span of edges that are incident to the affected vertices (see Fig. 3).

The data granularity is repeatedly reduced in software until the "atoms" are small enough to fit cache. The lower bound on data structure granularity is reached as soon as the cache miss ratio reaches zero: beyond this point, further reduction becomes unnecessary. For any given target environment, at runtime, we proceed to reduce the size of data set atoms until they are small enough that the miss ratio reaches zero.

This (often recursive) reduction / linearisation is explored in the MIT OCW lessons on Cache Oblivious algorithms (this lesson and the following one).

Perhaps other approaches exist(?), but it makes sense to me that an algorithm oblivious to block size `B` would use this sort of approach, in general.

# Answer
> 0 votes
Usually it is in the form of a space filling curve to store the data.

Say you have a table with both SSN and Birthday fields. Storing the data in either order would result in bad cache behavior for queries depending on the other field.

The solution to get cache oblivious queries is to store the data in a z-curve, http://en.wikipedia.org/wiki/Z-order\_curve I.e. sort the data on both SSN for your X dimension and on Birthday for your Y dimension and store it in Z order.

Great talk by Kmett a few weeks ago on using this technique for real world data sets.

---
Tags: cpu-cache
---


title: 3-sat to 2-sat reduction

text:
# Question
Title: 3-sat to 2-sat reduction
It is known that 3-SAT belong to - NP-Complete complexity problems, while 2-SAT belong to  as there is known polynomial solution to it.

So you can state that there is no such reduction from **3-SAT** to **2-SAT** unless $P=NP$.

I am looking for strong proof for this state, regardless NP belong to P or not.

# Answer
> 11 votes
You can prove it by contradiction:

Suppose that $P \neq NP$ and there is a polynomial-time reduction from 3-SAT to 2-SAT; then 2-SAT is NP-complete, but 2-SAT is also solvable in polynomial time, so for all decision problems $A \in NP$ you can decide $x \in A$ reducing $x$ to the corresponding 2-SAT instance in polynomial time and solve it in polynomial time (and the total time is still polynomial); so $A \in P$ and hence $NP \subseteq P$. But we also have $P \subseteq NP$, so $P = NP$ which is a contradiction. :-)

# Answer
> 1 votes
one could provably use 2SAT to solve 3SAT problems, ie a *reduction*, its just that there is not a *P-time/space* reduction unless P=NP. in other words, converting 3SAT to 2SAT, or reducing 3SAT instance $A$ to 2SAT instance $B$, is indeed possible *(using extra 2SAT variables and clauses!)*, but all known techniques lead to an "exponential blowup" in the size of $B$ wrt $A$ (ie *space* which also implies *time*). this shows how important it is to measure *time/space* requirements of a reduction and in fact there are many different ways to measure the complexity of a reduction. P-Time reductions are just more basic/common but many more complex "reduction complexities" are studied. so in this case in fact a *P-time* reduction from 3SAT to 2SAT exists *iff* P=NP...

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


# Question
Title: Non-uniform random distribution: How do I get a random between 100 and 180 that is on average close to 120? (like in a Gaussian distribution)
Presume I have the following case:

* int value `a`
* int value `b`, for which `a < b`
* int value i, for which `a <= i < b`
* I need an int value `x`, for which `a <= x < b`, randomly chosen, according to a non-uniform distribution: the distribution should follow a bell curve which is centered around `i`.

In Java, I have the following methods available on `java.util.Random`:

* `nextInt(int m)`: int between `0` and `m`
* `nextDouble()`: double between `0.0` and `1.0`
* `nextGaussian()`: double between `-Infinity` and `+Infinity`, usually close to `0.0`.

How do I build such a non-uniform distribution from these building blocks? How do I reliably and efficiently transform `nextGaussian()` into `nextGaussian(a, b, i)`? The part I am struggling with is to enforce that x is selected between a and b (without doing a trial-and-error).

# Answer
I would generate a beta distribution, and then expand to the desired range and round to the nearest integer.

A beta distribution on the 0-1 scale has two parameters: $Beta(a,b)$. $Beta(1,1)$ is simply a flat uniform. You want $a$ and $b$ to be \> 1 or it won't have a central peak. The mean is $a/(a+b)$, and the mode (peak) is $(a-1)/(a+b-2)$.

The larger $a$ and $b$ are, the more "peaked" the distribution is.

Here's how to generate it from uniform random numbers if $a$ and $b$ are integers:

First, here's how you generate a Gamma variate $Gamma(1,a)$.

```
double Gamma1(int n){
  double sum = 0;
  for (int i = 0; i < n; i++){
    sum += -log(getUniform());
  }
  return sum;
}

```

Then

```
double Beta(int a, int b){
  double x = Gamma1(a);
  double y = Gamma1(b);
  return x/(x+y);
}

```

Then for your problem, you have a span from A to B with mode at I. Then the distance from A to I is fraction $(I-A)/(B-A)$, so that is the mode of the distribution. Then decide how large you want $a+b$ to be, the more the sharper. You might start with 10, call it $n$. Then calculate $$a = (I-A)/(B-A)\*(n-2)+1$$ and use the nearest integer value for $a$, and of course $b=n-a$.

Then all you gotta do is calculate

```
A + (B-A)*Beta(a,b)

```

and round to the nearest integer.

It sounds like your requirements are pretty flexible, so this should be good enough.

Anyway, look up *Beta distribution*.

EDIT: Another way that might be simpler: Use *order statistics*. Generate $n$ uniforms, sort them, and then choose the $a$th one, and scale that.
> 5 votes

# Answer
Your problem is rather vague: "bell curve" and "centered around i" are not well defined.

One possible recipe is to generate a truncated gaussian: define `s= min(b-i,i-a)/c` where `c` is a free parameter (suggested values: \[1,3\] range), generate a gaussian with mean `i` and standard deviation `s` \- and round it to the nearest integer. If the value falls outside the \[a,b\] range, try again.

Related.
> 5 votes

# Answer
Use the alias method. There's a fairly elaborate description by Keith Schwarz, which there is no reason to repeat here. Instead, I'll explain what the final algorithm looks like.

Before describing the algorithm, let me explain the data you need to come up with. You need to decide on a probability distribution over the set $\\{100,\ldots,180\\}$. That is, you need to decide on numbers $p\_{100},\ldots,p\_{180}$ such that the probability that your random number is $i \in \\{100,\ldots,180\\}$ equals $p\_i$.

Given the $p\_i$, you can construct another array $q\_{100},\ldots,q\_{180} \in \[0,1\]$ and two integer arrays $a\_{100},b\_{100},\ldots,a\_{180},b\_{180} \in \\{100,\ldots,180\\}$ such that the following function samples the distribution $p\_i$:

1. Sample uniformly a number $t \in \\{100,\ldots,180\\}$ and a real $\theta \in \[0,1\]$.
2. If $\theta \< q\_t$ then return $a\_t$, otherwise return $b\_t$.

Keith Schwarz's essay explains how to generate the arrays $q\_i,a\_i,b\_i$ (he uses different letters; look under the section *The Alias Method*). The essay gives several algorithms for generating these arrays; in your case the range $\\{100,\ldots,180\\}$ is very small, so you can use whichever you prefer.
> 5 votes

---
Tags: randomness
---


# Question
Title: What is the complexity of this bubble sort algorithm?
I have been doing a little reading up on bubble sort and have read on wikipedia that it's complexity is measured as $\Theta(n^2)$

This bubble sort however is slightly more efficient. I thought this would be the best place to ask how I would work out this particular implementations complexity seeing that the number of iterations in the inner loop is reduced with each pass.

```
for (top = items.Length; top > 0; top--)
            {
                for (low = 0, high = 1; high < top; low++, high++)
                {
                    if (items[low].CompareTo(items[high]) > 0)
                    {
                        tmp = items[high];
                        items[high] = items[low];
                        items[low] = tmp;
                    }
                }
            }

```

# Answer
> 3 votes
The inner loop is executed $(n-1) + (n-2) + (n-3) + \dots + 0 = \tfrac{1}{2}n(n-1) = \Theta(n^2)$ times.

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


title: Converting English into Logic

text:
# Question
Title: Converting English into Logic
I'm learning about Logic; I've devised a few sentences to convert into logic to test myself and see if i've grasped the topic. It would be of great help if you could tell me if i'm doing it right!

* Every student who likes chocolate is smart:

(Every student) (who likes chocolate) (is smart)

∀x ∈D, \[Like (Student (x), chocolate) → Smart(x)\]

* There exists a barber that shaves all men who do not shave themselves.

(There exists a barber) (that shaves all men) (if and only if they do not shave themselves)

∃x ∈D, \[Shaves (x, ∀y) → Shave (y, y)\]

Thank you

# Answer
> 2 votes
These are both wrong, as they don't obey the syntactic rules of first-order logic. The rules are:

* if $P$ is an $n$-ary predicate and $x\_1, \dots, x\_n$ are variables, then $P(x\_1, \dots, x\_n)$ is a formula;
* if $\varphi$ and $\psi$ are formulas, then $\neg \varphi$, $\varphi\wedge\psi$ and $\varphi\vee\psi$ are formulas;
* if $\varphi$ is a formula and $x$ is a variable, then $\exists x\\,\varphi$ and $\forall x\\,\varphi$ are formulas;
* nothing else is a formula.

(If you like, you can say that $\varphi\rightarrow\psi$ and $\varphi \leftrightarrow \psi$ are formulas, or you can say that they're just abbreviations for $\neg\varphi\vee\psi$ and $(\neg\varphi\vee\psi)\wedge(\varphi\vee\neg\psi)$, respectively.)

There's often more than one way of translating any English-language statement into a first-order sentence. Decide what your domain is going to be and the rest will follow.

**Every student who likes chocolate is smart.** Here, you have several choices of domain, such as the following.

* Domain is the set of all students: $\forall x\\,\big(\mathrm{LikesChoc}(x)\rightarrow\mathrm{Smart}(x)\big)$. Since everything in the domain is a student, the variable $x$ can only be a student so you don't need a predicate to say that.
* Domain is, say, the set of all people: $\forall x\\,\big(\big(\mathrm{Student}(x) \wedge \mathrm{LikesChoc}(x)\big)\rightarrow \mathrm{Smart}(x)\big)$. The domain now includes things that aren't students, so we need to enforce that with a predicate. A professor who likes chocolate isn't necessarily smart.
* Domain is, say, the set of all people and all foods. $$\forall x\\,\big(\big(\mathrm{Student}(x) \wedge \exists y\\,\big(\mathrm{Chocolate}(y) \wedge \mathrm{Likes}(x,y)\big)\big)\rightarrow \mathrm{Smart}(x)\big).$$ That is, for every entity $x$, if $x$ is a student and there is a thing $y$ that is chocolate and is liked by the student $x$, then $x$ is smart. I've assumed that "likes chocolate" means "likes at least one thing that is chocolate"; you could interpret it to mean "likes all things that are chocolate", and you can probably figure out how to change the formula to reflect that.

**There exists a barber who shaves all men if, and only if, they do not shave themselves.** I'll let you have another go at this. Try taking the domain to be the set of men, with a unary predicate that says who's a barber and a binary predicate (as you have), that says who shaves whom.

---
Tags: formal-languages, logic
---


# Question
Title: Is an $\mathcal{O}(n\times \text{Number of clusters})$ clustering algorithm useful?
I am a physicist, with little formal training in computer science - please don't assume I know even obvious things about computer science!

Within the context of data analysis, I was interested in identifying clusters within a $d$-dimensional list of $n$ data-points, for which the dimensionality $d$ could be $\sim100$, whilst the number of data-points could be $\sim 1,000,000$, or perhaps more.

I wanted the points with a cluster to be close together, with distance measured in the Euclidean manner, $$ d(\vec x,\vec y) = \sqrt{\sum\_{i=1}^d (x\_i - y\_i)^2} $$ As long as the clustering was reasonably accurate, I wasn't bothered if the exactly correct result was obtained. i.e. if of my $\sim1,000,000$, $\sim1,000$ points were wrongly categorized, it wouldn't matter much.

I have written a short algorithm that can perform typically at $\mathcal{O}(n)$ (from trials of up to $n\sim5,000,000$ and some theoretical analysis) and worst-case $\mathcal{O}(n^2)$ (from my theoretical evaluation of the algorithm). The nature of the algorithm sometimes (but not always) avoids the so-called chaining problem in clustering, where dissimilar clusters are chained together because they have a few data-points that are close.

The complexity is, however, sensitive to the *a priori* unknown number of clusters in the data-set. The typical complexity is, in fact, $\mathcal{O}(n\times c)$, with $c$ the number of clusters.

Is that better than currently published algorithms? I know naively it is a $\mathcal{O}(n^3)$ problem. I have read of SLINK, that optimizes the complexitiy to $\mathcal{O}(n^2)$. If so, is my algorithm useful? Or do the major uses of clustering algorithms require exact solutions?

In real applications is $c\propto n$?, such that my algorithm has no advantage. My naive feeling is that for real problems, the number of "interesting" clusters (i.e. not including noise) is a property of the physical system/situation being investigated, and is in fact a constant, with no significant dependence on $n$, in which case my algorithm looks useful.

# Answer
> 3 votes
To answer your last question: In real problems, the number of clusters $c$ is usually much less than $n$.

To compare to other algorithms, the running time of a naive implementation of the standard $k$-means algorithm is $O(ncdt)$ (here your $c$ is often called $k$, so $c=k$, and $t$ is the number of iterations needed for $k$-means to converge; $t$ is often much smaller than $n$ and roughly a small constant, but certainly not always). There are ways to speed it up further. It tends to be very fast in practice.

For high-dimension spaces, such as you are working in, one can also apply various dimension-reduction techniques on all the values, and then do cluster the reduced-dimension values. This sometimes gives additional performance improvements.

To answer your first question: We can't tell you whether your algorithm is useful if you don't show us the algorithm. Sorry, but that question just isn't well-suited for this site. Some questions aren't, no matter how much you'd love to know the answer.

Perhaps you'd like to ask a new question about what is the state of the art in clustering for Euclidean metrics, for some class of parameters and some distribution on the inputs. Except... make sure you go do your research first. There's a *lot* that has been written on the subject of clustering, so go read about standard clustering algorithms first, and then make sure to tell us what research you've done when you ask the new question. (In fact, you probably should have done that for this question, too...)

---
Tags: algorithms, complexity-theory, cluster
---


title: PSPACE and NP complexity

text:
# Question
Title: PSPACE and NP complexity
I'm reading a definition of PSPACE and say: are the decision problems solvable in polynomial space on a Deterministic Turing Machine. My question is: Why NP is in PSPACE?. I have a doubt beccause for example a SAT problem is solvable in Non-Deterministic Turing Machine and SAT $\in NP$ and not in $P$.

# Answer
NP is a complexity class with constraints on time, whilst PSPACE is a complexity class with constraints on space. The difference between time and space is (in this case) simple: Space can be reused, whilst Time cannot. A Space-bounded machine can run for as long as it wants (as long as it terminates).

Therefore we can construct a PSPACE-Machine that solves SAT: The machine simply tries every solution.
> 7 votes

---
Tags: complexity-theory
---


# Question
Title: Is there such a thing as partial reduction?
I am trying to reduce `3-sat` to `2-sat`. With my reduction, I can find one assignment that satisfies them both, but there are some assignments that satisfy only the `3-sat`.

Does it make my reduction invalid? Is `3-sat` required to be equal-satisfiable to `2-sat` to call it a reduction?

# Answer
> 2 votes
For a reduction $f:\Sigma^{\ast}\_{\Pi\_{1}}\rightarrow \Sigma^{\ast}\_{\Pi\_{2}}$ from language $\Pi\_{1}$ to $\Pi\_{2}$ to be valid you have to prove that if $I\in \Pi\_{1}$ then $f(I) \in \Pi\_{2}$ and that if $f(I) \in \Pi\_{2}$ then $I\in \Pi\_{1}$.

Mathematically, you don't have to show how to get the solution of one from the other, just that if a solution for one exists, then a solution for the other has to as well (in both directions).

Practically of course, a reduction normally has a constructive way of doing this, i.e. if someone gave you the solution for either $I$ or $f(I)$, you would be able to produce the solution for the other.

Now in your specific case, what you would need to show is that, given any 3-SAT instance, *if* there's a satisfying assignment for the 3-SAT instance, then there's a satisfying assignment for the 2-SAT instance it maps to and vice versa. However I don't see how you can say you've found an assignment for the formulae - the reduction should work for every possible 3-SAT instance (that's the whole point), so there's no way you can know enough about the input to solve it, because it's not a specific, concrete formula.

Or to put it another way, if what you've got is a conversion between a specific boolean formula in 3-CNF to a specific boolean formula in 2-CNF, then you don't have a reduction from 3-SAT to 2-SAT, you only have a mapping between two particular formulae.

Lastly, attempting this reduction doesn't seem productive. This reduction cannot be polynomial-time computable unless $P=NP$. If it is only exponential-time computable, it's possible, but useless because there's a trivial reduction, you can simply solve 3-SAT in that amount of time, there's no need to convert it to a 2-SAT instance then solve that instead.

# Answer
> 5 votes
We went through this yesterday. The only property required for a reduction from 3SAT to 2SAT is that it maps satisfiable 3CNF formulas to satisfiable 2CNF formulas, and unsatisfiable 3CNF formulas to unsatisfiable 2CNF formulas. There is no other requirement. The formulas do not have to be related in any other way. They don't have to have the same truth table or even the same variables. If the 3CNF formula does happen to have the same variables as the 2CNF formula it's mapped to, there is no requirement whatsoever that an assignment that satisfies the first must satisfy the second, or *vice-versa*. The *only* requirement is that, if there is some way of making the 3CNF formula true, there must be some way of making the resulting 2CNF formula true; and if there is no way of making the 3CNF formula true, there must also be no way of making the 2CNF formula true.

---
Tags: satisfiability, 3-sat
---


# Question
Title: Turing machine that accepts language with more a's than b's
I am doing an assignment for my 1st year langauges and automata class. I have been having trouble with the last question which is this: Create a Turing machine that acccepts more a's than b's. I think I am supposed to pair the a's and b's together and then do some more but I can't wrap my head around it. Would help greatly if someone can post the algorithm and explain a little.

# Answer
> 5 votes
Sit before a big empty sheet of paper. Write down a sequence of a's and b's. Now mechanically check whether that string should be accepted. You cannot use counting, that would be requiring an infinite number of "states" inside your head. You can however use additional symols. A striked out b is just a new symbol that is written on the tape.

Turn your intuition into an algorithm. First informally, that is what Karolis has done. Then add information on how to implement this on a Turing tape. What direction is the head moving? Where will it stop? Then translate the whiles and untils into states and transitions (sort of goto-programming, which is improper unless you are programming a TM).

If you are a CS student, then you can do these steps. You can program. No matter whether it is C++, assembler, or Turing. That is just details.

# Answer
> 1 votes
Erase one `a`, erase one `b`, repeat until you can't. Then see whether `a`s or `b`s remain.

# Answer
> 1 votes
When I was a TA for a course on this stuff, I always recommended students think about it in terms of how you'd recognize patterns of colored marbles. This problem becomes: how do you recognize a row of marbles with more red marbles than blue marbles?

There are lots of approaches to such a problem. You could first count the red marbles, and then count the blue marbles. If you're allowed to give a multi-tape TM for this problem, this is a pretty straightforward solution:

```
while not at the end of the tape do

    if marble is red then
        write a symbol to the red auxiliary tape
        move the red auxiliary tape head to the right

    if marble is blue then
        write a symbol to the blue auxiliary tape
        move the blue auxiliary tape head to the right

    move the input tape head to the right

rewind the red tape to the front
rewind the blue tape head to the front

until you reach the end of the red tape do

    move the red tape head to the right
    move the blue tape head to the right

    if at the end of the blue tape and not at the end of the red tape then
        return Accepted

return Rejected

```

If you'd rather have a single tape solution, other procedures might lend themselves better to this problem. How else might you tell whether you have more blue or red marbles? As another answer points out, you can remove one blue and one red marble from the row of marbles, and repeat until you run out of one color of marble. This looks something like this:

```
while true do // forever

    enter the green state

    while not at the end of the tape do

        move the tape head right

        if in the green state and marble is blue then
            enter red state
            replace with green marble

        else if in the green state and marble is red then
            enter blue state
            replace with green marble

        else if in the red state and marble is red then
            enter black state
            replace with green marble

        else if in the blue state and marble is blue then
            enter black state
            replace with green marble

    if in the red or green states then
        // red state means we needed a red and didn't find one; #red < #blue
        // green state means that we removed all marbles and
        // had as many red as blue; #red = #blue
        return Rejected

    else if in the blue state then
        // blue state means we needed a blue and didn't find one; #red > #blue
        return Accepted

    else
        // in the black state, so we removed a red and a blue;
        // there may still be marbles to remove, so we start over.
        rewind the tape head to the beginning

```

Are there other possibilities? Sure there are. You could first sort the marbles to make it easier to find pairs, for instance. Remember: as far as we know, human beings can't do anything computationally more powerful than what a TM can do. That means that if you can answer this question for an arbitrary sequence of marbles, so can a Turing machine :)

---
Tags: decision-problem
---


# Question
Title: Undergraduate Computer Science Textbooks
What books would you recommend for someone starting B.Sc in Computer Science?

My Personal Info:
I am currently looking at B.Sc in Computer Science (Games), which is computer science, accept for the last year which is tailored more towards game dev.

I have a fair bit of programming experience with Unity and other things. But as far as CS goes, have little to no experience. I have just finished reading 'Introduction to Computation and Programming Using Python'. But am after something more in-depth and maths based.

My maths experience is quite poor which concerns me, as I have only studied maths up to GCSE level. (GCSE = English, there is no American equivalent. Taken at age 16)

Understanding CS is a broad topic, I was just looking for some reading that could introduce me to some key ideas that could be covered in an undergraduate course at uni.

Thanks for your time,
Magnus :)

# Answer
> 1 votes
Since you like to work through books, meaning you will spend a lot of time with one book and dig into the details using the book, I would recommend that your next book be

Introduction to algorithms by Cormen

I don't have this book as it didn't exist when I went to school but learning algorithms and data structures is where you will start at the University level once you have one programming language learned.

This is the kind of book that once you put it on your bookshelf and you will keep grabbing again and again for the rest of your life if you continue to program.

I know you asked about math, but if you can do problem solving, and converting word problems to math, then learning the math you need for programming is not something to worry about. In math you take word problems and convert them into the language of math, with programming you take word problems and convert them into algorithms and data structures. The thinking is the basically the same, one produces an abstract result and the other a program that can be run on a computer.

---
Tags: books
---


title: sorting stone Problem

text:
# Question
Title: sorting stone Problem
My friend asked this problem recently & am not sure which sorting to use for this kind of problem:-

There are 20 stones of different heights. Each stone is so heavy, we need to sort the stones such that smallest stones are to left and highest to right. As stones are heavy make algorithm which moves stone least distance possible

Which sorting method suits this kind of problem?

# Answer
> 4 votes
Original question.

> Could Any one provide a better solution for this?

I didn't see any solution provided, so that is not a valid question. Just pointing out that we expect an effort to be made by you on solving your problem before we put in an effort to help you.

Revised question.

> Which sorting method suits this kind of problem?

If I understand this correctly, it is not the choice of a sort algorithm that is important but getting the least number of moves that is important.

So first you can choose any sort method and find the correct order of the stones.

Now knowing the unsorted order and the sorted order, find the least number of moves. Since I will take it that there is a place off to the side that you can place one stone, it should take no more than a maximum of n+1 moves to sort all of the stones.

If that is not the kind of answer you expected, then you need to add more info to the question.

# Answer
> 1 votes
I'll be very interested to see a real answer for this. This is a tough problem.

I propose that we first figure out the sorted order, which we can do without touching the stones. Now, consider the worst case: the stones are in reverse-sorted order. The minimum distance required to move the stones to the correct positions is greater than $d(n-1) + d(n-2) + ... + d(n/2-1) + ... + d(n-2) + d(n-1)$ which is going to be $O(n^2)$ in the number of stones to sort. There is no sorting algorithm that will move stones such that the worst-case efficiency is any better than quadratic (under some assumptions, see below).

Given that, consider the dumbest algorithm imaginable:

1. Figure out the sorted order
2. Slide stones up, over, then up, one at a time, to put them in sorted order two squares above the original row.
3. Slide each stone down two squares.

Here, the horizontal sliding distance is optimal (assuming stones must return to the original row; if this is not actually required, the problem becomes significantly more interesting). We pay a tax of 4 moves per stone, $O(n)$ overhead, which is eaten by the $O(n^2)$ term in the worst case. The extra distance for moving vertically is $8rn$, or $80$ squares for the $n=20$ case, where the minimal distance in the worst case is at least about $380$. The number of squares would be $4000$ for the $n=1000$ case, where the minimal distance in the worst case is about $999,000$.

It seems likely that any workable algorithm (that returns stones to the original row, at least) is going to need to pay a tax of at least $\pi r - 2r$, or about $1.14r$, for round stones of cross-sectional radius $r$ that can rotate around each other, or $s$ for square stones of cross-sectional side $s$ that slide around each other on a grid.

There are some heuristics you can use to make the runtimes better in some cases, but I doubt whether there's a method to get around the $O(n^2)$ required for horizontal distances (unless we're allowed to line the stones up somewhere else, in which case this becomes more challenging).

(If the question is about finding a real procedure that gets the vertical move tax down as close to optimal as possible, that's something we can also discuss, but it will be useful to frame the question in those terms if that's the case. Even the dumb algorithm above can be modified so that in cases other than the worst, performance is significantly better).

---
Tags: sorting
---


title: Monte-Carlo algorithm for clustering

text:
# Question
Title: Monte-Carlo algorithm for clustering
I have written an algorithm for clustering data-points with their nearest neighbours with a Euclidean distance metric. I estimate its complexity to be $\mathcal{O}(n \times k)$ for $n$ data-points with $k$ genuine clusters. The dimension $d$ of the data results in $\mathcal{O}(e^d)$ complexity, though I believe this can be mitigated.

The algorithm is Monte-Carlo, resulting in an approximate solution. In pseudo-code, for `data` transformed to a unit hypercube:

```
radius = 0.15 # This should be fine-tuned for problem.
mode_number = 0 # Label for mode currently being investigated.

while length(data) > 0:

    mode_number += 1
    branching = True
    point = data[0] # i.e. first data point.

    while branching:
        within_radius = [] # Make this list empty.
        for item in data:
            if Euclidean_Distance(item,point) < radius:
                within_radius += point # List of points within a sphere.

        if length(within_radius) == 0:
            branching = False
            continue

        point = Pick_Random_From(within_radius) # Next point.
        data = data.Remove_From_Data(within_radius) # Remove neighbouring points from data.
        mode[mode_number] += within_radius # Add points to mode.

```

Although the `for item in data` loop contributes a complexity $\times$ `length(data)` each pass, `length(data)` shrinks rapidly, resulting in only $\times n$ complexity. In fact, the `length(data)` shrinks linearly with iteration (with a saw-tooth behaviour), e.g.

where branch is incremented every time `while branching` is passed, and number of deleted is the number of points removed at that pass of `while branching`. That result is from 3 Gaussians with 1000 points sampled from each Gaussian. My code identified six modes:

```
Modes: 6
Mode 5 , points: 1000
Mode 3 , points: 932
Mode 0 , points: 829
Mode 1 , points: 168
Mode 4 , points: 68
Mode 2 , points: 2

```

though only three substantial, which wasn't too far off.

The algorithm starts at a point, finds its nearby neighbours, and deletes them from the data list, and repeats from a point within those nearest neighbours. If a point has no nearby neighbours, it begins a new mode. If the data-points are spread in many modes, the algorithm requires more iterations to clear all the modes, resulting in $\times k$ complexity.

The dimension of the data limits performance. In higher dimensions of space, points are more "spread-out", e.g. a sphere radius $r$ takes up an $(r/R)^d$ fraction of the space, which shrinks exponentially with increasing $d$. This, I think, could be mitigated somewhat by increasing `radius = 0.15` in my algorithm. This is justifiable - with larger $d$, more of the space in a unit hypercube is "around the edges".

So overall I estimate complexity: $\mathcal{O}(n\times k\times e^d)$. Is my analysis reasonable? Is the working of the algorithm clear?

# Answer
> 2 votes
I suspect this clustering algorithm is going to give a poor quality clustering. The cluster heads are chosen just about arbitrarily (randomly, essentially) and then points are assigned to a cluster if they are near a cluster head or near some other randomly chosen points in the cluster. The whole algorithm looks unprincipled and I have serious doubts about the quality of the clustering it will produce.

Of course, if the clustering is of low quality, then it just doesn't matter what the running time is. I can suggest an *extremely* fast algorithm if you don't care about the quality of its output....

As far as running time, it will depend upon the distribution of the input points. If the input points are distributed uniformly across the input space, then I would expect that each iteration of the inner loop will remove roughly a $0.15^d$ fraction of the input points. This suggests that you'll need to do about $1/0.15^d \approx 2^{2.7 d}$ iterations. Each iteration takes about $O(n)$ distance computations, and each distance computation takes $O(d)$ steps, so I'd expect the running time to be something like $O(n d 2^{2.7d})$. That's dominated by the exponential factor, so the worst-case running time estimate is very bad, in high dimensions (e.g., $d \approx 100$). Welcome to the curse of dimensionality.

This algorithm does not look promising to me. Of course, before drawing any serious conclusions, you'd need to do a serious evaluation of both its running time and the quality of its clustering, on relevant input distributions, as compared to other standard clustering algorithms. So, if you want to seriously pursue this direction, you need to start studying the state of the art and work on performing such a careful evaluation. But personally, I think your time would be better spent by starting to look at what's available in the literature and seeing if you can make any standard algorithm work for your application.

---
Tags: algorithms
---


# Question
Title: clique, independent set, and minimum vertex cover
I was given a graph problem with 3 different questions and 1 set of answers. The problem is described below. The problem that I'm having is that it seems to me that the answer to all the questions is the same. I keep trying to find a caveat but I don't see one. What am I missing?

Here is the problem

Undirected graph $G$. $n$ - number of vertices. $m$ - number of edges. $d$ - maximum degree of a graph.

1. The maximum clique size of $G$ is no larger than
2. The minimum vertex cover size of $G$ is no larger than
3. The maximum independent set size of $\overline{G}$, the complement of $G$, is no larger than

Set of answers

* (a) $d+1$
* (b) $n$
* (c) $n-1$
* (d) $n/2$
* (e) $d$
* (f) $n-d$

It looks to me that the answer to every problem is (b) $n$, because

1. Clique cannot have more vertices than there are in a graph
2. Vertex cover cannot be larger than the number of vertices in a graph
3. Maximum independent set cannot be larger than the number of vertices in a graph.

I feel like I'm missing something, because the answers seem too obvious.

Any help is appreciated

# Answer
Of course, $n$ being the largest of the given answers will satisfy all conditions. You are expected to find the least upper bounds though.
> 1 votes

---
Tags: graphs
---


# Question
Title: Efficient algorithm for finding maximum subset of intersecting rectangles
What is an $O(n \log n)$ algorithm to find how big the largest subset of $n$ axis-aligned rectangles (in the plane) that contain a common point is? Perhaps by reducing this to a problem with such runtime?

An $O(n^{3})$ algorithm could be

```
for each of the n rectangles
    for each of the 4 sides of the rectangle
        find the points where it intersects other rectangles and keep the set of those points
        loop through the intersection points set and update the count

```

# Answer
You need a sweep line and an interval tree (modified so that it reports a number instead of intervals). I assume this is a course book problem and you are familiar with its background.

Move the sweep line bottom to top, stop at each horizontal segment. If the segment is the bottom side of a rectangle, insert it as an interval into the interval tree and remove it when the sweep line hits the top side of that rectangle. At each step you can query the number of rectangles containing a point on the sweep line. There are $O(n)$ stops for sweep line, each one adds $O(\log n)$ for interval operations, so it is $O(n\log n)$ in total. The only remaining issue is to keep track of the maximum covered point in $O(1)$ at each step. You should be able to complete this solution.
> 2 votes

# Answer
I'm not 100%, this is correct, but some answer it better than no answer, so here I go.

Let's define an *area* to be a rectangle (not necessarily from the given set) and for *area* `A` define `around(A)` to be the set of rectangles (from given set) that fully contain `A`, define `intersect(A)` to be the set of rectangles (from given set) that are contained inside or intersect `A`. The solution of your program, restricted to `A` is definitely between `|contain(A)|` and `|contain(A)| + |intersect(A)|`.

The given rectangles all lie in a finite space. Let that be `A`. Subdivide `A` into 4 *areas* `B1`, `B2`, `B3`, `B4` and distribute `intersect(A)` among them. Then `f(A) = max(f(B1), f(B2), f(B3), f(B4))`. This is a recursive relation, similar to quicksort, which should turn up to be $n \log n$ in average. Like quicksort it should have a sad ($n^2$ if you select sensible subdivisions) worst case performance as well.
> 0 votes

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


# Question
Title: Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s
Like the title says, we have the alphabet $\Sigma = \\{a,b,c\\}$ and the question is asking for the regular expression of the language $L$ that has the property that all strings in $L$ have at least two consecutive $a$'s but no consecutive $b$'s.

By attempt at a solution was this, where $aaa^+$ stands for $aaa(aaa)^\*$:

$$(a+c)^\*aaa^+(a+c)^\*b(a+c)^\* + (a+c)^\*b(a+c)^\*aaa^+(a+c)^\*$$

but I know this is wrong since we never get an instance of consecutive $b$'s. Can someone point me in the right direction?

# Answer
You'll need to guarantee the following:

* at some place, you have $aa$
* whenever there is a $b$, then there is a different letter between it and any further $b$

So one part of your regular expression will be $aa$, and that'll be need to be "in the middle" since we don't want to exclude the word $bcaab$ for example. The other part needs to take care of the restriction for $b$s.

One way to make ensure the restriction with regard to $b$ is to put at least one letter before every $b$ except for the first $b$ before and the first $b$ after $aa$. So you could do:

$(b + \epsilon)((a+c)^+b)^\*(a+c)^\*aa(b + \epsilon)((a+c)^+b)^\*(a+c)^\*$

where $\epsilon$ is the empty word. If you don't want to use $\epsilon$, you can split that expression up into 4 expressions without epsilon and sum them up.
> 1 votes

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


# Question
Title: Synchronizing sequence and Synchronizable DFA
I am trying to prove problem 1.59 in Sipser's book: *Introduction to the theory of computation , 2nd Edition.*

> Let $M=(Q,\Sigma,\delta,q\_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home". A **Synchronizing sequence** for $M$ and $q'$ is a string $s\in \Sigma^\*$ where $\delta (q,s)=q'$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).
>
> Say that $M$ is **Synchronizable** if it has a synchronizing sequence for some state $q'$.
>
> Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$. Moreover, can you improve upon this bound?

I'm more interested in proving that the synchronized sequence is of length of at most $k^3$ then trying to improve upon this bound.

I tried to prove (with no success) that there exists $w\in \Sigma^\*$ which $|w| \leq k^2 $ so that: $\delta(q\_1,w)=\delta(q\_2,w)$ for two distinct states in $M$: $q\_1,q\_2\in Q$ (thus, $w$ can be read from two states in the automaton and get to the same final state).
If I prove it, I could construct a word $w$ which will be a synchronizing sequence in $M$ and $|w|\leq k^3$ as required.

Any suggestions?

# Answer
I think you are on the right track:

Consider two states $q\_1,q\_2$. We claim the following:

If there exists a word $w$ such that $\delta(q\_1,w)=\delta(q\_2,w)$, then there is such a word $w$ of length at most $k^2$.

The proof of this a standard shrinking argument: if such a word is longer than $k^2$, then during the runs from $q\_1,q\_2$, a pair of states repeats, and we can shrink $w$.

Now, since you assume the existence of a synchronizing word for all states, you can proceed to construct a word that synchronizes all the states, pair by pair.
> 4 votes

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


# Question
Title: Grammar that numbers of letters `c` is greater than number of letters `b`
Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$.

Example: $acbccba$ is generated by the grammar.

I thought about:

$S \rightarrow aS \mid bS \mid SCS$

$ C \rightarrow cb \mid ca$

but not sure if it works. Could you help me, please.

# Answer
Your grammar never accepts a word since you can't make the $S$ disappear.

If you want to create more $c$ than $b$ you just have to make sure that when you create a $b$ you create a $c$ with it (but be careful they don't need to be side to side). You can also generate as much $a$ or $c$ as you want.

If you need more indication please ask.
> 3 votes

# Answer
Lowercase letters are terminals, uppercase nonterminals.

```
S → TcT

T → ε

T → aT
T → Ta

T → Tc
T → cT

T → bTc
T → cTb

```

The `S` rule ensures that there is at least one `c`. `T` then generates any string of `(abc)*` where every `b` is balanced by a `c`.
> 3 votes

# Answer
The correct grammar is:

```
C -> ScS //starting from C
S -> SaS | ScS | ScSbS | SbScS | ε

```
> 2 votes

# Answer
Whenever you add a **`b`** also add a **`c`** and add some(atleat one extra **`c`**) whereas on **`a`** language do not impose any constraint so feel free a add **`a`** any numbers of time (even `0`), any where in language string. A Context Free Grammar is possible for your language.

```
S  --> cS | Sc | T

T  -->  ABC | BAC | BCA | ACB | CAB | CBA

C  -->  cC  | c

B  -->  b   | ^

A  -->  aA  | ^

```

**Edit:**

your grammar is not correct, because you can generate a string in which **`b`*\*s are more then **`c`*\*s, e.g:

your grammar:

```
S --> aS | bS |SCS
C --> cb | ca

```

produces `bbacb` ad follows:

```
S --> bS --> bbS --> bbaS --> bbacb

```
> 1 votes

# Answer
$S \rightarrow SbS \mid bSS \mid SSb \mid b \mid bX \mid Xb$

$X \rightarrow bB \mid cA$

$A \rightarrow cX \mid cAA \mid b$

$B \rightarrow cX \mid bBB \mid b$
> -2 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Are Algebraic types just the combination of case classes and pattern matching?
On this page describing the precursor to the Scala language \- the pizza language - they refer to it having both case classes and pattern matching \- and then imply that these taken together provide algebraic types.

Is this the case? To provide algebraic types - do you combine case classes and pattern matching?

# Answer
Scala provides algebraic types and pattern matching in a way that is compatible with classes, but this is not what algebraic types are – it is Scala's realisation of the concept. Technically, pattern matching is not even needed for algebraic types; it just makes them must more convenient to use. One could instead use functions the pull apart the types. Early scheme's approach to ADTs would do just this.
> 0 votes

---
Tags: type-theory, pattern-recognition, abstract-data-types
---


title: Task Manager Performance tab in windows

text:
# Question
Title: Task Manager Performance tab in windows
I do not understand the following options in windows. Could any one explain

# Answer
> 1 votes
CPU Usage is how much your processor is running; of the available cycles to compute, how many are actually being used. On the left it shows the current value, and on the right it shows your history. The two graphs are because you have two CPUs (well, two cores in one CPU.)

Page File is something used when your RAM is filled up. All the data in your computer, while it's being used by a program, has to be "kept alive" somewhere, and this is what RAM is built for. When that's full, though, Windows will start using your hard drive instead. This is much, much slower to access than RAM, and will wear out your hard drive somewhat more quickly. I might recommend adding more RAM or closing unneeded processes.

In "Totals" you see: \- Handles, which is resources that a program is using - for instance, a program might have on handle to keep track of a file, one handle to check your registry for settings, and many many others. \- Threads, which is one part of a program that can run by itself. For instance, a simple video game will usually contain at least one thread for running the game, one thread for drawing graphics, and one thread to pay attention to mouse clicks or button presses. \- Processes, which is generally speaking "programs". Some programs, like Google Chrome or Metasploit, will keep many processes open at a time. Each process corresponds to one .exe file, although several instances of the same file could be loaded as separate processes. If you change tabs in Task Manager, you can see a list of all processes, and how much they're each using up resources on your computer.

The other three boxes, "Physical Memory", "Commit Charge", and "Kernel Memory", refer to different parts of RAM & Page File. \- Physical Memory refers to actual RAM (not page file!) being used by anything; right now you have 1.52GB out of 3.14GB of RAM available. \- Commit Charge refers to Physical Memory and Page File, collectively. Right now you are using 1.77GB, out of a total possible of 5.07GB. \- Kernel Memory refers to memory being used by Windows itself, and not by any particular process. Unlike closing a program, which frees its memory, kernel memory is almost impossible to free up.

---
Tags: operating-systems, performance
---


# Question
Title: Finding number of maximum independent sets in tree, using dynamic programming
I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around.

I've been trying to use a similar technique (ie. recursing through the childred and then the grandchildren of a node) to find the **number** of such sets but I have not been able to work it out.

Any help?

# Answer
Hint: If you are counting the number of MIS that include the root.

As you said a MIS that includes the root cannot include its children and you will recurse on the grand children. So if for the `ith` grandchild it has `k_i` Maximum independent sets(k\_i is the number of MIS for the subtree rooted at the grandchild i). Can you obtain a formula for the number of MIS for tree rooted at root?

If suppose the the subtrees rooted at the grand children of the root have k1,k2,k3,k4...,kt Maximum independent sets.(k1 for the 1st grand child and so on) Now if you select one MIS from the k1 available for the first grand child, one from the k2 available for the second and so on,and add the root to it you get a MIS of the whole tree.

So you have k1 choices in the first one, k2 in the second one, k3 in the third. So shouldn't the total number of MIS be the product of these? k1\*k2\*k3\*...\*kt

BTW you need to make sure that there is one MIS that contains the root
> 0 votes

---
Tags: dynamic-programming, trees, sets
---


# Question
Title: Maximum degree of concurrency in task dependency graphs
I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find out the maximum degree of concurrency in a given task graph.

In my case, I'm talking of a relatively small graph, around 100 nodes, but nodes, representing tasks, are long running tasks. So the occuracy, more then complexity of such an algorithm would matter.

Assuming I came up of such a degree, the second problem, is how should I distrubute tasks? I've read about topological sort, and transforming the result in a list of sets, with each set being run in parallel. But again, I suspect if this is the best approach.

# Answer
If you turn an activity-on-node task graph into a partial order (by taking the transitive closure), then the largest independent set of tasks is what you are looking for.

(Taking a topological sort, as suggested in another answer, does not work in general. Consider the series-parallel task graph $((a|b)c)|(d(e|f))$, where $\alpha|\beta$ means parallel composition of task graphs and $\alpha\beta$ means every task in task graph $\alpha$ precedes every task in task graph $\beta$. Here $\\{a,b,e,f\\}$ is the largest independent set, yet the topological sort will produce $\\{a,b,d\\}$.)

Although finding largest independent sets is NP-complete in general, it can be done quickly for partial orders. This starts by noting the equivalence of an independent set in a poset with a set of witnesses that realise the width of the poset, and applying König's theorem to compute the witnesses by a perfect matching.

Some of these basic algorithms are already part of software toolkits, like the Graph CPAN module for Perl, and the Boost Graph Library for C++.
> 5 votes

# Answer
Running a topological sort on the graph is the right thing to do. Topological sorting is just the linear time version of the following very simple greedy approach:

```
while there are nodes left:
    let S be the set of all nodes with indegree 0
    run all tasks in S in parallel
    remove all nodes in S from the graph

```

(I use the convention that Task A depends on Task B if there is an edge B-\>A)

It's fairly obvious that you can't do better than the above algorithm, and the maximum concurrency you can achieve is the size of the largest S that you encounter.
> 2 votes

# Answer
Since you stated that, by hypothesis, your task dependency graph is acyclic, you can easily determine the maximum degree of concurrency by running the breadth-first search algorithm. The algorithm starts from the root node (if the initial level contains more then one node then any node can be chosen as the root node) and proceeds towards the leafs level-wise: before inspecting nodes located on the next level it explores all of the nodes belonging to the same level. Just modify it trivially to count the number of nodes on each level, and update a variable holding the maximum number of nodes per level as the algorithms descends through the levels. The worst-case complexity is $O(V + E)$.
> 1 votes

---
Tags: optimization, distributed-systems, concurrency
---


# Question
Title: DNA Computing Algorithm to solve the Hamiltonian problem
Is it possible to represent the algorithm proposed by Adleman to solve the Hamiltonian problem in a probabilistic Turing Machine?

See also Computing with DNA

# Answer
> 1 votes
Yes, of course. The Hamiltonian path problem is decidable, so it can be solved using a Turing machine.

I recommend you read about the Church-Turing hypothesis, decidability, and undecidability. I think you'll find those topics of interest.

---
Tags: complexity-theory
---


# Question
Title: How can I analyze the time complexity of this Dynamic Time Warping algorithm implemented in MATLAB?
I have a rough idea that the time complexity is O(mn) where m and n are based on the length of signals, as per this http://en.wikipedia.org/wiki/Dynamic\_time\_warping.

How can I determine the time complexity of the following code (source)

```
function [Dist,D,k,w,rw,tw]=dtw3(t,r)
%
% [Dist,D,k,w,rw,tw]=dtw(r,t,pflag)
%
% Dynamic Time Warping Algorithm
% Dist is unnormalized distance between t and r
% D is the accumulated distance matrix
% k is the normalizing factor
% w is the optimal path
% t is the vector you are testing against
% r is the vector you are testing
% rw is the warped r vector
% tw is the warped t vector

[row,M]=size(r);
if (row > M)
     M=row;
     r=r';
end;
[row,N]=size(t);
if (row > N)
     N=row;
     t=t';
end;

d=((repmat(r',1,N)-repmat(t,M,1)).^2);

D=zeros(size(d));
D(1,1)=d(1,1);

for m=2:M
    D(m,1)=d(m,1)+D(m-1,1);
end
for n=2:N
    D(1,n)=d(1,n)+D(1,n-1);
end
for m=2:M
    for n=2:N
        D(m,n)=d(m,n)+min(D(m-1,n),min(D(m-1,n-1),D(m,n-1)));
    end
end

Dist=D(M,N);
n=N;
m=M;
k=1;
w=[M N];
while ((n+m)~=2)
    if (n-1)==0
        m=m-1;
    elseif (m-1)==0
        n=n-1;
    else
      [values,number]=min([D(m-1,n),D(m,n-1),D(m-1,n-1)]);
      switch number
      case 1
        m=m-1;
      case 2
        n=n-1;
      case 3
        m=m-1;
        n=n-1;
      end
    end
    k=k+1;
    w=[m n; w];
end

% warped waves
rw=r(w(:,1));
tw=t(w(:,2));
end

```

# Answer
> 1 votes
Look at the main double for loop that does all the work. It loops for m from 2 to M and then inside that for n from 2 to N. This is O(MN) like you expected.

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


# Question
Title: Difference between multitasking, multithreading and multiprogramming
I was a little confused between these three terms Multitasking, Multithreading and Multiprogramming

Although every one means executing different lines of codes, and for every one we need something like Task State Segment or context to store data for that particular thread/task.

I am missing something, can anyone give me the basic difference between them and how they are actually executed in a processor

**Edit:** Actually I was a guy from Electronics background and I was poor at OS related issues. The main thing I understood between multiprogramming and multithreading is that in multiprogramming we execute two separate programs where as in multithreading the scheduler produces two different threads which can be executed independently. I think these are a form of multitasking implementation. Am I correct. I was really confused

# Answer
The Wikipedia article Computer multitasking covers this well. In summary:

* **Multitasking:** there is more than one process and the operating system somehow decides which to run next.
* **Multithreading:** threads are essentially subprocesses, which share memory (separate processes cannot normally access each other's memory) but which are independently scheduled.
* **Multiprogramming:** a form of multitasking in which a process keeps running until it tries to access an I/O device, at which point another process is chosen to run so the CPU doesn't idle waiting for a punched card reader or something.
> 2 votes

# Answer
Multitasking is a user-interface term; it means the computer system allowed **the user** to do multiple tasks at once. Multitasking has nothing to say about how it's actually implemented; it can even be implemented as a single threaded program.

Multithreading and multiprogramming are forms of **the processor** being able to execute multiple tasks at once. The difference between multithreading and multiprogramming is the level of isolation between threads and program; each threads in a multithreaded system shares a common memory address space, while each program in a multiprogram system are independent from each other and can only communicate with each other through explicit IPC.
> -1 votes

---
Tags: terminology, operating-systems, concurrency
---


title: Set packing variant

text:
# Question
Title: Set packing variant
```
There are n collections of M sets.
Pick a single set from each collection,
such that all n picked sets are pairwise disjoint.

```

This problem can be converted to the standard Set Packing problem in the following way: add a unique element $e\_i$ to all $M$ sets in each collection $C\_i$. Then find a set packing of size $n$ in the resulting collection. Each set in the returned set packing must belong to a different collection.

So, the variant is not more difficult than the original set packing problem.

MY QUESTION IS: is the variant easier than the original problem? In particular:

* Is it possible to solve the variant problem in time polynomial in $n$ (assuming $M$ is constant)?
* Is it possible to approximate the variant problem in a more efficient way than the approximations known for the general set packing problem (i.e. $O(\sqrt{nM})$)?

# Answer
> 2 votes
Let $(U,S,k)$ be an instance of Set Packing where $U$ is base set, $S$ is the collection of sets over $U$ and $k$ is the minimum size of the desired set packing.

We can construct an instance of Erel's Set Packing (nice name, no? ;) ) by taking $k$ copies of $S$ (i.e. $n=k$, $M=|S|$), label them $S\_{i}$ for $1\leq i\leq k$.

Then if $(U,S,k)$ has a set packing of size at least $k$, there is some set $C \subseteq S$ such that $|C| \geq k$ and for every pair $c\_{i},c\_{j} \in C$, we have $c\_{i} \cap c\_{j} = \emptyset$. Moreover, this also holds for every $k$ sized subset of $C$. Arbitrarily pick one of these $k$ sized subsets $C' = \\{c\_{1},\ldots,c\_{k}\\}$, this will correspond to a solution for Erel's Set Packing where we take (in whatever order you care for) $c\_{i}$ in $S\_{i}$.

The reverse is also (clearly) true, a solution for Erel's Set Packing consists of $k$ pairwise disjoint sets, one from each $S\_{i}$, but as all the $S\_{i}$s are just copies of each other, all the sets they correspond to sets from the original $S$ that are pairwise disjoint.

So then the variant problem is also NP-complete, though I'm not sure what happens when $M=c$ for some constant $c$, I suspect it remains hard though (from just an intuition standpoint, no firm evidence).

---
Tags: algorithms, np-complete, sets, packing
---


# Question
Title: Equivalence of independent set and set packing
According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent.

The Independent Set search problem is: given a graph $G(V,E)$ and an integer $n$, find $n$ vertices no two of which are adjacent.

The Set Packing search problem is: given a finite collection $C$ of finite sets and an integer $n$, find $n$ sets that are pairwise disjoint.

I think they are equivalent based on the following bidirectional reduction:

→: Given an independent set problem on a graph $G(V,E)$, create a collection of $C$ of sets, where for each vertex $v \in V$ there is a set $S\_v \in C$ containing all edges adjacent to $v$. Now, every set packing in $C$ corresponds to a set of vertices no two of which have an edge in common, i.e., this is an independent set in $G$ of the same size.

←: Given a set packing problem on a collection $C$, create a graph $G(V,E)$ where for every set $S \in C$ there is a vertex $v\_S \in V$, and there is an edge between $v\_{S\_1}$ and $v\_{S\_2}$ iff the sets $S\_1$ and $S\_2$ intersect. Now, every independent vertex set in $G$ corresponds to a set of sets from $C$ no two of which intersect, i.e., this is a set packing in $C$ of the same size.

My question is: is my reduction correct? If so, are these problem equivalent? Is it possible to use approximation algorithms for one problem on the other problem?

# Answer
> 8 votes
The exact meaning of "equivalent" isn't obvious but you have shown something deeper than the normal equivalence under reductions considered for NP-complete problems.

You've demonstrated what's known as a **parsimonious reduction** between the two problems. Ordinarily, reductions between NP-complete problems are many-one reductions: they only have the property that problem A has a solution if, and only if, problem B has a solution. For example, when you reduce 3SAT to 3-Colourability, you produce a graph $G$ that is 3-colourable if, and only if, the original formula $\varphi$ is satisfiable. However, if $\varphi$ has $N$ variables, the number of satisfying assignments could be anything between zero and $2^N$, inclusive, whereas the number of 3-colourings of any graph is a multiple of six because of permutations of the set of colours.

The point about parsimonious reductions is that they're one-to-one. Your reduction sets up a bijection between solutions of the independent set problem and solutions of the corresponding set packing problem. Parsimonious reductions are useful because they preserve optimization and (approximate) counting versions of the problem. So your reduction also shows that the problem of finding the biggest independent set is as hard as finding the set packing using the most sets and that the problem of counting all the independent sets is as hard as to counting all the set packings.

There is a wider class of reductions that also preserve counting and approximate counting. These are the **approximation-preserving reductions** of Dyer *et al.* \[1\]. These are oracle reductions and relax the one-to-one requirement of parsimonious reductions to what is, essentially, "If you know (an approximation of) one, you can easily compute (an approximation of) the other." In particular, AP reductions can easily deal with the factor of $q!$ that's inherent in any reduction to the $q$-colouring problem. As the name suggests, AP reductions preserve approximability, in the sense that, if there's an AP-reduction from A to B and there's an FPRAS for B, then there's an FPRAS for A, too.

---

\[1\] Dyer, Goldberg, Greenhill, Jerrum. The relative complexity of approximate counting problems. *Algorithmica* 38(3):471–500, 2003. DOI; free PDF

# Answer
> 3 votes
Both problems are NP-complete, so even without checking your reductions, they are equivalent in that sense.

However, your reduction does seem okay. Technically for approximation results you want to verify some additional properties of the reduction (not necessarily hard to do, e.g. in this case PTAS reductions are of interest). You also have to talk about the optimization versions of the problems, rather than the decision versions (i.e. asking for the max/min answer, rather than for the existence of one of a certain size or more/less).

In fact it is already known that they do have related approximability. Unfortunately, they generally don't have good approximations. For both problems (and Maximum Clique, which is also closely related) there are inapproximability results, the primary being inapproximability with $|V|^{1-\varepsilon}$ for any $\varepsilon \> 0$ (unless NP=ZPP), which is about as bad as it gets.

If you're looking at restricted classes of graphs, you might be able to find something interesting. For further reading, I refer you to the inestimably useful compendium of Viggo Kann:

1. Max Set Packing
2. Max Independent Set
3. Max Clique

---
Tags: algorithms, graphs, sets, packing
---


# Question
Title: Questions on the definition of polynomial time
I been reading Wikipedia for polynomial time, and it says:

> An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$.

My questions are:

1. Why do we have addition and multiplication but no division?
2. Why do we have both multiplication and addition, couldn't we express one with the other?
3. What is the difference between polynomial time and exponential time by definition?

# Answer
You seem to be struggling with a lot of the fundamental concepts, here. All the NP-completeness stuff is cool and fascinating and I can absolutely see why you're attracted to it. But you really aren't going to get anywhere with this stuff until you have a good grasp of the basics. If you want to work on NP-completeness, you need first to get a good book on basic discrete mathematics and you need to study it until you understand it. I know that's kind of dull but there is no other way. There might be a question here already about recommendations for discrete maths books.

This is a technical, precise subject where every little part of every little sentence has some special meaning. It's not like, say, the rules of some sport that you can pick up more or less just by watching people play. Yes, you can get a general, intuitive understanding of why, say, an NP-complete problem seems to be very hard to solve, in just the same way that you can get a general, intuitive understanding of how quantum tunnelling allows radioactive decay to happen. But, if you want to discover new things about it, you need to understand the underlying mathematics. There is no other way.

---

If all you want to do is talk about the running time of algorithms, you don't need to worry about polynomial expressions; just about polynomials. Polynomial expressions are generalizations of polynomials to be functions of things other than numbers. Over numbers (integers, reals, complex, anything else), the polynomials are the functions of the form $$f(x) = a\_kx^k + a\_{k-1}x^{k-1} + \dots + a\_1x + a\_0\\,,$$ where $k$ is an integer constant and the $a\_{i}$ are constants of the same kind of number as $x$ will be.

**1. Why do we have addition and multiplication but not division?**
The unhelpful answer is "Because that's the definition," just like CNF is defined using AND and OR rather than, say, XOR and NOR. The reason for forbidding division is that you might want to have a polynomial in a situation where division doesn't make sense (e.g., if you're working mod 2, or $x$ is an integer and you want to guarantee that $f(x)$ is also an integer). The kind of function you can make by dividing one polynomial by another is called a *rational function* and these are also widely studied and very useful in many situations. Why don't we use rational functions instead of polynomials in complexity theory? It's mostly because we don't need that level of detail: we already say that $4x^3 + 2x + 1$ is basically just some constant times $x^3$ so we wouldn't gain anything by bringing division to the party.

**2. Why do we have both multiplication and addition, couldn't we express one with the other?**
Because there's no way to express all the multiplications in a polynomial as repeated addition, while still keeping the form of a polynomial. Sure, you could write $3x$ as $x+x+x$ but that would be hard to read and wouldn't gain anything. But there's no way to write $x^2$ using a fixed number of additions: there's nothing in the definition of a polynomial that lets you write $$\underbrace{x + \dots + x}\_{x \text{ times}}\\,.$$

**3. What is the difference between polynomial time and exponential time by definition?**
An exponential function is one of the form $k^x$ for some constant $k$. Note that this is different to a polynomial: polynomials are "variable-to-the-constant" and exponentials are "constant-to-the-variable". Exponentials grow *much* faster than polynomials. For example, see this plot. As G. Bach points out in his comment, if you're defining complexity classes around exponential functions, you need to take $k\>1$.
> 6 votes

# Answer
Note that the questions you're asking (apart from 3.) don't have anything to do with complexity theory, so you'll have to forget that mindset for a moment to understand what you read.

1. Because polynomials are defined as sums of multiples of non-negative integer powers of variables.
2. Because using both makes the expressions far smaller and easier to comprehend. One alternative would be to use recursive functions and those aren't exactly the most intuitive thing.
3. $\mathcal{O}(n^k) \subsetneq \mathcal{O}(b^{(n^c)})$ for any $k \in \mathbb{R}, b\>1, c \> 0$. In words: any exponential function grows strictly faster than any polynomial function, asymptotically.
> 4 votes

# Answer
1. We're mostly concerned with approximate bounds. If you know an upper bound, given by a rational function, you can write a shorter one, given by a polynomial. This doesn't mean that you can't, only that you don't need to.
2. No, how?
3. One is $n^k$, the other is $k^n$. Take $k=2$ and see how they compare.
> 2 votes

---
Tags: time-complexity
---


title: Exponential time algorithms

text:
# Question
Title: Exponential time algorithms
Wiki define Polynomial time as fallow:

> An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$

I understand that in general speaking the difference between **Polynomial time** and Exponential time is that exponential function grows strictly faster than any polynomial function, asymptotically(reference).

I am trying to understand the core definition of **Exponential time**.

1. What elements will make one algorithm to run in **Exponential time**?
2. What change do I need to do in the **polynomial expression** to make it **Exponential time**?(By *it* I am referring to the algorithm definition in the beginning of the question)

# Answer
1. There's no easy answer for this one, though there are signs to look out for. Examining every possible subset of a set, for instance, is exponential - so if I had a set of integers $\\{x\_1,...,x\_n\\}$, and wanted to check every subset of these to see if they sum to $0$, I'd have to consider exactly $2^n$ subsets, which makes this method exponential time. Several different traps can make an algorithm exponential time, however, so rather than looking out for broad categories, analyse algorithms on a case-by-case basis.
2. If an algorithm takes $n^2$ steps to complete, then it's polynomial. If it takes $2^n$ steps, it's exponential. The difference is the position of the $n$. If something is $O(n^m)$ for $n\> 1$, $m\>0$, then it's polynomial in $n$ for fixed $m$, but exponential in $m$ for fixed $n$.
> 7 votes

# Answer
Often you get an exponential time brute-force algorithm when you consider a problem, and enumerate its whole search space. Typically, you'd think of subset problems (in SAT, you would choose a subset of variables set to true), permutation problems (in TSP, every tour is a permutation of the cities), and partition problems (in graph coloring, you are trying to partition the vertices into color classes). Or consider sorting even: there are $n!$ permutations of $n$ integers. Go through every permutation, and check if it is sorted. Silly (and slow), but it works.
> 4 votes

---
Tags: time-complexity
---


title: EXPTIME vs Super-polynomial time

text:
# Question
Title: EXPTIME vs Super-polynomial time
It is proven by Time hierarchy theorem that EXPTIME-complete do not belong to P even if we do not know if NP belong to P.

Before I read wiki, I found EXPTIME algorithm for solving 3-sat, the brute algorithm $O(2^n)$. Could I announced then, that there could not be polynomial solution for 3-sat?

1. **Time hierarchy theorem** prove that there are EXPTIME problems that are not in P. But how can you prove that problem is EXPTIME and not super-polynomial time?
2. Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

\*If you have solution for just one of the questions it's fine.

# Answer
> 10 votes
No, that doesn't prove there's no polynomial time solution for 3-SAT, for a couple of reasons.

1. Saying that you have an $O(2^n)$ algorithm for something only provides an upper bound. The algorithm takes *no more than* some constant times $2^n$ steps, for big enough $n$ but I can tell you that I have *no more than* one trillion dollars in the bank and you still have no idea how wealthy I am.
2. If your suggested argument was solid, the following would be a direct proof that $\mathrm{P}\neq\mathrm{EXP}$. Here's an exponential-time, brute-force recursive algorithm for graph connectivity: check that every proper subset of the graph's vertices is connected and sends an edge to at least one vertex not in the subset. This can't prove that there's no polynomial time algorithm for graph connectivity because we already know that plenty of those exist. Similarly, observing that you have an exponential-time algorithm for 3-SAT doesn't prove that there isn't also a polynoial one.
3. $\mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{EXP}$ so we already know there is an exponential-time algorithm for every problem in $\mathrm{P}$ and $\mathrm{NP}$. Knowing that 3-SAT is in $\mathrm{EXP}$ tells you nothing new. However, if you could prove that 3-SAT is $\mathrm{EXP}$-complete, that would prove that $\mathrm{NP}=\mathrm{EXP}$ and, since we know that $\mathrm{P}\neq\mathrm{EXP}$ from the time hierarchy theorem, that would prove $\mathrm{P}\neq\mathrm{NP}$. But it's very unlikely that 3-SAT is $\mathrm{EXP}$-complete. :-)

> \[...\] how can you prove that problem is EXPTIME and not super-polynomial time?

"Super-polynomial" just means "more than a polynomial". EXPTIME is an example of a super-polynomial time complexity class.

> Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

That doesn't make sense. A polynomial is a polynomial so it can be expressed as a polynomial; a function that's super-polynomial isn't a polynomial so it can't be expressed as a polynomial. I'm not sure why you've latched onto this phrase "polynomial expression".

---
Tags: time-complexity
---


# Question
Title: Mastermind (board game) - Five-guess algorithm
The algorithm (from here) -

> 1. Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb.
> 2. Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer.
> 3. For each possible guess (not necessarily in S) calculate how many possibilities from S would be eliminated for each possible colored/white score. The score of the guess is the least of such values. Play the guess with the highest score (minimax).
> 4. Go back to step 2 until you have got it right.

I confused about the 3nd step -

what is mean -

> how many possibilities from S would be eliminated for each possible colored/white score

what is the "correct answer" and the "guess" here ?

Can someone clear it some more ?

# Answer
> 4 votes
The text you quoted seems clear as it is. But I'll try to elaborate on step 3, since you asked:

Let $S$ denote the set of possible secrets (given responses to moves you've made so far). Given a candidate guess $g$, you run over all possibilities $s \in S$ and calculate the response that you'd get if you guessed $g$ and the secret was $s$ (the number of black pegs and the number of white pegs); this is "the colored/white score". Now, for each colored/white score that could be received, if you were to get that score, you could eliminate some possibilities from $S$ as incompatible with that colored/white score; the "goodness" of a colored/white score is the number of possibilities eliminated. The "helpfulness" of a candidate guess $g$ is the minimum of the "goodness" of all the colored/white scores you could possibly get, in response to $g$. Select the guess $g$ with highest "helpfulness".

In other words, let $R(g,s)$ denote the number of black pegs and number of white pegs you'd get if the secret were $s$ and you guessed $g$ (this is what your quote calls the "colored/white score"). Let $Z(g) = \\{R(g,s) : s\in S\\}$, so that $Z(g)$ denotes the set of "colored/white scores" you could possibly get if you made guess $g$ (given that the secret $s$ has to be one of the possibilities in $S$). Now, if you have a "colored/white score" $z$ where $z \in Z(g)$, let

$$G(g,z) = |\\{ s \in S : R(g,s) \ne z\\}|,$$

so that $G(g,z)$ is the "goodness" of getting a "colored/white score" $z$ in response to guess $g$. Also, let

$$H(g) = \min \\{G(g,z) : z \in Z(g)\\},$$

so that $H(g)$ denotes the "helpfulness" of a candidate guess $g$.

Now step 3 says: you should play the guess $g$ that maximizes $H(g)$.

---
Tags: algorithms, board-games
---


title: Definition of a regular language

text:
# Question
Title: Definition of a regular language
I'm a little confused by Wikipedia's definition of a regular language:

> The collection of regular languages over an alphabet $\Sigma$ is defined recursively as follows:
>
> * The empty language $\emptyset$ is a regular language.
> * For each $a \in \Sigma$ ($a$ belongs to $\Sigma$), the singleton language ${a}$ is a regular language.
> * If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A \cdot B$ (concatenation), and $A^\ast$ (Kleene star) are regular languages.
> * No other languages over $\Sigma$ are regular.

This seems defines a regular language as any set that contains a finite number of unique elements, though the set can be countably infinite (it's worth noting that the article doesn't explicitly state that $\left\vert{\Sigma}\right\vert$ is finite in the definition), i.e., a regular language is any set $S$

$$ \left\vert{S}\right\vert \le \left\vert{\infty}\right\vert, {S} \in \Sigma \\ \left\vert{\Sigma}\right\vert \lt \left\vert{\infty}\right\vert $$

I think this is correct because the union, concatenation or Kleene star of a singleton that is part of a finite set or the empty set must be also part of that set, even when operated on recursively.

It's been a fair while since I did any maths, and even longer since I've touched set theory. Have I completely misread Wikipedia's definition? If so, how? If I haven't how is a regular language different from my definition?

# Answer
Regular languages over a finite alphabet are always countable: indeed, $\Sigma^\*$ is countable. However, not every subset of $\Sigma^\*$ is regular. This is because the set of regular languages is only *finitely* additive rather than $\sigma$-additive. That means that if $A\_1,\ldots,A\_\ell$ are regular then so is $A\_1 \cup \cdots \cup A\_\ell$, but the same isn't true for an *infinite* sequence. Indeed, every subset of $\Sigma^\*$ can be written as an infinite sum of singletons (sets of size $1$), which are regular, but not all subsets of $\Sigma^\*$ are regular. For example, the following subset of $\\{0,1\\}^\*$ isn't: $\\{ 0^n 1^n : n \geq 0 \\}$.

You define a regular language as one which has a *finite number of unique elements*. Unfortunately, you don't define what these *unique elements* are, so your definition is vague at best. Regular languages have other definitions than the one given by Wikipedia - for example, they are the languages accepted by *deterministic finite automata*, by *non-deterministic finite automata*, and by Turing machines running in time $o(n\log n)$. Each of these has a finite number of *states*, which might correspond to your *unique elements*. A third approach defines a regular language as one having finitely many Myhill-Nerode equivalence classes (two words $x,y \in \Sigma^\*$ are equivalent with respect to a language $L$ if for all $z \in \Sigma^\*$, $xz \in L$ iff $yz \in L$).

Here is a Wikipedia-like definition of the regular languages (both definitions are the same for finite $\Sigma$). It is the smallest collection of languages which:

1. Contains all singletons $\\{a\\}$ for $a \in \Sigma$.
2. Closed under finite unions and intersections, under complementation, under concatenation, and under Kleene star.

Every regular language has a "proof" of its being regular which comes from applying the operations above. In the case of the Wikipedia definition, this proof is a *regular expression*, which is why they chose their particular definition. For example, $0^\*1^\* + 1^\*0^\*$, the language of "monotone" sequences over $\Sigma = \\{0,1\\}$, can be derived as follows from Wikipedia's rules:

1. $0$ is regular (singleton axiom).
2. $0^\*$ is regular (Kleene star applied to (1)).
3. $1$ is regular (singleton axiom).
4. $1^\*$ is regular (Kleene star applied to (3)).
5. $0^\*1^\*$ is regular (concatenation of (2) and (4)).
6. $1^\*0^\*$ is regular (concatenation of (4) and (2)).
7. $0^\*1^\* + 1^\*0^\*$ is regular (union of (5) and (6)).

My rules are more permissive: they allow complementation and intersection. You can try to prove that both definitions are equivalent - this is quite difficult from these definitions, but becomes much easier using either DFAs (deterministic finite automata) or Myhill-Nerode relations.
> 3 votes

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


# Question
Title: Correctness of asymptotic expression from exact expression
I have the expression: \begin{equation} |Q|f(n)|\Gamma|^{f(n)} \end{equation}

Here is my solution to convert the above into an asymptotic expression: $|Q| = 2^l$ for some $l\in\mathbb{R}$ $|\Gamma| = 2^k$ for some $k\in\mathbb{R}$

Therefore we have $2^lf(n)(2^k)^{f(n)} = f(n)2^{kf(n)+l} = f(n)2^{O(f(n))}$

1. Is this correct? I just want to verify my understanding of a discussion in Sipser's Theory of Computation text.

# Answer
> 1 votes
What you wrote is correct under the assumption that $|\Gamma|$ and $|Q|$ are constant (which, from the context, is indeed the case), but can be taken a bit further, and can be made more explicit:

For every $x\>0$ it holds that $x=2^{\log x}$. Therefore you get

$$f(n)|Q||\Gamma|^{f(n)}=2^{\log f(n)}2^{\log |Q|}2^{f(n)\log |\Gamma|}= 2^{\log f(n)+\log |Q|+f(n)\log |\Gamma|}=2^{O(f(n))}$$

which is somewhat cleaner.

---
Tags: asymptotics
---


title: Process Types and names

text:
# Question
Title: Process Types and names
There seems to be a classification of processes in IT. For example, "business process" refers to the collection of tasks done by organization members / software systems to achieve a goal.

If a process is completely automated and carried out by software (no people involved) what is the process called? Say we have a Web service A and service B online and we have a process that automatically uses both in achieving a goal.

I googled for "Software process" but the results are not what I am looking for (e.g waterfall)

My apologies if this is not the correct forum to ask this question. Thanks in advance

# Answer
"Business process" can also be applied. Or you could call it "automated process" or "automated business process" or "software processing" or "service" or any of a number of other things.

In other words: these terms do not have a precise mathematical/technical definition. So, define your terms, and use them consistently. This is not a technical question (and this site is better-suited for technical questions, not terminology questions).
> 1 votes

---
Tags: software-engineering
---


# Question
Title: Time complexity of languages that are polynomial time reducible to NP complete languages
I am wondering if given the time complexity of an NP-Complete problem or at least some information about it for example if $ SAT\in Time(2^{sqrt(n)})$ (hypothetically) could I assume that all languages in NP (which are clearly polynomial time reducible to SAT) are also $\in Time(2^{sqrt(n)})$

I believe the answer is false because I could basically pick any arbitrary class of exponential time functions and claim that all languages in NP are contained within it while it may actually belong to a class of higher power... but I'm not sure how to formulate this as a proof.

# Answer
You are right. You can't draw that inference. Given the assumption that SAT can be solved in $O(2^{\sqrt{n}})$ time, it does not follow that all NP-complete problems can be solved in $O(2^{\sqrt{n}})$ time.

For instance, the reduction from the NP-complete problem to SAT might transform a problem instance of size $n$ to a SAT instance of size $n^2$, so applying the SAT algorithm to that would take $O(2^n)$ time. There are some reductions that preserve the size of the problem instance, and for those reductions, you will be able to solve them about as fast as SAT -- but as far as we know, not all NP-complete problems fall into that category.

You might enjoy reading about the exponential time hypothesis, which is the hypothesis that there is no such subexponential-time algorithm for SAT. Folks have studied the consequences of the exponential time hypothesis in depth (as well as the consequences of the negation of the exponential time hypothesis).
> 7 votes

---
Tags: time-complexity, np-complete, polynomial-time
---


# Question
Title: Multi-level cache for which inclusion holds
For inclusion to hold between two cache levels L1 and L2 in a multi-level cache hierarchy, which of the following are necessary?

1. L1 must be a write-through cache.
2. L2 must be a write-through cache.
3. The associativity of L2 must be greater than that of L1.
4. The L2 cache must be at least as large as the L1 cache.

This was a multiple-choice question with the following possible answers:

* (A) 4 only
* (B) 1 and 4 only
* (C) 1, 2 and 4 only
* (D) 1, 2, 3 and 4

I think L2 cache must be at least as large as the L1 cache but I am confused what the need for writeback is for this cache.

# Answer
Correct Answer: 1) and 4) only . For inclusion property to hold, every changes in L1 should be made in L2 also. therefore , L1 should be write-through. It is not necessary fr L2 to be write -back. And 4) is mandatory for the same reason i.e L2 would need to hold the contents as same as L1 and as much as ,or may be greater than L1.
> 2 votes

---
Tags: cpu-cache
---


# Question
Title: Is the language of all ucv with u ≠ v context-free?
Is $L = \\{w\_1cw\_2 : w\_1, w\_2 \in \\{a, b\\}^\* , w\_1 \neq w\_2 \\}$ a CFL?

In my opinion it is not since if we want to know the inequality of $w\_1$ and $w\_2$ we must be aware of their equality and that is not a $CFG$.

# Answer
This is a CFL, but the complement (with equality) is not. Notice that both the language and the complement become CFL when you mirror one of the two words.

To show that this is a CFL, you can design a PDA that guesses the letter at position $i$ that will be different in $w\_1$ and $w\_2$. It start by reading the first $i$ letters of $w\_1$ and pushing $i$ symbols to the stack up to this letter, and remembers the letter $a$ in $w\_1$ at position $i$. Then, it waits to read $c$, and pops the $i$ symbols off the stack. It accepts if the current letter (at position $i$ in $w\_2$) is not $a$.

You have to also treat the case of different lengths, but it's not hard, I leave it as exercise ;)
> 4 votes

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


title: Regular concat with non regular

text:
# Question
Title: Regular concat with non regular
If L is regular and M is non regular; then L.M is necessarily not regular. Is this true or false? And why?

I feel its false

# Answer
The claim is this:

> If $L$ is a regular language and $M$ is a non-regular language, then the concatenation $LM$ of the two languages is necessarily non-regular.

If this claim is false, all you need to do is to provide one counterexample showing that it's false. If the claim is true, you need to prove that it's true for any languages $L$ and $M$, a much harder task. Fortunately, this claim is not true.

If we let $L = \emptyset$ and let $M$ be any non-regular language, then $LM = \emptyset = L$, a regular language.

Now, if that feels too much like cheating, we can find other examples. Consider this:

1. $L = \Sigma^\*$
2. $M = \\{ww^R \mid w \in \Sigma^\*\\}$

$L$ is regular, $M$ is non-regular (in fact, it's the language of palindromes, a canonical context-free language). Since the empty word is in $M$, we have $LM = \Sigma^\* = L$, so the concatenation is regular.
> 5 votes

---
Tags: regular-languages
---


# Question
Title: Is the set partitioning problem NP-complete?
I know that the set partitioning problem defined like this:

> Given $$S = \left\\{ x\_1, \ldots x\_n \right\\}$$ find $S\_1$ and $S\_2$ such that $S\_1 \cap S\_2 = \emptyset$, $S\_1 \cup S\_2 = S$ and $\displaystyle\sum\_{x\_i \in S\_1} x\_i=\sum\_{x\_i \in S\_2} x\_i.$

is NP-complete. But I don't understand why (or am not even sure if) the following problem is NP-complete:

> Given $$S = \left\\{ x\_1, \ldots x\_n \right\\}$$ find $S\_1$ and $S\_2$ such that $S\_1 \cap S\_2 = \emptyset$, $S\_1 \cup S\_2 = S$ and $$| \sum\_{x\_i \in S\_1} x\_i-\sum\_{x\_i \in S\_2} x\_i |$$ is minimized.

The paper 'The Differencing Method of Set Partitioning' by Karp and Karmarkar and some others say that it is NP-complete. But, if I have a sample solution to this problem, I can not tell whether it is an optimal solution (unlike in the first problem) and therefore I feel it NP-hard. If this is not true, how can I conclude that it is NP-complete? Thanks!

# Answer
Karmarkar and Karp do *not* claim that the second problem is NP-complete. It can't be, because it is not in NP. Remember that NP is a class of decision problems, i.e., problems where the answer is either "yes" or "no". Because the problem is not in NP, it's not required that the answer be efficiently checkable. The same thing happens with TSP: sure, if I give you a route around the cities and claim that it's less than 50 miles, you can check that easily; but if I give you a route and claim that it's the shortest, there's (probably) no way to check that in polynomial time.

Rather, the second problem is what is known as an NP optimization problem. It asks us to minimize a certain function $f$ and the decision problem, "Given $S$ and $k$, is $f(S)\leq k$?" is in NP. Now, if this decision problem is NP-complete, the optimization problem is NP-hard: there's a trivial reduction from the decision version to the optimization problem. Going the other way around, if you had an efficient algorithm for the decision problem, you could find out the optimum by binary search.
> 6 votes

---
Tags: complexity-theory, optimization, np-complete, partitions
---