Page 10 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 1: Introduction to Data Structure and Arrays

2, multiply: Notes

Function: multiply two complex numbers a1 + ib1 and a2 + ib2.
Precondition: no Precondition.
Post condition: a1a2 + ia1b2 + ib1a2 + i2b1b2.
i.e. a1a2 + ia1b2 + ib1a2 – b1b2.

Abstract data type (ADT) is a mathematical model with a collection of operations defined on that
model. Sets of integers, together with the operations of union, intersection and set difference, form
a simple example of an ADT. The ADT encapsulates a data type in the sense that the defi nition
of the type and all operations on the type can be localized and are not visible to the users of the
ADT. To the users, just the declaration of the ADT and its operations are important.

Abstract Data Type (ADT)

1. A framework for an object interface
2. What kind of stuff it’d be made of (no details)?

3. What kind of messages it would receive and kind of action it’ll perform when properly
triggered?

Do_this (p1, p2, p3) Conceptualization phase

Also_this (p1, p2, p3) Object

Do_that (p1, p2, p3)

From this we fi gure out
1. Object make-up (in terms of data)
2. Object interface (what sort of messages it would handle?)

3. How and when it should act when triggered from outside (public trigger) and by another
object friendly to it?
These concerns lead to an ADT – a definition for the object.

An Abstract Data Type (ADT) is a set of data items and the methods that work on them.
An implementation of an ADT is a translation into statements of a programming language, of the
declaration that defines a variable to be of that ADT, plus a procedure in that language for each

operation of the ADT. An implementation chooses a data structure to represent the ADT; each
data structure is built up from the basic data types of the underlying programming language.
Thus, if we wish to change the implementation of an ADT, only the procedures implementing the
operations would change. This change would not affect the users of the ADT.
Although the terms ‘data type’, ‘data structure’ and ‘abstract data type’ sound alike, they have
different meanings. In a programming language, the data type of a variable is the set of values
that the variable may assume. For example, a variable of type boolean can assume either the
value true or the value false, but no other value. An abstract data type is a mathematical model,
together with various operations defined on the model. As we have indicated, we shall design

algorithms in terms of ADTs, but to implement an algorithm in a given programming language

LOVELY PROFESSIONAL UNIVERSITY 5