Python MIT OOPS

andyyuduo

　　







L3:






Italian program




commands


assignment


input/output


condition


loop




print x, 'hello world'



Defensive programming




@ToDo: To test the code List: mylist = [] mylist = mylist + #Here the '+' is overridden already.


mytuple = () mytuple = mytuple + (i) # Does it really work? To be checked.


Answer: Both can be.





[code="python"]mytuple = ('abc')

mytuple = mytuple + ('de')

print mytuple #Show 'abcde' instead of ('abc','de')

[code="python"]mytuple = ('abc','cde')

[code="python"]mytuple += ('fg') #Cause error. Last example because, the tuple convert to string, and the () is ignored.







You can't add elements to a tuple. Tuples have no append

or extend

method.





You can't remove elements from a tuple. Tuples have no remove

or pop

method.





You can't find elements in a tuple. Tuples have no index

method.





You can, however, use in

to see if an element exists in the tuple.



L4:




@Todo: To simulate


return None , no value assign to variable, but when use '==' to check, it return 'true'. Too suprised



[code="python"]def returnNone():

   return None


result = returnNone()

print result # show None # In shell mode, it would be nothing

print (result == None) #show true




@Todo: 20heads, 56 legs, how many chicken and pigs


Done, looping all possible values



@Todo: to verify it return [None,None] return [a,b,c] #return more than 1 value a,b,c = return [a,b,c] #assign to more than 1 variable


Done, actually, it return the tuple or list




@Todo: check Fibonacci number Use recursive method to calculate the numbers


Done, remember to handle the 0 & 1 number.



@Todo:Palindrome, to be write program to test



LS5:



@Todo: 2**1000


In shell prompt, it would large number with 'L'. When use print, auto conver and remove L



@Todo

: x=0.1, print x IEEE 754 floating point @Todo 64bits?? modem computer 64bit? what's that? 1 bit negative/positive 11 bit exponent 52 bit number (mantissa) 17 decimal number @Todo: for i in range(10) s+=0.1 actual result 0.999999999999989, when print, it auto round it.





successive approxmaition (极限法)



bisection method (二分法)



@Todo , try assert in sqrt method


Done. assert (condition), 'not match condition , error and terminate'



@Todo: find out sqrt To solve decimal fraction issue, to tune the program for the espion.


Done, use x*x - y 0):

    ans *= a

    b -= 1

  return ans





Use big O notation




汉诺塔


@Todo: to simulate the twoner


Done



[code="python"]def move (element, from, target)

   print 'move',element, 'from', from, 'target', target


def tower(i, from, target, tmp)

    if (i == 1):

      move(i,from,target)

    elsif

      #move n tower to tmp

      tower(i-1,from,tmp,target)

      #move last one to target

      move(i,from,target)

      #move n-1 tower to target

      twoer(i-1,tmp,target,from)




Complexity calculation as below







t(n) = t(n-2) + t(n-2) + t(n-2) + t(n-2)


t(n) = 2^k ( t(n-k) )





t(n) = 2^(n-1) t(1)





4种算法



@Todo: compare the 4 different alg




@Todo: write Binary search, then compare the one by one search



[code="python"]bsearch(num, list, first, last):

   i= ( first + last ) / 2

   if list == num:

      return true, i

   elif last - first == 1:

      return false

   elif list  num:

      return bsearch (num, list, first, i)



#Complexity calculation


t(n) = t(n/2)

t(n) = t(n/2/2)

t(n) = t(n/2/2/2)

t(n) = t(n/2^k)



2^k= n

k = log2(n)



t(n) = O(


  







@Todo: check link list ,constant list



LinkList: use 2 cell, one for value, the other for next element memory address, when add new one, just change one element, if you find one, you need to iternative some element, next next to skip skip ...



Depends on what element on your hand, if next element is far away, it cost more time.




Constant List: fixed space of each cell value, if add new element, it would reconstrut list

.


Access each element cost same time. You can calculate each skip steps



L9


:


linear



list, python, list of list


use box to save the pointer, each pointer point to a special area contains value.



Before search, sorted or not?


Linear search


N times



@Todo: check linklist, how to store object of object



Sorted + Search


nlog2(n), + log2(n)



If only search 1 time, use linear search



ksearch times


@Use selection sorting method with binary search, found out how many element that worth to sort before search




@Todo: Bubble sorting & selection sorting


Sorting method



Swap the small one




Selection sorting


Bubble section



Done



@Todo, dynamic function.



val=int


val(x)



@Todo list have sort function, to be try to found out how fast of it.



@Todo try assert


raise 'exception'


assert precondition



LS11




function debugging


performance debugging

LS11





Defensive programming



Both validation & debugging



Test: examine input/output


Unit Testing: validate each piece of program indivually, functions classes


Integration testing: PUt whole program togather, see does the program work?



Rush to integration test, but it's big mistake.


Test each part of unit



Easier to test & debug small thing than big thing




Why testing is always challenge



2 best way


Print Statement


Reading



Be systemmatic



@Todo clone list



list = otherlist[:]



different



list = otherlist



LS12





code should not always grow


Add more code to fix bug



Big Packing


Shortest path


Travles sales person


Sequence alignment


Knapsack problem



Greedy algor



locall optimal decision do not always lead to global opt.



@Todo: Knapsack problem


@Todo: To check optimal fibionic sequence because overlapping problem

overlapping subproblem


optimal structure




Optimal fibionic sequence


fibnoic, optimal to save the value






[code="python"]memres = {0:0,1:1} #init first elements

def getfib(num=10):

  if num in memres: #check key exist:

      return memres[num]


  memres[num] = getfib(num-1) + getfib(num-2)


  return memres[num]


#complexity, O(n) if not save value, O(2^n)




Decision tree



w=5,3,2

V=9,7,8



Each n





2,5,0



index,weight still available,value



2,5,0



1,5,0



0,5,0



@todo, write a decision tree daigram and code



@Todo:use try and raise the exception to check whether list element existing






[code="python"]num=10

assert num>7, 'error' #Assume the exper is correct, otherwise prompt error msg.


 

 



decision tree @to check


1. Depth first , left first

2. Back check
　　LS14:

　　Binary decision tree
　　Size of the problem? Size of the solution?
　　@Todo: problem? Solution?
　　@Knapsack problem, constraint volumn also
　　@Todo: what's pseudo polynomic?
　　LS15
　　Shallow equality ( point to same reference)
　　Deep equality
　　pass keyword
　　__init__(self,x,y)
　　__str__
　　__cmp__
　　__eq__ @tocheck this overloading use ==
　　dir(class), you know how many methods
　　dir(1)
　　dir('1')
　　LS16
　　class template for data type
　　data hidding, encapution
　　class Person(object) #Extend from object
　　if type (xxx) == QQ 
　　@Todo type to judge class
　　LS17
　　


class Location(object)
def __init_(self,x,y)
x = float(x)
y = y...
def move(xc,yc)
return Location(x+xc,y+yc)
def get Coords
return x,y
def getDis(other)
cx,cy = getCoords(other)
xd = x -xc
yd = y-yc
return math.sqrt(xd**2,yd**2)
class CompassPt(obj)
possibles = {n,w,w,..}
def init(pt)
if pt in possibles, self.pt = pt
else: raise error
def move (dist)
if self.pt == n, return (0,dist)
elif pt == S, return (0,-dist)
w (dist,0)
e (0,dist)
else: raise error
class field(obj)
def init (drunk, loc)
self.d = d
self.l = l
def move (self, cp , dist)
oldLoc = self.d
xc,yc = cp.move(dist)
self.loc = oldLoc.move(xc,yc)
def getLoc(self)
return self.loc
def getDrunk(self)
return self.drunk
class Drunk(obj)
def init(self,name)
def move(self, field, time = 1)
if field.getDrunk() == self:
raise error
for i in range(time)
pt = CompressPt(random.choice(CompressPt.possibles))
field.move(pt,1)
def performTrial(time,f):
start = f.getLoc()
distance = [0,0]
for t in range(1,time+1):
f.getDrunk().move(f)
newLoc = f.getLoc()
distance = newLoc.getDist(start)
distance.append(distance)
return distance
drunk = Drunk(hello world)
for i in range(j):
f = Field(drunk, Location(0,0))
distance = performTrial(500,f)
pylab.plot(distances)
pylab.title('hello')
pylab.xlabel(ok)
pylab.ylabel(okok)
pylab.show