# Question
Title: What NP-complete problem to reduce to k-Edge-Colorability to prove its NP-hardness?
What known NP-complete problem would one reduce to $k$-Edge-Colorability to prove that the latter is NP-hard?

# Answer
> 3 votes
This is a classic result of Holyer \[1\]. The reduction is from 3-SAT, and the constructed graph is cubic.

---

\[1\] Holyer, Ian. "The NP-completeness of edge-coloring." SIAM Journal on Computing 10.4 (1981): 718-720.

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


# Question
Title: $\mathbf{NC_2}$ is closed under log-space reduction
I actually have to prove the following :

$\mathbf{NL} \subseteq \mathbf{NC\_2}$

I have the following approach :

1. I will prove that $\mathbf{PATH} = \\{〈D, s, t〉 | \text{D is a directed graph with a path from vertex s to t}\\} \in \mathbf{NC\_2}$.
2. I will show that $\mathbf{NC\_2}$ is closed under log-space reductions i.e:

$$(1): B \in \mathbf{NC\_2} \hbox{ and } A \le\_l B \Longrightarrow A \in \mathbf{NC\_2}$$

where $\le\_l$ is the logspace reduction defined as

$$A \le\_l B :\Longleftrightarrow (\exists M \hbox{ TM}, \forall x)\[x \in A \Longleftrightarrow M(x) \in B\]$$

($M$ is a TM which runs in logarithmic space).

3. Since $\mathbf{PATH}$ is an $\mathbf{NL}$-complete problem the proof will be done.

Proving The 1st part was easy, i am stuck at the second part and have no idea how to proceed.

Any help?

# Answer
> 2 votes
We want to show that if $A\le\_lB$ and $B\in NC\_2$ then $A\in NC\_2$.

Since $A\le\_l B$ we have a Turing machine $M\_{f,i}(x)$ calculating the i'th bit of the reduction output $f(x)\_i$, using logarithmic space.

$M\_{f,i}(x)=1 \iff \left( G\_{M\_{f,i}(x)},c\_{start},c\_{acc} \right)\in PATH$

Where $G\_{M\_{f,i}(x)}$ is the configuration graph of the computation of the logspace machine $M\_{f,i}$ on $x$,and $c\_{start},c\_{acc}$ are the initial and accepting configurations, correspondingly.

Now your $NC\_2$ circuit for $A$ will, "in parallel", compute all the bits of the reduction $f(x)$ (this can be done since you proved $PATH\in NC\_2$) and send the result as input to the $NC\_2$ circuit for $B$. This results in an $NC\_2$ circuit for $A$.

---
Tags: complexity-theory, reductions, closure-properties, complexity-classes
---


# Question
Title: Can we show that non-determinism adds no power, for some specific running time?
$NP = \cup\_{k \in \mathbb{N}} NTIME(n^k)$

$P = \cup\_{k \in \mathbb{N}} TIME(n^k)$

Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$?

For how large of a $k$ can we show the above statement to be true?

# Answer
> 9 votes
If $\mathsf{NTIME}(n^k) \subseteq \mathsf{TIME}(n^\ell)$ for any $k,\ell$ then $\mathsf{P} = \mathsf{NP}$. Indeed, any problem $L \in \mathsf{NP}$ can be solved in non-deterministic time $O(n^r)$ for some $r$. Consider now the problem $L' = \\{0^{|x|^{r/k}}1x : x \in L\\}$. Clearly this problem is still in $\mathsf{NP}$, and furthermore the previous algorithm solves it in non-deterministic time $O(n^k)$. Therefore $L'$ has a deterministic algorithm running in time $O(n^\ell)$, implying that $L$ has a deterministic algorithm running in time $O(n^{r(\ell/k)})$.

This trick is known as *padding*.

---
Tags: complexity-theory, time-complexity, polynomial-time, nondeterminism
---


# Question
Title: Practical exponential time algorithms for polynomial-time solvable problems
Inspired by this quote attributed to Alan Perlis:

> For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.

How I interpret this statement is that some exponential running times should be preferred over polynomial ones for realistic problem sizes. I have never actually seen such a case though.

I wonder if there are any problems for which exponential algorithms are known that are preferable to the best polynomial ones up to a nontrivial problem sizes?

# Answer
The simplex method for linear programming has worst case exponential time complexity but is widely used in practice instead of the polynomial algorithms (which do exist).
> 13 votes

# Answer
another big/ widespread example is Prime detection/ generation for RSA cryptography. theres a P-Time algorithm discovered early this century but it runs slow in practice so the probabilistic Miller-Rabin test is used. the algorithm runs slower the more bases are tested and could be said to run in exponential time (or at least nonpolynomial) in worst case as certainty of (non)primality is increased. a pragmatic/ P-time limit/ "compromise" is chosen in implementations so that its efficient but there is still high certainty.

see also
> -1 votes

---
Tags: algorithms, reference-request, efficiency
---


title: Example Context free grammar

text:
# Question
Title: Example Context free grammar
Is there a nice way to give context free grammar for $$\\{a^nb^ma^kb^l:n+m=k+l\\}?$$

From PDA point of view it seems we just push + on stack if we see a, push + on stack if we see b, pop + from stack if we see a, pop + from stack if we see b and accept if you have empty stack.

# Answer
> 3 votes
Here is a simple grammar: $$ \begin{align\*} & S \to aSb|U|V \\ & U \to aUa|T \\ & V \to bVb|T \\ & T \to bTa|\epsilon \end{align\*} $$

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


title: Master method recurrence question

text:
# Question
Title: Master method recurrence question
This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below).

For a recurrence of $$T(n) = a T(\frac{n}{b}) + f(n)$$

where f(n) is $\Theta{(n)}$, would we be comparing $n^{\log\_b(a)}$ with $n^{1}$ - meaning we would be comparing $log\_b(a)$ with 1? Since the rate of growth is linear?

what about where f(n) is $\Theta{(1)}$ (aka some constant?), would we be comparing $n^{\log\_b(a)}$ with $n^{0}$? '0' since there is no rate of growth for a constant?

# Answer
I think the question is asking how to translate $f(n)$ into Big-Theta notation to be used for the Master Theorem. You have the right idea about switching between notations.

Another way to write the Master Theorem is as follows:

$T(n) = aT(n/b) + \Theta(n^d)$

So, yes, if you have a linearly growing function, then $f(n)$ may be substituted with $\Theta(n)$.

Then you may proceed with your comparisons.
> -1 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


title: Union of right congruence relations

text:
# Question
Title: Union of right congruence relations
Since we started talking about relations on languages and so on i keep on struggling with this subject.

So now iam faced with two questions where i really dont know how to start.

1. > First of all, the natural relation of a language $L \subseteq \Sigma^\*$ is the equivalence relation on $\Sigma^\*$ with the equivalence classes $L$ and $\Sigma^\* \setminus L$
>
> Let the natural relations of two arbitrary languages $L\_1$ and $L\_2$ be right congruent. Is the natural relation of the language $L\_1 \cup L\_2 $ also right congruent?
>
> So a right congruence is a equivalence relation with the added property that:
>
> $ \forall a \in \Sigma : u \equiv v \Longrightarrow ua \equiv va$
>
> Intuitively i would say that the union of this two relations remains to be a right congruence but i dont know how to prove this idea.
2. > For every equivalence relation $\equiv$, there are at least two languages which are saturated by $\equiv$, true or false?
>
> An equivalence relation saturates a Language $L$ if: $ u \equiv v \Longrightarrow u \in L \Leftrightarrow v \in L $
>
> My guess would be that any equivalence relation saturates the Language $L$ and $\bar{L}$

I would be pleased if some one could provide me with a useful hint on how to solve this questions.

# Answer
> 1 votes
I'll walk you through the first question. You can ask the second question separately (see D.W.'s answer).

When faced with a "proof or refute" question like this, we need to try both directions. First, we can try proving the claim. If we seem to get stuck, we can look for a counterexample.

Let's try proving the claim. We are given that $L\_1$ and $L\_2$ are right congruent. This means the following, for $u,v \in \Sigma^\*$ and $a \in \Sigma$:

* If $u,v \in L\_1$ or $u,v \notin L\_1$ then either $ua,va \in L\_1$ or $ua,va \notin L\_1$.
* If $u,v \in L\_2$ or $u,v \notin L\_2$ then either $ua,va \in L\_2$ or $ua,va \notin L\_2$.

Let's try to prove that $L\_1 \cup L\_2$ also satisfies a similar condition. We have to consider two cases: $u,v \in L\_1 \cup L\_2$ and $u,v \notin L\_1 \cup L\_2$. The second case looks simpler, so let's start with it. If $u,v \notin L\_1 \cup L\_2$ then $u,v \notin L\_1$ and $u,v \notin L\_2$. The assumptions then show that:

* Either $ua,va \in L\_1$ or $ua,va \notin L\_1$.
* Either $ua,va \in L\_2$ or $ua,va \notin L\_2$.

We have to prove that either $ua,va \in L\_1 \cup L\_2$ or $ua,va \notin L\_1 \cup L\_2$. We reason as follows. If $ua,va \in L\_1$ then $ua,va \in L\_1 \cup L\_2$ so we're done. Same if $ua,va \in L\_2$. The remaining case is $ua,va \notin L\_1$ and $ua,va \notin L\_2$. In this case, $ua,va \notin L\_1 \cup L\_2$, so we're again done.

Now let's get back to the other case: $u,v \in L\_1 \cup L\_2$. This case looks harder. There are many different subcases. Let's start with a simple one: $u,v \in L\_1$. In this case we can say that $ua,va \in L\_1$ (and then we're done, since $ua,va \in L\_1 \cup L\_2$) or $ua,va \notin L\_1$. What do we do in the latter case? We have to consider membership of $u,v$ in $L\_2$. If $u,v \in L\_2$ or $u,v \notin L\_2$ then either $ua,va \in L\_2$ (and then we're done, since $ua,va \in L\_1 \cup L\_2$) or $ua,va \notin L\_2$, in which case we know that $ua,va \notin L\_1 \cup L\_2$. But what happens if $u \in L\_2$ and $v \notin L\_2$? Then we seem to be stuck.

Now we switch gears, trying to refute the claim. We got stuck when we had $u,v$ such that $u,v \in L\_1$, $ua,va \notin L\_1$, $u \in L\_2$, $v \notin L\_2$. So we try to look for two right congruent languages for which two such words exist. In order to do that, we need first to think of examples of right congruent languages. One very simple example is the language of even-length words. We can enrich the repertoire by taking the language of all words having an even number of some letter $a$.

Here are two examples of this sort: take $L\_1$ to be all words with an even number of $0$s, and take $L\_2$ to be all words with an even number of $1$s. We can take $u = \epsilon \in L\_1 \cap L\_2$ (here $\epsilon$ is the empty word) and $v = 1 \in L\_1 \setminus L\_2$. Since we want $ua,va \notin L\_1$, we take $a = 0$. Then $u0,v0 \notin L\_1$ while $u0 \in L\_2, v0 \notin L\_2$. So $u0 \in L\_1 \cup L\_2$ but $v0 \notin L\_1 \cup L\_2$, and we have found our counterexample!

As you can see, finding a counterexample is often more creative then proving a statement, which can be quite mechanical. You just need to try a lot of things until something works.

The next step is to reflect on what we have shown. Is there any other operation on two languages which preserves the property of being right congruent? Is there an operation on *one* language? Indeed, there are: if $L$ is right congruent then so is $\overline{L}$; and if $L\_1,L\_2$ are right congruent then their *symmetric difference* $L\_1 \triangle L\_2$ is right congruent. See if you can prove these claims.

(In fact, right congruent languages are exactly the languages accepted by a DFA with at most two states. This leads to a complete classification of these languages, which I leave to the reader.)

---
Tags: formal-languages
---


# Question
Title: Context-free Grammar To Generate $L=\{a^nb^k | 1 =< n =< 2k }
I need to write a context-free grammar for this Language :

```
$\L = {a^nb^k | 1 =< n <= 2k}

```

Please help me solve this problem! Thanks.

# Answer
You can break up this problem into two parts: starting with the shortest legal string with $n$ a's, you can follow it with zero or more b's and still be legal, so you have a string in your language will be the concatenation of $L$ and $X$, where $L$ generates the smallest legal strings and $X$ generates the extra b's.

The $X$ part is easy to produce: $X\rightarrow bX\mid\epsilon$.

Now for the $L$ part we have two cases: the number of a's is even or odd. If we have $a^{2k}$ then we need at least $k$ b's. That's easy to generate as well: $E\rightarrow aaEb\mid aab$, since we're not allowed to have zero a's. If, $n$ is odd, then we must have $2k+1$ a's and $k+1$ or more b's, which is to say we need to generate $aa^{2k}b^{k+1}=aa^{2k}b^kb$. That gives us two subcases: either $ab$ or $a..b$ with $a^{2k}b^k$ inside. That's also easy: $O\rightarrow ab\mid aEb$. Putting all this together, a grammar for your language is $$\begin{align} S &\rightarrow LX\\ L &\rightarrow E\mid O\\ E &\rightarrow aaEb\mid aab\\ O &\rightarrow aEb\mid ab\\ X &\rightarrow bX \mid \epsilon \end{align}$$ Of course we could simplify this a bit. For a more detailed tutorial on this topic, you could look here.
> 2 votes

# Answer
Here's how I would break it down:

Your language consists of an `a` followed by some number of `b`s, or two `a`s followed by at least 4 `b`s, or...

In other words, you take the previous definition and add `abb` to the middle, or some number of `b`s to the end

`L := M | L b
M := a b b | a M b b`

(`L` here is the "add stuff to the end" part, and `M` is the "add stuff to the middle" part)

Note that you can write this more simply if you allow repeats and optionals.

Then your language becomes simply:

`L := a (L) b b b*`

That is, your language consists of an `b`, followed optionally by another statement in the language, followed by two `b`s, followed by zero or more `b`s.
> 0 votes

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


# Question
Title: Partition array - elements non-negative and negative. Minimal number of replacements of elements
I consider following problem:
It is given array with numbers, for example $\[-2,0,1,-324,213,321,-2\]$.
The problem is: replace elements such that negative numbers precede the non-negative. For our example: $\[-2, -324, -2, 321,0,213,1\]$.
Additional requirement is that algorithm should do minimal number of replacements.

**My approach**
Let's use partition from qsort algorithm - pivot is always $0$. It does $\lfloor n/2\rfloor $ replacements.
I think that it is minimal number. It is because of pesimistic case:
$|\[1,1,..,1,-1,-1,...-1\]|=n$ - in this case we must do at least $\lfloor n/2\rfloor $ replacements.

*Can you give me algorithm that do less than $\lfloor n/2\rfloor$ replacements ?*

# Answer
> 2 votes
Hint:

Create a new array $B=\[\]$ where $B\[i\]=1$ if $A\[i\]\<0$ and $2$ elsewhere. You can prove that sorting $B$ is same as performing said operation on $A$

So now, We have to sort an array which only contains two values. You can do this by a greedy algorithm, whose proof you can obtain by the principle of Induction.

As an extra hint: Let $B=\[1.....1,2.....2,1,........\]$. where C is another segment of the array. You have to do something now.

Trust me this is great help. You can continue from here.

As for why it requires fewer(or equal) than $n/2$. The proof is quite easy, once you've devised the algorithm.

---
Tags: algorithms, arrays, lower-bounds
---


# Question
Title: Partitions of a directed graph - common prey and common enemy partitions
Let $D=(V,E)$ be a finite directed graph with no isolated nodes(from every node there is at least one edge entering and one exiting). For $v \in V$ define the following sets: $$v^+= \left\\{w \in V|(v,w)\in E \right\\}, v^-= \left\\{w \in V|(w,v)\in E \right\\}$$

For some $S \subseteq V$ we have, $S^+= \bigcup\_{v \in S} v^+, S^-= \bigcup\_{v \in S} v^-$.

Now define two related graphs, $G\_{cp}=(V,E\_{cp}),G\_{ce}=(V,E\_{ce})$ such that for two distinct nodes $v,w \in V$ we have $vw \in E\_{cp}$ iff $v^+ \cap w^+ \neq \emptyset$ (we identify this by condition $C(p)$, and $vw \in E\_{ce}$ iff $v^- \cap w^- \neq \emptyset$ (condition $C'(p)$ (The notations cp and ce come from "common prey" and "common enemy" )

Let $B\_1,B\_2,...,B\_p$ be the sets of nodes of the connected components of $G\_{cp}$ and $A\_1,A\_2,...,A\_k$ be the set of connected components of $G\_{ce}$. Obviously those sets are two partitions of $V$

Prove that $(B^+\_1,B^+\_2,...,B^+\_p)$ and $(A^-\_1,A^-\_2,...,A^-\_k)$ represent partitions of $V$. Also prove that $p=k$ (that is both graphs have the same number of connected components).

To prove the first part I thought about taking some arbitrary $v \in V$ and than proving that $v$ is in $(B^+\_1,B^+\_2,...,B^+\_p)$. Then a proof by contradiction may be required to complete the first part, but I can't quite seem to make the connection. I don't even know how to start proving $p=k$. Could you help, give me some hints that I miss or something?

**UPDATE**

So, after some research, it seems that $G\_{cp}$ is a competition graph.

# Answer
> 1 votes
Let $p = p\_1,\ldots,p\_n$ be a sequence of vertices. We say that this is a *+path from $p\_1$ to $p\_n$* if $n$ is even and $(p\_1,p\_2),(p\_3,p\_2),(p\_3,p\_4),(p\_5,p\_4),\ldots,(p\_{n-1},p\_{n-2}),(p\_{n-1},p\_n)$ are all directed edges. In other words, a +path is one that alternates taking the edges in the "correct" and "wrong" ways, starting with a "correct" and ending with a "wrong". A *-path* is defined analogously with the directions reversed.

Say that two vertices $p,q$ are *+equivalent* if there is a +-path from $p$ to $q$. I claim that this is an equivalence relation. Indeed:

* The empty +path connects a vertex with itself.
* The reverse of a +path from $p$ to $q$ is a +path from $q$ to $p$.
* The concatenation of a +path from $p$ to $q$ and a +path from $q$ to $r$ is a +path from $p$ to $r$.

The equivalence classes of this relation are $B\_1,\ldots,B\_p$. If $x \in B\_i$ and $y \in B\_j$ have a common out-neighbor $z$ then $x,z,y$ is a +path from $x$ to $z$, so $i = j$. This shows that the $B\_i^+$ are distinct, and because every vertex has an incoming edge, they form a partition of the vertex set.

We can similarly define -equivalence, whose equivalence classes are $A\_1,\ldots,A\_k$, and show that the $A\_j^-$ partition the vertex set (since every vertex has an outgoing edge).

Take any $x,y \in B\_i^+$, say $(z,x),(w,y)$ are edges for $z,w \in B\_i$ (possibly $z = w$) and there is a +path $\alpha$ from $z$ to $w$. It's not hard to check that $x,\alpha,y$ is a -path from $x$ to $y$. Conversely, suppose that $x \in B\_i^+$ and $y \in B\_j^+$, say $(z,x),(w,y)$ are edges for $z \in B\_i, w \in B\_j$. If there is a -path $\beta$ from $x$ to $y$ then $z,\beta,w$ is a +path from $z$ to $w$, so that $i = j$. We conclude that $\\{B\_1^+,\ldots,B\_p^+\\} = \\{A\_1,\ldots,A\_k\\}$, so $p = k$. Similarly $\\{A\_1^-,\ldots,A\_k^-\\} = \\{B\_1,\ldots,B\_p\\}$.

---
Tags: graphs, partitions
---


# Question
Title: Use subset of training data as prediction data
At our company, we've started using Amazon Machine Learning to predict the likelihood of a certain segment of our customers cancelling their subscription.

We only have 500 customers in that segment so we uploaded training data of all our customers who

* are on a subscription or
* were on a subscription but cancelled

Amazon tells us there's an AUC score 0.70 which is just ok from what I read.

I'm new to Machine Learning so my question is the following:

Out of the 500 customers that are in the training set, can I load the ones that haven't cancelled into the prediction set to predict the likelihood of them cancelling their subscription in the future? Or can I only use the model for new customers that are not included in the training data?

# Answer
> 3 votes
The most important thing is to avoid "testing on the training set". If you trained a model on a set of 500 users and then evaluate how well it performs by testing it on some of those same users, you're committing the "testing on the training set" sin. The consequences of doing that is that your evaluation results will be misleading: they will over-estimate the effectiveness of your model.

There are various standard methods to avoid this problem. One method is to use a holdout set: you set aside, say, 67% of your data for training and the other 33% for testing. You train a model on the first 70% (the training set), and then evaluate how well your model performs on the other 30% (the testing set). This will then give you a reasonable, unbiased estimate of the performance of your machine learning model. In practice, a test+train division is often not enough; for various reasons, you'll often want three sets, a training set, a validation set, and a testing set. You can read more about that in standard resources.

Another reasonable method is to use cross-validation to estimate the effectiveness of your scheme. Basically, this involves repeatedly dividing up the data, learning a model on one portion of the data and evaluating on another portion, and then averaging the results. This is a reasonable alternative to dividing the data into train+validate+test sets, when you don't have a lot of labelled data -- as in your case.

These comments are all about how to build the model, select parameters for your model, and evaluate the model's performance (predict how effective it will be in practice). Once you've done all that and settled on a model, then you can simply apply the model to new customers to predict their likelihood of cancelling their subscription.

Finally, one last comment: your approach assumes uniformity over time: i.e., that the factors that influence behavior in the past will continue to hold in the same way in the future. This may or may not be realistic. For instance, maybe today some people are more likely to cancel cable subscriptions because of the availability of Netflix/Hulu/etc. whereas ten years ago that wasn't as much of a factor. In many areas, things can change over time. Read about concept drift to learn more about that particular challenge.

If this didn't answer your question, edit the question to clarify in more detail what you are asking about.

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


# Question
Title: How to understand the mathematical constraint of potentials?
Good evening! I am studying scheduling problems and I have some difficulties understanding constraints of potentials:

Let be $t\_j$ the time when a task $j$ starts, and $t\_i$ the time when a task $i$ starts. I'm assuming that $a\_{ij}$ is the length of the task $i$ but I'm not sure. Why is a "constraint of potential" mathematically expressed by:

$$t\_j-t\_i \le a\_{ij}$$

Shouldn't it be the reverse, $t\_j-t\_i \ge a\_{ij}$? If we know that the length of task $i$ is $a\_{ij}$, isn't it impossible to do something in less that the necessary allocated time?

# Answer
> 2 votes
I suspect there's some misunderstanding about the definition/meaning of $a\_{ij}$. The time to complete task $i$ depends only on $i$ (not on $j$), so it wouldn't make sense to use notation like $a\_{ij}$ for the length of task $i$: we'd instead expect to see only the index $i$, but not $j$, appear in that notation.

I suspect you'll probably need to go back to your textbook or other source on scheduling and look for a precise definition of the notation that it uses. If your textbook doesn't define its notation, look for a better textbook.

---

As far as the constraint $t\_j - t\_i \le a\_{ij}$, that is expressing that $t\_j$ should start at most $a\_{ij}$ seconds after $t\_i$ starts. So, it'd make more sense for $a\_{ij}$ to be a permissible delay that expresses the maximum time you can wait to start task $j$, once task $i$ has been started.

---
Tags: scheduling, notation
---


# Question
Title: If a language has any single occurrence of a letter, is it not context-free?
From what I understand, the rules for CFL from my notes say:

If $L$ is a language and

• for all integers $N$,

• there is a string $w \in L$ of length greater than $N$ such that

• for all ways of writing $w$ as $uvxyz$ with ($v \neq \epsilon$ or $y \neq \epsilon$),

• there is an $i$ such that $u(v^i)x(y^i)z$ is not in $L$,

then $L$ is not context-free.

Does this mean that if we have any equation like: $L = \\{a^m b a^n \mid m = n\\}$, then we can use this for example: $u=a^m, v=b, x=a, y=a^{n-1}, z=null$

Where we any value of i greater than 1 would make the equation invalid? This gives us $a^m(b^i)(a)((a^{n-1})^i)$ where $b^2$ means that there are two $b$'s, a string that's not accepted in that language.

However, in this case, then a Language $L = \\{bcde \mid b = c = d = \epsilon\\}$ could be proven as not context free. What am I misunderstanding here?

# Answer
No: context free languages are closed under union, so for any CFL language $L$, we have $L \cup \\{ a \\}$ is context free, for any letter $a$.

The trick is that, when applying the pumping lemma, we don't get to choose the length $L$.

For a finite language, you just choose $L$ to be larger than any word in the language, and the pumping lemma trivially holds. (Remember, $a \implies b$ is true whenever $a$ is false).

As an intuition, you can see the "length" part of the lemma as being how long of words we need to get to a part of the automaton with loops, or a part of the grammar with recursion. So the small examples will in general not affect the pumping property.
> 2 votes

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


# Question
Title: Maximum Spanning Tree vs Maximum Product Spanning Tree
So I'm kind of wondering if I'm correct on something relating to an algorithms class. Let's say I want to, for whatever reason, find the maximum spanning tree of a graph such that the edge weight is at maximum instead of minimum.

In addition, let's say I want to find a spanning tree with the maximum product-sum weight (the product of the edges of the spanning tree is at its maximum).

Assuming edge-weights must be greater than 0, would their spanning trees contain the same edges? I'm pretty sure that their spanning trees are equal.

Plus, I also believe that a modified Kruskal's algorithm searching for maximum weighted edges would create these spanning trees since you'd want the largest weights for both types of maximum trees.

Is my thinking correct?

# Answer
> 3 votes
You state several beliefs but no reasoning. In math, if things are true then usually there is a good reason, namely a *proof* that the thing is true. Don't just make guesses, try to prove that your claims hold.

Regarding your conjecture, consider Kruskal's algorithm, modified so that it arranges the weights in decreasing rather than increasing order. If we apply any monotone increasing function on the weights, the algorithm would make exactly the same choices. Consider what happens when you replace each weight $w$ by its logarithm $\log w$. The weight of a spanning tree containing the edges $e\_1,\ldots,e\_{n-1}$ is then $$ \log w(e\_1) + \cdots + \log w(e\_{n-1}) = \log \[w(e\_1) \times \cdots \times w(e\_{n-1})\]. $$ In other words, after replacing all weights with their logarithms, you are actually computing the maximum spanning tree with respect to product. Since both algorithms compute the same spanning tree, your conjecture is correct.

---
Tags: graphs, spanning-trees, minimum-spanning-tree
---


title: Subset-sum variation, multiple sums

text:
# Question
Title: Subset-sum variation, multiple sums
Subset-sum problem is NP-complete. I presume so is the problem of determining, given a positive integer $p$, whether in a set of positive integers $\\{x\_1,x\_2,...,x\_n\\}$ there is a subset which sums to one of the numbers $\\{p-1,p,p+1\\}$. Am I correct?

I've been struggling to reduce standard Subset-sum to this variation, but for no good so far. Can you see any other reduction? Or could give me a hint on this one? Perhaps I'm fixed for that Subset-sum and don't some other obvious possibility.

# Answer
Hint: Given an instance $\\{x\_1,\ldots,x\_n\\},T$ of SUBSET-SUM, construct the instance $\\{2x\_1,\ldots,2x\_n\\},2T$ of your problem.
> 1 votes

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


# Question
Title: What is the state of the art in encapsulated search in functional logic programming?
I am particularly interested in solutions to the problem that encapsulated search can depend on the order of evaluation.

According to \[1\], encapsulated search in PAKCS depends on the order of evaluation, while in MCC, it does not, but using it requires knowledge of the compiler implementation and it does not follow the Curry language specification. This was written in 2007, so it may of course be out of date now.

KiCS2 returns results from encapsulated search in the IO monad, but I do not understand why.

\[1\] Braßel and Huch, *On a Tighter Integration of Functional and Logic Programming*, Proc. APLAS 2007

# Answer
> 1 votes
The reasons for using the IO monad appear to be described in Braßel and Huch and Hanus, 2004, but I cannot find a clear reason given for using a list instead of a set. I guess it is so the list can be elaborated lazily.

It seems that the approach described in the 2007 paper was unsatisfactory for some reason (I don't know why), because KiCS2 has gone back to the "API" described in the 2004 paper, i.e. using the IO monad. (There is an unsafe version which does not use the IO monad, but that is not referentially transparent!)

# Answer
> 1 votes
See http://www-ps.informatik.uni-kiel.de/kics2/lib/Findall.html: it says `IO` based approach is deprecated and the prefferred way not is Curry's `SetFunctions` module, This new design does away with `IO`-wrapped return values and has other means to avoid leaking indeterminism and referential non-transparency into the pure-FP land.

---
Tags: reference-request, functional-programming, nondeterminism, logic-programming
---


# Question
Title: Can you solve 2-sat problem when truth assignments of some variables are determined
I am trying to find a assignment to satisfy a 2-sat statement. Problem is some of the clauses are `0 or x` or `1 or x`. I think the `1 or x` clauses have no effect on the solution, but the `0 or x` clauses determine the value for x. As I have clauses like `~x or y` the determined value for x results in determining the value for y and so on. Can I solve this problem with Krom's procedure?

# Answer
> 9 votes
First set all literals $x$ to $1$ if they appear in a clause $0 \vee x$, and set $\bar x$ to $0$. If that requires you to set some $x$ to both $0$ and $1$, it's unsatisfiable. Iterate this until you don't have to set any more literals to $0$. If you get this far without finding out that the formula is unsatisfiable, remove all clauses that contain a $1$. Now you either have no clauses left - then it's satisfiable - or some 2-CNF formula to which you can apply Krom's algorithm.

Alternatively, remove all clauses $1 \vee x$ and replace all clauses $0 \vee x$ by $(y \vee x) \wedge (\bar y \vee x)$ for a newly introduced variable $y$. You can directly apply Krom's algorithm (or more likely, a linear-time algorithm like that of Aspvall, Plass, Tarjan) to the formula you get this way.

# Answer
> 7 votes
Also a similar solution is to define `Zero` and `One` variables and add two extra clauses $ \bar{zero} \vee \bar{zero} $ for value 0 and $ one \vee one $ for value 1. After that we can follow the Krom's algorithm.

---
Tags: 2-sat
---


title: Assignment based on ranked preference

text:
# Question
Title: Assignment based on ranked preference
Assume that there are `n` students, who have to be evenly assigned to `m` groups. For every student, a preference ranking of of the `m` groups is given.

I partially order assignment by pointwise preference, i.e. one is better or equal to another if for every student, the assigned group is ranked higher or equal.

What algorithm can I use find “locally optimal” solutions, i.e. assignments where there are no strictly better solutions?

I assume there will be multiple locally optimal solutions. Is there a sensible way to order them without giving the students an incentive to be dishonest in their ranking, i.e. without encouraging strategic voting? If so, can that be solved?

And finally: What are the right terms to search for research that solves this and related problems?

# Answer
The terms you can use to search the literature are stable marriage and the assignment problem.

As far as discouraging strategic voting, one relevant term might be strategy-proof. This might also be relevant to the general area of mechanism design. My vague recollection is that discouraging strategic voting in stable-marriage-like problems is a hard problem, but I don't know if I'm remembering that right.

For instance, consider stable marriage. The traditional algorithm gives a matching that is male-optimal and female-pessimal (every male gets the best possible mate he possibly could have received in any stable matching; and every female gets the worst possible mate she could have received in any stable matching). Now suppose the females all get together and collude. In a world of perfect information, they can compute what the female-optimal matching would be, and then change their reported preferences to ensure that the female-optimal matching will be selected.

In fact, collusion is not necessary -- the same result happens if each female individually acts in their own self-interest, without any cooperation or conspiracy. Assume again a world of perfect information, where everyone's true preferences are known (to the females, at least). Then each female can compute the best possible mate she could hope for, i.e., the best mate out of all possible matches in all possible stable matchings; she can then change her reported preferences to list that male as her first preference. If the men use their true preferences and each woman uses this procedure to select her preferences strategically, and then we run the traditional algorithm, we end up with the female-optimal (and male-pessimal) matching. Each woman has an incentive to behave in this way, and no collusion is necessary (assuming perfect information).
> 2 votes

---
Tags: optimization, combinatorics, matching, voting
---


title: Bit-parallelism and NFA simulation

text:
# Question
Title: Bit-parallelism and NFA simulation
In several papers I have read that Bit-parallel pattern matching is an NFA-simulation.

My questions are:

1- Is it true in general? Or, is there any restrictions?

2- As any regular expression can be converted to NFA, how Bit-parallelism is able to handle some regex like: a?5

Update: Bit-parallel pattern matching is a family of well-known pattern matching algorithms in the literature of hardware-based pattern matching. It was introduced by Baeza-Yates and Gonnet (*A New Approach to Text Searching*, *Communications of the ACM*, 35(10):74–82, 1992; PDF) and has gained more attention recently, for example in Faro and Lecroq, *Twenty Years of Bit-Parallelism in String Matching* (*Festschrift for Bořivoj Melichar*, pp. 72–101; PDF).

In these papers there are several statements like: "Bit-parallelism is indeed particularly suitable for the eefficient simulation of non-deterministic automata.", second reference, page 2.

# Answer
on p4-5 of your 2nd ref by Faro and Lecroq they write:

> Online string matching algorithms (hereafter simply string matching algorithms) can be divided into three classes: algorithms which solve the problem by making use only of comparisons between characters, algorithms which make use of deterministic automata and algorihtms which simulate nondeterministic automata using bit-parallelism.

however, while sounding general, these statements seem to be wrt "within the realm of string matching algorithms". in other words there is massive use/ research of bit parallelism of NFAs *for string matching algorithms in particular,* but have not seen much bit parallelism ideas applied to *arbitrary* NFAs, even though it is clearly applicable. here are two refs turned up that do consider bitwise operations on a more *general/ arbitrary* case (apparently the focus of your question). in the 2nd case, "vector algorithms" are capable of/ nearly the same as "bit parallelism".
> 0 votes

---
Tags: automata, finite-automata, pattern-recognition, matching, dfa
---


# Question
Title: Can a Turing machine have infinite states?
Does it make sense for a Turing machine to have infinite number of states ? I had previously asked a question Can Turing machines have infinite length input. From which I came to know about Type-2 Turing machines. If there can be infinite states, encoding of such a Turing machine would be infinite ( but again I am not sure if it make sense to encode a Turing machine with infinite states thus having an infinite description ). So it would make sense that if I have to give the encoding of such a Turing machines as input, I would give it as input to Type-2 Turing machines.
But is there any use of infinite states ( and what is there link to Type-2 Turing machines ? ) ? If I am not wrong there is no function which is uncomputable by normal Turing machine but computable by Turing machine with infinite states.

# Answer
> 14 votes
No. The definition of Turing machines requires that the finite-state control unit have a *finite* number of states. It's not allowed to have an infinite number of states.

A machine that could have infinitely many states in its control could accept any language (unlike a Turing machine). However such a machine could not be implemented in practice. For these two reasons, it would not be a good model of the computational power of real computers.

In addition, once you allow an infinite-state automaton, there's no need to have any tape -- the tape doesn't add any computational power, because an infinite-state automaton can already do "everything". For these reasons, while it would be possible to construct machines that look like Turing machines but have infinite state, there would be little point: their power would be equivalent to an infinite-state automaton on their own, i.e., every language can be accepted by such a machine.

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


title: coding theory- perfect codes

text:
# Question
Title: coding theory- perfect codes
I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows:

You are given that $C \subseteq D \subseteq F^n\_q$ where $|C| \< |D|$ and $C$ is a perfect code. Show that $d(C) \> 2d(D)$.

I have been using the fact that $C$ is a perfect code so it attains the Hamming bound then saying that it is less than the Hamming bound for $D$, but you get an inequality involving a binomial sum on both sides, which is really messy. I'm not really sure what other properties I can use to work this out. Any help would be really appreciated, thanks

# Answer
Guidelines for the future: start with reviewing the definitions.

According to Wolfram, a **perfect code** (with distance $d=2e+1$) is one such that "for every possible word $w\_0$ of length $n$ with letters in $A$, there is a unique code word $w$ in $C$ in which at most $e$ letters of $w$ differ from the corresponding letters of $w\_0$."

OK, but this is cheating.

So let's start with an equivalent definition:

> A code $C$ is perfect if it attains the Hamming bound

what is this Hamming bound? Basically, it's a counting argument. If you have a word $w\in F^n\_q$, how many words are there with in $F^n\_q$ whose distance from $w$ is at most $e$? If you do the counting, you will get there are exactly $\sum\_{i=0}^e \binom{n}{i} (q-1)^i$ such words. <sub>\[Why? If the distance is $i$, choose $i$ indices (out of the $n$ possible indices), each such index can get any of the $q-1$ different values from $w$ in that index.\]</sub> The bound then says that if we split the universe into disjoint "balls" where each ball contains a center $w$ and all the $\sum\_{i=0}^e \binom{n}{i} (q-1)^i$ words within distance $e$ from $w$, we will have at most $$\frac{|F^n\_q|}{size(ball)} = \frac{q^n}{\sum\_{i=0}^e \binom{n}{i} (q-1)^i}$$ such (disjoint) balls.

A code that attains the Hamming bound means that any word is within distance $e$ of **some** codeword. That is, if you think on each codeword in $C$ as a center of a ball with radius $e$, then the codewords cover the entire universe: no word in $F^n\_q$ is left outside some ball. Note that the distance of this code is $2e+1$: two codewords belong to two different "balls", and each ball is of radius $e$ (in Hamming distance).

But if the entire space is covered with balls, it means that any word is within distance $e$ of some codeword. This is exactly the first definition I wrote in this post. Thus, if you take any other word and make it a codeword, this word already belongs to some ball, so it is within distance $e$ from the center of that ball, and the new code cannot have a minimal distance greater than $e$.
> 3 votes

---
Tags: discrete-mathematics, coding-theory, hamming-code
---


title: Paxos consistency

text:
# Question
Title: Paxos consistency
I'm looking at the paxos family of protocols for solving consensus in a network of unreliable processors. I'm working through scenarios where processors fail, and I know I'm wrong, but I don't know why.

I have 3 machines with the state A.

1. One machine goes down.
2. The client requests a state change. Paxos works, and machines 2 and 3 have the state B.
3. The client requests a state change, prepare and promise phases are completed successfully.
4. A second machine goes down
5. The proposer sends an Accept Request message
6. The machine accepts the new value

At the end each machine has a different value: A, B and C.

I thought that Paxos can never left the system in a inconsistent state, I think that my problem is that I don't understand what Paxos safety properties really are.

# Answer
> 3 votes
In your example no client gets a confirmation that the value was written hence the system is in undefined state, but it is consistent with its history. To read a value a client should initiate a new round of Paxos. The main result of the "Paxos made simple" is that if a value was reported as chosen then any further rounds of Paxos will propose the same value.

---
Tags: algorithms, distributed-systems, consensus
---


# Question
Title: String matching for wildcard-based records
Let's say that we have a string `"1.2.3"` and want to find a match for it in the following records:

```
1.2.9
1.4.5
1.*.3

```

For each record:

* The `.` is a separator that divides the string into segments.
* Each segment can have a static value or `*` that matches any segment value.
* There are no duplicated records. If there are multiple matches for a given string, only one is returned, following an exact match and left to right rule. So, for the following hypothetical matches for `1.2.3`, the previous has priority over the latter: `1.2.3` \> `1.2.*` \> `1.*.3` \> `*.2.3`.

In the initial example, the matching record will be "1.\*.3".

**Note:** here, the numbers used to represent a record are a simplification of a more complex, unpredictable, variable-sized value, such as `abc.wxyz.fghijklm`. So it is not possible to build tables for possible wildcard values.

I'm looking for the (theoretically) fastest lookup algorithm to find a matching record in memory given these non-requirements:

* Longest prefix matches are not a requirement;
* Only lookup speed matters: record insertion or deletion are not required to be fast;
* Memory space efficiency is not a requirement.

I experimented a range of trie variants and I am guessing (sorry if this sounds naive) that tries, or any datastructure, can't find a match for the proposed problem without backtracking. I'd appreciate some comments on this.

So, which datastructure would best fit my (non-)criteria?

# Answer
One candidate approach would be build a BDD or a deterministic finite-state automaton that accepts all strings that match at least one of the records in your set of records. These data structures can handle wildcards. To use a BDD, treat each segment as a bit string, so the alphabet is $\\{0,1,.\\}$ (perhaps it's now a *trinary* decision diagram rather than a binary decision diagram, but the ideas remain the same).

---

An alternative approach (if the number of segments per string will always be relatively small): You can solve your problem by building a set of indices, one index for each subset of possible segments.

Suppose we're guaranteed that every string will have exactly 3 segments, call them segments ABC. We're now going to build seven indices:

* The ABC index contains the set of all records with no wildcard. e.g., `1.2.3`
* The AB index contains the set of all records with a single wildcard, in the 3rd (C) segment. e.g., `1.2.*`
* The AC index contains the set of all records with a single wildcard, in the 2nd (B) segment. e.g., `1.*.3`
* The BC index contains the set of all records with a single wildcard, in the 1st (A) segment. e.g., `*.2.3`
* The A index contains the set of all records with two wildcards, in the 2nd and 3rd (B and C) segments. e.g., `1.*.*`
* The B index contains the set of all records with two wildcards, in the 1st and 3rd (A and C) segments. e.g., `*.2.*`
* The C index contains the set of all records with two wildcards, in the 1st and 2nd (A and B) segments. e.g., `*.*.3`
* I assume you won't have any records with three wildcards (`*.*.*`), but if that was possible, you'd have an 8th index that records whether you have such a record or not.

Each index is stored as a hash table, so given a string you can quickly (in $O(1)$ time) check whether that string is present in that index.

Now, when you receive a string `4.5.6`, you look it up in each index. For instance, you look up `4.5.6` in the ABC index, `4.5.*` in the AB index, `4.*.6` in the AC index, and so on. If any of these lookups succeeds, then you know that `4.5.6` matches one of the records. Otherwise, `4.5.6` does not match any of the records. The running time for a lookup is $O(1)$.

If you know that every string will have exactly 5 segments, you'll need 31 indices and the time for a lookup is $O(1)$ (31 lookups into 31 hashtables). If every string has exactly 5 segments and you know that no record will have more than 2 wildcards, then it's enough to have $1+5+10=16$ indices.

This will probably be OK for your particular parameters, where every string has at most 5 segments. Obviously, though, if the number of segments is too large, this will be extremely slow and inefficient.
> 2 votes

# Answer
Edit: I was short on time earlier, but I'll expand my reasoning a bit:

Assumptions:

1. No bound on insertion time or memory size.
2. Lookup speed should be minimal, ie O(query length) which is the time to read the input.
3. Backtracking during search or any extra search time beyond O(length) would violate #2.

Given that there are no constraints on memory or insertion time, one solution is to enumerate each wildcard during insertion, with backtracking, and insert each key generated in a trie or hash table.

So for 1.\*.3 above you generate 1.0.3, 1.1.3, ... and insert them into the index. For multiple wildcards this obviously becomes large, but it guarantees that any match will be found as-is in the index.

This idea simply moves any backtracking to the insertion phase, and guarantees optimal search times.

Rivest also gives some ways to bound this process if #1 is not actually true; his approach in this case would be to reduce the number of keys in the index by allowing some wildcards, but only up to a fixed number k, so that the amount of backtracking during search is O(1).

A quick example:

Say k=1 but we're inserting a key $2.\*.3.\*$; we generate all keys

```
2.[0-9].3.* = 2.0.3.*, 2.1.3.*, etc.
2.*.3.[0-9]

```

And insert them in the index. Then at search time, if we have a key

```
2.1.3.1

```

We generate and search for all 1-wildcard variants:

```
*.1.3.1
2.*.3.1  (match)
2.1.*.1
2.1.3.*  (match)

```

and probe for those exact strings; the number of variants is bounded by our choice of k (and the key length).

=== original:

Your situation is a bit reversed from the usual partial match problem, where the wildcards appear in the queries, but the data is fixed.

If the number of wildcards is bounded, you can expand the wildcards on insertion to get o(length) lookup time.
> 1 votes

---
Tags: algorithms, data-structures, search-algorithms, regular-expressions, strings
---


# Question
Title: Closure properties of undecidable languages
I know that the decidable are close under: complementation, union, intersection and concatenation?

What about the undecidable languages? I think they are close under complementation, but not under concatenation, union and intersection. But I don't know how to prove it...

My prove

> "Lets say L is undecidable lang. Because L is undecidable lang we know one of the following:
>
> 1. there is a word w1 from L that there is no TM that stop for this word
> 2. there is a word w2 in L that stopping in reject state in every TM
> 3. there is a word w3 Not from L that stopping in accept state in every TM
>
> L' is the complementation lang of L
>
> If 2, the word w2 that stopping in reject state, will stop in the accept state for every TM, but w2 not in L' so L' is Undecidable.
>
> If 3, the word w3 that stopping in accept state, will stop in the reject state for every TM, but w2 is in L' so L' is Undecidable.
>
> If 1, so all the TM are not stopping for w1 so L' is Undecidable???? "

# Answer
> 2 votes
Let $K$ be some undecidable language. Define languages $A\_0,A\_1,B\_0,B\_1$ as follows: $$ A\_0 = \\{ 0 w : w \in K \\}, A\_1 = \\{ 1 w : w \in K \\}, \\ B\_0 = A\_0 \cup \\{ 1 w : w \in \\{0,1\\}^\* \\}, B\_1 = A\_1 \cup \\{ 1 w : w \in \\{0,1\\}^\* \\}. $$ See if you can use these languages to show that the collection of undecidable languages is not closed under concatenation, union or intersection.

As for complementation, try to use the fact that if you can decide a language $L$ then you can decide its complement $\overline{L}$ (why?).

---
Tags: computability, undecidability, closure-properties
---


# Question
Title: Do iterative DNS queries return results from the servers cache?
So if i only used iterative requests to a recursive dns server and since this server has cached results from recursive queries, does this mean the iterative request gets a result from the cache or just a response with a difference server to check?

Example for clarification:

User requests example.com recursive dns server doesn't have it so fetches and saves the ip in cache iterative request made to this server does the response return the cached result or just another server ip?

# Answer
> 1 votes
Cached data about a domain for which a DNS server is not authoritative could only have come from prior recursive queries. If you send a query without the RD (recursion desired) bit set, the server is not going to send you any of the cached recursive data that it has. If the server is authoritative for the domain you asked about then it will answer authoritatively, otherwise the answer section of the response will be empty.

---
Tags: computer-networks, communication-protocols
---


title: Regular Expression for the given DFA

text:
# Question
Title: Regular Expression for the given DFA
Hi, what should be the regular expression for this language ? My guess was

r = (a ∗ a(a + b) ∗ (a + b) + (a ∗ b + c))(a + b ∗ ) ∗

But the arrow from C to B is making it tough . If it was B to C then my answer would have bee correct.

# Answer
> 0 votes
Assuming that the alphabet of your DFA is $\Sigma=\\{a,b,c\\}$ it doesn't meet the standard definition of the transition function.

$M = \\{Q,\Sigma,\delta,q\_0,F\\}$

$\delta: Q\times \Sigma \rightarrow Q $

If you have a valid DFA then I suggest to use a proved algorithm(like State Removal Method for example) to transform it into a regular expression.

---
Tags: automata, finite-automata, regular-expressions
---


title: fastest counting of nested loops

text:
# Question
Title: fastest counting of nested loops
I need to find out the fastest way to count nested loops. I am adding 3 numbers , the final number is wanted result. For better explanation here is example

```
   read number 1
   read number 2
   read final number 3

```

There are 17 ways how to achieve 500 with those two numbers e.g

```
10*2 + 15*32

```

and so on , the code for this is pretty simple

```
 i_max=final_number/number1
 j_max=final_number/number2
for(i=0;i<i_max;i++){

     for(j=0;j<j_max;j++){
             count=number1 * i;
              count_two = number 2 * j;
               if(count+count_two==final_number){
                    //print it
}
}}

```

This code works fine , but the problem is when i input large numbers like

```
number1=100
number2=500
final_number=50000000

```

in this case , the computer takes very long time to count/find/print all possible ways. Is there any way to make alghoritm for this as fast for big numbers too? I have found out that the better way and fastest is not to increment i by 1 but by whole number or whole number /2 and sometimes both of them ; but how can i decide if i should add whole number or just half of the number to the i/j?

I tred to write in as much in pseudo code as i could

Also , i find out the second loop does not have to start always from 0/max number everytime it gets triggered , so

```
for i=0 ; i<max_number1;i++
  for j=max_number2;j>=0;j--
    if number1*i + number2*j == final number
     max_number 2 = j

```

But i still fail to find when should i add whole number and when just half of it, I tried to increment first number by half of number2 , and second number by 1 until it finds match and then adding whole numbers , but this didnt work as i expected it worked for larger numbers but for numbers like

10 13 100 it said there is now way to combine first two and make 100 while there is a one `10 * 10 + 13 * 0`

On request / for those who got lost in my explanation = i input 3 random numbers e.g 10 13 749 and i want to find out how many combinations of first two nubmers

```
10
13

```

would get result `749` it made it with nested loops

```
for(j=0;j<j_max;j++){
                 count=number1 * i;
                 count_two = number 2 * j;
                   if(count+count_two==final_number){
                        //print it
    }
    }}

```

which works but takes very long time to calculate if i input large numbers , for things i have tried or come up with read whole post.

Full example = number 1=757 number 2=989 final number = 56899148 There is 77 way how to combine first two numbers into the final one and those are

```
757 * 0 + 989 * 57532
 757 * 989 + 989 * 56775
 757 * 1978 + 989 * 56018
 757 * 2967 + 989 * 55261
 757 * 3956 + 989 * 54504
 757 * 4945 + 989 * 53747
 757 * 5934 + 989 * 52990
 757 * 6923 + 989 * 52233
 757 * 7912 + 989 * 51476
 757 * 8901 + 989 * 50719
 757 * 9890 + 989 * 49962
 757 * 10879 + 989 * 49205
 757 * 11868 + 989 * 48448
 757 * 12857 + 989 * 47691
 757 * 13846 + 989 * 46934
 757 * 14835 + 989 * 46177
 757 * 15824 + 989 * 45420
 757 * 16813 + 989 * 44663
 757 * 17802 + 989 * 43906
 757 * 18791 + 989 * 43149
 757 * 19780 + 989 * 42392
 757 * 20769 + 989 * 41635
 757 * 21758 + 989 * 40878
 757 * 22747 + 989 * 40121
 757 * 23736 + 989 * 39364
 757 * 24725 + 989 * 38607
 757 * 25714 + 989 * 37850
 757 * 26703 + 989 * 37093
 757 * 27692 + 989 * 36336
 757 * 28681 + 989 * 35579
 757 * 29670 + 989 * 34822
 757 * 30659 + 989 * 34065
 757 * 31648 + 989 * 33308
 757 * 32637 + 989 * 32551
 757 * 33626 + 989 * 31794
 757 * 34615 + 989 * 31037
 757 * 35604 + 989 * 30280
 757 * 36593 + 989 * 29523
 757 * 37582 + 989 * 28766
 757 * 38571 + 989 * 28009
 757 * 39560 + 989 * 27252
 757 * 40549 + 989 * 26495
 757 * 41538 + 989 * 25738
 757 * 42527 + 989 * 24981
 757 * 43516 + 989 * 24224
 757 * 44505 + 989 * 23467
 757 * 45494 + 989 * 22710
 757 * 46483 + 989 * 21953
 757 * 47472 + 989 * 21196
 757 * 48461 + 989 * 20439
 757 * 49450 + 989 * 19682
 757 * 50439 + 989 * 18925
 757 * 51428 + 989 * 18168
 757 * 52417 + 989 * 17411
 757 * 53406 + 989 * 16654
 757 * 54395 + 989 * 15897
 757 * 55384 + 989 * 15140
 757 * 56373 + 989 * 14383
 757 * 57362 + 989 * 13626
 757 * 58351 + 989 * 12869
 757 * 59340 + 989 * 12112
 757 * 60329 + 989 * 11355
 757 * 61318 + 989 * 10598
 757 * 62307 + 989 * 9841
 757 * 63296 + 989 * 9084
 757 * 64285 + 989 * 8327
 757 * 65274 + 989 * 7570
 757 * 66263 + 989 * 6813
 757 * 67252 + 989 * 6056
 757 * 68241 + 989 * 5299
 757 * 69230 + 989 * 4542
 757 * 70219 + 989 * 3785
 757 * 71208 + 989 * 3028
 757 * 72197 + 989 * 2271
 757 * 73186 + 989 * 1514
 757 * 74175 + 989 * 757
 757 * 75164 + 989 * 0

```

Again this works , but with very big numbers it takes lot of time to actually calculate it.

# Answer
With inputs $n\_1,n\_2,n\_3$, you want to find all positive integers $(a,b)$ such that $an\_1+bn\_2 = n\_3$ You observed that for even moderately large inputs, your two nested loops with a test to see if you come up with a solution takes a long time. It you apply a bit of number theory, there's an algorithm that is very much faster.

1. First, find the greatest common divisor of $n\_1$ and $n\_2$. The extended euclidean algorithm is not only very fast (using a number of steps proportional to the number of digits in the larger of the two numbers), but also provides a way to do the next step. If $g=\gcd(n\_1,n\_2)$ divides $n\_3$, continue to the next step, otherwise there will be no solutions to your problem, so quit.
2. The extended Euclidean algorithm will give you integer solutions, $a, b$ to $$ an\_1+bn\_2=g $$ In what follows, we'll assume $g=1$ for simplicity. If it's not, just divide $n\_1,n\_2,n\_3$ by $g$ and carry on as below. We'll then have $$ (an\_3)n\_1+(bn\_3)n\_2 = n\_3 $$ You're getting close to a solution, but $an\_3$ or $bn\_3$ might not both be positive, so we'll need some other solution. Observe that for any integer $k$, $$\begin{align} & (an\_3-kn\_2)n\_1+(bn\_3+kn\_1)n\_2\\ =&\ (an\_3)n\_1-kn\_2n\_1+(bn\_3)n\_2+kn\_1n\_2\\ =&\ (an\_3)n\_1+(bn\_3)n\_2 = n\_3 \end{align}$$ so $an\_3-kn\_2$ and $bn\_3+kn\_1$ will also be solutions, for any integer $k$.
3. Now all we have to do is pick $k$ values such that $$ an\_3-kn\_2\ge 0\quad\text{and}\quad bn\_3+kn\_1\ge 0 $$ In other words, all we have to do is loop through the integers $k$ such that $$ -\frac{bn\_3}{n\_1}\le k\le\frac{an\_3}{n\_2} $$

**Edit:** There's a potential problem here, though: it might be that some of the intermediate calculations might be too large to avoid integer overflow. Let's see if we can keep everything no larger than $n\_3$. We could let $k=a\lfloor n\_3/n\_2\rfloor$ and it's not hard to show that $$ a'=an\_3-kn\_2=an\_3-a\left\lfloor\frac{n\_3}{n\_2}\right\rfloor n\_2\>0 $$ and then let $$ b'=\frac{n\_3-a'n\_1}{n\_2} $$ we will have found a solution, $(a',b')$ to $$ a'n\_1+b'n\_2=n\_3 $$ which was our goal.

---

Here's how it would work for an example almost like yours with $n\_1=989$, $n\_2=757$, $n\_3=56899150$.

First, find $\gcd(989,757)=1$, and we find from the extended Euclidean algorithm that $$ 1=(62)989+(-81)757 $$ so we let $$\begin{align} a'&=62\left(56899150-757\left\lfloor\frac{56899150}{757}\right\rfloor\right)\\ &= 62(56899150-757\cdot75164)\\ &= 62(56899150-56899148)\\ &= 62\cdot 2 = 124 \end{align}$$ and we also find that $b'=75002$, so we'll have solutions $(a',b')$ given by $$\begin{array}{cc} a' & b'\\ 124 & 75002 \\ 881 & 74013 \\ 1638 & 73924 \\ \vdots & \vdots \\ 56899 & 827 \end{array}$$ where each row in the solution is the previous row solution for $a'$ plus 757 and the previous row solution for $b'$ minus 989, stopping when the $b'$ solution is negative.
> 1 votes

---
Tags: algorithms, counting
---


title: Time complexity of a Divide and Conquer

text:
# Question
Title: Time complexity of a Divide and Conquer
I have Master theorem for finding complexities but the problem is Master theorem says

For a recurrence of form $T(n) = aT(n/b) + f(n)$ where $a \geq 1$ and $b \> 1$, there are following three cases:

* if $f(n) = Θ(n^c)$ where $c \< \log\_ba$, then $T(n) = Θ(n\log\_ba)$;
* if $f(n) = Θ(n^c)$ where $c = \log\_ba$, then $T(n) = Θ(nc\log n)$;
* if $f(n) = Θ(n^c)$ where $c \> \log\_ba$, then $T(n) = Θ(f(n))$.

I have$T(n) = T(n/2) + n^2$.

My solution is that $c = 2$ and $\log\_ba = \log\_1 2=\infty$. So in which case does it fall and what is the complexity?

# Answer
> 2 votes
As Rick Decker points out in his comment, your error is that you have $a=1$, $b=2$, so $\log\_ba = \log\_21=0$. (Not, as you say, $\log\_ba=\log\_12$.)

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Sorting array with two elements - in place and minimal number of comparisons, lower bound
Algorithm must be in place.
I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ and $0s$.

Decision tree give us lower bound $\log(n+1)$. It is to weak, because we know lower bound for findiing minimum, hence our algorithm must do at least $n-1$ comparisons. If it is lower bound ? I don't, but I think that it is $n$.

**Why Do I think that lower bound is equal to $n$** ?

Let consider array $|a|=n$ such that $a\[1\]=a\[2\]=...=a\[n-1\]=0$ and $a\[n\]=1$.

It is needed at least $n-2$ comparisons to check that there is $n-1$ equal elements. And additional $2$ comparisons to check that $1$ is greater then rest of elements.

What is it real lower bound? What about my justification ?

**Edit: We assume model computation as comparison $\le$.**

# Answer
> 1 votes
$n-1$ comparisons are necessary and sufficient. To show that $n-1$ comparisons are necessary, we consider an adversary that always answers "EQUAL". Suppose that an algorithm makes at most $n-2$ comparisons. Construct a comparison graph whose vertices are the array elements and whose edges are the comparisons. Since the graph has at most $n-2$ edges, it is not connected. Let $C\_1,C\_2$ be two connected components. It is consistent that the value of all elements in $C\_1$ is $0$ and that the value of all elements in $C\_2$ is $1$. It is also consistent that all elements in $C\_1$ are $1$ whereas all elements in $C\_2$ are $0$. No monotone ordering of the array is consistent with both options, showing that the algorithm is incorrect.

To show that $n-1$ comparisons are sufficient, consider the algorithm that compares the first element to all other elements. There are three cases to consider:

1. The first element is equal to all other elements. In this case the array is already sorted.
2. The first element equals the elements in $S$ and is smaller than the elements in $T$. Thus the first element and the elements in $S$ have the value $0$ and the elements in $T$ have the value $1$, and we can sort the array accordingly.
3. The first element equals the elements in $S$ and is larger than the elements in $T$. This is symmetric to the previous case.

---
Tags: complexity-theory, time-complexity, sorting, arrays, lower-bounds
---


# Question
Title: What do you call a subtree covering a subset of contiguous leaves?
In the data structure field, what is the (best) term used to identify (designate) a subtree covering a subset of contiguous leaves?

# Answer
You seem to mean a subtree obtained by taking a certain node and all its successors.

In data structures, the implicit assumption usually is that we consider *rooted* (and often *ordered*) trees. Therefore, "subtree" is usually taken to mean what you intend; "subtree" as in graph-theoretic "subgraph" is rarely used (in my experience).

If you want to make very clear what you mean, you can write

> The subtree of $T$ which is rooted in $x \in T$.

A common notation for this tree is $T\_x$.
> 2 votes

# Answer
It is the subtree rooted at the *least common ancestor* of the set of leaves (the fact that the leaves are continuous makes no difference). I'm not sure there is any shorter term.
> 0 votes

---
Tags: terminology, data-structures, trees
---


# Question
Title: A model of computation vs an abstract machine
1. Wikipedia says

> **A model of computation** is a formal description of a particular type of computational process. The description often takes the form of an **abstract machine** that is meant to perform the task at hand.

What other forms can a model of computation take than an abstract machine?
2. What are the difference and relation between a model of computation and an abstract machine? I thought that they were the same, until I saw the the quote above.

# Answer
An abstract machine typically defines instructions with opcodes and operands. A Warren abstract machine, a java virtual machine, a Turing machine. A programming model defines operations at a higher level, and could be independently supported by a number of different machines. For example the actor programming model says that an actor can send a message, create a new actor, and define internal state for its next message to be handled. This is said without defining specific opcodes and operands, though one could envision an abstract machine that supported that.
> 2 votes

---
Tags: terminology, computation-models
---


# Question
Title: Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?
I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability.

The algorithm choose a random $r$ n-bit vector and if $$A(Br) = Cr$$ then outputs YES, otherwise outputs no.

I want to show that it has has one-sided success probability 1/2. For that I want to show that when $AB = C$ then the algorithm is correct with probability 1 and when $AB \neq C$ then the probability of it being correct is at least 1/2.

When $AB = C$ its clear that the algorithm is always correct because:

$$ A(Br) = (AB)r = Cr$$

So, if $AB=C$, then $A(Br)$ is always equal to $Cr$.

The case when $AB \neq C$ is a little trickier. Let $D = AB - C$. When the multiplication are not equal then $D \neq 0$. Let a good $r$ be a vector that discovers the incorrect multiplication (i.e. $D \neq 0$ and $Dr \neq 0$, multiplying by $r$ makes it still zero). let a bad $r$ be a vector that makes us mess up, i.e. conclude the multiplication is correct when is not. In other words, when $D \neq 0$ (i.e. multiplication was done correctly $AB = C$) but when we use $r$ to check this we get the wrong conclusion (i.e. $Dr = 0$, when in fact $D \neq 0$).

The high level idea of the proof is, if we can show that for every bad $r$ there is a good $r$, then half the $r$'s are good so our algorithm is about 1/2 percent of the time correct. This high level idea of the proof makes sense to me, however, what is not clear to me is the precise detail of the inequality (whether $Pr\[error\] \geq \frac{1}{2}$ or the other way round).

So consider the case where $D \neq 0 $ i.e. $AB \neq C$. In this case then we have that at least one entry $(i,j)$ in $D$ is not zero (its 1 cuz we are doing mod 2). Let that entry be $d\_{i,j}$. Let $v$ be a vector such that it picks up that entry. i.e. $Dv \neq 0$ such that $(Dv)\_{i} = d\_{i,j}$. In this case, if we have a bad $r$ (i.e. an r such that when $D \neq 0$ yields $Dr = 0$ ) then we could make it into a good vector $r'$ by flipping its $i$ coordinate. i.e.

$$ r' = r +v\_i$$

This mapping from Bad to Good is clearly 1 to one. i.e. it clear that the equation $ r' = r +v\_i$ only maps to one unique $r'$, so it cannot be one to many. Now lets see that its not many to one either. If there was another $\tilde r$ s.t. $\tilde r = r'$ then that would mean

$$r' = r+ v\_i = \tilde r + v\_i \\;\\; (\operatorname{mod} \\; 2) \implies r = \tilde r \\;\\; (\operatorname{mod} \\; 2)$$

So its one to one. Therefore, the for each Bad $r$ there is a good $r'$. However, it is not clear to me why that would imply:

$$ Pr\[A(Br) \neq C\] = Pr\[Dr \neq 0\] \geq \frac{1}{2}$$

I see why it would be exactly equal to 1 but it is not clear to me at all why it implies the above inequality.

# Answer
Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors are equally likely, $$ \Pr\[Dr \neq 0\] = \frac{G}{G+B} \geq \frac{1}{2}. $$ The last inequality is a bit of algebra I leave to you.
> 6 votes

# Answer
Let $D=\[d\_{k,l}\]$. If $d\_{i,j}\not=0$, then $Prob(Dr\not=0)\geq Prob(i^{th}$ line of $Dr$ is $\not=0)=1/2$.
> -1 votes

---
Tags: algorithms, randomized-algorithms, correctness-proof, matrices
---


# Question
Title: Implementing primitive recursive functions in a programming language
I started studying Design Concepts in Programming Languages by Turbak, Gifford and Sheldon. In the first chapter, they define a language called POSTFIX, similar to a postfix calculator's input language. This one also has a conditional command and a subroutine-like struct. So, it seemed like it could implement a looping construct like while. But later, the book gives proof that POSTFIX is not able to encode infinite loops, programs always terminate.

In an exercise, the book wants me to implement a factorial program in POSTFIX, if possible. I tried and failed miserably for hours. I looked up on primitive recursive functions, which factorial is one. Found a language called LOOP, designed by Uwe Schöning that can compute only the primitive recursive functions. I tried implementing in POSTFIX a looping construct that always terminates but could not do it. Because the language does not have any naming or abstraction facilities, I could not see how I can do it.

What I ask is this:

Using the POSTFIX definition given on the below link, can someone implement a language construct that can be used to implement primitive recursive functions, like implementing a looping construct that always terminates? Or give a proof that it is not possible maybe.

*Note:* There is a draft of the book (thanks @YuvalFilmus) where you can find the description of POSTFIX language (section 1.4, pp5).

# Answer
You can prove by induction that the number of instructions executed by any given program is bounded (essentially since no command can create instructions). In particular, the number of arithmetic instructions executed by a program is bounded. This means that the output of a univariate function is polynomially bounded. Since the factorial function is not polynomially bounded, you cannot compute factorial.

If, however, we add a `pget` instruction which is similar to `nget` but gets a subroutine rather than a number then we can compute factorial, for example with the following program:

`(postfix 1 1 (3 nget 3 nget mul 4 nget 1 sub swap 2 nget (3 pget 1 pget exec) () sel exec) 1 pget exec)`
> 5 votes

---
Tags: programming-languages, primitive-recursion
---


# Question
Title: Optimal prefix code: full binary tree existence
I'm ok following the passages generally used to prove this theorem, like in this question concerning the same subject. Anyway i've the unpleasant feeling that the proof lacks something to be completely understood, perhaps because considered obvious by many people.

We know that a binary tree corresponding to the optimal prefix code is full. To produce a proof you start considering a binary tree $T$ corresponding to optimal prefix code, and suppose it's not full. If it's not full, then it must contains at least a node $u$ with just one child $v$. If you replace $u$ with $v$ you end up with a new tree $T'$ whose leafs in the subtree rooted in $u$ require less bits to be encoded: so the average bits per letter of the prefix code corresponding to $T'$ is smaller and this contradicts the optimality of $T$.

As far i can see, with this proof, we know that if we had the possibility to erase useless nodes we would obtain trees with best encoding, and therefore they must be full. But how do we prove that these trees actually exist?

I think that you can always replace nodes that aren't leafs, as stated by the proof, because they are just "auxiliary": you don't loose any information replacing them as long as the structure of the new tree you obtain is still valid to produce a prefix code. So, starting from a tree $T$ that is not full, $T'$ always exists.

Is this interpretation correct?

# Answer
You can formulate this proof in completely constructive terms. Starting with any prefix code, consider any node $v$ which has exactly one child $w$, and contract the edge $(v,w)$. Repeat this as long as no node has exactly one child. Since each operation decreases the number of nodes, we know that after finitely many iterations we reach a full binary tree.
> 1 votes

---
Tags: proof-techniques, check-my-answer
---


# Question
Title: Term for an approximation that becomes better as the problem grows
For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F\<1$ is some constant and $\textrm{Max}$ is the exact maximal value.

What term describes an algorithm in which the approximation factor is a function $F(n)$ of the problem size, and $F(n)\to 1$ as $n\to \infty$?

# Answer
> 3 votes
You can say your algorithm is *asymptotically optimal*. One example is universal codes, which are a certain type of codes for the natural numbers. They satisfy the following property. Let $D$ be a monotone probability distribution over the natural numbers, that is $\Pr\[D=n\] \> \Pr\[D=n+1\]$. The average codeword length under a universal code is $H(D)(1 + o(1))$. Since $H(D)$ is the optimal length, universal codes are *asymptotically optimal*, in exactly the same sense as the one you're after.

---
Tags: terminology, time-complexity, approximation
---


# Question
Title: Restricted Boltzmann machine confusing details
Hi I'm new to RBM and machine learning/computer vision in general, and I'm using the code from: http://blog.echen.me/2011/07/18/introduction-to-restricted-boltzmann-machines/ while reading on https://en.wikipedia.org/wiki/Restricted\_Boltzmann\_machine for some theories. But right now i'm totally confused. In the code there is a part:

```
# Calculate the activations of the hidden units.
      hidden_activations = np.dot(visible, self.weights)
      # Calculate the probabilities of turning the hidden units on.
      hidden_probs = self._logistic(hidden_activations)

```

I assume the equivalence in wikipedia would be the conditional probability, but when I look that up, nothing makes sense! I mean, what are v and h, are they supposed to be vectors or values? (I assume they are in fact just values, as wikipedia only talks about each seperate samples while the code groups all of them into a matrix, but even them it's still hazy :( ). I'm new to this so my question may be a little dumb but please help me. Thank you very much! P/s: Sorry I am unable to post the equations :(

# Answer
The equation from the wikipedia implemented with this code is the one in picture bellow. Sigma function is logistic sigmoid (self.\_logistic()). The dot product is the sum of products bellow. bj is offset and might be included in the sum (some visible neuron is always 1) or it might be omitted completely for simplicity or something else.
> 1 votes

---
Tags: machine-learning, boltzmann-machine
---


title: Why is this an infinite loop?

text:
# Question
Title: Why is this an infinite loop?
```
while userinput != "yard" or userinput != "gym" or userinput != "basement" or userinput != "cell" or userinput != "showers" or userinput != "outside":
            print "Enter 'yard' or 'gym' or 'basement' or 'cell' or 'showers' or 'outside' to search them."
            if userinput == "yard":
                Rooms.yard()
            elif userinput == "gym":
                Rooms.gym()
            elif userinput == "basement":
                Rooms.basement()
            elif userinput == "cell":
                Rooms.cell()
            elif userinput == "showers":
                Rooms.showers()
            elif userinput == "outside":
                Rooms.outside()
            else:
                end_game()

```

It doesn't go into an infinite loop when I enter the prompts listed but once I hit enter it goes into an infinite loop. Why is that? I tried to figure out why but I'm having a hard time. Thanks

# Answer
> 1 votes
Your condition is:

```
while userinput != "yard" or userinput != "gym" or ...

```

By using De Morgan's law it is equivalent to:

```
while !(userinput == "yard" and userinput == "gym" and ...)

```

As `userinput` can only have a single value it cannot be equal to both "yard" and "gym" meaning that the expression in the brackets is always False making the whole condition !False = True no matter the value of the userinput.

I am unsure of what `end_game()` does so I cannot comment if it can break out of the loop or not.

---
Tags: loops
---


# Question
Title: space complexity of DFA intersection problem
the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper significance in computational complexity theory.\[1\]\[2\] it is O(n2) time with no better lower bounds known, and tight bounds possibly having major implications on multiple complexity class separations. looking for insight/ refs.

> what is the best known *space* complexity of determining DFA intersection (emptiness)? how does the best known algorithm work?

\[1\] Deciding emptiness of intersection of regular languages in subquadratic time / cstheory SE
\[2\] Two DFA intersection emptiness connections to SETH & L vs P / cstheory SE

# Answer
> 9 votes
**Solving intersection Non-Emptiness for 2 DFA's:**

It essentially just becomes a reachability problem for the product DFA.

* Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space.
* Or, we can solve it non-deterministically with $O(\log(n))$ space.
* By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time using $O(\log^2(n))$ space.

To the best of my knowledge, it is not known if we can solve it deterministically in polynomial time using $O(n^{2-\epsilon})$ space.

Feel free to share any thoughts or ideas in the comments. :)

---
Tags: reference-request, complexity-classes, space-complexity, lower-bounds, dfa
---


# Question
Title: What language should this NFA recognise?
I am trying to figure out which language does the following NFA (taken from a Sipser's book "Introduction to theory of computation") recognise

From my understanding, this NFA accepts strings that contain at least two $1$s, but this is not precise, because, e.g., between the two ones we could have a $0$ or nothing ($\epsilon$). We can also have any number of $0$s or $1$s after these two $1$s.

My guess is that this NFA recognises a language whose strings contain the substrings $11$ or $101$, but I am not sure.

Can you help me defining the language that this NFA recognises?

In general, what is the best way to see what language is recognised by a NFA?

# Answer
> 3 votes
Don't overthink it; your intuition is correct. The only strings that get you from the start state to the final state are $\<anything\>11$ or $\<anything\>101$. Once you're in the final state, any subsequent inputs are also accepted, so the language accepted by this FA is, as a regular expression, $(0+1)^\*(11+101)(0+1)^\*$, which is obviously all strings containing 11 or 101.

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


# Question
Title: Determining whether a digital circuit is optimal
Are there any techniques that can be used to determine whether a digital logic circuit is optimal, or if it has extraneous operations that don't contribute to the output?

I'm especially curious in the case where the circuit is defined in terms of XOR and AND gates.

I know I could make a karnaugh map and create a circuit from that, but that doesn't really tell me about the circuit I had, it just gives me another circuit.

Thanks for any info!

# Answer
> 3 votes
Use one of the standard techniques for circuit minimization. As far as I know, verifying that a candidate circuit is minimal is as hard as finding the minimal circuit in the first place (I know of no faster algorithm for verifying minimality than finding a minimal circuit in the first place).

Circuit minimzation is NP-hard (in fact it's even harder than that, in some sense), so you shouldn't expect an efficient algorithm for it that handles all functions efficiently.

---
Tags: optimization, digital-circuits
---


# Question
Title: Optimal data structure for a time-windowed streaming graph in order to compute fast statistics
I apologize if this is the wrong place or too trivial a question for this community. What is the best data structure to store a time-windowed streaming graph in order to compute fast statistics over all nodes in the graph, for e.g., running computation of average degree?

I believe the best way to describe this is as follows: Let $G=(V,E)$ be a sparse time-evolving network modeled as an undirected graph with $n$ nodes and $m \geq n$ edges over time (in hours) $t = t\_0, t\_1, \dots $. Suppose further, that at any time point $t\_i$, any edges that are more than $k$ hours are removed. In addition, nodes that have no edges connecting to it are removed.

My idea (for e.g. the average degree) is as follows: keep track of an array of edge arrival times as well as a degree array of size $n$ where each element represents the total degree. At any new time point $t\_i$, we would add 1 to the degree array corresponding to the two nodes with the new edge. We would then remove all edges that are older than $k$ hours (i.e. added before $t\_i-k$). Any nodes that are edge-less are removed. At all time points, a running average of the degree is computed by taking the average of the degree array.

If I'm not mistaken, this algorithm would be $O(n)$ in run-time and $O(n)$ in space. Is there any better way of doing this?

The best data structure I could find from previous posts such as this one, recommend adjancency lists. Additionally, is there any advantage in using disjoint set data structures such as in the post here?

# Answer
> 2 votes
There's an efficient streaming algorithm for computing the average degree. Note that if you have the sum of the degrees and the number of vertices, you can compute the average -- so we'll try to keep track of those two values.

Also note that if you delete or insert an edge, it is easy to update the sum of the degrees. If you delete or insert a vertex, it is easy to update the number of vertices.

Taking all of this into account, we do $O(1)$ work (amortized) per time step, and at every time step we can infer the average degree. This is as efficient as one could possibly hope for.

---
Tags: graphs, data-structures, streaming-algorithm, network-analysis
---


# Question
Title: Data structures as algorithms themselves
Can data structures be thought of as algorithms themselves?

For example, I could implement a stack data structure that has certain non-functional characteristics.

Is the separation between data structures and algorithms formally defined?

# Answer
Yes, a data structure can be thought of as an algorithm. A data structure is a collection of state together with one or more algorithms that operate on that state.

A data structure can be thought of as a tuple $(s,f\_1,f\_2,\dots,f\_k)$ where $s$ is its state, and each $f\_i$ is an operation that can be performed on the data structure; the operation $f\_i$ can read the state $s$ and its input parameters, and possibly modifies $s$ and possibly returns a new value. Alternatively, from an object-oriented viewpoint, you can think of a data structure as an object; $s$ is the state of the object, and $f\_1,\dots,f\_k$ are the methods that can be invoked on the object. Normally, $f\_1,\dots,f\_k$ are described as algorithms that operate on $s$ and their inputs. This lets you use the language and concepts of algorithms to analyze various data structures.

I'm not sure there is a formal specification of what counts as a data structure, but this seems to get about close as I've seen.

You might be interested in the notion of abstract data type (ADT) from programming languages. You can think of a data structure as an ADT, or more carefully, you can think of an ADT as the specification and the data structure code as a particular implementation of that ADT. When people talk about data structures informally, they don't always distinguish between specification vs implementation; the term ADT helps make that distinction more precise.

I don't know if people normally try to formally define what we mean by "data structure"; it's a loose term that is more useful to illustrate a particular type of concept in computer science. If I wanted to make it as precise as possible, the notion of an ADT would probably be the first formalization I'd consider. An ADT is like an interface specification, and a specific data structure is like a particular way of implementing that specification.
> 7 votes

# Answer
A data structure is an implementation of the ADT. An ADT can be assumed to be a contract which guarantees certain operations in a promised amount of time. It doesn't state how it will layout the underlying data in memory.

Now, it's up to the programmer to implement the ADT which is known as Data Structure. For example, Stack is an ADT and it can be implemented over a linear data structure like Array or over a linked data structure like Linked List.

Regarding your question I am not sure because it's said that:

$Programs = Data Structures + Algorithms $ Reference

So, Stack in itself is not an algorithm, but evaluating a postfix expression using a Stack is an algorithm.

It seems a subjective matter though.
> 7 votes

# Answer
Many divide-and-conquer algorithms map directly to tree structures which match their call graphs. For instance Bentley and Sedgewick's *Fast Algorithms for Sorting and Searching Strings* introduces both a recursive algorithm and a search tree with the same structure; the sorting process amounts to traversing the tree without physically instantiating it (beyond the nodes saved in the stack). There's also a table in there of other algorithm-tree examples.

These tree structures are often necessary to do proper algorithm analysis, because information-theoretic results about the average number of nodes in a trie or Patricia tree can be mapped to the number of recursive calls and character comparisons in a string sorting algorithm, for instance.

It's also a fairly common pattern to instantiate only part of this mapped data structure as an intermediate step in, eg, a sorting process, where a search tree is used to divide the input into bins which are then procedurally sorted. For instance parallel sorting may instantiate only the first few levels of a search tree to distribute data among nodes, which then procedurally sort each bin.
> 1 votes

# Answer
Both concepts are about mapping some input to some output. Algorithms does this mapping by following a sequence of instructions whereas data structures does the mapping (Array map index to value, dictionary map key to value etc) by memory lookup(s). From this point of view both are same but the way they does the mapping is different.

NOTE: Mutating a data structure can be thought of mapping where the output also contains new update data structure.
> 0 votes

# Answer
“Can data structures be thought of as algorithms themselves?” (Aston, 2015) It is possible to map the information about a process kept in record-based structures into a computer program (Chionglo, 2104). Thus data kept in records can be thought of as algorithms.

If you consider records as data structures and if you consider the following (a repeating countdown timer/counter) an algorithm:

1. Initialize a variable to 9.
2. Subtract 1 from the variable.
3. If the value of the variable is 0, go to step 1 else go to step 2.

Then a process description of the algorithm can be “stored” in several record structures. The entities in the records are (Petri) net elements and their properties/annotations. The annotations include logic computations and interfaces (such as graphics, user events, and system events) for visualization and interaction purposes. These properties give the user or reader the ability to see and to step through the algorithm. The information kept in the record structures may be mapped to a JavaScript program that controls Figure 1 in the PDF version of this reply, an interactive process description (based on Petri Nets) of the algorithm.

## References

Aston, B. (2015). Data structures as algorithms themselves. Computer Science Stack Exchange.

Chionglo, J. F. (2014). Net elements and annotations for computer programming: computations and interactions in PDF.
> 0 votes

---
Tags: algorithms, terminology, data-structures
---


title: Optimized resource allocation problem

text:
# Question
Title: Optimized resource allocation problem
I am from ECE background and trying to solve channel allocation problem. Let's assume I have three users and three available channels. I would like to allocate channel among them in such a way that average BER would be minimum.
For example, consider BER matrix for each user for each frequency allocation \begin{bmatrix} User/frequency & User1 & User2 & User3 \\ f1 &0.01 & 0.05 & 0.3\\f2 & 0.12 & 0.045 & 0.02 \\ f3 &0.02 & 0.01 & 0.01 \end{bmatrix}

Now, I would like to allocate channels f1--\> User1, f2--\> User3 and f3--\>User2, which gives least average BER (Sum of each users BER/no of users). (Note: Same frequency can't allocated to different users.)

Brute force is obliviously one solution, but I am trying to find optimized solution.

# Answer
This is just the assignment problem: you need to find a maximum-weight matching between the users and frequencies. The Hungarian algorithm solves this in time $O(n^3)$.
> 3 votes

---
Tags: optimization, dynamic-programming
---


# Question
Title: Is the program in secondary memory can be a process?
Let us consider the following scenario,

The cpu started executing a program, which is in secondary memory with n lines of code, so, it brings m ( \< n ) lines of code in to main memory and started executing.

We can call the m lines of code, which are in main memory as process.

But my doubt is that, what about the remaining n-m lines of code that are in secondary memory, which are not yet reached main memory, can we call them process? or just program? The remaining n-m lines may execute by the CPU in future. But what now the n-m lines of code are?

# Answer
A process is a technical term that has a well-defined meaning. You can't just re-define standard terms that have an accepted meaning... or if you do, you should expect it to cause confusion. My advice is to stick with the standard meaning of this term, and read an operating system textbook to learn what is the accepted notion of a "process".

Wikipedia defines a process as "an instance of a computer program that is being executed". A process is not some set of lines of code. A program contains a bunch of machine-level instructions. (Those machine-level instructions are typically obtained by compiling some source code.) A process is then a running instance of a program. The process typically is comprised of multiple resources: some memory (in particular, a region of virtual memory), one or more threads of execution, and some operating system state that is specific to the particular process.

So, no, you can't call "the set of lines of code in secondary memory" a process -- that's not what a process is. Similarly, when you write "We can call the m lines of code, which are in main memory as process.", my reaction is: no, you can't -- that's not what a process is.
> 2 votes

# Answer
A process is a set of instructions that will eventually be executed by the CPU , it doesn't matter if it's on main or secondary memory, the CPU will see it as Virtual Memory (https://en.wikipedia.org/wiki/Virtual\_memory).

A process can be seen as an entity that has his own memory and tables on the CPU (see GDT: https://en.wikipedia.org/wiki/Global\_Descriptor\_Table) so it will still be a process even if it's on main or secondary memory.
> 1 votes

---
Tags: terminology, process-scheduling
---


# Question
Title: Error in solution in Types and Programming Languages?
I'm reading Types and Programming Languages and trying to understand the solution to exercise 5.2.4 on untyped lambda calculus / Church numerals:

> Define a term for raising one number to the power of another.

The proposed solution says:

> $\textrm{power2} = \lambda m. \lambda n. m~n$

In an attempt to understand how this solution works, I tried it on 01 as follows:

$$ \begin{array}{ll} & \textrm{power2}~c\_0~c\_1 \\ \rightarrow & c\_0~c\_1 \\ = & (\lambda s.\lambda z.z)~c\_1 \\ \rightarrow & \lambda z.z \end{array}$$

The result doesn't look like a Church numeral to me. Is it an error in the solution, or have I misunderstood something?

# Answer
If $power2~m~n$ stands for $m^n$, then it should be

$$power2=λm.λn.n~m$$

Let's try it on $0^1$: $$ \begin{array}{ll} & power2~c\_0~c\_1 \\ = & (λm.λn.n~m)~c\_0~c\_1 \\ \rightarrow & c\_1~c\_0 \\ = & (λs.λz.s~z)~c\_0 \\ \rightarrow & λz.c\_0~z \\ = & λz.(λs.λz.z)~z \\ \rightarrow & λs.λz.z \\ = & c\_0 \end{array} $$ Works fine.

Let's try it on $1^0$: $$ \begin{array}{ll} & power2~c\_1~c\_0 \\ = & (λm.λn.n~m)~c\_1~c\_0 \\ \rightarrow & c\_0~c\_1 \\ = & (λs.λz.z)~c\_1 \\ \rightarrow & λz.z \end{array} $$

Wait, we should have got $c\_1$.

Although syntactically $λz. z$ is different from it, but it has the same behavior as $c\_1$. In fact, you can use the function $equal$ (ex. 5.2.7) to prove it: $$ equal = λm. λn.~and~(iszro~(m~prd~n))~~~(iszro~(n~prd~m)) $$

By the way, another form of the power function, given in the solution to this exercise have the arguments swapped:

$$power1 = λm. λn. m~(times~n)~c\_1$$.
> 1 votes

---
Tags: programming-languages, lambda-calculus, types-and-programming-languages
---


# Question
Title: Consequence of NP=coNP to some hierarchy problems
If $NP=coNP$ does it hold that $P/Poly=PH/Poly$ and/or $NP\subseteq P/Poly$ and/or $VNP=VP$?

What can we legitimately say if $NP=coNP$?

# Answer
To the best of my knowledge, no such implications are known.
> 1 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Finding a minimal cover of a subset of a finite cartesian product by cartesian products
Given a subset of a cartesian product $I \times J$ of two finite sets, I wish to find a minimal cover of it by sets which are cartesian products themselves.

For example, given a product between $I=\\{A,B,C\\}$ and $J=\\{1,2,3\\}$, I may observe the subset $\\{(A,2), (B,3), (B,2)\\}$ and try to cover it with a minimal number of cartesian products.

Two ways to do so are $\\{A\\} \times \\{2\\} + B \times \\{2,3\\}$ and $\\{A,B\\}\times \\{2\\} + \\{B\\}\times \\{3\\}$, both requiring 2 products. A sub-optimal solution may be breaking it into 3 trivial products.

Can such an optimal cover be found efficiently (e.g., in polynomial time)?

# Answer
> 2 votes
NM reformulates this problem in comments as finding minimum number of bipartite cliques (bi-cliques) that cover a bipartite graph. the two sets you mention are the 2 vertex sets of the bipartite graph. the cartesian products of subsets of the two vertex sets are bicliques. wikipedia states this is the bipartite dimension problem and is problem GT18 in Garey and Johnson, proved NP complete based on straightforward reformulation of set basis problem SP7.

---
Tags: algorithms, set-cover
---


title: Petri nets boundedness

text:
# Question
Title: Petri nets boundedness
I want to ask about Petri net (PN) boundedness. When I have a state `s1 = (2 0 0)`, then I find state `s2 = (2 0 1)`, so since `s1 < s2` can I declare the net as *not* bounded ? Because when I have this PN:

the PN is bounded but you can find there (2 0 0) \< (2 0 1). Am I wrong about boundedness of Petri nets or is something wrong with the PT on the picture ?

# Answer
> 2 votes
Unboundedness can be studied from a fixed initial marking (=state). Then you want to find a state that is reachable, by firing transitions, but larger than the initial one.

You mention both states s1=(2,0,0) and s2=(2,0,1), which is in the picture. The problem is that I do not see how either one can be reached from the other.

So, start in the initial state, and analyse which transitions can be fired.

# Answer
> 2 votes
For the given Petri Net, the number of tokens for P\_1,P\_2 and P\_3 is represented by m\_1,m\_2 and m\_3 respectively. Based on the definition of boundedness of a Petri Net by Popova-Zeugmann (2013), the given Petri Net is bounded because m\_1 ≤ 2,m\_2 ≤ 2 and m\_3 ≤ 2. In other words, there is a natural number (2 in this case) such that the number of tokens in P\_1,P\_2 and P\_3 never exceeds the number.

I am also providing an example of an unbounded Petri Net and an example of a bounded Petri Net. Regardless of the initial marking, the Petri Net in Figure 1 is not bounded (or it is unbounded) because m\_0 → ∞ when T\_0 keeps firing.

For the given initial marking, the Petri Net in Figure 2 is bounded because m\_0 ≤ 1 and m\_1 ≤ 2. In general, the Petri Net in Figure 2 is bounded: let the initial value of m\_0 = q\_0 and the initial value of m\_1 = q\_1; m\_0 ≤ q\_0 and m\_1 ≤ 2q\_0+q\_1

## References

Popova-Zeugmann, L. (2013). Chapter 2 The Classic Petri Net \[Electronic version\]. Time and Petri Nets. Berlin; Heidelerg: Springer-Verlag.

---
Tags: petri-nets
---


# Question
Title: Finding Minimum Weight Subgraph Spanning Tree
Suppose we have a graph $G = (V, E, w:e\in E \to x \in \\{0,1\\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1.

Suppose we also have a subset of vertices $S \subset V$ and that we want to find a minimum-weight tree that spans the vertices in $S$. Since the vertices in $S$ might not be directly connected, we are allowed to use vertices in $V$ that may not be in $S$ to build our minimum-weight tree.

Is there an algorithm similar to Prim's or Kruskal's that we can use to solve this?

# Answer
> 3 votes
No, it's highly unlikely there is a polynomial time algorithm for this problem. The problem you describe is known as Steiner tree, and it is NP-hard. Moreover, it is computationally quite difficult from many other viewpoints as well.

A classical dynamic programming approach is the Dreyfus-Wagner algorithm running in $O^\*(3^k)$ time, where $k$ is the number of terminals (i.e., the size of the set of pairs $S$ in your terminology). There is *a lot* of literature on the problem, so you might want to look at it from a particular viewpoint.

---
Tags: algorithms, graphs, optimization, trees
---