Homework I Solution



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 [ai; bi] 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 a1; : : : ; an, a 132-pattern is a subsequence ai; aj; ak such that i < j < k and ai < ak < aj. For example: the sequence 31; 24; 15; 22; 33; 4; 18; 5; 3; 26 has several 132-patterns including 15, 33, 18 among others. Design an algorithm that takes as input a list of n numbers and checks whether there is a 132-pattern in the list.

Problem 5: Toeplitz matrices

A Toeplitz matrix is an n n matrix A = (aij) such that aij = ai 1;j 1 for i = 2; 3; : : : ; n and j = 2; 3; : : : ; n.

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

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

  1. 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).

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