Algorithm

This post is a concept guide to algorithms – covering exam questions, key takeaways, and reference points.

In a Nutshell

An algorithm is a finite, precisely defined sequence of steps that solves a problem. We evaluate algorithms by correctness, runtime, memory usage, stability, and robustness.

Concise Technical Overview

An algorithm processes well-defined inputs and produces deterministic or probabilistic outputs. It’s usually described in pseudocode with preconditions and postconditions.

Analysis relies on asymptotic notation:

• O (upper bound)
• Ω (lower bound)
• Θ (tight bound)

Often separated by best-case, average-case, and worst-case scenarios, plus amortized analysis.

Common design paradigms:

• Divide and Conquer
• Greedy
• Dynamic Programming
• Backtracking
• Randomization

Data structures (arrays, linked lists, heaps, hash tables, trees, graphs) heavily influence real-world performance.

Security angle: worst-case inputs can trigger algorithmic complexity attacks, so input validation and resource limits matter.

Key Exam Points

• Exact vs heuristic/approximate; deterministic vs randomized
• O/Ω/Θ; best/average/worst; amortized
• Paradigms: D&C, Greedy, DP, Backtracking
• IHK standards: preconditions/postconditions, termination, loop invariants
• Practice: choose the right data structure, measure before optimizing
• Security: harden against worst-case, set limits
• Documentation: problem definition, pseudocode, complexity, test reports

Core Components

1. Specification (input/output/constraints)
2. Cost model (time/space/I/O)
3. Pseudocode (sequence, branching, loops)
4. Data structure selection
5. Correctness (invariants/induction/termination)
6. Complexity analysis
7. Design approach
8. Implementation details (recursion/iteration)
9. Robustness and security
10. Testing (edge cases, fuzzing, regression)

Practical Example: Insertion Sort (Pseudocode)

function insertionSort(a)
  for i from 1 to length(a)-1
    key <- a[i]
    j <- i-1
    while j >= 0 and a[j] > key
      a[j+1] <- a[j]
      j <- j-1
    end
    a[j+1] <- key
  end
  return a

Explanation: Stable, in-place, worst-case O(n^2), best-case O(n) on nearly sorted data.

Typical Exam Questions (with Brief Answers)

1. O vs Ω vs Θ? O is the upper bound, Ω is the lower bound, Θ is the tight bound.
2. When is Greedy correct? When optimal substructure and the greedy-choice property both hold.
3. How do you spot Dynamic Programming? Overlapping subproblems plus optimal substructure.
4. How do you prove termination? Define a variant function that strictly decreases and is bounded below.

Free Response

For IHK exams: define the problem clearly, write clean pseudocode, justify the complexity, and test edge cases. In production systems, cache effects, I/O behavior, and hardening against worst-case inputs are critical.

Learning Strategy

1. Write pseudocode and invariants for past exam problems.
2. Measure runtimes (linear vs binary search, different sorts).
3. Model a DP example (knapsack) as a table.
4. Always test boundary conditions and exit criteria.

Key References

1. https://en.wikipedia.org/wiki/Algorithm
2. https://cp-algorithms.com/