Algorithm

This article is a concept explanation about algorithms - including exam questions, key points, and tags.

In a Nutshell

An algorithm is a finite, unambiguously described sequence of steps to solve a problem. It’s evaluated by criteria such as correctness, runtime, memory usage, stability, and robustness.

Compact Technical Description

An algorithm processes well-defined inputs and delivers deterministic or probabilistic outputs. It’s often described in pseudocode with pre- and post-conditions.

For analysis, asymptotic notations are used:

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

Often separated by best/average/worst case and supplemented with 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, therefore 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
• Vocational training: Pre/post-conditions, 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 (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) for 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 to recognize DP? Overlapping subproblems + optimal substructure.
4. How to prove termination? Variation function that strictly decreases and is bounded below.

Free Response

For vocational training tasks: 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 crucial.

Learning Strategy

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

Most Important Sources

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