Algorithms (Copy)

Chapter 9.2: Algorithms – Detailed Summary

Key Terms

• Algorithm: A step-by-step ordered set of instructions to complete a specific task.
• Structured English: A way of expressing an algorithm using a restricted subset of the English language with logical and mathematical operators.
• Flowchart: A diagrammatic representation of an algorithm using standard symbols.
• Pseudocode: A structured, human-readable method to represent an algorithm using programming-like syntax but without adhering to a specific programming language.
• Stepwise Refinement: The process of breaking down a large problem into smaller, more manageable subproblems.

9.2.1 Writing Algorithms that Provide Solutions to Problems

• Three Common Methods to Represent Algorithms:
  1. Structured English: Uses simple and clear English-like statements to describe the steps of an algorithm.
  2. Flowchart: Uses symbols and connecting arrows to show the flow of execution.
  3. Pseudocode: Represents the logic of the solution in a structured manner that closely resembles programming code.
• Example Algorithm (Calculating the Average of Input Values)
  • Structured English Representation:
    1. Ask for the number of values to average.
    2. Loop the specified number of times:
       • Enter a value.
       • Add the value to the total.
    3. Compute the average.
    4. Output the average.
  • Pseudocode Representation:

    Total ← 0
    PRINT "Enter the number of values to average"
    INPUT Number
    FOR Counter ← 1 TO Number
        PRINT "Enter value"
        INPUT Value
        Total ← Total + Value
    NEXT Counter
    Average ← Total / Number
    PRINT "The average of ", Number, " values is ", Average
    

  • Flowchart Representation: Uses standard flowchart symbols to show the sequence of operations.

9.2.2 Writing Simple Algorithms Using Pseudocode

• Rules for Writing Pseudocode:
  • Each line represents a single step.
  • Use meaningful identifier names.
  • Follow indentation conventions for clarity.
  • Statements should be case insensitive.
  • Input and output operations should be clearly specified.
• Identifier Table:
  • Helps in tracking variables and their meanings.
  • Example:
    

    Identifier Name	Description
    Total	Stores the running sum
    Number	Number of values to average
    Value	Individual input values
    Average	Computed average

9.2.3 Using Flowcharts to Represent Algorithms

• Flowchart Symbols:
  • Oval (Start/End): Represents the start or end of an algorithm.
  • Parallelogram (Input/Output): Represents user input or system output.
  • Rectangle (Process): Represents calculations or actions.
  • Diamond (Decision): Represents branching conditions.
• Example Flowchart for Computing the Average:
  • Start → Input Number of Values → Loop through Values → Compute Total → Compute Average → Output Result → End

9.2.4 Writing Pseudocode from a Flowchart

• Example Algorithm: Checking an Exam Grade:
  • Flowchart Representation:
    • Input student’s exam mark.
    • If mark < 40 → Grade = “Fail”.
    • Else if mark < 60 → Grade = “Pass”.
    • Else if mark < 80 → Grade = “Merit”.
    • Otherwise → Grade = “Distinction”.
  • Pseudocode Representation:

    OUTPUT "Enter your exam mark"
    INPUT Mark
    IF Mark < 40 THEN
        Grade ← "Fail"
    ELSE IF Mark < 60 THEN
        Grade ← "Pass"
    ELSE IF Mark < 80 THEN
        Grade ← "Merit"
    ELSE
        Grade ← "Distinction"
    ENDIF
    OUTPUT "Your grade is ", Grade
    

• Identifier Table for Exam Grade Algorithm:
  

  Identifier Name	Description
  Mark	Student’s exam mark
  Grade	Final assigned grade

9.2.5 Stepwise Refinement

• Concept:
  • Complex problems should be broken down into smaller, manageable steps.
  • Each step should be simple enough to be translated directly into programming code.
  • Helps in debugging and structuring code logically.
• Example: Converting Marathon Time to Seconds
  • High-Level Steps:
    1. Input marathon time in hours, minutes, and seconds.
    2. Convert total time to seconds.
    3. Output the result.
  • Stepwise Refinement Breakdown:
    • Step 1: Ask user to enter the time in hours, minutes, and seconds.
    • Step 2: Convert each component into seconds.
    • Step 3: Display the result.
  • Pseudocode Representation:

    OUTPUT "Enter hours"
    INPUT MarathonHours
    OUTPUT "Enter minutes"
    INPUT MarathonMinutes
    OUTPUT "Enter seconds"
    INPUT MarathonSeconds
    TotalMarathonTimeSeconds ← (MarathonHours * 3600) + (MarathonMinutes * 60) + MarathonSeconds
    OUTPUT "Time for marathon in seconds: ", TotalMarathonTimeSeconds
    

9.2.6 Applying Algorithms in Problem-Solving

• Example Activity:
  • Problem: Draw a regular polygon.
  • Solution:
    1. Identify similar repetitive steps.
    2. Break the problem into small, reusable segments.
    3. Write structured English, pseudocode, or flowchart representation.
    4. Test the algorithm by manually following the steps.
• Algorithm Optimization:
  • Efficiency Considerations:
    • Reduce unnecessary steps.
    • Use efficient loops and conditions.
    • Identify and remove redundant calculations.

End of Chapter Questions

• Examples:
  1. Define structured English, flowcharts, and pseudocode.
  2. Explain abstraction, decomposition, and pattern recognition.
  3. Demonstrate stepwise refinement with an example.
  4. Evaluate expressions using pseudocode.
  5. Identify different control structures in pseudocode.

Conclusion

• Algorithms are the foundation of computational thinking:
  • They provide structured problem-solving techniques.
  • They can be represented in multiple ways (structured English, flowcharts, pseudocode).
  • Stepwise refinement helps simplify complex problems.
  • Writing efficient algorithms improves program performance.