2019-03-19
1
Lecture 8-1 Introduction to Algorithms — Representations
This lecture is about
the concept of algorithms and its basic characteristics the basic symbols used in flow charts
Algorithm representation in flow charts
Algorithm representation in pseudo-code 3 basic control structures
2019-03-19 2
Topics
Why algorithms?
”If you cannot describe what you are doing as a process, you don’t know what you’re doing.”
http://www.brainyquote.com/quotes/quotes/w/wedwards d133510.html
W. Edwards Deming
2019-03-19 3
Why algorithms?
• Programming is not only about coding in some languages.
• Algorithm is an important part of programming activity
– It is carried out before coding in a computer language
– It is even more important for the beginners to develop solutions
2019-03-19 4
Programming
• Programming can be viewed as the process of designing and implementing algorithms that a computer can carry out
– a programmer’s job is to:
2019-03-19
5
1) 2)
create an algorithm for accomplishing a given objective, then
translate the individual steps of the algorithm into computer language code that the computer can understand
Definition of Algorithm
• An algorithm is an ordered set of unambiguous, executable steps for carrying out some task.
• Characteristics
– Ordered step-by-step, actions one by one in order – Unambiguous action is clear; entydig;
– Executableeach action is simple and do-able
– The number of steps is countable and finite
– Finally a solution is obtained
2019-03-19 6
Algorithm
• An algorithm is a list that looks like
1) 2) 3) 4) 5) 6) 7)
STEP 1: STEP 2: STEP 3:
. . . . . .
Do something. Do something. Do something.
Stop. You are finished.
STEP N:
• Each step is simple enough to be do-able
• The steps are ordered and have to be followed
2019-03-19 7
Algorithms in the Real World
• the use of algorithms is not limited to the domain of computing
– e.g., recipes for baking cookies
– e.g., directions to your house
• there are many unfamiliar tasks in life that we could not
complete without the aid of instructions
– in order for an algorithm to be effective, it must be stated in a manner that its intended executor can understand
• a recipe written for a master chef will look different than a recipe written for a college student
– as you have already experienced, computers are more demanding with regard to algorithm specifics than any human could be
• Kanel- och kardemummabullar
– Follow 14 steps, you will enjoy the best bullar! 2019-03-19
8
Algorithm Representation
• The representation of an algorithm (for programming) requires some form of languages
– Human
• Natural languages (English, Swedish, Chinese,… Not good, since people do not speak the same language
– Computer science
• Computer languages (Assembler, C, C++, Java, …)
– We have too many languages
• Pseudo-codeswhat is this? • Flow charts??
• In computer science, pseudo-code and flowchart are widely used for algorithm representation
2019-03-19 9
Definition: Pseudo-code
• An artificial and informal language to represent the algorithm by the programmer
• It is close to computer languages and easy for programmers to understand
• It is also similar to everyday language (e.g. English)
• It is read by human (programmers)
2019-03-19 10
•
An example pseudo-code
Calculate the class average
Set total to zero
Set grade counter to one
While grade counter is less than or equal to ten
Input the next grade
Add the grade into the total
endwhile
Set the class average to the total divided by ten Print the class average.
Can you read and understand the above pseudo-code? – What does the algorithm do?
•
2019-03-19
11
Video
Programming Basics #36 Writing Pseudocode (4 min) https://www.youtube.com/watch?v=4G0EYfrrD T8
• Watch video clip
2019-03-19 12
Flowchart
http://en.wikipedia.org/wiki/Flowchart
• A flowchart is a type of diagram
– Used to represent an algorithm or process,
• It shows the steps as boxes of various kinds, and their order by connecting them with arrows.
• This diagrammatic representation illustrates a solution to a given problem. Process operations are represented in these boxes, and arrows;.
• Flowcharts are used in analyzing, designing, documenting or managing a process or program in various fields.
2019-03-19 13
Flowchart
– Shows logic of an algorithm (follow the arrow)
– Emphasizes individual steps and their interconnections
• Control flow from one action to the next
• Aflowchart
2019-03-19
14
Flowchart Symbols
http://www.wiley.com/college/busin/icmis/oakman/outline/chap05/slides/symbols.htm
2019-03-19 15
Example flowchart
• http://en.wikipedia.org/wiki/File:LampFlowch art.svg
2019-03-19 16
Video
Flow Chart Example (12 min)
https://www.youtube.com/watch?v=h736bEHkT _Y&index=44&list=PLHcpeXHQSQXVJg2N2u ZAe-d1009Lp_Eu6
• Watch video clip
2019-03-19 17
2019-03-19
18
There are some standard building blocks for representing an algorithm.
Building block 1: Assignment Pseudo- code:
var = expression
Meaning: “assign var the value of expression” Flowchart symbol:
var= expression
2019-03-19 19
Example of Assignment
• Write assignment statements that perform the following operations with the variables a, b, c.
– Variables are containers used to keep values in computation
• Add 2 with a and store the result in b
b = a+2
• Multiplies b with 4 and stores the result in a c
a = 4*b
• Divides a by 3.14 and stores the result in b
b = a/3.14
• Subtracts 8 from b and stores the result in a
a= b–8
2019-03-19
20
• •
Building block 2
Conditional selections
Sometime, which action is taken is dependent on a condition.
•
2019-03-19
21
Pseudo-code
IF condition THEN action1
ELSE
action2 ENDIF
Example:
IF temp is less than 15 degree THEN print ‘Take a jacket.’
ELSE
print “Do not take a jacket.”
ENDIF
flowchart:
Building block 2:
Conditional selections
• ELSE part can be empty IF condition THEN
action ENDIF
• Example:
IF temp is less then 15 degree THEN
print “Take a jacket” ENDIF
2019-03-19 22
Building block 3
Conditional Repetition
• Sometimes, an action is carried out many times – Loop, iteration
– There are 2 basic forms while-do and do-while loops
1. WHILE-DO loop — Condition is checked at the beginning
WHILE condition is true DO action
ENDWHILE
2. Do-while loop — Condition is checked at the end DO
action
WHILE condition is true
2019-03-19
23
Building block 3
Conditional Repetition
1. While-do – loop
Condition is checked at the beginning:
WHILE condition DO action
ENDWHILE
• Evaluatethecondition:
– If it is true, do the action.
– Continue the loop until the condition is false
2019-03-19 24
2. Do – while loop
Building block 3
Conditional Repetition
Condition is checked at the end
DO
action
WHILE condition
• Do the action.
• Evaluate the condition
• If it is true, continue the loop.
2019-03-19 25
Building block 3
Conditional Repetition
2. Difference between while-do and do-while loops
Condition is checked at the beginning or the end Action is done at least once for do-while loop
2019-03-19 26
Building block 3
Conditional Repetition
• FOR-loop: for those who have learnt for-loop in some computer languages, here is the pseudo-code and flow chart. For
beginners, we can ignore it, since it can always be realized by a WHILE-DO loop.
FOR ( exp1; exp2; exp3) action
END FOR
FOR-loop can be re-written as:
exp1
WHILE exp2 is true DO
action
exp3
END WHILE
2019-03-19 27
Building block 4
Input and output
• How to get data into computer, how to output data?
• input – get data into the computer IN var
Read a value to variable var
Keyword could be IN, INPUT, READ
• Output – output the data OUT var
Output the value of var
Keyword could be OUT, OUTPUT, WRITE, Print
2019-03-19 28
Control Structures– Sequence
• It is the default structure
• Sequential actions executed in
the order
2019-03-19 29
Control Structures– selection
• Take an action based on a condition
2019-03-19 30
Control Structures– iteration
• Loop: some action is repeated many times
2019-03-19 31
Using AlgoBuild to draw flowchart
• First be sure to be able to draw by hand
• Then use AlgoBuild to get a nice flowchart
– https://algobuild.com/en/index.html
2019-03-19 32