Unit 3
Advance Data Structure:- Binary Search Tree, AVL Tree, Red-Black Tree, B-Tree, B+ Tree, Binomial Tree, Binomial Heap, Fibonacci Heap, Trie, Skip List.
University Questions are from
(AKTU, IPU, DTU, MDU, LPU, VIT, SRM, Amity, PU, JMI and many more…)
Design & Analysis of Algorithm
Assignment 1
Q – Suppose R that the key (1, 2, …,n) are inserted into an empty B-Tree with minimum degree 2. How many nodes does the final B-Tree have? (in terms of n)
Q – Argue that in every n-node binary search tree, there are exactly n-1 possible rotations.
Q – Describe the properties of red black tree. Show that a red black tree with n internal nodes has height at most 2lg(n+1).
Q – Write down the properties of binomial tree?
Q – Explain the algorithm to delete a given element in a binomial heap. Give an example for the same.
Design & Analysis of Algorithm
Assignment 2
Q – Difference between Complete binary tree and Binary tree?
Q – Discuss various properties of binomial tree?
Q – What are the various differences in Binomial heap and Fibonacci Heap? Explain.
Q – What are the advantages of Red Black Tree over Binary Search Tree? Write algorithms to insert a key in a red black tree. Insert the following sequence of information in an empty red black tree 1, 2, 3, 4, 5, 5.
Q – Using minimum degree ‘t’ as 3, insert following sequence of integers 10, 25, 20,35, 30, 55 40, 45, 50, 55, 60, 75, 70, 65, 80, 85 and 90 in an initially empty B-tree. Give the number of nodes splitting operations that take place.
Design & Analysis of Algorithm
Assignment 3
Q – Explain the process of augmenting a data structure with an example.
Q – Insert the following keys in a 2-3-4 B tree.
40, 35, 22, 90,12, 45, 58, 78, 67, 60 and then delete key 35 and 22 one after other.
Q – Prove that the maximum degree of n node in a binomial tree is log2n.
Q – Discuss the complexity of Max-Heapify and Build-Max Heap procedures.
Q – Explain Skip list in brief and its operation.
Design & Analysis of Algorithm
Assignment 4
Q – Suppose that x is a node in a Binomial Tree within a binomial heap, and assume that siblings[x] NIL. If x is not a root, how does degree (siblings(x)) compare to degree [x]. How about if x is a root.
Q – Write an algorithm HEAP-DELETE (A, i) which deletes the item in node i from heap A.
Q – What do you understand by amortized analysis? What are different methods for it? Explain with an example.
Q – What is a disjoint set data structure? How running times of disjoint set data structures is analyzed?
Q – Show the results of inserting the keys:
F, S, Q, K, C, L, H, T, V, W, M, R, N in order into an empty B-tree with minimum degree 2.
Design & Analysis of Algorithm
Assignment 5
Q – Write pseudo-code. Find set(x) for disjoint – set data structure which returns a pointer to the representative of the set containing x.
Q – Write pseudo-code for deleting a node in a Fibonacci heap.
Q – How B-Tree differs with other tree structures. Insert the following information F, S, Q, K, C, L, V, W, M, R, N, P, A, D, Z, E into an empty B-Tree with degree t = 2.
Q – Insert the following information F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E, G, I into an empty B-tree with degree t = 3.
Q – Explain Red Black tree with suitable example.
Design & Analysis of Algorithm
Assignment 6
Q – Prove that the maximum degree of any node in an n-binomial tree is log n.
Q – Explain insertion in Red Black Tree. Show steps for inserting 9, 8, 7, 6, 5, 4, 3, 2 & 1 into RB Tree.
Q – Prove that if n ≥ 1, then for any key B-tree of height h and minimum degree t ≥ 2, h ≤ logt((n+1)/2).
Q – Write the characteristics of B-Tree of order m. Create B-Tree of order 5 from the following lists of data items:
20, 30, 35, 85, 10, 55, 60, 25, 5, 65, 70, 75, 15, 40, 50, 80, 45.
Q – What is Fibonacci heap? Discuss the applications of Fibonacci heaps.
Design & Analysis of Algorithm
Assignment 7
Q – Write an algorithm for inserting a key into a B-tree in a single pass down the tree.
Q – Insert the nodes 15, 13, 12, 16, 19, 23, 5, 8 in empty Red Black tree and delete in reverse order of insertion.
Q – Show that the maximum degree D(n) of any node in an n-node Fibonacci Heap is O(lgn).
Q – How B-Tree differs with other tree structures. Insert the following information F, S, Q, K, C, L, V, W, M, R, N, P, A, D, Z, E into an empty B-Tree with degree t = 2.
Q – Explain Tries and Skip list in brief and its operation.
Design & Analysis of Algorithm
Assignment 8
Q – Insert the elements 8, 20, 11, 14, 9, 4, 12 in a red black tree and delete 12, 4, 9, 14 respectively.
Q – Consider T is a B-tree of order m and height h. Let d=m/2 and let n be the number of elements in T. Then show that:
Logm(n+1) ≤ h ≤ logd((n+1)/2) + 1
Q – What is a binomial heap? Describe the union of binomial heap. Also find the minimum key.
Q – Explain and write an algorithm for union of two binomial heaps. Also discuss the time complexity for the same.
Q – Describe the properties of red black tree. Show that a red black tree with n internal nodes has height at most 2lg(n+1).
Â
Design & Analysis of Algorithm
Assignment 9
Q – Describe the properties of red black tree. Show that a red black tree with n internal nodes has height at most 2lg(n+1).
Q – Insert the nodes 15, 13, 12, 16, 19, 23, 5, 8 in empty Red Black tree and delete in reverse order of insertion.
Q – Write short notes in the following
(i) B-trees
(ii) Fibonacci heap
Q – Discuss various properties of binomial tree and binomial heap?
Q – Insert the following information F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E, G, I into an empty B-tree with degree t = 3.
Design & Analysis of Algorithm
Assignment 10
Q – Write about linked list representation of disjoint sets.
Q – Prove that the maximum degree of any node in an n-binomial tree is log n.
Q – Show that if only the mergeable operations are supported, the maximum degree D(n) in an n-node Fibonacci heap is at most [log n].
Q – Show the results of inserting the keys:
F, S, Q, K, C, L, H, T, V, W, M, R, N in order into an empty B-tree with minimum degree 2.
Q – Describe the properties of red black tree. Show that a red black tree with n internal nodes has height at most 2lg(n+1).