Objectives

To improve your understanding of the time complexity of algorithms and recurrence relations. To develop problem-solving and design skills. To improve written communication skills; in particular the ability to present algorithms clearly, precisely and unambiguously.

Problems

1.  [10 marks]

Alex loves skiing and, in order to keep gaining speed, they prefer to always ski downwards. Alex collected the measured altitude of an area that they plan to go next month, represented using an array of size n by n. An example with n = 4 is given below:

Alex can start skiing from any cell and move to an adjacent cell on the right, left, up or down (no diagonals), anytime as needed. They will always ski towards an adjacent cell with a strictly lower altitude. In the above example, one possible skiing path is 50 −23 − 15 − 12 −4. Of course, 50 − 33 − 28 − 23 − 15 − 12 − 4 is another one, and in fact the longest possible one.

(a) Write a function LongestSkiingPath(M[0..n − 1][0..n − 1]) in pseudocode, which takes

a 2-D array representing for the measured altitude of an area as input and calculates the number of cells involved in the longest path, using Dynamic Programming.  Using the above example, your algorithm should return 7.

(b) What’s the time complexity of your algorithm? Briefly justify your answer.   Note: Partial marks will be awarded to working but less efficient implementations.

2.  [15 marks]

Drug discovery is a costly and time consuming process that usually involves experimentally testing molecules (drug candidates) in a wet-lab in order to assess their efficacy. More than often, combinations of molecules could lead to better efficacy.

The intuition behind using combination of molecules is that, if a molecule A has good efficacy, and another molecule B also does, one might expect them to be as good or better together than individually (even though this might not always hold).

Additionally, the number of possible combinations of molecules grows quite quickly with the number of molecules (and testing molecules costs a lot of money!), meaning we need to be clever while designing ways to evaluate sets of molecules.

This process involves automation of the wet-lab tests and you have been assigned with the task of defining a strategy to optimise combinations of molecules against their antiviral effect.

You receive a very long list of n molecules as input and is also given access to the automa- tion robot that will do the wet-lab tests, through a programming interface, via the function test wet lab robot(mol[1...k]). It receives a list of one or more molecules as input and returns a positive number denoting the efficacy of the molecule(s) (the larger this value, the better!).

Your job is to develop algorithms that optimises molecule efficacy, given a set of molecules, using the robot as little as possible.

(a) Describe with your own words (and in pseudocode) two different greedy approaches to

optimise the combination of molecules, one with linear time complexity (O(n)) and the other with quadratic time complexity (O(n2 )), where n is the number of input molecules. Remember that the most costly operation is the function test wet lab robot.

(b) Do any of your approaches always find the optimal solution?  (e.g., does this problem

have optimal substructure?) Briefly justify.

3.  [5 marks]

You are a hacker that recently got hired by a cybersecurity company.  The team needs to be preemptive against any adversarial attacks.  Your role is to develop such attacks so the defense team can prepare mechanisms to avoid them.

In this problem, you were able to inject code into the algorithm for inserting an element into a Binary Search Tree.  Your goal is to force the BST to always degrade to a  “stick” (to the right), or more specifically, a linked list.  The algorithm to insert an element into the BST is as follows.

function BSTInsert(root, new)

if new .value < root.value then

if root.left = NULL then

root.left ← new

Stickify(new , root)

else

BSTInsert(root.left, new)

if new .value > root.value then

if root.right = NULL then

root.right ← new

Stickify(new , root)

else

BSTInsert(root.right, new)

Here root and new are nodes with fields left and right (which are pointers to other nodes) and a field value. If the BST is already a “right stick”, then running the BSTInsert algo- rithm (with your Stickify function) should always leave the tree as a “right stick”.

For example if we start with the tree on the left and insert 2 we will get the tree in the middle. After Stickify is run, we should get the tree on the right.

Your task is to write the pseudocode for the algorithm Stickify which takes the newly inserted node along with its parent and performs any necessary rotations to ensure the tree remains a “right stick”. You may use RotateRight(node) and RotateLeft(node) without implementing these functions. In the above example, the RotateRight(3) should be called.