Application of clustering

Informal goal - given n points [web pages images, genome fragments, etc] classify into "coherent groups" People in machine learning must have heard of unsupervised learning. Assumption 1) As input, given a (dis) similarity measure 2 symmetric examples - euclidean distance, genome similarity goal - same clusters => nearby So, coherent group has smaller distance. Objective function to do clustering - there are many objective functions, but we are reading max-spacing k-clusterings.  Max spacing  k-clustering Assume we know...

Read More

Minimum Spanning tree MST

MST is used to connect a bunch of points to each other as cheaply as possible. Applications clustering networking Blazingly fast greedy algorithms There are many greedy algorithm, but we will talk about 2: Prim's algo [1957, also djikstra' 1959] or Jarnic found it in 25 years earlier. Kruskal's algo[1956]. Will be using union find data-structure. They are blazingly fast as they are almost close to linear time of number of edges: O( m log n) time m = edges, n=vertices OR better O (|E| log |V|) Problem definition Input - undirected graph...

Read More

Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here. Example So consider the tree:       1    /    \   2      3  /   \   /    \ 4   5  6   7 The BFS or level order traversal here is : 1 2 3 4 5 6 7 Last time we used BFS,...

Read More

Binary Tree Post-Order Traversal - Recursive and Iterative Solution

Consider the tree: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root. Therefore, the Postorder traversal of the above tree will...

Read More

Binary Tree In-Order Traversal - Recursive and Iterative Solution

Consider the tree Inorder traversal prints the binary tree in increasing order in case of Binary Search Tree, but here we are discussing any binary tree. To traverse a binary tree in Inorder, following operations are carried-out : Traverse the left most subtree starting at the left external node,  Visit the root, and Traverse the right subtree starting at the left external node. Therefore, the Inorder traversal of the above tree will...

Read More

Find the rank w.r.t K - Number of nodes with value less than K

If the rank of the BST is k, it implies how many nodes/keys are less than k. So, it boils down to 3 easy recursive calls In the simplest case if K==node value, then whole of the let is rank of the node if K < node.value then we know that rank depends on the size of left sub tree and its less than sub tree's length If K > node.value then we know that we have to count full left subtree w.r.t with that node, and some nodes in right public int rank(int K, node x) { if(x==null) return 0; if(K < x.data) return rank(K,x.left); ...

Read More