life ideas

November 12, 2007

Algorithm

Filed under: Uncategorized — manoftoday @ 7:05 pm

 

BFS and FDS

Background

There’re 2 ways to traverse a tree, “Breadth-First Search (BFS)” and “Depth-First Search (DFS).” The following are their strategies.(Both of them begins from the root.)

BFS
  1. Traverse the node.
  2. Expand the node (if it has at least one child) and put its children (in the same level) into a queue respectively (leftest child first).
  3. If the queue is NOT empty, take out the first element from the queue and go to 1. Go to 4 if empty.
  4. End the process.

 

DFS
  1. Traverse the node.
  2. Expand the node (if it has at least one child) and push its children (in the same level) into a stack respectively (leftest child first). <— i think rightest child first is better and clearer
  3. If the stack is NOT empty, pop the top element from the stack and go to 1. Go to 4 if empty.
  4. End the process.

The binary search tree (BST) holds some `nice’ properties (it will be mentioned in your Data Structure course). Now, I just tell you its definition.

BST
  • It’s a binary tree. and its node holds one of these properties.
    1. The node has no children.
    2. The node has either one or two children. The value of all left descendent is smaller than the node, while the value of all right descendent is larger. 

 

Implementation

 DFS

DFS():  non-recursive

Initialize Stack S with root node ROOT;  //if it is graph, it is any beginning node K;

while S.isNotEmpty()

{

node v = S.pop();

 if   v.isVisitedBefore() == false

{

            process(v);

            mark v as visited;

            for all children i of node v // if it is graph, all vertices i adjacent to v

                    push i into Stack S;

}

 
dfs(v) //recursive
{
    if v.isVisitedBefore()
            return;
    process(v)
    mark v as visited
    for all children i of v   //if it is graph, all vertices i adjacent to v 
        dfs(i)
}
 

sorting

http://cs.fit.edu/~wds/classes/algorithms/Sort/sort/sort.html

Quick sort

First, the sequence to be sorted a is partitioned into two parts, such that all elements of the first part b are less than or equal to all elements of the second part c (divide). Then the two parts are sorted separately by recursive application of the same procedure (conquer).

void quicksort (int[] a, int lo, int hi)
{
//  lo is the lower index, hi is the upper index
//  of the region of array a that is to be sorted
    int i=lo, j=hi, h;
    int x=a[(lo+hi)/2];

    //  partition
    do
    {    
        while (a[i]<x) i++; 
        while (a[j]>x) j--;
        if (i<=j)
        {
            swap(i, j);
            i++; j--;
        }
    } while (i<=j);

    //  recursion
    if (lo<j) quicksort(a, lo, j);
    if (i<hi) quicksort(a, i, hi);
}
Average: O(nlogn), Best: O(logn), Worst: O(n2)
It requires log n space for recursion.
 
Merge sort

Similar to Quicksort, the Mergesort algorithm is based on a divide and conquer strategyexplanation. First, the sequence to be sorted is decomposed into two halves (Divide). Each half is sorted independently (Conquer). Then the two sorted halves are merged to a sorted sequence (Combine)

 

void mergesort(int lo, int hi)
{
    if (lo<hi)
    {
        int m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}
 
// Straightforward variant
void merge(int lo, int m, int hi)
{
    int i, j, k;

    // copy both halves of a to auxiliary array b
    for (i=lo; i<=hi; i++)
        b[i]=a[i];

    i=lo; j=m+1; k=lo;
    // copy back next-greatest element at each time
    while (i<=m && j<=hi)
        if (b[i]<=b[j])
            a[k++]=b[i++];
        else
            a[k++]=b[j++];

    // copy back remaining elements of first half (if any)
    while (i<=m)
        a[k++]=b[i++];
}
Similar to QuickSort, but requires  O(n) extra space.

Exchange sort:

[[Bubble sort]]=
public void  bubbleSort (Record[] record) {
  for (int i = record.length; i > 1; i--) {
    for (int j = 1; j < i; j++) {
      if (record[j-1].key > record[j].key) { 
        record.swap(j-1, j);
      }
    }
  }
}
Average: O(n2), Best: O(1), Worst: O(n2)

Insertion Sort

 

Let a0, …, an-1 be the sequence to be sorted. At the beginning and after each iteration of the algorithm the sequence consists of two parts: the first part a0, …, ai-1 is already sorted, the second part ai, …, an-1 is still unsorted (i element 0, …, n).

In order to insert element ai into the sorted part, it is compared with ai-1, ai-2 etc. When an element aj with aj<=ai is found, ai is inserted behind it. If no such element is found, then ai is inserted at the beginning of the sequence.

After inserting element ai the length of the sorted part has increased by one. In the next iteration, ai+1 is inserted into the sorted part etc. While at the beginning the sorted part consists of element a0 only, at the end it consists of all elements a0, …, an-1.

nsertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n2), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.

 

private void insertionsort()
    {
        int i, j, t;
        for (i=1; i<n; i++)
        {
            j=i-1;
            value=A[i];
            while (j>0 && A[j]>value)
            {
                A[j+1]=A[j]; //shift right side for one more position
                j--;
            }
            A[j]=value;
        }
    }

sorting by selection

the smallest (largest) item is found and placed first (last), then the next smallest (largest) is selected, and so on.

Straight selection sort

Find the smallest key and transfer it to output (or the first location in the file). Repeat this step with the next smallest key, and continue. 
Notice after i steps, the records from location 0 to i - 1 will be sorted.
 
[[Straight selection sort]]=
public void selectionSort(Record[] record) {
  for (int i = 0; i < record.length; i++) {
    int min = i;
    for (int j = i+1; j < record.length; j++) { 
      if (record[j].key < record[min].key)  min = j;   //find the min value's location
    }
    Swap (record[min], record[i]);
  } 
}

Average: O(n2)

HeapSort

 

That is, a heap is a binary tree which is completely filled at all levels except possibly the last, which is filled from

left to right and the key in each node is larger than (or equal to) the keys of its children.

[Build a heap]=
  buildHeap(Record[] record) {
  for (int k = Math.floor (record.length/2); i > 0; i--) {
    heapify(record, k);
  }
}
[[Heapify from Node k ]]=
public void  heapify (Record[] records, int k) {
  int j = k;
  int left = 2*k;
  int right = 2*k+1;
  if (left <= records.length-1 && records[left].key > records[k].key) {
    j = left;
  }
  if (right <= records.length-1 && records[right].key > records[largest].key) {
    j = right;
  }
  if (largest != k) {
    records.swap(k, j);
    heapify(records, j);
  }
}
Building a heap is O(n).
[[Heapsort]]=
public void  heapSort(Record[] record) {
  int n = record.length;
  buildHeap(record);
  for (int k = n-1; k > 1; k--) {
    record.swap(1, k);  //Exchange the root of the tree with the last element of the tree;
    --record.length;    //Decrement the heap size by one;
    heapify(record, 1); //Heapify from the root of the tree;
  }
  record.length = n;
}
Swapping the root and the last element and decrementing heap size are $ \Omega$(1). Each time we heapify from the root of the tree it will take 
time  O(logK), thus total time is O(nlogK)
 

Shell Sort

The idea of Shellsort is the following:

  1. arrange the data sequence in a two-dimensional array
  2. sort the columns of the array

The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column.

 
 

Sorting by Distribution :  counting sort, radix sort, and bucket (or bin) sort

Sorting by Insertion    straight insertion sort, binary insertion, and Shell’s sort

Sorting by selection   straight selection sort, tree sort, and heapsort

Sorting by Exchange bubblesort and  cocktail shaker sort.

 

A sorting technique that guarantees that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be stable

 

 

You want to check whether a given set of items is sorted or not.Which of the following sorting methods will be the most efficient if it is already in sorted order?
a. Bubble sort b. Selection sort c. Insertion sort d.Merge sort
Ans. c

Dijkstra  Prim Kruskal

The shortest path algorithm gives minimum distance between any two nodes.  Floyd’s algorithm

Dijkstra  : Given a connected graph G=(V,E), a weight d:E->R+ and a fixed vertex s in V, find a shortest path from s to each vertex v in V.  Time complexity:  O(E+VlogV);  Dijkstra  gives Shortest path only between a given source and multiple destinations;

Prim:    Given a connected graph G=(V,E) and a weight d:E->R+, find a minimum spanning tree.   In minimum spanning tree,we get the shortest path between the source and the destination.

Kruskal: Given a connected graph G=(V,E) and a weight d:E->R+, find a minimum spanning tree T.  O(E*logV);

 

Encoding algorithms

Lossless encoding techniques include
i) Run length encoding
ii) Huffman encoding
iii) Transform coding
The correct option is
a. i
b. i and ii
c. all of the above
d. only ii
Ans. b

Greedy algorithms

Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems

A greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, reducing each problem to a smaller one.

Blog at WordPress.com.