Algorithm analysis - Data Structures and Problem Solving Using Java - page 224

A majority element in an array A of size N is an element that appears
more than times (thus there is at most one such element). For
example, the array
3, 3, 4, 2, 4, 4, 2, 4, 4
has a majority element (4), whereas the array
3, 3, 4, 2, 4, 4, 2, 4
does not. Give an algorithm to find a majority element if one exists, or
reports that one does not. What is the running time of your algorithm?
( Hint : There is an

5.33

N ⁄ 2

O ( N ) solution.)

The input is an N × N matrix of numbers that is already in memory.
Each individual row is increasing from left to right. Each individual
column is increasing from top to bottom. Give an

5.34

O ( N ) worst-case

algorithm that decides if a number X is in the matrix.

Design efficient algorithms that take an array of positive numbers a ,
and determine
a.

5.35

The maximum value of a[j]+a[i] , for j ≥

≥
≥
≥

i

b. The maximum value of a[j]-a[i] , for j

i

c. The maximum value of a[j]*a[i] , for j

i

d. The maximum value of a[j]/a[i] , for j

i

Suppose that when the capacity of an ArrayList is increased, it is
always doubled. If an ArrayList stores N items, and started with an
initial capacity of 1, what is the maximum number of times that an
ArrayList 's capacity could have been increased?

5.36

The ArrayList class in java.util always increases the capacity by
50%. What is the maximum number of times that its capacity can be
increased?

5.37

The ArrayList class contains a trim method that resizes the internal
array to exactly the capacity. The trim method is intended to be used
after all the items have been added the ArrayList , in order to avoid
wasting space. Suppose, however, the novice programmer invokes
trim after each add . In that case, what is the running time of building
an N -item ArrayList ? Write a program that performs 100,000 adds to
an ArrayList and illustrates the novice's error.

5.38

Because a String is immutable, a String concatenation of the form
str1+=str2 takes time that is proportional to the length of the resulting
string, even if str2 is very short. What is the running time of the code
in Figure 5.15, assuming that the array has N items?

5.39