Solutions -- Analysis of Algorithms, part 1, CS 288, May 7, 2007

Solutions -- Analysis of Algorithms, part 1, CS 288,
May 7, 2007

1. &Theta(n^{lg 7})
2. &Theta(log² n)
3. &Theta(n log² n)
4. O(1)
5. O(1)
6. &Theta(log n). Asymptotic analysis is not particularly relevant here since once the minimal degree reaches a certain size, the height of a B-tree will be quite small (well under 10) for any likely value of n. Also, height computations are important largely to find the cost of search and insertion, but for B-trees, comparing two keys within the same node has a dramatically different cost in practice than comparing a key with a key from another node, which must be fetched from external memory.
1. In both cases, the worst-case time complexity is Θ(n log n).
2. Although n points would be sufficient to represent each factor, n points would be insufficient to represent the product.
3. Horner's rule has time complexity Θ(n), so using it n times on n independent problems would take time Θ(n²). The resulting algorithm would then take time Ω(n²), which cannot lead to an improvement over the multiplication algorithm for a coefficient-based representation. A similiar objection applies regarding the time required for interpolation.
4. If nth roots of 1 are used, the evaluations and interpolations are not independent. In particular, they can be formulated in terms of shared subproblems, so that a divide-and-conquer strategy makes multiplication using the Fast Fourier transform to change representations work faster asymptotically than multiplication in a coefficient-based representation.
1. The first seven tasks are scheduled in the respective slots 4, 2, 3, 1, 7, 6, 5. The last task cannot be scheduled.
2. The scheduling of task i requires inspecting i slots. So scheduling n tasks requires inspecting Θ(n²) slots, and thus Θ(n²) time. Sorting can be done in time Θ(n log n), so the necessity of sorting would not change the time complexity of the overall scheduling algorithm.
3. The classes would be {0,1,2,3,4}, {5}, {6,7}, and {8}.
4. Here the scheduling would take time O(nα(n)), where α is the slow-growing function of Chapter 21 of Cormen et al. Since the cost of sorting is asymptoticallly larger than this, the overall cost of the algorithm would be Θ(n log n).
5. Since tasks with deadline d, and any equivalent deadline, would now have to be treated the same as a task with deadline s-1, so the arguments to UNION would be d and s-1 (or equivalently s and s-1, since s would be d's representative). Recall that UNION calls FIND-SET.
6. The union-find structure after completion of the scheduling of the tasks of part 1 is given below. Note that the nodes represent slots, and FIND-SET(x) returns the slot to which a task with deadline x can be assigned. In particular, if x is in a tree rooted at 0, then a task with deadline x can no longer be scheduled. Note that any representation would have to provide a way of determining which tasks cannot be scheduled.
  The calls to UNION would have respective arguments (assuming that its arguments are d and s-1) 4 and 3, 2 and 1, 4 and 2, 3 and 0, 7 and 6, 6 and 5, and 5 and 4.
  Here no path compression is assumed. If path compression is assumed, then it would only take place for the very last successful task assignment, with deadline 5, after which the node 4 and its parent 3 would point directly to 0.
```
          0          8
       /     \
      1       5   
     / \     / \
    2   3   7   6
        |
        4
```
Note that for the scheduling problem of Section 16.5 of Cormen et al, a greedy scheduling algorithm of the sort we are considering can be used; cf their Exercise 16-4.