Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
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.