Computer Programming - Lecture 23

Computer ProgrammingLecture 23Summary of Previous LectureIn the previous lecture, we have learntIntellectual Property Types of Intellectual Property RightsCopyrightsPatentsTrade SecretsLawsEmployees and Trade SecretsKey intellectual Property Right IssuesPlagiarismReverse engineeringSummary of Previous LectureOpen source codeCompetitive intelligenceCyber squattingToday’s LectureProgramming in real life.IntroductionWhat is Problem Solving?Problem Solving process.AlgorithmHistoryWorking DefinitionExamplesToday’s LectureAlgorithms to ProgramsComponents of AlgorithmsVariables and valuesInstructionsSequencesProceduresSelectionsRepetitionsDocumentationToday’s LectureSoftware Development ProcessTop Down Algorithm DesignSummaryWhere is programming in real life?Short answer: all over the place!Where is programming in real life?Short answer: all over the place!Introduction People think in words: Like “The sky is so beautiful!” The computer understand in ‘binary’.Which just means ones and zeros: 00111000100111.“Programming languages” are different ways of taking your words and turning them into instructions that the computer can understand.IntroductionPrograms are a set of instructions for the computer.There are three levels of programming languages.Machine level, i.e.; direct hardware commandsMiddle level i.e.; Assembly languageHigher level i.e.; C, Java, C++, LISP etc.Don’t worry.Programming isn’t really that hard.The only thing you have to remember is that: THE COMPUTER IS STUPID. Even if you really, really want it to do something, it won’t do it unless you give it specific instructions! It only does what you tell it to do. the good news is that YOU are smart. so you can make the computer do really, really cool things.Problem solvingProgramming is a process of problem solvingProblem solving techniquesAnalyze the problem Outline the problem requirementsDesign steps (algorithm) to solve the problemHow do we solve problems?We "just do"Guesswork-and-luckTrial-and-errorExperience (possibly someone else's)"Scientifically"0100111010110010101010101001010101010100110010101010101001011010011101010101010010010111010011110101010111110101010001101sterilize(saw,alcohol);raise_hammer();lower hammer(fast);start(saw);/* etc. etc. */Patient has elevated pressure in anterior parietal lobeThe Problem-solving ProcessProblem specificationAlgorithmProgramExecutable (solution)DesignImplementationCompilation"Doctor, my head hurts"Analysis1. Sterilize cranial saw2. Anaesthetize patient3. Remove top of skull4. Get the big spoon...5. etc., etc.sterilize(saw,detol);raise_hammer();lower hammer(fast);start(saw);/* etc. etc. */The Problem-solving ProcessProblem specificationAlgorithmProgramExecutable (solution)AnalysisDesignImplementationCompilation"Doctor, my head hurts"Patient has elevated pressure in anterior parietal lobe.1. Sterilize cranial saw2. Anaesthetize patient3. Remove top of skull4. Get the big spoon...5. etc., etc.010011101011001010101010100101010101010011001010101010100101101001110101010101001001011101001111010101011111010101000110100001101...The Problem-solving ProcessProblem specificationAlgorithmProgramExecutable (solution)AnalysisDesignImplementationCompilationA sequence of instructions specifying the steps required to accomplish some task.The idea behind the computer programSolution achieved in finite amount of timeSolves a well-specified problem in a general wayFormally: “An algorithm is an ordered set of unambiguous executable steps, defining a terminating process.”AlgorithmAlgorithm –HistoryNamed after: Muhammad ibn Musa al-Khwarizmiعَبْدَالله مُحَمَّد بِن مُوسَى اَلْخْوَارِزْمِي of Khowarezm (now Khiva in Uzbekistan) Circa 780-850 C.E. (Common Era) was a Persian, mathematician, astronomer and geographer, a scholar in the House of Wisdom in Baghdad. Book on arithmetic:Hindu numeration, decimal numbers, use of zero, method for finding square rootLatin translation (c.1120 CE): “Algoritmi de numero Indorum” Book on algebraHisab al-jabr w’al-muqabala الكتاب المختصر في حساب الجبر والمقابلة Formally: “An algorithm is an ordered set of unambiguous executable steps, defining a terminating process.”Ordered set of steps: structure!Executable steps: doable!Unambiguous steps: follow the directions!Terminating: must have an end!Algorithm – Working DefinitionAlgorithm -- ExamplesA cooking recipeAssembly instructions for a modelThe rules of how to play a gameVCR instructionsDescription of a martial arts techniqueDirections for driving from A to BA knitting patternA car repair manualAlgorithm – Examples ..Recipe for Almond and honey sliceAlmond and Honey Slice1/2 quantity Shortcrust Pastry185 g unsalted butter100 g castor sugar5 tablespoons honey50 ml cream300 g flaked almondsPreheat oven for 200° CLine a 30 cm  20 cm baking tray with baking paper, and then with pastryBake blind for 20 minutes, then remove weights and foilTurn oven up to 220° C.Bring remaining ingredients to a boil, stirring.Spread evenly over pastry.Bake until topping is bubbling and has caramelised evenly, about 15 minutes.Cool before cutting into fingers or squares.From: Stephanie Alexander, The Cook’s Companion, Viking/Penguin, Ringwood, Victoria, 1996, p. 349.Almond and Honey Slice1/2 quantity Shortcrust Pastry185 g unsalted butter100 g castor sugar5 tablespoons honey50 ml cream50 ml brandy or any other liqueur or spirit300 g flaked almondsPreheat oven for 200° CLine a 30 cm  20 cm baking tray with baking paper, and then with pastryBake blind for 20 minutes, then remove weights and foilTurn oven up to 220° C.Bring remaining ingredients to a boil, stirring.Spread evenly over pastry.Bake until topping is bubbling and has caramelised evenly, about 15 minutes.Cool before cutting into fingers or squares.From: Stephanie Alexander, The Cook’s Companion, Viking/Penguin, Ringwood, Victoria, 1996, p. 349.Instructions are given in the order in which they are performed (“executed”)Correct Algorithm?Cut chicken into pieces and brown the pieces on all sides in a casserole dish in hot olive oil.Remove the chicken and to the juices in the casserole add garlic, onions and green peppers, and cook until onion is golden.Add bay leaf, whole tomatoes, and chicken soup.When the soup boils add salt, saffron and rice.Arrange chicken on rice, cover casserole and bake in a moderate oven (350°F) for 20 minutes or until the rice is tender.Add beans and artichokes during last 10 minutes of cooking.From: “Arroz Con Pollo” in The Margaret Fulton Cookbook, Hamlyn, Sydney, 1968. Cut chicken into pieces and brown the pieces on all sides in a casserole dish in hot olive oil.Remove the chicken and to the juices in the casserole add garlic, onions and green peppers, and sauté until onion is golden.Add bay leaf, whole tomatoes, and chicken broth.When the broth boils add salt, saffron and rice.Arrange chicken on rice, cover casserole and bake in a moderate oven (350°F) for 20 minutes or until the rice is tender.Add beans and artichokes during last 10 minutes of cooking.From: “Arroz Con Pollo” in The Margaret Fulton Cookbook, Hamlyn, Sydney, 1968. Correct Algorithm?Cut chicken into pieces and brown the pieces on all sides in a casserole dish in hot olive oil.Remove the chicken and to the juices in the casserole add garlic, onions and green peppers, and sauté until onion is golden.Add bay leaf, whole tomatoes, and chicken broth.When the broth boils add salt, saffron and rice.Arrange chicken on rice, cover casserole and bake in a moderate oven (350°F) for 10 minutes.Add beans and artichokes. Cover, and bake for another 10 minutes or until rice is tender.Correct Algorithm?From Algorithms to ProgramsProblemC ProgramAlgorithm: A sequence of instructions describing how to do a task (or process)Components of an AlgorithmVariables and valuesInstructionsSequencesProceduresSelectionsRepetitionsAlso required: DocumentationValuesRepresent quantities, amounts or measurementsMay be numerical or alphabetical (or other things)Often have a unit related to their purposeExample:Recipe ingredientsAlmond and Honey Slice1/2 quantity Shortcrust Pastry185 g unsalted butter100 g castor sugar5 tablespoons honey50 ml cream300 g flaked almondsPreheat oven for 200° CLine a 30 cm  20 cm baking tray with baking paper, and then with pastryBake blind for 20 minutes, then remove weights and foilTurn oven up to 220° C.Bring remaining ingredients to a boil, stirring.Spread evenly over pastry.Bake until topping is bubbling and has caramelised evenly, about 15 minutes.Cool before cutting into fingers or squares.From: Stephanie Alexander, The Cook’s Companion, Viking/Penguin, Ringwood, Victoria, 1996, p. 349.Almond and Honey Slice1/2 quantity Shotcrust Pastry185 g unsalted butter100 g castor sugar5 tablespoons honey50 ml cream50 ml brandy or any other liqueur or spirit300 g flaked almondsPreheat oven for 200° CLine a 30 cm  20 cm baking tray with baking paper, and then with pastryBake blind for 20 minutes, then remove weights and foilTurn oven up to 220° C.Bring remaining ingredients to a boil, stirring.Spread evenly over pastry.Bake until topping is bubbling and has caramelised evenly, about 15 minutes.Cool before cutting into fingers or squares.From: Stephanie Alexander, The Cook’s Companion, Viking/Penguin, Ringwood, Victoria, 1996, p. 349.VariablesThis jarcan contain 10 cookies50 grams of sugar 3 slices of cakeetc.ValuesVariable Are containers for values – places to store  values Example:Restrictions on VariablesVariables may be restricted to contain a specific type of valueComponents of an AlgorithmValues and VariablesInstruction (a.k.a. primitives)Sequence (of instructions)Procedure (involving instructions) Selection (between instructions)Repetition (of instructions)Documentation (beside instructions)Instructions (Primitives)Some action that is simpleunambiguousthat the system knows about......and should be able to actually doInstructions – ExamplesTake off your shoesCount to 10 Cut along dotted lineKnit 1Purl 2Pull rip-cord firmlySift 10 grams of arsenicDirections to perform specific actions on values and variables.Instructions -- ApplicationSome instructions can only be applied to a specific type of values or variablesExamples:ChopInstructions (Primitives) -- RecommendationsWhen writing an algorithm, make each instruction simple and unambiguousExample:Cut chicken into pieces and brown the pieces on all sides in a casserole dish in hot olive oil.Cut chicken into pieces.Heat olive oil in a casserole dish.Brown the chicken pieces in the casserole dish.ProcedureA named sequence of instructionsSo that you canRefer to it collectively (by name)...instead of individually (by each instruction in the sequence)Example:Drive_To_UniProcedure – following a sequence.Example procedure Drive_To_Uni { 1. find car keys 2. disable car alarm 3. open car door 4. get in car 5. shut car door 6. put keys in ignition 7. start car 8. back car out of  driveway 9. drive to end of street 10. turn right 11. drive to end of street 12. turn left ...etc...etc...etc ...etc...etc...etc... 52. find parking space 53. pull into parking  space 54. turn off engine 55. remove keys from  ignition 56. open car door 57. get out 58. shut car door 59. lock car door 60. enable alarm }Procedure – Example (cont)procedure Do_Wednesday{ Wake_up Have_Shower Eat_Breakfast Drive_To_Uni Sit_CS100_Lecture ...etc...etc...etc... Drive_From_Uni ...etc...etc...etc...}procedure Do_Week{ Do_Monday Do_Tuesday Do_Wednesday Do_Thursday ...etc...etc...etc...}Procedure – Example (cont)procedure Do_Wednesday{ Wake_up Have_Shower Eat_Breakfast Drive_To_Uni Sit_1301_Lecture ...etc...etc...etc... Drive_From_Uni ...etc...etc...etc...}In this subject, we also use the following words to refer to a “Procedure” :Sub-routineModuleFunctionProcedure – Example (cont)procedure Do_Wednesday{ Wake_up Have_Shower Eat_Breakfast Drive_To_Uni Sit_1301_Lecture ...etc...etc...etc... Drive_From_Uni ...etc...etc...etc...}We use brackets to mark the beginning and end of a sequence.Procedure – Example (cont)procedure Do_Wednesday{ Wake_up Have_Shower Eat_Breakfast Drive_To_Uni Sit_1301_Lecture ...etc...etc...etc... Drive_From_Uni ...etc...etc...etc...}An instruction invoking a procedure is known as a “procedure call”ProcedureA procedure may have a set of parametersprocedure customerService ( myName ,timeOfDay ){ say “Good timeOfDay” say “My name is myName” say “How can I help you?”}customerService ( “Ali”, “Morning” )customerService (“Jamil”, “Afternoon” )customerService ( “Shah”, “Afternoon” )Components of an AlgorithmValues and VariablesInstruction (a.k.a. primitives)Sequence (of instructions)Procedure (involving instructions) Selection (between instructions)Repetition (of instructions)Documentation (beside instructions)SelectionAn instruction that decides which of two possible sequences is executedThe decision is based on a single true/false conditionExamples:Car repairReciprocalsSelection Example -- Car Repairif (motor turns) then { CheckFuel CheckSparkPlugs CheckCarburettor}else { CheckDistributor CheckIgnitionCoil}Selection Example –Car Repair..if (motor turns) then { CheckFuel CheckSparkPlugs CheckCarburettor}else { CheckDistributor CheckIgnitionCoil}Should be a true or false condition.if (motor turns) then { CheckFuel CheckSparkPlugs CheckCarburettor}else { CheckDistributor CheckIgnitionCoil}Sequence if the condition is true.Selection Example –Car Repair..if (motor turns) then { CheckFuel CheckSparkPlugs CheckCarburettor}else { CheckDistributor CheckIgnitionCoil}Sequence if the condition is false. Selection Example –Car Repair..Selection Example -- ReciprocalsQ. Give an algorithm for computing the reciprocal of a number.Examples:Reciprocal of 2: 1/2Reciprocal of -3/4: 1/(-3/4) = -4/3Reciprocal of 0: “undefined”Selection Example – Reciprocals ..Q. Give an algorithm for computing the reciprocal of a number.Algorithm: input Num if (Num is not equal 0) then { output 1/Num } else { output "infinity" }Selection Example-- Reciprocals input Num if (Num is not equal 0) then { output 1/Num } else { output "infinity" }Algorithm:Num is a variable whose value depends on the actual number the user provides. Selection Example – Reciprocals input Num if (Num is not equal 0) then { output 1/Num } else { output "infinity" }Algorithm:Condition depends on the value of NumSelection Example – Reciprocals input Num if (Num is not equal 0) then { output 1/Num } else { output "infinity" }Algorithm:For a given value of Num, only one of these two sequences can be executedSelection Example – Reciprocals input Num if (Num is not equal 0) then { output 1/Num } else { output "infinity" }Algorithm:Executed if Num is not equal to 0 Selection Example – Reciprocals input Num if (Num is not equal 0) then { output 1/Num } else { output "infinity" }Algorithm:Executed if Num is equal to 0 Selection -- Exercise input Num if (Num is not equal 0) then { output 1/Num } else { output "infinity" }Will the following algorithms produce the same output?Algorithm 1: input Num if (Num is not equal 0) then { output 1/Num }output "infinity"Algorithm 2:Selection – Several ConditionsWhat if several conditions need to be satisfied?if ( today is Wednesday and the time is 10.00am ) then { Go to CS100 Lecture } else { Go to Library }Solution 1Selection – Several Conditions..Solution 2Often called a “nested selection” if ( today is Wednesday ) then { if ( the time is 10.00am ) then { Go to CSE1301 Lecture } } else ...etc...etc...etc...Selection – At Least One of Several ConditionsWhat if at least one of several conditions needs to be satisfied?if ( I feel hungry or the time is 1.00pm or my friend has his eye on my lunch )then { Eat my lunch now} Components of an AlgorithmValues and VariablesInstruction (a.k.a. primitives)Sequence (of instructions)Procedure (involving instructions) Selection (between instructions)Repetition (of instructions)Documentation (beside instructions)RepetitionRepeat an instruction......while (or maybe until) some true or false condition occursTest the condition each time before repeating the instructionAlso known as iteration or loopExample:Algorithm for getting a leave from the class.Repetition -- Exampleprocedure getleave ( teacher, course, time){ reach_to(teacher) Say(“Hello", teacher, “I am feeling fever!") Say(“I want leave in ", course, "at", time, "?") ListenToReply ( )start begging count at zerowhile (reply is "No" and begging count < 100){ Say("please!") add 1 to begging count ListenToReply ( )}}Repetition – Example (cont)procedure getleave ( teacher, course, time){ reach_to(teacher) Say(“Hello", teacher, “I am feeling fever!") Say(“I want leave in ", course, "at", time, "?") ListenToReply ( )start begging count at zerowhile ( reply is "No" and begging count < 100 ){ Say("please!") add 1 to begging count ListenToReply ( )}}Condition is tested before sequenceRepetition – Example (cont)procedure getleave ( teacher, course, time){ reach_to(teacher) Say(“Hello", teacher, “I am feeling fever!") Say(“I want leave in ", course, "at", time, "?") ListenToReply ( )start begging count at zero while (reply is "No" and begging count < 100){ Say(“Please!") add 1 to begging count ListenToReply ( )}}Sequence may not get executed at all Repetition – Example (cont)procedure getleave ( teacher, course, time){ reach_to(teacher) Say(“Hello", teacher, “I am feeling fever!") Say(“I want leave in ", course, "at", time, "?") ListenToReply ( )start begging count at zerowhile (reply is "No" and begging count < 100){ Say(“Please!") add 1 to begging count ListenToReply ( ) }}Ensure initial values of variables used in the conditions are set correctly Repetition – Example (cont)procedure getleave ( teacher, course, time){ reach_to(teacher) Say(“Hello", teacher, “I am feeling fever!") Say(“I want leave in ", course, "at", time, "?") ListenToReply ( )start begging count at zero while (reply is "No" and begging count < 100){ Say(“Please!") add 1 to begging count ListenToReply ( ) }}Ensure the variables used in the conditions are updated in each iterationRepetition – Example (cont)procedure getleave ( teacher, course, time){ reach_to(teacher) Say(“Hello", teacher, “I am feeling fever!") Say(“I want leave in ", course, "at", time, "?") ListenToReply ( )start begging count at zerowhile (reply is "No" and begging count < 100){ Say("please!") }}Infinite loop What if we don’t increment the begging count?DocumentationRecords what the algorithm doesDescribes how it does itExplains the purpose of each component of the algorithmNotes restrictions or expectationsExample:Getting a leave (again)Components of an AlgorithmValues and VariablesInstruction (a.k.a. primitives)Sequence (of instructions)Procedure (involving instructions) Selection (between instructions)Repetition (of instructions)Documentation (beside instructions)The Software Development ProcessWe have covered this topic in Lecture 7 “Database systems”.Same process is followed to develop a computer program.Top-down Algorithm DesignWrite down what you have to doBreak that into 3-7 smaller stepsBreak each step into 3-7 smaller stepsKeeping subdividing until each individual step is easy enough to do – i.e., until it is a single instructionExample:LearningTop-down Design -- ExampleLearnPrepareStudyReinforceReadMake notesPrepare questionsAttend lectureListen and thinkComplete pracAttend tuteRecord answers to questionsRevise notesRead lecture notesRead textbookRead exerciseDesign algorithmCode solutionTest and documentRecord insightsSummaryProgramming is the way to instruct the computer what to do?Users set of computer instructions to be executed by the computer.Different levels of programming exists.Algorithms are developed before making a program to set a procedure.Remember “Computers are stupid” means you need to teach them step by step each and every instruction, they can not do it by themselves.