I PUC Computer Science Chapter 4 Introduction to problem solving
INTRODUCTION TO PROBLEM SOLVING 15marks (2+2+6+5)
Problem solving :
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.
Steps for Problem Solving :
Key steps required for solving a problem are in following subsections,
1. Analysing the problem
2. Developing an algorithm
3. Coding
4. Testing and debugging
1. Analysing the problem
It is important to clearly understand a problem before we begin to find the solution for it.
List the principal components of the problem
Decide the core functionalities that out solution should have
Figure out inputs to be accepted and output to be produced
2. Developing an algorithm
It is essential to device a solution before writing a program code for a given problem
The solution is re[resented in natural language and is called an algorithm
There can be more than one algorithm is possible and we have to select the most suitable
solution
3. Coding
After finalising the algorithm, we need to convert the algorithm into the format which can
be understand by the computer
Different high level programming languages can be used for writing a program
4. Testing and debugging
The program created shoud be tested on various parameters
The program should meet the requirements of the user
It must respond within the expected time
It shoud generate correct output for all possible inputs
Software industry follows standardised testing methods like,
a. Unit or component testing
b. Integration testing
c. System testing
d. Acceptance testing
Algorithm:
A finite sequence of steps required to get the desired output is called an algorithm
It will lead to the desired result in a finite amount of time, if followed correctly
Algorithm has a definite end, and consists of a finite number of steps
Characteristics of a good algorithm
Precision – The steps are precisely started or defined
Uniqueness – Results of each step are uniquely defined and only depend on the input and
result of the preceding steps
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 1
I PUC Computer Science Chapter 4 Introduction to problem solving
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
Representation of algorithm
There are two common methods of representing an algorithm
1. Flowchart
2. Pseudocode
1. Flowchart
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
Each shape represents a step of the solution process
The Arrow represents the order or link among the steps
Flowchart symbol Function Description
Start/End Also called “Terminator” symbol. It
indicates where the flow starts and ends.
Process Also called “Action Symbol,” it
represents a process, action, or a single
step.
Decision A decision or branching point, usually a
yes/no or true/ false question is asked,
and based on the answer, the pathgets
split into two branches.
Input/output Also called data symbol, this
parallelogram shape is usedto input or
output data
Arrow Connector to show order of flow between
shapes.
Example: Write an algorithm to find the square of a number.
Before developing the algorithm, let us first identify the input, process and output:
• Input: Number whose square is required
• Process: Multiply the number by itself to get its square
• Output: Square of the number
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
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 2
I PUC Computer Science Chapter 4 Introduction to problem solving
Flowchart :
2. Pseudocode
The word “pseudo” means “not real,” so “pseudocode” means “not real code”.
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.
It is a detailed description of instructions that a computer must follow in a particular
order.
It is intended for human reading and cannot be executed directly by the computer.
No specific standard for writing a pseudocode exists.
Following are some of the frequently used keywords while writing pseudocode:
• INPUT
• COMPUTE
• PRINT
• INCREMENT
• DECREMENT
• IF/ELSE
• WHILE
• TRUE/FALSE
Example : Write an algorithm to display the sum of two numbers entered by user,
using both pseudocode and flowchart.
Pseudocode for the sum of two numbers will be:
INPUT num1
INPUT num2
COMPUTE Result = num1 + num2
PRINT Result
Figure: Flowchart to display sum of two number
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 3
I PUC Computer Science Chapter 4 Introduction to problem solving
Example : Write an algorithm to calculate area and perimeter of a rectangle, using both
pseudocode and flowchart.
Pseudocode for calculating area and perimeter of a rectangle.
INPUT length
INPUT breadth
COMPUTE Area = length * breadth
PRINT Area
COMPUTE Perim = 2 * (length + breadth)
PRINT Perim
Figure : Flowchart to calculate area and perimeter of a rectangle
Benefits of Pseudocode
By writing the code first in a human readable language, the programmer safeguards against
leaving out any important step.
For non-programmers, actual programs are difficult to read and understand, but pseudocode
helps them to review the steps to confirm that the proposed implementation is going to
achieve the desire output.
Flow Of Control
The flow of control depicts the flow of events as represented in the flow chart.
The events can flow in a sequence, or on branch based on a decision or even repeat some part
for a finite number of times.
In such situations algorithm can be written using,
1. Sequence
2. Selection
3. Repetition
1. Sequence
In Algorithms where all the steps are executed one after the other are said to execute in
sequence.
However, statements in an algorithm may not always execute in a sequence.
We may sometimes require the algorithm to either do some routine tasks in a repeated
manner or behave differently depending on the outcomes of previous steps.
2. Selection
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 4
I PUC Computer Science Chapter 4 Introduction to problem solving
The program checks one or more conditions and perform operations (sequence of actions)
depending on true or false value of the condition.
These true or false values are called binary values.
Conditionals are used to check possibilities.
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
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
In programming languages, ‘otherwise’ is represented using Else keyword. Hence, a true/false
conditional is written using if-else block in actual programs.
Example: Let us write an algorithm to check whether a number is odd or even.
Input: Any number
Process: Check whether the number is even or not
Output: Message “Even” or “Odd”
Pseudocode of the algorithm can be written as follows:
PRINT "Enter the Number" INPUT number
IF number MOD 2 == 0 THEN PRINT "Number is Even"
ELSE
PRINT "Number is Odd"
Figure: Flowchart to check whether a number is even or odd
Example 4.6: Let us write a pseudocode and draw a flowchart where multiple conditions are
checked to categorise a person as either child (<13), teenager (>=13 but <20) or adult (>=20),based
on age specified:
Input: Age
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 5
I PUC Computer Science Chapter 4 Introduction to problem solving
Process: Check Age as per the given criteria
Output: Print either “Child”, “Teenager”, “Adult”
Pseudocode is as follows:
INPUT Age
IF Age < 13 THEN
PRINT "Child" ELSE IF Age < 20 THEN
PRINT "Teenager"
ELSE
PRINT "Adult"
Figure: Flowchart to check multiple conditions
3.Repetition
In programming, repetition is also known as iteration or loop.
A loop in an algorithm means execution of some program statements repeatedly till some
specified condition is satisfied.
Example: Write pseudocode and draw a flowchart to accept 5 numbers and find their average.
Pseudocode will be as follows:
Step 1: SET count = 0, sum = 0
Step 2: WHILE count < 5 , REPEAT steps 3 to 5 Step 3: INPUT a number to num
Step 4: sum = sum + num Step 5: count = count + 1
Step 6: COMPUTE average = sum/5 Step 7: PRINT average
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 6
I PUC Computer Science Chapter 4 Introduction to problem solving
Figure: Flowchart to Calculate the Average of 5 Numbers
Example: Write pseudocode and draw flowchart to accept numbers till the user enters 0 and then
find their average.
Pseudocode is as follows:
Step 1: SET count = 0, sum = 0 Step 2: INPUT num
Step 3: WHILE num is not equal to 0, REPEAT Steps 4 to 6 Step 4: sum = sum + num
Step 5: count = count + 1 Step 6: INPUT num
Step 7: COMPUTE average = sum/count Step 8: PRINT average
Figure: Flowchart to accept numbers till the user enters 0
VERIFYING ALGORITHMS
When we have written an algorithm, we want to verify that it is working as expected.
To verify, we have to take different input values and go through all the steps of the
algorithm to yield the desired output for each input value and may modify or improve as per
the need.
The method of taking an input and running through the steps of the algorithm is sometimes
called dry run.
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 7
I PUC Computer Science Chapter 4 Introduction to problem solving
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
It is important to decide the type of input value to be used for the simulation.
In case all possible input values are not tested, then the program will fail.
Example: 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 h1
INPUT m1
PRINT value for T2 INPUT h2
INPUT m2
hh_total = h1 + h2 (Add hours)
m_total = m1 + m2 (Add mins)
Print T_total as h_total, m_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.
Now let us take another example where T1 = 4 hrs 50 mins and T2 = 2 hrs 20 mins, and we end up
getting the result as 6 hrs 70 mins which is not how we measure time. The result should have been 7
hrs 10 mins.
With this second example we realise that our algorithm will work only when m1 + m2 (m_total)
< 60. For all other cases, it will give us output not the way we want. When m_total >= 60, the algorithm
should increase the sum of hours (h_total) by 1 and reduce m_total by 60, i.e., (m_total - 60). So the
modified algorithm will be:
PRINT value for T1 INPUT hh1
INPUT m1
PRINT value for T2 INPUT hh2
INPUT m2
h_total = h1 + h2 (Add hours)
m_total = m1 + m2 (Add mins)
h_total = h1 + h2 (Add hours)
m_total = m1 + m2 (Add mins)
IF (m_total >= 60) THEN
h_total = h_total + 1
m_total = m_total - 60
PRINT T_total as h_total, m_total
Now we can simulate through algorithm for T1 = 4 hrs 50 mins and T2 = 2 hrs 20 mins, and get
T_total= 7 hrs and 10 mins, which means the algorithm is working correctly.
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 8
I PUC Computer Science Chapter 4 Introduction to problem solving
COMPARISON OF ALGORITHM
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 proecssing time required (time complexity) and the memory they utilise (space
complexity).
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.
The machine language or low-level language consisting of 0s and 1s only is the ideal way
to write a computer program.
Low-level languages are difficult to deal with and comprehend by humans.
This led to the invention of high-level languages, which are close to natural languages
and are easier to read, write, and maintain, but are not directly understood by the
computer hardware.
A wide variety of high-level languages, such as FORTRAN, C, C++, Java, Python, etc.,
exists.
A program written in a high-level language is called source code.
We need to translate the source code into machine language using a compiler or an
interpreter, so that the computer can understand it.
DECOMPOSITION
Decomposition is to 'decompose' or break down a complex problem into smaller sub
problems.
Breaking down a complex problem into sub problems also means that each sub problem can
be examined in detail.
Decomposition also helps in reducing time and effort as different sub problems can be
assigned to teams who are experts in solving such problems.
Once the individual sub problems are solved, it is necessary to test them for their
correctness and integrate them to get the complete solution.
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 9
I PUC Computer Science Chapter 4 Introduction to problem solving
Reservation Information about
Trains information-
information- booking staff, security
days, timings,
open or close available railway
stations, classes &
or waiting list, infrastructure
berths
cancellation & refund
Other details about
Food service Billing service railways
figure: Railway reservation system
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 10
