title: DAG with modulo 3 restrictions

text:
# Question
Title: DAG with modulo 3 restrictions
Consider the following problem.

The input is a Directed Acyclic Graph. Each vertex $v\_i$ may have exactly 0 or 2 incoming edges with associated vertices $v\_{i1}$ and $v\_{i2}$. If it has 0 incoming edges, it is considered an *input vertex*. The input of the problem specifies with each input vertex exactly two numbers out of {0,1,2} that may be associated with that input vertex.

Each vertex may have any number of outgoing edges. All vertices that don't have any outgoing edge, are considered *output vertices*.

The goal of our algorithm is to associate with each vertex a number 0, 1 or 2 that respects the constraints:

* each input vertex must be associated with one of its two numbers in the input.
* each output vertex must be associated with 0 or 1.
* each non-input vertex $v\_i$ must be associated with $(v\_{i1} + v\_{i2}) \bmod 3$.

Example problem and solution:

The general case for this problem should be NP-complete. But in my case, all paths from any input vertex to any output vertex have length at most $c$, where $c=27$. Does this make the problem feasible?

# Answer
I don't know whether your problem is feasible, but here is another way to express it, in the language of linear algebra instead of the language of DAGs.

The upper bound on the path length means that each output vertex depends on at most $2^{27}$ input vertices... which is technically a constant.

Your problem is equivalent to the following:

Input: a matrix $M$, a vector $c$
Question: do there exist vectors $x,y$ all of whose entries are 0 or 1, such that $y=Mx+c \pmod 3$?

In your particular case, we are guaranteed that each row of $M$ has at most $2^{27}$ non-zero entries, and you're asking whether this is sufficient to make the problem feasible. I don't know the answer to that.

---

Here is the equivalence between your formulation based on DAGs, and the linear algebra formulation above: we think of each non-input vertex as summing (modulo 3) the two inputs entering it, so it represents an addition (modulo 3) gate. Suppose the two numbers on an input gate are $a,b$. Then we can equivalently think of the input vertex as accepting a zero-or-one input variable $x$, and outputting $(b-a)x + a$ (modulo 3). Note that $b-a$ and $a$ are known constants, so an input vertex computes an affine function of the corresponding zero-or-one input variables. As a result, we have one zero-or-one input value per input vertex, and one output value per output vertex, and we are hoping that all the output values will be zero or one. By unfolding the summations, we see that each output value is the sum (modulo 3) of at most $2^{27}$ expressions of the form $\alpha\_i x\_i + \beta\_i$ where the $\alpha\_i,\beta\_i$ are known constants and the $x\_i$ are the zero-or-one inputs. That then leads to the reformulation I listed above.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: LL(1) CFG for triple amount of b's compared to a's?
I would like to construct a LL(1) context-free grammar for a formal language $A$ = "strings where the amount of character `b` is exactly triple compared to the amount of character `a`" for $\Sigma = \\{a,b\\}$.

I've tried to figure it out so that if we consider a string $w$ to have one `a`, then the acceptable presentations for $w$ considering language $A$ would be `abbb`, `babb`, `bbab` and `bbba`.

But how do I build the CFG rules for that? I have tried something like $$S \rightarrow A$$ $$A \rightarrow \epsilon | aAbbb |baAbb | bbaAb | bbbaA$$ but I think it's not very good because at least I cannot build an LL(1)-parser out of it (which would be good) because of ambiguity. And it doesn't quite work out for a string like bbbbbbaa $\in A$.

Is it possible to build a CFG for this language that can be parsed using a LL(1) parser? If not, why not?

# Answer
I believe that any string able to be represented by a CFG can also be parsed in LL or LR. That is just one of the features of CFG's. The grammar you have originally written can be parsed using LL as the upper-case $A$ will act always as your left-most variable to be expanded and simplified.

I think your problem with constructing the grammar can be solved by also including rules in which the lower-case and upper-case $a$'s are switched, though, that is a rather clunky solution.

$S \rightarrow A$

$A \rightarrow \epsilon | baAbb | bAabb | bbbaA | bbbAa | bbaAb | bbAab | aAbbb| Aabbb$
> -2 votes

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


title: Understanding a formula on article

text:
# Question
Title: Understanding a formula on article
I just read an article "Statistical approach for figurative sentiment analysis on Social Networking Services: a case study on Twitter", which provide an algorithm to analyze tweets, and this article includes 2 formulas which I don't really understand.

Link to the article

I hope maybe someone here can help me.

* The first formula is the (4) formula (Page 5)
* The second formula is the (6) formula (Page 8)

I will be very thankful if someone will help me with this.

Examples will be most welcome! :)

# Answer
> 0 votes
Each tweet and each cluster is represented as an $m\_k$-dimensional vector. The distance between a tweet $t\_k$ and a cluster $\delta$ is then $$ dis(t\_k,\delta) = 1 - \frac{\langle t\_k, \delta \rangle}{\\|t\_k\\| \\|\delta\\|}, $$ where $\langle a,b \rangle = \sum\_{i=1}^{m\_k} a\_i b\_i$ is the inner product and $\\|a\\| = \sqrt{\langle a,a \rangle}$ is the norm. This explains equation (4).

The definition of $P(S\_t|w)$ is given below (6):

> $P(S\_t|w)$ is the probability that a term has a score with the given tweet score.

This is the number of tweets containing $w$ which have score $S\_t$ divided by the total number of tweets containing $w$.

The rest of the formula is hopefully self-explanatory ($\times$ is just ordinary multiplication).

If you have any more questions, I suggest contacting the authors.

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


# Question
Title: Of monotone formulas and same ones satisfying certain properties
There is the following theoretical computer science, namely:

> For a particular monotone formula $M$ of size $n$, there's an equivalent formula of depth $\text{O}(\text{ln}\\,n)$.

(I am reading the original paper in my library, if I have time later I will scan it and add scans of it to this post. My apologies for being unable to find a copy online.)

However, I'm finding myself going from step to step in the proof without really understanding what's going on, lacking intuition, as the paper is quite short and condensing quite a bit of reasoning and motivation, at least I feel. I was wondering if somebody could offer me their explanation of the proof of this result, hopefully with lots of their intuition thrown in so I and others reading can have a greater understanding of a proof?

# Answer
Spira's result uses the technique of *formula balancing*. For simplicity, I describe the non-monotone case, the monotone case being similar.

Let $\phi$ be a formula of size $n$. We can think of $\phi$ as a binary tree. In general, $\phi$ need not be balanced. It is not hard to show that $\phi$ always has a vertex $\psi$ corresponding to a subformula of size between $n/3$ and $2n/3$ (proof: descend from the root until you reach a subformula of size smaller than $2n/3$). Replace $\psi$ with a new formal variable $x$. The original formula is equivalent to the formula $$ (\psi \land \phi|\_{x=1}) \lor (\lnot \psi \land \phi|\_{x=0}). $$ (If $\phi$ is monotone, we don't need $\lnot \psi$.) What have we accomplished? At the cost of slightly increasing the size of the formula, we managed to get the two top levels of the formula balanced: the subformulas at depth 2 all have size between $n/3$ and $2n/3$.

We continue this process recursively with all the subformulas at depth 2. The process stops after $O(\log n)$ steps, since the subformulas at depth 2 decrease at a constant rate. Hence the final formula has depth $O(\log n)$, and so size $n^{O(1)}$. At the cost of polynomially increasing the size, we have ensured that it is balanced.
> 3 votes

---
Tags: complexity-theory, intuition
---


# Question
Title: Must a min weight subset of edges connecting all vertices form a tree?
Got this question in an exam.

In a graph where all edge weights are positive, if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree?

True or false?

This seems to be the definition of a MST, but since it doesn't state anything about cycles I'm not 100% sure.

# Answer
> **Claim :** if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree

True. It is the definition of MST on weighted (positive) graphs. Subset $S$ can't form a cycle due to minimum total weight condition.

You can prove this by contradiction, assume $S$ is a MST and forms a cycle, as all weights are positive, you can still remove a one edge $e$ from a cycle. $S -e $ is still going to be connect all the vertices of graph, but subset $S - e$ has total weight strictly less than the total weight of $S$, this is a contradiction to our assumption.
> 3 votes

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


# Question
Title: Calculate the average Big O from a function?
I was given this function: $T(N) = 3N\log^2 N + 5N^2\log N + \log N + 17N + 2$ and was asked to find the average Big O complexity.

If the Big(O) deals with an upper bound, would this algorithm be $O(N^2\log N)$ on average? But, because Big O is an upper bound, couldn't this also be $O(N^3)$, $O(N^4)$, etc.? Basically, is there a difference between Big O complexity and *average* Big O complexity of an algorithm?

# Answer
> 2 votes
Strictly speaking, there are no such things as "Big O complexity" or "average Big O complexity". Look at the definition of Big Oh and you can stop guessing.

The right mindset is that you can analyze whatever aspect (say, the number of steps taken by an algorithm) in some case you care about (say, in the worst case, however you define it). You write a function $f$ of the input size $n$ that captures this. You do not need to know anything at all about asymptotic analysis up to this point. Now you can look at the definition of Big Oh again, and express $f(n)$ as the Big Oh of something.

With that being said, I think the questioner should clarify the meaning of "average Big O complexity". Concepts should not be intuitive and come out of thin air, but have precise definitions.

# Answer
> 0 votes
I agree with @Juho in that there is no average Big $O$ concept. Big $O$ is purely an upper bound for the time needed by the algorithm to process the whole input.

What you might have is an amortized cost, which tells you the average performance of each operation in the worst case.

Furthermore, of course you can say that $n = O(2^n)$ but this is a very weak upper bound.

---
Tags: asymptotics
---


# Question
Title: Rounding logarithm to next integer — Potential function
The problem is IV-3 of this pdf: potential function.

Defining a potential function as $\Phi(i) = 2i - 2^{\lfloor{\log\_2i}\rfloor+1} + 1$

The solution states that if $i$ is *not* an exact power of $2$, we have:

$$\Phi(i) = 2i - i + 1 .$$

This means that $2^{\lfloor{\log\_2i}\rfloor+1} = i$. I'm having some trouble understanding this equality.

Can somebody shed some light?

# Answer
> 4 votes
The analysis there is slightly wrong, though the conclusions are correct. Here is the correct calculation:

1. $i$ is not a power of 2. In that case $\lfloor \log\_2 i \rfloor = \lfloor \log\_2 (i-1) \rfloor$ and so $\Phi(i) - \Phi(i-1) = (2i+1) - (2(i-1)+1) = 2$.
2. $i$ is a power of 2. In that case $2^{\lfloor \log\_2 i \rfloor} = i$ and $2^{\lfloor \log\_2 (i-1) \rfloor} = i/2$, and so $\Phi(i) - \Phi(i-1) = (2i - 2i + 1) - (2(i-1) - i + 1) = 2-i$.

---
Tags: algorithm-analysis, rounding
---


# Question
Title: Changing Rabin-Karp without modulo to Rabin-Karp with modulo
I am trying to solve a string matching problem using Rabin-karp algorithm.

I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now.

(this is for starting pattern length of the big string)

```
  1     for(i=0;i<l1;i++)
  2     {
  3         unsigned long long int k2 = *(s1+i);
  4         p1 += k2 * k1;
  5         k1 = (k1 * 31);
  6     }

```

where s1 is a string containing characters,and its like

> `s1[0]*(k1^0) + s1[1]*(k1^1)` and so on.

and I did the same for the pattern we need to find:

```
  0     unsigned long long int j;
  1     for(j=0;j<l1;j++)
  2     {
  3         unsigned long long int k3 = *(str+j);
  4         p2 += k3 * k4;
  5         k4 = (k4 *31);
  6     }

```

Now I am going through strings of length = pattern length in the big string. Code for that is:

```
  0  long long int ll1 = strlen(s1),ll2=strlen(str);
  1     for(j=1;j<=ll2;j++)
  2     {
  3         printf("p1 and p2 are %d nd %d\n",p1,p2);
  4         if ( p2 == p1)
  5         {
  6             r1 = 1;
  7             break;
  8         }
  9         long int w1 = *(str+j-1);
 10         p2 -= w1;
 11         p2 = p2/31;
 12         long int lp = *(str+j+l1-1);
 13         p2 += ((lp *vp));
 14  }
 15     if ( r1 == 0)
 16     {
 17         printf("n\n");
 18     }
 19     else
 20      {
 21           printf("y\n");
 22      }
 23    }

```

where str is the big string, s1 is pattern string.

I tested for multiple inputs and I am getting correct answers for all of them but its taking a lot of time. I then realized it's because of high calculations needed when the pattern string is too long and if we use a modulo operator we can minimize those calculations.

> My question is how to incorporate modulo operator in this code while searching for patterns?

My entire code: http://ideone.com/81hOiU

# Answer
> 1 votes
Don't wait to do the modular reduction at the end. Every time you do an addition or multiplication, immediately reduce modulo the modulus. This keeps all intermediate results small.

---
Tags: strings, pattern-recognition, performance
---


# Question
Title: Prove that every two vertices in graph are connected by a path of some length
I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning.

Every node in network is connected to exactly 3 others. Is it possible for me to prove that every two nodes have a path of length O(n/3) between them? I can show people that the way I setup the network guarantees some existence of relatively fast routes. The n is much more than 3

Thank you

# Answer
> 2 votes
$O(n/3)$ doesn't mean what you think it means: in particular, $O(n/3)$ denotes exactly the same class of functions as $O(n)$. However, it's not true that the longest distance between two vertices in a $3$-regular graph is roughly $n/3$. Consider the graph

```
o---o       o       o             o       o---o
|\ / \     /|\     /|\           /|\     / \ /|
| X   o---o | o---o | o-- ... --o | o---o   X |
|/ \ /     \|/     \|/           \|/     \ / \|
o---o       o       o             o       o---o

```

(where the `X`s denote two crossing edges). The distance from the top-left vertex to the top-right vertex is approximately $3n/4$.

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


# Question
Title: Polymorphism restriction on lambda-bound variables in HM
I'm trying to implement the Hindley-Milner type system, following Milner 1978, "A Theory of Type Polymorphism in Programming" (link). In the Hindley-Milner system, a polymorphic let-bound expression may take on a different type each time it is referenced. For example, we can have `let id = (λx · x) in (id 3, id true)` where `id` has type `α → α` with two instantiations, `α = int` and `α = bool`. However, the variable of a lambda expression is not permitted to be polymorphic in this way: `λf · (f 3, f true)` is not a well-typed expression.

To prevent this restriction from being "cheated" by something like `λx · let x2 = x in ...`, we must recognize some restriction on the polymorphism of let-variables as well. Milner 1978 describes it as follows:

> We decree that in instantiating the type of a variable bound by *let* or by *letrec.* only those type variables which do not occur in the types of enclosing λ-bindings (or formal parameter bindings) may be instantiated. We call such instantiable variables (in a generic type) generic type variables.

However, using what seems to me the obvious interpretation of "enclosing λ-bindings" (namely, that the let-expression should occur in the `e` of some `λx · e`), Milner's prescription does not seem to cover all of the cases where it is necessary to prevent some type variables of a let-binding from being polymorphically instantiated. Consider the following expressions:

```
let id = (λx · x) in (id 3, id true)
let id = (λx · x) (λx · x) in (id 3, id true)

```

While the first one is of course acceptable, I believe the second one should not be, as if this type of code is allowed, it becomes impossible in general for a compiler to generate statically typed code. And indeed, OCaml rejects the statement `let id = (fun x -> x) (fun x -> x) in (id 3, id true)`.

So my questions are:

1. Am I interpreting the paper incorrectly?
2. How should I determine whether a type variable in a let-bound expression is eligible to be instantiated with multiple types?

# Answer
Yes, you are restricting it too much. The second code is perfectly fine.

For the record, Haskell has no issue with your code:

```
> let myid = (\x->x)(\x->x) in (myid 'a', myid True)
('a',True)

```

and Ocaml as well works fine, after eta-expansion:

```
let myid y = (fun x -> x)(fun x -> x) y in (myid 'a', myid true);;
- : char * bool = ('a', true)

```

Eta expansion is needed in Ocaml, I think, because of the value restriction, where a binding is not generalized unless it is a function (`let f x = ...` instead of `let f = ...`). This restriction was needed to avoid some soundness issues with mutable variables -- remember Ocaml is not a "pure" language, and allows side effects everywhere.

Anyway, Hindley-Milner should generalize `let f = (\x->x)(\y->y) in ...` just fine. First, `\y->y` is given the monotype $\alpha\to\alpha$, where $\alpha$ is a fresh type variable. Then `\x->x` is given $\beta\to\beta$, with a fresh $\beta$. Then we type check the application, which succeeds and unifies $\beta = (\alpha\to\alpha)$. The resulting type for the application is $\alpha\to\alpha$. Since $\alpha$ is not present in the environment, it can be generalized so the we get $f : \forall \alpha.\\, \alpha\to\alpha$.

Bonus exercise: type check the following

```
# let myid y = (fun x -> x)(fun x -> x) y ;;
val myid : 'a -> 'a = <fun>
# myid myid myid true;;
- : bool = true

```
> 6 votes

---
Tags: typing, type-inference
---


# Question
Title: Improvement of algorithm due to constrained graph
This algorithm runs natively in O(V * E^2).

The description states that

> The running time of O(V * E^2) is found by showing that each augmenting path can be found in O(E) time, **that every time at least one of the E edges becomes saturated (an edge which has the maximum possible flow)**, \[...\]

My graph has the property that at there are exactly |V| edges with a limited capacity, that is, all remaining |E|-|V| edges have an unlimited capacity; any amount of flow can pass through them.

Given that those edges with an unlimited capacity can never become saturated, can I safely assume that a maximum of |V| augmenting paths will be found, and therefore the complexity reduced to O(V * E)?

If so, is there an adequat proof for the assumption made in the Wiki article? It only states *There is an accessible proof in Introduction to Algorithms.*

# Answer
> 5 votes
Edmonds-Karp algorithm works by building successive flows $f\_0, \dots, f\_n$ where each flow $f\_{i+1}$ can be obtained by combining $f\_i$ and a path in the "residual graph" $G\_{f\_i}$ obtained through a BFS (the residual graph is just the original graph where we removed full edges).

Now, the idea of the proof in *Introduction to Algorithms* is to introduce a distance $\delta\_f(s,v)$ from the source node $s$ to all nodes $v\in V$ in the graph $G\_f$. Then they prove 4 things:

* $\delta\_{f\_i}(s,v)$ can only increase with $i$ (i.e. $\delta\_{f\_i}(s,v)\leq \delta\_{f\_{i+1}}(s,v)$) that is their lemma 26.7;
* if an edge $(u,v)$ is not saturated by a flow $f\_i$ (i.e. $(u,v)$ is not saturated in $f\_{i-1}$ but is in $f\_i$) and then unsaturated in the flow $f\_j$ with $j\>i$ then $\delta\_{f\_j}(s,v)-\delta\_{f\_i}(s,v)\geq 2$. That means an edge can become saturated at most $1+|V|/2$ times (since $\delta\_{f}(s,v)\leq|V|$);
* at each BFS, an edge become saturated.

By combining these, we have that each edge can be saturated at most |V|/2+1 times ($\delta\_{f}(s,v)\leq |V|$) and that the Edmonds-Karp algorithm is in $O(E×(E×V))$ where $O(E)$ is the time taken for one BFS and $O(E×V)$ the number of BFS (i.e. the maximum number of times an edge can become saturated).

For you the complexity is O(K×V×E) : finding a path is in $O(E)$ and you might have to find $(|V|/2+1)×K$ times an augmenting path where $K$ is the number of edges that can become saturated (i.e. $K=V$ for you thus $O(E×V^2)$).

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Computing snapshot of Turing machine from previous snapshots in logarithmic space?
> To prove that $P \subseteq P\_{\ poly}$\[see book by Arora and Barak, chapter 6, page no 105\]

Proof : Let $M$ be an oblivious TM and running time is $T(n)$, let $x \in \\{0,1\\}^\* $ be some input for $M$ and define the transcript of $M$'s execution on $x$ to be the sequence $z\_1,z\_2,..z\_{T(n)}$ of snapshots (the machine's state and symbol read by all heads) of the execution at each step in time.

We can encode each such snapshot $z\_i$ by a constant-sized binary string, and furthermore, **we can compute the string $z\_i$ based on input $x$, the previous snapshot $z\_{i-1}$ and snapshot $z\_{i\_1},z\_{i\_2},\cdots ,z\_{i\_k}$, where $z\_{i\_j}$** denotes the last step that $M$ 's jth head was in the same position as it is in the ith step.

The composition of all these constant-sized circuits gives rise to circuit that computes from the input $x$ the snapshot $z\_{T(n)}$. This requires polynomial space, but I want to do this whole computation in logarithmic space.

**My question :** How to compute snapshot $z\_i$ of Turing machine $M$ from previous snapshots using logarithmic space?

# Answer
What you seem to be asking is what is the complexity of computing each bit in the sequence of snapshots. The complexity depends on the way you encode the snapshots. Here are a few options:

1. Encode the state of the machine, the position of the head, and the tape. Computing a bit of the tape requires knowing whether the head is currently at that position or at a neighboring position. Since in general a polytime machine has a polysize tape, this requires circuits accessing $\Theta(\log n)$ inputs.
2. Encode the state of the machine and the tape, where the tape alphabet is enlarged to include another bit, signifying whether the head is at that position or not. Now each tape bit only depends on a constant number of bits. However, determining the next state is (still) very costly, since we need to know the value under the head.
3. Encode the state of the machine and the tape, where the tape alphabet is enlarged to include the "head bit" as well as the symbol currently under the head. Now each bit indeed depends only on a constant number of bits.

Of course, given any formula, we can always convert it to a 3CNF using auxiliary variables without blowing it up by too much. What I outline above is a particular way of doing this transformation in the case at hand.
> 0 votes

---
Tags: complexity-theory, turing-machines, circuits
---


title: When is a bound asymptotically tight?

text:
# Question
Title: When is a bound asymptotically tight?
> What does it mean that the bound $2n^2 = O(n^2)$ is asymptotically tight while $2n = O(n^2)$ is not? We use the o-notation to denote an upper bound that is not asymptotically tight.

The deﬁnitions of O-notation and o-notation are similar. The main difference is that in $f(n) = O(g(n))$, the bound $0 \leq f(n) \leq cg(n)$ holds for **some constant,** $c\>0$, but in $f(n) = o(g(n))$, the bound $0 \leq f(n) \< cg(n)$ holds for **all constants,** $c\>0$.

So what is the difference in big-O notation and small-o notation?

# Answer
We say that a bound $f(n) = O(g(n))$ is tight if in fact $f(n) = \Theta(g(n))$, that is, if also $g(n) = O(f(n))$. So $2n^2 = O(n^2)$ is tight since $n^2 = O(2n^2)$, whereas $2n = O(n^2)$ is not tight since $n^2 \neq O(2n)$.

As you mention in your question, if $f(n) = o(g(n))$ then the bound $f(n) = O(g(n))$ is not asymptotically tight. However, there is a third option: it could be that $f(n) = O(g(n))$, $f(n) \neq o(g(n))$, and yet the bound $f(n) = O(g(n))$ is not asymptotically tight. An example is $f(n) = n|\sin n|$ and $g(n) = n$.

One could also *define* $f(n) = O(g(n))$ to be tight if $f(n) \neq o(g(n))$. In that case the "third option" is that $f(n) = O(g(n))$ is asymptotically tight although $f(n) \neq \Theta(g(n))$.
> 5 votes

---
Tags: asymptotics
---


# Question
Title: How to find whether a grammar's language is finite or infinite?
I have this context-free grammar and I want to find out whether its language is finite or infinite.

```
S -> XY|bb  Step 1
X -> XY|SS  Step 2
Y -> XY|SS  Step 3

```

So I would do

```
S -> XY            From step 1
S -> YYY           From step 2
S -> SSYY          From step 3
S -> SSSSY         From step 3
S -> SSSSSS        From step 3
S -> bbSSSSS       From step 1
S -> bbbbSSS       From step 1
S -> bbbbbbSSS     From step 1
S -> bbbbbbbbSS    From step 1
S -> bbbbbbbbbbS   From step 1
S -> bbbbbbbbbbbb  From step 1

bbbbbbbbbbbb

```

So I know how to generate words like this but how to find out whether the language is finite or infinite?

# Answer
A language is infinite if it can generate infinitely many words. In order to prove that a language generated by a grammar is infinite, you need come up with some infinite list of words generated by the grammar. Proving that the language is finite is slightly more messy—you need to make a list of all possible derivations, and show that all of the terminate.

In your case, you have the derivation $S\to^\*SSSS$, which suggests that the language is infinite. Can you come up with an infinite list of words generated by this grammar?
> 8 votes

# Answer
The only way a finite system (grammar) can generate an infinite set of words is by repeating stuff: you start at $S$ and keep expanding until you hit a non-terminal that you've already expanded. So now you can just copy the sub-tree corresponding to that symbol and paste it. You can do this forever so it must be that the grammar generates infinitely many words.

You can use a directed graph to represent a context-free grammar: think of the grammar specification as being an adjacency list of some graph (In the first rule, there is an edge from $S$ to $X$ and from $X$ to $Y$ and so on). Now, the grammar generates an infinite set if and only if the graph is cyclic (this needs proof). A technicality is that the cycle should generate something other than the empty word. This gives a general procedure for deciding whether a grammar generate an infinite set of words or not.

The graph corresponding to your example looks like:

There are lots of cycles. $S^\*$ ($(bb)^\*$ is a subset of the language that the grammar generates) is one example.
> 6 votes

# Answer
The language is infinite iff its grammar can generate an infinite number of words, or equivalently iff a recognizing automaton can recognize an infinite number of words.

This is something that you have to prove.

For that purpose you can rely on some facts.

* a language is infinite if and only if contains words of unbounded length, i.e. longer than any size you may choose.

(*Useful and easy exercise: prove that the total number of words of size less than some integer $n$ built on a finite alphabet $\Sigma$ is always finite.* \- this proves the above statement)

This tells you two things

+ that if you can show that the language contains words of unlimited size, it is indeed infinite.
    + that you can always count on that property to prove language infinity
* To prove that words can have unlimited size, you must use an induction proof. And, when using a grammar definition of the language, it will have to be based on non-terminals as they are the only part of a derived string that can be replaced by something longer.

For example, if the initial symbol derives on a string that contains it plus other symbols, including a terminal, and only non-terminal that derive on a terminal word ... the you may think on using that for an induction proof.

Well ... what about trying?

And try to think why I specify these constraints. (remember, the words of the language contain only terminals)

By the way, the recursion must sometimes be on another non-terminal than the initial one (S). But it will do in your case.
> 5 votes

# Answer
I recall from the 1960's a technique for at least some classes of formal grammars for finding cycles (loops generating an infinite language ) in a grammar. A Boolean matrix is created for all rules or productions in the grammar. All terminals and non-terminals are listed as the vertical side of the matrix and the horizontal side of the matrix. There are zeros in the matrix where vertical side of the rule does not directly produce a symbol across the horizontal side. There ones where the left part (row title) directly produces the right part (column title)

This captures all the direct transitions. This matrix is multiplied times its transpose. The martix multiplication is simplified by the use of Warshall's algorithm. The result is the reflexive transitive closure of the grammar. The grammar is cycle free if the right to left diagonal of the resulting matrix is all zeros.
> 3 votes

---
Tags: formal-languages, context-free, formal-grammars, proof-techniques, induction
---


# Question
Title: Algorithm for smallest String without a given prefix
How can I find the lexicographicaly smallest string that doesn't start with a given prefix AND is lexicographicaly bigger than the given prefix? Example:

1. prefix : cat; next string : cau
2. prefix : cazz next string; cb

# Answer
> 1 votes
There is no solution if all characters in the input string are equal to the last character in the alphabet (this includes the case of the empty string).

Otherwise, as long as the last character in the input string is the last character in the alphabet, remove it from the string. Then replace the last character of the result with the next character in the alphabet.

---
Tags: strings, substrings
---


# Question
Title: Function problems and $FP \subseteq FNP$
I find it hard to find formal definitions of function complexity classes. Here are two from Wikipedia.

> A binary relation $P(x,y)$ is in **FP** if and only if there is a deterministic polynomial time algorithm that, given $x$, can find some $y$ such that $P(x,y)$ holds.

The definition above seems to imply that for all relations in **FP** it holds that for every $x$ there exists at least one $y$ which its length is polynomial in the length of $x$. However, it does not seem to restrict that there exists more $y$ for that $x$ so that $P(x,y)$ holds while $y$ is exponentially longer than $x$.

> A binary relation $P(x,y)$, where $y$ is at most polynomially longer than $x$, is in **FNP** if and only if there is a deterministic polynomial time algorithm that can determine whether $P(x,y)$ holds given both $x$ and $y$.

This definition implies that for a relation in **FNP** it need not to be true that there exists at least one $y$ for every $x$ so that $P(x,y)$ holds. It implies however that if $P(x,y)$ holds, $y$ has to be at most polynomially longer than $x$.

In literature, one can read that **FP** $\subseteq$ **FNP**. As far as I do (or do not) understand, this can not be true. It is possible that for some relation $R(x,y) \in$ **FP** there exists a $(x,y)$ so that $R(x,y)$ holds and $y$ is exponentially longer than $x$. Because of this, this relation does not belong to **FNP** and therefore **FP** $\not\subseteq$ **FNP**.

Are the definitions on Wikipedia incomplete? Am I missing something?

Either way, what are some good sources to read up on function problems (I deem myself knowledgeable of decision problems)?

# Answer
I found the following in Papadimitriou's book *Computational Complexity* which I've found satisfying.

> Let $R \subseteq \Sigma^\* \times \Sigma^\*$ be a binary relation on strings.
>
> $R$ is called *polynomially decidable* if there is a deterministic Turing Machine deciding the language $\\{x;y : (x,y) \in R\\}$ in polynomial time.
>
> We say that $R$ is *polynomially balanced* if $(x,y) \in R$ implies $|y| \leq |x|^k$ for some $k \geq 1$.

Then Papadimitriou notes the following, which basically is another definition for **NP**:

> Let $L \subseteq \Sigma^\*$ be a language. $L \in$ **NP** if and only if there is a polynomially decidable and polynomially balanced relation $R$, such that $L = \\{x : (x,y) \in R$ for some $y \\}$.

A few dozen pages later...

> The *function problem associated with* $L$ \[$\in$ **NP**\], denoted $FL$ \[here $L$ stands for said language, not logspace\], is the following computational problem:
>
> Given $x$, find a string $y$ such that $R\_L(x,y)$ if such a string exists; if no such string exists, return "no".

Then

> The class of all function problems associated as above with languages in **NP** is called **FNP**. **FP** is the subclass resulting if we only consider function problems in **FNP** that can be solved in polynomial time.
> 4 votes

# Answer
Let's forget about the Wikipedia definitions and come up with our own.

> A function $f$ is in $\mathsf{FP}$ if there is a polytime Turing machine that on input $x$ outputs $f(x)$.
>
> A function $f$ is in $\mathsf{FNP^\ast}$ if:
>
> 1. The function $f$ is polynomially bounded: there exists a polynomial $p$ such that $|f(x)| \leq p(|x|)$.
> 2. There is a polytime Turing machine that given $x,y$ determines whether $f(x)=y$.

If $f$ is in $\mathsf{FP}$ then it is definitely polynomially bounded. Since we can compute $f(x)$ in polynomial time, given $x,y$ we can compute $f(x)$ and compare it to $y$, all in polynomial time.

Consulting the complexity zoo, it seems that $\mathsf{FNP}$ actually has a different definition, and that $\mathsf{FP}$ has two different and incompatible definitions, one of them being the one stated above.
> 3 votes

# Answer
I want to add another set of definitions from *Automata, Computability and Complexity* by Elaine Rich.

> **The Class FP**: A binary relation $Q$ is in $\mathsf{FP}$ iff there is a deterministic polynomial time algorithm that, given an arbitrary input $x$, can find some $y$ such that $(x,y) \in Q$.
>
> **The Class FNP**: A binary relation $Q$ is in $\mathsf{FNP}$ iff there is a deterministic polynomial time verifier, given an arbitrary input pair $(x,y)$, determines whether $(x,y) \in Q$. Equivalentely, $Q$ is in $\mathsf{FNP}$ iff there is a nondeterministic polynomial time algorithm that, given an arbitrary input $x$, can find some $y$ such that $(x,y) \in Q$

This is only slightly different than the definitions found on Wikipedia but they imply different things nonetheless. Most importantly, Elaine Rich her definition of $\mathsf{FNP}$ doesn't imply that if $(x,y) \in Q$, $y$ *has* to be polynomial in $x$. It's likely that the wiki-definitions are sloppy copies of these.

From these definitions it is more clear that $\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Conway's Game Of Life Problem Parallel (OpenMP)
I am currently working in solving Conway's Game Of Life problem for a Parallel and Distributed Computing course.

The problem is a little bit different form the original, in the sense that instead of having a 2D representation of the cells we have a 3D one, each cell is represented by three ints. When considering neighbours, only the x + 1, x - 1, y + 1, y - 1, z + 1 and z - 1 are considered (no diagonals).

The input of the problem is constituted by the size of the cube (size) where the cells are present, followed by a list of positions of live cells.

The number of cells, is in the order of O(size^2), and the space is in the order of O(size^3).

My current implementation uses C++ maps, in which a key is a tuple with x, y and z, and the value is an integer telling in that position the cell is alive or not. My current approach is to just go through every position available in the cube and check the number of neighbours and update that position accordingly, but i believe this is not ideal because the number of live cells is in the order of O(size^2) and not O(size^3).

My question is how would you improve this solution ? Is there a better data structure to use ? Considering that I have to build an OpenMP implementation (shared memory) for very large input cases (size \> 10000).

Thank you !

# Answer
> 1 votes
There is a simple solution. Instead of storing a hashmap of *all* positions, store the set of only the positions that are currently alive. Live cells are included in the set; dead cells are not. When you want to know whether a particular cell is alive or not, look up that position in the set; if it is found, then the cell is alive, otherwise the cell is dead. You can store the set as a hashtable.

You said that you expect only about O(size^2) cells to be alive. My proposal reduces the space complexity to O(size^2), instead of O(size^3). Also, the running time to check whether a particular cell is alive will be O(1). The running time to enumerate all live cells will be O(size^2).

It follows that the running time to compute the next state of the world will be O(size^2). Since each cell has only 4 neighbors, you only need to enumerate O(5 * size^2) = O(size^2) many cells (all of the live cells and their neighbors) to see which will be alive in the next iteration. To tell whether a cell will be alive in the next iteration can be done by examining its state and the state of its 4 neighbors, which can be done in O(1) time.

This approach should also generalize nicely to a parallel/distributed implementation.

This all assumes that the number of live cells is limited to O(size^2) for all iterations. That might be a dubious assumption in practice: the number of live cells can quickly grow to O(size^3), for some initial configurations (in particular, it might take only O(lg size) iterations to go from O(size^2) to O(size^3) live cells).

---
Tags: algorithms, data-structures, parallel-computing, shared-memory
---


title: Set Cover and additional constraints

text:
# Question
Title: Set Cover and additional constraints
Consider the following bipartite graph:

Each node in red color represents a warehouse $w = \\{ 1,2,3\\} $. For this example we have three warehouses located at different locations. Each warehouse has a cost of opening ${c\_w} = \\{ 7,8,10\\} $ for all $w$. In addition to that, each warehouse provides different resources ${r\_1},{r\_2}$ or ${r\_3}$ required for stores that they have connection to be opened.

Each node in blue color is a store $s = \\{ 1,2,3,4,5\\} $. We have five stores for this example. Each store has its opening cost ${c\_s} = \\{ 9,11,12,10,8\\} $ for all $s$. In addition to that each store requires some resources that can be provided by one or more warehouses it is connected to.

Each edge between store and warehouse has some cost. You can think about it as a distance from store location to a warehouse location. Thus, in order to open a store ${s\_i}$ it should be connected to one or more warehouses which, together provide resources that ${s\_i}$ needs.

The problem is to find a subset of possible warehouses, a subset of possible stores, and a plan to serve each open store by a list of connected open warehouses. Our goal is to compute the total profit from opened stores minus the total cost from opening warehouses and servicing open stores using those open warehouses is maximized.

For this example, the optimal plan:

* Open $w = 1$, provide ${r\_1}$ to $s = 1$, then open it.
* Open $w = 2$, provide $\\{ {r\_1},{r\_2}\\} $ to $s = 2$, then open it.
* Open $s = 3$, by providing resources from $w = \\{ 1,2\\} $

Thus, we opened 2 warehouses $w = \\{ 1,2\\} $ that provided resources for $s = \\{ 1,2,3\\} $, which we decided to open and we used only 4 edges. The optimal profit for this example is ${p\_{OPT}} = 9 + 11 + 12 - (7 + 8 + 3 + 3 + 3 + 4) = 4$

Now the task is to model this problem as mixed integer programming, more specifically i think using binary variables i have to define the objective function and all required constraints, also stating new variables.

I have noticed that each ${r\_s}$ can be considered a universe set and each ${r\_w}$ or union of ${r\_w}$s must cover ${r\_s}$. This problem, was definitely, designed with a flavor of set covering. However, it was made more complicated by adding extra constraints.

I need to model this problem as MIP. So far, i managed to determine the objective function and came up with some constraints that allow me to chose edges to warehouses that cover the store resources.

My objective function: $$\max :\sum\nolimits\_{i:s} {{c\_s}} {z\_i} - \left( {\sum\nolimits\_{j:w} {{c\_w}{y\_j} + \sum\nolimits\_{k:e} {{c\_e}{x\_k}} } } \right)$$where ${z\_i},{y\_j},{x\_k}$ - binary values and ${c\_e}$ is the cost of edge.

Ok, since this example is short i will write my objective function in expanded form so it becomes clear about my notation:

My objective function (expanded form): $\max :9{z\_0} + 11{z\_1} + 12{z\_2} + 10{z\_3} + 8{z\_4} - 7{y\_0} - 8{y\_1} - 10{y\_2} - 3{x\_{00}} - 5{x\_{01}} - 3{x\_{02}} - 3{x\_{11}} - 4{x\_{12}} - 5{x\_{13}} - 7{x\_{22}} - 6{x\_{23}} - 4{x\_{24}};$

* ${z\_i} = 0$ if we don't open store $s = i$ and ${z\_i} = 1$ otherwise
* ${y\_i} = 0$ if we don't open warehouse $w = i$ and ${y\_i} = 1$ otherwise
* ${x\_{ij}}$ means edge from store $j$ to warehouse $i$.
* ${x\_{ij}} = 0$ if we don't use it and ${x\_{ij}} = 1$ otherwise

Now i'm trying to set the following constraints:

1. For each ${s\_i}$, i consider ${r\_{{s\_i}}} = U$ that is a universe set for which i should cover each element.
2. Then i apply $\sum\nolimits\_{S:v \in S} {{y\_S} \ge 1,\\,\\,\forall v \in U} $, that is i pick 1 element from $U$ and determine which adjacent ${r\_{{w\_j}}}$ can cover it.
3. For each resource required by store, it is covered by one or more sets from 2.
4. Then i ensure that store is opened if all of its resources are covered by reachable warehouse(s)

Here is my constraint examples for $s = 2 $.

Case $s = 2$:

Denote ${y\_{ij}}$ a warehouse $i$ resource set that covers first element from the resource set of store $j$, ${z\_j}$ - opening store $j$, ${r\_{kj}}$ - required resource ${r\_k}$ from store $j$. All indexes starting from 0. Now i have

$$\begin{gathered} {y\_{01}} + {y\_{11}} \ge1; \hfill \\ {y\_{11}} \ge 1; \hfill \\ {r\_{11}} \le {y\_{01}} + {y\_{11}}; \hfill \\ {r\_{11}} \ge {y\_{01}}; \hfill \\ {r\_{11}} \ge {y\_{11}}; \hfill \\ {r\_{21}} \le {y\_{11}}; \hfill \\ {r\_{21}} \ge {y\_{11}}; \hfill \\ {z\_1} \ge {r\_{11}} + {r\_{21}} - 1; \hfill \\ {z\_1} \le {r\_{11}}; \hfill \\ {z\_1} \le {r\_{21}}; \hfill \\ \end{gathered} $$

In a first line i determine that ${r\_1}$ is contained in ${w\_1}$ and ${w\_2}$ sets. The second required resource ${r\_2}$ is only in ${w\_2}$ set. Then i ensure that either one or both sets cover ${r\_1}$ same with ${r\_2}$. Finally i want to make sure that store can be opened if all resources can be supplied by warehouse. Now from this point i do something wrong because ${z\_i}$ is always 1 if some reachable warehouse(s) can cover all resources. So basically with this encoding the solver always sets ${z\_i}$ and i need to somehow link ${z\_i}$ with warehouse opening. I guess instead of using ${z\_i}$ to check if all resources can be obtained i need to introduce another dummy variable say $a$ and define a constraint something like: $a \to {\text{ some }}{w\_i}$

As you can see from my constraints i'm missing a link between ${z\_i},{y\_j},{x\_{ij}}$. I managed to create a set of constraints that answer the question: Can any warehouse or their union cover all resources needed by some store. If they do ${z\_i}$ is always set to 1 and i don't want it to be necessary set to 1 if the resource set is covered. What i need is to add some logic that will force the objective function to choose weather to open ${z\_i}$ and what ${y\_j}$ and ${x\_{ij}}$ should be set to 0/1 in order to maximize the objective function.

# Answer
> 1 votes
Once you've defined the variables $x\_{ij},y\_j,z\_i$, all you need to do is add ILP constraints that enforce the domain requirements. The general approach is: write down the list of domain requirement, then go through them one-by-one, and for each, translate it to ILP.

What are the domain requirements? First, if you open store $j$, then you must enable a set of edges that are sufficient to provide all the resources that store $j$ needs. Second, if you enable an edge between some warehouse and some store, then that warehouse must be opened.

Now we express each of the domain requirements as ILP. Here is how we express the first domain requirement. For each store $j$ and each resource $r$ required by store $j$, we require

$$\sum\_{j \in S\_r} x\_{ij} \ge y\_j,$$

where $S\_r$ is the set of warehouses that supply resource $r$. This ensures that, for each resource $r$ needed by store $j$, if you open store $j$, then you must enable at least one edge that can supply resource $r$ to store $j$.

Enforcing the second domain requirement is relatively straightforward, once you know that you can represent a logical implication as a less-than-or-equal constraint. For each warehouse $i$ and each store $j$, we require

$$z\_i \ge x\_{ij}.$$

This ensures that if you enable an edge, then the corresponding warehouse needs to be open.

Now you ask the ILP solver to find an assignment that satisfies all of these inequalities, and minimizes the value of the objective function.

---
Tags: linear-programming, integer-programming, modelling
---


# Question
Title: Computing the longest common substring of two strings using suffix arrays
After I learned how to build a suffix array in $O(N)$ complexity, I am interested in discovering the applications of the suffix arrays. One of these is finding the longest common substring between two strings, in $O(N)$ time. I found on the internet the following algorithm:

1. merge the two strings $A$ and $B$ into one string $AB$
2. compute the suffix array of $AB$
3. compute the $LCP$(longest common prefix) array
4. the answer is the largest value $LCP\[i\]$

I tried to implement it, but as many implementation details were not said(i.e. when concatenating the strings, should I put a special character between them($AcB$)?), my code failed on many test cases. Could someone elaborate more on this algorithm?

Thanks in advance.

**Note:** I do not guarantee the correctness of this algorithm; I found it on a blog, and I'm not sure it is working. If you think it is incorrect, please suggest another algorithm.

# Answer
> 21 votes
Your algorithm is **incorrect**. I assume you know how to compute the suffix array and the LCP array of a string, that is, their efficient implementation. As has been pointed out in the comments, you should try to understand what each component is, and why it works.

First of all, is the suffix array ($SA$) of a string. A suffix array is basically all the suffixes of the string $S$ arranged in ascending lexicographic order. More specifically, the value $SA\[i\]$ indicates that the suffix of $S$ starting from position $SA\[i\]$ is ranked $i$ in the lexicographic ordering of all suffixes of $S$.

Next is the $LCP$ array. $LCP\[i\]$ indicates the length of the longest common *prefix* between the *suffixes* starting from $SA\[i-1\]$ and $SA\[i\]$. That is, it keeps track of the length of the longest common prefix among two consecutive suffixes of $S$ when arranged in lexicographic order.

As an example, consider the string $S = abbabca$. The suffixes in lexicographic order would be $\\{a, abbabca, abca, babca, bbabca, bca, ca\\}$, so $SA = \[7, 1, 4, 3, 2, 5, 6\]$ for a 1-indexed array. The $LCP$ array would be $LCP = \[-, 1, 2, 0, 1, 1, 0\]$.

Now, given two strings $A$ and $B$, we concatenate them as $S = A\\#B$, where $\\#$ is a character not present in both $A$ and $B$. The reason for choosing such a character is so that when computing the LCP of two suffixes, say $ab\\#dabd$ and $abd$, the comparison will break off at the end of the first string (since it only occurs once, two different suffixes will never have it in the same position), and won't *"overflow"* into the other string.

Now, it can be seen that you should be able to see why you only need to see consecutive values in the $LCP$ array (the argument is based on contradiction and the fact that the suffixes in $SA$ are in lexicographic order). Keep checking the $LCP$ array for the maximum value *such that* the two suffixes being compared do not belong to the same original string. If they don't belong to the same original string (one begins in $A$ and the other in $B$), then the largest such value is the length of the largest common substring.

As an example, consider $A = abcabc$ and $B = bc$. Then, $S = abcabc\\#bc$. Sorted suffixes are $\\{abc\\#bc, abcabc\\#bc, bc, bc\\#bc, bcabc\\#bc, c, c\\#bc, cabc\\#bc\\}$.
$\begin{align\*} SA &= \[4, 1, 8, 5, 2, 9, 6, 3, 7\] \\ LCP &= \[-, 3, 0, 2, 2, 0, 1, 1, 0\] \end{align\*}$

Now, the greatest value is $LCP\[2\] = 3$, but it is for $SA\[1\]$ and $SA\[2\]$, both of which start in the string $A$. So, we ignore that. On the other hand, $LCP\[4\] = 2$ is for $SA\[3\]$ (corresponds to the suffix $bc$ of $B$) and $SA\[4\]$ (corresponding to suffix $bcabc\\#bc$ of $A$). So, this is the longest common substring between the two strings. For getting the actual substring, you take a length $2$ (value of the greatest *feasible* $LCP$) substring starting from either $SA\[3\]$ or $SA\[4\]$, which is $bc$.

# Answer
> 1 votes
The algorithm you found online is not entirely correct. As mentioned by Paresh, it will fail in the example given by him.

However, if you ensure that while checking the LCP, you only check the LCP of substrings of different strings. For example, if you are finding the LCS of strings A and B, then you need to ensure that the adjacent entries of the Suffix Array while checking for LCP are both not from the same string.

More details here.

# Answer
> 0 votes
I think something like the algorithm you cite should indeed work if a character that is not part of the character set is used as a separator, and the suffix/prefix arrays are built to *exclude* all strings that contain the separator, probably the intention of the designer. this is basically equivalent to building suffix/prefix arrays for the two separate strings.

it would be helpful for future ref if you posted a link to the algorithm. note that wikipedia has the algorithm for this in pseudocode & many other algorithms. and there are implementations in most standard languages available online.

---
Tags: algorithms, suffix-array
---


# Question
Title: Do networking ports come from "port-mapped I/O"?
Do networking ports come from "port-mapped I/O"?

I was watching a hardware basic video by Brian Will:

https://www.youtube.com/watch?v=9-KUm9YpPm0

And they brought up this concept at 18:15

Initially, I thought it makes sense that networking ports come from the implementation of port-mapped I/O, but it's strange that the video uses the term "devices" instead of "applications" when referring to doing I/O tasks with ports.

# Answer
Moving my comment to an answer, while the word "port" is being used in the same non-technical sense for both "port-mapped I/O" and for "network ports", they have literally no technical connection.

In port-mapped I/O, the "ports" are accessed with special CPU instructions (`in`, `out` in the x86 family) which communicate with hardware devices. For x86, at least, due to the limited "address space" of port-mapped IO (and other reasons), memory-mapped IO or direct memory access are used for bulk data movement. There's nothing magical about port-mapped I/O. Modern ARM processors, for example, don't have it at all and instead rely entirely on memory-mapped I/O.

Network "ports" are just pieces of data in TCP or UDP packets to allow multiplexing connections to a single IP address (or host because it technically could be over a network level protocol other than IP). As far as the network hardware and CPU is concerned, the port is just another piece of data in the packet like any other. The operating system will use the port to route the packet to the appropriate application on the host
> 1 votes

---
Tags: operating-systems, computer-networks
---


# Question
Title: Can Nondet Rabin Tree automaton be determinized?
In other words, are they equally powerful?

(for *word* automata the answer is "yes"; this question is about *tree* automata).

(i am talking about tree automata that work on $in$finite trees)

# Answer
The answer is no, nondeterministic Rabin automata are more expressive than deterministic ones.

As an example, consider the language of $\\{a,b\\}$-labeled binary trees that contain at least one $b$.

It's easy to construct a two-state Büchi tree automaton for this language (and hence a Rabin automaton), but there is no deterministic equivalent.

You can look at Lemma 6.1 here, for a start.
> 3 votes

---
Tags: reference-request, nondeterminism, tree-automata
---


# Question
Title: Turn biased random number generator into uniform
I'm looking at a problem in the book Introduction to Algorithms by Cormen et al. It says that if we are given a random number generator rand() which satisfies the distribution:

$P(X = 0) = p,\\;\\;P(X=1)=1-p,\\;\\;0\<p\<1$,

then we can use rand() as a subroutine to create a unbiased sampler from the set {0,1}. My idea for this is along the following lines:

1. Choose some fairly large even integer n.
2. Create a table "t" containing two integers.
3. Loop over $i=1,\ldots,n$ sampling $x=rand()$ for each $i$. When $i$ is even increment $t\[i\]$ and when odd increment $t\[1-i\]$.
4. Return $0$ if $t\[0\]\geq t\[1\]$ and vice versa.

Now the expected value for $t\[0\]=t\[1\]=n/2$, so this should give a value very close to the uniform distribution. The only problem is that the set of outcomes in (4) is biased towards $0$, so for any fixed $n$, we do not get a uniform distribution, although we do get it in the limit. There has to be a way to get $n$ to depend on some random value to balance it out, but I can't figure out how.

Anyone have any other ideas how to approach this? The key in the problem was that we do not know $p$.

# Answer
For general $p$ you can't generate a random bit using a finite number of samples. Indeed, suppose you could do it using $n$ samples. Let $c\_k$ be the number of inputs of Hamming weight $k$ which will cause you to return $1$. For your generator to be unbiased, you need $$ \frac{1}{2} = \sum\_{k=0}^n c\_k p^k (1-p)^{n-k} = \sum\_{\ell=0}^n \left(\sum\_{k=\ell}^n c\_k (-1)^{\ell-k} \binom{n-k}{\ell-k} \right) p^\ell. $$ If $p$ is transcendental or of the form $a/b$ for odd $b$ then the equation $\frac{1}{2} = \sum\_{\ell=0}^n d\_\ell p^\ell$ has no integer solutions $d\_0,\ldots,d\_n$. In particular, even if you know $p$, then in these cases no finite number of samples can be used to extract even one uniformly random bit.

The standard solution, attributed (IIRC) to von Neumann, is to use the following algorithm:

1. Repeatedly sample two biased samples $r\_1,r\_2$ until $r\_1 \neq r\_2$.
2. Return $r\_1$.

Conditioned on $r\_1 \neq r\_2$, the two outcomes $(r\_1,r\_2)=(0,1)$ and $(r\_1,r\_2)=(1,0)$ have the same probability, and so the result is an unbiased bit.

How efficient is this generator? The probability that $r\_1 \neq r\_2$ is $2p(1-p)$, and so on average you will need $1/(2p(1-p))$ samples per bit. Compare that to the optimal extractor given by Shannon's source coding theorem: extracting $n$ bits should take $n/H(p) + o(n)$ samples with high probability (when $p$ is known).

The plot shows that the von Neumann algorithm is reasonably good but not optimal.
> 5 votes

# Answer
I think you can roll twice each time. If you get (0,1), return yield of 0. If (1,0), return 1. Because the probability of (0,1) and (1,0) are both p\*(1-p), the probability of returning 0 and 1 is identical. Of course, this algorithm has a risk of very very long loop, especially p or (1-p) is very small (like 0.01 or 0.99). But it is easier to implement.
> 0 votes

---
Tags: probability-theory, randomized-algorithms
---


title: Insertions in Red-Black Trees

text:
# Question
Title: Insertions in Red-Black Trees
I studied methods for inserting new nodes into Red-black trees for the first time this month.

In doing so, I read a lot of pages on the internet and found that ( if I'm not mistaken ) there are many, many, many accepted algorithms for inserting nodes into red-black trees.

Furthermore, I noticed that it is possible to have two insertion algorithms that don't break red-black tree invariants, but also can start with the same initial tree, insert the same node, and end up with different resulting trees.

I think.

For example, take this website's algorithm for insertion: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

And then there's this famous example from 'Purely Functional Data Structures' by Chris Okasaki:

And then there's this algorithm from Ohio State: https://www.pdf-archive.com/2017/03/28/08-red-black-tree/08-red-black-tree.pdf

Is it true that there are many red-black tree insertion algorithms that, given the same domain, will map the elements in that domain differently?

# Answer
> 4 votes
Yes, a given set can be represented by multiple red-black trees, and this works incrementally, at least some of the time. That is, there exists more than one valid red-black tree insertion algorithm, whose outputs are not always equal.

The easiest way of seeing this is to focus on the correspondence between red-black trees and $(2, 4)$-B-trees. A black node with its red children correspond to a B-tree node.

In particular, if you have two sibling B-tree nodes with four elements in total, they can be distributed 1/3 or 2/2. In red-black terms, if two black nodes are cousins, it's possible for each to have one red child, or for one of them to have two red children and the other to have none. More than that, you can shuffle the elements around between the nodes locally to transform one such pattern into the other.

As wikipedia says, "The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time"; the imperfection of balancing gives room for multiple tree representations of the same set.

---
Tags: algorithms, balanced-search-trees
---


# Question
Title: Total depth of external nodes in complete binary tree
> Assume a proper and complete binary tree $T$ with $n\>1$ nodes. Let $E(T)$ represent the sum of the depths of all external nodes in $T$, and $I(T)$ represent the sum of the depths of all internal nodes in $T$. Prove that:
>
> **$E(T) = O(n⋅\log n)$**

To prove this that it is equal to $E(T)$, do I just go plug in numbers till I get the exact $E(T)$ given? I can't figure this out, can someone help?

# Answer
Let $T$ be a complete binary tree of height $h$.

The number of nodes in the last level (external nodes) as a function of the height is $2^h$

The number of nodes in the tree as a function of the height is $2^{h+1}-1$.

Now you just need to compute $E(T)$ and prove that *(a)* holds.
> 1 votes

---
Tags: binary-trees
---


# Question
Title: Adjacency-list to Adjacency matrix in logarithmic space?
**Input :** Adjacency-list representation of Directed acyclic graph (Boolean circuit). see Complexity theory by Arora and bark, page no- 104

**Find :** Adjacency matrix representation of DAG (Boolean circuit).

**My attempt :**

Let us assume that DAG has $n$ vertices.

First of all create a $n \times n $ table for adjacency matrix. As we have given the list representation, just go through the each list and enter 1 in the adjacency matrix $1$ corresponding to each edge. At the end make all untouched entries of matrix 0's.

**My Question :** I want to design an algorithm that uses only $O(\log n)$ space.

# Answer
Any time you have a problem parameterized by a number $n$ and you need an algorithm whose space usage is logarithmic in $n$, you should immediately think "loop counter". You can store numbers in the range $0$$n$ in $\Theta(\log n)$ bits.

So, in this case, you can use an algorithm along the lines of

```
for i = 1 to n
    for j = 1 to n
        if j is in i's adjacency list
            write 1 to the output
        else
            write 0 to the output

```

The loop counters take $\log n$ bits each, and you might need a small amount of extra storage for book-keeping but you only need to store a constant number of data items, and none of those will be anything bigger than a number in the range $0$$n$, so that's still only $O(\log n)$.
> 3 votes

# Answer
The algorithm you suggest uses too much space. You are looking for an algorithm that can output the entire adjacency matrix while using only $O(\log n)$ additional space. Equivalently, you need an algorithm that given an index $i$, determines the $i$th bit of the adjacency matrix (serialized in some fixed way).

> Can you think of a way of doing this using only $O(\log n)$ space?
>
> Do you see why the two problems are equivalent?
> 2 votes

---
Tags: algorithms, complexity-theory, data-structures, circuits
---


title: General Intelligence Utility Function

text:
# Question
Title: General Intelligence Utility Function
I was watching the AI Stop Button Problem from Computerphile, and was very confused on the difference between two approaches.

Background: there is a barebones general intelligence running in the form of some robotic device. The device acts in accordance to optimize some utility function. The GI is asked to make tea, and this is the dilemma of how it will choose to press its stop button rather than make tea if the two are given the same reward, as pressing its stop button is easier and yields the same reward as making tea for the programmer.

One approach to try and get the GI to not care about the stop button is to set the reward function of pressing the button equal to what it's trying to achieve (let's say it gets 100 reward to make tea and 100 reward if the button is pressed). Then, he explains how this will cause the robot to hit its own button immediately, because it's the same reward but easier than making tea (explained 5 minutes in). If we tried making the button something only us humans can hit, then it would try to slap us immediately, threatening us into hitting the button, as slapping us to hit the button would also be easier and give us the same reward as getting the tea (explained 9 minutes in).

Then, at 10:00, it says that another, better approach is to define the utility function is set with an adjustment term to make the value of utility of the button being pressed and not being pressed would be, theoretically, exactly equal, so that it would be indifferent to the button being pressed.

I don't see how this second approach is different than the first approach. If, in the second approach, the utility function is defined so that the button being pressed and not pressed is equal, isn't that the same thing as giving 100 reward to make tea and 100 reward if the button is pressed? Wouldn't this supposedly better solution still cause the robot to either press its own button if possible, or slap you to threaten you to press its button? Because they both yield the same utility, but slapping or hitting its own button is easier than what it wants to achieve in life.

# Answer
The difference he is making is between long-term and short-term goals. Both need to be definable, and there is obviously a mutual dependency between these two sets of goals, so you can think of pressing the red button as something that will also have to be treated within this framework. You can then imagine that if pressing the button has the same utility of your present long-term goal, that would cause the button to be pressed imediately, whereas if it had the same utility of any of your immediate and cheaper short-term goals (because it would be normalized that way), it could ideally go unnoticed, meaning that it would be made uninteresting as an action, but not as a result. He then immediately addresses the need to consider the existence of the button in long-term goal scenarios, so there's no free lunch here.

This is evidently an oversimplification made for didactic purposes. The idea is not to show exactly how difficult is the problem, but that it is more complicated than common sense would conceive.
> 2 votes

---
Tags: artificial-intelligence
---


title: Potential function for stack problem

text:
# Question
Title: Potential function for stack problem
Consider the follow operations on a *stack* of size at most $k$.

*Push* \- insert element in the stack - actual cost 1

*Pop* \- remove top element from the stack - actual cost 1

*Copy* \- copy whole stack (but maintain the number of elements) - actual cost is the number of elements in the stack

Prove using the potential method that each single operation (push, pop or copy) has amortized cost at most 2.

What would be a suitable potential function for this problem?

# Answer
> 1 votes
A reasonable potential function here would be $C\ell$ or $C(k-\ell)$, where $\ell$ is the number of elements on the stack.

However, I don't think that the amortized cost can be bounded. Consider $k$ push operations followed by $M$ copy operations. The total cost is $k(M+1)$. If the amortized cost of push is $a$ and of copy is $b$, then $ka + Mb \geq k(M+1)$. Dividing by $M$ and letting $M\to\infty$, we obtain $b \geq k$.

# Answer
> 0 votes
Let us consider a particular potential function in the context of amortized analysis:

$$ \hat{c\_i} = c\_i + \phi(D\_i) - \phi(D\_{i-1}) $$

Let's assume we have some stack $S$.

So let's look at `push` — this has an actual cost of 1, so it's potential function will look like

$$ \hat{c\_i} = 1 + (|S| + 1) - |S| \rightarrow 1 + 1 \rightarrow 2 $$

Similarly, `pop` has an actual cost of 1, so we get

$$ \hat{c\_i} = 1 + (|S| - 1) - |S| \rightarrow 1 - 1 \rightarrow 0 $$

Finally, `copy` has an actual cost of $|S|$ so we end up with

$$ \hat{c\_i} = |S| + |S| - |S| \rightarrow |S| + 0 \rightarrow |S| $$

> Prove using the potential method that each single operation (push, pop or copy) has amortized cost at most 2.

As you can see, the amortized cost for copying the entire stack will always be $|S|$ since copying does not affect the potential energy of your stack.

However, both `push` and `pop` have an amortized cost of at most 2.

---
Tags: data-structures, amortized-analysis
---


# Question
Title: What can you do with lambda calculus if you aren't allowed parentheses?
Is there a concise/existing way to denote the expressive power of "lambda calc without using parentheses/tree-of-expressions/application-order-restructuring anywhere"?

Can you do without them/reinvent them? Does it break completely (i.e, even with a naive no-more-parentheses, you're using them implicitly, like when naming things)? Does it become completely trivial/boring?

I haven't tried very hard, but I feel like I couldn't express something like

$\lambda x y z . x y (x z)$

without using parentheses somewhere.

# Answer
### Answer 1

The best answer to this question is: This is the **wrong** question to ask! Let me explain.

The fact that we write down expressions (in $\lambda$-calculus or anywhere else) as sequences of symbols is a *convenience* and *tradition* established by humans. From a theoretical point of view the strings of symbols are not the optimal way of representing expressions. Instead, abstract syntax trees are.

Abstract syntax trees do not require any parentheses. Parentheses are there *only* because we use a particular way of writing things. There is nothing deep in having or not having parenthesis. Your question then boils down to the following: "Suppose we use a notation which requires parentheses, but then we remove parenthesis, what happens?" This is not a mathematically interesting question. It *can* be answered, but it's *irrelevant* for $\lambda$-calculus. The answer might be interesting, but it will not reveal anything about parentheses. Instead, it will reveal something about abstract syntax trees of a certain shape.

Were you born in a slightly different universe, where everyone used reverse Polish notation then you would not have known that there is such a thing as parentheses.

Let me put it another way. It is a *convention* that in $\lambda$-calculus we write $a\\,b\\,c$ to mean $(a\\,b)\\,c$. Without such a convention we would always have to write parentheses everywhere, all the time. The first person to establish the convention could have picked the other one, so that $a\\,b\\,c$ would mean $a\\,(b\\,c)$. Then your question would have a different answer because of some person who picked a convention a long time ago.

### Answer 2

It is not entirely clear where you *think* parentheses are needed, but let's suppose that

1. application is left-associative, so that $x y z = (x y) z$, and
2. $\lambda$-abstraction has lower precedence than application, and it binds as much as it can, so that $\lambda x . x y z$ and $(\lambda x . x y) z$ are different expressions.
3. You think that $x \lambda y . y$ is not a valid expression because it should be written as $x (\lambda y . y)$. That is, a $\lambda$-abstraction in an aplication must always be parenthesized.

Under these conditions, we cannot ever write any $\beta$-redeces (because we would have to apply a $\lambda$-abstraction). So any expression must be of the form $\lambda x\_1 . \lambda x\_2 . \ldots \lambda x\_n . M$, possibly with $n = 0$, where $M$ is of the form $y\_1 y\_2 \ldots y\_m$ for some variables $y\_1, \ldots, y\_m$ (which may be equal to the $x\_i$'s).

If anyone can say anything interesting about this fragment of $\lambda$-calculus, I'd be interested to hear.
> 6 votes

---
Tags: lambda-calculus
---


# Question
Title: Confusion about the definition of the average-case running time of algorithms
In this lecture note,

> The *average-case* running time is defined by the *expected value*, over all inputs $X$ of a certain size, of the algorithm's running time for $X$: $$T\_{\text{average-case}}(n) = E\_{|X| = n}\[T(X)\] = \sum\_{|X| = n} T(X) \cdot Pr\[X\].$$

This wiki article (Quicksort) gives an average-case time complexity analysis for Quicksort:

> When the input is a random permutation, the rank of the pivot is uniform random from $0$ to $n − 1$. Then the resulting parts of the partition have sizes $i$ and $n − i − 1$, and $i$ is uniform random from $0$ to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation: $$C(n) = n - 1 + \frac{1}{n} \sum\_{i=0}^{n-1} (C(i)+C(n-i-1)).$$

My confusion is how does the average-case analysis for Quicksort fit the definition above? First, I would expect a term $\frac{1}{n!}$ (which is $Pr\[X\]$) in the recurrence. But, it is not the case. Second, the analysis above is on a random permutation and the averaging is done over all possible splits. How is this related to averaging over all possible inputs? Do I need another definition for average-case running time?

# Answer
> 4 votes
The definition is a special case of a more general notion. Given probability distributions $\mu\_1,\mu\_2,\ldots$ on inputs, the average running time (with respect to the $\mu\_i$) is defined as $$ \newcommand{\Tavg}{T\_{\mathit{avg}}} \newcommand{\EE}{\mathbb{E}} \Tavg(n) = \sideset{\EE}{}{}\_{X \sim \mu\_n} \[T(X)\]. $$ Usually $\mu\_n$ is supported on inputs of "length" $n$, though length is not necessarily measured in bits or in machine words.

When analyzing comparison-based sorting algorithms, usually $\mu\_n$ is chosen as the uniform distribution over all permutations of the array $1,2,\ldots,n$ (or any other array consisting of $n$ distinct comparable elements). The analysis of quicksort uses these distributions.

Now regarding the recursive formula you mention. Given an input array $X$, let $I$ be the rank of the pivot; if $X$ is a random variable, then so is $I$. The formula in Wikipedia is $$ \Tavg(n) = \sum\_{i=0}^{n-1} \Pr\[I=i\] \EE\[T(X)|I=i\] = \sum\_{i=0}^{n-1} \frac{1}{n} \left\[n-1 + \Tavg(i) + \Tavg(n-1-i)\right\]. $$ Rearranging gives you the quoted formula.

# Answer
> 2 votes
Let $U\_n$ be the set of all inputs of size $n$. Suppose $S\_n^i$ are some partition of $U\_n$ (indexed by $i$), such that each member of $S\_n^i$ takes time $T(n, i)$. We can write the expected time formula like $$T\_{average\text{-}case}(n) = \sum\_{X \in U\_n}{T(X) Pr(X)} = \sum\_{S\_n^i} \sum\_{X \in S\_n^i} T(n, i) Pr(X) = \sum\_{S\_n^i} T(n, i) Pr(S\_n^i) $$

In your case, $S\_n^i$ is the set of inputs of length $n$ with the chosen pivot being the $i$th (0-based) largest element, $Pr(S\_n^i) = 1/n$, and $T(n, i) = C(i) + C(n - i - 1)$.

# Answer
> 0 votes
Shorn of all formulae, the difference is this:

The general definition of average running time for an algorithm on inputs of size N is direct: It is the sum of the running times of *each specific input of size N*, weighted by that input's probability. Note that this definition makes *no reference whatsoever* to what the algorithm actually does with each specific input, nor does it propose any relationships between average running times for different input sizes.

The recurrence relation of average running time for Quicksort on inputs of size N is INdirect: It computes the average running time for size N as a function of the *average* running times for sizes *smaller than* N. In effect, the running times of specific inputs of size N are calculated from the running times of *sections of* those inputs of smaller size, base on the partition; then all of those section times are re-grouped by size and weighted sums taken for each grouping. All references to the probabilities of specific inputs are buried behind the averages.

---
Tags: time-complexity, runtime-analysis, probability-theory, quicksort, average-case
---


title: How to reduce 2-coloring to 2-SAT

text:
# Question
Title: How to reduce 2-coloring to 2-SAT
Let $G=(V,E)$ be an undirected graph in which $V = \\{v\_1,v\_2,\dots,v\_n\\}$.

I need to describe a reduction from the 2-coloring problem to the 2-SAT problem (in polynomial time).

I thought of splitting each vertex $v\_i$ into $v\_i^\*$ and $v\_i^{\**}$, one for each color. Then I was thinking about making for each edge $(u,v)\in E$, two correspond literals: $(u^\* \lor v^\*)$ and $(u^{\**} \lor v^{\**})$.

I know I'm on the right track but I can't prove it.

any ideas?

# Answer
If all you require is a polynomial-time reduction, then test in polynomial time if $G$ is $2$-colourable. If it is, map it to the formula $X$; if it isn't, map it to $X\land\lnot X$.
> 2 votes

# Answer
Consider a graph $G=(V,E)$.

Given a node $v\_i \in V$ as you did, you can split into 2 variables $v\_{i,1}$ and $v\_{i,2}$ representing the 2 colors.

Now you just need 3 kind of clauses:

* each node cannot have more than one color
* Each node must have assigned a color
* $\forall$ edge $(u,v) \in E$, $u$ and $v$ cannot have the same color.

Then you just have to write it as a conjunction of clauses, where each clause is a disjunction of 2 literals.

G admits a 2-coloring $\iff$ there exists a truth assignment that satisfy the formula.
> 1 votes

---
Tags: algorithms, graphs, np-complete, reductions
---


# Question
Title: Algorithm to identify if a string of numbers is a lottery sequence
Suppose that a valid lottery ticket consists of a sequence of 7 numbers drawn from the set $\\{1,2,\ldots,59\\}$. Given a string like "$12345678$", I want to efficiently print all the lottery sequences using every digit in the input string.

In the example above, a couple of possible sequences are: ${1,2,3,4,56,7,8}$ or ${1,2,3,45,6,7,8}$ which both satisfy lottery number conditions.

I thought of a combinatorial solution like this:

Let $n$ be the number of characters in the input string. If $n\<7$ or $n\>14$ then there is no solution possible. For valid input strings of length $n$, where $n\in \[7,14\]$, the problem reduces to the following:

In a string of length $n$ there are $n-1$ locations to put a comma. We have to put $6$ commas in $n - 1$ spaces such that no two consecutive spaces are empty (Otherwise, a number will be consist of three digits or be greater than $59$). This simply means arrange six ones like this:

> 111111

and then put $n-7$ $0$'s (representing emptiness) in the 7 slots. So, for example, if the input string is of length $8$ ("$12345678$") then we have to put $8-7 = 1$ zero in $7$ slots. So there are $7$ places where a zero can go and the strings generated are:

> 0111111, 1011111, 1101111, 1110111, 1111011, 1111101, 1111110

which correspond to $\\{12,3,4,5,6,7,8\\}$, $\\{1,23,4,5,6,7,8\\}$ etc.

So the problem reduces to computing $\binom{7}{k}$ and for each arrangement like above, put the corresponding commas in the appropriate place in the input string. So $0111111$ maps to $12,3,4,5,6,7,8$ (the space between 1 and 2 is left empty while the commans occupy the remaining 6 slots).

Is this algorithm a bad choice or can I do better?

# Answer
I'm not sure if I understood your solution or not. But it seems that 78 also is included in the last sequence.

Here is my answer: For any valid sequence $w$ ($w$ is valid iff $7\le n\le14$ where $n$ is the size of $w$) there should be $n-7$ pairs and $14-n$ single numbers ($14-n+n-7=7)$. We run a recursive function:

1. Setup the memory: $A$ count of pairs and $B$ count of single numbers in the sequence
2. If $w\[0\]$ is equal or less than 5, then there are two possibilities:

1. It can be a single member if $B\<14-n$
    2. It can be combined with the next number if $A\<n-7$

If neither of these cases is valid, this sequence is not valid
3. If $w\[0\]$ is greater than 5, then it can not be combined with the next number. If $A\ge n-7$ then this sequence is not valid.

Then run the same algorithm for the sequence following $w\[0\]$ (or $w\[1\]$ for case 1.1).

For example $w=12345678$

1. $\\{1\\}$ and $\\{12\\}$
2. $\\{1,2\\}$, $\\{1,23\\}$, $\\{12,3\\}$
3. $\\{1,2,3\\}$, $\\{1,2,34\\}$,$\\{1,23,4\\}$, $\\{12,3,4\\}$
4. $\\{1,2,3,4\\}$, $\\{1,2,3,45\\}$, $\\{1,2,34,5\\}$, $\\{1,23,4,5\\}$, $\\{12,3,4,5\\}$
5. $\\{1,2,3,4,5\\}$,$\\{1,2,3,4,56\\}$,$\\{1,2,3,45,6\\}$,$\\{1,2,34,5,6\\}$,$\\{1,23,4,5,6\\}$,$\\{12,3,4,5,6\\}$
6. $\\{1,2,3,4,5,6\\}$,$\\{1,2,3,4,5,67\\}$,$\\{1,2,3,4,56,7\\}$,$\\{1,2,3,45,6,7\\}$,$\\{1,2,34,5,6,7\\}$,$\\{1,23,4,5,6,7\\}$,$\\{12,3,4,5,6,7\\}$
7. $\\{1,2,3,4,5,6,7\\}$,$\\{1,2,3,4,5,67,8\\}$,$\\{1,2,3,4,56,7,8\\}$,$\\{1,2,3,45,6,7,8\\}$,$\\{1,2,34,5,6,7,8\\}$,$\\{1,23,4,5,6,7,8\\}$,$\\{12,3,4,5,6,7,8\\}$

all the sequences ended with $8$ are valid.
> 1 votes

---
Tags: combinatorics, strings, subsequences
---


# Question
Title: Why is this greedy algorithm claim true?
I'm taking a course about submodular functions and their applications towards influence maximization in a network. We've been discussing a greedy algorithm for selecting $k$ initial nodes to maximize influence and I'm confused about a statement made in class.

Let $O = \\{o\_1, . . . , o\_l\\}$, and $o\_{\max}$ be the element with the highest marginal contribution in $O$ at stage $i + 1$. That is: $o\_{\max} = \arg\max\_{o\in O} f\_{S\_i}(o)$. At stage $i + 1$ the algorithm selects element $a\_i+1$ and we are guaranteed that its marginal contribution is the highest. In particular, **its marginal contribution is also higher than the marginal contribution of the element in $O$** that has the highest marginal contribution: $$f\_{S\_i}(a\_i+1) \geq f\_{S\_i}(o\_{\max})$$

$f$ gives the expected number of nodes influenced and $f\_S$ is the marginal contribution of adding set $a$ to set $S$ ie: $f\_S(a) = f(S\cup a) - f(S)$ $$f\_{S}(a) \geq f\_S(o^\*)\\,.$$

This doesn't make sense to me. Consider the circle cover problem:

At timestep $t = 1$, the greedy algorithm selects $A$ and optimal selects $B$. (Greedy is on the left and optimal is on the right).

$$f\_S(A) \geq f\_S(B)\\,,$$ but at $t=2$ the greedy selects $B$ and optimal selects $C$. $$f\_S(B) \ngeqslant f\_S(C)\\,,$$ because the marginal contribution of the greedy algorithm is only 4 when the optimal is 5.

**Why did we say that selecting elements greedily has better marginal contributions than optimal?** I'd appreciate a theoretical and possible concrete example if possible!

# Answer
The claim is *not* that

$$f\_S(B) \ge f\_S(C).$$

Rather, the claim is that

$$f\_{S\_1}(B) \ge f\_{S\_1}(C).$$

Do you see the difference? Here $S\_i$ is the set of elements chosen (by the greedy algorithm) in the first $i$ iterations, so $S\_i=\\{A\\}$. Thus, the claim is that

$$f\_{\\{A\\}}(B) \ge f\_{\\{A\\}}(C),$$

i.e.,

$$f(\\{A\\} \cup \\{B\\}) \ge f(\\{A\\} \cup \\{C\\}).$$

The latter claim is indeed true, as both the left-hand side and the right-hand side are 9 (i.e., $f(\\{A,B\\})=f(\\{A,C\\})=9$), since they cover 9 of the "blue dots".
> 1 votes

---
Tags: optimization, approximation, greedy-algorithms
---


title: Variant of offline Turing machine

text:
# Question
Title: Variant of offline Turing machine
Let $M$ be a variant of Turing machine with no working tape but with several heads on input word. Prove that these machines accept exactly the languages in $L$.

Please hint me how to start.

# Answer
> 1 votes
Let $S$ denote the languages accepted by such machines. The question wants you to prove $S=L$.

When you have a complicated-looking task, it often helps to break it down into pieces. So, a first helpful hint on how to break it into pieces: try to prove $S \subseteq L$. Separately, try to prove $L \subseteq S$. (If you still can't solve it, then you're able to ask a more specific question about one or the other of those.)

---
Tags: complexity-theory, computability, turing-machines
---


# Question
Title: Are there any efficient algorithems to find packets similarities in a list?
I would like to make a program which finds similar packets (there might be more then one class of similarity) in packet list (which is updated all the time). Are there any efficient algorithems to find these similarities?

By similarities I mean that they have the same size, type and payload.

I thought about using tree(with conditions on the branches just like decision tree) or vector support machine with k classes (k\>2), but it means that it should have a lot of classes/nodes. Say there are 10 different packets and 2 kinds of similar packets (3 packets in each group). Then there will be 10 classes with single packet, 2 classes with 3 packets - So its size depends on the amount of packets which can be really big.

thank you

# Answer
There are many possible approaches for measuring document similarity:

I suggest you think more about what metric makes sense for you, and review the literature on information retrieval and natural language processing to see what metrics have been used in other contexts.
> 2 votes

---
Tags: machine-learning, trees, real-time
---


# Question
Title: Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$
The following problem is from CLRS (31.1-13, Page 933, 3rd edition):

> Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most $\beta$ takes time $M(\beta)$, then we can convert binary to decimal in time $Θ(M(\beta)\log \beta)$. (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)

By a simple divide and conquer (by dividing $\beta$-bit integer into two $\beta/2$-bit integers), I obtain the recurrence $T(\beta) = 2T(\beta/2) + M(\beta)$. However, how to argue that it is $O(M(\beta) \log \beta)$?

---

*My attempt:* I think the result relies on $M(\beta)$. If $M(\beta) = \Theta(\beta)$, then $T(\beta) = \Theta(M(\beta)\log \beta)$. But, if, for example, $M(\beta) = o(\beta)$ or $M(\beta) = \omega(\beta^2)$, you may not obtain $T(\beta) = \Theta(M(\beta)\log \beta)$.

---

According to the hint, it seems that we should use different recursions to obtain $O(M(\beta)\log \beta)$ and $\Omega(M(\beta) \log \beta)$, respectively. But how?

# Answer
The exercise seems fine. You can take care of those issues with a little more work, by reasoning about what the running time of a multiplication algorithm must look like.

One can show that, for any correct multiplication algorithm, we have $M(\beta)=\Omega(\beta)$. Indeed, any correct algorithm has to read all bits of the input, so the lower bound follows. Thus, the first case you were worried about, where $M(\beta)=o(\beta)$, can't happen.

We can consider two remaining cases:

* If $M(\beta)= \Theta(\beta \cdot \text{poly}(\log(\beta))$, then by the Master theorem, we have $T(\beta) = \Theta(M(\beta) \log(\beta))$. This matches the bound proposes in the exercise statement.
* If $M(\beta) = \Omega(\beta^{1+\epsilon})$ for some $\epsilon\>0$, then by the Master theorem $T(\beta)=\Theta(M(\beta))$. Of course, if you can solve a problem in time $T(\beta)$, you can also solve it in time $T'(\beta)$, if $T'(\beta) \ge T(\beta)$ by padding (just add some extra no-ops). Consequently, in this case there also exists a binary-to-decimal conversion algorithm whose running time is $\Theta(M(\beta) \log(\beta))$.

In either case, we achieve the claimed result.

OK, technically I realize that these don't cover all remaining cases. But I believe it is still true that once we know that $M(\beta)=\Omega(\beta)$, then it follows that the solution to the recurrence relation satisfies $T(\beta) = O(M(\beta) \log(\beta)$, so there exists a binary-to-decimal conversion algorithm whose running time is $\Theta(M(\beta) \log(\beta))$.
> 1 votes

# Answer
If we take $M(\beta) = \log \beta$ we can disprove the assignment's claim (assuming base 2 $\log$).

\begin{align\*} T(\beta) &= 2T(\beta/2) + M(\beta)&\text{given}\\ T(\beta) &= 2T(\beta/2) + \log \beta&\text{given (1)}\\ T(\beta) &= 2\beta - \log (\beta) - 2&\text{inductive hypothesis (2)}\\ T(\beta) &= 2(2\beta/2 - \log (\beta/2) - 2) + \log \beta&\text{substitute (2) into (1)}\\ T(\beta) &= 2\beta - 2(\log (\beta) - 1) - 4 + \log \beta&\text{algebra}\\ T(\beta) &= 2\beta - \log (\beta) -2&\text{QED}\\ \end{align\*}

So we've proven that if $M(\beta) = \log \beta$ then $T(\beta) = O(\beta)$. However the assignment claims $O(T(\beta)) = M(\beta)\log \beta = \log^2 \beta$. This cannot be true.

---

If we read between the lines it seems implied that $M = Ω(\beta)$.
> 1 votes

---
Tags: algorithm-analysis, asymptotics, recurrence-relation, recursion, divide-and-conquer
---


title: Euclid's Algorithm Time Complexity

text:
# Question
Title: Euclid's Algorithm Time Complexity
I have a question about the Euclid's Algorithm for finding greatest common divisors.

gcd(p,q) where p \> q and q is a n-bit integer.

I'm trying to follow a time complexity analysis on the algorithm (input is n-bits as above)

```
gcd(p,q)
    if (p == q)
       return q
    if (p < q)
       gcd(q,p)
    while (q != 0)
       temp = p % q
       p = q
       q = temp
    return p

```

I already understand that the sum of the two numbers, `u + v` where `u` and `v` stand for initial values of `p` and `q` , reduces by a factor of at least `1/2`.

Now let `m` be the number of iterations for this algorithm. We want to find the smallest integer `m` such that `(1/2)^m(u + v) <= 1`

Here is my question. I get that sum of the two numbers at each iteration is upper-bounded by `(1/2)^m(p + q)`. But I don't really see why the max `m` is reached when this quantity is `<= 1`.

The answer is O(n) for n-bits `q`, but this is where I'm getting stuck.

Please help!!

# Answer
Here is the idea of the proof. Throughout, we assume that $p \geq q$.

Let $p^{(t)},q^{(t)}$ be the values of $p,q$ after $t$ iterations, so that $p^{(0)}=p$ and $q^{(0)}=q$.

Let $F\_m$ be the $m$th Fibonacci number, which satisfies $F\_m = \Theta(\varphi^m)$, where $\varphi = \frac{1+\sqrt{5}}{2} \> 1$. Suppose that $p \leq F\_m$. If $q \leq F\_{m-1}$ then $p^{(1)} = q \leq F\_{m-1}$. If $q \geq F\_{m-1}$ then $q^{(1)} = p \bmod q \leq F\_{m-2}$, and so $p^{(2)} = q^{(1)} \leq F\_{m-2}$.

This argument shows that if $p \leq F\_m$ then after at most (roughly) $m$ steps, the algorithm will terminate (since we cannot have $p \leq F\_0 = 0$). Since $F\_m$ grows exponentially, it's not hard to check that $p \leq F\_{O(n)}$, where $n$ is now the length of $p$ in bits. Therefore the algorithm terminates in $O(n)$ steps.

If you want a bound depending on $\min(p,q)$ rather than on $\max(p,q)$, simply notice that $p^{(1)} = q$, and run the above analysis on $p^{(1)}$.
> 3 votes

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


# Question
Title: Cost of find operation on a tree data-structure
I implement my data sets with a tree data-structure.

The tree data-structure has a method named `MakeSet` which creates a set with one node. The tree data-structure has also a method named `Merge(i,j)` which merges trees of set `i` and set `j` in this way: the set with smaller depth becomes a child of the root of the set with larger depth.

I do `MakeSet` $n$ times and I do `MergeSet` $n-1$ times with a random order. Then I do a `Find` operation. What is the cost of `Find` in a worst case scenario?

---

I feel like the answer might be $O(n\log{n})$, because after doing $n$ `MakeSet` and $n-1$ `MergeSet`, it might be safe to say that we have a tree with $n$ nodes and height of $\log{n}$. I'm not sure.

# Answer
Since my two comments already form the solution, I can also write the answer in total.

If you have a datastructure consisting of a bunch of trees, then the worst-case cost of a Find-Operation is the maximal height of a tree in your data structure. Your trees are built from $n$ trees consisting of a single node each by $n-1$ Merge-Operations. A Merge-Operation merges two trees such that the tree of smaller height is added to the root of the tree of larger height.

First observation: If you merge two trees of different height, then the resulting tree has the same height as the initial tree of larger height.

Second observation: If you merge two trees of the same height $h$, then the resultung tree has height $h+1$.

Conclusion: To increase the maximum height from $h$ to $h+1$, you first need two trees of height $h$.
So the worst-case scenario in your setting is the following: You initially merge two trees consisting of a single node each. This gives a tree of height $1$. You now need to merge two other trees consisting of a single node each such that a second tree of height $1$ occurs. If you now merge this trees of height $1$, then you have a resulting tree of height $2$. Now if you want to increase the height again, you need again $4$ of the initial trees to construct an other tree of height $2$.

The iteration of that argument shows that you can only increase the height $\log n$ times, where $n$ is the number of initial trees.
> 1 votes

---
Tags: algorithms, graphs, data-structures, trees
---


# Question
Title: A real life system that faces and solves the dining philosophers problem
I'm looking for an application of the dining philosophers problem. Is there some real life system that faces the concurrency problem of "the dining philosophers problem" and implements a solution? I've been searching for over an hour.

It would be even better if the implemented solution is Tanenbaum's solution described here.

# Answer
The dining philosopher's problem is a worst case scenario used to illustrate issues in algorithms. It's a test case. You probably won't find a static one-to-one mapping between it and a real world case.

However, similar situations can occur dynamically. If at any point the graph of actors waiting for resources forms a cycle, you are stuck in a deadlock. Most of the time this happens with n = 2 actors, but sometimes you can get more complicated deadlocks.
> 3 votes

---
Tags: operating-systems, concurrency, deadlocks
---


# Question
Title: Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges
I know that this doesn't work because shortest path with a lot of edges may have bigger weight than a longer path with less edges. But what if, you keep track of the edges that our current weight path on each node and when we compare we subtract the number of edges on this path * the constant so that we get the original weight. I understand there is also the negative cycles problem, but is there an efficient algorithm that tell if a graph contains a negative cycle ?

# Answer
It's called Johnson's algorithm.

Instead of trying to keep track of the number of edges, it searches for a function $\delta:V\to \mathbb R$ so that for all edge $(v,v')$, $w(v,v')+\delta(v)-\delta(v')\ge 0$ and set that as the new weight $w'(e,e')$ of the edge $(e,e')$.

Then, for any path $p=v\_1\cdot \dots\cdot v\_n$ the $\delta$ values of all intermediate vertices cancel so that $w'(p)=w(p)+\delta(v\_1)-\delta(v\_n)$. And the shortest paths for $w$ and $w'$ therefore coincide.

Then remains the problem of finding such a $\delta$. The magic is that you can just add a new vertex $v\_\*$ and edges $(v\_\*,v)$ of weight $0$ for every vertex $v$, and then set $\delta (v)$ to be the weight of a shortest path $p\_v$ from $v\_\*$ to $v$. Then the positiveness condition simply becomes $w(v,v')+w(p\_v)-w(p\_{v'})\ge 0$ which can be rewritten as $w(p\_v)+w(v,v')\ge w(p\_{v'})$ which is true because $p\_v\cdot v'$ is a path from $v\_\*$ to $v'$ and $p\_{v'}$ is a path from $v\_\*$ to $v'$ of minimal weight.
> 2 votes

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