Tag Info

2

In this answer, whenever I say "function," I mean a positive real-valued function on the natural numbers $\{1, 2, 3, \ldots\}$. Big-O notation is a way to compare the growth rates of functions as their arguments go to infinity. Let's define a relation $\preccurlyeq$ between functions by saying that $f \preccurlyeq g$ if the ratio $\frac{f(n)}{g(n)}$ remains ...

1

To answer your second question first: yes, it is allowable to simplify $3^{2n}$ to $9^n$. Recall that $f\in \mathcal O(g)$ iff: $$\limsup_{x\to\infty}\frac{f(x)}{g(x)} = c,\quad 0\leq c < \infty$$ Letting $f(x) = 10^x$ and $g(x) = 9^x$, and taking the limit: \begin{align} \limsup_{x\to\infty}\frac{f(x)}{g(x)} &= ...

1

You’re having trouble because $L$ is regular. If by $\Bbb N$ you mean the set of non-negative integers, then $L=\Sigma^*$, because any word $w\in\Sigma^*$ can be written in the form $a^0wb^0$, where $|w|\ge 0$. If by $\Bbb N$ you mean $\Bbb Z^+$, the set of positive integers, then $$L=\left\{awb\in\Sigma^*:|w|\ge 1\right\}\;,$$ which corresponds to the ...

1

For a more concrete example, if our alphabet is $\{a, b\}$ then the set of words where the number of $a$'s and $b$'s is equal, say $E$, is non regular. But, $(ab)^*$ is a regular subset of $E$. But, you can just as easily imagine another, non regular subset of $E$. For instance, those words in E where the number of $b$'s never exceeds the number of $a$'s in ...

1

Hint: Suppose you have an automata for $\mathcal L_1$. Duplicate its set of states and send the letters between them in both directions.

1

$\exists c_1, c_2, c_3= c_1 c_2$ s.t. $f(x) \leq c_1 g(x) \leq c_1 c_2 h(x) \rightarrow f(x) = O(h(x))$.

1

No, this is wrong. Your tree is not in sorted order. Notice that you have 15 to the left of 12.

1

You should take a look at the diagrams on Wikipedia which show you how the heights of the subtrees involved change, which will then tell you why you need to use the rotations for the RL case. If you use only one rotation, that middle subtree will stay at the same height and it will remain unbalanced. Don't simply memorize which case it is supposed to be ...

1

I can compute $DP[i][j][k]$ in $O(N^2)$. To see this, note that the first term of the summation ($DP[i][m][0]$) can always be computed in $O(1)$, and the second term of the second term of the summation ($j$ from $DP[m+1][j][k-1]$)... is always $j$. ...assuming everything is memoized, of course.

1

Take two tasks next to each other. Perform $i$ then $j$, you will pay $p_id_i+p_j(d_i+d_j)$. Perform $j$ then $i$, you will pay $p_i(d_i+d_j)+p_jd_j$. The other costs are unchanged. The sign of the difference $p_id_j-p_jd_i=\left(\frac{d_j}{p_j}-\frac{d_i}{p_i}\right)p_ip_j$ tells you to swap or not. If you keep doing this until there are no more ...

1

Since $f(x) = O(g(x))$, we have $|f(x)| \leq c \cdot |g(x)|$ for all $x \geq n_{0}$. Similarly, $|g(x)| \leq k \cdot |h(x)|$ for all $x \geq m_{0}$. So take $|f(x)| \leq ck \cdot |h(x)|$ for all $x \geq max\{n_{0}, m_{0}\}$.

1

Hint: the complement of a regular language is regular. Can you prove that there's a/no way to construct a regular expression/finite state automaton that describes/accepts all strings in the English language?

Only top voted, non community-wiki answers of a minimum length are eligible