1.1 Some Definitions

We provide below informal definitions of a few important, common notions that we will frequently use in this lecture notes.

DEF.

Algorithm. A finite sequence of instructions, each of which has a clear meaning and can be executed with a finite amount of effort in finite time.

• whatever the input values, an algorithm will definitely terminate after executing a finite number of instructions.

DEF.

Data Type. Data type of a variable is the set of values that the variable may assume.

Basic data types in C :

• int char float double

Basic data types in Pascal:

• integer real char boolean

DEF.

Abstract Data Type (ADT): An ADT is a set of elements with a collection of well defined operations.

-

The operations can take as operands not only instances of the ADT but other types of operands or instances of other ADTs.

-

Similarly results need not be instances of the ADT

-

At least one operand or the result is of the ADT type in question.

Object-oriented languages such as C++ and Java provide explicit support for expressing ADTs by means of classes.

Examples of ADTs include list, stack, queue, set, tree, graph, etc.

DEF.

Data Structures: An implementation of an ADT is a translation into statements of a programming language,

-

the declarations that define a variable to be of that ADT type

-

the operations defined on the ADT (using procedures of the programming language)

An ADT 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 using the available data structuring facilities, such as arrays, records (structures in C), pointers, files, sets, etc.

Example: A ``Queue'' is an ADT which can be defined as a sequence of elements with operations such as null(Q), empty(Q), enqueue(x, Q), and dequeue(Q). This can be implemented using data structures such as

-

array

-

singly linked list

-

doubly linked list

-

circular array