I need help with 4 Advanced Computer Science problems

Get Help With a similar task to - I need help with 4 Advanced Computer Science problems

Additional Instructions:

CS 253 Midterm Spring 2020 Due on Canvas as a PDF at 3:45PM EDT (UTC -4), March 26. 1. (a) Interpret the array [5, 12, 2, 3, 11, 6, 4, 10, 7, 1, 8, 9] as a complete binary tree and use the bottom-up heap construction (heapify) to turn it into a min-oriented heap. Show the result after applying the construction to each level in the tree. (b) We showed in class that heapify runs in time O(n), where n is the number of elements. Consider the following alternate approach: heapulate(a[]): n = a.length for i in 0,1,...,n-1: upheap(a, i) where upheap() takes an array, treats it as a complete binary tree, and bubbles up the key at position i. What is the worst-case runtime of this algorithm, and what is an example of an array that achieves that worst-case bound? 2. Consider the following binary tree with external nodes omitted: (a) Label the nodes with the keys 10, 20, . . . , 80 to make a binary search tree. (b) Give a red-black coloring of this tree and use your coloring to produce an equivalent (2, 4)-tree. (c) Now interpret the tree as an AVL tree and show the effect of inserting the key 55, rebalancing if necessary. 3. (a) Create a Huffman code for the following string (whitespace inserted for clarity): AAA BB CCCCC CCCCC DD EEE (b) How many bits does your code use to encode the above string? (c) Huffman codes are always optimal prefix codes, and there are many different ways one can build a Huffman code from the same set of character frequencies (e.g. by swapping the left and right subtrees at any iteration). Give an example of an optimal prefix code for this text that is not a Huffman code, i.e., that cannot be generated using the Huffman algorithm (Hint: in any Huffman code, what is the relationship between the two characters with the lowest frequencies?). 1 CS 253 Midterm Spring 2020 4. Let P = p1, p2, . . . , pn be a sorted list of real numbers (e.g. each pi is of double type). A unit interval U is the interval [x, x + 1] of real numbers for some real number x. A unit interval cover of P is a collection of k unit intervals U1, U2, . . . , Uk, where each pi is inside of some unit interval Uj. The following is a collection of five points covered by three intervals: The goal of this problem is to find the smallest unit interval cover of a set of points P , in terms of the number of intervals. The above solution is optimal because one cannot cover all those points using just two intervals. (a) Give an example of a set of points P where the following greedy algorithm fails to be optimal: i. Find a unit interval U ′ which covers the most number of points. ii. Repeat this process on the remaining points not covered by U ′. (b) Devise an optimal greedy algorithm for this problem (Hint: some unit interval needs to cover the leftmost point, so what’s the greedy way of covering that point?). (c) Prove the correctness of your algorithm, showing that it satisfies the greedy choice property. 2

Related Questions