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.
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.
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:
a="abc"
, b="defg"
, and
c="hij"
.
a -> b
, and c -> b
.
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.
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.
Your report should contain two parts: