Beyond Code
Algorithm Lab

The First Experiments

Subtitle

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
end

Linear Search With Step Counter

class Linear_Search_Algo
feature
  find(a1, a2, a3, a4, a5, a6, a7, a8, 
       target: Integer): Search_Result
    do
      let found: Boolean := false
      let idx: Integer := -1
      let steps: Integer := 1
      if a1 = target then
        found := true
        idx := 0
      elseif a2 = target then
        steps := 2
        found := true
        idx := 1
      elseif a3 = target then
        steps := 3
        found := true
        idx := 2
      elseif a4 = target then
        steps := 4
        found := true
        idx := 3
      elseif a5 = target then
        steps := 5
        found := true
        idx := 4
      elseif a6 = target then
        steps := 6
        found := true
        idx := 5
      elseif a7 = target then
        steps := 7
        found := true
        idx := 6
      elseif a8 = target then
        steps := 8
        found := true
        idx := 7
      else
        steps := 9
      end

      result := create Search_Result.make(found, idx, steps)
    ensure
      steps_recorded: result.steps >= 1
      valid_index: result.index >= -1 
                   and result.index <= 7
    end
end

Binary Search With Step Counter

class Binary_Search_Algo
feature
  find(a1, a2, a3, a4, a5, a6, a7, a8, target: Integer): Search_Result
require
  sorted_input:
  a1 <= a2 and a2 <= a3 and a3 <= a4 and
  a4 <= a5 and a5 <= a6 and a6 <= a7 
    and a7 <= a8
do
  if a4 = target then
    result := create Search_Result.make(true, 3, 1)
  elseif target < a4 then
    if a2 = target then
      result := create Search_Result.make(true, 1, 2)
    elseif target < a2 then
      if a1 = target then
        result := create Search_Result.make(true, 0, 3)
      else
        result := create Search_Result.make(false, -1, 3)
      end
    else
      if a3 = target then
        result := create Search_Result.make(true, 2, 3)
      else
        result := create Search_Result.make(false, -1, 3)
      end
    end
  else
    if a6 = target then
      result := create Search_Result.make(true, 5, 2)
    elseif target < a6 then
      if a5 = target then
        result := create Search_Result.make(true, 4, 3)
      else
        result := create Search_Result.make(false, -1, 3)
      end
    else
      if a7 = target then
        result := create Search_Result.make(true, 6, 3)
      elseif target > a7 and a8 = target then
        result := create Search_Result.make(true, 7, 4)
      elseif target > a7 then
        result := create Search_Result.make(false, -1, 4)
      else
        result := create Search_Result.make(false, -1, 3)
      end
    end
   end
 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 l_hit: Search_Result 
     := lin.find(3, 7, 10, 14, 19, 21, 25, 30, 30)
    let b_hit: Search_Result 
     := bin.find(3, 7, 10, 14, 19, 21, 25, 30, 30)

    let l_miss: Search_Result 
     := lin.find(3, 7, 10, 14, 19, 21, 25, 30, 11)
    let b_miss: Search_Result 
     := bin.find(3, 7, 10, 14, 19, 21, 25, 30, 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

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/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 uniform)

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/miss comparisons
  • short write-up of strategy tradeoffs
  • one paragraph on how contracts influenced your design