Shamir's Secret Shring

Introduction:
In the year 1979, an article appeared in the 22nd volume and 11th issue of the journal “Communications of ACM”. The article was written by a person called Adi Shamir from Massachusetts Institute of Technology. The article was called “How to share a secret?”. The article spoke about a secret sharing scheme which divided the secret into parts and distributes these parts to the secret-keepers.
Over the years, this scheme has been the focal point of many cryptographic techniques. Also, many new schemes have been developed based on this idea. This scheme is particularly fascinating because, it opens up a whole new realm of computational hardness problems (such as the RSA encryption scheme).
General idea of Shamir’s secret sharing!
Data security is one of the most important and essential fields today. Why is data security necessary?
Consider this example.
There is a strong room of a bank. It should have some security. Consider that the bank has three managers. The lock of the strong room must be designed such that if any two of the three managers come they must be in a position to open the room.  Here the idea is that the security is more when two keys are required to open the lock rather than just one key.
                                             
What are the possible combinations in which the managers open the room or in other words how many different doors are required for the strong room? There are 3 managers and any two can open the door. Hence there are 3 choose 2 possibilities32. If the number of managers is less then this method can be easily implemented.
In the original article the author used the analogy of 11 scientists working on a science project. They are faced with the problem of placing their findings in a secret cabin. The scheme is such that 6 or more scientists should be able to open the cabin at any given time. It is not hard to show that the minimal solution involves 462 locks and 252 keys per scientist. These numbers are clearly impractical as far as implementation is concerned. What is more intriguing and impossible is that these numbers become exponentially large as the number of participants increases.
Secret sharing principle:

• Let the number of people be n.
• Let the number of people required to open the door be k.
• The idea is to choose a polynomial whose degree is k-1.
• The roots of the equation are distributed as the keys.
• The polynomial is calculated to open the door.
• n keys are generated for the polynomial. Each of the keys is a point on the polynomial.
• For example, consider a straight line ax+b=c . Two points are enough to find the equation of the straight line. However, any point on the straight line can be distributed as a key.
• Generalizing the idea for a k th degree polynomial k keys are sufficient to obtain the polynomial. But any n points on the polynomial can be distributed as keys.
• Lagrange’s interpolation method is used to obtain the polynomial initially.

Mathematical Representation:   
  Formally our goal is to divide D( the secret) into n pieces say D1, D2, D3……….,Dn in such a way that :

1. Knowledge of any k or more Di pieces make D easily computable.
2. Knowledge of any (k-1)  or fewer Di pieces leaves D undetermined.

This scheme is called (k,n) threshold scheme.

Mathematical Representation:   
  Formally our goal is to divide D( the secret) into n pieces say D1, D2, D3……….,Dn in such a way that :

1. Knowledge of any k or more Di pieces make D easily computable.
2. Knowledge of any (k-1)  or fewer Di pieces leaves D undetermined.

This scheme is called (k,n) threshold scheme.

the idea of this secret sharing scheme is that, 2 points are sufficient to define a straight line, 3 points are sufficient for a parabola, 4 points for cubic circle etc…….
That is, it takes k points to define a polynomial of degree (k-1). Say, F is a finite field and say a0,a1,a2,……ak-1are coefficients.
f(x)=a0+a1x+a2x2+……………….ak-1xk-1
Let us construct any n points out of the function f(x). For instance, i=1……..n  to retrieve (i, f(i) ). Every participant is given a point (a pair of input to the polynomial and output). Given any subset of k points, the coefficients of the polynomial can be calculated using interpolation. The secret is the constant term a0.

Shamir’s secret sharing scheme provides are very secure, dynamic, and extensible scheme. Participants can be added or deleted whenever necessary. Thus this secret sharing method is one of the most robust and secure methods available for situations involving many participants and one secret!!

Vigenere cipher

The Vigenère cipher is a method of encrypting alphabetic text by using a series of different Ceasar ciphers based on the letters of a keyword. The Vigenère cipher is named after Blaise de Vigenère.

It is based on a technique that appears to be unsolvable!!!

ENCRYPTION:

The input taken is plain text with special characters and numbers eliminated. A second text known as the key of length k is used to encrypt the plain text.The new text obtained after this process is called the cipher text(encrypted text). Each character in the alphabet is given a weight based on its position(i.e from 0 to 25)

                    a=0

                    b=1

                    .

                    .

                    z=25

 Now, consider the plain text (say P₀, shown bellow), and a key (SET). Place the key repeatedly below the plain text to span till the end of plain text. it is clearly seen that there now exists a one to one correspondence between a character of the P₀ and the key as shown below.

P₀:         T H I S I S M Y P L A I N T E X T

KEY:        S E T S E T S E T S E T S E T S E

      

Now, each character in the plain text is replaced by another character based on a "shift". The plain text character is "shifted" corresponding to the key character's weight to obtain the new character.The text thus obtained is called the cipher text. For the example above,the key is SET. The equivalent weight of each character is given by:

S=18

E=4

T=19

Thus the cipher text (C₀) is obtained by shifting the first character by 18 positions in the english alphabet set, the second character by 4 positions, the third character by 19 positions, the fourth character by 18 and so on..

P₀:           T H I S I S M Y P L A I N T E X T

KEY:          S E T S E T S E T S E T S E T S E

C₀:           L L B K M L E C I D E B F X X P X 

Thus we have obtained our cipher text.

DECRYPTION:

To begin the decryption process, we start by finding the length of the key. We shift the cipher text by one position towards the right to obtain C₁. We compare the obtained shifted text C₁ to the initial cipher text C₀ to find the number of collisions. This is repeated to obtain C₂, C₃, C₄ and so on upto one less than the number of characters in C₀ as continuing will repeat the generation of C₀,C₁,C₂ respectively.

For example:

C₀:        L L B K M L E C I D E B F X X P X

C₁:        X L L B K M L E C I D E B F X X P                             

   

As seen from the above example, at positions 2 and 15, the same characters occur (L and X) in C₀ and C₁ resulting in collisions. Thus the number of collisions is 2.

Similarly we obtain C₂,C₃ and so on and obtain the number of collisions in each case. Comparing the results of each of them, we observe that there is a sudden increase in the number of collisions for a particular C_n. This reveals that the length of the key is n. This happens so because, if the length of the key is n,then every nth character is encrypted by the same alphabet of the key. Thus for maximum collisions, every character seperated by a distance of 'n' must be the same and will be encrypted by the same letter of the key. This happens only when the cipher text is shifted by 'n' positions and it will have the same number of collisions as that of the plain text when shifted by 'n' positions.

Once the length of the key is obtained, we have to find the individual characters of the key. Since the plain text taken is valid English text, the occurance of characters is biased and not random. Some letters occur with higher frequency than the rest. Keeping this fact in mind, we crack each character of the key.

We extract all the characters from the cipher text that have been encrypted by 1st character of the key and store them in an array i.e the 1st, (n+1)th, (2n+1)th... characters are stored in the array.

The frequency of all characters in this array are calculated. From the tabulated frequency of the English alphabet, we can see that the most occuring character is the alphabet 'e'. Similarly, we find the most occuring character in the array and match it to 'e' which means that all the 'e's have become the most occuring character. Hence the character shift is determined and this shift gives us the corresponding equivalent character.For example, if the most occuring character was found to be 'v', then it means that all the 'e's have become 'v's which means that a shift of 17 has occured. this tells that the first character of the key is the 17th alphabet i.e 'q'.

FREQUENCY DISTRIBUTION OF ENGLISH CHARECTERS:

Now, we extract all the characters that have been encrypted by the second character of the key and repeat the above process.

This process is repeated for the rest of the characters and all the characters of the key are determined.

Once the key is known its a child's play to decipher the text!!

Authors:


Amitash Ramesh

Soumya Ramesh

Varsha Bhat K

CHAIN MATRIX MULTIPLICATION

“Neo: What is the Matrix?
Trinity: The answer is out there, Neo, and it's looking for you, and it will find you if you want it to’’…You guys remember this famous quote from the movie ‘MATRIX’? Yes? No?
Anyways, if Neo would have bothered to ask us the same question instead of asking Trinity, most would have given an answer we learnt since 4th grade…’Matrix is a rectangular collection of elements arranged in rows and columns. These elements can be numbers, expressions or symbols’…Don’t you agree?
Among the various operations that can be applied on matrices, let us concentrate on matrix multiplication. Given 2 matrices everybody knows how to multiply them. If we need to multiply matrix A with matrix B then the first thing we do is check if the number of columns in A equals rows in B. If it’s not so, then matrix multiplication is invalid. The product AB is nothing but the dot product of corresponding rows of A with columns of B. Here is an algorithm for matrix multiplication.


MATRIX_MULTIPLICATION(A,B)
1.if columns(A) != rows(B)
2.$\hspace{0.2in}$ “invalid”
3.else for i $\leftarrow$ 1 to rows(A)
4.$\hspace{0.2in}$$\hspace{0.2in}$for j $\leftarrow$ 1 to columns(B)
5.$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$do C[i, j] $\leftarrow$ 0
6.$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$for k $\leftarrow$ 1 to columns(A)
7.$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$do C[i, j] $\leftarrow$ C[i, j] + A[i, k] $\times$ B[k, j]
8.return C
The basic operation in the above algorithm is in the inner most ‘for’ loop.
i.e C[i, j] = C[i, j] + A[i, k] $\times$ B[k, j] which contains both addition and scalar multiplication. Since multiplication is costlier than addition we can safely say that cost of multiplying 2 matrices depends on number of such scalar multiplications. So what is the cost? Here is how you find it. If A is a matrix of order p$\times$q and B is of order q$\times$r, then to find each C[i, j] you have to conduct q scalar multiplications[True isn’t it? Check out the inner most for loop. It executes columns(A) times, which is nothing but q times] and there are p$\times$r elements in product C. Hence in total there are pqr scalar multiplications. Hence cost of multiplying matrix AB is pqr.
This is when you have 2 matrices to be multiplied. What if you have a sequence of, say ‘N’, matrices to be multiplied? Given a chain of matrices ABCD, how do you multiply them? If one of the matrix is Boolean we may start by multiplying that matrix because it seems easier to start with or some of us may just start multiplying the matrices in the order they have been presented or may follow some other pattern. Multiply in any order, it doesn’t matter, (“do you agree? Please remember your answer to this”) matrix multiplication is associative. Multiply it either as (AB)(CD) or (A(B(CD))) or (((AB)C)D) or ((A(BC))D) or (A((BC)D)). We get the same product.

Now check this out. Consider the problem of multiplying the chain ABC where A is of order 10$\times$100, B is of order 100 $\times$ 5 and C is of order 5$\times$50. Now we can multiply ABC by grouping them in 2 different ways, (A(BC)) and ((AB)C). People always say try applying what you have studied. Common let us give it shot. Sometime back we learnt that cost of multiplying 2 matrices is pqr. Remember!!! Applying this to find the cost or number of scalar multiplications in (A(BC)) we get the result as follows:
1. Cost of multiplying BC is 100 $\times$ 5 $\times$ 50 = 25000
2. Next matrix A of order 10 $\times$ 100 is multiplied with product BC of order 100 $\times$ 50 and the cost turns out to be 10 $\times$ 100 $\times$ 50 = 50000
3. Total cost of multiplying (A (BC)) is : 25000+50000 = 75000
Following the same procedure the cost of multiplying ((AB)C) is:
10 $\times$ 100 $\times$ 5 + 10 $\times$ 5 $\times$ 50 = 7500.
Did you see!!! Same chain of matrices multiplied to obtain the same product, but the cost of multiplying (A (BC)) is 10 times higher than the cost of multiplying ((AB) C). Everyone who agreed previously that the order in which matrix is multiplied doesn’t matter, you were wrong. Because it does matter and you know the reasons too. [There are 2 ice-creams, same flavor, amount and everything, just that the chocolate layer in one comes before the vanilla layer in the other. Both the ice-creams cost different. Which one do you choose? P.S: Imagine both the combo gives the same yummy taste. ]





Chain-Matrix multiplication problem is nothing but given a chain <$A_1$,$A_2$,…$A_n$> of n matrices, where for i=1,2,…n , $A_i$ has dimensions $p_{i-1}$ $\times$ $p_i$ fully parenthesize the product $A_1$$A_2$…$A_n$ such that it minimizes the number of scalar multiplications. So now we have to find the optimal way of parenthesizing the matrices so that number of scalar multiplications and hence the cost is minimum. The time spent on finding the optimal parenthesizations is well paid for the time spent later on actual multiplication. How do we find out the optimal parenthesization? The first idea that strikes our mind is to find all different ways of grouping or parenthesizing the chain of matrices and finding the cost in each case. Then choose the grouping which has the minimum cost. That sounds right and it is right. So let us find out the number of ways of grouping the chain of matrices. Let n be the matrix count. If P(n) represents the number of ways of grouping then

P(1) = 1 [Because there is only one matrix and there is only one way to parenthesize it]

Now consider ABC. You can parenthesize them as (A(BC)) wherein you are actually parenthesizing 2 sub products A and BC or can parenthesize as ((AB)C) wherein the sub products are AB and C. You can notice that we are trying to split it into 2 sub products. Let us consider this split position as ‘k’ where for $A_{i}$...$A_{j}$ i $\leq$ k < j. For n=3, split can happen at position 1 and 2.Therefore k =1, 2 for n=3.After splitting into sub products, each sub product will again be a chain of matrices and again they need to be parenthesized and the process goes on recursively. To generalize, recurrence relation is: P (1) = 1 for n=1 P (n) = $\sum_{k=1}^{n-1}$ P(k)P(k+1) for n $\geq$ 2 The solution to the above relation turns out to be $\Omega$ ($2^n$).This means the number of ways of grouping is exponential in ‘n’ and if we apply the first idea that struck into our mind(hope you remember it… i. e Finding all possible grouping…), which is nothing but brute force method we won’t end up in an efficient algorithm. There must be some other way out. Let us look a little deeper into the grouping method. As mentioned before by parenthesizing we get 2 sub products which again need to be grouped and that grouping should also be optimal. That is nothing but while grouping we get sub problems and sub problems must be solved by taking it as another chain matrix multiplication problem. So can we say that optimal solution to the problem is obtained by finding optimal solution to the sub problem? You bet we can!!! Let us keep this as one of the observations. Ok going to the next observation. Given ABCD. If we apply the brute force method then we have to check out the cost of all possible grouping for ABCD. If at first we tried (AB)(CD).This includes cost of computing AB + CD. Next we try (((AB)C)D).This again includes finding cost of multiplying AB!!. Instead of recalculating it, we can minimize the cost if we just store the already computed value… [I think by now most of you know which method to apply to solve this problem $\smile$] .So as we can observe there are only few distinct sub problems. Let’s pen down the observations. Observation: 1. Optimal solution to the problem is obtained by finding optimal solution to the sub problems. 2. There are only few distinct sub problems From the above discussions and observations we can conclude that dynamic programming can be applied to solve the chain matrix multiplication problem…Store the calculated values, find the cost for different values of k. Choose the k that results in minimum cost…There you go. That is the main funda. For 1 $\leq$ i $\leq$ j $\leq$ n , Let m[i, j] denote the minimum number of scalar multiplications required to find the product $A_{i...j}$ [From now on product of $A_{i}$....$A_{j}$ is denoted as $A_{i...j}$] . If final optimal solution of $A_{i}$....$A_{j}$ involves splitting into $A_{i}$....$A_{k}$ and $A_{k+1}$…$A_{j}$, then total minimum cost equals sum of minimum cost of parenthesizing of $A_{i...k}$ and $A_{k+1...j}$ and the cost of multiplying $A_{i...k}$ and $A_{k+1...j}$. Cost of multiplying is $p_{i-1}$$p_k$$p_j$ where $A_i$ has dimensions $p_{i-1}$ $\times$ $p_i$. Based on this we can develop the following recurrence relation: m[i, j] = 0 $\Rightarrow$ if i=j [Since there is only one matrix no multiplication required] m[i, j] = $\underset{i <= k < j}{min}${m[i, k] + m[k+1 ,j] + $p_{i-1}$$p_k$$p_j$ } otherwise... For a particular i and j, there are j-i different values of k. Out of these ,one k gives the minimum cost which is stored in m[i ,j]. But then we lose the value of k where split or grouping should occur so that the cost is least of all. So let us take s[i, j] which stores the value of k for which m[i, j] is minimum. Using the knowledge we gained so far let us try building an efficient algorithm using dynamic programming that computes optimal cost in tabular form using bottom up fashion. [Try to be like Uncle scrooge when you are developing an algorithm. Try the one which costs the least $\smile$. Just as in ice cream example. ] We will require 2 tables, one for m [i, j] and another for s[i, j]. Also the table should be filled in such a manner that when an m [i, j] is calculated using recurrence relation m [i, k] and m [k+1, j] is already calculated. For both the cases, the corresponding length of the matrix-chain are less than j-i+1. Hence, the algorithm should fill the table in increasing order of the length of the matrix chain. As is always the case, how much ever someone blabbers nothing explains best as examples do...So consider the problem of multiplying the following matrices with their dimensions as follows: • $A_1$: 30 $\times$ 35 • $A_2$: 35 $\times$ 15 • $A_3$: 15 $\times$ 5 • $A_4$: 5 $\times$ 10 • $A_5$: 10 $\times$ 20 • $A_6$: 20 $\times$ 25 Based on what is said above, [please be sure that you understood the above points. If not, just go back and read the above para…Common don’t be lazy , Off u go… $\smile$] to find the optimal grouping of $A_1$$A_2$$A_3$$A_4$$A_5$$A_6$ we find m[i, j] and the corresponding s[i, j] in the following order : m[1,1], m[2,2], m[3,3] … m[6,6] m[1,2], m[2,3] … m[5,6] m[1,3],.......m[4,6] m[1,4],...m[3,6] m[1,5],m[2,6] m[1,6] Hence if we start filling the table in this order, m [i, i] will be 0.They all come up in one row. Next comes m[1,2]…. m[1,2] =m[1,1] + m[2,2] + $p_0$$p_{1}$$p_{2}$ $\hspace{0.2in}$=0+0+15750 $\Rightarrow$ [notice that m[1,1] and m[2,2] is taken from the table ] s[1,2]=1 $\Rightarrow$ [only choice] Similarly we find for all sub products of length 1.Next we go for sub products of length 2 ,thus filling the 3rd row of table m from bottom. Go on filling the table to get it in a final form as shown below.


The table stores the costs of computing for each sub product and also the corresponding split positions so there is no need for recalculation. What we needed is minimum cost of multiplying the given 6 matrices and it is nothing but
m[1,6]= 15125 with split at position s[1,6]=3.
So given $A_1$$A_2$$A_3$$A_4$$A_5$$A_6$ how do you parenthesize it? Check out the table s[i, j]
s[1,6]=3 $\Rightarrow$ ( $A_1$$A_2$$A_3$ ) ( $A_4$$A_5$$A_6$ )
s[1,3]=1,s[4,6]=5 $\Rightarrow$ ( $A_1$ ( $A_2$$A_3$ ) ) ( ( $A_4$$A_5$ ) $A_6$)
Done!!! That’s how you do the grouping. Wasn’t that simple enough!!!
Now we are left with only one job…. writing the algorithm. I think you guys can easily build it up using the concepts above and the algorithms. Anyways algorithm is given below
MATRIX-CHAIN-ORDER(n)
1.for i $\leftarrow$ 1 to n
2.$\hspace{0.2in}$do m[i, i ] $\leftarrow$ 0
3.for d $\leftarrow$ 2 to n [ d is the chain length]
4.$\hspace{0.2in}$do for i $\leftarrow$ 1 to n − d + 1
5.$\hspace{0.2in}$$\hspace{0.2in}$do j $\leftarrow$ i + d − 1
6.$\hspace{0.2in}$$\,$m[i, j ] $\leftarrow$ $\infty$
7.$\hspace{0.2in}$$\hspace{0.2in}$$\,$for k $\leftarrow$ i to j − 1
8.$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$do q $\leftarrow$ m[i, k]+m[k + 1, j ]+$p_{i-1}$$p_k$$p_j$
9.$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$$\,$ if q < m[i, j ] 10.$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$$\,$then m[i,j] $\leftarrow$ q 11.$\hspace{0.2in}$$\hspace{0.2in}$$\hspace{0.2in}$$\,$$\,$s[i, j ] $\leftarrow$ k 12.return m and s Time complexity of this algorithm is O($n^3$) which is way better than the exponential time taken for brute method. Voila!!! Uncle Scrooge will be way to happy with this business!!

So here was a brief [OK, actually not brief… ] explanation about the chain matrix multiplication .Hope it was helpful. So remember, it is good to be like Uncle Scrooge while building an algorithm, Happy multiplying!!!! $\smile$

Shobitha Shetty

The Fibonacci Heaps

One fine morning, I heard my mom shouting at me…" What the hell is this? Look at your room. Why don’t you learn to arrange things properly? Blah blah and BLAH...” . I bet, this is the scene in your home too (if you are a lazy kid ) I never felt the importance of organizing things until I realized that searching of certain things becomes really difficult when you don’t arrange your things. Being a computer enthusiast, I wondered how such large amount of data was organized in computer. Later I was enlightened() by the amazing concept of Data Structures that binds everything together in an organized way.

Coming to Data Structures, it is a particular way where in data is organized and stored so that it can be used efficiently. Array, Hash table, stacks, queues, binary heap, Linked Lists are few popular data structures. In this blog, we'll discuss another ingenious data structure known as Fibonacci Heaps.

Fibonacci heap!! Fibonacci series and Heaps !! Whoa..Two amazing concepts spliced together !! Michael L. Fredman and Robert E. Tarjan are the brains behind it.

Let us start the kindergarten of Fibonacci heap

Level 0: Pre- Requisites

In order to understand this, it’s good if you have a prior knowledge about the data structure circularly doubly linked list. If you can’t recall what it is,just take a look at the figure below.

What you need to know is just this:

1. Inserting or removing a node from any location is done in O(1) time.
2. Given two circularly doubly linked lists, we can concatenate them into one list in O(1) time.

Another basic concept of heap should be known.

Min-Heap : A heap in which the value of the parent node is less than that of the child nodes.

We are done with the pre-requisites. Just make sure that you are thorough with it.
Level 1: Structure of a node in Fibonacci heap.

‘A picture speaks a thousand words’. So, it is very important to know “What does it look like?". So, here we are!!

Siblings: Children of same node are called siblings. Obvious isn’t it? :)

Node label: Name of the node.

Key: Information that the node holds.

Degree: It is a attribute of a node to indicate the number of children it has.

Mark : It is a Boolean value which indicates if it has lost one of its child or not

Child: A pointer of a node that points to any one of its children.

Structure of a Fibonacci Heap:

• Fibonacci heap is a collection of many trees.
• Roots of such trees form the root list.
• H.min is a heap attribute that points to the minimum in the root list.

One important thing to be noted is that the values in the root list are unordered but the trees in the heap are min-heap ordered.

Level 3: Operations.

• MAKE-FIB-HEAP :

A home is constructed for Fibonacci heap to live in :P That is, it allocates memory for the heap to be created. This function returns a Fibonacci heap object H, but there are no trees in H.

• INSERT (H, x) : H is the Heap. x is the node label.

There are two possibilities. If it is the first node being inserted, then H.min points to it. Else a new node inserted becomes left sibling of the H.min node by convention.

• Finding the minimum node: Accessing the H.min gives the minimum.

• UNION (H1, H2):

This function plays a role of a broker who bonds two heaps into one with minimum commission

If H1 and H2 are two heaps, then a new heap, H = H1 +H2. H1 and H2 are destroyed.

• Extract-Minimum (H):

The H.min is extracted. Now that the children of H.min are orphans (not a technical term), they are sheltered in the root list But as the root list has to be optimized, CONSOLIDATE function is used to set everything right. It aims at having nodes in the root list with distinct degree in order to minimize the number of elements in the root list.

• · Decrease Key (H, x, k):

Given a node label in a heap, its key can be decreased to desired extent. Later the heap is restructured to preserve its property by CUTS and CASCADING CUTS.

1. Say a node G is marked and has a child P.

2. P has children X and Y.

3. As a result of some operation say P lost its child Y. Now P is marked and is left with the only child 'X'.

4. Lets say the node 'X' is decreased by a finite amount.

5. There are two possibilities.

a. H.min < X.key

b. X.key < H.min (Violation of the heap min-heap property)

6. What we know is that H.min has to be sheltered in root list and H.min is the minimum among all the other elements of heap. Hence we just CUT the node X and is attached as the left sibling of the H.min(again by convention).

7. Now due to Decrease-Key operation even X will have to part from P which means P is losing its second child. Unfair right?

8. Hence P is detached from G and attached as the left sibling of the H.min now. This detachment is termed as CASCADING CUT.

9. But what about G? G is marked and has already lost one of its child. To add to the sorrows, it losing P now. Hence G is detached from its parent and added into the root list as the left sibling of H.min.

10. This goes on till it encounters a node which is unmarked. These are called CASCADING CUTS which are recursive in nature.

If you got stuck somewhere, please take a look at this figure.

(Click on it to get a clear view)

• Delete Key:

What do you think is the obvious way of doing it?

Firstly decrease the key to -∞ and extract the minimum. The node gets deleted.

Why is this better?

‘A stitch in time saves nine’. This proverb stands as a backbone in all walks of life and so in computer science. The true usefulness of the data structure is decided based on the time it takes to perform certain operations on it.

Now let’s compare with the time complexities of two different data structures. Binomial Heaps and Fibonacci heaps. Similar in structure, but with different characteristics.

Here we look at the amortized time it takes to perform all these operations. Clearly, Fibonacci heaps are way better when compared to the time complexity of the binomial heaps.

Why the name ‘Fibonacci’ heap?

We have come almost to the end of the story and still we haven’t justified the name given to it. Formally speaking,.

If F_k represents the k^th Fibonacci number, then the size of a node x is always greater than F_k+2, where k is the degree of the node x.

Size(x) is nothing but the size of the tree rooted at x i.e. the number of nodes it holds including itself.

Let us take the example of this figure.

By the rule,

Which is true

Hence this is a part of Fibonacci heap. Basically, the idea of Fibonacci series is plugged into the concept of heap and all together a new data structure called ‘Fibonacci Heap’ is formed.

If you did not understand any of the above, here is the essence of it. Fibonacci heap is a data structure which is desirable when the number of EXTRACT-MIN and DELETE operations is small relative to the number of other operations performed. It is an efficient data structure. It finds its application in Dijkstra's algorithm, Minimum Spanning Tree etc. For more details on this, please download

http://www.filestube.com/c/cormen+algorithms+pdf

By the way, my Mom is a sweet lady and so am I

Shruthi R Nayak