A range of code relating to Algorithms and Data Structures
Jan 21, 2019
The code for this algorithm can be found in
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
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
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
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