1. [15pts] Trace the action of the left-to-right binary method to compute: a) x256 b) x255 c) x1023 2. [15pts] Trace the action of the algorithm EuclidGCD for the following input pairs: a) (2400,109) b) (90,245) c) (1953,109387) 3. [10pts] Trace the action of Horner's rule for 3x5+10x32x2+x+5 for x=7. 4. [20pts] To evaluate a polynomial of degree n at v and v, one could simply call HornerEval twice, involving 2n multiplications and 2n additions. Describe and analyze an algorithm that uses HornerEval and solves this problem using only n+1 multiplications and n+1 additions (or subtractions). Hint: Split the coefficient array of the polynomial into even- and odd-indexed terms. A generalization of this process is the basis of the famous Fast Fourier Transform, which we will cover later in this course. 5. a) [12ps] Consider two input lists of integers of size n. Design an efficient algorithm that tests whether or not they have at least one element in common. b) [8pts] Analyze the computing time of your algorithm (B(n) and W(n)). Hint: Sort both lists first using an efficient sorting algorithm like Mergesort (you can assume Mergesort has worst-case complexity nlog2n ). 6. a) [12ps] Design an efficient algorithm for computing the largest and second largest element in a list. b) [8pts] Analyze the computing time of your algorithm. Hint. Base your algorithm on a single-elimination tournament, where the winner is the largest element and observe that the second largest element only loses to the largest. Also observe that the number of rounds in a single elimination tournament with n players is log2n