Mastery Test 1

Mastery Test 1 must be solved individually. No collaboration is allowed, and you
are not allowed to discuss the test with other students until after the oral presentations are
completed. See further the EECS Code of Honour.

The problems of Mastery Test 1 are available in the following pdf: mas1-2020.pdf Download mas1-2020.pdf

Good luck!

Clarification Feb 18th:

• Problem 3:
  Regarding "significantly better time complexity than Theta(d*n^2)".
  
  • You should think of both n and d as growing parameters.  In situations like that with several parameters it is helpful to think about a concrete relation between them, like d=n, or d=n^{^2}, and see what happens in those cases -- for instance in the case when d=n the time complexity of your algorithm should be significantly better than O(n^3).
  • As usual in the course, the time complexity refers to the worst-case complexity of the algorithm (not best-case or average-case complexity).

Clarifications Feb 17th:

• Problem 2: the algorithm only has to return the smallest possible discrepancy that can be achieved (over all possible trees).  I.e., in the example, the answer from the algorithm is "5".
• Problem 4:
  • There is no restriction on the number of cells of the input map that are on fire, it can be more than two (which is what the example shows).
  • There are no particular restrictions on how the fire is contained apart from what is explicitly stated in the problem. For instance it does not have to be contained within one single big region, but could be contained in several smaller regions if that is better (requires using less firetrucks). 

Clarifications Feb 10th:

• Problem 1: it is sufficient that your algorithm returns the maximum possible value that can be achieved (it does not have to construct a solution that achieves that value).

• Problem 2: the tree that is built must "respect" the given order of the values.  For instance if the input is (5, 0, 0, -5) you are not allowed to build your tree by first combining the first and the last items into a tree.  More formally: at every internal node, the input values appearing as leaves in the left subtree of that node must all come before the input values appearing as leaves in the right subtree.