Practice Problem Solutions

Problem 1:

// This is a rather brute force, but easy to understand solution. There
// is an easy way to replace 3 nested loops by 2. You should think about this.
void minimumSum (const Vector < int > & list, int & minLeft, int & minRight)
{
	int i, j, k, sum;
	int size = list.length();
	int minSum = list[0]; // Assuming that the size of list is at least 1
	minLeft = 0; minRight = 0;

	// Generate all possible left endpoints
	for (i = 0; i < size; i++)
	{
		// Generate all possible right endpoints
		for (j = i; j < size; j++)
		{
			sum = 0;

			// Compute the sum of the sequence list[i..j]
			for (k = i; k <= j; k++)	
				sum = sum + list[k];

			// Found a better sum
			if (sum < minSum)
			{
				minLeft = i;
				minRight = j;
				minSum = sum;
			}
		} // end of j-loop
	} // end of i-loop
} // end of function

Problem 2:

// This is a rather brute force, but easy to understand solution. As in Problem 1
// you can replace the 3 nested loops by 2.
void longestStutter(const Vector < int > & list, int & left, 
		    int & right, int & stutterElement)
{
	int i, j, k, stutterLength;
	int size = list.length();
	int maxStutterLength = 0; 

	// Generate all possible left endpoints
	for (i = 0; i < size; i++)
	{
		// Generate all possible right endpoints
		for (j = i; j < size; j++)
		{
			stutterElement = list[j];
			stutterLength = 1;
			left = j; right = j;

			// Is list[i..j] a stutter?
			for (k = i+1; k <= j; k++)	
				if (list[k] == stutterElement)
					stutterLength++;
				else
				{
					stutterLength = 1;
					break;
				}

			// Found a longer stutter
			if (stutterLength >= maxStutterLength)
			{
				maxStutterLength = stutterLength;
				left = i;
				right = j;
			}
				
		} // end of j-loop
	} // end of i-loop
} // end of function




Problem 3:


int maximum(Vector < int > & list, int N, int & loc)
{
	// Base Case
	if (N == 1)
	{
		loc = 0;
		return list[0];
	}

	// Recursive Case
	else if (N > 1)
	{
		int smallmax = maximum(list, N-1, loc);
		
		if (smallmax >= list[N-1])
			return smallmax;

		else
		{
			loc = N-1;
			return list[N-1];
		}
	}
}






Problem 4:


int ascend(int N, int prev)
{
	int num;

	// Base Case
	if (N == 0)
		return 1;

	// Recursive Case
	else
	{
		cin >> num;
		
		if (num < prev)
			return 0;

		return ascend(N-1, num);
	}
}


	



Problem 5:


int count(int N)
{
	if (N <= 9)
		return 1;

	else
	{
		int digit = count(N/10);
		return digit + 1;
	}
}






Problem 6:


Part (i)


int choose(int N, int K)
{
	// Base Case
	if ((N == K) || (K == 0))
		return 1;

	// Recursive Case
	return choose(N-1, K-1) + choose(N-1, K);
}	





Part (ii)


Given N = 5 and K = 2:


	choose(5, 2)
	choose(4, 1)
	choose(3, 0)
	choose(3, 1)
	choose(2, 0)
	choose(2, 1)
	choose(1, 0)
	choose(1, 1)
	choose(4, 2)
	choose(3, 1)
	choose(2, 0)
	choose(2, 1)
	choose(1, 0)
	choose(1, 1)
	choose(3, 2)
	choose(2, 1)
	choose(1, 0)
	choose(1, 1)
	choose(2, 2)