Algorithm Design And Problem Solving (Copy)

7.1 Program Development Life Cycle (PDLC)

• Definition:
  The sequence of steps followed when developing a program to solve a problem.
• Stages Covered (in syllabus): Analysis → Design → Coding → Testing
• Stage 1: Analysis
  • Purpose: To understand the problem and what is required.
  • Tasks in Analysis:
    • Abstraction: Removing unnecessary details, focusing only on essential features of the problem.
    • Decomposition: Breaking the problem down into smaller, more manageable parts.
    • Identification of problem and requirements:
      • Inputs required (what data will be entered into the system)
      • Processes required (what actions must be performed on the data)
      • Outputs expected (what results should be produced)
      • Storage needs (what data must be stored for later use)
  • Example:
    Problem: Create a program to calculate the average score of students in a class.
    • Inputs: Student scores
    • Processes: Sum scores, count students, divide sum by count
    • Outputs: Average score
    • Storage: Scores in an array/list
• Stage 2: Design
  • Purpose: To plan the solution to the problem before writing code.
  • Tasks in Design:
    • Decomposition: Further breaking down components of the problem.
    • Structure diagrams:
      • Hierarchical diagram showing the breakdown of the system into sub-systems.
    • Flowcharts:
      • Graphical representation of algorithm flow using standard symbols:
        • Oval: Start/End
        • Parallelogram: Input/Output
        • Rectangle: Process
        • Diamond: Decision
    • Pseudocode:
      • Structured, English-like description of steps the program will take.
  • Example Pseudocode:

    total ← 0  
    count ← 0  
    FOR each score in list  
        total ← total + score  
        count ← count + 1  
    average ← total / count  
    OUTPUT average  
    

• Stage 3: Coding
  • Purpose: Translating the design into program code using a specific programming language.
  • Tasks in Coding:
    • Writing code
    • Iterative testing during development to catch errors early
  • Example: Writing the above pseudocode in Python.
• Stage 4: Testing
  • Purpose: To ensure the program works as intended and meets requirements.
  • Tasks in Testing:
    • Using test data to check correctness
    • Checking for edge cases, invalid inputs, and performance

7.2 System Structure and Problem Decomposition

• Understanding Sub-Systems:
  • Every computer system is made up of sub-systems (modules).
  • Sub-systems can be further broken down into smaller sub-systems.
  • Helps in managing complexity, testing, and reusing components.
• Decomposition Process:
  • Breaking a complex problem into smaller, simpler parts that are easier to solve.
• Example:
  ATM software:
  • Main System: ATM Operations
    • Sub-system 1: Authentication
    • Sub-system 2: Withdrawal
    • Sub-system 3: Deposit
    • Sub-system 4: Balance Inquiry

7.3 Methods to Design and Construct Solutions

• Structure diagrams (hierarchical)
• Flowcharts (graphical step-by-step representation)
• Pseudocode (structured English statements)
• Program code (actual implementation)
• Example Flowchart Symbols:
  • Start/End → Oval
  • Process → Rectangle
  • Input/Output → Parallelogram
  • Decision → Diamond

7.4 Understanding and Explaining Algorithms

• Purpose of an algorithm: What problem it solves and why it exists.
• Describing processes in an algorithm: Identify each step’s role, the inputs it requires, the processes it performs, and the outputs it generates.
• Example:
  Algorithm to find the largest number in a list:
  • Input: List of numbers
  • Process: Compare each number to the current maximum
  • Output: Largest number

7.5 Standard Methods of Solution

• Linear Search:
  • Checks each element in a list one by one until the desired element is found or the list ends.
  • Suitable for small/unsorted lists.
• Bubble Sort:
  • Repeatedly compares adjacent elements and swaps them if they are in the wrong order.
  • Process repeats until no swaps are needed.
• Totalling:
  • Adding up values (e.g., sum of sales in a month).
• Counting:
  • Counting the number of occurrences of a value or event.
• Finding maximum, minimum, and average values:
  • Iterating through data to determine required statistics.

7.6 Validation and Verification

• Validation: Checks if data entered meets certain rules before processing.
  • Types:
    • Range check: Data must fall between defined limits.
    • Length check: Data must have correct number of characters.
    • Type check: Data must be of correct data type.
    • Presence check: Field must not be left empty.
    • Format check: Data must follow a specific pattern (e.g., DD/MM/YYYY).
    • Check digit: Extra digit to verify data entry accuracy (often in account numbers).
  • Purpose: Prevent incorrect data from being entered into the system.
• Verification: Ensures data entered matches the source.
  • Types:
    • Visual check: Manually comparing entered data with source document.
    • Double entry check: Entering the data twice and comparing.
  • Purpose: Detect errors during data entry.

7.7 Test Data

• Types:
  • Normal data: Expected, valid inputs.
  • Abnormal data: Invalid inputs to test error handling.
  • Extreme data: Values at the limits of acceptable range.
  • Boundary data: Values at the boundary between valid and invalid data.
• Example for age field (valid range 18–65):
  • Normal: 30
  • Abnormal: -5, 100
  • Extreme: 18, 65
  • Boundary: 17, 66

7.8 Trace Tables and Dry Runs

• Trace Table:
  A table used to record the values of variables step-by-step during a dry run of an algorithm.
• Purpose:
  To check logic and identify errors without running code.
• Example:

  i   value   total
  1     5       5
  2     3       8
  3     7      15
  

7.9 Identifying and Correcting Errors

• Types of Errors:
  • Syntax errors: Violations of programming language rules.
  • Logic errors: Program runs but produces wrong output.
  • Runtime errors: Errors that occur during execution (e.g., division by zero).
• Correction Methods:
  • Reviewing algorithm logic
  • Step-by-step debugging
  • Adding print/debug statements

7.10 Writing and Amending Algorithms

• Accepted formats:
  • Pseudocode: Structured, precise, follows defined syntax.
  • Program code: Written in a chosen programming language.
  • Flowcharts: Graphical representation of algorithm steps.
• Precision Requirement:
  Expressions like x > y are valid; natural language descriptions like “x is greater than y” are not.