taheri.javad
BAN USER#include <stdio.h>
const int rowN = 3;
const int colN = 3;
int findElement(int matrix[rowN][colN]){
/* if matrix is null, return null*/
if(matrix == NULL)
return NULL;
int result = NULL;
/* matrix size */
int numOfRows = rowN;
int numOfCols = colN;
/* create an auxiliary list boolean array */
int smallestColPerRow[numOfRows];
/*find the smallest element in each row*/
int rowIter, colIter;
for(rowIter=0; rowIter < numOfRows; rowIter++){
int smallestCol = 0;
for(colIter=0; colIter < numOfCols; colIter++){
if(matrix[rowIter][colIter] < matrix[rowIter][smallestCol])
smallestCol = colIter;
}
smallestColPerRow[rowIter]= smallestCol;
}
/* search for largetst element in each col, check if it is the smallest element in that row too*/
for(colIter=0; colIter< numOfCols; colIter++){
int largestRow = -100000;
for(rowIter=0; rowIter< numOfRows; rowIter++){
if(matrix[rowIter][colIter] > matrix[largestRow][colIter])
largestRow = rowIter;
}
if(smallestColPerRow[largestRow]== colIter){
result =matrix[largestRow][colIter];
break;
}
}
return result;
}
int main(){
int matrix [rowN][colN] = {
{1,1,3},
{0,1,-1},
{1,-1,2}};
int result = findElement(matrix);
if(result == NULL)
printf("\nnot found");
else
printf("\nresult is:%d\n", result);
return 0;
}
indices i, j, k <-- 0 pointing to lists 1, 2, 3 respectively
minVal <-- +infinity
iMax, jMax, kMax <--0;
at each step
find which list[index] is minimum among i, j, k then increase that index by 1
if minVal is greater than max(three lists at their index) - min(three lists at their index))
update minVal and iMax, jMax, kMax
while indices are not out of list size
return minVal
takes O(n+m+l)
- taheri.javad October 09, 2012This can be solved by using Quick-sort algorithm, choosing 0 as the pivot at the first step and stopping after first iteration. The only requirement is that 0 should be placed at its right location.
Takes O(n)
This can be solved using a recursive function. Since the sub-problems overlap with each-other, a dynamic programming approach speeds up the algorithm.
O(n*m)
#include<iostream>
#include<math.h>
using namespace std;
const long m=6;
const long n=12;
const long x=20;
int *table;
int func(int remainingX, int remainingDices ){
int result =0;
if(table[remainingX*n + remainingDices] != -1)
return table[remainingX*n + remainingDices];
if(remainingDices==1){
if(remainingX >=1 && remainingX<=m)
result =1;
else
result =0;
}
else{
for(int i=1; i<=m; i++){
if( (remainingX-i) >= (remainingDices-1) )
result += func(remainingX-i, remainingDices-1);
}
}
table[remainingX*n + remainingDices] = result;
return result;
}
int main(int argc, char* argv[]){
long tableSize = n*m*n + n +1;
table = new int[tableSize];
for(int i=0; i< tableSize; i++)
table[i]=-1;
double cumProb=0;
for(int i=n; i<=x; i++){
double tmpf = func(i,n);
double probI = tmpf/(long)pow(m,n);
cumProb += probI;
}
printf("prob for x => %ld is:%11.10f\n", x, 1-cumProb);
}
What do you mean by "sum of difference"? And by 'equal' arrays, do you mean 'equal-sized' arrays? Thanks
- taheri.javad September 29, 2012
The problem with the matrix is that it occupies N*N rooms of the memory, where only a small subset of node-pairs (let's say m) have distance information. To solve this problem, one can use a hashmap, where the keys are the pair information, and the values are the distance between the two. The key of a pair could be defined as an interger, which can be uniquely built having the pair ids. For example, (x*N + y) can be used as the key id for the nodes with ids x, and y.
- taheri.javad January 14, 2013Using this scheme, the required space for storing the information will be: 2*len(Integer) *m/alpha , which for an enough large N, it would be much smaller than N*N*len(Integer)