CS 415 Algorithm Analysis Spring 2011
Practice Problems for the final examination
1)An algorithm solves a problem of size n (in the worst-case) in 20 n2 steps, while another algorithm takes n3 steps in the worst-case for the same problem. What is the smallest value of n for which the former algorithm would outperform the latter?
2)Use iterative substitution to solve the recurrence equationT(n) = 2 T(n – 1) + 1, with the initial condition T(1) = 1.
3)Given integers x and y, we want to compute x2, xy and y2. Clearly this can be done with 3 multiplications. Describe how to compute all the three numbers using only two multiplications and other operations like addition, subtraction and bit shift (left or right) operations.
4)We are to complete a set of n jobs using m identical machines. Each job has a known duration. The goal is to schedule the jobs on m machines so that the time to finish the last job is as small as possible. Once a job is scheduled on a machine, it can’t be stopped and restarted. Any job can run on any machine. A greedy algorithm to solve this problem is as follows: sort jobs in decreasing order of duration. Schedule jobs one by one, choosing the machine where it can start the earliest.
(a)For m = 3 and n = 6 where the durations are <9, 12, 3, 8, 6, 5>, what is the finish time of the last job using greedy schedule?
(b)Exhibit an input for which the greedy schedule is NOT optimal.
(c)Describe an efficient implementation of the above greedy algorithm using a binary heap and estimate the time complexity.
5)Consider the following knapsack problem:
Object 1 2 3 4
Weight 7 4 8 6
Profit 21 11 23 15
Volume of the knapsack is 20.
(a)Let T[j, k] denote the optimal solution of the problem with the first j objects, where the profit is k. What values does T[4, 15] depend on? What values does T[3, 10] depend on?
(b)If we are allowed to choose the same object arbitrary number of times, what is the optimum solution to the above problem?
6)Consider a version of the knapsack problem in which each object has a weight and a profit, and a specified knapsack capacity. Each object can be taken 0 or 1 time. Will any of the following ((greedy) algorithms always produce an optimal solution? In each case, an order of the objects is specified. The algorithm includes the objects one at a time in that order and skips over the objects that will cause the weight of the knapsack to exceed the capacity. Prove or give a counter-example:
(a)increasing order of weight.
(b) decreasing order of profit
(c) decreasing order of profit to weight ratio
7)You bring a t-foot log of wood to your favorite sawmill. You want it cut in k specific places: feet from the left end. The sawmill charges x dollars to cut an x-foot log any place you want. Give a dynamic programming based algorithm that determines the order in which they should cut in order to minimize the cost. Estimate the time complexity of your algorithm. (It should be a polynomial in k.)
8)Exercises 3.11, 3.12, page 112.
9)Exercise 4.6, page 191.
10) Exercise 5.1, page 246.
11)Exercise 7.4, 7.5 and 7.6 page 416.