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
bi be the i
th number in B. You are allowed to rearrange the numbers within each sequence, but not swap
numbers between sequences, then you receive a score of ∏
1≤i≤n
a
bi
i
. 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(mlogn) 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}
