Data Structures & Algorithms
1/69
3 topics
01·Fundamentals

Algorithms & Pseudocode

Complexity
Core Concepts
Theory
  • algorithm = a finite, deterministic procedure mapping inputs to correct outputs
  • three required properties: correctness, finiteness (always terminates), determinism (same input → same output)
  • pseudocode is language-agnostic — expresses logic without syntax constraints
  • ← for assignment, indentation for blocks, and for loops, while loops
  • problem defines what to compute; algorithm defines how to compute it
Pseudocode
GCD(a, b, gcd)
  input:  a, b ∈ ℕ
  output: gcd = greatest common divisor of a and b

  while a ≠ b
    if a > b
      a ← (a - b)
    else
      b ← (b - a)
  gcd ← a

// Pseudocode conventions:
// ← instead of = for assignment
// Blocks by indentation (no semicolons, no braces)
// null = no value (also for numbers)
// a.length = length of array a
// Data types: ℕ, ℤ, ℚ, ℝ
// Comparisons: <, >, ≤, ≥, =, ≠
1 / 3
Search unsortedΩ(n)
Search sortedΩ(log n)
SortingΩ(n log n)
BST worstΘ(n)
Build heapΘ(n)
Balanced treeO(log n)
Dijkstrano neg. weights
KMPΘ(n + m)
Max-Flow= Min-Cut
Union-FindO(α(n)) ≈ O(1)