Program Development

Objectives

Program Development: Five Steps







1E3Topic 5

5 Program Development

5 Program Development

1

Programming and Problem Solving 





A sequence of precise instructions which leads to a solution



Program 



An algorithm expressed in a language the computer can understand 5 Program Development

2

Programming Process

Algorithm 

This topic introduces programming as a problem solving discipline. It presents a five step procedure for program development. At the end of this topic you should be able to develop more complex programs using a systematic approach.



3

Up till now we’ve gone straight to programming. For big complex problems we need to be more systematic. We need “solve the problem” and “map out a solution” before trying to code it in C++. This is where algorithms in pseudocode come in.

5 Program Development

4

1

Program Design 

Problem Solving Phase Step 1: Understand the Problem

Programming is a creative process  

No complete set of rules for creating a program It takes lots of practice.

  



Program Design Process 

Problem Solving Phase 



Step 2: Do a small example by hand

Result is an algorithm that solves the problem

Step 3: Write an algorithm to solve the problem

Implementation Phase 

Result is the algorithm translated into a programming language 5 Program Development



Use pseudocode

5

5 Program Development

Implementation Phase

6

Example: Better-valued Pizza

Step 4: Translate the algorithm into a programming language Step 5: Test the program Testing may result in Compilation (parse) errors Logic errors Errors will require you to return to some step. 5 Program Development

What is the input? What is the output? What is the relationship between the input and output? What formulas or techniques do we need?

7

 

Consider Practical 2. Step 1  



Input: diameter and price of two pizzas Output: the diameter of the better valued pizza, based on price per sq. inch Info required: 

Price per square inch is price/area Area of a circle is (pi * radius * radius)



Radius is diameter/2



5 Program Development

8

2

Testing for Primality: Step 2 

Step 2: Work examples by hand 



Given a 10 inch costing 12 euro and a 12 inch costing 15 euro    



Better-value Pizza : Step 3 Step 3: Write an algoritm 

Area of 10 inch pizza is … 78.5 Price per sq inch is 12/78.5 or 15 cents

 Algorithm  pseudocode

12inch 113 sq inches; 15/113 = 13.26 cents per sq inch… Since ppsi of 12 inch is smaller it is better value

This step is more useful for other problems 

But it might have helped avoid people doing 

Area/price !!! Or ppsi1 < ppsi2 => No.2 is better value!!!!

5 Program Development

9

5 Program Development

Definition: Algorithm 

An algorithm is an



ordered set of unambiguous  executable steps  that defines a terminating process. 

F = (9/5)C+32  Multiply the celsius reading by 9, then divide by 5, then add 32. 

Though some examples may have ambiguity!! 5 Program Development

An algorithm can be represented in many ways. 

Recipes, route directions, knitting instructions, assembly instructions are all examples. 

10

Algorithm Representation





Before looking at Step 3 let’s look more closely at the meaning of

11

A program is one formal representation of an algorithm designed for execution on a computer. 5 Program Development

12

3

Knitting pattern Extract

Algorithmic Primitives 



We need representations that are detailed enough to allow the algorithm to be implemented. Define primitives 



5 Program Development

Building blocks for constructing algorithmic representations.

Example: Knitting instructions .. (k2, p2) twice

13

5 Program Development

Languages 

 

 

Pseudocode (1)

A language consists of 



Primitives Syntax for how to combine the primitives Semantics - meaning of the primitives and the combinations



15

a <- expression

A is given the value of the expression

SELECT



Known as pseudocode 5 Program Development

ASSIGN 

A programming language like C++ is an example. But we will now look at a less formal language for algorithm design. 

14

IF condition THEN activity ELSE activity

IF balance < 0 THEN print “Overdrawn” ELSE print “In credit” 5 Program Development

16

4

Pseudocode (2) Repetition 

LOOP 



Pseudocode (3) Abstraction

WHILE condition DO activity



WHILE there are more names in the hat DO draw a name and print it



ITERATE

FOR EACH of a set of items DO activity  FOR EACH integer between 1 and 100 DO print the number squared 5 Program Development



The preceding primitives are enough to specify all algorithms. However we will also use procedural abstraction to create pseudocode algorithms. Abstraction means identifying and naming an algorithm and then using that name to carry out that algorithm.

17

5 Program Development

Pseudocode (3) Abstraction 





Abstraction contd./

Procedural abstraction 







 Means

names.

procedure sqrt (x) {algorithm for computing sq. root} sqrt (789.54) 

Example 2 procedure sort (list) {algorithm for sorting a list}  sort (list-of-names)

Give a name to an algorithm Use the name to execute that algorithm within another one.

Example 



Means APPLY the sqrt procedure to the number 789.54.

5 Program Development

18

19

APPLY the sort procedure to the list of

Abstraction allows you to separate details of how to carry out the procedure from the algorithm that uses the procedure. 5 Program Development

20

5

Writing pseudocode 



 

Better-value Pizza: Step 3 1. Read in the diam and price of the first pizza. 2. ppsi1 <- the price per sq. inch of the first pizza 3. Read in the values for the second pizza. 4. ppsi2 <- the price per sq. inch of the second pizza. 5. IF ppsi1 < ppsi2 THEN first pizza is better value ELSE second pizza is better value.

Pseudocode is informal and can be adapted to fit your needs BUT you must avoid writing sweeping commands that hide all the interesting detail! Use indentation to help readability. Use brackets to help readability/ambiguity. 5 Program Development

More detail may be provided in this step, such as how to compute ppsi. 21

5 Program Development

Same algorithm but using ABSTRACTION

Step 4: Implement in C++ 

1. Read in the diam and price of the first pizza. 2. ppsi1 <- ppsi (diameter1, price1) 3. Read in the values for the second pizza. 4. ppsi2 <- ppsi (diameter2, price 2) 5. IF ppsi1 < ppsi2 THEN first pizza is better value ELSE second pizza is better value. FUNCTION ppsi (diameter, price) returns the price per square inch of a pizza diameter inches wide costing price euros. RETURN price / (PI * diam/2 * diam/2) 5 Program Development

22



 



23

Implement the algorithm in C++ This step is relatively straightforward for the pizza algorithm. See solution. In other cases it involves some ingenuity. Sometimes at this stage you discover that your algorithm is inadequate and have to go back to Step 3, or earlier. (We’ll be looking at how to implement procedural abstraction next.) 5 Program Development

24

6

Step 5: Testing   



Another Sample Algorithm

Good testing is crucial. Don’t assume that any answer is correct! Try a variety of test cases that test different paths of your program. Developing test data is a whole science in itself!

 



Write a program to print the perfect numbers between 1 and an entered number. A positive whole number is ‘perfect’ if the sum of its divisors (apart from itself) equals the number. Step 1:   

5 Program Development

Input : an integer Output : the perfect numbers between 1 and the entered integer Info needed: definition of “perfect number” above.

25

5 Program Development

Perfect Numbers Step 2 

Is 4 perfect?



Is 6 perfect?









Perfect numbers Step 3

Try to do it yourself 

 

Factors are 1 and 2; 1 + 2 = 3; not 4; not perfect.

Get number from user FOR n from 1 to entered number 

Factors are 1, 2, 3; 1+2+3=6; 6 is perfect.



Try 1, 2, 10, 12, …



we need to test each integer from 1 to n-1 to see if it’s a factor; if it is add it to a running total. If the running total ends up equal to n, n is perfect print it out. 5 Program Development

Sum <- 0 FOR i from 1 to n {

So for each number n to be checked 

26

27





IF i is a factor of n THEN add i to sum }

IF sum = n THEN print n “is perfect”

5 Program Development

28

7

Perfect numbers Step 4 

    

Perfect numbers Step 5

Implementing the algorithm in C++ is straightforward. See allperfectnumbers.cpp Remember to use == for equality tests! Declare variables. Check that they all get initialised. Be very careful with { } braces

5 Program Development

  

Compile , run and check. Is the output what you expect given step 2? If there are logic errors you can’t find 



What happens if the user’s input is invalid? 







5 Program Development

30

Practical 6 continued

Apply the 5 step process to Practical 6. Step 1: Make sure you understand what the input is and how you are to compute the output. Step 2: Work the example given and a few more to get a sense of the algorithm Step 3: Sketch the algorithm before trying to code it. 5 Program Development

We have ignored this problem so far, for simplicity, but in general all inputs should be checked for validity before use.

29

Practical 6 

Add debug output statements.

31

 

Step 4: Implement the algorithm in C++. Step 5: Test 

Check at least  No

overtime and some overtime at 20% and some at 40% tax  Where tax credit covers full tax liability and where it doesn’t.  Boundary conditions : 0 hours, 40 hours, 0 euro per hour, 200 euro gross, and tax = tax credit.  All

5 Program Development

32

8