Saravana Kumar's

What matters

Union-Find Data Structure Python : For Clustering Algorithm

| Comments

I was coding kurskal’s clustering algorithm for a max-spacing k-clustering problem. To improve the efficiency of the clustering algorithm, I needed an efficient data structure to union two cluster and find an element in a cluster.

Union Find (disjoint-set) data structure is best option for above operations. Implemented the Union Find structure as per the algorithm specified in the Introduction to Algorithms book.

This Implementation includes Union by Rank and Path compression, which gives a amortized runtime of a(n) (i.e a – Ackermann function)

#! /usr/bin/env python
#
# Copyright 2012 Saravana Kumar(RIT)
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may
# not use this file except in compliance with the License. You may obtain
# a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations
# under the License.
"""
Author : Saravana Kumar
E-mail : saran8@gmail.com
Union-find data structure.
Based on Algorithm from Introduction to Algorithms Book(http://mitpress.mit.edu/books/introduction-algorithms),
"""
from node import Node
class UnionFind(object):
def __init__(self):
#To hold the clusters
self.clusters = []
#create a new set(cluster) with a node
def makeSet(self,node):
#set the nodes parent to the node itself
node.parent = node
#set initial rank of node to 0
node.rank = 0
#add the node to cluster list
self.clusters.append(node)
#union the nodeA and nodeB clusters
def union(self, nodeA, nodeB):
self.link(self.findSet(nodeA), self.findSet(nodeB))
#link the nodeA to nodeB or vice versa based upon the rank(number of nodes in the cluster) of the cluster
def link(self, nodeA, nodeB):
if nodeA.rank > nodeB.rank:
nodeB.parent = nodeA
#remove the nodeB from the cluster list, since it is merged with nodeA
self.clusters.remove(nodeB)
else:
nodeA.parent = nodeB
#remove the nodeA from the cluster list, since it is merged with nodeB
self.clusters.remove(nodeA)
#increade the rank of the cluster after merging the cluster
if nodeA.rank == nodeB.rank:
nodeB.rank = nodeB.rank + 1
#find set will path compress(makes the nodes in cluster points to single leader/parent) and returns the leader/parent of the cluster
def findSet(self, node):
if node != node.parent:
node.parent = self.findSet(node.parent)
return node.parent
#get cluster size
def clusterSize(self):
return len(self.clusters)
view raw unionFind.py hosted with ❤ by GitHub

Interview Street Challenge - Candies


Problem:
         Interview Street Problem:

Idea:
        If the rating is in increasing order
                             - Just traverse through it and increase the number of candies
        If the rating is in decreasing order
                             - Same as increasing order but in reverse way
        If the rating is in random
                             - the ordering will be like line of mountains with valley in between.Refer to this

Solution:
C++ solution in git
Passed all test cases.
#include <iostream>
using namespace std;
int main() {
int N;
//Get Number of students
cin>>N;
//initialize rating and candidates array
int *rating = new int[N];
int *candies = new int[N];
//get rating of each student
for (int i=0; i<N; i++){
cin>>rating[i];
}
for ( int i = 0; i<N ; i++){
//Each student gets at least one candy
candies[i] = 1 ;
//Check boundary condition
if( i-1 >= 0){
//Look for previous student rating and if it less than current student
//assign the current student rating to the previous student rating plus one
if( rating[i-1] < rating[i]){
candies[i] = candies[i-1]+1;
}
//Other wise if previous student rating is greater than current student
//Imagine it as slope of mountain for example consider rating in decreasing order( 9 8 7 6 5 4)
// so the number of candies has to increased for all previous students
else {
int j = i;
while (j>0 && rating[j-1] > rating[j])
{
//check is the current student already has max number of candidates
//for example if students are arranged in below fashion
// 123456 7 5432
//here 7 will have more candies if we go back from 2 it will result in 5/4 candies which violates the rule from the front
candies[j-1] = max(candies[j-1],candies[j] + 1);
j= j-1;
}
}
}
}
//sum up all the candies of the students
int total = 0;
for ( int i = 0; i<N ; i++){
total += candies[i];
}
//display the candies
cout<<total;
system("pause");
return 0;
}
view raw candies.cpp hosted with ❤ by GitHub

Serial Port Communication in Windows Using Java

Serial Port communication using java can be done using RXTX library.  RXTX library is a native library provides serial and parallel communication for the Java Development Toolkit (JDK). RXTX is provided under gnu LGPL license. RXTX provides same support as javax.comm library

Installing RXTX in Windows 32Bit Machine:

  • Identify your Java Runtime Environment’s folder. For version 1.6.0, this usually isc:\Program Files\Java\jre1.6.0_01\

  • Copy the files from the downloaded RXTX binaries folder. Download binaries here http://rxtx.qbang.org/wiki/index.php/Download

  • Copy rxtxParallel.dll to c:\Program Files\Java\jre1.6.0_01\bin\

  • Copy rxtxSerial.dll to c:\Program Files\Java\jre1.6.0_01\bin\

  • Copy RXTXcomm.jar to c:\Program Files\Java\jre1.6.0_01\lib\ext\

Installing RXTX in Windows 64Bit Machine:

Do the same as for 32 bit except download the binaries from here http://www.cloudhopper.com/opensource/rxtx/

Using RXTX in Eclipse

Usually RXTX works but for eclipse sometimes it won’t work. You can use below way to configure the eclipse environment.

Way-I:

  • Copy RXTXcomm.jar, rxtxSerial.dll and rxtxParallel.dll files to the lib directory of your project
  • Under Project | Properties | Java Build Path | Libraries
  • Click Add JARs… Button
  • Select the RXTXComm.jar from lib directory
  • Jar should now be in the Build Path
  • expand the RXTXComm.jar entry in the list and select “Native Library Location”
  • Select the project lib directory and apply

Alternative way:

The above setup didn’t quite work for me, so here is an alternative.

  • Copy RXTXcomm.jar to the lib directory of your project.
  • Navigate your package explorer to the lib folder, right click on RXTXcomm.jar | Build Path | Add to build path.
  • Copy rxtxSerial.dll and rxtxParallel.dll files to the root directory of your project.
  • Under Run | Run configurations | Classpath tab | User entries | Advanced | Add folder, choose the root folder of your project.

This should be enough just to run it under Eclipse, when deploying a runnable jar, just make sure the dlls are on the same folder as the jar (JVM assumes it for classpath).

For installing RXTX in Other OS:

Refer this link http://rxtx.qbang.org/wiki/index.php/Installation.

Usage:

import gnu.io.*;

The above header file is equivalent to javax.comm and provides all classes and methods provided by it.

Be careful when using System.in.read() and rxtx in win32; 
It can trip across a known JRE deadlock bug.

Samples:

Follow below link for samples given by rxtx. Link

Answer to a Question(Numeric to Word)

Read a interview question to write an algorithm to convert entered numeric values to words (ex: 1—one ,2 – two) for up to six digits. Is it hard to convert ? No . We could do this in lot many ways but an effective program which uses proper data structure and algorithm that’s what it takes.

Here I got it https://sites.google.com/site/ourorganisationsite/number-to-currency

I had a dictionary to hold one and Tenths position words then rest lies in identifying the position of a numeric.

One of friend surpassed my limitation and he converted number till Quintillion I dont have idea how many digit has ? Awesome work chinmoy!!!

MVC Architecture

| Comments

The power of MVC Architecture in ASP.Net:

  • Great level of modularity .Abstraction between layers and functionalities too.
  • Your Html code will be neat ,no more unwanted scripts and ugly ids for controls (i.e.) “ctl_100contentplaceholder_input”.
  • Easy accessable of control ids from java script .
  • Easy integration with jquery and other ajax frameworks .
  • With LINQ and SQL class, database is abstracted totally from the other business logic.
  • Clean Urls ,Mapping of urls are done nicely as in servelts (Java) .
These are some of the advantages I explored so far .

Working on it ..Will update if get to known more..

Comments

SEO,SEM
ya started blogging it seems……….






http://kpsnirmalsingh.wetpaint.com/
http://nirmalsinghkps.wordpress.com/
Montu
gethu man !