Solve the problems below. Your answers do not have to be long, but
they should be complete, precise, concise and clear. Write the solutions on
your own and acknowledge your sources in case you used \library” material.
Look in the course web page on how to avoid plagiarism and for submis-
sion details (where/when/how). Exercises marked with (?) are usually more
challenging. NB: some of the exercises may require material that will be
covered in forthcoming lectures while others marked with (?) may involve
additional material not covered in class. It is preferred that you type your
work using your favourite software package but you submit only in pdf. At
the discretion of the TA a 10% bonus will be added if carefully typed and
rigorously explained. Two excellent and free packages are LATEX (for type-
setting mathematics) and Ipe (for drawing pictures).
1 [10 pts]
Consider networks of n nodes labeled 1; 2; : : : ; n. In each of the graphs below
describe the triple N = (V; P; p), of vertices V , vertex-port pairs P, and port
function p that define the networks.
1. Unidirectional Ring
2. Bidirectional Ring
In each case draw a picture indicating the ports at the nodes.
2 [10 pts]
This exercise is related to the colouring algorithm discussed in class. The
vertices of a linear unit disk graph G are unit length intervals (i.e., of length
1) placed in arbitrary positions on an infinite line. Two nodes (i.e., intervals)
are adjacent if they overlap. The clique number of G, denoted by !(G), is
the size of the largest number of paitwise overlapping intervals.
1. [2 pts] Apply the greedy sequential coloring algorithm discussed in
class to such an interval unit disk graph. In the pseudo-code place the
vertices in order of their left endpoint,
2. [4 pts] Give an algorithm to compute the clique number !(G).
3. [4 pts] Now assume !(G) is known. Consider the following sequential
algorithm. When a new interval I is presented whose left endpoint aI ,
it uses a color in f1; : : : ; !(G)g if the oor baIc of aI is even, and uses a
color in f!(G)+1; : : : ; 2!(G)g if the oor baIc of aI is odd. Prove that
the algorithm colors the graph correctly. What is the competitive ratio
of the algorithm? (By competitive ratio we mean the ratio achieved by
our algorithm divided by the optimal one.)
3 [10 pts]
In these two exercises we illustrate what \distributed thinking” might mean.
1. [5 pts] First we illustrate how a sequence of interactions can help to
identify a user. A man and a woman are standing in front of a shop.
\I am a man” said the one with black hair. \I am a woman”, said the
one with brown hair. If at least one of them is lying, then which one is
2. Next we illustrate why some information exchange can help you make
a decision. \Fred has more than a thousand dollars”, said Anthony.
\He does not,” said George. \He has less than that.” \Surely he has at
least one dollar,” said Henry. If only one statement is true, then how
much money does Fred have?
4 [10 pts]
Two robots are placed at arbitrary positions on the interval [L;R], where
L < R. They can move with respective constant speeds 1 and v, where
v > 1. The robots know only their own speed (and if they meet they can
compare speeds) and the initial positions of the robots are unknown to them.
1. [2 pts] Draw picture of all the possible robot congurations.
2. [8 pts] A package is placed at L. Give an optimal distributed algorithm
which delivers the package from L to R; write the pseudocode and
prove it delivers the package in optimal time. Note that the robots can
recognize L and R.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx