Design and Analysis of Algorithms

Let ๐‘‹[1: ๐‘›] be an array of real numbers, and ๐‘™ a fixed positive integer โ‰ค ๐‘›. An ๐‘™-subarray of ๐‘‹ is
any sequence of ๐‘™ consecutive elements of the array ๐‘‹. The trough of an ๐‘™-subarray is the
minimum value in that ๐‘™-subarray. Give a divide-and-conquer algorithm that takes as input an
array ๐‘‹[1: ๐‘›] and a positive integer ๐‘™ โ‰ค ๐‘›, and returns the starting position of the ๐‘™-subarray that
has the largest trough. Analyze the time complexity of your algorithm in terms of ๐‘› and ๐‘™. (Your
algorithm should split the input into two halves)
2. In a given undirected graph G, an independent set of G is any subset S of nodes in G such
that there are no edges between the nodes of S. The independent set problem is the problem
of finding a maximum-size independent set in an input undirected graph G. Give a greedy
algorithm for this problem, and prove by a counter example that the Greedy solution is not
always optimal.
3. In a given undirected graph G, a vertex cover of G is any subset C of nodes in G such that
every edge in G involves at least one node in C. The vertex cover problem is the problem of
finding a minimum-size vertex cover in an input undirected graph G. Give a greedy
algorithm for this problem, and prove that the Greedy solution is not always optimal