Python MIT OOPS

[b]


L3:




Italian program



commands

assignment

input/output

condition

loop



print x, 'hello world'


Defensive programming



@ToDo: To test the code List: mylist = [] mylist = mylist + [i] #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.



[img]/admin/blogs/images/callouts/1.png" border="0" alt="1" width="12" height="12[/img]

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

[img]/admin/blogs/images/callouts/2.png" border="0" alt="2" width="12" height="12[/img]

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

[img]/admin/blogs/images/callouts/3.png" border="0" alt="3" width="12" height="12[/img]

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

[img]/admin/blogs/images/callouts/4.png" border="0" alt="4" width="12" height="12[/img]

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[i] == num:
      return true, i
   elif last - first == 1:
      return false
   elif list[i]  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[/b]




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