FUNDAMENTALS OF COMPUTER ALGORITHMS

INTRODUCTION:

The word algorithm is named after the ninth century scholar 'Abu Jafar Muhammad Ibn Musa Al-Khwarizmi'. An algorithm is a step-by-step procedure by which a computer can produce the required outputs from the available inputs. An algorithm must have a finite set of steps in reaching the solution of the problem. We can say that an algorithm is a set of rules that precisely (unambiguously) defines the sequence of operations that have to be performed to generate the required output.

An algorithm can be written in English-like language. But since the English language is not precise, most algorithms are written in a notation called pseudocode. Pseudocode looks like statements from a programming language, but it will not run on any computer. Pseudocode is simple, readable, and has no grammatical rules. The words algorithm and pseudocodes are often used interchangeably.

An algorithm is useful because it can be used to state the sequence of steps that will eventually lead to the correct output. While writing an algorithm, the programmer need not be concerned about the syntax of the programming language. Thus, an algorithm can be used to write the program in any programming language because the logical steps are given in the algorithm. An algorithm can also be used to reduce the number of steps in computation and increase the speed of computation.

The three types of algorithms we will study here are:

1. Based on input-process-output: In this type, we take input from the user, use a formula for calculations, and display (output) the result.
2. Based on input-decision-process-output: In this type, we take input from the user, check whether the input is correct, and then use a formula for calculations, and display (output) the result. If the input is invalid, we terminate the process.
3. Based on simple loops: In this type, we take input from the user, use a formula for calculations, and display (output) the result. We then perform the steps all over again as many times as indicated by the user or till a condition is true. These types of algorithms will usually also involve decision making.

Examples Based on Input-Process-Output:

Example 1: Computing the total marks obtained by a student

Let us consider a simple example of calculating the total marks obtained by a student in three subjects. The following algorithm shows the steps in performing this calculation. Observe that the sequence of steps is important; we cannot change the sequence because it is in a logical order.

• Enter the marks of subject 1 (let us call this as MKS1).
• Enter the marks of subject 2 (MKS2)
• Enter the marks of subject 3 (MKS3).
• Calculate total marks : Total = MKS1 + MKS2 + MKS3
• Display MKS1, MKS2, MKS3, and Total.

Example 2: Algorithm to convert an amount in US Dollars into equivalent amount in Indian rupees.

• Enter the amount in US dollars (let us call this as D).
• Let conversion rate be 1 US dollar = INR 55
• Amount in Indian rupees ( R ) = D * 55
• Display the amount in US dollars and the amount in Indian rupees.

Examples based on Input-Decision-Process-Output

Example 3: An algorithm for a simple calculator:

1. Get two numbers (A and B) and the operation desired.
2. Check the operation:
   • If the operation is addition, the result is A + B.
   • If the operation is subtraction, the result is A - B.
   • If the operation is multiplication, the result is A * B.
   • If the operation is division, check the second number.
     • If the second number (B) is zero, create an error message (since division by zero is not defined)
     • If the second number (B) is not zero, the result is A / B

3. Display the result or the error message.

Example 4: An algorithm to find the largest of three numbers.

• Read the numbers A, B and C.
• Max = A (Assume A is the largest number)
• If B > Max, then Max = B
• If C > Max, Max = C
• Display Max

Examples based on loops

Example 5: Write an algorithm to find the sum of first 10  numbers (i.e. 1+2+3+4+…+ 10)

• Initialize sum S = 0.
• Initialize N = 1. (N is a variable that we will take on different values from 1 to 10)
• Calculate S = S + N.
• Calculate N = N+1.
• If N > 10, then go to step 6 else go to step 3.
• Display the sum S.

Example 6:  An algorithm for a simple ATM machine:

The following example illustrates an algorithm for a simple ATM machine.

1. Insert the ATM card into the slot.
2. Get the password from the user.
3. If the password is not valid, display an error message and go to step 7.
4. Get the inputs:
   • Get the type of transaction (deposit or withdrawal) and the amount from the user.
   • Get the current balance from the bank.
5. If the transaction type is deposit, add the amount to the current balance.
6. If the transaction type is withdrawal, check the current balance.
   • If amount is greater than the current balance, display an error message and go to step 7
   • If amount is equal to or less than the current balance, subtract the amount from the current balance.
7. Output the error message or the cash, and display the current balance.
8. Ask the user whether to repeat steps 1 through 6 for another transaction.

The Efficiency of Algorithms:

An efficient algorithm must utilise effectively all the available resources of a computer system. The two most important resources in a computer system are CPU time and primary memory (RAM). An efficient algorithm must run as quickly as possible (i.e. occupy least amount of CPU time), and use as little memory as possible. The following points must be kept in mind for designing efficient algorithms:

1. Avoid redundant computations: If any calculation is likely to be repeated, it is better to do that calculation once instead of doing it inside a loop. For example, suppose the bonus of all employees must be Rs 5000, then it is better to do this assignment once before a loop.
2. Do not provide more tests than necessary to solve a problem. For example, suppose we are searching for a particular name in an alphabetically ordered list of names. Suppose we are looking for a name POOJA. Since the list is arranged alphabetically, if we come across the name PRIYA without locating POOJA, it means that POOJA is not in the list. Hence there is no need to search till the end.
3. The algorithm should be capable of detecting the desired output condition and stop immediately. For example, consider the job of sorting a list of names in alphabetical order. When the given data is sorted, the algorithm should stop.
4. Algorithms should use the least number of loops.

 Qualities of Good Algorithms:

1. Each statement of an algorithm must have a clear and unambiguous meaning.
2. The algorithm must be executed in a finite time.
3. They are simple but offer general solutions to problems.
4. They are easily understood by others, hence it is easy to write algorithms.
5. They can be modified easily.
6. They give correct solutions for clearly defined problems.
7. Efficient algorithms help in economical use of computer time (CPU time), main memory and secondary storage devices.
8. They are documented well enough to be understood and used by others.
9. They are not dependent on a particular programming language or computer.
10. They can be used as part of other more complex problems.

REVIEW QUESTIONS

1. Define the term algorithm.
2. What are the three different types of algorithms you have encountered in this chapter?
3. What are the qualities of a good algorithm?
4. What is meant by an efficient algorithm? Explain.
5. Write an algorithm to calculate the area of a circle when the radius is input (A = π r²).
6. Write an algorithm to compute the simple interest and total amount due to be paid to a customer on a Principal amount P, kept in a bank for T years at interest rate R. The formula for simple interest is I = PRT/100.
7. Write an algorithm to find the sum of first p natural numbers where p is entered by the user.
8. Write an algorithm to find the sum of first 10 even integers.
9. Write an algorithm to read a series of numbers until the number -99 is encountered. Compute an print the total and average of these numbers, excluding -99 from these calculations.