1. Consider the following algorithm:

int mystery(int A[1..n]): . s = empty stack . for i = 1 to n: { . if s.empty() or s.peek()==A[i]: . s.push(A[i]) . else: . s.pop() . } . return s.pop() // returns null if the stack is empty

This algorithm computes a certain attribute of the array A, or rather, it computes what might be a certain attribute of it. The array might not have have this property, depending on what the values of its elements are. And if the algorithm returns null, then the array definitely didnt have this attribute. But heres the sort of positive guarantee that can be given about the algorithm: if A has this attribute, then the algorithm return the value of that attribute. Or put another way, whenever it returns some (non-null) number x, youre guaranteed that either x is the value of this mystery attribute of A, or A doesnt have the attribute.

(a) What mystery attribute of the array is the algorithm finding?

(b) What is the algorithms space complexity?

(c) How many bits are required to store the number n? (This should be in big-O notation as a function of n.)

(d) Modify the algorithm a little, to reduce its space complexity to O(log n).

1. Consider the following algorithm int mystery(int Al1.n]) s- empty stack for i -1 to n: if s.empty() or s.peek)--Ai s.push(Ali]) else: s.pop0) return s.pop() // returns null if the stack is empty This algorithm computes a certain attribute of the array A, or rather, it computes what might be a certain attribute of it. The array might not have have this property, depending on what the values of its elements are. And if the algorithm returns null, then the array definitely didn't have this attribute. But here's the sort of positive guarantee that can be given about the algorithm: if A has this attribute, then the algorithm return the value of that attribute. Or put another way, whenever it returns some (non-null) number x, you're guaranteed that either x is the value of this mystery attribute of A, or A doesn't have the attribute, (a) What mystery attribute of the array is the algorithm finding? (b) What is the algorithm's space complexity? (c) How many bits are required to store the number n? (This should be in big-O notation as a function of n.) (d) Modify the algorithm a little, to reduce its space complexity to O(log n). 1. Consider the following algorithm int mystery(int Al1.n]) s- empty stack for i -1 to n: if s.empty() or s.peek)--Ai s.push(Ali]) else: s.pop0) return s.pop() // returns null if the stack is empty This algorithm computes a certain attribute of the array A, or rather, it computes what might be a certain attribute of it. The array might not have have this property, depending on what the values of its elements are. And if the algorithm returns null, then the array definitely didn't have this attribute. But here's the sort of positive guarantee that can be given about the algorithm: if A has this attribute, then the algorithm return the value of that attribute. Or put another way, whenever it returns some (non-null) number x, you're guaranteed that either x is the value of this mystery attribute of A, or A doesn't have the attribute, (a) What mystery attribute of the array is the algorithm finding? (b) What is the algorithm's space complexity? (c) How many bits are required to store the number n? (This should be in big-O notation as a function of n.) (d) Modify the algorithm a little, to reduce its space complexity to O(log n)