Homework Assignment #3 Solution

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 = jSj. 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 modi cations needed here.




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 eld(s), and what identity should this (these) elds 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.




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



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.



[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 2 fA; R; S g; 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 modi cations needed here.




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 ve 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.




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, nd a way to sort n numbers in the range 0 to n in O(n) time in the worst-case.




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