CSC263 – Problem Set 2 Solved

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 different 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 justification.

2.    [10] A PowerStack consists of a potentially infinite 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 first Pop all the elements off Si and Push them onto stack Si+1 to make room. If Si+1 is already full, we first 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 justified.

(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 first 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 efficiently 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/TEXfile 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 offence.

4. [10] In this problem, your task is to solve the following equation.



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, finds the number of unique integer solutions to the above equation, each of which satisfies the following condition:

−50 ≤ xi ≤ 50 ∀i ∈{1,2,3,4,5}

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 filename must be equation.py as required my MarkUs.

Submission: Your submission will include the following parts.

•    The Python file 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 file, provide a brief high-level description of your algorithm. A short paragraph should suffice.

•    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 file:

–    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?