Ccac C++ 020 Patterns And Uml (Rq And Sum)

Front 1

design principles that apply across a variety of software applications.

Back 1

patterns

Front 2

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.

Back 2

The Adapter
pattern

Front 3

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.

Back 3

Model-View-Controller
pattern

Front 4

One big task is divided into three smaller tasks with well-defined
responsibilities.

Back 4

The Model-View-Controller pattern is an example of a divide-andconquer
strategy:

Front 5

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.

Back 5

Model-View-Controller pattern

Front 6

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.

Back 6

Model-View-Controller pattern

Front 7

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.

Back 7

merge sort

Front 8

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.

Back 8

quick-sort

Front 9

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

Back 9

selection sort

Front 10

Today’s candidate for a graphical representation formalism

Back 10

Unified Modeling Language (UML)

Front 11

The patterns discussed in this chapter are

Back 11

Container-Iterator, Adapter, Model-
View-Controller, and Divide-and-Conquer Sorting patterns.

Front 12

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

Back 12

pattern

Front 13

a graphical representation language for
object-oriented software design.

Back 13

The Unified Modeling Language (UML)

Front 14

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

Back 14

UML

Front 15

1. Is a template function definition a pattern?

Back 15

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.)

Front 16

2. Give the contents of a file named selectionsort.cpp that will realize the selection
sort algorithm (see Display 5.8) for the Divide-and-Conquer 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.)

Back 16

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.
}

Front 17

3. Which of the following would give the fastest running time when an array is sorted
using the quick-sort 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.

Back 17

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 worst-case 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 quick-sort algorithm has its worst
behavior on an already sorted array. There are variations on the quick-sort 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 worst-case running time.

Front 18

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

Back 18

pg. 891

Front 19

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

Back 19

pg. 891