Notes on Algorithms, IPO, and Pseudocode Concepts

Shortest Path Context

  • Real-world application: shortest path problem (e.g., Google Maps).
  • Algorithms mentioned: Dijkstra's algorithm and A* algorithm.
  • Purpose: compute the shortest distance from point A to point B.

Algorithm and Pseudocode Basics

  • An algorithm is a step-by-step procedure to solve a problem.
  • Can be expressed via pseudocode or flowcharts.
  • Three fundamental constructs in algorithms: sequence, selection, repetition.
  • Pseudocode is a language-agnostic way to model an algorithm in plain language with annotations.
  • IPO chart (Input-Processing-Output) helps plan algorithms:
    • Input: what data the computer needs
    • Processing: steps to transform inputs
    • Output: results to display/store
  • Each instruction should start with a verb when describing actions.
  • Example structure for a simple sum:
    • Input: three numbers
    • Processing: sum = a + b + c or sum = sum + number
    • Output: display sum
      extsum=extsum+extnumberext{sum} = ext{sum} + ext{number}

IPO Chart Essentials

  • Purpose: analyze a problem by separating inputs, processing, and outputs.
  • Example: compute area of a rectangle
    • Input: width, length
    • Processing: area = width × length
    • Output: area

Pseudocode Keywords and Notation

  • Start and flow: START, END or equivalent (not always shown as keywords in every version).
  • Input/Output: INPUT, READ, GET; OUTPUT, PRINT, DISPLAY.
  • Processing: COMPUTE, CALCULATE, DETERMINE; SET, INIT; INCREMENT, DECREMENT.
  • Operators (arithmetic): +, −, ×, ÷, mod.
  • Assignment: uses an assignment operator (often ← or :=; sometimes a colon-equals).
  • Comparisons (relations): =, ≠,
  • Logical operators: AND, OR.
  • Conditional structures:
    • IF … THEN … END IF
    • IF … THEN … ELSE … END IF
    • IF … THEN … ELSE IF … THEN … ELSE … END IF (IF-ELSE-IF ladder)
    • CASE … OF … [case values] … END CASE (with OTHERS as default)
  • Iteration structures:
    • WHILE … DO … END WHILE
    • FOR … FROM … TO … DO … END FOR (explicit bounds)
    • DO … WHILE … (do-while)

Pseudocode Patterns: Problem-Solving Examples

  • Example 1: Tip calculation

    • Inputs: totalbill, tippercentage
    • Output: tip
    • Processing: exttip=exttotalextunderscorebillimesexttipextunderscorepercentageext{tip} = ext{total extunderscore bill} imes ext{tip extunderscore percentage}
    • Pseudocode steps: enter totalbill; enter tippercentage; compute tip; display tip

  • Example 2: Lowest and highest of two integers

    • Inputs: firstnumber, secondnumber
    • Outputs: highest, lowest
    • Processing: if firstnumber > secondnumber then first_number is higher and second is lower else second is higher and first is lower
    • Pseudocode: obtain two numbers; use IF to compare; output results

  • Example 3: Map letter to fruit using CASE

    • Input: letter
    • Output: fruit interpretation
    • Processing: match input to cases: A/a → "apple", B/b → "banana", C/c → "cranberry"; otherwise default message
    • Pseudocode: input letter; CASE on letter with cases for a/A, b/B, c/C; OTHERS → print valid letter

  • Example 4: Sum of three numbers with FOR loop

    • Inputs: number (three times)
    • Output: sum
    • Processing: initialize sum = 0; FOR i = 1 to 3 do read number; sum := sum + number; end FOR
    • Pseudocode: set sum = 0; FOR i in 1..3: input number; sum = sum + number; end FOR; print sum

  • Example 5: Sum of three numbers with WHILE loop

    • Same IPO: inputs, sum, output
    • Processing: use counter numbercounter starting at 1; while numbercounter ≤ 3 do input number; sum = sum + number; numbercounter := numbercounter + 1
    • Pseudocode: set numbercounter = 1; set sum = 0; WHILE numbercounter ≤ 3: input number; sum = sum + number; numbercounter = numbercounter + 1; END WHILE; print sum

  • Example 6: Sum with DO-WHILE loop

    • Similar setup to Example 5, but the loop body executes before the condition check.
    • Pseudocode: set numbercounter = 1; set sum = 0; DO: input number; sum = sum + number; numbercounter = numbercounter + 1; WHILE numbercounter ≤ 3; print sum

Quick Reference for Last-Minute Review

  • Always start with IPO analysis: identify inputs, processing, and outputs.
  • Use the right control structure for the task:
    • Simple choice: IF/ELSE
    • Multiple choices: CASE … OF … ELSE
    • Repetition with a known bound: FOR
    • Repetition with unknown bound until condition: WHILE
    • Do-While when you need to run once before checking: DO … WHILE
  • When expressing formulas, use …… for mathematical content in notes.
  • Keep pseudocode language-agnostic: focus on logic, not specific syntax.