CSE 428: Exercises on abstract data types and data protection


The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.

  1. (s) Consider the implementation of the ADT "simple list" seen in Lecture 10 (CSE 428 Spring 99, see LN). Assume that the data are somehow protected, so that it is possible to access to lists only via the operations of the ADT.
    1. Is it possible to create "circular lists", i.e. lists in which it is possible, following the links from an element, to come back to the element itself?
    2. Is it possible to create "shared lists", i.e. lists which have a part in common?
    3. Is it possible that an operation done on a list affects another list?
  2. (s) Suppose that the above implementation of "simple lists" is done in a language like Pascal Standard or C, which do not offer a mechanism for data protection.
    1. Would the creation of circular lists, shared lists and side effects be possible?
    2. Would it be possible to create lists with multiple links in their elements, for instance tree-like structures or two-dimentional structures?
  3. (s) Describe briefly the advantages of having a mechanism for data protection.
  4. (s) What are the mechanism offered in Modula 2 and in C++ for data protection?