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[1], a[2],..., 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