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. Information : Organised data 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 ? Image source : Google 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 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 Greedy Algorithms An algorithm is designed to achieve optimum solution for a given problem. In greedy algorithm approach, decisions are made from the given solution domain. As being greedy, the closest solution (localized) that seems to provide an optimum solution is chosen. Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions. However, generally greedy algorithms do not provide globally optimized solutions. Image source : Google Greedy Algorithms-Examples Travelling Salesman Problem Prim's Minimal Spanning Tree Algorithm Kruskal's Minimal Spanning Tree Algorithm Dijkstra's Minimal Spanning Tree Algorithm Graph - Map Coloring Graph - Vertex Cover Knapsack Problem Job Scheduling Problem Image source : Google Divide and conquer In divide and conquer approach, the problem in hand, is divided into smaller sub- problems and then each problem is solved independently. When we keep on dividing the sub problems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those "atomic" smallest possible sub-problem (fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the solution of an original problem. Image source : Google Steps of Divide and conquer Algorithm 1. Divide/Break 2. Conquer/Solve 3. Merge/Combine Image source : Google Dynamic Programming 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 that − 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. Image source : Google 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 − 1. Built-in Data Type 2. Derived Data Type Image source : Google 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. 1. Integers 2. Boolean (true, false) 3. Floating (Decimal numbers) 4. Character and Strings Image source : Google 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 − 1. List 2. Array int arr; 3. Stack 4. Queue Image source : Google Classification of Data Structure Image source : Google Primitive Data Structure There are basic structures and directly operated upon by the machine level instructions. In general, there are different representation on different computers. It is a fundamental data type. Integer, Floating-point number, Character constants, string constants, pointers etc, fall in this category. Image source : Google Non-Primitive Data Structure These are derived from the primitive data structures. The non primitive data structures are not directly operated by machine level instruction. The non primitive data structure is also known as complex or composite data structure. The non-primitive data structures emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items. Lists, Stack, Queue, Tree, Graph are example of non-primitive data structures. Linear Data Structure Data structure where data elements are arranged sequentially or linearly where the elements are attached to its previous and next adjacent in what is called a linear data structure. In linear data structure, single level is involved. Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. Its examples are array, stack, queue, linked list, etc. Image source : Youtube video Non-Linear Data Structure Data structures where data elements are not arranged sequentially or linearly are called non-linear data structures. In a non-linear data structure, single level is not involved. Therefore, we can’t traverse all the elements in single run only. Non-linear data structures are not easy to implement in comparison to linear data structure. It utilizes computer memory efficiently in comparison to a linear data structure. Its examples are trees and graphs Image source : Google Operations on DS Creation Selection Updation Deletion Image source : Google Creation This operation is used to create a data structure. e.g. In ‘C’ language using declaration statement int n = 45; Once any data is declared, it is associated with memory space, address and the value. 1010 45 n Address Value Name Image source : Google Selection This operation is used to access data within data structure Selection is used to refer the value stored in data structure e.g. created data structure is int a = 10; So value 10 is referred from created data structure. Image source : Google Deletion Once the structure is used and its purpose is over, it is to be destroyed. Image source : Google Operations on Non-Primitive Data Structure Image source : Google Pointers Pointer is used to points the address of the value stored anywhere in the computer memory. To obtain the value stored at the location is known as dereferencing the pointer. Image source : Google Strings In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. A string is generally considered as a data type and is often implemented as an array data structure of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence (or list) data types and structures. Image source : Google Strings in C string is stored in an array of characters. Each character in a string occupies one location in an array. The null character ‘\0’ is put after the last character. This is done so that program can tell when the end of the string has been reached. For example, the string “Hello” is stored as Image source : Google Strings Since the string contains 5 characters. it requires a character array of size 6 to store it. the last character in a string is always a NULL('\0') character. Always keep in mind that the ‘\0' is not included in the length if the string, so here the length of the string is 5 only. Notice above that the indexes of the string starts from 0 not one so don't confuse yourself with index and length of string. 5 Image source : Google String functions #include include this library to your program to use some of the inbuilt string manipulation functions present in the library. There are about 20-22 inbuilt string manipulating functions present in this library. 1.strlen("name of string") 2. strcpy( dest, source) 3. strcmp( string1, string2 ) Image source : Google strlen( string ) Declaration and usage of strlen() function It is one of the most useful functions used from this library, whenever we need the length of the string say "str1“ vijya we write it as int len; len = strlen(str1); len will be the length of the string "str1".(it will include all the spaces and characters in the string except the NULL(‘\0') character. Image source : Google strcpy( dest, source) Str1=“Vijya” Str2=“” This function copies the string "source" to string "dest". Declaration strcpy( str2, str1 ); strcpy(“”,Vijya) strcpy(Vijya,Vijya) Return value This returns a pointer to the destination string dest. Image source : Google strcmp( str1, str2 ) This function is used to compare two strings "str1" and "str2". this function returns zero("0") if the two compared strings are equal, else some none zero integer. Declaration and usage of strcmp() function strcmp( str1 , str2 ); //declaration //using this function to check given two strings are equal or not. Str1=Vijya str2=vibhuti if( strcmp( str1, str2 )==0) { printf("string %s and string %s are equal\n",str1,str2); } else printf("string %s and string %s are not equal\n",str1,str2); 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)