Description
1. (10 pts) 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. (15 pts) 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.)
1
(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. (15 pts) 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. (15 pts) 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. (15 pts) 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:
2
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:
P8
i=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:
3
(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.
4
