Okay, what is this about?

Python Programming Constructs

• Reminder: intuitively read the code segments to grasp their behavior

• Key components of the Python programming segments

  • Function calls
  • Assignment statements
  • Iteration constructs
  • Conditional logic
  • Variable creation
  • Variable computations
  • Variable output

• Make sure that you can find all of these components in Python source code!

Variables in Python Programs

• Variables in Python have values, types, and names

• A function can manipulate a variable using operators

  • The + symbol denotes addition and concatenation

  • The -,*,/ symbols denotes have standard meanings

  • The += symbol denotes addition and assignment

  • The % symbol denotes modular arithmetic for a remainder

• Variable Types: The type(a) returns the type of a

• Type Changing: int(a) transforms variable a into an integer type

A First Look at Exhaustive Enumeration

• Many numerical computations require a specific output value for an input, often achieved by iteration with a decrementation approach

• The exhaustive enumeration approach "naively" looks through all possibilities until it finds the correct solution

• How does exhaustive enumeration work?

  • List all possible values for a computation
  • Check to see if the current value is correct
  • If not correct, try the next value in the list
  • Continue until the correct value is found

• Easy to implement and understand. Often fast enough for practical purposes!

• When is it not efficient enough to perform exhaustive enumeration?

Exhaustive Primality Testing

x = int(input("Enter integer greater than 2: "))
sm_div = None
for guess in range(2, x):
    if x % guess == 0:
        sm_div = guess
        break
if sm_div != None:
    print(f"Smallest divisor of {x} is {sm_div}")
else:
    print(f"Wow, {x} is a prime number!")

Efficient Primality Testing

x = int(input("Enter integer greater than 2: "))
sm_div = None
if x % 2 == 0:
    sm_div = 2
else:
    for guess in range(3, x, 2):
        if x % guess == 0:
            sm_div = guess
            break

What is the purpose of the range(3, x, 2) function call?

Table of Prime Numbers

      2      3      5      7     11     13     17     19     23     29
     31     37     41     43     47     53     59     61     67     71
     73     79     83     89     97    101    103    107    109    113
    127    131    137    139    149    151    157    163    167    173
    179    181    191    193    197    199    211    223    227    229
    233    239    241    251    257    263    269    271    277    281
    283    293    307    311    313    317    331    337    347    349
    353    359    367    373    379    383    389    397    401    409
    419    421    431    433    439    443    449    457    461    463
    467    479    487    491    499    503    509    521    523    541
    547    557    563    569    571    577    587    593    599    601
    607    613    617    619    631    641    643    647    653    659
    661    673    677    683    691    701    709    719    727    733
    739    743    751    757    761    769    773    787    797    809
    811    821    823    827    829    839    853    857    859    863
    877    881    883    887    907    911    919    929    937    941
    947    953    967    971    977    983    991    997   1009   1013

• Do this code correctly detect prime numbers? How quickly?

Exhaustive Square Root Computation

epsilon = 0.01
step = epsilon**2
num_guesses = 0
ans = 0.0
while abs(ans**2 - x) >= epsilon and ans <= x:
    ans += step
    num_guesses += 1
print(f"Guessed {num_guesses} times")
if abs(ans**2 - x) >= epsilon:
    print(f"Could not find sqrt of {x}")
else:
    print(f"{ans} is close to sqrt of {x}")

Programming Warmup

Bisection Square Root Computation

epsilon = 0.01
step = epsilon**2
num_guesses, low = 0, 0
high = max(1,x)
answer = (high + low)/2
while abs(answer**2 - x) >= epsilon:
    num_guesses += 1
    if answer**2 < x:
        low = answer
    else:
        high = answer
    answer = (high + low)/2

Programming Warmup

Computing the Arithmetic Mean

def compute_mean(numbers):
    s = sum(numbers)
    N = len(numbers)
    mean = s / N
    return mean
numbers = [5,1,7,99,4]
print(str(compute_mean(numbers)))

Type Hints for Function Parameters

from typing import List

def compute_mean(numbers: List) -> float:
    s = sum(numbers)
    N = len(numbers)
    mean = s / N
    return mean

• How is this function different from the previous one?

• What are the benefits of adding type hints to parameters?

• Why is this not a complete implementation of compute_mean ?

Investigating Numerical Computation

• Different algorithms exhibit different performance trade-offs

• There are different forms of numerical computation in Python:

  • Q1: What are the benefits of exhaustive enumeration?

  • Q2: Why is exhaustive enumeration not always efficient?

  • Q3: How does bisection search improve algorithms?

  • Q4: How can bisection search help other algorithms?

  • Q5: How can we compare the performance of two algorithms?

• We will investigate these algorithms in upcoming projects!

• Guess and check and divide and conquer are general purpose strategies