CS 344 - Sections 1,2,3 Homework 3.

CS 344 - Sections 1,2,3 - Fall 2018 Homework 3 100 points total plus extra credit
1 Problem 1 (15 points)
For each part below, say whether the statement is true or false. If true, give a brief (one or two sentences) explanation; if false, give a counterexample. • Part 1 (3 points) The minimum element of a max-heap is always a leaf • Part 2 (3 points) The second smallest element of a max-heap is always a leaf • Part 3 (4 points) The second and third largest elements of a max-heap are always the two children of the root • Part 4 (5 points) The sum of the heights of all nodes in an n-node heap is Θ(n).
2 Problem 2 (20 points total)
no need to show your work on this problem: just draw the final heap Consider the array A = 3,7,15,4,25,1,20,8. • Part 1 (5 points): What is the tree corresponding to this array? (Note: it is not a max-heap) • Part 2: (5 points) What is the tree that results from calling BuildMax-Heap(A)? • Part 3: (5 point) What is the result of calling Max-Heap-Insert(A,17) on the max-heap that results from part 2? • Part 4: (5 points) What is the result of calling Delete-Max(A) on the heap that results from part 3?
1
3 Problem 3 (25 points)
Say there are n sorted arrays A1,A2,...,An, each with n numbers (so n2 numbers between all of them.) Write pseudocode that uses the heap data structure to find the n smallest numbers between all the arrays in time O(nlog(n)). You must make it clear why the run-time is O(nlog(n)). REMINDER: Heaps are now in our virtual library. For this problem, you can use a min-heap or a max-heap without explaining how the heap works.
4 Problem 4 (20 points)
For both parts below, make sure to show your work • Part 1 (10 points): Say that I throw a 4-sided die and a 3-sided die. What is the expectation of the product of the two numbers? What is the expectation of the max of the two numbers? • Part 2 (10 points): Given an array A, we say that a pair (i,j) is swapped if i < j but A[i] A[j]. What is the expected number of swapped pairs if A contains the integers 1 through n in a random order.
5 Problem 5 (20 points)
For both parts, make sure to show your work • Part 1: (10 points) If I throw 100 dice, what is the expected number of times that I observe the pattern 3,6,6? Note that the 3,6,6 have to appear consecutively to count as the pattern. So for example, if my result was 4,3,6,6,5,2,3,6,1,6,3,6,6,2 then the pattern occurs twice. • Part 2: (10 points) We say that three people have a 3-way birthday if they all have a birthday on the same day. Question: if each person has a random birthday (assume no leap years), then how many people do you need in a room for the expected number of 3-way-birthdays to be at least 2?
2
6 Problem 6 – extra credit • Say that I have n objects, and I play a game where I repeatedly look at a random object. (Note: I don’t throw away the objects I look at, so I might end up looking at the same object more than once.) In big-O notation, what is the expected number of objects I will look at before I have seen every one of the n objects? You must show your work, as always. HINT 1: You will want to use the formula that 1+1/2+1/3+...+1/n = O(log(n))
3