Algorithms as discussed earlier are step by step procedure for solving a given problem. As said earlier, algorithms can be written using natural language or pseudocode. There is no standard way of writing algorithms in pseudocode. So there is a need for basic guidelines for writing algorithms. The problem solving starts with stepwise refinement. The idea of stepwise refinement is to take a problem and try to divide it into many subproblems. The subproblems can further be divided more subproblems. The subdivision will be carried out till the problem can\u2019t further be divided. Hence, the idea of stepwise refinement is to evolve structures that can be directly implemented in a programming language.<\/p>\n\n\n\n
The kinds of structures thus evolved are sequence, decision and Iteration. These are called control structures and are described below:<\/p>\n\n\n\n
1. Sequence<\/p>\n\n\n\n
Sequence is a structure whereby the computer system executes tasks one by one. This is given as follows:<\/p>\n\n\n\n
Task P<\/p>\n\n\n\n
Task Q<\/p>\n\n\n\n
Task R<\/p>\n\n\n\n
Here, the task P is executed first, followed by tasks Q and R.<\/p>\n\n\n\n
2. Decision or Conditional Branching<\/p>\n\n\n\n
This is a control structure where the condition is evaluated first and based on its condition the course of action is decided. The control structure for decision is given as follows:<\/p>\n\n\n\n
IF (Condition C) Then<\/p>\n\n\n\n
Perform Task A<\/p>\n\n\n\n
Else <\/p>\n\n\n\n
Perform Task B<\/p>\n\n\n\n
It can be observed that the condition C is evaluated first. Then based on the results of the condition, task P is performed if the condition is true or task Q is performed if the condition is false.<\/p>\n\n\n\n
3. Repetition<\/em><\/p>\n\n\n\n Computers are known for their effectiveness in solving repetitive tasks. Repetition control structure is given as follows:<\/p>\n\n\n\n While (condition C) do<\/p>\n\n\n\n R<\/p>\n\n\n\n For example, informally we say often in English language \u201cPerform the task 100 times\u201d. This is a kind of repetition.<\/p>\n\n\n\n There are two types of iteration. Iteration like saying \u201cPerform task A exactly 500 times\u201d is called a bounded iteration. Programming languages do provide a \u2018For \u2013 Statement\u201d that implements a bounded iteration. On the other hand, statements like performing a task for a specific condition are called unbound iteration. Good examples of unbounded iteration are statements like \u201cWhile\u2026End while\u201d and \u201crepeat \u2026. until\u201d.<\/p>\n\n\n\n Once the control structures are evolved, then it has to be written as an algorithm. There are only three ways of writing algorithms:<\/p>\n\n\n\n 1. Using a natural language like English.<\/p>\n\n\n\n 2. Using a programming languages, say C++ or Java.<\/p>\n\n\n\n 3. Pseudocode<\/p>\n\n\n\n English, or any natural language, is obvious choice for writing algorithms. But the problem is most of the natural languages are ambiguous as a wrong interpretation of a word may lead to imprecise implementation. Hence, natural languages are not considered suitable for algorithm writing. Similarly, the usage of a programming language makes algorithm dependent on a particular language. Hence, pseudocode is preferable for writing algorithms. One can recollect from module 1 that pseudocode is a mix of natural language like English and mathematical constructs.<\/p>\n\n\n\n Let us evolve a pseudocode conventions so that the algorithm can be written. The pseudocode conventions of the algorithms are specified below:<\/p>\n\n\n\n 1. Assignment Statement<\/p>\n\n\n\n Assignment statement is a statement for assigning a value or expression to a variable. For example, the following assignment statements are valid.<\/p>\n\n\n\n x <\/em>= 20<\/p>\n\n\n\n z = r + k<\/p>\n\n\n\n 2. Input\/output Statements<\/p>\n\n\n\n Input statement is used by the user to give values to the variables of the algorithm. For example, the following statement is right.<\/p>\n\n\n\n Input x, y<\/p>\n\n\n\n Similarly, the print or write statement is used to print the values of the variables. For example, the following statement is used to print the value of the variable x and y.<\/p>\n\n\n\n Print x,y or Write x,y<\/p>\n\n\n\n 3. Conditional Statements<\/strong><\/p>\n\n\n\n Algorithm can have conditional statement. The syntax of the conditional statement can be shown as:<\/p>\n\n\n\n If <\/em>(condition) then<\/p>\n\n\n\n Statement (s)<\/p>\n\n\n\n End if<\/p>\n\n\n\n Here, the condition (True or false type) is evaluated first. If the condition is true, then statement(s) are executed. \u201cIf- Endif\u201d serves as brackets for the conditional statement. Conditional statement can have else part also as shown below:<\/p>\n\n\n\n If<\/em> (condition) then <\/p>\n\n\n\n Statement A ;<\/p>\n\n\n\n else<\/em><\/p>\n\n\n\n <\/em> Statement B <\/p>\n\n\n\n End if<\/em><\/p>\n\n\n\n Here, If the condition is true, then statement A (This can be a set of statements also) are executed. Otherwise, if the condition is false, then statement B (This also can be a single or multiple statements) is executed.<\/p>\n\n\n\n 4. Repetition Statement<\/strong><\/p>\n\n\n\n Algorithms can have repetitive statements. Three repetitive statements are supported by most of the programming languages.<\/p>\n\n\n\n Unconditional repetitive statement is \u2018For\u2019 statement. This is an example of bounded iteration. The syntax of this statement is given as follows<\/p>\n\n\n\n For variable = value1 to value2 do<\/p>\n\n\n\n Statement(s)<\/p>\n\n\n\n End for<\/p>\n\n\n\n Computer system executes this statement like this: First the variable is to value1. Value1 and value2 can be a value or an expression. Then the statement(s) is executed till the variable values reaches value2. <\/p>\n\n\n\n Conditional Loop:<\/p>\n\n\n\n One useful repetitive statement is \u201cWhile\u201d statement that provides a conditional loop. The syntax of the statement is given below:<\/p>\n\n\n\n While (Condition) do begin<\/p>\n\n\n\n Statement(s);<\/p>\n\n\n\n End while.<\/p>\n\n\n\n Repeat\u2026Until also provides repetition control structure. The difference between this statement and While statement is that \u201crepeat \u2013 until\u201d statement first executes the task and then checks condition of the statement. The syntax of repeat statement is given below:<\/p>\n\n\n\n repeat <\/p>\n\n\n\n Statement(s)<\/p>\n\n\n\n until (condition)<\/p>\n\n\n\n Using these statements, some elementary algorithms can be designed.<\/p>\n\n\n\n let us practice some elementary algorithms and let us consider the problem of converting Fahrenheit to Celsius. The problem can be directly solved using a simple formula. The formula for conversion is given as<\/p>\n\n\n\n\n\n The algorithm can be written informally as follows:<\/p>\n\n\n\n 1. Input Fahrenheit temperature<\/p>\n\n\n\n 2. Apply the formula for temperature conversion<\/p>\n\n\n\n 3. Display the results.<\/p>\n\n\n\n The algorithm can be given formally as follows:<\/p>\n\n\n\n Algorithm FtoC(F)<\/strong><\/p>\n\n\n\n Input : Fahrenheit F<\/p>\n\n\n\n Output: Celsius<\/p>\n\n\n\n Begin<\/p>\n\n\n\n Celsius = (5\/9)* (F-32)<\/p>\n\n\n\n Return Celsius;<\/p>\n\n\n\n End.<\/p>\n\n\n\n Let us practice one more algorithm for finding the count and sum of even\/odd numbers of an array. The algorithm can be given informally as follows;<\/p>\n\n\n\n 1. Initialize oddcount, evencount, oddsum and evensum<\/p>\n\n\n\n 2. Read the sumber<\/p>\n\n\n\n 3. If it is odd or even, then increment the appropriate counters<\/p>\n\n\n\n 4. Display the results<\/p>\n\n\n\n The algorithm is formally given as follows:<\/p>\n\n\n\n Algorithm sumoddeven (A[1..n])<\/p>\n\n\n\n Input: An array A[1..n]<\/p>\n\n\n\n Output: sum on odd and even number count<\/p>\n\n\n\n oddcount = 0<\/p>\n\n\n\n evencount = 0<\/p>\n\n\n\n oddsum = 0<\/p>\n\n\n\n evensum = 0<\/p>\n\n\n\n for i = 1 to n<\/p>\n\n\n\n reminder = A[i] mod 2<\/p>\n\n\n\n if (reminder = 0) then<\/p>\n\n\n\n evensum = evensum + A[i]<\/p>\n\n\n\n evencount = evencount + 1<\/p>\n\n\n\n else<\/p>\n\n\n\n oddsum = oddsum + A[i]<\/p>\n\n\n\n oddcount = oddcount + 1<\/p>\n\n\n\n End if<\/p>\n\n\n\n End for<\/p>\n\n\n\n Return evensum, evencount, oddsum, oddcount<\/p>\n\n\n\n End<\/p>\n\n\n\n Another popular algorithm is linear search. Here, a target is given and the objective of the linear search is to display whether the target is present in the given array, if so where? And failure message is the target is not present in the array.<\/p>\n\n\n\n The informal algorithm is given as follows:<\/p>\n\n\n\n 1. Read the value of the target and array A<\/p>\n\n\n\n 2. Index = 1, found = false<\/p>\n\n\n\n 3. Repeat until found = true of index > n<\/p>\n\n\n\n if the value at index = target then<\/p>\n\n\n\n return the index and set found = true<\/p>\n\n\n\n else index = index + 1<\/p>\n\n\n\n 4. If (not found) then output message that target is not found<\/p>\n\n\n\n 5. Exit<\/p>\n\n\n\n It can be seen that initially index and flag found is initialized to 1 and \u2018false\u2019 respectively. Every value guided by index pointer is checked and if the target is found, then the flag is set true and the corresponding index is sent. Otherwise, the failure message to find target is printed.<\/p>\n\n\n\n Formally this can be written as follows:<\/p>\n\n\n\n Algorithm Search(list, n , target)<\/p>\n\n\n\n Begin<\/p>\n\n\n\n index = 1<\/p>\n\n\n\n found = false<\/p>\n\n\n\n repeat until found = true of index > n<\/p>\n\n\n\n if (listindex<\/sub> = target ) then<\/p>\n\n\n\n print \u201ctarget found at\u201d, index<\/p>\n\n\n\n found = true<\/p>\n\n\n\n else index = index + 1<\/p>\n\n\n\n if (not found) then print \u2018Target is not found\u2019<\/p>\n\n\n\n End<\/p>\n\n\n\n Thus one can conclude that after stepwise refinement, the control structures are evolved and can be written suitable as a pseudocode. Now let us discuss about recursive algorithms.<\/p>\n\n\n\n Basics of Recursion <\/strong><\/p>\n\n\n\n Recursion is a way of defining an object using the concept of self-reference. The statements like \u201cA length of the linked list of size N is 1 plus the length of the remaining linked list of size N-1\u201d are examples of recursive definition.<\/p>\n\n\n\n Let us start with recursive definitions. The basic components of a recursive algorithm definition are given as follows:<\/p>\n\n\n\n 1. Base case \u2013 This is also known as initial values. This is the non-recursive part.<\/p>\n\n\n\n 2. Recursive step – It is the recursive part of the algorithm. Often this is a rule used for calculating a function in terms of the previous values of the function.<\/p>\n\n\n\n 3. Step for progress towards base case: This is a condition that ensures the algorithm eventually converges by bringing the recursive step towards the base case.<\/p>\n\n\n\n Let us discuss some recursive algorithms now. Let us consider the problem of finding summation problem given as Sigma(n) =<\/p>\n\n\n\n n+ Sigma(n-1) if n > 1<\/p>\n\n\n\n A simple recursive algorithm for implementing the above recursive formula is given as follows:<\/p>\n\n\n\n Algorithm Sigma (N)<\/strong><\/p>\n\n\n\n Program: Compute sum recursively<\/em><\/p>\n\n\n\n Input: N<\/em><\/p>\n\n\n\n Output: Sum of N numbers<\/em><\/p>\n\n\n\n Begin<\/p>\n\n\n\n if (N == 0)<\/p>\n\n\n\n return 0; <\/p>\n\n\n\n else<\/p>\n\n\n\n return N + Sigma(N – 1);<\/p>\n\n\n\n End if<\/p>\n\n\n\n End<\/p>\n\n\n\n The above algorithm can also be written as an iterative algorithm. The iterative algorithm is given as follows:<\/p>\n\n\n\n Algorithm iterative-sigma(N)<\/strong><\/p>\n\n\n\n Program: Compute sum recursively<\/em><\/p>\n\n\n\n Input: N<\/em><\/p>\n\n\n\n Output: Sum of N numbers<\/em><\/p>\n\n\n\n Begin<\/p>\n\n\n\n sum = 0;<\/p>\n\n\n\n for i = 1 to N do<\/p>\n\n\n\n sum = sum + I<\/p>\n\n\n\n end for<\/p>\n\n\n\n End<\/p>\n\n\n\n It can be observed that both versions give identical answers. It can be observed that recursive algorithms are compact and it is easier to formulate the algorithms. But , the disadvantage is that recursive algorithms take extra space and require more memory.<\/p>\n\n\n\n 1 if n = 0<\/p>\n\n\n\n Factorial(n) = n The pseudocode for finding factorial of a number is given as follows:<\/p>\n\n\n\n Algorithm MFactorial(m)<\/p>\n\n\n\n Begin<\/p>\n\n\n\n If m < 0 then<\/p>\n\n\n\n print \u201cfactorial for negative numbers is not possible\u201d<\/p>\n\n\n\n End if<\/p>\n\n\n\n If ((m=0) OR (m = 1) then<\/p>\n\n\n\n Return 1;<\/p>\n\n\n\n Else<\/p>\n\n\n\n Return m * MFactorial(m-1);<\/p>\n\n\n\n End If<\/p>\n\n\n\n End.<\/p>\n\n\n\n Another important problem is towers of Hanoi. There are three pegs \u2013 source, intermediate and destination. The objective of this problem is to move the disks from source peg to the destination peg using the intermediate peg with the following rules:<\/p>\n\n\n\n 1. At any point of time, only one disk should be moved<\/p>\n\n\n\n 2. A larger disk cannot be placed on the smaller disk at any point of time<\/p>\n\n\n\n The logic for solving this problem is that, for N disks, N-1 disks are moved to the intermediate tower and then the larger disk is moved to the destination. Then the disks are moved from the intermediate tower to the destination.<\/p>\n\n\n\n The formal algorithm is given as follows:<\/p>\n\n\n\n Algorithm towersofhanoi(A,B,C,n)<\/strong><\/p>\n\n\n\n Input: Source Peg A, intermediate Peg B and Destination Peg C, n disks<\/em><\/p>\n\n\n\n Output: All the disks in the tower C<\/em><\/p>\n\n\n\n Begin<\/p>\n\n\n\n if n = 1 the move disk from A to C<\/p>\n\n\n\n lse<\/p>\n\n\n\n towersofhanoi (A,C,B,n-1);<\/p>\n\n\n\n move disk from A to C <\/p>\n\n\n\n towersofhanoi (B,A,C,n-1);<\/p>\n\n\n\n End if<\/p>\n\n\n\n End.<\/p>\n\n\n\n Thus, one can conclude this module as follows:<\/p>\n\n\n\n 1. Stepwise refinement leads to a better algorithm<\/p>\n\n\n\n 2. Control structures are sequence, Decision or conditional branching and repetition<\/p>\n\n\n\n 3. Pseudocode is better way of writing algorithms.<\/p>\n\n\n\n References<\/p>\n\n\n\n This module focuses on the basics of the algorithm writing. The learning objectives of this module are as follows: To introduce pseudocode notations for writing algorithms To practice writing elementary algorithms To introduce iterative and recursive algorithms Algorithms as discussed earlier are step by…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","footnotes":""},"categories":[],"tags":[5,6],"class_list":["post-419","post","type-post","status-publish","format-standard","hentry","tag-algorithm-writing","tag-psudocode"],"_links":{"self":[{"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=\/wp\/v2\/posts\/419","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=419"}],"version-history":[{"count":1,"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=\/wp\/v2\/posts\/419\/revisions"}],"predecessor-version":[{"id":420,"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=\/wp\/v2\/posts\/419\/revisions\/420"}],"wp:attachment":[{"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.drssridhar.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}. The recursive definition of summation can be given compactly as follows<\/p>\n\n\n\n
0 if n = 0<\/p>\n\n\n\n
Let us discuss about one more recursive algorithm for finding factorial of a number. The recursive function for finding the factorial of a number is given as follows:<\/p>\n\n\n\n
factorial(n-1) if
<\/p>\n\n\n\n