Exam 2 Review

The exam will consist of short-answer questions, multiple choice questions, understanding written code, and writing your own code. The emphasis is on reading and writing code, particularly with recursive code and code which manipulates binary search trees.

The review below, in addition to the code you wrote for your labs, are all fair game for the exam. This is intended to be comprehensive; there will be no material on the exam which isn't touched by either the labs or this review.

If you're pushed for time, my personal recommendation is to spend the majority of your time studying the code you wrote for your labs. The best next thing to look at would be the materal below in the same order as it is presented. Overall, my philosophy with programming is that reading and writing code are the best ways to learn, and my questions tend to reflect this.

Carryover

The questions below were not on the prior exam, though they were technically fair game. At least some of these are highly likely to be on this exam.

Consider the code below:

#include <iostream>
using namespace std;
class Des {
  public:
    Des(int x) { this->x = x; cout << x << endl; }
    ~Des() { cout << x << endl; }
  private:
    int x;
};

void test() {
  Des d(1);
}

int main() {
  Des* p = new Des(0);
  test();
  delete p;
  return 0;
}

If the above code is compiled and run, what is the output?

Name and describe two operations which are typical of a stack ADT.

Possible operations:
- push puts an item on top of the stack
- pop removes an item from the top of the stack
- top observes the top element of the stack without removing it
- Also will accept creating a new, empty stack
Name and describe two operations which are typical of a queue ADT.

Possible operations:
- enqueue adds an item to the back of the queue
- dequeue removes an item from the front of the queue
- Will also accespt the creation of a new, empty queue

Consider the following code:

#include <iostream>
using namespace std;
class Stack {
  public:
    Stack(); // creates a new, empty stack
    void push(int item); // adds an item to the stack
    int pop(); // removes an item from the stack
};

class Queue {
  public:
    Queue(); // creates a new, empty queue
    void enqueue(int item); // adds an item to the end of the queue
    int dequeue(); // removes an item from the front of the queue
};

int main() {
  Stack s;
  Queue q;

  s.push(1);
  s.push(2);
  s.push(3);

  q.enqueue(4);
  q.enqueue(5);
  q.enqueue(6);

  for(int x = 0; x < 3; x++) {
    cout << s.pop() << " " << q.dequeue() << endl;
  }
}

If the program above is compiled and run, what is the output?

3 4
2 5
1 6

Time Complexity Analysis

Name one reason why someone would prefer an equation in Big-O notation instead of terms like “efficient” or “fast”.

Some possible answers:
- Highly precise
- Speaks about how it behaves with respect to changing input sizes

Consider the code below. What is its time complexity?

void foo(int* array, int length) {
  int sum = 0;
  for(int x = 0; x < length; x++) {
    sum += array[x];
  }
  return sum;
}

O(N)

Consider the code below. What is its time complexity?

void foo(int* array, int length) {
  int sum = 0;
  for(int x = 0; x < length; x++) {
    for(int y = 0; y < length; y++) {
      sum += array[x];
      sum += array[y];
    }
  }
  return sum;
}

O(N^2)

Consider the code below. What is its time complexity?

// precondition: array is sorted
bool foo(int* array, int elem, int min, int max) {
  if (min <= max) {
    int mid = min + ((max - min) / 2);
    if (elem < array[mid]) {
      return foo(array, elem, min, mid - 1);
    } else if (elem > array[mid]) {
      return foo(array, elem, mid + 1, max);
    } else {
      return true;
    }
  } else {
    return false;
  }
}

O(log(N))

Recursion

Overall, you should be able to read and write recursive code. I have some examples in the questions below, but these are not comprehensive. Recursion is just as general as loops, so I cannot possibly give a comprehensive list of recursive programs, in much the same way that I cannot give a comprehensive list of programs that use loops.

What does it mean to be tail-recursive? Why is this important?

The last operation the function performs is a recursive call to itself. Smart compilers can automatically optimize such functions to use a constant amount of stack space (just like with iteration), so we aren't in danger of blowing the stack.

You should be able to take a tail-recursive algorthm and convert it to an iterative version. I will not ask about non-tail-recursive programs, since these need quite a bit of fairly tedious modification. As an example of this problem, consider the following tail-recursive program which would be fair game:

// precondition: length >= 1
int getMax(int* array, int length) {
  return getMax(array + 1, length - 1, array[0]);
}

int getMax(int* array, int length, int curMax) {
  if (length == 0) {
    return curMax;
  } else if (array[0] > curMax) {
    return getMax(array + 1, length - 1, array[0]);
  } else {
    return getMax(array + 1, length - 1, curMax);
  }
}

An iterative implementation is shown below, which mirrors the recursive version as closely as possible. Many alternative implementations are possible - an alternative is valid as long as it gets the same results on the same inputs, and doesn't use recursion.

// precondition: length >= 1
int getMax(int* array, int length) {
  int curMax = array[0];
  array = array + 1;
  length = length - 1;

  while (length != 0) {
    if (array[0] > curMax) {
      curMax = array[0];
      array = array + 1;
      length = length - 1;
    } else {
      curMax = curMax;
      array = array + 1;
      length = length - 1;
    }
  }

  return curMax;
}

Be able to convert an iterative algorithm to a recursive version. In general, it should be possible to convert to a tail-recursive version, though you will not be required to do so if you don't want. I may, however, give bonus points for tail-recursive versions. As an example of this kind of problem, consider the iterative program below:

// Gets the second to last element of a linked list.
// Precondition: the provided list contains at least two elements
int getSecondToLast(Node* list) {
  Node* prev2 = list;
  Node* prev1 = prev2->getNext();
  Node* current = prev1->getNext();

  while (current != NULL) {
    prev2 = prev1;
    prev1 = current;
    current = current->getNext();
  }

  return prev2->getInt();
}

One possible solution is below, which intentionally mirrors the iterative implementation as closely as possible. Many different possible solutions are possible; a solution is valid as long as it gets the same output on all inputs and uses recursion.

int getSecondToLast(Node* list) {
  return getSecondToLast(list, list->getNext(), list->getNext()->getNext());
}

int getSecondToLast(Node* prev2, Node* prev1, Node* current) {
  if (current != NULL) {
    return getSecondToLast(prev1, current, current->getNext());
  } else {
    return prev2->getInt();
  }
}

In a recursive setting, what does it mean to “blow the stack”?

We run out of memory on the stack (a stack overflow). Best case scenario, this will cause our program to crash.
Name one reason why someone would choose recursion over iteration.

Possible answers:
- Operating on a recursive data structure, so it's a more natural representation
- Connection to induction makes it easier to reason about whether or not an algorithm will terminate than with a loop
Name one reason why someone would choose iteration over recursion.

Possible answers:
- Fear of blowing the stack
- Unsure if the compiler is smart enough to make a tail-recursion optimization

Binary Search Trees

Provide definitions for the following terms, and be able to point them out in tree diagrams. For example, for a question regarding depth, you should be able to provide the depth of an arbitrary node in a tree.
- Node
- Edge
- Parent
- Child
- Leaf
- Internal Node
- Root
- Depth
- Level
- Full
- Complete
- Balanced
- Subtree
Definitions for these terms, along with example trees, are provided near the beginning of the slides for week 8, lecture 1.
What is the time complexity of addition / insertion / removal?

O(N)
If we could guarantee that a binary search tree had a particular property, then we could guarantee a better time complexity for addition / insertion / removal. Name the property.

For full credit, the most correct answer is balanced. Other possible answers are full and complete, though these aren't as correct (such trees are also balanced, which is where the performance gain comes from).
What data structure is needed for a breadth-first search?

A queue
What data structure is needed for a depth-first search?

A stack
Be able to provide the traversal order of a tree for the following (i.e., provide the order in which we'd process nodes):
- Breadth-first search
- Pre-order depth-first search
- In-order depth-first search
- Post-order depth-first search
Examples for each of these can be seen here.

Heaps

Both heaps and binary search trees are types of binary trees. However, operations on both have very different time complexities. Why?

Heaps are forced to be complete, so they always end up being balanced. In contrast, an arbitrary binary search tree may not be balanced, leading to trees which look more like linked lists (and behave more like linked lists with respect to time complexity).
For the enqueue operation on a heap, where is the element initially inserted? Why can't we always just leave the element in this position?

The element will be inserted in the last position in the last level of the tree, or as the leftmost element on a deeper level of the tree if the tree is already full. The element inserted may violate the heap property (i.e., have a value greater than that of the root), and so we may need to bubble up to move the element to its proper position in the tree.