Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Exercises

  1.   For each of the following implementations derive an expression for the total memory space required to represent a set which contains of n elements drawn from the universe tex2html_wrap_inline66148.
    1. SetAsArray (Program gif),
    2. SetAsBitVector (Program gif),
    3. MultisetAsArray (Program gif), and
    4. MultisetAsLinkedList (Program gif).
  2.   In addition to = and tex2html_wrap_inline66264, a complete repertoire of set operators includes tex2html_wrap_inline66276, tex2html_wrap_inline66278, tex2html_wrap_inline66280 and tex2html_wrap_inline60646. For each of the set implementations listed in Exercise gif show how to implement the remaining operators.
  3. The symmetric difference   of two sets S and T, written tex2html_wrap_inline66834 is given by

    displaymath66810

    For each of the set implementations listed in Exercise gif devise an algorithm to compute symmetric difference. What is the running time of your algorithm?

  4. The complement  of a set S over universe U, written S' is given by

    displaymath66811

    Devise an algorithm to compute the complement of a set represented as a bit vector. What is the running time of your algorithm?

  5. Devise an algorithm to sort a list of integers using a multiset. What is the running time of your algorithm? Hint: See Section gif.
  6.   Consider a multiset implemented using linked lists. When the multiset contains duplicate items, each of those items occupies a separate list element. An alternative is to use a linked list of ordered pairs of the form tex2html_wrap_inline66842 where i an the element of the universal set U and tex2html_wrap_inline61758 is a non-negative integer that counts the number of instances of the element i in the multiset.

    Derive an expression for the total memory space required to represent a multiset which contains of n instances of m distinct element drawn from the universe tex2html_wrap_inline66148.

  7.   Consider a multiset implemented as described in Exercise gif. Devise algorithms for set union, intersection, and difference. What are the running times of your algorithms?
  8.   Consider the initial partition tex2html_wrap_inline66858. For each of the methods of computing the union listed below show the result of the following sequence join operations: tex2html_wrap_inline66860, tex2html_wrap_inline66862, tex2html_wrap_inline66864, tex2html_wrap_inline66866, tex2html_wrap_inline66868, tex2html_wrap_inline66870, tex2html_wrap_inline66872, tex2html_wrap_inline66874, tex2html_wrap_inline66876.
    1. simple union,
    2. union by size,
    3. union by height, and
    4. union by rank.
  9. For each final partition obtained in Exercise gif, show the result of performing a collapsing find operation for item 9.
  10. Consider the initial partition P of the universe tex2html_wrap_inline66148 comprised of N sets[22].
    1. Show that N-1 join operations can be performed before the number of elements in the partition is reduced to one.
    2. Show that if n join operations are done ( tex2html_wrap_inline66888), the size of the largest element of the partition is at most n+1.
    3. A singleton  is an element of a partition that contains only one element of the universal set. Show that when n join operations are done ( tex2html_wrap_inline66888), at least tex2html_wrap_inline66896 singletons are left.
    4. Show that if less that tex2html_wrap_inline66898 join operations are done, at least one singleton is left.

next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.