Remember to write your full name and student number prominently on your submission. To avoid suspicions of plagiarism:
at the beginning of your submission, clearly state any resources (people, print, electronic) outside of your group,
the course notes, and the course sta , that you consulted.
Remember that you are required to submit your problem sets as both LaTEX.tex source les and .pdf les. There is a 10%
penalty on the assignment for failing to submit both the .tex and .pdf.
Due January 27, 2018, 22:00; required les: ps1sol.pdf, ps1sol.tex and heap.py
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on
correctness, but also on clarity. Answers that are technically correct that are hard to understand will not receive full marks.
Mark values for each question are contained in the [square brackets].
You may work in groups of up to THREE to complete these questions.
1. [10] Consider the following algorithm that describes the procedure of a casino game called \Game148". The index of
the array A starts at 1. Let n denote the length of A.
1 def Game148(A):
2 ’’’
3 Pre: A is a list of integers , len(A) > 148, and it is generated
4 according to the distribution specified below.
5 ’’’
6 winnings = -6.00 # the player pays 6 dollars for each play
7 for i from n downto 1:
8 winnings = winnings + 0.01 # winning 1 cent
9 if A[i] == 148:
10 print("Boom! Game Over.")
11 return winnings
12 print("You survived!")
13 return winnings
The input array A is generated in the following speci c way: for A[1] we pick an integer fromf0;1guniformly at random;
for A[2] we pick an integer fromf0;1;2guniformly at random; for A[3] we pick an integer fromf0;1;2;3guniformly at
random, etc. That is, for A[i] we pick an integer fromf0;:::;iguniformly at random. All choices are independent from
each other. Now, let’s analyse the player’s expected winnings from the game by answering the following questions. All
your answers should be in exact form, i.e., not in asymptotic notations.
(a) Consider the case where the player loses the most (i.e., minimum winnings), what is the return value of Game148
in this case? What is the probability that this case occurs? Justify your answer carefully: show your work and
explain your calculation.
(b) Consider the case where the player wins the most (i.e., maximum winnings), what is the return value of Game148
in this case? What is the probability that this case occurs? Justify your answer carefully: show your work and
explain your calculation.
(c) Now consider the average case, what is the expected value of the winnings of a player (i.e., the expected return
value of Game148) according to the input distribution speci ed above? Justify your answer carefully: show your
work and explain your calculation.
(d) Suppose that you are the owner of the casino and that you want to determine a length of the input list A so that
the expected winnings of a player is between 1:01 and 0:99 dollars (so that the casino is expected to make about
1 dollar from each play). What value could be picked for the length of A? You are allowed to use math tools such
as a calculator or WolframAlpha to get your answer.
2. [10] You are given a binary max-heap H and you will design the following two algorithms with di erent requirements.
For both algorithms you may assume that the size of H is at least 3, and that all elements in H have distinct values.
Also, recall that H is an array since that’s how heaps are implemented. You may decide yourself where the index starts
from (0 or 1), and your pseudocode should work correctly according to your decision.
(a) Design the EXTRACT-THIRD-LARGEST(H) algorithm which removes and returns the third largest element in H.
The worst-case runtime must be O(logn). Write the pseudocode of your algorithm and justify its correctness and
worst-case runtime.
(b) Design the GET-THIRD-LARGEST(H) algorithm which returns the third largest element in H without removing
it. The worst-case time complexity of your algorithm must be as low as possible. Only the fastest possible
algorithm will get full mark. Write the pseudocode of your algorithm and justify its correctness and worst-case
runtime.
Note: For both designs you may use the following functions that we learned from the lecture as helper functions:
BUBBLE-DOWN, EXTRACT-MAX, INCREASE-KEY and INSERT.
3. [10] For this problem, we de ne the golden element of a collection of n elements to be the element at indexd0:618 ne
in the sorted list of all the elements (where index starts from 1). Note that this de nition does not imply that the
collection of elements is always fully sorted. It is only a convenient way to de ne the notion of \golden element"
rigorously, by imagining the elements in sorted order.
Consider the following abstract data type that we will call a \GOLDEN-SET."
Objects: A collection of elements taken from an ordered set (i.e., elements can be compared with each other). Duplicate
elements are allowed (this is why we use the term \collection" instead of \set").
Operations:
INSERT(S;x): Add element x to the collection S.
FIND-GOLD(S): Return the golden element of collection S without removing it.
DIG-GOLD(S): Remove and return the golden element of collection S.
Requirements: Let n be the size of S,
INSERT(S;x) must have worst-case runtime O(logn).
FIND-GOLD(S) must have worst-case runtime O(1).
DIG-GOLD(S) must have worst-case runtime O(logn).
Give a detailed description of a data structure that implements GOLDEN-SET and satis es the above requirements on
runtime. Described your algorithms for each of the operations, and justify that they are correct and have the required
worst-case runtime.
Note: Please do not repeat algorithms or runtime analyses from class or the textbook | just refer to known results
as needed.
Programming Question
The best way to learn a data structure or an algorithm is to code it up. In each problem set, we will have a programming
exercise for which you will be asked to write some code and submit it. You may also be asked to include a write-up about
your code in the PDF/TEX le that you submit. Make sure to maintain your academic integrity carefully, and protect
your own work. The code you submit will be checked for plagiarism. It is much better to take the hit on a lower mark than
risking much worse consequences by committing an academic o ence.
4. [10] In this programming question, you will implement the two versions of the BUILD-MAX-HEAP operation that we
learned in lecture, which takes an unordered list as the input and manipulates it into a list that represents a binary
max-heap. Version 1 builds the heap by repeatedly heap-inserting all elements in the list into an initially-empty heap,
which takes O(nlogn) time; Version 2 is the beautiful and e cient O(n) algorithm that calls BUBBLE-DOWN on about
half of the elements in the list. You will also implement an IS-HEAP function which is useful for checking whether the
heap that you built is a valid one. Below are the detailed speci cations.
Your code must be written in Python 3, and the lename must be heap.py as required by MarkUs. In your
heap.py, implement the following three functions:
build max heap slow(L): Version 1 of the build max heap implementation.
{ Precondition: L is an unordered list of integers.
{ Postcondition: L is a heap-ordered list that represents a valid binary max heap.
build max heap fast(L): Version 2 of the build max heap implementation. Its precondition and postcondition
are the same as those of Version 1.
is heap(L):
{ Precondition: L a list of integers.
{ Postcondition: returns TRUE if and only if L represents a valid binary max-heap.
Write-up: In your ps1sol.pdf, include the following results from your program.
Count the number of swaps performed by each version of the build-max-heap operation, and create a table that
compares the numbers of swaps of the two implementations. Record the number of swaps for input sizes 1000,
5000, 10000, 50000, and 100000.
You must pick your input lists carefully such that the recorded numbers show the O(nlogn) vs O(n) runtime
di erence between the two versions of build-max-heap. Indicate clearly what kind of inputs you choose and
explain why the result shows the O(nlogn) vs O(n) di erence.
If the input lists are simply randomly generated, do you observe theO(nlogn) vsO(n) runtime di erence? Brie y
explain your thoughts about the reasons behind your observations