Data Structure

Data Structure is a systematic way to organize data in order to use it efficiently. Following terms are the foundation terms of a data structure.

Interface
− Each data structure has an interface. Interface represents the set of operations that a  data structure  supports. An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations.

Implementation
−  Implementation  provides  the  internal  representation  of  a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure.

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution.

So we can say −

·    The problem should be able to be divided into smaller overlapping sub-problem.

·      An optimum solution can be achieved by using an optimum solution of smaller sub- problems.

·    Dynamic algorithms use memorization.

Comparison

In contrast to greedy algorithms, where local optimization is addressed, dynamic algorithms are motivated for an overall optimization of the problem.

In contrast to divide and conquer algorithms, where solutions are combined to achieve an overall solution, dynamic algorithms use the output of a smaller sub-problem and then try to optimize a bigger sub-problem. Dynamic algorithms use memorization to remember the output of already solved sub-problems.

Example

The following computer problems can be solved using dynamic programming approach −

·     Fibonacci number series

·     Knapsack problem

·     Tower of Hanoi

·     All pair shortest path by Floyd-Warshall

·     Shortest path by Dijkstra

·     Project scheduling

Dynamic programming can be used in both top-down and bottom-up manner. And of course, most of the times, referring to the previous solution output is cheaper than re- computing in terms of CPU cycles.

Data Definition

Data Definition defines a particular data with the following characteristics.

·    Atomic − Definition should define a single concept.

·    Traceable − Definition should be able to be mapped to some data element.

·    Accurate − Definition should be unambiguous.

·    Clear and Concise − Definition should be understandable.

Data Object

Data Object represents an object having a data.

Data Type

Data type is a way to classify various types of data such as integer, string, etc. which determines the values that can be used with the corresponding type of data, the type of operations that can be performed on the corresponding type of data. There are two data types −

·     Built-in Data Type

·     Derived Data Type

Built-in Data Type

Those data types for which a language has built-in support are known as Built-in Data types. For example, most of the languages provide the following built-in data types.

·     Integers

·     Boolean (true, false)

·     Floating (Decimal numbers)

·     Character and Strings

Derived Data Type

Those data types which are implementation independent as they can be implemented in one or the other way are known as derived data types. These data types are normally built by the combination of primary or built-in data types and associated operations on them. For example −

·     List

·     Array

·     Stack

·     Queue

Basic Operations

The data in the data structures are processed by certain operations. The particular data structure chosen largely depends on the frequency of the operation that needs to be performed on the data structure.

·     Traversing

·     Searching

·     Insertion

·     Deletion

·     Sorting

·     Merging

Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array.

·    Element − Each item stored in an array is called an element.

·      Index − Each location of an element in an array has a numerical index, which is used to identify the element.