Question 1 (20%) Using induction on n, specify an algorithm to get them all across the bridge in the shortest possible time. State explicitly what is the base case and what is the induction hypothesis. (Hint: if you count the number of return trips, you will observe that there are at least two people that never return. Which people should never return? Also, the solution for four people discussed in the lecture can be used to complete the induction step). You should use the following steps in order to solve the problem: 1. State explicitly what is the base case (5%) 2. State explicitly what is the induction hypothesis (5%) 3. Show how to use the induction hypothesis to solve the inductive step (10%)