Beyond Code
Algorithm Lab

The First Experiments

Testing algorithm ideas on small systems before formal complexity notation.

Lab Focus Run controlled experiments, collect evidence, and compare algorithm choices under explicit assumptions.

Why This Lab Exists

Part III introduced algorithm thinking:

  • define guarantees
  • decompose work
  • use recursion when structure fits
  • reason about behavior under growth

Now we run controlled experiments.

The goal is not to chase micro-optimizations. The goal is to build engineering intuition by observing how different algorithm choices behave on the same task.

Lab Objectives

By the end of this lab, you should be able to:

  • compare two algorithms for the same requirement
  • collect simple evidence (operation counts, not just wall-clock time)
  • explain when an approach is acceptable and when it breaks down
  • preserve correctness contracts while changing strategy

Experiment Theme

Use one task, multiple strategies:

“Find a target value in a sorted sequence.”

Why this task:

  • easy correctness criteria
  • easy to vary input size
  • clear contrast between algorithm behaviors

Strategies:

  • linear scan
  • binary search

We will track an explicit step counter to observe behavior directly.

Nex Implementation

Suggested file names:

  • algorithm_lab_1.nex
  • algorithm_lab_1_main.nex

Result Type

class Search_Result
create
  make(found: Boolean, index: Integer, steps: Integer) do
    this.found := found
    this.index := index
    this.steps := steps
  end
feature
  found: Boolean
  index: Integer
  steps: Integer
invariant
  index_valid: index >= -1
  steps_non_negative: steps >= 0
  found_matches_index: found = (index >= 0)
end

Linear Search With Step Counter

class Linear_Search_Algo
feature
  find(items: Array[Integer], target: Integer): Search_Result
  do
    let idx: Integer := -1
    let steps: Integer := 0
    from let i := 0 
    until i >= items.length or idx >= 0 do
      steps := steps + 1
      if items.get(i) = target then
        idx := i
      end
      i := i + 1
    end
    result := create Search_Result.make(idx >= 0, idx, steps)
  ensure
    hit_is_correct: not result.found 
                    or items.get(result.index) = target
    bounded_steps: result.steps <= items.length
    miss_checks_every_item: result.found 
                            or result.steps = items.length
  end
end

Binary Search With Step Counter

class Binary_Search_Algo
feature
  is_sorted(items: Array[Integer]): Boolean do
    result := true
    from let i := 1 until i >= items.length do
      if items.get(i - 1) > items.get(i) then
        result := false
      end
      i := i + 1
    end
  end

  -- How many times n can be halved before nothing is left:
  -- the most probes a binary search over n items needs.
  max_probes(n: Integer): Integer do
    result := 0
    from let k := n until k = 0 do
      result := result + 1
      k := k / 2
    end
  end

  find(items: Array[Integer], target: Integer): Search_Result
  require
    sorted_input: is_sorted(items)
  do
    let lo: Integer := 0
    let hi: Integer := items.length - 1
    let idx: Integer := -1
    let steps: Integer := 0
    from until lo > hi or idx >= 0 do
      let mid: Integer := (lo + hi) / 2
      steps := steps + 1
      if items.get(mid) = target then
        idx := mid
      elseif items.get(mid) < target then
        lo := mid + 1
      else
        hi := mid - 1
      end
    end
    result := create Search_Result.make(idx >= 0, idx, steps)
  ensure
    hit_is_correct: not result.found 
                    or items.get(result.index) = target
    logarithmic_steps: 
      result.steps <= max_probes(items.length)
  end
end

Driver: Compare Behaviors

class App
feature
  run() do
    let lin: Linear_Search_Algo 
     := create Linear_Search_Algo
    let bin: Binary_Search_Algo 
     := create Binary_Search_Algo
    let items: Array[Integer] 
     := [3, 7, 10, 14, 19, 21, 25, 30]
    let l_hit: Search_Result := lin.find(items, 30)
    let b_hit: Search_Result := bin.find(items, 30)
    let l_miss: Search_Result := lin.find(items, 11)
    let b_miss: Search_Result := bin.find(items, 11)
    print("Linear hit steps: " + l_hit.steps)
    print("Binary hit steps: " + b_hit.steps)
    print("Linear miss steps: " + l_miss.steps)
    print("Binary miss steps: " + b_miss.steps)
  end
end

-- Run the driver
let app := create App
app.run

Expected pattern:

  • both algorithms are correct
  • binary search usually uses fewer steps on sorted inputs
  • binary search depends on stronger preconditions (sorted_input)

Lab Tasks

Task A — Correctness Check

Run both strategies with:

  • first element target
  • middle element target
  • last element target
  • absent target

Record:

  • found or not found
  • returned index
  • steps

Task B — Constraint Violation

Call binary search with unsorted inputs and observe contract behavior.

Question:

  • what failure signal do you get?
  • how is this better than silent wrong results?

Task C — Extension

Add one more strategy for comparison:

  • jump search, or
  • interpolation-inspired search (if values are uniformly distributed)

Keep the same Search_Result format so results remain comparable.

Reflection Prompts

Use evidence from your run logs:

  1. Which strategy has stricter input assumptions?
  2. Which strategy is easier to reason about for correctness?
  3. At what scale would you stop using linear search for this task?
  4. Which contract prevented the most dangerous misuse?

Deliverables

  • runnable Nex code for at least two strategies
  • output log showing hit and miss comparisons
  • short write-up of strategy tradeoffs
  • one paragraph on how contracts influenced your design