本次代写主要为数据结构算法的assignment

Problem 1. (10 points)

We are given a rooted tree T = (V, E) and its root u, i.e., a simple connected undi-

rected acyclic graph and a vertex u of this tree that we consider to be its root. We

want to compute the smallest set of vertices S V such that every edge in E is

incident to some vertex in S.

Example:

u v w x

Vertex u is the root of the above tree. If we choose S = fvg, we indeed have the

property that every edge is incident to a vertex in S. Furthermore, there’s no smaller

set with this property. Picking S = fu,w, xg would also yield a set where every edge

is incident to a vertex in S, but it isn’t the smallest set. Picking S = fu,wg would

mean that edge (v, x) isn’t incident to any vertex in S.

We are given two algorithms for this problem:

degreeAlgorithm sorts the vertices of T by their degree and adds a vertex to S

if it’s incident to some edge that isn’t incident to any vertex in S.

BFSAlgorithm runs a breadth ﬁrst search from the root u. Then it compares the

size of the union of all vertices in even layers to the size of the union of all vertices

in odd layers and returns the smaller of the two sets.

1: function degreeAlgorithm(M)

2: S Æ

3: Sort vertices in T by their degree and rename such that deg(v1) deg(v2)

… deg(vn)

4: for each vi in T do

5: if vi is incident to some edge e

6: and e isn’t incident to any vertex in S then

7: S S [ fvig

8: return S

1: function BFSAlgorithm(T, u)

2: layers, parent BFS(T, u)

3: even the union of all vertices in layers[i], where i is even

4: odd the union of all vertices in layers[i], where i is odd

5: if jevenj < joddj then

6: return even

7: else

8: return odd

Argue whether degreeAlgorithm always returns the correct answer by either

arguing its correctness (if you think it’s correct) or by providing a counterex-

ample (if you think it’s incorrect).

a)

Argue whether BFSAlgorithm always returns the correct answer by either

arguing its correctness (if you think it’s correct) or by providing a counterex-

ample (if you think it’s incorrect).

b)

Problem 2. (25 points)

Our publishing company has accepted contracts to publish a set of n books B. For

each book bi (0 i < n) we know the number of copies ci that we agreed to

print, the time pi that printing a single copy of this book takes, and the deadline

di by which all copies of the book should be printed. All ci, pi, and di are positive

integers. We can start printing at time 0 and all deadlines are given relative to this,

i.e., if di = x this means that printing all copies of book bi should be completed by

time x.

As we’re a small printing company, we only have a single printing press, so we

can only work on printing one book at a time. We’re allowed to change which book

we’re printing after we completed a full copy (i.e., we can’t switch halfway into

printing a book). We’re worried that we agreed to publish too much and you’ve

been hired to develop an algorithm to decide if this is indeed the case (and we

might need to start apologising to our clients). In other words, you need to design

an algorithm that returns true if there is an order to print the copies of the books

such that all deadlines are met, and false otherwise.

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

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

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

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