Introduction to Algorithm as Technology

Introduction to Algorithm as Technology:

Algorithm: An algorithm is defined as a finite set of instructions that if followed, accomplishes a particular task.

Different phases of the Study of Algorithms:

  1. Designing algorithms: (How to devise algorithms?)
    1. Various design techniques are available to design algorithms. They include:
      1. Divide and Conquer
      2. Greedy Method
      3. Dynamic Programming
      4. Backtracking
      5. Branch and Bound
    2. Based on the type of problem, proper design technique is to be selected
  2. Algorithm Validation: (How to validate algorithms?)
    1. Once an algorithm is devised, it is necessary to show that it computes the correct answer for all possible legal inputs
    2. The purpose of the validation is to assure that this algorithm will work correctly independent of the issues concerning the programming language to be used
    3. After validation only a program can be written
  3. Analysis of algorithms: (How to analyze algorithms?)
    1. It refers to the task of determining the computing time (Time Complexity) and storage space required (Space Complexity) to execute an algorithm on a computer.
    2. It allows you to compare various algorithms used to solve a particular problem (iii)Performance of an algorithm in the best case, average case or the worst case will be measured

4.Testing programs: (How to test a program?)
              (i)Debugging the program is done in this phase
             (ii)It is the process of executing a program on sample data sets to determine whether errors occur and correcting them, if any.

Different criteria that satisfy an algorithm:

   An algorithm must satisfy the following criteria:

  1. Input: zero or more quantities are externally supplied.
  2. Output: At least one quantity is produced.
  3. Definiteness: each instruction is clear and unambiguous. Example: add 6 or 7 to x (not permitted)
  4. Finiteness: if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite no.of steps
  5. Effectiveness: every instruction must also be feasible.

Example: performing arithmetic with real numbers is not much feasible due to long decimal expansions.

Leave a Reply