1) Chapter 3 – Programming Problem 5 (Page 195) Write the solution to this problem and then show a box trace of your algorithm when looking for the 3rd smallest item in the following array: { 14, 5, 21, 17, 6, 2, 22, 15, 7, 13}. Your recursive algorithm should not alter the original array. (10 marks for program & 10 marks for box trace) 2) You just won the lottery – but the prize is paid in a very peculiar way. For the first week, you will receive one cent. For week 2, you will receive 2 cents; 4 cents for week 3; 8 cents for week 4 – and the amount received keeps doubling every week until the end of the year. So at the end of week one, you will have been paid 1 cent; at the end of week two, 3 cents (2 + 1 cents); at the end of week three, the total will be 7 cents (4 + 3 + 1) and so on. Write a program that implements two recursive methods: one that given the week number, it will report the amount to be received for that week (i.e. week 10 pays $5.12); and second method that reports the total amount received to date given the week number (i.e. by the end of week 8, $2.55 has received in total) . The program should repeatedly ask the user to indicate the number of weeks and report the results of the two recursive methods. If the user enters 0 weeks, the program will terminate. 20 marks.