[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?
   Binary search.  It chops off whole chunks of the array at every step.

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

 
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.

O(log(n))
 

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.

There are many possible answers to this question.  Here are some samples:

Will the number of students remain fixed, or change a lot over time?
    (If the number is fixed, I might want to implement my ADT using an array.  If it's going to change a lot, arrays can get inefficient and I'll want to use something more like a linked list.)

Is there a fixed upper bound on class size?
    (This can have a serious effect on my implementation.  If there is a small fixed upper limit, I'll definitely use an array.  If the upper limit is really big, arrays will be no good.  If there's no upper limit, obviously I can't use an array.  I can also use an upper limit for debugging, to make sure nobody tries to overfill the class.)

What information will be stored with each student?
    (This will allow me to write the struct of info associated with every student. )

How will this information be searched/accessed?
    (This will influence whether I should implement a simple collection or a dictionary.  If I'm implementing a dictionary, I'll need to figure out which piece of student information will act as the key.)

Will the information be searched frequently?
    (If there will be frequent searching, then I might want to choose an ADT that makes this fast.  For instance, I might use an array and keep the students sorted by name, which will greatly speed up searching for students by name.)

Note that questions like "should I use a linked list or array" and not valid, because they are questions about the implementation and not the specification.  Your job in this question was to ask questions of someone that will allow YOU to choose a good implementation.  You were not supposed to ask for an implementation.  Assume the person you're asking doesn't know anything about computers; they just know what information they'll need.

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

#include <iostream.h>

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

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

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

int Complicated::goAhead() {
    return 51;
}

Simple *getsimpleObject()
{
    return new Complicated();
}

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:
 

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

void printDir( Dir d )
{
    switch( d ) {
    case NORTH:
        cout << "north";
        return;
    case EAST:
        cout << "east";
        return;
    case SOUTH:
        cout << "south";
        return;
    case WEST:
        cout << "west";
        return;
    }
}

Using the numbers 0, 1, 2 and 3 instead of the contants NORTH, EAST, SOUTH and WEST is a serious violation of the abstraction barrier!!
 

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.
                               16
                              /  \
                            11    19
                           /     /  \
                          2    18    29
                           \        /
                            5     24

 
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

Preoder: 16 11 2 5 19 18 29 24
Inorder: 2 5 11 16 18 19 24 29 (should just be in sorted order)
Postorder: 5 2 11 18 24 29 19 16
 
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.

16 11 2 5 (and NULL, if you want to absolutely specific).

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.


class MovieDict
{
public:
    MovieDict();

    void vote( const char *name, int value );
    double getRating( const char *name );
    void findBest( char *buf );

private:
    Node *front;
};
 
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.


double MovieDict::getRating( const char *name )
{
    for( Node *cur = front; cur != NULL; cur = cur->next ) {
        if( strcmp( cur->name, name ) == 0 ) {
            return (double)( cur->sum_of_votes ) / (double)( cur->number_of_votes );
        }
    }
    return -1.0; // a safe value.
}
 

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?

You could get a dangling pointer if you did some operation that destroyed m2.front while not updating m1.front.  This is similar to the example presented in class about the need for a deep copy when assigning stacks.



4. What methods should I add to the MovieDict class to prevent it from potentially causing memory errors?
   
   To prevent all possible errors, the methods that should be added are:
       - An assignment operator
       - A copy constructor
       - A destructor
   In other words, we should make sure that MovieDict conforms to the Canonical Form.

[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;
};

// This is a pretty hard question.  Here's a piece of code that probably does the trick.
// The idea is to remember what direction you're traveling in and use that information 
// to decide what to do next.  I don't guarantee that this works, and I welcome comments
// about potential bugs.

enum Direction { NW, NE, SW, SE };

Direction upFrom( FancyNode *node )
{
    if( node->parent != NULL && node->parent->left == node ) {
        return NE;
    } else {
        return NW;
    }
}

void cheapInOrder( FancyNode *root ) 
{
    if( root == NULL ) {
        return;
    }

    FancyNode *cur = root;
    Direction dir = SW;

    while( cur != NULL ) {
        if( dir == NW ) {
            dir = upFrom( cur );
            cur = cur->parent;
        } else if( dir == NE ) {
            cout << cur->data << " ";
            if( cur->right != NULL ) {
                cur = cur->right;
                dir = SE;
            } else {
                dir = upFrom( dir );
                cur = cur->parent;
            }
        } else if( cur->left != NULL ) {
            cur = cur->left;
            dir = SW;
        } else if( cur->right != NULL ) {
            // There's a right child, and we're not coming from it.
            // Print out the current node and go there.
            cout << cur->data << " ";
            cur = cur->right;
            dir = SE;
        } else {
            dir = upFrom( cur );
        }
    }
}