Q4 Algorithm Design 10 Points Marty McFly is working as a paper boy in Hill Valley, a small town containing 100 houses or so connected by roads. Everyday, he delivers newspapers to every house in the town. Since he rides his skateboard during the delivery, he can carry one newspaper at a time. Hence, after each delivery, he has to come back to the newsstand to pick up another delivery. Last week, the temperatures fell sharply and a storm hit Hill Valley, leaving 100 cm of snow on all the roads in the town. To deliver the newspapers, Marty McFly needs to clear snow on the roads, which, of course, cost him a lot of work and money. He decides that instead of clearing snow from all the roads on his delivery routes at once, he will clear the snow while delivering the newspapers. (a) (5 pts) Marty McFly knows he will get an order for each one of the houses as they are all regular customers. That's why he would like to plan in advance which roads he is going to clear. How should he choose which roads to use so that he minimize the overall cost? Briefly describe the most appropriate algorithm for this task and state its running time complexity. Enter your answer here (b) (5 pts) Under these circumstances, how should Marty McFly determine what roads to take to deliver the newspaper to the house that the new order comes in? Briefly describe the most appropriate algorithm for this task and state its running time complexity. Enter your answer here