# Tag Info

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 consumingm$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\$ ...