In this tutorial we will learn basic concepts of algorithm and it’s application. We will also learn about Pseudo Code.
Algorithm is not a concept unique to computation. It is everywhere. Even we use it knowingly or unknowingly, to carry out day-to-day activities or solve specific problems.
Taking bath algorithm
Taking bath is a daily activity and we follow certain steps to carry out it.
Car parking algorithm
We are writing a car parking algorithm to park a car at a parking spot. All numbers are hypothetical.
Step 1: Go to parking lot using main gate. Step 2: Go straight for 10 meters. Step 3: Take a left turn. Step 4: Go straight for 8 meters. Step 5: Turn car in 45 degree angle. Step 6: Move back your car in same angle for 12 meters Step 7: Stop Engine Ignition. Step 8: Lock car gates.
If we write down the steps required to carry out our day-to-day activities or problem solving. We came across following computational concepts:
- Loop or Repetition – Repeating certain steps again and again. For e.g. Sprinkle water on plant 10 times (for 10 plants of course).
- Sequencing – Following one step after another or so on. For e.g. Wearing shoes require following steps in a sequence: pull shoe from shoe rack, putting sock and wearing shoes. Not following step in sequence will lead to a problem.
- Conditional Logic – Out of two possible steps which one to follow. For e.g. If it is Friday I will wear casual otherwise formal cloths.
When we break down any activity into discrete steps and create an algorithm like we did before, this way of thinking called algorithmic thinking. It is a powerful tools for better decision-making in life, because it brings clarity in out action.
What is an algorithm in computation?
Our expectation from computer is to help in solving real life problems with fast and accurate results in compare to manual work. Algorithm is one of the most important concept of computer science. It provides tools and methodologies to solve well-defined computational problems.
Algorithm is an idea and a plan to solve well-defined general purpose computational problem. It takes Input, process them using step by step instruction and produce expected output.
For e.g. Finding max value in a list of number.
SET Max to listOfNumbers FOR i = 1 to listOfNumbers length - 1 IF listOfNumbers[i] > Max THEN SET Max to listOfNumbers[i] ENDIF ENDFOR PRINT Max
It is a well-defined general purpose problem which clearly mention the Input and expected output. It will work for any Input consisting it is a list of numbers.
If a problem is not well-defined and general purpose, we are not finding an algorithm but solving a very specific problem, which may or may not an algorithm for a general purpose problem.
We evaluate algorithm against these important factors:
- Correctness – An algorithm need to yield correct result for all possible inputs.
- Efficiency – What is performance of an algorithm against the size of inputs.
Another important factor is implementation complexity, but it not as significant than correctness and efficiency. But in situations when we have two algorithm with similar efficiency, we will select which is easier to implement.
We can represent an algorithm using plain english, pseudo code, flow chart (for small problems) or program.
Plain english is very descriptive while programs are very complex to read. Pseudo Code is easier to read while looks like program without any syntax validation.
Note: Pseudo code is not a standard but it’s a convention.
Most common Pseudocode notations:
INPUT – To take user input.
SET – Set value in variable.
INITIALIZE – initialize variable with a value.
WHILE – A loop with a condition at the beginning.
FOR – A loop with a counter.
REPEAT – UNTIL – A loop with condition at the end.
IF – THEN – ELSE – It denote conditional logic or decision-making for multiple choices.
OUTPUT – To display output on-screen, print, file etc.
PRINT – Print output.
- Indentation – Any step that occur inside a choice or iteration are usually indented.
- Convention not rule – You are free to make changes into convention.
- Capital case for notations – You may use lowercase or CamelCase whatever suits you.
Example 1: Print Pass or Fail for a score
Input: A number
Output: If input number is 50 or more than Output Pass otherwise fail
INPUT score IF score >= 50 OUTPUT Pass ELSE OUTPUT Fail
Example 2: Average of classroom scores
Input: A list of numbers
Output: A number representing average of input list of numbers
INPUT scores into listOfScore SET total to 0 SET noOfScore to 0 SET classAverage to 0 WHILE length of listOfScore > noOfScore SET total = total + listOfScore[noOfScore] SET noOfScore = noOfScore + 1 SET classAverage = total divided by noOfScore OUTPUT classAverage
- Pseudocode definition at BBC website.
- University of Texas Pseudocode examples.
- Khan Academy video explaining algorithm basics.
- How to explain algorithm to Kids.