[SOLVED] Csci570 – homework 3

1. Consider a collection of n ropes which have lengths L1, L2, …, Ln, respectively. Two ropes of length L and L′ can be connected to form a single rope of length L + L′, and doing so has a cost of L + L′. We want to connect the ropes, two at a time, until all ropes are connected to form one long rope. Design an efficient algorithm for finding an order in which to connect all the ropes with minimum total cost. You do not need to prove that
your algorithm is correct. (20 points)

2. Suppose you want to drive from USC to Santa Monica. Your gas tank, when full, holds enough gas to drive p miles. Suppose there are n gas stations along the route at distances d1 ≤ d2 ≤ … ≤ dn from USC. Assume that the distance between any neighboring gas stations, and the distance between USC and the first gas station, as well as the distance between the last gas station and Santa Monica, are all at most p miles. Assume you start from USC with the tank full. Your goal is to make as few gas stops as possible along the way. Design an efficient algorithm for determining the minimum number of gas stations you must stop at to drive from USC to Santa Monica. Prove that your algorithm is correct. Analyze the time complexity of your algorithm. (25 points)

3. Suppose you are given two sequences A and B of n positive integers. Let ai be the i-th number in A, and let bi be the i-th number in B. You are allowed to permute the numbers in A and B (rearrange the numbers within each sequence, but not swap numbers between sequences), then you receive a score of ∏1
≤ i ≤ n aibi. Design an efficient algorithm for permuting the numbers to maximize the resulting score. Prove that your algorithm maximizes the score and analyze your algorithm’s running time (25 points).

5. The array A below holds a max-heap. What will be the order of elements in array A after a new entry with value 19 is inserted into this heap? Show all your work. A = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1} (10 points)