Solution to Homework 10

Solution to Problem 1

int maximum (const Vector < int > & list, int N)
{
	// Base case
	if (N == 1)
		return list[0];
	// Recursive case
	else if (N > 1)
	{
		// Compute the maximum of the first N-1 slots
		int smallMax = maximum (list, N - 1);

		// Compare this with the contents of the last slot
		if (smallMax > list[N-1])
			return smallMax;
		else 
			return list[N-1];
	}
}

Solution to Problem 2

int binarySearch (const Vector<int> & list, int key, int first, int last)
{
	// Base case
	if (first > last)
		return 0; 	// no element can be found in a Vector with no elements

	else if (first <= last)
	{
		// find the index of the middle slot
		int mid = (first + last) / 2;
	
		// Compare key with the middle slot
		if (list[mid] == key)
			return 1;	// Found the element
		
		// Element can only be in the right half
		else if (list[mid] < key)
			return binarySearch( list, key, mid + 1, last);

		// Element can only be in the left half
		else if (list[mid] > key)
			return binarySearch( list, key, first, mid - 1);
	}
}

Solution to Problem 3

string toBinary (int N)
{
	string str;

	// Base case
	if (N == 1)
		str = "1";

	// Recursive case
	else if (N > 1)
	{
		// check is N is even
		if (N % 2 == 0)
			str = toBinary (N/2) + "0";

		// check if N is odd
		else
			str = toBinary (N/2) + "1";
	}

	return str;
}