INTRODUCTION TO PROBLEM SOLVING

CONTENT – REVIEW
S.NO TOPIC
 1. Introduction
2. Steps for Problem Solving
3. Algorithm
4. Representation of Algorithms
5. Flow of Control
6. Verifying Algorithms
7. Comparison of Algorithm
8. Coding
9. Decomposition

1. INTRODUCTION
 Computers are used for solving various day-to-day problems.
 It is pertinent to mention that computers themselves cannot solve a problem.
 Precise step-by-step instructions should be given by us to solve the problem.
 Thus, the success of a computer in solving a problem depends on how correctly and
precisely we define the problem, design a solution (algorithm) and implement the
solution (program) using a programming language.
 Thus, problem solving is the process of identifying a problem, developing an
algorithm for the identified problem and finally implementing the algorithm to
develop a computer program.

2. Steps for Problem Solving

There are four steps in problem solving
 Analysing the problem , Developing an Algorithm , Coding , Testing and
Debugging
2.1 Analysing the problem
 It is important to clearly understand a problem before we begin to find the solution
for it.
 If we are not clear as to what is to be solved, we may end up developing a program
which may not solve our purpose.
 By analysing a problem, we would be able to figure out what are the inputs that our
program should accept and the outputs that it should produce.

2.2 Developing an Algorithm

 The solution for a problem is represented in step by step procedure called an algorithm.
 For a given problem, more than one algorithm is possible and we have to select the
most suitable solution.

2.3 Coding
 After finalising the algorithm, we need to convert the algorithm into the format which
can be understood by the computer to generate the desired solution.

2.4 Testing and Debugging

 The program created should be tested on various parameters.
 The program should meet the requirements of the user.
 In the presence of syntactical errors, no output will be obtained.
 In case the output generated is incorrect, then the program should be checked for
logical errors, if any.

3. Algorithm

Algorithm is the step by step procedure for solving the problem. Suppose following are the
steps required for an activity ‘riding a bicycle’:
 remove the bicycle from the stand,
 sit on the seat of the bicycle,
 start peddling,
  use breaks whenever needed and
 stop on reaching the destination.

Example:
Algorithm to find square of a number.

Step 1: Input a number and store it to num

Step 2: Compute num * num and store it in square
Step 3: Print square

3.1 Why do we need an Algorithm

 Writing an algorithm is mostly considered as a first step to programming.
 Once we have an algorithm to solve a problem, we can write the computer program
for giving instructions to the computer in high level language.
 If the algorithm is correct, computer will run the program correctly, every time.
 So, the purpose of using an algorithm is to increase the reliability, accuracy and
efficiency of obtaining solutions.

Characteristics of a good algorithm

• Precision — the steps are precisely stated or defined.
• Uniqueness — results of each step are uniquely defined and only depend on the
input and the result of the preceding steps.
• Finiteness — the algorithm always stops after a finite number of steps.
• Input — the algorithm receives some input.
• Output — the algorithm produces some output.
While writing an algorithm, it is required to clearly identify the following:
• The input to be taken from the user
• Processing or computation to be performed to get the desired result
• The output desired by the user

4. Representation of Algorithms
There are two common methods of representing an algorithm —flowchart and pseudocode.
Either of the methods can be used to represent an algorithm while keeping in mind the
following:
• it showcases the logic of the problem solution, excluding any implementational
details
• it clearly reveals the flow of control during execution of the program
4.1 Flowchart — Visual Representation of Algorithms
 A flowchart is a visual representation of an algorithm.
 A flowchart is a diagram made up of boxes, diamonds and other shapes, connected
by arrows.
Symbols Functions Descriptions
Also called “Terminator” symbol. It indicates
Start/End
where the flow starts and ends.
Also called “Action Symbol,” it represents a
Process
process, action, or a single step.
A decision or branching point, usually a
yes/no or true/ false question is asked, and
Decision
based on the answer, the path gets split into
two branches.
Also called data symbol, this parallelogram
Input/Output
shape is used to input or output data
Connector to show order of flow between
Arrow
shapes.
Flowchart to calculate square of a number

4.2 Pseudocode
A pseudocode (pronounced Soo-doh-kohd) is another way of representing an algorithm. It is
considered as a non-formal language that helps programmers to write algorithm. The word
“pseudo” means “not real,” so “pseudocode” means “not real code”. Following are some of
the frequently used keywords while writing
pseudocode:
• INPUT / • COMPUTE / • PRINT / • INCREMENT / • DECREMENT
• IF/ELSE, • WHILE , • TRUE / FALSE

Example:
Pseudocode for the sum of two numbers will be:
input num1
input num2
COMPUTE Result = num1 + num2
PRINT Result

4.5 Flow of Control

The flow of control depicts the flow of events as represented in the flow chart.

4.5.1 Sequence
  Sometimes the algorithm to either does some routine tasks in a repeated manner or
behave differently depending on the outcomes of previous steps.
 The statements are executed one after another is known as sequence.

4.5.2 Selection
Let us look at some other examples where decision making is dependent on certain
conditions. For example,
(i) Checking eligibility for voting.
Depending on their age, a person will either be allowed to vote or not allowed to vote:
• If age is greater than or equal to 18, the person is eligible to vote
• If age is less than 18, the person is not eligible to vote
(ii) Let us consider another example
If a student is 8 years old and the student likes Maths put the student in Group A
Otherwise
Put the student in Group B

Actions depending on true or false of a condition

Conditionals are written in the algorithm as follows:

If <condition> then
steps to be taken when the
condition is true/fulfilled
There are situations where we also need to take action when the condition is not fulfilled (In
above Figure). To represent that, we can write:
If <condition> is true then
steps to be taken when the condition is
true/fulfilled
otherwise
steps to be taken when the condition is
false/not fulfilled

4.6 Verifying Algorithms

 The software designer should make sure that the functioning of all the components
are defined correctly, checked and verified in every possible way.
 When we were told that the formula for the sum of first N natural numbers is N(N+1)
/ 2 , how did we verify it?
 Well, we can check this for small numbers, for which we can manually calculate the
sum.
 Let N = 6, then the sum is 1 + 2 + 3 + 4 + 5 + 6 = 21 Using formula we get sum =
6x(6+1) / 2
 The method of taking an input and running through the steps of the algorithm is
sometimes called dry run. Such a dry run will help us to:
1. Identify any incorrect steps in the algorithm
2. Figure out missing details or specifics in the algorithm
Write an algorithm to calculate the time taken to go from place A to C (T_total) via B
where time taken to go from A to B (T1) and B to C (T2) are given. That is, we want the
algorithm to add time given in hours and minutes. One way to write the algorithm is:
PRINT value for
T1 INPUT hh1
INPUT mm1
PRINT value for
T2 INPUT hh2
INPUT mm2
hh_total = hh1 + hh2 (Add hours)
mm_total = mm1 + mm2 (Add
mins) Print T_total as hh_total,
mm_total
Now let us verify. Suppose the first example we take is T1 = 5 hrs 20 mins and T2 = 7 hrs
30 mins. On dry run, we get the result 12 hrs and 50 mins. This looks fine.

4.7 Comparison of Algorithm

There can be four different ways to write algorithms to check whether a given number is
prime or not as shown below:
(i) Starting with divisor 2, divide the given number (dividend) and check if there are
any factors. Increase the divisor in each iteration and repeat the previous steps as
long as divisor < dividend. If there is a factor, then the given number is not prime
(ii) In (i), instead of testing all the numbers till the dividend, only test up to half of
the given value (dividend) because the divisor can not be more than half of the
dividend
(iii) In method (i), only test up to the square root of the dividend (numbers)
(iv) Given a prior list of prime number till 100, divide the given number by each
number in the list. If not divisible by any number, then the number is a prime else it
is not prime
All these four methods can check if a given number is prime or not. Now the question is
which of these methods is better or efficient?

Algorithm (i) requires large number of calculations (means more processing time) as it
checks for all the numbers as long as the divisor is less than the number. If the given
number is large, this method will take more
time to give the output.

Algorithm (ii) is more efficient than (i) as it checks for divisibility till half the number, and
thus it reduces the time for computation of the prime number.
Algorithm (iii) is even more efficient as it checks for divisibility till square root of the
number, thereby further reducing the time taken.
As algorithm (iv) uses only the prime numbers smaller than the given number for
divisibility, it further reduces the calculations. But in this method we require to store the list
of prime numbers first. Thus it takes additional
memory even though it requires lesser calculations.

Hence, algorithms can be compared and analysed on the basis of the amount of processing
time they need to run and the amount of memory that is needed to execute the algorithm.
These are termed as time complexity and space complexity, respectively. The choice of an
algorithm over another is done depending on how efficient they are in terms of processing
time required (time complexity) and the memory they utilize (space complexity).
4.8 Coding
 Once an algorithm is finalised, it should be coded in a high-level programming
language as selected by the programmer.
 The ordered set of instructions are written in that programming language by
following its syntax.
 Syntax is the set of rules or grammar that governs the formulation of the statements
in the language, such as spellings, order of words, punctuation, etc.

4.9 Decomposition
 The basic idea of solving a complex problem by decomposition is to 'decompose' or
break down a complex problem into smaller sub problems

Answer the Following Questions (Very Short Annswers)

1. Define Algorithm
2. What is decomposition?
3. Why do we need Algorithm?
4. What is meant by Debugging?

Answer the Following Questions (Short Answers)

1. Write an algorithm to find the greatest among two different numbers

2. Write a pseudocode to calculate the factorial of a number
3. Write an algorithm to fing greates among three numbers

Answer the Following Questions (LongAnswers)

1. Write pseudocode and draw flowchart to accept numbers till the user enters 0 and
then find their average.
2. Write a pseudocode and draw a flowchart where multiple conditions are checked to
categorize a person as either child (<13), teenager (>=13 but <20) or adult
(>=20),based on age specified:
3. Write an algorithm that accepts four numbers as input and find
the largest and smallest of them.