11
First, the string of minimum length might not be defined properly since it might not be unique.
Here is a way to find a string of minimum length:
Convert the regular expression to a nondeterministic finite automaton.
Convert the nondeterministic automaton into a deterministic one.
Use a breadth first search until you encounter the first nonfinal state (if ...
8
Your reasoning is incorrect.
It is true that your hypothetical "proof deriver" cannot derive all true statements. No proof derivation system can, and indeed, it is not even possible to express the set of true statements in arithmetic, which is a consequence of Tarski's theorem on truth, itself a consequence of Gödel's theorem.
However, your algorithm does ...
6
Your basic idea (in particular the choice of $t$) works, but there are some issues with the "proof" as such:
What is $n$?
Why do you have $y=b$ have to be pumped? You have to work against all allowed decompositions of $t$!
$n+i < n+2$ does indeed not work for all $i$, but that's kind of the point. Just drop that condition.
I suggest you read our ...
6
This is similar to the recurrence arising in the analysis of Quicksort, search for "quicksort analysis" to get lots of results.
An easy road is to write:
\begin{align}
(n + 1) T(n + 1) &= 2 \sum_{0 \le k \le n} T(k) + (n + 1) c \\
n T(n) &= 2 \sum_{0 \le k \le n - 1} T(k) + n c
\end{align}
Subtract to get:
$$
(n + 1) T(n + 1) - (n + 2) T(n)...
6
Your idea is correct.
You should take the following path to formally write it up/prove it. First assume that $L$ is accepted by some DEA $M=(Q,\Sigma,\delta,q_0,F)$ then define a new NEA $M'=(Q',\Sigma,\delta',q'_0,F')$ based on $M$. Just express you ideas formally, for example start with
$Q'=Q\cup\{q_\text{new1},q_\text{new2}\}$,
$F'=\{q_\text{new2}\}$,
...
5
Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:
Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.
Not every AVL tree satisfies this condition, for example the Wikipedia example doesn't.
5
your answers look good.
To do this properly, it might helpful to convert the expression into the equivalent language (i.e., using English words to describe it), however, for certain expressions this language will be very complicated.
Another "algorithmic" way is to convert it to a DFA/NFA, and then check all the strings lexicographically, until you find ...
5
To make life simple, assume $T(1)=1$. If we look at this just for integral powers of $k$, i.e. $n=k^m$ for some $k \in \mathbb Z$, we have, by definition,
$$
T(k^m)=kT(k^{m-1})+ck\cdot k^m
$$
We can repeatedly substitute into the recurrence to get:
$$\begin{align}
T(k^m)&=k\cdot{\color{red}{T(k^{m-1})}}+ck\cdot k^m\\
&=k\cdot{\color{red}{[k\cdot T(k^...
5
You can compute $S\setminus T$ and $T\setminus S$ from $S$ and $T$ in $O(n+m)$ time using a hash table. Put all of list $S$ into a hashtable, and then iterate through list $T$ and look it up in the hashtable. Then do the same, with $T$ in the hashtable and iterating through $S$.
Fine print for complexity purists: this is expected running time, making ...
4
If $f = O(g)$, then
$$\exists n_0. \exists c. \forall n. (n > n_0 \rightarrow f(n) \le c g(n))$$
The negation of this statement is
$$\forall n_0. \forall c. \exists n. (n > n_0 \land f(n) > c g(n))$$
This doesn't match your negation, so I believe your proof is incorrect.
I actually think the statement you're trying to prove is false. Try ...
4
Stirling's approximation states that
$$ n! \sim \sqrt{2\pi n} (n/e)^n. $$
This notation means that the ratio between the two sides tends to 1 as $n$ tends to infinity. For your purposes, we can simply write
$$ n! = \Theta(\sqrt{n} (n/e)^n). $$
Since $\sqrt{n} = o(e^n)$,
$$ n! = o(n^n). $$
If all you want to show $n! = O(n^n)$, then as Jukka mentions you can ...
4
It is hard to answer this question since it is hard to find a formal statement of Rabin's compression theorem. Here is one from the book Complexity Theory and Cryptology: An Introduction to Cryptocomplexity by Jörg Rothe, page 63:
For each time constructible function $t(n)$ there exists a decidable set $D_t$ such that each deterministic Turing machine $M$ ...
4
Your invariant, together with the negation of the loop condition, is not strong enough to imply your postcondition. Try adding an additional conjunct to the invariant which, together with $\neg\ i<10$, implies $i=10$ (the $j=-1$ part then follows from $i+j=9$).
4
An alternative solution still using domain transformation/change of variables.
$$T(n) = T(\sqrt{n}) + \log \log n$$
1. Let $m = \log n$
We can then define a new function $S$ based on how $m$ changes in $T$ and expand it:
$$\begin{align}
S(m) &= S\left(\frac{m}{2}\right) + \log m\\
&=S\left(\frac{m}{4}\right) + \log m -1 + \log m\\
& \vdots\\
&...
4
You seem to think the structure of the proof is:
suppose the algorithm is incorrect;
prove that the algorithm is, in fact, correct;
this contradicts 1., so the algorithm is correct.
That's almost, but not quite true. Step 2 doesn't prove that the returned value $\mathrm{max}$ is bigger than every element of the array, which is what would be required to ...
4
You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again.
To repeat, it is correct that "the cost $c_1=1$, $\Phi_0=0$", "$num_1=size_1=1$ $\implies$ $\Phi_1 = 2\cdot1-1 =1$" and " $\hat{c_1}=$ $c_1+\Phi_1-\Phi_0$ $=2$". It is incorrect to state that $\widehat c_i=...
3
We can expand the recursion (ignoring the constant 10) as follows:
$$
\begin{align*}
T(n) &= \log \log n + \log \log n^{1/2} + \log \log n^{1/4} + \log \log n^{1/8} + \cdots \\ &=
\log \log n + \log \frac{1}{2} \log n + \log \frac{1}{4} \log n + \log \frac{1}{8} \log n + \cdots \\ &=
\log \log n + (\log \log n - \log 2) + (\log \log n - \log 4) + ...
3
Here is a simple counterexample:
$$
\begin{align*}
&f(2m) = 2^{2^{4m}} & &g(2m) = 2^{2^{4m+1}} \\
&f(2m+1) = 2^{2^{4m+3}} & &g(2m+1) = 2^{2^{4m+2}}
\end{align*}
$$
The first few values (starting at $0$) are
$$
f = 2^{2^0}, 2^{2^3}, 2^{2^4}, 2^{2^7}, 2^{2^8}, 2^{2^{11}}, \ldots \\
g = 2^{2^1}, 2^{2^2}, 2^{2^5}, 2^{2^6}, 2^{2^9}, 2^{2^{...
3
Thanks for the clarification! I really misinterpreted your question.
Okay, so we have the computable function $f$, the also computable function $F$ that is based on $f$, and the Turing machine $M_F$ with the following behavior:
when started with a tape with $y$ $1$'s, writes a block of $F(y)$ $1$'s to the right, separated by at least one blank
Note that ...
3
You have made significant progress on this problem. Your final conclusion, "the overall algorithm asymptotically requires $\Omega(n^2)$ steps" is likely to be correct as well.
Analysis of Your Argumentation
Here are some unclear or unconventional or inconsistent notations found in your post, which makes it difficult to understand or justify your arguments ...
3
In this context, lexicographic order means:
First order by length.
Within each length, order lexicographically.
You're saying that the proof is incorrect, but in fact it is only inaccurate in that the order is not quite the lexicographic order. I would say that the proof has a small mistake, but is otherwise correct.
One often encounters such small issues ...
3
It's a proof by contradiction that could easily be rewritten as a direct proof.
To rephrase it as a direct proof, we divide it into two claims:
$max$ is an element of $A$.
$max \geq A[j]$ for all $j$.
We can conclude that $max = \max(A)$.
3
The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$.
Instead of looking at the leaves, you should look at the root of the tree: since the tree is perfect, it has two children of size $2^{h-1}-1$ (this is how $C_{h-1}$ appears). You just ...
3
$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$
so
$\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$
3
This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain this remarkable and beautiful argument, from many viewpoints.
Still, to answer your question: denote by $Q$ the program you describe. Then $Q$ is a valid ...
2
The nature of the answer depends on what you are attempting to optimize (e.g. computation, communication, interactivity) and the computational model (e.g. deterministic, probabilistic,distributed/centralized).
In the case where the two sets are on remote devices, this problem is known as the set reconciliation problem, or more generally the data ...
2
The solution in the question is correct.
The constraint $i\ne j$ is the one that gives us trouble. To get around it we have to split into two cases: (i) $i<j$, and (ii) $i>j$ (but still $i<2j$)
thus
$S\to S_{(i)} \mid S_{(ii)}$
as the first production splits into this two cases.
Now, divide and conquer: case (i) is very simple, since we only ...
2
There is a trivial $O(kn^2)$ algorithm:
Choose a vertex $v$ and calculate its degree $k$. Then verify that all other vertices have degree $k$.
Choose some neighbor $w$ of $v$ and calculate the number of common neighbors $\lambda$. Then verify that all other pairs of adjacent vertices have $\lambda$ common neighbors.
Choose some non-neighbor $x$ of $v$ and ...
2
Here's an explicit construction of $f$ and $g$ such that neither $f=O(g)$ nor $g=O(f)$. To make the calculations slightly easier, I've chosen $g$ to be increasing and $f$ to be nondecreasing (namely, $f$ will be a step function), but one can follow the technique and tweak $f$ so that it's increasing, as well.
First, let $g(n)=n$. Construct $f$ as follows:
...
2
You are missing something.
If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the numbers in the purported factorisation are primes.
Fortunately there is theorem that for every prime number, there is a polynomial time proof that it is a ...
Only top voted, non community-wiki answers of a minimum length are eligible
