DS assignment 2

Anand Engineering College, Agra Department of Computer Science
Apoorv Garg Page 1 of 1
Data Structures Using C (ECS-302)
Home Work Assignment 2
Q. 1. Define:
a. Data
b. Information
Q. 2. Explain the term ‘Data Structure’.
Q. 3. Describe in brief the various data structures.
Q. 4. Give the difference between linear and non-linear data structures with examples.
Q. 5. Define an array. Explain: Traversing of Linear Arrays.
Q. 6. Consider the linear array A(5:50), whose base address is 300 and the number of words
per memory cell is 4. Find the address of A[15].
Q. 7. Give a procedure to find the average of the values stored in a linear array A.
Q. 8. Write a program in C to sort a set of 100 complex numbers into ascending order of their
absolute values. Real and imaginary part of all the complex numbers are integers.
Absolute value of a complex number x + iy is defined as 2 2 x + y . Choose suitable
data structure to represent complex numbers.
Q. 9. Give the time-complexity analysis of the two algorithms (discussed in the class) for
deleting duplicate numbers of a linear array.
Q. 10. Calculate the address of X[10][10] in an array X[20][50]. Assume the base address to be
2000 and that each element requires 4 bytes of storage, and that the array is stored in:
a. Row major
b. Column major
Q. 11. Let A be an N x N square matrix array. Write modules (algorithms) for the following:
a. Find the number of elements in the matrix
b. Find the number NUM of non-zero elements in A.
c. Find the product PROD of the diagonal elements (a11, a22, a33, …, aNN).
d. Find the summation SUM of the diagonal elements.
Q. 12. Derive the formula to find physical address of an element of three dimensional array
stored in row major order.

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);
}

DS assignment

assignment is done...............