Kruskal's algorithm Wiki article

January 18, 2018

Introduction

It is the very good investment of time to read the article of Kruskal's algorithm on the wiki page. What I do is to go over each word and each sentence slowly, write down some new terms I like to learn. Today I spent over 30 minutes to read the article.

Kruskal's algorithm 

Plan to spend 20 minutes to read the article first.

Terms:

minimum-spanning-tree algorithm
greedy algorithm in graph theory

minimum spanning tree

a subset of edges that forms the tree that includes every vertex, where the total weight of all the edges in the tree is minimized.


How to read the algorithm Kruskal's algortihm


How to read the graph simulation of steps: b and e are added, but there is a cycle.

Average performance:  O(|E|log|V|)

Worset-case space complexity:


Prim's algorithm, Reverse-delete algorithm, Boruvka's algorithm

comparison sort

disjoint-set data structure
union by rank

(counting sort or radix sort)  Ackerman function

induction -

minimality

Leetcode 684: redudant connection

January 17, 2018

Introduction

It is the second time to meet the peer again in less than one week. Julia chose to give a medium level algorithm for peer to solve, Leetcode 684: redudant connection.

Discussion

Here is the transcript for the discussion.

Highlights of good things in discussion

Peer did:

1. First the peer came out to check if the graph has a cycle

2. Second the peer drew a more complicated tree, and then try to add one edge to make it a cycle

3. Third the peer write down a list of graph algorithm he worked before.



I try not to give out hint explicitly. So what I talk is about the example a tree drawed by the peer how node 1 is connected to node 7.

What is the connected meaning for us? The nodes are connected.

Also, I added one more graph algorithm called Kruskal algorithm, and then share the wiki page for the algorithm. I talked about the algorithm for minimum spanning tree using disjoint set data structure. And then I asked if the peer knew the data structure before.

I explained the data structure, what is for, why we need this data structure. Since the path from one node to other node is not needed, all we care about is if two nodes are connected. We do not need to search a path from one node to other node.

At last, I tried to give the explanation how to solve it in less than five minutes.


Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3         
 

Julia's explantion:


At the beginning, each node has its own set.
{1}, {2}, {3}, {4}, {5}.

[1,2] first edge is to connect 1 to 2, so {2} likes to join {1].


{1} <- {2}, {3}, {4}, {5}.

we have {1, 2}, {3}, {4}, {5}.

[2,3] second edge is to connect 2 to 3, 2 is not the set, but 3 is not in the set.


{1, 2} <- {3}, {4}, {5}
we have {1, 2, 3}, {4}, {5}

[3,4] third edge is to connect 3 to 4, 3 is in the set, but 4 is not in the set.

{1, 2, 3} <-{4}, {5}
we have {1, 2, 3, 4}, {5}

[1, 4] fourth edge is to connect 1 to 4, 1 is in the set, and 4 is also in the set. Then we know that node 1 and node 4 are connected, but direct connected edge 1 to 4 is to be added. Then edge [1, 4] is to form a cycle.

Super Mancunian - HourRank 22

July 2, 2017

Introduction

It is a minimum spanning tree algorithm. But there is additional work to remove max cost edge in the tree. Julia started to work on the algorithm last 30 minutes, she spent 10 minutes to go over the problem statement and then figured out the whole requirement. She only had 20 minutes, she fumbled, and she looked at the leaderboard, checked players from Google's performance, she likes to write a simple code to score partial points to make her a medal player.

Too short time, it just reminds her that she needs to work on and review what she works on. She just needs to look into past work and then find a solution to score the points.

An algorithm makes her Sunday morning so challenging.

Algorithm 

Previous practice on Kruskal's algorithm is here. Julia spent wrong on the name, she spelled Krusal. In order to pay respect the scientist, Julia decided to review his wiki page and get more detail on his work.

Read wiki page as well. Plan to spend one hour to read this Sunday morning.

Kruskal's algorithm workout (I)

April 14, 2017

Introduction

It is a good workout to work on Kruskal's algorithm based on the geeksforgeeks.com article.  Julia likes to spend 2 - 3 hours to play with Kruskal's algorithm using C#. 

Later on, she likes to work on the algorithm on Hackerrank week code 31 - Spanning Tree Fraction. 

Kruskal's algorithm

Greedy algorithm to get minimum spanning tree using Kruskal's algorithm. 

Spent near 2 hours to work on the C# code. C# code is here. 

Hackerrank: Spanning Tree Fraction

April 13, 2017

Problem statement

Introduction

Julia likes to work on spanning tree algorithm, even though it is hard algorithm, but Julia did spend some time on the algorithm before. So, it is also a good practice to review previous contests related algorithms.

Julia started to read minimum spanning tree, understand why union set is better than DFS algorithm to detect cycle in the tree algorithm.

Minimum Spanning Tree

Here is the tutorial she studied for the algorithm.

minimum spanning tree -  April 13, 2017 

Hackerearth.com -> graph -> minimum spanning tree -> tutorial 

Kruskal's algorithm - 

Learn the algorithm - using disjoint set / not DFS 

check how it is not connected? Using DFS algorithm to search - O(V + E) 

Value of friendship

Code review of algorithm "value of friendship" is here.

Kruskal's algorithm

GeeksforGeeks article

Code preparation