Detailed notes – 1- Chapter 4 : Introduction to Problem Solving

Introduction to Problem Solving and Programming

• Computers have become ubiquitous, aiding in faster and more accurate task execution.
• Tasks like train ticket booking, once complex, have been simplified due to computerization.
• Computerization involves using computers to automate routine human tasks efficiently.
• Problem-solving is a fundamental skill in computer science, crucial for developing solutions using computers.
• Computers require precise step-by-step instructions to solve problems effectively.
• Problem solving involves identifying a problem, devising an algorithm, and implementing it as a program.

Steps for Problem Solving:

1. Analysing the Problem:

   • Understand the problem statement clearly.
   • Identify the principal components of the problem.
   • Determine the core functionalities the solution should have.
   • Define the inputs the program should accept and the outputs it should produce.

2. Developing an Algorithm:

   • Devise a solution plan before writing the program.
   • Represent the solution in natural language as an algorithm.
   • Refine the algorithm until it captures all aspects of the desired solution.
   • Select the most suitable algorithm for the problem.

3. Coding:

   • Convert the algorithm into a format understandable by the computer.
   • Write the program using a high-level programming language.
   • Document the coding procedures and the solution for future reference.

4. Testing and Debugging:

   • Test the program on various parameters to ensure it meets user requirements.
   • Check if the program responds within the expected time and generates correct output for all possible inputs.
   • Debug any syntactical or logical errors found during testing.
   • Follow standardized testing methods like unit testing, integration testing, system testing, and acceptance testing.
   • Rectify errors or defects found during testing and retest the program until all issues are resolved.

5. Maintenance:

   • Address user queries and resolve any problems encountered during the use of the software application.
   • Serve requests for addition or modification of features as needed.
   • Ensure the ongoing functioning and performance of the solution through regular maintenance and updates.

An algorithm is a finite sequence of steps required to achieve a specific task or solve a problem. It provides a roadmap for completing a task effectively and efficiently. Let’s break down the concept and importance of algorithms:

Example: Finding the Greatest Common Divisor (GCD)

1. Identify Divisors:
   • Find divisors of both numbers: 45 and 54.
     • Divisors of 45: 1, 3, 5, 9, 15, 45
     • Divisors of 54: 1, 2, 3, 6, 9, 18, 27, 54
2. Find Common Number:
   • Determine the largest common number: 9
3. Conclusion:
   • GCD of 45 and 54 is 9.

Importance of Algorithms:

1. Guidance for Programming:
   • Algorithms serve as a roadmap for programmers to clearly visualize the instructions needed for writing code.
   • They help ensure that the program performs as expected.
2. Foundation of Problem-Solving:
   • Algorithms are fundamental to problem-solving, providing a systematic approach to tackle complex tasks.
   • From searching the internet to playing games, algorithms are the basis of various activities.
3. Characteristics of Good Algorithms:
   • Precision: Clearly defined steps.
   • Uniqueness: Each step’s results depend only on preceding steps and input.
   • Finiteness: The algorithm always stops after a finite number of steps.
   • Input/Output: Receives input and produces output.

Writing an Algorithm:

1. Identify Inputs, Processing, and Outputs:
   • Input: Information provided to the algorithm.
   • Processing: Steps performed to manipulate the input.
   • Output: Desired result produced by the algorithm.

Representation of Algorithms

Software designers and programmers use algorithmic thinking to analyze problems and outline logical steps for reaching a solution. These steps are then represented using two common methods: flowcharts and pseudocode.

 Flowchart

• Visual Representation: A flowchart is a diagram comprising boxes, diamonds, and other shapes connected by arrows.
• Logic Demonstration: Each shape represents a step in the solution process, and arrows show the order or link between the steps.
• Standard Symbols: There are standardized symbols for drawing flowcharts.

 Pseudocode

• Non-Formal Language: Pseudocode is a non-formal language aiding programmers in writing algorithms.
• Detailed Instructions: It provides a detailed description of instructions to be followed by the computer in a particular order.
• Human Readability: Intended for human reading and understanding, it cannot be directly executed by the computer.
• Common Keywords: Some frequently used keywords in pseudocode include INPUT, COMPUTE, PRINT, IF/ELSE, WHILE, TRUE/FALSE, etc.

Benefits of Pseudocode

• Clarity and Readability: Helps represent the basic functionality of a program before writing code in a high-level language.
• Error Prevention: Safeguards against missing important steps in the program implementation.
• Accessibility: Makes it easier for non-programmers to review and understand the program’s logic and intended output.

Flow of Control

The flow of control illustrates how events progress through an algorithm, represented in a flowchart. Events can flow sequentially, branch based on decisions, or repeat some parts for a finite number of times.

Sequence

• Sequential Execution: In a sequence, statements are executed one after another, following the natural order of the algorithm.

Selection

• Decision Making: Selection involves making decisions based on certain conditions.
• Example: Determining a route from home to school based on traffic conditions.
• Conditionals: Conditions are used to check possibilities and execute different actions based on the outcome.
  • Examples include checking eligibility for voting or placing students in different groups based on age and preferences.
• Representation in Algorithms:
  • Using If statements:

Including an else statement for handling alternative conditions

• In programming languages, ‘otherwise’ is represented using the else keyword within an if-else block.

Verifying Algorithms

Imagine the consequences if banking software malfunctioned, crediting only half the amount in online money transfers or debiting accounts erroneously. Faulty software can disrupt systems, emphasizing the critical need for accurate programming, especially in fields like medicine and space technology. Verifying algorithms is crucial to ensure their correctness.

Verification Methods:

1. Manual Verification: Just as we manually verify mathematical formulas, algorithms can be tested with different inputs to ensure correct outputs.
   • For instance, verifying the formula for the sum of first N natural numbers by calculating sums for small N values.
2. Dry Run: Simulating the algorithm with different inputs to validate its correctness.
   • Identifies incorrect steps or missing details in the algorithm.

Example:

• Algorithm to calculate total travel time from A to C via B, given travel times from A to B (T1) and B to C (T2).
• Initial algorithm resulted in incorrect sums when minutes exceeded 60.
• Modified algorithm includes a conditional statement to handle minute overflow and adjust hours accordingly.

Importance of Verification:

• Software development without algorithm verification risks faulty outcomes.
• Verifying algorithms is essential as it minimizes the effort required to detect and rectify errors in later stages of development.

Comparison of Algorithms

When solving a problem with a computer, there can be multiple approaches, leading to different algorithms. Comparing these algorithms helps determine which is the most efficient for a given task. Let’s explore this through the example of determining whether a number is prime or not.

Problem:

Given a number, determine if it is prime.

Algorithms:

1. Divide by All Numbers: Test divisibility by all numbers up to the number itself.
2. Divide by Half: Test divisibility up to half of the number.
3. Divide by Square Root: Test divisibility up to the square root of the number.
4. Use Prime Number List: Divide by pre-determined prime numbers less than the given number.