program anaylsis

1. Consider the following algorithm. AverageAbove(A, k) : Inputs: a sequence A = (a1, . . . , an) of reals, a real k Output: the average of those values in A that are ≥ k (1) (total, count) ← Total&CountAbove(A, k, n) (2) return total ÷ count (a) Give the pseudocode for the algorithm Total&CountAbove that is used in line (1) of AverageAbove. *** It is essential that the algorithm you give is recursive. *** Your algorithm should not contain any loops. Here is the specification of Total&CountAbove: Total&CountAbove(A, k, i) : Inputs: a sequence A = (a1, . . . , an) of reals, a real k, an integer i, where 0 ≤ i ≤ n Output: a pair consisting of the sum of values in (a1, . . . , ai) that are ≥ k, the number of values in (a1, . . . , ai) that are ≥ k Note that, i, the third parameter of Total&CountAbove is needed to record which part of the sequence A is being considered in a given recursive call. Also, note that when i = 0, it is the empty subsequence of A that is being considered. 2. Last month, you had a chat with your friend Amy at a party. She mentioned that she had recently taken over as one of the trustees of a charity. As someone who enjoys programming, she has volunteered to set up a database containing the details of the several thousand people who are registered as so-called ‘friends’. You talked to her about some of the exciting things that you were learning in your Program Analysis module, and offered to help. Yesterday, Amy called and explained that she had managed to track down a file on the charity’s ageing computer that contains data that the charity has about the names and addresses of its friends. Amy’s problem, and the reason she has called you, is that she hasn’t been able to work out how to write code that will extract anything useful from the file. For some strange reason, the file doesn’t contain any non-alphanumeric characters (i.e. the file has absolutely no punctuation or whitespace characters, just containing letters and digits) and is entirely lowercase. Without anything that marks the end of one word (or token) and the start of another, Amy hasn’t been able to figure out any way of splitting up the contents so that she can extract the information she wants from the file. Here is the start of the file: “jonathanpsmiththegablesturnersgreensussexjorice5westst...” The particular thing that she wants your help with is the problem of separating out each of the tokens (words, numbers, abbreviations, etc). She is confident that once that has been done she can deal with working out how to distinguish the names from the addresses and then populate the database. Luckily, you were able to help her. You started to tell her how she can use Dynamic Programming to solve the problem, but you could see that she was having difficultly understanding what you were getting at. As a result, you both agreed that the best way forward was for you to send her an email explaining in detail the way that the problem can be approached. Since she wants to write all of the code herself, and was keen to learn how these kinds of problems can be solved, you agree that you would explain what is needed in words, and would describe the algorithm in pseudocode. Compose the email that you would send to Amy. Don’t forget that she has a degree in Maths, so it is fine to present things formally.