Problem 1. (10 marks) The problems here are about using induction to prove the correctness of recur- sively defined algorithms. Refer to "week 02 slides" on eClass. a. (5 marks) Example #3 describes a solution to the problem of a person climbing a staircase of n stair. Now we change the problem to: Each step she takes can be either a regular-size step that climbs 1 stair or a big-size step that climbs 2 stairs, or a super-size step that climbs 3 stairs; the question is in how many different ways can she climbs the while set of n steps. Give an algorithm (in pseudocode) and prove its correctness. b. (5 marks) In Example #4, an algorithm is provided for the problem of Towers of Hanoi. Prove by induction that the algorithm is correct. Note: You must clearly label the base case and the induction step in your proof. You must justify your reasoning steps, in particular, how induction hypothesis is applied. Problem 1. (10 marks) The problems here are about using induction to prove the correctness of recur- sively defined algorithms. Refer to "week 02 slides" on eClass. a. (5 marks) Example #3 describes a solution to the problem of a person climbing a staircase of n stair. Now we change the problem to: Each step she takes can be either a regular-size step that climbs 1 stair or a big-size step that climbs 2 stairs, or a super-size step that climbs 3 stairs; the question is in how many different ways can she climbs the while set of n steps. Give an algorithm (in pseudocode) and prove its correctness. b. (5 marks) In Example #4, an algorithm is provided for the problem of Towers of Hanoi. Prove by induction that the algorithm is correct. Note: You must clearly label the base case and the induction step in your proof. You must justify your reasoning steps, in particular, how induction hypothesis is applied