Problem Solving & Algorithms
|
Problem
■ an intricate unsettled
question
■ a source of perplexity,
distress, or vexation
■ Examples of Problems?
■ - Finding Value of Unknown
■ -Finding optimal route to town
etc.
4/8/24 | 2
Problem Solving
■ Process of finding solutions to
difficult or complex issues
■ Solutions to the problems
earlier stated
4/8/24 | 3
Sample Problem 1
■ You have 2 water containers, one 3litre
and one 5 litre
■ No markings on the container save for
the total volume marking
■ The tap has running water
■ Aim is to fetch 4 litres. How do we go
about it?
Puzzle Adapted from [Link]
4/8/24 | 4
Sample Solution to Problem 1
■ Fill the 5 litre can (B)
■ Pour water from the 5 litre can into the
3 litre one i.e. B into A
■ You remain with 2 Litres in B
■ Pour the 2 litres in B into A
■ Fill the container B
■ Pour the water in container B into A
■ Container B now has 4 litres
Puzzle Adapted from [Link]
4/8/24 | 5
Sample Problem 2
A farmer lives on a small plot of land next to a river. One day, he travels across the river in a small
boat and purchases a fox, a chicken, and a bag of corn from a feed and supply store. When the
farmer returns to his boat to cross the river again and go home, he realizes he has a dilemma.
The farmer can only take one item in his small boat at a time, otherwise he risks capsizing.
He cannot leave the fox alone with the chicken, because the fox will eat the chicken.
He cannot leave the chicken alone with the corn, because the chicken with eat the corn.
How does the farmer successfully get all three items across the river?
Adapted from [Link]
4/8/24 | 6
Sample Problem 2
■ Farmer Takes chicken across the river
■ Farmer goes back alone and takes the fox across the river
■ He then goes back with the chicken and takes the cabbage
across
■ Farmer goes back alone and takes the chicken across
Adapted from [Link]
4/8/24 | 7
Sample Problem 3
Adapted from [Link]
4/8/24 | 8
Sample Problem 3: Solution
Adapted from [Link]
4/8/24 | 9
Sample Problem 4
Adapted from [Link]
4/8/24 | 10
Sample Problem 4
You ask "In which of those two directions do you live?"
A Citizen of the City of Lies will point to the City of Truth
A Citizen of the City of Truth will point to the City of Truth
Adapted from [Link]
4/8/24 | 11
Sample Problem 5
Let’s suppose you needed to measure a time of exactly 45 minutes but only had a couple
of old ropes coated in oil and a lighter. You know that each rope takes exactly 1 hour to
burn all the way through.
But the ropes do not burn at a uniform rate with spots that will burn a little faster than
others. Whatever the case, and location of these slow and fast burn spots, the entire rope
still burns up in exactly an hour.
You can burn the ropes at either end or at multiple points at the same time. How would
you measure exactly three-quarters of an hour?
Adapted from [Link]
4/8/24 | 12
Sample Problem 5: Solution
So here's what you do: Light one of the ropes on fire on both ends and light the
second rope on one end at the same time. When the first rope burns out, 30
minutes have elapsed. At that exact moment, you light the unlit end of the
second rope.
Because 30 minutes of the second rope have already been used up, 30 more
remain (though this does not necessarily mean that half of the rope's length has
been burned, it could be more or less). Lighting the other end at the moment the
first rope burns up will cause the remaining part of the second rope to burn up in
15 minutes. Once the second rope has been consumed by the flames, exactly
45 minutes have passed.
Adapted from [Link]
4/8/24 | 13
Real World Applications
■ Design a marketing campaign for company X
■ Your company experiencing a downsize. How to mitigate
■ Smear campaign against your company etc.
■ IS Project
4/8/24 | 14
Algorithms
|
Definition
■ Set of steps taken when solving a problem / Recipe for solving a
problem
■ Imagine the algorithm of Google Self Driving Car
Problem Algorithm Solution
4/8/24 | 16
Programmatic Definition
■ Well-defined computational procedure consisting of a set of
instructions, which takes input to produce some given output.
■ Embeds the complete logic of the program
Input Algorithm Output
4/8/24 | 17
Characteristics of An Algorithm
■ Exact steps – precisely and unambiguously described, leaving no
uncertainty e.g. lift the restriction is ambiguous
■ It must terminate – Has finite number of steps leading to solution
■ Must be effective – Provides correct answer to the problem
■ Must be general – Solve every instance of the problem
4/8/24 | 18
Representing Algorithms
■ Can be represented by pseudocode or flowcharts
■ E.g. to find minimum, maximum and average of a set of numbers
4/8/24 | 19
Representing Algorithms
■ Flowchart
4/8/24 | 20
Attempt the Following:
• Write an algorithm as a pseudocode and flowchart, for a program
that:
• Prompts the user to enter 15 numbers
• Computes the sum, maximum, minimum, average and product of
all the fifteen numbers
• Displays the output to the user as the sum, average, product,
maximum and minimum
4/8/24 Report for 2010 | 21
Questions?
4/8/24 | 22
Ole Sangale Road, Madaraka Estate. PO Box 59857-00200, Nairobi, Kenya
Tel: (+254) (0)703 034000/200/300 Fax : +254 (0)20 607498
Email: info@[Link] Website: [Link]
|