Description
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 ai
bi
.
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).
4. 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 containing every student in California.
However, each school only has an ordered list of its own students sorted by GPA and the
commission needs an algorithm to combine all the lists. Design an efficient algorithm
with running time O(m log n) for combining the lists, where m is the total number of
students across all colleges and n is the number of colleges. (20 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)
