Approximate solutions

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

cube = int(input("Enter a number: ")
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
if abs(guess**3 - cube) >= epsilon:
  print('Failed on cube root of', cube)
else:
  print(guess, 'is close to the cube root of', cube)

• decreasing increment size -> slower program
• increasing epsilon -> less accurate answer

Bisection Search

• half interval each iteration
• new guess is halfway in between
• Play a game to illustrate this

Finding the cube root through a bisection search

cube = int(input("Enter a number: ")
epsilon = 0.01
low = 0
high = cube
guess = (low+high)/2.0
num_guesses = 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)

Convergence of Bisection Search

• Search space (using N=(cube+1)*epsilon)
  • first guess: N/2
  • second guess: N/4
  • k^th guess: N/2k
• guess converges on the order of log2N steps
• bisection search works when value of function varies monotonically with input
• code as shown only works for positive cubes > 1 -- why?
• challenges:
  • modify to work with negative cubes!
    • Use the abs() function.
  • modify to work with cube<1!
  • For cube<1, search space is 0 to x, but cube root is greater than cube and less than 1.
  • Modify the code to choose the search space depending on value of cube.

Functions

• More code is not necessarily a good thing
• Measure good programmers by the amount of functionality
  • Introduce functions
  • Mechanism to achieve decomposition and abstraction

Example: Pen

• A pen is a black-box
• We don't need to know how it works
• Know the interface: click before use, press against paper to release ink
• Abstraction: do not need to know how pen works to use it.
• Different components in the pen are manufactured by different entities. The assembler simply assembles the components to produce something useful.
• Decomposition: different components work together to achieve an end goal.

In programming, create structure with decomposition

• Divide code into modules:
  • Modules are self contained
  • used to break-up code
  • intended to be reusable
  • keep code organized
  • keep code coherent
  In this lecture, we achieve decomposition with functions. Later, we achieve decomposition with classes.

Functions are reusable pieces/chunks of code. Functions are not run in a program until they are called or invoked in a program. Function characteristics:

• has a name
• has parameters (0 or more)
• has a docstring (optional but recommended)
• has a body
• returns something

Writing a function

def is_odd(i):  #keyword name parameeters
  """  #docstring begin
  Input: i, a positive int
  Returns true if i is odd, otherwise False
  """  #docstring end
  #body
  print("inside is_odd")
  return i%2 == 1   #return is a keyword


is_odd(4)  #later in the code, you call the function using its name and values for parameters