In addition to all concepts from Quiz 1,

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

• Asymptotic analysis and Big-O notation
• Emperical analysis
• Amortized analysis
• Constant, logarithmic, linear, quasilinear, quadratic, and exponential functions
• Induction
• Correctness of an algorithm
• Loop invariant
• Abstract data types, interface, implementation
• The List interface, including implementaiton details and runtime analysis using array lists, linked lists, and circular array lists
• Stack interface and operations
• Queue interface and operations
• Depth-first and breadth-first search
• Segmentation fault (You probably know this one by heart :) )
• Divide and conquer
• Recursion trees
• Merge sort and merge
• Quick sort, partition, randomized quick sort, and pivot
• Dynamic memory management and responsibilities

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

• new and delete for basic types, one-dimensional arrays, and two-dimensional arrays
• Class Destructors
• Pointer/array equivalence
• Exceptions (how to throw exceptions)
• Abstract (or pure virtual) classes
• Templates
• this pointer
• Basic uses of gdb (I won't test knowledge of commands)

Practice problems

1. Prove that 41*n^2 + 12n - 1 is O(n^2).


2. Using induction, prove that 0^2 + 1^2 + 2^2 + ... + n^2 is less than or equal to n^3 for all non-negative integers n.


3. Declare and implement a templated ArrayList removeItem(int i) function that, given a position i (indexed from 0), removes the ith item from an ArrayList. Do the same for the CircularArrayList class


4. Declare and implement a templated LinkedList removeItem(int i) function that, given a position i (indexed from 0), removes the ith item from a LinkedList.


5. Write a program that prompts the user for an integer n, then reads n strings into an array of strings stored on the heap, prints true if the array is sorted and false otherwise, and then frees the memory on the heap. As part of this program declare and implement a templated boolean isSorted(T* a, int n) function that, given a pointer to an array a and the length of that array n, returns true if the array is sorted and false otherwise.


6. 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.
   
   
7. 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.
   
   
8. 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