16. Three algorithms A, B, and C, are under consideration for the Insert operation of a particular data set. Through an analysis of these algorithms, their speed functions have been determined to be: Algorithm A: 23n + 36n²; Algorithm B: 6 + nlog₂(n) + n; Algorithm C: log₂n + 36n².

(a) Calculate the value of these three functions when n, the number of nodes in the data structure, is equal to 1,000,000.

(b) Using Big-O analysis, calculate the value of each function. Note: To do this correctly, you must use the complete dominant term for the Big-O part including the co-efficient so for Algorithm A that is 36n², not n².

(c) Determine the percent difference between the values calculated in parts (a) and (b) for each algorithm.

17. A 1000 element array is used to store integers in ascending order. The array is to be searched using the binary search algorithm for the two integers 5215 and 7282. How many elements of the array would be examined by the algorithm to locate

(a) the integer 5215 stored in element 499?

(b) the integer 7282 stored in element 686?

18. What is the maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers if the search algorithm is

(a) the binary search?

(b) the sequential search?

19. Half of the integers stored in the array data are positive, and half are negative. Determine the absolute speed of the following algorithm, assuming: the time to execute a memory access is 100 nanoseconds and that all other operations (arithmetic, register accesses, etc.) take 10 nanoseconds.

for(int i = 0; i<1000000; i++)

{ if(data[i] < 0 )

data[i] = data[i] * 2;

}

20. Observations of the traffic on a data structure over a certain period of time indicate that 500 Insert operations, 500 Delete operations, 700 Fetch operations, and 200 Update operations were performed on a data set. If Insert operations take 10 nanoseconds, Delete operations take 250 nanoseconds, Fetch operations 200 nanoseconds, and Update operations take 300 nanoseconds, determine:

(a) the probability of performing a Fetch operation over the observation period.

(b) the average speed, in nanoseconds, of the data structure over the observation period.

21. Calculate the density of a data structure whose data set consists of 1,000,000 nodes, assuming the structure requires 1,000,000 bytes of overhead to maintain itself, and:

(a) each node in the data set contains 2000 information bytes.

(b) each node in the data set contains 20 information bytes.

22. Repeat the above exercise assuming the overhead is 10 bytes per node.

(a) each node in the data set contains 2000 information bytes.

(b) each node in the data set contains 20 information bytes.

23. State the Java code to declare an array of 100 integers named ages.

24. State the Java code to declare an array of three Listing objects named data that are initialized with the no-parameter constructor.

25. Draw a picture of the storage allocated in the previous exercise. Assume the array is stored at location 20, and the three objects are stored at locations 60, 70, and 50.

26. Two objects, objectA and objectB, are objects in the class Listing. The object objectA is copied to objectB. How many objects exist after the copy, if the copy is performed as:

(a) a deep copy?

(b) a shallow copy?

27. Of the two types of copies discussed in the previous exercise, which one produces a clone (an exact duplicate of an existing object)?

28. Give the signature of a method named deepCopy, that clones an object in the class Listing sent to it as a parameter and returns a reference to the clone.

29. Give the Java invocation to clone the object objectA (using the method discussed in the previous exercise) and store a reference to the clone in the variable: newListing.