CompSciWeek2

(Wed. only)

Reading Assignment

• Beginning Python, Chapter 5

Algorithms, Continued

• Complexity notation, O(n), etc.
• Loop Complexity
• First algorithms (Horner, Euclid, Babylonian)
• Code walk-through for a poorly designed Euclids algo.
• The KISS, DRY, and incremental principles
• Loading python modules

Poorly Designed Euclid's Algo.

<source lang="python"> a = 1547 b = 224

while(1):

 if a < b:
   c = a
   a = b
   b = c
 a = a % b
 if a < b:
   c = a
   a = b
   b = c
 if a == 0:
   break
 print "%d, %d"%(a,b)

print "The GCD of %d and %d is %d"%(a,b,b) </source>

Improved Version

<source lang="python"> doc = """ Euclid's Algo.: reduce 7/30 - 8/18

30 = 6*5 18 = 6*3 (7*3 - 8*5)/(6*5*3)

gcd(a,b)

gcd(30,18) = 6 = gcd(18,12) = 6 = gcd(12,6) = gcd(6, 0) = 6 [termination]

show: gcd(a, b) = gcd(b, a mod b)

 ... gcd(a, 0) = a

write:

 a = s*u, b = t*u
 u also divides r = a % b = a - b*q = (s - q*t)*u

Properties:

   (a + b) mod c = a % c + b % c
   a - b mod c = a mod c - b mod c
   (a*b) mod c = (a mod c) * (b mod c)

a*(b/a) """

1. always return a <= b

def order(a, b):

 if a < b:
   return a, b
 else: # a >= b
   return b, a

b = 1547 a = 224

1. Input integer a, b
2. Output: integer gcd(a,b)

def gcd(a, b):

 b, a = order(b, a)

 while b != 0:
   #print "%d, %d"%(a,b)
   a = a % b # a < b
   a, b = b, a
 return a

r = gcd(a, b)

str = "The GCD %d of %d and is %d "%(a, b, r) print str

1. subtracting numbers in quotient form

def qsub((a, b), (c, d)):

   return (a*c -b*d), (c*d)

</source>