In addition to all concepts from Quiz 1 and Quiz 2,

You should be able to define or explain the following terms:

• abstract data types
• stacks and their operations
• queues and their operations
• depth-first search
• breadth-first search
• circular arrays (a.k.a. circular buffers)
• amortized analysis
• divide and conquer
• recursion trees
• merge sort and merge
• quick sort, partition, randomized quick sort, and pivot

You should be familiar with the following C++-related concepts:

• using new and delete for multi-dimensional arrays
• operator<

Practice problems

1. Consider the following (somewhat strange) Queue definition, TwoStackQueue, that uses two Stacks to represent the data in the queue:

       #ifndef TWOSTACKQUEUE_H_
       #define TWOSTACKQUEUE_H_
   
       #include "arraystack.h"
       #include "queue.h"
   
       template <typename T>
       class TwoStackQueue : public Queue<T> {
         private:
           ArrayStack<T> in;
           ArrayStack<T> out;
   
         public:
           void enqueue(T item);
           T dequeue();
           T getFront();
           int getSize();
           bool isEmpty();
       };
   
       #include "twostackqueue.inl"
   
       #endif
   

   (The TwoStackQueue constructor and destructor are both empty and not shown.)

   Using just the two Stacks in and out (and no other data), implement each queue function such that:

   • enqueue, getSize, and isEmpty each have O(1) worst-case running time.
   • dequeue and getFront each have O(n) worst-case but O(1) amortized running time.
   
   
2. Consider the following somewhat simplified map of Sharples:
   • Use depth-first search to find a path from the Entrance to the Fried food location. Carefully track the data used by depth-first search as the algorithm runs.
   • Use breadth-first search to find a path from the Entrance to the Fried food location. Carefully track the data used by breadth-first search as the algorithm runs.
   • How many distinct paths from the Entrance to the Fried food might be returned by different depth-first searches? Explain why.
   • How many distinct paths from the Entrance to the Fried food might be returned by different breadth-first searches? Explain why.
   
   
3. Consider the following algorithm, wackyMergeSort, similar to mergeSort:

       wackyMergeSort(A, n):
         if (n <= 1)
           return
         A1 = new array
         A2 = new array
         copy first two-thirds (2n/3)  of A into A1
         copy last  one-third (n-2n/3) of A into A2
         wackyMergeSort(A1, 2n/3)
         wackyMergeSort(A2, n-2n/3)
         merge(A1, 2n/3, A2, n-2n/3, A)  // merges sorted A1, A2 back into A
   

   • Is wackyMergeSort a correct sorting algorithm?
   • Draw a recursion tree for wackyMergeSort on an input of size n. For each node (recursive call) in the recursion tree, write the amount of work you expect to be done for just that recursive call to wackyMergeSort. Use Big-O notation for all parts of this problem, justifying (but not proving) your work.
   • How much total work is done per level in the recursion tree?
   • How many total levels are in the tree?
   • Overall, how much total work is done for wackyMergeSort for an input of size n?

Home Page