Algorithms and Data Structures

A range of code relating to Algorithms and Data Structures

Jan 21, 2019

6 minutes


Built with


Hash Table

The code for this algorithm can be found in Question 1/q1.py

This adds keys to a hash table of size 19 using the hash function defined by h(k)=6k+3 mod 19

In the first implementation hash_quadratic collisions are handled by probing

def hash_quadratic(d):
    #initialize table
    table = ["-"]*19
    flag=0
    #consider each integer k in the input
    for k in d:
        flag=0
        #if k is already in the table this is a duplicate so move to next integer in the input
        #note this check for a duplicate is using the functionality of python rather than checking using a linear probe
        if k in table:
            continue
        #apply the hash function
        i = (6*k+3) % 19
        init=i
        #initialize count that checks whether linear probe has considered each bucket and is now full
        count = 0
        #while bucket is already filled
        while table[i] != "-":
            #move to next bucket
            i = (init+count*count) % 19
            #increment count
            count += 1
            #if table is full
            if count == 18:
                flag=1
                #can return table as nothing further can be added
                break
        if flag==1:
            continue

        #table[i] is empty so k can be added here
        table[i] = k
    #now each part of the input has been considered return the table
    return table

In the second implementation, hash_double collisions are handled using double hashing with the secondary hash function h’(k)=11-(k mod 11)

def hash_double(d):
    #initialize table
    table = ["-"]*19
    flag=0
    #consider each integer k in the input
    for k in d:
        flag=0
        #if k is already in the table this is a duplicate so move to next integer in the input
        #note this check for a duplicate is using the functionality of python rather than checking using a linear probe
        if k in table:
            continue
        #apply the hash function
        i = (6*k+3) % 19
        init=i
        #initialize count that checks whether linear probe has considered each bucket and is now full
        count = 1
        #while bucket is already filled
        while table[i] != "-":
            #move to next bucket
            i = (init+count*(11-(k%11))) % 19
            #increment count
            count += 1
            #if table is full
            if count == 20:
                flag=1
                #can return table as nothing further can be added
                break

        if flag==1:
            continue
        #table[i] is empty so k can be added here
        table[i] = k
    #now each part of the input has been considered return the table
    return table

Ephemeral numbers

This code calculates the number of ephemeral numbers between two values.

A positive integer is k-ephemeral if its k-descendent sequence ends in 1, otherwise it is k-eternal.

The k-descendant sequence of a positive integer begins with the integer and then each successive term is the k-child of the previous one. The sequence terminates if it reaches a 1 or a term is repeated.

The k-child of a positive integer is the number obtained by taking the kth power of each digit and adding them.

This is implemented using the following function

def count_ephemeral(n1,n2,k):
    # Create a list of the powers required for the given value of k
    power_list=[x**k for x in range (10)]
    # Count keeps track of the number of ephemeral numbers
    count=0
    # Create two tables, one to store the eternal numbers, and one to store the ephemeral numbers
    eternal=set()
    eph=set()
    for n in range (n1,n2):
        # Current sequence stores all the values in the current sequence
        current_seq=set()
        # This checks if n has been seen before or if it is 1, in any of those cases it will break out of the loop
        while n not in current_seq and n not in eternal and n not in eph and n!=1:
            # Add the new number to the current sequence
            current_seq.add(n)
            # Calculate the k child of n
            k_child=0
            while n:
                digit = n % 10
                k_child+=power_list[digit]
                n //=10
            n=k_child
        # If n is an ephemeral number add it, and the rest of the sequence to the list of ephemeral numbers
        if n==1 or n in eph:
            eph.update(current_seq)
            count+=1
        # Otherwise add the sequence to the list of eternal numbers
        else:
            eternal.update(current_seq)
    return count

Sum and product expression

A sum and product expression is a statement containing positive integers, brackets and the plus and times operators. A sum and product expression i said to be good is none of the brackets are redundant. This function decides whether a sum and product expression is good. It is implemented using stacks and queues, the code for defining how these work is left out for brevity.

def good_expression(expression):
    # For completeness, remove all the spaces from the string just in case there are any
    expression=expression.replace(" ", "")
    # Initialise flags for if the statement is valid, if a close bracket was the last term and if the stack became empty on the last loop
    flag=0
    empty=False
    valid = True
    # Initialise a stack to store the operators
    data=Stack()

    for i in expression:
        count=0
        # The below if statement will trigger if a close bracket occurred on the last loop
        if flag==1 and empty==False:
            after = i
            before = b
            # If there isn't a multiplication on either of the sides of a pair of brackets, the statement is invalid
            if before!="*" and after!="*":
                valid=False
                break
        # If empty is True, then the first bracket of the pair was the first thing in the string, so there would need to be multiplication on the other side
        elif empty:
            after = i
            if after!="*":
                valid=False
        flag=0
        empty=0
        # If I is an operator or open bracket, just push it to the stack
        if i=="*" or i=="+" or i=="(":
            data.push(i)
        # But if i is a close bracket, more needs to be done
        if i==")":
            # Check if the stack is empty, as I will be popping from it, if it is empty, then there is an error
            if data.isEmpty()==True:
                valid=False
                break
            # Temporarily make valid false, for the purpose of checking the symbols in the bracket
            valid=False
            b=data.pop()
            while b!="(" and data.isEmpty()==False:
                # There needs to be an addition somewhere in the bracket, otherwise it is unnecessary
                if b=="+":
                    valid=True
                count+=1
                b = data.pop()
            # If there wasn't an addition, then break out of the loop ad the expression is bad
            if valid==False:
                break
            # If the bracket only had one symbol in it, it is unnecessary, and so the expression is bad
            if count==0:
                valid=False
                break
            # If the stack is empty, set the flag for the next element to check against
            if data.isEmpty()==True:
                empty=True
                flag=1
                continue
            b=data.top()
            flag=1
    # If the flag was set on the last element
    if flag==1:
        # If the symbol before the brackets isn't a multiply, then the statement is false
        if b!="*":
            valid=False

    return valid

Hybrid Merge Sort

For this algorithm, instead of recursively calling Merge Sort until the list to be sorted has length 1, we will implement Selection Sort to sort any list of length 4 or less. This algorithm will output a sorted list from largest to smallest.

First I implemented a function to perform Selection Sort

def SelectionSort(list):
    for i in range (0,len(list)):
        elem=list[i]
        pos=i
        for j in range(i+1,len(list)):
            if list[j]>=elem:
                elem=list[j]
                pos=j
        list[i], list[pos] = list[pos], list[i]
    return list

Then the function which performs Merge Sort and calls the Selection Sort function when appropriate

def HybridSort(nlist):
    # If the length of the list is less than or equal to 4, then sort using selection sort
    if len(nlist)<=4:
        nlist=SelectionSort(nlist)
    # Otherwise sort using merge sort, unless the list is of length 1
    if len(nlist)>1 and len(nlist)>4:
        # Find the middle of the list
        mid = len(nlist)//2
        # Use this to create two lists
        lefthalf = nlist[:mid]
        righthalf = nlist[mid:]

        HybridSort(lefthalf)
        HybridSort(righthalf)

        # Merging
        i=j=k=0
        # While the lists are not exhausted
        while i < len(lefthalf) and j < len(righthalf):
            # If the left half first index is greater than right half, add it to the output list
            if lefthalf[i] >= righthalf[j]:
                nlist[k]=lefthalf[i]
                # Increment the value of i so that the element would not be added multiple times
                i=i+1
            else:
                # Other wise the right half first index is larger, so add that
                nlist[k]=righthalf[j]
                # And again increment the index
                j=j+1
            # Increment k to jump to the next index in nlist
            k=k+1
        # If the loop has broken out to here then one of the lists is empty
        # Loop adding all the remaining elements of the lefthalf list, if it is empty then just move on
        while i < len(lefthalf):
            nlist[k]=lefthalf[i]
            i=i+1
            k=k+1
        # Loop adding all the remaining elements of the righthalf list, again, if it is empty then just move on
        while j < len(righthalf):
            nlist[k]=righthalf[j]
            j=j+1
            k=k+1