# I need help with 4 Advanced Computer Science problems

The assignment needs to be fully done and every problems justified.

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

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

Similar orders to I need help with 4 Advanced Computer Science problems
17
Views
0
Nested imbalanced design of expriment using Box-Adjusted wald-type test
I need to provide statistical analysis of a nested design non-balanced design of experiment. I am hoping to have the implementation in either R, SPSS, or both. I will need the answers to be provided as shown in the attached file (Project.docx), and also wo...
32
Views
0
CMPT 200 Coding Homework
Write a class called Fraction that can store a rational number (reminder: those numbers that can be expressed in the form a/b, where a and b are integers are rational numbers). For example, a variable with a value of Â½ would be created using oneHalf ...
15
Views
0
Artificial Inteligence System Technique
This is a Master Degree course and I have attached example questions, there are 5 questions and only 3 need to be answered. We will get the actual questions on the day of the exam and they need to be completed within 2 hours, which means the expert has to ...
18
Views
0