# 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