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 should be tested on various parameters
•The program should meet the requirements of the user
It must respond within the expected time
•It should generate correct output for all possible inputs

Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 6

 I PUC
Software industry follows standardised testing methods like,
Computer Science Chapter 4 Introduction to problem solving
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
•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

1. Representation of algorithm
There are two common methods of representing an algorithm
1.Flowchart
2.Pseudocode

2. 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
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U.indicates
College, Shivamogga
where the6 flow starts and
 ends. I PUC
Computer Science Chapter 4 Introduction to problem solving

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 path gets split into
two branches.
Input/output Also called data symbol, this
parallelogram shape is used to
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

Flowchart :

3. 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.
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 6
•It is a detailed description of instructions that a computer must follow in a particular order.
 I PUC
•It is intended for human reading and cannot be executed directly by the computer.
Computer Science Chapter 4 Introduction to problem solving
•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

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)
Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 6
 I PUC
PRINT Perim
Computer Science Chapter 4 Introduction to problem solving

Figure : Flowchart to calculate area and perimeter of a rectangle

4. 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.

5. 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
•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.

Dept. Of Computer
Conditionals areScience,
writtenSriinAdichunchanagiri
the algorithmInd.
asP.U. College, Shivamogga 6
follows:
 I PUC
If <condition> then steps to be taken when the condition is true/
fulfilledComputer Science Chapter 4 Introduction to problem solving

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 6

 I PUC
•Process: Check Age as per the given criteria
Computer Science Chapter 4 Introduction to problem solving
•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

6. 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.

Such
Dept. Ofa Computer
dry run will helpSriusAdichunchanagiri
Science, to: Ind. P.U. College, Shivamogga 6
 I PUC
1.Identify any incorrect steps in the algorithm
Computer Science
2.Figure out missing details or specifics inChapter 4
the algorithm Introduction to problem solving

•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.

7. 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).

Dept. Of Computer Science, Sri Adichunchanagiri Ind. P.U. College, Shivamogga 6

8. CODING
 I PUC
•Once an algorithm is finalised, it should be coded in a high-level programming language as selected
Computer
by the programmer. Science Chapter 4 Introduction to problem solving

•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.

9. 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 6

 I PUC
Computer Science Chapter 4 Introduction to problem solving
Reservation Information about
Trains information-
days, timings, information- booking staff, security
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 6