INTRODUCTION TO PROBLEM SOLVING (CSC 102)

INTRODUCTION

Regardless of the area of study, computer science is all about solving problems
with computers. 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. Since we will be using computers to
solve problems, it is important to first understand the computer’s information
processing model.

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, test, sound). Sometimes the
incoming and outgoing data may be in the form of hard drives or network devices.

In regards to problem solving, we will assume that we are given some kind of input
information that we need to work with in order to produce some desired output
solution. However, 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.

There are many definitions for “problem solving”.

PROBLEM SOLVING is the sequential process of analyzing information related

to a given situation and generating appropriate response options.

PROBLEM SOLVING is the act of defining a problem; determining the cause of

the problem; identifying, prioritizing, and selecting alternatives for a solution; and
implementing a solution.

PROBLEM SOLVING STRATEGIES

There are a number of different ways that people go about solving a problem.
Some of these strategies might be used on their own, but people may also employ a
range of approaches to figuring out and fixing a problem.

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. Examples
restarting your phone, turning off wifi, turning off Bluetooth in order to determine
why your phone is malfunctioning.

If there are many different choices, you are better off narrowing down the possible
options using another problem-solving technique before attempting trial-and-error.
Algorithms
An algorithm is a step-by-step procedure that will always produce the correct
solution. A mathematical formula is a good example of a problem-solving
algorithm. Another example of algorithm is Instruction manual for installing new
software on your computer.

Heuristics

A heuristic is a mental rule-of-thumb strategy that may or may not work in certain
situations. Unlike algorithms, heuristics do not always guarantee a correct solution.

However, using this problem-solving strategy does allow people to simplify

complex problems and reduce the total number of possible solutions to a more
manageable set. Examples working backwards, breaking a task into steps.

Insight

In some cases, the solution to a problem can appear as a sudden insight. This can
occur because you realize that the problem is actually similar to something that you
have dealt with in the past. However, the underlying mental processes that lead to
insight happen outside of awareness.
STEPS IN PROBLEM SOLVING

There are 6 steps that you should follow in order to solve a problem:

1. Understand / Define the Problem

2. Formulate a Model

3. Develop an Algorithm

4. Write the Program

5. Test the Program

6. Evaluate the Solution

Consider a simple example of 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 … perhaps 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.

As you can see, the problem is easily solved by simply getting the input,
computing something and producing the output. Let us now examine the 6 steps to
problems solving within the context of the above example.

STEP 1: UNDERSTAND/ DEFINE THE PROBLEM

It sounds strange, but the first step to solving any problem is to make sure that you
understand the problem that you are trying to solve. You need to know:

o What input data/information is available ?

o What does it represent ?

o What format is it in ?

o Is anything missing ?
o Do I have everything that I need ?

o What output information am I trying to produce ?

o What do I want the result to look like … text, a picture, a graph … ?

o What am I going to have to compute ?

In our example, we well understand 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 (e.g.,
some were away during the test) ? Do we want to 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 we output a whole or real number or a letter grade ? Maybe we want
to display a pie chart with the average grade. It is our choice. Finally, we should
understand the kind of processing that needs to be performed on the data. This
leads to the next step.

STEP 2: FORMULATE A MODEL

Now we need to understand the processing part of the problem. Many problems
break down into smaller problems that require some kind of simple mathematical
computations in order to process the data. In our example, we are going to compute
the average of the incoming grades. So, we need to know the model (or formula)
for computing the average of a bunch of numbers. If there is no such “formula”, we
need to develop one. Often, however, the problem breaks down into simple
computations that we well understand. Sometimes, we can look up certain
formulas in a book or online if we get stuck.

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
x1,x2,…,xn representing a grade percentage, we can use the following
computational model:

Average1 = (x1 + x2 + x3 + … + xn) / n

where the result will be a number from 0 to 100.

That is very straight forward (assuming that we knew the formula for computing
the average of a bunch of numbers). However, this approach will not work if the
input data is a set of letter grades like B-, C, A+, F, D-, etc.. because we cannot
perform addition and division 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:

A+ = 12 B+ = 9 C+ = 6 D+ = 3 F = 0

A = 11 B = 8 C = 5 D = 2

A- = 10 B- = 7 C- = 4 D- = 1

If we assume that these newly assigned grade numbers are y1,y2,…,yn, then we
can use the following computational model:

Average2 = (y1 + y2 + y3 + … + yn) / n

where the result will be a number from 0 to 12.

As for the output, if we want it as a percentage, then we can use either Average1
directly or use (Average2 / 12), depending on the input that we had originally. If
we wanted a letter grade as output, then we would have to use (Average1/100*12)
or (Average1*0.12) or Average2 and then map that to some kind of “lookup table”
that allows us to look up a grade letter according to a number from 0 to 12. Do you
understand this step in the problems solving process ? It is all about figuring out
how you will make use of the available data to compute an answer.

STEP 3: DEVELOP AN ALGORITHM

Now that we understand the problem and have formulated a model, it is time to
come up with a precise plan of what we want the computer to do.
 An algorithm is a precise sequence of instructions for solving a problem. An
Algorithm is a step by step process to solve 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 in may not
even have a finite number of instructions. However, the above definition will
apply for all algorithms.

To develop an algorithm, we need to represent the instructions in some way that

is understandable to a person who is trying to figure out the steps involved. Two
commonly used METHODS of representing an algorithm are:

(1) pseudo code

(2) flow charts.

PSEUDOCODE : is a simple and concise sequence of English-like instructions to

solve a problem. Pseudo code is often used as a way of describing a computer
program to someone who doesn’t understand how to program a computer. When
learning to program, it is important to write pseudo code because it helps you
clearly understand the problem that you are trying to solve. It also helps you avoid
getting bogged down with syntax details (i.e., like spelling mistakes) .

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.

• Pseudo code fits more easily on a page of paper.

• Pseudo code can be written in a way that is very close to real program code,
making it easier later to write the program .

• Pseudo code takes less time to write than drawing a flowchart.

Pseudo code will vary according to whoever writes it. That is, one person’s pseudo
code is often quite different from that of another person. However, there are some
common control structures (i.e., features or keywords) that appear whenever we
 write pseudoocode. The frequently used keywords are INPUT, COMPUTE,
PRINT, INCREMENT, IF/ELSE, WHILE, TRUE/FALSE.

FLOW CHAT: A flowchart is a graphical representation of an algorithm OR

A flowchart is a type of diagram that represents an algorithm, workflow or
process. Programmers often use it as a program-planning tool to solve a problem.
It makes use of symbols which are connected among them to indicate the flow of
information and processing.

Flowchart Symbols

Flowcharts use special shapes to represent different types of actions or steps in a

process. Lines and arrows show the sequence of the steps, and the relationships
among them. These are known as flowchart symbols.

Common Flowchart Symbols

 Rectangle Shape – Represents a process

 Oval or Pill Shape – Represents the start or end
 Diamond Shape – Represents a decision
 Parallelogram – Represents input/output
 Advantages of flowchart:

1. The Flowchart is an excellent way of communicating the logic of a program.

2. It is easy and efficient to analyze problem using flowchart.
3. During program development cycle, the flowchart plays the role of a guide or a
blueprint. Which makes program development process easier.
4. After successful development of a program, it needs continuous timely
maintenance during the course of its operation. The flowchart makes program or
system maintenance easier.
5. It helps the programmer to write the program code.
6. It is easy to convert the flowchart into any programming language code as it does
not use any specific programming language concept.

Disadvantage of flowchart
1. The flowchart can be complex when the logic of a program is quite complicated.
2. Drawing flowchart is a time-consuming task.
3. Difficult to alter the flowchart. Sometimes, the designer needs to redraw the
complete flowchart to change the logic of the flowchart or to alter the flowchart.
4. Since it uses special sets of symbols for every action, it is quite a tedious task to
develop a flowchart as it requires special tools to draw the necessary symbols.
5. In the case of a complex flowchart, other programmers might have a difficult time
understanding the logic and process of the flowchart.
6. It is just a visualization of a program, it cannot function like an actual program

STEP 4: WRITE THE PROGRAM

Now that we have a precise set of steps for solving the problem, most of the hard
work has been done. We now have to transform the algorithm from step 3 into a set
of instructions that can be understood by the computer. Writing a program is often
called "writing code" or “implementing an algorithm”. So the code (or source
code) is actually the program itself. The computer requires precise instructions in
order to understand what you are asking it to do. For example, if you removed one
of the semi-colon characters ( ; ) from a program , the computer would become
confused as to what you are doing because the ( ; ) is what it understands to be the
end of an instruction. Leaving one of them off will cause your program to generate
what is known as a compile error.

COMPILING is the process of converting a program into instructions that can be

understood by the computer. The longer your program becomes, the more likely
you will have multiple compile errors. You need to fix all such compile errors
before continuing on to the next step.

STEP 5: TEST THE PROGRAM

Once you have a program written that compiles, you need to make sure that it
solves the problem that it was intended to solve and that the solutions are correct.
 RUNNING a program is the process of telling the computer to evaluate the
compiled instructions. When you run your program, if all is well, you should see
the correct output. It is possible however, that your program works correctly for
some set of data input but not for all. If the output of your program is incorrect, it
is possible that you did not convert your algorithm properly into a proper program.
It is also possible that you did not produce a proper algorithm back in step 3 that
handles all situations that could arise. Maybe you performed some instructions out
of sequence. Whatever happened, such problems with your program are known as
bugs.

BUGS are problems/erroras with a program that cause it to stop working or

produce incorrect or undesirable results. You should fix as many bugs in your
program as you can find. To find bugs effectively, you should test your program
with many test cases (called a test suite). It is also a good idea to have others test
your program because they may think up situations or input data that you may
never have thought of. The process of finding and fixing errors in your code is
called debugging and it is often a very time-consuming “chore” when it comes to
being a programmer. If you take your time to carefully follow problem solving
steps 1 through 3, this should greatly reduce the amount of bugs in your programs
and it should make debugging much easier.

STEP 6: EVALUATE THE SOLUTION

Once your program produces a result that seems correct, you need to re-consider
the original problem and make sure that the answer is formatted into a proper
solution to the problem. It is often the case that you realize that your program
solution does not solve the problem the way that you wanted it to. You may realize
that more steps are involved.

For example, if the result of your program is a long list of numbers, but your 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 you visualize or interpret the results
with respect to the problem. Perhaps a chart or graph is needed.
CONCEPT OF AN ALGORITHM

Although nowadays algorithms are primarily associated with software and

computers, their origins lie much further in the past. They have been used
intuitively for centuries, for example in the form of regulatory systems,
instructions, rules for games, architectural plans and musical scores.

Even some illustrated art books in the Renaissance period, for example Albrecht
Dürer’s “Four Books on Measurement” in 1525, were in fact structured
instructions for producing paintings, sculptures and buildings. In the history of
music, too, from Bach and Mozart to Schönberg and Schillinger, we see
mathematical methods and even small mechanical devices being used to make the
process of musical composition easier.

Step by step instructions

But what exactly is meant by the term algorithm? Over time, the following
descriptions have emerged as definitions: “An algorithm is a procedure for
decision-making or an instruction on how to act which consists of a finite number
of rules” or “… a limited sequence of unambiguous elementary instructions which
exactly and completely describe the way to solve a specific problem.” This applies
regardless of whether it relates to mathematics, fine art or music.

However, the most well-known application of algorithms is undoubtedly their use

in computer programming. A program is an algorithm that is formulated in a
language that allows it to be processed by a computer. Every computer program – a
more advanced machine language – is therefore an algorithm. In this way, people
pass the work of processing the procedures required in production or decision-
making – often calculations requiring days or hours – to a machine.

Programming becomes ever more precise

The first algorithm designed for a mechanical computing machine – to calculate

probabilities using Bernoulli numbers – was written in 1842-1843 by the British
mathematician Ada Lovelace in her notes about the work of Charles Babbage’s
“Analytical Engine”, designed in 1833.

However, because the English inventor, mathematician and philosopher never

managed to complete his mechanical computing machine for general applications
in his lifetime, the algorithm for it was also never implemented.

“The Babbage machine was never built because it was too unwieldy and
complicated, even though the software for it was formulated,” reports Dr Manuel
Bachmann, a researcher at the University of Basel and lecturer at the University of
Lucerne, in his book “The triumph of the algorithm – how the idea of software was
invented”. Nevertheless, other computing machines did see the light of day and, in
parallel, more and more precise programming became necessary.

The most complex things can be calculated

In recent decades, algorithms have become a key aspect of information science and
the theory of complexity and computability, in particular. Any problem that can be
programmed can be resolved by an algorithm. Even the most complex things can
be calculated using ones and zeros.

That includes the “Dream of Pythagoras” – the ability to explain the world in the
relationships between whole numbers, and the vision of Gottfried Wilhelm Leibniz
that all rational truths are based on a kind of calculus. This is all reflected in a
digital philosophy and a view of the world based on algorithms which found its
most recent formulation in a book called “A New Kind of Science”, written in
2002 by the British physicist and mathematician, Stephen Wolfram.

Using numerous visual examples, he describes the power of cellular automata to

explain nature, compared with more traditional mathematical models. His views
are highly controversial in the scientific community – as has so often been the case
in the history of the algorithm.

*DÜRER (21 May 1471 – 6 April 1528) was a painter, printmaker, and theorist of
the German Renaissance. Born in Nuremberg, Dürer established his reputation
and influence across Europe when he was still in his twenties due to his high-
quality woodcut prints.

CHARACTERISTICS OF AN ALGORITHM

All Algorithms must satisfy the following criteria -

1)Input: There are more quantities that are extremely supplied.

2)Output: At least one quantity is produced.

3)Definiteness: Each instruction of the algorithm should be clear and

unambiguous.

4)Finiteness: The process should be terminated after a finite number of steps.

5)Effectiveness: Every instruction must be basic enough to be carried out

theoretically or by using paper and pencil.

PROPERTIES OF ALGORITHM
Simply writing the sequence of instructions as an algorithm is not sufficient to
accomplish certain task. It is necessary to have following properties associated
with an algorithm.

1. Non Ambiguity
Each step in an algorithm should be non-ambiguous. That means each
instruction should be clear and precise. The instruction in any algorithm
should not denote any conflicting meaning. This property also indicates the
effectiveness of algorithm.
2. Range of Input
The range of input should be specified. This is because normally the
algorithm is input driven and if the range of input is not being specified then
algorithm can go in an infinite state.

3. Multiplicity
The same algorithm can be represented into several different ways. That
means we can write in simple English the sequence of instruction or we can
write it in form of pseudo code. Similarly, for solving the same problem we
can write several different algorithms.
4. Speed
The algorithms written using some specified ideas. But such algorithm
should be efficient and should produce the output with fast speed.
5. Finiteness
The algorithm should be finite. That means after performing required
operations it should be terminate.

THE ROLE OF ALGORITHM IN PROBLEM SOLVING PROCESS

1. Better problems solving

Developing an algorithm involves identifying the process, key decision points as
well as the variables required for solving the problem. The identification of
decision points and process divides the task into various smaller steps that are more
manageable. This means problems that would normally have been impossible or
difficult to resolve wholesale are going to be approached like a series of much
smaller and solvable problems. By using algorithms, problem solving is made
more rational.

2. Improves efficiency
Algorithm makes decision making more consistent and more efficient. Efficiency
is the immediate result of both the specification and analysis process. An algorithm
acts like a reminder device and assists in making sure that all variables or small
parts of a certain problem or task are not overlooked. Presenting any solution
process like an algorithm therefore allows for more accurate communication.
Eventually, algorithm promotes expertise development as it facilitates the division
of work amongst the employees.

3. Provides clarity
If a problem solver is not aware of what was performed, it is likely that she or he
will not be aware of what went wrong. The presence of a detailed solution process
enables easier identification of errors and weaknesses in the whole process.
Reducing a vital task to several specified steps through using algorithm provides
clarity and it is a critical part of evaluation, control and analysis.

The only algorithm shortcoming is that it is time consuming and some people
consider it as a waste of resources.

EXAMPLES USING PSEUDOCODE, FLOW CHART AND ALGORITHM

TO SOLVE PROBLEMS.

EXAMPLE 1

Find the AREA of rectangle using pseudocode, flow chart, algorithm.

USING PSEUDOCODE:

 INPUT length
 INPUT breadth
 COMPUTE Area=length * breadth
 PRINT Area
 USING FLOW CHART

USING ALGORITHM

STEP 1: start

STEP 2: INPUT length, breadth

STEP 3: SET Area=length*breadth

STEP4: DISPLAY/PRINT/OUTPUT Area

STEP 5: STOP

EXAMPLE 2
Write pseudocode. Flow chart, algorithm to ADD two numbers.

USING PSEUDOCODE

 INPUT numb1
 INPUT numb2
 COMPUTE S = numb1 + numb2
 PRINT S

USING FLOW CHART

OR
USING ALGORITHM

STEP1: start

STEP2: Accept numb1

STEP3: Accept numb2

STEP 4: Add numb1+ numb2

STEP 5: DISPLAY RESULT

OR

STEP1: Enter numb1, numb2

STEP2: SET Sum = (numb1 + numb2)

STEP 3: Output Sum

STEP4: END

EXAPMPLE 3

Find the largest of three numbers.

USING PSEUDOCODE

START

READ a, b, c

INPUT a
INPUT b
INPUT c

IF a > b AND a > c THEN

OUTPUT a "is largest"
ELSE IF b > c THEN
OUTPUT b"is largest"
ELSE
OUTPUT c "is largest"
END IF

STOP

USING FLOW CHART

USING ALGORITHM

STEP1: Start

STEP2: Declare variables a, b, c.

STEP3: Read variables a, b, c.

STEP4: If a > b

If a > c

Display b is largest
Else

Display c is the largest

Else

If b > c

Display b is the largest

Else

Display c is the greatest

STEP5: Stop