Introduction to Programming (22C:16, 22C:106)

Final Exam: Wednesday, 12/18/96

This exam contains 4 questions and you have 2 hours to complete the exam. This is an open notes, open book exam so feel free to use your notes and the textbook. Problems 1, 2, and 3 require that you write C++ code. You will be graded based on what you write and not on what you intended to write. So please write legibly and if necessary use comments to convey or clarify your ideas. Please write your name and section number on the exam booklet provided.

Note: No questions will be answered during the exam. I have tried to make each question as clear as possible. If you still find that something is ambiguous or imcomplete make an appropriate assumption and proceed.

Problem 1: [25 points] On Classes and Vectors

In this problem the goal is to modify the Dice class so that the faces of a k-sided die are not restricted to contain numbers in the range . As a user of the Dice class, in addition to the number of faces that a die has, I would like to specify the number that goes on each face of the die. To make these ideas more concrete, let me give you a program that I would like to run using the Dice class.

 
	#include "vector.h"
	#include "dice.h"
	#include <iostream.h>
	int main()
	{
		 Vector<int> faces(4);
		 faces[0] = 7; faces[1] = 11; faces[2] = 3; faces[3] = 9;
		 Dice tetra(faces);
		 int i;
		 for (i = 0; i < 100; i++)
			 cout << tetra.Roll() << endl;
		 return 0;
	 }

This program creates an object called tetra belonging to the Dice class by calling a constructor that takes as a parameter a Vector of integers. The object tetra has 4 faces containing the numbers 7, 11, 3, and 9. The program then rolls tetra 100 times and produces as output the values of these rolls. Thus the output is a sequence of 100 integers drawn from among 7, 11, 3, and 9.

Make changes to the Dice class that will allow programs such as the above to run correctly. These changes could include changes to the private portion of the Dice class, changes to the public portion of the Dice class, and changes to the implementation of the Dice class. You should make sure that the Dice class continues to provide all the features that it currently provides. In other words, the ``new'' Dice class should contain all the member functions that the ``old'' Dice class contained (including the constructor) and furthermore these member functions should behave exactly as they used to.

Problem 2: [25 points] On Binary Search

A bitonic sequence is a sequence of integers that first grow until a peak is reached and then shrink. More precisely, a sequence of integers

is a bitonic sequence if for some p, , and . So the integers in the sequence grow until the peak is reached and then start shrinking. Here are some examples of bitonic sequences:

• 3, 5, 11, 100, 98, 96. Here the peak is 100 and this is in position 3 in the sequence.
• 1, 2, 3, 4, 5. Here the peak is a 5 and this is in position 4 in the sequence.
• 3, 10, 11, 10, 9, 7, 6, 5, 4, 3, 2, 1. Here the peak is 11 and this is in position 2 in the sequence.

Write a function called bitonic_max that finds the peak, that is the largest element, in a bitonic sequence and returns the position of the peak. The bitonic sequence is passed to the function as a Vector of integers. The function should return the position of the peak in the sequence. You should use the following function header:

int bitonic_max(Vector<int> sequence)

The function you write should not scan the entire Vector to find the peak. Instead, it should use a technique very similar to that used in binary search to find the peak. In particular, your function should examine the elements in the middle of the Vector being considered and based on this examination should either (a) return an answer or (b) consider the left-half of the Vector for further search or (c) consider the right-half of the Vector for further search.

Note: You are free to write a recursive or a non-recursive version of this function.

Problem 3: [25 points] On Strings and Characters

You are given two strings, say str1 and str2, each containing one or more digits. By a digit, I mean a character that is one of '0', '1', '2',..., '8' or '9'. There is no limit on the number of digits that either str1 or str2 contains. This means that you cannot convert the strings into integers, add them together, and then convert the result back to a string. Furthermore, str1 and str2 may have different lengths. Write a function called add that adds the numbers represented by the two strings and returns the result via a reference parameter called str3. You should use the following function header:

void add(string str1, string str2, string & str3)

For example, if str1 equals "389276437432" and str2 equals "6224371479246", then by the end of the function add, the string str3 should take on the value "6613647916678". You may assume that str3 is passed into the function add with value equal to the empty string "".

Hint: Add the two numbers, digit-by-digit, starting from the rightmost digits and moving to the left. You might want to use the concatenate operator to place the result of the addition in str3.

Problem 4: [25 points] On Recursion and Reference Parameters

Consider the following program that contains a recursive function called factorial.

 
	#include <iostream.h>
	int factorial(int n)
	{
		 if ((0 == n) || (1 == n))
			 return 1;
		 else {
			 n = n - 1;
			 int temp = factorial(n);
			 cout << "Factorial of " << n << " is " << temp << endl;
			 return (n+1) * temp;
		 }
	 }


	 int main()
	 {
		 int i = 5;
		 int temp = factorial(i);
		 cout << "Factorial of 5 is " << temp << endl;
		 return 0;
	 }

(a)

Write down the output produced by the above program.

(b)

What is the output produced by the above program if we change the value parameter in the function factorial to a reference parameter. In other words, we change the function header of factorial to:

int factorial(int & n)