[Link]
sg/~cs1010/
UNIT 3
Algorithmic Problem Solving
© NUS CS1010 Unit2 - 2
Unit 2: Algorithmic Problem Solving
1. Plinko by Psudocode
2. Algorithm
3. Control Structures
4. Examples of Pseudocodes
5. Euclid’s Algorithm
IS PROGRAMING
SCARY?
An example of a “program” by pseudocode
© NUS CS1010 Unit2 - 4
What is programming?
© NUS CS1010 Unit2 - 5
Imagine
© NUS CS1010 Unit2 - 6
Running a Booth
• Dropping a ball from the
top and you will get
• 3: Big prize
• 2: Medium prize
• 1: Small prize
© NUS CS1010 Unit2 - 7
Let’s see what we have for prizes
• Giant Teddy Bears
• X 10
• Water guns
• X 50
• Candy
• X 200
© NUS CS1010 Unit2 - 8
Your Job is
• Run the booth until the end of the day or all prizes given
out
• 3: Giant Teddy Bear
• 2: Water Gun
• 1: Candy
• What is the potential problem?
• You may run out of Teddy Bears!
• Or Water guns or candies
• Any suggestion?
© NUS CS1010 Unit2 - 14
Before Real Coding
• A Program can be expressed by
• Pseudocode
• An artificial and informal language that helps programmers develop
algorithms.
• "text-based“
• Or A Flow Chart
© NUS CS1010 Unit2 - 15
Start
Plinko Flow Chart
Any No
Get Someone Yes
more Close
Play Plinko
prizes?
Yes Any Yes
3? more Give bear
bears?
No No
2? Omitted..
Any
more Note the different
Candy? shape of the
bubbles
© NUS CS1010 Unit2 - 16
Control Structures on Pictionary
© NUS CS1010 Unit2 - 17
© NUS CS1010 Unit2 - 18
Flow Chart Bubble Types
© NUS CS1010 Unit2 - 19
Algorithm
Ways of representing an algorithm:
Flowchart Pseudocode
[Link]
© NUS CS1010 Unit2 - 20
Algorithms
• Named for al-Khwārizmī (780-850)
• Persian mathematician
• Many ancient algorithms
• Multiplication: Rhind Papyrus
• Babylon and Egypt: ~1800BC
• Euclidean Algorithm: Elements
• Greece: ~300BC
• Sieve of Eratosthenes
• Greece: ~200BC
© NUS CS1010 Unit2 - 21
© NUS CS1010 Unit2 - 22
Algorithm (1/3)
An algorithm is a well-defined computational
procedure consisting of a set of instructions,
that takes some value or set of values as
input, and produces some value or set of
values as output.
Input Algorithm Output
‘Algorithm’ stems from ‘Algoritmi’, the Latin form of al-
Khwārizmī, a Persian mathematician, astronomer and geographer.
Source: [Link]
© NUS CS1010 Unit2 - 23
Control Structures
An algorithm is a set of instructions, which are
followed sequentially by default.
However, sometimes we need to change the
default sequential flow.
We study 3 control structures.
CONTROL
STRUCTURES
© NUS CS1010 Unit2 - 25
Control Structures
Sequence • Default
True False
• Also called ?
Selection branching
• Also called False ?
Repetition loop
True
© NUS CS1010 Unit2 - 26
Control Structure: Sequence
© NUS CS1010 Unit2 - 27
Control Structure: Sequence
A Block
#include <stdio.h>
int main(void) {
int a,b,c;
a = 2001; Sequentially run
b = 4002; this line by line
c = a + b;
printf(“ The value of %d + %d = %d\n”,a,b,c);
return 0;
}
Don’t worry about the C syntax; we will
Tips: How to read a C discuss it next week. For now, just to show
program? you how the algorithm is translated into the
You look for the code. The logic remains the same, but you
“main()” and start need to write the code according to the
reading it’s “block” rules of the programming language.
© NUS CS1010 Unit3 - 28
Control Structures: Sequence
Task: Compute the average of three integers
How the program might look like Unit3_prog1.c
// This program computes the average of 3 integers
#include <stdio.h>
int main(void) {
int num1, num2, num3;
float ave;
printf("Enter 3 integers: ");
scanf("%d %d %d", &num1, &num2, &num3);
ave = (num1 + num2 + num3) / 3.0;
printf("Average = %.2f\n", ave);
return 0;
}
© NUS CS1010 Unit2 - 29
Control Structures
Sequence • Default
True False
• Also called ?
Selection branching
• Also called False ?
Repetition loop
True
© NUS CS1010 Unit2 - 30
True False
?
Control Structure: Selection
• If the player strikes a “3”
• Give him a bear
• Else
• Let him choose a water gun or a candy
© NUS CS1010 Unit2 - 31
True False
?
Control Structure: Selection
If (a condition is true)
Do A
Else Can be MORE THAN one
Do B single instruction
• For example:
If (I have $1000000000000000)
Buy a car
Eat a lot of buffets
Go travel
Quit NUS!
Else
Be good and study
© NUS CS1010 Unit2 - 32
True False
?
Control Structure: Selection
If (a condition is true)
Do A
Else
Do B Can be MORE THAN one
single instruction
• For example:
If (I have $1000000000000000)
If (I am heartless)
Buy a car
Eat a lot of buffets
Go travel Nested “if”
Quit NUS!
Else
donate all the money to charity
Else
Be good and study
© NUS CS1010 Unit2 - 33
True False
?
Control Structure: Selection
If (a condition is true)
Do A
Else Can be WITHOUT “else”
Do B
• For example:
If (I have $1000000000000000)
Buy a car
Eat a lot of buffets
Go travel
Quit NUS!
Else
Be good and study
© NUS CS1010 Unit3 - 34
True False
Control Structures: Selection (1/3) ?
Task: Arrange two integers in ascending order (sort)
Algorithm A:
enter values for num1, num2 Variables
// Assign smaller number into final1, used:
// and larger number into final2 num1 num2
if (num1 < num2)
then final1 num1 final1 final2
final2 num2
else final1 num2
final2 num1
// Transfer values in final1, final2 back to num1, num2
num1 final1
num2 final2
// Display sorted integers
print num1, num2
© NUS CS1010 Unit3 - 35
True False
Control Structures: Selection (2/3) ?
Task: Arrange two integers in ascending order (sort)
Algorithm B:
enter values for num1, num2 Variables
used:
// Swap the values in the variables if necessary
if (num2 < num1) num1 num2
then temp num1
temp
num1 num2
num2 temp
// Display sorted integers
print num1, num2
Compare Algorithm A with Algorithm B.
© NUS CS1010 Unit3 - 36
True False
Control Structures: Selection (3/3) ?
How the program might look like for Algorithm B
// This program arranges 2 integers in ascending order
Unit3_prog2.c
#include <stdio.h>
int main(void) {
int num1, num2, temp;
printf("Enter 2 integers: ");
scanf("%d %d", &num1, &num2);
if (num2 < num1) {
temp = num1;
num1 = num2;
num2 = temp;
}
printf("Sorted: num1 = %d, num2 = %d\n", num1, num2);
return 0;
}
© NUS CS1010 Unit2 - 37
Control Structures
Sequence • Default
True False
• Also called ?
Selection branching
• Also called False ?
Repetition loop
True
© NUS CS1010 Unit2 - 38
False ?
Control Structure: Repetition True
• While there are prizes left
• Play Plinko and give prizes
© NUS CS1010 Unit2 - 39
False ?
Control Structure: Repetition True
• While (a condition)
• Do something
• For example
While (I am hungry)
Eat a bun
• Again, can be more than one single instruction
While(I have money in bank)
Take some money out from bank
Eat an expensive meal
While(I have money in my wallet)
Go Shopping
© NUS CS1010 Unit3 - 40
False
?
Control Structures: Repetition (1/3) True
Task: Find sum of positive integers up to n (assume n>0)
Algorithm:
enter value for n Variables
// Initialise a counter count to 1, and ans to 0 used:
count 1 n
ans 0
while (count ≤ n) do count
ans ans + count // add count to ans
count count + 1 // increase count by 1 ans
// Display answer
print ans
Initialisation is
very important!
© NUS CS1010 Unit3 - 41
False
?
Control Structures: Repetition (2/3) True
Important to trace pseudocode to check its correctness
Algorithm: Assume user enters 3 for n.
enter value for n
(count <= n)? count ans
count 1
ans 0 1 0
while (count ≤ n) do true 2 1
ans ans + count true 3 3
count count + 1 true 4 6
// Display answer false
print ans
Output: 6
© NUS CS1010 Unit3 - 42
False
?
Control Structures: Repetition (3/3) True
How the program might look like
Unit3_prog3.c
// Computes sum of positive integers up to n
#include <stdio.h>
int main(void) {
int n; // upper limit
int count = 1, ans = 0; // initialisation
printf("Enter n: ");
scanf("%d", &n);
while (count <= n) {
ans += count;
count++;
}
printf("Sum = %d\n", ans);
return 0;
}
© NUS CS1010 Unit2 - 43
Euclid’s Algorithm (1/3)
To compute the greatest common divisor
(GCD) of two integers
First documented algorithm by Greek
mathematician Euclid in 300 B.C.
Also known as Euclidean Algorithm
1. Let A and B be integers with A > B ≥ 0.
2. If B = 0, then the GCD is A and algorithm ends.
3. Otherwise, find q and r such that
A=q×B+r where 0 ≤ r < B
4. Replace A by B, and B by r. Go to step 2.
© NUS CS1010 Unit2 - 44
Euclid’s Algorithm (2/3)
q is not important;
r is the one that
matters.
r could be obtained
by A modulo B (i.e.
remainder of A / B)
1. Let A and B be integers with A > B ≥ 0. Assumption on A > B
2. If B = 0, then the GCD is A and algorithm ends. unnecessary
3. Otherwise, find q and r such that
We will rewrite the
A=q×B+r where 0 ≤ r < B
algorithm
4. Replace A by B, and B by r. Go to step 2.
© NUS CS1010 Unit2 - 45
Euclid’s Algorithm (3/3)
Euclid’s algorithm rewritten in modern form
// Assume A and B are non-negative
// integers, but not both zeroes. Let’s trace GCD(12, 42)
Algorithm GCD(A, B) { (B > 0)? r A B
while (B > 0) { 12 42
r A modulo B true 12 42 12
AB
true 6 12 6
Br
true 0 6 0
}
false
result is A
}
Result: 6
© NUS CS1010 Unit2 - 46
What is the difference between
Algorithm vs Program Research Idea vs Thesis
• Algorithm • Research Idea
• Ideas • Can be drawings, sketches,
• Machine independent concepts, in any languages
• Program • Thesis
• The final code on a machine • Well-written documents in
• Machine dependent any languages, English,
German, Chinese, etc…
© NUS CS1010 Unit2 - 47
Algorithm (1/3)
An algorithm is a well-defined computational
procedure consisting of a set of instructions,
that takes some value or set of values as
input, and produces some value or set of
values as output.
Input Algorithm Output
‘Algorithm’ stems from ‘Algoritmi’, the Latin form of al-
Khwārizmī, a Persian mathematician, astronomer and geographer.
Source: [Link]
© NUS CS1010 Unit1 - 48
And computer will follow exactly
• “I asked my husband
to peel half of the
potatoes and put
them on to boil…”
• And finally….
© NUS CS1010 Unit2 - 49
Algorithm: Example #1
© NUS CS1010 Unit2 - 50
Algorithm: Example #2 (1/2)
Find maximum and average of a list of numbers:
Terminator box
start
Flowchart
Process box
sum count 0
max 0
Decision box
Yes end of
input?
No
Enter num
increment count
ave sum/count sum sum + num
print max, ave Yes
num > max? max num
No
end
© NUS CS1010 Unit2 - 51
Algorithm: Example #2 (2/2)
Find maximum and average of a list of numbers:
Pseudocode The need to initialise variables.
sum count 0 // sum = sum of numbers
// count = how many numbers are entered?
max 0 // max to hold the largest value eventually
for each num entered,
count count + 1
sum sum + num The need to indent.
if num > max
then max num
ave sum / count
print max, ave Are there any errors
in this algorithm?
© NUS CS1010 Unit2 - 52
Algorithm: Pseudocode
We will write algorithms in pseudocode instead
of flowchart as the former is more succinct
However, there are no standard rules on how
pseudocodes should look like
General guidelines:
Every step must be unambiguous, so that anybody is
able to hand trace the pseudocode and follow the
logic flow
Use a combination of English (keep it succinct) and
commonly understood notations (such as for
assignment in our previous example)
© NUS CS1010 Unit2 - 53
Summary
In this unit, you have learned about
The process of algorithmic problem solving
The properties of an algorithm
The three control structures
How to write algorithms in pseudocode
Tracing algorithms to verify their correctness
