Data structure unit 1.pptx.pdf

Data Structure Unit 1 data and Information Collection of raw facts and figures is called Data and it is meaningless. Information is the processed data done by computer.  Different forms of Data Represent...

Data Structure Unit 1 data and Information Collection of raw facts and figures is called Data and it is meaningless. Information is the processed data done by computer.  Different forms of Data Representation Images Text Numbers Audio and Video  Difference between data and information Data Information Unrefined facts and Output of processed figures worked as input Meaning data Individual unit , contains Product and group of raw materials and Feature data collectively carry meaningless logical meaning Records and Based on Analysis Observation  Data Structure It is a data organization, management, and storage format that enables efficient access and modification. collection of data values the relationships among them, and the functions or operations that can be applied to the data. a mathematical or a logical model of a particular organization of data items. how to store data in memory  What is a Need of Data Structure? Computer is an electronic machine which is used for data processing and manipulation. In order to make computer work we need to know Representation of data in computer. Accessing of data. How to solve problem step by step. For doing this task we use data structure.  Data Structure Non Primitive Primitive Linear Non Linear e.g. Float, e.g.Array,stack, e.g. graph, integer,charac queue,linked ter list tree Short description of various data structures Array Amit Ajay John Rajesh Jatin 1 2 3 4 5 It is a linear collection of finite number of data elements Above is a one dimensional array S Size of Array : ub-lb+1 Student name Rajesh is denoted as S  Linked List ❖ It is a linear collection of data elements in which data elements are managed by collection of nodes where each node contains link or pointer which points to the next node. ❖ The beginning is maintained by special pointer variable which contains address of first node ❖ Last node contains special value called NULL  Stack ❖ It is a linear collection of data elements in which insertion and deletion are restricted at only one end known as top. ❖ It is restricted kind of data structure. ❖ In stack, elements are removed in reverse order i.e. LIFO pattern  Queue ❖ It is a linear collection of data structure in which insertion can take place at one end and deletion can take place at other end. ❖ It is popularly known as FIFO list  Tree ❖ It is non linear kind of data structure which is used to represent data elements having hierarchical relationship between them. ❖ It is also referred as Parent – Child relationship. ❖ In non linear data structure each element can have many different next elements where as in that of linear , each element has fixed next element.  Graph ❖ It is non linear kind of data structure which is used to represent data having relationship among its elements which are not necessary hierarchical in nature. ❖ It is a collection of nodes and edges where edges connects various pairs of nodes.  Non Linear Linear DS DS Data In Linear sequence Not in linear sequence arrangement Data In single run Traversed Not in single run Implementata Easy Difficult tion Each item is related to Relation with Every item is attached its next and previous other items to many other items items Data Structure Study covers following topics 1 Amount of memory required to store data Amount of time required to process 2 3 Representation of data in memory Operations performed on that data 4  Different Data Types ❖ Primitive Data Type It deals with set of values, their representation and a set of operations that can be applied to them. ❖ Abstract Data Type It deals with set of values and a set of operations that can be applied to them.  file organization FO refers to the way data is stored in a file. It is very important as it determines the method of access, efficiency , flexibility and storage devices to use. Different File organization techniques are Sequential file organization Random file organization Indexed sequential file organization Data structure vs file organization In implementation In access method Types of memory used  Create Destroy Selection Operations Updation Splitting on Data Structure Merging Sorting Searching  Operations on Data Structure 1) Create: This operation results in reserving memory for program elements 2) Destroy: This operation destroys memory space allocated for specific data structure 3)Selection: It deals with accessing a particular data within data structure. 4)Updation: It updates or modifies data in the data structure.  Operations on Data Structure 5) Searching: It finds the presence of desired data item in the list of data items 6) Sorting: This is a process of arranging all data items in a data structure in a particular order ie ascending or descending. 7) Merging: It is a process of combining data items of two different sorted list into single sorted list 8) Splitting: It is a process of partitioning single list into multiple list Question and answer 1) File organisation is the way of arranging data in __________ 2) Data structure deals with the arrangement of data in _______ memory. 3) _______is a process of partitioning single list into multiple list. 4) _______process updates or modifies the data in data structure. 5) _____process arranges data either in ascending or in descending order. 6) ___________operation results in reserving memory for program elements. Contd…… 7) ______process deals with accessing particular data within data structure. 8) The process of combining data items of two different sorted list into single sorted list is known as Merging____________. 9) _______process finds the presence of desired data item in the list of data items. 10)_________operation destroys memory space allocated for a specific data structure.  What is an algorithm? Instructions given to the computer to solve a particular problem is known as “Algorithm.” It is defined as finite collection of well defined steps designed to solve a particular problem. Data structure is implemented by using algorithm. Algorithm states how data will be manipulated Characteristics of an algorithm Input Process Output Finiteness Effectiveness Contd….. 1) Input: An algorithm must take some inputs that are required for the solution of a problem. 2) Process: An algorithm must perform certain operations on the input data which are necessary for the solution of a problem. 3) Output: An algorithm should produce certain output after processing the inputs. 4) Finiteness: An algorithm must terminate after executing certain finite number of steps. 5) Effectiveness: Every step of an algorithm should play a role in the solution to the problem.  Importance of algorithm analysis To solve any problem there are two basic requirements 1. Data 2. Algorithm To efficiently process the data , we decide the suitable data structure. Once the data structure is decided , the concentration is given to the choice of algorithm. Problem can be solved by using efficient algorithm.  Factors for deciding efficient algorithm Programming Requirements of an algorithm Space Requirements of an algorithm Time Requirements of an algorithm  Programming Requirements of an Algorithm 1. An Algorithm must use the features supported by the programming language in which it is to be implemented. 2. An algorithm is of no use if it can not be programmed and executed. 3. Therefore , algorithm must satisfy the programming features of the language s Space Requirement of an algorithm To execute any program , space is needed for various reasons 1. Space Required by Data: This includes space required to store variables and constants which is generally fixed. This space is allocated dynamically hence this space is not fixed. 2. Space Required by Instructions: This is the space required to store instruction sets.This space remains unchanges as the instructions of the program do not change during run time  Time Requirement of an Algorithm Each algorithm takes some amount of time to execute. The study for the time requirement of an algorithm is important for various reasons 1. Sometimes it is necessary to know in advance , the required to execute a program is within acceptable limit or not. 2. There can be various solutions for a particular problem each with different time requirements. One can choose the most optimal solution. 3. The execution time is depends on machine/processor and size of an algorithm. So its always better to estimate execution time irrespective of machine/processor. Complexity of an algorithm Complexity of an algorithm is a measure of the amount of time and/or space required by an algorithm for an input of a given size (n) Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input. If time and space requirement is more then complexity of an algorithm is also more. If time and space requirement is less then complexity of an algorithm is also less. Out of two, space requirement of the algorithm is not very important as it is available at low cost. Hence time requirement of the algorithm is considered as important factor to find complexity.  For example, consider an algorithm which sorts an array of size 2000 will definitely take more time than to sort array of size 200. It is calculated by finding number of times key operation is executed. Key operation is the major operation that is executed maximum number of times. Time complexity is further classified into three categories. 1. Worst Case Complexity 2. Best Case Complexity 3. Average Case Complexity  1) Worst Case Complexity: If the running time of an algorithm is longest for all the inputs then the complexity is called “Worst Case”. 2) Best Case Complexity: If the running time of an algorithm is shortest for all the inputs then the complexity is called “Best Case”. 3) Average Case Complexity: If the running time of an algorithm is falls between worst case and best case then the complexity is called “Average Case”.