acaa9c23f2f23aaa58b06f38e0d0c908.pdf

By: Hussain K  ALGORITHM DESIGN Algorithm design is the process of creating step-by-step instructions to solve a specific problem or perform a particular task. It involves breaking down a problem into smaller, manageable parts and designing efficient and effective...

By: Hussain K  ALGORITHM DESIGN Algorithm design is the process of creating step-by-step instructions to solve a specific problem or perform a particular task. It involves breaking down a problem into smaller, manageable parts and designing efficient and effective solutions. Problem solving, on the other hand, refers to the ability to find solutions to various problems, often using algorithms as a systematic approach. Computers follow algorithms. Programs are written as a series of instructions that the computer then follows. Algorithms for software are millions of lines long, and they have to make use of specific instructions to tell the processor what to do. A computer can only run machine code, that is binary. If you enter a command into the computer, this has to be converted into binary for the processor to execute (run) it. CONT’ Can you work out what this is designed to do? An algorithm is a solution to an existing problem that is written step-by-step. Algorithms can either be represented as flowcharts or pseudocodes. Things you should notice in order to understand the purpose of a given algorithm: Look at what is being taken as input T his algorithm takes in the length of three sides as inputs, which indicates the algorithm deals with a shape. Look at the output messages This algorithm talks about triangles, and triangles have three sides, so the shape in question is a triangle. Look at what the algorithm does with the input This algorithm is checking the value of the three sides. Based on comparing the values for each side, it determines what type of triangle it is.  IDENTIFYING ERRORS IN AN ALGORITHM A computer is a system that faithfully follows any instructions it An algorithm for the above problem could be written as is given, but that does not mean it will always give the correct the following pseudocode: results. Errors in algorithms can take many forms, and even with these errors present the algorithm can still produce an output, but that output may not be the one intended, and it may not even be immediately clear that it is wrong. This is why error checking is such an essential part of all algorithm design and coding. One of the most important parts of designing algorithms is not just how to write them, but how to make sure they work as intended. Some of the methods we have seen so far include: Identifying inputs and outputs Identifying processes (and decisions) Checking if the inputs are sensible and correct (validation and verification) Observing when a loop starts and ends Using this algorithm a student who scored 97 received a ‘C’ grade. Can Tracing the algorithm using a trace table you see why? Can you see the flaw in the logic? The methods above should ensure your final algorithm performs Remember that algorithms, just like programs, are executed line-by-line. as intended, but there is also the unpredictable element of The control first goes to the statement: human error, and this tends to produce unintended or unusable outputs from your algorithms. IF Score > 50 THEN Grade ← C Example: a simple grade calculator, can be defined as follows: The score is 97, which satisfies the first condition right away, so the Students who achieve more than 50 get a ‘C’ grade, more than computer would look no further in the code! It simply displays ‘C’. 70 get a ‘B’ grade, and more than 90 get an ‘A’ grade. How would you propose to fix the above flaw? As a program is developed, a series of processes are followed to find and fix errors, for example, using trace tables. Errors that are introduced at the design stage can filter through to the development stage if they are not identified early on. This could result in the product needing to be redeveloped, which could be very costly and would take extra time. Therefore, it is important to find and fix any errors as early as possible in the process. Errors can be categorized in three ways: ❖ Logic errors: The program will run but does not output what is expected; an example of a logic error is the inclusion of an incorrect conditional operator. ❖ Syntax errors: Errors in the program code that stop the program from running; an example of a syntax error is where the code has been typed incorrectly, for instance, missing brackets, colons or indentation or incorrect spelling, to name a few. ❖ Runtime errors: Errors that occur while the program is running as the instructions cannot be completed; an example of a runtime error is where the variable name has not been added correctly in one aspect of the program - it would not generate an error until it is used. Testing an algorithm before it is developed into the program code can help to find and fix any errors early on. Trace tables can also be used to find any logic errors in an algorithm. A logic error does not stop the program from running, but the program doesn't do what you expect it to. One area that can cause a logic error is the use of conditional operators in conditional statements. A program takes shape after a lot of research, analysis and designing. The word ‘life cycle’ is representative of the stages that are done in order to create a new product. This product, in our case, is a program. The program development life cycle (PDLC) is a simple representation of the steps that are followed in developing a program. This program may be anything from a smartphone app to a website. Each step in the process is decomposed into sub-steps: The life cycle process follows a phase by phase approach, starting with understanding what the program must solve (analysis), working out a draft of how the program should behave (design), then actually writing the program (coding) and finally checking to see if it works as intended (testing). Often, these phases are not followed in a linear fashion, i.e., one after another, but is iterative (repetitive) in nature. While designing we may want to go back and analyze some other part of the program or while testing we may want to go back and change an aspect of our code. This first stage involves looking at the problem and the system that is needed. The problem is explored, and the requirements of the program are identified.Before any problem can be solved, it needs to be clearly defined and set out so anyone working on the solution understands what is needed. This is called the ‘requirements specification’ for the program. The analysis stage uses abstraction and decomposition tools to identify exactly what is required from the program. Decomposition means breaking down a complex problem into smaller. manageable parts which are easier 1o solve. This comprises the following steps: Identify the main problem Identify the component parts of inputs, processes, outputs and storage List the main sub-problems. sub-systems, functions or tasks Break these down into smaller sub-problems or sub-tasks which can then be completed separately Abstraction is the process of selecting the information in a problem and focusing only on the important parts of that information. During abstraction, any detail that is irrelevant to the problem is ignored. In the design phase, the developers of the program will continue the decomposition phase from the analysis and begin to draw up visuals of the end product. This will include structure diagrams that help to visualize the end goal. The coding required to make the visual representations happen will be started at this point. The developers will create flowcharts that show how a program’s decomposed parts will run, including any decisions or inputs that are needed. The programmers will then begin to develop pseudocode that enables the complex problems and instructions to be read in plain English. Pseudocode is an excellent way to check that the instructions make sense prior to the coding process. Structure diagrams are hierarchical, showing how a computer system solution can be divided into sub- systems with each level giving a more detailed breakdown. If necessary, each sub-system can be further divided. A structure diagram is developed by decomposing a program into its subprograms. The diagram has the name of the program at the top, and below this its subprograms. Each subprogram can be split down further as well if required. Coding and iterative testing Once you have decomposed your problem into subproblems, and you have designed the algorithms using flowcharts and/or pseudocode then you can start writing the program in your chosen programming language. This is often referred to as coding. This is sometimes known as the implementation stage. The programmers work on the design modules, such as: Input, Output, and Processes, and write the code to make each part of the program functional. The programming is then linked together as a complete solution. A testing strategy is planned by analysts and the test plan will comprise details of all the programs to be tested. Testing This will also include some iterative testing. This is testing that is carried out while the program is being developed, for example, if you write the program code for one of the subproblems, then you will test it with a range of different data to make sure it is fully working before moving onto the next step. Testing every part of the programming requires a test strategy. First, the entire system is divided into small sections that are tested for input, output and validation rules. Test data is used for all of the tests to be carried out. Testing each part of the code individually is known as unit testing, and integration testing is used when this code is all combined to form a program. The testing team reports any errors to the programmers and the testing is repeated until there are no errors found in the system.  IMPORTANCE OF TEST DATA Just as it can take a team of people to write a program, there is also a specific team of people who are in charge of testing. With the various types of testing involved, a number of teams have the job of making sure that the product works as intended. Test data should include Normal :typical data, using examples of typical data that the program is designed to handle Extreme data:ie the largest and smallest acceptable value e.g.. 1-50. Boundary: data includes both ends of the allowed range (e g 1-50) s well as invalid data that Should not be allowed, just outside this range. For example, if a range of 0 10 50 needs to be Tested, then the boundary data would be 1. 0, 50, 51. Abnormal: or erroneous data, i.e.. Data of the wrong type, for example non-numeric characters in A numeric field. As an example, imagine you are testing data for people’s age between 21 and 74 inclusive. Normal data would be any age between 21 and 74. Boundary data would be 21 and 74 accepted, 20 and 75 rejected. Extreme data could be ~21–24 and ~71–74. Abnormal data would be 20 or less, 75 or greater, or any data that is not an age. Any problem that uses a computer system for its solution Example 1: An alarm app needs to be decomposed into its component parts. The For example, the alarm app can be component parts of any computer system are: decomposed into: ▪ Inputs – time to set the alarm, remove a ❖ inputs – the data used by the system that needs to be previously set alarm time, switch an entered while the system is active alarm off, press snooze button ▪ Processes – continuously check if the ❖ processes – the tasks that need to be performed using current time matches an alarm time that the input data and any other previously stored data has been set, storage and removal of alarm times, management of snooze ❖ outputs – information that needs to be displayed or ▪ Outputs – continuous sound/tune (at printed for the users of the system alarm time or after snooze time expired) ▪ Storage – time(s) for alarms set. ❖ storage – data that needs to be stored in files on an appropriate medium for use in the future. EXAMPLE 3: CHECKING FOR THE ALARM TIME Have a look at a flowchart below showing how the checking for the alarm time sub-system works COMPUTER SYSTEM A computer system is made up of software, data, hardware, communications and people; each computer system can be divided up into a set of sub-systems. Each sub-system can be further divided into sub-systems and so on until each sub-system just performs a single action. Computer systems can be very large, very small or any size in between; most people interact with many different computer systems during their daily life without realising it. For example, when you wake up in the morning, you might use an app on your smartphone for your alarm, then you might check the weather forecast on your computer before driving to work. The alarm program is a very small computer system but when you check the weather forecast, you obtain the information you need from one of the largest computer systems in the world.  THE COMPUTER SYSTEM AND ITS SUB-SYSTEMS In order to understand how a computer system is built up and how it works it is often divided up into sub-systems. This division is shown using top-down design to produce structure diagrams that demonstrate the modular construction of the system. Each sub-system can be developed by a programmer as a sub-routine. How each sub-routine works can be shown by using flowcharts or pseudocode. Top-down design is the decomposition of a computer system into a set of subsystems, then breaking each sub-system down into a set of smaller sub-systems, until each sub-system just performs a single action. This is an effective way of designing a computer system to provide a solution to a problem, since each part of the problem is broken down into smaller more manageable problems. The process of breaking down into smaller sub- systems is called stepwise refinement. This structured approach works for the development of both large and small computer systems. When larger computer systems are being developed this means that several programmers can work independently to develop and test different sub-systems for the same system at the same time. This reduces the development and testing time. SUB-ROUTINE A sub-routine is a self-contained algorithm. It has an identifier, which is the name of the sub-routine. By using this identifier you can call the sub-routine from other code. Calling the sub-routine means that: the algorithm in the main code stops where it is the sub-routine runs at the end of the sub-routine, the algorithm returns to where it stopped in the main code. This is used to start the sub-routine and to call it from another flowchart. The identifier (name) of the sub-routine is written in the shape. The sub-routine has one arrow coming from it in the actual sub-routine. Where it is used to call the sub-routine, it will have one arrow going in and one arrow going out. A sub-routine needs an identifier (name). This could be anything! However, identifiers should be appropriate and meaningful. For example, a bad name for a sub-routine that outputs a story is maths Questions. The identifier can be two words in a flowchart, but in these examples, we will use programming-style identifiers. These will be one word ('addNumbers' instead of 'add numbers'). They will also have brackets () after the name: addNumbers(). This is because these brackets will be needed when programming sub-routines, and it makes it clear that the identifier refers to a sub-routine instead of anything else.  METHODS USED TO DESIGN AND CONSTRUCT A SOLUTION TO A PROBLEM Solutions to problems need to be designed and developed rigorously. The use of formal methods enables the process to be clearly shown for others to understand the proposed solution. The following methods need to be used: ❖ Structure diagrams ❖ Flowcharts ❖ Pseudocode  STRUCTURE DIAGRAMS Structure diagrams are another way of representing data flow in diagram form. They are different from flowcharts as they display the different levels of detail within a set of decomposed problems. The problems are sometimes broken down into smaller problems, or sub-systems, and they are represented in a tree diagram, with the big picture at the top. Structure diagrams can be used to show top- down design in a diagrammatic form. Structure diagrams are hierarchical, showing how a computer system solution can be divided into sub-systems with each level giving a more detailed breakdown. If necessary, each sub- system can be further divided. Basic structure diagram Flowcharts A flowchart is a diagrammatic representation of an algorithm. A flowchart shows diagrammatically the steps required to complete a task and the order that they are to be performed. These steps, together with the order, are called an algorithm. Flowcharts are an effective way to communicate how the algorithm that makes up a system or sub-system works. Flowcharts are drawn using standard flowchart symbols. A flowchart shows each step of a process, in the order that each step is performed. Each shape has one statement within it, for example, input number, or add 1 to x. The shapes are joined with arrows to show the direction of flow and the content inside each box can be written as words, or as pseudocode statements. Advantages of using flowcharts Disadvantages of using flowcharts The sequence of steps can easily be seen They can take a lot of time to produce Changes to the algorithm mean sections of the Paths through the algorithm can be easily flowchart have to be re-drawn. This can take a followed lot of time The logic of the algorithm (sequence, selection Large flowcharts can become extremely and iteration) can often be understood better complicated and difficult to follow when represented visually Flowcharts can form part of the documentation for a Pseudocode Data Types: Pseudocode is a text-based method of describing an algorithm. The word In order for a computer to store data, ‘pseudo’ means ‘false’ – and ‘pseudocode’ means exactly that: ‘false code’. different types of data are given different Pseudocode resembles actual code but cannot be understood by a computer. types. Data can be stored as numbers or It is written in a human-readable format that makes more sense to a non- characters. programmer than an actual program would. Since this is closer to real code, Integer- A integer is a whole number programmers find it easy to write code after a design process that uses that can be used in mathematical pseudocode. And because there is less interpretation needed, pseudocode can make handing over work between team members smoother operators. Which basically means 1,2,3 THE MAIN CONSTRUCTS OF PSEUDOCODE and so on. At its core pseudocode is the ability to represent six programming constructs Real- A Real Number is a positive or a (always written in uppercase): SEQUENCE, CASE, WHILE, REPEAT-UNTIL, negative numbers with a fractional part FOR, and IF-THEN-ELSE. These constructs — also called keywords —are which also can be used with operators. used to describe the control flow of the algorithm. Char- A variable or constant which is a 1.SEQUENCE represents linear tasks sequentially performed one after the single character.(Also it makes sure other. someone enters something) 2.WHILE a loop with a condition at its beginning. 3.REPEAT-UNTIL a loop with a condition at the bottom. String- A variable or constant which can 4.FOR another way of looping. have several characters in length. 5.IF-THEN-ELSE a conditional statement changing the flow of the algorithm. Boolean- Boolean has 2 values, True and 6.CASE the generalization form of IF-THEN-ELSE. False otherwise known as 1 and 0 Note that:Structure diagrams, flowcharts and pseudocode are all design representations for program code, and can be used interchangeably or all together Note the following points in the pseudocode used in this course: Comments start with two forward stashes / / and continue to the end of the line identifiers contain only letters and digits D-9 and start with an uppercase letter A variable may be declared with a statement such as DECLARE Start Number : INTEGER DECLARE Total : REAL DECLARE Valid Password: BOOLEAN A constant may be declared with a statement such as CONSTANT VAT  0. 2 The assignment operator Is  ItemCode ← USERINPUT Python EXAMPLE StockLevel ← USERINPUT ReorderLevel ← USERINPUT ItemCode = input("enter item code") IF StockLevel ≤ ReorderLevel THEN StockLevel = int(input("enter stock level")) ReOrder() ReorderLevel = int(input("enter reorder level")) OUTPUT 'Stock ordered' if StockLevel B means ‘A is greater than B’ comparisons can be simple or more complicated, for example: IF ((Height > 1) OR (Weight > 20)) AND (Age < 70) AND (Age > 5) THEN OUTPUT "You can ride" ELSE OUTPUT "Too small, too young or too old" ENDIF Have a look at the algorithm below that checks if a percentage mark is valid and whether it is a pass or a fail. This makes use of two IF statements; the second IF statement is part of the first ELSE path. This is called a nested IF. OUTPUT "Please enter a mark " INPUT Percentage Mark IF Percentage Mark < 0 OR PercentageMark > 100 A rejected THEN percentage mark OUTPUT "Invalid Mark“ must be either less than zero or ELSE greater than 100 IF PercentageMark > 49 This is a nested IF THEN statement, shown clearly by OUTPUT "Pass" the use of a second level of ELSE indentation. The percentage OUTPUT "Fail" mark is only tested if it is in ENDIF the correct range ENDIF CASE OF … OTHERWISE … ENDCASE For a CASE statement the value of the variable decides the path to be taken.Several values are usually specified. OTHERWISE is the path taken for all other values. The end of the statement is shown by ENDCASE. the algorithm below that specifies what happens if the value of Choice is 1, 2, 3 or 4. CASE OF Choice 1 : Answer ← Num1 + Num2 2 : Answer ← Num1 - Num2 3 : Answer ← Num1 * Num2 4 : Answer ← Num1 / Num2 OTHERWISE OUTPUT "Please enter a valid choice" ENDCASE THE PSEUDOCODE FOR ITERATION When some actions performed as part of an algorithm need repeating this is called iteration. Loop structures are used to perform the iteration. Pseudocode includes these three different types of loop structure: A set number of repetitions: FOR … TO … NEXT A repetition, where the number of repeats is not known, that is completed at least once: REPEAT … UNTIL A repetition, where the number of repeats is not known, that may never be completed: WHILE … DO … ENDWHILE A WHILE … DO … All types of loops can all perform the same task, for example displaying ten ENDWHILE loop stars: A REPEAT … FOR Counter ← 1 TO 10 UNTIL loop OUTPUT "*“ NEXT Counter Counter ← 0 Counter ← 0 REPEAT WHILE Counter < 10 DO OUTPUT "*" OUTPUT "*" AFOR… NEXT Counter ← Counter + 1 Counter ← Counter + 1 loop UNTIL Counter > 9 ENDWHILE FOR … TO … NEXT loops A variable is set up, with a start value and an end value, this variable is incremented in steps of one until the end value is reached and the iteration finishes. The variable can be used within the loop so long as its value is not changed. This type of loop is very useful for reading values into lists with a known length. FOR Counter ← 1 TO 10 Counter starts at 1 and OUTPUT "Enter Name of Student “ finishes at 10 INPUT StudentName[Counter] NEXT Array items Student Name to Student Name have data input  THE PSEUDOCODE FOR INPUT AND OUTPUT STATEMENTS INPUT and OUTPUT are used for the entry of data and display of information. Sometimes READ can be used instead of INPUT but this is usually used for reading from files. Also, PRINT can be used instead of OUTPUT if a hard copy is required. INPUT is used for data entry; it is usually followed by a variable where the data input is stored, for example: INPUT Name INPUT StudentMark OUTPUT is used to display information either on a screen or printed on paper; it is usually followed by a single value that is a string or a variable, or a list of values separated by commas, for example: OUTPUT Name OUTPUT "Your name is ", Name OUTPUT Name1, "Ali", Name3 EXAMPLE 1: OUTPUT AN ALARM SOUND The purpose of the following pseudocode is to output the alarm sound at the appropriate time. The processes are: waiting 10 seconds, getting the current time, checking the current time with the alarm time, and outputting the alarm sound when the times match. Waits for 10 REPEAT seconds Wait (10) Get (Time) Get current time UNTIL Time = Alarm _ Time from the system clock OUTPUT AlarmSound