本次加拿大代写是一个分布式计算算法相关的assignment

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).

## Assignment 1

### 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

which?

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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。