CSCI 570 HW 3 Solution

1. You have N ropes each with length L1, L2, . . . , LN, and we want to connect the ropes into one rope. Each time, we can connect 2 ropes, and the cost is the sum of the lengths of the 2 ropes. Develop an algorithm such that we minimize the cost of connecting all the ropes. No proof is required. (10 points)

1. There are N tasks that need to be completed by 2 computers A and B. Each task “i” has 2 parts that take time: a_i (first part) and b_i (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(nlogn) algorithm that minimizes the time to complete all the tasks, and give a proof of why the solution is optimal. (15 points)

1. Suppose you were to drive from USC to Santa Monica along I-10. Your gas tank, when full, holds enough gas to go $p$ miles, and you have a map that contains the information on the distances between gas stations along the route. Let ₁ < ₂ < .... < be the locations of all the gas stations along the route where is the distance from USC to the gas station. We assume that the distance between neighboring gas stations is at most miles. Your goal is to make as few gas stops as possible along the way. Give the most efficient algorithm to determine at which gas stations you should stop and prove that your strategy yields an optimal solution. Give the time complexity of your algorithm as a function of . (15 points)

1. (a) Consider the problem of making change for 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 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.

1. Suppose you are given two sets A and B, each containing n positive integers. You can choose to reorder each set however you like. After reordering, let a_i

be the i-th element of set A, and let b_i be the i-th element of set B. You then payoff (6 points). Prove that your algorithm maximizes the payoff(10 points) and state its running time (4 points).

1. The United States Commission of Southern California Universities (USCSCU) is researching the impact of class rank on student performance. For this research, they want to find a list of students ordered by GPA containing 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. There are a few hundred colleges of interest, but each college can have thousands of students, and the USCSCU is terribly underfunded so the only computer they have on hand is an old vacuum tube computer that can do about a thousand operations per second. They are also on a deadline to produce a report so every second counts. Find the fastest algorithm for yielding the combined list and give its runtime in terms of the total number of students (m) and the number of colleges (n).

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