$30.00
Description
Problem 1: Next greater element
Given an array, print the Next Greater Element (NGE) for every element. The Next Greater Element of an item x is the rst greater element to its right in the array.
Problem 2: Sorted matrix search
Given an m n matrix in which each row and column is sorted in ascending order, design an algorithm to nd an element.
Problem 3: Maximum overlap of two intervals
Design an algorithm that takes as input a list of intervals [a_{i}; b_{i}] for 1 i n and outputs the length of the maximum overlap of two distinct intervals in the list.
Problem 4: 132 pattern
Given a sequence of n distinct positive integers a_{1}; : : : ; a_{n}, a 132pattern is a subsequence a_{i}; a_{j}; a_{k} such that i < j < k and a_{i} < a_{k} < a_{j}. For example: the sequence 31; 24; 15; 22; 33; 4; 18; 5; 3; 26 has several 132patterns including 15, 33, 18 among others. Design an algorithm that takes as input a list of n numbers and checks whether there is a 132pattern in the list.
Problem 5: Toeplitz matrices
A Toeplitz matrix is an n n matrix A = (a_{ij}) such that a_{ij} = a_{i} _{1;j} _{1} for i = 2; 3; : : : ; n and j = 2; 3; : : : ; n.

Is the sum of two Toeplitz matrices necessarily Toeplitz? What about the product?

Describe how to represent a Toeplitz matrix so that two n n Toeplitz matrices can be added in O(n) time.

Give an O(n lg n)time algorithm for multiplying an n n Toeplitz matrix by a vector of length n. Use your representation from part (b).

Give an e cient algorithm for multiplying two n n Toeplitz matrices. Analyze its running time.
1