Practice Final 7 Solutions

Question 1: BadTree Class

This question involved fleshing out a BadTree class and involved dynamic memory management, a bit of string processing, and working with an array representation for binary trees. One could imagine this evolving into a full-on programming assignment with several other functions.

There are many possible small variations on this solution. Note that some of the error checking and other requirements (e.g., the checks for out-of-bounds array accesses, ensuring we only expand when we know we will be adding a node successfully, and ensuring that we don't hop over any empty spaces to add a node that's totally detached from the tree) are prone to fairly subtle errors.

BadTree.h

...

// Data type for array.
int *_array;

// New member variables.
int _capacity;  // length of array
int _numNodes;  // number of nodes in tree

BadTree.cpp

BadTree::BadTree() {
  _capacity = kInitialCapacity;
  _numNodes = 0;

  _array = new int[_capacity];
  for (int i = 0; i < _capacity; i++) {
    _array[i] = kEmptyCell;
  }
}

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

void BadTree::set(string pathString, int value) {
  int index = 0;

  for (int i = 0; i < pathString.length(); i++) {
    // Before moving left or right, ensure we're at a valid node.
    if (index >= _capacity) {
      error("Exceeded _capacity prematurely in set()!");
    } else if (_array[index] == kEmptyCell) {
      error("Fell off tree prematurely in set()!");
    }

    if (pathString[i] == 'L') {
      index = 2 * index + 1;
    } else {
      index = 2 * index + 2;
    }
  }

  if (index >= _capacity) {
    expandArray(index + 1);
  }

  // It's critical not to increment the node count unless
  // the cell had been empty.
  if (_array[index] == kEmptyCell) {
    _numNodes++;
  }

  _array[index] = value;
}

// Returns, in O(1) time, the # of nodes in the tree
// (# of occupied cells in _array)
int BadTree::size() const {
  return _numNodes;
}

// Returns, in O(1) time, the # of unused cells in _array.
int BadTree::wastedSpace() const {
  return _capacity - _numNodes;
}

void BadTree::expandArray(int newLength) {
  if (newLength <= 0) {
    // This particular check is primarily aimed at future-proofing the code.
    error("Invalid newLength in expandArray()!");
  } else if (newLength <= _capacity) {
    error("newLength is no larger than _capacity in expandArray()!");
  }

  int *newArray = new int[newLength];

  for (int i = 0; i < _capacity; i++) {
    newArray[i] = _array[i];
  }
  for (int i = _capacity; i < newLength; i++) {
    newArray[i] = kEmptyCell;
  }

  delete [] _array;
  _array = newArray;
  _capacity = newLength;
}


Question 2: Backtracking and Linked Lists: perturb()

For this question, there was one pruning case: the situation where the string we have built so far is not a prefix to any of the strings in our lexicon. The wrapper function was provided on the exam; the recursive helper function below was the only function to be implemented for this question.

As with many of the questions on this exam, there are many possible subtle variations on this solution.

int perturb(Node *head, int k, string soFar, Lexicon& lexy, Set<string>& results) {
  if (!lexy.containsPrefix(soFar)) {
    return 0;
  }

  if (head== nullptr) {
    if (lexy.contains(soFar)) {
      results.add(soFar);
      return 1;
    } else {
      return 0;
    }
  }

  int count = perturb(head->next, k, soFar + char(head->data + k), lexy, results) +
              perturb(head->next, k, soFar + char(head->data - k), lexy, results);

  return count;
}


Question 3: Wacky Ternary Tree Traversal

This question gave everyone a chance to demonstrate their understanding of recursive binary tree processing functions. It was designed to reward those who have cultivated a solid understanding of the tree traversals covered in class and who were therefore able to trace through a novel, but similar, algorithm.

Solution:

54 23 63 19 50 33 55 44 21 92 84 17


Question 4: Binary Tree Coding: treeCut()

As with many of the questions on this exam, there are many possible subtle variations on this solution.

void treeCut(Node *root, int target, Set<Node *>& results) {
  if (root == nullptr) {
    return;
  }

  Node *leftChild = root->left;
  Node *rightChild = root->right;

  if (root->data == target) {
    results.add(root);
  }

  if (root->left != nullptr && root->left->data == target) {
    root->left = nullptr;
  }

  if (root->right!= nullptr && root->right->data == target) {
    root->right = nullptr;
  }

  treeCut(leftChild, target, results);
  treeCut(rightChild, target, results);
}


Question 5: Hash Tables and Graphs

a) Hash Tables:

r a d i c a l - d o d o
0 1 2 3 4 5 6 7 8 9 10 11

b) BFS:

  • P A R T I E S:  yes
  • P I R A T E S:  yes
  • P A S T I E R:  yes
  • T R A I P S E:  no
  • T R A P I E S:  yes

c) DFS:

  • P A R T I E S:  no
  • T A P R I S E:  yes
  • T R A P I S E:  no
  • T R I P S E A:  yes
  • T R I P E A S:  yes (*)

(*) That last one (T R I P E A S) might be surprising, but it's correct.