Program Design
7/25/2006 1
Problem Solving
Start with a real-world problem that needs to be
solved
Convert the real-world problem into a
computational problem
Develop an algorithm and use it to solve the
computational problem
An algorithm is a precise list of instructions that
determine what operations to perform on what
pieces of data, in what order
2
Algorithm Example
Consider the problem of computing the sum of 2
numbers which are entered by the user at the keyboard:
Possible algorithm to solve the problem:
Read (i.e. input) the first number and store it in the
computer
Read the second number and store it in the
computer
Add the first number to second number to produce
a sum, SUM. Store SUM in the computer
Display (i.e. output) the value of SUM
3
Computer Programming
A computer is a machine that can compute
What does “compute” mean ?
Can represent & manipulate data
Programming is about finding a way to tell the machine
what computational operations it must do on what data
A program is just an algorithm, expressed in a
language the computer an understand
4
Programming Overview
Program Design Process has 2 phases:
Problem Solving Phase
Creates an algorithm that solves the
problem
Implementation (Coding) Phase
Translates the algorithm into a
programming language
5
Design Tool: Pseudocode
Pseudocode
Generic way of describing an algorithm, without
use of any specific programming language
Helps programmers to plan an algorithm
Not an actual programming language, but may
borrow syntax from popular programming
languages
Styles vary
6
Pseudocode Example
Example Problem: Calculate the bill when someone
buys a specific number of some item:
Pseudocode:
PROMT for number of items being purchased
READ number of items being purchased
PROMPT for price per item
READ price per item
CALCULATE subtotal
CALCULATE tax
CALCULATE total
DISPLAY total
7
Common Pseudocode
Keywords
When describing input, output, computations, etc,
the following terms are often used:
Input: INPUT, READ, GET
Output: PRINT, DISPLAY, SHOW, PROMPT
Compute: COMPUTE, CALCULATE, DETERMINE
Initialize: SET, INIT
Add one: INCREMENT, BUMP
Decisions: TEST, IF/THEN/ELSE, WHILE/DO
8
Writing Pseudocode
Algorithms
Be certain the task is completely specified!
Questions to ask:
What data is known before the program runs?
What data must be input by the user?
What computations will be performed on the
data?
What data will be output (displayed) to the
user?
9
Pseudocode Sequential
Algorithm Example (1/2)
Real World Problem:
Calculate your two childrens’ allowances, based upon
75 cents per year old.
Known Values
Rate = 75 cents per year
Inputs
Ages of children
Calculations
Allowance = Age x Rate
Outputs
Allowances for each child
10
Pseudocode Sequential
Algorithm Example (2/2)
Pseudocode Algorithm:
PROMPT for Age of Child1
READ Age of Child1
PROMPT for Age of Child2
READ Age of Child2
CALCULATE
Allowance for Child1 = Age of Child1 x Rate
CALCULATE
Allowance for Child2 = Age of Child2 x Rate
DISPLAY Allowance for Child1
DISPLAY Allowance for Child2
11
Sequential
Program Statements
With sequential program statements, you
execute one statement after another (like steps
in a list)
After step X is completed, step X+1 will be
performed, until the last statement has been
executed.
Every step in the list will be performed.
Each step in the list will be performed once and
only once.
12
Non-Sequential
Program Statements
Programs that execute only sequential program
statements are pretty simplistic.
Most programs need more flexibility in the order
of statement execution.
The order of statement execution is called the
flow of control.
Control statements allow the execution of
statements based upon decisions.
13
Flow of Control Statements
Conditional statements:
Decide whether or not to execute a particular
statement or statements
Also called the selection statements or decision
statements.
Pseudocode Example:
IF HoursWorked over 40
THEN DISPLAY overtime pay
ELSE DISPLAY regular pay
14
Pseudocode Selection
Algorithm Example (1/2)
Real World Problem:
Calculate one child’s allowance, based upon 75 cents per
year old if s/he is under 10, and $1 per year if 10 or over.
Known Values
YoungRate = 75 cents per year
OlderRate = 100 cents per year
BreakAge = 10
Inputs
Age of child
Calculations
Allowance = Age x Rate
Outputs
Allowance
15
Pseudocode Selection
Algorithm Example (2/2)
Pseudocode Algorithm:
PROMPT for Age
READ Age
IF Age less than 10
THEN CALCULATE Allowance = Age x YoungRate
ELSE CALCULATE Allowance = Age x OlderRate
DISPLAY Allowance
16
Flow of Control Statements
Loop statements:
Repeatedly execute the same statement(s) for a
certain number of times or until a test condition is
satisfied.
Pseudocode Example:
WHILE Population UNDER Limit DO
COMPUTE Population = Population + Births - Deaths
17
Pseudocode Looping
Algorithm Example (1/2)
Real World Problem:
Calculate the total allowance paid to each of three
children at $1 per year old.
Known Values
Rate = $1 per year
NumKids = 3
Inputs
Ages of children
Calculations
Allowance = Age x Rate
Outputs
Total Allowance paid
18
Pseudocode Looping
Algorithm Example (2/2)
Pseudocode Algorithm:
Set KidsPaid to 0
Set Total to 0
WHILE KidsPaid under 3 DO
PROMPT for Age
Read Age
CALCULATE Allowance = Age x Rate
ADD Allowance to Total
INCREMENT KidsPaid
DISPLAY Total
19
Flow Control Design Tool:
Flowcharts
Flowchart - a graphical way of writing algorithms
Rectangle is used for calculations
Parallelogram is used for input and output
Circle is used as connector
Diamond is used as decision
Symbols are connected by arrows to
represent the order of the operations
20
Flowcharts Symbols:
Calculations
Calculations (e.g. arithmetic
expressions) are shown in
rectangles
Examples:
Total = Cost + Tax
Total = Cost + Tax
Num = Num + 1 (add one to
the current value of Num
Num = Num + 1
and make that the new
value of Num)
21
Flowcharts Symbols:
Input/Output
Data input and output are shown
in parallelograms
Input means a read operation of
data from a peripheral device to READ Num
memory (e.g. a user typing in data
at a keyboard)
Output means a write operation of
WRITE Num
data to a peripheral device from
memory (e.g. data displayed to the
monitor)
22
Flowcharts Symbols:
Decisions
Decisions are shown within diamonds
and specify a condition to be tested
False
Based on the condition being TRUE or Gross > 50000
FALSE, the next operation will be
determined Rate = 0.28
True
A decision is composed of :
Rate = 0.31
A condition
An operation to be done if
condition is TRUE
Possibly an operation to be done if
condition is FALSE
23
Flowcharts Symbols:
Start and End
Every algorithm starts somewhere
and terminates somewhere start
Every flowchart must have one
input num
start symbol and one end symbol
square = num x num
Start and end symbols are ovals
A start symbol denotes the start print square
of the algorithm
stop
An end symbol indicates the
algorithm has terminated
24
Sequential Algorithm start
Flowchart prompt Age1
input Age1
Previous Pseudocode Algorithm:
READ Age of Child1 prompt Age2
PROMPT for Age of Child1
input Age2
READ Age of Child2
PROMPT for Age of Child2
Allow1 = Age1 x Rate
CALCULATE Allowance for
Child1 = Age of Child1 x Rate Allow2 = Age2 x Rate
CALCULATE Allowance for
Child2 = Age of Child2 x Rate Print Allow1
DISPLAY Allowance for Child1
DISPLAY Allowance for Child2 Print Allow2
stop 25
Selection Algorithm
Flowchart start
prompt Age
Previous Pseudocode
Algorithm: input Age
PROMPT for Age
TRUE FALSE
READ Age Age < 10
IF Age less than 10
Allow = Age x Allow = Age x
THEN CALCULATE YoungRate OlderRate
Allowance = Age x
YoungRate
ELSE CALCULATE Print Allow
Allowance = Age x
OlderRate stop
DISPLAY Allowance 26
start
Looping Algorithm KidsPaid = 0
Flowchart Total = 0
Previous Pseudocode
Algorithm: KidsPaid < 3
Set KidsPaid to 0 TRUE FALSE
Set Total to 0 Prompt Age
WHILE KidsPaid < 3 DO
PROMPT for Age Read Age
Display Total
READ Age
Calc Allowance
CALCULATE stop
Allowance = Age x Rate
Add Allowance
ADD Allowance to Total to Total
INCREMENT KidsPaid
Increment KidsPaid
DISPLAY Total 27
High-Level Design Tool:
Structure Charts
So a flowchart:
Details exactly HOW your program will do
each task
In contrast, our next design tool, the
structure chart:
Shows only WHAT tasks your program
will do (not HOW it will complete them)
28
High-Level Design Tool:
Structure Charts
Structure charts are hierarchical diagrams
They diagram the overall program structure
They show the relationship between all the
tasks in the program
They indicate which data is shared by the
tasks
29
Creating a
Structure Chart
A large program design is first broken into tasks
Tasks are repeatedly divided into even smaller subtasks
Rectangles are used to represent tasks/subtasks
within the program
Lines are used to hierarchically connect the
tasks/sutasks
Subtasks are diagrammed below the task that they
are part of Task
SubTask1 SubTask2
30
Creating
Structure Charts
The passing of data between tasks is shown by arrows
going up from or down to the task’s rectangle
Task
Data1 Data1
SubTask1 SubTask2
An upward arrow indicates that the data value has been set
inside the task and is being passed out for use by other tasks
A downward arrow indicates a data value previously set in
some other task is now being passed into this task
Data may also be passed both into a task (downward arrow),
modified, and passed back out again (upward arrow). 31
Sample Structure Chart
Given a generic program that reads some data from the
user, runs some calculations using that data, and
displays results to the user, the structure chart could
look like this:
main
Result
Data Data
Result
Get_Input Process_Data Display_Results
32
Structure Chart for
Sequential Program
Using our previous sequential program design
example (calculate your two childrens’ allowances,
based upon 75 cents per year old), the structure
chart might be:
main
Allow1,
Age1, Age1, Allow1, Allow2
Age2 Age2 Allow2
Get_Ages Calculate_Allowances Display_Allowances
33
Structure Chart for
Selection Program
Using our previous selection program design
example (calculate one child’s allowance, based upon
75 cents per year old if s/he is under 10, and $1 per
year if 10 or over), the structure chart might be:
main
Age Age Allowance Allowance
Get_Age Calculate_Allowance Display_Allowance
34
Structure Chart for
Selection Program
Note that this SAME structure chart could also have
been used for the sequential program (calculate your
two childrens’ allowances, based upon 75 cents per
year old). Each of the modules in the chart would be
called by main TWICE.
main
Age Age Allowance Allowance
Get_Age Calculate_Allowance Display_Allowance
35
Structure Chart for
Looping Program
Using our previous looping program design example
(calculate the total allowance paid to each of three
children at $1 per year old), the structure chart might
be:
main
Total Total
Calc_Allowance_Total Display_Total
The Get_Age and
Age Age Allowance
Calc_Allowance modules
would be called every
Get_Age Calc_Allowance time the program loops.
36
Summary of
Structure Chart Creation
Put name of program in rectangle root of an upside-down tree.
Determine the main subtasks that must be performed by the
program to solve the problem.
Put main subtasks in rectangles below the root, and draw a
connecting line from the root to each subtask.
Examine each subtask individually, and break them down into
even smaller tasks.
Put subtasks in rectangles below the task that they are part
of, and draw a connecting line from task to subtask.
Repeat until the bottom tasks of the tree are very simple tasks
to complete
37
