Problem 1 [20 points]: Problem 16-1 (Coin Changing) in your textbook.
Problem 2 [30 points]: Suppose you were planning a scenic cross country road–trip along the “Mother
Road” (i.e., U.S. Route 66). 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 d1 < d2 < · · · < dn
be the locations of all the gas stations along the route, where di
is the distance from the Chicago end of the
freeway (your starting point in this hypotehtical trip) to the gas station. You may assume that the distance
between neighboring gas stations is at most p miles. Your goal is to make as few gas stops as possible along
the way, as you want to enjoy the scenery instead of gas stations.
• Give the most efficient algorithm you can come up with to determine at which gas stations you should
stop.
• Prove that your algorithm yields an optimal solution
• Give the time complexity of your algorithm as a function of n. Note that for full marks, you must
show how you derived the complexity.
Problem 3 [25 points]: Suppose you are participating in a skiing competition with your friends. Suppose
skiers go fastest when their skis’ length is about their height. To help your team win the competition, you
decide to come up with an efficient algorithm to match skis to skiers. Your team consists of n members,
with heights h1, h2, . . . , hn, respectively, and has n pairs of skis, with corresponding lengths l1, l2, . . . , ln.
• Describe an efficient algorithm in English (and, if helpful, pseudo–code) to minimize the sum of the
absolute differences between the height of skier hi and the length of the corresponding ski lj , i.e.,
minimize 1
n
P|hi − li
|.
• Prove (or at least provide compelling arguments in favor of) the correctness of your algorithm.
• Provide an analysis of the running time of your algorithm (i.e., show the time complexity of your
algorithm, and explain how you derived it).
1
Problem 4 [25 points]: Consider a very simplistic video
game, as shown on the right, where given a field of n ∗ m cells,
your goal is to help the miner move around in order to maximize
the gold she can collect. Suppose the field is represented as
matrix F, each element Fij ≥ 0 of which denotes the amount
of gold (positive integer) to be collected from that particular
cell. A .csv file representation of F is to be provided as input
to your program. Specifically, each separate line will contain
exactly m elements separated by a coma, and there will be n
lines in total. The example input file below, represents a 3 × 3
field:
1,3,3
2,1,4
0,6,4
Initially the miner is at the first column, but can be at any row. Additionally, from any given cell, the miner
can move to the cell directly to the right, diagonally up towards the right, or diagonally down towards the right.
Given the example input above, your solution should produce the following output:
12: (2,1) -> (3,2) -> (3,3)
The first element is the total amount of gold collected, and the sequence of tuples following the “:”
character denotes the sequence of steps the miner should take. Specifically, each transition (i, j) → (k, m)
denotes a move from cell Fij to Fkm. In the specific example, the miner initially moves from cell F21,
collecting a reward of 2 amount of gold, to F32, and subsequently to F33, for a total harvest of 2 + 6 + 4 = 12
units of gold.
Implement your algorithm in Python or Java. Make sure to indicate your setup (e.g., version of Python
and libraries required), and how to run your program. If your program fails to compile, or produces logical
errors, will receive 0 points. For full marks, your code should be well documented/commented.
Your program will be evaluated for correctness [20 points] using small–scale, toy fields, and scalability [5
points] on large fields.