Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
EC 504 Midterm Pratice
Instructions: Put your name and BU ID on the first page. This exam is closed book and no notes – except for 2 pages of personal notes to be passed in the end. No use of laptops or internet. You have one hour and fifty minutes. Do the easy ones first. 1. (20 pts) Answer True or False to each of the questions below. Each question is worth 2 points. Answer true only if it is true as stated, with no additional assumptions. No explanation is needed, but any explanation is likely to earn partial credit, and no explanation will not earn any credit if the answer is wrong. (a) N2e−1/ ln(N) ∈ Θ(Neln(N)). Solution: False: N2e−1/ ln(N) ∈ Θ(N2), since 1/ln(N) → 0 it does not change the Θ(N2) factor. (b) If fi(n) ∈ O(n2), then ∑n i=1 fi(n) ∈ O(n3) Solution: True. There are n terms, each of which is O(n2), so you can bound this by a constant times n3, making it O(n3). (c) The following tree is an AVL binary search tree – explain. 11 / \ 9 23 / \ / \ 8 12 16 50 / \ / \ 1 10 10 80 Solution: False. The key 12 must be the right of 11 and the second 10 to the left of 11. (d) The second smallest element in a binary min-heap with all elements with distinct values will always be a child of the root. Solution: True. The children of the root must be smaller than any of their children. (e) The set Θ(f(n)) is identical to the set O(f(n))∩Ω(f(n)) (Note: ∩ means intersection of two sets.) Solution: False. It is identical to Θ((f(n)) ∩ Ω(f(n)) but not the larger set O(f(n)) that include slower functions. (e.g. like the relation ≤). (f) It is possible to formulate Quick Sort to be worst case O(N logN) including the cost of picking a suitable pivot. Solution: True. You pick the pivot to be them medium using the ()(N) algorirthm that sorts N/5 columns recursive find the medium for N/5 in the middle row. 1 (g) Consider the array [2, 20, 3, 21, 90, 4,23, 22]. This array has elements in order of a min-heap. Solution: True. All path for the root are in decreasing order. 2 / \ 20 3 / \ / \ 21 90 4 23 / 22 (h) A min-Heap (or priority queue) is a null tree or a root node with a minimum value plus a left and a right min-Heap subtrees. Solution: True. This is the correct recursive defintion of a min-Heap. (i) The maximum subsequence sum algorithm finds i and j that maximize ∑j k=i a[k] for an array a[N ] of positive and negative integers. The fastest one is a recursive algorithm with complexity Θ(N logN). Solution: False. As I demonstrated in class, qx the fastest one, which is a sort of investors scan, is Θ(N) – suprising! (j) NN ∈ O( eln(N !) ) Solution: True. The Sterling’s approxmation of the factorial: N ! = √ 2piNNNe−M(1+ O(1/N)) shows that is goes slower than N ! so N ! = O(NN) but not the reverse. 2. (10 pts) Consider the binary tree illustrated below. * / \ + - / \ / \ * 8 - 10 / \ / \ + 2 8 * / \ / \ 6 7 2 3 (a) List the node values in the order in which they would be found in an in-order traversal. 2 (b) List nodes in pre-order. (c) List the nodes in post=order. (d) Which order is uses on stack to do the arithmetic? . (HINT the stack order is like depth first search on this tree!) Evaluate the arithmetic using stack Solution: In-order 6 + 7 ∗ 2 + 8 ∗ 8 − 2 ∗ 3 − 10 (1) pre-order ∗ + ∗ + 6 7 2 8 − − 8 ∗ 2 3 10 (2) post-order 6 7 + 2 ∗ 8 + 8 2 3 ∗ − − 10 − ∗ (3) Evaluation of arithmatic. Easiest way is bottom up on the tree (e.g. in-order) to get Result is −272. The stack has two solutions. You get −272 if you remeber that we pushed left and then right so for a minus sign is pop y pop x =⇒ x− y. You could assume pop x pop y - =⇒ y − x which gives 408. I accept this rule altough it is inconsistent with the definition of post-order. This could be corrected by exchangeing left and righ in post order. Hard becuase Minus sign hard because ther are not symmetric. 3 3. (20 pts) Consider the following min-heap. 1 / \ 10 2 / \ / \ 11 12 17 3 / \ / \ / \ / \ 15 18 201 13 155 20 4 5 / \ / 17 16 21 (a) Show the min-heap which results after inserting the element 7 in the heap. (Indicate the sequence of steps with arrows.) Then in this new heap show the steps required to delete element 1 and then delete 11. Draw the final min-heap. (b) Re-arrange the original min-heap (repeated below) into a max-heap by a “bottom up” O(N) algorithm. Describe the steps level by level. 1 / \ 10 2 / \ / \ 11 12 17 3 / \ / \ / \ / \ 15 18 201 13 155 20 4 5 / \ / 17 16 21 Solution: Start with next to bottom row of 8 1 / \ 10 2 / \ / \ 11 12 17 3 / \ / \ / \ / \ 17 21 201 13 155 20 4 5 <---- Start with row of 8 / \ / 15 16 18 4 1/ \ 10 2 / \ / \ 21 201 155 5 <---- Next row of 4 / \ / \ / \ / \ 17 18 12 13 17 20 4 3 / \ / 15 16 11 1 / \ 201 155 <---- Next row of 2 / \ / \ 21 13 20 5 / \ / \ / \ / \ 17 18 12 10 17 2 4 3 / \ / 15 16 11 201 <---- Final Root node / \ 21 155 / \ / \ 18 13 20 5 / \ / \ / \ / \ 17 11 12 10 17 2 4 3 / \ / 15 16 1 (c) Using this example for a min-heap with the size N = 18 and a[0] = N. Describe in a few word an an Θ(N logN) algorithm to sort in place the array elements a[1], a[2], · · · , a[N ] in descending order (i.e. a[1] > a[2] > · · · > a[N ] ) Solution: a[0] store the size of heap starting with a[0] = N The algorithm is iterative. You delete the min in a[1] restoring the heap and copying a[a[0]]] = a[1] reducing the size by by 1 (a[0] = a[0] − 1) until the heap is empty (a[0] = 0) Now the array a[1], a[2], ..a[N ] is sorted array in descending order. Restorig the heap each time is (log(N) so the alogritym is O(NlogN) (d) Solve the recursion relation for the Heap, T (H) = 2T (H − 1) + c0H to show that “bottom up” scales like T (H) = Ω(N) (HINT: Use N ' 2H) Solution: 5 Substitute the guess in the equation that is suggested: T (H) = c 2H c 2H ' c 2 2H−1 + c0H = c 2H + c0H ' c 2H (4) So the leading behavior is T [H] = c 2H ∈ Ω(H). 6 4. (20 pts) This problem is to construct step by step BST and AVL trees given the following list of N = 12 elements. 1 2 12 7 3 6 30 36 37 2 40 51 (a) Insert them sequentially into a BST (Binary Search Tree). Solution: The BST (depth of a node is the numbe of hop form the root. height is the maximun number of hops to the deapest node. 1 h=7, d = 0 \ 2 h=6, d = 1 / \ h=0, d = 2 2 12 h=5, d = 2 / \ h=2, d = 3 7 30 h=4, d = 3 / \ h= 1,d = 4 3 36 h=3, d = 4 \ \ h=0, d = 5 6 37 h=2, d = 5 \ 40 h=1, d = 6 \ 51 h=0, d = 7 (b) 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). Solution: Final AVL form; See next page for sequence of steps! 30 h = 3 d = 0 / \ 3 36 h = 2 d = 1 / \ / \ 2 7 3 48 h = 1 d = 2 (excep 3 is h =0) / \ \ / \ 1 2 6 37 54 h = 0 d = 3 (excep 3 is h =0) (c) Give the total height TH(N) and the total depth TD(N) for both the resulting BST and AVL. (d) Compare the sum TH(N)+TD(N) for the BST and AVL. For each compare these values with HN where H is the height of each tree. 7 Solution: BST: TH(N) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 1 + 2 = 31 and TD(N) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 2 + 3 + 4 + 5 = 42 So TH(N) + TD(N) = 73 < HN = 7 ∗ 12 = 84 AVL: TH(N = 3 + 2 ∗ 2 + 3 ∗ 1 = 10 and TD(N) = 2 ∗ 1 + 4 ∗ 2 + 5 ∗ 3 = 25 So‘ TH(N) + TD(N) = 35 < HN = 3 ∗ 12 = 36 Note a perfect tree of N = 15 and height H = 3 has TH(N) = 3 + 2 ∗ 2 + 4 ∗ 1 = 11 and TD(N) = 2 ∗ 1 + 4 ∗ 2 + 8 ∗ 3 = 34 so TH(N) + TD(N) = 45 = HN = 3 ∗ 15 = 45 I thought this is the only one that saturates the upper bound but a counter example is to remove one leaf NH → NH −H and that leaf remove d = H form the sum of TD(N)! 8 5. (10 POINTS) Consider the following recursion relation. T (N) = 3T (N/2) +Nk (a) Substitute T (N) = c0N γ into the homogeneous equation (i.e. dropping Nk) and de- termine γ and for what values of k does the exact solution satisfy T (N) = Θ(Nγ). Solution: The homogeneous equation (i.e. drop the last term has solution by substi- tution c0 N γ = c0 3 (N/2) γ =⇒ 1 = 3/2γ or γ = log(3)/ log(2) (5) Base 2 is nice since log2(2) = 1 or γ = log2(3) This is gives a leading solution T (N) = Θ(Nγ) if k < γ (b) Now assume that k = γ and find the exact solution in the form: T (N) = c0N γ + c1N γ log2(N). (HINT: First show that c1 = 1. Then Determine c0 in terms of T (1) by setting N = 1. ) Solution: Note a homogeneous solution never determines the multiplicative const c0. For this we must find a fulls solution. The substution gives c0 N γ + c1N γ log2(N) = c0 3 (N/2) γ + c13(N/2) γ log2(N/2) +N γ = c0 3 (N/2) γ + c1(N) γ[log2(N)− log2(2)] +Nγ (6) Obviously the first (homegeneous term) still cancels. We could have ignore this piece for now. But to cancel the additive term we need to use both 3/2γ = 1 and again log2(2) = 1, to get c1 = 1. The setting N = 1 we finally fix c0 by T (1) = c0 1 γ + c11 γ log2(1) = c0. Actually you can do this step first if you prefer. 9 6. (20 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 1 give below: alphabet:| V | A | M | P | I | R | E | S | weights:| 4 | 40 | 16 | 7 | 30 | 18 | 75 | 8 | (a) Determine the Huffman code by constructing a tree with minimum external path length: ∑8 i=1widi. (Arrange tree with smaller weights to the left.) Solution: V P S M R I A E 4 7 8 16 18 30 40 75 27 40 11 1 Minimize ext length = ∑i wi di 4 V 34 74 16 M 198 49 19 18 R 75 E 7 P 8 S 30A 1 1 1 1 1 1 0 0 0 0 0 Sort Wi = 0 123 I 0 (b) Identity the code for each letter and list the number of bits for each letter and compute the average number of bits per symbol 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.) Solution: (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? Solution: 1vampire: Origin mid 18th cent: from French, from Hungarian vampir, perhaps form Turkish uber “witch”. In European folklore, a monster with long pointed canine teeth! 10 RESULTING CODE: AVERAGE BITS/CHAR =508/198 = 2.565 Letter Weight Code Bits Count ! E 75 0 1 75 ! A 40 101 3 120 ! I 30 111 3 90 ! M 16 1000 4 64 ! R 18 1001 4 72 ! S 8 1100 4 32 ! V 4 11010 5 20 ! P 67 11011 5 35 Total: 198 508 28 External length = ∑i wi di It is perfect binary tree. One can have each have weight 10 for example ( 80 ) / \ (40) (40) / \ / \ (20) (20) (20) (20) / \ / \ / \ / \ V A M P I R E S Actually the weight don’t have to exactly equal. Try it with weights: 100, 101, 102, 103, 104, 105, 106, 107 It is still perfect tree1 11 7. (10 POINTS EXTRA CREDIT) Given an array of N-distinct positive integers a[N ] and a second array of N-distinct positive integers b[N ] to construct the sum: N−1∑ i=0 a[i] ∗ b[i] (7) (a) Assume that a[k] is sorted in ascending order. Give an O(N logN) algorithm that maximizing the sum S by permuting the values of b[k]. Solution: To maximize the sum you sort the array b[k] into ascending order by any Θ(NlogN) algorithm such as merg sort. This is an example of every pair {i, j} maximizing the scalar product a[i]b[i] + a[j]b[j] since a[i] < a[j] and b[i] < b[j]. Any exchang of i, j reduces this contribution the sum. (b) Given the result of part (a) give an algorithm that minimizes S in O(N). Solution: To minimize the result of part (a) one just reverse the order of b[k] with N/2 swaps of b[i] and b[N − 1− i] for i = 0, 1, · · ·N/2 (c) If you are allowed to permute independently both a[k] and b[k] how many different solutions will maximize S? Solution: There are N ! solution because give maximun Smax = N−1∑ k=0 a[k] ∗ b[k] (8) as describe in part (a) is unchange by any simultaineous permutation of k (pi(k) Smax = N−1∑ k=0 a[pi(k)] ∗ b[pi(k)] (9)