## Stacks and Queues

Stacks and Queues

Both stacks and queues are like lists (ordered collections of items), but with more restricted operations. They can both be implemented either using an array or using a linked list to hold the actual items.

### Stacks

Think of a stack of newspapers, or trays in a cafeteria. The only item that can be taken out (or even seen) is the most recently added item; a stack is a Last-In-First-Out (LIFO) data structure.

## Merge Sort Algorithm Merge sort is based on the divide-and-conquer approach. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems. Continue reading

## QuickSort Algorithm

Features

• Similar to mergesort – divide-and-conquer recursive algorithm
• One of the fastest sorting algorithms
• Average running time O(NlogN)
• Worst-case running time O(N2)

Basic idea

• Pick one element in the array, which will be the pivot.
• Make one pass through the array, called a partition step, re-arranging the entries so that:
• the pivot is in its proper place.
• entries smaller than the pivot are to the left of the pivot.
• entries larger than the pivot are to its right.
• Recursively apply quicksort to the part of the array that is to the left of the pivot,
and to the right part of the array.

Here we don’t have the merge step, at the end all the elements are in the proper order. Continue reading

## Prim’s Algorithm

At first a peak is chosen in random order ,which for simplicity we accept it as V(1).This way two sets of pointers are initialized,the 0={1} and P={2…n}.          The O set (the O is taken from the Greek word Oristiko which means Terminal),will always contain the pointers of those peaks which are terminally attached in the T tree.The V(1) peak has already been attached in the Ttree.The P set( P is taken form the Greek word Prosorino which means Temporary) contains the rest of the pointers for the peaks,P={1…n}-O which are those pointers who have not been terminally connected with a node of T,that means they are not attached in the tree.

## How to measure time taken by a function in C?

To calculate time taken by a process, we can use clock() function which is available time.h. We can call the clock function

at the beginning and end of the code for which we measure time, subtract the values, and then divide by CLOCKS_PER_SEC (the number of clock ticks per second) to get processor time, like following. Continue reading

## Program: Pascal’s Triangle

is a triangular array of the binomial coefficients. Write a function that takes an integer value n as input and prints first n lines of the Pascal’s triangle. Following are the first 6 rows of Pascal’s Triangle.
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Method 1 ( O(n^3) time complexity )
Number of entries in every line is equal to line number. For example, the first line has “1″, the second line has “1 1″, the third line has “1 2 1″,.. and so on. Every entry in a line is value of a
Binomial Coefficient. The value of ith entry in line number line is C(line, i). The value can be calculated using following formula.
C(line, i)   = line! / ( (line-i)! * i! )
A simple method is to run two loops and calculate the value of Binomial Coefficient in inner loop.
 // A simple O(n^3) program for Pascal’s Triangle #include int binomialCoeff(int n, int k); // Function to print first n lines of Pascal’s Triangle void printPascal(int n) {   // Iterate through every line and print entries in it   for (int line = 1; line < n; line++)   {     // Every line has number of integers equal to line number     for (int i = 1; i <= line; i++)       printf(“%d “, binomialCoeff(line, i));     printf(“\n”);   } } int binomialCoeff(int n, int k) {     int res = 1;     if (k > n – k)        k = n – k;     for (int i = 0; i < k; ++i)     {         res *= (n – i);         res /= (i + 1);     }     return res; } // Driver program to test above function int main() {   int n = 7;   printPascal(n);   return 0; }
Time complexity of this method is O(n^3). Following are optimized methods.

Method 2( O(n^2) time and O(n^2) extra space )
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So we can create a 2D array that stores previously generated values. To generate a value in a line, we can use the previously stored values from array.

 // A O(n^2) time and O(n^2) extra space method for Pascal’s Triangle void printPascal(int n) {   int arr[n][n]; // An auxiliary array to store generated pscal triangle values   // Iterate through every line and print integer(s) in it   for (int line = 0; line < n; line++)   {     // Every line has number of integers equal to line number     for (int i = 0; i <= line; i++)     {       // First and last values in every row are 1       if (line == i || i == 0)            arr[line][i] = 1;       else // Other values are sum of values just above and left of above            arr[line][i] = arr[line-1][i-1] + arr[line-1][i];       printf(“%d “, arr[line][i]);     }     printf(“\n”);   } }
This method can be optimized to use O(n) extra space as we need values only from previous row. So we can create an auxiliary array of size n and overwrite values. Following is another method uses only O(1) extra space.

Method 3 ( O(n^2) time and O(1) extra space )
This method is based on method 1. We know that
ith entry in a line number line is Binomial CoefficientC(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1). It can be calculated in O(1) time using the following.

C(line, i)   = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line-i + 1)! * (i-1)! )
We can derive following expression from above two expressions.
C(line, i) = C(line, i-1) * (line – i) / i
So C(line, i) can be calculated from C(line, i-1) in O(1) time
 // A O(n^2) time and O(1) extra space function for Pascal’s Triangle void printPascal(int n) {   for (int line = 1; line <= n; line++)   {     int C = 1;  // used to represent C(line, i)     for (int i = 1; i <= line; i++)      {       printf(“%d “, C);  // The first value in a line is always 1       C = C * (line – i) / i;  // C(line, i) = C(line, i-1) * (line – i) / i     }     printf(“\n”);   } }
So method 3 is the best method among all, but it may cause integer overflow for large values of n as it multiplies two integers to obtain values.

## Program: Next higher number with same number of set bits

Given a number x, find next number with same number of 1 bits in it’s binary representation.
For example, consider x = 12, whose binary representation is 1100 (excluding leading zeros on 32 bit machine). It contains two logic 1 bits. The next higher number with two logic 1 bits is 17 (100012). Algorithm:
When we observe the binary sequence from 0 to 2n – 1 (n is # of bits), right most bits (least significant) vary rapidly than left most bits. The idea is to find right most string of 1′s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position. An example makes it more clear,
x = 156
10
x = 10011100
(2)
10011100
00011100 – right most string of 1’s in x
00000011 – right shifted pattern except left most bit ——> [A]
00010000 – isolated left most bit of right most 1’s pattern
00100000 – shiftleft-ed the isolated bit by one position ——> [B]
10000000 – left part of x, excluding right most 1’s pattern ——> [C]
10100000 – add B and C (OR operation) ——> [D]
10100011 – add A and D which is required number 163
(10)
After practicing with few examples, it easy to understand. Use the below given program for generating more sets.
Program Design:
We need to note few facts of binary numbers. The expression x & -x will isolate right most set bit in x (ensuring x will use 2′s complement form for negative numbers). If we add the result to x, right most string of 1′s in x will be reset, and the immediate ’0′ left to this pattern of 1′s will be set, which is part [B] of above explanation. For example if x = 156, x & -x will result in 00000100, adding this result to x yields 10100000 (see part D). We left with the right shifting part of pattern of 1′s (part A of above explanation).
There are different ways to achieve part A. Right shifting is essentially a division operation. What should be our divisor? Clearly, it should be multiple of 2 (avoids 0.5 error in right shifting), and it should shift the right most 1′s pattern to right extreme. The expression (x & -x) will serve the purpose of divisor. An EX-OR operation between the number X and expression which is used to reset right most bits, will isolate the rightmost 1′s pattern.
A Correction Factor:
Note that we are adding right most set bit to the bit pattern. The addition operation causes a shift in the bit positions. The weight of binary system is 2, one shift causes an increase by a factor of 2. Since the increased number (rightOnesPattern in the code) being used twice, the error propagates twice. The error needs to be corrected. A right shift by 2 positions will correct the result.
The popular name for this program is same number of one bits.
 #include using namespace std; typedef unsigned int uint_t; // this function returns next higher number with same number of set bits as x. uint_t snoob(uint_t x) {   uint_t rightOne;   uint_t nextHigherOneBit;   uint_t rightOnesPattern;   uint_t next = 0;   if(x)   {     // right most set bit     rightOne = x & -(signed)x;     // reset the pattern and set next higher bit     // left part of x will be here     nextHigherOneBit = x + rightOne;     // nextHigherOneBit is now part [D] of the above explanation.     // isolate the pattern     rightOnesPattern = x ^ nextHigherOneBit;     // right adjust pattern     rightOnesPattern = (rightOnesPattern)/rightOne;     // correction factor     rightOnesPattern >>= 2;     // rightOnesPattern is now part [A] of the above explanation.     // integrate new pattern (Add [D] and [A])     next = nextHigherOneBit | rightOnesPattern;   }   return next; } int main() {   int x = 156;   cout<<“Next higher number with same number of set bits is “<

## Program: Lowest Common Ancestor in a Binary Search Tree

Given the values of two nodes in a *binary search tree*, write a c program to find the lowest common ancestor. You may assume that both values already exist in the tree.

The function prototype is as follows:

` int FindLowestCommonAncestor(node* root, int value1, int value)`
`  I/P : 4 and 14`
`  O/P : 8`
`  (Here the common ancestors of 4 and 14, are {8,20}.`
`  Of {8,20}, the lowest one is 8).`

Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it’s value is greater than both n1 and n2 then our LCA lies on left side of the node, if it’s value is smaller than both n1 and n2 then LCA lies on right side.
Implementation:
 `#include ` `#include ` `/* A binary tree node has data, pointer to left child` `   and a pointer to right child */` `struct` `node` `{` `    int` `data;` `    struct` `node* left;` `    struct` `node* right;` `};` `struct` `node* newNode(int` `);` `/* Function to find least comman ancestor of n1 and n2 */` `int` `leastCommanAncestor(struct` `node* root, int` `n1, int` `n2)` `{` `  /* If we have reached a leaf node then LCA doesn't exist ` `     If root->data is equal to any of the inputs then input is ` `     not valid. For example 20, 22 in the given figure */`  `  if(root == NULL || root->data == n1 || root->data == n2)` `    return` `-1; ` `  `  `  /* If any of the input nodes is child of the current node` `     we have reached the LCA. For example, in the above figure` `     if we want to calculate LCA of 12 and 14, recursion should ` `     terminate when we reach 8*/` `  if((root->right != NULL) && ` `    (root->right->data == n1 || root->right->data == n2))` `    return` `root->data;` `  if((root->left != NULL) && ` `    (root->left->data == n1 || root->left->data == n2))` `    return` `root->data;    ` `    `  `  if(root->data > n1 && root->data < n2)` `    return` `root->data;` `  if(root->data > n1 && root->data > n2)` `    return` `leastCommanAncestor(root->left, n1, n2);` `  if(root->data < n1 && root->data < n2)` `    return` `leastCommanAncestor(root->right, n1, n2);` `}    ` `/* Helper function that allocates a new node with the` `   given data and NULL left and right pointers. */` `struct` `node* newNode(int` `data)` `{` `  struct` `node* node = (struct` `node*)` `                       malloc(sizeof(struct` `node));` `  node->data  = data;` `  node->left  = NULL;` `  node->right = NULL;` `  return(node);` `}` `/* Driver program to test mirror() */` `int` `main()` `{` `  struct` `node *root  = newNode(2);` `  root->left         = newNode(1);` `  root->right        = newNode(4);` `  root->right->left  = newNode(3);` `  root->right->right = newNode(5); ` `/* Constructed binary search tree is` `            2` `           / \` `         1   4` `             / \` `           3   5` `*/` `  printf("\n The Least Common Ancestor is \n");` `  printf("%d", leastCommanAncestor(root, 3, 5));` `  getchar();` `  return` `0;` `}`
Note that above function assumes that n1 is smaller than n2.
Time complexity: Time complexity is O(Logn) for a balanced BST and O(n) for a skewed BST.

Please Leave comment if you have doubts. Give ur solution thru comments.

Concat me through mail id: poratltechinfo@gmail.com

## Programs: Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).
Example:
Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3
Output:  3->2->1->6->5->4->8->7->NULL.
Inputs:   1->2->3->4->5->6->7->80->NULL and k = 5
Output:  5->4->3->2->1->8->7->6->NULL.

1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be
next and pointer to the previous node be prev. See this post for reversing a linked list.
2)
head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return
prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */
Please Leave comment if you have doubts. Give ur solution thru comments.

Concat me through mail id: poratltechinfo@gmail.com

## Print a given matrix in spiral form

Given a 2D array, print it in spiral form. See the following examples.
Input:
1    2   3   4
5    6   7   8
9   10  11  12
13  14  15  16
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Input:
1   2   3   4  5   6
7   8   9  10  11  12
13  14  15 16  17  18
Output:
1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
Solution:
 #include #define R 3 #define C 6 void spiralPrint(int m, int n, int a[R][C]) {     int i, k = 0, l = 0;     /*  k – starting row index         m – ending row index         l – starting column index         n – ending column index         i – iterator     */     while (k < m && l < n)     {         /* Print the first row from the remaining rows */         for (i = l; i < n; ++i)         {             printf(“%d “, a[k][i]);         }         k++;         /* Print the last column from the remaining columns */         for (i = k; i < m; ++i)         {             printf(“%d “, a[i][n-1]);         }         n–;         /* Print the last row from the remaining rows */         if ( k < m)         {             for (i = n-1; i >= l; –i)             {                 printf(“%d “, a[m-1][i]);             }             m–;         }         /* Print the first column from the remaining columns */         if (l < n)         {             for (i = m-1; i >= k; –i)             {                 printf(“%d “, a[i][l]);             }             l++;            }            } } /* Driver program to test above functions */ int main() {     int a[R][C] = { {1,  2,  3,  4,  5,  6},         {7,  8,  9,  10, 11, 12},         {13, 14, 15, 16, 17, 18}     };     spiralPrint(R, C, a);     return 0; } /* OUTPUT:   1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 */ Please Leave comment if you have doubts. Give ur solution thru comments.