In addition to all concepts from Quiz 1,

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

• Algorithmic analysis (e.g., how to count steps, how to evaluate loops)
• Pseudocode (both interpreting and writing)
• Asymptotic analysis and Big-O notationg
• Emperical analysis
• Amortized analysis
• Constant, logarithmic, linear, quasilinear (n lg n), 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 :) )

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
• Abstract (or pure virtual) classes
• Templates
• this pointer

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 replaceItem(int i, T val) function that replaces the existing value at position i with val. It should return the previously held value. Do the same for the CircularArrayList class


4. Define replaceItem for a templated LinkedList implementation. Compare and contrast the expected run time with the ArrayList implementation


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. In class, we defined a Queue using various List implementations. Let's flip this around. Consider the following (somewhat strange) List definition, QueueList, that uses an awesomely cool MagicQueue to represent the data in the list. (Note that the details of MagicQueue are not given, but are also unnecessary given what you know about interfaces. Professor Danner suggests you imagine it is really a team of corgis managing a queue of cattle):

    
       #ifndef QUEUELIST_H_
       #define QUEUELIST_H_
    
       #include "list.h"
       #include "magicqueue.h"
    
       template <typename T>
       class QueueList : public List<T> {
         private:
           MagicQueue <T> values;
   
         public:
           QueueList();
           ~QueueList();        
           void insertAtHead(T item);
           void insertAtTail(T item);
           int getSize();
           bool isEmpty();
           // ... etc.  All List methods are declared here
       };
    
       #include "queuelist.inl"
    
       #endif
   

   Using the above declarations, complete an implementation for the methods getSize(),insertAtHead(T item), and removeTail(). Your answers should be written as they would appear in queuelist.inl, paying attention to the scope and template operators. Once complete, describe the O() of each of your implementations. Again, the details of MagicQueue are not important; you should assume it implements a Queue interface properly in O(1) 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.
   
   

Home Page