DS assignment 1

Anand Engineering College, Agra Department of Computer Science
Apoorv Garg Page 1 of 3
Data Structures Using C (ECS-302)
Home Work Assignment 1
Q.1. In the following are given C functions for four different algorithms for solving the
Maximum Subsequence Problem. For each algo, check whether it will be able to give the
right solution to the Maximum Subsequence Problem. Calculate the growth-rate (in terms
of the Big-O notation) for these algorithms, and state which one you consider the most
appropriate and why.
(a) The 'Brute Force Algo'
int MaxSubsequenceSum(const int A[], int N)
{
int S, MaxS, i, j, k;
MaxS=0;
for(i=0; ifor(j=i; j{
S=0;
for(k=i; k<=j; k++)
S = S + A[k];
if(S>MaxS)
MaxS=S;
}
return MaxS;
}
(b) The 'Improved Brute Force Algo'
int MaxSubsequenceSum(const int A[], int N)
{
int S, MaxS, i, j;
MaxS=0;
for(i=0; i{
S=0;
for(j=i; j{
S = S + A[k];
if(S>MaxS)
MaxS=S;
}
}
return MaxS;
}
Anand Engineering College, Agra Department of Computer Science
Apoorv Garg Page 2 of 3
(c) The 'Divide and Conquer Algo'
int Max3(int A, int B, int C)
{
/* function to calculate maximum of 3 integers*/
if(A>=B && A>=C) return A;
else if(B>=C) return B;
else return C;
}
int MaxSubSum(const int A[], int L, int R)
{ /*Recursive function*/
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int MaxBorderSum;
int LeftBorderSum, RightBorderSum;
int i, Center;
if (L==R) /* Base Case */
if (A[L] > 0)
return A[L];
else
return 0;
Center=(L+R)/2; /*Find the mid point of the array*/
MaxLeftSum = MaxSubSum(A, L, Center);
/*Find max. subsequence sum in the left half*/
MaxRightSum = MaxSubSum(A, Center+1, R);
/*Find max. subsequence sum in the right half*/
MaxLeftBorderSum=0; LeftBorderSum=0;
for(i=L; i<=Center; i++)
{
LeftBorderSum = LeftBorderSum + A[i];
if (LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum=0; RightBorderSum=0;
for(i=Center; i<=H; i++)
{
RightBorderSum = RightBorderSum + A[i];
if (RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
MaxBorderSum=MaxLeftBorderSum+MaxRightBorderSum;
return Max3(MaxLeftSum, MaxRightSum, MaxBorderSum);
}
int MaxSubsequenceSum(const int A[], int N)
{
return MaxSubSum(A, 0, N-1);
}
Anand Engineering College, Agra Department of Computer Science
Apoorv Garg Page 3 of 3
(d) The 'Online Algo'
int MaxSubsequenceSum(int A[], int N)
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for(j=0; j{
ThisSum = ThisSum + A[i];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
Q.2. Find the complexity of the following C programs:
(a) Euclid's Algorithm for GCD:
(You might like to verify the program for any two positive integers)
unsigned int GCD(unsigned int M, unsigned int N)
{
unsigned int Remainder;
while (N>0)
{
R = M%N;
M = N;
N = R;
}
return M;
}
(b) Smart Exponentiation (calculates XN):
long int Power(long int X, unsigned int N)
{
if (N==0) return 1;
if (N==1) return X; /* base cases */
if (N%2 == 0) /* N is even */
return Power(X*X, N/2);
else /* N is odd */
return X*Power(X*X, N/2);
}