Programming Style - A discipline of writing code

29, March 2011


Discipline is simple, yet powerful word. However, the meaning can vary from person to person (Remember that practice is always different from law :)). The same applies to programming.


When writing code we never exercise importance of meaningful and precise comments. I have seen many code snippets on Geeksforgeeks and other forums. Most of the code snippets posted by readers are missing comments. Readability, maintainability (simplicity), clarity and generality are key to write elegant code. Brevity also key principle of writing code.


Note that geting it right (or code is fine since it is working.... bla bla) are poor reasons to convince ourself. Accept comments if they are adding value.


About 2 years ago, I had written a program in Perl script to extract symbol table from binary executable. It was about 5000 lines. Yesterday I reviewed it again, based on a call from previous teammate. I am proud that the code is well commented in such a way any engineer in future can take it forward. I could able to recap all the data structures, algorithms easily from the comments.


I would recommend to read The Practice of Programming by Kernighan.

Tournament Tree and Winner Tree

March 19, 2011.

How many minimum comparisons are needed to trace second smallest element in an unsorted array?

We can use a tournament tree approach based on adversary argument to prove minimum number of comparisons.

In tournament method, every number (element) is paired with other number successively to find the maximum number. This forms a tree like structure. We must have N - 1 comparisons to find maximum number.

The information gained while finding max number will be used in reducing the comparisons for second largest. It meas, we would need to consider only those which lost against max number to be considered for second largest.

From the tree structure, we can conclude such lost numbers can't be more than [log(N) - 1] (consider tree height).

Overall, at minimum we need ( N - 1 + log(N) - 1 = N + log(N) - 2 ) comparisons.

Read my post on Geeksforgeeks for details on Winner tree approach.

Count number of set bits in an array

There are various techniques to count bits in an integer. These methods can be integrated to count bits in an array. I have published a simple and efficient method on Geeksforgeeks.


In the post, observe the meta program using C/C++ preprocessor that generates code for main program.

Minesweeper program

A nice program written in Qt and Python.

For details see the following link,

http://lionel.textmalaysia.com/minesweeper-in-python-gui.html

Last week KDE India meeting was organised. The above program was explained by KDE geek Dinesh Sai. Thanks to him.

A puzzle (mathematics) - properties of decimal number system

5, March 2011.

I come across one geek blog, and there is one interesting question... "Given a number containing all numbers from 1 through 9, find next higher number with same digits!".


The question should trigger a hint. "Same digits" mean the next higher number will have all same digits (In other words, the difference between N and N_next should be multiple of 9). Since all the digits are same in both the numbers, difference between the two numbers will cancel out, and makes the next higher number increase by a factor which is multiple of 9. Also, since the number is higher one, we should look for increasing patterns from right to left.

For example consider


N = 125786493


We can see 125786439 can't be next higher number. We must look for first three digits. 125786493 should be transformed to 125786934 with a difference of 441 which is multiple of 9. Or simply 49 x 9 (observe the original number).


Another number - 157869324 transformed to 157869342 with difference of 18 = 2 x 9. Obviously, there is a pattern.


Logic is clear, can we write the program easily, ....? Not really! Try out.


Another variant "Find the next higher number with same number of set bits", I had published an article here.

How many levels?

4th, March, 2011

Tree is one interesting data structure in computer science. I like the properties of trees and graphs.

Sometimes we receive some junk mails, containing junk information something like if you don't forward the mail to next 3 people something bad will happen... bla... bla... bla... and some more BS... (these mails usually related to God, even if-at-all God exists, he might be laughing at such mails. Recently I have seen a funny mail, I will post on http://wemeanourthoughts.blogspot.com/ fun to read).

But as an Electronics and Computer Science Engineer, it fascinates me to find how many pages would go for waste because of sense-less people.

We can represent the above mail chain as an m-ary tree. Where m is the branching factor, such as 3 in the above case.

As a simple math, if the mail chain ends at L-th level, how much space would they all occupy in mail servers (ofcourse this is apart from the space on user machines, assume each mail takes few MBs since those mails contain pictures as well)?. It would be in few Giga Bytes of space.

If all the persons at X-level changes the number 3 to 6, how the output will be affected?

Reverse (Synthesis) Question:

Given there are N leaves in a binary tree, how many levels an optimally balanced binary tree can have?

Answer: log₂N + 1

In general, an m-ary tree with N leaves can have log_mN + 1 levels.