The Insertion sort, algorithm for sorting a list L of n numbers represented by an array A [ 1 n] proceeds by picking up the numbers in the array from left one by one and ACH newly picked up number is placed at its relative position, w. r. T. The sorting order, among the earlier ordered ones. The process is repeated till each element of the list Is placed at Its correct relative position. 2. Bubble sort The Bubble Sort algorithm for sorting of n numbers, represented by an array A [1 .. Nil, proceeds by scanning the array from left to right.

At each stage, compares adjacent pairs of numbers at positions A[I] and A [I +1] and whenever a pair of adjacent numbers Is found to be out of order, then the positions of the numbers are exchanged. The algorithm repeats the process for numbers at positions A [1+1] and A I + 2] 3. Selection sort Selection Sort for sorting a list L of n numbers, represented by an array A [ 1.. N], proceeds by finding the maximum element of the array and placing It In the last position of the array representing the list.

Then repeat the process on the sub array representing the subsist obtained from the list excluding the current maximum element. 4. Shell sort The sorting algorithm Is named so in honor of D. L Short (1959), who suggested the algorithm. Shell sort Is also called diminishing -Increment sort. The essential Idea behind Shell Sort is to apply any of the other sorting algorithms (generally Insertion Sort) to each of the several interleaving subsists of the given list of numbers to be sorted.

In successive iteration, the subsists are formed by stepping through the file with an Increment INC taken from some pre- defined decreasing sequence of step - . INC 1, which must terminate In 1. 5. Heap sort sizes INC > > In order to discuss Heap - Sort algorithm, we recall the following definitions; where we assume that the concept of a tree is already known: Binary Tree: A tree is called a binary tree, If it is either empty, or It consists of a node called the root together with two binary trees called the left substrate and a right substrate.

In respect of the above definition, we make the following observations. 1. It may be noted that the above 1 org in its own terms (I. E. Binary tree). 2. The following are all distinct and the only binary trees having two nodes. Heap: is defined as a binary tree with keys assigned to its nodes (one key per node) such that the following conditions are satisfied. I) The binary tree is essentially complete (or simply complete), I. E. All its levels are full except possibly the last where only some rightmost leaves may be missing. T) The key at reach node is greater than or equal to the key at its children. The following binary tree is Heap 6. Merge sort In this method, we recursively chop the list into two subsists of almost equal sizes and when we get lists of size one, then start sorted merging of lists in the reverse order in which these lists were obtained through chopping. The following example clarifies the method. 7. Quick sort Quick sort is also a divide and conquer method of sorting. It was designed by C. A. R Hoarer, one of the pioneers of Computer Science and also Turing Award Winner for the year 1980.

This method does more work in the first step of partitioning the list into two subsists. Then combining the two lists becomes trivial. To partition the list, we first choose some value from the list for which, we hope, about half the values will be less than the chosen value and the remaining values will be more than the chosen value. Division into subsist is done through the choice and use of a pivot value, which is a value in the given list so that all values in the list less than the pivot are put in one list and rest of the values in the other list.

The process is applied recursively to the subsists till we get subsists of lengths one. The choice of pivot has significant earning on the efficiency of Quick Sort algorithm. Sometime, the every first value is taken as a pivot. Generally, some middle value is chosen as a pivot. Divide and Conquer Technique The Divide and Conquer is a technique of solving problems from various domains and will be discussed in details later on. Here, we briefly discuss how to use the technique in solving sorting problems.

A sorting algorithm based on Divide and Conquer technique has the following outline. Procedure Sort (list) If the list has length 1 then returns the list Else {I. E. , when length of the list is greater than 1} Begin Partition the list into two subsists say L and H, sort (H) Combine (sort (L), Sort (H)) {During the combine operation, the subsists are merged in sorted order} End There are two well known Divide and conquer methods for sorting: I) Merge sort it) Quick sort Question 2 - Explain in your own words the different asymptotic functions and notations.

Well Known Asymptotic Functions & Notations The purpose of these asymptotic growth rate functions to be introduced is to facilitate the recognition of essential character of a complexity function through some simpler functions delivered by these notations. For examples, a complexity function (n) = 5004 no + 83 no + 19 n + 408, has essentially same behavior as that of g(n) = no as the problem size n becomes larger and larger. But g(n) = no is much more comprehensible and its value easier to compute than the function f(n) Enumerate the five well known approximation functions and how these are pronounced.

O : (O (n 2) is pronounced as 'big - Oh of no' or sometimes Just as Oh of no) Q : (Q (n 2) is pronounced as 'big - omega of no' or sometimes Just as omega of no) e : (e (n 2) is pronounced as theta of no') o : (o (n 2) is pronounced as 'little - Oh of no') : (o (n 2) is pronounced as 'little - omega of no') These approximations denote relations from functions to functions. For example, if functions f, g: N *N are given by f (n) = no - an and then O (f(n)) = g(n) or O(no - an) = no The Notation O Provides asymptotic upper bound for a given function.

Let f(x) and g(x) be two functions each from the set of natural numbers or set of positive real numbers to positive real numbers. Then f(x) is said to be O (g(x)) (pronounced as big - Oh of g of x) if there exists two positive integers / real number constants C and k such that f(x) g(x) for all x k The Q Notation The Q notation provides an asymptotic lower for a given function. Let f(x) and g(x) be two functions, each from the set of natural numbers or set of positive real numbers to positive real numbers.

Then f(x) is said to be Q (g(x)) (pronounced as big - omega of g of x) if there exists two positive integer/ real number constants C and k such that f(x) (g(x)) whenever x k Provides simultaneously both asymptotic lower bound and asymptotic upper bound for a given function. Let f(x) and g(x) be two functions, each from the set of natural numbers or positive real numbers to positive real numbers. Then f(x) is said to be e (g(x)) (pronounced as big - theta of g of x) if, there exists positive constants CLC, CO and such that CO g(x) f(x) CLC(x) for all x k.

Theorem: For any two functions f(x) and g(x), (g(x)) if and only if f (x) = O (g(x)) and f(x) = Q (g(x)) where f(x) and g(x) are nonnegative. The Notation o The asymptotic upper bound provided by big - Oh notation may or may not be tight in the sense that if(x) = ex. + ex. + 1. Then for f(x)= O (xx) , though there exist C and k such that f(x) (xx) for all x k yet there may also be some values for which the following equality also holds f(x) = C (xx) for x k However, if we consider boo = o (xx) then there cannot exist positive integer C such that f(x)=Ex. for all x k

The case off(x) = O (xx) , provides an example for the notation of small - Oh. The notation o Let f(x) and g(x) be two functions, each from the set of natural numbers or positive real numbers to positive real numbers. Further, let C > O be any number, then f(x) = o (g(x)) (pronounced as little Oh of g of x) if there exists natural number k satisfying f (x) < C g (x) for all x 2k 21 (B) Here we may note the following points i) In the case of little - Oh the constants C does not depend on the two functions f(x) and g(x) .

Rather, we can arbitrarily choose C > O it) The inequality (B) is strict whereas he inequality (A) of big - Oh is not necessarily strict. The Notation Again the asymptotic lower bound Q may or may not be tight. However, the asymptotic bound w cannot be tight. The definition of w is as follows; Let f(x) and g(x) be two functions each from the set of natural numbers or the set of positive real numbers to set of positive real numbers. Further Let C > O be any number, then f (x) = (g(x)) if there exist a positive integer k such that f(x)>C g(x) for all x k.

Question 3 - Describe the following: Fibonacci Heaps Binomial Heaps Fibonacci heap is a collection of min-heap-ordered trees. The trees in a Fibonacci heap are not constrained to be binomial trees. Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps are rooted but unordered. As Figure to any one of its children. The children of x are linked together in a circular, doubly linked list, which we call the child list of x. Each child y in a child list has pointers left [y] and right [y] that point toys left and right siblings, respectively. If node y is an only child, then left [y] = right [y] = y.

The order in which siblings appear in a child list is arbitrary. Two other fields in each node will be of use. The number of children in the child list of node x is stored in degree[x]. The Boolean-valued field mark[x] indicates whether node x has lost a child since the last time x was made the child of another node. Newly created nodes are unmarked, and a node x becomes unmarked whenever it is made the child of another node. A given Fibonacci heap H is accessed by a pointer min [H] to the root of a tree containing a minimum key; this node is called the minimum node of the Fibonacci heap.

If a Fibonacci heap H is empty, then min [H] = NIL. The roots of all the trees in a Fibonacci heap are linked together using their left ND right pointers into a circular, doubly linked list called the root list of the Fibonacci heap. The pointer min [H] thus points to the node in the root list whose key is minimum. The order of the trees within a root list is arbitrary. Potential function: For a given Fibonacci heap H, we indicate by t (H) the number of trees in the root list of H and by m(H) the number of marked nodes in H.

The potential of Fibonacci heap H is then defined by (H) = t(H) + mm(H) For example, the potential of the Fibonacci heap shown in Figure is 5+2. 3 = 11. The potential of a set of Fibonacci heaps is the sum of the potentials of its constituent Fibonacci heaps. We shall assume that a unit of potential can pay for a constant amount of work, where the constant is sufficiently large to cover the cost of any of the specific constant-time pieces of work that we might encounter. We assume that a Fibonacci heap application begins with no heaps.

The initial potential, therefore, is O, and by equation (a), the potential is nonnegative at all subsequent times. Maximum degree: The amortized analyses we shall perform in the remaining sections of this unit assume that there is a known upper bound D(n) on the maximum degree of any node in an n-node Fibonacci heap. Binomial Heaps A binomial heap H is a set of binomial trees that satisfies the following binomial heap properties. 1. Each binomial tree in H obeys the min-heap property: the key of a node is greater than or equal to the key of its parent. We say that each such tree is min- heap-ordered. . For any nonnegative integer k, there is at most one binomial tree in H whose root has degree k. The first property tells us that the root of a min-heap- ordered tree contains the smallest key in the tree. The second property implies that an n-node binomial heap H consists of at most [lag n] + 1 binomial tree. To see why, observe that the binary representation of n has [lag n] + 1 bits, say _([lag n]- , so that b_I AI ) . By property 1 of 4, therefore, binomial tree Bi appears in H if and only if bit bal = 1. Thus, binomial heap H contains at most[lag n] + 1 binomial trees.

Question 4 - Discuss the process of flow of Strainer's Algorithm and also its Question 5 - How do you formalize a greedy technique? Discuss the different steps one by one? Answer: Formalization of Greedy Technique Following are the steps to formalize the greedy technique: I) A set or list of give / candidate values from which choices are made, to reach a elution. For example, in the case of Minimum Number of Notes problem, the list of candidate values (in rupees) of notes is {1, 2, 5, 10, 20, 50, 100, 500, 1000}. Further, the number of notes of each denomination should be clearly mentioned.

Otherwise, it is assumed that each candidate value can be used as many times as required for the solution using greedy technique. G. Ft. Set of Given Values it) Set (rather multi-set) of considered and chosen values: This structure contains those candidate values, which are considered and chosen by the algorithm based on greedy technique to reach a solution. C.V.. Structure of Chosen Values If the amount to be collected is RSI. 289 then 100, 50, 20, iii) Set of Considered and Rejected Values: As the name suggests, this is the set of all those values, which are considered but rejected.

Let us call this set as REV: Set of considered and Rejected Values A candidate value may belong to both C.V. and REV. But, once a value is put in REV, then this value cannot be put any more in C.V.. For example, to make an amount of RSI. 289, once we have chosen two notes each of denomination 100, we have C.V.= {100, 100} At this stage, we have collected RSI. 200 out of the required RSI. 89. At this stage REV= {1000, 500}. So, we can chose a note of any denomination except those in REV, I. E. , except 1000 and 500. Hence we reject the choice of 100 third time and put 100 in REV, so that now REV= {1000, 500, 100}.

From this point onward, we cannot choose even denomination 100. Iv) A function say Solo that checks whether a solution is reached or not. However, the function does not check for the optimality of the obtained solution. In the case of Minimum Number of Notes problem, the function Solo finds the sum of all values in the multi-set C.V. and compares with the desired amount, say RSI. 89. For example, if at one stage C.V.= {100, 100} then sum of values in C.V. is 200 which does not equal 289, then the function Solo returns. 'Solution not reached'.

However, at a later stage, when C.V.= {100, 100, 50, 20, 10, 5, 2, 2}, then as the sum of values in C.V. equals the required amount, hence the function Solo returns the message of the form 'Solution reached'. It may be noted that the function only informs about a possible solution. However, solution provided through Solo may not be optimal. For instance in the Example above, when we reach {60, 10, 10}, then Solo returns 'Solution, reached'. However, as discussed earlier, the solution 80 = 60 + 10 + 10 using three notes is not optimal, because, another solution using only two notes, biz. 80=40+ 40, is still cheaper. V) Selection Function say Self finds out the most promising candidate value out of the values not yet rejected, I. E. , which are not in REV. In the case of Minimum Number of Notes problem, for collecting RSI. 289, at the The denomination 100. But, through function Solo, when it is found that by addition of 100 to the values already in C.V., the total value becomes 300 which exceeds 289, the value 100 is rejected and put in REV. Next, the function Self attempts the next lower denomination 50.

The value 50 when added to the sum of values in C.V. gives 250, which is less than 289. Hence, the value 50 is returned by the function Self. V') The Feasibility-Test Function, say Feb.. When a new value say v is chosen by the function Self, then the function Feb. checks whether the new set, obtained by adding v to the set C.v. already selected values, is a possible part of the final solution. Thus in the case of Minimum Number of Notes problem, if amount to be collected is RSI. 289 and at some stage, C.V.= {100, 100}, then the function Self returns 50.

At this stage, the function Feb. takes the control. It adds 50 to the sum of the values in C.V., and on finding that the sum 250 is less than the required value 289 informs the main/calling program that {100, 100, 50} can be a part of some final solution, and needs to be explored further. Vii) The Objective Function, say Bobs, gives the value of the solution. For example, in the case of the problem of collecting RSI. 289; as C.V.= {100, 100, 50, 20, 10, 5, 2, 2} is such that sum of values in C.V. equals the required value 289, the function Bobs returns the number of notes in C.V., I. E. , the number 8.

These functions upend upon the problem under consideration. The Greedy-structure outlined below takes the set XV of given values as input parameter and returns C.V., the set of chosen values. For developing any algorithm based on greedy technique. Question 6 - Briefly explain the Prism's algorithm. Prism's algorithm The algorithm due to Prim builds up a minimum spanning tree by adding edges to form a sequence of expanding substrate. The sequence of substrate is represented by the pair (VT, ET), where W and ET respectively represent the set of vertices and the set of edges of a substrate in the sequence.

Initially, the substrate, in the sequence, insists of Just a single vertex which is selected arbitrarily from the set V of vertices of the given graph. The substrate is built-up iteratively by adding an edge that has minimum weight among the remaining edges (I. E. , edge selected greedily) and, which at the same time, does not form a cycle with the earlier selected edges. We illustrate the Prism's algorithm through an example before giving a semi-formal definition of the algorithm. Example 1: Let us explain through the following example how Prime's algorithm finds a minimal spanning tree of a given graph.

Let us consider the following graph: Initially 3 1. 5 Figure - 1 he edges having a as one of its vertices, is chosen. In this case, the edge ABA with weight 1 is chosen out of the edges ABA, AC and ad of weights respectively 1, 5 and 2. Thus, after First iteration, we have the given graph with chosen edges in bold and VT and ET as follow: VT = (a, b) Figure- 2 In the next iteration, out of the edges, not chosen earlier and not making a cycle with earlier chosen edge and having either a or b as one of its vertices, the edge with minimum weight is chosen. In this case the vertex b does not have any edge originating out of it.

In such cases, if required, weight of a non-existent edge may be oaken as Thus choice is restricted to two edges biz. , ad and AC respectively of weights 2 and 5. Hence, in the next iteration the edge ad is chosen. Hence, after second iteration, we have the given graph with chosen edges and VT and ET as follows: = (a, b, d) Figure- 3 earlier chosen edges and having either a, b or d as one of its vertices, the edge with minimum weight is chosen. Thus choice is restricted to edges AC, dc and De with weights respectively 5, 3, 1. 5. The edge De with weight 1. 5 is selected.

Hence, after third iteration we have the given graph with chosen edges and VT and ET as follows: VT = (a, b, d, e) 5 2 earlier chosen edge and having either a, b, d or e as one of its vertices, the edge with minimum weight is chosen. Thus, choice is restricted to edges dc and AC with weights respectively 3 and 5. Hence the edge dc with weight 3 is chosen. Thus, after fourth iteration, we have the given graph with chosen edges and W and ET as follows: VT = At this stage, it can be easily seen that each of the vertices, is on some chosen edge and the chosen edges form a tree.