Problem 1. Assume that each word of your machine has 60 bits. Assume that you can multiply two n-word numbers in time 4n2 with a standard algorithm. Assume that you can multiply two n-word numbers in time 11nlg3 with a "fancy" algorithm. For each part briefly justify and show your work. (a) Approximately how large does n have to be for the fancy algorithm to be better? (b) Approximately how many bits is that? Problem 2. Consider the following recurrence (for the time of some algorithm). T(n)=4T(n/5)+3n+1,T(1)=2. (a) Calculate T(25) by hand. Show your work. (b) Use the tree method to solve the recurrence exactly, assuming n is a power of 5 . For each subpart briefly justify and/or show your work when appropriate. (i) Draw the tree. You should show at least three levels at the top and at least two levels at the bottom (as done in class). (ii) What is the height of the tree? (Note that a tree with one node has height 0 , a tree with a root and some children has height 1 , etc.) (iii) How many leaves are there? (iv) What is the total work done by the leaves? (v) What is the size of each subproblem at level i ? (Note that the root is at level 0 , its children are at level 1 , etc.) (vi) How much work does each subproblem at level i (above the leaves) do? (vii) What is the total work for level i (above the leaves)? (viii) Write a summation for the total work not including the leaves? (ix) Simplify the summation. (Show your work.) (x) What is the total work for the entire algorithm