20-10-2010, 10:47 AM
ADA.doc (Size: 752 KB / Downloads: 97)
algorithm,Analysis of INSERTION SORT,Hiring Problem,Quicksort,knapsack problem,Greedy
1. What is algorithm? What are the characteristics of an algorithm? And explain designing methods of an algorithm with example.
Ans: Algorithm:
In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields.
Characteristics of an algorithm
Algorithms should have the following five characteristics:
1.Input: An algorithm must receive some input data supplied externally.
2. Output: An algorithm must produce at least one output as the result
3. Finiteness: no matter what is the input, the algorithm must terminate after a finite number of steps .for ex. procedure which goes on performing a series of steps infinitely is not an algorithm.
4. Definiteness: the steps to be performed in the algorithm must be clear & unambiguous
5.Effectiveness: one must be able to perform the steps in the algorithm without applying any intelligence. For ex. The steps –select three numbers which form a pythogorian triplet-is not effective.
6. Termination: An algorithm must be terminated after its successful completion.
To under stand these characteristics consider the following problem
Problem: finding the largest value among n>=1 numbers.
Input: the value of n and n numbers
Output: the largest value
Steps:
1. let the value of the first be the largest value denoted by BIG
2. Let R denote the number of remaining numbers. R=n-1
3. If R! = 0 then it is implied that the list is still not exhausted. Therefore look the next number called NEW.