Simple Programs Flashcards
Week 2 of Intro to computer science and programming using Python
Strings
- 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
More on strings
- Can slice strings using [start:stop:step]
- Strings are “immutable” - cannot be modified
Approximate solutions
- can’t guarantee exact answer
- start with exhaustive enumeration
- take small steps to generate guesses in order
- check to see if close enough
Approximate solutions - continued
- 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)
Bisection search
- 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
- Floats approximate real numbers
- Internally computers represents numbers in binary
Decimal number
302 = 310n2 + 010n1 + 2*10n0
Binary number
10011 = 12n4 + 02n3 + 02n2 + 12n1 + 1*2n0
Convert decimal integer to binary
- 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
Fractions
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)
Implications
- 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.
Newton-Raphson - definition
General approximation algorithm to find roots of polynomial in one variable
Newton-Raphson
- 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
Good Programming
- more code not necessarily a good thing
- measure good programmers by the amount of functionality
- Mechanism to achieve decomposition and abstraction
Decomposition
Break problems into different, self-contained, pieces
Abstraction
Suppress details of method to compute something from use of that computaion
Modules
- self-contained
- break up code
- reusable
- keep code organized
- keep code coherent
Achieve decomposition
- with functions
- with classes
Abstraction in detail
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
Achieve abstraction
- with function specification
- with docstrings
Functions
- called or invoked
- has a name
- has parameters
- has a docstring (optional)
- has a body
Variable scope
- 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
return only
- 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
Function specification
a contract between the implementer and the client.
- Assumption: conditions that must be met by clients
- Guarantees: conditions that must be met by the function
Recursion
- divide-and-conquer
- decrease-and-conquer
- a function that calls itself
- must have 1 or more base cases
- must solve the same problem on some other input
Recursion observations
- each recursive call creates its own scope/environment
- bindings of variables in a scope is not changed
- flow of control passes back to previous scope once function call returns a value
Iteration
vs
Recursion
- recursion may be simpler, more intuitive
- recursion may be efficient from programmer POV
- recursion may not be efficient from computer POV
