CS245 - Comp Sci II Chapter 10

Chapter 10 - Process III: Algorithms

OBJECTIVES

Investigate several ways of searching for an element in a list
Learn how to design functions that call themselves.
Design and implement an array-like class to represent lists of integers.
Discuss measures we can use to express the time it will take for an algorithm to run.
Compare the efficiency of two algorithms that sort a list of elements.

10.1 Searching for an element in a list

Finding the Smallest Element

Receives: arr - array of integers [0..end],start - index in range [0..end]
Returns: index of smallest element in arr[start]..arr[end]

int FindMin(IntArray arr, int start, int end)
{
      int min = arr[start];
      int where = start;

      for (int j = start + 1; j <= end; j++)
     {
            if (arr[j] < min)
           {
                min = arr[j];
                where = j;
           }
     }
     return where;
}

Finding a Particular Element (I)

Receives: arr - array of integers [0..end], match - an integer
Returns: pos - index of element match in arr[0]..arr[end]; -1 if no match found

int Find(IntArray arr, int match, int end)
{
      for (int j = 0; j <= end; j++)
           if (arr[j] == match)
                return j;
      return -1;
}

10.2 Divide and Conquer: Finding a Particular Element (II)

1) Find a phone number, given a name
2) Find a name, given a phone number.

int BinSearch (SortedArray arr, int match, int start, int end)
{
     if (start == end)
          return start;
     else
     {
          int middle = (start + end) / 2;
          if (match < arr[middle])
              return BinSearch(arr, match, start, middle-1);
          else if (match > arr[middle])
              return BinSearch(arr, match, middle+1, end);
          else
              return middle;
      }
}

Recursion

algorithms finite sequence of clear instructions that can be performed in a finite length of time

recursive algorithm algorithm which moves ahead by applying itself to a smaller part of the problem

recursive function - function that calls itself

Recursive Functions must have:

1) an exit case (trivial case)
2) one or more recursive cases, in which the problem is reduced to a simpler problem

ex. find N!

Binomial Theorem & Combinations
C(n,k) = C(n1, k) + C(n1, k1)
= 1 if n = k
= 1 if k = 1

Towers of Hanoi

10.3 Safer Arrays: The IntArray Class

//
INTARRAY.H 

// An array of integers, with boundschecking and careful memory management.

#include <iostream.h>

class IntArray
{
 friend ostream& operator<< (ostream& os, const IntArray& a);
public:
           IntArray();   // Construct a 10element IntArray of zeros
           IntArray(int n);   // Construct a zero IntArray of size n
           IntArray(const IntArray& a); // Copy constructor
          ~IntArray() {delete data;}; // inline function to delete the array of data

          Length() {return (upper + 1);}; // inline function which returns actual length of array

           int& operator[] (int I) const;
           IntArray& operator= (const IntArray& a);

private:
          int upper;   // the upper bound on array indices
          int* data;   // ptr to the array elements (indices 0 .. upper)
};

The copy constructor for an object is invoked:

1) an object is defined to have the value of another object of the same type
2) an object is passed to a function by value
3) an object is returned by a function

ex.

 IntArray ZeroTail(IntArray arr, int end)  // 2 here
 {
  IntArray newArray = arr;                            // 1 here
  for (int j = end; j < Length(arr); j++)
          NewArray[j] = 0;
  return newArray;                                       // 3 here
 }

The copy constructor for a type TypeName is declared with a reference argument:

TypeName (const TypeName&);

If you design a class with pointers in its member data, it is always a good idea to provide the class with its own copy constructor, assignment operator, and destructor.

Defining Safe Arrays

// INTARRAY.CPP
#include <iostream.h> // for cerr
#include <stdlib.h> // for exit
#include "INTARRAY.H"
ostream& operator<< (ostream& os, const IntArray& a)
{
for (int I = 0; I <= a.upper; I++)
os << a.data[i] << '\t';
return os;
}

IntArray::IntArray()
// Construct a 10element IntArray of zeros.
{
upper = 9;
data = new int[upper + 1];
if (data == 0)
{
cerr << "Out of memory in IntArray()" << endl;
exit(1);
}
else
for (int I = 0; I < 10; I++)
data[i] = 0;
}

IntArray::IntArray(int n)
// Construct a zero IntArray of size n.
{
if (n <= 0)
{
cerr << "Illegal size argument (" << n << ") in IntArray(int n)" << endl;
exit(1);
}
else
{
upper = n 1;
data = new int[n];
if (data == 0)
{
cerr << "Out of memory in IntArray()" << endl;
exit(1);
}
else
for (int I = 0; I < n; I++)
data[i] = 0;
}
}

IntArray::IntArray(const IntArray& a)
// Copy constructor
{
upper = a.upper;
data = new int[upper + 1];
if (data == 0)
{
cerr << "Out of memory in IntArray()" << endl;
exit(1);
}
else
for (int I = 0; I <= upper; I++)
data[i] = a.data[i];
}

int& IntArray::operator[] (int I) const
// overload of subscript operator
{
if ((I < 0) || (I > upper))
{
cerr << "Illegal array index [" << I << ']' << endl;
exit(1);
}
return (data[i]);
}

IntArray& IntArray::operator= (const IntArray& a)
// Assign one array to another
{
int u = ((a.upper < upper) ? a.upper : upper);

if (a.upper != upper)
cerr << "Size mismatch: (" << upper << ") = (" << a.upper << ')' << endl;
for (int I = 0; I <= u; I++)
data[i] = a.data[i];
return *this;
}

10.4 Sorting

void SelectionSort(IntArray& arr, int start, int end)
{
int pos;
for (j = start; j < end; j++)
{
pos = FindMin(arr, j, end);
Swap(arr[j], arr[pos]);
}
}

10.5 Analysis of Algorithms

Selection Sort: n-j+1elements inspected each time FindMin is called --
n + (n-1) + ... + 2 + 1 = (n+1)(n/2) ~ n² inspections

Big O

Efficiency

time vs space	size of data
initial arrangement of data	language used
generated machine code	speed of computer

1) Count # of steps
2) Count # of operations
3) Count "most costly" operations
4) Count # of times critical steps are executed

Definition The dominant segment of a program is that collection of steps that consume the most time (measured by # of times they are executed). The dominant segment often occurs within the innermost loop and/or the most deeply nested calling level for a method.

Definition The complexity of an algorithm is the number of times the dominant operation in the dominant segment is performed

Definition The worst-case complexity of an algorithm is the maximum number of times the dominant operation can be performed. the average-case complexity is the average number of times the dominant operation in the dominant segment would be performed for all possible arrangements of the input data. The best-case complexity is the minimum number of times the dominant operation in the dominant segment can be performed.

Algorithm Growth Rates

growth rate part of formula that varies with problem size
O(1) constant; O(log(N)) logarithmetic; O(N) linear;
O(Nlog(N)); O(N²) quadratic

Estimating the Growth Rate of an Algorithm

1. Sequence simple statements & sequence of simple statements (O(1))
2. Decision if; ifelse; case (Big O of the most complex branch)
3. Loop counting loop (FOR, WHILE) vs. constant loop

(Big O of inner steps * number of loops)

        for (OuterCounter = 1; OuterCounter <=  N; OuterCounter++)
           for (InnerCounter = 1; InnerCounter <= OuterCounter; InnerCounter++)

Multiplicatively controlled loop

      Control = 1;
      while (Control <= N) 
 {
                 :                       O(log(N))
         Control := 2 * Control
 }

Some Examples of Performance Prediction

Factorial	O(N)
Reverse of a String	O(N * O(TextConcatenate)
Permuations of a set	O(N!)
Recursive binary search	O(log(N))
Recursive merge/sort	O(N log(N))

MAINTAINING A DYNAMIC TABLE

phone list table key part & value part

ADT Create, Update, Search, Delete, Report

Unordered Array vs. Ordered Array

UNORDERED ORDERED

Create	O(1)	O(1)
Update	O(1)	O(N)
Search	O(N)	O(Log(N))
Delete	O(N)	O(N)
Report	O(N Log(N))	O(N)

10.6 Faster Sorting

Sequential Search - O(n)
Binary Search - O(log n)
Selection - O(n²)

void QuickSort (IntArray& arr, int start, int end)
{
      if (start < end)
      {
           int split = Partition(arr, start, end);
          QuickSort(arr, start, split);
          QuickSort(arr, split+1, end);
       }
}

int Partition (IntArray& arr, int start, int end)
{
      int top = end + 1;
      int bottom = start -1;
      int pivot = arr[start];
      while (top > bottom)
      {
          do 
              { bottom++; }
          while (arr[bottom] < pivot);
          do
              { top--;  }
          while (arr[top] > pivot);
          Swap(arr[top], arr[bottom]);
      }
      Swap(arr[top], arr[bottom]);
      return top;
}

Recursive MergeSort

        IF Size(List) > 1 
           Split(List, first half, second half)
           MergeSort(first half of List)
           MergeSort(second half of List)
           Merge(two halves of List)

Empirical Evaluation of Sorting Algorithms (100 Integers)

Sorting Algorithm	Run Time - List in Random Order	Run Time - List in Ascending Order
Selection	3.0	3.1
Insertion	2.4	0.0
Shell	0.8	0.4
Merge	4.0	3.9
Quick	0.6	0.3
Heap	1.4	1.6

Exercises

pp. 355-356: #2, #6, #14