Introduction to Problem Solving Chapter Notes | Computer Science for Class 11 - Humanities/Arts PDF Download

Introduction

Computers are an integral part of daily life and help us perform tasks faster and with greater accuracy. For example, booking railway tickets online is possible because of computers and smartphones.

India has a vast and complex railway network, which makes railway reservations a challenging task. This process requires managing details of trains (types, berths, compartments, schedules) and handling many users attempting to book tickets at the same time.

Online reservation systems have made ticket booking convenient by allowing users to obtain tickets from anywhere at any time. The process of using computers and software to automate routine human tasks is called computerisation.

Problem solving is central to computer science because computers are tools used to solve a wide range of problems. However, computers cannot solve problems by themselves. They need precise, step-by-step instructions from humans. The success of any computer-based solution depends on how clearly the problem is defined, how well the solution (the algorithm) is designed, and how correctly that algorithm is implemented as a program in a programming language.

In short, problem solving with computers involves identifying a problem, creating an algorithm to solve it, and implementing the algorithm as a program.

Steps for Problem Solving

Solving a practical problem often requires several steps. For instance, if a vehicle makes an unfamiliar noise while driving, the owner first identifies the source of the noise. If the owner cannot fix it, they take the vehicle to a mechanic, who analyses the problem, plans the repair, and carries out the fix. This real-life process illustrates that problem solving is multi-step and systematic.

Some problems are simple and can be solved quickly, while others are complex and need systematic analysis and careful implementation. Problem solving with a computer generally follows these main steps, which are explained in the following subsections.

Analysing the Problem

Before attempting a solution, it is essential to understand the problem fully. If the problem is not clearly understood, the final program may not meet the intended objectives. Careful reading and analysis of the problem statement helps identify:

• What inputs are required
• What outputs are expected
• Constraints and special cases
• Major subtasks that must be performed

By analysing the problem, you determine the essential functionalities that your solution must provide.

Algorithm Development

An algorithm is a precise sequence of steps that, when followed, solves the problem or achieves the desired task. Before coding, design a clear algorithm in natural language or a representation such as pseudocode or a flowchart. Think of the algorithm as a recipe that specifies the exact steps to reach the goal.

Coding

• Translate the finalised algorithm into a programming language (a high-level language).
• Document the code and the overall solution. Documentation helps others and yourself when the program is reviewed or modified later.

Testing and Debugging

• Test the program with a variety of inputs to ensure it meets user requirements, is correct, and performs within acceptable time limits.
• Syntactical errors prevent the program from running. Logical errors cause incorrect outputs. Use testing methods such as unit testing, integration testing, system testing, and acceptance testing to validate the software.
• Debugging is the process of identifying and fixing errors found during testing. After debugging, retest until no errors remain.
• Maintenance continues after software delivery to fix issues that users may face and to keep the software functioning correctly as requirements evolve.

Algorithm

Many everyday activities require following a fixed order of steps. Examples include:

• Getting ready for school
• Making breakfast
• Riding a bicycle
• Wearing a tie
• Solving a puzzle

A finite sequence of steps that leads to the desired output when followed correctly is called an algorithm. An algorithm has a definite start and end and consists of a finite number of precise steps.

Example: Find the Greatest Common Divisor (GCD) of 45 and 54

Note: The GCD is the largest number that divides both given numbers.

Step 1: List divisors of 45 and 54.

Divisors of 45 are: 1, 3, 5, 9, 15, 45

Divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, 54

Step 2: Find the largest common divisor in both lists.

Common divisors: 1, 3, 9

Therefore, GCD(45, 54) = 9

Why Do We Need an Algorithm?

• A program is a set of instructions that guides a computer to perform tasks. Before writing a program, a programmer prepares a roadmap that outlines the exact sequence of steps; this roadmap is the algorithm.
• An algorithm ensures the intended sequence of operations is clear and reduces the risk of creating a program that does not work as intended.
• Many daily activities and digital services-such as web search, messaging, online taxi booking, online banking and games-are driven by algorithms.
• Writing an algorithm is the first step in programming. If the algorithm is correct, a correctly implemented program will produce the expected results every time.
• The principal purposes of algorithms are to improve reliability, accuracy and efficiency of solutions.

Characteristics of a Good Algorithm

• Precision: Each step is clearly and unambiguously defined.
• Uniqueness: Each step's outcome is uniquely determined by the input and previous steps.
• Finiteness: The algorithm stops after a finite number of steps.
• Input: The algorithm takes zero or more inputs.
• Output: The algorithm produces one or more outputs that satisfy the desired result.

While Writing an Algorithm, Identify

• The input to be taken from the user
• The processing or computation required
• The output desired by the user

Representation of Algorithms

After analysing a problem and determining the logical steps, these steps should be written down along with required inputs and desired outputs. Two common representations are flowcharts and pseudocode. Both should:

• Show the logic of the solution without implementation details
• Reveal the flow of control during execution

Flowchart - Visual Representation of Algorithms

A flowchart is a diagram made of boxes, diamonds and other shapes connected by arrows. Each shape represents a step, and arrows show the sequence. Flowcharts use standard symbols for common operations.

Shapes or Symbols to Draw Flowcharts

Example: Algorithm to find the square of a number

First identify input, process and output.

• Input: Number (num)
• Process: square = num × num
• Output: square

Algorithm to find the square of a number:

1. Input a number and store it in num
2. Compute square = num × num
3. Print square

The flowchart for this algorithm can be drawn using the standard symbols.

Flowchart to solve the problem of a non-functioning light bulb

Pseudocode

• Pseudocode is an informal language used to describe algorithms in a way that is easy for humans to read.
• It describes the steps a computer must take, arranged in sequence, using plain words and some structured keywords.
• Pseudocode cannot be executed by a computer directly.
• There are no fixed rules for writing pseudocode; the emphasis is on clarity.
• The term pseudo means "not real"; hence pseudocode is not actual code.
• Common pseudocode keywords include: INPUT, COMPUTE, PRINT, INCREMENT, DECREMENT, IF/ELSE, WHILE, TRUE/FALSE.

Example: Write an algorithm to display the sum of two numbers entered by the user, using both pseudocode and flowchart.

Sol:

Pseudocode:

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

The corresponding flowchart represents these steps in sequence.

Example: Write an algorithm to calculate area and perimeter of a rectangle, using both pseudocode and flowchart.

Sol:

Pseudocode:

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

The flowchart for this algorithm visualises input, computation and output steps.

Benefits of Pseudocode

• Clarity of Functionality: Helps outline basic functionality before coding.
• Readability for Non-Programmers: Allows reviewers who are not coders to understand and validate logic.
• Error Prevention: Helps catch logical mistakes early.
• Focus on Logic: Encourages concentration on the sequence and logic rather than language syntax.

Flow of Control

The flow of control is the order in which statements or operations are carried out in an algorithm or program. The three main types of flow are:

1. Sequence

Steps are executed one after the other in linear order without deviation. This is the simplest form of control.

2. Selection (Decision)

Execution branches according to conditions. A condition evaluates to true or false, and different actions are taken based on the result. Examples include choosing the best route based on traffic or checking voting eligibility.

• Checking voting eligibility: If a person is 18 years or older, they are eligible to vote; otherwise they are not eligible.
• Grouping students based on age and interest: If a student is 8 years old and likes Maths, place them in Group A; otherwise place them in Group B.
• Ravi (8 years old, dislikes Maths): Group B
• Priti (8 years old, likes Maths): Group A
• Anish (7 years old, likes Maths): Group B

In algorithms, conditional actions are typically written as:

IF <condition> THEN steps when condition is true ELSE steps when condition is false

In programming languages the else clause implements the "otherwise" behaviour.

Example 1: Checking whether a number is odd or even

Algorithm:

• Input: a number
• Process: Check if the number is even or odd
• Output: Print "Even" or "Odd"

Pseudocode:

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

Example 2: Categorising a person based on age

• Input: Age
• Process: Check age against given ranges
• Output: Print "Child", "Teenager", or "Adult"

Pseudocode:

INPUT Age IF Age < 13 THEN PRINT "Child" ELSE IF Age < 20 THEN PRINT "Teenager" ELSE PRINT "Adult"

3. Repetition (Iteration or Looping)

Repetition involves executing a set of instructions multiple times until a specified condition is met. Loops automate repetitive tasks.

• Example instruction: "Clap your hands five times" - repeat clapping five times.
• Card game example: Withdraw 10 cards - repeat the withdraw action 10 times.
• Daily routines like brushing or dressing also follow repeated steps.

Example: Finding the average of 5 numbers

Pseudocode:

• Initialize count and sum to 0
• Repeat while count < 5:
• Input a number and add it to sum
• Increment count by 1
• After loop, compute average = sum / 5
• Print average

Explanation: A counter keeps track of loop iterations. After each iteration increase the counter until it reaches the limit.

Example: Accept numbers until 0 is entered

Pseudocode:

• Initialize sum and count to 0
• Input num
• While num ≠ 0 do the following:
• Add num to sum
• Increment count by 1
• Input num (new value)
• After loop, compute average = sum / count
• Print average

Explanation: When the number of iterations is not known beforehand, a while loop checks the condition repeatedly until it becomes false.

Verifying Algorithms

Importance: Verification ensures that algorithms work correctly and produce expected results. Faulty algorithms can cause serious problems in critical systems such as banking, healthcare and aerospace.

Example: Verify the formula for the sum of first N natural numbers

• For N = 6, compute the sum: 1 + 2 + 3 + 4 + 5 + 6 = 21
• Formula: N(N + 1) / 2. For N = 6, compute 6 × 7 / 2 = 21, which confirms the formula for this case.

Dry Run Method:

• Dry run an algorithm by manually tracing it with different input values to check if it produces the correct outputs.
• This helps find incorrect steps, missing details or ambiguous parts in the algorithm.

Importance of Input Selection:

• Choose representative inputs, including edge cases, to ensure the algorithm works for all possible inputs. Failing to test all important cases may cause the program to fail in real use.

Activity 4.5: Write an algorithm to calculate the area and perimeter of a rectangular shape given the length and breadth in feet and inches (for example, 5 ft 6 in). Consider inputs in mixed units and show conversion steps before computing area and perimeter.

Notes

Concept of Algorithm - Definition: A step-by-step set of instructions to solve a problem is called an algorithm.

Example: Addition of Time

• We want to add two times, T1 and T2. Suppose T1 = 5 hours 20 minutes and T2 = 7 hours 30 minutes.
• We will create an algorithm to add these two times and adjust minutes if required.

Step 1: Input the values for T1

• PRINT value for T1
• INPUT hh1 (hours of T1)
• INPUT mm1 (minutes of T1)

Step 2: Input the values for T2

• PRINT value for T2
• INPUT hh2 (hours of T2)
• INPUT mm2 (minutes of T2)

Step 3: Calculate the total time

• hh_total = hh1 + hh2
• mm_total = mm1 + mm2

Step 4: Adjust if necessary

• IF mm_total >= 60 THEN
• hh_total = hh_total + 1
• mm_total = mm_total - 60

Step 5: Output the total time

• PRINT T_total as hh_total hours and mm_total minutes

Verification:

• Example 1: T1 = 5 h 20 m, T2 = 7 h 30 m
• hh_total = 5 + 7 = 12, mm_total = 20 + 30 = 50
• Result: T_total = 12 h 50 m (correct)
• Example 2: T1 = 4 h 50 m, T2 = 2 h 20 m
• hh_total = 4 + 2 = 6, mm_total = 50 + 20 = 70 (mm_total ≥ 60, adjustment needed)
• After adjustment: hh_total = 7, mm_total = 10
• Correct result: T_total = 7 h 10 m

Importance of Verification:

• Verification is crucial because errors in an algorithm will produce incorrect software.
• Fixing errors at the algorithm stage is usually easier than fixing them after full implementation.

Comparison of Algorithms

For a given problem there can be multiple algorithms. Choosing the best algorithm requires comparing them in terms of efficiency and resource usage. Consider the problem of checking whether a number is prime. Here are four possible algorithms:

• (i) Try dividing the number by all integers starting from 2 up to the number - 1. If any divisor divides evenly, the number is not prime.
• (ii) Try dividing the number by integers from 2 up to number/2. A divisor cannot be greater than half of the number.
• (iii) Try dividing by integers only up to the square root of the number. If no divisor ≤ √n divides the number, it is prime.
• (iv) Given a precomputed list of prime numbers up to a limit (for example up to 100 or up to √n), divide the number by those primes only. If none divide evenly, the number is prime. This reduces checks but requires extra memory to store the list.

All methods determine primality, but they differ in efficiency. Method (i) is least efficient; method (iii) is much better; method (iv) can be very efficient if a list of prime divisors is available and memory allows it.

Time Complexity

• Time complexity measures how the running time of an algorithm grows with input size (usually expressed using Big O notation).
• For example, O(n) indicates the time grows linearly with input size n.

Space Complexity

• Space complexity measures the amount of memory required by an algorithm as a function of input size.
• It includes memory for input and auxiliary space used by the algorithm.

Coding

• Coding is the process of translating an algorithm into a program using a programming language.
• Key steps in coding:

• Choose a Programming Language: Select a suitable high-level language such as Python, Java, C++ or JavaScript.
• Set Up the Development Environment: Install and configure tools like text editors, IDEs and compilers or interpreters.
• Write the Code: Implement the algorithm following language syntax; organise code into functions or modules.
• Test the Code: Execute the program with various inputs and debug errors.
• Optimise the Code: Improve performance and reduce resource usage where necessary.
• Document the Code: Add comments and documentation for future maintenance.

Decomposition

When a problem is complex, break it down into smaller, manageable sub-problems. This process is called decomposition. Solve each sub-problem independently and combine solutions to form the overall solution.

For example, a Railway Reservation System can be decomposed into sub-systems such as:

• Train information: days, timings, stations, classes and berths
• Reservation details: booking, availability checks, waiting list, cancellation and refund
• Staff and security management
• Railway infrastructure and scheduling
• Billing services and transaction management
• On-board or station food services

Decomposition allows teams to work in parallel on different components according to their expertise. It is applicable to many real-life problems such as:

• Solving complex mathematical or scientific problems
• Organising events in schools
• Weather forecasting systems
• Delivery and logistics management systems