Analysis Of Algorithms ---------------------- Questions 1 ----------- Answers to these questions will appear in "~ian/algorithms" in due course. The questions include some of the previous exam questions for the course. Starred questions are harder than you would expect in the exam. 1. Suppose we have an array of numbers a[1]...a[n] in which the first i numbers a[1]...a[i] have been sorted into ascending order, and the remaining numbers a[i+1]...a[n] have also been sorted into ascending order. The aim is to sort the entire array into ascending order. Design an algorithm which merges the two sorted lists into a second array b[1]...b[n] and copies the result back into a. Prove that the algorithm takes time O(n). Design an algorithm which does the same job using only b[1]...b[i] for temporary storage, and which also takes O(n) time. What do you think is the minimum temporary storage (as a function of n) needed to solve this problem in time O(n)? 2 Show how a boolean array b[1]...b[n] can be used to represent a set of numbers taken from 1...n. What does b contain if n=9 and the set is {1, 2, 4, 5, 7, 8, 9} ? Show that inserting a number into the set, deleting a number from the set, and testing a number for membership in the set are all O(1) operations. How long does it take to find the union of two sets or to test them for equality? (This is the representation used in most versions of pascal for "set" variables). 3 One disadvantage of the above representation is that initialising the set to be empty takes O(n) time. Find a representation in which initialisation is O(1) as well as insertion, deletion and membership testing. It can be done using a variable s giving the set size, an array a[1]...a[n] of set elements and an array b[1]...b[n] of sequence numbers. Only s needs to be initialised; a and b are assumed to contain random data initially. How long does it take to find the union of two sets represented this way, or to test them for equality? (This is the basis of "memory marking" algorithms in operating systems). 4 Consider the problem of finding the mode (most frequent item) and its frequency in a sorted array of numbers. For example 1, 3, 3, 6, 6, 6, 6, 7, 8, 8, 8, 9, 9 has mode 6 with frequency 4 since 6 occurs more times (4) than anything else. Suppose that you know the mode and frequency of a[1]...a[i-1]. Show that with only a single comparison you can tell whether the mode and frequency of a[1]...a[i] is different. Use this to design a recursive algorithm for finding the mode and frequency. Estimate the time it takes. Turn the recursive algorithm into a non-recursive one (perhaps by examining the sequence of operations performed by the recursive one). 5 The following recursive algorithm calculates the n'th Fibonacci number, i.e. the n'th number in the sequence 1, 2, 3, 5, 8, 13, ... in which each number is the sum of the previous two. Find n'th Fibonacci number F(n) ------------------------------- if n <= 2 then return n return F(n-1) + F(n-2) Show that it takes time at least O(2^(n/2)). Would you rate it as a good algorithm? Design another recursive algorithm for the problem which returns both F(n) and F(n+1), and only does one recursive call. Estimate the time it takes. How does it compare to the above algorithm? Turn this second algorithm into a non-recursive one. 6 One way to produce all the permutations of a collection of (say) n letters is to use the following rough algorithm. To permute a set of letters (e.g. CADF) --------------------------- for each letter in alphabetical order (A,C,D,F) put that letter first (say A) (recursively) permute the remaining letters (CDF) For the letters CADF this produces the permutations: ACDF, ACFD, ADCF, ADFC, AFCD, AFDC, CADF, CAFD, CDAF, CDFA, CFAD, CFDA, DACF, DAFC, DCAF, DCFA, DFAC, DFCA, FACD, FADC, FCAD, FCDA, FDAC, FDCA Assume that the letters are held in an array a[1]...a[n]. Make this algorithm more precise, using an array of markers, one for each letter, to indicate whether the letter has been considered yet. 7* Design an algorithm which will examine a particular permutation of n letters (in an array a[1]..a[n]) and will change it into the FOLLOWING permutation, (in the order of the previous question). For example if the algorithm is presented with CAFD it will swap A, F and D to produce CDAF. Prove that the algorithm takes O(1) time on average (assuming all the permutations are equally likely). Does this provide a better algorithm than the previous question?