## Description

Question 1. (22 marks) Consider an abstract data type that consists of a set S of integers on which the

following operations can be performed:

Add(i) Adds the integer i to S. If this integer already is in S, then S does not change

Sum(t) Returns the sum of all elements of S that are less than or equal to the integer t. If all the elements

of S are greater than t, then return 0.

Describe how to implement this abstract data type using an augmented AVL tree. Each operation should

run in O(log n) worst-case time, where n = |S|. Since this implementation is based on a data structure

and algorithms described in class and in the AVL handout, you should focus on describing the extensions

and modifications needed here.

a. Give a precise and full description of your data structure. In particular, specify what data is associated

with each node, specify what the key is at each node, and specify what the auxiliary information is at

each node. In particular, what is (are) the augmented field(s), and what identity should this (these) fields

satisfy. Illustrate this data structure by giving an example of it (with a small set of your own choice).

b. Describe the algorithm that implements each one of the two operations above, and explain why each

one takes O(log n) time in the worst-case. Your description and explanation should be in clear and concise

English. For the operations Sum, you should also give the algorithm’s high-level pseudocode.

Question 2. (18 marks) Describe an algorithm for the following problem. The input to the algorithm is

two unsorted sequences X = x1, x2, . . . , xn and Y = y1, y2, . . . , yn of n distinct positive integers each, and a

positive integer z. The algorithm should determine whether or not there are i and j, 1 ≤ i, j ≤ n, such that

z = xi + yj . The expected time complexity of your algorithm should be O(n), under some assumptions

that we discussed in class.

Hint: What data structures or algorithms that we learned in class involve reasoning about probability?

Note: Do not assume that the numbers in the array are small, or they have a small range, e.g., they

could be arbitrary integers. So a solution based on a direct access table or on linear time sorting is not

acceptable.

a. Describe your algorithm clearly and concisely in English, and then give the pseudo-code.

b. Explain why the expected running time of your algorithm is O(n). Explicitly state every assumption

that you need for your complexity analysis.

c. What is the worst-case running time of your algorithm? Use the Θ notation and justify your answer.

2

[The questions below will not be corrected/graded. They are given here as interesting problems

that use material that you learned in class.]

Question 3. (0 marks)

A Scheduler S consists of a set of threads; each thread is a tuple t = (id, status) where id is a distinct

positive integer and status ∈ {A, R, S}; intuitively, A means active, R means ready to be scheduled, and

S means stalled. The operations that Scheduler S supports are:

NewThread(t): Given a thread t = (id, A) where id is larger than that of any thread currently in S,

add thread t to S.

Find(i): If S has a thread t = (i, −) then return t, else return −1.

Completed(i): If S has a thread t = (i, −) then remove t from S, else return −1.

ChangeStatus(i, stat): If S has a thread t = (i, −) then set the status of t to stat, else return −1.

ScheduleNext: Find the thread t with smallest id among all the threads whose status is R in S, set

the status of t to A and return t; if S does not have a thread whose status is R then return −1.

In this question, you must describe how to implement the Scheduler S described above using an augmented

AVL tree such that each operation takes O(log n) time in the worst-case, where n is the number of threads

in S. Since this implementation is based on a data structure and algorithms described in class and in the

AVL handout, you should focus on describing the extensions and modifications needed here.

a. Give a precise and full description of your data structure. In particular, specify what data is associated

with each node, specify what the key is at each node, and specify what the auxiliary information is at each

node. Illustrate this data structure by giving an example of it (with a small set of threads of your own

choice).

b. Describe the algorithm that implements each one of the five operations above, and explain why

each one takes O(log n) time in the worst-case. Your description and explanation should be in clear and

concise English. For the operations ChangeStatus(i, stat) and ScheduleNext, you should also give

the algorithm’s high-level pseudocode.

Question 4. (0 marks) You are given a list L of n, not necessarily distinct, integers. Your task is to devise

an algorithm that outputs a list of the distinct integers in L, in order of non-increasing frequency (the

frequency of an element in L is the number of times it occurs in L). For example, if L is 2, 5, 4, 4, 2, 3, 4, 3,

then a suitable output is 4, 3, 2, 5; the only other suitable output for this list is 4, 2, 3, 5. In this example,

L contains only small integers, but this is not always the case. You cannot make any assumption on the

integers in L (e.g., their maximum size, or distribution). In particular, some integers of L can very large,

and so it is not feasible to use tables of size proportional to these integers.

a. Give a Hash Table-based algorithm for this problem whose expected time complexity is O(n), under

some Hash Table assumptions that you must clearly state. Explain why your algorithm is correct and

achieves this time complexity under these assumptions.

What is the worst-case time complexity of your algorithm? Use the Θ notation and justify your answer.

Hint: As part of your algorithm, find a way to sort n numbers in the range 0 to n in O(n) time in the

worst-case.

b. Give an algorithm for this problem whose worst-case time complexity is O(n log n). Describe why

your algorithm in clear and concise English, and explain why it achieves this time complexity.

3