Programming: Allspark

Splay tree (Super Search Tree) Vs Binary Search Tree

2012-01-17T06:24:00.000-08:00

In one of the earlier posts I had called for the use of binary search trees for set representation and general search operations. I take it back. Now it is splay trees !. These are very similar to binary search trees but, these ones are balanced binary search trees. A binary search tree gives you log(n) of search and insertion theoretically. This is true only of the keys that are going into the tree are totally random. So if the set of keys { 10, 2, 38, 63, 21, 9, 1} go into a binary search tree then, the tree looks like

This tree gives you log(n) time on its search. It is balanced too. But, if the application was putting in data in not-so random way then the tree can easily become unbalanced. This can lead to n time search. so if keys were to go in like { 1, 2, 9, 10, 21, 38, 63 }. Then the tree looks like

This seems ok with the defenition of the search tree but, if you were searching for 63 then, you need to do 7 comparisons compared to 3 in the previous tree. Also, recently accessed data may be frequently needed. Effectively this will turn into a list. In a splay tree, all operations are similar to a binary search tree but, you bubble up the recently accessed node up to the root or the first level from root. So next time you access it, the node will be available real fast. The bubble up will cost some time but, will compensate over a number of operations with the efficiency of balancing the tree. For splay tree the average of a collection of operations is always of the order of log(n) although some of these operations may be of n time complexity. Accessing a node means searching / inserting / deleting. In all these cases we bubble up the node / the node that replaced it in the case of deletion.

The process of bubbling up the node consists of left rotations and right rotations. The algorithms to bubble up the node / balance the tree has three conditions.

1) If the node is a right child of a left child then you rotate the node left once and then rotate it right. (vice versa also for this case)

2) If the node is the right child of a right child then, you rotate the parent left once and then the node also once to left. (vice versa also for this case)

3) This has to be done until the node reaches the root or the first level from root.

So for a set of keys { 18, 12, 25, 4, 15, 26, 1, 13, 17, 30, 3, 14, 28, 29} suppose the tree looks like this before any splay. We access 3 in 4 operations.

For splaying, 3 is the right child of a left child so we rotate it left once and then right again. The left rotation gives a tree like this

Then a right rotation again gives

Again since 3 is the left child of a left child we do right rotations. one at 12 then at 3. This brings 3 to the root.

Next time we do a search for 3 we get a faster response. Also, the tree is better balanced so, we get a better time for any node than before.

A run time profiling example: Tree is created with values from 0 - 99999 in order. Then 99999 is searched before and after splaying. The cpu runtime profiling results are shown below.

Another profiling result, to get a feel of the advantage, (constructing the same tree as before) 4 values near leaf and 1 value near mid section are searched together. Both before and after splaying. The run time results are shown below.

Obviously, splay operation has an advantage on an average since, the tree is now balanced and we can find any value in less than half time than before.

Code Design for Singleton / Lazy initialization Concurrency

2012-01-14T09:53:00.000-08:00

This post is an experiment on the concurrency of the common Singleton design pattern and it memory profiling results. Singleton pattern is commonly used in coding and the objective of Singleton is to make sure that, only a single instance of the class is created. The common design with lazy initialization is present in most code. This is shown below (read with out the synchronized keyword).

This is fine as long as the code is executed by a single thread. If ever the code is executed by multiple threads, the 'check for null then act' part can result in multiple instances of the singleton class. If one thread A is checking the instance for null, returns true and it is moved out of processor for another thread B, B checks for null creates an instance. A comes back and creates another instance. So there will be 2 instances now as shown in the run below. The class IamSingle has two instances without the synchronized keyword.

With the Synchronized keyword, the run profile is as follows. There is only one instance.

This kind of bug can be difficult to reproduce as even getting the wrong scenario depends on the timing of the threads.

Classic Longest common subsequence via Dynamic programming

2011-12-13T09:02:00.000-08:00

Run time Profiling results of classic longest common subsequence algorithm.

An example application of this algorithm is finding the difference of two text files. We need to find the longest common subsequence of two sequences. i.e for "bdca" and "bcbda" the longest common subsequence is of length 3 and is "bda"

The core algorithm using dynamic programming for this is as follows

Lcs(i,j) = { Lcs(i-1, j-1) + 1 ; if match at i & j.

Max( Lcs(i-1, j), Lcs(i, j-1) ); if mismatch at i & j

}

This can be implemented recursively using a two dimensional array m x n where m, n are sequence lengths. For example, two sequences "bdca" and "bcbda" we have the matrix for the algorithm above

0 1 2 3 4

b c b d a

--------------------------------------

0 b | 1 1 1 -1 -1

1 d | 1 1 1 2 -1

2 c | -1 2 2 2 -1

3 a | -1 -1 -1 -1 3

--------------------------------------

So here 3 is the length of the longest common subsequence. base on the core algorithm above.

Runtime complexity is about O(mn). This particular basic program yeilds a time as show here

Improvement:

By analysing the recurssion tree of this particular problem there is an improvement that can be made to the runtime. The addition to the core algorithm is as follows

If Lcs(i, j) has not been calculated so far ?

Lcs(i,j) = {

Lcs(i-1, j-1) + 1 ; if match at i & j.

Max( Lcs(i-1, j), Lcs(i, j-1) ); if mismatch at i & j

}

else return the calculated Lcs(i, j);

This small addition saves the code from going to calculate duplicate recursion trees. The time saved (~ 30 ms) is evident here.

The sample recurssion tree is shown below. There are a lot of repeated duplicate tasks.

4, 4

3,4 4, 3

2, 4, 4,3 3, 3 4, 2

1, 4 2, 3 .... 2, 3 3,2 .... 3, 2 4,1

Reconstruction is based again on the algorithm. We backtrack based on the two steps of the algorithm. ie if match occurred or the Max of sub-problems.

1. We start at the right end of the tree

2. if there was a match at i & j then we take sequence[i] (= sequence[j] as in step 1 of algorithm) and go to (i-1, j-1)

3. else we can go either to (i-1, j) or (i, j-1) in the matrix. The logical thing to do is to go where there is maximum value.

4. if matrix values at (i-1, j) or (i, j-1) are same we may have to investigate both.

The disadvantage of this approach is that, as the length of the sequences go up the memory for the matrix also goes up as m x n. One way to improve the memory is to use only two rows since we look at only those every time. But, we may need to keep track of which way we step to reconstruct the lcs sequence.

A take on Huffman coding algorithm. How to squeeze data. 133 bytes to 69 bytes.

2011-12-07T08:45:00.000-08:00

Problem: Compress data in a text file using huffman encoding algorithm.

Basic approach:

1 Read the file and build a Huffman encoding tree.

2 Get encoded bit string.

3 Decode and get the original data by walking the Huffman encoding tree.

This method of compression is based on an inefficiency in normal representation of data strings. The inefficiency is that, we use 8 bits to encode a character that appears 1000 times and 8 bits again for a character that appears only once in the input data. So, if we use less number of bits to represent a high frequency character and comparatively more for low frequency character, then we can compress the data. This gives rise to two new issues.

a) The issue then becomes one of knowing the character set or the alphabet of your data in advance inorder to go ahead with this type of encoding.

b) Encoding the characters as bit sequences can lead to one character being the prefix of another. This can lead decoding program astray. i.e if m is 01101 and e is 011, then we have problem decoding 01101 in out stream since the m might be decoded as an e.

For the time being lets take the ascii character set to address issue a. To deal with issue b we can use a binary tree to represent the encoding. To make sure that, no bit sequnce is a prefix of another character we use the huffmann algorithm to build the tree. This tree is the huff encoding tree. For example an encoding tree is shown here.

Input: is a file with the content

"this is a test file input to huffman encoding algorithm. This will be compressed to a huffmann code. Huffmann encoding tree is used."

The frequency of the characters is calculated as shown here.

Notice that, e occurs 11 times and is encoded with only 3 bits where as b occurs only once and is encoded by 7 bits!. The huffman encodings for the characters are shown here.

Result: The huffman encoding tree has 45 nodes and the encoded bit stream of the input above is 551 bits ie 68.8 bytes as opposed to the 133 bytes in the input. Bit vector and heap help the encoding tree generation algorithm. But, the tree itself seems to be better of as a pointer based tree as opposed to a array based tree (may not be a balanced tree). This can be pretty handy when sending considerable amounts of data over the network in a software environment.

Tree building algorithm:

1 Read the data from the file.

2 Build a table with the count for each character in your alphabet.

3 Build a huffmann encoding tree based on the frequency of your alphabet.

a) create leaf nodes with all the characters occuring in the file along with their

frequencies.

b) take two nodes which have the smallest frequencies.

c) combine these two nodes as the left and right children of a new node.

d) push the new node into the list with frequency set to the sum of the two child nodes.

4 repeat step three until you end up with one node in the list i.e your root node for the encoding tree.

To encode:

1. Replace each character with the bits encountered while getting to the character form the root of the tree.

To decode:

1 input your stream of encoded bits

2 Until your input is not over

3 for each of the bit encountered

a move to the left of the tree if it is a bit 0

b move to the right of the tree if 1 bit

4 if you have reached the leaf node of the encoding tree, go to the root.

How to Code your own Search Engine Like Google, Bing or Yahoo

2011-10-28T06:47:00.000-07:00

Problem:
How to code your own search engine like Google or Bing? How to design the search engine? The search engine should give results in run time Order of (length of search key words)
Input:
100 html files which have a lot of english words in it. Here we focus on the words only. Parsing out the html tags can be done too.
Solution:
Here I use Trie and Binary Tree data structures to design the core search engine. Data can be extracted from pages and the data structures can be built by another program called crawler. This can be combined with the spell suggestion program in the previous post to make it close to real life.
Design considerations here:
The design for the search engine is shown below. The tries as explained in the previous post gives search results in the Order of length of key words. Here we have two words "search " and "engine". The trie has paths for each of these search terms and end in a list of HTML files that have these search terms in them. This list is maintained as a binary search tree. This makes it to find the set intersection of the files which have both the search terms! Any data structure that efficiently finds set intersection can be used.

Working:
1) Crawl the files. Take the words from the files and add them to the trie. At the trie leaf node set the list of files in a binary tree.
2) Input the search terms.
3) For each term retrieve the set of files. Here it is available as binary search trees at the leaf nodes. Since we use a trie, for any number of files, I get the set of files for any given word proportional to the length of the search key word.
4) Find the set intersection of these and display to the user. Here a binary search tree is used to represent sets. Any set representation can be as long as the process of finding set intersection is done efficiently.

The following screen shot shows the search engine in action for the key words, "search", "engine" and "search engine"

The run-time:
To find a single word is around 39 microseconds on my computer using the netbeans profiler (as the trie in the previous blog post). The run time for my search engine is shown below. The search took only 62 microseconds. Now that is how Google is fast. As long as your search data structure and set data structure is chosen correct, you can have it as fast as Google or Bing. Plus you can add additional meta data such for paid pages, relevance to terms, page rank etc and make it better. As for memory you can use a better trie as mentioned in the previous post.

Spell Suggestion Like Google / Microsoft Word

2011-10-25T11:35:00.000-07:00

Problem:

To implement a spell suggestion program similar to the one you see on Google search box, Microsoft Word and the like. English Language dictionary is used.

Solution / Approach:

Algorithm uses a trie to store your keys. Walk through the trie with the user to find the suggestions. An alternative approach is use word edits and employ the spell checker in a previous post.

Input: A english dictionary of 59000 words.

Advantages: Search for a Key is very fast. Suggestions can be found in good time too.

Disadvantages:

The size of the trie can be a limiting factor. But, more than one trie compression technique is available especially for English. But, for this experiment I was focussing on run-time with the first implementation only.

Theory:

Trie is a M-ary tree. An indexing operation is done at each node of the tree. The indices are the characters of the search Key. Suppose there are k possible character values for key. In English a-z + unique marker gives 27. Then each node of the trie has k+1 pointers one for each characters possible at that node. This is similar to the way we search for a word in the dictionary. For example, the word "alpha" is looked up by looking up character "a" then within that, lookup "l" and so on. You can have the pages of all words beginning with "al". In a trie lookup the first character of the key at the root. Then, follow the pointer in the table corresponding to that character. For the word list the number of nodes in the Trie is 143699 ! The word list is by no means compact / processed for that matter.

Searching an item simply follows characters in the key through the tree and if you have exhausted the key, you have a hit or a miss. Inserting Keys is simple as in searching, you add nodes when you have a miss for the key values.

In a trie, you search in O(length of the Key). The snapshots speak for themselves on this.

On the other hand the memory requirement for the basic trie is high. If there are n nodes, then there are n * (k + 1) pointers. The two variations that can be used are

1) Linked list for Pointers in nodes as most of the table is empty in a Trie for English. The trie using the linked list is a de la Briandais Trie.

2) Then there is Practical Algorithm To Retrieve Information Coded In Alphanumeric. Patricia Tries! Here, the algorithms for building and maintaining the tree will change since we have to store the keys too.

3) Tries can also be represented as two dimensional arrays without the key values being stored in the table. This can save quite a bit compared to basic trie.

Experiment:

The run of the java program in NetBeans profiler is here. This is for a small word.

For a really long word the time is bit more as shown in profiler.

Suggestions example runs. The algorithm follows from where the user strayed. Although this throws up more suggestions, it works.

Beginning Java Security on Android

2011-08-02T22:37:00.000-07:00

Android provides all of the java security libraries in Java. Android provides cipher engine classes, Keystore, algorithms, public key cryptography, key generators and the like. The list of algorithms that are supported seems as in the java language updates. Some searching and trials may be needed on this. This is true for the simulator that comes with the android devices too.

One difference is that, while the default security provider for java on desktops is SunJCE the one on android is bouncycastle. So the default keystore type is BKS rather than JKS. This was not so obvious at first but, a few trials showed that, the keystore was BKS and you can also have PKCS12 keystore. The rest is all the same except that, if you create a PKCS12 keystore you need to store an entry as a PKCS12 type/stream otherwise you get an exception asking for a PKCS12 type.

Also, If the keystore path has a '.' anywhere in the path, storing the keystore throws exception. So if you stor your keystore at a location with your 'package folder' name for example 'com.myapp' it may result in exception. Removing the '.' character from the path name avoided this.

Encrypting Text Editor Crystal v 1.0 for Android

2011-08-01T03:53:00.000-07:00

About the application

In the past few weeks I put together an android application which is similar to Crystal in my old blog post. This application allows the user to store text data on an android device by encrypting it. Crystal v 1.0 for android uses java security libraries available on android sdk. Crystal allows you to create a master password for your data files. Once you set your master password, you can write files using crystal and save them in encrypted form and read them later with your master password.

Crystal v 1.0 for android apk file is here . You will need a third party application to install it on your android phone. (Until I get my android market account set properly !)

Welcome Screen

More screen shots and how to use crystal is here

Current limitations
1) Your master password is immutable.
2) Crystal Selects the location for files on your device automatically.
3) AES is the only algorithm supported in the current version.

How it works
Crystal uses java security on android to create a master keystore on your device. This key store holds your key which is used to encrypt/decrypt your data files. The keystore has a password which is the master password. You set this password while using the application and it automatically generates a symmetric key and stores it in your keystore. The master password is never stored anywhere on your device. Your key is also safe as long as you keep your master password.

Android User Interface Part 2

2011-07-16T03:00:00.000-07:00

To build a compound control as shown below.

As in the previous post the steps are to
1) Define the layout in xml.
2) Define a class to represent the layout in code.
3) Inflate the layout in code.
4) Set it to an activity.
The xml layout.
-------------------
The difference is in the attributes that are specified on the xml layout that allows the buttons or any other view to take up enough space as we need it to.

The layout specifies a editview, a list view and two buttons. The two buttons have their width set to 0 dip. The table row which has the button has a collective weight sum of 2. Each of the buttons has a weight of 1. So they occupy half the width each.
The layout class
-------------------

This is similar to the class in the previous blog but, here it is sub-classed from tablelayout. The rest is same.
Using this in an activity
----------------------------
This is also the same as in previous post. Insatntiate a class of the layout just created with the activity as the context. Set it to the activity using 'setContentView' method. The method also shows how to use the arrayadapter to set values to a listview.

The advantage of using the xml layout is that, once it is defined and represented in a layout sub-class it can be used at multiple application activities on the run.

Android User Interface: Using Xml layout resources Part 1

2011-07-16T00:43:00.000-07:00

Problem: Getting a layout in xml, to bring it up on an activity.

In android Views are widgets or controls like textviews, buttons, lists and the like. Activity is what you see on the screen i.e your window or frame that is to be displayed. Layout is how you arrange / position your views on the screen. This is similar to java layouts.

Solution:

The first thing to do is to get your layout defined in an xml layout resource. This can easily be done by using the tools in eclispe for android development. Either you define the xml as shown below in hand or you can use the graphical editor.

In the xml file below, there is a textview that acts as a banner and a listview. The attributes of the views are mostly straight forward. We can get more control over the views using these attributes. For the time being we focus on getting this xml layout on the screen.

The second step is to represent layout in code using a class which is subclassed from android.widget.LinearLayout. We will use this class in code to build the layout and the views in it (inflate) at runtime.

(i) Define a class that extends from android.widget.LinearLayout
(ii) Define fields in the class for the textview and listview. For an instance of this layout class we will get the corresponding view objects into these.
(iii) Override the Constructor for the view, place a call to the super class constructor. Now we add the code to inflate the xml layout.
(iv) Inflating the layout is done using a system service in android called layout inflator service. Once we inflate the layout we get a reference to the textview and the listview of this layout by calling the findViewById method.

So far the layout is there to be used on an activity. To use this layout class in an activity,

(i) Declare this layout object in your activity.
(ii) In the onCreate method of this activity create the layout object using the current activity as context.
(iii) Set the layout using the 'setContentView' method.

You can set some values for the text view and the list view after this or in the layout class itself. Here an arrayadapter is used to set values to the listview.

The advantage of using the xml layout is that, you dont build the layout in code and keep you user interface decoupled from the code. When the layout inflator inflates the layout, it can determine the best by using the xml attributes.

** Note: Never forget to list your own new activities into the android manifest.

Lejos

2011-06-12T12:13:00.000-07:00

Lejos is a firmware jvm that can live in the mindstorms nxt brick. I installed it a couple of days ago after some hiccups. I was following some documents on the web to install this on the brick. After a bit of frustration I was able to get it right. Thanks to mindstormscreator and his installation videos on youtube. This also shows how to get everything up and running even with eclispe IDE. The test run of a java program that plays a tune on the mindstorms brick was successful. At one time after failed flashes my brick was showing the lejos version like a counter 0.7 -0.8, also showing a java exception on the lego brick, finally settling in 0.8. But, it is all sorted out now. A particular book on robotics studio was very tiring even after a number of reads. So, I decided to go the Java way. More information on how to on Lejos is here Lejos. Can't wait to program in java for the mindstorms brick. Hoping for challenges as in Bentley!

Google.com Doodle Guitar 9 June 2011

2011-06-09T00:40:00.000-07:00

Check out the new doodle from Google. If you have not seen it go to Google.com. Not your regional google search page but, the US or .com level page. The doodle is a playable guitar. This is my favourite doodle and also the shortest post on this blog ! Also, Google voice search is available on this google.com domain. in case you did not notice. A picture of the doodle

Spell checker design using scatter hash algorithm

2011-06-02T10:39:00.000-07:00

This is the design of a spell checker that, I finally coded up. The principle is same as that of McIlroy but, the hash and the bit vector distribution is based on trial and error. I used a list of words that, I stumbled upon in the web. It is by no means optimized for spell corrections. It has 58112 words which I assume as almighty. I take each word and subsequently hash it 32 times to get 32 values which are mapped into a bit vector. The bit vector from the previous post was reused. So, if a word not in the dictionary is entered and checked, atleast one of the hashes would fail. If it failed, the word is not in the dictionary. Happy. Since this uses scattered hash/sort of :), an invalid word can match the hashes accidentally. The fun part was, how this is affected by the hash table size and the hash function. You can literally see the error increase/decrease as you alter these.

The input: a list of 58112 word.
The output behaviour:

Bit vector size invalid word accepted?

--------------------------------------------------------------
case a                500KB                No.
case b                375KB               No.
case c                250KB                No.
case d                125KB                Yes.
Final case:     93.75 KB                Yes.

The first numbers on the bit vector memory feel not so good for a 58K word list. The mathematics that, describes the relation between the hash bit length (32 here), word list length and the probablity of an invalid word hashing correctly is described by McIlroy. This comes into play in the last two cases above. I did not prove it but, runs of the program point to that clearly. It can still be downsized but, the point was to try the scatter technique for the spell checker.

Observation: I did change the 32 values used in the hash functions which gave me a good reduction in bit vector size and lower error rate. The
final run used 32 consecutive values from the farther end of the proposed hash table size. Previously, I was using differences of 100 ie N - 100, N - 200, N -300, N -400 ...... N - (32 * 100). All that left me was with even values in the hash functions. This affected the accuracy of the hash I can say from the run of the program (i.e invalid words matched seeminlgy easy). But, when I used the consecutive values i.e N - 1, N -2....N - 32 I have introduced primes not purposefully. But, the urge to change the hash values was there. McIlroy says that, the use of n primes for the n hash functions is very good and he used it. A lot of reading on the web claimed that, the use of primes in hash function and their advantage was not that great. But, this small program with only a couple of primes seems to be faring better than with out them. Why 32? McIlroy used 27 I picked 32!. :)). This choice is to be based on the mathematical relation I pointed to above (refer McIlRoy paper).

The program when profiled in Netbeans takes 0.169ms to find if a word in the dictionary. A run of the program on this 573 word post gave optimized, Netbeans, McIlroy, atleast, probablity, seeminlgy as invalid. True. None of these were in the word list. "seeminlgy" is misspelt in this post! The checking code took 20.4 ms.

Designing a spell check or corrector. Round 1

2011-05-20T02:30:00.000-07:00

Problem: How to implement a simple dictionary. Given a list of words 60000 words in my case. The tough part is not with checking if a word is in the dictionary or not. It is the correction part that is challenging.

I was aware of how McIlroy used a hash to convert strings and subsequently used the hash as an index into a table. The space compression using bits is also there. So, how to go about the correcting a word. For example, type in the words 'intelligence', 'indelligence', 'itelligance', 'indelligance' into Google search. The search engine asks if you meant the word intelligence. The similarities with all these is how they sound. Even 'entelligant' will get you intelligent. Some reading gave two methods to approach this problem one was to play with the word and making slight changes to see if the new word is in the dictionary. The second is known as the Soundex method that, identifies words that sound alike. The concept of a signature seems to be crucial in this business but the better the signature is in representing all the letter, their sequence in the final signature the more successful the checker will be.

Could the signature itself be used to find the locality of the word if not the word itself?

A simple not so effective solution: I used the most common signature for strings. Given a word 'cabbage' the signature is a2b2c1e1g1. Kind of beats the purpose to store a signature larger than the word. So another common knowledge to use a2b2ceg. This could tell me some relations between the existing word in the dictionary only. But, when it comes to a wrongly spelt word for example 'cabage' the signature becomes 'a2bceg'. Binary search through the signature list will not help because the signature can lead you astray. A modification with a look ahead logic to see if the direction of binary search will yeild a result or close, was also not up to the mark. The real question is whether I need to store the correct words' list. Data structures like tries, suffix arrays all come to mind. But, search engine uses tries to go to the list of pages with that word. Here I just want to correct the word. My instinct says no if I was to go with the first method mentioned above.

I am curious to look at Knuth's description of the soundex algorithm and went through some documents of english words. But, for the time being I feel like abandoning both, although not completely, in favour of a simple approach to do a simple spell correction in a given list of words. More on this as I near a good to disclose method.

Serialization to the rescue

2011-05-14T23:21:00.000-07:00

I wanted to post this ever since I had been through Bentley's articles. This happened when I was working on mobile devices and subject is about exploring alternate solutions for a given software problem, each with its own plus, minus points. The lesson I learned is that, there is always a scope and environment to the code that you write and making the right tradeoffs can get you a solution faster.

The Problem: To display visual warning to users on a PDA (MDA Compact 3 & HTC Qtek S9100) when they cross the speed limit. Simple enough. But, there are strings attached. You have to build the feature on an existing solution which displays a map on the screen and provides navigation, traffic info to the users. The exisitng solution is keeping track of the location via gps <= every second and you have to use that data. Now, the display should be like the speed signs on the streets. You need to provide audio alerts too. Things are not simplified by the fact that, a version of TomTom will also be running on the PDA. PDA has 200MHz processor, 64MB RAM. There is the previous version with still limited features that, the software is to work. How do we show the sign/live feed on the screen ? A sample sign

Solution 1: Since we had the speed info from the existing components, we could simply draw our way through. A good drawing algorithms to put the street symbol with the speed data on the screen. After a couple of runs and stress tests (remember the existing load too), it was not very responsive plus the screen was left in an inconsistent state. Also, the platform was Microsoft Windows mobile, programming was done using embedded VC++ and Microsoft foundation classes.

Solution 2: Show the sign on a seperate window and use MFC window region classes. What about the Sign itself ? Store it in the memory. The device could spare some. So why not? The bottle neck was with the MFC classes in the device sdk. It was stripped down and did not have the full region functionalities. You can set the region but, how to define the circular region? Again a dead end.

At this time I was pretty much finished with Jeff Prosise's Programming windows with MFC. It and other old Wintellect books have been my favourite while on Microsoft platform. Not to mention Charles Petzold. At this time I remembered about Serialization. Yes, that can let you save the state of an object. Aha. So, I can define the region on my desktop and serialise the region classes. Read the region classes in the PDA and use them as I like. I ran back to my workstation to try this out and see the effects of the stress tests. And it worked. Next my test representative and myself took a version with the modification on a field test. It performed better than the other option.

Although there were a number of tradeoffs in terms of memory, response time etc, solution worked. I discussed it with my lead, tech consultant, project colleagues and we had a good laugh.

Oho! algorithms

2011-05-12T12:07:00.000-07:00

Again I have been coding some stuff and analysing the runtimes. This time was the two algorithms for rotating a vector left by N locations. This, a reverser algorithm, is used by Brian Kerningham and Plaugher in their text editor and also by Ken Thomson in the editor for Unix and by Bentley too. So, if ABCD is a vector you want to rotate it by 2 locations to the left, we get CDAB.

The first algorithm is a Juggler algorithm which juggles the values at indices similar to a shift. This is something that, I arrived at and so I will describe the other 'Reverser' algorithm. It goes like this. AB be the string. A is N units length and we want to rotate by N so the result is BA. First do a Ar B where Ar stands for the reverse of A. Then Ar Br. Then ( Ar Br )r. This should give you BA. Brian reported that, this worked first time. I also am glad to report that, it worked first time ;) :)). This is ofcourse if you have a reverse function to do the Ar and Br etc. In my case it is just a switch of array locations starting from the extremities and moving to the center of the array.

The general analysis of the two algorithms is not much a do to share on a blog. The reverser is always better than the Juggler algorithm. They did exhibit some minor changes in their runtimes of the order of 1 or 2 ms.

Well that said, *There is a general question of how the GCD of N and the length of the string figure in the analysis. So, this is what I did (open to questioning).

Input a 1248000 long string.

N is such that, N is the GCD.

At lower values of N (the GCD), both algorithms are the closest in terms of runtimes. Here is N = 4. Almost same. 10 ms and 10.7 ms.

At huge N for N = 1248, the Juggler takes almost twice the time of the Reverser. 6.99 and 13.1.

This seems to be consistent. Anyways, I think I will use the Reverser in my encrypting text editor Crystal. :)

Getting runtime from ~ 15 seconds to 4 seconds

2011-05-10T02:50:00.000-07:00

This is a bit of information on how I got a ~ 15 second program to work in less than 4 seconds. Although the insights are obvious, using the profiler defenitely gave more info than raw intuition.

The Problem: The anagram problem as discussed by Bentley. For a quick example 'rickets', 'sticker' and 'tickers' are anagrams. Using a permutations approach is defenitely unacceptable because of the time complexity. This brings us to the signature approach where we identify anagrams based on signatures. My program uses quick sort to build a signature. The partition code for the quick sort is that discussed by Bentley as I know from my college days the bugs and the confusion involved in coding the partition using the regular method.

The input to the code is a 58111 long list of english words.

Case 1: Using a swap function, quick sort and signature function. Output was dumped to the screen using 'System.out'. The total run time of the program was around 15 seconds. The quick sort took close to under 5 seconds. The screen dump took around 7-8 seconds !.

* I replaced the screen dump code with a write to a text file. So, I wrote all the anagrams (the hash map contents) to a text file. But, this was done using Buffered Writer. This saved 8 seconds leaving the whole code to around 6-7seconds.

This is a general approach I always used.

Case 2: I had a look at the time taken by the functions and noted the following. Notice the quicksort, partition, swap methods in the hot spots window. The invocation frquency for the simple swap is a place to tune. I replaced the 3 line swap code at 3 invocation points in the quick sort. So swap as a seperate function is gone.

Before the substitution was made partition code took colse to 2 seconds. After eliminating the method invocation, it takes 414 ms ! Quick sort now takes 2.3 seconds. But, overall time saved is 2 seconds! Now the runtime is 3.6 seconds compared to 5.5 before.

Case 3: Something I have taken for granted is Horners method in hashing a string. This is explained by Robert Lafore in his book. Hasing the strings took 120 ms.

Case 4: Since we can save time on method invocations, I believed that a non-recursive version of quick sort can have a serious effect on the running time. This was not the case. The self time of the quick sort function was more by 1 second. The program itself was a bit slow by 3-4 seconds. There are more instructions in the quicksort function so, the increase is 'explainable'. The stack which was used to bypass the recurssion was being called, for pop and push a huge number of times. The point is that, the non recursive version of quick sort did not yield anything better. On the contrary it is performing a bit worse (7-9 seconds for the whole program ! looking for the missing 3-4 seconds ).

Crystal v1.0 An encryting text editor.

2011-01-27T11:21:00.000-08:00

I have been coding and developing an encrypting text editor recently after I felt the need for such an editor myself. It protects your text file by encrypting it. It is not complicated to use and has familiar menu actions.

Some technical details.

1. It uses TripleDES key to encrypt your data onto the disk.

2. The data on the disk i.e. the encrypted binary is in base64 encoding.

3. Built out of SUN JAVA.

Features:

1. It performs the actions of a simple text editor well.

2. Provides encryption for the data. TripleDES with a strong key is good enough and is supported by SUN Java.

3. User provides password from which the encryption key is generated.

4. Since it is purely Java it can run on multiple platforms.

5. The data from the file can be copied on to an email text and then you can use it at the other end with Crystal and the password.

Limitations and Future features:

1. Handles only one file at version 1.0.

2. AES encryption on next version.

3. Another thought that came to my mind is that, the encryption module can be used in application to protect configuration files.

Installation:

1. Crystal is here OR http://www.filefactory.com/file/b52f2h0/n/Crystal.jar

2. You will need SUN Java 1.6.x for this to work.

3. Since it used TripleDES you will also need unlimited encryption strength policy files from SUN website here OR https://cds.sun.com/is-bin/INTERSHOP.enfinity/WFS/CDS-CDS_Developer-Site/en_US/-/USD/ViewProductDetail-Start?ProductRef=jce_policy-6-oth-JPR@CDS-CDS_Developer

4. Copy the policy files to your JRE/lib/security folder. Thats it.

Hope you find this useful.

Screen shots

Bit Vector approach in Java

2011-01-16T08:34:00.000-08:00

This is my implementation of the bit vector mentioned in programming pearls. As mentioned in the book the bit vector has execution time and space advantage.1/4th execution time to order a list of 1 million integers in my experiments compared to a quick sort. The execution time was less than a second. The code is self explanatory. May be some more optimization is possible but, this seems ok. The limitation is that, none of the integers repeat in the list plus and integer type is expected for the array index.

An example bit vector representing the numbers 8, 10, 2, 4, 7 is 0010100110100000 with the corresponding bit location set. (0 is inclusive in the list)

/**
*
* @author Hari
*/
public class BitVector
{
   //the array of bytes.
   byte[] bitvector;
   //this is the maximum number we expect in the range.
   int nMaxLimit;
   //byte count needed.
   int nByteCount;
   // the zero mask.
   byte byZero = 0x00;
   //byte values used to set and retireve individual bits.
...................
...................
...................
...................
...................

   // Generate the bytes used to set - reset bits in the sequence
   private void genSet()
   {
   bySets[0] = 0x01;
   for(int nIndex = 1; nIndex < 8; nIndex++)
   {
   bySets[nIndex] = (byte) (bySets[nIndex - 1] << 1);
   }//for
   }//

   // Initialize all the bits to zero.
   private void setAllToZero()
   {
   for(int nIndex = 0; nIndex< nByteCount; nIndex++)
   {
   bitvector[nIndex] &= byZero;
   }//for
   }//

   //set the nth bit in the array.
   public void setAt(int n) throws Exception
   {
...................

...................
...................
...................
...................

   locInVector = qt;
   bitvector[locInVector] |= bySets[7 - rem];

   }//

   // check if n is in the vector. i.e by checking the nth bit in the byte array.
   public boolean isPresent(int n) throws Exception
   {
   if(n > nMaxLimit || n < 0)
   throw new Exception("Argument outside range of bit vector.");

   int locInVector;
   int qt = n / 8;
   int rem = n % 8;

   locInVector = qt;
   if((bitvector[locInVector] & bySets[7 - rem])==0)
   {
   return false;
   }
   return true;
   }//

...................
...................
...................
...................
...................

}//class

Alpha Rex Complete

2011-01-12T13:25:00.000-08:00

I finally finished the Alpha rex robot. The head and hands were remaining from where I left it last time. The hands are operated using a single motor using lever, gears like lego blocks which is pretty amazing. The hands do not do much apart from being able to move as in the video.

Overall pretty impressed with what lego mindstorms came up with. Now remains using regular code rather than vpl.

The video is here
http://www.youtube.com/watch?v=9WuMRkO8lSk

Cloud Computing 2. Ground level

2010-12-15T06:50:00.000-08:00

‘Cloud computing is a type of computing that provides simple, on-demand access to pools of highly elastic computing resources. These resources are provided as a service over a network (often the Internet), and are now possible due to a series of innovations across computing technologies, operations, and business models. Cloud enables the consumers of the technology to think of computing as effectively limitless, of minimal cost, and reliable, as well as not be concerned about how it is constructed, how it works, who operates it, or where it is located’.

This did not help much though when it came to a complete non-tech person. So, I again use an example that was used in the seminar I attended. Consider your work place in an IT company, you may be availing a lot of services such as email and intranet sitting at your computer. If you are accessing a leave management system like I did some time ago, you could look at the back of your computer and see a network cable. Following the cable you end up on the socket on the wall and then you plough out the lines and still follow them to a switch then to a router and you finally find yourself in the server room of your company. Then, you follow the cables to the server that, was hosting the leave application software for everyone in that location. So you have pin pointed the fixed server/hardware, the room, the air conditioning, the people who maintain that (by this time you should have met them), saw the power supply, back-up and the like. Now you get the general idea. You, the user, located it feeling.
Now, if you ended up in huge warehouse with containers upon containers (holding the cable of course), and you see that, there is a lot of hardware with thousands of network connections going to as many stacks and you simply cannot pin point which one is your application server by yourself then, you are dealing with a cloud. Basically, you may have ended up with something like this.

http://www.youtube.com/watch?v=K3b5Ca6lzqE

There is a video of the Google Datacenter too.

Notice/see the mentioning of network, storage, cooling, power supply etc which you might have located in your server room too but, in a minute scale compared to this. So your data, application are on some server that is in this huge software + hardware infrastructure. There might be someone else’s data, application residing there too.
So did this explain the concept? It does not seem to be so very new outright but, the approach as we will see to utilizing such hardware software infrastructure and deriving advantages from it is new.

Cloud Computing - 1 The beginning

2010-12-15T06:45:00.000-08:00

I have been reading up on a number of stuff the past couple of months and have consolidated stuff to put on my blog. One of the topics is cloud computing. This was rather vague in the sense that, if, I referred to any material couple of years back I used to get different ideas. But, a seminar I attended recently helped me to get some basic ideas to build upon.

What is there so much to understand about cloud computing? You may ask. Rather than being able to work with it in all its glory, you would be better off if, you can explain simply and clearly to an executive, preferably from a non-IT background, about the what is, how, why of cloud computing. Not agreeing to this? A lot of literatures just do this and only this. Why? Because as long as the execs don’t see the up-side, no computing is going to take off. So explaining the whole idea, selling cloud seems to be challenge I am facing now. So who started all this? A colleague some time ago asked how I would explain cloud computing to my grandma and expect her to figure out some advantage on her own. I am never going be able to explain to my grandma because, she is not around. But, the idea was still hanging around. After this, I just continued with my reading to understand cloud more and pursue some development too.

The rest of the stuff such as developing something to run on the cloud for an example, using the Google App Engine etc is left to books and technology literature directed at the tech people. I am going through these too and will put on some stuff as I progress. These will be totally technical and nothing in the direction of the para above.

The next few blogs would focus on specific aspects/points that, I got from my literature review which I did not come across in general.

Fun Fun Fun with Robotics

2010-10-27T09:24:00.000-07:00

This is yet another part of a new interest I developed. Its Robotics Again. I was building the walking mechanism for the alpha rex on Mindstorms.

It took me a while to build it manually, and the VPL program was larger than most other examples.
It was all worth the effort. Why? There are a lot of reasons for a software engineer to be happy with this.

- First, not a single line of code has been written!! All the instructions are using the VPL that comes with the mindstorms studio. Yes, it does compile and all that stuff but, hey I did not have to type in the code. I was dragging 'logic blocks' to get the job done.

- Second, with this a software engineer can imagine something and he has to imagine not only the logic but, also dream something that is mechanically feasible.

- Third, you have to build it mechanically!!. Finally, something tangible compared to the programs and processes.

The walking mechanism is here in this video

http://www.youtube.com/watch?v=s9h9i2o8YnU

The touch sensors usage is very very impressive so is the technique used to walk. Stuff written on the package is true. 'Only three motors, 2 touch sensors, ultra sonic sensor, color sensor but a lot of possibilities'

Visual Programming Language - Lego Nxt2.0 Robotics Kit

2010-10-25T03:28:00.001-07:00

In 2008 I attended a career exhibition at Cardiff City Hall. There were a lot of companies who had put up a booth to guide to-be-grads in the room . One particular company Texas Instruments got my attention with their equipments (looked more circuit like) on the desk. I gave them a visit and the guy there eagerly explained to me how their equipment measures my temperature, heartbeat ... while I was holding a metal wire!! Then, we struck a techie cord and he started talking about other stuff like Visual Programming Language and then about Lego Mindstorms Robotics kit. After listening to all that, I thought that, I should get to know this VPL thing and Mindstorms Nxt.

I had a copy of MS Robotics Studio and played around with the studio. Missing was the sensors and motors i.e a robot kit.

Recently, I got a Nxt2.0 Kit and started doing some VPL programs and running it on the servo motors, sensors in the kit.

1) It is really nice to see and use the VPL studio that comes with the kit.
2) Even though there are only a limited number of sensors and motors, there is a lot of things that can be imagined and programmed.
3) Not to mention that, MSRS is compatible with this kit and we can code specifics in addition to the VPL capabilities.

When you read a books on Robotics, you see terms like actuators, sensors, services, concurrent execution etc and it was upto imagination to piece them together. But, with a kit like this it makes understanding things a lot more easier.

I tried out a few of the vehicles and really enjoyed building and programming with VPL. One of the sensors I really like is the Ultrasonic sensor that can be used to measure distance. The shooter robot was really interesting. The technique to shoot the colored balls is really impressive. (old pool game idea). My bot was ready and I gave it a try.

The video is here ---> http://www.youtube.com/watch?v=bhB_lYPPCto

It senses when some thing comes closer than one foot and fires. Simple. The villain was the only thing I can get my hands on before the batteries ran dry, a rolled up carpet.

Next would be Finishing the alpha rex humanoid and then moving to using custom code with this.

And yes, there are a lot of other robots and kits you can get your hands on these days. But, this is definitely a good place to start.

Comments on Two books.

2010-09-22T21:59:00.001-07:00

Here are my thoughts on two books that, I have been through.

1) Code: The Hidden Language of Computer Hardware and Software. From Charles Petzold.

After hearing a lot of praise for this book, I decided to give it a go myself. During my bachelors, I had gone through books in basic computer science, operating systems, computer networks etc. As an eager-to-learn reader, I felt, this book from Charles Petzold is different in the following ways

- It does not start with a chapter 1 scare about computers, digital world taking over your life.

- Enjoyed the progress from Chapter 1 - 15. Things like Braille, Morse code, Telegraph, relays

are described from a different perspective. Without having the end result/objective defined,

the chapters build on what is simple and available to expand concepts. This is absent in all

other books I have been through.

- Earlier attempts at code / represent data are interesting.

- The book is a progressive sequence of thoughts leading to understanding computers, from oh! to ah!. If you already had taken subjects like digital logic/electronics during study, you might find this a replay. Only that, in semester study you get air-dropped right in the middle of details and learn from there.

Only downside is, I felt that,

- the fine-grained description of what each company / corporate / individual did could have been avoided. It was enough for me to know that, XYZ inc came up with yet another approach/processor. If I wanted to dig into that, I would read another specific book. Just that, such descriptions are out of the scope of this book. Not to mention that, it is enough to kill the spirit of reading the rest of the book and put you to sleep.

- This book should have come out 10yrs ago as the author says. I wish it had.

This is must have for High-schools', colleges' libraries or anyone who is interested in understanding how computers work and see through the layers of abstraction.

2) Practices of an Agile Developer by Venkat and Andy.

What can I say? At least, the authors don't guarantee success with agile.

- This book is for people who don't understand that, software engineering involves great people/teams empowered by good enough process/methodology. Even agile can't help if this is not understood.

- If you are a developer with discipline, skip this book. You are already way ahead.

- A plus side, you can finish it in hours!!

Protect Shred Throw away

2010-08-25T02:42:00.000-07:00

2 softwares that are useful if you are protecting information on your machine.

1 Software for storing passwords for users.

1) True Crypt.

This software allows you to protect information with encrypted container files, hidden volumes and hidden operating systems. Simply you follow the instructions to protect your data files with encryption.

2) PGP

I was under the impression that, the software turns features off after 30 days. But, the pgp author mentions that, it would simply continue to work. So, I am trying this especially the shredding part. This software can shred empty spaces in the disk or files.

Both these softwares can be used when you a throwing away your hard disk. Cryptographically erase data.

3) Password Safe from Bruce Schneier

This is an extremely useful piece of software for people who have loads of ids and passwords.

Instead of using a commercial application that drags your system down, this can be easily used with little or no performance hit. It allows you to create a username, password, tag to describe where this is used, credential groups. Simply drag the name / password to the corresponding edit boxes in other windows. The password data base is itself encrypted and just remember the master password.

Extremely useful software.

Google it. Download it. Try it

Development environment

2010-07-21T05:33:00.000-07:00

If you are embarking on software development or programming seriously then you need a environment, as George Carlin would say, to "put your stuff".

My requirements for a development environment are.

1) It must be reasonably fast. Windows Xp? not a chance. Have tried.

2) As I progressed over the years, doing coding projects as learning and now after 4 months tops, the file system is confusing to even myself. tons of versions of jre, shell scripts add to the confusion. On a short notice I want a clean system. i.e No installation of any sorts allowed. I don't want to worry if my previous pet project is gnawing at the current one.

3) Backup ! If something goes wrong on a monday morning, I want to just revert back and continue breaking things.

4) I should be able to make things tick with scripts when ever necessary. I hate windows scripting.

5) Need a strong, flexible shell.

6) Make private networks without the physical machines.

I have used linux in the past and found it to be the best. I was not going to install a development environment on my Xp laptop. Definitely not for Java development. If it was for visual studio then, ok. But then, linux as a VM seems to be my choice for quite a long time now. The reason is that,

I found a number of ways to make this OS fast from other blogs. Search for it on the web!. Some things to do are

- change swappiness

- services. Used Yast to disable unwanted ones.

- Look and feel for best performance

- on Vmware server settings make sure that the entire vm memory is on physical memory.

- visit inittab and strike off unwanted stuff.

- Allocate all the disk space. Some blogs say this is unnecessary but, I found it to be otherwise.

- list all processes and continue filtering.

- Disable CD drive.

- Disable USB.

One way to see the changes is to list the number of processes running on your vm. Mine has 56 processes and without X windows 38. The vm is more responsive with heavy IDEs like RAD. Well, faster than my friend's Ubuntu on physical machine!. (My VM has only 1.3 GB RAM)

So to be precise

1) Use a Virtual Machine.

2) Use Linux.

3) Use Xming or Similar tool and avoid UI on your VM.

Elevate thinking on Software Development Models.

2010-06-06T09:04:00.000-07:00

If you have been to presentations on Software development models then, you have been exposed to this.

a) Someone is talking about a new model.
b) The benefits list is longer than your shopping list.
c) There are also convincing Wow! Wow! examples.
d) It is some thing very different from all the models you have ever seen, heard or used.
especially that mean Waterfall model.

Then, the all time champion false claim

e) The model is promised to deliver you success at all times !!.

Here is what I think.

1) The Waterfall model gave us the basic stages of software development. That's the truth. Face it. It is NOT a guaranteed to fail. It might fail.

2) Every Software model has all the stages laid out by the waterfall model. Rarely do you see a new phase in the new models.

3) It is how you string these phases together, how much effort you spend in these stages, that makes the difference and the different models.

The questions to answer before adopting a new model.

1) What is the process you are following now?

2) What precisely is wrong with that process?
- Look for answers in Cost, Effort, Schedule.
- Get the numbers straight for the above three.

3) How much is the new process profitable in the above three?
4) Is this worth the shift?
5) Above all, Is your business process, team process compatible with the new model??
i.e can you map it to your processes?

These basic questions can set things really straight.

Windows Server 2008

2009-08-17T22:13:00.000-07:00

http://blogs.msdn.com/vijaysk/archive/2008/02/11/using-windows-server-2008-as-a-super-desktop-os.aspx

http://h0bbel.p0ggel.org/windows-server-2008-as-desktop-laptop-os

ShopEasy v1.1

2009-07-07T04:48:00.000-07:00

I am happy to release this software for Windows mobile devices.

About ShopEasy v1.1:

Ever been to a super store, walked through all the isles and been back home just to find that you forgot to buy something? or simply don't have the memory to remember the long list of shopping items. Then this is for you.

ShopEasy is a software designed for Windows Mobile 6.1 devices and helps you to shop!

It helps you to maintain your shopping list in a simple and easy to use manner. Before you go shopping, just run the software, select them items you want to shop and away you go, never to forget an item. You can keep track of items as you buy using the software so that, you are never in doubt if you have bought it or not.

Features:

1) Easy and Simple way to maintain your shopping list.

2) Help Facility for software.

3) Fast and efficient.

Specifications and Requirements:

Devices: Windows Mobile 6.1 devices. Screen shots from HTC Touch Diamond.

You will need: 1) Microsoft .Net Compact Frame work 3.5 to run the software. You can download this from Microsoft Website.

Your experience and suggestions in using ShopEasy are welcome. Enhancements will added and new versions will be uploaded soon.

Download:

v 1.1

-----

Link: http://www.filefactory.com/file/ahb4046/n/ShopEasyInstaller_CAB

To prototype or not to prototype

2009-04-24T12:12:00.000-07:00

All engineering disciplines frequently use scaled down models to prove a concept before actually building something real or the real thing. This is the case, be it related to building architecture, bridges or aircraft manufacturing. So what about software? As an answer comes up the word, prototyping. The question is whether to or not to prototype? The question deserves special attention in software domain. This is due to the following reasons. First, software is created by developers who are unfortunately not the end-users of the product. Second, the end-user is not usually involved in specifying what they want, be it to see, type in or interact. In addition to that, the so called requirements get passed through quite a lot of hands and is perused and interpreted by the lot too. The funny thing is that, each will have an idea of what needs to be done, let alone how and with what. When this comes to the developer again there will be an interpretation of what is to be done. Finally, what the user wants is in his/her head and cannot be elicited in one go or so. The end result of this can be an unhappy user who thinks the software is useless or an irritated client who thinks the real objective was not met. For the developer this result can manifest as anything from, burning down new screens the user wants, dealing with the so called ‘changes’ to re-doing the whole thing.

If you have been in any of the above situation then you need to think of prototyping. First about what benefits it brings. Prototyping can help in the following ways

- If your team has thought of a concept which is core to building the solution. Prototyping can help in proving this concept. If the prototype proves your concept wrong, then you are in a position to plan accordingly rather than having to re-trace in the middle of development. It can also uncover any mistakes in your concept.

- You might have designed the solution with application layers and so on. Prototyping would be helpful in making sure things will get along as they were planned in the first place. If things do get along, you have something to look at when you build the real thing, a distinct advantage.

- It can help in comparing technologies that can be utilized to deliver a solution.

- You can identify bottle necks earlier which otherwise unnoticed will surface as impediments. i.e you make things as risk free as possible at an early stage.

- Above all, the user/client when presented with the prototype will start talking more than you expected. You will get a clear idea of ‘what they want to see’ and how they want to interact with the solution. I.e your interface will be change-proof as much as possible. There will be a better understanding between the two.

As for the downside of prototyping, besides the fact that it takes time, there is nothing horribly wrong with the idea at all. The problem stems from the fact that, not many people in the field understand the need to prototype and if they do, they lack the knowledge of how to prototype. The followers of the perfect world of waterfall model where things go in order or anything similar fall into this category.

In short, prototyping does help a software development team to move in the right direction based on facts and deliver what the user wants in the first go itself. i.e if you have not been able to deliver the right product in the first pass, you should think about prototyping.

Six Sigma and Software Development

2009-03-15T05:41:00.000-07:00

The software domain has its own set of tools, concepts and management processes, techniques to ensure quality and the success of a project. Some of these are development methodologies like Agile development and others are process management techniques like CMM and its process areas. But, Six Sigma, its ideas and concepts did not evoke an interest in Software engineering domain as it did to the manufacturing doamin. In fact, software engineers and IT project managers are still confused as to how and where to apply this concept and related tools in software 'product' development.

At the end of its life cycle software is a product that, is used by a user/client to realise their goal. Quality, reduced variation from user requirements, reducing cost, well informed decisions, increased customer satisfaction are all important to the IT software industry as it to the manufacturing industry. These are things that Six Sigma aims for and the way to do this is even better in Six Sigma. If so, then software engineering and management can adopt quite a lot if not all, from this strategy. The initial skepticism can be removed by replacing the terms client/user (in Software domain) with customer (Six Sigma), issues (Software) with defects/variations (Six Sigma) and Software/System with product. The only hurdle in the case of softwares is tangibility. Again, 'Changes' are common to software development processes. Also, it is most unwelcome and software engineering processes tend to be brittle when it comes to managing changes. This is because most of the process models such as CMM tend to keep processes prognosticative. So they are uncomfortable with Changes. This 'Change' is also core to Six Sigma and But, is addressed very effectively. In short, Six Sigma should not be alien to Software Engineering companies which in turn can definitely reap great benefits by applying this strategy.