Both pictures are from the same question. Please help with explanation thank you!

(103. You have been hired by Western Wells - a water well company - to find a water source for the city of Saskatoon. The company has plotted out a 1-by-n grid in which it knows exactly one grid contains an underground stream that is suitable. You however have also minored in Such an algorithm actually exists. It is called the Bellman-Held-Karp algorithm. It is based on dynamic programming which we will cover later in the term. hydrology and will be able to determine, if when a pilot hole does not find the water source. to which end of the grid the source is. One approach is to use binary search - drill in the grid at position n/2 and recursively drill at n/4 or 3n/4 if needed, and repeat. U (a) In the worst-case, how many holes will need to be drilled? Before commencing operations you are told the following: if a hole is drilled to the right of the actual source, the drill bit will break due to the geology of the area but drilling to the left of the source will not break the bit and thus can be reused. (That is, if the true location of the source is at location i, drilling at any location j>i will break the bit but at any location j i will not.) (1) (b) Suppose you have only one drill bit. Describe an algorithm that is guaranteed to find the source. Compare the runtime of your algorithm to that of the binary search algorithm - which one would you expect to be faster in the worst-case? [6] (c) The city's water department is only able to acquire two drill bits for you to use. Further the city's conservation department will not allow you to drill holes. Describe an algorithm that will find the water source that will drill at most f(n) holes where f(n) o(n). (E.g. f(n) = n/2 is not acceptable.) 2) (d) What is the runtime of your algorithm? Asymptotically, how many holes will it dig in the worst-case