HW 3

Graded Problems

    1. We have N ropes having lengths L1, L2, . . . , LN . We can connect two ropes at a time: Connecting ropes of length L and L′ gives a single rope of length L + L′ and doing so has a cost of L + L′ . We want to repeatedly perform such connections to finally obtain one single rope from the given N ropes. Develop an algorithm to do so, while minimizing the total cost of connecting. No proof is required. (10 points)

    2. There are N tasks that need to be completed using 2 computers A and B. Each task i has 2 parts that take time: ai (first part) and bi (second part) to be completed. The first part must be completed before starting the second part. Computer A does the first part of all the tasks while computer B does the second part of all the tasks. Computer A can only do one task at a time, while computer B can do any amount of tasks at the same time. Find an O(n log n) algorithm that minimizes the time to complete all the tasks, and give a proof of why the solution obtained by the algorithm is optimal. (15 points)

    3. Suppose you want to drive from USC to Santa Monica. Your gas tank, when full, holds enough gas to go 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. Give the most efficient algorithm to determine which gas stations you should stop at and prove that your algorithm yields an optimal solution (i.e., the minimum number of gas stops). Give the time complexity of your algorithm as a function of n. (15 points)

    4. (a) Consider the problem of making change for n cents using the fewest number of coins. Describe a greedy algorithm to make change consisting of quarters(25 cents), dimes(10 cents), nickels(5 cents) and pennies(1 cents). Prove that your algorithm yields an optimal solution. (Hints: consider


1





how many pennies, nickels, dimes and dime plus nickels are taken by an optimal solution at most.)

(b) For the previous problem, give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Assume that each coin’s value is an integer. Your set should include a penny so that there is a solution for every value of n.

    5. Suppose you are given two sets A and B, each containing n positive in-tegers. You can choose to order the numbers in each set however you like. After you order them, let ai be the ith number in set A, and let bi
n
be the ith element of set B.  You then receive a payoff of    abii .  Give
i=0
an algorithm to decide the ordering of the numbers so as to maximize your resultant payoff (6 points). Prove that your algorithm maximizes the payoff (10 points) and state its running time (2 points).

    6. The United States Commission of Southern California Universities (USC-SCU) is researching the impact of class rank on student performance. For this research, they want to find a list of students ordered by GPA contain-ing every student in California. However, each school only has an ordered list of its own students by GPA and the commission needs an algorithm to combine all the lists. Find the fastest algorithm for yielding the combined list and give its runtime in terms of m, the total number of students across all colleges, and n, the number of colleges. (12 points)

    7. 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}























2