Algorithm

This post is a concept explanation on the topic of Algorithm – including exam questions, key points, and tags.

In a Nutshell

An algorithm is a finite, unambiguously described sequence of steps for solving a problem. It is evaluated based on correctness, runtime, memory usage, stability, and robustness.

Compact Technical Description

An algorithm processes well-defined inputs and delivers deterministic or probabilistic outputs. It is often described in pseudocode with preconditions and postconditions.

Asymptotic notations are used for analysis:

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

Often separated by best/average/worst case and supplemented by amortized analysis.

Typical design paradigms:

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

Data structures (array, list, heap, hash table, tree, graph) strongly determine real costs.

Security aspect: Worst-case inputs can trigger algorithmic complexity attacks, so input validation and resource limits are relevant.

Exam-Relevant Key Points

• Exact vs heuristic/approximate; deterministic vs randomized
• O/Ω/Θ; best/average/worst; amortized
• Paradigms: D&C, greedy, DP, backtracking
• IHK: preconditions/postconditions, termination, loop invariants
• Practice: choose appropriate data structure, measure first then optimize
• Security: worst-case hardening, limits
• Documentation: problem definition, pseudocode, complexity, test protocols

Core Components

1. Specification (input/output/constraints)
2. Cost model (time/memory/I/O)
3. Pseudocode (sequence, selection, loop)
4. Data structure selection
5. Correctness (invariants/induction/termination)
6. Complexity analysis
7. Design approach
8. Implementation details (recursion/iteration)
9. Robustness/security
10. Tests (boundary values, fuzzing, regression)

Practical Example: Insertion Sort (Pseudocode)

funktion insertionSort(a)
  fuer i von 1 bis laenge(a)-1
    key <- a[i]
    j <- i-1
    solange j >= 0 und a[j] > key
      a[j+1] <- a[j]
      j <- j-1
    ende
    a[j+1] <- key
  ende
  gib a zurueck

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

Typical Exam Questions (with Brief Answers)

1. O vs Ω vs Θ? O upper bound, Ω lower bound, Θ tight bound.
2. When is greedy correct? When optimal substructure and greedy-choice property hold.
3. How do you recognize DP? Overlapping subproblems + optimal substructure.
4. How do you prove termination? Variant function that strictly decreases and is bounded below.

Free Response

For IHK tasks, what counts: clearly define the problem, write clean pseudocode, justify complexity, and test edge cases. In real systems, cache/I/O effects and robustness against worst-case inputs are decisive.

Learning Strategy

1. Write pseudocode + invariant for past exam questions.
2. Measure runtimes (linear vs binary, various sorts).
3. Model a DP example (knapsack) as a table.
4. Always test edge cases and termination conditions.

Most Important Sources

1. https://de.wikipedia.org/wiki/Algorithmus
2. https://cp-algorithms.com/