Test #1, CS 255, March 1, 2006

There are 150 points on the test.
Problem 8 is worth 10 points; the others are worth 20 points each
The phrase "the text" below means Cormen et al

What is the expected time complexity of
1. the text's RANDOMIZED-SELECT algorithm?
2. the selection algorithm of Problem 1 of Problem Set 1 (using the constant 5, not the constant 3)?
3. randomized quicksort?
4. finding the second smallest element in a sequence of numbers?
Your answers to the first three parts should use Θ-notation, your answer to the last part should not.
Given the instance (8 5 4 9 7 6 3 2) for the simultaneous max & min problem,
1. How many element comparisons would be required for this instance by the divide and conquer algorithm discussed in class for this problem?
2. Which pairs of elements are compared?
Note that we discussed two versions of the algorithm in class. You may use either version, but whenever you divide, your left piece should be no larger than your right piece.
What solution will the greedy algorithm for the activity-selection problem of the text's Section 16.1 find, where there are 7 tasks, and tasks t₁ through t₇ have respective start times 1, 2, 4, 3, 6, 9, and 7, and respective finish times 3, 5, 7, 8, 11, 12, and 13?
1. Give an optimal solution that is not a greedy solution for the instance of the previous question
2. Give an instance of the task-scheduling problem of the text's Section 16.5, such that there are two distinct optimal solutions of size 4. The term "solution" here means the set of tasks that are scheduled by their deadlines.
An instance of the bin packing problem is an integer T and a set of items with weights in (0,1). The question is whether there is a mapping of items to {1,2,…,T} so that the sum of the weights of the items mapped to i is at most 1 for each i. Show that the bin packing problem is in NP.
1. Show that the partition problem is polynomially reducible to the subset sum problem.
2. To show that the partition problem is NP-complete, Problem Set 2 asks you to use a reduction from a third problem (3-CNF-SAT). Given that the subset sum problem is NP-complete, why isn't it enough just to use the result of the first part of this question?
The test continues on the reverse side

Show how the dynamic programming algorithm for the assembly-line scheduling problem of the text's Section 15.1 would find the minimum time through the factory for the instance diagrammed below. You needn't give the schedule that achieves this time. In other words, in the terminology of the text, you need only give the values for f₁ and f₂, as well as the optimal cost f*. You needn't give the values for l₁ and l₂.

a[1,i]:         3 →→→→→ 5 →→→→→ 5 →→→→→ 10
               ↗ ↘     ↗  \    ↗  \    ↗ \
              2    3  /    3  /    3  /   1 
     item    /      \/      \/      \/     ↘   item
   enters    \      /\      /\      /\     ↗   exits
              3    2  \    2  \    2  \   6
               ↘  /    ↘  /    ↘  /   ↘ /
a[2,i]:         7 →→→→→ 1 →→→→→ 2 →→→→→ 8

Suppose that an instance of the matrix-chain multiplication problem has constructed the s matrix given below. Give the optimal method for multiplying the 6 matrices in the instance, if they are named A₁ through A₆.
```
                     2
                   3   2
                 2   3   3
               1   3   4   5
             1   2   3   4   5
```