1    Statement on Collaboration and Use of Resources

To develop good practices in doing homeworks, citing resources and acknowledging input from others, please complete the following. This question is worth 2 marks.

1. All group members have read and followed the guidelines for groupwork on assignments in CPSC 320              (seehttps://www.students.cs.ubc.ca/~cs-320/2021W2/index.php?page=assignments&menu=1&submenu= 3).

 Yes               No

2. We used the following resources (list books, online sources, etc. that you consulted):

3. One or more of us consulted with course staff during office hours.  Yes               No

4. One or more of us collaborated with other CPSC 320 students, none of us took written notes during our consultations and we took at least a half-hour break afterwards.

 Yes               No

If yes, please list their name(s) here:

5. One or more of us collaborated with or consulted others outside of CPSC 320, none of us took written notes during our consultations and we took at least a half-hour break afterwards.

 Yes               No

If yes, please list their name(s) here:

6. One or more of us collaborated with or consulted others CPSC 320 students or people outside of CPSC 320, but we took written notes during our consultations or we did not take at least a half-hour break afterwards.

 Yes               No

If yes, please list their name(s) here:

2    Recurrence relations

1.  [5 points] Give a tight upper bound (O) on the solution of the following recurrence relation.

T(n) = (T(⌊⌋) + log2 n

if n ≥ 2

if n = 1

T(n) = (T(n − b) + cn

if n ≥ b

if n < b

3    Significant inversions

Recall the problem of computing the number of inversions from the assigned readings:  we are given a sequence of n numbers a1 , a2 , . . . , an, which we assume are all distinct, and we want the compute the number of inversions: pairs i < j such that ai > aj. The number of inversions is a measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let us call a pair a significant inversion if i < j and ai > 2aj .

1.  [6 points] Give an O(nlog n) algorithm to count the number of significant inversions between two orderings.

4    Rank by element, rather than element by rank

In worksheet #4, we will describe an algorithm QuickSelect to find the kth smallest element of an unsorted array.  In this problem, we are considering the converse problem: given a value x, find the rank of x in a collection of data. For instance, if we have n elements, the rank of the smallest element of the set is 1, and the rank of the largest element of the set is n.

1.  [1 point] Give a simple O(n) time algorithm to solve this problem in the case where the input consists of an unsorted array A with n elements, and the value x.

2.  [3 points] Now assume that we want to answer q such queries, with the same array A each time but different values of x.

(a) Describe a way to answer these queries that will be more efficient than your algorithm from the previous question, at least for some values of q .

(b) Give a tight bound on the worst-case running time of a sequence of q queries using your algorithm from the previous part, as a function of both n and q .

(c) For which values of q is this more efficient than calling the algorithm from question 1 repeatedly?

3.  [5 points] Suppose now that the collection of values we have is dynamic, instead of being a static array A:  we will be inserting new values, and deleting old ones.  In CPSC 221, you learned that we could store this data in a balanced binary search tree (such as an AVL tree) so every insertion and deletion operation takes in O(log n) time, where n is the size of the tree.  So assume that we have a balanced binary search tree containing our data, and that in addition to the usual fields each node N also contains the size of tree rooted at N .

Describe an efficient algorithm that takes in such a tree T and a value x, and returns the rank of x. What is the worst-case running time of your algorithm?

Note:  you can think of the Quicksort algorithm as implicitly constructing a binary search tree:  the pivot is the value stored at the root of the tree, the array Lesser contains the elements of the left subtree of the root, and Greater contains the elements of the right subtree.