string manipulation

s = "abc"
len(s) # 3

s[0] # "a"
s[1] # "b"
s[2] # "c"
s[3] # out of bounds error
s[-1] # "c"
s[-2] # "b"
s[-3] # "a"

string slicing [start:stop:step]

s = "abcdefgh"
s[3:6]    # "def", same as s[3:6:1]
s[3:6:2]  # "df"
s[::]     # "abcdefgh" same as s[0:len(s):1]
s[::-1]   # "hgfedcba" same as s[-1:-(len(s)+1):-1]
s[4:1:-2] # "ec"

string are immutable

  • i.e. cannot be modified 
    s = "hello"
s[0] = y              # gives an error
s = 'y' + s[1:len(s)] # allowed, but s is bound to new object

for loop over a string

s = "abcdefgh"
for index in range(len(s));
  if s[index] == 'i' or s[index] == 'u':
    print("There is an i or u")

# above for loop is the same as 
for char in s:
  if char == 'i' or char == 'u':
    print("There is an i or u")

guess and check

  • the process is also called exhaustive enumeration
  • given a problem:
    • guess a value
    • check if the solution is correct
    • keep guessing until solution is found or guessed all values

cube root problem

cube = 8
for guess in range(cube+1):
  if guess**3 == cube:
    print("Cube root of ",cube," is ", guess)

approximate solutions

  • good enough solution
  • start with a guess and increment by some value
  • error band is epsilon

cube root problem

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

cube root

cube = 27
epsilon = 0.01
num_guesses = 0
low = 0 
high = cube
guess = (high+low)/2.0
while abs(guess**3 - cube) >= epsilon:
  if guess**3 < cube:
    low = guess
  else:
    high = guess
  guess = (high + low)/2.0
  num_guesses += 1

print('num_guesses = ", num_guesses)
print(guess, " is close to the cube root of ", cube )