辅导案例-CS240

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
University of Waterloo
CS240 - Fall 2019
Assignment 2
Due Date: Wednesday October 2 at 5pm
Please read http://www.student.cs.uwaterloo.ca/~cs240/f19/guidelines.pdf for
guidelines on submission. Problems 1 – 5(a) are written problems; submit your solutions
electronically as a PDF with file name a2Submit.pdf using MarkUs. We will also accept
individual question files named a2q1.pdf, a2q2.pdf, ... ,a2q5.pdf if you wish to submit
questions as you complete them. Submit your solution to 5(b) electronically as a file named
report.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 is
heapified 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 priorities
A =
[ −1 −2 −3 · · · −n ]. Perform two deleteMax operations, and show the
first 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 input
are ever stored outside the array. But suppose you are given an array A[0 . . . n − 1] that
contains a permutation of the first n non-negative integers. Allowing non-comparison-based
algorithms, give an O(n) in-place algorithm to sort A. Analyze the running time of your
method. Note: For simplicity we are assuming A is filled with integer keys. Your algorithm
must easily extend to work for an array A that is filled with (key, element) pairs, each integer
key in the range 0 . . . n− 1 occurring exactly once.
1
Problem 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 running
time which depends on the random numbers chosen (randomized quick-select and quick-sort
are of this type). Informally, such algorithms are always correct, and probably fast. A
Monte Carlo randomized algorithm has running time independent of the random numbers
chosen, 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 at
least 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 Carlo
randomized algorithm to find the dominant element. Show that your algorithm has
running 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 Vegas
randomized algorithm to find the dominant element. Show that your algorithm always
returns 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 running
time 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 size
n, then the n integers in the heap A[0 . . . n − 1], and finally the integer c, and then
write to cout the integers in the heap that are greater than or equal to c. You may
assume that every integer in the input is at least 0 and at most 231−1 (so every integer
will fit into a variable of type int).
Every integer in the input and output should be on a separate line. So for instance if
the input consists of the following lines:
5
17
15
13
10
3
12
2
then your program should print out the integers 17, 15, and 13 in any order (and on
separate lines).
Submit the code for your main function, along with any helper functions, in a file called
report.cpp.
3
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468