EC504-Homework 3 Solved

Reading Assignment on GitHub – In CRLS add to past assignments Sorting  Data Structure (Chapters 6, 7,8,9,10) , new material on Trees.pdf (12, 13) and TreeMath B.pdf (Appendix B .5) and Huffman Coding 16.3

1. Determine whether the following statements are true or false, and explain briefly why.

(a)     If doubling the size ( N → 2N ) causes the execute time T(N) of an algorithm to increase by a factor of 4, then T(N) ∈ O(4N).

(b)    The height of a binary tree is the maximum number of edges from the root to any leaf path. The maximum number of nodes in a binary tree of height h is 2h+1 − 1.

(c)     In a binary search tree with no repeated keys, deleting the node with key x, followed by deleting the node with key y, will result in the same search tree as deleting the node with key y, then deleting the node with key x.

(d)    Inserting numbers 1, . . . , n into a binary min-heap in that order will take O(n) time.

(e)     The second smallest element in a binary min-heap with all elements with distinct values will always be a child of the root.

2. This exercise is to learn binary search tree operations

(a)     Draw the sequence of binary search trees which results from inserting the following values in left-to-right order, assuming no balancing. 15, 10, 31, 25, 34, 56, 78, 12, 14, 13

(b)    Starting from the tree at the end of the previous part, draw the sequence that results from deleting the following nodes in left-to-right order: 15, 31, 12, 14.

(c)     After deleting them draw the sequence of reinserting left-to-right in reverse order: 14, 12, 31, 15. in order into the tree and comment on the result?

3.    (20 pts) Reading CRLS Chapter 6 and do the written

(a)     Exercises: 6.1-3, 6.1-4, 6.1-6, and 6.3-3

(Note chapter 6 gives background to the coding exercise to use an array for a Max Heap.

Also there is of course a nice Wikipedia article to look at https://en.wikipedia.org/wiki/Heapsort.)

(b)    Exercises: 12.3-2, 12.3-3, 12.3-4, B.5-4

(Note that the degree of in an undirected graph (or tree) is the number links incident on the node. A leaf is a node with degree 1.)

4. Determine whether the following statements are true or false, and explain briefly why.

(a)     A heapsort algorithm for a given list first forms a max-heap with the elements in that list, then extracts the elements of the heap one by one from the top. This algorithm will sort a list of n elements in time of O(log(n)).

(b)    A connected undirected acyclic graph with N nodes and N-1 edges is a tree.

(c)     A binary heap of n elements is a full binary tree for all possible values of n.

(d)    The following tree is a valid min-heap.

4

                                                    /       \

                                                 10        5

/ \

12    14

(e)     The following tree can appear in a binomial min-heap. .

4

                                                    /       \

                                                 10        5

/ \

12    14

(f)      Given a array of positive integers a[i], maximizing Pi ∗ a[i] over permutations of the array requires sorting a[i] in assigning order.

5. Given the following list of elements,

35,22,11,98,55,66,77,80,85,90,95

(a)     Draw the sequence of binary min-heaps which results from inserting the following values in the order in which they appear into an empty heap.

(b)    Compare this answer with inserting them into the BST tree. (c) Compare this answer with inserting them into the AVL tree.

6. You are interested in compression. Given a file with characters, you want to find the binary code which satisfies the prefix property (no conflicts) and which minimizes the number of bits required. As an example, consider an alphabet with 8 symbols, with relative weights (frequency) of appearance in an average text file give below:

                                          alphabet:|    A    |    L    |    G    |    O    |    R    |    I    |    T    |    H    |

                                        weights:|   68    |    20     |    5    |    30    |   18    |   15    |    19    | 12    |

(a)     Determine the Huffman code by constructing a tree with minimum external path length: P8i=1 widi. (Arrange tree with smaller weights to the left.)

(b)    Identity the code for each letter and list the number of bits for each letter and compute the average number of bits per symbole in this code. Is it less than 3? (You can leave the answer as a fraction since getting the decimal value is difficult without a calculator.)

(c)     Give an example of weights for these 8 symbols that would saturate 3 bits per letter. What would the Huffman tree look like? Is a Huffman code tree always a full tree?

7.    (15 pts) Given the following list of N = 10 elements.

                                                                       28   14    7    4    6   30    36   33   10   40

(a)     Insert them sequentially into a BST (Binary Search Tree). Compute the total height TH(N) and the total depth TD(N), where H is the height of the root. (Note the height of a node is the longest path length to a leaf whereas its depth is its unique distance from the root.)

(b)    Find H, TH(N), TD(N) and check the sum rule:

TH(N) + TD(N) ≥ HN
(c)     Insert them sequentially into an empty AVL tree, restoring the AVL property after each insertion. Show the AVL tree which results after each insertion and name the type of rotation (RR or LL zig-zig or versus RL or LR zig-zag).

(d)    Has the final AVL tree decreased the total height TH(N) and the total depth TD(N)?

What are the new values? What is the new value of TH(N) + TD(N)?

Coding Exercise
8. (0pts) Implement a Max Heap for n elements as and array int HeapArray[n+1]; of n + 1 setting elements by placing the integers setting HeapArray[0] = n and copying the elements putting the elements in sequence into HeapArray[i], for i = 1,2,..., n (May choose to have an longer array with extra space and a save a value heapSize to tell how many are in the heap. This is a useful index in any case!

(a) Provide the in HW4_codes/heap.cpp to enable:

(1)        Insert random sequence to Heap array

(2)        Bottom up Heapify for Max Heap

(3)        Delete any key and restore Max Heap

(4)        Insert new key and restore Max Heap

(4) Sort in place and print out array
Put final code with Makefile in /projectnb/alg504/username/HW4 (b) Analize the behavior of this code with the following plots:

(1)            Plot timing for range of sise n = 8, 16, 32,....2^20

(2)            Histogram the performance over random permutation of UnsortedList100.txt

(3)            Combine these two part to define the average for n = 8, 16, 32,....2^20 and fit T(n) = a + b n Log[n] + c n*n
Place these figures in /projectnb/alg504/username/HW4 as well.