# 算法代写 | Comp2123 Assignment 5

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.

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