CMPSC 20
2003:April:02
Acknowledgement: Some of these exercises are derived from "A Practical Introduction to Data Structures and Algorithm Analysis" by Clifford A. Shaffer.
HighArray
class in the highArray.java
program (Listing 2.3), add a method called getMax()
that returns the value of the highest key in the array,
or -1 if the array is empty.
Add some code in main()
to exercise this method.
You can assume all the keys are positive numbers.
removeMax()
.
removeMax()
method in Programming Project 2.2
suggests a way to sort the contents of an array by key value.
Implement a sorting scheme that does not require modifying the
HighArray
class,
but only the code in main()
.
You'll need a second array,
which will end up inversely sorted.
(This scheme is a rather crude variant
of the selection sort in Chapter 3,
"Simple Sorting.")
orderedArray.java
program (Listing 2.4)
so that the insert()
and delete()
routines,
as well as find()
,
use a binary search, as suggested in the text.
4n^{2} log_{3}n 3^{n} 20n 2 log_{2}n n^{2/3} n!
n n^{2} n^{3} 2^{n}
n
,
determine O()
for the following code-fragments
in the average case.
Assume that all variables are of type int
.
a = b + c; d = a + e;
sum = 0; for ( i = 0; i < 3; i++ ) for ( j = 0; j < n; j++ ) sum++;
sum = 0; for ( i = 0; i < n*n; i++ ) sum++;
A
contains n
values.
for ( i = 0; i < n; i++ ) { for ( j = 0; j < n; j++ ) A[i] = (int) (n * Math.random()); // Math.random() takes constant time sort(A); // sort() takes n * log(n) time }
A
contains
a random permutation of the values
from 0 to n - 1
.
sum = 0; for ( i = 0; i < n; i++ ) for ( j = 0; A[j] != i; j++ ) sum++;
sum = 0; if ( EVEN(n) ) for ( i = 0; i < n; i++ ) sum++ else sum = sum + n;
n
:
count = 0; while ( n > 1 ) { if ( ODD(n) ) n = 3*n + 1; else n = n/2; count++; }Then, briefly discuss what you think the real O() worst-case running-time of this code may be.