Assignment 1: Abstract Data Types

Introduction

Abstract data types are an important mechanism for encapsulating implementation details and only expose a clearly defined interface to the user. One does not typically care whether a set is implemented as a list, a search tree, or a hash table so long as common operations such as union, intersection, membership, etc are available.

Programming languages offer various mechanisms to implement abstract data types and in this assignment you will implement three abstract data types in two or three different programming languages and then evaluate the implementations and compare them with one another.

You should implement all data types in all languages (for a total of 3*2 or 3*3 implementations).

This assignment should be solved in pairs.

Instructions

The three languages are Java, C, and Standard ML. You are required to implement in Standard ML and either C or Java, but we strongly recommend that you implement in all three languages to get the most from this assignment.. For each data type you should use the facilities offered by the language to construct as effective and beautiful code as you can manage given the time constraints. You will likely have to iterate the process of design and implementation to refine your code until you feel satisfied. Of course, you are not allowed to reuse existing code that implements similar functionality. Limit yourself to lists, arrays, vectors, etc. If you are uncertain about what is permitted, contact an assistant.

Below is a list of three abstract data types listed in order of increasing complexity. You need only implement a small subset of the common operations (specified below). You should also construct a non-trivial test case for each data type/language pair in order to test your code.

  1. Queue. An unbounded FIFO queue with the following operations:
    Enqueue
    Adds an element to the back of the queue.
    Dequeue
    Removes the front element from the queue and returns it.
  2. Binary Tree. A binary tree is a special kind of ordered tree with the following additional properties: Operations:
    In-order Traversal
    This operation performs an in-order traversal and upon visiting a node a user-supplied function is applied to the content of the node.
    Accumulation
    Each leaf in the binary tree has a weight (calculated by a user-supplied function). These weights are accumulated by the accumulation operation. The accumulation function (be it summation, string concatenation, etc) is also a user-supplied function. An example would be a binary tree where each leaf node contains a string. An example weight could be an integer and a weight function could return the length of the string at a leaf. By using addition as the accumulation function we could find out the number of letters in all leaf nodes by accumulating onto an initial weight of zero. Note that the term "weight" could be somewhat misleading depending on your particular example and a weight could have any type.
  3. Directed Acyclic Graph. A directed acyclic graph (DAG) contains a set of nodes and a set of directed edges between pairs of nodes. The edges do not form a cycle. A DAG may be used to represent a partial order. A contrived but illustrative example is the is-shorter-than relation applied to strings. The string "abc" is-shorter-than "defg" but is not comparable with "hij" since they have the same length. We could represent this information as a DAG: Operation:
    Topological Sort
    A topological sort of a DAG is an arrangement of its nodes in a sequential order such that whenever x is related to y then the node of x comes before the node of y. Another way to say the same thing is that a topological sort is an arrangement of the nodes of the DAG in a linear horizontal order such that all edges goes from left to right. In the is-shorter-than example, one topological sort would be "hij", "abc", "defg".

As you might have noticed, the data types above are loosely specified. This has been done on purpose to allow some creativity on your part. You are encouraged to pick some example application and specify the missing parts based on what makes sense for that application. Of course, use the same example for all languages to get comparable implementations.

Evaluation

A large part of this assignment is the written evaluation and comparison of the implementations centered around programming language concepts.

Focus on the concepts below and compare how your implementations are able to support (or do not support) them.

Encapsulation.
How well can data and methods that manipulate the data be encapsulated in a logical unit?
Information Hiding.
How well can the implementation details be kept from the user?
Type Checking.
All of the abstract data types above are containers of some sort and the type of the contained elements should match. Can your implementations guard against accidental use of the wrong element type? For example, enqueuing an Apple to a Queue that is intended for Oranges?
Higher Order Functions.
The Binary Tree data type has operations that take user-supplied functions as arguments. They are therefore higher order functions. What language feature(s) did you take advantage of when implementing higher order functions? Any pros or cons with your choice?

Report

Your report should contain two parts:

  1. A short description of your selected examples (one per data type) as well as a discussion of the implementation details. The aim of this section is to communicate to the reader (which we assume is familiar with the topic) what techniques you used to implement the abstract data types. Imagine that an interested reader who knows about abstract data types should get a good idea of how to implement them and the language-related issues involved.
  2. An evaluation focusing on the concepts presented above. Strive to get a short and concise discussion that is easy to read. The reader should get a feel for the pros and cons of the chosen implementation technique.