represents the set of operations that a data structure supports / only provides the list of supported operations, type of parameters they can accept and return type of these operations.

(a)  

provides the internal representation of a data structure. Also provides the definition of the algorithms used in the operations of the data structure.

(a)  

CHARACTERISTICS: Data structure implementation should implement its interface correctly.

(a)  

CHARACTERISTICS: Running time or the execution time of operations of data structure must be as small as possible.

(a)  

CHARACTERISTICS: Memory usage of a data structure operation should be as little as possible

(a)  

NEED FOR A DS: As data grows, search will become slower.

(a)  

NEED FOR A DS: although being very high, falls limited if the data grows to billion records.

(a)  

NEED FOR A DS: As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.

(a)  

This is the scenario where a particular data structure operation takes maximum time it can take. Calculation is based on the MAX no. of operations

(a)  

This is the scenario depicting the average execution time of an operation of a data structure. Calculating computation time / operation time of all inputs.

(a)  

This is the scenario depicting the least possible execution time of an operation of a data structure. Calculating execution time of MIN no. of operations

(a)  

Values / set of values

(a)  

Data item refers to single unit of values.

(a)  

Data items are divided into sub items

(a)  

A.k.a simple attributes / cannot be divided.

(a)  

is that which contains certain attributes or properties, which may be assigned values.

(a)  

Entities of similar attributes

(a)  

is a single elementary unit of information representing an attribute of an entity.

(a)  

is a collection of field values of a given entity

(a)  

is a collection of records of the entities in a given entity set.

(a)  

is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output.

(a)  

3 CHARACTERISTICS OF A DATA STRUCTURE

(a)  

3 COMMON PROBLEMS THAT APPLICATIONS FACE

(a)  

3 EXECUTION TIME CASES

(a)  

5 CATEGORIES OF ALGORITHIMS

(a)  

6 CHARACTERISTICS OF AN ALGORITHM

(a)  

This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.

(a)  

This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.

(a)  

Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.

(a)  

Space is measured by counting the maximum memory space required by the algorithm.

(a)  

the amount of memory space required by the algorithm in its life cycle.

(a)  

is a space required to store certain data and variables, that are independent of the size of the problem.

(a)  

is a space required by variables, whose size depends on the size of the problem.

(a)  

the amount of time required by the algorithm to run to completion.

(a)  

it manipulates data

(a)  

study how data is organized in a computer, how it is manipulated, how it is retrieved, and how it can be utilized, resulting in more efficient programs.

(a)  

the concealing of the implementation details of data object from the outside world

(a)  

the separation between specification of a data object and its implementation

(a)  

a collection of objects and set of operations that act on those objects

(a)  

2 DATA TYPES

(a)  

Combines the description of data structure and association operations / Provides description of elements n terms of data types

(a)  

4 DATA STRUCTURE OPERATIONS

(a)  

Accessing each record exactly once so that certain items in the record may be processed. (This accessing or processing is sometimes called 'visiting" the records.)

(a)  

Finding the location of the record with a given key value, or finding the locations of all records, which satisfy one or more conditions.

(a)  

Adding new records to the structure.

(a)  

Removing a record from the structure.

(a)  

Its elements form a sequence or in other words, a linear list

(a)  

mainly used to represent data containing a hierarchical relationship between elements

(a)  

4 EXAMPLES OF LINEAR DATA STRUCTURES

(a)  

2 EXAMPLES OF NON-LINEAR DATA STRUCTURES

(a)  

Zero or more quantities are externally supplied / Must have zero or more well-defined inputs

(a)  

At least one quantity is produced / algorithm must have 1 or more well-defined outputs.

(a)  

Each instruction is clear and unambiguous / each steps, inputs or outputs should be clear and lead to only one meaning

(a)  

the algorithm terminates after a finite number of steps.

(a)  

every instruction must be basic enough to be carried out; must be feasible.

(a)  

Algorithm must have step-by-step directions / compatible of any programming code.

(a)  

designed to search for a giver item in large data collection

(a)  

used to arrange data items in ascending or descending order

(a)  

Meant to reduce the size of data and program files (image, audio, video)

(a)  

designed for digital signal processing

(a)  

used for encryption of data

(a)  

used for identification of geometric shapes

(a)  

comparing images and shapes

(a)  

designed to identify different programming constructs

(a)  

certain steps are repeated in loops unil the goal is achieved (sorting an array)

(a)  

a given problem is fragmented into sub- problems which are solved partially; terminated when further sub- division cannot be performed; used for searching and sorting.

(a)  

an immediately available best solution at each step is chosen; used for scheduling and graph theory

(a)  

all possible solutions are explored, until the end is reached and then the steps are traced back; useful in graph theory (depth first search, breadth first search; used frequently for traversing trees

(a)  

2 PHASES IN PERFORMANCE EVALUATION

(a)  

2 COMPONENTS OF SPACE COMPLEXITY

(a)  

Helps to compare algorithms. / Describes running time of space complexity.

(a)  

a.k.a space-time or time-memory tradeoff; is a way of solving a problem or calculation in less time by using more storage space (or memory), or by solving a problem in very little space by spending a longtime.

(a)  

is a collection of Homogenous, Ordered and Finite set of elements.

(a)  

implies all elements must be of the same type and have the same structure

(a)  

means that elements are organized in sequence

(a)  

means that each array contains a fixed number of elements.

(a)  

position of an element

(a)  

range of values for the index

(a)  

Smallest value in of index

(a)  

Largest value in of index

(a)  

array has not enough space

(a)  

represents arrangement of data elements in the memory.

(a)  

The address of the first element

(a)  

4 BASIC ARRAY OPERATIONS

(a)  

It is also called Accessing

  -To retrieve an element we must know the Index value

(a)  

  - inserts new element in a position specified by the index

-is also sometimes referred to as Assigning

(a)  

removes an existing element with the given index.

(a)  

involves accessing and processing an array element exactly once

  -It is also called Visiting.

(a)  

Provides a description of elements in terms of data types

(a)  

a collection of data elements called nodes

(a)  

has 2 parts, Information field and link field / separates linked list

(a)  

a value in the information field/ uniquely identifies each node of the list.

(a)  

1st element on the list

(a)  

Last element in the list

(a)  

describes physical arrangement of nodes

(a)  

identifies physical adress of a successor node

(a)  

Storage space is made available out of a special memory block called (a)  

6 OPERATIONS ON LINKED LISTS

(a)  

4 VARIATIONS OF LINKED LISTS

(a)  

the pointer in the tail node points to the front node

(a)  

we can add or remove elements from both sides. / we can traverse in forward and backward directions. In other words we can perform bi-directional traversals

(a)  

is a variant of the doubly linked list / In this case next link pointer in the tail node contains pointer to the first element.

(a)  

combine a set of related list structures into an integrated list / nodes of all the integrated list can be accessed using link pointers

(a)