Practice Final 3 Solutions

Q1) Short answer

a) 30

b) BSTs for learn, hasty, and arches are shown below. flown is not possible.

The best case occurs when no collisions, each value has a distinct hash code. Insert single value = O(1), insert N values = O(N).
The worst case occurs when every insert is a collision, each value has same hash code, all values end up in one list. Insert single value = O(len) (list len initially 0, grows to N), insert N values = O(N^2).

Q2) Classes

  private:
    string *_array;
    int _capacity, _numFilled;

RandomBag::RandomBag(int cap) {
    _capacity = cap;
    _numFilled = 0;
    _array = new string[_capacity];
}

RandomBag::~RandomBag() {
    delete[] _array;
}

bool RandomBag::isEmpty() const {
    return _numFilled == 0;
}

string RandomBag::choose() {
    if (isEmpty()) {
        error("Cannot choose from empty bag!");
    }
    int index = randomInteger(0, _numFilled-1);
    string name = _array[index];
    _array[index] = _array[--_numFilled]; // replace with last, compact array
    return name;
}

void RandomBag::add(string name) {
    if (_numFilled == _capacity) {
        choose(); // discard random name
    }
    _array[_numFilled++] = name;    // new name added to end
}

Q3) Recursive backtracking

bool canMorph(string soFar, string target, Lexicon& lex) {
    if (soFar == target) {
        return true;    // success!
    }
    if (!lex.contains(soFar)) {
        return false;   // failure
    }
    for (int i = 0; i < soFar.length(); i++) {
        char orig = soFar[i];
        if (orig != target[i]) {
            soFar[i] = target[i];   // choose
            if (canMorph(soFar, target, lex)) {
                return true;
            }
            soFar[i] = orig;        // unchoose
        }
    }
    return false;         // backtrack on failure
}

Q4) Linked lists

ListNode *extractStrand(ListNode*& input) {
    if (input == nullptr) {
        return nullptr;
    }
    ListNode *head, *tail;
    head = tail = input;    // initial strand is frontmost node
    input = input->next;
    while (input != nullptr) {
        ListNode *cur = input;
        if (cur->value <= head->value) {
            input = input->next;
            cur->next = head;   // prepend to strand
            head = cur;
        } else if (cur->value >= tail->value) {
            input = input->next;
            tail->next = cur;   // apppend to strand
            tail = cur;
        } else {
            break;
        }
    }
    tail->next = nullptr;   // terminate strand
    return head;
}

Q5) Trees

int deleteMin(BSTNode*& t) {
    if (t->left == nullptr) {   // if no left subree, t is min node
        int min = t->value;
        BSTNode *trash = t;
        t = t->right;   // replace min with right child (perhaps nullptr)
        delete trash;
        return min;
    } else {
        return deleteMin(t->left); // min will be in left subtree
    }
}

The iterative alternative below requires differential handling when min node is root versus not.

int deleteMin(BSTNode*& t) {
    BSTNode *parent = nullptr;
    BSTNode *cur = t;
    while (cur->left != nullptr) { // iterate down to min node
        parent = cur;
        cur = cur->left;
    }
    int min = cur->value;
    BSTNode *trash = cur;
    if (parent == nullptr) {
        t = cur->right;             // replace min if root
    } else {
        parent->left = cur->right;  // replace min if not root
    }
    delete trash;
    return min;
}

b) If the pointer is passed by value instead of by reference, changes to t inside the function will not persist. The min node is still correctly identified, memory deallocated, and min value is returned. However, the pointer to min node (wherever it is in tree) is not updated and continues to point to min node and that memory is now deleted, oops!

A correct version of deleteMin(t) would delete root node 5 and replace with right child 8. If t is not passed by reference, t is unchanged and still points to the (now-deleted) 5.

If deleteMin is recursive, every input tree is affected. If deleteMin operates iteratively, only an input tree where the min node is root is affected.