algorithms.md

Big O Notation :

• asymptotic notations to calculate the running time
• longest amount of time an algorithm can possibly take to complete

DataStructure (Create,access,Search,Insert,Update,Delete)

• String

• Array / 2D aray

• LinkedList (Create ,append , display , ReverseDisplay, remove , Change value, Update By Index

    class LinkedList:
        def __init__(self,i):
            self.i=i
            self.nxt:LinkedList=None
  
        def append(self,i):
            if(self.nxt==None):self.nxt=LinkedList(i)
            else:self.nxt.append(i)
  
        def display(self):
            if(self.nxt!=None):
                print(self.i)
                self.nxt.display()
            else:print(self.i)
  
        def reverseDisplay(self):
            if(self.nxt!=None):
                self.nxt.display()
                print(self.i)
            else:print(self.i)
  
        def remove(self,i):
            if(self.i==i):                      #1st ele
                self.i=None
                self.nxt=None
            elif(self.nxt==None):print("Not Found") #last ele
            else:                                   #Middle
                if(self.nxt.i==i):self.nxt=self.nxt.nxt
                else:self.nxt.remove(i)
  
        def change(self,i,j):
            if(self.i==i):
                self.i=j
            elif(self.nxt==None):print("Not Found")
            else:self.nxt.change(i,j)
  
    def upDateIndex(lnkdlst, index, value):
        temp=lnkdlst.nxt
        for i in range(1,index):temp=temp.nxt
        temp.i=value
        return lnkdlst
  

• Set

• Dictionary (HashTable)

• Stack (LIFO)

  • PUSH: l.append(dataval)
  • POP: l.pop()

• Queue (Queue Daily Life - FIFO)

  • PUSH: l.insert(0,dataval)
  • POP: l.pop()

• Binary Tree:

  • In-order Traversal: left subtree is visited first, then the root and later the right sub-tree.

  • Pre-order Traversal: the root node is visited first, then the left subtree and finally the right subtree.

  • Post-order Traversal we traverse the left subtree, then the right subtree and finally the root node.

      class BinaryTree:
          def __init__(self,i):
      	self.i=i
      	self.left:BinaryTree=None
      	self.right:BinaryTree=None
    
          def append(self,i):
      	if(i<self.i):
      	    if(self.left==None):self.left=BinaryTree(i)
      	    else:self.left.append(i)
      	else:
      	    if(self.right==None):self.right=BinaryTree(i)
      	    else:self.right.append(i)
    
          def find(self,i):
      	if(self.i==i):print(i)
      	elif(i<self.i):
      	    if(self.left!=None):self.left.find(i)
      	elif(i>self.i):
      	    if(self.right!=None):self.right.find(i)
      	else:print("Not Found")
    
          def preOrder(self):  #Root > Left > Right
      	print(self.i)
      	if(self.left):self.left.preRoot()
      	if(self.right):self.right.preRoot()
    
          def postOrder(self): #left>Right>Root
      	if(self.left):self.left.postRoot()
      	if(self.right):self.right.postRoot()
      	print(self.i)
    
          def inOrder(self): #Left > Root > Right
      	if(self.left):self.left.inRoot()
      	print(self.i)
      	if(self.right):self.right.inRoot()
    
      def preRoot2(root):
          if root is None:return
          print(root.i)
          preRoot2(root.left)
          preRoot2(root.right)
    
      bt=BinaryTree(10)
      for i in [5,15,4,6,16,14,3]:bt.append(i)
    

Types of Algorithms:

• Recursive Algorithm: same function again and again.
  • No Calculation done until base is reached
  • Uses a Stack (call Stack) called Stack Frame
  • Lot of Function calls for large Dataset lead to Out Of Memory
  • Always Start code with exit Condition First eg:if(n==1):return 1
• Searching Algorithm: searching elements or groups of elements from a particular data structure. They can be of different types
  • Linear Search: all items one by one.
  • Binary Search :
  • Recursively divide array into halfs and compare last element
• Sorting Algorithm: sort groups of data in an increasing or decreasing manner.

  • Bubble Sort

      def BubbleSort(arr):
          for i in range(0,len(arr)-1):
      	for j in range(0,len(arr)-1-i):
      	    if(arr[j]>arr[j+1]):arr[j],arr[j+1]=arr[j+1],arr[j]
          return arr
    

  • Selection Sort: finding the minimum value in a given list and swappng

      def selection_sort(input_list):
          for idx in range(len(input_list)):
              min_idx = idx
              for j in range( idx +1, len(input_list)):
                  if input_list[min_idx] > input_list[j]:
                      min_idx = j
              # Swap the minimum value with the compared value
              input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]
    

• Divide and Conquer Algorithm: This algorithm breaks a problem into sub-problems. It consists of Divide>Solve>Combine

  • Binary Search

      def Search(arr,value):
          mid=len(arr)//2
          if(len(arr)==0):
      	print("Not Found")
      	return
          if(arr[mid]==value): print("Found")
          elif(value<arr[mid]):Search(arr[0:mid],value)
          elif(value>arr[mid]):Search(arr[mid+1:],value)
    

  • Quick Sort

      def QuickSort(arr):
          res1,res2=[],[]
          if(len(arr)==0):return arr
          else:pivot=arr.pop()
          for i in arr:
      	if(i<pivot):res1.append(i)
      	else:res2.append(i)
          return QuickSort(res1)+[pivot]+QuickSort(res2)
    

  • Merge Sort

  • Insertion Sort

• Graph Algorithms
  • Depth First Traversal
  • Breadth First Traversal