2019- C, Data, OS

Programming:

1) Complexity of any program

https://philipstel.wordpress.com/2011/03/07/determining-the-complexity-of-an-algorithm-the-basic-part/

2) Tower of Honai problem:

It is very simple:  n, A, B, C

a) Toh(n, A, C, B) <=====Move all n from A to C using B
b) Toh(n-1, A, B, C)<=====First we need to move n-1 from A to B using C
     At this point of time move nth one to C.
c) Toh(n-1, B, C, A)<======Move n-1 from B to C using A


void Toh(int n, char Beg, char End, char Aux){
       if(n >= 1){
           Toh(n-1, Beg, Aux, End);
            printf("%d Dsik move %c to %c \n", n, Beg, End);
           Toh(n-1,Aux, End, Beg);
      }
}
int main()
{
   int n;
   printf("\n Enter The number of disks : ");
   scanf("%d", &n);
   printf("\n ");
   Toh(n, 'A', 'C','B');
   return (0);
}

Algorithm Link:

https://www.youtube.com/watch?v=fffbT41IuB4


3) Fibonacci series

0,1, 1, 2, 3, 5, 8, .........

First=0, Second=1, Next=First+second
first=seconds
second=Next


4) Palindrome number

Example: 5225, 23455432

 while(input){
   sum=sum*10+rem;
   rem= input%10;
   input=input/10;
}


input == sum


5) How to find given number is prime number



6) AVL Tree

AVL trees are often compared with red–black trees because both support the same set of operations and take ${\displaystyle O(\log n)}$ time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced


Alogorithm:

 a) /* 1. Perform the normal BST insertion */
 b) /* 2. Update height of this ancestor node */
 c) /* 3. Get the balance factor of this ancestor
             node to check whether this node became
            unbalanced */
     int balance = getBalance(node);

     // If this node becomes unbalanced, then
     // there are 4 cases



  Basic Insert Part:
 
struct Node* insert(struct Node* node, int val)
 {
     /* 1. Perform the normal BST insertion */
     if (node == NULL)
         return(newNode(val));

     if (val < node->val)
         node->left = insert(node->left, val);
     else if (val > node->val)
         node->right = insert(node->right, val);
     else // Equal keys are not allowed in BST
         return node;


Rotation:
   33 struct Node *rightRotate(struct Node *z)
 34 {  
 35     struct Node *y = z->left;
 36     struct Node *T3 = y->right;
 37    
 38     // Perform rotation
 39     y->right = z;
 40     z->left = T3;


struct Node *leftRotate(struct Node *z)
 54 {
 55     struct Node *y = z->right;
 56     struct Node *T3 = y->left;
 57
 58     // Perform rotation
 59     z->right = T3;
 60     y->left = z;
 61



70 int getBalance(struct Node *N)
 71 {  
 72     if (N == NULL)
 73         return 0;
 74     return height(N->left) - height(N->right);
 75 }


   // Left Left Case
105     if (balance > 1 && val < node->left->val)
106         return rightRotate(node);
107
108     // Right Right Case
109     if (balance < -1 && val> node->right->val)
110         return leftRotate(node);
111    
112     // Left Right Case
113     if (balance > 1 && val > node->left->val)
114     {
115         node->left = leftRotate(node->left);
116         return rightRotate(node);
117     }  
118    
119     // Right Left Case
120     if (balance < -1 && val < node->right->val)
121     {
122         node->right = rightRotate(node->right);
123         return leftRotate(node);
124     }
125    
126     /* return the (unchanged) node pointer */
127     return node;



7) IP-address storeage

   Tries or Radix tree or Red-black tree


8)