New answers tagged recursion
0
Wikipedia is being sloppy. The procedure returns all LCSs of $X[1..i]$ and $Y[1..j]$, which corresponds to $C[i,j]$. It should mention that in order to obtain all LCSs, we need to set $i=m$ and $j=n$.
If $X[i] = Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ is obtained by taking an LCS of $X[1..i-1]$ and $Y[1..j-1]$, and adding to it $X[i] = Y[j]$.
If $X[...
0
Quoting Introduction to Algorithms:
The easy case occurs when $j = i-1$. Then we have just the dummy key $d_{i-1}$.
The expected search cost is $e[i,i-1] = q_{i-1}$.
In slightly more detail, $e[i,j]$ is supposed to be the cost of the optimal binary search tree for $k_i,\ldots,k_j$. It is important to understand what cost means here. The cost is with ...
0
Taking $n=2^k$, we have
$$T(n)=2T\left(\frac{n}{2}\right)+f(n)=\\=2\left[2T\left(\frac{n}{2^2}\right) +f(n)\right]+f(n)=2^2T\left(\frac{n}{2^2}\right)+2f(n)+f(n)=\\=2^3T\left(\frac{n}{2^3}\right)+2^2f(n)+2f(n)+f(n)=\cdots=2^kT(1)+f(n)[2^{k-1}+\cdots+1]=\\=2^kT(1)+f(n)(2^k-1) = nT(1)+f(n)(n-1)$$
Now we have 2 cases: 1. $T,f$ are defined only for $2$s powers ...
0
I feel like this is basically paraphrasing the explantion in CLRS but maybe it will help.
Let $j$ be the length of the leftmost rod piece in an optimal solution. This piece has a cost of $p_j$ and so it contributes exactly that much to the total revenue. It is easy to see that the remaining part of the rod (of length $n-j$) must be divided up in an optimal ...
3
This problem is equivalent to Perfect Matching
We can view the input as an almost-complete graph, with L as its vertices and every two vertices connected by an edge except for those in C. We then want to find a set of edges that uses every vertex exactly once. This is the perfect matching problem.
To solve this problem, you can use any algorithm for finding ...
0
Here is an argument by substitution:
$$\begin{aligned}
T(n) &= 3T(n/2)+2n \\&= 3(3T(n/4)+n)+2n \\&= 3(3(3(T(n/8)+n/2)+n)+2n \\&= \cdots \\&= 3^kT(n/2^k)+\sum_{i=0}^{k-1}{2n\left(\frac{3}{2}\right)^i} \\&= 3^kT(n/2^k)+2n\frac{\left(\frac{3}{2}\right)^k-1}{\left(\frac{3}{2}\right)-1} \\&= 3^kT(n/2^k)+4n\left(\frac{3}{2}\right)^k-4n
\...
1
The candle burning rules are as follows: if you have c>=m candles, you can remove (m-1) of them and score m points while doing so. If you have fewer than c<m candles, then you score c points and are then done.
The total number of points you can score are then the points you score at the end (c % (m-1)), and the number of points you score before then (m ...
0
In order to prove the closed form you have to think in a different way about the consuming $m$ candles and adding a new one. Notice that if you break down the $(n-1)//(m-1)$ part into an iterative approach you basically subtract $m$ raise your counter of possible candles by $1$ and add $1$ back to the number you subtracted from, hence you don't subtract $m$ ...
Top 50 recent answers are included
