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

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

Answer each of the following questions using O-notation (or Θ-notation or Ω-notation where appropriate)
1. What is the time complexity of Strassen's algorithm for matrix multiplication?
2. What is the time required to sort n numbers using the sorting network of Cormen et al?
3. How many comparators are there in this network?
4. What is the amortized time complexity of implementing a binary counter that counts upward from 0?
5. What is the amortized time complexity of the DECREASE-KEY operation in Fibonacci heaps (assuming that the key can be located in O(1) time)?
6. What is the worst-case height of a B-tree with n keys? Why is asymptotic analysis not particularly relevant for this question?
For the Fast Fourier transform algorithm,
1. what is the worst-case asymptotic time complexity? what is the worst-case time complexity of the inverse Fast Fourier transform algorithm?
2. suppose that the algorithm is to be used to multiply two polynomials of degree n-1. Why is it insufficient to choose n points to represent these factors?
3. why is multiplying using the algorithm superior to an algorithm that first evaluates the factors at a given set of points using Horner's rule, then multiplies each value by the corresponding value of the other factor, and then interpolates using these values to get the product polynomial?
4. why are nth roots of 1 useful?
Imagine a greedy algorithm for a task scheduling problem in which
- each of the n tasks takes one unit of time to complete
- each task has a deadline, and must be scheduled to complete before the deadline, or not at all
- there is a single processor available, that can work on only one task at a time
- that the schedule is to consist of an assignment of tasks to slots, where slot k corresponds to the interval between time k-1 and time k, that no slot can be assigned more than one task, and that each task is assigned to at most a single slot. You may assume that there are only n slots in a schedule, numbered from 1 through n.
- the algorithm is to maximize the number of tasks scheduled
Suppose that the greedy algorithm considers tasks one at a time, and assigns them to the latest available slot consistent with their deadline. If there is no such slot, the task is simply not scheduled. Slots are unavailable if and only if they are filled by another task. So for example, if there are only 3 tasks, and each has deadline 2, only the first two tasks can be scheduled.
1. Suppose that there are 8 tasks, and the respective deadlines of tasks 1 through 8 are are 4, 2, 4, 3, 7, 6, 5, and 1. Assume that tasks are numbered in the order that they are to be considered for scheduling. Show the schedule that the greedy algorithm would construct.
2. Suppose that the available slot for a task with deadline d is found by a sequential search that starts at slot d and checks successively lower-numbered slots until either an available slot is reached or slot 1 is found to be unavailable. What is the asymptotic time complexity of task scheduling if all n tasks have deadline n? Does your answer change if the tasks first have to be sorted to determine the order in which they are to be considered for scheduling?
3. One possible improvement to the scheduling algorithm would use the notion of equivalence classes. In this approach, if slots j through k were filled, but slot j-1 was not, then slots j-1 through k would belong to the same equivalence class (because a task with a deadline anywhere from j-1 through k would be assigned to the same slot, namely slot j-1). Note that to handle the case where j is 1 when we compute j-1, a dummy slot 0 would be needed, which is not actually part of the schedule.
  Show the equivalence classes of part 1 after the first 5 tasks have been scheduled. Don't forget to include the dummy slot.
4. The introduction of equivalence classes suggests that the disjoint set data structure of Chapter 21 of Cormen et al might improve the performance of the scheduling algorithm. What would be the asymptotic time complexity of the scheduling algorithm if this data structure were used, and the tasks first had to be sorted, as in part 2? Note that union-by-rank can still be used even though the representative needs to be the smaller of the two roots -- the roots can simply be exchanged if necessary so that the larger root ends up pointing to the smaller one.
5. Using the disjoint set representation, when a task with deadline d gets assigned to slot s, what should the arguments of the corresponding UNION operation be?
6. Show the forest that results after the tasks of part 1 are scheduled. Don't forget to include the dummy slot.