Module 2 – Algorithms and Features of Algorithms

Algorithms and Fundamental Definitions

  • Algorithm

    • Step-by-step, finite procedure that transforms given input(s) into the desired output(s).

    • Language-independent; the same algorithm can be implemented in any programming language.

  • Canonical operations on data structures

    • Search • Sorting • Insert • Update • Delete.

Reasons for Studying Algorithms

  • Understand core ideas of a problem and devise sound solution strategies.

  • Improve individual problem-solving ability and algorithmic thinking.

  • Compare competing techniques quantitatively (time, space, I/O).

  • Measure behaviour across best, average and worst cases.

  • Identify resource/​cycle requirements to turn programming from an art into a science.

  • Clarify requirements/goals for designers and yield higher-quality software.

Characteristics of a Good Algorithm

  • Mandatory traits

    • Unambiguous: every step has one clear meaning.

    • Input / Output: 0\text{ or more inputs} \;\to\; 1\text{ or more well-defined outputs} that match the goal.

    • Finiteness: terminates after a finite number of steps.

    • Feasibility: executable with available resources.

    • Independence: described without relying on any specific code base.

  • Desirable traits

    • Integrity (correctness), Clarity, Simplicity, Efficiency, Modularity, Generality, Robustness, Maintainability, Functionality, User-friendliness, Extensibility, Documentation.

Algorithm Development vs. SDLC

  • Software Development Life-Cycle phases
    • Requirement Gathering • Analysis • Design • Coding • Testing • Deployment • Maintenance.

  • Algorithm Development mirrors SDLC

    1. Problem Definition

    2. Problem Analysis

    3. Algorithm Design (often via pseudocode)

    4. Flow-charting (visual for non-technical stakeholders)

    5. Implementation (coding)

    6. Testing (incl. edge cases)

    7. Documentation

Top-Down vs. Bottom-Up Design Approaches

  • Top-Down (Decomposition)

    • Break big problem ⇒ smaller sub-problems ⇒ solve independently.

    • Typical in structured languages (C, COBOL, FORTRAN).

    • Pros: conceptual clarity. Cons: code redundancy, weak inter-module interaction.

  • Bottom-Up (Composition)

    • Build solutions to small units first, then integrate.

    • Favoured by OOP (C++, Java, Python). Emphasises encapsulation, module communication, reuse; heavily used in unit testing.

Algorithm Design Techniques (Paradigms)

  • Brute Force / Exhaustive Search

    • Test every candidate solution; simple but exponential in time \Theta(k^n) on many problems.

    • Examples: linear search, selection sort, naive string match, exhaustive TSP, knapsack.

  • Divide & Conquer (Top-Down)

    • Steps: Divide → Conquer (recursively) → Combine.

    • Algorithms: binary search, merge sort, quick sort, Strassen matrix multiplication.

  • Greedy Method

    • Make locally optimal choice hoping for overall optimum.

    • Often yields near-optimal or optimal solutions to optimisation problems.

    • Examples: Prim, Kruskal, Dijkstra, Huffman coding.

  • Dynamic Programming (DP)

    • Like D&C but stores sub-problem results to avoid recomputation.

    • Key principle: optimal sub-structure + overlapping sub-problems.

    • Examples: Fibonacci (memoised), matrix-chain multiplication, assembly-line scheduling.

  • Branch & Bound

    • Searches full solution space while pruning sub-spaces using bounds.

    • Used in combinatorial optimisation, e.g.
      TSP, job sequencing.

  • Randomised Algorithms

    • Incorporate randomness to influence behaviour.

    • Las Vegas: always correct; running time random (e.g., randomised quick sort).

    • Monte Carlo: fixed time; answer may be wrong with small probability (e.g., Karger min-cut).

  • Backtracking

    • Depth-first enumeration of candidates; abandon partial solutions that cannot lead to success.

    • Examples: N-Queens, Sudoku, maze navigation.

  • Linear Programming

    • Optimise linear objective subject to linear constraints.

    • Solutions via Simplex, Interior-point, etc.

Writing an Algorithm – General Conventions

  • Ideation independent of code; afterwards translate to chosen language.

  • Typical pseudo-step keywords: START/STOP, READ, PRINT, IF/ELSE, REPEAT, etc.

  • Variable naming: descriptive, starts with letter, CamelCase recommended.

  • Assign using \leftarrow or :=\;.

  • Arithmetic: +,-,*,/,^,\text{mod},\text{div}.

  • Relational: <,>,\le,\ge,=,\neq.

  • Selection structures: single-, double-, nested IF, GOTO, SELECT-CASE.

  • Loop structures: WHILE, DO WHILE, FOR, REPEAT UNTIL, FOR-EACH.

Expressing Algorithms

  • Structured English (narrative)

  • Pseudocode (most common; mixture of plain English & code-like constructs)

  • Flowcharts (graphical; rectangles ⬜ = process, diamonds ◇ = decision, arrows = flow)

Algorithm vs. Pseudocode

  • Algorithm: abstract, language-independent logical procedure; guarantees task completion.

  • Pseudocode: one notation used to document an algorithm in quasi-English code; flexible syntax, emphasises readability & documentation.

Examples Showcasing Basic Control Structures

Sequential

  • Sum of two numbers: c = a + b (display c).

  • Weight of hollow sphere – physics example
    R0 = \frac{d}{2},\; R1 = \frac{d}{2} - t
    V = \frac{4}{3}\pi (R1^3 - R0^3)
    W = \rho V

  • Temperature conversion: C = \frac{5}{9}(F-32).

  • Energy to heat water: Q = M\,(Tf - Ti)\,4184.

  • Triangle semi-perimeter: P = \frac{a+b+c}{2}.

Selection / Branching

  • Determine larger of two numbers using IF … ELSE.

  • Sign classification (negative/zero/positive) via nested IF.

  • Piecewise mathematical function
    Y=\begin{cases}4x^2 - x^2 + 1,&x\ge 0\x^2 + x -1,&x<0\end{cases}

Looping

  • Sum & average of N numbers: FOR loop accumulating \text{Sum}.

  • Sum & average of first N integers: FOR with counter variable.

  • Inches → centimetres conversion table (increment inches by 0.5).

  • Factorial via loop
    n! = \begin{cases}1, & n \le 0\1\times2\times\dots\times n, & n>0\end{cases}

Ethical / Practical Implications & Real-World Relevance

  • Selecting an efficient algorithm lowers computation cost, energy usage and carbon footprint.

  • Correctness and robustness critical for safety-critical systems (medical, aviation, finance).

  • Documentation, clarity and maintainability ensure future teams can audit, extend and ethically reuse algorithms.

  • Generality & extensibility encourage open, collaborative software ecosystems.