Algorithm: UNIT 1

(1.1) Introduction:

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.

Before the electronic computer was invented, the word "computer" meant a human being involved in performing numeric calculations.

Notion of algorithm:

Some important points:

• The non-ambiguity requirement for each step of an algorithm cannot be com· promised.
  This means that there must be no place for multiple views or assumptions on the algorithm, but must convey the same instruction to everyone, by stating it as clearly as possible.

• The range of inputs for which an algorithm works has to be specified carefully.

• The same algorithm can be represented in several different ways.

• Several algorithms for solving the same problem may exist.

• Algorithms for the same problem can be based on very different ideas and can solve the problem with dramatically different speeds.

As an example, below are three different ways of finding greatest common divisor (gcd) of two numbers.

gcd(m, n), is defined as the largest integer that divides both m and n evenly, i.e., with a remainder of zero.

• (1) Euclid’s method: Euclid's algorithm is based on applying repeatedly the equality

  gcd(m, n) = gcd(n, m mod n)

  until m mod n is equal to 0; since gcd(m, 0) = m

  For example, gcd(60, 24) can be computed as follows:

  gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.

  The algorithm for the same will look like,

  Euclid's algorithm for computing gcd(m, n):

  • Step 1 : If n = 0, return the value of m as the answer and stop; otherwise, proceed to Step 2.

  • Step 2 : Divide m by n and assign the value of the remainder to r.

  • Step 3: Assign the value of n tom and the value of r ton. Go to Step 1.

  Alternatively, we can express the same algorithm in a pseudocode:

  ALGORITHM Euclid(m, n):

  • //Computes gcd(m, n) by Euclid's algorithm !!Input: Two non-negative, not -both-zero //integers m and n
    //Output: Greatest common divisor of m and n
    while n≠0 do
    r ← m % n
    m ← n
    n ← r
    return m

• (2) Consecutive integer checking algorithm for computing gcd(m, n):

  • Step 1: Assign the value of min{m, n) to t.

  • Step 2: Divide m by t. If the remainder of this division is 0, go to Step 3; otherwise, go to Step 4.

  • Step 3: Divide n by t. If the remainder of this division is 0, return the value of t as the answer and stop; otherwise, proceed to Step 4.

  • Step 4: Decrease the value oft by 1. Go to Step 2.

    For example, for numbers 60 and 24, the algorithm will try first 24, then 23, and so on until it reaches 12, where it stops.

    Note that unlike Euclid's algorithm, this algorithm, in the form presented, does not work correctly when one of its input numbers is zero. This example illustrates why it is so important to specify the range of an algorithm's inputs explicitly and carefully.

• (3) Middle-school procedure for computing gcd(m, n):

  • Step 1: Find the prime factors of m.

  • Step 2: Find the prime factors of n.

  • Step 3: Identify all the common factors in the two prime expansions found in Step 1 and Step 2. (If p is a common factor occurring Pm and Pn times in m and n, respectively, it should be repeated min{pm, p,) times.)

  • Step 4: Compute the product of all the common factors and return it as the greatest common divisor of the numbers given.

    Thus, for the numbers 60 and 24, we get

    60=2·2·3·5

    24=2·2·2·3

    gcd(60, 24) = 2. 2. 3 = 12.

• (4) sieve of Eratosthenes: The algorithm starts by initializing a list of prime candidates with consecutive integers from 2 to n. Then, on the first iteration of the algorithm, it eliminates from the list all multiples of 2, i.e., 4, 6, and so on.

  (continuation, if interested) Then it moves to the next item on the list, which is 3, and eliminates its multiples. (In this straightforward version, there is an overhead because some numbers, such as 6, are eliminated more than once.) No pass for number 4 is needed: since 4 itself and all its multiples are also multiples of 2, they were already eliminated on a previous pass. (By similar reasoning, we need not consider multiples of any eliminated number.) The next remaining number on the list, which is used on the third pass, is 5. The algorithm continues in this fashion until no more numbers can be eliminated from the list. The remaining integers of the list are the primes needed.
  

  As an example, consider the application of the algorithm to finding the list of primes not exceeding n = 25:

  
  

  The pseudocode for the same will look like:
  ALGORITHM Sieve(n):
  //Implements the sieve of Eratosthenes
  //Input: An integer >= 2
  //Output: Array L of all prime numbers less than or equal to n
  for p ← 2 to n do A[p] ← p
  for p ← 2 to |_n_| do //see note before pseudocode
  if A[p] ≠ 0 //p hasn't been eliminated on previous passes
  j ← p * p
  while j <= n do
  A[j] ← 0 //mark element as eliminated
  j ← j + p
  //copy the remaining elements of A to array L of the primes
  i ← 0
  for p ← 2 to n do
  if A[p] ≠ 0
  L[i] ← A[p]
  i ← i + 1
  return L

  
  

(1.2) Fundamentals of Algorithmic Problem Solving:

We can consider algorithms to be procedural solutions to problems.

These solutions are not answers but specific instructions for getting answers.

Steps to design and analyze an Algorithm:

• Understanding the Problem: Read the description, do some research on its history and ask questions on it to get a clear view on the problem.

• Ascertaining the Capabilities of a Computational Device: Be sure that the device it is meant to be used on, has the required resources to use the algorithm. For instance, the RAM, if the program is very huge, or the graphics card, if it is something related to visual presentation.

  • Choosing between Exact and Approximate Problem Solving: Some problems are difficult to be solved, hence there is a need to choose an approximate algorithm to save reasonable time and space.

  • Deciding on Appropriate Data Structures: Some programs don’t require for specific data-structure to be used, but some do. For instance, you can input a number to a string, but you cannot perform arithmetic addition, as in C, on the number unless there are other methods to extract a number from the string, like in python.

  • Algorithm Design Techniques: Following a systematic approach while designing or analyzing algorithms will help build a collection of tools which will help solve other problems as well. For example, the divide and conquer technique.

• Methods of Specifying an Algorithm: Decide the way to present your algorithm, either in the form of a typical algorithm, or as pseudocode.

  Proving an Algorithm's Correctness: Prove that the algorithm yields a required result for every legitimate input in a finite amount of time. For example, correctness of Euclid's algorithm for computing the greatest common divisor stems from correctness of the equality gcd(m, n) = gcd(n, m mod n)

• Analyzing an Algorithm: Improve the quality of the algorithm, which includes time efficiency, generality, space efficiency and simplicity.

• Coding an Algorithm: The heading says it all. Choose a language and get yo’ ass up.