Code Zone: Revise

Showing posts with label Revise. Show all posts

Thursday, January 12, 2012

Binary heap

http://quiz.geeksforgeeks.org/binary-heap/
http://quiz.geeksforgeeks.org/heap-sort/
http://www.geeksforgeeks.org/applications-of-heap-data-structure/
http://www.geeksforgeeks.org/heap/
http://www.geeksforgeeks.org/why-is-binary-heap-preferred-over-bst-for-priority-queue/
http://www.geeksforgeeks.org/g-fact-85/

Check if a given Binary Tree is Heap
Given a binary tree we need to check it has heap property or not, Binary tree need to fulfill following two conditions for being a heap –
It should be a complete tree (i.e. all levels except last should be full).
Every node’s value should be greater than or equal to its child node (considering max-heap).

http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-heap/

Check if a given array represents a Binary Heap
http://www.geeksforgeeks.org/how-to-check-if-a-given-array-represents-a-binary-heap/

Convert min Heap to max Heap
http://www.geeksforgeeks.org/convert-min-heap-to-max-heap/

Heap Operations

1.Heapify
2 Insertion
3.Deletion
4.Heapsort

1. Building a heap:
Lets take an array with the following elements:
4 1 3 2 16 9 10 14 8 7
Note:-------------------------
Parent( i ) return ⌊i/2⌋
Left( i ) return 2i
Right( i ) return 2i + 1

Build-Max-Heap (A)
1	A.heap-size ← A.length
	/@ loop-invariant \forall int j; i < j ≤ A.length; A[ j ] ≥ A[Left( j )] && A[ j ] ≥ A[Right( j )] @/
2	for i ← ⌊ A.length/2 ⌋ downto 1 do
3	Max-Heapify (A, i)

Max-Heapify (A, i)
1	l ← Left (i)
2	r ← Right (i)
3	if l ≤ A.heap-size and A[l] > A[i]
4	then largest ← l
5	else largest ← i
6	if r ≤ A.heap-size and A[r] > A[largest]
7	then largest ← r
8	if largest ≠ i then
9	exchange A[i] ↔ A[largest]
10	Max-Heapify (A, largest)

A.length = 10
i starts at 5, the last parent in the array: always at ⌊ n/2 ⌋
Max-Heapify is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.
Note that Max-Heapify is run on each node that is a parent:starts with the last parent in the array: always at ⌊n/2⌋

Note:Max-Heapify(A, largest) is called as after swapping the new largest may not be heapified
e.g. After swapping 16 and 1 1 becomes new largest and 7 is greater than 1 in that tree.So heapify needs to be called on 1 to take 7 into its proper position.
Visualisation:

The number of times through the loop is ⌊n/2⌋ or O(n)
Max-Heapify T(n) = Θ(lg n)
Build-Max-Heap T(n) = O(n lg n)

Useful Link:
http://homepages.ius.edu/rwisman/C455/html/notes/Chapter6/BldHeap.htm

Insert a node into a heap:
To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle up, heapify-up, or cascade-up), by following this algorithm:

Add the element to the bottom level of the heap or to the end of the array.
Compare the added element with its parent; if they are in the correct order, stop.
If not, swap the element with its parent and return to the previous step.

Suppose we have a heap as follows

Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot available at the lowest level of the tree. This is to ensure that the tree remains complete.

Now we do the same thing again, comparing the new node to its parent. Since 14 < 15, we have to do another swap:

Now we are done, because 15

20.

Useful Link:
http://en.wikipedia.org/wiki/Binary_heap
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm
3.Heap Sort:
The heap sort combines the best of both merge sort and insertion sort. Like merge sort, the worst case time of heap sort is O(n log n) and like insertion sort, heap sort sorts in-place. The heap sort algorithm starts by using procedure BUILD-HEAP to build a heap on the input array A[1 . . n]. Since the maximum element of the array stored at the root A[1], it can be put into its correct final position by exchanging it with A[n] (the last element in A). If we now discard node n from the heap than the remaining elements can be made into heap. Note that the new element at the root may violate the heap property. All that is needed to restore the heap property.

HEAPSORT (A)

BUILD_HEAP (A)

for i ← length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)

Code:

void heapSort(int numbers[], int array_size)
{
  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1);
  }
}


void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 <= bottom) && (!done))
  {
    if (root*2 == bottom)
      maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}

Useful Link:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm
http://www.algorithmist.com/index.php/Heap_sort.c

Deletion in a heap:[ Follows the same sift_down method as in heapsort
The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap (also known as bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down and extract-min/max).

Replace the root of the heap with the last element on the last level.
Compare the new root with its children; if they are in the correct order, stop.
If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)

Useful Link:
http://en.wikipedia.org/wiki/Binary_heap
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Tuesday, December 20, 2011

Binary Search

Describe the Binary Search approach and optimize it.

http://quiz.geeksforgeeks.org/binary-search/
http://www.geeksforgeeks.org/the-ubiquitous-binary-search-set-1/
http://www.geeksforgeeks.org/problem-binary-search-implementations/

Typical Problems:
Question 1:
Suppose you have a sorted array of infinite numbers, how would you search an element in the array?
http://www.geeksforgeeks.org/find-position-element-sorted-array-infinite-numbers/

Question 2:
http://www.programcreek.com/2013/01/leetcode-search-insert-position/

Question 3:Guess Number is higher or lower
http://www.programcreek.com/2014/07/leetcode-guess-number-higher-or-lower-java/

Question 4:First Bad Version
http://www.programcreek.com/2014/05/leetcode-first-bad-version-java/

Dynamic Programming

What is Dynamic Programming and how we can use it to solve sub-problems

Theory:
http://video.mit.edu/watch/introduction-to-algorithms-lecture-19-dynamic-programming-i-fibonacci-shortest-paths-14225/
https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
Overlapping Sub-problems/ Optimal Substructure:
http://www.geeksforgeeks.org/archives/12635:
http://www.geeksforgeeks.org/archives/12819
Bottom Up:
https://www.interviewcake.com/concept/java/bottom-up

DP in Java
http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/
http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_01_-_Introduction.jsp
http://algorithms.tutorialhorizon.com/category/dynamic-programming/

Problems in Difficulty Order - Leetcode:
https://leetcode.com/tag/dynamic-programming/
Easy
1.Climbing Stairs: http:sudhansu-codezone.blogspot.in/2011/12/fibonacci-series.html
2. http://www.programcreek.com/2014/02/leetcode-best-time-to-buy-and-sell-stock-java/
3. http://www.programcreek.com/2014/03/leetcode-house-robber-java/
4. http://www.programcreek.com/2014/05/leetcode-pain-fence-java/
5. http://www.programcreek.com/2014/04/leetcode-range-sum-query-2d-immutable-java/

Medium
1.

Problems - 1D
http://www.programcreek.com/2013/02/leetcode-maximum-subarray-java/
http://www.programcreek.com/2014/04/leetcode-longest-increasing-subsequence-java/
http://www.programcreek.com/2014/06/leetcode-decode-ways-java/

Problems List

0. http://www.ideserve.co.in/#dynamicProgramming

1. http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

2. http://algorithms.tutorialhorizon.com/category/dynamic-programming/

3. http://www.geeksforgeeks.org/fundamentals-of-algorithms/#DynamicProgramming

4. http://codercareer.blogspot.in/p/dynamic-interview-questions.html

5. https://www.quora.com/What-are-the-top-10-most-popular-dynamic-programming-problems-among-interviewers

6. https://people.cs.clemson.edu/~bcdean/dp_practice/

7. http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_02_-_No_of_ways_to_climb_stairs.jsp

Saturday, December 17, 2011

Stack with 2 Queues and Queue with 2 Stacks

Stack using 2 Queues.

http://www.geeksforgeeks.org/implement-stack-using-queue/

Strategy:

Version A:

push:
- enqueue in queue1
pop:
- while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
- dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Version B:

push:
- enqueue in queue2
- enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
pop:

deqeue from queue1

Queue using 2 STACKS.

Strategy:
A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x)
  1) While stack1 is not empty, push everything from satck1 to stack2.
  2) Push x to stack1 (assuming size of stacks is unlimited).
  3) Push everything back to stack1.

dnQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it

Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q,  x)
  1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
  1) If both stacks are empty then error.
  2) If stack2 is empty
       While stack1 is not empty, push everything from satck1 to stack2.
  3) Pop the element from stack2 and return it.

Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.

Code:Using Method 2
#include<stdio.h>
#include<stdlib.h>

struct sNode
{
   int data;
   struct sNode *next;
};

struct queue
{
   struct sNode *stack1;
   struct sNode *stack2;
};

void push(struct sNode** top_ref, int new_data)
{
struct sNode* new_node =
            (struct sNode*) malloc(sizeof(struct sNode));

if(new_node == NULL)
{
     printf("Stack overflow \n");
     getchar();
     exit(0);
}

new_node->data = new_data;

new_node->next = (*top_ref);

(*top_ref)    = new_node;
}

int pop(struct sNode** top_ref)
{
int res;
struct sNode *top;

if(*top_ref == NULL)
{
     printf("Stack overflow \n");
     getchar();
     exit(0);
}
else
{
     top = *top_ref;
     res = top->data;
     *top_ref = top->next;
     free(top);
     return res;
}
}

void enQueue(struct queue *q, int x)
{
   push(&q->stack1, x);
}

int deQueue(struct queue *q)
{
   int x;

   /* If both stacks are empty then error */
   if(q->stack1 == NULL && q->stack2 == NULL)
   {
      printf("Q is empty");
      getchar();
      exit(0);
   }

   /* Move elements from stack1 to stack 2 only if
       stack2 is empty */
   if(q->stack2 == NULL)
   {
     while(q->stack1 != NULL)
     {
        x = pop(&q->stack1);
        push(&q->stack2, x);
     }
   }

   x = pop(&q->stack2);
   return x;
}

int main()
{
   struct queue *q = (struct queue*)malloc(sizeof(struct queue));
   q->stack1 = NULL;
   q->stack2 = NULL;
   enQueue(q, 1);
   enQueue(q, 2);
   enQueue(q, 3);

   printf("%d ", deQueue(q));
   printf("%d ", deQueue(q));
   printf("%d ", deQueue(q));

   getchar();
   return 0;
}

Queue using a single stack

Strategy:

Queue can be implemented using one user stack and one Function Call Stack.i.e using recursion

enQueue(x)
  1) Push x to stack1.

deQueue:
  1) If stack1 is empty then error.
  2) If stack1 has only one element then return it.
  3) Recursively pop everything from the stack1, store the popped item
    in a variable res,  push the res back to stack1 and return res

The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in dequeue() and all other items are pushed back in step 3.

Code:
#include<stdio.h>
#include<stdlib.h>

struct sNode
{
   int data;
   struct sNode *next;
};

struct queue
{
struct sNode *stack1;
};

void push(struct sNode** top_ref, int new_data)
{
struct sNode* new_node =
            (struct sNode*) malloc(sizeof(struct sNode));

if(new_node == NULL)
{
     printf("Stack overflow \n");
     getchar();
     exit(0);
}

new_node->data = new_data;

new_node->next = (*top_ref);

(*top_ref)    = new_node;
}

int pop(struct sNode** top_ref)
{
int res;
struct sNode *top;

if(*top_ref == NULL)
{
     printf("Stack overflow \n");
     getchar();
     exit(0);
}
else
{
     top = *top_ref;
     res = top->data;
     *top_ref = top->next;
     free(top);
     return res;
}
}

void enQueue(struct queue *q, int x)
{
push(&q->stack1, x);
}

int deQueue(struct queue *q)
{
   int x, res;

   /* If both stacks are empty then error */
   if(q->stack1 == NULL)
   {
     printf("Q is empty");
     getchar();
     exit(0);
   }
   else if(q->stack1->next == NULL)
   {
      return pop(&q->stack1);
   }
   else
   {

      x = pop(&q->stack1);

      res = deQueue(q);

      push(&q->stack1, x);

      return res;
   }
}

int main()
{
struct queue *q = (struct queue*)malloc(sizeof(struct queue));
q->stack1 = NULL;

enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);

printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));

getchar();
}

Two stacks in a single array

Create a data structure twoStacks that represents two stacks. Implementation of twoStacks should use only one array, i.e., both stacks should use the same array for storing elements. Following functions must be supported by twoStacks.

push1(int x) –> pushes x to first stack
push2(int x) –> pushes x to second stack

pop1() –> pops an element from first stack and return the popped element
pop2() –> pops an element from second stack and return the popped element

Implementation of twoStack should be space efficient.

http://www.geeksforgeeks.org/implement-two-stacks-in-an-array/

Stack & Queue Problems

0.Simplify Path
http://www.programcreek.com/2014/04/leetcode-simplify-path-java/

1.Sliding Window Maximum
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Examples:
Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6
C++ Implementation:
http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
http://articles.leetcode.com/sliding-window-maximum/
Java Implementation:

http://www.programcreek.com/2014/05/leetcode-sliding-window-maximum-java/

2.Moving Average from Data Stream in a sliding window

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

http://www.programcreek.com/2014/05/leetcode-moving-average-from-data-stream-java/

Moving Average from Data stream:

Given a stream of numbers, print average (or mean) of the stream at every point. For example, let us consider the stream as 10, 20, 30, 40, 50, 60, …

Average of 1 numbers is 10.00
  Average of 2 numbers is 15.00
  Average of 3 numbers is 20.00
  Average of 4 numbers is 25.00
  Average of 5 numbers is 30.00
  Average of 6 numbers is 35.00
  ..................

Strategy:

To print mean of a stream, we need to find out how to find average when a new

number is being added to the stream. To do this, all we need is count of numbers

seen so far in the stream, previous average and new number. Let n be the count,

prev_avg be the previous average and x be the new number being added.

The average after including x number can be written as (prev_avg*n + x)/(n+1).

Code:

#include <stdio.h>
 
// Returns the new average after including x
float getAvg(float prev_avg, int x, int n)
{
    return (prev_avg*n + x)/(n+1);
}
 
// Prints average of a stream of numbers
void streamAvg(float arr[], int n)
{
   float avg = 0;
   for(int i = 0; i < n; i++)
   {
       avg  = getAvg(avg, arr[i], i);
       printf("Average of %d numbers is %f \n", i+1, avg);
   }
   return;
}

int main()
{
    float arr[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    streamAvg(arr, n);
    getchar();
    return 0;
}

The above function getAvg() can be optimized using following changes. We
can avoid the use of prev_avg and number of elements by using static 
variables (Assuming that only this function is called for average of 
stream). Following is the oprimnized version.

Revised Code:

#include <stdio.h>
 
// Returns the new average after including x
float getAvg (int x)
{
    static int sum, n;
 
    sum += x;
    return (((float)sum)/++n);
}
 
// Prints average of a stream of numbers
void streamAvg(float arr[], int n)
{
   float avg = 0;
   for(int i = 0; i < n; i++)
   {
       avg  = getAvg(arr[i]);
       printf("Average of %d numbers is %f \n", i+1, avg);
   }
   return;
}

int main()
{
    float arr[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    streamAvg(arr, n);
    getchar();
    return 0;
}

3. Next higher element for each element in an array.
For e.g. if array is 1 2 3 4 5 8 6
o/p should be
(element) (next higher element)
1 2
2 3
3 4
4 5
5 8
8 nothing
6 nothing

Or
You are given an unsorted array A of n elements, now construct an array B for which B[i] = A[j] where j is the least number such that A[j] > A[i] and j>i if such a j does not exist B[i] = -1 Eg:

A={1,3,5,7,6,4,8}
B = {3 5 7 8 8 8 -1}

Approach:

While iterating over the array if the element is smaller than stack top, push it to stack along with index.if the element is larger than stack top, pop till current element is smaller than stack top and for all the popped indices store the current element.
Code:

#include<stdio.h>
#include<stdlib.h>
#define STACKSIZE 100

struct stack
{
int top;
int items[STACKSIZE];
};

void push(struct stack *ps, int x)
{
if (ps->top == STACKSIZE-1)
{
printf("Error: stack overflow\n");
getchar();
exit(0);
}
else
{
ps->top += 1;
ps->items[ps->top] = x;
}
}

bool isEmpty(struct stack *ps)
{
return (ps->top == -1)? true : false;
}

int pop(struct stack *ps)
{
int temp;
if (ps->top == -1)
{
printf("Error: stack underflow \n");
getchar();
exit(0);
}
else
{
temp = ps->items[ps->top];
ps->top -= 1;
return temp;
}
}

void printNGE(int arr[], int n)
{
int i = 0;
struct stack s;
s.top = -1;
int element, next;

push(&s, arr[0]);

for (i=1; i<n; i++)
{
next = arr[i];

if (isEmpty(&s) == false)
{
element = pop(&s);

while (element < next)
{
printf("\n %d --> %d", element, next);
if(isEmpty(&s) == true)
break;
element = pop(&s);
}
if (element > next)
push(&s, element);
}
push(&s, next);
}

while(isEmpty(&s) == false)
{
element = pop(&s);
next = -1;
printf("\n %d --> %d", element, next);
}
}

int main()
{
int arr[]= {11, 13, 21, 3};
int n = sizeof(arr)/sizeof(arr[0]);
printNGE(arr, n);
getchar();
return 0;
}
Time Complexity:O(n)
Simple Code in Java [ Easy to understand ]

public class Test {

    public static void upateArray(int[] a){
        Stack<Integer> stack = new Stack<Integer>();
        int len = a.length;
        int cur = 0;
        while(cur < len){
            while(!stack.isEmpty() && a[stack.peek()] < a[cur]){
                a[stack.pop()] = a[cur];
            }
            stack.push(cur);
            cur++;
        }
    }

    public static void main (String args[]){
        int a[] = {3,2,5,11,4,11,13,8,6,20,10};
        upateArray(a);
        for(int i : a)
            System.out.print(" "+i);
    }
}

Source:

http://stackoverflow.com/questions/5007941/next-larger-number-in-an-array

Method 2:

Make an empty array called c[].
Start at the end of a[] and work backwards.
Do a binary search in c[] for the first value greater than a[i]. Put that into b[i], or a -1 if you can't find one.
Drop everything in c[] that is less than b[i].
Append a[i] to the beginning of c[].
c[] will always be sorted, allowing binary search.

For example, with the sample A={1,3,5,7,6,4,8}
Start at the end, A[i]=8, C={}
First iteration is a bit weird.
Binary search of C for the first value greater than 8 gives nothing, so B[i] = -1
You don't have to drop anything from C because it is empty, but you would have had to empty it anyway because of the -1.
Append A[i]=8 to the beginning of C, so C={8}
Now A[i]=4, C={8}
Binary search of C for the first value greater than 4 gives 8, so B[i]=8
Drop everything less than 8 from C, which still leaves C={8}
Append A[i]=4 to the beginning of C, so C={4,8}
Now A[i]=6, C={4,8}
Binary search of C for the first value greater than 6 gives 8, so B[i]=8
Drop everything less than 8 from C, which leaves C={8}
Append A[i]=6 to the beginning of C, so C={6,8}
Now A[i]=7, C={6,8}
Binary search of C for the first value greater than 7 gives 8, so B[i]=8
Drop everything less than 8 from C, which leaves C={8}
Append A[i]=7 to the beginning of C, so C={7,8}
Now A[i]=5, C={7,8}
Binary search of C for the first value greater than 5 gives 7, so B[i]=7
Drop everything less than 7 from C, which leaves C={7,8}
Append A[i]=5 to the beginning of C, so C={5,7,8}
Now A[i]=3, C={5,7,8}
Binary search of C for the first value greater than 3 gives 5, so B[i]=5
Drop everything less than 5 from C, which leaves C={5,7,8}
Append A[i]=3 to the beginning of C, so C={3,5,7,8}
Now A[i]=1, C={3,5,7,8}
Binary search of C for the first value greater than 1 gives 3, so B[i]=3
Done

Wednesday, December 14, 2011

Queue Implementation

Queue:
Implement a queue[ Add( ) and Delete( )] operations using

1.Circular Array
2.Singly Linked Lists and TWO POINTERS
3.Circular Linked List and SINGLE POINTER

Deque:
Implement the following Deque operations using i)Linked List ii)Stacks

1.Enqueue ( )
2.Dequeue ( )

Priority Queue using LINKED LIST .Discuss advantage of Priority Queue.

http://quiz.geeksforgeeks.org/priority-queue-set-1-introduction/
http://www.geeksforgeeks.org/why-is-binary-heap-preferred-over-bst-for-priority-queue/

void INSERT_QUEUE_TWO(struct node *&front, struct node *&rear,int data)
{struct node *tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=NULL;

if(front==NULL)
    front=tmp;
else
    rear->link=tmp;//LAST NODE POINTS TO TMP
rear=tmp;//REAR ALSO POINTS TO TMP
}

void INSERT_QUEUE_SINGLE(struct node *&rear,int data)
//INSERTION is at the beginning of a CIRCULAR LL
{struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;

if(rear==NULL)
    {rear=tmp;
    tmp->link=rear;}
else
    {tmp->link=rear->link;
    rear->link=tmp;
    rear=tmp;}
}

void DELETE_QUEUE_TWO(struct node *&front,struct node *&rear,int data)
{struct node *tmp;
if (front==NULL)
    printf("Queue UNDEFLOW");
else
    {tmp=front;//Delete From Front
    front=front->link;
    free(tmp);}
}

void DELETE_QUEUE_SINGLE(struct node *&rear)
{struct node *tmp,*q;
if (rear==NULL)
    {printf("Queue UNDEFLOW");
    return;}

if(rear->link==rear)//ONLY ONE ELEMENT
    {tmp=rear;
    rear=NULL;
    free(tmp);
    return;}

tmp=rear->link;
rear->link=tmp->link;
free(tmp);
}

Stack Operations

Implement a STACK using a singly LINKED LIST

Push()-Adding elemnt at start of linked list
Pop()-Deleting element at start of the List

Track the Maximum Element in a Stack:
In a Stack, keep track of maximum value in it. It might be the top element in the stack but once it is poped out, the maximum value should be from the rest of the elements in the stack.
http://algorithms.tutorialhorizon.com/track-the-maximum-element-in-a-stack/

Sort a Stack:
Given a stack S, write a C program to sort the stack (in the ascending
order).
We are not allowed to make any assumptions about how the stack is implemented.
The only functions to be used are:
Push Pop Top IsEmpty IsFull
Concept:
Use a temp variable to store the popped item in each recursive traversal.Then go on popping the stack until stack is empty and go on pushing the item in the recursion thereafter.O(n) stack space is used in this process.
Pseudo Code:

void recursive(Stack s)
{
if(s.isEmpty == true)
return ;
elem temp = s.pop();
recursive(s);
recur_push(temp, s);
return;
}
recur_push(elem t, stack s)
{
if(s.isEmpty == null || s.top() > t)
{
s.push(t);
return;
}
temp1= s.pop()
recur_push(t,s);
s.push(temp1);
}

Alternative:

We can use another stack to do the sorting. Suppose s1 is the original stack and s2 is the other stack. The algorithm will look like this,

- Pop from s1(e1) and peek s2(e2).
- if e2 < e1, then push e1 on s2,
- if e2 > e1, then keep popping from s2 into s1 till the next element is less than e1 and then push e1 on s2.

Keep doing it till s1 is empty. Now, s2 will be sorted in ascending order! This algorithm will have a time complexity of O(N^2).

Sunday, December 11, 2011

Sorting Algorithms

Exchange Sorts: Bubble,Quick,Odd-even

Selection: Selection,Heap,Tournament

Insertion: Insertion,Shell,Tree,Patience

Merge: Merge

Distribution: Bucket,Counting,Radix

Useful Links:
http://en.wikipedia.org/wiki/Sorting_algorithm
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/sortingIntro.htm

BST Operations: Insert, Search, Delete - Recursive and Iterative

Write functions in C for following BST operations

1. Search-both iterative and recursive

2. INSERT_BST- both iterative & recursive

3. DELETE_BST

Recursive:

http://quiz.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
http://quiz.geeksforgeeks.org/binary-search-tree-set-2-delete/
http://quiz.geeksforgeeks.org/data-structure/binary-search-trees/

Iterative:

void Search_BST_Iterative(int item,struct node *root,struct node *&par,struct node *&loc)
{
struct node *ptr,*ptrsave;
       if(root==NULL) //Tree EMPTY
         { loc=NULL;
            par=NULL;
            return;
         }
       if(item==root->data) //Item is at root
         { loc=root;
            par=NULL;
            return;
         }
       //Initialise ptr & ptrsave

         if(item<root->data)
                 ptr=root->left;
         else
                 ptr=root->right;
         ptrsave=root;

         while(ptr!=NULL)
         {
            if(item==ptr->data)
              {   loc=ptr;
                  par=ptrsave;
                   return;
              }
            ptrsave=ptr;
            if(item<ptr->data)
                ptr=ptr->left;
            else
                ptr=ptr->right;
         }
loc=NULL; //ITEM NOT FOUND
par=ptrsave;
}

Insert_BST_Iterative:

void INSERT_BST_Iterative(struct node *&root,int item)
{struct node *tmp,*parent,*location;
tmp=(struct node*)malloc(sizeof(struct node));
tmp->data=item;
tmp->left=NULL;
tmp->right=NULL;
Search_BST_Iterative(item,root,parent,location);
if(location!=NULL)
    {printf("Data already present");
    return;
    }
if(parent==NULL)
    root=tmp;
else
    if(item<parent->data)
        parent->left=tmp;
    else
        parent->right=tmp;
}

Runtimes:

Both the BST search and insert algorithms share the same running time: log₂ n in the best case, and linear in the worst case. The insert algorithm's running time mimics the search's because it essentially uses the same tactics used by the search algorithm to find the location for the newly inserted node.

While binary search trees ideally exhibit sub-linear running times for insertions, searches, and deletions, the running time is dependent upon the BST's topology. The topology, as we discussed in the Inserting Nodes into a BST section, is dependent upon the order with which the data is added to the BST. Data being entered that is ordered or near-ordered will cause the BST's topology to resemble a long, thin tree, rather than a short, wide one. In many real-world scenarios, data is naturally in an ordered or near-ordered state.

The problem with BSTs is that they can become easily unbalanced. A balanced binary tree is one that exhibits a good ratio of breadth to depth. As we will examine in the next part of this article series, there are a special class of BSTs that are self-balancing. That is, as new nodes are added or existing nodes are deleted, these BSTs automatically adjust their topology to maintain an optimal balance. With an ideal balance, the running time for insertion, searches, and deletion, even in the worst case, is log₂ n.

Delete BST Iterative:

void case_a(struct node *&root,struct node *par,struct node *loc)
{    if(par==NULL)
        root=NULL;
    else
        if(loc==par->left)
            par->left=NULL;
        else
            par->right=NULL;
}

void case_b(struct node *&root,struct node *par,struct node *loc)
{struct node *child;
//Initialaise CHILD
if(loc->left!=NULL)
    child=loc->left;
else
    child=loc->right;
if(par==NULL)
    root=child;
else
    if(loc==par->left)
        par->left=child;
    else
        par->right=child;
}

void case_c(struct node *&root,struct node *&par,struct node *&loc)
{
     struct node *ptr,*ptrsave,*suc,*parsuc;
     ptrsave=loc;
     ptr=loc->right;
    while(ptr->left!=NULL)
    {    ptrsave=ptr;
        ptr=ptr->left;
    }
suc=ptr;
parsuc=ptrsave;

if(suc->left==NULL && suc->right==NULL)
                   case_a(root,parsuc,suc);
else
                   case_b(root,parsuc,suc);

if(par==NULL)
    root=suc;
else
    if(loc==par->left)
        par->left=suc;
    else
        par->right=suc;

    suc->left=loc->left;
    suc->right=loc->right;
}

void DELETE_BST_Iterative(struct node *& root,int data)
{struct node *parent,*location;
if(root==NULL)
{printf("Tree Empty");
return;}Search_BST_Iterative(data,root,parent,location);
if(location==NULL)
{printf("DATA Not Present in Tree");
return;}

if(location->left==NULL && location->right==NULL)
    case_a(root,parent,location);
if(location->left!=NULL && location->right==NULL)
    case_b(root,parent,location);
if(location->left==NULL && location->right!=NULL)
    case_b(root,parent,location);
if(location->left!=NULL && location->right!=NULL)
    case_c(root,parent,location);
free(location);
}

Useful Links on BST:
Java Version:
http://algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/

http://msdn.microsoft.com/en-us/library/aa289150(v=vs.71).aspx

Labels