## 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)