Homework 6 Solution

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.



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.



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.



Show that if An = f1, c, c2, ..., cn 1g, c 2, then the greedy algorithm always gives a minimal solution for the coin-changing problem.



Design an O(nC) algorithm that gives a minimum solution for the general case of An.



Given n items f1, ..., ng, 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 xi wi 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.



Recall the problem of finding the number of inversions. We are given an array A[1..n] of n num-bers, 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.









Express your algorithm in a well-structured manner. Use pseudo code and the textbook has good examples to follow. Avoid using a long continuous piece of text to describe your algorithm. Start each problem on a NEW page. Unless specified, you should justify the time complexity of your algorithm and why it works. For grading, we will take into account both the correctness and the clarity. Your answers are supposed to be in a simple and understandable manner and sloppy answers are expected to receiver fewer points.



Homework assignments are due on Gradescope. Email attachments or paper submissions are NOT acceptable.



Raw photo is NOT acceptable. Upload your homework as a PDF scan by using a scanner or mobile scanner app. Match each problem with your answer on Gradescope. Use dark pen or pencil and your handwriting should be clear and legible.



1
We recommend using LATEX, LYX or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.
































































































































































































2