MC80

|
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
 4 views
of 13

Please download to get full document.

View again

Description
1. Describe the following:  Fibonacci Heaps  Binomial Heaps 3  Explain the concept of binary search and also write the algorithm for binary search. Binary Search: Binary Search algorithm searches a given value or element in an already sorted array by repeatedly dividing the search interval in half. It first compares the value to be searched with the item in the middle of the array. If there is a match, then search is successful and we can return the required result immediately. But if the
Share
Tags
Transcript
  1. Describe the following:  FibonacciHeaps  BinomialHeaps  3  Explain the concept of binary search and also write the algorithm forbinary search.  Binary Search: Binary Search algorithm searches a given value or element in an already sorted array byrepeatedly dividing the search interval in half. It first compares the value to be searched withthe item in the middle of the array. If there is a match, then search is successful and we canreturn the required result immediately. But if the value does not match with the item in middleof the array, then it finds whether the given value is less than or greater than the value in themiddle of array. If the given value is less than the middle value, then the value of the itemsought must lie in the lower half of the array. However, if the given value is greater than theitem sought, must lie in the upper half of the array. So we repeat the procedure on the loweror upper half of the array according as the given value is respectively less than or greater thanthe middle value. The following C++ function gives the Binary Search Algorithm . Ex :int Binary Search (int * A, int low, int high, int value){int mid:While (low < high){mid = (low + high) / 2;If (value = = A [mid])return mid;else if (value < A [mid])high = mid – 1;else low = mid + 1;}return – 1;} Explanation of the Binary Search Algorithm :It takes as parameter the array A, in which the value is to be searched. It also takes the lowerand upper bounds of the array as parameters viz., low and high respectively. At each step of the integration of the while loop, the algorithm reduces the number of the elements of thearray to be searched by half. If the value is found then its index is returned. However, if thevalue is not found by the algorithm, then the loop terminates if the value of the low exceedsthe value of high, there will be no more items to be searched and hence the function returns anegative value to indicate that item is not found.  4  Prove that “ If n ≥ 1, then for any n-key,B-tree T of height h andminimum degree t ≥ 2,   h ≤ log t  ( n+ 12 ) . In computer science, a B-tree is a tree data structure that keeps data sorted and allowssearches, sequential access, insertions, and deletions in logarithmic amortized time. The B-treeis a generalization of a binary search tree in that more than two paths diverge from a singlenode. Unlike self-balancing binary search trees, the B-tree is optimized for systems that readand write large blocks of data. It is commonly used in databases and filesystems.  Proof  :If a B – tree has height h, the root contains at least one key and all other nodes contain atleast t-1 keys. Thus, there are at least 2 nodes at depth 1, at least 2t nodes at depth 2, atleast 2t raise to 2 nodes at depth 3, and so on, until at depth h there are at least 2t raise to h– 1 nodes.n >= 1 + (t-1) Summation of 2t raise to i-1 from i=1 to h= 1 + 2(t-1) (t raise to h - 1 / t-1)= 2t raise to h - 1.By simple algebra, we get t raise to h <= (n+1) / 2 .Taking base - t logarithms of both sidesproves the theorem. Therefore, theorem is proved.  5. Explain briefly the concept of breadth-First search(BFS) Breadth first search as the name suggests first discovers all vertices adjacent to a given vertexbefore moving to the vertices far ahead in the search graph. If G(V, E) is a graph having vertexset V and edge set E and a particular source vertex s, breadth first search find or discoversevery vertex that is reachable from s. First it discovers every vertex adjacent to s, thensystematically for each of those vertices find all the vertices adjacent to them and so on. Indoing so, it computes the distance and the shortest path in terms of fewest numbers of edgesfrom the source node s to each of the reachable vertex. Breadth-first Search also produces abreadth-first treewith root vertex the process of searching or traversing the graph.For recording the status of each vertex, whether it is still unknown, whether it has beendiscovered (or found) and whether all of its adjacent vertices have also been discovered. Thevertices are termed as unknown, discovered and visited respectively. So if (u, v) є E and uis visited then v will be either discovered or visited i.e., either v has just been discovered orvertices adjacent to v have also been found or visited.As breadth first search forms a breadth first tree, so if in the edge (u, v) vertex v is discoveredin adjacency list of an already discovered vertex u then we say that u is the parent orpredecessor vertex of V. Each vertex is discovered once only.The data structure we use in this algorithm is a queue to hold vertices. In this algorithm weassume that the graph is represented using adjacency list representation. front [u] us used torepresent the element at the front of the queue. Empty() procedure returns true if queue isempty otherwise it returns false. Queue is represented as Q. Procedure enqueue() anddequeue() are used to insert and delete an element from the queue respectively. The datastructure Status[ ] is used to store the status of each vertex as unknown or discovered orvisite. Algorithm of Breadth First Search 1. for each vertex u є V – {s} 2. status[u] = unknown 3. status[s] = discovered 4. enqueue (Q, s) 5. while (empty[Q]! = false) 6. u = front[Q] 7. for each vertex v є Adjacent to u 8. if status[v] = unknown 9. status[v] = discovered 10. parent (v) = u 11. end for 12. enqueue (Q, v); 13. dequeue (Q) 14. status[u] = visited 15. print “u is visited”  16. end while
Similar documents
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks