Please write it in your own word and explained as detail as possible.

(E.g. including any drawing and pseudo code)

Greedy Algorithm

Part a,

Provide a greedy algorithm for the following problem:

Selecting breakpoints:

- Road trip from Princeton to Palo Alto along fixed route.

- Refueling stations at certain points along the way.

- Fuel capacity = C

- Goal: makes as few refueling stops as possible.

Part b,

Given the following greedy algorithm, prove that it is optimal or provide a counter example.

Given a set of activities and their start and finish times, and you create a greedy algorithm that adds activities based on latest start times.

Thank you.