# CompSciWeek2

(Wed. only)

## Contents

• 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

## 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>