[12] Question 2:
Here is a C++ function that implements a new kind of searching algorithm:
 

int deluxeSearch( int data[], int size, int item )
{
    return deluxeSearchInRange( data, item, 0, size - 1 );
}

int deluxeSearchInRange( int data[], int item, int lo, int hi )
{
    if( lo hi ) {
        return -1;
    }

    int mid1 = lo + (hi-lo)/3;
    int mid2 = lo + 2 * (hi - lo)/3;

    if( item < data[ mid1 ] ) {
        return deluxeSearchInRange( data, item, lo, mid1 - 1 );
    } else if( item == data[ mid1 ] ) {
        return mid1;
    } else if( item data[ mid1 ] && item < data[ mid2 ] ) {
        return deluxeSearchInRange( data, item, mid1 + 1, mid2 - 1 );
    } else if( item == data[ mid2 ] ) {
        return mid2;
    } else {
        return deluxeSearchInRange( data, item, mid2 + 1, hi );
    }
}

1. In terms of the way it searches through a sorted array, is deluxe search more like linear search or binary search?

 

 

2. For an array of size n, what's the maximum number of times deluxeSearchInRange will make a recursive call to itself while searching?

 

 
 
 

3. Give a tight Big-O bound for deluxeSearch in terms of the size of the passed-in array.  Make the bound as simple as possible by removing any constant factors or lower-order terms.

 

 

Give two questions that you would like to ask about the specification of this ADT before you start programming.  For each question, write a sentence or two explaining why the answer to this question would affect your approach to the task
 

[14] Question 4:
Here is a portion of a program:
 

#include <iostream.h>

class Simple
{
public:
    virtual int goAhead();
};

int Simple::goAhead() {
    return 17;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 

int main( void )
{
    Simple *obj = getSimpleObject();
    cout << (obj-goAhead()) << endl;
    return 0;
}

[10] Question 5:
Suppose you are given the following definition of a Dir type:
 

1. Write a function printDir that takes a direction and prints (using cout) the textual representation of that direction.

 

 
 
 
 
 
 
 
 
 
 
 
 
 

2. A malicious programmer could potentially cause an error in your printDir function using a cast, as follows:

1. Draw the binary search tree that results from inserting the numbers 16, 11, 2, 19, 5, 29, 18, 24 (in that order) into an initially empty tree.

 

 
 
 
 
 
 
 
 
 
 
 
 
 

2. Write out the values in the tree from part (a) as they would be encountered in a preorder, inorder and postorder traversal of the tree

 

 
 
 
 
 
 
 
 
 

3. Now suppose I search the tree for the value 6, using the recursive method for finding an item in a binary search tree (the one that doesn't examine the whole tree).  Write down the nodes that I would look at while performing the search.

 

To store movie ratings, you decide to create a table-style ADT called MovieDict. An instance of the MovieDict ADT should be able to record votes, return the ratings for movies by name, and provide the name of the highest-rated movie.  Although the final version of the program will be used from a WWW turnin-like form, you are provided with the following sample client program to get an idea of how MovieDict will be used:
 

#include "moviedict.h"

int main( void )
{
    MovieDict dict;

    dict.vote( "Citizen Kane", 9 );   // Bob votes 9 on "Citizen Kane"
    dict.vote( "The Avengers", 1 );   // Fred votes 1 on "The Avengers"
    dict.vote( "Citizen Kane", 10 ); // Fred votes 10 on "Citizen Kane"
    dict.vote( "Fargo", 10 );         // Alice votes 10 on "Fargo"

    // Prints out 1.0, the average of all votes for "The Avengers"
    cout << dict.getRating( "The Avengers" ) << endl;
    // Prints out 9.5, the average of all votes for "Citizen Kane"
    cout << dict.getRating( "Citizen Kane" ) << endl;

    char buf[ 100 ];
    // Copies "Fargo" into the buffer buf, because it has
// the highest overall rating, 10.
    dict.findBest( buf );
cout << "The movie to bet on is " << buf << "." << endl;

    return 0;
}

#ifndef __MOVIEDICT_H__
#define __MOVIEDICT_H__
 

1. Complete the header file above by adding a declaration for the MovieDict class.  The methods that need to go into the class are precisely those that are implied by the sample client above.  The private data should be chosen to allow a linked-list representation based on the Node struct.  All the information you need to create the header file should be given above.  But if you need to make additional assumptions about the class in order to answer this question, simply state your assumptions below.

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Give the implementation of the getRating method of MovieDict.  You may find the function strcmp helpful.  strcmp takes two strings as arguments.  It returns 0 when the strings are equal and nonzero when they are unequal.  Your function should attempt to deal gracefully with the case of trying to get the rating of a movie that isn't in the database.

 

 
 
 
 
 
 
 
 
 
 
 
 
 

3. Suppose that somewhere in my client program, I have the following:


    MovieDict m1;
    m1.vote( "Pi the Movie", 9 );
    // ... other stuff here
    MovieDict m2 = m1;

What potential dynamic memory problem can arise by doing this assignment?
 
 

4. What methods should I add to the MovieDict class to prevent it from potentially causing memory errors?

 

 
 
 
 
 
 

[4] Bonus Question 1:
Give at least four of the metasyntactic variable names mentioned in lecture this quarter.
 
 
 
 

[10] Bonus Question 2:
Suppose that we redefine the nodes we use in binary search trees as follows:
 

struct FancyNode
{
    int data;

    FancyNode *parent;
    FancyNode *left;
    FancyNode *right;
};