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 February 24, 2018, 22:00; required les: ps2sol.pdf, ps2sol.tex and equation.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] Suppose that we want to generate a BST by inserting the keys 1 through n into an initially empty BST (assume
n > 1). Assume that the insert sequence is a random permutation of [1;2;3;:::;n] and each permutation is equally
likely to occur. Answer the following questions.
(a) What is the maximum possible height of the generated BST? Describe three di erent insert sequences that would
result in a BST with the maximum height.
(b) By picking a random permutation of [1;2;3;:::;n] as the insert sequence, what is the probability that the resulting
BST has the maximum height? Show detailed steps of your calculation with clear justi cation.
2. [10] A PowerStack consists of a potentially in nite series of stacks S0;S1;S2;:::, where the i-th stack Si can hold up
to 2i elements. In this question, we study the following PowerPush operation for an PowerStack.
The main working mechanism of a PowerPush is the following: whenever there is an attempt to Push an element onto
any full stack Si, we rst Pop all the elements o Si and Push them onto stack Si+1 to make room. If Si+1 is already
full, we rst recursively move all its members to Si+2, etc. Each PowerPush operation starts by attempting to Push to
S0. Assume that each elementary Push and Pop operation takes 1 unit of time, and the cost of any other operation
(e.g., checking if a stack is full) is ignored.
(a) In the worst case, how many units of time does it take to PowerPush one new element onto a PowerStack containing
n elements? Your answer should be in exact form. (i.e., not in asymptotic notation) and justi ed.
(b) Consider performing a sequence of n PowerPush operations onto a PowerStack that is initially empty. Show that
the amortized runtime per operation is O(logn).
Hint: You can rst try to analyze it using the aggregate method, which is doable but quite complicated; then you
should try the accounting method and realize that it becomes much simpler.
3. [10] In this problem, you will design the data structure for implementing an ADT called SHOPPING-SET. Below is the
description of the ADT.
Objects: A collection of items objects for sale. Each item object obj has the following attributes:
obj.name: a string which is the name of the item. Each item has a unique name, i.e., no two items have the
same name.
obj.price: a decimal value such as 12:99. For simplicity, assume that the each item’s price is unique, i.e., no
two items have the same price.
obj.rating: a decimal value between 0:0 and 5:0, e.g., 0:012, 3:1415926. For simplicity, assume that each
item’s rating value is unique, i.e., no two items have the same rating value.
Operations:
GET-ITEM(S, name): returns the item object with name name if it exists in the SHOPPING-SET S; returns NIL
if the item does not exist in S.
ADD-ITEM(S, obj): Add an item object obj to the SHOPPING-SET S. You may assume that obj has a unique
name, a unique price and a unique rating.
TOP-RATED-UNDER-PRICE(S, p): returns the top-rated item object (item with the maximum rating value)
whose price is less than or equal to p.
Requirements: Let n be the size of S,
GET-ITEM(S, name) must have average-case runtime O(1).
ADD-ITEM(S, obj) must have worst-case runtime O(logn).
TOP-RATED-UNDER-PRICE(S, p) must have worst-case runtime O(logn).
Give a detailed description of the design of your data structure by answering the following questions.
(a) Which data structure(s) do you use in your design? What is the key of each data structure? What attributes does
each node in your data structure(s) keep?
(b) Explain concisely in English how your GET-ITEM operation works, and justify its runtime.
(c) Explain concisely in English how your ADD-ITEM operation works, and justify its runtime. In particular, explain
why all the attributes kept in each node can be maintained e ciently upon the addition of the new node.
(d) Explain how your TOP-RATED-UNDER-PRICE works and write the pseudocode of this operation, then justify its
runtime.
Note: As usual, please do not repeat algorithm details or runtime analyses from class or the textbook | just directly
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 problem, your task is to solve the following equation.
Ax31 + Bx32 + Cx33 + Dx44 + Ex55 = S
where x1;x2;:::;x5 are unknowns, and A;B;C;D;E;S are given constants. All these constants are integers and can
be positive, negative, or zero.
You will write a Python program that, given the values of A, B, C, D, E, and S, nds the number of unique integer
solutions to the above equation, each of which satis es the following condition:
50 xi 50 8i2f1;2;3;4;5g
The header of your function is as follows. The test cases in the docstring can be used to verify the correctness of your
program.
1 def solve(A, B, C, D, E, S):
2 ’’’
3 Return the number of unique integer solutions
4 where each integer is in the range [-50, 50]
5
6 Precondition: A, B, C, D, E, S are integers in the range [-1000, 1000]
7
8 >>> solve(12, 34, 56, 78, 9, 10)
9 159
10 >>> solve(148, -42, 21, 77, -2, -263)
11 112
12 >>> solve(0, 0, 0, 0, 0, 0)
13 10510100501
14 ’’’
Requirements:
Your solve() function must be able to return the correct answer within 5 seconds (measured when running on
the cslinux.utm.utoronto.ca server). It’s not hard to think of a na ve algorithm which enumerates and checks
all possible 5-tuples of the unknowns, but this algorithm will obviously be too slow.
You are not allowed to use the built-in Python set or dict in your code, and you are not allowed to use any
import statement in your code.
Your code must be written in Python 3, and lename must be equation.py as required my MarkUs.
Submission: Your submission will include the following parts.
The Python le equation.py which implements the solve() function. The TA will test your code using the
following manner:
import equation # importing your equation.py
check_equal(159, equation.solve(12, 34, 56, 78, 9, 10))
# check_equal reports FAIL if exceeding the 5 seconds timeout.
In your PDF le, provide a brief high-level description of your algorithm. A short paragraph should su ce.
It is likely that you’ll implement a hash table in your solution (take this as a hint). If this is the case, provide your
answers to the following questions in your PDF le:
{ Which mechanism do you use to resolve collision, chaining or open addressing?
{ What is your hash function? Why do you think it is a good hash function?
{ What size do you choose for the hash table? Is this the optimal size that makes your code run as fast as
possible? Why