+ | D Page view | A Read aloud | Draw 8 8 3x3 1. a) Illustrate the Heap Extract Max operation on the following heap: Heap = {45, 39,27, 15, 36, 24, 21, 12,0, 18,6,3} b) Illustrate the operation of Insertion Sort on the follow array: A = {25, 10, 20, 30,5,15} c) Draw a separate figure to demonstrate each of the following relations: f(n) = (g(n)) ii. f(n) = 0(g(n)) iii. f(n) = (g(n)) 2. a) Array = {10,40,50,100,160,170,180} i. Build a Binary Search Tree using the above mentioned array. ii. Build an AVL Tree using the above mentioned array. b) Draw the Adjacency-list and Adjacency Matrix representations for the following graph. 2 5+10 5+5 5 10 5+10 4 5 c) What is the problem of finding Longest Common Subsequence (LCS) between two strings using brute-force approach? 3. a) Show that Merge Sort requires 0(nlog(n)) auxiliary space to sort n numbers which can further be optimized to (n). b) How does Huffman codes increase the efficiency of data compression? The following table an alphabet consisting of 6 letters. Frequency of each letter is provided in a separate column. Demonstrate the operations of Huffman coding for the alphabet. Letter Frequency i 48 k 39 h 15 1 27 135 a S 36