Longest Common Subsequence

      Monotone Array

A. First Edition
This is one of problem in assignment of comp465 and it is regarded as a joke because professor said it is for fun.
But I spent quite a lot of time thinking about it. Actually, I made a cheap mistake before my classmates pointed 
out. My mind cannot move after one night's killing in Diablo(I) in Battle.net. It is Diablo ONE not Two!
B.The problem

A two-dimensional array a is called monotone if

a(i, j)  a(i + 1, j) and a(i, j)  a(i, j + 1)

for all i and j. Design an algorithm that, given an nกมn monotone array a of

integers, returns either a pair (i, j) such that a(i, j) = 0 or a message tough

luck signifying that no such pair exists. Your objective is to minimize the

worst-case number of entries of a that your algorithm consults (n2 is trivial

and ndlg ne is easy; to get any points, you must do better than O(n lg n)).

Present your algorithm in the pseudocode style of Question 1.

(This problem has nothing to do with any material covered in class; it is

simply a fun exercise in the design of ecient algorithms.)

 
กก

1. An array of nxn and has such property that for every entry [i,j], it is always bigger than both upper and left engtry: [i-1,j] and [i, j-1]. This is called monotone array of size of n.

2. Can you find if the array has at least one entry which is 0? Don't say you can do it by binary search which is trivial. Don't say you need sort because it is a kind of sorted.

C.The idea of program
กก

Originally it is proposed by some other guy, but he didn't believe it shortly. I had a feeling that it is divide-and-conquer like Strasseng's algorithm.

First you search along the diagonal of matrix until you encounter the positive entry. Then you divide matrix into four parts by row and column passing this entry: both the upper-left and lower-right will not contain 0 because one includes all negative and the other includes all positive. The upper-right and lower-left is your target which are two sub-matrix containing both positive and negative numbers. You recursive call to solve these two sub-matrix.

D.The major functions
I tried to confirm my idea by running single test and multi-test which simply iterates a number of times and 
calculates the average number of comparison operations of entries which is a scale of big O.
E.Further improvement
กก
F.File listing
1. monotone.cpp
file name: monotone.cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

const int ArraySize=20;
const int Step=8;
int array[ArraySize][ArraySize];

void initialize();

void display(int startR, int startC, int row, int col);

void construct(int row, int col);
bool search(int startR, int startC, int row, int col);

int counter=0;
bool showTrace=false;
bool noDisplay=true;

int testNumber=20;

double monoRun();

void singleTest();
void multiTest();

int main(int argc, char* argv[])
{
	srand(time(0));
/*
	if (argc==2)
	{
		if (strcmp(argv[1], "trace")==0)
		{
			showTrace=true;
		}	
	}
*/
	printf("single test no. 1\n");
	singleTest();
	printf("single test no. 2\n");
	singleTest();
	printf("multi test \n");
	multiTest();
	return 0;
}

void singleTest()
{
	showTrace=true;
	noDisplay=false;
	monoRun();
}

void multiTest()
{
	double result=0;

	showTrace=false;
	noDisplay=true;
	for (int i=0; i<testNumber; i++)
	{
		result+=monoRun();
	}
	printf("\n%d times and average is %g\n", testNumber, result/testNumber);
}

double monoRun()
{
	initialize();
	if (!noDisplay)
	{
		display(0, 0, ArraySize, ArraySize);
	}
	if (search(0, 0, ArraySize, ArraySize))
	{
		printf("\nfind it! at counter/ArraySize=%d/%d=%f\n", counter, ArraySize,
			(double)counter/ArraySize);
	}
	else
	{
		printf("\nNo luck! counter/ArraySize=%d/%d=%f\n", counter, ArraySize,
			(double)counter/ArraySize);
	}
	return (double)counter/ArraySize;
}

bool search(int startR, int startC, int row, int col)
{
	int r=startR, c=startC;
	if (row==0||col==0)
	{
		return false;
	}
	if (showTrace)
	{
		display(startR, startC, row, col);
	}
	while (array[r][c]<0)
	{
		r++;
		c++;
		counter++;//comparison
		if (r==startR+row||c==startC+col)
		{
			break;
		}
	}
	counter++;//comparison
	if (r<ArraySize&&c<ArraySize)
	{
		if (array[r][c]==0)
		{
			printf("\nfind it! array[%d][%d]=0\n", r, c);
			return true;
		}
	}
	return search(r, startC, row-r+startR, c-startC)||search(startR, c, r-startR, col-c+startC);
}



void construct(int row, int col)
{
	int left, upper, prev;
	if (row==ArraySize||col==ArraySize)
	{
		return;
	}
	
	if (row-1>=0&&col-1>=0)
	{
		upper=array[row-1][col];
		left=array[row][col-1];
	}
	else
	{
		if (row-1<0&&col-1>=0)
		{
			upper=left=array[row][col-1];
		}
		else
		{
			if (row-1>=0&&col-1<0)
			{
				upper=left=array[row-1][col];
			}
			else
			{
				//row=col==0, starting
				upper=left=-50;
			}
			
		}
	}
	prev=upper>left?upper:left;
	array[row][col]=prev+rand()%Step;//increase step everytime
	construct(row+1, col);
	construct(row, col+1);
	construct(row+1, col+1);
}

void display(int startR, int startC, int row, int col)
{
	printf("\n");
	for (int r=startR; r<startR+row; r++)
	{
		printf("row[%d]\t", r);
		for (int c=startC; c<startC+col; c++)
		{
			printf("%-5d", array[r][c]);
		}
		printf("\n");
	}
}

int max(int i, int j)
{
	return i>j?i:j;
}

void initialize()
{
	int max(int i, int j);
	counter=0;
	for (int r=0; r<ArraySize; r++)
	{
		for (int c=0; c<ArraySize; c++)
		{
			if (r==0&&c==0)
			{
				array[r][c]=-50;
			}
			else
			{
				if (r==0&&c!=0)
				{
					array[r][c]=array[r][c-1]+rand()%Step;
				}
				else
				{
					if (r!=0&&c==0)
					{
						array[r][c]=array[r-1][c]+rand()%Step;
					}
					else
					{
						array[r][c]=max(array[r-1][c], array[r][c-1])+rand()%Step;
					}
				}
			}
		}
	}
	//construct(0, 0);
}


How to run?
I try to get the longest common subsequence from FIVE strings by trying all their permutation of sequence.
 
1. The single test shows you each step the search goes through.
2. The multi-test doesn't show searching procedure and only calculates the average.

single test no. 1

row[0] -50 -45 -44 -39 -39 -33 -29 -24 -23 -21 -16 -9 -4 1 4 9 12 18 19 21
row[1] -49 -41 -40 -32 -27 -24 -17 -11 -6 0 7 10 14 21 23 30 36 41 45 52
row[2] -43 -35 -34 -27 -22 -17 -15 -6 0 5 10 13 14 28 35 38 42 42 50 52
row[3] -36 -28 -24 -22 -20 -12 -7 -4 0 11 12 20 20 35 38 44 48 49 56 61
row[4] -35 -23 -21 -20 -20 -5 -2 -1 4 11 15 22 27 42 44 48 52 52 59 66
row[5] -35 -23 -21 -15 -15 -5 -2 1 6 11 15 27 31 47 47 52 53 58 66 67
row[6] -29 -20 -18 -12 -7 2 3 6 8 11 17 29 35 51 54 55 61 68 70 71
row[7] -22 -18 -11 -6 0 8 12 16 18 19 22 32 37 51 55 58 61 74 76 82
row[8] -19 -14 -6 -6 5 10 13 20 22 26 26 36 39 51 58 63 64 81 87 89
row[9] -14 -12 0 0 12 12 13 22 28 33 36 41 41 56 59 70 73 82 89 93
row[10] -11 -11 2 3 16 18 22 27 31 34 43 47 47 57 59 76 83 85 96 96
row[11] -4 0 8 9 17 20 22 34 39 40 50 52 54 60 61 78 89 96 99 104
row[12] 1 5 14 18 22 28 29 40 40 47 57 62 64 66 69 78 95 100 101 104
row[13] 6 9 21 28 28 32 36 45 50 50 64 69 76 83 86 86 96 100 103 105
row[14] 9 15 28 29 29 39 40 48 57 59 69 71 77 90 92 93 98 104 107 111
row[15] 13 19 29 35 35 41 48 50 64 71 73 78 78 90 92 97 100 108 108 113
row[16] 17 24 32 40 42 46 49 52 67 73 80 85 87 94 101 107 109 115 116 117
row[17] 22 28 33 44 50 55 56 62 72 74 80 91 95 99 104 108 109 118 121 122
row[18] 24 35 42 46 56 56 59 68 75 78 81 95 99 106 106 113 120 124 126 133
row[19] 28 40 44 51 56 56 64 75 78 82 82 100 106 108 111 115 121 131 136 143

row[0] -50 -45 -44 -39 -39 -33 -29 -24 -23 -21 -16 -9 -4 1 4 9 12 18 19 21
row[1] -49 -41 -40 -32 -27 -24 -17 -11 -6 0 7 10 14 21 23 30 36 41 45 52
row[2] -43 -35 -34 -27 -22 -17 -15 -6 0 5 10 13 14 28 35 38 42 42 50 52
row[3] -36 -28 -24 -22 -20 -12 -7 -4 0 11 12 20 20 35 38 44 48 49 56 61
row[4] -35 -23 -21 -20 -20 -5 -2 -1 4 11 15 22 27 42 44 48 52 52 59 66
row[5] -35 -23 -21 -15 -15 -5 -2 1 6 11 15 27 31 47 47 52 53 58 66 67
row[6] -29 -20 -18 -12 -7 2 3 6 8 11 17 29 35 51 54 55 61 68 70 71
row[7] -22 -18 -11 -6 0 8 12 16 18 19 22 32 37 51 55 58 61 74 76 82
row[8] -19 -14 -6 -6 5 10 13 20 22 26 26 36 39 51 58 63 64 81 87 89
row[9] -14 -12 0 0 12 12 13 22 28 33 36 41 41 56 59 70 73 82 89 93
row[10] -11 -11 2 3 16 18 22 27 31 34 43 47 47 57 59 76 83 85 96 96
row[11] -4 0 8 9 17 20 22 34 39 40 50 52 54 60 61 78 89 96 99 104
row[12] 1 5 14 18 22 28 29 40 40 47 57 62 64 66 69 78 95 100 101 104
row[13] 6 9 21 28 28 32 36 45 50 50 64 69 76 83 86 86 96 100 103 105
row[14] 9 15 28 29 29 39 40 48 57 59 69 71 77 90 92 93 98 104 107 111
row[15] 13 19 29 35 35 41 48 50 64 71 73 78 78 90 92 97 100 108 108 113
row[16] 17 24 32 40 42 46 49 52 67 73 80 85 87 94 101 107 109 115 116 117
row[17] 22 28 33 44 50 55 56 62 72 74 80 91 95 99 104 108 109 118 121 122
row[18] 24 35 42 46 56 56 59 68 75 78 81 95 99 106 106 113 120 124 126 133
row[19] 28 40 44 51 56 56 64 75 78 82 82 100 106 108 111 115 121 131 136 143

row[6] -29 -20 -18 -12 -7 2
row[7] -22 -18 -11 -6 0 8
row[8] -19 -14 -6 -6 5 10
row[9] -14 -12 0 0 12 12
row[10] -11 -11 2 3 16 18
row[11] -4 0 8 9 17 20
row[12] 1 5 14 18 22 28
row[13] 6 9 21 28 28 32
row[14] 9 15 28 29 29 39
row[15] 13 19 29 35 35 41
row[16] 17 24 32 40 42 46
row[17] 22 28 33 44 50 55
row[18] 24 35 42 46 56 56
row[19] 28 40 44 51 56 56

find it! array[9][3]=0

find it! at counter/ArraySize=11/20=0.550000
single test no. 2

row[0] -50 -46 -45 -45 -40 -36 -29 -24 -17 -16 -10 -7 -7 -1 0 5 6 6 7 9
row[1] -45 -43 -37 -36 -36 -36 -25 -21 -12 -9 -8 -4 3 8 14 18 21 26 31 34
row[2] -41 -36 -34 -29 -22 -20 -16 -15 -12 -5 1 2 7 15 16 23 24 26 36 36
row[3] -38 -32 -32 -22 -22 -14 -9 -9 -3 4 4 11 14 18 19 30 35 36 43 50
row[4] -34 -29 -29 -20 -15 -14 -3 1 1 10 14 16 20 23 24 31 36 42 47 51
row[5] -28 -26 -25 -17 -11 -8 -1 2 5 13 16 22 26 33 39 45 51 57 62 68
row[6] -23 -21 -19 -10 -10 -6 6 13 14 20 23 24 29 38 46 52 59 63 69 73
row[7] -16 -16 -12 -4 3 9 10 17 18 20 28 32 32 41 52 53 66 73 80 83
row[8] -14 -7 -3 4 9 10 13 18 22 22 33 40 43 43 58 65 73 74 80 87
row[9] -10 -7 4 9 10 12 14 25 26 29 37 44 47 54 62 69 77 83 88 91
row[10] -7 -2 10 12 18 20 27 29 32 32 41 51 52 58 64 71 77 90 92 93
row[11] -1 5 14 17 22 28 33 39 39 43 47 55 59 63 66 77 84 97 97 104
row[12] 2 8 19 23 30 36 43 44 49 51 53 55 65 65 73 84 89 103 110 117
row[13] 4 10 20 27 30 40 43 46 49 58 58 62 72 73 75 87 95 107 116 122
row[14] 5 13 20 30 32 40 50 50 56 63 65 72 72 75 78 91 100 114 116 128
row[15] 5 15 20 33 40 43 54 58 64 70 76 79 81 82 87 94 100 121 122 134
row[16] 12 19 25 37 44 46 57 61 68 73 80 82 89 89 96 99 103 122 124 134
row[17] 19 25 32 42 45 52 58 67 70 78 87 89 89 92 96 99 107 125 125 135
row[18] 25 27 34 49 54 55 64 71 74 81 92 98 99 102 105 107 114 125 128 141
row[19] 31 33 35 52 56 58 68 74 76 86 95 105 106 108 110 114 116 129 134 148

row[0] -50 -46 -45 -45 -40 -36 -29 -24 -17 -16 -10 -7 -7 -1 0 5 6 6 7 9
row[1] -45 -43 -37 -36 -36 -36 -25 -21 -12 -9 -8 -4 3 8 14 18 21 26 31 34
row[2] -41 -36 -34 -29 -22 -20 -16 -15 -12 -5 1 2 7 15 16 23 24 26 36 36
row[3] -38 -32 -32 -22 -22 -14 -9 -9 -3 4 4 11 14 18 19 30 35 36 43 50
row[4] -34 -29 -29 -20 -15 -14 -3 1 1 10 14 16 20 23 24 31 36 42 47 51
row[5] -28 -26 -25 -17 -11 -8 -1 2 5 13 16 22 26 33 39 45 51 57 62 68
row[6] -23 -21 -19 -10 -10 -6 6 13 14 20 23 24 29 38 46 52 59 63 69 73
row[7] -16 -16 -12 -4 3 9 10 17 18 20 28 32 32 41 52 53 66 73 80 83
row[8] -14 -7 -3 4 9 10 13 18 22 22 33 40 43 43 58 65 73 74 80 87
row[9] -10 -7 4 9 10 12 14 25 26 29 37 44 47 54 62 69 77 83 88 91
row[10] -7 -2 10 12 18 20 27 29 32 32 41 51 52 58 64 71 77 90 92 93
row[11] -1 5 14 17 22 28 33 39 39 43 47 55 59 63 66 77 84 97 97 104
row[12] 2 8 19 23 30 36 43 44 49 51 53 55 65 65 73 84 89 103 110 117
row[13] 4 10 20 27 30 40 43 46 49 58 58 62 72 73 75 87 95 107 116 122
row[14] 5 13 20 30 32 40 50 50 56 63 65 72 72 75 78 91 100 114 116 128
row[15] 5 15 20 33 40 43 54 58 64 70 76 79 81 82 87 94 100 121 122 134
row[16] 12 19 25 37 44 46 57 61 68 73 80 82 89 89 96 99 103 122 124 134
row[17] 19 25 32 42 45 52 58 67 70 78 87 89 89 92 96 99 107 125 125 135
row[18] 25 27 34 49 54 55 64 71 74 81 92 98 99 102 105 107 114 125 128 141
row[19] 31 33 35 52 56 58 68 74 76 86 95 105 106 108 110 114 116 129 134 148

row[6] -23 -21 -19 -10 -10 -6
row[7] -16 -16 -12 -4 3 9
row[8] -14 -7 -3 4 9 10
row[9] -10 -7 4 9 10 12
row[10] -7 -2 10 12 18 20
row[11] -1 5 14 17 22 28
row[12] 2 8 19 23 30 36
row[13] 4 10 20 27 30 40
row[14] 5 13 20 30 32 40
row[15] 5 15 20 33 40 43
row[16] 12 19 25 37 44 46
row[17] 19 25 32 42 45 52
row[18] 25 27 34 49 54 55
row[19] 31 33 35 52 56 58

row[9] -10 -7 4
row[10] -7 -2 10
row[11] -1 5 14
row[12] 2 8 19
row[13] 4 10 20
row[14] 5 13 20
row[15] 5 15 20
row[16] 12 19 25
row[17] 19 25 32
row[18] 25 27 34
row[19] 31 33 35

row[11] -1 5
row[12] 2 8
row[13] 4 10
row[14] 5 13
row[15] 5 15
row[16] 12 19
row[17] 19 25
row[18] 25 27
row[19] 31 33

row[12] 2
row[13] 4
row[14] 5
row[15] 5
row[16] 12
row[17] 19
row[18] 25
row[19] 31

row[11] 5

row[9] 4
row[10] 10

row[6] -10 -10 -6
row[7] -4 3 9
row[8] 4 9 10

row[7] -4
row[8] 4

row[8] 4

row[6] -10 -6

row[6] -6

row[0] -29 -24 -17 -16 -10 -7 -7 -1 0 5 6 6 7 9
row[1] -25 -21 -12 -9 -8 -4 3 8 14 18 21 26 31 34
row[2] -16 -15 -12 -5 1 2 7 15 16 23 24 26 36 36
row[3] -9 -9 -3 4 4 11 14 18 19 30 35 36 43 50
row[4] -3 1 1 10 14 16 20 23 24 31 36 42 47 51
row[5] -1 2 5 13 16 22 26 33 39 45 51 57 62 68

row[3] -9 -9 -3
row[4] -3 1 1
row[5] -1 2 5

row[4] -3
row[5] -1

row[5] -1

row[3] -9 -3

row[3] -3

row[0] -16 -10 -7 -7 -1 0 5 6 6 7 9
row[1] -9 -8 -4 3 8 14 18 21 26 31 34
row[2] -5 1 2 7 15 16 23 24 26 36 36

row[2] -5 1

row[2] 1

row[0] -7 -7 -1 0 5 6 6 7 9
row[1] -4 3 8 14 18 21 26 31 34

row[1] -4

row[0] -7 -1 0 5 6 6 7 9

row[0] -1 0 5 6 6 7 9

row[0] 0 5 6 6 7 9

find it! array[0][14]=0

find it! at counter/ArraySize=57/20=2.850000
multi test

find it! array[4][8]=0

find it! at counter/ArraySize=42/20=2.100000

find it! array[5][5]=0

find it! at counter/ArraySize=6/20=0.300000

find it! array[8][3]=0

find it! at counter/ArraySize=10/20=0.500000

find it! array[8][2]=0

find it! at counter/ArraySize=22/20=1.100000

find it! array[15][0]=0

find it! at counter/ArraySize=22/20=1.100000

find it! array[6][4]=0

find it! at counter/ArraySize=43/20=2.150000

find it! array[9][1]=0

find it! at counter/ArraySize=12/20=0.600000

No luck! counter/ArraySize=49/20=2.450000

find it! array[9][1]=0

find it! at counter/ArraySize=12/20=0.600000

find it! array[12][0]=0

find it! at counter/ArraySize=17/20=0.850000

find it! array[16][0]=0

find it! at counter/ArraySize=24/20=1.200000

find it! array[6][4]=0

find it! at counter/ArraySize=34/20=1.700000

find it! array[11][1]=0

find it! at counter/ArraySize=22/20=1.100000

find it! array[14][0]=0

find it! at counter/ArraySize=23/20=1.150000

find it! array[15][1]=0

find it! at counter/ArraySize=24/20=1.200000

find it! array[9][1]=0

find it! at counter/ArraySize=27/20=1.350000

find it! array[13][0]=0

find it! at counter/ArraySize=18/20=0.900000

find it! array[11][1]=0

find it! at counter/ArraySize=15/20=0.750000

find it! array[12][0]=0

find it! at counter/ArraySize=17/20=0.850000

find it! array[3][11]=0

find it! at counter/ArraySize=48/20=2.400000

20 times and average is 1.2175
กก










                                                               
                      







                       back.gif (341 bytes)       

up.gif (335 bytes)                                       
next.gif (337 bytes)