Cs520 Advanced Analysis of Algorithms and Complexity

• Data Abstraction and Basic Data Structures

Abstract Data Type (ADT)

• An ADT describes a set of objects sharing the same properties and behaviors
• The properties of an ADT are its data
• The behaviors of an ADT are its operations or functions
• Thus, an ADT couples its data and operations
• OOP emphasizes data abstraction

• Abstraction: hide implementation details.
• A data structure is the physical implementation of an ADT.

• Logical vs. Physical Form
• Data items have both a logical and a physical form.
• Logical form:
• definition of the data item within an ADT.
• Physical form:
• implementation of the data item within a data structure.

Data Abstraction and Basic Data Structures

• Improving efficiency by building better
• Data Structure
• Object IN
• Abstract Data Type
• Specification
• Design
• Architecture [Structure, Function]
• Abstract Data Types
• Lists, Trees
• Stacks, Queues
• Priority Queue, Union-Find
• Dictionary

• ADT

Abstract Data type

• i is an instance of type T, i  T
• e is an element of set S, e  S
• o is an object of class C, o  C
• Abstract Data Type
• Structures: data structure declarations
• Functions: operation definitions
• An ADT is identified as a Class
• in languages such as C++ and Java

ADT Specification

• The specification of an ADT describe how the operations (functions, procedures, or methods) behave
• in terms of Inputs and Outputs
• A specification of an operation consists of:
• Calling prototype
• Preconditions
• Postconditions
• The calling prototype includes
• name of the operation
• parameters and their types
• return value and its types
• The preconditions are statements
• assumed to be true when the operation is called.
• The postconditions are statements
• assumed to be true when the operation returns.