Microsoft Power Point - Algorithms.ppt [Compatibility Mode] PDF

Preview

Summary

Software Design and development for Year 12...

Description

Algorithms (Flowcharts and Pseudocode) Introduction

Objectives  What

is an algorithm?  What components does an algorithm have?  What is modularity?

What is an Algorithm? 

“Algorithm: a step-by-step procedure for solving a problem; programming languages are essentially a way of expressing algorithms.” … “Informally, an algorithm is a collection of instructions which, when performed in a specific sequence, produce the correct result. The study of algorithms is at the heart of computer science.” BOS



Given an initial state, execution of an algorithm should result in a recognisable end state.



An algorithm is: "A thing that does stuff"



What do we mean by a well-defined statement?  Intuitively, a statement (instruction) is well-defined if it explains to another person how to accomplish it.  You will never create an obsoletely precise algorithm.  You can construct algorithms that are logical, understandable and testable.  Your aim is to create an algorithm that a reader can “blindly” follow in order to accomplish the task.  Therefore: • Use keywords, standard symbols, and the standard control structures • Use meaningful names for your objects (variables, procedures, etc) • Modulise your algorithms (use sub-programs) • As a last resort, annotate your algorithm to add clarity.

An Algorithm   



An algorithm is not written in any particular programming language A computer program expresses (implements) an algorithm in a particular programming language A well written algorithm can be translated into any programming language (with varying degrees of difficulty) Algorithms can be expressed as pseudocode (textual) or as a flowchart (graphical).

An Algorithm   



An algorithm is not written in any particular programming language A computer program expresses (implements) an algorithm in a particular programming language A well written algorithm can be translated into any programming language (with varying degrees of difficulty) Algorithms can be expressed as pseudocode (textual) or as a flowchart (graphical).

Components of an Algorithm Algorithms typically: 

Acquire data (input) INPUT variablename or GET variablename or SET variablename



Manipulate data (processing)



Report the result (output) OUTPUT variablename or REPORT variablename or DISPLAY variablename

Stepwise Refinement  Each

step of an algorithm should be simple 

But what is simple?

 An

algorithm is organised in terms of levels of abstraction 



Higher levels give the general idea and basic steps Lower levels fill in the details

The Pie Example – part 1 

At a high level, making a pie may consist of the steps     

Prepare pie crust Place crust in dish Prepare filling Place filling in crust Bake pie



This high level abstraction only gives the general idea while hiding many of the details



This level of abstraction may be adequate for an experienced cook



A beginner cook will require the outline above to be broken down into simpler steps; it requires “refinement”

Stepwise Refinement This is also known as top-down design  The idea is to attack a large problem by breaking it up into smaller pieces  This process is repeated for each piece until the individual pieces are small enough  What is small enough? It depends on the knowledge of the person implementing the algorithm  Each module produces encapsulates the details of a particular step

The Pie Example – part 2 The steps previously provided were too coarse. 

Therefore we need to refine the modules that are too large or not detailed enough. eg:

Module 1: Prepare Pie Crust  In a large bowl, sift 2 C flour, 2 tsp baking powder and 1 tsp salt  Cut in ½ C shortening  Add ¾ cup milk  Stir to form dough  Roll crust on a floured surface to a thickness of 4mm 

Additional modules would be created for the remaining steps if they are required by the person implementing the algorithm

Modularity Advantages of modularity:  Makes the algorithm easier to design, understand, modify and fix  Information hiding: reduces the complexity of the algorithm by hiding details from higher levels of abstraction  Allows us to refer to a module by a simple name without worrying about how it performs its task  At the level of abstraction using the module, we only need to worry about what the module does, not how it does it  A module can be referred to many times  Each module can be built and tested separately

Sub Programs...