PowerPoint Presentation
1
Design Tools
· Flow Chart
– for a simple problem or
– a module of a complex problem
2
Design Tools
· Flow Chart
– for a simple problem or
– a module of a complex problem
· Pseudocode
– is part English, part program logic: its purpose is to describe, in precise algorithmic
detail, what the program being designed is to do. Contains basic algorithmic constructs – sequence, selection, iteration.
3
Design Tools
· Flow Chart
– for a simple problem or
– a module of a complex problem
· Pseudocode
– is part English, part program logic: its purpose is to describe, in precise algorithmic
detail, what the program being designed is to do. Contains basic algorithmic constructs – sequence, selection, iteration.
· Structure Chart
– for a complex problem
4
Pseudocode vs Flow Chart
The flow chart is basically the same as the pseudocode:
5
Pseudocode vs Flow Chart
The flow chart is basically the same as the pseudocode:
· FLOW CHART is recommended for the new programmers, because it is a visual tool that is easier to create than pseudocode.
6
START
checkEven (ary, n)
oneEven false
i 0
i < n
AND oneEven
is false
ary[i] is even
oneEven true
i i + 1
RETURN
oneEven
True
True
Flow Chart
7
Pseudocode vs Flow Chart
The flow chart is basically the same as the pseudocode:
· FLOW CHART is recommended for the new programmers, because it is a visual tool that is easier to create than pseudocode.
· PSEUDOCODE is more common among professional programmers.
Data Structures: A Pseudocode Approach with C, Second Edition
8
Data Structures: A Pseudocode Approach with C, Second Edition
9
10
Pre/Post Header Documentation
Problem:
1. Write an algorithm that checks if there is at least one even number in a list of n integers.
11
5
7
3
9
10
13
8
1
0 1 2 3 4 5 6 7
Pre/Post Header Documentation
Problem:
1. Write an algorithm that checks if there is at least one even number in a list of n integers.
12
START
checkEven (ary, n)
oneEven false
i 0
i < n
AND oneEven
is false
ary[i] is even
oneEven true
i i + 1
RETURN
oneEven
True
True
Flow Chart
13
Algorithm checkEven ( ary, n )
This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
oneEven = false
i = 0
loop( i < n AND oneEven is false )
if( ary[i] is even )
oneEven = true
end if
i = i + 1
end loop
return oneEven
end checkEven
Pseudocode
14
Algorithm Header
Purpose, Pre and Post Conditions, and Return
Statement Numbers
Statment Constructs
Variables
Algorithm Analysis
Structure Diagrams
15
Algorithm checkEven ( ary, n )
This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
oneEven = false
i = 0
loop( i < n AND oneEven is false )
if( ary[i] is even )
oneEven = true
end if
i = i + 1
end loop
return oneEven
end checkEven
Pseudocode
16
Algorithm Header
Purpose, Pre and Post Conditions, and Return
Statement Numbers
Statment Constructs
Variables
Algorithm Analysis
Structure Diagrams
17
Algorithm checkEven ( ary, n )
This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
oneEven = false
i = 0
loop( i < n AND oneEven is false )
if( ary[i] is even )
oneEven = true
end if
i = i + 1
end loop
return oneEven
end checkEven
Pseudocode
18
Algorithm Header
Purpose, Pre and Post Conditions, and Return
Statement Numbers
Statment Constructs
Variables
Algorithm Analysis
Structure Diagrams
19
Algorithm checkEven ( ary, n )
This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
1 oneEven = false
2 i = 0
3 loop( i < n AND oneEven is false )
1 if( ary[i] is even )
1 oneEven = true
end if
2 i = i + 1
end loop
4 return oneEven
end checkEven
Pseudocode
20
Algorithm Header
Purpose, Pre and Post Conditions, and Return
Statement Numbers
Statment Constructs
Variables
Algorithm Analysis
Structure Diagrams
21
structured programming – one of the structured programming requirements is to write any algorithm using only three constructs
(without using break, continue, and goto):
Sequence Selection Loop
READ a, b
sum a + b
WRITE sum
a > 0
b a
b -a
a a – b
c c + 1
a > 0
c 0
This theorem (known as the Structured Program Theorem) was demonstrated by two mathematicians: Corrado Bohm and Giuseppe Jacopini, in 1966.
In 1968 Edsger Dijkstra wrote the article “Go To Statement Considered Harmful” that emphasized on the importance of structured programming.
22
READ a, b
sum a + b
WRITE sum
a > 0
b a
b -a
a a – b
c c + 1
a > 0
c 0
read( a, b )
sum = a + b
write( sum )
if( a > 0 )
b = a
else
b = -a
end if
c = 0
loop( a > 0 )
a = a – b
c = c + 1
end loop
structured programming – one of the structured programming requirements is to write any algorithm using only three constructs
(without using break, continue, and goto):
Sequence Selection Loop
23
Algorithm Header
Purpose, Pre and Post Conditions, and Return
Statement Numbers
Statment Constructs
Variables
Algorithm Analysis
Structure Diagrams
24
Algorithm checkEven ( ary, n )
This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
oneEven = false
i = 0
loop( i < n AND oneEven is false )
if( ary[i] is even )
oneEven = true
end if
i = i + 1
end loop
return oneEven
end checkEven
Pseudocode
25
Algorithm Header
Purpose, Pre and Post Conditions, and Return
Statement Numbers
Statment Constructs
Variables
Algorithm Analysis
Structure Diagrams
26
Algorithm checkEven ( ary, n )
This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
oneEven = false
i = 0
loop( i < n AND oneEven is false )
if( ary[i] is even )
oneEven = true
end if
i = i + 1
end loop
return oneEven
end checkEven
Pseudocode
Big O:
O(n)
27
Algorithm efficiency is generally defined as a function of the number of elements to be processed.
The simplification of efficiency is known as
big-O notation.
Algorithm efficiency is generally defined as a function of the number of elements to be processed.
The simplification of efficiency is known as
big-O notation.
28
Algorithm Header
Purpose, Pre and Post Conditions, and Return
Statement Numbers
Statment Constructs
Variables
Algorithm Analysis
Structure Diagrams
29
main
readList
checkEven
printResult
30
5
7
3
9
10
13
8
1
0 1 2 3 4 5 6 7
/* This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
*/
int checkEven ( int ary[], int n )
{
int i;
for( i = 0; i < n; i++ )
if( ary[i] % 2 == 0 )
return 1;
return 0;
}
Solution 1
31
5
7
3
9
10
13
8
1
0 1 2 3 4 5 6 7
/* This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
*/
int checkEven ( int ary[], int n )
{
int oneEven = 0;
int i;
for( i = 0; i < n; i++ )
if( !(ary[i] % 2) )
oneEven = 1;
return oneEven;
}
Solution 2
32
5
7
3
9
10
13
8
1
0 1 2 3 4 5 6 7
/* This algorithm checks if there is at least one even number in ary
Pre : ary – a non-empty array of integer numbers
n – the actual size of the array
Post:
Return: true or false
*/
int checkEven ( int ary[], int n )
{
int oneEven = 0;
int i;
for( i = 0; i < n && !oneEven; i++ )
if( !(ary[i] % 2) )
oneEven = 1;
return oneEven;
}
Solution 3
2
)
1
(
)
(
+
=
n
n
n
f
)
(
2
n
O
/docProps/thumbnail.jpeg