• Suppose we wish to multiply four matrices of real numbers
M1 x M2 x M3 x M4 where

M1 is 10 by 20,
M2 is 20 by 50,
M3 is 50 by 1, and
M4 is 1 by 100.

Assume that the multiplication of a p x q matrix by a q x r matrix
requires pqr scalar operations, as it does in the usual matrix multiplication
algorithm.

Find the optimal order in which to multiply the matrices so as
to minimize the total number of scalar operations.

How would you find this optimal ordering if there are an
arbitrary number of matrices?

• Describe a (n log2 n) time algorithm that, given a set S of n real numbers
and another real number x, determines whether or not there exist two
elements in S whose sum is exactly x.

• Given an array of n numbers a, a,..., a[n], find the
second minimum number in n + log n comparisons. You can only
compare elements. You can't assume anything about the range of values
of the numbers.

• An element in a sorted array can be found in O(log n) time via binary
search. But suppose I rotate the sorted array at some pivot unknown to you
beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise
a way to find an element in the rotated array in O(log n) time.

• Write a program that will display a "spiral" of NxN numbers, using
constant space (no arrays allowed). For example, here's what the spiral
looks like for N=10:

99    98    97    96    95    94    93    92    91    90
64    63    62    61    60    59    58    57    56    89
65    36    35    34    33    32    31    30    55    88
66    37    16    15    14    13    12    29    54    87
67    38    17     4     3     2    11    28    53    86
68    39    18     5     0     1    10    27    52    85
69    40    19     6     7     8     9    26    51    84
70    41    20    21    22    23    24    25    50    83
71    42    43    44    45    46    47    48    49    82
72    73    74    75    76    77    78    79    80    81

For N = 2
3 2
0 1

For N=3
8 7 6
1 0 5
2 3 4

For N=4
15 14 13 12
4  3  2 11
5  0  1 10
6  7  8  9