CSE1301
Computer Programming
Lecture 3:
Components of an Algorithm
1
Recall
•
•
•
•
•
What is the problem solving process?
What is an algorithm?
What are some examples?
What are values and variables?
What are instructions or primitives?
2
Topics
• More components of an algorithm
• The software development process
• Top-down design
3
Components of an Algorithm
Values and Variables
• Instruction (a.k.a. primitive)
–
–
–
–
Sequence (of instructions)
Procedure (involving instructions)
Selection (between instructions)
Repetition (of instructions)
• Documentation (beside instructions)
4
Family Tree of
Programming
Languages
The components of Algorithms
That we use correspond
To “structured programming”
(Algol, Pascal, C, Modula, Ada…)
5
Variables
• Are containers for values – places to store
values
• Example:
Variable
Values
This jar
can contain
10 cookies
50 grams of sugar
3 slices of cake
etc.
6
Restrictions on Variables
• Variables may be restricted to contain a
specific type of value
7
Components of an Algorithm
Values and Variables
Instruction (a.k.a. primitives)
• Sequence (of instructions)
• Procedure (involving instructions)
• Selection (between instructions)
• Repetition (of instructions)
• Documentation (beside instructions)
8
Instructions (Primitives)
• Some action that is
–
–
–
–
simple
unambiguous
that the system knows about...
...and should be able to actually do
9
Instructions – Examples
•
•
•
•
•
•
•
Take off your shoes
Directions to perform
Count to 10
specific actions on values
Cut along dotted line and variables.
Knit 1
Purl 2
Pull rip-cord firmly
Sift 10 grams of arsenic
10
Instructions -- Application
• Some instructions can only be applied to a
specific type of values or variables
• Examples:
11
Instructions (Primitives) -Recommendations
• When writing an algorithm, make each
instruction simple and unambiguous
• Example:
Cut chicken into pieces and Cut chicken into pieces.
brown the pieces on all
Heat olive oil in a casserole
sides in a casserole dish
dish.
in hot olive oil.
Brown the chicken pieces in
the casserole dish.
12
Instruction (Primitives)
• When
an algorithm,
make the
A writing
“sequence”
of
instructions
and unambiguous.
simplesimple
instructions
• Example:
Cut chicken into pieces and
brown the pieces on all
sides in a casserole dish in
hot olive oil.
Cut chicken into pieces.
Heat olive oil in a casserole
dish.
Brown the chicken pieces in
13
the casserole dish.
Sequence
•
•
•
•
A series of instructions
...to be carried out one after the other...
...without hesitation or question
Example:
– How to cook a Gourmet MealTM
14
Sequence -- Example
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Open freezer door
Take out Gourmet Meal™
Close freezer door
Open microwave door
Put Gourmet Meal™ on carousel
Shut microwave door
Set microwave on high for 5 minutes
Start microwave
Wait 5 minutes
Open microwave door
Remove Gourmet Meal™
Close microwave door
15
Components of an Algorithm
Values and Variables
Instruction (a.k.a. primitives)
Sequence (of instructions)
• Procedure (involving instructions)
• Selection (between instructions)
• Repetition (of instructions)
• Documentation (beside instructions)
16
Procedure
• A named sequence of instructions
• So that you can
– Refer to it collectively (by name)
– ...instead of individually (by each instruction in
the sequence)
• Example:
– Drive_To_Uni
17
Procedure -- Example
procedure Drive_To_Uni
{
1. find car keys
2. disable car alarm
3. open car door
4. get in car
5. shut car door
6. put keys in ignition
7. start car
8. back car out of
driveway
9. drive to end of street
10. turn right
11. drive to end of street
12. turn left
...etc...etc...etc
...etc...etc...etc...
52. find parking space
53. pull into parking
space
54. turn off engine
55. remove keys from
ignition
56. open car door
57. get out
58. shut car door
59. lock car door
60. enable alarm
}
18
Procedure – Example (cont)
procedure Do_Wednesday
{
Wake_up
Have_Shower
Eat_Breakfast
Drive_To_Uni
Sit_1301_Lecture
...etc...etc...etc...
Drive_From_Uni
...etc...etc...etc...
}
procedure Do_Week
{
Do_Monday
Do_Tuesday
Do_Wednesday
Do_Thursday
...etc...etc...etc...
}
19
Procedure – Example (cont)
procedure Do_Wednesday
{
Wake_up
Have_Shower
Eat_Breakfast
Drive_To_Uni
Sit_1301_Lecture
...etc...etc...etc...
Drive_From_Uni
...etc...etc...etc...
}
In this subject, we also
use the following words
to refer to a
“Procedure” :
• Sub-routine
• Module
• Function
20
Procedure – Example (cont)
procedure Do_Wednesday
{
Wake_up
Have_Shower
Eat_Breakfast
Drive_To_Uni
Sit_1301_Lecture
...etc...etc...etc...
Drive_From_Uni
...etc...etc...etc...
}
We use brackets to
mark the beginning
and end of a
sequence.
21
Procedure – Example (cont)
procedure Do_Wednesday
{
Wake_up
Have_Shower
Eat_Breakfast
Drive_To_Uni
Sit_1301_Lecture
...etc...etc...etc...
Drive_From_Uni
...etc...etc...etc...
}
An instruction invoking
a procedure is known
as a “procedure call”
22
Procedure
• A procedure may have a set of parameters
procedure customerService ( myName ,timeOfDay )
{
say “Good timeOfDay”
say “My name is myName”
say “How can I help you?”
}
customerService ( “Ann”, “Morning” )
customerService (“Ann”, “Afternoon” )
customerService ( “Jeff”, “Afternoon” )
23
Components of an Algorithm
Values and Variables
Instruction (a.k.a. primitives)
Sequence (of instructions)
Procedure (involving instructions)
• Selection (between instructions)
• Repetition (of instructions)
• Documentation (beside instructions)
24
Selection
• An instruction that decides which of two
possible sequences is executed
• The decision is based on a single true/false
condition
• Examples:
– Car repair
– Reciprocals
25
Selection Example -- Car Repair
if (motor turns)
then
{
CheckFuel
CheckSparkPlugs
CheckCarburettor
}
else
{
CheckDistributor
CheckIgnitionCoil
}
26
Selection Example –
Car Repair (cont)
if (motor turns)
then
{
CheckFuel
CheckSparkPlugs
CheckCarburettor
}
else
{
CheckDistributor
CheckIgnitionCoil
}
Should be a
true or false
condition.
27
Selection Example -Car Repair (cont)
if (motor turns)
then
{
CheckFuel
CheckSparkPlugs
CheckCarburettor
}
else
{
CheckDistributor
CheckIgnitionCoil
}
Sequence if
the condition
is true.
28
Selection Example -Car Repair (cont)
if (motor turns)
then
{
CheckFuel
CheckSparkPlugs
CheckCarburettor
}
else
{
CheckDistributor
CheckIgnitionCoil
}
Sequence if the
condition is
false.
29
Selection Example -- Reciprocals
Q. Give an
Examples:
algorithm for
computing the
reciprocal of a
number.
Reciprocal of 2:
1/2
Reciprocal of -3/4:
1/(-3/4) = -4/3
Reciprocal of 0:
“undefined”
30
Selection Example – Reciprocals (cont)
Algorithm:
Q. Give an
algorithm for
computing the
reciprocal of a
number.
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
else
{
output "infinity"
}
31
Selection Example-- Reciprocals
Algorithm:
Num is a variable
whose value
depends on the
actual number the
user provides.
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
else
{
output "infinity"
}
32
Selection Example – Reciprocals
(cont)
Algorithm:
Condition depends
on the value of
Num
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
else
{
output "infinity"
}
33
Selection Example – Reciprocals
(cont)
Algorithm:
For a given value
of Num, only one
of these two
sequences can be
executed
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
else
{
output "infinity"
}
34
Selection Example – Reciprocals
(cont)
Algorithm:
Executed if Num
is not equal to 0
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
else
{
output "infinity"
}
35
Selection Example – Reciprocals
(cont)
Algorithm:
Executed if Num
is equal to 0
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
else
{
output "infinity"
}
36
Selection -- Exercise
Will the following algorithms produce the same output?
Algorithm 1:
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
else
{
output "infinity"
}
Algorithm 2:
input Num
if (Num is not equal 0)
then
{
output 1/Num
}
output "infinity"
37
Selection – Several Conditions
• What if several conditions need to be satisfied?
if ( today is Wednesday and the time is 10.00am )
then
{
Go to CSE1301 Lecture
}
else
{
Go to Library
}
Solution 1
38
Selection – Several Conditions (cont)
if ( today is Wednesday )
then
{
if ( the time is 10.00am )
then
{
Go to CSE1301 Lecture
}
}
else
...etc...etc...etc...
Often called a
“nested selection”
Solution 2
39
Selection – At Least One of
Several Conditions
• What if at least one of several conditions
needs to be satisfied?
if ( I feel hungry or the time is 1.00pm or my
mate has his eye on my lunch )
then
{
Eat my lunch now
}
40
Components of an Algorithm
Values and Variables
Instruction (a.k.a. primitives)
Sequence (of instructions)
Procedure (involving instructions)
Selection (between instructions)
• Repetition (of instructions)
• Documentation (beside instructions)
41
Repetition
• Repeat an instruction...
– ...while (or maybe until) some true or
false condition occurs
– Test the condition each time before
repeating the instruction
• Also known as iteration or loop
• Example:
– Algorithm for getting a date
42
Repetition -- Example
procedure AskOnDate ( name, time, location )
{
Phone(name)
Say("Hey", name, "it's your lucky day!")
Say("Wanna come to", location, "at", time, "?")
ListenToReply ( )
start begging count at zero
while (reply is "No" and begging count < 100)
{
Say("Oh please!")
add 1 to begging count
ListenToReply ( )
}
}
43
Repetition – Example (cont)
procedure AskOnDate ( name, time, location )
{
Phone(name)
Say("Hey", name, "it's your lucky day!")
Say("Wanna come to", location, "at", time, "?")
ListenToReply ( )
start begging count at zero
while ( reply is "No" and begging count < 100 )
{
Say("Oh please!")
Condition is tested
add 1 to begging count
ListenToReply ( )
before sequence
}
}
44
Repetition – Example (cont)
procedure AskOnDate ( name, time, location )
{
Phone(name)
Say("Hey", name, "it's your lucky day!")
Say("Wanna come to", location, "at", time, "?")
ListenToReply ( )
start begging count at zero
while (reply is "No" and begging count < 100)
{
Say("Oh please!")
Sequence may not
add 1 to begging count
get executed at all
ListenToReply ( )
}
}
45
Repetition – Example (cont)
Ensure initial
procedure AskOnDate ( name, time, location )
values of variables
{
Phone(name)
used in the
Say("Hey", name, "it's your lucky day!")
conditions are set
Say("Wanna come to", location, "at", time, "?")
correctly
ListenToReply ( )
start begging count at zero
while (reply is "No" and begging count < 100)
{
Say("Oh please!")
add 1 to begging count
ListenToReply ( )
}
}
46
Repetition – Example (cont)
procedure AskOnDate ( name, time, location )
{
Phone(name)
Say("Hey", name, "it's your lucky day!")
Say("Wanna come to", location, "at", time, "?")
ListenToReply ( )
start begging count at zero
while (reply is "No" and begging count < 100)
{
Say("Oh please!")
Ensure the variables
add 1 to begging count
used in the conditions
ListenToReply ( )
}
are updated in each
}
iteration
47
Repetition – Example (cont)
• What if we don’t increment the begging count?
procedure AskOnDate ( name, time, location )
{
Phone(name)
Say("Hey", name, "it's your lucky day!")
Say("Wanna come to", location, "at", time, "?")
ListenToReply ( )
start begging count at zero
while (reply is "No" and begging count < 100)
{
Say("Oh please!")
}
Infinite loop
}
48
Repetition – Variation
decide on Time and Location
initialise booking to “unsuccessful”
while ( not successfully booked )
{
get next Name in little black book
AskOnDate(Name, Time, Location)
DetermineBookingSuccess
}
SighWithRelief
49
Components of an Algorithm
Values and Variables
Instruction (a.k.a. primitives)
Sequence (of instructions)
Procedure (involving instructions)
Selection (between instructions)
Repetition (of instructions)
• Documentation (beside instructions)
50
Documentation
• Records what the algorithm does
• Describes how it does it
• Explains the purpose of each component of
the algorithm
• Notes restrictions or expectations
• Example:
– Getting a date (again)
51
Documentation -- Example
Think of something romantic to do
decide on time and location
Work through address book to look for a person
initialise booking to “unsuccessful”
until (successfully booked)
{
get next Name in little black book
AskOnDate(Name, Time, Location)
DetermineBookingSuccess
}
Assumes that I will find someone in the book before it runs out
SighWithRelief
52
Components of an Algorithm
Values and Variables
Instruction (a.k.a. primitives)
Sequence (of instructions)
Procedure (involving instructions)
Selection (between instructions)
Repetition (of instructions)
Documentation (beside instructions)
53
The Software Development Process
•
•
•
•
•
•
Define the problem clearly
Analyse the problem thoroughly
Design an algorithm carefully
Code the algorithm efficiently
Test the code thoroughly
Document the system lucidly
54
Top-down Algorithm Design
•
•
•
•
Write down what you have to do
Break that into 3-7 smaller steps
Break each step into 3-7 smaller steps
Keeping subdividing until each individual
step is easy enough to do – i.e., until it is a
single instruction
• Example:
– Learning
55
Top-down Design -- Example
Prepare
Learn
Study
Reinforce
Read
Make notes
Prepare questions
Attend lecture
Listen and think
Complete prac
Attend tute
Record answers to
questions
Revise notes
Read lecture notes
Read textbook
Read exercise
Design algorithm
Code solution
Test and document
Record insights
56
Reading
• Deitel & Deitel, C: How to program
– Chapter 3, Sections 3.8 to 3.13
57
Descargar

Algorithms 2 (Lecture 4 of CSE1301)