Midterm Examination 1-2014 – Introduction to Algorithms and Programming 60-141

60-141-01 Introduction to Algorithms and Programming
Winter 2014
Midterm Examination # 1

Question 1. [ 6 marks ]
For each of the following parts, write a C language statement that performs the indicated task. Assume the float type variables N1 and N2 are defined and initialized. Each part is worth 1 mark.
A. Define the variables fPtr and fPtr2 to be pointers to objects of type float.
float * fPtr, * fPtr2 ;
B. Assign the address of variable N1 to pointer variable fPtr.
fPtr = &N1 ;
C. Print the value of the object pointed to by fPtr.
printf( “%f”, * fPtr ) ;
D. Assign the value of the object pointed to by fPtr to variable N2.
N2 = * fPtr ;
E. Print the address of variable N2. Use the %p conversion specifier.
printf( “%p”, & N2 ) ;
F. Print the address stored in fPtr. Use the %p conversion specifier.
printf( “%p”, fPtr ) ;

Question 2. [ 10 marks ]
Part A. [ 5 marks ]
Write a complete iterative function definition for the function Pow(X,N), where X is a double type variable, and N is an int type variable. If N is less than zero, the function returns POW_ERROR (assumed to be defined elsewhere using a #define); if N is equal to zero and X is also equal to zero, the function returns POW_ERROR, otherwise if X is not equal to zero, 1 is returned. If N is greater than 0, the function returns the value of XN.
ANSWER:
double Pow ( double X, int N )
{
int k ;
double Y = 1.0 ;
if( N < 0 ) return POW_ERROR ;
if( N == 0 && X == 0) return POW_ERROR ;
if( N == 0 ) return 1 ;
for( k=0 ; k Y = Y * X ;
return Y ;
}
Part B. [ 5 marks ]
Following the same description provided in Part A above, write a complete recursive function definition for the function Pow(X,N).
ANSWER:
double Pow ( double X, int N )
{
if( N < 0 ) return POW_ERROR ;
if( N == 0 && X == 0) return POW_ERROR ;
if( N == 0 ) return 1 ;
return X * Pow( X, N-1 );
}

Question 3. [ 10 marks ]
Write a complete C language function definition called Search(A,N,S), where A is an array of double type values, N is an int type variable, and S is a double type variable. When Search() is called, it performs a search for the value S in A and returns the value of the position (ie. subscript) where S was found; otherwise, a value -1 is returned is S is not found. Assume that all input parameters have been suitably initialized before the function call. (Announcement was made to clarify that N is the actual number of elements contained in the array A).
Part A. [ 4 marks ]
Write the function Search() assuming that the data in A is not organized in any particular way.
ANSWER:
int Search ( double A [ ], int N, double S )
{
int k ;
for( k=0; k<N; k++ )
if( A[k] == S ) return k ;
return -1 ;
}
Part B. [ 6 marks ]
Rewrite the function Search() assuming that A has been sorted in ascending order (smallest to largest) and using an algorithm with O( log N ) efficiency.
ANSWER: (Iterative solution)
int Search ( double A [ ], int N, double S )
{
int lo=0, mid, hi ;
hi = N-1 ;
while( lo<=hi ) { mid = (hi + lo)/2 ; if( A[mid] == S ) return mid ; if( A[mid] > S ) hi = mid – 1 ;
if( A[mid] < S ) lo = mid + 1 ; // or use else
}
return -1 ;
}

Question 4. [ 10 marks ]
Part A. [ 4 marks ]
Write a complete function definition of the function Swap(), used as in Swap(&X, &Y), where X and Y are each float type variables. The effect of Swap() is to exchange the values of X and Y. Do not write a complete program; write only the function definition.
ANSWER:
void Swap( float * X, float * Y ) {
float T ;
T = *X ;
*X = *Y ;
*Y = T ;
return ;
}
Part B. [ 6 marks ]
Write a single, complete function Sort() that accepts input of a 1-dimensional array of float values, and the number of values in the array, and then sorts the values in ascending order before returning. You may use any sorting algorithm to perform the sort. Do not write a complete program; write only the function definition. You may use the function Swap() defined in Part A above (it is not necessary that your answer to Part A is correct, just use the definition of what the function is supposed to do).
ANSWER:
void Sort ( float A [ ], int N ) /* BUBBLE SORT */
{
int I, J ;
for( I=0; I < N-1; I++ ) // Note: upper limit may be N-2 for( J=N-1; J > I; J– )
if( A[J] < A[J-1] )
Swap( &A[J], &A[J-1] ) ;
return ;
}
There are several equivalent and correct solutions to this problem and markers were advised to consider each strategy by tracing the logic. For instance, using Selection sort as discussed in lectures – look for the largest value in the current unsorted sub-list and swap this value with the first element of the unsorted sub-list, thereby adding it to the end of the sorted sub-list. As this iterates, the sorted sub-list grows while the unsorted sub-list shrinks.

Question 5. [ 6 marks ]
A palindrome is a string of characters which, when reversed, is identical to the original string. Examples of palindromes include: ”radar” and ”able was i ere i saw elba”. For this question it is assumed that a string of characters is stored in an array C and that the number of characters is stored in the int variable N.
Write a complete C language function called Palindrome(), with usage defined by:
if( Palindrome( C, N ) )
printf( “This is a palindrome.\n” ) ;
else
printf( “This is not a palindrome.\n” ) ;
ANSWER: (Iterative solution)
int Palindrome ( char C [ ], int N )
{
int K ;
for( K=0; K < N / 2; K++ ) // N/2 is the midpoint
if( C[ K ] != C[ N – K ] ) return 0 ;
return 1 ;
}
NOTE: This algorithm can be modified in several ways, each equivalent and correct. It is possible to modify it to eliminate having to compare a midpoint element with itself if N is an odd number – this can be used to eliminate one comparison operation by replacing it with another comparison operation – not much positive tradeoff in this, but still correct.
ALTERNATIVE ANSWER: (Recursive solution)
int Palindrome ( char C [ ], int N )
{
if( N == 0 || N == 1 ) return 1 ;
if( C[ 0 ] == C[ N – 1 ] ) Palindrome ( &C[1], N-2 ) ;
return 0 ;
}