Homework 3 Shortest Snowboarding

CS 341: Algorithms 
Homework 3
You are allowed to discuss with others but are not allowed to use any references other than the course
notes and the three reference books. Please list your collaborators for each question. You must write your
own solutions. See the course outline for the homework policy.
The full mark is 50. This homework is counted 10% of the course grade.
1. Programming Problem: Shortest Snowboarding Course (20 marks)
It is only the beginning of summer, but Alice already misses winter so much. Knowing that, Bob gives
Alice the following problem that is purportedly related to snowboarding.
Let’s model the mountain range as a grid, with pistes represented as H horizontal lines and V vertical
lines. The lines form H × V intersections. We use coordinates (i, j) to denote the point of intersection
of the i-th horizontal line (counting from top to bottom) with the j-th vertical line (counting from left
to right).
We want to design a snowboarding course. The starting point is (1, 1) and the ending point is (H, V ).
At each point you are only allowed to go right or go downwards. That means, at (i, j) you can only
go to (i + 1, j) or (i, j + 1). The time needed to travel from (i, j) to (i + 1, j) is denoted as Di,j . The
time needed to travel from (i, j) to (i, j + 1) is denoted as Ri,j . One cannot go right at (i, j) in case
j = V , so in this case Ri,j is undefined. Similarly, if i = H, then Di,j is undefined. In all other cases,
Di,j and Ri,j are defined and have positive integer value.
Let’s call a horizontal (resp. vertical) section any segment connecting a point (i, j) to point (i, j + 1)
(resp. (i + 1, j)). When one is near the end of the current section ready to turn into a perpendicular
section, one needs to decelerate, make the turn, and accelerate again. This takes extra time. In this
problem, we model the effect of turning as follows: if a section is either immediately preceded or
immediately succeeded by a section with perpendicular direction, its travel time is double that given
by Di,j or Ri,j . Otherwise, its travel time is unaffected.
Our task is to find a snowboarding course from (1, 1) to (H, V ) that takes the least amount of time.
Input: The first line of input contains H and V . H lines follow. The i-th of these lines contains
2V integers Ri,1, Di,1, Ri,2, Di,2, . . . , Ri,V , Di,V . If Di,j or Ri,j is undefined, the corresponding entry is
replaced by a −1.
It is guaranteed that 2 ≤ H, V ≤ 500, and all defined Di,j and Ri,j are positive and at most 100.
Output: On the first line, output the time needed to finish the shortest snowboarding course. On the
next H + V − 1 lines, output the points that the course will pass through in order, starting from (1, 1)
and ending at (H, V ). Output i j for the point (i, j).
In case there are multiple optimal solutions, any one of them will be accepted.
Sample Input 1:
2 4
3 10 5 3 3 3 -1 3
3 -1 3 -1 3 -1 -1 -1
1
Sample Output 1:
20
1 1
1 2
1 3
1 4
2 4
Explanation: The figure below shows the grid along with the travel time of each section. The
optimal path, highlighted in green, takes time 3 + 5 + 3 × 2 + 3 × 2 = 20. Note that the path
(1, 1) → (1, 2) → (2, 2) → (2, 3) → (2, 4) has a smaller sum of values, but after taking into account the
effect of turning, it takes a longer time (3 × 2 + 3 × 2 + 3 × 2 + 3 = 21).
Here are some additional sample inputs (the optimal paths are unique in each case):
Sample Input 2:
2 3
1 2 100 1 -1 100
2 -1 100 -1 -1 -1
Sample Output 2:
108
1 1
2 1
2 2
2 3
Sample Input 3:
3 3
2 1 100 2 -1 100
1 100 100 20 -1 100
100 -1 1 -1 -1 -1
Sample Output 3:
46
1 1
2 1
2 2
3 2
3 3
2
2. Written Problem: Meeting the Deadlines (10 marks)
It is the midterm period again. You have taken many courses, with assignments and exams lining up.
You also have other commitments and would like to find a schedule that allows you to meet all the
deadlines. We model this scheduling problem as follows.
We are given n jobs, each with a release time ri ∈ Z+, a deadline di ∈ Z+ and a processing time
pi ∈ Z+. Our task is to output a feasible schedule to finish the jobs so that all the deadlines are
met, or determine that such a schedule does not exist. A schedule is a set of disjoint time intervals
[s1, f1], [s2, f2], . . . , [sk, fk] (with s1 < f1 ≤ s2 < f2 ≤ . . . ≤ sk < fk), along with the associated jobs
j1, j2, . . . , jk ∈ {1, . . . , n} in each time interval such that we process job jt during interval [st, ft]. Note
that a job i can be processed in different time intervals (i.e. we do not have to finish a job in one time
interval), but in each time unit we can only process one job. Given a schedule, let Ti
:= {t | jt = i}
be the set of time intervals that are scheduled to process job i. A schedule is feasible if the following
conditions hold for every job 1 ≤ i ≤ n:
(a) ri ≤ st for each time interval t ∈ Ti
, i.e. we can only process job i after it is released in time ri
;
(b) ft ≤ di for each time interval t ∈ Ti
, i.e. we can only process job i before its deadline in time di
;
(c) P
t∈Ti
(ft −st) ≥ pi
, i.e. the total length of the intervals assigned to job i is at least its processing
time pi
.
Here is an example with n = 3 jobs, and a corresponding feasible schedule:
i ri di pi Intervals for job i
1 0 8 5 [0, 3], [4, 5], [6, 7]
2 3 6 2 [3, 4], [5, 6]
3 6 9 2 [7, 9]
Design the fastest algorithm that you can for the problem of outputting a feasible schedule or determining that a feasible schedule does not exist. You must prove the correctness and analyze the time
complexity of your algorithm.
3. Written Problem: Sketching Data (10 marks)
One of the major ways of dealing with big data sets is sketching: the approximation of the data set
by a smaller but approximately similar object. In this problem, we will see a way of sketching a
two-dimensional plot. The input consists of a set of points (x1, y1), . . . ,(xn, yn), where each xi and yi
is a real number. You may assume that all of the xi are distinct, and that they are in order so that
x1 < x2 < · · · < xn.
We will approximate this plot by a piece-wise constant function, that we call a sketch. You can
see an example of a sketch in Figure 1 below. A sketch is specified by a partition of the data into
consecutive intervals along with a value for each interval. That is, we will partition {1, . . . , n} into
consecutive intervals. As one interval will start right after another ends, it suffices to specify the
first index in each interval. A partition with k intervals should be specified by their starting indices,
1 = s1 < s2 < . . . < sk ≤ n. The end index of interval j will then be fj = sj+1 − 1 if j < k and fj = n
if j = k.
We then need to specify the height of the sketch in each interval. For the jth interval, we then
approximate the points (xi
, yi) for sj ≤ i ≤ fj by a horizontal line segment of height hj . So, a sketch
is fully specified by s2, . . . , sk and h1, . . . , hk. If we use more partitions in our sketch, we can represent
the data better.
3
Figure 1: A sketch of n = 8 data points. It has 3 segments. The red lines represent the error in the
approximation of every point. Note that this is not the best sketch of these points.
We now define the error of a sketch to be the maximum error that it makes at any point:
max
1≤j≤k
max
i:sj≤i≤fj
|hj − yi
|.
Design the fastest algorithm that you can for the following problem: given the points as input and an
error tolerance ?, find a sketch of error at most ? that uses as few segments as possible. This is, you
must minimize k, and make sure that for every j and every sj ≤ i ≤ fj , |hj − yi
| ≤ ?. You must prove
the correctness and analyze the time complexity of your algorithm.
4. Written Problem: Verifying Shortest Path Tree (10 marks)
The shortest paths problem arises in many applications. For this reason, people spend a lot of time
optimizing code for it. It sometimes happens that the fastest code is sometimes wrong. Or perhaps the
fastest code is based on a randomized algorithm that may make mistake with a certain low probability.
If we want to run the fastest code, then we should check that its output is correct. If it is not correct
for some input, then we could run a slower, reliable routine. This will still be a net gain on average if
we can quickly check the correctness of the code.
Imagine that you have been given a fast but untrustworthy piece of code for computing shortest path
trees. That is, the code takes as input a directed graph G = (V, E), edge lengths l, and a start vertex s.
It returns a tree that is supposed to be a shortest path tree from s. Your job is to design an algorithm
that checks if the tree really is a shortest path tree. Your algorithm should run in time O(n + m). It
should output “yes” for all shortest path trees, and “no” for all trees that are not shortest path trees.
Your algorithm is given access to G, l, s and the tree. You must prove the correctness and analyze the
time complexity of your algorithm.
4