Simple Programs

• A sequence of case sensitive characters • Can compare strings with ==, etc. • len() is a function to retrieve the lenght of the string • square brackets used to perform indexing

• Can slice strings using [start:stop:step] - Strings are “immutable” - cannot be modified

• can’t guarantee exact answer • start with exhaustive enumeration • take small steps to generate guesses in order • check to see if close enough

• Good enough solution • Start with a guess and increment by some small value • Use small epsilon (decreasing increment size -> slower program) (increasing epsilon -> less accurate answer)

• Radically reduces computation time - being smart about generating guesses is important. • Works well on problems with ‘ordering’ property, value of function being solved varies monotonically with input value.

• Floats approximate real numbers - Internally computers represents numbers in binary

302 = 310n2 + 010n1 + 2*10n0

10011 = 12n4 + 02n3 + 02n2 + 12n1 + 1*2n0

• take remainder relative to 2 (x%2) of number, that gives us the last binary bit • divide x by 2 (x//2), all the bits get shifted right • keep doing successive divisions, now remainder gets next bit and so on • then convert to binary form

Multiple by a power of 2 big enough to convert into a whole number. Can convert to binary and then divide by the same power of 2. • 0.375 * (2**3 = 3 (decimal) • convert 3 to binary (now 11) • divide by 2**3 (shift right) to get 0.011 (binary)

• if no integer p such that x*(2**p) is a whole number, then internal representation is always approximation • Suggest testing equality of floats is not exact Use abs(x-y) < some small number, rather than x == y • print(0.1) returns 0.1 because Python designers set it up this way to automatically round.

General approximation algorithm to find roots of polynomial in one variable

• Simple case cxn2 + k • First derivative 2cx • So if polynomial is xn2 + k, then derivative is 2x • Newton-Raphson says given a guess g for root, a better guess is: g-(gn2 -k)/2g

• more code not necessarily a good thing • measure good programmers by the amount of functionality • Mechanism to achieve decomposition and abstraction

Break problems into different, self-contained, pieces

Suppress details of method to compute something from use of that computaion

• self-contained • break up code • reusable • keep code organized • keep code coherent

• with functions - with classes

Think of piece of code as a black box • cannot see details • do not need to see details • do not want to see details • hide tedious coding details

• with function specification - with docstrings

• called or invoked • has a name • has parameters • has a docstring (optional) • has a body

• formal parameter (gets bound to the value of..) • actual parameter (when function is called) • new scope/frame/env. created when enter a function • scope is mapping of names to objects

• only inside a function • one return executed • code after a return is not executed! • value associated is given back to function caller

• outside and inside functions • execute many prints statements • code will be executed after print statement • value associated is outputted to the console