## Instructions

**Objective**

## Requirements and Specifications

**This is an individual assignment.**

**Question 1 (20 marks):**

- Locate only 3 of the bugs that are within the code, by indicating the line.
- Provide the correct code for each line where a bug is found.
- Briefly describe the methodology that allowed you to locate each one of the bugs (max. 200 words).

**Note:**Use the exact indentation as shown here to avoid including more bugs. A Python file is attached to avoid any mistakes in copying the code):

**Question 2 (50 marks):**

- Design your algorithm by providing pseudocode or diagrams that explain in appropriate level of detail the steps followed.
- Write Python code to tackle the aforementioned problem and use it to provide the outputs (that you should include in the text file deliverable) for a kitchen with 4 members of staff and with 6 members. What is your conclusion based on the waiting times?
- It would be faster to run one or two simulations of each kitchen set up. Why do you need to run multiple simulations? What is the risk of running one simulation per kitchen set up? Also, explain the choice of data structures and algorithms for your code. 50words.

**Question 3 (30 marks):**

- Design your algorithm by providing pseudocode or diagrams that explain in appropriate level of detail the steps followed.
- Write Python code (do not use built-in functions – you should use algorithms you learnt in practicals) to tackle the aforementioned problem with the following additional constrains:

- Use one sorting algorithm based on brute-force strategy to sort the whole array and test the running time for 10 instances of random arrays.
- Use another sorting algorithm with different complexity from the previous one to sort the whole array and test the running time for 10 instances of random arrays.

**Source Code
**

**QUESTION 1
**

import random

import pandas as pd

import numpy as np

from zmq import RATE

if __name__ == '__main__':

# Read xlsx

data = pd.read_excel('car_orders.xlsx', skiprows=1)

data = data.fillna(0)

print(data.head())

# Convert to numpy

data = data.to_numpy()

# Store the code of each drivethru

drivethru_codes = data[:,0]

data = data[:,2:]

# Define the step size. In this case, we will simulate with a stepsize of 1 minute

STEP = 1

# Define simulation time in minutes

SIM_TIME = 8*60 # 8 hours

# Define the number of items that can be delivered each 10 minutes

STAFF_MEMBERS = 6

RATE_OF_PRODUCTION = 16 # for 4 staff members

PRODUCTION_TIME = 10 # 10 minutes

# Define the number of instances

INSTANCES = 10

# Dictionary to store the average waiting times for each drive-thru

avg_time = dict()

number_clients = dict()

for i in range(INSTANCES):

#print(f"Running Instance {i+1}...")

# Define dictionaries to store the average time for each instance

instance_avg_time = dict()

instance_number_clients = dict()

# Simulate

time = 0

while time < SIM_TIME:

# Pick a random client

index = np.random.choice(data.shape[0], 1)

client = data[index, :]

# Number of items in client's order

order_items = np.sum(client)

# Compute the total number of minutes this order will take

order_time = order_items*PRODUCTION_TIME/RATE_OF_PRODUCTION

# Get code of drivethru

code = drivethru_codes[index][0]

# Now, add the average waiting time

instance_avg_time[code] = instance_avg_time.get(code, 0) + order_time

instance_number_clients[code] = instance_number_clients.get(code, 0) + 1

time = time + STEP

# Now, compute avg

instance_avg_time = {x: y/instance_number_clients[x] for x, y in instance_avg_time.items()}

# Add to avg_time

for key, val in instance_avg_time.items():

avg_time[key] = avg_time.get(key, 0) + val

# Now compute the final avg time

avg_time = {x: y/INSTANCES for x,y in avg_time.items()}

# Display results

print()

print(f"The average waiting time at each window given {STAFF_MEMBERS} staff members are:")

print("{:<10s} {:>10s}".format("Window", "Avg. Time (min)"))

print("{:<10s} {:>10s}".format("---------", "---------------"))

for key, val in avg_time.items():

print("{:<10s} {:>10.2f}".format(key, val))

print()

**QUESTION 2**

import random

import time

# Define a function to sort a row of integers

# This function will apply the Merge Sort algorithm since

# That algorithm has a time complexity of nlog(n) which is the faster

def sort(arr, ascending = False):

if len(arr) > 1:

N = len(arr) # size of list

# Compute mid index

mid = N//2

# Take left part

L = arr[:mid]

# Take right part

R = arr[mid:]

# Sort left part

sort(L, ascending)

# Sort right part

sort(R, ascending)

i = j = k = 0

while i < len(L) and j < len(R):

if ascending:

if L[i] <= R[j]: # The part in the left is smaller, so we need to swap

arr[k] = L[i]

i += 1

else:

arr[k] = R[j]

j += 1

else:

if L[i] >= R[j]: # The part in the left is smaller, so we need to swap

arr[k] = L[i]

i += 1

else:

arr[k] = R[j]

j += 1

k += 1

while i < len(L):

arr[k] = L[i]

i += 1

k += 1

while j < len(R):

arr[k] = R[j]

j += 1

k += 1

# Define a function that sorts the algorithm by brute force

def bruteSort(arr, ascending = False):

# Take the size of the array

N = len(arr)

# Now sort

for i in range(N):

for j in range(i+1, N):

; if ascending:

if arr[i] > arr[j]:

arr[i], arr[j] = arr[j], arr[i] # swap

else:

if arr[i] < arr[j]:

arr[i], arr[j] = arr[j], arr[i]

if __name__ == '__main__':

# Define size

N = 100

# Create array

vals_range = range(1,N+1) # 1 and 10

# Define number of instances

INSTANCES = 10

# Declare variables to store the average time for each sorting algorithm

time1 = 0

time2 = 0

# Now generate arrays and sort them to measure their execution times

for inst in range(INSTANCES):

array = [random.sample(vals_range, N) for _ in range(N)]

# Now, sort each row

startTime = time.time()

for i in range(N):

row = array[i]

if i%2 == 0: # Row index is even: Sort descending

sort(row)

else: # Sort ascending

sort(row, True)

array[i] = row

endTime = time.time()

time1 += (endTime - startTime)

# Now for the second sorting algo

array = [random.sample(vals_range, N) for _ in range(N)]

# Now, sort each row

startTime = time.time()

for i in range(N):

row = array[i]

if i%2 == 0: # Row index is even: Sort descending

bruteSort(row)

else: # Sort ascending

bruteSort(row, True)

array[i] = row

endTime = time.time()

time2 += (endTime - startTime)

# Compute final avg times

time1 = time1 / INSTANCES

time2 = time2 / INSTANCES

print("The average time for Merge Sort is: {:.8f} s".format(time1))

print("The average time for Brute Force Sort is: {:.8f} s".format(time2))