💡

chapter 4 introduction to problem solving

Introduction to Problem Solving

Computers are everywhere — in our homes, offices, and pockets.

They help us do tasks faster, more accurately, and more conveniently.

Example – Railway Ticket Booking

• Earlier: Booking tickets was slow and manual.
• Now: With computers, we can book anytime, anywhere using websites or apps.
• The system handles:
• Train details (type, compartments, berths, schedule)
• Multiple users booking at the same time
• Payment and confirmation instantly

Computerisation
• Meaning: Using computers to automate human tasks.
• Purpose: To make work faster, easier, and error-free.

Key Idea in Problem Solving

1. Identify the problem – Understand clearly what needs to be solved.
2. Design the solution – Create a step-by-step method (algorithm).
3. Implement the solution – Write a program in a programming language.

Note: Computers can’t solve problems on their own.

We must give them clear, precise instructions.

STEPS FOR PROBLEM SOLVING

1. Analysing the Problem

• Meaning: Understand exactly what you need to solve.
• Why? If you don’t understand the problem, your solution might not work.
• What to find out:
• What are the inputs? (What data will the program take in?)
• What are the outputs? (What should it give back?)
• Example: If you’re making a ticket booking system:
• Inputs → Passenger name, train number, seat type.
• Output → Ticket confirmation and details.

2. Developing an Algorithm
 • Meaning: Write step-by-step instructions in plain language before coding.
• Think of it like: Writing a recipe. Follow the steps, and you’ll always get the dish right.
• Example: For making tea:
1. Boil water.
2. Add tea leaves.
3. Add milk and sugar.
4. Serve.

3. Coding
• Meaning: Convert your algorithm into a language the computer understands (like
Python, C++, Java).
• Example: If your algorithm is for calculating the sum of two numbers, write it as a
Python program.

4. Testing and Debugging

• Meaning: Check if your program works for all possible cases and fix mistakes.
• Types of mistakes:
• Syntax errors: Wrong spelling or missing symbols in the code.
• Logic errors: The code runs but gives wrong results.
• Example: If your program to calculate average gives wrong answers, you must check
the formula.

5. Maintenance
• Meaning: After delivering the program, keep fixing bugs, answering user queries, and
adding new features.
• Example: A mobile app may work fine today but needs updates when a new phone
version comes out.

ALGORITHM

What is an Algorithm?

An algorithm is just a step-by-step set of instructions to solve a problem.

If you follow the steps exactly, you will get the right answer.

Everyday Example – Riding a Bicycle

Steps:
1. Take the bicycle off the stand.
2. Sit on the seat.
3. Start pedalling.
 4. Use brakes when needed.
5. Stop when you reach your destination.

Just like this, for any problem, we break it into clear steps from start to end.

Example Problem – Finding GCD of 45 and 54

Step 1: Find all numbers that divide 45.

→ 1, 3, 5, 9, 15, 45

Step 2: Find all numbers that divide 54.

→ 1, 2, 3, 6, 9, 18, 27, 54

Step 3: Find the biggest number common in both lists.

→9

GCD(45, 54) = 9

Important Points about Algorithms

• Definite start and end (You always know where to begin and when to stop).
• Finite steps (Not endless).
• Clear instructions (No confusion).
• Always works if followed correctly.

Why We Need an Algorithm

Think of an algorithm like a plan before building a house.

• If you start building without a plan, walls might not align, rooms might be too small, or
the door could open into a wall.
• Similarly, in programming, without a step-by-step plan (algorithm), you can end up with
a program that doesn’t work correctly.

In programming:
• Algorithm = Roadmap
• Code = Construction work
• If the algorithm is good, the code will work correctly every time.

Real-life Examples of Algorithms

• Google Search: Finds the most relevant results from billions of web pages.
• WhatsApp Message: Decides how to deliver your message quickly and securely.
• Word Search in a Document: Locates the exact word in seconds.
 • Uber/Ola Taxi Booking: Finds the nearest driver and calculates fare.
• Online Banking: Ensures money is sent to the right account.

All of these are powered by carefully designed algorithms.

A Good Algorithm Has These Qualities or characteristics of Good algorithm

1. Precision – Each step is clear and exact.
(Example: Recipe says “Add 2 teaspoons of sugar,” not “Add some sugar.”)
2. Uniqueness – The result of each step is predictable and doesn’t depend on guessing.
3. Finiteness – It finishes in a limited number of steps.
4. Input – Takes some starting information.
5. Output – Gives the final result.

When Writing an Algorithm, Identify:

• Input: What information will the user give? (e.g., two numbers)
• Processing: What calculations or steps will happen? (e.g., find divisors, compare)
• Output: What will the user get? (e.g., GCD value)

Representation of Algorithms
What It Means
After thinking about the problem and deciding the steps (algorithm), we need a clear way to
represent it so others can understand easily before coding.

There are two common ways to represent an algorithm:

1. Flowchart – Uses shapes and arrows to show the step-by-step flow.
2. Pseudocode – Looks like normal English but written in a structured way, without
worrying about actual programming syntax.

Key Points to Remember

• It should show the logic of solving the problem, not programming details.
• It must clearly display the order of execution — what happens first, next, and last.

Real-Life Example

Problem: Make tea

Flowchart:
• Start → Boil water → Add tea leaves → Add milk & sugar → Boil again → Serve → End.

Pseudocode:

START
START
Boil water
Add tea leaves
Add milk and sugar
Boil again
Serve tea
END

Flowchart — Visual Representation of Algorithms

A flowchart is like a picture of an algorithm.
It uses shapes + arrows to show the steps clearly.

Common Flowchart Symbols

• Oval (Start/End): Beginning or end of a process
• Rectangle (Process): Action/step to be done
• Diamond (Decision): A Yes/No question or True/False
• Parallelogram (Input/Output): Taking input or showing output
• Arrow: Shows the flow (what comes next)

Pseudocode — Text Representation of Algorithms

Pseudocode = Fake code (not real programming)

• Written in simple English with structured keywords.
• Cannot run on computer, but helps humans understand the logic.

Common keywords:
• INPUT → to take data
• COMPUTE → calculation
• PRINT → show result
• IF/ELSE → decision
• WHILE → loop

Benefits of Pseudocode
• Easy to understand for both programmers & non-programmers
• Prevents missing steps before coding
• Works like a rough draft before actual program

Flow of Control
Flow of control is the way your program moves through instructions. It can:
• Run steps one after another (Sequence)
 • Choose between different paths (Selection)
• Repeat steps several times (Iteration / Loop)

1. Sequence
• Definition: Instructions executed one after the other in order.
• Example: Your morning routine—wake up → brush teeth → have breakfast.
• Programming Example:
Step 1: Input num1
Step 2: Input num2
Step 3: Compute sum = num1 + num2
Step 4: Output sum

2. Selection (Decision-making)
• Definition: Executes different steps based on a condition, like a decision point.
• Example: Deciding attire based on weather — if it’s raining, carry umbrella; otherwise,
go without it.
• Programming Example:
IF temperature > 30 THEN
PRINT "It's hot, wear a T-shirt"
ELSE
PRINT "Carry a jacket"

3. Iteration (Loop)
• Definition: Repeating a set of instructions until a condition is satisfied.
• Example: Eating all slices of pizza—take one slice, eat it, repeat until none are left.
• Programming Example:
WHILE slices > 0 DO
eat one slice
slices = slices - 1
END

VERIFYING ALGORITHMS
Why Verify Algorithms?
• Software must work correctly.
• If an algorithm is wrong, the whole software gives wrong results.
• Example: In banking, if the transfer algorithm is wrong, you may lose money.
So, before using an algorithm in a program, we must test it.

How Do We Verify?
We check the algorithm by dry run:
• Take some inputs.
 • Go step by step through the algorithm.
• Check if the output is correct.
• If wrong → modify the algorithm.

Example: Algorithm to find the bigger number

Suppose we write an algorithm to find the larger of two numbers.

Algorithm (first version):

1. Input two numbers A and B.
2. If A > B → print A.
3. Else → print B.

Dry Run 1:

A = 10, B = 5
Result = 10 Correct

Dry Run 2:

A = 7, B = 12
Result = 12 Correct

Dry Run 3 (problem):

A = 8, B = 8
Algorithm says print B (8),
but actually both are equal, so result should be “Both are equal.”

Corrected Algorithm:
1. Input A and B.
2. If A > B → print A.
3. Else if B > A → print B.
4. Else → print “Both are equal.”

This way, by verifying with different inputs (dry run), we find the mistake and fix the
algorithm.

COMPARISON OF ALGORITHM
Why Compare Algorithms?
Sometimes, there is more than one way to solve a problem. Each way is written as an algorithm.
But not all algorithms are equally fast or efficient — so we need to compare them.

example :
Finding the lowest price of rice in different shops

You want to buy rice and there are many shops in the market. You want to check where the rice is
cheapest.

Different algorithms (ways) to solve the problem:

Method 1: Visit all shops one by one

• Go to every shop in the market and check the rice price.
• Compare all and find the lowest.
Takes a lot of time if the market has 100 shops.

Method 2: Visit only half the shops

• Instead of all 100 shops, you check only half (because you know the price won’t be
higher after a point).
Saves some time, but still needs many visits.

Method 3: Check only a few selected shops

• You already know some trusted shops where prices are usually lowest.
• So you check only those shops instead of all.
Much faster than visiting all shops.

Method 4: Use an app like Zomato/BigBasket/Amazon

• The app already has a list of prices for each shop.
• You just search “rice” and immediately get the cheapest option.
Very fast, but it needs extra memory/storage (the app maintains the list).

Conclusion:
• Checking all shops (Method 1) = More time, no memory needed.
• Using app (Method 4) = Less time, but more memory/storage.
• So, when we compare algorithms, we look at:
• Time complexity → How much time it takes
• Space complexity → How much memory/storage it uses

This is just like comparing shopping strategies!