Problem 1
Brookshear, Chapter Four Review Problem 18(pg 178).
Problem 2
The version of insertion sort presented by Brookshear
(algorithm presented pgs 151-155 and analyzed pg. 417) uses sequential
search to find where the pivot item belongs in the portion of the list
that is already sorted. (The sorted portion ranges from the beginning of the
list to just preceeding
the location of the pivot item before it is inserted in
the sorted portion.)
Suppose the list is stored as an array so that binary search can be used
in the sorted portion to find the correct position of the pivot item.
Will this improve the speed of insertion sort significantly? Justify
your answer.
Be careful to consider all the basic steps the new version of
insertion sort
would have to do -- in particular, each time an array item is examined or
changed must be counted as a step. (Note: the term "pivot item" is used here
in the same way as in Figure 4.12, pg. 154 of Brookshear; this is different
from the pivot item in quick sort).
Problem 3
Brookshear, Chapter Five Review Problem 4, (pg 227).
Before writing the machine language, write the Java statement.
Note that in Java, the symbol "=" is used only for assignment -- "let
x take on the value of y" becomes "x = y". To test equality, the notation
"= =" is used, so "if i equals n" becomes "if (i = = n)".
Problem 4
Java has a for loop control structure as well
as a while loop control structure --
see Brookshear page 201 and
Lab 7, Page 3. Below is a program fragment using a for loop.
Rewrite the fragment using
a while loop instead of the for loop. Variables
n
and k are integer variables declared elsewhere.
n = 0;
for (k = 1; k < 1000; k = 2*k)
{ n = n + k;}
Problem 5