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.
No comments:
Post a Comment