Interfaces and Inheritance We are going to cover this in detail before function-like objects
java.nio.file This, along with try-with-resources, is the new and better way to do fileIO. One plus: files close automatically.
Old Business Let's do the bozo sort. It is idiotic; you shuffle the items and check if they are in order. If not, repeat.
from random import shuffle
def is_in_order(x): #x is a list. Return True iff x is an ascending order.
y = x[0]
for i in x:
if i < y:
return False
y = i
return True
def bozo(x):
while not is_in_order(x):
shuffle(x)
x = list(range(10))
shuffle(x)
print(x)
bozo(x)
print(x)
The mean time to resolution is O(n!) It is hopeless to
sort more than a few elements in this manner. We did this for ten
elements in class and it was miserably slow.
Computing Powers
def motteler(x, n): #O(n)
if n < 0:
x = 1/x
n = -n
y = x
while n > 1:
x *= y
n -= 1
return x
def boyer(x, n): #x is a number, n is integer O(log(n))
sign = True
if n < 0:
sign = False
n = -n
if n == 0:
return 1
g = 1
s = x
while g * 2 < n:
s = s*s
g = g*2
while g < n:
s = s * x
g += 1
if sign:
return s
else:
return 1/s
print(boyer(4,5) == 1024)
print(boyer(1.00001, 100000))
Exercise Convering bases using bigendian and littleendian methods
The BigEndian Algorithm
def big_endian(n, b):
"""prec: n is a nonnegative integer, b is a positive integer and 2 <= n <= 16.
postc: returns a string with the base b representation of n
pass
The LittleEndian Algorithm
def little_endian(n, b):
"""prec: n is a nonnegative integer, b is a positive integer and 2 <= n <= 16.
postc: returns a string with the base b representation of n
pass
Bubbly goodness!
The Euclidean Algorithm
Theorem: suppose a, b, q and r are integers and that b = a*q + r.
Then gcd(a,b) = gcd(a, r)
gcd(49, 14) = 7
gcd(902358093285908325, 23590349349234983245)o
224
/ \
2 112
/ \
4 28 - 2
/ \ |\
2 2 7 2
224 = 7*2*2*2*2*2
140 = 7*5*2*2
gcd(224, 140) = 28
224 = 140(1) + 84 gcd(224,140) = gcd(140,84)
140 = 84(1) + 56 gcd(140, 84) = gcd(84, 56)
84 = 56(1) + 28 gcd(84, 56) = gcd(56, 28)
56 = 28(2) + 0 gcd(56, 28) = gcd(28, 0) = 28
proof of theorem
b = a*q + r
suppose d divides a and b evenly
Write a = s*d, b = t*d
r = b - a*q = t*d - s*d*q = d(t - s*q) d divides r evenly.
By a similar argument, every commond divisor of a and r is a divisor of b.
Hence, gcd(a,b) = gcd(a,r).
A little diophanatine fun:
Theorem. If a and b are integers, then theere are integers
x and y so a*x + b*y = gcd(a,b).
224 = 140(1) + 84
140 = 84(1) + 56
84 = 56(1) + 28 start here
56 = 28(2) + 0
28 = 84 - 56(1)
= 84 - (140 - 84)
= 84*2 - 140
= (224 - 140)*2 - 140
= 224*2 - 140*3
= 224*2 + 140*(-3)
--> (2,-3)
slowest case: two adjacent fibonacci numbers
Little endian method:
731
6
731 *5
121 *15
20 *215
3 *3215
0 3215
3 2 1 5
6 18 120 726
---------------------
3 20 121 731
a b c d
x ax ax^2 + bx
-------------------------------
a ax + b ax^2 + bx + c ax^3 + bx^2 + cx + d.
def convert(n, b):
return a string with a base-b representation of n. 1
4 1 9 6 7|
1 4 9 6 7|
1 4 6 9 7|
1 4 6 7|9 largest bubbles to the top
1 4 6|7 9
n - 1 + n - 2 + n - 3 + .... 1 = n(n-1)/2 = O(n^2)
r