# Question
Title: How can I minimize floating point error when multiplying normal distribution PDFs?
If you multiply two normal distribution PDFs with means $\mu\_1$ and $\mu\_2$ and variances $v\_1$ and $v\_2$, then according to this page, the new mean is

$$\mu = \frac{\mu\_1 v\_2 + \mu\_2 v\_1}{v\_1 + v\_2}$$

and the new variance is

$$v = \frac{v\_1 v\_2}{v\_1 + v\_2}.$$

However, if I use those expressions directly to combine several distributions sequentially, the floating point errors quickly pile up. Is there an algorithm for doing this stably?

# Answer
> 1 votes
While there is an entire subject that studies how to prevent or reduce floating point errors from piling up, it happens we have a shortcut here.

Let $\mathcal N(u, \sigma)=\frac{1}{\sqrt{2\pi\sigma^2} } e^{ -\frac{(x-\mu)^2}{2\sigma^2} }$ , the normal distribution with mean $u$ and standard derivation $\sigma$. Suppose we are given $n$ Gaussian normal distribution $\mathcal N\_i(u\_i, \sigma\_i)$ . What is the product of $n$ of them? It turns out,

$$\prod\_{i=1}^n \mathcal N(\mu\_i,\sigma\_i)= s\mathcal N (\mu,\sigma)$$ where $$ \frac1{\sigma^{2}} = \sum\_{i=1}^n \frac1{\sigma\_i^{2}}\\,, \quad \frac\mu{\sigma^2} = \sum\_{i=1}^n \frac{\mu\_i}{\sigma\_i^{2}} $$ and $$ s = (2\pi)^{\frac{1-n}2} \frac{\sigma}{\prod\_{i=1}^n \sigma\_i}\exp\left(\frac12 \left(\frac{\mu^2}{\sigma^2} - \sum\_{i=1}^n \frac{\mu\_i^2}{\sigma\_i^2}\right) \right) $$

If you use the above formula to compute, floating point errors should not be a concern any more.

Please note the reference you used is misleading in the sense the product function is not a probability distribution function.

---

Exercise. Prove the above formula for the product of $n$ normal distribution.

---
Tags: probability-theory, numerical-algorithms
---


# Question
Title: Decoding cyclic code, assuming we have no errors
Assuming the coded data is errorless and given generator polynomial coefficients. By what algorithm can I decode the data coded by matrix constructed by given generator polynomial?

# Answer
Let us start with generator matrix $G$, a matrix of $k$ rows and $n$ columns where $n\ge k$. Given any input row vector $s$ of $k$ characters, we can generate the codeword for $s$, a row vector of $n$ entries by $$w=sG$$ If given $s$, how can we get back $w$? Suppose we can find a matrix $G'$ of $n$ rows and $k$ columns such that $$GG'=I\_k$$ where $I\_k$ is the identity matrix of $k$, we will have $$s=sI\_k=s(GG')=(sG)G'=wG'$$

So the question becomes how to find such matrix $G'$ from $G$. You should be able to find in your course material the procedure or technique to accomplish that. Note that $G'$ is not a square matrix. In general $G'$ is not unique, either.

Now suppose you are given a generator polynomial instead. You can form the generator matrix from the generator polynomial and proceed as above. There might be a shortcut procedure for generator polynomial because of its special form.
> 1 votes

---
Tags: error-correcting-codes
---


# Question
Title: Two Turing machines $M_1$ and $M_2$ with $L(M_1) \subseteq L(M_2)$
Suppose $M\_1$ and $M\_2$ are two Turing machines such that $L(M\_1)\subseteq L(M\_2)$. Which of the following is true?

* (A) On every input on which $M\_1$ does not halt, M2 does not halt
* (B) On every input on which $M\_1$ halts, $M\_2$ halts too
* (C) On every input which $M\_1$ accepts, $M\_2$ halts.
* (D)On every input which $M\_2$ accepts, $M\_1$ halts.

I am confused between B and C. This was an online practice test question.

For (B) my claim is that when $M\_1$ is able to decide the language (i.e., $M\_1$ halts on every input), then, since it is given $L(M\_1) \subseteq L(M\_2)$, $M\_2$ should also halt and be able to decide on every input.

However, option (C) also looks convincing. If for every input $M\_1$ says "yes" in the language, then $M\_2$ should also be able to decide for that input.

Please let me know how to approach this correctly.

EDIT: After reading the discussion, am I correctly interpreting the problem If I imagine the figure below

SO, (B) must be the wrong choice according to this right?

# Answer
> 1 votes
"Halt" is not synonymous with "accept", although the latter implies the former. A TM can halt and *reject*. On the other hand, $L(M)$ stands for the set of words accepted by $M$, *not* the words it halts for.

Hence, alternative (C) is correct. (B) is incorrect because $M\_1$ could halt on and reject a word which is accepted by $M\_2$ (i.e., a word in $L(M\_2) \setminus L(M\_1)$), or for which $M\_2$ does not halt, even.

Note the question makes little sense, if any, if we assume $M\_1$ and $M\_2$ to be *deciders* since, then, *all* alternatives are correct, (A) because the premise is always false (since $M\_1$ always halts) and the others because the respective implications are always true.

---
Tags: turing-machines
---


# Question
Title: What will be big O complexity for this loop?
I am not able to understand time complexity of this for loop. While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity?

```
public void function(n) {
                    for(int i = 1; i< n; i++) {
                        for(int j =     1; j <= n;  j += i) {
                                System.out.println("*")
                        }
                    }
                }

```

# Answer
> 0 votes
The inner loopnever stopped for $n \geq 1$ as for the first time `i = 0` and `j += i` never increased the value of `j`. If we suppose `i` will be started from `1`, for `i = 1` the inner loop will be iterated $n$ times. for `i = 2` as value of `j` is increased by step size `2`, the number of iterations of the inner loop is $\frac{n}{2}$. Hence, the computation cost of the program is $\sum\_{i = 1}^{n-1}\frac{n}{i} = n \sum\_{i = 1}^{n-1}\frac{1}{i} = \Theta(n\log(n))$.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Boolean Functions Implemented by Multiplexers
Electrical engineers often use multiplexers to implement Boolean functions. What is the correct technical term for this model of computation? Is it Decision Tree model or is there another name?

# Answer
> 0 votes
I think there is no specific name for it, just several methods, c.p. this website Note that it's quite simple to e.g. implement all 2-input logic functions with a 4 input 1 output mux, by connecting the inputs to the address/select lines, and applying the constants 0/1 to the data inputs. (This actually transforms the MUX into a Lookup table (LUT))

---
Tags: reference-request
---


title: K Perfect Subgraph Algorithm

text:
# Question
Title: K Perfect Subgraph Algorithm
I have a problem that goes as follows:

**Problem.** Suppose we have undirected graph $G$. We denote a $k$-perfect graph as a graph such that $\forall v \in G, degree(v) = k$. Present an algorithm that constructs a subgraph $H$ such that $H$ is $k$-perfect, for $k$ maximized. Do this in $\theta(|V| + |E|)$ time.

I was thinking that perhaps we could borrow techniques from a BFS based topological sort, to work on the "fringe" vertices and continuously cut inwards. Formally, we would identify vertices with small degree and cut them out, but I don't know how to make sure that this doesn't accidentally take out a vertex that would create a $k$ perfect graph of larger $k$, and how to do this without the check for if we're done costing $\theta(V)$.

Have you got any ideas?

Note that we define a subgraph here as: $H = (V', E')$ is a subgraph of $G = (V,E)$ if $V' \subseteq V$ and $E' \subseteq E$. Basically we are allowed to remove both edges and vertices.

# Answer
This problem is NP-hard, meaning it's very unlikely that any algorithm exists that can solve every instance in polynomial (let alone linear!) time. I'll show this by reducing the NP-hard problem Clique to this problem. In Clique, we are given an undirected graph $F$ and a number $K$, and the task is to determine whether or not $F$ contains a clique (complete subgraph) with at least $K$ vertices. The strategy will be to add *universal vertices* to $F$ -- that is, new vertices that are connected to all existing vertices -- and show that doing so grows the size of cliques in $F$, but does *not* grow the size of any other regular subgraphs in $F$.

Let there be $n$ vertices in $F$. We will construct an instance $(G, k)$ of your problem from the given instance $(F, K)$ of the Clique problem:

* $G$ is formed by adding $n+1$ new vertices to $F$ that are adjacent to each other and to every vertex in $F$.
* $k = K + n$.

First we show that if there is a clique in $F$ of size at least $K$, then there is a regular subgraph with degree at least $K+n$ in $G$. Clearly a clique of $K+n+1$ vertices can be formed by including the $K$ clique vertices in $F$ and all $n+1$ new vertices. A clique containing $i$ vertices is regular with degree $i-1$, so this clique is regular of degree at least $K+n$. Thus a YES answer to the given Clique problem implies a YES answer to the constructed instance of your problem.

Now we show that if there is a regular subgraph $H$ with degree at least $K+n$ in $G$, then there is a clique of size at least $K$ in $F$. First observe that this $H$ must include at least one of the $n+1$ newly added universal vertices, since the largest degree obtainable using just the original $n$ vertices of $F$ is $n-1 \< n+K$. The following lemma is key:

> **Lemma:** If a regular graph $I$ contains a universal vertex, then it must be a clique.
>
> **Proof:** Let $c \ge 1$ be the number of universal vertices in $I$, and let $a$ be the number of other vertices. Since $I$ is regular, it must be that every non-universal vertex has the same degree $c+d$ for some $d$ -- that is, removing the $c$ universal vertices from $I$ must leave a $d$-regular subgraph, which I'll call $I'$. Again, since $I$ is regular, we must have that the degree $c-1+a$ of each universal vertex in $I$ is equal to the degree $c+d$ of the other vertices. But this implies $a-1=d$, i.e., $I'$ is a clique of $a$ vertices, and thus $I$ is a clique of $c+a$ vertices.

Since $H$ contains at least one universal vertex, by the above lemma, it must be a clique of size at least $K+n+1$. Since we only added $n+1$ universal vertices to $G$, at least $K$ of the vertices in $H$ must have come from the original graph $F$, where they also form a clique since every induced subgraph of a clique is a clique. Thus a YES answer to the constructed instance of your problem implies a YES answer to the given Clique problem.

Since a YES answer to one problem instance implies a YES answer to the other, it follows that a NO answer to one problem instance also implies a NO answer to the other. Thus any algorithm that could solve your problem could also solve Clique. Since constructing the instance of your problem requires only polynomial time, a polynomial-time algorithm that could solve your problem could also solve Clique in polynomial time.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Interview Question: Insert switch to maximize time lightbulb spends on
Problem statement:

> You have a lightbulb for an interval of $N$ seconds, where $N$ is given. At time 0, the lightbulb switches on, and at time $N$, it switches off, regardless of any switches. From time 1 to time $N-1$ you have a maximum of $N-2$ switches in the form of an array called switches, which turn the lightbulb to the opposite of what it currently is i.e. if it's on it'll turn off and vice versa. For example, suppose $N = 8$ and switches $\[1,2\]$. The lightbulb will switch on at time 0, a switch at time 1 will turn it off, a switch at time 2 will turn it on, and it'll remain on until time 8, when it turns off. Hence, the time it remains on is equal to $1-0 + 8-2 = 7$.
>
> Now suppose you have to insert a switch in this interval, where there is not already a switch present. What is the maximum time the lightbulb remains on once you insert the switch. For example, in the above case, the solution would be 6 since inserting a switch at time 7 keeps the time the lightbulb spends on maximum. Since $1-0 + 7-2 = 6$, the answer is 6.

I solved this using a brute force solution, using the reasoning that if you insert a switch at time $k$, the states of the lightbulb before this wouldn't be affected, and the states of the lightbulb from time $k$ to time $N$ will be reversed, and hence you can find the time it spends on after time $k$ by $(N - k) - t$, where $t$ is the time it would spend on from time $k$ to $N$ without the inserted switch. Hence, I can calculate the time the lightbulb would spend on for each time position of the inserted switch and maximize it. However, since calculating the time the lightbulb spends on is $O(n)$ operations and I go through all possible positions, my solution is $O(n^2)$ and this caused my code to time out for some test cases.

Can someone propose a better solution?

# Answer
Your solution is already O(N). You just don't have to recompute the complete light time for all position.

Compute once the full light time L0 before insertion.

Then as you are looping on positions, you keep an accumulator B of the light time before the tested position. And you know you have L0-B after...

So at position t, you have: L(t) = B + (N-t) - (L0-B)

NB: you even can skip L0 pre-computation as your accumulator B will be L0 at end of the loop and L(t)+L0 has the same maximum than L(t).
> 0 votes

# Answer
Let's call the array of switches $a$ and let's add two elements to the array at the beginning we add 0 and at the end we add 100.
We now want to insert an element between two consecutive elements to maximise the length the bulb is turned on.
Let's make the following observations:

**Note1** If a\[i+1\] = a\[i\] + 1, two consecutive elements have consecutive values. In this case we can't add anything between them.

**Note2** The optimal value we add between $a\[i\]$ and $a\[i + 1\]$ for some $i$ is either equal to $a\[i\] + 1$ or to $a\[i+1\] - 1$.
**Proof.** Assuming the claim is not true, there is an optimal value strictly between $a\[i\]+1$ and $a\[i+1\]-1$. However, if the bulb is turned off in this interval we can push it back to $a\[i\]+1$ increasing the length of the turned on pulp in this interval without effecting the others. On the other hand if the bulb is turned on, we push it right to $a\[i+1\]-1$ increasing the length of turned on pulp in this interval.

So now we can loop over the array, and for each $i$, if $a\[i\] \neq a\[i+1\]-1$, we try to add the value $a\[i\]+1$ and the value $a\[i+1\]-1$, these are 2\*(n-1) tries in total where n is the number of elements in the array (including 0 and n), which is linear in the number of the switches. We only have to show that we can do each step in constant time.
So let's say we already have the array, and we want to check the total value after adding a switch at position $k$. Let's pre-process the array and calculate and building the following 2 arrays in linear time:
1. The length of light-on since the begin.
2. The length of light-off from now till the end.
We can do that in two loops over the array using prefix-/suffix-sums.
Now when adding a switch between $a\[i\]$ and $a\[i+1\]$ with time stamp $k \in (a\[i\], a\[i+1\])$, the total value of on-light will be total value of on light from the begin to $i$ \+ the total off-light from $a\[i+1\]$ till the end + the total on-light in the interval between $a\[i\]$ and a\[i+1\] after adding $k$ (Which is either $k - a\[i\]$ or $a\[i+1\] - k$ depending on the original status of the interval).
**Summary,** In total we preprocess the array in $O(n)$, we do linear number of checks $O(n)$ and each in constant time in total we have $O(n) + O(n) * O(1) = O(n)$
> 0 votes

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


# Question
Title: Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable
Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$.

This problem is undecidable. To prove this, assume the contrary. We define a term $s$ as follows:

$$s x \equiv \lambda n.j. j y$$

if $x$ is an encoding of the configuration of a Turing machine and $y$ is the encoding of the configuration the Turing machine transitions into in one step and

$$s x \equiv \lambda n.j. n$$

if $x$ is an encoding of the configuration of a Turing machine that has halted.

Now define the term $t\_M$ as follows:

$$t\_M := Y (\lambda f.x. s x (\lambda a.b. b) f) i\_M$$

where $i\_M$ is the encoding of the initial configuration of $M$, and $Y$ is the fixed point combinator.

If $M$ halts, $t\_mv \equiv (\lambda b. b)$. Otherwise, $t\_mv$ does not have a normal form, and every term equivalent to it has $v$ in it. Therefore, $\phi(t, v)$ iff $M$ halts. This algorithm can be used to solve the halting problem, which is a contradiction.

On the other hand, it is semidecidable. For any $t$ and $v$, simply enumerate the $t'$ such that $t' \equiv t$. If a $t'$ is enumerated such that $v \notin FV(t')$, output yes and halt. This algorithm outputs yes iff $\phi(t, v)$.

That said, this algorithm is not very efficient, since you have to use an enumeration that enumerates all $t'$ such that $t' \equiv t$. **Is there an efficient algorithm to semidecide whether $\phi(t,v)$ is true?**

EDIT: We'll say an algorithm for determining $\phi(t,v)$ is efficient if, when $\phi(t,v)$ is true, it halts in an amount of time that is a polynomial of the minimum number of reduction and conversion steps required to eliminate $v$ from $t$.

---

An approach one might consider is to normalize $t$, and then check if $v$ is free in the result. Although this would be efficient, it would not be correct. For example, this algorithm would not halt on the input $(\Omega ((\lambda a.b. a) \Omega v), v)$ (where $\Omega := (\lambda x. x x)(\lambda x. x x)$), but $\phi(\Omega ((\lambda a.b. a) \Omega v), v)$ is true.

Another approach would be to use some reduction strategy, and then to check after each step if $v$ is free in the term produced by that step. Although I think this is a good direction to take, it should be noted that neither normal order reduction nor applicative order reduction would work. To see this, consider the input $(t\_M(t\_Nv),v)$. If $M$ diverges but $N$ halts, $\phi(t\_M(t\_Nv),v)$ is true, but normal order reduction will never eliminate $v$. Likewise, if $M$ halts but $N$ diverges, $\phi(t\_M(t\_Nv),v)$ is again true, but applicative order will never eliminate $v$.

The input $(t\_M(t\_Nv),v)$ is rather tricky in general. To solve this input, an algorithm would probably need to attempt to normalize $t\_M$ and $t\_N$ in parallel, outputting yes if either normalizes. Attempting to normalize $t\_M$ first or normalize $t\_N$ first will not work.

On the other hand, by the Church-Rosser theorem, we only need reductions, no expansions. We never need to "undo" a reduction step to eliminate a variable. That is because if $t' \equiv t \land v \notin FV(t')$, there is some term that both $t$ and $t'$ reduce to. It will not contain $v$, since $t'$ does not, and reductions never introduce free variables. Since $t$ also reduces to this term, $t$ can be reduced to a term without $v$.

Alpha conversion does not make a difference. It appears that eta conversion is also irrelevant.

# Answer
You can't semi-decide a non decidable problem in an efficient way.

Suppose that you have an algorithm $A$ which semidecides such a problem in, say, $T(n)$. I.e. every word in the problem is accepted within $T(n)$ steps. Assume that $T(n)$ is bounded from above by any computable total function $g(n)$ (say $2^{2^n}$, which allows $A$ to range over any efficient algorithm).

Then, the problem is decidable: run $A$ for at most $g(n)$ steps, and accept if $A$ accepts, otherwise reject.

Contradiction. QED

Asymptotically, a semidecider of a non recursive problem can never be efficient. (Unless we choose another definition of "efficient" than "low worst-case complexity", I guess)
> 2 votes

---
Tags: reductions, lambda-calculus, decision-problem, efficiency, semi-decidability
---


# Question
Title: Without using the Time Hierarchy Theorem, is there any other way to prove P /= EXP
I haven't found any way to show this was the case (that P/=EXP, without using the Time Hierarchy Theorem) If you can find a way to show this, can you give a short explanation of this,and also if possible link a paper supporting your conclusion. Thank you so much

# Answer
> 1 votes
There is a way, actually! Kind of.

Consider two cases:

1. $P \not= NP$. This case is easy: then $P \not= EXP$, because $NP \subset EXP$.
2. $P = NP$. It is known that $P = NP$ implies that there is a language from $EXP$ that has circuit complexity of at least $\frac{2^n}{10n}$, so $EXP$ is not a subset of $P/\mathrm{poly}$ in this case, let alone $P$. I will recall the proof here with more details if it is necessary, but that question has already been answered, for example, here: https://mathoverflow.net/questions/57828/p-np-exp-has-circuit-size-o2n-n (the answer is pretty sketchy, though, so feel free to ask for more details).

---
Tags: complexity-theory
---


title: Bytes addressable processor

text:
# Question
Title: Bytes addressable processor
In MIPS processor, address bus is of 32 bits. So on addressing an instruction, a whole 32 bit instruction is fetched. How is it byte addressable then? I mean if on addressing a particular address, the memory sends 32 bits as a wholesome, how is it byte addressable?

# Answer
> 1 votes
"Byte addressable" means that a 32-bit address points to a single byte of memory, so if you increment that address, it points one byte further.

"Word addressable" means that (on a 32-bit processor) every 32-bit address points to a 32-bit word, so if you increment that address, it points *four* bytes further in memory.

Some machines can support both byte addressable and word addressable modes of operation. But for the naming, we're concerned with the *smallest* unit they can address.

---
Tags: computer-architecture, cpu, mips
---


# Question
Title: Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}
I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help Thanks in Advance!

# Answer
> 0 votes
Hint, the grammar $S \to a S c \mid b$ generates the language $\\{a^n b c^n : n \geq 0\\}$. Can you you adapt this? Do you understand why it generates that language?

---
Tags: finite-automata, context-free
---


# Question
Title: Find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given 2-d points, but no edge exceeds length L
Given a set of points in the 2-d plane, find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given points, but no edge exceeds length L.

Here is an algorithm, which I think might work but seems slow:

1. Pick a random point
2. find the distance of its nearest neighbour, store the distance, d
3. your set of covered points, S, now has 2 points in it
4. find the nearest neighbour point (which is not in S) to any points in S and compute its distance to a point in S, e. Add this new point to S.
5. d = max(d,e)
6. repeat steps 4 and 5 until all points have been added to S. now d is the required distance L.

I need help determining if this is correct and if so, the time complexity. Also can the algorithm be made faster (it will be run over a lots of data)?

# Answer
Yes, your algorithm is correct. The correctness can be proven by induction on $S$ easily.

Instead of growing by selecting the nearest point to $S$, a faster way in general should be just selecting the shortest edge available and including both of its end points. How to select the next shortest edge available? Construct a min-heap of all edges up front. Pop out the top of the heap one by one. Using a counter you can stop once all points are included. The length of the last edge included is the minimum edge size wanted.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Find the smallest element greater than current element
my question is that given a list of integers (lets say A), for each element A\[i\], find the smallest element A\[j\] which could satisfy A\[i\] \< A\[j\] and i \< j. Return -1 if there is no such element.

For example, given \[4,2,1,9,3\], return \[9,3,3,-1,-1\]

I have come up with a brute force solution which costs $O(n^2)$, but I'm wondering if there could be a more efficient solution.

# Answer
> 3 votes
A better solution would be using a balanced binary search tree.
You can process the elements from the right to left and for each element you find the vertex in the tree with the smallest key greater than this element (a search query on the tree suffice) and then you add the element to the tree.
Total complexity is $O(n\log(n))$ since we are iterating over the elements once and having one query and one insert operations in each iteration.

---
Tags: algorithms, arrays
---


# Question
Title: How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount
I know that CFG for $$ \\{a^{m}b^{n}\mid m\leq n\leq 2m \\}$$ is $$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak it in such a way that it is **strictly** in between m and 2m and not equal to any of m or 2m. I want to draw PDA for the same.

For drawing the PDA what I did was to push non-deterministically 1 a and 2a's and popping them out for b one by one. How should I handle the edge case that it always doesn't push 1 a or not always 2 a's?

# Answer
> 1 votes
As you knew intuitively, you just missed the solution by a millimeter, which, however, may look like a mile away.

$S\rightarrow aabbb/aSb/aSbb$

The idea is simple. Since $ab$ and $abb$ should not be generated, what is the shortest or simplest word that can be generated?

Here is a sketch of a NPDA. When it reads the first $a$, it goes to state $q\_1$. When it reads the second $a$, it goes to state $q\_2$. Then every time if it reads one $a$, it will push one or two $a$'s nondeterministically onto the stack. Then when it reads the first $b$ it goes to state $q\_4$. When it reads the second $b$ it goes to state $q\_5$. When it reads the third $b$ it goes to state $q\_6$. Then every time if it reads one $b$, it pops out one $a$ from the stack, staying at state $q\_6$.

I will let you flesh out the details.

---
Tags: finite-automata, context-free, pushdown-automata
---


# Question
Title: Show that for any real constants $a$ and $b$, where $b > 0$, $(n + a)^b = \Theta(n^b)$
I'm currently studying growth of function chapter in Introduction to Algorithm. In exercise 3.1-2 the question is:

> Show that for any real constants $a$ and $b$, where $b\>0$,
> $(n + a)^b = \Theta(n^b)$.

I understand I need to find constants $c\_1$, $c\_2$, $n\_0 \> 0$ where

> $0 \leq c\_1n^b \leq (n+a)^b \leq c\_2n^b$ for all $n \geq n\_0$.

But I don't understand what should I do after above step. Looking at the solution, it shows

> $n + a \leq n + |a|$
> $n + a \leq 2n$, when $|a| \leq n$

and

> $n + a \geq n - |a|$
> $n + a \geq \frac{n}{2}$ , when $|a| \leq \frac{n}{2}$

How did they come up with $n + a \leq n + |a|$ and $n + a \geq n - |a|$ just from $0 \leq c\_1n^b \leq (n+a)^b \leq c\_2n^b$ ? Are they derived from $0 \leq c\_1n^b \leq (n+a)^b \leq c\_2n^b$ ? Or are they just a general knowledge that can help solve this problem?

Please help me to understand them.

Thank you!

UPDATE: I have updated the question to be more specific.

# Answer
> 1 votes
> I understand I need to find constants $c\_1$, $c\_2$, $n\_0 \> 0$ where
>
> $0 \leq c\_1n^b \leq (n+a)^b \leq c\_2n^b$ for all $n \geq n\_0$.
>
> But I don't understand what should I do after above step.

The approach you would like to use here is "going backwards from the target".

Suppose we do have $c\_1n^b \leq (n+a)^b$ for some constant $c\_1\gt0$ when $n$ is large enough. What can we understand or deduce from it? What is needed to make it true?

Since the exponent is the same, we can use the law of same exponent, $(x/y)^m = x^m/y^m$ to simplify that inequality so that we will have the appearances of our variable $n$ closer to each other.

$$ c\_1\leq \frac{(n+a)^b}{n^b}=\left(\frac{n+a}n\right)^b$$

Raising both sides to the power of $\frac1b$, we have

$$ (c\_1)^{\frac1b}\leq \left(\frac{n+a}n\right)^{b\\,\frac1b}=\frac{n+a}n = 1+\frac an$$

(Another way to obtain $(c\_1)^{\frac1b}\leq\frac{n+a}n$ is to raise both sides of $c\_1n^b \leq (n+a)^b$ to the power of $\frac 1b$.)

Since $c\_1$ is a positive constant, $(c\_1)^{\frac1b}$ is also a positive constant. To make the above inequality hold, we would like to make $\left|\frac an\right|$ small enough. For example, we can require $\left|\frac an\right|\le \frac12$. That is why you see the following condition.

$$|a|\le\frac12 n$$

What is nice here is that we can reverse the above argument to obtain a wanted constant $c\_1$. Note that it is just as fine if we choose a different condition such as $|a|\le\frac13 n$ or $|a|\le\frac1{2019}n$ or infinitely many others.

If we start from $(n+a)^b \leq c\_2n^b$, we could arrive at $|a|\le n$.

> Are they derived from $0\le c\_1n^b\le(n+a)^b\le c\_2n^b$ ? Or are they just a general knowledge that can help solve this problem?

Yes, they are derived as you have just seen. You could say that they are general knowledge that helps solve this problem. You could also say that we just discovered some specific facts that help solve this problem.

# Answer
> 0 votes
If n is large then we have n/2 ≤ n + a ≤ 2n.

We therefore have $(1/2)^b n^b ≤ n^b ≤ 2^b n^b$.

There you have your two constants: $(1/2)^b$ and $2^b$.

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


# Question
Title: O(·) is not a function, so how can a function be equal to it?
I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.

I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.

$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ ***equals*** $O(f(n))$, if one asks you what's the ***value*** of $O(f(n))$, what would be your answer? There is no answer.

# Answer
> 108 votes
Strictly speaking, $O(f(n))$ is a *set* of functions. So the value of $O(f(n))$ is simply *the set of all functions that grow asymptotically not faster than $f(n)$*. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some caveats of the $O$ notation. For example, we write that $(1/2) n^2 + n = O(n^2)$, but we never write that $O(n^2)=(1/2)n^2 + n$. To quote Donald Knuth (The Art of Computer Programming, 1.2.11.1):

> The most important consideration is the idea of *one-way equalities*. \[...\] If $\alpha(n)$ and $\beta(n)$ are formulas that involve the $O$-notation, then the notation $\alpha(n)=\beta(n)$ means that the set of functions denoted by $\alpha(n)$ is *contained* in the set denoted by $\beta(n)$.

# Answer
> 44 votes
$O$ is a function $$\begin{align} O : (\mathbb{N}\to \mathbb{R}) &\to \mathbf{P}(\mathbb{N}\to \mathbb{R}) \\ f &\mapsto O(f) \end{align}$$ i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic bound of (at most) $f$. And strictly speaking the correct notation is thus $$ (n \mapsto T(n)) \in O(n\mapsto f(n)) $$ or short $$ T \in O(f) $$ but it's customary in maths, science and CS to just use a variable somewhere in the expression to denote that you're considering *functions of the argument $n$* on both sides. So $T(n) \in O(f(n))$ is quite fine as well. $T(n) = O(f(n))$ is pretty much wrong though, as you suspected. It is very commonly used though, so definitely keep in mind what people mean when they write this.

I would advise against ever writing $T(n) = O(f(n))$, but opinions differ.

# Answer
> 13 votes
Formally speaking, $O(f(n))$ is a the set of functions $g$ such that $g(n)\leq k\\,f(n)$ for some constant $k$ and all large enough $n$. Thus, the most pedantically accurate way of writing it would be $T(n)\in O(f(n))$. However, using $=$ instead of $\in$ is completely standard, and $T(n)=O(f(n))$ just means $T(n)\in O(f(n))$. This is essentially never ambiguous because we almost never manipulate the set $O(f(n))$.

In a sense, using equality makes $O(f(n))$ mean "some function $g$ such that $g(n)\leq f\\,g(n)$ for all large enough $n$", and this means that you can write things like $f(n) = 3n + O(\log n)$. Note that this is much more precise than, e.g., $f(n)=\Theta(n)$ or $f(n)=O(n+\log n)$.

# Answer
> 11 votes
*Prologue: The big $O$ notation is a classic example of the power and ambiguity of some notations as part of language loved by human mind. No matter how much confusion it have caused, it remains the choice of notation to convey the ideas that we can easily identify and agree to efficiently.*

> I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.

Sorry, but you do not have an issue if you understand the meaning of big $O$ notation.

> I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things. $T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ ***equals*** $O(f(n))$, if one asks you what's the ***value*** of $O(f(n))$, what would be your answer? There is no answer.

**What is important is the semantics**. What is important is (how) people can agree easily on (one of) its precise interpretations that will describe asymptotic behavior or time or space complexity we are interested in. The default precise interpretation/definition of $T(n)=O(f(n))$ is, as translated from Wikipedia,

> $T$ is a real or complex valued function and $f$ is a real valued function, both defined on some unbounded subset of the real positive numbers, such that $f(n)$ is strictly positive for all large enough values of $n$. For for all sufficiently large values of $n$, the absolute value of $T(n)$ is at most a positive constant multiple of $f(n)$. That is, there exists a positive real number $M$ and a real number $n\_0$ such that
>
> ${\text{ for all }n\geq n\_{0}, |T(n)|\leq \\;Mf(n){\text{ for all }}n\geq n\_{0}.}$

Please note this interpretation is considered **the definition**. All other interpretations and understandings, which may help you greatly in various ways, are secondary and corollary. Everyone (well, at least every answerer here) agrees to this interpretation/definition/semantics. As long as you can apply this interpretation, you are probably good most of time. Relax and be comfortable. You do not want to think too much, just as you do not think too much about some of the irregularity of English or French or most of natural languages. Just use the notation by that definition.

> $T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ ***equals*** $O(f(n))$, if one asks you what's the ***value*** of $O(f(n))$, what would be your answer? There is no answer.

Indeed, there could be no answer, since the question is ill-posed. $T(n)$ does not mean an exact number. It is meant to stand for a function whose name is $T$ and whose formal parameter is $n$ (which is sort of bounded to the $n$ in $f(n)$). It is just as correct and even more so if we write $T=O(f)$. If $T$ is the function that maps $n$ to $n^2$ and $f$ is the function that maps $n$ to $n^3$, it is also conventional to write $f(n)=O(n^3)$ or $n^2=O(n^3)$. Please also note that the definition does not say $O$ is a function or not. It does not say the left hand side is supposed to be equal to the right hand side at all! You are right to suspect that equal sign does not mean equality in its ordinary sense, where you can switch both sides of the equality and it should be backed by an equivalent relation. (Another even more famous example of abuse of the equal sign is the usage of equal sign to mean assignment in most programming languages, instead of more cumbersome `:=` as in some languages.)

If we are only concerned about that one equality (I am starting to abuse language as well. It **is not an equality**; however, it **is an equality** since there is an equal sign in the notation or it could be construed as some kind of equality), $T(n)=O(f(n))$, this answer is done.

However, the question actually goes on. What does it mean by, for example, $f(n)=3n+O(\log n)$? This equality is not covered by the definition above. We would like to introduce another convention, **the placeholder convention**. Here is the full statement of placeholder convention as stated in Wikipedia.

> In more complicated usage, $O(\cdots)$ can appear in different places in an equation, even several times on each side. For example, the following are true for $n\to \infty$.
>
> $(n+1)^{2}=n^{2}+O(n)$
> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$
> $n^{O(1)}=O(e^{n})$
>
> The meaning of such statements is as follows: for any functions which satisfy each $O(\cdots)$ on the left side, there are some functions satisfying each $O(\cdots)$ on the right side, such that substituting all these functions into the equation makes the two sides equal. For example, the third equation above means: "For any function $f(n) = O(1)$, there is some function $g(n) = O(e^n)$ such that $n^{f(n)} = g(n)$."

You may want to check here for another example of placeholder convention in action.

You might have noticed by now that I have not used the set-theoretic explanation of the big $O$-notation. All I have done is just to show even without that set-theoretic explanation such as "$O(f(n))$ is a set of functions", we can still understand big $O$-notation fully and perfectly. If you find that set-theoretic explanation useful, please go ahead anyway.

You can check the section in "asymptotic notation" of CLRS for a more detailed analysis and usage pattern for the family of notations for asymptotic behavior, such as big $\Theta$, $\Omega$, small $o$, small $\omega$, multivariable usage and more. The Wikipedia entry is also a pretty good reference.

Lastly, there is some inherent ambiguity/controversy with big $O$ notation with multiple variables, and . You might want to think twice when you are using those.

# Answer
> 10 votes
In The Algorithm Design Manual \[1\], you can find a paragraph about this issue:

> The Big Oh notation \[including $O$, $\Omega$ and $\Theta$\] provides for a rough notion of equality when comparing functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its meaning can always be resolved by going back to the definitions in terms of upper and lower bounds. It is perhaps most instructive to read the " = " here as meaning "*one of the functions that are*". Clearly, $n^2$ is one of functions that are $O(n^3)$.

Strictly speaking (as noted by David Richerby's comment), $\Theta$ gives you a rough notion of equality, $O$ a rough notion of less-than-or-equal-to, and $\Omega$ and rough notion of greater-than-or-equal-to.

Nonetheless, I agree with Vincenzo's answer: you can simply interpret $O(f(n))$ as a set of functions and the *=* symbol as a set membership symbol $\in$.

---

\[1\] Skiena, S. S. The Algorithm Design Manual (Second Edition). Springer (2008)

# Answer
> 7 votes
Usually, statements like $$f = O(g)$$ can be interpreted as $$ \text{there exists } h \in O(g) \text{ such that }f = h\\,. $$

This becomes more useful in contexts like David Richerby mentions, where we write $f(n) = n^3 + O(n^2)$ to mean "there exists $g(n) \in O(n^2)$ such that $f(n) = n^2 + g(n)$."

I find this existential quantifier interpretation so useful that I am tempted to write things like

$$ f(n) \leq O(n^3) $$

which some will find an even more egregious style violation, but it is just a space-saving way of writing "there exists $C$ such that $f(n) \leq C n^3$."

# Answer
> 2 votes
Many other posters have explained that the Big-O can be thought of as denoting a set of functions, and that the notation $n^2 = O(n^3)$ indicates that $n^2$ (as a function of $n$) *is in the set* denoted by $O(n^3)$ (again considering $n$ as the parameter). In English text, you may prefer to write "$n^2$ is in $O(n^3)$" to avoid confusion.

Although the notation can be confusing, it may help to think of the $O$ and the $=$ as parts of the same notation, that is, to treat $= O$ as if it were one symbol. It is little different from what we do when we write `>=` in a programming language: two symbols, adjacent, become one in our eyes.

Another tricky aspect of the notation is that the variable acting as the parameter is not explicitly identified, or *bound*, the way it would be in a function declaration or a lambda notation. This can be especially confusing when there are two variables involved, as in $O(mn)$ or even more so in an expression like $O(n^c)$ since it may be implied that $c$ is a constant. Then again, some algorithms have complexity in a Big-O set that technically varies according to two variables, while in practice one of them is fixed. Still more, there may be multiple reasonable ways of measuring the complexity of one algorithm. For example, if the input is a number, your algorithm might be $O(n)$ in the value $n$ of the number but $O(2^b)$ in the bit size of the number. (Although in complexity theory per se, the bit size is usually the right parameter.)

All this is to say that the Big-O is an informal notation, hounded by imprecision, and you often have to use other context to understand what an author is saying.

As always, you're best to avoid confusion in your own writing, and I suggest avoiding the $= O$ and using instead $\in O$ or the English "…is in…"

# Answer
> 2 votes
Just to underline the point which has been made several times, allow me to quote from N. G. de Bruijn, *Asymptotic Methods in Analysis*:

> The common interpretation of all these formulas can be expressed as follows. Any expression involving the $O$-symbol is to be considered as a class of functions. If the range $0 \< x \< \infty$ is considered, then $O(1) + O(x^2)$ denotes the class of all functions of the form $f(x) + g(x)$, with $f(x) = O(1)\\,\\,(0 \< x \< \infty)$, $g(x) = O(x^2)\\,\\,(0 \< x \< \infty)$. And $x^{-1}O(1) = O(1) + O(x^{-2})$ means that the class $x^{-1}O(1)$ is contained in the class $O(1) + O(x^{-2})$. Sometimes, the left-hand-side of the relation is not a class, but a single function \[...\]. Then the relation means that the function on the left is a member of the class on the right.
>
> It is obvious that the sign $=$ is really the wrong sign for such relations, because it suggests symmetry, and there is no such symmetry. For example, $O(x) = O(x^2)\\,\\,(x \rightarrow \infty)$ is correct, but $O(x^2) = O(x)\\,\\,(x \rightarrow \infty)$ is false. Once this warning has been given, there is, however, not much harm in using the sign $=$, and we shall maintain it, for no other reason than that it is customary.

Donald Knuth also pointed out that mathematicians often use the $=$ sign as they use the word "is" in English. "Aristotle is a man, but a man isn’t necessarily Aristotle."

Having said that, Bender and Orszag's notation (from *Advanced mathematical methods for scientists and engineers*) is a lot less confusing and is worth considering. With respect to some limit, we say:

$$f(x) \sim g(x)\\,\\,(x \rightarrow x\_0)$$

(pronouncted "$f$ is asymptotic to $g$") means

$$\lim\_{x \rightarrow x\_0} \frac{f(x)}{g(x)} = 1$$

and:

$$f(x) \ll g(x)\\,\\,(x \rightarrow x\_0)$$

(pronounced "$f$ is negligible compared to $g$") means

$$\lim\_{x \rightarrow x\_0} \frac{f(x)}{g(x)} = 0$$

But I suppose the benefit of big-oh notation is that the constant factor is arbitrary. (And for little-oh notation, the constant factor is whatever you what.)

# Answer
> 0 votes
I went over this on stackoverflow; while perhaps the most correct answer to OP's has already been stated above (equivalence classes, restated below as #1), here is a complete answer:

1. **sets**: "$f= O(\cdot)$" means $f \in O(\cdot)$, i.e. membership in a set, e.g. $\\{\frac{1}{2} x^2, (5 x^2-x+5), 2.5x,...\\}$ "the set of functions asymptotically bounded by $x^2$". This is the standard mathematical treatment of asymptotic notation that I am aware of. This set has a partial order corresponding to subset-of, e.g. $O(x^2) \< O(x^3) = O(x^3 + x)$ (some sets may be incomparable; DAG; see polynomial hierarchy for an interesting example).

note. "$f= \Theta(\cdot)$" means $f \in \Theta(\cdot)$. However, note that unlike the above, this is an equivalence relation (obviously the naive relation X as in `f X g` iff $f \in O(g)$ is not an equivalence class, since $f \in O(g)$ does not imply $g \in f(g)$; the trivial equivalence relation "both an element of $O(g)$" is perhaps amusing to conceptualize but mathematically uninteresting, whereas with $\Theta$ the multiple equivalence classes partition the space of functions).
2. **wildcard expression**: You can backwards-engineer the definition of $f \in \Theta(g)$: after some radius of uncaring near the origin (i.e. there exists an $x\_0$, such that for all $x\>x\_0$...), there exists a band bounded constant multiples of $g$ that bounds $f$ (i.e. $LOW\*g(x) \le f(x) \le HIGH\*g(x)$)... and so we can backwards-engineer this to merely replace any expression $O(g)$ with the expression $k\_1g(x)+err(x)$, that is, replace it with the bound itself plus an error term we don't care about (an error term bounded by $0 \le err(x) \le k\_2g(x)$ for $x\>x\_0$ and potentially unbounded for $x\le x\_0$)..... so for example if we said $f = 2^{\Theta(x^2)}$, we could equivalently say $f(x)=2^{k\_1x^2+err(x)}$ where this error term is $0 \le err(x) \le k\_2x^2$. We would never ever write this down though... because it's a bit silly. But I believe it may be legitimate to think of it that way, and would preserve the notion of equality. (I am eliding proper treatment of negative signs here, which may be important.)

a. Modify the above as appropriate for $O$ instead of $\Theta$

# Answer
> 0 votes
A more exact answer would be that when we say a function f is 'big O of function g'. (I.e. x^2 + x is O(x^2)) we are saying that f(x) \< C\*g(x) for some value C and k where x \> k. This means that g is an upper bound for the behaiver of f.

Example

x^2 + 10x 4 is O(x^2 + x) which is itself O(x^2)

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


# Question
Title: Least number of guesses needed to determine all unknown subsets of a set
Say I have a set $\mathbb{S}=\\{1,2,...,n\\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and my adversary has to tell me if $s$ is itself a *subset of any element* in $\mathbb{A}$.

For example, if $n=4$, a valid $\mathbb{A}$ might be $\\{ \\{2\\}, \\{1,3,4\\}\\}$. All "true" guesses are $\\{1\\}$, $\\{2\\}$, $\\{3\\}$, $\\{4\\}$, $\\{1,3\\}$, $\\{3,4\\}$, $\\{1,4\\}$, $\\{1,3,4\\}$.

What's the fastest algorithm and the upper bound on number of guesses I need to make to fully reverse engineer $\mathbb{A}$?

---

Obviously the brute force algorithm takes $^nC\_1 + ^nC\_2 + ... + ^nC\_n $ guesses for every possible subset.

But I think I only need to test all possible subsets of size 2 i.e. exactly $^nC\_2$ guesses?

Then, I can represent each of the correct guesses of size 2 as an undirected edge in a graph. Every member of $\mathbb{A}$ of size 3 or greater should form a simple cycle in this graph. So I just need to DFS on every node in this graph, removing the *longest* cycle detected from the graph, and repeat for all remaining nodes until only lone edges (subsets of size 2) or unconnected vertices (subsets of size 1) remain.

This graph should have $n$ vertices and at most $^nC\_2$ edges. So the fastest algorithm has a time complexity of $\mathbb{o}(n^{2}\cdot{}^{n}C\_{2})$. Is there an approach with fewer guesses or a faster graph algorithm?

**P.S.: In case anyone's interested about the context:** One example use case is if $n$ known services are hosted on unknown $k$ servers with unknown grouping, and you have some way to overload any subset of services to mount a denial attack on a server. The problem becomes if you can profile the servers with the least number of queries. I came across a similar scenario and thought this was a pretty interesting problem with no literature on.

# Answer
> 2 votes
A simple algorithm may be:

Loop on:

1. take the next unassigned element Ei and create a new set Si assigning Ei to it.
2. loop on all unassigned elements Ej, testing the pair {Ei,Ej}. If it is true, assign j it to Si.

In worst case, this is O(kn) as you won't do this loop more than k times. In average case, I am not sure...

---
Tags: graphs, time-complexity, runtime-analysis, graph-traversal
---


# Question
Title: Given set of grammar rules, how to find if they correspond to Context-free or unrestricted
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted?

Just for Understanding (don't solve the below one), eg:

\begin{align} S &\rightarrow B/A, \\ 1B &\rightarrow 111B, \\ 1A0 &\rightarrow 00 \end{align}

# Answer
It is undecidable to determine whether the *language* generated by a given grammar has a context-free grammar.

However, if you are simply asking whether a *grammar* itself is context-free, look no further than the left hand side of each production. A grammar is context free iff the left hand side of each production is a single non-terminal.
> 1 votes

---
Tags: turing-machines, finite-automata, context-free
---


title: Reducing subset sum to even subset sum

text:
# Question
Title: Reducing subset sum to even subset sum
I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are *even positive* integers. I'm trying to show this problem is NP-hard by reducing the problem subset sum to it but I'm not sure where to start.

# Answer
Hint: suppose that we are able to solve your problem efficiently. Then what if we take an arbitrary subset sum problem and multiply all elements by $2$, as well as the target?
> 2 votes

---
Tags: reductions, np-hard, subset-sum
---


# Question
Title: How to draw a parsing tree according to syntax diagram?
I would really appreciate if someone can explain the syntax diagram itself and can help to build the parsing tree.

# Answer
That diagram describes a language, a set of words over some alphabet.

Intuitively, this language contains all the words that can be obtained traveling over the diagram from the beginning (on the left) and following the arrows.

If we take the upper route, we build a word starting with $x$, then continuing with any string (or at least that's how I read that "String" box), and then ending with another $x$.

If we take the lower route, we form the word $x$, only.

To solve the exercise, you have to find a route which can generate the given string $xxyxx$. When doing so, you have to note down what parts of your string correspond to the nodes in the diagram (e.g. what correspond to the "String" box).

Note that this diagram is somewhat simple, in that it has no loops, so the parse tree is also simple. With loops, it could be more complex.

The last part of the exercise asks you to find a word which can not be generated following the diagram.
> 3 votes

---
Tags: programming-languages
---


# Question
Title: Examples of interesting semantics to study during a small project for a graduate Semantics course
I have been following the course Concrete Semantics with Isabelle/HOL. At some point we are given the task to verify a program/extend some semantic construction/prove some mathematical fact. I personally prefer to dive a little bit more into operational semantics, so adding new features to the IMP language is the way to go.

The classical extensions are non-determinism/parallel execution. These are described in a variety of books (Winskel, Hennessy or Nielson to cite only classical authors). However, I feel the treatment is rather limited and I'm not sure that can be turned into project, it looks more like a bunch of exercises.

So my question is are you aware of any simple but interesting extensions of the operational semantics approach to the study of a simple WHILE-program (such as IMP)? I would be looking specially for significant properties that can be proved in that semantics and illustrative examples that may be relevant.

# Answer
You could add more flow control to IMP, like (simple) exceptions, or `break` to exit early from a `while` loop.

You could some partial operators (division, square root) requiring you to handle runtime errors.

You could add more complex data types, like pairs. Make it so that e.g. projecting a value out of a non-pair value causes a runtime error. Craft a (first-order) simple type system e.g. using `T ::= int | (T*T)` as types, and prove that "typeable programs do not go wrong", i.e. executing them never lead to runtime errors.

You could add functions / procedures. This is not so trivial at first, especially if you want to consider several ways for parameter passing (e.g. pass-by-value, pass-by-reference).

You could prove that a suitable restriction of IMP (say, sans `while`, or with a constrained `while`) is always terminating.
> 1 votes

---
Tags: programming-languages, semantics, operational-semantics
---


title: How is $L^* - \{\epsilon \} \neq L^+$?

text:
# Question
Title: How is $L^* - \{\epsilon \} \neq L^+$?
I was asked which among the following is true:

> 1. $\Sigma^\*-\\{\epsilon\\} = \Sigma^+$
> 2. $L^\* - \\{\epsilon \\} = L^+$

As I can see, both $\Sigma^\*$ & $L^\*$ are sets. I thought both were true because of set difference, but the answer lists only the first option as correct and the second as false. How so?

# Answer
> 3 votes
If $\varepsilon \in L$, then necessarily $\varepsilon \in L^+$ (and the converse as well). This is because $L$ itself is contained in $L^+$ and $L^+$ is defined as the union over the powers $L^i$ of $L$ for $i \in \mathbb{N}\_+$. Note $L^+$ is *not* defined as $L^\ast \setminus \\{ \varepsilon \\}$; this is a common mistake.

Hence, $\varepsilon \not\in L^+$ holds if and only if $\varepsilon \not\in L$. This is the case for the alphabet $\Sigma$, hence why it is correct in the first case.

---
Tags: formal-languages, kleene-star
---


# Question
Title: Leo's deterministic reduction for Earley Parsing
I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows:

```
def predict(self, column, symbol, state):
    # original predict
    for alternative in grammar[symbol]:
        column.add(a new state corresponding to alternative)
    # Aycock fix
    if nullable(symbol):
        column.add(state.advance())

```

And Leo's optimization for right recursion using the explanation here for further insight. I am able to understand how to parse Right Recursive grammars with it. However, I am confused when it comes to using it to parse non-right recursive grammars. For example, here is a grammar that can parse an example string `aa`

```
    <start> := <A>
    <A>     := <A> + 'a'
    <A>     := \epsilon

```

Without the deterministic reduction from Leo, the Earley items constructed (pipe indicates the dot) are as follows: The parenthesis is in this format (starting column, earley set).

```
char: _ column[0]
<start>:= | <A>(0,0)     #1) init
<A>:= | <A> a(0,0)       #2) predict from 1
<A>:= |(0,0)             #3) predict from 1
<start>:= <A> |(0,0)     #4) epsilon complete from 3
<A>:= <A> | a(0,0)       #5) epsilon complete from 3

char: a column[1]
<A>:= <A> a |(0,1)       #6) scan a from 5
<start>:= <A> |(0,1)     #7) complete A from 1 (start col of 6)
<A>:= <A> | a(0,1)       #8) complete A from 2 (start col of 6)

char: a column[2]
<A>:= <A> a |(0,2)       #9) scan a from 8
<start>:= <A> |(0,2)     #10) complete A from 1 (start col of 9)
<A>:= <A> | a(0,2)       #11) complete A from 2 (start col of 9)

```

According to Leo,

> **Definition 2.1**: An item is said to be on the deterministic reduction path above $ \[A \rightarrow \gamma., i\] $ if it is $ \[B \> \rightarrow \alpha A ., k\] $ with $ \[B \rightarrow \alpha . A, k\] $ being the only item in $ I\_i $ with the dot in front of A, or if it is on the deterministic reduction path above $ \[B \rightarrow \alpha A ., \> k\] $. An item on such a path is called *topmost* one if there is no item on the deterministic reduction path above it.

(I am assuming that $ \[B \rightarrow \alpha A ., k\] $ is also in $ I\_i $.)

The completer is as follows:

```
def complete(self, column, state):
    detred = self.deterministic_reduction(state)
    if detred:
        column.add(detred)
    else:
        for st in (matching states in start column of state):
            column.add(st.advance())

```

# column 0

So, when it processes item (3) `<A>:= |(0,0)` in `column[0]` for completing, it finds both item (1) which obeys the restriction for a single item with dot before `<A>` and the corresponding item (4) with dot after. Hence, it considers (4) on the deterministic path. This does not change anything for column\[0\]. However, things change for column\[1\].

# column 1

When it processes (6) for completing, it again finds (1) and item (4), and hence (4) is considered a parent in the deterministic path. Hence, it saves a copy (4) to the column\[1\] **rather than completing it traditionally in earley**. This means that the item (8) `<A>:= <A> | a(0,1)` from the original Earley parse **never gets created**, which means no item for accepting the next `a` in column\[2\] (which should have been added to column\[2\] by scanning of this item), and the parsing fails.

So, my understanding of *deterministic reduction* bye Leo is somehow faulty. Where have I gone wrong?

I have read up on all materials I could get on Leo's optimization, but still unclear what I have missed. I think the item (4) should not be a parent because it is not a previous instance of the recursive rule in item (6). However, nothing in Leo's paper seems to explain how I can exclude such instances from the deterministic path.

If it helps, the complete self contained implementation is here.

# Answer
> 2 votes
I found the problem: Essentially, I misunderstood the definition. It says that

> it is \[B→αA.,k\] with \[B→α.A,k\] being the only item in Ii with the dot in front of A, or if it is on the deterministic reduction path above \[B→αA.,k\].

Which should be interpreted as `[B→αA.,k]` should be considered to be created corresponding to `[B→α.A,k]`. The basic idea which seems to be elided in Leo's paper but given in Grune et al. (2008) is that, the deterministic reduction is basically simply an eager completion with all intermediate results thrown away. With this change, the parser works correctly.

(The "Parsing Techniques A Practical Guide" by Grune et al. from 2008 is the book I refer to here.)

---
Tags: algorithms, context-free, parsers
---


# Question
Title: If a DFA were implemented as a circuit, what would the empty string correspond to as input?
Say we have a DFA like the one shown below that accepts the empty string, $\varepsilon$.

Also suppose the functionality of this DFA has been implemented as a circuit so that an led lights up whenever an accepted word is detected as input.

While this hypothetical circuit is "idle", i.e. not receiving any a's or b's as input, is the led on? Is it appropriate to think of $\varepsilon$ as idling without real input? Is that what $\varepsilon$, an input string of length zero, represents?

As a follow up, for a circuit implementation of the next DFA, would it have an led that never turns on even while idle?

# Answer
> 1 votes
Deterministic automata over finite words (DFAs) that accept or reject a given word can be seen as finite-state machines that read elements from some alphabet $\Sigma$ and output elements from the output alphabet $\mathbb{B}$ that represent whether the word read so far is accepted by the original DFA.

Translating such finite-state machines to circuits is a classical topic in technical computer science. For instance, you could assign a bit-vector of the same length to every state and then use the Espresso logic minimizer to compute a relatively efficient circuit. Note that such circuits have memory.

Such finite-state machine come in two variants: **Mealy** and **Moore machines**. Both of them operate in discrete steps. At every step of their computation, Mealy machines first read an input character and them produce an output character. For Moore machines, it is the other way around: they first produce their output character and then read the next input character.

The answer to your question now depends on which model you use: If you translate your DFA into Moore machine form, the machine first outputs whether the word seen so far is accepted and only then looks at the next character. In the first step of its computation, it thus outputs whether the empty word is accepted. Mealy machines read the respective next character in every step and only then produce the next output. Thus, whether the empty word is accepted by the original DFA cannot be observed when looking at a run of the Mealy machine (unless you do the translation in a way that the machine always delays its output by one step, which normally increases the number of states by a factor of at most two).

The model that Yuval Filmus was referring to in his comments is one that is used in circuit complexity. There, it is looked at how large circuits need to be that categorize inputs of a fixed length into accepted and non-accepted ones. The characters of the input words are all read at the same time in this model and the circuits do not have memory.

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


# Question
Title: Time Complexity of Nested For Loops where second loop starts from +1 index of the first loop
Hi I know two nested for loops will have time Complexity of O(n²). However let's say first loop starts from 0 and goes upto variable X max value(suppose x is n) and second loop starts from +1 of the first loop then we woudn't compare all the values of x with all the other values of x.In that case it woudn't be n². In that case +1 method cannot be O(n²) right? So what is it? Thanks.

# Answer
In this example, you will do on total n x (n/2) = n²/2 iterations. This is better than n² of course... But still O(n²).

If you double n, the number of iterations growth by a factor 4.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Are all possible programming languages a formal system?
Based on the Wikipedia page for a formal system, will all programming languages be contained within the following rules?

* **A finite set of of symbols.**

(This seems obvious since the computer is a discrete machine with finite memory and therefore a finite number of ways to express a symbol.)

* **A grammar.**
* **A set of axioms.**
* **A set of inference rules.**

Are all *possible* languages constrained by these rules? Is there a notable proof?

EDIT:

I've been somewhat convinced that my question may actually be: can programming languages be represented by something other than a formal system?

# Answer
Technically, yes, because you can make your formal system have a single axiom that says “the sequence of symbols is in the set $S$” where $S$ is the set of programs in the programming language. So this question isn't very meaningful. The notion of formal system is so general that it isn't terribly interesting in itself.

The point of using formal systems is to break down the definition of a language into easily-manageable parts. Formal systems lend themselves well to compositional definitions, where the meaning of a program is defined in terms of the meaning of its parts.

Note that your approach only defines whether a sequence of symbols is valid, but the definition of a programming language needs more than this: you also need to specify the meaning of each program. This can again be done by a formal system where the inference rules define a semantics for source programs.
> 6 votes

# Answer
The people doing programming language semantics try to describe programming languages in that way. Practicing programmers don't, their intuitive descriptions of the language is often fuzzy and outright contradictory (just take a look at the newbie questions and hurdles in your neighborhod freshman programming class, or at the problems people seek help with at stackoverflow). The programming languages in common use are much too complicated for a really complete formal description, so they don't qualify either. And then there are entertaining phenomena like undefined behaviour...
> 3 votes

# Answer
I would argue that an interpreter is, in fact, one way of defining a programming language. Since there are countably many Turing Machines, we could consider the set of all programming languages to be the set of all Turing Machines which take 2 inputs, a program and some input for that program, and output the result of "running" the program, with halting states to represent if the program was syntactically correct, encountered errors, etc.

Then, since a TM can be described by a finite set of symbols, a programming language can be described by a finite set of symbols.
> 1 votes

# Answer
Of course yes, and they have mostly been describe as is.

In fact most programming language has been define using Turing Machine which aren't formal system has you've define, but they are a kind of computation's model, define using formal language. Then grammar or axioms or complex inference rule (as expected for formal system) are not required.

Formal system can be view as a subset of Turing Machine with extra properties. Say differently you can have a programming language define using a Turing Machine as computation model but not fully fill the definition of formal system.

I'd like to add, inference rule required to define formal system are more than simple rule (as you can encounter in C for example or more simply in ASM), but we must ensure that any complex formulation of these rule can be decidable, it's mean, we must have inference's rule which rely on strong logical foundation.

Considering axiom, again we need more than a set of *starting fact*, sharing truth among the program, but we most ensure from a mathematical point of view that these axioms mixed with the inference rule provide us a computation framework which must be consistent (axioms mixed with inference rule should not lead the program to have an unexpected behavior or contradiction) and complete (no formula express using axiom and inference rule should be undecidable).

Most of time theses requirements aren't apply to the language itself but to it's type system in order to benefit of safety at compilation time by the mean of completeness and consistency, which as said earlier derive from inference rules and axiom (True by construction is you like).

To conclude, all programming language are formal language, in the way that the program itself is writing using a formal language, but they don't required to be formal system, contrary to mathematics's theory as number theory, abstract algebra, category theory which are express too by formal language but this time with the goal to form a formal system.

Which why Functional Programming matter.
> 0 votes

# Answer
> Are all possible programming languages a formal system?

This is an interesting question. I would say that the answer is no. And then add that all **useful** programming languages are formal systems!

It is possible to imagine a programming language where the output is more or less non-controllable random regardless of the program and the input. I would describe this as a useless, non-formal system.

The formal system in a useful computer languages has a program, an input and an output. The formal system describes how the program + input creates the output, or as one special case never reaches a steady state output.
> 0 votes

---
Tags: formal-languages
---


# Question
Title: A repository for max flow and mincut datasets
I am not 100% sure if this is the right stackexchange to ask. I have a max-flow algorithm and I am also computing the min-cut from that algorithm.

I want to test the correctness and speed of it and I am trying to find if there are some datasets against which I can test my algorithm. The dataset should preferably have the max-flow value and the set of edges belonging to min-cut.

# Answer
> 2 votes
**To test correctness**: the set of edges belonging to a min-cut is *not unique* in general, so a dataset like you ask would not really be helpful, apart from checking that the value of the cut is the right one. However, it is easy to check correctness yourself by using the output of your algorithm if you compute *both* the max-flow and the min-cut; just check that the first is a valid flow, the second is a valid cut, and that their value is the same. By the max-flow/min-cut theorem, they must then both be optimal.

**To test speed**: it's pretty old (1990-91), but you may want to have a look at the archive of the DIMACS implementation challenge on the Maximum Flow problem. It includes many generators and several other codes. For a more modern dataset (1998-2013), here is a collection of Maximum Flow problems arising in computer vision. Also, Andrew V. Goldberg has a page on network optimization software with several useful links (although the Min Cut one seems to be dead).

---
Tags: network-flow
---


title: Graph Edit Distance

text:
# Question
Title: Graph Edit Distance
Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance, Advances in Computer Vision and Pattern Recognition.

Link: https://www.springer.com/cda/content/document/cda\_downloaddocument/9783319272511-c2.pdf?SGWID=0-0-45-1545097-p177820399

Below I want to ask clarification for an example in the text as it will help to understand when we say the edge is deleted and when we call it is substituted.

In the discussion of Example-8:

Deleting u1 costs 1, Substituting u2 by v3 will cost 2 (node substitution cost + deletion of (u1,u2)), Substituting u3 by v2 will cost 1 (node substitution, edge substitution: (u2,u3) by (v2,v3) ) and Substituting u4 by v1 will cost 2 (node substitution + deletion of (u2,u4)). So the total cost seems to be 6 but the text mentions it as 4.

I have also added the source as an image for convenience, thanks in advance!

# Answer
No, it is not an error.

u1 is deleted. Cost 1.
u2 is substituted with v3. Cost 0 (Equal labeling).
This Operation together with the first Node deletion implies the deletion of edge (u1, u2). Cost 1.
u3 is substituted with v2. Cost 1.
This implies the substitution of edge (u2,u3) with (v3,v2) with cost 0.
u4 is substituted with v1. Cost 0.
This implies the substitution of edge (u3,u4) with (v2,v1) with cost 0 and the deletion of edge (u1,u4) with cost 1.

Hence, we have a total cost of 4.
> 2 votes

---
Tags: algorithms, graphs, np-hard, edit-distance
---


# Question
Title: Is this definition of a "complete graph" correct?
Is it correct to say that:

"A complete graph is a graph in which each vertex is connected to all other vertices in the graph"

That's how I always thought about it, the official definition is different (I know that).

# Answer
I'm not sure what "official definition" you have in mind but your definition of a complete graph is correct: it implies that every pair of distinct vertices are connected by an edge.

At least, it does assuming that by "connected", you mean "has an edge to". It's best to avoid using the word in that way, since "connected" in graph theory refers to the existence of paths that might be longer than a single edge.
> 3 votes

# Answer
Yes, if you just want to talk about a property of complete graph, in which case, it is better to avoid using "A complete graph is ...". It will be clear and unambiguous if you say, in a complete graph, each vertex is connected to all other vertices.

No, if you did mean a definition of complete graph. For example, all vertice in the 4-cycle graph as show below are pairwise connected. However, it is not a complete graph since there is no edge between its middle two points.

We can review the definitions in graph theory below, in the case of undirected graph.

A path from $x$ to $y$ is a finite of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another.

An unordered pair of vertices {x, y} is called connected if a path leads from x to y. Otherwise, the unordered pair is called disconnected.

A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge

You may have been thinking that a vertex is connected to another only when there is an edge between them. While that is correct in ordinary English, you would better stick to the general convention and terminologies in the graph theory, where two vertices is connected is defined as above.

There is another way to think about complete graph. For each edge {x, y}, the vertices x and y are said to be adjacent to one another. As j\_random\_hacker suggested, we can say "A complete graph is a graph in which each vertex is adjacent to all other vertices in the graph".

---

Exercise: Is the 3-cycle graph a complete graph? Is the 5-cycle graph a complete graph?
> 0 votes

# Answer
Assume each edge's weight is 1. A complete graph is a graph which has eccentricity 1, meaning each vertex is 1 unit away from all other vertices. So, as you put it, "a complete graph is a graph in which each vertex has edge with all other vertices in the graph."
> 0 votes

---
Tags: graphs
---


# Question
Title: The role of the root switch after Spanning Tree Protocol has established a tree network in a LAN?
In **Spanning Tree Protocol**, a root switch is selected at first, and then somehow, the shortest path from each other switch to the root is obtained. Thus we established a tree network.

My questions are:

> * After the tree network is established, does the root switch act as a center in the network? In other words, all the traffic originated from other switch would first flow into the root switch along the shortest path and then routed to its destination by the root switch, also along the shortest path.
> * If it's not the case, why does the protocol calculate a tree such that the path between each non-root switches and the root is minimized? As far as I can see, a minimum spanning tree would work better, which is not difficult to calculate.

# Answer
> 1 votes
I can find no requirement that all traffic is routed through the root switch. For example, in A\<--\>B\<--\>C, with C the root switch, traffic fom A to B does not pass through the root switch.

The spanning tree protocol first selects a root switch. In Cisco, this is the switch with the lowest bridge ID. So the selection of the root is arbitrary. Now a tree is built that connects all switches, without creating cycles. Even if initially a *minimum* spanning tree is created because links with maximum bandwidth (minimum cost) are selected, at some future point this may no longer be when a link fails and a redundant link or path is enabled. This new link may result in the total tree not being a minimum spanning tree anymore. I can imagine that reconfiguring the whole tree to be minimum again can cause unwanted overhead.

I found this information on Wikipedia and Cisco. I am not a network guru so my answer may not be complete. I found no information that the initial tree created is minimum though it seems to meet the requirements and seems to follow e.g. Kruksal's algorithm.

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


# Question
Title: Polynomial Time Algorithm for Steiner Tree Problem
I know about Steiner Tree Problem. It is stated as

> Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree that spans all the nodes in T.

Can we give a `polynomial time algorithm` to solve the Steiner Tree Problem such that |T| ≥ n−1 where n is the number of nodes in the original graph. I've done a lot of RnD on it but it is still confusing. Can any one help me out?

# Answer
Yes, given a weighted graph $G$ with $n$ nodes and a subset $T$ of nodes whose cardinality is no less than $n−1$, there is a polynomial time algorithm that finds a minimum weight tree that spans all nodes in $T$.

Here is a simple algorithm.

* Find a minimum-weight spanning tree $M$ of $G$. This is can be done by Kruskal's algorithm in $O(E\log E)$ time-complexity.
* If $|T|=n$, return $M$.
* Otherwise, $|T|=n-1$. There is exactly one node of $G$ that is not in $T$. Let it be node $v$. Removing node $v$ and all edges incident to $v$ from $G$, we obtain a graph $G'$. Note that $T$ is the set of all nodes of $G'$. Find a minimum-weight spanning tree $M'$ of $G'$, using Kruskal's algorithm again. If the weight of $M$ is smaller than that of $M'$, return $M$; otherwise, return $M'$.

I will let you check that the above algorithm is correct with polynomial time complexity. It should be easy enough.

---

Exercise. When $|T|=n-1$, what does it mean if $M$ is returned instead of $M'$?

Exercise. Show that if $|T|\ge n-k$ for some constant $k$ instead of $|T|\ge n-1$, the same conclusion holds.
> 2 votes

---
Tags: algorithms, polynomial-time
---


# Question
Title: Complexity of linear programming with restricted quadratic constraints
A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x\_i$, there is a variable $s\_i$ (intuitively for approximating $x\_i^2$, and distinct from all the $x\_j$) and positive constants $l\_i,r\_i$, such that the following constraints are also included:

$l\_i ≤ x\_i ≤ r\_i$ (confined to boxes; this is the case for every variable in my application)

$l\_i x\_i ≤ s\_i ≤ r\_i x\_i$ (minor improvement over $l\_i^2 ≤ s\_i ≤ r\_i^2$)

$s\_i ≥ x\_i^2$ (the approximation is tightly constrained from below, only)

Only the third line is quadratic. I include the first two lines in case they make the problem more tractable.

Is this a convex optimization problem? Can it be formulated as a semidefinite program? I see that the regions confining the values of $x\_i^2$ are convex, but I doubt that implies the solution space as a whole is. \[edit: I was wrong; according to @Vincenzo it is indeed that simple.\]

The reason I suspect it might be efficiently solvable is that it seems it can be approximated well (provided the intervals $\[l\_i,r\_i\]$ are small, which they will be in my case) with increasing numbers of linear constraints over the same variables. In particular, each $s\_i ≥ x\_i^2$ is replaced by some $k$ linear constraints defined by

$s\_i ≥$ line tangent to $x\_i^2$ at the point $x\_i = a\_1$

...

$s\_i ≥$ line tangent to $x\_i^2$ at the point $x\_i = a\_k$

where each $a\_t$ is a constant in $\[l\_i,r\_i\]$.

Optional question: In case the set of infeasible such problems is coNP-hard, is there nonetheless some method that is said to work well in practice?

# Answer
The intersection of convex sets is a convex set, therefore the region defined by your inequalities is convex. Essentially, that implies you can solve the problem efficiently within any fixed positive accuracy $\epsilon\>0$.
> 0 votes

---
Tags: complexity-theory, optimization, linear-programming
---


# Question
Title: What is the real advantage of Google's new Fuchsia operating system kernel?
Google's new in-production OS which it desires to replace not only Android but many other devices utilizes a completely new kernel:

> The code differs from Android and Chrome OS due to its being based on the "Zircon" kernel (formerly "Magenta") rather than on the Linux kernel.

https://en.wikipedia.org/wiki/Google\_Fuchsia

> Zircon does not support Unix-style signals and provides no way to directly implement them. Instead, it supports waiting on handles, which can be in a number of different signal states, such as ready for writing, running, stopped, etc. Similarly, Zircon does not have Unix-like fork or exec but uses the launchpad library to create processes.

https://www.infoq.com/news/2018/04/google-fuchsia-zircon-early-look

I've seen demos of Fuchsia by reviewers but these are all just demos of a desktop interface and don't actually describe any of the advantages towards moving to a new platform and the motivation for a building a new kernel.

I see a lot of technical jargon and engineering-speak being thrown around but this isn't anything different from what I hear about every new platform and its super-sauce kernel.

In my opinion, it's *always* been about market penetration and mindshare. Google has a unique advantage in that they have a widespread platform already with Android and **may** be able to strong arm vendors into switching from Android to Fuchsia. But this may also be a re-run of several failed attempts by previous market leaders to do this very thing.

Software compatibility is, in my opinion, a constant when it comes to enticing existing users to move to a new platform. Apple was able to do this gracefully with Rosetta and Windows with NTVDM. I think that it will be very interesting to see how well Android can handle this with so much fragmentation.

So that was a little history and some of my opinion. But my actual question is on what, from a technical standpoint, does Fuchsia's new kernel "Zircon" bring to the table? Creating an entirely new userspace is one thing but swapping out a kernel is a completely other beast. Especially when there is so much existing experience not only for Android but also Linux kernel expertise.

My personal opinion may be dark but I feel that it comes down to licensing and an attempt at increasing vendor lock-in by moving away from Linux; that Google went window shopping and happened upon what became the basis of Zirkon. But this is speculation. What I would like to know is if there is any real technology that brings tangible benefit to all of this work when we already have the venerable Linux kernel available to us?

I would also like to highlight the following source for your reference:

https://fuchsia.googlesource.com/zircon/+/master/docs/concepts.md

I am an applications programmer and don't understand what the benefit is of Zircon's kernel as a design and welcome being educated on how it compares to existing architectures. If Google thinks that it is worthy as the successor of Android's Linux kernel then I feel that there are probably tangible benefits being brought to the table that I am just too inexperienced to appreciate.

# Answer
> 12 votes
From what I understand you are asking what are the technical benefits of zircon over linux?

First of all zircon is a micro kernel as opposed to the linux monolithic kernel. So lets look at some of the advantages of an microkernel over a monolith:

1. Segmentation, a micro kernel has a very segmented model and drivers live outside of the kernel. That means you have more control over what those pesky vendors put into your kernel to slow it down. Security is increased because you can protect the core of the kernels functions from god knows what monster code the vendors wanna chuck in there as drivers.
2. Size, a micro can be way way smaller in size and together with the modularity of the micro kernel can help so you have the same kernel on everything from your phone, laptop to a IoT thermometer.
3. Speed, although in practice you have a lot of microkernels that are slower than monoliths because all the communication between the pieces of the kernel create a lot of overhead, you could have speedier communication with things like File I/O, network traffic and other components by the lack of context switching between kernel space and user space (think \>10Gbps networks).
4. Control over updates. One of the biggest problem with Android is fragmentation, if you wanna build an app you have 839274326 versions of Android out there, for which version do you build your app? Also you have vendors not applying patches because they need to build their version with all the modifications they put in. If you had a really segmented core that you could update without affecting the vendor modifications that would be a big win for Google.
5. Real-time operation, they probably want a pure real time implementation because it goes well with their data collection needs.

---
Tags: operating-systems, os-kernel
---


# Question
Title: Complexity classes: What if different algorithms exist for different sizes of input?
If I understand(\*) correctly, a decision problem is some function $f(x)$ whose function argument $x$ can be represented by data of a limited length (e.g. not an irrational number) and whose value is either 0 or 1.

If there exists some algorithm which can calculate the function value $f(x)$ in less than $\sum\_{i=0}^{i\_\text{max}}K\_in^i$ steps (while $i\_\text{max}$ and $K\_i$ are constant) for every function argument with a length of $n$ (bits, bytes, digits, characters...), the decision problem belongs(\*) to the complexity class $P$.

**My actual questions:**

Let's say for every "length" $n$ there is an algorithm that takes less than $\sum\_{i=0}^{i\_\text{max}}K\_in^i$ steps to calculate $f(x)$ for a function argument $x$ which has a length of exactly $n$ (bits, bytes, ...).

(However, these algorithms do not necessarily work for every function argument $x$, but depending on the "length" $n$ of the function argument $x$ we have to use different algorithms.)

* Would this imply that there exists **one single** algorithm that can calculate $f(x)$ for any argument $x$ in polynomial time?
* If the answer is "no": Would the decision problem belong to the complexity class $P$ or not?
* If either of the two answers is "yes": How is the situation in other complexity classes than $P$?

---

(\*) Please excuse me if I use wrong terminology or my premises are wrong. I'm not a mathematician and my interest about complexity theory comes from the field of computing device development.

# Answer
What you are describing is *non-uniform* algorithms. You have to be careful when defining them. For example, consider the following algorithm, for inputs of length $n$:

> Look up the answer in a large table.

If this algorithm runs in polynomial time in your model, then the non-uniform version of your computation model can compute all decision functions.

There are two common ways to define non-uniform computation models in complexity theory: using advice and using circuits.

**Advice.** One possibility is to have a uniform algorithm (working for all input lengths) which gets an additional "advice" which only depends on the input. Let's see how such an algorithm can efficiently decide the following language:

$$ L\_H = \\{ w : \text{the $|w|$th Turing machine halts on the empty input} \\}. $$

(Here $|w|$ is the length of $w$.)

The algorithm gets an auxiliary advice $a\_n$, and just returns $a\_n$. The advice $a\_n$ is simply whether the $n$th Turing machine halts on the empty input. Incidentally, this example shows that non-uniform models can compute uncomputable functions.

One standard complexity class which can be defined in this way is $\mathsf{P/poly}$, which consists of all decision problems computable by polynomial time algorithms having access to a polynomial size advice.

**Circuits.** Cook's theorem shows (essentially) that if $L$ can be decided in polynomial time, then for every $n$ we can construct a polynomial size circuit deciding the length $n$ instances of $L$. These circuits are uniform in the sense that they can be constructed by an algorithm.

This suggests the following natural non-uniform model: polynomial size circuits. In this model, for every input length we can supply an arbitrary polynomial size circuit (that is, there is a polynomial $p(n)$ such that the $n$th circuit has size at most $p(n)$). Every problem in $\mathsf{P}$ can be decided in this model, as mentioned above. But this model is much more powerful — indeed, it can compute the uncomputable language $L\_H$ mentioned above: the $n$th circuit either computes the constant 0 function or the constant 1 function. It turns out that this circuit model is exactly equivalent to the class $\mathsf{P/poly}$ defined above.

Non-uniform models of computation are important in complexity theory, since many lower bound techniques apply directly to them. For example, one approach for proving $\mathsf{P} \neq \mathsf{NP}$ which used to be popular is proving superpolynomial lower bounds for circuits computing some NP-complete problem such as $\mathsf{SAT}$. Nowadays this approach seems less promising. But various weaker non-uniform models are the object of intensive study in complexity theory.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Verifier for A_tm in polynomial time - how to formally prove it does not exist?
How would you formally prove the non-existance of a polynomial time verifier for $A\_\mathrm{TM}$?

I mean we can't just say that in order to read a certain certificate we need more than poly-time because we need to prove it for **any possible** certificate. What would be the correct proof ?

# Answer
> 2 votes
Suppose by contradiction $A\_\mathrm{TM}$ has polytime verifier $\Longrightarrow$ $A\_\mathrm{TM}$ is in NP $\Longrightarrow$ $A\_\mathrm{TM}$ is decideable by some non-deterministic TM in polytime $\Longrightarrow$ $A\_\mathrm{TM}$ is dcidiable by some deterministic $2^{\mathrm{polytime}}$ TM $\Longrightarrow$ $A\_\mathrm{TM}$ is decidable $\Longrightarrow$ contradiction.

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


# Question
Title: How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.

$L\_1$ and $L\_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\\{σ\_1σ\_2...σ\_n\mid n\ge1, \sigma\_1, \sigma\_2, \cdots, \sigma\_n\in \Sigma, \\ &\exists \mu\_1, \mu\_2,\cdots,\mu\_n,\zeta\_1,\zeta\_2,\cdots\\, \zeta\_n \in\Sigma, \\ &\mu\_1\mu\_2\cdots\mu\_n\in L\_2,\sigma\_1\mu\_1\zeta\_1\sigma\_2\mu\_2\zeta\_2...\sigma\_n\mu\_n\zeta\_n\in L\_1\\}\\ &\cup\\{a\mid a\in L\_1, a\in L\_2, a=\epsilon\\}\end{align}$$ where the second set on the right hand side just says that $\epsilon\in L^\wedge\Leftrightarrow \epsilon\in L\_1\land \epsilon \in L\_2$.

How can we prove $L^\wedge$ is regular using closure properties or a product automaton?

What i tried to do is:

Since $n \geq 0$, we can build $\Sigma^\* = \\{ \sigma^\* | \sigma \in \Sigma \\} $ $(\Sigma \cup \Sigma) \to \Sigma^\*$, then for some function h we can assign $h(\sigma)=\sigma$ (also $h(\sigma')=\sigma$), so because of homomorphism $h^{-1}(L\_1 \cup L\_2) = \\{ \sigma\_1...\sigma\_n |\forall 1 \leq i \leq n \to \sigma\_i \in \\{ \mu\_i,\mu\_i' \\}, \mu\_1...\mu\_n \in L\_1 \cup L\_2 \\} $,

So if $(L\_1 \cup L\_2)' = h^{-1}(L\_1 \cup L\_2) \cap ( \sigma'\Sigma \Sigma')\*=\\{ \sigma\_1'\sigma\_2\sigma\_3'...\sigma\_{n-2}'\sigma\_{n-1}\sigma{n}' | \sigma\_1... \sigma\_n \in (L\_1 \cup L\_2)$ is also regular

So if for some function $f$, $f(\sigma)=\sigma$ and $f(\sigma')=\epsilon$ $(f|f:(\Sigma' \cup \Sigma) \to \Sigma^\*)$

Then $f(L\_1' \cup L\_2') = \\{ \mu\_1...\mu\_n | σ\_1μ\_1ξ\_1...σ\_nμ\_nξ\_n∈L\_1 \cup L\_2 = L^∧$ and if regular because of regular languages closure to homomorphism

I know it’s complicated and would appreciate help with it, seeing how to do it correctly (pretty sure I've made some mistakes along the way).

# Answer
> 2 votes
Let me point you to the proper tools.

The operation of (perfect) shuffle takes two languages $K,L\subseteq \Sigma^\*$ and alternatingly takes a symbol from one of them:

$sh(K,L) = \\{ a\_1b\_1a\_2b\_2 \dots a\_kb\_k\mid k\ge 0, a\_i,b\_i\in\Sigma,\text{ where } a\_1a\_2\dots a\_k\in L\text{ and } b\_1b\_2\dots b\_k\in K \\}$

This operationhas been discused various times, using both automata and closure properties: Proving regular languages are closed under a form of interleaving, Show that regular languages are closed under Mix operations, and Closure of regular languages to shuffle using closure operations, but probably more.

Then there is the kind-of reverse of this operation, given a language $K\subseteq \Sigma^\*$, keep every second letter of its strings:

$2nd(K) = \\{ a\_2a\_4 \dots a\_{2k} \mid k\ge 0, a\_i\in\Sigma,\text{ for some } a\_1a\_2\dots a\_{2k}\in K \\}$

An example for that is is: If L is regular, show that even(L) is also regular. Both solutions there are enlightening.

Also in your case one needs some shuffling (to move the letters from $L\_2$ within two other letters in order to compare with $L\_1$) and some unshuffling (to keep every first letter of three for $L^{\land}$) but now with three letters/languages rather than two.

# Answer
> 1 votes
Here is a solution using NFAs. Let $A\_1,A\_2$ be DFAs for $L\_1,L\_2$. We will construct a new automaton whose states are $Q\_1 \times Q\_2 \times \\{1,2,3\\}$. The accepting states are $F\_1 \times F\_2 \times \\{1\\}$. The initial state is $(q\_{01},q\_{02},1)$. The transitions are as follows:

* $\delta((q\_1,q\_2,1),\sigma) = \\{ (\delta\_1(q\_1,\sigma),q\_2,2) \\}$.
* $\delta((q\_1,q\_2,2),\epsilon) = \\{ (\delta\_1(q\_1,\sigma), \delta\_2(q\_2,\sigma), 3) : \sigma \in \Sigma\\}$.
* $\delta((q\_1,q\_2,3),\epsilon) = \\{ (\delta\_1(q\_1,\sigma),q\_2,1) : \sigma \in \Sigma \\}$.

I'll let you figure out why this works.

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


title: Wifi throughput calculation

text:
# Question
Title: Wifi throughput calculation
I have a problem which i don't know how to calculate or more specifically what am I missing. The subject is about 802.11 (wifi)

The selected PHY rate is 54Mbit/s, that is whenever DATA is being sent the rate is 54Mbit/s, and when the node is not sending anything the rate is 0. To simplify the task, assume that there are no collisions and no errors in the channel.

The frames in the figure are marked up as follows:

Message Purpose Duration, us RTS Request to send 44 CTS Clear to send 48 DATA Payload packet Variable ACK Acknowlegement 44 SIFS Inter-frame-spacing 4 DIFS Same as SIFS 16 Backoff MAC arbitration 0..63

The question is: What would be average effective throughput (in Mbit/s) with basic signaling if the DATA packet takes 166 microseconds? Write your answer as average effective bit rate for whatever is being put into DATA packets. Allowed error is 2%

What am I missing?

# Answer
Okay so I managed to solve it.

It was simply: PHY rate * (DATA time / Access cycle time, where backoff = 30us)
> 0 votes

---
Tags: computer-networks
---


title: Functional Dependencies

text:
# Question
Title: Functional Dependencies
Let relational schema R(A,B,C,D,E,F,G,H,I).

The functional dependencies are: A -\> BC, AD -\> BE, C -\>F , A-\>F , D-\> E

Find the number of non-trivial functional dependencies ? I know that R has only five non-trivial functional dependencies but i do not know how to prove this(How to think)?

# Answer
> $R$ has only five non-trivial functional dependencies (FDs).

No, $R$ has many more non-trivial FDs. For example, Since A-\> BC and C -\> F, we also have AC-\>BF, which is also a non-trivial FD although not a irreducible FD.

What you can say is that all given 5 FDs are non-trivial FDs, since for each given FD, the dependent set is not a subset of the the determinant set.

If you want to see all non-trivial function dependencies of $R$, you have to obtain the dependency closure of the given FDs, following, for example, the procedure given here using Armstrong's axioms.

> Step-1 : Add the attributes which are present on Left Hand Side in the original functional dependency.
>
> Step-2 : Now, add the attributes present on the Right Hand Side of the functional dependency.
>
> Step-3 : With the help of attributes present on Right Hand Side, check the other attributes that can be derived from the other given functional dependencies. Repeat this process until all the possible attributes which can be derived are added in the closure.

You can enter `R(A,B,C,D,E,F)` and `A -> B,C; A,D -> B,E; C ->F ; A->F; D-> E` into the first two fields on this page. Hit the "Calculate" button and view the result. It will list a lot of related concepts. In particular, it shows the following 43 non-trivial FDs.

```
A → B,C,F
C → F
D → E
A,B → C,F
A,C → B,F
A,D → B,C,E,F
A,E → B,C,F
A,F → B,C
B,C → F
B,D → E
C,D → E,F
C,E → F
D,F → E
A,B,C → F
A,B,D → C,E,F
A,B,E → C,F
A,B,F → C
A,C,D → B,E,F
A,C,E → B,F
A,C,F → B
A,D,E → B,C,F
A,D,F → B,C,E
A,E,F → B,C
B,C,D → E,F
B,C,E → F
B,D,F → E
C,D,E → F
C,D,F → E
A,B,C,D → E,F
A,B,C,E → F
A,B,D,E → C,F
A,B,D,F → C,E
A,B,E,F → C
A,C,D,E → B,F
A,C,D,F → B,E
A,C,E,F → B
A,D,E,F → B,C
B,C,D,E → F
B,C,D,F → E
A,B,C,D,E → F
A,B,C,D,F → E
A,B,D,E,F → C
A,C,D,E,F → B

```
> 1 votes

# Answer
To distinguish trivial and non-trivial functional dependencies first check if the dependent is subset of determinant or not if dependent is subset(not necessary a proper subset) then it is trivial dependency otherwise the functional dependency is non-trivial.successively you can count the number of functional dependencies whether trivial or non-trivial.For example:- A functional dependency X-\> Y id non-trivial if Y is not a subset of X.
> 0 votes

# Answer
I think you are asking not for how many *"non-trivial functional dependencies"* there are in the relation, but how many *"dependencies"* there are in the canonical cover of these 5 dependencies (let's call the set of these 5 dependencies $F$ ).

If that is the case, then you can compute the canonical cover of $F$ using the algorithm given on that page and count the number of dependencies in it.

You can refer to this and this if you are unclear about any of these concepts, e.g., what is meant by an *"extraneous"* attribute, or what the *"closure"* of a set of functional dependencies means.
> 0 votes

---
Tags: databases, functional-dependencies
---