Problem 2. (15p) Your boss has given you an assignment: to devise the fastest algorithm yoiu can for solving a particular problem whose input is an array A with n elements. After thinking for a while you came up with few alternatives. Which alternative do you prefer and why? Explain by showing the efficiency class of each algorithm Algorithm 1 Iterate over each element in A and do at most 3 operations per element Algorithm 2 For inputs of size n>l: 1. Recurse on the first half of the input 2. Recurse on the second half of the input 3. Make two operations Algorithm 3 For inputs A of size n> 1: 1. Recurse on an instance of size n- 1 2. Iterates over the size of A and makes at most one operation per element Problem 3. (20p) von Neumann's neighborhood: How many one-by-one squares are generated by the algorithm that starts with a single square (level n = 0) and adds new squares all round the outside level by level. The results for n = 0,1,2 are illustrated below in Figure 1, (in the parlance of cellular automata theory, the answer is the number of cells in the von Neumann neighborhood of range rn How many one-by-one squares are generated (from 0 to nth level) by an: (a) iterative algorithm (b) recursive algorithm Write the formulas in each case. Which one is more efficient ? Motivate your answers by showing the efficiency class for each case Figure 1: Illustration of von Neumann's neighborhood for levels n = 0,1,2