WIXLIB

Principles of ProgrammingChapter 2: Problem Solving In this chapter you will learn about: Introduction to Problem Solving Software development method (SDM) Specification of needsProblem analysisDesign and algorithmic representationImplementationTesting and verificationDocumentationNI S1 2009/101

Principles of ProgrammingIntroduction to Problem Solving Programming is a problem solving activity. Whenyou write a program, you are actually writing aninstruction for the computer to solve somethingfor you. Problem solving is the process of transformingthe description of a problem into a solution byusing our knowledge of the problem domain andby relying on our ability to select and useappropriate problem-solving strategies,techniques and tools.2

Principles of ProgrammingCase Study Problem: Compute the straight-line distancebetween two points in a plane.3

Principles of ProgrammingSoftware Development Method (SDM) For programmer, we solve problems using SoftwareDevelopment Method (SDM), which is as follows:1. Specification of needs State the problem clearly2. Problem analysis Describe the input and output information3. Design and algorithmic representation Work the problem by hand for a simple set of data4. Implementation Develop a solution and convert it to a computer program5. Testing and verification Test the solution with a variety of data6. Documentation Document and record information for reference4

Principles of ProgrammingSpecification of Needs Specifying the problem requirements requiresyou to state the problem clearly and to gain theunderstanding of what to be solved and whatwould be the solution. When specifying problem requirement, we askourselves the following questions: What the problem is.What the solution should provide.What is needed to solve it.If there are constraints and special conditions.5

Principles of ProgrammingCase StudyProblem: Compute the straight-line distance betweentwo points in a plane. What the problem is. What the solution should provide. What is needed to solve it. If there are constraints and special conditions.6

Principles of ProgrammingProblem Analysis Analyzing the problem require us to identify thefollowing: Input(s) to the problem, their form and the inputmedia to be used Output(s) expected from the problem, their form andthe output media to be used Special constraints or conditions (if any) Any formulas or equations to be used7

Principles of ProgrammingCase Study Input? Point 1 coordinate Point 2 coordinate Output? Distance between points Constraint/condition? Nil Formula/equation? Pythagorean theorem8

Principles of ProgrammingDesigning algorithm Designing algorithm to solve the problemrequires you to develop a list of steps, arranged ina specific logical order which, when executed,produces the solution for a problem. Using top-down design (also called divide andconquer): You first list down the major tasks For each major task, you further divide it into subtasks (refinement step) When you write algorithm, write it from thecomputer’s point of view.9

Principles of ProgrammingDesigning Algorithm cont. An algorithm must satisfy these requirements: It may have an input(s) It must have an output(s) It should not be ambiguous (there should not be differentinterpretations to it. Every step in algorithm must be clearas what it is supposed to do) It must be general (it can be used for different inputs) It must be correct and it must solve the problem for whichit is designed It must execute and terminate in a finite amount of time It must be efficient enough so that it can solve the intendedproblem using the resource currently available on thecomputer10

Principles of ProgrammingCase StudyMajor Task:1. Read Point 1 coordinate2. Read Point 2 coordinate3. Calculate distance4. Display the computed distanceHowever, looking at the above algorithm, we can still further refinestep 3, by introducing the formula to calculate the amount to pay.After refinement:1. Read Point 1 coordinate2. Read Point 2 coordinate3. Distance (𝑠𝑖𝑑𝑒 1)2 (𝑠𝑖𝑑𝑒 2)24. Display the computed distance11

Principles of ProgrammingRemember, the order of the steps inalgorithm is very important. Considerthe following, will the result be thesame?1.2.3.4.Display the distanceRead Point 1 coordinateCompute distanceRead Point 2 coordinate12

Principles of ProgrammingPseudocodes A pseudocode is a semiformal, English-likelanguage with limited vocabulary that can beused to design and describe algorithms. Criteria of a good pseudocode: Easy to understand, precise and clear Gives the correct solution in all cases Eventually ends13

Principles of ProgrammingFlowcharts Flowcharts is a graph used to depict or show astep by step solution using symbols whichrepresent a task. The symbols used consist of geometrical shapesthat are connected by flow lines. It is an alternative to pseudocoding; whereas apseudocode description is verbal, a flowchart isgraphical in nature.14

Principles of ProgrammingFlowchart SymbolsTerminal symbol - indicates the beginning andend points of an algorithm.Process symbol - shows an instruction other thaninput, output or selection.Input-output symbol - shows an input or an outputoperation.Disk storage I/O symbol - indicates input from oroutput to disk storage.Printer output symbol - shows hardcopy printeroutput.15

Principles of ProgrammingFlowchart Symbols cont Selection symbol - shows a selection processfor two-way selection.Off-page connector - provides continuation of alogical path on another page.On-page connector - provides continuationof logical path at another point in the samepage.Flow lines - indicate the logical sequence ofexecution steps in the algorithm.16

Principles of ProgrammingControl Structure An algorithm can be represented usingPseudocode or Flowchart. In 1966, two researchers, C. Bohn and G. Jacopini,demonstrated that any algorithm can bedescribed using only 3 control structures:sequence, selection and repetition.17

Principles of ProgrammingControl Structure Sequence: A series of steps or statements thatare executed in the order they are written in analgorithm. Selection: Defines two courses of actiondepending on the outcome of a condition. Acondition is an expression that is, whencomputed, evaluated to either true or false. Repetition: Specifies a block of one or morestatements that are repeatedly executed until acondition is satisfied.18

Principles of ProgrammingYou may have more thanone control structure in oneprogram in order to solve aproblem.19

Principles of ProgrammingThe Sequence control structure A series of steps or statements that are executed in theorder they are written in an algorithm. The beginning and end of a block of statements can beoptionally marked with the keywords begin and end.beginstatement 1.statement 2. statement n.endbeginstatement 1statement 2 statement nend20

Principles of ProgrammingThe Sequence control structureProblem: calculate a person’s ageBeginread birth yearage current year – birth yeardisplay ageEndbeginread birth yearAge current year –birth yearDisplay ageend21

Principles of ProgrammingThe Selection control structure Defines two courses of action depending on the outcomeof a condition. A condition is an expression that is, whencomputed, evaluated to either true or false. The keyword used are if and else. Format:if (condition)then-partelseelse-partend 2

Principles of ProgrammingThe Selection control structureBeginread ageif (age is greater than 55)print “Retired”elseprint “Still working”end ifEndBeginRead ageYESBeginread ageif (age 55)print “Retired”elseprint “Still working”end ifEndage 55?print “Still working”print “Retired”End23NO

Principles of ProgrammingPseudocodes: The Selection control structure Sometimes in certain situation, we may omit the else-part.if (number is odd number)print “This is an odd number”end ifExample 1 Nested selection structure: basic selection structure thatcontains other if/else structure in its then-part or else-part.if (number is equal to 1)print “One”else if (number is equal to 2)print “Two”else if (number is equal to 3)print “Three”elseprint “Other”end if24Example 2

Principles of ProgrammingExerciseDraw the flowchart diagram forExample 1 and Example 225

Principles of ProgrammingThe Repetition control structure Specifies a block of one or more statementsthat are repeatedly executed until a conditionis satisfied. The keyword used is while. Format:while (condition)loop-bodyend whileyesCondition?no26LoopStatement(s)

Principles of ProgrammingProblem: Write a program that reads and displaysthe age of 10 people (one after another).For this problem, we need a way to count how manypeople whose age have been processed (read anddisplayed). Therefore, we introduce a concept of counter,a variable used to count the number of people whoseage have been processed by the program.27

Principles of ProgrammingCounter initialisationBeginnumber of users giving his age 1while (number of users giving his age 10)read the age from the user.Loop conditionprint the user age.number of user giving his age 1end whileUpdating counterEndBeginusers 1while (users 10)read ageprint age.users users 1end whileEnd28

Principles of ProgrammingBeginusers 1NOEndusers 10?YESread ageprint ageusers users 129

Principles of ProgrammingSubsequently.You can start theBegincounter with ZEROnumber of users giving his age 0while (number of users giving his age 10)read the age from the user.print the user age.The loop conditionnumber of user giving his age 1must less than theend whilevalue it requires toEndstopBeginusers 0while (users 10)read ageprint age.users users 1end whileEndBeconsistent30

Principles of ProgrammingLittle extra Now let us put together everything that youhave learnt so far. Problem:Write a program that will calculate and print theage of 10 persons, given their birth year. If the ageof the person is above 55, then the program willprint “Retired”, otherwise, the program will print“Still working”.31

Principles of ProgrammingBeginusers 1Example 3while (users 10)beginRead birth yearage current year – birth yearprint ageNote that in thisif age 55example, we areprint “Retired”using all the threeelsecontrol structures:print “Still working”sequence, selectionend ifand repetitionusers users 1endend whileEnd32

Principles of ProgrammingExerciseDraw the flowchart diagram forExample 333

Principles of ProgrammingImplementation The process of implementing an algorithm bywriting a computer program using a programminglanguage (for example, using C language) The output of the program must be the solutionof the intended problem The program must not do anything that it is notsupposed to do(Think of those many viruses, buffer overflows, trojanhorses, etc. that we experience almost daily. All theseresult from programs doing more than they wereintended to do)34

Principles of ProgrammingTesting and Verification Program testing is the process of executinga program to demonstrate its correctness Program verification is the process ofensuring that a program meets userrequirement After the program is compiled, we mustexecute the program and test/verify it withdifferent inputs before the program can bereleased to the public or other users (or to theinstructor of this class)35

Principles of ProgrammingDocumentation Writing description that explain what theprogram does. Important not only for other people to use ormodify your program, but also for you tounderstand your own program after a long time(believe me, you will forget the details of yourown program after some time .) Can be done in 2 ways: Writing comments between the line of codes Creating a separate text file to explain theprogram36