For each problem, provide a high-level description of your algorithm. Please make sure to include the necessary details that are crucial for its correctness and e ciency. Prove its correctness and analyze its time complexity.
Problem 1: Maximum contiguous rectangle
Use divide-and-conquer approach to write an e cient recursive algorithm that nds the maximum area contiguous subsequence in a given sequence of n nonnegative real values. Analyse your algorithm, and show the results in order notation. Can you do better? Obtain a linear-time algorithm.
The area of a contiguous subsequence is the product of the length of the subsequence and the minimum value in the subsequence.
Problem 2: Balanced Parentheses
You are given a string consisting of right ( g) and left (f) brackets. The string may or may not be balanced. You are allowed to make the following alterations to the string: change a left bracket to a right bracket or a right bracket to a left one. Balance the string with minimum number of changes.
Problem 3: Olay
Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil eld of n wells. From each well, a spur pipeline is to be connected directly to the main pipeline along a shortest path (either north or south). Given x and y coordinates of the wells, how should the professor pick the optimal location of the main pipeline (the one that minimizes the the total length of the spurs?) Show that the optimal location can be determined in linear time.
Problem 4: Maximum di erence in a matrix
Given an n n matrix M[i; j] of integers, nd the maximum value of M[c; d] M[a; b] over all choices of indexes such that both c a and d b.
Problem 5: Perfect matching in tree
Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect matching:
a set of edges that touches each node exactly once.
1
