$30.00
Description

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 A_{n} = a_{1}, a_{2}, …, a_{n} is a set of distinct coin types, where each a_{i} is a positive integer. Suppose also that a_{1} < a_{2} < … < a_{n}. The coinchanging problem is defined as follows. Given a positive integer C, find the smallest number of coins from A_{n} that add up to C, given that an unlimited number of coins of each type are available.


Suppose a_{1} = 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 A_{n} = f1, c, c^{2}, …, c^{n} ^{1}g, c 2, then the greedy algorithm always gives a minimal solution for the coinchanging problem.



Design an O(nC) algorithm that gives a minimum solution for the general case of A_{n}.


Given n items f1, …, ng, and each item i has a nonnegative weight w_{i} and a distinct value v_{i} . 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 x_{i} of it, where 0 x_{i} 1. Then item i contributes weight x_{i} w_{i} and value x_{i} v_{i} 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 x_{i} 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 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.

Express your algorithm in a wellstructured 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 L^{A}T_{E}X, L_{Y}X or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.
2