Previous Section
 < Free Open Study > 
Next Section


Exercises

  1. The Unsorted List ADT is to be extended with a Boolean member function, IsThere, which takes as a parameter an item of type ItemType and determines whether there is an element with this key in the list.

    1. Write the specification for this function.

    2. Write the prototype for this function.

    3. Write the function definition.

    4. Describe this function in terms of Big-O notation.

  2. The Sorted List ADT is to be extended with a Boolean member function, IsThere, which takes as a parameter an item of type ItemType and determines whether there is an element with this key in the list.

    1. Write the specification for this function.

    2. Write the prototype for this function.

    3. Write the function definition using the binary search algorithm.

    4. Describe this function in terms of Big-O notation.

  3. Write a paragraph comparing your answers in Exercises 1 and 2.

  4. Rather than enhancing the Unsorted List ADT by adding a member function IsThere, you decide to write a client function to do the same task.

    1. Write the specification for this function.

    2. Write the function definition.

    3. Describe this function in terms of Big-O notation.

    4. Write a paragraph comparing the client function and the member function (Exercise 1) for the same task.

  5. Rather than enhancing the Sorted List ADT by adding a member function IsThere, you decide to write a client function to do the same task.

    1. Write the specification for this function.

    2. Write the function definition.

    3. Were you able to use the binary search algorithm? Explain your answer.

    4. Describe this function in terms of Big-O notation.

    5. Write a paragraph comparing the client function and the member function (Exercise 2) for the same task.

  6. Write a client function that merges two instances of the Sorted List ADT using the following specification:

    1. Write the prototype for MergeLists.

    2. Write the code for the function.

    3. Describe the algorithm in terms of Big-O notation.

  7. Redo your answers to Exercise 6, making MergeLists a member function of the Sorted List ADT.

  8. A List ADT is to be extended by the addition of the function SplitLists, which has the following specification where ListType is either the class UnsortedType or the class SortedType:

    1. Implement SplitLists as a member function of the Unsorted List ADT.

    2. Implement SplitLists as a member function of the Sorted List ADT.

    3. Compare the algorithms used in parts (a) and (b).

    4. Implement SplitLists as a client function of the Unsorted List ADT.

    5. Implement SplitLists as a client function of the Sorted List ADT.

  9. The specification for the Unsorted List ADT states that the item to be deleted is present in the list.

    1. Rewrite the specification for DeleteItem so that the list is unchanged if the item to be deleted is not present in the list.

    2. Implement DeleteItem as specified in part (a).

    3. Rewrite the specification for DeleteItem so that all copies of the item to be deleted are removed if they exist.

    4. Implement DeleteItem as specified in part (c).

  10. The specification for the Sorted List ADT states that the item to be deleted is present in the list.

    1. Rewrite the specification for DeleteItem so that the list is unchanged if the item to be deleted is not present in the list. (There is at most one such item.)

    2. Implement DeleteItem as specified in part (a).

    3. Rewrite the specification for DeleteItem so that all copies of the item to be deleted are removed if they exist.

    4. Implement DeleteItem as specified in part (c).

  11. Write a formal specification for the problem explored in the Case Study.

  12. Give an example of an algorithm (other than the examples discussed in the chapter) that is

    1. O(1)

    2. O(N)

    3. O(N2)

  13. A routine to calculate the sum of the results of applying the int function X to the values in the array data contains the following code segment:

    sumOfX  =  0;
    for (int index = 0; index < numberOfElements; index++)
      sumOfX = sumOfX + X(data[index]):
    

    If the function X is O(N), what is the order of magnitude of the algorithm with respect to numberOfElements?

  14. Algorithm 1 does a particular task in a "time" of N3, where N is the number of elements processed. Algorithm 2 does the same task in a "time" of 3N + 1,000.

    1. What are the Big-O requirements of each algorithm?

    2. Which algorithm is more efficient by Big-O standards?

    3. Under what conditions, if any, would the "less efficient" algorithm execute more quickly than the "more efficient" algorithm?

  15. Replace the function ComparedTo in the Unsorted List ADT by assuming that member functions of ItemType overload the relational operators.

  16. Replace the function ComparedTo in the Sorted List ADT by assuming that member functions of ItemType overload the relational operators.

  17. Discuss extending a List ADT by the addition of a member function Head, which has the following precondition and postcondition:

    Precondition: list has been initialized and is not empty.

    Postcondition: return value is the last item inserted in the list and the list is of type

    1. UnsortedType

    2. SortedType

  18. Discuss extending a List ADT by the addition of function Tail, which has the following precondition and postcondition:

    Precondition: list has been initialized and is not empty.

    Postcondition: return value is a new list with the last item inserted in the list removed and the list is of type

    1. UnsortedType

    2. SortedType

  19. DeleteItem does not maintain the order of insertions because the algorithm swaps the last item into the position of the item being deleted and then decrements length. Would there be any advantage to having DeleteItem maintain the insertion order? Justify your answer.

  20. Give a Big-O estimate of the run time for the functions you wrote in Exercises 9 and 10.

    1. Change the specification for the Unsorted List ADT so that InsertItem throws an exception if the list is full.

    2. Implement the revised specification in part (a).

    1. Change the specification for the Sorted List ADT so that InsertItem throws an exception if the list is full.

    2. Implement the revised specification in part (a).

  21. The method names used in the class FractionType were not very object oriented. Rewrite the CRC card for this class using more object-oriented terminology.

  22. Complete coding class HouseType(ItemType).



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)