30 December, 2012

27 Inches - Part 1

2' 3". I like this number.

Its the length of arm of my standard person who  is 6' 9" tall. Since 99% people are shorter, it covers 99% of cases.

Uses in Widths

It keeps coming at all places where some width is occupied by a person:
  1. on bed
  2. on chair
  3. on desk when working
  4. on dining table while eating with others
  5. in corridor or door when walking or standing
Uses in Depths

It also keeps coming at all places where something is directly in front of a person:

  • Depth of cabinet directly reachable by arms without stretching
  • Depth in dining table directly reachable by hands without stretching

Uses in Lengths / Heights

Whenever we have to pass / put some person into something, we encounter this number:
  • Length and Width of Mattress
  • Height and Width of Door
  • Height of Ceiling
In a previous post about some of the above I said 2 ft, not 2.25 ft. Now looking at it more deeply, I found that its slightly less than 2 ft for me. My height is 5' 10". So its like 1/3 of height. So for 6' 9" person, its exactly 2' 3".

Mattress

Width For A Person

A person laying on a mattress would occupy 27" unsqueezed. He would be comfortable but not most. He is laying straight with chest up and arms on side with a little distance from hips. No pain in this position. So 27" is the minimum width of a comfortable mattress (not bed, more on this later in this article).

The maximum width of a comfortable mattress, without any wastage, is 54". There is a principle, if 1 unit meets the basic needs, then 2 units is the most the person would use without waste and without saving. Anything beyond 2 units is either wasted or used as a saving. The saving thing is significant in money matters but we do not need it in mattresses.

The person can use a 81" wide mattress. More and its hard to use all of it. It can be used readily but is still a waste.

The 45" width is enough for:

  1. Comfortably laying down, with arms stretched at most comfortable angle i.e. 60 degrees.
  2. Turnings during sleep.
  3. Putting books, files, laptop at side.
  4. Having another person comfortably fit in, but only for a short duration.
  5. Having a child of age 10 or less, comfortably fit in, for a long duration.
Width For Two People

If the mattress is to be shared by two people routinely then 81" width is fine. Not excessive, not miserable, just fine. Its because each person gets the necessary 27" and the remaining 27" is shared. For example one person stretch legs while the other stretch arms, thereby sharing the space.

Two people sharing bed, however, bring more problems than benefits. The turnings in sleep, lighting up to read a book, using laptop, getting out of bed to go to toilet etc unnecessarily disturbs the sleep of other. If two people have to share a room, then each of them must have a separate bed, with enough space in between the beds for each of them to get out and walk comfortably in dark without hitting anything. The in-between space can be used by a third person in emergency.

Length For Single Person

Pillows are usually about a foot long and 2.25 ft wide. Heads are usually 8" long i.e. palm-length. Therefore, about 4.5" top length of pillow is unoccupied.

4.5" must be left below feet for a good sleep.

Therefore, 9" extra length is needed in mattresses beyond person's height.

So for a 6' 9" person we should have 7' 6" or 90" long mattress.

Conclusion of Mattress Discussion

From the above, we have concluded that ideal mattress is for a single person and it is 7.5 ft x 4.5 ft.

Wood Thickness

Lets talk a little about the remaining portion of bed, the wooden structure.

The bed I am using since 11 years has a structure of 1" thick wood except at four corners where its 2" thick.

Ideally a bed should have 2" wide structure. The corners must be 4" thick. This is how beds used to be constructed till 20th century.

We can cut some corners by making corners 3" thick. With that altogether the bed would be 5' x 8'.

Further Thought About Mattresses

The above calculation was intentionally made large enough to fit in 99% of population. Infact for a general case, we do not have to go to that extreme. We can have a case for 93.75% with comfort that still fit in the rest (with decreasing comfort and the last one, the 6' 9" case just fit in with no comfort ).

Looking at my habit of using mattress, I notice that I never use more than 33" width at a time. If one hand stretch then other contract a bit etc. Also files, books and laptops are not meant to be put on bed, so we do not have to plan room for them.

My 5' 10" (= 70") uses 33". May be 36" is the real need.

I have tried 36" spaces and noted that they met all of my needs with one or two extra inches left.

5' 9" or less is height of 75" of men. Ofcourse women are shorter. Children are even shorter.

Length-wise 81" leaves the necessary 9" for even 6' tall people.

Only 6.25% men are taller than 6'.

May be the right dimension is 36" x 81".

Sometimes when people sleep, they stretch an arm to its full extent below pillow at side. On a 36" wide mattress, it has to go out of the mattress to hang in air. In 54" wide mattress we can guarantee that it would not happen in most of the cases.

An idea is to have two beds in each room, opposite to each other, fixed tightly with a side wall. Beds in this case are 1 meter or 40" wide (36" mattress + 4" structure). A 40" wide space is left in middle. Enough space to stretch an arm.

On the topic of stretching of arm, I have noted that when the arm goes outside the mattress, it seldom stretch more than 9", and atmost 12". Its because after 12" the part of arm still on mattress is unable to comfortably support the hanging part so the hanging part start to go down. So, atleast 12" space at each side is a generous thing for stretching arms.

If we do have to add 12 + 12 = 24 inches in the mattress width (not bed width because arms start hanging as soon as out of bed, not care how wide wooden structure is) then we get 36 + 24 = 60. Same number we have got before when we planned for wider mattress. If we add 9 + 9 = 18 inches, then its 36 + 18 = 54 inches, the previously proposed width of mattress.

So, no matter how we put it, we have to give each bed 5 ft x 8 ft space. Its better to have most of this space covered with mattress, as proposed before, than to have body parts hanging in air.

On Even Further Thought

Seems like a loop, got through many iterations but still don't find a dimensions that feels optimum.

81" length of mattress seems optimum. Fit in comfortably 6' or shorter. This covers 93.75% men, 96.875% women and 100% children. Altogether about 97.66% population.

Hard to decide about width, though some things are well-decided. Below 36" is pain. Above 54" is waste.

One advantage of 36" width is getting out of bed is one step, in 54" its two steps because the person have to move on side first. Another advantage is no waste, there is some built-in wastage in 54" width. Another advantage is killing of choice, a mattress is exactly for one person, no sharing (not even with a child), less choice means less headache.

Now about stretching of arms while sleeping. First of all very few people do this, and those that do it can be trained out of necessity to adjust. Second, my experiment showed that maximum 8" open-air space at each side of mattress is needed. We have to leave this space anyways at one side to walk out of bed. I am not planning for a system in which one can get out of bed only by the end because its a lot of pain.

About width of wood, I think 1" for structure and 2" for corners is enough. After all, my bed has not shown slightest sign of breaking up in 11 years.

So width wise: 36" mattress + 2" left corners + 2" right corners = 40" = 1 meter. Length wise: 81" mattress + 2" top corners + 2" bottom corners = 85".

Mattress = 36" x 81". Bed = 40" x 85".

Now about open space. At one side 8". At other side 16". The other bed would have its own 16" space, making the middle space 32". So, 36" + 8" + 16" = 60".

Some space have to be left at top of bed near wall. This have to be 8" as at minimum side. Since this gives an odd number 91", lets make it 7". So 5" between bed and top wall, 7" between mattress and top wall.

Final: Mattress = 36" x 81". Bed = 40" x 85". Total Space = 60" x 90".

29 December, 2012

"Necessity" of Musical Chair In Democracy

First of all, all democracies develop into two-party systems, other parties become non-existent (usa) or too small to matter. This is achieved by alliances, unions, take overs and yes buying.

In Pakistan we have not yet reached that point, we have two big parties but there still is significant power in smaller parties. Its because we didn't have a continuous democracy, due to frequent military take overs.

So, once the two-party system is reached, a musical chair develops. One party get in power, spend atmost 10 years, then let the other party take over for atmost 10 years. Rinse and Repeat. Why?

Its because if only one party remain in power, then it cannot blame its faults to anybody else, it has to take some responsibility of its actions. The musical chair scheme works great for both parties, because they can keep on blaming each other.

If you want to play a long game, then you have to be careful about what you are playing with, that thing should not deplete. People's trust is the thing most democracies play with.

Note that musical chair is not effective to achieve its target if first two-party system is not developed. Its because in presence of significant others, when the first party let the seat go, its not necessary that the second party catch it, some third entity can take hold.

Two-party system in democracy is like duopoly in economics. Lesser the competition, lesser the efficiency. As retail is the most perfect real world market, due to presence of numerous suppliers (no monopoly), democracy is as efficient as number of parties are. This however do not work, because after a threshold, the multi-party country sieze to exist, because it breaks down in smaller units. Democracy divides. Its in this division the short-term efficiency is.

Let me explain. The efficiency democracy brings is by reducing political corruption. This actually is a very small portion of economy. Its because very small portion of economy, usually less than a quarter goes in taxes, and a fraction of taxes goes in corruption. There is an upper limit on corruption-to-taxes ratio, which is amount needed to run the country, the unavoidables, things like salaries of govt employees, maintenance of infra structure, maintenance of military weapons etc.

Greater efficiency can be achieved by making empires. By combining districts into provinces into countries into regions into empires. Greater the size (population, land) of a country, the more efficient it is. This efficiency comes by using same currency, free internal traveling and trade, specializations of areas etc. This efficiency comes in the whole economy.

So, assuming that taxes are one quarter of economy, and corruption is half of taxes, only 12.5% of economic output goes in corruption. The most that we can theoretically do with efficiency is to make it 100%, so assuming a perfect democratic system, having hundreds of almost equal political parties, we may reach 99% of efficiency. So there is a saving of almost 12.5% of economy. Now lets see at what cost it will come.

The least that we do with real world division is to limit it to 2, that is divide in half. Ofcourse having hundreds of political parties means that you have to divide by some greater number, say 10 or may be even 100, but lets be very optimistic. At a division of 2, efficiency decreases somewhat. My point here is, that at whatever length that decrease in efficiency is, it would still be larger than the 12.5% number we have got to above.

So, its must to have a very corrupt govt, for most of human history where there is a large empire. This corruption can come in many forms. It might be the mughal kings giving outrageous amounts of money in gifts to their families, or warlords of medieval europe basically doing almost whatever they want in their little strongholds inspite of law of land and desire of kings.

Empires are expensive. No doubt about it. One expense is excessive corruption. To keep united a large region, with may be hundreds of languages and cultures, there have to be a lot of earmarks, grants, buyings on the soft hand and rebellions, civil wars, crushings etc on the hard hard. We know from the roman experience that all democracies, even the two-party systems, become empires in the long run. Empire means having a king, that is monopoly, no competition at political level. By definition this arrangement is inefficient. Yet this efficiency is many times less than the efficiency gain in economy.

27 December, 2012

Some Basic Mathematical And Computer Stuff To Keep On Finger Tips

In How Many Number Of Ways n People Can Sit On r Chairs

Case 1: When n = r i.e. when number of people equals number of chairs


n!

At start all chairs are empty, so any of the n people can choose to sit on that first chair. So there are n possibilities for the first chair. For the second chair, n-1 people are left, so probability for the second chair is n-1. The probability for the first two chairs taken together is n * (n-1), its because any arrangement of the first chair can be combined with any arrangement of the second chair.

Its like if a room has two sets of doors, one to enter and one to exit, for example at opposite sides of wall, and in the first set there are 5 doors and in the second set there are 7 doors then altogether there are 35 combinations of entry-exit. You can enter from the first door and exit from any of the 7 exit doors, and you can enter from the second door and exit from any of the 7 exit doors, so 7 + 7 = 14 combinations so far. Accounting for the rest of the 3 entry doors you have a total of 7 + 7 + 7 + 7 + 7 = 35 combinations of entry-exit.

So, uptil now we have covered two chairs and the number of combination is (n) * (n-1). For the third chair the number of combinations is n-2 and for the first three chairs taken together there are (n) * (n-1) * (n-3) combinations. Altogether, for all the n chairs we have n! combinations.

Case 2: When r < n i.e. some people will be left standing

n! / (n-r)!

Lets suppose we have 5 people and 2 chairs. For the first chair there can be 5 possibilities, for second chair 4 possibilities i.e.

5 x 4  = 20

We know from case 1 above that if number of people is equal to number of chairs then its 5! = 120 possibilities.

So, its n! / (n-r)! possibilities.

5! / (5-2)! = 5! / 3! = 120 / 6 = 20.

Lets try some other numbers: n = 7, r = 4.

Our naive approach gives us: 7 x 6 x 5 x 4.

The formula we derived above gives us: 7! / (7-4) ! = 7! / 3! = 7x6x5x4x3! / 3! = 7 x 6 x 5 x4. Same answer as above.

So its confirmed that our formula is correct.


How Many States Can A Machine Having n Bits Can Hold

2 to the power n.

The number 2 came from the fact that a bit can have only two states: 0 and 1.

Note that only one state can be hold by the machine at any given time. The machine can hold 2 power n unique states each at a different time.

Consider a bit, it can have only two states. Now consider two bits, the second bit can independently have two states of its own. Taking the first and second bit together, four unique states can be hold. For three bits its 2 x 2 x 2 = 8 states. For n bits its 2 power n states.

How Much Time It Takes To Sort A Binary Tree

log2 of n.

The 2 is the base of the log. n is the total number of leaves in the tree.

Suppose we have 8 elements in binary tree. In a perfect binary tree, there would be three levels of nodes / root and at the last level there would be 8 leaves. That number 3 can come from taking log2 of 8. Its because 8 = 2 power 3.

If the tree is not binary, but say have 5 branches at each level, then the base would be of 5 when taking the log.

How Much Time It Takes To Run A Nested Loop

Case 1 : The Two Iterations Are Independent Of Each Other - Simplest

m * n.

Where m is the number of iterations in the first loop, and n is the number of iterations in the second loop.

for(i=0; i    for(j=0; j         
       // do some work here

Case 2: The Second Iteration Depends On The First - Harder

m + (m-1) + (m-2) + ... 1 = sum of a geometric series of difference 1.

for(i=0; i

    for(j=i; j        
        //do some work here

Its because in the inner loop, first iteration runs m times, second (m-1) times, third (m-2) times and so on.


If m = 5, then the inner loop would run 5 + 4 + 3 + 2 + 1 = 15 times.

Its a simple geometric sum of 5 items, starting from 1 and having difference 1.

Speed Classification of Algorithms

Algorithms considered here are typically of searching and sorting.

In descending order of speed, n is input size:


  • Constant Time - O(1), O(6) etc
  • Logarithmic Time - O(log n) etc
  • Linear Time - O(n) etc
  • Polynomial Time - O(n^2), O(n^3) etc
  • Exponential Time - O(2^n), O(3^n) etc
  • Factorial Time - O(n!).
Usually execution time of algorithms is a function of input size. Above are fundamental classes of algorithms, starting from the fastest. Ofcourse there are sub-classes in between such as sub-linear O(n/2) etc.

If big O notation is O(n) then for an input size of n the algorithm requires n steps or iterations.

             n      O(1)   O(log2 n)      O(n)        O(n^2)          O(2^n)              O(n!)

             1         1        ~ 0.1              1                    1               2                       1

           10         1            3.3            10                100         1 024             362 880

         100         1            6.6           100           10 000      1 exp 30           very large

      1 000         1            9.9         1 000      1 000 000      1 exp 300         very large

    10 000         1           13.3        10 000       1 exp  8      1 exp 3000        very large

   100 000        1           16.6       100 000      1 exp 10      1 exp 30 000     very large

1 000 000        1           19.9     1 000 000     1 exp 12      1 exp 300 000    very large



Note that in computers which are bi-state (0,1) machines, both exponential functions and log functions are always of base 2.

Factorial functions are the worst performants, then come exponentials, then polynomials, then linears, then logs and finally constant time ones which are special because they always execute in same time regardless of input size.


Any algorithm that actually works on input has to be atleast logarithmic. This is theory. Practically the most efficient algorithms are usually of efficiency O(n * log n).

 For searching, the fastest algorithms are those that divide the search space in every iteration. So its divide and conquer winning again. In more parts the space is divided each time, the faster is the algorithm. Usually the space is divided in two parts only, greater and smaller and the third possibility of equality is dealed directly at which point the algorithm stops. If we can divide the space say in 5 parts each time, then the base of log becomes 5, therefore we can cover space of 10 elements in log5 (10) = 1.1 iterations. This is called binary searching and requires an already sorted binary tree to work. 

The logarithmic function came from the fact that a binary tree containing 8 leaves have to have 3 levels and log2 (8) = 3. Since in every iteration we are omitting half of the remaining tree from search space, we need only 3 iterations in worst case. 

An example of this is finding a book in a library where books are arranged by topic in corridors then cabinets then floors and then rows (assuming multiple rows one behind other at each floor of cabinet). As we move along an iteration such as decide a corridor we omit the search space of rest of the corridors and so on. So even if we have 10 corridors, 10 cabinets in each corridor, 100 floors in each cabinet, 10 rows in each floor we just have to iterate 5 times till we reach the correct row. Till this point we have used a logarithmic function of base 10. Once in the row we can do a linear search, so altogether its O(log10 (total number of books in library ) * no. of books in each row).

So, if the data structure is an already sorted binary tree, then efficiency is exactly O(log n). For a general and unsorted data structure, such as an array, we have to divide the search space in every outer loop and in inner loop we have serially search the space, so its O( n * log n).

If we have to visit each element of data structure exactly once, such as in naive approach of searching, then its O(n).

Everytime we use nested loops each of which iterate through all elements of an array, we have O(n^2). Its when there are only two loops. If there are three loops, outer most, outer and inner, then O(n^3). Examples include bubble sort, comparing shopping items list with items purchased etc.

Understanding examples of O(2^n) is complicated. Its opposite of the logarithmic function shown above. In logarithmic function we have an existing tree and we use it. In exponential algorithms we make trees, by branching of to different points in execution paths in body of function (on basis of different conditions) as long as each execution path is a recursion. See example below:







public int fib(int n)  
{
    if (n <= 1)  
       return n;
    else 
        return fib(n - 2) + fib(n - 1);
}



In the fib function above fibonacii series is generated. In the "if" condition no branching or recursion happens, in the "else" condition the execution path branches off in either of two branches. Note that for algorithm to be O(2^n) its not enough to have multiple execution paths branching out, the necessary condition is that each of those branches have recursion i.e. call the original functions. In the "else" condition in the function above, two recursive calls to fib is made.

For n =1, there would be only one call of the function. For n = 2, the first call would have two more calls, so three calls. For n = 3, the first call would call two functions, one of which would have another calls so its 1 + 2 + 1 = 4 calls. Altogether, number of recursive calls increasing exponentially (of base 2) as size of n increase linearly.

Another example:

void somefunc(some input)
{
      some work;

      if(some condition)
           somefunc(...);

      some work;

      if(some other condition)
           somefunc(...);

      some work;

      if(some yet other condition)
           somefunc(...);

}





As the fib function above has potential to branch into any of two paths at each call (each path being recursive is necessary condition), the somfunc has potential to branch into any of three paths. Its O(3^n).


Finally the factorial algorithm. Its the most inefficient, naive and simplest algorithm. Easiest to program but hardest to execute. Its also called brute force. Its when instead of using an intelligent method of searching or sorting, we simply try to make as many combinations as we can and test which of them is correct.

An example is trying different combinations of numbers at a number-lock briefcase or keypad-lock door. 

Another example is making people sit in different arrangements to see which one looks best before taking a group photo.

Types of Relations Between Database Tables

There are only three types of relations between database tables: One-to-one, one-to-many, many-to-many.

Relationships are represented by Primary Keys (PK) and Foreign Keys (FK). When a primary key of a table A is referred in another table B, then in B its called a foreign key.

One-to-One Relation

Keeping one-to-one relation is meaningless because the two tables can be combined in one table, unless the parent table P can relate to different child tables C, D, E in different rows.

An example of one parent table relating to different child tables in different rows is a document management system where parent table Document have a record for all types of documents such as html pages, pdfs, images, word documents, audio files etc but separate child tables for each of these document-categories contain specific format and address information. Such as table C contains records for html pages only and have columns such as urls, useCookies etc. Another table D contains records for pdf files only and have columns such as isPasswordProtected, pageCount etc.

One-to-Many Relation

This is essentially same as many-to-one relation with just the sides changed so considered together.

Unlike the one-to-one relation considered above, here we are discussing simple form only, in which only one parent table relates with only one child table. The reason we are not discussing the complex form where one parent table relates to multiple child tables is that we do not have to because the concept and implementation can be well understood from simple form and can be extended for the complex form.

Parent is the one side, Child is the many side. Means for every record in Parent table, there can be multiple records in Child tables, but for every record in child table only one record exist in parent table.

It may happen that for a parent no child exist and for a child no parent exist but the latter though is a valid state as far as data is considered must be prevented because it go against data integrity.

Since a cell can contain only one value, and since a parent record can have multiple child records, parent cannot know about child. Its because we have no way of putting child information in parent record. For one parent record there can be 5 child records, for another 575, yet for another 0. How can we put so many different ids in parent record. 

Tables Are Not Ragged

Note that tables are by definition non-ragged, meaning number of columns are same in all records. Its not like the first record have 5 columns, the second 17 columns, no, all of the records would have same number of columns. 

If a parent record have 5 child records, then if parent knows about children then that parent record must have some way to store ids of all the child records, so these are 5 numbers (lets say 101, 102, 103, 109, 214). Since a cell can have only one number (1 NF), we have to have five columns to keep this information. Now if the second parent record has 17 children, then that record needs 17 columns to contain ids of children. Since any parent can have any number of children, it will all get mess up if we keep children information in parent table. A parent record can related to a billion children record or to no child record at all. Moreover, the relation is not fixed, as time moves on the record that links with 5 children can now link with 4 children only, and the one that links with 17 children can now link with 25 children. 

Although theoretically we can change definition of parent table for this purpose, keeping nulls in non-used columns, and design a dbms that deals with this efficiently, at the end of the day its all a big mess and can be elegantly avoided simply by putting the information about parent in child table instead.

So the child table have to have a foreign key which relates to the primary key of the parent table. The only issue with this is that some children may have information about parent records even after those parent records are deleted. Its like those child records have gone orphan since their parent record is deleted ("died").

Maintaining Data Integrity

To maintain data integrity, we have to have a consistent method of dealing with what to do about child records when their parents have to be deleted. We have following options:

(1) Do not delete a parent until all of its children are deleted.

(2) When a parent record is deleted, automatically delete all its child records too.

(3) Just delete the parent record letting the child records exist as orphans.

The third approach breaks data integrity and must be avoided. There is no fixed rule about (1) and (2), depends on intuition of programmer. 

Link With Transaction

Its the parent-child relation that become basis of transactions. In absence of such relations no transaction mechanism is needed in database management systems.

Its the transaction mechanism that ensures that data integrity is to be maintained if option (2) of above is chosen, means either both parent and child records would be deleted, or none of them. 

Transactions also maintains data integrity in insertion and updation.

Many-to-Many Relation

For the same reason by which we cannot put child information in parent table in one-to-many relations (one call can have only one value, tables are not ragged, its inefficient to keep changing table-definition / schema for updations in data), we cannot put information of other in any of the parent or child tables in many-to-many relations. Its because here a parent can have multiple children and a child can have multiple parents. 

The solution is to use a bridge table. This table has three columns: Id, IdParent, IdChild. Relations between parent and child records can either exist or not, so there would be only two operations in this bridge table: insert, delete. 

Joins vs Unions

If we join a table A (5 columns, 15 rows) with a table B (7 columns, 10 rows), then the join in its simplest form (called cross-join or cross-product) results in a recordset R (5 x 7 = 35 columns, 15 x 10 = 150 rows).

Its like nested loops complexity O(n^2) discussed above, but in two dimensions (columns and rows) and n is different for each table, so its m * n. 

The resultant recordset R gets both long and fat, basically big.

Since this has redundant information, we have to put some condition. Old method is to put the condition in where clause, new method is to use "join" keyword. 

When we add condition, we have to decide the null case i.e. when FK is null (PK ofcourse can never be null). Note that joins are supposed to be always between FKs and PKs.

Unions are different. Unions are made between tables that have same schema (columns' names, columns' count, columns' types, columns' size). Therefore in the resultant recordset number of columns remains same, rows increase. Typically all of these rows have unique PKs so we don't have to add any condition.

Tail Recursion And Stack Overflow

The default working of compilers is such that, whenever a function is called, its entry is made on stack. This ensures that when this functions calls another function (whose entry would also be made on stack), and that function will exit, control would be transferred to this function.

Even in OOP, the call stack is based only on functions, just that function-names are prefixed by object-identifiers. So when program starts the entry point function, which is usually the main function starts. This function then calls other functions through message-passing (a fancy name for calling methods of other objects). Event handling is a special type of message-passing.

Under the hood, in assembly language, its just goto command passing instruction pointer to different control segments of memory. Instruction pointer itself is outside memory, its a cpu register.

There is a problem in this architecture. The call stack can be filled upto a very small limit. This limit comes very quickly, long before the memory exhausts. This is called stack overflow problem.

Recursion i.e. a method calling itself is a very elegant solution to a variety of problems. The problem is, a function calling itself can very quickly (milli seconds) overflow the stack resulting in abrupt termination of program.

The solution to this is tail recursion. In this technique, the recursive call is made at the very last line of the function. Therefore when the called function exits, it not really have to return to one step backwards, because no computation is left there, it can return to two step backwards. If that is also a recursive call then three step backwards and so on. 

Ofcourse an elegant compiler is needed to understand this and convert these kind of recursive calls in non-recursive, loop-based calls internally. 

What Happens At Bit Level In Computers If We Try To Divide By Zero

Computers divide in the same way we do, called long division. For example:

  _012
8| 100
    _8
      20
      16
        4

Ofcourse we know how to divide, still please proceed with me looking at each step carefully because we have to use these rules below when we divide by 0.

We divide 100 by 8. First we take the first digit 1, since 1 is smaller than 8, we take another digit by putting a zero above. Now we have 10, we divide it by 8, remainder is 2, 2 is less than 8 so we get another digit making it 20. Note that since we have done division once we can take one digit without adding a zero. If we need more digit then we have to put more zeros. 

So we get 20, we divide it by 8, remainder is 4. 4 is less than 8 and no digit left, so program terminates.

Note that computers do divisions in the same way we do, its just that they use binary numbers. Since numbers in their essence are same, no matter in what system (decimal, binary, octal, hexa) we represent them, we do not have to consider binary numbers to understand working of following division in computers:

  111
0|95
   0
   9
   0
   9
   0
   9

So we take a number 95 and try to divide it by 0. Nothing special about 95, we can use any number. 

We take first digit 9, since its greater than 0 we do not need to take the second digit. 0 time 1 is 0. 9 minus 0 is 9. Since 9 is greater than 0 we cannot take the second digit, so we have to divide again. 

No matter how many times we divide, result is same as input. So this program conceptually never ends. However on a real computer, with finite memory, and finite word-size (32 or 64 bits) we get all 1 and then program terminates. All 1s mean maximum number that can be represented in that word-size. actually referring to infinity. 

On paper when we divide 1 by 1 we get 1, 1/0.1 = 10, 1/0.01 = 100 and so on. As the denominator decrease, result increase. So as denominator approaches zero, result approaches infinity.

22 December, 2012

Vector Comparison And A Solution To The Knapsack Problem

There are two things in world: (i) scalars (ii) vectors. Scalars have only one value i.e. only one dimensions, examples are numbers, boolean values, intensity of emotions etc. Vectors have multiple values i.e. multiple dimensions, examples are points, multi-column tables etc.

Its easy to compare scalars. Given a list of numbers its straightforward to tell which one is the largest or one among the largest ones. Vector analysis is very hard. A thing can be good in one aspect but bad in another aspect, how to tell that the goodness in one aspect is more important than the badness in the other aspect?

Lets have a situation. Suppose you are manager of three subordinates in a business organization. The organization have these four basic functions: production, accounting, marketing and customer interaction. Every subordinate provide some service in each of these functions but they are not equally good in any of these functions. Some employee is good in two things, average in the third thing and bad in the fourth thing. Another employee is good in some other set of functions, average in some other and bad in some other. How to tell which subordinate is the best among the three subordinates?

I have created this situation as a four dimensional vector analysis. The four dimensions are the four functions of the organization, in which each employee has some value. Each employee is a vector, so we have three vectors. To have an intuition about vectors, consider them as points in n-dimensional space.

The above situation is one of the knapsack problems. The classical knapsack problem has only two dimensions: weight and value (in dollars). You have a bag to fill with objects (vectors) where each object has a weight and a value (in dollars). The bag has a maximum capacity so total weight of all the objects that you put in the bag must be less than or equal to that capacity. The task is to fill the bag with as much cummulative value of objects as you can.

There is a long way to solve this problem which is quiet complicated. Infact the easiest solution that I can find is here on stackoverflow (please scroll down on that link to read the last comment). I really cannot understand why people do not offer a simpler solution, May be nobody has thought about it. Anyways, my solution is below and I think I am the first one to make it this simple.

Here is my algorithm to solve the knapsack problem:

Step 1: For each object, divide value with weight, so you get one number for each object. Lets call this number Efficiency Factor. Put these values in an array so we have one element in array for each object.

Step 2: Sort the Efficiency Factors array in descending order.

Step 3: For each element in array, put the element in the bag, till either the bag is full or the array exhausts.

The big O notation for the stackoverflow solution is O(nW) where n is number of items and W is the capacity of bag. The big O notation of my solution is, well lets see, we have to visit each object once to calculate the Efficiency factor, so we have a n there in our big O notation. Then we have to sort the array, so we have a log n there. Then we have to run through the Efficiency Factor array, which is of same length as number of objects. So its O(2nlogn). Since we remove co-efficients in big O notations, so its O(nlogn). Actually we might not have to visit every element in the last loop because the bag might be filled before the array exhausts.

This is great and I think more efficient than normally available algorithms. Its also quiet simple so score some points there too. The core of the algorithm is to reduce the vectors into scalars. Works great but what if the vectors are of more than 2 dimensions. In case of 2 dimensions we can use divisions but what to divide with what when there are more than 3 dimensions. Also in more general vector analysis i.e. in non-knapsack problems, like comparison of employees above, the division approach makes no sense and this algorithm of mine do not work. We cannot divide performance in one field by performance in another field because the result is meaningless. In two equally important fields A and B, if employee 1 scores 7 and 5, and employee 2 scores 5 and 7, then actually the two employees should have equal grading. But if we divide A by B, then the first employee gets a score 1.4 whereas the second employee gets score 0.714, wrongly grading the employee 1 better than the employee 2. If we swap place of A and B in the division then we see opposite result. Since fields are equal, so we cannot decide which field to go in nominator and which to do in denominator.

To solve this problem of employees grading in particular and vector analysis in general, lets use the analogy of points. Lets consider each employee a point in 4 dimensional space. Since that is hard to visualize lets first consider only two dimensions. Following is the performance of each employee in the four functions of the organization, lets call these functions A, B, C, D in the order given above (means A for production, B for accounting, 3 for marketing, 4 for customer interaction). Lets call each of our vectors (employees) Vi.

V1(7, 8, 5, 1)
V2(1, 9, 10, 4)
V3(4, 7, 4, 6)

Lets suppose we have only two employees to consider. The first one scores 5 in field A and 5 in field B. The second one scores 10 in field A and 0 in field B. A naive approach of summing the points (the same approach use in grading students in marks sheet) says that both employees are equal. However its easy to see that the first employee is an average performer whereas the second one is a specialist. We have two choices here: (i) Reward the specialist (ii) Reward the mediocre.

If we want to reward the specialist, which is generally the case in big organizations and govt institutes, which can afford to have specialists and where quality is more important than flexibility, we can use the following algorithm that I created:

The algorithm is to simply reward the employee who go farthest from the origin. In case of the first employee, the mediocre. who is at point x=5, y=5, we can use pythagorous theorem to find out that the distance from the origin is root(5*5 + 5*5) = root(25 + 25) = root(50) = 7.14. So thats the score of the first employee. For the second employee the score is root(10*10 + 0*0) = root(100 + 0) = root(100) = 10. So if the employees are enemy planes moving in two dimensional space and we have our anti-aircraft guns at origin, we have to have a range of 7.14 for our guns to hit the plane of the first employee but to hit the second employee we need far better guns of range 10. Therefore, where we reward the specialists, the solution is to simply use the phythagorous theorem. Every science person knows the phythagorous theorem of two dimensions, but the phythagorous theorem of three dimension is root(x*x + y*y + z*z) and for four dimensions it is root(A*A + B*B + C*C + D*D).

If we do not want to reward the specialists, but want to reward the mediocres, a strategy good for small organizations where flexibility and jack-of-all-tradeness is more desirable than specialism or intense knowledge of a very few things, we simply have to take the reciprocal of the length of diagonal calculated above. So in that case, for the first employee the score would be 1/7.14 = 0.14 and for the second employee the score would be 1/10 = 0.10. Here, the first employee scores more indicating that he is more valuable for the organization than the second employee. Unlike the diagonal approach, there is no way to easily visualize which employee is good, meaning no aircraft like story exists, other than saying that being closer to origin is desirable (consider both the planes and aircraft guns to be friendly and the planes are now going on bombing missions on enemy territories under the cover of our own anti aircraft guns so the enemy fighter planes cannot destroy our bombers, we do not want our planes to go very far from the origin).

Now to solve our employee situation, assuming that our organization is big and therefore reward specialists:

V1: root(7*7, 8*8, 5*5, 1*1) = root(49 + 64+ 25 + 1) = root(139) = 11.79

V2: root(1*1, 9*9, 10*10, 4*4) = root(1 + 81+100+16) = root(198) = 14.07

V2: root(4*4, 7*7, 4*4, 6*6) = root(16 + 49+ 16 + 36) = root(117) = 10.81

So the middle one is the best employee. A few things to note:

(1) We are assuming all values to be positive. For negative values where negation is undesirable, subtract instead of adding, after taking square of the value i.e. root(x*x + y*y - z*z) if z has a negative value. If negation is not undesirable then do not subtract but add as usual.

(2) We do not really have to take the root because the value before the roots is also reliable for grading. Its however not reliable for precise grading where we do not just have to tell which employee is best but also have to tell the margin of goodness. Suppose an organization has only three functions, and an employee has 5,5,5 value and another employee has 10, 10, 10 value. We know that the second employee is better than the first employee, but by how much. Can we say double, actually we can, because if the second employee has value 10,5,5 then that employee is obviously not twice as good as the first employee. To get the right grading, we do have to take root. Its because before taking roots, the values are (5*5 + 5*5 + 5*5 = 25 + 25 +25 = ) 75 vs (10*10 + 10*10 + 10*10 = 100 + 100 + 100 = ) 300 which wrongly says that the second employee is 4 times as good as the first employee. After taking roots the values become root(75) = 8.66 vs root(300) = 17.32, a difference of 2 times

(3) All we are doing is converting vectors into scalars. We humans are not capable of vector comparison, we can only compare scalars.

(4) We are assuming that each of the fields or functions of organization are equally important. If they are not, then we have to multiply each value with weight before taking square. Suppose the weights are as follows:

production: 5
accounting: 2
marketing: 3
customer interaction: 4

The scores of the employees would be as follows:

V1(7, 8, 5, 1) => (7*5, 8*2, 5*3, 1*4) => (35, 16, 15, 4)

V2(1, 9, 10, 4) => (1*5, 9*2, 10*3, 4*4) => (5, 18, 30, 16)

V3(4, 7, 4, 6) => (4*5, 7*2, 4*3, 6*4) => (20, 14, 12, 24)


03 December, 2012

Interior Spacings : First Part

This post is about recommended widths of corridors, mattresses, chairs, tables etc.

95% of humans have height under 6 ft. We can therefore take this height to cover 95% of situations.All of the following numbers are for this height, meaning for near to 95% of humans there is some extra space available when following numbers are used.

To Stand:
    Breadth-Wise:
  
        Shoulder to Shoulder                                                                18 inches
        Shoulder to Shoulder + Muscles + Hips                                     24 inches

        Stand Without Touching Another Person                                    27 inches
        Stand Without Touching + Room For Arms March Movement   36 inches

    Length-Wise:

        From Tip of Middle Toe of Foot to Back of Heel Of Foot          12 inches (definition of Ft.)
     
        Standing Without Touching Person In Front                                18 inches
        Standing Comfortably                                                                 24 inches

    Conclusion:
 
        Actual space needed to stand is 18 inches breadth-wise and 12 inches length-wise. This is when people are packed (in a bus or row for example) like bricks in wall. To just stand (no walking) without touching any person at side or front or back 1.5 times the above in each dimension is enough. To walk without touching any person 2 times the above is enough.

    Recommendation:

        36 inches breadth-wise and 24 inches length-wise per person space.

    Applications:

        Mattress Width. As long as person is laying flat means no turn-overs.

        Corridors: 36 inches width is good (and enough for almost anything) as long as only one person is supposed to walk in the corridor at any given time. If two people are supposed to walk in the corridor (for example coming from opposite directions), then we need a 27 inches per person plus a 9 inches space in between i.e. 63 inches minimum space. Practically this could be rounded to 60 inches (5 ft.). However a full 72 inches (36 inches per person, 6 ft.) results in maximum comfort to space ratio, means the optimum point. Its also the most beautiful.

        Doors: 36 inches width is optimum (comfort to space ratio, beauty) for single-person or couple rooms (bedrooms, kitchens, toilets, study rooms, computer rooms etc). These are the rooms which are supposed to be not used by more than two people at the same time. For rooms which are supposed to be used by more than two people at the same time (drawing rooms, halls, dining rooms, garages, main entrance to a large building, large warehouses etc) a 72 inches width is recommended as long as no vehicles are supposed to enter the room. If vehicles are supposed to enter the room then needed door width ofcourse depends on width of vehicle multiply by 1.25 (atleast) to 1.5 (recommended) to 2.0 (maximum).

        Office Tables: These are the tables that are supposed to be used by only one person at a time. Examples are normal office tables, study tables, computer tables plus some room to do paper work, repairman's tables used by carpenters, electricians etc to make or build some machine etc. Since a person's height is under 6 ft. in 95% of cases, the arms span of a person is 6 ft when stretched at 0 degrees. A table however have to be considerably less wide because angle has to be greater than zero to be able to grasp things in front at sides of table.
   
Chairs:

    To sit a person needs a chair that is maximum 2 ft long and 2 ft wide. We are not concerned with height of chair over here.

    Almost all chairs fit in these dimensions. The left over are very huge luxury chairs that are not usually used or even seen.

    These dimensions are not for sofas because some sofas have very thick bodies taking the whole scheme to something less than 4 ft x 4 ft, though these new dimensions cover almost all of the single person sofas.

    These dimensions are not for couches or multi-person sofas because we are talking about sitting devices only, not devices that can be used for laying down also.

    To move a chair comfortably backwards or sidewards to get out of the chair is 2 ft at each side. So, a chair when put in a position that its front-most end is touching the table and back-most end is 2 ft from the table, a 2 ft space at back of the chair (4 ft distance from table) is enough for people to comfortably move chair back and get out. In the same position, a 1 ft extra space at each side of chair is enough for comfortably move chair at sides while using it.

    For wheelchairs, corridors need to be 4 ft wide.

    From the above, it can be safely concluded that in a chair, the space for chair movement must be 4 ft wide for maximum comfort. It means that any drawers in the table at sides, or any wooden rack placed at far side of table (to place an electronic switch board or computer casing for example) must be beyond the 4 ft width. Since (as explained later below) recommended width of single-person table is 5 ft, placing drawers at sides in table is not practical unless the drawers are extremely narrow (4 inches wide).

Cabinets:

    Cabinets, be them kitchen ones or clothes ones or office ones needs a 4 ft space behind them for cabinet door to be comfortably open plus space for person to stand, as long as the door of cabinet is less than 2 ft wide. The point is that, the person standing must have a 2 ft space atleast when cabinet door is fully opened.

    Later we will see that depth of no cabinet should exceed 18 inches inside the cabinet (means other than the walls of cabinet). Its because distance between elbow and tip of middle finger of hand is under 18 inches in 95% of humans, therefore any length beyond 18 inches requires elbows to be bend which is a pain.

    Later we will see that the width of walls of cabinet should never exceed 2 inches. This limits the depth of cabinet including cabinet-walls to 22 inches, meaning that door of cabinet can not be greater than 11 inches if there are two doors and 22 inches if there is only one door. So about 2 ft length of door plus 2 ft space behind the cabinet for person to stand, a total of 4 ft space is needed near all cabinets to both stand and comfortably use the cabinets. Ofcourse 4 ft. width means that a person on wheel chair can also use that space to comfortably move around the room / kitchen when the cabinet is closed.

    As discussed below in the section of Office Tables, it is found that effective reach of a person width wise is under 5 ft, therefore no cabinet including walls should be more than this wide. Infact, the most comfortable width inside is 4.5 ft i.e. excluding walls.

    Therefore, recommended dimensions of cabinets is: 5 ft x 2 ft (outside), 4.5 ft x 1.5 ft (inside)

Office Tables:

    A 6 ft. person with arms stretched at 0 degrees covers as much space horizontally as his height i.e. 6 ft. When sitting on a table, a person has to reach not only the ends of table at 0 degrees but also at some greater than zero degrees to grasp things put at sides of tables at extreme i.e. corners of table. Therefore, 5 ft. is the recommended width of a single-person table i.e. office table. Beyond 5 ft the person cannot use without standing up or extending at uncomfortable positions at sides.

    Length wise, when sitting comfortably at table, a person has his elbows at the edge of table, so can reach to 18 inches in front. Since the length of whole arms is 27 inches (distance between shoulder and tip of middle finger of hand), a person can reach 27 inches in front. If the person sit as close to table as he can, that is table touching his chest, he can reach 27 inches in front without bending, and 36 inches in front when bending as much as he can without leaving the chair. Therefore, the maximum reach of hand on table is 36 inches. We have to keep this as a standard because a person's hands need not reach all the edges of table to fully use the table, this is because the objects the person want to grasp have some volume of their own, so a 27 inches reach is enough to utilize a 36 inches space when most of the things (files, papers, printers etc) have about 9 inches width of their own.

    Conclusion:

        5 ft width and 3 ft length.

Mattresses:

    A person needs 18 inches shoulder to shoulder when fully packed with other person, 24 inches if some muscles' and hips' space is allowed and 27 inches without having any physical contact with neighbours. 36 inches is good enough to walk but not enough to sleep because some people like to put arms at sides and also we have to keep room for turn-overs during sleep. However, if some open space is allowed at sides of mattress then 36 inches width of mattress is enough. If we do not want the person to extend any body part outside mattress during sleep, then 4.5 ft or 54 inches is the most we need.

    Length-wise, 81 inches is enough. This allows 72 inches (6 ft) of person's height plus 6 inches for pillow plus 3 inches below person.

    54 inches is also wide enough for two adults to sleep (but with some discomfort) and for one adult and one child to sleep comfortably.