# Inf2 - Introduction to Algorithms and Data Structures
# Python lab sheets, Sept-Oct 2020

# LAB SHEET 2: SOLUTIONS TO EXERCISES 


# Exercise 1 (page 5)

def GCD(m,n):
    if n == 0:
        return m
    else:
        return GCD(n, m % n)

# works whenever m > n, by complete induction on n
# hence works in other cases too


# Exercise 2 (page 7)

# Part 1

def expmod1(a,n,m):
    return (a ** n) % m

# Part 2

def expmod2(a,n,m):
    r = 1
    for i in range(n):
        r = (r * a) % m
    return r

# Part 3

def expmod3(a,n,m):
    if n==0: return 1
    else:
        r = expmod3(a,n//2,m)
        if n%2==0: return (r * r) % m
        else: return (r * r * a) % m

# Part 4

# Timing the above should reveal results similar to those in Lecture 2 slides.
# For small n, expmod1 may be the fastest, as the built-in '**' is more
# efficient than repeated multiplication.
# But once the results of a ** n get too big, expmod1 struggles, and can even
# be observed to crash once space limit is reached.
# For a,n,m of 12 digits or more, only expmod3 is feasible, and it remains so
# even for 100-digit numbers.

# Part 5

def isprobableprime(n):
    return expmod3(2,n-1,n)==1

def probableprime(n):
    m = (n//2)*2 + 1  # first odd number >= n
    while True:
        if isprobableprime(m): return m
        else: m += 2

# this version searches the odd numbers from n upwards
# it could be further refined e.g. to avoid testing multiples of 3


# Exercise 3 (page 9)

# Part 1

# in-place insert sort, as in lecture slides:

def insertSort(A):
    for j in range(1,len(A)):
        a=A[j]
        i=j-1
        while i>=0 and a < A[i]:
            A[i+1] = A[i]
            i -= 1
        A[i+1]=a
    return A

# Part 2

# again we closely follow lecture slides:

def merge(B,C):
    D = [0] * (len(B)+len(C))
    i,j = 0,0
    for k in range(0,len(D)):
        if (i < len(B) and (j == len(C) or B[i] < C[j])):
            # this does what we want even when i,j out of range for B,C
            D[k] = B[i]
            i += 1
        else:
            D[k] = C[j]
            j += 1
    return D

def mergeSort(A,m,n):
    if n-m == 1:
        return [A[m]]
    else:
        p = (m+n)//2
        B = mergeSort(A,m,p)
        C = mergeSort(A,p,n)
        return merge(B,C)

def mergeSortAll(A):
    return mergeSort(A,0,len(A))

# Part 3

# Timing the above on random lists should produce results similar to those
# in the Lecture 2 slides. But it's also observable that insertSort beats
# mergeSortAll on already sorted inputs:

L1 = list(range(0,1000000))
L2 = L1[:]
time('insertSort(L1)')      # 0.37s on my machine
time('mergeSortAll(L2)')    # 9.46s


# Part 4

# insert sort with user-supplied comparison operation

def generalInsertSort(A,before):
    for j in range(1,len(A)):
        a=A[j]
        i=j-1
        while i>=0 and before(a,A[i]):
            A[i+1] = A[i]
            i -= 1
        A[i+1]=a
    return A

# merge sort can be adapted similarly

# example: suppose list entries are 'records' implemented as dictionaries, e.g.

students = [
       { 'surname' : 'Smith', 'forename' : 'Sarah', 'matric' : 1234567,
         'degree' : 'BEng Computer Science'} ,
       { 'surname' : 'Jones', 'forename' : 'James', 'matric' : 1345678,
         'degree' : 'BSc Mathematics'} ,
       { 'surname' : 'Piper', 'forename' : 'Peter', 'matric' : 1123456,
         'degree' : 'MEng Engineering'}
    ]

# we can sort this either alphabetically by surname...

def surnameBefore (s,t):
    return s['surname'] < t['surname']

generalInsertSort (students, surnameBefore)

# ...or numerically by matric number...

def matricBefore (s,t):
    return s['matric'] < t['matric']

generalInsertSort (students, matricBefore)

# ...or indeed by any other ordering we can think of.

# slicker alternative using 'lambda' (no need for surnameBefore, matricBefore)

generalInsertSort (students, lambda s,t: s['surname'] < t['surname'])

generalInsertSort (students, lambda s,t: s['matric'] < t['matric'])


# END OF FILE