CS 124 Data Structures and Algorithms — Spring 2018
Problem Set 2
Due: 11:59pm, Wednesday, February 14th
See homework submission instructions at
http://sites.fas.harvard.edu/~cs124/cs124/problem_sets.html
Problem 4 is worth 40% of this problem set, and problems 1-3 constitute the
remaining 60%.
For each problem where you are asked to give an algorithm, more points are given for
asymptotically faster algorithms. In judging the number of points to award a correct solution,
we only consider the running time in asymptotic notation, i.e. a writeup of an algorithm
taking 1000n2 steps versus one taking .01n2 steps would receive the same number of points
— both would be simply treated as Θ(n2)-time solutions.
1 Problem 1
A min-ordered binary heap stores keyed items in a rooted tree in which each node has two
children and all leaves are all roughly at the same depth (if n, the number of items being
stored, is not of the form 2k − 1, then some leaves will be one level shallower than othres).
The min-ordered property says that if u is a parent of v, then the key of the item in node u
is at most that of node v.
Suppose we instead use a min-ordered b-ary heap, which is similar to the above except
that each internal node in the tree now has b children instead of 2 (except for possibly one
internal node, since n may not be of the form 1 + b + b2 + . . . + bk for some k.
(a) (7 points) Describe how you would modify the implementation of DecreaseKey, Insert,
and DeleteMin from binary heaps to work for b-ary heaps.
(b) (3 points) How would you choose b to optimize the running time of Dijkstra’s algorithm
when using a b-ary heap (getting the right answer up to a constant factor is sufficient)?
2 Problem 2
You are given an n × n pixelated image, where each pixel is 1mm × 1mm. Some pixels are
black and others are white. White pixels should be considered as empty. If two black pixels
are adjacent (where each pixel p has eight adjacent pixels, i.e. above, below, to the right, to
the left, and diagonal from it in all four diagonal directions), then we say those two pixels
are part of the same object. Being part of the same object is transitive: if black pixels a
and b are part of the same object and b and c are, then a and c are as well. The perimeter
Figure 1: Example pixelated image containing only one object, with perimeter 16. The edges
on the perimeter are highlighted in red.
of an object is the sum of side lengths of pixels in that object such that either the pixel side
is on the boundary of the image, or on one side a black pixel, and on the other side is a
white pixel.
Describe an algorithm which, given the description of a pixelated image stating which
pixels are black and white, outputs the number of objects, and for each object outputs its
perimeter. Hint: to identify the objects in the image, construct an appropriate graph based
on the input image, and run one of the algorithms from class on it.
3 Problem 3
You are Blink, the protagonist in the game Legend of Griselda. You live on an M ×N two-
dimensional grid, where each grid cell is labeled with a pair (x, y) ∈ {1, . . . ,M}×{1, . . . , N}.
You are trying to reach position (M,N), where a certain dragon lives that you must defeat.
Your weapon of choice is a bow and arrow, and you plan to shoot the dragon upon arrival
in his grid cell. You start at cell (1, 1). For each of the problem parts below, when you are
asked to give an algorithm, you should also analyze its running time.
(a) (2 points) Suppose that some grid cells are open fields you can walk through, but
others are mountainous terrain that are impassable. The cells (1, 1) and (M,N) are
open fields. At each step you can walk in one of the four cardinal directions: up, down,
left, and right, though not into impassable cells. Describe an algorithm to find the
shortest time to reach the dragon. If impossible, your algorithm should say so.
(b) (3 points) You need to eat, and suppose that some cells with open fields have edible
plants to sustain you, but others don’t. You start the game with a “life counter” of 5
lives, and every time you walk through an open field that happens to be a desert, you
go hungry a bit and lose some of your vitality, causing your life counter to decrease by
1. (There’s nothing you can ever do later to make it increase again.) You need to make
sure that you have at least 1 life counter when reaching the dragon. Now describe an
algorithm to reach the dragon in the shortest time with at least 1 life counter left. If
impossible, your algorithm should say so. You are promised that neither cell (1, 1) nor
2
cell (M,N) is a desert. Hint: how can you modify your world representation from
part (a) to take into consideration your five lives?
4 Programming Problem
Solve ESCAPE on the programming server (https://cs124.seas.harvard.edu).
3