Problem 4-6 Monge arrays

Answers 

for a n x m matriz

a.

So we need to proof this:

The right implication is trivial as we can see that the left operand of the if only if is just a especial case of the monge definition. 

So to proof the left implication we assumed

and so we try to proof the monge definition by induction(fist on the rows as the hint suggested):

so we can use our assumption on k :

So using our inductive hypothesis we get:

For this to work l must be l=j+1 but when proving the same thing for the rows we then prove it for all possible k,l,j,i. 

b.

37 23 24 32 

21  6   7  10 

53 34 30 31 

32 13  9   6 

43 21 15  8

c. It can be proved by contradiction.

We make the assumption:  

being A[i,f(i)] and A[i+1,f(i+1)] the leftmost minimums, this must be false:

And so we prove it by contradiction 

d. 

This hold for all the odd rows:

So we just need to find the minimum between those bounds. 

The run time for finding all the leftmost minimums for the odd rows is given by the summation:

e.

Since each time the size is split to just the even rows and the merge step takes O(n+m), the run time
of the algorithm is given by the recurrence:

we analyse it using the recursion tree method and we can ignore the ceiling since it wont affect the asintotic behavior. The base case is O(1) since m is constant so assuming that n is a power of 2 there is lg(n) levels and each one takes m constant time so:

The code for the algorithm is:

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

int findMin(int* array, int init, int finale){ int index = 0; for (int min = INT_MAX; init < finale; ++init) { if (min > array[init]) { min = array[init]; index = init; } } return index; } void divideAndConquereMonge(int **matrizMonge, int* leftmost, int rows, int factor, int column){ if (rows == 1) leftmost[0] = findMin(matrizMonge[0], 0, column); else { int mid = static_cast<int>(std::ceil(rows / 2.0)); divideAndConquereMonge(matrizMonge, leftmost, mid, 2 * factor, column); for (int i = 1; i < rows - 1; i+= 2) { int dev = factor * i, end = leftmost[dev + factor] + 1; leftmost[dev] = findMin(matrizMonge[dev], leftmost[dev - factor], end); } if (rows % 2 == 0) { int dev = factor * (rows - 1); leftmost[dev] = findMin(matrizMonge[dev], leftmost[dev - factor], column); } } }

Rust 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

fn left_most_minimum(monge: &[i32], from: usize, to: usize) -> usize { let mut min = monge[from]; (from + 1..to).fold(from, |m,i| { if monge[i] < min { min = monge[i]; i } else { m } }) } fn minimums(monge: &[i32], leftmost: &mut Vec<usize>, rows: usize, columns: usize, factor: usize) { if rows == 1 { leftmost[0] = left_most_minimum(monge, 0, columns) % columns; } else { let mid = rows - (rows / 2); minimums(monge, leftmost, mid, columns, 2 * factor); let map = |i, j| (i * columns) + j; let x_rows = (0..) .map(|x| factor * (2 * x + 1)) .take_while(|&x| x < (rows - 1)); for row in x_rows { let (from, to) = (map(row, leftmost[row - factor]), map(row, leftmost[row + factor] + 1)); leftmost[row] = left_most_minimum(monge,from,to) % columns; } if rows % 2 == 0 { let row = factor * (rows - 1); let (from, to) = (map(row, leftmost[row - factor]), map(row, columns)); leftmost[row] = left_most_minimum(monge, from, to) % columns; } } } fn monge_left_most_minimums(monge: &[i32], rows: usize) -> Option<Vec<usize>> { let size = monge.len(); if rows == 0 || size % rows != 0 { return None; } let mut left_mosts = vec![0; rows]; minimums(&monge, &mut left_mosts, rows, size / rows, 1); Some(left_mosts) } fn main() { let row = 7; let monge = vec![ 10, 17, 13, 28, 23, 17, 22, 16, 29, 23, 24, 28, 22, 34, 24, 11, 13, 6, 17, 7, 45, 44, 32, 37, 23, 36, 33, 19, 21, 6, 75, 66, 51, 53, 34, ]; println!("{:?}", monge_left_most_minimums(&monge, row)); }