CS22 : Break it down


This section introduces all the major programming paradigms and considers why they may be needed. Then we move on to look at procedural programming in particular and why programmers break problems down into smaller, more manageable parts.

We are learning ...
  • About the major programming paradigms
  • How to break down computational problems to make them easier to solve.
So that we can ...
  • Describe different programming paradigms
  • Understand that computational problems can be broken down into smaller, more manageable parts
  • Use structure charts to represent the flow of data
  • State the two types of subroutine and the differences between them
  • State the difference between local and global variables
  • Describe the effect of passing variables by reference and by value


Activity 1 What is a programming paradigm?

A programming paradigm is a fundamental style of computer programming; a way of building the structure and elements of a computer program.


Task 1.1
 Comparing paradigms
Web browser

Use the World Wide Web to research, and define, the following programming paradigms. For each one, give two examples of languages which conform to each paradigm and the type of problem which may be solved using the techniques. You may start with the Wikipedia article.
  • Structural
  • Imperative
  • Procedural
  • Object oriented
  • Functional
  • Event driven
  • Declarative
The ones in bold are considered (by some) to be the main programming paradigms. What is your view?

OUTCOME : A set of notes / mindmap of the main programming paradigms plus examples and applications where appropriate.

Why so many?

As you will see, there are a wide variety of 'ways' of programming, each suited to a particular problem. It's a bit like cooking - the problem of how to serve my egg can be solved in many different ways depending on the situation.


We won't go into too much more depth yet - at this level, we are only really focusing on one type of programming style which is imperative / structural. So, here we go ...

Why structure?
Stay tuned ...


Activity 2 Top down design / stepwise refinement

This strategy can be applied, not just to programming, but to anything in life. Like the old joke goes ...

Answer : One piece at a time!

"Are we nearly there yet?"

Let's say that (for some reason) I wanted to travel from Badsey nr Evesham to the nearby village of Bretforton. A quick search on Google Maps reveals this route ...

http://drive.google.com/uc?export=view&id=0B83yXMOilskaNkl3TjZZeWZjbm8
Click to enlarge, or visit the actual map.

Google Maps neatly decomposes (breaks down) the journey into separate, smaller parts, each one of which must be nagivated before the next one can be started. It's possible to represent the journey using a Structure Table ...

0 Badsey to Bretforton

  0.1 Take High St and Synehurst to Bretforton Rd / B4035

      0.1.1 Head north-west on Sands Ln towards Binyon Cl
      0.1.2 Turn right onto Willersey Rd
      0.1.3 Turn left onto School Ln
      0.1.4 Turn right onto High St
      0.1.5 Continue onto Synehurst

  0.2 Turn right onto Bretforton Rd / B4035

  0.3 Drive to Orchard Cl

      0.3.1 Turn left onto Orchard Cl
      0.3.2 Turn left to stay on Orchard Cl


The depth we require in this structure table in order to complete the task will clearly depend on our experience of the situation. In any event, it's possible to represent the journey in three Levels of Refinement.

Level Zero
0 Badsey to Bretforton


Level One
0.1 Take High St and Synehurst to Bretforton Rd / B4035
0.2 Turn right onto Bretforton Rd / B4035
0.3 Drive to Orchard Cl

Level Two

0.1.1 Head north-west on Sands Ln towards Binyon Cl
0.1.2 Turn right onto Willersey Rd
0.1.3 Turn left onto School Ln
0.1.4 Turn right onto High St
0.1.5 Continue onto Synehurst
0.3.1 Turn left onto Orchard Cl
0.3.2 Turn left to stay on Orchard Cl


We can also represent this journey as a Hierarchy Chart ...


Can you see how the Structure Table, the Levels of Refinement and the Hierarchy chart all represent the solution of the same problem? Breaking down a problem like this into smaller parts is called decomposition / top-down design or stepwise refinement.

Task 2.1
 A trip ...

Time for you to apply your understanding to a particular problem. Ready?

So, I need to travel from my farm in Hutton, nr Preston to my friends house in Penwortham ...


Visit this Google Maps page and use the suggested route to construct a Structure Table, Levels of Refinement and a Hierarchy Chart for my journey.

OUTCOME : Decomposed journey from Hutton to Penwortham.


Yipee, maths!

Look at this example from the world of Mathematics - the quadratic formula. In elementary mathematics, the quadratic formula is a fast way of finding a solving a given quadratic equation.


This equation actually represents two processes - one where the second term in the numerator is added and one where it is subtracted. Let's concentrate on just one of them and develop a simple hierarchy chart.


Notice that, in this situation, each subsequent level is designed to perform any calculations on which aspects of the higher levels demand are completed before they can be. Eventually, everything cascades up to the highest level and we have the answer - voila!

Task 2.2
 Speed of an oscillating body!

You may (or may not) be familiar with the method of calculating the speed of an oscillating body. I know I'm not. However, should you care, the formula for it's derivation is as follows ...


Draw a suitable hierarchy chart for one of the two situations described here.

OUTCOME : Hierarchy chart to work out the answer to a formula you've never seen before.


Yum, dinner!

Finally, how about this simple example ...

Task 2.3
 Roast dinner

A meal consists of soup, followed by a main course, followed by ice cream.  The main course consists of beef, potatoes, peas to be served in that order.  Draw a hierachy chart for the meal.

OUTCOME : Hierarchy chart about my dinner

https://drive.google.com/file/d/0B83yXMOilskaR0VMRXVQUlFnYlU/view?usp=drive_web


Activity 3 Structured programming

When coding structured programs, we can take a number of approaches ...
  • Focus on handling Input, Processing, Storage and Output in separately
  • Focus on solving smaller parts of the problem first before combining the solutions
To represent solution to problems in a structured way, we use a diagram similar to a hierarchy chart but which attempts to show the flow of data around our system. These diagrams are called Structure Charts. Structure charts are similar to hierarchy charts in that they split a problem into smaller parts but they also describe how data passes between those parts. Technically, the smaller parts of programs are called subroutines.

Subroutines, parameters and return values

https://drive.google.com/file/d/0B83yXMOilskad0ZKd2hmN0E3MGs/view?usp=drive_web

When you are coding structured solutions, you use subroutines to break up the problem into smaller parts. There are two types of subroutine ...
  • Procedures may or may not take parameters and never return any values;
  • Functions may or may not take parameters and always returns one or more values.
When a function returns a value, it must be caught be a variable by assigning it to the function call itself.

NOTE : In Python, no distinction is made between procedures and functions in code - they are both called functions. In Python, a function is a procedure which returns a value. In other languages you may find that you define functions and procedures differently.

https://drive.google.com/file/d/0B83yXMOilskacnZRY09YRHF0Vjg/view?usp=drive_web

Task 3.1
 Grade calculator and other problems

STAGE ONE

In your notebooks
 : Explain the difference between a function and a procedure.

STAGE TWO

Look carefully at the structure chart below. You will be provided with a copy for your notebooks .

https://drive.google.com/file/d/0B83yXMOilskaZWFEcUhjNElMYkU/view?usp=drive_web
Click to enlarge

There are a few symbols in this structure chart that we haven't met before. First, download Components of a structure chart.docx and stick it in your notebooks. Next, download the Python script gradeCalculator.py, save it in a suitable place in your user area, find it and right click > Edit with Idle to up the script up so you can inspect it's contents. Print a copy for your notebooks using Notepad++ or equivalent.

In your notebooks : write about the following aspects of the code ...
  • The realisation of the separate modules in the structured solution as subroutines (functions);
  • The ways in which parameters are passed into a subroutine;
  • The ways in which return values are 'caught' using variable assignment;
  • The realisation of the repetition in the processRawMarks subroutine;
  • The realisation of selection in the checkBoundary subroutine;
  • The use of the STOP flag and whether it's really necessary.
Discuss your answers with your teacher before you move on.

STAGE THREE

Now try to construct suitable scripts to represent the following structured solutions. For each one, use the template.py file (available from the lesson resources) to write your script. The original file is read only so you will have to save a fresh copy of the file before you run it.

Fahrenheit to Celsius converter

https://drive.google.com/file/d/0B83yXMOilskacnV2MXF3Q1dCdXM/view?usp=drive_web Write a script using structured programming techniques which asks the user for a temperature in degrees Fahrenheit, converts this into Celsius and displays the result. Use the structure chart to help you.

HINT : You may need to look online to find the formula for conversion of Fahrenheit to Celsius.

Test Data
a) 32°F gives 0.00°C
b) 100°F gives 37.78°C
c) 212°F gives 100.00°C
https://drive.google.com/file/d/0B83yXMOilskabHFPNzZRbzk5c3M/view?usp=drive_web
Click to enlarge

Calculate basic and overtime pay

https://drive.google.com/file/d/0B83yXMOilskaYUpENFVVdlNMbE0/view?usp=drive_web Write a script using structured programming techniques which calculates the pay of an employee. The solution should ask the user for the total number of hours worked and the basic rate of pay. It should then calculate the basic pay and any overtime the employee worked which is over and above 5 hours at 'time and a half'. The employees total pay should be displayed. Use the structure chart below to help you.

Test Data
a) Hours = 3, Rate = 4.00 gives Pay = 12.0
b) Hours = 5, Rate = 4.00 gives Pay = 20.0
c) Hours = 7, Rate = 4.00 gives Pay = 32.0
https://drive.google.com/file/d/0B83yXMOilskaMktYRUJybV9aeGM/view?usp=drive_web
Click to enlarge

Dice throw

https://drive.google.com/file/d/0B83yXMOilskaX0tpaVlsbDRxYWc/view?usp=drive_web Write a script using structured programming techniques which works out the sum of a fixed number of dice throws. The script should ask the user for the number of rolls required, calculate the sum of that many random dice throws and output the total to the screen. Use the structure chart to help you.

HINT : You will have to use the random module to help you choose a random number.

Test Data
a) Dice = 1 gives Total between 1 and 6
b) Dice = 5 gives Total between 5 and 30
c) Dice = 10 gives Total between 10 and 60

https://drive.google.com/file/d/0B83yXMOilskaWVJJVHEtR0MyX3c/view?usp=drive_web
Click to enlarge


When you have got your scripts running, ask your teacher for his / her solutions and
compare yours to theirs. Are they the same or different? If they are different,
is the difference important? Can you see any advantages or disadvantages to
this method of programming?


OUTCOME : Structured scripts for three situations.


Local and global variables

If you are not careful when you are coding in this way, you often find that variables that you use appear not to exist in other subroutines - they have to be explicitly passed as parameters. Variables which are declared outside subroutines are classed as global and are available to all subroutines. Variables which exist either as parameters to the function or are used within the function are local and are only available within that subroutine.

https://drive.google.com/file/d/0B83yXMOilskaZVhNR0lNUzRTa3M/view?usp=drive_web
Confused? You bet!

As a general rule, global variables should be avoided as their content can be unpredictable because they can be altered from anywhere in the code.

https://drive.google.com/file/d/0B83yXMOilskaWHhLVW1BdzM3MHc/view?usp=drive_web
Yeah but we still need to learn about it!

Task 3.2
 I love Paris

Download the script globalAndLocal.py from the lesson resources (which is actually the script from the image above). Open the script in IDLE and run it. Confused?

In your notebooks : Explain what is happening. Try to use the words 'local' and 'global' as many times as you can!

OUTCOME : Vague awareness of the difference between local and global variables


By Reference / By Value / By George

NEW SECTION


Features of structured programming

Programming is such a complicated business that the chances of you being completely structured in your approach is unlikely. However, making sure that your code has the following features will help ...
  • Breaking code up into subroutines with sensible interfaces;
  • Subroutines execute atomic tasks;
  • Using parameters to pass values;
  • Avoiding global variables;
  • Using meaningful identifiers;
  • Effective use of indentation;
  • Use of named constants.

https://drive.google.com/file/d/0B83yXMOilskaTk1FTFdfV05QcVE/view?usp=drive_web

Task 3.3
 Muppetry

Consider the following example. A program is written which strips vowels from a sentence. Unsurprisingly, the program is called vowelRemover.py. There are two different versions of vowelRemover.py available from the lesson resources, one is (structured) and one is (unstructured). You could download them if you wish, but it will suffice to look at them here ...

https://drive.google.com/file/d/0B83yXMOilskaTDFiY1BoOEFmcms/view?usp=drive_web
'Unstructured' vowel remover program

https://drive.google.com/file/d/0B83yXMOilskabHRGZUp6RzVGM1k/view?usp=drive_web
'Structured' vowel remover program

For arguments sake, let's assume that the 'structured' version is a) clearer to follow and b) more efficient than the 'unstructured' version (yeah, yeah). With that view in mind ...

... download and complete the worksheet Muppetry.docx from the lesson resources.

OUTCOME : Completed worksheet.


Extension Activities 

How about these?
  • Another similiar structured programming is called 'Jackson Structured Programming' and was invented by Micheal A. Jackson in 1975. It's similiar to normal structured programming but uses different methods of representing iteration and selection.

  • Before the days of procedural programming, the only real way of structuring code was to use the dreaded GOTO statement. In practice, this often lead to Spaghetti code.
https://drive.google.com/file/d/0B83yXMOilskaNGZmNUNlS2U1eDQ/view?usp=drive_web

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT