Description
1. Given an array A[1..n] of n numbers, we can calculate the maximum in A only by comparing
numbers. Give an algorithm that finds the maximum and second maximum using exactly n +
O(log n) comparisons.
2. Suppose An = a1
, a2
, …, an
is a set of distinct coin types, where each ai
is a positive integer.
Suppose also that a1 < a2 < … < an
. The coin-changing problem is defined as follows. Given
a positive integer C, find the smallest number of coins from An
that add up to C, given that an
unlimited number of coins of each type are available.
(a) Suppose a1 = 1. A greedy algorithm will make change by using the larger coins first, using
as many coins of each type as it can before it moves to the next lower denomination. Show
that this algorithm does not necessarily generate a solution with the minimum number of
coins.
(b) Show that if An = {1,c,c
2
, …,c
n−1
},c ≥ 2, then the greedy algorithm always gives a minimal
solution for the coin-changing problem.
(c) Design an O(nC) algorithm that gives a minimum solution for the general case of An
.
3. Given n items {1, …, n}, and each item i has a nonnegative weight wi and a distinct value vi
. We
can carry a maximum weight of W in a knapsack. The items are blocks of cheeses so that for each
item i, we can take only a fraction xi of it, where 0 ≤ xi ≤ 1. Then item i contributes weight xiwi
and value xi vi
in the knapsack.
The continuous knapsack problem asks you to take a fraction of
each item to maximize the total value, subject to the total weight does not exceed W. The original
knapsack problem is equivalent to say xi
is either 0 or 1 depends whether the item is in or not.
Give an O(n) algorithm for the continuous knapsack problem.
4. Recall the problem of finding the number of inversions. We are given an array A[1..n] of n numbers, which we assume are all distinct, and we define an inversion to be a pair i < j such that
A[i] > A[ j]. The problem is to count the number of inversions in A. Let’s call a pair (i, j) is a
significant inversion if i < j and A[i] > 2A[ j] . Give an O(n log n) algorithm to count the number
of significant inversions in A.
CS180 Homework 6
