McGill University:
Department of Computer Science
Winter 1997 Class Notes for 308-251

DATA STRUCTURES AND ALGORITHMS

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.

Developing An Algorithm For A Scheduling Problem.

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.

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:
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:

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.

The ADT Demonstrator 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:

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!

The ADT Demonstrator Applet.

Your Web browser does not allow you to view Java applets. Consider getting one of the following:

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.


Links to Related Material

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

Kazuo Sugihara's Lecture #1 on ADTs. Definition, implementation, and advantages of ADTs. An illustrative example of an ADT is given.
Kazuo Sugihara's Algorithms and Data Structures, Lecture #2

Definition of data structures and algorithms. Design process of data strucures.

Kazuo Sugihara's Algorithms and Data Structures, Lecture #3 Outline for design and analysis of algorithms.
Sughara's complete lecture notes The index to the complete lecture notes of Kazou Sugihara of the Univ. of Hawaii.
Peter Muller, Globalwide Network Academy Problem handling, properties of ADTs, generic ADTs, object orientation.
University of Massachusetts Darmouth Definition of ADTs, operations, specifications with examples.
Index to Jim Webb's Course Notes

Chapters 2 to 6 and 10 contain a comprehensive description of problem specification, algorithm design and implementation, and ADTs.

Paulette Lieby, Northern Territory University Algorithm and problem solving.
Rob Probin, Birmingham UK Abstract Data Types and examples.
Mike Atkinson, U. of St. Andrew's Introduction to ADTs and their design.
Dictionary of Object Oriented Terms Definitions of ADTs, implementation, etc.


References

For More Information on Abstract Data Types consult these selected materials:

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


This Web Page was Created by:


To ask us to join your bible studies group or to treat us to milk and cookies don't hestitate to contact us.

This web page was last updated January 23, 1997 by Alberto D'Urso.

Copyright © 1997 by The Triple A Software People -- Alberto D'Urso, Albert Mah, Adam Smith. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy. Disclaimer: this collection of notes is experimental, and does not serve as-is as a substitute for attendance in the actual class.