Topic #1: ABSTRACT DATA TYPES

An algorithm is a finite collection of precise instructions to perform a certain task in a finite amount of time and with a finite number of resources. Note that:

1. Finite collection means we must be able to describe it to anyone succintly.
2. We must have precise instructions since there is no such things as an algorithm with a bug or a wrong algorithm. By definition algorithms are exact.
3. A finite amount of time means that our algorithm must stop. It cannot go into an infinite loop. Also, there does not exist an algorithm to compute the digits of "pi", as that would require an infinite amount of time.
4. Finite resources means we have finite storage.
Algorithms need not be described in a programming language.

Phases in Developing an Algorithm.

Phase Description Desired Result
1
Problem Formulation.
At this stage our goal is to break up the problem and formulate the solution in a rough algorithm. A Rough Algorithm.
2
The General Algorithm (in a Pseudo Language).
Next we construct a mathematical model and operations on that model. Together these are known as an ADT. For instance, our mathematical model may be a set or a graph, and our operations may be to find the first element or to list all elements. The result of this phase is to express the algorithm in a pseudo-language. This step is implementation-independent: an important feature if we need to organize big software projects. Persons working on one ADT need not know what others are doing with another ADT. Nowhere in an ADT's definition is there any mention of how the operations were implemented. ADTs are generalizations of primitive operations. Programs that use them will not need to know which implementation was used. Thus, ADTs are at the basis of modern object-oriented programming languages. The ADT.
3
Implementation of an Algorithm.
This last step is where we code our variables, functions, structures, etc. A data structure is an implementation of an ADT in a high-level language, that is, a combination of variables in some manner. The operations of the ADT are also implemented. Data Structures.

Phase 1.

Consider the problem of scheduling courses or exams. In this case, our algorithm might use a mathematical model such as a graph to create a picture of all our scheduling constraints. Each node represents a course and an edge exists between two nodes if there is at least one student in both courses. Nodes are coloured the same if courses occur during the same time slot.

Phase 2.

We take two mathematical models, one is a graph G and the other is a set of nodes with the same colour S -- as in the following illustration:

Phase 3.

Finally, we code our algorithm in a programming languge, to find all the nodes that can be coloured the same.

• S <- 0
• Find an uncoloured node u. S <- {u} U S
• For all uncoloured nodes v
• if v is not adjacent to any node u in S (loop through S)
• S <- {v} U S (colour the node)

Note that:

1. This algorithm only identifies some nodes that may receive the same color. To find all colors, it must be placed in a loop.
2. The algorithm is not guaranteed to find the minumum number of colors. That is much tougher.
3. The general problem is known as the "vertex coloring" or "graph coloring" problem.
4. Other vertex coloring problems:
• Coloring countries in a geographical map;
• Designing traffic light phases at multi-street intersections. (Food for thought: What do nodes, edges mean here?).
In this example we will have several implementations of our algorithm, one for each of our functions. We would require an ADT set with operations:
• MAKENULL.
This operation is needed to make the list empty.
• FIRST.
We need the operation First in order to locate a starting point; First returns null if the list is empty.
• NEXT.
Next is needed for looping through our list; it returns null if there is no next element.
• INSERT.
Insert is used to place an element into a null list or to insert an element in the correct location of an initialized list.

ADTs encourage modularity. One team might work on developing the graph G, other teams would code the functions Makenull, First, Next or Insert. Yet another team might be at work on the function "main" even without knowing the details of how these functions are implemented, by relying only on header files.

Java Applet.

Illustration of Implementation-Independence

One of the most important notions of current software design thinking is the ADT, whose salient feature is its independence from any particular programming language, platform or hardware. This applet illustrates this aspect by animating two different implementations of a List ADT.

The List ADT used here is very simple and is a commonly used example of ADTs. It is a set of non-negative integers (possibly with repetitions) equipped with the following operations:

MAKENULL
Empties the list.
INSERT
Inserts an integer into the list.
FIND
Determines if a given integer is present in the list.
DELETE
Erases the first located occurrence of a given integer.

For reasons of display space for the applet, this List ADT also has a size restriction: it will hold a maximum of 10 integers in the list at any time.

The applet lets you perform any of these operations, and displays how these operations would be carried out in two different implementations:

• A sorted array (on the left)
• A linked list (on the right)

To use the applet, just enter an integer argument in the text box Argument and click on the operation you would like to perform. The operation Make Empty doesn't require that you enter an argument. Go ahead, knock yourself out!

Source code for this applet. Four days before finishing this applet we were completely clueless about Java, and we learned mostly by trial and error (complier errors especially!). Check out these tips to avoid making the same errors we did.

For additional information on topics covered in this lecture visit these selected web sites:

References

• Aho, Alfred V. Data Structures and Algorithms. Addison-Wesley, 1983: 10-3. Describes the role of ADTs in overall program design and provides an example of an ADT implementation, and operations on a list ADT.
• Azmoodeh, Manoochehr. Abstract Data Types and Algorithms. Macmillan, 1988: 25-44. General discussion of abstract data types and how utilizing them will speed up problem solving.
• Dersham, H.L. and M.J. Jipping. Programming Languages: Structures and Models. PWS Publishing, 1995: 175-185. Discussion of ADTs as independent from the implementation. Also, different approaches to the definition of ADTs.
• Feldman, M.B. Data Structures with Modula-2. Prentice-Hall, 1988: 6-8. A basic discussion of how an abstract data type together with operations permit the creation and manipulation of objects of that type; data structures as a concrete implementation of an ADT.
• Friedman, D.P., M. Wand, and C.T. Haynes. Essentials of Programming Languages. MIT Press, 1992: 88-98. Explains how data abstraction techniques allow the details of implementation to be isolated and thus simplify our understanding of a program. Discussion of ADT representations in Scheme.
• Friedman, L.W. Comparative Programming Languages, Generalizing the Programming Function. Prentice-Hall, 1991: 7-9. An overview of how abstraction and structures can create generalized functions. Both are described in terms of data, programming and control.
• Ghezzi C. and M. Jazayeri. Programming Language Concepts, Second ed. Wiley, 1987: 140-157. The concept of abstract data types as way to classify objects not just by their representation structure but by their expected behavior. ADTs in SIMULA 67, CLU, Ada, Modula-2, and Smalltalk are discussed.
• Horowitz, Ellis. Fundamentals of Programming Languages, Second ed. Computer Science Press, 1984: 256-60. Covers abstract specification of data types, considers definitions of a data type in its most general form.
• Koffman, E.B. Turbo Pascal, Fifth ed. Addison-Wesley, 1995: 548-555. Introduces data abstraction and abstract data types, information-hiding, and provides examples of an ADT implementation.
• Nance, D.W. and T.L. Naps. Introduction to Computer Science: Problem Solving, and Data Structures, Third ed. West Publishing, 1995: 461-2, 848-53. Data structures as a separation of a conceptual definition of a data structure and its implementation. Examples are given in Pascal. The linked list as an ADT is illustrated.
• Pressman, R.S. Software Engineering, A Practitioner's Approach, Fourth ed. McGraw-Hill, 1997: 347-48. Contains a concise description of how abstraction allows programmers to generalize, and thus sidestep irrelevant low level details. Also has a brief mention of the mechanisms in various languages for creating abstract data types.
• Sedgewick, Robert. Algorithms in C, 2nd ed. Addison-Wesley, 1990: 31-32. Studies the notion of an ADT as a separation of what the data structure does from any particular implementation. ADTs as a mechanism to limit the interaction between algorithms and associated data structures.
• Standish, T.A. Data Structures, Algorithms and Software Principles. Addison-Wesley, 1994: 20-23. Basic concepts and principles, ideas of abstraction and representation, as well as using abstraction and information hiding.
• Weiss, Mark Allan. Algorithms, Data Structures, and Problem Solving with C++. Addison-Wesley, 1996: 41-43. Explains the concept of an abstract data type and how ADTs can be seen as an extension of modular design.

To find out if the reference materials mentioned are currently available try the web site of the PSE library.