3. Puzzles

1. Find the switch
There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.

Gee, I surprised my self by putting this age old thing here. Buy anyway.

Ans.Switch the first one on for a couple of minutes then switch it off, switch the second one on, and keep the third turned off. Get into the room, the first should be hot and not lit, the second is lit, and the third is cold and not lit.

2. 100 doors
you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

question: what state are the doors in after the last pass? which are open which are closed?

Ans.
solution: you can figure out that for any given door, say door #42, you will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the door, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close. for every pair of divisors the door will just end up back in its initial state. so you might think that every door will end up closed? well what about door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square doors will be open at the end.

3. Color of Hat
Four men are lined up on some steps. They are all facing in the same direction. A wall separates the fourth man from the other three.
So to summarise: -

Man 1 can see men 2 and 3.
Man 2 can see man 3.
Man 3 can see none of the others.
Man 4 can see none of the others.
The men are wearing hats. They are told that there are two white hats and two black hats. The men initially don't know what colour hat they are wearing. They are told to shout out the colour of the hat that they are wearing as soon as they know for certain what colour it is.
They are not allowed to turn round.
They are not allowed to talk to each other.
So the question is -
Who is the first person to shout out and why

Ans.
The man who calls out is Number 2. Why?

After a short time, Number 1 has not shouted out what colour hat he is wearing. Because of this number 2 knows that he cannot be wearing the same colour hat as the person in front of him. If he was then number 1 would see two black hats and would therefore know that his hat must be white.

Armed with the knowledge that :-

He isn't wearing the same colour hat as the man in front.
The man in front is wearing a black hat.
number two can confidently shout out that the hat he is wearing is white.


4. Angle of Hour Hand
An analog clock reads 3:15. What is the angle between the minute hand and hour hand?

Ans.
12 hours on the clock make 360 deg. so one hour is 30 deg. the hour hand will be directly on the 3 when the minute hand is at 12 (3:00). after 15 minutes or 1/4 of an hour, the hour hand will be 1/4 * 30 deg = 7.5 deg. away from the minute hand.


5. Need to cross desert
An explorer wishes to cross a barren desert that requires 6 days to cross, but one man can only carry enough food for 4 days. What is the fewest number of other men required to help carry enough food for him to cross?

Ans.
Three men, each with 4-days of food head out (day 1).
The next day eachhas three days worth of food.

The first man gives one-days rations to each of the other 2. That leaves him with one day's rations to go back.

The other two, now with 4-days of rations continue (day 2)

The next day the second man gives one-days worth of rations to the third man. The second man has 2-days of rations to go back. The third man now has 4-days of rations to make the 4-day trip across the desert.


Next Puzzle here

2. Puzzles

1. Count 16 Hrs

John has a small and a large hourglasses. The small one can measure 5 minutes and the large one can measure 7 minutes. How can he measure 16 minutes with 2 hourglasses running together?

The rule is when any one of the hourglasses finishes leaking, that hourglass must be flipped over immediately to keep it running

Ans. Steps Below

7m             5m

2/5              0/5     => Tot =5
0/7              3/2     => Tot = 7
5/2              0/5     => Tot = 9. Here flip the 7m glass
0/7              0/5     => Tot =11. Flip 5 min glass
0/7              0/5     => Tot =16


2. Which egg is lighter
Eight eggs look identical except one is lighter. How can you weigh only 2 times on a balance scale to find out which one is lighter?

Ans. Split into 3 groups 3-3-2.
Measure 3 against 3.
If they are of same weight:
lighter ball is among 2 ball, weigh them to find the lighter ball. (So total weighed 2 time)
Else 3-3 are of different weight, take the lighter pile
weight 1-1, if they are same, left out ball is lightest. Otherwise you know it (total in this case too 2 time)

3. Which coin is lighter
There are 80 pieces of gold. One of them is lighter. You can weigh only 4 times to find out which one is lighter

Ans. Based on same concept as question number 2 above.
One of many solution is below.
Slit 30-30-20.

Weight 1: 30-30
Case 1: they are equal, then coin is in 20's pile
Split 8-8-4
As you know this problem is same as question number 2 which takes 2 weighs to find out the lightest. So total weight would be 1+2 = 3. Means we are game.

Case2: one of the 30's pile is light.
split 12-12-6

Weight 2: 12-12
if one of the 12's pile is ligher

split 8-4. Which again is problem number 2 and max weights would be 2+2 =4.
 Finding lightest among 6 coins is again 2 weighs.

Problem is solved.


4. Cross the Bridge
There are 4 women who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross
For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. What is the order required to get all women across in 17 minutes? Now, what's the other way?

Ans.

1,2,5,10----------------------
5,10--------------------------1,2 Tot =2 mins
1,5,10-------------------------2, tot = 3 mins
1-------------------------------2,5,10, tot = 13 min
1,2-----------------------------5,10, tot =15min
---------------------------------1,2,5,10 tot =17 min


5. Ratio of color in bucket
 If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.

Ans. Same
let the volume of buckets be 2 L each represented by 2x and 2y ( x for bucket 1 and y for bucket 2).
so initially A=2x , B=2y
let the volume of cup be x.
so after [ step 1 ] : one cup red paint from bucket 1 to 2
A=x L and B = xL + 2yL.
so ratio of paints Red:Blue in red bucket = 1:2

[step 2] : one cup paint from bucket 2 to 1
so B = x + 2y - [ (1/3)x + (2/3)y ] = 2x/3 + 4y/3
and A= x + [ (1/3)x + (2/3)y ] = 4x/3 + 2y/3

so coeff of x in a = coeef of y in B.



More puzzles follow here

1. Puzzles

1) Which Pill is contaminated
You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?

Ans. Take 1 pill from Jar1, 2 from Jar2, 3 from 3, 4 from 4th and 5 from 5th.
Now, if none of the pills were contaminated, total weight would be (1+2+3+4+5)*10 =150.
As one of jar would be contaminated, weight would be less. If its less by 1 gm, jar is jar 1 and so on.

 2) How would you measure 4 quarts
If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

Ans. follow below
               5quart           3quart
step1:        0                  3
step2:        3                  0
step3         3                  3
step4:        5                  1 (poured water from 3 quart to 5, we will have 1 quart left)
step5         1                  0
step6:        1                  3
step7:        4                  0


3. Pick 2 of same color
You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same

Ans. You have to consider worst case scenario, i.e. what ever you pick are all different. So if you pick 4, it will have at least 2 of same color.


4. Defective Ball
Among 12 identical looking golf balls there is one that is defective in weight. It is either heavier or lighter than the standard one. You have a balance. You can only weigh 3 times to find out which one is defective and whether it is heavier or lighter

Ans. Note the cache here is, we don't know whether defective ball is heavy or light.
first take 3 balls on one side of the scale and another 3 balls on the other side of the scale. If they don?t weigh equal then the defective ball is here in this bunch.
if they weigh equal then defective ball is in the set of other 6 balls.Thus we have 6 balls in which we need to find out the defective one.
now the bunch of other six balls are equal weighted..take 3 balls of from them and weigh them with the bunch of 3 balls of the above weighted, if they are equal then defective ball is in the other bunch of 3 balls and if they are not equal defective ball is in this 3 ball set.(if this set weighs heavier than the ideal group of 3 balls {that we have selected from the remaining set of 6 balls} than defective ball is heavier and vice versa. now we have 3 balls..take any 2 and weigh them with the other equal set of 2 balls..if they weigh equal then the remaining ball is defective..and if they don?t weigh equal then the ball which is heavier(as we have assumed the set if 3 is heavier than ideal set in the second step.) is
defective in the scale.

5. 12 ounces of water
There are 3 glasses. The biggest one can hold 24 ounces. The medium one can hold 11 ounces and the smallest one can hold 5 ounces. Now you have 24 ounces of soft drink in the largest glass. Can you use just these 3 glasses to make the largest glass contain 12 ounces of soft drink by pouring soft drink from one glass to another?

Ans. Follow these steps
      24_B     11_B   5_B
1)   24          0          0
2)   13         11         0
3)   13         6           5
4)   18         6           0
5)   18         1           5
6)   23         1           0          
7)   23         0           1
8)   12        11          1


continue puzzling your brain with next post

ARM Architecture

ARM Architecture in naive terms.

ARM is 32 bit architecture. It is based on the RISC cpu design. It means if has fewer instructions set.
Fewer instruction set may mean
a) Limited functionality.
b) Less power demand. Using the RISC approach, the ARM processor requires only 35,000 transistors, compared to the millions in many conventional processor chips, resulting in a much lower power usage

Normally a) above is okay, as in small embedded devices need 'not' to perform zillions of operation as required by the Home PC. But, by design ARM also has improved data store and transfer capability during various calculations.  This makes processing more efficient

About b) above,  Ah, thats what we need for hand held devices. Long battery backup.


Refrences:
http://en.wikipedia.org/wiki/ARM_architecture#cite_note-cortex-a50_announce-22

Symbol Resolution, Weak Symbols, How compiler resolves multiple Global Symbols

Whats Symbol Resolution

Linker need to find the definition of all global before generating an .exe or .out file. This process of finding and association each global symbol with a definition is called symbol resolution (again talking in loose term, avoiding shared libs).

For local symbols, resolution is straight forward, the local symbols must be defined in same module. For static local/global variable are also kind of easy, compiler wants them to be defined in same compilation unit i.e. a file.

However, resolving reference for global variable is tricky. When compiler encounter a global undefined symbol, it makes an entry into the linker table, assumption here is that it must be defined in one of other modules.

If after all of its tries, linker is not able to resolve the the global symbols, it generates a undefined symbol.

There is also one more level of difficulty of global symbol resolution, what if global symbol is defined in more than  one linking modules.



How Linker Resolved multiply defined Global symbols, Strong/Weak Linking

At compile time compiler exports each global symbol as strong or weak to the assembler. Assembler add this information into the symbol table.

What goes as Strong symbols
All function definitions, all initialized global variables.

What goes as Weak symbols
Uninitialized global variables.

Rules of resolving multiply defined global symbols
1)  Muliple defined global symbol found, they are given as linker error.
2) Given a strong and a weak symbol(s), linker chooses the strong symbol.
3) If multiple weak symbols, linker is free to choose anything. 

So, be very careful for rule 2 and 3 as you would be in blind spot linker wont stop and give you any error and you may get unexpected results.

e.g consider this example for Rule 2.

/* file1.c */
#include
int glob = 100;
int main()
{
   file2Fun();
   printf("%d", glob);
   return 0;
}


/*file2.c*/

int glob;

void file2Fun()
{
   glob = 200;
}


Well, if you know rule 2 you wont be expecting value of global  as 100 anymore, because file2.c effectively access glob of file1.



 consider this example for Rule 3.

/* file1.c */
#include
int glob ;
int main()
{
   glob = 100;
   file2Fun();
   printf("%d", glob);
   return 0;
}


/*file2.c*/

int glob;

void file2Fun()
{
   glob = 200;
}


IF this is the case, you would never know what would be the value of glob. As both places symbol is weak and linker is free to choose any.

Even more difficult type of buggs would welcome you if suppose in one file glob is define as int and other file as double. If you try to use glob as double variable you may not be able to store those bigger values there. 

Error Correcting Code, Error Detection and Correction, Checksum

Error Detection and Correction (EDC)

Engineering is such a beautiful field, how brilliant minds are able to find awesome solution to the difficult problems.Error detection and correction is again such an example. As you have reached this post, try to think and generate a strategy yourself for EDC. Error detection is really easy and you should be able to find the primitive solution to it. Error correction on the other hand is little tricky. Anyway I will also explain one of simple strategy here.

Definition (WikiPedia)

• Error detection (say ED) is the detection of errors caused by noise or other impairments during transmission from the transmitter to the receiver.
• Error correction(say EC) is the detection of errors and reconstruction of the original, error-free data.

So problem what we are trying to solve here is find 1) if there are incorrect bits in a byte stream (EC) and 2) find which bit is incorrect and correct it (EC)

Error Detection using Parity Check
Strategy is intentionally add few extra bit(s) to the original message which would help us finding sanity of the message on the other end.
Extra bits are called parity.
Original message + Parity is called Codeword.

Single parity check code
Simplest of strategy is called single parity check code (SPC).The SPC involves the addition of a single extra bit to the binary message, the value of this parity would depends on the bits in the message. In an even parity code, the additional bit added to each message ensures an even number of 1s in every codeword.
e.g. lets say message(7 bit ) is 1000 110. It has 3 bits as 1 so parity bit would be 1 to make total numbers event i.e 4
Code word would be 1000 1101

Mathematically
c = [c1 c2 c3 c4 c5 c6 c7 c8],
where each ci is either 0 or 1, and every codeword satisfies the constraint
c1 ⊕ c2 ⊕ c3 ⊕ c4 ⊕ c5 ⊕ c6 ⊕ c7 ⊕ c8 = 0

symbol ⊕ is modulo 2 addition.

You must be getting now, if message was sent through faulty channel and you recevied
1001 1101
Here number of 1's are 5 which are odd, means, there is error in this message.

Yeah, I get it you are already jumping your guns telling me
1) What if there are more than 1 bits which were turned from 0 to 1
2)  How to find which bit got flipped.

Answer of both of above questions is you DON'T. Remember when  I told its very primitive strategy. You have to add more redundant and sophisticated parity bits.

Below I will try to explain error detection strategy for 1 bit error correction

Encoding and Constraint Matrix
Lets say we have message bits c1, c2 and c3
and we are adding three parity bits
c4, c5,c6

we make a strategy to define c4, c5, c6 in such a way that

c4 = c1 ⊕ c2
c5 = c2 ⊕ c3
c6 = c1 ⊕ c2 ⊕ c3
These conditions of defining/choosing parity bits is called constraints. 

Using the constraints above the message 110 produces the parity-check bits
c4 = 1 ⊕ 1 = 0,
c5 = 1 ⊕ 0 = 1,
c6 = 1 ⊕ 1 ⊕ 0 = 0,
and so the codeword for this message is c = [1 1 0 0 1 0].

Above things can be put in mathematical form as



[c1 c2 c3 c4 c5 c6] = [c1 c2 c3][   1 0 0 1 0 1    ]
                                                       0 1 0 1 1 1
                                                       0 0 1 0 1 1           ---------Equation   1


Second matrix here is call Generator matrix or Parity check matrix(H)
suppose y is the code word received then

       c1
       c2           0
[G][c3  ]  = [ 0 ]                                                   ---------    Equation 2
       c4           0
       c5
       c6

            T
or H(y)     =  0

If its not all zero.. That particular code constraint is not satisfied.

The message bits are conventionally labeled by u = [u1, u2, · · · uk], where the vector u holds the
k message bits. Thus the codeword c corresponding to the binary message
u = [u1u2u3] can be found using the matrix equation c = uG.

Substituting each of 8 distinct messages c1 c2 c3 = 000, 001, . . . , 111
into equation above yields the following set of codewords for the code from
[0 0 0 0 0 0] [0 0 1 0 1 1] [0 1 0 1 1 1] [0 1 1 1 0 0]
[1 0 0 1 0 1] [1 0 1 1 1 0] [1 1 0 0 1 0] [1 1 1 0 0 1]   --------------------- Equation3


Error Detection and Correction

Suppose a code word is sent through binary channel and one bit got corrupted. This section would try to find and correct that bit.

The codeword c = [1 0 1 1 1 0] from the code in  was sent through a binary symmetric channel and the the string y = [1 0 1 0 1 0]  received.



substituting in equation 2

                  1
H(y)T  = [  0  ] 
                  0
This result is non zero that means bit flip must have been occurred. This resultant matrix is called syndrome of y.

Syndrome tells which parity constraint is not satisfied.

Error Detection/Correction
Above syndrome tells that first parity check constraint is not satisfied. Since this parity-check
equation involves the 1-st, 2-nd and 4-th codeword bits we can conclude that at
least one of these three bits has been inverted by the channel.

Hamming Distance

The Hamming distance between two codewords is defined as the number of bit positions in which they differ. For example the codewords [1 0 1 0 0 1 1 0] and [1 0 0 0 0 1 1 1] differ in two positions, the third and eight codeword bits, so the Hamming distance between them is two. The measure of the ability of a code to detect errors is the minimum Hamming distance or just minimum distance of the code. The minimum distance of a code, dmin, is defined as the smallest Hamming distance between any pair of codewords in the code. For the code in above example, dmin = 3, so the corruption of three or more bits in a codeword can result in another valid codeword.

A Simple Decoder to Find corrupted bit/ Maximum LikeliHood Decoder
To go further and correct the bit flipping errors requires that the decoder determine which codeword was most likely to have been sent. Based only on knowing the binary received string, y, the best decoder will choose the codeword closest in Hamming distance to y. When there is more than one codeword at the minimum distance from y the decoder will randomly choose one of them.This decoder is called the maximum likelihood (ML) decoder as it will always chose the codeword which is most likely to have produced y.

In above example we detected that the received string y = [1 0 1 0 1 0] was not a codeword of the code. By comparing y with each of the codewords in this code, the ML decoder will choose c = [1 0 1 1 1 0], as the closest codeword as it is the only codeword Hamming distance 1 from y.

This is one of the strategy. But still you can see that
1) Above exampled code can only correct errors  if hamming distance is 1
2) There are better algorithms available but this is just to give feel how things can work. You can check LDPC on wikipedia(reference below)




Refrences
1)http://www.cs.utexas.edu/~eberlein/cs337/errorDetection3.pdf
2)http://en.wikipedia.org/wiki/Error_detection_and_correction
3)http://en.wikipedia.org/wiki/Low-density_parity-check_code

6. What are Semaphores, RTOS Semaphores, MQX Semaphores

I would try to explain

what are semaphores?
What you need to take care if you want to implement your own semaphores?
Though I have label this post as MQX. But description is more on general term.


Semaphores

When They are used
Semaphores are used for two purposes
1) Process Synchronization
2) Critical Section problem / Mutual Exclusion

Is their any alternative to Semaphores?
Yes there are few solutions know as n process synchronize(software solutions) and Hardware solutions. Hardware solutions becomes complicated when number of process increases and secondly in all these you have busy waiting (it means you are eating CPU cycles when waiting and no other productive work can be done during this). So practically they are never used.

What are Semaphore?
They are synchronization tool. In a very abstract terms, semaphore is a global variables, which apart form initialization can be modified by only two operations wait() and signal().

Suppose S is semaphore
where wait is as simple as
wait(s)
{
     while(s <=0)
         ; //do no operation
    s--;
}

signal(S)
{
       S++;
}

Example of Usage
1) n process critical section problem
put every process code like this
do {
       wait ( mutex );
       critical section;
       signal(mutex);
       reminder section;
}while(1);

2) Example of using semaphores for Synchronization
Lets say, two concurrent process P1 and P2 having statements S1 and S2. We want in any case S1 should execute first. this can be achieved easily by
initialize Sem=0;

In process P1
{
   // Execute what ever you want to do
   // before executing P2
   S1;
   signal(Sem);

}

in process P2
{
     wait(Sem);
     S2;
}


Why not use Global Variables instead of semaphores to synchronize ?

Now if world was perfect, global variables can be used. You can write above mentioned functions in your C code to create semaphores. But(as its case with World anyway), its not that simple. In addition to above things we need to ensure

1) Modification of S value must be done exclusively.
2) In addition checking of while(s<=0) in wait and possible modification S--, should also be done without interruption
3) Above implementation is having busy wait too

How OS/RTOS implement Semaphores.What is spin lock?

The very basic implementation which I showed above has one problem they also have busy waiting. This is not at very appreciated in real time environments where wasting CPU is crime, equivalent to murdering someone (i.e murdering in civilized society). These type of semaphores are called the spin-lock semaphores.

But spin-lock semaphores have advantage too. There is no context switch required when process wait on Semaphore. Hence if waiting time is minimal this approach is very helpful.

How to overcome busy waiting.
You can modify wait and signal functions. When ever you have to wait, instead of looping you can block the current process. Bock is very common system call present in every Operating system.
In signal you simply call wakeup() for that process.
You also have to make sure that you maintain queue for all blocked process.

 There is one more important point.  On wakeup() you are simply putting it on ready queue. Its up to CPU scheduler scheduling policy when that process will be executed.


Critical Section Problem of Semaphore implementation.
The critical aspect of semaphore implementation that they are executed atomically. We must guarantee that no two processes can execute wait and signal operations on the same semaphores at same time. This is called critical section problem and can be solved in 2 ways.

1) In uni-processor environment, we can simply inhibit (disable) interrupts during the time that wait and signal operations are executing. This works very well in uni processor environment. Because, once interrupts are inhibited, there is no one, I mean literally no one (even 'the one' from matrix) can ask CPU to execute some thing else.

2)In multiprocessor env inhibiting of interrupts does not work. Instructions from different processors many be interleaved in some arbitrary way. We can  not employ any simple software solutions (not discussed here) for critical section problem.

I again emphasize what I said earlier, that MQX gives you two type of implementation one is called light weight implementation. When you call light weight implementation, MQX RTOS forgets about complexity of multiprocessor environment.