A range of code relating to Algorithms and Data Structures

Jan 21, 2019

6 minutes

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

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