- The exam consists of eight questions and two pages of C++ code.
Be sure that you have all of these items and that they are all legible.
- Read all questions and their instructions thoroughly before you begin.
It is always worth your time to plan ahead!
- You have also been given three blank pages. Use these sheets for your
exam answers. Be sure to write your name on each sheet.
- The exam is worth 100 points. Questions 1-2 and 4-7 are worth twelve
points each; Questions 3 and 8 are worth 14 points each.
- Keep the exam questions when you are done, for future reference.
- Points will be awarded based on your explicit answers. Partial credit
will be given where possible, so show all of your work.
- The exam lasts sixty (60) minutes. It is due one hour after you receive it.

- List the steps of the software lifecycle and give a one to two sentence
description of each.

- In class, we discussed approaches to software design: Top-Down Design
(TDD) and Object-Oriented Design (OOD).
- Explain two significant similarities between TDD and OOD.
- Explain two significant differences between TDD and OOD.

- Explain two significant similarities between TDD and OOD.
- The function
`void removeBlanks(char word[])`takes as input a C++ string and compresses any whitespace characters out of it. For example:input:

`word[] = "Hi Bob good to see you"`output:

`word[] = "HiBobgoodtoseeyou"`- Rewrite this specification as a precondition and a postcondition.
- Specify an invariant for the primary loop in
`removeBlanks`, either symbolically or with a picture. - Using your assertions as a guide, write the function
`removeBlanks`.

- Rewrite this specification as a precondition and a postcondition.
- The function
`void computeParity(int sequence[], int n)`takes as input an integer array of length`n`and computes the*parity*of each entry in the array. The element in position`k`is replaced by 0 if`sequence[k]`is even and by 1 if`sequence[k]`is odd. For example, if`sequence[] = {1 2 4 7 -1}`before calling`computeParity`, then afterwards`sequence[] = {1 0 0 1 1}`.Write a short test plan for

`computeParity`. Group your tests according to the kind of situation that they address.

- Many applications require the ability to work with times. Suppose that we
need a
`Time`class for a piece of scheduling software. Clients of`Time`would want to be able to ask questions such as "If Aldi closes at 7:00 PM, then how much time left do I have to do my shopping?"- Specify a set of messages to which a useful
`Time`object would respond. Your list should include at least half a dozen, probably more. - What private member data might a
`Time`object contain? Your answer may be in English; you do not have to write C++ code.

- Specify a set of messages to which a useful
- Answer the following questions about the
`linearSearch`and`unknownSearch`algorithms from Laboratory Exercise 15 in Roberge. Explain your answers with references to the code wherever possible.- What is the critical operation in these search operations?
- What is the run-time efficiency for each in terms of order of
magnitude (big-oh notation)?
- In the lab, timing experiments indicated that one of these algorithms was much faster than the other. Explain the difference.

- What is the critical operation in these search operations?
- What is the output of the mystery program?
For partial credit in the case of an incorrect answer, be sure to show as
much of your work, such as the changing values of variables, as you can.

- MergeSort is an algorithm that sorts an array with O(
*n*log*n*) worst case performance. Like QuickSort, it consists of two procedures:- a recursive procedure that splits the array in half, makes recursive
calls to merge-sort the halves, and then calls a merge procedure to
put the sorted halves back together, and
- a merge procedure that takes two sorted sub-arrays as input and modifies the array so it that it is sorted across the full range.

For now, let's assume that someone else has written the merge procedure for us and that its specification is:

`void merge(int a[], int first, int middle, int last)``middle`is the index of the last integer in the left sub-array, and`middle + 1`is the first integer in the right sub-array.Write a recursive function named

`merge_sort`that satisfies the following specification:-
*Interface*:`int merge_sort(int a[], int first, int last)` -
*Precondition*:`a`is an array beginning in slot`first`and ending in slot`last` -
*Postcondition*:`a`is sorted in ascending order from slot`first`to slot`last`

As with QuickSort, the base case in MergeSort will be an array of size 0 or 1, that is,

when`first`>=`last`. - a recursive procedure that splits the array in half, makes recursive
calls to merge-sort the halves, and then calls a merge procedure to
put the sorted halves back together, and