University of WaterlooCS240 – Fall 2019Assignment 2Due Date: Wednesday October 2 at 5pmPlease read http://www.student.cs.uwaterloo.ca/~cs240/f19/guidelines.pdf forguidelines on submission. Problems 1 – 5(a) are written problems; submit your solutionselectronically as a PDF with file name a2Submit.pdf using MarkUs. We will also acceptindividual question files named a2q1.pdf, a2q2.pdf, … ,a2q5.pdf if you wish to submitquestions as you complete them. Submit your solution to 5(b) electronically as a file namedreport.cpp.There are 57 possible marks available. The assignment will be marked out of 55.Problem 1 [5+5+5=15 marks]For this question, it is sufficient to provide the drawings requested.a) Starting with an empty heap, show the heap resulting from insertion of 31, 40, 58, 34,25, 43, 10. Show the heap, drawn as a binary tree, after each insert operation.b) Let A =[1 2 3 4 5 6 7 8]. Draw the heap, in binary tree form, after A isheapified in-place using fix-downs according to the recipe in module 2.c) Consider a heap of size n ≥ 15 that is stored as an array A and contains the prioritiesA =[ −1 −2 −3 · · · −n ]. Perform two deleteMax operations, and show thefirst three levels of the resulting heap, drawn as a binary tree, after each operation.Problem 2 [10 marks]Let A[0 . . . n − 1] be a random permutation of the first n non-negative integers. Let P (n)be the probability that A is a max-heap, that is, that the heap-order property is satisfied.Derive the value of P (n) for the first eight sizes n = 1, 2, 3, . . . , 8.Problem 3 [10 marks]A sorting algorithm is said to sort in-place if only a constant number of elements of the inputare ever stored outside the array. But suppose you are given an array A[0 . . . n − 1] thatcontains a permutation of the first n non-negative integers. Allowing non-comparison-basedalgorithms, give an O(n) in-place algorithm to sort A. Analyze the running time of yourmethod. Note: For simplicity we are assuming A is filled with integer keys. Your algorithmmust easily extend to work for an array A that is filled with (key, element) pairs, each integerkey in the range 0 . . . n− 1 occurring exactly once.1Problem 4 [4+6=10 marks]A deterministic algorithm is one whose execution depends only on the input. By contrast,the execution of a randomized algorithm depends also on some randomly-chosen numbers.A Las Vegas randomized algorithm always produces the correct answer, but has a runningtime which depends on the random numbers chosen (randomized quick-select and quick-sortare of this type). Informally, such algorithms are always correct, and probably fast. AMonte Carlo randomized algorithm has running time independent of the random numberschosen, but may produce an incorrect answer. Informally, such algorithms are always fast,and probably correct.Given an array A of length n, an element x is said to be dominant in A if x occurs atleast bn/2c+ 1 times in A. That is, copies of x occupy more than half of the array.a) Given an array A that contains a dominant element, describe an in-place Monte Carlorandomized algorithm to find the dominant element. Show that your algorithm hasrunning time O(1) and returns the correct answer with probability at least 1/2.b) Given an array A that contains a dominant element, describe an in-place Las Vegasrandomized algorithm to find the dominant element. Show that your algorithm alwaysreturns the correct answer, and has expected running time O(n).Problem 5 [6+6=12 marks]You are given an array A[0 . . . n− 1] of integers (not necessarily distinct) that forms a max-heap of size n.a) Describe an algorithm that takes as input an integer c, not necessarily in the heap,and reports all integers in the heap that are greater than or equal to c. The runningtime of your algorithm should be O(1 +k), where k is the number of integers reported.Provide a brief explanation for why the running time of your algorithm is O(1 + k).b) Implement your algorithm from part (a). Your program should read from cin the sizen, then the n integers in the heap A[0 . . . n − 1], and finally the integer c, and thenwrite to cout the integers in the heap that are greater than or equal to c. You mayassume that every integer in the input is at least 0 and at most 231−1 (so every integerwill fit into a variable of type int).Every integer in the input and output should be on a separate line. So for instance ifthe input consists of the following lines:5171513103122then your program should print out the integers 17, 15, and 13 in any order (and onseparate lines).Submit the code for your main function, along with any helper functions, in a file calledreport.cpp.3
