Algorithm

This post is a conceptual guide to algorithms — including exam questions, key takeaways, and core concepts.

In a Nutshell

An algorithm is a finite, precisely defined sequence of steps for solving a problem. Quality is measured by correctness, runtime, space consumption, stability, and robustness.

Formal Definition

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

Analysis relies on asymptotic notation:

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

Often categorized by best-case, average-case, and worst-case scenarios, with amortized analysis added as needed.

Common design paradigms:

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

Data structures (array, linked list, heap, hash table, tree, graph) have a major impact on real-world performance.

Security consideration: Worst-case inputs can trigger Algorithmic Complexity Attacks, making input validation and resource limits essential.

Exam-Relevant Checklist

• Exact vs heuristic/approximation; deterministic vs randomized
• O/Ω/Θ; best/average/worst; amortized
• Paradigms: D&C, Greedy, DP, Backtracking
• IHK: Pre- and postconditions, termination, loop invariants
• Practice: Choose the right data structure, measure before optimizing
• Security: Harden against worst-case inputs, enforce limits
• Documentation: Problem definition, pseudocode, complexity analysis, test protocols

Core Components

1. Specification (input/output/constraints)
2. Cost model (time/space/I/O)
3. Pseudocode (sequence, selection, 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

Notes: 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 an upper bound, Ω is a lower bound, Θ is a 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.

Open-Ended Response

For IHK-style problems: define the problem clearly, write clean pseudocode, justify the complexity, and test edge cases. In production systems, cache effects, I/O patterns, and defense against worst-case inputs matter most.

Study Strategy

1. Write pseudocode and invariants for past exam problems.
2. Benchmark runtimes empirically (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/