CSCI 570 - HW 3

CSCI 570 - HW 3
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)
2. There are N tasks that need to be completed by 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(nlogn) algorithm that minimizes the time to complete all the tasks, and
give a proof of why the solution is optimal. (15 points)
3. 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
1 < 𝑑
2 < .... < 𝑑
𝑛
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)
4. (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.
5. 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 ai
be the i-th element of set A, and let bi be the i-th element of set B. You then
receive a payoff on .Give an algorithm that will maximize your
𝑖=0
𝑛
∏ 𝑎
𝑖
𝑏
𝑖
payoff (6 points). Prove that your algorithm maximizes the payoff(10 points)
and state its running time (4 points).
6. 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).
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}