SIMPLE NUMERICAL

PROGRAMS
PROF. ASSOC. DR. GLORIA TYXHARI

I N T R O D U C T I O N TO C O M P U TAT I O N A N D P R O G R A M M I N G U S I N G P Y T H O N

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 1

LAST TIME
• strings
• branching – if/elif/else
• while loops
• for loops

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 2

TODAY
• string manipulation
• guess and check algorithms
• approximate solutions
• bisection method

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 3

Strings
• Strings are sequences of case sensitive
characters processed as ordered
collections.

• Strings are structured (non-scalar)

objects.
o has internal structure
o can access individual characters
o ex h e l l o
01234
3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 4
Strings
• can compare strings with ==, >, < etc.
• len() is a function used to retrieve the
length of the string in the parentheses
o Ex: s = “abc”
len(s) → evaluates to 3
• indexing retrieves characters by
position
• Slicing extracts substrings from the
sequence

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 5

Strings
• Strings are immutable objects
• Operations that appear to modify strings
create new string objects
• This ensures the stability of data
structures

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 6

Iterations
• Iteration allows processing each character
sequentially.
• Loops can examine each character in a
string one by one.
• Direct iteration is typically clearer than
index iteration.
Ex: Direct Ex: Index iteration
iteration word = "Python"
word = "Python" for i in
for letter in word: range(len(word)):
3/24/2026
print(letter) print(word[i])
PROF. ASOC. DR GLORIA TYXHARI 7
STRINGS
• square brackets used to perform indexing into a string to
get the value at a certain index/position
s = "abc"
index: 0 1 2 -- indexing always starts at 0
index: -3 -2 -1 -- last element always at index -1

s[0] → evaluates to "a" s[-1] → evaluates to "c"

s[1] → evaluates to "b" s[-2] → evaluates to "b"
s[2] → evaluates to "c" s[-3] → evaluates to "a"
s[3] → trying to index out of bounds, error

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 8

STRINGS
• can slice strings using [start:stop:step]
• if give two numbers, [start:stop], step=1by default
• you can also omit numbers and leave just colons
s = "abcdefgh"
s[3:6] → evaluates to "def", same as s[3:6:1]
s[3:6:2] → evaluates to "df"
s[::] → evaluates to "abcdefgh", same as s[0:len(s):1]
s[::-1] → evaluates to "hgfedbca", same as s[-1:-(len(s)+1):-1]
s[4:1:-2] → evaluates to "ec"

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 9

STRINGS
• strings are “immutable” – cannot be modified
s = "hello"
s[0] = ‘y’ → gives an error
s = 'y'+s[1:len(s)] → is allowed, s bound to new object

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 10

for LOOPS RECAP
• for loops have a loop variable that iterates over a set of values
for var in range(4): → var iterates over values 0,1,2,3
<expressions> → expressions inside loop executed with
each value for var

for var in range(4,6): → var iterates over values 4,5

<expressions>
• range is a way to iterate over numbers
• but a for loop variable can iterate over any set of values, not
just numbers!

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 11

STRINGS AND LOOPS
• these two code snippets do the same thing
• bottom one is more “pythonic”
s = "abcdefgh"
for index in range(len(s)):
if s[index] == 'i' or s[index] == 'u’:
print("There is an i or u")
for char in s:
if char == 'i' or char == 'u’:
print("There is an i or u")

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 12

 CODE EXAMPLE:
ROBOT CHEERLEADERS
an_letters = "aefhilmnorsxAEFHILMNORSX“ else:
word = input("I will cheer for you! Enter a word: ") print("Give me a " + char + "! " +
char)
times = int(input("Enthusiasm level (1-10): "))
i += 1

i=0
print("What does that spell?")
while i < len(word):
for i in range(times):
char = word[i]
print(word, "!!!")
if char in an_letters:
print("Give me an " + char + "! " + char)

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 13

EXERCISE
s1 = "IE u rock"
s2 = "i rule IE"
if len(s1) == len(s2):
for char1 in s1:
for char2 in s2:
if char1 == char2:
print("common letter")
break

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 14

GUESS-AND-CHECK
Also called exhaustive enumeration, a problem-solving
technique where the program systematically tries every
possible solution until it finds the correct one.

• given a problem…
• you are able to guess a value for solution
• you are able to check if the solution is correct
• keep guessing until find solution or guessed all values

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 15

GUESS-AND-CHECK
This technique works whenever:
• the number of possible answers is finite
• we can check whether a guess is correct

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 16

GUESS-AND-CHECK
Example Problem: Finding a Cube Root
Suppose we want to find the cube root of an integer.

Example:
x=27
We know that:
33=27 → So the cube root is 3.
Instead of using math formulas, we can search for the
answer.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 17

GUESS-AND-CHECK
Idea of the Algorithm
The program will:
1. Start from 0
2. Compute the cube of the guess
3. Compare it to the number
4. Increase the guess by 1
5. Repeat until the correct cube root is found
This is the exhaustive search: we enumerate all
possibilities.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 18

GUESS-AND-CHECK
cube = 27
for guess in range(abs(cube) + 1):
if guess**3 == abs(cube):
print("Cube root of", cube, "is", guess)

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 19

GUESS-AND-CHECK
Understanding the Code
cube = 27 → the number whose cube root we
want to find
for guess in range(abs(cube) + 1): → tries every
possible guess from 0 up to cube
abs(cube) → the cube might be negative. Ex. cube
= -27
if guess**3 == abs(cube) → we test and if the
condition is true, we found the cube root.
print("Cube root of", cube, "is", guess) → The
program prints the result.
3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 20
GUESS-AND-CHECK
No Exact Cube Root
When
cube=20
There is no integer such that:
n3=20

The program must detect this situation.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 21

GUESS-AND-CHECK
No Exact Cube Root
cube = 27
for guess in range(abs(cube) + 1):
if guess**3 >= abs(cube):
print("Cube root of", cube, "is", guess)

After the loop we check:

if guess**3 != abs(cube):
print("Cube root is not a perfect cube")

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 22

GUESS-AND-CHECK
- Cube Root
cube = 8
for guess in range(abs(cube)+1):
if guess**3 >= abs(cube):
break
if guess**3 != abs(cube):
print(cube, 'is not a perfect cube')
else:
if cube < 0:
guess = - guess
print('Cube root of '+str(cube)+' is '+str(guess))

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 23

GUESS-AND-CHECK
Why the Algorithm Works
Exhaustive enumeration works because:
1. the search space is finite
2. we eventually test every possible value
3. the correct solution must appear somewhere in
the list of guesses
Therefore the algorithm is guaranteed to find the
solution if one exists.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 24

GUESS-AND-CHECK
Example of Execution
Suppose: cube = 8
The program tries:
guess guess³ result
0 0 not correct
1 1 not correct
2 8 correct
The algorithm stops when it finds the solution.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 25

GUESS-AND-CHECK
Advantages of Exhaustive Enumeration
This method is useful because:
• it is simple
• it is easy to implement
• it always works when the search space is
small
It is often the first algorithmic approach
students learn.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 26

GUESS-AND-CHECK
Disadvantage: Inefficiency
The algorithm can be very slow
o for a large search space
o program must test many possibilities
Ex. If number = 1,000,000 the algorithm may
need to test up to one million guesses.
So exhaustive enumeration is often replaced by
more efficient algorithms such as:
o approximation methods
o bisection search

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 27

APPROXIMATE SOLUTIONS
• good enough solution
• start with a guess and increment by some small
value
• keep guessing if |guess3- cube| >= epsilon
for some small epsilon

• decreasing increment size → slower program

• increasing epsilon → less accurate answer

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 28

Why Approximate Solutions
Are Needed
Find the cube root of x = 20?
o the integer whose cube equals 20?
number cube
2 8
3 27
The cube root of 20 lies between 2 and 3 →, not an integer.
Exhaustive enumeration cannot give the exact answer.
We search for a value whose cube is close enough to 20.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 29

Idea of an Approximate
Solution
Instead of checking only integers, we allow decimal guesses.
Example guesses:2.0
2.1
2.2
2.3
...

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 30

Idea of an Approximate
Solution
Each guess is tested.
If → ∣guess3−x∣<ϵ then the guess is considered good
enough.
Here: ε (epsilon) is a small tolerance value
it defines how accurate the answer must be.

Ex: epsilon = 0.01

This means the cube of the guess can differ from the real
value by less than 0.01.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 31

Algorithm for Approximation
The basic algorithm works like this:
1. Start with a guess (usually 0)
2. Increase the guess gradually
3. Check how close the cube of the guess is to the
number
4. Stop when the difference is smaller than epsilon

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 32

Example Code (Approximation)
cube = 20
epsilon = 0.01
increment = 0.0001
guess = 0
while abs(guess**3 - cube) >= epsilon:
guess += increment
print("Approximate cube root:", guess)

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 33

Explanation of the Algorithm
epsilon = 0.01 → defines acceptable error. The result does
not need to be perfect, only close enough.
increment = 0.0001 → determines how fast the guesses
increase.
◦ Small increment → higher precision
◦ Large increment → faster but less precise.

abs(guess**3 - cube) >= epsilon → checks the difference

between:
◦ the cube of the guess
◦ the actual number.
If the difference becomes smaller than epsilon, we stop.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 34

 APPROXIMATE SOLUTION
cube = 27 print('num_guesses =', num_guesses)
epsilon = 0.01 if abs(guess**3 - cube) >= epsilon:
guess = 0.0 print('Failed on cube root of', cube)
increment = 0.0001 else:
num_guesses = 0 print(guess, 'is close to the cube
root of', cube)
while abs(guess**3 - cube) >= epsilon
and guess <= cube :
guess += increment
num_guesses += 1

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 35

Problem With Approximation
by Incrementing
Although this method works, it can be very slow.
Ex: If → increment = 0.0001
The program might need millions of iterations.

Why?
Because the guess increases very slowly.
Let’s introduce a better algorithm.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 36

Bisection Search
Bisection search is a more efficient method.
Instead of checking values one by one, the
algorithm repeatedly divides the search interval in
half.
The method relies on an important property:
◦ The cube function is monotonic.
That means:
◦ If a number increases, its cube also increases.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 37

Bisection Search
• half interval each iteration
• new guess is halfway in between

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 38

Bisection Search: Example
number cube
1 1
2 8
3 27
Because of this property, we can determine
whether the cube root is:
◦ above or
◦ below
our current guess.
3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 39
Example: Initial Search Interval
For positive numbers, the cube root must lie
between: 0 and x
Ex: cube = 27
◦ cube root must be between:0 and 27
So we define:
low = 0
high = cube

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 40

Example: First Guess
The algorithm chooses the middle point.
guess = (low + high) / 2
Ex: low = 0
high = 27
guess = 13.5
Then we check: guess³

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 41

Example: Updating the Interval
If → guess³ < cube
◦ the cube root must be greater than the guess.
◦ So we update:
◦ low = guess
If → guess³ > cube
◦ the cube root must be smaller than the guess.
◦ So we update:
◦ high = guess

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 42

Example: Repeating the Process
The algorithm repeats this process:
1. take the middle of the interval
2. test the cube
3. update the interval
4. repeat
Each iteration cuts the search space in half.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 43

Example of Bisection
For cube = 27 → Steps might look like this:
low high guess
0 27 13.5
0 13.5 6.75
0 6.75 3.375
0 3.375 1.6875
... ... ...
Eventually the guess converges to 3.
3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 44
 Bisection Algorithm
cube = 27 else:
epsilon = 0.01 high = guess
low = 0 guess = (high + low) / 2
high = cube print("Approximate cube
root:", guess)
guess = (high + low) / 2
while abs(guess**3 - cube) >= epsilon:
if guess**3 < cube:
low = guess

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 45

Why Bisection is Much Faster
Each step halves the interval.
Ex: 27
13.5
6.75
3.375
...
◦ search space shrinks very quickly.
◦ Instead of testing millions of guesses, the algorithm
finds the solution in very few steps.
3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 46
BISECTION SEARCH: Convergence
• search space: 0 - N
◦ first guess: N/2
◦ second guess: N/4
◦ third guess: N/8
◦ kth guess: N/2k
• guess converges on the order of log2N steps
• bisection search works when value of function
varies monotonically with input

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 47

Using Floats
•This chapter introduced algorithms that rely on
approximate solutions (using decimal numbers).
• These algorithms use floating-point numbers
(floats).
• However, floats behave differently from integers.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 48

What Are Floats?
A float is a number that can contain a decimal point.
Ex: 3.14 0.5 2.0
Floats → used to represent real numbers, not just
integers.
In algorithms like approximate cube root or bisection
search, floats are necessary because the solution is
often not an integer.
3
Ex: 20≈2.714
This value cannot be represented exactly using integers.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 49

Floats Are Not Exact
Representations
One of the most important ideas:
◦ Floating-point numbers cannot represent all real
numbers exactly.
Computers store numbers in binary format, not
decimal format.
◦ Because of this, some decimal numbers cannot be
represented perfectly.
◦ Ex: 0.1 → This number does not have an exact binary
representation. So internally the computer stores a
value very close to 0.1, but not exactly 0.1.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 50

Consequences of Float
Representation
Because floats are approximations, calculations
using floats may produce small rounding errors.
Ex: 0.1 + 0.2 → In mathematics this equals: 0.3
→ In a computer the result may be
something like:0.30000000000000004
This happens because each number is stored
approximately, and the small errors accumulate.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 51

Why This Matters for Algorithms
This issue becomes important when algorithms
compare floating-point numbers.
Ex: suppose we write:
if guess**3 == x:
This comparison may fail even if the numbers are
extremely close.
Because of floating-point rounding, the cube might
be:19.999999999 instead of:20
The equality test returns False.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 52

Using Tolerance Instead of
Equality
To solve this problem, we use a tolerance value (like
epsilon (ε) ).
Instead of checking equality, the program checks
whether the difference is small enough.
Ex: abs(guess**3 - x) < epsilon
This means: The cube of the guess is close enough
to the target value.
This avoids problems caused by floating-point
rounding errors.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 53

Why Equality Comparisons Are
Dangerous with Floats
Comparing floats using == can be unreliable.
Ex: 0.1 + 0.2 == 0.3
This may return: False, even though mathematically
the values are equal.
Therefore, when working with floats, avoid direct
equality comparisons.
Instead, use a tolerance comparison.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 54

Floats and Approximation
Algorithms
Algorithms introduced earlier rely on floats.
Approximation algorithm → Uses floats when
incrementing guesses:
guess += increment
Bisection search → Uses floats when dividing the
interval:
guess = (high + low) / 2
Because floats are approximate, the algorithm must use
epsilon as the stopping condition.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 55

Stopping Condition for Float
Algorithms
The algorithm stops when:
|guess³ − x| < epsilon
This ensures:
• the solution is sufficiently accurate
• floating-point rounding does not cause problems
Without this condition, the algorithm might:
• never terminate, or
• fail to recognize the correct solution.

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 56

 Thank you

3/24/2026 PROF. ASOC. DR GLORIA TYXHARI 57