Simple Programs

Question 1

Strings

Answer 1

• 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

Question 2

More on strings

Answer 2

• Can slice strings using [start:stop:step]

- Strings are “immutable” - cannot be modified

Question 3

Approximate solutions

Answer 3

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

Question 4

Approximate solutions - continued

Answer 4

• 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)

Question 5

Bisection search

Answer 5

• 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.

Question 6

Floats

Answer 6

• Floats approximate real numbers

- Internally computers represents numbers in binary

Question 7

Decimal number

Answer 7

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

Question 8

Binary number

Answer 8

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

Question 9

Convert decimal integer to binary

Answer 9

• 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

Question 10

Fractions

Answer 10

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)

Question 11

Implications

Answer 11

• 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.

Question 12

Newton-Raphson - definition

Answer 12

General approximation algorithm to find roots of polynomial in one variable

Question 13

Newton-Raphson

Answer 13

• 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

Question 14

Good Programming

Answer 14

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

Question 15

Decomposition

Answer 15

Break problems into different, self-contained, pieces

Question 16

Abstraction

Answer 16

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

Question 17

Modules

Answer 17

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

Question 18

Achieve decomposition

Answer 18

• with functions

- with classes

Question 19

Abstraction in detail

Answer 19

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

Question 20

Achieve abstraction

Answer 20

• with function specification

- with docstrings

Question 21

Functions

Answer 21

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

Question 22

Variable scope

Answer 22

• 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

Question 23

return only

Answer 23

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

Question 24

print

Answer 24

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

Question 25

Function specification

Answer 25

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

Question 26

Recursion

Answer 26

- 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

Question 27

Recursion observations

Answer 27

- 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

Question 28

Iteration vs Recursion

Answer 28

- recursion may be simpler, more intuitive - recursion may be efficient from programmer POV - recursion may not be efficient from computer POV