Posted by: atri | December 17, 2009

## Question 3(b) on the finals

I messed up: I thought I had an $O(n)$ time algorithm to compute the $p$ values but I was wrong. ($O(n \log{n})$ time is not hard or $O(n)$ is easy if the jobs are also sorted by their start times– i.e. in addition to being sorted by their finish times.) An $O(n)$ time might still be possible (let me know if you find an algorithm) but Jeff and I could not figure out one after thinking about it for an hour or so today.

Given the above, I have decided to give everyone the full 15 points on that question, irrespective of whether you attempted the question or not.

The finals have been graded– they should be available for pick up tomorrow (Friday). I’ll put up another blog post later tonight/tomorrow morning with more details on the graded finals.

## Responses

1. Woo hoo is all I have to say.

2. I’m curious what the wording was for that question.
Its entirely possible to calculate a single p value in o(n) (infact you can do it faster) but its not possible to calculate all p values (as noted in post).

Is the wording such that this could’ve been interpreted both ways?

3. I sat at this question forever on the test! I think that I eventually came up with a solution that I thought worked in O(n) time. Sort of makes me wish I didn’t have to leave Buffalo before we could get our tests back.

If I remember my solution was sort of like this. Create an array S (not P) that each index of S represents a start time and the value the highest job number that is finished by then. Initialize all indexes of S to 0 at first. Then loop through each job i, f(i) is the finish time of i. Set S(f(i)) = i if i > S(f(i)). So for example S(3) = 2 would mean that for a start time of 3, job 2 is the highest number job that has finished by then. Since we loop through each job this step takes O(n) time.

Now just buildup the P array by using the S array. Let s(i) be the start time of job i. Loop through the i jobs, letting P(i) = S(s(i)). Since you are looping through each job this takes O(n) time.

I believe that was the algorithm I had on the test. I did a test example from the example on the test and I believe it worked and I’m pretty sure its O(n) time. The only thing I’m not sure on is initializing the S array since not all indexes may be used (for example S(1) may not be used if no job finishes at time 1 so the S array may be bigger than the number of jobs, but practically only n indexes would be used). I’m curious if this would be an acceptable solution.

• David,

Your array $S$ looks to have size at least the largest finish time. So if you are initializing $S$ to all zeros at the beginning, then just the cost of initialization will be at least the largest finish time. Now consider an input where the $i$th job has finish time $i^2$. Note that in this case the maximum finish time is $n^2$, so the running time of your algorithm is $\Omega(n^2)$.

Let me know if I missed something in the above.

• That is correct, I thought maybe since we are only actually going to be using and accessing n indexes it would be okay. Is there a way we can use the same idea but use a different data structure for S like a hash map or something with keys so we are initializing only n elements for S. I know we did not go into this in class, but the problem here I assume the time complexity for accessing is not O(1) since it has to check the keys.

4. David,

Hashing only work if you are allowed to use randomization, which means with some probability the algorithm will give a wrong answer. Otherwise in the worst-case for any hash function you can always pick the finish times so that they all hash to the same value. In the latter case you gain nothing by hashing. Since the question asked for a deterministic algorithm (as that is all we have done in class), the hashing would not help.