Chapter 5 Algorithms and Programming Languages1OutlineConceptsDefinitionHow to develop an algorithmEssential features Three ConstructsAlgorithm RepresentationPseudocodeFlowchartStructure chartBasic algorithms Recursion2OutlineEvolutionCategories of languagesBuilding programsElements of programming languages3ObjectivesDefine algorithms.List the 5 essential properties of an algorithm.Define and use the three constructs for developingalgorithms: sequence, decision, and repetition.Understand and use three tools to represent algorithms: flowchart, pseudocode, and structure chart.Understand the concept of modularity and subalgorithms.List and comprehend common algorithms, such as sorting and searching. Differentiate between recursion and iteration.4ObjectivesHave a vision of computer language evolution.Distinguish between machine, assembly, and high-level languages.Distinguish between the different categories of languages: procedural, object-oriented, functional, declarative, and special.Understand the process of creating and running a program.Become familiar with elements of programming languages.5part 1DEFINITION6Informal definition7Example-Finding the largest integer among five integers8Defining actions9Refinement 2 problems with the previous method:The action in the first step is different from the ones for the other steps.The wording is not the same in steps 2 to 5. 10Generalization11Formal definitionAlgorithm: an ordered set of unambiguous steps that produces a result and terminates in a finite time.It is a step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps. It is a precise, systematic method for producing a specified result.12SpecificationThe specification of an algorithm must be “precise”.To write a precise algorithm, we need to pay attention to three things:Capability. Make sure that the computer knows what and how to do the operations.Language. Ensure that the description is unambiguousthat is, it can only be read and understood one way.Context. Make few assumptions about the input and execution setting.135 essential properties of algorithmsTo write algorithms that are specified well enough for a computer to follow, make sure every algorithm has five essential properties:Inputs specifiedOutputs specifiedDefinitenessEffectivenessFiniteness14Input specifiedThe inputs are the data that will be transformed during the computation to produce the output.We must specify the type of the data, the amount of data, and the form that the data will take.Suppose the algorithm is a recipe. We must list the ingredients(type of inputs), their quantities(amount of input), and their preparation, if any(form of inputs), as in “1/4 cup onion, minced.”15Outputs specifiedThe outputs are the data resulting from the computation, the intended result.Often the description is given in the name of the algorithm, as in “Algorithm to compute a batting average.”As with inputs, we must specify the type, amount, and any form of the outputs. “3 dozen 3-inch chocolate chip cookies.”A possible output for some computation is a statement that there can be no outputthat is, no solution is possible.16DefinitenessAlgorithms must specify every step. Definiteness means specifying the sequence of operations for transforming the inputs into the outputs.Every detail of each step must be spelled out, including how to handle errors.Definiteness ensures that if the algorithm is performed at different times or by different agents (people or computers) using the same data, the output will be the same.17EffectivenessIt must be possible for the agent to execute the algorithm mechanically without any further inputs, special talent, clairvoyance, creativity, help from Superman, and so on.Whereas definiteness specifies which operations to do, effectiveness means that they are doable.Examples of ineffectiveness: “Enter the amount of income you would have received this year had you worked harder”, “Print the length of the longest run of 9s in the decimal expansion of ”18FinitenessAn algorithm must have finiteness; it must eventually stop, either with the right output or with a statement that no solution is possible. If no answer comes back, we cant tell whether the algorithm is still working on an answer or is just plain “stuck”.Finiteness becomes an issue for computer algorithms because if the algorithm doesnt specify when to stop the repetition, the computer will continue to repeat the instructions forever. For example, divide 3 into 10. Any process having these five properties will be called an algorithm.19part 2 3 CONSTRUCTS203 ConstructsComputer scientists have defined three constructs for a structured program or algorithm.The idea is that a program must be made up of a combination of only these three constructs: sequence, decision (selection), and repetition.21SequenceAn algorithm, and eventually a program, is a sequence of instructions, which can be a simple instruction or either of the other two constructs.A program is an algorithm that has been customized to solve a specific task under a specific set of circumstances in a specific language. 22Decision Some problems can not be solved with only a sequence of instructions. Sometimes you need to test a condition.If the result of testing is true, you follow a sequence of instructions; if it is false, you follow a different sequence of instructions.This is called the decision (selection) construct.23Repetition In some problems, the same sequence of instructions must be repeated.You handle this with the repetition (loop) construct.24part 3 Algorithm Representation25Algorithm RepresentationWe can use different tools to represent algorithms: Pseudo-codeFlowchartStructure chart 26Pseudocode It is an English-like representation of the code required for an algorithm. It is part English and part structured code.English part provides a relaxed syntax that is easy to read.Code part consists of an extended version of the basic algorithmic constructs (sequence, decision and repetition).Until now, there is no standard for pseudocode.27Pseudocode exampleAlgorithm: Finding SmallestPurpose: This algorithm finds the smallest number among a list of numbers.Pre: List of numbersPost: NoneReturn: The Smallest1. Set smallest to the first number2. loop (not end of list)2.1 if (next number rbeginInput m, nr = 0 ?NYoutput nn - m; r- nGet remainderend41Exercise1.Rewrite the GCD example in pseudocode.2.Rewrite the Algorithm 8.4 Find largest (page149) example in flowchart.42ATM ExampleWrite the algorithm for a simple ATM machine. It should include two functions: deposit and withdrawal.43ATM Example1.Get the password from the user.2.If the password is not valid, construct an error message and skip to step 6.3.Get the inputs.3.1 Get the transaction type and the amount from the user. 3.2 Get the current balance from the bank.4.If the transaction type is deposit, add amount to the current balance.5.If the transaction type is withdrawal, check the current balance.5.1 If amount is larger than balance, error and skip to step 6.5.2 If amount is equal to or less than balance, subtract.6.Output the error message or the cash, and the current balance.7.Ask the user whether to repeat step 3 though 6 for another transaction.44Flowcharts for two functions of ATM machineGet passwordGet deposit amountAdd amount to balancePrint the receiptGet passwordGet cash amountSubtract amount from balanceDispense the cashATM Example45Complete ATM machine flowchartGet passwordPassword right?Get type and amountDeposit orwithdrawal?Amount balanceAdd amount to balanceSubtract amountfrom balanceGive responseor errorYYNNdepositwithdrawalATM Example46SubprogramsThe principles of structured programming require that an algorithm be broken into small units called subalgorithms (the term subprograms, subroutines, procedures, functions, methods, and modules are also used).Each subalgorithm is in turn divided into smaller subalgorithms.The process continues until the subalgorithm become intrinsic (understood easily).47SubprogramsWe can divide “Algorithm Find Largest” into a main algorithm and a subalgorithm.In each iteration, the algorithm finds the larger of two integers.We can separate this part of the task and create a small subtask out of it.48SubprogramsIn line 2.1, FindLargest is suspended and FindLarger begins.FindLarger finds the larger number between the current Largest value and the current integer value. This is known as a function call.Note that in each iteration, FindLarger is called once.The advantages of using subalgorithms:It is more understandable.A subalgorithm can be called many times in different parts of the main algorithm without being rewritten.49SubprogramsFindLargestInput: A list of positive integers1.Set Largest to 02.while (more integers) 2.1 FindLargerEnd while3.Return LargestEndFindLargerInput: Largest and current integer1.if (the integer is greater than Largest)then 1.1 Set Largest to the value of the integerEnd ifEnd50Structure chartA structure chart is a high-level design tool that shows the relationship between different modules in an algorithm.It is mostly used at the design level. In other words, it is created before you start writing your program.511Symbols used in the structure chart:Structure ChartStructure ChartFunctionCommon functionConditionLoopCondition loop(+)Exclusive ORData flowFlag52Structure ChartStructure Chart1Using the structure chart to write the algorithm for a simple ATM machine in top-down design.Simulate an ATM machineGet inputsGet inputsPerform allPerform allcalculationscalculationsGive outputsGive outputsFirst-level ATM structure chart53Structure ChartStructure ChartSecond-level structure chart for ATM inputSecond-level structure chart for ATM outputGet inputsGet inputsGetGetpasswordpasswordGetGettransactiontransactiontypetypeGetGettransactiontransactionamountamountGive outputsGive outputsPrintPrinterrorerrorPrint Print balancebalanceDispenseDispensecashcash54Second- and third-level structure chart for ATM calculationsStructure ChartStructure ChartAdd amountAdd amountto balanceto balancePerformcalculationsHandledepositsHandlewithdrawalsCheckCheckbalancebalanceSubtract amountSubtract amountfrom balancefrom balanceGiveGiveerrorerror55Example1. Write an algorithm that will calculate and print the average grade on three tests for an entire class. (in pseudocode, structure chart and flowchart)Pseudocode:lGet the 3 test scores;lAdd the scores together;lDivide the sum by 3;lPrint the average;lRepeat step1 through 4 for each student.56Example (con.)(con.)Structure chart:NoteNote The structure chart gives no indication of looping. The iteration is shown in the pseudocode and flowchart.CalculategradesGet inputsCalculateAverage gradePrint gradeGet 3 scoresAdd 3 scoresDivide by 357Flowchart:Example (con.)(con.)Get 3 scoresPrint the averageMorestudents?Add the scores togetherDivide the sum by 3YN58ExampleExample2. Write an algorithm for a simple calculator (in pseudocode and structure chart).Pseudocode:lGet two numbers and the operation desired.lCheck the operation:2.1 If operation is addition, the result is the first + the second;2.2 If operation is subtraction, the result is the first - the second;2.3 If operation is multiplication, the result is the first * the second;2.4 If operation is division, check the second number:2.4.1 If zero, send error message. 2.4.2 If not zero, the first / the second.lPrint out the result or the error message.59Structure chart:Example (con.)Example (con.)calculatorinputsinputsperformperformoutputsoutputs2 numbers2 numbersoperationoperationadditionadditionsubtractionsubtractionmultiplicationmultiplicationdivisiondivisionresultresulterrorerrorCheck 2nd for zeroCreate error60ExampleExample3. Write an algorithm in pseudocode for a program to calculate the area of simple shapes (rectangle, right triangle and circle).lGet the shape desired.lIf it is a rectangle:2.1 get the length and width.2.2 calculate the area as length * width.lIf it is a right triangle:3.1 get the base and height.3.2 calculate the area as base* height / 2.lIf it is a circle:4.1 get the radius.4.2 calculate the area as radius * radius * 3.14.lPrint out the area.61part 4 Basic Algorithms62Summation 63Product64SortingSorting is the process by which data are arranged according to their values.There are three fundamental sorting algorithms:Selection sortBubble sortInsertion sort65Selection sortIn selection sort, the list is divided into 2 sublistssorted and unsortedwhich are divided by an imaginary wall.You find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted data.After each selection and swapping, the imaginary wall moves one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones.Each time you move one element from the unsorted sublist to the sorted sublist, you have completed a sort pass.A list of n elements requires n-1 passes to completely rearrange the data.66676869Bubble sortIn bubble sort method, the list is divided into 2 sublistssorted and unsorted.The smallest element is bubbled from the unsorted sublist and moved to the sorted sublist.After the smallest element has been moved to the sorted list, the wall moves one element ahead.Each time an element moves from the unsorted sublist to the sorted sublist, one sort pass is completed.Given a list of n elements, bubble sort requires up to n-1 passes to sort the data.7071Insertion sortIn insertion sort method, the list is divided into 2 sublistssorted and unsorted.In each pass, the first element of the unsorted sublist is picked up, transferred to the sorted list, and inserted at the appropriate place.Note that a list of n elements will take at most n-1 passes to sort the data.7273SearchingSearching is the process of finding the location of a target among a list of objects.In the case of a list, searching means that given a value, you want to find the location (index) of the first element in the list that contains that value.74Sequential searchSequential search is used if the list being searched is not ordered.In a sequential search, you start searching for the target from the beginning of the list. You continue until you either find the target or you are sure that it is not in the list (because you have reached the end of the list).7576Binary searchIf the list is sorted, you can use a more efficient algorithm called binary search.A binary search starts by testing the data in the element at the middle of the list.This determines if the target is in the first half or the second half of the list.With every pass, we eliminate half of the list.77part 5 Recursion78RecursionIn general, there are two approaches to writing algorithms for solving a problem:IterationRecursionRecursion is a process in which an algorithm calls itself.79Iterative definition of factorialAn algorithm is iterative whenever the definition does not involve the algorithm itself.80Recursive definition of factorialAn algorithm is defined recursively whenever the algorithm appears within the definition itself.81RecursionThe recursive solution for a problem involves a two-way journey.First you decompose the problem from top to bottom, and then you solve it from bottom to top.82Iterative solution of factorialFactorialInput: A positive integer num1.Set FactN to 02.Set i to 13.while (i is less than or equal to num) 3.1 Set FactN to FactN x I 3.2 Increment iEnd while4.Return FactNEnd83Recursive solution of factorialFactorialInput: A positive integer num1.if (num is equal to 0)then 1.1 return 1else1.2 return num x Factorial (num 1) End ifEnd84part 6Evolution85EvolutionA computer language is a set of predefined words that are combined into a program according to predefined rules (syntax).Computer languages have evolved from machine language to natural languages.86Machine languagesMachine language, the lowest level of language, is the basic language of the computer, representing data as 1s and 0s.Machine programs vary from computer to computer; that is, they are machine dependent.The only language understood by a computer is machine language.These binary digits correspond to the on and off electrical states of the computer.87Machine languages Advantage: it works efficiently for computer.Disadvantage: it is not convenient for people to read and use.00000000000001000000000000000000010111100000110011000010000000000000001011101111 00010110000000000000010111101111 10011110000000000000101111111000 10101101 11011111 00000000000100100110001011011111 000000000001010111101111 0000001011111011 0000000000010111111101001010110111011111 0000000000011110000000111010001011011111 000000000010000111101111 0000001011111011 000000000010010001111110 111101001010110111111000 10101110110001010000000000101011000001101010001011111011 000000000011000111101111 0000001011111011 00000000001101000000010000000000001111010000010000000000001111011 12 23 34 45 56 67 78 89 9101011111212131314141515161688Symbolic languagesSymbolic language, also called assembly language, is a low-level language that allows a programmer to use abbreviations or easily remembered words instead of numbers.Assembly language varies from computer to computer; its machine dependent.A programmer can write instructions in assembly language more quickly than in machine language; however, its still not an easy one to learn, and its so tedious to use that mistakes are frequent.89Symbolic languages1 12 23 34 45 56 67 78 89 9101011111212131314141515161600000000 00000100 000000000000000001011110 00001100 11000010 0000000000000010 11101111 00010110 0000000000000101 11101111 10011110 000000000000101111111000 10101101 11011111 0000000000010010 01100010 11011111 000000000001010111101111 00000010 11111011 000000000001011111110100 10101101 11011111 000000000001111000000011 10100010 11011111 000000000010000111101111 00000010 11111011 000000000010010001111110 11101000 1010110111111000 10101110 11000101 000000000010101100000110 10100010 11111011 000000000011000111101111 00000010 11111011 0000000000110100 00000100 0000000000111101 00000100 0000000000111101Entry main,msubl2 #12,spjsb C$MAIN_ARGSmovab $CHAR_STRING_CONpushal -8(fp)pushal (r2)calls #2,readpushal -12(fp)pushal 3(r2)calls #2,readmull3 -8(fp),-12(fp),-pushal 6(r2)calls #2,printclrl r0ret90Language translatorsA special program called an assembler is used to translate symbolic code into machine language.A language translator is a type of system software that translates a program written in a second- or higher-generation language into machine language.91Language translatorsLanguages translators are of three types: Assemblers Compilers InterpretersSourceCodeObjectCodeLanguage Translator92High-level languagesA high level language is an English-like language that allows users to write in a familiar notation, rather than numbers or abbreviations.Most high-level languages are not machine dependent; they can be used on more than one kind of computers. They are portable, allowing the programmer to concentrate on the application rather than the intricacies of the computer.93High-level languagesThe translator for high-level languages is depending on the language, either a compiler or an interpreter.Compilerexecute later. Its software that looks at an entire high-level program before translating it into machine language. Examples are C and COBOL.Interpreterexecute immediately. Its software that converts high-level language statements into machine language one at a time, in succession. Examples are BASIC and LISP.94Natural languagesNatural languages are of two types. The first are ordinary human languages (such as Chinese, English, Spanish and so on). The second are programming languages that use human language to give people a more natural connection with computer.Natural languages are part of the field of study known as artificial intelligence (AI).95part 7Categories of languages96Categories of languagesWe divide computer languages into five categories: 97Procedural languagesA procedural language is a set of instructions that are executed one by one from beginning to end unless an instruction forces the control elsewhere.When programmers need to solve a problem using one of the procedural languages, they should know the procedure to follow.Because each instruction of procedural languages is a command to the computer system to do some specific task, procedural languages sometimes called imperative languages.98Procedural languagesFORTRAN (FORmula TRANslation)COBOL (Common Business-Oriented LanguagePascalCAda99Object-oriented languages Unlike C and Pascal are procedural oriented languages, forcing the user to follow a predetermined path from step A to Step B and so on, object-oriented languages are event driventhat is, they respond to input from the user or other programs at unregulated times and thus are driven by user choices.100Object-oriented languagesIf we think of a data item in a programming language as an object, a program can be thought of as a series of operations that you want to perform on the object.In procedural languages, the objects are passive. They do not have operations defined for them. The programmers define the operations and apply them to the objects.In object-oriented programming, the objects and the operations to be applied to them are tied together. The objects are active.101Object-oriented languagesC+EncapsulationInheritancePolymorphismJavaApplication vs. appletMultithreading102Part 8 Building a program 103Building a programIt is the job of a programmer to write the program and then turn it into an executable (machine language) file. There are 3 steps in this process: Writing and editing the programCompiling the programLinking the program with the required library modules104Edit programCompile programLink programC LibraryCompileSystem*.c*.obj*.obj*.exeEdit Compile Link Execute 105106part 9 Elements of programming languages 107Elements of Programming Languages There are variables or objects, in which you can store the pieces of data that a program is working on. There are expressions, which compute new values from old ones. There are assignments which store values (of expressions, or other variables) into variables. 108Elements of Programming Languages There are conditionals which can be used to determine whether some condition is true, such as whether one number is greater than another. Variables and expressions may have types, indicating the nature of the expected values. There are statements which contain instructions describing what a program actually does. 109Elements of Programming Languages There are control flow constructs which determine what order statements are performed in. An entire set of statements, declarations, and control flow constructs can be lumped together into a function (also called routine, subroutine, or procedure) which another piece of code can then call as a unit. A set of functions, global variables, and other elements makes up a program. The source code for a program may be distributed among one or more source files.110Elements of Programming Languages Many of these elements exist in a hierarchy. A program typically consists of functions and global variables; a function is made up of statements; statements usually contain expressions; expressions operate on objects. Programfunctionsglobal variablesstatementsexpressionsobjects111112113Skills Needed in ProgrammingThe first hard thing about programming is to learn, become comfortable with, and accept some artificial mechanisms, whether they make “sense” to you or not. Attention to detailStupidityGood memoryAbility to abstract, think on several levels 114Attention to detailIn programming, the details matter. You cant be vague; you cant describe your program 3/4 of the way and then say “You know what I mean?” and have the compiler figure out the rest. You have to dot your is and cross your ts. If the language says you have to declare variables before using them, you have to. 115Stupidity Computers are incredibly stupid. They do exactly what you tell them to do: no more, no less. When youre programming, it helps to be able to “think” as stupidly as the computer does, so that youre in the right frame of mind for specifying everything in minute detail, and not assuming that the right thing will happen unless you tell it to. 116Good memory Things to remember while programming: the syntax of the languagethe set of prewritten functions and their parameters what variables and functions youve defined in your program and how youre using themtechniques youve used or seen in the past bugs youve had in the past. 117Ability to abstract One of the most powerful techniques for managing the complexity of a software system (or any complex system) is to compartmentalize it into little black box processes which perform useful tasks but which hide some details so you dont have to think about them all the time. Think about the mechanics of a design hierarchy, while also use that hierarchy to avoid having to think about every detail of it at every level. 118ObjectivesDefine algorithms.List the 5 essential properties of an algorithm.Define and use the three constructs for developingalgorithms: sequence, decision, and repetition.Understand and use three tools to represent algorithms: flowchart, pseudocode, and structure chart.Understand the concept of modularity and subalgorithms.List and comprehend common algorithms, such as sorting and searching. Differentiate between recursion and iteration.119ObjectivesHave a vision of computer language evolution.Distinguish between machine, assembly, and high-level languages.Distinguish between the different categories of languages: procedural, object-oriented, functional, declarative, and special.Understand the process of creating and running a program.Become familiar with elements of programming languages.120Thats all for this chapter!121