PART A:-

A long distance runner wants to carry only a single water bottle along the route and she can run k miles on one bottle of water. Before the race which is D miles long where D k, she is given a map of all n watering stops (i.e. mile markers of these stops). Design an effcient algorithm by completing the following function for determining where she should take a new bottle in order to make as few stops as possible. Estimate its time complexity. MinStops(A;D) Input: Array A[0..n] where A[i] is distance of i-th watering stop, D is distance of race Output: Sequence S of watering stops for the runner minimizing number of stops; use append() function to add to S.

PART B:-

A plaindrome is a nonempty string that reads the same forward and backward. Examples of palndromes are all strings of length 1 : civic and racecar. Write a dynamic programming formulation to find effciently the longest palindrome that is a subsequence of a given input string.

For example carac is the longest palindrome that is a subsequence of the string character. Based on this formulation write an algorithm to find this palindrom given an input string. Derive the time compleity of this algorithm.