Twitter Facebook Delicious Digg Stumbleupon Favorites More

Friday, 10 March 2017

IPU BCA/BTech Semester 2 - Data Structures - Abstract Data Type (ADT)

Data Structures - Abstract Data Types (ADT)

IPU BCA/BTech Semester 2 - Data Structures - Abstract Data Type (ADT)

(a) What is Abstract Data Type (ADT)? 
(b) Give examples of commonly used ADTs.
(c) What are the advantages of ADTs?

(a) An abstract data type (ADT) is a logical description or a specification of components of the data and the operations that are allowed and it is independent of the implementation. An ADT is a user defined data type that are defined along with their operations.

An ADT consists of two parts:
1. Declaration of data
2. Declaration of operations

(b) Commonly used ADTs are:
Linked Lists,
Priority Queues,
Binary Trees,
Disjoint Sets,
Hash Tables,
Graphs etc.

(c) Advantages of ADTs are:

Encapsulation: The user need not know knowledge of implementing the ADT. Its implementation may be complex but it is be encapsulated in a simple interface while defining it.

Localization of change: Code that uses an ADT object do not require editing if the implementation of the ADT  changes.

Flexibility: Different implementations of an ADT may be more efficient in different situations thus increases the overall efficiency of the program.

Easy to understand and reusable code.

Question: Write down one dimensional array specifications as ADT.

Answer: eltype denotes type of element and ub is the upper bound.

abstract typedef <<eltype, ub>> ARRTYPE(ub, eltype);
condition type(ub) == int;

abstract eltype extract(a, i)  /* written as a[i] */
ARRTYPE(ub, eltype) a;
int i;
precondition 0 <= i < ub;
postcondition extract == a₁

abstract store(a, i, elt)
ARRTYPE (ub, eltype) a;
int i;
eltype elt;
precondition  0 <= i < ub;
postcondition a[i] == elt;

Question: Write down representation of a stack as ADT.


abstract typedef <<eltype>> STACK (eltype);

abstract empty(s)
STACK (eltype s)
postcondition (empty == len(s) == 0);

abstract eltype pop(s)
STACK (eltype) s;
precondition empty(s) == FALSE;
postcondition pop == first(s)
s == sub(s', 1, len(s') - 1);

abstract push (s, elt)
STACK (eltype) s;
eltype elt;
postcondition s == <elt> + s';

Question: Represent queue as Abstract Data Type (ADT).


abstract typedef <<eltype>> QUEUE (eltype);

abstract empty(q)
QUEUE (eltype) q;
postcondition empty == (len(q) == 0);

abstract eltype remove(q)
QUEUE (eltype) q;
precondition empty(q) == FALSE;
postcondition remove == first(q');
q == sub(q', 1, len(q') - 1);

abstract insert (q, elt)
QUEUE (eltype) q;
eltype elt;
postcondition q = q' + <elt>;

See also:
  - Abstract Data Type Notes by CSE Department IIT Kharagpur
  - Data Structure Notes by IIT Kgp


Post a Comment

BCE-Hacks Notes

BCE-Hacks Notes
Chemical Engineering Notes

Maths Resources

Maths Resources
Maths Resources

Buy Books

Buy Books
Buy Books

Geography Quiz

Geography Quiz
Geography Quiz

NodeJS Tutorial

NodeJS Tutorial

History MCQs

History MCQs
History Quiz For Competitive exams


Popular Posts


Recent Posts

Unordered List

Express Print Zone

Eduvictors Quizzes

Online Quizzes, Study notes for CBSE Class 6 - 12

Text Widget


Study notes for Competitive Exams

Developer Bytes

Developer Bytes
Developer Bytes
Powered by Blogger.

Blogger Tutorials

Blogger Templates

Sample Text

Copyright © IP University Musings BCA, MCA, BBA, MBA, BTech Question Papers and Study Notes | Powered by Blogger
Design by SimpleWpThemes | Blogger Theme by