Logicical Problem Solving Notes_b3e658ee5d173e434449aae9f46c40cd.pdf

Information Systems & Technology University of KwaZulu-Natal ISTN103 LOGICAL PROBLEM SOLVING notes 1 Table of Contents Section 1: Introduction.........................................................................................

Information Systems & Technology University of KwaZulu-Natal ISTN103 LOGICAL PROBLEM SOLVING notes 1 Table of Contents Section 1: Introduction................................................................................................................................................. 4 Section 2: Terms and Concepts..................................................................................................................................... 4 Computer System...................................................................................................................................................... 4 Computer Hardware.............................................................................................................................................. 4 Computer Software............................................................................................................................................... 5 Significant Features of Computer System.............................................................................................................. 6 Natural Language....................................................................................................................................................... 6 Computer Languages................................................................................................................................................. 6 Symbolic/Assembly Languages.............................................................................................................................. 6 Machine Language................................................................................................................................................. 7 High-level Language / Programming Language..................................................................................................... 7 Syntax..................................................................................................................................................................... 7 Elements of a Programming Language.................................................................................................................. 7 Compilers and Interpreters.................................................................................................................................... 8 Machine Code, Source Code, and Object Code..................................................................................................... 8 GIGO (Garbage In Garbage Out)............................................................................................................................ 9 Section 3: The Programming Process and Problem Solving Process............................................................................ 9 Phase 1: Define the Problem.................................................................................................................................... 9 Phase 2: Outline the Solution................................................................................................................................... 9 Phase 3: Develop the outline from Phase 2 into an algorithm (flowchart or pseudocode)..................................... 9 Phase 4: Test the algorithm or flowchart............................................................................................................... 10 Phase 5: Code the algorithm/flowchart and run the program............................................................................... 10 Phase 6: Document and maintain the program...................................................................................................... 10 Section 4: Algorithm, Pseudocode, and Flowchart..................................................................................................... 10 Algorithm................................................................................................................................................................. 10 Importance of an Algorithm................................................................................................................................ 11 Pseudocode.......................................................................................................................................................... 11 Flowchart............................................................................................................................................................. 12 Elements of a flowchart....................................................................................................................................... 12 Flow of Control.................................................................................................................................................... 14 Verifying algorithms............................................................................................................................................. 17 Algorithm in summary............................................................................................................................................. 17 Coding...................................................................................................................................................................... 17 Flowchart Examples................................................................................................................................................. 18 Example 1: Temperature information................................................................................................................ 18 Example 2: Determining Pass or Fail................................................................................................................... 18 Example 3: Making popcorn............................................................................................................................... 18 2  Example 4: Age Restriction................................................................................................................................. 19 Example 5: Example from the Internet – Tech Support...................................................................................... 20 How to draw flowcharts.......................................................................................................................................... 20 The general idea.................................................................................................................................................. 20 Example 6: Find the largest of three numbers that are provided as input......................................................... 21 Example 7: Grocery shopping – Paying for items............................................................................................... 22 Example 8.1: Student Acceptance System.......................................................................................................... 24 Example 8.2: Student Acceptance System with criteria..................................................................................... 24 Example 8.3: Student Acceptance System with criteria and limited space........................................................ 26 Section 5: Exercises..................................................................................................................................................... 29 References................................................................................................................................................................... 30 Acknowledgements..................................................................................................................................................... 30 3 Section 1: Introduction The topic LOGICAL PROBLEM SOLVING is designed to introduce students to the concept of Programming Process and Steps for Problem Solving, Algorithms, and Representation of Algorithms (Flowcharts, and Pseudocodes). The topic also summarises the general terms and concepts related to Information Systems, computer programs and logical problem solving in general that students learnt in ISTN101. Nowadays, computers (Desktops, Laptops, Tablets, Game Consoles, Smartphones, and Workstations) are all around us. We use them for doing various tasks in a faster, automated and more accurate manner. For example, using a desktop computer or laptop or smartphone, we can request Uber taxi and Bolt taxi online, we can we book bus tickets online, we can communicate via WhatsApp online, and we can learn online. We can create invoices, quotations, schedules and budgets using Spreadsheets. We can create, edit and format documents using Word Processors. We usually use the term computerisation to indicate the use of computer to develop software in order to automate any routine human task efficiently. Computers are used for solving various day-to-day problems and thus problem solving is an essential skill that an Information Systems and Technology (IS&T) student should know. It is pertinent to mention that computers themselves cannot solve a problem – they need to be programmed with instructions to solve problems. Precise step- by-step instructions should be given by us to solve the problem. Thus, the success of a computer in solving a problem depends on how correctly and precisely we define the problem, outline and design a solution (algorithm), and implement the solution (program) using a programming language. Thus, Problem Solving is the process of identifying a problem, developing an algorithm for the identified problem and finally implementing the algorithm to develop a computer program. Section 2: Terms and Concepts This section covers general terms and concepts related to Information Systems, computer programs and logical problem solving in general. Computer System A computer is a programmable machine capable to perform arithmetic and logical operations automatically and sequentially. It is also known as a data processor, as it can store, process, and retrieve data as per the wish of the user. Data processing involves the following four activities: Input of data Manipulation/processing of data Giving output (i.e. management of the output result) Storing the output result In a computer system, data is arranged orderly and systematically. A computer is a system made of two major components: hardware and software. The computer hardware is the physical equipment. The software is the collection of programs (instructions) that allow the hardware to do its job. Computer Hardware The hardware component of the computer system consists of six parts: input devices, central processing unit (CPU), memory, storage, output devices, and auxiliary devices. The input device is usually a keyboard where programs and data are entered into the computers. Examples of other input devices include a mouse, a pen or stylus, a touch screen, or an audio input unit. The central processing unit (CPU) is responsible for executing instructions such as arithmetic calculations, comparisons among data, and movement of data inside the system. Today’s computers may have one, two, or more CPUs. Primary memory, also known as main memory, is a place where the programs and data are stored temporarily during processing. The data in primary storage are erased when we turn off a personal computer or when we log off from a time-sharing system. 4 The output device is usually a monitor or a printer to show output. If the output is shown on the monitor, we say we have a soft copy. If it is printed on the printer, we say we have a hard copy. Storage, also known as secondary storage is the place where the programs and data are stored permanently. When we turn off the computer, programs and data remain in the secondary storage, ready for the next time we need them. Computer Software Software, often used interchangeably with the term program, is set of instructions for solving a particular problem. Computer software is divided in to two broad categories: system software and application software. System software manages the computer resources. It provides the interface between the hardware and the users. Application software, on the other hand is directly responsible for helping users solve their problems. Systems Software is a set of programs which allows a person to take advantage of the hardware capabilities of a computer. System software consists of programs that manage the hardware resources of a computer and perform required information processing tasks. These programs are divided into three classes: the operating system, system support, and system development. The operating system provides services such as a user interface, file and database access, and interfaces to communication systems such as Internet protocols. The primary purpose of this software is to keep the system operating in an efficient manner while allowing the users access to the system. System support software provides system utilities and other operating services. Examples of system utilities are anti-virus programs, file compressing programs, and disk format programs. Operating services consists of programs that provide performance statistics for the operational staff and security monitors to protect the system and data. The last system software category, system development software, includes the language translators that convert programs into machine language for execution, debugging tools to ensure that the programs are error free and computer–assisted software engineering (CASE) systems. Application Software is a set of programs that can be used to solve problems. Application software is broken in to two classes: general-purpose software and application–specific software. General purpose software is purchased from a software developer and can be used for more than one application. Examples of general purpose software include word processors, database management systems, and computer aided design systems. They are labelled general purpose because they can solve a variety of user computing problems. Application–specific software can be used only for its intended purpose. A general ledger system used by accountants and a material requirements planning system used by a manufacturing organization are examples of application-specific software. They can be used only for the task for which they were designed, they cannot be used for other generalized tasks. The relationship between system and application software is shown in the figure below. The inner core is hardware. The user is represented by the out layer. To work with the system, the typical user uses some form of application software. The application software in turn interacts with the operating system, which is a part of the system software layer. The system software provides the direct interaction with the hard ware. The user may interact directly with the operating system (e.g. Operating System) when necessary. Relationship between system and application software User 5 Significant Features of Computer System The following are the salient features of a Computer System: Automation − The operating system of a computer system is automatic, as no human intervention is required; simply you need to give the command and then it will do the work automatically. Speed − Depending upon the power of the computer, it can perform, it can take Millions of instructions per second. Storage − A computer system can store an enormous quantity of data in different format. The storage capacity of a computer system is normally expressed in terms of Kilobytes (KB), Megabytes (MB), Gigabytes (GB), or Terabytes (TB). Accuracy − The accuracy of a computer system is very high. Versatility − A computer system is capable of performing a wide range of tasks. Diligence − A computer neither gets tired nor loses concentration. Reliability − As a computer system always gives accurate result; therefore, its reliability is very high. Vast memory − A computer system can have a wide range of memory which can recall the desired data at any point of time. Natural Language The language that humans understand and use for communication is known as natural language. An example of natural language is English, isiZulu, isXhosa, Portuguese, etc. Computers do not understand natural language. Computer Languages To write a program for a computer, we must use a computer language. Over the years computer languages have evolved from machine languages to high-level languages. 1940’s: Machine level Languages 1950’s: Symbolic Languages 1960’s – up to the present time: High-Level Languages Symbolic/Assembly Languages The early programming languages simply mirror to the machine languages using symbols of mnemonics to represent the various machine language instructions because they used symbols, these languages were known as symbolic languages. Computer does not understand symbolic language it must be translated to the machine language. A special program called assembler translates symbolic code into machine language. Because symbolic languages had to be assembled into machine language they soon became known as assembly languages. 6 Machine Language Machine language is the language that a computer uses and understands – i.e. the only language understood by computer hardware is machine language. In the earliest days of computers, the only programming languages available were machine languages. Each computer has its own machine language, which is made of streams of 0’s and 1’s. Instructions in machine language must be in streams of 0’s and 1’s because the internal circuits of a computer are made of switches transistors and other electronic devices that can be in one of two states: off or on. The off state is represented by 0, the on state is represented by 1. High-level Language / Programming Language Working with symbolic languages was very tedious because each machine instruction has to be individually coded. The desire to improve programmer efficiency and to change the focus from the computer to the problem being solved led to the development of high-level languages. High level languages share one thing with symbolic languages; they must be converted into machine language. The process of converting them is known as compilation. Programmers find machine code difficult to learn, program in and debug. As a result, the majority of programmers write programs in high-level programming languages. These languages are close to natural language - the spoken and written language of humans. For example, Python uses 'print', ‘if’, 'input' and 'while' statements - all words from the English language - to form instructions. In fact, instructions often look like abbreviated English sentences. High-level Language / Programming Language is a structured, precise, unambiguous language that can be understood by both the computer and humans. High-level languages, like Visual Basic, JavaScript, C#, C++, Python, JAVA, etc., are very near to English. It makes programming process relatively easy. However, program code must be translated into machine language before execution. This translation process is conducted by either a compiler or an interpreter. High level languages are portable to many different computers, allowing the programmer to concentrate on the application problem at hand rather than the intricacies of the computer. High-level languages are designed to relieve the programmer from the details of the assembly language and machine language. Syntax Syntax refers to the set of rules and grammar that govern the formulation of the statements in the programming language, such as spellings, order of words, punctuation, etc. Computers are machines that understand what you type, only if you type it in the exact form that the computer expects. The expected form is called the syntax. Each programming language defines its own syntactical rules that control which words the computer understands, which combinations of words are meaningful, and what punctuation is necessary. An example of syntax in Visual Basic programming language would be Dim variable1, variable2, variable3 as Integer. This syntax simply means declaring three variables as of ‘Integer’ data type – i.e. setting aside an appropriate dimension of memory to store the three variables. Elements of a Programming Language Natural Languages also known as Human Interface Languages (like English, isiZulu, French, Arabic, etc.), are made of several elements like verbs, nouns, adjectives, adverbs, propositions, and conjunctions, etc. Similar to Human Interface Languages, computer programming languages are also made of several fundamental elements. These 7 fundamental elements include: Data Types, Variables, Keywords, Basic Operators, Decision Making, Loops, Classes, Objects, Functions, Controls, Events, Arrays, Procedures, Modules, Integrated Development Environment (IDE), etc. You will learn some of these elements in another ISTN103 topic called Programming in Visual Basic. Compilers and Interpreters A computer cannot understand the spoken or written language that we humans use in our day to day conversations. It is very difficult for us as humans to understand the binary language that the computer uses to do its tasks. If we want to instruct the computer to do a task, it is necessary for us to write instructions in some specially defined language (e.g. JavaScript, VBScript, Java, Python, C++) which we can understand, then have that very precise language converted into the very structured language that the computer can understand. This is the job of the compiler. The compiler works by translating the entire body of code that humans write into machine language. The program is then executed thereafter, provided that there are no errors with the code. An alternative to the compiler is an interpreter. An interpreter is a computer program that compiles and executes (interprets) another computer program on-the-fly (line by line). Some differences between compilers and interpreters are outlined in the table below: Differences between Compilers and Interpreters (Clearn.com, 2014) No Compiler Interpreter 1 Uses the entire program as input Input is a single instruction at a time Conditional Control Statements (e.g. “if…then” 2 Conditional Control Statements execute slower statements) execute faster More memory is required as entire object code for Less memory required since the interpreter only 3 the whole program is generated works on one line at a time Errors are displayed for every instruction interpreted 4 Errors are displayed after entire program is checked (if any) An interpreter has a number of advantages over a compiler, including: It can be tailored to a specific programming language, making it simpler to implement and more compact. It allows program implementation to be independent of the characteristics of the host CPU. The main disadvantage of interpreters is that when a program is interpreted, it runs slower than if it had been compiled. The difference in speed could be tiny or great; often an order of magnitude and sometimes more. Machine Code, Source Code, and Object Code Machine Code: machine languages are very close to the hardware. Every computer has its machine language. Machine language programs are made up of series of binary pattern (e.g. 110110). It represents the simple operations which should be performed by the computer. Machine language programs are executable so that they can be run directly. Source Code is the term given to a set of instructions that are written in human readable programming language. It refers to programming statements and instructions that are written by the developer. Source code is what a programmer writes, but it is not directly executable by the computer. Source code must be translated into machine 8 code before a computer can understand and execute it. It must be converted into machine language by compilers, or interpreter. Object Code: On compilation of source code, the machine code generated for different processors like Intel, AMD, an ARM is different. To make code portable, the source code is first converted to Object Code. It is an intermediary code (similar to machine code) that no processor will understand. At run time, the object code is converted to the machine code of the underlying platform. GIGO (Garbage In Garbage Out) The correctness of the output that a computer gives depends upon the correctness of input provided. In the field of computer science or information and communications technology, GIGO refers to the fact that computers, since they operate by logical processes, will unquestioningly process unintended, even nonsensical, input data (“garbage in”) and produce undesired, often nonsensical, output (“garbage out”). For example, if a program asks for an integer and you enter a string, you may get an unexpected result. Section 3: The Programming Process and Problem Solving Process As described in Section 2, a program is a set of instructions that enables a computer to perform some task or a set of tasks. The complexity of these tasks vary, ranging from adding and subtracting numbers, determining a company’s monthly expenses, solving scientific theories or even playing video games and conducting simulations. In order to develop a program that meets the requirements specified, a process is usually performed to allow you to create your program easily and according to the specifications given to you. The last thing you want to do is spend days or even months designing your program only to realise that it does nothing or does not perform the tasks required. There are several processes followed in industry, some of which are covered at ISTN 2nd year, 3rd year and honours levels. For this Logic section, a simple programming process is described below: Phase 1: Define the Problem A problem that needs to be solved using a program should be broken down into three components: a) The input – What you will enter into the program. b) The output – What answers your program should be able to provide. c) The processing – What formulae, calculations, comparison and/or steps should be taken to convert the input into output. Phase 2: Outline the Solution In this phase, we determine what is needed in order to provide an answer to the problem. This usually involves: a) Determining the major processing steps involved b) The subtasks (if any) c) The User Interface – What will the system look like and how will it interact with the user? d) The major control structures (variables, command statements, repetition loops etc.) e) The logic – How the program moves from one instruction to another in a correct and organised manner Phase 3: Develop the outline from Phase 2 into an algorithm (flowchart or pseudocode) An algorithm is a set of precise steps that exactly describes the tasks to be performed and the order in which they should be carried out. An algorithm can also be thought of as a recipe which the programmer will instruct the computer to follow. Using the outline in Phase 2, develop a logical flow of steps from the beginning of the process/task to the end. Flowcharts are often used to record steps of an algorithm and will be covered in more detail in the next section. 9 Phase 4: Test the algorithm or flowchart Once you have developed your algorithm and/or flowchart, test to ensure that you have covered all necessary steps in the process/task. Often, Sample or test data (input) can be used to check what the algorithm will do and if the output is correct, then the program will probably work. If it does not work, the algorithm designer must try to find the problem and fix it. Common problems include an incorrect formula, missing steps in the algorithm and incorrect flow in the logic. Phase 5: Code the algorithm/flowchart and run the program The programmer chooses his/her preferred programming language and converts the algorithm/flowchart into a program, being aware of possible syntax errors and programming language limitations. Once the program has been typed out, the programmer checks for any errors and runs the program. If any bugs or errors are found, they need to be removed. Phase 6: Document and maintain the program This is an ongoing part of the program design and implementation process. Documentation is important as it would allow other programmers and analysts to understand the objectives of the program, how it works as well as how to run the program. Documentation will allow easier maintenance and upgrading of systems in the event that the original designer is unavailable. Section 4: Algorithm, Pseudocode, and Flowchart This section expands on Phase 3 of the programming process described in Section 3 by covering the concept of Algorithm, Pseudocode and Flowchart. Algorithm From programming point of view, an Algorithm is a set of exact steps which when followed, solve the problem or accomplish the required task. An algorithm is a step-by-step procedure to resolve any problem. An algorithm is an effective method expressed as a finite set of well-defined instructions. Thus, a computer programmer lists down all the steps required to resolve a problem before writing the actual code. Algorithms can be represented using natural language, Pseudocode, and flowchart. Flowchart and pseudocode are most methods of representing an algorithm. For example we can write an algorithm to display the sum of two numbers entered by user, using both pseudocode and flowchart as follows: Example: Flowchart for the sum of two numbers Example: Pseudocode for the sum of two numbers would be: would be: BEGIN input num1 input num2 COMPUTE Result = num1 + num2 PRINT/DISPLAY Result END From the above Pseudocode and flowchart, it is clear that while writing an algorithm, it is required to clearly identify the following: The input to be taken from the user. Processing or computation to be performed to get the desired result The output desired by the user 10 Importance of an Algorithm An algorithm is an important phase towards writing the actual program code to instruct the computer to do a certain tasks – it is a building block of a computer program. Writing an algorithm is mostly considered as a first step to programming. A programmer writes a program to instruct the computer to do certain tasks as desired. The computer then follows the steps written in the program code. Therefore, the programmer first prepares a roadmap of the program to be written, before actually writing the code. Without a roadmap, the programmer may not be able to clearly visualise the instructions to be written and may end up developing a program which may not work as expected. Such a roadmap is nothing but the algorithm which is the building block of a computer program. For example, searching using a search engine, sending a message, finding a word in a document, booking a taxi through an app, performing online banking, playing computer games, all are based on algorithms. Once we have an algorithm to solve a problem, we can write the computer program for giving instructions to the computer in high level language. If the algorithm is correct, computer will run the program correctly, every time. So, the purpose of using an algorithm is to increase the reliability, accuracy and efficiency of obtaining solutions. Pseudocode As already mentioned in the above sub-section above, Pseudocode is one the most common methods of representing an algorithm. A pseudocode (pronounced Soo-doh-kohd) is another way of representing an algorithm. It is considered as a non-formal language that helps programmers to write algorithm. It is a detailed description of instructions that a computer must follow in a particular order. It is intended for human reading and cannot be executed directly by the computer. No specific standard for writing a pseudocode exists. The word “pseudo” means “not real,” so “pseudocode” means “not real code”. Following are some of the frequently used keywords while writing pseudocode: INPUT, READ, COMPUTE, DISPLAY, PRINT, INCREMENT, DECREMENT, IF/ELSE, WHILE, TRUE/FALSE, BEGIN, END. The benefits of Pseudocode before writing program code in a high level language is that a pseudocode of a program helps in representing the basic functionality of the intended program. By writing the code first in a human readable language, the programmer safeguards against leaving out any important step. Besides, for non-programmers, actual program code is difficult to read and understand, but pseudocode helps them to review the steps to confirm that the proposed implementation is going to achieve the desire output. Below are examples of Pseudocode: Example: Pseudocode to find the sum and Example: Pseudocode to check whether the number is even average of given three numbers would be: or odd would be: READ num1 Begin READ num2 INPUT num READ num3 IF num%2==0 Sum = num1+num2+num3 PRINT/DISPLAY num is even Avg = Sum/3 ELSE PRINT/DISPLAY Sum, Avg PRINT/DISPLAY num is odd End NB: % means modulus, which means the remainder after dividing one number by another. Advantages of Pseudocode: Improves the readability of any approach. It’s one of the best approaches to start implementation of an algorithm. Acts as a bridge between the program and the algorithm or flowchart. Also works as a rough documentation, so the program of one developer can be understood easily when a Pseudocode is written out. In industries, the approach of documentation is essential. And that is where a pseudo-code proves vital. The main goal of a Pseudocode is to explain what exactly each line of a program should do, hence making the code construction phase easier for the programmer. 11 Disadvantages of Pseudocode Pseudocode does not provide a visual representation of the logic of programming. There are no proper format for writing the pseudocode. In Pseudocode there is no proper/universal standard; every company follows their own standard for writing the pseudocode. In summary, Pseudocode is simply an implementation of an algorithm in the form of annotations and informative text written in plain English. Pseudocode can be understood as one of the methods that helps in the representation of an algorithm. Pseudocode is a simpler version of coding in a programming language. Pseudocode is written in plain English, and uses short phrases to write the functionalities that is specific line of code would do. There is no specific syntax for writing Pseudocode, which is actually present in other programming languages. This means Pseudocode cannot be executed on a computer. There are many formats that could be used to write pseudocode. Pseudocode is not actually a programming language. Control structures such as 'while', 'if-then-else', 'repeat-until', and so on can be used. Flowchart As already mentioned in the above sub-section above, a flowchart is one the most frequently used methods of representing an algorithm. A flowchart is a visual representation of an algorithm. A flowchart is a diagram made up of boxes, diamonds and other shapes, connected by arrows. Each shape represents a step of the solution process and the arrow represents the order or link among the steps. A flowchart is an easy-to-understand diagram that show how steps in a process fit together. The main objectives of a flowchart is to: Define and analyse processes; Build a step-by-step picture of a current process for analysis, discussion and/or communication Define, standardize or find areas of improvement for a given process This makes flowcharts useful tools for communicating how processes work, and for documenting clearly how a particular job is done. Furthermore, the act of mapping a process out in flowchart format helps you clarify your understanding of the process, and helps you think about where the process can be improved. Also, by conveying the information or processes in a step-by-step flow, you can then concentrate more intently on each individual step, without feeling overwhelmed by the bigger picture or by reading through detailed paragraphs in documents. Elements of a flowchart While there are other symbols and different ways to display flowcharts, for the purposes of this course, only four (4) symbols will be used: START (BEGIN) and AND (STOP): All flowcharts will begin AND end with an elongated circle (or curved rectangle). These symbols signify the STARTing and ENDing point of the flowchart. A START symbol will ONLY have a single arrow flowing out of the symbol. Usually, an END symbol has only one arrow flowing into the symbol, but in some cases, may have two or more arrows flowing into it. An END symbol will never have an arrow flowing out it. Also called “Terminator” symbol. It indicates where the flow starts and ends. Other START END symbols... 12  Rectangle: In a flowchart, a rectangle shows that at this point of a flowchart, an action or an instruction is being performed. Also called “Action Symbol,” it represents a process, action, or a single step. Instruction or Action Diamond: A diamond shape, often called a decision diamond, represents that a decision needs to taken at this point of the flowchart. Based on the decision made, a certain path is taken. In many cases, the diamond shows a number of paths (two or more). One (AND ONLY ONE) of these paths must be taken and this is determined based on a particular condition, decision or calculation. A decision or branching point, usually a yes/no or true/false question is asked, and based on the answer, the path gets split into two branches. Yes No Decision? Input and Output: In a flowchart, input and output is represented by a skewed rectangle (or parallelogram). Also called data symbol, the parallelogram shape is used to input or output data. Input: Output: Arrows: All symbols in a flowchart are linked using arrows. The arrows show movement through the flowchart from one symbol to another. The arrows therefore indicate the order in which to execute each action (represented using the symbols). Connector to show order of flow between shapes. Within each symbol, write down what the symbol represents. This could be the Start or Finish of the process, the action to be taken, the decision to be made or what needs to be received from the keyboard (Input) or placed on the screen (Output). 13  Below are two simple examples of flowcharts: Example: The algorithm to find square of a number Example: The algorithm to determine the greater number can be represented pictorially using a flowchart as between two unequal numbers can be represented shown below. pictorially using a flowchart as shown below: Flow of Control The flow of control depicts the flow of events as represented in the flowchart. The events can flow in a sequence, or on branch based on a decision or even repeat some part for a finite number of times. The algorithm classification is grouped according to the three types of control structures. They are Sequence, Branching (Selection), and Loop (Repetition). Sequence In the sequence structure, statements are placed one after the other and the execution takes place starting from up to down. Consider the two examples of an algorithm below: Example: Pseudocode to find the sum and Example: The algorithm to find square of a number average of given three numbers would be: can be represented pictorially using flowchart as READ num1 shown below. READ num2 READ num3 Sum = num1+num2+num3 Avg = Sum/3 PRINT/DISPLAY Sum, Avg In the above two examples of an algorithm, the statements are executed one after another, i.e., in a sequence. Such algorithms where all the steps are executed one after the other are said to execute in sequence. However, statements in an algorithm may not always execute in a sequence. We may sometimes require the algorithm to either do some routine tasks in a repeated manner or behave differently depending on the outcomes of previous 14 steps. In the next sub-sections, we are going to learn how to write algorithms for such situations – i.e. we are going to learn the concept of Selection and Repetition. Selection (Branching) Selection (branching) refers to a binary decision based on some condition. In a selection (branching) control, there is a condition and according to the condition, a decision of either TRUE/YES or FALSE/NO is achieved. In the case of TRUE, one of the two branches is explored; but in the case of FALSE condition, the other alternative is taken. Generally, the ‘IF-THEN’ is used to represent branch control in pseudo-code and program code. In flowcharts, this is represented by the diamond-shaped decision box. Below are some examples of algorithms that use selection/branching: Example: Pseudocode to find the greater number Example: Pseudocode to categorise people as Child or between two unequal numbers Teenager or Adult based on age group Step1: Start INPUT Age if Age < 13 then Step2: Read/input num1 and num2 PRINT "Child" Step3: If num1 > num2 then num1 is greater else if Age < 20 then Step4: else num2 is greater PRINT "Teenager" else Step5: Print greater PRINT "Adult" Step6: End Example: Flowchart to check whether the number is Example: Flowchart to categorise people as Child or even or odd would be: Teenager or Adult based on age group. NB: % means modulus, which means the remainder after dividing one number by another. Repetition (Loop, sometimes called Iteration) Sometimes we require a set of statements to be executed repeatedly until a condition is met. For instance, we may want the program to accept N numbers, and terminate when the number X is entered. We may want a program that displays all the even numbers between 0 and 250. This is where the control structure known as loop (repetition) comes in. A loop (repetition) in an algorithm means execution of some program statements repeatedly till some 15 specified condition is satisfied. The loop (repetition) allows a statement(s) to be executed repeatedly based on a certain loop condition. In the program code of a high-level language (programming language), the most commonly used loop keywords are WHILE and FOR. You will learn to use the WHILE and FOR in another ISTN103 topic called Programming in Visual Basic. Below is the general form of a loop (repletion) statement in most of the programming languages. Below is an example of an algorithm (pseudocode and flowchart) that applies a loop (repetition). Example: Pseudocode to accept 5 numbers and Example: Flowchart to accept 5 numbers and find their find their average average Step 1: Set count = 0, sum = 0 Step 2: While count < 5 , repeat steps 3 to 5 Step 3: Input a number to num Step 4: sum = sum + num Step 5: count = count + 1 Step 6: Compute average = sum/5 Step 7: Print average In summary, a flowchart is a visual representation of an algorithm: It is a graphical representation of an algorithm. Programmers use it as a program-planning tool in order to solve a problem. It uses symbols that are inter-connected. This helps indicate the flow of control and information, and processing. It is a diagram that can be created using different shapes to represent flow of data. It is easy to understand. It is a graphical representation of logic 16 Verifying algorithms An algorithm is first step towards writing the program code that produces the required software/program. Can you imagine what would happen if a billing software does not work correctly, thus credits and debits incorrect amounts because of an incorrect algorithm? An important aspect of any algorithm is that it is correct: it always produces the expected output for the range of inputs and it eventually terminates – i.e. that it is working as expected. To verify the algorithm, a programmer tests the algorithm procedure with various inputs in order to determine if there are one or more cases where it does not produce the expected output. The programmer would have to take different input values and go through all the steps of the algorithm to yield the desired output for each input value and may modify or improve the algorithm as per the need. The method of taking an input and running through the steps of the algorithm is sometimes called dry run. Such a dry run will help: Identify any incorrect steps in the algorithm Figure out missing details or specifics in the algorithm Algorithm in summary It is defined as a sequence of well-defined steps. These steps provide a solution/a way to solve the problem in hand; it gives the solution to a specific problem. It is a systematic, and a logical approach, where the procedure is defined step-wise. This solution will be translated to machine code, which is then executed by the system to give the relevant output. Many simple operations are combined to help form a more complicated operation, which is performed with ease by the computer. Algorithms can be represented using natural language, flowcharts and so on. It can be understood as the pseudocode for a program. Coding Once an algorithm is finalised, it will be coded in a high-level programming language such as Java, C#, Python, Visual Basic, etc. as selected by the programmer. The programmer uses an editor to write a set of instructions using a selected programming language by following the syntax of the selected programming language. This is referred to as coding. The terms coding and programming are often used interchangeably, but there are some differences. Coding is the process of writing program code, whereas programming is the process of creating functioning software or a computer program. The machine language (code) or low level language consisting of 0s and 1s is not an ideal way to write a computer program. Programs written using binary digits are directly understood by the computer hardware, but they are difficult to deal with and comprehend by humans. This led to the invention of high-level languages which are close to natural languages like English and are easier to read, write, and maintain, but are not directly understood by the computer hardware. An advantage of using high-level languages is that they are portable, i.e., they can run on different types of computers with little or no modifications. Low-level programs can run on only one kind of computer and have to be rewritten in order to run on another type of system. A wide variety of high-level languages, such as Visual Basic, C#, C++, Java, Python, etc., exist. A program written in a high-level language is called source code. The source code has to be translated into machine language (code) using a compiler or an interpreter, so that it can be understood by the computer. There are multiple programming languages available and choosing the one suitable for specific requirements requires a consideration of many factors. It depends on the platform (OS) where the program will run. An organisation or programmer would have to decide whether the application would be a desktop application, a mobile application or a web application. Desktop and mobile applications are generally developed for a particular operating system and for certain hardware whereas the web applications are accessed in different devices using web browsers and may use resources available over the Internet. Besides, programs are developed not only to work on a computer, mobile or a web browser, but it may also be written for embedded systems like digital watches, mp3 players, traffic 17 signals or vehicles, medical equipment and other smart devices. In such cases, the organisation or programmer would have to look for other specialised programming tools or sometimes write programs in assembly languages. Flowchart Examples Example 1: Temperature information This example will provide one of two output values depending on the temperature provided as input. Output: “Below Freezing” Yes Input: START Temp < 0 END Temp No Output: “Above Freezing” Example 2: Determining Pass or Fail The flowchart below takes in four values as input. These values, M1, M2, M3 and M4, represent marks. The grade is calculated by adding the marks and dividing the sum by 4. If the grade is 50 or more, a Pass output is provided. If not, then a Fail value is provided. So if M1, M2, M3 and M4 are the values 57, 22, 66 and 22 respectively, what will the output be? i (See the end of these notes for the answer) Output: “Fail” Grade < 50 Input: Grade = START M1, M2, END (M1+M2+M3+M4)/4 M3, M4 Grade >= 50 Output: “Pass” Example 3: Making popcorn. Is it correct? Maybe… Maybe not. In this case, you could argue that extra/fewer steps are needed. Remember that flowcharts are meant to encourage discussion. Note how the flow labelled “No” loops back to a previous step. This is known as repetition. We continue to listen for popping until we are satisfied that it has slowed enough. This would mean that most of the kernels have popped. 18  Input: 1 Cup Turn on Stove and place Start oil, 2 Cups Pot popcorn, salt Output: Has popping noise Turn off Stove Yes Popping slowed sufficiently? Noise No Output: Popcorn with few/no End unpopped kernels Example 4: Age Restriction In Cape Town, movie theatre managers are very serious about age restrictions in a movie. No matter how popular the movie may be, a person will not be allowed in if they are below the age specified. The flowchart for this process is shown below. Is it correct? Discuss (see answer at the end of the document ii). Input: Movie Allow into movie Start Age Restriction Age > MAR theater (MAR) Age < MAR Change movie Do not allow into End ticket details movie theater Output: Watch another No Yes Ticket movie? Refund 19 Example 5: Example from the Internet – Tech Support This example, while massive, shows how complex a flowchart could be in a business setting. Many possibilities are illustrated using several decision diamonds. While the diagram looks complex, it may have been more complex had it been written in words. Note that there are no START and END symbols and several punctuation and spelling issues. In this flowchart, the starting point is the instruction “Help, My computer is not working” How to draw flowcharts The general idea Start the flowchart by drawing the “START” symbol. Move to the first action or question, and draw a rectangle or diamond or parallelogram depending on the type of action/question. Write a description of the action/question within the shape and join the START symbol and this shape with an arrow pointing away from the START. You then need to work your way through the entire process, showing actions and decisions appropriately in the order they occur, and linking these together using arrows to show the flow of the process. Where a decision needs to be made, draw arrows leaving the decision diamond for each possible outcome, and label them with the outcome E.g. two flows exiting the decision diamond for Yes and No options; three arrows exiting the decision diamond for the three values of a variable: variable < 0 ; variable = 0 ; variable > 0. Show the end of the process using an elongated circle labelled “Finish”. Challenge your flowchart! Work from step to step asking yourself if you have correctly represented the sequence of actions and decisions involved in the process. As a final step, (if you’re looking to improve the process) look at the steps identified and think about whether work is duplicated, whether other steps should be involved, and whether the right people are doing the right jobs. 20 Example 6: Find the largest of three numbers that are provided as input Start your flowchart with the “START” symbol. START Since you need the largest of three numbers, your flowchart must accept as input three numbers. However, since anyone can enter any three numbers, each number is stored in three different variables, in this case A, B and C. You can name these variables anything e.g. num1, num2, num3 etc. These three variables represent any three numbers that is stored by the process. Input: START A, B, C You now need to compare the three numbers against each other. We can start with A and B. A decision diamond is required and the flowchart will look like this: Input: START A, B, C YES A > B? NO When asking the question is A > B?, there are only two possibilities i.e. either A is greater than B or it is not. The diamond will then have only two paths and we follow ONE of these two paths. If A IS GREATER THAN B (Path labelled YES), we then need to check if C is greater than A. If B IS GREATER THAN A or equal to A (Path labelled NO), then we need to check if C is greater than B. The flowchart will then look like this: Input: START A, B, C C > A? YES A > B? NO C > B? 21 Depending on the values of A, B and C, once the comparisons are made, the output values will be the largest number. Once the output of the largest number is given, the flowchart ends. Input: START A, B, C YES C > A? YES A > B? NO C > B? YES NO NO Output: Output: C C Output: Output: B A END Example 7: Grocery shopping – Paying for items When shopping for groceries at a supermarket, think about going to the till to pay for your items. It may be similar to the descriptions below: The system starts by placing your items on the cashier’s table. This could be regarded as input into the system. Note that we have an instruction TotalDue = 0. Here, the = symbol implies that we are creating a variable (storage location) called TotalDue. We will store the value 0 in this variable TotalDue. Input: START TotalDue = 0 Grocery Items 22 The cashier then scans the first item’s barcode to get the price. Input: START TotalDue = 0 Grocery Items Scan Grocery Item to get Price Add the Price to the Total Due. Are there any more items to scan? If so, scan the item’s barcode to get the price. This is the same step as before. Input: START TotalDue=0 Grocery Items Scan Grocery Item to TRUE get Price More Add Price to TotalDue Items? If there are no more items to scan, then output the total due. The customer then provides the money. The change must then be calculated and given to the customer (if needed). 23  Input: START TotalDue = 0 Grocery Items Scan Grocery Item to TRUE get Price More Add Price to TotalDue Items? Output: FALSE TotalDue Input: Calculate Change Amount (If any) Paid Output: END Change and receipt What do you think? Can the diagram be improved by adding any extra steps? iii Example 8.1: Student Acceptance System Star City College (SCC) is a new tertiary institution offering B.Com degrees. The first step of the process for accepting a student is that the student must send their matric results. The matric results are then stored and an acceptance letter is sent to the student. Draw the flowchart for the process described. The flowchart must begin with START. A student’s matric results are provided as input. Therefore the flowchart is drawn: Matric START Results As described above, the results are stored and the acceptance letter is sent. So this simple flowchart is completed using a process and an output symbol followed by the END. Input: Output: START Matric Store student results Acceptance END Results Letter Example 8.2: Student Acceptance System with criteria An administrator at SCC points out an obvious flaw with the system. Anyone could send their results through and be accepted. This would result in them not knowing the quality of students entering the college. The academics and admin staff then agreed on a system to produce a score based on the student’s matric results. If the matric score (call it MScore for short) is > 36, a student is accepted. If MScore is < 30, then the student is rejected. If MScore is 24 in the range 30 to 36, then the student must be notified to take an acceptance test. If they pass the test, only then are they accepted. Considering the new criteria, redraw the flowchart. When looking at redrawing the diagram, a process needs to be included that calculates the MScore. In order to determine the route that must be taken based on MScore, a decision diamond is needed and for that diamond, how many alternative paths to take. In this case, there are 3 paths i.e. a score > 36, a score < 30 and a score between the two values. The diamond would therefore look like this: < 30 Calculate MScore MScore > 36 30 To 36 For students with an MScore of 30 to 36, a test must be written (process). A student can either PASS or FAIL the test. Therefore this diamond will only have two logical paths. If the student passes, he/she is sent an acceptance letter. Output: Acceptance Letter 30 To 36 Pass END Administer Test Result Fail So the diagram would look like this: 25  Input: START Matric Calculate MScore Results Output: MScore > 36 Acceptance Letter Pass 30 to 36 END Administer Test Result Fail < 30 Example 8.3: Student Acceptance System with criteria and limited space The facilities manager has pointed out that SCC only has space for 100 students currently. In addition to the criteria for acceptance, allowing for more than 100 students would violate several laws and regulations. The academic and administrative staff then decide that the first 100 students that apply and go through the criteria and are accepted. So the staff want to continue to capture students and their matric marks and determine to accept or reject UNTIL 100 students have been accepted. Redraw the flowchart to take into consideration the student limit. Repetition is the process of repeating a set of instructions continuously until something happens that causes these instructions to stop repeating. Repetition is a continuous part of our lives, either in the things that we do as well as biologically. Examples of repetition include: Walking – when a person wants to go to a destination (assume it is straight ahead), the process of moving left leg forward, then right leg forward continues until the destination is reached. As seen in the flowchart below, a check is made after moving each leg. If the destination has not been reached, go back to the process of move legs forward. If the destination has been reached, then STOP walking (END). Left foot forward START Reached destination END Right foot forward Not reached destination Bank queues – A teller at a bank will continue to serve customers until all the customers in the queue have been dealt with. As the flowchart shows, the teller checks to see if there are customers in his queue. If there is not, he/she says “Next customer please” and serves that customer based on their needs (could be another flowchart). Once the customer is served, they can check the queue again. If there are customers, repeat the process. If there are no customers, the process ends (until there are customers to deal with again). 26  Customer in Output: “Next Serve START YES queue? customer please” customer NO END Counting – Whether you are counting the number of students in a class or the number of pens you have, counting is a form of repetition where you continuously add 1 to a number until you have pointed your finger at all the items that you are counting. In the flowchart below, a counter variable is initially set to 0. Now think of some students sitting in the first row of a lecture room. You can start on the left and count each student. Each time you count, you add 1 to the counter (this is reflected in the instruction below as “Counter = Counter + 1”. You check if you have finished count all students in the row. If you have not, you continue counting. When you reach the end of the row and there are no students left, you stop counting. START Counter = 0 Finished counting? NO Counter = Counter + 1 YES Output: Counter END In the SCC scenario, the repetition involves continuing the process of capturing matric results and determining a course of action (accept, test or reject) until the college has 100 students. Therefore, some adjustments need to be made to the solution shown in example 8.2. Firstly, as SCC will be counting students as they are accepted, a variable is required that will count whenever a student is accepted. This variable will be called StudentCount and will be set to 0 initially. The process of assessing each student then begins as shown in example 8.2. i.e. enter matric score and determine whether to accept, test or reject the student. If the student is accepted (either due to their MScore being > 36 or if they passed the acceptance test), only then does the StudentCount variable increase by 1. Regardless, we need to check if the StudentCount has reached the limit (100) or not. If it has, then SCC has accepted the maximum number of students and cannot accept any more. If the StudentCount is still less than 100, then we can request another student’s matric result and follow the process. Thus, the final flowchart would look like this: 27  < 100 Input: Store student results START StudentCount = 0 Matric Calculate MScore Results Output: Increment MScore > 36 Acceptance StudentCount StudentCount by 1 Letter Pass 30 To 36 Fail =100 Administer Test Result < 30 END 28 Section 5: Exercises This section provides extra exercises for practice in drawing flowcharts. Please note that solutions will not be provided or uploaded. Should you have any queries, email or make an appointment with your lecturer/tutor/PGA who will provide you with guidance as to whether you are on the right track or not. 4.1. Draw a flowchart that takes in three numbers as input and outputs the sum of the three numbers. 4.2. Draw a flowchart that will output the sum, product and difference of two numbers. The two numbers are 27 and 7 respectively. 4.3. Draw a flowchart that will take two numbers as input and must output the larger of the two numbers. If the numbers are the same, a relevant message must be given. 4.4. Draw a flowchart that will allow the input of a number. The end result must produce the opposite of that value. For example, if the input is 5, the output is -5. Another example, if the input is -7, the output must be 7. 4.5. Draw a flowchart that takes in three numbers, A, B and C as input. Add values A and B. The flowchart must then output whether the sum of values A and B is greater than, less than or equal to C. 4.6. Draw a flowchart that will accept as input two values, A and B. Determine whether value A, when squared, results in value B. 4.7. You are asked to draw a flowchart that will take in a number. If the number is greater than 50, determine the number’s square root. Otherwise, determine the square of that number. 4.8. Draw a flowchart that will determine the largest of four numbers entered by the user. 4.9. Darrian goes to a stationery shop to purchase rulers, pens and books. Each ruler costs R 4.50, pens cost R 2.75 each and books cost R 6.75 each. A discount of 15% is awarded if purchases exceed R200.00. Draw a flowchart to determine the total cost of items purchased, where the quantity of each item is entered by the user. Output the discount (if any) and the total amount that Darrian has to pay, inclusive of discount. 4.10. Given the length of the square as input, draw a flowchart that will determine the square’s area, as well as its perimeter. 4.11. Determine whether a person passes or fails an examination based on the total he has obtained for six subjects. If his total exceeds 720, then output the message “Promoted”, otherwise output the message “Not Promoted”. 4.12. Take in three values, A, B and C. The flowchart should then find the smallest number and store it in A, find the largest number and store it in C, with the remaining number being stored in B. 4.13. Write a Pseudocode and draw a flowchart for checking eligibility for voting depending on the person`s age; a person will either be allowed to vote or not allowed to vote: If age is greater than or equal to 18, the person is eligible to vote If age is less than 18, the person is not eligible to vote. 29 References http://www.c4learn.com/c-programming/compiler-vs-interpreter/ https://bennettbusinessconnections.com/2011/04/03/fix-your-own-computer-issues-a-flowchart-2/ https://mrcet.com/downloads/digital_notes/HS/Programming%20for%20Problem%20Solving.pdf https://www.bbc.co.uk/bitesize/guides/z4cck2p/revision/1 https://www.tutorialspoint.com/difference-between-algorithm-and-pseudocode https://www.guru99.com/difference-compiler-vs-interpreter.html https://ncert.nic.in/textbook/pdf/kecs104.pdf https://courses.minia.edu.eg/Attach/16036flowchart-algorithm-manual.pdf https://faradars.org/wp-content/uploads/2015/07/Algorithm-and-Flow-Chart.pdf https://mrcet.com/downloads/digital_notes/HS/Programming%20for%20Problem%20Solving.pdf Acknowledgements Special thanks to CS Price for reviewing of the document and identifying problems, corrections and suggestions. Solutions to exercises i Fail (57+22+66+22 = 167. 167/4 = 41.75. Since 41.75 < 50, we follow that path which leads to the output FAIL) ii The age needs to be provided as an input symbol before the check can be made. In addition, the Yes and No arrows need to be swapped. The instruction “Change movie details” can also be an input where the user provides the new movie. iii The diagram could be improved. There could be a diamond where if the money provided is greater than the amount due, calculate and provide change. If the money provided is equal to amount due, provide no change. If the money provide is less than the amount due, notify customer that there is insufficient money to pay for items. 30