Data Structure PDF

Data Structure Prof. Vijya Tulsani, Assistant Professor IT and Computer Science  CHAPTER-1 Introduction of Data Structure Terms Data: facts and statistics collected together for reference or analysis. Collection of values, for example, student's name and its id are the data...

Data Structure Prof. Vijya Tulsani, Assistant Professor IT and Computer Science  CHAPTER-1 Introduction of Data Structure Terms Data: facts and statistics collected together for reference or analysis. Collection of values, for example, student's name and its id are the data about the student. Record: Record can be defined as the collection of various data items, for example, if we talk about the student entity, then its name, address, course and marks can be grouped together to form the record for the student. Structure : Way of organising information , so that it is easier to use. Data organization, in broad terms, refers to the method of classifying and organizing data sets to make them more useful. What is Data Structure ? Data Structures are the programmatic way of storing and organizing data. Is a data organization , management and storage format that enables efficient access and modifications. Allows handling data in an efficient way. Plays a vital role in enhancing the performance of a software or a program as the main function of the software is to store and retrieve the user's data as fast as possible “Way we organise our data” Image source : Google What is Data Structure ? Image source : Google Need of Data Structure As applications are getting complex and amount of data is increasing day by day, there may arise the following problems: 1. Processor speed 2. Data Search 3. Multiple requests Advantages of Data Structures Efficiency – access and store data Reusability Used to manage large amounts of data Specific data structure used for specific tasks Image source : Google Applications of DS Compiler Design Operating System DBMS Simulation Network Analysis AI Graphs Numerical Analysis Statistical Analysis Package Algorithm-Introduction Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. Categories of Algorithm Search − Algorithm to search an item in a data structure. Sort − Algorithm to sort items in a certain order. Insert − Algorithm to insert item in a data structure. Update − Algorithm to update an existing item in a data structure. Delete − Algorithm to delete an existing item from a data structure. Image source : Google Criteria for efficiency of the algorithm Correctness Implementation Simplicity Execution time Memory space required Alternative way of doing the same task. Image source : Google Characteristics of Algorithm Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning. Input − An algorithm should have 0 or more well-defined inputs. Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output. Finiteness − Algorithms must terminate after a finite number of steps. Feasibility − Should be feasible with the available resources. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code. Image source : Google Algorithm Complexity Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X. 1. Time Factor − Time is measured by counting the number of key operations such as comparisons in the sorting algorithm. 2. Space Factor − Space is measured by counting the maximum memory space required by the algorithm. The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data. Image source : Google Example Image source : Google Asymptotic Analysis In mathematical analysis, asymptotic analysis of algorithm is a method of defining the mathematical boundation of its run-time performance. Using the asymptotic analysis, we can easily conclude about the average case, best case and worst case scenario of an algorithm. It is used to mathematically calculate the running time of any operation inside an algorithm. Usually the time required by an algorithm comes under three types: 1. Worst case: It defines the input for which the algorithm takes the huge time. 2. Average case: It takes average time for the program execution. 3. Best case: It defines the input for which the algorithm takes the lowest time Image source : Google Asymptotic Notations - Big oh Notation (O) It express the upper boundary of an algorithm running time. It measures the worst case of or upper bound of running time complexity or the longest amount of time, algorithm takes to complete their operation. It is represented as shown below: For example: If f(n) and g(n) are the two functions defined for positive integers, then f(n)=O(g(n)) IFF F(n)≤cg(n) for all n≥no, c=0 ,n0>=1 This implies that f(n) does not grow faster than g(n), or g(n) is an upper bound on the function f(n). Image source : Google Asymptotic Notations -Omega Notation (Ω) It is the formal way to represent the lower bound of an algorithm's running time. It measures the best amount of time an algorithm can possibly take to complete or the best case time complexity. If we required that an algorithm takes at least certain amount of time without using an upper bound, we use big- Ω notation For example: If f(n) and g(n) are the two functions defined for positive integers, then f(n)= Ω(g(n)) IFF F(n)>=c*g(n) for all n≥no,c=0 ,n0>=1 Image source : Google Asymptotic Notations -Theta Notation (?) It is the formal way to express both the upper bound and lower bound of an algorithm running time. It is represented as shown below: Expressed average case scenario c2*g(n) For example: If f(n) and g(n) are the two functions defined for positive integers, then f(n)= (g(n)) c1*g(n) IFF C1*g(n)