# Tag Info

3

Note that, when we compute binary addition of two binary strings $|A|=n,|B|=m$, we read $n+m$ bits. On the other hand the time complexity of computing the addition of two bits, are $\mathcal{O}(1)$, so we do $n+m$ additions that each of them needs $\mathcal{O}(1)$ time. As a result, the time complexity is $$\mathcal{O}(n+m).$$ Remember that, $A+B$ need at ...

3

No you can't. Consider any set $S=\{a,b,c\}$ with $a+b+c=0$, and the set $S'=\{a+b,b+c,c+a\}$. The subset sums for $S$ are $0, a, b, c, a+b, b+c, c+a, a+b+c=0$. The subset sums for $S'$ are $0, a+b, b+c, c+a, a+2b+c=b, b+2c+a=c, c+2a+b = a, 2(a+b+c)=0$. Hence, you can't distinguish $S$ and $S'$ from the subset sums: $0, a, b, c, a+b, b+c, c+a, 0$. If all ...

2

You can solve your problem with $O(n)$ queries. Let $Q(i,j)$ denote the result of a query on $A[i,j]$. This upper bound on the number of queries is trivial since you can always reconstruct $A$ with $n$ queries $Q(i,i)$ for $i=1,\dots,n$ and then solve your problem on $A$ with any algorithm (regardless of its running time). The following greedy algorithm ...

2

Your problem statement is unclear, but under reasonable assumptions: No. You can't. If the input is an infinite sequence, you can't solve it in any finite time. To put it another way, suppose you have an algorithm that terminates after some fixed amount of time. Now consider feeding in the input [5,5,5,5,..] to the algorithm. Presumably, you want it to ...

1

Your question is very broad and has possibly hundreds of answers depending on the interpretation. The fact you tagged it with "formal-languages" and "formal-grammars" suggests you are actually asking "how the syntax of a language describing this kind of stuff should look like". Sometimes, reading your question I feel you are ...

1

Run BFS and traverse only edges with weight $1$, now if the graph isn't connected, then add edges with weight $2$ to traversed graph until your graph form a tree. The running time is $\Theta(E+V)$. Note that you can also use Dijkstra that in this case has linear running time...

1

For every edge $(u,v)$ with weight $2$, create a new node $w_{u,v}$. Discard the edge $(u,v)$, and instead of it add two edges $(u,w_{u,v})$ and $(w_{u,v},v)$ with weight $1$. Now you can use a standard unweighted pathfinding algorithm, such as BFS.

1

If $m,n>=0$, then $\max(m,n)<=m+n<=2\max(m,n)$. So $O(\max (m,n))$ and $O(m+n)$ are the same; the two expressions are within a constant factor of each other.

1

Suppose that no symbol has frequency $0$ (otherwise the claim is false). Consider the tree $T$ built by the standard greedy algorithm to construct the Huffman code. This algorithm maintains a forest $F$ where each node $v$ is associated with a frequency $f_v$. Initially $F$ contains a collection of isolated vertices, one per input symbol (with the ...

1

I eventually found the solution for the first problem I proposed. Lemma 10.5.3.2 CAN be proved by induction, but it requires additional lemmata for doing so. I was misled by the note on page 292, specifically by the mention of "strengthening". It is common to say that a theorem is strengthened when its inductive hypothesis is rewritten to hold in ...

1

Let $f_k(n)=\log_kn$,$k>2$, and let $t(n)=\log_2n$. You can rewrite $f_k(n)$ as follow $$f_k(n)=\frac{\log_2n}{\log_2k}$$ Now $k$ have two states: $k$ is constant: $$\lim_{n\to \infty}\frac{f_k(n)}{t(n)}=\lim_{n\to \infty}\frac{\frac{\log_2n}{\log_2k}}{\log_2n}=c$$ that $c$ is a constant$>0$, hence $$t(n)=\Theta(f_k(n)).$$ So there is no difference ...

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