1Algorithms, Part 1 of 3Topics Definition of an Algorithm Algorithm Examples Syntax versus SemanticsReading Sections 3.1 - 3.3Problem Solving Problem solving is the process of transformingthe description of a problem into the solution ofthat problem. We use our knowledge of the problem domain. We rely on our ability to select and useappropriate problem-solving strategies,techniques, and tools.Algorithms An algorithm is a step by step solution to aproblem. Why bother writing an algorithm? For your own use in the future. You won’t have torethink the problem. So others can use it, even if they know very littleabout the principles behind how the solution wasderived.2Examples of Algorithms Washing machine instructions Instructions for a ready-to-assemble piece offurniture A classic: finding the greatest common divisor(GCD) using Euclid’s AlgorithmWashing Machine Instructions Separate clothes into white clothesand colored clothes. Add 1 cup of powdered laundrydetergent to tub. For white clothes: Set water temperature knob toHOT. Place white laundry in tub. For colored clothes: Set water temperature knob toCOLD. Place colored laundry in tub. Close lid and press the start button.Observations About the WashingMachine Instructions There are a finite number ofsteps. We are capable of doing eachof the instructions. When we have followed all ofthe steps, the washing machinewill wash the clothes and thenwill stop.3Refinement of Algorithm Definition Our old definition: An algorithm is a step by step solution to a problem. Adding our observations: An algorithm is a finite set of executable instructionsthat directs a terminating activity.Instructions for a Ready-to-AssemblePiece of Furniture "Align the marks on side Awith the grooves on Part F.“ How could theseinstructions be hard tofollow? Which side is A? A & B lookalike -- both line up with PartF! This instruction isambiguous.Final Version of the Algorithm Definition Our old definition: An algorithm is a finite set of executable instructionsthat directs a terminating activity. Final version:An algorithm is a finite set of unambiguous,executable instructions that directs a terminatingactivity.4History of Algorithms The study of algorithms began as a subject inmathematics. The search for algorithms was a significantactivity of early mathematicians. Goal: To find a single set of instructions that canbe used to solve any problem of a particulartype (a general solution).Euclid’s AlgorithmProblem: Find the largest positive integer thatdivides evenly into two given positive integers(i.e., the greatest common divisor).Algorithm:1 Assign M and N the values of the larger andsmaller of the two positive integers, respectively.2 Divide M by N and call the remainder R.3 If R is not 0, then assign M the value of N, assignN the value of R, and return to Step 2. Otherwise,the greatest common divisor is the value currentlyassigned to N.Finding the GCD of 24 and 9M N R24 9 6 9 6 3 6 3 0So, 3 is the GCD of 24 and 9.5Euclid’s Algorithm (con’t) Do we need to know the theory that Euclid usedto come up with this algorithm in order to use it? What intelligence is required to find the GCDusing this algorithm?The Idea Behind Algorithms Once an algorithm behind a task has beendiscovered We don't need to understand the principles. The task is reduced to following the instructions. The intelligence is "encoded into the algorithm."Algorithm Representation Syntax and Semantics Syntax refers to the representation itself. Semantics refers to the concept represented (i.e.,the logic).6Contrasting Syntax and Semantics In the English language, we have both syntax andsemantics. Syntax is the grammar of the language. Semantics is the meaning. Given the following sentence,I walked to the corner grocery store. Is this sentence syntactically correct? Is it semantically correct?Contrasting Syntax and Semantics Given the following sentence,I talked to the funny grocery store. Is this sentence syntactically correct? Is it semantically correct? How aboutI grocery store walked corner the to.Contrasting Syntax and Semantics Conclusion: An Englishsentence may be syntacticallycorrect, yet semanticallyincorrect. This is also true of algorithms. And it is also true of
View Full Document
Unlocking...