Algorithm Design and Logic Formulation

Learning Objectives

  • Define algorithms and list their essential characteristics.
  • Apply structured problem-solving techniques to computational problems.
  • Create and interpret Pseudocode for algorithm representation.
  • Utilize standard flowchart symbols to visually design algorithms.
  • Understand and apply the three fundamental control structures: Sequence, Selection, and Iteration.
  • Perform desk checking (dry running) to trace algorithm logic.
  • Evaluate algorithm efficiency using Big O Notation for both Time and Space Complexity.

A deep dive into algorithms, flowcharts, pseudocode, and structured problem-solving techniques.

Algorithm

An Algorithm is a step-by-step procedure or set of rules to solve a specific problem. It is a well-defined sequence of computational steps that transforms an input into a desired output.

Characteristics of an Algorithm

  • Input: Should receive zero or more well-defined inputs.
  • Output: Must produce at least one clear output or result.
  • Definiteness: Each step must be unambiguous, clear, and exact.
  • Finiteness: The algorithm must eventually terminate after a finite number of steps.
  • Effectiveness: Each step must be basic enough that it can be carried out, in principle, exactly and in a finite length of time.

1. Problem Solving Techniques

Before writing any code, it is crucial to understand the problem and plan a solution. A structured approach involves the software development life cycle at a micro-level.

Structured Problem-Solving Approach

  1. Define the Problem: What is the exact input? What is the expected output? What are the constraints?
  2. Analyze the Problem: Break the main problem down into smaller, manageable sub-problems (Top-Down Design).
  3. Design the Solution: Create an algorithm using tools like Flowcharts or Pseudocode. Select appropriate data structures.
  4. Implement the Solution: Translate the logic into a specific programming language (coding).
  5. Test and Verify: Run the program with various inputs, including edge cases, to ensure correctness (debugging).

2. Pseudocode

Pseudocode

Pseudocode is an informal, high-level description of an algorithm that uses the structural conventions of programming languages but is intended for human reading rather than machine reading.

Common Pseudocode Keywords

  • Input/Output: READ, GET, PRINT, DISPLAY
  • Processing: SET, COMPUTE, CALCULATE, ADD
  • Selection (Decisions): IF, THEN, ELSE, ENDIF
  • Iteration (Loops): WHILE, ENDWHILE, FOR, ENDFOR, REPEAT, UNTIL

Syntax Freedom

Pseudocode does not follow strict compiler syntax rules. The primary goal is logical clarity and conveying the flow of control to other programmers.

3. Flowcharting

Flowchart

A Flowchart is a graphical representation of an algorithm. It uses standard geometric symbols to depict the flow of logic and operations.

Common Flowchart Symbols (ISO 5807)

  • Oval / Pill (Terminator): Indicates the START or END point of the process.

  • Parallelogram (Input/Output): Represents an operation that inputs data (Read) or outputs results (Print).

  • Rectangle (Process): Represents a processing step, such as a mathematical calculation or variable assignment.

  • Diamond (Decision): Represents a decision point (a YES/NO or TRUE/FALSE question) where the flow of control branches.

  • Arrows (Flow Lines): Solid lines with arrowheads that indicate the direction of the flow of control from one symbol to the next.

  • Circle (On-Page Connector): Connects separated flow lines on the same page. A distinct off-page connector symbol shows a link to another page.

Common flowchart symbol meanings

The shapes summarize common program-flowchart conventions. The decision branches use labeled arrows so the direction and meaning remain clear without relying on color.

A terminator marks start or end, a parallelogram marks input or output, a rectangle marks a process, and a diamond marks a decision with separate yes and no exits.

Interact with the simulation below to step through a simple flowchart and see how the logic branches based on conditions.

Flowchart Execution

Step through the simple algorithm to see how logic flows from start to finish.

Start
Read Temperature (T)
Is T > 30?
Print 'Hot'
End

4. Fundamental Control Structures

Structured programming commonly expresses control flow with three fundamental structures: sequence, selection, and iteration.

The Three Control Structures

  • Sequence: The default behavior. Instructions are executed sequentially, one after another, in a linear top-to-bottom order.

  • Selection (Branching): A decision is evaluated (usually a Boolean expression). The flow branches to different paths based on whether the condition is TRUE or FALSE (e.g., IF-THEN-ELSE).

  • Iteration (Looping): A specific block of instructions is repeated continuously as long as a given condition remains TRUE (e.g., WHILE loops) or for a set number of times (e.g., FOR loops).

Sequence, selection, and iteration

Larger algorithms can be composed from these three control patterns: ordered steps, conditional choice, and repetition governed by a condition or count.

Three rows compare statements running in order, a condition selecting one of two branches, and a condition controlling repetition.

4.1 Desk Checking (Dry Running)

Desk checking (or tracing) is the manual process of walking through an algorithm step-by-step with sample data to verify its logic before writing actual code. You maintain a table of variable values as they change over time.

Trace a positive-value counter

The table shows the counter after each list item is tested. Only 4 and 7 satisfy value greater than zero, so the final count is 2.

The trace tests 4, negative 2, 0, and 7 against greater than zero, updating a counter from 0 to a final count of 2.

5. Algorithm Efficiency and Time Complexity

As programs scale to handle larger datasets, the efficiency of an algorithm becomes critical. An algorithm might run instantly for 10 items but take years to compute for 1,000,000 items. We measure this efficiency primarily using Big O Notation.

Time Complexity

Time Complexity is the computational complexity that describes the amount of time it takes to run an algorithm as a function of the length of the input.

Space Complexity

Space Complexity is the computational complexity that describes the amount of memory an algorithm takes up to run as a function of the length of the input.

5.1 Big O Notation

Big O notation gives an asymptotic upper bound on how a chosen resource, such as running time or memory, grows as input size nn increases. State which input case is analyzed—such as worst case or average case—when that distinction matters. Big O is an upper-bound notation, not a synonym for worst case.

Qualitative comparison of common growth classes

The curves compare asymptotic growth classes only. They are schematic, do not share a calibrated operation-count scale, and do not predict wall-clock time for a particular program.

A schematic graph shows constant, logarithmic, linear, n log n, quadratic, and exponential growth rising at different rates as input size increases.

Common Time-Growth Classes

  • O(1)O(1) — Constant: Growth is bounded independently of input size; actual runtime can still vary. Example: reading a known array index in the usual analysis model.

  • O(log⁡n)O(\log n) — Logarithmic: Growth is proportional to the number of times the input can be reduced by a constant factor. Binary search on a sorted array halves the remaining search range at each step.

  • O(n)O(n) — Linear: Growth is bounded in proportion to input size. A full scan that may inspect every array element is a common example.

  • O(nlog⁡n)O(n \log n) — Linearithmic: Common for comparison sorting with efficient divide-and-conquer behavior. Merge sort has O(nlog⁡n)O(n \log n) worst-case time; standard quicksort has O(nlog⁡n)O(n \log n) average-case and O(n2)O(n^2) worst-case time.

  • O(n2)O(n^2) — Quadratic: Growth is bounded by a multiple of n2n^2; it is polynomial, not exponential. Nested loops over the same input are a common source. Simple bubble sort and selection sort have quadratic worst-case comparison counts.

  • O(2n)O(2^n) — Exponential: The upper bound can double when one input element is added. Enumerating all subsets of an nn-element set produces 2n2^n subsets, so outputting them all takes at least proportional time.

Key Takeaways
  • Define an algorithm's inputs, outputs, constraints, and expected termination before coding.
  • Pseudocode and flowcharts communicate logic without tying it to a particular programming language.
  • Sequence, selection, and iteration are reusable patterns for expressing control flow.
  • Desk checking traces variable values through representative inputs to expose logic errors.
  • Big O describes an asymptotic upper bound for a selected resource and input case; it does not itself mean worst case or exact runtime.
  • State whether a complexity claim concerns time or space, and identify the input case when that distinction matters.

References