Data Structure Lecture Notes PDF

Data structure Dr. Asmaa Awad What are Data Structures? ▪ Data Structures are different ways of organizing data on your computer, that can be used effectively. ▪ A data structure is a way to store and organize data in order to facilitate the access and modifications Data Structure Types ...

Data structure Dr. Asmaa Awad What are Data Structures? ▪ Data Structures are different ways of organizing data on your computer, that can be used effectively. ▪ A data structure is a way to store and organize data in order to facilitate the access and modifications Data Structure Types  Data Structure Types ▪ Linear data structure: data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements  Static data structure: Static data structure has a fixed memory size. It is easier to access the elements in a static data structure.  Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code.  Data Structure Types ▪ Arrays:  it is a collection of items stored at contiguous memory locations. It allows the processing of a large amount of data in a relatively short period. The first element of the array is indexed by a subscript of 0.  Data Structure Types ▪ Stack:  Stack is a linear data structure that follows a particular order in which the operations are performed. The order is LIFO(Last in first out). The entering and retrieving of data is also called push and pop operation in a stack.  Data Structure Types ▪ Queue:  Queue is a linear data structure that follows a particular order in which the operations are performed. The order is First In First Out(FIFO) i.e. the data item stored first will be accessed first. In this, entering and retrieving data is not done from only one end.  Data Structure Types ▪ Linked list:  A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:  Data Structure Types ▪ Tree:  A tree is a non-linear and hierarchical data structure where the elements are arranged in a tree-like structure. In a tree, the topmost node is called the root node. Each node contains some data, and data can be of any type. It consists of a central node, structural nodes, and sub-nodes which are connected via edges.  Data Structure Types ▪ Graph:  A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a finite set of vertices and set of edges that connect a pair of nodes. The graph is used to solve the most challenging and complex programming problems. Data Structure Operations ▪ Navigating  Accessing each data element exactly once so that certain items in the data may be processed ▪ Searching Finding the location of the data element (Key) in the structure ▪ Insertion Adding a new data element to the structure Data Structure Operations ▪ Deletion  Removing a data element from the structure ▪ Sorting Arrange the data elements in a logical order (ascending/descending) ▪ Merging Combining data elements from two or more data structures into one What is an Algorithm? ▪ An algorithm, is a step-by-step procedure for solving a problem in a finite amount of time. What is a good algorithm? ▪ It must be correct ▪ It must be finite (in terms of time and size) ▪ It must terminate ▪ It must be unambiguous  Which step is next? ▪ It must be space and time efficient A program is an instance of an algorithm, written in some specific programming language What is Complexity? ▪ Complexity is a measure of how difficult a problem or a solution is. ▪ There are two types of complexity that are relevant for data structures: time complexity and space complexity. ▪ Time complexity measures how long it takes to execute an operation on a data structure, such as inserting, deleting, searching, or sorting. ▪ Space complexity measures how much memory or storage it takes to store a data structure. ▪ Both time and space complexity depend on the size of the input, which is usually denoted by n. Measurement of Complexity of an Algorithm 1. Best Case Analysis (Omega Notation) ▪ In the best-case analysis, we calculate the lower bound on the running time of an algorithm. ▪ We must know the case that causes a minimum number of operations to be executed. ▪ In the linear search problem, the best case occurs when x is present at the first location. Measurement of Complexity of an Algorithm 2. Worst Case Analysis (Big-O Notation) ▪ In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. (maximum number of operations to be executed.) ▪ For Linear Search, the worst case happens when the element to be searched (x) is not present in the array. When x is not present, the search() function compares it with all the elements of arr[] one by one. ▪ The worst-case time complexity of the linear search would be O(n). Measurement of Complexity of an Algorithm ▪ 3. Average Case Analysis (Theta Notation) ▪ In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. ▪ Sum all the calculated values and divide the sum by the total number of inputs. We must know (or predict) the distribution of cases. ▪ For the linear search problem,we sum all the cases and divide the sum by (n+1). Following is the value of average-case time complexity. Complexity ▪ Big O notation is a powerful tool used in computer science to describe the time complexity or space complexity of algorithms. ▪ It provides a standardized way to compare the efficiency of different algorithms in terms of their worst-case performance. ▪ Big O notation is essential for analyzing and designing efficient algorithms. Complexity Complexity Complexity (O(n)) ▪ Sum number from 1 to n //O(n) //O(1) ▪ Time complexity = 1+n=O(n) Complexity (O(1)) ▪ Sum number from 1 to n //O(n) Formula: //O(1) Sum=n*(n+1)/2 //O(1) ▪ Time complexity = 1+n=O(n) Complexity Complexity ▪ In O(log n) algorithms , the execution time grows logarithmically with respect to the input size.an example is binary search. (increase multiply or division ) //O(log(n)) //O(1) //O(1) ▪ Time complexity =1+log(n)=O() Complexity Complexity (O()) ▪ Example : nested loop //O(n) //O(n) //O(1) ▪ Time complexity =1+n*n=O() Complexity Complexity (n*log(n)) ▪ Example : //O(n) //O(log(n)) //O(1) //O(1) ▪ Time complexity =1+n*log(n)=O(n*log(n))