[CLRS 23.1-6] Unique Light edges lead to a unique spanning tree

23.1-6 [CLRS]:Show that a graph has a unique minimum spanning tree if, for every cut of the
graph, there is a unique light edge crossing the cut. Show that the converse is not
true by giving a counterexample.

Here, let's use the theorem 23-1, according to which we can select $A$ to be a subset of $E$, the set of edges that is included in some minimum spanning tree. Then,
Hypothesis-1 : We can always make $A$ such that it can respect any cut $(S,V-S)$.
Eventually, that is very easy to do. We can just ignore all the edges that lie on the cut (that is, connect the two components produced by the cut), and put the rest of the edges into $A$. This leads to an $A$ that respects the underlying cut.

Now, according to the question, each cut corresponds to a light edge. Now we know that we have a total of $2^{n-1}-1$ possible cuts for $n$ vertices. So, each of these cuts, points towards an edge, that, according to the theorem is safe to add into $A$. So we add all the corresponding edges of all the possible cuts.

Hypothesis-2: $|A|=|V|-1$, when $A$ is made by adding all the corresponding light edges of every possible cut.
Let's assume that we'll have $|A|=|V|$. Since there are $|V|$ vertices in total, we're sure to have a cycle in $G_A$. Now, when we make cuts such that we have one vertex of the cycle in one cut, and all the other vertices in the other one, then we'll always leave one edge of the cycle out. Thus, contradicting the assumption. Therefore the hypothesis is true.

Now, we know that $A$ has exactly $|V|-1$ edges in it. Moreover, $A$ will always come to be the same set, on the same graph $G$.

And, we know that a set of $|V|-1$ different edges, for $|V|$ vertices, always leads to an MST.

CONVERSE:
The converse states that, "If a graph has a unique MST, then for every cut of the graph, there is a unique light edge crossing the cut."

[Photo credits : https://github.com/gzc/CLRS/blob/master/C23-Minimum-Spanning-Trees/23.1.md]

[CLRS-23.1-2] Proving the conjecture wrong

23.1-2 Professor Sabatier conjectures the following converse of theorem 23.1. Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree $G$, let $(S,V-S)$  be any cut of $G$ that respects $A$  and let, $(u,v)$ be a safe edge for $A$ crossing $(S,V-S)$. Then, $(u,v)$ is a light edge for the cut. Show that the professor's conjecture is incorrect by giving a counterexample.

So, the basic problem that I faced here was :

Every edge is added to $A$ only after comparing all the other edges that connect both the components of $G_A$. So, $(u,v)$ connecting any two components must be a light edge.

Well, this is obviously wrong. Since, the two components that we're talking about, in both the scenarios are different. That is to say, when we added $(u,v)$ to $A$, there might not be any other edge connecting the two components (like for example, if both the components contain only one vertex), but when we have our present $A$,then we might have many other edges other than $(u,v)$, which connect the chosen components. So, in that case $w(u,y)$ is not necessarily the minimum of all the edges' weights connecting those components.
For example see:

Here, we have a tree (which itself is a graph), let $A$ have all the edges (that is $A$ is the MST here)  $S = \{A,E,D\}$ and $V-S = \{B,C\}$. Now see that $(A,B)$ is not a light edge, even though it is a part of $A$, and is safe.

Proof- Safe edges in a Graph

Consider the following theorem:(23.1 in CLRS)

Let $G =  (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S,V - S)$ be any cut of $ G$ that respects $A$, and let $(u,v)$
be a light edge crossing $(S,V- S)$. Then, edge $(u,v)$ is safe
for $A$.

Now, from what I understood after reading the book, we take an edge $(u,v)$ (that is not in $A$), that is either in $T$ or not. If it is in $T$, then it is already safe. But if it isn't, we can see that since $T$ must include all the vertices of the graph $G$, then there must be some edge $(x,y)$ crossing the cut. (Since $(u,v)$ isn't in $T$). Now, if we make another tree $T'$ that contains $(u,v)$, but not $(x,y)$, then we'll still have an MST, since $(u,v)$ is a light edge, thus $w(u,v) \leq w(x,y)$, therefore, $$w(T') = w(T) - w(x,y)+w(u,v) \\ \leq w(T)$$. Thus $T'$ is an MST of $G$ that contains $(u,v)$. Thus all-in-all, $(u,v)$ is a safe edge. Cool!

4-3 CLRS part (a)

Finally, something apt for my appetite!
4-3[clrs]:

Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for sufficiently small $n$. Make your bounds as tight as possible, and justify your answers.

(a) $T(n) = 4T(n/3)+nlgn$
Since I'm a lazy person, I'll not show the lower bounds.
For the upper bound:
First of all we'll need two summations:
$$\sum_{j=0}^{j=i}(\frac {4}{3})^j = 4[(\frac{4}{3})^i-1]$$
and
$$\sum_{j=0}^{j=i}(j \times (\frac {4}{3})^j) = M = 1 \times (4/3)+2 \times (4/3)^2+ 3 \times (4/3)^3 +...+i \times (4/3)^i \\ \frac {4}{3} \times M = 1 \times (4/3)^2 + 2 \times (4/3)^3 + 3 \times (4/3)^4 +...+i \times (4/3)^{i+1} \\ M - \frac{4}{3} \times M = \sum_{j=1}^{j=i}(\frac{4}{3})^j-i \times (\frac{4}{3})^{i+1}\\  \frac{M}{3} = i \times (\frac{4}{3})^{i+1}-4 \times (\frac {4}{3})^i+4 \\ M = 3i \times (\frac{4}{3})^{i+1}-12 \times(\frac{4}{3})^i+12 \\ =  (4i-12) \times (\frac{4}{3})^i+12$$

Now, see $$T(n) = 4 T(\frac{4}{3})+nlgn \\ = 4 ( 4T(n/3^2)+(n/3)lg(n/3))+nlgn \\ = 4 ^2 T(n/3^2)+(4/3)lg(n/3)+n lgn \\ = 4 ^3 T(n/3^3)+ (4/3)^2lg(n/3^2)+n lgn \\ = 4^i T(n/3^i)+ \sum_{j=1}^{j=i}(\frac{4}{3})^{j-1}lg(\frac{n}{3^{j-1}}) \\ = 4^iT(n/3^i)+ \frac{3}{4} \times \sum_{j=1}^{j=i} (\frac{4}{3})^j[lgn - (j-1)lg3] \\ = 4^i T(n/3^i)+ \frac{3}{4} \times lgn \times \sum_{j=1}^{j=i} (\frac{4}{3})^j - \frac{3}{4} log 3 \sum_{j=1}^{j=i} j \times (\frac{4}{3})^j + \frac{3}{4} lg3 \times \sum_{j=1}^{j=i} (\frac{4}{3})^j  \\ = 4^i T(n/3^i)+3\times lgn [4 [(\frac{4}{3})^i-1]] -\frac{3}{4} log 3 [(4i-12)(\frac{4}{3})^i+12]+\frac{3}{4}\times lg3 [4[(\frac{4}{3})^i-1]] \\ = 4^iT(n/3^i)+3\times lgn \times (\frac{4}{3})^i -3\times lg 4 - 3 \times lg3 [ 4i\times (4/3)^i-12 (4/3)^i+12]+3 lg3 \times (4/3)^i- \frac{3}{4}lg3 $$
Since, we're finding only the asymptotic bounds, therefore, we can remove the constant terms, and moreover $n/3^i=1$ when $i=log_3n = k$. Therefore, doing that:
$$T(n) =  4^k \times T(1) + 3 lgn \times (\frac{4}{3})^k - 4k (4/3)^k +12\times /3)^k -12 +(4/3)^k \\= 4^{log_3n} + 3 log_2n \frac{4^{log_3n}}{n}-\frac{4 log_3n}{n}+\frac{4^{log_3n}}{n}-12$$
From this equation, we can see that the largest term is $4^{log_3n}$. Hence the asymptotic upperbound of the given recurrence is $O(4^{log_3n})=O(n^{log_34})$.

4.3-1,2,3 CLRS

Again, all three of these questions were easy, but were marked. So, alas, I'll put their solutions here too.
4.3-1[clrs]:

Show that the solution of $T(n)=T(n-1)+n$ is $O(n^2)$.

Assume $T(n) \leq cn^2$, for some constant $c$. Then we'll have, $$T(n)\leq c(n-1)^2+n \\ =c(n^2+1-2n)+n\\=cn^2+c-2cn+n\\ \leq cn^2$$
This can be done only if $c+n \leq 2cn$. Now, assume, $c \geq 1$ and $n \geq 1$, then $c+n \geq 2$ and $2cn \geq 2$. Therefore this inequality can exist for these assumptions.

4.3-2[clrs]:

Show that the solution of $Tn(n)=T(\lceil n/2 \rceil)+1$ is $O(log n)$.

Assume $T(n) \leq clog n-d$, for some constant $c$. Then we'll have, $$T(n)  \leq c log(\lceil n/2 \rceil) -d+1 \\ = c log(\frac{n}{2}+1)-d+1 \\ < c(log(\frac{n}{2})+1)-d+1 \\ = c(logn - log2+1)-d+1 \\= clog n -d +1 \\ \leq  clogn$$
Note that this inequality will only exist if  $log(\frac{n}{2}+1) \leq log(\frac {n}{2})+1$. It's proof(backwards):
Raising both sides to the power of 2.
$$\frac{n}{2}+1 \leq  2^{log(\frac{n}{2})+1}\\ \frac{n}{2}+1 \leq 2 \times 2 ^{log \frac{n}{2}}\\ \frac{n}{2}+1 \leq 2 \times \frac{n}{2} \\ \frac{n}{2}+1 \leq n \\ 1 \leq \frac{n}{2} \\ 2 \leq n$$
Therefore, $n_0 = 2$, for our inequality to exist.

4.3-3[clrs]:

We saw that the solution of $T(n)=2T(\lfloor n/2 \rfloor)+n$ is $O(nlogn)$ . Show that the solution of this recurrence is also $\Omega (n logn )$. Conclude that the solution is $\Theta (n logn )$.

Assume, this time that $T(n) \geq c logn $ for some constant $c$. Then we'll have, $$ T(n) \geq 2 c \lfloor \frac {n}{2} \rfloor log \lfloor \frac{n}{2} \rfloor +n \\ T(n) \geq 2(c(\frac{n}{2}-1)log(\frac{n}{2}-1))+n \\ T(n) \geq 2 (\frac {cn}{2}-c)log(\frac{n}{2}-1)+n\\2(\frac{cn}{2}-c)(log(\frac{n}{2})-1)+n \\ T(n) \geq (cn -2c)(log(\frac{n}{2})-1 )+n \\ T(n) \geq (cn-2c)(log n -2) +n \\ T(n) \geq cnlogn -2cn -2clogn + 4c +n\\ T(n) \geq cnlogn$$

Notice that here too we are needed to prove that $log(\frac{n}{2})-1 \leq log(\frac{n}{2}-1)$, but that can easily be derived from the proof we did in the last answer, by putting $\frac{n}{2}-1$ in place of $\frac{n}{2}$.

4.2-6 CLRS

4.2-6[clrs]:

How quickly can you multiply a $kn \times n$ matrix by an $n \times kn$ matrix, using Strassen's algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.

Well, this one was easy. I don't know why I couldn't do it earlier. So,
Case-1:
We want to multiply a $kn \times n$ matrix with a $n \times kn$ matrix. Now we can see that the $kn \times n$ matrix is composed of $k$, $n \times n$ matrices. We can say the same thing for the $n \times kn$ matrix.

Therefore we can rewrite both the matrices as $k \times 1$ and $1 \times k$, by assuming each $n \times n$ matrix as a single element.

Now, if we want to multiply a $k \times 1$ matrix by a $1 \times k$ matrix, then we'll do $k^2$ multiplications, along with no additions. So if  $T(kn \times n,n \times k)$ represents the running times of the multiplication of these two matrices then:$$T(kn \times n,n \times kn) = k^2 T(n \times n,n \times n)+ O(1)$$

And, by Strassen's Algorithm, we know that $T(n \times n,n \times n)= n^{log_2 7}$. Therefore, $$T(kn \times n, n \times kn)=k^2 \times n^{log_2 7}$$

Case-2:
Now, in this case, we want to multiply a $n \times kn$ matrix by a $kn \times n$ matrix. Now again, we'll change them into $ 1 \times k$ into $k \times 1$ matrices. Notice that this multiplication requires $k$ multiplications of $n \times n$ matrices and $k-1$ additions. Therefore, $$T(n \times kn, kn \times n)= k T(n \times n) +O(k)$$
Which, equals:
$$T(n \times kn,kn \times n) = k \times n^{log_2 7}+O(k) = k \times n^{log_2 7}$$

4.2-5 CLRS

4.2-5[CLRS], States that:

V. Pan has discovered a way of multiplying $68 \times 68$ matrices using $132,464$ multiplications, a way of multiplying $70 \times 70$ matrices using $143,640$ multiplications, and a way of multiplying $72 \times 72$ matrices using $155,424$ multiplications. Which method yields the best asymptotic running time when used in a divide and conquer matrix multiplication algorithm ?  How does it compare to Strassen's algorithm?

ANSWER:
Here is my try over this question:
We are provided with three options:

1.  Use $68 \times 68$ matrices in order to find the multiplications of larger matrices.
2.  Use $70 \times 70$ matrices.
3.  Use $72 \times 72$ matrices instead.

But which one to choose? How to compare?
Well, if we want to compare these three, we need a (bigger) matrix that can use all three of them. Consider the LCM of $68$,$70$ and $72$: $42840$. So, if we get to multiply two $42840 \times 42840$ matrices, then we can test all the three of the submatrices!

So, let's do that.

I'll start with a smaller example in order to clarify stuff. Let's consider a multiplication of two $9 \times 9$ matrices. If we divide a $9 \times 9$ matrix into 9 $3 \times 3$ matrix, then we'll do $3^3=27$ $3 \times 3$ matrix multiplications. And if we claim that each  $3 \times 3$ matrix multiplication takes $k$ multiplications, then we can multiply two $9 \times 9$ matrices in $27 \times k$ multiplications.

Here, the claims are given in the question. All we have to find is the total number of multiplications.

CASE-1:
We'll get a $630 \times 630 $ matrix, thus $630^{3} \times 132464 = 3.3122 \times 10^{13}$ multiplications.

CASE-2:

We'll get a $612 \times 612 $ matrix, thus $612^{3} \times 143640 = 3.2925 \times 10^{13}$ multiplications.

CASE-3:

We'll get a $595 \times 595 $ matrix, thus $595^{3} \times 155424 = 3.2739 \times 10^{13}$ multiplications.So eventually, the least number of multiplications are in the case-3, when we take $72 \times 72$ matrices in a divide and conquer matrix-multiplication algorithm.

Now, guess what? I'm wrong.
 REAL ANSWER: 

The thing I'm calculating considers only the multiplications, not the additions that are done.
Well, I'd seen this  blog-post upon this question.  I didn't really understand it.  But later, I found my mistake. In the question number 4.2-4 of the same blog, we can find a formula: $$T(n) = k\times T(n/3)+\Theta(n^2)$$

which, by case-1 of the master theorem gives the answer $O(n^{log_3k})$. In this case we also consider the additions.
So, this blog gives the second way as the answer, and that seems legit too, because the third case might have extra additions, (because it has a bigger tree) leading to extra running time. Therefore, IMHO a $70 \times 70$ matrix should be used for the divide and conquer matrix-multiplication.