Chapter one Department Computer Science

This is Data structure chapter one

1. Chapter One Introduction to Elementary Data Structures

2. Get started … Outlines Motivations Design goals Algorithms Asymptotic Analysis Heap Hashing

3. Motivations To enhances the performance of processor, which affect the security, scalability and reusability the computer system To solve the i mportant problems such as sorting, searching,, graph problems, Combinational problems, are basic motivations for designing algorithm

4. Design Goal Solving problem with multiple constraints (problem size performance and cost in terms of space and time) T o design fast, efficient and effective solution to a problem domain. The study of algorithm is to design efficient algorithm not only limited in reducing cost and time but to enhance scalability, reliability and availability

5. The main concern of this course: Correctness of the solutions Decomposition of application into small and clear units which can be maintained precisely Improving the performance of application

6. Definition of Algorithm is a sequence of computational steps that transform the input into the output. is a sequence of operations performed on data that have to be organized in the data structures. A finite set of instruction that specify a sequence of operations to solve a specific problem is a step-by-step procedure to perform a specific task within finite number of steps.

7. Characteristics of Algorithms Input : Must take an input. Output : Must give some output (yes/no value etc.) Definiteness : each instruction is clear and unambiguous. Finiteness : algorithm terminates after a finite number of steps. Effectiveness : every instruction must be basic i.e. simple instruction. (N.B: It is not enough that each operation be definite, but it must also be feasible).

8. Performance of a program A mount of computer memory and time needed to run a program. We use two approaches to determine the performance of a program: Analytical methods for performance analysis Experimental methods for performance measurement that needs to conduct experiments.

9. Algorithm Analysis Concepts AA refers to the process of determining the amount of computing time and storage space required by different algorithms. Its a process of predicting the resource requirement of algorithms in a given environment. In order to solve a problem, there are many possible algorithms. Some are: choose the best algorithm for the problem. To classify data structures and algorithms as good (analyzing in terms of resource requirement). The main resources are Running Time, and Memory Usage

10. Complexity Analysis It is the systematic study of the cost of computation, measured either in time units or in the amount of storage space required. The goal is to have a meaningful measure that permits comparison of algorithms independent of operating platform. Time Complexity : is the amount of computer time it needs from run to completion.

11. Complexity Analysis … Space Complexity : The space complexity of a program is the amount of memory it needs to run to completion. The space need by a program has the following components: Instruction space : is the space needed to store the compiled version of the program instructions. The amount of instructions space that is needed depends on factors such as: The compiler used to complete the program into machine code. The compiler options in effect at the time of compilation

12. Complexity Analysis … Data space : is the space needed to store all constant and variable values. Data space has two components: Space needed by constants and simple variables in program. Space needed by dynamically allocated objects such as arrays and class instances. Environment stack space : is used to save information needed to resume execution of partially completed functions.

13. Expectation from an algorithm Correctness : Algorithms must produce correct result. Less resource usage : Algorithms should use less resources (time and space).

14. Measures of Times The function f(n), gives the running time of an algorithm, depends not only on the size “n‟ of the input data but also on the particular data. The complexity function f(n) for certain cases are: Best Case : The minimum possible value of f(n) is called the best case. Average Case : The expected value of f(n). Worst Case : The maximum value of f(n) for any key possible input.

15. Asymptotic Analysis is concerned with how the running time of an algorithm increases with the size of the input in the limit, as the size of the input increases without bound. Big-Oh Notation (O), Big-Omega Notation ( W ), and Big-Theta Notation ( Q ) are the rate of growth .

16. Big–OH (O) f(n) = O(g(n)), (pronounced order of or big oh), says that the growth rate of f(n) is less than or equal ( < ) that of g(n).

17. Big–OMEGA (  ) f(n) =  (g(n)) (pronounced omega), says that the growth rate of f(n) is greater than or equal to ( > ) that of g(n).

18. Big–THETA (  ) f(n) =  (g(n)) (pronounced theta), says that the growth rate of f(n) equals (=) the growth rate of g(n) [if f(n) = O(g(n)) and T(n) =  (g(n)].

19. Heap Heap is a special tree-based data structure in which the tree is a complete binary tree. Heap has the property of: Max-Heap : the key present at the root node must be greatest among the keys present at all of its children. Min-Heap: the key present at the root node must be minimum among the keys present at all of its children.

20. Applications of Heaps Heapsort sorting algorithm Graph algorithms like Prim’s MST and Dijkstra’s Shortest path algorithm Priority queue

21. Implementations Creating nodes in memory and link them I tree structure (min-heap)

22. Implementations … Arranging the heap elements in an array structure (min-heap) The representation is done as: The root element will be at A[0] Below table shows indexes of other nodes for the i th node: A[(2* i )+1] returns the LEFT child node A[(2* i )+2] returns the RIGHT child node

23. Implementations …

24. Operations using Heap getMin(): it returns the root element of Min-Heap. Time complexity is O(1). getMax(): it returns the root element of Max-Heap. Time complexity is O(1). extractMin(): removes the minimum element from min-heap. Time complexity is O(logn) extractMax(): removes the maximum element from max-heap. Time complexity is O(logn)

25. Operations using Heap … insert(): inserting a new key takes O(logn). If new key is greater than its parent, then we don’t need to do anything; otherwise, we need to traverse up to fix the violated heap property. delete(): Deleting a key takes O(logn). heapify(): is the process of creating a heap data structure from a binary tree. heapify used to create Min-Heap or Max-Heap.