VJY Softworx Inc.

SELECTION_SORT (A)

for i ← 1 to n-1 do
    min j ← i;
    min x ← A[i]
    for j ← i + 1 to n do
        If A[j] < min x then
            min j ← j
            min x ← A[j]
    A[min j] ← A [i]
    A[i] ← min x

Implementation

void selectionSort(int numbers[], int array_size)
{
  int i, j;
  int min, temp;

  for (i = 0; i < array_size-1; i++)
  {
    min = i;
    for (j = i+1; j < array_size; j++)
    {
      if (numbers[j] < numbers[min])
        min = j;
    }
    temp = numbers[i];
    numbers[i] = numbers[min];
    numbers[min] = temp;
  }
}

 

1. We start with an empty left hand [sorted array] and the cards face down on the table [unsorted array].
2. Then remove one card [key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].
3. To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.

• The worst-case running time gives a guaranteed upper bound on the running time for any input. That is, upper bound gives us a guarantee that the algorithm will never take any longer.
• For some algorithms, the worst case occurs often. For example, when searching, the worst case often occurs when the item being searched for is not present, and searches for absent items may be frequent.
• Why not analyze the average case? Because it's often about as bad as the worst case.

• For Insertion sort we say the worst-case running time is θ(n²), and the best-case running time is θ(n).
• Insertion sort use no extra memory it sort in place.
• The time of  Insertion sort is depends on the original order of a input. It takes a time in Ω(n²) in the worst-case, despite the fact that a time in order of n is sufficient to solve large instances in which the items are already sorted.

void insertionSort(int numbers[], int array_size)
{
  int i, j, index;

  for (i = 1; i < array_size; i++)
  {
          index = numbers[i];
          j = i;
          while ((j > 0) && (numbers[j − 1] > index))
          {
                   numbers[j] = numbers[j − 1];
                   j = j − 1;
          }
          numbers[j] = index;
  }
}

SEQUENTIAL BUBBLESORT (A)

for i ← 1 to length [A] do
    for j ← length [A] downto i +1 do
        If A[A] < A[j-1] then
            Exchange A[j] ↔ A[j-1]

 

Memory Requirement

 

 

Implementation

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

  for (i = (array_size - 1); i >= 0; i--)
  {
    for (j = 1; j <= i; j++)
    {
      if (numbers[j-1] > numbers[j])
      {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}

 

PARALLEL BUBBLE SORT (A)

1. For k = 0 to n-2
2. If k is even then
3.     for i = 0 to (n/2)-1 do in parallel
4.         If A[2i] > A[2i+1] then
5.             Exchange A[2i] ↔ A[2i+1]
6. Else
7.     for i = 0 to (n/2)-2 do in parallel
8.         If A[2i+1] > A[2i+2] then
9.             Exchange A[2i+1] ↔ A[2i+2]
10. Next k

 Parallel Analysis

Problem:   Given an array of n real number A[1.. n].
Objective: Sort the elements of A in ascending order of their values. Internal Sort
 
External Sort

• Sorting files from tape or disk.

• In this method, an external sort algorithm must access records sequentially, or at least in the block.

 
Memory Requirement

1. Sort in place and use no extra memory except perhaps for a small stack or table.

1. Algorithm that use a linked-list representation and so use N extra words of memory for list pointers.

1. Algorithms that need enough extra memory space to hold another copy of the array to be sorted.

 
Stability
The Decision Tree Model
 
 
A Lower Bound for the Worst Case
Taking logarithms on both sides

(lg(n!) ≤ h
        h  ≥ lg(n!)
Taking logarithms on both sides
(lg(n!) ≤ h
        h  ≥ lg(n!)
(lg(n!) ≤ h
        h  ≥ lg(n!)
        h  ≥ lg(n!)

• Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
• Solve the sub-problem recursively (successively and independently), and then
• Combine these solutions to subproblems to create a solution to the original problem.

Binary Search (simplest application of divide-and-conquer)

 Sequential Search

for i = 1 to n do
    if A [i] ≥ q then
        return index i
    return n + 1

 Analysis

 

Binary Search

A[i-1] < x ≤ A[j]
If i = j then
    return i (index)
k= (i + j)/2
if q ≤ A [k]
    then return Binary Search [A [i-k], q]
    else return Binary Search [A[k+1 . . j], q]

 

Analysis

 

 

Iterative Version of Binary Search

if q > A [n]
    then return n + 1
i = 1;
j = n;
while i < j do
    k = (i + j)/2
    if q ≤ A [k]
        then j = k
        else i = k + 1
return i (the index)

 Analysis

An algorithm, named after the ninth century scholar Abu Jafar Muhammad Ibn Musu Al-Khowarizmi, is defined as follows: Roughly speaking:

• An algorithm is a set of rules for carrying out calculation either by hand or on a machine.
• An algorithm is a finite step-by-step procedure to achieve a required result.
• An algorithm is a sequence of computational steps that transform the input into the output.
• An algorithm is a sequence of operations performed on data that have to be organized in data structures.
• An algorithm is an abstraction of a program to be executed on a physical machine (model of Computation).

The most famous algorithm in history dates well before the time of the ancient Greeks: this is the Euclid's algorithm for calculating the greatest common divisor of two integers. This theorem appeared as the solution to the Proposition II in the Book VII of Euclid's "Elements." Euclid's "Elements" consists of thirteen books, which contain a total number of 465 propositions.

 The Classic Multiplication Algorithm
1. Multiplication, the American way:
Multiply the multiplicand one after another by each digit of the multiplier taken from right to left.

                                          981
                                        1234
                                -------------
                                        3924
                                      2943
                                    1962
                                    981
                                ------------
                                  1210554


 2. Multiplication, the English way:
Multiply the multiplicand one after another by each digit of the multiplier taken from left to right.

                                           981
                                        1234
                                ---------------
                                    981
                                    1962
                                      2943
                                        3924
                                ----------------
                                  1210554
Algorithmic is a branch of computer science that consists of designing and analyzing computer algorithms
1. The “design” pertain to
i. The description of algorithm at an abstract level by means of a pseudo language, and
ii. Proof of correctness that is, the algorithm solves the given problem in all cases.

2. The “analysis” deals with performance evaluation (complexity analysis).

We start with defining the model of computation, which is usually the Random Access Machine (RAM) model, but other models of computations can be use such as PRAM. Once the model of computation has been defined, an algorithm can be describe using a simple language (or pseudo language) whose syntax is close to programming language such as C or java.

Algorithm's Performance

Two important ways to characterize the effectiveness of an algorithm are its space complexity and time complexity. Time complexity of an algorithm concerns determining an expression of the number of steps needed as a function of the problem size. Since the step count measure is somewhat coarse, one does not aim at obtaining an exact step count. Instead, one attempts only to get asymptotic bounds on the step count. Asymptotic analysis makes use of the O (Big Oh) notation. Two other notational constructs used by computer scientists in the analysis of algorithms are Θ (Big Theta) notation and Ω (Big Omega) notation.
The performance evaluation of an algorithm is obtained by totaling the number of occurrences of each operation when running the algorithm. The performance of an algorithm is evaluated as a function of the input size n and is to be considered modulo a multiplicative constant.

The following notations are commonly use notations in performance analysis and used to characterize the complexity of an algorithm.

Θ-Notation (Same order)

This notation bounds a function to within constant factors. We say f(n) = Θ(g(n)) if there exist positive constants n0, c1 and c2 such that to the right of n0 the value of f(n) always lies between c1 g(n) and c2 g(n) inclusive.

In the set notation, we write as follows:

Θ(g(n)) = {f(n) : there exist positive constants c1, c1, and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0}

We say that is g(n) an asymptotically tight bound for f(n).

Graphically, for all values of n to the right of n0, the value of f(n) lies at or above c1 g(n) and at or below c2 g(n). In other words, for all n ≥ n0, the function f(n) is equal to g(n) to within a constant factor. We say that g(n) is an asymptotically tight bound for f(n).

In the set terminology, f(n) is said to be a member of the set Θ(g(n)) of functions. In other words, because O(g(n)) is a set, we could write

f(n) ∈ Θ(g(n))

to indicate that f(n) is a member of Θ(g(n)). Instead, we write

f(n) = Θ(g(n))

to express the same notation.

Historically, this notation is "f(n) = Θ(g(n))" although the idea that f(n) is equal to something called Θ(g(n)) is misleading.

Example: n2/2 − 2n = (n2), with c1 = 1/4, c2 = 1/2, and n0 = 8.


Ο-Notation (Upper Bound)

This notation gives an upper bound for a function to within a constant factor. We write f(n) = O(g(n)) if there are positive constants n0 and c such that to the right of n0, the value of f(n) always lies on or below c g(n).

In the set notation, we write as follows: For a given function g(n), the set of functions

Ο(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0}

We say that the function g(n) is an asymptotic upper bound for the function f(n). We use Ο-notation to give an upper bound on a function, to within a constant factor.

Graphically, for all values of n to the right of n0, the value of the function f(n) is on or below g(n). We write f(n) = O(g(n)) to indicate that a function f(n) is a member of the set Ο(g(n)) i.e.

f(n) ∈ Ο(g(n))

Note that f(n) = Θ(g(n)) implies f(n) = Ο(g(n)), since Θ-notation is a stronger notation than Ο-notation.

Example: 2n2 = Ο(n3), with c = 1 and n0 = 2.

Equivalently, we may also define f is of order g as follows:

If f(n) and g(n) are functions defined on the positive integers, then f(n) is Ο(g(n)) if and only if there is a c > 0 and an n0 > 0 such that

| f(n) | ≤ | g(n) | for all n ≥ n0

Historical Note: The notation was introduced in 1892 by the German mathematician Paul Bachman. 

Ω-Notation (Lower Bound)

This notation gives a lower bound for a function to within a constant factor. We write f(n) = Ω(g(n)) if there are positive constants n0 and c such that to the right of n0, the value of f(n) always lies on or above c g(n).

In the set notation, we write as follows: For a given function g(n), the set of functions

Ω(g(n)) = {f(n) : there exist positive constants c and n0 such that 0 ≤ c g(n) ≤ f(n) for all n ≥ n0}

We say that the function g(n) is an asymptotic lower bound for the function f(n).

The intuition behind Ω-notation is shown above.

Example: √n = (lg n), with c = 1 and n0 = 16.

Algorithm Analysis

The complexity of an algorithm is a function g(n) that gives the upper bound of the number of operation (or running time) performed by an algorithm when the input size is n.

There are two interpretations of upper bound.

Worst-case Complexity
The running time for any given size input will be lower than the upper bound except possibly for some values of the input where the maximum is reached.
Average-case Complexity
The running time for any given size input will be the average number of operations over all problem instances for a given size.

Because, it is quite difficult to estimate the statistical behavior of the input, most of the time we content ourselves to a worst case behavior. Most of the time, the complexity of g(n) is approximated by its family o(f(n)) where f(n) is one of the following functions. n (linear complexity), log n (logarithmic complexity), na where a ≥ 2 (polynomial complexity), an (exponential complexity).

 Optimality

Once the complexity of an algorithm has been estimated, the question arises whether this algorithm is optimal. An algorithm for a given problem is optimal if its complexity reaches the lower bound over all the algorithms solving this problem. For example, any algorithm solving “the intersection of n segments” problem will execute at least n2 operations in the worst case even if it does nothing but print the output. This is abbreviated by saying that the problem has Ω(n2) complexity. If one finds an O(n2) algorithm that solve this problem, it will be optimal and of complexity Θ(n2).

Reduction

Another technique for estimating the complexity of a problem is the transformation of problems, also called problem reduction. As an example, suppose we know a lower bound for a problem A, and that we would like to estimate a lower bound for a problem B. If we can transform A into B by a transformation step whose cost is less than that for solving A, then B has the same bound as A.

The Convex hull problem nicely illustrates "reduction" technique. A lower bound of Convex-hull problem established by reducing the sorting problem (complexity: Θ(n log n)) to the Convex hull problem.

Simple ppl dont know why they cant create File named with "CON"? Very few know that they can still create it someway.. but  why are they supposed to do exactly like that.. Now, After reading this tutorial, you will become one of the rest. Not only CON, we cannot create any of these:
CON, PRN, AUX, CLOCK$, NUL, COM1, COM2, COM3, COM4, COM5, COM6, COM7, COM8, COM9, LPT1, LPT2, LPT3, LPT4, LPT5, LPT6, LPT7, LPT8, LPT9 and more The reason is that con, prn, lpt1..lpt9, etc are underlying devices from the time dos was written. so if u r allowed to create such folders, there will be an ambiguity in where to write data when the data is supposed to go to the specified devices. In other words, if i want to print something, internally what windows does is -- it will write the data to the folder prn (virtually u can call it a folder, i mean prn, con, etc are virtual folders in device level). So if we are able to create con folder, windows will get confused where to write the data, to virtual con folder or real one. So Now, Try this...


C:\> md \\.\x:\con
Note: x: repersent the Drive letter where want to create. (it may be C:, D: and So on)
Now, Open My Computer and browse through the path where you created CON folder ... Surprising.. ?? Yeah.. you have created it successfully..
Now, try to delete the folder from My computer 
OOPS!!! You cant delete it...


Now, try this in command prompt console




C:\> rd \\.\x:\con


You Did it


For More info You can Click on http://support.microsoft.com