Data Structures and Algorithms with Object-Oriented Design Patterns in C#
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_inline66431.
    1. SetAsArray (Program gif),
    2. SetAsBitVector (Program gif),
    3. MultisetAsArray (Program gif), and
    4. MultisetAsLinkedList (Program gif).
  2.   In addition to = and tex2html_wrap_inline66547, a complete repertoire of set operators includes tex2html_wrap_inline66559, tex2html_wrap_inline66561, tex2html_wrap_inline66563 and tex2html_wrap_inline60913. 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_inline67117 is given by

    displaymath67093

    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

    displaymath67094

    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_inline67125 where i an the element of the universal set U and tex2html_wrap_inline62025 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_inline66431.

  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_inline67141. For each of the methods of computing the union listed below show the result of the following sequence join operations: tex2html_wrap_inline67143, tex2html_wrap_inline67145, tex2html_wrap_inline67147, tex2html_wrap_inline67149, tex2html_wrap_inline67151, tex2html_wrap_inline67153, tex2html_wrap_inline67155, tex2html_wrap_inline67157, tex2html_wrap_inline67159.
    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_inline66431 comprised of N sets[24].
    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_inline67171), 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_inline67171), at least tex2html_wrap_inline67179 singletons are left.
    4. Show that if less that tex2html_wrap_inline67181 join operations are done, at least one singleton is left.

next up previous contents index

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