Description
1. (30 points) You are provided a sequence of points P = pi(xi
, yi), 1 ≤ i ≤ n. These points were
drawn on the screen as a single stroke (i.e. without lifting the pen) by a user in a sketching application
(Table 1(a)). The sequence is ordered by how the user drew the stroke.
(a) (b) (c)
Table 1: (a) the set of points (b) the result of fitting one least-squares line (c) the result of fitting 4
least-squares line segments
We can fit a line y = ax + b to these set of points using a least-squares formulation (Table 1(b)). In
this formulation, the values of a and b can be computed as:
a =
n
P
i
xiyi−(
P
i
xi)(P
i
yi)
n
P
i
xi
2−(
P
i
xi)
2
b =
P
i
yi−a
P
i
xi
n
The error of this fit can be measured as
1
e =
P
i
(a ∗ xi + b − yi)
2
The issue is that the drawn points may not form just one line, but a chain of connected line segments
(Table 1(c)). However we do not know the points where one line segment ends and the next one begins.
We consider a partition of P to be a set I = i1, i2, i3, …im such that 1 ≤ i1 ≤ i2… ≤ im ≤ n. This partition creates a poly-line by fitting segments to points (x1, y1)…(xi1
, yi1
), (xi1
, yi1
)…(xi2
, yi2
),…,(xim, yim)…(xn, yn).
We would like to create as few partitions as possible, while also ensuring that a line fits well (i.e. the
error of the fit is minimized). Accordingly, we associate a penalty with the partition. The penalty is the
sum of the following:
1. The penalty associated with each segment in the partition, a constant C. (this would discourage
excessive partitioning)
2. For each segment, the error value of line fit on the points in that segment
Our problem is to determine a partition of minimum penalty. This would correspond to the “best fit
of segments over the stroke”.
(a) Prove that this problem exhibits the optimal substructure property. That is, an optimal partition
contains optimal partitions for sub-problems.
(b) Devise the problem as a recurrence. Hint: let OPT(i) be the penalty for the optimal partition of
points p1, …pi
.
(c) Write the pseudo-code for a complete bottom-up solution to this problem. The output of your
algorithm should be the optimal partition.
(d) Analyze your solution in time and auxiliary space.
Note: the fit line segments may not actually pass through the partitioning points (the figure above is
misleading in this regard). In practice, we would create the poly-line by considering the intersection points
of adjacent segments.
2. (20 points)
Amit has joined a year-old weight-loss boot camp. This includes weekly weigh-ins, measured in pounds.
Obviously the goal for each participant is to lose weight over the year. However to increase healthy
competition and promote a sustainable healthy lifestyle, the program awards one special point every time
a person weighs less than what they did at an earlier point in the program. the program awards points for
a losing streak. For example if Amit’s weights are {180, 178, 182, 175, 174, 177, 173} then {182, 177, 173} is
a losing streak. At the end of the boot camp, the person who has the longest weight-losing streak wins a
special prize.
We must devise an algorithm that computes the longest losing streak for each participant and declares
a winner.
(a) Can this problem be solved using dynamic programming? Justify your answer.
(b) State the technical problem formally (i.e. remove the context and state the computational problem).
2
(c) Provide an algorithm to solve the general version of this problem (i.e. report the longest losing streak
for the winner and the weeks that it occurred in) in O(mn2
) time or better, where m is the number
of participants, and the program is n weeks long. Your answer may be in pseudo-code. If it is not,
you must state it in a precise sequence of steps. You do not have to prove its running time.
3