PYTHON ALGORITHMS, DATA STRUCTURE, SORTING TECHNIQUES

PYTHON ALGORITHMS

1. CHAPTER 6 ALGORITHMS

2. Algorithm: An algorithm is a set of instructions for solving a problem or accomplishing a task . To design a better a program, algorithm is required

3. Algorithm vs program Algorithm To design It can be written in any natural language The person who is having the particular domain knowledge can write algorithm Algorithm is independent of hardware and software P rogram To Implement It can be written in any programming language Programmers can write programs Program is dependent on hardware and software

4. How to write an algorithm? Problem- Design an algorithm to add two values and display the result Step 1- Start Step 2- Declare three integers a,b,c Step 3- Define values of a & b Step 4- add values of a & b Step 5- Store added values to c Step 6- print c Step 7- Stop

5. Different types of Algorithm Searching Binary search tree AVL Hashing Sorting Shortest path Dynamic programming

6. Searching algorithms Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored . T hese algorithms are generally classified into two categories : Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search. Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example: Binary Search.

7. Linear search-compare key element with every element in an array

8. def search( arr , x): for i in range( len ( arr )): if arr [ i ] == x: return i return -1 print(search([12,34,23,54,32,78,67 ],80))

9. Binary search First sort the elements in ascending order Initialize the first value with low. Initialize as 0 Initialize the last value with high. Initialize as n-1 Now we can calculate the middle values Mid = low+high //2

10. def binary_search ( arr , low, high, x): if high >= low : mid = (high + low) // 2 if arr [mid] == x: return mid elif arr [mid] > x: return binary_search ( arr , low, mid - 1, x ) else: return binary_search ( arr , mid + 1, high, x ) else : return -1 arr = [ 2, 3, 4, 10, 40 ] x = 10 result = binary_search ( arr , 0, len ( arr )-1, x ) if result != -1: print("Element is present at index", result) else: print("Element is not present in array")

11. Jump search- Searching algorithm for sorted arrays or list Procedure: 1.Calculate the array size and jump size(j= sqrt (n)). 2.Jump from index i to index j 3.Check x== arr [ j ] , return x or x< arr [ j ], back a step and perform linear operation

12. Example:

13. Interpolation Search Conditions to be satisfied 1.Sorted array 2.Elements should be uniformly distributed Example: 2 4 6 8 10 12 3.Formula to find the key element Pos =l+(x-a[l])/(a[h]-a[l]) x(h-l)

14. Binary Search Tree(BST) A binary Search Tree is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key . There must be no duplicate nodes.

15. Example: class Node: def __ init __(self, data): self.left = None self.right = None self.data = data def PrintTree (self): print( self.data ) root = Node(8) root.PrintTree ()

16. Construction and insertion of elements in BST If the tree is empty, then consider the element as a root If the element is greater than the root, insert to right subtree If the element is lesser than the root, insert to left subtree

17. Example: 50,30,10,60,80,20,70,55,35

18. Python implementation def insert(self, data ): if self.data : if data < self.data : if self.left is None: self.left = Node(data) else: self.left.insert (data) elif data > self.data : if self.right is None: self.right = Node(data) else: self.right.insert (data) else: self.data = data def PrintTree (self): if self.left : self.left.PrintTree () print( self.data ), if self.right : self.right.PrintTree () # Use the insert method to add nodes root = Node(12) root.insert (6) root.insert (14) root.insert (3) root.PrintTree ()

19. Deletion: Delete a node having no children(leaf nodes) Delete a node having 1 children  Child replace the position of parent Delete a node having 2 children  Replace parent with child Child can be minimum element of right subtree Child can be maximum element of left subtree

20. Searching, Minimum & maximum element Example: 8 10 3 14 1 6 4 7 13

21. AVL Tree It should satisfy the properties of binary search tree Self balancing binary search tree- Balancing heights of left sub tree and right sub tree Measured in terms of balancing factor If BST obeys balancing factor, we call that as AVL tree Balancing factor=Height of LST-Height of RST Every node in a tree should contain the Balancing factor as either 0 or 1 or -1 Invented by Adelson,Velsky,Lindas We can perform the operations like insertion and deletion in AVL tree

22. Rotations involved in AVL Tree There are 4 types rotations involved to change the unbalanced tree to balanced tree 1.LL rotation 2.RR rotation 3.LR rotation 4.RL rotation

23. LL rotation- Left subtree inserting node on left side

24. RR rotation- Right subtree inserting a node on Right side

25. LR Rotation- Left subtree inserting node on right side

26. RL rotation-Right subtree inserting node on left side

27. Insertion operation in AVL tree Example: 20,30,80,40,10,60,50,70

28. Sorting Algorithms A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements . There are different types of sorting techniques Bubble sort Insertion sort Selection sort Merge sort Heap sort

29. Bubble sort- Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order .

30. Insertion Sort- compare each element with all the previous element and inserting the correct element into the desired location

31. Selection sort- Selection sort is a sorting algorithm  that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

32. Merge sort- Merge sort is one of the most efficient sorting algorithms. It is based on the divide-and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists until each has only one item, then merges those sublists into a sorted list

33. Heap sort To implement heap sort, we need to follow two properties. 1.Constructing complete binary tree 2.Follow the heap order  min heap & max heap Min heap- Parent node shoud be lesser than the child nodes. Max heap- Parent node should be greater than the child nodes . Delete and replace the root node with tha last chid node. Deleted node should be placed at the last position of the array.

34. Example: 40,60,30,10,20,50

35. Graphs Graph is defined as a set of (V,E) pairs, where V is set of vertices, E is set of edges Vertices- represented by circles Edges- represented as lines A,B,C are vertices (A,B),(B,C),(A,C)-Edges A B C

36. Different types of graphs:

37. Graph traversals-Travelling to all the nodes Two algorithms in graphs traversals 1.Depth First Search(DFS)- stack data structure 2.Breadth First Search(BFS)-Queue datastructure A B C D E F G

38. Spanning tree- A spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible number of edges Rules to be followed while constructing Spanning tree 1.Spanning tree should connect all vertices of a graph. 2.If graph is having n vertices, spanning tree should have n-1 edges. 3.Should not contain any cycles.

39. Kruskal’s Algorithm: To find the minimum cost spanning tree Procedure: Arrange all the elements in ascending order based on the cost. Consider least cost weighted edge and include it in a tree. If the edge forms a cycle,just ignore and consider the next least cost weighted edge. Repeat step 2 until all the vertices are included in a tree.

40. Example: a b d f e c

41. Prim’s Algorithm: To find minimum cost spanning tree Procedure: Consider any vertex of a graph. Find all the edges of the selected vertex to all new vertices. Select the least weighted edge and include it in a tree. If the least weighted edge forms a cycle , then discard it. Repeat step 2 and 3 until all the vertices are included in a tree.

42. Example: a b d f e c

43. Shortest path routing algorithm Route- Path through which the packet travels from source to destination. We can find the shortest route with the help of some functions between nodes Functions can be cost, distance,time,traffic etc., Finding shortest path can be done in two ways 1.By constructing a tree 2.Using Dijkstra’s algorithm

44. Consider a small network

45. Dijkstra’s Algorithm

46. Dynamic Programming Used to solve optimization problems. The Dynamic Programming works: 1.Breaks down the complex problem into simpler sub problems 2. Find optimal solution to these sub problems. 3. Store the result of sub problems 4. Reuse them so that same sub problem is not calculated more than once 5. Finally calculate the result of complex problem Applicable to the problems having the properties: 1.Optimal substructure 2.Overlapping Sub problem

47. Example: Recursive method def fib(n): if n<=1: return n else: return(fib(n-1)+fib(n-2)) nterms =4 if nterms <=0: print("Enter positive integer") else: for i in range( nterms ): print(fib( i ))

48. Dynamic programming method class solution(object): def fib( self,n ): if n==0: return(0) if n==1: return(1) dp =[0]*(n+1) dp [0]=0 dp [1]=1 print( dp ) for i in range(2,n+1): dp [ i ]= dp [i-1]+ dp [i-2] print( dp ) out=solution() out.fib (5)