(1) the x_j's smaller than or equal to 6 are 1, 3 and 6, and the total of the corresponding w_j's is 4+5+11 = 20, which is greater than T=17, and furthermore,

(2) no smaller x_i has this property: the sum of w_j's corresponding to x_j's smaller than or equal to x_5=3 is 16, which is less than T.

For Assignment 3, Question 2(a), the entries in the unsorted array are distinct, positive integers. The problem is to give an algorithm for selecting the kth smallest element of an array, assuming you have an algorithm that solves the problem defined in the first few lines of the question. For 2(b), think about the following. I keep your marks for this course in a file with each students marks on a separate line. If I sort the file according to your last names, I don't just sort the names and leave the marks where they are; I move the marks along with the names as I sort.

For Asmt 3, Question 1, note that there should only be one call to MEDIAN in an entire execution of your selection algorithm. (This means, of course, that you cannot call MEDIAN inside a loop, because then several calls to MEDIAN might happen in some execution.)

For Asmt 3, Question 4, the output should be an assignment of all the activities to rooms. Hint: Consider the activities one by one (in some order) and choose a room for each one. The room you choose for the activity should be the best one with respect to the partial schedule you've already constructed. Carefully prove your solution works. An O(n^2) solution is sufficiently efficient, although you can do it in O(nlogn) time. Ignore the stuff about interval graphs.

A clarification about the meaning of the kth smallest element of an array (in case the array has multiple copies of the same element): We will consider the kth smallest element of an array to be the smallest element x such that at least k elements of the array are less than or equal to x. Eg, if the array contains [1 2 3 1 2 4 7 9], the fourth smallest element is 2.