PROBLEM SOLVING STRATEGIES

Problem solving is the process of identifying an existing problem,

determining the root cause or causes of the problem, deciding the best course
of action in order to solve the problem, and then finally implementing it to
solve the problem. Problem-solving is used to solve our everyday basic needs; and
there are many ways to solve problems. The countless number of everyday
solutions are as diverse and specialized as the problems themselves.
Problem solving techniques are great in variation and are nearly as important as the
problem solving itself. Without having proper techniques to begin the problem
solving process, individuals would find it much more difficult to do effectively. It
Includes: trial and error, algorithms and heuristics, means-ends-analysis, etc. This
list is by no means exhaustive and exemplifies how simple problem-solving
techniques can be as well as how different they are from one another at times.
Choosing the correct technique for the given situation is dependent on the
individual, their experience and their resourcefulness.

People face problems every day—usually. Sometimes these problems are

straight forward, however, the problems we encounter are more complex. For
example, say you have a work deadline, and you must mail a printed copy of a
report to your supervisor by the end of the business day. The report is time-
sensitive and must be sent overnight. You finished the report last night, but your
printer will not work today. What should you do? First, you need to identify the
problem and then apply a strategy for solving the problem.
Practicing different problem-solving strategies can help professionals develop
efficient solutions to challenges they encounter at work and in their everyday lives.
Each industry, business and career has its own unique challenges suggesting that
employees may implement different strategies to solve them.

Problem-solving strategies defined

Given a problem—be it a complex mathematical problem or a broken printer, the
main concern is mapping out a strategy to solve or fix it. Finding a solution implies
that the problem must first be clearly identified. After that, one of the many
problem solving strategies can be applied, hopefully resulting in a solution.
A problem-solving strategy is a plan used to find a solution or overcome a
challenge. Different strategies have different action plans associated with them. For
example, a well-known strategy is trial and error. Each problem-solving strategy
includes multiple steps to provide you with helpful guidelines on how to resolve
a business problem or industry challenge. Effective problem-solving requires you
to identify the problem, select the right process to approach it and follow a plan
tailored to the specific issue you are trying to solve.
Importance of Understanding Multiple Problem-solving Strategies
Problems themselves can be classified into two different categories known as ill-
defined and well-defined problems. Ill-defined problems represent issues that do
not have clear goals, solution paths, or expected solutions whereas well-defined
problems have specific goals, clearly defined solutions, and clear expected
solutions. Problem solving often incorporates logical reasoning and interpretation
of meanings behind the problem, and also in many cases require abstract thinking
and creativity in order to find novel solutions. Various methods of studying
problem solving exist including introspection, simulation, computer modelling, and
experimentation.
It is important to have a clear understanding of how a variety of problem-solving
strategies work because different problems are typically required to be approached
in different ways to find the best solution. By mastering several problem-solving
strategies, you can effectively select the right plan of action when faced with
challenges in the future. This can help you solve problems faster and develop
stronger critical thinking skills.

Trial and Error

A trial-and-error approach to problem-solving involves trying a number of different
solutions and ruling out those that do not work. This approach can be a good option
if you have a very limited number of options available. In terms of a broken printer
for example, one could try checking the ink levels, and if that doesn’t work, you
could check to make sure the paper tray isn’t jammed. Or maybe the printer isn’t
connected to a laptop. When using trial and error, one would continue to try
different solutions until the problem is solved. Although trial and error is not
typically one of the most time-efficient strategies, it is a commonly used one.

Algorithm and Heuristic

A common type of strategy is an algorithm. An algorithm is a problem- solving
formula that provides you with step-by-step instructions used to achieve a desired
outcome. You can think of an algorithm as a recipe with highly detailed instructions
that produce the same result every time they are performed. Algorithms are
used frequently in our everyday lives, especially in computer science. When you
run a search on the Internet, search engines like Google use algorithms to decide
which entries will appear first in your list of results. Facebook also uses algorithms
to decide which posts to display on your newsfeed. Can you identify other
situations in which algorithms are used?
A heuristic is another type of problem-solving strategy. While an algorithm must be
followed exactly to produce a correct result, a heuristic is a general problem-
solving framework. You can think of these as mental shortcuts that are used to
solve problems. A “rule of thumb” is an example of a heuristic. Such a rule saves
 the person time and energy when making a decision, but despite its time-saving
characteristics, it is not always the best method for making a rational decision.
Different types of heuristics are used in different types of situations, but the impulse
to use a heuristic occurs when one of five conditions is met:

• When one is faced with too much information

• When the time to make a decision is limited
• When the decision to be made is unimportant
• When there is access to very little information to use in making the decision
• When an appropriate heuristic happens to come to mind in the same moment

Working backwards is a useful heuristic in which you begin solving the problem by
focusing on the end result. It is common to use the working backwards heuristic to
plan the events of your day on a regular basis, probably without even thinking
about it.
Another useful heuristic is the practice of accomplishing a large goal or task by
breaking it into a series of smaller steps. Students often use this common method to
complete a large research project or long essay for school. For example, students
typically brainstorm, develop a thesis or main topic, research the chosen topic,
organize their information into an outline, write a rough draft, revise and edit the
rough draft, develop a final draft, organize the references list, and proofread their
work before turning in the project. The large task becomes less overwhelming when
it is broken down into a series of small steps.

Means-Ends Analysis
This strategy involves choosing and analysing an action at a series of smaller steps
to move closer to the goal. One example of means-end analysis can be found by
using the Tower of Hanoi paradigm. This paradigm can be modelled as a word
problem.
The actual Tower of Hanoi problem consists of three rods sitting vertically on a
base with a number of disks of different sizes that can slide onto any rod. The
puzzle starts with the disks in a neat stack in ascending order of size on one rod, the
smallest at the top making a conical shape. The objective of the puzzle is to move
the entire stack to another rod obeying the following rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing
it on top of another stack or on an empty rod.
3. No larger disc may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal moves required to
solve a Tower of Hanoi puzzle is 2n – 1, where 𝑛 is the number of disks. For
example, if there were 14 disks in the tower, the minimum amount of moves that
could be made to solve the puzzle would be 214 – 1 = 16,383 moves. There are
various ways of approaching the Tower of Hanoi or its related problems in addition
to the approaches listed above including an iterative solution, recursive solution,
non-recursive solution, a binary and Gray-code solutions, and graphical
representations.

An iterative solution entails moving the smallest pieces over one, then moving the
next over one and if there is no tower position in the chosen direction you are
moving to, move the pieces to the opposite end, but then continue to move in the
same direction. By doing this one will complete the puzzle in the minimum amount
of moves when there are 3 disks. Recursive solutions represent recognizing that the
puzzle can be broken down into a series of sub problems to each of which the same
general solving procedures apply, and then the total solution can be found by
putting together the sub solutions. Non-recursive solutions entail recognizing that
the procedures required to solve the problem have many regularities such as when
counting the moves starting at 1, position of the disk in the series to be moved
during move 𝑚 represents the number of times 𝑚 can be divided by 2 which
indicates that every odd move involves the smallest disk. This allows for the
following algorithm:
Move the smallest disk to the peg that it has not recently come from. Move another
disk legally (there will only be one possibility).

A binary and Gray solutions describe disk move numbers in binary notation (base-
2) where there is only one binary digit (a bit) for each disk and the most
significant (leftmost bit) represents the largest disk. A bit with a different value to
the previous one means that the corresponding disk is one position to the left or
right of the previous one.

Graphical representations, as their name imply, represent visual presentations of

conditions that can be modelled in order to view the most efficient and effective
solutions. A common graph for the Tower of Hanoi is represented by a
unidirectional, pyramid shaped graph, where different nodes (pieces within each
level of the graph) represent distributions of disks and the edges represent moves,
as shown in Fig. 1- 1-1 below.
Figure 1-1-1: Graphical representation of nodes (circles) and moves (lines) of
Tower of Hanoi.

Other Problem-solving Strategies

Here are some examples of problem-solving strategies that may equally be adopted
to see which works best for you in different situations:

Past Experience
Take the time to consider if you have encountered a similar situation to your current
problem in the past. This can help draw connections between different events. Ask
yourself how you approached the previous situation and adapt those solutions to
the problem currently being solved. For example, a company trying to market a
new clothing line may consider marketing tactics they have previously used, such
as magazine advertisements, influencer campaigns or social media
advertisements. By analysing what tactics have worked in the past, they can create
a successful marketing campaign again.

Bring in a facilitator
If one is trying to solve a complex problem with a group of other people, bringing
in a facilitator can help increase efficiency and mediate collaboration. Having an
impartial third party can help a group stay on task, document the process and have a
more meaningful conversation. Consider inviting a facilitator to your next group
meeting to help generate better solutions.
 Develop a decision matrix for evaluation
If multiple solutions are developed for a problem, one may need to determine which
one is the best. A decision matrix can be an excellent tool to help you approach this
task because it allows you to rank potential solutions. Some factors you can analyse
when ranking each potential solution are:
• Timeliness
• Risk
• Manageability
• Expense
• Practicality
• Effectiveness

After having decided which factors to include, use them to rank each potential
solution by assigning a weighted value of 0 to 10 in each of these areas. For
example, one solution may receive a score of 10 in the timeliness factor because it
meets all the requirements, while another solution may only receive a seven.
Having ranked each of the potential solutions based on these factors, add up the
total number of points each solution received. The solution with the highest number
of points should meet the most important criteria.

Ask your peers for help

Getting opinions from peers can expose new perspectives and unique solutions.
Friends, families or colleagues may have different experiences, ideas and skills that
may contribute to finding the best solution to a problem. Consider asking a diverse
range of colleagues or peers to share what they would do if they were in your
situation. Even if you don't end up taking one of their suggestions, the conversation
may help you process your ideas and arrive at a new solution.
Step away from the problem
Finally, if the problem being worked on does not need an immediate solution,
consider stepping away from it for a short period of time. You can do this literally
by taking a walk to help clear your mind or figuratively by setting the problem
aside for a few days until you are ready to approach it again. Allowing yourself
time to rest, exercise and take care of your own well-being can make solving the
problem easier when you come back to it because you may feel energised and
focused.

Regardless of the area of study, computer science is all about solving problems with
computers. Hence, it is important to first understand the computer’s information
processing model. The problems that we want to solve can come from any real-
world problem or perhaps even from the abstract world. We need to have a standard
systematic approach to solving problems. The model shown in Fig. 1-2-1 below
assumes a single CPU (Central Processing Unit). Many computers today have
multiple CPUs, so it can be imagined the above model being duplicated multiple
times within the computer.

Input devices

Storage/Network devices

Figure 1-2-1: Simplified Model of a Uniprocessor Computer

 A typical single CPU computer processes information as shown in the diagram.
Problems are solved using a computer by obtaining some kind of user input (e.g.,
keyboard/mouse information or game control movements), then processing the
input and producing some kind of output (e.g., images, text, sound). Sometimes the
incoming and outgoing data may be in the form of hard drives or network devices.

Computer as a model of computation

In regards to problem solving, we will apply the model in Fig. 2-1 and assume that
we are given some kind of input information that we need to work with in order to
produce some desired output as solution. However, the above model is quite
simplified. For larger and more complex problems, we need to iterate (i.e., repeat)
the input/process/output stages multiple times in sequence, producing intermediate
results along the way that solve part of our problem, but not necessarily the whole
problem. For simple computations, the above model is sufficient.

Definition 1-2-1: Problem Solving is the sequential process of analysing

information related to a given situation and generating appropriate response
options.
In solving a problem, there are some well-defined steps to be followed. For
example, consider how the input/process/output works on a simple problem:
Example: Calculate the average grade for all students in a class.
1. Input: get all the grades … possibly by typing them in via the keyboard or by
reading them from a USB flash drive or hard disk.
2. Process: add them all up and compute the average grade.
3. Output: output the answer to either the monitor, to the printer, to the USB flash
drive or hard disk … or a combination of any of these devices.
It is noted that the problem is easily solved by simply getting the input, computing
something and producing the output. We now examine the steps to problem solving
within the context of the above example.

Understand the Problem

It sounds strange, but the first step to solving any problem is to make sure that one
understands the problem about to be solved. One needs to know:
What input data/information is available?
• What does the data/information represent?
• In what format is the data/information?
• What is missing in the data provided?
• Does the person solving the problem have everything needed?
• What output information needs to be produced?
• In what format should the result be: text, picture, graph?
• What are the other requirements needed for computation?
In the example given above, it is understood that the input is a bunch of grades. But
we need to understand the format of the grades. Each grade might be a number
from 0 to 100 or it may be a letter grade from A to F. If it is a number, the grade
might be a whole integer like 73 or it may be a real number like 73.42. We need to
understand the format of the grades in order to solve the problem.

We also need to consider missing grades. What if we do not have the grade for
every student: for instance, some were away during the test? Should we be able to
include that person in our average (i.e., they received 0) or ignore them when
computing the average? We also need to understand what the output should be.
Again, there is a formatting issue. Should the output be a whole or real number or a
letter grade? Do we want to display a pie chart with the average grade? The choice
is ours. Finally, one needs to understand the kind of processing that must be
performed on the data. This leads to the next step.

Formulating a Model
The next step is to formulate a model for the problem. A model (or formula) is thus
needed for computing the average of a bunch of numbers. If there is no such
“formula”, one must be developed. In order to come up with a model, we need to
fully understand the information available to us. Assuming that the input data is a
bunch of integers or real numbers 𝑥1, 𝑥2, ⋯ , 𝑥𝑛 representing a grade percentage,
the following computational model may apply:
𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 = (𝑥1 + 𝑥2 + 𝑥3 + ⋯ + 𝑥𝑛)/𝑛
where the result will be a number from 0 to 100.
That is very straight forward, assuming that the formula for computing the average
of a bunch of numbers is known. However, this approach will not work if the input
data is a set of letter grades like B-, C, A+, F, D-, etc., because addition and
division cannot be performed on the letters. This problem solving step must figure
out a way to produce an average from such letters. Thinking is required.
After some thought, we may decide to assign an integer number to the incoming
letters as follows:
𝐴+ = 12 𝐵+ = 9 𝐶+ = 6 𝐷+ = 3
𝐴 = 11 𝐵 =8 𝐶 =5 𝐷 =2
𝐹=0
𝐴− = 10 𝐵− = 7 𝐶− = 4 𝐷− = 1
If it is assumed that these newly assigned grade numbers are
𝑦1, 𝑦2, ⋯ , 𝑦𝑛, then the following computational model may be used:
𝐴𝑣𝑒𝑟𝑎𝑔𝑒2 = (𝑦1 + 𝑦2 + 𝑦3 + ⋯ + 𝑦𝑛)/𝑛
where the result will be a number from 0 to 12.
As for the output, if it is to be represented as a percentage, then
𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 can either be used directly or one may use (𝐴𝑣𝑒𝑟𝑎𝑔𝑒2/12), depending
on the input that we had originally. If a letter grade is preferred as output, then one
may need to use (𝐴𝑣𝑒𝑟𝑎𝑔𝑒1/100 ∗ 12) or (𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 ∗ 0.12) or 𝐴𝑣𝑒𝑟𝑎𝑔𝑒2 and
then map that to some kind of “lookup table” that allows one to look up a grade
letter according to a number from 0 to 12.
The main point to understand in this step is that it is all about figuring out how to
make use of the available data to compute an answer.

Develop an Algorithm
Having understood the problem and formulated a model, it is time to come up
with a precise plan of what the computer is expected to do.

Definition 1-2-2: Algorithm is a precise sequence of instructions for solving a

problem.
Some of the more complex algorithms may be considered randomized algorithms
or non-deterministic algorithms where the instructions are not necessarily in
sequence and may not even have a finite number of instructions. However, the
above definition will apply for all algorithms that will be discussed in this course.
To develop an algorithm, the instructions must be represented in a way that is
understandable to a person who is trying to figure out the steps involved. Two
commonly used representations for an algorithm is by using (1) pseudocode, or (2)
flowcharts. Consider the following example for solving the problem of a broken
lamp. First is the example in a flowchart, and then in pseudocode, as presented in
Fig. 1-2-2 and Fig. 1- 2-3 respectively.
 Lamp not working

Lamp
plugged Plug in Lamp
in?

Yes

Bulb Yes
burned Replace Bulb
out?

No

Buy new Lamp

Figure 1-2-2: Flowchart for a broken Lamp

Pseudocode
1. IF lamp works, go to step 7.
2. Check if lamp is plugged in.
3. IF not plugged in, plug in lamp.
4. Check if bulb is burnt out.
5. IF blub is burnt, replace bulb.
6. IF lamp doesn’t work buy new lamp.
7. Quit ... problem is solved.

Figure 1-2-3: Flowchart for a broken Lamp

Note: pseudocode is a simple and concise sequence of English-like instructions to
solve a problem.
Pseudocode is often used as a way of describing a computer program to someone
who doesn’t understand how to program a computer.
Although flowcharts can be visually appealing, pseudocode is often the preferred
choice for algorithm development because:
• It can be difficult to draw a flowchart neatly, especially when mistakes are
made.
• Pseudocode fits more easily on a page of paper.
• Pseudocode can be written in a way that is very close to real program code,
making it easier later to write the program.
• Pseudocode takes less time to write than drawing a flowchart.
Pseudocode will vary according to whoever writes it. That is, one person’s
pseudocode is often quite different from that of another person. However, there are
 some common control structures (i.e., features) that appear whenever pseudocode is
written. These features are shown along with some examples:
• Sequence: Listing instructions step-by-step in order (often numbered)
1. Make sure switch is turned on
2. Check if lamp is plugged in
3. Check if bulb is burned out
4. ……
If lamp is not plugged in
then plug it in
If bulb is burned out then replace bulb Else buy new lamp
• Condition: Making a decision and doing one thing or something else depending on
the outcome of the decision.
• Repetition: repeating something a fixed number of times or until some condition
occurs
get a new light bulb
Repeat put it in the lamp
Until lamp works or no more bulbs left
Repeat 3 times Unplug lamp
Plug into different socket
…..
Storage: storing information for use in instructions further down the list
x ← a new bulb count ← 8

Transfer of Control: being able to go to a specific step when needed If

bulb works then goto step 7
Note:
• The bold in the above examples highlights the specific control structure.
• For the condition and repetition structures, the portion of the pseudocode that is part
of the condition or the repeat loop are indented a bit in order to make it clear that
these kinds of inner steps that belong to that structure. Braces ({ }) may also be
used to indicate what is in or out of a control structure as shown below:

If (bulb is burned out) then {

Replace bulb
}
Else {
Buy a new bulb
Repeat { }
Get a new light bulb Put it in the lamp
} until lamp works or no more bulbs left
Repeat 3 times { Unplug lamp
Plug into different socket}

The point is that there are a variety of ways to write pseudocode. The important thing
to remember is that the algorithm should be clearly explained with no ambiguity as to
what order the steps are performed in. Whether using a flow chart of pseudocode, an
algorithm should be tested by manually going through the steps in mentally to make
sure a step or a special situation is not missed out. Often, a flaw will be found in
one’s algorithm because a special situation that could arise was missed out.
Only when one is convinced that the algorithm will solve the problem, should the
next step be attempted.
Consider the previous example of finding the average of a set of 𝑛 grades stored in a
file. What would the pseudocode look like? Here is an example of what it might look
like if we had the example of 𝑛 numeric grades 𝑥1, 𝑥2, ⋯ , 𝑥𝑛 that were loaded from a
file:
Algorithm: Display Grades
1. set the sum of the grade values to 0.
2. load all grades 𝑥1, 𝑥2, ⋯ , 𝑥𝑛 from file.
3. repeat n times {
4. get grade xi
5. add xi to the sum

6. compute the average to be sum / n.

7. print the average

It would be wise to run through the above algorithm with a real set of numbers.
Each time an algorithm is tested with a fixed set of input data, this is known as a
test case.
Many test cases can be created. Here are some to try:
𝑛 = 5, 𝑥1 = 92, 𝑥2 = 37, 𝑥3 = 43, 𝑥4 = 12, 𝑥5 = 71…result should be 51
𝑛 = 3, 𝑥1 = 1, 𝑥2 = 1, 𝑥3 = 1……………………….…result should be 1
𝑛 = 0……………………………………………………result should be 0

Writing the Program

Writing a program is often called "coding" or “implementing an algorithm”. So the
code (or source code) is actually the program itself. Without much of an
explanation, below is a program (written in processing) that implements the given
algorithm for finding the average of a set of grades. Note that the code looks quite
similar in structure, however, the processing code is less readable and seems
somewhat more mathematical:
Pseudocode Processing code (Program)
1. set the sum of the grade values to int sum = 0;
0.
2. load all grades 𝑥1, 𝑥2, ⋯ , 𝑥𝑛 from byte[] x = loadBytes("numbers");
file.
3. repeat 𝑛 times {
for (int i=0; i<x.length; i++)
4. get grade 𝑥𝑖 sum = sum + x[i];
5. add 𝑥𝑖 to the sum
}
6. compute average to be sum/𝑛. int avg = sum / x.length;
7. print the average. print(avg);

For now, the details of how to produce the above source code will not be discussed.
In fact, the source code would vary depending on the programming language that
was used. Learning a programming language may seem difficult at first, but it will
become easier with practice.
The computer requires precise instructions in order to understand what it is being
asked to do. For example, removing one of the semi-colon characters (;) from the
program above, will make the computer become confused as to what it’s being
asked to do because the semi-colon characters (;) is what it understands to be the
end of an instruction. Leaving one of them off will cause the program to generate
what is known as a compile-time error.

Definition 1-2-3: Compiling is the process of converting a program into

instructions that can be understood by the computer.
The longer a program is, the more the likelihood of having multiple compile-time
errors. One needs to fix all such compile-time errors before continuing on to the
next step.

Test the Program

Running a program is the process of telling the computer to evaluate the compiled
instructions. When a program is run and all is well, you should see the correct
output. It is possible however, that a program works correctly for some set of input
data but not for all. If the output of a program is incorrect, it is possible that the
algorithm was not properly converted into a proper program. It is also possible that
the programmer did not produce a proper algorithm back in step 3 that handles all
situations that could arise. Perhaps some instructions are performed out of
sequence. Whatever happened, such problems with the program are known as bugs.
Definition 1-2-4: Bugs are errors with a program that cause it to stop working or
produce incorrect or undesirable results.
It is the responsibility of the programmer to fix as many bugs in a program as
present. To find bugs effectively, a program should be tested with many test cases
(called a test suite). It is also a good idea to have others test one’s program because
they may think up situations or input data that one may never have thought of.

Definition 1-2-5: Debugging is the process of finding and fixing errors in program
code.
Debugging is often a very time-consuming “chore” when it comes to being a
programmer. However, if one painstakingly and carefully follows steps 1 through 3,
this should greatly reduce the amount of bugs in a program, thus making debugging
much easier.

Evaluating the Solution

Once the program produces a result that seems correct, the original problem
needs to be reconsidered to make sure that the answer is formatted into a
proper solution to the problem. It is often the case that it may be realised that the
program solution does not solve the problem the way it is expected. It may also be
realized that more steps are involved. For example, if the result of a program is a
long list of numbers, but the intent was to determine a pattern in the numbers or
to identify some feature from the data, then simply producing a list of numbers
may not suffice. There may be a need to display the information in a way that
helps visualize or interpret the results with respect to the problem; perhaps a
chart or graph is needed. It is also possible that when the results are examined,
it is realised that additional data are needed to fully solve the problem.
Alternatively, the results may need to be adjusted to solve the problem more
efficiently (e.g., a game is too slow).
It is important to remember that the computer will only do what it is told to do. It is
up to the user to interpret the results in a meaningful way and determine whether or
not it solves the original problem. It may be necessary to re-do some of the steps
again, perhaps going as far back as step 1 again, if data were missing.
The decision to get a solution to any existing problem involves a cycle that
consist of the following using a Computer as a model of computation,
Understanding the Problem, Formulating a Model, Developing an Algorithm,
Writing the Program, Testing the Program and finally Evaluating the Solution.
It is important to emphasize, however, that there are usually many different
problem-solving processes with different steps, and the afore stated is simply meant
as a guide. Problem-solving in real world situations requires a great deal of
resourcefulness, flexibility, resilience and continuous interaction with the
environment.
COMPUTATIONAL APPROACHES TO PROBLEM-SOLVING
Solving a problem involves finding a way to move from a current situation to a
desired outcome. To be able to solve a problem using computational approaches, the
problem itself needs to have certain characteristics such as:
• The problem needs to be clearly defined — this means that one should be able to
identify the current situation, the end goal, the possible means of reaching the end
goal, and the potential obstacles
• The problem needs to be computable — one should consider what type of
calculations are required, and if these are feasible within a reasonable time frame
and processing capacity
• The data requirements of the problem need to be examined, such as what types of
data the problem involves, and the storage capacity required to keep this data
• One should be able to determine if the problem can be approached using
decomposition and abstraction, as these methods are key for tackling complex
problems.
Once these features of the given problem are identified, an informed decision can
then be made as to whether the problem is solvable or not using computational
approaches.

Brute-force Approach
This strategy is characterized by a lack of sophistication in terms of their approach
to the solution. It typically takes the most direct or obvious route, without
attempting to minimize the number of operations required to compute the solution.
Brute-force approach is considered quite often in the course of searching. In a
searching problem, we are required to look through a list of candidates in an
attempt to find a desired object. In many cases, the structure of the problem itself
allows us to eliminate a large number of the candidates without having to actually
search through them. As an analogy, consider the problem of trying to find a frozen
pie in an unfamiliar grocery store. You would immediately go to the frozen food
aisle, without bothering to look down any of the other aisles. Thus, at the outset of
your search, you would eliminate the need to search down most of the aisles in the
store. Brute force approach, however, ignores such possibilities and naively search
through all candidates in an attempt to find the desired object. This approach is
otherwise known as exhaustive search.

Example:
Imagine a small padlock with 4 digits, each from 0-9. You forgot your combination,
but you don't want to buy another padlock. Since you can't remember any of the
digits, you have to use a brute force method to open the lock. So you set all the
numbers back to 0 and try them one by one: 0001, 0002, 0003, and so on until it
opens. In the worst case scenario, it would take 104, or 10,000 tries to find your
combination.

Divide-and-conquer Approach
In the divide and conquer strategy, a problem is solved recursively by applying
three steps at each level of the recursion: Divide, conquer, and combine.

Divide
“Divide” is the first step of the divide and conquer strategy. In this step the problem
is divided into smaller sub-problems until it is small enough to be solved. At this
step, sub-problems become smaller but still represent some part of the actual
problem. As stated above, recursion is used to implement the divide and conquer
algorithm. A recursive algorithm calls itself with smaller or simpler input values,
known as the recursive case. So, when the divide step is implemented, the recursive
case is determined which will divide the problem into smaller sub- problems.
Then comes the “conquer” step where we straightforwardly solve the sub-problems.
By now, the input has already been divided into the smallest possible parts and
we’re now going to solve them by performing basic operations. The conquer step is
normally implemented with recursion by specifying the recursive base case. Once
the sub- problems become small enough that it can no longer be divided, we say
that the recursion “bottoms out” and that we’ve gotten down to the base case. Once
the base case is arrived at, the sub-problem is solved.

Combine
In this step, the solution of the sub-problems is combined to solve the whole
problem. The output returned from solving the base case will be the input of larger
sub-problems. So after reaching the base case we will begin to go up to solve larger
sub-problems with input returned from smaller sub-problems. In this step, we
merge output from the conquer step to solve bigger sub-problems. Solutions to
smaller sub-problems propagate from the bottom up until they are used to solve the
whole original problem.

Example: The Merge Sort Algorithm

The merge sort algorithm closely follows the divide and conquer paradigm. In the
merge sort algorithm, we divide the n-element sequence to be sorted into two
subsequences of 𝑛 = 2 elements each. Next, we sort the two subsequences
recursively using merge sort. Finally, we combine the two sorted subsequences to
produce the sorted answer.
Let the given array be:

Divide the array into two halves

Again, divide each subpart recursively into two halves until you get individual
elements.

Now, combine the individual elements in a sorted manner. Here,

conquer and combine steps go side by side.

Advantages of Divide and Conquer Algorithms

The first, and probably the most recognizable benefit of the divide and conquer
paradigm is the fact that it allows us to solve difficult problems. Being given a
difficult problem can often be discouraging if there is no idea how to go about
solving it. However, with the divide and conquer method, it reduces the degree of
difficulty since it divides the problem into easily solvable sub-problems.
Another advantage of this paradigm is that it often plays a part in finding other
efficient algorithms. In fact, it played a central role in finding the quick sort and
merge sort algorithms. It also uses memory caches effectively. The reason for this
is the fact that when the sub-problems become simple enough, they can be
solved within a cache, without having to access the slower main memory, which
saves time and makes the algorithm more efficient. And in some cases, it can even
produce more precise outcomes in computations with rounded arithmetic than
iterative methods would.

In the divide and conquer strategy problems are divided into sub- problems that can
be executed independently from each other. Thus, making this strategy suited for
parallel execution.

Disadvantages of Divide and Conquer Algorithms

One of the most common issues with this sort of algorithm is the fact that the
recursion is slow, which in some cases outweighs any advantages of this divide and
conquer process. Another concern with it is the fact that sometimes it can become
more complicated than a basic iterative approach, especially in cases with a
large n. In other words, if someone wanted to add large numbers together, if they
just create a simple loop to add them together, it would turn out to be a much
simpler approach than it would be to divide the numbers up into two groups, add
these groups recursively, and then add the sums of the two groups together.

Dynamic Programming Approach

Dynamic programming approach is similar to divide-and-conquer in that both solve
problems by breaking it down into several sub-problems that can be solved
recursively. The difference between the two is that in the dynamic programming
approach, the results obtained from solving smaller sub-problems are reused in the
calculation of larger sub- problems. Thus, dynamic programming is a bottom-up
technique that usually begins by solving the smallest sub=problems, saving these
results and then reusing them to solve larger and larger sub-problems until the
solution to the original problem is obtained. This is in contrast to the divide-and-
conquer approach, which solves problems in a top- down fashion. In this case the
original problem is solved by breaking it down into increasingly smaller sub-
problems, and no attempt is made to reuse previous results in the solution of any of
the sub-problems.
It is important to realise that a dynamic programming approach is only justified if
there is some degree of overlap in the sub-problems. The underlying idea is to
avoid calculating the same result twice. This is usually accomplished by
 constructing a table in memory, and filling it with known results as they are
calculated (memoization). These results are then used to solve larger sub-problems.
Note that retrieving a given result from this table takes Θ(1) time.
Dynamic programming is often used to solve optimisation problems. In an
optimisation problem, there are typically large number of possible solutions, and
each has a cost associated with it. The goal is to find a solution that has the smallest
cost (i.e., optimal solution).

Example: Fibonacci Series

Let's find the Fibonacci sequence up to the 5th term. A Fibonacci series is the
sequence of numbers in which each number is the sum of the two preceding ones.
For example, 0,1,1, 2, 3. Here, each number is the sum of the two preceding
numbers.

Algorithm
Let 𝑛 be the number of terms.
1. If 𝑛 ≤ 1, return 1.
2. Else return the sum of two preceding numbers.
We are calculating the Fibonacci sequence up to the 5th term.
1. The first term is 0.
2. The second term is 1.
3. The third term is sum of 0 (from step 1) and 1(from step 2), which is 1.
4. The fourth term is the sum of the third term (from step 3) and second term
(from step 2) i.e. 1 + 1 = 2.
5. The fifth term is the sum of the fourth term (from step 4) and third term (from
step 3) i.e. 2 + 1 = 3.
Hence, we have the sequence 0,1,1, 2, 3. Here, we have used the results of the
previous steps as shown below. This is called a dynamic programming approach.

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)

Recursion vs Dynamic Programming

Dynamic programming is mostly applied to recursive algorithms. This is not a
coincidence, most optimization problems require recursion and dynamic
programming is used for optimization. But not all problems that use recursion can
use Dynamic Programming. Unless there is a presence of overlapping sub-problems
like in the Fibonacci sequence problem, a recursion can only reach the solution
using a divide and conquer approach. This is the reason why a recursive algorithm
like Merge Sort cannot use Dynamic Programming, because the sub- problems are
not overlapping in any way.

Randomized Approach
This approach is dependent not only on the input data, but also on the values
provided by a random number generator. If some portion of an algorithm involves
choosing between a number of alternatives, and it is difficult to determine the
optimal choice, then it is often more effective to choose the course of action at
random rather than taking the time to determine the vest alternative. This is
particularly true in cases where there are a large number of choices, most of which
are “good.”
Although randomising an algorithm will typically not improve its worst- case
running time, it can be used to ensure that no particular input always produces the
worst-case behaviour. Specifically, because the behaviour of a randomised
algorithm is determined by a sequence of random numbers, it would be unusual for
the algorithm to behave the same way on successive runs even when it is supplied
with the same input data.
Randomised approaches are best suited in game-theoretic situations where we want
to ensure fairness in the face of mutual suspicion. This approach is widely used in
computer and information security as well as in various computer-based games.
Solving problems is a key professional skill. Quickly weighing up available
options and taking decisive actions to select the best computational approach to a
problem is integral to efficient performance.
It is important to always get the problem-solving process right, avoiding taking too
little time to define the problem or generate potential solutions. A wide range of
computational techniques for problem solving exist, and each can be appropriate
given the peculiarity of the problem and the individual involved. The important
skills to attain are to assess the situation independently of any other factors and to
know when to trust your own instincts and when to ask for a second opinion on a
potential solution to a problem.
ROLE OF ALGORITHM IN PROBLEM SOLVING
Computational thinking allows us to take a complex problem, understand what it is
and develop possible solutions. The solutions can then be presented in a way that a
computer, a human or both, can understand. There are four cornerstones to
computational thinking:
• decomposition - breaking down a complex problem or system into smaller,
more manageable parts
• pattern recognition – looking for similarities among and within problems
• abstraction – focusing on the important information only, ignoring
irrelevant detail
• algorithms - developing a step-by-step solution to the problem, or the rules to
follow to solve the problem

Correctly applying all the four cornerstones will help to develop a computer-enabled
solution.

This approach involves taking a complex problem and breaking it down into a series
of small, more manageable problems (decomposition). Each of these smaller
problems can then be looked at individually, considering how similar problems have
been solved previously (pattern recognition) and focusing only on the important
details, while ignoring irrelevant information (abstraction). Next, simple steps or
rules to solve each of the smaller problems can be designed (algorithms).
Finally, these simple steps or rules are used to implement a computer- enabled
solution.
For example, when playing a videogame, depending on the game and in order to
complete a level, one may need to know:
• what items are needed to collect, how to collect them, and how much time one
has to collect them
• where the exit is and the best route to reach it in the quickest time possible
• what kinds of enemies there are and their weak points?
From these details, a strategy can be worked out for completing the level in the most
efficient way.
35