CS 117
Midterm 2
Ondich
Due ON PAPER 11:11 AM Wednesday, March 7, 2001
This is an open book, open notes, and open computer test.
If you get stuck, you may talk to me (Jeff Ondich) or
Jenny Cooper, but please don't talk to anyone else (including
the lab assistants) about the exam.
- (15 points) Write two versions of the following function,
one recursive and one iterative.
// Returns true if the given character is equal to
// a[0] or a[1] or...or a[N-1], and false otherwise.
bool IsCharInArray( char ch, char a[], int N )
{
//...
}
- (9 points) Modify the main program in
emailClassTester.cpp to
sort the array of e-mail messages by subject line before printing them out.
Hand in your new main program, and any other code you added or changed in
emailClassTester.cpp,
emailClass.cpp, or
emailClass.h.
- (9 points) Searching in computer science is the process of
looking through a collection of items to find a particular item. For
example, the function IsCharInArray in problem 1 is a search function.
- Read about binary search in your textbook.
- Suppose you have a list of the
US states in alphabetical order, and you want to know whether
Saskatchewan is on the list. Start at the beginning of
the list and compare Saskatchewan to each item until
you find Saskatchewan or encounter an item that is alphabetically
later than Saskatchewan. (This is called "linear search on a sorted
list.") To how many states do you need to compare Saskatchewan
before you determine that it's not on the list? What is the last
state to which you compare Saskatchewan?
- Now do binary search for Saskatchewan. To how many states
do you need to compare Saskatchewan before you decide it's not on
the list? List the states to which you compare Saskatchewan, in
the order in which you do the comparisons.
- (12 points) I have N numbers stored in an array
a[], and I want to know the distance between
the pair of these numbers that are furthest apart.
Elmo suggests the following code, which does the job:
int max = 0;
for( int i=0; i < N; i++ )
{
for( int j=0; j < N; j++ )
{
if( a[i] - a[j] > max )
max = a[i] - a[j];
}
}
- When I used Elmo's code on N = 5000 numbers, the program
took an average of 4.2 seconds (I tried it several times).
Approximately how long will Elmo's code take to run if N = 30000
(assuming I use the same computer)? Justify your answer.
It is not sufficient to tell me that you ran the code yourself
and it took a certain amount of time. I want you to explain
why it will take as long as you say it will.
- Zoe says she thinks Elmo's code is stupid. Elmo says,
"Elmo likes Elmo's code. If Zoe thinks she can do better,
Zoe should show Elmo how." Describe an
algorithm that Zoe could use to show Elmo that his code
is too slow. Explain why your algorithm faster than Elmo's.
- (2 points) Tell me a joke, please.
- (7 points) A little binary arithmetic.
- What is the base ten equivalent of the binary number 1000110?
- What character is represented by the byte 01000110 in ASCII?
- Suppose you have an int-type variable i, and you want to
print out its binary equivalent. How would you do it? (Hint: it's
easier to print it backwards than forwards, and you can use
the operations / and % to good effect.)