Runtime complexity <= O(1) (possibly amortized)

• Empty()
• Begin(), End()
• Front(), PushFront(t), PopFront()
• Back(), PushBack(t), PopBack()
• Insert(I,t), Remove(I)
• All Iterator operations

Runtime complexity <= O(n), n = no of elements stored

• Clear()

• Size()
• Constructors and Destructor
• Assignment

Proper type

Operations

int       operator == (const Iterator& I2);
int       operator != (const Iterator& I2);
Iterator& operator = (const Iterator&);
const T&  operator *() const;
T&        operator *();
Iterator& operator ++();
Iterator  operator ++(int);

Bidirectional Iterator Interface

Proper Type

Forward Iterator

Additional Operations

Iterator& operator --();
Iterator  operator --(int);

Bidirectional Iterator plus

T&        operator [] (size_t i);
const T&  operator [] (size_t i) const;
"pointer" arithmetic

FSU sContainers

TVector, TList, TDeque

What do they all have in common?

FSU sContainers

TVector, TList, TDeque

What are the sContainer options that conform to runtime constraints:

The interface for fsu::TVector conforms to the constraints for sequential containers. The operations that distinguish TVector among all sContainers are highlighted in color.

Size() returns the number of elements in the vector, and Capacity() returns the number of elements of storage that is currently owned by the vector: the size of the "footprint".

SetCapacity(n) always establishes a footprint of exactly n elements. SetSize(n,t) expands the capacity if necessary to achieve size n, but never shrinks the capacity; new elements are initialized to t.

The plan shows that we are just putting a nice "face" on a C-array, managing memory for the client program. The client can manage the footprint in as much detail as desired via the "allocator" methods SetSize and SetCapacity. Note that SetSize is expansive only, whereas SetCapacity sets the footprint size precisely, whether increasing or decreasing from the current capacity.

The implementation plan for fsu::TVector::Iterator is to put a new interface on a raw pointer into the data array. Note that this is the classic unsafe & fast way to implement iterators. The classic safe & slow way is taken in fsu::TDeque::Iterator

The interface for fsu::TList conforms to the constraints for sequential containers. The operations that distinguish TList among all sContainers are highlighted in color.

The new idea facilitating the list is that of the dynamic link: with every data element, also store the address of the next data element and the previous data element. This way, elements of a list can be scattered anywhere in memory, so long as the link information is stored with the elements.

A list iterator needs to access an element of the list directly. The simplest way to do this is via the links in the list. The implementation plan is to provide a protected pointer to a current link that is accessed by the public methods and operators:

template <typename T>
class listiterator
{
  protected:
    link * currLink;  // pointer to current link in a list

  public:
    listiterator& operator ++();
    // ... 
} ;

By keeping the link pointers protected (in both list and list iterator), we are preventing a client from accessing the list structure, while providing access to the list data.

Maintaining the integrity of list structure while implementing all of the list and list iterator methods is fairly complicated and error-prone programming. Once implemented, however, the resulting generic list and iterator classes are extremely useful and at the same time extremely robust and client-friendly.

Our implementation for TDeque uses another item from classical data structures tradition: the circular array. (The STL version of deque uses a different implementation.) The essential ingredients are depicted in the slide. Here is the actual declaration of protected data from the TDeque class definition:

protected:
  T*           content;
  unsigned int content_size, beg, end;

Consistency between content and content_size must be maintained at all times: content_size is the size of memory allocated to the array content.

Algorithm Components

Required  & Optional

Required

Assumptions

Asserted Outcomes

Body

Proof

Optional

Execution Speed & Space Performance

• Algorithm for finding a value in a collection of values
• Collection must have "array-like" structure
  • random access to data through bracket operator
  • example containers: array, vector, deque
• Collection must be sorted
  • elements in increasing (or decreasing) order
• Idea: "Divide and Conquer"
• Efficiency:
  • very fast
  • no extra space required

• Three versions:
  • binary_search
  • lower_bound
  • upper_bound
• Assumptions:
  • collection v of data of type T and size sz
  • v is sorted (increasing order)
  • bracket operator provides random access to elements of v
  • element t of type T
• Outcomes:
  • binary_search: return true if t is in v, false if not
  • lower_bound: return smallest index i such that t <= v[i]
  • upper_bound: return smallest index i such that t < v[i]

lower_ bound

Binary Search Code

unsigned int lower_bound (T* v, unsigned int size, T t)
{
  unsigned int   low  = 0;
  unsigned int   mid;
  unsigned int   hih = size;
  while (low < hih)
  {
    mid =  (low + hih) / 2;  
    if (v[mid] < t)          
      low = mid + 1;         
    else                     
      hih = mid;             
  }  
  return low;
}

upper_bound

Binary Search

unsigned int upper_bound (T* v, unsigned int size, T t)
{
  unsigned long   low = 0;
  unsigned long   mid;
  unsigned long   hih = size;
  while (low < hih)
  {
    mid =  (low + hih) / 2;
    if (t < v[mid]))
      hih = mid;                
    else                        
      low = mid + 1;            
  }  
  return low;
}

binary_search

Algorithm

bool binary_search (T* v, unsigned int size, T t)
{
  unsigned int lb = lower_bound(v,t);
  if (lb < size)
  {
    if (t == v[lb])
    {
      return true;
    }
  }
  return false;
}

• Loops
  • Loop termination
  • State entering loop
  • State exiting loop
• Loop invariants
  • Statements that are true in each iteration of loop
  • Analogous to the "induction" part of mathematical induction

boolean sequential_search
{
  T item = first(L);
  // Before entering loop: t has not been found
  while (item is in L)
  {
    // loop invariant: current item has not been tested
    if (t == item)
      return true;
    // loop invariant: t is not current item
    item = next(L);
  }
  return false;
}

unsigned int lower_bound (T* v, unsigned int max, T t)
{
  unsigned int   low  = 0;
  unsigned int   mid;
  unsigned int   hih = max;
  while (low < hih)
  {
    // (1) low < hih
    // (2) v[low - 1] < t (if index is valid)
    // (3) t <= v[hih]     (if index is valid)
    mid =  (low + hih) / 2;  
    if (v[mid] < t)          
      low = mid + 1;         
    else                     
      hih = mid;             
    // (4) low <= hih
    // (5) hih - low has decreased
    // (6) v[low - 1] < t (if index is valid)
    // (7) t <= v[hih]     (if index is valid)
  }  
  return low;
}

g(n) <= O(f(n)) iff there exist positive constants c and n₀ such that 0 <= g(n) <= cf(n) for all n >= n₀
"g is asymptotically bounded above by f "

g(n) >= Ω(f(n)) iff there exist positive constants c and n₀ such that 0 <= cf(n) <= g(n) for all n >= n₀
"g is asymptotically bounded below by f "

g(n) = Θ(f(n)) iff there exist positive constants c₁, c₂, and n₀ such that 0 <= c₁f(n) <= g(n) <= c₂(n) for all n >= n₀
"g is asymptotically bounded above and below by f "

Stated in terms of Big O, Big Omega, or Big Theta

Independent of hardware

Independent of programming language

Steps:

1. n = some measure of size of input to the algorithm
2. find an atomic notion of computational activity to count
3. find f(n) = the number of atomic activities done by the algorithm for input of size n
4. complexity of algorithm <= O(f(n)) (or >= Ω(f(n)) or = Θ(f(n)))

for (i = 0; i < n; ++i)
{
  // 3 atomics in loop body
}

for (i = 0; i < n; ++i)
{
  // 3 atomics in loop body
  if (condition) break;
}

for (i = 0; i < n; ++i)
{
  // 3 atomics in loop body
}
for (i = 0; i < n; ++i)
{
  // 5 atomics in loop body
}

• Complexity <= O(3n + 5n) <= O(n)

for (i = 0; i < n; ++i)
{
  // 2 atomics in outer loop body
  for (j = 0; j < n; ++j)
  {
    // 3 atomics in inner loop body
  }
}

Algorithm Complexity - Binary Search

stack ->
---------
1
1 2
1 2 5
1 2 5 6
1 2 5 6 8
1 2 5 6
1 2 5
1 2
1
1 3
1 3 9
1 3 9 7
1 3 9
1 3 9 12
1 3 9 12 10
1 3 9 12 10 11

<- queue
---------
1
2 3 4
3 4 5 6
4 5 6 9 10
5 6 9 10
6 9 10
9 10 8
10 8 7 12
8 7 12 11
7 12 11
12 11
11

Analysis of Quicksort
The partition routine is called at most one time for each element
All comparisons are done inside the partition routine
Therefore algorithm runtime is O(n + x), where x is the total number
of comparisons made by the partition routine
Worst case: x = T(n2)
Average case: E[x] <= O(n log n)

Theory of comparison sorts: runtime lower bound, proof
Key Comparison Sorts Theorem.

Any comparison sort requires O(n log n) comparisons in the worst case.
Proof - Use decision tree for the algorithm
Binary tree with node for each comparison, leaf for each solution
Each leaf represents a permutation of the input range
Sort of a particular data set is represented by a descending path to a leaf
Length of this path = number of comparisons made by the sort
n! leaves
Depth >= log2 n!
log2 n! >= O(n log n) by Stirlings formula

Sort             Runtime  Runspace  Stability  Generic
Insertion Sort   O(n2)   in place  yes   Bidirectional
Selection Sort   T(n2)   in place  no   Forward
Heapsort   T(n log n)  in place  no   Random Access
Merge Sort   T(n log n) + T(n)   yes   Random Access
Quicksort   WC = T(n2)
   AC = T(n log n) + T(n)   maybe  Smart Bidirectional
Counting Sort   T(n + k) + T(k)   yes   function object argument
Radix Sort   T(d(n + k)) + T(k)   yes   ??
Bit Sort   T(n) + T(n)    yes  Use funObj in counting sort

n = size of range to be sorted
k = upper bound of size of integers to be sorted
d = loop length in radix sort
Estimates are worst case unless noted otherwiseiterator category, value type)

Algorithm Complexity
Loops  T(3n) = T(n)
Loops w/break <= O(n)
Loops in Seq <= O(3n + 5n) <= O(n)
Loops nested <= O((2 + 3n)n) <= O(2n + 3n2) <= O(n2)
Loops nested = T((2 + 3n)n) = T(2n + 3n2) = T(n2)
Sequen Search = T(n)  Simplified
Sequen Search <= O(n)
Binary Search = T(log n)

Requirement      Actual
PopBack(), Clear()
Front(), Back()
Empty(), Size(), Capacity()
bracket operator []      O(1)     T(1) 
PushBack(t)       Amortized O(1)     Amortized T(1) 
SetSize(n), SetCapacity(n)      O(n)     O(n) 
assignment operator =      O(n), n = Capacity()     T(n), n = Capacity() 
Constructors, Destructor
O(n), n = Capacity()      T(n), n = Capacity() 
Display(os,ofc)            T(n), n = Size() 
Dump(os)             T(n), n = Capacity() 

Traversal  Type Container Visit Vertex
Inorder     DFS 
Preorder    DFS Stack  Arrival
Postorder  DFS Stack  Departure
Levelorder BFS Queue  Departure

template< class I >
  void g_quick_sort(I p, I r)  // got assistance
  {
   if (r - p > 1)
   {
      I q = PartitionA(p,r);
      g_quick_sort(p,q);
      g_quick_sort(q+1,r);
    }
  }
template< class I >  // got assistance
  I PartitionA(I p, I r)  
  {
   
 I i = p;
  --r;
  
   for (I j = p; j != r; ++j)
   {
    if ( *j <= *r )
    {
      Swap(*i , *j);     
      ++i;
    }
   }
   // the last place requires no test:
   Swap(*i, *r);
   return i;
  }

// merge
  template < class I, class T >
  void merge(I p, I q, I r)
  {
    T B;                            // temp space for merged copy of A
    g_set_merge(p, q, q, r, B);     // merge the two parts of A to B
    g_copy(B.Begin(), B.End(), p ); // copy B back to A[p,r)
  }

  template < class I > 
  void g_merge_sort(I p,I r)
  {
     size_t size(r - p);
  if(size<2) return;
    
   I q = p + size/2;       // integer arithmetic
      g_merge_sort(p , q);    // recursive call
      g_merge_sort(q,  r);    // recursive call
      fsu::merge( p, q, r );  // defined below
   
  }

selection
 template < class ForwardIterator , class Comparator >
  void g_selection_sort (ForwardIterator beg, ForwardIterator end, Comparator cmp)
  {
    ForwardIterator i, j, k;
    for (i = beg; i != end; ++i)
    {
      k = i;
      for (j = i; j != end; ++j)
        if (cmp(*j , *k))
          k = j;
      Swap (*i, *k);
    }
  }

heap
template <class I, class P>
  void g_heap_sort (I beg, I end, const P& LessThan)
  // Implements heapsort for the iterators
  // Heapsort has the following attributes:
  //   * fast:     runtime O(size*log(size))
  //   * in-place: the sort happens in the space implied by the iterators
  //   * NOT stable -- the original order of objects a, b may change when
  //                   a == b
  // pre:  I is a random access iterator class (operator [] and "pointer" arithmetic)
  //       T is the value_type of I
  //       P is a predicate class for type T
  // post: the range of values specified by the iterators is ordered by LessThan,
  //       i.e., true = LessThan(a,b)  <==>  a comes before b in the container
  {
    if (end - beg <= 1)
      return;
    size_t size = end - beg;
    size_t i;
    // push elements onto heap one at a time
    for (i = 1; i < size; ++i)
    {
      g_push_heap(beg, beg + (i + 1), LessThan);
    }
  
    // keep popping largest remaining element to end of remaining array
    for (i = size; i > 1; --i)
    {
      g_pop_heap(beg, beg + i, LessThan);
 // XC(beg[0],beg[i-1]) and restructure beg[0..i-2] as POT
    }
  } // end g_heap_sort()

Runtime Complexity of Iterator Operations
Theorem. Assume that bt is a binary tree of type TBinaryTree<T> and
i is an iterator of type
TBinaryTreePreorderIterator<T>, TBinaryTreeInorderIterator<T>,
TBinaryTreePostorderIterator<T>, or
TBinaryTreeLevelorderIterator<T>.
Then the loop
for (i = bt.Begin(); i != bt.End(); ++i){}

has runtime complexity T(bt.Size()).
Corollary. For any of the four iterator types, operator ++() has amortized runtime complexity T(1).

Lemma 1. For the cases of preorder, inorder, and postorder,
  the loop in the Theorem makes exactly 2*size edge steps.

Lemma 2. For the case of levelorder, the loop in the
  Theorem invokes no more than 3*size queue push/pop operations.

• Apply to ranges
• Omit size change (step 1)
• Specified by random access iterators
• Currently support:
  • arrays
  • TVector<T>
  • TDeque<T>
• Source code file: gheap.h
• Test code file: fgss.cpp

template <class T>
void g_XC (T& t1, T& t2)
{
  T temp(t1);
  t1 = t2;
  t2 = temp;
}

void preorder (TNode<T>* root, void (TNode<T>*) visit)
{
  if (root == 0)
    return;
  visit(root);                   // visit node before visits to children
  preorder(root->lchild, visit); // recursive call
  preorder(root->rchild, visit); // recursive call
}

template < typename T >
void TBinaryTreeInorderIterator<T>::Initialize (const TBinaryTree<T>& b)
{
  // enter tree at root
  nav_ = b.Root();
  // slide to leftmost node
  while (nav_.HasLeftChild())
    ++nav_;
}

// C c = input container
sorted_list<T> L;
C::Iterator i;
for (i = c.Begin(); i != c.End(); ++i)
  L.Insert(*i);
// now L is a sorted list of all elements of c
sorted_list<T>::Iterator j;
for (i = c.Begin(), j = L.Begin(); j != L.End(); ++i, ++j)
  *i = *j;
// now c is sorted

template < class ForwardIterator >
void g_selection_sort (ForwardIterator beg, ForwardIterator end)
{
  ForwardIterator i, j, k;
  for (i = beg; i != end; ++i)
  {
    k = i;
    for (j = i; j != end; ++j)
      if (*j < *k)
        k = j;
    swap (*i, *k);
  }
}

• in place
• not stable
• run time = Θ(n²)
• requires forward iterators

template <class RAIter>
void g_heap_sort (RAIter beg, RAIter end)
{
  if (end - beg <= 1)
    return;
  size_t size = end - beg, k;

  // push elements onto heap one at a time
  for (k = 0; k < size; ++k)
    g_push_heap(beg, beg + (k + 1));
   
  // keep popping largest remaining element to end of remaining range
  for (k = size; k > 1; --k)
    g_pop_heap(beg, beg + k);
}

Classic Quicksort

Theorem. Any comparison sort requires Ω(n log n) comparisons in the worst case.

Proof.

• Use decision tree for the algorithm
• Binary tree with node for each comparison, leaf for each solution
• Each leaf represents a permutation of the input range
• Sort of a particular data set is represented by a descending path to a leaf
• Length of this path = number of comparisons made by the sort
• n! leaves
• Depth >= log₂ n!
• log₂ n! >= Ω(n log n) by Stirlings formula