Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle
Toggle OnToggle Off
 Alphabetize
Toggle OnToggle Off
 Front First
Toggle OnToggle Off
 Both Sides
Toggle OnToggle Off
 Read
Toggle OnToggle Off
How to study your flashcards.
Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key
Up/Down arrow keys: Flip the card between the front and back.down keyup key
H key: Show hint (3rd side).h key
A key: Read text to speech.a key
19 Cards in this Set
 Front
 Back
design principles that apply across a variety of software applications.

patterns


transforms one class into a different class without changing the
underlying class, merely by adding a new interface. (The new interface replaces the old interface of the underlying class.) For example, in Chapter 19 we mentioned that the stack and queue template classes of the STL were adapter classes. We described both the stack and queue interfaces and said you could choose the underlying class that would actually store the data. For example, you can have a stack of int s with an underlying vector, stack< vector<int> > , or a stack of int s with an underlying list, stack< list<int> > (or a stack with some other underlying container class, but two is enough for our point). In either case, list or vector, the underlying class is not changed. Only an interface is added. How might the interface be added? That is an implementation detail that need not be part of the Adapter pattern. There are, however, at least two obvious ways to do it. For example, for a stack adapter the underlying container class could be a member variable of the stack class, or the stack class could be a derived class of the underlying container class. 
The Adapter
pattern 

a way of dividing the I/O task of an application
from the rest of the application. The Model part of the pattern performs the heart of the application. The View part is the output part; it displays a picture of the Model’s state. The Controller is the input part; it relays commands from the user to the Model. 
ModelViewController
pattern 

One big task is divided into three smaller tasks with welldefined
responsibilities. 
The ModelViewController pattern is an example of a divideandconquer
strategy: 

is particularly
well suited to GUI (graphical user interface) design projects, where the View can indeed be a visualization of the state of the Model. 
ModelViewController pattern


the Model might be an object
to represent your list of computer desktop object names. The View could then be a GUI object that produces a screen display of your desktop icons. The Controller relays commands to the Model (which is a desktop object) to add or delete names. The Model object notifies the View object when the screen needs to be updated. 
ModelViewController pattern


an example in which the definition of split is very simple. It divides
the array into two intervals with no rearranging of elements. The join function is more complicated. After the two subintervals are sorted, it merges the two sorted subintervals, copying elements from the array to a temporary array. The merging starts by comparing the smallest elements in each smaller sorted interval. The smaller of these two elements is the smallest of all the elements in either subinterval, and so it is moved to the first position in the temporary array. The process is then repeated with the remaining elements in the two smaller sorted intervals to find the next smallest element, and so forth. 
merge sort


the definition of split is quite sophisticated. An arbitrary value in the array is
chosen; this value is called the splitting value. In our realization we chose a[begin], as the splitting value, but any value will do equally well. The elements in the array are rearranged so that all those elements that are less than or equal to the splitting value are at the front of the array and all the values that are greater than the splitting value are at the other end of the array; the splitting value is placed so that it divides the entire array into these smaller and larger elements. Note that the smaller elements are not sorted and the larger elements are not sorted, but all the elements before the splitting value are smaller than any of the elements after the splitting value. The smaller elements are sorted by a recursive call, the larger elements are sorted by another recursive call, and then these two sorted segments are combined with the join function. In this case the join function is as simple as it possibly could be: It does nothing. Since the sorted smaller elements all preceed the sorted larger elements, the entire array is sorted. 
quicksort


divides the array
into two pieces, one with a single element and one with the rest of the array interval (see SelfTest Exercise 2). Because of this uneven division, the ___ ___ has a worstcase, and even averagecase, running time that is O(N2). In practice, the ___ ___ is not a very fast sorting algorithm, although it does have the virtue of simplicity. 
selection sort


Today’s candidate for a graphical representation formalism

Unified Modeling Language (UML)


The patterns discussed in this chapter are

ContainerIterator, Adapter, Model
ViewController, and DivideandConquer Sorting patterns. 

can give you a framework for comparing related algorithms for efficiency.

pattern


a graphical representation language for
objectoriented software design. 
The Unified Modeling Language (UML)


is one formalism that can and is used to express patterns.

UML


1. Is a template function definition a pattern?

1. Yes, a template function definition is a pattern, but the term pattern is much more general
and encompasses more. Moreover, a useful pattern expressed as a template function would leave some details unimplemented. If the only variation possible is a type parameter, it is still a pattern but not likely to be usefully viewed as a pattern. (It can still be useful as a template function, but it might not be useful to view it as a pattern in the sense discussed in this chapter.) 

2. Give the contents of a file named selectionsort.cpp that will realize the selection
sort algorithm (see Display 5.8) for the DivideandConquer Sorting pattern given in Display 20.2. (This is the selection sort analog of what was done for the quick sort in Display 20.5.) 
2. //File selectionsort.cpp: the selection sort realization
//of the Sorting pattern. #include <algorithm> using std::swap; template <class T> int indexOfSmallest(const T a[], int startIndex, int sentinelIndex) { int min = a[startIndex], indexOfMin = startIndex; for (int index = startIndex + 1; index < sentinelIndex; index++) if (a[index] < min) { min = a[index]; indexOfMin = index; //min is the smallest of a[startIndex] //through a[index] } return indexOfMin; } template <class T> int split(T a[], int begin, int end) { int index = indexOfSmallest(a, begin, end); swap(a[begin], a[index]); return (begin + 1); } template <class T> void join(T a[], int begin, int splitPt, int end) { //Nothing to do. } 

3. Which of the following would give the fastest running time when an array is sorted
using the quicksort algorithm: a fully sorted array, an array of random values, or an array sorted from largest to smallest (that is, sorted backwards)? Assume that all arrays are of the same size and have the same base type. 
3. An array of random values would have the fastest running time, since it would divide the
array segments into approximately equal subarrays most of the time. The other two cases would give approximately the same running time, which would be the worstcase O(N2) running time because the algorithm would always divide an array segment into very unequal pieces, one piece with only one element and one piece with the rest of the elements. It is ironic but true that our version of the quicksort algorithm has its worst behavior on an already sorted array. There are variations on the quicksort algorithm that perform well on a sorted array. For example, choosing the middle element as the splitting value will give good performance on an already sorted array. But whatever splitting value you choose, there will always be a few cases with this worstcase running time. 

4. Draw a class diagram for a class whose objects represent circles. Use Display 20.6
as a model. 
pg. 891


5. Draw a class diagram for the IntNode class presented in Display 17.4.

pg. 891
