Differences between Semaphores and Mutexes

11, Apr 2011

What are the differences between semaphores and mutexes?. Are binary semaphore and mutex same or just a notational convenience?

It is typical interview question. Surprisingly, we get correct answers rare.

From my learnings during RTOS design, I am preparing an article for Geeksforgeeks (link), it will be published soon.

An interesting question, if you observe Windows word 2003, Adobe PDF reader, only one instance will be running in the task manager. Where as Windows Excel 2003 will create as many processes as number of excel documents opened. How to implement, only one instance of process must be running, invoking another instance should prompt "An instance is already running" message?

Beautiful Architecture - Worth Reading (Productive Weekend)

10, Apr 2011.

Got new book "Beautiful Architecture". I got the book from local book shop. Good to know that the royalty on the book will be donated to "Doctors Without Boarders".

The book is collection of essays from experts that designed high end, and high availability systems. Yet to finish few chapters, left good learning experience.

Few topics to name,

1. Scalable Architectures

2. Resource Oriented Architectures

3. Data Centric Architectures (Facebook)

4. Virtualization (Xen Hypervisor)

5. Fault Tolerant Operating Systems

6. GNU Emacs and KDE (Qt)

7. Metacircular Virtual Machines

Happy and worthy weekend.

An Interview Experience

8 April, 2011

I don't like to present in interview panels unless really required. Today I had to be in an interview panel. Good puzzle I recapped after long time.

Two players A and B playing a game (similar to game of Nim). Given a pile of N coins, the players need to pick coins from the pile. In each move a player can pick atleast 1 and utmost m coins. The player who makes the last move is the winner.

For example if A starts the game, he can pick 1, 2, 3, ... m coins from the pile. Then B can pick 1, 2, 3, .... m coins from the remaining pile. Next A, followed by B, so on...

In the process, the player who makes last move (picks all remaining coins <= m from the pile) is the winner.

Now, given N = 15, m = 3, and A starts the game with some 1 <= x <= m coins. How many different ways are there that A can win the game?

Hint: Use state space analysis method (i.e. trees).

Pascal’s Identity - Theoretical Significance

April 8, 2011

We know that C (n, r) = C (n – 1, r – 1) + C (n – 1, r)

It is quite easy to prove it mathematically. But what is its significance in real life examples?

C (n, r) is selecting r elements from n elements. Pick a special element k from these n elements, we left with (n – 1) elements.

Now this r elements selection C (n, r) can be grouped into two categories,

A)      r elements that contain the element k.

B)      r elements that do not contain the element k.

From A) the special element k is in all r selections. Since k is part of r elements, we need to choose remaining (r – 1) elements from remaining (n – 1) elements, this can be done in C (n – 1, r – 1) ways.

From B) the special element k is not there in all r selections. It means, we will have to select all the r elements from available (n – 1) elements (we must exclude element k from n). This can be done in C (n – 1, r) ways.

Now it is evident that, the first term of RHS is combination containing special element k, and the second term is combination without the special element k. Sum of these two is selecting r elements from n elements.

Interesting proof, little confusing to understand, but useful in practice.

Pascal's Identity and Dynamic Programming:

If we note the identity, it is the base for recursive calculation of binomial coefficients. However, when plain recursion is used, it will lead to an exponential algorithm.

Recursion with memoization can result in an efficient algorithm. The idea behind this dynamic programming (programming we mean a method of tabulation) is to tabulate the first occurrence of binomial co-efficients.

Pascal's triangle can serve as the tabulation in the dynamic method. Each co-efficient is sum of coefficients in the previous row. The table can grow till min(k, i) where 0 <= i <= n.

Try the dynamic algorithm.

Note that there is no need of two dimensional array to memoization of partial results. This fact is evident from Pascal's triangle with an extra variable to store nCk.

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.