Chapter 4: Introduction to Problem Solving

CBSE Unit: Unit 2, Python Programming (45 marks) Marks Weightage: ~3-5 marks Priority: HIGH, algorithm and flowchart questions common in exams

Key Concepts

4.1 Steps for Problem Solving

Solving a problem using a computer requires a systematic, methodical approach. The key steps are:

Analysing the problem - understand inputs, outputs, core functionalities
Developing an algorithm - step-by-step solution in natural language
Coding - converting algorithm into programming language
Testing and Debugging - verifying correctness, fixing errors

GIGO: Garbage In, Garbage Out, correctness of output depends on correctness of input.

Analysing the Problem

Before solving any problem, clearly identify:

What inputs the program should accept
What processing/computation is needed
What output the user expects

Example: To calculate area of a rectangle, Input: length, breadth, Process: area = length x breadth, Output: area

Testing and Debugging

Syntactical errors: program will not run at all (missing colon, wrong spelling)
Logical errors: program runs but gives wrong output (using + instead of *), Testing methods in software industry: unit testing, integration testing, system testing, acceptance testing
Maintenance: even after delivery, software needs updates and bug fixes over time

4.2 Algorithm, A finite sequence of steps required to get desired output, Has a definite beginning and end

Origin: Persian mathematician Al-Khwarizmi (~850 AD)

Characteristics of a Good Algorithm:

Precision: Steps precisely defined
Uniqueness: Results of each step uniquely defined
Finiteness: Always stops after finite steps
Input: Receives some input
Output: Produces some output

Why do we need an algorithm?

Acts as a roadmap before writing code, Without it, programmer may not visualise instructions clearly, Increases reliability, accuracy and efficiency of solutions, All software (search engines, apps, games, online banking) is based on algorithms

Algorithm Examples from NCERT

Example 1: Find the square of a number

Input: Number whose square is required, Process: Multiply the number by itself, Output: Square of the 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

Example 2: Find GCD of two numbers (45 and 54)

Step 1: Find the divisors of both numbers
        Divisors of 45: 1, 3, 5, 9, 15, 45
        Divisors of 54: 1, 2, 3, 6, 9, 18, 27, 54
Step 2: Find the largest common divisor
        Common divisors: 1, 3, 9
        GCD = 9

Example 3: Check whether a number is odd or even

Step 1: Input a number
Step 2: IF number MOD 2 == 0 THEN
            Print "Number is Even"
        ELSE
            Print "Number is Odd"

Example 4: Categorise a person by age

Step 1: INPUT Age
Step 2: IF Age < 13 THEN
            PRINT "Child"
        ELSE IF Age < 20 THEN
            PRINT "Teenager"
        ELSE
            PRINT "Adult"

Example 5: Accept 5 numbers and find their average (Repetition)

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

Example 6: Accept numbers until 0 and find average

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

Example 7: Add two time values (hours and minutes)

Step 1: INPUT hh1, mm1 (first time)
Step 2: INPUT hh2, mm2 (second time)
Step 3: hh_total = hh1 + hh2
Step 4: mm_total = mm1 + mm2
Step 5: IF mm_total >= 60 THEN
            hh_total = hh_total + 1
            mm_total = mm_total - 60
Step 6: PRINT hh_total, mm_total

Note: The initial version without Step 5 would fail for inputs like 4hrs 50min + 2hrs 20min = 6hrs 70min (wrong!). The corrected version gives 7hrs 10min.

4.3 Representation of Algorithms

Flowchart (Visual Representation)

A flowchart is a visual representation of an algorithm using standardised shapes connected by arrows.

Symbol	Name	Function
Oval/Rounded rectangle	Start/End (Terminator)	Indicates where flow starts and ends
Rectangle	Process	Represents action or computation
Diamond	Decision	Yes/No or True/False branching
Parallelogram	Input/Output	Data input or output
Arrow	Connector	Shows order of flow

Rules for drawing flowcharts:

Every flowchart must have exactly one Start and one End
Arrows show the direction of flow, never leave a shape without an outgoing arrow (except End)
Diamond (decision) must have exactly two outgoing branches: Yes and No
Process boxes have one input and one output flow
Keep the flowchart clean, flow should generally go top to bottom, left to right

Pseudocode (Text Representation), Non-formal language for representing algorithms

"Pseudo" means "not real", not directly executable by computer, Intended for human reading only
No specific standard exists, use clear, consistent keywords

Common Pseudocode Keywords:

Keyword	Purpose
INPUT	Accept data from user
PRINT	Display output
COMPUTE	Perform calculation
INCREMENT	Increase by 1
DECREMENT	Decrease by 1
SET	Assign a value
IF / ELSE	Conditional branching
WHILE	Loop (repeat while condition true)
TRUE / FALSE	Boolean values
END IF / END WHILE	Mark end of block

Benefits of Pseudocode:

Represents basic functionality before writing actual code, Safeguards against leaving out important steps, Easier for non-programmers to read and review, Language-independent, same pseudocode can be converted to Python, Java, C++

Pseudocode Examples

Sum of two numbers:

INPUT num1
INPUT num2
COMPUTE Result = num1 + num2
PRINT Result

Area and perimeter of a rectangle:

INPUT length
INPUT breadth
COMPUTE Area = length * breadth
PRINT Area
COMPUTE Perim = 2 * (length + breadth)
PRINT Perim

Check odd or even:

PRINT "Enter the Number"
INPUT number
IF number MOD 2 == 0 THEN
    PRINT "Number is Even"
ELSE
    PRINT "Number is Odd"
END IF

Find factorial of a number:

INPUT n
SET factorial = 1
SET counter = 1
WHILE counter <= n
    factorial = factorial * counter
    INCREMENT counter
END WHILE
PRINT factorial

Print all multiples of 5 between 10 and 25:

SET num = 10
WHILE num <= 25
    IF num MOD 5 == 0 THEN
        PRINT num
    END IF
    INCREMENT num
END WHILE

Find largest of three numbers:

INPUT a, b, c
IF a >= b AND a >= c THEN
    PRINT a, "is largest"
ELSE IF b >= a AND b >= c THEN
    PRINT b, "is largest"
ELSE
    PRINT c, "is largest"
END IF

Water bill calculation (slab-based):

INPUT units
SET bill = 0
IF units <= 100 THEN
    bill = units * 5
ELSE IF units <= 250 THEN
    bill = 100 * 5 + (units - 100) * 10
ELSE
    bill = 100 * 5 + 150 * 10 + (units - 250) * 20
END IF
bill = bill + 75          (meter charges)
PRINT "Total bill:", bill

4.4 Flow of Control

Sequence, Statements executed one after another in order, No branching or repetition, Examples: sum of two numbers, area calculation

Selection (Decision Making), One of the alternatives selected based on condition outcome

Uses IF/ELSE construct, Based on True/False (binary) values, Can have multiple conditions: IF / ELSE IF / ELSE

NCERT Card Game Example - "Dragons and Wizards":

IF (shape is diamond) OR (shape is club) THEN
    INCREMENT Dpoint
ELSE IF (shape is heart) AND (value is number) THEN
    INCREMENT Wpoint
ELSE IF (shape is heart) AND (value is not a number) THEN
    INCREMENT Dpoint
ELSE
    INCREMENT Wpoint
END IF

This example shows use of AND and OR logical operators in conditionals.

Repetition (Iteration/Looping), Repeating a set of steps until a condition is met

Controlled by a loop variable or condition, Must eventually terminate (avoid infinite loops), Two types:
Counter-controlled: repeat a fixed number of times (e.g., "do this 5 times")
Condition-controlled: repeat until condition becomes false (e.g., "until user enters 0")

4.5 Verifying Algorithms

Dry run / Trace: Executing algorithm step by step manually on paper using test data, Check with multiple inputs including edge cases, Verify for boundary conditions, Helps identify:
1. Incorrect steps in the algorithm
2. Missing details or specifics

Dry Run Example: Average of 5 numbers

Input values: 3, 7, 2, 8, 5

Step	count	num	sum	Condition (count < 5)
Init	0	-	0	True
Iter 1	1	3	3	True
Iter 2	2	7	10	True
Iter 3	3	2	12	True
Iter 4	4	8	20	True
Iter 5	5	5	25	False (exit loop)

average = 25 / 5 = 5.0

Dry Run Example: Time Addition (verifying the corrected algorithm)

Input: T1 = 4hrs 50min, T2 = 2hrs 20min

Step	hh1	mm1	hh2	mm2	hh_total	mm_total	Condition
Input	4	50	2	20	-	-	-
Add	-	-	-	-	6	70	mm_total >= 60? Yes
Fix	-	-	-	-	7	10	-

Output: 7 hours 10 minutes (correct!)

4.6 Comparison of Algorithms, Multiple algorithms can solve the same problem, Compare based on: number of steps, time taken, memory required

Time complexity: amount of processing time needed
Space complexity: amount of memory required, Choose the most efficient algorithm

NCERT Example, Four algorithms to check if a number is prime:

Algorithm	Method	Efficiency
(i)	Check divisibility from 2 to n-1	Slowest, checks all numbers
(ii)	Check divisibility from 2 to n/2	Better, half the checks
(iii)	Check divisibility from 2 to sqrt(n)	Even better, far fewer checks
(iv)	Check divisibility only by known primes	Fastest computation, but needs extra memory

For n = 100:

Algorithm (i): up to 98 checks, Algorithm (ii): up to 49 checks, Algorithm (iii): up to 9 checks, Algorithm (iv): checks against [2, 3, 5, 7] only = 4 checks (but requires stored list)

4.7 Coding, Convert finalised algorithm into a high-level programming language

Syntax: set of rules/grammar governing formulation of statements
Source code: program written in a high-level language
Compiler/Interpreter: translates source code into machine language, High-level languages are portable (run on different types of computers), Choice of language depends on: platform (OS), type of application (desktop/mobile/web/embedded)

4.8 Decomposition, Breaking a complex problem into smaller, manageable sub-problems

Each sub-problem solved independently, Solutions combined for final solution, Helps in managing complexity, Different teams can work on different sub-problems

NCERT Example, Railway Reservation System decomposed into:

Trains' information (days, timings, stations, classes, berths)
Reservation information (booking open/close, available/waitlisted, cancellation, refund)
Food service
Billing service
Staff, security, railway infrastructure information
Other details

More real-life decomposition examples:

Weather forecasting: data collection + processing + prediction + alert generation, School event management: venue + invitations + budget + logistics + programme, Online shopping: product listing + cart + payment + shipping + returns

Important Definitions

#	Term	Definition
1	Algorithm	Finite sequence of well-defined steps to solve a problem
2	Flowchart	Visual/diagrammatic representation of an algorithm
3	Pseudocode	Informal textual representation of an algorithm (not executable)
4	Sequence	Executing statements one after another in order
5	Selection	Choosing a path based on condition (if/else)
6	Iteration/Repetition	Repeating steps until condition is met
7	Decomposition	Breaking complex problem into smaller sub-problems
8	GIGO	Garbage In, Garbage Out, wrong input leads to wrong output
9	Dry run/Trace	Manually executing algorithm step by step with test data
10	Time complexity	Amount of processing time an algorithm requires
11	Space complexity	Amount of memory an algorithm requires
12	Source code	Program written in a high-level language

Common Board Exam Question Patterns

Write algorithm/pseudocode for a given problem (3-4 marks)
Draw flowchart for a given problem (3-4 marks)
Identify flowchart symbols and their functions (1-2 marks)
Difference between algorithm and flowchart, pseudocode and flowchart (2 marks)
Characteristics of a good algorithm (2 marks)
Steps for problem solving (2 marks)
Trace/dry run an algorithm with given input (2-3 marks)
Decomposition - explain with example (2 marks)

Practice Problems

Short answer (2 marks each):

What is GIGO? Give an example.
List 4 characteristics of a good algorithm.
What is the difference between pseudocode and flowchart?
What is decomposition? Why is it important?
What is a dry run? Why do we perform it?

Algorithm/Pseudocode (3-4 marks each):

Write pseudocode that reads two numbers and divides one by another and displays the quotient.
Write pseudocode to print all multiples of 5 between 10 and 25 (including both).
Write pseudocode to calculate the factorial of a number.
Write an algorithm to find the greatest among two different numbers.
Write pseudocode to calculate the total water bill:

First 100 units: Rs 5/unit
Next 150 units: Rs 10/unit
Above 250 units: Rs 20/unit
Add meter charges of Rs 75/month

Write an algorithm to collect money from relatives. You need Rs 200. Different people give Rs 10, Rs 20, or Rs 50. Collect till total reaches 200.
Write pseudocode to accept a number and print "GREEN" (5-15), "BLUE" (15-25), "ORANGE" (25-35), or "ALL COLOURS ARE BEAUTIFUL" (any other).
Write an algorithm to accept four numbers and find the largest and smallest.

Flowchart (3-4 marks each):

Draw a flowchart to check whether a given number is an Armstrong number (e.g., 371 = 3^3 + 7^3 + 1^3).
Draw a flowchart to calculate the sum of first N natural numbers.
Draw a flowchart to determine if a person is eligible to vote (age >= 18).

Trace/Verify (2-3 marks each):

Verify the following algorithm for inputs 5, 9, 47, 99, 100, 200:
```
INPUT Number
IF Number < 9
    "Single Digit"
ELSE IF Number < 99
    "Double Digit"
ELSE
    "Big"
```
(Hint: It fails for 9 and 99, correct the conditions to <= 9 and <= 99)
The following algorithm accepts numbers 1-100. Find where it fails:
```
INPUT Number
IF (0 <= Number) AND (Number <= 100)
    ACCEPT
ELSE
    REJECT
```
(Hint: It accepts 0, which is not a positive integer. Fix: change 0 <= to 0 <)

Key Points Students Miss

Algorithm must be finite - it must terminate after a fixed number of steps
Flowchart diamond is for decisions (not processes), always has Yes/No branches
Pseudocode is for human understanding only - computer cannot execute it directly
Decomposition is key to solving complex problems, divide and conquer
An algorithm is independent of programming language - it's the logic, not the code
Always identify Input, Process, Output before writing an algorithm
Testing involves trying different inputs including edge cases and boundary values
When verifying algorithms, use boundary values - they are most likely to reveal errors (e.g., mm_total = 60)
In selection, conditions must cover all possible cases - including edge values like 9, 99 in the classify numbers example
A counter-controlled loop has a known number of iterations; a condition-controlled loop depends on user input or computed values

Board Exam Tips

When asked to write pseudocode, use consistent keywords (INPUT, PRINT, IF, WHILE, etc.)
When drawing flowcharts, always include Start and End ovals
For algorithm tracing questions, create a table with columns for each variable, show values at each step
"Write algorithm" and "write pseudocode" are treated as the same in most CBSE papers
Always mention the three flows of control if asked: sequence, selection, repetition
For comparison questions (algorithm vs flowchart), mention at least 3-4 points