Question 1 (10 marks) For each of the following problems indicate which algorithmic approach (Greedy Divide-and-conquer, Dynamic programming, Max-flow) you would use to at- tempt to solve the problem. You do not have to give an algorithm. (a) In an nxn array, a peak is an element that is greater than its four neighbours (left, right, top and bottom). Peaks can also lie on edges or corners, they are greater than their three or two (respectively) neighbours. There can be more than one peak in an array. Come up with an algorithm that efficiently finds a peak in an n x n array. (b) A computer network is a graph where the vertices are computers and the (undirected) edges indicate a physical network link between two computers. A computer sends a message to another computer on the network by passing it along the network links until it reaches its destination. Find an algorithm that can determine if an eavesdropper that has the ability to monitor mes- sages on up to k network links can intercept every message sent from s to (e) You are in charge of assigning planes to gatdk at an airport. After a plane lands, it needs to be assigned to a gate, where it must remain until it takes off. Given a list of plane arrival and departure times, come up with an algorithm that assigns planes to gates in an efficient manner. (d) Your small town has grown large enough that it has to be divided into suburbs to efficiently allocate resources (e.g. electricity, water, school zones). Come up with an algorithm that assigns households into five "geographically close" suburbs - i.e. divide houses into five groups so that the minimum distance between houses in different suburbs is maximized. (e) Come up with an algorithm for determining how many ways you can make a total t by summing k numbers (possibly repeated) from a set S