Description
1. Because of the recent droughts, N proposals have been made to dam the Murray river.
The i
th proposal asks to place a dam xi meters from the head of the river (i.e., from the
source of the river) and requires that there is not another dam within ri metres (upstream
or downstream). What is the largest number of dams that can be built? You may assume
that xi < xi+1.
2. We are given a checkerboard which has 4 rows and n columns, and has an integer written in
each square. We are also given a set of 2n pebbles, and we want to place some or all of these
on the checkerboard (each pebble can be placed on exactly one square) so as to maximize
the sum of the integers in the squares that are covered by pebbles. There is one constraint:
for a placement of pebbles to be legal, no two of them can be on horizontally or vertically
adjacent squares (diagonal adjacency is fine).
(a) Determine the number of legal patterns that can occur in any column (in isolation,
ignoring the pebbles in adjacent columns) and describe these patterns.
Call two patterns compatible if they can be placed on adjacent columns to form a legal
placement. Let us consider sub-problems consisting of the first k columns 1 ≤ k ≤ n.
Each sub-problem can be assigned a type, which is the pattern occurring in the last
column.
(b) Using the notions of compatibility and type, give an O(n)-time algorithm for computing
an optimal placement.
3. Skiers go fastest with skis whose length is about their height. Your team consists of n
members, with heights h1, h2, . . . , hn. Your team gets a delivery of m ≥ n pairs of skis, with
lengths l1, l2, . . . , lm. Your goal is to write an algorithm to assign to each skier one pair of
skis to minimize the sum of the absolute differences between the height hi of the skier and
the length of the corresponding ski he got, i.e., to minimize
X
1≤i≤n
|hi − lj(i)
|
where lj(i)
is the length of the ski assigned to the skier of height hi
.
4. You know that n+ 2 spies S, s1, s2, . . . , sn and T are communicating through certain number
of communication channels; in fact, for each i and each j you know if there is a channel
through which spy si can send a secret message to spy sj or if there is no such a channel
(i.e., you know what the graph with spies as vertices and communication channels as edges
looks like).
(a) Your task is to design an algorithm which finds the fewest number of channels which
you need to compromise (for example, by placing a listening device on that channel) so
that spy S cannot send a message to spy T through a sequence of intermediary spies
without the message being passed through at least one compromised channel.
(b) Assume now that you cannot compromise channels because they are encrypted, so the
only thing you can do is bribe some of the spies. Design an algorithm which finds the
smallest number of spies which you need to bribe so that S cannot send a message to T
without the message going through at least one of the bribed spies as an intermediary.
5. You are given a flow network G with n > 4 vertices. Besides the source s and the sink t,
you are also given two other special vertices u and v belonging to G. Describe an algorithm
which finds a cut of the smallest possible capacity among all cuts in which vertex u is at the
same side of the cut as the source s and vertex v is at the same side as sink t.
1
