Showing posts sorted by date for query kruskal's algorithm. Sort by relevance Show all posts
Showing posts sorted by date for query kruskal's algorithm. Sort by relevance Show all posts

Saturday, January 20, 2018

Leetcode 684: redundant connection

January 20, 2018


Introduction


One of ways to learn the algorithm is to ask the peer to solve the algorithm after mock interview. I met a peer this morning 10:00 am mock interview. He is graduating from K.I.T. a university in German. He likes to apply Switzerland Google instead of German one.

Algorithm problem solving


The peer came out the idea of the algorithm Kruskal's algorithm. And he also talked about minimum spanning tree. How does the edge joins the union by determining if the node is belonging to the union or not. If both of nodes of edge is in the same union, then the extra edge is found.

I asked him what is last time he worked on the Kruskal's algorithm recently. He said that he did not work on. But he worked on video project, cycle detection, filter, or canvas, video, use interface, when the video start time clip something related to the algorithm.

Aha, how do you compete with some one with super talent, and also hands on with projects outside the university, job?

And also the peer is super calm when he worked on the algorithm. He said that let me think about 1 to 2 minutes. And then at last, I asked him if I gave him the hint, he said no.


Thursday, January 18, 2018

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

Sunday, July 2, 2017

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.





Friday, April 14, 2017

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. 

Thursday, April 13, 2017

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 



Friday, September 2, 2016

Book reading: competitive programming

Sept. 2, 2016

Plan to spend 30 minutes a time, up to 10 hours to read a short book - 152 pages first.

Competitive programming course:

Free download - version 1


Julia spent more than 1 hour to look into lead board of HackerRank, and then, she found the book to read:

https://algo.is/
competitive programming course

https://sites.google.com/site/stevenhalim/

Free download - version 1

Competition course


Julia is looking for a book talking about suffix array etc. advanced data structure. She found one today.

Write down some great ideas after reading. 

1. 10 terms Julia's favorite from the book:
1. Simple array that is pre-preprocessed with Dynamic Programming - Data Structure term (page 7)
2. Page 11, a form of Hash Table - ‘Direct Addressing Table’ (DAT) 

2. Page 8 Question:
2. Given a list of integers L of size up to 1M items, determine whether a value v exists in L?

(More details in Section 2.2.1).

Page 16 - Balanced Binary Search Tree (BST): C++ STL <map>/<set> 
Java TreeMap/TreeSet 
argument: implement a bug-free balanced BST like AVL Tree or Red-Black (RB) Tree is tedious and hard to do under time constrained contest environment. 

3. Look into those typical problems, first, remember the terms - Page 17 - Page 18 
Spend 30 minutes for each problem - warmup, and get traditional problems into daily routine - talk, warmup, and study some implementation using C# as well. (9/11/2016 - 1:21pm)

Programming exercises to practice using basic data structures and algorithms (with libraries):
• Static array, C++ STL <vector>, <bitset>, Direct Addressing Table
1. UVa 482 - Permutation Arrays (simple array manipulation)
2. UVa 594 - One Two Three Little Endian (manipulate bit string easily with <bitset>)
3. UVa 11340 - Newspaper (Direct Addressing Table)

• C++ STL <algorithm>
1. UVa 146 - ID Codes (use next permutation)
2. UVa 10194 - Football a.k.a. Soccer (multi-fields sorting, use sort)
3. UVa 10258 - Contest Scoreboard (multi-fields sorting, use sort)

• Sorting-related problems
1. UVa 299 - Train Swapping (inversion index3 problem solvable with bubble sort)
2. UVa 612 - DNA Sorting (inversion index + stable sort)
3. UVa 10810 - Ultra Quicksort (inversion index - requires O(n log n) merge sort)
4. UVa 11462 - Age Sort (counting sort problem, see [4])
5. UVa 11495 - Bubbles and Buckets (inversion index - requires O(n log n) merge sort)

• C++ STL <stack>
1. UVa 127 - “Accordian” Patience (shuffling <stack>)
2. UVa 514 - Rails (use <stack> to simulate the process)
3. UVa 673 - Parentheses Balance (classical problem)
4. UVa 727 - Equation (Infix to Postfix conversion)

• C++ STL <queue>
1. UVa 336 - A Node Too Far (<queue> used inside BFS, Section 4.3)
2. UVa 10901 - Ferry Loading III (simulation with <queue>)
3. UVa 11034 - Ferry Loading IV (simulation with <queue>)

• C++ STL <map>/<set>
1. UVa 10226 - Hardwood Species (use <map>)
2. UVa 11239 - Open Source (use <map> and <set> to check previous strings efficiently)
3. UVa 11308 - Bankrupt Baker (use <map> and <set> to help managing the data)
4. UVa 11136 - Hoax or what (use multiset in <set>)

• C++ STL priority queue in <queue>
1. UVa 908 - Re-connecting Computer Sites (priority queue in Kruskal’s, Section 4.4)
2. UVa 11492 - Babel (priority queue in Dijkstra’s, Section 4.5)
3. LA 3135 - Argus (Beijing04)

Find a website about Ultra quicksort:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1751


Nov. 24, 2016
C# book reading: