Student Instructions | Week 4 | Topics: Exhaustive enumeration, binary numbers, fractions

Oregon State University | ENGR 103 | Dr. Cheng Li

Studio Overview

• Theme: Optimization by Exhaustive Search
• Related Reading: Ch 3.1, 3.3
• Duration: 90 minutes | All 4 sections run the same activity
• Materials: Laptop with Spyder or Jupyter, this handout

0:00–0:10 — Warm-Up

Without running code, predict the output:

Recall

Type and run this code:

for i in range(5):
    if i**2 == 9:
        print('Found:', i)
        break
print('Done')

What prints?

0:10–0:35 — Part 1 — Codedex Warmup (Guided)

Type and run each snippet.

Exercise 4A — Binary Conversion

Type and run this code:

# Test integer values — convert each one to binary step by step
for test_val in [0, 1, 5, 10, 255, 1023, 4095]:
    n = test_val
    if n == 0:
        bits = '0'
    else:
        bits = ''
        while n > 0:
            bits = str(n % 2) + bits
            n //= 2
    print(f'{test_val:5d}  →  {bits:>14s}  (Python check: {bin(test_val)[2:]})')

What is the binary of 2024? How many bits does it need?

Exercise 4B — Guess-and-Check for Perfect Cube

Type and run this code:

# Find the cube root of a perfect cube
target_number = 3375
cube_root = None

for guess in range(0, target_number + 1):
    if guess ** 3 == target_number:
        cube_root = guess
        break
    elif guess ** 3 > target_number:
        break

if cube_root is not None:
    print(f'Cube root of {target_number} = {cube_root}')
else:
    print(f'{target_number} is not a perfect cube')

Try with 4096, then 1000, then 500. Which are perfect cubes?

Exercise 4C — Quadratic Optimization Search

Type and run this code:

# Equation: y = -(x - 5.5)^2 + 100  (a downward-opening parabola)
# Find the value of x (between 4.0 and 9.0) that maximizes y

best_x = None
max_y = -1

for x_int in range(40, 91):   # Test x from 4.0 to 9.0 in 0.1 steps
    x = x_int / 10.0
    y = -(x - 5.5)**2 + 100
    if y > max_y:
        max_y = y
        best_x = x

print(f'Optimal x value: {best_x:.1f}')
print(f'Maximum y value: {max_y:.2f}')

Why do we multiply the range by 10? What is the optimal x value?

0:35–1:10 — Part 2 — Practical Lab: Digital-to-Analog Voltage Mapping

Work in pairs. You are mapping a digital 12-bit ADC value to an analog electrical Voltage. Your task: use exhaustive search to find the digital ADC value that most closely corresponds to a specific target analog voltage.

Background & Setup

Type and run this code:

# 12-bit ADC mapping to Voltage: digital input 0–4095
# Formula: voltage = adc_value * (14.0 / 4095)
# (14.0 V = max voltage, ADC 4095 = full scale)

target_voltage = 8.5   # Volts — we want to find the closest integer ADC value

# Example: check what voltage ADC value 2485 maps to
adc = 2485
voltage = adc * 14.0 / 4095
print(f'ADC {adc} maps to {voltage:.4f} V')

Copy this setup. Change the adc value and observe how voltage changes.

Tasks

1. Use exhaustive search (for loop, adc = 0 to 4095) to find the ADC value
   where  abs(adc * 14.0 / 4095 - target_voltage)  is minimized.
2. Print: best_adc, best_voltage (what the ADC actually outputs), and the error.
3. Convert your best_adc to binary and print it.
4. Repeat for target voltages: 2.0, 6.0, 8.5, 12.0
5. Make a small table: Target Voltage | Best ADC | Actual Voltage | Error | Binary

1:10–1:25 — Part 3 — Extension: Exponential Doubling Search

Find the minimum number of doublings needed such that a starting value of 500 exceeds 1,000,000.

Extension

Type and run this code:

start_val = 500
target = 100000000
n_doublings = 0

while start_val * (2 ** n_doublings) <= target:
    n_doublings += 1

print(f'Minimum doublings: {n_doublings}')
print(f'Final value: {start_val * 2**n_doublings:,}')
print(f'Binary of n: {bin(n_doublings)}')

import math
print(f'Analytical check: ceil(log2({target}/{start_val})) = {math.ceil(math.log2(target/start_val))}')

Run it. Does the while-loop answer match the analytical log₂ answer?

1:25–1:30 — Wrap-Up & TA Check-Off

Show TA the Part 2 table (4 target voltages with binary conversion). Discuss: why is exhaustive search slow for large ranges?