Give introduction to Data Structure and Algorithms

Question

Introducttion to Data structure and Algorithms

1. Basic terminologies

• How it is classified ? 
• Classification on how many types 

2. Variables

• How many variables are there? 
• Why and when it is used?
• Examples

3. Data types

• what are data types ? 
• Its functions
• How many types? 
• Examples

4. Data structure

• Its definition
• Its types
• Examples 
• Linear data structure and its examples
• Non linear data structure and its examples 

5. Abstract Data Types(ADT's) 

• what is ADT's? 
• What are its functions? 
• Examples

Answer 1

Introduction

Algorithm :

Finite set of steps to solve a problem is called algorithm. Steps means instructions which contains fundamental operators.

• Every algorithm must satisfy following criteria:  

Input: 

• There are zero or more quantities which are externally supplied. 

Output:

• At least one quantity is produced. 

Definitness:

• Each instruction must be clear and unambiguous. 

 Finiteness:

•  If we trace out the instruction , then for all cases the algorithm will terminate after finite number of steps. 

 Effectiveness:

•  Every instruction must be sufficiently basic that it can be carried out by a person easily. 

---

2. Some basic terminolgies related to Data Structure:

 Data:

• In  general, data is input quantity or value and is processed by an algorithm.

Data types:

• It refers to the type of quantities that variable may hold in a programming language. Every programming language has a set of inbuilt data types(int, char, etc.) and instructions which manipulates the variable of this data types, but some other data types cannot be handled/manipulated by instructor known as well defined data types.  

It is of two types :

1) System defined data types(primitive data type)

2) User defined data types

1) System defined data types(primitive data tpes):

They are the data types which are defined by a system. For example:int, float, char, double, bool, etc.

2) User-defined data types:

Basically, they are the data types which are defined by a user itself.

Data object:

Data object is a term referring to a set of elements. Now, we want to describe the set of operator which may legally applied. This implies we must specify the set of operation and show how they work.

---

3. What is Data structure? 

Data structure: 

Data structure is an arrangement of data in computer memory in such a way that we can perform operations on these data in an effective way. 

Examples:Arrays, linked list , stack, trees, graphs, table, sets.

• Data structures are basic building blocks of any software program. 

• When you are building a home , you need certain bricks, metal rods, clay, rocks, sand wooden parts and building material etc. On top of that you apply instructions to building a home, you will get a home as a result. Similarly when you building a software applicaton you need raw building blocks which are basically your data structures like array,linkedlist, tree etc. On top of that you apply code instructions that operates on those data structures as result you will get a software application.

• Depending on the organization of the elements , it can be classified in two types:

1) Linear Data Structure:

Here, elements are accessed in sequential order. Examples:Linked lists, arrays,stacks and queues.

 Arrays:

• Arrays is a collection of continuous data elements that stores the common name. These elements are stored in continuous memory location. It has following advantages,
• It has a fixed rate. 
• It always stored in continuous memory loaction.  

 Linked lists:

Linked list is a dynamic data structure which can be represented by links. Each element is called node. Each node contains two parts i. e. data element and address of the next node. Last value or node pointer contains null value means end of the list. It’s advantages are as follows,

• Adding is easy. 
• Size is not fixed and no memory wastage.  

 Stack:

• Stack is a LIFO data structure (last in first out) in which element are inserted last that element out first . It has two variables.
• Top is used to store the address of top most element of a stack. 
• Max is used to hold the total number of elements that are available in stack.  

 Queue:

• It is FIFO(first in first out) in which the element is inserted first that element come out first, it has two variables i. e. front and rear.
• The elements in a queue are added at one end called the rear. 
• Removed from the other end called the front.  
• Every queue will have front and rear variables.  

2) Non-linear data structure:

We can access or stored elements in non linear order. Examples:Trees , tables,sets,graphs. 

Tree:

•  Atree is a non-linear data structure which consist of collection of nodes.  
• The simplest form of a tree is a binary tree. A binary tree consists of a root node and left and right sub-trees. 
•  Where both subtrees are also binary trees. Each node contains a data elements.  

Graphs:

• A graph is a non-linear data structure which is collection of vertices(also called nodes) and edges.
•  It can also be used to represent a computer network where the nodes are workstations and the edges are the network connectors. 
•  Two nodes are  connected via an edges.  

 On the basis of opeartion, data structure are:

 Traversing :

• Visiting each element of the data structure in order to perform some task/opeartions like sorting/searching.

 Insertion :

• Process of adding the elements to the data structure at any location.

 Deletion:

• Process of removing an element from the data structure from any location/random location.

 Searching:

Finding the location of an element within the data structure.

Sorting:

• Process of arranging the data structure in specific order.

 Merging:

• Combining of two similar list of size m and n to produce third result.

 Data Variables: 

For example:We have placeholders such as p and q ;which holds data . So, in data structure variables are those which acts as placeholder to hold data.

---

•  At this stage data structure should be designed, so that we know what it does, but not necessarily how it will do it.

• For simplification for the process of solving problems, we combine the data structures with their operations and thus, called Abstract Data Types.

4. What is abstract data Types (ADTs) in Data Structures?

An abstract data types(ADT’s) 

• is a concept where we define the data type , its possible set of values and the possible set of operations on such a data type without referring to how it is going to be implemented.

in other words, ADTs are entities that are definitions of data and operations but do not have implementation details.

• It consists of two parts namely:
•  Declaration of data
•  Declaration of operations

Examples of abstract data types are linked lists, stacks, queues, priority queues, binary trees, dictionaries, disjoint sets, hash tables, graphs , etc.

Since the data values and operations are defined with mathematical precision, rather than as an implementation in a computer language. So implementation can vary if you change language like c,c++,java, python etc. but data and operations are fixed and come under abstract/logical view.

ADT specifies only what operations are to be performed without referring process of actual implementation of these operations.

For example, an ADT for a stack might include operations such as initialization, pushing data, popping data, destroying the stack, checking to see if the stack is full, checking to see if the stack is empty, and so on.

---