SSE | Problem Ton toee A jostumile Solving Gta rning Objectives _o oe concepts in this iter learning the ¢ Aer learning the concer chapter, the students wil of + To understand the cone a algorithmic problem —_ solving: + Toapply the knowledge of algorithmic technique in problem solving. A number of processes ‘performed in our daily life follow the step-by-step execution of a sequence of instructions. Getting ready to school in the morning, drawing “kolams’, cooking a dish, adding tivo numbers are examples of processes. Pro. cesses are generated by executing algorithms. In this chapter, we will see how algorithms are specified and how elements of a process are abstracted in algorithms. 6.1 Algorithms 3.942 ( algorithm is ‘2° sequence of instructfons to accomplish a task or solve ae pre instruction describes an action When theinstructionsare executed, a process evolves, which accomplishes the intended task or solves the given nee can compare an algorithm to a recipé and the resulting process to cooking. We are interested in executing our algorithms in a computer. A computer can onlyexecute instructions ina programming language. Instructions of a computer are also known as Statements. Therefore, ultimately, algorithms must be expressed 16 Ww action Specification and Abstra | SP! tements of a Progra using sta ngage. . A problem is specified by given inp data, desired output data and a relation between the input and the output data Ay algorithm starts execution with the ‘np data, executes the statements, and finishes execution with the output data, ‘When it finishes execution, the specified relation between the input data and the outpy data should be satisfied. Only then has the G Polya was a Hungarian mathematician. © He made fundamental contributions _ to combinatorics, number theory, numerical analysis and probability theory. He is also noted for his work in heuristics and mathematics education, identifying systematic methods of problem solving to further discovery and invention in mathematics for students and teachers, In "How to Solve It", he suggests the following 7 Steps when solving a8 mathematical problem: 1.’ a Understand the problem, 2. Devise a plan. 3, Carry ot the pn Review AZ Zp Your work BL An algorithm is a step by step Sequence of statements intended to solve a Problem. When executed with input data, it ‘Senerates a computational Process, and ends CHAPTER 6 ¥ # i oe eehn output data, Satistying the specific jon bebween the input dat Lr ght Mand the apn dati, psample 6.1. Add Ovo numbers: Uyak o numbers, we proceed by \ adding the two numbers, then the next Tight most digits together © ight most digits of the rat with carry that resulted from the previous (right) position, and 80 on, ‘The computational process for adding 2586 and 9237 is illustrated in Table 6.1, Gny 1 0 1 0 Number 102 5 8 6 Number 209020307 Sam 118 23 Table 6.1: The process for adding two numbers 6.2 Algorithmic Problems in ‘There are some principles aft” techniques for constructing algorithm usually say that a problem is algorithmic in nature when its solution involves the construction of an algorithi). Some types of problems can be immediately recognized as algorithmic. Example 6.2. Consider the well-known Goat, grass and wolf problem: A farmer wishes to take a goat, a grass bundle and a wolf acrossa river. However, his boat can take only one of them at atime. So several tripsare necessary to across the river. Moreover, the goat should not be left alone with the grass (otherwise, the goat would eat the grass) and the wolf should not be left alone with the goat (otherwise, the wolf would eat the goat), How M7 Can the farmer achieve the tas? Initially, we ‘sstime that all the four are at the sare side of ‘he tiverand finally all the four snust bein the Opposite side. ‘The farmer must be in the boat when crossing the river, A solution consis! of a sequence of instructions indicating, who oor what should cross. ‘Therefore, this is an algorithmic problem, Instructions may be ‘BULLS Let the farmer cross with the wolf. or Let the farmer cross alone. However, some algorithmic problems do not require us to construct algorithms Instead, an algorithm is provided and we are required to prove some ofits properties Example 6.3. Consider The Chameleons of Chromeland problem: On the island of Chromeland there are three different types of chameleons: red chameleons, green chameleons, and blue chameleons. Whenever two chameleons of different colors meet, they both change color to the third color. For which number of red, green and blue chameleons it is possible to arrange ‘a series of meetings that results in all the chameleons displaying the same color? This is an algorithmic problem, because there is an algorithm to arrange meetings between chameleons, Using some properties of the alge initial number of chameleons, the goal is possible, hm, we can find out for which 6.3 Building Blocks of Algorithms oo We construct algorithms using basic building blocks such as| \ I + Data “y" + Variables + Control flow + Functions 6.3.1 Data Algorithms take input — data, process the data, and produce output data, Computers provide instructions to r example, perform operations on dal there are instructions for doing arithmetic operations on numbers, such as add, subtract, multiply and divide. There are different kinds of data such as numbers and text. 6.3.2 Variables Variables are named boxes for storing data. When we do operations on data, we need to store the results in variables. The data stored in a variable is also knownas the value of the variable. We can store a value in a variable or change the value of variable, using an assignment statement. , Computational processes in the real-world have state. As a process evolves, the state changes. How do we represent the state of a process and the change of state, in an algorithm? The state of a process can be represented by a set of variables in an algorithm. The state at any point of execution is simply the values of the variables at that point. As the values of the variables are changed, the state changes. Example 6.4. State: A traffic signal may be in one of the three states: green, amber, or red. The state is changed to allow a smooth flow of traffic. The state may be 18 | represent ar » have one of the three value, which ¢ ven, amber, or red. ed by a single variable sippy iy it 6.3.8 Control flow 4 - it An algorithm is a sequence statements, However, after executing a statement, the next statement to be executed need not be the next statemen, i in the algorithm. The statement to be executed next may depend on the state of the process. Thus, the order in which the statements are executed may differ from the order in which they are written in the algorithm. This order of execution of statements is known as the control flow. ‘There are three important control flow statements to alter the control flow depending on the state. | + In sequential control flow, a sequence of statements are executed one after | another in the same order as they are written, + In alternative control flow, a condition of the state is tested, and if the condition is true, one statement is executed; if the condition is false, an alternative statement is executed, “peeved + In iterative control flow, a condition of the state is tested, and if the condition is true, a statement is executed. The two steps of testing the condition and executing the statement are repeated until the condition becomes false. 6.3.4 Functions Algorithms can become very complex. ‘The variables of an algorithmx dependencies among the varies ys » puild algorithms correctly. In such be too many, Then, it is difficult ations, we break an algorithm into pts: construct each part separately, and then integrate the parts to the complete Algorithm. hing geri? te as Lo the parts of an algorithm are jmown as functions, A function is like a sub algorithm. It takes an input, and produces an output, satisfying a desired input output relation. Example 6.5. Suppose we want Lo calculate the surface area of a cylinder of radius r and height h. A= 2ar + dark We can identify two functions, one for calculating the area of a circle and the other for the circumference of the circle. If we abstract the two functions as circle_ area(r) and circle_circumference("), then cylinder_area(r, h) can be solved as cylinder_area (nh) = 2X circle_area (r) + circle_circunsference (r) X h Algorithm Design Techniques ‘There area few basic principles and techniques for designing algorithms. ‘the first step in problem 1. Specification: solving is to state the problem precisely. fied in terms of the A problem is speci input given and the output desired. ‘the specification must, also state the properties of the given input, and the relation between the input and the output. VS properties is known z i 7 2. Absteactionf A problem can involve a lot of details, Several of these details are unnecessary for solving the problem Onlyafew detailsareessential. Ignoring or hiding unnecessary details and ts essential modeling an entity only b abstraction. “For example, when we represent the state of a process, we select only the variables essential to the problem and ignore inessential details) Ihe a9 3. Composition: An algorithm is composed of assignment and control flow statements. A control flow statement tests @ condition of the state and, depending on the value of the condition, decides the next statement to be executed. 4, Decomposition: We divide the main algorithm into functions. We construct each function independently of the hm and other functions. main main algorit Finally, we algorithm using the functions. When we use the functions, it is enough to know the specification of the function. It is not necessary to know how the construct the function is implemented. 6.5 Specification — ee ‘To solve a problem, first we must state the problem clearly and precisely. A problem isspecified by the given inputand the desired output. To design an algorithm for solving a problem, we should know the properties of the given input and the properties of the desired output. ‘The goal of the algorithm is to estab sh the relation between the input and.the desired output. 9Generation First Generation Perlod 1942 1955 eration Computers Mal Component used size 8 feet x 100 feet watts of power NIAC, EDVAC, UNIVAG) = 4 + Big in size + Consumed More power + Malfunction due 10 overheat » Machine Langua Language ‘ Buage was Used * 3 feet and consumed around 159 Second | Generation 1955- 1964 ® Transistors Smaller comp Generation Generated Less Heat Consumed less power compared to first Seneration Punched cards were used First operating system was developed - Batch Processing and Multiprogramming Operating System Machine language as well as Assembly language was used, ared to First Second Generation Co: mputers IBM 1401, IBM 1620, UNIVAG 1108 + Computers were smaller, faster and more reliable Third 1964 3 é e + Consumed less power Generation | -1975 ° + High Level Languages were Integrated used Circuits (IC) third Generation Computers IBM360 series, Honeywell 6000 series + Smaller and Faster + Microcomputer series such Fourth as IBM and APPLE were 4 i. Generation | 11989) Microprocessor | developed Very Large Scale |* Portable Computers were Integrated Circuits | _im'roduced. (Vist)11080 = till, | | | | |Therefore, there is no need les of the grammar of a e 78 Tanguage. However, even PSeudo code m P ust be rigorous and correct. “tudo code aha is the most widely used ‘ation to Tepresent algorithms, 13" Flowcharts & Flowchart is a diagrammatic notation . Representing algorithms. ‘They show the satel flow of algorithms using diagrams in a stal manner. In flowcharts, Fectangular boxes 5 Present simple statements, diamond-shaped DOXes represent fe ib Control flows during the execution of the algorithm. 4 flowchart is a collection of boxes Containing statements and conditions which ate connected by arrows showing the order in which the boxes are to be executed, 1. A statement is contained in a rectangular box with a/single outgoing arrowwhich Points to the box to be executed next, A condition is contained in a diamond- shaped box with two outgoing arrows, labeled true and false. The true arrow points to the box to be executed next if the condition is true, and the false arrow Points to the box to be executed next if the condition is false. false tt conditions, and arrows describe lelogram boxes represent inputs given and outputs produced, Inputs / (Outputs) . Special boxes marked Start and the End are used to indicate the start and the end ofan execution: ak a7 eli Start End} } ‘The flowchart of an algorithm to compute the quotient and remainder after dividing an integer A by another integer B is shown in Figure 7.1, illustrating the different boxes such as input, output, condition, and assignment, and the control flow between the boxes. The algorithm is explained in Example 74. Figure 7.1: Flowchart for integer division Flowcharts also have disadvantages. (1) Flowcharts are less compact than representation of algorithms in 131 | | | i] i i i | } i | |programming language or pseudo code. (2) They obscure the basic hierarchical structure of the algorithms. (3) Alternative statements and loops are disciplined control flow structures. Flowcharts do not restrict us to disciplined control flow structures.