4

Just for fun, I've constructed the TM sketched by Rodion, you can simulate its behaviour here. Observe that I assume $p$ (or $m$, which is the same) strictly positive; moreover one actually has to use two cells outside the input, namely the cell immediately to the left of the first symbol of the input and the one immediately to the right of the last symbol ...


4

This problem can be solved in two steps. First, you need to work out the $k$ by repeatedly "dividing" the string by $3$, and storing how many times this was repeated. For example, each "division" will process the zeros in triplets. Each triplet will replaced by one zero, and in the first triplet processed you store a "1", as an ...


3

Obviously, $f(n)+o(f(n))=\Omega(f(n))$ (clearly, I'm assuming all functions being positive), so you need only to prove that $f(n)+o(f(n))=O(f(n))$. But a function in $o(f(n))$ is definitevely smaller than $f(n)$, so for sufficient large $n$ you have $f(n)+o(f(n))\leq 2f(n)=O(f(n))$. Actually, in the same way you can easily prove also this stronger claim: $f(...


2

It's widely known, that $f=\Theta(g)$ we understand as "one direction" equality i.e. $f \in \Theta(g)$. But when we write something like $\Theta(f) = \Theta(g)$, then situation becomes slightly different: now it is equality between sets, so need proof in "two directions". Equality $f+o(f)=\Theta(f)$ formally considered as equality between ...


2

There sure is. Some sort of backtracking program will do the job. If you want the minimal number of moves, perhaps the (memory expensive) way to go is breadth first search. Maybe you can squeeze some performance out of it by adding conditions to cut off impossible branches or stop expanding when the current path is longer than the current best, or heuristics ...


1

Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that: $n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$ i.e. $n_0 = 1 + n_2 + 2n_3 + ...$ I think there is a small mistake here, since $n_j$ should be considered as the number of symbols of degree $j$ and not of degree $d_j$ in $\alpha$. $n_0 + n_1 +...


1

This is a very simple question, I will explain steps-by-steps: First, you need to count total elements and total comparisons in your tree Second, you need to know that for each element in the tree, it takes $\frac{total \ comparisons}{total \ elements}$ average comparisons to search for an element in the tree. Third, if the problem gives you a probability to ...


1

The Dense Subgraph Problem (thanks @PalGD) is a special case of the above problem--with no node weights and unit edge weights. See the solutions for the dense subgraph problem here. These solutions (LP and 2-approximation Greedy) easily generalize to the above problem (generalizing LP requires a bit of understanding/effort, but generalizing Greedy is trivial)...


1

For bit #k to be set in the output, you need to arrange the numbers so that bit #k is either set in a[i] and cleared in c[i] or the other way round. Therefore bit #k must be set in exactly n of your 2n inputs. If that is not the case then bit #k cannot be set in the output. So first you determine all k such that bit #k is set in exactly n of the 2n inputs, ...


1

From a brief look at Leetcode streaming problem solutions, the complexity solutions provided for streaming problems refer to the time complexity of a single iteration for the stream i.e. after $n$ elements in the stream, what is the complexity of updating the data structure and answering a query with a new element?


1

It depends on the definition of in-place algorithm you are using. if in-place just means that the algorithm transforms the input without returning a new array, then yes; if you also want to use no additionnal data structure, or limit the additionnal space usage to be $o(n)$, then no, because of the creation of the arrays count and output. There are ...


1

We need to first find the length of array in long time as it is not given. Start with length as 1 and increase it as multiple of 2. Check whether element at length-1 position is positive or not. If so repeat steps 1 and 2. If not return the index position it will be the maximum size of the array. As it is mentioned beyond the maximum position element value ...


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