CSci 1901: Lab 8, March 8

Lab 8: Multiple Representations of Data

Related files: Write Up

The Lab 8 template contains 4 definitions for each of the following procedures: empty?, element-of-set?, count, adjoin, union, intersection, difference, and symmetric-difference. One for each of the following three representations of sets - unordered lists with duplicates, ordered lists without duplicates, and binary search trees, and one definition you must complete that will work with any of the data types.

For each of data sets all of the operations are already implemented except for the ones you had to write for the last lab. Copy and paste these in from the last lab before you do anything else. These are adjoin and union for ordered list representation, and union and intersection for binary search trees. You may also need to copy your definition of tree->set.

Your goal for the lab is to get all of the test cases provided in the template to work while maintaining distinct data types in the system (i.e. you may not just convert all data to one type and your code must maintain distinct representations). The book presents three possible solutions: tagging, message passing, and data directed programming. You may pick one of these and modify the existing code accordingly. If you come up with a different approach feel free to use it as long as it maintains the three distinct set representations underneath.

You may assume the procedures that take in two sets such as union will only be passed two sets in a given call if they are in the same representation. For instance, union will never be sent a binary search tree for the first argument and an ordered list as the second, but union should work for two binary search trees or two ordered lists.

Be sure that your system maintains consistency in representations. For instance, if union takes in two binary search trees be sure to return a binary search tree representing the union of these two trees. If you are representing your data with tags, be sure that the generic union operation returns data that is properly tagged. Likewise if you are implementing your data as message passing procedures, be sure the generic union procedure returns a message passing representation. In either case the sample files below provide examples of how you can do this. Be sure adjoin, intersection, difference, and symmetric-difference are consistent also.

Examples for unordered lists have been worked out by the TAs for each of the three methods, you may feel free to use these for inspiration:

If you implement a message passing scheme test your code with the second set of test cases and implement a message 'data that returns the actual list data of your representation. This way the test cases will show your the actual set generated by operations such as union and intersection, and not just a representation for the procedure returned. You may also find this useful for implementing union, intersection, etc. See the example in the message passing file above.

Hints Congratulations on completing Lab 8!
Lab 8 total: 10 pts

This is what you will learn in this lab

Copyright: © 2006 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.